О некоторых задачах анализа и трансформации программ (стр. 4 из 8)

На Рис. 5 показан пример применения маскирующего преобразования внесения тождеств к программе, вычисляющей функцию Фибоначчи. Преобразование основано на малой теореме Ферма

для любого целого a, такого, что , и простого числа p). В таблице 2 приведена цена применения маскирующего преобразования и полученное усложнение программы. Для этого примера цена равна 3.83, а усложнение программы - 4.85. Расстояние между исходной и замаскированной программой равно 21.

LC	UC	YC	DC
Исх. процедура fib	12	0	0.1111	14
Замаскированная fib	23	0	0.3086	29

Таблица 2. Оценка влияния маскирующего преобразования внесения тождеств

Другое маскирующее преобразование - введение непрозрачных предикатов - является ключевым для повышения устойчивости других маскирующих преобразований, например, внесения недостижимого кода. Непрозрачным предикатом называется предикат, всегда принимающий единственное значение true или false. При маскировке программы предикат строится таким образом, что его значение известно, но установить по тексту замаскированной программы, является ли некоторый предикат непрозрачным, трудно. В работе рассматриваются методы построения непрозрачных предикатов, использующие динамические структуры данных и булевские формулы.

На основании определения устойчивости маскирующих преобразований, дан-ного выше, становится возможным провести анализ всех опубликованных маскирующих преобразований для выявления их устойчивости по отношению к нашему множеству демаскирующих преобразований и алгоритмов анализа. Мы можем ввести количественную классификацию маскирующих преобразований и выявить наиболее устойчивые маскирующие преобразования. Для этого вводятся - эвристическая оценка CL сложности анализа, которая устанавливает глубину анализа замаскированной программы, необходимого для выполнения демаскирующего преобразования, и эвристическая оценка SL степени поддержки демаскировки, устанавливающая необходимую степень участия человека в процессе демаскировки. Для оценки CL используется шкала, приведённая в таблице 1. Для оценки SL используется шкала: "автоматический анализ" (0 баллов), "полуавтоматический анализ" (1 балл), "ручной анализ с развитой инструментальной поддержкой" (2 балла), "только ручной анализ" (3 балла). Итоговая оценка DL трудоёмкости анализа равна

DC=CL+SL

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

Таким образом можно получить количественную классификацию маскирующих преобразований. Для каждого маскирующего преобразования приводится оценка сложности маскировки и оценка трудоёмкости демаскировки. Значение, получаемое как разность оценки трудоёмкости демаскировки и оценки сложности маскировки, позволяет оценить насколько демаскировка данного маскирующего преобразования сложнее, чем маскировка. Исходя из этого определяются маскирующие преобразования, применение которых неоправдано, например, переформатирование программы, разложение циклов, локализация переменных; методы маскировки, которые следует применять только в комплексе с другими методами, например, изменение идентификаторов, внесение дублирующего кода и методы маскировки, применение которых наиболее оправдано, например, внесение тождеств, переплетение процедур, построение диспетчера, повышение косвенности. Сравнение двух маскирующих преобразований приведено в таблице 3. Через D обозначена разность OC-DL, через ρ1 обозначено расстояние между текстами замаскированной и исходной программ fib, а через ρ2 - расстояние между текстами демаскированной и исходной программ. Из таблицы следует, что маскирующее преобразование построения диспетчера предпочтительнее, так как, при равных с методом внесения тождеств трудо-затратах на демаскировку, обеспечивает лучшее соотношение усложнения программы к цене преобразования.

Преобразование	OC	TC	MC	ρ1	CL	SL	DL	ρ2	D	<>
Внесение тождеств	2	3.83	4.85	21	4 - 5	2	7	0	5	1.27
Построение диспетчера	2	3.83	6.14	39	5	2	7	2	5	1.60

Таблица 3. Сравнение методов маскировки

3.3. Новый метод маскировки программ

Новый метод маскировки программ мы далее обозначим аббревиатурой "ММ". Его более подробное описание можно найти в [2]. Метод ММ применяется к функциям маскируемой программы по отдельности, при этом структура маскируемой программы в целом не изменяется. Для изменения структуры маскируемой программы могут применяться стандартные методы открытой вставки и выноса функции, которые, однако, не являются частью предлагаемого метода маскировки.

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

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

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

Общая идея метода может быть охарактеризована следующим образом.

Во-первых, значительно увеличить сложность графа потока управления, но так, чтобы все дуги графа потока управления, внесённые при маскировке, проходились при выполнении программы. Это позволяет преодолеть основную слабость "непрозрачных" предикатов: насколько бы не были они сложны для статического анализа программы, полустатический анализ позволяет выявить такие предикаты (точнее, порождённые ими несущественные дуги графа потока управления) с большой долей уверенности.

Во-вторых, увеличить сложность потоков данных маскируемой функции, "наложив" на неё программу, которая заведомо не влияет на окружение маскируемой функции и, как следствие, не изменяет работы программы. "Холостая" функция строится как из фрагментов маски-руемой функции, семантические свойства которых заведомо известны, так и из фрагментов, взятых из библиотеки маскирующего трансля-тора. Чтобы затруднить задачу выявления холостой части замаскиро-ванной функции используются как языковые конструкции, трудно поддающиеся анализу (указатели), так и математические тождества.

Метод маскировки можно разбить на несколько этапов:

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

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

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

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

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

Метрика	queens	MM(queens)	CM(queens)
LC	49	711	4171
YC	0.595	0.8119	0.2402
UC	0	0	0
DC	82	8964	143807

Таблица 4. Изменение метрик для замаскированной процедуры queens