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


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


Мы можем расширить понятие непрозрачного предиката, предположив, что область его определения может быть произвольной (например, множество всех целых чисел, представимых определённым количеством битов). Покажем, что непрозрачные предикаты могут быть реализованы и с использованием указателей, и с использованием массивов.

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

Доказательство. Пусть f - булевский непрозрачный предикат. Пусть f:

m - >
, f записана в базисе
. Построим следующее определение структурного типа на Си.

struct s { struct s *neg; struct s *min[2]; struct s *max[2]; };

Создадим в начале работы программы в динамической памяти ссылочную структуру, показанную на рис. 9.

Здесь элемент, на который указывает Pfalse, соответствует логическому значению "ложь", а элемент, на который указывает Ptrue, соответствует логическому значению "истина".

Рассмотрим каждую булевскую операцию и поставим ей в соответствие операцию над указателями в созданной структуре данных.

  1. xi, где xi - булевская переменная. Ей соответствует переменная pi указательного типа struct s*, которая равна либо Ptrue, либо Pfalse.
  2. u, где u - булевское выражение. Ему соответствует выражение указательного типа e->neg, где e - выражение, соответствующее u.
  3. u v u, где u, v - булевские выражения. Такому выражению соответствует выражение указательного типа e->max[e == f], где e соответствует u, а f - v.
  4. u
    v, где u, v - булевские выражения. Такому выраженю соответствует выражение указательного типа e->min[e == f], где e соответствует u, а f - v.

Рис. 9: Схема построения непрозрачного предиката из указателей

Таким образом, каждому булевскому выражению u мы сопоставили выражение указательного типа e. Поскольку задача определения u

true NP-полна, то и задача определения e == Ptrue также NP-полна. Непрозрачному предикату f соответствует выражение указательного типа f, также являющееся непрозрачным предикатом.




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



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