A survey of recent advances in SAT-based formal verification

Mukul R. Prasad, Armin Biere, Aarti Gupta

Research output: Contribution to journalReview articlepeer-review

211 Scopus citations

Abstract

Dramatic improvements in SAT solver technology over the last decade and the growing need for more efficient and scalable verification solutions have fueled research in verification methods based on SAT solvers. This paper presents a survey of the latest developments in SAT-based formal verification, including incomplete methods such as bounded model checking and complete methods for model checking. We focus on how the surveyed techniques formulate the verification problem as a SAT problem and how they exploit crucial aspects of a SAT solver, such as application-specific heuristics and conflict-driven learning. Finally, we summarize the noteworthy achievements in this area so far and note the major challenges in making this technology more pervasive in industrial design verification flows.

Original languageEnglish (US)
Pages (from-to)156-173
Number of pages18
JournalInternational Journal on Software Tools for Technology Transfer
Volume7
Issue number2
DOIs
StatePublished - Apr 2005

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems

Keywords

  • ATPG
  • Model checking
  • QBF
  • SAT
  • Verification

Fingerprint

Dive into the research topics of 'A survey of recent advances in SAT-based formal verification'. Together they form a unique fingerprint.

Cite this