A Counterexample-guided Approach to Finding Numerical Invariants

ThanhVu Nguyen, Timos Antonopoulos, Andrew Ruef, Michael Hicks

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.

Introduction

Numerical invariants are the mathematical "ground truth" of software—they are essential for proving correctness, ensuring security, and analyzing performance. However, discovering these invariants automatically presents a classic trade-off. Static analysis is sound (guaranteed correct) but often too computationally expensive or too weak to find complex nonlinear relationships. Conversely, dynamic analysis is fast and expressive but unsound, potentially identifying patterns that only hold for specific test cases.

This paper introduces NumInv, a tool designed to bridge this gap. NumInv automatically discovers numerical invariants, including complex nonlinear polynomial relations that often stump traditional static analysis tools. By combining dynamic learning from execution traces with symbolic verification, NumInv finds the strongest possible numerical relationships even in programs lacking formal specifications.

Methodology: The CEGIR Loop

NumInv operates on a Counterexample-Guided Invariant Generation (CEGIR) loop, which functions as an iterative student-teacher relationship between inference and verification.

  1. The Student (Inference): NumInv executes the program to collect traces. It uses algorithms from the DIG (Dynamic Invariant Generator) framework to propose candidate invariants. For equalities, it uses a template-based approach to solve for coefficients. For inequalities, it searches for "octagons" (relations like $\pm x \pm y \leq k$) using a divide-and-conquer strategy to find the tightest possible bounds.
  2. The Teacher (Verification): These candidates are handed to KLEE, a symbolic executor. KLEE attempts to find a path through the code that violates the proposed invariant.
  3. The Feedback: If KLEE identifies a counterexample, that trace is fed back to the inference engine to refine the invariant. This process repeats until KLEE can no longer find counterexamples within a set time limit.
Cohen's division algorithm and sample execution traces used for invariant inference.

A key innovation is the use of KLEE as a practical oracle. While symbolic execution is computationally heavy, the authors found it remarkably effective at refuting incorrect nonlinear polynomials where traditional SMT solvers often time out.

Evaluation and Results

NumInv was evaluated against three primary suites: Non-Linear Arithmetic (NLA) programs, HOLA benchmarks for general verification, and complexity benchmarks used to evaluate execution time predictions.

Experimental results for the NLA benchmark suite, showing successful invariant discovery across diverse programs.

Key Findings

  • Correctness in Complex Arithmetic: NumInv successfully found required invariants for 23 out of 27 NLA programs, including complex algorithms for GCD, LCM, and square roots.
  • Complexity Analysis: By inserting "ghost" counter variables into loops, NumInv discovered closed-form polynomial expressions for program running times. In 18 out of 19 cases, it found expected or more informative complexity bounds than the original benchmark authors.
  • Comparative Performance: On the HOLA benchmarks, NumInv matched or outperformed the state-of-the-art tool PIE in 36 out of 46 cases. Notably, it discovered critical invariants for Cohen’s division algorithm which other tools failed to converge on.

Discussion and Future Work

NumInv employs a strong-to-weak refinement strategy. Unlike static tools that start with a weak guess and try to strengthen it, NumInv starts with the strongest possible guess based on available data and iteratively weakens it as counterexamples prove it wrong.

While highly effective, the approach has limitations. Because KLEE might time out, a "verified" invariant is technically "unrefuted" rather than formally proven. Additionally, current support is limited to integer-based C programs due to KLEE's constraints on floating-point math. Future work includes extending support to other languages like Java and integrating formal verifiers like CPAChecker to provide absolute soundness guarantees upon completion of the 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 = {{A Counterexample-guided Approach to Finding Numerical Invariants}},
  booktitle = {ESEC/SIGSOFT FSE},
  year = {2017},
  url = {https://openreview.net/forum?id=62yqvasED-n},
}
Figure