Certifying Code Generation with Coq

Guaranteeing correctness of compilation is a major precondition for correct software. Code generation can be one of the most error-prone tasks in a compiler. One way to achieve trusted compilation is certifying compilation. A certifying compiler generates for each run a proof that it has performed the compilation run correctly. The proof is checked in a separate theorem prover. If the theorem prover is content with the proof, one can be sure that the compiler produced correct code.

This paper presents a certifying code generation phase for a compiler translating an intermediate language into assembler code. The time spent for checking the proofs is the bottleneck of certifying compilation. We exhibit an improved framework for certifying compilation and present considerable advances to overcome this bottleneck. Our framework comprises a checker -- an executable program that is formalized within a theorem prover to increase the speed of distinct subtasks of certificate checking. We prove our checker correct and thus are able to use it instead of traditional proving techniques within our theorem prover environment. We compare our implementation featuring the Coq theorem prover to an older implementation. Our current implementation is feasible for medium to large sized programs.

Keywords: Translation Validation, Certifying Compilation, Theorem Proving, Coq.