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

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

Соловьев Михаил Александрович

ВОССТАНОВЛЕНИЕ АЛГОРИТМА ПО НАБОРУ БИНАРНЫХ ТРАСС

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

Автореферат

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

005059934

2 3 мдй /013

Москва 2013

005059934

Работа выполнена в Федеральном государственном бюджетном учреждении науки Институте системного программирования РАН.

Научный руководитель: доктор физико-математических наук, доцент

Аветисян Арутюн Ишханович

Официальные оппоненты: Машечкин Игорь Валерьевич, доктор физико-

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

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

Ведущая организация: Федеральное государственное бюджетное учреждение науки Институт проблем информатики Российской академии наук

Защита диссертации состоится 13 июня 2013 г. в 16 часов на заседании диссертационного совета Д 002.087.01 при Федеральном государственном бюджетном учреждении науки Институте системного программирования Российской академии наук по адресу: 109004, Москва, ул. Александра Солженицына, д. 25.

С диссертацией можно ознакомиться в библиотеке Федерального государственного бюджетного учреждения науки Института системного программирования Российской академии наук.

Автореферат разослан « » ЛД& & 2013 г.

Ученый секретарь диссертационного совета кандидат физ.-мат. наук

/Прохоров С. П./

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Актуальность

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

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

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

В таких условиях многие существующие решения статического анализа бинарного кода перестают работать или выдают малоосмысленные результаты. При применении динамического анализа необходимо преодолеть две основные трудности: (1) выполняющийся анализ может повлиять на поведение программы; (2) возможно исследование лишь той части программы, которая оказалась покрыта в ходе запусков, произведённых в процессе анализа. Одним из наиболее перспективных подходов к преодолению первой трудности является полносистемная трассировка, когда вся анализируемая система выполняется в достаточно точном симуляторе целевой машины: записывается трасса всех инструкций, выполнявшихся на симулируемом процессоре. В настоящей работе предполагается, что используется именно такой подход, а применяемый симулятор достаточно точен: результаты выполнения программ в симуляторе не отличаются от выполнения на реальной аппаратуре.

Вторая трудность — вопрос покрытия программы — связана с природой динамического анализа и должна решаться путём увеличения рассмотренной части программы. Существуют два основных источника данных для улучшения покрытия: (1) дополнительные трассы выполнения, покрывающие большее количество сценариев использования программы; (2) статический образ программы. В данной работе рассматривается только первый из перечисленных вариантов: предлагается метод анализа композиции трасс. Совместное использование набора трасс и статического образа программы (или образов в разных точках выполнения) является возможным направлением дальнейших исследований.

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

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

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

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

Основные результаты

В диссертации получены следующие основные результаты.

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

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

3. Разработан язык спецификаций для описания моделей машинных инструкций и описаны такие модели для базовых наборов инструкций процессорных архитектур х86 и х86-64, ARM, PowerPC и MIPS.

4. На основе предложенных автором методов и языка спецификаций разработан и реализован набор инструментов:

• подсистема спецификации моделей машинных инструкций;

• подсистема оптимизации и устранения артефактов, внесённых трансляцией в машинно-независимый вид (общие подвыражения, мёртвый код и т.п.);

• подсистема конкретной интерпретации;

• проведена интеграция подсистем со средой анализа бинарного кода, разрабатываемой в ИСП РАН.

Практическая ценность работы

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

Апробация работы

Основные результаты работы опубликованы в статьях [1-5]. Результаты работы обсуждались на следующих конференциях.

1. XVI Международная научная конференция студентов, аспирантов и молодых учёных «Ломоносов-2009», Москва, 13-18 апреля 2009 г.

2. Международная конференция «РусКрипто'2009», Москва, 2-5 апреля 2009 г.

3. Международная конференция «РусКрипто'2010», Москва, 1-4 апреля 2010 г.

4. XIX Научно-техническая конференция «Методы и технические средства обеспечения безопасности информации», Санкт-Петербург, 510 июля 2010 г.

5. XX Научно-техническая конференция «Методы и технические средства обеспечения безопасности информации», Санкт-Петербург, 27 июня -1 июля 2011 г.

6. Научная конференция «Ломоносовские чтения 2013», Москва, 1524 апреля 2013 г.

Объём и структура диссертации

Работа состоит из шести глав, списков иллюстраций и таблиц, списка литературы и одного приложения. Общий объём диссертации — 123 страницы (из них 4 — приложение), в том числе 56 иллюстраций и 9 таблиц. Список источников насчитывает 60 наименований.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

В главе 2 приводится обзор работ, имеющих непосредственное отношение к теме диссертации. Рассматриваются существующие программные средства, связанные с восстановлением алгоритмов: (1) средства моделирования семантики машинных инструкций, в том числе системы бинарной трансляции; и (2) системы статического и динамического анализа бинарного кода. В первой группе рассматривается, в частности, библиотека VEX, являющаяся частью средства инструментирования бинарного кода Valgrind. Среди средств, отнесённых ко второй группе, следует особо отметить компоненты Vine и TEMU системы BitBlaze, а также среду анализа ВАР (Binary Analysis Platform).

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

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

2. Все рассмотренные промежуточные представления работают с фиксированными наборами базовых типов и примитивных операций. Это

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

Глава 3 посвящена описанию предлагаемого подхода к восстановлению алгоритма. Описывается в общем виде процедура, лежащая в основе данного подхода (рисунок 1), и подробно разбираются её этапы.

Рис. 1: Схема восстановления алгоритма

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

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

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

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

Раздел 3.2 описывает графовое представление тСРО и метод объединения нескольких связанных трасс в виде такого представления. В общем виде тСРО — это ориентированный граф с петлями, соответствующий набору межпроцедурных графов потока управления отдельных потоков выполнения (нитей) изучаемой системы с дополнительными пометками. Каждая компонента связности в тСЕй отвечает одному потоку выполнения.

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

ски изменяемый код. Динамически изменяемый код в программе возникает в следующих случаях: (1) когда происходит подгрузка динамической библиотеки на место в памяти, откуда была выгружена другая; (2) когда в программе используются «трамплины», обеспечивающие позднее связывание функций; (3) когда программа содержит навесную защиту, выполняющую поэтапную распаковку, расшифровку кода или динамическую кодогенера-цию; и (4) когда программа обладает полиморфной природой. В настоящей работе все эти ситуации рассматриваются единообразно: выделяются интервалы статичности кода в программе, и соответствующие базовые блоки причисляются к одному поколению. Подграф графа тСЕй, соответствующий одному поколению, представляет собой обычный статический межпроцедурный граф потока управления, к которому могут применяться без изменений известные алгоритмы анализа. Если же, наоборот, все базовые блоки, соответствующие одному поколению, заменить на единственную вершину, сохранив только рёбра, соединяющие разные поколения, то полученный граф будет отражать этапы модификации кода программы.

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

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

Модель операционной семантики строится для одной или нескольких машинных инструкций, называемых вместе единицей моделирования. С

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

Под атомом понимается тип элемента данных, которым как единым целым могут оперировать инструкции машины (например, 32-разрядное целое число, 64-разрядное число с плавающей точкой или 128-разрядное векторное значение). Задание атома предполагает сопоставление с его именем размера описываемых данных в битах. Различные целевые машины могут иметь различные атомы, однако большая их часть для рассмотренных процессорных архитектур оказывается общей.

Преобразования над данными описываются в терминах операций. Операция принимает набор параметров и на его основании вырабатывает результат. В соответствии с требованием к простоте модели возникает естественное желание вводить операции таким образом, чтобы они не имели побочных эффектов. Однако исследование наборов инструкций СЛБС-архитектур, в частности, х86, показывает, что в таком случае описание обновления слова флагов машины для арифметико-логических инструкций оказывается в несколько раз более объёмным, чем описание прямого эффекта инструкции. В связи с этим к побочным эффектам операций предъявляется несколько ослабленное требование: операция не имеет побочных эффектов, кроме, возможно, чтения и записи некоторых флагов модельного слова состояния, представляющего собой 16-разрядное значение, включающее различные флаги состояния (рисунок 2, таблица 1).

р и О г О 1 Б 1 А Р С

Рис. 2: Модельное слово состояния

Таблица 1: Модельное слово состояния

Номер бита Флаг Описание

0 С Флаг переноса (беззнакового переполнения)

2 Р Флаг чётности

4 А Флаг ВСО-переноса

6 Ъ Флаг нуля

7 Б Флаг знака

10 1 Флаг неверной операции с плавающей точкой

11 О Флаг знакового переполнения

12 7. Флаг деления на ноль

13 О Флаг переполнения значения

14 и Флаг антипереполнения значения

15 р Флаг потери точности

При задании операции указывается её имя, сигнатура (последовательность атомов параметров и атом результата) и две 16-разрядных маски — ¡-маска и о-маска. Первая из них указывает, какие биты модельного слова состояния операция читает, а вторая — какие она записывает. К операциям предъявляется требование независимости этих множеств от конкретных значений параметров. При наличии такой информации для каждой операции заранее известно, как организован поток данных через неё: входами являются параметры и флаги, перечисленные в ¡-маске, а выходами — основной результат и флаги, перечисленные в о-маске.

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

Модель адресных пространств используется для единообразного описания всех адресуемых машинными инструкциями данных (регистров, элементов памяти, портов ввода-вывода). Адресное пространство описывается своим именем и атомом адреса и может включать в себя список имён, определённым в нём, и расположения соответствующих участков адресного пространства. В этой модели любое адресуемое инструкцией данное описывается тройкой {Б, а, в), где 5 — адресное пространство, а — адрес

в адресном пространстве, as — размер адресуемого данного. При этом требуется, чтобы а и s соответствовали атому адреса пространства S.

Для пространств оперативной памяти и иных подобных пространств (таких, как пространство портов ввода-вывода х86) представление в модели адресных пространств получается естественным образом. Регистровый файл организуется в адресное пространство так, чтобы максимально учесть вложенность и пересечения регистров. Модель позволяет описать такие особенности регистровых файлов, как регистровые окна или несколько теневых наборов регистров общего назначения.

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

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

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

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

Оператор BRANCH используется для передачи управления в рамках единицы моделирования. Поддерживаются (1) безусловные; (2) условные по маске; и (3) условные по сложному предикату передачи управления. В каждом случае задаётся неотрицательное смещение, по которому следует передать управление при выполении условия. Условная по маске передача управления позволяет в качестве условия использовать произвольный конъюнкт над флагами модельного слова состояния. Условная по сложно-

му предикату передача управления происходит по одному из предопределённых предикатов над флагами модельного слова (например, «знаковое больше или равно», «беззнаковое меньше или равно»).

Операторы LOAD и STORE выполняют, соответственно, загрузку значения из адресного пространства во временную переменную и выгрузку значения из временной переменной в адресное пространство. Для адресации используются описанные выше тройки, где в качестве адреса а выступает значение какой-либо временной переменной, а в качестве размера s — размер атома значения (для LOAD атом указывается явно).

Оператор SPECIAL используется для указания на особое моделируемое состояние машины, при котором дальнейший просмотр операторов данной единицы моделирования должен быть приостановлен: состояние HALT, обозначающее останов процессора до возникновения внешнего события; состояние TRAP, обозначающее возникновение исключения или прерывания с указанным номером; и состояние EXIT, соответствующее побочному выходу из расширенного базового блока.

Оператор ANNOTATION зарезервирован для использования в дальнейших анализах с целью пометки участков кода дополнительными аннотациями. С точки зрения операционной семантики является эквивалентом оператора NOP.

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

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

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

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

В разделе 3.4 описывается подход к выделению алгоритма, основанный на построении срезов (слайсинге и чоппинге). Выделение алгоритма основано на отборе тех операторов программы, на выполнение которых оказали влияние входные данные изучаемого алгоритма, и/или тех, выполнение которых повлияло на выходные его данные. Описывается, каким образом известные алгоритмы статического и динамического слайсинга могут быть применены к программе, переведённой в модельное представление.

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

Раздел 3.5 посвящён оптимизационным преобразованиям, которые применяются к полученному графу алгоритма: нумерация значений, упрощение загрузок и выгрузок и удаление мёртвого кода. Рассматриваемые преобразования упрощают полученный граф и устраняют артефакты, внесённые в процессе трансляции программы в модельное представление. В среднем объём рассматриваемых в дальнейшем операторов сокращается на 20-30%.

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

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

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

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

Далее рассматриваются вопросы интеграции со средой анализа, в частности вопросы моделирования сложных операндов (обращений к памяти по вычисляемым адресам в х86 и операндов со сдвигом в ARM). Приводятся примеры обработки таких операндов.

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

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

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

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

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

В первом примере (раздел 5.1) рассматривается модельная программа, реализующая обменную сортировку. Была проводена процедура восстановления алгоритма. Для алгоритма сортировки с использованием реализованных инструментов были построены машинно-независимый листинг и машинно-независимая блок-схема, описывающие заложенный алгоритм. Далее эта же программа была обработана средством навесной защиты АБР1ЮТЕСТ, и для полученной защищённой версии также был восстановлен алгоритм. В таблице 2 приведены численные характеристики обеих версий программы. В столбцах «ББ всего» и «ББ алгоритма» указаны, соответствено, число базовых блоков в потоке выполнения программы до выделения алгоритма и после.

Таблица 2: Обменная сортировка (пример 1)

Размер Шагов Поколений ББ всего ББ алгоритма

Без защиты 4 КБ 23 х 10ь 7 9000 11

С защитой 137 КБ 123 х 10ь 215 17 000 11

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

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

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

1 label В0_401207:

2 discard sub.i8((±8) v[r:esi], 0)

3 branch.z B0_401218

4

5 label B0_40120C:

6 t.O = r:esi

7 r:al = rl.i8(xor.18((i8) v[t.O], 65), 3)

8 v[t.0] = r:al

9 r:esi = inc.i32(t.O) 10 branch B0_401207

Рис. 3: Алгоритм преобразования пароля (пример 3)

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

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

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

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

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

3. Разработан язык спецификаций для описания моделей машинных инструкций и описаны такие модели для базовых наборов инструкций процессорных архитектур х86 и Х86-64, ARM, PowerPC и MIPS.

4. На основе предложенных автором методов и языка спецификаций разработан и реализован набор инструментов:

• подсистема спецификации моделей машинных инструкций;

• подсистема оптимизации и устранения артефактов, внесённых трансляцией в машинно-независимый вид (общие подвыражения, мёртвый код и т. п.);

• подсистема конкретной интерпретации;

• проведена интеграция подсистем со средой анализа бинарного кода, разрабатываемой в ИСП РАН.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Падарян В. А., Соловьев М. А., Кононов А. И. Моделирование операционной семантики машинных инструкций // Программирование. Москва, 2011. № 3. С. 50-64.

2. Соловьев М. А. Модель вычислительной платформы для динамического анализа защищенного бинарного кода // Сборник тезисов XVI Международной научной конференции студентов, аспирантов и молодых ученых «Ломоносов-2009», секция «Вычислительная математика и кибернетика». Москва: 2009. С. 81.

3. Падарян В. А., Гетьман А. И., Соловьев М. А. Программная среда для динамического анализа бинарного кода // Труды Института системного программирования РАН. Москва, 2009. Т. 16. С. 51-72.

4. О некоторых методах повышения уровня представления при анализе защищенного бинарного кода / А. И. Аветисян, В. А. Падарян, А. И. Гетьман, М. А. Соловьев // Материалы XIX научно-технической конференции «Методы и технические средства обеспечения безопасности информации». Санкт-Петербург: 2010. С. 97-98.

5. Возможности среды анализа бинарного кода ТРАЛ и актуальные направления ее развития / А. И. Аветисян, А. И. Гетьман, В. А. Падарян, М. А. Соловьев // Материалы юбилейной XX научно-технической конференции «Методы и технические средства обеспечения безопасности информации». Санкт-Петербург: 2011. С. 120-123.

Заказ № 144-р/05/2013 Подписано в печать 08.05.2013 Тираж 60 экз. Усл. п.л. 1

ООО "Цифровичок", тел. (495) 649-83-30 www.cfr.ru; е-таП:zak@cfr.ru

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ УЧРЕЖДЕНИЕ НАУКИ ИНСТИТУТ СИСТЕМНОГО ПРОГРАММИРОВАНИЯ РАН

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

04201358089

Соловьев Михаил Александрович

ВОССТАНОВЛЕНИЕ АЛГОРИТМА ПО НАБОРУ БИНАРНЫХ ТРАСС

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

комплексов и компьютерных сетей

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

Научный руководитель: д. ф.-м. н. А. И. Аветисян

Москва - 2013

Аннотация

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

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

В диссертации получены следующие основные результаты.

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

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

3. Разработан язык спецификаций для описания моделей машинных инструкций и описаны такие модели для базовых наборов инструкций процессорных архитектур х86 и х86-64, ARM, PowerPC и MIPS.

4 На основе предложенных методов и языка спецификаций разработан и реализован набор инструментов, подсистема спецификации моделей машинных инструкций; подсистема оптимизации и устранения артефактов трансляции; подсистема конкретной интерпретации. Проведена интеграция подсистем со средой анализа бинарного кода, разрабатываемой в ИСП РАН.

Оглавление

1 Введение 5

2 Обзор работ 10

2.1 Средства моделирования семантики машинных инструкций................10

2.2 Системы анализа бинарного кода ..............................................16

2.3 Выводы............................................................................23

3 Восстановление алгоритма 25

3.1 Исходные данные ................................................................26

3.2 Объединение связанных трасс..................................................28

3.2.1 Статический код..........................................................31

3.2.2 Динамический код........................................................34

3.2.3 Дополнительные уточнения..............................................40

3.2.4 Композиция графов нескольких трасс..................................41

3.3 Моделирование операционной семантики......................................50

3.3.1 Атомы......................................................................51

3.3.2 Операции..................................................................52

3.3.3 Адресные пространства..................................................54

3.3.4 Временные переменные..................................................56

3.3.5 Операторы................................................................56

3.3.6 Примеры моделей........................................................60

3.3.7 Поток управления модели................................................61

3.3.8 Поток данных модели....................................................62

3.3.9 Корректность моделей....................................................64

3.3.10 Трансляция................................................................65

3.4 Выделение алгоритма............................................................65

3.5 Оптимизационные преобразования..............................................68

3.5.1 Нумерация значений......................................................68

3.5.2 Устранение излишних загрузок и выгрузок............................71

3.5.3 Удаление мёртвого кода..................................................72

3.5.4 Пример работы оптимизационных преобразований ..................72

3.6 Представление результата........................................................72

3.6.1 Машинно-независимый листинг........................................74

3.6.2 Машинно-независимая блок-схема......................................76

4 Программное обеспечение 77

4.1 Подсистема спецификации......................................................78

4.1.1 Спецификация машины..................................................79

4.1.2 Архив машины............................................................82

4.1.3 Компилятор спецификаций..............................................84

4.1.4 Компоненты интеграции со средой анализа............................86

4.2 Подсистема конкретной интерпретации........................................87

4.2.1 Механики операций......................................................87

4.2.2 Механики адресных пространств ......................................89

4.2.3 Кодогенерация............................................................91

4.3 Технические ограничения........................................................95

5 Применение 97

5.1 Пример 1..........................................................................97

5.2 Пример 2.....................................104

5.3 Пример 3.....................................105

6 Заключение 109 Список иллюстраций 113 Список таблиц 114 Литература 115 А Язык спецификаций машин 120

Глава 1

Введение

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

Актуальность

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

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

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

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

При применении динамического анализа необходимо преодолеть две основные трудности: (1) выполняющийся анализ может повлиять на поведение программы; (2) возможно исследование лишь той части программы, которая оказалась покрыта в ходе запусков, произведённых в процессе анализа. Одним из наиболее перспективных подходов к преодолению первой трудности является полносистемная трассировка, когда вся анализируемая система выполняется в достаточно точном симуляторе целевой машины: записывается трасса всех инструкций, выполнявшихся на симулируемом процессоре. В настоящей работе предполагается, что используется именно такой подход, а применяемый симулятор достаточно точен: результаты выполнения программ в симуляторе не отличаются от выполнения на реальной аппаратуре. В частности, предполагается, что замедление системы во время выполнения в симуляторе не настолько велико, чтобы приводить к обрывам сетевых соединений. Примером симулятора, обладающего необходимыми свойствами, является доработанный симулятор (^ЕМи [6].

Вторая трудность — вопрос покрытия программы — связана с природой динамического анализа и должна решаться путём увеличения рассмотренной части программы. Существуют два основных источника данных для улучшения покрытия: (1) дополнительные трассы выполнения, покрывающие большее количество сценариев использования программы; (2) статический образ программы. В данной работе рассматривается только первый из перечисленных вариантов: предлагается метод анализа композиции трасс. Совместное использование набора трасс и статического образа программы (или образов в разных точках выполнения) является возможным направлением дальнейших исследований.

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

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

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

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

Основные результаты

В диссертации получены следующие основные результаты.

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

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

3. Разработан язык спецификаций для описания моделей машинных инструкций и описаны такие модели для базовых наборов инструкций процессорных архитектур х86 и Х86-64 [7], ARM [8], PowerPC [9] и MIPS [10,11].

4. На основе предложеннных автором методов и языка спецификаций разработан и реализован набор инструментов:

• подсистема спецификации моделей машинных инструкций;

• подсистема оптимизации и устранения артефактов, внесённых трансляцией в машинно-независимый вид (общие подвыражения, мёртвый код и т.п.);

• подсистема конкретной интерпретации;

• проведена интеграция подсистем со средой анализа бинарного кода [3], разрабатываемой в ИСП РАН.

Практическая ценность работы

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

Апробация работы

Основные результаты работы опубликованы в статьях [1-5]. Результаты работы обсуждались на следующих конференциях.

1. XVI Международная научная конференция студентов, аспирантов и молодых учёных «Ломоносов-2009», Москва, 13-18 апреля 2009 г.

2. Международная конференция «РусКрипто'2009», Москва, 2-5 апреля 2009 г.

3. Международная конференция «РусКрипто'2010», Москва, 1-4 апреля 2010 г.

4. XIX Научно-техническая конференция «Методы и технические средства обеспечения безопасности информации», Санкт-Петербург, 5-10 июля 2010 г.

5. XX Научно-техническая конференция «Методы и технические средства обеспечения безопасности информации», Санкт-Петербург, 27 июня - 1 июля 2011 г.

6. Научная конференция «Ломоносовские чтения 2013», Москва, 15-24 апреля 2013 г.

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

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

В главе 2 приводится обзор работ, имеющих непосредственное отношение к теме диссертации. Рассматриваются существующие программные средства, связанные с восстановлением алгоритмов: (1) средства моделирования семантики машинных инструкций, в том числе системы бинарной трансляции; и (2) системы статического и динамического анализа бираного кода.

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

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

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

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

Глава 6 содержит заключение: делаются выводы и задаются направления дальнейшего развития разработанных методов и реализованного программного обеспечения.

Глава 2 Обзор работ

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

2.1 Средства моделирования семантики машинных инструкций

Симулятор (^ЕМи

Симулятор <ЗЕМи [12] поддерживает широкий набор симулируемых (целевых) и инструментальных процессорных архитектур. (^ЕМи может работать в двух режимах: полносистемном, когда в симуляторе выполняется вся целев�