Reflex DSL: Automating Formal Proofs for Reactive Systems

University of California, San Diego
University of Washington

Funded by NSF Award 1228967

We built and verified the kernels of a Web browser and SSH server using Reflex, without any manual proof effort. Watch them in action! [Web browser] [SSH server]

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 verifications 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 verification of a single system. A crucial insight of our approach is simultaneously designing both (1) a domain-specific 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 verification. We apply this insight in a deeply embedded Coq DSL, dubbed Reflex, and illustrate Reflex 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.

Our talk from PLDI 2014

We have a VM image (Version 0.1, 06/07/2014, 3.05 GB) that you can use to run the web browser, SSH server, and web server that we built using Reflex. You can run the proof automation on the properties for the kernels for these systems. You can also use it to build some of your own systems using Reflex. Here are the instructions for the VM.

Source code (GitHub)