STABLE: A new QF-BV SMT solver for hard verification problems combining Boolean reasoning with computer algebra
Authors:
- 1 March 2011
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 15301591,p. 1-6
Abstract
This paper presents a new SMT solver, STABLE, for formulas of the quantifier-free logic over fixed-sized bit vectors (QF-BV). The heart of STABLE is a computer-algebra-based engine which provides algorithms for simplifying arithmetic problems of an SMT instance prior to bit-blasting. As the primary application domain for STABLE we target an SMT-based property checking flow for System-on-Chip (SoC) designs. When verifying industrial data path modules we frequently encounter custom-designed arithmetic components specified at the logic level of the hardware description language being used. This results in SMT problems where arithmetic parts may include non-arithmetic constraints. STABLE includes a new technique for extracting arithmetic bit-level information for these non-arithmetic constraints. Thus, our algebraic engine can solve subproblems related to the entire arithmetic design component. STABLE was successfully evaluated in comparison with other state-of-the-art SMT solvers on a large collection of SMT formulas describing verification problems of industrial data path designs that include multiplication. In contrast to the other solvers STABLE was able to solve instances with bit-widths of up to 64 bits.Keywords
This publication has 11 references indexed in Scilit:
- New developments in the theory of Gröbner bases and applications to formal verificationJournal of Pure and Applied Algebra, 2009
- An Algebraic Approach for Proving Data Correctness in Arithmetic Data PathsLecture Notes in Computer Science, 2008
- Word-Level Predicate-Abstraction and Refinement Techniques for Verifying RTL VerilogIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2008
- A Lazy and Layered SMT( $\mathcal{BV}$ ) Solver for Hard Industrial Verification Problems2007
- A Decision Procedure for Bit-Vectors and Arrays2007
- Equivalence Verification of Polynomial Datapaths Using Ideal Membership TestingIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2007
- Efficient E-Matching for SMT Solvers2007
- GSTE Is Partitioned Model CheckingLecture Notes in Computer Science, 2004
- BerkMin: A fast and robust SAT-solver2003
- Symbolic model checking using SAT procedures instead of BDDs2003