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

Symbolic Model Checker for Propositional Projection Temporal Logic

现有模型检测工具的形式化规范语言,如计算树逻辑(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系统的验证能力,使得时间敏感、并发性和周期性等实时性质可以被描述和验证.

The formal specification languages for existing model checking tools such as computation tree logic （CTL） and linear temporal logic （LTL） are not powerful enough to describe ω-regular properties, in that those properties cannot be verified with 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 work based on the acclaimed symbolic model checking system NuSMV. As PPTL has the expressive power of full-regular expressions, both qualitative and quantitative properties can be verified with PLSMC. Moreover, PLSMC is an effective model checking tool to tackle the state space explosion problem Finally, safety and iterative properties of a railway and highway crossing guardrail control system are checked with PLSMC. Experimental results show 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 with PPTL.