LCS Publication Details
Publication Title: On Verifying a File System Implementation
Publication Author: Arkoudas, Konstantine
Additional Authors: Karen Zee, Viktor Kuncak, Martin Rinard
LCS Document Number: MIT-LCS-TR-946
Publication Date: 5-6-2004
LCS Group: Computer Architecture
Additional URL:
We present a correctness proof for a basic file system implementation. This implementation contains key elements of standard Unix file systems such as inodes and fixed-size disk blocks. We prove the implementation correct by establishing a simulation relation between the specification of the file system (which models the file system as an abstract map from file names to sequences of bytes) and its implementation (which uses fixed-size disk blocks to store the contents of the files). We used the Athena proof checker to represent and validate our proof. Our experience indicates that Athena's use of block-structured natural deduction, support for structural induction and proof abstraction, and seamless connection with high-performance automated theorem provers were essential to our ability to successfully manage a proof of this size.
To obtain this publication:

To purchase a printed copy of this publication please contact MIT Document Services.