Loading article…
コールグラフ（コールマルチグラフ[1] [2]とも呼ばれる）は、コンピュータプログラム内のサブルーチン間の呼び出し関係を表す制御フローグラフ[3]である。各ノードは手順を表し、各エッジ（f、g）は手順fが手順gを呼び出すことを示す。したがって、グラフ内のサイクルは再帰的な手順呼び出しを表す。
基本概念
呼び出しグラフは動的または静的である。[4]動的呼び出しグラフは、たとえばプロファイラの出力などのプログラム実行の記録である。したがって、動的呼び出しグラフは正確である可能性があるが、プログラムの 1 回の実行のみを記述する。静的呼び出しグラフは、プログラムのあらゆる実行を表すことを目的とした呼び出しグラフである。正確な静的呼び出しグラフは決定不可能な問題であるため、静的呼び出しグラフ アルゴリズムは一般に過近似である。つまり、発生するすべての呼び出し関係がグラフに表され、プログラムの実際の実行では決して発生しない呼び出し関係も表される可能性がある。
呼び出しグラフは、さまざまな精度を表現するように定義できます。より正確な呼び出しグラフは、実際のプログラムの動作をより正確に近似しますが、計算に時間がかかり、保存するメモリが多くなります。最も正確な呼び出しグラフは完全にコンテキスト依存で、各プロシージャについて、グラフにはプロシージャをアクティブ化できる各コール スタックの個別のノードが含まれます。完全にコンテキスト依存の呼び出しグラフは、呼び出しコンテキスト ツリーと呼ばれます。これは、大量のメモリを消費する可能性がありますが、簡単に動的に計算できます。呼び出しコンテキスト ツリーは、大規模なプログラムでは時間がかかりすぎるため、通常、静的には計算されません。最も精度の低い呼び出しグラフはコンテキスト非依存で、各プロシージャに 1 つのノードしかありません。
動的ディスパッチを特徴とする言語（JavaやC++など）、[5] 第一級関数（PythonやRacketなど）、または関数ポインタ（Cなど）では、静的呼び出しグラフを正確に計算するには、エイリアス解析の結果が必要です。逆に、正確なエイリアシングを計算するには、呼び出しグラフが必要です。多くの静的解析システムは、両方を同時に計算することで、見かけ上の無限後退を解決します。
使用法
コールグラフはさまざまな方法で使用できます。コールグラフの簡単な用途の1つは、呼び出されないプロシージャを見つけることです。コールグラフは、人間がプログラムを理解するためのドキュメントとして機能します。[6]コールグラフは、プログラム実行の異常やコードインジェクション攻撃を検出するためにも使用できます。[7]
ソフトウェア
フリーソフトウェアコールグラフジェネレータ
実行時コールグラフ（リストされているツールのほとんどはコールグラフ機能を備えたプロファイラーです）
- gprof : BSDに含まれるか、GNUバイナリユーティリティの一部です。
- callgrind : Valgrindの一部
- KCachegrind: callgrind によって生成されたデータに基づいてコールグラフを生成および分析する強力なツール
- Mac OS X アクティビティ モニタ: Apple GUI プロセス モニタ アクティビティ モニタには、プロセスをサンプリングしてコール グラフを返すコール グラフ ジェネレータが組み込まれています。この機能は、Mac OS X Leopardでのみ使用できます。
- OpenPAT:実行時の測定からGraphviz呼び出しグラフ画像
control_flowを自動的に作成するツールが含まれています。 - pprof は、gperftools と組み合わせて使用する、プロファイル データの視覚化と分析のためのオープン ソース ツールです。
- AMDのCodeAnalyst (GPL に基づいてリリース)
- makeppgraph は、 makeppで実行されるビルド用の依存関係グラフ ジェネレーター (モジュール レベル) です。
- Intel(R) シングル イベント API (無料、オープンソース)
アプリケーションを実行せずにコールグラフを取得するための静的
- C++ の
- Sourcetrailは静的なコールグラフを作成し、ユーザーが動的に探索できるようにします。PythonとJavaもサポートしています。
- doxygen : Graphviz を使用して静的呼び出し/継承図を生成します
- Cally: GCC のレジスタ転送言語 (RTL) ファイルを使用して、C プロジェクトの呼び出し元または呼び出し先の呼び出しグラフを構築するツール。
- cflow : GNU cflow は C プログラムの直接および逆呼び出しグラフを生成することができます。
- egypt : gcc とGraphviz を使用してC プログラムの静的呼び出しグラフを生成する小さなPerlスクリプト。
- Analizo: ソースコードメトリクスを計算し、依存関係グラフを生成します。
- CCTree : cscopeデータベースを読み取って静的な呼び出しグラフを表示できるネイティブVimプラグイン。C プログラムで動作します。
- codeviz : 静的呼び出しグラフ ジェネレーター (プログラムは実行されません) 。gccへのパッチとして実装され、C および C++ プログラムで動作します。
- calltree.sh : cscope、graphviz、およびドット レンダリング ツールのサンプルを結合して、指定した C 関数の上、下、および/または C 関数間の「呼び出し元」と「呼び出し先」の関係を表示する Bash シェル関数。
- tceetree : calltree.sh と同様に、CscopeとGraphviz を接続しますが、 bash スクリプトではなく実行可能ファイルです。
- 行く
- go-callvis : Go プログラム用の対話型コールグラフ ジェネレーター。出力はGraphvizで描画できます。
- 多言語
- callGraph: awk、bash、basic、dart、fortran、go、lua、javascript、julia、kotlin、matlab、perl、pascal、php、python、R、raku、ruby、rust、scala、swift、tcl、typescript 用のオープンソースの呼び出しグラフ ジェネレーター。
- 。ネット
- NDependは、.NET コードの静的解析ツールです。このツールは多数のコード メトリックをサポートし、有向グラフと依存関係マトリックスを使用して依存関係を視覚化できます。
- PHP、Perl、Python
- Devel::NYTProf: Perl パフォーマンス アナライザーおよびコール チャート ジェネレーター
- phpCallGraph : Graphviz を使用する PHP プログラム用の呼び出しグラフ ジェネレーター。PHP で記述されており、少なくとも PHP 5.2 が必要です。
- pycallgraph は、Wayback Machineで 2007-05-25 にアーカイブされています。Graphvizを 使用する Python プログラムの呼び出しグラフ ジェネレーターです。
- pyan : Graphviz を使用する Python プログラム用の静的呼び出しグラフ ジェネレーター。
- gprof2dot : Python で書かれたコールグラフ ジェネレーター。多くの言語/ランタイムのプロファイリング データをGraphvizコールグラフに変換します。
- code2flow: Graphviz を使用する Python および Javascript プログラム用のコールグラフ ジェネレーター
- rcviz : Graphvizを使用して実行時に生成された呼び出しグラフをレンダリングするための Python モジュール。各ノードは、渡されたパラメーターと戻り値を持つ関数の呼び出しを表します。
- XQuery
- XQuery Wikibook の XQuery コール グラフ: Graphviz を使用する XQuery 関数モジュールのコール グラフ ジェネレーター
独自のコールグラフジェネレータ
- LDRA テストベッド
- ホスト ソフトウェアと組み込みソフトウェアの両方に対応した静的および動的解析エンジンと、呼び出しグラフを含むさまざまなレポート。
- プロジェクトアナライザー
- Visual Basic コード用の静的コード アナライザーとコール グラフ ジェネレーター
- ビジュアルエキスパート
- Oracle PL/SQL、SQLServer Transact-SQL、C#、PowerBuilderコード用の静的コード アナライザーおよびコール グラフ ジェネレーター
- インテル VTune パフォーマンス アナライザー
- 呼び出しグラフと実行統計を表示するプロファイラーのインストルメンテーション
- DMS ソフトウェア リエンジニアリング ツールキット
- C、Java、COBOL 用の静的なプログラム全体のグローバル呼び出しグラフ抽出機能を備えたカスタマイズ可能なプログラム分析ツール
その他の関連ツール
サンプルグラフ
gprofが自身を分析することによって生成されたサンプル呼び出しグラフ:
名前と呼ばれるインデックス | 名前と呼ばれるインデックス
72384/72384 sym_id_parse [54] | 1508/1508 cg_dfn [15]
[3] 72384 マッチ [3] |[13] 1508 事前訪問 [13]
---------------------- |----------------------
4/9052 cg_tally [32] | 1508/1508 cg_assemble [38]
3016/9052 ヒストプリント [49] |[14] 1508 伝播時間 [14]
6032/9052 propagate_flags [52] |----------------------
[4] 9052 sym_lookup [4] | 2 cg_dfn [15]
---------------------- | 1507/1507 cg_assemble [38]
5766/5766 コア作成関数シンボル [41]|[15] 1507+2 cg_dfn [15]
[5] 5766 コアシンボリッククラス [5] | 1509/1509 番号付き [9]
---------------------- | 1508/1508 ビジー状態 [11]
24/1537 解析仕様 [19] | 1508/1508 事前訪問 [13]
1513/1537 コア作成関数シンボル [41]| 1508/1508 事後訪問 [12]
[6] 1537 sym_init [6] | 2 cg_dfn [15]
---------------------- |----------------------
1511/1511 コア作成関数シンボル [41]| 1505/1505 ヒストプリント [49]
[7] 1511 get_src_info [7] |[16] 1505 print_line [16]
---------------------- | 2/9 印刷名のみ [25]
2/1510 アーク追加 [31] |----------------------
1508/1510 cg_assemble [38] | 1430/1430 core_create_function_syms [41]
[8] 1510 arc_lookup [8] |[17] 1430 ソースファイルルックアップパス [17]
---------------------- |----------------------
1509/1509 cg_dfn [15] | 24/24 sym_id_parse [54]
[9] 1509 is_numbered [9] |[18] 24 parse_id [18]
---------------------- | 24/24 parse_spec [19]
1508/1508 propagate_flags [52] |----------------------
[10] 1508 継承フラグ [10] | 24/24 解析ID [18]
---------------------- |[19] 24 parse_spec [19]
1508/1508 cg_dfn [15] | 24/1537 sym_init [6]
[11] 1508 is_busy [11] |----------------------
---------------------- | 24/24 メイン [1210]
1508/1508 cg_dfn [15] |[20] 24 sym_id_add [20]
[12] 1508 post_visit [12] |
参照
参考文献
- ^ Callahan, D.; Carle, A.; Hall, MW ; Kennedy, K. (1990 年 4 月)。「プロシージャ コール マルチグラフの構築」IEEE Transactions on Software Engineering 16 ( 4): 483–487. doi :10.1109/32.54302。
- ^ Uday Khedker、Amitabha Sanyal、Bageshri Sathe (2009)。データフロー分析：理論と実践。CRC Press。p. 234。ISBN 978-0-8493-3251-7。
- ^ Pankaj Jalote (1997).ソフトウェアエンジニアリングへの統合アプローチ. Springer Science & Business Media. p. 372. ISBN 978-0-387-94899-7。
- ^ Ryder, BG (1979 年 5 月)。「プログラムの呼び出しグラフの構築」。IEEE Transactions on Software Engineering。SE - 5 (3): 216–226。doi :10.1109/tse.1979.234183。S2CID 16527042 。
- ^ Grove, David; DeFouw, Greg; Dean, Jeffrey; Chambers, Craig; Grove, David; DeFouw, Greg; Dean, Jeffrey; Chambers, Craig (1997 年 10 月 9 日). 「オブジェクト指向言語におけるコールグラフ構築」. ACM SIGPLAN Notices . 32 (10). ACM: 108, 108–124, 124. doi : 10.1145/263700.264352 .
- ^ Eisenbarth, T.; Koschke, R.; Simon, D. ( 2001). 「静的および動的機能分析によるプログラム理解の支援」。IEEE国際ソフトウェア保守会議議事録。ICSM 2001。pp. 602–611。doi :10.1109 / icsm.2001.972777。ISBN 0-7695-1189-9. S2CID 5934718。
- ^ Gao, Debin; Reiter, Michael K.; Song, Dawn (2004 年 10 月 25 日)。「異常検出のための実行グラフのグレーボックス抽出」。第 11 回 ACM コンピュータおよび通信セキュリティ会議 - CCS '04 の議事録。ACM。pp. 318–329。doi : 10.1145 / 1030083.1030126。ISBN 1581139616.S2CID 1189805 。