Вычисление подобия двоичных данных

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

Предполагают, что у Вас есть два файла, A и B.

Сжатие каждый файл индивидуально и добавляют сжатые размеры вместе. Затем свяжите эти два файла в единственный, большой файл и сожмите его также.

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

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

XDelta довольно полезен для получения достойного двоичного файла diffs: http://xdelta.org

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

Моя идея:

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

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

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

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

Хранилище этот график на ROM. Сравните графики частоты для двух различных ROMs путем вычисления суммы квадратов различия в частотах для каждого значения хэш-функции. Если это суммирует для обнуления тогда ROMs, то вероятно, будут идентичны. Еще дальше от нуля это, менее подобное, которым будет ROMs.

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

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

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

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

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

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

Nils Pipenbrinck входил в то же направление как мой существующий метод. Так как одним из основных результатов нахождения клонов являются огромные сбережения от серьезной архивации, я полагал, что мог просто попытаться сжать любые два ROMs вместе и видеть, сколько свободного места было оставлено. Я использую алгоритм LZMA в 7zip для этого.

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

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

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

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

Две мысли:

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

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

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

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

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

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