Bitwuzla  
by Aina Niemetz and Mathias Preiner, 17 Jul 2023  

Our paper Bitwuzla received a Distinguished Paper Award at CAV 2023 in Paris. It accompanies the first official release of Bitwuzla, our SMT solver for the quantified and quantifier-free theories of fixed-size bit-vectors, arrays, floating-point arithmetic, and uninterpreted functions. In this post we explain why we wrote a new solver from scratch, how it is organized, and how it performs.

From Boolector to Bitwuzla

Bit-precise reasoning, that is, reasoning about fixed-size bit-vectors, often in combination with arrays, uninterpreted functions and floating-point arithmetic, is at the heart of many applications in hardware and software verification, symbolic execution, and model checking. For years, our previous solver Boolector largely dominated the quantifier-free divisions with bit-vectors and arrays in the annual SMT competition (SMT-COMP). Boolector was originally published by Robert Brummayer and Armin Biere in 2009, and since 2012 we have been its main developers, extending it with support for uninterpreted functions and lambda terms, local search, and quantified bit-vector formulas.

Boolector, however, has several limitations that make it increasingly hard to maintain and extend. Its code base consists of largely monolithic C code with a rigid architecture built around a tight integration of bit-vectors and arrays. Users have to manage memory and reference counts manually, and terms and sorts are tied to a single solver instance. Further, all preprocessing techniques are destructive, which prevents incremental preprocessing, and incremental solving with quantifiers is not supported.

In 2018, we forked Boolector and entered an extended version of this fork in SMT-COMP 2020 under the name Bitwuzla, with support for floating-point arithmetic, ternary propagation-based local search, and unsat cores, and, since 2022, quantifiers. Architectural and structural limitations inherited from Boolector, however, remained. We thus decided to discard the existing code base and rewrite Bitwuzla from scratch in C++. Rather than reimplementing Boolector, we carefully dissected and reevaluated each of its parts to guide the design of the new solver. Its name, pronounced bitvootslah, is derived from an Austrian dialect expression that can be translated as someone who tinkers with bits.

Architecture

Bitwuzla consists of two main components: the Node Manager and the Solving Context.

Bitwuzla's system architecture: a C++ API with C and Python APIs and a parser and command line interface on top, wrapping the Node Manager (with type and node databases) and the Solving Context (with rewriter, preprocessor, and a solver engine that connects the bit-vector solver to the array, floating-point, function, and quantifier solvers via a communication layer).
Bitwuzla's system architecture. From Figure 1 of the paper.

The Node Manager constructs and maintains terms and sorts. Terms are represented as immutable, reference-counted nodes in a directed acyclic graph, and hash-consing maximizes the sharing of subterms. Nodes and types are stored globally (thread-local), which allows them to be shared between arbitrarily many solver instances within one thread. This is one of the key differences from Boolector, where terms and sorts are reference-counted manually and belong to a single solver instance.

A Solving Context is the internal equivalent of a solver instance. It determines the satisfiability of the current set of assertions, provides models and unsat cores, and supports incremental solving via push and pop and solving under assumptions. A Solving Context consists of three main components:

Every component except the rewriter depends on the current set of assertions. To take full advantage of incremental solving, Bitwuzla saves and restores the internal solver state on push and pop by means of backtrackable data structures, similar to the context-dependent data structures in cvc5. This allows the solver to reuse work from previous satisfiability checks and enables incremental preprocessing.

Bitwuzla provides a comprehensive C++ API as its main interface, with C and Python APIs built on top, and a command line interface that supports SMT-LIBv2 and BTOR2 as input languages.

Lemmas on demand with a bit-vector abstraction

Unlike SMT solvers such as cvc5 and Z3, which are based on the CDCL(T) framework, the solver engine implements the lazy, abstraction/refinement-based paradigm lemmas on demand. However, rather than using a propositional abstraction of the input formula, Bitwuzla works with a bit-vector abstraction, similar to Boolector. All propositional and bit-vector terms are handled by the bit-vector solver. Theory atoms that do not belong to the theory of bit-vectors are abstracted as Boolean constants, and bit-vector terms with operators from other theories are abstracted as bit-vector constants. For example, a read from an array with bit-vector elements is abstracted as a fresh bit-vector constant, and an equality between two arrays as a fresh Boolean constant.

If the bit-vector abstraction is satisfiable, the floating-point, array, uninterpreted function, and quantifier solvers check the resulting satisfying assignment for consistency with their theory axioms. If a theory solver finds an inconsistency, it sends a lemma that refines the abstraction and rules it out. This loop is repeated until either the abstraction is unsatisfiable, or none of the theory solvers report an inconsistency.

The theory solvers implement the following techniques:

Results

We evaluated Bitwuzla on all non-incremental and incremental benchmarks in SMT-LIB of all logics it supports, against Boolector, the SMT-COMP 2022 version of Bitwuzla (SC22, the Boolector-based fork), and the SMT-COMP 2022 versions of cvc5 and Z3, using a time limit of 1200 seconds.

What’s next

The paper outlines several directions for future work. We plan to explore more interleaved combinations of local search and bit-blasting, possibly sharing information between the two procedures. For arrays, we plan to add dedicated operators for extended array operations such as memset and memcpy, as well as support for extensional constant arrays (which we have since added, see our post on the CAV 2026 paper). We further plan to support the upcoming SMT-LIB version 3 standard, once it is finalized.

Bitwuzla is available on GitHub under the MIT license, and its documentation is available at bitwuzla.github.io. It has been extensively tested for robustness and correctness with our API fuzzer Murxla, which is an integral part of its development workflow.

For all the details, see the paper. The artifact is available on Zenodo.