Testing Deep Neural Network (DNN) models has become more important than ever with the increasing usage of DNN models in safety-critical domains such as autonomous cars. Traditionally, DNN testing relies on the performance on a dedicated subset of the available data, namely test set. However, DNNs require more thorough testing approaches to exercise corner-case behaviors. Coverage-guided fuzzing (CGF) which is a common practice in software testing aims to produce new test inputs by mutating existing ones to achieve high coverage on a test adequacy criterion. CGF has been an effective method for finding error inducing inputs by satisfying a well-established criterion. In this paper, we propose a novel CGF algorithm for structural testing of DNNs. The proposed algorithm employs Monte Carlo Tree Search to drive the coverage-guided search. In our evaluation, we show that the inputs generated by our method result in higher coverage than the inputs produced by the previously introduced CGF techniques on various criteria in a fixed amount of time.
Given enough amount of data and processing power, training a Deep Neural Network (DNN) is the most popular way for dealing with many hard computational problems such as image classification [Cires¸an et al., 2012], natural language processing [Sutskever et al., 2014] and speech recognition [Hinton et al., 2012]. Impressive achievements in such tasks raised expectations for deploying DNNs in real-world applications, including the ones in safety-critical domains.
Despite the remarkable achievements, recent works [Szegedy et al., 2013; Goodfellow et al., 2015] have demonstrated that DNNs are vulnerable to small perturbations on seed inputs, also called adversarial attacks. Considering the Most of the work was done when the author was in Bog˘azic¸i Uni. Copyright c 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). catastrophic results that can emerge from erroneous behaviors in safety-critical systems, DNNs must be characterized by a high degree of dependability before being deployed in safety-critical systems.
Testing is the primary practice for analyzing and evaluating the quality of a software system [Ammann and Offutt, 2016]. It helps in reducing the risk by finding and eliminating erroneous behaviors before deployment of the systems. One of the most fundamental testing concepts is defining a coverage criterion for a given test set, also called a test adequacy criterion. A coverage criterion measures how much of the system structures are exercised (covered) when test inputs are provided. Having a test set that satisfies a coverage criterion provides a degree of dependability to the system under test.
Recent research in DNN testing introduces new DNNspecific coverage criteria such as neuron coverage [Pei et al., 2017] and its variants [Ma et al., 2018], MC/DC-inspired criterion [Sun et al., 2018b] or other criteria such as surprise adequacy [Kim et al., 2019] and DeepImportance [Gerasimou et al., 2020]. Previous works [Pei et al., 2017; Ma et al., 2018; Kim et al., 2019], and future studies on coverage criteria for DNNs could be useful for exposing defects in DNNs, finding adversarial examples, or forming diverse test sets. On the other hand, satisfying a coverage criterion or at least achieving a high coverage measurement can be difficult without a structured methodology. Existing works [Xie et al., 2018; Odena and Goodfellow, 2018] leverage coverage guided fuzzing (CGF) to achieve high coverage for a given criterion. However, both of these works apply mutations on inputs randomly. Therefore, their effectiveness is limited, as shown in our experiments.
In this work, we introduce DeepSmartFuzzer, a novel CGF, for achieving high coverage in DNNs for existing coverage criteria in the literature. Our ultimate goal is to help practitioners extend their test sets with new inputs so that new behaviours are covered. To that end, we leverage Monte Carlo Tree Search (MCTS) [Chaslot et al., 2008], a search algorithm for decision processes. In our method, MCTS is used to determine a series of mutations that would result in the best coverage increase for a given input.
We introduce DeepSmartFuzzer, a novel Coverage Guided Fuzzing (CGF) technique for testing DNNs. DeepSmartFuzzer is applicable to all existing coverage metrics.
We show the effectiveness of our method for many popular coverage criteria and for many DNNs with different complexities.
We compare the effectiveness our method with existing CGF methods. 2
Recently, several DNN testing techniques have been developed in the literature. Among these techniques, there exist works developing coverage criteria for DNNs. For example, DeepXplore [Pei et al., 2017] proposed neuron coverage (analogous to statement coverage in software). DeepGauge [Ma et al., 2018] proposed a set of fine-grained test coverage criteria. Kim et al. [2019] proposed surprise adequacy criteria based on a measure of surprise caused by the inputs and Gerasimou et al. [2020] presented a metric for composing a semantically diverse test set. Sun et al. [2018a] proposed the first concolic testing approach for DNNs.
We now discuss studies that are close to ours. TensorFuzz [Odena and Goodfellow, 2018] proposed the first CGF for neural networks that aims to increase a novel coverage metric. DeepHunter [Xie et al., 2018] is another work exploring CGF for DNNs by leveraging techniques from software fuzzing, such as power scheduling. Our work is different from TensorFuzz and DeepHunter where random mutations are applied on inputs whereas we employ Monte Carlo Tree Search (MCTS) for applying mutations on inputs. Also, we apply mutations on a small subset of features of a given input, whereas they apply mutations on all features of a given input. DeepSmartFuzzer is also similar to [Wicker et al., 2018] in that both works employ Monte Carlo Tree Search. However, the objective in [Wicker et al., 2018] is to find the nearest adversarial example, whereas our objective is to increase the value of a given coverage criterion.
Szegedy et al. [2013] first discovered the vulnerability of DNNs to adversarial attacks. Since then, numerous whitebox and black-box adversarial attacks have been proposed. The most popular attacks include FGSM [Goodfellow et al., 2015], JSMA [Papernot et al., 2016], PGD [Madry et al., 2017], and C&W [Carlini and Wagner, 2017]. 3
titions the input space into equivalence classes [Ammann and Offutt, 2016] and it is measured by dividing the number of equivalence classes that are sampled by at least one input in the test set to the number of all equivalence classes in the test set. For example, statement coverage in software measures the percentage of the statements in the program that are executed with the given set of test inputs.
Coverage Guided Fuzzing Coverage Guided Fuzzing (CGF) performs systematic mutations on inputs and produces new test inputs to increase the number of covered cases for a target coverage metric. A typical CGF process starts with selecting a seed input from the seed pool, then continues with mutating the selected seed a certain number of times. After that, the program under test is run with the mutated seed. If a mutated seed creates an increase in the number of covered cases, CGF keeps the mutated seed in the seed pool.
Search [Chaslot et al., 2008] is a search algorithm for decision processes such as game play. It represents games as trees where each node has children for each possible action to be taken. Each node of the game tree represents a particular state in the game. On taking an action, one makes a transition from a node to one of its children. MCTS algorithm aims to find the most promising action in an arbitrary state of a game. In other words, given an initial state, the objective is to find the best sequence of actions to win the game.
MCTS process can be broken down into the following four steps: Selection: Starting from the root node R, successively select child nodes according to their potentials until a leaf node L is reached. The potential of each child node is calculated by using UCT (Upper Confidence Bound applied to Trees) [Kocsis and Szepesva´ri, 2006; Chaslot et al., 2008]. UCT is defined as v + e q lnnN where v refers to the value of the node, n is the visit count of the node, and N is the visit count for the parent of the node. e is a hyperparameter determining exploration-exploitation trade-off. Expansion: Unless L is a terminal node (i.e. win/loss/draw), create at least one child node C (i.e. any valid action from node L) and take one of them. Simulation: play the game from node C by picking moves randomly until reaching a terminal condition. Backpropagation: propagate back the result of the play to update values associated with the nodes on the path from C to R. The path containing the nodes with the highest values in each layer would be the optimal strategy in the game. 4
Let T = f[X1; X2; :::]; [Y1; Y2; :::]g be a test set where (Xi; Yi) is an input-output pair of the ith test sample. Let I be a set of inputs called a batch. Let I0, I00, ..., I(n) be a sequence of mutated batches of the original batch I such that: I
IM(r0;m0) ! I
0 IM(r00;m0!0) I00::: IM(r(n);m(n!)) I(n) (1) where IM(r(n); m(n)) is the nth input mutation, r(n) and m(n) are the region and mutation indexes, respectively. Also, let Ibest 2 fI0; I00; :::g be the best batch that creates the greatest amount of coverage increase. 4.1
DeepSmartFuzzer is an MCTS-based coverage-guided fuzzer for DNNs. It can be classified as a grey-box testing method since it uses coverage information which is related to the internal states of a DNN model. Our method generates inputs that increase the current level of coverage formed by the initial test set. The core idea of our approach is to employ reward-guided exploration and exploitation in order to achieve high coverage scores. The workflow of the proposed method is illustrated in Figure 1. It is composed of an input chooser, a coverage criterion, an input mutator, and a mutation selector, which is the essential part.
For each iteration, the input chooser chooses a batch, which is a set of inputs I. Then, the mutation selector determines the mutation (r0; m0) to be applied to the inputs. Note that, applying one kind of mutation to all input features may be too coarse because, for a given mutation, a subset of input features may increase coverage while others may decrease coverage. Our fuzzer takes a finer approach and applies mutations to a subset of input features (i.e. regions) at each step. The input mutator takes the selected batch I and the selected mutation (r0; m0), where the selected mutation is applied to the selected batch of inputs such that the mutated inputs I0 are formed (I IM(r0;m!0) I0). The mutated inputs are then given to the coverage criterion to calculate the coverage of the mutated inputs together with the test set. The coverage and mutated inputs are given to the mutation selector such that it could use the coverage and continue working with I0 so that new mutated inputs I00 are generated (I0 IM(r00;m0!0) I00). This process continues until a termination condition such as exploration limit or mutation limit is reached. The best set of mutated inputs Ibest is stored and updated in the meantime. If there is an increase in coverage because of the mutated inputs Ibest, they are added to the test set. This concludes the iteration for the batch I. We continue iterating with different batches until a termination condition such as a target number of new inputs or timeout is reached. Now, we detail each component. 4.2
We use two types of input choosers for selecting inputs. These are random input chooser and clustered random input chooser. The random input chooser randomly samples a batch of inputs using the uniform random distribution. The clustered random input chooser samples similar inputs together. It applies an off-the-shelf clustering algorithm. After clustering, it selects a random cluster using the uniform random distribution. Finally, it samples a random batch of inputs from the selected cluster. We use sampling without replacement to avoid same inputs in a batch since we apply the same mutations to all inputs in the batch. In this work, we use k-means clustering as the clustering algorithm. 4.3
The mutation selector takes a batch of inputs and sequentially selects parameters region index r and mutation index m. The selected mutations are sequentially applied to the selected regions by the input mutator and a sequence of mutated batches I0; I00; :::; I(n-1); I(n) is generated. Note that I(n) contains all the mutations up to that point. This formulation of the problem has a sequential nature. Therefore, we decided to model the problem as a game, which consists of a sequence of actions and rewards related to the actions. We use a two-player game model since two selections (one for region and one for mutation) are made for each mutation.
Our proposed mutation selector is a two-player game such that Player I selects the region to be mutated, and Player II selects the mutation to be made on the chosen region. Since regions and mutations are enumerated, these are just integer selection problems. The game continues as Players I and II play iteratively so that multiple mutations could be applied on top of each other and a sequence of mutated batches is generated as described above. Region selection and mutation selection are considered as separate actions. We call a tuple of actions taken by Players I and II together as a complete action (r; m).
Reward A naive reward for our problem is the coverage increase for each action. We use this reward to guide the search for mutations. In this study, the coverage increase corresponds to the difference between the coverage for the current test set and the coverage obtained by adding a new batch to the test set. Overall, the purpose of the mutation selector is to find the best sequence of mutations that could result in the greatest amount of coverage increase.
End of the game In order to avoid creating unrealistic inputs and consequently human intervention to eliminate unrealistic inputs, we put constraints on mutations. Generally, Lp norms are used for this purpose. These are defined as jjXi0 Xijjp < where Xi0 is the mutated input such that the distance between mutated inputs and original inputs are limited. In general form, let d(X0; Xi) be a distance metric, i the game is over when d(Xi0; Xi) < constraint is violated, where d and are hyperparameters.
Searching We use Monte Carlo Tree Search (MCTS) in order to exploit rewards and guide the search for mutations towards rewarded mutations. For this purpose, MCTS searches the game tree for the best mutations. The nodes in our game tree correspond to region and mutation selections. We continuously update the batch of inputs Ibest that creates the best coverage increase so that the batch is added to the test set when MCTS is finished. The input mutator mutates the input according to the region index and mutation index selected by the mutation selector. The availability of so many mutations potentially makes the job of mutation selector harder.
Therefore, we come up with a 0 10 20 31 Igtendeivriadleisnpaunt immuatgaetoirnftoorloimcaalgrees-.
1 2 3 gions and provides general image 10 mutations as mutation options for each region. These general mu4 5 6 tations include, but are not lim20 ited to, brightness change, con7 8 9 trast change, and blur. When a 31 region r and a mutation m are selected, it applies the selected Figure 2: Regions mutation to the selected region.
The number of regions and the set of available mutations for regions are hyperparameters for the input mutator. With appropriate settings, we can obtain either a pixel-level mutator or an image-level mutator or something in-between, which we think is the best for practical reasons. We enumerate the regions and mutations so that the mutation selector identifies them by indexes. Figure 2 shows an example for the division of input into regions. Our proposed input mutator induces a bias towards locality since it applies mutations to regions of an image. Therefore, it is a natural fit for image problems and convolutional neural networks. 4.5
Algorithm 1 Algorithmic description of DeepSmartFuzzer 1: procedure DEEPSMARTFUZZER(T, tc0, tc1, tc2, tc3) 2: while not tc0 do 3: I = Input Chooser(T) 4: R = MCTS Node(I) 5: best cov, Ibest = 0, I 6: while not tc1 do 7: while not tc2 do 8: L = MCTS Selection(R) 9: C = MCTS Expansion(L) 10: (n-1) = get batch corresponding to node(C) 11: rI(n); m(n) = MCTS Simulation(C) 12: I(n) = Input Mutator(I(n-1), r(n); m(n)) 13: if not tc3 then 14: cov inc = Coverage(T [ I(n)) - Coverage(T) 15: if cov inc > best cov then 16: best cov, Ibest = cov inc, I(n) 17: 18: 19: 20: 21:
R = select child(R) if best cov > 0 then
T = T [ I best return T
We describe our method more formally in Algorithm 1. The while loop in line 2 refers to iterating until a termination condition (tc0) that is a timeout or reaching a target number of new inputs. In line 3, a batch of inputs I is sampled using the input chooser. The root node R is created in line 4, and variables to store the best mutated batch Ibest are initialized in line 5. The while loop in line 6 refers to looping until a termination condition (tc1) that limits the search space by limiting the number of levels in the search tree that the MCTS can search. Next, the while loop in line 7 refers to iterating until a termination condition (tc2) that determines the number of times the subtree of the root node R will be explored. In line 8, MCTS Selection, which is selection of a path from the root node R to a leaf node L using the potentials (calculated by using UCT) of the nodes, is made and it results in a leaf node L. Then, in line 9, MCTS Expansion is applied and it creates a new child node C as a child of the leaf node L. In line 10, the mutations formed by the path from the root node of the game tree to the given node C are applied to the initial batch I and it results in I(n-1). Basically, I(n-1) is the mutated batch that is the result of MCTS Selection and Expansion. Then, MCTS Simulation plays the game until a complete action so that r(n) and m(n) are assigned to a region index and a mutation index, respectively (line 11). Our MCTS Simulation is different than the original MCTS Simulation. Instead of playing the game randomly until the end, our MCTS Simulation plays the game randomly until a complete action since our game formulation produces a reward for every complete action. The input mutator then mutates the batch I(n-1) according to a region index r(n) and a mutation index m(n) so that a new batch I(n) is created (line 12). Termination condition (tc3) controls the rationality of the generated batch by limiting the distance between the mutated batch I(n) and the original batch I. If this new batch I(n) does not violate the termination condition (tc3), then the mutated batch I(n) is considered a candidate batch of test inputs (line 13-14). In line 15, coverage increase is calculated from the difference between the coverage of test set T together with the mutated batch I(n) and the test set T . If this is the greatest coverage increase for this batch I, the mutated batch I(n) is stored as the best mutated batch Ibest (line 15-16). MCTS Backpropagation is applied from the new child node C with coverage increase as reward (line 17). This concludes one iteration of the while loop with tc2, and the algorithm continues looping to explore the root node until tc2. When termination condition tc2 is reached, it sets the best child of root R as the new root node (line 18). The best child is the node with the greatest value, which is the average coverage increase (reward) found on the paths (sequences of mutations) that contain the node. After setting a child as the new root, an iteration of the while loop with tc1 is completed, and the while loop continues iterating by working on the subtree of the child node (now called as the root node R). After the while loop is completely finished, the best batch found Ibest is added to the test set if it creates a coverage increase (line 19-20). Here, we add the complete batch to the test set in order to avoid the search for the effective inputs in the batch and thereby speed up the process. This concludes a complete iteration of MCTS on the batch I and the algorithm continues iterating with new batches until termination condition tc0 is reached. When tc0 is reached, the final test set which includes the mutated inputs found up to that point is returned (line 21).
...
... ... ... ... ...
region 4
... mutation 16
... region 5
... mutation 4
... (a) The game tree (b) The selected mutations on a seed input
Experiments2
Datasets and DL Systems We evaluate DeepSmartFuzzer on two popular publicly available datasets namely MNIST [LeCun, 1998] and CIFAR10 [Krizhevsky and Hinton, 2009] (referred to as CIFAR from now on). MNIST is a handwritten digit dataset with 60000 training and 10000 testing inputs. Each input is a 28x28 pixel white and black image with a class label from 0 to 9. CIFAR is a 3-channel colored image dataset with 50000 training and 10000 testing samples. Each input is a 3x32x32 image in ten different classes (e.g., plane, ship, car). For the MNIST dataset, we study LeNet1, LeNet4, and LeNet5 [LeCun et al., 1998] DNN architectures, which are the three well-known and popular models in the literature. For the CIFAR dataset, we make use of a suggested convolutional neural network architecture [Wicker et al., 2018].
marks We evaluate our tool by comparing its performance with two existing CGF frameworks for deep learning systems. The first tool, namely DeepHunter [Xie et al., 2018], aims to achieve high coverage by randomly selecting a batch of inputs and applying random mutations on them. DeepHunter also leverages various fuzzing techniques from software testing, such as power scheduling. However, the tool is not publicly available. Therefore we use our implementation of DeepHunter in evaluation. The second tool, namely Tensorfuzz [Odena and Goodfellow, 2018], uses the guidance of coverage to debug DNNs. For example, it finds numerical errors and disagreements between neural networks and quantized versions of those networks. Tensorfuzz code is publicly available, and we integrate it into our framework.
For an unbiased evaluation of DeepSmartFuzzer, we test our tool on various coverage criteria. We use DeepXplore’s 2Source code: https://github.com/hasanferit/DeepSmartFuzzer [Pei et al., 2017] neuron coverage (NC), DeepGauge’s [Ma et al., 2018] k-multisection neuron coverage (KMN), neuron boundary coverage (NBC), strong neuron activation coverage (SNAC) and Tensorfuzz’s coverage (TFC).
Hyperparamters We set neuron activation threshold to 0:75 in NC and the number of sections k to 10000 in KMN, respectively. For NBC and SNAC, we set as lower (upper) bound the minimum (maximum) activation value encountered in the training set, respectively. These are the recommended settings in the original studies. On the other hand, we observed that the distance threshold used in the original TensorFuzz study was too small for MNIST and CIFAR models such that every little mutation could increase the coverage. Therefore, we tune the threshold of TFC for LeNet1, LeNet4, LeNet5 and CIFAR CNN as 302, 132, 112 and 32, respectively.
The number of regions, the set of mutations, and termination conditions (tc1, tc2, tc3) constitute the hyperparameters of DeepSmartFuzzer. The number of regions is selected as 9, which corresponds to 3 3 division of an image. The set of mutations is contrast change, brightness change, and blur. The first termination conditions (tc1) is chosen to limit MCTS from going down more than 8 levels deep in the game tree. The second termination condition (tc2) limits the number of iterations on each root to 25. For the last termination condition (tc3), we use the limitations that DeepHunter [Xie et al., 2018] puts on the distance between mutated and seed inputs to avoid unrealistic mutated inputs.
Summary We aim to show that DeepSmartFuzzer is able to generate good test inputs. First, we compare DeepSmartFuzzer with DeepHunter and TensorFuzz by comparing the coverage increases created by approximately 1000 new inputs for each method in combination with different DNN models and coverage criteria. Experimental results in Table 1 and 3 show that the inputs generated by our method result in the greatest amount of coverage increase for all (DNN model, coverage criterion) pairs except for a few. This suggests that DeepSmartFuzzer creates better test inputs than DeepHunter and TensorFuzz with regards to the coverage measurements. experiments with 6 hours limit for timeout ments with 6, 12, 24 hours limits for timeout puts created by DeepSmartFuzzer.
We focus on the inputs generated by DeepSmartFuzzer, DeepHunter, and Tensorfuzz. For experimental integrity, we make each method generate approximately 1000 input samples. Only the inputs which induce coverage increase are taken into account. We also put a time limit in order to avoid unending cases resulting from being unable to find any coverage increase for some (DNN model, coverage criteria) pairs. When a method could not produce the target amount of inputs in time, yet it creates some coverage increase such that it shows more potential to be explored, the timeout limit is extended so that they could reach 1000 inputs. This condition is not applied to TensorFuzz since it generates inputs one by one, and therefore, it could practically take days to reach 1000 inputs for some cases. The timeout is set to be 2 hours initially. It is then gradually increased to 6, 12, and 24 hours to explore the full potential. Tables 1 and 3 show the amounts of coverage increase produced by approximately 1000 generated input samples from each method with divergent set of coverage criteria and DNN models for MNIST and CIFAR datasets. In order to provide complete results, Tables 2 and 4 indicate exactly how many inputs are generated for each case. All of these results are given as mean and standard deviation of the population resulting from running the same experiment three times with different random seeds.
For most of the cases, DeepSmartFuzzer is better than the other two. Especially for the case of TFC, DeepSmartFuzzer provides a substantial improvement over DeepHunter and TensorFuzz. This might be related to TFC being a layerlevel coverage criterion, while the others are neuron-level coverage criteria. Our solution gets better when model complexity is increased. This is suggested by the increasing performance gap between our method and the others. Furthermore, DeepSmartFuzzer with clustering tends to be better than naive DeepSmartFuzzer when the complexity of the model is increased.
On the other hand, for a few cases, our approach fails to provide an improvement. For example, in neuron coverage (NC) with LeNet1 model case, we observe that all fuzzers fail to generate any coverage-increasing input. This is because when we cannot find any reward (i.e. coverage increase), our MCTS solution is similar to a random search. However, we believe this problem can be avoided with a well-designed reward shaping, and this is left to future work. Also, for the case of LeNet4 in combination with NBC, DeepHunter seems to be better than ours. This may indicate a need for further hyperparameter tuning since it conflicts with the general trend.
In order to check the statistical significance of the results, we apply one-tailed t-test. We check two hypotheses which are whether DeepSmartFuzzer is better than Tensorfuzz and whether DeepSmartFuzzer is better than DeepHunter in terms of coverage increase. For the statistical comparisons, we use all 60 experiments (with different models and different coverage criteria) for each CGF method as observations. The significance threshold is set at .05. We find P<.001 for the former hypothesis and P=.007 for the latter hypothesis. Therefore, we accept the hypotheses.
6
In this study, we introduce a novel Coverage Guided Fuzzing (CGF) technique for DNNs that uses Monte Carlo Tree Search (MCTS) to explore and exploit the coverage increase patterns. We experimentally show that our method is better than previous CGFs for DNNs in terms of satisfying subject coverage criteria. Our results also show that MCTS methods can be promising for better DNN testing. We use naive coverage increase as reward. Therefore, experimentation with reward shaping and different reinforcement learning methods for this problem are left for future studies. Finally, we share the source code regarding to our experiments and implementation publicly in order to provide a base for future studies.
This research was supported in part by Semiconductor Research Corporation under task 2020-AH-2970.