Synthesis of opaque systems with static and dynamic masks

Franck Cassez 1 Jérémy Dubreil 2 Hervé Marchand 3
2 COMETE - Concurrency, Mobility and Transactions
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France, Polytechnique - X, CNRS - Centre National de la Recherche Scientifique : UMR7161
Abstract : Opacity is a security property formalizing the absence of secret information leakage and we address in this paper 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 choose to control the observability of events by adding a device, called a mask, between the system G and the users. We first investigate the case of static partial observability where the set of events the user can observe is fixed a priori by a static mask. In this context, we show that checking whether a system is opaque is PSPACE-complete, which implies that computing an optimal static mask 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 and is chosen by a dynamic mask.We show how to check that a system is opaque w.r.t. to a dynamic mask and also address the corresponding synthesis problem: given a system G and secret states S, compute the set of dynamic masks under which S is opaque. Our main result is that the set of such masks can be finitely represented and can be computed in EXPTIME and this is a lower bound. Finally we also address the problem of computing an optimal mask.
Type de document :
Article dans une revue
Formal Methods in System Design, Springer Verlag, 2012, 40 (1), pp.88-115. 〈10.1007/s10703-012-0141-9〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00662539
Contributeur : Hervé Marchand <>
Soumis le : mardi 24 janvier 2012 - 14:09:26
Dernière modification le : jeudi 11 janvier 2018 - 06:22:14
Document(s) archivé(s) le : mercredi 25 avril 2012 - 02:41:20

Fichier

FMSD-2012.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

Collections

Citation

Franck Cassez, Jérémy Dubreil, Hervé Marchand. Synthesis of opaque systems with static and dynamic masks. Formal Methods in System Design, Springer Verlag, 2012, 40 (1), pp.88-115. 〈10.1007/s10703-012-0141-9〉. 〈hal-00662539〉

Partager

Métriques

Consultations de la notice

248

Téléchargements de fichiers

117