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

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

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

Трошина Екатерина Николаевна

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

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

АВТОРЕФЕРАТ

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

Москва - 2009

003481783

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

Научный руководитель:

академик РАН, профессор Иванников Виктор Петрович

Официальные оппоненты: доктор физико-математических наук

профессор

Смелянский Руслан Леонидович

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

Ведущая организация:

Вычислительный центр имени А. А. Дородницина РАН

Защита диссертации состоится «20» ноября 2009 г. в 11:00 на заседании диссертационного совета Д 501.001.44 в Московском государственном университете имени М. В. Ломоносова по адресу: 119991, ГСП-1, Москва, Ленинские горы, МГУ, 2-й учебный корпус, факультет вычислительной математики и кибернетики, ауд. 685.

С диссертацией можно ознакомиться в библиотеке факультета вычислительной математики и кибернетики МГУ имени М. В. Ломоносова. С текстом автореферата можно ознакомиться на официальном сайте ВМК МГУ имени М. В. Ломоносова: http://cs.msu.su в разделе «Наука» - «Работа диссертационных советов» - «Д 501.001.44».

Автореферат разослан « 17 » октября 2009 г.

Ученый секретарь диссертационного совета

профессор Н.П. Трифонов

>бщая характеристика работы ктуальность.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Апробация работы. Основные результаты диссертационной работы публикованы в статьях [1] - [12], в том числе две [1] и [2] - в изданиях екомендованных ВАК для публикации результатов кандидатских и докторских иссертаций, и представлены в докладах на следующих конференциях и еминарах.

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

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

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

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

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

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

Структура и объем диссертации. Диссертация состоит из введения, пяти глав, заключения и списка литературы и приложения. Объем диссертации составляет 134 страницы. Диссертация содержит 17 таблиц и 66 иллюстраций. Список литературы состоит из 81 наименования.

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

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

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

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

Декомпиляция - это процесс автоматического восстановления программ] на языке высокого уровня из программы на языке низкого уровня. С практическо точки зрения задача декомпиляции чрезвычайно сложна в силу того, что пр компиляции утрачивается много информации о высокоуровневой программ! Часть информации, например, имена неэкспортируемых объектов, утрачиваете безвозвратно. Также утрачивается информация о высокоуровневых конструкция: используемых типах данных и др., однако эту информацию частично ил полностью можно восстановить. На практике задача восстановления программ: из низкоуровневого представления в программу на языке высокого уровн зачастую решается посредством привлечения специалиста. Такой подход восстановлению программ высоко трудозатратный и малоэффективный п времени.

В данной работе восстановление выполняется в язык программирования Ci Программы на языке ассемблера, корректно работающие со стеком и i: содержащие данных, интерпретируемых как код и наоборот, являются правильи построенными программами. Так как язык Си сочетает в себе высокоуровневые низкоуровневые возможности программирования, то можно утверждать, чт существует отображение, которое любую правильно построенную ассемблерну; программу непосредственно переводит в программу на языке Си. Однако такс отображение является трансляцией, но не декомпиляцией. Восстановленная таки образом программа будет содержать много низкоуровневых конструкций язьи Си, таких как операторы перехода goto, явного приведения типов (type) прерывания цикла break, прерывания витка цикла continue, ассемблернь

:тавки и другие. Такое восстановление является корректным, однако уровень эедставления про1раммы не повышается.

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

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

Мера качества декомпиляции рассчитывается следующим образом. Пусть входная программа на языке высокого уровня содержала К штрафных баллов, усть восстановленная программа содержит К' штрафных баллов. Качество установления оценивается на некотором тестовом наборе программ, который 5означим TS. Пусть prog - это исходная программа. Пусть KLOC (prog) - это шичество тысяч значимых строк кода программы prog. Мера качества ¡компиляции Cdecomp вычисляется согласно следующей формуле:

= у max(0,K'-K) m dKOmp ¿¿п KLOCiprog) 1 J-ем ближе значение меры к нулю, тем выше качество декомпиляции.

Таблица 1. Штрафы за артефакты трансляции и неполноту восстановления.

конструкции программы назначаемые штрафы

операция явного приведения типов (type) 2

оператор перехода goto 3

оператор выхода из середины цикла break 1 1

оператор прерывания витка цикла continue

тип данных объединение union 3

ассемблерная инструкция 4

невосстановление оператора switch 2

невосстановление оператора for 1

невосстановление производного типа данных использование адресной арифметики вместо оператора 4 2

доступа к элементу массива

Задачу декомпиляции предлагается рассматривать как совокупность трех

адач:

1. восстановление функционального интерфейса,

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

3. восстановление переменных и типов данных.

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

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

В заключении первой главы представлена постановка зада1 диссертационной работы.

В главе 2 в первой части представлен обзор методов решения bci составляющих задачи декомпиляции. Обзор задачи восстановлен! функционального интерфейса программы начинается с обзора метод< обнаружения точки входа пользовательского кода, то есть функции main. Дал> рассматривается восстановление библиотечных функций и системных вызов! для программ, скомпонованных как динамически, так и статически. Так» рассматривается восстановление функций с учетом возможных оптимизащ компилятора и использования разных стандартных соглашений о вызовах.

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

Анализ графа потока управления при декомпиляции описан в работах ! Цифуентес (С. Cifuentes). Предложенный ею метод основан на выделении в грае потока управления регионов, где регион - это набор базовых блоков, имеющ! только одну входную и только одну выходную дуги. После чего размеченный i регионы граф потока управления перестраивается в модифицированный граф, г; в отличие от исходного графа, узлами являются не базовые блоки, а регион После того, как в графе выделены регионы, вычисляется отношен] доминирования, а дуги классифицируются на прямые, обратные и косые. Далее i модифицированный граф потока управления накладываются шаблонь соответствующие восстанавливаемым структурным конструкциям программ: if-then, if-then-else, while, do-while. Циклом считается множест] вершин, доступных из данной по обратному ребру и удовлетворяюшр дополнительным условиям, определяющим тип цикла. Метод работа итеративно. Восстановленная структурная конструкция преобразовывается новый регион, после чего на обновленный граф снова накладываются шабло* структурных конструкций. Выполнение завершается, когда на очередном этапе i один из структурных шаблонов уже не подходит.

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

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

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

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

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

1. базовых типов данных языка, таких как char, unsigned long и т. п., и

2. производных типов данных, таких как типы структур, массивов и

указателей.

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

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

Алгоритм опускает из рассмотрения восстановление локальных переменных, сохраненных на стеке и регистрах. Также алгоритм не поддерживает восстановление знаковости типов. В случае конфликтов создаются объединения (union). Как следствие, программа восстанавливается с низким уровнем качества. Конфликтующие термы не удаляются из рабочего множества, что может приводить к его быстрому росту, делая алгоритм неэффективным по времени и

памяти. Размер рабочего множества не ограничен и, как следствие, во мног случаях алгоритм не сходится. Следовательно, предложенный А. Майкрофт< метод не применим для автоматического восстановления типов данных.

Другой подход к задаче анализа бинарной программы представлен работах Г. Балакришнана (G. Balacrishnan), которые посвящены метод! статического выявления значений переменных в исполняемых файле Предложенные им методы основаны на интервальном анализе. Для необходим! переменных восстанавливаются размер производных типов данных и размещен в памяти полей структурных типов. Алгоритм базируется на интуитивн< предположении, что шаблоны обращения к памяти в программе да! информацию о том, как располагаются данные. Следует заметить, что, посколь задачей алгоритма является поиск уязвимостей, а не восстановление тип данных, в нем не предусмотрено объединение раздельных использований одно и того же структурного типа, что неприемлемо для задачи восстановления тип данных. Кроме того, в методе не предусмотрено восстановление базовых тип полей структур и элементов массивов.

Еще один подход к восстановлению типов данных в задаче декомпиляц] предложен в работе М. Ю. Гусенко. В качестве операций над типизированньи данными рассматриваются инструкции процессора, а в качестве значен] типизированных данных рассматриваются значения примитивов, которыми oi оперируют. Каждый тип характеризуется именем и длиной. В работе предложе! методы восстановления следующих типов данных: числовой, указатель, структу (struct), объединение (union) и массив.

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

Следует также отметить, что в работах К. Цифуентес восстановление тип переменных практически не рассматривается.

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

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

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

Во второй части второй главы дается краткое описание существующих на ¡анный момент декомпиляторов. Это - декомпилятор Boomerang, декомпилятор )СС, декомпилятор REC и плагин Hex-Rays к интерактивному дизассемблеру Ida 'го. Все рассматриваемые декомпиляторы, кроме плагина Hex-Rays, на вход [ринимают исполняемый файл, а на выходе выдают программу на языке Си. Для сравнения функциональных возможностей декомпиляторов был разработан естовый набор на языке Си, покрывающий основные языковые конструкции зыка.

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

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

Модели восстановления типов данных оперируют объектами. Объекты строятся из конструкций ассемблерной программы, в которые отображаются переменные исходной программы, а именно из:

1. регистров общего назначения центрального процессора,

2. непосредственно адресуемых областей памяти:

1) ячеек памяти по абсолютным адресам, которые соответствуют глобальным переменным в исходной программе,

2) ячеек памяти по фиксированным смещениям относительно стекового кадра, соответствующим локальным параметрам,

3) ячеек памяти по фиксированному смещению относительно вершины стека, а также занесенных на стек соответствующими инструкциями. Они соответствуют фактическим параметрам в вызываемых функциях.

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

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

Для восстановления типов данных в представляемой работе разработано дь модели: модель восстановления базовых типов данных (char, unsigned cha: short int, int,....float) и модель восстановления производных типе данных (массивы, структуры, указатели произвольного уровня косвенности).

Основная задача, которая должна быть решена при восстановлени базовых типов данных, это определить,

1. имеет ли объект указательный, вещественный или целый тип,

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

3. для объектов целого типа определить, знаковый ли это тип данных ил беззнаковый.

Все базовые типы языка Си отображаются в модельные типы, которь: представляются в виде тройки <core, size, sign >. Ядро(соге) может принимат значение указательный (pointer), целый (int) или вещественный (float Размер (size) может принимать значение 1, 2 или 4 (для 32-битной архитектуры Знак (sign) может принимать значение «знаковый» (signed) или «беззнаковый (unsigned). Множество модельных типов - это множество троек, полученнь. отображением базовых типов языка Си, следовательно, оно не содержит трое: которые не соответствуют ни одному базовому типу языка. В процесс восстановления типов данных для каждого объекта строится модельный тип. Д: этого вводится понятие обобщенного модельного типа данных. Обобщенны модельный тип данных - это тройка множеств <CORE, SIZE, SIGN>, где

CORE с {pointer, int, float}, SIZE с {1, 2, 4} и SIGN £ {signed, unsigned}.

Изначально каждый объект характеризуется обобщенным модельным типо] каждый атрибут которого - полное множество, то есть:

«{pointer, int, float}, {1,2,4}, {signed, unsigned}> Далее по ассемблерной программе строятся три системы уравнений типов д: каждого из атрибутов модельного типа. Например, по ассемблерной инструквд add гх,гг,гъ, которая складывает регистры г,, г2 и помещает результат в регистр i для атрибута sign строится уравнение obj¡-.<signi>-objí<sign¡>+obj1<sign1>, г;

бъекты obj[,obj1,obj3 построены по регистрам г„гг,г2 соответственно, а : sign, >, <sign2 >, <signз > - это атрибуты обобщенных восстанавливаемых типов бъектов objvobj2,obj3 соответственно. Каждая система решается итеративным игоритмом, который основан на продвижении значений. Сбор информации по сем атрибутам выполняется независимо от значений остальных атрибутов ройки.

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

Определены пять типов ограничений:

• регистровое ограничение, оно влияет на атрибут core и атрибут size типа объекта,

• командное ограничение, оно влияет на все атрибуты типа объекта,

• флаговое ограничение, оно влияет на атрибут sign соответствующего типа объкта и

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

• ограничение профиля является дополнительным. Это ограничение предоставляет информацию о том, что тип объекта не является указательным или не является знаковым. Ограничения профиля строятся на основе результатов динамического анализа программы, описание которого представлено в главе 4 работы.

Продвижение значений атрибутов выполняется на основании правил работы

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

(1) < sign > {unsigned} + (2) < sign, > {signed, unsigned} +

(l)<sign? >{signed,unsigned} = (2)<signg >{signed} =

(1) < signr > {signed, unsigned} (2) < signr > {signed, unsigned}

Рис. 1. Пример операции объединения для атрибута знак.

[а рис. 1 показаны 2 уравнения. В уравнении (1) тип объекта objp беззнаковый, о яаковости типа объекта objq нет информации, он может быть как знаковый, так и еззнаковый, но согласно стандарту языка Си тип объекта objr должен быть еззнаковый. В уравнении (2) из уравнения (1) уже известно, что тип объекта objr

беззнаковый, следовательно, согласно стандарту, тип объекта objv тоже долже быть беззнаковый, так как тип объекта objq знаковый согласно уравнению (2).

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

Модель восстановления производных типов данных основывается i представлении адресов обращения к памяти в канонической форме:

(base+offset+YJCjXj), где base - это база, то есть базовый адрес, который являете

>1

объектом при восстановлении базовых типов, offset - это константное смещени

я

значение которого известно при статическом анализе, £CjXj

м

мультипликативная составляющая. При условии, что исходная Си програм!» строго удовлетворяет стандарту, base имеет указательный тип. Для кажде инструкции обращения к памяти во входной программе на языке ассемблера,: исключением инструкций обращения к локальным переменным, глобальны переменным и параметрам функций, строится локальное адресное выражен! адреса обращения к памяти в данной инструкции. Например, инструкщ moví 12(%ebx), %есх соответствует локальное адресное выражеш %ebx + 12. Для аргументов локального адресного выражения выполняет! прослеживание значений в обратном направлении либо до загрузки из памят значения, либо до вычисления, отличного от сложения или умножения, либо ; границы базового блока. Найденные выражения для аргументов подставляются локальное адресное выражение, и после алгебраических преобразований строит! полное адресное выражение, которое отображается в терм адресного выражени Таким образом, полным адресным выражениям доступа к памяти во входне программе соответствуют термы адресных выражений в модели восстановлен! производных типов.

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

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

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

[1] struct t {

[2] int of 1;

[3] short of 2,*

[4] double of3;

is] } г6]

[7] void f (void) {

[8] struct t * tmpl, *tmp2, *tmp3;

[9] tmpl»tmp2;

[10] tmpl->of1;

[11] tmp2->of2;

[12] tmp3=tmp2;

[13] tmp3->of3;

[14] }

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

Объекты, соответствующие переменным struct t * tmpl, *tmp2 и *tmp3, помечаются метками LI, L2 и L3 соответственно. Все три метки оказываются в одном классе эквивалентности баз после применения прямого продвижения меток. Операция присваивания в строке 9 определяет эквивалентность объектов, помеченных метками L1 и L2. Операция присваивания в строке 12 определяет эквивалентность объектов, помеченных метками L2 и L3. Далее строится множество смещений для нового структурного типа S. В соответствии со строками 10, 11 и 13 множество смещений для структуры S следующее: {ofl, of 2, of3}. На рис. 3 представлен скелет восстанавливаемой структуры S.

struct S{

typel ofl; type2 of2; type3 of3;

}

Рис. 3. Пример скелета восстанавливаемой структуры S.

Массивы восстанавливаются аналогичным способом, Если все смещения п эквивалентным базам имеют одну и ту же мультипликативную составляющую, т восстанавливаемый производный тип объявляется массивом. Для дальнейшег восстановления строится объект для первого элемента массива. Размер элемент массива вычисляется как НОД всех мультипликативных составляющих, некоторых случаях оказывается возможным восстановить размер самого массив; На рис. 4 представлен пример восстановления массива структур.

ьазе [0) п

- П •

агг [1] Л2 => агг +4+8*1; [1] п

агг [Л .£1 => агг + 0 + 8 * ;) ; п

[2] п

а

Рис. 4. Пример восстановления массива структур.

Массив агг состоит из элементов, тип которых - структура, состоящая I полей £1 и 12. В исходной программе были инструкции обращения к полю 1 1-го элемента массива и полю £1 j -го элемента массива. На рис. 4 представлен выражения в канонической форме, соответствующие этим инструкциям. Разме элемента массива составляет 8, однако разность между смещениями 12 элемент агг [1] и 11 элемента агг [ j ] составляет |4 - 0| = 4 < 8, что меньше разме{ элемента массива, и, следовательно, тип элементов массива агг - структура.

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

В корректной программе на языке Си указатели, как правило, хранят адреса [з множества отображенных виртуальных адресов (стек, куча, статические ;анные, код), либо специальное значение null. Значения, которые принимают наковые целочисленные переменные, сгруппированы около нуля. То есть, [апример, значение -2 знаковая целочисленная переменная принимает начительно чаще, нежели значение 2*10'. С другой стороны беззнаковые [елочисленные переменные для 32-х битной архитектуры редко принимают начение, соответствующее -2 в дополнительном коде. Значение -1 необходимо усматривать специальным образом, так как оно соответствует максимальному беззнаковому целому значению и часто выступает в роли индикатора ошибки2.

Для 32-х битной архитектуры достаточно профилировать значения только 2-битных ячеек памяти, так как указатели имеют размер 32-бита. 1епосредственно профилирование значений переменных реализовать атруднительно, так как:

• значения разных переменных могут храниться по одним и тем же адресам.

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

• одни и те же локальные переменные могут иметь различный адрес в разные

моменты времени.

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

Отображение VP - это отображение из множества Addr виртуальных дресов сегмента кода программы во множество 32-битных значений Val, которые аписывались или считывались инструкцией по этому адресу. Множество дресов, которые не принадлежат сегменту кода программы, исключается. )тображение DM - это отображение из множества Addr виртуальных адресов :амяти во множество объектов Loe, соответствующих этим адресам памяти в ^ассемблированной программе. Отображение IVP из множества ассемблерных инструкций во множество 32-битных значений, которые загружаются на регистр [ли выгружаются в память соответствующими инструкциями, строится

VP: Addr -» 2Va¡ DM: Addr -> Loe

посредством комбинирования отображений VP и DM: ^ ^

IVP{x) = VP(DM'\x))

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

2 Эвристики составлены на основании результатов исследования значений, принимаемых переменными различного типа данных, которые опубликованы в работе Я. Сазейда (Y. Sazeides) и Дж. Смита (J. Smith) «Предсказуемые значения данных»//Материалы конференции Micro-3,1997, стр. 749-754.

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

Множество УР(оЬу') - это множество значений, принимаемых объектом оЬ j за время выполнения программы. УаШАс1с1г - это множество значений, которое может принимать переменная указательного типа. Для разделения целочисленных и указательных типов предложена метрика РС(оЬдля уточнения знаковости типа предложена метрика иС(оЪ}). На рис. 5 представлены формулы для вычисления этих метрик.

\УР{оЪ]1)-{пиЩ\

ВД,.)=1- Е^^^г [3]

<у,ы, М = 1. если X е КР(о6/,.), и аск. (х) = 0, если х £ УР(оЬ]{) Рис. 5. Метрики для повышения точности восстановления базовых типов данных.

В этой же главе представлены алгоритмы сбора профиля анализируемой программы и обработки собранного профиля. Представленные алгоритмы реализованы в утилите ТОТгасе, особенности реализации которой представлены в главе 5. Утилита позволяет анализировать адреса и значения, используемые во время выполнения программы, и выдаёт результат в формате ХМЬ-документа, который подгружается по запросу инструментальной среды декомпиляции ТуБес.

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

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

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

Результат работы утилиты ЮНеар предоставляется в формате ХМЬ-документа, который подгружается по запросу инструментальной среды декомпиляции ТуБес.

Глава 5 посвящена описанию инструментальной диалоговой среды ¡компиляции программ в язык Си - декомпилятору TyDec. Декомпилятор додерживает несколько входных форматов: программы на языке ассемблера для >хитектуры IA32 в синтаксисе AT&T и Intel, исполняемые модули, бинарные »ассы выполнения, собранные на симуляторе процессора. Декомпилятор имеет □витый графический интерфейс аналитика для управления процессом ¡компиляции. Результатом работы декомпилятора является типизированная руктурная программа на языке Си. Схема архитектуры декомпилятора эедставлена на рис. 6.

Восстановление > функционального интерфейса

Входные данные !

/ Графический . ( интерфейс ] \ пользователя/'

Си-дерево

Си-программа

""[_/ Граф потока _J~ \ управления /

Структурный ; анализ j

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

Информация

времени выполнения

Рис. 6. Схема архитектуры декомпилятора TyDec.

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

Множество входных форматов: текстовый файл с ассемблерными ютрукциями в нотации AT&T или Intel, исполняемые файлы, трассы, снятые [мулятором AMD SimNow или другими инструментальными средствами.

ASMTree - это внутреннее представление входной программы в виде >следовательности инструкций. Модуль ASMTree отвечает за построение и ¡анение дерева внутреннего представления программы и предоставляет лерфейс для работы с ним другим компонентам системы.

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

Модуль CFG выполняет построение графа потока управления.

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

CTree - это компонент, обеспечивающий работу декомпилятора с 1утренним представлением восстанавливаемой программы на языке Си в виде штаксического дерева. Модуль строит текст программы на языке Си по {утреннему представлению с использованием результатов работы модулей «становления типов данных и структурных конструкций.

Модуль GUI реализует графический интерфейс декомпилятора и поддерж* диалогового режима работы эксперта.

Модуль восстановления типов данных отвечает за восстановление типе данных декомпилируемой программы. В качестве входных данных используетс внутреннее представление программы (граф потока управления). По ней строится система уравнений типов данных. Далее применяется алгорит восстановления типов данных. Информация, полученная при динамическо анализе программы, подгружается непосредственно в модуль восстановлен! типов данных из файлов, в которые сохраняется при профилировании программ дополнительными утилитами, встроенными в инструментальную сре; декомпиляции TyDec.

Представленные в работе методы позволяют решать задачу декомпилящ целостным образом от начала до конца, так как разработанные и реализованнь методы позволяют решить все подзадачи декомпиляции. В главе 5 представлен особенности реализации восстановления функционального интерфеш программы на основе стандартных соглашений о вызовах, также описаны метод обнаружения точки входа в пользовательскую программу (функции mair Методы структурного анализа, традиционно используемые при компиляци существенно расширены и адаптированы с учетом особенностей декомпиляш как преобразования, обратного к компиляции. Поддерживается полн< восстановление управляющих конструкций языка Си, включая не толы операторы цикла while и do-while и оператор ветвления if, но и оператс множественного выбора switch, а также оператор цикла for. Восстановлен! типов данных выполнено на основе представленных моделей.

На рис. 7 представлены примеры восстановления программ расширение Hex-Rays к интерактивному дизассемблеру IdaPro. Меры качества декомпилящ для Hex-Rays, рассчитанные по формуле (1) с учетом назначаемых штрафе представленных в таблице 1, для примера 1 и для примера 2 соответствен] равны:

С Z0)=_ii_ = 7333; и Cd = гпах(0,9*2-0 +1) _ —— 2714;.

tecomp 6*10 6*10 7*10 7*10

Соответствующие меры качества декомпиляции для декомпилятора TyDec для т же примеров нулевые.

Тестирование работы инструментальной среды TyDec было произведе] более чем на 100 примерах, пятая часть которых это программы с открыть исходным кодом. На всех примерах инструментальная среда показала высок качество восстановления низкоуровневых программ. На рис. 8 представл пример работы инструментальной среды TyDec для примера 1 и примера которые представлены на рис. 7.

Экспериментальное сравнение качества восстановления програа декомпилятором TyDec и декомпилятором HexRays проводилось на 7 программ: 6 из которых - это утилиты с открытым исходным кодом, а последн программа - это утилита, которая вычисляет значение производной многочлена точке.

Пример 1 Результат декомпиляции Пример 2 Результат декомпиляции

iclude <stdio.h> intl6 cdecl void f2 ir.t cdacl

f(float al, float a2) (signed short x. aub_401314

. 3id f { unsigned short y) (int al, int a2)

float a, float b) _intis result! // ax@3 { {

[ asm unsigned short int result; // eax@2

if (a < b) { { i = 0; int v3;

printfO'a < b\n")/ fid tebp+arg_0] for (i . 0; // [sp+14h] [bp-4b]§l

} fid [ebp+arg_4] i С X! signed _xntl6 v4;

if (a > b) { fucompp i + + ) // [sp+12h] [bp-6h]@l

printfC'a > b\n") i fnstsw ax { HIWORD(v3) = al;

} sahf у 3, LOWORD(v3) « a2;

aturn; } g(y>; v4 = 0;

) if ( I(_CF | _ZF> ) } while ( 1 ){

puts("a < b"); return; result = SHIW0RD(v3);

asm } if ((unsigned _intl6)v4>=

{ (signed int)SHIWORD(v3))

fid [ebp+arg_0] break;

fid [ebp+arg_4] LOWORD(v3)a(_WORD)v3 + 3;

fxch st(l) sub_40129 0((unsigned

fucompp _intl6)v3);

fnstew ax ++v4 ;

sahf }

} return result;

if ( 1(_CF | _ZF) ) }

result ■ puts("a > b")?

return result; >

Рис. 7. Примеры восстановления программ с невысоким уровнем качества.

3: sub esp, 0x8

4: fid duord ptr [0x8 + ebp]

5: fid duord ptr [Oxe + ebp] |

6: fucompp

7: fnstsw ax

8: sahf

9: jbe ",L2"

10: label ".17"

11: mov duord ptr [esp] , ".LC0"

12: call "puts"

13: label ".LZ"

14: fid duord ptr [0x8 + ebp]

15: fid duord ptr [Oxc + ebp]

¡'void f ( float, float ); : void puts ( char * ); j;ivoid f ( float argl, float arg2 )

if I azg2 > argl ) < )'

)

if ( argl > arg2 ) puts ( "a > b" );

)

return;

; mov uord ptr I [Oxfffifffe + ebp], 0x0 10: jmp ".L2" 11: label. ".L3" 12: add word ptr |[Oxffffffe8 + ebp], 0x3

: movz eax, uord ptr I[OxffffffeB + ebp]

14: mov duord ptr [esp], 1 eax

: call "g" : add uord ptr |[Oxfffffffe + ebp], 0x1 K 17: label ".L2"

18: movz edx, uord ptr |[Oxfffffffe + ebp]

void f2 ( short, unsigned short ); ¡void g ( unsigned short );

¡void f2 ( short argl, unsigned short arg2 ) j{

short varl; unsigned short var2; short var3; unsigned short i;

m - ««n

var2 •= arg2; var3 ■ 0;

for ( 1 - 0; i < f§|g; i = ( short } i + 1 ) < var2 = ( short ) var2 + 3; g ( var2 );

}

return;

Рис. 8. Пример работы инструментальной среды TyDec.

В таблице 2 представлены характеристики программ, для которь: выполнялось сравнение качества восстановления. Колонка «СЬОС» содержа количество строк кода в исходной программе, колонка «АЬОС» содержа количество строк кода в ассемблерной программе.

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

Название CLOC ALOC Описание

35 wc 241 465 Утилита wc, файл «wc.c»

36 cat 262 618 Утилита cat, файл «cat.c»

37 execute 726 1837 Утилита be, файл «execute.c»

38 day 503 1383 Утилита calendar, файл «day.c»

39 deflate 403 669 Утилита gzip, файл «deflate.c»

59 lair 674 1664 Утилита yacc, файл «lalr.c»

84 derive 71 255 Утилита derive, файл «derive.c»

Таблица 3 показывает процент восстановления исходного кода до декомпилятора ТуИес и декомпилятора НехКаув соответственно. Следу< отметить, что программа Зб_cat и программа 37_ехес1^е не были полность восстановлены декомпилятором НехЖауз из-за наличия оператора б^л/л-Ьс! восстановление которого он не поддерживает в полном объеме. В таблице представлен подсчет количества штрафных баллов за использован! низкоуровневых конструкций при восстановлении, а также за невосстановлеш высокоуровневых конструкций языка Си в соответствии с таблицей 1. Колош «011» содержат количество штрафных балов у исходных программ, колонки «ТЕ - количество штрафных балов у программ, восстановленных декомпиляторе ТуВес, и колонки «НЯ» - количество штрафных балов у програм: восстановленных декомпилятором He.xR.ays.

Таблица 3. Процент восстановления программы декомпиляторами.

Название TyDec HexRays

35 wc 100% 100%

36 cat 100% 84%

37 execute 100% 0%

38 day 100% 100%

39 deflate 100% 100%

59 lair 100% 100%

84 derive 100% 100%

Вычисление качества восстановления программ обоими декомпиляторами соответствии с формулой [1] представлено в таблице 5. Как можно заметить, всех примерах качество восстановления программ декомпилятора ТуБ существенно выше, чем качество восстановления программ декомпилято НехЯауй.

Таблица 4. Вычисление количества штрафных баллов.

35 wc 36 са1 38 <1ау 39 deflate 59 larl 84 derive

OR TD HR OR TD HR OR TD HR OR TD HR OR TD HR OR TD HR

type) 1 1 32 0 0 9 7 6 102 23 6 66 5 0 332 0 0 0

ioto 1 4 2 0 3 7 0 5 0 0 0 1 0 1 0 0 0 2

jreak 0 0 5 8 8 10 0 0 0 1 3 0 5 3 9 0 1 1

:ontinue 0 0 0 5 0 0 0 0 0 1 0 0 0 1 0 0 1 0

inion 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

ism 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 48

iwitch . 0 1 - 0 1 - 0 1 - 0 0 - 0 0 - 0 0

or 1 2 - 1 2 - 6 14 - 32 37 - 2 36 - 0 5

itruct - 0 1 - 0 0 - 0 1 - 0 0 - 0 1 - 1 0

] 0 0 - 0 3 - 0 3 - 0 16 - 16 79 - 0 0

otai 5 15 52 13 18 59 14 33 230 48 44 201 15 41 539 0 3 204

Таблица 5. Вычисление меры качества.

Название TyDec HexRays

35 wc 41 195

36 cat 19 156

38 day 37 429

39 deflate 0 389

59 lair 38 777

84 derive 42 2873

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

о теме диссертации опубликованы следующие работы:

В изданиях рекомендованных ВАК для публикации результатов шдидатских и докторских диссертаций:

1. К. Н. Долгова, А. В. Чернов. Автоматическое восстановление типов в задаче декомпиляции. Программирование, номер 2, журнал Российской академии наук. Март - апрель 2009, стр. 63-80.

2. К. Н. Долгова, А. В. Чернов, Е. О. Деревенец. Методы и алгоритмы восстановления программ на языке ассемблера в программы на языке высокого уровня. Проблемы информационной безопасности, Компьютерные системы, № 3.2008 год, стр. 48-62.

Прочие публикации:

3. Katerina Troshina, Alexander Chernov and Yegor Derevenets. С Decompilatio Is It Possible? In Proceedings of International Workshop on Progra Understanding. Altai Mountains, Russia. 19-23 June 2009, pp. 18-27.

4. Katerina Troshina and Alexander Chernov. High-Level Composite Ту] Reconstruction During Decompilation from Assembly Programs. In Proceedin of 7th Perspectives of System Informatics. Akademgorodok, Novosibirsk, Russi 15-19 June 2009, pp. 292-299.

5. Katerina Troshina, Alexander Chernov and Alexander Fokin. Profile-Based Ту] Reconstruction for Decompilation. In Proceedings of IEEE 17th Internatior Conference on Program Comprehension. Vancouver, Canada, 17-19 May 200 pp. 263-267.

6. Katerina Dolgova, Alexander Chernov. Automatic Type Reconstruction Disassembled С Programs. In Proceedings of IEEE 15th Working Conference < Reverse Engineering 2008. Antwerp, Belgium, October 2008, pp. 202-206.

7. E. О. Деревенец, К. H. Долгова. Структурный анализ в зада декомпиляции. Прикладная информатика №4 Август 2009 г., Моек МаркетДС, стр. 87-99.

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

9. В. Ю. Антонов, К. Н. Долгова. Восстановление типов данных использованием информации о выполнении программы. Сборник стат молодых ученых факультета ВМиК МГУ № 6 2009 г., Москва, стр. 6-16.

10. К. Н. Долгова, А. В. Чернов. О некоторых задачах обратной инженер*: Труды Института системного программирования, Том 15, Москва 2008, ст 119-134.

11. К. Н. Долгова, А. В. Чернов. Методы и алгоритмы восстановлен программ на языке ассемблера в программы на языке высокого уров! Материалы XVII Общероссийской научно-технической конференц: «Методы и технические средства обеспечения безопасности информацш С.-Петербург, июль 2008, стр. 101.

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

Напечатано с готового оригинал-макета

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

Введение

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 методы, позволяющие восстанавливать методы обработки исключительных ситуаций для языка Си++, а также расширить инструментальное средство модулями, позволяющими восстанавливать программы в язык Си++ непосредственно.

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.