Search papers, labs, and topics across Lattice.
This paper introduces Mizzle, a complete concurrent incorrectness logic designed to enhance bug-finding capabilities of large language models (LLMs) by requiring them to provide machine-checked proofs that validate reported bugs. By leveraging incorrectness logics, Mizzle ensures that only genuine bugs are reported, effectively reducing the number of false alarms that burden developers. The authors demonstrate Mizzle's soundness and completeness through its mechanization in the Rocq proof assistant, showcasing its application in certifying bugs in concurrent OCaml programs.
LLMs can now certify bug reports with machine-checked proofs, drastically cutting down on false alarms in software development.
Large language models are increasingly used to find bugs in real-world programs, but they also produce a flood of false alarms that waste developers'time. We propose a method to prevent these false alarms by requiring an LLM to accompany each bug report with a machine-checked proof, in a program logic, that the reported bug is real. We follow the approach of incorrectness logics, whose under-approximate reasoning establishes that a claimed behavior is genuinely reachable, and hence a true positive. In our case, however, the logic must model a realistic programming language, have a mechanization so that proofs can be checked, and be complete, so that no real bug is ruled out for want of a derivation. We present Mizzle, an incorrectness separation logic for concurrent programs written in a substantial subset of OCaml, parametric in the notion of incorrectness. We mechanize Mizzle in the Rocq proof assistant on top of the Iris framework, and we prove that it is both sound (that is, it never justifies a false alarm) and complete (that is, every incorrect execution admits a derivation). We instantiate Mizzle with three notions of incorrectness: stuckness (triggering undefined behavior), the non-linearizability of a data structure, and the presence of a race. As a proof of concept, we illustrate how an LLM can use Mizzle in order to certify the existence of a bug.
