Вычисление сходства двоичных данных

https://stackoverflow.com/questions/579981

06-09-2019
|

Вопрос

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

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

Проблема, над которой я работаю, заключается в том, Обнаружение клонов образов ПЗУ видеоигр.Для тех, у кого нет опыта эмуляции, ПЗУ представляют собой дампы данных на игровых картриджах.«Клон» ПЗУ обычно представляет собой модифицированную версию той же игры, причем наиболее распространенным типом является переведенная версия.Например, японская и английская версии оригинала. Последняя фантазия для NES это клоны.В играх используются почти все ресурсы (спрайты, музыка и т. д.), но текст переведен.

В настоящее время существует несколько групп, которые занимаются ведением списков клонов для различных систем, но, насколько я могу судить, все это делается вручную.Я пытаюсь найти метод автоматического и объективного обнаружения похожих образов ПЗУ на основе сходства данных, а не «это похоже на одну и ту же игру».Существует несколько причин для обнаружения клонов, но одна из основных – их использование вместе с Твердое сжатие.Это позволяет сжимать все клоны игр в один архив, при этом весь сжатый набор клонов часто занимает лишь немного больше места, чем одно из отдельных ПЗУ.

Некоторые проблемы, которые следует учитывать при разработке потенциальных подходов:

ПЗУ сильно различаются по размеру в зависимости от системы.Некоторые из них небольшие, но в современных системах могут быть большие, 256 МБ и более.Некоторые (все?) системы имеют только степень 2 возможных размеров, игра размером 130 МБ на одной из этих систем будет иметь ПЗУ размером 256 МБ, в основном пустое.Обратите внимание, что из-за этого некоторые клоны могут иметь совершенно разные размеры, если версия игры превышает порог и должна использовать картридж вдвое большего размера.
В настоящее время во многих системах существуют тысячи известных ПЗУ, причем для большинства систем постоянно выпускаются новые.Даже для старых систем существует крупное сообщество хакеров ПЗУ, которое часто создает модифицированные ПЗУ.
Хранение данных о сходстве для каждой возможной пары ПЗУ приведет к появлению миллионов строк данных для любой из наиболее популярных систем.Система с 5000 ПЗУ потребует 25 миллионов строк данных о сходстве, а для одной новой игры потребуется еще 5000 строк.
Состояние обработки должно быть восстанавливаемым, чтобы в случае прерывания она могла продолжиться с того места, где остановилась.При использовании любого метода потребуется большой объем обработки, и предполагать, что все это будет выполняться в одном пакете, небезопасно.
Новые ПЗУ могут быть добавлены в любое время, поэтому метод не должен предполагать, что у него уже есть «полный» набор.То есть, даже после того, как вы уже выяснили сходство всех существующих ПЗУ, в случае добавления нового (а это также могло произойти до полного завершения предыдущей обработки) должен существовать метод сравнения его со всеми предыдущими, чтобы определить клоном которого (если есть) он является.
Более высокая скорость обработки должна иметь приоритет над точностью (до определенной степени).Знание того, являются ли два ПЗУ похожими на 94% или 96%, не особенно важно, но если для сравнения нового ПЗУ со всеми предыдущими потребуется целый день, программа, вероятно, никогда не будет полностью завершена.

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

Решение

Похоже, вам нужна двоичная дельта или, возможно, индекс, полученный в результате применения двоичной дельты (например, ее размера).Затем вы можете сравнить этот индекс с каким-то базовым уровнем, который вы определите экспериментально, чтобы решить, является ли это «клоном» или нет.

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

При этом попарное сравнение каждого двоичного файла в вашей базе данных, вероятно, будет непомерно дорогим (O(n²), Я думаю).Я бы попробовал найти простой хэш для выявления возможных кандидатов для сравнения.Что-то концептуально похожее на то, что предлагают Спденне и Эдуард.То есть найдите хэш, который можно применить к каждому элементу один раз, отсортируйте этот список, а затем используйте более детальное сравнение элементов, хеши которых расположены близко друг к другу в списке.

Создание хэшей, полезных для общего случая, было активно изучаемой темой исследований в CS в течение нескольких лет.А ЛШКит программная библиотека реализует некоторые алгоритмы такого рода.Бумага, доступная в Интернете ПОИСК ПОХОЖИХ ФАЙЛОВ В БОЛЬШОЙ ФАЙЛОВОЙ СИСТЕМЕ похоже, что он больше ориентирован на сравнение текстовых файлов, но может быть вам полезен.Более поздняя статья Хеширование сходства с несколькими разрешениями описывает более мощный алгоритм.Однако, похоже, он недоступен без подписки.Вероятно, вы захотите сохранить статью в Википедии. Хэширование с учетом местоположения удобно при просмотре других ресурсов.Все они довольно технические, а сама статья в Википедии довольно сложна в математике.В качестве более удобной альтернативы вы можете применить некоторые идеи (или даже исполняемые файлы) из области Акустическая дактилоскопия.

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

Если хеш-функции не помогают вам полностью (или они требуют какого-либо ввода для определения метрики/расстояния), то в Интернете доступно несколько двоичных дельта-алгоритмов и их реализаций.Тот, с которым я наиболее знаком, используется системой контроля версий Subversion.Он использует двоичный дельта-алгоритм, называемый xdelta, для эффективного хранения версий двоичных файлов.Вот ссылка непосредственно на файл в их репозитории, который его реализует: xdelta.c.Вероятно, в Интернете есть инструмент, который делает это более доступным.

Другие советы

Возможно, вы захотите посмотреть bsdiff, который представляет собой двоичную систему сравнения/исправления.Есть еще дипломная работа с большим количеством теории.

Используйте некоторые идеи из Обнаружение плагиата алгоритмы.

Моя идея:

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

Не просто хешируйте один раздел, затем следующий раздел, начиная с конца первого раздела, а вместо этого используйте скользящее окно, хэшируя раздел, начиная с 1 байта, затем хешируя раздел того же размера, начиная с байта 2, затем с байта. 3 и т. д.Это сведет на нет эффект изменения размеров частей вашего ПЗУ.

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

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

Сохраните этот график в каждом ПЗУ.Сравните графики частот для двух разных ПЗУ, рассчитав сумму квадратов разницы частот для каждого значения хеш-функции.Если сумма равна нулю, то ПЗУ, скорее всего, будут идентичными.Чем дальше от нуля, тем менее похожими будут ПЗУ.

Хотя прошло гораздо больше, чем «пара дней», я решил, что, вероятно, мне следует добавить сюда свое текущее решение.

Нильс Пипенбринк шел в том же направлении, что и мой нынешний метод.Поскольку одним из основных результатов поиска клонов является огромная экономия от надежного архивирования, я решил, что можно просто попробовать сжать любые два ПЗУ вместе и посмотреть, сколько места сэкономится.Я использую алгоритм LZMA в 7zip для этого.

Первый шаг — сжать каждое ПЗУ по отдельности и записать сжатый размер, затем попытаться заархивировать любые два ПЗУ вместе и посмотреть, насколько полученный размер отличается от их индивидуальных сжатых размеров.Если объединенный размер такой же, как сумма отдельных размеров, они схожи на 0%, а если размер такой же, как у одного из них (самого большого), они идентичны.

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

Расставьте приоритеты в сравнении на основе того, насколько похожи сжатые размеры.Если ПЗУ A имеет сжатый размер 10 МБ, а ПЗУ B имеет сжатый размер 2 МБ, они не могут быть похожими более чем на 20%, поэтому их сравнение для получения реального результата можно оставить на потом.Использование одного и того же алгоритма сжатия для очень похожих файлов обычно приводит к получению результатов одинакового размера, поэтому это позволяет очень быстро обнаружить множество клонов.
В сочетании с вышеизложенным сохраняйте как верхние, так и нижние «границы» возможного сходства между любой парой ПЗУ.Это позволяет дополнительно расставить приоритеты.Если ПЗУ A и B схожи на 95 %, а ПЗУ B и C — только на 2 %, то вы уже знаете, что A и C находятся между 0 % и 7 %.Это слишком мало, чтобы быть клоном, поэтому это сравнение можно смело отложить или даже полностью проигнорировать, если только я действительно не хочу знать точное сходство всего.

Я думаю, что некоторые методы, заимствованные из сжатия данных, могут быть здесь интересны:

Предположим, у вас есть два файла: A и B.

Сожмите каждый файл по отдельности и сложите сжатые размеры вместе.Затем объедините два файла в один большой файл и также сожмите его.

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

Я предлагаю вам попробовать преобразование Берроу Уиллера (bzip2) для сжатия.Большинство других алгоритмов сжатия имеют лишь ограниченную историю.Алгоритм BWT otoh может работать с очень большими фрагментами данных.Алгоритм «видит» оба файла одновременно, и любое сходство приведет к более высокой степени сжатия.

XDelta очень полезен для получения приличных двоичных различий: http://xdelta.org

Вы можете начать с сохранения чего-то вроде хэш-деревья.Необходимо хранить только один такой набор хешей для каждого ПЗУ, а необходимое пространство для хранения только пропорционально (но намного меньше) размеру ПЗУ, при условии постоянного размера блока.Выбранный размер блока должен обеспечивать достаточную степень детализации для обеспечения точности, например:для минимального размера 128 МБ, ограничение точности 1% и Хэш Тигр-128 (аналогично тому, что используют для проверки файлов, передаваемых через DirectConnect), размер блока в 1МиБ вполне подойдет и можно хранить все хеши в 128*128/8=2048 байт!Таким образом, для 10 000 ПЗУ потребуется всего около 20 МБ пространства.Кроме того, вы можете выбрать менее безопасный, но более быстрый и/или меньший хэш.Добавление/проверка сходства нового ПЗУ повлечет за собой что-то вроде:

Разделите новое ПЗУ на блоки и хэшируйте каждый из них.
Для каждого ПЗУ, уже находящегося в базе данных, сравните (см. ниже) его хэши с хэшами нового ПЗУ.

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

Как видите, проблема сводится к более простой с точки зрения производительности:проверка гораздо меньших наборов данных на сходство.

Две мысли:

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

Как сказал Уэйлон Флинн, вам может понадобиться двоичный дельта-алгоритм.А алгоритм rsync хороший.Это быстро и надежно.См. также документация утилиты.

Сложность здесь в том, что, поскольку вы имеете дело с исполняемым кодом, простые изменения могут распространиться по всему ПЗУ.Адреса и смещения для ВСЕХ значений могут измениться при добавлении одной переменной или бездействующей инструкции.Это сделает бесполезным даже блочное хеширование.

Быстрым и грязным решением было бы взломать решение с помощью разница в библиотеке (или его эквивалент на вашем любимом языке), поскольку он дает вам скользящее сравнение, позволяющее добавлять или удалять данные.Разделите ПЗУ на разделы исполняемых файлов и данных (если возможно).Раздел данных можно сравнивать напрямую и рассчитан коэффициент сходства, хотя у вас все равно будут проблемы с адресами или смещениями.

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

К сожалению, это по-прежнему операция O(n^2) над количеством отслеживаемых ПЗУ, но ее можно облегчить с помощью (инкрементной) кластеризации или порядка сравнения на основе частоты, чтобы уменьшить количество необходимых сравнений.

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow