于露
摘要:无论是计算机系统硬件设计还是软件设计,随着设计规模越来越复杂和庞大,会产生越来越多的设计缺陷。传统检测方法代价高,并且难以检测这些设计缺陷。有界模型检验是一种重要的形式化验证方法,可以大大提高检测、验证的效率。作为一种形式化方法构造系统的模拟运行过程,有界模型检验通过把有限状态机和线性时序逻辑验证规范否定形式编码成布尔可满足性实例,再由各种布尔可满足性工具来求解,以获得反例。由于有界模型检验使用深度优先搜索,它可以很快找到路径最短的反例。
关键词:有界模型检验;模型检验;SAT
中图分类号:TP311 文献标识码:A 文章编号:1009-3044(2017)35-0070-02
1 有界模型检验的概念
模型检测(model checking)是形式化验证方法的一种,它可以自动检测系统的模拟运行是否满足某些期望的规范。随着计算机系统越来越复杂,网络应用越来越普及和重要,通过模型检测技术来验证系统和网络的安全性和正确性的应用也逐渐增多。针对前期的OBDD(ordered binary decision diagram)技术的模型检测的不足,有界模型检测(bounded model checking,简称BMC)使用SAT(satisfiability)求解器来求解
需要验证的问题。BMC通过设置界限阈值k,可以有效地克服状态爆炸问题,并可以解决逻辑公式相对应的BDD(binary decision diagram)结构的存储空间、检测变量少等问题[1]。BMC有两个主要的优势:其优势之一是充分利用SAT(satisfiability)求解工具的特征,把BMC 问题编码成SAT实例,有效地使模型检验的变量数提升一个数量级以上;另一优势是BMC的求解过程向着不满足命题的方向发展,有利于得到长度最短、最简明的反例,方便设计者理解问题,找出原因。……