Tue 18 Jan 2022 09:30 - 10:00 at Salon I - Synthesis Chair(s): Viktor Kunčak

In classic program synthesis algorithms, such as counterexample-guided inductive synthesis (CEGIS), the algorithms alternate between a synthesis phase and an oracle (verification) phase. Many synthesis algorithms use a white-box oracle based on satisfiability modulo theory (SMT) solvers to provide counterexamples. But what if a white-box oracle is either not available or not easy to work with? We present a framework for solving a general class of oracle-guided synthesis problems which we term synthesis modulo oracles. In this setting, oracles are black boxes with a query-response interface defined by the synthesis problem. As a necessary component of this framework, we also formalize the problem of satisfiability modulo theories and oracles, and present an algorithm for solving this problem. We implement a prototype solver for satisfiability and synthesis modulo oracles and demonstrate that, by using oracles that execute functions not easily modeled in SMT-constraints, such as recursive functions or oracles that incorporate compilation and execution of code, SMTO and SyMO can solve problems beyond the abilities of standard SMT and synthesis solvers.

Tue 18 Jan

Displayed time zone: Eastern Time (US & Canada) change

09:00 - 10:00
SynthesisVMCAI at Salon I
Chair(s): Viktor Kunčak EPFL, Switzerland
09:00
30m
Paper
Gradient-Descent for Randomized Controllers under Partial ObservabilityInPerson
VMCAI
Jip Spel RWTH Aachen University, Linus Heck RWTH Aachen University, Sebastian Junges University of California, Berkeley, Joshua Moerman Open University of the Netherlands, Joost-Pieter Katoen RWTH Aachen University
09:30
30m
Paper
Satisfiability and Synthesis Modulo OraclesRemote
VMCAI
Elizabeth Polgreen University of Edinburgh, Andrew Reynolds University of Iowa, Sanjit Seshia UC Berkeley