摘要
模型检测基于概率系统的反例产生问题,在最近引起人们的关注.已有的工作主要围绕模型检测Markov链的反例产生而开展.基于概率时间自动机(PTA)是Markov链的不确定性和系统时钟的扩展.关注的是模型检测PTA的反例产生问题.首先通过在PTA上寻找概率之和恰好大于λ的k条最大概率的路径,并根据这些路径和原PTA构造原PTA的一个子图,从而快速找到违背性质的具有较少证据的反例.然后精化此结果——通过逐条加入上述各条最大概率的路径来精确地计算已加入路径所构成的PTA子图的最大概率.由于考虑到符号状态交集对概率系统的影响,可以得到证据更少的反例.
Counterexample is a typical topic in model checking. Model checking probabilistic systems have bee3n studied well these years, but counterexample generation for probabilistic system model checking has just drawn some attentions recently. Current works are mainly focusing on the counterexample generation for Markov chain. Probabilistic timed automata （PTA） are the extension of Markov chain with non-determinism and system clocks, and have been used broadly on network protocol modeling and verification. The focus of this paper is on counterexample generation while model is checking PTA. Firstly, a research is made for the k most probable paths whose probability sum is just greater than λ. PTA can be regarded as discrete-time Markov chain （DTMC） in this situation. The sub-graph of PTA constructed from the above paths and the initial PTA is a counterexample which can be obtained quickly with small number of testimonies. When the maximal probability is calculated in a PTA, the contribution to probability not only comes from the contained paths, but also from the symbolic state intersections originated in the existence of system clocks. So refinement can be done as a further step By adding paths from the above one by one in order to decrease probability, and to calculate the precise maximal probability on the sub-graph of PTA constructed from the added paths and initial PTA, the counterexample occupying less testimonies can be obtained. The refinement process is accomplished through an executable and converging algorithm with high efficiency.
出处
《计算机研究与发展》
EI
CSCD
北大核心
2008年第10期1638-1645,共8页
Journal of Computer Research and Development
基金
国家自然科学基金项目(60473036)~~
关键词
模型检测
反例
基于概率时间自动机
符号状态交集
不确定性
model checking
counterexample
probabilistic timed automata
symbolic state intersection
non-determinism
