A Fresh Look at Best Inductive Loop Invariant Synthesis for Bit-Vector Relations
Open Access
- 27 October 2026
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Software Engineering and Methodology
Abstract
Synthesizing best inductive invariants (BII) is fundamental to program analysis and verification, yet existing approaches face significant efficiency challenges. We introduce a new formulation for the problem through the lens of mathematical optimization over quantified constraints in first-order theories. The formulation offers a constructive and operational perspective on the BII problem and opens new algorithmic avenues. Building on this formulation, we present two new algorithms for bit-vector programs: a strategically guided linear search that exploits the lattice structure and a bitwise greedy approach that resolves bound bits from high to low with a solver-call count linear in bit-width. We evaluate our approach on a comprehensive benchmark suite, demonstrating significant performance improvements over conventional methods based on symbolic abstraction and chaotic iteration. Experimental results demonstrate our approach solves up to 86% more benchmarks than baseline methods, with improved scaling in solver-call count for high bit-widths and improved verification effectiveness when integrated with k-induction.Keywords
This publication has 47 references indexed in Scilit:
- Template Polyhedra with a Twist2017
- Sound Bit-Precise Numerical Domains2017
- Automatic Abstraction for Congruences2010
- Precise Relational Invariants Through Strategy Iteration2007
- Taming the Wrapping of Integer Arithmetic2007
- SMT Techniques for Fast Predicate Abstraction2006
- A Policy Iteration Algorithm for Computing Fixed Points in Static Analysis of Programs2005
- A Note on Karr’s Algorithm2004
- Symbolically Computing Most-Precise Abstract Operations for Shape Analysis2004
- Houdini, an Annotation Assistant for ESC/Java2001