An Analysis of SAT-Based Model Checking Techniques in an Industrial Environment

Nina Amla, Xiaoqun Du, Andreas Kuehlmann, Robert P. Kurshan, Kenneth L. McMillan

Abstract

Model checking is a formal technique for automatically verifying that a finite-state model satisfies a temporal property. In model checking, generally Binary Decision Diagrams (BDDs) are used to efficiently encode the transition relation of the finite-state model. Recently model checking algorithms based on Boolean satisfiability (SAT) procedures have been developed to complement the traditional BDD-based model checking. These algorithms can be broadly classified into three categories: (1) bounded model checking which is useful for finding failures (2) hybrid algorithms that combine SAT and BDD based methods for unbounded model checking, and (3) purely SAT-based unbounded model checking algorithms. The goal of this paper is to provide a uniform and comprehensive basis for evaluating these algorithms. The paper describes eight bounded and unbounded techniques, and analyzes the performance of these algorithms on a large and diverse set of hardware benchmarks.
BibTeX
@inproceedings{amla2005analysis,
  author = {Nina Amla and Xiaoqun Du and Andreas Kuehlmann and Robert P. Kurshan and Kenneth L. McMillan},
  title = {{An Analysis of SAT-Based Model Checking Techniques in an Industrial Environment}},
  booktitle = {CHARME},
  year = {2005},
  doi = {10.1007/11560548\_20},
}

Loading related content...

Figure