Publications

Combining Partial Order Reduction with Bounded Model Checking

Authors
José Vander Meulen, Charles Pecheur
Tags
, , , ,
Title
Combining Partial Order Reduction with Bounded Model Checking
Authors
José Vander Meulen, Charles Pecheur
FM2018 Δ   0Kb   28 May 2020
Fmics2013 Δ   0Kb   28 May 2020
GandALF2017 Δ   0Kb   28 May 2020
HMI2011 Δ   0Kb   28 May 2020
LVLPrivate Δ   0Kb   28 May 2020
LVLPrivateNews Δ   0Kb   28 May 2020
Main Δ   0Kb   28 May 2020
Members Δ   0Kb   28 May 2020
Publications Δ   4Kb   28 May 2020
Site Δ   0Kb   28 May 2020
Talks Δ   4Kb   28 May 2020
Tools Δ   0Kb   28 May 2020
Type
In Proceedings
Book title
Proceedings of Communicating Process Architectures 2009, Eindhoven, Netherlands
Publisher
IOS Press
Year
2009

Abstract

Model checking is an efficient technique for verifying properties on reactive systems. Partial-order reduction (POR) and symbolic model checking are two common approaches to deal with the state space explosion problem in model checking. Traditionally, symbolic model checking uses BDDs which can suffer from space blow-up. More recently bounded model checking (BMC) using SAT-based procedures has been used as a very successful alternative to BDDs. However, this approach gives poor results when it is applied to models with a lot of asynchronism. This paper presents an algorithm which combines partial order reduction methods and bounded model checking techniques in an original way that allows efficient verification of temporal logic properties (LTL_X) on models featuring asynchronous processes. The encoding to a SAT problem strongly reduces the complexity and non-determinism of each transition step, allowing efficient analysis even with longer execution traces. The starting-point of our work is the Two-Phase algorithm (Namalesu and Gopalakrishnan) which performs partial-order reduction on process-based models. At first, we adapt this algorithm to the bounded model checking method. Then, we describe our approach formally and demonstrate its validity. Finally, we present a prototypal implementation and report encouraging experimental results on a small example.

Tags Tags: , , , ,

BibTeX Record
  @INPROCEEDINGS{lvl-2009-3,
    TITLE = {Combining Partial Order Reduction with Bounded Model Checking},
    AUTHOR = {José {Vander Meulen} and Charles Pecheur},
    YEAR = {2009},
    PUBLISHER = {IOS Press},
    URL = {https://lvl.info.ucl.ac.be/Publications/CombiningPartialOrderReductionWithBoundedModelChecking},
  }