paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Accurate Inference of Termination Conditions

终止条件的精确推断
ICSE Proceedings of the 2026 IEEE/ACM 48th International Conference on Software Engineering2026匹配度 4/10 · 该论文属于程序验证中的终止条件推断,与形式化验证/静态分析有邻接关系,但未涉及用户核心关注的LLM/Agent、浮点程序分析或贝叶斯程序分析,也没有AI与PL的交叉方法。引用 0 inbox
Biting Huang, Zhilei Han, Fei He
crossref: 2026-09-12

AI 速览

一句话:提出首个能精确刻画终止状态的终止条件推断方法,并证明其正确、精确、可终止且相对完备。

本文研究如何推断精确的终止条件,即所生成条件能准确刻画程序的终止状态集合。作者提出一个简洁而有效的框架:迭代识别并移除非终止状态,同时调用终止性证明器验证当前条件。该框架用数据驱动的证明器实例化,并设计多路数据共享机制以增强证明器之间的交互。论文证明该方法具备正确性、精确性、可终止性和相对完备性,并引入循环集泛化技术加速迭代收敛。基于文献程序基准的评估表明,该实现显著优于当前最先进工具 Acabar,能生成更精确的终止条件,且所提技术对加速收敛起到关键作用。

问题
现有终止性分析多关注整体程序是否终止,或推断出的终止条件不够精确,难以精确刻画哪些状态会终止。
方法
提出迭代识别并移除非终止状态的框架,用终止性证明器验证当前条件,并以数据驱动证明器实例化,辅以多路数据共享和循环集泛化加速收敛。
评估
在文献中的程序基准上实现并评估,与最先进工具 Acabar 比较,结果显示能生成更精确的终止条件,且所提技术显著加快迭代收敛。
原文摘要(Abstract)

We present the first approach to infer termination conditions that are accurate in the sense of precisely characterizing terminating states. It builds on a simple but effective framework where non-terminating states are iteratively identified and removed, and a termination prover is employed to validate the current condition. We instantiate the framework with data-driven provers and design a multi-way data sharing mechanism to enhance their interaction. Our proofs show that this method is correct, accurate, terminating, and relatively complete. Additionally, we introduce generalization techniques for recurrent sets to accelerate the iteration process. Evaluation on a benchmark of programs from the literature shows that our implementation significantly outperforms the state-of-the-art tool Acabar, producing much more accurate termination conditions, with the proposed techniques playing a crucial role in speeding up the convergence of the process.

链接与引用

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

BibTeX
@inproceedings{paperbot11950,
  title = {Accurate Inference of Termination Conditions},
  author = {Biting Huang and Zhilei Han and Fei He},
  booktitle = {ICSE},
  year = {2026},
  doi = {10.1145/3744916.3764568}
}