Система с известной спецификацией реакций на входные воздействия и неизвестным содержимым характеризуется как черный ящик. Когда внутренняя структура, устройство и архитектура системы известны, - ящик белый. Есть и промежуточное понятие - серый ящик, частичное знание внутреннего устройства и ожидаемое поведение.
Как охарактеризовать систему, выходные реакции которой очевидны, но нет информации о входных данных, вызывавших эти реакции? Я сейчас про компьютеры, а не о психологии или медицине. Строго говоря, входные данные не просто есть, они присутствуют в полном спектре возможных вариантов, но целиком, глыбой, блобом, а реакция происходит на отдельную неизвестную часть (части) входных данных.
По аналогии с ящиками для этого рассказа я отважно назвал такую систему именем четырехмерного ящика - черным тессерактом. Ну, во-первых, это красиво(с). Черный - за неизвестные входные спецификации. Четвертое измерение - из-за того, что конечные данные устройства автомобильной навигации выдают в виде изображений, попытка компьютеризированного анализа результатов вывода бессмысленна и беспощадна. А процесс реверс-исследований затягивает, как наблюдение за проекцией тесерракта на 2D: только стало понятно, как всё устроено, но потом он чуть поворачивается....
Давным-давно, в одной далекой галактике...
Началась история, когда в 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, не иметь возможности хотя бы просто видеть местонахождение автомобиля на карте на штатном экране.
Всего-то нужно разобраться в закрытом и недокументированном формате хранения информации. Без возможности схитрить и "подглядеть" с 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.
Структура данных в carindb, блоки
BigEndian
Просматривая в hex carindb, бросается в глаза, что данные расположены порциями - начинаются с адреса, кратного 0x800, затем заканчиваются и до следующего кратного, идут 00.
Темплейтом вывожу DWORD через каждые 0x800, первые 5 значений:
0x00000000 : 01000000
0x00000800 : 01010000
0x00001000 : 01020000
0x00001800 : 01030000
0x00002000 : 02040000
Сильно похоже (если продолжить дальше по hex), тут BigEndian (привет, Motorolla?), порядок байт, не обратный, как у Intel, а прямой. Добавляю в начале темплейта директиву обработки значений, как BigEndian().
Структура BL_ADDR - адрес блока
Для тех размеченных как DWORD записей, что расположены после нулевой информации, первые 3 байта равны смещению / 0x800, 4й байт - размер информационного блока в 0x800 байт.
Язык темплейтов позволяет описывать пользовательские структуры, и даже, как битовые поля. Первые 24 бита 32битной структуры нарекаю адресом, последние 8 - размером. В темплейте размечаю этой структурой BL_ADDR - переменной begin_block только те места, где begin_block.addr == смещению от начала hex, деленного на 0x800 (деление заменил правым смещением на 11 бит).
include и самодиагностика валидности структур
Можно вынести описания структур данных в отдельный файл, а в темплейте подключить его стандартной для препроцессора С #include "inc_common.bt"
Кое-что в структуре изменил. При объявлении 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 - рассчитывая на заведомо невалидные значения для иллюстрирования, как работает добавленная проверка валидности данных.
И неожиданный результат - значение по смещению 0x9804 внезапно оказывается валидным BL_ADDR, расположенным где-то по адресу 0x00981000. Запомним.
Что после адреса, структура BL_HEAD
Увеличиваю максимальный адрес i до 0x400000, и пробегаю в поисках валидных BL_ADDR, Printf-ом вывожу смещение, размер блока и следующий за BL_ADDR DWORD something (в hex - на салатовом фоне).
У 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.
Цикл темплейта завершается на середине блока данных, если прописать несколько BL_ADDR или BL_HEAD, они будут находиться заведомо не в положенных местах, и самопроверка должна окрасить фон красным.
Невалидный BL_HEAD отрабатывает верно, и в Value предупреждение, и цвет красный, но неожиданно BL_ADDR non_valid_begin[1] с raw = 0x004d130d - проходит проверку, по адресу 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), и сколько каких типов блоков.
Чуть отредактировал руками для хабра результат вывода в консоль - перенес колонки информации о количестве блоков правее.
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.
Максимальное значение номера типа 0x1D.
В последовательности нумерации типов некоторые (0x04, 0x05, 0x17, 0x18, 0x19, 0x1A, 0x1B) отсутствуют.
Больше всего типов 0x16 и 0x00
Но есть и присутствующие в единичных экземплярах (0x12, 0x13, 0x07, 0x0B, 0x0A), в основном вначале файла.
Темплейт отрабатывает аналогично на carindb_ee или carindb_bnl. Почти так же - у официальных карт появляются дополнительные типы, которых не было в carindb_rus. На будущее сохраняю темплейт под именем "util_vdo_stat.bt"
Итак
Выяснено, что числовые данные в файле carindb сгруппированы в блоки различных типов.
Созданы две симулятивно-интеллектуалных (притворяющихся типа умными) типа структур данных, характерных для файла carindb.
BL_ADDR проверяет, что данные по адресу, который несет его значение, являются началом блока, и читает тип этого блока.
BL_HEADER проверяет, что он сам располагается по адресу, на который указывают значения его данных.
Написана утилита-темплейт, выводящая информации о распределении блоков внутри carindb, максимальный размер блока и информации о количестве каждого типа.
Попутно даны начальные сведения для работы с 010Editor.
Слона, к которому непонятно было, как подступиться, нарезал на более мелкие куски.
Дальнейший анализ - в следующей статье.
