# You Can’t See the Forest for Its Trees: Assessing Deep Neural Network
Testing via NeuraL Coverage

Yuanyuan Yuan, Qi Pang, Shuai Wang
The Hong Kong University of Science and Technology
{yyuanaq, qpangaa<EMAIL_ADDRESS>
###### Abstract.

Recent works propose various deep neural network (DNN) coverage criteria to
assess DNN test inputs and steer input mutations. Coverage is usually defined
as the number of neurons whose outputs fall within certain ranges, and the
range specifications distinguish these criteria. Despite the fact that a DNN
is seen as a network of neurons with topological connections, its data and
control flows are often constant when given diverse inputs. Observing the
outputs of neurons alone is insufficient to define the behaviors of DNNs. As a
result, recent research indicates that there is little correlation between the
quality of test suites and neuron coverage criteria.

In general, DNNs approximate distributions, by incorporating hierarchical
layers and neurons, in order to make decisions based on observed inputs. Thus,
this work champions to deduce the behavior of a DNN from its approximate
distributions. Accordingly, a test suite should be assessed from its induced
neuron and layer output distributions. Meanwhile, to fully examine DNN
behaviors, input mutation in typical DNN testing should be directed toward
diversifying the approximated distributions.

This paper summarizes eight design requirements for DNN testing criteria,
taking into account distribution properties and practical concerns. We then
propose a new criterion, NLC, that satisfies all of these design requirements.
NLC treats a single DNN layer as the basic computational unit (rather than a
single neuron) and captures four critical features of neuron output
distributions. Thus, NLC is denoted as NeuraL Coverage, which more accurately
describes how neural networks comprehend inputs via approximated distributions
rather than neurons. We demonstrate that NLC is significantly correlated with
the diversity of a test suite across a number of tasks (classification and
generation) and data formats (image and text). Its capacity to discover DNN
prediction errors is promising. Test input mutation guided by NLC result in a
greater quality and diversity of exposed erroneous behaviors.

Preprint, under review.

##  1\. Introduction

Recent work has incorporated software testing methodologies to successfully
evaluate DNNs without the need for human annotations, for example, by
transforming test inputs with always-hold relations (e.g., metamorphic
relations) (Tian et al., 2018; Zhang et al., 2018; Wang and Su, 2020). Such
practice can effectively augment evaluation datasets and benchmark DNNs.
However, fundamental understanding of a DNN’s mechanism has remained largely
unexplored due to its intrinsic non-linearity. Additionally, it has been
observed that the decisions made by a DNN are susceptible to certain biases in
the inputs (Geirhos et al., 2019; Zeiler and Fergus, 2014; Brendel and Bethge,
2019). As a result, DNN evaluation is highly dependent on the test suite’s
representativeness. Testing criteria is thus required to characterize a test
suite’s quality and toward which the input mutations can comprehensively
explore DNN behaviors.

In a manner similar to how coverage criteria are developed in traditional
software testing, recent research proposes several neuron coverage criteria.
In principle, the current criteria are mostly designed to monitor the outputs
of neurons in a DNN model to assess the quality of test inputs. They argue
that each neuron is an “individual computing unit” (as the authors put it (Pei
et al., 2017)), or “individually encoding a feature” (Ma et al., [n.d.]),
comparable to a statement in traditional software. Further, despite that
neuron outputs are continuous, existing criteria often first convert neuron
outputs into discrete states (e.g., activation or not) to reduce the modeling
complexity. Thus, by analyzing the discrete states of neurons, the DNN
coverage exercised by an input is measured.

However, the key assumption — each neuron is an individual computing unit —
often does not hold true for modern DNNs. Given a DNN is composed of stacked
and non-linear blocks, the intermediate outputs (also known as latent
representations) from neurons are continuous and highly entangled.
Disentangling intermediate outputs remains a long-lasting challenge in the AI
community (Lee et al., 2018; Ren et al., 2021; Liu et al., 2018). And recent
research in the software engineering community also points out that that the
efficacy of a test suite to uncover faults and existing neuron coverage
attained by the test suite are not always positively correlated (Harel-Canada
et al., 2020).

Establishing proper DNN coverage criteria requires a principled understanding
about how DNN performs computations, which is fundamentally different with
traditional software. A DNN, as a composition of parameterized non-linear
functions (i.e., layers), extracts task-oriented features and then makes
decisions accordingly. Features, hierarchically captured by layer outputs,
approximate the posterior distribution of underlying explanatory factors $H$
for observed inputs $X$, namely $P(H|X)$ (Bengio et al., 2013; Bishop et al.,
1995). For example, given an image, layers in an image classifier extract
hierarchical features that imply its class label (Bengio et al., 2013). More
precisely, an image classifier generates a set of posterior distributions
$P(h_{i}|x)$ (where $i$ is the layer index, $h_{i}\in H$ and $x\in X$) with
each $h_{i}$ describes class-invariant properties of an image from different
perspectives (e.g., shape, texture). The dependability of a DNN is defined as
the degree to which the distribution, approximated on training data, is
accurate when applied to real test data.

This work initializes a fresh and principled view on designing DNN coverage
criteria, by assessing test inputs in terms of its induced neuron and layer
output distributions. This work first concretizes our focus on distributions
into eight design requirements of DNN testing criteria. These design
requirements characterize the distribution approximated by a DNN from various
perspectives, and also take practical constraints (e.g., speed, hyper-
parameter free) into account. Then, we propose a new coverage criterion,
namely NLC (NeuraL Coverage), that can fully meet the design principles. NLC
is referred to as “neural coverage” rather than neuron coverage since our
study focuses on the overall activity of groups of neurons and consider
relations of neurons, which distinguishes NLC from all existing efforts. Our
evaluation encompasses nine DNNs that analyze a variety of data formats (e.g.,
image, text) and perform a variety of tasks (e.g., classification,
generation). We demonstrate that NLC is substantially correlated with the
diversity and capacity of a test suite to reveal DNN defects. Meanwhile, by
taking NLC as the fuzzing feedback, we show that more and diverse errors can
be found, and the error-triggering inputs mutated under the guidance of NLC
manifest high naturalness. Our contributions are summarized as:

  * •

This work advocates to design DNN testing criteria via a principled
understanding about how DNN, with its hierarchical layers and neurons,
approximate distributions. We argue that a proper DNN testing criterion should
model the continuous neuron outputs and neuron entanglement in a comprehensive
manner, instead of analyzing each neuron individually.

  * •

We propose eight design requirements by characterizing the distributions
approximated by a DNN and also taking into account practical implementation
considerations. We accordingly design NLC, which satisfies all these
requirements.

  * •

We show that NLC can better assess the quality of test suites. NLC is
particularly correlated with the diversity and fault-revealing capacity of a
test suite. Fuzz testing under the guidance of NLC can also detect a large
number of errors, which are shown as diverse and natural-looking.

##  2\. Preliminary

DNNs are often explained from the perspective of distribution approximation
(Bengio et al., 2013; Bishop et al., 1995; Schmidhuber, 2015). To motivate
NLC, this section provides a high-level overview of DNNs from the distribution
perspective.

Layer and Hierarchy. The term network in DNN refers to topological connections
of non-linear layers. Each layer (e.g., a fully connected layer) has a group
of neurons cooperating to process certain input features. The DNN hierarchy is
established by gradually abstracting features from shallow to deep layers. For
instance, image classifiers commonly collect shapes in an image at shallow
layers and texture at deeper layers. Each layer (not each neuron) serves a
minimal computing unit, whose output distribution encodes its focused
features.

Neurons in a Layer. The term neural in DNN may be obscure. In cognitive
science, neural signifies non-linear functions (e.g., Sigmoid) in DNNs that
simulate how human neurons process signals (Rosenblatt, 1958; Block, 1962).
DNNs are powerful at analyzing high-dimensional media data and alleviating the
curse of dimensionality due to their non-linearity (Bellman, 1966; Bengio et
al., 2013). Moreover, outputs of neurons are continuous. Neurons in a layer
are therefore highly entangled, impeding to comprehend the DNN’s internal
mechanics.

Given a collection of data $X$ labeled as $Y$, most popular DNNs can be
categorized as discriminative and generative models, depending on how $X$ and
$Y$ are involved in the distribution approximation.

Discriminative Models. Deep discriminative models approximate the conditional
probability distribution $P(Y|X)$. A classification model requires $Y$ as
discrete labels, and a regression model (e.g., forecasting) requires $Y$ as a
range of continuous values. For instance, a convolutional neural network (CNN)
can classify images by extracting features (conveyed via outputs of
intermediate neurons) and making decisions in one forward propagation. A layer
outputs a conditional distribution denoting the extracted input features at
this layer (Bengio et al., 2013; Bishop et al., 1995; Schmidhuber, 2015). And
with the extracted features getting more abstract at deeper layers, the ending
layer returns the probability that the input belongs to each label. Sequential
data, such as text, is typically processed by recurrent models, since the
sequence, i.e., dependency between tokens, usually contains richer
information. For example, an RNN conducting machine translation translates
source language text into target language text. The model outputs one word
every step, computing the conditional probability on all target words based on
the current input word and processed words.

Generative Models. Another popular paradigm is the deep generative model,
which estimates the joint probability distribution $P(X,Y)$ of data $X$ and
label $Y$. The most common models are VAE (Kingma and Welling, 2013) and GAN
(Goodfellow et al., 2014). Generative models are primarily adopted to
synthesize realistic data. To do so, both VAE and GAN project the data
distribution to a simple distribution (e.g., normal distribution). To generate
realistic outputs, random inputs sampled from the pre-defined distribution are
fed into deep generative models.

Figure 1. Visualization of $n_{1}$ and $n_{2}$’s outputs in three models
extended from $Net$. X- and y-axis are outputs of $n_{1}$ and $n_{2}$.

Visualizing DNN Outputs. We empirically assess and visualize distribution of
intermediate neurons’ outputs. We prepare a DNN (denoted as $Net$) with two
neurons $n_{1}$ and $n_{2}$ in the last layer (thus the dimensions are two)
and extend $Net$ into 1) a VAE, 2) a class-conditional VAE, and 3) a
classifier model. The three models are trained on the MNIST dataset (Deng,
2012) for 1) random image generation, 2) labeled image (e.g., “2”) generation,
and 3) image classification. In short, these three models inherent the same
structure from $Net$ yet perform different tasks by using different trailing
layers. We plot outputs of $n_{1}$ and $n_{2}$ in these three models in Fig.
1.

Each dot denotes one output of $n_{1}$ and $n_{2}$, corresponds to one image
input. Multiple colors represent different labels of the inputs (e.g., red
represents “9”). In Fig. 1(a), neuron outputs are jointly distributed
corresponding to different labels. Fig. 1(c) shows a similar distribution,
whereas the outputs are separated with labels to facilitate image
classification. For Fig. 1(b), since class labels are provided as inputs, the
model only captures common attributes of images. Therefore, outputs are not
split.

This study examines the continuity of neuron outputs. Moreover, it considers
neuron entanglement, where neurons in a layer jointly form distributions that
reflect how DNNs (of different tasks) understand input data distinctly. Also,
outputs in high-density regions are not uniform. Rather, they tend to
concentrate in the center.

NLC. Distributions formed by entangled neurons are important indicators of DNN
behaviors. Given that “neural”, holistically, denotes the distributions of
neuron outputs when understanding input features, this work proposes NeuraL
Coverage, NLC, a new criterion that captures features in distributions formed
in neuron outputs. The term “neural”, as an adjective, better reflects neuron
outputs are processed in the continuous form and “L” also indicates each Layer
is considered as the minimal computing unit.

##  3\. Motivation and Related Works

This work proposes eight requirements to design a proper DNN testing
criterion. We introduce the first three requirements in Sec. 3.1 and the rest
five requirements in Sec. 3.2.

Figure 2. A schematic view of prior DNN coverage criteria. Two axises denote
two neurons in a layer.

###  3.1. DNN Testing and Software Testing

Discrete vs. Continuous States. For software, coverage is typically measured
by counting #statements, #basic blocks, or #paths executed by a test input.
Accordingly, software testing aims to maximize code coverage, as high coverage
suggests comprehensive testing. Inspired by software testing, previous DNN
testing often first converts a neuron’s continuous outputs into two states,
activated or not. Activation signals that a neuron is covered. Counting
#activated neurons by a test input measures DNN coverage.

As shown in Fig. 1, a binary state (or a discretized state in general) is not
expressive for describing neuron behavior. Instead, we advocate that a DNN
coverage criterion should ①precisely describe the continuous output of a
neuron.

Path vs. Layer. We argue that it is inaccurate to compare neurons to software
statements. Each neuron is not as individual computing unit. In general, an
“unactivated” neuron (in prior work’s (Pei et al., 2017) language) can still
affect the subsequent neurons’ outputs and even the final output. Since DNN
weights are fixed after training, contributions from each neuron are fixed
(encoded in weights). However, software statements may not be covered
regarding a particular input. On the other hand, Fig. 1 has shown that neuron
outputs are often entangled to form joint distributions. Neuron entanglement
is, to some extent, analogous to control-flow dependency, i.e., statements on
the same path are executed together. Rather than studying individual neurons,
it is preferable (and more efficient) to measure DNN coverage by
②characterizing correlations of neurons.

Execution vs. Estimation. Software executes its input on an execution path.
DNNs, as described in Sec. 2, use a series of matrix and non-linear
computations to approximate certain distributions given inputs as
observations. Different DNN inputs produce different distributions, as seen in
Fig. 1. Hence, further to ②, we advocate defining DNN criterion over the
approximated distributions.

While it’s difficult to precisely describe the approximated distribution
(Rasmussen et al., 1999; Reynolds, 2009; Xuan et al., 2001), certain
informative properties of a distribution can be captured. Also, since coverage
criteria are used to assess test suite quality and guide input mutations,
knowing the exact distribution may not be required (see our empirical results
in Sec. 7). In brief, we advocate that the DNN coverage criterion should
analyze ③how outputs of neurons in a layer are distributed.

###  3.2. Existing Neuron Coverage

We illustrate existing DNN coverage criteria in Fig. 2 using two neurons (in a
layer) to ease reading. In general, existing coverage criteria discretize
neuron outputs to decide if a neuron is “covered.”

Capturing “Major Behavior” of a Neuron. The first criterion, namely neuron
coverage (NC), was proposed in (Pei et al., 2017). It is argued by (Pei et
al., 2017) that the major behavior of a neuron is mostly reflected when its
outputs are above zero. As in Fig. 2(a), NC deems a neuron as activated if its
output is above threshold $T$ ($T$ is usually zero or a small value above).
Following, three criteria were proposed (Ma et al., [n.d.]), namely
K-Multisection Neuron Coverage (KMNC), Neuron Boundary Coverage (NBC) and
Strong Neuron Activation Coverage (SNAC). We display KMNC, NBC and SNAC in
Fig. 2(b), Fig. 2(c) and Fig. 2(d). All three criteria first run training data
to scope the output range of each neuron. Then, KMNC splits each range into
$K$ segments and regards coverage as #segments covered by neuron outputs. NBC
denotes coverage as #neuron outputs lying outside the range, while SNAC counts
coverage as #neurons whose outputs are larger than the upper bound of its
normal value range. The intuition behind the three criteria is that the major
behaviors of neurons are denoted as outputs that lie in the range decided by
training data.

Considering the blue region in Fig. 1(c), it is easy to see that when feeding
inputs of label “1”, NC over those two neurons will saturate. This indicates
that criteria, which simply discretize neuron outputs, cannot properly
describe the diversity of test suits (e.g., inputs of different labels).
Moreover, note that all these criteria should not change if the orange
distribution in Fig. 2(c) is rotated for 90 degrees (possibly due to fine-
tuning). That is, these criteria might hardly reflect distinctly changed
distributions of neuron outputs.

Further to ①, we argue that a neuron’s major behavior can hardly be defined
using coarse-grained thresholds. Instead, given that the high-density regions
formed by neuron outputs in a layer (the “dots” on the background of Fig. 2)
are distinct on shapes, we deem the major behavior as the shapes which reflect
the divergence of neuron outputs and the correlations among neurons. The
corner-case behavior, accordingly, is regarded as neuron outputs lying in low-
density regions. Therefore, we advocate that ④DNN coverage should take the
density of neuron output distributions into account. Holistically, measuring
the density considers both major and corner-case behaviors of DNNs, which is
desirable in software testing.

Discretizing Outputs of Several Neurons. Two layer-wise neuron coverage
criteria were also proposed in (Ma et al., [n.d.]), i.e., Top-K Neuron
Coverage (TKNC) and Top-K Neuron Patterns (TKNP). Both criteria denote a
neuron as activated if its outputs are ranked at top-$K$ among neurons in a
layer. TKNC counts #neurons once been activated, whereas TKNP records
#patterns formed by activated neurons. In the case where there are two neurons
in a layer, as we show in Fig. 2(e), a neuron is activated if its output is
greater than the other one (i.e., $K=1$ and $n_{1}>n_{2}$). Despite
considering all neurons in a layer, TKNC and TKNP are not able to
comprehensively assess the diversity of a test suite, since both are easily
saturated w.r.t. inputs of one or a few classes (see Fig. 1).

A cluster-based coverage (CC) was proposed in (Odena and Goodfellow, 2018), in
which the coverage is denoted as #clusters. Two clusters are formed if, the
Euclidean distance of outputs from all neurons within a layer, is larger than
a threshold. Given that the cluster is determined based on distance, CC can be
regarded as counting #regions formed by several neuron outputs as shown in
Fig. 2(f). CC is more desirable than prior criteria given it is more
comprehensive to overlay the joint distribution of neurons. Nevertheless, for
the class-conditional VAE shown in Fig. 1(b), only inputs of one class can
saturate CC, despite that inputs are far less being diverse. Also, CC could
not capture correlations among neurons. Some recent studies propose coverage
criteria based on the surprise adequacy (SA) (Kim et al., 2019, 2020), which
is a “distance” measure (in terms of neuron outputs) between a new input and
historical inputs. More specifically, they discretize the distance range into
several slots and count coverage as #slots covered by test suites. In that
sense, they are conceptually variants of CC. See more details in Sec.
Comparison with Surprise Adequacy.

The Sign-Sign Coverage (SSC) criterion was proposed in (Sun et al., 2018). SSC
captures the sign change of layer-wise adjacent neurons. A neuron is activated
if 1) its outputs, and outputs from its adjacent neuron, have different signs
for any pair of input $<p_{1},p_{2}>$ (i.e., $n_{1}^{l}$ and $n_{1}^{l+1}$ in
Fig. 2(g)) and simultaneously, 2) outputs from all other neurons with in the
same layer have an identical sign for $<p_{1},p_{2}>$ (i.e., $n_{2}^{l}$ and
$n_{2}^{l+1}$ in Fig. 2(g)). SSC is specifically designed for ReLU-DNNs (i.e.,
DNNs with ReLU as the non-linear function). However, since most of the neuron
outputs are nearly zero-centered due to input and layer normalization in
modern DNNs (Ioffe and Szegedy, 2015; Sola and Sevilla, 1997), SSC can be less
useful for many of them. Also, while SSC takes the relation of adjacent layers
into consideration, since each neuron is still a separate unit in SSC, the
relation of layers is modeled in the neuron-level. As introduced in Sec. 2,
the DNN hierarchy is formed by input feature re-use (e.g., processing object
shape at shallow layers and then texture at deep layers). The hierarchy is
generally encoded into layer outputs. NLC, by capturing the distribution of
layer outputs, is more desirable compared to SSC.

Incorporating Training Data. The development of a DNN involves a “test-and-
fix” procedure in which DNN is gradually fine-tuned to reduce its errors and
fit on training data. This way, training data generally reflects DNN’s
internal logic and property. We argue that ⑤DNN coverage should support
incorporating prior-knowledge extracted from training data. Existing criteria
incorporate training data to scope neuron output ranges or to detect corner-
case behaviors. Nevertheless, for some criteria, e.g., TKNC/TKNP, their hyper-
parameter $K$ depends on model structures instead of training data. NLC can
incorporate training data to estimate distributions of neuron outputs before
being used in online testing.

Implementation Considerations. DNN coverage criteria are often used in costly
DNN testing. According to the released code of existing criteria, we notice
that they are implemented in a loop-fashion which is slow. We find that
testing frameworks guided by these criteria spend most (over $80\%$) of the
time on coverage calculation. We re-implemented these criteria in a matrix-
fashion, i.e., the calculation is performed as a sequence of matrix
operations. Given that modern DL frameworks (e.g., PyTorch) can optimize
matrix operations and also use hardware optimizations (Chen et al., 2018;
Rotem et al., 2018; Ma et al., 2020b), the calculation is accelerated for over
$100$ times.

DNN coverage is often used to guide test input mutations. Since inputs are
gradually fed, it is preferred if computing coverage incrementally. Ideally,
given a new input, the cost for updating coverage should be roughly constant.
Since TKNP iterates over existing patterns and #patterns increases when more
data are produced, it does not support incremental computation. CC and SSC
suffer from similar drawbacks. In sum, we advocate that ⑥a coverage criterion
should support matrix-form computation to be optimizable by modern DL
frameworks and hardwares and ⑦a coverage criterion should support incremental
update.

Most existing criteria rely on hyper-parameters. When using existing criteria,
we find that coverage results are usually highly sensitive to hyper-
parameters, whereas existing works hardly provide guidance to decide hyper-
parameters under different scenarios. Viewing that deciding hyper-parameters
likely requires expertise (in both software testing and deep learning), we
advocate that ⑧a DNN coverage is desirable to be hyper-parameter free.

Comparison with Existing Criteria. Table 1 benchmarks existing DNN coverage
criteria (and NLC) w.r.t. the eight requirements summarized in this section.
Note that TKNC/TKNP considers the relative relation of neuron outputs and SSC
considers the sign relation between two neurons. They are deemed as partially
satisfying ②. Similarly, since CC counts #regions formed by several neurons,
it partially fulfills ③. Also, given that neuron outputs concentrate on center
points, the neuron output range overlays the high-density regions. We thus
regard KMNC, NBC and SNAC as partially satisfying ④. In contrast, we emphasize
that NLC can satisfy all these requirements, as will be introduced in Sec. 4.

Table 1. Bechmarking coverage criteria for DNN tesing. ✓, $\Diamond$, ✗ denote
support, partially support, and not support.

| NC | KMNC | NBC | SNAC | TKNC | TKNP | CC | SSC | NLC
---|---|---|---|---|---|---|---|---|---
① | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✓
② | ✗ | ✗ | ✗ | ✗ | $\Diamond$ | $\Diamond$ | ✗ | $\Diamond$ | ✓
③ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | $\Diamond$ | ✗ | ✓
④ | ✗ | $\Diamond$ | $\Diamond$ | $\Diamond$ | ✗ | ✗ | ✗ | ✗ | ✓
⑤ | ✓ | ✓ | ✓ | ✓ | ✗ | ✗ | ✓ | ✗ | ✓
⑥ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✗ | ✓
⑦ | ✓ | ✓ | ✓ | ✓ | ✓ | ✗ | ✗ | ✗ | ✓
⑧ | ✗ | ✗ | ✓ | ✓ | ✗ | ✗ | ✗ | ✓ | ✓

Figure 3. Four properties describing neuron output distributions. We take
these properties into account to form NLC.

##  4\. Design of NLC

As mentioned in Sec. 3.1, it’s generally difficult to precisely and
efficiently describe distributions approximated by DNNs (Rasmussen et al.,
1999; Reynolds, 2009; Xuan et al., 2001). Instead, NLC captures four key
properties of distributions, namely the divergence, correlation, shape, and
density, as depicted in Fig. 3. In Sec. 7, we present empirical results to
show that these properties are sufficient to constitute a criterion that
outperforms all existing works. We now elaborate on each property in details.

Figure 4. Output distribution of one neuron from ResNet50.

Measuring Activation in Continuous Space. Neuron outputs are continuous
floating-point numbers. Instead of discretizing their continuous outputs, we
directly measure them in the continuous space. We start with the case of one
neuron.

We randomly select one neuron from a pretrained ResNet50 and plot its output
distribution in Fig. 4(a) using all images in its training dataset. The x-axis
denotes the output value and the y-axis denotes the ratio of involved inputs.
Consistent with Fig. 1, output values converge to a certain point (zero in
this case). NLC directly measures how divergent (i.e., the activation) the
neuron output is in its continuous form by calculating the following variance:

(1) $\sigma_{n}^{2}=\mathbb{E}[(n-\mathbb{E}[n])(n-\mathbb{E}[n])],$

where $n$ is the output of a neuron. Overall, variance is widely-adopted for
characterizing the divergence of a collection of samples. Eq. 1 increases when
output values spread along the x-axis. In contrast, if most outputs are zero,
the variance will decrease, as in Fig. 4(b). Variance serves as an important
descriptor of neuron output distributions. A test suite is regarded as
comprehensive if it results in a high variance. Similarly, input mutations can
be launched towards the direction that increases variance. Comparing with
previous criteria, we require no discretization, thus taking all distinct
neuron outputs into account (in response to ①). In addition, Eq. 1 does not
ship with hyper-parameters (respond to ⑧).

Figure 5. Neurons having various correlations.

Characterizing Neuron Entanglement. As noted in Sec. 2, neurons in a layer are
entangled and jointly process input features. As empirically assessed in Fig.
1, neurons manifest distinct correlations under different tasks and for inputs
of different classes. For example, in Fig. 1(c), one neuron is positively
(e.g., class “1”) or negatively (e.g., class “9”) correlated with the other
neuron.

Fig. 5 presents three different correlations of two neurons, namely, no
correlation, positive correlation and negative correlation. Given that there
are more than one neuron, the DNN coverage should simultaneously consider the
divergence of each neuron and correlations among neurons. Eq. 1 uses variance
to describe divergence of a neuron’s output, i.e., $\sigma^{2}_{n_{1}}$ and
$\sigma^{2}_{n_{2}}$. Similarly, we use the covariance, a common metric for
joint variability of two variables, to characterize the correlation between
two neurons. Thus, the correlation between the two neurons is formulated as

(2)
$\varsigma_{n_{1},n_{2}}=\mathbb{E}[(n_{1}-\mathbb{E}[n_{1}])(n_{2}-\mathbb{E}[n_{2}])]=\varsigma_{n_{2},n_{1}}.$

$\varsigma_{n_{1},n_{2}}=0$ implies that $n_{1}$ and $n_{2}$ are not
correlated, whereas $\varsigma_{n_{1},n_{2}}>0$ denotes a positive correlation
between $n_{1}$ and $n_{2}$, i.e., $n_{1}$ will increase with $n_{2}$, and
vice verse. A higher $\varsigma_{n_{1},n_{2}}$ denotes a stronger correlation.
The same holds when $\varsigma_{n_{1},n_{2}}<0$. Taking Eq. 1 and Eq. 2 into
account, we simultaneously represent the divergence of each neuron and
correlations of neurons in a unified form as

(3) $\varSigma=\begin{bmatrix}\sigma^{2}_{n_{1}}&\varsigma_{n_{1},n_{2}}\\\
\varsigma_{n_{2},n_{1}}&\sigma^{2}_{n_{2}}\end{bmatrix},$

where $\varSigma$ is the covariance matrix of $n_{1}$ and $n_{2}$. As we show
in Fig. 5, the value of $\varsigma_{n_{1},n_{2}}$ also represents the
divergence along the “correlation direction” of two neurons. Thus, we use

(4) $\frac{1}{m\times m}\|\varSigma\|_{1}=\frac{1}{m\times
m}\sum\nolimits_{j=1}^{m}\left(\sum\nolimits_{i=1}^{m}|\varsigma_{n_{i},n_{j}}|\right),$

where $m$ is #neurons and $\varsigma_{n_{i},n_{i}}=\sigma^{2}_{n_{i}}$, to
represent the DNN coverage. The size of $\varSigma$ is $m\times m$ and
$\frac{1}{m\times m}$ works as the normalization term to eliminate the affect
of #neurons to the coverage values. In the case where more than two neurons
are correlated, e.g., $n_{i}$, $n_{j}$ and $n_{k}$, $\varSigma$ will
characterize the entanglement via $\varsigma_{n_{i},n_{j}}$,
$\varsigma_{n_{i},n_{k}}$ and $\varsigma_{n_{j},n_{k}}$. Hence, Eq. 4
facilitates addressing requirements ① and ②. Note that $\varSigma$ can be set
using the correlation term $\varsigma_{n_{i},n_{i}}$ decided by training data.
Therefore, it conceptually subsumes the neuron output range leveraged by KMNC
to recognize major DNN behaviors. The key difference is that $\varSigma$
denotes major behaviors as the majority of neuron correlations (i.e., the
shape of the distribution). Also, $\varSigma$ can be further refined in a
class conditional manner by extending the size to $c\times m\times m$ where
$c$ is #classes. It thus will be calculated by first indexed using the class
labels. In both two cases, NLC fulfills the requirement of ⑤.

We note that NLC employs Eq. 4 over all neurons in each layer. Thus, ③, which
champions modeling the distribution of neuron outputs in a layer, is taken
into account. Further, given a DNN contains multiple layers, the coverage of
DNN is computed as

(5) $\textsc{NLC}\ =\sum_{l}\frac{1}{m^{l}\times
m^{l}}\|{\varSigma}^{l}\|_{1},$

where $l$ is the layer index. A higher NLC indicates a more diverse test
suite. Test input mutations, accordingly, are expected to accumulate towards
directions that maximize NLC.

Capturing Distribution Shape. Unlike previous works where each neuron is
considered separately, we take neurons from the same layer as a group. As in
Fig. 1, the output distribution of neurons in the same layer is mostly
distinct under different tasks. Moreover, for the separated regions (in
different colors) under certain tasks (e.g., classification), they may also
have different shapes characterizing various DNN behaviors. Hence, we capture
a major behavior by describing the shape of a distribution. We now explain why
$\varSigma$ in Eq. 3 captures a distribution’s shape.

Figure 6. Transforming white noise to a desired distribution.

To ease the understanding, we first show how to transform a white noise (whose
covariance matrix is degenerated into an identity matrix $I$) to the
distribution formed by outputs from a group of neurons. Fig. 6(a) displays a
white noise $\mathcal{N}$ and Fig. 6(c) presents the output distribution of
two neurons, namely $x$ and $y$. Thus, the transformation can be decomposed
into two elementary operators — scaling and rotating. The scaling operator
spreads the two neuron outputs and the rotating operator introduces
correlations between $x$ and $y$. The rotating and scaling operations are
defined by rotation matrix and scaling matrix as

(6) $\mathcal{R}_{2\times 2}=\begin{bmatrix}\cos\theta&-\sin\theta\\\
\sin\theta&\cos\theta\\\ \end{bmatrix},\mathcal{S}_{2\times
2}=\begin{bmatrix}s_{x}&0\\\ 0&s_{y}\\\ \end{bmatrix},$

respectively. Thus, the output distribution can be represented as
$(\mathcal{R}\mathcal{S})\mathcal{N}$. Following Eq. 1 and Eq. 2, we have

(7) $\displaystyle\varSigma$
$\displaystyle=\mathbb{E}[(\mathcal{R}\mathcal{S}\mathcal{N}-\mathbb{E}[\mathcal{R}\mathcal{S}\mathcal{N}])(\mathcal{R}\mathcal{S}\mathcal{N}-\mathbb{E}[\mathcal{R}\mathcal{S}\mathcal{N}])^{\top}]$
$\displaystyle=(\mathcal{R}\mathcal{S})\mathbb{E}[(\mathcal{N}-\mathbb{E}[\mathcal{N}])(\mathcal{N}-\mathbb{E}[\mathcal{N}])^{\top}](\mathcal{R}\mathcal{S})^{\top}$
$\displaystyle=(\mathcal{R}\mathcal{S})I(\mathcal{R}\mathcal{S})^{\top}=(\mathcal{R}\mathcal{S})(\mathcal{R}\mathcal{S})^{\top},$

which indicates that covariance matrix $\varSigma$ in Eq. 3 encodes
transformations from a white noise to a desired distribution. Therefore, we
illustrate that the covariance matrix captures the shape of the output
distribution formed by outputs of neurons in a layer.

Figure 7. Density.

Responding to Local Density Change. Neuron outputs generally concentrate to
certain points to form clusters, and the density varies in the output space.
We first elaborate on what may introduce a local density change. Recall that
we deem corner-case behaviors as neuron outputs lying at the low-density
regions (e.g., boundary of one cluster), which are likely to trigger DNN
defects. Given that these outliers typically have much lower local-density,
their existence will lead to density change. Previous works (e.g., NBC, SNAC)
characterize the corner-case behavior as out-of-range outputs of a neuron.
Since neuron outputs will gather at multiple regions for certain tasks, some
rare outputs (i.e., the corner cases) still lie in the range decided by the
majority of neuron outputs. Consider Fig. 7(a) where the DNN outputs in red
are deemed as outliers. Nevertheless, since they are still in the output
ranges formed by all green dots, SNAC and NBC will not treat them as corner
case behaviors. In fact, the new red outputs will not induce coverage increase
for all previous criteria except CC, since CC divides the entire output space
into grids. However, CC requires a properly selected grid size, which is a
hyper-parameter configured by users.

Also, for certain cases where neuron outputs are separated (e.g., the
classifier in Fig. 1(c)), the appearance of a new major behavior (e.g., images
get classified as a new class) also leads to density change. As shown in Fig.
7(b), the newly-formed cluster of red dots denotes a new major behavior of the
DNN, nevertheless, NC possibly has no response since their values are lower
than the threshold.

We show that NLC responds to density change. For Fig. 7(a), the
$||\varSigma||_{1}$ of existing green dots is $13.2$. It will be updated as
$13.4$ given the new red dots, which will lead to a response to our criterion.
Whereas for the new yellow dots, since it stays close to the majority of
existing outputs, our criterion has no response. Meanwhile, for Fig. 7(b), the
$||\varSigma||_{1}$ will change from $13.2$ to $14.6$ when the cluster formed
by red dots appears. We thus state that our criterion can respond to density
change which is possibly introduced by corner-case behaviors and new major
behaviors. This way, NLC satisfies ④, which requires DNN coverage to take the
density of neuron outputs into account.

##  5\. Implementation Considerations

From Sec. 4, it is easy to see that NLC supports matrix-form computing and has
no hyper-parameters. Thus, NLC satisfies ⑥ and ⑧. We now clarify that NLC also
satisfies the requirement of incremental computing (requirement ⑦). We also
show that NLC supports batch computation, which is also vital as DNNs
generally take a batch of inputs and the batch size varies from $1$ to
hundreds. Let existing data be $\varmathbb{B}$, given a batch of new data $B$,
the covariance matrix $\varSigma$ (Eq. 4) of each layer can be calculated as

(8) $\displaystyle\varSigma$
$\displaystyle=\frac{|\varmathbb{B}|\times|B|\times(\mu_{\varmathbb{B}}-\mu_{B})(\mu_{\varmathbb{B}}-\mu_{B})^{\top}}{(|\varmathbb{B}|+|B|)^{2}}$
$\displaystyle+\frac{|\varmathbb{B}|\times\varSigma_{\varmathbb{B}}+|B|\times\varSigma_{B}}{|\varmathbb{B}|+|B|},$

where $\mu$ represents the mean of a collection of data. It is clear to see
that Eq. 8 does not iterate over existing data and update $\varSigma$
incrementally. Accordingly, NLC formed in Eq. 5 satisfies ⑦.

## Comparison with Surprise Adequacy

Three Surprise Adequacy (SA) (Kim et al., 2019, 2020), namely, Likelihood-
based SA (LSA), Distance-based SA (DSA) and Mahalanobis Distance-based SA
(MDSA) are proposed in previous works. All SAs measure the interest for a new
input based on its dissimilarity, which is a real value and can be regarded as
a distance, to historical inputs in terms of neuron outputs. Several coverage
criteria can be derived from SAs, in general, they first divided the range of
“distance” into slots and then count coverage as #covered slots. Conceptually,
they can be regarded as variants of CC since each distance-slot can be viewed
as a cluster and the threshold deciding new cluster is the slot size. The
difference is how to calculate the “distance”: CC employs Euclidean distance
but SA-based coverage criteria use SAs.

LSA characterizes the dissimilarity using density estimated by Gaussian kernel
function: a new input is more desired if it appears in a low-density region.
Note that a cluster is defined as a high-density region and a point introduces
a new cluster when it lies in a low-density region. That is, when solely
adopting LSA to measure the dissimilarity for a DNN input (e.g., a lower
density value), it is equivalent to prioritize inputs using CC (e.g., a higher
CC value). Also, despite LSA considers multiple neurons, it does not reflect
neuron correlation and treats neurons independently. LSA excludes neurons with
low output-variances; nevertheless, a lower variance of neuron outputs does
not necessarily indicate less significance, as a smaller output range also
induces lower variance. In fact, this is common since modern DNNs use
normalization layers to normalize neuron outputs around zero. Moreover, given
that modern DNNs have millions of neurons, the kernel density estimation in
LSA is infeasible for such extremely high-dimension variable.

For implementation consideration, both LSA and DAS do not support incremental
update (i.e., ⑦) and LSA has hyper-parameters which violates ⑧. We note that
both MDSA and NLC adopt covariance. However, we clarify that the two
“covariance” are used in distinct aspects. NLC characterizes how fresh inputs
change the neuron relation, or lead to a new distribution, using an actively-
updated covariance. NLC incrementally updates covariance given new inputs and
rollbacks the value if new input is not desired. Nevertheless, the covariance
in MDSA does not describe how neuron relation, or distribution, change given
new inputs. It is a pre-computed constant which, together with the output
mean, represents the distribution of historical neuron outputs, such that
Mahalanobis distance can be computed. We point out that the intuition behind
Mahalanobis distance assumes that historical neuron outputs follow a Gaussian
distribution, which is impractical given that neuron output distribution is
intractable and estimating this distribution is still an open problem.

##  6\. Evaluation Setup

NLC is implemented using PyTorch (ver. 1.9.0) with roughly 2,300 LOC. All
experiments are launched on one Intel Xeon CPU E5-2683 with 256GB RAM and one
Nvidia GeForce RTX 2080 GPU. We will introduce all target DNNs and datasets
along with each launched experiment in Sec. 7. We now introduce detailed
settings of DNN coverage criteria compared with NLC.

Neuron Coverage (NC). The authors of NC state that a neuron is “activated” if
its output is higher than a threshold $T$ (Pei et al., 2017). Some previous
works (Ma et al., [n.d.]) also evaluate NC following this setting. However,
according to the official codebase of NC (cod, [n.d.]), they first rescale all
neuron outputs in a layer to $[0,1]$ and the activation of one neuron is
decided on the rescaled value. We also implement this variant of NC (referred
to as NCS). NC is evaluated given $T\in\\{0,0.3,0.6\\}$ and for NCS,
$T\in\\{0.25,0.5,0.75\\}$.

K-Multisection Neuron Coverage (KMNC). KMNC has one hyper-parameter $K$ noting
the #segments for a neuron output. We choose $K$ in $\\{10,100,1000\\}$.

Top-K Neuron Coverage/Patterns (TKNC/TKNP). TKNC and TKNP monitor neurons with
top-$K$ highest outputs among neurons in a layer. We configure
$K\in\\{1,10,100\\}$.

Cluster-based Coverage (CC). CC denotes two layer-outputs as lying in two
clusters if their Euclidean distance is larger than a threshold $T$. $T$
primarily depends on specific DNNs. We introduce $T$ in each experiment.

SSC is specifically designed for ReLU-DNN, whereas modern DNNs have various
non-linear functions. Also, SSC does not support matrix-form and incremental
computing. Our preliminary study shows that due to a large number of neurons
in modern DNNs, SSC is not applicable (too slow). We thus omit to compare with
it.

##  7\. Evaluation

###  7.1. Assessing Test Suite Quality

We first compare NLC with existing criteria on its effectiveness to 1) assess
the diversity of test suites and 2) characterize the fault-revealing
capability of test suites.

Table 2. DNN Models used in Sec. 7.1. All image models are trained on CIFAR10
and ImageNet.

Model | #Neuron | #Layer | Remark
---|---|---|---
ResNet50 (He et al., 2016) | 26,570/27,560 | 54 | Non-sequential topology
VGG16_BN* (Simonyan and Zisserman, 2014) | 12,426/13,416 | 16 | Sequential topology
MobileNet-V2 (Howard et al., 2017) | 17,066/18,056 | 53 | Mobile devices
BigGAN (Brock et al., 2018) | 6,403/48,627 | 11/41 | Generative model
LSTM (Hochreiter and Schmidhuber, 1997) | 32,769 | 129 | Text model

  * •

*All image models have batch normalization (BN) layers.

Table 3. Datasets (train/test) used in Sec. 7.1. Each class has the same
number of images.

Dataset | CIFAR10 | ImageNet | IMDB
---|---|---|---
#Classes | 10 | 100 | 2
#Data | 50,000/10,000 | 100,000/5,000 | 17,500/17,500

Settings. We evaluate NLC on both discriminative and generative models. The
involved models and datasets are listed in Table 2 and Table 3. For
discriminative models, we choose VGG16, ResNet50, and MobileNetV2, which
represent popular models on mobile platforms and standard large-scale DNNs
with sequential and non-sequential topological structures. The three models
are trained on two datasets of different scales, namely, CIFAR10 (Krizhevsky
et al., 2009) and ImageNet (Deng et al., 2009). Models trained on CIFAR10 have
over $92\%$ test accuracy and those trained on ImageNet are provided by
PyTorch. CIFAR10 is composed of $32\times 32$ images labeled as ten classes.
ImageNet contains images of $1,000$ classes and the average image size is
$469\times 387$. To speed up the progress, we randomly select $100$ classes
from ImageNet. We also evaluate NLC on the text model, i.e., a LSTM
(Hochreiter and Schmidhuber, 1997) trained on the IMDB dataset (Maas et al.,
2011) for sentiment analysis (Feldman, 2013). Given that each layer in the
LSTM is unrolled to process sequential inputs, the unrolled layers are deemed
separate for computing coverage. For generative models, we choose the SOTA
model BigGAN. The BigGAN is also trained on CIFAR10 and ImageNet.

Table 4. Coverage achieved by different datasets on image models. CR and IN
denote CIFAR10 and ImageNet. Assessments matching ground truth are marked.

Criteria | Config. | DNN | CR | $\text{CR}_{\times 1}$ | $\text{CR}_{\times 10}$ | IN | $\text{IN}_{\times 1}$ | $\text{IN}_{\times 10}$
---|---|---|---|---|---|---|---|---
NC ($\%$) | $T$=$0$ | ResNet | 0.037 | 0.030 | 0.113 | 0.025 | 0.022 | 0.028
VGG | 0.096 | 0.145 | 0.177 | 0.007 | 0.007 | 0.015
MobileNet | 0.046 | 0.058 | 0.094 | 0 | 0 | 0.005
$T$=$0.3$ | ResNet | 0 | 0 | 0 | 0.036 | 0.018 | 0.037
VGG | 0.58 | 0.33 | 0.63 | 0 | 0 | 0.045
MobileNet | 0 | 0 | 0 | 0.016 | 0.022 | 0.038
$T$=$0.6$ | ResNet | 0 | 0 | 0 | 0 | 0 | 0.004
VGG | 0 | 0 | 0 | 0 | 0 | 0.002
MobileNet | 0 | 0 | 0 | 0.044 | 0.027 | 0.078
NCS ($\%$) | $T$=$0.25$ | ResNet | 0.026 | 0.031 | 0.031 | 0 | 0 | 0
VGG | 0.113 | 0.177 | 0.225 | 0 | 0 | 0
MobileNet | 0 | 0 | 0 | 0 | 0 | 0
$T$=$0.5$ | ResNet | 0.75 | 1.14 | 2.10 | 0 | 0 | 0.01
VGG | 0.56 | 0.77 | 1.09 | 0 | 0 | 0.01
MobileNet | 0.02 | 0.01 | 0.05 | 0 | 0 | 0
$T$=$0.75$ | ResNet | 2.15 | 2.52 | 4.54 | 0.13 | 0.21 | 0.38
VGG | 2.49 | 3.25 | 4.27 | 0.02 | 0 | 0.02
MobileNet | 1.57 | 1.69 | 2.17 | 0.02 | 0.02 | 0.03
KMNC ($\%$) | $K$=$10$ | ResNet | 8.89 | 40.01 | 40.50 | 4.10 | 4.25 | 5.59
VGG | 7.33 | 55.25 | 55.50 | 4.19 | 8.34 | 9.17
MobileNet | 8.53 | 8.97 | 10.43 | 4.67 | 4.52 | 6.82
$K$=$100$ | ResNet | 8.52 | 26.96 | 28.37 | 2.17 | 5.08 | 5.14
VGG | 7.54 | 45.25 | 45.60 | 1.36 | 5.22 | 5.26
MobileNet | 4.81 | 10.02 | 10.19 | 1.43 | 2.15 | 3.01
$K$=$1,000$ | ResNet | 3.99 | 10.64 | 10.78 | 1.87 | 4.29 | 4.31
VGG | 2.84 | 12.36 | 12.50 | 0.91 | 2.61 | 2.68
MobileNet | 4.61 | 8.38 | 8.69 | 2.01 | 3.44 | 3.92
NBC ($\%$) | N/A | ResNet | 0 | 1.75 | 4.85 | 0.13 | 0.48 | 1.20
VGG | 0.27 | 2.04 | 2.12 | 0.08 | 0.13 | 0.23
MobileNet | 0.003 | 2.46 | 2.51 | 0.15 | 0.20 | 0.32
SNAC ($\%$) | N/A | ResNet | 0 | 0.97 | 2.62 | 0.14 | 0.57 | 0.73
VGG | 0.53 | 1.52 | 1.64 | 0.13 | 0.01 | 0.23
MobileNet | 0 | 1.41 | 2.37 | 0.15 | 0.27 | 0.38
TKNC ($\%$) | $K$=$1$ | ResNet | 0.20 | 0.23 | 0.41 | 0.06 | 0.03 | 0.10
VGG | 0.81 | 1.20 | 1.97 | 0.29 | 0.13 | 0.44
MobileNet | 0.24 | 0.13 | 0.28 | 0.10 | 0.06 | 0.20
$K$=$10$ | ResNet | 0.38 | 0.36 | 0.68 | 0.11 | 0.02 | 0.14
VGG | 2.29 | 2.66 | 3.83 | 0.01 | 0.01 | 0.01
MobileNet | 0.21 | 0.12 | 0.31 | 0.03 | 0.03 | 0.03
$K$=$50$ | ResNet | 0.24 | 0.23 | 0.45 | 0.03 | 0.01 | 0.06
VGG | 3.07 | 3.35 | 4.57 | 0.01 | 0.02 | 0.02
MobileNet | 0.17 | 0.22 | 0.38 | 0.02 | 0 | 0.05
TKNP ($\\#$) | $K$=$1$ | ResNet | 9,995 | 9,586 | 80,561 | 4,900 | 3,954 | 23,384
VGG | 6,060 | 6,809 | 36,887 | 4,882 | 3,386 | 17,187
MobileNet | 9,998 | 9,924 | 90,537 | 4,900 | 5,000 | 48,083
$K$=$10$ | ResNet | 10,000 | 10,000 | 100,000 | 4,901 | 5,000 | 50,000
VGG | 10,000 | 10,000 | 100,000 | 4,901 | 5,000 | 50,000
MobileNet | 10,000 | 10,000 | 100,000 | 4,901 | 5,000 | 50,000
$K$=$50$ | ResNet | 1,034 | 434 | 1,823 | 4,901 | 5,000 | 50,000
VGG | 10,000 | 10,000 | 100,000 | 4,901 | 5,000 | 50,000
MobileNet | 694 | 650 | 1,665 | 4,901 | 5,000 | 50,000
CC* ($\\#$) |  $T$=$10$ $T$=$1,000$ | ResNet | 55 | 44 | 60 | 4,945 | 1,333 | 9,787
VGG | 147 | 137 | 168 | 14,532 | 2,148 | 7,681
MobileNet | 37 | 29 | 38 | 4,947 | 4,614 | 43,613
$T$=$20$ $T$=$2,000$ | ResNet | 19 | 19 | 23 | 4,918 | 397 | 9,771
VGG | 51 | 48 | 63 | 11,914 | 954 | 1,606
MobileNet | 9 | 10 | 11 | 4,946 | 2,618 | 12,466
$T$=$50$ $T$=$5,000$ | ResNet | 9 | 7 | 9 | 4,130 | 256 | 8,263
VGG | 22 | 21 | 22 | 4,526 | 426 | 571
MobileNet | 7 | 4 | 7 | 4,943 | 346 | 531
NLC | N/A | ResNet | 1.03 | 0.05 | 0.47 | 6006.38 | 11.00 | 113.37
VGG | 403.95 | 0 | 0 | 20327.50 | 49.50 | 413.50
MobileNet | 0.61 | 0.12 | 0.23 | 10693.50 | 86.25 | 757.25

  * •

*$d\in\\{10,20,50\\}$ for models trained on CIFAR10 and $d\in\\{1000,2000,5000\\}$ for models trained on ImageNet.

Table 5. Coverage achieved by different datasets on text models. Assessments
matching ground truth are marked.

Criteria | Config. | DNN | IMDB | $\text{IMDB}_{\times 1}$ | $\text{IMDB}_{\times 10}$
---|---|---|---|---|---
NC ($\%$) |  $T$=$0$ | LSTM | 1.25 | 2.32 | 2.41
$T$=$0.3$ | LSTM | 0.42 | 0.87 | 1.52
$T$=$0.6$ | LSTM | 0.17 | 0.41 | 0.72
NCS ($\%$) |  $T$=$0.25$ | LSTM | 0.012 | 0.018 | 0.034
$T$=$0.50$ | LSTM | 0.015 | 0.018 | 0.027
$T$=$0.75$ | LSTM | 2.191 | 1.001 | 2.554
KMNC ($\%$) |  $K$=$10$ | LSTM | 7.68 | 3.69 | 12.11
$K$=$100$ | LSTM | 1.92 | 2.99 | 5.31
$K$=$1,000$ | LSTM | 0.05 | 0.08 | 0.15
NBC | N/A | LSTM | 0.12 | 0.04 | 0.13
SNAC | N/A | LSTM | 0.11 | 0.03 | 0.03
TKNC ($\%$) |  $K$=$1$ | LSTM | 0.28 | 0.19 | 0.67
$K$=$10$ | LSTM | 0.50 | 0.39 | 0.96
$K$=$50$ | LSTM | 1.34 | 1.20 | 2.86
TKNP ($\\#$) |  $K$=$1$ | LSTM | 20,252 | 12,118 | 101,789
$K$=$10$ | LSTM | 6,515 | 2,224 | 8,602
$K$=$50$ | LSTM | 11,830 | 4,633 | 20,479
CC ($\\#$) |  $T$=$10$ | LSTM | 266 | 265 | 283
$T$=$20$ | LSTM | 134 | 137 | 146
$T$=$50$ | LSTM | 57 | 1 | 65
NLC | N/A | LSTM | 1279.81 | 11.01 | 132.99

Table 6. Coverage achieved by different datasets on generative models.
$\text{BigGAN}_{\text{C}}$ and $\text{BigGAN}_{\text{I}}$ refer to BigGAN
trained on CIFAR10 and ImageNet. Assessments matching ground truth are marked.

Criteria | Config. | DNN | Normal | ${N/2}$ | ${N/10}$ | ${C/2}$ | ${C/10}$
---|---|---|---|---|---|---|---
NC | $T$=$0$ | $\text{BigGAN}_{\text{C}}$ | 97.19 | 96.89 | 96.31 | 96.56 | 94.45
$\text{BigGAN}_{\text{I}}$ | 85.88 | 85.65 | 85.05 | 85.56 | 84.59
$T$=$0.3$ | $\text{BigGAN}_{\text{C}}$ | 59.21 | 55.61 | 44.90 | 54.41 | 40.76
$\text{BigGAN}_{\text{I}}$ | 14.41 | 13.82 | 12.03 | 12.96 | 10.47
$T$=$0.6$ | $\text{BigGAN}_{\text{C}}$ | 16.40 | 15.40 | 13.62 | 14.12 | 9.68
$\text{BigGAN}_{\text{I}}$ | 6.92 | 6.56 | 5.50 | 6.07 | 5.14
NCS | $T$=$0.25$ | $\text{BigGAN}_{\text{C}}$ | 99.97 | 99.97 | 99.95 | 99.97 | 99.95
$\text{BigGAN}_{\text{I}}$ | 99.43 | 99.42 | 99.40 | 99.42 | 99.39
$T$=$0.5$ | $\text{BigGAN}_{\text{C}}$ | 99.34 | 99.30 | 99.02 | 99.25 | 98.73
$\text{BigGAN}_{\text{I}}$ | 94.18 | 93.96 | 93.44 | 93.87 | 93.44
$T$=$0.75$ | $\text{BigGAN}_{\text{C}}$ | 86.66 | 84.88 | 79.70 | 82.85 | 76.90
$\text{BigGAN}_{\text{I}}$ | 81.64 | 81.30 | 80.17 | 80.98 | 77.61
KMNC | $K$=$10$ | $\text{BigGAN}_{\text{C}}$ | 54.72 | 56.00 | 54.71 | 54.24 | 52.44
$\text{BigGAN}_{\text{I}}$ | 58.15 | 57.06 | 58.14 | 56.20 | 56.82
$K$=$100$ | $\text{BigGAN}_{\text{C}}$ | 21.54 | 21.45 | 21.84 | 21.83 | 21.48
$\text{BigGAN}_{\text{I}}$ | 22.66 | 22.33 | 22.59 | 22.20 | 22.32
$K$=$1000$ | $\text{BigGAN}_{\text{C}}$ | 3.04 | 3.04 | 3.04 | 3.04 | 3.03
$\text{BigGAN}_{\text{I}}$ | 3.07 | 3.08 | 3.07 | 3.07 | 3.06
NBC | N/A | $\text{BigGAN}_{\text{C}}$ | 0.22 | 0.09 | 0.04 | 0.09 | 0.10
$\text{BigGAN}_{\text{I}}$ | 0.54 | 0.21 | 0.21 | 0.03 | 0.06
SNAC | N/A | $\text{BigGAN}_{\text{C}}$ | 0.02 | 0.03 | 0.03 | 0.03 | 0.03
$\text{BigGAN}_{\text{I}}$ | 0.03 | 0.07 | 0.04 | 0.64 | 0.14
TKNC | $K$=$1$ | $\text{BigGAN}_{\text{C}}$ | 31.69 | 27.75 | 16.95 | 27.16 | 15.56
$\text{BigGAN}_{\text{I}}$ | 16.79 | 14.56 | 9.62 | 13.11 | 5.91
$K$=$10$ | $\text{BigGAN}_{\text{C}}$ | 62.64 | 58.89 | 48.34 | 58.46 | 45.14
$\text{BigGAN}_{\text{I}}$ | 34.92 | 33.77 | 29.90 | 32.44 | 22.62
$K$=$50$ | $\text{BigGAN}_{\text{C}}$ | 83.96 | 81.45 | 75.03 | 81.23 | 73.54
$\text{BigGAN}_{\text{I}}$ | 42.02 | 41.68 | 40.58 | 41.27 | 38.08
TKNP | $K$=$1$ | $\text{BigGAN}_{\text{C}}$ | 31,415 | 15,843 | 3,193 | 15,779 | 3,134
$\text{BigGAN}_{\text{I}}$ | 32,000 | 16,000 | 3,200 | 16,000 | 3,200
$K$=$10$ | $\text{BigGAN}_{\text{C}}$ | 32,000 | 16,000 | 3,200 | 16,000 | 3,200
$\text{BigGAN}_{\text{I}}$ | 32,000 | 16,000 | 3,200 | 16,000 | 3,200
$K$=$50$ | $\text{BigGAN}_{\text{C}}$ | 32,000 | 16,000 | 3,200 | 16,000 | 3,200
$\text{BigGAN}_{\text{I}}$ | 10,894 | 6,898 | 2,088 | 6,997 | 2,178
CC | $T$=$50$ | $\text{BigGAN}_{\text{C}}$ | 347 | 302 | 175 | 232 | 89
$\text{BigGAN}_{\text{I}}$ | 1,204 | 921 | 485 | 780 | 324
$T$=$100$ | $\text{BigGAN}_{\text{C}}$ | 90 | 70 | 40 | 50 | 18
$\text{BigGAN}_{\text{I}}$ | 323 | 266 | 147 | 239 | 108
$T$=$200$ | $\text{BigGAN}_{\text{C}}$ | 27 | 25 | 13 | 23 | 7
$\text{BigGAN}_{\text{I}}$ | 105 | 99 | 77 | 95 | 64
NLC | N/A | $\text{BigGAN}_{\text{C}}$ | 1051.63 | 776.29 | 653.62 | 280.67 | 178.92
$\text{BigGAN}_{\text{I}}$ | 3596.89 | 3306.88 | 3141.02 | 2636.64 | 1462.11

Diversity. To assess the diversity of test suites for discriminative models,
we construct two datasets of different diversity using schemes noted as
$\times 1$ and $\times 10$. For the $\times 1$ scheme, we randomly choose
$100$ images from the test data and add white noise to produce mutated images
(the total number of mutated images in $\text{test}_{\times 1}$ equals to the
size of test). The white noise is truncated within $[-0.1,0.1]$ to preserve
the appearance of images. Given that text is discrete, it is infeasible to add
white noise. We thus randomly shuffle words in the $100$ selected sentences to
produce meaningless sentences. The $\times 10$ scheme follows the same
procedure, but the number of the produced data is $10$ times of the test data.
The diversity of these datasets (ground truth of Table 4 and Table 5) are
ranked as $\text{test}>\text{test}_{\times 10}>\text{test}_{\times 1}$,
because test contains over 10K diverse images in real-world datasets, whereas
$\text{test}_{\times 10}$ and $\text{test}_{\times 1}$ are generated by
(slightly) mutating 100 real images.

For the generative model, it generates images by sampling from a fixed
distribution (i.e., the normal distribution). Since the generation procedure
is conditioned on a given class label, we construct datasets of different
diversity by following the $Normal$, $N/x$ and $C/x$ schemes (see Table 6).
For the $Normal$ scheme, we sample total $m$ inputs from the normal
distribution and each class has the same number of inputs. For the $N/x$
scheme, we only keep $1/x$ of inputs from each class, whereas for the $C/x$
scheme, we only keep $1/x$ of classes. We set $m$ to $32,000$ and choose
$x\in\\{2,10\\}$. Since inputs conditioned on different classes are all
sampled from normal distribution, behaviors of generative models are primarily
decided by the class labels. Thus, the diversity of these datasets (ground
truth of Table 6) are ranked as: $Normal>N/2>N/10>C/2>C/10$.

Given that each model is deployed using the training data, we show the
increased coverage of the corresponding test data and its variants in Table 4,
Table 5 and Table 6 for image models, text models, and generative models,
respectively. All experiments are launched for five times to reduce
randomness.

Existing criteria (except for NBC and SNAC) require extra hyper-parameters,
and their evaluation results are largely determined by these hyper-parameters.
For instance, all variants of CIFAR10 test data have zero coverage when $T$ of
NC is $0.6$, whereas they reach a saturation coverage when $K$ of TKNP is $10$
(i.e., #patterns equals to #inputs) despite they are still evaluated on same
models. Moreover, the hyper-parameter $T$ of CC is model specific, for
instance, $T=10$ is suitable for ResNet trained on CIFAR10, but is too small
if the ResNet is trained on ImageNet — any input will form a new cluster. We
thus increase $T$ 100 times for models trained on ImageNet. Again, without
prior knowledge on setting hyper-parameters, it is obscure to adopt these
criteria in real-life usage. In contrast, NLC is hyper-parameter free,
enabling an “out-of-the-box” usage.

For most cases of image models and text models, the $\times 1$ scheme and the
test dataset have comparable results, and the $\times 10$ scheme has the
highest coverage. Given datasets created by $\times 1$ have identical size
with the test dataset, we interpret that existing neuron coverage criteria are
more sensitive to the number of data samples rather than the diversity.
Nevertheless, the coverage assessed by NLC are consistent with the diversity
of these datasets (i.e., the ground truth). Moreover, despite the number of
$\times 10$ variant is 10 times of test data, its reflected coverage on NLC is
smaller, which indicates that NLC successfully reflects the diversity of the
inputs.

For generative models like BigGAN, inputs for both training and test phases
are random variables sampled from the normal distribution. Infinite “training
data” exists, and therefore, KMNC, NBC and SNAC are infeasible to use, as they
assign each neuron an output range decided by the training data. In practice,
we find that coverage measured by them tend to be random. In contrast, NLC, by
default, can be used with no training data, and it can be adopted in both
discriminative and generative models. For the remaining coverage criteria,
most of their results are ranked as $Normal>N/2>C/2>N/10>C/10$, which further
reflects that prior criteria are more sensitive to the number of inputs
instead of their diversity. Since previous criteria analyze neuron outputs
separately, feeding more inputs might possiby increase the chance of
activating more neurons in a linear manner. In contrast, NLC analyzes the
formed distributions among neurons, where most “trivial” inputs will not
influence the correlations or distributions. In contrast, since a diverse test
suite possibly uncovers different correlations among neurons, NLC becomes more
responsible for a diverse test suite.

Table 7. Coverage achieved by test data and AEs of CIFAR10. Assessments
matching ground truth are marked.

| Data | NC | NCS | KMNC | NBC | SNAC | TKNC | TKNP | CC | NLC
---|---|---|---|---|---|---|---|---|---|---
$T$=$0$ |  $T$=$0.75$ |  $K$=$100$ |  $K$=$10$ |  $K$=$50$ |  $T$=$10$
($\%$) | ($\%$) | ($\%$) | ($\%$) | ($\%$) | ($\%$) | ($\\#$) | ($\\#$)
ResNet | Test | 0.04 | 2.15 | 8.52 | 0 | 0 | 0.38 | 1,034 | 55 | 1.03
CW | 0.11 | 0.90 | 0 | 3.94 | 2.73 | 0.18 | 31 | 5 | 2.44
PGD | 0.24 | 1.43 | 0 | 13.83 | 23.22 | 0.35 | 680 | 29 | 22.92
VGG | Test | 0.10 | 2.49 | 7.54 | 0.27 | 0.53 | 2.29 | 10,000 | 147 | 403.95
CW | 0.24 | 0.20 | 0 | 5.03 | 7.08 | 0.20 | 9,542 | 125 | 931.03
PGD | 0.20 | 1.69 | 0.74 | 12.64 | 15.23 | 1.32 | 4,997 | 142 | 4749.08
MobileNet | Test | 0.05 | 1.57 | 4.81 | 0 | 0 | 0.21 | 694 | 37 | 0.61
CW | 0.19 | 0.02 | 0 | 1.77 | 1.62 | 0.14 | 172 | 13 | 0.83
PGD | 0.51 | 0.36 | 0 | 9.71 | 10.39 | 0.16 | 299 | 16 | 13.56

Figure 8. Adversarial perturbations.

Fault-Revealing Capability. To evaluate the fault-revealing capabilities of
test suites, we construct adversarial examples (AE) using two adversarial
attack algorithms, Carlini/Wagner (CW) (Carlini and Wagner, 2017) and Project
Gradient Descent (PGD) (Madry et al., 2017). CW is optimization-based, and it
generates AE according to certain optimization objectives. PGD is loss
function-based, and it adds perturbations on images which are guided by
gradients of the victim DNN. We truncate the adversarial perturbations within
$[-0.3,0.3]$. Perturbations added on AEs are different from white noise, as
shown in Fig. 8. AEs are generated using the training data, and all algorithms
attacking the three models reach over $98\%$ success rates. That is, more than
$N\times 0.98$ ($N$ is the size of training data) AEs can trigger erroneous
behaviors. We also find that the incorrect predictions uniformly distribute
across all classes. To benchmark criteria’s capability of revealing AEs, we
check if a criterion can notably respond to AEs; that is, our ground truth in
Table 7 specifies that a criterion should achieve higher coverage on CW/PGD
compared to using test data.

Similar with the previous settings, we first calculate the coverage using
training data and then record the increased coverage of test data and AEs. The
results are presented in Table 7. NCS, TKNC, TKNP and CC have higher coverage
for the test data than AEs. We interpret that these criteria are not
correlated with the fault-revealing capability of a test suite. Note that AEs
are generated using training data and the perturbations are truncated within a
small range. We thus interpret that AEs are regarded as similar with the
training data by these criteria. Furthermore, given that $\times 1$ scheme in
Table 4 increases comparable coverage with the test data, these criteria seem
more sensitive to white noise instead of adversarial perturbations despite
that the white noise lies in an even smaller range $[-0.1,0.1]$.

KMNC has nearly no response to AEs, but NBC and SNAC respond notably towards
AEs. The reason is straightforward: we find that AEs primarily lead to out-of-
range neuron outputs. NLC generally measures how divergent a layer output is
and responds to the density change of layer outputs. Therefore, the out-of-
range neuron outputs, which either induce a higher variance or introduce a
low-density layer output, can be captured by NLC. NC responds more to AEs when
compared with NCS. The key difference between NC and NCS is that NCS operates
on the rescaled values, thus it monitors the relative top percent neurons. If
all neuron outputs are increased with the same value, there will be no
coverage increase.

###  7.2. Guiding Input Mutation

This section uses existing criteria and NLC as the objective to guide input
mutation. This denotes a typical feedback-driven (fuzz) testing setting, where
inputs are mutated to maximize the feedback yielded by the criteria. We
evaluate the mutated inputs on 1) #triggered faults, 2) naturalness, and 3)
diversity of the erroneous behaviors.

Table 8. Transformations for mutating images.

Type | Operator | Remark
---|---|---
Pixel-Level | contrast, brightness | Robustness
Affine | translation, scaling, rotation | Shape bias
Texture-Level | blurring, stylizing | Texture bias

1 Transformation Set: $T$; Fuzzing Seed: $S$;

2 Tested DNN: $D$; Criterion: $C$; $num\leftarrow 50$;

3 while  _not terminate()_ do

4 $s=sample(S)$;

5 for  _$i\leftarrow 0$ to $num$ by $1$_ do

6 $t=sample(T)$;

7 $\hat{s}\leftarrow t(s)$;

8 if  _$is\\_valid(\hat{s},s)$ and $coverage\\_inc(C,D)$_ then

9 $S.add(\hat{s})$;

10 $update\\_coverage(C)$;

11 break;

12

13 end if

14

15 end for

16

17 end while

Algorithm 1 Fuzzing algorithm. Figure 9. Stylizing and blurring.

Setting. We use the same image classification models and datasets as in Sec.
7.1. Table 8 lists all mutation methods. Existing efforts mostly mutate images
at the pixel level or using affine operators (Zhang et al., 2018; Pei et al.,
2017). However, DNNs trained on natural pictures have a texture-bias (Geirhos
et al., 2019; Brendel and Bethge, 2019), meaning they generate predictions
overly depending on an image’s texture. Concerning that operators in Table 8
cannot fully examine DNN behaviors, we prepare texture-level transformations.
Studies in the AI community show that training DNNs on stylized images (see
Fig. 9) reduces texture-bias (Geirhos et al., 2019). Similarly, blurring, a
convolutional operator, smooths texture while keeping object shape in an
image. Stylization and blurring are hence used as texture-level
transformations.

We launch fuzzing using either prior coverage criteria or NLC according to
Alg. 1. $terminate()$ returns True when reaching 10K iterations.
$is\\_valid()$ is adopted from (Xie et al., 2018), which deems a mutation as
valid if 1) the #changed-pixels is less than $\alpha\times$ #pixels or 2) the
maximum of changed pixel value is less than $\beta\times 255$. We set $\alpha$
to $0.2$ and $\beta$ to $0.4$. As a baseline, we do not check validity and
coverage (line 8 in Alg. 1) for random mutation. That is, line 8 in Alg. 1
always yields true for random mutation. We randomly select 1K inputs from the
test dataset as the fuzzing seeds.

Table 9. #Faults, naturalness and erroneous behaviors of ResNet trained on
ImageNet.

| Rand | NC | NCS | KMNC | NBC | SNAC | TKNC | TKNP | CC | NLC
---|---|---|---|---|---|---|---|---|---|---
$T$=$0$ |  $T$=$0.75$ |  $K$=$100$ |  $K$=$10$ |  $K$=$50$ |  $T$=$1000$
#Faults | 6,488 | 911 | 3,309 | 0 | 5 | 8 | 3,127 | 7,190 | 7,902 | 9,975
#Image | 10,000 | 1,143 | 4,157 | 0 | 6 | 10 | 3,967 | 10,000 | 10,000 | 10,000
Rate (%) | 64.88 | 79.70 | 79.60 | 0 | 83.33 | 80.00 | 78.83 | 71.90 | 79.02 | 99.75
IS | 8.05 | 7.61 | 8.05 | N/A | 1.85 | 2.62 | 7.82 | 7.77 | 7.13 | 8.14
FID | 131.85 | 125.31 | 99.35 | N/A | 367.84 | 372.49 | 99.87 | 101.08 | 102.84 | 98.87
#Class | 595 | 367 | 672 | 0 | 4 | 7 | 668 | 711 | 708 | 732
Entropy | 0.82 | 0.92 | 0.91 | 0 | 0.96 | 0.97 | 0.90 | 0.87 | 0.86 | 0.88

Faults. The #triggered faults of ResNet trained on ImageNet are presented in
Table 9. We also evaluate fuzzing ResNet on trained CIFAR10, a smaller
dataset. We note that those results are highly consistent with Table 9.

Images mutated under the guidance of NLC (the last column) have the highest
error triggering rates compared with random mutation (second column) and other
criteria, especially for NBC and SNAC. The fuzzing guided by KMNC even has no
output. Recall that these criteria denote a neuron as activated if its output
is higher than a threshold or is out-of-range. Since modern DNNs frequently
normalize inputs and intermediate neuron outputs, layer outputs tend to
concentrate to certain regions (as reflected in Fig. 1). Without fine-grained
feedbacks such as gradients, mutated images can hardly flip an unactivated
neuron into activated. Nevertheless, we find that the degree of entanglement
among neurons can vary w.r.t. mutated inputs. Thus, NLC is very effective to
serve the fuzzing guidance, achieving the highest #faults and fault-triggering
rates. TKNP and CC have decent performance; TKNP records the patterns of
activated neurons (Sec. 3.2), which, to some extent, can reflect the
distribution of layer outputs and entanglement of neurons. CC measures the
#regions formed by several neurons, which is correlated with the divergence of
DNN outputs.

We also measure how each operator in Table 8 can mutate images and increase
coverage. An interesting finding is that texture-level transformations are
mostly preferred by fuzzing guided by all criteria, including NLC. Previous
criteria primarily use stylizing transformation whereas NLC prefers both
blurring and stylizing. This indicates that previous criteria and NLC all
explore DNN’s texture-bias. Moreover, since NLC describes the entanglement of
neurons, it captures DNN behaviors more comprehensively.

Naturalness. Contemporary testing works have pointed out the importance of
preserving naturalness of mutated images (Harel-Canada et al., 2020). We
measure the naturalness of mutated inputs under each criterion; a good
criterion should lead to mutations that mostly preserve the naturalness. We
use Inception Score (IS) (Salimans et al., 2016) and Fr$\grave{e}$chet
Inception Distance (FID) (Heusel et al., 2017), which are widely used in the
AI community to assess the naturalness of images, as the metrics. A higher IS
score is better, whereas a lower FID score indicates better naturalness. The
evaluation results are also listed in Table 9.

The IS and FID scores of random mutation are regarded as the baseline.
Overall, mutated images guided by NLC have the best performance regarding both
IS and FID scores. We note that mutated images guided by NBC and SNAC
manifests relatively low naturalness. Since these two criteria denote a neuron
as activated if it has out-of-range outputs, its guided mutations incline to
largely modify pixel values. We find that the mutated images become less
recognizable, e.g., a region in an image gets covered by a black block.
Overall, since neurons jointly process features in an input image, mutation
with the aim of covering different neuron entanglements are, holistically,
“bounded” by features.

Diversity of Erroneous Behaviors. A higher diversity of erroneous behaviors
indicates uncovering a practically larger vulnerability surface of DNN models.
Overall, a collection of fault-triggering images are regarded as more diverse
if they cover more classes. In case that #covered classes is equal, we further
use the scaled entropy, $-\frac{1}{|C|}\sum p_{c}\log p_{c}$ where $p_{c}$ is
the ratio of incorrect outputs predicted as class $c$ and $|C|$ is the
#classes, to assess the diversity; a higher entropy is better. The results are
also presented in Table 9. It is seen that fault-triggering images generated
by using NLC as the guidance cover the most classes. We thus envision
equipping fuzz testing frameworks with NLC to likely identify more and diverse
defects from real-world critical DNN systems. Diversity evaluation on CIFAR10
also reports promising and consistent results.

##  8\. Related Work

In addition to testing critieria reviewed in Sec. 3.2, we review the following
two aspects in terms of DNN testing.

Testing Oracles. Preparing a validation dataset with labelled data is the
traditional way to benchmark DNNs. However, standard dataset, with limited
labelled data, can only reflect the hold-out accuracy (Pei et al., 2017;
Ribeiro et al., 2020; Zhang et al., 2020; Sun et al., 2020). Many corner cases
(e.g., a snowy traffic scene) can be rarely included. Currently, the SE
community primarily uses testing schemes carrying implicit oracles. For
example, metamorphic testing can determine if a DNN model responds
consistently to mutated inputs (Dwarakanath et al., 2018; Zhang et al., 2018;
Tian et al., 2018; Wang and Su, 2020). Similarly, differential testing (Tian
et al., 2018; Pei et al., 2017) evaluates if a group of DNN models make
consistent predictions when given mutant inputs. Domain-specific oracles for
model robustness (Tjeng et al., 2017), fairness (Dwork et al., 2012;
Zliobaite, 2017), and interpretability (Herman, 2017; Tian et al., 2021) have
also been proposed.

Input Mutation. DNN models excel at interpreting real-world data such as
images and text. Pixel-level mutations are used to mutate images (Pei et al.,
2017). However, pixel-level mutations can be inefficient, and extending such
byte-level mutations to discrete data like text is obscure. The use of
affiline modifications (Tian et al., 2018) such as image rotation, scaling,
and shearing has recently been proposed. Some domain-specific transformations
are also defined over text or images, e.g., applying foggy filters (Tian et
al., 2018; Zhang et al., 2018; Yuan et al., 2021; Ma et al., 2020a; Dwork et
al., 2012; Zliobaite, 2017; Sun et al., 2020). Some AI models are also used to
change inputs, such as generating synonyms for a masked sentence (He et al.,
2020) or synthesizing severe driving scenes (Zhang et al., 2018).

##  9\. Conclusion

Inspired by the observations that DNNs are designed to approximate
distributions, we propose eight design principles for DNN testing criteria. We
design NLC, a testing criterion that satisfies all eight design requirements.
NLC describes distributions of single neuron output, neuron relations in a
layer, and layer hierarchical relations in a DNN. We show that NLC can
facilitate better test input assessment and serve as guidance of fuzz testing.

## References

  * (1)
  * cod ([n.d.]) [n.d.].  The official codebase of DeepXplore.  https://github.com/peikexin9/deepxplore.
  * Bellman (1966) Richard Bellman. 1966\.  Dynamic programming.  _Science_ 153, 3731 (1966), 34–37.
  * Bengio et al. (2013) Yoshua Bengio, Aaron Courville, and Pascal Vincent. 2013\.  Representation learning: A review and new perspectives.  _IEEE transactions on pattern analysis and machine intelligence_ 35, 8 (2013), 1798–1828.
  * Bishop et al. (1995) Christopher M Bishop et al. 1995\.  _Neural networks for pattern recognition_.  Oxford university press.
  * Block (1962) Hans-Dieter Block. 1962\.  The perceptron: A model for brain functioning.  _Reviews of Modern Physics_ 34, 1 (1962), 123\.
  * Brendel and Bethge (2019) Wieland Brendel and Matthias Bethge. 2019.  Approximating cnns with bag-of-local-features models works surprisingly well on imagenet.  _arXiv preprint arXiv:1904.00760_ (2019).
  * Brock et al. (2018) Andrew Brock, Jeff Donahue, and Karen Simonyan. 2018\.  Large Scale GAN Training for High Fidelity Natural Image Synthesis. In _International Conference on Learning Representations_.
  * Carlini and Wagner (2017) Nicholas Carlini and David Wagner. 2017.  Towards evaluating the robustness of neural networks. In _2017 ieee symposium on security and privacy (sp)_. IEEE, 39–57.
  * Chen et al. (2018) Tianqi Chen, Thierry Moreau, Ziheng Jiang, Lianmin Zheng, Eddie Yan, Haichen Shen, Meghan Cowan, Leyuan Wang, Yuwei Hu, Luis Ceze, et al. 2018\.  $\\{$TVM$\\}$: An automated end-to-end optimizing compiler for deep learning. In _13th $\\{$USENIX$\\}$ Symposium on Operating Systems Design and Implementation ($\\{$OSDI$\\}$ 18)_. 578–594.
  * Deng et al. (2009) Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. 2009\.  Imagenet: A large-scale hierarchical image database. In _2009 IEEE conference on computer vision and pattern recognition_. Ieee, 248–255.
  * Deng (2012) Li Deng. 2012.  The mnist database of handwritten digit images for machine learning research [best of the web].  _IEEE Signal Processing Magazine_ 29, 6 (2012), 141–142.
  * Dwarakanath et al. (2018) Anurag Dwarakanath, Manish Ahuja, Samarth Sikand, Raghotham M. Rao, R. P. Jagadeesh Chandra Bose, Neville Dubash, and Sanjay Podder. 2018\.  Identifying Implementation Bugs in Machine Learning Based Image Classifiers Using Metamorphic Testing. In _ISSTA_.
  * Dwork et al. (2012) Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. 2012.  Fairness through awareness. In _Proceedings of the 3rd innovations in theoretical computer science conference_. 214–226.
  * Feldman (2013) Ronen Feldman. 2013\.  Techniques and applications for sentiment analysis.  _Commun. ACM_ 56, 4 (2013), 82–89.
  * Geirhos et al. (2019) Robert Geirhos, Patricia Rubisch, Claudio Michaelis, Matthias Bethge, Felix A. Wichmann, and Wieland Brendel. 2019.  ImageNet-trained CNNs are biased towards texture; increasing shape bias improves accuracy and robustness.. In _International Conference on Learning Representations_.  https://openreview.net/forum?id=Bygh9j09KX
  * Goodfellow et al. (2014) Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. 2014\.  Generative adversarial nets. In _Advances in neural information processing systems_. 2672–2680.
  * Harel-Canada et al. (2020) Fabrice Harel-Canada, Lingxiao Wang, Muhammad Ali Gulzar, Quanquan Gu, and Miryung Kim. 2020\.  Is neuron coverage a meaningful measure for testing deep neural networks?. In _Proceedings of the 28th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering_. 851–862.
  * He et al. (2016) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. 2016\.  Deep residual learning for image recognition. In _Proceedings of the IEEE conference on computer vision and pattern recognition_. 770–778.
  * He et al. (2020) Pinjia He, Clara Meister, and Zhendong Su. 2020.  Structure-invariant testing for machine translation. In _ICSE_.
  * Herman (2017) Bernease Herman. 2017\.  The promise and peril of human evaluation for model interpretability.  _arXiv preprint arXiv:1711.07414_ (2017), 8.
  * Heusel et al. (2017) Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. 2017\.  Gans trained by a two time-scale update rule converge to a local nash equilibrium. In _Advances in neural information processing systems_. 6626–6637.
  * Hochreiter and Schmidhuber (1997) Sepp Hochreiter and Jürgen Schmidhuber. 1997.  Long short-term memory.  _Neural computation_ 9, 8 (1997), 1735–1780.
  * Howard et al. (2017) Andrew G Howard, Menglong Zhu, Bo Chen, Dmitry Kalenichenko, Weijun Wang, Tobias Weyand, Marco Andreetto, and Hartwig Adam. 2017\.  Mobilenets: Efficient convolutional neural networks for mobile vision applications.  _arXiv preprint arXiv:1704.04861_ (2017).
  * Ioffe and Szegedy (2015) Sergey Ioffe and Christian Szegedy. 2015.  Batch normalization: Accelerating deep network training by reducing internal covariate shift. In _International conference on machine learning_. PMLR, 448–456.
  * Kim et al. (2019) Jinhan Kim, Robert Feldt, and Shin Yoo. 2019.  Guiding Deep Learning System Testing Using Surprise Adequacy. In _ICSE_.
  * Kim et al. (2020) Jinhan Kim, Jeongil Ju, Robert Feldt, and Shin Yoo. 2020\.  Reducing dnn labelling cost using surprise adequacy: An industrial case study for autonomous driving. In _Proceedings of the 28th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering_. 1466–1476.
  * Kingma and Welling (2013) Diederik P Kingma and Max Welling. 2013.  Auto-encoding variational bayes.  _arXiv preprint arXiv:1312.6114_ (2013).
  * Krizhevsky et al. (2009) Alex Krizhevsky, Geoffrey Hinton, et al. 2009\.  Learning multiple layers of features from tiny images.  (2009).
  * Lee et al. (2018) Hsin-Ying Lee, Hung-Yu Tseng, Jia-Bin Huang, Maneesh Singh, and Ming-Hsuan Yang. 2018.  Diverse image-to-image translation via disentangled representations. In _Proceedings of the European conference on computer vision (ECCV)_. 35–51.
  * Liu et al. (2018) Yu Liu, Fangyin Wei, Jing Shao, Lu Sheng, Junjie Yan, and Xiaogang Wang. 2018\.  Exploring disentangled feature representation beyond face identification. In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_. 2080–2089.
  * Ma et al. ([n.d.]) Lei Ma, Felix Juefei-Xu, Jiyuan Sun, Chunyang Chen, Ting Su, Fuyuan Zhang, Minhui Xue, Bo Li, Li Li, Yang Liu, et al. [n.d.].  DeepGauge: Comprehensive and multi-granularity testing criteria for gauging the robustness of deep learning systems. In _Proceedings of the 33rd ACM/IEEE International Conference on Automated Software Engineering_ _(ASE 2018)_.
  * Ma et al. (2020b) Lingxiao Ma, Zhiqiang Xie, Zhi Yang, Jilong Xue, Youshan Miao, Wei Cui, Wenxiang Hu, Fan Yang, Lintao Zhang, and Lidong Zhou. 2020b.  Rammer: Enabling Holistic Deep Learning Compiler Optimizations with rTasks. In _14th $\\{$USENIX$\\}$ Symposium on Operating Systems Design and Implementation ($\\{$OSDI$\\}$ 20)_. 881–897.
  * Ma et al. (2020a) Pingchuan Ma, Shuai Wang, and Jin Liu. 2020a.  Metamorphic Testing and Certified Mitigation of Fairness Violations in NLP Models. In _IJCAI_. 458–465.
  * Maas et al. (2011) Andrew Maas, Raymond E Daly, Peter T Pham, Dan Huang, Andrew Y Ng, and Christopher Potts. 2011\.  Learning word vectors for sentiment analysis. In _Proceedings of the 49th annual meeting of the association for computational linguistics: Human language technologies_. 142–150.
  * Madry et al. (2017) Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. 2017\.  Towards deep learning models resistant to adversarial attacks.  _arXiv preprint arXiv:1706.06083_ (2017).
  * Odena and Goodfellow (2018) Augustus Odena and Ian Goodfellow. 2018.  Tensorfuzz: Debugging neural networks with coverage-guided fuzzing.  _arXiv preprint arXiv:1807.10875_ (2018).
  * Pei et al. (2017) Kexin Pei, Yinzhi Cao, Junfeng Yang, and Suman Jana. 2017\.  DeepXplore: Automated Whitebox Testing of Deep Learning Systems. In _Proceedings of the 26th Symposium on Operating Systems Principles_ (Shanghai, China) _(SOSP ’17)_. ACM, New York, NY, USA, 1–18.  https://doi.org/10.1145/3132747.3132785
  * Rasmussen et al. (1999) Carl Edward Rasmussen et al. 1999\.  The infinite Gaussian mixture model.. In _NIPS_ , Vol. 12. Citeseer, 554–560.
  * Ren et al. (2021) Jie Ren, Mingjie Li, Zexu Liu, and Quanshi Zhang. 2021\.  Interpreting and Disentangling Feature Components of Various Complexity from DNNs. In _International Conference on Machine Learning_. PMLR, 8971–8981.
  * Reynolds (2009) Douglas A Reynolds. 2009\.  Gaussian mixture models.  _Encyclopedia of biometrics_ 741 (2009), 659–663.
  * Ribeiro et al. (2020) Marco Tulio Ribeiro, Tongshuang Wu, Carlos Guestrin, and Sameer Singh. 2020.  Beyond Accuracy: Behavioral Testing of NLP Models with CheckList. In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_. Association for Computational Linguistics, Online, 4902–4912.  https://doi.org/10.18653/v1/2020.acl-main.442
  * Rosenblatt (1958) Frank Rosenblatt. 1958\.  The perceptron: a probabilistic model for information storage and organization in the brain.  _Psychological review_ 65, 6 (1958), 386.
  * Rotem et al. (2018) Nadav Rotem, Jordan Fix, Saleem Abdulrasool, Garret Catron, Summer Deng, Roman Dzhabarov, Nick Gibson, James Hegeman, Meghan Lele, Roman Levenstein, et al. 2018\.  Glow: Graph lowering compiler techniques for neural networks.  _arXiv preprint arXiv:1805.00907_ (2018).
  * Salimans et al. (2016) Tim Salimans, Ian Goodfellow, Wojciech Zaremba, Vicki Cheung, Alec Radford, and Xi Chen. 2016\.  Improved techniques for training gans.  _Advances in neural information processing systems_ 29 (2016), 2234–2242.
  * Schmidhuber (2015) Jürgen Schmidhuber. 2015\.  Deep learning in neural networks: An overview.  _Neural networks_ 61 (2015), 85–117.
  * Simonyan and Zisserman (2014) Karen Simonyan and Andrew Zisserman. 2014.  Very deep convolutional networks for large-scale image recognition.  _arXiv preprint arXiv:1409.1556_ (2014).
  * Sola and Sevilla (1997) Jorge Sola and Joaquin Sevilla. 1997.  Importance of input data normalization for the application of neural networks to complex industrial problems.  _IEEE Transactions on nuclear science_ 44, 3 (1997), 1464–1468.
  * Sun et al. (2018) Youcheng Sun, Xiaowei Huang, Daniel Kroening, James Sharp, Matthew Hill, and Rob Ashmore. 2018\.  Testing deep neural networks.  _arXiv preprint arXiv:1803.04792_ (2018).
  * Sun et al. (2020) Zeyu Sun, Jie M Zhang, Mark Harman, Mike Papadakis, and Lu Zhang. 2020.  Automatic testing and improvement of machine translation. In _Proceedings of the ACM/IEEE 42nd International Conference on Software Engineering_. 974–985.
  * Tian et al. (2021) Yongqiang Tian, Shiqing Ma, Ming Wen, Yepang Liu, Shing-Chi Cheung, and Xiangyu Zhang. 2021\.  To what extent do DNN-based image classification models make unreliable inferences?  _Empirical Software Engineering_ 26, 5 (2021), 1–40.
  * Tian et al. (2018) Yuchi Tian, Kexin Pei, Suman Jana, and Baishakhi Ray. 2018\.  DeepTest: Automated Testing of Deep-neural-network-driven Autonomous Cars _(ICSE ’18)_.
  * Tjeng et al. (2017) Vincent Tjeng, Kai Xiao, and Russ Tedrake. 2017.  Evaluating robustness of neural networks with mixed integer programming.  _arXiv preprint arXiv:1711.07356_ (2017).
  * Wang and Su (2020) Shuai Wang and Zhendong Su. 2020.  Metamorphic Object Insertion for Testing Object Detection Systems. In _ASE_.
  * Xie et al. (2018) Xiaofei Xie, Lei Ma, Felix Juefei-Xu, Hongxu Chen, Minhui Xue, Bo Li, Yang Liu, Jianjun Zhao, Jianxiong Yin, and Simon See. 2018.  Coverage-guided fuzzing for deep neural networks.  _arXiv preprint arXiv:1809.01266_ (2018).
  * Xuan et al. (2001) Guorong Xuan, Wei Zhang, and Peiqi Chai. 2001.  EM algorithms of Gaussian mixture model and hidden Markov model. In _Proceedings 2001 International Conference on Image Processing (Cat. No. 01CH37205)_ , Vol. 1. IEEE, 145–148.
  * Yuan et al. (2021) Yuanyuan Yuan, Shuai Wang, Mingyue Jiang, and Tsong Yueh Chen. 2021.  Perception Matters: Detecting Perception Failures of VQA Models Using Metamorphic Testing. In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_. 16908–16917.
  * Zeiler and Fergus (2014) Matthew D Zeiler and Rob Fergus. 2014.  Visualizing and understanding convolutional networks. In _European conference on computer vision_. Springer, 818–833.
  * Zhang et al. (2020) Jie M Zhang, Mark Harman, Lei Ma, and Yang Liu. 2020\.  Machine learning testing: Survey, landscapes and horizons.  _IEEE Transactions on Software Engineering_ (2020).
  * Zhang et al. (2018) Mengshi Zhang, Yuqun Zhang, Lingming Zhang, Cong Liu, and Sarfraz Khurshid. 2018.  DeepRoad: GAN-based Metamorphic Testing and Input Validation Framework for Autonomous Driving Systems. In _ASE_.
  * Zliobaite (2017) Indre Zliobaite. 2017\.  Fairness-aware machine learning: a perspective.  _arXiv preprint arXiv:1708.00754_ (2017).