Evaluating the Robustness of Neural Networks: An Extreme Value Theory Approach

Introduction

Recent studies have highlighted the lack of robustness in state-of-the-art neural network models, e.g., a visually imperceptible adversarial image can be easily crafted to mislead a well-trained network (Szegedy et al., 2013; Goodfellow et al., 2015; Chen et al., 2017a). Even worse, researchers have identified that these adversarial examples are not only valid in the digital space but also plausible in the physical world (Kurakin et al., 2016a; Evtimov et al., 2017). The vulnerability to adversarial examples calls into question safety-critical applications and services deployed by neural networks, including autonomous driving systems and malware detection protocols, among others.

In the literature, studying adversarial examples of neural networks has twofold purposes: (i) security implications: devising effective attack algorithms for crafting adversarial examples, and (ii) robustness analysis: evaluating the intrinsic model robustness to adversarial perturbations to normal examples. Although in principle the means of tackling these two problems are expected to be independent, that is, the evaluation of a neural network’s intrinsic robustness should be agnostic to attack methods, and vice versa, existing approaches extensively use different attack results as a measure of robustness of a target neural network. Specifically, given a set of normal examples, the attack success rate and distortion of the corresponding adversarial examples crafted from a particular attack algorithm are treated as robustness metrics. Consequently, the network robustness is entangled with the attack algorithms used for evaluation and the analysis is limited by the attack capabilities. More importantly, the dependency between robustness evaluation and attack approaches can cause biased analysis. For example, adversarial training is a commonly used technique for improving the robustness of a neural network, accomplished by generating adversarial examples and retraining the network with corrected labels. However, while such an adversarially trained network is made robust to attacks used to craft adversarial examples for training, it can still be vulnerable to unseen attacks.

We highlight the main contributions of this paper as follows:

We propose a novel robustness metric called CLEVER, which is short for Cross Lipschitz Extreme Value for nEtwork Robustness. To the best of our knowledge, CLEVER is the first robustness metric that is attack-independent and can be applied to any arbitrary neural network classifier and scales to large networks for ImageNet.

The proposed CLEVER score is well supported by our theoretical analysis on formal robustness guarantees and the use of extreme value theory. Our robustness analysis extends the results in Hein & Andriushchenko (2017) from continuously differentiable functions to a special class of non-differentiable functions – neural+ networks with ReLU activations.

Background and Related work

2 Existing Defense Methods

Since the discovery of vulnerability to adversarial examples (Szegedy et al., 2013), various defense methods have been proposed to improve the robustness of neural networks. The rationale for defense is to make a neural network more resilient to adversarial perturbations, while ensuring the resulting defended model still attains similar test accuracy as the original undefended network. Papernot et al. proposed defensive distillation (Papernot et al., 2016), which uses the distillation technique (Hinton et al., 2015) and a modified softmax function at the final layer to retrain the network parameters with the prediction probabilities (i.e., soft labels) from the original network. Zantedeschi et al. (2017) showed that by changing the ReLU function to a bounded ReLU function, a neural network can be made more resilient. Another popular defense approach is adversarial training, which generates and augments adversarial examples with the original training data during the network training stage. On MNIST, the adversarially trained model proposed by Madry et al. (2017) can successfully defend a majority of adversarial examples at the price of increased network capacity. Model ensemble has also been discussed to increase the robustness to adversarial examples (Tramèr et al., 2017; Liu et al., 2017). In addition, detection methods such as feature squeezing (Xu et al., 2017) and example reforming (Meng & Chen, 2017) can also be used to identify adversarial examples. However, the CW attack is shown to be able to bypass 10 different detection methods (Carlini & Wagner, 2017a). In this paper, we focus on evaluating the intrinsic robustness of a neural network model to adversarial examples. The effect of detection methods is beyond our scope.

3 Theoretical Robustness Guarantees for Neural Networks

Szegedy et al. (2013) compute global Lipschitz constant for each layer and use their product to explain the robustness issue in neural networks, but the global Lipschitz constant often gives a very loose bound. Hein & Andriushchenko (2017) gave a robustness lower bound using a local Lipschitz continuous condition and derived a closed-form bound for a multi-layer perceptron (MLP) with a single hidden layer and softplus activation. Nevertheless, a closed-form bound is hard to derive for a neural network with more than one hidden layer. Wang et al. (2016) utilized terminologies from topology to study robustness. However, no robustness bounds or estimates were provided for neural networks. On the other hand, works done by Ehlers (2017); Katz et al. (2017a; b); Huang et al. (2017) focus on formally verifying the viability of certain properties in neural networks for any possible input, and transform this formal verification problem into satisfiability modulo theory (SMT) and large-scale linear programming (LP) problems. These SMT or LP based approaches have high computational complexity and are only plausible for very small networks.

Intuitively, we can use the distortion of adversarial examples found by a certain attack algorithm as a robustness metric. For example, Bastani et al. (2016) proposed a linear programming (LP) formulation to find adversarial examples and use the distortions as the robustness metric. They observe that the LP formulation can find adversarial examples with smaller distortions than other gradient-based attacks like L-BFGS (Szegedy et al., 2013). However, the distortion found by these algorithms is an upper bound of the true minimum distortion and depends on specific attack algorithms. These methods differ from our proposed robustness measure CLEVER, because CLEVER is an estimation of the lower bound of the minimum distortion and is independent of attack algorithms. Additionally, unlike LP-based approaches which are impractical for large networks, CLEVER is computationally feasible for large networks like Inception-v3. The concept of minimum distortion and upper/lower bound will be formally defined in Section 3.

Analysis of Formal Robustness Guarantees for a Classifier

Suppose $\Delta_{p,\text{min}}$ is the minimum adversarial distortion of $\bm{x_{0}}$. A lower bound of $\Delta_{p,\text{min}}$, denoted by $\beta_{L}$ where $\beta_{L}\leq\Delta_{p,\text{min}}$, is defined such that any perturbed examples of $\bm{x_{0}}$ with $\|\bm{\delta}\|_{p}\leq\beta_{L}$ are not adversarial examples.

Suppose $\Delta_{p,\text{min}}$ is the minimum adversarial distortion of $\bm{x_{0}}$. An upper bound of $\Delta_{p,\text{min}}$, denoted by $\beta_{U}$ where $\beta_{U}\geq\Delta_{p,\text{min}}$, is defined such that there exists an adversarial example of $\bm{x_{0}}$ with $\|\bm{\delta}\|_{p}\geq\beta_{U}$.

where $L_{q}=\max\{\|\nabla h(\bm{x})\|_{q}:\bm{x}\in S\},\nabla h(\bm{x})=(\frac{\partial h(\bm{x})}{\partial x_{1}},\cdots,\frac{\partial h(\bm{x})}{\partial x_{d}})^{\top}$ is the gradient of $h(\bm{x})$, and $\frac{1}{p}+\frac{1}{q}=1,1\leq p,q\leq\infty$.

Given Lemma 3.1, we then provide a formal guarantee to the lower bound $\beta_{L}$.

The intuitions behind Theorem 3.2 is shown in Figure 1 with an one-dimensional example. The function value $g(x)=f_{c}(x)-f_{j}(x)$ near point $x_{0}$ is inside a double cone formed by two lines passing $(x_{0},g(x_{0}))$ and with slopes equal to $\pm L_{q}$, where $L_{q}$ is the (local) Lipschitz constant of $g(x)$ near $x_{0}$. In other words, the function value of $g(x)$ around $x_{0}$, i.e. $g(x_{0}+\delta)$ can be bounded by $g(x_{0})$, $\delta$ and the Lipschitz constant $L_{q}$. When $g(x_{0}+\delta)$ is decreased to 0, an adversarial example is found and the minimal change of $\delta$ is $\frac{g(x_{0})}{L_{q}}$. The complete proof is deferred to Appendix A.

$L_{q}^{j}$ is the Lipschitz constant of the function involving cross terms: ${f_{c}(\bm{x})-f_{j}(\bm{x})}$, hence we also call it cross Lipschitz constant following (Hein & Andriushchenko, 2017).

To distinguish our analysis from (Hein & Andriushchenko, 2017), we show in Corollary 2 that we can obtain the same result in (Hein & Andriushchenko, 2017) by Theorem 3.2. In fact, the analysis in (Hein & Andriushchenko, 2017) is a special case of our analysis because the authors implicitly assume Lipschitz continuity on $f_{i}(\bm{x})$ when requiring $f_{i}(\bm{x})$ to be continuously differentiable. They use local Lipschitz constant ($L_{q,x_{0}}$) instead of global Lipschitz constant ($L_{q}$) to obtain a tighter bound in the adversarial perturbation $\bm{\delta}$.

An important use case of Theorem 3.2 and Corollary 2 is the bound for targeted attack:

Assume the same notation as in Theorem 3.2 and Corollary 2. For a specified target class $j$, we have \|\bm{\delta}\|_{p}\leq\min\big{\{}\frac{f_{c}(\bm{x_{0}})-f_{j}(\bm{x_{0}})}{L_{q,x_{0}}^{j}},R\big{\}}.

In addition, we further extend Theorem 3.2 to a special case of non-differentiable functions – neural networks with ReLU activations. In this case the Lipchitz constant used in Lemma 3.1 can be replaced by the maximum norm of directional derivative, and our analysis above will go through.

Let $h(\cdot)$ be a $l$-layer ReLU neural network with $W_{i}$ as the weights for layer $i$. We ignore bias terms as they don’t contribute to gradient.

The CLEVER Robustness Metric via Extreme Value Theory

In this section, we provide an algorithm to compute the robustness metric CLEVER with the aid of extreme value theory, where CLEVER can be viewed as an efficient estimator of the lower bound $\beta_{L}$ and is the first attack-agnostic score that applies to any neural network classifiers. Recall in Section 3 we show that the lower bound of network robustness is associated with $g(\bm{x_{0}})$ and its cross Lipschitz constant $L_{q,x_{0}}^{j}$, where $g(\bm{x_{0}})=f_{c}(\bm{x_{0}})-f_{j}(\bm{x_{0}})$ is readily available at the output of a classifier and $L_{q,x_{0}}^{j}$ is defined as $\max_{\bm{x}\in B_{p}(\bm{x}_{0},R)}\|\nabla g(\bm{x})\|_{q}$. Although $\nabla g(\bm{x})$ can be calculated easily via back propagation, computing $L_{q,x_{0}}^{j}$ is more involved because it requires to obtain the maximum value of $\|\nabla g(\bm{x})\|_{q}$ in a ball. Exhaustive search on low dimensional $\bm{x}$ in $B_{p}(\bm{x}_{0},R)$ seems already infeasible, not to mention the image classifiers with large feature dimensions of our interest. For instance, the feature dimension $d=784,3072,150528$ for MNIST, CIFAR and ImageNet respectively.

One approach to compute $L_{q,x_{0}}^{j}$ is through sampling a set of points $\bm{x}^{(i)}$ in a ball $B_{p}(\bm{x}_{0},R)$ around $\bm{x}_{0}$ and taking the maximum value of $\|\nabla g(\bm{x}^{(i)})\|_{q}$. However, a significant amount of samples might be needed to obtain a good estimate of $\max\|\nabla g(\bm{x})\|_{q}$ and it is unknown how good the estimate is compared to the true maximum. Fortunately, Extreme Value Theory ensures that the maximum value of random variables can only follow one of the three extreme value distributions, which is useful to estimate $\max\|\nabla g(\bm{x})\|_{q}$ with only a tractable number of samples.

It is worth noting that although Wood & Zhang (1996) also applied extreme value theory to estimate the Lipschitz constant. However, there are two main differences between their work and this paper. First of all, the sampling methodology is entirely different. Wood & Zhang (1996) calculates the slopes between pairs of sample points whereas we directly take samples on the norm of gradient as in Lemma 3.1. Secondly, the functions considered in Wood & Zhang (1996) are only one-dimensional as opposed to the high-dimensional classification functions considered in this paper. For comparison, we show in our experiment that the approach in Wood & Zhang (1996), denoted as SLOPE in Table 5.3 and Figure 4f, perform poorly for high-dimensional classifiers such as deep neural networks.

When sampling a point $\bm{x}$ uniformly in $B_{p}(\bm{x}_{0},R)$, $\|\nabla g(\bm{x})\|_{q}$ can be viewed as a random variable characterized by a cumulative distribution function (CDF). For the purpose of illustration, we derived the CDF for a 2-layer neural network in Theorem D.1.The theorem and proof are deferred to Appendix D. For any neural networks, suppose we have $n$ samples $\{\|\nabla g(\bm{x}^{(i)})\|_{q}\}$, and denote them as a sequence of independent and identically distributed (iid) random variables $Y_{1},Y_{2},\cdots,Y_{n}$, each with CDF $F_{Y}(y)$. The CDF of $\max\{Y_{1},\cdots,Y_{n}\}$, denoted as $F_{Y}^{n}(y)$, is called the limit distribution of $F_{Y}(y)$. Fisher-Tippett-Gnedenko theorem says that $F_{Y}^{n}(y)$, if exists, can only be one of the three family of extreme value distributions – the Gumbel class, the Fréchet class and the reverse Weibull class.

If there exists a sequence of pairs of real numbers $(a_{n},b_{n})$ such that $a_{n}>0$ and $\lim_{n\to\infty}F_{Y}^{n}(a_{n}y+b_{n})=G(y)$, where $G$ is a non-degenerate distribution function, then $G$ belongs to either the Gumbel class (Type I), the Fréchet class (Type II) or the Reverse Weibull class (Type III) with their CDFs as follows:

Theorem 4.1 implies that the maximum values of the samples follow one of the three families of distributions. If $g(\bm{x})$ has a bounded Lipschitz constant, $\|\nabla g(\bm{x}^{(i)})\|_{q}$ is also bounded, thus its limit distribution must have a finite right end-point. We are particularly interested in the reverse Weibull class, as its CDF has a finite right end-point (denoted as $a_{W}$). The right end-point reveals the upper limit of the distribution, known as the extreme value. The extreme value is exactly the unknown local cross Lipschitz constant $L_{q,\bm{x}_{0}}^{j}$ we would like to estimate in this paper. To estimate $L_{q,\bm{x}_{0}}^{j}$, we first generate $N_{s}$ samples of $\bm{x}^{(i)}$ over a fixed ball $B_{p}(\bm{x_{0}},R)$ uniformly and independently in each batch with a total of $N_{b}$ batches. We then compute $\|\nabla g(\bm{x}^{(i)})\|_{q}$ and store the maximum values of each batch in set $S$. Next, with samples in $S$, we perform a maximum likelihood estimation of reverse Weibull distribution parameters, and the location estimate $\hat{a}_{W}$ is used as an estimate of $L_{q,\bm{x}_{0}}^{j}$.

2 Compute CLEVER: a robustness score of neural network classifiers

Given an instance $\bm{x_{0}}$, its classifier $f(\bm{x_{0}})$ and a target class $j$, a targeted CLEVER score of the classifier’s robustness can be computed via $g(\bm{x_{0}})$ and $L_{q,x_{0}}^{j}$. Similarly, untargeted CLEVER scores can be computed. With the proposed procedure of estimating $L_{q,x_{0}}^{j}$ described in Section 4.1, we summarize the flow of computing CLEVER score for both targeted attacks and un-targeted attacks in Algorithm 1 and 2, respectively.

Experimental Results

We conduct experiments on CIFAR-10 (CIFAR for short), MNIST, and ImageNet data sets. For the former two smaller datasets CIFAR and MNIST, we evaluate CLEVER scores on four relatively small networks: a single hidden layer MLP with softplus activation (with the same number of hidden units as in (Hein & Andriushchenko, 2017)), a 7-layer AlexNet-like CNN (with the same structure as in (Carlini & Wagner, 2017b)), and the 7-layer CNN with defensive distillation (Papernot et al., 2016) (DD) and bounded ReLU (Zantedeschi et al., 2017) (BReLU) defense techniques employed.

For ImageNet data set, we use three popular deep network architectures: a 50-layer Residual Network (He et al., 2016) (ResNet-50), Inception-v3 (Szegedy et al., 2016) and MobileNet (Howard et al., 2017). They were chosen for the following reasons: (i) they all yield (close to) state-of-the-art performance among equal-sized networks; and (ii) their architectures are significantly different with unique building blocks, i.e., residual block in ResNet, inception module in Inception net, and depthwise separable convolution in MobileNet. Therefore, their diversity in network architectures is appropriate to test our robustness metric. For MobileNet, we set the width multiplier to 1.0, achieving a $70.6\%$ accuracy on ImageNet. We used public pretrained weights for all ImageNet modelsPretrained models can be downloaded at https://github.com/tensorflow/models/tree/master/research/slim.

In all our experiments, we set the sampling parameters $N_{b}=500$, $N_{s}=1024$ and $R=5$. For targeted attacks, we use 500 test-set images for CIFAR and MNIST and use 100 test-set images for ImageNet; for each image, we evaluate its targeted CLEVER score for three targets: a random target class, a least likely class (the class with lowest probability when predicting the original example), and the top-2 class (the class with largest probability except for the true class, which is usually the easiest target to attack). We also conduct untargeted attacks on MNIST and CIFAR for 100 test-set images, and evaluate their untargeted CLEVER scores. Our experiment code is publicly availableSource code is available at https://github.com/huanzhang12/CLEVER.

2 Fitting Gradient Norm samples with Reverse Weibull distributions

We fit the cross Lipschitz constant samples in $S$ (see Algorithm 1) with reverse Weibull class distribution to obtain the maximum likelihood estimate of the location parameter $\hat{a}_{W}$, scale parameter $\hat{b}_{W}$ and shape parameter $\hat{c}_{W}$, as introduced in Theorem 4.1. To validate that reverse Weibull distribution is a good fit to the empirical distribution of the cross Lipschitz constant samples, we conduct Kolmogorov-Smirnov goodness-of-fit test (a.k.a. K-S test) to calculate the K-S test statistics $D$ and corresponding $p$-values. The null hypothesis is that samples $S$ follow a reverse Weibull distribution.

Figure 3 plots the probability distribution function of the cross Lipschitz constant samples and the fitted Reverse Weibull distribution for images from various data sets and network architectures. The estimated MLE parameters, $p$-values, and the K-S test statistics $D$ are also shown. We also calculate the percentage of examples whose estimation have $p$-values greater than 0.05, as illustrated in Figure 3. If the $p$-value is greater than 0.05, the null hypothesis cannot be rejected, meaning that the underlying data samples fit a reverse Weibull distribution well. Figure 3 shows that all numbers are close to 100%, validating the use of reverse Weibull distribution as an underlying distribution of gradient norm samples empirically. Therefore, the fitted location parameter of reverse Weibull distribution (i.e., the extreme value), $\hat{a}_{W}$, can be used as a good estimation of local cross Lipschitz constant to calculate the CLEVER score. The exact numbers are shown in Table 3 in Appendix E.

3 Comparing CLEVER Score with Attack-specific Network Robustness

4 Time v.s. Estimation Accuracy

Conclusion

In this paper, we propose the CLEVER score, a novel and generic metric to evaluate the robustness of a target neural network classifier to adversarial examples. Compared to the existing robustness evaluation approaches, our metric has the following advantages: (i) attack-agnostic; (ii) applicable to any neural network classifier; (iii) comes with strong theoretical guarantees; and (iv) is computationally feasible for large neural networks. Our extensive experiments show that the CLEVER score well matches the practical robustness indication of a wide range of natural and defended networks.

Acknowledgment. Luca Daniel and Tsui-Wei Weng are partially supported by MIT-Skoltech program and MIT-IBM Watson AI Lab. Cho-Jui Hsieh and Huan Zhang acknowledge the support of NSF via IIS-1719097.

References

Appendix

According to Lemma 3.1, the assumption that $g(\bm{x}):=f_{c}(\bm{x})-f_{j}(\bm{x})$ is Lipschitz continuous with Lipschitz constant $L_{q}^{j}$ gives

Let $\bm{x}=\bm{x_{0}}+\bm{\delta}$ and $\bm{y}=\bm{x_{0}}$ in (4), we get

which can be rearranged into the following form

When $g(\bm{x_{0}}+\bm{\delta})=0$, an adversarial example is found. As indicated by (5), $g(\bm{x_{0}}+\bm{\delta})$ is lower bounded by $g(\bm{x_{0}})-L_{q}^{j}\|\bm{\delta}\|_{p}$. If $\|\bm{\delta}\|_{p}$ is small enough such that $g(\bm{x_{0}})-L_{q}^{j}\|\bm{\delta}\|_{p}\geq 0$, no adversarial examples can be found:

Finally, to achieve $\operatorname*{argmax}_{1\leq i\leq K}f_{i}(\bm{x_{0}}+\bm{\delta})=c$, we take the minimum of the bound on $\|\bm{\delta}\|_{p}$ in (A) over $j\neq c$. I.e. if

the classifier decision can never be changed and the attack will never succeed. ∎

B Proof of Corollary 2

By Lemma 3.1 and let $g=f_{c}-f_{j}$, we get $L_{q,x_{0}}^{j}=\max_{y\in B_{p}(x_{0},R)}\|\nabla g(y)\|_{q}=\max_{y\in B_{p}(x_{0},R)}\|\nabla f_{j}(y)-\nabla f_{c}(y)\|_{q}$, which then gives the bound in Theorem 2.1 of (Hein & Andriushchenko, 2017). ∎

C Proof of Lemma 3

For any $\bm{x},\bm{y}$, let $\bm{d}=\frac{\bm{y}-\bm{x}}{\|\bm{y}-\bm{x}\|_{p}}$ be the unit vector pointing from $\bm{x}$ to $\bm{y}$ and $r=\|\bm{y}-\bm{x}\|_{p}$. Define uni-variate function $u(z)=h(\bm{x}+z\bm{d})$, then $u(0)=h(\bm{x})$ and $u(r)=h(\bm{y})$ and observe that $D^{+}h(\bm{x}+z\bm{d};\bm{d})$ and $D^{+}h(\bm{x}+z\bm{d};\bm{-d})$ are the right-hand and left-hand derivatives of $u(z)$, we have

For ReLU network, there can be at most finite number of points in $z\in(0,r)$ such that $g^{\prime}(z)$ does not exist. This can be shown because each discontinuous $z$ is caused by some ReLU activation, and there are only finite combinations. Let $0=z_{0}<z_{1}<\dots<z_{k-1}<z_{k}=1$ be those points. Then, using the fundamental theorem of calculus on each interval separately, there exists $\bar{z}_{i}\in(z_{i},z_{i-1})$ for each $i$ such that

Theorem 3.2 and its corollaries remain valid after replacing Lemma 3.1 with Lemma 3. ∎

D Theorem D.1 and its proof

The $j_{\text{th}}$ output of a one-hidden-layer neural network can be written as

where $\sigma(z)=\max(z,0)$ is ReLU activation function, $\bm{W}$ and $\bm{V}$ are the weight matrices of the first and second layer respectively, and $\bm{w}_{r}$ is the $r_{\text{th}}$ row of $\bm{W}$. Thus, we can compute $g(\bm{x})$ and $\|\nabla g(\bm{x})\|_{q}$ below:

Therefore, if we perform uniform sampling in a ball $B_{p}(\bm{x_{0}},R)$ centered at $\bm{x_{0}}$ with radius $R$ and denote $\|\nabla g(\bm{x})\|_{q}$ as a random variable $Y$, the probability distribution of $Y$ is discrete and its CDF is piece-wise constant with at most $M$ pieces. Without loss of generality, assume there are $M_{0}\leq M$ distinct values for $Y$ and denote them as $m_{(1)},m_{(2)},\ldots,m_{(M_{0})}$ in an increasing order, the CDF of $Y$, denoted as $F_{Y}(y)$, is the following:

E Additional experimental results

Table 3 shows the percentage of examples where the null hypothesis cannot be rejected by K-S test, indicating that the maximum gradient norm samples fit reverse Weibull distribution well.

E.2 CLEVER v.s. number of samples