HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Reports

Dynamic Observers for the Synthesis of Opaque Systems

Abstract : In this paper, we address the problem of synthesizing opaque systems. A secret predicate S over the runs of a system G is opaque to an external user having partial observability over G, if s/he can never infer from the observation of a run of G that the run belongs to S. We first investigate the case of static partial observability where the set of events the user can observe is fixed a priori. In this context, we show that checking whether a system is opaque is PSPACE-complete, which implies that computing an optimal static observer ensuring opacity is also a PSPACE-complete problem. Next, we introduce dynamic partial observability where the set of events the user can observe changes over time. We show how to check that a system is opaque w.r.t. to a dynamic observer and also address the corresponding synthesis problem: given a system G and secret states S, compute the set of dynamic observers under which S is opaque. Our main result is that the set of such observers can be finitely represented and can be computed in EXPTIME.
Document type :
Reports
Complete list of metadata

Cited literature [24 references]  Display  Hide  Download

https://hal.inria.fr/inria-00396442
Contributor : Anne Jaigu Connect in order to contact the contributor
Submitted on : Thursday, June 18, 2009 - 10:43:07 AM
Last modification on : Wednesday, April 27, 2022 - 4:25:07 AM
Long-term archiving on: : Tuesday, June 15, 2010 - 5:32:45 PM

File

PI-1930.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00396442, version 1

Citation

Franck Cassez, Jérémy Dubreil, Hervé Marchand. Dynamic Observers for the Synthesis of Opaque Systems. [Research Report] PI 1930, 2009, pp.22. ⟨inria-00396442⟩

Share

Metrics

Record views

189

Files downloads

228