Найти подходящие последовательности в двух двоичных файлах

Question

Позвольте мне начать с небольшого фона.

Этим утром один из наших пользователей сообщил, что установочный файл Testuff был объявлен зараженным антивирусом CA. Уверенный, что это был ложный положительный результат, я заглянул в Интернет и обнаружил, что пользователи другой программы (SpyBot) сообщили об этой же проблеме.

А сейчас, по актуальному вопросу.

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

Я попробовал следующее в Python, но он уже давно запущен, и мне было интересно, есть ли лучший или более быстрый способ.

from difflib import SequenceMatcher

spybot = open("spybotsd160.exe", "rb").read()
testuff = open("TestuffSetup.exe", "rb").read()

s = SequenceMatcher(None, spybot, testuff)
print s.find_longest_match(0, len(spybot), 0, len(testuff))

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

Answer 1

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

Использование perl Tree :: Suffix может быть самым простым решением. По-видимому, он дает все общие подстроки в указанном диапазоне длин:

@lcs = $tree->lcs;
@lcs = $tree->lcs($min_len, $max_len);
@lcs = $tree->longest_common_substrings;

Answer 2

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

Answer 3

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

Если вы заинтересованы в этом - здесь .ps документ, связанный здесь , вы можете найти хорошее введение в эту тематику.

Если существует хорошая реализация для этих алгоритмов, я не могу сказать.

Answer 4

Почему бы вам не связаться с CA и не попросить их рассказать, что они ищут для этого вируса?

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

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

Answer 5

Я подозреваю, что поиск двоичных строк не поможет вам. Программа установки, вероятно, будет делать некоторые «подозрительные» вещи.

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