Разрушение структурности графа потока управления

Эта группа маскирующих преобразований включает зацепление дуг и создание псевдоциклов.

Зацепление дуг. Схема преобразования показана на рис. 3. Для преобразования выбираются две случайных дуги графа потока управления функции. При этом предпочтение отдаётся "далёким" друг от друга дугам, где расстояние измеряется как минимальное из длин двух кратчайших путей по графу от конца одной дуги к началу другой. Две выбранные дуги не должны иметь общее начало или общий конец. Ключевым для обеспечения надёжности зацепления дуг является предикат P, который в конце выполнения нового базового блока B[new] гарантирует возврат на "правильный" путь выполнения. Такой предикат мы назовём возвращающим.

До преобразования после выполнения базового блока B[from1] всегда выполнялся базовый блок B[to1], а после базового блока B[from2] всегда выполняется базовый блок B[to2]. В результате выполнения этого преобразования создаётся новый базовый блок B[new], который выполняется и после B[from1], и после B[from2]. Новый базовый блок завершается вычислением предиката P, в зависимости от которого управление передаётся либо на базовый блок B[to1], либо на базовый блок B[to2]. Предикат P должен гарантировать, что управление вернётся на ту ветвь, с которого оно пришло в блок B[new]. Методы генерации предикатов, удовлетворяющих этому требованию, будут рассмотрены ниже.

Интегрированная среда Poirot предусматривает гибкий интерфейс для подключения новых возвращающих предикатов. Добавление очередного возвращающего предиката при маскировке программы производится посредством интерфейса ReturnPredicateFactory. Интерфейс к методам генерации кода для возвращающих предикатов называется ReturnPredicateGenerator. Оба интерфейса приведены на рис. 4.

Реализованы некоторые простейшие виды возвращающих предикатов. Простейший вид возвращающего предиката - это обычная булевская переменная. Переменная может быть объявлена как на уровне локальных переменных, так и на уровне глобальных переменных.

Возвращающие предикаты могут быть построены на основе хэш-функций. Пусть хэш-функция f отображает целочисленный тип в булевский. Введём переменную v, которую будем использовать как аргумент f. Таким образом, предикат P равен f(v). Установка


(a) Исходный граф.	(b) Преобразованный граф
Рис. 3. Схема преобразования зацепления дуг

public interface ReturnPredicateFactory { public String getReturnPredicateKindName(); public String getReturnPredicateKindDescription(); public boolean mayGenerateJumps(); public ReturnPredicateGenerator newInstance (ObfuscationEnvironment env); } public interface ReturnPredicateGenerator { public ReturnPredicateFactory getFactory(); public MIFInstr emitType(MIFInstr p); public MIFInstr emitGlobalDecl(MIFInstr p); public MIFInstr emitLocalDecl(MIFInstr p); public MIFInstr emitSetFalse(MIFInstr p); public MIFInstr emitSetTrue(MIFInstr p); public MIFInstr emitTest(MIFInstr p, MIFElem e, MIFInstr d[]); public Set getDepends(); public MIFInstr emitInit(MIFInstr p); public MIFInstr emitFini(MIFInstr p); }

Рис. 4 Интерфейсы для возвращающих предикатов

значения P в true эквивалентна присваиванию переменной v любого значения x, на котором f(x) = true. Такие значения x могут браться из массива Ptrue, который индексируется произвольным выражением e. Тогда установка значения предиката P в true выполняется присваиванием v < - Ptrue[e]. Установка значения предиката P в false выполняется аналогично.Для построения возвращающих предикатов могут быть использованы динамические структуры данных, аналогично тому, как они использовались для построения счётчиков.


(a) Исходный граф.	(b) Преобразованный граф
Рис 5. Схема построения "псевдоцикла"

Размещение возвращающих предикатов обычно обладает существенным недостатком, снижающим степень его устойчивости. Все операции с возвращающим предикатом сконцентрированы в небольшой области графа потока управления. Используется два способа преодоления этого недостатка. Во-первых, инструкции установки значения возвращающего предиката помечаются как кандидаты на продвижение вверх в графе потока управления функции.

На заключительном шаге перемешивания инструкций эти инструкции будут перемещены вверх как можно выше. Во-вторых, инструкции инициализации возвращающих предикатов могут быть размещены не в самих базовых блоках B[from1] или B[from2], а в базовых блоках, из которых управление может попасть только в нужный блок.

Создание псевдоциклов. Преобразование состоит во внесении в граф потока управления функции обратной дуги. При этом контролируется, чтобы тело полученного цикла выполнялось только один раз. Схема преобразования показана на рис. 5. Здесь сцепляются дуги B[i1]->B[i2] и B[i2]->B[i3]. Предикат P, находящийся в конце базового блока B[new], должен обеспечить однократное выполнение базового блока B[i2].

Устойчивость преобразования создания псевдоцикла к анализу определяется устойчивостью возвращающего предиката. В отличие от преобразования зацепления дуг, в котором инструкции установки значения возвращающего предиката P могут быть размещены достаточно "далеко" от точки зацепления дуг, преобразование создания псевдоцикла более ограничено. Установка значения предиката P, чтобы управление покинуло псевдоцикл, не может быть вынесено из блока B[i2].

Содержание раздела