Page 37 - 《软件学报》2024年第6期

沈天琪 等: DDoop: 基于差分式 Datalog 求解的增量指针分析框架 2613

从整体架构上, DDoop 框架主要可分为前端和后端两个部分, 这两个部分都拥有增量特性.
(1) 增量生成输入事实的前端. 其自动化处理待分析程序, 从中抽取变更信息并转化为后端增量评估所需的增
量输入.
(2) 自动化生成 DDlog 增量分析程序的后端. 根据输入的分析选项, 后端会将原始 Doop 框架的 Soufflé 规则
自动化重写为支持增量评估的 DDlog 规则, 并生成相应的增量分析程序.
首先, 我们对图 1 所示的 DDoop 框架的整体运行流程概述如下: 根据分析输入, 我们可以确定分析使用的
Soufflé 指针分析规则, DDoop 后端会将这份分析规则自动化重写为 DDlog 版本的增量分析程序. 随后, DDoop 前
端会收到待分析程序对应的一系列代码提交, 其将会按照顺序, 将代码变更转化为 DDlog 增量分析程序可接受的
增量输入事实形式. 增量分析程序接收到代码变更的增量输入事实后, 增量评估产生分析结果的增量输出.
接下来, 我们将详细介绍 DDoop 框架前端和后端这两个部分.

2.1 前端: 增量输入事实构建
DDoop 框架和 Doop 框架都将指针分析问题归约为 Datalog 程序评估问题. Datalog 引擎接受一组事实和规则
模块视为“增量单元”. 增量单元越大, 每一次出现变更时需要重做的范围就会越大, 但是增量单元越小, 用来判断
作为输入. 在 Doop 框架中, 规则对应指针分析算法, 而输入事实则对应待分析程序的一组语义性质. 为此, 我们需
要一个前端来对待分析程序进行预处理, 从中抽取与指针分析相关的程序语义性质作为 Datalog 引擎的输入事实.
前端的存在是为了实现分析框架的端到端过程: 将不能直接被 Datalog 引擎处理的 jar 包转换为其可接受的输入
事实形式.
Doop 框架中已经提供了一个前端, 能够将一个完整的 Java 程序 (jar 包) 转换为 Soufflé 引擎的输入事实. 其
前端的输入生成器抽取语义信息时不涉及类之间的相互依赖信息. 它使用 Soot 框架加载 jar 包中所有的类字节码
文件, 然后对已加载的每个类并行化的抽取其中的语义信息. 在具体处理时, 每个类中的方法在逻辑上都是独立
的. 但是 Doop 中的前端在我们的增量场景下存在一些问题.
● 第 1 个问题是, Soufflé 引擎和 DDlog 引擎的输入在形式上存在细微差异: DDlog 引擎是为增量评估设计的,
输入时需要标记每条输入事实是插入还是删除 (特别地, 某一条事实在增量过程中的更新会被处理为一条删除旧
值和一条插入新值的组合); 而 Soufflé 引擎将所有输入事实均视为插入.
● 第 2 个问题是, Doop 框架的前端并未考虑到增量设计: 对于待分析程序的每一个版本, 其都会从头开始处
理整个待分析程序. 但在连续输入的增量场景中, 绝大多数的 Java 类文件都是不变的, 对应的语义信息是完全相
同的. 这就导致了重复计算问题.
解决第 1 个问题相对容易, 这只是格式上的区别. 我们只需要: 1) 标记每条输入事实是插入还是删除; 2) 格式
转换. 然而, 对第 2 个问题, 我们需要一个支持增量事实生成的全新前端. 这也是我们在此处的最主要挑战.

2.1.1 框架前端架构
在我们的增量指针分析框架中, 我们希望避免重复计算: 即对于那些在代码变更中未发生变化的类和方法, 我
们可以复用此前生成的输入事实. 为此, 对于给定两个版本的 jar 包, 我们需要一种方案来识别出在代码变更中未
发生变化的类文件, 并在处理时跳过它们. 为此, 我们需要解决以下 3 个主要问题.
(1) 划分合适的基本“增量单元”, 其粒度必须适当. 在实现增量分析时, 选择适当的“增量单元”是至关重要的.
该单元应能在保证分析精度的同时, 最大程度地降低实现和计算的复杂度. 我们需要确定, 是将方法、类还是编译

增量的范围就相对更加复杂.
(2) 找出能够标识增量单元未发生变化的元素, 或者说一种“摘要”. 为了实现快速的增量变更检测, 我们需要
一种能够快速且准确地反映“增量单元”变化的“摘要”机制. 这种机制可以采用“增量单元”哈希值, 或者是结合“增
量单元”的某些性质, 如代码行数, 方法数量等. 选择哪种“摘要”机制取决于它们能否提供足够的信息来判断代码
的变化, 同时又能在短时间内完成计算.
(3) 维护我们在增量过程中的必要信息. 在增量分析过程中, 有效地管理和存储分析信息是一个挑战. 我们需