静态分析R程序的数据流

《Proceedings of the ACM on Programming Languages》：Statically Analyzing the Dataflow of R Programs

R语言动态特性静态分析框架设计与实验验证。摘要：提出处理R语言动态特性的静态数据流分析框架，生成数据流图并实现程序切片。实验验证在779个切片点正确率达99.7%，平均分析时间576ms，内存占用213kB，程序切片缩减84.8%。

　　

摘要

R编程语言主要用于统计计算，主要由没有计算机科学背景的研究人员使用。R提供了许多动态特性和独特功能，这些特性很难通过静态分析来理解，例如动态作用域、惰性求值以及动态副作用等。同时，R生态系统缺乏能够帮助研究人员理解和改进代码的复杂分析工具。在本文中，我们提出了一种针对R编程语言的新型静态数据流分析框架，该框架能够处理R程序的动态特性，并生成给定R程序的数据流图。这种数据流图在多种分析中都非常有用，包括程序切片分析，我们通过一个概念验证来实现这一点。核心分析机制是对R程序抽象语法树的标准化版本进行状态化处理，跟踪（重新）定义、值、函数调用、副作用以及动态控制流，从而为每个程序生成一个数据流图。我们使用一个包含779个来自实际R脚本的合理切片点的手动策划数据集，通过输出等价性测试来评估分析的正确性。此外，我们还基于R语言的功能和R解释器的实现设计了一组系统测试用例，测量了4,230个实际R脚本以及R包管理器CRAN上20,815个包的运行时间和内存消耗。我们还评估了我们的程序切片器的召回率、准确性，并比较了其与现有技术的优劣。在我们的等价性测试套件中，我们几乎正确地分析了对所有程序，其中99.7%的手动策划切片点保持了相同的输出结果。平均而言，分析数据流需要576毫秒的时间，存储程序的数据流图大约需要213KB的内存。这表明我们的分析方法能够快速且准确地分析实际代码。我们的程序切片器平均减少了84.8%的代码元素，显示出其在提高程序理解能力方面的潜力。