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

РОССИЙСКАЯ АКАДЕМИЯ НАУК СИБИРСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ ДИНАМИКИ СИСТЕМ И ТЕОРИИ УПРАВЛЕНИЯ

На правах рукописи - -УДК: 681.3.06

-У

I I О <J <-

Хмельнов Алексей Евгеньевич

Язык FlexT для спецификации бинарных форматов

данных.

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

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата технических наук.

Иркутск - 2000

Работа выполнена d Институте динамики систем и теории управления (ИДСТУ) Сибирского отделения Российской академии наук (СО РАН).

Научный руководитель: чл.-к. РАН С.Н. Васильев

Официальные оппоненты: д.т.н., профессор A.B. Петров,

■ к.ф.-м.н., доцент В.В. Братищенко

Ведущая организация: Иркутский государственный университет

Защита состоится б июля 2000 г. в 15j0 часов на заседании диссертационного совета Д 003.64.01 в ИДСТУ СО РАН по адресу:

664033, г. Иркутск, ул. Лермонтова, 134,

зал заседаний Учёного совета ИДСТУ СО РАН, ком. 407

С диссертационной работой можно ознакомиться в библиотеке ИДСТУ СО РАН, а также на странице Р1ехТ в Интернете по адресу http://monster.icc.ru/~alex/FlexT.

Автореферат разослан "_" июня 2000 г.

И.о. учёного секретаря диссертационного совета,

д.т.н.

Яаая з,v2»~ 0[\г п с О

Общая характеристика работы

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

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

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

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

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

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

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

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

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

Апробация работы. Результаты диссертационной работы докладывались на конференциях по информатике: III Международный симпозиум "Интеллектуальные системы" (ИНТЕЛС'98, Псков, 1998), The 3rd IMACS International Multiconference on Circuits, Systems, Communications and Computers (CSCC'99), а также на семинарах ИДСТУ СО РАН по информатике.

Публикации. Основные результаты диссертации опубликованы в 4 печатных работах.

Структура и объём работы. Диссертационная работа состоит из введения, четырёх глав, заключения, литературы и приложения. Список литературы содержит 30 наименований. Основной текст изложен на 99 страницах машинописного текста, полный объём диссертационной работы 138 страниц. Работа включает 22 рисунка и 12 таблиц.

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

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

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

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

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

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

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

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

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

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

PTypelnfо = "TTypelnfo;

TTypelnfo = record

Kind: TTypeKind; Name: ShortString;

{TypeData: TTypeData} end;

PTypeData = ~TTypeData; TTypeData = packed record case TTypeKind of

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

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

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

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

Особенности предлагаемого механизма определения типов состоят в ^пользовании следующих конструкций:

> Составляющие переменного размера: поддерживаются поля записей и элементы массивов переменного размера, который может зависеть от содержимого элемента данных.

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

Каждый тип имеет свойство Size (Размер). Свойства могут задаваться конкретным значением при определении типа либо некоторым выражением, которое вычисляет значение данного свойства через значения и/или свойства вложенных элементов данных сложного типа, а также, может быть, через значения параметров типа. Некоторые правила для вычисления свойства Размер могут автоматически добавляться компилятором, если они не указаны явно. Это касается, например, случая, когда известен размер всей записи и всех её полей, кроме последнего. Параметры в объявлении типа предоставляют ту информацию, которую необходимо указать дополнительно при использовании (вызове) данного типа. Выражения в языке оцениваются в ленивом режиме, т.е. они вычисляются только при необходимости получения значения параметра или свойства типа. В некоторых случаях это позволяет избежать переполнения стека. Выражения вычисляются в контексте некоторого типа, ссылка на этот тип в выражении обозначается при этом ':' <Имя> означает ссылку на параметр или свойство <Имя> данного типа. Механизм параметризации типов позволяет описывать зависимости между элементами данных.

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

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

TRecTbl(Cnt,Base) array[@:Cnt] of PRec(@:Base) Здесь параметр в тип PRec передаётся позиционно. Другой пример: PSecData(Kind,Sz) ^TSecData(@:Kind,@:Sz) TSection (Sz) struc

TSectionType subsection Word iMod

PSecData(Kind=@.subsection) lfo ulong cb raw[] rest ends:lfo:Sz=@.cb] Здесь при описании поля lfo записи TSection используется передача фактических параметров по имени, причём параметр Kind передаётся непосредственно в вызове типа PSecData, а значение параметра Sz задаётся в блоке утверждений.

Программа на FlexT состоит из нескольких видов блоков определений, в которых определения разделяются переводом строки. Основные блоки определений:

• Блок констант:

'CONST' nl

{<Имя константы> ' = ' <Int Ехрг> ';', nl}*

• Блок типов:

'TYPE' ['BIT'] nl

{<Имя типа> <Определение типа>, nl}* содержит определения типов. Признак BIT указывает, что все определяемые здесь типы будут иметь битовое, а не байтовое размещение.

• Блок данных:

'DATA' [<Блок>] nl

(<Int Ехрг> «Эпределение типа> <Имя>, nl}* содержит информацию о переменных, размещённых в блоке памяти <Блок>.

• Блок кода:

'CODE' ['(' <Имя типа кода> ')'] [<Блок>] nl {<Int Ехрг> <Имя>, nl}* содержит адреса и названия точек входа в блоке памяти <Блок>. При указании имени типа кода этот код разбирается в соответствии с указанным типом данных, описывающим кодирование машинной команды и признаки команд, завершающих код (таких, как RET или JMP), по умолчанию используется код процессоров Intel 80x86. Кроме блоков определений, стоит упомянуть конструкции программы ' INCLUDE' <Имя файла> nl для включения содержимого другого файла и ASSERT <Int Expr> '; ' для задания логических утверждений, которые должны выполняться, если файл действительно относится к рассматриваемому формату.

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

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

'NUM' {' + 'Г-'|} 'С <Ехрг> ')' , который позволяет указать размер типа и является ли число знаковым. Также имеется ряд предопределённых типов: byte, int, long и т.д., которые просто являются предопределёнными вызовами конструктора NUM, например, тип int можно определить: int NUM - (2)

!) Перечислимый тип позволяет поставить в соответствие некоторым значениям имена или термы (вариант 3). Конструктор: 'ENUM' [<Имя типа>] {

' Г {<Имя> [ ' =' <Int Expr>] , ','} ')' I

['=']<Expr> ';' I

'FIELDS' ' (' ' «¡Определения полей> ')' 'OF' '(' {<Имя> ['(' {<Имя поля>, ','}+ ')'] ['=' <Int>] , ','}')'

}

имеет три варианта:

1. В круглых скобках могут перечисляться пары <Имя>=<1ш Ехрг>, если 1=1 < IntExpr > опущено, то имени сопоставляется предыдущее значение +1. Начальное значение равно 0.

2. Если круглых скобок нет или стоит знак '=', то указывается выражение для сопоставления значению строки.

3. Ключевое слово 'FIELDS' указывает на перечисление термов, которое позволяет интерпретировать значения типа не просто как константы, а как терм с параметрами - битовыми полями. Этот тип удобно использовать для описания кодирования машинных команд в стиле New Jersey Machine Code Toolkit (NJMCTK).

Если <Имя типа> опущено, то используется тип Byte.

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

'STRUC' NL

{СОлределение типа> <Имя поля>,ЫЬ}* 'ENDS'

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

4) Вариант. Тип составляющей определяется в зависимости от значения его параметра - выбранного случая. Поддерживаются три типа вариантов: с числовыми и строковыми значениями, а также по перечислению термов. Синтаксис:

'CASE' <Expr> 'OF'

{<Список констант>':' < Определение Tnna>,NL}*

['ELSE' < Определение типа> NL]

'ENDC'

где ССписок констант> определяется как в традиционных языках программирования.

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

5) Проверка, в отличие от варианта, использует для выбора типа содержимого условия корректности (блок assert) предполагаемых типов содержимого. Синтаксис:

'TRY'

(<Имя случая>':' < Определение Tnna>,NL}*

'ENDT1

Типы проверяются в порядке перечисления. <Имя случая> используется для ссылок на тип содержимого в выражениях.

6) Массив состоит из переменного числа однотипных элементов. Размер массива может ограничиваться либо заданием числа элементов, либо заданием размера, либо условия на последний элемент (как с ASCIIZ строкой). Синтаксис:

'ARRAY' [ '[' [<Ехрг>] ']' ] 'OF' «Определение типа> {'?' <Условие> '!'<Определение типа>] | <3начение>|}

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

7) Сырые данные служат для отображения блока данных, про которые ничего не известно, кроме их размера, в виде шестнадцатеричного дампа. Синтаксис:

'RAW '['[<Int Expr>]']' ['AT' < Int Expr> ';'] Значение в скобках определяет размер блока и может быть опущено, чтобы, например, задать этот размер в блоке утверждений сложного типа, содержащего данный тип. Второе выражение задаёт базовый адрес.

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

■ALIGN' <Int Expr> ['AT' < Int Expr> ';'] Значение первого выражения должно быть степенью 2. Оно задаёт границу выравнивания. Второе выражение задаёт базу выравнивания; если оно опущено, то выравнивание происходит относительно начала блока памяти.

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

Таким образом, элемент данных может являться адресным блоком. При этом может быть указано его адресное пространство, виртуальный адрес в этом пространстве и виртуальный размер. При ■ объявлении типа данных указателя может бьгть'задано адресное пространство, в которое он ссылается. Немного упрощённый синтаксис указателя:

'л' сОпределение типа> ['NIL' {'=' <Expr> | ':' <Expr> |

'-'}] ['NEAR' ['=' <Имя типа>] <Ссылка на блок> ] [','

'REF1 '=' <Ехрг> ';'] После 'NIL' может либо указываться конкретное значение ' = ' <Ехрг>, соответствующее отсутствию ссьшки, либо условие ': ' <Ехрг> для проверки на отсутствие ссылки, либо то, что любое значение надо рассматривать, как ссылку ('-'). По умолчанию, в качестве Nil рассматривается значение, равное 0. ' NEAR' означает, что ссылка идёт в конкретный блок, иначе она рассматривается как виртуальный адрес в текущем адресном пространстве. <Имя типа> означает, что размер указателя равен размеру данного типа. Если адрес ссылки не совпадает с целочисленным значением базового типа, то после 'REF можно указать выражения для вычисления адреса.

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

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

'CODES' 'OF' <Тип инструкций '?'<Стоп выражение> [

'!'<Тип последней инструкции> ] ';1 Таким образом, кодирование отдельной машинной команды может описываться любыми конструкциями языка FlexT, а условие для определения команд с безвозвратной передачей управления задаётся стоп-выражением в типе CODES. Это условие используется впоследствии при разборе блоков кода дизассемблером FlexT, являющимся пока достаточно примитивным, т.е. не использующим никакую другую информацию о семантике машинных команд.

Примитивизм дизассемблера проявляется, в основном, в его неспособности находить части кода, управление на которые передаётся через косвенные переходы, например, коды виртуальных методов. Этот недостаток в достаточной для практического использования степени компенсируется механизмами описания данных языка FlexT, которые позволяют указать расположение структуры данных, содержащих ссылки на код. Например, при использовании описаний типов данных RTTI Delphi и указании адресов таких структур для классов форм в блоке DATA удаётся разобрать практически весь прикладной код программы на Delphi.

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

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

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

Для представления в памяти информации об определённых в спецификации на языке Р1ехТ типах данных в коде интерпретатора используется иерархия классов, базовым классом в которой является тип TDataType. Этот класс определяет ряд методов, которые задают: способ настройки параметров и свойств типа после его определения, вид значения типа (число, строка и т.д.); способы получения квалификатора составляющей по её смещению или по её ¡Гомеру, вычисления размера, извлечения целочисленного и строкового значений; выполнения некоторой вложенной процедуры на всех составляющих 'итератор); вызова типа №ной составляющей, проверки условий корректности типа, автоматической генерации имени, инициализаций значений свойств

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

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

В простейшем случае весь файл с данными некоторого формата может рассматриваться как один блок памяти, при этом для указания положения переменных в таком файле используются физические адреса, т.е. смещения от начала файла. Такими свойствами обладает большинство форматов, описанных на FlexT в настоящее время. Однако, некоторые форматы и, в частности, практически все форматы исполняемых и объектных файлов, устроены сложнее, так что их нельзя качественно описать без использования механизма вложенных блоков памяти и виртуальных адресных пространств. Так, большинство форматов исполняемых файлов не только содержит информацию о виртуальных блоках, но и указатели в виртуальное адресное пространство из полей переменных физического адресного пространства, например, адрес точки входа в заголовке файла. В наиболее общем случае адресное пространство может содержать несколько виртуальных блоков, а каждый виртуальный блок может иметь в качестве носителя несколько физических блоков, каждый из которых содержит образ памяти некоторого интервала виртуальных адресов. Физический блок имеет, кроме виртуального адреса, также и физический адрес, который, в свою очередь, может быть не только файловым адресом, но и адресом в некотором другом виртуальном адресном пространстве. Для поддержания работы с виртуальными адресными пространствами и указателями в них в интерпретаторе FlexT используются типы данных TAbstrBlock и TAbstrPtr. TAbstrPtr - это пара (Bl, Of s), где В1 является указателем на абстрактный блок TAbstrBlock, а Of s - смещением в этом блоке. Абстрактный указатель имеет ряд методов для доступа к данным, на которые он ссылается и, в частности, для: получения соответствующих указателю физического и виртуального адресов, проверки на Nil и установки в Nil, определения максимального размера данных, получения

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

При определении формата файла используется комбинированная стратегия: учитывается как расширение имени файла, так и его содержимое. По умолчанию, расширению <Ext> соответствует файл с описанием формата <Ext>. rfh. Кроме того, существует специальный файл описания расширений REF.CFG с информацией о связи расширений и файлов с описаниями форматов. Для проверки соответствия данных файла некоторому формату используется информация, содержащаяся в блоках утверждений. Выбирается первое описание, у которого все утверждения истинны. Кроме общего описания формата, некоторому файлу может соответствовать и "личное" описание, которое должно содержаться в том же каталоге, где находится этот файл, иметь то же имя и расширение . réf. Это описание может потребоваться для объявления дополнительных структур данных и адресов процедур, которые не являются частью описания формата и были обнаружены в результате изучения содержимого конкретного файла. Процесс исполнения программы можно разделить на следующие шаги: 1) поиск и загрузка описания формата; 2) загрузка "личного" описания файла; 3) прослеживание указателей; 4) дизассемблирование; 5) отображение результата.

В программных системах, использующих интерпретатор FlexT, был применён ряд решений, которые были разработаны автором и аналоги которых не приходилось встречать в других программных системах, хотя полностью поручиться за их уникальность невозможно. К таким решениям можно отнести технологию размеченных потоков данных и способ отображения информации о перемещаемых адресах в шестнадцатеричном дампе. Все разработанные программы поддерживают вывод результата в различные текстовые форматы (просто текст, RTF, HTML, TeX), кроме того, программа РЕ Explorer реализует интерактивный просмотр результатов с возможностью гипертекстового перемещения, поиска строк и адресов и т.д. Использование технологии размеченных потоков позволяет решить все эти задачи при помощи одной процедуры вывода результата в размеченный поток. Такое многообразие способов применения процедуры отображения результатов разбора достигается за счёт того, что процесс записи строк текста в поток сопровождается дополнительной информацией об отображаемых данных. Каждый поток может по-своему интерпретировать эту дополнительную информацию: часть игнорировать, а другую часть использовать, например, для выбора шрифта при выводе текста.

В четвёртой главе рассматриваются вопросы использования языка FlexT. Описывается работа программ, в состав которых входит интерпретатор языка: разбор файлов в программе Bin View, удалённая обработка файлов в программе WWWBinView, просмотр 32-разрядных файлов Windows в программе РЕ Explorer. Далее рассматриваются примеры описаний форматов: файла класса Java-машины и кодирования машинных команд процессора Z-80 (Intel-

8080). После этого рассматривается использование описаний RTTI Delphi при дизассемблировании программ, написанных на Delphi, а также опыт реконструкции 32-разрядных объектных файлов Delphi (DCU).

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

С использованием программы BinView был реконструирован формат 32-разрядных объектных файлов Delphi (DCU). Это стало возможным благодаря лёгкости проверки спецификаций на реальных данных и наличию генератора файлов с известной семантикой (компилятора Delphi). Тело цикла восстановления формата можно разбить на следующие этапы: 1) анализ результатов разбора тестовых файлов; 2) формирование гипотезы о виде некоторой структуры данных или её уточнение; 3) генерация тестовых файлов для проверки гипотезы; 4) уточнение спецификации на FlexT; 5) разбор тестовых файлов.

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

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

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

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

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

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

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

Основные публикации по теме диссертации.

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

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

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

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