Spirea: A Mechanized Concurrent Separation Logic for Weak Persistent Memory
Open Access
- 16 October 2023
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 7 (OOPSLA2) , 632-657
Abstract
Weak persistent memory (a.k.a. non-volatile memory) is an emerging technology that offers fast byte-addressable durable main memory. A wealth of algorithms and libraries has been developed to explore this exciting technology. As noted by others, this has led to a significant verification gap. Towards closing this gap, we present Spirea, the first concurrent separation logic for verification of programs under a weak persistent memory model. Spirea is based on the Iris and Perennial verification frameworks, and by combining features from these logics with novel techniques it supports high-level modular reasoning about crash-safe and thread-safe programs and libraries. Spirea is fully mechanized in the Coq proof assistant and allows for interactive development of proofs with the Iris Proof Mode. We use Spirea to verify several challenging examples with modular specifications. We show how our logic can verify thread-safety and crash-safety of non-blocking durable data structures with null-recovery, in particular the Treiber stack and the Michael-Scott queue adapted to persistent memory. This is the first time durable data structures have been verified with a program logic.Keywords
Funding Information
- Villum Foundation (25804)
This publication has 23 references indexed in Scilit:
- Weak persistency semantics from the ground up: formalising the persistency semantics of ARMv8 and transactional modelsProceedings of the ACM on Programming Languages, 2019
- Iris from the ground up: A modular foundation for higher-order concurrent separation logicJournal of Functional Programming, 2018
- A persistent lock-free queue for non-volatile memory2018
- Interactive proofs in higher-order concurrent separation logic2017
- Linearizability of Persistent Memory Objects Under a Full-System-Crash Failure Model2016
- A Program Logic for C11 Memory Fences2015
- GPS2014
- Memory persistency2014
- Relaxed separation logic2013
- Mnemosyne2011