Interpretation is widely used to determine programs' numerical properties. However, current abstract domains primarily focus on mathematical semantics, which do not fully capture the complexities of real-world programs relying on machine integer semantics and involving extensive bit-vector operations. This paper presents a solution that combines a bit-level abstraction and a word-level abstraction to capture machine integer semantics. First, we generalize the bit-level abstraction used in the Linux eBPF verifier for determining known and unknown bits of real-world programs, by supplementing all required operations as a standard abstract domain. Based on this abstraction, we design an abstract domain that is signedness-aware and simultaneously retains both the above bit-level and the word-level bound information. These two levels of information cooperate via a standard reduced product operation to improve analysis precision. We implement the proposed domains in the Crab analyzer and the out-of-kernel eBPF verifier PREVAL. Experiments demonstrate their effectiveness in analyzing SV-COMP benchmark programs, assisting hardware designs, and eBPF verification.
Whether a counterexample is genuine or spurious fundamentally influences the effectiveness and completeness of loop invariant inference, which is a core component of automated program verification. However, reliably determining the validity of a counterexample remains a challenging task. In this paper, we present a systematic evaluation of large language models (LLMs) on this problem. We construct a benchmark of program states that serve as counterexamples, categorized into three representative types: (i) pre-states of inductive counterexamples derived from LLM-proposed invariants and (ii–iii) boundary states derived from correct inductive invariants, where the states themselves either violate (ii) or satisfy (iii) the program’s precondition. Ground-truth labels are established using a state-of-the-art program verifier. We evaluate multiple LLMs under diverse prompting strategies. Our results show that LLMs perform well on the first two types of counterexamples in the benchmark but poorly on the third. Moreover, LLMs are substantially more accurate in classifying spurious counterexamples than genuine ones. These findings offer valuable guidance for future research on LLM-assisted loop invariant inference.
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.