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

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

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

Проблема, над которой я работаю, - это обнаружение клона для изображений ROM для видеоигр. Для тех, у кого нет опыта эмуляции, ПЗУ представляют собой отвалы данных на игровых картриджах. ПЗУ "клон" обычно представляет собой модифицированную версию той же игры, наиболее распространенным типом которой является переведенная версия. Например, японская и английская версии оригинальной Final Fantasy для NES являются клонами. Игры разделяют почти все их активы (спрайты, музыка и т.д.), Но текст был переведен.

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

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

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

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

Ответ 1

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

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

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

Построение хешей, полезных для общего случая, было продолжением темы исследований в CS в течение нескольких лет. Библиотека LSHKit реализует некоторые алгоритмы такого рода. Доступная в Интернете бумага НАЙТИ СХОДНЫЕ ФАЙЛЫ В БОЛЬШОЙ СИСТЕМЕ ФАЙЛОВ кажется, что она может быть нацелена больше на сравнение текстовых файлов, но может быть вам полезна. В более поздней работе хэширование сходства с несколькими разрешениями описывается более мощный алгоритм. Однако он не доступен без подписки. Вероятно, вы захотите сохранить статью wikipedia в Locality Sensitive Hashing, когда вы просматриваете другие ресурсы. Они все становятся довольно техничными, а сам вход в википедию довольно тяжелый. В качестве более удобной альтернативы вы можете применить некоторые идеи (или даже исполняемые файлы) из поля Acoustic Fingerprinting.

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

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

Ответ 2

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

Ответ 3

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

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

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

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

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

Ответ 4

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

Моя идея:

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

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

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

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

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

Ответ 5

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

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

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

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

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

Ответ 6

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

Ответ 7

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

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

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

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

Ответ 8

Две мысли:

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

Ответ 9

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

Ответ 10

Трудность здесь состоит в том, что, поскольку вы имеете дело с исполняемым кодом, простые изменения могут распространяться по всему ПЗУ. Адреса и смещения для значений ALL могут изменяться с добавлением одной переменной или инструкцией no-op. Это сделает даже хэширование на основе блоков бесполезным.

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

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

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