| 摘要: |
| 现有模型检测工具的形式化规范语言,如计算树逻辑(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系统的验证能力,使得时间敏感、并发性和周期性等实时性质可以被描述和验证. |
| 关键词: 符号模型检测 时序逻辑 模型检测器 嵌入式系统验证 |
| DOI：10.13328/j.cnki.jos.004689 |
| 分类号: |
| 基金项目:国家自然科学基金(61133001, 61202038, 61272117, 61272118, 61322202); 国家重点基础研究发展计划(973) (2010 CB328102) |
|
| Symbolic Model Checker for Propositional Projection Temporal Logic |
|
PANG Tao1,2, DUAN Zhen-Hua1,2, LIU Xiao-Fang1,2
|
|
1.Institute of Computing Theory and Technology, Xidian University, Xi'an 710071, China;2.State Key Laboratory of Integrated Services Networks (Xidian University), Xi'an 710071, China
|
| 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. |
| Key words: symbolic model checking temporal logic model checker embedded system verification |
