模型检验是一种自动化的形式验证方法,用于判定系统的数学模型是否满足以形式化方式表述的要求。模型描述系统可能的状态及状态之间的转移;要求则规定哪些状态、事件序列或分支可能性是可接受的。模型检验工具分析这些可能性,并报告要求是否成立。若不成立,工具通常会给出反例,说明要求为何未得到满足。
对于行为取决于并发、非确定性或组件间复杂交互的系统,这种方法尤为重要,例如通信协议、数字电路、控制软件和分布式服务。测试只检查选定的执行过程,而穷尽式模型检验能够确认某个性质对模型所表示的每一种执行过程都成立。不过,这一保证仍以模型、性质以及有关环境的各项假设准确无误为前提。
模型检验最初是为有限状态系统开发的,如今已涵盖符号表示、基于可满足性的判定过程、抽象,以及适用于时间模型、概率模型和部分无限状态模型的方法。其实践中的核心挑战在于:简洁的系统描述也可能产生数量极其庞大的状态。
历史发展与理论基础
模型检测源于将反应式系统推理自动化的探索。反应式系统持续与环境交互,而不是仅仅计算出结果后便终止。对于这类系统,正确性涉及事件在时间上的先后关系:请求最终应当得到响应,两个进程绝不能同时进入受保护区域,通信协议应能在发生容许范围内的故障后恢复。传统的输入—输出规约无法直接表达所有这些要求。
1977 年,阿米尔·普努埃利提出使用时序逻辑来描述程序的性质。时序算子使人们能够表达“始终”和“最终”等概念,而不必为每个事件指定数值化的时间。这一进展提供了一种非常适合描述非终止行为和并发行为的规约语言,也将程序验证与数理逻辑及计算语义学领域的既有研究联系起来。
模型检测的奠基性研究于 20 世纪 80 年代初由不同研究团队独立开展。埃德蒙·M. 克拉克与 E. 艾伦·爱默生开发了针对有限状态模型检查分支时间规约的算法;与此同时,约瑟夫·西法基斯与让-皮埃尔·奎耶在法国提出了密切相关的方法。其中的关键转变,是将验证视为迁移结构上的算法问题,而不再要求为每个系统分别手工构造证明。克拉克、爱默生和西法基斯因其在模型检测发展中的贡献,共同获得了 2007 年图灵奖。
早期实现显式表示状态和迁移,因此能够处理的模型规模受到限制。20 世纪 80 年代末前后,符号化技术的采用大幅拓展了模型检测的能力。肯尼斯·麦克米伦在符号模型检测方面的研究及其 SMV 系统表明,对于许多硬件设计,布尔表示能够以远比显式枚举紧凑的方式描述状态集合与迁移关系。这项成就并非彻底消除了状态空间问题,而是使一批原本难以处理的大型系统变得可以处理。
在 20 世纪 90 年代和 21 世纪头十年,若干相辅相成的研究方向拓宽了这一领域。SPIN 推动了通信进程的验证;时间自动机工具为实时系统提供了支持;基于可满足性的技术则将验证与效能日益提升的布尔求解器联系起来。软件模型检测引入了抽象与自动化精化。微软的 SLAM 项目和 Static Driver Verifier 展示了如何将这些思想应用于设备驱动程序代码中与接口使用有关的性质。由此形成的领域涵盖了一系列技术,它们围绕着同一个任务:判定模型所描述的行为是否满足明确给定的规约。
迁移系统、模型与验证断言
一种常用的数学基础是 Kripke 结构,可写为
其中, 是状态集合, 是初始状态集合, 是迁移关系, 则为每个状态指定在该状态下成立的原子命题。一个状态可以包含寄存器的值、程序执行位置、队列内容或多个进程的状态。一次迁移表示模型中的一个执行步骤。许多定义要求每个状态都有后继状态;在这种情况下,可以用自环表示终止。
验证的基本问题是判断是否有
其中, 是要求满足的性质。通常,这意味着在选定的语义下,该性质从每个初始状态出发都成立。模型可以直接构造为有限状态机,也可以由建模语言生成,或由验证工具的前端从源代码中提取。模型的状态变量不必与实现中的变量一一对应:无关数据可以省略,而环境可能作出的选择则可以显式加入模型。
非确定性是这种表示方式的核心。如果一个状态有多条出边迁移,它们可以表示不同的输入、调度选择、硬件行为,或有意不作规定的实现决策。在并发计算中,交错模型通常通过每一步只允许一个进程向前执行来表示执行过程。这会揭示依赖于调度的行为,包括竞态条件或死锁。这种模型能否准确表示某个实现,还取决于对原子性及其内存模型所作的假设。
例如,互斥模型可以将每个进程的状态记录为空闲、等待或处于临界区。安全性要求是:任何可达状态都不能让两个进程同时处于临界区。模型还必须描述进程如何请求进入临界区、共享变量如何变化,以及调度器可以采取哪些操作。对于最终能够进入临界区之类的活性要求,则需要格外谨慎:即使加锁协议本身正确,如果调度器始终不让某个等待中的进程运行,该进程也可能无法取得进展。
模型检验证明的是关于模型的事实,而不是对实际物理系统或软件制品作出无条件的断言。一个具有有限容量的队列模型,并不能直接说明队列长度超出所选上限后的情况。一个排除了消息重复的网络模型,也无法确立系统在消息重复情况下的正确性。因此,验证断言应当同时包含所验证的性质、建模采用的语义以及相关假设。明确这些限定条件,才能区分数学上成立的结果,以及该结果实际能够支持的工程论断。
时序规约、安全性与活性
许多模型检测要求用线性时序逻辑(LTL)或计算树逻辑(CTL)来表达。LTL 描述沿执行路径的行为。其常用算子包括表示“下一步”的 、表示“最终”的 、表示“始终”的 ,以及表示“直到”的 。例如,
表示每个请求最终都会获得授权。在系统验证通常采用的全称解释下,模型的每一次执行都必须满足这一公式。
CTL 显式地对各种可能的未来路径进行量化。路径量词 和 分别表示“对所有路径”和“存在一条路径”,并与时序算子组合使用。因此, 要求每条路径上的每个可达点都满足安全条件,而 则询问是否能够到达错误状态。公式 表示,从每个可达状态出发,始终还存在某条通向复位的路径。这种分支上的可能性,不同于断言每次执行最终都会复位。
安全性与活性之间的区分十分重要。安全性性质排除某种不良事件或状态,其违反情况可以通过有限的执行前缀来证明:一旦两个进程进入同一个受保护区域,互斥要求就已经被违反。活性性质则要求某种期望的事件最终发生。活性性质的违反通常涉及无限执行,因为仅凭有限的延迟无法确定某个事件永远不会发生。有些规约同时包含这两类性质,而有界响应要求通常可以通过添加计数器或时钟来表示为安全性性质。
公平性假设限定哪些无限执行应被纳入考虑。弱公平性通常要求:如果某个动作从某一时刻起一直处于使能状态,那么它最终必须发生;强公平性通常针对那些无限多次处于使能状态的动作。这类假设可以排除无限期忽略某个进程的调度方式。然而,实际调度器并不天然具备公平性,将公平性加入规约会改变所证明的断言。公平性假设不能掩盖确实可能导致系统无法继续推进的机制。
即使公式十分精确,也仍可能表达了错误的要求。由于请求根本不可达,关于响应的蕴含式可能空泛成立。如果性质没有跟踪标识或参数,也可能无法区分正确响应与无关事件。因此,规约评估还包括可达性检查、见证检查,以及通过刻意构造的错误模型测试该要求是否确实可能被违反。时序逻辑赋予要求以数学上的精确性,但选择恰当的命题和量词仍是一项实质性的建模工作。
显式状态探索与反例
显式状态模型检测存储或生成各个状态,并探索状态之间的迁移。对于可达性性质,基本流程是从初始状态出发,反复计算后继状态,并记录已访问的状态。如果到达某个违反该性质的状态,就重建一条从初始状态通往该违规状态的路径。如果探索结束时仍未找到这样的状态,则该性质在整个可达状态图中成立。
搜索策略既影响资源消耗,也影响诊断输出。在所有迁移代价相同的情况下,广度优先搜索能找到迁移次数最少的反例,但其搜索前沿可能占用大量内存。深度优先搜索通常只需维护较小的活动搜索栈,但已访问状态集合的存储仍可能占据大部分内存。状态表示通常采用紧凑编码和哈希表。精确存储能够为穷尽性结论提供依据;而有意丢弃信息或容许哈希冲突的方案虽然可以减少内存消耗,却可能遗漏状态。
对于线性时序逻辑(LTL),一种核心方法是将待验证性质的否定转换为一个自动机,使其恰好接受所有违反该性质的执行。检测器将这个自动机与系统模型组合起来,判断所得乘积是否存在一条被接受的无限路径。在有限图上,这样的路径可以表示为一段有限前缀,后接一个不断重复的环,通常称为套索。基于嵌套搜索或强连通分量的算法可以检测出相关的环。展示出的套索能够说明某项必须满足的要求为何会永远得不到满足。
SPIN 是一款著名的显式状态验证器,由杰拉德·J. 霍尔兹曼(Gerard J. Holzmann)自 20 世纪 80 年代起开发。它使用的 Promela 语言可描述相互通信的进程、通道和非确定性选择。模型无需复现每一项实现细节,就能表达异步消息传递和共享状态交互。随后可以回放反例轨迹,展示进程的执行步骤和变量值的变化。这种诊断作用十分重要,因为并发错误往往难以通过常规运行复现。
其主要局限是状态空间爆炸。如果 个组件各有 种可能的局部状态,那么在尚未计入额外的共享数据或通信缓冲区之前,组合系统就可能拥有多达 种状态组合。许多组合可能不可达,但即使只是其中可达的部分,也可能极为庞大。困难并不只在于轨迹过长:大量短小且相互独立的选择也会形成巨大的分支空间。
因此,显式方法高度依赖约简、紧凑存储以及精心选取的模型。当状态生成的开销较低、反例相对较浅,或者尽管完整乘积空间很大、可达图却仍在可处理范围内时,这类方法依然尤为有效。
符号表示与基于可满足性的方法
符号模型检测用逻辑表达式表示状态集合和迁移关系,而不是逐一列举所有状态。对于布尔状态变量为 的模型,公式 描述初始状态,公式 描述到下一状态变量 的迁移。随后,可以通过反复加入以符号形式表示的后继状态集合来计算可达状态:
在统一重命名变量后,当不再有新状态加入时,迭代便停止。如果最终得到的可达状态集合不包含任何坏状态,则安全性质成立。
二叉决策图(BDD)是布尔函数的一种图表示。约简有序 BDD 共享等价的子函数,并消除冗余测试,有时能够紧凑地表示包含天文数字般众多状态的集合。然而,其规模对变量顺序和所表示函数的结构极为敏感。有些函数无论采用何种变量顺序,都需要指数规模的 BDD。符号表示改变了实际计算中的瓶颈,但并不保证表示一定紧凑。
有界模型检测采用另一种方法。为了寻找 次迁移以内的安全性质违例,它会构造如下形式的公式:
其中, 描述坏状态。布尔可满足性问题求解器判定该公式是否存在满足赋值。这样的赋值会给出一个具体的反例。不可满足的结果可以排除该界限内的违例,但仅凭这一结果无法证明无界安全性。要保证完备性,需要足够大的界限,或另行给出证明论证。
现代算法还会寻找安全性的归纳论证。归纳不变式包含所有初始状态,在每次迁移后均保持成立,并排除所有坏状态。Aaron Bradley 于 2011 年提出的 IC3 算法以增量方式构造支持这种论证的子句;相关实现通常称为性质导向可达性分析。与基本的有界探索不同,这些算法无需显式构造整个可达状态集合,就能证明有限状态系统的无界性质。
可满足性模理论(SMT)将算术、数组和位向量等理论引入可满足性求解。这使验证器能够保留有用的结构,而不必立即将每个运算都转换为布尔门。例如,可以用固定位宽的位向量对机器算术建模,从而保留整数溢出行为。理论的选择既影响语义的准确性,也影响求解器的性能,尤其是在涉及非线性算术、量词和多种理论组合时。
抽象、精化与组合式验证
抽象用一个更简单的系统替代详细系统,同时保留验证所选性质所需的信息。一种常见的安全性验证策略是过近似:抽象模型涵盖所有具体行为,但也可能包含额外的行为。如果没有任何抽象行为能够到达错误状态,那么具体行为也不可能到达错误状态。然而,如果在抽象层面发现了错误,它可能是伪错误——它源于信息丢失,而非实际执行中可能出现的缺陷。
谓词抽象用一组选定逻辑谓词的真值来表示程序状态。例如,模型不必精确跟踪某个整数的值,而可以只保留 、 或 是否成立的信息。这可以将无限的具体取值集合转化为有限的抽象状态集合。抽象迁移关系必须保守地涵盖具体迁移,通常需要借助定理证明或 SMT 查询来构建。增加谓词可以提高精度,但也会扩大抽象状态空间,增加推理成本。
反例引导的抽象精化(CEGAR)于 2000 年前后发展起来,能够自动决定应补充哪些信息以提高精度。它从一个粗略的抽象开始,检测目标性质。如果检测器返回反例,就通过可行性分析判断这条抽象轨迹是否对应某次具体执行。可行的轨迹表明确实违反了目标性质;不可行的轨迹则为精化抽象提供信息。这一过程不断重复,直到证明目标性质成立、发现具体错误,或耗尽资源。
这种方法与抽象解释密切相关,后者是对程序语义进行可靠近似的框架。两者有很大程度的重叠,但通常侧重不同的计算模式:模型检测方法可能更关注时序性质和反例驱动的搜索,而抽象解释器通常通过不动点迭代来计算近似不变式。混合工具会同时运用这两种思路。对于不加限制的程序,精化过程并不保证终止;这反映了一般验证问题的不可判定性,而不只是实现上的不足。
其他约简方法利用的是结构,而非数据抽象。当独立动作的不同执行顺序不会影响目标性质时,偏序约简可以避免探索所有这些顺序。其正确性取决于有关独立性、可见性和环的条件;随意舍弃某些调度是不可靠的。对称约简则将可互换组件(例如相同的进程)经过置换后彼此等价的状态视为同一状态。互模拟及相关等价关系可以为用更小的迁移系统替代原系统提供依据,同时保留特定类别的逻辑性质。
组合式验证通过对组件所处环境的假设,以及组件对自身行为的保证,来验证各个组件。这可以避免构建完整的全局乘积系统。其难点在于,不借助循环论证,确立各组件确实满足彼此的假设。因此,抽象、约简和分解不只是提升性能的技巧:每一种方法都需要给出性质保持的论证,将较小的验证问题与原始断言联系起来。
时间模型、概率模型及其他扩展模型
普通迁移系统描述事件可能发生的先后顺序,但本身并不区分一毫秒的延迟与一小时的延迟。实时验证显式引入了定量时间。时间自动机将离散的控制位置与实值时钟相结合;这些时钟以相同速率推进,并可在迁移时接受条件检查或重置。守卫条件限制迁移何时可以发生,而位置不变式则可以限制系统在某个位置停留的时间。
尽管时钟的取值有无限多个,标准时间自动机的可达性问题仍可通过有限抽象来判定。区域构造将时钟赋值分组,同一组中的赋值对于模型所使用的比较而言是等价的。实际工具通常使用差分约束矩阵来操作时钟区间集,即由时钟差分约束描述的赋值集合。UPPAAL 是支持此类验证的一个知名工具环境。典型的查询包括:控制器是否可能错过截止期限,或者定时活动之间是否可能出现不安全的时间重叠。
概率模型检测引入了可用数值刻画的不确定性。马尔可夫链为后继状态分配概率,从而能够回答诸如最终发生故障的概率是多少之类的问题。马尔可夫决策过程则将概率迁移与非确定性选择相结合。验证通常需要在所有允许的调度器中计算最小概率和最大概率。当不应为环境选择或控制决策任意指定概率时,这一区分就十分重要。
对于有限离散时间马尔可夫链,可达概率满足如下形式的方程:
同时还需为目标状态以及无法到达目标的状态设置适当的边界条件。奖励可以表示累计成本、能耗或已经历的步数。连续时间马尔可夫链则使用迁移速率,支持分析事件是否在某个给定时间区间内发生等问题。PRISM 是一种广泛使用的工具,支持多种此类概率模型和性质描述语言。
数值结果带来了纯布尔可达性分析中不存在的精度问题。迭代求解器需要收敛判据,而不严谨的停止规则可能导致缺乏依据的误差估计。统计模型检测采取另一种方法:对执行进行采样,并运用统计估计或假设检验。它能够处理规模过大、无法进行穷尽数值分析的模型,但其结论依赖于采样假设以及所声明的置信水平或误差界。
表达能力更强的系统也会遇到更难突破的限制。一般混合系统将离散控制与连续演化的变量相结合,针对这类系统的许多验证问题都是不可判定的。参数化系统研究的是任意数量进程的情况,而非某个固定实例。安全性质可能需要同时比较多次执行,信息流要求就是如此。这些扩展需要专门的抽象、逻辑框架或受限的模型类别,而不能依靠单一的通用检测过程。
复杂性、可判定性与可信保证的局限
模型检验的开销既取决于系统的表示方式,也取决于规约语言。对于显式表示的有限图,普通可达性分析的时间复杂度与状态数和迁移数之和成线性关系。CTL 模型检验同样可以在与图规模和公式规模的乘积成线性关系的时间内完成。这些界限很有用,但并不意味着验证的成本低廉:对系统的简洁描述可能展开为一个规模呈指数级增长的图。
LTL 检验带来了另一种权衡。标准的基于自动机的构造,其规模可能随公式长度呈指数增长;但对于固定的性质,检验时间仍可与显式表示的系统规模成线性关系。将系统和公式都作为输入的 LTL 模型检验问题是 PSPACE 完全的。计算复杂性中的相关结果区分了这种增长与具体实现效率低下所造成的开销。更好的编码方式和搜索策略可以显著改善实际性能,却无法消除最坏情况下固有的计算困难。
无限状态模型不仅带来高复杂性,还会引入不可判定性。具有无界整数、不受限制的动态内存分配或任意计算能力的程序,可以编码与停机问题有关的问题。对于不受限制的程序,不存在一种算法,能够始终判定所有非平凡的验证问题。尽管如此,某些特定的无限状态模型类别仍有实用的判定过程。下推系统可以表示具有无界调用栈的递归控制,而某些特定的算术模型或良结构模型则支持其他受限形式的分析。
因此,必须将资源限制与逻辑结论区分开来。“已验证”意味着某个可靠的过程在其假设成立的前提下,确立了所述性质。“未发现反例”则可能只是意味着有界搜索已经完成、已达到时间限制,或者近似探索仅检查了部分状态空间。超时并不能证明系统正确,有界查询不可满足也不自动构成无界情形下的证明。工具报告需要区分这些结果。
检验器的实现也是可信保证边界的一部分。解析器、语义转换、归约、求解器或反例重构中的错误,都可能使结果失效。证明证书和可独立检查的不变式,可以减少对庞大验证引擎的依赖。例如,检验器无需重复原先的搜索,就可以核验所提出的不变式是否包含初始状态、对迁移封闭,并排除错误状态。
最后,穷尽式验证无法弥补需求本身的错误。系统可能满足所有已检查的性质,却仍未履行某项遗漏的要求。同样,模型也可能遗漏某种物理故障、实现层面的数据竞争或相关的算术细节。模型检验能够使某个特定的逻辑断言获得格外有力的保证;但它并不能使这一断言成为对所有期望行为的完整描述。
工具、应用与工程实践
在硬件工程中,模型检测用于控制逻辑验证、协议检查,以及分析流水线、缓冲区与缓存一致性机制之间的交互。硬件很适合用固定位宽的寄存器和下一状态函数来表示,因此符号技术和基于可满足性的技术尤为适用。工业工作流程将这些方法与仿真及其他电子设计自动化手段结合使用。例如,某项性质可以规定:绝不会同时发出两个授权信号,或者在指定的环境约束下,请求最终会得到服务。
软件领域的应用要求程序语义与模型之间有更紧密的联系。CBMC 对 C 和 C++ 程序执行有界验证,包括与断言和内存安全相关的检查。CPAchecker 提供了一个框架,将可配置的程序分析、抽象和验证技术集成在一起。SPIN 侧重于对通信进程进行显式建模,而 nuXmv 则支持对有限状态系统及部分无限状态系统进行符号验证。这些工具面向不同的建模风格和性质类别,并不是同一种算法的可互换实现。
对于分布式计算,显式规约可以揭示由不常见的消息顺序、重试、崩溃和恢复步骤引发的故障。TLC 是与 TLA+ 配套的模型检测器,用于探索以基于动作和时序推理的语言编写的规约的有限实例。分布式共识模型可以对参与者数量和待处理消息数量设定上界,同时检查一致性以及允许的状态转移。这类探索能够在实现之前发现设计错误,但有限实例检查通过,并不意味着已经证明系统在参与者数量任意多时都正确。
工程工作流程通常首先选定要分析的行为和性质。随后,模型会明确队列容量上限、故障假设、原子操作和调度方式等事项。检查完成后,必须对反例进行分类:它们可能揭示系统缺陷、错误的需求或不准确的模型。如果同一种底层机制仍可能通过另一条执行路径出现,那么仅修正已报告的轨迹是不够的。修改后重新检查,有助于确定系统是否确实重新满足了目标性质。
模型检测是对测试和自动定理证明的补充,而非替代。测试在真实实现和环境中运行,但只能抽样考察行为。借助证明助手开展交互式证明,可以建立适用范围很广的定理,但通常需要大量人工指导。模型检测在两者之间占据了一个实用的位置:自动化程度高,能提供详细的诊断信息,但也受到模型类别和可用计算资源的限制。
在持续维护的项目中,规约和验证配置都是工程产物。协议、编译器假设、数据位宽或故障模型发生变化,都可能使先前的结果失效,即使性质的文本没有改变。将验证与受版本管理的模型及可重复执行的检查相结合,可以把验证结果与具体的设计和假设关联起来,而不是将其视为某个系统名称所代表的永久属性。