How to Win First-Order Safety Games

Helmut Seidl, Christian Müller, Bernd Finkbeiner

Abstract

First-order (FO) transition systems are essential for verifying parametric systems like network protocols and multi-agent workflows. While verification is well-established, this article explores the frontier of automatic synthesis: generating the predicates necessary to enforce safety and hypersafety properties. By generalizing FO transition systems into FO safety games, we provide a framework for constructing winning strategies. We demonstrate this approach by automatically synthesizing specifications for leader election protocols and conference management systems, ensuring properties like noninterference and functional correctness.

The Challenge of Parametric Synthesis

Parametric systems—where the number of participants, such as processes in a network or papers in a conference, is not fixed—pose a significant challenge for formal methods. Traditionally, researchers have used First-Order (FO) logic to verify that a manually designed protocol is safe. However, a more powerful approach is synthesis: automatically generating the protocol's rules to guarantee safety by design. This paper introduces First-Order Safety Games to bridge this gap, treating the system as a contest between an environment (trying to break safety) and a controller (trying to maintain it).

Methodology: Games and Quantifier Elimination

The authors model these systems as games where states are represented by FO structures and transitions are defined by FO formulas. A key methodological contribution is the proof that if a safety player has a winning strategy, a positional (memoryless) strategy exists.

To synthesize strategies for complex, non-monadic predicates, the authors utilize Second-Order (SO) quantifier elimination. By applying techniques like Ackermann’s Lemma, the synthesis problem is reduced to "solving" for a missing predicate. The goal is often to find the weakest winning strategy—the most permissive rule that still guarantees safety—rather than a trivial or overly restrictive one.

Case Study: Leader Election

One primary application is the synthesis of message content in a ring-based leader election protocol. The goal is to ensure that exactly one leader is elected, regardless of the number of nodes in the ring.

Figure 5: Transition system for a leader election protocol, where the logic for messages and leader designation is synthesized to ensure safety.

The tool successfully synthesized a strategy that is more permissive than standard protocols. Instead of nodes only passing their own IDs, the synthesized logic allows nodes to send any ID higher than their own, provided it doesn't lead to a multi-leader state. This demonstrates the framework's ability to discover non-obvious, optimal protocol specifications.

Case Study: Conference Management

The framework also handles multi-agent workflows, such as conference management systems. Here, the challenge is twofold: ensuring safety (e.g., authors cannot read reports for their own papers) and hypersafety (e.g., ensuring secret information like reviewer identities does not leak through system observations).

Figure 6: A conference management workflow modeled as an FO safety game to synthesize rules for paper assignment and review access.

By treating the assignment process as a game, the system automatically generates the Assign and Review predicates that prevent conflicts of interest and unauthorized data access. The tool correctly distinguished between trivial strategies (like assigning no papers at all) and meaningful, weakest strategies that allow the system to function while remaining safe.

Key Results and Performance

The implementation, which extends the NIWO solver and utilizes the Z3 theorem prover, demonstrated high efficiency. Most benchmarks were resolved in under a second. Even the most complex noninterference benchmarks, which required unrolling loops and handling causal agents, were resolved in roughly 3 to 7 seconds.

Conclusion and Future Directions

While the current approach is limited by the inability to express transitive closure (reachability) without user-provided invariants, it marks a significant step toward the automated design of provably safe parametric systems. Future work will explore models involving partial information, where nodes only see their local state, and history-dependent strategies that could win games where positional strategies fail.

Summary updated

Abstract

First-order (FO) transition systems have recently attracted attention for the verification of parametric systems such as network protocols, software-defined networks or multi-agent workflows like conference management systems. Functional correctness or noninterference of these systems have conveniently been formulated as safety or hypersafety properties, respectively. In this article, we take the step from verification to synthesis—tackling the question whether it is possible to automatically synthesize predicates to enforce safety or hypersafety properties like noninterference. For that, we generalize FO transition systems to FO safety games. For FO games with monadic predicates only, we provide a complete classification into decidable and undecidable cases. For games with non-monadic predicates, we concentrate on universal first-order invariants, since these are sufficient to express a large class of properties—for example noninterference. We identify a non-trivial sub-class where invariants can be proven inductive and FO winning strategies be effectively constructed. We also show how the extraction of weakest FO winning strategies can be reduced to SO quantifier elimination itself. We demonstrate the usefulness of our approach by automatically synthesizing nontrivial FO specifications of messages in a leader election protocol as well as for paper assignment in a conference management system to exclude unappreciated disclosure of reports.
BibTeX
@inproceedings{seidl2020how,
  author = {Helmut Seidl and Christian Müller and Bernd Finkbeiner},
  title = {{How to Win First-Order Safety Games}},
  booktitle = {VMCAI},
  year = {2020},
  url = {https://openreview.net/forum?id=jhlcY6nn94},
}
Figure