37

ファイルの類似性を判断することに関連するいくつかの質問をここで見ましたが、それらはすべて特定のドメイン (画像、音声、テキストなど) にリンクされています。ソリューションとして提供される手法では、比較対象のファイルの基になるファイル形式に関する知識が必要です。私が探しているのは、この要件のない方法です。この方法では、含まれるデータの種類を理解する必要なく、任意のバイナリ ファイルを比較できます。つまり、2 つのファイルのバイナリ データの類似性パーセンテージを判断しようとしています。

これは多くのことに適用できる可能性がありますが、私が取り組んでいる特定の問題があります。現在、実用的なソリューションもありますが、理想的ではないと思います。比較方法と結果の保存に関しては、おそらく多くの最適化があります。うまくいけば、ここにいる何人かの人々が私にいくつかの新しいアイデアを与えることができます. 数日後に現在の方法に関する情報を編集する予定ですが、私がすでに行っている方法を説明することで、問題に関する人々の考えを偏らせたくはありません.

私が取り組んでいる問題は、ビデオ ゲームの ROM イメージのクローン検出です。エミュレーションの経験がない方のために説明すると、ROM はゲーム カートリッジのデータのダンプです。ROM「クローン」は通常、同じゲームの修正版であり、最も一般的なタイプは翻訳版です。たとえば、ファミコン用のオリジナルのファイナルファンタジーの日本語版と英語版はクローンです。ゲームはほぼすべてのアセット (スプライト、音楽など) を共有していますが、テキストは翻訳されています。

現在、さまざまなシステムのクローンのリストを維持する作業を行っているグループがいくつかありますが、私が知る限り、これはすべて手動で行われています。私が試みているのは、「これらは同じゲームのように見える」のではなく、データの類似性に基づいて、類似した ROM イメージを自動的かつ客観的に検出する方法を見つけることです。クローンを検出する理由はいくつかありますが、主な動機の 1 つは、Solid 圧縮を使用することです。これにより、すべてのゲーム クローンを同じアーカイブにまとめて圧縮できます。多くの場合、圧縮されたクローン セット全体は、個々の ROM の 1 つよりもわずかに多くのスペースしか占有しません。

潜在的なアプローチを考え出す際に考慮すべきいくつかの懸念事項:

  • ROM のサイズは、システムによって大きく異なります。小さいものもありますが、最新のシステムには 256MB 以上の大きなものがある場合があります。一部の (すべての?) システムでは、可能なサイズとして 2 の累乗しかありません。これらのシステムの 1 つで 130MB のゲームを実行すると、256MB の ROM が使用され、ほとんど空になります。このため、ゲームのバージョンがしきい値を超え、2 倍のサイズのカートリッジを使用する必要がある場合、一部のクローンのサイズが大幅に異なる可能性があることに注意してください。
  • 現在、多くのシステムには数千の既知の ROM があり、ほとんどのシステムでは新しい ROM が常にリリースされています。古いシステムでも、変更された ROM を頻繁に作成する主要な ROM ハッキング コミュニティがあります。
  • ROM のすべての可能なペアの類似性データを格納すると、より一般的なシステムのいずれかで数百万行のデータが生成されます。5000 の ROM を備えたシステムでは、2500 万行の類似性データが必要になり、1 つの新しいゲームでさらに 5000 行が追加されます。
  • 中断された場合に中断したところから再開できるように、処理の状態は回復可能でなければなりません。どの方法でも、多くの処理が必要になるため、すべてが 1 つのバッチで実行されると仮定するのは安全ではありません。
  • 新しい ROM はいつでも追加される可能性があるため、この方法では、「完全な」セットが既にあると想定しないでください。つまり、既存のすべての ROM の類似性をすでに把握した後でも、新しい ROM が追加された場合 (これは前の処理が完全に終了する前に発生する可能性もあります)、それを以前のすべての ROM と比較して判断する方法が必要です。 （もしあれば）それはのクローンです。
  • 精度よりも処理速度を優先する必要があります（ある程度）。2 つの ROM が 94% または 96% 類似しているかどうかを知ることは特に重要ではありませんが、新しい ROM を以前のすべての ROM と比較するのに 1 日かかる場合、プログラムはおそらく完全には完了しません。

取り組むのは興味深い問題でした。他の人が何を考え出すことができるかを楽しみにしています。詳細が必要な場合は、コメントでお知らせください。提供できるように努めます。

4

10 に答える 10

22

バイナリデルタ、またはバイナリデルタのアプリケーションから派生したインデックス(サイズなど)が必要なようです。次に、このインデックスを実験的に決定したベースラインと比較して、それが「クローン」であるかどうかを判断できます。

圧縮とデルタ作成の間には多くの類似点があるため、現在の実装とそれほどかけ離れていないと思います。

そうは言っても、データベース内のすべてのバイナリ ファイルのペアごとの比較は、おそらく非常にコストがかかります (O(n 2 ) だと思います)。比較の候補を特定するための単純なハッシュを見つけようとします。spdenne と Eduard が示唆しているものと概念的に似ているもの。つまり、すべてのアイテムに 1 回適用できるハッシュを見つけ、そのリストを並べ替えてから、ハッシュがリスト内で互いに近接しているアイテムに対して、よりきめ細かい比較を使用します。

一般的なケースに役立つハッシュの構築は、数年間、CS で積極的に追求されてきた研究テーマです。LSHKitソフトウェア ライブラリは、この種のアルゴリズムをいくつか実装しています。インターネットでアクセス可能な論文FINDING SIMILAR FILES IN A LARGE FILE SYSTEMは、テキスト ファイルの比較をより対象としているように見えますが、役に立つかもしれません。最近の論文Multi-resolution similarity hashingでは、より強力なアルゴリズムが説明されています。ただし、サブスクリプションなしではアクセスできないようです。Locality Sensitive Hashingに関するウィキペディアの記事を残しておきたいと思うでしょう。他のリソースをブラウズするときに便利です。それらはすべてかなり技術的になり、ウィキペディアのエントリ自体はかなり数学が重くなります。よりユーザーフレンドリーな代替手段として、 Acoustic Fingerprintingの分野からいくつかのアイデア (または実行可能ファイル) を適用できる場合があります。

一般的なケースを放棄しても構わないと思っている場合は、ROM だけで機能する、はるかに単純な (そして高速な) ドメイン固有のハッシュ関数を見つけることができる可能性があります。おそらく、標準または共通のバイトシーケンスの配置と、それらの近くの選択ビットの値に関係するものです。バイナリ形式についてはよくわかりませんが、サウンド、画像、テキストの領域など、ファイル内のセクションの開始を知らせるものを想像しています。バイナリ形式では、この種のセクションのアドレスがファイルの先頭近くに保存されることがよくあります。また、最初のセクションのアドレスをそのサイズとともに既知の場所に格納するチェーン メカニズムを使用するものもあります。これにより、サイズなども含まれる次のセクションに移動できます。少し調査すると、おそらく関連するフォーマットを見つけることができます。

ハッシュ関数でうまくいかない場合 (またはメトリック/距離を定義するために何らかの入力が必要な場合) は、Web で利用できるバイナリ デルタ アルゴリズムと実装がいくつかあります。私が最もよく知っているのは、Subversion バージョン管理システムで使用されるものです。xdelta と呼ばれるバイナリ デルタ アルゴリズムを使用して、バイナリ ファイルのリビジョンを効率的に格納します。これを実装するリポジトリ内のファイルへの直接リンクは次のとおりです: xdelta.c。おそらく、これをよりアクセスしやすくするツールがウェブ上にあります。

于 2009-03-05T21:17:58.350 に答える
11

bsdiffを参照してください。これは、バイナリの差分/パッチ システムです。理論の多い論文もあります。

于 2009-02-24T00:30:42.850 に答える
7

剽窃検出アルゴリズムからいくつかのアイデアを使用します。

私の考え:

各 ROM の比較可能な「署名」を作成するために、小さな部分が変化するにつれてわずかに変化し、単語頻度グラフのようなものを作成しますが、単語の頻度を記録する代わりに、ROM の非常に短いセクションをハッシュして記録することができます。ハッシュ値の頻度。

1 つのセクションをハッシュしてから、最初のセクションの終わりから次のセクションをハッシュするのではなく、スライディング ウィンドウを使用して、バイト 1 からセクションをハッシュし、次にバイト 2 から、次にバイト 1 から同じサイズのセクションをハッシュします。 3など。これにより、ROM内の可変サイズの可変部分の効果が無効になります。

各 8 ビット バイトの xor のような単純なハッシュ関数を使用した場合、次のウィンドウ位置のハッシュを、発信 8 ビットを使用した現在のハッシュの xor と着信 8 ビットの xor によって簡単に計算できます。別の代替ハッシュ関数は、単に命令コードのワード長を使用することです。機械語命令を表すコードの静的パターンを作成するには、これで十分かもしれません。重要なことは、命令コード内で共通の短いシーケンスが同じハッシュ値になるハッシュ関数が必要になることです。

おそらく、それぞれの頻度が高いほど少ないハッシュ値が必要になるでしょうが、行き過ぎないでください。そうしないと、グラフが平坦になりすぎて、比較が難しくなります。同様に、範囲を広げすぎないでください。そうしないと、非常に小さな周波数が多くなり、比較が難しくなります。

このグラフを ROM ごとに保存します。各ハッシュ値の頻度の差の二乗和を計算して、2 つの異なる ROM の頻度グラフを比較します。合計がゼロになる場合、ROM は同一である可能性が高くなります。ゼロから離れるほど、ROM の類似性は低くなります。

于 2009-03-04T12:02:07.273 に答える
6

「数日」以上経ちましたが、おそらく現在のソリューションをここに追加する必要があると考えました。

Nils Pipenbrinck は、私の現在の方法と同じ方向に進んでいました。クローンを見つけることの主な結果の 1 つは、堅実なアーカイブによる大幅な節約であるため、任意の 2 つの ROM を一緒に圧縮して、どれだけのスペースが節約されたかを確認するだけでよいと考えました。これには、 7zipの LZMA アルゴリズムを使用しています。

最初のステップは、すべての ROM を個別に圧縮し、圧縮サイズをメモすることです。次に、任意の 2 つの ROM を一緒にアーカイブして、結果のサイズが個々の圧縮サイズとどのくらい異なるかを確認します。組み合わせたサイズが個々のサイズの合計と同じ場合、それらは 0% 類似しており、サイズがそれらの 1 つ (最大のもの) と同じ場合、それらは同一です。

さて、これは膨大な数の圧縮試行が必要なため、これまでにいくつかの最適化を行いました (さらに詳しく調べたいと思います)。

  1. 圧縮サイズの類似性に基づいて比較に優先順位を付けます。ROM A の圧縮サイズが 10MB で、ROM B の圧縮サイズが 2MB の場合、それらが 20% 以上類似することはあり得ないため、実際の結果を得るためにそれらを比較することは、後で行うことができます。非常に類似したファイルに対して同じ圧縮アルゴリズムを実行すると、同様のサイズの結果が得られる傾向があるため、多くのクローンが非常に迅速に検出されます。

  2. 上記と組み合わせて、ROM の任意のペア間の類似性の上限と下限の両方を維持します。これにより、さらに優先順位を付けることができます。ROM A と B が 95% 類似しており、ROM B と C が 2% しか類似していない場合、A と C が 0% から 7% の間であることが既にわかっています。これはクローンには低すぎるため、すべての正確な類似点を本当に知りたい場合を除き、この比較は安全に延期するか、完全に無視することさえできます.

于 2009-03-03T15:35:01.403 に答える
3

ここでは、データ圧縮から借用したいくつかの手法が興味深いと思います。

A と B の 2 つのファイルがあるとします。

各ファイルを個別に圧縮し、圧縮されたサイズを合計します。次に、2 つのファイルを 1 つの大きなファイルに連結し、同様に圧縮します。

サイズの違いから、ファイルがどの程度似ているかを大まかに見積もることができます。

Burrow Wheeler Transformation (bzip2) を試して圧縮を行うことをお勧めします。他のほとんどの圧縮アルゴリズムの歴史は限られています。BWT アルゴリズム otoh は、非常に大きなデータ チャンクを処理できます。アルゴリズムは両方のファイルを同時に「認識」し、類似性があると圧縮率が高くなります。

于 2009-02-24T02:54:00.137 に答える
2

XDelta は、まともなバイナリ差分を取得するのに非常に便利です: http://xdelta.org

于 2009-03-10T12:02:08.220 に答える
1

Waylon Flinn が言ったように、バイナリ デルタ アルゴリズムが必要になる場合があります。rsync アルゴリズムは優れたアルゴリズムです。高速で信頼性があります。ユーティリティのドキュメントも参照してください。

于 2009-03-08T13:01:57.050 に答える
1

ここでの問題は、実行可能なコードを扱っているため、単純な変更が ROM 全体に伝播する可能性があることです。すべての値のアドレスとオフセットは、単一の変数またはノーオペレーション命令を追加することで変更できます。これにより、ブロックベースのハッシュでさえ価値がなくなります。

データの追加または削除を処理できるスライド比較が得られるため、迅速で汚い解決策は、 difflib (または好みの言語と同等のもの)を使用してソリューションをハックすることです。ROM を実行可能セクションとデータ セクションに分割します (可能な場合)。データ セクションを直接比較して類似度を計算できますが、アドレスやオフセットに関してはまだ問題があります。

実行可能セクションはさらに興味深いものです。マシンの asm 形式を読み、実行可能ファイルを取り出して一連のオペコードに分割します。オペコードとレジスタ部分はそのままにして、「ペイロード」/「即時」部分 (変数アドレスをロードする場所) をマスクします。結果の情報も類似度計算機に渡してください。

残念なことに、これは追跡する ROM の数に対する O(n^2) 操作のままですが、必要な比較の量を減らすために (増分) クラスタリングまたは頻度ベースの比較順序で軽減できます。

于 2009-03-08T19:47:22.783 に答える
1

2つの考え：

  • ファイルをデータ フロー グラフとして整理し、その表現に対して何らかの正規化を行うことを検討してください。命令セットを知っているので、逆アセンブラを取り付けてテキスト処理を行うだけで、これは実現可能かもしれません。
  • CRM114などのトレーニング可能な分類子は、バイナリに多くの共通点があるかどうかを示すコンパクトな表現を提供するのに役立つ場合があります。
于 2009-02-24T03:09:54.870 に答える
1

hash trees のようなものを保存することから始めることができます。ROMごとにそのようなハッシュのセットを1つ格納するだけでよく、必要なストレージスペースは、ブロックサイズが一定であると仮定すると、ROMのサイズに比例するだけです(ただし、ROMのサイズよりもはるかに小さくなります)。選択したブロック サイズは、精度を確保するために十分な粒度を提供する必要があります。たとえば、最小サイズが 128MiB、精度制約が 1%、Tiger-128 ハッシュ(DirectConnect 経由で転送されるファイルをチェックするために使用するものと同様)、ブロック サイズが 1MiB の場合すべてのハッシュを 128 * 128 / 8 = 2048 バイトに格納できます。したがって、10,000 ROM に対して実行する場合、約 20MiB のスペースしか必要としません。さらに、安全性は低くなりますが、より高速で小さいハッシュを選択できます。新しい ROM の類似性を追加/チェックするには、次のような作業が必要になります。

  1. 新しい ROM をブロックに分割し、それぞれをハッシュします。
  2. データベースに既に存在するすべての ROM について、そのハッシュを新しい ROM のハッシュと比較します (以下を参照)。

比較関数は類似性をチェックする必要があります。ただし、各ハッシュを分割できない値として扱う必要があります。つまり、2 つのハッシュ間で論理的に有意な差関数を見つけようとする必要はありません。ブロック サイズが十分に小さく、ハッシュの衝突が十分にまれである限り、単純な is-equal 比較によって精度が保証されます。

ご覧のように、問題はパフォーマンスの面でより単純なものに縮小されます。つまり、はるかに小さなデータ セットの類似性をチェックします。

于 2009-02-24T02:45:12.387 に答える