Федеральное государственное автономное образовательное учреждение высшего профессионального образования

Национальный исследовательский университет «Высшая школа экономики»

Московский институт электроники и математики Национального исследовательского университета «Высшая школа экономики»

Допущен к защите

Заведующий кафедрой ВСиС

___________ А.В. Вишнеков

«__» ____________ 2013 г.

Ишханов Илья Григорьевич

ИССЛЕДОВАНИЕ МЕТОДОВ ДЕКОМПИЛЯЦИИ ПРОГРАММ ДЛЯ ПРОЦЕССОРОВ X86

Направление 23.01.00.68 - Информатика и вычислительная техника

Магистерская программа - Сети ЭВМ и телекоммуникации

Магистерская диссертация

Выполнил	подпись	магистрант группы СМ-31 И.Г. Ишхановы
Научный руководитель	подпись	доцент, к.т.н. В.Э. Карпов
Рецензент	подпись	доцент, к.т.н. А.А. Рогов

СОДЕРЖАНИЕ

ВВЕДЕНИЕ 1

СОДЕРЖАНИЕ 2

1 ОБЗОР СУЩЕСТВУЮЩИХ РАБОТ 8

1.1 Предыдущие работы 8

1.1.1 История декомпиляции (1960-1979) 9

1.1.2 История декомпиляции (1980-1999) 19

1.1.3 История декомпиляции (2000-н/в) 23

1.1.4 Обзор существующих декомпиляторов на язык Си 28

1.2 Проблемы декомпиляции 30

1.2.1 Отделение кода от данных 34

1.2.2 Отделение указателей от констант 35

1.2.3 Восстановление указателей, сложенных со смещением 35

1.2.4 Виды декомпиляторов 37

1.2.5 Теоретические пределы 44

2 АРХИТЕКТУРА ДЕКОМПИЛЯТОРА 46

2.1 Фазы декомпиляции 46

2.1.1 Синтаксический анализ 47

2.1.2 Семантический анализ 48

2.1.3 Генерация промежуточного кода 50

2.1.4 Генерация графа потока управления 50

2.1.5 Анализ потока данных 51

2.1.6 Анализ графа потока управления 51

2.1.7 Генерация кода 52

2.2 Группировка фаз 53

2.3 Вспомогательный инструментарий декомпилятора 54

2.3.1 Загрузчик 55

2.3.2 Генератор сигнатур 55

2.3.3 Генератор прототипов 56

2.3.4 Дизассемблер 56

2.3.5 Связывание библиотек 56

2.3.6 Постпроцессор 56

3 МЕТОДЫ ДЕКОМПИЛЯЦИИ 58

3.1 Восстановление функций 58

3.1.1 Выделение функций 58

3.1.2 Выявление параметров и возвращаемых значений 60

3.1.3 Распознавание библиотечных функций 64

3.1.4 Обнаружение функции main 67

3.2 Восстановление управляющих конструкций 68

3.2.1 Сводимые и несводимые графы 69

3.2.2 Шаблоны графа потока управления 72

3.2.3 Методы анализа управляющих конструкций 80

4 ПРОЕКТИРОВАНИЕ И РАЗРАБОТКА ДЕКОМПИЛЯТОРА 86

4.1 Введение 86

4.2 Проектирование загрузчика 87

4.2.1 Загрузчик PE файла 88

4.3 Декодер 96

4.4 Дизассемблер 103

4.4.1 Принципы дизассемблирования 103

4.4.2 Проблемы при дизассемблировании 104

4.4.3 Модуль дизассемблирования 104

4.4.4 Алгоритм дизассемблирования 105

4.5 Трассировка программы 110

4.6 Декомпилятор 113

4.6.1 Генерация промежуточного представления 113

4.6.2 Анализ графа потока управления 125

5 АПРОБАЦИЯ 127

6 ВЫВОДЫ 135

7 СПИСОК ЛИТЕРАТУРЫ 137

ВВЕДЕНИЕ

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

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

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

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

В настоящее время из широко используемых компилируемых языков программирования высокого уровня распространены языки Си и Си++, поскольку именно они наиболее часто используются при разработке прикладного и системного программного обеспечения для платформ Windows, MacOS и Unix. Поэтому декомпиляторы с этих языков имеют наибольшую практическую значимость. Язык Си++ можно считать расширением языка Си, добавляющим в него концепции более высокого уровня относительно языка Си. Поскольку при обратной инженерии в целом и при декомпиляции в частности уровень абстракции представления программы повышается, то можно считать, что программы на языке Си являются промежуточным уровнем при переходе от программы на языке ассемблера к программе на языке Си++. Дальше повысить уровень абстракции представления программы можно посредством широко известных методов рефакторинга, позволяющих, например, выделять объектные иерархии из процедурного кода.

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

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

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

Достижение поставленной цели предполагает решение следующих задач:

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

Надо отметить, что в рамках данной работы был реализован прототип, работающий только с исполняемыми файлами семейства ОС Microsoft Windows (PE-файлы), но в будущем планируется его расширить для работы с другими видами исполняемых файлов. Возможность подобного расширения уже заложена в архитектуру прототипа.

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

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

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

1. ОБЗОР СУЩЕСТВУЮЩИХ РАБОТ
1. Предыдущие работы [6]

Самый первый декомпилятор был написан Джоэлом Доннелли в 1960 году на компьютере Remington Rand Univac М-460 Countess в Военно-морской Лаборатории Электроники для декомпиляции машинного кода в язык Neliac. Проектом руководил Профессор Моррис Холстед, занимавшийся декомпиляцией на протяжении 60-х и 70-х годов. Результатом его работы стали методы и способы, определившие фундаментальные основы, по сей день использующиеся при создании декомпиляторов.

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

Далее следует описание наиболее известных декомпиляторов и исследовательских работ, посвященных проблемам декомпиляции. Большинство из этих описаний впервые появились в кандидатской диссертации Кристины Чифуэнтес "Методы обратной компиляции".

1. История декомпиляции (1960-1979)
1. Декомпилятор D-Neliac (1960,1962)

Как сообщает Холстед (Halstead), декомпилятор Donnelly-Neliac (D-Neliac) был разработан Дж. К. Доннели и Х. Энглендером в Военно-морской Лаборатории Электроники (NEL) в 1960 году. Neliac является диалектом Алгола, разработанным в NEL в 1955 году. Декомпилятор D-Neliac преобразовывал машинный код в код на языке Neliac. Различные версии были написаны для компьютеров Remington Rand Univac М-460 Countess и Control Data Corporation 1604.

D-Neliac оказался полезным для перевода программ написанных на других языках на язык Neliac и для обнаружения в них логических ошибок. D-Neliac послужил доказательством того, что возможно создать декомпилятор.

2. Декомпилятор The Lockheed Neliac (1963-1967)

Декомпилятор Lockheed, также известен как декомпилятор из IBM 7094 в Univac 1108 Neliac, который помог в переносе научных приложений с IBM 7094 на новый Univac 1108 от компании Lockheed Missiles and Space. Перфокарты были переведены на Univac 1108 Neliac, а также в код на ассемблере (в тех случаях, когда это было возможно). Двоичный код был получен в результате компиляции приложений на Фортране.

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

3. У. Сассаман (1966)

Сассаман разработал декомпилятор в TRW Inc для упрощения переноса программ с компьютеров второго поколения на третье. Данный декомпилятор получал программы на ассемблере для IBM серии 7000 в качестве входных данных и преобразовывал их в Фортран. Ассемблер был выбран потому, что содержал больше полезной информации по сравнению с двоичным кодом, а Фортран был распространен на компьютерах второго и третьего поколений. Декомпилируемые программы представляли собой инженерные приложения с большим количеством алгебраических алгоритмов. Пользователь приходилось самому определять правила распознавания подпрограмм. Точность декомпиляции была около 90%, но требовала ручного вмешательства.

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

4. Прототип К. Р. Холландера (1973)

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

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

Данный декомпилятор был реализован для трансляции языка System/360 на Алголоподобный язык. Он был написан для компилятора Algol-W, разработанного в Стэндфордском университете. 10 программ, на которых тестировался декомпилятор, были правильно восстановлены.

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

5. Диссертация Хаузела (1973)

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

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

Экспериментальный декомпилятор был написан для декомпиляции ассемблера MIX (MIXAL) на PL/1 для IBM 370. При тестировании 6 программ 88% генерируемого кода были восстановлены правильно, а остальные 12% требовали ручного вмешательства.

Хаузел достиг больших успехов в разработке обобщенного декомпилятора, несмотря на серьезное ограничение по времени (он был написан за 5 человеко-месяцев). Он описывает ряд отображений данных (преобразований) в "Окончательное абстрактное представление" ("Final Abstract Representation") и обратно. Экспериментальный декомпилятор был расширен в работе Фридмана.

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

6. Система Piler (1974)

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

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

Несмотря на то, что система Piler была попыткой разработать общий декомпилятор, в итоге был разработан интерпретатор только для машинного языка GE/Honeywell 600, и скелет преобразователей для Univac 1108 в Fortran и Cobol. Основные усилия этого проекта были сосредоточены на анализаторе.

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

7. Ф. Л. Фридман (1974)

Кандидатская диссертация Фридмана описывает декомпилятор трансляции операционных систем мини-компьютеров в рамках одного архитектурного класса. В работе описаны четыре основных этапа: предварительная обработка, декомпилятор, генератор кода, и компилятор.

В начале, препроцессор преобразует код ассемблера в стандартную форму (описательный язык ассемблера). Декомпилятор получает этот описательный язык, анализирует ее и преобразует во внутреннее представление. Потом из него генерируется FRECL-код, после чего FRECL-компилятор компилирует FRECL-программу в машинный код для целевой платформы. FRECL – это язык высокого уровня для разработки и переноса программного обеспечения. Он был разработан Фридманом, также написавшим для него компилятор. Декомпилятор, использовавшийся в этом проекте был адаптацией декомпилятора Хаузела.

Были проведены два эксперимента. Первый предусматривал перенос небольшой, но закрытой части системы IBM 1130 Disk Monitor в Microdata 1600/21, где на вводимые ассемблерные программы потребовалось около 33% ручного вмешательства. В целом, объем работ, необходимых при подготовке кода для ввода в систему переноса был слишком велик, чтобы завершить его в течение разумного промежутка времени, поэтому было решено провести второй эксперимент. В его рамках программы операционной системы Microdata 1621 декомпилировались в FRECL, а затем – обратно в машинный код Microdata 1621. Некоторые из полученных программ вновь включили в операционную систему для проведения тестирования. В среднем лишь 2% от общего числа ассемблерных инструкций потребовали ручного вмешательства, но окончательная программа имела 194% увеличение числа машинных инструкций.

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

8. Ultrasystems (1974)

Согласно информации, полученной от консультанта по системному проектированию Ultrasystems Inc. Г.Л. Хопвуда, его компания вела разработку декомпилятора для программного обеспечения субмарин Trident. Данный декомпилятор использовался при составлении документации для кода систем ведения огня. В качестве входных данных он принимал ассемблерные программы Trident и декомпилировал их в код на языке высокого уровня Trident (Trident High Level Language), разрабатывавшийся в их компании. Были выделены четыре основных этапа: нормализация, анализ, упрощение выражений и генерация кода.

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

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

9. В. Шнайдер и Г. Уиниджер (1974)

Шнайдер и Уиниджер опубликовали нотацию с подробным описанием компиляции и декомпиляции языков высокого уровня. Определив контекстно-свободную грамматику для процесса компиляции, статья описывала применение такой грамматики для получения исходного кода программы из объектного модуля. Более того, неоднозначная грамматика компиляции должна была производить оптимальный объектный код и приводить к генерации однозначной грамматики при декомпиляции. Проверка, проведенная позднее, показала, что объектный модуль, полученный из Algol 60, не может быть декомпилирован детерминировано.

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

10. Декомпиляция польского кода (1977, 1981, 1988)

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

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

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

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

11. Кандидатская диссертация Хопвуда (1978)

В кандидатской диссертации Хопвуда описывается 7-ступенчатый декомпилятор, написанный для облегчения процесса переноса программ и реверс инжиниринга при составлении документации. В ней также утверждалось, что в процессе декомпиляции может помочь ручное вмешательство или предоставление дополнительных внешних данных.

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

Экспериментальный декомпилятор был написан для машины Varian Data 620/i. Он восстанавливал ассемблер в MOL620, машинно-ориентированный язык, разработанный в Калифорнийском университете М.Д. Хопвудом и самим автором работы – Г.Л. Хопвудом. Декомпилятор был проверен на большой программе-отладчике Isadora. Получившийся код требовал дополнительной ручной корректировки перед повторной компиляцией из-за наличия самомодифицирующегося кода, использования дополнительных регистров для вызова подпроцедур и вызовов прерываний обслуживающих программ. Окончательная программа была лучше документирована, чем оригинальная программа на ассемблере.

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

12. Д.А. Уоркман (1978)

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

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

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

2. История декомпиляции (1980-1999)
1. Zebra (1981)

Прототип Zebra был разработан в Военно-морской Лаборатории Электроники для портирования ассемблерных программ. Zebra принимал на входе подмножество ассемблера ULTRA/32, называемое AN/UYK-7, и генерировал ассемблер для PDP11/70.

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

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

2. Декомпилятор Forth (1982, 1984)

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

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

3. Система Переноса Программного Обеспечения (1985)

Ч.В. Йо описывает автоматическую Систему Переноса Программного Обеспечения (Software Transport System, STS), которая портирует ассемблерный код с одного компьютера на другой. Процесс переноса включает в себя декомпиляцию ассемблерной программы в язык высокого уровня на одной машине и последующую компиляцию полученного кода на другой.

Экспериментальный декомпилятор был разработан для архитектуры Intel 8080. В качестве входных данных он принимал ассемблерный код, который декомпилировался в программу на языке PL/M. Перекомпилированная программа PL/M была на 23% эффективнее, чем ее исходная версия на ассемблере. Экспериментальный декомпилятор STS была разработан с целью создания кросс-компилятора языка Си для процессоров Z-80. Проект столкнулся с проблемой отсутствия типов данных в STS.

Как упоминалось выше STS получал в качестве входных данных ассемблерный код для одной машины и ассемблерную грамматику для другой, а на выходе генерировал ассемблерную программу для последней. Полученная на входе грамматика анализировалась для определения таблицы, используемой синтаксическим анализатором для разбора кода и генерации абстрактного синтаксического дерева (АСД) программы. Далее АСД поступало на вход декомпилятору, который затем разбирал поток управления и поток данных методами, описанными Холландером, Фридманом и Барбом, и в конечном итоге генерировал код на языке высокого уровня. Полученный код затем компилировался для целевой машины.

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

4. FermaT (1989)

Кандидатская диссертация Мартина Уорда является работой, формализующей процесс трансляции программ. Он написал FermaT – движок для преобразования программ, который облегчал прямой и обратный инжиниринг с языка ассемблера в спецификацию и обратно. Была произведена декомпиляция нескольких реальных ассемблерных программ, таких как IBM-370, на Си и COBOL, а впоследствии и с ассемблера 80186 на Си. В настоящее время эта технология распространяется компанией SoftwareMigrations.

5. exe2c (1990)

Компания Austin Code Works спонсировала создание декомпилятора exe2c для семейства PC-совместимых компьютеров под управлением операционной системы DOS. Проект был анонсирован в апреле 1990 года, после того, как его протестировало около 20 человек, было решено, что его необходимо доработать. Через год проект вышел в виде беты, но так никогда и не был закончен.

exe2c является многопроходным декомпилятором, состоящим из 3-х программ: e2a, a2aparse и е2с. e2a – это дизассемблер, преобразующий исполняемые файлы в ассемблер, и снабжающий комментариями ассемблерный листинг. a2aparse является транслятором ассемблера во front-end Си, анализирующим файл, созданный e2a, и генерирующим файлы.cod и.glb. Наконец, е2с транслирует файлы, подготовленные a2aparse, и генерирует код на псевдо-Си языке. Также в рамках проекта предоставлялась интегрированная среда envmnu.

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

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

6. Восстановление типов при декомпиляции. А. Майкрофт (1999)

Одной из самых трудных задач, которые приходится решать в процессе декомпиляции – это правильное восстановление высокоуровневых типов данных. ППод такими типами подразумеваются структуры, массивы и пр. В своей работе, Алан Майкрофт (Alan Mycroft) представляет систему для определения высокоуровневых типов в ассемблерном (RTL) коде. Система определения типов Майкрофта во многом основывается на работе Милнера для ML. Майкрофт описывает систему типов в целом, а также ограничения, накладываемые на конкретные типы, такие как структуры и массивы. Экспериментальные результаты работы системы остаются недоступными.

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

3. История декомпиляции (2000-н/в)
1. Asm21toc (2000)

Asm21toc ­– это декомпилятор ассемблера для кода цифровой обработки сигнала (ЦОС). Авторы отмечают, что ЦОС является одной из немногих областей, где до сих пор широко используется ассемблер. Как уже отмечалось, декомпилировать ассемблер значительно проще, чем сам исполняемый код; фактически, авторы "сомневаются в полезности" декомпиляции бинарных файлов.

2. Декомпиляция низкоуровневого кода для проверки его правильности (2001)

Катцумата и Охори опубликовали работу по декомпиляции на основе теоретических методов математического доказательства. На вход декомпилятору подавался Jasmin, по сути, ассемблерный язык для Java. На выходе получался ML-подобный упрощенный функциональный язык. В их примере демонстрировалось, как реализация итеративной функции факториала превращается в две функции (эквивалент рекурсивной реализации). Особенность такого подхода состояла в обработке каждой инструкции как математического доказательства, представляющего свое вычисление. Хотя их работу нельзя применить непосредственно при написании общего декомпилятора, она может использоваться в случаях необходимости доказательства валидности (обычно на этапе компиляции).

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

3. Анализ компьютерной безопасности с помощью декомпиляции и высокоуровневой отладки (2001)

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

4. Распространение типов в дизассемблере IDA Pro (2001)

И. Гильфанов рассказывает о системе распространения типов (type propagation system) в популярном дизассемблере IDA Pro. В ней типы параметров библиотечных вызовов восстанавливаются из заголовочных фалов, а типы параметров для часто используемых библиотек сохраняются в файлах, называемых библиотеками типов. В местах, где происходит определение параметров, вставляются комментарии с указанием имени и типа параметра. Далее эта информация распространяется на другие части дизассемблируемой программы, в том числе и на все известные вызывающие функции. В настоящее время попытки найти типы переменных, не связанных с параметрами библиотечных вызовов, не предпринимаются.

5. DisC (2001)

DisC – декомпилятор, предназначенный только для чтения программ, написанных на Turbo C версии 2.0 или 2.01, является примером декомпилятора к компилятору. У такого подхода нет существенных преимуществ, так как сложность реализации общих методов декомпиляции не намного выше. Интересно, что поскольку большинство аспектов декомпиляции представляют собой сравнение с каким-либо эталоном, то основная разница между общими и частными декомпиляторами – это только тип шаблонов, которые используются при сопоставлении.

6. ndcc (2002)

Андре Янц (Andr Janz) изменил dcc для работы с 32-битными PE-файлами (Portable Executable). Цель этого проекта – разработка модифицированного декомпилятора для анализа вредоносного программного обеспечения. По словам автора, для полной реализации подмножества инструкций процессора 80386 необходимо было переписать декомпилятор. Тем не менее, несмотря на серьезные ограничения dcc, были достигнуты неплохие результаты.

7. Анализ косвенных вызовов при трансляции бинарных файлов(2002)

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

8. Boomerang (2002)

Декомпилятор с открытым исходным кодом, с несколькими front-ends (два хорошо развиты) и back-end для языка Си. Он использует внутреннее представление, основанное на Static Single Assignment (SSA) и анализе типов на основе потока данных. Ссылка на сайт проекта: http://boomerang.sourceforge.net.

9. Desquirr (2002)

Плагин IDA Pro, написанный Дэвидом Эрикссоном (David Eriksson) в рамках магистерской диссертации. Хотя плагин не является полноценным декомпилятором, он показывает, что с помощью мощного дизассемблера и приблизительно 5000 строк кода на C++, можно достигнуть неплохих результатов. Так как дизассемблер не содержит семантики машинных команд, то для каждого поддерживаемого процессора требуется написать модуль для декодирования инструкций и способов адресации. Поддерживаются процессоры X86 и ARM. Условия и циклы, интерпретируются как goto, есть простой анализ переходов, некоторые возможности восстановления параметров и возвращаемых значений. http://desquirr.sourceforge.net/desquirr.

10. CodeSurfer (2004)

Балакришнан (Balakrishnan) и Репс (Reps) из Университета Висконсина разработали инфраструктуру для анализа бинарных программ, названную ими Codesurfer/x86. Целью являлось получение промежуточного представления, похожего на то, которое может быть создано для программы на языке высокого уровня. Вначале дизассемблер IDA Pro производит разбор бинарного файла, после чего для получения промежуточного представления применяется алгоритм анализа возможных значений (Value-set Analysis, VSA). Полученный результат представляется в CodeSurfer для последующего анализа. http://www.grammatech.com/research/technologies/codesurfer

11. Анализ типов для Декомпиляторов (2004)

В своей дипломной работе для Технического Университета Дрездена Р. Фальке (R. Falke), реализует адаптацию теории ограничения типов Майкрофта в декомпиляторе под названием YaDeC. Он расширил теорию для обработки массивов. Чтобы иметь возможность легко управлять проектом, он использовал objdump в виде front-end'а, игнорировал числа с плавающей точкой и допускал передачу параметров только через стек.

12. Andromeda (2004-2005)

Андрей Шульга (A. Shulga) написал декомпилятор для языка Си и платформы Windows x86. Конечный вариант декомпилятора так никогда и не был выпущен. В настоящее время написан только front-end для x86 и back-end для C/C++, хотя утверждается, что декомпилятор способен взаимодействовать и с другими front-end и back-end. Демонстрация работы впечатляет, но не ясно, генерируется ли она автоматически или же производится ручное вмешательство. Веб-страница неактивна с мая 2005 года.

13. Hex Rays Decompiler (2007)

И. Гильфанов, автор дизассемблера IDA Pro, выпустил коммерческий плагин для декомпиляции к IDA Pro. Этот плагин добавляет в программу различные инструменты декомпиляции. Просмотреть можно только одну функцию за раз; однако большинство функций декомпилируются в доли секунды, выдавая на выходе Cи-подобный код. Автор подчеркивает, что плагин написан как вспомогательный инструмент, и генерируемый им код не предназначен для повторной компиляции. Вывод включает в себя логические операторы (|| и &&), циклы (for, while, break и.т.д.), параметры функции и возвращаемые ими значения. Существует также API, который позволяет пользователю написать дополнительный функционал для расширения возможностей декомпилятора. На данном этапе, поддерживается только архитектура x86. Декомпилятор зависит от дизассемблера (и возможности ручного вмешательства), отделяющего код от данных и идентифицирует функции.

14. Static Single Assignment (2007)

В октябре 2007 года М. Ван Эммерик (M. Van Emmerik) закончил написание диссертации основной темой, которой было упрощение анализа различных аспектов декомпиляции с помощью SSA-представления. В работе также затрагивались проблемы анализа типов и анализа косвенных переходов и вызовов.

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

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

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

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

В отличие от этого, плагин Hex-Rays принимает на вход программу, являющуюся результатом работы дизассемблера IDA Pro, то есть схему программы на ассемблеро-подобном языке программирования. В качестве результата Hex-Rays выдает восстановленную программу в виде схемы на Си-подобном языке программирования.

1. Boomerangс

Декомпилятор Boomerang является программным обеспечением с открытым исходным кодом. Разработка этого декомпилятора активно началась в 2002 году, на данный момент есть только альфа версия. Начиная с 2006 года проект не разрабатывается. Изначально задачей проекта была разработка такого декомпилятора, который восстанавливает исходный код из исполняемых файлов, вне зависимости от того, с использованием какого компилятора и с какими опциями исполняемый файл был получен. Для этого в качестве внутреннего представления было решено использовать представление программы со статическими одиночными присваиваниями (SSA). Однако, несмотря на поставленную цель, в результате декомпилятор не сильно адаптирован под различные компиляторы и чувствителен к применению различных опций, в частности, опций оптимизации. Еще одной особенностью, затрудняющей использование декомпилятора Boomerang, является то, что в нем не поддерживается распознавание стандартных функций библиотеки Си.

2. DCC

Проект по разработке этого декомпилятора был открыт в 1991 году и закрыт в 1994 году с получением главным разработчиком степени PhD. В качестве входных данных декомпилятор DCC принимает 16-битные исполняемые файлы в формате DOS EXE. Алгоритмы декомпиляции, реализованные в этом декомпиляторе, основаны на теории графов (анализ потока данных и потока управления). Для распознавания библиотечных функций используется сигнатурный поиск, для которого была разработана библиотека сигнатур. Однако надо заметить, что, несмотря на это, декомпилятор плохо справляется с выявлением функций стандартной библиотеки.

3. REC

Этот проект был открыт в 1997 году компанией BackerStreet Software, но вскоре закрылся из-за ухода ведущего разработчика проекта. Позднее разработка декомпилятора продолжилась его автором в статусе собственного продукта. Сейчас декомпилятор распространяется свободно, а развивается медленно. Одной из особенностей рассматриваемого декомпилятора является то, что он восстанавливает исполняемые файлы в различных форматах, в частности ELF и PE. Также декомпилятор REC можно использовать на различных платформах. В ходе тестирования этого декомпилятора было отмечено, что наиболее успешно декомпилятор восстанавливает исполняемые файлы, полученные при компиляции с включением опций, которые отвечают за отключение оптимизаций и добавление отладочной информации.

4. Hex-Rays

Hex-Rays не является самостоятельным программным продуктом, а распространяется в виде плагина к дизассемблеру IDA Pro. Это самое новое из рассматриваемых средств декомпиляции: плагин появился на рынке в 2007 году. Особенностью данного инструмента является то, что он, как отмечалось, восстанавливает программы, полученные на выходе дизассемблера IDA Pro. Среди алгоритмов, используемых в Hex-Rays, заслуживают внимания алгоритм сигнатурного поиска FLIRT и алгоритм поиска параметров в стеке PIT (Parameter Identification and Tracking).

2. Проблемы декомпиляции

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

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

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

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

В таблице приведены проблемы, с которым приходится сталкиваться декомпиляторам разных типов:

• декомпиляторы байт-кода Java и CLI/CIL;
• декомпиляторы ассемблерного кода и объектных файлов;
• идеальный дизассемблер, преобразующий машинный код ассемблер, который можно заново собрать;
• идеальный декомпилятор машинного кода, который может представить исходную программу на высокоуровневом языке, который можно перекомпилировать;
• проблемы, которые были решены в декомпиляторах dcc и Reverse Engineering Compiler (REC)

Проблема	Декомпилятор бинарного кода	Декомпилятор dcc	Декомпилятор REC	Декомпилятор объектных модулей	Декомпилятор ассемблерного кода	Идеальный дизассемблер	Декомпилятор байт-кода Java	Декомпилятор CLI
Отделение кода от данных	Да	частично	частично	частично	нет	да	нет	нет
Отделение указателей от констант	Да	нет	нет	легко	нет	да	нет	нет
Восстановление указателей, сложенных со смещением	Да	нет	нет	легко	нет	да	нет	нет
Объявление данных	Да	нет	нет	да	легко	да	легко	легко
Восстановление параметров и возвращаемых значений функций	Да	да	большая часть	да	да	нет	нет	нет
Анализ неявных переходов и вызовов	Да	нет	нет	да	да	да	нет	нет
Анализ типов	Да	нет	нет	да	частично	нет	для большинства локальных переменных	нет
Слияние инструкций	Да	да	да	да	да	нет	да	да
Восстановление управляющих конструкций	Да	да	да	да	да	нет	да	да
Итог	9	3,5	3,25	6,5	4,5	5	2,5	2

1. Отделение кода от данных

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

Для обеспечения возможности повторной компиляции программы необходимо решить ряд проблем, первичная из которых – отделение кода от данных. Основная причина этой проблемы в принципе однородности памяти Фон Неймановской архитектуры, согласно которому построено большинство современных ЭВМ. Было доказано, что общее решение этой задачи по сложности эквивалентно решению проблемы останова. Названия секций исполняемого файла.text или.data никак не отражают их содержимого, поскольку и компиляторы, и программисты часто вставляют константные данные (например, текстовые строки или таблицы переходов) в секцию кода, или наоборот – программный код в секцию данных. Как результат, проблема отделения кода от данных остается актуальной.

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

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

Одной из задач отделения кода от данных является выявление границ процедур. Такая проблема отсутствует в программах, использующих стандартные инструкции вызова и возврата. Можно выявить случаи оптимизации хвостовой рекурсии, когда пары инструкций call и return заменяются на jmp, который переходит на начало той же функции, что и инструкция call. Стоит учесть, что существуют такие компиляторы, как MLton, не использующие общепринятые нотации при вызове функции и возврате из нее значения. MLton генерирует код, используя Continuation Passing >

Очевидно, что для декомпиляторов байт-кода Java или CIL, проблема разделения кода и данных не актуальна.

2. Отделение указателей от констант

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

3. Восстановление указателей, сложенных со смещением

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

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

#include <stdio.h>

int a[8] = {1, 2, 3, 4, 5, 6, 7, 8};

float b[8] = {1., 2., 3., 4., 5., 6., 7., 8.};

char* str = "collision!";

int main()

{

int i;

for (i=-16; i < -8; i++)

printf("%-3d ", (a+16)[i]);

printf("\n");

for (i=-8; i < 0; i++)

printf("%.1f ", (b+8)[i]);

printf("\n");

printf("%s\n", str);

return 0;

}

и результата ее дизассемблирования в машинный код для архитектуры x86 с помощью IDA Pro:

mov eax, offset str

lea eax, [edx+eax]

mov eax, [eax]

push eax

push offset a3d ; "%-3d "

call sub_8048324 ; printf

mov eax, offset str

lea eax, [edx+eax]

fld dword ptr [eax]

lea esp, [esp-8]

fstp [esp+24h+var_24]

push offset a_1f ; "%.1f "

call sub_8048324 ; printf

mov eax, str

push eax

call sub_8048304 ; puts

Главное, на что стоит обратить внимание – это использование в машинном коде одной и той же константы str для доступа ко всем трем массивам. В данной программе таблица символов не была разделена, что позволило дизассемблеру получить значения констант, которые используются в инструкциях, работающих с массивом. В то же время дизассемблер ошибочно посчитал указатель str основным для всех трех массивов. Единственный способ определить, что в первых двух случаях str является результатом сложения основного указателя со смещением, это проверить границы возможных значений для переменной i (регистр edx в машинном коде содержит i*4).

При декомпиляция первых двух массивов в

((int*)(str-16))[i]

и

((float*)(str-8))[i]

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

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

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

4. Виды декомпиляторов

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

Из рисунка ниже видно, что в процессе компиляции исходного кода в ассемблер смешения данных не происходит. На данном этапе есть возможность сохранить простые комментарии (даже на уровне циклов, до и после вызовов процедуры и.т.д.). Более детальные комментарии, а так же управляющие конструкции (циклы, условные операторы), будут потеряны. Исходные выражения разбиваются на множество элементарных арифметических операций (сложение, умножение и т.д.). Еще могут оставаться представления некоторых высокоуровневых типов. Например, доступ к полю структуры Customer.address получается с помощью символов Customer (адрес структуры) и address (смещение для поля address). Массив чисел с плавающей точкой начинается с метки, а место под него выделяется ассемблерными командами, таким образом, несмотря на потерю информации о типе данных, которые в нем хранятся, имя массива и его размер все же сохраняются. Итак, можно сделать вывод, что в декомпиляции из ассемблерного кода, возникает при намного меньше проблем, чем при декомпиляцией из машинного представления.

Рис. 1. Потеря информации в процессе компиляции

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

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

1. Дизассемблеры

Для создания идеального декомпилятора на базе идеального дизассемблера нужно решить следующие задачи:

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

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

2. Декомпиляторы ассемблерного кода

Среди всех видов декомпиляторов с наименьшим количеством проблем сталкиваются те, что принимают на вход только ассемблерный код. Основная причина заключается в том, что не нужно заниматься отделением кода от данных. Более того, здесь присутствуют комментарии и понятные названия переменных, функций, указателей и их смещений. Анализ типов и объявление данных осуществляются довольно просто. Более того, есть имена и размеры объектов, так что выделение основных и смещенных указателей тоже не представляет собой серьезную проблему. В листинге представлен ассемблерный код для программы из листинга выше с явными метками a, b и str.

movl $a+64, %eax

leal (%edx,%eax),%eax

movl (%eax), %eax

pushl %eax

pushl $.LC1 ;"%-3d "

call printf

movl $b+32, %eax

leal (%edx,%eax),%eax

fld (%eax)

leal -8(%esp), %esp

fstpl (%esp)

pushl $.LC2 ; "%.1f "

call printf

movl str, %eax

pushl %eax

call puts

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

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

3. Декомпиляторы объектного кода

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

mov eax, (offset a+40h)

lea eax, [edx+eax]

mov eax, [eax]

push eax

push offset a3d ; "%-3d "

call printf

mov eax, (offset b+20h)

lea eax, [edx+eax]

fld dword ptr [eax]

lea esp, [esp-8]

fstp [esp+24h+var_24]

push offset a_1f ; "%.1f "

call printf

mov eax, str

push eax

call puts

Как видно, здесь все еще содержатся ссылки на символы a, b и str.

4. Декомпиляторы байт-кода Java и CLI

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

• данные отделены от кода;
• определение констант и указателей является очень простой задача, благодаря наличию отдельных инструкций для работы со ссылками (getfield, new);
• параметры и возвращаемые значения определяются явно;
• в декодировании какой-либо глобальной информации нет необходимости, потому что вся она содержится в классах, поля-члены классов могут быть получены непосредственно из байт-кода;
• анализ типов нужно проводить только для локальных переменных, т.к. несмотря на наличие отдельных инструкций для целых чисел, ссылок, чисел с плавающей запятой, нельзя получить точную информацию с каким именно подтипом ведется работа (например, bool, short или int).

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

Единственная дополнительная задача, которую потребуется решить – это преобразование инструкций Java (или CIL), ориентированных на работу со стеком, в стандартные инструкции процессора по работе с регистрами. Хотя реализация такого алгоритма довольно проста, для этого потребуется создавать временные переменные, хранящие последнее значение стека. Некоторые декомпиляторы игнорируют данную проблему, что приводит к ошибкам при декомпиляции оптимизированного байт-кода.

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

5. Недостатки существующих реализаций декомпиляторов

Все реализации декомпиляторов, имеющиеся на данный момент имеют проблемы при идентификации параметров и возвращаемых значений функций, определении неявных вызовов и переходов. Анализ типов проводится ими в неполном виде, а максимальный размер программ, принимаемых на входе, сильно ограничен. В качестве примера возьмем два известных декомпилятора: REC и dcc. REC – некоммерческий декомпилятор, восстанавливающий получаемые программы в C-подобный код. Способен работать с несколькими видами бинарных файлов. dcc – декомпилятор, написанный в исследовательских целях, принимает на вход только программы DOS для архитектуры 80286 и восстанавливает их код на C.

Проблемная область	dcc	REC
Обработка больших программ	Нет	Да, но не проводит серьезного межпроцедурного анализа
Определение параметров и возвращаемых значений функций	Да, но проводит межпроцедурный анализ только для регистров, а для параметров на стеке делает предположения	Результаты непостоянны
Непрямые переходы	Сравнимает шаблоны на уровне промежуточного представления; сообщает о необходимости определения «дополнительных идиом»	Результаты непостоянны
Неявные вызовы	Указатели на функции определяются, как константы; высокоуровневый код не восстанавливается	Высокоуровневый код не восстанавливается
Анализ типов	Восстанавливает пары регистров для long int’ов; не восстанавливает числа с плавающей запятой, массивы данных, структуры	Не восстанавливает числа с плавающей запятой, массивы данных, структуры