PyCG: Practical Call Graph Generation in Python
PyCG: Practical Call Graph Generation in Python
复制标题
PyCG：Python 中的实用调用图生成
DOI：
10.1109/icse43902.2021.00146
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Dimitris Mitropoulos
中科院分区：
文献类型：
--
作者：
Vitalis Salis;Thodoris Sotiropoulos;Panos Louridas;D. Spinellis;Dimitris Mitropoulos
调用图在不同的环境中发挥着重要作用，例如分析和漏洞传播分析。对于模块化且包含动态功能和高阶函数的高级语言来说，以有效的方式生成调用图可能是一项具有挑战性的任务。尽管该语言很受欢迎，但旨在为 Python 程序生成调用图的工具却很少。更糟糕的是，这些工具存在一些有效性问题，限制了它们在实际程序中的实用性。我们提出了一种实用的、静态的方法来在 Python 中生成调用图。我们通过过程间分析来计算函数、变量、类和模块的程序标识符之间的所有赋值关系。基于这些赋值关系，我们通过解析对潜在调用函数的所有调用来生成最终的调用图。值得注意的是，底层分析被设计为高效且可扩展，处理多个 Python 功能，例如模块、生成器、函数闭包和多重继承。我们使用两个基准测试来评估我们的原型实现（我们称之为 PyCG）：一个包含小型 Python 程序的微基准测试套件和一组包含几个流行的现实世界 Python 包的宏基准测试。我们的结果表明 PyCG 可以在不到一秒的时间内有效处理数千行代码（1k LoC 平均为 0.38 秒）。此外，它在精确度和召回率方面都优于 Python 的最新技术：PyCG 实现了约 99.2% 的高精确度和约 69.9% 的足够召回率。最后，我们通过使用真实示例展示 GitHub 的“安全咨询”通知服务的潜在增强功能，展示了 PyCG 如何帮助依赖性影响分析。
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.
JVM 托管语言的调用图构建研究
影响因子：
7.4
作者：
Ali, Karim;Lai, Xiaoni;Luo, Zhaoyi;Lhotak, Ondrej;Dolby, Julian;Tip, Frank
通讯作者：
Tip, Frank
JavaScript Promise 的推理模型
影响因子：
--
作者：
Madsen, Magnus;Lhoták, Ondřej;Tip, Frank
通讯作者：
Tip, Frank