2

特定のコードの実行中にプログラムカウンターが取る一連の値があります。これを使用して、この実行可能ファイルを生成した元のコードの静的分析を行いたいと思います（明確にするために：元のコードは利用できません）-特に、ループの数とそれらがどのようにネストされているか。例を挙げると、

A: for()
B:     if () 
C:         ...
D:     else
E:         ...
F:     for () {
G:         ...
H:         ...
I:     }

この場合、プログラムカウンターシーケンスは次のようになります。ABCDF{GHIGHIGHI} ABDEF {GHIGHI} ABDEF {GHIGHIGHIGHI}

上記のシーケンスから、2つのループがあり、一方が他方の中にネストされていることをどのように理解できますか？使用する適切な構文解析手法へのポインタも役立ちます。

元のコードにgotoがない、コンパイラーに最適化されたループ展開がないなど、いくつかの単純化された仮定を行うことができます。

4

1 に答える 1

2
  1. プログラムカウンターシーケンスからグラフを作成します。各プログラムカウンターは頂点であり、シーケンス内の連続するプログラムカウンターの各ペアは有向エッジです。（ある頂点から別の頂点に複数のエッジがある場合は、そのうちの1つだけを保持します）。
  2. シーケンスの最初のプログラムカウンターによって生成された頂点から開始して、深さ優先探索を実行してサイクルを見つけます。各サイクルが見つかったら、このサイクルの最後の端を別のリストに移動します。
  3. すべてのサイクルが検出されてグラフから移動すると、DAG（有向非巡回グラフ）が作成されます。このDAGでトポロジカルソートを実行して、if / elseブロックを除いて、ソースコードとまったく同じように、プログラム内のステートメントの正しいシーケンスを復元します（プログラムカウンターシーケンスから、どちらが「if」でどちらが「else」かを判別できません）。 ）。適切な結果を得るには、トポロジカルソートで特定の順序が指定されていない場合、深さ優先探索の順序を使用する必要があります。while / forループ本体を適切に配置するために、ステップ2の追加情報を使用できます。ループ検出アルゴリズムは、各ループの2番目のノードをマークする場合があります。
  4. if / elseブロックを分析するには、グラフに分割/マージの個別のリストを作成します。
  5. ループのリスト（ステップ2で抽出）とif / elseのリスト（ステップ4で抽出）を1つの間隔のリストに結合します。これらの間隔（一方が他方の中にネストされている）の関係を使用して、すべてのfor / if/elseステートメントのツリーを構築します。
  6. 場合によっては、「while」ループの最後にある「if」ブロックが、while{...if{}}while {loop {} ...}のように、「while」と「loop」の同じ開始アドレスで誤って検出されることがあります。'while'の開始アドレスは、ネストされたループの開始アドレスと一致することはできないため、これは簡単に後処理して。に戻すことができますwhile{...if{}}。（ネストされた「do-while」ループは同じ開始アドレスを持つ場合がありますが、ネストされた「if」では問題はありません）。

このアプローチは、「goto」、「break」、またはその他のサイクルからのジャンプがなく、「for」ループが単一の条件のみをチェックする最も単純な場合にのみ機能します。

于 2012-05-16T18:44:36.470 に答える