Counterexample-Driven Genetic Programming: Stochastic Synthesis of Provably Correct Programs

Krzysztof Krawiec, Iwo Bladek, Jerry Swan, John H. DrakeIJCAI 2018 · OpenReview

TL;DR

This paper introduces Counterexample-Driven Genetic Programming (CDGP), a novel approach to program synthesis that combines evolutionary search with formal verification. By using counterexamples generated from failed formal proofs to guide the evolutionary process, CDGP can synthesize provably correct programs from formal specifications, overcoming the generalization limitations of traditional test-based methods.

What Problem Does This Paper Address?

Traditional program synthesis techniques, particularly those based on Genetic Programming (GP), often rely on "test-based" specifications. These specifications consist of input-output examples, and while GP can effectively learn programs that satisfy these examples, there's no guarantee that the synthesized program will behave correctly for inputs not seen during training. This lack of generalization is a significant drawback for applications where correctness is paramount, such as in safety-critical systems or security. The paper addresses this by proposing a method to synthesize programs that are provably correct according to formal specifications, ensuring adherence to the intended behavior for all possible inputs.

Methods

CDGP builds upon the principles of Genetic Programming but integrates formal verification into its evaluation phase. Instead of solely relying on a fitness function derived from test cases, CDGP uses a Satisfiability Modulo Theories (SMT) solver to formally verify candidate programs against a given formal specification (defined by preconditions and postconditions).

Here's how it works:

  1. Evolutionary Search: Like standard GP, CDGP maintains a population of candidate programs and evolves them over generations through selection, crossover, and mutation.
  2. Formal Verification: For each program, CDGP attempts to formally verify its correctness against the specification using an SMT solver.
  3. Counterexample Generation: If the verification fails, the SMT solver provides a "counterexample" – a specific input for which the program violates the specification.
  4. Fitness Update: These counterexamples are then used to augment the set of test cases. Programs are evaluated based on how many of these tests (including the newly generated counterexamples) they pass. This creates a more informative fitness function that guides the search towards programs that satisfy the formal specification.
  5. Conservative vs. Non-Conservative: The paper explores two variants: a "conservative" approach that only verifies programs that have already passed all existing tests, and a "non-conservative" approach that verifies every program.

Datasets

The paper evaluates CDGP on a range of "spec-based synthesis benchmarks" of varying difficulty. These benchmarks belong to the theory of Linear Integer Arithmetic (LIA) and involve synthesizing functions with linear arithmetic, Boolean logic, and conditional statements. The benchmarks include:

  • Functions from the "Syntax Guided Synthesis" competition (e.g., CountPos, IsSeries, IsSorted, Max, Median, Range, Search, Sum).
  • Additional benchmarks designed by the authors.

The paper also introduces a baseline approach called "GP Random" (GPR), which is similar to CDGP but adds randomly generated tests instead of counterexamples.

Key Insights and Ideas

  • Counterexamples as Powerful Tests: The core insight is that counterexamples generated by formal verification are significantly more effective "tests" for guiding evolutionary search than randomly generated inputs. This is because counterexamples are derived directly from the problem specification and reflect the solver's sophisticated search tactics, providing targeted feedback.
  • Bridging the Gap: CDGP successfully bridges the gap between stochastic, test-based synthesis (like standard GP) and formal, provably correct synthesis. It leverages the strengths of both paradigms.
  • Generalization is Achievable: By focusing on formal specifications and using counterexamples, CDGP demonstrates that it's possible to achieve provable generalization in evolutionary program synthesis.
  • Non-conservative is Better: The non-conservative variant of CDGP, which verifies every program, generally outperforms the conservative variant. This suggests that actively seeking out and learning from violations, even for programs that might seem "good" on existing tests, is crucial for effective synthesis.

Key Results

CDGP systematically outperforms existing approaches on the tested benchmarks. Key findings include:

  • Higher Success Rate: CDGP offers a greater likelihood of synthesizing a correct program compared to baseline methods like GPR.
  • Faster Synthesis: CDGP typically synthesizes correct programs faster and uses fewer tests.
  • Lexicase Selection Boost: Incorporating Lexicase selection significantly improves the performance of both CDGP and GPR.
  • Computational Cost: While formal verification adds computational overhead, the improved effectiveness of CDGP often justifies this cost, especially when considering the guarantee of correctness. In experiments where time budgets were equalized, CDGP proved more effective.

Limitations and Future Work

Limitations: * Computational Overhead: The primary limitation acknowledged is the significant computational cost associated with formal verification using SMT solvers, which can increase runtimes. * Scalability: While CDGP shows promise, the paper notes that exact methods of program synthesis struggle to scale with program length, implying that CDGP might also face scalability challenges for very complex programs.

Future Work: * Broader Domains: The authors suggest that CDGP can be extended to other domains supported by SMT solvers, such as reasoning about Reals, Strings, or Lists, opening up possibilities for synthesizing programs in these areas. * Hybridization: The work paves the way for more effective hybridization of heuristic search methods like GP with specification-based synthesis. * Further Exploration: The paper mentions investigating steady-state GP and other selection mechanisms, though steady-state did not yield anticipated benefits in their experiments.

Summary updated

Abstract

Genetic programming is an effective technique for inductive synthesis of programs from tests, i.e. training examples of desired input-output behavior. Programs synthesized in this way are not guaranteed to generalize beyond the training set, which is unacceptable in many applications. We present Counterexample-Driven Genetic Programming (CDGP) that employs evolutionary search to synthesize provably correct programs from formal specifications. CDGP employs a Satisfiability Modulo Theories (SMT) solver to formally verify programs in the evaluation phase. A failed verification produces counterexamples that are in turn used to calculate fitness and thereby drive the search process. When compared with a range of approaches on a suite of state-of-the-art specification-based synthesis benchmarks, CDGP systematically outperforms them, typically synthesizing correct programs faster and using fewer tests.
BibTeX
@inproceedings{krawiec2018counterexample,
  author = {Krzysztof Krawiec and Iwo Bladek and Jerry Swan and John H. Drake},
  title = {{Counterexample-Driven Genetic Programming: Stochastic Synthesis of Provably Correct Programs}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  url = {https://openreview.net/forum?id=ry4PA4M_br},
}
Figure