Demystifying Fuzzer Behaviour

Demystifying Fuzzer Behaviour

Speakers: Addison

Conference: 39C3

YouTube: https://www.youtube.com/watch?v=h3UcecN5fvQ

Overview

In this insightful talk, "Demystifying Fuzzer Behaviour," Addison, a PhD student and former teacher, challenges the prevailing, often uncritical, perception of fuzzing as a "magic box" solution for bug discovery. The presentation aims to shed light on the fundamental limitations and misunderstood aspects of fuzzers, advocating for a return to scientific rigor and deeper understanding within the security research community. Addison argues that while fuzzing is a powerful technique, its efficacy is often hampered by critical weaknesses in our understanding of how fuzzers interact with target programs, particularly concerning state, input interpretation, and search strategies.

The talk is driven by Addison's passion for education, a desire to combat objective-oriented research focused solely on KPIs, and a commitment to scientific rigor. The core message is that security practitioners and researchers alike must move beyond superficial metrics like code coverage and engage in a more critical, empirical analysis of fuzzer behavior. By dissecting the underlying assumptions and mechanisms of fuzzing, Addison reveals that many of our current approaches are fundamentally limited, leading to an incomplete and often misleading picture of software security. This deep dive into the theoretical and practical shortcomings of fuzzing serves as a call to action for a more thoughtful and principled approach to software testing.

Background

▶ Watch: Speaker's motivation for demystifying fuzzer behavior (0:56)

To understand the intricacies of fuzzer behavior, Addison first establishes a foundational understanding of what testing truly entails. He posits that testing isn't merely inspecting a program but rather an empirical process akin to the scientific method: proposing a falsifiable hypothesis about a program's behavior, running an experiment, collecting results, and checking if those results falsify the hypothesis, thereby revealing a bug. This approach emphasizes disproving assumptions rather than proving correctness.

Programs operate within an input space, which represents all possible inputs they can receive. Testing typically involves selecting a finite subset of this space. To measure how completely a program is tested, we often rely on code coverage, which subdivides the input space based on the program's internal implementation paths. The intuition is that if these subdivisions (or partitions) are aligned with the program's implementation, covering them provides a good indicator of testing thoroughness, as bugs are often linked to specific code paths.

Fuzzing, a prominent empirical testing technique, comes in two main flavors:

1. Generative Fuzzing: This involves sampling inputs directly from the input space, typically using a grammar to construct valid inputs. Its strengths include not requiring program feedback and high flexibility. However, it often has a limited "radius" (tending to generate smaller, simpler inputs) and is not inherently aligned with program-based partitions, making its bug discovery less efficient for complex internal logic.
2. Mutational Fuzzing: This method starts with existing inputs (seeds) and iteratively transforms them through mutations. When a mutation leads to an input that crosses a new program partition (e.g., discovers new code coverage), that input is added to the pool of seeds. This is known as guided mutational fuzzing, where program feedback directs the search. The theoretical advantages include exploring the program according to its structure and enabling a more "local" generation of inputs within specific partitions.

However, Addison immediately introduces skepticism, posing questions about whether this seemingly "awesome system" truly finds all bugs, especially when considering unseen partitions, bad luck in mutation draws, or other missing elements. This sets the stage for the talk's core revelations about the critical weaknesses in our understanding of fuzzer behavior.

Key Findings

▶ Watch: Fundamental question: What does it mean to test? (3:38)

Addison systematically dismantles common assumptions about fuzzing by highlighting four critical weaknesses that limit both research and practice:

1. Fuzzers struggle with stateful programs: Modern software is highly stateful, from client-server applications and GUIs to CPUs, compilers, and databases. Fuzzers guided primarily by code coverage fail dramatically in these scenarios. Addison illustrates this with the Sokoban puzzle game, where a single function describes all puzzles. For a code coverage-guided fuzzer, every Sokoban puzzle appears to offer the same guidance, rendering it ineffective for solving complex, state-dependent problems. He provides a concrete example using Libé AFL attempting to reach a simple state (v=4), which required an astounding 250,000 to 34 million executions with havoc mutation. This demonstrates that classical partitioning methods, like code coverage, do not adequately model state, leading to severe limitations in exploration.

1. The Havoc Effect breaks locality of search: The assumption that mutations lead to locally related inputs is often false. Addison introduces the havoc effect, a phenomenon where "small mutations cause these destructive changes to later parts of the input or other parts of the input." Originally observed in parametric input generators (where random bits are transformed into structured data), Addison extends this concept to general programs. In the Sokoban example, changing an early move (e.g., "left" to "right") completely invalidates the subsequent sequence of moves, leading to a "dead" state. This reinterpretation of later input segments due to early mutations means that a local change does not guarantee a local search; instead, it can lead the fuzzer far away from its current exploration path, undermining the theoretical advantage of guided mutational fuzzing. This applies broadly to areas like networking, where changing a packet type reinterprets the entire payload.

1. Limited guidance and novelty search lead to local optima: Fuzzers, particularly those employing novelty search (prioritizing unseen paths), frequently get stuck in local optima. Once a fuzzer discovers a path, it may de-prioritize exploring alternative ways to reach the same or similar states, even if those alternatives could lead to further, more valuable discoveries. Addison demonstrates this by showing how a fuzzer might find a solution to a Sokoban puzzle after several attempts, but subsequent runs could get stuck or take vastly different amounts of time due to the lack of robust guidance. This means fuzzers may not thoroughly explore a program, potentially missing entire classes of bugs or specific program regions that are hard to reach without precise, often impossible-to-generalize, guidance. The two proposed "solutions" – making better guidance (which is often intractable) or intermittently restarting (which is merely hopeful) – underscore the depth of this problem.

1. Input projection (representation) fundamentally alters fuzzer effectiveness: The way an input is represented or provided to a program profoundly impacts how a fuzzer explores it. Addison argues that testing a program with just one type of input is insufficient. He uses the example of an XML parsing library: one can either provide raw XML documents or programmatically construct XML using the library's API. The latter, an input projection, effectively maps the original input space into a new one, which can realign bugs and program partitions. The real-world impact is stark: when researchers changed the input method for LibXML2 (one of the most aggressively fuzzed programs globally), it led to the discovery of numerous new issues, with 75 subsequent commits fixing bugs found by this new approach. This highlights that fuzzer effectiveness is not just about the fuzzer itself, but how well the input "aligns" with the program's internal logic and the types of bugs being sought.

Technical Deep Dive

▶ Watch: Empirical testing and falsifiable hypotheses explained (3:50)

Addison's talk delves into the technical underpinnings of these issues, using illustrative examples to clarify complex concepts.

The foundation of his critique rests on empirical testing, which he re-emphasizes as the "f* around and find out" method. This involves a cycle of falsifiable hypothesis** generation, experiment execution, result collection, and falsification checking. While conceptually sound, its application in fuzzing often falls short due to the complexities of program interaction.

The concept of input space subdivision is central. While code coverage is a popular and seemingly intuitive metric, it's merely one way to partition the input space. For a simple is_ascii function, covering all branches might seem sufficient. However, this simplicity breaks down rapidly with more complex, stateful programs.

Consider the v=4 example: a program where a variable v is incrementally updated based on input. Reaching v=4 might require a specific sequence of inputs. A code coverage-guided fuzzer like Libé AFL might see the same code paths being executed, even as v changes internally. This is because the state of v is not directly reflected in the code coverage metrics. The fuzzer doesn't "know" that v=4 is a special target state; it only sees the same if (v == 1) or if (v == 2) branches. This leads to the massive number of executions required just to stumble upon v=4, underscoring the inadequacy of coverage alone for stateful logic.

Generative fuzzing, while flexible, is often limited by its grammar. If a grammar tends to produce smaller strings, it creates a "limited radius" of exploration within the input space. This means large, complex inputs or those requiring specific, rarely generated sequences are unlikely to be found. Critically, without program feedback, it cannot adapt its generation strategy to explore interesting program behaviors.

Guided mutational fuzzing attempts to overcome this by using program feedback (like new code coverage) to inform subsequent mutations. The idea is to "progressively search the program by traversing the partitions of the input space." This implies a local generation of inputs, meaning mutations should ideally keep the fuzzer within a related region of the input space. However, the havoc effect directly contradicts this.

The havoc effect, as articulated in the context of parametric input generators, describes how a small change in a random byte sequence (e.g., 0x01 to 0x02) can lead to a drastic, destructive change in the derived structured input. Addison extends this to general program inputs: if a program reinterprets later parts of an input based on earlier parts (e.g., a network packet header dictating the interpretation of the payload), then a mutation to that early part will have non-local, potentially invalidating effects on the entire input. This means the fuzzer's "local search" assumption is fundamentally broken; it often jumps to entirely different, often invalid, regions of the input space, making efficient exploration challenging.

Furthermore, the concept of novelty search in guided fuzzing, where fuzzers prioritize inputs that discover new code paths, can lead to local optima. Once a fuzzer has "seen" a path, it may not revisit or extensively explore alternative ways to reach similar states or subsequent states. This is a known problem, suggesting that current guidance mechanisms are often too simplistic to enable thorough exploration of complex state machines or deeply nested conditions. The solutions, such as crafting better guidance (often an NP-hard problem in itself) or simply restarting the fuzzer, highlight the current state of limited understanding.

The most profound technical insight is input projection. Instead of simply feeding bytes or strings, we can abstract the input. For LibXML2, a highly complex XML parser, the traditional approach is to supply raw XML documents. However, by using the library's own API to programmatically construct XML, one effectively "projects" the input space. This changes the "surface" of the input that the fuzzer interacts with. The programmatic interface, being closer to the library's internal logic, naturally aligns the input structure with the program's partitions and the types of bugs that might arise from API misuse or specific data structures. This re-alignment, rather than just brute-force mutation of raw bytes, proved incredibly effective, leading to a surge of new bug discoveries in a program thought to be thoroughly tested. This demonstrates that the representation of the input is as crucial as, if not more than, the fuzzer's mutation strategy itself.

Demo / Proof of Concept

▶ Watch: Understanding code coverage for testing completeness (6:18)

Addison's talk ingeniously uses the Sokoban puzzle game as a live demonstration and a powerful metaphor to illustrate the fundamental challenges of fuzzing. He invites 15 volunteers to play a simplified version of Sokoban, where the goal is to push crates into target positions using basic moves (left, up, right, down, undo). This game, known to be NP-hard and PSPACE-complete to solve optimally, immediately highlights the complexity of state-dependent problems.

While the volunteers struggle, Addison "cheats" by introducing a fuzzer (which he controls) that quickly solves the puzzle. This initial "win" for the fuzzer is immediately qualified: he admits he specifically chose a puzzle that fuzzers are "very good at solving." This sets up the critical reveal that follows: even though the fuzzer can solve certain puzzles, the underlying mechanisms are deeply flawed for the general case.

The Sokoban game then becomes a recurring example throughout the talk to explain the key findings:

• Statefulness: The game's state (player position, crate positions) changes with each move. A code coverage-guided fuzzer sees the same "move left" function being called, regardless of the profound changes in the game state. This demonstrates why code coverage fails to provide meaningful guidance in state-rich environments.
• Havoc Effect: Changing an early move in a sequence of Sokoban inputs (e.g., "left" to "right") drastically alters the game's state, rendering subsequent, carefully planned moves meaningless or even impossible. This visually represents how local mutations can have non-local, destructive effects.
• Limited Guidance/Local Optima: The fuzzer might find a solution, but it might get stuck in local optima on other puzzles, unable to explore alternative paths or recover from suboptimal decisions.
• Input Projection: The speaker hints at his "cheating" fuzzer's secret: instead of simple directional moves, it operates on a higher level of abstraction, such as "move box 7 left four times." This demonstrates the power of input projection – by providing inputs that align with the intent of the game (moving boxes) rather than just raw actions, the fuzzer becomes far more effective.

The Sokoban demo effectively bridges the gap between abstract fuzzing concepts and tangible, relatable challenges, making the technical points more accessible and impactful.

Defensive Implications

▶ Watch: Transition to fuzzing: generative fuzzing introduced (7:30)

Addison’s talk offers crucial guidance for both practitioners and researchers aiming to improve software security. The overarching message for defenders is to move beyond treating fuzzers as black boxes and to cultivate a deep, critical understanding of their interaction with specific target programs.

1. Question Fuzzer Behavior and Assumptions: Defenders should critically evaluate the implicit assumptions underlying their fuzzing efforts. Is the fuzzer truly exploring the relevant input space? Is code coverage an adequate metric for the program's complexity, especially if it's highly stateful? Don't blindly trust the fuzzer; instead, understand why it finds what it finds, and what it might be missing.

1. Acknowledge and Address Statefulness: For programs with significant internal state (e.g., network protocols, APIs, GUIs, compilers, databases), traditional code coverage-guided fuzzing is profoundly limited. Defenders must consider alternative guidance mechanisms that capture state transitions or specific program states. This might involve instrumenting the program to report state changes, designing custom mutators that understand state semantics, or exploring techniques beyond simple code coverage.

1. Beware the Havoc Effect: Recognize that basic byte-level or bit-level mutations can have non-local, destructive effects on inputs, particularly when parts of the input re-interpret later segments. This means the fuzzer's "local search" might be an illusion. To mitigate this, consider structure-aware fuzzing or grammar-based fuzzing that understands the input format and applies mutations in a way that maintains structural validity or semantic consistency where possible. This is particularly relevant for complex file formats or network protocols.

1. Overcome Local Optima with Diverse Strategies: Since fuzzers can get stuck in local optima, relying on a single fuzzer configuration or strategy is insufficient. Defenders should experiment with diverse fuzzer types, mutation strategies, and even intermittent restarts. More importantly, they should invest in better guidance mechanisms that go beyond simple novelty search, perhaps incorporating domain-specific knowledge or state-tracking to encourage exploration of truly novel program behaviors rather than just new code lines.

1. Embrace Input Projection and Transformation: This is perhaps the most impactful defensive implication. Defenders should actively explore different ways to represent and provide inputs to their target programs. Instead of only fuzzing a program's lowest-level input interface (e.g., raw bytes from a file), consider fuzzing through its higher-level APIs, programmatic interfaces, or intermediate representations. As seen with LibXML2, this input projection can unlock entirely new bug classes by aligning the fuzzer's interaction with the program's internal logic. This requires a deeper understanding of the program's architecture and how it processes various forms of input. Harness generation should consider these projections.

1. Adopt an Empirical Testing Mindset: Finally, Addison urges a return to the scientific method in security testing. Instead of aiming to "prove" a tool is good or that a program is secure, the goal should be to "disprove" our understanding – to find the limits of our knowledge and the weaknesses in our assumptions. This means documenting hypotheses, carefully designing experiments, and rigorously analyzing results, always seeking to falsify current beliefs rather than confirm them. This approach fosters a continuous learning cycle and a more robust security posture.

Key Takeaways

• Fuzzing is not a magic solution; its behavior is poorly understood. We lack a comprehensive model for how inputs, mutations, and program guidance interact, leading to an incomplete understanding of fuzzer limitations and bug distributions.
• Statefulness is a major blind spot for traditional fuzzers. Code coverage-guided fuzzing is largely ineffective for highly stateful programs, as it fails to capture the nuances of internal program state changes, leading to inefficient exploration.
• The "havoc effect" undermines local search assumptions. Small mutations, especially early in an input sequence, can cause drastic and destructive changes to later input interpretation, making fuzzer exploration less local and predictable than commonly assumed.
• Fuzzers frequently get stuck in local optima. Current guidance and novelty search mechanisms often fail to thoroughly explore programs, missing valuable paths and alternative ways to trigger bugs, highlighting the need for more sophisticated guidance.
• Input representation (projection) is critical for effectiveness. Changing how inputs are provided to a program (e.g., programmatic API vs. raw data) can drastically realign program partitions and bug discovery, revealing new vulnerabilities even in heavily tested software.
• Security research needs greater scientific rigor and a shift in focus. Researchers and practitioners must move away from objective-oriented metrics (KPIs) towards a deeper, empirical understanding of fuzzer-program interaction, actively seeking to falsify assumptions rather than just achieve incremental coverage gains.

About the Speaker(s)

Addison is a PhD student who brings a unique perspective to security research, deeply rooted in a passion for education and scientific rigor. Before pursuing his PhD, Addison worked as a teacher, a role he cherishes and believes is incredibly important. This background informs his approach to disseminating complex technical information, striving to make it accessible and understandable. He is a vocal advocate for critical thinking in science, particularly concerned with the trend of objective-oriented research that prioritizes key performance indicators (KPIs) over a true understanding of the underlying phenomena. Addison is dedicated to fostering an environment where scientific inquiry focuses on genuine discovery and rigorous validation, aiming to push the security community towards a more profound comprehension of its tools and methodologies.