Model checking hyperproperties for Markov decision processes
Model checking hyperproperties for Markov decision processes
复制标题
马尔可夫决策过程的模型检查超属性
DOI：
10.1016/j.ic.2022.104978
复制
发表时间：
2022
影响因子：
1
通讯作者：
Bonakdarpour, Borzoo
中科院分区：
文献类型：
--
作者：
Dobe, Oyendrila;Ábrahám, Erika;Bartocci, Ezio;Bonakdarpour, Borzoo
本文研究马尔可夫决策过程概率超性质的形式化和检验问题。我们介绍的时间逻辑HyperPCTL，允许明确和同时量化的概率计算树以及在多个。我们表明，该逻辑可以表达重要的定量要求，如概率不干扰，差分隐私，定时边信道对策，概率一致性测试的安全性和隐私。我们发现，HyperPCTL模型检查MDP一般是不可判定的，但限制域的调度量化到无记忆的非概率的调度器把模型检查问题可判定的。随后，我们提出了一个基于SMT的编码模型检查这种语言。最后，我们证明了我们的方法的适用性，通过提供实验结果进行验证，我们展示了它如何可以用来解决甚至某些合成问题。
We study the problem of formalizing and checkingprobabilistic hyperpropertiesfor Markov decision processes (MDPs). We introduce the temporal logic HyperPCTL that allows explicit and simultaneous quantification over schedulers as well as probabilistic computation trees. We show that the logic can express important quantitative requirements in security and privacy such as probabilistic noninterference, differential privacy, timing side-channel countermeasures, and probabilistic conformance testing. We show that HyperPCTL model checking over MDPs is in general undecidable, but restricting the domain of scheduler quantification to memoryless non-probabilistic schedulers turns the model checking problem decidable. Subsequently, we propose an SMT-based encoding for model checking this language. Finally, we demonstrate the applicability of our method by providing experimental results for verification, and we show how it can be used to solve even certain synthesis problems.
登录
查看更多内容
影响因子：
0.6
作者：
Finkbeiner, Bernd;Hahn, Christopher;Tentrup, Leander
通讯作者：
Tentrup, Leander
HyperProb：概率超属性的模型检查器
DOI：
--
发表时间：
2021
期刊：
World Congress on Formal Methods
影响因子：
--
作者：
Oyendrila Dobe;E. Ábrahám;E. Bartocci;Borzoo Bonakdarpour
通讯作者：
Borzoo Bonakdarpour
DOI：
10.1109/csf51468.2021.00009
发表时间：
2021
期刊：
2021 IEEE 34th Computer Security Foundations Symposium (CSF
影响因子：
--
作者：
Wang, Yu;Nalluri, Siddhartha;Bonakdarpour, Borzoo;Pajic, Miroslav
通讯作者：
Pajic, Miroslav
马尔可夫决策过程的概率超性质
DOI：
--
发表时间：
2020
期刊：
Automated Technology for Verification and Analysis
影响因子：
--
作者：
Rayna Dimitrova;B. Finkbeiner;Hazem Torfah
通讯作者：
Hazem Torfah
影响因子：
0.8
作者：
Finkbeiner, Bernd;Hahn, Christopher;Tentrup, Leander
通讯作者：
Tentrup, Leander