The Burden of Proof: Automated Tooling for Rapid Iteration on Large Mechanised Proofs
This program is tentative and subject to change.
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 hundreds 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 the challenges in proof engineering this, we developed \supersketch{}, a tool that automates the generation of proofs involving multiple subgoals in Isabelle/HOL, enabling efficient management and maintenance of large-scale proofs. We discuss the iterative development of the inductive invariant, the lack of modularity in proofs of inductive invariants, and how \supersketch{} mitigates these issues. We further contribute tools to fix corner cases that cannot be fully automated with \supersketch{}, such as correcting proof scripts invalidated by upstream definition changes. This allowed us to drop simplifying restrictions in our model whilst retaining the correctness proof, as we avoid significant manual effort inspecting and fixing the broken lines of the original proof when making the model more general. Our work provides insights into proof engineering practices and highlights the need for improved support in proof assistants for large-scale mechanized proofs.
This program is tentative and subject to change.
Sun 27 AprDisplayed time zone: Eastern Time (US & Canada) change
14:00 - 15:30 | |||
14:00 30mTalk | The Burden of Proof: Automated Tooling for Rapid Iteration on Large Mechanised Proofs Research Track Chengsong Tan Imperial College London, Kaihong, Alastair F. Donaldson Imperial College London, Jonathan Julian Huerta y Munive Czech Technical University, John Wickerson Imperial College London | ||
14:30 30mTalk | A proof-based ground algebraic meta-model for reasoning on ASTD in Event-B Research Track Christophe Chen INPT-ENSEEIHT/IRIT, Peter Rivière INPT-ENSEEIHT / IRIT, University of Toulouse, France, Neeraj Kumar Singh INPT-ENSEEIHT/IRIT, Guillaume Dupont INPT–ENSEEIHT, Yamine Ait Ameur IRIT/INPT-ENSEEIHT, Marc Frappier Université de Sherbrooke, Canada | ||
15:00 30mTalk | Probabilistic Model Checking of Disaster Resource Distribution Strategies Research Track |