О некоторых задачах обратной инженерии

К.Н. Долгова, А.В. Чернов, Труды Института системного программирования РАН

Назад Содержание

5.3. REC

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

5.4. Hex-Rays

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

В таблице 1 представлена сводная характеристика всех рассматриваемых декомпилятров.

	Boomerang	DCC	REC	Hex-Rays
распознавание библиотечных функций	нет	заявлено	нет	да
активность разработки	да	нет	да	да
переносимость	нет	да	да	да
open source	да	да	нет	нет

Таблица 1. Сравнительный анализ декомпиляторов

6. Исследование возможностей декомпиляторов

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

Тестирование проводилось по следующей методике. Исходный код программы на Си компилировался компилятором gcc 3.4.5 в среде Debian Linux и компилятором Borland C++ 3.1 в среде Windows XP. В первом случае результатом работы компилятора являлся файл формата ELF для архитектуры ia32, во втором – исполняемый файл DOS для 16-битного режима процессора. Исполняемый файл формата ELF подавался на вход декомпиляторам Boomerang, REC и Hex-Rays, работающим в среде Windows XP. Исполняемый файл формата DOS~EXE подавался на вход декомпилятору DCC. Результат декомпиляции сравнивался с исходным текстом.

Такая комбинация инструментальных и целевых сред была выбрана по следующим причинам. Во-первых, декомпилятор DCC поддерживает только 16-битные исполняемые модули DOS, поэтому для оценки качества работы декомпилятора был использован компилятор 16-битного режима. Декомпиляторы Boomerang и REC, наоборот, не поддерживают 16-битный режим DOS. Исполняемый модуль подавался на вход декомпиляторам в формате ELF, а не в естественном для Windows формате PE, поскольку, как оказалось, декомпиляторы Boomerang и REC некорректно обнаруживают точку начала программы на Си в файлах формата PE.

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

Так, оценка «3» выставлялась в случаях, когда в декомпилированной программе использовались адресная арифметика вместо массивов или приведение типов для получения указательных значений вместо корректного объявления типов переменных. Кроме того, оценка «3» выставлялась, если в результате декомпиляции цикл for оказывался преобразовыванным в цикл while.

Количество баллов за тест	Комментарий
0	Декомпилятор закончил работу с ошибкой выполнения или пустым результатом.
1	Декомпилятор выдал ассемблерный код. Программа на Си не была получена.
2	Декомпилятор выдал программу на языке Си, которая либо не компилируется, либо работает неверно (неэквивалентна исходной), либо содержит ассемблерные вставки, то есть недекомпилированные фрагменты программы.
3	Декомпилятор выдал корректную программу, которая эквивалентна исходной, но в ней используются конструкции, отличные от конструкций исходной программы.
4	Декомпилятор выдал программу, которая эквивалентна исходной, и в которой используются те же конструкции, которые использовались в исходной программе.

Таблица 2. Шкала оценки декомпиляторов

6.1. Система тестов

Тестовый набор содержал следующие основные группы.

1. Типы. В тестах этой группы проверялась корректность восстановления типов переменных и параметров функций. В языке Си поддерживается богатый набор базовых целочисленных типов от типа char до типа unsigned long long. Декомпилятор должен по возможности точно восстановить как размер, так и знаковость переменной.

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

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

   Для структурных типов проверялся факт распознавания использования структурного типа и точность восстановления полей структур.

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

2. Языковые конструкции. В тестах этой группы проверялась корректность восстановления управляющих структур программы. Проверялась корректность восстановления оператора if с простым условием, в том числе и с отсутствующей частью else, операторов цикла while и do while с простыми условиями.

   В другой группе тестов проверялась корректность восстановления логических операций && (логическое «и»), || (логическое «или») в условиях операторов if и циклов. Согласно семантике языка Си эти операторы транслируются в условные и безусловные переходы, то есть являются конструкциями, задающими поток управления, а не вычисления значений. Декомпиляторы должны по возможности восстанавливать сложные условия в операторах языка.

   Отдельно проверялась корректность восстановления структурных операторов передачи управления, таких как break, continue и return.

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

3. Функции. В тестах этой группы проверялась корректность выделения параметров функций и локальных переменных в условиях разных соглашений о вызовах. Кроме того, проверялась корректность обработки рекурсивных функций.
4. Оптимизации. В тестах этой группы проверялась корректность работы декомпиляторов в ситуации, когда при компиляции были использованы некоторые оптимизационные преобразования, такие как открытая вставка функций (inlining) и оптимизации вызовов функций (tail call optimization, tail recursion optimization, sibling call optimization).
5. Взаимодействие с окружением. В данной группе находился тест, проверяющий корректность обнаружения функции main в исполняемых файлах формата PE. Как известно, выполнение программы на языке Си начинается с функции main, которой передается определенный список параметров. Однако в исполняемых файлах вызову функции main предшествует выполнение специального кода, задача которого настроить окружение программы на Си, что заключается, в частности, в создании стандартных потоков ввода-вывода, инициализации служебных структур данных управления динамической памятью и т. п. Этот код частично написан на языке ассемблера, кроме того, он не представляет интереса, так как является стандартным для всех программ. Поэтому декомпиляторы должны игнорировать этот инициализационный код и начинать декомпиляцию непосредственно с функции main.

   Кроме того, в тестах этой группы проверялось распознавание стандартных библиотечных функций языка Си (например, strlen и т. п.). Реализация сигнатурного поиска присутствует в декомпиляторе DCC, но наиболее развита эта технология в декомпиляторе Hex-Rays.

6.2. Результаты тестирования

В таблице 3 приводятся результаты работы декомпиляторов на выбранном наборе тестов в соответствии с системой оценок, приведенной в таблице 2. Каждый столбец таблицы соответствует декомпилятору, а каждая строка – тесту. Общий результат для каждого декомпилятора получен суммированием оценок по всем тестам.

Из всех рассмотренных декомпиляторов только Boomerang поддерживает декомпиляцию оператора switch. Остальные декомпиляторы генерируют в этом случае некорректный код на языке ассемблера. Только декомпилятор REC сумел восстановить цикл for, в то время как остальные декомпиляторы в этом случае генерируют программу, использующую цикл while.

		Bom-merang	Rec	DCC	Hex-Rays
типы данных	struct	3	2	3	3
	массивы	4	3	3	4
	unsigned int	4	3	3	3
	unsigned short	3	3	3	3
структурные конструкции языка	логические операции	4	4	4	4
	циклы for	3	4	3	3
	циклы while	4	3	4	4
	циклы do while	4	4	4	4
	оператор switch	4	2	2	2
функции	рекурсия	4	4	4	4
оптимизация	inlining	2	2	–	2
	tail recursion	2	2	–	2
обнаружение функции main в PE файлах		1	1	–	4
обнаружение функций стандартной библиотеки		2	2	3	4
сумма баллов		48	43	40	50

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

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

7. Заключение.

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

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

Литература

1. Гуильфанов И. FLIRT – Fast Library Identification and Recognition Technology. http://www.idapro.ru/description/flirt/
2. Щеглов К.Е. Обзор алгоритмов декомпиляции//Электронный журнал «Исследовано в России». http://zhurnal.ape.relarn.ru/articles/2001/116.pdf
3. AT\&T Assembly Syntax. http://sig9.com/articles/att-syntax
4. G. Balakrishnan, T. Reps. Analyzing Memory Accesses in x86 Executables. Compiler Construction vol. 2985/2004, Springer Berlin / Heidelberg, 2004, стр. 5-23.
5. Boomerang Decompiler Home Page. http://boomerang.sourceforge.net/
6. C. Cifuentes, D. Simon, A. Fraboulet. Assembly to High-Level Language Translation. Technical Report 439. Department of Computer Science and Electrical Engineering. The University of Queensland. 1998.
7. M. Davis. Computability and Unsolvability, New York: McGraw-Hill, 1958.
8. DCC Decompiler Home Page. http://www.itee.uq.edu.au/~cristina/dcc.html
9. Agner Fog. Calling conventions for different C++ compilers and operating systems.
10. Hex-Rays Decompiler SDK. http://www.hex-rays.com/
11. Интерактивный дизассемблер Ida Pro. http://www.idapro.ru/
12. Steven S. Muchnik. Advanced Compiler Design And Implementation.
13. А. Mycroft. Type-based decompilation. In European Symp. on Programming, 1999.
14. REC Decompiler Home Page. http://www.backerstreet.com/rec/
15. Tool Interface Standards (TIS). Executable and Linkable Format (ELF). http://www.x86.org/intel.doc/tools.htm
16. Tool Interface Standards (TIS). Portable Executable Formats (PE). http://www.x86.org/intel.doc/tools.htm

Назад Содержание