NIL: Learning Nonlinear Interpolants
Authors:
- Mingshuai ChenMCMingshuai Chen
- Jie AnJAJie An
- Bohua ZhanBZBohua Zhan
Preprint
Abstract
Nonlinear interpolants have been shown useful for the verification of programs and hybrid systems in contexts of theorem proving, model checking, abstract interpretation, etc. The underlying synthesis problem, however, is challenging and existing methods have limitations on the form of formulae to be interpolated. We leverage classification techniques with space transformations and kernel tricks as established in the realm of machine learning, and present a counterexample-guided method named NIL for synthesizing polynomial interpolants, thereby yielding a unified framework tackling the interpolation problem for the general quantifier-free theory of nonlinear arithmetic, possibly involving transcendental functions. We prove the soundness of NIL and propose sufficient conditions under which NIL is guaranteed to converge, i.e., the derived sequence of candidate interpolants converges to an actual interpolant, and is complete, namely the algorithm terminates by producing an interpolant if there exists one. The applicability and effectiveness of our technique are demonstrated experimentally on a collection of representative benchmarks from the literature, where in particular, our method suffices to address more interpolation tasks, including those with perturbations in parameters, and in many cases synthesizes simpler interpolants compared with existing approaches.Keywords
All Related Versions
This publication has 29 references indexed in Scilit:
- Sharper and Simpler Nonlinear Interpolants for Program Verification2017
- Interpolant Synthesis for Quadratic Polynomial Inequalities and Combination with EUF2016
- Interpolation and Symbol EliminationLecture Notes in Computer Science, 2009
- Automatically Refining Abstract Interpretations2008
- Quantified Invariant Generation Using an Interpolating Saturation Prover2008
- Efficient Interpolant Generation in Satisfiability Modulo Theories2008
- A Combination Method for Generating InterpolantsLecture Notes in Computer Science, 2005
- Interpolation and SAT-Based Model Checking2003
- Counterexample-Guided Abstraction Refinement2000
- Construction of abstract state graphs with PVS1997