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


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


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

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

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

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

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

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

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

На рис. 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] также могут содержать инструкции для поддержки равномерного распределения потока выполнения по трём альтернативам.

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


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



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