一句话：提出静态跨过程分析生成 Python 调用图，精度约 99.2%，千行代码平均 0.38 秒。
调用图在性能分析与漏洞传播分析等场景中至关重要，但 Python 这类模块化、动态且支持高阶函数的高级语言难以高效生成调用图，现有工具在真实程序上效果不佳。本文提出一种实用的 Python 调用图静态生成方法：通过跨过程分析计算函数、变量、类与模块等程序标识符之间的赋值关系，再基于这些关系解析所有可能被调用的函数，从而构建调用图；该分析在设计上兼顾效率与可扩展性，并处理模块、生成器、闭包与多重继承等 Python 特性。原型工具 PyCG 在包含小型程序的微基准与多个流行真实 Python 包的宏基准上评估，平均 0.38 秒即可处理千行代码，且在精度与召回上均优于现有 Python 方案，精度约 99.2%、召回约 69.9%。最后，论文以真实案例展示 PyCG 可增强 GitHub“安全公告”通知服务，用于依赖影响分析。
Call graphs play an important role in different contexts, such as profiling and vulnerability propagation analysis. Generating call graphs in an efficient manner can be a challenging task when it comes to high-level languages that are modular and incorporate dynamic features and higher-order functions. Despite the language's popularity, there have been very few tools aiming to generate call graphs for Python programs. Worse, these tools suffer from several effectiveness issues that limit their practicality in realistic programs. We propose a pragmatic, static approach for call graph generation in Python. We compute all assignment relations between program identifiers of functions, variables, classes, and modules through an inter-procedural analysis. Based on these assignment relations, we produce the resulting call graph by resolving all calls to potentially invoked functions. Notably, the underlying analysis is designed to be efficient and scalable, handling several Python features, such as modules, generators, function closures, and multiple inheritance. We have evaluated our prototype implementation, which we call PyCG, using two benchmarks: a micro-benchmark suite containing small Python programs and a set of macro-benchmarks with several popular real-world Python packages. Our results indicate that PyCG can efficiently handle thousands of lines of code in less than a second (0.38 seconds for 1k LoC on average). Further, it outperforms the state-of-the-art for Python in both precision and recall: PyCG achieves high rates of precision ~99.2% and adequate recall ~69.9%. Finally, we demonstrate how PyCG can aid dependency impact analysis by showcasing a potential enhancement to GitHub's "security advisory" notification service using a real-world example.
DOI 原文 · arXiv · PDF（开放获取） · DBLP
@inproceedings{SalisSLSM21,
title = {PyCG: Practical Call Graph Generation in Python},
author = {Vitalis Salis and Thodoris Sotiropoulos and Panos Louridas and Diomidis Spinellis and Dimitris Mitropoulos},
booktitle = {ICSE},
year = {2021},
doi = {10.1109/icse43902.2021.00146}
}