Automated Debugging of Datalog Programs

幕后故事

这篇工作的 idea 来源于左志强老师——这是比较显然的，因为他曾经做过 Datalog 的研究，也做过 SBFL (Spectrum-Based Fault Localization) 的研究。这篇工作的初稿是于2021年左右成型，但是一直缺少真实的 Datalog Bug Benchmark 用于做比较扎实的 Evaluation。由于左老师后面专心于做其它工作了，他便把这个工作交给我们继续做下去。

为了把这个工作做出来，钮鑫涛老师决定需要构建一个真实的 Datalog 故障的 Benchmark，而这个过程比较一波三折。一开始，钮老师是把这个任务交给计算机系的一位硕士生做，但是他没有做成。后来钮老师来了苏州校区的智能软件与工程学院之后，这个任务被交给了一个本科生大创的团队。在此之后的故事就交给卫佳申同学来讲述：

这项工作背后的故事，可以从 2023 年 11 月的一次大创说起。当时钮老师把他在 2021 年与左老师合作时的一个 idea 交给我们：从 Doop 的历史版本中构建 Datalog 故障基准，并在这个基准上验证我们的自动故障定位方法。那也是我们第一次接触 Datalog，第一次了解 Doop 和 Soufflé。

这个目标听起来似乎很简明直了，只需要解决两个核心问题：第一，回退 Doop 历史版本，得到对应版本的 Datalog 文件；第二，让 Soufflé 在运行时输出我们方法所需要的信息。也正是这两个问题，几乎贯穿了整个项目。

一开始的进展并不顺利，我们连最新版 Doop 的构建都失败了，最后发现是 build.gradle 中某处依赖的链接需要更新。这个小问题也埋下了伏笔：后续回退历史版本时，依赖问题也会反复出现。最初我们人工从 Doop 2019—2024 的 commit 中挑出修改幅度较大的版本，希望从中捕获 bug；同时修改适配 Doop 的 Soufflé 2.0.2 的解释器模式，让它输出运行时信息。但现实并不符合我们的计划预期，到 2024 年 12 月大创结束时，我们甚至没有构建出一个真实 bug 实例。Doop 的大量 commit 无法成功构建；成功构建的版本多集中在 2021 年及之后，而它们之间的 Datalog 文件变化很小；零星的早期版本又因跨度太大，人工分析几乎无效。Soufflé 的运行同样困难：修改后的 Soufflé 需要记录证明树，一开始的思路是修改 Soufflé 运行时，深入它构建出的语法树节点进行魔改，让 Soufflé 一边运行一遍输出中间数据用于数据分析，付出了许多努力但是成效有限，并且在大型 Datalog 程序上内存开销巨大，解释器模式几乎无法运行；早期 Doop 的 Datalog 语法也不兼容 Soufflé 2.0.2，Soufflé 会报出大量错误。最终，我们只能在 toy Datalog 程序上初步验证方法。

此后近一年时间里，项目因学业等原因停滞。一直到 2025 年 9 月，我们决定重启这项工作，重新攻克这两个核心问题。

首先是 Doop 回退。我们重新整理了自 2017 年起更完整的 commit 集合，逐一解决构建失败。大多数问题来自找不到依赖，于是我们下载依赖到本地缓存，并在回退时自动修改build.gradle实现从本地缓存读取。有些版本则是存在 doop 自定义的依赖包名，有些干脆直接是源码有小错误或兼容问题，我们也一一做了自动化修复。运行方面，Doop 在线运行会持续调用线上仓库，服务器会由于网络问题导致超时，我们改为在实体机上生成 Datalog 文件后自动推送到服务器，并记录超时 commit。经过反复试错，到 2025 年 11 月，我们终于获得所有筛选 commit 对应的 Datalog 文件。

其次是 Soufflé。基于之前的教训，我们直接锁定 Soufflé 1.5.1——这是 Doop 刚支持 Soufflé 时适配的版本。我们先把构建系统从 automake 迁移到 CMake，方便调试；然后聚焦编译器模式。编译器模式不仅运行成本远低于解释器模式，而且允许我们直接操作编译产生的中间 C++ 文件，极大减少了修改原版 Soufflé 语法树逻辑和调试它的负担。Soufflé 1.5.1 版本较早，其编译器优化并不完善。一方面，这使 C++ 结构更一致，便于自动捕获插桩位置；另一方面，相似 Datalog 规则有时被优化、有时没有，也增加了插桩的复杂性。除了一些自适应的插桩操作外，我们做了两个关键处理，其一是去除 .plan 语句，避免同一条规则生成多个 C++ 语句；其二是标注元素类型，便于后续成功对齐不同版本的输出元组。到 2025 年 12 月，我们基本解决该问题并开始构建 benchmark。通过比较筛选后的相对相邻版本的 Datalog，人工识别 bug，最终确定 37 个唯一 bug。

但 2025 年 12 月底，新的问题出现：旧版 Doop 运行依赖的在线仓库停止维护，不可访问了。此时我们虽已人工分析出 bug，但比较是基于一段跨度的 commit，尚未拿到精确修复该bug 的commit 对应的 Datalog 文件。于是我们用脚本扫描 Doop 源码，模拟Doop逻辑生成对应版本所需配置的 datalog 文件。尽管 Doop 源码随时间变化很大，我们还是根据不同时期的典型特征，成功复原了不同版本所需三种配置的 Datalog 文件。

投稿过程同样一波三折。我们最初计划投 ISSTA，但临近 2026 年 1 月投稿时，论文尚未完成，部分设计仍有漏洞，于是决定改投截止日期在 2026 年 3 月的 OOPSLA。这期间我们进一步完善基准和方法，但评估运行成本很大，截止前仍只得到一次评估数据。原本我们设想谓词级定位结合均值和方差排序，但实验发现方差对准确率没有增益，不符合最初的预期，多次尝试也没有找到更好的组合，最终只采用可疑值均值进行谓词级定位。反复修改后，我们提交了初稿。

坦白说，对这份临时反复修改的初稿，我们起初并不抱很高期望，更多是抱着听取意见的心态投出。在收到评审意见前，我们继续优化实验、压缩时间成本（将原本10天才能跑完的一轮评估压缩到一天多）、修复新发现的细小故障、调整文件结构等等。2026 年 5 月，我们收到三位评审的审稿意见。评审给了我们 rebuttal 的机会，他们建设性的意见也为我们指明了优化方向。我们用一个小规模试点噪声实验回应了评审对人工标注需求的担忧，并逐一回答每个问题，最终获得 minor revision。随后我们补充了完整噪声实验与分析，优化行文逻辑。经过一步步修改完善，我们在 7 月提交了 revision 版本，并最终在 8 月得知最终接收的消息，对此我们倍感荣幸。