调用图（Call Graph）

本文为译文，点击 此处查看原文

一个调用图call graph(也称为call multigraph[1] [2])是一种控制流图[3]，它表示一个计算机程序中子程序之间的调用关系。每个节点表示一个过程，每条边(f, g)表示过程f调用过程g。因此，图中的一个循环表示递归过程调用。

1. 基本概念

调用图可以是动态的，也可以是静态的[4]。一个动态调用图是程序一次执行的记录，例如一个分析器的输出。因此，一个动态调用图可以是精确的，但只能描述程序的一次运行。一个静态调用图是一个调用图，用于表示程序的每一次可能运行。准确的静态调用图是一个不可判定的问题，因此静态调用图算法通常是过度近似的。也就是说，发生的每个调用关系都在图中表示出来，而且可能还有一些调用关系在程序的实际运行中永远不会发生。
可以定义调用图来表示不同程度的精度。一个更精确的调用图更精确地近似于真实程序的行为，代价是计算时间更长，存储内存更大。这个最精确的调用图是完全上下文敏感的，这意味着对于每个过程，这个图为每个调用堆栈包含一个单独的节点，可以使用该调用堆栈激活该过程。完全上下文敏感的调用图称为调用上下文树。这可以很容易地动态计算，尽管它可能占用大量内存。调用上下文树通常不是静态计算的，因为对于大型程序来说，这会花费太长时间。最不精确的调用图是上下文不敏感的，这意味着每个过程只有一个节点。
使用具有动态分派特性的语言，如Java和c++，计算静态调用图精确地需要别名分析结果。相反，计算精确的别名需要一个调用图。许多静态分析系统通过同时计算这两种方法来解决视无穷回归问题。

2. 用法

调用图可以被以不同的方式使用。调用图的一个简单应用是查找从未被调用的过程。调用图可以作为人类来理解程序[6]的文档。它们还可以作为进一步分析的基础，例如跟踪过程之间的值流的分析，或者变更影响预测[7]。调用图还可以用来检测程序执行的异常或代码注入攻击。

3. 软件

3.1 免费软件 调用图生成器

3.1.1 运行时调用图(列出的大多数工具都是带有调用图功能的分析器)

• gprof：包含在BSD中或GNU二进制实用程序的一部分
• callgrind: Valgrind的一部分
• KCachegrind：根据callgrind生成的数据生成和分析调用图的强大工具
• Mac OS X 活动监视器：Apple GUI进程监视器活动监视器有一个内置的调用图生成器，可以对进程进行采样并返回调用图。此功能仅在Mac OS X Leopard中可用
• OpenPAT：包含control_flow工具，该工具可以根据运行时度量自动创建Graphviz调用图。
• pprof：一个用于可视化和分析概要数据的开源工具，将与gperftools一起使用。
• 来自AMD的代码分析(在GPL下发布)
• makeppgraph是一个依赖关系图生成器(在模块级)，用于与makepp执行构建。
• Intel®单事件API(免费、开源)

3.1.2 静态(用于C语言)，用于在不运行应用程序的情况下获取调用图

• doxygen：使用graphviz生成静态调用/继承关系图
• cflow：GNU cflow能够生成C程序的直接调用图和反向调用图
• egypt：一个小型Perl脚本，使用gcc和Graphviz生成C程序的静态调用图。
• Analizo：计算源代码度量，生成依赖关系图。
• CCTree：本地Vim插件，可以通过读取一个cscope数据库来显示静态调用图。为C程序工作。
• codeviz：一个静态调用图生成器(程序没有运行)。作为gcc的补丁实现；适用于C和C++程序。
• Cppdepend：是一个用于C/C++代码的静态分析工具。此工具支持大量代码度量，允许使用有向图和依赖关系矩阵可视化依赖关系。
• calltree.sh：Bash shell函数，它将cscope、graphviz和一些dot呈现工具样本粘合在一起，以显示指定的C函数之上、之下和/或之间的“调用者”和“被调用者”关系。
• tceetree：类似calltree.sh。它连接Cscope和Graphviz，但它是一个可执行文件，而不是bash脚本。

3.1.3 Go

• go-callvis：一个用于Go程序的调用图生成器，其输出可以用Graphviz绘制

3.1.4 .Net

• NDepend：是一个用于.Net代码的静态分析工具。此工具支持大量代码度量，允许使用有向图和依赖关系矩阵可视化依赖关系。

3.1.5 PHP、Perl和Python

• Devel::NYTProf：一个perl性能分析器和调用图表生成器
• phpCallGraph：用于PHP程序的调用图生成器，使用Graphviz。它是用PHP编写的，至少需要PHP 5.2。
• pycallgraph:用于Python程序的调用图生成器，使用Graphviz。
• pyan：用于Python程序的静态调用图生成器，使用Graphviz。
• gprof2dot：用Python编写的调用图生成器，它将许多语言/运行时的分析数据转换为Graphviz调用图。
• code2flow：用于Python和Javascript程序的调用图生成器，使用Graphviz

3.1.6 XQuery

• XQuery Wikibook中的XQuery调用图：XQuery函数模块的调用图生成器，使用Graphviz

3.2 专有的调用图生成器

3.2.1 项目分析

Visual Basic代码的静态代码分析器和调用图生成器

3.2.2 Visual Expert

用于Oracle PL/SQL、SQLServer Transact-SQL、c#和PowerBuilder代码的静态代码分析器和调用图生成器

3.2.3 Intel VTune性能分析器

检测分析器来显示调用图和执行统计数据

3.2.4 DMS软件再工程工具包

可定制的程序分析工具，具有静态的全程序全局调用图提取，适用于C, Java和COBOL

3.3 其他相关工具

3.3.1 Graphviz

将任何图(包括调用图)的文本表示形式转换为图片。

4. 示例图

由gprof分析自身生成的一个示例调用图：

index    called     name                              |index    called     name
      72384/72384       sym_id_parse [54]             |       1508/1508        cg_dfn [15]
[3]   72384             match [3]                     |[13]   1508             pre_visit [13]
----------------------                                |----------------------
          4/9052        cg_tally [32]                 |       1508/1508        cg_assemble [38]
       3016/9052        hist_print [49]               |[14]   1508             propagate_time [14]
       6032/9052        propagate_flags [52]          |----------------------
[4]    9052             sym_lookup [4]                |          2             cg_dfn [15]
----------------------                                |       1507/1507        cg_assemble [38]
       5766/5766        core_create_function_syms [41]|[15]   1507+2           cg_dfn [15]
[5]    5766             core_sym_class [5]            |       1509/1509        is_numbered [9]
----------------------                                |       1508/1508        is_busy [11]
         24/1537        parse_spec [19]               |       1508/1508        pre_visit [13]
       1513/1537        core_create_function_syms [41]|       1508/1508        post_visit [12]
[6]    1537             sym_init [6]                  |          2             cg_dfn [15]
----------------------                                |----------------------
       1511/1511        core_create_function_syms [41]|       1505/1505        hist_print [49]
[7]    1511             get_src_info [7]              |[16]   1505             print_line [16]
----------------------                                |          2/9           print_name_only [25]
          2/1510        arc_add [31]                  |----------------------
       1508/1510        cg_assemble [38]              |       1430/1430        core_create_function_syms [41]
[8]    1510             arc_lookup [8]                |[17]   1430             source_file_lookup_path [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             inherit_flags [10]            |         24/24          parse_id [18]
----------------------                                |[19]     24             parse_spec [19]
       1508/1508        cg_dfn [15]                   |         24/1537        sym_init [6]
[11]   1508             is_busy [11]                  |----------------------
----------------------                                |         24/24          main [1210]
       1508/1508        cg_dfn [15]                   |[20]     24             sym_id_add [20]
[12]   1508             post_visit [12]               |

5. 另请参阅

依赖关系图

---

6. 参考文献

1. Callahan, D.; Carle, A.; Hall, M.W.; Kennedy, K. (April 1990). “Constructing the procedure call multigraph”. IEEE Transactions on Software Engineering. 16 (4): 483–487. doi:10.1109/32.54302.
2. Uday Khedker; Amitabha Sanyal; Bageshri Sathe (2009). Data Flow Analysis: Theory and Practice. CRC Press. p. 234. ISBN 978-0-8493-3251-7.
3. Pankaj Jalote (1997). An Integrated Approach to Software Engineering. Springer Science & Business Media. p. 372. ISBN 978-0-387-94899-7.
4. Ryder, B.G. (May 1979). “Constructing the Call Graph of a Program”. IEEE Transactions on Software Engineering. SE-5 (3): 216–226. doi:10.1109/tse.1979.234183.
5. Grove, David; DeFouw, Greg; Dean, Jeffrey; Chambers, Craig; Grove, David; DeFouw, Greg; Dean, Jeffrey; Chambers, Craig (9 October 1997). “Call graph construction in object-oriented languages”. ACM SIGPLAN Notices. ACM. 32: 108, 108–124, 124. doi:10.1145/263700.264352.
6. Eisenbarth, T.; Koschke, R.; Simon, D. “Aiding program comprehension by static and dynamic feature analysis”. Proceedings IEEE International Conference on Software Maintenance. ICSM 2001. doi:10.1109/icsm.2001.972777.
7. Musco, Vincenzo; Monperrus, Martin; Preux, Philippe (26 July 2016). “A large-scale study of call graph-based impact prediction using mutation testing”. Software Quality Journal. 25 (3): 921–950. doi:10.1007/s11219-016-9332-8.
8. Gao, Debin; Reiter, Michael K.; Song, Dawn (25 October 2004). “Gray-box extraction of execution graphs for anomaly detection”. ACM: 318–329. doi:10.1145/1030083.1030126.