Исследование и разработка методов декомпиляции программ тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат физико-математических наук Трошина, Екатерина Николаевна

• Трошина, Екатерина Николаевна
• кандидат физико-математических наук
• 2009

Оглавление диссертации кандидат физико-математических наук Трошина, Екатерина Николаевна

Введение

1 Декомпиляция как задача обратной инженерии

1.1 Задача декомпиляции как составляющая задачи обратной инженерии

1.1.1 Обзор задачи дизассемблирования

1.1.2 Декомпозиция задачи декомпиляции на подзадачи.

1.1.3 Универсальность в задаче декомпиляции.

1.1.4 Корректность декомпиляции.

1.2 Декомпиляция Си программ.

1.2.1 Строго удовлетворяющие стандарту Си программы

1.2.2 Качество декомпиляции.

1.2.3 Постановка задачи.

2 Методы и инструментальные средства декомпиляции программ

2.1 Восстановление функционального интерфейса программы.

2.1.1 Обнаружение функции main.

2.1.2 Восстановление библиотечных функций и системных вызовов

2.1.3 Восстановление функций.

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

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

2.3 Восстановление типов данных.

2.3.1 Методы математической логики в задаче восстановления типов

2.3.2 Интервальный анализ в задаче восстановления типов данных

2.3.3 Восстановление типов на основе шаблонов.

2.3.4 Смежные подходы решения задачи восстановления базовых типов данных.

2.4 Использование информации времени выполнения для повышения качества декомпиляции.

2.4.1 Обзор работ, рассматривающих использование информации времени выполнения программы.

2.4.2 Система Valgrind.

2.5 Инструментальные средства.

2.5.1 Boomerang.

2.5.2 DCC.

2.5.3 REC.

2.5.4 HexRays.

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

3 Восстановление типов данных

3.1 Основные идеи алгоритма

3.2 Объекты

3.3 Восстановление базовых типов данных.

3.3.1 Представление типов данных.

3.3.2 Система уравнений модельных типов.

3.3.3 Ограничения.

3.3.4 Объединение типовых переменных

3.3.5 Решение системы уравнений зависимости типов.

3.3.6 Алгоритм восстановления базовых типов данных.

3.4 Восстановление производных типов данных.

3.4.1 Общее описание работы алгоритма.

3.4.2 Формальное описание алгоритма

4 Использование информации о выполнении программы для повышения качества декомпиляции

4.1 Профилирование значений ячеек памяти.

4.2 Распознование инструкций memset и memcpy.

4.3 Профилирование кучи

4.4 Экспериментальные результаты.

5 Декомпилятор TyDec

5.1 Инструментальная среда декомпиляции программ TyDec.

5.1.1 Архитектура.

5.2 Компоненты системы.

5.2.1 Реализация восстановления функционального интерфейса.

5.2.2 Восстановление структурных конструкций.

5.2.3 Восстановление типов данных.

5.3 Утилиты профилирования.

5.3.1 Утилита TDTrace.

5.3.2 Утилита TDHeap.

5.3.3 Накладные расходы профилирования.

5.4 Сравнительная оценка качества восстановления программ декомпилятором TyDec.

Введение диссертации (часть автореферата) на тему «Исследование и разработка методов декомпиляции программ»

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

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

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

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

Если восстановленная программа функционально эквивалентна исходной, то декомпиляция выполнена корректно. На рис. 1 представлен пример программы, которая декомпилирована некорректно. Слева представлена исходная программа на языке Си, а справа представлена программа, восстановленная декомпилятором boomerang [9]. Восстановленная функция ргос16 соответствует исходной функции f, функции g и read исходной программы в тексте восстановленной программы опущены как несущественные. В функции main в строке 24 вызывается функция g с параметром еах, переменная ах соответствует регистру %еах, через который возвращается значение функции. Так как функция ргос16 восстановлена как не возвращающая значение, то функция g не будет вызвана с параметром, содержащим результат работы функции ргос16, тогда как в исходной программе функции g в строке 23 в качестве параметра передается результат работы функции f. Следовательно, восстановленная программа не является функционально эквивалентной исходной программе. Более того, можно отметить, что выражение в строке 11 восстановленного листинга не соотвествует стандарту языка Си, так как нарушены правила арифметики указателей. Такое выражение будет обработано компилятором семейства GNU GCC последних версий, однако другие Си компиляторы выдадут ошибку.

Исходная программа

Восстановленная программа

1 2 3 4

5 В 7

8 9

10 11 12

13

14

15

16

17

18

19

20 21 22

23

24 int read (unsigned short *a, int k){ int i ; for (i = 0; i < k; i+ + ) scan f ('"Xu" Л(а[к ]) ) ; unsigned short f (unsigned abort *a, int k) { unsigned short u = 0; int i ; for(i=0; i <k ; iH—r) u+-a [ i ]; ret urn u; int g(unsigned short u) { printf (,u ) ; int main (void){ int к - 10; unsigned short a [ 1 0 ]; read(a , к ) ; S(f(a, k)); id procl6(void "paraml , int param2) { unsigned int eax; // т24 unsigned int edx ; // r26 unsigned short loca!0 ; // m[ e&p — 6J int locall ; // mf eap — 12} localO — 0; locall ~ 0; while (locall < par am 2) { cdx=( 1or a10 ); eax —"(unsigned short *)( lorall-flocall -fparaml ); localO—(unsigned short) edx-rrax ; locall -f+; ret urn ; it main () { int к = 10; int eax ; unsigned short a (1 0 ]; read(a , к ) ; f(a, k); g(eax);

Рис. 1. Пример некорректно декомпилированной программы

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

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

Исходная программа Восстановленная программа

1 ^include <s t d i о - h> 2 3 void f(doub!e a, double b) { 4 if (л < b) { 5 pr i n t f("a*.<^b\n" ) ; e } 7 if (a > b) { 8 printf("a„>„b\n" ) ; n > 10 return; и > 1 intlfi cdecl sub 401290 (double al , double a2) 2 { 3 intlO result ; // axgtl3 4 5 Ш1 6 { 7 fid [ebp+arg 0] 8 fid [ebp+arg8] 9 fucompp 10 fnstsw ax 11 sail f 12 } 13 if ( !( CF | ZF) ) 14 ///'da: char ~~CF; unsigned tnt8 ZF; 15 printf (".i<-b\n" ); 16 asm 17 { 18 fid [ebp+arg 0] 19 fid [ebp+arg 8) 20 fxch st(l) 21 fucompp 22 fnstsw ax 23 Rfthf 24 } 25 if ( !(CF | ZF) ) 26 result = printf("a>wb\n"); 27 return result; 28 >

Рис. 2. Пример №1 декомпиляции, программы с низким уровнем качества

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

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

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

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

Низкоуровневые конструкции языка Си такие, как явные приведения типов, неестественные циклы, организованные с использования операторов goto или с использованием операторов continue и break, замена оператора множественного выбора switch операторами if и другие низкоуровневые конструкции, а также ассемблерные вставки кода, который не удалось восстановить, крайне нежелательны в восстановленной программе. Автоматически восстановленная программа декомпилирована качественно, если она содержит минимальное количество низкоуровневых конструкций, а также наиболее полно использует высокоуровневые конструкции языка Си. Например, вместо оператора цикла while, если возможно, используется оператор цикла for, вместо операций с адресной арифметикой используются операции доступа к элементам массива.

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

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

Исходная программа Восстановленная программа

1 void f2 (signed short x, 2 unsigned short y) 3 { 4 unsigned short i — 0; 5 fo г ( i =5 0; i < *; i ) « { 7 у 3; 8 g(y); 3 } 10 return ; H } 1 int cdecl sub 401314 ( int ftl, int a2) 2 { .7 3 int result ; // toiflS 4 int v3; // fap + l^hj [bp-Jhlttl 5 signed intlfi v4 ; // [ap + lShj [bp-6h]Ol 6 7 HIWORD(v3) - al j 8 lOWDRDf v3 ) = n2 ; 9 v4 = 0; 10 while ( 1 ) H { 12 result - SHIWORD(v3 ) ; 13 if ((unsignedin 116 ) v4 >=(signed i n t )SHIWORD( v3 ) ) 14 break ; 15 LOVTORD(v3) = ( \\CKD)v3 -r 3j 16 sub 401290 ((unsigned intl6)v3); 17 T+vJ; 18 } 19 return result; 20 }

Рис. 3. Пример №2 декомпиляции программы с низким уровнем качества ную программу на фиксированном языке высокого уровня, назовем универсальным.

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

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

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

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

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

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

Практическая значимость. Разработанные алгоритмы восстановления типов данных реализованы в инструментальной среде декомпиляции TyDec, что позволило восстанавливать все высокоуровневые конструкции языка Си, включая как базовые, так и производные типы данных, оператор множественного выбора switch, оператор цикла for. Предложенные уточнения правил отображения шаблонов графа потока управления и деревьев доминирования программ на языке высокого уровня в конструкции языка Си позволили в рамках системы TyDec реализовать инструмент, который позволяет восстанавливать структурные конструкции языка Си, даже если в программе на низком уровне имелись неструктурные операции выхода из середины цикла (оператор break) и прерывание витка цикла (оператор continue). Предложены методы восстановления типов данных на основе статического и динамического анализа, позволяющие существенно повысить качество декомпиляции программ. Прототип инструментальной среды декомпиляции TyDec, разработанный в рамках представленной работы, позволяет поддерживать унаследованное ПО с утраченными исходными кодами, позволяет восстанавливать структуры данных обмена и протоколы взаимодействия между модулями ПО, а также существенно облегчает задачу исследования ПО с точки зреиия информационной безопасности его использования.

Апробация работы. Основные результаты диссертационной работы опубликованы в статьях [18], [19], [78], [77], [79], [51] , [14], [13], [1], [17], [16], [15], в том числе две [18] и [19] — в изданиях рекомендованных ВАК для публикации результатов кандидатских и докторских диссертаций, и представлены в докладах на следующих конференциях и семинарах. \

1. Международная конференция «15th Working Conference on Reverse Engineering» (WCRE 2008). Антверпен, Бельгия, 15-18 октября 2008 г.

2. Международная конференция «17th International Conference on Program Comprehension» (ICPC 2009). Ванкувер, Канада, 17-19 мая 2009 г.

3. Международная конференция «7th International Andrei Ershov Memorial Conference Perspectives of System Informatics» (PSI 2009). Новосибирск, Россия. 15-19 июня 2009 г.

4. Международный семинар «International Workshop on Program Understanding» (PU 2009). Алтай, Россия. 19-23 июнь 2009 г.

5. Общероссийская научно-техническая конференция «Методы и технические средства обеспечения безопасности информации», Санкт-Петербург, Россия, 7-11 июля 2008 г.

6. Конференция «РусКрипто», г. Звенигород, Россия, 3-5 апреля 2009 г.

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

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

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

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

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

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

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Трошина, Екатерина Николаевна

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

На рис. 58 представлен результат работы декомпилятора TyDec по восстановлению типов данных для примеров 591а1г и 38day. Представлено две программы. Слева расположено окно, отображающее входную программу, а справа от него находится окно, отображающее восстановленную программу. Как можно заметить на рисунке представлено успешное восстановление знаковости типов, указателей более одного уровня косвенности, а также показано восстановление операций доступа к элементам массива.

В таблице 9 приведены результаты ручной проверки качества восстановления типов данных. Колонка 'CLOC' содержит количество строк кода в исходном коде на языке Си, колонка 'ALOC1 содержит количество строк кода в соответствующем ассемблерном коде.

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

YKESii -" *-i* b* в мпн

Jjd

1 •« ant laa aa>. dan Ed ftr tad* ♦ ш ааи]

14 i wr «<tx. dvocd Ptr

IQutttttttQ » cbp]

45; an dtptd ptr t™«1 tda

44i WT tn, dtaatd ptr tortf*e«*rc ♦ atop]

47» an ««, dword per tae*]

1t; ■a* daerd ptr

Опашне * ■bni.

CM

4Ps Jtabai - lOntttitttc abp|,

0X0

111 )na --L5"

Us ll«t

1 nt

141 Xaba-I iGtiuird^ nu> el" "

Si: |v«k abp

61 wr *bp, n;

•7i Bvb aap, 0*B

SOl ae* eax,

Jlil и

2 fa lirt нкЫ; iiiiv I gti rtva> * • int MtiMi wwtpnad ehar • • Int BJtM! «ulpud duf * * Ши1(П«<1 UlMf * * int nvaxa; шм1«м4 DMI * * rwtuci U«t afe ; ■ з chU ■ * *tU * i tbl; bMI * *

Start «ТАОИ kMlftH ftn» • * LeKt(*i wilfnr4 Int («Шмвшш ■uialfnts rtui • * topi val* i tft« nt« addJaoteeoH^dce { wuttiHrt с«мт * •, wmI«M4 •Iwrt, unaIfn«4 rfur • * )r чм1щи| еЬя* • * itlgcu* ( witlftiM diet • . |i m< Niia HiiUou ( )t т»И caveute FOLLOW I itftBlir' 2 № i W Imil li ft Г

• »<* » cue), ее* toruowm ; STT ли tu, dvcrc 1 ([i

-i." ft* ♦ ' < С»' 1]

D^etM; 5*1 t«»l tM. w

W; jM '

UtltMl to: IM ,11 10И4 •

At0капа/ tl'. MV 94ITd til loNi

Hlllfelti 1

I mi

I raU "»»«• It! lafe*l

И; Hf , d«( Itbttrtttti * «Ьр)

3lnt

Int Will

OHIywi rhu tulf;

ItJkt tb*at); Inl Mdli int wl>i al«u< «Ил* uiUj in* Cbxit; IKt №iif ebpl " ( tali • J | | tn W] » (ЬН!

ISt 1*4 W| t«PtU per fi: «и u»ra ptr [tip), tu

•Ts ми ■«*[ *в« dwDcd ptr от « a»* » 0*0) . с ал

491 Iti ей. ilvutil pet (OontrifTS « «Bpj аи d*otd ptr (One * »;) # сам

Tit mm diced ptr [0*9 * up),

JI WT dtHid ptr *

•|i| , OlSO

Mi iu, ivord per

0«Htflt»1 4 Cbp]

141 ■и* ftotd OWl

I «apt ■ 4 )J

I + t I I tl * t|

•tcCeue ( ( rHa* ■ J t -91 ♦ ( int ) ebp; ), тс,

•a*. ( *at4 * ) t 'Ив » I Int > rbpi J, vac5 I i v*C7 • ttrln I 4 unai«na« dw • ) ( * | Int ) ebpj | |; wHtXa ( I | v«7 <• 0 I U | etrp« blee | ), eul * |

4fiB)«na4 OlU I • | OUl«iw4 chM ■ } | -« ♦ ( l*t I ebpi » j la | t w -1*1, I Ut I I • «, Ш1«ма ah*ft • J I ( int 1 • ccypabl®c ( ) t t ea*8 * caxB | ) ( 0192 i " 0 i ) i var"> - ( tat | i vmit - 1 )i

• ( imii(n*4 char • ) ( -9S » 1 t*t I abpz f vac7 } tf ( ■ i ( i*t » аЗауа t I ) — D ) t 1 (tea | odara ( 1 } li

0!

3 - ti wS*T» I 3 I * ttaXaV t I ntlM char • •ЬГ2 I >f

11 | • | ( tat | adara f J J s- 0 > ) | art* ( I, "cau&or aiUuu мам у* )i 1

ЕЯ10 * *f -

I -« * I Ш 1

Рис. 58. Результат работы компоненты восстановления типов данных лице 11. Так как переменная char * endp используется только как аргумент функции getf ield и никогда не разыменовывается, в результате только статического анализа она восстановлена как 4-байтиая переменная типа int. Однако в результате профилирования значений было получено, что показатель «указатель» PC равен 1, следовательно, тип переменой по результатам динамического анализа восстановлен как указатель void*.

Колонка (ВТ' таблицы 10 показывает количество переменных базового типа данных на стеке; переменные, расположенные на регистрах, не учитываются. Колонка 'ExactBT' показывает количество переменных, тип которых был восстановлен точно, а колонка 4СоггВТ' показывает количество переменных, тип которых был восстановлен корректно. Колонка 4Fail ВТ1 показывает количество переменных, тип которых не удалось восстановить ни точно, ни корректно. Колонка 4PTR' содержит количество переменных типа «указатель на переменную базового типа». Колонки 'EcaxtPTR', 'CorrPTR', 'FailPTR* показывают количество переменных указательного типа, тип которых удалось восстановить точно, корректно и не удалось восстановить ни точно, ни корректно соответственно.

Example CT.OC ALOC Description

35vc 107 245 cnt() функция утилиты wc (file 'wc.c')

36cat 27 104 rawcat() функция утилиты cat (file 'cat.c')

37execute 486 1167 execute () функция утилиты be (file 'execute.c')

3Sday 173 346 isnowC) функция утилиты calendar (file 'day.c')

Заключение

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

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

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

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

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

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

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

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

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Трошина, Екатерина Николаевна, 2009 год

1. Брукс Ф. Мифический человеко-месяц или как создаются программные системы. — 1975.

2. Гаулъфанов И. Описание flirt fast library identification and recognition technology // http://www.idapro.ru/description/flirt/. — 1997.

3. Горелик A. M. Программирование на современном Фортране.— Финансы и статистика, 2006.

4. Гусенко М. Ю. Декомпиляция типов данных исполняемых модулей Win32 // Безопасность и конфиденциальность информации в сетях и системах. — 1998. — Pp. 35-36.

5. Гусенко М. Ю. Декомпиляция типов данных исполняемых программ / / Безопасность информационных технологий. — 1998. — Р. 83-88.

6. Гусенко М. Ю. Анализ и метод восстановления управляющих конструкций кода структурной обработки исключений в приложениях Win32 // Информационные технологии. — 1999. — Р. 32-44.

7. Гусенко М. Ю. Метод анализа идиом в исполняемом коде с целью декомпиляции // Межрегиональная конференция «Информационная безопасность регионов России». 1999. - Р. 65-67.

8. Декомпилятор бумеранг / / Boom,erang Decompiler SDK,http://boomerang.sourceforge.net/.

9. Декомпилятор dcc // http://www.itee.uq.edu.au/ cristina/dcc.html.— 1994.

10. Декомпилятор hex-rays // Hex-Rays Decompiler SDK, http://www.hex-rays.com/.

11. Декомпилятор rec — reverce ingeneering compiler / /http://www.backerstreet.com/rec/rec.htm.

12. Деревенец E. О., Долгова К. H. Восстановление управляющих конструкций фзыка высокого уровня из исходной программы на языке ассемблера // Сборник статей молодых ученых факультета ВМиК МГУ. — 2009. — по. 6. — Pp. 69-80.

13. Деревенец Е. О., Долгова К. П. Структурный анализ в задаче декомпиляции // Прикладная информатика. — 2009. — по. 4. — Pp. 63-80.

14. Долгова К. Н., Антонов В. Ю. Введение в задачу декомпиляции // Сборник статей молодых ученых факультета ВМиК МГУ. — 2008. — по. 5. — Pp. 5-15.

15. Долгова К. Н., Чернов А. В. Методы и алгоритмы восстановления программ на языке ассемблера в программы на языке высокого уровня // Методы и технические средства обеспечения безопасности информации. — 2008. — Pp. 101-102.

16. Долгова К. П., Чернов А. В. О некоторых задачах обратной инженерии // Труды института систелтого программирования. — 2008. — по. 15. — Pp. 119-134.

17. Долгова К. Н., Чернов А. В. Автоматическое восстановление типов в задаче декомпиляции // Программирование. — 2009. — по. 2. — Pp. 63-80.

18. Долгова К. П., Чернов А. В., Деревенец Е. О. Методы и алгоритмы восстановления программ на языке ассемблера в программы на языке высокого уровня // Проблемы информационной безопасности. Компьютерные системы. — 2008. — по. 3. — Pp. 4862.

19. Зубков С. Assembler для DOS, Windows и UNIX для программистов. — Питер, 2005.

20. Инструментальное средство grammatech codesurfer // http://www.grammatech.com/products/codesurfer/.

21. Интерактивный дизассемблер ida pro // http://www.idapro.ru/.

22. Иткин В., Звенигородский 3. On equivalence of program schemata // Journal of Computer and System Sciences. — 1971. — № 5.

23. Касперски К. Исскуство дизассемблирования. — БХВ-Петербург, 2008.

24. Колмогоров А. Н., Драгалин А. Г. Введение в математическую логику.— БХВ-Петербург, 2008.

25. Кормен Т., Ле-йзерсон Ч., Риверст Р. Алгоритмы. Построение и анализ. — Вильяме, 2007.

26. Пакет gnn binntils // http://www.gnu.org/software/binutils/.

27. Пильш,иков В. Н. Assembler. Программирование на языке ассемблера IBM PC. — Диалог-МИФИ, 2005.

28. Симулятор amd simnow // http://developer.amd.com/cpu/simnow/Pages/default.aspx.

29. Современные декомпиляторы // http://www.program-transformation. org/Transform/Machine CodeDecompilers.

30. Современные дизассемблеры // http://www.program-transformation. org/Transform/DisAssembly.

31. Стандарт си 11 ISO/IEC 9899, The С Programming Language. — 1999.

32. Фаулер М. Рефакторинг. Улучшение существующего кода. — 2008.

33. ФонНейман Д. First Draft of a Report on the ED VAC. — 1945.

34. Формат elf // http://www.skyfree.org/linux/references/ELFFormat.pdf.

35. Aho A., Sethi R., Ullman J. Compilers: Principles, Techniques, and Tools.— Morgan Kaufmann Publishers, 1986.

36. Alpern В., Wegman M. N., Zadeck F. R. Detecting equality of variables in programs // Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages. — 1988. — Pp. 1-11.

37. Balakrishnan G., Ganai M. Ped: Proof-guided error diagnosis by triangulation of program error causes // Proc. of Software Engineering and Formal Methods (SEFM). 2008.— November.

38. Balakrishnan G., Reps T. Analyzing memory accesses in x86 execu tables j j Compiler Construction. — 2004. — February. — Vol. 2985. — Pp. 5-23.

39. Balakrishnan G., Reps T. Divine: Discovering variables in executables // Verification, Model Checking, and Abstract Interpretation. — 2007. — November. — Vol. 4349. — Pp. 128.

40. Balakrishnan G., Reps T. Improved memory-accesses analysis for x86 executables // Compiler Construction. — 2008. — April. — Vol. 4959. — Pp. 16-35.

41. Burroes M., Fruend S., Wiener J. Run-time type checking for binary programs // Proceedings of CC. — 2003. — April. — Pp. 90-105.

42. Cavazos J., Fursin G., Agakov F. Rapidly selecting good compiler optimizations using performance counters // Proceeding of the international symposium on the Code Generation and Optimization. — 2007.

43. Cifuentes C. Reverse compilation techniques // http://www.itee.uq.edu.au/ cristina/d-cc.html# thesis. — 1994.

44. Cifuentes C., Emmerik M. Recovery of jump table case statements from binary code // Proceedings of the 7th International Workshop on Program Comprehension.— 1999.— Pp. 192-203.

45. Cifuentes C., Fraboulet A. Interprocedural static data flow recovery of high-level language code from assembly // Technical Report. — 1997. — no. 421.

46. Cifuentes С., Simon D., Fraboulet A. Assembly to high-level language translation // Int. Conf. on Softw. Maint. 1998. — November. — Vol. 20, no. 16. — Pp. 223-237.

47. CodeSonar. Codesonar, http://www.grammatech.com/products/codesonar/.

48. Curry H., Feys R., Craig W. Combinatory logic // Journal of Combinatory Logic. — 1958.

49. Davis M. Computability and unsolvability // chapter 5. — 1958.— Pp. 69-70.

50. Dolgova К., Chernov A. Type reconstruction in disassembled с programs // Working conference on reverse engineering. — 2008. — Pp. 202-206.

51. Dynamic inference of abstract types / P. Cuo, J. Perkins, S. McCamant, M. Ernst // Proceedings of ISSTA. — 2006. — July. Pp. 749-754.

52. Eagle C. The IDA Pro Book: The Unofficial Guide to the World's Most Popular Disassembler. — 2008.

53. Efficiently computing static single assignment form and the control dependence graph / R. Cytron, J. Ferrante, B. Rosen et al. // ACM Transactions on Programming Languages and Systems. — 1991. — October. — Pp. 450 490.

54. Eilam E. Reversing: Secrets of Reverse Engineering. — 2005.

55. Ellis M., Slroustrup B. The annotated С++ reference manual // Reading, MA: Addison-Wesley. — 1990.

56. Experience in the design, implementation and use of a retargetable static binary translation framework / C. Cifuentes, M. Emmerik, B. Lewis, N. Ramsey // Technical Report. — 2002. —January.-Vol. 105.

57. Fog A. Calling conventions for different С++ compilers and operating systems // http://www.agner.org/optimize/calling conventions.pdf. — 2009.

58. Gaines R. The translation of machine language programs // Communications of the ACM. — 1965. — Vol. 8(12). Pp. 737-741.

59. Goldschlanger L., Lister A. Computer science: A modern introduction. — 1982.

60. Halstead M. H. Elements of software science. — Elsevier North-Holland, 1977.

61. Hind M., A P. Which pointer analysis should i use? // Proceedings of the ACM SIGSOFT International Symposium on Software Testing and Analysis. — 2000. — August. — Pp. 113 123.

62. Horspool R., Marovac N. An approach to the problem of detranslation of computer programs // The computer journal. — 1979. — Vol. 23(3). — Pp. 223-229.

63. Jager G., Kretz M., Studer T. Cut-free common knowledge // Journal of applied logic.— 2007. — Vol. 5. — Pp. 681-689.

64. Kim I., Segal Z. A formal method for providing temporal equivalence inbinary-to-binary translation of real-time applications // Real-Time Systems Symposium Proceedings.— 2000. —Pp. 185-195.

65. Meirelles P., Fabio K. Mangue: Metrics and tools for automatic quality evaluation of source code // VII Workshop de Teses e Dissertacoes em Qualidade de Software (WT-DQS).- 2009.

66. Microsoft portable executable and common object file format specification // http://www. microsoft, com/whdc/system/platform/firmware /PECOFF. mspx.69.70.71.72.73.74.75176.77.78.79.80. 81]

67. Milner R. A theory of polimorphism in programming // Journal of Computer and System Sciences. — 1978. — December. — Pp. 223-237.

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

69. My croft A. Type-based decompilation // European Symp. on Programming. Vol. 1576. Pp. 208 - 223.1999.

70. Nethercote N., Seward J. Valgrind: A framework for heavyweight dynamic binary instrumentation // Proceedings of PLDI. — 2007. — June.

71. Pierce В. C. Types and Programming Languages. — Cambridge, 2004.

72. Pettier F. A modern eye on ml type inference // INTRA. — 2005.

73. Rosen В. K., Wegman M. N., Zadeck F. R. Global value numbers and redundant computations // Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages. — 1988. — Pp. 12-27.

74. Sazeides Y., Smith J. The predictability of data value // Proc. of Micro-30.— 1997.— December. — Pp. 749-754.

75. Stout В., Coffin J. Stout on decompilation // http:/'/www.program-transformation. org/Transform/BobStoutOnDecompilationOn. — 1997.

76. Troshina K., Chernov A. High-level composite type reconstruction during decompilation form assembly programs // Perspectives of system informatics. — 2009. — Pp. 292-299.

77. Troshina K., Chernov A., Derevenets Y. С decompilashion: is it possible? // International workshop on program understanding.— 2009.— Pp. 18-27.

78. Troshina K., Chernov A., Fokin A. Profile-based type reconstruction for decompilation // International conference on program comprehension. — 2009. — Pp. 263-267.

79. Valgrind // Документация системы Valgrind: http://valgrind.org/docs.

80. Zakharov V. Two-tape machinery for the equivalence checking of sequential programs // International workshop on program understanding. — 2009. — Pp. 28-40.