MTFuzz: Fuzzing with a Multi-Task Neural Network

Introduction

Coverage-guided graybox fuzzing is a widely used technique for detecting bugs and security vulnerabilities in real-world software (Zalewski, 2017; Darpa, 2016; Zalewski, 2017; Manes et al., 2018; Wang et al., 2019a; Nilizadeh et al., 2019; You et al., 2018; Lemieux and Sen, 2018; She et al., 2019b; Godefroid et al., 2008a; Arya and Neckar, 2012; Evans et al., 2011; Moroz and Serebryany, 2016). The key idea behind a fuzzer is to execute the target program on a large number of automatically generated test inputs and monitor the corresponding executions for buggy behaviors. However, as the input spaces of real-world programs are typically very large, unguided test input generation is not effective at finding bugs. Therefore, most popular graybox fuzzers use evolutionary search to generate new inputs; they mutate a set of seed inputs and retain only the most promising inputs (i.e., inputs exercising new program behavior) for further mutations (Zalewski, 2017; Wang et al., 2019a; Nilizadeh et al., 2019; You et al., 2018; Wei et al., 2018; Li et al., 2017; Godefroid et al., 2017; Lemieux and Sen, 2018; Jiang et al., 2018).

However, the effectiveness of traditional evolutionary fuzzers tends to decrease significantly over fuzzing time. They often get stuck in long sequences of unfruitful mutations, failing to generate inputs that explore new regions of the target program (Chen and Chen, 2018; She et al., 2019b, a). Several researchers have worked on designing different mutation strategies based on various program behaviors (e.g., focusing on rare branches, call context, etc.) (Lemieux and Sen, 2018; Chen and Chen, 2018). However, program behavior changes drastically, not only across different programs but also across different parts of the same program. Thus, finding a generic robust mutation strategy still remains an important open problem.

Recently, Machine Learning (ML) techniques have shown initial promise to guide the mutations (Saavedra et al., 2019; She et al., 2019b; Rajpal et al., 2017). These fuzzers typically use existing test inputs to train ML models and learn to identify promising mutation regions that improve coverage (She et al., 2019b; Godefroid et al., 2017; Rajpal et al., 2017; Saavedra et al., 2019). Like any other supervised learning technique, the success of these models relies heavily on the number and diversity of training samples. However, collecting such training data for fuzzing that can demonstrate successful/unsuccessful mutations is prohibitively expensive due to two main reasons. First, successful mutations that increase coverage are often limited to very few, sparsely distributed input bytes, commonly known as hot-bytes, in a high-dimensional input space. Without knowing the distribution of hot-bytes, it is extremely hard to generate successful mutations over the sparse, high-dimensional input space (She et al., 2019b; Saavedra et al., 2019). Second, the training data must be diverse enough to expose the model to various program behaviors that lead to successful/unsuccessful mutations—this is also challenging as one would require a large number of test cases exploring different program semantics. Thus, the ML-based fuzzers suffer from both sparsity and lack of diversity of the target domain.

In this paper, we address these problems using Multi-Task Learning, a popular learning paradigm used in domains like computer vision to effectively learn common features shared across related tasks from limited training data. In this framework, different participating tasks allow an ML model to effectively learn a compact and more generalized feature representation while ignoring task-specific noises. To jointly learn a compact embedding of the inputs, in our setting, we use different tasks for predicting the relationship between program inputs and different aspects of fuzzing-related program behavior (e.g., different types of edge coverage). Such an architecture addresses both the data sparsity and lack of diversity problem. The model can simultaneously learn from diverse program behaviors from different tasks as well as focus on learning the important features (hot bytes in our case) across all tasks. Each participating task will provide separate pieces of evidence for the relevance or irrelevance of the input features (Ruder, 2017).

To this end, we design, implement, and evaluate MTFuzz, a Multi-task Neural Network (MTNN) based fuzzing framework. Given the same set of test inputs, MTFuzz learns to predict three different code coverage measures showing various aspects of dynamic program behavior:

edge coverage: which edges are explored by a test input (Zalewski, 2017; She et al., 2019b)?

approach-sensitive edge coverage: if an edge is not explored, how far off it is (i.e., approach level) from getting triggered (McMinn and Holcombe, 2004a; Arcuri, 2010; McMinn, 2011; Pachauri and Srivastava, 2013)?

context-sensitive edge coverage: from which call context an explored edge is called (Chen and Chen, 2018; Wang et al., 2019b)?

Note that our primary task, like most popular fuzzers, is to increase edge coverage. However, the use of call context and approach level provides additional information to boost edge coverage.

Architecturally, the underlying MTNN contains a group of hidden layers shared across the participating tasks, while still maintaining task-specific output layers. The last shared layer learns a compact embedding of the input space as shown in Figure 1. Such an embedding captures a generic compressed representation of the inputs while preserving the important features, i.e., hot-byte distribution. We compute a saliency score (She et al., 2019a) of each input byte by computing the gradients of the embedded representation w.r.t. the input bytes. Saliency scores are often used in computer vision models to identify the important features by analyzing the importance of that feature w.r.t. an embedded layer (Simonyan et al., 2013). By contrast, in this paper, we use such saliency scores to guide the mutation process—focus the mutations on bytes with high saliency scores.

Our MTNN architecture also allows the compact embedding layer, once trained, to be transferred across different programs that operate on similar input formats. For example, compact-embedding learned with MTFuzz for one xml parser may be transferred to other xml parsers. Our results (in RQ4) show that such transfer is quite effective and it reduces the cost to generate high quality data from scratch on new programs which can be quite expensive. Our tool is available at https://git.io/JUWkj and the artifacts available at doi.org/10.5281/zenodo.3903818.

We evaluate MTFuzz on 10 real world programs against 5 state-of-the-art fuzzers. MTFuzz covers at least 1000 more edges on 5 programs and several 100 more on the rest. MTFuzz also finds a total of 71 real-world bugs (11 previously unseen) (see RQ1). When compared to learning each task individually, MTFuzz offers significantly more edge coverage (see RQ2). Lastly, our results from transfer learning show that the compact-embedding of MTFuzz can be transferred across parsers for xml and elf binaries.

Overall, our paper makes the following key contributions:

We present a novel fuzzing framework based on multi-task neural networks called MTFuzz that learns a compact embedding of otherwise sparse and high-dimensional program input spaces. Once trained, we use the salience score of the embedding layer outputs w.r.t. the input bytes to guide the mutation process.

Our empirical results demonstrate that MTFuzz is significantly more effective than current state-of-the-art fuzzers. On $10$ real world programs, MTFuzz achieves an average of $2\times$ and up to $3\times$ edge coverage compared to Neuzz, the state-of-the-art ML-based fuzzer. MTFuzz also finds $11$ previously unknown bugs other fuzzers fail to find. The bugs have been reported to the developers.

We demonstrate that transferring of the compact embedding across programs with similar input formats can significantly increase the fuzzing efficiency, e.g., transferred embeddings for different file formats like ELF and XML can help MTFuzz to achieve up to $14\times$ edge coverage compared to state-of-the-art fuzzers.

Background: Multi-task Networks

Multi-task Neural Networks (MTNN) are becoming increasingly popular in many different domains including optimization (Argyriou et al., 2008; Gong et al., 2014), natural language processing (Collobert and Weston, 2008; Binge and Sogaard, 2017), and computer vision (Standley et al., 2019). The key intuition behind MTNN is that it is useful for related tasks to be learned jointly so that each task can benefit from the relevant information available in other tasks (Caruana, 1996, 1997; Standley et al., 2019; Zamir et al., 2018). For example, if we learn to ride a unicycle, a bicycle, and a tricycle simultaneously, experiences gathered from one usually help us to learn the other tasks better (Zhang and Yang, 2017). In this paper, we use a popular MTNN architecture called hard parameter sharing (Caruana, 1997), which contain two groups of layers (see Fig. 5): a set of initial layers shared among all the tasks, and several individual task-specific output layers. The shared layers enable a MTNN to find a common feature representation across all the tasks. The task specific layers use the shared feature representation to generate predictions for the individual tasks (Kokkinos, 2017; Standley et al., 2019; Ruder, 2017).

MTNN Training. While MTNNs can be used in many different ML paradigms, in this paper we primarily focus on supervised learning. We assume that the training process has access to a training dataset $\mathcal{X}=\{x_{1},x_{2},...,x_{n}\}$. The training data contains the ground truth output labels for each task. We train the MTNN on the training data using standard back-propagation to minimize a multi-task loss.

Multi-task Loss. An MTNN is trained using a multi-task loss function, $\mathcal{L}$. We assume that each individual task $\tau_{i}$ in the set of tasks $\mathcal{T}=\{\tau_{1},\tau_{2},...,\tau_{m}\}$ has a corresponding loss function $\mathcal{L}_{i}$. The multi-task loss is computed as a weighted sum of each individual task loss. More formally, it is given by $\mathcal{L}=\sum^{m}_{i=1}\alpha_{i}\cdot\mathcal{L}_{i}$. Here, $\alpha_{i}$ represents the weight assigned to task $i$. The goal of training is to reduce the overall loss. In practice, the actual values of the weights are decided based on the relative importance of each task. Most existing works assign equal weights to the tasks (Uhrig et al., 2016; Teichmann et al., 2018; Liao et al., 2016).

The multi-task loss function forces the shared layer to learn a general input representation for all tasks offering two benefits:

1) Increased generalizibility. The overall risk of overfitting in multi-task models is reduced by an order of $m$ (where $\mathit{m}$ is the number of tasks) compared to single task models (Baxter, 1997). Intuitively, the more tasks an MTNN learns from, the more general the compact representation is in capturing features of all the tasks. This prevents the representation from overfitting to the task-specific features.

2) Reduced sparsity. The shared embedding layer in an MTNN can be designed to increase the compactness of the learned input representation. Compared with original input layer, a shared embedding layer can achieve same expressiveness on a given set of tasks while requiring far fewer nodes. In such compact embedding, the important features across different tasks will be boosted with each task contributing its own set of relevant features (Ruder, 2017).

Methodology

This section presents a brief overview of MTFuzz that aims to maximize edge coverage with the aid of two additional coverage measures: context-sensitive edge coverage and approach-sensitive edge coverage using multi task learning. Figure 1 illustrates an end-to-end workflow of the proposed approach. The first stage trains an MTNN to produce a compact embedding of an otherwise sparse input space while preserving information about the hot bytes i.e., the input bytes have the highest likelihood to impact code coverage (Section 3.2). The second stage identifies these hot bytes and focuses on mutating them (Section 3.3). Finally, in the third stage, the seed corpus is updated with the mutated inputs and retains only the most interesting new inputs (Section 3.4).

The goal of any ML-based fuzzers, including MTFuzz, is to learn a mapping between input space and code coverage. The most common coverage explored in the literature is edge coverage, which is an effective measure and quite easy to instrument. However, it is coarse-grained and misses many interesting program behavior (e.g., explored call context) that are known to be important to fuzzing. One workaround is to model path coverage by tracking the program execution path per input. However, keeping track of all the explored paths can be computationally intractable since it can quickly lead to a state-space explosion on large programs (Wang et al., 2019b). As an alternative, in this work, we propose a middle ground: we model the edge coverage as the primary task of the MTNN, while choosing two other fine-granular coverage metrics (approach-sensitive edge coverage and context-sensitive edge coverage) as auxiliary tasks to provide useful additional context to edge coverage.

Edge coverage measures how many unique control-flow edges are triggered by a test input as it interacts with the program. It has become the de-facto code coverage metric (Zalewski, 2017; She et al., 2019b; Lemieux and Sen, 2018; You et al., 2018) for fuzzing. We model edge coverage prediction as the primary task of our multi-task network, which takes a binary test case as input and predicts the edges that could be covered by the test case. For each input, we represent the edge coverage as an edge bitmap, where value per edge is set to 1 or 0 depending on whether the edge is exercised by the input or not.

In particular, in the control-flow-graph of a program, an edge connects two basic blocks (denoted by prev_block and cur_block) (Zalewski, 2017). A unique $edge\_id$ is obtained as: $hash(\texttt{prev\_block},\texttt{cur\_block})$. For each $edge\_id$, there is a bit allocated in the bitmap. For every input, the edge_ids in the corresponding edge bitmap are set to 1 or 0, depending on whether or not those edges were triggered.

1.2. Approach-Sensitive Edge Coverage: Auxiliary Task 1.

For an edge that is not exercised by an input, we measure how far off the edge is from getting triggered. Such a measure provides additional contextual information of an edge. For example, if two test inputs failed to trigger an edge, however one input reached “closer” to the unexplored edge than the other, traditional edge coverage would treat both inputs the same. However, using a proximity measure, we can discern between the two inputs and mutate the closer input so that it can reach the unexplored edge. To achieve this, approach-sensitive edge coverage extends edge coverage by offering a distance measure that computes the distance between an unreached edge and the nearest edge triggered by an input. This is a popular measure in the search-based software engineering literature (McMinn and Holcombe, 2004a; McMinn, 2011; Arcuri, 2010), where instead of assigning a binary value (0 or 1), as in edge bitmap, approach level assigns a numeric value between 0 and 1 to represent the edges (McMinn and Holcombe, 2004b); if an edge is triggered, it is assigned 1. However, if the edge is not triggered, but one of its parents are triggered, then the non-triggered edge is assigned a value of $\beta$ (we use $\beta=0.5$). If neither the edge nor any of its parents are triggered, it is assigned . This is illustrated in Fig. 2. Note that, for a given edge, we refrain from using additional ancestors farther up the control-flow graph to limit the computational burden. The approach sensitive coverage is represented in an approach bitmap, where for every unique $edge\_id$, we set an approach level value, as shown in Fig. 2. We model this metric in our Multi-task Neural Network as an auxiliary task, where the task takes binary test cases as inputs and learn to predict the corresponding approach-level bitmaps.

1.3. Context-sensitive Edge Coverage: Auxiliary Task 2.

Edge coverage cannot distinguish between two different test inputs triggering the same edge, but via completely different internal states (e.g., through the same function called from different sites in the program). This distinction is valuable since reaching an edge via a new internal state (e.g., through a new function call site) may trigger a vulnerability hidden deep within the program logic. Augmenting edge coverage with context information regarding internal states of the program may help alleviate this problem (Chen and Chen, 2018).

Consider the example in Fig. 3. Here, for an input , the first call to function foo() appears at site line 12 and it triggers the if condition (on line 2); the second call to foo() appears on site line 14 and it triggers the else condition (on line 5). As far as edge coverage is concerned, both the edges of the function foo() (on lines 2 and 5) have been explored and any additional inputs will remain uninteresting. However, if we provide a new input say , we would first trigger line 5 of foo when it is called from line 12. Then we trigger line 2 of foo from line 14 and further cause a buffer overflow at line 3 because a 12 bytes string is written into a 8 bytes destination buffer buf. Moveover, the input will not be saved by edge coverage fuzzer since it triggers no new edges. Frequently called functions (like strcmp) may be quite susceptible such crashes (Wang et al., 2019b).

In order to overcome this challenge, Chen et al. (Chen and Chen, 2018) propose keeping track of the call stack in addition to the edge coverage by maintaining tuple: $(\textit{call\_stack},\textit{prev\_block},\textit{cur\_block})$. Fig. 4 shows the additional information provided by context-sensitive edge coverage over edge coverage. Here, we see an example where a buggy input has the exact same edge coverage as the clean input . However, the call context information can differentiate these two inputs based on the call stacks at line 12 and 14.

We model context-sensitive edge coverage in our framework as an auxiliary task. We first assign a unique id to every call. Next, at run time, when we encounter a call at an edge ($edge\_id$), we first compute a $hash$ to record all the functions on current call stack as: $call\_stack=call\_id_{1}\oplus...\oplus call\_id_{n}$, where $call\_id\_i$ represents the $\mathit{i}$-th function on current call stack and $\oplus$ denotes XOR operation. Next, we compute the context sensitive edge id as: $call\_trace\_id=call\_stack\oplus edge\_id$.

Thus we obtain a unique $call\_trace\_id$ for every function called from different contexts (i.e., call sites). We then create a bit-map of all the $call\_trace\_id$s. Unlike existing implementations of context-sensitive edge coverage (Chen and Chen, 2018; Wang et al., 2019b), we assign an additional id to each call instruction while maintaining the original $edge\_id$ intact. Thus, the total number of elements in our bit map reduces to sum of $call\_trace\_id$s and $edge\_id$s rather than a product of $call\_trace\_id$s and $edge\_id$s. An advantage of our design is that we minimize the bitmap size. In practice, existing methods requires around $7\times$ larger bitmap size than just edge coverage (Chen and Chen, 2018); our implementation only requires around $1.3\times$ bitmap size of edge coverage. The smaller bitmap size can avoid edge explosion and improve performance.

In our multi-tasking framework, the context-sensitive edge coverage “task” is trained to predict the mapping between the inputs and the corresponding $call\_trace\_id$s bitmaps. This can enable us to learn the difference between two inputs in a more granular fashion. For example, an ML model can learn that under certain circumstances, the second input byte (input in Fig. 3) can cause crashes. This information cannot be learned by training to predict for edge coverage alone since both inputs will have the same edge coverage (as shown in Fig. 4).

2. Stage-I: Multi-Task Training

This phase builds a multi-task neural network (MTNN) that can predict different types of edge coverage given a test input. The trained model is designed to produce a more general and compact embedding of the input space focusing only on those input bytes that are most relevant to all the tasks. This compact representation will be reused by the subsequent stages of the program to identify the most important bytes in the input (i.e., the hot-bytes) and guide mutations on those bytes.

Fig. 5 shows the architecture of the MTNN. The model contains an encoder (shared among all the tasks) and three task-specific decoders. The model takes existing test input bytes as input and outputs task-specific bitmap. Each input byte corresponds to one input node, and each bitmap value corresponds to an ouput node.

Encoder. Comprises of one input layer followed by three progressively narrower intermediate layers. The total number of nodes in the input layer is equal to the total number of bytes in the largest input in the seed corpus. All shorter inputs are padded with 0x00 for consistency. The last layer of the encoder is a compact representation of the input to be used by all the tasks (green in Fig. 5). Decoders. There are three task-specific decoders (shown in lilac in Fig. 5). Each task specific decoder consists of three intermediate layers that grow progressively wider. The last layer of each of the decoder is the output layer. For edge coverage, there is one node in the output layer for each unique $edge\_id$, likewise for context-sensitive edge coverage there is one output node for each $call\_trace\_id$, and for approach-sensitive edge coverage there is one output node for each unique $edge\_id$ but they take continuous values (see Fig. 2).

2.2. Loss functions.

The loss function of a MTNN is a weighted sum of the task-specific loss functions. Among our three tasks, edge coverage and context-sensitive edge coverage are modeled as classification tasks and approach-sensitive edge coverage is modeled as a regression task. Their loss functions are designed accordingly.

Loss function for approach-sensitive edge coverage. Approach-level measures how close an input was from an edge that was not triggered. This distance is measured using a continuous value between 0 and 1. Therefore, this is a regression problem and we use mean squared error loss, given by:

Where $Y_{i}$ is the prediction and $\hat{Y_{i}}$ is the ground truth.

Loss functions for edge coverage and context-sensitive edge coverage. The outputs of both these tasks are binary values where 1 means an input triggered the $edge\_id$ or the $call\_trace\_id$ and 0 otherwise. We find that while some $edge\_id$s or $call\_trace\_id$s are invoked very rarely, resulting in imbalanced classes. This usually happens when an input triggers a previously unseen (rare) edges. Due to this imbalance, training with an off-the-shelf loss functions such as cross entropy is ill suited as it causes a lot of false negative errors often missing these rare edges.

To address this issue, we introduce a parameter called penalty (denoted by $\beta$) to penalize these false negatives. The penalty is the ratio of the number of times an edge is not invoked over the number of times it is invoked. That is,

Here, $\beta_{\tau}$ represents the penalty for every applicable task $\tau<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∈</mo></mrow><annotation encoding="application/x-tex">\in</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.5782em;vertical-align:-0.0391em;"></span><span class="mrel">∈</span></span></span></span></span>\mathcal{T}$ and it is dynamically evaluated as fuzzing progresses. Using $\beta_{\tau}$ we define an adaptive loss for classification tasks in our MTNN as:

In Eq. 2, $\mathcal{L}_{\tau_{\text{\tiny ec/ctx}}}$ results in two separate loss functions for edge coverage and context-sensitive edge coverage. The penalty ($\beta_{\tau}$) is used to penalize false-positive and false-negative errors. $\beta_{\tau}>1$ penalizes $p\cdot log({\hat{p}})$, representing false negatives; $\beta_{\tau}=1$ penalizes both false positives and false negatives equally; and $\beta_{\tau}<1$ penalizes $(1-p)\cdot log({1-\hat{p}})$, representing false positives. With this, we compute the total loss for our multi-task NN model with $K$ tasks:

This is the weighted sum of the adaptive loss $\mathcal{L}_{i}$ for each individual task. Here, $\alpha_{i}$ presents the weight assigned to task $i$.

3. Stage-II: Guided Mutation

This phase uses the trained MTNN to generate new inputs that can maximize the code coverage. This is achieved by focusing mutation on the byte locations in the input that can influence the branching behavior of the program (hot-bytes).

We use the the compact embedding layer of the MTNN (shown in green in Fig. 5) to infer the hot-byte distribution. The compact embedding layer is well suited for this because it (a) captures the most semantically meaningful features (i.e., bytes) in the input in a compact manner; and (b) learns to ignore task specific noise patterns (Kumar et al., 2017) and pays more attention to the important bytes that apply to all tasks (Chen et al., 2016; Kulkarni et al., 2015; Bengio et al., 2013).

Note that when input bytes in $\mathbf{xb}$ changes, $\mathbf{z}$ changes accordingly. The amount of the change is determined by how influential each byte in the input is to all the tasks in the MTNN model. Changes to the hot-bytes, which are more influential, will result in larger changes to $\mathbf{z}$. We use this property to discover the hot-bytes.

To determine how influential each byte in $\mathbf{xb}$ is, we compute the partial derivatives of the nodes in compact layer with respect to all the input bytes. The partial derivative of the $j$-th node in the embedding layer with respect to the $\mathit{i}$-th input byte is:

For each selected byte-locations, we create a new mutated input by changing the bytes to all permissible values between 0 and 255. Since this only happens to the $\mathit{top-k}$ hot-bytes, the number of newly mutated seeds remains manageable. We use these mutated inputs for fuzzing and monitor various coverage measures.

4. Stage-III: Seed Selection & Incremental Learning

In this step, MTFuzz samples some of the mutated inputs from the previous stage to retrain the model. Sampling inputs is crucial as the choice of inputs can significantly affect the fuzzing performance. Also, as fuzzing progresses, the pool of available inputs keeps growing in size. Without some form of sampling strategy, training the NN and computing gradients would take prohibitively long.

To this end, we propose an importance sampling (Owen, 2013) strategy where inputs are sampled such that they reach some important region of the control-flow graph instead of randomly sampling from available input. In particular, our sampling strategy first retains all inputs that invoke previously unseen edges. Then, we sort all the seen edges by their rarity. The rarity of an edge is computed by counting how many inputs trigger that specified edge. Finally, we select the top $T$-rarest edges and include at least one input triggering each of these rare edges. We reason that, by selecting the inputs that invoke the rare edges, we may explore deeper regions of the program on subsequent mutations. In order to limit the number of inputs sampled, we introduce a sampling budget $K$ that determines how many inputs will be selected per iteration.

Using these sampled inputs, we retrained the model periodically to refine its behavior—as more data is becoming available about new execution behavior, retraining makes sure the model has knowledge about them and make more informed predictions.

Evaluation

Implementation. Our MTNN model is implemented in Keras-2.2.3 with Tensorflow-1.8.0 as a backend (Abadi et al., 2016; Chollet et al., 2015). The MTNN is based on a feed-forward model, composed of one shared encoder and three independent decoders. The encoder compresses an input file into a $512$ compact feature vector and feeds it into three following decoders to perform different task predictions. For encoder, we use three hidden layers with dimensions 2048, 1024 and 512. For each decoder, we use one final output layer to perform corresponding task prediction. The dimension of final output layer is determined by different programs. We use ReLU as activation function for all hidden layers. We use sigmoid as the activation function for the output layer. For task specific weights, set each task to equal weight ($\alpha_{\tau}=1$ in Eq. 3). The MTNN model is trained for 100 epochs achieving a test accuracy of around $95\%$ on average. We use Adam optimizer with a learning rate of 0.001. As for other hyperparameters, we choose k=1024 for $top-K$ hot-bytes. For seed selection budget $T$ in Stage-III (§3.4), we use $T=750$ input samples where each input reaches atleast one rare edge. We note that all these parameters can be tuned in our replication package.

To obtain the various coverage measures, we implement a custom LLVM pass. Specifically, we instrument the first instruction of each basic block of tested programs to track edge transition between them. We also instrument each call instructions to record the calling context of tested programs at runtime. Additionally, we instrument each branch instructions to measure the distance from branching points to their corresponding descendants. As for magic constraints, we intercept operands of each CMP instruction and use direct-copy to satisfy these constraints.

Study Subjects. We evaluate MTFuzz on 10 real-world programs, as shown in Table 2. To demonstrate the performance of MTFuzz, we compare the edge coverage and number of bugs detected by MTFuzz with $5$ state-of-the-art fuzzers listed in Table 2. Each state-of-the-art fuzzer was run for 24 hours. The training, retraining, and fuzzing times are included in the total 24 runs for each fuzzer. Training time for MTFuzz is shown in Table 2. MTFuzz and Neuzz both use the same initial seeds for the the approaches and the same fuzzing backend for consistency. We ensure that all other experimental settings were also identical across all studied fuzzers.

Experimental Setup. All our measurements are performed on a system running Ubuntu 18.04 with Intel Xeon E5-2623 CPU and an Nvidia GTX 1080 Ti GPU. For each program tested, we run AFL-2.52b (Zalewski, 2017) on a single core machine for an hour to collect training data. The average number of training inputs collected for $10$ programs is around $2K$. We use 10KB as the threshold file size for selecting our training data from the AFL input corpus (on average 90% of the files generated by AFL were under the threshold).

Experimental Results

We evaluate MTFuzz with the following research questions:

RQ1: Performance. How does MTFuzz perform in comparison with other state-of-the-art fuzzers?

RQ2: Contributions of Auxiliary Tasks. How much does each auxiliary task contribute to the overall performance of MTFuzz?

RQ3: Impact of Design Choices. How do various design choices affect the performance of MTFuzz?

RQ4: Transferrability. How transferable is MTFuzz?

We compare MTFuzz wiht other fuzzers (from Table 2) in terms of the number of real-world and synthetic bugs detected (RQ1-A and RQ1-B), and edge coverage (RQ1-C).

RQ1-A. How many real world bugs are discovered by MTFuzz compared to other fuzzers?

Evaluation. To evaluate the number of bugs discovered by a fuzzer, we first instrument the program binaries with AddressSanitizer (asa, 2020) and UnderfinedBehaviorSanitizer (ubs, 2020). Such instrumentation is necessary to detect bugs beyond crashes. Next, we run each of the fuzzers for 24 hours (all fuzzers use the same seed corpus) and gather the test inputs generated by each of the fuzzers. We run each of these test inputs on the instrumented binaries and count the number of bugs found in each setting. Finally, we use the stack trace of bug reports generated by two sanitizers to categorize the found bugs. Note, if multiple test inputs trigger the same bug, we only consider it once. Table 3 reports the results.

MTFuzz finds a total of 71 bugs, the most among other five fuzzers in 7 real world programs. In the remaining three programs, no bugs were detected by any fuzzer after 24 hours.

Among these, 11 bugs were previously unreported.

Among the other fuzzers, Neuzz (another ML-based fuzzer) is the second best fuzzer, finding 60 bugs. Angora finds 58. We observe that the 11 new bugs predominantly belonged to 4 types: memory leak, heap overflow, integer overflow, and out-of-memory. Interestingly, MTFuzz discovered a potentially serious heap overflow vulnerability in mupdf that was not found by any other fuzzer so far (see Figure 6). A mupdf function ensure_solid_xref allocates memory (line 10) for each object of a pdf file and fills content to these memory chunks (line 14). Prior to that, at line 6, it tries to obtain the total number of objects by reading a field value xref->num_objects which is controlled by program input: a pdf file. MTFuzz leverages gradient to identify the hot bytes which control xref->num_objects and sets it to a negative value. As a result, num maintains its initial value $1$ as line 6 if check fails. Thus, at line 10, the function allocates memory space for a single object as $num=1$. However, in line 14, it tries to fill more than one object to new_sub->table and causes a heap overflow. This bug results in a crash and potential DoS if mupdf is used in a web server.

RQ1-B. How many synthetic bugs in LAVA-M dataset are discovered by MTFuzz compared to other fuzzers?

Evaluation. LAVA-M is a synthetic bug benchmark where bugs are injected into four GNU coreutil programs (lava). Each bug in LAVA-M dataset is guarded by a magic number condition. When the magic verification is passed, the corresponding bug will be triggered. Following conventional practice, we run MTFuzz and other fuzzers from Table 2 on LAVA-M dataset for a total of 5 hours. We measure the number of bugs triggered by each of the state-of-the-art fuzzers. The result is tabulated in Table 4.

Observations. MTFuzz discovered the most number of bugs on all 4 programs after 5 hours run. The better performance is attributed to the direct-copy module. To find a bug in LAVA-M dataset, fuzzers need to generate an input which satisfies the magic number condition. MTFuzz’s direct-copy module is very effective to solve these magic number verification since it can intercept operands of each CMP instruction at runtime and insert the magic number back into generated inputs.

RQ1-C. How much edge coverage does MTFuzz achieve compared to other fuzzers?

Evaluation. To measure edge coverage, we run each of the fuzzers for 24 hours (all fuzzers use the same seed corpus). We periodically collect the edge coverage information of all the test inputs for each fuzzer using AFL’s coverage report toolkit afl-showmap (Zalewski, 2017). AFL provides coverage instrumentation scheme in two mainstream compilers GCC and Clang. While some authors prefer to use afl-gcc (She et al., 2019b; Lemieux and Sen, 2018; Böhme et al., 2017), some others use afl-clang-fast(Chen and Chen, 2018; Gan et al., 2020). The underlying compilers can have different program optimizations which affects how edge coverage is measured. Therefore, in order to offer a fair comparison with previous studies, we measure edge coverage on binaries compiled with with both afl-gcc and afl-clang-fast. In the rest of the paper, we report results on programs compiled with afl-clang-fast. We observed similar findings with afl-gcc.

Observations. The results for edge coverage after 24 hours of fuzzing are tabulated in Table 5. The edge-coverage gained over time is shown in Fig. 7. Overall, MTFuzz achieves noticeably more edge coverage than all other baseline fuzzers. Consider the performance gains obtained over the following families of fuzzers:

$\circ$ Evolutionary fuzzers: MTFuzz outperforms all the three evolutionary fuzzers studied here. MTFuzz outperforms Angora on the 6 programs which Angora supports and achieves up to $2297$ more edges in objdump. Note, Angora can’t run on some programs due to the external library issue on its taint analysis engine (Chen and Chen, 2018; Aschermann et al., 2019). When compared to both FairFuzz and AFLFast, MTFuzz covers significantly more edges, e.g., $4702$ more than FairFuzz in readelf and over 28.1$\times$ edges compared to AFLFast on objdump.

$\circ$ Machine learning based fuzzers: In comparison with the state-of-the-art ML based fuzzer, Neuzz (She et al., 2019b), we observed that MTFuzz achieves much greater edge coverage in all 10 programs studied here. We notice improvements of 2000 more edges in readelf and 2500 more edges in nm and strip.

MTFuzz found 71 real-world bugs (11 were previously unknown) and also reach on average $1,277$ and up to $2,867$ more edges compared to Neuzz, the second-best fuzzer, on $10$ programs.

RQ2: Contributions of Auxiliary Tasks

MTFuzz is comprised of an underlying multi-task neural network (MTNN) that contains one primary task (edge coverage) and two auxiliary tasks namely, context-sensitive edge coverage and approach-sensitive edge coverage. A natural question that arises is—How much does each auxiliary task contributes to the overall performance?

Evaluation. To answer this question, We study what would happen to the edge coverage when one of the auxiliary tasks is excluded from the MTFuzz. For this, we build four variants of MTFuzz:

(EC): A single-task NN with only the primary task to predict edge coverage.

(EC, Call Ctx): An MTNN with edge coverage as the primary task and context-sensitive edge coverage as the auxiliary task.

(EC, Approach): An MTNN with edge coverage as the primary task and approach-sensitive edge coverage as the auxiliary task.

MTFuzz: Our proposed model with edge coverage as the primary task and two auxiliary tasks context-sensitive edge coverage and approach-sensitive edge coverage.

To rule out other confounders, we ensure that each setting shares the same hyper-parameters and the same initial seed corpus. Also, we ensure that all subsequent steps in fuzzing remain the same across each experiment. With these settings, we run each of the above multi-task models on all our programs from Table 2 for 1 hour to record the edge coverage for each of these MTNN models. Observations. Our results are tabulated in Table 6. We make the following noteworthy observations:

1. Fuzzer that uses an MTNN trained on edge coverage as the primary task and context-sensitive edge coverage as the only auxiliary task tends to perform only marginally better than a single task NN based on edge coverage. In some cases, e.g., in Table 6 we notice about 25% more edges. However, in some other cases, for example libjpeg, we noticed that the coverage reduces by almost $31\%$.

2. The above trend is also observable for using edge coverage with approach-sensitive edge coverage as the auxiliary. For example, in libjpeg, the edge coverage is lower than the single-task model that uses only edge coverage.

3. However, MTFuzz, which uses both context-sensitive edge coverage and approach-sensitive edge coverage as auxiliary tasks to edge coverage, performs noticeably better than all other models with up to 800 more edges covered ($\mathbf{\approx}$20%) in the case of readelf.

The aforementioned behavior is expected because each auxiliary task provides very specific albeit somewhat partial context to edge coverage. Context-sensitive edge coverage only provides context to triggered edges, while approach-sensitive edge coverage only reasons about non-triggered edges (see §3.1 for details). Used in isolation, a partial context does not have much to offer. However, while working together as auxiliary tasks along with the primary task, it provides a better context to edge coverage resulting in overall increased edge coverage (see the last column of Table 6).

MTFuzz benefits from both the auxiliary tasks. Using context-sensitive edge coverage and edge coverage along with the primary task (of predicting edge coverage) is most beneficial. We achieve up to 20% more edge coverage.

RQ3. Impact of Design Choices

While building MTFuzz, we made few key design choices such as using a task-specific adaptive loss (§3.2.2) to improve the quality of the multi-task neural network (MTNN) model and a novel seed selection strategy based on importance sampling (see §3.4). Here we assess how helpful these design choices are.

RQ3-A. What are the benefits of using adaptive loss?

MTNN model predicting for edge coverage and for context-sensitive edge coverage tends to experience severely imbalanced class labels. Consider the instance when a certain input triggers an edge for the first time. This is an input of much interest because it represents a new behaviour. The MTNN model must learn what lead to this behaviour. However, in the training sample, there exists only one positive sample for this new edge in the entire corpus. An MTNN that is trained with an off-the-shelf loss functions is likely to misclassify these edges resulting in a false negative error. Such false negatives are particularly damaging because a large number of new edge discoveries go undetected affecting the overall model performance. To counter this, we defined an adaptive loss in §3.2.2; here we measure how much it improves the MTNN’s performance.

Evaluation. To evaluate the effect of class imbalance, we measure recall which is high when the overall false negatives (FN) are low. While attempting to minimize FNs the model must not make too many false positive (FP) errors. Although false positives are not as damaging as false negatives, we must attempt to keep them low. We therefore also keep track of the F1-scores which quantify the trade-off between false positives and false negatives. We train MTFuzz with two different losses (i.e., with our adaptive loss and with the default cross-entropy loss) on $10$ programs for $100$ epochs and record the final recall and F-1 scores.

Observations. The result are shown in Table 7. We observe that adaptive loss results in MTNNs with an average of $\mathbf{90\%}$ recall score on $10$ programs, while the default loss model only achieves on average $75\%$ recall score. Generally, we notice improvements greater than $\mathbf{15\%}$ over default loss functions. The low recall for default loss function indicates that it is susceptible to making a lot of false negative predictions. However, our adaptive loss function is much better at reducing false negative predictions. Also, the adaptive loss model achieves on average F-1 score of $72\%$, while unweighted loss model achieves an average of $70\%$. This is encouraging because even after significantly reducing the number of false negatives, we maintain the overall performance of the MTNN.

Weighted loss improves MTFuzz’s recall by more than 15%.

Evaluation. Here, we evaluate our seed selection strategy (§3.4) by comparing it to a random selection strategy. Specifically, we run two variants of MTFuzz, one with importance sampling for seed selection and the other with a random seed selection. All other components of the tool such as MTNN model, hyperparameters, random seed, etc. are kept constant. We measure the edge coverage obtained by both the strategies on 10 programs after fuzzing for one hour. Table 7 shows the results.

Observations. When compared to a random seed selection strategy. Importance sampling outperforms random seed selection in all $10$ programs offering average improvements of $1.66\times$ more edges covered than random seed selection—for readelf, it covers around $2000$ more edges. This makes intuitive sense because, the goal of importance sampling was to retain the newly generated inputs that invoke certain rare edges. By populating the corpus with such rare and novel inputs, the number of newly explored edges would increase over time, resulting in increase edge coverage (see Table 7).

Importance sampling helps MTFuzz achieve on average $1.66\times$ edge coverage compared with random seed selection.

RQ4. Transferability

In this section, we explore the extent to which MTFuzz can be generalized across different programs operating on the same inputs (e.g., two ELF fuzzers). Among such programs, we study if we can transfer inputs generated by fuzzing from one program to trigger edge coverage in another program (RQ4-A) and if it is possible to transfer the shared embedding layers between programs (RQ4-B).

RQ4-A. Can inputs generated for one program be transferred to other programs operating on the same domain?

MTFuzz mutates the hot-bytes in the inputs to generate additional test inputs. These hot-bytes are specific to the underlying structure of the inputs. Therefore, inputs that have been mutated on these hot-bytes should be able to elicit new edge coverage for any program that parses the same input.

Evaluation. To answer this question, we explore 5 different programs that operate on 2 file types: (1) readelf, size, and nm operating on ELF files, and (2) libxml and xmlwf (xml, 2020) operating on XML files. For all the programs that operate on the same file format:

Observation. We observe from Table 8 that inputs generated by MTFuzz produce much higher edge coverage on the target program compared to seeds generated by Neuzz or AFL. In general, we notice on average $10\times$ more edge coverage than AFL and $2\times$ more edge coverage than Neuzz. Here, AFL performs the worse, since it generates seeds very specific to the source program. Neuzz, a machine learning based fuzzer, performs better than AFL since it attempts to learn some representation of the input, but it falls short of MTFuzz which learns the most general input representation.

RQ4-B. Can the shared layer be transferred between programs?

We hypothesize that since MTFuzz can learn a general compact representation of the input, it should, in theory, allow for these compact representations to be transferred across programs that share the same input, e.g., across programs that process ELF binaries.

Evaluation: To verify this, we do the following:

Note that the key distinction here is, unlike RQ4-A, here we fuzz the target program with MTFuzz using the shared layers and the seed from the source program to bootstrap fuzzing.

Observation. We achieve significantly more edge coverage by transferring both the seeds and the shared embedding layers from the source to target program (Table 8). On average, we obtain $2\times$ more edge coverage on all $10$ programs. Specifically, transferring the shared embedding layers and the seeds from nm to readelf results in covering 2$\times$ more edges compared to Neuzz and over 15$\times$ more edges compared to AFL. Transferring offers better edge coverage compared to fuzzing the target program with AFL.

MTFuzz’s compact embedding can be transferred across programs that operate on similar input formats. We achieve up to $14$ times edge coverage for XML files (with an average of $2$ times edge coverage across all programs) compared to other fuzzers.

Threats to validity

(a) Initialization: For the fuzzers studied here, it is required to provide initial set of seed inputs. To ensure a fair comparison, we use the same set of seed inputs for all the fuzzers. (b) Target programs: We selected diverse target programs from a wide variety of software systems. One still has to be careful when generalizing to other programs not studied here. We ensure that all the target programs used in this study have been used previously; we do not claim that our results generalize beyond these programs. (c) Other fuzzers: When comparing MTFuzz with other state-of-the-art fuzzers, we use those fuzzers that are reported to work on the programs tested here. Our baseline fuzzer Neuzz (She et al., 2019b) has reported to outperform many other fuzzers on the same studied programs. Since we are outperforming Neuzz, it is reasonable to expect that we will outperform the other fuzzers as well.

Related Work

Fuzzing (Miller et al., 1990) has garnered significant attention recently. There are three broad types of fuzzers: (a) Blackbox (Hocevar, 2011; Höschele and Zeller, 2016; Cha et al., 2015) with no knowledge of the target program, (b) Whitebox (Cadar et al., 2008; Godefroid et al., 2005; Sen and Agha, 2006; Godefroid et al., 2008b) with source/binary level access the target program, and (c) Greybox fuzzers like AFL with the ability to instrument and collect some target-program-specific information like code coverage. This paper specifically focuses on greybox fuzzers. Most greybox fuzzers use evolutionary search to guide their input generation strategy (Zalewski, 2017). Since the release of AFL (Zalewski, 2017), the researchers have attempted to implement a wide range of mutation strategies augmented with program analysis to optimize the evolutionary mutation process (Böhme et al., 2017; Lemieux and Sen, 2018; You et al., 2019; You et al., 2018; Chen and Chen, 2018; Aschermann et al., 2019; Blazytko et al., 2019; Lemieux and Sen, 2018; Pham et al., 2019). All of these projects focus on manually designing different mutation strategies and use either program analysis (Chen and Chen, 2018; Aschermann et al., 2019; Blazytko et al., 2019) or aggregate statistics (Lemieux and Sen, 2018) to customize their strategy for specific target programs. By contrast, MTFuzz uses multi-task neural networks to automatically learn an compact representation of input to identify and mutate the hot-bytes.

More recently, machine learning techniques are being increasingly used to improve fuzzing. One line of work focused on using neural networks to model the input format of the target programs based on a corpus of sample inputs (Godefroid et al., 2017; Rajpal et al., 2017; Bastani et al., 2017; Böttinger et al., 2018; She et al., 2019b). Another alternative approach like Neuzz (She et al., 2019b) models the edge behaviour of a program using a neural network. In this paper, we demonstrate that neural networks can be further used to adaptively learn a number of mutation parameters that can significantly improve edge coverage.

Transfer learning (Pratt, 1992; Helleputte and Dupont, 2009; Silver and Bennett, 2008; Finn et al., 2015; Mihalkova et al., 2007) is beneficial when there is insufficient data for a target task but there exists sufficient data for other source task. To ensure ideal transfer, the target task and source task should have same or similar feature space and share similar data distribution. Raina et al. (Raina et al., 2006) and Dai et al. (Dai et al., 2007a) (Dai et al., 2007b) use transfer learning to perform cross-domain text classification. Long et al. (Long et al., 2015) and Sun and Saenko (Sun and Saenko, 2016) apply transfer learning to solve image-classification problem. We demonstrate that MTFuzz can transfer a NN learnt on one program to other similar programs.

Conclusion

This paper presents MTFuzz, a multi-task neural-network fuzzing framework. MTFuzz learns from multiple code coverage measures to reduce a sparse and high-dimensional input space to a compact representation. This compact representation is used to guide the fuzzer towards unexplored regions of the source code. Further, this compact representation can be transferred across programs that operate on the same input format. Our findings suggest MTFuzz can improve edge coverage significantly while discovering several previously unseen bugs.

Acknowledgements

This work is sponsored in part by NSF grants CNS-18- 42456, CNS-18-01426, CNS-16-17670, CNS-16-18771, CCF-16-19123, CCF-18-22965, CNS-19-46068, CCF 1845893, CNS 1842456, and CCF 1822965. This work is also sponsored by ONR grant N00014-17-1-2010; an ARL Young Investigator (YIP) award; a NSF CAREER award; a Google Faculty Fellowship; a Capital One Research Grant; and a J.P. Morgan Faculty Award. Any opinions, findings, conclusions, or recommendations expressed herein are those of the authors, and do not necessarily reflect those of the US Government, ONR, ARL, NSF, Google, Capital One or J.P. Morgan.

References