Lemmas for Satisfiability Modulo Transcendental Functions via Incremental Linearization

Ahmed Irfan, Alessandro Cimatti, Alberto Griggio, Marco Roveri, Roberto SebastianiSC-square@SIAM AG 2019 · OpenReview

Abstract

Satisfiability Modulo Theories (SMT) solvers are essential for formal verification, yet they often struggle with nonlinear real arithmetic involving transcendental functions like $e^x$ and $\sin(x)$. This paper provides a comprehensive framework for implementing incremental linearization, a technique that approximates these functions using piecewise-linear constraints. By detailing the mathematical recipes for generating sound linear lemmas via Taylor series, tangents, and secants, the authors bridge the gap between high-level algorithmic theory and practical solver implementation.

Introduction

While SMT solvers are highly effective for linear arithmetic, transcendental functions pose a significant challenge because they often result in irrational values that cannot be represented exactly. Incremental linearization addresses this by iteratively refining linear approximations of nonlinear functions. However, previous literature often described this process at an abstract level, leaving implementers without specific guidance on how to generate sound lemmas—linear inequalities that bound the function without accidentally excluding valid solutions. This work serves as a "missing manual," providing the formal proofs and algorithms necessary for robust implementation.

Methodology: The Abstraction-Refinement Loop

The core of the approach is an abstraction-refinement loop. The solver begins by treating nonlinear functions as "uninterpreted functions," obeying only basic functional consistency (e.g., if $x = y$, then $f(x) = f(y)$). When the solver finds a "spurious solution"—a result that satisfies the linear abstraction but violates the actual transcendental function—it generates refinement lemmas to prune the search space.

Lemma Generation

To refine the abstraction, the solver generates linear inequalities that bound the function. This process involves several mathematical tools:

  1. Taylor Series: Used to establish polynomial upper ($P_u$) and lower ($P_l$) bounds for the function at specific points.
  2. Tangent Lines: Employed when the function's concavity allows a single line to remain entirely on one side of the function curve.
  3. Secant Lines: Used to "box in" the function between two points, providing bounds on the opposite side of the tangent.
Figure 1: Visualization of the linearization process. The transcendental function $tf(x)$ is bounded by Taylor polynomials $P_l, P_u$, a tangent line $T(x)$, and secant lines $S_l, S_u$.

For transcendental constants like $\pi$, the authors utilize Machin’s formula to generate increasingly precise rational bounds as the search progresses, ensuring the solver remains sound even when dealing with irrational limits.

Key Insights and Implementation Challenges

The "Proxy" Tangent

A significant hurdle in implementation is that the value of a transcendental function at a rational point is typically irrational. To maintain a purely rational linear solver, the authors do not draw tangents directly to the function. Instead, they draw a tangent to a Taylor polynomial that has already been proven to bound the function. This "proxy" tangent remains sound while staying within the domain of rational arithmetic.

Concavity and Validity Intervals

The choice between tangent and secant lemmas depends on the function's second derivative (concavity). For example, because $exp(x)$ is always concave up, tangents consistently provide lower bounds while secants provide upper bounds. A critical contribution of this paper is the proof of "validity intervals." For $exp(x)$, the authors prove that tangent-based lemmas are valid across the entire real line ($[-\infty, \infty]$), providing massive pruning power. Trigonometric functions like $\sin(x)$ are more complex due to periodicity; the authors handle these by focusing on a base period $[-\pi, \pi]$ and using rational approximations of $\pi$ to determine local concavity.

Results and Formal Framework

The paper formalizes these techniques into a set of proven lemmas and algorithms:

  • Lemma 2: Establishes the global validity ($[-\infty, \infty]$) for tangent refinements of the exponential function.
  • Lemma 9: Defines the specific validity intervals for $\sin(x)$ based on the input point's position within the base period.
  • Algorithm 3: Provides concrete pseudocode for the block-spurious-nta-term function, which serves as the engine for the refinement process in the solver.

Conclusion and Future Work

This work provides the necessary mathematical foundations to make incremental linearization a practical reality for SMT solvers. While the current framework focuses on $exp$ and $sin$, the underlying methodology is extensible. Future work includes deriving specific validity interval proofs for other functions like $\log(x)$ and $\tan(x)$, as well as developing more sophisticated heuristics for managing the precision parameter to balance solver speed with accuracy.

Summary updated

BibTeX
@inproceedings{irfan2019lemmas,
  author = {Ahmed Irfan and Alessandro Cimatti and Alberto Griggio and Marco Roveri and Roberto Sebastiani},
  title = {{Lemmas for Satisfiability Modulo Transcendental Functions via Incremental Linearization}},
  booktitle = {SC-square@SIAM AG},
  year = {2019},
  url = {https://openreview.net/forum?id=ggeKgrOp6jM},
}
Figure