用部分契约实现高效可靠的代码变更验证,无需完整规格说明。
Partial Contracts Suffice: Sound, LLM-Inferred Regression Verification
- 基于调用者足够性构建部分契约,自动从反例中推导。
- 在多数情况下,部分契约已达最优紧致度,验证结果无误。
- 适合关注代码演进安全性的开发者与形式化验证研究者。
软件持续演化,但确保补丁不破坏原有行为却难以实现。现有回归验证方法需全程序推理或依赖手动编写规格,实用性差。本文提出首个基于契约的回归验证工具:通过证明所有函数版本行为一致确保契约正确性,并利用假设-保证机制验证程序流。研究发现,仅满足调用者需求的部分契约已足够,无需完整行为规范。在Frama-C-Problems上对推导出的契约进行强化测试,结果表明其紧致度几乎不变;多数目标下部分契约与强化契约等价。该验证过程可靠:在EqBench-C第三方套件上未产生虚假等价证明,零误报,并发现九对被错误标记为等价的实例,优于同期工具。契约由检查器自身反例自动推导,无需额外规格步骤;在Frama-C-Problems和ANSSI X509解析器上达到与AutoSpec、Preguss相当的验证率,且通过结果至少保证‘安全保持的条件等价’——即强制执行加调用者足够性。
原文摘要 · Abstract (English)
Software evolves continuously, yet ensuring that a patch preserves intended behavior without re-verifying an entire codebase remains difficult. Regression verification addresses this problem, but existing techniques require expensive whole-program reasoning or rely on manually written specifications that are rarely available in practice. We present the first contract-based regression verification tool. Contract soundness is ensured by proving all function versions match the behavior. The contract then verifies program flow via assume-guarantee. We ask whether a partial, caller-sufficient contract, rather than a full behavioral specification, is enough. On Frama-C-Problems we strengthen each inferred contract past what the caller needs and measure how much tighter it becomes. It barely moves: for most targets in every model the caller-sufficient contract is already the tightest the loop reaches, and our tightness comparator rates the partial and strengthened contracts equivalent for the large majority of targets it can compare. Partial-spec contracts thus capture nearly all the attainable tightness, so stopping at caller-sufficiency costs almost nothing. The regression check underneath is sound: on the third-party EqBench-C suite it never fabricates an equivalence, returning zero false proofs and reporting an unprovable difference instead. It also surfaced nine pairs that EqBench mislabels as equivalent, more than a concurrent tool reports. The contracts themselves are inferred automatically from the checker's own counterexamples, with no separate specification step; on Frama-C-Problems and the ANSSI X509 parser this reaches a verification rate comparable to tools AutoSpec and Preguss, while a passing result certifies at least as strong a property, which we call \emph{safety-preserving conditional equivalence}: enforcement plus caller-sufficiency.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。