文章标题:Verifying formal models of Raft implementations
正文:

在 Antithesis,我们热衷于在分布式系统中寻找 bug。但 Antithesis 也能通过结合 AI 与形式化方法,证明复杂设计选择的正确性,从而帮助消除某些类别的 bug。
本文中,我们在两个 Raft 实现上演示这一范式——来自 etcd 和 HashiCorp 的生产级库。尽管两者实现的是同一协议,但二者采用的方法存在显著差异。我们使用 AI、TLA+ 和 Antithesis 对这两个库进行带 trace 验证的形式化建模。我们在模型检查、Antithesis 测试和证明尝试之间反复迭代,每一次迭代都暴露出代码中的 bug 或模型中的缺口。我们修补 bug 并改进模型,直到模型可被证明,直到每一次测试运行都符合一致性。
我们的模型处理了核心 Raft 算法的若干扩展,包括 pre-vote、快照、领导权转移,以及仅针对 etcd-raft 的:用于线性一致性的读索引、异步存储写入,和成员变更(etcd 的实现有意偏离了 Raft 论文)。
最终的证明确立了核心 Raft 安全性质,如 Election Safety、Leader Completeness 和 State-Machine Safety。换言之,我们的流程确立了:在应用了必要的变通方案和修复之后,HashiCorp Raft 和 etcd-raft 中所体现的具体设计(限定于我们建模的功能范围)实际上提供了与 Raft 论文相同的保证。我们将产物公开以供评审:
- HashiCorp Raft formalized
- etcd-raft formalized
Raft 不是已经被验证过了吗?
今年早些时候,我们撰文讲述了我们如何用 Antithesis 测试时,在每一个主要 Raft 实现中都能不断发现 bug。这令人意外,因为底层 Raft 协议已被广泛研究、形式化规约并严格证明其正确性(在一组假设之下)。在那篇文章中,我们指出许多实现会微妙地偏离这些假设、为性能重新设计算法,和/或用未经验证的扩展来扩展核心 Raft 协议——从而引入 bug。
此后,AI 的进展使得自动化定理证明和复杂系统的形式化验证的可扩展性大大提高,使得将规约与其实现连接起来变得可行。因此我们着手形式化验证不仅是核心 Raft 协议,还有生产级 Raft 库所实现的具体设计,涵盖自定义数据结构、不同的并发模式,以及各种扩展,如 pre-vote、领导权转移、快照,以及(就 etcd-raft 而言)成员变更。
对 Raft 实现进行形式化建模
应用形式化方法的一个关键挑战是,确定一个抽象层次,既允许我们对期望的性质进行数学推理,又能弥合规约与实现之间的鸿沟。我们尚未达到直接以汇编指令乃至编程语言语义的层次进行推理、以验证生产系统中分布式安全性质的程度。
Anthropic/Theorem 的 OSS-Verify 和 Google DeepMind 的 AlphaProof Code 都只对单线程汇编代码建模;而分布式系统是并发的。
最广泛使用的方法是在 TLA+ 之类的规约语言中将软件建模为状态转移系统,并在有限状态空间上检查这些转移上的不变量。TLA+ 模型可以由专家手写,或如今使用 AI 直接从代码中推断出来。这种方法有其自身的局限,但越来越流行。那么接下来的挑战就是,证明 TLA+ 模型对应于将在生产环境中运行的实际软件。
文章标题:Verifying formal models of Raft implementations
正文: 在我们的演示中,我们使用 Claude Fable 5.2 从 HashiCorp Raft 和 etcd-raft 的实现中自动推断 TLA+ 模型,然后人工审查了规范中声明的安全属性。
etcd-raft 仓库中有一个为跟踪验证而构建的 TLA+ 模型,该模型现已过时,且在设计上并不便于证明。Specular 项目产出了 etcd-raft 和 hashicorp-raft 的模型,但这些模型是为跟踪验证而设计的,而非便于证明,并且 TLAPS 排行榜显示,截至 2026 年 11 月 20 日,它们仍未得到解决。
我们不得不手动提供指导,说明哪些特性需要建模或省略、为模型检查指定哪些场景,并对自动生成的安全属性做了一处细化。虽然 AI 在推断属性方面普遍表现不佳,但在本例中,我们只是指示 agent 表达 Raft 论文中定义的核心安全属性。
但我们如何知道模型与软件相对应?
这正是 Antithesis 的用武之地。
我们使用最近推出的 Antithesis 插件自动搭建了一个测试集群、一个旨在覆盖模型中所有特性的输入生成工作负载,以及与模型安全属性相对应的断言。随后,软件在故障注入下接受测试,同时被喂以随机输入,从而执行各种代码路径以及线程/消息交错。
在本演示中,我们开发了一个轻量级的跟踪验证工具包,使在 Antithesis 中运行的软件能够发出与 TLA+ 规范中的状态转换相对应的结构化日志事件。任何产生的跟踪与模型中某条路径不符的测试执行都会被标记出来。不符合的跟踪可能表明跟踪日志记录本身的插桩有误,或者更严重地,表明存在建模错误或系统中的真实缺陷。我们指示 AI agent 在必要时借助 Antithesis 来诊断它可能是其中哪一种,并持续迭代,直到跟踪与推断出的模型收敛。
不变量、模型检查与缺陷修复
对于两个 Raft 模型,规范表达了以下安全属性,直接取自 Raft 论文:
- 选举安全:在给定任期内最多只能选出一个 leader。
- 日志匹配:如果两个日志具有相同索引和任期的条目,则它们在该索引之前的每个条目上都一致。
- Leader 完整性:leader 的日志包含在更早任期内已提交的每个条目。
- 状态机安全:没有两个节点会在同一索引处将不同的条目应用到其状态机(状态机本身未被建模)。
在尝试证明任何内容之前,我们使用 TLC(标准的 TLA+ 模型检查器)验证了这些不变量在有界实例上成立。这些实例同样由我们的 AI agent 合成,指定了各种边界:集群通常为三个节点、单个客户端值、最多几个任期的 leader 选举、日志限制在少量条目、仅有少量网络消息在途。这些边界听起来很小,但足以创造出若干有趣的情况:竞争性选举、被废黜的 leader 仍在复制、日志条目被覆盖并重新复制、操作中途崩溃等。我们还对 Raft 库的各种配置进行了模型检查,例如启用和禁用 pre-vote 或快照特性。这些“小”实例可以达到超过 160 万个状态的状态空间,TLC 会对其进行穷尽探索。我们还纳入了一些较大的问题,仅通过随机模拟进行检查。如果模型检查触发了安全违规,我们会尝试在本地或 Antithesis 中将其复现为断言失败;如果软件无法表现出该行为,则必须收紧模型。
总体来看,我们的流程是一个迭代循环,由模型检查(标记不变式违规)、跟踪验证(标记偏差)、模型精化(修复设计缺陷或一致性问题)以及软件打补丁(修复 bug)组成。
在某些方面,这种方法与 Specular 相似,并受其启发。不过,鉴于其目标是发现 bug,Specular 的做法是在编写模型之前使用 AI 来识别有 bug 的场景,这意味着静态分析承担了大量繁重工作。相比之下,我们的模型旨在更通用,并证明整个设计的安全性。
在此过程中,我们在两个系统中都遇到了 bug,包括此前已知的未解决问题,如 hashicorp/raft#695 和 etcd-io/raft#551,以及新问题,如 hashicorp/raft#746 和 etcd-io/raft#558。在我们的内部仓库中,我们在这两个实现上总共应用了 7 个补丁。在每种情况下,我们的目标都是让系统和模型同时通过验证与确认。
我们还遇到了另外几个崩溃 bug,但它们并不违反安全性。
但有界模型检查只能表明在较小状态空间中不存在 bug。要针对无界输入规模获得保证,唯一途径是严格的数学证明。
证明、保证与局限
有两种好技术可以证明不变式在整个规范上正确:使用集成到 TLA+ 中的定理证明器 TLAPS,或者将模型翻译为 Veil——一个用于状态转移系统建模的 Lean 证明助手库。我们两者都用了,并将证明构造任务委托给 Claude Fable 5.2。
我们使用 Veil 官方的 tla-to-veil LLM skill 进行模型翻译,并采用推荐方法,通过在我们先前存储的实例上使用 TLC 和 Veil 自带的模型检查器进行有界等价性检查来验证。
理想情况下,TLAPS 证明提供最好的保证,因为它可以证实在 TLA+ 模型本身上定义的安全属性。然而,我们决定将 TLA+ 翻译为 Veil,并在 Lean 中尝试证明。为什么?如上一节所述,我们的流程极其迭代,涉及多个模型精化步骤。我们希望将证明引擎作为该过程中的额外反馈,把任何有界模型检查和跟踪验证都成功的候选规范输入给它。我们发现 Lean 的交互式 tactic 范式、可预测的性能以及持久的内核检查证明项是这一迭代过程中的关键优势。
有一次,一个按实际实现建模的 etcd-raft 成员变更模型无法被证明正确,揭示了一个复杂的 bug,其触发条件超出了有界模型检查所探索的状态空间。在这种情况下,我们可以使用 Antithesis 插件尝试合成工作负载以复现反例。
Antithesis 在证明构造过程中也有帮助。在处理证明中具有挑战性的部分时,Claude 假设了几个中间不变式,如果它们为真,将导向一种直接的证明策略。该 agent 随后使用 Antithesis 快速检查这些不变式在测试运行中是否成立,并在运行时断言失败时将其丢弃。因此,Antithesis 使证明构造阶段更加高效。
一旦我们收敛到安全属性在 Lean 中完全可证明、且模型通过 Antithesis 跟踪验证的状态,我们就冻结规范,并要求 agents 直接用 TLAPS 在 TLA+ 规范上证明相同的不变式。这最后一步并非严格必要,但消除了关于 Lean 证明和 TLA+ 规范之间任何一丝疑虑。
端到端来看,每个库的工作花费不到 1,200 美元的 Claude Fable token 费用,以及约 2000 个 Antithesis 计算小时。
我们应当指出,这少于 Antithesis Teams 单月预付额度。
请注意,我们的最终证明验证的是实现的形式化模型,而非代码本身。不过,基于 Antithesis 提供的广泛测试覆盖所执行的跟踪验证,包括网络分区和节点崩溃等故障注入,我们可以对模型的保真度获得信心。为进一步加强保证,我们的迭代过程包含多个步骤的变异测试,包括:对规范进行变异以检查证明是否会失效,对存储的测试日志进行变异以确保跟踪验证失败,以及对软件本身进行变异以确保一切都会崩溃。
这些模型仍然对环境做出了若干假设,这限制了验证的覆盖范围。例如,两个 Raft 库都为本地持久化存储提供了可插拔接口。在我们的测试工作负载中,我们使用 BoltDB 作为存储,模型假设任何单次写入(例如,一条日志条目或一个 raft 状态元组)都不会被撕裂或损坏,BoltDB 保证了这一点。但崩溃仍可能发生在两次写入之间。
我们的工作还遗漏了若干我们未建模的库特性,例如 etcd-raft 基于租约的读取(因为它依赖挂钟时间)、hashicorp-raft 的异步心跳(因为它已知非常非常多的 bug;真的),以及 hashicorp-raft 的成员变更(因为我们已经疲于在更简单的核心中修补 bug)。最后,在这个原型中我们只验证安全性质,忽略活性。相关 artifact 的 README 中提供了假设和局限性的完整列表。
展望
鉴于我们作为“一家 fuzzing 公司”的声誉,形式化方法对我们来说似乎是一个奇怪的探索方向。但我们认为自己与其说是“一家 fuzzing 公司”,不如说是一家正确性公司。如果我们想构建真正健壮的系统,就需要各种不同的方法。每种技术都能弥补其他技术的弱点。此外,它们还能放大彼此的优势。第一个基于性质的测试框架 QuickCheck,从函数的静态类型推导出测试输入。我们的许多客户同时使用测试和形式化方法,因此我们希望让这两种技术更好地协同工作。
形式化规范最大的弱点是,它证明的是设计正确,但并不保证我们实现的代码实际上与设计匹配。跟踪验证利用测试的优势来弥补形式化规范的核心弱点。如果我们的测试能够达到极其不寻常的系统状态,验证效果最好,这与我们的核心技术高度契合。
形式化规范如何帮助测试则相对较少被探索,但这里也有一些机会。我们经常发现,基于性质的测试的新手很难描述他们系统的性质。但他们可以描述系统本质上做什么的高层概要。借助跟踪验证,我们有可能将这份概要转化为要测试的性质!
话虽如此,这是一个早期研究项目。我们能够轻松地将跟踪日志映射到规范行为,因为代码和规范大致处于相同的抽象层次,Go 代码行与 TLA+ 行之间存在密切的对应关系。然而,大多数现实世界的规范比它们所建模的代码高出两个抽象层次。这是因为 1) TLA+ 可以做到真实系统中不可能的事情,比如做出真正任意的非确定性选择,以及 2) 规范可以简化不影响本质设计的实现细节。这些特性使规范更强大,但也使跟踪验证更加困难。
可以这样理解:我们是在演示一种药物在小鼠身上有效,但尚未进行人体试验。还需要更多工作,而我们目前正在 Antithesis 开展这些工作。敬请关注它最终的走向。
附录:跟踪验证简介
文章标题:验证 Raft 实现的形式化模型
正文: 在形式化规约(比如用 TLA+)中,我们为系统编写高度抽象的蓝图,也就是规约,并直接在这些蓝图中发现缺陷。一旦我们发现并修复了所有缺陷,就可以确信我们的真实系统不会出现某些设计问题。
但我们怎么知道我们编写的代码确实对应我们所验证的设计呢?这是形式化规约中尚未解决的重大问题之一,而我们在这里采用的解决方案是 trace validation(也称为“trace checking”)。这一方法首次公开描述于 MongoDB 的论文 eXtreme Modeling in Practice。作者们取生产系统中记录的事件,将其转换为一个状态序列,并检查该序列在蓝图中是否可能发生。如果不可能发生,那么实现必然做了蓝图所禁止的事情,因此实现与规约之间存在偏差。
用一个具体例子来理解这一点会更容易。假设我们有下面这段伪代码作为规约:
i := 0;passed := 0;failed := 0;
while (i < $some_arbitrary_number) { i := i + 1; either {passed := passed + 1} or {failed := failed + 1}}
所谓 either-or,我的意思是每次迭代中两者恰好会发生一个,但判定逻辑属于实现细节,我不关心。这个规约还有一个性质:每次循环迭代之后,passed + failed == i。
下面是一个符合该规约的实现:
for sensor in get_sensors(): reading = sensor.get_data() if convoluted_analysis_passes(reading): add_reading_to_dataset(reading) else: sensor.mark_broken() alert_someone_sensor_is_broken(sensor)
尽管它在实际运作方式上与单纯地任意递增变量非常不同,但本质上仍是同一回事,我们应当预期每个传感器要么被加入集合,要么被标记为损坏。要做 trace validation,我们首先在代码中加入一些日志:
for sensor in get_sensors(): print("loop") reading = sensor.get_data() if convoluted_analysis_passes(reading): print("passed") add_reading_to_dataset(reading) else: print("failed") sensor.mark_broken() alert_someone_sensor_is_broken(sensor)
我们运行这个程序,它打印出“loop passed loop failed”。我们可以把它转换为规约的一个行为。如果我们把一个状态记为 (i, passed, failed),那么对应的状态序列就是 [(0, 0, 0), (1, 0, 0), (1, 1, 0), (2, 1, 0), (2, 1, 1)]。这在该行为下是合法的,因此这条 trace 符合规约。
现在如果我们做一个引入偏差的改动,像这样:
for sensor in get_sensors(): print("loop") try: reading = sensor.get_data() except NetworkTimeoutError: continue reading = sensor.get_data() # ...
现在就有可能运行它并看到日志“loop loop”。对应的行为 [(0, 0, 0), (1, 0, 0), (2, 0, 0)] 在规约中是不可能发生的,因此这会通不过 trace checking,并暴露出代码与规约之间的偏差。
总之,这就是它在原理上的运作方式。要在实践中让它工作,存在大量技术挑战。例如,我们怎么知道一次网络超时可能会给我们带来一条非法的 trace,我们又究竟该如何触发它?这个问题的答案是我们在 Antithesis 中使用的一组技术的结合:确定性模拟测试与 fuzzing。不过这些内容我们在其他文章中详细讨论。