Leaf: Modularity for Temporary Sharing in Separation Logic
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) , 31-58
Abstract
In concurrent verification, separation logic provides a strong story for handling both resources that are owned exclusively and resources that are shared persistently (i.e., forever). However, the situation is more complicated for temporarily shared state, where state might be shared and then later reclaimed as exclusive. We believe that a framework for temporarily-shared state should meet two key goals not adequately met by existing techniques. One, it should allow and encourage users to verify new sharing strategies. Two, it should provide an abstraction where users manipulate shared state in a way agnostic to the means with which it is shared. We present Leaf, a library in the Iris separation logic which accomplishes both of these goals by introducing a novel operator, which we call guarding, that allows one proposition to represent a shared version of another. We demonstrate that Leaf meets these two goals through a modular case study: we verify a reader-writer lock that supports shared state, and a hash table built on top of it that uses shared state.Keywords
Funding Information
- NSF/VMware Partnership on Software Defined Infrastructure as a Foundation for Clean-Slate Computing Security (CNS-1700521)
This publication has 28 references indexed in Scilit:
- Impredicative Concurrent Abstract Predicates2014
- Communicating State Transition Systems for Fine-Grained Concurrent Resources2014
- Views2013
- Design, verification and applications of a new read-write lock algorithm2012
- Fictional Separation Logic2012
- Concurrent Abstract Predicates2010
- A Fresh Look at Separation Algebras and Share Accounting2009
- Resources, concurrency, and local reasoningTheoretical Computer Science, 2007
- Permission accounting in separation logicACM SIGPLAN Notices, 2005
- Checking Interference with Fractional Permissions2003