Pushing the Limits of Compiler Verification PDF Download

Author: Eric Mullen
Publisher:
ISBN:
Category :
Languages : en
Pages : 86

Get Book Here

Book Description
Modern computer systems rely on the correctness of at least one compiler for correct operation. Formal verification is a powerful technique for constructing correct systems. While there have been many efforts to develop formally verified compilers, those compilers are still not widely used. In this thesis, I present two major systems developments and one case study which push the limits of compiler verification, towards more and better verified compilers. Œuf: Verifying systems by implementing them in the programming language of a proof assistant (e.g., Gallina for Coq) lets us directly leverage the full power of the proof assistant for verifying the system. But, to execute such an implementation requires extraction, a large complicated process that is in the trusted computing base (TCB). Here I present Œuf, a verified compiler from a subset of Gallina to assembly. Œuf's correctness theorem ensures that compilation preserves the semantics of the source Gallina program. I describe how Œuf's specification can be used as a foreign function interface to reason about the interaction between compiled Gallina programs and surrounding shim code. Additionally, Œuf maintains a small TCB for its front-end by reflecting Gallina programs to Œuf source and automatically ensuring equivalence using computational denotation. This design enabled my collaborators and me to implement some early compiler passes (e.g., lambda lifting) in the untrusted reflection and ensure their correctness via translation validation. To evaluate Œuf, we compile Appel’s SHA256 specification from Gallina to x86 and write a shim for the generated code, yielding a verified sha256sum implementation with a small TCB. Using Œuf: Œufwas developed in order to allow verified systems to be developed and verified in Coq, compiled to executable code using Œuf, with all guarantees proven at the Gallina level preserved through compilation to the assembly level. In order to evaluate this goal, I built the WordFreq verified system in Coq, compiled it with Œuf, and preserve the correctness guarantee through to the generated assembly code. Here I present the WordFreq verified system, its correctness guarantee, and the major parts of its correctness proof. I discuss the development of the system and its proof, as well as the axiomatic primitives necessary to tie it together. Peek: Transformations over assembly code are common in many compilers. These transformations are also some of the most bug-dense compiler components. Such bugs could be eliminated by formally verifying the compiler, but state-of-the-art formally verified compilers like CompCert do not support assembly-level program transformations. Here I present Peek, a framework for expressing, verifying, and running meaning-preserving assembly-level program transformations in CompCert. Peek contributes four new components: a lower level semantics for CompCert x86 syntax, a liveness analysis, a library for expressing and verifying peephole optimizations, and a verified peephole optimization pass built into CompCert. Each of these is accompanied by a correctness proof in Coq against realistic assumptions about the calling convention and the system memory allocator. Verifying peephole optimizations in Peek requires proving only a set of local properties, which my collaborators and I have proved are sufficient to ensure global transformation correctness. We have proven these local properties for 28 peephole transformations from the literature. Here I discuss the development of our new assembly semantics, liveness analysis, representation of program transformations, and execution engine; describe the verification challenges of each component; and detail techniques we applied to mitigate the proof burden.