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

ВВЕДЕНИЕ.

1. Актуальность задачи описания форматов бинарных данных.

2. Пример: разбор файла в формате БВР.

3. Цели и структура работы.

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

ГЛАВЫ.

1. Общие принципы предлагаемого подхода.

1.1. Проблемы обработки данных и способы их решения.

1.2. Спецификация интерпретации и спецификация изменения.

1.3. Требования к языку спецификации.

1.4. Используемые термины.

1.5. Идентификация типов данных, как базовая интерпретация данных.

1.6. Динамические и статические типы данных.

1.7. Использование механизма определения типов данных.

1.8. Необходимые конструкции.

2. Основные элементы языка БьехТ.!.

2.1. Описание синтаксиса.

2.2. Общие особенности.

2.3. Выражения.

2.4. Структура программы.

2.5. Основные конструкторы типов.

2.6. Предопределённые типы.

2.7. Интерфейсы.

2.8. Ограничения предлагаемого подхода.

3. Детали реализации языка БьехТ.

3.1. Механизм вызова типов.

3.2. Вычисление значений параметров и свойств типа по необходимости.

3.3. Представление информации о типах данных.

3.4. Представление информации о переменных.

3.5. Представление информации о блоках памяти.

3.6. Обработка типов данных с битовым размещением.

3.7. Влияние порядка байтов на определения типов.

3.8. Процесс исполнения программы Р1ехТ и автоматическое определение формата файла в программах просмотра.

3.9. Логическая семантика спецификаций форматов.

3.10. Использование размеченных потоков вывода.

3.11. Отображение информации о перемещаемых адресах в шестнадцатеричном дампе.

3.12. Деревья и таблицы решений для индексации перечислений термов.

4. Использование языка FlexT

4.1. Разбор файлов в программе Bin View.

4.2. Удалённая обработка файлов в программе WWWBinView.

4.3. Просмотр 32-разрядных файлов Windows в программе РЕ Explorer.

4.4. Описание формата файла класса Java-машины.

4.5. Описание кодирования машинных команд процессора Z-80.

4.6. Использование описания RTTI Delphi при дизассемблировании программ, написанных на Delphi.:.

4.1. Реконструкция формата 32-разрядных DCU.

1. Актуальность задачи описания форматов бинарных данных.

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

Для того, чтобы отображать содержимое файлов различных форматов, могут использоваться специализированные программы, которые вызываются из универсальной программы просмотра (пример: QuickView в Windows). Для обработки данных одного вида, например, растровых графических файлов, в некоторых программах используются подключаемые динамические библиотеки, предоставляющие определённый набор функций, которые могут быть написаны независимыми производителями для заранее неизвестных форматов файлов (пример: plug-ins в Adobe Photoshop). Также могут существовать готовые статические библиотеки (*.lib) или исходные тексты для работы с некоторыми форматами. Недостатком всех этих подходов является то, что они фиксируют способ обработки данных и скрывают информацию о структуре поддерживаемых форматов, смешивая её в коде со вспомогательными и специализированными операциями. Хотелось бы иметь возможность представления информации о форматах данных в таком виде, который допускает её многоцелевое использование и который бы содержал как можно меньше несущественной, т.е. не относящейся к способу представления данных, информации. Данная работа показывает, что для этих целей может использоваться язык спецификации форматов данных.

Автору неизвестны успешные решения задачи описания форматов бинарных данных. Более того, не приходилось встречать и постановки подобных задач с предлагаемой в данной работе степенью универсальности. Наиболее близкой по постановке является работа [1]. Там автор поставил себе цель описать формат DWG (AutoCAD), а, может быть, и какие-то другие при помощи специального вида контекстно-свободных грамматик, в которых терминальными символами являются примитивные типы данных. К сожалению, данная работа, судя по всему, не увенчалась успехом й сейчас ссылка [1] устарела, а следы этой работы можно найти под именем BFF на сайте [2].

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

По пути такого расширения пошли авторы проекта [3], которые являются признанными авторитетами в вопросах универсальной (независимой от компилятора) декомпиляции. В проекте [3] ставится задача автоматического перевода исполняемых файлов с одной платформы на другую. Для решения этой задачи необходимо уметь считывать во внутреннее представление исполняемые файлы различных форматов. На более старой версии этой страницы находилась ссылка на работу [1], как на единственную известную авторам попытку спецификации форматов бинарных файлов. Эта ссылка сопровождалась замечанием, что "эта грамматика сильно зависит от формата файлов AutoCAD" а и в настоящее время непригодна для решения задачи загрузки файлов". В текущей версии страницы [3] имеется ссылка на собственную работу авторов этой страницы, также названную BFF [4], которая является попыткой развития идей из [1] применительно к поставленной задаче. С использованием спецификации формата файла автоматически генерируется код для считывания в память и запоминания адресов некоторых частей файла, таких, как его заголовок или загружаемый образ памяти. После этого в сгенерированном коде что-то необходимо исправить, а остальное считывание необходимо дописать вручную, т.е. используемые описания не являются полными. Если выразить возможности предложенного в проекте [3] языка в терминах языка FlexT, рассматриваемого в настоящей диссертации, то можно сказать, что там в какой-то степени реализованы всего два конструктора типов: "запись" и "массив", а также поддерживаются динамические адреса переменных, т.е. этих возможностей явно недостаточно для полного описания даже самого простого формата данных.

В заключение этого по необходимости краткого обзора предшествующих работ следует сказать несколько слов о "конвергенции" терминологии и ложных предшественниках. Дело в том, что в данной работе используются такие термины, как "элемент данных", "интерпретация", "абстракция" и т.д., которые могут напомнить невнимательному читателю терминологию проблематики моделирования и описания хранимых данных в технологии баз данных, например, языка CODASYL [5], что может существенно помешать пониманию данной работы. По отношению к таким задачам язык FlexT рассматривает вопросы гораздо более низкого уровня представления информации, чем уровень моделей данных в СУБД, которые не опускаются до описания физического представления данных. Кроме того, при описании моделей данных СУБД рассматриваются только вопросы хранения информации в СУБД, а не способы представления произвольных видов данных. "Конвергенция" терминологии происходит потому, что между описываемыми сущностями возникают похожие отношения (например, как ещё можно назвать составную часть более сложных данных, как не элементом данных?).

Заключение

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

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

2. Разработан интерпретатор языка FlexT и несколько программных систем, использующих этот интерпретатор: программа просмотра файлов произвольных форматов BinView, программа просмотра/дизассемблер исполняемых файлов Windows (формат Portable Executable - COFF) РЕ Explorer, а также ISAPI расширение IIS - WWWBinView для удалённой обработки файлов (подробности - на странице FlexT http://monster.icc.ru/~alex/FlexT).

3. На языке FlexT описано несколько десятков различных форматов файлов. В основном это форматы исполняемых и других файлов, содержащих программный код, что объясняется областью интересов автора. В их числе форматы файлов со следующими расширениями: EXE (MZ,NE,LE), ELF, CLA, TPU, OBJ, BGI, TTF, WAV, BMP, DBF. Конструкции языка использовались при декомпиляции различных программ и описании характерных для конкретных компиляторов форматов данных, например, RTTI Delphi.

4. На примере объектных файлов 32-разрядных версий Delphi (формат DCU) продемонстрирована возможность использования спецификаций на языке FlexT для реконструкции неизвестного формата данных при наличии генератора данных этого формата с известной семантикой. Это стало возможным благодаря лёгкости проверки спецификации формата на FlexT на реальных данных.

Перспективными направлениями развития языка FlexT являются: реализация в нём механизма интерфейсов, дополнение языка средствами спецификации семантики машинных команд, разработка механизмов определения спецификаций редактирования, построение автоматических генераторов кодов на различных языках программирования для обработки форматов данных по их спецификациям, расширение возможностей программы РЕ Explorer для работы с произвольными форматами, оснащение её средствами взаимодействия с подключаемыми модулями (plug-in) для отображения/обработки данных, предоставляющих конкретные интерфейсы.

1. F. Faase. BFF: A grammar for Binary File Formats, http://wwwis.cs.utwente.nl:8080/~faase/BFF, 1996.

2. F. Faase. Binary File Format Definition, http://www.wotsit.org, 1996.

3. Cr. Cifuentes, M. Van Emmerik et all. UQBT A Resourceable and Retargetable Binary Translator, http://www.csee.uq.edu.au/csm/uqbt.html, 1999.

4. Cr. Cifuentes, M. Van Emmerik et all. Binary File Format language, http://www.csee.uq.edu.au/csm/srl/table.htm, 1999.

5. Д. Цикритзис, Ф. Лоховски. Модели данных: Пер. с англ., М.: "Финансы и статистика", 1985.

6. Г. Борн. Форматы данных, К.: "Торгово-издательское бюро BHV", 1995.

7. General Format of .dbf files in Xbase languages, http://www.wotsit.org, 1996.

8. A.E. Хмельное. Язык описания данных FlexT: гибкие типы для описания статических данных // Сб. Третий Международный симпозиум "Интеллектуальные системы".- М.: ООО "ТВК", 1998, С. 150-154.

9. A. Hmelnov, S.Vassilyev. Data description language FlexT: flexible types for description of static data // In: Proc. of The 3rd IMACS International Multiconference on: Circuits, Systems, Communications and Computers (CSCC'99), 1999, P. 1371-1376.

10. A. Hmelnov, S.Vassilyev. Data description language FlexT: flexible types for description of static data // In: Software and Hardware Engineering for the 21th Century (N. Mastorakis, ed.), WSES Press, 1999, P. 146-151.

11. A.E. Хмельнов. Язык описания данных FlexT: использование динамических типов для описания статических данных // Сб. Оптимизация, Управление, Интеллект, №4. Иркутск: ИДСТУ СО РАН, 2000, С. 148-166.

12. В.Н.Агафонов. Спецификация программ: понятийные средства и их организация, Новосибирск:Наука. Сиб. отд-ние, 1990.

13. А.Тей и др. Логический подход к искусственному интеллекту: от классической логики к логическому прграммированию: Пер. с франц., М.: "Мир", 1993.

14. Б.Лисков, Дж.Гатэг. Использование абстракций и спецификаций в разработке программ: Пер. с англ., М.: "Мир", 1989.

15. Borland Intl., Inc. Borland Delphi 3.0. run image, файл . \SOURCE\VCL\TypeInfo .pas, 1997.

16. Т.Сван. Форматы файлов Windows: Пер. с англ. М.:Бином, 1994.

17. K.Mitchell. PARADOX 4.x file formats, http://www.wotsit.org, 1998.

18. Randy Beck. The PARADOX File Structure, http://www.wotsit.org, 1996.

19. Red Hat Software. The Red Hat Package Manager, файл . /docs / format, ftp://ftp^m.org/pub/rpm, http://www.rpm.org, 1998.

20. Clarion BBS. Bulletin #117, Clarion data files, http://www.wotsit.org, 1991.

21. Borland Intl., Inc. Open Architecture Handbook The Borland Developer's Technical Guide, http://www.wotsit.org, 1993.

22. W.Wouters, Windows Bitmap File Format Specifications, http://www.wotsit.org, 1997.

23. T.Lindholm, F. Yellin. The Java Virtual Machine Specification. Addison-Wesley: The Java Series, (http://java.sun.com/docs/books/vmspec/index.html, ftp://ftp.javasoft.com/docs/specs/vmspec.html.zip), 1996.

24. M.J.O'Leary. Portable Executable Format. Документ Microsoft Developer Support, PE.TXT.

25. Microsoft Corp. Microsoft Portable Executable and Common Object File Format Specification, MSDN Library, http://www.microsoft.com/msdn/, 1997.

26. LX Linear executable Module Format Description, http://www.wotsit.org, 1992.

27. Linear Executable Format, http://www.wotsit.org, 1993.

28. Unicode, Inc. The Unicode Standard, Version 3.0, http://www.unicode.org, 1999.

29. N.Ramsey, M.Fernandez. The New Jersey Machine-Code Toolkit, http://www.eecs.harvard.edu/~nr, 1997.

30. Intel. Executable and Linkable Format, http://www.wotsit.org, 1993.

31. Netscape Communications Corp. Client-Side JavaScript Reference, http://developer.netscape.com/docs/manuals/js/client/jsref/, 1999.

32. Н.П.Брусенцов. Микрокомпьютеры, M.: "Наука", 1985.

33. Borland Intl., Inc. Object Pascal Language Guide, 1997.

34. R. Jung. ARJ Technical Information, http://www.wotsit.org, 1993.

35. TrueType format specification, http://www.wotsit.org, 1995.

36. D.E.Knuth, The DVItype processor, http://www.wotsit.org, 1995.

37. Borland Intl., Inc. Borland Delphi 3.0. run image, файл\SOURCE\VCL\classes . pas, 1997.

38. TIS Committee, Tool Interface Standards OMF: Relocatable Object Module Format, Version 1.1., http://www.wotsit.org, 1995.

39. PKWARE. General Format of a ZIP file, http://www.pkware.com/download.html appnote.zip, 1998.

40. А.Филд, П.Харрисон. Функциональное программирование, М.: "Мир", 1993.

41. Microsoft Corp. Microsoft multimedia standards update, http://www.wotsit.org -riff.doc, 1993.

42. Microsoft Corp. Windows Shell API/File Viewers, MSDN Library, http://www.microsoft.com/msdn/, 1997.

43. К.Хоггер. Введение в логическое программирование: Пер. с англ., М.: "Мир", 1988.

44. М. Kifer, G. Lausen, J. Wu: Logical Foundations of Object-Oriented and Frame-Based Languages, Journal of the ACM, 1995, vol. 42, ftp://ftp.infonnatik.uni-freiburg.de/documents/papers/JACMflogic.ps.gz.

45. SunOS, файлы sys/elf* .h, 1997.

46. В.Липский. Комбинаторика для программистов: Пер. с польск. М.:Мир, 1998.

47. А.Е.Хмельнов. Программа для разбора юнитов Delphi 2.0-5.0., http://monster.icc.ru/~alex/DCU/, 2000.