Verified Software Toolchain

The software toolchain includes static analyzers to check assertions about your program; optimizing compilers to translate your program to machine language; operating systems and libraries to supply context for your program. The Verified Software Toolchain project assures with machine-checked proofs that the assertions claimed at the top of the toolchain really hold in the machine-language program, running in the operating-system context.

Research results

Verifiable C tools (diagram at left)
Book, software, documentation

Technical overview of the VST logic

Mechanized Software Library
for Separation Logic and Indirection Theory

VeriStar certified entailment checker

VeriSmall foundationally verified shape analysis

Other publications below

Participants

Andrew W. Appel
Princeton University

Lennart Beringer
Princeton University

William Mansky
U. of Illinois at Chicago

Qinshi Wang
Princeton University

Alumni, collaborators, and affiliated researchers

David Naumann
Stevens Inst. of Tech.

Santiago Cuellar
Princeton University

Qinxiang Cao
Princeton U

Gordon Stewart
Princeton U

Josiah Dodds
Princeton U

Robert Dockins
Princeton U

Aquinas Hobor
Nat'l U. Singapore

Xavier Leroy
INRIA

Rationale

In some application domains it is not enough to build reliable software systems, one wants proved-correct software. This is the case for safety-critical systems (where software bugs can cause injury or death) and for security-critical applications (where an attacker is deliberately searching for, and exploiting, software bugs). Since proofs are large and complex, the proof-checking must be mechanized. Machine-checked proofs of real software systems are difficult, but now should be possible, given the recent advances in the theory and engineering of mechanized proof systems applied to software verification. But there are several challenges:

Real software systems are usually built from components in different programming languages.
Some parts of the program need full correctness proofs, which must be constructed with great effort; other parts need only safety proofs, which can be constructed automatically.
One reasons about correctness at the source-code level, but one runs a machine-code program translated by a compiler; the compiler must be proved correct.
These proofs about different properties, with respect to different programming languages, must be integrated together end-to-end in a way that is also proved correct and machine-checked.

We address these challenges by defining Verifiable C, a program logic for the C programming language. Verifiable C is proved sound with respect to the operational semantics of CompCert C; in turn, the CompCert verified optimizing C compiler is proved correct with respect to the assembly-language semantics of the PowerPC, ARM, and x86 processors.

Publications

Abstraction and Subsumption in Modular Verification of C Programs, by Lennart Beringer and Andrew W. Appel. FM2019: 23rd International Symposium on Formal Methods, October 2019.

VST-Floyd: A separation logic tool to verify correctness of C programs, by Qinxiang Cao, Lennart Beringer, Samuel Gruetter, Josiah Dodds, and Andrew W. Appel. Journal of Automated Reasoning 61(1), pp. 367-422, 2018. (Local copy)

A verified messaging system, by William Mansky, Andrew W. Appel, and Aleksey Nogin. OOPSLA'17: ACM Conference on Object-Oriented Programming Systems, Languages, and Applications, October 2017. Proceedings of the ACM on Programming Languages (PACM/PL) volume 1, issue OOPSLA, paper 87, 2017.

Bringing order to the separation logic jungle, by Qinxiang Cao, Santiago Cuellar, and Andrew W. Appel. APLAS'17: 15th Asian Symposium on Programming Languages and Systems, November 2017.

Modular Verification for Computer Security, by Andrew W. Appel. In CSF 2016: 29th IEEE Computer Security Foundations Symposium, June 2016.

Verified Correctness and Security of OpenSSL HMAC, by Lennart Beringer, Adam Petcher, Katherine Q. Ye, and Andrew W. Appel. In 24th USENIX Security Symposium, pages 207-221, August 2015.

Compositional CompCert, by Gordon Stewart, Lennart Beringer, Santiago Cuellar, and Andrew W. Appel. POPL 2015: The 42nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 275-287, January 2015. (local copy)

Second Edition: Verification of a Cryptographic Primitive: SHA-256. This is a very minor revision (as explained in its abstract) of Verification of a Cryptographic Primitive: SHA-256, by Andrew W. Appel, ACM Transactions on Programming Languages and Systems 37(2) 7:1-7:31, April 2015.

Verified Correctness and Security of mbedTLS HMAC-DRBG by Katherine Q. Ye, Matthew Green, Naphat Sanguansin, Lennart Beringer, Adam Petcher, and Andrew W. Appel. CCS'17: ACM Conference on Computer and Communications Security, October 2017.

Verified Heap Theorem Prover by Paramodulation, by Gordon Stewart, Lennart Beringer, and Andrew W. Appel. In ICFP 2012: The 17th ACM SIGPLAN International Conference on Functional Programming, September 2012.

A Certificate Infrastructure for Machine-Checked Proofs of Conditional Information Flow, by Torben Amtoft, Josiah Dodds, Zhi Zhang, Andrew Appel, Lennart Beringer, John Hatcliff, Xinming Ou and Andrew Cousino. First Conference on Principles of Security and Trust (POST 2012), March 2012.

VeriSmall: Verified Smallfoot Shape Analysis, by Andrew W. Appel. In CPP 2011: First International Conference on Certified Programs and Proofs, December 2011.

Relational Decomposition, by Lennart Beringer. Proceedings of the Second International Conference on Interactive Theorem Proving (ITP 2011), pages 39-54, August 2011. Springer LNCS 6898.

Verified Software Toolchain, by Andrew W. Appel. In ESOP 2011: 20th European Symposium on Programming, LNCS 6602, pp. 1-17, March 2011.

Relational program logics in decomposed style, by Lennart Beringer, July 2010.

Formal Verification of Coalescing Graph-Coloring Register Allocation, by Sandrine Blazy, Benoit Robillard, and Andrew W. Appel. In ESOP 2010: 19th European Symposium on Programming, March 2010.

A Theory of Indirection via Approximation, by Aquinas Hobor, Robert Dockins, and Andrew W. Appel. In POPL 2010: The 37th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, January 2010.

Local Actions for a Curry-style Operational Semantics by Gordon Stewart and Andrew W. Appel. In PLPV'11: 5th ACM SIGPLAN Workshop on Programming Languages meets Program Verification, January 29, 2011.

A Fresh Look at Separation Algebras and Share Accounting by Robert Dockins, Aquinas Hobor, and Andrew W. Appel. To appear in Seventh Asian Symposium on Programming Languages and Systems (APLAS 2009), December 2009.

Multimodal Separation Logic for Reasoning About Operational Semantics, by Robert Dockins, Andrew W. Appel, and Aquinas Hobor, (to appear) in Twenty-fourth Conference on the Mathematical Foundations of Programming Semantics, May 2008.

Automating Separation Logic for Concurrent C Minor, by William Mansky. Undergraduate thesis, May 2008.

Foundational High-level Static Analysis, by Andrew W. Appel. In CAV 2008 Workshop on Exploiting Concurrency Efficiently and Correctly, July 2008.

Oracle Semantics for Concurrent Separation Logic by Aquinas Hobor, Andrew W. Appel, and Francesco Zappa Nardelli. European Symposium on Programming (ESOP), April 2008. Extended version with appendix.

Separation Logic for Small-step C Minor, by Andrew W. Appel and Sandrine Blazy. in TPHOLs 2007: 20th International Conference on Theorem Proving in Higher-Order Logics, September 2007. Tactics for Separation Logic, by Andrew W. Appel, January 2006.

Funding

Parts of this research are funded by:

Defense Advanced Research Projects Agency, Compositionality and Automation for Robotics Security.
Air Force Office of Scientific Research (via subcontract to Kansas State University), Evidence-based trust in large-scale MLS systems.
National Science Foundation, Combining Foundational and Lightweight Formal Methods to Build Certifiably Dependable Software.

This research has also been supported by Princeton University, INRIA, and National Science Foundation Grant CCF-0540914.

Early research leading to the Verified Software Toolchain was conducted in the Concurrent C minor project.

Last overhaul of this page: April 2013