Probabilistic opacity for Markov decision processes

B. Bérard, K. Chatterjee, N. Sznajder, Information Processing Letters 115 (2015) 52–59.


Journal Article | Published | English
Author
; ;
Department
Abstract
Opacity is a generic security property, that has been defined on (non-probabilistic) transition systems and later on Markov chains with labels. For a secret predicate, given as a subset of runs, and a function describing the view of an external observer, the value of interest for opacity is a measure of the set of runs disclosing the secret. We extend this definition to the richer framework of Markov decision processes, where non-deterministicchoice is combined with probabilistic transitions, and we study related decidability problems with partial or complete observation hypotheses for the schedulers. We prove that all questions are decidable with complete observation and ω-regular secrets. With partial observation, we prove that all quantitative questions are undecidable but the question whether a system is almost surely non-opaquebecomes decidable for a restricted class of ω-regular secrets, as well as for all ω-regular secrets under finite-memory schedulers.
Publishing Year
Date Published
2015-01-01
Journal Title
Information Processing Letters
Volume
115
Issue
1
Page
52 - 59
IST-REx-ID

Cite this

Bérard B, Chatterjee K, Sznajder N. Probabilistic opacity for Markov decision processes. Information Processing Letters. 2015;115(1):52-59. doi:10.1016/j.ipl.2014.09.001
Bérard, B., Chatterjee, K., & Sznajder, N. (2015). Probabilistic opacity for Markov decision processes. Information Processing Letters, 115(1), 52–59. https://doi.org/10.1016/j.ipl.2014.09.001
Bérard, Béatrice, Krishnendu Chatterjee, and Nathalie Sznajder. “Probabilistic Opacity for Markov Decision Processes.” Information Processing Letters 115, no. 1 (2015): 52–59. https://doi.org/10.1016/j.ipl.2014.09.001.
B. Bérard, K. Chatterjee, and N. Sznajder, “Probabilistic opacity for Markov decision processes,” Information Processing Letters, vol. 115, no. 1, pp. 52–59, 2015.
Bérard B, Chatterjee K, Sznajder N. 2015. Probabilistic opacity for Markov decision processes. Information Processing Letters. 115(1), 52–59.
Bérard, Béatrice, et al. “Probabilistic Opacity for Markov Decision Processes.” Information Processing Letters, vol. 115, no. 1, Elsevier, 2015, pp. 52–59, doi:10.1016/j.ipl.2014.09.001.

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar