Stochastic Local Search for Satisfiability Modulo Theories

Andreas Fröhlich, Armin Biere, Christoph M. Wintersteiger, Youssef HamadiAAAI 2015 · DOI

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.

Comparison of solved instances across different solvers and benchmarks.

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.

Runtime comparison plots for BV-SLS against CCAnr and Z3 (Default) on QF_BV and SAGE2 benchmarks.

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

BibTeX
@inproceedings{frohlich2015stochastic,
  author = {Andreas Fröhlich and Armin Biere and Christoph M. Wintersteiger and Youssef Hamadi},
  title = {{Stochastic Local Search for Satisfiability Modulo Theories}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2015},
  doi = {10.1609/aaai.v29i1.9372},
}
Figure