Увеличение размера графа потока управления

Преобразования перестройки циклов заключаются в том, что в маскируемой функции выбираются подходящие гнёзда циклов и одиночные циклы и над ними выполняются преобразования пространства индексов. К таким преобразованиям относятся:

• Понижение размерности пространства итерирования.

Повышение размерности пространства итерирования.

Изменение порядка обхода пространства итерации.

Аффинные преобразования пространства итерации.

Частичная или полная развёртка цикла.

На этапе перестройки циклов просматриваются все циклы в теле функции. Для каждого цикла проверяются достаточные условия применимости каждого преобразования, определяя таким образом множество доступных преобразований. Затем для каждого цикла программы определяется какое преобразование будет к нему применено, и выполняются преобразования циклов.

На рис. 1 приведён пример применения преобразования понижения размерности индексного пространства к функции перемножения двух матриц. Преобразование позволило перейти от трёхкратного вложенного цикла к единственному циклу.

(a) функция до преобразования	(b) функция после преобразования
Рис. 1. Пример преобразования понижения размерности

Преобразование клонирования базовых блоков заключается в замене последовательного выполнения двух базовых блоков (например, B[i] и B[j]) на оператор разветвления с выполнением копии базового блока B[j] на каждой из ветвей. Для этого базовый блок B[j] должен быть скопирован необходимое число раз. На рис. 2 приведена схема преобразования.

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

На рис. 2 базовый блок B[j] был размножен дважды. Базовый блок B[cond] будет содержать инструкции, необходимые для того, чтобы каждая из трёх копий базового блока B[j] выполнялась примерно с одинаковой частотой. Базовые блоки B[new1], B[new2], B[new3] также могут содержать инструкции для поддержки равномерного распределения потока выполнения по трём альтернативам.

Уже на этапе клонирования базовых блоков начинается построение параллельной "холостой" функции, которая в дальнейшем будет объединена с основной функцией для получения результирующей замаскированной функции.
Типы данных реализации счётчиков, их переменные состояния и инструкции, соответствующие операциями над счётчиками, являются частью параллельной "холостой" функции. Переменная c, которая хранит состояние счётчика, может быть создана как на уровне локальных переменных маскируемой функции, так и вынесена в статические переменные всей единицы компиляции. Последнее позволяет разделять одну и ту же переменную состояния между разными счётчиками разных функций, что полезно ещё и тем, что создаёт в замаскированной программе межпроцедурные зависимости по данным.

В настоящее время в интегрированной среде Poirot реализованы некоторые простейшие виды счётчиков, которые описаны ниже.

• 
  
  Счётчик по модулю. Это - простейший вид счётчика. Состояние счётчика хранится в переменной целого типа, которая размещается на уровне статических переменных единицы компиляции. Операция init заключается в записи в переменную счётчика произвольного числа, например, значения какого-либо параметра функции или глобальной переменной. Операция get заключается во взятии остатка от деления на k текущего значения переменной счётчика. Операция next заключается в прибавлении или вычитании произвольного числа, не кратного k, причём семейство операций next порождается различным выбором этого числа.


Линейный конгруэнтный счётчик. Этот вид счётчика реализует хорошо известный линейный конгруэнтный метод получения псевдослучайных чисел [5]. Операции init и get не изменяются, а операция next определяется как next(cntr)

(C1*cntr+C2)modC3 , где C2 и C3 - взаимно простые числа. Можно также применять полиномиальные конгруэнтные счётчики, а также любой другой алгоритм получения псевдослучайных равномерно распределённых чисел [5].

Криптографические хэш-функции. Для реализации счётчиков могут использоваться криптографические хэш-функции, например, MD5 или SHA [17], или симметричные криптосистемы. Тогда операция next может выглядеть следующим образом next(cntr)

f(cntr

x) . Здесь f - хэш-функция, а x - некоторые произвольные данные, например, значение какой-либо локальной переменной или параметра функции.Отметим, что алгоритмы вычисления криптографических хэш-функций имеют специфический вид (они состоят из побитовых операций с использованием табличныц), и поэтому могут быть достаточно легко опознаны при демаскировке.

Динамические структуры данных. Например, может быть создан кольцевой список, который заполняется числами от 0 до k-1 в произвольном порядке. Операция get состоит в чтении значения текущего элемента списка, а операция next - в продвижении указателя на следующий элемент списка.

Дробление базовых блоков. Это преобразование заключается в том, что базовый блок достаточной длины разделяется на два или более меньших базовых блока. Дробление базовых блоков никак не отражается на коде функции и заключается в модификации вспомогательных структур, используемых для представления графа потока управления.


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

---