State-Aware Greybox Fuzzing

70 concepts42 papers1 proposal

Imagine an automated testing tool trying to find a security vulnerability deep inside a network protocol, a smart contract, or a device driver. Traditional coverage-guided greybox fuzzers excel at this task by throwing randomized inputs at a program and tracking which code branches are executed. If an input uncovers a new branch, the fuzzer saves it as a "seed" and mutates it further.

However, this strategy hits a wall when dealing with stateful systems. In these applications, the software's behavior is dictated not just by the current input, but by the history of all preceding inputs. If a fuzzer sends a message out of order—such as trying to read a file before authenticating—the program will immediately reject it. As Ma et al. observe in their work on protocol testing, Test data generation for stateful network protocol fuzzing using a rule-based state machine, these shallow state checks act as a shield, preventing traditional fuzzers from ever reaching deep program logic.

To bypass this shield, a new paradigm has emerged: state-aware fuzzing. By tracking and navigating a program's internal state space alongside its code execution paths, these tools can systematically drive complex systems into deep, vulnerable configurations.

The Illusion of Code Coverage

Why does traditional coverage-guided fuzzing fail on stateful software? The core issue is that standard code coverage metrics are decoupled from state-dependent logic.

Zhao et al., the authors of StateFuzz: System Call-Based State-Aware Linux Driver Fuzzing, point out that standard fuzzers prioritize discovering new code paths while discarding inputs that do not increase branch coverage. This is a fatal flaw for stateful testing: an input might not execute any new lines of code, but it might modify an internal variable that is essential for reaching a deep state later.

Furthermore, high branch coverage does not guarantee thorough exploration. As Ba et al. explain in Stateful Greybox Fuzzing, and Meng et al. reinforce in AFLNet Five Years Later: On Coverage-Guided Protocol Fuzzing, a fuzzer can execute every single line of code inside individual message handlers without ever triggering the specific sequence of state transitions necessary to expose deep-seated vulnerabilities. The exact same line of code might behave perfectly safely when the system is in an unauthenticated state, but trigger a critical crash when executed after an encryption key has been loaded.

Tracking the Hidden Dimension

State-aware fuzzing solves this problem by making the program's internal state space visible to the testing engine. Instead of viewing the target as a flat graph of basic blocks, the fuzzer constructs a dynamic map—a Finite State Machine (FSM) or State Transition Tree (STT)—of the application's behavior.

Fuzzers extract this state information using two primary strategies:

  1. External Indicators: Tools can infer states by observing how the application responds to inputs. For example, Meng et al. utilize server response codes to dynamically map out protocol state machines during execution.
  2. Internal State Variables: Fuzzers can look directly inside the program's memory. Zhao et al. and Ba et al. identify and track "state variables" (such as enum types or status flags) within the source code.

As Wang et al. demonstrate in SyzTrust: State-aware Fuzzing on Trusted OS Designed for IoT Devices, tracking variables like authentication status or key loading prevents the fuzzer from being blind to the underlying logical conditions that dictate whether an operation is valid.

Traditional Fuzzer:  [Input A] ──> Code Path X (Discarded if Path X was already seen)

State-Aware Fuzzer:  [Input A] ──> Code Path X + Internal State 2 (Saved as a valuable transition!)

Alternatively, this state machine can be reverse-engineered before fuzzing even begins. Shi et al. show in Extracting Protocol Format as State Machine via Controlled Static Loop Analysis that seeding fuzzers with state machines extracted via static analysis can increase code coverage by over 200%, allowing the tool to immediately target rarely used protocol features that dynamic exploration struggles to find.

The Composite Feedback Loop

Once the state space is mapped, how does the fuzzer use it to find bugs? The breakthrough lies in a composite feedback mechanism.

Instead of evaluating an input's worth solely on whether it hits a new code branch, a state-aware fuzzer rewards inputs that discover either a new code path or a new internal logical state or transition. Wang et al. and Meng et al. demonstrate that this dual-feedback loop allows the fuzzer to maintain a diverse corpus of seeds that keep the system in deep, hard-to-reach states.

Once the fuzzer knows how to reliably hold the system in a deep state, it can perform surgical mutations. As Amusuo et al. show in Systematically Detecting Packet Validation Vulnerabilities in Embedded Network Stacks, driving a network stack into precise states (like connection termination or specific handshake stages) before injecting malformed data is highly effective at uncovering zero-day defects that randomized fuzzers miss.

Taking this concept further, Chen et al. introduce a state-distance metric in Vulseye: Detect Smart Contract Vulnerabilities via Stateful Directed Graybox Fuzzing. By integrating state variable constraints directly into the fuzzer's fitness function, they actively steer the mutation engine toward the narrow, specific state configurations required to trigger deep exploits.

Finding a deep state is only half the battle; the fuzzer must also generate a valid chain of operations to get there. In stateful systems, inputs cannot be generated in isolation; they must be structured as a sequence where each step satisfies the prerequisites of the next.

Cho et al. demonstrate in MACE: Model-inference-Assisted Concolic Exploration for Protocol and Vulnerability Discovery that navigating through an inferred state model allows automated tools to explore logic buried ten or more messages deep, far surpassing the shallow search depth limits of traditional concolic execution.

To build these long request sequences without triggering early errors, fuzzers must respect data dependencies between operations. Yang et al. (Rethinking Smart Contract Fuzzing: Fuzzing With Invocation Ordering and Important Branch Revisiting) and Qian et al. (MuFuzz: Sequence-Aware Mutation and Seed Mask Guidance for Blockchain Smart Contract Fuzzing) solve this by analyzing Read-After-Write (RAW) data dependencies. This analysis ensures that functions which modify state variables are executed in the correct order before functions that read them are tested.

In the context of web services, Saurabh Sinha argues in Automated test generation for REST APIs: no time to rest yet that explicitly modeling these producer-consumer dependencies between API operations is essential. Without this awareness, automated tools rely on weak heuristics, generating invalid test sequences that fail to penetrate the real-world logic of complex, multi-step stateful applications.

Key Foundational Work

MACE: Model-inference-Assisted Concolic Exploration for Protocol and Vulnerability Discovery (2011) — contributed 2 concept elements to this direction.
Test data generation for stateful network protocol fuzzing using a rule-based state machine (2016) — contributed 1 concept elements to this direction.
Generating test case chains for reactive systems (2016) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_state_dependent_vulnerability_discovery_fb09d440,
  title = {state-dependent vulnerability discovery},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/state-dependent-vulnerability-discovery/rdr_fb09d440268e4e56b1f8522460f79578},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_state_dependent_vulnerability_discovery_fb09d440_v1,
  title = {state-dependent vulnerability discovery},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/state-dependent-vulnerability-discovery/rdr_fb09d440268e4e56b1f8522460f79578/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake