💻 computer science

Deductive Verification of Weak Memory Programs with View-based Protocols (extended version)

本文提出了名为 VerCors-relaxed 的扩展工具，通过将弱内存并发模型编码为基于协议的权限分离逻辑，实现了利用 VerCors 对弱内存并发程序进行自动化演绎验证。

原作者： Ömer Şakar, Soham Chakraborty, Marieke Huisman, Anton Wijs

发布于 2026-04-24

📖 1 分钟阅读☕ 轻松阅读

原作者： Ömer Şakar, Soham Chakraborty, Marieke Huisman, Anton Wijs

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

这篇论文讲述了一个关于如何让计算机程序在“混乱”的内存环境下依然保持正确的故事。

为了让你轻松理解，我们可以把计算机的内存想象成一个繁忙的公共图书馆，把计算机的线程（Thread）想象成不同的读者。

1. 背景：为什么会有“弱内存”问题？

在理想的计算机世界里（这叫“顺序一致性”），图书馆的管理非常严格：

读者 A 把书放在桌子上，读者 B 下一秒就能看到。
所有读者看到的顺序都是一样的，就像大家排着队一样。

但在现代计算机（弱内存模型）里，为了追求速度，图书馆变得非常“灵活”：

读者 A 把书放在桌子上，但他可能还没告诉管理员，书就“暂时”放在了他手边的推车里。
读者 B 可能先看到了读者 C 放的书，却没看到读者 A 放的书。
甚至，读者 A 可能还没放书，读者 B 就“猜”书已经在那儿了（这叫投机读取）。

这种“混乱”会导致程序出现奇怪的错误，比如两个程序以为自己在操作同一个数据，结果却互相覆盖，或者读到了不存在的值。

2. 核心挑战：如何证明程序是对的？

以前，程序员要证明程序在这么混乱的环境下是对的，只能靠人工手写复杂的数学证明。这就像让每个人凭记忆去画图书馆的监控录像，既慢又容易出错。

这篇论文的作者们开发了一个叫 VerCors 的工具，它原本擅长检查“秩序井然”的图书馆。现在，他们给这个工具装上了一个超级大脑，让它也能理解“混乱”的图书馆。

3. 核心创意：基于“视图”的协议（View-based Protocols）

这是论文最精彩的部分。作者发明了一种新的方法，叫**“基于视图的协议”**。我们可以用两个比喻来理解：

比喻一：每个线程都有自己的“私人日记” (Thread-local Views)

在混乱的图书馆里，每个读者（线程）都记着一本私人日记。

日记里记录了：“我看到 A 读者在几点放了一本书”、“我看到 B 读者在几点拿走了书”。
因为每个人看到的顺序可能不同，所以每个人的日记内容（视图）都不一样。
关键点：这个工具会检查每个人的日记，确保虽然大家看到的顺序不同，但大家的日记合起来，没有产生逻辑矛盾（比如没人会看到一本还没被写出来的书）。

比喻二：每个书架的“交通指挥树” (Protocols)

对于图书馆里的每一个书架（内存位置），作者画了一棵**“交通指挥树”**。

这棵树规定了：在这个书架上，书只能按什么顺序被放上去。
比如，书架 X 上，书必须先放“红色”，才能放“蓝色”。
每个读者在放书之前，必须检查这棵树，确保自己的操作符合规则。
如果读者试图在没放“红色”之前直接放“蓝色”，工具就会报警。

结合起来：
这个工具会同时检查：

每个人的私人日记是否自洽（你看到的顺序符合逻辑吗？）。
每个人的操作是否符合交通指挥树的规则（你放书的顺序对吗？）。
最后，检查所有人的日记拼在一起，是否构成一个合法的、没有矛盾的历史。

4. 他们做了什么？

翻译官：他们把复杂的数学逻辑（SLR 逻辑）翻译成了 VerCors 工具能听懂的“语言”。
自动化：以前需要数学家花几天时间手写的证明，现在只要把程序代码喂给 VerCors-relaxed（他们的新工具），它就能自动在几秒钟内告诉你程序是对是错。
实战测试：他们用这个工具验证了文献中很多经典的、很难的“混乱”程序例子，发现它既快又准。

5. 总结：这有什么用？

想象一下，如果你要开发一个控制自动驾驶汽车或医疗设备的软件，你绝对不能容忍程序因为内存“看错了顺序”而崩溃。

这篇论文的意义在于：

它给程序员提供了一把自动化的“安全锁”。
即使是在最混乱、最追求速度的现代计算机硬件上，也能自动证明软件是安全的。
它把原本只有专家能做的复杂数学证明，变成了程序员可以日常使用的工具。

一句话总结：
作者们发明了一套**“自动监控员”**，它能理解现代计算机为了快而搞的“小动作”（弱内存），通过给每个线程发一本“私人日记”和给每个内存位置画一棵“规则树”，自动检查程序会不会因为“看花眼”而犯错，让复杂的并发程序变得安全可控。

论文技术总结：基于视图协议的弱内存程序演绎验证

1. 研究背景与问题 (Problem)

弱内存模型（Weak Memory Models）的挑战：
现代编译器和硬件为了优化性能，采用了弱内存模型。在这种模型下，程序执行无法仅通过线程指令的“顺序一致性”（Sequential Consistency, SC）交错来解释。这导致程序可能出现违反直觉的结果（例如，两个线程分别写入不同变量，但读取时却观察到乱序的值）。

现有方法的局限性：

手动证明困难： 虽然已有多种程序逻辑（如 RSL, GPS, FSL, SLR）用于形式化推理弱内存并发，但它们主要依赖繁琐的手动证明，难以自动化。
工具支持不足： 现有的演绎验证工具（如 VerCors）主要支持顺序一致性（SC）原子操作，缺乏对弱内存并发程序进行自动化演绎验证的能力。
协议粒度问题： 之前的工作通常使用“每个位置（per-location）”的协议来规范写入行为，这在处理复杂的线程间交互和推测性写入（speculative writes）时显得不够灵活。

核心问题： 如何构建一种自动化的演绎验证方法，能够利用现有的分离逻辑工具（VerCors）来验证弱内存并发程序的正确性，特别是处理乱序写入和推测性读取？

2. 方法论 (Methodology)

本文提出了一种名为 VerCors-relaxed 的方法，通过引入**基于视图的协议（View-based Protocols）**将弱内存并发编码到 VerCors 验证器中。

2.1 核心概念：基于视图的协议

作者结合了“单线程协议”和“线程局部视图”两个概念：

单线程协议（Single-thread Protocols）： 不同于以往针对每个内存位置定义一个全局协议，本文定义每个线程与每个其意图写入的内存位置组合一个独立的协议（Protocol）。协议被建模为树状结构，状态代表写入的值，边代表转换。这允许更精细地规范每个线程的写入行为。
线程局部视图（Thread-local Views）： 每个线程维护一个局部视图，记录其对所有其他线程协议状态的“观察”。
- 线程不仅跟踪自己的写入进度，还**推测（Speculate）**其他线程可能进行的写入。
- 通过视图，线程可以决定在读取操作时能观察到哪些值（即哪些协议状态是可达的）。

2.2 形式化机制

操作语义（SOS Rules）： 定义了加载（Load）和存储（Store）操作如何更新线程局部视图（ $L$ $L$ ）、最近观察到的存储操作（ $\pi$ $π$ ）以及修改顺序关系（ $\tau$ $τ$ ）。
- 写入规则： 线程根据协议转换更新自己的视图，并更新全局的修改顺序。
- 读取规则： 线程根据当前视图和修改顺序，从其他线程的协议状态中选择一个可达状态作为读取结果。
一致性检查： 验证过程通过反复应用 SOS 规则构建执行空间，并在结束时检查两个条件：
1. CC1（协议完整性）： 每个线程的协议必须到达接受状态。
2. CC2（推测有效性）： 线程对其他线程写入的推测必须是有效的（即推测的状态必须是实际可达的）。
与 SLR 逻辑的关联： 作者证明了该方法与 SLR（Separation Logic for Relaxed memory） 逻辑的松弛片段是等价的。SLR 中的时间戳（Timestamps）和观察断言（Observation assertions）被映射到本文的协议状态和视图关系上，从而保证了方法的可靠性（Soundness）。

2.3 在 VerCors 中的实现

ADT 编码： 使用 VerCors 的公理化数据类型（ADT）来定义协议状态、转换关系和接受状态。
幽灵变量（Ghost Variables）： 在方法契约（Contracts）中引入幽灵参数（如 oldLV, newLV, prevPi）来模拟视图的演变和修改顺序，而不影响实际代码执行。
权限管理： 利用基于权限的分离逻辑（PBSL）来管理对协议状态和全局视图的读写权限，确保数据竞争自由。

3. 主要贡献 (Key Contributions)

VerCors-relaxed 框架： 提出了第一个在 VerCors 中自动验证弱内存并发程序的方法，填补了自动化演绎验证工具在此领域的空白。
基于视图的协议编码： 创新性地提出了“每线程 - 每位置”的协议定义，结合线程局部视图，优雅地处理了乱序写入和推测性写入问题。
SLR 逻辑的自动化编码： 成功将先进的 SLR 程序逻辑编码到 VerCors 中，利用协议和视图自动验证文献中的经典弱内存示例。
形式化可靠性证明： 证明了基于视图协议的方法与 SLR 逻辑在松弛内存模型下是等价的，确保了验证结果的数学可靠性。

4. 实验结果 (Results)

验证对象： 编码并验证了 13 个来自文献的示例（包括 ARM-weak, COH, LB, SB, 2+2W 等经典弱内存测试用例）。
性能表现：
- 验证时间： 平均验证时间在 48 秒到 91 秒 之间（在 MacBook Pro 2020 上测试），对于演绎验证而言属于合理范围。
- 代码规模： 协议编码平均约 100 行，完整编码（含程序）约 470-750 行。
功能验证：
- 成功自动区分了**一致（Consistent）和不一致（Inconsistent）**的执行路径。
- 能够检测协议定义错误（如错误的转换边或缺失的状态），证明协议不仅用于验证程序，还能验证协议本身的正确性。
- 支持了读 - 改 - 写（RMW）操作的验证。

5. 意义与影响 (Significance)

自动化突破： 将弱内存验证从“手工证明”推向“自动化演绎验证”，显著降低了验证弱内存并发程序的门槛。
模块化验证： 该方法支持模块化验证（Modular Verification），允许逐个线程地推理，符合现代软件验证的最佳实践。
工具生态扩展： 扩展了 VerCors 工具集的能力，使其能够处理现代硬件（如 ARM, x86 TSO 等）上的弱内存行为，增强了其在工业界的应用潜力。
理论基础： 为弱内存模型的演绎验证提供了一种新的视角（基于视图的协议），为后续支持更复杂的内存模型（如 Release/Acquire 语义）奠定了基础。

总结： 本文通过引入基于视图的协议，成功在 VerCors 中实现了对弱内存并发程序的自动化演绎验证。该方法不仅理论上可靠（与 SLR 等价），而且在实际案例中表现出良好的性能和实用性，为弱内存程序的正确性保证提供了强有力的工具支持。