Verifying Programs with Non-Linear Arithmetic

99 concepts82 papers1 proposal

In formal verification, linear arithmetic is a safe haven. When program constraints only involve addition and multiplication by constants (e.g., $3x + 2y \le 5$), the state space can be represented as convex polytopes. Tools can efficiently navigate these spaces using well-established algorithms like Simplex or polyhedral abstract domains.

However, real-world software frequently breaks these linear boundaries. Whether calculating a geometric trajectory, managing a financial portfolio, or indexing multi-dimensional arrays, code regularly introduces non-linear arithmetic (NRA)—operations involving the multiplication of variables, higher-degree polynomials, or transcendental functions.

When arithmetic becomes non-linear, the underlying mathematics shifts from linear programming to algebraic geometry. The state space curves, splits, and becomes fundamentally harder to reason about. Complete decision procedures for non-linear real arithmetic suffer from double-exponential time complexity, causing standard automated theorem provers to hang or time out. To verify these systems, researchers have developed strategies that bridge the gap between logical search and algebraic refinement.

The Computational Wall of Non-Linearity

To understand why non-linear verification is difficult, consider how a standard Satisfiability Modulo Theories (SMT) solver processes a program. As noted in early work on CVC Lite: A New Implementation of the Cooperating Validity Checker Category B by Clark Barrett et al., traditional decision procedures rely heavily on normal form transformations. While these transformations easily flatten linear equations, they fail to capture general non-linear reasoning because variable multiplication creates complex dependencies across constraints.

This problem compounds dramatically when analyzing loops. To prove a loop safe, a verifier typically needs to discover a loop invariant—a mathematical property that holds true before and after every iteration. When a loop contains non-linear updates or mutual dependencies, it lacks a predictable linear recurrence relation, making it impossible to compute a closed-form solution using standard heuristics (Daneshvar Amrollahi et al. in (Un)Solvable loop analysis).

Furthermore, as highlighted in Sound and Complete Witnesses for Template-Based Verification of LTL Properties on Polynomial Programs, proving properties over non-linear systems often requires solving formulas with quantifier alternation (e.g., proving that for all inputs, there exists a set of coefficients satisfying a safety boundary). This structure quickly renders automated verification intractable for standard linear solvers.

Synthesizing Polynomial Invariants

When linear boundaries fail to capture a program's behavior, verifiers must synthesize polynomial invariants (e.g., $x^2 + y \le z$). Because searching the infinite space of polynomial coefficients is computationally intensive, researchers leverage numerical optimization and machine learning to find candidate boundaries.

Sums-of-Squares (SOS) Optimization

One powerful insight is to transform the logical search for an invariant into a continuous optimization problem. Assalé Adjé et al. pioneer this in Property-based Polynomial Invariant Generation using Sums-of-Squares Optimization.

The core intuition relies on a mathematical fact: if a polynomial can be written as a sum of squared terms (e.g., $f(x) = (g(x))^2 + (h(x))^2$), it is guaranteed to be non-negative for all real values. By using Sums-of-Squares (SOS) relaxation, the authors convert the hard algebraic problem of proving polynomial non-negativity into a semidefinite programming (SDP) problem. Highly optimized numerical solvers can then compute the coefficients of the polynomial invariant in polynomial time, providing a scalable way to prove safety properties for non-linear software.

Counterexample-Guided Learning

An alternative approach balances dynamic execution with symbolic verification. In A Counterexample-guided Approach to Finding Numerical Invariants, ThanhVu Nguyen et al. introduce a "learner-teacher" framework.

  +-------------------+                   +---------------------+
  |      Learner      |--Candidate Invariant->|       Teacher       |
  | (Execution Traces)|                   | (Symbolic Executor) |
  +-------------------+                   +---------------------+
            ^                                        |
            |                                Counterexample
            +----------------------------------------+

The learner executes the program to gather concrete variable traces and fits a polynomial curve to those points. It then passes this candidate invariant to a teacher (a symbolic execution engine). If the invariant is incorrect, the teacher generates a counterexample—a real program state where the invariant fails. The learner uses this new data point to refine the polynomial curve. By using symbolic execution to refute incorrect candidates, the authors bypass the timeouts that occur when forcing an SMT solver to prove a complex polynomial from scratch.

This search space can also be navigated using deep learning. Xujie Si et al. demonstrate in Code2Inv: A Deep Learning Framework for Program Verification that combining Graph Neural Networks (GNNs) with reinforcement learning allows a system to learn structural heuristics directly from program syntax, successfully generating non-linear constraints without human-engineered rules.

Bypassing Invariants via Global Induction

If finding a local loop invariant is too difficult, can we prove the program correct by looking at it globally?

Supratik Chakraborty et al. introduce this paradigm shift with Full-Program Induction in Full-Program Induction: Verifying Array Programs sans Loop Invariants. Traditional verification inducts over loop iterations ($k \to k+1$). If an array index depends on a non-linear expression like a cubic polynomial, tracking the index modification at each step causes solvers to fail.

Instead, the authors induct over a global program parameter, such as the total array size $N$. By proving that the property holds for a base size and that a program of size $N$ preserves the property for size $N+1$, Full-Program Induction bypasses the need to track complex intermediate loop states entirely, resolving intensive non-linear benchmarks in seconds.

A complementary approach is loop acceleration, which aims to compute symbolic recurrence equations to "jump" directly to a target iteration. While Daniel Kroening et al. note in Counterexamples with Loops for Predicate Abstraction that symbolic analysis struggles with non-linear recurrences like factorials, recent advances show that focusing on polynomial expressions rather than individual variables allows verifiers to isolate and accelerate non-linear cycles (Chenglin Wang et al. in On Polynomial Expressions with C-Finite Recurrences in Loops with Nested Nondeterministic Branches).

Bridging SMT and Symbolic Computation

Ultimately, any high-level verification strategy must lower its constraints to a foundational solver. Historically, two communities tackled this from opposite sides: the Satisfiability Checking (SAT/SMT) community focused on efficient logical search over boolean combinations of linear constraints, while the Symbolic Computation community focused on deep algebraic algorithms (like Cylindrical Algebraic Decomposition) for pure non-linear equations.

The SC² initiative, detailed by Erika Ábrahám et al. in SC-square: when Satisfiability Checking and Symbolic Computation join forces, formalizes the integration of these two worlds. Instead of treating the algebraic solver as an isolated back-end, modern architectures embed algebraic reasoning directly into the SMT conflict-driven clause learning (CDCL) loop.

To scale this integration practically, Ahmed Irfan proposes an incremental reduction strategy in Invariant Checking of NRA Transition Systems via Incremental Reduction to LRA with EUF. Rather than passing full non-linear real arithmetic formulas to an expensive solver, the system abstracts non-linear terms using Linear Real Arithmetic (LRA) and the Equality Modulo Uninterpreted Functions (EUF). For example, a multiplication $x \times y$ is initially treated as an uninterpreted function $f(x,y)$. The solver only introduces precise non-linear algebraic constraints incrementally when an abstract counterexample proves to be spurious.

These combined insights have culminated in industrial-strength tools like cvc5, developed by Clark Barrett et al. As outlined in cvc5: A Versatile and Industrial-Strength SMT Solver, native procedures for non-linear arithmetic allow modern solvers to handle complex variable dependencies and bit-vector operations that once formed an impassable bottleneck in formal software engineering.

Key Foundational Work

Counterexamples with Loops for Predicate Abstraction (2006) — contributed 2 concept elements to this direction.
CVC Lite: A New Implementation of the Cooperating Validity Checker Category B (2004) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_non_linear_arithmetic_verification_966631e1,
  title = {non-linear arithmetic verification},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-linear-arithmetic-verification/rdr_966631e19b2146b0ab84ce49ddb70f2b},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_non_linear_arithmetic_verification_966631e1_v1,
  title = {non-linear arithmetic verification},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-linear-arithmetic-verification/rdr_966631e19b2146b0ab84ce49ddb70f2b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake