Towards Bit-Width-Independent Proofs in SMT Solvers

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

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 of non-fixed 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 advancements 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},
}

Loading related content...

Figure