💻 computer science

Enhancing Symbolic Execution of Programs for Interprocedural Control Flow Path Feasibility Analysis

This paper proposes a directed symbolic execution method enhanced with automatic symbolization and loop-bounding strategies to efficiently verify interprocedural control flow path feasibility, demonstrating superior recall and precision compared to existing tools like KLEEF when applied to real-world projects and static analysis integration.

Original authors: Hovhannes Movsisyan, Hripsime Hovhannisyan, Tigran Avagyan, Hayk Aslanyan

Published 2026-07-08

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Hovhannes Movsisyan, Hripsime Hovhannisyan, Tigran Avagyan, Hayk Aslanyan

Original paper licensed under CC BY 4.0 (https://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 solve a crime in a massive, multi-story building (the computer program). Your job is to check if a specific route the police report says a suspect took is actually possible.

The police report (the "static analyzer") says: "The suspect went from the lobby, up the stairs, through the kitchen, and then jumped out the window."

However, looking at the blueprints, you realize that the stairs don't connect to the kitchen, or the window is painted shut. The police report was a "false alarm"—a path that looks possible on paper but is physically impossible in reality.

This paper introduces a new, smarter way for detectives to check these routes without getting overwhelmed by the sheer size of the building. Here is how it works, using simple analogies:

1. The Problem: The "Path Explosion"

Traditional detective work tries to check every single possible path in the building to see if the suspect could have gone anywhere. In a huge building with thousands of rooms and endless hallways, this takes forever. The detective gets lost in the sheer number of possibilities (a problem called "path explosion") and runs out of energy (computer resources) before finding the answer.

2. The Solution: "Directed" Detective Work

The authors propose a method called Directed Symbolic Execution. Instead of wandering aimlessly, the detective is given a specific map of the route they need to verify.

The Trick: If the map says the suspect went Left, the detective ignores all the "Right" turns. They only follow the specific path in question, cutting out all the dead ends and irrelevant rooms. This makes the job much faster.

3. Handling the "Unknowns" (Automatic Symbolization)

In real life, a detective might encounter a room where the furniture hasn't been moved in yet, or a door with a lock they don't have the key to. In computer programs, these are "unknown values" (like variables that haven't been set yet).

The Old Way: The detective would stop and say, "I can't proceed because I don't know what's in this room."
The New Way: The detective says, "Okay, let's pretend this room could contain anything." They treat the unknown as a "mystery box" that can be filled with any value needed to make the path work.
The Magic: The paper teaches the detective how to automatically handle these mystery boxes, including:
- Uninitialized variables: Empty rooms.
- External functions: Doors controlled by a neighbor (a different program) that the detective can't see inside.
- Pointers: A note that says "Go to the room number written on this piece of paper." The detective learns to follow the note even if the number changes.

4. The Infinite Hallway Problem (Loop Bounding)

Imagine a hallway that loops around in a circle. If the suspect keeps walking, they could theoretically walk forever.

The Problem: If the detective tries to simulate every single step of an infinite loop, they will never finish.
The Solution: The detective sets a rule: "I will walk around this loop no more than 4 times." If the loop is still going after 4 times, the detective forces the suspect to exit the loop and continue down the main path.
Why it works: This prevents the detective from getting stuck in an endless circle, allowing them to finish the investigation of the specific route, even if it means skipping some very long, repetitive steps.

5. The Results: Catching the Liars

The authors tested their new detective method on real-world software (like the GNU Coreutils, which are the basic tools on a computer) and a famous test suite called "Juliet."

Accuracy: They found that their method correctly identified 95.3% of the paths that were actually possible.
Cleaning up False Alarms: When they used this method to double-check the work of other security tools (like MLH, Infer, and Clang), it was a game-changer.
- One tool (MLH) was reporting 666 false alarms. The new method filtered them all out, leaving zero false alarms while keeping all the real bugs.
- Another tool (KLEEF) actually made things worse when trying to check these paths, crashing or missing almost all the real bugs. The new method stayed strong and accurate.

Summary

Think of this paper as a new set of instructions for a robot detective. Instead of trying to explore the entire universe of possibilities, the robot:

Focuses only on the specific path it needs to check.
Imagines possibilities for anything it doesn't know about (like empty rooms or mystery locks).
Forces itself to stop walking in circles if a hallway goes on too long.

The result is a system that is much better at telling the difference between a real security threat and a fake one, without getting tired or confused.

Technical Summary: Enhancing Symbolic Execution for Interprocedural Control Flow Path Feasibility Analysis

Problem Statement

Static analysis is a scalable technique for software security and reliability, yet it frequently suffers from high false-positive rates. These false positives often arise because static analyzers report control flow paths in an Interprocedural Control Flow Graph (ICFG) that are theoretically possible but actually infeasible at runtime due to semantic constraints (e.g., contradictory variable values). Determining whether a specific path in a program's ICFG is executable is known as path feasibility analysis.

While symbolic execution is a powerful technique for verifying path feasibility by exploring paths using symbolic values and SMT solvers, it faces two primary challenges when applied to this specific problem:

Resource Demand and Path Explosion: Standard symbolic execution attempts to explore all reachable paths, leading to exponential state growth, particularly in the presence of loops and complex branching.
Automation Gaps: Existing engines often require manual configuration to handle variables with unknown values (e.g., uninitialized memory, external function returns, or pointer arguments), which hinders fully automated integration with static analysis tools.

Methodology

The authors propose a directed symbolic execution method designed specifically to verify the feasibility of a pre-defined set of ICFG paths. Unlike traditional symbolic execution that explores the entire state space, this approach directs execution strictly toward a target path, eliminating exploration of unrelated branches.

The methodology relies on four core technical components:

1. Directed Execution and Pruning

The algorithm takes a set of allowed basic blocks ( $S_{allowed}$ ) and a set of required milestones ( $S_{req}$ ) as input. During execution:

Pruning: At every branching point, any successor basic block not belonging to $S_{allowed}$ is pruned, preventing the engine from exploring irrelevant code regions.
Verification: A path is deemed feasible only if the execution reaches the target block ( $B_{target}$ ) while having visited all blocks in $S_{req}$ and remaining within $S_{allowed}$ .

2. Automatic Symbolization Strategies

To enable fully automated analysis without user intervention, the authors introduce strategies to symbolize values that are typically unknown or concrete in standard execution:

Entry-Point Parameters: All parameters of the function where the path analysis begins are symbolized.
Uninitialized Variables and Memory: Uninitialized local variables and dynamically allocated memory (e.g., via malloc) are treated as symbolic objects with unconstrained values, rather than causing undefined behavior or concrete initialization.
External Functions:
- Return Values: Return values from external functions (whose bodies are unavailable) are symbolized.
- Pointer Arguments: Memory locations referenced by non-constant pointer arguments of external calls are re-symbolized to account for side effects.
- Special Globals: Specific handling is applied to errno (made symbolic after external calls) and environ (modeled as a fixed set of symbolic variables with fixed lengths to prevent non-termination during string comparisons).
Function Pointers and Virtual Functions: The system resolves potential targets for function pointers and virtual calls by analyzing virtual tables and function signatures, forking symbolic states for all valid candidates.

3. Flexible Memory Model

The paper introduces a memory model that supports symbolic pointers without relying on fixed-size array allocations.

Lazy Allocation: Memory objects are not created until the symbolic pointer is dereferenced.
Aliasing Handling: When a symbolic pointer is dereferenced, the engine considers aliasing scenarios. It forks the symbolic state to explore cases where the pointer references an existing memory object (with matching or differing offsets) versus a completely new memory location. This allows the analysis of complex data structures like linked lists and trees without pre-defining their size.

4. Loop Bounding Strategy

To mitigate path explosion in loops, the method employs a loop-bounding strategy:

A maximum iteration count ( $C_{max}$ ) is defined.
If a symbolic state enters a loop more than $C_{max}$ times, the engine forces the state to exit the loop via available exit edges.
Crucially, memory locations written during the loop execution are symbolized before the forced exit. This ensures that the engine can still explore paths that depend on the side effects of the loop, even if the exact iteration count is truncated. This introduces a trade-off between completeness and scalability, prioritizing the reachability of the target defect location.

Key Contributions

The paper claims the following contributions:

A directed symbolic execution algorithm for determining the feasibility of any ICFG path in a specified set.
Fully automatic symbolization strategies for variables with unknown values, external function returns, and pointer arguments.
A memory model supporting symbolic pointer reasoning and aliasing without fixed-size constraints.
A loop-bounding algorithm that limits iterations without terminating the symbolic execution of the path.
An empirical evaluation on real-world software and the Juliet test suite.

Experimental Results

The method was implemented as an extension to the KLEE symbolic execution engine (v3.1) and evaluated using the following datasets:

1. Real-World Path Verification (GNU Coreutils)

Dataset: 234 unique ICFG paths extracted from GNU Coreutils, ranging from 22 to 1,218 basic blocks.
Result: The tool achieved a 95.3% recall, successfully verifying 223 of 234 paths.
Observation: 49 paths required the loop-bounding strategy. The study noted that a Breadth-First Search (BFS) strategy was occasionally necessary to find target states in complex loop scenarios where Depth-First Search (DFS) failed to reach the state within time limits.

2. Integration with MLH Static Analyzer

Setup: The method was integrated into the MLH static analysis tool and tested on the Juliet Test Suite (CWE-401: Memory Leak).
Result: Integration increased the tool's precision from 56% to 100% while maintaining a 100% recall. The method successfully eliminated all false positives without discarding any true positives.

3. Comparison with KLEEF

Setup: The proposed method was compared against KLEEF (a specialized KLEE derivative) using reports from the Infer and Clang Static Analyzer (CSA) on the Juliet Test Suite (CWE-415 and CWE-416).
Result:
- Infer: KLEEF reduced the F1-score from 1.0 to 0.0 (crashing on 60 reports and classifying all true positives as infeasible). The proposed method maintained the F1-score at 1.0.
- CSA: KLEEF reduced the F1-score from 0.766 to 0.058. The proposed method maintained the F1-score at 0.767 (slightly improving precision by filtering some false positives while keeping recall at 100%).
Analysis: The authors attribute KLEEF's failure to its inability to handle specific external function calls and symbolic pointer arithmetic, leading to early termination.

Significance and Claims

The paper positions this work as a practical solution for bridging the gap between the scalability of static analysis and the precision of symbolic execution. The authors claim that by directing symbolic execution and automating symbolization, the method effectively filters infeasible paths reported by static analyzers.

The significance lies in the ability to:

Automate the verification process without manual configuration of symbolic variables.
Handle complex memory models (pointers, dynamic allocation) that often cause other tools to fail or require fixed-size approximations.
Improve Static Analysis Metrics: Specifically, the method demonstrates the ability to eliminate false positives (increasing precision) without sacrificing the detection of real vulnerabilities (preserving recall).

The authors acknowledge a trade-off between completeness and scalability due to the loop-bounding strategy but argue that for the specific goal of validating static analysis reports, prioritizing the reachability of the target location is an acceptable compromise. Future work is proposed to parallelize the analysis and develop specialized state selection strategies to further improve efficiency.