Certified Compilation

Core Idea

Certified compilation produces a compiler whose behavior is proven correct by a machine-checked formal proof. A certified compiler guarantees that the compiled code behaves identically to the source program — miscompilation bugs are impossible by mathematical proof, not by testing. CompCert (the foundational example) is a certified C compiler where every optimization pass is formally verified in Coq to preserve program semantics. The proof demonstrates a simulation or bisimulation between source and compiled code: any observable behavior (input/output, termination, failure) of the source is faithfully reproduced by the compiled code. This provides absolute assurance that the compiler will not introduce subtle bugs that testing might miss.

Explainer

Every programmer knows the frustration: a compiler bug sneaks a miscompilation into production code. The program works correctly in isolation but fails in specific contexts because the compiler incorrectly optimized or transformed it. Compiler bugs are rare but devastating because they strike at a level of abstraction the programmer trusts completely. Certified compilation solves this problem at its root: prove mathematically that the compiler is correct.

CompCert, developed by Xavier Leroy and colleagues, demonstrated that certified compilation is practical. CompCert is a compiler from a subset of C to multiple target architectures (x86, PowerPC, ARM), with every transformation pass proven correct in Coq. The proof is machine-checked, meaning no argument is accepted unless the Coq kernel formally verifies it. The result is a compiler with an absolute guarantee: any observable behavior (input/output, termination, failure) of a C program compiled by CompCert will be identical to the behavior if that program were executed by a reference interpreter of C semantics.

The approach has two main components:

1. Formal semantics: Both the source language (C) and target language (assembly) are formalized mathematically. This is not a vague description but a precise definition of every operation, rule, and edge case. For C, this includes pointer operations, type conversions, memory layout, and undefined behavior boundaries. For the target assembly, it includes instruction execution, memory access, register semantics.

2. Verified transformations: Each compiler pass (parsing, type checking, optimization, code generation, register allocation) is implemented and proven to preserve semantics. A proof of semantic preservation for a pass P says: given a source program S that satisfies source semantics, the output P(S) satisfies target semantics and exhibits identical observable behavior.

The key insight is the simulation relation (or bisimulation): a formal notion of "same behavior." A backward simulation says that for every step of the target program (compiled), there is a corresponding step (or sequence of steps) of the source program, and the states remain "equivalent" throughout execution. This equivalence is carefully defined to ignore irrelevant differences (variable names, intermediate machine states) while preserving observable behaviors.

Practical implications:

• No miscompilation bugs: Unlike conventional compilers tested on large benchmark suites, CompCert's correctness is absolute. A bug in the verified transformation is mathematically impossible; any failure must lie outside the verified scope (e.g., in the un-verified parts like preprocessing or linking).

• Scope tradeoff: CompCert doesn't support every C feature (some undefined behaviors, dangerous casts, volatile access are excluded) and doesn't target every architecture. But the subset it covers is suitable for systems programming and critical applications.

• Performance: CompCert includes optimizations (constant propagation, dead code elimination, common subexpression elimination, instruction scheduling). The compiler is 80-90% as fast as GCC on many benchmarks, demonstrating that certified compilation doesn't require sacrificing performance.

• Widespread applicability: CompCert has been applied to verify embedded systems, aerospace software, and critical infrastructure. The guarantee that no compiler-introduced bugs can appear provides enormous value in high-assurance contexts.

Beyond CompCert:

• Sel4 microkernel: The seL4 operating system kernel (a microkernel used in military/critical systems) was verified in Isabelle/HOL, including compilation to executable code.
• Cryptol: A domain-specific language for cryptographic specifications, with a certified compiler to C.
• CakeML: A dialect of Standard ML with a fully certified compiler from source to machine code, verified in HOL4.

The cost of certified compilation is development effort: CompCert took many years and extensive formalization effort. But as proof automation improves and certified compiler frameworks are reused, the cost is decreasing. The benefit — absolute assurance of compiler correctness — is increasingly valuable for critical systems where a single bug can have catastrophic consequences.

The fundamental question certified compilation raises is: how much can we trust automation? The answer CompCert provides is: we can trust compilers completely if we formalize their behavior and mechanically verify it. This is not a rejection of testing or engineering rigor but a complement: formal proof for the parts we can formalize, testing and review for the parts we cannot.