HyperPCTL*のためのベイズ統計モデル検査によるマルチエージェントシステム検証
Bayesian Statistical Model Checking for Multi-agent Systems using HyperPCTL*
離散時間マルコフ連鎖上の確率的ハイパープロパティを対象に、ベイズ仮説検定に基づく統計的モデル検査アルゴリズムを提案し、SPRT法より高速かつ少ないサンプルで検証できることを示した。
著者: Spandan Das, Pavithra Prabhakar
分類: cs.MA, cs.AI, cs.LO, cs.RO
原文アブストラクト
In this paper, we present a Bayesian method for statistical model checking (SMC) of probabilistic hyperproperties specified in the logic HyperPCTL* on discrete-time Markov chains (DTMCs). While SMC of HyperPCTL* using sequential probability ratio test (SPRT) has been explored before, we develop an alternative SMC algorithm based on Bayesian hypothesis testing. In comparison to PCTL*, verifying HyperPCTL* formulae is complex owing to their simultaneous interpretation on multiple paths of the DTMC. In addition, extending the bottom-up model-checking algorithm of the non-probabilistic setting is not straight forward due to the fact that SMC does not return exact answers to the satisfiability problems of subformulae, instead, it only returns correct answers with high-confidence. We propose a recursive algorithm for SMC of HyperPCTL* based on a modified Bayes' test that factors in the uncertainty in the recursive satisfiability results. We have implemented our algorithm in a Python toolbox, HyProVer, and compared our approach with the SPRT based SMC. Our experimental evaluation demonstrates that our Bayesian SMC algorithm performs better both in terms of the verification time and the number of samples required to deduce satisfiability of a given HyperPCTL* formula.
