The Burden of Proof: Automated Tooling for Rapid Iteration on Large Mechanised Proofs
Chenqing Tan, Alastair F. Donaldson, Jonathan Julián Huerta y Munive, John Wickerson · 2025
We report on challenges and solutions in making large mechanised proofs scale, based on our experience proving correctness properties for a cache coherence protocol. This was a difficult proof that required dozens of iterations to get right, and ultimately led to an inductive invariant with nearly 800 conjuncts, and to over 54,000 proof obligations. To address these proof engineering challenges we developed super_sketch, a tool that automates the generation of proofs involving multiple subgoals in Isabelle/HOL, enabling efficient management and maintenance of large-scale proofs. We further contribute super_fix, a tool to fix corner cases that cannot be fully automated with super_sketch, such as correcting proof scripts invalidated by upstream changes to definitions. This allowed us to drop simplifying restrictions in our model while retaining the correctness proof, as we avoid the significant manual effort that would otherwise be required to inspect and fix the broken lines of the original proof when generalising the model. Our work provides insights into proof engineering practices and highlights the need for improved support in proof assistants for large-scale mechanized proofs.