SAT-based counterexample-guided abstraction refinement

We describe new techniques for model checking in the counterexample-guided abstraction-refinement framework. The abstraction phase "hides" the logic of various variables, hence considering them as inputs. This type of abstraction may lead to "spurious" counterexamples, i.e., trac...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on computer-aided design of integrated circuits and systems 2004-07, Vol.23 (7), p.1113-1123
Main Authors: Clarke, E.M., Gupta, A., Strichman, O.
Format: Article
Language:English
Subjects:
Bridge circuits
Chaff
Checkers
Computer aided design
Computer simulation
Concrete
Contracts
Design engineering
Government
Integer linear programming
Iterative methods
Latches
Logic
Machine learning
Manuals
Mathematical analysis
Mathematical models
Solvers
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We describe new techniques for model checking in the counterexample-guided abstraction-refinement framework. The abstraction phase "hides" the logic of various variables, hence considering them as inputs. This type of abstraction may lead to "spurious" counterexamples, i.e., traces that cannot be simulated on the original (concrete) machine. We check whether a counterexample is real or spurious with a satisfiability (SAT) checker. We then use a combination of 0-1 integer linear programming and machine learning techniques for refining the abstraction based on the counterexample. The process is repeated until either a real counterexample is found or the property is verified. We have implemented these techniques on top of the model checker NuSMV and the SAT solver Chaff. Experimental results prove the viability of these new techniques.
ISSN:0278-0070
1937-4151
DOI:10.1109/TCAD.2004.829807