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

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

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

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

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

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

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

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

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

Моя идея:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Две мысли:

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

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

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

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

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

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