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



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


Теорема 4.

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

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

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

  • Переменная pi заменяется на переменную qi целого типа, которая может принимать значения из множества {0,5}.
  • Выражение e->neg заменяется на выражение a[b], где b - индексное выражение, соответствующее e.
  • Выражение e->min[f] заменяется на выражение a[b + 1 + c], где b - индексное выражение, соответствующее e, а c - индексное выражение, соответствующее f.
  • Выражение 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.


    Содержание  Назад  Вперед