paperbot · PL 论文追踪

全部论文 待读 收藏

P2 A Hoare Logic for Symmetry Properties

面向对称性质的 Hoare 逻辑
OOPSLA 9(OOPSLA2)2025匹配度 3/10 · 该论文属于形式化验证/程序分析方向,提出了新的 Hoare 逻辑并实现原型工具,这与用户对形式化验证和程序分析的兴趣有一定交集;但它不涉及 LLM/Agent 与静态分析的交叉,也不涉及浮点程序分析或贝叶斯程序分析,因此与用户当前核心研究方向匹配度较低。引用 0 inbox
Vaibhav Mehta, Justin Hsu
crossref: 2026-09-10

AI 速览

一句话:提出基于群作用的 Hoare 逻辑,用于验证命令式程序的对称性质,并实现原型工具 SymVerif 发现实际模型错误。

许多程序正确性性质可表述为对称性,但现有形式化方法对这类性质的推理支持有限。作者针对以群作用表达的广泛对称性质,设计群作用的语法与自然蕴涵关系,支持标准构造;进而提出一种 Hoare 风格逻辑,用群作用替代传统前置/后置条件断言,验证命令式程序的对称性质。作者实现原型工具 SymVerif,并在手工基准上验证对称性质。评估表明该方法可行,且工具在 McLachlan 与 Quispel [Acta Numerica 2002] 描述的动态系统模型中发现一处错误。

问题
现有形式化方法难以支持以群作用表达的对称性质,因而无法系统验证这类程序正确性属性。
方法
设计群作用语法与蕴涵关系,并构建以群作用为前置/后置条件的 Hoare 风格逻辑,用于命令式程序验证。
评估
实现原型工具 SymVerif,在一组手工基准上验证对称性质,并在一个已发表动态系统模型中发现错误。
原文摘要(Abstract)

Many natural program correctness properties can be stated in terms of symmetries, but existing formal methods have little support for reasoning about such properties. We consider how to formally verify a broad class of symmetry properties expressed in terms of group actions. To specify these properties, we design a syntax for group actions, supporting standard constructions and a natural notion of entailment. Then, we develop a Hoare-style logic for verifying symmetry properties of imperative programs, where group actions take the place of the typical pre- and post-condition assertions. Finally, we develop a prototype tool SymVerif, and use it to verify symmetry properties on a series of handcrafted benchmarks. Our tool uncovered an error in a model of a dynamical system described by McLachlan and Quispel [Acta Numerica 2002].

链接与引用

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

BibTeX
@article{paperbot2962,
  title = {A Hoare Logic for Symmetry Properties},
  author = {Vaibhav Mehta and Justin Hsu},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {9},
  number = {OOPSLA2},
  year = {2025},
  doi = {10.1145/3763080}
}