EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

A lazy and modular approach to int-blasting

Max Barth, Matthias Heizmann, Jochen Hoenicke

Acta Informatica · 2026-06 · 63 (2)

DOI: 10.1007/s00236-026-00529-y ↗

Kurz gefasst

Fachartikel in der Zeitschrift Acta Informatica, online erschienen am 10.04.2026. Verfasst von Max Barth und 2 weiteren Autor:innen. Die Arbeit nennt 34 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Ludwig-Maximilians-Universität München.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Bit-vector operations are ubiquitous in programming languages and formal verification, but their complex semantics pose challenges for SMT solvers. Although bit-blasting—translating bit-vectors to Boolean variables—is widely used, it struggles with arithmetic bit-vector operations on large bit-widths (e.g., 64-bit or 256-bit variables) due to exponential blowup. Int-blasting, which maps bit-vectors to integer arithmetic, offers a scalable alternative for arithmetic bit-vector operations, but introduces many modulo operations of which some are redundant. This article presents a modular three-step translation from bit-vector formulas to integer formulas, designed to keep the amount of modulo operations low, while preserving correctness. In the first step, we translate bit-vector operations to integer operations. Thereby, we introduce the two functions $$\texttt {bv2nat}$$ and $$\texttt {nat2bv}_k$$ as explicit operators in the SMT-LIB theory of bit-vectors. Each integer operation is wrapped by $$\texttt {bv2nat}$$ and $$\texttt {nat2bv}_k$$ . Hence, the sort of all bit-vector terms is preserved. Therefore, the first translation step is an equivalence transformation. In the second step, we simplify the formula by replacing the composition $$\texttt {bv2nat} \circ \texttt {nat2bv}_k$$ with a modulo operation. These modulo operations are added lazily, i.e., if the modulo does not change the result of the operation, it is omitted. In our experiments this reduced the average amount of modulo operations by 51%. In the third step, we introduce lemmas to precisely capture the meaning of $$\texttt {bv2nat}$$ and $$\texttt {nat2bv}_k$$ . We prove that these lemmas suffice to solve bit-vector formulas. Furthermore, we illustrate that these lemmas are also sufficient for bit-vector formulas with quantifiers, arrays and uninterpreted functions. We implement our translation in SMTInterpol and evaluate it on 19570 SMT-LIB benchmarks. Results show that our lazy int-blasting solves 15% more tasks than an eager int-blasting, with 35% faster average runtime and 12% lower memory usage.

Förderung

  • Ludwig-Maximilians-Universität München

Zitieren

APA

Barth, M., Heizmann, M., & Hoenicke, J. (2026). A lazy and modular approach to int-blasting. Acta Informatica, 63(2). https://doi.org/10.1007/s00236-026-00529-y

Vancouver

Barth M, Heizmann M, Hoenicke J. A lazy and modular approach to int-blasting. Acta Informatica. 2026;63(2). doi:10.1007/s00236-026-00529-y

BibTeX
@article{Barth2026,
  author = {Barth, Max and Heizmann, Matthias and Hoenicke, Jochen},
  title = {A lazy and modular approach to int-blasting},
  journal = {Acta Informatica},
  year = {2026},
  volume = {63},
  number = {2},
  doi = {10.1007/s00236-026-00529-y}
}
Kostenlos starten →