Abstract
This paper introduces BV-SLS, a novel Stochastic Local Search (SLS) algorithm designed to solve bit-vector formulas directly at the theory level. Traditional Satisfiability Modulo Theories (SMT) solvers often rely on "bit-blasting," which translates high-level operations into massive propositional logic problems, potentially losing critical structural information. By exploiting word-level structure and employing advanced search heuristics, BV-SLS outperforms existing SAT-based local search solvers and proves highly competitive with state-of-the-art solvers like Z3 on industrial benchmarks.
Introduction
In formal verification and software testing, solving SMT problems involving fixed-size integers (bit-vectors) is a core challenge. The industry standard, bit-blasting, hands a giant web of Boolean gates to a Conflict-Driven Clause Learning (CDCL) SAT solver. While CDCL is excellent at proving unsatisfiability, it can struggle to find solutions for large, complex, but satisfiable formulas. Furthermore, bit-blasting destroys high-level arithmetic relationships (e.g., $x + 1 = y$).
Stochastic Local Search (SLS) offers a heuristic alternative that excels at finding satisfying assignments. This paper proposes a framework to "lift" successful SLS techniques from the SAT domain directly to the high-level SMT representation, preserving word-level information to guide the search more effectively.
Methods
The BV-SLS framework incorporates several key innovations to handle bit-vector theories directly:
- Theory-Level Scoring: Instead of simple clause counting, the algorithm uses a recursive scoring function. For bit-vectors, it employs metrics like Hamming distance for equalities and normalized arithmetic differences for inequalities to quantify how close an assignment is to being satisfied.
- Candidate Selection via Bandit Theory: To balance exploration and exploitation when choosing which variable to flip, the solver uses an Upper Confidence Bound (UCB) heuristic, a technique borrowed from multi-armed bandit problems.
- Extended Neighborhoods: Beyond single-bit flips, BV-SLS introduces "natural" bit-vector moves such as incrementing, decrementing, and bitwise negation. These moves allow the solver to traverse the search space in ways that would require many individual bit-flips in a bit-blasted model.
- Efficiency Optimizations: The solver utilizes a Directed Acyclic Graph (DAG) for formula representation and employs early pruning during score calculation to minimize computational overhead.
Key Results
The authors evaluated BV-SLS against two primary benchmark sets: the standard QF_BV (SMT-LIB) reference set and SAGE2, a collection of 8,017 hard instances from whitebox fuzz testing.
As shown in the results table, BV-SLS significantly outperforms existing SAT-based SLS solvers. On the challenging SAGE2 dataset, the best SAT-SLS solver (PAWS) solved only 143 instances, whereas BV-SLS solved 3,719. While the industrial-strength Z3 solver remains the overall leader, BV-SLS demonstrated a unique ability to solve instances that Z3 could not, suggesting that the two approaches are complementary.
The scatter plots further illustrate the performance characteristics. BV-SLS often finds solutions significantly faster than other local search methods and maintains a competitive profile against Z3's default bit-blasting engine, particularly on instances where word-level structure is prominent.
Discussion and Future Work
BV-SLS demonstrates that keeping bit-vector structure allows solvers to use word-level information to guide search more effectively than bit-blasting. However, as an SLS algorithm, it is inherently incomplete and cannot prove unsatisfiability.
Future research directions include optimizing the move selection bottleneck, extending the framework to other theories like floating-point arithmetic or strings, and developing hybrid solvers that combine the strengths of SLS for finding solutions with the completeness of CDCL for proving unsatisfiability. Such a portfolio approach could offer the best of both worlds for industrial-scale verification tasks.
Summary updated