Размещено на http://www.allbest.ru/

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ

"НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ

"ВЫСШАЯ ШКОЛА ЭКОНОМИКИ"

ФАКУЛЬТЕТ КОМПЬЮТЕРНЫХ НАУК

МАГИСТЕРСКАЯ ДИССЕРТАЦИЯ

Создание базы спецификаций форматов данных и их уточнение на основе анализа набора трасс программ

Соболев Сергей Александрович

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

проф. В.А. Семенов

Москва 2020



Аннотация

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

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



Abstract

Protocol reverse engineering is the process of extracting data format specifications and states from network traffic or implementations. Such specifications very useful in security-related tasks, for example, black-box fuzzing, malware neutralization, to perform deep packet inspection to detect and prevent intrusions. Use of protective mechanisms by developers prevents manual protocol analysis.

This graduation paper offers an automated way to solve the problem of data format specifications recovery based on a dynamic approach to the analysis of binary code by program traces. The advantages and disadvantages of alternative approaches to solving the problem are considered. Methods have been developed and implemented to resolve the disadvantages of the chosen approach and obtain more accurate results.



Содержание

Введение

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

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

2.1 Уточнение формата данных

2.2 Инструмент Netzob

2.3 Инструмент Prospex

2.4 Выводы по главе

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

3.1 Дерево формата данных

3.2 Обобщение формата данных

3.3 Описание доработанного алгоритма Нидлмана-Вунша

3.4 Построение объединенного дерева формата

3.5 Выводы по главе

4. Реализация модуля восстановления формата данных

4.1 Описание системы восстановления формата данных

4.2 Тестирование системы объединения форматов данных

4.3 Выводы по главе

Заключение

Список литературы



Введение

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

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

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

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

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

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

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

Работа проводилась в рамках среды анализа бинарного кода, разрабатываемой в ИСП РАН [4]. В основе данного инструмента лежит подход из комбинации методов статического и динамического анализа. Модульная архитектура среды позволяет разрабатывать в виде отдельных компонентов различные виды анализа.

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

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

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

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

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

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

2. Реализован алгоритм сериализации (десериализации) восстановленных форматов данных в (из) JSON для унифицированного представления получаемых результатов;

3. Разработан прототип базы данных форматов для долговременного хранения получаемых результатов, а также реализован API для взаимодействия с хранилищем;

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

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

Диссертационная работа состоит из введения, четырех глав и заключения.

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

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

В главе 3 содержит описание алгоритмов для решения задачи восстановления формата данных:

· Восстановление структуры и семантики данных;

· Обобщение формата данных;

· Объединение нескольких обобщенных форматов данных;

В данном разделе описывается модифицированный подход для решения задачи объединения форматов данных на основе существующих методов.

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



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

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

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

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

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

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

1. Восстановить структуру и семантику сообщений из бинарных трасс целевого ПО;

2. Получить обобщенное представление всех полученных конкретных форматов данных;

3. Произвести уточнение всех обобщенных форматов данных в один для получения универсального формата данных.

Данная диссертационная работа посвящена решению задачи уточнения формата данных: описание основного алгоритма и реализация соответствующих инструментальных средств в виде подключаемого модуля для среды анализа бинарного кода разрабатываемой в ИСП РАН.



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

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

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

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

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

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

2.1 Уточнение формата данных

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

Рассмотрим работу [6], в которой предложен базовый подход для решения данной задачи с использованием алгоритма Нидлмана-Вунша [13]. Оригинальная версия данного алгоритма используется для выравнивания двух нуклеотидных последовательностей.

В качестве примера работы адаптированного алгоритма Нидлмана-Вунша рассмотрим два сообщения протокола HTTP "GET /index.html HTTP/1.0" и "GET / HTTP/1.0". Результатом выравнивания будет:

GET /index.html HTTP/1.0

GET /__________ HTTP/1.0

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

Рисунок 1 Построение матрицы сравнения с обратным проходом

Алгоритм Нидлмана-Вунша является алгоритмом динамического программирования на матрицах и сравнивает две символьных последовательности. Он состоит из трёх стадий: вычисление схожести, суммирование и обратный проход. Алгоритм работает на двух матрицах S (матрица совпадений) и M (матрица сравнения) размера , где m - длина первой последовательности, а n - второй. Первая последовательность располагается по вертикали слева, вторая по горизонтали сверху. На рисунке 1 приведён пример матрицы M для сообщений протокола HTTP, описанных выше.

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

На втором этапе заполняется матрица сравнения M. Изначально все ячейки аналогично матрице S заполнены нулями. Проход начинается с ячейки (1, 1) и каждое значение вычисляется по следующей формуле:

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

На третьем этапе осуществляется обратный проход по матрице M - формирование результирующей последовательности. Проход начинается с правой нижней точки (m, n), на каждом следующем шаге выбирается ячейка с максимальным значением: слева, сверху или по диагонали влево-вверх. При совпадении значений приоритет выше у диагональной ячейки. Алгоритм выравнивания выполняется по следующим правилам:

1. Если движение было по диагонали, то никаких действий не требуется;

2. Если движение было влево - добавить пропуск во вторую последовательность на соответствующую позицию;

3. Если движение было вверх - добавить пропуск в первую последовательность на соответствующую позицию.

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

2.2 Инструмент Netzob

Рассмотрим работу [7], в которой используется подход к восстановлению формата данных на основе анализа сетевого трафика. Реализованный инструмент имеет название Netzob и находится в свободном доступе.

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

Алгоритм восстановления формата данных состоит из следующих шагов:

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

2) С помощью расширенного базового алгоритма Нидлмана-Вунша (на основе работы [6]) определяется общая семантика сообщений в кластерах;

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

Рассмотрим каждый шаг более подробно (Рисунок 2).

Рисунок 2 Обзор системы Netzob

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

1) Долгая пауза в сессии без сообщений, обычно, указывает на конец действия;

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

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

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

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

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



Рисунок 3 Пример применения базового и модифицированного Нидлмана-Вунша

Далее вычисляется степень совпадения сообщений (в рамках контекстного кластера) и с помощью алгоритма UPGMA [23], модификация которого позволяет объединить два похожих сообщения (Рисунок 4).

Рисунок 4 Объединение сообщений по степени совпадения с помощью алгоритма UPGMA

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

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

Алгоритм выявления зависимостей состоит из следующих шагов:

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

2) Комбинируются основные характеристики полей, к которым относятся размер, смещение и значение, например, пара (field_1.size, field_3.value);

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

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

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

2.3 Инструмент Prospex

Рассмотрим инструмент Prospex [10], который использует динамический подход для восстановления формата данных. На рисунке 5 представлена архитектура данного инструмента.

Рисунок 5 Архитектура инструмента Prospex

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

1. Анализ помеченных данных. Цель данного шага заключается в том, чтобы определить границы буфера и определить инструкции, которые обрабатывали конкретный участок данных в нем. Анализ помеченных данных подробно рассмотрен в работе [9];

2. Анализ сессии. На данном этапе среда восстанавливает структуру конкретных сообщений: определяются последовательности (участки переменной длины) и строится иерархическое дерево формата данных;

3. Кластеризация сообщений. После получения определённого набора сообщений, среда выполняет их объединение по общим признакам для получения обобщенного формата данных;

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

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

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

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

· Системные вызовы,

· Вызываемые функции (инструкция call),

· Инструкции, которые участвовали в обработке сообщения.

Далее коэффициент подобия сообщений вычисляется на основе сходства получившихся множеств.

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

1. Формат выходных данных. Если в ответ на сравниваемые сообщения сервер отвечает другими сообщениями, то для вычисления коэффициента подобия необходимо применить первый подход (алгоритм Нидлмана-Вунша) к выходным данным;

2. Взаимодействие с файловой системой. Если в результате получения входных сообщений, сервер начинает взаимодействовать с файловой системой, то для вычисления коэффициента подобия необходимо сравнить системные вызовы (open, close, read, write, mkdir, rmdir и т.п.), возникающие в момент их обработки.

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



2.4 Выводы по главе

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



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

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

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

После того, как буфер локализован в трассе, аналитик производит следующие действия:

1) Определяются границы и размеры полей в результате анализа отдельных инструкций доступа к данным буфера;

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

3) Формирование обобщенного формата данных на основе полученной иерархической структуры данных;

4) Сериализация результата в формат JSON;

5) Сохранение сериализованного формата в базе данных форматов.

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

1) Загрузить из базы данных два обобщенных формата в модуль объединения форматов;

2) Получить объединенный формат данных с помощью доработанного алгоритма Нидлмана-Вунша;

3) Сохранить полученный результат в базе данных форматов;

4) Повторить процедуру объединения с полученным результатом на предыдущем шаге и другим форматом.

Рисунок 6 Общая схема восстановления формата данных

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

3.1 Дерево формата данных

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

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

Каждый узел содержит в себе следующую информацию об элементе буфера:

· Смещение относительно начала буфера;

· Размер данных;

· Тип узла и его атрибуты.

Рисунок 7 Дерево формата данных

На рисунке 7 представлен пример дерева формата данных. Для его построения необходимо произвести анализ структуры данных и анализ семантики данных [2].

В задаче восстановления структуры данных в дереве формата выделяются следующие элементы:

· Поля

· Последовательности

· Структуры

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

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

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

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

· Поля длины

· Поля-флаги

· Поля-разделители

· Поля-указатели

· Ключевые поля

· Виртуальные поля

Поле длины определяет размер некоторой последовательности (Рисунок 7). Если поле задает длину некоторой последовательности, то должны выполняться следующие условия:

1) Данное поле использовалось для проверки условия выхода из цикла обработки последовательности;

2) Условие выхода на всех предыдущих итерациях цикла не выполнялось.

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

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

1) На каждой итерации цикла каждое поле последовательности сравнивается с некоторой константой;

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

3) Поле, которое участвовало в сравнении на последней итерации, объявляется разделителем.

Поля-указатели используются для формирования адреса (смещения) на некоторое другое поле в буфере. Их поиск заключается в анализе способа формирования некоторого числа (адреса) для доступа к другим данным буфера. Рассмотрим пример:

mov EAX, dword ptr [EBX + ECX]

Допустим, в регистре EBX записан адрес начала буфера, а в регистре ECX - значение некоторого другого поля этого же буфера. Тогда в регистр EAX будет записано значение по смещению ECX от начала данных. Поле буфера, значение которого было загружено в регистр ECX, объявляется полем-указателем.

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

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

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

3.2 Обобщение формата данных

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

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



Рисунок 8 Обобщенный формат данных

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

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



Рисунок 9 Обобщение формата с неоднородной последовательностью

На рисунке 9 представлен способ обобщения формата данных с неоднородной последовательностью. Как и в предыдущем примере (Рисунок 8), последовательность зависит от поля длины, однако в процессе восстановления оказалось, что на каждой итерации обрабатывались различные по семантике и размеру элементы этой последовательности. Так как исходная спецификация неизвестна, то алгоритм обобщения предполагает, что на каждой итерации в последовательности может оказаться как поле с длиной 1, так и ключевое поле с длиной 2. Для обозначения неопределенности данные поля сгруппированы с помощью типа вариант. Размер варианта считается неопределенным, если его дочерние элементы имеют различную длину.

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

1) Сформировать множество элементов unkLength в исходном формате, длина которых может быть неопределенной;

2) Для каждого родительского элемента из множества элементов unkLength добавить информацию о том, что значение длины не определено;

3) Для каждого элемента, который расположен после элемента (по смещению) из множества unkLength, добавить информацию о том, что значение смещения не определено;

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

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

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

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

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

3.3 Описание доработанного алгоритма Нидлмана-Вунша

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

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

· Базовый тип (поле, структура, последовательность, вариант),

· Семантика элемента,

· Смещение,

· Размер.

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

· Расширена система бонусов и штрафов с учетом иерархической структуры форматов данных;

· Введена функция для оценки близости элементов (степени совпадения);

· Поддержаны рекурсивные вызовы алгоритма Нидлмана-Вунша для элементов форматов, которые не являются листовыми (последовательности, структуры и варианты).

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

В доработанной версии алгоритма также присутствуют матрицы совпадений S и сравнения M. Каждая матрица имеет размер , где m и n - количество элементов в первом и втором дереве формата соответственно.

Таблица 1

Бонусы и штрафы в доработанной версии алгоритма Нидлмана-Вунша

Случай	Бонус/штраф
Совпадение базового типа	8
Совпадение семантики	2
Совпадение размера	3
Совпадение смещения	3
Несовпадение базового типа	-5
Вставка варианта (пропуск)	-1
Сравнение с вариантом	-2

Матрица S заполняется аналогично базовому варианту алгоритма, но с учетом новой системы бонусов и штрафов (Таблица 1). Значения бонусов и штрафов были получены опытным путем, исходя из свойств сравниваемых элементов. Последние два случая требуют отдельного пояснения. Вставка варианта представляет собой слагаемое w в формуле (1) и является аналогом вставки пропуска в оригинальном алгоритме. Штраф за сравнение с вариантом сделан для того, чтобы ослабить штраф за несовпадение базового типа: если элемент присутствует в варианте, то такие поля будут считаться полностью совпадающими.

Рассмотрим матрицу сравнения M. В модифицированной версии алгоритма ячейка матрицы M содержит следующие данные:

· Степень совпадения,

· Количество бонусов,

· Внутренний указатель,

· Внешний указатель.

Степень совпадения - это числовое поле, которое используется алгоритмом для построения результирующего дерева формата. Данное поле может принимать значение 0, 0.5 или 1.

Определения:

· П_1 - это поддерево, корнем которого (К_1) является текущая вершина дерева 2 (i-ый элемент первой последовательности);

· П_2 - это поддерево, корнем которого (К_2) является текущая вершина дерева 2 (j-ый элемент первой последовательности);

· ДК_1 - дочерние элементы К_1;

· ДК_2 - дочерние элементы К_2.

Алгоритм заполнения:

ЕСЛИ

!(К_1.тип == Вариант) И !(К_2.тип == Вариант) И (П_1 == П_2)

ИЛИ

(К_1.тип == Вариант) И (К_2.тип == Вариант)

ИЛИ

!(К_1.тип == Вариант) И (К_2.тип == Вариант) И (К_1 В ДК_2)

ИЛИ

(К_1.тип == Вариант) И !(К_2.тип == Вариант) И (К_2 В ДК_1)

ТО

M[i][j].степень_совпадения = 1

ИНАЧЕ ЕСЛИ

(К_1.тип == К_2.тип)

ИЛИ

!(К_1.тип == Вариант) И (К_2.тип == Вариант) И !(К_1 В ДК_2)

ИЛИ

(К_1.тип == Вариант) И !(К_2.тип == Вариант) И !(К_2 В ДК_1)

ТО

M[i][j].степень_совпадения = 0.5

ИНАЧЕ ЕСЛИ

!(К_1.тип == К_2.тип)

ТО

M[i][j].степень_совпадения = 0

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

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

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

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

3.4 Построение объединенного дерева формата

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

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

Таблица 2

Алгоритм объединения вершин

Ситуация	Степень совпадения	Действие (создание потомка для текущей вершины)
A и B листовые	0	Создание варианта C с двумя потомками A и B
	0.5	Если у вершины A нет семантики, а у B есть, то B станет новым потомком. Если оба поля - ключевые поля, их возможные значения объединяются. Иначе - создание варианта C с двумя потомками A и B
	1	Любая из вершин A и B становится потомком
A - листовая, B - нелистовая	0	B - структура или последовательность, поэтому создается вариант C с потомками A и B
	0.5	B - вариант, в котором нет вершины A. Необходимо скопировать в B вершину A и сделать B потомком текущей вершины
	1	B - вариант, в котором есть вершина A, тогда B становится потомком текущей вершины
A и B нелистовые	0	Создание варианта C с двумя потомками (поддеревьями) A и B
	0.5	Создается новая нелистовая вершина (такого же типа, как A и B) и становится текущей. Происходит рекурсивный вызов алгоритма и на вход передается другая матрица M, которая находится во внешнем указателе текущей ячейки
	1	Если A и B полностью совпадают (последовательность или структура), то любая вершина становится новым потомком. Если A и B - варианты, то создается вариант C, в котором будут все потомки A и B (повторяющиеся вершины должны быть удалены)

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

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

Рисунок 10 Пример объединения форматов данных

Рассмотрим пример объединения форматов данных (Рисунок 10). В результирующем дереве формата можно отметить следующие изменения:

1) Ключевое поле теперь содержит две константы (0x01 и 0x02), так как в объединяемых форматах значения были различными;

2) В первом дереве формата последовательность содержит поле размером в два байта, во втором дереве - один байт. При объединении создается вариант, элементами которого являются поля из последовательностей первого и второго дерева формата, чтобы показать неоднородность объединяемых элементов;

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

4) Последнее поле помещено в результирующее дерево с помощью варианта, так как оно есть во втором формате, но отсутствует в первом (аналог пропуска в базовом алгоритме Нидлмана-Вунша).

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

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

3.5 Выводы по главе

В данной главе были рассмотрены следующие основные разделы:

1) Восстановления конкретных форматов данных из бинарных трасс программ;

2) Обобщение восстановленных форматов данных;

3) Объединение нескольких обобщенных форматов данных в универсальный формат.

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

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

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



4. Реализация модуля восстановления формата данных

Модуль восстановления формата данных реализован в составе среды анализа бинарного кода, разрабатываемой в ИСП РАН, которая рассматривается в работах [1, 4, 5].

Общая архитектура среды представлена на рисунке 11.

Рисунок 11 Архитектура среды анализа бинарного кода

Среда анализа бинарного кода имеет следующие свойства:

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

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

3) Графический интерфейс для изучения и коррекции восстановленных высокоуровневых данных.

Модуль восстановления реализован на языке программирования C++ [21] с использованием фреймворка Qt [20] для разработки графических интерфейсов.

4.1 Описание системы восстановления формата данных

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

Рисунок 12 Архитектура системы восстановления формата данных

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

...