An Analysis of SAT-Based Model Checking Techniques in an Industrial Environment
Lists
Only you see this
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...