吉林大学学报(工学版) ›› 2015, Vol. 45 ›› Issue (1): 245-251.doi: 10.13229/j.cnki.jdxbgxb201501036

• 论文 • 上一篇    下一篇

基于惰性切片的线性时态逻辑性质验证

黄宏涛1,王静2,叶海智1,黄少滨3   

  1. 1.河南师范大学 河南省教育信息工程技术研究中心,河南 新乡 453007;
    2.中国石化管道储运公司 新乡输油处信息中心,河南 新乡 453007;
    3. 哈尔滨工程大学 计算机科学与技术学院,哈尔滨 150001
  • 收稿日期:2013-05-14 出版日期:2015-02-01 发布日期:2015-02-01
  • 作者简介:黄宏涛(1980),男,副教授,博士.研究方向:模型检测.E-mail:huanghongtao@outlook.com
  • 基金资助:
    国家科技支撑计划项目(2012BAH08B02);河南省科技攻关计划项目(082400420250,112300410008);河南省教育厅科学技术研究重点项目(13A520508);河南师范大学博士科研启动基金项目(qd12107);河南师范大学青年科学基金项目(2013qk33).

Lazy slicing based method for verifying linear temporal logic property

HUANG Hong-tao1,WANG Jing2,YE Hai-zhi1,HUANG Shao-bin3   

  1. 1.Engineering Research Center for Education Information, Henan Normal University, Xinxiang 453007, China;
    2.Information Center of Xinxiang Oil Transportation Department, Sinopec Pipeline Storage
    Transportation Company, Xinxiang 453007, China;
    3.College of Computer Science and Technology, Harbin Engineering University, Harbin 150001, China
  • Received:2013-05-14 Online:2015-02-01 Published:2015-02-01

摘要: 惰性切片是一种有效的状态空间缩减方法,但是它无法直接判定一个模型是否满足所期望的线性时间性质。针对该问题,提出了一种基于惰性切片的线性时态逻辑公式验证方法。该方法首先构造给定线性时态逻辑公式的否定Büchi自动机与系统模型的乘积自动机,然后使用惰性切片算法在该乘积自动机上以惰性方式搜索可接受迹,从而把线性时间性质验证问题转换为通过可达性分析搜索可接受状态的不变性检测过程。实验结果证明,基于惰性切片的线性时态逻辑公式验证算法在不损失验证结果正确性的前提下使惰性切片算法具备了验证线性时间性质的能力,同时也有效提高了LTL模型检测方法的可扩展性。

Abstract: Lazy slicing is an effective state-space reduction method, but it can not directly determine whether a model satisfies the expected linear property. A lazy slicing based method is proposed to solve this problem. First, it constructs a negation Büchi automaton for given linear temporal logic formula and a product automaton of the system model. Then it searches for an acceptable trace on this product automaton lazily. Thus, the problem of verifying a linear time property is converted into the problem of invariance validation, which makes it possible to search the acceptable state by reachability analysis. Experiment results show that this lazy slicing based algorithm not only makes lazy slicing be able to verify linear time property, but also remarkably improves the scalability of LTL model checking.

中图分类号: 

  • TP311.5
[1] 李勇, 黄志球, 王勇, 房丙午. 基于多源数据的跨项目软件缺陷预测[J]. 吉林大学学报(工学版), 2016, 46(6): 2034-2041.
[2] 王志坚, 胡玉平, 陈章. 构件系统结构的Petri网方法描述[J]. 吉林大学学报(工学版), 2012, 42(增刊1): 304-308.
[3] 赵倩1,2,王慧强2,冯光升2,赵靖2. 基于Pi演算的软件可信性度量方法[J]. 吉林大学学报(工学版), 2011, 41(6): 1684-1689.
[4] 王金波,赵光恒,陈蔚薇 . 基于任务剖面关键度划分的嵌入式
软件可靠性增长模型
[J]. 吉林大学学报(工学版), 2009, 39(02): 436-0439.
[5] 范永开,林君,孙天泽,随阳轶 . 基于需求驱动的虚拟仪器软件自动生成构架[J]. 吉林大学学报(工学版), 2007, 37(03): 606-0610.
[6] 潘洪军,,孙吉贵. 面向对象代数Petri网[J]. 吉林大学学报(工学版), 2006, 36(03): 382-0386.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!