ファイル比較のためのJavaのプログラムアプローチ

Question

類似性について、2つの16進数ファイルの署名を互いに比較するための最良のアプローチは何ですか。

より具体的には、私がやりたいことは、.exeファイルの16進表現を取り、一連のウイルス署名と比較することです。このアプローチでは、ファイル（EXE）HEX表現をN CHARの個々のグループ（つまり、10ヘクスCHARS）に分割し、ウイルスの署名で同じことをすることを計画しています。私はある種のヒューリスティックを実行することを目指しているため、このEXEファイルが既知のウイルス署名に対する類似性のx％があるかどうかを統計的に確認します。

私がこれを行うことを考えた最も単純でおそらく非常に間違った方法は、exe [n、n-1]をウイルス[n、n-1]と比較することです。 9] virus1 [0,9]に対して。各サブセットは統計的に格付けされます。

ご存知のように、膨大な数の比較があるので、非常に遅いです。そこで、私はあなたがそのような比較を行うためのより良いアプローチを考えることができるかどうかを尋ねると思いました。

これは、多型マルウェアを検出するためのアルゴリズムを開発しようとしている私のBSCのために行っているプロジェクトのためです。これはシステム全体の一部にすぎません。もう1つは静的ウイルス署名を進化させる遺伝的アルゴリズムに基づいています。リソースなどのアドバイス、コメント、または一般的な情報は大歓迎です。

---

意味: ：Polymorphic Malware（ウイルス、ワームなど）は、「元の」バージョンと同じ機能とペイロードを維持しますが、明らかに異なる構造（バリアント）を持っています。彼らはコードの難読化によってそれを達成し、したがって彼らの六角署名を変更します。多型に使用される手法のいくつかは次のとおりです。フォーマットの変更（ブランクの削除を挿入）、変数の名前変更、ステートメント再配置、ジャンクコードの追加、ステートメント置換（x = 1はx = y/5にy = 5に変更）、コントロールステートメントのスワッピング。インフルエンザウイルスが変異しているため、ワクチン接種が効果的ではないように、検出を避けるために多型のマルウェアが変異します。

---

アップデート： アドバイスの後、皆さんは読書をすることに関して私に与えてくれました。私はそれをしましたが、それはやや混乱しました。次のような問題に適用できる距離アルゴリズムをいくつか見つけました。

• 最長の一般的なサブシーケンス
• levenshteinアルゴリズム
• Needleman – Wunschアルゴリズム
• スミス - ウォーターマンアルゴリズム
• ボイヤームーアアルゴリズム
• Aho Corasickアルゴリズム

しかし今、私はどちらを使うべきかわからない、彼らはすべて異なる方法で彼と同じことをしているようだ。私はそれぞれをよりよく理解できるように、研究を続けます。しかし、その間にあなたは私にあなたの意見を与えてくれませんか which might be more suitable 私は私の研究中にそれを優先し、それをより深く研究することができるように。

---

更新2： 結局、LcSubsequence、Lcsubstring、Levenshtein距離の融合を使用しました。提案ありがとうございます。

完成した紙のコピーがあります github

Answer 1

このようなアルゴリズムについては、バイオインフォマティクス領域を調べることをお勧めします。特定の署名（遺伝子、特別なよく知られている短いベースシーケンスなど）を探している大きなファイル（ゲノムシーケンス）があるという点で、同様の問題設定があります。

また、多型のマルウェアを考慮するために、このセクターはあなたに多くを提供するはずです。なぜなら、生物学では、正確な一致を得ることも同様に難しいと思われるからです。 （残念ながら、私はあなたを指摘するための適切な近似検索/マッチングアルゴリズムを知りません。）

この方向の一例は、 Aho Corasick いくつかのマルウェア署名を同時に検索するためのアルゴリズム。

同様に、のようなアルゴリズム ボイヤー・ムーア アルゴリズムは、特にサイズM、つまりサブリン検索時間のパターンを探すサイズNのテキストの長いシーケンス（n/mの平均ケース（n/m）の平均的なシーケンス（n/m）の素晴らしい検索ランタイムを提供します。

Answer 2

WebSearchのコンテキストで、文書の大規模なコーパスに近い文書に近い文書を見つけることについて、多くの論文が公開されています。あなたはそれらが便利だと思うと思います。たとえば、これを参照してください プレゼンテーション.

Answer 3

最近、バグリポジトリの重複バグレポートの検出を自動化するための深刻な研究がありました。これは本質的にあなたが直面している問題と同じです。違いは、バイナリデータを使用していることです。パターンにはわずかな違いがある場合でも、同じ基本的なパターンを持つ文字列を探しているため、同様の問題です。まっすぐな距離アルゴリズムは、おそらくここではうまくいかないでしょう。

このペーパーでは、問題の適切な要約と、試された引用のいくつかのアプローチを示しています。

ftp://ftp.computer.org/press/outovering/proceedings/patrick/apsec10/data/4266a366.pdf

Answer 4

誰かが指摘したように、既知の文字列とバイオインフォマティクスの問題との類似性が役立つかもしれません。最も長い一般的なサブストリングは非常に脆く、1つの違いがそのような弦の長さを半分にすることができることを意味します。ストリングアライメントの形式が必要ですが、スミスウォーターマンよりも効率的です。 Blast、Blat、Mummer3などのプログラムを見て、あなたのニーズに合うかどうかを確認しようとします。これらのプログラムのデフォルトのパラメーターは、生物学的アプリケーション（たとえば挿入または置換をペナルティする量）に基づいていることを忘れないでください。したがって、おそらくアプリケーションドメインに基づいてパラメーターの再推定パラメーターを再推定することを検討する必要があります。トレーニングセット。これは、生物学であっても、異なるアプリケーションが異なるパラメーターを必要とするため（たとえば、2つのゲノムの進化距離に基づいて比較するため）、これは既知の問題です。ただし、デフォルトでも、これらのアルゴリズムの1つが使用可能な結果が生じる可能性があります。何よりも、ウイルスがどのように変化するかの生成モデルを持つことであり、距離と比較アルゴリズムの最適な選択であなたを導くことができます。