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:
- 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.
- For Equalities: It uses a template-based approach ($c_1t_1 + c_2t_2 ... = 0$) and solves for the coefficients.
- 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.
- 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.
- 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