
TLAPS-Bench 基准发布:用 TLA+ 形式化验证真实系统规格的正确性
来源标题:TLAPS-Bench: Formally Proving Correctness Of Real-World System Specs With TLA+
TLAPS-Bench 基准发布,用于检验 AI 对真实系统 TLA+ 规格进行形式化证明的能力。此前 TLAPS 因需人工构造归纳不变式并拆分证明义务而几乎无人实际使用,但今年夏天 Claude 已能完成 TLAPS 证明。该基准覆盖模型检查难以穷举的所有配置。
以下正文由 AI 翻译自 Hacker News 最新(原文版权归原站所有),可能存在偏差,重要内容请以原文为准。
TLA+ 规范语言在大多数人心中长期只与 TLC 模型检查器联系在一起。用 TLC 做模型检查能快速发现 bug,但它只覆盖你给定的配置,而且只有对小规模配置(3 个节点、取值范围 “1..4” 等)才便宜。此外还有 TLA+ 证明系统 TLAPS,它检查的是演绎证明,而不是像模型检查那样枚举状态。你在 TLA+ 中把证明写成带编号的层级步骤后,TLAPS 会把每一步变成证明义务,交给后端证明器。作为证明器,TLAPS 能一次性覆盖所有配置,但需要大量专业知识和投入。我一直对 TLAPS 敬而远之,因为觉得自己驾驭不了。你得找出归纳不变式(见下文),证明每个动作都保持它,并把论证拆成足够小的义务,交给 Z3、Isabelle 或 LS4 去检查。所以实践中最终发生的是:几乎所有人都在做模型检查,几乎没人做证明。
不过,和我们行业里的大多数事情一样,过去一年这发生了剧变。今年夏天早些时候,我看到 Claude 在做 TLAPS 证明时,整个人都惊呆了!我的天,这可不是我今年 bingo 卡上有的项目!我知道在这方面多投入是明智的,结果发现 Tianyin Xu、Qian Cheng 和 Markus Kuppe 已经在做这件事了,而且有一篇论文在写。我加入团队较晚,不确定自己是否做出了显著贡献。不过,能和这样一支高水平的团队合作与交流,还是很棒的。
论文现在在 arXiv 上,代码在 GitHub 上。论文问的是:如今 agent 能承担多少证明负担,并引入了一个 benchmark 和一套 harness 来研究这个问题。TLAPS-Bench 是一个包含 265 个证明目标的 benchmark,来自 95 个真实系统和协议的 TLA+ 规范。Tilapia 是在这些目标上运行 agent 的 harness,它提供证明检查器、模型检查器、证明库,以及防止 agent 作弊的守卫。我们在 70 个最难的目标上做了评估,最好的模型证明了其中 44.3%。我希望各实验室用 TLAPS-Bench 训练 agent,让它们在接下来的几个模型版本中,在证明以及一般性的自动形式化方面变得强得多。
大多数验证 benchmark 都是受限的证明补全任务。它们给模型一个脚手架。Selene 和 FVELer 从 seL4 的 Isabelle 证明中抽出引理。CoqStoq 和 VeriSoftBench 从已完成的 Rocq 和 Lean 项目中抽出定理。NTP4VC 提供验证条件。VeruSAGE-Bench 和 Laurel 从已经验证过的系统中提取函数。模型拿到辅助引理、中间不变式或定理依赖结构,然后填空。TLAPS-Bench 什么都不给。
第二个区别是范围。Dafny、Verus 和 Lean 的 benchmark 针对单个函数、API 或模块的功能正确性。即便是要求模型给出不变式的那些(DafnyBench 和 VerusBench),要的也是单个函数内部的循环不变式。这些都没有要求分布式协议的归纳不变式。相比之下,TLAPS-Bench 正面强攻这一点。TLAPS-Bench 中的性质是关于整个系统随时间的:一个 term 中不会有两个 leader、已提交的条目在崩溃后存活、事务串行化、缓存行保持一致。
最近有一篇论文 TLA-Verus,主张把 TLA+ 规范翻译成 Verus 并在那里证明,还错误地声称 TLAPS 无法证明任意时序性质。(在证明步骤上写 BY PTL 会告诉 TLAPS 把该步骤当作命题时序逻辑,送给 LS4——一个 LTL 判定过程。)恰恰相反,从 TLA+ 翻译出去也意味着把时序逻辑抛在身后。Verus 验证 Rust,对 [] 和 <> 一无所知,所以只能通过 Anvil 以库的形式获得时序逻辑。Anvil 在 Verus 之上构建了 always、eventually、leads_to 和 WF1。Lean 最近获得了大量应得的关注,处境也一样。Lean 是通用证明助手,所以要推理协议,你得自己写状态机和自己写时序算子,或者从别的框架借用,比如 Veil。在 TLA+ 中,状态机是语言自带的。你写变量、初始谓词,以及作为前后关系的动作,而 “always”、“eventually”、“leads_to” 随逻辑一起提供。行为是状态的无限序列,规范和你想让它满足的性质都是关于这些行为的公式。Verus 和 Lean 是为不同的工作打造的,而且它们擅长各自的工作。但 TLA+ 才是状态机和时序逻辑内置的地方。
精化是 TLA+ 中另一项免费获得的东西。要证明一个实现满足其抽象规范,你只需写两个时序公式之间的蕴含。对于抽象规范中的每个变量,你提供一个“精化映射”,从实现的变量计算出它。然后你用和其他一切相同的证明器证明 Concrete => Abstract。在其他系统中,精化是你必须搭建的机制(通过在两个状态机之间建立/证明模拟关系)。既然 TLA+ 把精化作为蕴含交给你,TLAPS-Bench 就能在安全性和活性目标之外,也承载精化目标,比如 Wildfire 的缓存一致性协议精化 Alpha 内存模型。太好了!
(原文较长,此处译出前 6000 字,完整内容请点「打开原文」。)
正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。