POPL 2025
Sun 19 - Sat 25 January 2025 Denver, Colorado, United States

This program is tentative and subject to change.

Sun 19 Jan 2025 11:18 - 11:36 at Hopscotch - Proof Stability and Applications

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 Jan

Displayed time zone: Mountain Time (US & Canada) change

11:00 - 12:30
Proof Stability and ApplicationsDafny at Hopscotch
11:00
18m
Talk
Helping users to reduce Brittleness in their Dafny programs - a success story
Dafny
11:18
18m
Talk
Towards Proof Stability in SMT-based Program Verification
Dafny
Yi Zhou Carnegie Mellon University, Bryan Parno Carnegie Mellon University
11:36
18m
Talk
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
18m
Talk
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
18m
Talk
Well-Behaved (Co)algebraic Semantics of Regular Expressions in Dafny
Dafny
Stefan Zetzsche Amazon Web Services, Wojciech Różowski University College London