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

Cite as @seo-2024-correctly (helia, typst) · \cite{seo-2024-correctly} (LaTeX)
BibTeX
bibtex · 14 lines
@inproceedings{seo-2024-correctly,
  doi = {10.4230/LIPICS.ITP.2024.33},
  url = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITP.2024.33},
  author = {Seo, Audrey and Lam, Christopher and Grossman, Dan and Ringer, Talia},
  keywords = {proof transformations, compiler validation, program logics, proof engineering, Theory of computation → Logic and verification, Theory of computation → Hoare logic, Software and its engineering → Compilers},
  language = {en},
  title = {Correctly Compiling Proofs About Programs Without Proving Compilers Correct},
  volume = {309},
  pages = {33:1-33:20},
  publisher = {Schloss Dagstuhl – Leibniz-Zentrum für Informatik},
  year = {2024},
  copyright = {Creative Commons Attribution 4.0 International license},
  booktitle = {15th International Conference on Interactive Theorem Proving (ITP 2024)}
}
hayagriva YAML (typst)
yaml · 18 lines
seo-2024-correctly:
  type: article
  title: Correctly Compiling Proofs About Programs Without Proving Compilers Correct
  author:
  - Seo, Audrey
  - Lam, Christopher
  - Grossman, Dan
  - Ringer, Talia
  date: 2024
  page-range: 33:1-33:20
  url: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITP.2024.33
  serial-number:
    doi: 10.4230/LIPICS.ITP.2024.33
  parent:
    type: proceedings
    title: 15th International Conference on Interactive Theorem Proving (ITP 2024)
    publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
    volume: 309
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.
PDF · DOI · pldb

Interactive proofs in higher-order concurrent separation logic krebbers-2017-interactive

PDF · DOI · pldb

Iris: Monoids and Invariants as an Orthogonal Basis for Concurrent Reasoning jung-2015-iris

PDF · DOI · pldb

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.
PDF · DOI · pldb

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.
PDF · DOI · pldb

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.
DOI

Certification of Compiler Optimizations Using Kleene Algebra with Tests kozen2000certification

DOI
External (38)
seo-2024-correctly reference entries/refs/seo-2024-correctly/seo-2024-correctly.hel