Chapter 9: Finding Vulnerabilities: Testing, Fuzzing, and Symbolic Execution
Every exploit in the previous chapters started from a bug that someone had already
found: a strcpy into a 64-byte buffer, a function pointer next to it, a missing
length check. We took the bug as given and asked how to turn it into control of the
program. This chapter turns the question around. Given a large program you did not
write — a PDF reader, an image library, a network daemon — how do you find the
bugs in the first place?
The answer matters to both sides. Attackers want to find exploitable bugs before anyone else does; defenders want to find them before attackers do. The tools are the same, and today the most productive of them are automated: fuzzers that throw millions of mutated inputs at a program, and symbolic execution engines that reason mathematically about which inputs reach which code. Increasingly, large language models sit alongside both.
Learning objectives. After this chapter you should be able to:
- Explain the two halves of vulnerability discovery: locating a bug and reaching it.
- Classify testing approaches as manual or automated, black-box or white-box, and name a tool in each category.
- Define function, statement, and branch coverage, and explain why coverage guides fuzzing.
- Run AFL/AFL++ and libFuzzer on a small target, and explain how AFL’s coverage bitmap works and why sanitizers matter.
- Explain symbolic execution, path constraints, and SMT solving, and why path explosion limits it.
- Describe how hybrid (concolic) fuzzing and LLMs extend these techniques.
9.1 From Bugs to Exploits
Finding a security bug, whether in source code (an open-source project) or in a binary (a closed-source product or a malware sample), involves two distinct questions:
// Q2: how do we reach it?
if (magic == 0x31323334) {
// Q1: is this a bug?
memcpy(dst, src, len);
}
- Is this a bug? Locate code that can misbehave: a
memcpywhoselenis not checked against the size ofdst, a format string built from user input, an integer that can wrap (Chapter 12). - Can we trigger it? This is reachability: is there an input that drives the
program from its entry point, through all the intervening checks, to the buggy
statement with the dangerous values? Here the input must contain the 32-bit value
0x31323334(the bytes"4321"in little-endian memory) at the right place.
A bug that cannot be reached by any attacker-controlled input is not a vulnerability. Conversely, a reachable crash is the raw material for every exploit we have studied. The techniques in this chapter differ mainly in how they answer these two questions: humans reading code are good at Q1 but slow at Q2; fuzzers answer Q2 by brute force; symbolic execution answers Q2 by solving equations.
9.2 Code Review and Its Limits
The oldest technique is reading the code. Experienced reviewers recognize patterns instantly:
int i;
int array[5];
int j;
for (i = 0; i <= 5; i++) /* off-by-one: writes array[5] */
cin >> array[i];
The loop runs six times for a five-element array; the sixth write lands on whatever
the compiler placed next to array — possibly j or i itself.
char *initialize() {
char string[80];
char *ptr = string;
return ptr; /* returns a pointer into a dead stack frame */
}
int main() {
char *myval = initialize();
do_something_with(myval); /* uses memory that the next call will overwrite */
}
Here string lives in initialize’s stack frame, which is reclaimed when the function
returns. The pointer survives, but the memory is reused by the very next call — a
dangling pointer to stack memory (compilers warn about the obvious form of this, but
not when the pointer passes through a variable as above).
Code review finds real bugs, and security-critical projects require it. But it does not scale. A browser has tens of millions of lines; a single reviewer cannot hold the data flow of even one component in their head, and the dangerous path often crosses dozens of functions and files. We need machines to do most of the work.
9.3 A Taxonomy of Software Testing
Software testing compares a program’s behavior on some input against its specification — its supposed behavior. A test fails when the observed behavior differs from the expected one; for security testing, the “specification” is often simply does not crash, does not corrupt memory, does not hang.
+-------------------+
input ---> | program | ---> observed behavior
+-------------------+ |
v
compare with expected behavior
Testing approaches vary along two axes. Who creates the tests — a human (manual) or a tool (automated)? What does the tester know — only the interface (black-box) or the source/internal structure (white-box)?
| Black-box (no source needed) | White-box (source / internals used) | |
|---|---|---|
| Manual | Penetration testing; crafting malformed inputs by hand; frameworks such as Metasploit | Hand-written unit and integration tests; test-driven development; CI test suites |
| Automated | Black-box fuzzers; binary-only coverage fuzzers (e.g., WinAFL, AFL QEMU mode) | Coverage-guided fuzzing with compile-time instrumentation (AFL/AFL++, libFuzzer); whitebox fuzzing / symbolic execution (SAGE, KLEE) |
Each axis is a trade-off:
- Automated testing finds bugs quickly, needs no hand-written tests, and needs no test maintenance when the software changes. Manual testing produces a compact, intentional test suite that can target logic no tool understands.
- Black-box testing needs no access to or analysis of the code, works on code in any format (managed, binary, obfuscated), and works on code you cannot modify. White-box testing can measure and target internal structure, and so tends to achieve better coverage with fewer tests.
Manual white-box testing in practice
Tests written by hand require full knowledge of the source code, deployment, and infrastructure, but they can target any part of the system. Running them can be automated: modern projects run their suites on every commit, merge, or deployment in continuous integration (CI). Test-driven development writes the test first — including, for security, regression tests for every vulnerability ever fixed, so that it never silently returns.
Manual black-box testing
A penetration tester interacts with a running system from the outside, crafts ill-formed inputs, and watches how it reacts. Frameworks such as Metasploit package known exploits and scanning modules so that a tester can probe a target’s components — or the application as a whole — for known vulnerabilities and demonstrate compromise (stealing data, getting a shell).
9.4 Measuring Tests: Code Coverage
How do we know whether a test suite is good? Too few tests miss bugs; too many cost time to run and maintain. The standard proxy is code coverage: the fraction of the program’s code that the tests execute.
- Function coverage: which functions were called at least once?
- Statement coverage: which statements (or lines) were executed?
- Branch coverage: for each conditional, were both the true and the false outcomes taken?
int f(int a, int b)
{
int r = 0;
if (a > 10) /* branch 1 */
r += 1;
if (b == 42) /* branch 2 */
r += 2;
return r;
}
The single test f(11, 42) executes every statement (100% statement coverage) but
only the true side of each branch (50% branch coverage). Adding f(0, 0) reaches
100% branch coverage. Note that even then, these two tests exercise only two of the
four paths — combinations of branch outcomes — through f; path coverage grows
exponentially with the number of branches and is rarely achievable.
GCC can measure coverage for you:
$ gcc --coverage f.c test.c -o test && ./test
$ gcov -b f.c
Branches executed:100.00% of 4
Taken at least once:50.00% of 4
100% coverage is rare in practice — some code is unreachable or handles conditions that cannot be produced in a test environment — but it is required in some safety-critical domains. For security, the key insight is the converse: code that your tests never execute is code in which your tests can never find a bug. That insight is what turns fuzzing from random guessing into a search.
9.5 Coverage-Guided Fuzzing with AFL
Fuzzing means running a program on a huge number of automatically generated inputs and watching for crashes or hangs. The earliest fuzzers (Barton Miller’s 1990 study of Unix utilities) fed purely random bytes. Random inputs are rejected almost immediately by any non-trivial parser, so pure random fuzzing explores only the outermost layer of the program.
American Fuzzy Lop (AFL), released by Michał Zalewski in 2013, made fuzzing dramatically more effective with one idea: use coverage feedback to decide which inputs are worth mutating further. AFL is a free, open-source fuzzer, and its design is the template for most modern fuzzers.
The AFL loop
+---------------------------------------------------------+
| |
v |
+-----------+ pick +----------+ run +-----------------+ |
| queue of | --------> | mutate | -----> | instrumented | |
| inputs | an input | (bitflip,| | target program | |
| (seeds + | | arith, | +-----------------+ |
| discovered| | splice, | | |
| inputs) | | havoc) | coverage bitmap, |
+-----------+ +----------+ crash? hang? |
^ | |
| new coverage? keep the input | |
+----------------------------------------------+ |
| crash |
v |
output/crashes/ ----+
- Start from one or more seed inputs (any valid-ish example files).
- Pick an input from the queue and apply mutations: flip bits, add or subtract
small integers, insert “interesting” values (0, −1,
INT_MAX), splice two inputs together, and stack random combinations (“havoc”). - Run the instrumented program on each mutant and record which edges of the control-flow graph it exercised.
- If a mutant exercised a new edge (or an existing edge a substantially different number of times), it is interesting: add it to the queue.
- If the program crashed (e.g.,
SIGSEGV,SIGABRT,SIGILL) or hung, save the input for a human to triage.
This is a genetic algorithm with coverage as the fitness function. An input that gets one byte further into a parser is kept and becomes the starting point for the next step, so the fuzzer can peel through layers of checks one at a time.
How AFL measures coverage
At compile time, afl-gcc (a wrapper around GCC) inserts a small piece of code at the
start of every basic block, each with a random compile-time constant as its ID. At
runtime, the instrumentation updates a 64 KB bitmap shared with the fuzzer:
cur_location = <COMPILE_TIME_RANDOM>;
shared_mem[cur_location ^ prev_location]++;
prev_location = cur_location >> 1;
XOR-ing the current block’s ID with the (shifted) previous block’s ID gives an index
for the edge prev → cur, not just the block; shifting prev_location makes the
edge A → B distinct from B → A. Each bitmap byte counts how often an edge was taken,
and AFL buckets those counts (1, 2, 3, 4–7, 8–15, 16–31, 32–127, 128+) so that “the
loop ran 5 times instead of 4” does not count as new behavior but “the loop ran 50
times instead of 4” does. Comparing the bitmap after each run against the global
“seen” map is a fast, constant-size operation, which is why AFL can execute thousands
of inputs per second.
A worked example
/* crackme487.c */
#include <unistd.h>
int main(int argc, char *argv[])
{
char data[100] = {0};
size_t size = read(0, data, 100);
if (size > 0 && data[0] == '4')
if (size > 1 && data[1] == '8')
if (size > 2 && data[2] == '7')
__builtin_trap(); /* the "bug": crashes with SIGILL */
return 0;
}
Any input beginning with 487 triggers the built-in bug. Random inputs would need to
guess three bytes at once — about one chance in 16.7 million per try. AFL needs far
fewer attempts: the first time a mutant happens to start with 4, the new edge into
the second if makes it interesting, and it is saved. From then on, AFL mutates
inputs that already start with 4 and needs only to guess 8 (one in 256), and so on.
The search is incremental, and each step is cheap.
To run it:
$ afl-gcc crackme487.c -o crackme487.afl # instrument at compile time
$ mkdir input && echo AAAA > input/test # create a seed input
$ afl-fuzz -i input -o output ./crackme487.afl # fuzz; input is fed on stdin
On many Linux systems, afl-fuzz refuses to start until crash reports are delivered
directly rather than to an external crash handler (which would make AFL misclassify
crashes as timeouts):
$ sudo sh -c "echo core >/proc/sys/kernel/core_pattern"
AFL’s status screen shows executions per second, paths found, and — within seconds
for this example — a non-zero uniq crashes count. The crashing inputs are saved in
output/crashes/ (output/default/crashes/ with AFL++); replay one to confirm:
$ ./crackme487.afl < output/crashes/id:000000,*
Illegal instruction (core dumped)
If the program reads a file named on its command line instead of standard input, put
@@ where the file name goes: afl-fuzz -i input -o output ./prog @@.
Try it. The public
afl-trainingworkshop materials (https://github.com/mykter/afl-training) walk through fuzzing real libraries step by step, including writing harnesses, using dictionaries, and triaging crashes. Work through the quickstart before attempting real targets.
AFL++
The original AFL is no longer developed. Its community successor, AFL++
(https://github.com/AFLplusplus/AFLplusplus), is faster and adds better mutations,
better instrumentation (afl-cc, afl-clang-fast, and afl-clang-lto use LLVM
passes instead of assembly rewriting), custom mutator modules, and several features
aimed squarely at the “magic value” problem discussed in §9.7: CmpLog (inspired by
the RedQueen paper) records the operands of comparisons at runtime and splices them
into inputs, and laf-intel splits a 32-bit comparison into four 8-bit comparisons so
coverage feedback can reward each matching byte separately. For new work, use AFL++.
9.6 In-Process Fuzzing with libFuzzer, and Why Sanitizers Matter
AFL starts (or forks) the target process for every input. libFuzzer, part of LLVM/Clang, instead links the fuzzer into the target and calls a single entry function in a loop, which avoids process creation and can run hundreds of thousands of inputs per second. You write a fuzz harness — a function that takes a byte buffer and feeds it to the code under test:
/* fuzz_parse.c */
#include <stdint.h>
#include <stddef.h>
#include <string.h>
static int parse_header(const uint8_t *buf, size_t len)
{
char name[16];
if (len < 4 || memcmp(buf, "HDR:", 4) != 0)
return -1;
memcpy(name, buf + 4, len - 4); /* BUG: no check against sizeof(name) */
return name[0];
}
int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size)
{
parse_header(data, size);
return 0; /* non-zero values are reserved */
}
$ clang -g -O1 -fsanitize=fuzzer,address fuzz_parse.c -o fuzz_parse
$ ./fuzz_parse
...
==12345==ERROR: AddressSanitizer: stack-buffer-overflow on address 0x7ffd...
WRITE of size 21 at 0x7ffd... thread T0
#0 ... in __asan_memcpy
#1 ... in parse_header fuzz_parse.c:11
...
artifact_prefix='./'; Test unit written to ./crash-5f1c...
-fsanitize=fuzzer links libFuzzer’s driver (so you do not write main), and
-fsanitize=address adds AddressSanitizer.
Why fuzzers need sanitizers
A fuzzer can only report bugs it can observe, and most memory-corruption bugs do not
crash. Overflowing name by five bytes may silently corrupt a neighboring local
variable, and the program carries on. The bug is there; the fuzzer simply cannot see
it.
Sanitizers turn silent corruption into an immediate, well-described crash:
- AddressSanitizer (ASan) surrounds every stack, heap, and global object with poisoned redzones and records, in a compact shadow memory, which bytes are addressable. Every load and store is instrumented to check the shadow first. It detects out-of-bounds accesses, use-after-free, double free, and more, at roughly a 2× slowdown.
- UndefinedBehaviorSanitizer (UBSan,
-fsanitize=undefined) detects signed integer overflow, invalid shifts, misaligned pointers, and other undefined behavior (Chapter 12). - MemorySanitizer (uses of uninitialized memory) and ThreadSanitizer (data races) cover other bug classes.
Fuzzing + sanitizers is the standard recipe. Google’s continuous fuzzing service for open source, OSS-Fuzz, builds every project with libFuzzer or AFL++ and sanitizers and has reported tens of thousands of bugs.
9.7 Black-Box Fuzzing and the Limits of Fuzzing
When you have only a binary — closed-source software, firmware, a malware sample — you cannot recompile with instrumentation. Automated black-box (or “binary-only”) fuzzing still needs the same three components:
- Test-case generation — mutation of seeds, or generation from a grammar or protocol description.
- Tracing the execution to obtain coverage, using
- dynamic binary instrumentation, which rewrites code as it runs (DynamoRIO, TinyInst);
- an emulator that translates and observes every block (QEMU — AFL’s
-Qmode); - hardware tracing that records branches with little overhead (Intel Processor Trace, PT).
- Exception detection and logging — catching crashes and hangs and saving the inputs that caused them.
WinAFL (https://github.com/googleprojectzero/winafl), from Google Project Zero, is an example: it brings AFL-style coverage-guided fuzzing to closed-source Windows applications, obtaining coverage through DynamoRIO, Intel PT, or TinyInst.
Fuzzing: strengths
Fuzzing automatically discovers bugs and proves them — every finding comes with a concrete crashing input, so there are no false positives to argue about — and the fixed version can be re-fuzzed to confirm the correction. It is remarkably effective for its simplicity, and it is the workhorse of industrial vulnerability discovery. In DARPA’s 2016 Cyber Grand Challenge, fully autonomous systems found, exploited, and patched bugs in previously unseen binaries with no human involvement; the participating systems all combined fuzzing with other program analyses.
Fuzzing: weaknesses
- Non-determinism. Results depend on random choices and on how long you run it. Two campaigns on the same target can find different bugs, and “no crash after 24 hours” proves nothing.
- Hard-to-pass checks. Coverage feedback rewards progress only when a new edge is
taken. A check like
magic == 0x31323334is a single edge that is taken only when all 32 bits match at once — there is no partial credit, so mutation is reduced to blind guessing (one in 2³²). Worse are checksums (a network packet whose CRC must match its contents) and grammar checks (bytecode or source that must parse before any interesting code runs): almost every mutation breaks them.
The usual remedies are dictionaries of magic tokens, comparison splitting (laf-intel), comparison logging (CmpLog), grammar-aware generators, and patching checksums out of the target during fuzzing. The principled remedy is to compute the input that passes the check — which is exactly what symbolic execution does.
9.8 Symbolic Execution
A normal (concrete) execution runs the program on one specific input. Symbolic execution runs it on symbols standing for all possible inputs and keeps track of two things:
- a symbolic state mapping each variable to an expression over the input symbols;
- a path constraint — the conjunction of branch conditions that must hold for the execution to have followed the current path.
At each branch whose condition depends on symbolic input, execution forks: one
copy continues with the condition added to its path constraint, the other with its
negation. When a path reaches something interesting — a crash, an assertion, a
memcpy with an out-of-range length — the engine asks a constraint solver for a
concrete input satisfying the path constraint. That input is guaranteed to drive the
program down exactly that path.
A worked example
void process(int x, int y)
{
int z = 2 * y;
if (x == 0x31323334) { /* the "magic" check */
if (z == x + 10)
bug(); /* we want to reach this */
}
}
Treat the inputs as symbols x = α, y = β:
z = 2β
|
α == 0x31323334 ?
/ \
true false
/ \
2β == α + 10 ? return
/ \ PC: α != 0x31323334
true false
| \
bug() return
PC: α == 0x31323334 PC: α == 0x31323334
∧ 2β == α + 10 ∧ 2β != α + 10
To reach bug(), the solver must satisfy α = 0x31323334 ∧ 2β = α + 10. It answers
for example α = 0x31323334, β = 0x1899199F — instantly, where a mutation fuzzer would need on
the order of 2³² attempts just for the first condition. Each leaf yields one test
input, and together they cover every path.
SMT solvers
The path constraints of real programs involve machine arithmetic — 32-bit
wrap-around, bitwise operations, array (memory) reads and writes — so symbolic
executors use Satisfiability Modulo Theories (SMT) solvers, which decide the
satisfiability of formulas over theories such as fixed-width bit-vectors and
arrays. Z3 (from Microsoft Research) and STP are widely used. Modeling bit-vectors
precisely matters: over mathematical integers, x + 1 < x is unsatisfiable, but over
32-bit machine integers it is satisfied by x = 0x7fffffff (signed) — precisely the
kind of integer-overflow bug in Chapter 12.
You can try the solving step directly with Z3’s Python bindings:
from z3 import BitVec, Solver
x, y = BitVec('x', 32), BitVec('y', 32)
s = Solver()
s.add(x == 0x31323334, 2 * y == x + 10)
print(s.check(), s.model()) # e.g. sat [y = 412686751, x = 825373492]
Tools
- KLEE (https://klee.github.io/) symbolically executes LLVM bitcode compiled from C programs. Its OSDI 2008 paper ran it on the GNU Coreutils and automatically generated tests with high coverage that also found serious bugs in these heavily tested programs.
- angr (https://angr.io/) is a Python framework for binary analysis that
includes a symbolic execution engine working directly on machine code; it is a
favorite for CTF reverse-engineering challenges (“find the input that prints
Correct!”).
The fundamental problem: path explosion
Every symbolic branch can double the number of paths. A loop that runs up to n
times on symbolic data produces n paths; nested loops and loops over input buffers
quickly produce more paths than there are atoms in the universe. This is path (state)
explosion, and it is why symbolic execution alone does not scale to large programs.
Further costs come from modeling the environment (system calls, files, the network),
from symbolic memory addresses (a write to buf[i] with symbolic i might touch any
element), and from constraints too hard for the solver.
Whitebox fuzzing and concolic execution
The practical compromise is to mix concrete and symbolic execution — concolic execution. Godefroid, Levin, and Molnar’s SAGE (“Automated Whitebox Fuzz Testing,” NDSS 2008), used at scale at Microsoft on file parsers, worked like this:
- Run the program concretely on a well-formed input and record the trace.
- Re-execute the trace symbolically to collect the path constraint of that one path.
- Negate one branch condition at a time, ask the solver for an input satisfying the modified constraint, and run the program on that new input.
Because each step follows a real, concrete path, the environment and hard constraints can always fall back to concrete values, and the search explores paths systematically from known-good inputs.
Hybrid fuzzing splits the work by strength: a fast coverage-guided fuzzer explores most of the program, and when it gets stuck behind a check it cannot pass, a concolic engine solves that one branch and hands the resulting input back to the fuzzer. Driller (Stephens et al., NDSS 2016) paired AFL with angr this way; QSYM (Yun et al., USENIX Security 2018) made the concolic side fast enough to keep up with the fuzzer by executing natively and solving constraints selectively.
9.9 AI-Assisted Vulnerability Discovery
Large language models are now part of the toolbox at nearly every step:
- Harness generation. The hardest part of fuzzing a library is often writing a
good harness that calls its API correctly. LLMs read the API and write candidate
LLVMFuzzerTestOneInputfunctions; the fuzzing infrastructure compiles and runs them and keeps the ones that build and increase coverage. Google’s open-source OSS-Fuzz-gen project applies this to OSS-Fuzz projects. - Seed and grammar generation. An LLM that knows what a valid PDF, ELF file, or HTTP request looks like can produce structurally valid seeds or input grammars, getting a fuzzer past format checks that would stop mutation alone.
- Crash triage. Fuzzers produce many crashing inputs, most of them duplicates of a few root causes. LLMs can read sanitizer reports and stack traces, deduplicate, explain the root cause, and estimate exploitability — and then propose a patch.
- Code review at scale. LLMs can flag suspicious code (Q1 from §9.1), but they also hallucinate bugs that are not there. The strongest systems therefore combine them with tools that produce evidence: a model suggests where a bug might be, and a fuzzer or symbolic executor confirms it with a concrete crashing input.
DARPA’s AI Cyber Challenge (AIxCC) built a competition around exactly this pipeline: autonomous systems combining LLMs with fuzzing and program analysis had to find and patch vulnerabilities in real open-source software such as the Linux kernel and widely used libraries.
Note. The usual cautions apply. LLM findings without a reproducing input are hypotheses, not bugs; and the same capabilities help attackers. The rest of this course returns to AI as both a security tool and a new attack surface.
Check Your Understanding
1. In the code below, explain the two separate questions a bug hunter must answer, and give an input property that answers the second.
if (magic == 0x31323334) { memcpy(dst, src, len); }
Answer
Q1 (is it a bug?): does memcpy copy more than dst can hold, i.e., is len
attacker-influenced and unchecked? Q2 (reachability): can an input make magic equal
0x31323334 so execution reaches the memcpy? If magic is read from the first four
bytes of the input on a little-endian machine, the input must start with the bytes
34 33 32 31, i.e., the string "4321".
2. A test suite achieves 100% statement coverage of a function. Does it necessarily achieve 100% branch coverage? Give an example.
Answer
No. For if (a > 10) r += 1; the single test a = 11 executes every statement, but
the false outcome of the branch (skipping r += 1) is never taken, so branch coverage
is 50%. Bugs that occur only when a branch is not taken (e.g., a variable left
uninitialized) are missed.
3. Why does AFL record edges (prev ^ cur) rather than just which basic blocks
executed? Why is prev_location shifted right by one?
Answer
Two inputs can execute the same set of blocks in different orders or along different transitions (e.g., A→B→C vs. A→C plus B elsewhere); edges distinguish these behaviors, giving a finer fitness signal. The shift makes the index asymmetric, so A→B and B→A map to different bitmap entries, and a tight self-loop A→A does not always map to index 0.
4. Your fuzzer has run for a day on a parser with no crashes. You rebuild with
-fsanitize=address and it finds three bugs in an hour. Why?
Answer
Most memory errors — small overflows, use-after-free, reading freed memory — corrupt memory silently without crashing, so the fuzzer cannot observe them. ASan checks every access against shadow memory and aborts immediately with a report on the first invalid access, turning silent corruption into a detectable crash.
5. Explain why a mutation-based fuzzer struggles with
if (crc32(pkt, n) == pkt->checksum), and name two ways to get past it.
Answer
Almost any mutation of the packet body changes its CRC so the check fails, and the check is a single edge with no partial-credit feedback; the fuzzer never gets past it. Remedies: patch or compile out the check in the fuzzing build (and fix up checksums when reproducing); use a structure-aware or grammar-based generator that recomputes the checksum; use concolic/hybrid fuzzing to solve for inputs (though CRCs over long data can still be hard for solvers — patching is the common practical fix).
6. For if (x > 5) { if (x * 2 == 22) bug(); } with 32-bit int x, write the path
constraint for reaching bug() and give a solution.
Answer
x > 5 ∧ 2x = 22 (in 32-bit arithmetic). x = 11 satisfies it. (Over 32-bit
bit-vectors, 2x = 22 has a second solution, x = 11 + 2³¹, which as a signed int is
negative and so fails x > 5 — an example of why solvers must model machine
arithmetic exactly.)
7. What is path explosion, and how does hybrid fuzzing (e.g., QSYM) avoid most of its cost?
Answer
Each symbolic branch can fork execution, so the number of paths grows exponentially with the number of branches and loop iterations, making exhaustive symbolic execution infeasible for real programs. Hybrid fuzzing lets a cheap fuzzer explore most paths concretely and invokes concolic execution only on specific inputs and specific branches the fuzzer cannot pass, solving one constraint at a time instead of enumerating all paths.
Summary
- Vulnerability discovery has two halves: locating a bug and reaching it with attacker-controlled input.
- Code review finds bugs but does not scale; testing is classified as manual vs. automated and black-box vs. white-box.
- Code coverage (function, statement, branch) measures what tests exercise; untested code cannot yield bugs.
- Coverage-guided fuzzing (AFL, AFL++, libFuzzer) mutates inputs and keeps those that reach new edges, peeling through checks incrementally. Sanitizers (ASan, UBSan) make silent memory errors visible to the fuzzer.
- Binary-only fuzzing obtains coverage via dynamic instrumentation, emulation, or hardware tracing (e.g., WinAFL).
- Fuzzing is effective and produces proof-of-concept inputs but is non-deterministic and blocked by magic values, checksums, and grammars.
- Symbolic execution collects path constraints and solves them with SMT solvers (KLEE, angr) but suffers from path explosion; concolic/whitebox fuzzing (SAGE) and hybrid fuzzing (Driller, QSYM) combine it with concrete execution.
- LLMs increasingly generate harnesses and seeds, triage crashes, and propose patches — most reliably when paired with tools that produce concrete evidence.
Connection to the Labs
There is no dedicated lab for this chapter, but the techniques apply to all of them. Try these exercises in your VM:
- Fuzz the
crackme487.cexample above with AFL/AFL++ and measure how long it takes to find the crash; then replace the three byte checks with a single 32-bit comparison and observe how much harder it becomes (and how AFL++’s CmpLog mode changes that). - Write a libFuzzer harness for the vulnerable functions in Lab 2 or Lab 3 and check that ASan pinpoints the overflow or format string bug.
- Use angr or Z3 to solve for an input that reaches a guarded branch in a small crackme.
- Many final-project ideas (fuzzing AI agents or MCP servers, LLM-generated harnesses, automatic patch generation) build directly on this chapter.
Further Reading
- Patrice Godefroid, Michael Y. Levin, and David Molnar. “Automated Whitebox Fuzz Testing.” NDSS, 2008.
- Cristian Cadar, Daniel Dunbar, and Dawson Engler. “KLEE: Unassisted and Automatic Generation of High-Coverage Tests for Complex Systems Programs.” USENIX OSDI, 2008.
- Nick Stephens et al. “Driller: Augmenting Fuzzing Through Selective Symbolic Execution.” NDSS, 2016.
- Insu Yun, Sangho Lee, Meng Xu, Yeongjin Jang, and Taesoo Kim. “QSYM: A Practical Concolic Execution Engine Tailored for Hybrid Fuzzing.” USENIX Security, 2018. https://www.usenix.org/system/files/conference/usenixsecurity18/sec18-yun.pdf
- AFL (original): https://lcamtuf.coredump.cx/afl/
- AFL++: https://github.com/AFLplusplus/AFLplusplus
- libFuzzer tutorial: https://github.com/google/fuzzing/blob/master/tutorial/libFuzzerTutorial.md
- afl-training workshop: https://github.com/mykter/afl-training
- WinAFL: https://github.com/googleprojectzero/winafl
- KLEE: https://klee.github.io/ · angr: https://angr.io/
- DARPA Cyber Grand Challenge: https://www.darpa.mil/research/programs/cyber-grand-challenge
- AI Cyber Challenge: https://aicyberchallenge.com/