SynRG: Syntax Guided Synthesis of Invariants with Alternating Quantifiers

Elizabeth Polgreen, Sanjit A. SeshiaarXiv 2020 · arXiv

Abstract

Program synthesis for unbounded data structures like arrays often requires reasoning with complex, alternating quantifiers. Existing solvers frequently fail when faced with these alternations. We present SynRG, a framework that addresses this by restricting infinite-domain problems to finite ones, solving them using standard tools, and generalizing the results back to the infinite domain. SynRG demonstrates significant improvements over state-of-the-art solvers, particularly on benchmarks involving alternating quantifiers.

Introduction

Program synthesis—the automated generation of code that meets a logical specification—often struggles with "unbounded" data. In real-world software, arrays can be arbitrarily large. To reason about them, we need quantifiers (e.g., "for all elements $i$ in array $A$...") and often quantifier alternations (e.g., "for every element in $A$, there exists an equal element in $B$").

Most current synthesis solvers, such as CVC4 or Z3, are designed for quantifier-free logic or simple universal quantifiers and often fail when faced with alternations. This creates a significant gap when automatically generating loop invariants for complex code or filling in "holes" in program sketches for standard libraries like Java’s StringUtils.

Methodology: The SynRG Framework

SynRG introduces a "Restriction and Generalization" loop to bridge the gap between finite-domain solving and infinite-domain specifications. The process is divided into four primary stages:

The SynRG algorithm workflow: Restrict, Synthesize, Generalize, and Verify.
  1. Restrict: The algorithm takes a specification $\sigma$ over an infinite domain and restricts it to a finite domain of size $b$ (e.g., considering only the first two elements of an array). This transforms complex quantified formulas into simpler, quantifier-free ones.
  2. Synthesize: It utilizes a standard Syntax-Guided Synthesis (SyGuS) solver to find a candidate solution $P^b$ that satisfies the finite case.
  3. Generalize: This core innovation attempts to lift the finite solution $P^b$ back into a quantified expression $P^*$ for the infinite domain. This is achieved through:
  4. Syntactic Generalization: Identifying patterns in the finite solution (e.g., generalizing A[0] > 0 && A[1] > 0 to $\forall i. A[i] > 0$).
  5. Synthesis-based Generalization: Using the finite solution as a template to guide a secondary synthesis step for a valid quantified expression.
  6. Verify: An SMT solver checks if $P^*$ satisfies the original specification. If verification fails, the bound $b$ is increased, and the loop repeats.

Experimental Evaluation

The authors evaluated SynRG against a suite of 65 benchmarks, including 24 from the Software Verification Competition (SV-COMP), 19 crafted problems testing nested quantification, and 22 program sketching tasks (19 from Java's StringUtils).

SynRG significantly outperformed state-of-the-art solvers, particularly in handling alternating quantifiers ($\forall \exists$), which other solvers could not achieve on these benchmarks.

Solver Total Solved (out of 65)
SynRG 38
CVC4 14
QUIC3 9
Z3 1

Discussion and Conclusion

SynRG leverages the "Small Model Property," the idea that many array properties can be understood through a small number of elements. By treating finite solutions as "hints" or templates, SynRG effectively guides the synthesis of complex invariants. While the approach is heuristic and dependent on the efficiency of underlying solvers, it represents a major step forward in synthesizing expressions with alternating quantifiers. Future work includes exploring more sophisticated generalization heuristics and extending the framework to other theories exhibiting small model properties.

Summary updated

Abstract

Program synthesis is the task of automatically generating expressions that satisfy a given specification. Program synthesis techniques have been used to automate the generation of loop invariants in code, synthesize function summaries, and to assist programmers via program sketching. Syntax-guided synthesis has been a successful paradigm in this area, however, one area where the state-of-the-art solvers fall-down is reasoning about potentially unbounded data structures such as arrays where both specifications and solutions may require quantifiers and quantifier alternations. We present SynRG, a synthesis algorithm based on restricting the synthesis problem to generate candidate solutions with quantification over a finite domain, and then generalizing these candidate solutions to the unrestricted domain of the original specification. We report experiments on invariant synthesis benchmarks and on program sketching benchmarks taken from the Java StringUtils class and show that our technique can synthesize expressions out of reach of all existing solvers.
BibTeX
@misc{polgreen2020synrg,
  author = {Elizabeth Polgreen and Sanjit A. Seshia},
  title = {{SynRG: Syntax Guided Synthesis of Invariants with Alternating Quantifiers}},
  year = {2020},
  eprint = {2007.10519},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2007.10519},
}

Loading related content...

Figure