Counterexample-guided approach to finding numerical invariants

ThanhVu Nguyen, Timos Antonopoulos, Andrew Ruef, Michael Hicks

This paper presents NumInv, a tool designed to automatically discover numerical invariants—mathematical relationships between variables that always hold true at specific points in a program. By combining dynamic "learning" from execution traces with symbolic "teaching" from a verifier, NumInv can find complex, nonlinear polynomial relations that stump traditional static analysis tools.

TL;DR

NumInv uses a Counterexample-Guided Invariant Generation (CEGIR) loop to automatically discover complex nonlinear program invariants. By pairing dynamic inference with the KLEE symbolic executor, it finds the strongest possible numerical relationships (like $x = qy + r$) even in programs lacking formal specifications.

What Problem Does This Paper Address?

Program invariants are the "ground truth" of code—they are essential for proving correctness, ensuring security, and analyzing performance. However, finding them is a classic "Goldilocks" problem:

  • Static Analysis is sound (guaranteed correct) but often too expensive or too "weak" to find complex nonlinear math.
  • Dynamic Analysis is fast and can find expressive patterns, but it’s unsound—it might find a pattern that only holds for a few specific test cases.

Existing hybrid approaches (CEGIR) often require a "goal" (like a programmer-provided assertion) to guide the search. If you have an undocumented legacy codebase, these tools struggle. Furthermore, many struggle with nonlinear arithmetic (e.g., $x^2 + y^2 = z$). NumInv aims to bridge this gap by finding the strongest possible invariants automatically, without needing a predefined goal.

Methods

NumInv operates on a CEGIR (Counterexample-Guided Invariant Generation) loop, which functions like a student-teacher relationship:

  1. The Student (Inference): NumInv runs the program to collect execution traces. It uses algorithms from the DIG (Dynamic Invariant Generator) framework to propose candidate invariants.
  2. For Equalities: It uses a template-based approach ($c_1t_1 + c_2t_2 ... = 0$) and solves for the coefficients.
  3. For Inequalities: It looks for "octagons" (relations like $\pm x \pm y \leq k$) using a smart divide-and-conquer search to find the tightest possible bounds.
  4. The Teacher (Verification): It hands these candidates to KLEE, a symbolic executor. KLEE tries to find a path through the code that breaks the proposed invariant.
  5. The Feedback: If KLEE finds a "counterexample" (an input that breaks the rule), that trace is fed back to the "Student," who refines the invariant. This repeats until KLEE can no longer find any counterexamples within a time limit.

A key innovation is using KLEE as the verifier. While symbolic execution can be computationally heavy, the authors found it surprisingly effective at refuting incorrect nonlinear polynomials where traditional SMT solvers often time out.

Datasets

The authors evaluated NumInv against three primary suites:

  • NLA (Non-Linear Arithmetic): 27 programs involving complex math like GCD, LCM, and square root algorithms.
  • HOLA Benchmarks: 46 programs commonly used to test general program verification tools.
  • Complexity Benchmarks: 19 programs from academic literature (e.g., Microsoft’s SPEED project) used to evaluate how well tools can predict a program's execution time.

Key Insights and Ideas

  • Strong-to-Weak Refinement: Unlike many static tools that start with a "weak" guess and try to strengthen it, NumInv starts with the "strongest" possible guess (based on limited data) and iteratively weakens it as counterexamples prove it wrong.
  • KLEE as a Practical Oracle: The authors demonstrate that while symbolic execution is technically "incomplete" (it might time out), it is a powerful practical tool for finding bugs in candidate invariants, especially for nonlinear arithmetic.
  • Ghost Variables for Complexity: By inserting a "ghost" counter variable into loops, NumInv can discover closed-form polynomial expressions for a program's running time. In some cases, it found more precise bounds than the researchers who originally published the benchmark programs.

Key Results

  • Correctness: NumInv successfully found the required invariants for 23 out of 27 NLA programs.
  • Complexity: It discovered expected or more informative complexity bounds for 18 out of 19 programs. For example, in a triple-nested loop, it found a precise disjunctive bound that captured different behaviors based on input sizes.
  • Comparison: On the HOLA benchmarks, NumInv matched or outperformed the state-of-the-art tool PIE in 36 out of 46 cases.
  • Discovery: Unlike its competitors, NumInv was able to find the critical invariants for integer division (Cohen’s algorithm) which other tools like ICE and PIE failed to converge on.

Limitations and Future Work

  • Soundness vs. Practicality: Because KLEE might time out, a "verified" invariant is technically only "unrefuted." While highly likely to be correct, it isn't a formal mathematical proof in the strictest sense.
  • Floating Point Support: KLEE’s support for floating-point math is limited, meaning NumInv is currently restricted to integer-based programs.
  • Language Dependency: The current implementation is specific to C code.
  • Future Directions: The authors suggest extending NumInv to support more languages (like Java via JPF) and integrating "true" verifiers (like CPAChecker) to provide absolute soundness when KLEE finishes its search.

Summary updated

Abstract

Numerical invariants, e.g., relationships among numerical variables in a program, represent a useful class of properties to analyze programs. General polynomial invariants represent more complex numerical relations, but they are often required in many scientific and engineering applications. We present NumInv, a tool that implements a counterexample-guided invariant generation (CEGIR) technique to automatically discover numerical invariants, which are polynomial equality and inequality relations among numerical variables. This CEGIR technique infers candidate invariants from program traces and then checks them against the program source code using the KLEE test-input generation tool. If the invariants are incorrect KLEE returns counterexample traces, which help the dynamic inference obtain better results. Existing CEGIR approaches often require sound invariants, however NumInv sacrifices soundness and produces results that KLEE cannot refute within certain time bounds. This design and the use of KLEE as a verifier allow NumInv to discover useful and important numerical invariants for many challenging programs. Preliminary results show that NumInv generates required invariants for understanding and verifying correctness of programs involving complex arithmetic. We also show that NumInv discovers polynomial invariants that capture precise complexity bounds of programs used to benchmark existing static complexity analysis techniques. Finally, we show that NumInv performs competitively comparing to state of the art numerical invariant analysis tools.
BibTeX
@inproceedings{nguyen2017counterexample,
  author = {ThanhVu Nguyen and Timos Antonopoulos and Andrew Ruef and Michael Hicks},
  title = {{Counterexample-guided approach to finding numerical invariants}},
  booktitle = {ESEC/SIGSOFT FSE},
  year = {2017},
  url = {https://openreview.net/forum?id=62yqvasED-n},
}

Loading related content...

Figure