Types, bytes, and separation logic
Open Access
- 17 January 2007
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGPLAN Notices
- Vol. 42 (1) , 97-108
Abstract
We present a formal model of memory that both captures the low-level features of C's pointers and memory, and that forms the basis for an expressive implementation of separation logic. At the low level, we do not commit common oversimplifications, but correctly deal with C's model of programming language values and the heap. At the level of separation logic, we are still able to reason abstractly and efficiently. We implement this framework in the theorem prover Isabelle/HOL and demonstrate it on two case studies. We show that the divide between detailed and abstract does not impose undue verification overhead, and that simple programs remain easy to verify. We also show that the framework is applicable to real, security- and safety-critical code by formally verifying the memory allocator of the L4 microkernel.Keywords
This publication has 23 references indexed in Scilit:
- CCured: type-safe retrofitting of legacy softwareACM Transactions on Programming Languages and Systems, 2005
- Integration of a Software Model Checker into IsabelleLecture Notes in Computer Science, 2005
- A Verification Environment for Sequential Imperative Programs in Isabelle/HOLLecture Notes in Computer Science, 2005
- Checking Memory Safety with Blast2005
- Towards Mechanized Program Verification with Separation Logic2004
- Certifying Machine Code Safety: Shallow Versus Deep Embedding2004
- No-Longer-Foreign: Teaching an ML compiler to speak C “natively”Electronic Notes in Theoretical Computer Science, 2001
- Type classes and overloading in higher-order logic1997
- Kit: a study in operating system verificationIEEE Transactions on Software Engineering, 1989
- Specification and verification of the UCLA Unix security kernelCommunications of the ACM, 1980