Refining Constructive Hybrid Games

Rose Bohrer, André Platzer

TL;DR

This paper introduces a novel refinement calculus for Constructive Differential Game Logic (CdGL), enabling the formal verification of hybrid games. This calculus allows for the "inlining" of winning strategies from hybrid games into concrete hybrid systems, effectively translating game-theoretic specifications into implementable code. This work bridges a critical gap, allowing us to leverage powerful game-theoretic reasoning for the robust design of cyber-physical systems.

What Problem Does This Paper Address?

Cyber-physical systems (CPS) are increasingly complex, operating in dynamic and adversarial environments. Ensuring their reliability requires formal methods that can handle both discrete control logic and continuous dynamics, all while accounting for potential adversaries. Differential Game Logic (dGL) and its constructive variant (CdGL) provide a powerful framework for proving properties of such systems by modeling them as hybrid games.

While CdGL can prove the existence of winning strategies for specific goals, a significant challenge remains: how do we translate these abstract winning strategies into actual, executable code for CPS? Existing tools for synthesizing code from formal specifications are well-developed for simpler "systems" (one-player games), but applying them to the richer expressiveness of hybrid games has been difficult. This paper addresses this gap by providing a formal method to construct a hybrid system that embodies a winning strategy from a hybrid game.

Methods

The core contribution of this paper is the development of a refinement calculus for CdGL. This calculus allows us to formally compare two hybrid games and prove that one "refines" another. This means that any winning strategy for a postcondition in the refined game also guarantees a winning strategy in the original game.

The key techniques include:

  • Constructive Game Logic (CdGL): Building upon prior work, the paper uses a constructive logic where proofs directly yield implementable strategies.
  • Refinement Connective: A new connective is introduced to formally express game refinements. This allows reasoning about the relationship between games.
  • Type-Theoretic Semantics: The semantics of CdGL and the refinement calculus are grounded in a type theory, ensuring their formal correctness and enabling proof extraction.
  • Inlining Operation: A recursive operation is defined that takes a hybrid game and a proof of a winning strategy, and produces a corresponding hybrid system. This system commits to the winning strategy's choices while leaving only adversarial choices to the opponent.
  • Proof Calculus: A natural deduction calculus for game refinements is provided, along with rules for handling discrete and continuous components of hybrid games.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Bridging the Game-System Divide: The most significant insight is the formalization of "inlining" strategies from games to systems. This is not just a theoretical exercise; it provides a concrete pathway to implement game-theoretic guarantees in real-world CPS.
  • Refinement as a Unifying Concept: The refinement calculus acts as a crucial bridge. It allows us to formally relate games and systems, proving that an inlined system correctly captures the essence of the game's winning strategy.
  • Constructivity is Key: The constructive nature of CdGL is essential. It ensures that the extracted strategies are not just abstract proofs but are effectively computable, making them suitable for implementation.
  • Formalizing Folklore: The paper formalizes a long-standing idea in the community: that winning strategies in games can be translated into systems. This formalization provides the necessary rigor and machinery to achieve this.

Key Results

  • Sound Refinement Calculus: The paper presents a sound refinement calculus for CdGL, meaning all provable statements are semantically valid.
  • Inlining Theorems: The paper proves key theorems about the inlining operation:
  • Systemhood: The inlined program is guaranteed to be a system (i.e., it does not contain adversarial choices).
  • Transfer: If a game property holds, the corresponding property holds for the inlined system.
  • Refinement: The inlined system refines the original game, meaning it is at least as safe or robust.
  • Formalization of Strategy Equality: The refinement calculus provides an "intensional" view of strategy equality: two strategies are the same if their inlined systems refine each other.

Limitations and Future Work

  • System-Test Fragment: The inlining operation is primarily defined for the "system-test" fragment of CdGL. While this is a practical restriction, extending it to more general cases could be beneficial.
  • Practical Implementation: While the theoretical framework is established, the practical implementation and integration of these techniques into existing CPS development tools are future work.
  • Comparing Controllers: The authors suggest that refinements can be used to compare the efficacy of different controllers, a direction for future research.
  • Broader Applications: The authors envision this work enabling a wider range of applications in hybrid systems and games literature, leveraging the modeling power and synthesis guarantees of CdGL.

Summary updated

Abstract

We extend the constructive differential game logic (CdGL) of hybrid games with a refinement connective that relates two hybrid games. We use this connective to prove a folk theorem relating hybrid games to hybrid systems.
BibTeX
@inproceedings{bohrer2020refining,
  author = {Rose Bohrer and André Platzer},
  title = {{Refining Constructive Hybrid Games}},
  booktitle = {FSCD},
  year = {2020},
  doi = {10.4230/lipics.fscd.2020.14},
}
Figure