形式验证死锁自由性证明:liveness 类属性证明死锁自由的套路、fairness 约束写法与证明分解策略
更新时间:2026-10-06。死锁是并发系统最阴的缺陷:仿真里它表现为「跑着跑着不动了」,但跑得不够久、激励没踩中仲裁序列就永远漏掉;形式上它又恰好是最难证的那类属性——「请求最终一定被响应」是一个 liveness(活性)属性,要求证明器排除「无限循环永不前进」的所有可能执行,这比 safety(安全性,「坏事永不发生」)难一个量级。很多团队的形式验证计划里,死锁自由一栏常年写着「unreachable / 不收敛」,最后不了了之退回仿真兜底。本站的 形式 liveness 与 fairness 约束 讲了 fairness 的基础,SVA liveness 与 safety 属性 讲了属性分类;本文把「证明死锁自由」这件具体的事拆成可操作的全流程:属性怎么表述、fairness 怎么加、证明不收敛时怎么拆。
本文要回答的问题
- 死锁自由为什么是 liveness 属性?它和安全属性在证明机制上差在哪?
- 「请求最终被响应」有哪几种形式化表述,强 eventual 和 weak 表述各证明什么?
- fairness 约束解决什么问题?写过头的 fairness 为什么会证出假阳性?
- 大系统死锁证明不收敛时,有哪些标准的证明分解套路?
- 死锁自由证明的结果怎么折算进签出证据?bounded 结论意味着什么?
一、liveness 与 safety:两种属性的证明机制差异
先把属性分类钉死,因为它决定证明策略。safety 属性(「永不进入坏状态」)的证明是可达性分析:证明器检查从初始状态出发的有限深度内坏状态是否可达,配合归纳法可以外推到任意深度——形式 K 归纳不变量证明 就是这条线。liveness 属性(「好事最终会发生」)的证明本质不同:它要求排除无限不前进的公平执行,证明器要在状态转移图里寻找「无限循环且永不满足目标」的闭合路径(lasso,套索形反例)。这套搜索在 BMC 框架里没有天然的深度边界——循环可以是任意长度,所以 liveness 证明要么靠专门的 liveness-to-safety 变换(如 k-liveness、liveness 转 ranking function),要么靠带套索检测的模型检查算法,成本天然高于同规模 safety。
落到死锁自由上,这个差异的实际含义是:别指望「加深 BMC 深度」能证死锁自由——深度 200 没找到死锁,只说明 200 拍内没有,套索可能在 300 拍处闭合。正确的入口是先选对表述和证明引擎,再谈深度。
主流形式工具对 liveness 的支持形态值得了解,因为它直接决定工作流。一类工具内置 liveness 属性类型(属性声明时标注 eventually 语义),引擎自动选 liveness-to-safety 变换;另一类要求用户手工做变换——引入一个「观测标志位」,把「请求后 ack 终将到来」改写成「请求发生时置标志、ack 到来时清标志、标志置位期间某个 ranking 度量严格递减」,把 liveness 拆成若干 safety 小属性。手工变换的额外好处是强制你想清楚「系统凭什么前进」——ranking 度量(剩余信用、队列占用、仲裁轮转位置)往往就是死锁自由性证明的核心洞察本身,把它显式写出来,证明过程从黑盒搜索变成有方向的论证,调试不收敛时也知道该往哪里加不变量。
二、死锁自由的表述选型:从资源级到系统级
「没有死锁」是一句口语,形式化时必须落成具体属性。表述按粒度分三档,证明难度递增。
| 表述档位 | 属性形态 | 证明什么 | 典型适用 |
|---|---|---|---|
| 响应性 | req 发生蕴含 eventually ack | 单个请求不被饿死 | 仲裁器、桥、接口协议 |
| 前进性 | 系统蕴含 eventually 回到空态 | 全局不会卡死在某配置 | 互连网络、DMA 调度 |
| 无饥饿 | 持续请求蕴含 eventually 服务 | 公平性下的逐请求保证 | 共享资源调度器 |
响应性表述是最常用的入口:assert property (req |-> strong (##[1:$] ack)) 或工具专属的 eventually 形式(SVA 的 strong sequence 语义见 SVA strong sequence 与 liveness)。它的证明往往还能再降一档:如果协议本身有响应延迟上界(比如仲裁器最多等 N 个请求),liveness 可以直接改写成 bounded safety——「ack 在 N 拍内必到」,性质从「排除套索」退化成「深度 N 的可达性」,证明成本骤降。能转成 bounded safety 的 liveness 一律转,这是死锁证明的第一优化。只有协议确实无上界(credit 依赖对端行为)时,才需要真 liveness 证法。
前进性表述适合全局死锁:「从任何可达状态,系统最终能回到所有通道空闲、所有队列空的状态」。它不求逐请求响应,只求系统不被整体卡死——片上网络、多层互连的死锁自由证明多用这一档,因为逐通道响应性在乱序路由下根本无法局部表述。无饥饿表述最强也最难,通常只在 fairness 约束齐备后尝试,属于第三节的领地。
表述选型时还有一个常被忽略的对应关系:三档表述分别对应死锁的三种成因。响应性失败暴露的是「单点饿死」——某个请求者被仲裁器持续绕过;前进性失败暴露的是「循环等待」——A 等 B、B 等 C、C 等 A 的资源环;无饥饿失败暴露的是「活锁边缘」——系统没卡死但某方永远抢不到。死锁注入测试(第三节)构造已知死锁时,按这三种成因各埋一种,能同时检验表述选型和 fairness 强度是否覆盖了全部失败模式——只埋循环等待一种,可能让「响应性表述对单点饿死失明」的漏洞混过去。这个「按成因埋雷」的思路和 形式仲裁器属性证明 里的故障模型分类是同一个方法论:证明能力的检验集要和缺陷的成因分类对齐。
三、fairness 约束:给「最终」一个公平的舞台
真 liveness 证明几乎离不开 fairness 约束,原因是物理系统里的很多「永不前进」执行在现实中根本不发生。经典例子:请求-响应环路里,「对端永远不释放 credit」是一条合法的无限执行,证明器若不排除它,任何响应性属性都证不出来。fairness 约束就是把这些「不公平的无限执行」显式排除的 assume:「credit 释放事件无限多次发生」「仲裁器不会无限期绕过任一请求者」。写法上它通常是无条件的 liveness assume(assume eventually 某事件),而不是普通的 safety assume。形式 liveness 与 fairness 约束 给了语法细节,这里聚焦两条工程红线。
红线一,fairness 约束必须有物理依据。每条 fairness assume 都要能回答「现实中什么机制保证这件事」——「对端终会释放 credit」的依据是对端模块自身的前进性属性,这就引出了第四节的分层证明;答不出依据的 fairness 是空中楼阁,证出来的死锁自由也是假的。红线二,fairness 过强等于把死锁假设掉。极端例子:直接 assume「每个请求 eventually 被响应」,那死锁自由属性同义反复、秒证通过、什么都没验证。判别 fairness 是否过强的实用测试是「死锁注入测试」:往设计里故意埋一个已知死锁(比如改一行仲裁优先级逻辑制造循环等待),带全套 fairness 约束跑证明——属性应该失败、反例应该展示这个死锁;如果照样通过,说明 fairness 把真死锁也假设掉了,必须逐条收紧。这个反向验证和 断言 assume 与 cover 的形式分工 的 assume 审计是同一种纪律。
四、证明分解:把不收敛的大证明拆成能收敛的小证明
系统级死锁证明直接跑常常不收敛,标准对策是分解,三个套路按序尝试。
套路一,bounded 化降级:先尝试把 liveness 改成 bounded safety——分析协议找出(或人为约束出)响应上界,证「N 拍内必响应」。上界找不到时,退而求其次证「深度 D 内无死锁」的 bounded 结论,并在签出证据里如实标注深度论证,方法同 形式验证有界证明深度。
套路二,组件级 assume-guarantee 分解:全局死锁 = 各组件局部前进性加组件间无循环等待。对组件 A 证「在 B 终会响应的假设下,A 终会前进」,对 B 证对称属性——然后用组合论证闭合全局。这套 形式 assume-guarantee 分解 方法的关键纪律是防止循环依赖:A 的 assume 用 B 的 guarantee、B 的 assume 又用 A 的 guarantee,构成循环论证。防法是建立组件的依赖序(拓扑排序),只许下游 assume 上游已证的 guarantee。互连网络里这个依赖序对应「无环通道依赖图」——这正是经典的 deadlock-free routing 理论(无圈通道依赖)在形式流程里的化身。
套路三,抽象降维:数据宽度、队列深度、ID 数量按 形式抽象建模 缩减(数据无关性把 32 位数据抽象成 token、队列深度裁到能暴露循环等待的最小值 2 或 3),死锁本质是资源竞争结构问题,与数据值无关的属性在抽象模型上证明后,结论可回挂原设计——但抽象有效性论证要随证明一起存档。
三个套路有一个共同的前置动作容易被跳过:先把「不收敛」归因。不收敛有三种截然不同的病因——状态空间太大(该抽象)、深度太深(该 bounded 化或 形式验证复位抽象)、证明缺关键不变量(该补 helper lemma 而不是分解)。病因不查明就上分解,常常把一个大而不收敛的证明拆成五个小而不收敛的证明。归因手段是看证明器的中间报告:状态爆炸曲线陡是空间问题、深度线性爬而不收敛是深度问题、反例反复出现在同一类「不该发生但约束没拦住」的状态里是缺不变量。补不变量这条路尤其值得先尝试——一个对的 helper lemma(比如「通道依赖图无环时各队列占用和守恒」)常常让全局证明从几周不收敛变成几小时通过,成本远低于结构性分解。
三个套路的产出折算进签出证据时口径要清楚:bounded 结论标注深度与论证、assume-guarantee 结论附组件依赖序与每环的证明状态、抽象结论附有效性论证。形式证明状态报告解读 的报告格式里这些都该落字。死锁自由这类属性还要特别记录 fairness 约束清单——它本质上是证明成立的前提条件,前提变了结论就要重估,形式验证应用组合 的组合管理里 fairness 清单和复位抽象假设同属「证明前提登记」的范畴。最后一点运营经验:死锁类 bug 的仿真侧逃逸率本来就高(需要精确的多方等待序列),所以死锁自由的形式证明即使只做到 bounded 加分解,其价值也通常高于同成本的仿真回归——这是给形式验证计划排优先级时值得记住的排序依据。
这一篇在知识体系里的位置
本篇属 chip-design/verification 目录形式验证线的 liveness 深文,上承 形式 liveness 与 fairness 约束 与 形式验证基础,横向衔接 SVA liveness 与 safety 属性 的属性分类、SVA strong sequence 与 liveness 的表述语法、形式 K 归纳不变量证明 的 safety 侧方法,分解侧接 形式 assume-guarantee 分解 与 形式抽象建模,证据侧落在 形式验证有界证明深度 与 形式证明状态报告解读,应用范例参考 形式仲裁器属性证明。
总结
形式验证证明死锁自由的核心套路是「先认清它是 liveness、再分层降维」:liveness 要求排除套索形无限反例,BMC 加深只能证伪不能证明,必须走专门算法或降级;表述按响应性、前进性、无饥饿三档选型,协议有延迟上界时一律转成 bounded safety;真 liveness 离不开 fairness 约束,但每条 fairness 要有物理依据、且必须通过死锁注入测试防止「强到把死锁假设掉」;不收敛时按 bounded 化降级、组件依赖序上的 assume-guarantee 分解(严禁循环论证)、数据无关抽象三套路拆解,子证明独立收敛后组合闭合全局——死锁自由从「计划里常年 unreachable 的一栏」变成「有前提、有分解、有证据的可交付证明」,靠的就是这套套路。