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

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

公式 (2) 中展示了一个实例 Datalog 程序, 其中包含 2 条用于计算图中的可达性信息的规则. 谓词 edge(X, Y)
表示图中从节点 X 到节点 Y 存在一条边, 谓词 reachable(X, Y) 表示图中从节点 X 到节点 Y 存在一条可达路径. 第
1 条规则表示若 X 和 Y 间存在一条边, 则 Y 从 X 可达; 第 2 条规则表示若从 Z 到 X 可达且 Z 和 Y 间存在一条边,
则 Y 从 X 可达.
给定一个 Datalog 程序以及一组输入事实, 经 Datalog 引擎评估后得到一组输出事实. Datalog 引擎通常使用
自底向上的评估模型, 它重复应用规则, 直到不再有新的事实产生或达到终止条件. 为了在计算的时候尽量避免重
复之前迭代中已经完成的结果, 提出了一种名为半朴素法 (semi-naive) 的更优的自底向上评估方法. 此外, 在实际
应用中, Datalog 常常需要处理大规模的数据集和复杂的查询, 涉及到输入事实的变化. 为了提高 Datalog 的性能,
引入了增量评估技术. 基于差分数据流的增量评估是一种优化技术, 它通过跟踪输入数据的变化, 并更新相应的输
出结果, 从而避免重复计算和减少计算开销. 这种增量评估技术在处理大规模数据和持续查询时非常有效, 显著提
高了 Datalog 的查询性能和效率.
如今, Datalog 已经发展成为一类语言规范: 由于 Datalog 在不同应用场景中的发展和拓展, 出现了一些不同
的 Datalog 方言. 不同的 Datalog 方言加入了为了增强语言表现力或方便程序员开发而设计的拓展语言特性. 例如
增量规则重写器
bddbddb [19] 、Soufflé [15] 、DDlog [14] 等. 尽管这些方言间并不能直接互通, 它们都可以被归类为“Datalog 语言”.
Datalog 方言的实现被称为 Datalog 引擎.
最后介绍 Datalog 语言在程序分析领域中的应用. 最初, 静态分析研究人员因为使用传统的命令式语言实现
具体的程序分析算法而感到困扰, 因为这需要开发人员具备强大的工程能力. 大量的开发时间并未用于实现算法,
而是用于处理各种细节性的工程问题, 例如极其复杂的数据结构设计、内存管理、程序并行化过程中的信号量同
步、死锁问题的解决、异常处理、边界条件检查甚至性能调优等.
声明式的 Datalog 语言在这方面有其突出的优势: 由于声明式语言的抽象特性, 这类工程问题可以委托给
Datalog 引擎处理, 让开发人员可以专注于算法逻辑, 无需过多关心底层实现细节. Datalog 语言在指针分析领域的
应用可以追溯到 2006 年的 bddbddb [19] . Doop 是当前最先进的 Java 指针分析框架, 其同样采用了基于 Datalog 的
声明式分析范式. Doop 将指针分析算法表述为 Datalog 规则, 并实现了一个从 Java 程序中抽取语义信息并转换
为 Datalog 引擎可接受的输入事实格式的前端. 通过这种方式, Doop 框架成功地将指针分析从指针赋值图上的一
个图计算问题转换为了 Datalog 引擎上的一个数据查询问题.

2 DDoop 框架

本节我们主要介绍针对 Java 语言的增量指针分析框架 DDoop 的架构设计, 并介绍实现中的相关细节. 在现
有非增量的 Doop 指针分析框架的基础上, 我们在 DDoop 框架中提出了增量输入事实生成技术和 DDlog 增量分
析程序自动生成技术, 以兼容复用 Doop 框架中已有的大量指针分析实现, 并提供高效的透明增量化支持. 图 1 展
示了 DDoop 增量指针分析框架的整体架构.

前端
待分析程序 增量事实生成器 增量事实 上一轮
分析结果

后端
分析选项 增量分析程序 分析结果

Soufflé 规则 DDlog 规则 DDlog 编译器
图 1 框架整体架构