Using Lightweight Formal Methods to Validate a Key-Value Storage Node in Amazon S3
Authors:
Open Access
- 26 October 2021
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 836-850
Abstract
This paper reports our experience applying lightweight formal methods to validate the correctness of ShardStore, a new key-value storage node implementation for the Amazon S3 cloud object storage service. By "lightweight formal methods" we mean a pragmatic approach to verifying the correctness of a production storage node that is under ongoing feature development by a full-time engineering team. We do not aim to achieve full formal verification, but instead emphasize automation, usability, and the ability to continually ensure correctness as both software and its specification evolve over time. Our approach decomposes correctness into independent properties, each checked by the most appropriate tool, and develops executable reference models as specifications to be checked against the implementation. Our work has prevented 16 issues from reaching production, including subtle crash consistency and concurrency problems, and has been extended by non-formal-methods experts to check new features and properties as ShardStore has evolved.Keywords
This publication has 19 references indexed in Scilit:
- Specifying and Checking File System Crash-Consistency Models2016
- SibylFS2015
- Using Crash Hoare logic for certifying the FSCQ file system2015
- How Amazon web services uses formal methodsCommunications of the ACM, 2015
- Resource Aware ML2012
- Formal Modeling and Analysis of a Flash Filesystem in AlloyLecture Notes in Computer Science, 2008
- A mini challenge: build a verifiable filesystemFormal Aspects of Computing, 2007
- The model checker SPINIEEE Transactions on Software Engineering, 1997
- Model checking for programming languages using VeriSoft1997
- Linearizability: a correctness condition for concurrent objectsACM Transactions on Programming Languages and Systems, 1990