对 Raft 实现的形式化模型进行验证

Lobsters Hottest 论文

摘要

Antithesis 结合 AI 与形式化方法,对来自 etcd 和 HashiCorp 的生产级 Raft 实现进行形式化建模与验证,证明了选举安全性(Election Safety)、领导者完备性(Leader Completeness)和状态机安全性(State-Machine Safety)等核心安全属性,同时既发现了代码中的缺陷,也暴露了模型本身的问题。

<p><a href="https://lobste.rs/s/4qcr3k/verifying_formal_models_raft">评论</a></p>
查看原文
查看缓存全文

缓存时间: 2026/11/20 23:18

# 验证 Raft 实现的形式模型 | Antithesis 来源:https://antithesis.com/blog/2026/verifying-formal-models/ Rohan Padhye 头像Rohan Padhye研究员 在 Antithesis,我们热衷于在分布式系统中发现 bug。但 Antithesis 还能通过结合 AI 与形式化方法来*证明*复杂设计选择的正确性,从而帮助*消除*某些类别的 bug。 在这篇文章中,我们展示了这一范式在两个 Raft (https://raft.github.io/) 实现上的应用——来自 etcd (https://github.com/etcd-io/raft/) 和 HashiCorp (https://github.com/hashicorp/raft) 的生产级库。尽管它们实现的是同一协议,但两者采用的方法存在显著差异。我们使用 AI、TLA\+ 和 Antithesis 对这两个库进行了形式化建模,并配合 trace validation(轨迹验证)<sup>https://antithesis.com/blog/2026/verifying-formal-models/#fn-body-1</sup>。我们在模型检查、Antithesis 测试和证明尝试之间反复迭代,每一步都暴露出了代码中的 bug 或模型中的缺口。我们修补 bug 并改进模型,直到模型可以被证明,*并且*每次测试运行都符合模型规范。 我们的模型涵盖了核心 Raft 算法的若干扩展,包括 pre\-votes(预投票)、快照、领导者转移,以及仅针对 etcd\-raft 的:用于线性一致性的读索引、异步存储写入和成员变更(其中 etcd 的实现会[有意偏离](https://github.com/etcd-io/raft/blob/v3.7.0/doc.go#L262-L270) Raft 论文)。 **最终的证明确立了 Raft 的核心安全属性,如选举安全(Election Safety)、领导者完备性(Leader Completeness)和状态机安全(State\-Machine Safety)**。换句话说,我们的流程表明:在应用了必要的变通方案和修复之后,HashiCorp Raft 和 etcd\-raft 中体现的**具体设计**(限于我们建模的那些特性)确实提供了与 Raft 论文相同的保证。我们将相关工件开放供审查: - HashiCorp Raft 形式化 (https://github.com/antithesishq/hashicorp-raft-formalized) - etcd\-raft 形式化 (https://github.com/antithesishq/etcd-raft-formalized) ### Raft 不是已经被验证过了吗?(https://antithesis.com/blog/2026/verifying-formal-models/#isn-t-raft-already-verified) 今年早些时候,我们曾撰文介绍[为何我们测试的每个主要 Raft 实现都能被发现 bug](https://antithesis.com/blog/2026/finding-bugs-in-raft-implementations/)。这令人惊讶,因为底层的 Raft 协议已经过广泛研究、形式化规范和严格证明正确(在一组假设之下)。在那篇文章中,我们指出许多实现会微妙地偏离这些假设、为性能重新设计算法,和/或用未经验证的扩展来扩展核心 Raft 协议——从而引入 bug。 自那以后,AI 的进步使[自动定理证明](https://openai.com/index/navier-stokes-solution/)和[复杂系统的形式验证](https://www.anthropic.com/research/formal-verification)变得更加可扩展,使得将规范与其实际实现连接起来成为可能。因此,我们着手对不仅核心 Raft 协议、而且是生产级 Raft 库所实现的具体设计进行形式验证,包括自定义数据结构、不同的并发模式,以及 pre\-votes、领导者转移、快照和(在 etcd\-raft 的情况下)成员变更等各种扩展。 ### 对 Raft 实现进行形式化建模 (https://antithesis.com/blog/2026/verifying-formal-models/#formally-modeling-raft-implementations) 应用形式化方法的一个关键挑战是找到一种抽象层次,既能让我们用数学方式推理期望的属性,*又能*弥合规范与实现之间的鸿沟。我们尚未达到可以直接在汇编指令甚至编程语言语义层面进行推理,以验证生产系统中分布式安全属性的程度。https://antithesis.com/blog/2026/verifying-formal-models/#fn-body-2 最广泛使用的方法是用 [TLA\+](https://lamport.azurewebsites.net/tla/tla.html) 之类的规范语言将软件建模为状态转换系统,并在有限状态空间上检查这些转换的不变量。TLA\+ 模型可以由专家手写,如今也可以直接从代码中用 AI 推断出来。这种方法[有其局限性](https://buttondown.com/hillelwayne/archive/llms-are-bad-at-vibing-specifications/),但正日益[流行](https://zfhuang99.github.io/github%20copilot/formal%20verification/tla+/2025/05/24/ai-revolution-in-distributed-systems.html)。那么下一个挑战就是证明 TLA\+ 模型与[实际将在生产中运行的软件](https://www.datadoghq.com/blog/engineering/continuous-formal-spec-validation/)相对应([对应性检查](https://www.mongodb.com/company/blog/engineering/conformance-checking-at-mongodb-testing-our-code-matches-our-tla-specs))。 在我们的演示中,我们使用 Claude Fable 5.2 从 HashiCorp Raft 和 etcd\-raft 的实现中自动推断出 TLA\+ 模型,然后手动审查规范中声明的安全属性。https://antithesis.com/blog/2026/verifying-formal-models/#fn-body-3 我们必须手动提供指导,说明要建模或省略哪些特性、为模型检查指定哪些场景,并对自动生成的安全属性做了一处调整。虽然 AI 通常[不擅长推断属性](https://newsletter.pragmaticengineer.com/p/formal-methods-with-hillel-wayne),但在这种情况下,我们只需指示智能体用形式化语言表达 [Raft 论文](https://raft.github.io/raft.pdf)中定义的核心安全属性。https://antithesis.com/blog/2026/verifying-formal-models/#fn-body-4 ### 但我们怎么知道模型与软件相对应?(https://antithesis.com/blog/2026/verifying-formal-models/#but-how-do-we-know-the-model-corresponds-to-the-software) 这正是 Antithesis 发挥作用的地方。 我们使用了新推出的 [Antithesis 插件](https://github.com/antithesishq/antithesis-plugin)来自动搭建测试集群、生成能够覆盖模型中所有特性的输入工作负载,以及与模型安全属性相对应的断言。随后,软件在故障注入下接受测试,同时接收随机输入,遍历各种代码路径以及线程/消息的交错执行。 在这次演示中,我们开发了一个轻量级的 [trace validation(轨迹验证)](https://arxiv.org/abs/2404.16075)工具包,让运行在 Antithesis 中的软件能够发出与 TLA\+ 规范中状态转换相对应的结构化日志事件。任何产生的轨迹若不符合模型中的某条路径,就会被标记出来。不合规的轨迹可能意味着轨迹日志本身的埋点不正确,或者更严重地说,意味着建模错误或系统中真实的 bug。我们指示 AI 智能体诊断究竟属于哪种情况,必要时使用 Antithesis([时间旅行智能体](https://antithesis.com/blog/2026/time-traveling-agents/)),并持续迭代直到轨迹与推断出的模型收敛一致。 ### 不变量、模型检查与 bug 修复 (https://antithesis.com/blog/2026/verifying-formal-models/#invariants-model-checking-and-bug-fixes) 对于两个 Raft 模型,规范表达了以下安全属性,它们直接取自 [Raft 论文](https://raft.github.io/raft.pdf): - **选举安全(Election Safety)**:给定任一任期,最多只能选出一个领导者。 - **日志匹配(Log Matching)**:如果两条日志在相同索引和任期下有相同条目,则它们在该索引之前的所有条目都一致。 - **领导者完备性(Leader Completeness)**:领导者的日志包含之前所有任期中已提交的条目。 - **状态机安全(State Machine Safety)**:不会有两个节点在相同索引处向其状态机应用不同的条目(状态机本身不在建模范围内)。 在尝试证明任何东西之前,我们先使用 TLC(标准的 TLA\+ 模型检查器)在有界实例上验证这些不变量成立。这些实例同样由我们的 AI 智能体合成,指定了各种边界:集群通常为三个节点、单个客户端值、最多一两轮领导者选举任期、日志限制在几条条目内,且只有少量网络消息在途。这些边界听起来很小,但足以构造出多个有趣的场景:竞争选举、被废黜的领导者仍在复制、日志条目被覆盖并重新复制、操作中途崩溃等等。我们还对 Raft 库的各种配置进行了模型检查,例如启用或禁用 pre\-vote 或快照功能。这些"小"实例可以达到超过 160 万个状态的状态空间,TLC 会对其进行穷举探索。我们还包含了一些更大的问题,它们仅通过随机模拟进行检查。如果模型检查触发了安全违规,我们尝试在本地或 Antithesis 中将其复现为断言失败;如果软件无法展现该行为,模型就必须收紧。 总体而言,我们的流程是一个迭代循环,由模型检查(标记不变量违规)、轨迹验证(标记偏差)、模型改进(修复设计缺陷或符合性问题)和软件修补(修复 bug)组成。https://antithesis.com/blog/2026/verifying-formal-models/#fn-body-5 在某些方面,这种方法类似于 [Specular](https://arxiv.org/abs/2607.25333) 并受到其启发。然而,由于 Specular 的目标是发现 bug,其方法涉及在编写模型之前用 AI 识别有 bug 的场景,这意味着[静态分析承担了大量繁重工作](https://github.com/specular-org/Specular/issues/176)。相比之下,我们的模型旨在更具通用性,并证明整个设计的安全性。 在此过程中,我们在两个系统中都遇到了 bug,包括已知的未解决问题,如 [hashicorp/raft\#695](https://github.com/hashicorp/raft/issues/695) 和 [etcd\-io/raft\#551](https://github.com/etcd-io/raft/issues/551),以及新发现的问题,如 [hashicorp/raft\#746](https://github.com/hashicorp/raft/issues/746) 和 [etcd\-io/raft\#558](https://github.com/etcd-io/raft/issues/558)。在我们的内部仓库中,我们共为两个实现打了 7 个补丁。https://antithesis.com/blog/2026/verifying-formal-models/#fn-body-6 在每种情况下,我们的目标都是让系统和模型同时通过验证和测试。 我们还遇到了几个额外的崩溃 bug,但那些并不违反安全性。 然而,有界模型检查只能证明小状态空间中没有 bug。要对无界输入规模获得保证,唯一的方法是严格的数学证明。 ### 证明、保证与局限 (https://antithesis.com/blog/2026/verifying-formal-models/#proofs-assurances-and-limitations) 有两种优秀的技术可以为整个规范证明不变量的正确性:使用集成在 TLA\+ 中的定理证明器 [TLAPS](https://proofs.tlapl.us/doc/web/content/Home.html),或将模型翻译成 [Veil](https://veil.dev/)——一个用于 [Lean](https://lean-lang.org/) 证明助手的状态转换系统建模库。我们两者都用了,https://antithesis.com/blog/2026/verifying-formal-models/#fn-body-7 并将证明构造的任务委托给 Claude Fable 5.2。 我们使用 Veil 官方的 tla\-to\-veil LLM 技能进行模型翻译,并采用推荐的方法——在我们之前存储的实例上,使用 TLC 和 Veil 自己的模型检查器进行有界等价性检查来验证翻译的正确性。 理想情况下,TLAPS 证明能提供最好的保证,因为它可以直接证明 TLA\+ 模型本身定义的安全属性。然而,我们决定将 TLA\+ 翻译成 Veil 并在 Lean 中尝试证明。为什么?如上一节所述,我们的流程极具迭代性,涉及多个模型改进步骤。我们希望将证明引擎作为该过程中的额外反馈来源,将任何通过了有界模型检查和轨迹验证的候选规范都输入其中。我们发现 Lean 的交互式策略范式、可预测的性能以及内核校验的持久化证明项是这一迭代过程中的关键优势。 有一次,etcd\-raft 成员变更实现的模型无法被证明正确,这[揭示了一个复杂的 bug](https://github.com/etcd-io/raft/issues/558),其触发条件超出了有界模型检查所探索的状态空间范围。在这种情况下,我们可以使用 Antithesis 插件尝试合成一个工作负载来复现该反例。 Antithesis 也在证明构造过程中提供了帮助。在处理证明中具有挑战性的部分时,Claude 提出了几个中间不变量,如果它们为真,就能导出一个直接的证明策略。然后该智能体使用 Antithesis [快速检查](https://antithesis.com/blog/2026/streaming-results/)这些不变量在测试运行中是否成立,如果运行时断言失败就丢弃它们。因此,Antithesis 使证明构造阶段更加高效。 当我们最终收敛到一个安全属性在 Lean 中完全可被证明、且模型在 Antithesis 上通过轨迹验证的状态时,我们冻结了规范,并要求智能体使用 TLAPS 直接在 TLA\+ 规范上证明相同的不变量。这最后一步并非严格必要,但消除了对 Lean 证明和 TLA\+ 规范之间一致性的任何疑虑。 端到端来看,每个库的工作在 Claude Fable 用量上花费不到 1,200 美元,约需 2000 个 Antithesis 计算小时。https://antithesis.com/blog/2026/verifying-formal-models/#fn-body-8 值得指出的是,这少于单月 [Antithesis Teams](https://antithesis.com/pricing/) 预付额度的用量。 请注意,我们最终的证明验证的是实现的形式模型,而非代码本身。不过,基于 Antithesis 提供的广泛测试覆盖(包括网络分区和节点崩溃等故障注入)所进行的轨迹验证,我们可以对模型的保真度建立信心。为了进一步加强保证,我们的迭代过程包含多个*变异测试(mutation testing)*(https://antithesis.com/blog/2026/mutation-testing/)步骤,包括:变异规范以检查证明确实会失效、变异已存储的测试日志以确保轨迹验证会失败,以及变异软件本身以确保一切都会崩溃。 模型仍然对环境做了若干假设,这限制了验证的适用范围。例如,两个 Raft 库都提供了本地持久存储的可插拔接口。在我们的测试工作负载中,我们使用 [BoltDB](https://github.com/boltdb/bolt) 进行存储,模型假设任何单次写入(例如一条日志条目或一组 Raft 状态)都不会被撕裂或损坏,这是 BoltDB 所保证的。崩溃仍可能发生在两次写入之间。 我们的工作还省略了若干未建模的库特性,例如 etcd\-raft 的基于租约的读(因为它依赖挂钟时间)、hashicorp\-raft 的异步心跳(因为它[已知非常](https://github.com/hashicorp/raft/issues/666)[非常](https://github.com/hashicorp/raft/issues/695)[有 bug](https://github.com/hashicorp/raft/issues/742);[真的](https://github.com/hashicorp/raft/issues/717)),以及 hashicorp\-raft 的成员变更(因为我们修补更简单核心的 bug 已经筋疲力尽)。最后,我们在这个原型中只验证安全属性,忽略活性(liveness)。相关的假设和限制完整列表见对应工件的 README。 ### 展望 (https://antithesis.com/blog/2026/verifying-formal-models/#looking-ahead) Hillel Wayne 头像

相似文章

一个使用AI证明器的Rust到Lean验证流水线:经验报告

Lobsters Hottest

本文报告了一个验证流水线的经验,该流水线使用AI证明器(Aristotle和Aleph)结合符号提取工具和形式化密码学库,为Lean 4中的Rust密码学代码生成机器检查的正确性证明,并提供了来自以太坊基金会zkEVM项目的案例研究。

Aristotle 扩展至 Rust

Hacker News Top

Harmonic 宣布,其形式化验证工具 Aristotle 现已支持 Rust,让开发者能够在发布前通过数学方法证明代码(包括 unsafe 代码块)符合其规范。该公司还宣布与 Solana 基金会建立合作伙伴关系,协助验证智能合约;针对 Manifest 和 Project 0 的案例研究已发现实际存在的漏洞。