Action-Based Model Checking: Logic, Automata, and Reduction

Stutter invariant properties play a special role in state-based model checking: they are the properties that can be checked using partial order reduction (POR), an indispensable optimization. There are algorithms to decide whether an LTL formula or Büchi automaton (BA) specifies a stutter-invariant property, and to convert such a BA to a form that is appropriate for on-the-fly POR-based model checking. The interruptible properties play the same role in action-based model checking that stutter-invariant properties play in the state-based case. These are the properties that are invariant under the insertion or deletion of “invisible” actions. We present algorithms to decide whether an LTL formula or BA specifies an interruptible property, and show how a BA can be transformed to an interrupt normal form that can be used in an on-the-fly POR algorithm. We have implemented these algorithms in a new model checker named McRERS, and demonstrate their effectiveness using the RERS 2019 benchmark suite.

@inproceedings{siegel-yan:2020:actions,
  author = "Siegel, Stephen F. and Yan, Yihao",
  editor = "Lahiri, Shuvendu K. and Wang, Chao",
  title = "Action-Based Model Checking: Logic, Automata, and Reduction",
  booktitle = "Computer Aided Verification (CAV 2020)",
  year = "2020",
  publisher = "Springer",
  address = "Cham",
  series = "Lecture Notes in Computer Science",
  volume = "12225",
  pages="77--100",
  doi = "10.1007/978-3-030-53291-8_6"
}