WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     | 1 || 3 |

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

M П O O*, O* П :A( O( M )) П,A( O( M )) P (1), где П – множество всех программ, процесс работы которых имеет конечный результат;

M – программа из множества П;

O – алгоритм обфускации;

O* - семейство алгоритмов обфускации;

P – множество алгоритмов полиномиальной сложности;

A – алгоритм деобфускации, принимающий на вход запутанный алгоритм O( M ).

Во второй главе рассматривается модифицированный теоретический аппарат, который описывает процесс обфускации, как добавление в программу избыточного функционала, что и является основным смыслом этого процесса.

В связи с этим под функциональным свойством подпрограммы понимается описатель логики, которую выполняет данная подпрограмма. Для функциональных свойств справедливо следующее:

p1, p2 П( f = f ( p1 p2 )), (2) p1 pгде - функциональное свойство подпрограммы;

П – множество всех подпрограмм;

p1, p2 - подпрограммы, принадлежащие множеству П;

f, f - функции, вычисляемые соответственно подпрограммами p1, p2.

p1 pВведем левостороннюю операцию «*», означающую конкатенацию функциональных свойств. Запись 1 * означает, что подпрограмма с функциональным свойством выполняется сразу же за подпрограммой с функциональным свойством 1. Таким образом, некоторую подпрограмму, обладающую функциональным свойством исх, можно представить следующим образом:

исх = 1* 2 *...* n (3) После применения запутывающих преобразований получим следующее:

исх = * * 1 *1 * * *...* * (4) 0 0 2 2 n n,1,,..., - добавленные функциональные свойства.

0 2 n = e, где e – единичное функциональное свойство, т.е. функциональное свойство подпрограммы, не влияющей на входные и выходные данные.

Заметим, что если,1,,..., из предыдущей формулы равняются e, 0 2 n то это равенство будет сводиться к системе равенств следующего вида:

0 = = e = 1 * e = * e (5) 2..........................

n = n * e Предположим теперь, что = 0 * * 1 *1 * * *...* * исх (6) 0 2 2 n n В этом случае несводимость неравенства (6) к системе (5) достаточно несложно обеспечить. Докажем следующее утверждение.

Задача определения существенности функционального свойства i(i ) в равенстве (6) NP-полна.

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

( Xi Yi ), (7) i где X – выходные данные, полученные до исключения функционального свойства, Y - выходные данные, полученные после исключения функционального свойства. Если результат формулы (7) не будет нулевым, то исключенное функциональное свойство будет существенным. Очевидно, что задача определения существенности функционального свойства сводится к задаче выполнимости булевской формулы, а, следовательно, лежит в классе NP.

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

Из вышесказанного следует, что задача определения существенности функциональных свойств в равенстве (6) NP-полна.

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

1. Маскировка графа потока управления подпрограммы (в частности, адрес, на который передается управление из инструкции ветвления, рассчитывается динамически, исходя из хеш-суммы подпрограммы).

2. Граф потока управления подпрограммы должен быть неприводимым.

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



3. Определения «фальшивых» переменных не должны уничтожаться в конце подпрограммы. Под «фальшивыми» переменными понимаются переменные, добавленные в процессе обфускации для усложнения понимания логики работы запутанного кода.

4. Определения «фальшивых» переменных не должны уничтожаться до того, пока эти переменные хоть раз не были использованы.

5. Множества ячеек памяти для исходного и добавленного в процессе обфускации контекстов, с которыми работает запутанная программа, должны соответствовать системе (8).

R R V VFAKE, (8) REAL W W VFAKE VREAL R R где VREAL,VFAKE - множества всех ячеек памяти, из которых производят чтение соответственно исходные и добавленные в результате применения запутывающих преобразований инструкции;

W W VREAL,VFAKE - множества всех ячеек памяти, в которые производят запись соответственно исходные и добавленные в результате применения запутывающих преобразований инструкции;

- пустое множество.

6. Определения глобальных «фальшивых» переменных должны уничтожаться тогда и только тогда, когда данная глобальная переменная используется в качестве одного из параметров в определении, уничтожающем её предыдущее значение.

7. «Мертвый» код (код, на который не предусмотрена передача управления в процессе нормального функционирования программы) не должен сильно отличаться от реально выполняемого кода. Все правила, приведенные выше, должны относится, в том числе, и к нему.

В главе 3 описаны разработанные методики обфускации. Данные методики используют глобальный, по отношению к запутываемому блоку, контекст для обеспечения стойкости к автоматическим алгоритмам деобфускации. Процесс запутывания выглядит следующим образом:

1. Анализ входных данных.

2. Добавление «фальшивого» локального контекста.

3. Генерация «мусорного» кода (кода, добавленного в процессе обфускации).

4. Разбавление инструкций ветвления.

5. Маскировка графа потока управления (динамическое вычисление адресов ветвлений).

6. Разбиение полученных базовых блоков на набор функций.

7. Генерация машинных инструкций с использованием генератора полиморфного кода.

Рассмотрим более подробно каждый из пунктов.

1. Методика анализа входных данных подразумевает под собой разбиение на базовые блоки, анализ псевдонимов, перевод в промежуточное представление, распознавание неделимых блоков памяти (структур, массивов и т.д.), выделение операция память-память (частичная оптимизация).

Алгоритмы разработаны для архитектур x86 и AMD64, но могут быть легко модифицированы для использования на других аппаратных платформах.

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

Перевод в промежуточный код производится сразу после анализа псевдонимов. Основной задачей данного этапа является необходимость избавления от флагов и стека. Абстрагирование от флагов производится либо непосредственным сравнением операндов (с помощью инструкции промежуточного кода if) - либо введением дополнительной переменной, которая впоследствии будет использована в инструкции if. Типы операндов могут быть следующими:

UNKNOWN – тип, о котором невозможно получить информацию;

LOC_PTR – указатель на локальную память функции;

GLOB_PTR – указатель на память, глобальную по отношению к функции;

ARG_PTR – указатель на аргумент;

UNKNOWN_PTR – указатель на неизвестную область памяти;

CONST – константное значение.

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

В процессе анализа каждая переменная представляется следующей тройкой значений. (MemId, Offset, Size), где MemId – идентификационный номер области памяти, Offset – смещение начала абстрактной ячейки относительно точки отсчета, а Size – размер ячейки. Смещение в данном случае удобно считать от адреса возврата, который имеет нулевое смещение.

Для удобства анализа доступа к памяти введем понятие множества значений для каждой переменной (vs). Множества значений удобно записывать в виде сжатых интервальных конгруэнций (RIC) каждая из которых представляет собой кортеж из 4-х значении (a, b, c, d) и трактуется следующим образом:

a [ b,c ] + d, что описывает множество целых значений { aZ + d | Z [ b,c ]}.

Ниже приведен ряд операций, которые можно применять по отношению к множествам значений:

–( vs1 vs2 ): возвращает TRUE, если множество значений vs1 является подмножеством vs2.

–( vs1 vs2 ) : возвращает пересечение множеств значений vs1 и vs2.

–( vs1 vs2 ) : возвращает объединение множеств значений vs1 и vs2.

–( vs1vs2 ): возвращает множество значений, полученное посредством расширения множества значений vs1 по отношению к vs2. Т.е., если vs=(10,4[0,1]), а vs2 =(10,4[0,2]), то ( vs1vs2 )= (10,4[0,]).

–( vs c ) : возвращает множество значений, полученное в результате «подстройки» значений vs с константой c. Т.е., если vs =(4,4[0,2]+4), а c=12, то ( vs c ) =(16,4[0,2]+16). Аналогичным образом может быть задан целый ряд арифметических операций.

–* ( vs,s ) : возвращает пару множеств (F, P). F представляет собой множество «полностью доступных» абстрактных ячеек памяти (т.е. ячеек памяти размером s и их стартовый адрес находится в vs). P представляет собой множество «частично доступных» ячеек памяти. Т.е. ячеек памяти у которых стартовый адрес лежи в vs, а размер не равен s, а также ячеек, которые лежат в vs, но их стартовый адрес и размер не удовлетворяют требованиям к множеству F.

–RemoveLowerBounds(vs): возвращает множество значений, полученное посредством установки нижней границы каждого компонента RIC равного. Например, если vs =([0, 100],[0, 200]), то RemoveLowerBounds(vs)= ([-, 100],[ -, 200]).

–RemoveUpperBounds(vs): аналогично RemoveLowerBounds, но устанавливает верхнюю границу каждого компонента равной.

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

а) внешняя функция уже проанализирована с учетом того, что её параметры неизвестны;

б) внешняя функция еще не проанализирована.

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

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

Распознавание неделимых блоков памяти производится на основе информации о множествах значений абстрактных ячеек памяти.

Консервативным решением будет перебор всех множеств значений для каждого из операндов и вычисление операции *( vs,s ) для каждого из RIC.

Полученные множества F, P и будут являться искомыми массивами абстрактных ячеек памяти, которые в свою очередь являются неделимыми блоками памяти.

Далее проводится дополнительный анализ входных данных, который включает в себя следующие пункты:

а) выделение множества «мертвых» локальных переменных D. Т.е.

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

б) выделение множества переменных, имеющих простые типы (множество C);

в) выделение множества переменных, имеющих сложные типы (CO);

г) выделение абстрактных ячеек памяти, являющихся элементами неделимых блоков памяти, которые уже были использованы в подпрограмме, как единое целое и после прохождения определенной точки графа потока управления, как единое целое, в подпрограмме не используются (множество CA);

д) выделение абстрактных ячеек памяти, являющихся элементами неделимых блоков памяти, которые используются порознь в пределах одного или нескольких базовых блоков (множество CB). Такие переменные можно переносить в «фальшивый» локальный контекст только в пределах границ этих базовых блоков. В последствии значения этих ячеек памяти должны быть восстановлены;

е) Выделение множества абстрактных ячеек памяти с заведомо известными значениями (множество V).

2. Добавление «фальшивого» локального контекста. На данном этапе добавляется «фальшивый» локальный контекст, который будет впоследствии использоваться для создания «мусорного» кода и обеспечения полиморфизма. Локальный контекст перекомпоновывается в целях усложнения анализа данных. Перекомпоновка означает перенос части локальных переменных в область памяти «фальшивого» контекста. Область памяти, откуда этот перенос произошел, используется для работы «мусорного» кода. Переносить можно переменные из множеств C, CO, CA (после прохождения определенной точки) и CB (в пределах базового блока).

Pages:     | 1 || 3 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»