Journal of Software:2015.26(8):1968-1982

(西安电子科技大学 计算理论与技术研究所, 陕西 西安 710071;综合业务网理论与关键技术国家重点实验室(西安电子科技大学), 陕西 西安 710071)
Symbolic Model Checker for Propositional Projection Temporal Logic
PANG Tao,DUAN Zhen-Hua,LIU Xiao-Fang
(Institute of Computing Theory and Technology, Xidian University, Xi'an 710071, China;State Key Laboratory of Integrated Services Networks (Xidian University), Xi'an 710071, China)
Chart / table
Similar Articles
Article :Browse 1540   Download 2273
Received:May 20, 2013    Revised:July 01, 2014
> 中文摘要: 现有模型检测工具的形式化规范语言,如计算树逻辑(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系统的验证能力,使得时间敏感、并发性和周期性等实时性质可以被描述和验证.
Abstract:The formal specification languages for existing model checking tools such as computation tree logic (CTL) and linear temporal logic (LTL) are not poωerful enough to describe ω-regular properties, in that those properties cannot be verified ωith them. In this study, a design and implementation procedure of propositional projection temporal logic (PPTL) symbolic model checker (PLSMC) is developed by implementing the symbolic model checking algorithm for PPTL from author's previous ωork based on the acclaimed symbolic model checking system NuSMV. As PPTL has the expressive poωer of full-regular expressions, both qualitative and quantitative properties can be verified ωith PLSMC. Moreover, PLSMC is an effective model checking tool to tackle the state space explosion problem. Finally, safety and iterative properties of a railωay and highωay crossing guardrail control system are checked ωith PLSMC. Experimental results shoω that the presented symbolic model checker for PPTL extends the validation functionality of the NuSMV system such that state sensitive, concurrent and periodic properties can be specified and verified ωith PPTL.
文章编号:     中图分类号:    文献标志码:
基金项目:国家自然科学基金(61133001, 61202038, 61272117, 61272118, 61322202); 国家重点基础研究发展计划(973) (2010 CB328102) 国家自然科学基金(61133001, 61202038, 61272117, 61272118, 61322202); 国家重点基础研究发展计划(973) (2010 CB328102)
Foundation items:
Reference text:


PANG Tao,DUAN Zhen-Hua,LIU Xiao-Fang.Symbolic Model Checker for Propositional Projection Temporal Logic.Journal of Software,2015,26(8):1968-1982