Foundational Verification of Running-Time Bounds for Interactive Programs
Some important domains of software demand concrete bounds on how long functions may run, for instance for real-time cyberphysical systems where missed deadlines may damage industrial machinery. Such programs may interact with external devices throughout execution, where time deadlines ought to depend on, for instance, sensor readings (e.g. we only scramble to close a valve immediately when a sensor reports that a tank is about to overflow). We present the first software-development toolchain that delivers first-principles proofs of meaningful time bounds for interactive machine code, while allowing all per-application programming and verification to happen at the source-code level. We allow C-like programs to be proved against separation-logic specifications that constrain their running time, and such proofs are composed with verification of a compiler to RISC-V machine code. All components are implemented and proved inside the Coq proof assistant, producing final theorems whose statements depend only on machine-language formal semantics and some elementary specification constructions for describing running time. As a capstone case study, we extended a past verification (of a real microcontroller-based cyberphysical system) to bound time between arrival of network packets and actuation of an attached device.
Mon 12 JanDisplayed time zone: Brussels, Copenhagen, Madrid, Paris change
16:00 - 17:30 | |||
16:00 22mTalk | Mechanized Dominator Tree Certificationdistinguished paper CPP Jean-Christophe Léchenet Université Côte d’Azur, Inria DOI Pre-print | ||
16:22 22mTalk | Brack: A Verified Compiler for Scheme via CakeML CPP Pascal Lasnier University of Cambridge, Jeremy Yallop University of Cambridge, Magnus O. Myreen Chalmers University of Technology | ||
16:45 22mTalk | Verified VCG and Verified Compiler for Dafny CPP Daniel Nezamabadi NTU Singapore, Magnus O. Myreen Chalmers University of Technology, Yong Kiam Tan Institute for Infocomm Research, A*STAR | ||
17:07 22mTalk | Foundational Verification of Running-Time Bounds for Interactive Programs CPP Thomas Carotti MIT, Andy Tockman Massachussetts Institute of Technology, Pratap Singh CMU, Andres Erbsen Google, Samuel Gruetter ETH Zurich, Adam Chlipala Massachusetts Institute of Technology | ||