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:
- 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.
- Synthesize: It utilizes a standard Syntax-Guided Synthesis (SyGuS) solver to find a candidate solution $P^b$ that satisfies the finite case.
- 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:
- Syntactic Generalization: Identifying patterns in the finite solution (e.g., generalizing
A[0] > 0 && A[1] > 0to $\forall i. A[i] > 0$). - Synthesis-based Generalization: Using the finite solution as a template to guide a secondary synthesis step for a valid quantified expression.
- 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