-
Selection by year
-
Selection by authors
-
Complete lists
atva09
F. Cassez, J. Dubreil, H. Marchand. Dynamic Observers for the Synthesis of Opaque Systems. In 7th International Symposium on Automated Technology for Verification and Analysis (ATVA'09), Z. Liu, A.P. Ravn (eds.), LNCS, Volume 5799, Pages 352-367, Macao SAR, China, October 2009.
Download [help]
Download paper:
Doi page 
Download paper:
Adobe portable document (pdf) 
Copyright notice:
This material is presented to ensure timely dissemination of scholarly and
technical work. Copyright and all rights therein are retained by authors or
by other copyright holders. All persons copying this information are expected
to adhere to the terms and constraints invoked by each author's
copyright. These works may not be reposted without the explicit permission of
the copyright holder.
This page is automatically generated by bib2html v216, © INRIA 2002-2007, Projet Lagadic
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
Contact
Hervé Marchand http://people.rennes.inria.fr/Herve.Marchand/
BibTex Reference
@InProceedings{atva09,
Author = {Cassez, F. and Dubreil, J. and Marchand, H.},
Title = {Dynamic Observers for the Synthesis of Opaque Systems},
BookTitle = {7th International Symposium on Automated Technology for Verification and Analysis (ATVA'09)},
editor = {Liu, Z. and Ravn, A.P.},
Volume = { 5799},
Pages = {352--367},
Series = {LNCS},
Publisher = {Springer-Verlag},
Address = {Macao SAR, China},
Month = {October},
Year = {2009}
}
EndNote Reference [help]
Get EndNote Reference (.ref)