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

Московский государственный университет им. М. В. Ломоносова Факультет вычислительной математики и кибернетики

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

Чернов Александр Владимирович

ИССЛЕДОВАНИЕ И РАЗРАБОТКА МЕТОДОЛОГИИ МАСКИРОВКИ ПРОГРАММ

Специальность 05.13.11 — "Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей"

АВТОРЕФЕРАТ

диссертации на соискание учёной степени кандидата физико-математических наук

Москва — 2003

Работа выполнена на кафедре системного программирования факультета вычислительной математики и кибернетики Московского государственного университета им. М. В. Ломоносова.

Научный руководитель: кандидат физико-математических наук, доцент

Гайсарян Сергей Суренович Официальные оппоненты: доктор физико-математических наук, профессор

Подловченко Римма Ивановна

кандидат физико-математических наук Шокуров Александр Владимирович

Ведущая организация: Институт прикладной математики

им. М. В. Келдыша РАН

Защита диссертации состоится «_»

2003 г. в_час._мин. на засе-

дании Диссертационного совета Д.501.001.44 в Московском государственном университете им. М. В. Ломоносова по адресу: 119992, ГСП-2, г. Москва, Ленинские горы, МГУ им М. В. Ломоносова, 2-й учебный корпус, факультет вычислительной математики и кибернетики, аудитория №_.

С диссертацией можно ознакомиться в библиотеке факультета вычислительной математики и кибернетики МГУ

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

Учёный секретарь диссертационного совета, кандидат физико-математических наук,

профессор

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

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

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

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

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

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

Исследование методов маскировки программ, которые применяются к программе на язы-

1 Говоря неформально, маскирующее преобразование (obfuscating transformation) текста программы можно описать как преобразование, которое делает задачу понимания и модификации текста программы как можно более сложной.

РОС. НАЦИОНАЛЬНАЯ БИБЛИОТЕКА С. Петербург г-/а. » 09 ?00J«k*7//C'

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

Актуальность темы. В настоящее время разработаны и распространяются десятки маскирующих компиляторов для языка Java и несколько — для языков Си и Си++. Они, как правило, выполняют лишь простейшие маскирующие преобразования текста программы и (или) графа потока управления программы и её структур данных. Методы, используемые в них, как правило, подобраны эмпирически и слабо обоснованы теоретически. С другой стороны, разработаны и успешно применяются в оптимизирующих компиляторах и средствах обратной инженерии весьма мощные методы анализа программ. Назрела необходимость теоретического и практического анализа действия маскирующих преобразований и оценки устойчивости замаскированных программ против существующих методов анализа программ. Необходимо также разработать методики маскировки программ, устойчивые к современным методам статического и динамического анализа и методам обратной инженерии.

Основные результаты работы. В диссертации получены следующие основные результаты:

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

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

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

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

На защиту выносятся.

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

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

3. Инструментальная интегрированная среда Poirot для изучения алгоритмов преобразования программ. Специализированные инструментальные средства (анализаторы и преобразователи программ) для анализа замаскированных программ.

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

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

Интегрированная среда используется в учебном процессе на факультетах ВМиК МГУ и ФПМЭ МФТИ для обучения алгоритмам анализа и оптимизации программ.

Апробация работы. Основные результаты работы опубликованы в статьях [1, 2, 3]. Результаты работы обсуждались на следующих конференциях и семинарах:

• Научно-исследовательском семинаре по автоматизации программирования под руководством проф. М. Р. Шуры-Буры.

• Конференции, посвященной 90-летию со дня рождения А. А. Ляпунова, Россия, Новосибирск, 8—11 октября 2001 года.

• Школе-семинаре молодых учёных факультета ВМиК МГУ, Дубна, октябрь 2001.

• Тихоновских чтениях факультета ВМиК МГУ, 30 октября 2002 года.

Объём и структура диссертации. Работа состоит из введения, четырёх глав, заключения и списка литературы. Общий объём диссертации — 132 страницы, в том числе 47 иллюстраций и 24 таблицы. Список литературы содержит 75 наименований.

Краткое содержание работы

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

Глава 1 носит вводный характер и посвящена анализу различных подходов к задаче маскировки программ, практических приёмов маскировки и существующих инструментов маскировки.

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

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

В разделе 1.2 вводятся термины, которые используются далее в тексте диссертации.

В разделе 1.3 вводятся метрики сложности кода программы, используемые в тексте диссертации для оценки эффекта действия маскирующих преобразований на программы. В работе используются следующие метрики: размер функции (LC), цикломатическая сложность (СС), метрика сложности связей (FC), метрика сложности графа функций (GC), метрика структурной сложности функции (SC), метрика сложности циклической структуры (YC) и метрика сложности потока данных (DC). Раздел 1.4 вводит метрики сложности непосредственно маскирующих преобразований. В частности, метрика сложности маскирующего преобразования (ОС) показывает глубину анализа маскируемой программы, необходимого для выполнения этого маскирующего преобразования.

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

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

В рамках диссертационной работы автором предложено новое определение маскирующего преобразования, основанное на понятии «расстояния между программами», определяемого на основе введённых ранее метрик сложности кода. Замаскированная программа т(р) такова, что для любого полиномиального вероятностного алгоритма с/ вероятность найти программу р' = с1(т(р)) такую, что р(М(р),М(р')) < Д мала:

Рг[р(М(р),М(р'))<Д]<а(|р|).

Здесь М[р) — вектор метрик программы р, а р(М(р),М(р')) — расстояние между программами. а(я) — это бесконечно малая функция, убывающая быстрее обратной к любой полиномиальной функции. Параметры 8, р, М выбираются исходя из требований устойчивости маскировки. Далее показано, что множество маскирующих преобразований непусто.

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

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

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

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

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

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

В разделе 1.7 кратко рассмотрены существующие реализации маскировщиков программ для языков Java и Си.

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

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

держкой», «только ручной анализ». Далее для каждого метода маскировки, описанного в главе 1, даётся оценка степени устойчивости метода маскировки.

Одним из мощных преобразований потока управления функции является построение «диспетчера». Граф потока управления изменяется так, что после выполнения очередного базового блока управление всегда передаётся на блок диспетчера, который вычисляет номер следующего базового блока по состоянию переменных функции и по номеру текущего базового блока. В результате граф потока управления функции произвольной сложности преобразовывается в граф характерного «плоского» вида. В литературе описано несколько алгоритмов построения диспетчера таким образом, чтобы статический анализ и устранение диспетчера были бы вычислительно сложной задачей. В разделе 2.1 рассматривается метод анализа функций, замаскированных построением диспетчера. Метод основан на сборе трасс выполнения замаскированной функции. Обнаружение функций, замаскированных построением диспетчера, возможно из-за характерного вида их графа потока управления. Базовый блок диспетчера в графе потока управления также легко может быть обнаружен. По трассам замаскированной программы можно получить трассы исходной (незамаскированной) программы, удалив из трасс базовый блок диспетчера. Далее по совокупности трасс возможно построить граф потока управления функции, который близок к графу управления функции до маскировки. Далее восстанавливаются условия ветвления. Таким образом показано, что метод построения диспетчера не обеспечивает устойчивой маскировки, если применяются методы полустатического анализа.

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

Раздел 2.3 посвящён демонстрации применения методик распутывания к двум показательным примерам. В качестве первого примера выбрана программа-победитель междуна-

родного конкурса замаскированных вручную программ на Си (International Obfuscated С Code Contest). Программа выполняет преобразование знаков в коде ASCII в код Морзе и наоборот. Демаскировка для замаскированных вручную программ заключается в выявлении семантических свойств программы, в том числе свойств потока управления и данных, а также в преобразовании программы к виду, более удобному для понимания человеком. В этом случае размер демаскированной программы может увеличиться. Применение мощных методов анализа алиасов и мощных методов анализа потока данных (анализ доменов, анализ нулевых значений, устранение частичной избыточности) позволило выявить в программе скрытые зависимости и преобразовать их в явный вид, что упростило логику программы.

Вторая программа была замаскирована предварительной версией одного из коммерческих маскировщиков программ на Си. Она находила и печатала все решения задачи о 8 ферзях. В программе была замаскирована только главная функция программы, которая называлась queens. Размер текста замаскированной программы составлял 103 килобайта. Простейшие преобразования синтаксического уровня, такие как удаление избыточных скобок и избыточных ключевых слов позволили сократить программу на 20%. Статическое устранение мёртвого кода, минимизация переменных и переименование идентификаторов позволили уменьшить размер программы до 26 килобайт. Далее по виду графа потока управления функции queens было установлено, что к главному циклу функции было применено преобразование клонирования цикла, затем каждый из двух циклов был полностью развёрнут. После сворачивания циклов и устранения дублирования размер программы составил 3.5 килобайта. Данный пример демонстрирует, что даже огромное увеличение размера программы при маскировке (в данном случае в 200 раз) может не препятствовать эффективной демаскировке с применением стандартных средств статического анализа программ. '

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

В разделе 3.1 даётся описание общих принципов, положенных в основу предложенного метода маскировки:

• Увеличение сложности потока управления маскируемой функции, но таким образом, чтобы в замаскированной программе отсутствовали мёртвые (то есть никогда не про-

ходимые) дуги.

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

Предлагаемый метод маскировки состоит из следующих этапов:

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

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

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

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

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

Преобразование клонирования базовых блоков заключается в замене дуги, соединяющей два базовых блока (например, 5 [г] и В [./]) на оператор разветвления с выполнением базового блока Я [Л на каждой из ветвей. Для этого базовый блок ВЦ] должен быть скопирован необходимое число раз.

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

(а) Исходный граф. (Ь) Преобразованный граф

Рис. 1 : Схема преобразования зацепления дуг

В исходной программе после выполнения базового блока В [from \} всегда выполнялся базовый блок В [toi], а после базового блока B[from2] всегда выполнялся базовый блок й [ ¿02 ] ■ В результате выполнения преобразования создаётся новый базовый блок В [new], который выполняется и после В [from\ ], и после В [from2]. Новый базовый блок завершается вычислением предиката Р, в зависимости от которого управление передаётся либо на базовый блок В [to] ], либо на базовый блок В [Юг]. Предикат Р должен гарантировать, что управление вернётся на ту ветвь, с которой оно пришло в блок В [new]. Такие предикаты мы назовём возвращающими.

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

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

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

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

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

init: int, env —»counter get: counter, env —► int next: counter, env —> counter Здесь env — это среда выполнения программы, поставляющая источник недетерминизма в счётчик. Обсуждается поддержка счётчиков в реализации предложенного метода маскировки в рамках интегрированной среды Poirot. Реализация нового вида счётчиков должна состоять как минимум из двух классов, реализующих интерфейсы CouterFactory и CounterGenerator. Далее описываются виды счётчиков, реализованных в рамках интегрированной среды: счётчик по модулю, линейный конгруэнтный счётчик, счётчик на хэш-функциях, счётчик на динамических структурах данных.

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

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

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

можно использовать булевские тождества, которые строятся с помощью эквивалентных преобразований из тождества (у; V V]") Л ■ ■ • Л (уд. V где переменные V), ..., V* являются как существенными, так и несущественными. Рассматриваются некоторые комбинаторные и теоретико-числовые тождества, применяемые в реализации метода маскировки в рамках интегрированной среды. Далее рассматривается один способ внесения фиктивных зависимостей по данным, использующий динамические структуры данных.

В разделе 3.3 устанавливается устойчивость предложенного метода маскировки по отношению к статическим и полустатическим методам анализа.

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

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

М(*с/0-р)(Л(5/)-ма)< о(и).

Здесь — случайный представитель семейства непрозрачных предикатов, ж — оракул, а(т) — функция от количества переменных в предикате, убывающая быстрее, чем обратная функция к любому полиному. Затем доказывается утверждение, что если непрозрачные предикаты существуют, то Р ^ ЫР. Далее показывается, как по булевскому непрозрачному предикату можно построить предикат па указателях и предикат на элементах массива.

Задача ЗАВ вводится следующим образом. Пусть У = — множество пере-

менных замаскированной программы. Предположим, что базовый блок представляет собой вычисление булевской функции / : £т —► Пусть Ут С V, ]Ц„\ = т — переменные, значения которых используются при вычислении /, а Уош С V, \У0Ш\ — п — переменные, которые получают новые значения в результате вычисления. Если для некоторой переменной V € У,„ и V 6 Уош, при вычислении используется старое значение переменной. Пусть С Ут! — множество «существенных» переменных на выходе из базового блока (например, это могут быть переменные, значения которых печатаются, либо переменные, интересные по другой

причине). Определим задачу анализа зависимостей по данным (ЗАВ) как задачу нахождения минимального множества переменных Wm С Vm такого, что переменные из множества Vin — W,„ несущественны относительно Wout.

Данной оптимизационной задаче соответствует задача проверки свойств ЗАВ: дано множество булевских переменных V = {vi,...,v^}, булевская функция над переменными из V,„, подмножество Woul С Voul, число р (О < р < к). Существует ли множество W,n С Vm, |W,„\ < р такое, что переменные Vln - Wm несущественны относительно Wou!.

На основе данного определения доказываются две теоремы.

Теорема 1 Задача ЗАВ NP-полна.

Теорема 2 Если Р / NP, то для любого р > 1 не существует полиномиального р-приближённого алгоритма решения оптимизационной задачи ЗАВ.

Определение 1 (обратный слайс базового блока)

Пусть Wout С Vout — множество интересующих нас переменных на выходе из базового блока В. Обратным слайсом базового блока относительно множества переменных Wout называется базовый блок В', из которого удалены вычисления переменных, несущественных относительно множества Wolll.

Из доказанного выше немедленно следует, что задача построения обратного слайса в программе, состоящей из одного базового блока, NP-полна, и, более того, для любого р > 1 не существует р-приближённого полиномиального алгоритма построения обратного слайса.

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

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

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

. Глава 4 посвящена описанию интегрированной программной среды для изучения мето- >

дов анализа и трансформации программ Poirot, разработанной при работе над настоящей диссертацией.

Интегрированная среда Poirot построена как набор связанных друг с другом инструмен- :

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

В настоящее время в качестве исходного и целевого языка программирования используется язык Си, но внутреннее представление разработано таким образом, чтобы поддерживать широкий класс процедурных и объектно-ориентированных языков программирования. Все компоненты ИС реализованы на языке Java, за исключением транслятора из Си в MIF, который реализован на языке Си и поддерживает полный стандарт ISO С 90.

В рамках интегрированной среды реализованы многие методы анализа и трансформации программ: преобразование в представление SSA и обратно, выявление мёртвого кода, выяв- ^

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

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

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

I

ков, построение диспетчера, зацепление дуг, инкапсуляция переменных в массив, генерация j

тождеств, профилирование значений, профилирование дуг и т. д. Кроме того, интегрирован- j

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

Основные результаты работы

В диссертации получены следующие основные результаты:

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

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

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

Работы автора по теме диссертации

[1] А. В. Чернов. Интегрированная среда для исследования «обфускации» npoipaMM. Доклад на конференции, посвященной 90-летию со дня рождения А. А. Ляпунова. Россия, Новосибирск, 8—11 октября 2001 года.

http://www-sbras.nsc.ru/ws/show_abstract.dhtml?ru+l9+2350

[2] А. В. Чернов. Анализ запутывающих преобразований программ//В сб. «Труды Института системного программирования РАН», под ред. В. П. Иванникова. М.: ИСП РАН, 2002.

[3] А. В. Чернов. Об одном методе маскировки программ//В сб. «Труды Института системного программирования РАН», под ред. В. П. Иванникова. М.: ИСП РАН, 2003.

Издательство ООО "МАКС Пресс". Лицензия ИД № 00510 от 01.12.99 г. Подписано к печати 29.04.2003 г. Формат 60x90 1/16. Усл.печ.л. 1,0. Тираж 100 экз. Заказ 436. Тел. 939-3890, 939-3891, 928-1042. Тел./факс 939-3891. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В.Ломоносова.

12/77 2777

Введение

1 Маскирующие преобразования программ

1.1 Задача маскировки программ.

1.2 Используемая терминология.

1.3 Метрики сложности программ.

1.4 Расстояние между программами.

1.5 Определение устойчивости маскирующего преобразования

1.6 Методы анализа и трансформации программ.

1.7 Маскирующие преобразования программ.

1.7.1 Текстуальные маскирующие преобразования

1.7.2 Преобразования управляющей структуры.

1.7.3 Преобразования реструктуризации всей программы

1.7.4 Преобразования маскировки одной процедуры.

1.7.5 Непрозрачные предикаты.

1.7.6 Трансформация графа потока управления («диспетчер»).

1.7.7 Сравнение свойств разных маскирующих преобразований.

1.8 Использование маскирующих преобразований программ.

2 Анализ маскирующих преобразований программ

2.1 Анализ маскирующих преобразований.

2.1.1 Анализ лексических преобразований.

2.1.2 Анализ маскирующих преобразований графа потока управления

2.2 Классификация маскирующих преобразований программ.

2.3 Применение методов демаскировки.

2.3.1 Анализ замаскированных вручную программ.

2.3.2 Анализ программ, замаскированных автоматически.

2.4 Выводы.

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

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

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

3.1.2 Разрушение структурности графа потока управления.

3.1.3 Генерация несущественного кода.

3.1.4 Перемешивание программ.

3.2 Реализация метода маскировки.

3.2.1 Увеличение графа потока управления процедуры.

3.2.2 Преобразования разрушения структурности.

3.2.3 Генерация несущественного кода.

3.2.4 «Зацепление» холостой и основной программы.

3.3 Устойчивость метода.

3.3.1 Формальная устойчивость метода.

3.3.2 Неформальная устойчивость метода.

3.4 Пример применения метода

3.5 Выводы.

4 Интегрированная среда Poirot

4.1 Архитектура системы.

4.2 Промежуточное представление.

4.3 Интерфейс пользователя.

4.3.1 Меню Analyze.

4.3.2 Меню Optimize.

4.3.3 Меню Transform.

4.3.4 Меню Obfuscate

4.3.5 Меню Generate.

4.3.6 Меню Execute.

4.3.7 Меню Visualize.

4.3.8 Меню Traces.

4.3.9 Меню Options.

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

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

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

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

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

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

1. Исходная и замаскированная программа записаны на языке Си [8].

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

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

4. Метод маскировки устойчив относительно современных методов статического и полустатического анализа программ, развитых для языка Си.

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

Актуальность темы. Необходимость разработки средств защиты программ от обратной инженерии подтверждается следующими наблюдениями. Во-первых, для обеспечения переносимости программ на разные платформы в ряде случаев они распространяются в исходных кодах на языке высокого уровня. Например, система статического анализа программ на Си и Си++[15] FlexeLint [42] распространяется в замаскированных исходных файлах. Во-вторых, широко распространены языки программирования, такие как Java [2], в которых «исполняемой» формой программы является не машинный код для некоторого типа процессоров, а машинно-нейтральное представление. Задача декомпиляции программы из такого представления обратно в программу на языке Java значительно проще, чем декомпиляция из машинного кода, и успешно решена [71].

Основные результаты работы. В диссертации получены следующие основные результаты:

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

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

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

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

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

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

Практическая ценность работы. Система Poirot позволяет демаскировать замаскированные программы и маскировать программы устойчивым образом. Она помещена в открытый доступ в Internet и может использоваться для анализа существующих методов маскировки программ и разработки новых методов маскировки программ, непосредственно для маскировки программ и анализа замаскированных программ, а также для решения некоторых проблем обратной инженерии. С помощью интегрированной среды Poirot исследованы методы маскировки программ, используемые одним из коммерческих маскировщиков, и выявлены слабые стороны этого метода. Интегрированная среда используется в учебном процессе на факультетах ВМиК МГУ и ФПМЭ МФТИ.

С помощью интегрированной среды Poirot разработан новый метод автоматического разбиения последовательной программы на нити, который учитывает локальность доступов к данным [29].

Апробация работы. Основные результаты работы опубликованы в работах [16, 17, 18, 19, 28]. Результаты работы обсуждались на следующих конференциях и семинарах:

• Научно-исследовательском семинаре по автоматизации программирования под руководством проф. М. Р. Шуры-Буры.

• Конференции, посвященной 90-летию со дня рождения А. А. Ляпунова, Россия, Новосибирск, 8—11 октября 2001 года.

• Школе-семинаре молодых учёных факультета ВМиК МГУ, Дубна, октябрь 2001.

• Тихоновских чтениях факультета ВМиК МГУ, 30 октября 2002 года.

• Семинаре "International Workshop on Program Understanding" в рамках Пятой международная конференции «Перспективы систем информатики», 9—12 июля 2003 г., Россия, Новосибирск.

Объём и структура диссертации. Работа состоит из введения, четырёх глав, заключения и списка литературы. Общий объём диссертации — 133 страницы, в том числе 49 иллюстраций и 9 таблиц. Список литературы содержит 81 наименование.

Результаты работы могут использоваться для маскировки и демаскировки программ на языке Си.

Заключение

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

В диссертации получены следующие основные результаты:

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

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

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

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

Дальнейшие исследования по результатам диссертации будут вестись в следующих направлениях:

1. разработка новых методов демаскировки замаскированных программ;

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

3. дальнейшее развитие интегрированной среды Poirot.

1. В. Н. Агафонов. Спецификация программ: понятийные средства и их организация. М.: «Наука», 1987.

2. К. Арнольд, Д. Гослинг, Д. Холмс. Язык программирования Java. Пер. с англ. М.: Вильяме, 2001.

3. А. Ахо, Р. Сети, Д. Улльман. Компиляторы. Принципы, технологии, инструменты. Пер. с англ. М.: Вильяме, 2001.

4. А. Ахо, Дж. Хопкрофт, Дж. Ульман. Построение и анализ вычислительных алгоритмов. Пер. с англ. М.: Мир, 1979.

5. Введение в криптографию. Под общей редакцией В. В. Ященко. М.: МЦМНО, 1999.

6. М. Гери, Д. Джонсон. Вычислительные машины и труднорешаемые задачи. Пер. с англ. М.: Мир, 1982.

7. Р. Грэхем, Д. Кнут, О. Паташник. Конкретная математика. Основания информатики. Пер. с англ. М.: Мир, 1998.

8. Б. В. Керниган, Д. М. Ритчи. Язык программирования Си. Пер. с англ. СПб.: Невский диалект, 2001.

9. Д. Э. Кнут. Искусство программирования. Том 2. Получисленные алгоритмы. Пер. с англ. М.: Вильяме, 1998.

10. Т. Кормен, Ч. Лейзерсон, Р. Ривест. Алгоритмы: построение и анализ. Пер. с англ. М.: МЦНМО, 2000.

11. В. В. Липаев. Качество программного обеспечения. М.: Финансы и статистика, 1983.

12. В. В. Липаев. Тестирование программ. М.: Радио и связь, 1986.

13. Д. Пик, Т. О'Райли, М. Лукидис. Unix. Инструментальные средства. Пер. с англ. М.: BHV, 2002.

14. Р. И. Подловченко. Эквивалентные преобразования схем программ для "запутывания" самих программ//Программирование. — 2002 — №2 — С. 66-80.

15. Б. Страуструп. Язык программирования С++. Пер. с англ. М.: Бином, 1999.

16. А. В. Чернов. Интегрированная среда для исследования «обфускации» программ. Доклад на конференции, посвященной 90-летию со дня рождения А. А. Ляпунова. Россия, Новосибирск, 8—11 октября 2001 года.http://www-sbras.nsc.ru/ws/showabstract.dhtml?ru+19+2350

17. А. В. Чернов. Анализ запутывающих преобразований программ//В сб. «Труды Института системного программирования РАН», под ред. В. П. Иванникова. М.: ИСП РАН, 2002.

18. А. В. Чернов. Об одном методе маскировки программ//В сб. «Труды Института системного программирования РАН», под ред. В. П. Иванникова. М.: ИСП РАН, 2003.

19. А. В. Чернов. Интегрированная инструментальная среда Poirot для изучения методов маскировки программ. Препринт Института системного программирования РАН. М.: ИСП РАН, 2003.

20. С. В. Яблонский. Введение в дискретную математику. М.: Наука, 1986.

21. A. W. Appel. Modern Compiler Implementation in С. Cambridge University Press. 1998.

22. M. Arnold, S. Fink, D. Grove, M. Hind, P. F. Sweeney. Adaptive Optimizations in the Jalapeno JVM. In Proceedings of ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA'OO), 2000.

23. T. Ball, J. R. Larus. Optimally Profiling and Tracing Programs. In Proceedings of the Nineteenth Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL'92), 1992.

24. T. Ball, J. R. Larus. Efficient Path Profiling. In Proceedings of the 29th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO-29), 1996.

25. B. Barak, O. Goldreich, R. Impagliazzo, S. Rudich, A. Sahai, S. Vadhan, K. Yang. On the (Im)possibility of Obfuscating Programs. LNCS 2139, pp. 1-18, 2001.

26. B. Calder, P. Feller, A. Eustace. Value Profiling. In Proceedings of the 30th International Symposium on Microarchitecture (MICROSO), 1997.

27. P. P. Chang, S. A. Mahlke, W. W. Hwu. Using Profile Information to Assist Classic Code Optimizations. In Software Practice and Experience, 21(12): 1301-1321, December 1991.

28. A. Chernov. A New Program Obfuscation Method. In Proceedings of the Adrei Ershov Fifth International Conference "Perspectives of Systems Informatics". International Workshop on Program Understanding, Novosibirsk, July 14-16, 2003.

29. S. Chow, Y. Gu, H. Johnson, V. Zakharov. An approach to the obfuscation of control-flow of sequential computer programs. LNCS 2200, pp. 144-155, 2001.

30. С. Cifuentes, К. J. Gough. Decompilation of Binary Programs. Technical report FIT-TR-1994-03. Queensland University of Technology, 1994.http://www.fit.qut.edu.au/TR/techreports/FIT-TR-94-03.ps

31. Cloakware Corp. Web Page, http://www.cloakware.com

32. C. Collberg, C. Thomborson, D. Low. A Taxonomy of Obfuscating Transformations. Departament of Computer Science, The University of Aukland, 1997.http://www.cs.arizona.edu/~collberg/Research/Publications/ ** CollbergThomborsonLow97a

33. C. Collberg, C. Thomborson, D. Low. Breaking Abstractions and Unstructuring Data Structures. In Proceedings of the IEEE International Conference on Computer Languages (ICCL'98), Chicago, IL, May 1998.

34. C. Collberg, C. Thomborson, D. Low. Manufacturing Cheap, Resilient, and Stealthy Opaque Constructs. In Proceedings of the International Conference on Principles of Programming Languages (POPL'98), San Diego, CA, Januaiy 1998.

35. C. Collberg, C. Thomborson. On the Limits of Software Watermarking. Technical Report #164. Departament of Computer Science, The University of Aukland, 1998.http://www.cs.arizona.edu/~соliberg/Research/Publications/«• CollbergThomborson98e

36. R. Cytron, J. Ferrante, В. K. Rosen, M. N. Wegman, F. K. Zadeck. Efficiently computing static single assignment form and the control dependence graph. ACM Transactions on Programming Languages and Systems, 13(4): 450-90, October 1991.

37. R. Cytron, R. Gershbein. Efficient Accommodation of May-Alias Information in SSA Form, in Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'93), pp. 36-45, June 1993.

38. DashO-Pro. Java Code Optimizer, Obfuscator, Compressor.http://www.codework.com/dashO/product.html41. The dcc decompiler.http://www.itее.uq.edu.au/~cristina/dcc.html

39. Gimpel Software Home Page for PC-lint and FlexeLint for C/C++.http://www.gimpel.com/

40. Google Web Directory. Decompilers and Disassemblers.http://directory.google.com/Top/Computers/Programming/Languages/«• Java/DevelopmentTools/Translators/DecompilersandDisassemblers/

41. Google Web Directory. Obfuscators.http://directory.google. com/Top/Computers/Programming/Languages/** Java/DevelopmentTooIs/Obfuscators/

42. R. Gupta, D. Berson, J. Z. Fang. Path Profile Guided Partial Redundancy Elimination Using Speculation. In Proceedings of the IEEE International Conference on Computer Languages (ICCL'98), pp. 230-239, 1998.

43. Y. Gurevich. Evolving Algebras. In Proceedings of the IFIP 13th World Computer Congress, volume I: Technology/Foundations, pp. 423-427, 1994.

44. G. Hachez, C. Vasserot. State of the Art in Software Protection. Project FILIGRANE (Flexible IPR for Software Agent Reliance) deliverabIe/V2.http://www. dice.ucl.ac.be/crypto/filigrane/External/d21.pdf

45. W. H. Harrison. Compiler Analysis of the Value Ranges for Variables. In IEEE Transactions on Software Engineering, 3(3): 243-250, May 1977.

46. W. A. Harrison, К. I. Magel. A complexity measure based on nesting level. In SIGPLAN notices, 16(3):63—74, 1981.

47. M. H. Halstead. Elements of Software Science. Elsevier North-Holland, 1977.

48. S. Henry, D. Kafura. Software structure metrics based on information flow. IEEE Transactions on Software Engineering, 7(5): 510-518, September 1981.

49. M. Hind, A. Pioli. Which pointer analysis should I use? In Proceedings of the ACM SIGSOFT International Symposium on Software Testing and Analysis, pp. 113-123, August 2000

50. S. Horwitz. Precise Flow-Insensitive May-Alias Analysis Is NP-Hard. In ACM Transactions on Programming Languages and Systems, 19(1): 1-6, January 1997.

51. Introduction to HOL. A theorem proving environment for higher order logic. Edited by M. J. C. Gordon and T. F. Melham. Cambridge University Press, 1993.

52. The International Obfuscated С Code Contest, http://www.ioccc.org

53. H. Lai. A comparative survey of Java obfuscators available on the internet.http://www.cs . auckland.ac.nz/~cthombor/Students/hlai

54. M. H. Lipasti, С. B. Wilkerson, J. P. Shen. Value Locality and Load Value Prediction. In Proceedings of the Seventh International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS-VII), 1996.

55. D. Low. Java Control Flow Obfuscation. MSc Thesis. University of Aukland, 1998. http://www.cs.arizona.edu/~collberg/Research/Student s/** DouglasLow/thesis.ps

56. J. MacDonald. On Program Security and Obfuscation. 1998. http://www.xcf.berkeley.edu/~jmacd/cs261.pdf

57. M. Mambo, T. Murayama, E. Okamoto. A Tentative Approach to Constructing Tamper-Resistant Software. In Proceedings of the ACM New Security Paradigms Workshop, Langdale, Cumbria UK, 1998.

58. A. von Mayrhauser, A. M. Vans. Program Understanding: Models and Experiments. In M. Yovits, M. Zelkowitz (eds.), Advances in Computers, Vol 40, 1995. San Diego: Academic Press, pp. 1-38.

59. S. Muchnick. Advanced Compiler Design and Implementation. Morgan Kaufmann Publishers, 1997.

60. H. A. Muller Understanding Software Systems Using Reverse Engineering Technologies Research and Practice. In Proceedings of the 18th International Conference on Software Engineering (1CSE-18), 1996.

61. R. Muth, S. Watterson, S. Debray. Code Specialization based on Value Profiles. In Proceedings of the 7th International Static Analysis Symposium (SAS'2000), 2000. LNCS 1824, pp. 340-359.

62. J. Q. Ning, A. Engberts, W. Kozaczynski. Automated Support for Legacy Code Understanding. In Communications of the ACM, 37(5): 50-57, May 1994.

63. E. I. Oviedo. Control flow, data flow, and program complexity. In Proceedings of IEEE COMPSAC, 1980, pp. 146-152.

64. The Poirot IRE download page, http://www.ispras.ru/groups/ctt/ire.html

65. G. Ramalingam. The Undecidability of Aliasing. In ACM Transactions on Programming Languages and Systems, 16(5): 1467-1471, 1994.

66. SourceAgain Java decompiler.http://www.ahpah.com

67. B. Schneier. Applied Cryptography: protocols, algorithms and source code in C. Second Edition. John Wiley & Sons, Inc., 1996.

68. M. Spivey. Fast, accurate call graph profiling. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'02), 2002.

69. B. Steensgaard. Points-to analysis by type inference of programs with structures and unions. In Proceedings of the 6th International Conference on Compiler Construction. LNCS 1060, pp. 136-150, 1996.

70. F. Tip. A survey of program slicing techniques. Journal of Programming Languages, 3(3): 121—189, September 1995.

71. N. P. Varnovsky, V. A. Zakharov. On the Possibility of Provably Secure Obfuscating Programs. In Perspectives of System Informatics (Proceedings of Andrei Ershov Fifth International Conference), Novosibirsk, July 2003.

72. E. Walle. Methodology and Applications of Program Code Obfuscation. Faculty of Computer and Electrical Engineering, University of Waterloo, 2001.http://walle. dyndns.org/morass/misc/wtr3b.doc

73. C. Wang. A Security Architecture for Survivability Mechanisms. PhD Thesis. Departament of Computer Science, University of Virginia, 2000.http://www.cs.Virginia.edu/~survive/pub/wangthesis.pdf

74. C. Wang, J. Davidson, J. Hill, J. Knight. Protection of Software-based Survivability Mechanisms. Departament of Computer Science, University of Virginia, 2001.http://www.es.virginia.edu/~jck/publications/*' dsndistribute.pdf

75. G. Wroblewski. General Method of Program Code Obfuscation. PhD Thesis. Wroclaw, 2002.

76. Zelix KlassMaster Java Code Obfuscator and Obfuscation. http://www.zelix.com