Computer and Information Science

Title: “Scaling Machine-Checkable Systems Verification in Coq”

System software like operating systems and hypervisors forms the critical backbone of our computing infrastructure. However, due to their size and complexity, these systems often contain vulnerabilities that can compromise security. Formal verification offers a solution by mathematically proving software correctness, but its adoption is hindered by the substantial effort required to create these proofs.

In this talk, I will introduce Spoq, a highly automated verification framework designed to dramatically reduce the proof effort in verifying system software. Spoq leverages LLVM to automatically translate C code—including full C semantics like macros, inline assembly, and compiler directives—into Coq, a proof assistant for formal verification. This automation eliminates the need for manual modification of source code prior to verification. Spoq leverages a layering proof strategy and introduces novel Coq tactics and transformation rules to automatically generate layer specifications and refinement proofs to simplify verification of concurrent system software. Spoq also supports easy integration of manually written layer specifications and refinement proofs. We applied Spoq to verify a multiprocessor KVM hypervisor implementation. Verification using Spoq required 70% less proof effort than the manually written specifications and proofs to verify an older implementation. Furthermore, the proofs using Spoq hold for the unmodified implementation that is directly compiled and executed.