StateAFL: Greybox fuzzing for stateful network servers

According to recent statistics (Hawkes 2019; O’Neill 2021), high-severity software vulnerabilities of network servers have been on the rise, and will likely still be in the near future. Network servers are a critical part of the attack surface of IT infrastructures, as they are openly exposed to malicious users over local networks and the Internet, and can be attacked with malformed traffic to cause a denial-of-service (e.g., crashing the server), and to execute arbitrary code on the server machine to perpetrate further attacks. For this reason, any vulnerability not yet found by developers (0-days) has a significant economic value for attackers (Guo et al. 2021).

Fuzzing is a relevant security testing technique to identify such vulnerabilities, by automatically generating large volumes of malformed inputs. However, fuzzing network servers is still a technical challenge, since the input space of network servers is strictly regulated by a stateful protocol. Therefore, the behavior of the server, and its vulnerabilities, depend on a sequence of several messages exchanged over time, which determine the state of the server. Examples of well-know stateful protocols include cryptographic ones such as TLS (De Ruiter and Poll 2015; Fiterau-Brostean et al. 2020), file transfer and messaging protocols such as FTP, SMB, and SMTP (Antunes and Neves 2011; Comparetti et al. 2009), and multimedia protocols such as SIP (Banks et al. 2006; Alrahem et al. 2007) and RSTP (Pham et al. 2020). All of these protocols are selective with respect to which messages they can receive at a given time, and which actions they can perform, depending on previous messages in a session.

The existing stateful protocol fuzzing techniques and tools can only be applied with a significant effort, which has prevented their widespread adoption so far: generation-based fuzzers require formal specifications manually written by human experts, based on their detailed knowledge of the protocols (Beyond Security 2020; Synopsis Inc 2020; Rapid7 2020); learning-based fuzzers infer the protocol state machine at a significant computational cost, and still require custom implementations of wrappers to abstract protocol messages in efficient ways (De Ruiter and Poll 2015; Fiterau-Brostean et al. 2020).

Coverage-driven fuzzing techniques have recently emerged as a popular solution, as demonstrated by the widespread adoption of the AFL fuzzer and similar tools (Zalewski 2021; Metzman et al. 2021; Manès et al. 2019; Boehme et al. 2021). For example, as of June 2021, OSS-Fuzz has found over 30,000 bugs in 500 open source projects (Google 2021; Serebryany 2017), with more and more open-source projects being integrated by the community (Korczynski and Korczynski 2021). This success could only be possible thanks to its fully-automated approach, which is based on unsupervised evolution of fuzz inputs, using simple and robust heuristics. However, research on coverage-driven fuzzing for stateful protocols is still at an early stage (Pham et al. 2020; Feng et al. 2021). These recent approaches infer protocol states by analyzing the contents of messages (e.g., status codes), using message parsers that are specifically developed for the protocol under test. Moreover, it is difficult for these approaches to fuzz many protocols, which only embed little or no state information within messages. These problems are a limiting factor towards securing more stateful network servers through fuzzing.

In this work, we propose a new solution for stateful coverage-driven fuzzing (StateAFL). Similarly to coverage-driven fuzzing, we inject code in the target binary using compile-time instrumentation techniques. The injected code infers protocol state information by: tracking memory allocations and network I/O operations; at each request-reply exchange, taking snapshots of long-lived memory areas; and applying fuzzy hashing (Locality-Sensitive Hashing, LSH) to map each in-memory state to a unique protocol state identifier. This approach does not rely on state information from network messages, and does not require developers to implement custom message parsers for extracting such state information. The aim of this approach is to contribute towards a completely-automated solution for stateful protocol fuzzing, similarly to what AFL was able to achieve for stateless programs, in order to promote a wider application of fuzzing in real-world systems. We note that fuzzing research achieved significant progress from the point of view of fuzzing algorithms, but we are still witnessing at critical vulnerabilities (e.g., the well-known case of Hearthbleed (Wheeler 2020)) that in hindsight could have been easily prevented with fuzzing. Moreover, empirical research also showed that fuzzing a new system for the first time is likely to find security bugs (Böhme and Falk 2020). For these reasons, it is now a priority to make fuzzing more broadly applicable, as it is still too difficult to setup fuzzing to target new systems. In the case of stateful network fuzzing, StateAFL overcomes the issues of writing custom parsers to extract individual requests from seed inputs, and to extract status codes from response messages from the target server. These issues make fuzzing less accessible for developers that are new to this technique, since they are not inclined to write more code to use a fuzzing tool unfamiliar to them. Moreover, StateAFL is even applicable for protocols that do not provide any explicit status code in the messages, such as in the TLS protocol in our experiments, or where the status code only represents the status of the last request executed by the server instead of the protocol state, as in FTP and HTTP.

To assess the feasibility of the approach, we implemented and publicly released StateAFL as open-source software. Moreover, to support reproducible experimentation, we integrated StateAFL with a publicly-available benchmark of 13 open-source network servers, the largest experimental setup among stateful network fuzzing studies to the best of our knowledge. Our proposed approach allowed us to integrate StateAFL with no manual customization of the fuzzer to accomodate for the protocols under test. The experimental evaluation shows that StateAFL is a robust approach that can be applied to diverse network servers without requiring any protocol customization. Moreover, StateAFL can achieve comparable, or even better code coverage and bug detection than previous solutions based on stateless coverage-driven fuzzing and on stateful, protocol-customized fuzzing. We also qualitatively analyze state information both from parsing response codes returned by the target server, and from inference based on long-lived data. We found that using response codes provides misleading representation of the protocol state, leading to redundant states in the inferred protocol state machine and wasted fuzz inputs.

In summary, this paper presents the following contributions:

The paper is structured as follows. Section 2 discusses related work on stateful fuzzing. Section 3 presents the design and implementation of StateAFL. Section 4 presents the experimental plan, and Section 5 presents the experimental results. Section 6 concludes the paper.

Generation-based fuzzers address stateful protocols by generating fuzz inputs using a model of the protocol, to be provided by a human analyst (Beyond Security 2020; Synopsis Inc 2020; Rapid7 2020). The model specifies both the format of protocol messages (e.g., field types, message separators, etc.) and their sequencing over a session (Poll et al. 2015), typically in the form of a graph, such as finite state machines, prefix acceptor trees, and Markov chains. The completeness of the model is critical for the effectiveness of fuzzing, but it can be difficult to achieve, since protocol specifications (which are typically written in natural language) are prone to misinterpretations and costly to analyze, and do not cover proprietary protocol extensions (Antunes and Neves 2011).

Several model learning techniques have been proposed to compensate for these issues, by (semi-)automatically inferring the types and formats of messages, and protocol state machines. Passive learning techniques infer from a corpus of network traces, using sequence alignment techniques (e.g., the Needleman-Wunsch algorithm) and statistical techniques (e.g., clustering into message types, and correlation of message fields) (Duchene et al. 2018; Kleber et al. 2018). Active learning techniques interact with the protocol server during the learning process, in order to refine the model and to elicit new protocol behaviors (e.g., based on Angluin’s L ∗ algorithm and derivates) (De Ruiter and Poll 2015; Fiterau-Brostean et al. 2020). Both passive and active learning techniques provide valuable support for the human analyst, but cannot fully automate the process. For example, active learning can suffer from convergence issues and are applicable to finite input alphabets of modest size; thus, it needs an ad-hoc mapper to abstract protocol messages from/to the learner, to be tailored for the system-under-test (e.g., TLS-Attacker for the TLS protocol) (Somorovsky 2016). More powerful solutions leverage static and dynamic binary analysis (e.g., taint propagation analysis) to achieve full automation (Comparetti et al. 2009; Caballero et al. 2007), but in practice these solutions are difficult to implement and to port across different systems, which limits their adoption (Harman and O’Hearn 2018).

Coverage-driven fuzzing techniques have been adopted by AFL, libFuzzer, and other derivative tools (Manès et al. 2019) as a more practical and automated solution. This form of fuzzing only relies on lightweight metrics collected from the target system at run-time (e.g., about code blocks and branches covered by the fuzz inputs), and iteratively mutates the fuzz inputs to maximize these metrics. Therefore, the fuzzer can start from an initial set of fuzz inputs (i.e., a seed corpus) to automatically evolve them, without any a-priori knowledge about the protocol.

Only recently, coverage-driven fuzzing has been investigated for stateful protocols. AFLnet (Pham et al. 2020) extended AFL for fuzzing network protocols, by: structuring fuzz inputs into messages and applying mutation operators at message-level (e.g., by corrupting, dropping or injecting individual messages in a session); by learning a protocol state machine, where states are represented by response codes from the system-under-test; and by using the protocol state machine to prioritize mutations. Snipuzz (Feng et al. 2021) tailored coverage-driven fuzzing to IoT protocols, where the system-under-test could not be instrumented to collect coverage information, because of lack of access to the firmware. Thus, Snipuzz also analyzes response codes, using them as indicators to identify sensitive bytes of the inputs (snippets) that trigger different paths in the target.

This paper proposes a new approach for stateful protocol fuzzing. Our approach infers a protocol state machine on the basis on richer feedback than traditional coverage-driven fuzzing. The approach is not limited to analyze response codes, since response codes may provide a poor indication of the current state of the server. For example, in an HTTP-based protocol, successful GET and POST requests may both receive the same response code (200), but POST requests may have side-effects on the state of the server, which are not reflected in the response code. Moreover, the protocol may lack response codes, such as in the case of TLS, thus leaving the fuzzer without any guidance about the current protocol state. Finally, even when response codes available, the fuzzer must be tailored for the target protocol, in order to extract and parse response codes from the response messages. For these reasons, our approach does not rely on response codes, but adopts compile-time instrumentation to get more information from the system-under-test and to infer the current protocol state. Moreover, the proposed approach relieves the user from providing custom message parsers.

We designed StateAFL to drive fuzzing based on protocol states covered during executions. In general terms, a protocol state guides the behavior of a process, by defining which actions the process is allowed to take, which events it expects to happen, and how it will respond to those events (Holzmann and Lieberman 1991). For example, most Internet protocols standardize the protocol states and their transitions in Request for Comments (RFC) documents, by describing them using prose in natural language or, in few cases, using finite state machines. Covering protocol states is a prerequisite for deeper code coverage of a protocol implementation, as some of its parts are only executed when the protocol reaches specific states. Moreover, exploring the protocol state space can uncover unintended or spurious behaviors of the protocol implementation that deviate from the protocol specification (Poll et al. 2015).

The StateAFL approach is designed around the fundamental receive-process-reply loop implemented by network servers. In this scheme, two parties (e.g., a client and a server) establish a session, which consists of a series of request messages and their corresponding reply messages (Poll et al. 2015). As the session progresses, the current protocol state is updated accordingly. The fundamental loop can be summarized by the following simplified pseudo-code:

The key idea of StateAFL is to infer the current protocol state by inspecting the contents of process memory at each iteration of this loop. The current protocol state is necessarily stored into data structures, such as in heap and stack memory, which are updated at each request-reply exchange. In particular, the protocol state is represented by long-lived data, whose lifetime goes beyond an individual request-reply exchange, and spans across an entire session. Examples of such data are the current authentication status of a client, the current working directory, and enqueued inputs to be processed (Natella and Pham 2021). Conversely, short-lived data have a short lifetime, as they store data only needed by one or few request-reply exchanges (such as, a buffer that temporarily holds the reply message). StateAFL follows the evolution of long-lived data structures thorough a session, and discards short-lived data. When fuzzing succeeds at reaching a new protocol state, the new state results in new contents of the long-lived data structures. Thus, the proposed approach takes a snapshot of such data at the end of each request-reply exchange. Then, it uses this snapshot as a proxy for the current protocol state, by assigning a unique state identifier to each unique memory state through fuzzy hashing.

Figure 1 shows the fundamental loop, with an overview of long- and short-lived data over a session. We refer to an individual request-reply exchange as an iteration of the fundamental loop. For the purpose of example, in addition to the loop in the previous pseudocode, the figure also shows the typical case of a main thread that listens for connection requests, and spawns a worker thread for each session. Long-lived data can be allocated both by the main and the worker thread. At the beginning of a session, the worker may optionally perform a send() to transmit an initial banner message that welcomes the client. Then, the worker performs one or more receive() s to get a request from the client, processes the request, and performs one or more send() s to communicate a reply to the client. The worker can allocate short-lived data both before the receive() s (e.g., a buffer for the incoming request) and after them (e.g., data for intermediate computations). Similarly, it can free short-lived data both before and after the send() s. We note that the end of a request/reply iteration (and the beginning of the next one) is denoted by a receive() after one or more send() s.

StateAFL has been designed on the basis of the fundamental loop of network servers. Similarly to AFL and other coverage-driven fuzzers, StateAFL is a mutation-based fuzzer, which automatically produces fuzz inputs by mutating previous ones, and gets feedback from the target program about the coverage achieved by the previous fuzz inputs. This feedback is important for coverage-driven fuzzers to prioritize which previous inputs to mutate, where to mutate them, and which mutation operators to apply. Differently from other fuzzers, StateAFL gets feedback not only about code coverage (e.g., which statements and branches were executed), but also about protocol states reached during an execution.

Figure 2 provides an overview of StateAFL. In the first step, StateAFL compiles the source code of the target program. During this process, we apply compile-time instrumentation techniques to introduce additional code in the binary executable generated by the compiler. The instrumentation adds code to collect feedback about the coverage of protocol states, in a similar manner to instrumentation code added by other fuzzers for analyzing code coverage. Note that this approach requires the availability of the source code of the target server. This scenario represents relevant use cases for stateful network fuzzing, such as developers that need to fuzz their own software (e.g., as part of an automated V&V process), and users of open-source software that need to gain additional security evidence. We leave the fuzzing of binary-only software out of the scope of this work.

After the instrumentation, the StateAFL fuzzer runs the target server by launching the binary. To exercise the target server with fuzz inputs, StateAFL exchanges TCP/IP messages with the target, in the same way of a client. A fuzz input is managed as a sequence of request messages: for each request message in the sequence, the fuzzer sends it through TCP/IP, waits for a reply message, and moves to the next request message. In addition, the StateAFL fuzzer collects information about protocol states reached by the target server, through a side channel (a shared memory area). The feedback consists of a sequence of states, one for each request/reply iteration. Note that StateAFL works on application-level messages, as demarked by the fundamental loop of send() and receive() primitives. The application messages may be (or may be not) divided among multiple packets by the TCP/IP stack, transparently to the fuzzer.

Our current design focuses on TCP/IP (including both the TCP and UDP transport protocols), since this protocol suite is the most commonly adopted by network servers. It is possible to easily adapt the design to other communication protocols, such as RPC servers. This design also focuses on client-server communication; fuzzing through multiple channels (e.g., multi-party protocols) represents a separate, still open research problem (Natella and Pham 2021), which we leave out of scope of this paper.

To assess the feasibility of the approach and to support reproducible experimentation, we implemented StateAFL and integrated it with ProFuzzBench, a public benchmark for network fuzzers (Natella and Pham 2021). The benchmark includes 13 open-source network servers (Table 2). These targets are quite diverse with respect to several aspects: they cover 10 network protocols that have been typical targets of previous fuzzing studies; they are implemented both in C and in C++; they include both TCP and UDP, and both binary and text protocols; they adopt a variety of APIs (e.g., send/recv vs. fwrite/fread for networking, pthreads vs. fork for multiprocessing). ProFuzzBench automates the setup and the execution of the target servers using Docker containers, in a reproducible way. Moreover, ProFuzzBench configures the servers according to the best practices for coverage-driven fuzzing. In particular, the targets are patched to disable sources of randomness (e.g., pseudo-random number generators) in order to have reproducible behavior (i.e., if the program is executed again with the same input, then the same execution path is covered), which is an implicit assumption for coverage-driven fuzzing techniques. The experiments adopt the seed inputs from the ProFuzzBench project, where both practitioners and researchers contributed with both benchmark targets and with seeds for these targets. These seeds reflect typical basic usage of the servers according to their experience. The seeds include correct authentication and passwords (otherwise, the fuzzer would waste significant time before getting access to the server), and other frequent commands for the protocol (e.g., for FTP, the seeds get the list of files on the server, create directories and move across them, etc.). Table 2 provides the number of unique commands in the seeds for each target server. We remark that the need to provide initial seeds for the target server is a problem for any greybox fuzzing approach, in terms of automation and ability to work out-of-the-box for new software to test. We leave this aspect out of the scope of this work.

The experimental evaluation compares StateAFL with two baseline fuzzers. The baseline fuzzers were selected such that: (i) They are not limited to specific network protocols, but are applicable to a large set of network targets, including the ones in ProFuzzBench; this leaves out fuzzers that are highly-customized for a specific protocol (e.g., TLS (De Ruiter and Poll 2015), DTLS (Fiterau-Brostean et al. 2020)) but are not applicable to other protocols; (ii) They adopt state-of-the-art greybox, coverage-driven techniques, in order to evaluate how the proposed greybox solution relates to them. The two baseline fuzzers are:

These two tools represent different points in the design space of greybox network fuzzers. On the one hand, AFLnwe is a pure greybox, coverage-driven fuzzer, and it is a baseline to evaluate the relative merit of stateful fuzzing compared to plain coverage-driven fuzzing. On the other hand, AFLnet is a stateful network fuzzer that performs protocol state inference. Differently from the proposed StateAFL fuzzer, AFLnet relies on the contents of response messages to infer protocol states. Therefore, to be applicable, AFLnet must be customized with protocol-specific parsers, in order to extract status codes from the messages (where available). Therefore, AFLnet comes with parsers for a set of common protocols, and ProFuzzBench extended AFLnet with more parsers to support the network servers under test (Table 2). For some protocols (e.g., TinyDTLS), response messages do not have status codes; thus, the protocol parsers generate status codes from other fields (e.g., in DTLS, by joining the content type field from the header, and the message type field from the payload), based on protocol knowledge of AFLnet’s developers.

StateAFL overcomes the need for protocol-specific parsers, by instrumenting the target process and analyzing its memory at run-time, in order to be more broadly applicable without the need for manual customizations. In our evaluation, we analyze whether the protocol state inference by StateAFL can overcome the lack of protocol parsers. The experimental plan consists of a total of 156 experiments, with 4 repeated fuzzing experiments for each of the 13 target servers and of the 3 fuzzers, over a period of 24 h for each experiment. We execute experiments on the Google Cloud Platform, using E2 high-memory VM instances with 4 vCPUs, with a dedicated vCPU for each replication.

In our evaluation, the StateAFL fuzzer could successfully run on all of the target servers, without any protocol customization. StateAFL automatically instruments I/O APIs from the standard C library, to trigger on_send (on send, sendto, sendmsg, write, fprintf, and fwrite) and to trigger on_receive (recv, recvfrom, recvmsg, read, fgets, fread). In only one of the targets (Forked-daapd), which performs network I/O through the libevent API, we needed to configure StateAFL to probe the evhttp_request_get_uri and evhttp_send_reply API functions, in order to keep track of its request/reply loop. The information about the names of these APIs is easily available to developers, and can be learned from a quick inspection of the target server. No modification of StateAFL was needed, as it instruments these APIs in the same way of other APIs.

We implemented and released StateAFL as open-source software, and experimentally evaluated it on a benchmark of network servers. The experimental evaluation showed that StateAFL can match a protocol-custom fuzzer in terms of both code coverage and vulnerabilities, and can even exceed it for some targets. Moreover, StateAFL only introduces a limited overhead on the execution of the server under test. We also presented a qualitative analysis of the states inferred by StateAFL. The qualitative analysis pointed out an important insight about stateful fuzzing: the response codes returned by many protocols are often not representative of the current state of the server, but only reflect the outcome of the last request. For this reason, inferring states for response codes can significantly inflate the protocol state machine, leading to redundant fuzz tests. Having knowledge about the actual state of the server can be exploited by the fuzzer to avoid the redundant tests.

We expect that future work on stateful network protocol fuzzing will develop new solutions based on this observation. Potential directions for future research include new solutions from inferring states from memory analysis, such as by using techniques for static and dynamic program analysis, and new heuristics for generating fuzz inputs tailored for stateful protocols, such as algorithms for selecting which protocol states to fuzz and which portions of the input to mutate. Early work on these areas include Ba et al. (2022) and Li et al. (2022) for efficient definition of states based on program analysis, and Liu et al. (2021) on state selection algorithms. We also leave to future work the application of the proposed approach to binary-only programs. Since the instrumentation is limited to identifying and changing calls to library APIs, without changing the control and data flow, binary rewriting techniques represent good candidates for further research on this aspect (Dinesh et al. 2020; Duck et al. 2020). Finally, we expect future work to explore more applications of stateful fuzzing beyond network protocols, such as for the security testing of local stateful applications based on inter-process communication.