Реверс черного тессеракта. Начало

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

Как охарактеризовать систему, выходные реакции которой очевидны, но нет информации о входных данных, вызывавших эти реакции? Я сейчас про компьютеры, а не о психологии или медицине. Строго говоря, входные данные не просто есть, они присутствуют в полном спектре возможных вариантов, но целиком, глыбой, блобом, а реакция происходит на отдельную неизвестную часть (части) входных данных.
По аналогии с ящиками для этого рассказа я отважно назвал такую систему именем четырехмерного ящика — черным тессерактом. Ну, во-первых, это красиво©. Черный — за неизвестные входные спецификации. Четвертое измерение — из-за того, что конечные данные устройства автомобильной навигации выдают в виде изображений, попытка компьютеризированного анализа результатов вывода бессмысленна и беспощадна. А процесс реверс-исследований затягивает, как наблюдение за проекцией тесерракта на 2D: только стало понятно, как всё устроено, но потом он чуть поворачивается…

image-loader.svg

Давным-давно, в одной далекой галактике…

Началась история, когда в 2012 купил Citroen C5 2002 года выпуска. В комплектации штатное устройство навигации (оно же CD-player) Сlarion RD3 2295 с большим цветным экраном на торпеде и отдельным считывателем CD с навигационной информацией, запрятанном в бардачке. В считывателе — CD с картой Франции пяти- семилетней давности. Но там, где находился я, навигатор отображал карту Великого Ничего или некоторый кусок неизвестной пустыни.

Предыдущий опыт использования широкого спектра навигаторов — Garmin, WinCE, Nokia, различного специализированного ГеоПО с поддержкой NMEA приемников меня не готовил к тому, что навигатор не показывает местоположения на экране. Требовалось решение мучительной дилеммы: с картой я мог быть во Франции, но когда я был вне Франции, я был без карты.

Поиски информации по сети дали следующие результаты:

  • Навигационная система — Siemens VDO Dayton and Carin Navigation. Устанавливалась, как штатная, широким рядом производителей на многие модели (BMW, Citroen, Land Rover rank Rover, Discovery, Freelander — Ford Lincoln, OPEL/Vauxhall Astra, Corsa, Omega, Vectra, Zafira, Peugeot, Renault Laguna, Megane, Clio, Scenic, Safrane, Vel Satis, Avantime, Espace, Trafic, Rover/mg 75, Volkswagen phaeton)

  • Официальных карт РФ для этой навигационной системы — Siemens/VDO Dayton Carminat — в природе не существует от слова вообще.

  • Ежегодно, и, похоже, до сих пор, выпускаются в продажу актуализированные карты Европы, цена за комплект в районе 150€-200€, но СНГ в ихнюю Европу не входит.

  • Отыскать на торрентах европейские карты можно.

  • На разных торрентах присутствует единственный образ с картой РФ и СНГ весьма печального качества — основные города и дороги, скомпилированный в 2005 году.

  • Формат карт пропириетарный, доступных редакторов, просмотрщиков, или инструментов для конвертации из/в этот формат — нет. Следы попыток энтузиастов французов расковырять формат уходили в глубины web.archive.org, и быстро и бесплодно (почти) там оканчивались.

Нет, конечно, навигация на телефоне полностью перекрывает штатную по функциональности, то же отображение пробок и перекрытий, получаемых по интернету — ультимативный козырь. Но, покатавшись по Польше с штатной автомобильной навигацией, не могу не признать, что при наличии CD с картами в ридере, вождение заметно комфортнее. Просто обидно же, при существовании в природе доступных топооснов в лице OpenStreetMap, Публичной карты Росреестра, https://github.com/nvkelso/natural-earth-vector, не иметь возможности хотя бы просто видеть местонахождение автомобиля на карте на штатном экране.

_bgay4d7elgboyptszuq0zxmutu.jpeg

Всего-то нужно разобраться в закрытом и недокументированном формате хранения информации. Без возможности схитрить и «подглядеть» с IDA или radare2 процесс обращения к этим данным — данные читаются автомобильным устройством. Без пути декомпилировать это навигационное приложение — прошивку навблока. Без спецификаций, документации, справочников и советов сообщества, за отсутствием такого. Да неизвестна даже архитектура процессора, на котором работает приложение, читающее эти данные. Без варианта посмотреть «а что будет, если вот этот байт изменить?» даже не от того, что запись образа CD занимает время, а от того, что этих данных — почти компакт-диск, и попытка скормить «видоизмененные данные» со значительной вероятностью приводит к тому, что информация с диска распознается, как непригодная.

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

С другой стороны, согласитесь, какой красивый вызов: расковырять практически абсолютный черный ящик, у которого есть только вход. У Жан-Франсуа Шампольона был хотя бы розеттский камень, у меня — только понимание, что данные используются компьютером, и там внутре у неё карта.

Что человек ни построил бы, другой завсегда разобрать сможет. В цикле статей постараюсь рассказать наглядно и пошагово, как можно колупать такие орехи: провести реверс-инжиниринг данных известного назначения, но неизвестного формата, на основе проанализированных данных восстановить алгоритмы работы программы. И рассказать о великолепном 010Editor — на Habr он всего пяток раз упоминался мимоходом — в виде понятного Tutorial на реальном примере.

Уровень изложения — максимально доступный для знающих любой язык программирования (не гарантируется для 1с, ДРАКОН, Перфолента.NET), основы операций с типами данных C и готовых смириться с постулатом шарообразности Земли и вытекающим из него понятием географических координат.

Данные

Под анализ попали три варианта карты, 3 CD:

  • Вышеупомянутый давно ходящий по сети образ диска с картой восточной Европы, в т.ч. и РФ и Белоруссии, далее carindb_rus или «русский вариант» — потому как иных вариантов с РФ мне найти не удалось. Только основные дороги, нет лесов, карта достаточно неряшливая, и масштаб практически без улиц в городах. Вероятно кто-то когда то на официальном инструменте попробовал сформировать тестовый файл европейской части РФ и прилегающих стран — и результат ушел в народ.

  • CARiN- and VDODayton navigation 2013, CD3 EastEurope_13_14, официальный выпуск навигации, подробные отличные карты Болгарии, Чехии, Эстонии, Хорватии, Латвии, Венгрии, Польши, Румынии и Словении, далее carindb_ee

  • CARiN- and VDODayton navigation 2013, CD1 Benilux_13_14, официальный выпуск навигации, подробные отличные карты Бельгии, Люксембурга и Нидерландов, далее carindb_bnl

Навигационные CD содержат несколько файлов: небольшие текстовые ABSTRACT, BIBLIOGR, COPYRIGH, содержимое которых описывается их названием, и занимающий основное пространство бинарный carindb, (на официальных дисках есть еще файл CARINET размером примерно 1/10 от carindb, содержащий расшифровку сообщений системы радиооповещения RDS CARINET, но не буду забегать вперед, этот файл не так важен для собственно навигации).

Картографические и навигационные данные находятся в carindb.

Если я говорю carindb, понимать, как carindb_rus, экономлю 4 байта.

010 Editor

Для анализа формата данных самый удобный, на мой взгляд, инструмент — программа 010 Editor. Платная, под win, linux, macos, с месячным триальным периодом. Не самый восхитительный редактор скриптов и темплейтов, недружелюбный к русскому даже в комментариях, довольно тяжелый, не сравнить с молниеносным HxD, порой подвисающий и подбагивающими float окнами. Но зато возможности задавать С-подобным синтаксисом структуры данных и логику, расцвечивать в отображении bin, ввод-вывод при «распознании», поддерживаются размеры файлов за 50Гб, наглядный вывод значений каждой единицы данных, и прочее и прочее — невыразимо восхитительна. Своих $50 за домашнюю лицензию (и $130 за коммерческую) безусловно стоит. В него еще встроено использование репозитория с шаблонами описания различных форматов — и чего там только нет. Разве что VDO Dayton navsystem data нет. Разработчики редактор позиционируют, как World’s Best Hex Editor, и я соглашусь с этим мнением.

В 010Editor файл для анализа отображается в hex — окне, его можно разметить созданным пользователем (или загруженным из облачного репозитория) темплейтом.
Темплейты — это пользовательские описания структуры данных на С-подобном интерпретируемом языке 010Editor, хранимые в файлах с расширением .bt. Декларация «переменной» после исполнения (F5) темплейта на открытом бинарнике приводит к её появлению на закладке Variables. Если имя переменной используется неоднократно, то во вкладке Variables, результатах выполнения темплейта, оно будет представлено, как элемент массива. При клике мышкой на переменные в этой вкладке, фокус в окне просмотра hex сместится на соответствующее место, выделив выбранные данные. Внутренний курсор разметки после объявления переменной переместится на следующий после неё байт, и следующая переменная будет начинаться с этого места. При объявлении переменных в темплейте можно к ним объявить дополнительные свойства-атрибуты, например, bgcolor или fgcolor (выделят в hex окне визуально местоположение соответствующей переменной). Если в описании переменной предварительно указано ключевое слово local, то переменная будет присутствовать в Variables, но не будет воспринята, как часть разметки данных в hex.

image-loader.svg

Структура данных в carindb, блоки.

BigEndian

Просматривая в hex carindb, бросается в глаза, что данные расположены порциями — начинаются с адреса, кратного 0×800, затем заканчиваются и до следующего кратного, идут 00.
Темплейтом вывожу DWORD через каждые 0×800, первые 5 значений:

0x00000000 : 01000000
0x00000800 : 01010000
0x00001000 : 01020000
0x00001800 : 01030000
0x00002000 : 02040000

Сильно похоже (если продолжить дальше по hex), тут BigEndian (привет, Motorolla?), порядок байт, не обратный, как у Intel, а прямой. Добавляю в начале темплейта директиву обработки значений, как BigEndian ().

image-loader.svg

Структура BL_ADDR — адрес блока

Для тех размеченных как DWORD записей, что расположены после нулевой информации, первые 3 байта равны смещению / 0×800, 4й байт — размер информационного блока в 0×800 байт.
Язык темплейтов позволяет описывать пользовательские структуры, и даже, как битовые поля. Первые 24 бита 32 битной структуры нарекаю адресом, последние 8 — размером. В темплейте размечаю этой структурой BL_ADDR — переменной begin_block только те места, где begin_block.addr == смещению от начала hex, деленного на 0×800 (деление заменил правым смещением на 11 бит).

image-loader.svg

include и самодиагностика валидности структур

Можно вынести описания структур данных в отдельный файл, а в темплейте подключить его стандартной для препроцессора С #include "inc_common.bt"

image-loader.svg

Кое-что в структуре изменил. При объявлении addr и size, задаю оранжевый фон и контрастный цвет. Добавились три локальных, рассчитываемых, не отображаемых на hex переменных структуры — raw, offset и is_valid. Их значения используются в том числе и для того, чтобы on-fly проверять -, а являются ли размеченные структурой BL_ADDR данные в hex действительно адресом начала блока? У объявленной структуры появился атрибут read со значением Read_BL_ADDR — это имя автоматически вызываемой при каждом BL_ADDR функции, которая должна возвратить строковое значение, которое будет отображаться в колонке Value во вкладке Variables. Параметр этой функции — конкретный экземпляр структуры BL_ADDR a. И если данные не валидны, это будет отображено в колонке Value.

В основном темплейте добавил аттрибуты скрытия из вкладки Variables у локальных переменных i и data, и после вызова цикла пару раз разметил данные в hex, как BL_ADDR non_val_begin — рассчитывая на заведомо невалидные значения для иллюстрирования, как работает добавленная проверка валидности данных.

image-loader.svg

И неожиданный результат — значение по смещению 0×9804 внезапно оказывается валидным BL_ADDR, расположенным где-то по адресу 0×00981000. Запомним.

Что после адреса, структура BL_HEAD

Увеличиваю максимальный адрес i до 0×400000, и пробегаю в поисках валидных BL_ADDR, Printf-ом вывожу смещение, размер блока и следующий за BL_ADDR DWORD something (в hex — на салатовом фоне).

image-loader.svg

У something везде первый, третий и четвертый байт — нули, а у второго — ненулевое значение. И это значение меняется как 12h — 13h — 7h — bh — ah — 3 раза dh — далее все ch (h — hex — шестнадцатеричные).
Более того, если везде всё так одинаково после BL_ADDR блока, то заведу новую структуру BL_HEAD для начала блока в include файле. Сначала в этой структуре идёт BL_ADDR addr, затем четыре байта с именами эмммм… Ну, пусть zero_aligment, type, is_compressed и uncompressed_size. Локальные переменные структуры — аналогичный BL_ADDR признак is_valid, и временный пойнтер tmp_ptr. Обработка is_valid очевидна и откомментирована. В tmp_ptr хранится адрес, куда возвращаться после определения самой последней переменной блока here_last_byte. Атрибутивная функция string Read_BL_HEAD (BL_HEAD &a) аналогична той, что и для структуры BL_ADDR.

image-loader.svg

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

image-loader.svg

Невалидный BL_HEAD отрабатывает верно, и в Value предупреждение, и цвет красный, но неожиданно BL_ADDR non_valid_begin[1] с raw = 0×004d130d — проходит проверку, по адресу 0x004d13*0x800 записаны ровно те же цифры, что и в raw.

enum, EnumToString, статистика и распределение типов в carindb

Добавлю локальную переменную type в BL_ADDR, которая будет читать значение +2 байта за BL_ADDR — т.е. быть равной type соответствующего BL_HEADER. И заведу перечисление en_BL_TYPE для этих type c элементом ABSTRACT, равным 12h, типу самого первого блока и элементом Invalid, со значением 0xFF, которое в BL_ADDR у type по умолчанию. Изменяю Read_BL_ADDR и Read_BL_HEAD, используя EnumToString (замечательная функция, возвращающая строковое название числа из перечисления).

И переписываю основной темплейт, задача — посмотреть, как распределяются блоки во всём файле (верхний предел i — FileSize), и сколько каких типов блоков.

image-loader.svg

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

File size=1EA2E000				Max block size = 16*0x800

 Offset  Type Qty                Type  Qty
0x00000000 12 1                 0x00  15329  
0x00000800 13 1                 0x01  5279  
0x00001000 07 1                 0x02  5809  
0x00001800 0B 1                 0x03  5867  
0x00002000 0A 1                 0x04  --
0x00003000 0D 3                 0x05  --
0x00010800 0C 692               0x06  5198  
0x011F6000 0F 31                0x07  1  
0x012EA000 0E 1114              0x08  26  
0x02401800 11 145               0x09  7712  
0x02763800 10 1524              0x0A  1  
0x048A2000 08 1                 0x0B  1  
0x048A2800 09 9                 0x0C  692  
0x048BC800 06 5198              0x0D  3  
0x055E0000 08 17                0x0E  1114  
0x05620800 09 7192              0x0F  31  
0x0643F800 00 15329             0x10  1524  
0x127BF800 08 1                 0x11  145  
0x127C1000 09 169               0x12  1  
0x1281C000 03 5867              0x13  1  
0x13C2F000 08 1                 0x14  324  
0x13C30800 09 169               0x15  4097  
0x13C8A800 02 5809              0x16  15817  
0x15070800 08 1                 0x17  --
0x15071000 09 54                0x18  --
0x1509C800 01 5279              0x19  --
0x16335000 08 1                 0x1A  --
0x16335800 09 86                0x1B  --
0x16365800 16 15817             0x1C  1095  
0x1C36A000 08 1                 0x1D  114  
0x1C36A800 09 26                0x1E  --
0x1C37A000 15 4097              0x1F  --
0x1E00A800 08 1
0x1E00B000 09 3
0x1E010000 1C 1095
0x1E6E5800 08 1
0x1E6E6000 09 3
0x1E6EA000 14 324
0x1E90D800 08 1
0x1E90E000 09 1
0x1E910800 1D 114

Капитан очевидность:

  • Присутствует логика группировки типов в теле carindb.

  • Явно просматривается последовательность типов 08h → 09h → XXh.

  • Максимальное значение номера типа 0×1D.

  • В последовательности нумерации типов некоторые (0×04, 0×05, 0×17, 0×18, 0×19, 0×1A, 0×1B) отсутствуют.

  • Больше всего типов 0×16 и 0×00

  • Но есть и присутствующие в единичных экземплярах (0×12, 0×13, 0×07, 0×0B, 0×0A), в основном вначале файла.

Темплейт отрабатывает аналогично на carindb_ee или carindb_bnl. Почти так же — у официальных карт появляются дополнительные типы, которых не было в carindb_rus. На будущее сохраняю темплейт под именем «util_vdo_stat.bt»

Итак

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

Созданы две симулятивно-интеллектуалных (притворяющихся типа умными) типа структур данных, характерных для файла carindb.

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

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

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

Попутно даны начальные сведения для работы с 010Editor.

Слона, к которому непонятно было, как подступиться, нарезал на более мелкие куски. Дальнейший анализ — в следующей статье

© Habrahabr.ru