Stateless Model Checking Under a Reads-Value-From Equivalence
Authors:
Open Access
- 15 July 2021
- book chapter
- Published by Springer Nature
- p. 341-366
Abstract
Stateless model checking (SMC) is one of the standard approaches to the verification of concurrent programs. As scheduling non-determinism creates exponentially large spaces of thread interleavings, SMC attempts to partition this space into equivalence classes and explore only a few representatives from each class. The efficiency of this approach depends on two factors: (a) the coarseness of the partitioning, and (b) the time to generate representatives in each class. For this reason, the search for coarse partitionings that are efficiently explorable is an active research challenge.In this work we present $${\text {RVF-SMC}}$$ , a new SMC algorithm that uses a novelreads-value-from (RVF)partitioning. Intuitively, two interleavings are deemed equivalent if they agree on the value obtained in each read event, and read events induce consistent causal orderings between them. The RVF partitioning is provably coarser than recent approaches based on Mazurkiewicz and “reads-from” partitionings. Our experimental evaluation reveals that RVF is quite often a very effective equivalence, as the underlying partitioning is exponentially coarser than other approaches. Moreover, $${\text {RVF-SMC}}$$ generates representatives very efficiently, as the reduction in the partitioning is often met with significant speed-ups in the model checking task.
Keywords
All Related Versions
This publication has 27 references indexed in Scilit:
- Stateless model checking concurrent programs with maximal causality reduction2015
- Optimal dynamic partial order reduction2014
- Iterative context bounding for systematic testing of multithreaded programsACM SIGPLAN Notices, 2007
- Dynamic partial-order reduction for model checking software2005
- State space reduction using partial order techniquesInternational Journal on Software Tools for Technology Transfer, 1999
- Testing Shared MemoriesSIAM Journal on Computing, 1997
- Model checking for programming languages using VeriSoft1997
- Refining dependencies improves partial-order verification methods (extended abstract)1993
- All from one, one for all: on model checking using representatives1993
- Trace theory1987