循环终止证明不再只靠模板:RAINFALL 让大模型填断言,358 个 C 程序解出 323 个
核心概要
证明循环终止通常要人工设计排序函数模板,模板选不好就难以覆盖非线性更新和复杂控制流。RAINFALL 把排序函数合成改写成代码断言补全:在程序中插入四个占位槽,由大模型填写,再用符号验证器检查,失败时把诊断信息回灌给模型迭代修正。在 358 个终止 C 程序上,使用 MiniMax V2.7 的 RAINFALL 为 323 个程序合成出可验证的排序函数(90.22%),比 SV-COMP 2026 终止类冠军 PROTON 2.1 多解 12 个;两者合用达到 346 个(96.65%)。
深度剖析
排序函数的构造从依赖预设模板转向由大模型补全程序中的断言槽位,再交给符号验证器判定。 经典方法把合成问题化为在预定义模板上的约束求解,效果取决于是否有合适的模板,面对非线性更新和复杂控制流时受限。 在两个公开基准套件共 358 个终止 C 程序上,使用 MiniMax V2.7 的 RAINFALL 解出 323 个(90.22%),而 PROTON 2.1 为 311 个(86.87%),AProVE 为 282 个(78.77%),UAutomizer 为 283 个(79.05%),LOOPY 为 264 个(73.74%)。
每个循环被插入四个占位槽,分别用于声明记录排序值的辅助变量、在循环体开头保存上一轮取值、在循环体末尾更新当前取值、以及写入断言。 大模型因此只做受限的槽位填充,而不是自由生成整段代码,从而降低改动原程序逻辑的风险。 验证流程先用语法等价检查确认原程序代码未被修改,再检查断言是否覆盖严格递减、非负和终止条件,最后用 UAutomizer 做安全性检查;任一环节失败都会把诊断信息写回提示词。
验证器给出的诊断信息被翻译成自然语言反馈,用于下一轮提示,形成生成、验证、修正的循环。 此前的 LOOPY 在候选排序函数不正确时直接重新询问模型,不把验证反馈带入下一轮。 在 BS-F 上,RAINFALL 用 6 次大模型查询解出 129 个程序,用 12 次查询解出 156 个;LOOPY 用 12 次查询解出 124 个,限制到 6 次时降到 107 个。
启示与展望
评估覆盖 LOOPY 与 FreqTerm 提供的两个公开基准套件,共 358 个终止 C 程序,程序以单个 while 循环建模,for 循环被转换为等价的 while 循环;实验使用 Clang 构建和操作抽象语法树,并以 UAutomizer 作为后端安全验证器。
在 BS-F 上 RAINFALL 未解出的 14 个程序中,3 个是模型给出了正确的循环界而非排序函数,4 个是模型在初始提示下没有返回结果,5 个是 UAutomizer 在 60 秒内超时,2 个在 12 次大模型查询后仍未成功。使用 Qwen-Plus 时 RAINFALL 的表现低于 ddlTerm 和 PROTON。作者指出基准可能已出现在大模型训练数据中,并说明在更多基准和真实程序上的评估仍待开展。
