paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Software model-checking as cyclic-proof search

软件模型检测作为循环证明搜索
POPL 6(POPL)2022匹配度 3/10 · 论文属于软件模型检测与循环证明系统的基础理论工作,与形式化验证/程序分析有间接关联,但未涉及 LLM/Agent、浮点程序分析或贝叶斯程序分析,也不面向 ML/Agentic 程序的静态分析,因此与当前研究画像核心方向匹配度较低。引用 11 inbox
Takeshi Tsukada, Hiroshi Unno
crossref: 2026-09-10

AI 速览

一句话:将多种软件模型检测算法统一为循环证明系统中的证明搜索策略,并揭示极大保守性启发式的意义。

本文研究软件模型检测算法之间的逻辑基础与统一理解问题。作者提出将这些算法视为非标准证明系统——循环证明系统——中的证明搜索策略,从而比较不同算法、从少数简单原则重构已知算法,并免费获得可靠性证明。论文特别强调一种称为“极大保守性”的启发式,说明 property-directed reachability(PDR)等核心算法的本质,并揭示其与无限图博弈高效求解器之间此前未被认识的联系。

问题
软件模型检测算法繁多且缺乏统一逻辑基础,难以比较、重构和证明其可靠性。
方法
将软件模型检测算法刻画为循环证明系统中的证明搜索策略,并分析极大保守性等启发式。
评估
通过统一框架重构 PDR 等已知算法、给出可靠性证明,并揭示其与无限图博弈求解的联系。
原文摘要(Abstract)

This paper shows that a variety of software model-checking algorithms can be seen as proof-search strategies for a non-standard proof system, known as a cyclic proof system . Our use of the cyclic proof system as a logical foundation of software model checking enables us to compare different algorithms, to reconstruct well-known algorithms from a few simple principles, and to obtain soundness proofs of algorithms for free. Among others, we show the significance of a heuristics based on a notion that we call maximal conservativity ; this explains the cores of important algorithms such as property-directed reachability (PDR) and reveals a surprising connection to an efficient solver of games over infinite graphs that was not regarded as a kind of PDR.

链接与引用

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

BibTeX
@article{paperbot1588,
  title = {Software model-checking as cyclic-proof search},
  author = {Takeshi Tsukada and Hiroshi Unno},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {6},
  number = {POPL},
  year = {2022},
  doi = {10.1145/3498725}
}