TL;DR
This paper introduces SESpec, a novel framework that combines symbolic execution with Large Language Models (LLMs) to automatically generate formal program specifications (like loop invariants and pre/postconditions) for C code. This approach significantly improves the accuracy and robustness of specification generation, even for complex programs with data structures, by leveraging the strengths of both symbolic reasoning and LLM capabilities.
What Problem Does This Paper Address?
Generating formal specifications for existing, often complex, C code is crucial for understanding, reusing, and verifying software. However, this task is notoriously challenging due to intricate control flow (loops, branches) and data structures (structs, pointers, linked lists). Traditional methods often struggle with scalability, expressiveness, or require significant manual guidance. While LLMs show promise in understanding code, they tend to produce syntactically incorrect or semantically imprecise specifications, often suffering from hallucinations. Existing LLM-based approaches also typically rely on predefined verification goals, limiting their ability to capture a program's overall functional correctness.
Methods
SESpec employs a multi-stage approach:
- Default Precondition Generation: Uses symbolic execution with a flattened memory model to generate weakest preconditions ensuring memory-safe execution.
- Symbolic Execution: Tracks path conditions and state transitions to derive precise specifications for loop-free code segments.
- Function Call Handling: Uses a call stack to process nested function calls compositionally, generating specifications for callees and reusing them in callers.
- Loop Invariant Generation:
- Loop Analysis: Identifies unchanged and inductively updated variables within a loop.
- Template Generation: Creates ACSL-style invariant templates based on symbolic execution results and variable analysis.
- LLM-based Synthesis: Guides an LLM to fill these templates, leveraging its reasoning capabilities while being constrained by the structure and context.
- Iterative Refinement: Uses a verifier (Frama-C) to check generated invariants and provides feedback to the LLM for iterative repair, strengthening, or regeneration. This process is crucial for ensuring both validity and accuracy.
- Postcondition Generation: Synthesizes postconditions summarizing the callee's functional behavior.
The core novelty lies in the tight integration of symbolic execution (for precise semantic context and structural guidance) with LLMs (for flexible reasoning and template filling), and a robust refinement loop driven by formal verification.
Datasets
The evaluation uses a combination of existing benchmarks and newly introduced ones:
- Existing Benchmarks: SyGuS, OOPSLA, SV-COMP, NLA, numer-S, Frama-C, list-S.
- Newly Introduced Benchmarks:
- pIp: Extracted from an aerospace system, featuring complex structs, pointers, and branching.
- list-S: Includes singly linked list programs from SLING and SV-COMP.
- numer-S: A collection of linear and nonlinear loops for numerical programs.
Key Insights and Ideas
- Synergy of Symbolic Execution and LLMs: Combining symbolic execution's precision with LLMs' flexibility is key. Symbolic execution provides structured context and constraints, guiding the LLM and mitigating hallucinations.
- Template-Guided LLM Generation: Using pre-defined ACSL templates significantly improves the LLM's ability to generate syntactically correct and semantically meaningful specifications, shifting the task from full generation to template completion.
- Iterative Refinement is Crucial: Formal verification feedback is essential for correcting and strengthening LLM-generated specifications, ensuring they are not only valid but also accurate and meet verification goals.
- Handling Complex Data Structures: The flattened memory model and inductive predicates enable the framework to effectively handle programs with structs, pointers, and linked lists, a common weakness in other approaches.
- Goal-Independent Specification Generation: The approach can generate strong specifications even without explicit verification goals, focusing on capturing the program's overall functional correctness.
Key Results
- High Success Rate: SESpec successfully verified 354 out of 395 benchmark programs (nearly 90%).
- Outperforms State-of-the-Art: Consistently outperforms LLM-based approaches like AutoSpec and ACInv, especially on complex benchmarks. For instance, on the pIp benchmark, SESpec achieved an average 50% higher success rate than AutoSpec.
- Robustness to Model Choice: The framework shows consistent improvements with stronger LLM models, and the performance gap between models is narrowed compared to other approaches.
- Effective on Complex Programs: Achieves good performance on programs with nested loops, complex data structures, and inductive operations, which are challenging for other methods.
- Minimal Performance Drop Without Goals: Specification generation accuracy drops only slightly when verification goals are masked, demonstrating its ability to generate meaningful specifications autonomously.
Limitations and Future Work
- Limitations:
- Does not yet cover recursive functions or programs involving library functions and system calls.
- Performance drop in the refinement process when targeting specific verification goals (though overall quality remains high).
- Challenges with highly complex nested loops where correlations among multiple induction variables arise.
- Future Work:
- Extend support to recursive data structures and functions.
- Strengthen invariant generation for challenging cases like nested loops.
- Integrate symbolic sampling and targeted training strategies to improve precision for nested loops.
Summary updated