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

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

情况下后端每次评估的耗时, 如图 10 所示. 从图 10 可以看出, 第 11 次提交对应的代码变更显著拉高了增量分析
耗时的平均值. 分析此次提交对应的代码变更可以发现, 在这一次提交中, 代码的变化引发了上下文方面的大范围
变化, 在相对更加复杂的上下文敏感性选项下, 这个问题会更加容易变得不可拓展. 但是从我们的实验评估中的所
有 665 次评估数据 (7 种精度设置下 5 个项目各有 19 次增量分析) 来看, 这种异常情况出现的概率 (2/665) 并不高.
整体上看, DDoop 的增量化支持依旧可以在绝大多数场景下获得性能优势.
10 000
单次后端计算时间 (s) 1 000

100
10

0.1 1
iter 0 iter 1 iter 2 iter 3 iter 4 iter 5 iter 6 iter 7 iter 8 iter 9 iter 10 iter 11 iter 12 iter 13 iter 14 iter 15 iter 16 iter 17 iter 18 iter 19
迭代次数
框架中整合
图 10 selective2objH 精度设置下 DDoop 在 ZooKeeper 上的后端耗时

实验结果表明, 我们的 DDoop 增量分析框架在代码频繁变更的场景下, 通过对代码变更进行增量分析, 在分
析耗时方面能够实现比现有先进的 Doop 框架的全量分析的显著加速. 并且在变更越频繁, 变更次数更多的场景
下, 我们的增量分析框架的累计耗时加速优势将更为显著.

3.3 RQ2: 兼容性
与 Doop 中现有指针分析规则兼容是 DDoop 增量框架设计中的一大核心目标. 为了评估 DDoop 增量框架对
Doop 框架中现有指针分析规则的兼容性, 在这部分的实验中, 我们将 DDoop 增量框架和两个现有的尝试为
Doop 框架提供基础增量支持的工作进行对比. 具体而言, 我们将 DDoop 框架与一个基于 Soufflé-elastic 实现基础
增量支持的 Doop-SE 框架以及另一个初步整合了 DDlog 引擎的 Doop-DDlog 框架进行兼容性测试. 基于实验设
置中选定的 7 种不同精度的指针分析规则以及 Doop 中提供的一种简化的指针分析规则 micro, 我们分别使用
DDoop 和 Doop-SE, 在我们的实验基准集中的 5 个真实世界大型 Java 项目上对 20 次连续的代码提交对应的 jar
包进行指针分析. 由于 Doop-DDlog 当前并无开放可获取的工具, 我们无法对其进行实际的实验评估, 因此我们这
里采用了其论文 [17] 中报告的结果和结论.
表 2 展示了 DDoop、Doop-SE 和 Doop-DDlog 对 Doop 现有指针分析规则的兼容性情况. 从表 2 可以看出,
我们的 DDoop 能够兼容所有 8 种精度的指针分析规则, 而 Doop-SE 和 Doop-DDlog 都只能处理简化的 micro 分
析规则, 在其他复杂分析规则上的兼容性测试均无法正确运行. 对于 Doop-SE, 就目前 Soufflé-elastic 的实现而言,
在面对 Doop 中的绝大多数指针分析规则时, 它并不能将规则文件正确的编译或是解释执行, 对报错信息和实现
细节进行分析可以发现, 这个问题的直接原因是出在其中的规则重排器组件实现中. 此外, 对于 Doop 规则中的聚
合函数 (例如 sum()), 它实际上也并没有提出有效的增量解决方案, 它只提供了 Soufflé 中有限的语法结构的增量
能力. 对于 Doop-DDlog, 它试图在 Doop DDlog 引擎以提供增量分析的能力, 然而和我们更为完善的
规则重写器相比, 它只实现了从 Soufflé 到 DDlog 的简单转换, 并且明确指出了其只支持了 Doop 中最简单的“self-
contained”分析和简化的 micro 分析. 此外, 根据其实验评估, 它只是在每一轮分析的时候将 Soufflé 引擎换成
DDlog 引擎, 实际运行的还是完整评估, 并未有效地利用 DDlog 引擎的增量能力.

表 2 实验数据集

Analysis framework CI lobj 2objH 1callsite 1type 2typeH selective2objH micro
DDoop √ √ √ √ √ √ √ √
Doop-SE × × × × × × × √
Doop-DDlog × × × × × × × √