Scalable Bit-Blasting with Abstractions  
by Aina Niemetz and Mathias Preiner, 24 Jul 2024  

Our CAV 2024 paper Scalable Bit-Blasting with Abstractions, joint work with Centaur alum Yoni Zohar (now at Bar-Ilan University), tackles a long-standing weakness of bit-blasting: it does not scale well with increasing bit-widths, especially in the presence of arithmetic. In this post we explain how abstracting expensive arithmetic operators, and refining these abstractions with carefully chosen lemmas, allows an SMT solver to avoid bit-blasting them altogether in most cases.

Why bit-blasting struggles with large bit-widths

The dominant technique for SMT solvers to reason about fixed-size bit-vectors is bit-blasting: after aggressive simplification, bit-vector constraints are eagerly translated into a propositional formula and handed to a SAT solver. This is surprisingly efficient in practice, since modern SAT solvers can handle formulas with millions of variables. However, the translation can significantly increase the size of the formula, and this increase is the main reason why bit-blasting does not scale well for large bit-widths. This is especially true for arithmetic operators such as multiplication, division, and remainder, whose circuits grow roughly quadratically with the bit-width. In practice, this can already become a problem with bit-widths as low as 32, and it is especially severe for applications that inherently reason about much larger bit-widths, such as smart contract verification, where 256-bit words are the norm.

And-Inverter Graph of a 2-bit multiplier: six AND gates connecting four input bits to two output bits.
2 bits
And-Inverter Graph of an 8-bit multiplier: a dense web of AND gates and wires.
8 bits
And-Inverter Graph of a 16-bit multiplier: a tangle of wires in which individual gates are hard to distinguish.
16 bits
And-Inverter Graph of a 32-bit multiplier: an even denser tangle of gates and wires.
32 bits
And-Inverter Graph (AIG) circuits of multipliers with increasing bit-widths, each scaled to fit its panel. From Aina Niemetz's invited talk Tackling Scalability Issues in Bit-Vector Reasoning at FMCAD 2024.

Abstraction refinement for bit-vectors

Rather than providing an alternative to bit-blasting, our approach aims at making bit-blasting itself scale better, by means of a counterexample-guided abstraction refinement (CEGAR) scheme. We abstract terms over the expensive operators bvmul, bvudiv and bvurem with fresh constants, which over-approximates the original problem and translates to significantly smaller circuits on the bit-level. For example, a 32-bit multiplication \(x \cdot s\) is replaced by a fresh 32-bit constant \(t\).

The abstraction module then interacts with the bit-vector solver in a loop:

  1. If the abstracted problem is unsatisfiable, so is the original problem.
  2. If it is satisfiable, the abstraction module checks whether the model values of all abstracted terms are consistent with the true semantics of their operators. If, for example, the model assigns \(x = 3\), \(s = 6\) and \(t = 1\), the abstraction of \(x \cdot s\) is inconsistent.
  3. For every inconsistent abstraction, the abstraction module adds a refinement lemma that rules out the spurious model, and the loop starts over. If all abstractions are consistent, the original problem is satisfiable.

Conceptually, our term abstractions are uninterpreted functions. However, since our procedure refines every abstraction until it is consistent, fresh bit-vector constants suffice. This avoids the overhead of involving the UF solver and allows our approach to be integrated into any SMT solver that supports bit-vectors, even without support for uninterpreted functions. Note that we do not abstract bit-vector addition: while more expensive to bit-blast than bit-wise operators, it is considerably cheaper than the operators we abstract, and preliminary experiments showed that the trade-off is not worth it.

Four tiers of refinement

The main challenge is finding refinement lemmas that, ideally, allow us to avoid bit-blasting abstracted terms entirely. For each abstracted operator, we define a refinement scheme, a four-tiered set of lemmas that is checked tier-wise, in ascending order:

  1. Hand-crafted lemmas that encode core properties of the operator. For example, the product of two bit-vectors is odd if and only if both operands are odd, and it has at least as many trailing zeros as one of its operands. For a non-zero divisor, the result of an unsigned division is never greater than the dividend. Some of these lemmas are derived from invertibility conditions, which precisely characterize when a bit-vector equation has a solution for one of its operands.
  2. Synthesized lemmas, generated automatically via abduction (more on this below).
  3. Value instantiation lemmas, a limited fallback that rules out a single spurious value. For the example above, we add \((x \approx 3 \wedge s \approx 6) \Rightarrow t \approx 18\).
  4. Bit-blasting, as a last resort, by adding the lemma \(t \approx x \cdot s\).

Since value instantiation lemmas each rule out only one spurious model, we limit their number per abstracted term before resorting to bit-blasting.

Finding good lemmas: scoring and abduction

What makes a good refinement lemma? It should not introduce new terms over abstracted operators, which may lead to non-termination of the procedure or to new expensive abstractions, and it should use as few other expensive operators, such as addition, as possible. Further, a lemma should rule out as many spurious models as possible without being subsumed by the lemmas we already have.

To measure the latter, we define a lemma score. For a lemma over \(x\), \(s\) and \(t\), we enumerate all triplets of values for a small bit-width and count those that satisfy the lemma. At bit-width 4, there are 4,096 triplets, 256 of which are correct, that is, \(t\) is the actual result of applying the operator to \(x\) and \(s\). A lemma that is always true scores 4,096, and a perfect characterization of the operator scores 256. The lower the score, the more incorrect triplets the lemma rules out. This extends naturally to sets of lemmas: our hand-crafted lemmas for multiplication, for example, jointly rule out 88% of the incorrect triplets, and those for division and remainder rule out 71% and 91%, respectively.

Schematic diagram: a large circle containing a smaller red circle, overlapped by four ellipses labeled l1 to l4 that each contain the red circle. The area where all four ellipses intersect is hatched and only slightly larger than the red circle. The lemma scores are listed next to it: l1 2416, l2 2791, l3 1961, l4 2048.
Scores of the four hand-crafted lemmas ℓ1, …, ℓ4 for multiplication at bit-width 4 (schematic). The outer circle represents all 4,096 triplets and the red circle the 256 correct ones. Each ellipse represents the triplets that satisfy a lemma. Together, the lemmas only admit the 704 triplets in the hatched area. From Aina Niemetz's invited talk at FMCAD 2024.

To close the remaining gap, we synthesize additional lemmas via syntax-restricted abduction, as implemented in the SMT solver cvc5. Given a literal \(\varphi\) such as \(x \cdot s \approx t\), an abduct of \(\top\) and \(\neg\varphi\) is a satisfiable formula \(C\) that implies \(\neg\varphi\). Its negation \(\neg C\) is then a lemma for \(\varphi\) that is guaranteed to be non-trivial. A set of grammars restricts the operators that may occur in these lemmas. We synthesize lemmas at bit-width 4 and add a candidate to the scheme only if it improves the score of the current set of lemmas. This yields lemmas that a human would be unlikely to come up with, for example, \(x \not\approx (x \ll (s + t)) - 1\) for multiplication. With the synthesized lemmas, the refinement schemes rule out 94% of the incorrect triplets for multiplication and 96% for division and remainder.

Lemma synthesis happens offline: the resulting lemmas are fixed and independent of the input problem. Since synthesized lemmas are only guaranteed to be correct for the bit-width they were synthesized for, we verified the correctness of our lemmas for all bit-widths up to 256 with four different SMT solvers (Bitwuzla, cvc5, Yices, and Z3), which took 1,112 days of CPU time in total. A few of the synthesized lemmas do not hold for bit-widths 1 or 2, which is irrelevant in practice, since we only abstract terms of bit-width 32 and above.

Integration into Bitwuzla

We implemented our approach in our SMT solver Bitwuzla, which follows the lemmas on demand paradigm with a bit-vector abstraction at its core. This architecture allows a seamless integration of the abstraction module into its abstraction/refinement loop, alongside the other theory solvers. The abstraction module is called after the floating-point solver, since word-blasting floating-point constraints introduces new bit-vector terms to abstract, which allows us to also apply our approach to pure floating-point problems. It is called before the array, uninterpreted function and quantifier solvers, which rely on a consistent bit-vector abstraction.

Flow diagram: the input assertions pass through AM::abstract to the bit-vector solver T_BV::solve, which either returns unsat or passes its model to a chain of checks T_FP::check, AM::check, T_A::check, T_UF::check and T_Q::check. If all checks succeed, the result is sat. Otherwise, the resulting lemmas are fed back to the bit-vector solver.
The lemmas on demand loop of Bitwuzla with the abstraction module (AM, highlighted). The abstraction module abstracts the input assertions before they are passed to the bit-vector solver, and checks the model of the abstraction after the floating-point solver and before the array, uninterpreted function and quantifier solvers. Lemmas produced by these checks refine the abstraction. From Aina Niemetz's invited talk at FMCAD 2024.

In practice, we only abstract terms of bit-width 32 and above, and limit the number of value instantiation lemmas per abstracted term to an eighth of its bit-width, for example, at most four for a 32-bit term. We further implemented assertion abstraction, a known, more coarse-grained abstraction technique where assertions themselves are abstracted and only added incrementally when they are violated by the current model. This is particularly effective on unsatisfiable problems with many assertions where the unsatisfiable core is small.

Results

We evaluated our approach on five benchmark sets against Bitwuzla, cvc5 and Z3 (all using bit-blasting), and a configuration of cvc5 that instead translates bit-vector problems to integer arithmetic (int-blasting), with a time limit of 1200 seconds. Overall, term abstraction outperforms all of these solvers on all benchmark sets, and considerably reduces memory usage.

The synthesized equivalence checks also illustrate how term abstraction scales with increasing bit-widths. The table below additionally compares against alternative approaches that do not (mainly) rely on bit-blasting: the layered approach with lazy bit-blasting in CVC4, MCSAT in Yices2, int-blasting in cvc5, and PolySAT in Z3. All of them degrade considerably with increasing bit-widths, as does plain bit-blasting in Bitwuzla, which solves only 49% of the benchmarks at bit-width 8,192. Term abstraction, on the other hand, still solves 85%.

Table of solved benchmarks per bit-width from 16 to 8,192. From bit-width 16 to 8,192, the share of solved benchmarks drops from 99% to 49% for Bitwuzla, from 97% to 13% for CVC4, from 93% to 33% for Yices2, from 74% to 26% for cvc5, from 46% to 37% for Z3, and from 100% to 66% for their virtual best solver, but only from 99% to 85% for Bitwuzla with term abstraction.
Solved synthesized equivalence checks per bit-width (1,500 benchmarks each), with a time limit of 1,200 seconds and a memory limit of 8 GB. The bottom row gives the share of solved benchmarks at bit-widths 16 and 8,192. VBS is the virtual best solver of all solvers except term abstraction (Bit-Blast+Abstr). Adding term abstraction to the VBS improves it from 66% to 88% at bit-width 8,192. From Aina Niemetz's invited talk at FMCAD 2024.

The abstractions themselves turned out to be highly effective. On the solved benchmarks of all sets, only 37% of the abstracted multiplication terms, 13% of the division terms, and 2% of the remainder terms had to be bit-blasted. Of the solved benchmarks with abstracted terms, 80% were solved without bit-blasting any of them, and solving required a median of only four refinement iterations. The synthesized lemmas pay off, too: without them, term abstraction solves 336 fewer of the synthesized equivalence checks, runs into twice as many memory outs, and is 23% slower on the commonly solved instances while using 61% more memory.

What’s next

Existing techniques that mitigate the cost of bit-blasting large bit-widths are mainly based on under-approximation. Incorporating these techniques into our over-approximation-based framework is an interesting direction for future work.

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