2つのバイナリファイルで一致するシーケンスを見つける

Question

少しの背景から始めましょう。

今朝私たちのユーザーのうちの1人は、TestpassのセットアップファイルがCAアンチウイルスによってウイルスに感染していると報告していました。これが偽陽性であると確信して、Webを見て、別のプログラム（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

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と話をする必要があります。