Parameterized Synthesis with Safety Properties

Oliver Markgraf, Chih-Duo Hong, Anthony W. Lin, Muhammad Najib, Daniel Neider

TL;DR

This paper introduces a novel, learning-based approach to automatically synthesize controllers for parameterized systems that guarantee safety properties. By framing the problem as a regular safety game and leveraging Angluin's L* algorithm, they achieve a conceptually simpler and often more efficient synthesis procedure compared to existing state-of-the-art tools.

What Problem Does This Paper Address?

Many real-world systems, like distributed protocols, have a variable number of components (e.g., processes, clients) that are not known at design time. Ensuring these systems behave correctly, especially with safety guarantees (i.e., preventing "bad things" from happening), is a significant challenge. This problem, known as parameterized verification, is notoriously difficult, even for simple safety properties. While existing methods exist for synthesizing controllers for such systems, they often require significant user guidance or are computationally expensive. This paper aims to bridge this gap by providing an automated, efficient, and conceptually simpler synthesis method for parameterized systems with safety guarantees.

Methods

The core of the paper's approach lies in combining regular model checking with automata learning.

  1. Regular Model Checking: Parameterized systems are modeled as infinite-state systems. The synthesis problem is then translated into an infinite-duration two-player safety game. In these games, one player (the system) tries to avoid "bad" states, while the other (the environment) tries to force the system into them. The goal is to synthesize a strategy (a controller) for the system player that guarantees they always stay in "safe" states, regardless of the environment's moves.
  2. Angluin's L* Algorithm: This is a well-established algorithm for learning regular languages. The authors adapt it to learn a "winning set" of states for the system player. This winning set represents a safe region from which the system can always avoid bad states. The L* algorithm interacts with a "teacher" that can answer membership queries (is a state safe?) and equivalence queries (does the learned set match the true winning set?).
  3. Strict but Generous Teacher: A key innovation is the design of a specialized teacher. This teacher is "strict" in that it drives the learner towards the correct winning set but "generous" in that it accepts any correct winning set, not necessarily the minimal one. This is crucial because winning sets are not always unique.
  4. Length-Preserving Transducers: To make membership queries decidable within the regular model checking framework, the paper restricts the model to use length-preserving transducers. This allows for efficient, finite-state model checking of queries.

Datasets

The paper uses a set of benchmarks to evaluate their tool, L*-PSynth. These benchmarks are derived from:

  • Existing benchmarks from prior work (e.g., [35]), with modifications to fit the regular safety game framework.
  • Known games translated into regular safety games (e.g., the Nim game).
  • Scenarios inspired by real-world applications, such as resource allocation protocols and robotic motion planning.

Specific benchmark examples include: Box game, Control unit game, Diagonal game, Evasion game, Follow game, Nim game, Resource allocation game, Robot vacuum cleaner game, and Solitary box game.

Key Insights and Ideas

  • Learning for Synthesis is Powerful: The paper demonstrates that established automata learning algorithms like L* can be effectively repurposed for synthesizing controllers, not just for verification.
  • Simplicity Can Be Efficient: By leveraging the L* algorithm and regular model checking, the authors achieve a synthesis procedure that is conceptually simpler than many existing methods, yet competitive or even superior in performance.
  • The "Strict but Generous Teacher" is Key: Designing a teacher that guides the learning process without being overly restrictive is crucial for learning winning sets in games where multiple solutions might exist.
  • Regular Model Checking as a Unifying Framework: The paper shows how a wide range of parameterized systems and safety games can be elegantly encoded and solved within the regular model checking paradigm.

Key Results

The paper introduces a tool called L*-PSynth and evaluates its performance against three state-of-the-art tools: SAT-Synth, RPNI-Synth, and DT-Synth.

  • Performance: L*-PSynth successfully solved all 9 benchmark games, while other tools failed on some or timed out.
  • Runtime: L*-PSynth achieved a significantly lower aggregated runtime (20.82 seconds for 9 games) compared to RPNI-Synth (36.91 seconds for 8 games) and SAT-Synth (665.09 seconds for 7 games).
  • Solution Size: L*-PSynth produced smaller synthesized automata for 6 out of 9 benchmarks, outperforming SAT-Synth in this regard as well.
  • Completeness: The approach guarantees a complete synthesis procedure whenever a winning strategy can be expressed by a regular set.

Limitations and Future Work

  • Regularity Assumption: The current approach is limited to cases where the winning strategy can be expressed by a regular set.
  • Liveness Properties: The current work focuses on safety properties. Extending the framework to handle liveness properties (e.g., "something good eventually happens") is a significant future direction.
  • Uncountably Many Vertices: The framework currently handles infinite-state systems that can be encoded using regular languages. Extending it to arenas with uncountably many vertices (common in cyber-physical systems) would require techniques like w-regular languages and w-transducers.
  • Direct Strategy Synthesis: The current method learns a "winning set" as a proxy for a strategy. Future work aims to directly learn the winning strategy itself, which could allow for optimization of criteria like size or computational cost of the next move.

Summary updated

Abstract

Parameterized synthesis offers a solution to the problem of constructing correct and verified controllers for parameterized systems. Such systems occur naturally in practice (e.g., in the form of distributed protocols where the amount of processes is often unknown at design time and the protocol must work regardless of the number of processes). In this paper, we present a novel learning-based approach to the synthesis of reactive controllers for parameterized systems from safety specifications. We use the framework of regular model checking to model the synthesis problem as an infinite-duration two-player game and show how one can utilize Angluin’s well-known L\(^{*}\) algorithm to learn correct-by-design controllers. This approach results in a synthesis procedure that is conceptually simpler than existing synthesis methods with a completeness guarantee, whenever a winning strategy can be expressed by a regular set. We have implemented our algorithm in a tool called L\(^{*}\)-PSynth and have demonstrated its performance on a range of benchmarks, including robotic motion planning and distributed protocols. Despite the simplicity of L\(^{*}\)-PSynth it competes well against (and in many cases even outperforms) the state-of-the-art tools for synthesizing parameterized systems.
BibTeX
@inproceedings{markgraf2020parameterized,
  author = {Oliver Markgraf and Chih-Duo Hong and Anthony W. Lin and Muhammad Najib and Daniel Neider},
  title = {{Parameterized Synthesis with Safety Properties}},
  booktitle = {APLAS},
  year = {2020},
  doi = {10.1007/978-3-030-64437-6\_14},
}
Figure