一个命题投影时序逻辑符号模型检测器

来源：软件学报杂志2015年第8期北京时间：

作者：逄涛,段振华,刘晓芳

单位：逄涛，西安电子科技大学 计算理论与技术研究所, 陕西 西安 710071;综合业务网理论与关键技术国家重点实验室(西安电子科技大学), 陕西 西安 71007111,段振华，西安电子科技大学 计算理论与技术研究所, 陕西 西安 710071;综合业务网理论与关键技术国家重点实验室(西安电子科技大学), 陕西 西安 71007102,刘晓芳，西安电子科技大学 计算理论与技术研究所, 陕西 西安 710071;综合业务网理论与关键技术国家重点实验室(西安电子科技大学), 陕西 西安 71007103

摘要：现有模型检测工具的形式化规范语言,如计算树逻辑(computation tree logic,简称CTL)和线性时序逻辑(linear temporal logic,简称LTL)等的描述能力不足,无法验证ω正则性质.提出了一个命题投影时序逻辑(propositional projection temporal logic,简称PPTL)符号模型检测工具——PLSMC(PPTL symbolic model checker)的设计与实现过程.该工具基于著名的符号模型检测系统NuSMV,实现了PPTL的符号模型检测算法.PLSMC的规范语言PPTL具有完全正则表达能力,这使得定性性质和定量性质均可被验证.此外,PLSMC可以有效地缓解模型检测工具中容易发生的状态空间爆炸问题.最后,利用PLSMC对铁路公路交叉道口护栏控制系统的安全性质和周期性性质进行验证.实验结果表明,PPTL符号模型检测工具扩充了NuSMV系统的验证能力,使得时间敏感、并发性和周期性等实时性质可以被描述和验证.

关键词：符号模型检测;时序逻辑;模型检测器;嵌入式系统验证

基金资助：国家自然科学基金(61133001, 61202038, 61272117, 61272118, 61322202); 国家重点基础研究发展计划(973) (2010 CB328102)