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.
Type de document :
Communication dans un congrès
7th International Symposium on Automated Technology for Verification and Analysis (ATVA'09), Oct 2009, Macao SAR, China. Springer-Verlag, 5799, pp.352-367, 2009, Lecture notes in computer science. 〈10.1007/978-3-642-04761-9_26〉
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00399229
Contributeur : Hervé Marchand <>
Soumis le : vendredi 16 octobre 2009 - 09:02:52
Dernière modification le : mercredi 16 mai 2018 - 11:48:03
Document(s) archivé(s) le : lundi 15 octobre 2012 - 14:45:23

Fichier

atva-final.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Franck Cassez, Jérémy Dubreil, Hervé Marchand. Dynamic Observers for the Synthesis of Opaque Systems. 7th International Symposium on Automated Technology for Verification and Analysis (ATVA'09), Oct 2009, Macao SAR, China. Springer-Verlag, 5799, pp.352-367, 2009, Lecture notes in computer science. 〈10.1007/978-3-642-04761-9_26〉. 〈inria-00399229〉

Partager

Métriques

Consultations de la notice

233

Téléchargements de fichiers

81