Buffer Overflows & Fuzzing

Buffers

A buffer is a block of memory (or other storage) used to hold data temporarily. Three ordinary examples show why buffers are so common, and so easy to get wrong: a calculator program storing a user's typed input until they press return; a program counting lines in a large file, which reads and processes the file a block at a time rather than loading the whole thing into memory or reading it one byte at a time; and a webserver building a log line by concatenating a timestamp and a page name in memory before writing the whole message out with a single system call.

Buffer Overflows

A buffer overflow, also called a buffer overrun, happens when a program that is meant to write data into a buffer instead writes past the end of it, into whatever memory happens to follow. The most common cause is simply a programmer allocating a fixed-size buffer and assuming, incorrectly, that it would always be large enough. Other causes include miscalculating the required size of a variable-length buffer, or making a wrong assumption about how much data a library call could write into a buffer passed to it.

What Can a Buffer Overflow Actually Do?

Writing past the end of a buffer can do anything from nothing at all to complete compromise, depending entirely on what happens to live in the memory that gets overwritten: the program might simply crash; a nearby variable's value might silently change; a stored return address might be corrupted; and in the worst case, an attacker can achieve arbitrary code execution.

Triggering an overflow is sometimes trivially easy — just send a program more data than it expects, over a network connection, say — but sometimes only occurs under very specific conditions: a message format might include a field that specifies the length of another field, and the overflow only appears if the actual data is longer than its own claimed length; or the bug might depend on several rare events lining up simultaneously, and only manifest after the software has run safely for years.

Exploiting a Buffer Overflow

Merely triggering an overflow is not the same as exploiting it — the most likely outcomes of an accidental overflow are nothing happening at all, or a crash. To turn an overflow into arbitrary code execution, an attacker typically wants to run code of their own choosing, often shellcode: a small program that opens a network connection back to the attacker and runs whatever command it's given. Aleph One's 1996 Phrack article "Smashing the Stack for Fun and Profit" laid out this technique in detail and remains the foundational reference for how stack-based overflows are actually exploited [1]. Two separate problems have to be solved: getting shellcode into memory on the target at all, and then actually making the target jump to and run it.

Sending Shellcode

The obvious approach is to send the shellcode inside the overflowing buffer itself, but several practical constraints get in the way. The buffer might be small, forcing the shellcode to be optimised for size, or hand-coded, to fit. The program reading into the buffer might expect text or some other specific format, in which case certain byte values — a zero byte, which many languages and libraries treat as a string terminator, is a classic example — can't simply appear in the shellcode unmodified, and need an alternate encoding, or hand-coding, to avoid them. And the buffer might not sit at the same memory address every time the program runs, which breaks any shellcode relying on absolute jumps — a problem addressed by compiling position-independent code (PIC) instead.

Running Shellcode

Making the shellcode actually run means carefully examining the compiled program's memory layout and writing a value into the buffer that redirects execution to the right address — a value that can vary between different builds of the same program, and even between separate runs of the identical binary. Heap-spraying is one response to that unpredictability: fill memory with many copies of the shellcode, preceded by "ramps" that lead into it, so that a jump to almost any address within the sprayed region ends up landing somewhere that leads to the shellcode. Heap-spraying usually still needs a separate way of getting the shellcode into memory in the first place — JavaScript running inside a buggy browser plugin was a common vector historically.

Countermeasures

Defending against buffer overflows works at several different layers at once, and no single layer is sufficient alone. The most direct defence is simply not writing buggy code — hard to guarantee, but testing and auditing help. Using a language with automated memory management removes the underlying bug class almost entirely, though it isn't a universal option: high-performance code, systems code, and the runtimes that implement memory-managed languages in the first place still need to be written in something else. Address Space Layout Randomisation (ASLR) has the operating system pick a different memory layout on every run specifically to defeat the "same address every time" assumption many exploits rely on. Hardware protection — memory segmentation, paging, and a no-execute flag on data pages — stops injected shellcode from being run as code even if it does land in memory. Malware detection and web application firewalls (see Port Scanning & Firewalls) can catch some exploitation attempts in transit; Nozzle, for instance, was built specifically to detect heap-spraying JavaScript by analysing the objects being allocated on the heap [2]. And, mundanely but importantly, installing security updates and patches promptly closes known holes before they get exploited at scale.

Fuzz Testing

The basic idea behind fuzz testing is almost embarrassingly simple: run a program with random input, and see whether it crashes. If it does, log the input for later analysis; if not, try again — and modern fuzzers can try billions of inputs in a single run. Some bugs only show up under a specialised execution environment (Valgrind, for instance) that forces a visible crash on a memory-management error that would otherwise go unnoticed. The idea itself is older than it might seem: Miller, Fredriksen and So's 1990 study of the reliability of ordinary Unix utilities, feeding them pseudo-random input, was among the first to systematically demonstrate just how many production tools crashed or hung on unexpected input [3] — establishing fuzzing as a genuinely productive way to find bugs, not just a curiosity.

Problems with Purely Random Fuzz Testing

Purely random input struggles against a very common code shape:

try {
    f = read_input_file();
    x = parse(f);
}
catch (ParseError e) {
    println("Error: malformed input.");
}
// do something interesting with x

Random bytes almost never happen to parse successfully, so the genuinely interesting logic that runs on a successfully-parsed x rarely gets exercised at all — most random inputs are rejected before they ever reach it. The same problem shows up wherever behaviour is gated behind a narrow condition:

if (complex_test(x) && complex_test(y)) {
    // do something interesting with x and y
}
else {
    // do something boring with x and y
}

Purely random x and y satisfy complex_test so rarely that the interesting branch is, in practice, almost never reached by chance alone.

Improving Fuzz Testing: Generation vs. Mutation

A generation-based fuzzer constructs a new random input from scratch each time. A mutation-based fuzzer instead takes existing inputs and alters them — flipping random bits, inserting random bytes, or splitting, merging and concatenating existing test cases — which can be considerably better at producing genuinely interesting test inputs, provided it starts from a reasonably good initial corpus. Fuzzing a parser for HTML fragments illustrates the idea: starting from a small corpus like <p>Hello.</p> and <em>Yes.</em>, mutation might produce <p>Hello.</p><p>Hello.</p>, the malformed <p>He<em>Yes.</em>, or fragments like <en>Yes.</em> and s.</em> that a purely generative fuzzer starting from nothing would be extremely unlikely to stumble on by chance.

Improving Fuzz Testing: Unstructured vs. Structured

An unstructured fuzzer has no knowledge of the input format it's generating for. A structured fuzzer works from a grammar, or some other formal description, that lets it generate or recognise syntactically valid inputs directly. Structured fuzzing is more likely to reach genuinely interesting program paths — especially where the input format includes checksums that an unstructured fuzzer would almost never satisfy by chance — but it misses bugs specifically in the parser itself, needs an accurate grammar supplied up front, and generates test cases more slowly than simply mutating bytes.

Improving Fuzz Testing: Black, Grey and White Box

A black box fuzzer has no visibility into the program's internal structure at all — rare in practice, since even minimal instrumentation tends to help. A grey box fuzzer uses lightweight instrumentation, via a special compiler pass or a virtual machine, to track which execution path each test case takes; when a test case produces a genuinely new trace, later mutations focus around it. A white box fuzzer goes further still, using symbolic execution and constraint solvers to construct test cases that deliberately target specific, previously-unexplored execution paths. Moving from black to grey to white box trades fuzzing speed and simplicity for the ability to reach code paths that random or lightly-guided mutation would essentially never find.

Example: American Fuzzy Lop

American Fuzzy Lop (AFL), and its actively maintained successor AFL++, is a mutation-based, unstructured, grey-box fuzzer [4]. It is not the most technically sophisticated fuzzer available, and yet has been used to find an enormous number of real bugs in widely-used software. Its own track record suggests a few genuinely transferable lessons: sensible defaults and ease of use matter more for real-world adoption than raw flexibility; reliability and speed matter almost as much as cleverness; and in practice, sheer volume of test cases often finds more bugs than a smaller set of higher-quality ones.

Ethical Issues: Buffer Overflows

Buffer overflows raise mostly the same ethical questions as other software vulnerabilities, applied to a specific, well-understood bug class. As a developer, what obligation do you have to test for, or actively minimise, the likelihood of buffer overflows in your own code? As a system administrator, what obligation do you have to limit the chance that one gets exploited if it exists? As a penetration tester who discovers one, when and how should you disclose it — and to whom? As a developer who is told about one in your own software, what should you do, and how quickly? And more fundamentally: is it ever ethical to deliberately introduce a buffer overflow into a software project, or to exploit one you've found in someone else's?

Ethical Issues: Fuzz Testing

Fuzz testing raises much the same questions as any other security tool with a genuinely dual offensive/defensive use. Is it ethical to write a fuzz tester? To distribute one publicly? To restrict the distribution of fuzzers by law? And is it ethical to run a fuzz tester over the network against a system you don't own, without the owner's knowledge or consent?

References

  1. Aleph One (Elias Levy). (1996). Smashing the Stack for Fun and Profit. Phrack Magazine, 7(49), article 14. https://phrack.org/issues/49/14
  2. Ratanaworabhan, P., Livshits, B., & Zorn, B. (2009). NOZZLE: A Defense Against Heap-Spraying Code Injection Attacks. 18th USENIX Security Symposium.
  3. Miller, B. P., Fredriksen, L., & So, B. (1990). An Empirical Study of the Reliability of UNIX Utilities. Communications of the ACM, 33(12), 32–44. https://doi.org/10.1145/96267.96279
  4. Fioraldi, A., Maier, D. C., Eißfeldt, H., & Heuse, M. (2020). AFL++: Combining Incremental Steps of Fuzzing Research. 14th USENIX Workshop on Offensive Technologies (WOOT '20).