Read the original article here.

---

Module: The Forbidden Code

Technique: Fuzzing - Unlocking Software Secrets

---

Welcome to the world of "Forbidden Code," where we explore the techniques that peel back the layers of software to expose its deepest weaknesses. Forget structured test cases and clean unit tests for a moment. We're diving into Fuzzing, a technique that embraces chaos to reveal vulnerabilities no one intended to be found. It's not taught in basic programming courses because it challenges conventional testing paradigms and is a cornerstone of vulnerability research and security auditing.

1. What is Fuzzing? Embracing the Unexpected

In the realm of "forbidden" techniques, fuzzing stands out. It's about throwing rules out the window and seeing what breaks.

Fuzzing (or Fuzz Testing): An automated software testing technique that involves providing invalid, unexpected, or purely random data as inputs to a computer program. The goal is to trigger crashes, assertion failures, memory leaks, or any other unexpected behavior that could indicate a bug or security vulnerability.

Think of it as deliberately trying to confuse and overload a program with garbage data to see if it trips over itself. While standard testing feeds a program carefully crafted valid inputs to check expected outputs, fuzzing feeds it invalid or malformed inputs to check for unexpected failures.

Why is this "Underground"? Traditional software development often focuses on happy paths and expected inputs. Fuzzing, however, focuses on the edge cases, the malformed data, the adversarial inputs that a developer might not have considered. It's a technique heavily used by security researchers, reverse engineers, and vulnerability hunters – people looking for ways into or through software defenses, rather than just verifying its intended function.

2. The Genesis of Chaos: History of Fuzzing

The idea of throwing random data at a program isn't new, but the term "fuzzing" has a specific origin that solidified it as a distinct technique.

Early Randomness (Pre-Fuzz): The concept dates back to the 1950s. Imagine using discarded punch cards or random number lists as program input just to see what happened. If the program stumbled or crashed, you found a bug. This early, crude form was essentially "random testing" or "monkey testing."

Monkey Testing: A testing technique where inputs are generated randomly, often without any specific knowledge of the system being tested, mimicking a monkey randomly hitting keys on a keyboard. While simple, it can sometimes uncover unexpected bugs.

In the early 1980s, researchers like Duran and Ntafos formally studied the effectiveness of random testing, concluding it could be a cost-effective alternative to more systematic methods, despite being perceived as less sophisticated. Tools like "The Monkey" for Mac OS applications emerged to automate this random input generation.

The Birth of "Fuzz" (1988): The term "fuzz" was coined by Professor Barton Miller at the University of Wisconsin. During a graduate class project, the team developed a tool to bombard UNIX command-line utilities with streams of random characters and signals. Their goal was simple: make the utilities crash or hang.

The results were eye-opening: they crashed 25-33% of the tested utilities. This wasn't just random failure; it exposed fundamental reliability issues. The source code and results were made public, allowing others to replicate and build upon this work. This early method was a form of black-box, generation-based, unstructured (dumb) fuzzing. The key takeaway was using crashes or hangs as a simple, universal "oracle" (way to detect a failure).

Test Oracle: A mechanism or principle used to determine if a test case has passed or failed. In fuzzing, a simple oracle is often a program crash or hang, indicating unexpected behavior. More sophisticated oracles can involve checking output against a specification or comparing behavior to a known-good version.

Modern Evolution: From academic curiosity, fuzzing grew into a critical industrial practice.

• 2012: Google introduced ClusterFuzz, a large-scale cloud-based fuzzer for security-critical components like the Chrome browser. This emphasized its role in finding security vulnerabilities.
• 2014-2015: Fuzzing proved its mettle by helping find or demonstrating the findability of major vulnerabilities like Shellshock (in the Bash shell) and Heartbleed (in OpenSSL). These were critical flaws impacting vast swathes of the internet, highlighting fuzzing's power in auditing core infrastructure software.
  • Shellshock: A family of bugs in the Bash shell that allowed attackers to execute arbitrary commands via crafted environmental variables, often delivered through web server requests. Fuzzing (specifically AFL) was instrumental in finding many variants.
  • Heartbleed: A severe vulnerability in the OpenSSL cryptography library that allowed attackers to read sensitive data (like private keys and user credentials) from server memory by exploiting a simple boundary check missing in the TLS 'heartbeat' extension. Fuzzing demonstrated how easily it could have been found.
• 2016 onwards: Fuzzing became central to automated vulnerability detection contests like the DARPA Cyber Grand Challenge, proving its effectiveness in discovering flaws in real-time. Companies like Microsoft launched their own fuzzing services (Project Springfield, OneFuzz). Google's OSS-Fuzz provided continuous fuzzing for critical open-source projects.
• Black Hat 2018: A dramatic example of fuzzing's power: uncovering a hidden RISC core within a processor that could bypass security rings. This exemplifies how fuzzing can reveal hardware-level secrets and unintended features by observing unexpected behavior under stress – truly "forbidden code" territory.

3. Classifying the Chaos: Types of Fuzzers

Not all fuzzers are created equal. They differ in how they generate inputs and how much they "know" about the program or its input structure. Understanding these types is crucial for choosing the right tool for the job.

Fuzzers can generally be categorized based on three axes:

1. How inputs are created: Mutation-based vs. Generation-based
2. Awareness of input format: Dumb (Unstructured) vs. Smart (Structured)
3. Awareness of program internals: Black-box vs. Grey-box vs. White-box

Let's break these down.

3.1. Input Creation Strategy: Mutation vs. Generation

• Mutation-Based Fuzzers:

  • Concept: Start with a set of valid example inputs (called "seeds"). Generate new inputs by making small, often random, changes (mutations) to these seeds.
  • How it works: Take a seed file (e.g., a valid PNG image), randomly flip bits, insert/delete bytes, change values, duplicate blocks, etc. The mutated output is fed to the program.
  • Advantage: Doesn't require prior knowledge of the input format; simple to implement. Relies on having a good corpus of seed files that cover different aspects of the input format.
  • Example: Fuzzing an image library with a seed corpus of different image types (.jpg, .png, .gif). The fuzzer mutates these files.
  • Consideration: The quality and variety of the initial seed corpus significantly impact effectiveness. Techniques exist for automated seed selection to maximize coverage.

• Generation-Based Fuzzers:

  • Concept: Generate inputs from scratch based on a model or specification of the input format.
  • How it works: If the input is a network protocol, the fuzzer uses the protocol specification to build valid and invalid message sequences. If it's a file format defined by a grammar, it generates files according to the grammar rules, potentially introducing invalid elements deliberately.
  • Advantage: Can generate a higher proportion of inputs that reach deeper logic (compared to dumb mutation) because they adhere somewhat to the expected structure. Can explore paths defined by the model more systematically. Doesn't require existing seed inputs (though they can often be used to help build the model).
  • Consideration: Requires an accurate model of the input format, which can be difficult or impossible to obtain for complex or proprietary formats.

• Hybrid Approaches: Some advanced fuzzers combine both strategies, mutating seeds while also having some understanding of the input structure to guide mutations or generate new, complex inputs.

3.2. Input Structure Awareness: Dumb vs. Smart

This axis relates closely to the generation vs. mutation types, but focuses specifically on the understanding of the input format.

• Dumb (Unstructured) Fuzzers:

  • Concept: Treat the input as a stream of bytes without any knowledge of its internal structure or format rules.
  • How it works: Primarily mutation-based. Apply simple byte-level or bit-level mutations (flipping bits, inserting random bytes, duplicating sections) without regard for what those bytes represent (e.g., is this byte part of a header checksum? is this sequence a valid command?).
  • Advantage: Highly portable and easy to apply to any program that accepts input, regardless of complexity or proprietary format. Requires no manual effort to define input structure.
  • Consideration: May spend a lot of time generating inputs that are immediately rejected by the program's initial input parser (e.g., invalid headers, incorrect magic bytes). This limits the ability to reach and test deeper logic.
  • Example: Applying random byte mutations to a compiled executable file and running it. Most mutations will just break the file and cause an immediate crash or rejection. Similarly, randomly changing bytes in a complex file format like a video or database file is unlikely to produce anything that gets processed beyond basic parsing checks.
  • Classic Limitation Example (CRC Checksum): If an input file has a CRC (Cyclic Redundancy Check) checksum to verify data integrity, a dumb fuzzer changing data bytes is extremely unlikely to also correctly compute and update the checksum. The program will likely fail the checksum validation immediately, and the mutated input won't reach the code that processes the actual data.

• Smart (Structured) Fuzzers:

  • Concept: Understand the structure of the input format (e.g., file format specification, network protocol grammar, command syntax).
  • How it works: Uses this understanding to generate inputs that are syntactically valid or semi-valid, or to apply mutations that make sense within the format's rules (e.g., changing a length field correctly, modifying parameters within valid ranges, creating valid but nonsensical combinations). This helps bypass initial parsing layers.
  • Advantage: Can generate a much higher proportion of inputs that pass basic validation and reach deeper into the program's logic, increasing the chance of finding bugs hidden there.
  • Consideration: Requires significant effort to define the input model. If the format is complex, undocumented, or changes frequently, building and maintaining the model is challenging. Techniques like grammar induction (learning the structure from examples) can help but are not always perfect.
  • Example: A fuzzer that understands the structure of a JSON request. It can generate JSON objects with valid syntax but unexpected values, missing fields, deeply nested structures, or incorrect data types, all while ensuring the overall structure remains syntactically valid JSON.

3.3. Program Structure Awareness: Black-box, Grey-box, White-box

This axis describes how much visibility the fuzzer has into the internal workings of the program being tested. This knowledge is often used to guide the input generation or mutation process towards unexplored code paths.

• Black-Box Fuzzers:

  • Concept: Treat the program as an opaque "black box." No knowledge of internal code structure is used to guide fuzzing.
  • How it works: Inputs are generated or mutated based on external factors (e.g., random generation, mutation of seeds) without feedback from the program's execution path.
  • Advantage: Simple to set up and run. Scales well to large programs of unknown internal complexity. Can execute inputs very quickly.
  • Consideration: May spend a lot of time exploring the same code paths repeatedly. Less likely to reach deep or complex logic unless a random input happens to hit the right sequence. Prone to finding "shallow" bugs near the input handling layer.
  • Example: The original 1988 fuzzer, simply generating random bytes and checking for crashes. More sophisticated black-box approaches might monitor output or timing to infer behavior, but they don't analyze the code itself.

• White-Box Fuzzers:

  • Concept: Have full visibility into the program's source code or binary structure. Use program analysis techniques to guide input generation.
  • How it works: Often leverage symbolic execution or concolic execution.
    • Symbolic Execution: Analyze the program's code to represent variables as symbolic values rather than concrete data. Trace possible execution paths. As the fuzzer encounters conditional branches (if/else statements, loops), it attempts to generate constraints on the input values that would force execution down a specific, unexplored path.
    • Concolic Execution (Concrete + Symbolic): A hybrid approach that executes the program with concrete inputs while simultaneously performing symbolic execution along the executed path. When a branch is encountered, it uses symbolic execution to generate new concrete inputs that satisfy constraints to explore alternative paths.
  • Advantage: Can systematically explore different program paths and generate inputs specifically designed to reach deep, complex logic or specific critical code locations (like potential vulnerability points). Highly effective at finding bugs hidden deep within the code.
  • Consideration: Computationally very expensive and often doesn't scale well to large, complex programs due to the "path explosion" problem (the number of possible execution paths grows exponentially). Analyzing the program can take significantly longer than executing inputs.
  • Example: SAGE (Scalable Automated Guided Execution) from Microsoft, used for finding bugs in Windows components.

• Grey-Box Fuzzers:

  • Concept: Lie between black-box and white-box. They don't perform deep static code analysis like white-box fuzzers but gain some insight into the program's execution using lightweight techniques, most commonly code instrumentation.
  • How it works: The program is compiled with instrumentation that records which basic blocks of code are executed or which transitions between blocks occur when a given input is processed. The fuzzer uses this feedback (typically code coverage) to prioritize or mutate inputs that lead to new code paths being explored. Inputs that hit new code are kept and used as seeds for further mutation.
  • Advantage: Achieves a good balance between the speed of black-box fuzzing and the effectiveness of white-box fuzzing in reaching deeper code. The instrumentation overhead is relatively low compared to full program analysis. Extremely efficient for vulnerability detection in practice.
  • Consideration: Doesn't guarantee full path coverage like a theoretical white-box fuzzer might attempt. Still relies on mutations potentially hitting interesting program states.
  • Example: AFL (American Fuzzy Lop) and libFuzzer. These are prominent examples that use coverage feedback to guide mutations. If mutating an input causes the program to execute a piece of code not seen before, the fuzzer recognizes this and prioritizes further mutations of that input.

4. Fuzzing in Practice: Finding What Others Miss

Fuzzing isn't just an academic exercise; it's a powerful tool for revealing actual bugs and security vulnerabilities that elude traditional testing methods.

Exposing Bugs: The primary goal is to find instances where the program behaves unexpectedly. While fuzzers can't prove the absence of bugs (a program might still fail on an input not yet tested), they are highly effective at proving their presence.

• Detecting Crashes: The most obvious failure. A crash indicates a severe issue, often related to memory corruption (buffer overflows, use-after-free, null pointer dereferences) which can frequently be exploited for denial-of-service or even arbitrary code execution. Fuzzing excels at triggering these conditions by corrupting data structures or providing unexpected sizes/values.
• Beyond the Crash: The Oracle Problem Revisited: Simply checking for crashes is a simple test oracle. However, many bugs don't cause an immediate crash. For example, a buffer overflow in C/C++ might corrupt memory but the program continues running until much later, or its behavior becomes undefined. This is where sanitizers come in.

Sanitizers: Runtime tools or libraries that instrument code to detect specific types of programming errors that might not immediately cause a crash but represent serious bugs or vulnerabilities. When a sanitizer detects an error (like a buffer overflow), it deliberately causes the program to crash with a clear error report, making the bug easy for the fuzzer to detect.

Using sanitizers turns subtle issues into detectable crashes, greatly increasing the types of bugs a fuzzer can find. Common sanitizers include: * AddressSanitizer (ASan): Detects memory safety errors like buffer overflows, use-after-free, double-free. * ThreadSanitizer (TSan): Detects data races and deadlocks in multi-threaded code. * UndefinedBehaviorSanitizer (UBSan): Detects various types of undefined behavior in C/C++ (e.g., integer overflow, division by zero, invalid pointer casts). * LeakSanitizer (LSan): Detects memory leaks. * Control Flow Integrity Sanitizer (CFISanitizer): Detects control-flow hijacking attempts by verifying that indirect jumps and calls land on valid instruction addresses.

• Differential Fuzzing: Another technique to overcome the oracle problem. If you have two different implementations of the same specification (e.g., two different JPEG parsing libraries, or two versions of the same web server), you can fuzz both with the same inputs. If they produce different outputs or exhibit different behavior (one crashes, the other doesn't; they return different results), it suggests a bug in at least one of them.

Validating Static Analysis: Static analysis tools analyze code without running it, often reporting potential issues. These tools can have "false positives" (reporting a problem that doesn't actually exist in practice). Fuzzing can be used to validate these reports. If a static analyzer flags a potential buffer overflow at a specific code location, a fuzzer can attempt to generate an input that actually triggers execution at that location and causes the overflow, confirming the static analysis finding.

Browser Security: Modern web browsers are prime targets for attack and heavy users of fuzzing. Their complexity and the untrusted nature of web content make robust input handling critical. Projects like ClusterFuzz for Chrome and Microsoft's efforts on Edge/IE involve massive, continuous fuzzing campaigns generating trillions of inputs to find subtle vulnerabilities in rendering engines, JavaScript engines, and network handling code.

5. Taming the Chaos: The Fuzzing Toolchain

Running a fuzzer generates a colossal amount of data. A single fuzzing campaign can produce thousands or even millions of unique failure-inducing inputs. Turning this flood of failures into actionable bug reports requires automated tooling.

• Automated Bug Triage:

  • Problem: Many different inputs might trigger the same underlying bug. You don't want to report the same crash thousands of times. You also need to prioritize bugs.
  • Solution: Tools analyze the crashing state (e.g., the call stack trace at the point of the crash) to group inputs that likely hit the same root cause. They can also attempt to rate the exploitability or severity of the crash (e.g., using tools like Microsoft's "!exploitable") to help developers prioritize fixing critical vulnerabilities.
  • Integration: Automated systems often report newly identified, unique bugs directly to a bug tracking system, notifying developers and sometimes even monitoring if the bug gets fixed.

• Automated Input Minimization:

  • Problem: A crashing input generated by a fuzzer can be very large and mostly junk data, making it hard for a developer to understand why it crashes.
  • Solution: Tools take a large, crashing input and automatically remove as many bytes or parts of the input as possible while still retaining the property of triggering the original crash.
  • How it works: Techniques like Delta Debugging use algorithms similar to binary search to isolate the critical parts of the input by repeatedly removing chunks and checking if the crash still occurs.
  • Benefit: Provides developers with a small, clean test case that makes debugging significantly easier.

6. Fuzzing in Your Underground Arsenal

Fuzzing is not a silver bullet, but it is an indispensable weapon in the arsenal of anyone seeking to find deep, unexpected flaws in software. It complements, rather than replaces, other testing methods like unit testing, integration testing, and static analysis.

By deliberately providing invalid, unexpected, or semi-valid inputs, fuzzing stresses programs in ways developers might not have anticipated. It's particularly effective at uncovering:

• Memory corruption bugs (leading to crashes or potential exploits)
• Assertion failures
• Undefined behavior
• Logic errors triggered by unexpected data states
• Vulnerabilities in parsers, protocol handlers, and file format readers

Whether you're auditing closed-source binaries (black-box), leveraging lightweight instrumentation (grey-box), or diving deep with analysis (white-box), fuzzing provides a path to uncovering secrets hidden within the code – the forbidden knowledge of how software can be made to misbehave.

This is just the beginning. As you delve deeper into "The Forbidden Code," you'll see how fuzzing integrates with other techniques like reverse engineering and exploit development to turn unexpected behavior into concrete security findings.

7. Related Techniques (Briefly)

• Concolic Testing: A specific type of white-box fuzzing combining concrete and symbolic execution to explore paths systematically.
• Symbolic Execution: A core program analysis technique used by white-box fuzzers to reason about program paths and generate inputs.
• Runtime Error Detection: This is what sanitizers and other tools provide – the ability to detect errors during execution, which is crucial for a fuzzer to identify failures beyond simple crashes.

Fuzzing is a dynamic and evolving field, constantly finding new ways to leverage computation and clever strategies to make software reveal its hidden flaws. Master this technique, and you gain a powerful capability to find vulnerabilities others cannot.