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

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

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

Оглавление

Введение

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

1.1. Описание контекста задачи

1.2. Определение формата данных

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

2.1 Анализ сетевого трафика

2.2 Статический анализ кода

2.3 Динамический анализ кода

2.4 Анализ входящих и исходящих данных

2.5 Восстановление автомата протокола

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

2.7 Выводы

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

3.1 Определения терминов

3.2 Анализ помеченных данных

3.3 Алгоритм восстановления границ полей

3.4 Анализ циклов

3.5 Алгоритм поиска развёрнутых циклов по графу потока управления

3.5.1 Анализ алгоритма оптимизации

3.5.2 Алгоритм поиска шаблонов на графе потока управления

3.6 Алгоритмы восстановления семантики

3.6.1 Поиск полей длины

3.6.2 Поиск полей разделителей

3.6.3 Поиск полей указателей

3.6.4 Поиск ключевых полей

3.6.5 Поиск флаговых полей

3.6.6 Поиск связанных полей

3.6.7 Поиск шаблонов на графе зависимостей

3.7 Восстановление группировки полей в виде последовательностей и записей

3.8 Использование спецификаций функций для уточнения восстановленного формата

3.9 Восстановление формата данных, вводимых по частям

3.9.1 Уточнение понятия сообщение

3.9.2 Особенности анализа файлов

3.9.3 Виртуальный буфер

3.10 Анализ шифрованного трафика

3.11 Выделение сессий обмена

4. Метод обобщения и уточнения восстанавливаемого формата данных

4.1 Обобщение восстановленного формата

4.2 Объединение нескольких форматов

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

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

4.2.3 Построение обобщающего дерева

5. Реализация разработанной системы восстановления форматов

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

5.2 Проверка реализованной системы

5.2.1 Проверка методов восстановления формата

5.2.2 Проверка алгоритма обобщения формата

5.2.3 Проверка системы объединения форматов

Заключение

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

Приложение 1. Описание промежуточного представления формата сообщения

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

Введение

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

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

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

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

привести отсутствие аварийных завершений и передач управления на произвольные участки кода: такие ситуации представляют собой уязвимости и могут использоваться злоумышленниками для исполнения зловредного кода. Рост количества вариантов входных данных представляет собой экспоненту от длины этих данных, и полный перебор, в большинстве случаев, невозможен даже при достаточно небольших размерах входных данных. Знание формата данных позволяет значительно снизить количество вариантов для перебора, так как позволяет исключить класс данных, не подходящих под описанный формат. Примерами систем тестирования по методу фаззинга являются Packet Vaccine[8] и ShieldGen[9],

Для предотвращения эксплуатации обнаруженных, но ещё не устранённых разработчиком ПО уязвимостей, используются программы фильтрации входного трафика, такие как Shield [10]. Для предотвращения несанкционированного доступа по сети используются системы обнаружения и предотвращения вторжений (IDS/IPS), такие как Snort[ll] и Вго[12]. Во всех этих системах выполняется разбор сетевых пакетов с использованием технологии глубокого исследования пакетов DPI[13] для оценки потенциальной опасности их содержимого. Для использования этой технологии также необходимо описание структуры сетевых пакетов.

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

Ещё один важный класс задач, для решения которых знание сетевого протокола критически важно - анализ вирусного ПО. Многие вирусы используют собственные сетевые протоколы уровня приложения для передачи конфиденциальных данных с заражённого компьютера. В последнее время широкое распространение получил новый класс вирусного ПО, которое позволяет формировать из заражённых компьютеров крупномасштабные сети - ботнеты. Примерами таких программ могут служить MegaD[15] и agobot[16]. Эти программы активно используют сеть для взаимодействия между заражёнными машинами и управляющим компьютером с целью организации массовых

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

Восстановление формата "вручную" является весьма сложной и ресурсоёмкой задачей, требующей высокой квалификации, а получаемые результаты могут быть не вполне точны. Так, трудоёмкость ручного анализа закрытых, в то время, протоколов SMB фирмы Microsoft и OSCAR фирмы AOL составила несколько человеко-лет [17, 18]. Таким образом, проблема автоматизации восстановления форматов сетевых сообщений и файлов является актуальной.

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

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

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

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

перспективных направлений исследований является динамический подход на основе полносистемной трассировки, который не подвержен перечисленным проблемам.

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

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

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

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

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

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

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

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

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

1. Международные конференции "РусКрипто" (Москва, 2009 и 2010 гг.)

2. Научно-технические конференции "Методы и технические средства обеспечения безопасности информации" (Санкт-Петербург, 2010 и 2011 гг.).

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

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

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

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

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

• анализ помеченных данных,

• анализ циклов,

• алгоритмы восстановления полей, записей и последовательностей,

• алгоритмы восстановления семантики.

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

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

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

Заключение

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

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

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

• Использование битовой гранулярности представления данных, что, повысило точность и, в частности, позволило анализировать поля-флаги.

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

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

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

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

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

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

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

• Разработан алгоритм уточнения полученного формата за счёт анализа нескольких сообщений того же типа.

Проводимые исследования были поддержаны грантом РФФИ 11-07-00450-а. Среди направлений дальнейших работ по данной тематике можно выделить два наиболее важных:

• Разработка специализированных алгоритмов анализа формата исходящих данных на основе работ, описанных в разделе 2.4,

• Разработка подходов к решению второй части задачи восстановления протоколов, а именно - автоматическое восстановление автомата протокола на основе работ из раздела 2.5.

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

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

1. В.А. Падарян, А.И. Гетьман. Автоматизация динамического анализа бинарного кода. // Материалы конференции "РусКрипто'2009". Москва, 2-5 апреля 2009

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

3. Гетьман А.И., Падарян В.А. Методика восстановления формата данных. Материалы конференции "РусКрипто'2010". Москва, 2-5 апреля 2010

4. А.И. Гетьман, Ю.В. Маркин, В.А. Падарян и др. Восстановление формата данных. // Труды Института системного программирования, том 19, 2010, с. 195214.

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

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

7. А.И. Аветисян, А.И. Гетьман. Восстановление структуры бинарных данных по трассам программ. Труды Института системного программирования, том 22, 2012, с.95-118.

8. X. Wang, Z. Li, J. Xu, M. К. Reiter, С. Kil, and J. Y. Choi. Packet vaccine: black-box exploit detection and signature generation. In Proceedings of the 13th ACM Conference on Computer and Communication Security(CCS'06), pages 37-46, New York, NY, USA, 2006. ACM Press.

9. W. Cui, M. Peinado, H. J. Wang, and M. Locasto. Shield-gen: Automatic data patch generation for unknown vulnerabilities with informed probing. In Proceedings of 2007 IEEE Symposium on Security and Privacy, Oakland, CA, May 2007.

10. H. J. Wang, C. Guo, D. R. Simon, and A. Zugenmaier. Shield: vulnerability-driven network filters for preventing known vulnerability exploits. In Proceedings of ACM SIGCOMM'04, pages 193-204, 2004.

11. The SNORT network intrusion detection system, http://www.snort.org.

12.V. Paxson. Bro: A System for Detecting Network Intruders in Real-Time. Computer Networks, 31 (23-24):2345-2463, 1999.

13. DPI: Deep Packet Inspection Motivations, Technology, and Approaches for Improving Broadband Service Provider ROI, Radisys Whitepaper, September 2010, http://go.radisys.com/rs/radisys/images/paper-dpi-motivations.pdf дата обращения 26 марта 2013

14. A. Tongaonkar, R. Keralapura, A. Nucci. Challenges in Network Application Identification. Proceedings of the Large-Scale Exploits and Emergent Threats (LEET), 2012

15. J. P.John, A.Moshchuk, S.D.Gribble, A.Krishnamurthy. Studying spamming botnets using Botlab. In Symposium on Networked System Design and Implementation, Boston, MA, April 2009.

16. Know your Enemy: Tracking Botnets - Bot-Commands. http://www.honeynet.org/papers/bots/botnet-commands.html дата обращения 26 марта 2013

17. How Samba was written, http://www.samba.org/ftp/tridge/misc/french_cafe.txt дата обращения 26 марта 2013

18. Protocol Reverse Engineering and Application Dialogue Replay. http://bitblaze.cs.berkeley.edu/protocol.html дата обращения 26 марта 2013

19. Сетевые модели OSI и TCP/IP. http://www.quizful.net/post/osi_tcpip_layers дата обращения 26 марта 2013

20. Network Driver Interface Specification 5.1 http://msdn.microsoft.com/en-us/library/ff556916.aspx дата обращения 22 апреля 2012

21. Wireshark. http://www.wireshark.org дата обращения 26 марта 2013

22. Е. Dolgova and A. Chernov. Automatic reconstruction of data types in the decompilation problem. Programming and Computer Software, 35(2):105 -119, Mar. 2009.

23. Z. Lin, X. Zhang. Deriving Input Syntactic Structure from Execution and Its Applications. Purdue Technical Report CSD TR #08-006, 2008.

24. W. Cui, J. Kannan and H. Wang. Discoverer: Automatic Protocol Reverse Engineering from Network Traces. The 16th USENIX Security Symposium, 2007, pages 199-212.

25. M. Shevertalov and S. Mancoridis. A reverse engineering tool for extracting protocols of networked applications. In Proc. of the Working Conf. on Reverse Engineering 2007,pages 229-238.

26. Y. Wang , X. Li ,J. Meng , Y. Zhao , Z. Zhang ,and L. Guo. Biprominer: Automatic Mining of Binary Protocol Features. In Proceeding of 12th International Conference on Parallel and Distributed Computing, Applications and Technologies, 2011, pages 179184.

27. J. Antunes, N. Neves, and P. Verissimo. Reverse engineering of protocols from network traces. In Proc. of the Working Conf. on Reverse Engineering (WCRE), 2011, pages 169-178

28. Y. Wang, Z. Zhang , D. Yao, B. Qu, L. Guo. Inferring protocol state machine from network traces: a probabilistic approach. In Proceeding of the 9th international conference on Applied cryptography and network security (ACNS), 2011, pages 1-18

29. T. Krueger , N. Kramer , K. Rieck. ASAP: Automatic Semantics-Aware Analysis. Proceedings of the international ECML/PKDD conference on Privacy and security issues in data mining and machine learning (PSDML), 2010, pages 50-63

30. "A. Trifilo, S. Burschka, E. Biersack. Traffic to Protocol Reverse Engineering. In Proc. of Computational Intelligence for Security and Defense Applications (CISDA), 2009, pages 1-8.

31. J. Lim, T. Reps, B. Liblit. Extracting Output Formats from Executables. In Proceedings of the 13th Working Conference on Reverse Engineering (WCRE), 2006, pages 167 — 178.

32. Z. Lin, X. Jiang, D. Xu, X. Zhang. Automatic Protocol Format Reverse Engineering through Context-A ware Monitored Execution. In Proceedings of the 15th Annual Network and Distributed System Security Symposium (NDSS), 2008.

33. J.Caballero, H. Yin, Z. Liang, D. Song. Polyglot: Automatic Extraction of Protocol Message Format using Dynamic Binary Analysis. In Proceedings of the 14th ACM Conference on Computer and Communications Security, Alexandria,VA,October 2007.

34. G. Wondracek, C. Kruegel, E. Kirda, P. Milani. Automatic Network Protocol Analysis. In Proceedings of the 15th Annual Network and Distributed System Security Symposium(NDSS), February 2008.

35. W. Cui, M. Peinado, K. Chen, H. J.Wang, L.Irun-Briz. Tupni: automatic reverse engineering of input formats. In CCS'08: Proceedings of the 15th ACM conference on Computer and communications security, 2008.

36. L. Chen, X. Li. A Survey on Methods of Automatic Protocol Reverse Engineering. Proceedings of the 2011 Seventh International Conference on Computational Intelligence and Security (CIS), 2011, pages 685-689

37. S. B. Needleman and C. D. Wunsch. A General Method Applicable to the Search for

Similarities in the Amino Acid Sequence of Two Proteins. Journal of Molecular Biology, 48(3):443^153, 1970.

38. G. Balakrishnan. and T. Reps. Analyzing memory accesses in x86 executables. In CC,2004.

39. G.Balakrishnan and T.Reps. Recovery of variables and heap structure in x86 executables. Tech. Rep. TR-1533, Comp.Sci. Dept.,Univ. of Wisconsin, Madison, WI, Sept. 2005.

40. J. Newsome, J., D.Song. Dynamic Taint Analysis for Automatic Detection, Analysis, and Signature Generation of Exploits on Commodity Software. In Proceedings of the Network and Distributed System Security Symposium (NDSS), 2005

41. J.Caballero, P.Poosankam, C. Kreibich, D.Song. Dispatcher: Enabling Active Botnet Infiltration using Automatic Protocol Reverse-Engineering. Proceedings of the 16th ACM conference on Computer and communications security (CCS), 2009, pages 621634

42. E. M. Gold. Language Identification in the Limit. Information and Control, vol. 10, no. 5, 1967.

43. D. Angluin. On the complexity of minimum inference of regular sets. Information and Control, 39(3):337-350,1978.

44. Z. Zhang. Mining Protocol State Machines by Interactive Grammar Inference. Proceedings of Digital Manufacturing and Automation (ICDMA), 2012 , pages 524 -527

45.M.E. Deyoung. Dynamic protocol reverse engineering - a grammatical inference approach. PhD Thesis. Ohio: Air Force Institute of Technology, 2008.

46. P.M. Comparetti, G. Wondracek, C. Kruegel, E. Kirda. Prospex: Protocol Specification Extraction. In Proceedings of the 30th IEEE Symposium on Security and Privacy, 2009, pages 110-125

47. P. Jaccard. The Distribution of Flora in the Alpine Zone. The New Phytologist, vol. 11, no. 2, pp. 37-50, 1912.

48. L. Kaufman, P. Rousseeuw. Finding Groups in Data: An Introduction to Cluster Analysis. Wiley, 1990.

49. J. Dunn. Well Separated Clusters and Optimal Fuzzy Partitions. Journal of Cybernetics, vol. 4, 1974.

50. N. R. Pal, J. Biswas. Cluster Validation Using Graph Theoretic Concepts. Pattern Recognition, vol. 30, no. 6, 1997.

51.0. Cicchello, S.C. Kremer. Inducing grammars from sparse data sets: a survey of

algorithms and results. J. Mach. Learn. Res., 4:603-632, 2003. ISSN 1533-7928.

52. M. Bugalho and A.L. Oliveira, "Inference of Regular Languages Using State Merging Algorithms with Search, Pattern Recognition, vol. 38, no. 9, 2005.

53. K. J. Lang. Faster Algorithms for Finding Minimal Consistent DFAs. NEC Research Institute, Tech. Rep., 1999.

54. P. J. McCann, S. Chandra. PacketTypes: Abstract specification of network protocol messages. In SIGCOMM, ACM Press, 2000, pages 321-333.

55.N. Borisov, D. Brumley, H. J. Wang, J. Dunagan, P. Joshi, C. Guo. Generic application-level protocol analyzer and its language. In Proceedings of the 14th Annual Network and Distributed System Security Symposium (NDSS), 2007.

56. R. Pang, V. Paxson, R. Somer, and L. Peterson, binpac: A yacc for writing application protocol parsers. In Proceedings of the Internet Measurement Conference (IMC), 2006, pages 289 - 300.

57.R.Sekar, L.Cavallaro, P.Saxena. Anti-taint-analysis: Practical evasion techniques against information flow based malware defense. Technical report, Stony Brook University, 2007.

58.Korel В., Laski J. Dynamic program slicing. Information Processing Letters, Vol. 29, Issue 3, 1988, pages. 155-163.

59. Тихонов А. Ю., Падарян В. А.. Применение программного слайсинга для анализа бинарного кода, представленного трассами выполнения. Материалы XVIII Общероссийской научно-технической конференции «Методы и технические средства обеспечения безопасности информации», 2009, стр. 131.

60. А. Ахо, Р.Сети, Д.Ульман. Компиляторы. - М.: Изд. дом «Вильяме», 2001.

61. V. Sreedhar, G. Gao, and Y. Lee. Identifying loops using DJ graphs. ACM Transactions on Programming Languages and Systems (TOPLAS), 18(6), 1996.

62. A. Slowinska, T. Stancescu, H. Bos. Howard: A Dynamic Excavator for Reverse Engineering Data Structures. In Proceedings of the Network and Distributed System Security Symposium (NDSS), 2011

63. GCC. http://gcc.gnu.org дата обращения 22 апреля 2012

64. Z. Lin, X. Zhang, D. Xu. Automatic Reverse Engineering of Data Structures from Binary Execution. Proceedings of the Network and Distributed System Security Symposium(NDSS), 2010

65. Portable Executable and Object File Format Specification http://download.microsoft.eom/download/e/b/a/ebal 050f-a31 d-436b-9281 -92cdfeae4b45/pecoff.doc дата обращения 22 апреля 2012

66. J.Lee, Т. Avgerinos, D. Brumley. TIE: Principled Reverse Engineering of Types in Binary Programs. In Proceedings of the Network and Distributed System Security Symposium (NDSS), 2011

67. Bitmap Storage http://msdn.microsoft.com/en-us/library/ddl 83391(VS.85).aspx дата обращения 22 апреля 2012

68. JPEG. http://www.w3.org/Graphics/JPEG/itu-t81.pdf дата обращения 22 апреля 2012

69. Z.Wang, X.Jiang, W.Cui, andX.Wang. ReFormat: Automatic reverse engineering of encrypted messages. In European Symposium on Research in Computer Security, Saint-Malo, France, September 2009.

70.N.Lutz. Towards revealing attacker's intent by automatically decrypting network traffic. Master's thesis, ETH,Zurich, Switzerland, July 2008

71. J. Kannan, J. Jung, V. Paxson, and С. E. Koksal. Semi-Automated Discovery of Application Session Structure. In Proceedings of the Internet Measurement Conference (IMC), 2006, pages 119- 132

72. H. Shacham, M. Page, B. Pfa, E.-J. Goh, N. Modadugu, D. Boneh. On the effectiveness of address-space randomization. In Proceedings of the 11th ACM conference on Computer and communications security (CCS), 2004, pages 298-307

73. M. A. Beddoe. Network Protocol Analysis using Bioinformatics Algorithms. Technical report, The Protocol Informatics Project, 2005

74. Использование средства NSlookup.exe. http://support.microsoft.com/kb/200525 дата обращения 26 марта 2013

75. PictView. http://www.pictview.com/ дата обращения 26 марта 2013

Приложение 1. Описание промежуточного представления формата сообщения

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

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

• открывающей или закрывающей скобкой

• строкой, задающей поле (field)

• строкой, задающей запись (structure)

• строкой, задающей последовательность (sequence)

Тип structure

Строка, задающая группировку полей в запись, имеет следующий формат id:buf fer;

где id - идентификатор вершины дерева buffer - тип вершины

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

Строка, задающая отдельное поле, имеет следующий формат

id:field:fieldSize:fieldType:fieldVals[:fieldRefId];

id - идентификатор вершины дерева

field - тип вершины

fieldSize - размер поля (для виртуальных полей размер задается в байтах в шестнадцатеричной форме, для всех остальных полей fieldSize принимает значение uint8, uintl6 или uint32)

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

если поле-флаг размером 1 байт нужно разделить на блоки 1, 2, 5 бит, то значение fieldType должно быть flag(l+2+5). В случае отсутствия информации, вместо конкретного размера блока битов указать символ '?'.

fieldVals - множество возможных значений поля в шестнадцатеричной форме или empty если о возможных значениях поля ничего не известно

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

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

id:sequence:sequenceSize:sequenceChild[:seqRefId] ; id - идентификатор вершины дерева sequence - тип вершины

sequenceSize - размер последовательности в байтах или '?', если размер последовательности определяется некоторым полем

sequenceChild - информация о типе потомка последовательности; если потомок-поле, то значение соответствует его размеру (uint8, uintl6 или uint32); если потомок - структура, то в sequenceChild записывается идентификатор этой структуры

seqRef Id - дополнительный атрибут, задается в том случае, когда размер последовательности определяется полем с идентификатором seqRefld Редактирование промежуточного представления

При редактировании промежуточного представления нужно придерживаться следующих правил:

• Каждая вершина (кроме полей-потомков последовательностей) должна иметь уникальный идентификатор

• Промежуточное представление должно иметь следующую структуру

• Необходимо использовать правильные скобочные выражения

• Пустые строки не допускаются

• Пробел и символ табуляции не допускаются

• В промежуточном представлении должна быть ровно одна вершина с базовым типом buffer

• Вершина может ссылаться только на вершину с базовым типом field

• Вершина не может ссылаться на саму себя

• Каждая вершина должна иметь ровно одного родителя (потомком последовательности может быть только вершина, которая не является ничьим потомком)

• Все размеры, задаваемые в виде шестнадцатеричных чисел, должны быть отличными от нуля

• Для виртуальных полей размер задается в байтах в шестнадцатеричной форме, для всех остальных полей fieldSize принимает значение uint8,uintl6 или uint32

• Для последовательности нельзя задать размер и задать ссылку на вершину, определяющую размер этой последовательности

• В текущей реализации для последовательности нельзя не задать размер и не задать ссылку на вершину, определяющую размер этой последовательности

• Если размер последовательности задается полем длины, то значение этого поля должно определяться до того, как определена последовательность

• Если размер последовательности задается разделителем, то строка, задающая этот разделитель, должна сразу следовать за строкой, задающей последовательность

• Если задан размер последовательности, то он должен быть кратен размеру потомка этой последовательности; при этом размер потомка последовательности должен быть определен

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

• Нужно учитывать, что на каждый символ '?' приходится как минимум один бит.

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

Пример правильного промежуточного представления

О:buffer; {

l:field:uintl6:simple:empty; 2:field:uint8:flag(1+1+1+4+1):empty; 3:field:uint8:flag(4+2+1+1):empty; 4:field:uintl6:length:empty; 5:field:uintl6:length:empty; 6:field:uintl6:simple:empty; 7:field:uintl6:simple:empty;

8:sequence:?:10 : 4;

9:sequence:?:11:5; }

10:structure; {

12:sequence:?:24:13;

13:field:uint8:delimiter:0;

14:field:uintl6:simple:empty;

15:field:uintl6:simple:empty; }

11:structure; {

16:field:uint8:flag(6+2),pointer:empty:2 6

17:field:uint8:pointer:empty:2 6;

18:field:uintl6:key:!5,!6,12,!33;

19:field:2:virtual:empty;

20:field:uint32:simple:empty;

21:field:uintl6:simple:empty;

22:sequence:?:25:23;

23:field:uint8:delimiter:0; }

24:structure; {

26:field:uint8:flag(6+2),length:empty;

27:sequence:?:uint8:26; }

25:structure; {

28:field:uint8:flag(6+2),length:empty;

2 9:sequence:?:uint8:28; }