LINUX.ORG.RU

Тестирую компиляцию описания формата Kaitai Struct в диаграмму GraphViz

 , ,


4

2

Сделали новую фичу в Kaitai Struct: раньше мы умели описания бинарных форматов файлов и пакетов смотреть в визуализаторе и компилировать в исходный код парсера на поддерживаемых языках программирования (к ним, кстати, медленно, но верно добавляются PHP и Perl), а теперь мы умеем еще и генерировать по описаниям форматов вот такие вот диаграммы.

На скриншоте - развернутая на фул-скрин схема базовых тестовых форматов стека OSI 2-4 уровней. Все начинается с pcap-файла (вне уровневой классификации), в который вложены фреймы формата Ethernet (2 уровень), в которые вложены IPv4-пакеты (3 уровень), в которые вложены либо TCP-сегменты (4 уровень), либо ICMP-пакеты (3 уровень). Таблички - классы. Жирные стрелки - включения типов один в другой, серые дуги - использования значений из какого-то поля в другом.

В правом верхнем углу - для сравнения - окошко с текстовым редактором, в котором видно, как выглядит исходник описания формата pcap в .ksy.

Схема получена абсолютно автоматически без каких-либо ручных правок и дорисовываний ровно за 2 шага:

1. Пачка файлов с описаниями форматов .ksy компилируется в graphviz:

ksc -t graphviz файлы.ksy

2. Полученный dot-файл банально обрабатывается graphviz:

dot -Tsvg <файл.dot -o файл.svg

Если стало интересно, вот еще пачка примеров:

>>> Просмотр (3840x2160, 223 Kb)

★★

Проверено: JB ()

Кстати, да, кастую Quote, frob, SZT, tailgunner, ProtoH — в продолжение разговора — возможно, вам будет интересно на эти картинки посмотреть. Совершенно другая сторона компилятора парсеров — из императивного формата ничего такого бы, понятно, не получилось — в лучшем случае была бы блок-схема алгоритма.

GreyCat ★★ ()

Крутая идея, пока не пробовал, но картинка нравится.

ProtoH ()

Выглядит полезно.
Более наглядное представление того как формат устроен.

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

В OLEToy для файлов Freehand приделана возможность сгенерировать граф со связями между записями в реальном файле. Правда на «настоящих» файлах получается такое месиво, что не разобраться. Но на маленьких файлах с выкинутыми «встроенными» ресурсами получилось понять как оно вообще увязано. Пример.

frob ★★★★★ ()
Последнее исправление: frob (всего исправлений: 1)

Лучше сделать возможность как-нибудь эту схему просматривать и редактировать при генерации, чтобы можно было более удачно стрелочки и блоки расставить руками

SZT ★★★★ ()
Последнее исправление: SZT (всего исправлений: 1)
Ответ на: комментарий от SZT

Лучше сделать возможность как-нибудь эту схему просматривать и редактировать при генерации, чтобы можно было более удачно стрелочки и блоки расставить руками

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

А если совсем «руками», то это уже недоредактор диаграмм какой-то получится.

frob ★★★★★ ()

В правом верхнем углу - для сравнения - окошко с текстовым редактором

В правом верхнем углу

Хм...

theNamelessOne ★★★★★ ()
Ответ на: комментарий от theNamelessOne

Упс, я уже не смогу поправить. Если кто-нибудь из модераторов-корректоров сможет - прошу :)

GreyCat ★★ ()

Kaitai Struct интересная вещь. Написано, что C++ в процессе, а известно ли когда процесс будет завершен? И как с производительностью таких парсеров?

Vark ()

Интересный инструмент, спасибо за информацию.

gns ★★★★ ()

Рекурсивные ссылки на блоки это поля переменной длинны? Не нашел в документации (просто быстро глянул). TLV может описать?

ioway ()
Ответ на: комментарий от ioway

Рекурсивные ссылки - это рекурсивные ссылки (т.е. ссылка типа на самого себя - что-нибудь типа single-linked list), но вроде бы как раз в этих примерах их нигде нет. Пример такого можно посмотреть в формате .cr2, например.

Если вы про эти лихие петли, окружающую всю табличку и ведущие от какого-нибудь поля вроде «total_length» к колонке «size» у поля «body» - и при этом в колонке «size» на этот total_length явно ссылаются - это использование зачитанного значения для образования поля с длиной, соответствующей этому значению. В целом поля переменной длины могут быть гораздо более сложные - например, длина поля явно не задается, но она зависит от длины вложенной подструктуры. В этом случае (когда не удалось сходу определить длину) в поле «size» выводится "..."

TLV может описать?

Вот ыз ыт?

GreyCat ★★ ()
Ответ на: комментарий от Vark

известно ли когда процесс будет завершен?

Во-первых, стоит оговориться, что речь о C++/STL. Было еще ненулевое количество заявок на C++/Qt, его еще даже не начинали.

Сейчас поддержка C++/STL примерно такая - т.е. 77%. Не хватает enum'ов, не хватает вдумчивого тестирования exception'ов, есть проблемы со сложными вложенными типами. Нет (и на самом деле скорее всего не будет) встроенной поддержки кодировок, нет простой поддержки zlib (ну и в целом надо решать вопрос с модульной сборкой, чтобы zlib нужно было линковать только тем, кому он нужен).

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

Четких дат релизов нет, проект некоммерческий. Если если желание чем-топомочь с C++ - с благодарностью примем помощь в консультировании, и тестировании тестами, code review, рекомендациями по тому, как сделать лучше / быстрее / оптимальнее, etc.

как с производительностью таких парсеров?

Сложный вопрос, смотря с чем сравнивать. Если учесть, что это - компилятор и получается готовый статический код, то оно априори быстрее каких-либо интерпретирующих штук, которые в рантайме смотрят в описание формата, а затем принимают решение, как парсить. Но надо понимать, что задача KS - сначала все запарсить, разложить в памяти, а затем предоставить _API_. Есть некий класс задач, когда вам сильно быстрее будет не раскладывать все в памяти, а сделать какое-то одно действие прямо в процессе парсинга. В этом случае, вероятно, stateful parser generators / parser combinators - ваш выбор.

GreyCat ★★ ()
Ответ на: комментарий от SZT

По идее можно как-то из graphviz экспортировать в формат «graphviz + рассчитанные автоматом координаты», а потом руками грузить это в какой-нибудь Inkscape / OO Draw / Scribus - и доводить.

GreyCat ★★ ()
Ответ на: комментарий от frob

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

Для файлов - это же по сути дерево, которое показывает визуализатор. Вообще в целом вся идея показывать связи - она такая, достаточно спорная. Это не то, чтобы дико сложно было сделать (благо транслятор языка выражений у нас уже написан) - но визуального мусора генерируется много. Возможно, надо как-то это интерактивно показывать (например, подсвечивать все зависимые поля при наведении мышки?)

GreyCat ★★ ()

Очень крутая штука. Спасибо за наводку :)

pon4ik ★★★★★ ()
Ответ на: комментарий от GreyCat

Можно попробовать сделать-таки как вариант «визуализатора» что-то вроде «редактора диаграмм», но тогда графвиз останется разве что для «начального размещения» использовать, а в формате придётся где-то хранить данные о том куда расставлять блоки при выдаче графа.

Идея показывать связи хорошая, но полезность разная — для одних форматов не нужно, а для других «как же вообще без этого...». Посмотрите на ссылку, что я дал — после такого выхлопа стало понятно во что разбирать записи в libfreehand.
Поскольку записей слишком много, пришлось определённые типы подкрасить. Если что-то такое делать более универсально (а как ещё это могло бы быть в KS?), то придётся предусмотреть в формате разные возможности описания того как чего показывать/подсвечивать, как располагать относительно друг-друга и всё такое.
(Это если говорить про визуализацию разбора файла с использованием KS.)
Визуализация структуры самого формата по идее должна быть проще и наверное подсветка особо не нужна. Если делать что-то интерактивное, то можно попытаться вместо выбрасывания всего сразу на один лист для каких-то частей формата показывать «чёрный ящик», а по клику открывать «детализацию».

frob ★★★★★ ()
Ответ на: комментарий от GreyCat

TLV

В википедии какая-то на редкость убогая статья про TLV.

TLV очень широко используется в сетевых протоколах — IS-IS, CDP/LLDP, BGP, RADIUS, EAP, LDP и пр.
Писать/читать просто, расширяемость есть, при желании можно легко реализовать какой-нибудь механизм для автоматического определения необходимости поддержки и проброса того или иного TLV (выдавать отказ если заявлена необходимость поддержки, а получатель не знает что с этим TLV делать; передавать/дропать «неизвестные» TLV) — если поддержка необязательна, а «T» неизвестен, то данные можно успешно пропустить и продолжить дальше.

Аналогично устроены MS-овские WMF и EMF, только length они называют size и в WMF «T» и «L» шли в обратном порядке.

frob ★★★★★ ()
Ответ на: комментарий от frob

В википедии какая-то на редкость убогая статья про TLV.

Я вот подозреваю, что это потому, что аббревиатура как-то высосана из пальца. Посмотрите выдачу гугла - на первых эдак 5-6 страницах кроме этой википедии про «TLV» - ничего.

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

GreyCat ★★ ()
Ответ на: комментарий от GreyCat

Зря подозреваете =)
Посмотрите в выдачу гугла по «TLV IANA».

В тех TLV, что в RFC, как раз всё бездьявольско.

Ну и вопрос про возможность закодировать TLV в KS был «от Ъ», поскольку на скриншоте имеются два TLV.

frob ★★★★★ ()
Ответ на: комментарий от frob

Если брать хотя бы просто все сетевые протоколы, стандартизированные в RFC - я там тоже большой системности не вижу. В IP есть опции - по сути тот же TLV (на самом деле «флаг + тип1 + тип2 + длина блока вместе с заголовков + value») - но его так никто не называет. DHCP активно использует vendor options - которые по сути такие variable-length блоки - и их тоже никто не называет TLV.

По большому счету, протоколов, которые активно используют именно термин TLV - я вижу примерно 2 - это IS-IS и RADIUS, и всяческие подпротоколы авторизаций типа EAP/PEAP, использующиеся внутри них.

В любом случае - ioway я могу сказать спасибо хотя бы за расширение моего терминологического кругозора.

GreyCat ★★ ()
Ответ на: комментарий от GreyCat

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

ioway ()
Ответ на: комментарий от ioway

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

95% сетевых протоколов, что я наблюдаю, если не брать в расчет protobuf-based - сильно хуже даже этого ;)

GreyCat ★★ ()

Да, рисовать такие схемы это конечно интересный функционал, но намного важнее как мне кажется сделать GUI и подсветку отдельных байт/бит(когда будет возможность с ними работать) в разбираемом файле, как например https://s11.postimg.io/6u4t983ab/K_15_edit.png https://dump.bz/storage-2/0916/HlmCA1o6L6H8y0DdQuOJvuEB50kO9LpQ.jpg

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

0123456789ABCDEF
ЗЗЗ__ЗЗ__ЗЗ_____
Где З - занято, _ - свободное место, и нам надо записать 4 кб (четыре блока), то можно это сделать так:
0123456789ABCDEF
ЗЗЗ++ЗЗ++ЗЗ_____
или так
0123456789ABCDEF
ЗЗЗ__ЗЗ__ЗЗ++++_
или вообще как-нибудь так
0123456789ABCDEF
ЗЗЗ_+ЗЗ+_ЗЗ_+_+_
И это вполне может потребоваться для каких-нибудь тестов, например замера скорости дефрагментации, проверка скорости ФС когда она сильно фрагментирована и так далее. Возникает вопрос - каким должно быть API сгенерированное KS? Должно ли оно быть настолько гибким? Для драйвера ФС в микроконтроллере оно настолько гибким быть точно не должно

SZT ★★★★ ()
Последнее исправление: SZT (всего исправлений: 1)
Ответ на: комментарий от SZT

Думаю, нужен какой-то способ специализировать API под решения какого-то узкого круга задач, например для задания политики в отношении того, каким образом «занять» место на ФС новым файлом, если мы его создаем. Когда мы читаем файл из ФС мы можем вообще не думать как разбросаны кусочки файлов, просто собираем их по занятым кластерам, там такой проблемы с неоднозначностью не возникает, а с записью есть много вариантов.

SZT ★★★★ ()
Последнее исправление: SZT (всего исправлений: 1)
Ответ на: комментарий от SZT

но намного важнее как мне кажется сделать GUI и подсветку отдельных байт/бит(когда будет возможность с ними работать) в разбираемом файле

Она есть, но в текстовом виде. Сделать именно GUI, наверное, было бы тоже полезно, но GUI-писатель из меня лично как-то весьма так себе, как показывает практика.

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

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

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

GreyCat ★★ ()

А как вы добились, чтобы концы стрелочек не сходились в одну точку, когда один из их концов указывает на один и тот же элемент? Например, как в графе для PE .exe файла к элементу MicrosoftPE::DataDir?

DinoAsm ()

Случайно наткнулся опять на визуальную описывалку.
DataWorkshop называется.
http://dataworkshop.de/

frob ★★★★★ ()
Ответ на: комментарий от frob

Забавно, спасибо, я такой, кажется, даже не находил. Проект, конечно, выглядит весьма мертвым (с последними апдейтами в 2005), но прецедент интересный. Язык структур относительно богатый (на уровне Hexinator, на самом деле) - но, разумеется, нет подпотоков, нет полноценных выражений (но есть возможность из x сделать x * a + b), нет массивов (тем более массивов подструктур), нет полноценных условных конструкций (есть только case по одному полю) и т.д. Зато внутри все прямо натурально в битах считается, можно задавать unaligned поля по 3 бита и т.д. :)

GreyCat ★★ ()
Ответ на: комментарий от GreyCat

Я на него наткнулся осенью 2006-го. А потом потерял и даже забыл как звать. А тут случайно обнаружил в списках «всякого полезного софта» =)

10 лет назад оно на моём компе тормозило и падало. Возможно из-за того что памяти было мало.
Но выглядело интересно.

frob ★★★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.