License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2017.13
URN: urn:nbn:de:0030-drops-83844
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8384/
Go to the corresponding LIPIcs Volume Portal

Bérard, Béatrice ; Haddad, Serge ; Lefaucheux, Engel

Probabilistic Disclosure: Maximisation vs. Minimisation

pdf-format:
LIPIcs-FSTTCS-2017-13.pdf (0.6 MB)

Abstract

We consider opacity questions where an observation function provides
to an external attacker a view of the states along executions and
secret executions are those visiting some state from a fixed
subset. Disclosure occurs when the observer can deduce from a finite
observation that the execution is secret, the epsilon-disclosure
variant corresponding to the execution being secret with probability
greater than 1 - epsilon. In a probabilistic and non deterministic
setting, where an internal agent can choose between actions, there
are two points of view, depending on the status of this agent: the
successive choices can either help the attacker trying to disclose
the secret, if the system has been corrupted, or they can prevent
disclosure as much as possible if these choices are part of the
system design. In the former situation, corresponding to a worst
case, the disclosure value is the supremum over the strategies of
the probability to disclose the secret (maximisation), whereas in
the latter case, the disclosure is the infimum (minimisation). We
address quantitative problems (comparing the optimal value with a
threshold) and qualitative ones (when the threshold is zero or one)
related to both forms of disclosure for a fixed or finite
horizon. For all problems, we characterise their decidability status
and their complexity. We discover a surprising asymmetry: on the one
hand optimal strategies may be chosen among deterministic ones in
maximisation problems, while it is not the case for minimisation. On
the other hand, for the questions addressed here, more minimisation
problems than maximisation ones are decidable.

BibTeX - Entry

@InProceedings{brard_et_al:LIPIcs:2018:8384,
  author =	{B{\'e}atrice B{\'e}rard and Serge Haddad and Engel Lefaucheux},
  title =	{{Probabilistic Disclosure: Maximisation vs. Minimisation}},
  booktitle =	{37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)},
  pages =	{13:1--13:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-055-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{93},
  editor =	{Satya Lokam and R. Ramanujam},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8384},
  URN =		{urn:nbn:de:0030-drops-83844},
  doi =		{10.4230/LIPIcs.FSTTCS.2017.13},
  annote =	{Keywords: Partially observed systems, Opacity, Markov chain, Markov decision process}
}

Keywords: Partially observed systems, Opacity, Markov chain, Markov decision process
Collection: 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)
Issue Date: 2018
Date of publication: 12.02.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI