PaperlayerView exact revision on arXiv

Source-linked AI summary

Stateful Greybox Fuzzing

Jinsheng Ba, Marcel Böhme, Zahra Mirzamomen, Abhik Roychoudhury

arXiv:2204.02545v3cs.CRcs.SE

TL;DR

Protocol fuzzers need to discover sequences that reach state-dependent bugs, often without a formal protocol specification. SGFUZZ identifies enum-based state variables and tracks their value sequences to guide exploration. It discovers stateful bugs about twice as fast as LIBFUZZER.

  • Problem

    Protocol bugs may require a particular sequence of messages to reach the relevant state, while conventional coverage-guided fuzzers do not effectively track the state space.

    Source: §1 · p. 1

  • Method

    SGFUZZ identifies enum variables assigned named constants, records their value sequences in a state transition tree, and uses that tree to steer inputs toward under-explored states.

    Source: §1 · p. 2

  • Results

    SGFUZZ discovered stateful bugs about twice as fast as LIBFUZZER, the baseline greybox fuzzer into which it was implemented.

    Source: §8 · p. 14

  • Takeaways & Limitations

    State-transition feedback captures distinctions that code coverage alone misses, such as whether a sequence reaches state-dependent code.

    Source: §1 · p. 2, §2.3 · p. 3

    The state transition tree tracks explicit states, not implicit states such as accumulated database or filesystem changes that survive connection resets.

    Source: §3.4 · p. 6

Abstract

from arXiv · show

Many protocol implementations are reactive systems, where the protocol process is in continuous interaction with other processes and the environment. If a bug can be exposed only in a certain state, a fuzzer needs to provide a specific sequence of events as inputs that would take protocol into this state before the bug is manifested. We call these bugs as "stateful" bugs. Usually, when we are testing a protocol implementation, we do not have a detailed formal specification of the protocol to rely upon. Without knowledge of the protocol, it is inherently difficult for a fuzzer to discover such stateful bugs. A key challenge then is to cover the state space without an explicit specification of the protocol. In this work, we posit that manual annotations for state identification can be avoided for stateful protocol fuzzing. Specifically, we rely on a programmatic intuition that the state variables used in protocol implementations often appear in enum type variables whose values (the state names) come from named constants. In our analysis of the Top-50 most widely used open-source protocol implementations, we found that every implementation uses state variables that are assigned named constants (with easy to comprehend names such as INIT, READY) to represent the current state. In this work, we propose to automatically identify such state variables and track the sequence of values assigned to them during fuzzing to produce a "map" of the explored state space. Our experiments confirm that our stateful fuzzer discovers stateful bugs twice as fast as the baseline greybox fuzzer that we extended. Starting from the initial state, our fuzzer exercises one order of magnitude more state/transition sequences and covers code two times faster than the baseline fuzzer. Several zero-day bugs in prominent protocol implementations were found by our fuzzer, and 8 CVEs have been assigned.

1 Introduction

Protocol fuzzers must discover input sequences that reach state-dependent behavior without relying on a formal specification. This section motivates SGFUZZ’s state-transition tracking approach and describes its evaluation against existing fuzzers.

1 Introduction

  • Protocol bugs can require a particular sequence of messages to reach a target state, but conventional coverage-guided fuzzers do not track the state space traversed.In the HTTP2 example, sending DATA before HEADER can cover both handlers without reaching the state needed to process the DATA frame correctly.Source: §1 · pp. 1–2
  • The introduction frames the challenge as exploring an unknown state space without protocol specifications or human annotations.It presents automated state identification and SGFUZZ’s evaluation as the paper’s contributions.Source: §1 · p. 2
  • SGFUZZ identifies enum variables assigned named constants, records their assigned-value sequences in a shared state transition tree, and steers inputs toward under-explored states.The authors report that this named-constant pattern held across the top 50 widely used protocol implementations and every stateful protocol in ProFuzzbench.Source: §1 · p. 2
  • SGFUZZ covers 33x more state-transition sequences than LIBFUZZER, 15x more than IJON, and 260x more than AFLNET; it reaches the same branch coverage more than 2x faster than LIBFUZZER.It also exposes stateful bugs about twice as fast as LIBFUZZER and IJON, more than 155x faster than AFLNET, and found 12 new bugs, 8 assigned CVEs.Source: §1 · p. 2

2.1 The HTTP2 Protocol

  • The HTTP2 specification regulates frame processing through stream states, including idle, open, half-closed, and closed states.Headers open a stream, while END_STREAM and reset frames can move it toward closure.Source: §2.1 · p. 3

2.2 The H2O Implementation

  • H2O implements a finer-grained HTTP2 stream state machine using an enumerated state variable, with states for receiving requests and sending responses.Its eight states include an intermediate pending-request state and a state for a client-ended stream with server frames still pending.Source: §2.2 · p. 3

2.3 Challenges of Fuzzing Stateful Software

  • In H2O, code that handles a request-body chunk is reachable only when a valid header frame first sets the stream state to RECV_BODY.Coverage can include both handlers regardless of frame order, but only header-before-data reaches the state-dependent code; adding sequences that reach new tree nodes distinguishes these cases.Source: §2.3 · pp. 3–4

3 Methodology

The methodology automatically identifies enum-based state variables and records their observed value sequences in a State Transition Tree (STT), which guides exploration without protocol specifications. It also distinguishes explicit states from implicit state changes that can persist across connection resets.

3 Methodology

  • The STT guides SGFUZZ’s exploration by incrementally recording observed state transitions during fuzzing.The tree is built from state-variable values and represents explored state-transition sequences.Source: §3 · p. 4, §3.2 · p. 5

3.1 Offline State Variable Identification

  • Regular-expression matching identifies enum variables assigned named constants automatically, though some enums represent response codes or configuration rather than protocol states.The authors report that all 50 widely used implementations examined use named constants for state variables; 44 use enums and six use #define statements.Source: §3.1 · p. 4

3.2 State Transition Tree Data Structure

  • Each STT node represents a state-variable value, and each root-to-leaf path records a unique state-transition sequence.Merging nodes with identical enum values yields a compact graph that can recover parts of the official state machine while retaining finer-grained implementation states.Source: §3.2 · p. 5

3.3 State Transition Tree Construction

  • Compile-time instrumentation injects calls before state-variable assignments, and the runtime uses them to extend the STT as inputs execute.The runtime resets its last-visited-node pointer to the root after each input and can limit repeated states along a path.Source: §3.3 · pp. 5–6

3.4 Handling Implicit States

  • The STT tracks explicit states, but not implicit changes such as database or filesystem updates and memory that is allocated but never freed.The authors let implicit states accumulate without reset to explore bugs involving those persistent changes.Source: §3.4 · p. 6

4 Stateful Greybox Fuzzing Algorithm

SGFUZZ uses the STT to guide corpus selection and mutation, adding inputs that expand state coverage and prioritizing promising seeds and bytes. Its energy schedule favors rare states and mutations that change STT paths.

4 Stateful Greybox Fuzzing Algorithm

  • SGFUZZ repeatedly selects and mutates corpus seeds, adds inputs that reveal new code branches or STT nodes, and updates seed energy when new nodes appear.The algorithm returns a crashing input when execution crashes.Source: §4 · pp. 6–7

4.1 State Coverage Feedback

  • Inputs that exercise new STT nodes are added to the corpus to increase state-space coverage.Each new node represents a new value in the current sequence of state-variable values.Source: §4.1 · p. 7

4.2 Energy Schedule

  • Seed energy increases for paths through below-average-hit STT nodes and for seeds whose mutations take different STT paths, with energy capped at 10 times the original.The schedule also favors valid state transitions and uses the inverse proportion of mutated offspring that follow the same path.Source: §4.2 · p. 7

4.3 Fuzzing Individual Bytes

  • SGFUZZ prioritizes mutating bytes associated with newly reached STT nodes, then gradually expands the mutation range if those mutations are uninteresting.The byte ranges are identified from differences between an input and its mutated version that reaches new nodes.Source: §4.3 · pp. 7–8

5 Experimental Setup

The experiments assess state-transition and branch coverage, state-variable identification, bug-finding speed, and newly found bugs. They compare SGFUZZ with other fuzzers on selected protocol implementations using matched fuzzing setups.

5.1 Research Questions

  • The research questions assess state-transition coverage, branch coverage, state identification, bug-finding speed, and discovery of previously unknown bugs.Source: §5.1 · p. 8

5.2 Subject Programs Studied

  • The study selected eight real-world targets spanning distinct, widely used protocols and security-critical applications, subject to in-memory fuzzer compatibility.The targets implement more than 30 protocols; netdriver incompatibility with UDP and fork limited eligible ProFuzzBench programs.Source: §5.2 · p. 8

5.3 Fuzzers

  • SGFUZZ is compared with LIBFUZZER as its baseline and with AFLNET and IJON as stateful-fuzzer comparators.All fuzzers receive equivalent setups, environments, seeds, and resources.Source: §5.3 · pp. 8–9

5.4 Experimental Infrastructure

  • 20 repeated 23-hour campaigns used matched environments, seeds, and resources; Table 3 reports average state-transition coverage and the SGFUZZ-to-LIBFUZZER improvement factor.Source: §5.4 · p. 9, §5.3 · p. 9, Table 3 · p. 9

RQ.1 State Transition Coverage

SGFUZZ explores substantially more state-transition sequences than the compared fuzzers, although its gains are smaller in implementations with relatively few reachable sequences or difficult state conditions.

RQ.1 State Transition Coverage

  • Across campaigns, state-transition coverage counts unique paths in the STT, each representing a sequence of state transitions during one input's execution.The table reports average sequence counts over 20 campaigns of 23 hours and gives the percentage of all distinct sequences exercised.Source: RQ.1 State Transition Coverage · p. 9
  • SGFUZZ exercises 34x more state transitions on average and 20x more at the median than LIBFUZZER across eight subjects.The comparison attributes the gains to the STT-guided approach.Source: RQ.1 State Transition Coverage · p. 10
  • SGFUZZ covers 15.29x more state transitions than IJON, while IJON covers 2.75x more than LIBFUZZER on average.SGFUZZ covers 92% of the transition sequences exercised in any run by any fuzzer, on average.Source: RQ.1 State Transition Coverage · p. 10
  • LIBFUZZER performs well on OpenSSL, where only 39 distinct state-transition sequences exist, but mostly explores states near the initial or end states.The reported gains are smaller for OpenSSL and MbedTLS, where reaching some states requires additional conditions or external state such as UDP traffic.Source: RQ.1 State Transition Coverage · p. 10

RQ.2 Branch Coverage

SGFUZZ improves average branch coverage and reaches LIBFUZZER’s coverage sooner, while transition-aware feedback helps distinguish inputs that branch coverage alone treats alike. Gstreamer is an exception where a large, frequently changing state space adds exploration cost without a comparable branch-coverage gain.

RQ.2 Branch Coverage

  • Gstreamer's frequently updated best_probability variable has 100 states, increasing SGFUZZ's state exploration without much additional branch coverage.After removing that variable, the authors report improved coverage; LIBFUZZER took 23 hours to reach about the coverage SGFUZZ reached in 12 hours.Source: RQ.2 Branch Coverage · p. 10
  • SGFUZZ achieves 2.20% more branch coverage than LIBFUZZER, 4.41% more than IJON, and 38.73% more than AFLNET on average.It achieves the same branch coverage 2.3x faster than LIBFUZZER on average.Source: RQ.2 Branch Coverage · p. 10, Table 4 · p. 11
  • The transition-coverage increase exceeds the branch-coverage increase, supporting the authors' view that branch feedback is insufficient to measure state-space coverage.State-dependent code may be reached faster by SGFUZZ or reached by SGFUZZ but not by LIBFUZZER within 23 hours.Source: RQ.2 Branch Coverage · p. 11
  • Function sequences 1-2-3 and 3-1-2 can have identical branch coverage but different state values, so SGFUZZ retains both seeds for further exploration.LIBFUZZER may miss a later function reachable more easily from one sequence; SGFUZZ explored it faster or LIBFUZZER did not reach it within 23 hours.Source: RQ.2 Branch Coverage · p. 11

RQ.3 State Identification Effectiveness

The enum-based heuristic includes false positives, but most nodes in the resulting STT correspond to actual state-variable values. The evaluation also finds a false negative where protocol states are implicit rather than explicitly represented by a state variable.

RQ.3 State Identification Effectiveness

  • 99.5% of STT nodes correspond to actual state-variable values, despite 32% of identified variables not being state variables.Non-state variables tend to appear only once or at execution start, so they rarely enter the growing STT and have low impact on the algorithm or branch coverage.Source: RQ.3 State Identification Effectiveness · p. 12
  • On average, 68.44% of variables identified by the enum-based heuristic are actual state variables.The evaluation classifies variables using their data sources and their effect on execution through if- or switch-statements.Source: RQ.3 State Identification Effectiveness · pp. 11–12
  • The one reported false negative is Live555's RTSP state machine, which is implied by transport or parser variables rather than an explicit state variable.The authors count this case as a false positive because no explicit state variable represents the protocol state machine.Source: RQ.3 State Identification Effectiveness · p. 12
  • SGFUZZ covers 88.98% more distinct values of true state variables than LIBFUZZER in 23 hours.The evaluation counts distinct values for variables known to represent states.Source: RQ.3 State Identification Effectiveness · p. 12, Table 6 · p. 12
  • Some protocol states require specific inputs or external environment conditions, though SGFUZZ still outperforms the other fuzzers in state coverage.For example, OpenSSL's state transitions can depend on whether traffic arrives over UDP rather than TCP.Source: RQ.3 State Identification Effectiveness · p. 12

RQ.4 Bug Finding Effectiveness

SGFUZZ exposes the evaluated stateful bugs about twice as fast as LIBFUZZER and IJON, and much faster than AFLNET. It also shows a slight advantage on the evaluated stateless bugs.

RQ.4 Bug Finding Effectiveness

  • The evaluation selected seven stateful bugs requiring at least two state transitions and three stateless bugs executable without any state transition.The known stateful bugs were originally found by LIBFUZZER because they required few state transitions.Source: RQ.4 Bug Finding Effectiveness · pp. 12–13
  • For the evaluated stateless bugs, SGFUZZ shows a slight advantage over LIBFUZZER and IJON.The bugs were generally in functions that execute alongside, but do not depend on, state transitions, such as message parsing.Source: RQ.4 Bug Finding Effectiveness · p. 13
  • SGFUZZ exposes stateful bugs about 2x as fast as LIBFUZZER and IJON, and about 155x faster than AFLNET.For the OpenSSL bug, LIBFUZZER did not trigger it in 23 hours, while IJON and SGFUZZ triggered it in 6 and 10 of 20 campaigns, respectively.Source: RQ.4 Bug Finding Effectiveness · p. 13

RQ.5 New Bugs Found

SGFUZZ found 12 new bugs, 10 of them stateful, and received eight CVE IDs. A Live555 case study shows how a repeated parser state after a sequence of RTSP commands exposed an assertion failure.

RQ.5 New Bugs Found

  • 12 new bugs were found, 10 stateful, and eight CVE IDs were received; all 12 could not be triggered by AFLNET in 23 hours.Two stateful bugs involving implicit states and one stateless bug could also be triggered by LIBFUZZER; IJON exposed two additional bugs with SGFUZZ’s identified state variables.Source: RQ.5 New Bugs Found · p. 13
  • The Live555 bug required RTSP states INIT→READY→PLAY→READY→PLAY and a repeated MPEG parser transition from PARSING_PACK_HEADER to itself.The parser failed to reset the number of bytes read, so the second media-file-header parse was incorrect and triggered an assertion error.Source: RQ.5 New Bugs Found · p. 13

7 Related Work

Prior protocol-fuzzing approaches infer state machines, use symbolic execution, or guide greybox fuzzing with annotations, invariants, or response codes. SGFUZZ instead derives a state-transition tree from execution traces, and the discussion reports faster bug discovery and coverage than LIBFUZZER.

7 Related Work

  • Unlike passive or active state-machine learning, SGFUZZ builds its state-transition tree from execution traces without analyzing protocol messages or using learning algorithms.Passive learning analyzes observed traffic and cannot learn protocols communicated over encrypted channels; active approaches query implementations with generated sequences.Source: §7 · p. 13
  • Blackbox fuzzers generate message sequences without internal program information, while whitebox methods such as MACE use symbolic execution and face scalability issues.Existing greybox methods use annotations, likely invariants, response codes, or manually specified fork points; SGFUZZ uses state variables without requiring protocol-state-machine knowledge.Source: §7 · p. 14

8 Discussion

  • SGFUZZ discovered stateful bugs about twice as fast as LIBFUZZER, covered 33x more state-transition sequences than LIBFUZZER, 15x more than IJON, and 260x more than AFLNET, and reached the same branch coverage about 2x faster than LIBFUZZER.The paper also reports 12 new bugs and says SGFUZZ was released open source.Source: §8 · p. 14

A Appendix

The appendix evaluates SGFUZZ configurations, branch-coverage growth, and the prevalence and triggers of stateful bugs. Its findings include substantial gains in state-transition coverage and a high proportion of stateful bugs among OSS-Fuzz reports.

A.1 Sensitivity Analysis

  • 4.43x, 21.95x, and 33.92x were the average state-transition coverage increases over LIBFUZZER for SGFUZZx, SGFUZZy, and SGFUZZ, respectively.The experiments used 23 hours and 20 runs; HONGGFUZZ, like LIBFUZZER, had little state-transition coverage, and SGFUZZx slightly outperformed IJON.Source: §A.1 · p. 16, Table 9 · p. 16

Subject HONGGFUZZ LIBFUZZER SGFUZZx SGFUZZy SGFUZZ

  • SGFUZZx slightly underperformed LIBFUZZER in branch coverage, while SGFUZZy and SGFUZZ overcame the state-tracing cost; for Gstreamer, SGFUZZy did better than SGFUZZ.HONGGFUZZ excelled on H2O, Curl, and OpenSSL but performed poorly on MbedTLS and OwnTone; Table 10 reports average branch coverage and time to match LIBFUZZER’s 23-hour coverage.Source: Subject HONGGFUZZ LIBFUZZER SGFUZZx… · p. 16, Table 10 · p. 16

A.2 Growth Trend of Branch Coverage

  • Branch coverage for all fuzzers nearly saturated after 12 hours, despite substantial variation in state-transition coverage.On OwnTone, AFLNET processed fewer than 10 inputs per second, compared with more than 1000 for SGFUZZ, and consequently achieved much less branch coverage.Source: §A.2 · pp. 16–17, Figure 5 · p. 17

A.3 Prevalence of Stateful Bugs

  • 57 of 73 OSS-Fuzz bugs, or 78.08%, were classified as stateful because their crash location followed at least one state transition.The appendix summarizes this prevalence as roughly four in five bugs among the studied protocol implementations.Source: §A.3 · p. 17, Table 11 · p. 17
  • All six stateful H2O bugs followed specific stream-state transitions, including bugs triggered by assigning priority to a closed stream or sending a trailing header to one.The latter cases involved END_STREAM; the three stateless H2O bugs occurred before request processing, without state transitions.Source: §A.3 · p. 17
  • Existing fuzzers found H2O stateful bugs only at the END_STREAM endpoint, whereas the appendix reports that stateful bugs outnumbered stateless bugs even with limited state-space exploration.The authors use this observation as evidence that stateful bugs are prevalent in protocol implementations.Source: §A.3 · p. 18

A.4 Top-50 most widely used open-source protocol implementations.

A review of 50 widely used open-source protocol implementations found named constants in every implementation’s state representation. Forty-four used enum-type state variables.

A.4 Top-50 most widely used open-source protocol implementations.

  • All 50 reviewed subjects represented states with named constants, and 44 used enum-type variables.The review examined state variables whose values affect execution through if or switch statements; examples included both protocol and customized states.Source: §A.4 · p. 18, Table 12 · p. 18
  • OpenSSL defines 50 partially ordered handshake-state values; the server moves from TLS_ST_BEFORE through message-specific states after receiving HELLO.The described progression ends at TLS_ST_SW_SRVR_DONE.Source: §A.4 · p. 18
Loading 2204.02545v3…