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

2616 软件学报 2024 年第 35 卷第 6 期

2.1.5 增量前端剪枝优化
通过增量单元的设计, 我们已经大幅减少了需要重新抽取输入事实的类和方法数量. 然而在实现过程中, 由于
框架使用的 Soot 框架的类加载机制, 为了获取一个类的所有依赖, 需要加载大量的类. 不仅包括输入的 jar 包中的
所有类, 还包括这些类可能引用的系统类库中的类. 这个过程是迭代的, 直到无法继续找到传递依赖的类为止. 这
样的类加载策略是为了尝试对输入的待分析程序进行一个尽可能精确的建模. 在 DDoop 框架的早期实现中, 我们
采用了这种类加载策略, 以保证与原始 Doop 框架有等价的指针分析精度. 然而, 这种实现相对低效.
在我们关注的变更频繁的增量场景下, 一次代码提交引入的变化通常是局部的, 不会导致整个程序引用的基
础类库发生巨大的变化. 因此, 全面类加载中也包含重复计算. 因此, 我们提出了对类加载过程的剪枝优化策略, 通
过减少需要加载的类数量来提升前端增量输入事实生成的速度.
图 4 展示了我们所采用的剪枝策略. 在增量输入事实生成的类加载过程中, 我们不再加载间接引用的类库中
的类. 也即在加载类时, 我们只会包括应用类和被应用类直接引用的类库中的类. 然而, 我们的剪枝策略可能会对
精度产生影响. 我们将在第 3.4 节和第 4.2 节分别从实验和理论层面就剪枝策略对精度的影响进行讨论.

引擎需要对所有已经有的
lib classes
.......

class class class
剪枝

class class
APP classes

class

class class class

图 4 类加载过程剪枝策略示意图

2.2 后端: 增量分析程序生成
Datalog 是 Prolog 的一个子集, 它是一种更为限制和精简的逻辑编程语言. 现代 Datalog 引擎都遵循了 Datalog
语言的理论规范, 但为了增强表现能力都对语言进行了拓展. 然而不同引擎之间的拓展并不完全相同, 并且目前也
不存在通用的标准语法. 因此, 不同的 Datalog 引擎之间一般并不能直接互通.
Soufflé 和 DDlog 是当前流行的两种 Datalog 引擎. Soufflé 是 Doop 框架目前所采用的 Datalog 引擎, 而 DDlog
支持高效的增量评估. 如果将 Doop 中面向 Soufflé 引擎实现的分析规则直接提交给 DDlog 编译器, 因为语法细节
层面的细微变化, 是无法通过编译的.
这意味着, 切换具体的 Datalog Datalog 规则进行语义等价的重写, 这无疑是一项艰
巨的任务. Doop 框架在发展过程中就有过一次切换 Datalog 引擎的经历, 它从对学术使用有相当限制的 LogicBlox
引擎切换到了当时新发布的、专为程序分析开发的 Soufflé 引擎. 开发者为此耗费了大量精力 (大约 10 人月) [20] 完
全重写了指针分析的规则库, 将 LogicBlox 引擎所用的 LogiQL 语言切换到了 Soufflé 语言.
在我们框架的设计目标中, 我们需要兼容 Doop 框架已有的丰富的 Soufflé 指针分析规则. 这就意味着我们需
要对 Doop 框架中已有的 Soufflé 指针分析规则进行完全的重写. 然而, 这其中存在两项主要的挑战, 使得像 Doop
开发者曾经做过的那样进行手动转换在软件工程领域变得不可接受.
(1) Doop 框架利用 Soufflé 语言的模块化特性动态地根据具体的分析选项情况从规则库中“装配”生成新的规
则, 而 DDlog 语言中没有显式的模块化语法. 这就意味着, 对于 Doop 中的数十种精度的分析及其对应的大量的分