Reference. Correctly Compiling Proofs About Programs Without Proving Compilers Correct
Guaranteeing correct compilation is nearly synonymous with compiler verification. However, the correctness guarantees for certified compilers and translation validation can be stronger than we need. While many compilers do have incorrect behavior, even when a compiler bug occurs it may not change the program’s behavior meaningfully with respect to its specification. Many real-world specifications are necessarily partial in that they do not completely specify all of a program’s behavior. While compiler verification and formal methods have had great success for safety-critical systems, there are magnitudes more code, such as math libraries, compiled with incorrect compilers, that would benefit from a guarantee of its partial specification. This paper explores a technique to get guarantees about compiled programs even in the presence of an unverified, or even incorrect, compiler. Our workflow compiles programs, specifications, and proof objects, from an embedded source language and logic to an embedded target language and logic. We implement two simple imperative languages, each with its own Hoare-style program logic, and a system for instantiating proof compilers out of compilers between these two languages that fulfill certain equational conditions in Coq. We instantiate our system on four compilers: one that is incomplete, two that are incorrect, and one that is correct but unverified. We use these instances to compile Hoare proofs for several programs, and we are able to leverage compiled proofs to assist in proofs of larger programs. Our proof compiler system is formally proven sound in Coq. We demonstrate how our approach enables strong target program guarantees even in the presence of incorrect compilation, opening up new options for which proof burdens one might shoulder instead of, or in addition to, compiler correctness.
Cite
Cites 45 works (7 here)
With notes (7)
ANF preserves dependent types up to extensional equality koronkevich-2022-anf
Many programmers use dependently typed languages such as Coq to machine-verify high-assurance software. However, existing compilers for these languages provide no guarantees after compiling, nor when linking after compilation. Type-preserving compilers preserve guarantees encoded in types and then use type checking to verify compiled code and ensure safe linking with external code. Unfortunately, standard compiler passes do not preserve the dependent typing of commonly used (intensional) type theories. This is because assumptions valid in simpler type systems no longer hold, and intensional dependent type systems are highly sensitive to syntactic changes, including compilation. We develop an A-normal form (ANF) translation with join-point optimization—a standard translation for making control flow explicit in functional languages—from the Extended Calculus of Constructions (ECC) with dependent elimination of booleans and natural numbers (a representative subset of Coq). Our dependently typed target language has equality reflection, allowing the type system to encode semantic equality of terms. This is key to proving type preservation and correctness of separate compilation for this translation. This is the first ANF translation for dependent types. Unlike related translations, it supports the universe hierarchy, and does not rely on parametricity or impredicativity.
Interactive proofs in higher-order concurrent separation logic krebbers-2017-interactive
Iris: Monoids and Invariants as an Orthogonal Basis for Concurrent Reasoning jung-2015-iris
CakeML: A verified implementation of ML kumar_cakeml_2014
We have developed and mechanically verified an ML system called CakeML, which supports a substantial subset of Standard ML. CakeML is implemented as an interactive read-eval-print loop (REPL) in x86-64 machine code. Our correctness theorem ensures that this REPL implementation prints only those results permitted by the semantics of CakeML. Our verification effort touches on a breadth of topics including lexing, parsing, type checking, incremental and dynamic compilation, garbage collection, arbitraryprecision arithmetic, and compiler bootstrapping.
Finding and Understanding Bugs in C Compilers yangFindingUnderstandingBugs
Compilers should be correct. To improve the quality of C compilers, we created Csmith, a randomized test-case generation tool, and spent three years using it to find compiler bugs. During this period we reported more than 325 previously unknown bugs to compiler developers. Every compiler we tested was found to crash and also to silently generate wrong code when presented with valid input. In this paper we present our compiler-testing tool and the results of our bug-hunting study. Our first contribution is to advance the state of the art in compiler testing. Unlike previous tools, Csmith generates programs that cover a large subset of C while avoiding the undefined and unspecified behaviors that would destroy its ability to automatically find wrong-code bugs. Our second contribution is a collection of qualitative and quantitative results about the bugs we have found in open-source C compilers.
Formal verification of a realistic compiler leroy_formal_2009
This paper reports on the development and formal verification (proof of semantic preservation) of CompCert, a compiler from Clight (a large subset of the C programming language) to PowerPC assembly code, using the Coq proof assistant both for programming the compiler and for proving its correctness. Such a verified compiler is useful in the context of critical software and its formal verification: the verification of the compiler guarantees that the safety properties proved on the source code hold for the executable compiled code as well.
Certification of Compiler Optimizations Using Kleene Algebra with Tests kozen2000certification
External (38)
- Dimsum: A decentralized approach to multi-language semantics and verification (2023)
- The coq proof assistant (2023)
- Relational compilation for performance-critical applications: Extensible proof-producing translation of functional models into low-level code (2022)
- Abstraction and subsumption in modular verification of C programs (2021)
- Compcerto: Compiling certified open c components (2021)
- Coq development for the course "Mechanized semantics" (2021)
- Metamath zero: Designing a theorem prover prover (2020)
- Refinement to imperative HOL (2019)
- An abstract stack based approach to verified compositional compilation to machine code (2019)
- VST-Floyd: A Separation Logic Tool to Verify Correctness of C Programs (2018)
- Oeuf: Minimizing the Coq extraction TCB (2018)
- CertiCoq: A verified compiler for Coq (2017)
- Type-preserving cps translation of Σ and Π types is not not possible (2017)
- Linking Types for Multi-Language Software: Have Your Cake and Eat It Too (2017)
- Cogent: Verifying high-assurance file system implementations (2016)
- A framework for the automatic formal verification of refinement from Cogent to C (2016)
- Using crash hoare logic for certifying the fscq file system (2015)
- Deep specifications and certified abstraction layers (2015)
- The bedrock structured programming system: Combining generative metaprogramming and hoare logic in an extensible program verifier (2013)
- Characteristic formulae for the verification of imperative programs (2011)
- Mostly-automated verification of low-level programs in computational separation logic (2011)
- Certificate translation for optimizing compilers (2009)
- Mechanized Semantics for the Clight Subset of the C Language (2009)
- Embedding proof-carrying components into Isabelle (2009)
- Certificate Translation Alongside Program Transformations (2009)
- Ynot: Dependent types for imperative programs (2008)
- Formalizing proof-transforming compilation of Eiffel programs (2008)
- Proof-transforming compilation of programs with abrupt termination (2007)
- Formal certification of a compiler back-end, or: programming a compiler with a proof assistant (2006)
- Proof obligations preserving compilation (2005)
- Theorem reuse by proof term transformation (2004)
- Changing data representation within the Coq system (2003)
- On the completeness of propositional hoare logic (2001)
- Translation validation for an optimizing compiler (2000)
- Proof Analysis, Generalization and Reuse (1998)
- Proof-carrying code (1997)
- Generalization at higher types (1992)
- Proof Transformations in Higher-Order Logic (1987)