A Timed Obstruction Logic for Dynamic Game Models
Securing computational systems within vital infrastructures, such as healthcare, aviation, and energy grids, against malicious attacks is an increasingly difficult challenge. Specially, provably secure systems are often required given the strict guarantees provided by formal methods. However, adversarial threats faced by these critical systems are highly sophisticated, needing verification methods that account for temporal constraints and dynamic interactions. While Timed Game Theory has recently emerged as a robust theoretical foundation for modeling attacker-defender dynamics, it often lacks the expressive power to capture complex real-time properties without prohibitive computational costs. In this paper, we introduce Timed Obstruction Logic (TOL), an extension of Obstruction Logic (OL) for verifying timed games with real-time objectives in dynamic models. TOL formally defines interactions where players’ actions influence the underlying system model, capturing essential timed properties required for cyber defense. Furthermore, we propose and implement a PSPACE-complete verification algorithm for TOL, achieving significantly higher expressiveness without exceeding the complexity bounds of classical timed temporal logics. Finally, we benchmarked our implementation against multiple case studies, confirming its potential viability for verifying real-time constraints in cybersecurity scenarios.
Authors
- Vadim Malvone (ORCID: https://orcid.org/0000-0001-6138-4229)
- James Ortiz (ORCID: https://orcid.org/0000-0001-5407-963X)
- David Cortés (ORCID: https://orcid.org/0009-0002-5771-8817)
- Jean Leneutre (ORCID: https://orcid.org/0000-0003-4810-0791)
Institutions
- Télécom Paris (FR)
- Université Paris-Est Créteil (FR)
- Institut Polytechnique de Paris (FR)
- Laboratoire Traitement et Communication de l’Information (FR)
Publication Details
- Journal
- ACM Transactions on Software Engineering and Methodology
- Published
- 2026-11-14
- DOI
- https://doi.org/10.1145/3862478
- Citations
- 1
- Primary Topic
- Formal Methods in Verification
- Type
- article
- Field-Weighted Citation Impact
- 2.37