“形式化验证可以把实现状态映射到“共同 committed 前缀 + 确定状态”的抽象机,并用精化关系说明选主、重试和快照等内部步骤不改变外部历史。模型检查适合在有限副本和有界状态下搜索不变式…”
形式陈述
先固定精化方向
设规格
读作“实现精化规格”。实现可以消除规格中的非确定选择、补充内部细节,却不能增加规格禁止的可观察行为。
有些文献把符号方向反过来,因此任何精化定理都应同时写出集合包含或匹配条件。只说“更精”而不说明哪一边允许行为更少,会在传递证明和接口替换中产生方向错误。
若规格性质
用模拟证明精化
直接比较无限行为集合通常困难。可建立表示关系
考虑一个抽象非负整数计数器,动作 inc 使值加一。实现用可扩展的二进制位数组保存值,并用多步 carry 传播完成一次 inc。具体状态还须包含操作阶段和已提交值;只把正在改写的位数组解释为整数,通常不能作为整个操作期间的表示函数。
例如
把内部 carry 步标作 inc 后,证明责任才成为:内部步保持
仅验证最终几个测试值相等不足以证明精化。还要覆盖溢出、非法位模式、执行中途被观察以及实现非确定调度等边界。
直觉
数据精化与操作责任
状态表示改变时,常用 abstraction function
此外还需 initialization 与 finalization:具体初态对应抽象初态,具体输出经观察函数得到规格允许的结果。忽略输出映射可能让内部状态匹配正确,却向用户返回错误值。
操作前置条件也不能被实现悄悄加强。若规格允许所有非空队列执行 dequeue,实现只能在长度至少二时成功,就减少了调用者受保证的输入范围,通常不构成可替换精化。
例子与边界
添加细节不等于添加行为
实现把一个抽象原子动作细分成多个内部步骤,是添加状态和路径细节;只要这些步骤不可观察且不引入新可见结果,仍可能缩小或保持可见行为集合。
相反,给接口增加一个可见错误返回看似“说明得更详细”,却可能增加规格没有允许的 trace。细节多寡是表示层概念,精化方向由可观察行为包含决定。
消除非确定性通常是合法精化。例如规格允许选择红或蓝,实现固定选择红,行为集合变小。对“每条完整执行最终返回结果”这类全称轨迹性质,只要行为集合确实包含无限执行并保持包含关系,删除选择仍会保持性质。对“仍存在一条选择蓝色的路径”则不同:它要求保留某个可能性,单纯行为包含并不保证它。
推论与应用
组合与边界
精化若是预序,应满足自反和传递,使多阶段开发可以串联。要在组件上下文中替换实现,还需 congruence:若
只比较有限可见 trace 时,活性或公平性可能丢失。实现可插入无限内部循环,使每个有限可见前缀都合法,却永远不完成规格承诺。若比较对象已经包含完整无限行为,并且性质是逐行为的全称条件,集合包含本身仍保持该性质;失效来自有限观察隐藏了发散,或公平路径的定义没有随精化正确对应。发散敏感的精化要显式处理这一证明义务。
精化证明也不自动连接到机器代码。若只证明高级模型之间的关系,还需编译器正确性、运行时假设或验证提取链才能把结论传到底层实现。
接口版本演进还要固定观察者能力。旧规格若保证调用 read 不改变状态,新实现增加缓存计数器但计数器不可见,仍可能精化;一旦监控接口暴露该计数器,相同内部步成为可见行为,原证明关系便需重做。这不是兼容层问题,而是行为字母表改变后精化命题本身改变。
精化结论因此总是相对于一份明确的观察契约。
参考资料
- Carroll Morgan, Programming from Specifications, 2nd ed., Prentice Hall, 1994, Chs. 1–5。
- J. M. Spivey, The Z Notation: A Reference Manual, 2nd ed., Prentice Hall, 1992, Chs. 5, 17。
- Nancy A. Lynch and Frits W. Vaandrager, “Forward and Backward Simulations,” Information and Computation 121(2), 1995, pp. 214–233。