Concolic Execution
Emulation & Symbolic Execution · VR Analysis & Discovery track
6 min read
In this module
The Best of Both Worlds
Pure symbolic execution tracks all possible program states at once — powerful, but it explodes combinatorially. Pure concrete testing runs fast but only ever follows one path at a time. Concolic execution (concrete + symbolic) does both simultaneously: it runs the program with concrete inputs while tracking symbolic constraints, then uses those constraints to generate inputs that explore different paths next time.
How Concolic Execution Works
The concolic approach follows a cycle:
- Run concretely: execute the program with a concrete input (the first run uses a random or default input).
- Track symbolically: while running, maintain symbolic expressions for all values derived from the input. At each branch, record the path constraint.
- Negate a constraint: after the run completes, pick one branch constraint from the recorded path and negate it.
- Solve: use an SMT solver to find a new concrete input that satisfies all constraints up to the negated branch but takes the opposite direction at that branch.
- Repeat: run the program with the new input, recording a new path. Continue until all reachable paths are explored or a bug is found.
Run 1: input = "AA A" Path: branch1=T, branch2=T, branch3=F Constraints: [x[0]>'@', x[1]>'@', x[2]<='@']
Run 2: negate branch3 -> constraint x[2]>'@' Solver finds: input = "AAAA" (satisfies x[0]>'@', x[1]>'@', x[2]>'@') Path: branch1=T, branch2=T, branch3=T
Run 3: negate branch2 -> constraints x[0]>'@', x[1]<='@' Solver finds: input = "A AA" Path: branch1=T, branch2=F, ...Each run adds one new leaf to the path tree. After three runs it looks like this, with the untried branches still waiting:
Run 4 would negate branch1, asking the solver for any input whose first byte is '@' or lower.
Concolic execution avoids several challenges of pure symbolic execution. Since it always runs with concrete values, it naturally handles operations that are difficult to model symbolically: floating-point arithmetic, pointer dereferencing, system calls, and library functions all execute concretely with real results. Only the input-dependent values need symbolic tracking. This dramatically reduces the complexity of the symbolic state.
KLEE: Symbolic Execution for LLVM
KLEE is one of the pioneering symbolic execution tools, operating on LLVM bitcode. Unlike binary-level tools, KLEE requires that you compile the target program with Clang using -emit-llvm to produce LLVM IR (intermediate representation). KLEE then symbolically executes the IR.
# Compile to LLVM bitcodeclang -emit-llvm -c -g target.c -o target.bc
# Run KLEE with symbolic stdinklee --posix-runtime target.bc --sym-stdin 10KLEE generates a test case for each unique execution path it discovers. Each test case is a concrete input that drives the program down that path. If KLEE detects an error (assertion failure, buffer overflow, null pointer dereference), it generates a test case that triggers the error.
KLEE's advantages are its precision (LLVM IR has a written specification for every instruction, including exactly which operations are undefined or produce poison, so KLEE can check for many of them) and its ability to model memory operations exactly. Its disadvantage is that it requires source code (or at least LLVM bitcode), making it unsuitable for closed-source binary analysis.
Triton: Dynamic Binary Analysis
Triton is a dynamic binary analysis framework that provides concolic execution capabilities for x86-64 binaries. It operates at the instruction level, maintaining symbolic expressions for registers and memory as the program executes.
Triton doesn't run the target itself. You hand it instructions one at a time, either from a trace collected by a separate tool (a DBI framework such as Pin or DynamoRIO) or by emulating the code with Triton's own instruction semantics. For each instruction it updates a concrete register and memory state alongside the symbolic expressions, so the two stay consistent as long as you feed it the path the program really took.
from triton import *
ctx = TritonContext(ARCH.X86_64)
# Symbolize input bytes in memoryfor i in range(input_len): ctx.symbolizeMemory(MemoryAccess(input_addr + i, 1))
# Process instructions one by onefor inst_bytes, addr in instructions: inst = Instruction(addr, inst_bytes) ctx.processing(inst)
# Check if we've reached an interesting branch if inst.isBranch(): constraint = ctx.getPathConstraints() # Negate the last constraint and solve for new inputTriton gives you granular control — choose which memory and registers to symbolise, which instructions to process, and when to query the solver. That flexibility makes it well-suited for targeted analysis of specific functions rather than whole-program exploration.
Guided Exploration Strategies
The order in which you negate constraints and explore new paths dramatically affects efficiency. Common strategies:
Depth-first: negate the last constraint first, exploring deep paths before backtracking. Good for finding bugs near the end of execution but may get stuck in deep loops.
Breadth-first: negate constraints from earliest to latest, exploring shallow paths first. Provides broader coverage but may miss deep bugs.
Coverage-guided: track which basic blocks have been covered and prioritise paths that reach uncovered code. Similar to how fuzzing tools like AFL select inputs.
Distance-guided: measure the distance (in the control flow graph) from the current state to the target address and prioritise paths that reduce this distance. Good when you have a specific target in mind.
Hybrid fuzzing: combine concolic execution with fuzzing. The fuzzer generates inputs quickly through mutation, and when it gets stuck (cannot increase coverage), concolic execution analyses the blocking branches and generates inputs that pass them. This combination, used by tools like Driller and QSYM, often outperforms either approach alone.
Limitations
Concolic execution has real-world ceilings. Each run takes time — millions of paths is slow, full stop. The SMT solver goes exponential on complex constraints, especially non-linear arithmetic. Symbolic tracking adds overhead per instruction. And like all dynamic techniques, it can only reach paths that are reachable from your starting state.
That said, it's still one of the most productive automated approaches for exploring program behaviour and surfacing bugs in both source-available and binary-only targets.