Метод защиты программных средств на основе запутывающих преобразований

Если есть обратная дуга т->п, тогда цикл, соответствующий дуге т-їп состоит из вершины п (заголовок цикла) и всех вершин, из которых достигается т, не проходя через п.

Современные языки программирования поддерживают стандартный набор управляющих конструкций (if-then, do-while и пр.). Структур­ные конструкции порождают специфические графы потока управления. Для оператора if-then-else (рис. 3.3(a)) на месте блоков then и else могут находиться другие структурные подграфы. Проанализировав структурные управляющие конструкции, для каждой конструкции можно представить шаблон графа потока управления (рис.3.3).

і

а)

б)

в)

г)

т\

е)

д)

з)

ж)

Рисунок 3.3 - Пример шаблонных конструкций: if-then-else (а), последовательность блоков (б), if-then (в), собственный цикл (г), естественный цикл (д), пример условной области (е), цикл while (ж), пример не сводимой области (з)

60

3.2 Преобразование графа потока управления

Преобразования циклов заключаются в том, что в цикл вносится лож­ное условие, при этом дуга, которая соответствует «истине» переходит внутрь цикла, а дуга, которая соответствует значению «ложь», переходит в начало цикла. Так же возможно создание цикла с двумя и более входами, на­пример, перед началом цикла ставится условие, которое всегда принимает значение «истина», истинная дуга переходит на начало цикла, ложная на ба­зовый блок, который помещается в конец физической последовательности, представляющий данный граф, а выходную дугу из этого блока на начало цикла.

На этом этапе так же используются метки (указатели), перемешивание и их переименование.

На рис. 3.4 приведен граф потока управления для исходного текста программы сортировки методом Шелла (метки L1,L2 иЬЗ для блоков 2 ,4 и 6 соответственно).

Перед операторами while, until, for и foreach, а также перед блоками ставятся указатели. В качестве указателя может использоваться лю­бой идентификатор, который не является зарезервированным словом.

В данном случае применение меток используется для усложнения пе­редачи управления программы, т.е. когда метки используются для передачи управления из внешнего цикла к глубоко вложенному циклу. Оператор пере­хода goto передает управление оператору с указанной меткой и заменяет конструкции if-then-else и циклы.

Все используемые метки рис. 3.4 фиксируют начало цикла. После за­мены циклов на метки, мы получаем множество новых указателей. В резуль­тате получим следующий граф потока, рис. 3.5. Базовые блоки, полученные в результате преобразования, остаются эквивалентными исходному графу.

61

int increment(long inc[], long size) { int pi, p2, p3, s/ pi = p2 = p3 = 1; s = -1; do {

if (++s % 2) {

inc[s] = 8*pl - 6*p2 + 1/} else {

inc[s} = 9*pl - 9*p3 + 1; p2 *= 2; p3 *= 2/ }pl *= 2;} while(3*inc[s] < size)/

return s > 0 ? —s : 0;} template<class T>

void shellSort(T a[], long size) { long inc, i, j, seq[40]/ int s/ s = increment(seq, size)/ while (s >= 0) {

inc = seqts—]/ for (i = inc/ і < size/ i++) { T temp = a[i]/ for (j = i-inc/ (j >= 0) && (a[j] > temp)/ j -= inc)

a[j+inc] = a[j]/a[j+inc] = temp/}}} void main () {    int arr[1000]/ srand(time(NULL))/ int size = 0/ size = sizeof(arr)/sizeof(int)/

for(int і = 0/ і < size/ i++){

arr[і] = rand() - rand()/} for(int і = 0/ і < size/ i++){ printf("%d\t", arr[i])/} shellSort(arr, size)/ for(int і = 0; і < size/ i++){ printf("%d\t", arr[i])/} clock_t tot_time=0/ tot_time = clockO/ float a=0/

a = (float)tot_time / (float)CLKJTCK/

printf("\ntotal time:%f\n%f", a, (float)tot_time)/

getch() / }

О (вход)

12 (выход)

Исходный текст программы

Граф потока управления исходного текста

Рисунок 3.4 - Граф потока управления исходного текста программы сортировки методом Шелла

62

long  inc,   і,   j,   seq[40];   int

s, k;

int  kof[10];k=l;     kof[l]=50;

kof[2]=25;   kof[3]=13;kof[4]=6;

kof[5]=3;     kof[6]=2;   kof[7]=l;

L3:

if   (k<=7)      goto  LI;

else              goto L2;

LI:    {

inc =  kof[k];   i=inc; L5:

if   (Ksize)

goto  L4;

else  goto L6; L4:

{   T temp = a[i];   j   =  i-inc; L9: if   ((j   >=  0)   &&   (a[j]   >  temp))

goto L7;

else  goto L8; L7:

a[j+inc]   = a[j];   j   -= inc;

goto L9; L8:

a[j+inc] = temp;

} i=i++;

goto L5; L6:

k=k++; goto L3;  } L2:}

Текст программы после внесения меток

Граф потока управления после внесения

меток

Рисунок 3.5 - Вид графа потока управления после замены циклов метками

При сравнении графов потока управления исходной и запутанной программы видно, что изменились только метки. Такая программа не вы­зывает особых трудностей даже при синтаксическом анализе.

Преобразование графа потока управления включает в себя введение блока мертвого кода программы и связности между блоками основного и мертвого кода с помощью указателей.

Следуя авторской работе А.В. Чернова, построение блока мертвого кода может осуществляться из нескольких этапов.

Этап создания мертвого кода состоит из следующих под этапов: ■  определение пула типов;

определение пула переменных;

генерация мертвого кода. На рис. 3.6 представлен граф после применения таких преобразований.

Рисунок 3.6 - Вид графа потока управления с внесением мертвого кода

64 Блок 1 рис. 3.6 соответствует указателям L3, Ы (метки имеют иные имена, это связано с прикладной реализацией). Блок 2 соответствует ука­зателям L5, L4, L6. Блок 3 соответствует L9, L7, L7. Блок 4 соответствует мертвому коду.

На следующем этапе, для дальнейшего запутывания применим преобразования структур данных с помощью введения массива для хранения переменных одного типа. Объединение и переупорядочивание элементов массива.

Листинг программы сортировки методом Шелла после объединения

переменных в массив будет выглядеть следующим образом:

long inc,і,j,seq[40];

int  s,k;

intkof[10];k=l;kof[1]=50;kof[2]=25;kof[3]=13;

kof[4]=6;kof[5]=3;kof[6]=2;kof[7]=1;intb[ 50];b[3]=1;

L3:

if   (b[3]<=7)   goto  LI;
else              goto  L2;

LI:

{b[4]   =  kof [b[3]]; b[l]=b[4];

L5:

if   (b[l]<size)     goto L4;
else              goto L6;

L4

{

T  temp =  a[b[l] ] ; b[2]   =b[l]-b[4];

L9

if   ((b[2]   >=  0)   &&   (a[b[2]]   >  temp))   goto L7; else  goto L8;

L7

a[b[2]+b[4]]   = a[b[2]]; b[2]   -= b[4]; goto L9;

L8

a[b[2]+b[4]]   = temp;} b[l]=b[l]++; goto  L5;

L6:

b[3]=b[3]++; goto  L3;} L2:

65 Связность блоков основного и мертвого кода программы осуществля­ется с помощью введения в тело этих блоков меток (указателей), что явля­ется трудноанализируемым свойством программы для проведения стати­ческого и синтаксического анализа. Кроме того, переменные одного типа мертвого и основного кода объединены в массив и используются в теле функций выполнения блоков только индексы массива. Чтобы затруднить анализ элементы массива заполняются случайным образом. Массив со­держит переменные, которые вычисляются основной функцией програм­мы и переменные, которые используются при перевычислении.

Полученный граф потока управления после таких преобразований представлен на рис. 3.8, и имеет свойство конечного графа 32-го порядка и размерностью 43.

Рисунок 3.8 - Граф потока управления запутанного кода программы

66

Листинг программы для графа потока управления представленного

рис. 3.7 выглядит следующим образом: long  inc,   і,   j,   seq[40];

int  d,s,k,h=4,q=ll;int   kof[10];int  b[50]; k=l;b[ll]=5;b[21]=-6;kof[3]=13;b[13]=7;b[23]=-8; kof[4]=6;kof[5]=3;b[24]=-9;b[34]=5;kof[6]=2;kof[7]=1; b[33]=4;b[31]=2;kof[1]=50;kof[2]=25;b[12]=6;b[22]=-7; b [32] =3;b [14] =8; goto L20;

Ll:{b[4]   =  kof [b[3] ] ;b[l]=b[4] ; goto L5; L20:

if   (h>l){b[l]=b[ll]+b[21]+b[31];b[2]=b[12]+b[22]+b[32]; b[3]=b[13]+b[2 3]+b[3 3];b[4]=b[14]+b[2 4]+b[3 4];

goto  L21;}

else  goto Ll; L6:b[3]=b[3]++;   goto  L3;   L4:{T  temp  =  a[b[l]];

b[2]   =b[l]-b[4]; goto L9;

L7:a[b[2]+b[4]]   = a[b[2]];   b[2]   -= b[4];goto  L9; L9:   if   ((b[2]   >= 0)   &&   (a[b[2]]   >  temp))   goto     L7;

else  goto  L8; L8:   a[b[2]+b[4]]   =  temp;   } b[l]=b[l]++;   goto  L5;} L21:   if   (q<12)    {h=5;   goto L22;} L5:   if   (b[l]<size)   goto  L4;

else  goto L6; L3:   if   (b[3]<=7)   goto  Ll;

else  goto L2; L22:   if   (d=5)

{b[3]=b[13]+b[23]+b[33];b[4]=b[14]+b[24]+b[34];}

goto Ll;   L2:

68

3.5 Теоретическое обоснование устойчивости метода

Для теоретического обоснования устойчивости метода используется ап­парат дискретной математики, теории схем программ, машин Тьюринга [20, 21,22,76,83].

Пусть S = {0,1}, poly{n) - произвольный многочлен от переменной п.

Определение 1. Пусть f: Sm -> S", т = poly(ri).

Функция / (отображение) называется односторонней функцией, если

для любого xeSm существует полиномиальный алгоритм вычисления значе­ний  f(x)   и  не существует полиномиального алгоритма инвертирования

функции /. Для любой полиномиальной вероятностной машины Тьюринга

РгТ выполнено следующее:

P{f{A{f(x))) = f(x)} < Vpolyim).

Вероятность здесь определяется случайным выбором х и случайными величинами, которые Ргт использует в своей работе.

Определение 2. Взаимнооднозначная односторонняя функция f:S"->Sn называется односторонней перестановкой.

Определение 3. є -приближённым алгоритмом решения оптимизацион­ной задачи называется алгоритм, находящий решение не более чем в є раз хуже оптимального решения.

Пример. Задача М минимизации некоторого функционала /.

Пусть А - є -приближённый алгоритм нахождения решения задачи М. Пусть для некоторой реализации задачи оптимальное значение функционала равно X. Тогда алгоритм А найдёт решение задачи, при котором значение / равно Y, причём будет справедливо неравенство X < Y < РХ.

Определение 4. Пусть f:Sm^S", x = {xx,...,xm), У = (ух,.-.,уп), y = f{x). Переменная хк называется существенной, если существуют

\Х\)...,Хк_\,Хкл.\,...,Хт) Є о   И J Є \1,...,Щ

такие, что выполняется условие:

69 J j\xx,...,xk_x,\),xk+x,...,xm) Ф jj{xl,...,xk_l,i,xk+l,...,xm).

Теорема 1. Пусть f:Sm^>Sn, f записана как система булевых формул в базисе {и.п,-,}, 1 < к < т.

Задача проверки существенности переменной хк NP -полна.

Доказательство.

Пусть ех Ф ег = (ех п е2) и (ех п е2),

где ех, е2 - булевы формулы.

Обозначим х = (хх,...,хт), у = (у1,...,уя) и *|/=а= (*,,.. jrM,o-,*/+1,...xJ.

1.              Задача существенности находится в классе NP.

                            п                                                       

Пусть g(x) = \J(fj(x\i^)^(fj(x\i=x)) булева формула.

Если переменная существенна, то существует такой вектор х, для кото­рого g(x) = 1. Если переменная не существенна, то на всех наборах х выпол­няется g(x) = 0.

И наоборот, если g(x) принадлежит языку «выполнения» (выполняется),

то переменная хк существенна. Если g(x) не принадлежит языку «выполне­ния», то хк - не существенна.

*S              Таким образом, задача проверки существенности сведена к задаче про-

верки выполнимости булевой формулы. Последняя находится в классе NP. Следовательно, и задача проверки существенности находится в классе NP, как показано в работе Чернова А.В. [83] и Ященко В.В.

2.              Задача выполнения, которая является NP - полной, полиноми­
ально сводится к задаче существенности.

"#*              Пусть g{x) - некоторая формула в базисе {u,n,-,}. Тогда формула, реали-

зующая функцию / = 1, принадлежит языку «выполнения», но ни одна пере­менная в такой формуле не является существенной.

70 В формуле, реализующей функцию f = 0, которая не принадлежит язы­ку «выполнения», также нет существенных переменных. Все прочие форму­лы, принадлежат языку «выполнения», и хотя бы одна переменная в них яв­ляется существенной. Таким образом, формула не принадлежит «выполне­нию», если её значение на любом битовом наборе равно 0, и в ней нет суще­ственных переменных.

Для проверки выполнимости формулы нужно проверить её значение в одной точке и т раз проверить существенность переменных формулы. Сле­довательно задача выполнения полиномиально по Тьюрингу сводится к зада­че существенности, что доказывает NP -полноту последней.

Определение 5. Пусть f:Sm->Sn,x = (xlt...,xm), у = (yv...,yn), у = f(x). Пусть множество / - это множество индексов компонент у.

Переменная хк называется существенной относительно множества /, если существуют такие (xv...,xk_x,xk+x,...,xm) є £ и такая j є І, что выполняет­ся условие f.{xv...,xk_x,Q,xM,...,xm).

Теорема 2. Пусть даны т, п, f:Sm->Sn, I £ 2(1--л), к. Задача проверки существенности переменной хк относительно множества / NP -полна.

Доказательство принадлежности задачи к классу NP аналогично дока­зательству теоремы 1.

Пусть / = {1,...,«} задача существенности является частным случаем для

доказательства NP.

Определение 6. Задача анализа зависимостей по данным определяется как задача нахождения минимального множества переменных Win с Vin тако­го, что переменные из множества Vin-Wы несущественны относительно W

где V = {vx,...,vk} - множество переменных запутанной программы,

/ :Sm -» S" - базовый блок представляющий вычисление булевой функ­ции над переменными из Vin;

71

Vin Q V,\Vin\ = m - переменные, значения которых используются при вы­числении /,

Уош Я: V, \У0Ш\ = п - переменные, которые получают новые значения в ре­зультате вычисления, если для некоторой переменной veVin и veV0Ut, при вычислении используется старое значение переменной;

Wout с Vout - множество «существенных» переменных на выходе из базо­вого блока.

Теорема 3. Задача ЗАВ NP-полна.

Доказательство.

Принадлежность задачи классу NP следует из того, что для каждого / такого, что (1 < і < к) можно найти решение задачи существенности относи­тельно множества (то есть определить принадлежит ли множеству Vin). Далее за полиномиальное время проверяется, что |^л|</, число /такое, что (0</<£).

Определение 7. «Мёртвые» инструкции - это инструкции, которые отно­сятся к вычислению несущественных переменных.

Из доказанного выше следует, что задача выявления мёртвого кода в программе, состоящей из одного базового блока, NP- полна, и, более того, не существует £-приближённого полиномиального алгоритма выявления мёртвого кода.

Переменные произвольных целых типов могут рассматриваться как на­бор переменных булева типа.

3.6 Практическое обоснование устойчивости метода

Устойчивость запутанной программы к автоматическому анализу обос­новывается следующим:

- При статическом анализе массивов невозможно сделать анализ с точ­ностью до каждого элемента массива. Следовательно, такой анализ окажется не эффективным.