Найти совпадающие последовательности в двух бинарных файлах

Question

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

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

A сейчас, для фактического вопроса.

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

Я пробовал следующее в 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

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

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

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

Answer 2

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

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

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

Answer 3

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

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

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

Answer 4

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

Answer 5

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

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