模型检测
自动验证技术
模型检测(model checking),是一种自动验证技术,由Clarke和Emerson以及Quelle和Sifakis提出,主要通过显式状态搜索或隐式不动点计算来验证有穷状态并发系统的模态/命题性质。
简介
由于模型检测可以自动执行,并能在系统不满足性质时提供反例路径,因此在工业界比演绎证明更受推崇。
尽管限制在有穷系统上是一个缺点,但模型检测可以应用于许多非常重要的系统,如硬件控制器和通信协议等有穷状态系统。很多情况下,可以把模型检测和各种抽象与归纳原则结合起来验证非有穷状态系统(如实时系统)。
应用
模型检测的基本思想是用状态迁移系统(S)表示系统的行为,用模态逻辑公式(F)描述系统的性质。这样“系统是否具有所期望的性质”就转化为数学问题“状态迁移系统S是否是公式F的一个模型”,用公式表示为S╞F。对有穷状态系统,这个问题是可判定的,即可以用计算机程序在有限时间内自动确定。
模型检测已被应用于计算机硬件、通信协议、控制系统、安全认证协议等方面的分析与验证中,取得了令人瞩目的成功,并从学术界辐射到了产业界。
参考资料
最新修订时间:2020-06-28 17:54
目录
概述
简介
应用
参考资料