SyGuS-Comp 2017: Results and Analysis.

Rajeev Alur, Dana Fisman, Rishabh Singh, Armando Solar-Lezama

Abstract: Syntax-Guided Synthesis (SyGuS) is the computational problem of finding an implementation f that meets both a semantic constraint given by a logical formula phi in a background theory T, and a syntactic constraint given by a grammar G, which specifies the allowed set of candidate implementations. Such a synthesis problem can be formally defined in SyGuS-IF, a language that is built on top of SMT-LIB. The Syntax-Guided Synthesis Competition (SyGuS-Comp) is an effort to facilitate, bring together and accelerate research and development of efficient solvers for SyGuS by providing a platform for evaluating different synthesis techniques on a comprehensive set of benchmarks. In this year's competition six new solvers competed on over 1500 benchmarks. This paper presents and analyses the results of SyGuS-Comp'17.

Introduction

Program synthesis aims to automatically generate executable code from high-level specifications. Syntax-Guided Synthesis (SyGuS) introduces a syntactic constraint: the generated code must follow a specific grammar $G$ in addition to satisfying a logical formula $\phi$. This constraint prevents trivial or overly complex solutions but significantly expands the search space. SyGuS-Comp 2017 evaluated six solvers across five specialized tracks, highlighting a shift toward hybrid approaches that combine traditional logic with statistical models and "divide-and-conquer" strategies to navigate astronomical search spaces.

Solver Methodologies

The 2017 competition featured diverse algorithmic philosophies among the six competing solvers:

  • Divide and Conquer (EUSOLVER2017): This approach finds expressions for subsets of the input space and unifies them into a complete solution using decision trees.
  • SMT-Based Synthesis (CVC42017): Built within an SMT solver, it extracts solutions directly from "proofs of unsatisfiability." If the solver can prove no counter-example exists, it can often reconstruct the function itself.
  • Statistical Acceleration (EUPHONY): This solver uses a Probabilistic Higher-Order Grammar (PHOG)—essentially a language model for code—to prioritize the search for likely code snippets based on patterns in previous benchmarks.
  • Specialized Solvers: Tools like LOOPINVGEN (for loop invariants) and E3SOLVER (for bitvector programming-by-example) utilized domain-specific optimizations to outperform general-purpose tools in their respective niches.

Benchmark Datasets

The competition utilized a massive library of over 1,500 benchmarks, including 250 new tasks designed to push the boundaries of current synthesis techniques:

  • Program Repair: 18 benchmarks derived from real-world Java bugs.
  • Crypto Circuits: 214 benchmarks focused on synthesizing constant-time circuits to prevent side-channel timing attacks.
  • Instruction Selection: 28 tasks aimed at synthesizing complex x86-style instructions from basic operations.
  • Invariant Generation: 7 new tasks for generating loop invariants in linear arithmetic.

Analysis of Performance

The results underscore the effectiveness of both generalization and specialization. EUSOLVER2017 emerged as the overall winner, solving the highest total number of benchmarks across all tracks.

Figure 2: Number of benchmarks solved per solver across different tracks.

Statistical methods proved powerful; EUPHONY demonstrated that learning from previous benchmarks significantly accelerates the search process. However, specialization remains a dominant strategy in specific domains. For instance, E3SOLVER achieved a 100% success rate in the Programming-by-Example (PBE) Bitvector track, proving that specialized unification techniques are highly effective for example-based synthesis.

Figure 3: Percentage of benchmarks solved per track for each solver.

In the Invariant track, the specialized LOOPINVGEN outperformed general solvers by using a data-driven approach to grow its feature set dynamically. Conversely, the "Instruction Selection" track proved insurmountable, with no solver clearing a single benchmark, indicating a significant gap in handling highly complex grammars where the gap between specification and available operators is wide.

Challenges and Future Directions

Despite the progress in tracks like PBE Strings, several bottlenecks remain for modern solvers:

  1. Interdependent Functions: Synthesizing multiple functions simultaneously remains a major computational bottleneck.
  2. Auxiliary Variables: Benchmarks requiring let expressions for intermediate calculations are significantly harder to navigate.
  3. Grammar Noise: Overly general grammars with many "distractor" operators hinder current enumerative techniques.
  4. Instruction Selection: This remains the "boss level" for future research, requiring new strategies to bridge the gap between specifications and complex operator sets.

Summary updated

Abstract

Syntax-Guided Synthesis (SyGuS) is the computational problem of finding an implementation f that meets both a semantic constraint given by a logical formula phi in a background theory T, and a syntactic constraint given by a grammar G, which specifies the allowed set of candidate implementations. Such a synthesis problem can be formally defined in SyGuS-IF, a language that is built on top of SMT-LIB. The Syntax-Guided Synthesis Competition (SyGuS-Comp) is an effort to facilitate, bring together and accelerate research and development of efficient solvers for SyGuS by providing a platform for evaluating different synthesis techniques on a comprehensive set of benchmarks. In this year's competition six new solvers competed on over 1500 benchmarks. This paper presents and analyses the results of SyGuS-Comp'17.
BibTeX
@inproceedings{alur2017sygus,
  author = {Rajeev Alur and Dana Fisman and Rishabh Singh and Armando Solar-Lezama},
  title = {{SyGuS-Comp 2017: Results and Analysis.}},
  booktitle = {SYNT@CAV},
  year = {2017},
  url = {https://openreview.net/forum?id=p-zhPawIgJjK},
}
Figure