Test data generation for stateful network protocol fuzzing using a rule-based state machine

Rui Ma, Daguang Wang, Changzhen Hu, Wendong Ji, Jingfeng XueTsinghua 2016 · DOI

Abstract

To improve the efficiency and coverage of stateful network protocol fuzzing, this paper proposes a new method, using a rule-based state machine and a stateful rule tree to guide the generation of fuzz testing data. The method first builds a rule-based state machine model as a formal description of the states of a network protocol. This removes safety paths, to cut down the scale of the state space. Then it uses a stateful rule tree to describe the relationship between states and messages, and then remove useless items from it. According to the message sequence obtained by the analysis of paths using the stateful rule tree and the protocol specification, an abstract data model of test case generation is defined. The fuzz testing data is produced by various generation algorithms through filling data in the fields of the data model. Using the rule-based state machine and the stateful rule tree, the quantity of test data can be reduced. Experimental results indicate that our method can discover the same vulnerabilities as traditional approaches, using less test data, while optimizing test data generation and improving test efficiency.

Introduction

Fuzzing is a critical technique in security testing, involving the delivery of malformed data to a target system to trigger crashes or unexpected behavior. However, stateful protocols—such as SIP, FTP, and BGP—present a significant challenge. In these protocols, the validity and impact of a message are contingent upon the prior sequence of events. Traditional "dumb" fuzzers often fail to account for these dependencies, resulting in a "state space explosion" where the majority of generated test cases are discarded by the target's initial logic, never reaching deeper, potentially vulnerable code paths.

Methodology

The proposed approach optimizes fuzzing by modeling protocol states and pruning irrelevant data through two primary structures: the Rule-Based State Machine (RSM) and the Stateful Rule Tree (SRT).

Rule-Based State Machine (RSM)

The RSM provides a formal description of the protocol's states. A key innovation in this method is the identification and removal of "safety paths"—sequences of messages that are known to be handled correctly by the protocol's standard logic. By pruning these paths, the fuzzer focuses exclusively on "danger zones" where transitions are complex or less thoroughly defined.

The Rule-Based State Machine (RSM) for the SIP INVITE transaction, illustrating the various states and transitions used to guide fuzzing.

Stateful Rule Tree (SRT)

To further refine the testing process, the authors introduce the Stateful Rule Tree (SRT). This hierarchical map links specific protocol states to valid message types, sub-messages, and headers. By breaking down messages into this tree structure, the fuzzer can prune irrelevant headers or sub-messages that do not apply to the current state, ensuring that every byte sent is contextually relevant.

The structure of a Stateful Rule Tree (SRT), showing the hierarchical relationship between states, messages, sub-messages, and headers.

Abstract Data Models

Using the paths defined by the SRT, the system generates templates for test cases. These templates are then populated with mutated data using standard fuzzing algorithms, creating a final test set that is both targeted and efficient.

Experimental Evaluation

The researchers implemented their method by extending the Sulley fuzzing framework to be state-aware. They evaluated the system using the Session Initiation Protocol (SIP), a complex stateful protocol common in VoIP applications. The target software was the officeSIP server 3.1, running in a Windows 7 environment.

Key Results

The rule-based method was compared against the standard Sulley fuzzer. Both approaches successfully identified CVE-2012-1008, a remote Denial-of-Service (DoS) vulnerability in the officeSIP server caused by malformed "To" headers.

However, the proposed method demonstrated superior efficiency:

  • Data Reduction: The optimized method generated 11,641 test cases, an 18.3% reduction compared to Sulley’s 14,247.
  • Time Savings: The test run was completed in 12 hours and 52 minutes, nearly 3 hours faster than the baseline of 15 hours and 31 minutes.

Conclusion

This research demonstrates that "smarter" fuzzing is achieved not just through better mutation, but through effective pruning of the search space. By leveraging protocol specifications to build RSMs and SRTs, security researchers can significantly reduce the volume of redundant test data while maintaining high effectiveness in vulnerability discovery. Future work will focus on automating the creation of these models from network traffic to reduce the reliance on manual protocol analysis.

Summary updated

Abstract

To improve the efficiency and coverage of stateful network protocol fuzzing, this paper proposes a new method, using a rule-based state machine and a stateful rule tree to guide the generation of fuzz testing data. The method first builds a rule-based state machine model as a formal description of the states of a network protocol. This removes safety paths, to cut down the scale of the state space. Then it uses a stateful rule tree to describe the relationship between states and messages, and then remove useless items from it. According to the message sequence obtained by the analysis of paths using the stateful rule tree and the protocol specification, an abstract data model of test case generation is defined. The fuzz testing data is produced by various generation algorithms through filling data in the fields of the data model. Using the rule-based state machine and the stateful rule tree, the quantity of test data can be reduced. Experimental results indicate that our method can discover the same vulnerabilities as traditional approaches, using less test data, while optimizing test data generation and improving test efficiency.
BibTeX
@inproceedings{ma2016test,
  author = {Rui Ma and Daguang Wang and Changzhen Hu and Wendong Ji and Jingfeng Xue},
  title = {{Test data generation for stateful network protocol fuzzing using a rule-based state machine}},
  booktitle = {Tsinghua},
  year = {2016},
  doi = {10.1109/tst.2016.7488746},
}
Figure