paperbot · PL 论文追踪

全部论文 待读 收藏

P2 The Undecidability of Overfitting in Automated Program Repair

自动程序修复中过拟合的不可判定性
ICSE Proceedings of the IEEE/ACM 48th International Conference on Software Engineering2026匹配度 4/10 · 论文从规约缺失下的不可判定性角度论证 APR 过拟合是结构性问题,属于 PL 理论/程序修复方向,与用户关注的静态分析理论形式化有一定气味相投之处,但既不涉及 ML/Agent 程序、也不涉及浮点或贝叶斯程序分析,且为立场性短文,缺少工程实现与 benchmark 验证。引用 0 inbox
Omar I. Al-Bataineh
crossref: 2026-09-12

AI 速览

一句话:论证过拟合并非测试套件不足导致的可修复缺陷,而是规约缺失下不可判定性的结构性后果。

本文针对自动程序修复(APR)中长期存在的过拟合问题提出一种不同的视角。通常过拟合被归因于测试套件薄弱或不完整,因而被视为可通过更好的测试或修补手段消除的工程缺陷。作者主张,当完整规约不可获得时,测试套件只能充当部分正确性判定器(partial correctness oracle),于是修复过程中出现的过拟合并非偶然的副作用,而是问题本身不可判定性的必然结果:在仅有部分判据的前提下,任何修复系统都无法保证所选补丁在全规约意义下正确。基于这一重新定位,论文讨论了该视角对 APR 研究与评价的含义,指出过拟合不应被当作可求解的 bug,而应被理解为修复问题的内在边界,并呼吁建立新的研究议程,在此边界内发展量化、解释并最终对过拟合进行推理的方法。全文为立场性论述,未给出实验评估。

问题
自动程序修复中过拟合普遍存在,通常被归因于测试套件薄弱;本文追问过拟合究竟是可修复的工程缺陷,还是问题本身固有的界限。
方法
通过论证当完整规约不可得时测试套件只能作为部分正确性判定器,从而将过拟合归约为不可判定性的结构性后果,并据此讨论其对 APR 的意涵。
评估
本文为立场/观点性论文,未开展实证评估或工具实现,其论证以概念分析与逻辑推理为主,并据此提出研究议程。
原文摘要(Abstract)

Overfitting is one of the most persistent challenges in automated program repair (APR), typically attributed to weak or incomplete test suites. In this paper, we take a different view: overfitting is not just a nuisance but a fundamental consequence of undecidability. When full specifications are unavailable, test suites serve only as partial correctness oracles. As a result, overfitting emerges as a structural outcome rather than an incidental defect. This perspective reframes overfitting not as a solvable bug in APR, but as an inherent boundary of the problem itself. We discuss the implications of this shift and call for a research agenda that works within these limits, developing methods to quantify, explain, and ultimately reason about overfitting as an unavoidable aspect of repair.

链接与引用

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

BibTeX
@inproceedings{paperbot11997,
  title = {The Undecidability of Overfitting in Automated Program Repair},
  author = {Omar I. Al-Bataineh},
  booktitle = {ICSE},
  year = {2026},
  doi = {10.1145/3786582.3786802}
}