Об одном методе маскировки программ


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


Пусть Vin
V,|Vin|=m - переменные, значения которых используются при вычислении f, а Vout
V, |Vout|=n - переменные, которые получают новые значения в результате вычисления. Если для некоторой переменной v
Vin и v
Vout, при вычислении используется старое значение переменной. Пусть Wout
Vout - множество "существенных" переменных на выходе из базового блока (например, это могут быть переменные, значения которых печатаются, или переменные, значения которых интересны нам по другой причине). Определим задачу анализа зависимостей по данным (ЗАВ) как задачу нахождения минимального множества переменных Win
Vin такого, что переменные из множества Vin - Win несущественны отностительно Wout.

Данной оптимизационной задаче соответствует задача проверки свойств ЗАВ: дано множество булевских переменных V={v1,...,vk}, булевская функция f:

m - >
n над переменными из Vin, подмножество Wout
Vout , число p (0
p
k). Существует ли множество Win
Vin , |Win|
p такое, что переменные Vin - Win несущественны отностительно Wout.

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

Доказательство Принадлежность задачи классу NP следует из того, что для каждого i (1

i
k ) можем найти решение задачи СУЩМНОЖ, то есть определить принадлежит ли множеству Vin. Далее за полиномиальное время проверяется, что |Win|
p.

Для доказательства NP-полноты покажем, как задача СУЩМНОЖ сводится к данной задаче. Пусть f - булевская функция f:

m - >
n . Предположим для определённости, что f записана в виде КНФ. Для определённости будем считать, что x1=v1,...,xm = vm - переменные, используемые при вычислении функции, а y1 = vm+1,...,yn = vm+n - переменные, получающие своё значение. Пусть требуется проверить существенность переменной xk относительно множества I.

Введём m-1 новую переменную z1,...,zm-1 следующим образом: каждое вхождение xk в формулу для вычисления f заменим выражением xk v z1 v...v zm-1, а выражение - на выражение

. В результате получим функцию f1 :
2m-1 - >
n , которая также записана в КНФ.

Если переменная xk существенна для f, то переменные xk,z1,...,zm-1 окажутся существенными для f1 .


Начало  Назад  Вперед



Книжный магазин