Automatic Repair and Deadlock Detection for Parameterized Systems
Authors:
- Swen JacobsSJSwen Jacobs
- Mouhammad SakrMSMouhammad Sakr
- Marcus VölpMVMarcus Völp
Preprint
Abstract
We present an algorithm for the repair of parameterized systems. The repair problem is, for a given process implementation, to find a refinement such that a given safety property is satisfied by the resulting parameterized system, and deadlocks are avoided. Our algorithm uses a parameterized model checker to determine the correctness of candidate solutions and employs a constraint system to rule out candidates. We apply this algorithm on systems that can be represented as well-structured transition systems (WSTS), including disjunctive systems, pairwise rendezvous systems, and broadcast protocols. Moreover, we show that parameterized deadlock detection can be decided in EXPTIME for disjunctive systems, and that deadlock detection is in general undecidable for broadcast protocols.Keywords
All Related Versions
This publication has 23 references indexed in Scilit:
- Parameterized Verification of Systems with Global Synchronization and Guards2020
- Model Checking Parameterised Multi-token Systems via the Composition Method2016
- Tight Cutoffs for Guarded Protocols with Fairness2015
- Parameterized Model Checking of Rendezvous Systems2014
- Parameterized Model Checking of Token-Passing Systems2014
- Bounded synthesisInternational Journal on Software Tools for Technology Transfer, 2012
- Lazy Synthesis2012
- Parameterized Verification of Ad Hoc Networks2010
- Exact and Efficient Verification of Parameterized Cache Coherence Protocols2003
- Reducing Model Checking of the Many to the Few2000