c - 最悪の可能性のあるパスを見つけるためのACプログラムの制御フローグラフ

Question

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

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

Answer 1

グラフにループが含まれる場合は、いいえ。質問は停止性問題と同等であるため、これを理解するための絶対確実な方法はありません。短いバージョン：任意の他のプログラムが与えられた場合、プログラムが戻るかどうかを判断することさえ不可能です。潜在的な無限ループを特定できる可能性がありますが、確実に近い場所にいる唯一の方法は、徹底的な入力セットを使用してプログラムを実際に実行することです。

Answer 2

あなたはおそらく最悪の場合の実行時間に興味があるでしょう。それが成功した場合、ある意味で最悪の制御フローパスを見つけたに違いありません。

C制御フローグラフを計算するためのライブラリについては、Cおよびその他の言語のDMSのフロー分析サポートを参照してください。