ConVer: Using Contracts and Loop Invariant Synthesis for Scalable Formal Software Verification

ConVer is a compositional verification tool that leverages large language models and contract synthesis to formally verify C programs more efficiently than traditional bounded model checking. The tool achieves 82-96% success on simple benchmarks and 67% on complex programs, demonstrating significant progress in automated software verification despite limitations on recursive and loop-intensive code.

ConVer addresses a fundamental challenge in formal software verification: the state-space explosion problem that makes verifying large C programs computationally intractable. Traditional bounded model checking requires encoding entire state spaces by unrolling all constructs, creating exponential complexity. By decomposing verification hierarchically—using LLMs to synthesize function contracts and applying CEGAR-CEGIS refinement loops—ConVer substantially reduces the computational burden while maintaining formal guarantees.

The tool represents a meaningful convergence of AI and formal methods. Rather than treating LLMs as black boxes, ConVer strategically uses them to propose candidate contracts, then validates these proposals through automated checking and refinement. The 93-95% single-iteration convergence rate on simple benchmarks suggests the LLM contract synthesis is remarkably effective for well-structured programs. However, performance degrades significantly on complex programs (55-64% on VerifyThis), indicating current LLMs struggle with reasoning about recursive structures and complex loop invariants.

For the software verification industry, ConVer demonstrates that AI-assisted formal methods can scale beyond academic toy problems. Security-critical domains like parsers and embedded systems require this kind of scalable verification. The introduction of ESBMC-LF as a transpilation bridge enables verification of programs written in formal specification languages, expanding ConVer's applicability. However, the tool's 33-50% success rate on real-world programs like X.509 parsers reveals substantial work remains before production deployment. The research validates compositional verification as viable while exposing limitations in current LLM reasoning for complex control flow, driving future development toward hybrid human-AI verification workflows.

• →ConVer achieves 82-96% verification success on simple C programs using LLM-synthesized contracts and automated refinement loops.
• →Compositional verification with CEGAR-CEGIS refinement reduces state-space explosion significantly compared to traditional bounded model checking.
• →Performance drops dramatically on complex programs (33-50% on real-world parsers), indicating challenges with loop invariant synthesis remain.
• →LLMs effectively propose function contracts but struggle with recursive and loop-intensive code, requiring domain-specific improvements.
• →The approach bridges formal methods and AI, enabling scalable verification for security-critical software when combined with automated tooling.