End-to-End Verification of Stack-Space Bounds for C Programs

Quentin Carbonneaux, Jan Hoffmann, Tahina Ramananandro, Zhong Shao (FLINT, Yale University)

PLDI 2014

• Conference Paper (final version at ACM Digital Library)
• Paper preprint
• Virtual machine archive (login: pldi  password: pldi  ) and usage instructions (which are also already included in the archive) submitted to the PLDI 2014 Artifact Evaluation process. Our reviewers from the Artifact Evaluation Committee unanimously judged our artifact as exceeding the expectations of our paper.
• Technical report (YALEU/DCS/TR-1487)
• Coq development (ZIP archive also including the abovementioned technical report)
• C source code of a stack monitor (written by Quentin Carbonneaux) showing the actual run-time stack consumption of any C program after its execution.
• Poster presented by Quentin Carbonneaux at the POPL 2014 student poster session
• Slides of the talk given at the INRIA Gallium team seminar.

Verified compilers guarantee the preservation of semantic properties and thus enable formal verification of programs at the source level. However, important quantitative properties such as memory and time usage still have to be verified at the machine level where interactive proofs tend to be more tedious and automation is more challenging.
This article describes a framework that enables the formal verification of stack-space bounds of compiled machine code at the C level. It consists of a verified CompCert-based compiler that preserves quantitative properties, a verified quantitative program logic for interactive stack-bound development, and a verified stack analyzer that automatically derives stack bounds during compilation.
The framework is based on event traces that record function calls and returns. The source language is CompCert Clight and the target language is x86 assembly. The compiler is implemented in the Coq proof assistant and it is proved that crucial properties of event traces are preserved during compilation. A novel quantitative Hoare logic is developed to verify stack-space bounds at the CompCert Clight level. The quantitative logic is implemented in Coq and proved sound with respect to event traces generated by the small-step semantics of CompCert Clight. Stack-space bounds can be proved at the source level without taking into account low-level details that depend on the implementation of the compiler. The compiler fills in these low-level details during compilation and generates a concrete stack-space bound that applies to the produced machine code. The verified stack analyzer is guaranteed to automatically derive bounds for code with non-recursive functions. It generates a derivation in the quantitative logic to ensure soundness as well as interoperability with interactively developed stack bounds.
In an experimental evaluation, the developed framework is used to obtain verified stack-space bounds for micro benchmarks as well as real systems code. The examples include the verified operating system kernel CertiKOS, parts of the MiBench embedded benchmark suite, and programs from the CompCert benchmarks.