2009 · 63 citations · 7 references
ComputingComputer EngineeringComputer ScienceAlgorithmsDesign AutomationFormal MethodsDeductive VerificationModel CheckingVerificationFormal Hardware VerificationHardware Model CheckingHardware VerificationInterpolation-based VerificationSymbolic Model Checking
SAT-based model checking is the most widely used method for verifying industrial designs against their specification. This is due to its ability to handle designs with thousands of state elements and more. The main drawback of using SAT-based model checking is its orientation towards ¿bug-hunting¿ rather than full verification of a given specification. Previous works demonstrated how Unbounded Model Checking can be achieved using a SAT solver. In this work we present a novel SAT-based approach to full verification. The approach combines BMC with interpolation-sequence in order to imitate BDD-based Symbolic Model Checking. We demonstrate the usefulness of our method by applying it to industrial-size hardware designs from Intel. Our method compares favorably with McMillan's interpolation based model checking algorithm.
7
E. M. Clarke, Orna Grümberg, D. Long · 1996 · 6.9K citations
The temporal logic of programs
Amir Pnueli · 1977 · 5.7K citations
Symbolic model checking: 1020 States and beyond
Jerry R. Burch, E. M. Clarke, Kenneth L. McMillan et al. · Information and Computation · 1992 · 2.7K citations
Model Checking of Safety Properties
Orna Kupferman, Moshe Y. Vardi · Formal Methods in System Design · 2001 · 577 citations
Linear reasoning. A new form of the Herbrand-Gentzen theorem
William Craig · Journal of Symbolic Logic · 1957 · 457 citations