# Обзор темы разбора форматов

[TOC]

## Сфера форматов данных

Данные хранятся и передаются в соответствии с некоторы форматом. Количество различных протоколов неуклонно растет, постоянно появляются новые и новые форматы. В программах, которые с ними работают, возникает необходимость обрабатывать данные в таких форматах.
Можно выделить следующие направления использования форматов:
* **хранение структурированных данных** (докуменеты, изображения и т.д.)
Программы-обработчики занимаются чтением и записью таких форматов. Количество поддерживаемых форматов обычно разнится от одного до нескольких десятков.
*Пример:* формат `.doc` и программа Microsoft Word
* **сериализация и десериализация программных объектов**
Обработчики называются сериализаторами. Их задача — сохранить временно объект с возможностью дальнейшей загрузки обратно в программу. Обработчик работает с одним едиственным (чаще всего бинарным) форматом.
*Пример:* сериализатор `pickle` в Python
* **мониторинг**
На ряду с сетевыми мониторами, обрабатывающими сетевые пакеты, можно рассматривать и различные антивирусы. Здесь разборщик форматов работает сразу с большим набором форматов. Каждый формат описывается некоторым универсальным образом и хранится в базе. Обработчик загружает произвольный формат из базы и начинает разбор данных в соответствии с ним. Протоколы в базу можно добавлять.
*Пример:* Wireshark (поддерживает более 1500 протоколов по умолчанию)
* **фаззинг**
При фаззинге необходимо по имеющемуся описанию формата (и, возможно, тестовому экземпляру данных) генерировать новые данные, используемые для тестирования программ. В этой ситуации необходимо уметь представлять формат в некотором виде, удобном для редактирования человеком и затем генерировать почти случайные данные, соответствующие или почти соответствующие этому формату. Таким образом, здесь не стоит задача разбора, но используется описание формата.
*Пример:* Peach (описание формата в XML-файлах PeachPit)
* **передача данных в интерфейсы**
Некоторые программы принимают и передают параметры и данные интерфейсам других программ, например, в распределенных системах. Соответственно частью их работы является сериализация и десериализация этих значений в соответствии с некоторыми правилами. Формат передаваемых сообщений определяется интерфейсом.
*Пример:* ASN.1
* **бинарные редакторы**
Некоторые редакторы имеют возможность разбирать бинарные данные в соответствии с некоторой грамматикой и строить асбтрактное представление результата. В таком случае само представление является конечной целью. Такая необходимость возникает при изучени/разработке формата или бинарного файла.
*Пример:* [Hexinator](https://hexinator.com/)
* **отладка, реверс-инжиниринг**
*Пример:* [radare2](https://github.com/radareorg/radare2)

В таблице приведены примеры известных форматов:

| | Бинарные | Текстовые |
| ------------------------------- | -------------- | ---------------- |
| *Формат файла* | ELF, GIF, gzip | HTML, YAML |
| *Формат сетевого пакета* | HTTP/2, DNS | SMTP, HTTP, POP3 |
| *Формат сериализованных данных* | BSON, EXI | JSON, XML |

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


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

## Цель

Для большинства форматов разработчиками уже написаны разборщики. Тем не менее новые форматы появляются и вместе с ними появляется необходимость их разбирать. Для описания формата удобно использовать некоторую декларативную форму описания, по которой автоматически бы генерировалась разбирающая этот формат программа. Другими словами, необходим язык описания форматов данных — **data description language (DDL)**.

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

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

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

1. *Условные поля*
Некоторые поля формата описываются как "необязательные" или "варьирующиеся". Наличие или отсутствие такого поля, а также его структура зависит от значения некоторого другого поля — *floating field* и *variable field*. Примером первого служат необязательные заголовки в PE/COFF формате. Пример второго случая — варьирующаяся структура сообщения в протоколе DNS (*DNS answer type*);

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

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

---

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

## Данные

Под *данными* подразумевается произвольный массив символов некоторого алфавита (*слово*). В случае с бинарными данными алфавитом является множество $\{0, 1\}$, в случае с текстовыми — набор поддерживаемых символов.

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

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

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

### Сегменты и поля
Будем предполагать, что данные находятся в буфере.

***Сегмент*** — это некоторое подслово (отрезок) всех данных.

Сегмент определяется двумя индексами в буфере — началом и концом (***start*** и ***end***). Одновременно с этим сегменты можно определять и другой парой чисел: ***offset*** и ***size***, сдвиг и длина сегмента.

Именованные сегменты (которым присвоено некое "имя") можно называть ***полями***.

### Иерархия полей
В древовидной структуре данных имеются отношения вида "родитель-ребенок" между полями. К примеру, поле `message` может иметь дочерние поля `header` и `text`.

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

Эти отношения подразумевают следующие ограничения на границы соответствующих сегментов:
* дочерний сегмент содержится целиком внутри родительского;

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

## Форматы данных

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

В рамках теории формальных языков, бинарный формат данных — это некий язык в двоичном алфавите: $A = \{0, 1\}$. Соответственно, данные — это слова (строки, цепочки символов), которые могут принадлежать языку, или не принадлежать (то есть соответствовать формату или не соответствовать). Как уже указывалось выше, вместо двоичного алфавита чаще рассматривается алфавит байтов $B=\{$`00`, `01`, ..., `AA` $\}$

### Способы задания языков

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

Пример правил грамматики:
1. $S \rightarrow 0S1$
2. $S \rightarrow 10$

Задача разбора строки здесь ставится как задача распознавания слова (принадлежит ли оно языку или нет) и задача восстановления синтаксической структуры — синтаксического дерева.

Грамматики можно классифицировать по виду их правил (иерархия Хомского):
*Тип 0* — неограниченные
*Тип 1* — контекстно-зависимые
*Тип 2* — контекстно-свободные
*Тип 3* — регулярные
Ограничение правил каким-то из этих типов приводит к сужению множества описываемых языков. Наиболее узкое множество — регулярные языки (тип 3) — описываются также регулярными выражениями.

В теории формальных языков существует большое количество написанных алгоритмов построения разборщиков по различным грамматикам. Примеры таковых: LL(k)-, LR-, LALR-анализаторы.

Существуют расширения понятия "грамматика", направленные в том числе на упрощение задания сложных языков. Одним из таких удачных расширений являются *атрибутные грамматики*. В них наряду с правилами, выводящими слова, содержатся правила, описывающие преобразования атрибутов символов. Эти атрибуты в дальнейшем могут быть использованы для проверки слова на свойства, не передаваемые только через синтаксис (грамматическую структуру).

В статье *"Parsing Expression Grammars: A Recognition-Based Syntactic Foundation" (Bryan Ford, Massachusetts Institute of Technology, 2004)* описывается аналогичный подход — распознающие грамматики, позволяющие строить разборщики, работающие за линейное время для любого языка.

В "компьютерном мире" есть устоявшиеся формы записи грамматик, такие как [BNF](https://en.wikipedia.org/wiki/Backus%E2%80%93Naur_form) и ее вариации. Так же существует целый ряд программ, строящий по грамматике в этой (или какой-то другой) форме разборщик: *yacc*, *ANTLR*, и т.д.

### Бинарные форматы

Основное отличие, делающее подход с использованием грамматик неэффективным, заключается в зависимости полей от данных (*data dependence*). Указанные выше конструкции (условные поля и поля переменной длины) требуют интерпретации значений полей и дальнейшего использования этих интерпретированных значений в разборе. Подобная семантика плохо реализуется в рамках грамматик, а иногда и вовсе не реализуется.

Разбор таких бинарных форматов представляет из себя более усложненный синтаксический разбор, зависящий от данных (*dependent parsing*). Именно эти особенности вынуждают отойти от классического подхода описания языков с помощью грамматик и перейти к DDL.

## Выходное представление результатов разбора

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

* программный интерфейс, структура, объект класса *(KaitaiStruct, Spicy)*
* абстрактное внутреннее представление, дерево *(Wireshark, Protosphere)*
* файл некоторого формата разметки, например PDML, XML, JSON *(Peach, NetPDL)*

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

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

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

*(иллюстрирующий пример)*

Возможность сериализации структуры результата очевидно необходима, поскольку проводить разбор каждый раз, когда необходимо изучить данные, нецелесообразно. Более того, наличие подобного формата вывода потенциально упрощает интеграцию со сторонними системами, в которых не требуется высокая скорость обработки, поскольку не требует использования определенного языка или интерфейса. Примером такого использования является связка tshark-PDML-Pyshark.
Однако при использовании в качестве результата некоторого документа с разметкой (PDML, XML) возникает необходимость также использовать разборщик для повторного изучения данных. Тем не менее часто такие разборщики будут на несколько порядков эффективнее. К примеру разбор достаточно сложного бинарного протокола займет сущетсвенное время, а считывание из XML-файла результатов займет существенно меньше времени в силу простоты этого формата.

## Требования к представлению результатов разбора
В рамках задач анализа бинарных данных часто возникают некоторые требования к результатам разбора этих данных и к внутренним представлениям. Основным требованием является наличие иерархичной структуры полей — дерева. Такой подход чаще всего реализуется в качестве внутренних представлений в том или ином виде, явно или не явно (Wireshark, Netbee, KaitaiStruct).

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

## Существующие инструменты
Существует ряд инструментов, позволяющих *декларативно* описывать форматы данных. Используя такое описание и специальный компилятор — генератор разборщиков — можно построить готовый разборщик данного формата, имеющий разного рода входные и выходные интерфейсы. Разборщик может представлять из себя код на некотором языке программирования (KaitaiStruct), исполняемую программу (Spicy) или модуль в некоторой инфраструктуре инструмента (PeachPit).

Список рассматриваемых инструментов для описания бинарных форматов:
* KaitaiStruct
* PeachPit
* Netbee
* binpac
* Spicy
* DataScript
* GAPA
* ANTLR (?)
* ... (что-то еще?)

Характеристики для сравнения:
* особенности форматов, семантическая выразительность:
* использование битовых полей в формате
* обобщающий перебор (switch-case)
* параметризованные типы
* ... (?)
* встроенные типы данных (int, uint и т.д.)
* интерфейсы генератора разборщиков (что на выходе), самодостаточность инфраструктуры (как использовать полученный разборщик)
* подходы к обработке ошибок разбора
* поддержка контекста разбора, автомата состояния протокола
* возможность использования пользовательского кода для разбора
* параллельный разбор нескольких потоков, поточный режим разбора
* потоковая обработка входящих (или вызодящих) байтов (degzip, например)

## Классификация

### Назначение
1. инструменты, нацеленные на разбор сетевых протоколов: *Spicy*, *binpac*, *Netbee*, *GAPA*
2. бинарные форматы файлов и структуры: *KaitaiStruct*, *DataScript*, *Peach*

### Самостоятельность инфраструктуры, входные-выходные данные
1. выходной формат — код разборщика на некотором языке программирования: *KaitaiStruct* (C++, Python, Java, ...), *binpac* (Cи)
2. выходной формат — исполняемый файл разборщика: *Spicy* (?), *DataScript* (java?)
3. выходного файла нет, описание формата загружается в инфраструктуру, компилятор и разборщик — часть этой одной инфраструктуры: *Netbee*, *Peach*, *GAPA*, *binpac* (интегрируется в Bro)

### Результат разбора
1. специальный формат разметки данных: Netbee, Peach(?)
2. API экземпляра сообщени: KaitaiStruct, binpac

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

В сетевом взаимодействии узлы обмениваются пакетами определенной структуры и возникает задача в их разборе. Причем форматы этих сообщений вообще говоря различные даже для сообщений в рамках одного сеанса взаимодействия. Например, распространенная схема общения клиент-сервер подразумевает два типа сообщения — запрос и ответ. Ответ в свою очередь может также иметь различную структуру в зависимости от параметров запроса. Сами форматы сообщений зачастую достаточно простые и имеют много общего друг с другом. Часто встречаются схемы вида *"заголовки + тело"* или *"длина сообщения + тело сообщения"*.

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

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

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

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

## Задача автоматического определения формата
Иногда встает задача имея определенный набор форматов (база), определить, к какому формату относятся данные и разобрать их в соответствии с этим ним. Такая задача может встретиться например в фильтрах сетевого трафика (?).

... (как она решается в Netbee?)