На правах рукописи

Щелкунов Дмитрий Анатольевич

РАЗРАБОТКА МЕТОДИК ЗАЩИТЫ ПРОГРАММ ОТ АНАЛИЗА И

МОДИФИКАЦИИ НА ОСНОВЕ ЗАПУТЫВАНИЯ КОДА И ДАННЫХ

Специальность 05.13.19 – Методы и системы защиты информации,

информационная безопасность

Автореферат

диссертации на соискание ученой степени кандидата технических наук

Москва – 2009

Работа выполнена в Московском Государственном Техническом Университете им. Н.Э. Баумана.

Научный руководитель: кандидат технических наук, доцент Мазин Анатолий Викторович

Официальные оппоненты: доктор технических наук, старший научный сотрудник Тарасов Александр Алексеевич кандидат технических наук, старший научный сотрудник Половников Алексей Юрьевич

Ведущая организация: Всероссийский Научно-Исследовательский Институт Проблем Вычислительной Техники и Информатизации

Защита диссертации состоится 2009 г. на заседании Диссертационного совета ДС 212.008.10 при Московском Государственном Техническом Университете им. Н.Э. Баумана по адресу 107005, г. Москва, 2я Бауманская ул., д.5.

С диссертацией можно ознакомиться в библиотеке МГТУ им. Н.Э. Баумана.

Отзыв на автореферат в одном экземпляре, заверенный печатью, просим направлять в адрес Совета университета.

Автореферат разослан « _ » _ 2009 г.

Ученый секретарь Диссертационного совета к.т.н., доцент А.В. Астрахов

Общая характеристика работы

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

Основы методологии создания подобного рода механизмов заложены такими учёными, как Варновский Н.П., Захаров В.А., Гайсарян С.С, Чернов А.В, Коллберг К.

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

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

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

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

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

Объектом исследования является автоматическая защита программного обеспечения от анализа и несанкционированной модификации.

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

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

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

В рамках решения указанной задачи в диссертации:

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

2. Сформулирована и доказана теорема о NP-полноте задачи деобфускации.

3. Обосновано применение разработанных правил построения запутывающих преобразований.

4. Разработана методика статического и полустатического анализа машинного кода программы с целью его последующего перевода в промежуточное представление.

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

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

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

Положения, выносимые на защиту 1. Формулировка и доказательство теоремы о NP-полноте задачи деобфускации в случае добавления к запутываемой программе дополнительных входных и выходных данных.

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

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

Научная новизна диссертации заключается в следующем:

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

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

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

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

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

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

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

Реализация результатов диссертационной работы Основные результаты диссертационной работы внедрены в российских компаниях ЗАО «Актив», ЗАО «Калуга-Астрал» и ФГУП КНИИТМУ, а также в учебный процесс КФ МГТУ им. Н.Э. Баумана в курсах «Организация информационной безопасности» и «Защита информации в компьютерных сетях».

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

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

Апробация работы Содержание отдельных разделов и диссертации в целом было доложено на:

1) научных семинарах и методических советах кафедры «Компьютерные системы и сети» МГТУ им. Н.Э. Баумана, 2005-2007;

2) III Российской НТК «Новые информационные технологии в системах связи и управления» ЦНТИ, Калуга, 2004;

3) Всероссийской НТК «Прогрессивные технологии, конструкции и системы в приборо- и машиностроении» Москва, МГТУ, 2005;

4) Всероссийской конференции студентов, аспирантов, молодых ученых. Центральный регион. Москва, 2-3 марта, 2006г. МГТУ им. Н.Э.

Баумана;

5) VII Международном симпозиуме «Интеллектуальные системы (INTELS 2006)». Краснодар, 2006.;

6) научном семинаре в рамках ассоциации «РусКрипто», 21 ноября, 2006.;

7) Международной конференции «РусКрипто-2007», 1-4 февраля, 2007.;

8) Международной конференции «РусКрипто-2008», 3-6 апреля, 2008.

Публикации Содержание диссертационной работы полностью отражено в 9-и работах, из них по списку ВАК – 1.

Структура и объем работы Диссертация состоит из введения, четырех глав, общих выводов, библиографического списка из 72 наименований. Работа содержит страницы машинописного текста содержательной части, 37 рисунков, таблицу, 6 страниц библиографии и 10 страниц приложений.

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

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

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

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

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

1. Свойство функциональности. Запутанный алгоритм должен выполнять ту же функцию, что и исходный.

2. Полиномиальное замедление. Запутанный алгоритм должен работать в полиномиальное число раз медленнее, чем исходный. Аналогичное можно сказать и про увеличение размера кода после запутывания.

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

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

Подробно рассмотрен пример реализации алгоритма блочного шифрования AES-128 на основе технологии белого ящика. Произведен анализ данной схемы и предложен метод извлечения скрытого ключа.

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

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

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

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

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

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

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

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

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

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

где - функциональное свойство подпрограммы;

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

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

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

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

следующее:

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

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

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

В этом случае несводимость неравенства (6) к системе (5) достаточно несложно обеспечить. Докажем следующее утверждение.

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

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

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

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

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

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

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

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

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

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

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

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

VREAL VFAKE

VREAL VFAKE

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

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]).

устанавливает верхнюю границу каждого компонента равной.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В подпрограмму может быть передан один или несколько указателей на «фальшивые» буферы памяти. Для алгоритма запутывания «фальшивые»

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

3. Генерация «мусорного» кода. На основе приведенных выше теоретических выкладок генерируется «фальшивый» код, работающий как с локальным, так и с глобальным контекстом. Обеспечивается полиморфизм кода за счет замены части исходных инструкций на набор других инструкций, выполняющих в своей совокупности те же действия (в том числе и с глобальным контекстом). В диссертационной работе приведен подробный пример алгоритма генерации «мусорного» кода. Алгоритм подразумевает добавление кода в соответствии с разработанными рекомендациями по построению запутывающих преобразований. Для генерации «мусорных» инструкций активно используется «фальшивый»

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

4 Разбавление инструкций перехода. Под разбавлением инструкций перехода подразумеваются различные схемы, позволяющие заменить одну инструкцию перехода несколькими.

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

Операция op означает любую операцию, удовлетворяющую тождеству (9).

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

6. Разбиение базовых блоков на функции производится как на этапе платформозависимой обфускации (обфускации на уровне машинного кода целевой платформы). Каждой инструкции в базовом блоке ставится в соответствие уровень вложенности. По мере приближения к «центру»

базового блока уровень вложенности увеличивается. Таким образом, получается, что первая и последняя инструкции базового блока имеют уровень вложенности равным 0. Максимальный уровень вложенности является задаваемым параметром.

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

При этом ни одна из добавленных подпрограмм не обладает функциональным свойством e.

Формула (10) дает формальное определение действий, выполняемых генератором полиморфного кода. instr – машинная инструкция, p – подпрограмма, обладающая тем же функциональным свойством, что и инструкция instr. Выбор подпрограммы осуществляется из конечного множества P мощностью k. Множество P является подмножеством всех подпрограмм с функциональным свойством. Основной задачей генератора полиморфного кода следует считать задачу сокрытия сигнатур. Если найдется алгоритм, который сможет установить взаимнооднозначное соответствие между инструкцией instr и подпрограммой p, то впоследствии можно осуществить деобфускацию при помощи алгоритмов сигнатурного поиска. Для того чтобы воспрепятствовать сигнатурному поиску, необходимо дополнить условие (10) следующим образом:

Исходные инструкции instri,instri +1,instri + m следуют друг за другом. На этапе генерации полиморфного кода они отображаются соответственно в подпрограммы pi, pi +1, pi +m. Далее эти подпрограммы объединяются в одну подпрограмму, но так, чтобы полученная подпрограмма p не представляла собой конкатенацию элементов pi, pi +1, pi +m - W ( pi, pi +1,..., pi + m ). Эта технология была названа технологией пересечения полиморфных инструкций. Она заключается в том, что часть инструкций подпрограммы pi переносится в тело подпрограммы pi +1 и наоборот.

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

В генераторе полиморфного кода используются системы полных функций И-НЕ и ИЛИ-НЕ. Также используются следующие тождества:

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

Разработанные алгоритмы и методы позволяют не только производить запутывание, но и эффективно внедрять код в тело приложения.

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

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

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

Подробно рассмотрены UML-диаграммы, описывающие статическую структуру разработанного программного обеспечения.

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

Коэффициенты C speed и Cvalue - коэффициенты, зависящие от платформы, на которой будет выполняться полученный код и от генератора машинного кода из промежуточного. IterNum в формуле (13) – это число вхождений в i-й базовый блок или число итераций в цикле. FPT - число «мусорных» инструкций на одну истинную, m – число констант, сгенерированных для сравнения. В результате проведения 200 замеров на различных подпрограммах было отмечено, что скорость работы запутанного кода уменьшается по сравнению с исходной не более чем на 2 порядка. В свою очередь размер запутанного кода увеличивается по сравнению с исходным не более чем на 2 порядка.

В результате оценки качества запутывающих преобразований, осуществляемых разработанными методиками, по методу, описанному в работе Гайсаряна, Чернова, Белеванцева и др., был сделан вывод, что качество запутывания при помощи данных методик превосходит качество обфускации, обеспечиваемое технологиями виртуализации на 30%.

Существующие методики оценки качества запутывающих преобразований не предполагают оценки потенциала исходных данных к запутыванию. Выделим ряд характеристик запутываемого кода – доля времени нахождения в запутываемом участке кода по отношению к времени работы всей программы (vc), доля инструкций перехода во внешнюю среду по отношению к общему количеству инструкций (tc) и процент редких инструкций по отношению к общему количеству инструкций (rc). Если vc некоторой функции превышает 20%, то данную функцию защищать не рекомендуется. Если tc превышает 30%, то данную функцию тоже не рекомендуется защищать так же, как если rc превышает 50%. Если функция удовлетворяет вышеописанным требованием, то качество запутывающих преобразований соответствует высокому уровню по Коллбергу.

В заключении изложены основные теоретические и практические результаты диссертационной работы.

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

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

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

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

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

6. Разработанные в диссертационной работе методики позволили повысить качество обфускации по сравнению с качеством, обеспечиваемым технологией виртуализации кода, на 30%. Оценка качества производилась по методике, описанной в работе Гайсаряна, Чернова, Белеванцева и др.

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

7. Созданные методики могут после небольшой модификации быть использованы для целей стеганографии, встраивания водяных знаков в программу и обфускации кода, имеющего объектно-ориентированную архитектуру.

Публикации по теме работы 1. Щелкунов Д.А. Методика защиты от несанкционированного доступа и контроля действий оператора в системах оповещения на базе ОС Windows NT\2000\XP/ //III Российская НТК «Новые информационные технологии в системах связи и управления». – Калуга: ЦНТИ, 2004. – C. 171 – 173.

2. Мазин А.А., Щелкунов Д.А. Анализ и применение запутывающих преобразований при защите исполняемых файлов от несанкционированного конструкции и системы в приборо- и машиностроении» Материалы. – М:

МГТУ, 2005. – Т. 1. – С. 330 – 333.

3. Щелкунов Д.А. Методы автоматической защиты Windowsприложений от исследования и несанкционированной модификации // Технологии Microsoft в теории и практике программирования. Труды Всероссийской конференции студентов, аспирантов и молодых ученых. – М.:

МГТУ им. Н.Э. Баумана, 2006 – С. 96-97.

4. Щелкунов Д.А. Автоматическая защита программ от исследования и отладки // Интеллектуальные системы (INTELS 2006): Сб. Трудов VII Международ. симпоз. – Краснодар, 2006. – С. 401 – 405.

5. Семинар в рамках Ассоциации РусКрипто на тему «Защита информации: аспекты теории и вопросы практических приложений»

http://www.ruscrypto.ru/netcat_files/File/seminar.015.zip 6. Щелкунов Д.А. Обфускация. Теоретические и практические аспекты., //Труды международной конференции РусКрипто, 1-4 февраля 2007 г. – http://www.ruscrypto.ru/sources/conference/rc2007/ 7. Щелкунов Д.А. Запутывание программ и внедрение в приложение стороннего кода // Технологии Microsoft в теории и практике программирования. Труды IV Всероссийской конференции студентов, аспирантов и молодых ученых. Центральный регион. – М.: Вузовская книга, 2007. – C.191 – 192.

8. Щелкунов Д.А. Применение запутывающих преобразований и полиморфных технологий для автоматической защиты исполняемых файлов от исследования и модификации. //Труды международной конференции РусКрипто, 3-6 апреля 2008 г.

http://www.ruscrypto.ru/sources/conference/rc2008/ 9. Щелкунов Д.А. Методика запутывания кода для автоматической защиты приложений от нелегального распространения //Безопасность информационных технологий. – М.: МИФИ, 2008. - №3. – С. 48 – 51.