DeepGD: A Multi-Objective Black-Box Test Selection Approach for Deep
  Neural Networks
Deep neural networks (DNNs) are widely used in various application domains
such as image processing, speech recognition, and natural language processing.
However, testing DNN models may be challenging due to the complexity and size
of their input domain. Particularly, testing DNN models often requires
generating or exploring large unlabeled datasets. In practice, DNN test
oracles, which identify the correct outputs for inputs, often require expensive
manual effort to label test data, possibly involving multiple experts to ensure
labeling correctness. In this paper, we propose DeepGD, a black-box
multi-objective test selection approach for DNN models. It reduces the cost of
labeling by prioritizing the selection of test inputs with high fault revealing
power from large unlabeled datasets. DeepGD not only selects test inputs with
high uncertainty scores to trigger as many mispredicted inputs as possible but
also maximizes the probability of revealing distinct faults in the DNN model by
selecting diverse mispredicted inputs. The experimental results conducted on
four widely used datasets and five DNN models show that in terms of
fault-revealing ability: (1) White-box, coverage-based approaches fare poorly,
(2) DeepGD outperforms existing black-box test selection approaches in terms of
fault detection, and (3) DeepGD also leads to better guidance for DNN model
retraining when using selected inputs to augment the training set.
Zohreh Aghababaeyan, Manel Abdellatif, Mahboubeh Dadkhah, Lionel Briand
# DeepGD: A Multi-Objective Black-Box Test Selection Approach for Deep Neural Networks

###### Abstract.

Deep neural networks (DNNs) are widely used in various application domains such as image processing, speech recognition, and natural language processing. However, testing DNN models may be challenging due to the complexity and size of their input domain. Particularly, testing DNN models often requires generating or exploring large unlabeled datasets. In practice, DNN test oracles, which identify the correct outputs for inputs, often require expensive manual effort to label test data, possibly involving multiple experts to ensure labeling correctness.

In this paper, we propose _DeepGD_, a black-box multi-objective test selection approach for DNN models. It reduces the cost of labeling by prioritizing the selection of test inputs with high fault-revealing power from large unlabeled datasets. _DeepGD_ not only selects test inputs with high uncertainty scores to trigger as many mispredicted inputs as possible but also maximizes the probability of revealing distinct faults in the DNN model by selecting diverse mispredicted inputs.

The experimental results conducted on four widely used datasets and five DNN models show that in terms of fault-revealing ability: (1) White-box, coverage-based approaches fare poorly, (2) _DeepGD_ outperforms existing black-box test selection approaches in terms of fault detection, and (3) _DeepGD_ also leads to better guidance for DNN model retraining when using selected inputs to augment the training set.

Deep Neural Network, Test Selection, Diversity, Uncertainty, Faults.

## 1. Introduction

Deep Neural Networks (DNNs) have become widely used in a variety of application areas, including image processing (Abadi et al., 2016), medical diagnostics (Bahdan et al., 2017), and autonomous driving (Bahdan et al., 2017). However, DNNs may produce unexpected or incorrect results that could lead to significant negative consequences or losses. Therefore, effective testing of such models is crucial to ensure their reliability (Bahdan et al., 2017). For testing and enhancing the performance of DNN-driven applications, a significant amount of labeled data is required. However, obtaining the correct output labels for a large amount of unlabeled data, referred to as oracle information, can be a challenging and resource-intensive task (Bahdan et al., 2017). This process often requires extensive manual efforts by domain experts and can be a significant challenge when resources are limited. This makes it difficult to effectively test and improve the performance of DNN models. In order to address these challenges and make DNN testing feasible and cost-effective in practice, it is essential to select a small subset of test inputs that possess a high fault-revealing power. This approach reduces the number of inputs required for DNN testing, making it more cost-effective.

Several test selection approaches for DNN models have been proposed in recent years (Bahdan et al., 2017; Wang et al., 2018; Wang et al., 2019; Wang et al.
terms of fault-revealing power and computational time. However, they did not study how such a metric can be used for DNNs test selection.

In this paper, we propose _DeepGD_, a black-box multi-objective search-based test selection approach. It relies on the Non-dominated Sorting Genetic Algorithm (NSGA-II) (Shi et al., 2017) to select test inputs that aim at revealing a maximal number of diverse faults in DNN models within a limited testing budget. _DeepGD_ prioritizes selecting a subset of test inputs with high fault-revealing power from a large unlabeled dataset. The main objectives of _DeepGD_ are twofold: (1) trigger as many mispredicted inputs as possible by selecting inputs with high uncertainty scores, and (2) maximize the probability of revealing distinct faults in the DNN model by selecting diverse mispredicted inputs. Such an approach alleviates the lack of effectiveness of existing techniques relying exclusively on model output uncertainty scores when used on insufficiently trained DNNs.

Similar to failures in traditional software systems, many mispredictions result from the same faults in the DNN model and are therefore redundant (Shi et al., 2017; Shi et al., 2017). This is why testing studies typically focus on faults, not failures (Shi et al., 2017; Shi et al., 2017). Detecting faults in DNNs is however not as straightforward as in traditional software and it is a challenging task to find the root cause of mispredictions. To validate the effectiveness of _DeepGD_, we use a fault estimation approach proposed by Aghababevan _et al._(Aghababevan et al., 2017) which is based on clustering mispredicted inputs (Shi et al., 2017). Each cluster represents a distinct fault in the DNN model since it embeds similar inputs that are mispredicted due to the same root causes.

In this paper, we present an empirical evaluation of the effectiveness of _DeepGD_ for selecting test input sets with high fault-revealing power using five widely-used DNN models and four image recognition datasets. The results are compared with nine SOTA baseline approaches, both white-box and black-box, that have been recently published. The experimental results demonstrate that _DeepGD_ shows a statistically significant and consistent improvement compared to SOTA approaches in terms of its ability to reveal DNNs faults.

Specifically, results show that _DeepGD_ is consistently the best approach and up to 6 percentage points (pp) better than the second-best alternative, and 13 pp better than the worst black-box alternative, when excluding random selection (RS) since RS showed far inferior results in general. It is important to note that the ranking of alternatives vary across datasets, models, and test set sizes. Consequently, selecting any approach other than DeepGD may end up being the worst choice and lead to significant differences in performance. Further, we also investigate the effectiveness of _DeepGD_ in guiding the retraining of DNNs and demonstrate that it consistently provides better results with that respect. _DeepGD_ is therefore the only technique we can confidently recommend. To summarize, the key contributions of this paper are as follows:

* We propose a black-box test selection approach (_DeepGD_) for DNNs that relies on a customized multi-objective genetic search and uses both diversity and uncertainty scores to guide the search toward finding test input sets with high fault-revealing power.
* Unlike existing test selection approaches, we consider in our validation a clustering-based approach to estimate faults in DNN models since test input sets typically contain many similar mispredicted inputs caused by the same problems in the model (Shi et al., 2017; Shi et al., 2017). We explain why this is important to evaluate any test set selection approach based on faults.
* We conduct a large-scale empirical evaluation to validate _DeepGD_ by considering five DNN models, four different datasets, and nine SOTA test selection approaches for DNNs as baselines of comparison. We show that _DeepGD_ provides better guidance than baselines for (1) selecting inputs with high fault-revealing power, and (2) improving the performance of the model through retraining based on an augmented training set.

## 2. Approach: Reformulation as an NSGA-II Search Problem

A central problem in testing DNNs, especially when the labeling of test data is costly, is the selection of a small set of test inputs with high fault revealing power. In this paper, we aim to support the testing of DNN models by relying on _DeepGD_, a black-box search-based test selection approach using a genetic algorithm to select small sets of test inputs with high fault-revealing power in DNN models. Intuitively, testers should select a set of diverse test inputs with high failure probabilities in order to be more likely to detect as many diverse faults as possible (Shi et al., 2017). Due to the combined high labeling cost of test inputs and large input space, we rely on NSGA-II to select test inputs with high fault-revealing capability. Such inputs are then selected for labeling and will be used to effectively test the DNN model. We choose NSGA-II since it is widely used in the literature and showed its performance to solve many search-based test selection problems (Shi et al., 2017; Shi et al., 2017). We also rely on NSGA-II since it is specifically adapted to our multi-objective search problem. It tries to find solutions with diverse trade-offs between fitness functions instead of covering all fitness functions separately (which is the case of MOSA, the many objective sorting algorithm (Shi et al., 2017) for example). Specifically, the search is driven by two objectives: (1) maximizing the uncertainty score of the test inputs to trigger a maximum number of mispredictions, and (2) maximizing the diversity of the test input set to trigger diverse mispredictions caused by distinct faults. To properly translate the process into a search problem using NSGA-II, we need to define the following elements.

### Individuals and Initial Population

In genetic algorithms, individuals consist of a set of elements called genes. These genes are connected and form an individual that is also called a solution. In our approach, we assign a unique identifier \(id_{i}\) to each input \(i\) in the test dataset where \(id_{1\leq i\leq n}\in[1,2,..,n]\) and \(n\) is the size of the test dataset. Our test selection problem has a fixed budget \(\beta<n\) which corresponds to the total number of inputs selected from the original test dataset to test the DNN model. In our search problem, an individual, therefore, corresponds to a subset of inputs of size \(\beta\). Each gene forming an individual corresponds to an \(id\) of a test input in the test dataset. In our context, each individual contains \(\beta\) distinct test inputs. We use random selection to build our initial population of individuals.
### Fitness Functions

Our search is guided by two fitness functions: (1) maximizing the uncertainty score of the selected inputs to trigger as many mispredicted inputs as possible, and (2) maximizing the diversity of the selected inputs to maximize the probability of revealing distinct faults in the DNN model. We will describe next the two fitness functions and detail how to compute them.

#### 2.2.1. **Gini Score**

We consider the _Gini_ score to estimate the likelihood of a test input being mispredicted. Feng _et al._[20] proposed this metric to measure the classification uncertainty of DNN models and therefore identify potential failing test inputs. Intuitively, a test input is likely to be misclassified by a DNN if the model is uncertain about the classification and outputs similar probabilities for each class [20]. We choose this metric since it has been widely used in the literature and showed good performance in prioritizing test inputs for DNN models [20; 34]. It is also a black-box metric that only requires the output probabilities of DNN models as we will describe in the following. Given a test input \(x\) and a DNN model that outputs \(DNN(x)=<P_{x_{1}},P_{x_{2}},...,P_{x_{m}}>\), where \(P_{x_{1\leq i\leq m}}\) is the probability that input \(x\) belongs to class \(C_{i}\) and \(m\) is the total number of classes, the _Gini_ score of the test input \(x\) is defined as:

\[\zeta(x)=1-\sum_{i=1}^{m}P_{x_{i}}^{2} \tag{1}\]

The higher the _Gini_ score, the higher the DNN's uncertainty. We compute the _Gini_ score of a subset \(S=\{s_{1},s_{2},....,s_{g}\}\) of size \(\beta\) by computing the average _Gini_ score of all inputs in the subset as follow:

\[Gini(S)=\frac{\sum_{i=1}^{\beta}\zeta(s_{i})}{\beta} \tag{2}\]

#### 2.2.2. **Geometric Diversity**

We consider geometric diversity (GD), one of the widely used metrics to measure the diversity of test input sets [16; 25; 35]. In a recent study, Aghababeyan _et al._[16] investigated several coverage and diversity metrics and found that the GD metric is positively correlated to DNN faults and outperforms SOTA coverage metrics in terms of fault-revealing capabilities. In other words, when the geometric diversity of a test input set increases, its fault-revealing power increases as well since the diverse test input set will cover more faults in the DNN model. Furthermore, GD is a black-box diversity metric that requires neither knowledge about the model under test nor access to the training set. Consequently, we have relied on this metric as a second fitness function to guide the search towards finding a diverse test input set with high fault-revealing capability.

**Feature Extraction**. In order for diversity to account for the content of images, we need to first extract features from each input image and then compute the diversity based on those extracted features. In our work, we use VGG-16 [36], one of the SOTA feature extraction models. VGG-16 is a pretrained convolutional neural network model which was already trained on ImageNet [37], a huge dataset including over 14 million labeled images. As a result, it has learned rich feature representations for a wide range of images and datasets [36]. We extract features of each image in the test input set \(S\) using VGG-16 and generate the corresponding feature matrix \(F=(f_{ij})\in R^{nsm}\) where \(n\) is the number of input images in \(S\), and \(m\) is the number of features. Each row of this matrix represents the feature vector of an image, and each column \((F_{j})\) represents a feature. Next, we normalize the matrix as a pre-processing step to eliminate the dominance effect of features with large value ranges and to make the computation of the selected diversity metrics more scalable [16]. We apply the _Min-Max normalization_ per feature, and transform the maximum and minimum values of that feature to one and zero, respectively. For every feature \(F_{j}\) in the feature matrix \(F\) where \(F_{j}(i)\) is the value of feature number \(j\) for \(i^{th}\) input image in the \(S\), the normalized feature \(F_{j}^{\prime}\) is calculated as follows:

\[F_{j}^{\prime}(i)=\frac{F_{j}(i)-min(F_{j})}{max(F_{j})-min(F_{j})} \tag{3}\]

**Computation of geometric diversity scores.** After extracting the feature vectors, we calculate the geometric diversity of the test inputs as our second fitness function with the goal of selecting as much diverse test input sets as possible. Given a dataset \(\mathbb{D}\), the normalized feature matrix \(F^{\prime}\) where \(F_{S}^{\prime}\) represents feature vectors of a subset \(S\subseteq\mathbb{D}\), the geometric diversity of \(S\) is defined as:

\[GD(S)=det(F_{S}^{\prime}*F_{S}^{\prime T}) \tag{4}\]

which corresponds to the squared volume of the parallelepiped spanned by the rows of \(F_{S}^{\prime}\), since they correspond to vectors in the feature space. The larger the volume, the more diverse is \(S\) in the feature space as depicted in Figure 1.

#### 2.2.3. **Multi-Objective Search**

We need to maximize in our search the two aforementioned fitness functions to increase the fault-revealing capability of the selected test input set. This is therefore a multi-objective search problem that can be formalized as follows:

\[\underset{S\subset\mathbb{D}}{max}\ Fitness(S)=(Gini(S),GD(S)) \tag{5}\]

where \(\mathbb{D}\) is the test dataset, \(S\) is a subset of test inputs of size \(\beta\), function \(\mathit{Fitness}:S\rightarrow\mathbf{R}^{2}\) consists of two real-value objective functions \((Gini(S),GD(S))\), and \(\mathbf{R}^{2}\) is the objective space of our optimization problem.

### Genetic Operators

We describe below the two genetic operators in our test selection approach. The first operator is crossover, which generates new offspring by cutting and joining high-fitness parents. The second operator is mutation which introduces small changes in individuals by mutating specific genes to (1) make the search more exploratory and (2) thus attempt to increase the uncertainty score and the diversity among individuals in the population. We provide below a

Figure 1. Illustration of the geometric diversity metric [16]
detailed description of how we customized these genetic operators to fit our test selection problem.

#### 2.3.1. **Crossover**

The crossover operator takes as input two parents (i.e., two subsets) and generates new offspring by slicing and joining the different parts of the selected parents. Let \(S_{1}\) and \(S_{2}\) be the two selected parents for crossover. We give in the following an example of selected parents:

\[S_{1}=\{\mathit{Input}_{1},\mathit{Input}_{2},\mathit{Input}_{3},\cdots, \mathit{Input}_{1}^{\mathit{a_{1}}},\cdots,\mathit{Input}_{4},\mathit{Input}_{5}\}\]

\[S_{2}=\{\mathit{Input}_{0},\mathit{Input}_{7},\mathit{Input}_{8},\cdots, \mathit{Input}_{1}^{\mathit{a_{2}}},\cdots,\mathit{Input}_{9},\mathit{Input}_{10}\}\]

where \(\mathit{Input}_{i}^{\mathit{a_{1}}}\) and \(\mathit{Input}_{i}^{\mathit{a_{2}}}\) correspond to the \(i^{th}\) input in \(S_{1}\) and \(S_{2}\), respectively. Before applying the crossover operator, we start by sorting the inputs forming each parent according to their _Gini_ scores. Inputs with higher _Gini_ scores are placed at the beginning of each corresponding parent, as in the example below.

\[S_{1}=\{\mathit{Input}_{3},\mathit{Input}_{1},\mathit{Input}_{5},\cdots, \mathit{Input}_{1}^{\mathit{a_{1}}},\cdots,\mathit{Input}_{4},\mathit{Input}_{ 2}\}\]

\[S_{2}=\{\mathit{Input}_{7},\mathit{Input}_{10},\mathit{Input}_{6},\cdots, \mathit{Input}_{1}^{\mathit{a_{2}}},\cdots,\mathit{Input}_{9},\mathit{Input}_{ 8}\}\]

Such reordering will help with the creation of potential high-fitness offspring with high uncertainty scores as we will explain in the following. After such sorting, we randomly select a crossover point using the uniform distribution. To form the first offspring, we slice and join the first parts of each parent based on the crossover point. Such offspring includes inputs with the highest _Gini_ scores thanks to sorting. Finally, the second offspring is formed by joining the remaining parts of the selected parents. Since this offspring has inputs with the lowest _Gini_ scores from both parents, it will be potentially discarded later by the selection operator or improved by the mutation operator as we will detail in the next section. Assuming that the crossover point is at position \(i\) in the example above, the generated offspring would be:

\[\mathit{Offspring}_{1}=\{\mathit{Input}_{3},\mathit{Input}_{1},\cdots, \mathit{Input}_{1}^{\mathit{a_{1}}},\mathit{Input}_{7},\mathit{Input}_{10}, \cdots,\mathit{Input}_{a_{-1}^{\mathit{a_{2}}}}\}\]

\[\mathit{Offspring}_{2}=\{\mathit{Input}_{i+1}^{\mathit{a_{1}}},\cdots, \mathit{Input}_{4},\mathit{Input}_{2},\mathit{Input}_{a_{-1}^{\mathit{a_{2}}},\cdots,\mathit{Input}_{9},\mathit{Input}_{8}}\}\]

However, applying the crossover on the selected parents may lead to redundant inputs in the created offspring. Since one of our search goals is to maximize the diversity of the selected subsets, we remove redundant inputs (and therefore increase the diversity of the offspring) by replacing them with random inputs that are not present in the created offspring.

#### Mutation

After completing the crossover, the offspring are selected for mutation to randomly change some genes that have (1) a low _Gini_ score, and (2) a low contribution to the diversity of the selected offspring. Therefore, the mutation operator is considered in our search approach as a corrective operator with the goal of improving the offspring in terms of both fitness functions. As an example, let us assume that \(S_{m}\) is the test input set to mutate. We select 2% of the inputs from \(S_{m}\) that have the lowest _Gini_ score. We mutate half of these inputs that have the least contribution to the diversity of \(S_{m}\). Consequently, only 1% of its genes are mutated. To measure the contribution of an \(\mathit{input}_{i}\) to increasing the diversity in \(S_{m}\), we measure the difference \(\mathit{GD}_{\mathit{diff}}(S_{m},i)\) between \(\mathit{GD}(S_{m})\) and \(\mathit{GD}(S_{m}\setminus\{\mathit{input}_{i}\})\). The lower the difference, the more similar the input compared to the other ones in \(S_{m}\). Inputs with low differences should therefore be mutated to accelerate our search process.

An example of offspring generated through mutation is provided below. \(S_{m}\) is the original offspring and \(S_{m}^{\prime}\) is the mutated one. Suppose that \(S_{m}\) has 10 genes. We mutate \(\mathit{Input}_{1}\) since it has a low _Gini_ score and a low contribution to the diversity of the selected offspring.

\[S_{m}:\quad\mathit{Input}_{3}\quad\mathit{Input}_{1}\quad\mathit{Input}_{5} \quad\cdots\quad\mathit{Input}_{7}\quad\mathit{Input}_{10}\]

\[\mathit{Gini}:\quad\mathit{Input}_{70}\quad\quad\quad\quad\quad\quad\quad \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \quad
mutation rate in the literature is proportional to the length of the individual (Srivastava et al., 2016; Wang et al., 2017; Wang et al., 2018), we have not used such a rate since we used mutation for a different purpose than just exploration, i.e., to help increase both uncertainty and diversity scores. According to our preliminary experiments (which we do not include in this paper), smaller recommended mutation rates led to poorer search results. The population size is set to 700 individuals. Finally, the stopping criterion is set to 300 generations. We should note that the number of generations was determined through empirical evaluation. This was done by monitoring the evolution of fitness functions over multiple generations using various datasets and models. The maximum number of generations was carefully selected to ensure the convergence of the search process. In this paper, we also modified the traditional NSGA-II algorithm by customizing its fundamental operators, as described above. Specifically, we introduced a novel crossover function and mutation operator. Preliminary empirical results showed that the modified NSGA-II outperformed the traditional version, as evidenced by higher Gini and diversity scores, and a faster convergence rate. Finally, we used Google Colab and the Pymoo library (Pymoo, 2017) to implement our genetic search.

## 3. Empirical Evaluation

This section describes the empirical evaluation of _DeepGD_, including the research questions we address, the datasets and DNN models on which we perform our assessments, our experiments, and results.

### Research Questions

Our empirical evaluation is designed to answer the following research questions.

**RQ1. Do we find more faults than existing test selection approaches with the same testing budget?** Similar to traditional software testing, selecting a subset of test inputs with high fault-revealing ability is highly important in DNN testing, as it should increase the effectiveness of the testing process while reducing input labeling costs. Consequently, we aim in this research question to compare the effectiveness of our approach (_DeepGD_) with existing baselines in terms of their ability to reveal faults in DNNs, while considering the same testing budget. Identifying the source of failures in traditional software systems is relatively straightforward due to the clear and explicit decision logic in the code. However, in DNNs, this task is more challenging as the complexity and non-linearity of the decision-making process make it difficult to determine the cause of the failure. Hence, many papers rely on mispredictions (Beng et al., 2016; Wang et al., 2018; Wang et al., 2018) for test selection evaluation. However, similar to failures in traditional software systems, many mispredicted inputs can be due to the same faults in the DNN model and are therefore redundant (Wang et al., 2018; Wang et al., 2018). When selecting inputs on a limited budget, we should therefore avoid similar or redundant mispredictions as they do not help reveal additional root causes or faults in DNN models. To accurately answer this research question, we thus rely on a clustering-based fault estimation approach (Wang et al., 2018) that we describe in section 3.2, to investigate the effectiveness of the test selection approaches in detecting faults for a fixed testing budget.

**RQ2. Do we more effectively guide the retraining of DNN models with our selected inputs than with baselines?** Retaining DNN models with unseen inputs carefully selected based on DNN testing results is expected to enhance the model's performance compared to that of the original training set. More specifically, it is highly recommended to retrain DNNs with inputs that have the potential to lead to mispredictions (Wang et al., 2018; Wang et al., 2018; Wang et al., 2018). Consequently, we aim in this research question to investigate the effectiveness of _DeepGD_ in guiding the retraining of DNN models by selecting inputs that will be labeled and used to improve the model through retraining. We will not only measure the accuracy improvement resulting from retraining but also analyze it considering the maximum improvement possible based on the available data for retraining.

### Estimating Faults in DNNs

Before addressing our research questions, one essential issue is how to count faults in DNN models. The motivation for counting faults rather than mispredictions, when evaluating selection techniques, stems from our objective of detecting different root causes for the latter. According to Chan et al. (Chan et al., 2017) for traditional software testing, failure-causing inputs tend to be dense and close together. The same insight applies to DNN model testing, since similar mispredicted inputs tend to be due to the same fault (Wang et al., 2018; Wang et al., 2018). Our goal is to devise a test selection method that is not only capable of detecting more mispredicted inputs but also diverse ones in terms of root causes.

We estimate faults in a DNN by clustering mispredicted inputs using the approach of Aghababaeyan _et al_(Aghababaeyan et al., 2018). They proposed a clustering-based fault estimation approach consisting of four main steps: feature extraction, dimensionality reduction, clustering, and evaluation. The first step relies on VGG-16 to extract the feature matrix of the mispredicted inputs (Wang et al., 2018). Then, two extra features that are actual and mispredicted classes related to each input are added to the feature matrix. This information about the misprediction behavior of the model under test helps build better clusters to reflect common causes of mispredictions.

In the next step, dimensionality reduction techniques boost the performance of clustering given the high dimensional feature space. HDBSCAN (Dong et al., 2016) is then applied to cluster mispredicted inputs based on the resulting features. Final clusters are investigated with SOTA clustering evaluation metrics and through manual analysis. Empirical results show that (1) inputs in the same cluster tend to be mispredicted due to the same fault, and (2) inputs belonging to different clusters are mispredicted because of distinct faults (Wang et al., 2018).

### Subject Datasets and Models

Table 1 shows the combinations of datasets and models that we have used in our experiments. We should note that we have considered the most used combinations of datasets and models in the literature. We consider four widely used image recognition datasets which are Cifar-10 (Cifar-10), MNIST (Cifar-10), Fashion-MNIST (Cifar-10) and SVHN (Dong et al., 2016). We use these datasets with five SOTA DNN models: LeNet1, LeNet4, LeNet5, 12 layers Convolutional Neural Network (12-layer ConvNet) and ResNet20.

We have selected datasets and models that are widely used by SOTA test selection approaches (Beng et al., 2016; Wang et al., 2018; Wang et al., 2018). Moreover, each input
in the provided datasets has proper labeling. Finally, because they provide a variety of distinct inputs (in terms of classes and domain concepts) and different models (in terms of internal architecture), these datasets and models are regarded as a good benchmark for observing key trends in DNN test selection.

### Baseline Approaches

We compare _DeepGD_ with two categories of baseline approaches: (1) four white-box test selection approaches including three well-known coverage-based approaches (Beng et al., 2015), along with Likelihood-based Surprise Adequacy (LSA) and Density-based Surprise Adequacy (DSA) (Dai et al., 2017), and (2) four SOTA black-box prioritization approaches including Maximum Probability (MaxP) (Krause et al., 2017), DeepGini (Li et al., 2017), Adaptive Test Selection (ATS) (Krause et al., 2017) and Random Selection (RS). We have selected the most prominent and recent baselines that can be applied and replicated on our models and datasets.

**A- White-box test selection baselines Neuron Coverage (NC).** It is the first coverage metric that has been proposed in the literature to test DNN models (Beng et al., 2015). It is defined as the ratio of neurons activated by a test input to the total number of neurons in the DNN model. A neuron is activated when its activation value is greater than a predefined threshold.

**Neuron Boundary Coverage (NBC).** This coverage metric measures the ratio of corner case regions that have been covered by test input(s). Corner case regions are defined as the activation values that are below or higher than the activation ranges observed during the training phase of the DNN model under test.

**Strong Neuron Activation Coverage (SNAC).** Similar to the NBC metric, SNAC measures how many upper corner cases have been covered by test input(s). Upper corner cases are defined as neuron activation values that are above the activation ranges observed during the training phase of the DNN model under test.

**ISA and DSA.** These two metrics have been proposed by Kim _et al._(Kim et al., 2017) and are based on the analysis of how surprising test inputs are with respect to the training dataset. LSA uses Kernel Density Estimation (KDE) (KDE, 2017) to estimate the likelihood of seeing a test input during the training phase. According to Kim _et al._(Kim et al., 2017), test inputs with higher LSA scores are preferred since they are closer to the classification boundaries. Thus it could be considered a priority score for DNN test selection. DSA is an alternative to LSA that uses the distance between the activation traces (Kim et al., 2017) of new test inputs and the activation traces observed during training.

**B- Black-box test selection baselines DeepGini.** It is a test selection approach that prioritizes test inputs with higher uncertainty scores (Li et al., 2017). It relies on the _Gini_ metric (Section 2.2.1) to estimate the probability of misclassifying a test input.

**MaxP.** It relies on the maximal prediction probability of the classification task to estimate the prediction confidence of the DNN model for a given input. Such method prioritizes inputs with lower confidence. The maximum probability score of a test input \(x\) is defined as \(MaxP(x)=1-max_{i=1}^{m}P_{x_{i}}\) where \(P_{x_{1}\leq i\leq m}\) is the probability that input \(x\) belongs to class \(C_{i}\) and \(m\) is the total number of classes (Krause et al., 2017). Intuitively, higher MaxP scores are more likely to lead to mispredictions (Krause et al., 2017).

**ATS.** It is a recent test selection method proposed by Gao _et al._(Krause et al., 2017). The selection is guided by a fitness function based on which test inputs are incrementally added to the final test set. The fitness function measures the difference between a test input and the currently selected test set based on computing a fault pattern coverage score. This score is obtained through analyzing the diversity of the output probability vectors of the DNN under test. They select test inputs with different fault patterns and higher uncertainty scores.

**Random Selection (RS)** It is the most basic and simplest test selection method in the literature. RS consists in randomly selecting (without replacement) \(\beta\) inputs from the test dataset. Each test input has the same probability of being selected.

### Evaluation and Results

We will describe in this section our experimental evaluation and present in detail the obtained results.

5.1. **Rq1. Do we find more faults than existing test selection approaches with the same testing budget?**

To investigate the effectiveness of test selection approaches in a DNN, existing baselines usually compare the misprediction detection rate (Krause et al., 2017; Li et al., 2017). Although the number of mispredicted inputs is a useful metric in some contexts, it is misleading for test selection in DNN-based systems since many mispredicted inputs may be redundant and caused by the same fault or root cause in the DNN model(Krause et al., 2017). Therefore, we compare the effectiveness of _DeepGD_ with the existing baselines based on the fault detection rate (_FDR_) (Krause et al., 2017). For each subject and for different sizes of the test input set \(\beta\in\{100,300,500\}\), we report the fault detection rate _FDR_ for each approach in Table 1, calculated as follows:

\[FDR(S)=\frac{|F_{s}|}{min(|S|,|F|)} \tag{6}\]

where \(S\) is the selected test input set, \(|F_{s}|\) is the number of faults in \(S\), \(|S|\) is the test input set size, and \(|F|\) is the total number of faults in the dataset.

Detailed results of the fault detection rate for six subjects, resulting from the combination of datasets and DNN models, for two subset sizes \(\beta=100\) and \(\beta=300\) are shown in Table 2 and Table 3 respectively. Due to space limitations, we only present results for two subset sizes. The results follow the same trend and the final conclusion is consistent for larger test subset sizes. Because of randomness in _DeepGD_, ATS, and random selection, we re-executed each of them five times and reported the corresponding average fault detection rates. Our results show that all of the test selection approaches guided by coverage metrics are ineffective in detecting faults. Even after repeating the experiment with various parameters as suggested in their original papers, the results are similar. The

\begin{table}
\begin{tabular}{l l l l} \hline \hline
**Dataset** & **DNN Model** & **Accuracy** & **\# Faults** \\ \hline \hline MNIST & LeNet5 & 87.85\% & 85 \\  & LeNet1 & 84.5\% & 137 \\ \hline Fashion-MNIST & LeNet4 & 88\% & 141 \\ \hline Cifar-10 & 12-layer ConvNet & 82.93\% & 187 \\  & ResNet20 & 86\% & 177 \\ \hline SVHN & LeNet5 & 88\% & 147 \\ \hline \hline \end{tabular}
\end{table}
Table 1. Datasets and models used for evaluation
fault detection rate of NC, for example, was between 4% and 25% for subset sizes of 100. SNAC and NBC also showed poor fault detection rates, which vary between 11% and 19% for the same subset size.

Compared with LSA and DSA, both _DeepGD_ and other black-box prioritization selection methods showed a much higher fault detection rate for all subjects. Overall, it can be concluded that black-box approaches are more effective in detecting faults than white-box approaches. _DeepGini_ and MaxP fare the same as _DeepGD_ for two different subjects with a test subset size of 100. However, for other subjects, _DeepGD_ achieves a higher fault detection rate than these two approaches. For larger test subset sizes (\(\beta=300\)), _DeepGD_ performs better than other black-box baselines in all subjects, with a fault detection rate between 53% and 64%.

Note that the second best approach is not consistently the same across subjects and sizes, therefore strengthening our conclusion that _DeepGD_ is the only solution we can confidently recommend regardless of the model, dataset, and test set size. For example, with \(\beta=100\), compared to black-box SOTA baselines, _DeepGD_ is, on average, 2 pp better (with a maximum of 6 pp across all models and datasets) than the second-best black-box alternative and 7 pp better (with a maximum of 13 pp across all models and datasets) than the fourth-best black-box alternative (excluding random selection which consistently showed poor performance). Since we cannot predict beforehand how a given alternative will fare compared to the others for a dataset and model, this implies that the effect of selecting another technique than _DeepGD_ is potentially significant as we may end up using the worst alternative. For example, if we rely on the inputs selected by _DeepGini_ to test LeNet1 on the MNIST dataset (\(\beta=300\)), we will only reach a fault detection rate of 44% instead of 55% with _DeepGD_. Further, we also report that _DeepGD_ is on average 15 pp better than the best white-box test selection approach and 40 pp better than the worst white-box alternative. We performed a statistical analysis using Wilcoxon signed-rank tests (Srivastava et al., 2014), with a significance level of 0.05, to investigate whether _DeepGD_ significantly outperforms each SOTA baseline in terms of fault-revealing power across all subjects and subset sizes. We found that all p-values are less than 0.05, indicating that _DeepGD_ significantly surpasses SOTA baselines in finding more faults in DNNs.

**Answer to RQ1:**_DeepGD_ outperforms both white-box and black-box test selection approaches for DNNs, in terms of detecting distinct faults given the same testing budget. Further, the second-best black-box approach after _DeepGD_ is not consistently the same.

5.2. **RQ2. Do we more effectively guide the retraining of DNN models with our selected inputs than with baselines?**

Having examined the effectiveness of _DeepGD_ and other baselines in selecting test input sets with high fault-revealing power, we next focus on the extent to which the test selection approaches can help select data to effectively retrain the DNN models under test. We only consider black-box test selection approaches in this research question, as they showed much better performance than white-box test selection baselines. We consider the same models and datasets as in the previous experiment. We augment the original training dataset with the test inputs selected in RQ1 by _DeepGD_, ATS, DeepGini, and MaxP, respectively, to retrain the DNN model. We measure the accuracy of the retrained model on both the whole test dataset and a newly generated dataset that is obtained by applying five realistic image transformations to the original test dataset. The latter allows for a fairer and more complete comparison between our proposed method and the other baseline approaches since none of the inputs in the generated dataset were used for retraining the model. We used the generated datasets of Gao _et al._(Gao et al., 2017), where various

\begin{table}
\begin{tabular}{|p{11.4pt} p{11.4pt}|p{11.4pt} p{11.4pt} p{11.4pt} p{11.4pt}|p{11.4pt} p{11.4pt} p{11.4pt}|p{11.4pt} p{11.4pt} p{11.4pt}|p{11.4pt} p{11.4pt}|} \hline \multirow{2}{*}{Data} & \multirow{2}{*}{Model} & \multicolumn{8}{c|}{White-box} & \multicolumn{8}{c|}{Black-box} \\ \cline{3-14}  & & NC & & \multicolumn{2}{c|}{NBC} & \multicolumn{2}{c|}{} & \multicolumn{2}{c|}{SNAC} & \multicolumn{2}{c|}{} & \multicolumn{2}{c|}{} \\  & & 0 & 0.75 & 0 & 0.5 & 1 & 0 & 0.5 & 1 & \multicolumn{2}{c|}{} & \multicolumn{2}{c|}{} \\ \hline \hline \multirow{2}{*}{Cifar-10} & 12 ConvNet & 13\% & 21\% & 13\% & 12\% & 12\% & 12\% & 11\% & 13\% & 31\% & 35\% & 14\% & 55\% & 54\% & 53\% & **59\%** \\  & ResNet20 & 10\% & 10\% & 11\% & 17\% & 16\% & 11\% & 17\% & 16\% & 42\% & 37\% & 11\% & 52\% & **56\%** & 50\% & **56\%** \\ \hline \multirow{2}{*}{MNIST} & LeNet1 & 25\% & 15\% & 16\% & 19\% & 12\% & 16\% & 18\% & 12\% & 31\% & 23\% & 12\% & **41\%** & 28\% & 40\% & **41\%** \\  & LeNet5 & 16\% & 13\% & 13\% & 17\% & 16\% & 14\% & 19\% & 16\% & 29\% & 33\% & 13\% & 35\% & 34\% & 36\% & **37\%** \\ \hline \multirow{2}{*}{Fashion} & LeNet4 & 5\% & 18\% & 14\% & 15\% & 14\% & 14\% & 15\% & 14\% & 17\% & 34\% & 10\% & **39\%** & **39\%** & 32\% & **39\%** \\ \hline \multirow{2}{*}{SVHN} & LeNet5 & 9\% & 4\% & 11\% & 12\% & 11\% & 11\% & 12\% & 11\% & 13\% & 19\% & 11\% & 43\% & 43\% & **44\%** & **50\%** \\ \hline \end{tabular}
\end{table}
Table 2. The fault detection rate for each subject with test subset size \(\beta=100\)

\begin{table}
\begin{tabular}{|p{11.4pt} p{11.4pt}|p{11.4pt} p{11.4pt} p{11.4pt} p{11.4pt} p{11.4pt} p{11.4pt} p{11.4pt} p{11.4pt}|p{11.4pt} p{11.4pt} p{11.4pt}|} \hline \multirow{2}{*}{Data} & \multirow{2}{*}{Model} & \multicolumn{8}{c|}{White-box} & \multicolumn{8}{c|}{Black-box} \\ \cline{3-14}  & & NC & & \multicolumn{2}{c|}{NBC} & \multicolumn{2}{c|}{SNAC} & \multicolumn{2}{c|}{} \\  & & 0 & 0.75 & 0 & 0.5 & 1 & 0 & 0.5 & 1 & \multicolumn{2}{c|}{} \\ \hline \hline \multirow{2}{*}{Cifar-10} & 12 ConvNet & 19\% & 28\% & 21\% & 22\% & 23\% & 22\% & 22\% & 22\% & 35\% & 37\% & 22\% & 54\% & 53\% & 50\% & **56\%** \\  & ResNet20 & 15\% & 17\% & 17\% & 17\% & 19\% & 17\% & 17\% & 19\% & 49\% & 45\% & 19\% & 56\% & 58\% & 52\% & **59\%** \\ \hline \multirow{2}{*}{MNIST} & LeNet1 & 25\% & 25\% & 33\% & 28\% & 27\% & 36\% & 29\% & 27\% & 40\% & 40\% & 25\% & 53\% & 44\% & 53\% & **55\%** \\  & LeNet5 & 34\% & 33\% & 32\% & 33\% & 30\% & 32\% & 30\% & 30\% & 54\% & 52\% & 24\% & 63\% & 59\% & 62\% & **64\%** \\ \hline \multirow{2}{*}{Fashion} & LeNet4 & 8\% & 25\% & 19\% & 23\% & 23\% & 19\% & 23\% & 23\% & 35\% & 45\% & 17\% & 51\% & 47\% & 49\% & **53\%** \\ \hline \multirow{2}{*}{SVHN} & LeNet5 & 11\% & 13\% & 17\% & 16\% & 18\% & 17\% & 16\% & 18\% & 19\% & 36\% & 17\% & 58\% & 61\% & 58\% & **62\%** \\ \hline \end{tabular}
\end{table}
Table 3. The fault detection rate for each subject with test subset size \(\beta=300\)
transformations were applied to the MNIST, Fashion-MNIST and Cifar-10 test datasets. However, since no generated inputs were included for the SVHN dataset, we generated new test inputs by applying the same transformations. These transformations include sheering, rotating, zooming, and changing the brightness and the blurriness of all images in each dataset. We should note that the size of the newly generated test dataset is five times larger than the original test dataset since we apply five image transformations on each original test input. For each black-box test selection approach, we measure the accuracy improvement of the retrained models on both the original test dataset and the generated one. We report the results in Table 4. We acknowledge that studying accuracy improvement of the retrained models on the generated datasets is more suitable in our context since it does not contain any of the inputs used for retraining. But we choose to also report improvements with the original test dataset to verify that the retraining process did improve model accuracy. Note that we only select a small part of the original test dataset to retrain the model (only 300 out of 10,000 to 26,000 inputs).

As described in Table 4, we found that _DeepGD_ provides better guidance for retraining DNN models than the other black-box test selection approaches. It consistently outperforms ATS, DeepGini, and MaxP in terms of accuracy improvements across all models and datasets. Similar to the previously reported results in RQ1, we found that the second-best approach for guiding retraining is not consistently the same across all subjects. For example, ATS was the second-best approach for retraining ResNet20 with Cifar-10, while it was the third-best approach for retraining LeNet5 with SVHN.

To further investigate the effectiveness of _DeepGD_ and the other black-box baselines in retraining DNN models, we also computed their _optimization effectiveness_ by accounting for the maximum possible accuracy improvement. We therefore retrain the model with the entire original test dataset and report the best accuracy that can be achieved by retraining. Then, for each test selection method, we calculate its optimization effectiveness, defined as the ratio of (1) the accuracy improvement when retaining the model with only 300 selected inputs from the original test dataset (Table 4) to (2) the accuracy improvement when retaining the model with the entire original test dataset. We also repeat the above experiment for the generated test data set to once again get a fairer comparison of the test selection approaches and to obtain better generalizability for our results. More specifically, we retrain the original model by adding all generated inputs to the training dataset to achieve the highest accuracy possible. Then, we calculate the corresponding optimization effectiveness which is the ratio of (1) the accuracy improvement when retaining the model with only 300 inputs from the original test dataset (Table 4) to (2) the accuracy improvement when retaining the model with the entire generated test dataset. We report the results in Table 5.

We found that _DeepGD_ consistently outperforms other black-box test selection approaches in terms of optimization effectiveness. Compared to black-box SOTA baselines, _DeepGD_ is, on average, 8.93 pp better (with a maximum of 20.11 pp) than the second-best black-box alternative and 11.49 pp better (with a maximum of 25.06 pp) than the worst black-box alternative. As for RQ1, it is worth noting that since the performance of alternatives is not consistent across datasets and models, selecting one of them may yield the worst results. We also report the average optimization effectiveness on the generated test datasets. Gini, MaxP and ATS yield 30.35%, 31.07%, and 32.25% respectively, while _DeepGD_ achieves 38.03%. In other words, with only 300 test inputs, from the original test dataset and selected by _DeepGD_ for retraining, we were able to reach 38.03% of the maximum achievable accuracy by retraining with all generated test dataset. We should note that these results are expected since _DeepGD_ showed better performance than the other baselines in retraining the DNN models under test in our previous experiment. Similar to RQ1, we performed a statistical analysis using Wilcoxon signed-rank tests, with a significance level

\begin{table}
\begin{tabular}{|c|c|c|c c c||c c c|c|} \cline{3-10} \multicolumn{1}{c}{} & & \multicolumn{3}{c||}{Accuracy imp. on orig. test dataset} & \multicolumn{3}{c|}{Accuracy imp. on generated test dataset} \\ \hline Data & Model & MaxP & Gini & ATS & **DeepGD** & MaxP & Gini & ATS & **DeepGD** \\ \hline \hline \multirow{2}{*}{Cifar-10} & 12 ConvNet & 3.52\% & 2.09\% & 2.12\% & **3.53\%** & 5.35\% & 5.12\% & **4.62\%** & **6.85\%** \\ \cline{2-10}  & ResNet20 & 1.66\% & 0.74\% & 2.03\% & **2.50\%** & 4.12\% & 3.45\% & 5.97\% & **6.18\%** \\ \hline \multirow{2}{*}{MNIST} & LeNet1 & 10.39\% & 10.40\% & 10.40\% & **11.10\%** & 13.18\% & 13.24\% & 13.19\% & **14.76\%** \\ \cline{2-10}  & LeNet5 & 7.94\% & 7.91\% & 7.92\% & **9.26\%** & 13.02\% & 12.92\% & 13.08\% & **15.82\%** \\ \hline \multirow{2}{*}{Fashion} & LeNet4 & 3.94\% & 3.94\% & 3.91\% & **4.17\%** & 7.33\% & 7.41\% & 7.62\% & **7.69\%** \\ \hline SVHN & LeNet5 & 0.96\% & 0.99\% & 0.93\% & **1.24\%** & 0.61\% & 0.54\% & 0.63\% & **1.26\%** \\ \hline \end{tabular}
\end{table}
Table 4. DNNs accuracy improvements after retraining with the selected test input sets.

\begin{table}
\begin{tabular}{|c|c|c|c c c||c c c|c c|} \cline{3-10} \multicolumn{1}{c}{} & & \multicolumn{3}{c||}{Opt effectiveness on orig. test dataset (\(\overline{1}\))} & \multicolumn{3}{c|}{Opt effectiveness on generated dataset (G)} \\ \hline \multirow{2}{*}{Data} & \multirow{2}{*}{Model} & Max imp. & \multirow{2}{*}{MaxP} & Gini & ATS & \multirow{2}{*}{**DeepGD**} & Max imp. & \multirow{2}{*}{MaxP} & Gini & ATS & **DeepGD** \\  & & (100\% T) & & & & & & & & & \\ \hline \hline \multirow{2}{*}{Cifar-10} & 12 ConvNet & 16.36\% & 21.51\% & 12.78\% & 12.96\% & **21.58\%** & 28.98\% & 18.47\% & 17.65\% & 15.94\% & **23.65\%** \\ \cline{2-10}  & ResNet20 & 9.99\% & 16.62\% & 7.41\% & 20.32\% & **25.03\%** & 23.33\% & 17.65\% & 14.80\% & 25.59\% & **26.47\%** \\ \hline \multirow{2}{*}{MNIST} & LeNet1 & 11.01\% & 93.60\% & 93.72\% & 93.69\% & **100\%** & 23.80\% & 55.39\% & 55.62\% & 55.43\% & **62.04\%** \\ \cline{2-10}  & LeNet5 & 9.52\% & 83.40\% & 83.08\% & 83.19\% & **97.27\%** & 22.78\% & 57.15\% & 56.72\% & 57.41\% & **69.46\%** \\ \hline \multirow{2}{*}{Fashion} & LeNet4 & 12.00\% & 32.83\% & 32.83\% & 32.58\% & **34.75\%** & 23.72\% & 30.91\% & 31.23\% & 32.10\% & **32.41\%** \\ \hline SVHN & LeNet5 & 1.25\% & 77.01\% & 79.79\% & 74.84\% & **99.90\%** & 8.92\% & 6.87\% & 6.06\% & 7.04\% & **14.15\%** \\ \hline \hline \multicolumn{10}{|c}{Average} & 10.04\% & 54.16\% & 51.60\% & 52.93\% & **63.09\%** & 21.92\% & 31.07\% & 30.35\% & 32.25\% & **38.03\%** \\ \hline \end{tabular}
\end{table}
Table 5. Optimization effectiveness compared to retraining with all candidate tests
of 0.05, to investigate whether _DeepGD_ significantly outperforms the selected black-box test selection approaches in terms of optimization effectiveness across all subjects. We found all p-values to be less than 0.05, indicating that _DeepGD_ is significantly better than the selected baselines in retraining DNN models. In other words, results show that _DeepGD_ can select a small, more informative subset from a large unlabeled dataset to effectively retrain DNN models and minimize the labeling costs. Selecting diverse inputs with high uncertainty scores not only helps at detecting more faults in the DNN model, but also significantly improves the accuracy of the model through retraining.

**Answer to RQ2:**_DeepGD_ provides better guidance than black-box alternatives for retraining DNN models. It consistently and statistically outperforms other black-box test selection approaches in terms of accuracy improvement, in absolute terms and relatively to the maximum achievable improvement.

#### 3.5.3. **Discussions**

Based on our experimental results, we show that _DeepGD_ provides better guidance than existing baselines for selecting test inputs with high-fault revealing power. The second-best approaches for test selection and model retraining are not consistently the same across all models and datasets. This reinforces our conclusion that _DeepGD_ is the only solution that we can confidently recommend regardless of the model, dataset, and test set size. Indeed, selecting diverse test inputs with high uncertainty scores not only enables higher fault detection, but also provides more effective guidance for retraining DNN models. Although results are encouraging, and though this remains to be further investigated, we conjecture that _DeepGD_ is particularly useful when datasets are more redundant, a situation that is often observed in real world DNN testing scenarios, especially with massive generated datasets. Selecting diverse test input sets with _DeepGD_ is then expected to help reduce redundancy by selecting more informative inputs to be labeled in order to test and retrain DNN models. We should also note that the mean execution time of our test selection approach on Google Colab was five hours. This is practically acceptable since, in DNN testing, (1) the labeling cost of test inputs is far more expensive than the computation cost of the search, and (2) test selection is neither frequent nor a real-time task.

## 4. Threats to Validity

We discuss in this section the different threats to the validity of our study and describe how we mitigated them.

**Internal threats to validity** concern the causal relationship between the treatment and the outcome. Since _DeepGD_ is black-box and relies on extracting feature matrices to measure the diversity of the selected test input sets, an internal threat to validity might be caused by the poor quality representation of inputs. To mitigate this threat, we have relied on VGG-16, one of the most accurate feature extraction models in the literature. This model has been pre-trained on the very large ImageNet dataset that contains more than 14 million labeled images belonging to 22,000 categories. Moreover, _DeepGD_ relies on the specification of a few hyperparameters related to NSGA-II. This also applies to several white-box and black-box test selection approaches that we considered in our study. The configuration of the different hyperparameters in our work may induce additional threats. To mitigate them, we have relied on the NSGA-II hyperparameters recommended in the literature (Shi et al., 2017; Li et al., 2018; Li et al., 2019) except for the mutation rate, which was intentionally set higher and experimentally tuned since we customized the mutation operator to take into account both fitness functions, as described in section 2.3.2. We have also considered different configurations of the baselines-related hyperparameters according to their original papers. A last internal threat to validity would be related to randomness when selecting test input sets with _DeepGD_, ATS, and random selection. We addressed this issue by repeating such selection multiple times while considering different input set sizes and different datasets and models.

**Construct threats to validity** concern the relation between the theory and the observations made. A construct threat to validity might be due to inaccuracies in estimating DNN faults since detecting faults in DNNs is not as straightforward as in regular software. To mitigate this threat, we have relied on a SOTA fault estimation approach (Li et al., 2018) that has been thoroughly validated on several models and datasets. We have reused their publicly available approach to obtain accurate fault estimates. Nonetheless, relying on a such fault estimation approach is still far better than just considering mispredicted inputs that are redundant and due to the same root cause in the DNN model.

**External threats to validity** concern the generalizability of our study. We mitigate this threat by considering six different combinations of widely used and architecturally distinct models and datasets. We also considered many testing budgets in our experiments and compared our results with nine SOTA baselines for DNN test selection.

## 5. Related Work

In this section, we introduce existing work related to our proposed approach from two aspects: test selection and test diversity in the context of DNN models.

**Test Selection for DNNs.** Test selection approaches proposed for DNN models can be characterized as black-box or white-box, depending on their access requirements to the internals of the DNN model.

A few black-box test selection approaches for DNNs have been introduced in the literature. They generally rely on the uncertainty of model classifications. For example, Feng _et al._(Feng et al., 2019) proposed DeepGini, a test selection approach that prioritizes the selection of inputs with higher _Gini_ scores (Feng et al., 2019). They conjecture that if a DNN model is unsure about a classification and outputs similar probabilities for each class, it is more likely to mispredict the test input. Compared to random and coverage-based selection methods, DeepGini was shown to be more effective in uncovering mispredictions (Feng et al., 2019; Li et al., 2019). Similar to their work, we rely on _Gini_ scores as one of the fitness functions in our approach. However, we also consider the diversity of the selected test set and rely on a multi-objective genetic search to guide the search toward finding test inputs with high fault-revealing power. Li _et al._(Li et al., 2019) introduced Cross Entropy-based Sampling (CES) and Confidence-based Stratified Sampling
(CSS), for black-box DNN test selection. These metrics are used to select a small subset of test inputs that accurately reflect the accuracy of the whole test dataset. They show that compared to random sampling, their approach could achieve the same level of precision with about half of the labeled data. Their goal is clearly different from ours. While our focus is to prioritize the selection of test inputs with high fault-revealing capability, their goal is to minimize test sets. Also, though Arrieta (Srieta et al., 2018) relied on NSGA-II and uncertainty scores for selecting metamorphic follow-up test cases, our goal with _DeepGD_ is also different. We use both diversity and DNN uncertainty to guide the search toward test inputs with high fault-revealing power, for a fixed budget.

Several white-box test selection approaches have been proposed as well. Such approaches generally rely on coverage (Beng et al., 2017; Chen et al., 2018; Li et al., 2019) or surprise metrics (Li et al., 2019) to select inputs that will be labeled and used for testing DNN models. For example, Pei _et al._(Pei et al., 2018) proposed Neuron Coverage (NC), which measures neurons activation rates in DNN models. Ma _et al._(Ma et al., 2019) proposed _DeepGauge_, a set of coverage metrics for DNN models that consider neurons activation ranges. Kim _et al._(Kim et al., 2019) proposed surprise coverage metrics which measure how surprising test sets are given the training set. The selection of test inputs for all these approaches is based on maximizing coverage or surprise scores. However, several studies (Liu et al., 2019; Li et al., 2019; Li et al., 2019; Li et al., 2019; Li et al., 2019; Li et al., 2019; Li et al., 2019), have shown that these white-box metrics are not always effective for guiding DNNs test selection. For example, Ma _et al._(Ma et al., 2019) performed an empirical study and compared the effectiveness of white-box metrics (coverage and surprise metrics) with black-box uncertainty in guiding test input selection. Results showed that the former have a weak or no correlation with classification accuracy while the latter had a medium to strong correlation. Uncertainty-based metrics not only outperform coverage-based metrics but also lead to faster improvements in retraining. In our work, as mentioned above, we also consider maximizing the uncertainty score of the test inputs as one of our two fitness objectives.

**Diversity in DNN Testing.** Many works have studied diversity-based test selection and generation for traditional software (Liu et al., 2019; Li et al., 2019; Li et al., 2019). The underlying assumption is that there is a strong correlation between test case diversity and fault-revealing power (Li et al., 2019). Their results confirmed this assumption and showed that diversity-based metrics are effective in revealing faults. Inspired by these encouraging results, researchers devised diversity-based approaches for DNN testing (Liu et al., 2019; Li et al., 2019; Li et al., 2019; Li et al., 2019). Zhao _et al._(Zhao et al., 2019) conducted an empirical study of SOTA test input selection approaches for DNNs (Li et al., 2019; Li et al., 2019; Li et al., 2019) and concluded that they have a negative impact on test diversity and suggest that more research is warranted on designing more effective test selection approaches that guarantee test diversity.

In a recent study, Gao _et al._(Gao et al., 2019) proposed the adaptive test selection method (ATS) for DNN models that use the differences between model outputs as a behavior diversity metric. Although ATS aims to cover more diverse faults, its test selection is guided only by model outputs. _DeepGD_, however, considers both the uncertainty of model output probabilities and input features' diversity. Moreover, our results show that _DeepGD_ outperforms ATS in test input selection for different combinations of models and datasets and for different test subset sizes. Aghababaeyan _et al._(Aghabaeyan et al., 2019) studied three black-box input diversity metrics for testing DNNs, including geometric diversity (Zhao et al., 2019), normalized compression (Li et al., 2019), and standard deviation. They investigated the capacity of these metrics to measure actual diversity in input sets and analyzed their fault-revealing power. Their experiments on image datasets showed that geometric diversity outperforms SOTA white-box coverage criteria in terms of fault detection and computational time. However, they did not study how the GD metric can be used in practice to guide the selection of test inputs for DNN models.

## 6. Conclusion

In this paper, we propose _DeepGD_, a multi-objective search-based test input selection approach for DNN models. Our motivation is to provide a black-box test selection mechanism that reduces labeling costs by effectively selecting unlabeled test inputs with high fault-revealing power. We rely on both diversity and uncertainty scores to guide the search toward test inputs that reveal diverse faults in DNNs. We conduct an extensive empirical study on six different subjects and compare _DeepGD_ with nine state-of-the-art test selection approaches. Our results show that _DeepGD_ statistically and consistently outperforms baseline approaches in terms of its ability to reveal faults in DNN models. Selecting diverse inputs with high uncertainty scores with _DeepGD_ not only helps detecting more faults in the DNN model for a given test budget, but also significantly improves the accuracy of the model through retraining with an augmented training set. Our results also indicate that the second-best approach for testing or retraining is not consistent across all models and datasets, further supporting the choice of _DeepGD_. We aim to extend our work by studying the application of diversity and uncertainty metrics for other DNN testing purposes such as test minimization and generation. Finally, we need to investigate alternative ways to estimate faults in DNNs.

###### Acknowledgements.

 This work was supported by a research grant from General Motors as well as the Canada Research Chair and Discovery Grant programs of the Natural Sciences and Engineering Research Council of Canada (NSERC).
