Содержание к диссертации
Введение
1 Декомпиляция как задача обратной инженерии 13
1.1 Задача декомпиляции как составляющая задачи обратной инженерии . 13
1.1.1 Обзор задачи дизассемблирования 17
1.1.2 Декомпозиция задачи декомпиляции на подзадачи 19
1.1.3 Универсальность в задаче декомпиляции 20
1.1.4 Корректность декомпиляции 21
1.2 Декомпиляция Си программ 22
1.2.1 Строго удовлетворяющие стандарту Си программы 23
1.2.2 Качество декомпиляции 26
1.2.3 Постановка задачи 29
2 Методы и инструментальные средства декомпиляции программ 31
2.1 Восстановление функционального интерфейса программы 31
2.1.1 Обнаружение функции main 31
2.1.2 Восстановление библиотечных функций и системных вызовов . 33
2.1.3 Восстановление функций 34
2.1.4 Выявление параметров и возвращаемых значений 36
2.2 Восстановление управляющих конструкций 38
2.3 Восстановление типов данных 41
2.3.1 Методы математической логики в задаче восстановления типов . 42
2.3.2 Интервальный анализ в задаче восстановления типов данных . 43
2.3.3 Восстановление типов на основе шаблонов 44
2.3.4 Смежные подходы решения задачи восстановления базовых типов данных 46
2.4 Использование информации времени выполнения для повышения качества декомпиляции 47
2.4.1 Обзор работ, рассматривающих использование информации времени выполнения программы 48
2.4.2 Система Valgrind 49
2.5 Инструментальные средства 50
2.5.1 Boomerang 50
2.5.2 DCC 51
2.5.3 REC 51
2.5.4 HexRays 51
2.5.5 Исследование возможностей декомпиляторов 52
3 Восстановление типов данных 56
3.1 Основные идеи алгоритма 56
3.2 Объекты 57
3.3 Восстановление базовых типов данных 59
3.3.1 Представление типов данных 59
3.3.2 Система уравнений модельных типов 62
3.3.3 Ограничения 63
3.3.4 Объединение типовых переменных 64
3.3.5 Решение системы уравнений зависимости типов 66
3.3.6 Алгоритм восстановления базовых типов данных 69
3.4 Восстановление производных типов данных 70
3.4.1 Общее описание работы алгоритма 72
3.4.2 Формальное описание алгоритма 75
4 Использование информации о выполнении программы для повышения качества декомпиляции 84
4.1 Профилирование значений ячеек памяти 84
4.2 Распознование инструкций memset и memcpy 90
4.3 Профилирование кучи 92
4.4 Экспериментальные результаты 99
5 Декомпилятор TyDec 102
5.1 Инструментальная среда декомпиляции программ TyDec 103
5.1.1 Архитектура 103
5.2 Компоненты системы 104
5.2.1 Реализация восстановления функционального интерфейса 104
5.2.2 Восстановление структурных конструкций 106
5.2.3 Восстановление типов данных 110
5.3 Утилиты профилирования 115
5.3.1 Утилита TDTrace 115
5.3.2 Утилита TDHeap 120
5.3.3 Накладные расходы профилирования 122
5.4 Сравнительная оценка качества восстановления программ декомпилятором TyDec 123
Заключение 126
- Декомпиляция Си программ
- Восстановление управляющих конструкций
- Восстановление базовых типов данных
- Распознование инструкций memset и memcpy
Введение к работе
Актуальность.
Создание и разработка сложных программных систем различного назначения часто ведется посредством интеграции отдельных компонент, выполненных как собственными, так и сторонними разработчиками. Это позволяет значительно сократить стоимость и время разработки программного обеспечения. Внешние модули могут поставляться без исходного кода. Наличие таких модулей в системе уменьшает уровень надежности разрабатываемого приложения с точки зрения информационной безопасности. В частности, сторонние модули могут содержать закладки или уязвимости, способствующие утечке информации и успешным атакам на информационную систему. Кроме того, программные модули от внешних разработчиков могут содержать ошибки, исправление которых оказывается затруднительным. Следовательно, весь сторонний код должен подвергаться аудиту с точки зрения безопасности его внедрения и использования.
Программные компоненты, представленные в виде исполняемых файлов или на языке ассемблера, сложны для анализа специалистами в области информационной безопасности. Для более качественного и продуктивного анализа их лучше предоставлять специалистам на более высоком уровне представления, например, на языке высокого уровня, в частности на языке программирования Си. Ассемблерный код и, тем более, исполняемые файлы не позволяют с приемлемыми трудозатратами оценить взаимосвязь элементов программы, а также идентифицировать в программе различные алгоритмические конструкции, в то время как наличие восстановленной программы на языке высокого уровня дает возможность преодолеть указанные выше трудности. В качестве одного из средств для повышения уровня абстракции представления программы может использоваться декомпиляция.
Декомпиляция - это процесс автоматического восстановления программы на языке высокого уровня из программы на языке низкого уровня. Под декомпилятором мы будем понимать инструментальное средство, получающее на вход программу на языке ассемблера или другое аналогичное низкоуровневое представление и выдающее на выход эквивалентную ей программу на некотором языке высокого уровня.
Также декомпиляция может использоваться для обеспечения совместимости программных приложений, а именно для анализа протоколов взаимодействия в случае, когда они описаны недостаточно полно или не описаны вообще. Декомпиляция позволяет упростить восстановление состояний и структур данных протокола взаимодействия.
В настоящее время из широко используемых компилируемых языков программирования высокого уровня распространены языки Си и Си++, поскольку именно они наиболее часто используются при разработке прикладного и системного программного обеспечения для платформ Windows, MacOS и Unix. Поэтому декомпиляторы с этих языков имеют наибольшую практическую
значимость. Язык Си++ можно считать расширением языка Си, добавляющим в него концепции более высокого уровня относительно языка Си. Поскольку при обратной инженерии в целом и при декомпиляции в частности уровень абстракции представления программы повышается, можно считать, что программы на языке Си являются промежуточным уровнем при переходе от программы на языке ассемблера к программе на языке Си++. Дальше повысить уровень абстракции представления программы можно посредством широко известных методов рефакторинга, позволяющих, например, выделять объектные иерархии из процедурного кода.
Из-за ряда трудностей задача декомпиляции не решена в полной мере до сих пор, хотя была поставлена еще в 60-е годы прошлого века. С теоретической точки зрения задачи построения полностью автоматического универсального дизассемблера и декомпилятора относят к алгоритмически неразрешимым. Неразрешимость задач следует из того, что задача автоматического разделения кода и данных является алгоритмически неразрешимой.
Помимо функциональной эквивалентности исходной программе декомпилированная программа должна быть восстановлена наиболее полно. Полнота восстановления определяется степенью использования высокоуровневых конструкций целевого языка, то есть программы, полученные на выходе декомпилятора, должны как можно больше и полнее использовать высокоуровневые конструкции языка.
Для оценки полноты восстановления в работе вводится новое требование к результату декомпиляции программ - качество, а также вводится мера качества, которая позволяет количественно сравнивать программы, восстановленные различными инструментальными средствами декомпиляции.
Представляемая работа посвящена разработке алгоритмов и методов автоматической декомпиляции программ на языке ассемблера в программы на языке Си.
Низкоуровневые конструкции языка Си, такие как явные приведения типов, неестественные циклы, организованные с использования операторов goto или с использованием операторов continue или break, замена оператора множественного выбора switch операторами if и другие, а также ассемблерные вставки кода, который не удалось восстановить, крайне нежелательны в восстановленной программе. Автоматически восстановленная программа декомпилирована качественно, если она содержит минимальное количество низкоуровневых конструкций и наиболее полно использует высокоуровневые конструкции языка Си. Например, вместо оператора цикла while, если возможно, используется оператор цикла for, вместо операций с адресной арифметикой используются операции доступа к элементам массива.
Отображение конструкций языка высокого уровня в конструкции языка низкого уровня - это отображение «многие ко многим». Если зафиксировать компилятор и значений опций, управляющих генерацией кода, то это отображение становится «многие к одному», что несколько упрощает задачу восстановления программ, даже несмотря на то, что распознавание компилятора,
которым была скомпилирована высокоуровневая программа - отдельная нетривиальная задача.
Декомпилятор, который восстанавливает низкоуровневую программу, изначально написанную на неизвестном заранее языке программирования, в качественную программу на фиксированном языке высокого уровня, назовем универсальным.
Разные языки высокого уровня одного типа (например, процедурные, компилируемые) предоставляют примерно одинаковый набор возможностей, однако, некоторые возможности одного языка могут не иметь прямых аналогов в другом языке. Например, указатели языка Си не имеют прямого аналога в языке Фортран. В таких случаях трансляторы программ из одного языка высокого уровня в другой на выходе вынуждены генерировать код, моделирующий особенности исходного языка средствами целевого языка. Сгенерированная на выходе программа содержит артефакты трансляции, то есть фрагменты кода, появившиеся вследствие различия понятийного аппарата исходного и целевого языков. Поэтому, хотя существующие в настоящее время трансляторы между языками высокого уровня и дают на выходе синтаксически и семантически корректный код, он зачастую труден для анализа и модификации человеком. Представляется, что задача построения универсального декомпилятора не проще задачи построения универсального транслятора в фиксированный язык высокого уровня, поэтому в настоящее время нет оснований рассчитывать на возможность успешного построения универсального декомпилятора.
В силу вышесказанного является актуальной разработка методов восстановления программ в предположении, что исходная программа была реализована на конкретном языке программирования. В представляемой работе в качестве такого языка используется язык Си. Декомпилятор определяется как транслятор с языка низкого уровня в язык высокого уровня, который минимизирует количество артефактов трансляции в результирующей программе и выполняет восстановление высокоуровневых конструкций целевого языка максимально полно в предположении, что исходная программа была написана на этом языке высокого уровня.
Целью диссертационной работы является разработка алгоритмов и методов декомпиляции программ, применимых к широкому спектру целевых низкоуровневых программ и позволяющих автоматически полно восстановить все высокоуровневые конструкции целевого языка высокого уровня. Помимо этого целью работы является разработка прототипа экспериментальной диалоговой инструментальной среды для декомпиляции программ в язык Си на основе предложенных методов и алгоритмов декомпиляции.
Научная новизна. В представляемой работе предложено новое требование к методам декомпиляции - качество восстановления программ, которое определяется полнотой восстановления высокоуровневых конструкций целевого
языка. Также предложен метод, позволяющий выполнять количественное сравнение качества восстановления программ различными декомпиляторами.
В работе представлен новый подход к восстановлению типов данных на основе методов статического и динамического анализа входной программы, позволяющий существенно повысить качество восстановления программ. Кроме того, для обеспечения восстановления всех высокоуровневых конструкций целевого языка существующие методы структурного анализа программ расширены новыми методами, позволяющими восстанавливать оператор множественного выбора switch и оператор цикла for.
Основные результаты диссертационной работы. В диссертации получены следующие результаты, характеризующиеся научной новизной.
Предложен новый подход к декомпиляции программ, позволяющий автоматически восстанавливать все высокоуровневые конструкции целевого языка. Предложен метод количественной оценки полноты восстановления.
Предложена модель представления типов данных, позволяющая восстанавливать как базовые, так и производные типы данных, и разработаны алгоритмы восстановления типов данных посредством статического и динамического анализа программы.
Для обеспечения полноты восстановления программ расширены существующие методы восстановления структурных конструкций.
На основе предложенных методов разработан прототип инструментальной среды декомпиляции TyDec, позволяющий целостно восстанавливать низкоуровневые программы в программы на языке Си, максимально полно использующие высокоуровневые конструкции языка. Проведена экспериментальная проверка прототипной версии инструментальной среды декомпиляции TyDec на наборе программ с открытыми исходными кодами, которая показала полноту восстановления высокоуровневых конструкций целевого языка разработанными алгоритмами и методами декомпиляции.
Все разработанные в рамках работы методы реализованы в инструментальной среде TyDec. Инструментальная среда для декомпиляции программ TyDec позволяет автоматически корректно и качественно восстанавливать широкий класс программ в низкоуровневом представлении.
Инструментальная среда TyDec, являясь диалоговой, позволяет аналитику управлять процессом декомпиляции вручную в случаях, когда не удается автоматически однозначно восстановить высокоуровневые конструкции. Также, являясь расширяемой, инструментальная среда TyDec позволяет добавлять новые методы и эвристики, позволяющие разрешать конфликты восстановления, и повышающие качество восстановленной программы. Прототипная версия среды TyDec является базовым средством для проведения исследований.
Практическая значимость. Разработанные алгоритмы восстановления типов данных реализованы в инструментальной среде декомпиляции TyDec, что позволило восстанавливать все высокоуровневые конструкции языка Си, включая как базовые, так и производные типы данных, оператор множественного выбора switch, оператор цикла for. Предложенные уточнения правил отображения шаблонов графа потока управления и деревьев доминирования программ на языке низкого уровня в конструкции языка Си позволили в рамках системы TyDec реализовать инструмент, который позволяет восстанавливать структурные конструкции языка Си, даже если в программе на низком уровне имелись неструктурные операторы выхода из середины цикла (оператор break) и перехода на следующую итерацию цикла (оператор continue). Предложены методы восстановления типов данных на основе статического и динамического анализа, позволяющие существенно повысить качество декомпиляции программ. Прототип инструментальной среды декомпиляции TyDec, разработанный в рамках представленной работы, позволяет поддерживать унаследованное ПО с утраченными исходными кодами, позволяет восстанавливать структуры данных обмена и протоколы взаимодействия между модулями ПО, а также существенно облегчает задачу исследования ПО с точки зрения информационной безопасности его использования.
Апробация работы. Основные результаты диссертационной работы опубликованы в статьях [1] - [12], в том числе две [1] и [2] - в изданиях рекомендованных ВАК для публикации результатов кандидатских и докторских диссертаций, и представлены в докладах на следующих конференциях и семинарах.
Общероссийская научно-техническая конференция «Методы и технические средства обеспечения безопасности информации», Санкт-Петербург, Россия, 7-11 июля 2008 г.
Международная конференция «15th Working Conference on Reverse Engineering» (WCRE 2008). Антверпен, Бельгия, 15-18 октября 2008 г.
Конференция «РусКрипто», г. Звенигород, Россия, 3-5 апреля 2009 г.
Международная конференция «17th International Conference on Program Comprehension» (ICPC 2009). Ванкувер, Канада, 17-19 мая 2009 г.
Международная конференция «7th International Andrei Ershov Memorial Conference Perspectives of System Informatics» (PSI 2009). Новосибирск, Россия. 15-19 июня 2009 г.
Международный семинар «International Workshop on Program Understanding» (PU 2009). Алтай, Россия. 19-23 июня 2009 г.
Структура и объем диссертации. Диссертация состоит из введения, пяти глав, заключения, списка литературы и приложения. Объем диссертации составляет 134 страницы. Диссертация содержит 17 таблиц и 66 иллюстраций. Список литературы состоит из 81 наименования.
Декомпиляция Си программ
Рассмотрим класс программ на языке программирования Си, которые строго удовлетворяют стандарту [32], далее такие программы будут называться СУС Си-программами. Хотя язык Си является языком высокого уровня, он предоставляет низкоуровневые средства, такие, как объединения (union), битовые поля, операции явного приведения типов. Они позволяют обходить контроль типов и поддерживаемые языком преобразования значений. Работа программы, использующей низкоуровневые возможности, будет зависеть от платформы, на которой она выполняется. Стандарт языка Си [32] определяет следующие понятия: Unspecified behavior (неспецифицированное поведение). Это ситуация, в которой стандарт предлагает два или более варианта поведения и не накладывает никаких ограничений на выбор варианта в каждой конкретной ситуации. Например, порядок вычисления аргументов функции даже в одной программе в разных точках вызова может отличаться. Implementation-defined behavior (реализационно-зависимое поведение). Это ситуация, в которой стандарт предлагает два пли более варианта поведения, но требует от каждой реализации строгого следования какому-либо одному варианту поведения. Undefined behavior (неопределенное поведение). Это ситуация использования ошибочной или непереносимой конструкции, в которой стандарт не накладывает никаких ограничений на поведение компилятора или программы. Например, ситуация неопределенного поведения возникает при попытке обращения к массиву за его пределами. Unspecified value (неспецифицированное значение). Некоторое допустимое значение соответствующего типа, на выбор конкретного значения в каждой ситуации стандарт не накладывает никаких ограничений. Например, таковы начальные значения локальных неинициализированных переменных. Implementation-defined value (реализационно-зависимое значение). Некоторое допустимое значение, причем каждая конкретная реализация должна строго следовать какому-либо одному варианту выбора значения. Indeterminate value (недетерминированное значение). Либо некоторое допустимое значение, либо аппаратная ошибка. Таким образом, стандарт языка Си четко оговаривает языковые конструкции и ситуации при работе программы, в которых проявляется низкоуровневое (то есть зависящее от данной реализации или платформы) поведение программы. Так, хотя стандарт фиксирует двоичное представление целых значений, размещение значений в памяти и способ представления отрицательных чисел являются реализационно-зависимыми. Точно так же способ представления указателей и результат преобразования между указательными и целыми значениями являются реализационно-зависимыми. Использование особенностей представления значений, например, с помощью явных приведений указательных типов с последующим разыменованием, либо с помощью объединений, делают программы зависящими от реализации. Программа, строго удовлетворяющая стандарту (strictly conforming program), не использует в работе неспецифицированпые, реализационно-зависимые или неопределенные особенности языка Си. Стандарт гарантирует идентичную работу такой программы в любом окружении, поддерживающем стандарт Си. С другой стороны, реализационно-зависимое поведение является фиксированным для каждой реализации, а де-факто во многом даже для каждой конкретной платформы. Все компиляторы на одной платформе, как правило, выбирают один и тот же вариант реализационно-зависимого поведения для обеспечения бинарной совместимости. Поэтому можно считать, что реализациопно-зависимые аспекты реализации являются параметрами декомпилятора. Изменяя реализационно-зависимые параметры, можно в определенных пределах адаптировать декомпилятор к разным реализациям. Поэтому расширим множество поддерживаемых программ такими, которые опираются на реализационно-зависимое поведение программы. Такое расширение, однако, не добавляет в поддерживаемое подмножество языка объединения и явные приведения уксізательньгх типов, сопровождающиеся разыменованием. Рассмотрим компиляцию как отображение программы на языке высокого уровня в программу на языке ассемблера. Для любой программы на языке высокого уровня существует ее образ во множестве программ на ассемблере, и для любой программы на ассемблере существует множество ее прообразов во множестве программ на языке высокого уровня. Компиляция — это отображение «многие ко многим», для фиксированного компилятора с фиксированным набором опций это отображение становится «многие к одному». Поэтому несколько различных программ, например, программы на языке Си, (в частности, даже использующих различные типы данных) могут отображаться в идентичный ассемблерный код. Декомпиляция, как обратное отображение, может давать в результате программу, существенно отличающуюся от исходной. На рис. 7 представлен шаблон Си-программы. Для любого значения параметра Туре Є {unsigned int, int, unsigned long, long} на архитектуре IA-32, где типы данных unsigned int, int, unsigned long и long занимают в памяти 4-байта, будет сгенерирован идентичный ассемблерный код, представленный ниже на этом же рис. 7. На рис.8 представлена схема отображения различных программ в ассемблерные программы. Утверждение. Пересечение образов СУС Си-программ и не СУС Си-программ, СУС Си-программ и не Си-программ непустые. Доказательство. Приведем соответствующие примеры. На рис. 9 представлены функции func двух программ, одна из который СУС Си-программа, другая не СУС Си-программа. Эти функции имееют один и тот же ассемблерный образ, представленный также на рис. 9. Ассемблерный образ получен посредством компилирования обеих программ компилятором GNU GCC версии 4.3.0 для операционной системы Win32.
Восстановление управляющих конструкций
Восстановление управляющих конструкций высокого уровня по представлению программы низкого уровня — одна из стандартных задач теории трансляции. Эта задача возникает в компиляторах языков высокого уровня, которые позволяют организовывать циклы и ветвления в программе с использованием условных и безусловных переходов. Поэтому задачи такого анализа потока управления программы рассматриваются в учебниках и монографиях, посвященных разработке трансляторов, например [69],[36]. Такие методы анализа потока управления также могут быть использованы и при решении задачи восстановления управляющих конструкций в процессе декомпиляции.
В монографии [69] рассматриваются два метода анализа потока управления: первый метод основан на построении доминирующих множеств вершин графа потока управления, а второй метод — это интервальный анализ, обобщением которого является структурный анализ.
Анализ потока управления, основанный на построении доминирующих множеств вершин графа потока управления, позволяет работать только с циклами и без существенных модификаций неприменим для выявления условных операторов. В этом методе сначала вычисляется доминирующее множество вершин, для чего используется либо алгоритм последовательной итерации, либо алгоритм Ленгауэра-Тарьяна. Алгоритм последовательной итерации завершается при достижении доминирующими множествами неподвижной точки. Алгоритм Ленгауэра-Тарьяна работает быстрее, его временная сложность 0(п а(п)).
После того как доминирующее множество найдено, выполняется разметка дуг графа потока управлення. Дуги графа потока управления классифицируются на прямые, обратные и косые. Прямая дуга — это дуга из доминирующей вершины в доминируемую, обратная дуга — это дуга из доминируемой вершины в доминирующую, все прочие дуги помечаются как косые. Размеченный граф потока управления позволяет выделить управляющие конструкции, например, обратной дуге та — п соответствует цикл, состоящий из вершины п и всех вершин, из которых доступна тп по пути, не содержащему п. В самом общем случае циклу в исходной программе соответствует компонента сильной связности графа потока управления. Недостатком этого метода является небольшой набор обнаруживаемых структурных конструкций (только циклы) и относительная сложность реализации.
Интервальный анализ основан на последовательном выделении регионов различных типов и объединением их в одну новую вершину графа потока управления. Регион — это набор базовых блоков, имеющий не более одной входящей дуги. Простейшим случаем региона является базовый блок. На первой итерации работы алгоритма все базовые блоки помечаются как самостоятельные регионы. Для выделения регионов строится дерево обхода графа потока управления в глубину. Вершины исследуются в обратном порядке обхода. Если два региона соединены только одной дугой, то они объединяются. Если вершина является входной точкой циклической или ациклической управляющей конструкции, то регион, соответствующий этой конструкции, выделяется в новую вершину, и соответствующим образом корректируются дуги. Тип конструкции определяется последовательным сравнением подграфов, включающих рассматриваемую вершину, с соответствующими шаблонами. Алгоритм заканчивает работу, когда преобразованный граф не содержит дуг и состоит только из одного региона.
В самой простой версии интервального анализа выполняется выделение только циклов, а условные переходы не анализируются. Обобщением интервального анализа является структурный анализ, где помимо циклов выделяются еще и условные операторы, а именно, выделяются следующие типы регионов: block, ifhen, ifhen-else, self loop, while loop, natural loop, improper interval (неприводимый подграф, строго говоря не являющийся регионом в нашем определении).
В работах [7] и [8] предложен метод восстановления управляющих конструкций на основе анализа идиом. В анализируемой программе выделяются идиомы посредством ее трансформации и сравнении выделенных идиом с библиотекой идиом. Для каждой идиомы из библиотеки идиом имеется высокоуровневая конструкция, в которую восстанавливается последовательность команд, соответствующая идиоме.
Диссертационная работа К. цифуентес (С. Cifuentes) [44] является одной из первых работ, посвященных разработке декомпилятора в язык Си. Метод восстановления структурных конструкций в рассматриваемой работе реализован автором в декомпиляторе dec. Структурный анализ основан на выделении в исходном графе потока управления управляющих конструкций посредством некоторого преобразования его в семантически эквивалентный граф.
Так как при декомпиляции в общем случае заранее неизвестно, на каком языке бьгла написана исходная программа, автор выделяет множество управляющих конструкций, общих для большинства языков высокого уровня: composition, conditional, preested loop, single branching conditional, n-way conditional, postested loop, endless loop.. В тех случаях, когда исходный граф не может быть структурирован с использованием предопределённого множества структурных конструкций, используется оператор goto.
Порядок выделения управляющих конструкций влияет на конечный вид графа. В предлагаемом автором методе используется следующий порядок выделения управляющих конструкций: n-way conditionals, loops, 2-way conditionals.
Для поиска циклов каждая вершина х проверяется на наличие входящего в неё обратного ребра из какой-либо вершины у, входящей в тот же регион. Цикл состоит из всех вершин, встречающихся в процессе обхода графа в глубину позже заголовка х и раньше замыкающей вершины, у, принадлежащих одному и тому же интервалу и доминируемых заголовком цикла. Циклы, у которых заголовок или замыкающая-вершина принадлежат другому циклу, считаются неприводимыми, и при их восстановлении используются операторы goto. После выявления циклов определяется их тип. Цикл с предусловием имеет заголовок с двумя исходящими рёбрами и замыкающую вершину с: одним обратным ребром в заголовок. Цикл с постусловием, наоборот, имеет замыкающую вершину с двумя рёбрами: в заголовок и вовне цикла. В остальных случаях цикл считается бесконечным. Условные конструкции и конструкции сокращённого вычисления выражений определяются путём сравнения подграфов с образцами.
На практике встречаются неприводимые графы, содержащие несколько точек входа. Так как алгоритм выделения структурных конструкций,не должен изменять семантику графа потока управления, дублирование вершин не применяется, и граф оставляется в исходном виде, а при восстановлении программы используются goto.
Помимо операторов цикла и ветвления управляющие конструкции языка Си включают оператор множественного выбора switch. Восстановлению оператора множественного выбора как в теоретическом аспекте, так и на практике уделено меньше внимания, нежели всем остальным управляющим операторам.
Восстановление базовых типов данных
В этом разделе рассматривается модель восстановления базовых типов языка Си и обобщенных указателей (void ) [51], а также алгоритм восстановления базовых типов данных и обобщенных указателей, построенный на этой модели. Восстановлению производных типов данных, таких как массивы, структуры и массивы структур, посвящен следующий раздел этой главы.
Пусть Q0 = { unsigned char, char, unsigned short, short, unsigned int, int, unsigned long, long, unsigned long long, long long, float, double, long double, void } — это рассматриваемое множество базовых типов языка Си и псевдотип void, который используется как специальный тип данных. Пусть Qi = {void } — это множество, состоящее только из одного обобщенного указателя. Элемент множества восстанавливаемых типов данных обозначим Т, Элемент множества идеальных типов данных обозначим 0. В представляемой модели множества восстанаолиоаеліих типов и идеальных типов совпадают и представлены множеством Г2 = Г2о U Q\.
Каждый тип Т из множества Q отображается в модельный тип т. Модельный тип т задается тройкой атрибутов: ядро (core Є {integer,pointer, float}), размер (size {1,2,4,8}) и знак (sign Є {signed, unsigned}). Псевдотип void представляется в виде тройки void = (0,0,0). Каждый Си-тип из множества Q можно отобразить в тройку (Tcore)Ts«e)Ts,sn)j где тсоге Є core, rstze е size, rsign Є sign. Множество модельных типов — это множество всех троек вида (rC0 ie)T«2e)T«sn)j полученное в результате отображения всех типов Т Є Г2. Каждая тройка из множества модельных типов получена отображением базового типа языка Си или обобщенного указателя, следовательно, каждый модельный тип можно отобразить обратно в один или несколько типов G Є Г2.
Например, тип 9 = unsigned short отображается в модельный тип (integer,2,unsigned). И наоборот, модельный тип можно однозначно с точки зрения корректной декомииляции восстановить в тип языка Си. Например, модельный тип (integer, 1, signed) восстанавливается в тип языка Си Т = unsigned char.
Каждый объект obj є OBJ в результате восстановления должен получить свой восстановленный тип ГеП, тогда можно сказать, что объект имеет восстанавливаемый тип, который надо найти в процессе работы алгоритма восстановления базовых типов данных, обозначается это obj : Т. Восстанавливаемый тип Т представляется обобщенным модельным типом. Обобщенный модельный тип — это тройка множеств ({}соге, {}sl2e, {}slsn), каждое множество которой соотвествует атрибуту модельного типа (тсогс,rstze,т"9П). Восстанавливаемый тип Т ищется через последовательное итеративное приближение атрибутов обобщенного модельного типа (TcorE)TSI2e).7-S!sn),
Каждый атрибут обобщенного модельного типа-объекта восстанавливается независимо от других, при этом значение совокупности атрибутов может соответствовать нескольким типам, а может не соответствовать ни одному типу. Например, обобщенный модельный тип ({mt, pointer}, {4}, {unsigned, signed}) восстанавливается во множество модельных типов
В этом случае, чтобы точнее установить тип объекта, требуется дополнительная информация. С другой стороны, если в процессе работы алгоритма какой-либо атрибут типа объекта стал пустым множеством, то в разных точках программы работа с объектом ведется несовместимым по типу данных образом. Например, в одной точке программы объект разыменовывается; а в другой точке программы — умножается на некоторое значение. В частности, такие ситуации могут возникать, когда в исходной программе используются типы объединения (union) или явные приведения указательных типов, что выводит такие программы из класса СУС Си-программ. Подобные конфликтные ситуации требуют привлечения аналитика для дополнительного анализа.
Итак, после того как обобщенный тип найден, по нему восстанавливаются соответствующие ему модельные типы по следующим правилам:
1. Каждое из множеств каждого атрибута содержит только одно значение, и эта тройка атрибутов является представлением модельного типа из множества всех модельных типов, тогда по обобщенному модельному типу строится только один модельный тип, и этот модельный тип отображается обратно в тип языка Си.
2. Если r int, тогда и атрибут size и атрибут sign являются значимыми, для r pointer ни атрибут size, ни атрибут sign значимыми не являются. Если какое-то из множеств атрибутов, значимое для атрибута core содержит более одного значения, то в этом случае либо не хватает информации, либо не существенно с точки зрения корректности декомпиляции восстановление соответствующего параметра. Атрибуту size присваивается наибольшее значение из полученного множества, а атрибуту sign присваивается значение signed.
3. Атрибут core содержит более одного значения. Тогда восстанавливаются все модельные типы, которые можно построить по такому обобщенному типу. Все модельные тины отображаются в восстановленные Си-типы, в качестве результата выполнения объекту назначаеіся тип объединение (union), объединяющий все восстановленные типы.
4. Какое-то из множеств атрибутов является пустым множеством. В этом случае имеется конфликт использования переменной. В этом случае тин переменной восстанавливается как тип объединения (union).
5. Ситуация, когда каждое из множеств каждого атрибута содержит только одно значение, но эта тройка атрибутов не является представлением модельного типа из множества Г, например, тройка ({float}, {2}, {0}, исключается, так как может возникнуть только в результате некорректной реализации алгоритма.
Так как для каждого объекта obj Є OBJ существует идеальный тип Э Є П, а в результате работы алгоритма должен быть найден восстанавливаемый тип Т Є Г2, определяется, что восстановленный тип Т Є Г2 для объекта obj Є OBJ найден корректно, если идеальный тип 0 Є fi, представленный в виде модельного типа, покомпонентно является подможеством обобщенного модельного типа, по которому построен восстановленный Т. То есть, если Э = int = {integer,4,signed), а Т = int -Ф= ({integer}, {4}, {signed, unsigned}), то T найден корректно. Восстановленный тип найден точно, если имеется полное совпадение.
Во множестве О. содержатся все базовые типы языка Си. Однако некоторые базовые типы языка Си на некоторых платформах с точки зрения представления в виде тройки атрибутов могут неразличимы, например, типы, int и long имеют одинаковый образ в множестве модельных типов для платформы IA32 ({integer}, {4}, {signed}). При обратном отображении такого модельного типа в типы языка Си может быть выбран любой из типов int или long.
Как правило, различить в программе на ассемблере, с каким типом данных мы работаем — с вещественным или с целым — нетрудно, так как наборы инструкций для работы с вещественными и целыми типами различны. На архитектуре IA32 (и на многих других) для выполнения операций над вещественными числами используется другой набор регистров и другие инструкции, нежели для целочисленных операций. Однако в ряде случаев для работы с вещественными числами могут использоваться и регистры общего назначения, например, при копировании переменных, передаче параметров в функции, и т. п.
Распознование инструкций memset и memcpy
Стандарт языка Си допускает побайтовый доступ к объектам с помощью указателя типа char . Так, например, возможно скопировать значение из одной переменной в другую переменную того же типа. Как правило, для таких низкоуровневых операций с памятью, как копирование, обнуление или побайтовое сравнение используются функции стандартной библиотеки memepy и другие. При глубокой оптимизации программы компилятор заменяет вызовы таких функций па реализации, оптимизированные для каждой конкретной архитектуры. Инструкции, соответствующие таким функциям, должны быть идентифицированы в декомпилируемом коде и исключены из анализа при восстановлении типов, так как они не подчиняются правилам строгой типизации и правилам распространения информации о типах по программе.
Распознавание инструкций memset и тешсру можно проводить либо сигнатурным анализом, либо анализом поведения программы во время выполнения. Сигнатурный анализ требует постоянно обновляющуюся базу сигнатур для всех поддерживаемых компиляторов. Анализ поведения во время выполнения программы лишен этого недостатка.
Например, функция memset (р, 0, 2 sizeof( p)) может транслироваться в ассемблер в две инструкции, представленные на рис. 35
Для распознавания операций записи фиксированного значения в память во время выполнения программы предлагается следующий эвристический подход. Если во время выполнения программы были найдены выполняющиеся подряд инструкции присваивания вида movl х, addr_i, для которых: используется фиксированное значение х, адреса ячеек памяти addri расположены в возрастающем или в убывающем порядке, и разность \addri — addri-\\ равна размеру ячейки памяти.
Тогда такие инструкции помечаются как нарушающие строгую типизацию и исключаются из рассмотрения в алгоритме восстановления типов.
Если во время анализа выполнения программы были найдены чередующиеся инструкции считывания movl addrl_i, еах и присваивания movl еах, addr2_i для которых: адреса ячеек памяти addrli расположены в возрастающем или убывающем порядке и разность \addrli — addrlj_i равна размеру ячейки памяти, адреса ячеек памяти аййг2г расположены в порядке, соответствующем порядку ячеек памяти addrli, и разность \addr2i — addr2i-i\ равна размеру ячейки памяти.
Тогда этот набор инструкций помечается как нарушающий строгую типизацию и также исключается из рассмотрения в алгоритме восстановления типов.
Исключение из анализа входной программы инструкций, соответствующих функциям копирования и обнуления памяти, позволяет существенно повысить качество восстановления типов благодаря тому, что устраняются противоречия в использовании типов данных.
