paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Causal Detection in Linear Temporal Counterexamples

线性时序反例中的因果检测
FSE Proceedings of the 33rd ACM International Conference on the Foundations of Software Engineering2025匹配度 3/10 · 论文研究 LTL 反例的因果诊断算法,属于形式化验证/模型检测方向,与用户关注的 PL 与 LLM/Agent 交叉(如用 LLM 改进验证、分析 Agentic 程序、浮点/贝叶斯程序分析与 LLM 交叉)没有直接关联。引用 1 inbox
Herong Meng, Dalal Alrajeh
crossref: 2026-09-12dblp: 2026-09-12

AI 速览

一句话:提出 LTL 反例的合取式因果定义与计算算法,改进模型检测反例诊断。

模型检测可判断系统是否满足规约,但 LTL 性质违反的反例诊断仍困难。现有因果推理方法在表达力、复杂依赖识别或计算可行性上受限。本文重新定义 LTL 反例中的 cause,使其支持合取原因(conjunctive causes),并给出计算这些原因的新算法。作者在工业规约基准上与基线因果计算算法比较;在所有比较中,新算法要么包含基线原因、要么识别更强原因,要么以可解释方式与基线不同,表明其能增强反例分析。

问题
LTL 反例中的性质违反诊断需要有效因果解释,但现有因果方法表达力有限、难以识别复杂依赖或计算不可行。
方法
提出支持合取原因的 LTL 反例 cause 修订定义,并设计计算这些原因的新算法,与基线因果计算算法对比。
评估
在工业规约基准上比较新算法与基线;结果显示新算法包含基线原因、识别更强原因或以可解释方式不同,证明其有效性。
原文摘要(Abstract)

Model checking and verification play a crucial role in ensuring the correctness of software systems by systematically analyzing whether a system satisfies desired specifications. Diagnosing property violations in LTL counterexamples is essential for debugging and refining software, helping developers identify faults and ensure requirement compliance. Several approaches have considered the use of causal reasoning to aid in the identification and explanation of counterexamples. However, these methods are often limited in their expressivity, ability to recognize complex dependencies in system behaviors, or computational feasibility. This paper proposes a revised definition of causes for LTL violations in counterexamples, allowing for the identification of conjunctive causes. Additionally, we introduce a novel algorithm for computing such causes and compare it against a baseline causal computation algorithm using a benchmark of industrial specifications. In all comparisons, our algorithm either subsumes baseline causes, identifies stronger causes, or diverges from the baseline in explainable ways, demonstrating its effectiveness in enhancing counterexample analysis.

链接与引用

DOI 原文 · DBLP

BibTeX
@inproceedings{MengA25,
  title = {Causal Detection in Linear Temporal Counterexamples},
  author = {Herong Meng and Dalal Alrajeh},
  booktitle = {FSE},
  year = {2025},
  doi = {10.1145/3696630.3731617}
}