FM2024Top-tier venue
The Opacity of Timed Automata
Jie An, Qiang Gao, Lingtai Wang, Naijun Zhan, Ichiro Hasuo
Abstract
Opacity serves as a critical security and confidentiality property, which concerns whether an intruder can unveil a system's secret based on structural knowledge and observed behaviors. Opacity in timed systems presents greater complexity compared to untimed systems, and it has been established that opacity for timed automata is undecidable. However, there exists a gap in the original proof concerning one-clock timed automata. In this paper, we explore three types of opacity within timed automata: language-based timed opacity, initial-location timed opacity, and current-location timed opacity. We begin by formalizing these concepts and establishing transformation relations among them. Subsequently, we fill the gap in the original proof by demonstrating the undecidability of the opacity problem for one-clock timed automata. Furthermore, we offer a constructive proof for the conjecture regarding the decidability of opacity for timed automata in discrete-time semantics. Additionally, we present a sufficient condition and a necessary condition for the decidability of opacity in specific subclasses of timed automata.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
Lineage
Builds on1
Related papers
- First-Order AutomataLuca Geatti, Alessandro Gianola, Nicola GiganteAAAI 2025 · 3 citations
- A Temporal Logic for Asynchronous HyperpropertiesJan Baumeister, Norine Coenen, Borzoo Bonakdarpour, Bernd Finkbeiner et al.CAV 2021 · 52 citations
- Asynchronous Extensions of HyperLTLLaura Bozzelli, Adriano Peron, César SánchezLICS 2021 · 36 citations
- Formalising the Prevention of Microarchitectural Timing Channels by Operating SystemsRobert Sison, Scott Buckley, Toby Murray, Gerwin Klein et al.FM 2023 · 2 citations
- Generalizing Non-punctuality for Timed Temporal Logic with Freeze QuantifiersShankara Narayanan Krishna, Khushraj Madnani, Manuel Mazo Jr., Paritosh K. PandyaFM 2021 · 3 citations
