Solving Invariant Generation for Unsolvable Loops

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

TL;DR

This paper introduces a novel technique for automatically generating loop invariants for "unsolvable" loops—those with complex, non-linear, or circular dependencies that traditional methods can't handle. By identifying "defective" variables and synthesizing specific polynomial combinations of them that behave linearly, the authors extend formal verification capabilities to a much broader class of deterministic and probabilistic programs.

What Problem Does This Paper Address?

In formal verification, an invariant is a property that remains true before and after every iteration of a loop. Finding these automatically is the "holy grail" for proving that a program is correct or safe.

For a long time, researchers have focused on "solvable loops." These are loops where the variables can be modeled by linear recurrence equations, allowing us to find "closed-form" solutions (mathematical formulas that tell you the value of a variable at any iteration $n$ without running the loop).

However, many real-world programs are "unsolvable." They contain non-linear updates (like $x \leftarrow x^2$) or mutual dependencies that form cycles in a way that prevents individual variables from having simple closed-form solutions. Until now, automated tools struggled to generate invariants for these loops without relying on rigid templates or manual hints.

Methods

The authors propose a two-step approach implemented in a tool called Polar:

  1. Defective Variable Analysis: They represent the loop as a dependency graph. Edges are labeled "L" for linear dependencies and "N" for non-linear ones. They define defective variables as those involved in (or reachable from) a cycle containing at least one non-linear edge. They prove that a loop is "unsolvable" if and only if it contains at least one such defective variable.
  2. Polynomial Synthesis: While individual defective variables might not have closed-form solutions, certain combinations of them might. The authors set up a "candidate polynomial" with unknown coefficients. They then derive a system of quadratic equations to find coefficients that force this polynomial to satisfy a "well-behaved" (C-finite) recurrence.
  3. Solving the Recurrence: Once a well-behaved polynomial combination is found, they use standard algebraic techniques to find its closed-form solution and eliminate the loop counter to produce a final polynomial invariant.

Datasets

The authors evaluated their approach on a benchmark suite of 15 unsolvable loops:

  • Literature Benchmarks: Three challenging cases from existing research in probabilistic systems and biology (e.g., a model of swarming bees and a non-linear Markov chain).
  • Self-Constructed Benchmarks: 12 new examples designed to push the limits of the tool, featuring high-degree polynomial updates (up to degree 500) and complex circular dependencies.

Key Insights and Ideas

  • Localization of Unsolvability: The "aha moment" is that unsolvability isn't a property of the whole loop, but is "caused" by specific defective variables. By isolating these, the tool can focus its heavy algebraic lifting only where it's needed.
  • Linearity from Non-Linearity: Even if $x$ and $y$ behave wildly on their own due to non-linear updates, a specific combination like $x^2 + y$ might follow a simple linear pattern. The paper provides a systematic way to "hunt" for these magic combinations.
  • Unified Framework: The method works equally well for deterministic programs (where variables have fixed values) and probabilistic programs (where the tool finds invariants for the expected values or moments of variables).

Key Results

  • Full Automation: The tool, Polar, successfully generated invariants for all 15 benchmarks, including those where full automation was previously considered impossible.
  • Scalability: The analysis of defective variables happens in polynomial time. While solving the resulting quadratic systems can be hard, the experiments showed that even for a loop with a degree-500 update (deg-500), the tool found an invariant in about 50 seconds.
  • Complexity Drivers: The results showed that the number of variables isn't the main bottleneck; rather, it's the density of mutual dependencies between variables that increases computation time.

Limitations and Future Work

  • Polynomial Restriction: The current technique is strictly limited to polynomial arithmetic. It cannot handle loops with transcendental functions like $\sin(x)$, $\cos(x)$, or $\log(x)$.
  • Non-Polynomial Invariants: The tool searches for polynomial invariants. If a loop's behavior can only be described by a non-polynomial relation, this method will not find it.
  • Future Directions: The authors suggest extending the work to handle transcendental updates by using power series approximations, effectively treating transcendental variables as "somehow 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},
}

Loading related content...

Figure