Automated Debugging of Datalog Programs

Datalog has become a widely adopted language in program analysis, security, and data-intensive systems. However, debugging Datalog programs remains fundamentally challenging due to their declarative semantics, lack of explicit control flow, and massive scale of derived facts. Existing approaches, such as inspecting proof trees, algorithmic debugging, or interactive debugging, all require developers to manually navigate through deeply recursive derivations, which quickly becomes infeasible for real-world programs. In this paper, we take a step toward fully automated debugging of Datalog programs. Our key insight is to reinterpret Datalog execution through a statistical lens: instead of explaining individual facts, we analyze multiple facts collectively, treating derived facts as test cases and their proof trees as execution spectra. This abstraction enables us to adapt Spectrum-based Fault Localization (SBFL) to Datalog, bridging the paradigm gap between declarative logic programs and automated debugging techniques originally designed for imperative languages. To enable systematic evaluation, we construct, to the best of our knowledge, the first benchmark suite for Datalog debugging, comprising 96 real-world instances (37 unique faults) mined from the evolution history of the Doop framework. Each instance is annotated with ground-truth faulty rules and organized under a three-level fault taxonomy. Experimental results demonstrate that our approach effectively localizes faults without any user interaction. The best suspiciousness metric achieves 87.50% Hit@1 (i.e., top-1 hit rate) for faulty rule localization, while faulty predicate localization reaches 37.50%–53.12% Hit@1.