Modular development of certified program verifiers with a proof assistant
Author:
Open Access
- 16 September 2006
- journal article
- conference paper
- Published by Association for Computing Machinery (ACM) in ACM SIGPLAN Notices
- Vol. 41 (9) , 160-171
Abstract
I report on an experience using the Coq proof assistant to develop a program verification tool with a machine-checkable proof of full correctness. The verifier is able to prove memory safety of x86 machine code programs compiled from code that uses algebraic datatypes. The tool's soundness theorem is expressed in terms of the bit-level semantics of x86 programs, so its correctness depends on very few assumptions. I take advantage of Coq's support for programming with dependent types and modules in the structure of my development. The approach is based on developing a library of reusable functors for transforming a verifier at one level of abstraction into a verifier at a lower level. Using this library, it's possible to prototype a verifier based on a new type system with a minimal amount of work, while obtaining a very strong soundness theorem about the final product.Keywords
This publication has 13 references indexed in Scilit:
- Formal certification of a compiler back-end or2006
- A language-based approach to functionally correct imperative programming2005
- Combining programming with theorem proving2005
- A Framework for Certified Program Analysis and Its Applications to Mobile-Code Safety2005
- The view from the leftJournal of Functional Programming, 2004
- Extracting a Data Flow Analyser in Constructive LogicLecture Notes in Computer Science, 2004
- Stack-based typed assembly languageJournal of Functional Programming, 2003
- Toward a foundational typed assembly languageACM SIGPLAN Notices, 2003
- Verified lightweight bytecode verificationConcurrency and Computation: Practice and Experience, 2001
- From system F to typed assembly languageACM Transactions on Programming Languages and Systems, 1999