Towards Proof Stability in SMT-based Program Verification
This program is tentative and subject to change.
Verification languages such as Dafny enable powerful proof automation with Satisfiability Modulo Theories (SMT) solvers. However, SMT-based verification is vulnerable to proof instability, where superficial changes to the source program may cause spurious verification failures. In this extended abstract, we discuss our line of work on proof instability. We start by reviewing our methodology to detect instability and a measurement study on five verification query sets generated by Dafny and F*. We then review our finding on how irrelevant SMT query context contributes to instability, along with a pruning algorithm to reduce instability. Finally, we discuss our ongoing work to control the relevant but unstable context. In this line of work, we quantitatively and systematically study the causes and mitigation of instability, and we hope SMT-based verification will eventually reach a point where we can have stable proofs while leveraging powerful automation.
This program is tentative and subject to change.
Sun 19 JanDisplayed time zone: Mountain Time (US & Canada) change
11:00 - 12:30 | |||
11:00 18mTalk | Helping users to reduce Brittleness in their Dafny programs - a success story Dafny | ||
11:18 18mTalk | Towards Proof Stability in SMT-based Program Verification Dafny | ||
11:36 18mTalk | Verifying the Fisher-Yates Shuffle Algorithm in Dafny Dafny Stefan Zetzsche Amazon Web Services, Tancrède Lepoint Amazon Web Services, Jean-Baptiste Tristan Amazon Web Services, Mikael Mayer Automated Reasoning Group, Amazon Web Services | ||
11:54 18mTalk | Shipwright: A Modular Framework for Verifying Liveness of Byzantine Fault Tolerant Systems Dafny Derek Leung MIT, Nickolai Zeldovich Massachusetts Institute of Technology, USA, M. Frans Kaashoek Massachusetts Institute of Technology, USA | ||
12:12 18mTalk | Well-Behaved (Co)algebraic Semantics of Regular Expressions in Dafny Dafny |