软件质量保障(2)

Software quality, part two

第 12 讲约 6 分钟阅读官方讲义 ↗

从循环不变量到模型检查,理解性质、假设与保证范围。

阅读目标与前置知识3 项目标
  • 写出循环不变量及其保持条件
  • 说明有限状态检查的边界
  • 区分测试证据与相对规格的证明

建议先读 第 11 讲

不变量invariant模型检查符号执行证明
本章关联演示全部覆盖,仍然可能出错。

测试从实际执行中寻找反例。形式化验证进一步问,在明确的规格、初始条件和执行模型下,可否证明某种错误行为无法出现。本讲从循环不变量到模型检查、符号执行和证明助手,说明不同方法各自检查哪一层,以及如何防止证明了错误的目标。

一、先把「正确」写成可判断的性质

一个性质应当说明适用的输入、允许的动作和所要求的结果。以前置条件和后置条件组织时,证明的含义是只要调用满足前提,执行结束时就得到约定结果。还可以指定终止和一直维持的条件。例如余额始终非负属于安全性质,合法转账应实际发生则约束任务效果。

方法 覆盖范围 一次成功的意义
样例测试 选择的一组运行条件与输入 观察到的运行符合断言
模型检查 模型给定的状态与转移,或某个明确界限 可以找到反例,或在所探索范围内排除反例
程序逻辑与证明 明示语义和前提覆盖的任意执行 推理链按规则成立
真实用户验收 代表性的业务场景 规格和行为更接近真正意图

证明范围随模型和假设变化。规格把非法实现也接受时,严格证明仍会失去工程意义。适合形式化的核心性质通常比实现表达更短、更独立。

二、通过不变量理解循环

证明一个循环,可以检查三项。初始进入循环时性质成立。每轮在给定前提下都保持性质。循环退出时,性质与退出条件共同推出目标。如果还要证明终止,需要有一个随步骤变化并且无法一直减小的量等依据。

2.1 Boyer–Moore 多数投票为什么成立

程序扫描选票,维护候选与计数。相同选项增加计数,不同选项抵消一票,余量归零以后可以换候选。计数代表抵消后的余量。

  • 初始条件。 空前缀可以分为零对票和零份余量。
  • 循环保持。 任一前缀都可以分解成若干对不同选项,外加计数所指的同一选项余量。读到同候选的票就增加余量,读到其他票就同一份余量配对。余量为零时,新票开始下一组。
  • 退出推导。 若存在严格多数,每次删除两张不同票,最多带走其中一张多数票。严格多数的优势不会因此消失,最后的余量仍应指向该选项。

这也精确说明算法前提。没有保证存在严格多数时,第一遍只给候选。第二遍要重新计数并检查候选是否确实超过一半。对于三个各得一票的选项,保留某个候选仍不能宣布它是多数。

三、将程序转成状态机检查错误路径

模型可以把共享变量、每个线程的局部值和执行位置当成状态,把一次读、计算或写定义为转移。讲义用两个线程分别执行一次加一说明问题:

  1. A 读到 0。
  2. B 也读到 0。
  3. 两个线程分别在本地算出 1。
  4. A 与 B 先后写回 1,最终结果只有 1。

这是一条可执行的反例轨迹。如果把读改写作为原子操作,或者用锁保护整段过程,允许的转移就改变了。模型检查要针对新转移重新验证,并说明保证适用的线程数、初始状态和操作模型。

3.1 完整探索与有界探索

完整探索能找到一个包含初态且对转移封闭的可达状态集合。若其中没有坏状态,可以用归纳说明坏状态不可达。多个变量和线程相乘会造成状态爆炸。符号表示可用公式表示一组状态。有界检查则询问是否存在一定步数内的反例,找到可满足解时能给轨迹。一个步数界限内无解,结论限于该界限,推广还需要其他依据。

3.2 从抽象模型回到实现

TLA+ 等建模方法允许聚焦事务参与者、消息与状态约束。写了一个正确的抽象模型后,还要说明具体实现如何对应到抽象状态和行为。这种精化关系允许实现有更多细节或在抽象层保持状态的中间步骤。以事务提交为例,先证明模型里不会一方提交、另一方中止,再检查实现中的日志和协议步骤能对应到模型。

四、从符号执行到真实系统的证明

符号执行把输入保留为变量。程序遇到分支时,在不同路径加入对应约束。给定路径条件 PC 和目标性质 P,可以问求解器 PC 与「P 不成立」能否同时满足。能满足时得到具体输入,无解时说明采用的语义及路径约束下没有这类反例。循环、依赖环境以及路径数量会限制探索规模。

讲义用 KLEE 说明按路径找输入,借 CompCert 和 seL4 讨论证明编译器和内核的投入。编译器验证关注源码和目标程序的语义关系,内核验证关注实现与抽象规范之间是否一致。基础设施被许多程序重复使用,证明收益可以反复发挥。学习时应同时读性质、环境假设与证明对象,避免把特定保证泛化成整个系统所有行为。

五、证明助手给 Agent 提供严格的反馈

证明助手保存已知条件和待证明目标。使用已知等式改写,应用定理产生子目标,或提供存在性证据,都会改变证明状态。自动化策略可以尝试寻找可行步骤,最终由内核检查证明对象是否成立。类型不匹配、定理前提未满足和子目标遗漏,都能变成下一轮可操作的反馈。

Curry–Howard 对应把这件事与程序联系起来。在这一视角中,命题对应类型,证明对应可构造的对象。

逻辑任务 对应的构造
从 P 推出 P 对 P 的证据直接返回,形如恒等函数
从 P 得到 Q 构造接收 P 的证据并产生 Q 的函数
证明存在满足条件的对象 一并给出见证和满足条件的证据
对自然数证明命题 写出基础情形和保持归纳步骤的构造,并说明终止

携带证明的代码把职责分给交付方和接收方。交付方附上满足指定策略的证明,接收方使用自己的环境核查是否可以接纳代码。生成式工具可能降低寻找证明的成本,检查环节仍依赖形式系统和明确策略。

六、验证模型和规格本身

讲义给出余额非负的例子。若转账实现始终保持账户原样,它可能满足非负条件,却缺少用户请求的行为。验证时需要同时检查「合法转账改变双方余额」「非法请求保持原状态」「余额不可以为负」等彼此相关的性质。形式化成果可以用已知样例和故意错误的实现来核对,看规格究竟允许和拒绝什么。

可从两端建立证据。一端是证明对象和真实代码能对应,另一端是通过用户场景、原型与反例检查规格。自动化越擅长实现与证明,越值得明确什么结论真正需要保证,以及模型遗漏了哪些现实条件。

综合练习

为「两位学生竞争最后一个选课名额」写一个有限状态模型,说明初态、请求步骤与允许的交错。先找到一条会使两人都认为成功的执行,再提出原子确认规则。说明安全性质、合法请求应有的进展和模型边界。最后记录哪部分可以用模型检查,哪部分仍需真实数据库的集成测试。

第 12 讲官方讲义

停一下,解释给自己听。

通过有限个输入测试,能证明所有输入都正确吗?

展开答案要点

通常不能。测试只覆盖执行过的输入;证明需要明确规格、模型与假设,并论证这些条件下性质对所声称的范围都成立。

为这次阅读留下一个标记。

已读由你决定,不代表自动评估掌握程度。

学习记录,留在这里。

阅读位置、已读章节和实验清单保存在当前浏览器。更换浏览器或清理站点数据后,这些记录不会同步。

0 / 12 讲已标记为已读

Search the course
输入关键词,或从下方开始。
试试 暂存区、CQRS、不变量Esc 关闭 · Tab 选择结果