Skip to main content
Be Bitwise

Symbolic Execution & Automated Exploit Generation

Defensive Exploitation & Red Team Techniques · Defense & Forensics track

7 min read

In this module

Beyond Random Testing

Fuzzing is powerful, but it hits walls. Some bugs hide behind input constraints that random mutation won't satisfy in a practical timeframe — reaching a specific vulnerable path might require passing a checksum, satisfying multiple interrelated conditions, and supplying magic values at exact offsets. A fuzzer might need billions of attempts. It might never get there.

Symbolic execution reasons about the program mathematically instead. Inputs are symbolic variables. As the program executes, constraints accumulate. A constraint solver then finds concrete input values that reach any desired state — including the one where the program breaks.

How Symbolic Execution Works

In normal execution, variables have concrete values: x = 5, y = 3. In symbolic execution, variables have symbolic values: x = X, y = Y (where X and Y are mathematical symbols representing any possible value).

As the program executes, operations produce symbolic expressions:

c
int x = input(); // x = X (symbolic)
int y = x + 5; // y = X + 5 (symbolic expression)
int z = y * 2; // z = (X + 5) * 2 = 2X + 10
if (z > 100) { // Branch condition: 2X + 10 > 100
vulnerable(); // Path constraint: 2X + 10 > 100 → X > 45
} else {
safe(); // Path constraint: 2X + 10 <= 100 → X <= 45
}

At each branch, the symbolic executor records the path constraint and explores both paths. For the "then" branch, it adds the constraint X > 45. For the "else" branch, it adds X <= 45.

To generate a concrete input that reaches vulnerable(), the symbolic executor passes the accumulated constraints (X > 45) to an SMT solver (Satisfiability Modulo Theories solver, like Z3). The solver determines whether the constraints are satisfiable and, if so, provides a concrete value (e.g., X = 46).

That X > 45 treats X as a mathematical integer, though. Real executors model x as a 32-bit bit-vector, where 2X + 10 wraps around, so the true path constraint isn't a simple range. The runner computes z the way the CPU does for a few values of X and compares it with the textbook answer. Predict which rows disagree before you run it.

Try itPredict the disagreeing rows, then search for the smallest positive X that takes the safe branch even though X > 45.
C (GCC 9.2.0)

A solver working on bit-vectors finds these wrap-around inputs as easily as X = 46, which is exactly why it's good at finding integer-overflow bugs.

Symbolic Execution

Symbolic execution analyses programs by treating inputs as symbolic variables and computing constraints as the program executes. At each branch, it records the branch condition as a constraint and explores both directions. An SMT solver determines which constraints are satisfiable, generating concrete inputs that reach specific code paths. This systematically explores program behaviour rather than relying on random testing.

Practical Symbolic Execution Tools

angr: A binary analysis framework written in Python. angr can perform symbolic execution on compiled binaries (without source code), supports multiple architectures (x86, ARM, MIPS, etc.), and includes libraries for binary loading, CFG recovery, data flow analysis, and constraint solving. It is widely used in CTF competitions and security research.

python
# Using angr to find input that reaches a specific address
import angr
project = angr.Project("./target_binary")
state = project.factory.entry_state()
simulation = project.factory.simgr(state)
# Explore until we reach the "win" function at 0x401234
simulation.explore(find=0x401234)
if simulation.found:
solution = simulation.found[0]
input_bytes = solution.posix.dumps(0) # stdin contents
print(f"Input to reach target: {input_bytes}")

KLEE: A symbolic execution engine built on LLVM. KLEE operates on LLVM bitcode and can symbolically execute C/C++ programs. It was designed for systematic testing and has found bugs in widely used programs including GNU Coreutils.

Manticore: A symbolic execution tool from Trail of Bits that supports analysis of both native binaries and smart contracts (Ethereum bytecode).

The Path Explosion Problem

The fundamental challenge of symbolic execution is path explosion. At every branch, the number of paths doubles. A program with 100 sequential branches has 2^100 possible paths, about 10^30, far more than any machine could ever explore.

Real programs have loops (potentially infinite iterations), recursive calls, and complex branching. Exhaustively exploring all paths is infeasible for any non-trivial program.

Practical symbolic execution tools use several strategies to manage path explosion:

  • Concolic execution (concrete + symbolic): Execute the program with concrete inputs while maintaining symbolic state. At branches, use the concrete execution to choose one path, but record the branch condition. Later, negate branch conditions to explore alternative paths. This avoids exploring all paths simultaneously.

  • Path prioritisation: Prioritise unexplored paths that are likely to reach interesting code (bug-prone areas, uncovered branches). Deprioritise paths stuck in loops or library code.

  • Merging: Combine paths that have diverged but converge at the same program point. Instead of maintaining two separate states, merge them into one state with a disjunctive constraint.

  • State pruning: Discard states that are clearly uninteresting (stuck in infinite loops, reached a dead end, etc.).

Despite these techniques, scaling symbolic execution to large programs remains a significant challenge. It works best on focused analysis targets: individual functions, specific modules, or limited-scope programs.

Automated Exploit Generation (AEG)

The most ambitious application of symbolic execution is Automated Exploit Generation (AEG) - using program analysis to automatically produce working exploits for discovered vulnerabilities.

The AEG concept, demonstrated by researchers at Carnegie Mellon University, works as follows:

  1. Bug finding: Use symbolic execution or fuzzing to find a crashing input
  2. Root cause analysis: Analyse the crash to determine the vulnerability class (buffer overflow, format string, etc.)
  3. Exploitability assessment: Determine whether the crash is exploitable (can the attacker control the instruction pointer? Can they write to arbitrary addresses?)
  4. Constraint formulation: Express the exploit requirements as constraints (e.g., "the return address must equal the address of the shellcode," "the shellcode must be placed at address X")
  5. Constraint solving: Use an SMT solver to find input values that satisfy all constraints simultaneously - the working exploit
text
Crashing input → Analyse crash → Formulate exploit constraints
↓
Working exploit ← SMT solver ← Constraint system

This is conceptually elegant but faces enormous practical challenges:

  • Modern mitigations (ASLR, DEP, stack canaries) add constraints that may require additional info leaks
  • The constraint system for a real exploit is extremely complex
  • Heap exploitation requires modelling the allocator's behaviour, which is difficult to express symbolically

Combining Fuzzing and Symbolic Execution

The most effective bug-finding approaches combine fuzzing and symbolic execution:

Driller: Uses AFL for initial fuzzing, then switches to symbolic execution when the fuzzer gets "stuck" (cannot find inputs that reach new coverage). Symbolic execution solves the specific constraint blocking the fuzzer, generates an input that passes the obstacle, and the fuzzer continues from there.

QSYM: A practical concolic execution engine that runs alongside AFL. When AFL generates an interesting input, QSYM symbolically executes it, collects branch constraints, negates them, and solves for inputs that take different paths. These new inputs are fed back to AFL's queue.

This pairing plays to each tool's strengths: fuzzing is fast and handles complex state well, while symbolic execution can solve specific constraints that randomness cannot.

The Defensive Perspective

From a defensive standpoint, these tools are used to:

  • Find vulnerabilities before attackers: Running symbolic execution on security-critical code to systematically explore paths that might contain vulnerabilities
  • Assess exploitability: Determining whether a crash bug is actually exploitable helps prioritise patching
  • Verify patches: Confirming that a fix actually prevents the vulnerability by checking whether the exploit constraints are still satisfiable after the patch
  • Generate test cases: Producing inputs that exercise specific code paths, improving test coverage

Automated analysis doesn't replace human expertise — it multiplies it. A researcher with angr, AFL++, and good sanitizers covers far more ground than manual review alone. Human intuition points you to where the interesting code is; automated tools systematically explore it once you've aimed them correctly. That pairing is hard to beat.