Информационная безопасность


Преобразования потока управления - часть 2


Непрозрачные предикаты могут быть трёх видов: PF - предикат, который всегда имеет значение "ложь", PT - предикат, который всегда имеет значение "истина", и P? - предикат, который может принимать оба значения, и в момент запутывания текущее значение предиката известно.

В работах [3], [7], [23] разработаны методы построения непрозрачных предикатов и переменных, основанные на "встраивании" в программу вычислительно сложных задач, например, задачи 3-выполнимости . Некоторые возможные способы введения непрозрачных предикатов и непрозрачных выражений вкратце перечислены ниже.

  • Использование разных способов доступа к элементы массива [23]. Например, в программе может быть создан массив (скажем, a), который инициализируется заранее известными значениями, далее в программу добавляются несколько переменных (скажем, i}, j), в которых хранятся индексы элементов этого массива. Теперь непрозрачные предикаты могут иметь вид a[i] == a[j]. Если к тому же переменные i} и j в программе изменяются, существующие сейчас методы статического анализа алиасов позволят только определить, что и i, и j могут указывать на любой элемент массива a.

  • Использование указателей на специально создаваемые динамические структуры [7]. В этом подходе в программу добавляются операции по созданию ссылочных структур данных (списков, деревьев), и добавляются операции над указателями на эти структуры, подобранные таким образом, чтобы сохранялись некоторые инварианты, которые и используются как непрозрачные предикаты.

  • Конструирование булевских выражений специального вида [3].

  • Построение сложных булевских выражений с помощью эквивалентных преобразований из формулы true. В простейшем случае мы можем взять k произвольных булевских переменных x1...xk и построить из них тождество

    . Далее с помощью эквивалентных алгебраических преобразований часть скобок (или все) раскрываются, и в результате получается искомый непрозрачный предикат.
  • Использование комбинаторных тождеств, например

    .




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



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