Interfacing Compilers, Proof Checkers, and Proofs for Foundational Proof-Carrying Code

Abstract:

Proof-Carrying Code (PCC) is a general framework for the mechanical verification of safety properties of machine-language programs. It allows a code producer to provide an executable program to a code consumer, along with a machine-checkable proof of safety such that the code consumer can check the proof before running the program. PCC has the advantage of small Trusted Computing Base (TCB), since the proof checking can be a simple mechanical procedure. A weakness of previous PCC systems is that the proof-checking infrastructure is based on some complicated logic or type system that is not necessarily sound.

Foundational Proof-Carrying Code (FPCC) aims to further reduce the TCB size by an order of magnitude by building the safety proof based on the simple and trustworthy foundations of mathematical logic. There are three major components in an FPCC system: a compiler, a proof checker, and the safety proof of an input machine-language program. The compiler produces machine code accompanied by a proof of safety. The proof checker verifies, sometimes also reconstructs, the safety proof before the program gets executed.

We have built a prototype system. Our prototype is the first end-to-end FPCC system, including a type-preserving compiler from Core ML to SPARC (based on SML/NJ), a low-level typed assembly language LTAL, a foundational proof-checker Flit, and a nearly complete machine-checkable soundness proof. The system compiles Core ML programs to SPARC code, accompanied with programs in a low-level typed assembly language; these typed assembly programs serve as the proof witnesses of the safety of the corresponding SPARC machine code.

In this thesis, I'll explain the design of interfaces between these components and show how to build an end-to-end FPCC system. We have concluded that a type system (a low-level typed assembly language) should be designed to check machine code, and that the proof-checking should be factored into two stages, namely type-checking of the input machine code and verification of soundness of the type system. Since a type checker can be efficiently interpreted as a logic program, Flit builds in a simple logic programming engine which enables efficient proof-checking.