Solving Invariant Generation for Unsolvable Loops

Daneshvar Amrollahi, Ezio Bartocci, George Kenison, Laura Kovács, Marcel Moosbrugger, Miroslav Stankovic

Abstract

Automatically generating invariants, key to computer-aided analysis of probabilistic and deterministic programs and compiler optimisation, is a challenging open problem. Whilst the problem is in general undecidable, the goal is settled for restricted classes of loops. For the class of solvable loops, introduced by Kapur and Rodríguez-Carbonell in 2004, one can automatically compute invariants from closed-form solutions of recurrence equations that model the loop behaviour. In this paper we establish a technique for invariant synthesis for loops that are not solvable, termed unsolvable loops. Our approach automatically partitions the program variables and identifies the so-called defective variables that characterise unsolvability. We further present a novel technique that automatically synthesises polynomials, in the defective variables, that admit closed-form solutions and thus lead to polynomial loop invariants. Our implementation and experiments demonstrate both the feasibility and applicability of our approach to both deterministic and probabilistic programs.

Introduction

In formal verification, an invariant is a property that remains true before and after every iteration of a loop. Finding these automatically is a fundamental challenge for proving program correctness and safety. Traditional automated methods have largely focused on "solvable loops"—those where variables can be modeled by linear recurrence equations, allowing for "closed-form" solutions (mathematical formulas that determine a variable's value at any iteration $n$ without running the loop).

However, many real-world programs are "unsolvable," containing non-linear updates (e.g., $x \leftarrow x^2$) or complex mutual dependencies that prevent individual variables from having simple closed-form solutions. This paper introduces a novel technique for automatically generating loop invariants for these unsolvable loops by identifying "defective" variables and synthesizing specific polynomial combinations that behave linearly.

Methodology: The Polar Approach

The authors implemented their approach in a tool called Polar, which follows a three-step process:

  1. Defective Variable Analysis: The loop is represented as a dependency graph where edges denote linear (L) or non-linear (N) dependencies. Defective variables are defined as those involved in or reachable from a cycle containing at least one non-linear edge. A loop is classified as "unsolvable" if it contains at least one such variable.
  2. Polynomial Synthesis: While individual defective variables may lack closed-form solutions, certain polynomial combinations of them might. Polar sets up a "candidate polynomial" with unknown coefficients and derives a system of quadratic equations to find coefficients that force the polynomial to satisfy a "well-behaved" (C-finite) recurrence.
  3. Solving the Recurrence: Once a well-behaved polynomial combination is found, standard algebraic techniques are used to find its closed-form solution. By eliminating the loop counter, the tool produces a final polynomial invariant.
Figure 3: Examples of programs handled by Polar. Program (a) demonstrates a closed-form for a variable combination, while Program (b) shows a non-linear loop and its synthesized polynomial invariant.

Key Insights

The core innovation lies in the localization of unsolvability. Unsolvability is often caused by specific defective variables rather than the entire loop structure. By isolating these, the tool can focus its algebraic computation where it is most needed. Furthermore, the paper demonstrates that even if variables $x$ and $y$ behave non-linearly, a specific combination like $x^2 + y$ might follow a simple linear pattern. This unified framework works for both deterministic and probabilistic programs, where it finds invariants for expected values or moments.

Evaluation and Results

The approach was evaluated on a benchmark suite of 15 unsolvable loops, including three challenging cases from literature (e.g., biological models and non-linear Markov chains) and 12 self-constructed examples with high-degree polynomial updates (up to degree 500).

  • Full Automation: Polar successfully generated invariants for all benchmarks, including cases where automation was previously considered impossible.
  • Scalability: Analysis of defective variables occurs in polynomial time. Even for complex loops like deg-500, Polar found an invariant in approximately 50 seconds.
  • Complexity Drivers: Experiments indicated that the density of mutual dependencies, rather than the raw number of variables, is the primary factor in computation time.

Limitations and Future Work

The current technique is restricted to polynomial arithmetic and cannot handle transcendental functions such as $\sin(x)$ or $\log(x)$. Additionally, it specifically searches for polynomial invariants; if a loop's behavior requires a non-polynomial relation, the method will not find it. Future work aims to extend this framework to transcendental updates using power series approximations, effectively treating transcendental variables as "defective" and approximating their behavior.

Summary updated

Abstract

Automatically generating invariants, key to computer-aided analysis of probabilistic and deterministic programs and compiler optimisation, is a challenging open problem. Whilst the problem is in general undecidable, the goal is settled for restricted classes of loops. For the class of solvable loops, introduced by Kapur and Rodr\'iguez-Carbonell in 2004, one can automatically compute invariants from closed-form solutions of recurrence equations that model the loop behaviour. In this paper we establish a technique for invariant synthesis for loops that are not solvable, termed unsolvable loops. Our approach automatically partitions the program variables and identifies the so-called defective variables that characterise unsolvability. We further present a novel technique that automatically synthesises polynomials, in the defective variables, that admit closed-form solutions and thus lead to polynomial loop invariants. Our implementation and experiments demonstrate both the feasibility and applicability of our approach to both deterministic and probabilistic programs.
BibTeX
@inproceedings{amrollahi2022solving,
  author = {Daneshvar Amrollahi and Ezio Bartocci and George Kenison and Laura Kovács and Marcel Moosbrugger and Miroslav Stankovic},
  title = {{Solving Invariant Generation for Unsolvable Loops}},
  booktitle = {SAS},
  year = {2022},
  doi = {10.1007/978-3-031-22308-2\_3},
}
Figure