Jul 2026· ACM Transactions on Software Engineering and Methodology· 0 citations· 72 references
TL;DR
A path-sensitive loop invariant inference approach based on Large Language Models and abstract interpretation that constructs candidate invariants as disjunctions of clause conjunctions satisfied by counterexamples across loop paths and iteratively refines them using counterexamples generated by the SMT solver during verification.
Abstract
Loop invariant inference remains a core challenge in program verification, particularly when disjunctive invariants are required. In this paper, we present a path-sensitive loop invariant inference approach based on Large Language Models (LLMs) and abstract interpretation. We apply abstract interpretation to derive initial invariants, which, if insufficient to verify the program, guide an LLM-based agent to generate more precise, path-specific clauses. The core of our method is Counterexample-Guided Clause Combination (CEGCC), a novel strategy that constructs candidate invariants as disjunctions of clause conjunctions satisfied by counterexamples across loop paths, and iteratively refines them using counterexamples generated by the SMT solver during verification. This shifts the focus of invariant synthesis from blind enumeration to semantic refinement driven by genuine counterexample verification and generation. To further refine this approach, we leverage dependencies across different loop paths, apply abstract interpretation to improve SMT solving, and deploy a second LLM-based agent for counterexample verification and mutation. Results show PAL2Inv matches state-of-the-art LLM methods on linear benchmarks and verifies 53–142% more programs on multi-phase benchmarks, while remaining competitive with specialized symbolic multi-phase verifiers.
A lightweight form of constraint solving and propagation that enables randomized testing of programs with complex preconditions is obtained, and a generator DSL whose monadic semantics are parametric over abstract domains is formalized.
Zain K. Aamer, Benjamin C. Pierce· Proceedings of the ACM on Pr...· 1 citation
LLM-generated, verifier-checked semantic hints can serve as a practical complement to conventional word-level PDR, demonstrating notable speedups and timeout avoidance on hard cases.
Guangyu Hu, Ming-Kai Miao, Zhi-Yuan Yan et al.· arXiv.org· 1 citation
This work introduces Path2Spec, a divide-and-conquer framework that leverages LLMs to extract all execution paths from an input program, generates path-specific specifications for each, and merges them into a comprehensive overall specification.
Dan Huang, Zhensu Sun, Hui-Hui Huang et al.· arXiv.org· 0 citations
Agentic-IC3 is presented, built on Pono's word-level model-checking infrastructure, which integrates a language-model agent into IC3 to guide semantic proof search using register-transfer-level (RTL) design information.
Yu-Wei Fan, SooHyuk Cho, Aarti Gupta et al.· 0 citations
Large language models (LLMs) have demonstrated great potential in code reasoning tasks, but their reasoning processes lack reliable verification mechanisms, making it difficult to ensure logical correctness. The Tree of Thoughts (ToT) framework improves reasoning by exploring multiple paths and employing backtracking,...
Hao-Liang Cheng, En-Yi Tang, Shuo-Xiao Zhang et al.· Proceedings of the ACM on So...· 0 citations
REST API constraints capture semantic properties of API responses and are essential for automated test oracle generation, but they are difficult to discover reliably. Static approaches infer constraints from API specifications and documentation, but their results may be affected by incomplete, ambiguous, or outdated sp...
Tuong Nguyen, Huy Nguyen, J. C. A. Valenzuela et al.· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.