形式验证抽象建模:状态空间爆炸时用数据位宽缩减、计数器抽象与环境 nondet 换可证明深度
更新时间:2026-10-03。跑过形式验证(formal verification,用数学方法穷举所有可达状态来证明属性成立)的人都有一个共同经历:属性写好了,约束加好了,工具跑了十个小时,结论既不是 proven 也不是 falsified,而是状态空间太大、证明超时。站内的 形式验证入门 讲了 formal 的基本概念,形式验证有界证明深度 讲了 BMC 深度和证明的关系,FPV 约束方法论 讲了 assume 怎么写。这一篇往前走一步:当设计原样喂给工具根本证不动时,怎么通过抽象建模——数据位宽缩减、计数器抽象、环境 nondet 建模——把状态空间裁到工具能吃下的尺寸,同时保证抽象不引入假证明。这是形式验证从「玩具模块能证」走向「真实 IP 能签核」的分水岭技能。
本文要回答的问题
- 状态空间爆炸到底炸在哪里,为什么几个 32 位寄存器就能让工具跑不动?
- 数据位宽缩减怎么做,什么属性在缩减后仍然成立、什么属性会失真?
- 计数器、FIFO 深度这类「深度参数」怎么抽象,抽象后时序还对吗?
- 环境用 nondet(非确定性)加 assume 建模,约束过紧和过松各有什么后果?
- 怎么判断一次抽象是安全的(sound),抽象模型证出来的结论能不能带回原设计?
一、状态空间爆炸:算一笔让人死心的账
形式验证工具的工作是探索设计的所有可达状态。一个 DUT 的状态空间大小约等于它所有寄存器位数构成的组合数:n 个触发器就是 2 的 n 次方个状态。算一笔账:一个普普通通的控制模块,4 个 32 位数据寄存器、一个 8 位状态机、两个 16 位计数器,寄存器总位数是 4×32+8+2×16=168 位,状态空间上界是 2 的 168 次方,约 3.7×10 的 50 次方。即使工具每秒能处理 10 的 12 次方个状态(实际远达不到,SAT/SMT 求解不是线性扫状态),穷举一遍也要 10 的 38 次方秒——宇宙年龄是 10 的 17 次方秒量级。
当然,真实工具靠符号化表示和归纳证明,不需要逐状态枚举,很多时候几十万状态的模块也能收敛。但问题的敏感度极高:属性里一旦牵涉数据通路的具体数值比较、长计数序列、深 FIFO 的内容一致性,求解器要展开的 SAT 子句数量会随位宽和深度指数增长,运行时间从几分钟跳到几天,中间没有任何预警。工程上把这种现象叫「撞上状态空间墙」。
撞墙之后有四条路:换更强的引擎参数调优(治标)、加 helper assertion 做分步证明(assume guarantee 推理 讲过 assume/guarantee 分层)、把证明拆成子属性各个击破,以及本篇的主角——抽象建模:直接改模型,让模型变小。抽象是四条路里唯一能把问题规模数量级压下来的手段,也是唯一需要工程师对「抽象是否保真」负责的手段。
上图是本篇的总地图:原设计撞墙后,三类抽象分别从数据、深度、环境三个维度裁剪状态空间,最终汇聚成一个工具能收敛的抽象模型。下面三节逐一展开每一类怎么做、坑在哪。
二、数据位宽缩减:把 32 位裁成 2 位凭什么还对
数据位宽缩减(data width reduction)是收益最大、使用最广的抽象。思路一句话:如果属性的正确性不依赖数据的具体取值,只依赖数据的「相等/不相等」关系,那么数据位宽可以缩到能区分「需要区分的最多几个值」的最小宽度。
经典场景是验证数据通路的搬运正确性:比如一个 DMA 引擎把数据从源地址搬到目的地址,属性是「读出的数据等于写入的数据」。这个属性根本不在乎数据是 32 位还是 2 位——它只在乎「同一笔数据在路径上没有被篡改、没有和别的数据混淆」。如果把位宽缩到 2 位,同时环境里最多只有 3 笔在途数据,2 位(4 个不同值)足够让工具为每笔数据赋不同的「标签值」,任何混淆都会表现为标签不匹配的反例。学术界把这个思想叫做数据抽象的对称性论证,工程上有个更直白的名字:小标签法(tag method)。
具体做法分三步。第一步,把 DUT 的数据端口、内部数据寄存器、数据存储器的位宽参数化(好的 RTL 本来就该用 parameter 写位宽),抽象模型里把 DATA_WIDTH 从 32 改成 2 或 3。第二步,环境里产生的激励数据用 nondet 值而不是确定性序列,保证工具自己挑值——它会挑最能揭露 bug 的那些值,也就是让两笔数据相等或不等的临界组合。第三步,检查属性里所有涉及数据的表达式:凡是出现算术运算(加、乘、比较大小)的地方都要警惕,因为算术结果依赖位宽。
这就引出位宽缩减的适用判据。安全:相等性检查、数据搬移一致性、tag 跟踪、选择器路由(数据走 A 口还是 B 口)。失真:溢出行为(8 位和 32 位溢出点完全不同)、进位链相关的逻辑、饱和运算、CRC 校验(CRC 的值强烈依赖位宽和多项式)、任何带阈值比较的属性。判据一句话:属性语义在位宽缩放前后同构才安全。站内的 验证计数器边界 讲的边界场景,恰恰是位宽缩减最容易破坏的那类属性——计数器回绕行为在 4 位和 32 位上完全不同,这类属性不能缩减数据位宽,得用下一节的计数器抽象。
| 属性类型 | 位宽缩减是否安全 | 原因 |
|---|---|---|
| 读出等于写入(搬移一致) | 安全 | 只依赖相等关系 |
| tag 不混淆、路由正确 | 安全 | 只依赖可区分性 |
| 计数器回绕、溢出标志 | 不安全 | 语义直接绑定位宽 |
| CRC/校验和正确 | 不安全 | 值依赖位宽与多项式 |
| 大于阈值触发告警 | 需审查 | 阈值在新位宽下要重映射 |
三、计数器与深度抽象:把 1024 拍裁成 4 拍
第二堵墙来自「深度」:1024 深的 FIFO、要数 65536 拍的定时器、等 512 个时钟的超时逻辑。这类结构的属性往往是「数到 N 时发生某事」,而 N 巨大。工具有界模型检查(BMC)要展开 N 个周期才能触及目标状态,归纳证明里 N 又构成巨大的可达状态集——形式验证有界证明深度 里讲过证明深度和时序逻辑长度的关系,深度抽象就是直接改这个长度。
FIFO 深度抽象的做法:把 DEPTH 参数从 1024 改成 2 或 4。判据和位宽缩减类似——属性是否依赖具体深度。「写满后写使能被反压挡住」这个属性,深度 2 和深度 1024 的行为同构:只要写指针追上读指针就满。但「水位线超过 75% 触发中断」这种属性,75% 在新深度下要重新映射,映射不好就是假反例。FIFO 类设计的完整验证策略可以参考站内 验证异步 FIFO CDC,本文只强调深度参数化这一条抽象通道。
计数器抽象更讲究,因为计数器的状态本身就是属性关注的对象。标准技巧叫「抽象计数器」或「区间抽象」:不数具体值,只维护「当前值和目标值的关系」——未到、恰好到达、已超过。实现上有两种形态。一种是直接改 RTL 参数(超时阈值 512 改 4),适用于阈值是 parameter 的干净设计。另一种是写抽象替换模块(abstraction module):在 formal 环境里用 --replace 或 bind 把真计数器换成一个三态抽象状态机,再用 assume 约束抽象状态机和真计数器控制信号的对应关系(比如真计数器使能时抽象状态机单调推进)。第二种不动 RTL,适合第三方 IP 或网表级设计,但 assume 写错就引入假证明,责任全在验证工程师。
上图是计数器区间抽象的结构:真实计数器被 bind 替换成三态抽象状态机,assume 保证两者控制行为对应,属性只消费「未到/恰达/超过」三种关系。要点在图右下——属性本身必须能翻译成只依赖这三种关系的形式;如果属性写的是「第 100 拍到第 200 拍之间输出保持高」,区间抽象就不够用,得退回参数缩减或者用分段计数器。
四、环境 nondet 建模:把协议伙伴换成一组约束
第三堵墙不在 DUT 内部,在 DUT 外面。真实设计的输入来自另一个复杂模块:CPU 总线、对端协议栈、软件写的寄存器序列。仿真里这些由 testbench 或 VIP 驱动,形式验证里没有 testbench 的概念——所有输入默认是完全自由的(每个周期每个输入可以是任意值),这叫完全 nondet。完全自由会产生大量非法输入序列,属性在这些序列上立刻失败,反例全是「对端不可能发出这种行为」的垃圾。
所以环境建模的本质是:从完全自由出发,用 assume 逐步剪掉非法行为,直到剩下的行为集恰好覆盖对端真实可能发出的行为。以 AXI 从接口为例,环境 assume 至少包括:握手信号满足 valid 拉高后直到 ready 前不能撤、写地址通道突发长度合法、ID outstanding 数量不超协议上限。站内的 SVA 断言实践 讲的断言写法在这里完全复用——assert 和 assume 是同一种 SVA 语法,只是工具对它们的角色解释相反:assert 是要证明的,assume 是当作前提的。
这个环节有两个方向相反的坑。约束过松(under-constrain):环境里还留着非法行为,工具报出假反例(false negative),工程师花半天追一个现实中不可能出现的波形。这是烦人的坑,但方向安全——证出来的属性依然可信。约束过紧(over-constrain):assume 剪掉了合法行为,属性在「被剪掉的场景」里没验过,工具却报 proven,这是假证明(false positive),方向危险。识别过紧的手段是给每条 assume 配一条对应的 cover 或 assert 镜像:在仿真回归或单独的形式任务里证明「环境确实可能到达被 assume 允许的各种边界行为」,assume 自身的合法性就成了可检查的对象。assume 与 cover 的配合 讲的正是这套约束健康度检查方法。
上图表达环境建模的收敛过程和安全性不对称:从完全自由出发逐条 assume 裁剪,剪到「恰好覆盖真实对端」是理想终点;右下角的健康度检查是防止剪过头的闸门。这张图里的不对称值得背下来——假反例浪费的是调试时间,假证明浪费的是硅。
五、抽象的安全性论证与工程落地流程
三类抽象讲完,回到最根本的问题:抽象模型上 proven,原设计上凭什么成立?答案是 soundness(可靠性)论证,工程上按抽象方向分两类。
过近似(over-approximation):抽象模型的行为集是原设计的超集。环境 nondet 建模天然是这类——只要 assume 没剪过头,抽象环境能发出的行为包含真实环境的所有行为。超集上证成立的属性,子集上必然成立;超集上发现的反例可能是假的(属于超集多出来的部分),需要人工甄别。所以过近似方向「proven 可信、falsified 待查」。欠近似(under-approximation):行为集是子集,比如只测了某几种数据模式。子集上 proven 对原设计没有任何保证,只适合做 bug hunting 找反例。数据位宽缩减严格说不属于两类中的任何一类,它靠的是同构论证——属性和设计在缩放前后行为结构一致,这个论证要逐属性人工完成,没有工具替你背书。
工程落地建议按固定流程走,避免「随手改个参数跑通了就算证完」。第一步,原设计直接跑,确认确实撞墙(记录超时时间、内存峰值),不撞墙不抽象——抽象是要付论证成本的,能原样证就别抽象。第二步,选抽象维度:属性涉及数据值就走位宽缩减,涉及长时序就走深度抽象,环境复杂就先做环境建模。第三步,写抽象变更清单:改了哪些参数、加了哪些 assume、替换了哪些模块,全部进版本管理,和 RTL 一起评审。第四步,做健全性检查(sanity):抽象模型上先跑几条应该失败的负向属性(故意写错的属性),确认工具能报出反例——连故意写错的属性都「证」得出来,说明约束已经把模型掐死了,所有 proven 都是假的。第五步,结论回写:报告里明确写「本结论在某某抽象下成立」,位宽多少、深度多少、assume 清单编号,让签核的人能复现。
上面这张流程图里第四步是全流程的保险丝。很多团队的形式验证流于形式,缺的就是这一步——模型被过紧的 assume 掐死之后,任何属性都 proven,报告漂亮得无可挑剔,而真实的 bug 躺在被剪掉的行为集里。健全性检查成本极低(写几条显然错误的属性跑一遍),拦住的却是最危险的一类假证明。
这一篇在知识体系里的位置
本篇是 chip-design/verification 目录下形式验证线的进阶篇,主关键词形式验证抽象建模。向上承接 形式验证入门 的基本概念和 形式验证有界证明深度 的证明深度分析,回答「撞墙之后怎么办」。横向与 FPV 约束方法论(assume 写法)、assume 与 cover 配合(约束健康度)、形式验证应用组合(哪些 app 吃抽象红利最大)互为支撑;抽象后的具体协议验证可落到 验证异步 FIFO CDC、验证计数器边界 这类场景实战。向下,抽象模型的证明结论最终汇入签核流程,和 逻辑等价检查 LEC 一起构成形式签核的两条腿。
总结
形式验证抽象建模是状态空间爆炸时的标准出路:数据位宽缩减靠「属性只依赖相等关系」的同构论证把 32 位裁成 2 位,计数器与 FIFO 深度抽象靠「属性只依赖到达关系」把 1024 拍裁成 4 拍,环境建模从完全 nondet 出发用 assume 剪到恰好覆盖真实对端行为;三类抽象的安全性各不相同——过近似 proven 可信而 falsified 待查,位宽缩减要逐属性人工论证,assume 过紧会产生假证明所以每条 assume 都要配 cover 镜像;工程上按「确认撞墙、选维度、清单评审、负向属性健全性检查、结论标注抽象条件」五步落地,其中健全性检查是拦住「被掐死的模型证出一切属性」这类假证明的唯一保险丝——抽象换深度是形式验证的核心手艺,但换来的每一个 proven 都必须能讲清它在什么抽象条件下成立。