Расчет бинарных данных

Question

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

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

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

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

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

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

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

Answer 1

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

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

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

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

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

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

Answer 2

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

Answer 3

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

Моя идея:

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

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

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

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

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

Answer 4

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

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

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

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

1. Приоритеты сравнений основаны на том, насколько похожи сжатые размеры. Если ROM A имеет сжатый размер 10 МБ, а ROM B имеет сжатый размер 2 МБ, они не могут быть похожими более чем на 20%, поэтому сравнение их для получения реального результата можно оставить на потом. Выполнение одного и того же алгоритма сжатия для очень похожих файлов приводит к результатам аналогичного размера, поэтому очень быстро находит множество клонов.

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

Answer 5

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

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

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

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

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

Answer 6

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

Answer 7

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

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

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

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

Answer 8

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

Answer 9

Две мысли:

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

Answer 10

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

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

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

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