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.
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:
- If the abstracted problem is unsatisfiable, so is the original problem.
- 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.
- 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:
- 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.
- Synthesized lemmas, generated automatically via abduction (more on this below).
- 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\).
- 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.
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.
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.
- Smart contract verification (benchmarks from Certora and the Ethereum Foundation, encoded over 256-bit bit-vectors). On the older Certora encoding, which uses quantifiers and contains 15,000 assertions per benchmark on average, combining term and assertion abstraction solves 573 of 850 benchmarks, more than five times as many as Bitwuzla without abstraction (111). On the newer Certora encoding, which was already optimized for bit-blasting solvers, term abstraction still improves over Bitwuzla (866 vs. 843 of 1,138 benchmarks). On the Ethereum benchmarks, both solve all instances, but term abstraction is more than 40% faster and requires 60% less memory.
- Synthesized equivalence checks (15,000 benchmarks with bit-widths from 16 to 8,192). Term abstraction solves 14,142 benchmarks, compared to 11,961 for Bitwuzla, and is more than 3× faster with a 5× lower memory usage. On the commonly solved instances, it is 12–90× faster than the other solvers.
- Zero-knowledge proof compilers (translation validation problems over 510-bit bit-vectors). A dedicated finite field solver in cvc5 solves the most benchmarks on the original finite field encoding, but on the bit-vector translation, term abstraction solves more than twice as many benchmarks as Bitwuzla (480 vs. 223), including 36 that the finite field solver cannot solve.
- SMT-LIB (all 155,269 non-incremental benchmarks of the logics Bitwuzla
supports). Term abstraction improves over Bitwuzla in 10 of 24 logics,
6 of them involving floating-point arithmetic. The only significant loss of
13 benchmarks is in
QF_BV, mainly due to two benchmark families that need further investigation.
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%.
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.