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


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


Теорема 4.

Если булевские непрозрачные предикаты существуют, то и непрозрачные предикаты, построенные над массивами, существуют.

Доказательство. Пусть е - непрозрачный предикат над указателями, построенный, как показано в предыдущей теореме. Поставим ему в соответствие массив целого типа a из 10 элементов, заполненный следующим образом: int a[10] = { 5, 0, 0, 5, 0, 0, 0, 5, 5, 5 };

Указательному значению Pfalse соответствует целое значение 0, а указательному значению Ptrue - целое значение 5. Тогда выражения непрозрачного предиката, построенного на указателях, заменяются на индексные выражения по следующим правилам:

  1. Переменная pi заменяется на переменную qi целого типа, которая может принимать значения из множества {0,5}.
  2. Выражение e->neg заменяется на выражение a[b], где b - индексное выражение, соответствующее e.
  3. Выражение e->min[f] заменяется на выражение a[b + 1 + c], где b - индексное выражение, соответствующее e, а c - индексное выражение, соответствующее f.
  4. Выражение e->max[f] заменяется на выражение \V{a[b + 3 + c]}, где b - индексное выражение, соответствующее e, а c - индексное выражение, соответствующее f.

Определение 6. Пусть f:

m - >
n. Пусть
=(x1,...,xm),
=(y1,...,yn),
=f(
). Пусть . Множество I - это множество индексов интересующих нас компонент
. Переменная xk называется существенной относительно множества I, если существуют такие x1,...,xk-1,xk+1,...,xm
$ и такая j
I , что выполняется условие fj(x1,...,xk-1,0,xk+1,...,xm).

Теорема 5. Пусть даны m, n, f:

m - >
n, I
2(1,...,n), k. Задача проверки существенности переменной xk относительно множества I (СУЩМНОЖ) NP-полна.

Доказательство. Доказательство принадлежности задачи к классу NP аналогично доказательству теоремы 1. Для доказательства NP-полноты заметим, что задача СУЩ является частным случаем данной задачи, если мы выберем I={1,...,n).

Пусть V={v1,...,vk) - множество переменных замаскированной программы. Предположим, что базовый блок представляет собой вычисление булевской функции f:

m - >
n.


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



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