Verifying observational robustness against a c11-style memory model
Open Access
- 4 January 2021
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 5 (POPL) , 1-33
Abstract
We study the problem of verifying the robustness of concurrent programs against a C11-style memory model that includes relaxed accesses and release/acquire accesses and fences, and show that this verification problem can be reduced to a standard reachability problem under sequential consistency. We further observe that existing robustness notions do not allow the verification of programs that use speculative reads as in the sequence lock mechanism, and introduce a novel "observational robustness" property that fills this gap. In turn, we show how to soundly check for observational robustness. We have implemented our method and applied it to several challenging concurrent algorithms, demonstrating the applicability of our approach. To the best of our knowledge, this is the first method for verifying robustness against a programming language concurrency model that includes relaxed accesses and release/acquire fences.Keywords
Funding Information
- Israel Science Foundation (5166651)
This publication has 31 references indexed in Scilit:
- The Best of Both Worlds: Trading Efficiency and Optimality in Fence Insertion for TSO2015
- Herding CatsACM Transactions on Programming Languages and Systems, 2014
- A Verification-Based Approach to Memory Fence Insertion in PSO Memory Systems2013
- What’s Decidable about Weak Memory Models?2012
- Show No Weakness: Sequentially Consistent Specifications of TSO Libraries2012
- Mathematizing C++ concurrencyACM SIGPLAN Notices, 2011
- Effective Program Verification for Relaxed Memory Models2008
- Making snapshot isolation serializableACM Transactions on Database Systems, 2005
- The model checker SPINIEEE Transactions on Software Engineering, 1997
- Programming for different memory consistency modelsJournal of Parallel and Distributed Computing, 1992