The FLINT Project








Refinement-Based Game Semantics for Certified Abstraction Layers

Last modified: Wed Jun 24 22:51:57 2020 GMT.


Jérémie Koenig
Zhong Shao


Formal methods have advanced to the point where the functional correctness of various large system components has been mechanically verified. However, the diversity of semantic models used across projects makes it difficult to connect these component to build larger certified systems. Given this, we seek to embed these models and proofs into a general-purpose framework where they could interact. We believe that a synthesis of game semantics, the refinement calculus, and algebraic effects can provide such a framework.

To combine game semantics and refinement, we replace the downset completion typically used to construct strategies from posets of plays. Using the free completely distributive completion, we construct strategy specifications equipped with arbitrary angelic and demonic choices and ordered by a generalization of alternating refinement. This provides a novel approach to nondeterminism in game semantics.

Connecting algebraic effects and game semantics, we interpret effect signatures as games and define two categories of effect signatures and strategy specifications. The resulting models are sufficient to represent the behaviors of a variety of low-level components, including the certified abstraction layers used to verify the operating system kernel CertiKOS.


In Proc. 35th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS'20), Saarbrücken, Germany, pages 633-647, July 2020.
  • Conference Paper [PDF]
  • Conference Presentation Slides [PDF] and Video [mp4]

  • Copyright © 1996-2023 The FLINT Group <flint at cs dot yale dot edu>
    Yale University Department of Computer Science
    Validate this page