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.
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).
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