Implementing systems in proof assistants like Coq and proving their correctness in full formal detail has consistently demonstrated promise for making extremely strong guarantees about critical software, ranging from compilers and operating systems to databases and web browsers. Unfortunately, these verications demand such heroic manual proof effort, even for a single system, that the approach has not been widely adopted. We demonstrate a technique to eliminate the manual proof burden for verifying many properties within an entire class of applications, in our case reactive systems, while only expending effort comparable to the manual verication of a single system. A crucial insight of our approach is simultaneously designing both (1) a domain-specic language (DSL) for expressing reactive systems and their correctness properties and (2) proof automation which exploits the constrained language of both programs and properties to enable fully automatic, pushbutton verication. We apply this insight in a deeply embedded Coq DSL, dubbed REFLEX, and illustrate REFLEXs expressiveness by implementing and automatically verifying realistic systems including a modern web browser, an SSH server, and a web server. Using REFLEX radically reduced the proof burden: in previous, similar versions of our benchmarks written in Coq by experts, proofs accounted for over 80% of the code base; our versions require no manual proofs.
Coq, Proof Assistants, Reactive Systems, Formal Verification
Jul 21, 2014