Dependency-Based Compositional Synthesis

Bernd Finkbeiner, Noemi Passing

TL;DR

Reactive synthesis struggles to scale to complex multi-component systems because individual components rarely have independent "winning" strategies. This paper introduces an incremental synthesis approach that decomposes systems based on variable dependencies and synthesizes "dominant" strategies sequentially, allowing components to rely on the known behavior of previously synthesized parts to drastically improve scalability.

What Problem Does This Paper Address?

Reactive synthesis is the "holy grail" of software engineering: you write a high-level specification (usually in Linear Temporal Logic, or LTL), and the system automatically generates a correct-by-construction implementation. However, it suffers from massive state-space explosion.

To scale synthesis, researchers use compositional synthesis, which breaks a large system into smaller components and synthesizes them independently. The fatal flaw here is that components in real-world systems usually have to cooperate. If Component A's success depends on Component B doing its job correctly, Component A does not have a guaranteed "winning" strategy in isolation. Because standard synthesis looks for strict winning strategies against an adversarial environment, compositional synthesis usually fails unless the human engineer extensively rewrites the specification to manually decouple the components. This paper seeks to automate this process, allowing compositional synthesis to work on interdependent components without manual intervention.

Methods

The authors pivot from traditional compositional synthesis to an incremental synthesis approach using dominant strategies.

  1. Remorsefree Dominance: Instead of demanding a "winning" strategy (which guarantees success against any environment), the algorithm looks for a "dominant" strategy. A dominant strategy might fail if the environment acts maliciously, but it performs at least as well as any alternative strategy. Essentially: "do your best, and you won't be blamed if the other components mess up."
  2. Dependency Analysis: To figure out the order in which to synthesize components, the authors introduce two dependency analysis techniques:
  3. Semantic Analysis: A rigorous mathematical check of how changing one output variable affects the need to change another to satisfy the spec. It perfectly identifies which components depend on which, but computing it is highly complex.
  4. Syntactic Analysis: A faster, conservative approximation that looks at the syntax tree of the LTL formula to guess dependencies based on how variables are grouped under logical operators (like AND, OR, and temporal operators).
  5. Incremental Synthesis Order: Using the dependency graph, the system is partitioned into strongly connected components. The algorithm synthesizes a dominant strategy for the foundational components first. Then, it moves to the next layer, synthesizing their strategies under the assumption that the first layer will follow its already-synthesized strategy.
  6. Specification Simplification: To further speed things up, the algorithm mathematically strips out parts of the specification that are irrelevant to the specific component currently being synthesized.

Datasets

The authors evaluated their prototype on four scalable, parameterized benchmarks:

  • n-ary Latch (from the SYNTCOMP 2018 competition)
  • Generalized Buffer (from SYNTCOMP 2018)
  • Sensors: A custom benchmark featuring $n$ sensors and a managing unit.
  • Robot Fleet: A custom benchmark featuring $n$ robots avoiding a collision with an external crossing robot.

Key Insights and Ideas

  • Dominance breaks the compositional deadlock: By shifting the goalpost from "must win no matter what" to "do your best" (dominance), we can mathematically justify synthesizing interdependent components separately.
  • Order is everything: If Component A depends on Component B, synthesizing them simultaneously causes a state-space explosion. Synthesizing A before B yields no strategy. But synthesizing B first, and feeding B's exact strategy to A as a known environmental assumption, makes A's synthesis trivial.
  • Syntax is a "good enough" proxy for semantics: While semantic dependency analysis is perfect, it is a complex "hyperproperty" that is hard to compute. The authors proved that simply looking at the structure of the LTL formula (syntactic analysis) is a safe overapproximation that still yields massive speedups in practice.

Key Results

The authors implemented their incremental algorithm as a prototype extending BoSy, a state-of-the-art bounded synthesis tool. The results show massive scalability improvements over standard monolithic synthesis:

  • Generalized Buffer: Standard BoSy timed out (after 60 minutes) at 2 receivers. The incremental approach solved 3 receivers in just 66 seconds.
  • Robot Fleet: Standard BoSy timed out at 3 robots. The incremental approach solved 4 robots in 269 seconds.
  • n-ary Latch: The incremental approach successfully scaled up to an impressive 1104 bits in under an hour, whereas standard BoSy timed out at just 5 bits.

Limitations and Future Work

  • Syntactic Overapproximation: The faster syntactic analysis is conservative. In the Sensors benchmark, the syntactic rules were too strict and failed to realize the sensors could be separated from the managing unit, missing out on optimization opportunities that the heavier semantic analysis caught.
  • Future Work: The current prototype is built on bounded synthesis (which translates the problem to SAT/SMT solvers). The authors note that this dependency-based incremental framework is highly adaptable and could be integrated into other synthesis paradigms, such as explicit approaches (like the tool Strix), provided they are extended to support dominant strategies.

Summary updated

Abstract

Despite many recent advances, reactive synthesis is still not really a practical technique. The grand challenge is to scale from small transition systems, where synthesis performs well, to complex multi-component designs. Compositional methods, such as the construction of dominant strategies for individual components, reduce the complexity significantly, but are usually not applicable without extensively rewriting the specification. In this paper, we present a refinement of compositional synthesis that does not require such an intervention. Our algorithm decomposes the system into a sequence of components, such that every component has a strategy that is dominant, i.e., performs at least as good as any possible alternative, provided that the preceding components follow their (already synthesized) strategies. The decomposition of the system is based on a dependency analysis, for which we provide semantic and syntactic techniques. We establish the soundness and completeness of the approach and report on encouraging experimental results.
BibTeX
@inproceedings{finkbeiner2020dependency,
  author = {Bernd Finkbeiner and Noemi Passing},
  title = {{Dependency-Based Compositional Synthesis}},
  booktitle = {ATVA},
  year = {2020},
  doi = {10.1007/978-3-030-59152-6\_25},
}

Loading related content...

Figure