Paper Info
Title
End-to-end verification of stack-space bounds for C programs
Abstract
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 system code. The examples include the verified operating-system kernel CertiKOS, parts of the MiBench embedded benchmark suite, and programs from the CompCert benchmarks. The derived bounds are close to the measured stack-space usage of executions of the compiled programs on a Linux x86 system.
Year
DOI
Venue
2014
10.1145/2594291.2594301
PLDI
Keywords
Field
DocType
quantitative program logic,machine code,event trace,novel quantitative hoare logic,stack-space bound,quantitative logic,end-to-end verification,compcert clight,source level,c program,important quantitative property,formal verification,compiler construction
Programming language,Computer science,Hoare logic,Compiler,Theoretical computer science,Automation,Compiler construction,Machine code,Soundness,Proof assistant,Formal verification
Conference
Volume
Issue
ISSN
49
6
0362-1340
Citations 
PageRank 
References 
5
0.45
0
Authors
4
Name
Order
Citations
PageRank
Quentin Carbonneaux1472.11
Jan Hoffmannand220316.61
Tahina Ramananandro3787.64
Zhong Shao489768.80