The OpenNET Project / Index page

[ новости /+++ | форум | wiki | теги | ]

Декларативная спецификация парсинга бинарных файлов Kaitai Struct

12.04.2016 17:21

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

Формат описывается в виде файла .ksy (который представляет собой YAML специального вида), который можно не только использовать в качестве документации, но и сразу же скомпилировать с помощью специального компилятора (ksc). На выходе компилятора — исходные коды библиотеки на одном из поддерживаемых языков, которая автоматически будет выполнять парсинг описанного в .ksy формата. Первый публичный релиз поддерживает Java, JavaScript, Python, Ruby, ожидается поддержка C, C++ и C#.

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

Целевая область применения подобных решений — быстрая разработка кросс-платформенных, кросс-языковых реализаций парсеров бинарных форматов, реверс-инжиниринг бинарных форматов, создание единой базы знаний о применяемых в тех или иных областях знаний бинарных форматах.

Ближайшие аналоги такого подхода — система диссекторов в Wireshark, ряд проприетарных hex-редакторов (таких, как 010 Editor, Synalysis, Hexinator), система шаблонизации в Okteta (но все они занимаются лишь описанием и визуализацией, а не парсингом как таковым) и ряд библиотек для одиночных языков, например Preon для Java или jBinary для JavaScript.

  1. Главная ссылка к новости (http://kaitai.io/...)
Автор новости: GreyCat
Тип: К сведению
Ключевые слова: kaitai, struct
При перепечатке указание ссылки на opennet.ru обязательно
Обсуждение (44) Ajax | 1 уровень | Линейный | +/- | Раскрыть всё | RSS
  • 1.1, ferux (ok), 18:45, 12/04/2016 [ответить] [﹢﹢﹢] [ · · · ]  
  • +/
    Это что, теперь для любителей подебажить бинарные форматы совсем не останется работы?!
     
     
  • 2.3, GreyCat (ok), 19:15, 12/04/2016 [^] [^^] [^^^] [ответить]  
  • +2 +/
    Останется, конечно — но жизнь можно слегка упростить :)
    Все-таки куда удобнее смотреть сначала на дерево в визуализаторе (и править спецификацию формата до получения желаемого) и оперировать уже именованными примитивами - писать "header.field", а не "field = readSomeInteger()", боясь за то, что где-то может съехать какой-нибудь паддинг или что-то такое.
     

  • 1.2, Аноним (-), 18:56, 12/04/2016 [ответить] [﹢﹢﹢] [ · · · ]  
  • –2 +/
    Очередной компилятор компиляторов? Описание формата в БНФ? Чем оно лучше bison?
     
     
  • 2.5, GreyCat (ok), 19:26, 12/04/2016 [^] [^^] [^^^] [ответить]  
  • +12 +/
    > Очередной компилятор компиляторов? Описание формата в БНФ? Чем оно лучше bison?

    Очередной, в какой-то степени. К БНФ и bison оно, тем не менее, отношения почти не имеет. Парсинг всяких текстов (исходников ли, каких-нибудь текстовых форматов разметки), как правило, упирается в то, что один и тот же символ алфавита (буква "a", скажем), может иметь совершенно разную роль в зависимости от контекста - может быть частью литерала, идентификатором, названием тэга, частью ключевого слова и т.д., и этот самый контекст на самом деле весьма нетривиально вычислить. Умные люди для этого придумывают всякие LL-, LR-, LALR- и прочие SLR и т.д. lexx/yacc/bison/т.п. работают как раз в этих парадигмах и львиная доля усилий там тратится именно на то, чтобы понять - вот эта буква "a", что мы только что считали - это вообще что.

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

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

     

  • 1.4, Аноним (-), 19:26, 12/04/2016 [ответить] [﹢﹢﹢] [ · · · ]  
  • +/
    Ну все, postgres, mysql, oracle перейдут на него для хранения данных и... а не, C/C++ пока нету.
     
     
  • 2.6, GreyCat (ok), 19:28, 12/04/2016 [^] [^^] [^^^] [ответить]  
  • +/
    > Ну все, postgres, mysql, oracle перейдут на него для хранения данных и...
    > а не, C/C++ пока нету.

    Форматы хранения MyISAM, InnoDB и SQLite, кстати, мы вполне умеем разбирать ;)

     
  • 2.8, Аноним (-), 19:33, 12/04/2016 [^] [^^] [^^^] [ответить]  
  • +/
    И для сборки всего, что его использует будет нужна Java.
     
     
  • 3.11, GreyCat (ok), 19:39, 12/04/2016 [^] [^^] [^^^] [ответить]  
  • +/
    > И для сборки всего, что его использует будет нужна Java.

    Либо JavaScript. Scala умеет компилироваться либо для JVM, либо для JavaScript-машин типа nodejs. Последнее, кстати, запускается радикально быстрее и сильно веселее в целом, если дергать его для десятка форматов из какого-нибудь Makefile, скажем.

     
     
  • 4.13, Crazy Alex (ok), 20:04, 12/04/2016 [^] [^^] [^^^] [ответить]  
  • +/
    Хм, вообще-то нода запускается ни разу не быстро...
     
     
  • 5.16, GreyCat (ok), 20:13, 12/04/2016 [^] [^^] [^^^] [ответить]  
  • +/
    > Хм, вообще-то нода запускается ни разу не быстро...

    У меня получается что-то в районе ~400 ms на один запуск компилятора на JVM и ~160 ms на запуск компилятора под nodejs. Не сверхбыстро, но все же в 2.5 раза быстрее, чем JVM.

     
     
  • 6.18, Crazy Alex (ok), 20:33, 12/04/2016 [^] [^^] [^^^] [ответить]  
  • +/
    У вас какой-то монстр, а не машина :-) с такой скоростью у меня на JVM даже hello world не взлетает, а на ноде - time nodejs -e 'console.log(1)'
    даёт 0.4 секунды
     
     
  • 7.19, GreyCat (ok), 20:48, 12/04/2016 [^] [^^] [^^^] [ответить]  
  • +1 +/
    > У вас какой-то монстр, а не машина :-) с такой скоростью у
    > меня на JVM даже hello world не взлетает, а на ноде
    > - time nodejs -e 'console.log(1)'
    > даёт 0.4 секунды

    Ноутбук не первой свежести, на средненьком i5. nodejs:

    $ time nodejs -e 'console.log(1)'
    0,06s user 0,00s system 98% cpu 0,061 total

    JVM:

    $ echo 'class Main { public static void main(String[] args) { System.out.println(1); }}' >/tmp/Main.java
    $ javac /tmp/Main.java
    $ time java -cp /tmp Main
    0,07s user 0,00s system 112% cpu 0,068 total

    Какие 400 ms?

     
  • 4.39, anonymous (??), 21:01, 13/04/2016 [^] [^^] [^^^] [ответить]  
  • +/
    >Последнее, кстати, запускается радикально быстрее

    Была какая-то тулза для ускорения многократного запуска программ на Java за счет переиспользования JVM

     

  • 1.7, Аноним (-), 19:32, 12/04/2016 [ответить] [﹢﹢﹢] [ · · · ]  
  • +/
    Бинарный bison...
    на Java...
     
     
  • 2.9, GreyCat (ok), 19:35, 12/04/2016 [^] [^^] [^^^] [ответить]  
  • +1 +/
    > Бинарный bison...
    > на Java...

    На Scala, на самом деле :)

     
     
  • 3.10, Аноним (-), 19:37, 12/04/2016 [^] [^^] [^^^] [ответить]  
  • +/
    Ааа, ну это многое объясняет.
     
  • 2.43, serg (??), 21:34, 20/04/2016 [^] [^^] [^^^] [ответить]  
  • +/
    Господа! Если время старта/компиляции критично, то можно файлы *.class скормить компилятору gcj (все про него забыли). Получится нативный исполняемый бинарь, который порадует вас не только быстрым стартом, но и шустрым исполнением кода.
     
     
  • 3.44, GreyCat (ok), 21:52, 20/04/2016 [^] [^^] [^^^] [ответить]  
  • +/
    > Господа! Если время старта/компиляции критично, то можно файлы *.class скормить компилятору
    > gcj (все про него забыли). Получится нативный исполняемый бинарь, который порадует
    > вас не только быстрым стартом, но и шустрым исполнением кода.

    Эм, вы сами пробовали? Нативный бинарь получается размером эдак мегабайт 30-35, JIT в нем отсутствует начисто, внутри по сути примерно такая же виртуальная машина, стартап там тоже мягко говоря небыстрый и сама программа работает, как правило, в несколько раз медленнее того, как она работает в JVM.

    Плюс, пардон, когда я последний раз туда смотрел, там не то, что Java 7 не поддерживалась, даже Java 6 местами не была реализована.

     

  • 1.12, Crazy Alex (ok), 20:03, 12/04/2016 [ответить] [﹢﹢﹢] [ · · · ]  
  • +1 +/
    Хм, правильно, конечно. Если б ещё было на чём-то человеческом (читай - компилируемом в шустрый бинарь, не требующий VM), а не Scala... Но, в конце концов, ничего идеального не бывает, если сделают выхлоп в виде C и C++ - то, в общем, вполне юзабельно. Да и удачный формат и большая  библиотека описаний в таких вещах важнее языка реализации, а здесь, вроде, есть кому эти описания клепать.
     
     
  • 2.14, GreyCat (ok), 20:07, 12/04/2016 [^] [^^] [^^^] [ответить]  
  • +/
    > Хм, правильно, конечно. Если б ещё было на чём-то человеческом (читай -
    > компилируемом в шустрый бинарь, не требующий VM), а не Scala... Но,
    > в конце концов, ничего идеального не бывает, если сделают выхлоп в
    > виде C и C++ - то, в общем, вполне юзабельно. Да
    > и удачный формат и большая  библиотека описаний в таких вещах
    > важнее языка реализации, а здесь, вроде, есть кому эти описания клепать.

    Поддержку C++ мы делаем уже месяц как, но, как выясняется, это несколько сложнее, чем казалось на первый взгляд.

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

     
     
  • 3.17, Crazy Alex (ok), 20:28, 12/04/2016 [^] [^^] [^^^] [ответить]  
  • +/
    Ну и я примерно о том же. Спасибо за интересный инструмент, а нужно ли будет его (и кому) реализовывать на других языках - будет видно.
     
  • 2.25, fi (ok), 01:01, 13/04/2016 [^] [^^] [^^^] [ответить]  
  • +/
    После RabbitMQ на Erlang стало фиолетово что там внутри готовой прикладухи круться. :)))
    Чего и вам желаю!
     

  • 1.15, Аноним (-), 20:07, 12/04/2016 [ответить] [﹢﹢﹢] [ · · · ]  
  • +/
    Не взлетит. Тем более с таким языком разметки, тем более оно не тьюринг-полное ни разу.
     
     
  • 2.20, GreyCat (ok), 20:51, 12/04/2016 [^] [^^] [^^^] [ответить]  
  • +1 +/
    > Не взлетит. Тем более с таким языком разметки, тем более оно не
    > тьюринг-полное ни разу.

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

     
     
  • 3.21, Аноним (-), 21:14, 12/04/2016 [^] [^^] [^^^] [ответить]  
  • +1 +/
    > DSL

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

     
  • 3.42, Алконим (?), 20:21, 20/04/2016 [^] [^^] [^^^] [ответить]  
  • +/
    Для парсинга *любого* бинарника нужна машина тюринга. Бинарь частично упакованый gzip или зашифрованый ssl, смогёт?
     

  • 1.22, Anonymous_1 (?), 21:55, 12/04/2016 [ответить] [﹢﹢﹢] [ · · · ]  
  • +/
    Прикольная штука, взял на заметку.
     
  • 1.23, None (??), 22:26, 12/04/2016 [ответить] [﹢﹢﹢] [ · · · ]  
  • +/
    Ожидаю сравнения с ASN.1
     
     
  • 2.24, Crazy Alex (ok), 23:28, 12/04/2016 [^] [^^] [^^^] [ответить]  
  • +/
    Не надо с ним сравнивать. С ним вообще связываться не надо - оно не человеческое.
     
  • 2.33, GreyCat (ok), 08:21, 13/04/2016 [^] [^^] [^^^] [ответить]  
  • +/
    > Ожидаю сравнения с ASN.1

    ASN.1 можно сравнивать с protobuf или, скажем, как продвинутый вариант bencoded или BSON. Т.е. это все варианты серилизации каких-то структур данных из памяти в поток и обратно, причем сам механизм сериализации фиксированный. KS — это инструментарий для парсинга произвольных потоков. Скажем, PNG-файл или там какие-нибудь пакеты из сетевого трафика.

     

  • 1.26, Аноним (-), 01:06, 13/04/2016 [ответить] [﹢﹢﹢] [ · · · ]  
  • +4 +/
    > Первый публичный релиз поддерживает Java, JavaScript, Python, Ruby, ожидается поддержка C, C++ и C#.

    Должно быть ровно наоборот.

     
  • 1.27, Аноним (-), 01:42, 13/04/2016 [ответить] [﹢﹢﹢] [ · · · ]  
  • +1 +/
    Как насчет сравнения с BinPac ? https://github.com/bro/binpac/blob/master/README
     
     
  • 2.28, Влад (??), 01:58, 13/04/2016 [^] [^^] [^^^] [ответить]  
  • +1 +/
    Присоединяюсь к вопросу. С binpac работать приходилось, отличная штука, которая может и файлы и поток парсить. Какие части декларативно никак не сделать (редко, но бывает) - можно вручную попарсить, есть встроенные в binpac средства для связи с ручным парсером. А если внутри того, что парсишь вручную снова можно декларативно парсить - тоже не проблема, легко и обратно к декларативному парсингу вернуться
     
     
  • 3.34, GreyCat (ok), 09:04, 13/04/2016 [^] [^^] [^^^] [ответить]  
  • +1 +/
    А вот это хороший вопрос В целом, да, проекты весьма похожие Если смотреть н... текст свёрнут, показать
     

  • 1.29, qpq (ok), 02:09, 13/04/2016 [ответить] [﹢﹢﹢] [ · · · ]  
  • +/
    А как на счёт генератора бинарного потока? Или парсер может в обе стороны?

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

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

     
     
  • 2.41, GreyCat (ok), 10:42, 14/04/2016 [^] [^^] [^^^] [ответить]  
  • +/
    Генератора пока нет — есть далекоидущая цель сделать это где-нибудь ко второй major версии. По большому счету в декларативном формате эта задача упирается в необходимость (и возможность) символического вывода: например, если где-то объявлено число x, а где-то есть строка str длиной (2 * x + 3), т.е. str.length = 2 * x + 3. Значит, при записи нужно развернуть формулу и записывать x = (str.length - 3) / 2. И, внезапно, иногда решений может вообще не быть, а иногда их может быть бесконечно много.
     

  • 1.30, j (??), 02:11, 13/04/2016 [ответить] [﹢﹢﹢] [ · · · ]  
  • +/
    Подхватываете флаг преона? великое дело, имхо
    от преона не забудьте взять легкую расширяемость - всех извращений не предусмотришь.
    для бигдаты было бы полезно простую интеграцию в виде преобразования в avro, например. прекрасно те же cdr разбирать. там за такой разбор с медиейшеном платят ой как много.
     
     
  • 2.35, GreyCat (ok), 10:06, 13/04/2016 [^] [^^] [^^^] [ответить]  
  • +/
    > Подхватываете флаг преона? великое дело, имхо
    > от преона не забудьте взять легкую расширяемость - всех извращений не предусмотришь.

    Тут в какой-то степени двоякая ситуация. С одной стороны — никто не запрещает в императивном уже режиме из языка дергать парсеры как угодно и комбинировать их результаты. Это по сути примерно то же самое, что есть в Preon — и это все можно, но (1) оно будет привязано к одному конкретному языку, (2) это императивно, а не декларативно.

    С другой стороны — по идее нужна какая-то более гибкая расширяемость, но оставаясь в декларативных рамках. Очень много что дают value instances (по сути внутри там — некий язык выражений, который гарантированно компилируется в соответствующее выражение на Java/JS/Python/Ruby), но они тоже не панацея, плюс они решают только задачу чтения (бинарник => классы), но не записи (классы => бинарник). Нужно придумывать что-то еще.

    > для бигдаты было бы полезно простую интеграцию в виде преобразования в avro,
    > например.

    Avro — в смысле, с генерируемых классах сразу Avro-аннотации генерировать, как-то так?

    > прекрасно те же cdr разбирать. там за такой разбор с
    > медиейшеном платят ой как много.

    CDR — имеются в виду всякие логи сотовых операторов и прочая биллинг-ориентированная тематика?

     
     
  • 3.40, j (??), 22:53, 13/04/2016 [^] [^^] [^^^] [ответить]  
  • +/
    > Avro — в смысле, с генерируемых классах сразу Avro-аннотации генерировать, как-то
    > так?

    В идеале + код. Если говорим о Hadoop семействе, то оптимально - InputFormat c выходом Avro объектов. Кроме самого Hadoop-а это практически автоматом даст интеграцию с Spark и Hive

    > CDR — имеются в виду всякие логи сотовых операторов и прочая биллинг-ориентированная
    > тематика?

    Сырые логи с оборудования. Навскидку http://bill-parser.googlecode.com/svn/trunk/doc/CDR_Description_M14.3.pdf

    При этом CDR - это вершина айсберга. Там еще траффик, технические логи итд


     

  • 1.31, Срп (?), 02:36, 13/04/2016 [ответить] [﹢﹢﹢] [ · · · ]  
  • +/
    ну и дела:
    seq:
          - id: image_width
            type: u2
          - id: image_height
            type: u2
          - id: flags
            type: u1
          - id: bg_color_index
            type: u1
          - id: pixel_aspect_ratio
            type: u1

    не лучше ли как-нибудь так:

    seq
        u16 image_width
        u16 image_height
        u8 flags
        u8 bg_color_index
        u8 pixel_aspect_ratio

     
     
  • 2.32, Аноним (-), 06:48, 13/04/2016 [^] [^^] [^^^] [ответить]  
  • +3 +/
    первый вариант - валидный YAML, второй - очередной нескучный велосипед.
     
     
  • 3.36, Анонимомус (?), 13:28, 13/04/2016 [^] [^^] [^^^] [ответить]  
  • +/
    Можно было и валиндный yaml:

    seq:
      image_width: u2
      image_height: u2
      flags: u1
      bg_color_index: u1
      pixel_aspect_ratio: u1

    только это не расширяемо.

     
     
  • 4.37, GreyCat (ok), 13:30, 13/04/2016 [^] [^^] [^^^] [ответить]  
  • +1 +/
    > Можно было и валиндный yaml:
    > seq:
    >   image_width: u2
    >   image_height: u2
    >   flags: u1
    >   bg_color_index: u1
    >   pixel_aspect_ratio: u1
    > только это не расширяемо.

    Главная проблема здесь в том, что у вас получился map под названием seq, в котором порядок элементов не определен. А нам он важен, т.к. нам их надо парсить именно в определенной последовательности.

     
  • 3.38, Никто (??), 17:53, 13/04/2016 [^] [^^] [^^^] [ответить]  
  • +/
    В этом и преимущество велосипедных DSL - больше возможности для краткости.
     
     Добавить комментарий
    Имя:
    E-Mail:
    Текст:



    Спонсоры:
    Слёрм
    Inferno Solutions
    Hosting by Ihor
    Хостинг:

    Закладки на сайте
    Проследить за страницей
    Created 1996-2019 by Maxim Chirkov
    Добавить, Поддержать, Вебмастеру