Как стать автором
Обновить

Создание конечного автомата для разбора HTTP запроса

Время на прочтение3 мин
Количество просмотров9.1K
Детерминированный конечный автомат можно использовать для реализации очень быстрого способа разбора входной последовательности. Требуется всего один проход по входной последовательности, и минимальные действия на каждом шаге. К сожалению эта модель имеет ограничения — не всегда возможно построить ДКА, для имеющегося Недетерминированного конечного автомата (регулярного выражения, грамматики). Или даже если возможно построить, автомат может иметь слишком большое число состояний.

Тем не менее я решил попробовать создать парсер для HTTP запроса на основе ДКА. Основная задача не просто проверить корректность HTTP запроса, а именно выделить во входной строке элементы соответствующие определенным значениям полей HTTP запроса. Автомат должен генерироваться из BNF правил (разбросанных по) RFC2616. Реализовано все на C#, автомат на выходе тоже на C#. Хотя понятно что когда автомат готов, сгенерировать его на любом языке, в любом виде не проблема.

Для генерации ДКА реализована следующая цепочка действий:
1. Разбор BNF правил
2. Создание на их основе НКА
3. Преобразование НКА в ДКА
4. Минимизация ДКА
5. Создание файлов с исходным текстом и таблицей переходов

Для разбора BNF грамматики я воспользовался Irony, грамматика ABNF хорошо описана в RFC5234. По синтаксическому дереву программа строит НКА по правилам Томсона. Для преобразования НКА в ДКА, и минимизации использованы стандартные алгоритмы, описывать их тоже не буду.

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

Подобный подход используется в регулярных выражениях (хотя не во всех реализациях делают преобразование в ДКА). Но имея прямой доступ к автомату, возможно произвести ряд интересных оптимизаций. К примеру, поле Content-Lenght содержит длину тела сообщения, для этого поля преобразование в число происходит прямо в автомате, на выходе имеем поле класса int ContentLenght. Еще одна интересная оптимизация, к примеру для HTTP запроса определен набор методов (GET,HOST...). На выходе парсера можно сразу получить константу соответствующую методу. И все это за один проход.

Так же очень важно, что парсер принимает на вход массив байт, особенно это актуально для современных языков вроде C#, где строка это не массив байт как в C++, и простым кастингом указателя здесь не обойдешься.

В целом система выглядит следующим образом. Имеется BNF грамматика, и описание класса который хотим получить на выходе. Все это подаем на вход генератора, и получаем ДКА на C#. С готовым автоматом можно работать следующим образом:

dfa.SetDefaultValue();
dfa.Parse(message0, 0, message0.Length);
dfa.SetArray(message0);

Console.WriteLine("Method: {0}", dfa.Method);
Console.WriteLine("Request-URI: |{0}|", dfa.RequestUri.ToString());
Console.WriteLine("Host: |{0}|", dfa.Host.ToString());
Console.WriteLine("Content-Type: |{0}|", dfa.ContentType.Value.ToString());
Console.WriteLine("Content-Length: {0}", dfa.ContentLength);
Console.WriteLine("Referer: |{0}|", dfa.Referer.ToString());


На практике, ДКА для HTTP запроса содержит до минимизации 150К состояний, после 1К-2К. Понятно, во первых, что 1К-2К вполне приемлемое значение для реального использования. Во вторых 150К состояний, требует некоторой памяти и времени на вычисления (по крайней мере в моей реализации) — минут x-цать.

Скорость работы парсера очень высокая, формальная грубая оценка для такого подхода ~С*O(n), и принципиально улучшить ее наверное сложно. В реальности, парсер на C# у меня на машине, успел распарсить 1М раз за 3.3 секунды сообщение длиной 220 байт.

Исходный код проекта доступен: code.google.com/p/siprevo

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

Update: «компилятор» автомата в виде отдельной утилиты живет здесь.
Теги:
Хабы:
Всего голосов 31: ↑23 и ↓8+15
Комментарии12

Публикации

Истории

Работа

.NET разработчик
61 вакансия

Ближайшие события

2 – 18 декабря
Yandex DataLens Festival 2024
МоскваОнлайн
11 – 13 декабря
Международная конференция по AI/ML «AI Journey»
МоскваОнлайн
25 – 26 апреля
IT-конференция Merge Tatarstan 2025
Казань