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:
- 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$.
- 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.
- Axiomatization Strategies: The researchers explored different levels of detail for these axioms:
- Full: Recursive definitions using induction to define exact bit interactions.
- Partial: Hand-crafted algebraic properties (e.g., commutativity: $x \& y = y \& x$).
- Combined: A hybrid approach that proved most effective in practice, providing the necessary "hints" for solvers to succeed quickly.
- 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