問題タブ [control-flow-graph]

Push、Pop、Jump、If の操作を伴うスタックベースのおもちゃの言語があるとします。

プログラムがあり、その入力はおもちゃの言語です。たとえば、シーケンスを取得します

その場合、最大スタックは 2 になります。より複雑な例では、ブランチが使用されます。

この場合、最大スタックは 3 になります。ただし、実際にはスタック アンダーフロー エラーが発生するため、この場合のように上から下に移動して最大スタックを取得することはできません。

CFG を使用すると、グラフを作成して、基本ブロックの可能なすべてのパスをたどることができます。ただし、パスの数は n 個の頂点で急速に増加する可能性があるため、(n-1) になります。可能なパス。

私の現在のアプローチは、グラフをできるだけ単純化し、可能なパスを少なくすることです。これは機能しますが、私はそれが醜いと思います。この問題を攻撃するためのより良い (読む: より速い) 方法はありますか? アルゴリズムが生成するスタック深度が最適でなくても問題ありません。正しいスタック サイズが m の場合、私の唯一の制約は、結果 n が n >= m であることです。ここで良い結果を生み出す貪欲なアルゴリズムが利用可能でしょうか?

更新:サイクルと、すべての制御フロー マージのスタック深度が同じであるという不変条件を認識しています。問題を説明するために、簡単なおもちゃのような言葉を書き留めようと思いました。基本的に、私は決定論的なスタックベースの言語 (JVM バイトコード) を使用しているため、各操作には既知のスタックデルタがあります。

私はこの問題に対して、良い結果 (単純化された cfg) を生成する実用的な解決策を持っていることに注意してください。

C# コードの制御フロー グラフを描画するツールを探しています。

AVRORAに似ていますが、C# 用です。

何か案は？

objdump-dの呼び出しによって返されるアセンブリ結果の制御フローグラフを作成しようとしています。現在、私が思いついた最善の方法は、結果の各行をリンクリストに入れ、各行のメモリアドレス、オペコード、およびオペランドを分離することです。objdumpの結果の通常の性質に依存してそれらを分離しています（メモリアドレスは、各行を表す文字列の文字2から文字7までです）。

これが完了したら、実際のCFG命令を開始します。CFGの各ノードは、開始メモリアドレスと終了メモリアドレス、前の基本ブロックへのポインタ、および任意の子基本ブロックへのポインタを保持します。次に、objdumpの結果を調べて、オペコードをx86_64内のすべての制御フローオペコードの配列と比較します。オペコードが制御フローのものである場合、基本ブロックの終わりとしてアドレスを記録し、オペコードに応じて、2つの子ポインター（条件付きオペコード）または1つ（呼び出しまたは戻り）を追加します。

私はこれをCで実装している最中であり、動作するように見えますが、非常に希薄な感じがします。誰か提案、または私が考慮していない何かがありますか？

これを読んでくれてありがとう！

編集：

これを使用して、DynamoRIOによって生成されたシステムコールのスタックトレースを、ターゲットバイナリの予想されるCFGと比較するという考え方です。このように構築することで、それが容易になることを願っています。利用可能なものを再利用していません。A）実際にはそれについては理解していなかったため、B）パス比較を実行できるように、グラフを使用可能なデータ構造にする必要があるためです。私を正しい方向に向けてくれてありがとう、あなたが並べたページのユーティリティのいくつかを見ていきます。コメントありがとうございます、本当に感謝しています！

私は LLVM を使い始めましたが、LLVM/clang から制御フロー グラフや基本ブロックを抽出して分析を行うプログラム的な方法があるかどうか知りたいと思っています。単純なコンパイルを行う代わりに、ツール チェーンにフックしてこの情報を引き出す方法はありますか? そうでない場合、代替手段は何ですか？

私は現在コンパイラクラスを受講しており、最適化を実装するためにCFGを構築する必要があります。私が理解できないことの1つは、プログラムにCFGがいくつあるかということです。私が今まで見たすべての例は、単純なコードセグメントのCGFのようです。したがって、3つの機能を持つプログラムがある場合。機能ごとに個別のCFGがありますか、それともプログラム全体に1つの大きなCFGがありますか？

Cプログラムの制御フローグラフを取得し、プログラムがたどることができる最悪のパスを見つけるためのツール、ライブラリ、またはフレームワークはありますか？

制御フローグラフに関連する他の質問を読んだときに、制御フローグラフを生成できるいくつかのツールに出くわしました。それらを使用して最悪のパスを見つける方法はありますか？

gccが生成するアセンブリコードから制御フローグラフを抽出しようとしています。引数-fdump-rtl-*および-dvを使用して、いくつかのIR（rtlフェーズ）のCFGを.vcgファイルにダンプすることができました。最終的なアセンブリコード以外に同じことを行う方法はありますか？一般的で、ターゲットに依存せず、解析しやすい表現（vcg表現など）が必要です。私のソースコードはC言語です（重要な役割を果たす場合）。

よろしく、ミカリス。

CFG をハイレベル コードにレンダリングしたいと考えています。通常、これは非常に簡単です。ツリーをたどり、各基本ブロックを順番にレンダリングし、goto ですべてを接着します。

残念ながら、最近 goto は時代遅れになっており、最新の言語のほとんどは goto をサポートしていません。そのため、言語に存在する制御フロー ステートメントのみを使用して基本ブロックを接着する何らかの方法が必要です: for、while、do... while、if、breakおよびcontinue. (変数を使用してステート マシンを構築することは考えたくありません。)

これを行うアルゴリズムはありますが、すべての場合に機能するとは限りません。つまり、上記の限られた一連の制御フロー構造のみを使用して、構造化コードにフラット化できない CFG を構築することが可能です。

これは私には直感的に明らかなように思えますが、それを証明することはできません (そして、私が見つけたアルゴリズムのドキュメントでは、これ以上詳しく説明されていません)。そして、このように平坦化できない CFG の例を見つけることができませんでした。

これが可能かどうか、はっきりと知りたいです。

オプション (a): 上記のように平坦化できない CFG の例はありますか? （それは不可能だと教えてくれます。）

オプション (b):上記のように CFG を平坦化できるという証拠を誰かが持っていますか? （それが可能であることがわかります。）それを機能させる必要があるため、それを行うアルゴリズムも非常に望ましいでしょう...

I am trying to analyse Java code sturcture.

So, I generated a Java parser and lexer by using ANTLRv3 and java grammar code...

but I don't know how could I generate Context Flow Graph using the generated parser and lexer.

I tried to learn how to do this through tutorial page, but the tutorial page has already disappeared.

Could you give me a way how to do this? or tutorial page?

Thank you.