LTL概率模型检验优化技术的研究

作     者：林哲超 

作者单位：国防科学技术大学 

学位级别：硕士

导师姓名：齐治昌

授予年度：2015年

学科分类：02[经济学] 0202[经济学-应用经济学] 020208[经济学-统计学] 07[理学] 0714[理学-统计学（可授理学、经济学学位）] 070103[理学-概率论与数理统计] 0701[理学-数学] 

主      题：LTL 概率模型检验 优化 

摘      要：概率模型检验是一种针对概率模型的形式化验证技术,与传统的非概率模型检验相比,概率模型检验不仅能对系统进行定性的检验,即判断系统是否满足某个给定的性质,而且还能定量的对概率系统,或者具有概率行为的系统进行检验,即模型在哪个概率区间满足给出的性质。概率模型检验中,通常用线性时序逻辑(Linear Temporal Logic,LTL)和计算树逻辑(Computational Tree Logic,CTL)来描述系统性质。虽然LTL与CTL表达能力有交集,但是如公平性性质这样重要的性质只能用LTL来表示。然而,相比于CTL,当前LTL概率模型检验算法的复杂度非常高,验证效率很低,因此目前已有的概率模型工具如MRMC和PRISM均不支持对LTL性质的验证。针对这个问题,本文提出了一种基于概率保持的公式化简技术。该优化技术通过缩短待验证公式的长度来减小算法执行的时空开销,从而提高算法的执行效率,在一定程度上缓解了LTL概率模型检验算法复杂度高的难题。以上述方法为基础,本文设计并实现了一个LTL概率模型检验工具,并针对现有概率模型检验的案例,利用该工具进行LTL概率模型检验的测试,以检验算法的有效性。