10

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

具体的には、.exeファイルの16進表現を取得し、一連のウイルス署名と比較することです。このアプローチでは、ファイル（exe）の16進表現をN文字の個々のグループ（つまり、10の16進文字）に分割し、ウイルス署名でも同じことを行う予定です。私はある種のヒューリスティックを実行することを目指しているので、このexeファイルが既知のウイルスシグネチャに対してX％の類似性を持っているかどうかを統計的にチェックします。

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

ご存知のように、膨大な数の比較が行われるため、非常に時間がかかります。そこで、たとえば、異なるデータ構造を一緒に実装するなど、そのような比較を行うためのより良いアプローチを考えられるかどうかを尋ねたいと思いました。

これは、ポリモルフィックマルウェアを検出するアルゴリズムを開発しようとしている私の理学士のために行っているプロジェクトです。これはシステム全体の一部にすぎず、もう一方は静的ウイルスシグネチャを進化させる遺伝的アルゴリズムに基づいています。アドバイス、コメント、またはリソースなどの一般的な情報は大歓迎です。

定義：ポリモルフィックマルウェア（ウイルス、ワームなど）は、明らかに異なる構造（バリアント）を持ちながら、「元の」バージョンと同じ機能とペイロードを維持します。彼らは、コードを難読化し、16進署名を変更することでそれを実現しています。ポリモーフィズムに使用される手法のいくつかは次のとおりです。フォーマットの変更（空白の削除を挿入）、変数の名前変更、ステートメントの再配置、ジャンクコードの追加、ステートメントの置換（x=1はx=y / 5に変更されます。y=5）、制御ステートメントの交換。インフルエンザウイルスが変異し、ワクチン接種が効果的でないのと同じように、ポリモルフィックマルウェアは検出を回避するために変異します。

更新：アドバイスの後、あなたたちは読書が何をすべきかに関して私に与えました。私はそれをしました、しかしそれは私をもっと混乱させました。私の問題に適用できるいくつかの距離アルゴリズムを見つけました。

  • 最長共通部分列
  • レーベンシュタインアルゴリズム
  • ニードルマン-ブンシュアルゴリズム
  • Smith–Watermanアルゴリズム
  • ボイヤームーアアルゴリズム
  • エイホ-コラシックアルゴリズム

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

更新2： LCSubsequence、LCSubstring、およびLevenshteinDistanceの融合を使用することになりました。提案ありがとうございます。

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

4

4 に答える 4

4

このようなアルゴリズムについては、バイオインフォマティクスの分野を調べることをお勧めします。そこには、特定のシグネチャ（遺伝子、よく知られている特別な短い塩基配列など）を探している大きなファイル（ゲノム配列）があるという点で、同様の問題があります。

また、ポリモルフィックマルウェアを検討する場合、生物学では完全に一致するものを取得することも同様に困難であるため、このセクターは多くのことを提供するはずです。（残念ながら、私はあなたを指すための適切な近似検索/マッチングアルゴリズムを知りません。）

この方向からの1つの例は、同時に複数のマルウェアシグネチャを検索するために、AhoCorasickアルゴリズムのようなものを適応させることです。

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

于 2010-11-02T14:15:25.777 に答える
2

Web検索のコンテキストでドキュメントの大規模なコーパスからほぼ重複するドキュメントを見つけることについて、多くの論文が公開されています。きっと役に立つと思います。たとえば、このプレゼンテーションを参照してください。

于 2010-11-02T13:49:34.273 に答える
1

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

この論文は、問題の良い要約と、試みられた引用におけるいくつかのアプローチを提供します。

ftp://ftp.computer.org/press/outgoing/proceedings/Patrick/apsec10/data/4266a366.pdf

于 2010-11-03T14:59:14.857 に答える
1

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

于 2010-11-03T21:11:53.013 に答える