函数调用图
![本页使用了标题或全文手工转换](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
![]() | 此条目可参照英语维基百科相应条目来扩充。 |
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/2/2f/A_Call_Graph_generated_by_pycallgraph.png/220px-A_Call_Graph_generated_by_pycallgraph.png)
函数调用图(call graph,也称为call multigraph)[1][2],属于控制流图[3],可以展示电脑程序中函数之间的关系。每一个节点是一个函数,每一个边(f, g)表示函数f调用函数g。若其中有出现互相调用的环,表示程序中可能有递归调用。
基本概念
函数调用图可以由动态程序分析产生(动态函数调用图),也可以由静态程序分析产生(静态函数调用图)[4]。动态函数调用图是程序执行过程的记录,可能是性能分析工具所输出的。动态函数调用图可以准确的描述这次程序执行时,各函数之间的关系。但会遗漏这次没有执行到的代码。静态函数调用图则是设法表示所有可能执行情形下,所有函数之间的关系。准确的静态函数调用图是不可判定问题,因此静态函数调用图是多半只是近似情形。函数调用图上有所有函数之间的调用关系,但有可能其中有一些调用是永远不会执行到的。
函数调用图可以定义来呈现不同程度的准确度。更准确的函数调用图会更近似真正程序的行为,不过要计算的时间会比较长,要存储的资料也会比较多。最准确的函数调用图是完全“上下文相关”(context-sensitive),针对每一个函数,图中会对不同情形,不同调用堆栈下的调用,有不同的节点。全上下文相关的函数调用图称为调用上下文树。利用动态程序分析可以轻易的产生,不过会花许多的存储器。调用上下文树一般不会用静态程序分析产生,因为对大型程序会花许多时间。最不准确的函数调用图称为“上下文无关”(context-insensitive),针对每一个函数只会有一个节点。
若编程语言中有动态分派的特性(例如Java或C++),要产生准确的静态程序分析会需要假名分析的结果[5]。相对的,要得到准确的假名分析也需要函数调用图。许多静态分析系统可以同步产生这二份资料,解决这个看似无限循环的问题。
用途
函数调用图有几种不同的用途。其中一个简单的应用是找出没有被其他程序调用的子函数。函数调用图可以当做文件,有助于程序员的程序理解[6]。函数调用图也是进一步分析的基础,例如追踪某一变量数值在各子函数中的变化,或是进行变更影响分析[7]。函数调用图可以用来侦测异常的程序执行,或是侦测代码注入攻击[8]。
示例的图
以下是用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] |
相关条目
参考资料
- ^ Callahan, D.; Carle, A.; Hall, M.W.; Kennedy, K. Constructing the procedure call multigraph. IEEE Transactions on Software Engineering. April 1990, 16 (4): 483–487. doi:10.1109/32.54302.
- ^ Uday Khedker; Amitabha Sanyal; Bageshri Sathe. Data Flow Analysis: Theory and Practice. CRC Press. 2009: 234. ISBN 978-0-8493-3251-7.
- ^ Pankaj Jalote. An Integrated Approach to Software Engineering. Springer Science & Business Media. 1997: 372. ISBN 978-0-387-94899-7.
- ^ Ryder, B.G. Constructing the Call Graph of a Program. IEEE Transactions on Software Engineering. May 1979, SE–5 (3): 216–226. doi:10.1109/tse.1979.234183.
- ^ Grove, David; DeFouw, Greg; Dean, Jeffrey; Chambers, Craig; Grove, David; DeFouw, Greg; Dean, Jeffrey; Chambers, Craig. Call graph construction in object-oriented languages. ACM SIGPLAN Notices (ACM). 9 October 1997, 32 (10): 108, 108–124, 124. doi:10.1145/263700.264352.
- ^ Eisenbarth, T.; Koschke, R.; Simon, D. Aiding program comprehension by static and dynamic feature analysis. Proceedings IEEE International Conference on Software Maintenance. ICSM 2001. 2001: 602–611. ISBN 0-7695-1189-9. doi:10.1109/icsm.2001.972777.
- ^ Musco, Vincenzo; Monperrus, Martin; Preux, Philippe. A large-scale study of call graph-based impact prediction using mutation testing. Software Quality Journal. 26 July 2016, 25 (3): 921–950. arXiv:1812.06286
. doi:10.1007/s11219-016-9332-8.
- ^ Gao, Debin; Reiter, Michael K.; Song, Dawn. Gray-box extraction of execution graphs for anomaly detection. Proceedings of the 11th ACM conference on Computer and communications security - CCS '04. ACM. 25 October 2004: 318–329. ISBN 1581139616. doi:10.1145/1030083.1030126.