Восстановление алгоритма по набору бинарных трасс тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат физико-математических наук Соловьев, Михаил Александрович

• Соловьев, Михаил Александрович
• кандидат физико-математических наук
• 2013

Оглавление диссертации кандидат физико-математических наук Соловьев, Михаил Александрович

Оглавление

1 Введение

2 Обзор работ

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

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

2.3 Выводы

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

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

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

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

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

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

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

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

3.3.1 Атомы

3.3.2 Операции

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

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

3.3.5 Операторы

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

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

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

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

3.3.10 Трансляция

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 Применение

5.1 Пример 1

5.2 Пример 2

5.3 Пример 3

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

Глава

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

Введение

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

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

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

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

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

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

При применении динамического анализа необходимо преодолеть две основные трудности: (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] поддерживает широкий набор симулируемых (целевых) и инструментальных процессорных архитектур. (^ЕМи может работать в двух режимах: полносистемном, когда в симуляторе выполняется вся целевая система, и пользовательском, когда выполняется только одна программа. Оба режима работают посредством динамической бинарной трансляции, при этом процесс трансляции в пользовательском режиме заканчивается на границах системных вызовов, а в полносистемном транслируется код всей выполняющейся системы.

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

Инструкции в промежуточном представлении работают над тремя видами переменных. Временные переменные (temporary) локальны в пределах базового блока и требуют явного задания в начале функции. Также явного задания требуют локальные временные переменные (local temporary), а их время жизни ограничено функцией. Наконец, глобальные переменные (global) определяются для заданной пары целевой и инструментальной машин, соответствуют регистрам целевой машины, внутренним структурам, описывающим состояние QEMU и т. д. Глобальным переменным сопоставляются ячейки памяти или регистры инструментальной машины.

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

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

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

Системы бинарной трансляции UQBT и UQDBT

В работах [13] и [14] авторы описывают системы статической и динамической бинарной трансляции UQBT и UQDBT, разработанные в университете Квинсленд. Основной особенностью разработанных систем является возможность их адаптации к широкому классу целевых и инструментальных машин за счёт использования внешних специ-

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

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

(2) декодер инструкций целевой процессорной архитектуры;

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

(4) компонент, преобразующий машинно-зависимое представление RTL с предыдущего шага в машинно-независимый вариант с виртуальными регистрами I-RTL;

(5) компонент обратного отображения, транслирующий I-RTL в машинно-зависимое представление RTL для инструментальной машины;

(6) кодер инструкций инструментальной процессорной архитектуры.

В компонентах (3), (4) и (5) применяются спецификации на языке SSL [15]. Семантика инструкций представляется в виде последовательности операторов: присваиваний (в том числе условных), передач управления, операций с аппаратным стеком и операций обновления флагов. При этом несмотря на заявленную возможность поддержки широкого класса машин, операции обновления флагов рассчитаны на архитектуры х86 и SPARC и используют близость их обработки в этих архитектурах, что не позволяет применять их в общем виде для моделирования семантики машинных инструкций. Помимо ограниченной обработки побочных эффектов базовых наборов инструкций, не поддерживаются векторные и привилегированные инструкции.

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

Система динамического инструментирования Valgrind

Valgrind [16] представляет собой платформу для проведения динамического анализа бинарного кода во время выполнения. Ядро системы Valgrind обеспечивает трансляцию машинного кода в промежуточное представление и обратно. Над промежуточным представлением работают остальные модули системы Valgrind, выполняя разные виды инструментирования. Среди этих модулей особо следует выделить инструмент Redux [17], обеспечивающий построение динамических графов потоков данных

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

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

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

(1) декодирование машинных инструкций в древовидное промежуточное представление;

(2) первый оптимизационный проход, включающий удаление общих подвыражений, мёртвого кода и продвижение констант, и выдающий на выходе плоское промежуточное представление;

(3) инструментирование: дополнение плоского промежуточного представления операторами, реализующими выполняемый вид анализа;

(4) второй оптимизационный проход, выполняющий свёртку констант и удаление мёртвого кода над плоским промежуточным представлением;

(5) построение инструментированного древовидного промежуточного представления по плоскому;

(6) кодогенерация с виртуальными регистрами;

(7) распределение регистров при помощи последовательного метода, описанного в [18];

(8) кодирование машинных инструкций целевой процессорной архитектуры.

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

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

Выражения в промежуточном представлении VEX могут включать ссылки на временные переменные, применения одной из нескольких сотен предопределённых операций, чтения «гостевых регистров» (регистров целевой машины в терминологии VEX), загрузки из памяти, константы, вызовы вспомогательных подпрограмм (реализованных в виде функций на Си в рамках инструмента анализа), а также тернарные операции if-then-else. Из выражений, в свою очередь, составляются операторы: записи «гостевых регистров», выгрузки в память, присвоения значений временным переменным, оператор атомарного сравнения и замены (CAS), условные переходы на другие адреса в программе и различные аннотации. Временные переменные в рамках единицы трансляции находятся в форме с единичным статическим присваиванием (SSA).

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

Большое количество поддерживаемых примитивных операций и соответствующих типов данных (в том числе с плавающей точкой и векторных) позволяет применять основанные на VEX инструменты к широкому классу программ, что также подчёркивает практическую ориенированность системы Valgrind. Вместе с тем, число таких примитивов приближается к числу инструкций в современных процессорах. Этот факт в совокупности с тем, что список операций фиксирован и одинаков для всех целевых процессорных архитектур, приводит к достаточно сложному промежуточному представлению и усложнению алгоритмов анализа.

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

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

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

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

Система динамического инструментирования Pin

Система Pin [19], разрабатываемая совместно корпорацией Intel и университетом Колорадо, реализует инфраструктуру для динамического инструментирования программ. Поддерживаются процессорные архитектуры х86, х86-64, ARM и Itanium [20]. Основными заявляемыми достоинствами Pin являются скорость работы (как самой системы, так и инструментированного кода) и прозрачность, которую авторы понимают так: инструментированная программа работает ровно с теми же адресами и данными, что и оригинальная.

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

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

Интересно, однако, отметить подход к полносистемному инструментированию, применяемый в системе PinOS [21], которая является расширением Pin. Система PinOS работает во взаимодействии с монитором виртуальных машин Xen [22], предоставляя возможность проводить инструментирование всех выполняющихся в изучаемой системе программ, в том числе ядра и других компонентов операционной системы. При этом не требуется модифицировать код операционной системы: изоляцию и взаимодействие обеспечивает Xen. При помощи PinOS могут быть получены полносистемные трассы без использования симулятора, а посредством виртуализации, что является интересной альтернативой при необходимости проведения «неинвазивной» трассировки.

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

Система анализа BitBlaze

Система анализа бинарного кода BitBlaze [23] состоит из большого числа взаимодействующих компонентов, в совокупности реализующих подходы к решению различных задач, связанных с безопасностью ПО. Среди основных компонентов системы выделяются компонент статического анализа Vine, динамического анализа TEMU и смешанного конкретного и символьного выполнения Rudder. Поверх этих базовых компонентов работают различные подключаемые модули. В контексте данной работы наибольший интерес представляют компоненты Vine и TEMU.

Компонент статического анализа Vine разбивается на две части. Первая часть (front end) обеспечивает разбор подаваемого на вход исполняемого бинарного файла программы, выделение в нём секций кода и перевод кода в язык промежуточного уровня Vine IL. Вторая часть (back end) работает над промежуточным языком и обеспечивает построение различных принятых в компиляторах представлений, а также предоставляет возможность выполнения над ними базовых видов анализа. Более сложные анализы работают поверх этих результатов и оформляются в виде подключаемых модулей.

В качестве целевых процессорных архитектур Vine поддерживает х86 и ARM. При этом отделение кода от данных производится параллельно с дизассемблировани-ем и базируется на использовании сторонних инструментов и библиотек, в том числе IDA Pro [24] и дизассемблера [25], специально созданного для работы с запутанным бинарным кодом. Далее применяется библиотека VEX, входящая в состав средства динамического инструментирования Valgrind [16], особенности которой были описаны выше. Авторы BitBlaze также отмечают как недостаток отсутствие в представлении

VEX выписанных в явном виде побочных эффектов инструкций. Далее это представление переводится в язык Vine IL, где такие эффекты представлены явно.

Язык Vine IL достаточно лаконичен. В качестве базовых типов в нём рассматриваются 1-, 8-, 16-, 32- и 64-разрядные регистры, а также ячейки памяти. Для ячеек памяти явно указывается порядок байтов (little endian, big endian) и тип регистра, при помощи которого адресуется эта ячейка (то есть, фактически, размер адреса). На базе этих типов в языке рассматриваются либо конкретные числовые значения перечисленных размеров, либо значения в памяти, записываемые как пары {паi —> nvi,na2 —>• nv2,...}, где в каждой паре первое число соответствует адресу, а второе — записанному значению. Выражения в языке не имеют побочных эффектов и составляются из констант, предопределённых унарных и бинарных операций, приведений типов, объявлений временных переменных, а также операций load и store, осуществляющих доступ к памяти. Интересной особенностью операции store является то, что она (как и все остальные подвыражения) не имеет побочных эффектов: выражение meml = store (memO, а, у) возвращает новое состояние памяти meml, полученное из memO добавлением (или заменой) пары а —> у. Операторы языка позволяют выполнять присваивания, осуществлять условные и безусловные передачи управления и сообщать о достижении особых точек в программе, таких как точка её окончания или точка системного вызова.

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

На рисунке 2.1 приведён результат перевода в язык Vine IL инструкции целочисленного сложения ADD ЕАХ, 1 процессорной архитектуры х86.

1 tmpl = ЕАХ;

2 ЕАХ = ЕАХ + 1;

3 CF:regl_t = (ЕАХ < tmpl);

4 tmp2 = cast(low, ЕАХ, reg8_t);

5 PF = (¡cast(low, ((((tmp2 » 7) Л (tmp2 »6)) Л ((tmp2 » 5)

6 Л (tmp2 » 4) ) ) л ( ( (tmp2 » 3) л (tmp2 » 2) ) л ( (tmp2 » 1)

7 л tmp2)))), regl_t);

8 AF = (1 == (16 & (ЕАХ A (tmpl л 2))));

9 ZF = (EAX == 0);

10 SF = (1 == (1 & (EAX » 31)));

11 OF = (1 == (1 & (((tmpl л (2 л OxFFFFFFFF))

12 & (tmpl л EAX)) » 31)));

Рис. 2.1: Представление инструкции ADD EAX, 1 (x86) в Vine IL

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

1. Проведение конкретной интерпретации с заданным пользовательским вводом.

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

3. Построение представления с единичным статическим присваиванием (SSA) [26].

4. Построение срезов программы методом чоппинга [27], что позволяет локализовать код определённого алгоритма на основе знаний о его входных и выходных данных.

5. Проведение компиляторных оптимизаций, в том числе нумерации значений, распространения констант и удаления мёртвого кода. Кроме того, может проводиться анализ возможных значений переменных VSA [28].

6. Генерация эквивалентного Си-кода, где чтения и записи памяти моделируются как обращения к глобальному массиву.

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

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

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

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

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

Компонент динамического анализа TEMU, входящий в систему BitBlaze, основан на полносистемном симуляторе QEMU. Этот компонент, так же, как и Vine, имеет модульную архитектуру. Модули расширения TEMU могут в режиме online-анализа обрабатывать различные интересные с точки зрения модуля расширения ситуации, которые фиксирует ядро TEMU. К таким ситуациям относятся ситуации уровня операционной системы, такие как создание нового процесса, загрузка и выгрузка динамических модулей и т. п. В то время, как подобная информация уровня операционной системы крайне интересна для анализа сложных систем, сам по себе online-анализ не позволяет в полной мере производить восстановление алгоритмов.

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

Следует также отметить, что выполнение под управлением QEMU (и, как следствие, TEMU) может быть достатчно легко определено изнутри анализируемой системы, что дополнительно ограничивает круг программ, к которым оказывается применимым подход BitBlaze.

Система анализа ВАР

В системе ВАР (Binary Analysis Platform) [29] развиваются идеи и подходы, предложенные в компоненте Vine системы BitBlaze. Так же, как и Vine, система может быть разделена на две части: front end, обеспечивающая трансляцию бинарного кода целевой машины в промежуточный язык; и back end, реализующая различные алгоритмы анализа. Основное отличие в первой части заключается в отказе от использования библиотеки VEX в качестве промежуточного шага построения представления на промежуточном языке. Кроме того, дизассемблирование в ВАР всегда осуществляется при помощи линейного прохода по секциям кода программы. Система ВАР на настоящий момент поддерживает только программы для архитектуры х86.

Промежуточный язык системы ВАР крайне близок к Vine IL. Из значимых изменений следует отметить добавленную поддержку переключения порядка байтов в памяти во время работы программы, что теоретически возможно в процессорах семейства ARM, но на практике почти не используется. Наиболее важный вклад ВАР в части промежуточного языка находится в теоретической плоскости: в [30] формально специфицирована операционная семантика операторов промежуточного языка. На основании этих результатов в ВАР развиваются виды анализов, связанные с автоматическим построением предикатов для верификации программ.

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

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

Система анализа CodeSurfer

CodeSurfer [32] — коммерческая интерактивная среда для изучения исходного кода на языках Си и Си++, разрабатываемая компанией GrammaTech. Среди основных возможностей среды можно выделить следующие.

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

2. Анализ зависимостей по данным: для заданного оператора возможен просмотр цепочек зависимостей по данным, проходящих через него. Кроме того, CodeSurfer позволяет построить граф зависимостей [33] для каждой функции в программе. При этом проводится и анализ указателей, что позволяет в части случаев рассматривать и зависимости, проходящие через операции разыменования.

3. Анализ путей в программе: компонент Path Inspector позволяет проверять условия на возможные последовательности операторов в программе (например, что функция инциализации некоторой библиотеки вызывается раньше, чем какая-либо ещё её функция, вдоль всех возможных в программе путей).

Среда CodeSurfer предоставляет также API для реализации сторонних модулей расширения. В частности, на базе CodeSurfer построена система автоматического поиска ошибок CodeSonar, также разработанная в GrammaTech.

В результате совместного проекта GrammaTech с университетом Висконсина в CodeSurfer была добавлена поддержка анализа бинарного кода процессорной архитектуры х86 в виде компонента CodeSurfer/x86 [34,35]. Построение промежуточного представления программы в этом случае происходит в несколько этапов.

Сначала бинарный код программы анализируется при помощи интерактивного дизассемблера IDA Pro [24], в результате чего происходит первоначальное выделение

сегментов кода и данных в программе и построение первого приближения графа потока управления. Далее работает анализ VSA [28], который для каждой абстрактной ячейки памяти в каждой точке программы строит приближенное сверху множество её возможных значений. Эти значения выступают как источник дополнительных данных для пополнения графа потока управления рёбрами, соответствующими переходам по вычисляемым адресам, и соответствующими базовыми блоками. Для вновь обнаруженных частей программы также проводится анализ VSA. Для получения более точных результатов параллельно с анализом VSA проводятся анализ составных типов ASI [36] и анализ аффинных отношений между значениями в различных абстрактных ячейках ARA.

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

Среди ограничений предлагаемого авторами CodeSurfer и CodeSurfer/x86 подхода с точки зрения задачи восстановления алгоритма отметим следующие.

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

2. Источником для построения графа потока управления программы является только её статический образ, что означает невозможность прямой работы с программами, содержащими динамически изменяемый код.

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

Система интроспекции Virtuoso

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

Эти программы выполняются под управлением симулятора (^ЕМи [12], и снимаются их трассы в терминах представления ТСй. В каждой трассе производится минимальная предобработка: из них исключается код обработчиков аппаратных прерываний, а вызовы функций выделения и освобождения памяти заменяются на соответствующие аннотации. Далее выполняется динамический слайсинг по методу Корела и Ласки [38], в результате чего выделяются подтрассы, соответствующие непосредственно процессу получения, например, имени исполняемого файла, соответствующего заданному идентификатору процесса. В данной работе, единственной из всех рассмотренных, в процесс анализа включён шаг объединения нескольких трасс. Объединение происходит в три этапа:

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

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

3. Выполняется замыкание Ш, описанное в [38]: все операции, которые присутствуют только в части рассматриваемых подтрасс, добавляются и в результирующий слайс, и строится ещё один динамический слайс по зависимостям таких операций, который также включается в рассмотрение.

1 tinclude <windows.h>

2 #include <psapi.h>

3 tpragma comment(lib, "psapi.lib")

4 tinclude "vmnotify.h"

5

6 int main(int arge, char **argv)

7 {

8 char *name;

9 HANDLE h;

10 DWORD pid = atoi(argv[1]);

11 name = (char *) malloc(1024);

12 vm_mark_buf_in(&pid, 4);

13 vm_mark_buf_in(Sname, 4);

14 h = OpenProcess(PROCESS_QUERY_INFORMATION, 0, pid);

15 GetProcessImageFileName(h, name, 1024);

16 vm_mark_buf_out(name, 1024);

17 return 0;

18 }

Рис. 2.2: Пример исходной программы для Virtuoso

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

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

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

(1) отсутствие поддержки динамически изменяемого кода (в частности, предлагаемый авторами алгоритм объединения трасс требует существенной переработки для снятия этого ограничения);

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

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

2.3 Выводы

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

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

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

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

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

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

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

2.3 Выводы

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

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

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

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

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

Глава 3

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

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

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

Анализ начинается с подготовки исходных данных (раздел 3.1). Далее производится построение графового представления, объединяющего информацию об исследуемой системе из исходных трасс (раздел 3.2). После этого происходит трансляция кода в машинно-независимое представление (раздел 3.3), на базе которого производится выделение той части кода, которая относится к изучаемому алгоритму (раздел 3.4). При этом применяются оптимизационные проходы, упрощающие полученное представление (раздел 3.5), и, наконец, результат представляется в виде, пригодном для просмотра аналитиком (раздел 3.6).

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

1. Для переходов по вычисляемым адресам построение множества всех возможных целевых адресов может оказаться затруднительным. В общем случае необходимо провести анализ множества возможных значений адресного выражения, подобный VSA [28], причём вообще говоря такой анализ возвращает не точное множество возможных адресов, а некоторое его надмножество.

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

Если анализ решено продолжать, то подготавливаются дополнительные трассы. Эти трассы добавляются к исследуемому набору, и процедура повторяется сначала. Вопрос целенаправленного выбора входных данных для новых трасс также выходит за рамки настоящей работы. Отметим лишь, что одним из успешно применяемых в настоящее время подходов является использование символьного выполнения [40] для подбора таких значений входных данных, которые гарантированно увеличивают покрытие за счёт изменения направления одного из ветвлений в программе. Такой подход реализован, например, в инструментах анализа Avalanche [41] и S2E [42]. Реже для подбора параметров может использоваться и фаззинг — метод «грубой силы», рассматривающий исследуемую систему как чёрный ящик [43]. Из-за значительных затрат на получение большого количества трасс и отсутствия гарантии улучшения покрытия применимость фаззинга в задаче восстановления алгоритма существенно ограничена.

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

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

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

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

3. Полнота: в соответствующем трассе промежутке времени процессор не выполнял иных инструкций, кроме содержащихся в шагах.

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

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

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

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

Уточним, что адрес ас1с1г[ь(гЦ понимается как значение счётчика инструкций перед выборкой инструкции тзп[ьЩ. В большинстве процессоров на момент выполнения инструкции это значение будет смещено на величину вгге^пвп^]]. Адрес аМг\р^\, как правило, будет виртуальным, за исключением случаев, когда исследуемая система не использует виртуальную память. Тогда работа будет происходить с физическими адресами.

Заключение

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

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

Основные особенности метода согласованного анализа композиции бинарных трасс, отличающие его от близких подходов, таковы:

1) возможность использования в итеративном сценарии, когда в рассмотрение постепенно добавляются новые трассы;

2) поддержка одновременной работы со всеми процессами и потоками выполнения анализируемой системы;

3) отсутствие ограничений на природу анализируемого кода: программы в анализируемой системе могут произвольным образом динамически изменять как свой код, так и код других программ; кроме того, поддерживается и изменение кода в результате ОМА-транзакций, инициированных различными устройствами, входящими в состав вычислительной системы;

4) метод позволяет получить представление о природе динамической модификации кода программы посредством построения её эволюционного графа, размеры которого могут рассматриваться как одна из метрик сложности программы.

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

1) поддержка широкого спектра процессорных архитектур за счёт гибкого формирования набора примитивных операций, через которые выражается семантика машинных инструкций;

2) поддержка возможности моделирования семантики не только пользовательских, но и системных инструкций;

3) возможность быстрого добавления поддержки новых процессорных архитектур и расширенных наборов инструкций за счёт применения текстовых спецификаций на разработанном в рамках диссертации языке;

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

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

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

1. Снятие технических ограничений, перечисленных в разделе 4.3, а также реализация алгоритмов построения машинно-независимых листингов (в более полном объёме) и машинно-независимых блок-схем.

2. Дополнение разработанных спецификаций машинных инструкций расширенными наборами инструкций, в том числе поддержка векторных операций (наборы инструкций SSE в х86, NEON в ARM).

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

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

4. Дальнейшее повышение уровня представления алгоритма на основе анализов, используемых в декомпиляторах [59,60], вплоть до машинно-независимой деком-пиляции в Си-подобный язык или язык виртуальной машины ЬЬУМ [31]. Сюда также относятся задачи восстановления составных типов, выделения функций и структурного анализ потоков управления для восстановления высокоуровневых конструкций.

Список литературы диссертационного исследования кандидат физико-математических наук Соловьев, Михаил Александрович, 2013 год

Литература

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.

6. Довгалюк Павел. Детерминированное воспроизведение процесса выполнения программ в виртуальной машине // Труды Института системного программирования РАН. Москва, 2011. Т. 21. С. 123-132.

7. Intel® 64 and IA-32 Architectures Software Developer's Manual. 2012. URL: http://download.intel.com/products/processor/manual/325462.pdf.

8. ARMv6-M Architecture Reference Manual. 2010. URL: http://infocenter.arm.com/help/topic/com.arm.doc.ddi0419c/index.html.

9. Programming Environments Manual for 32-Bit Implementations of the PowerPC™ Architecture. 2005. URL: http://www.freescale.com/files/product/doc/MPCFPE32B.pdf.

10. MIPS64™ Architecture For Programmers Volume I: Introduction to the MIPS64™ Architecture. 2001. URL: ftp://ftp.ece.lsu.edu/pub/koppel/ee4720/mips64vl.pdf.

11. MIPS64™ Architecture For Programmers Volume II: The MIPS64™ Instruction Set. 2001. URL: ftp://ftp.ece.lsu.edu/pub/koppel/ee4720/mips64v2.pdf.

12. Bellard F. QEMU, a fast and portable dynamic translator / USENIX. 2005.

13. Cifuentes C., Van Emmerik M., Ramsey N. The design of a resourceable and retar-getable binary translator // Reverse Engineering, 1999. Proceedings. Sixth Working Conference on / IEEE. 1999. P. 280-291.

14. Ung D., Cifuentes C. Machine-adaptable dynamic binary translation // ACM SIG-PLAN Notices. 2000. Vol. 35, no. 7. P. 41-51.

15. Cifuentes C., Sendall S. Specifying the semantics of machine instructions // Program Comprehension, 1998. IWPC'98. Proceedings., 6th International Workshop on / IEEE. 1998. P. 126-133.

16. Nethercote N., Seward J. Valgrind: a framework for heavyweight dynamic binary instrumentation // ACM Sigplan Notices. 2007. Vol. 42, no. 6. P. 89-100.

17. Nethercote N., Mycroft A. Redux: A dynamic dataflow tracer // Electronic Notes in Theoretical Computer Science. 2003. Vol. 89, no. 2. P. 149-170.

18. Traub O., Holloway G., Smith M. D. Quality and speed in linear-scan register allocation. ACM, 1998. Vol. 33.

19. Pin: building customized program analysis tools with dynamic instrumentation / Chi-Keung Luk, Robert Cohn, Robert Muth, Harish Patil, Artur Klauser, Geoff Lowney, Steven Wallace, Vijay Janapa Reddi, Kim Hazelwood // ACM SIGPLAN Notices / ACM. T. 40. 2005. C. 190-200.

20. Intel® Itanium® Architecture Software Developer's Manual. 2010. URL: http:// www.intel.com/content/dam/doc/manual/itanium-architecture-vol-l-2-3-4-reference-set-manual.pdf.

21. Bungale P. P., Luk C.-K. PinOS: a programmable framework for whole-system dynamic instrumentation // Proceedings of the 3rd international conference on Virtual execution environments / ACM. 2007. P. 137-147.

22. Xen and the art of virtualization / P. Barham, B. Dragovic, K. Fraser, S. Hand, T. Harris, A. Ho, R. Neugebauer, I. Pratt, A. Warfield // ACM SIGOPS Operating Systems Review. 2003. Vol. 37, no. 5. P. 164-177.

23. BitBlaze: A new approach to computer security via binary analysis / D. Song, D. Brumley, H. Yin, J. Caballero, I. Jager, M. G. Kang, Z. Liang, J. Newsome, P. Poosankam, P. Saxena // Information systems security. Springer, 2008. P. 1-25.

24. IDA Pro - Interactive Disassembler. URL: https://www.hex-rays.com/products/ida/ index.shtml.

25. Static disassembly of obfuscated binaries / C. Kruegel, W. Robertson, F. Valeur, G. Vi-gna // Proceedings of the 13th USENIX Security Symposium. 2004. P. 255-270.

26. Muchnick S. S. Advanced Compiler Design & Implementation. Morgan Kaufmann Publishers, 1997.

27. Jackson D., Rollins E. J. Chopping: A generalization of slicing: Tech. Rep.: : DTIC Document, 1994.

28. Balakrishnan G., Reps T. Analyzing Memory Accesses in x86 Executables // Proceedings of the 13th International Conference on Compiler Construction, CC. 2004. P. 5-23.

29. BAP: a binary analysis platform / D. Brumley, I. Jager, T. Avgerinos, E. J. Schwartz // Computer Aided Verification / Springer. 2011. P. 463-469.

30. Brumley David, Jager Ivan, Schwartz Edward J., Whitman Spencer. The BAP Handbook. URL: http://bap.ece.cmu.edu/doc/bap.pdf.

31. Lattner Chris, Adve Vikram. LLVM: A compilation framework for lifelong program analysis & transformation // Code Generation and Optimization, 2004. CGO 2004. International Symposium on. 2004. C. 75-86.

32. Anderson P., Zarins M. The CodeSurfer software understanding platform // Program Comprehension, 2005. IWPC 2005. Proceedings. 13th International Workshop on / IEEE. 2005. P. 147-148.

33. Ferrante J., Ottenstein K. J., Warren J. D. The program dependence graph and its use in optimization // ACM Transactions on Programming Languages and Systems (TOPLAS). 1987. Vol. 9, no. 3. P. 319-349.

34. CodeSurfer/x86—a platform for analyzing x86 executables / G. Balakrishnan, R. Gruian, T. Reps, T. Teitelbaum // Compiler Construction / Springer. 2005. P. 250254.

35. Reps T., Balakrishnan G., Lim J. Intermediate-representation recovery from low-level code // Proceedings of the 2006 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation / ACM. 2006. P. 100-111.

36. Ramalingam G., Field J., Tip F. Aggregate structure identification and its application to program analysis // Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages / ACM. 1999. P. 119-132.

37. Virtuoso: Narrowing the semantic gap in virtual machine introspection / B. Dolan-Gavitt, T. Leek, M. Zhivich, J. Giffin, W. Lee // Security and Privacy (SP), 2011 IEEE Symposium on / IEEE. 2011. P. 297-312.

38. Korel В., Laski J. Dynamic program slicing // Information Processing Letters. 1988. Vol. 29, no. 3. P. 155-163.

39. Collberg C., Thomborson C., Low D. Manufacturing Cheap, Resilient, and Stealthy Opaque Constructs // Principles of Programming Languages 1998, POPL'98. 1998. P. 184-196.

40. King J. C. Symbolic Execution and Program Testing // Commun. ACM. 1976. Vol. 19, no. 7. P. 385-394.

41. Исаев И. К., Сидоров Д. В. Применение динамического анализа для генерации входных данных, демонстрирующих критические ошибки и уязвимости в программах // Программирование. Москва, 2010. № 4. С. 51-67.

42. Chipounov V., Kuznetsov V. S2E: A Platform for In Vivo Multi-Path Analysis of Software Systems // Proceedings of the 16th Intl. Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS. 2011.

43. Саттон Майкл, Грин Адам, Амини Педрам. Fuzzing: исследование уязвимостей методом грубой силы. Санкт-Петербург: Символ-Плюс, 2009.

44. Fraser С. В., Irving R. W., Middendorf М. Maximal Common Subsequences and Minimal Common Supersequences // Information and Computation. 1996. Vol. 124, no. 2. P. 145-153.

45. Edgar R. C., Batzoglou S. Multiple sequence alignment // Current opinion in structural biology. 2006. Vol. 16, no. 3. P. 368-373.

46. Needleman S. В., Wunsch C. D. A General Method Applicable to the Search for Similarities in the Amino Acid Sequence of Two Proteins // Journal of Molecular Biology. 1970. Vol. 48, no. 3. P. 443-453.

47. ReTrace: Collecting Execution Trace with Virtual Machine Deterministic Replay / M. Xu, V. Malyugin, J. Sheldon, G. Venkitachalam, B. Weissman, V. Inc // Proceedings of the 3rd Annual Workshop on Modeling, Benchmarking and Simulation, MoBS. 2007.

48. Два способа организации механизма полносистемного детерминированного воспроизведения в симуляторе QEMU / К. Батузов, П. Довгалюк, В. Кошелев, В. Пада-рян // Труды Института системного программирования РАН. Москва, 2012. Т. 22. С. 77-94.

49. The next 700 slicing criteria / M. Harman, S. Danicic, Y. Sivagurunathan, D. Simpson // Second UK Workshop on Program Comprehension. 1996.

50. Weiser M. Program Slicing // Software Engineering, IEEE Transactions on. 1984. no. 4. P. 352-357.

51. Agrawal H., Horgan J. R. Dynamic Program Slicing // ACM SIGPLAN Notices. 1990. Vol. 25, no. 6. P. 246-256.

52. Allen F., Rosen В. K., Zadeck K. Optimization in compilers. 1992. URL: http://www.cs.ucr.edu/ gupta/teaching/553-07/Papers/value.pdf.

53. Briggs P., Cooper K. D., Simpson L. T. Value numbering // Software-Practice and Experience. 1997. Vol. 27, no. 6. P. 701-724.

54. Aho A. V., Ganapathi M., Tjiang S. W. Code Generation Using Tree Matching and Dynamic Programming // ACM Transactions on Programming Languages and Systems (TOPLAS). 1989. Vol. 11, no. 4. P. 491-516.

55. GCC. URL: http://gcc.gnu.org/.

56. Cygwin. URL: http://www.cygwin.com/.

57. ASProtect. URL: http://www.aspack.com/asprotect.html.

58. Программа Crack Me. URL: http://crackmes.de/users/fornix/fornixs_crackme_2_-bug_fixed/.

59. Cifuentes C., Gough K. J. Decompilation of binary programs // Software: Practice and Experience. 1995. Vol. 25, no. 7. P. 811-829.

60. Mycroft A. Type-based decompilation (or program reconstruction via type reconstruction) // Programming Languages and Systems. 1999. P. 208-223.