基于一阶迁移系统的限界模型检测工具实现

基于布尔可满足性(SAT)的限界模型检测是一种高效的模型检测方法，它具有快速查错，反例最小化等特点，已经成为学术界和工业界关注的热点。近些年出现了很多集成限界模型检测算法的验证工具，如ITC-IRST、卡内基梅隆大学(CMU)等多家科研机构联合开发的NuSMV工具；加利福尼亚大学伯克莱分校(UC Berkeley)、科罗拉多大学博尔德分校(CU Boulder)联合开发的VIS工具等。因此目前对于限界模型检测方法的研究和相关工具的设计与开发具有重要而广泛的意义。在进行限界模型检测的建模过程中，不同的工具采用了自定义的建模语言。如经典工具SPIN采用的建模语言是Promela语言，NuSMV采用的是自定义的NuSMV语言。随着系统验证规模的不断增大，建模语言的特点将会直接影响到建模的效率。例如采用NuSMV语言去建立一个网络通信协议模型会显得比较复杂和耗时，应用NuSMV语言去描述一个简单的数据链路层网络协议ABP协议(Alternating Bit Protocol)就不如采用Promela语言去描述显得直观和自然。 为了简化在限界模型检测过程中模型的建立过程，本文给出了一种采用基于一阶迁移系统语言描述的模型建立方法，并在一阶迁移系统语言中实现了通道的功能，从而增强了描述能力。在此基础上完成了一个以基于插值和k步归纳限界验证算法为核心的模型检测工具(BMCF)。最后利用该工具对常见的互斥协议，简单数据传输协议的性质进行了分析与验证。结果表明，利用该工具对系统进行建模具有方便直观的特点，并借助实现的验证算法能高效的检验安全性质的正确性，如果性质不成立工具会给出反例提示。