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

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

不存在 DRed 中的过度删除问题, 在这方面可以相比 DRed 可以取得更好的性能.

5.3 增量计算
随着输入变化而高效地更新计算输出, 而无需从头开始重新计算, 这一点对于许多应用来说可能很重要, 甚至
是必要的. 增量计算的基本想法是在静态算法执行期间维护某些信息, 这些信息可用于在输入变更时高效地更新
输出. 增量计算能够以一种对上层算法透明的方式为算法提供增量化的支持. 增量计算的早期工作包括静态依赖
图 [37] , 函数缓存或记忆化 [38] , 动态依赖图 [39] 等. 而将动态依赖图与记忆化相结合的自调整计算 (self-adjusting computa-
tion) [40] , 显著扩展了增量计算的适用性. Incoop [41] 是自调整计算技术的代表工作之一, 它是一种基于 MapReduce 的
通用增量计算框架, 无需更改一行应用程序代码即可显著提高性能.
差分计算 (differential computation) [42] 是由微软提出的一种新的增量计算模型, 以高效地支持迭代查询, 它扩展
了传统的增量计算以允许任意嵌套迭代. 基于差分计算模型的差分数据流 (differential dataflow, DDF) 现在是增量
Datalog 引擎的主流实现方式, 如 DDlog [17] , Laddder [36] 等. 我们的增量指针分析框架即是基于 DDlog 引擎来提供增
量计算支持, 而无需对上层的指针分析算法进行调整.
另一类增量计算模型是增量图计算 [43] . GraphBolt [44] 通过研究依赖驱动处理的方式来进行增量图计算.

Chronos [45] 是一个专门为在时间图上运行内存中迭代图计算而设计和优化的图计算引擎, 其设计探索了局部性、
并行性和增量计算之间有趣的相互作用. iGraph [46] 是一个针对持续更新的动态图的增量图处理系统. 静态分析中
的很多分析技术都是基于图形式进行计算的, 如数据流分析依赖于控制流图, 指针分析依赖于指针赋值图, 过程间
分析需要调用图. 因此增量图计算可能是未来的增量程序分析的一个重要的可探索方向. 目前 Gu 等人 [47] 在这个
方向进行了初步的探索, 提出了 BigSpa, 这是一个结合了离线批量静态程序分析和在线增量静态程序分析的大数
据图处理系统, 对于小批量更新可以实现近乎实时的增量分析.

6 总结与展望

本文设计并实现了一个增量指针分析框架 DDoop, 旨在解决现有指针分析技术在处理大规模程序的连续代
码提交时耗时过长的问题. 基于带增量评估机制的 DDlog 引擎, DDoop 框架通过前端输入事实增量生成技术以及
后端兼容 Doop 中指针分析规则的自动化增量分析程序生成技术, 能够高效地处理代码变更, 尽可能地复用上一
次分析的结果, 从而降低计算量, 大大节省了指针分析过程所消耗的时间. 实验评估展示, 相较于非增量式的原始
Doop 框架, 我们的增量框架可以获得平均约 5×, 最高达 36×的加速效果.
本文的方法和框架实现目前仍存在一些不足, 这也是我们未来的研究方向: 增量分析的内存消耗较大, 我们未
来计划结合 DDlog 特性进一步优化重写器, 以及探索基于磁盘的中间结果存储策略, 以降低内存使用量; 此外, 我
们的输入事实增量生成的前端采取的剪枝优化技术会带来细微的精度损失, 未来我们计划对优化技术进一步改
进, 以消除精度损失. 我们的增量分析框架不仅探索了对指针分析技术的透明增量化支持, 同时也支持其他能基
于 Datalog 表述的一大类静态分析技术, 这将为软件开发 CI/CD 流程中的静态代码扫描提供了更加高效的解决方
案可能性. 除差分计算之外, 增量图计算也是一类重要的增量计算模型, 我们未来也计划探索基于增量图计算的静
态分析透明增量化技术.

References:
[1] Cai YD, Yao PS, Zhang C. Canary: Practical static detection of inter-thread value-flow bugs. In: Proc. of the 42nd ACM SIGPLAN Int’l
Conf. on Programming Language Design and Implementation. New York: ACM, 2021. 1126–1140. [doi: 10.1145/3453483.3454099]
[2] Grech N, Smaragdakis Y. P/Taint: Unified points-to and taint analysis. Proc. of the ACM on Programming Languages, 2017,
1(OOPSLA): 102. [doi: 10.1145/3133926]
[3] Pradel M, Jaspan C, Aldrich J, Gross TR. Statically checking API protocol conformance with mined multi-object specifications. In: Proc.
of the 34th Int’l Conf. on Software Engineering (ICSE). Zurich: IEEE, 2012. 925–935. [doi: 10.1109/ICSE.2012.6227127]
[4] Zhang QR, Lyu MR, Yuan H, Su ZD. Fast algorithms for Dyck-CFL-reachability with applications to alias analysis. In: Proc. of the 34th
ACM SIGPLAN Conf. on Programming Language Design and Implementation. New York: ACM, 2013. 435–446. [doi: 10.1145/