7

私はバイナリAを持っています。これは、何年も前にビルドされたシンボルを伴うデバッグビルドです。私はバイナリBも持っています。これは、シンボルを伴わないリリースビルドであり、はるかに最近のものです。バイナリAのシンボルをバイナリBの潜在的な候補に一致させる最も効率的な方法を探しています。

デバッグ ビルドがかなり大きく (より多くの入力検証を行い、より多くのものを に出力するstderrなど)、関数は常に時間の経過とともに変化することを考えると、個々の関数をフィンガープリントしようとすると時間が無駄になると思います。

したがって、私は決定しました - 非常に何もないので、間違ったツリーを吠えている可能性があります - 関数をフィンガープリントする最良の方法は、両方のバイナリの呼び出しグラフを作成し、頂点を一致させることです (つまり、機能）。

すでにいくつかの前処理を行っているため、次のデータ構造があります。

# binary A
[[60, 60, 8734], # function 0 is called by functions 60 (twice) and 8734
 [193, 441, 505], # function 1 is called by functions 193, 441 and 505
 [193, 742],
 [23],  
 [21],  
 [21],  
 [26],  
 [26, 1508, 1509, 1573],  
 [24],  
 [25],
 ...] # (~10k functions)

# binary B
[[8999], # function 0 is called by function 8999
 [9016], # function 1 is called by function 9016
 [1126], 
 [7904, 7904, 7913], 
 [182, 336, 396, 396], 
 [9010], 
 [407], 
 [182, 632], 
 [20], 
 [24],
 ...] # (~10k functions)

重要な注意点は、バイナリA の関数 "0" とバイナリBの関数 "0" の間に対応がないことです。これらは、各バイナリの各関数に割り当てた任意の ID です。

次のステップは、私を混乱させるものです。私のアルゴリズム フーは非常に弱く、先に進む賢い方法が思い浮かびません。私の（非常に限られた）理解は、これを解決するために、何らかの形式の不正確なグラフマッチングを採用したいということです。言い換えれば、どのマッピング Ai -> Bi が 2 つのコールグラフの類似性を最大化するでしょうか?

バイナリAには追加のデバッグ機能があり、プログラムが時間の経過とともに進化するという明らかな事実を考えると、完全に一致するものはおそらくありません。理想的には、次の形式の出力が必要です。

[[(37, 0.998), (8432, 0.912), (442, 0.75)], # matching-ness of function "0" in binary A with function "37" in binary B is 0.998, second most likely candidate is function "8432" in binary B with score 0.912, etc.
 [(42, 0.973), (7751, 0.788)], # matching-ness of function "1" in binary A with function "42" in binary B is 0.973, second most likely candidate is function "7751" in binary B with score 0.788, etc.
 [(4579, 0.996), (123, 0.934)], 
 ...] # around ~10k mappings

現実的には、候補が1つだけでランキングが出なくてもよかったのですが、夢は叶います。

SO-goers は、私がどこから始めるべきかについて考えを持っていますか?

4

2 に答える 2

5

確かに興味深い問題ですが、解決するのは難しいと思います。これは、有向グラフ上の近似グラフ同型のインスタンスのようです。これについてはあまりグーグルを見つけられませんでしたが、無向一般グラフを解決するためのソフトウェアがいくつかあります.NP困難なより一般的なケースです。

実行可能コードの配置

あなたができる最も実用的なことは、ランタイム情報を忘れて、単純に各バージョンの実行可能コード セクションを取得し、グローバル アラインメント アルゴリズムを使用することだと思います (たとえば、 Needleman-Wunsch、はるかに高速ですが精度が低いものは存在しますが)アルゴリズム) で、次のことを行います。

  1. 命令全体を文字として扱います (これには、初歩的な逆アセンブラーを作成する必要があります)。
  2. 命令のアドレス コンポーネントを完全に無視する
  3. 削除の重みを下げる (「最初の」ファイルがデバッグ バージョンであると仮定すると、これはより大きくなると予想されます)
  4. 命令の一致を重み付けしCALL、場合によっては他の「信頼できる」命令シーケンスを重み付けします。

関数が実行可能ファイルに表示される順序があまり変更されていないと仮定すると (最適化されたバージョンで、リンカーが相互に呼び出す関数を互いに近くに配置するようにする何らかの最適化が使用されていない限り、変更されることはありません)、これは次のようになります。良い最初の近似を取得します。

割り当て問題 (二部最大マッチング)

fあるいは、デバッグ バージョンの関数が対応する可能性を「スコアリング」する方法を見つけることができれば (そして、私の直感では、PageRank が Web ページの値を決定する方法に沿って、反復的なアプローチが必要になることが示唆されています)。最適化されたバージョンの関数gであれば、はい、グラフ マッチング手法を使用できます。この場合、グラフの頂点は両方のバージョンのすべての関数になり、デバッグ バージョンのすべての関数と最適化されたバージョンのすべての関数の間に重み付けされたエッジがあり、重みはスコアリング システムによって決定されます。

同じバージョンの 2 つの関数間にエッジが存在しないため、このグラフは 2 部になります。つまり、これは代入問題のインスタンスであり、非常に優れた (そしてそれほど複雑ではない) アルゴリズムが存在します。

ただし、ここで欠けているのは、各ペアリングの重みを決定する手段です。これを行うおおよその方法の 1 つは、関数ごとに直接の子、孫、ひ孫などの数をカウントするベクトルを作成することです。次に、任意の距離測定を使用してこれらのベクトルを比較できます。しかし、デバッグ バージョンには最適化されたバージョンよりもはるかに多くの関数呼び出しが含まれていることが既に予想されているため、ここでこれを行うとうまくいかないことが予想されます。

フル コール ツリーの使用

両方のコール ツリー全体にアクセスできる場合は、関数内で行われた一連の呼び出しや、呼び出しの正確な階層に関する知識など、より多くの情報が得られます。後者だけを使用して、各関数の「署名」を作成できる場合があります。

  1. 特定の関数によって呼び出される個別の関数のリストを抽出します
  2. 最初に呼び出される関数 1、2 番目に呼び出される固有関数 2 などのラベルを付けます。
  3. シグネチャは、関数内で呼び出される順序で関数ラベルを並べたものです。

これで、レーベンシュタイン距離を使用して 2 つのシグネチャを比較できます。より多くの計算を犠牲にして精度を高めるには、デバッグ バージョンで最大 k 個の異なる関数を削除できるバリエーションを使用できます。いくつかの小さな k (たとえば、k = 3) については、最適なレーベンシュタイン距離が取得されます。そのような「スリム化」されたすべてのバージョンに対して、削除された機能の数に比例する小さなペナルティが付けられます。

于 2010-12-07T07:21:33.923 に答える
1

余裕があればIDA Pro + BinDiff .

于 2010-12-07T10:40:22.910 に答える