fbpx
维基百科

函式呼叫圖

行進 30, 2023

函式呼叫圖（call graph，也稱為call multigraph）[1][2]，屬於控制流圖[3]，可以展示计算机程序中函式之間的關係。每一個節點是一個函式，每一個邊(f, g)表示函式f呼叫函式g。若其中有出現互相呼叫的環，表示程式中可能有遞迴呼叫。

用Python程式產生的函式呼叫圖

基本概念

函式呼叫圖可以由動態程式分析產生（動態函式呼叫圖），也可以由靜態程式分析產生（靜態函式呼叫圖）[4]。動態函式呼叫圖是程式執行過程的記錄，可能是效能分析工具所輸出的。動態函式呼叫圖可以準確的描述這次程式執行時,各函式之間的關係。但會遺漏這次沒有執行到的程式碼。靜態函式呼叫圖則是設法表示所有可能執行情形下，所有函式之間的關係。準確的靜態函式呼叫圖是不可判定问题，因此靜態函式呼叫圖是多半只是近似情形。函式呼叫圖上有所有函式之間的呼叫關係，但有可能其中有一些呼叫是永遠不會執行到的。

函式呼叫圖可以定義來呈現不同程度的準確度。更準確的函式呼叫圖會更近似真正程式的行為，不過要計算的時間會比較長，要儲存的資料也會比較多。最準確的函式呼叫圖是完全「上下文相關」（context-sensitive），針對每一個函式，圖中會對不同情形，不同呼叫堆疊下的呼叫，有不同的節點。全上下文相關的函式呼叫圖稱為呼叫上下文樹（英语：calling context tree）。利用動態程式分析可以輕易的產生，不過會花許多的記憶體。呼叫上下文樹一般不會用靜態程式分析產生，因為對大型程式會花許多時間。最不準確的函式呼叫圖稱為「上下文無關」（context-insensitive），針對每一個函式只會有一個節點。

若程式語言中有动态分派的特性（例如Java或C++）,要產生準確的靜態程式分析會需要假名分析（英语：alias analysis）的結果[5]。相對的，要得到準確的假名分析也需要函式呼叫圖。許多靜態分析系統可以同步產生這二份資料，解決這個看似無限迴圈的問題。

用途

函式呼叫圖有幾種不同的用途。其中一個簡單的應用是找出沒有被其他程式呼叫的子函式。函式呼叫圖可以當做文件，有助於程式設計師的程式理解[6]。函式呼叫圖也是進一步分析的基礎，例如追蹤某一變數數值在各子函式中的變化，或是進行變更影響分析[7]。函式呼叫圖可以用來偵測異常的程式執行，或是偵測代碼注入攻擊[8]。

範例的圖

以下是用gprof（英语：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] |

相關條目

  • 相依性圖（英语：Dependency graph）
  • 功能樹

參考資料

  1. ^ 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. 
  2. ^ Uday Khedker; Amitabha Sanyal; Bageshri Sathe. Data Flow Analysis: Theory and Practice. CRC Press. 2009: 234. ISBN 978-0-8493-3251-7. 
  3. ^ Pankaj Jalote. An Integrated Approach to Software Engineering. Springer Science & Business Media. 1997: 372. ISBN 978-0-387-94899-7. 
  4. ^ 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. 
  5. ^ 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. 
  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. 2001: 602–611. ISBN 0-7695-1189-9. doi:10.1109/icsm.2001.972777. 
  7. ^ 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. 
  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. 

行進 30, 2023
函式呼叫圖, 此條目可参照英語維基百科相應條目来扩充, 若您熟悉来源语言和主题, 请协助参考外语维基百科扩充条目, 请勿直接提交机械翻译, 也不要翻译不可靠, 低品质内容, 依版权协议, 译文需在编辑摘要注明来源, 或于讨论页顶部标记, href, template, translated, page, html, title, template, translated, page, translated, page, 标签, call, graph, 也稱為call, multigraph, 屬於控制流圖, 可以. 此條目可参照英語維基百科相應條目来扩充 若您熟悉来源语言和主题 请协助参考外语维基百科扩充条目 请勿直接提交机械翻译 也不要翻译不可靠 低品质内容 依版权协议 译文需在编辑摘要注明来源 或于讨论页顶部标记 a href Template Translated page html title Template Translated page Translated page a 标签 函式呼叫圖 call graph 也稱為call multigraph 1 2 屬於控制流圖 3 可以展示计算机程序中函式之間的關係 每一個節點是一個函式 每一個邊 f g 表示函式f呼叫函式g 若其中有出現互相呼叫的環 表示程式中可能有遞迴呼叫 用Python程式產生的函式呼叫圖 目录 1 基本概念 2 用途 3 範例的圖 4 相關條目 5 參考資料基本概念 编辑函式呼叫圖可以由動態程式分析產生 動態函式呼叫圖 也可以由靜態程式分析產生 靜態函式呼叫圖 4 動態函式呼叫圖是程式執行過程的記錄 可能是效能分析工具所輸出的 動態函式呼叫圖可以準確的描述這次程式執行時 各函式之間的關係 但會遺漏這次沒有執行到的程式碼 靜態函式呼叫圖則是設法表示所有可能執行情形下 所有函式之間的關係 準確的靜態函式呼叫圖是不可判定问题 因此靜態函式呼叫圖是多半只是近似情形 函式呼叫圖上有所有函式之間的呼叫關係 但有可能其中有一些呼叫是永遠不會執行到的 函式呼叫圖可以定義來呈現不同程度的準確度 更準確的函式呼叫圖會更近似真正程式的行為 不過要計算的時間會比較長 要儲存的資料也會比較多 最準確的函式呼叫圖是完全 上下文相關 context sensitive 針對每一個函式 圖中會對不同情形 不同呼叫堆疊下的呼叫 有不同的節點 全上下文相關的函式呼叫圖稱為呼叫上下文樹 英语 calling context tree 利用動態程式分析可以輕易的產生 不過會花許多的記憶體 呼叫上下文樹一般不會用靜態程式分析產生 因為對大型程式會花許多時間 最不準確的函式呼叫圖稱為 上下文無關 context insensitive 針對每一個函式只會有一個節點 若程式語言中有动态分派的特性 例如Java或C 要產生準確的靜態程式分析會需要假名分析 英语 alias analysis 的結果 5 相對的 要得到準確的假名分析也需要函式呼叫圖 許多靜態分析系統可以同步產生這二份資料 解決這個看似無限迴圈的問題 用途 编辑函式呼叫圖有幾種不同的用途 其中一個簡單的應用是找出沒有被其他程式呼叫的子函式 函式呼叫圖可以當做文件 有助於程式設計師的程式理解 6 函式呼叫圖也是進一步分析的基礎 例如追蹤某一變數數值在各子函式中的變化 或是進行變更影響分析 7 函式呼叫圖可以用來偵測異常的程式執行 或是偵測代碼注入攻擊 8 範例的圖 编辑以下是用gprof 英语 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 相關條目 编辑相依性圖 英语 Dependency graph 功能樹參考資料 编辑 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 amp 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 取自 https zh wikipedia org w index php title 函式呼叫圖 amp oldid 75224259, 维基百科，wiki，书籍，书籍，图书馆，

文章

，阅读，下载，免费，免费下载，mp3，视频，mp4，3gp， jpg，jpeg，gif，png，图片，音乐，歌曲，电影，书籍，游戏，游戏。