Towards Bit-Width-Independent Proofs in SMT Solvers

Aina Niemetz, Mathias Preiner, Andrew Reynolds, Yoni Zohar, Clark W. Barrett, Cesare Tinelli

Introduction

Formal verification of software and hardware often relies on Satisfiability Modulo Theories (SMT) solvers to reason about bit-vector arithmetic. While these solvers are highly efficient for fixed-size bit-vectors (e.g., 32-bit or 64-bit integers), they typically rely on a technique called "bit-blasting." This process converts bit-vector formulas into massive propositional logic circuits, requiring the bit-width to be known a priori. Consequently, standard solvers cannot prove properties that hold for any bit-width $n$, a limitation that hinders the verification of parametric hardware designs, compiler optimizations, and smart contracts. This paper, originally presented at CADE 2019, introduces a method to overcome this "bit-width dependency" by translating parametric bit-vector formulas into a logic that supports reasoning over arbitrary widths.

Methodology: Translation to UFNIA

The authors propose bridging the gap by translating bit-vector problems into the theory of Uninterpreted Functions with Non-linear Integer Arithmetic (UFNIA). This allows solvers to treat bit-widths as symbolic variables rather than fixed constants. The translation involves several key steps:

  1. Integer Mapping: Bit-vectors are modeled as integers within the range $[0, 2^n - 1]$. Standard arithmetic operations, such as addition and multiplication, are mapped to their integer arithmetic counterparts modulo $2^n$.
  2. Axiomatizing Bitwise Operations: Unlike arithmetic, bitwise operations (AND, OR, XOR) do not have direct counterparts in integer arithmetic. The authors represent these as uninterpreted functions (UF) and define their behavior through logical axioms.
Table 1: Bit-vector operators, their SMT-LIB syntax, and their corresponding sorts.
  1. Axiomatization Strategies: The researchers explored different levels of detail for these axioms:
  2. Full: Recursive definitions using induction to define exact bit interactions.
  3. Partial: Hand-crafted algebraic properties (e.g., commutativity: $x \& y = y \& x$).
  4. Combined: A hybrid approach that proved most effective in practice, providing the necessary "hints" for solvers to succeed quickly.
  5. Conditional Inverses: To handle existential quantification (e.g., "does there exist an $x$ such that..."), the authors utilized synthesis techniques to find symbolic solutions valid across all bit-widths.

Evaluation and Results

The approach was evaluated across three real-world benchmark sets using state-of-the-art solvers including CVC4, Z3, and Vampire:

  • Invertibility Conditions: The framework successfully proved 110 out of 160 conditions for bit-vector operation inversion to be bit-width independent.
  • LLVM "Alive" Optimizations: 88 out of 180 peephole optimizations from the LLVM compiler were verified for any bit-width. Failures were often attributed to complex shift operations which are notoriously difficult to axiomatize.
  • SMT Rewrite Rules: The system achieved a 94% success rate in verifying the internal simplification rules used by SMT solvers themselves.

CVC4 emerged as the strongest performer, largely due to its sophisticated techniques for handling non-linear arithmetic and quantifiers.

Conclusion and Future Work

This research brings high-level automation to a domain previously reserved for manual effort in interactive theorem provers. While the translation to UFNIA enables automated bit-width-independent proofs, the target logic is undecidable, which can lead to "unknown" results for deep properties or complex operations like division. Future work aims to integrate this automated pipeline into trusted proof assistants like Coq, combining SMT-level speed with the ironclad security of formal proof verification.

Summary updated

Abstract

Many SMT solvers implement efficient SAT-based procedures for solving fixed-size bit-vector formulas. These approaches, however, cannot be used directly to reason about bit-vectors of symbolic bit-width. To address this shortcoming, we propose a translation from bit-vector formulas with parametric bit-width to formulas in a logic supported by SMT solvers that includes non-linear integer arithmetic, uninterpreted functions, and universal quantification. While this logic is undecidable, this approach can still solve many formulas by capitalizing on advances in SMT solving for non-linear arithmetic and universally quantified formulas. We provide several case studies in which we have applied this approach with promising results, including the bit-width independent verification of invertibility conditions, compiler optimizations, and bit-vector rewrites.
BibTeX
@inproceedings{niemetz2019towards,
  author = {Aina Niemetz and Mathias Preiner and Andrew Reynolds and Yoni Zohar and Clark W. Barrett and Cesare Tinelli},
  title = {{Towards Bit-Width-Independent Proofs in SMT Solvers}},
  booktitle = {CADE},
  year = {2019},
  url = {https://openreview.net/forum?id=fd_uSH2mYZE},
}
Figure