paperbot · PL 论文追踪

全部论文 待读 收藏

P2 CAAT: consistency as a theory

CAAT:一致性作为一种理论
OOPSLA 6(OOPSLA2)2022匹配度 3/10 · 论文属于程序验证与内存一致性模型的形式化理论/求解器工作,虽与静态分析和形式化验证的大方向弱相关,但未涉及用户核心关注的 LLM/Agent 与静态分析/形式化验证交叉、浮点程序分析或贝叶斯程序分析。引用 11 inbox
Thomas Haas, Roland Meyer, Hernán Ponce de León
crossref: 2026-09-10

AI 速览

一句话:提出一族可刻画多种内存一致性模型的逻辑理论及通用高效求解器,并用于有界模型检测。

并发程序语义受内存一致性模型影响,现有验证工具往往针对特定模型。本文提出一族逻辑理论,用于刻画抽象的一致性概念,并构造对族内所有理论通用的高效求解器。该理论族足以精确表达 TSO、POWER、ARMv8、RISC-V、RC11、IMM 及 Linux 内核内存模型等。作者将求解器集成到惰性 SMT 方案中,作为有界模型检测工具的后端。与相关验证工具的实验对比表明,该方法兼具灵活性,并在复杂内存模型下的挑战性程序上展现出有希望的性能。

问题
如何用一个统一且高效的逻辑框架表达多种内存一致性模型,并支持并发程序的有界模型检测?
方法
提出参数化逻辑理论族来捕获抽象一致性,并实现对所有成员通用的理论求解器,再将其集成到惰性 SMT 方案中作为有界模型检测后端。
评估
在 TSO、POWER、ARMv8、RISC-V、RC11、IMM 和 Linux 内核内存模型等例子上考察表达力,并与相关验证工具对比求解性能。
原文摘要(Abstract)

We propose a family of logical theories for capturing an abstract notion of consistency and show how to build a generic and efficient theory solver that works for all members in the family. The theories can be used to model the influence of memory consistency models on the semantics of concurrent programs. They are general enough to precisely capture important examples like TSO, POWER, ARMv8, RISC-V, RC11, IMM, and the Linux kernel memory model. To evaluate the expressiveness of our theories and the performance of our solver, we integrate them into a lazy SMT scheme that we use as a backend for a bounded model checking tool. An evaluation against related verification tools shows, besides flexibility, promising performance on challenging programs under complex memory models.

链接与引用

DOI 原文 · PDF(开放获取) ·

BibTeX
@article{paperbot1445,
  title = {CAAT: consistency as a theory},
  author = {Thomas Haas and Roland Meyer and Hernán Ponce de León},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {6},
  number = {OOPSLA2},
  year = {2022},
  doi = {10.1145/3563292}
}