💻 computer science

Guiding Symbolic Execution with Static Analysis and LLMs for Vulnerability Discovery

The paper presents SAILOR, a novel framework that automates symbolic execution harness construction by integrating static analysis for vulnerability targeting and LLMs for iterative driver synthesis, enabling the discovery of 379 previously unknown memory-safety vulnerabilities across 10 large C/C++ projects where existing baselines failed.

Original authors: Md Shafiuzzaman, Achintya Desai, Wenbo Guo, Tevfik Bultan

Published 2026-04-09

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Md Shafiuzzaman, Achintya Desai, Wenbo Guo, Tevfik Bultan

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to find hidden traps in a massive, ancient castle (a huge software codebase). You have three powerful tools, but each has a major flaw on its own:

The Static Analyzer (The Map Reader): This tool can scan the entire castle in seconds and point out 10,000 spots that look suspicious. But it's terrible at context; it flags everything from a loose brick to a whole wall, creating a mountain of false alarms.
The Symbolic Executor (The Super-Tester): This is a robot that can walk through every possible hallway in the castle at once to see if a trap actually triggers. It's incredibly precise. However, it can't start walking until you give it a specific door to enter, a map of the furniture, and a list of rules. Writing these instructions manually for a 1.8-million-line castle takes years.
The LLM (The Genius Intern): This is a super-smart AI that knows how to write code and understands the castle's layout. But if you just ask it, "Find the traps," it might hallucinate (make things up) or guess wrong because it can't actually walk the halls to prove a trap exists.

The Problem:
For years, finding deep, hidden software bugs has been stuck in a bottleneck. You need the Super-Tester (Symbolic Execution) to prove a bug is real, but you can't use it because you can't write the instructions (the "harness") fast enough.

The Solution: "Sailor"
The authors created a system called Sailor that acts like a perfect detective team, combining all three tools into a seamless assembly line. Think of it as a three-stage relay race:

Phase 1: The Scout (Static Analysis)

Instead of asking the AI to guess where to look, the Map Reader (Static Analysis) scans the code first. It doesn't try to prove the bug exists yet; it just says, "Hey, look at line 2699 in this file. Someone is copying data without checking the size. That looks risky."

Analogy: It's like a security guard pointing a flashlight at a specific, suspicious door and handing a note to the next person: "Check this door. It might be unlocked."

Phase 2: The Architect & The Builder (LLM + Symbolic Execution)

This is the magic part. The Genius Intern (LLM) takes that note and tries to build a "test room" (a harness) to see if the door actually opens.

The Struggle: The Intern builds a room, but it's missing a wall or has the wrong door handle. The Super-Tester (Symbolic Execution) tries to walk in, hits a wall, and says, "Error: Door handle missing."
The Fix: The Intern reads the error, fixes the room, and tries again. It does this over and over (iterative refinement), learning from every mistake, until it builds a perfect test room that leads exactly to the suspicious door.
The Test: Once the room is built, the Super-Tester walks through it. If it finds a trap (a bug), it doesn't just say "I think so." It produces a key (concrete input) that proves the trap works.

Phase 3: The Reality Check (Concrete Validation)

The Super-Tester is great, but sometimes it gets lost in a dream world. To be 100% sure, the team takes the key the Super-Tester made and tries it on the real, unmodified castle.

Analogy: They hand the key to a human guard and say, "Try this key on the real door." If the door opens and the trap snaps shut, BINGO! It's a real vulnerability. If the key doesn't work on the real door, it was a false alarm, and they discard it.

Why is this a big deal?

The team tested Sailor on 10 massive, real-world software projects (like the tools that power the internet, image processing, and security).

The Result: Sailor found 379 brand-new, previously unknown security bugs (memory safety issues).
The Comparison: When they compared Sailor to other methods:
- Just using the AI alone found almost nothing real.
- Just using the Super-Tester with human-written instructions found almost nothing (because humans are too slow to write instructions for everything).
- Sailor was 30 times more effective than the next best method.

The Takeaway

Sailor solves the "scaling" problem. It uses the Map Reader to narrow the search, the Genius Intern to build the test environment automatically, and the Super-Tester to prove the bug is real, all while using a Reality Check to ensure no false alarms slip through.

It's like automating the entire process of finding a needle in a haystack: instead of one person looking for hours, you have a robot that finds the haystack, a smart assistant that builds a magnet, and a final test to make sure the magnet actually picked up a needle.

1. Problem Statement

Automated vulnerability detection in large-scale C/C++ codebases faces a "scalability vs. precision" trade-off:

Static Analysis (SA): Scales well to millions of lines of code (LOC) but suffers from high false-positive rates and cannot determine if a vulnerability is actually exploitable.
Fuzzing: Effective at finding crashes but struggles to reach deep library internals that require complex, precisely structured program states.
Symbolic Execution (SE): Offers high precision by treating inputs as symbolic values and using constraint solvers to generate concrete witness inputs. However, SE does not scale to large codebases because:
1. Path Explosion: The number of execution paths grows exponentially.
2. Harness Construction: SE requires a "harness" (a driver program) to set up symbolic state, model dependencies (stubs), and specify assertions. Writing these harnesses manually is time-consuming, requires deep expertise, and is the primary bottleneck preventing SE adoption at scale.
3. LLM Limitations: While Large Language Models (LLMs) can reason about code, they lack formal correctness guarantees and often hallucinate vulnerabilities or fail to generate valid execution paths without feedback.

Core Challenge: How to automate the construction of SE harnesses for large codebases to achieve the precision of SE with the scalability of SA and the reasoning capabilities of LLMs.

2. Methodology: The Sailor Pipeline

The authors present Sailor (Static Analysis Informed and LLM-Orchestrated Symbolic Execution), a fully automated three-phase pipeline.

Phase 1: Static Analysis Informed Target Generation

Instead of scanning the whole codebase with SE, Sailor uses SA to narrow the search space.

Fact Generation: A CodeQL database is built, and a suite of 34 memory-safety queries (13 standard, 21 custom) scans the source code.
Fact Enrichment: For each flagged location, Sailor extracts contextual "fact packs," including suspect function calls, pointer variables, length variables, and build context (include paths).
Specification Generation: The system assembles a Vulnerability Specification for each candidate. This includes:
- The candidate location ( $\ell$ ).
- A natural language description of the vulnerability.
- An Assertion Template (e.g., for CWE-120, the template is n <= min(len(dst), len(src))).
- An entrypoint selection strategy (defaulting to inferring the nearest non-static caller).
Output: A set of self-contained JSON specifications that can be processed independently and in parallel.

Phase 2: LLM-Orchestrated Symbolic Execution

This is the core contribution. An LLM acts as an orchestrator to synthesize and iteratively refine the SE harness ( $H$ ) based on feedback.

Driver Synthesis: The LLM generates a main() function that:
- Allocates necessary structures (e.g., elf_x86_link_hash_table).
- Declares specific fields as symbolic (using klee_make_symbolic) to explore paths.
- Adds klee_assume constraints to bypass guards (e.g., null checks) that would prevent reaching the vulnerable line.
Stub Synthesis: The LLM creates a "code slice" containing only the path from the entry point to the vulnerability. It replaces off-path branches with if(0), loops with if(1), and external dependencies with stubs.
- Crucial Detail: Stubs for off-path functions return symbolic values if they influence the path, or hardcoded defaults otherwise. For Use-After-Free (CWE-416), the free() stub must call the real free().
Assertion Instantiation: The LLM encodes the safety property. It places a klee_assert(0) after the vulnerable statement to check reachability and adds constraints to the driver that violate the safety property (e.g., klee_assume(sz > 16) to trigger a buffer overflow).
Iterative Refinement Loop: The harness is compiled and executed by KLEE (the SE engine).
- Feedback: If compilation fails or SE reports "not reached," the error is fed back to the LLM.
- Correction: The LLM fixes type mismatches, missing headers, or overly aggressive path pruning.
- Termination: The loop continues until a bug is triggered (producing a .ktest witness file), the turn budget is exhausted, or the site is reached but no bug is found (likely a false positive).

Phase 3: Concrete Validation

To eliminate false positives caused by unrealistic harness generation or LLM hallucinations:

Replay Driver: The symbolic driver is converted to a concrete driver by replacing klee_make_symbolic calls with memcpy of the actual bytes from the .ktest witness file.
Execution: The unmodified project source is compiled with AddressSanitizer (ASan). The replay driver is linked against this instrumented binary.
Verdict: A vulnerability is only confirmed if ASan reports a crash (e.g., heap-buffer-overflow) with a stack trace inside the project's source code.

3. Key Contributions

Sailor Pipeline: The first fully automated system that combines SA for targeting, LLMs for harness synthesis, SE for path precision, and concrete execution for ground-truth validation.
Automated Harness Construction: Solves the scalability bottleneck of SE by using an LLM to iteratively refine drivers and stubs against compiler and SE feedback, removing the need for manual harness writing.
Evaluation at Scale: Demonstrated on 10 open-source C/C++ projects totaling 6.8 Million Lines of Code (LOC).
Novelty in LLM Usage: Unlike previous works that use LLMs for direct detection, Sailor uses LLMs strictly as a synthesis engine guided by formal execution feedback.

4. Experimental Results

The evaluation was conducted on 10 projects (including Binutils, FFmpeg, OpenSSL, SQLite, etc.).

Total Discoveries: Sailor discovered 379 unique, previously unknown memory-safety vulnerabilities (resulting in 421 confirmed crashes).
Comparison with Baselines:
- B1 (Human-written SE harnesses): 0 confirmed vulnerabilities (harnesses were too broad or failed to compile).
- B2 (LLM-generated SE harnesses, no iteration): 0 confirmed (high compilation failure rate due to hallucinations).
- B3-B5 (LLM-only or Agentic detection): Found at most 12 confirmed vulnerabilities. They suffered from massive false-positive rates (88–99%).
- Sailor: Found 379 confirmed vulnerabilities, outperforming the strongest baseline by >30x.
Ablation Studies:
- Without Static Analysis (A1): Confirmed vulnerabilities dropped by 12.2x (from 379 to 31), proving SA is critical for targeting.
- Without Iterative Refinement: Confirmed vulnerabilities dropped to 0, proving the feedback loop is essential for harness correctness.
- Without Symbolic Execution: No approach could detect more than 12 vulnerabilities, proving SE is necessary for path precision.
Cost: The pipeline consumed ~2.29 billion LLM tokens. The cost per bug varied significantly based on harness complexity (0.9M tokens for mupdf vs. 29.2M for libxml2), not project size.

5. Significance

Scalability: Sailor proves that Symbolic Execution can be scaled to multi-million LOC codebases by automating the harness generation bottleneck.
Precision: By combining the "ground truth" of concrete execution (ASan) with the path exploration of SE, Sailor achieves a very low false-positive rate compared to pure LLM or SA approaches.
Practical Impact: The system discovered 379 new vulnerabilities in critical infrastructure software (e.g., Binutils, FFmpeg, OpenSSL), many of which were deep in the codebase and unreachable by standard fuzzing.
Methodological Shift: The paper establishes a new paradigm where LLMs are not just "predictors" of bugs but "synthesizers" of formal verification artifacts, guided by iterative execution feedback.

In conclusion, Sailor demonstrates that the synergy of Static Analysis (for targeting), LLMs (for synthesis), and Symbolic Execution (for verification) creates a powerful, automated vulnerability discovery engine capable of finding deep, previously unknown bugs in large-scale software.