Наименьшее количество байтов для идентификации файла - PullRequest
0 голосов
/ 25 января 2019

В настоящее время я работаю над небольшим сайд-проектом, который оказывается немного сложным.Это настройка: у меня довольно старый процессор, который используется в различных продуктах.Существует около 500 различных версий прошивок для различных приложений.Иногда они отличаются на несколько байтов ~ 1k, в других случаях только 5%.Теперь я хотел бы идентифицировать каждую версию, создав для нее уникальный идентификатор.У меня есть бинарный файл firmewares, доступный в виде файлов для работы и обучения.

Цель состоит в том, чтобы при появлении любого устройства я хотел зачитать как можно меньше байтов установленной прошивки с момента подключениядовольно медленный с 9600 бод.Несмотря на то, что общее количество микропрограммного обеспечения составляет всего около 64 КБ, полное его чтение занимает довольно много времени (~ 5 минут из-за перегрузки протокола, тактовой частоты и т. Д.)сохраненные файлы прошивки и определяет, какие из его байтов могут быть использованы для его уникальной идентификации.Всякий раз, когда приходит устройство, оно считывает каждый из этих байтов отпечатка пальца один, а другой, почти как старый текстовый прогноз T9, чтобы сузить кандидатов до тех пор, пока не найдет правильную прошивку.Для этого мне нужно создать базу данных, которая содержит наиболее оптимизированный набор байтов отпечатков пальцев.Но как это тренировать?Как найти наиболее значимые байты более 500 файлов?

До сих пор я пытался статистически проанализировать файлы и найти верхние 50 байтов, которые больше всего отличаются между файлами.Проблема в том, что даже взяв 50 байтов, я получаю несколько версий, которые создают один и тот же хэш.

Любые предложения или алгоритмы, которые могут решить проблему, будут очень приветствоваться!Если у вас есть идея для совершенно другого подхода к этому, я хотел бы услышать это!

1 Ответ

0 голосов
/ 25 января 2019

Определите все позиции байтов, где значения могут отличаться. Затем найдите «наиболее эффективный разделитель», то есть позицию, в которой при измерении значения будет разбит текущий набор на наименьшие подмножества (в смысле minmax) или на более многочисленные подмножества.

Затем повторите всю процедуру с каждым подмножеством, рекурсивно. Это даст дерево решений, дающее вам (надеюсь, короткие) последовательности байтов для тестирования.

Это эвристический подход, возможно, неоптимальный, и я надеюсь

  • что процедура вычисления не слишком длинная (хотя она будет выполнена раз и навсегда),
  • что это не слишком далеко от оптимума.

Если предположить, что каждое разбиение сбалансировано, но каждый раз приводит к двум подмножествам, тестовые последовательности не будут превышать 10 байтов.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...