Title: EVALUATING THE ROBUSTNESS OF NEURAL NET-WORKS: AN EXTREME VALUE THEORY APPROACH

Abstract: The robustness of neural networks to adversarial examples has received great attention due to security implications. Despite various attack approaches to crafting visually imperceptible adversarial examples, little has been developed towards a comprehensive measure of robustness. In this paper, we provide a theoretical justification for converting robustness analysis into a local Lipschitz constant estimation problem, and propose to use the Extreme Value Theory for efficient evaluation. Our analysis yields a novel robustness metric called CLEVER, which is short for Cross Lipschitz Extreme Value for nEtwork Robustness. The proposed CLEVER score is attack-agnostic and computationally feasible for large neural networks. Experimental results on various networks, including ResNet, Inception-v3 and MobileNet, show that (i) CLEVER is aligned with the robustness indication measured by the 2 and ∞ norms of adversarial examples from powerful attacks, and (ii) defended networks using defensive distillation or bounded ReLU indeed achieve better CLEVER scores. To the best of our knowledge, CLEVER is the first attack-independent robustness metric that can be applied to any neural network classifier.

1. 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.

Motivated by the evaluation criterion for assessing the quality of text and image generation that is completely independent of the underlying generative processes, such as the BLEU score for texts (Papineni et al., 2002) and the INCEPTION score for images (Salimans et al., 2016) , we aim to propose a comprehensive and attack-agnostic robustness metric for neural networks. Stemming from a perturbation analysis of an arbitrary neural network classifier, we derive a universal lower bound on the minimal distortion required to craft an adversarial example from an original one, where the lower bound applies to any attack algorithm and any p norm for p ≥ 1. We show that this lower bound associates with the maximum norm of the local gradients with respect to the original example, and therefore robustness evaluation becomes a local Lipschitz constant estimation problem. To efficiently and reliably estimate the local Lipschitz constant, we propose to use extreme value theory (De Haan & Ferreira, 2007) for robustness evaluation. In this context, the extreme value corresponds to the local Lipschitz constant of our interest, which can be inferred by a set of independently and identically sampled local gradients.With the aid of extreme value theory, we propose a robustness metric called CLEVER, which is short for Cross Lipschitz Extreme Value for nEtwork Robustness. We note that CLEVER is an attack-independent robustness metric that applies to any neural network classifier. In contrast, the robustness metric proposed in Hein & Andriushchenko (2017) , albeit attack-agnostic, only applies to a neural network classifier with one hidden layer.

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. • We corroborate the effectiveness of CLEVER by conducting experiments on state-of-theart models for ImageNet, including ResNet (He et al., 2016) , Inception-v3 (Szegedy et al., 2016) and MobileNet (Howard et al., 2017) . We also use CLEVER to investigate defended networks against adversarial examples, including the use of defensive distillation (Papernot et al., 2016) and bounded ReLU (Zantedeschi et al., 2017) . Experimental results show that our CLEVER score well aligns with the attack-specific robustness indicated by the 2 and ∞ distortions of adversarial examples.

2. BACKGROUND AND RELATED WORK:



2.1. ATTACKING NEURAL NETWORKS USING ADVERSARIAL EXAMPLES:

One of the most popular formulations found in literature for crafting adversarial examples to mislead a neural network is to formulate it as a minimization problem, where the variable δ ∈ R d to be optimized refers to the perturbation to the original example, and the objective function takes into account unsuccessful adversarial perturbations as well as a specific norm on δ for assuring similarity. For instance, the success of adversarial examples can be evaluated by their cross-entropy loss (Szegedy et al., 2013; Goodfellow et al., 2015) or model prediction (Carlini & Wagner, 2017b) . The norm constraint on δ can be implemented in a clipping manner (Kurakin et al., 2016b) or treated as a penalty function (Carlini & Wagner, 2017b) . The p norm of δ, defined as δ p = ( d i=1 |δ i | p ) 1/p for any p ≥ 1, is often used for crafting adversarial examples. In particular, when p = ∞, δ ∞ = max i∈{1,...,d} |δ i | measures the maximal variation among all dimensions in δ. When p = 2, δ 2 becomes the Euclidean norm of δ. When p = 1, δ 1 = p i=1 |δ i | measures the total variation of δ. The state-of-the-art attack methods for ∞ , 2 and 1 norms are the iterative fast gradient sign method (I-FGSM) (Goodfellow et al., 2015; Kurakin et al., 2016b) , Carlini and Wagner's attack (CW attack) (Carlini & Wagner, 2017b) , and elastic-net attacks to deep neural networks (EAD) (Chen et al., 2017b) , respectively. These attacks fall into the category of white-box attacks since the network model is assumed to be transparent to an attacker. Adversarial examples can also be crafted from a black-box network model using an ensemble approach (Liu et al., 2016) , training a substitute model (Papernot et al., 2017) , or employing zeroth-order optimization based attacks (Chen et al., 2017c) .

2.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. 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.

2.3. THEORETICAL ROBUSTNESS GUARANTEES FOR NEURAL 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.

3. ANALYSIS OF FORMAL ROBUSTNESS GUARANTEES FOR A CLASSIFIER:

In this section, we provide formal robustness guarantees of a classifier in Theorem 3.2. Our robustness guarantees are general since they only require a mild assumption on Lipschitz continuity of the classification function. For differentiable classification functions, our results are consistent with the main theorem in (Hein & Andriushchenko, 2017) but are obtained by a much simpler and more 

f : R d → R K neural network classifier β U upper bound of minimum distortion x 0 ∈ R d original input vector L j q Lipschitz constant x a ∈ R d adversarial example L j q,x0 local Lipschitz constant δ ∈ R d distortion := x a -x 0 B p (x 0 , R) hyper-ball with center x 0 and radius R δ p p norm of distortion, p ≥ 1 CDF cumulative distribution function

intuitive manner1 . Furthermore, our robustness analysis can be easily extended to non-differentiable classification functions (e.g. neural networks with ReLU) as in Lemma 3.3, whereas the analysis in Hein & Andriushchenko ( 2017) is restricted to differentiable functions. Specifically, Corollary 3.2.1 shows that the robustness analysis in (Hein & Andriushchenko, 2017) is in fact a special case of our analysis. We start our analysis by defining the notion of adversarial examples, minimum p distortions, and lower/upper bounds. All the notations are summarized in Table 1 . Definition 3.1 (perturbed example and adversarial example). Let x 0 ∈ R d be an input vector of a K-class classification function f : R d → R K and the prediction is given as c(x 0 ) = argmax 1≤i≤K f i (x 0 ). Given x 0 , we say x a is a perturbed example of x 0 with noise δ ∈ R d and p -distortion ∆ p if x a = x 0 + δ and ∆ p = δ p . An adversarial example is a perturbed example x a that changes c(x 0 ). A successful untargeted attack is to find a x a such that c(x a ) = c(x 0 ) while a successful targeted attack is to find a x a such that c(x a ) = t given a target class t = c(x 0 ). Definition 3.2 (minimum adversarial distortion ∆ p,min ). Given an input vector x 0 of a classifier f , the minimum p adversarial distortion of x 0 , denoted as ∆ p,min , is defined as the smallest ∆ p over all adversarial examples of x 0 . Definition 3.3 (lower bound of ∆ p,min ). Suppose ∆ p,min is the minimum adversarial distortion of x 0 . A lower bound of ∆ p,min , denoted by β L where β L ≤ ∆ p,min , is defined such that any perturbed examples of x 0 with δ p ≤ β L are not adversarial examples. Definition 3.4 (upper bound of ∆ p,min ). Suppose ∆ p,min is the minimum adversarial distortion of x 0 . An upper bound of ∆ p,min , denoted by β U where β U ≥ ∆ p,min , is defined such that there exists an adversarial example of x 0 with δ p ≥ β U .

The lower and upper bounds are instance-specific because they depend on the input x 0 . While β U can be easily given by finding an adversarial example of x 0 using any attack method, β L is not easy to find. β L guarantees that the classifier is robust to any perturbations with δ p ≤ β L , certifying the robustness of the classifier. Below we show how to derive a formal robustness guarantee of a classifier with Lipschitz continuity assumption. Specifically, our analysis obtains a lower bound of

p minimum adversarial distortion β L = min j =c fc(x0)-fj (x0) L j q .

Lemma 3.1 (Lipschitz continuity and its relationship with gradient norm (Paulavičius & Žilinskas, 2006) ). Let S ⊂ R d be a convex bounded closed set and let h(x) : S → R be a continuously differentiable function on an open set containing S. Then, h(x) is a Lipschitz function with Lipschitz constant L q if the following inequality holds for any x, y ∈ S:

EQUATION

where  and 1 p + 1 q = 1, 1 ≤ p, q ≤ ∞.

L q = max{ ∇h(x) q : x ∈ S}, ∇h(x) = ( ∂h(x) ∂x1 , • • • , ∂h(x) ∂x d ) is the gradient of h(x),

Given Lemma 3.1, we then provide a formal guarantee to the lower bound β L . Theorem 3.2 (Formal guarantee on lower bound β L for untargeted attack). Let x 0 ∈ R d and f : R d → R K be a multi-class classifier with continuously differentiable components f i and let c = argmax 1≤i≤K f i (x 0 ) be the class which f predicts for x 0 . For all δ ∈ R d with

EQUATION

)

argmax 1≤i≤K f i (x 0 + δ) = c holds with 1 p + 1 q = 1, 1 ≤ p, q ≤ ∞

and L j q is the Lipschitz constant for the function f c (x)f j (x) in p norm. In other words, β L = min j =c fc(x0)-fj (x0) L j q is a lower bound of minimum distortion. 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 ±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 + δ) can be bounded by g(x 0 ), δ and the Lipschitz constant L q . When g(x 0 + δ) is decreased to 0, an adversarial example is found and the minimal change of δ is g(x0)

Lq . The complete proof is deferred to Appendix A.

Remark 1. L j q is the Lipschitz constant of the function involving cross terms: f c (x)f j (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 3.2.1 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 (x) when requiring f i (x) to be continuously differentiable. They use local Lipschitz constant (L q,x0 ) instead of global Lipschitz constant (L q ) to obtain a tighter bound in the adversarial perturbation δ. Corollary 3.2.1 (Formal guarantee on β L for untargeted attack).2 Let L j q,x0 be local Lipschitz constant of function f c (x)-f j (x) at x 0 over some fixed ball B p (x 0 , R) := {x ∈ R d | x-x 0 p ≤ R} and let δ ∈ B p (0, R). By Theorem 3.2, we obtain the bound in (Hein & Andriushchenko, 2017) :

δ p ≤ min min j =c f c (x 0 ) -f j (x 0 ) L j q,x0

, R .

(3)

An important use case of Theorem 3.2 and Corollary 3.2.1 is the bound for targeted attack: Corollary 3.2.2 (Formal guarantee on β L for targeted attack). Assume the same notation as in Theorem 3.2 and Corollary 3.2.1. For a specified target class j, we have δ p ≤ min

fc(x0)-fj (x0) L j q,x 0 , R .

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. Lemma 3.3 (Formal guarantee on β L for ReLU networks). 3 Let h(•) 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.

h(x) = σ(W l σ(W l-1 . . . σ(W 1 x)))

where σ(u) = max(0, u). Let S ⊂ R d be a convex bounded closed set, then equation (1) holds with

L q = sup x∈S {| sup d p =1 D + h(x; d)|} where D + h(x; d) := lim t→0 + h(x+td)-h(x) t

is the one-sided directional direvative, then Theorem 3.2, Corollary 3.2.1 and Corollary 3.2.2 still hold.

4. 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 β 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(x 0 ) and its cross Lipschitz constant L j q,x0 , where g(x 0 ) = f c (x 0 )f j (x 0 ) is readily available at the output of a classifier and L j q,x0 is defined as max x∈Bp(x0,R) ∇g(x) q . Although ∇g(x) can be calculated easily via back propagation, computing L j q,x0 is more involved because it requires to obtain the maximum value of ∇g(x) q in a ball. Exhaustive search on low dimensional x in B p (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 j q,x0 is through sampling a set of points x (i) in a ball B p (x 0 , R) around x 0 and taking the maximum value of ∇g(x (i) ) q . However, a significant amount of samples might be needed to obtain a good estimate of max ∇g(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 ∇g(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 3 and Figure 4 , perform poorly for high-dimensional classifiers such as deep neural networks.

4.1 ESTIMATE L j q,x0 VIA EXTREME VALUE THEORY When sampling a point x uniformly in B p (x 0 , R), ∇g(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. 4 For any neural networks, suppose we have n samples { ∇g(x (i) ) q }, and denote them as a sequence of independent and identically distributed (iid 

EQUATION

G(y) = exp -exp - y -a W b W , y ∈ R, Fréchet class (Type II): G(y) = 0, if y < a W , exp{-y-aW bW -cW }, if y ≥ a W , Reverse Weibull class (Type III): G(y) = exp{-aW -y bW cW }, if y < a W , 1,

if y ≥ a W , where a W ∈ R, b W > 0 and c W > 0 are the location, scale and shape parameters, respectively. Theorem 4.1 implies that the maximum values of the samples follow one of the three families of distributions. If g(x) has a bounded Lipschitz constant, ∇g(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 j q,x0 we would like to estimate in this paper. To estimate L j q,x0 , we first generate N s samples of x (i) over a fixed ball B p (x 0 , R) uniformly and independently in each batch with a total of N b batches. We then compute ∇g(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 âW is used as an estimate of L j q,x0 .

4.2. COMPUTE CLEVER: A ROBUSTNESS SCORE OF NEURAL NETWORK CLASSIFIERS:

Given an instance x 0 , its classifier f (x 0 ) and a target class j, a targeted CLEVER score of the classifier's robustness can be computed via g(x 0 ) and L j q,x0 . Similarly, untargeted CLEVER scores can be computed. With the proposed procedure of estimating L j q,x0 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.

Algorithm 1: CLEVER-t, compute CLEVER score for targeted attack Input: a K-class classifier f (x), data example x 0 with predicted class c, target class j, batch size N b , number of samples per batch N s , perturbation norm p, maximum perturbation R Result:

CLEVER Score µ ∈ R + for target class j S ← {∅}, g(x) ← f c (x) -f j (x), q ← p p-1 . for i ← 1 to N b do for k ← 1 to N s do randomly select a point x (i,k) ∈ B p (x 0 , R) compute b ik ← ∇g(x (i,k) ) q via back propagation end S ← S ∪ {max k {b ik }} end âW ← MLE of location parameter of reverse Weibull distribution on S µ ← min( g(x0) â , R)

Algorithm 2: CLEVER-u, compute CLEVER score for un-targeted attack Input: Same as Algorithm 1, but without a target class j Result: CLEVER score ν ∈ R + for un-targeted attack for j ← 1 to K, j = c do µ j ← CLEVER-t(f, x 0 , c, j, N b , N s , p, R) end ν ← min j {µ j }

5. EXPERIMENTAL RESULTS:



5.1. NETWORKS AND PARAMETER SETUP:

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-theart 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 models 5 . 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 available6 .

5.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 âW , scale parameter bW and shape parameter ĉ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. 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), â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 5 in Appendix E. All numbers for each model are close to 100%, indicating S fits reverse Weibull distributions well.

5.3. COMPARING CLEVER SCORE WITH ATTACK-SPECIFIC NETWORK ROBUSTNESS:

We apply the state-of-the-art white-box attack methods, iterative fast gradient sign method (I-FGSM) (Goodfellow et al., 2015; Kurakin et al., 2016b) and Carlini and Wagner's attack (CW) (Carlini & Wagner, 2017b) , to find adversarial examples for 11 networks, including 4 networks trained on CIFAR, 4 networks trained on MNIST, and 3 networks trained on ImageNet. For CW attack, we run 1000 iterations for ImageNet and CIFAR, and 2000 iterations for MNIST, as MNIST has shown to be more difficult to attack (Chen et al., 2017b) . Attack learning rate is individually tuned for each model: 0.001 for Inception-v3 and ResNet-50, 0.0005 for Mo-bileNet and 0.01 for all other networks. For I-FGSM, we run 50 iterations and choose the optimal ∈ {0.01, 0.025, 0.05, 0.1, 0.3, 0.5, 0.8, 1.0} to achieve the smallest ∞ distortion for each individual image. For defensively distilled (DD) networks, 50 iterations of I-FGSM are not sufficient; we use 250 iterations for CIFAR-DD and 500 iterations for MNIST-DD to achieve a 100% success rate.

For the problem to be non-trivial, images that are classified incorrectly are skipped. We report 100% attack success rates for all the networks, and thus the average distortion of adversarial examples can indicate the attack-specific robustness of each network. For comparison, we compute the CLEVER scores for the same set of images and attack targets. To the best of our knowledge, CLEVER is the first attack-independent robustness score that is capable of handling the large networks studied in this paper, so we directly compare it with the attack-induced distortion metrics in our study.

We evaluate the effectiveness of our CLEVER score by comparing the upper bound β U (found by attacks) and CLEVER score, where CLEVER serves as an estimated lower bound, β L . Table 3 compares the average 2 and ∞ distortions of adversarial examples found by targeted CW and I-FGSM attacks and the corresponding average targeted CLEVER scores for 2 and ∞ norms, and Figure 4 visualizes the results for ∞ norm. Similarly, Table 2 compares untargeted CW and I-FGSM attacks with untargeted CLEVER scores. As expected, CLEVER is smaller than the distortions of adversarial images in most cases. More importantly, since CLEVER is independent of attack algorithms, the reported CLEVER scores can roughly indicate the distortion of the best possible attack in terms of a specific p distortion. The average 2 distortion found by CW attack is close to the 2 CLEVER score, indicating CW is a strong 2 attack. In addition, when a defense mechanism (Defensive Distillation or Bounded ReLU) is used, the corresponding CLEVER scores are consistently increased (except for CIFAR-BReLU), indicating that the network is indeed made more resilient to adversarial perturbations. For CIFAR-BReLU, both CLEVER scores and p norm of adversarial examples found by CW attack decrease, implying that bound ReLU is an ineffective defense for CIFAR. CLEVER scores can be seen as a security checkpoint for unseen attacks. For example, if there is a substantial gap in distortion between the CLEVER score and the considered attack algorithms, it may suggest the existence of a more effective attack that can close the gap.

Since CLEVER score is derived from an estimation of the robustness lower bound, we further verify the viability of CLEVER per each example, i.e., whether it is usually smaller than the upper bound found by attacks. Table 4 shows the percentage of inaccurate estimations where the CLEVER score is larger than the distortion of adversarial examples found by CW and I-FGSM attacks in three ImageNet networks. We found that CLEVER score provides an accurate estimation for most of the examples. For MobileNet and Resnet-50, our CLEVER score is a strict lower bound of these two attacks for more than 96% of tested examples. For Inception-v3, the condition of strict lower bound Wood & Zhang (1996) . SLOPE significantly exceeds the distortions found by attacks, thus it is an inappropriate estimation of lower bound β L .

is worse (still more than 75%), but we found that in these cases the attack distortion only differs from our CLEVER score by a fairly small amount. In Figure 5 we show the empirical CDF of the gap between CLEVER score and the 2 norm of adversarial distortion generated by CW attack for the same set of images in Table 4 . In Figure 6 , we plot the 2 distortion and CLEVER scores for each 

I-FGSM L 2 L ∞ L 2 L ∞ L 2 L ∞ L 2 L ∞ L 2 L ∞ L 2 L ∞ MobileNet 4%

0% 0% 0% 2% 0% 0% 0% 0% 0% 0% 0% Resnet-50 4% 0% 0% 0% 2% 0% 0% 0% 1% 0% 0% 0% Inception-v3 25% 0% 0% 0% 23% 0% 0% 0% 15% 0% 0% 0% (a) MobileNet 

5.4. TIME V.S. ESTIMATION ACCURACY:

In Figure 7 , we vary the number of samples (N b = 50, 100, 250, 500) and compute the 2 CLEVER scores for three large ImageNet models, Inception-v3, ResNet-50 and MobileNet. We observe that 50 or 100 samples are usually sufficient to obtain a reasonably accurate robustness estimation despite using a smaller number of samples. On a single GTX 1080 Ti GPU, the cost of 1 sample (with N s = 1024) is measured as 2.9 s for MobileNet, 5.0 s for ResNet-50 and 8.9 s for Inception-v3, thus the computational cost of CLEVER is feasible for state-of-the-art large-scale deep neural networks. Additional figures for MNIST and CIFAR datasets are given in Appendix E.

6. 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.

For ReLU network, there can be at most finite number of points in z ∈ (0, r) such that g (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 < • • • < z k-1 < z k = 1 be those points. Then, using the fundamental theorem of calculus on each interval separately, there exists zi ∈ (z i , z i-1 ) for each i such that L q |z iz i-1 | p = L q xy p .

(z i are in line (x, y)) Theorem 3.2 and its corollaries remain valid after replacing Lemma 3.1 with Lemma 3.3. we have ∇g(x 1 ) q = ∇g(x 2 ) q . Since there can be at most M = d i=0 U i different regions for a d-dimensional space with U hyperplanes, ∇g(x) q can take at most M different values.

Therefore, if we perform uniform sampling in a ball B p (x 0 , R) centered at x 0 with radius R and denote ∇g(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 ≤ M distinct values for Y and denote them as m (1) , m (2) , . . . , m (M0) in an increasing order, the CDF of Y , denoted as F Y (y), is the following: 

:

The authors inHein & Andriushchenko (2017) implicitly assume Lipschitz continuity and use Mean Value Theorem and Hölder's Inequality to prove their main theorem. Here we provide a simple and direct proof with Lipschitz continuity assumption and without involving Mean Value Theorem and Hölder's Inequality.

proof deferred to Appendix B

proof deferred to Appendix C

The theorem and proof are deferred to Appendix D.

Pretrained models can be downloaded at https://github.com/tensorflow/models/tree/master/research/slim

Source code is available at https://github.com/huanzhang12/CLEVER

Figures and Tables:

Figure 1: Intuitions behind Theorem 3.2.

y), is called the limit distribution of F Y (y). Fisher-Tippett-Gnedenko theorem says that F n Y (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. Theorem 4.1 (Fisher-Tippett-Gnedenko Theorem). If there exists a sequence of pairs of real numbers (a n , b n ) such that a n > 0 and lim n→∞ F n Y (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: Gumbel class (Type I):

Figure 2 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 Figure3. 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. Figure3shows 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), âW , can be used as a good estimation of local cross Lipschitz constant to calculate the CLEVER score. The exact numbers are shown in Table5in Appendix E.

Figure 2: The cross Lipschitz constant samples for three images from CIFAR, MNIST and ImageNet datasets, and their fitted Reverse Weibull distributions with the corresponding MLE estimates of location, scale and shape parameters (a W , b W , c W ) shown on the top of each plot. The D-statistics of K-S test and p-values are denoted as ks and pval. With small ks and high p-value, the hypothesized reverse Weibull distribution fits the empirical distribution of cross Lipschitz constant samples well.

Figure 4: Comparison of ∞ distortion obtained by CW and I-FGSM attacks, CLEVER score and the slope based Lipschitz constant estimation (SLOPE) byWood & Zhang (1996). SLOPE significantly exceeds the distortions found by attacks, thus it is an inappropriate estimation of lower bound β L .

Figure 5: The empirical CDF of the gap between CLEVER score and the 2 norm of adversarial distortion generated by CW attack with random targets for 100 images on 3 ImageNet networks.

Figure 6: Comparison of the CLEVER scores (circle) and the 2 norm of adversarial distortion generated by CW attack (triangle) with random targets for 100 images. The x-axis is image ID and the y-axis is the 2 distortion metric.(a) Least likely target (b) Random target (c) Top-2 target

Y (m (i) ) = F Y (m (i-1) ) + V d ({x | ∇g(x) q = m (i) }) ∩ V d (B p (x 0 , R))) V d (B p (x 0 , R)) , i = 1, . . . , M 0 ,whereF Y (m (0) ) = 0 with m (0) < m (1) , V d (E) is the volume of E in a d dimensional space. E ADDITIONAL EXPERIMENTAL RESULTSE.1 PERCENTAGE OF EXAMPLES HAVING P VALUE > 0.05

Figure9shows the 2 CLEVER score with different number of samples (N b = 50, 100, 250, 500) for MNIST and CIFAR models. For most models except MNIST-BReLU, reducing the number of samples only change CLEVER scores very slightly. For MNIST-BReLU, increasing the number of samples improves the estimated lower bound, suggesting that a larger number of samples is preferred. In practice, we can start with a relatively small N b = a, and also try 2a, 4a, • • • samples to see if CLEVER scores change significantly. If CLEVER scores stay roughly the same despite increasing N b , we can conclude that using N b = a is sufficient.

Figure 9: Comparison of the CLEVER score calculated by N b = {50, 100, 250, 500} and the 2 norm of adversarial distortion found by CW attack (CW) on MNIST and CIFAR models with 3 target types.

Table of Notation

Table content: <table><tr><td>Notation</td><td>Definition</td><td>Notation</td><td>Definition</td></tr><tr><td>d</td><td colspan="2">dimensionality of the input vector ∆ p,min</td><td>minimum p distortion of x 0</td></tr><tr><td>K</td><td>number of output classes</td><td>β L</td><td>lower bound of minimum distortion</td></tr></table>

Comparison between the average untargeted CLEVER score and distortion found by CW and I-FGSM untargeted attacks. DD and BReLU represent Defensive Distillation and Bounded ReLU defending methods applied to the baseline CNN network.

Table content: <table><tr><td/><td>CW</td><td/><td colspan="2">I-FGSM</td><td colspan="2">CLEVER</td></tr><tr><td/><td>2</td><td>∞</td><td>2</td><td>∞</td><td>2</td><td>∞</td></tr><tr><td>MNIST-MLP</td><td colspan="6">1.113 0.215 3.564 0.178 0.819 0.041</td></tr><tr><td>MNIST-CNN</td><td colspan="6">1.500 0.455 4.439 0.288 0.721 0.057</td></tr><tr><td>MNIST-DD</td><td colspan="6">1.548 0.409 5.617 0.283 0.865 0.063</td></tr><tr><td colspan="7">MNIST-BReLU 1.337 0.433 3.851 0.285 0.833 0.065</td></tr><tr><td>CIFAR-MLP</td><td colspan="6">0.253 0.018 0.885 0.016 0.219 0.005</td></tr><tr><td>CIFAR-CNN</td><td colspan="6">0.195 0.023 0.721 0.018 0.072 0.002</td></tr><tr><td>CIFAR-DD</td><td colspan="6">0.285 0.032 1.136 0.024 0.130 0.004</td></tr><tr><td colspan="7">CIFAR-BReLU 0.159 0.019 0.519 0.013 0.045 0.001</td></tr></table>

Comparison of the average targeted CLEVER scores with average ∞ and 2 distortions found by CW, I-FSGM attacks, and the average scores calculated by using the algorithm inWood & Zhang (1996) (denoted as SLOPE) to estimate Lipschitz constant. DD and BReLU denote Defensive Distillation and Bounded ReLU defending methods applied to the CNN network. We did not include SLOPE in ImageNet networks because it has been shown to be ineffective even for smaller networks.(a) avergage ∞ distortion of CW and I-FGSM targeted attacks, and CLEVER and SLOPE estimation. Some very large SLOPE estimates (in parentheses) exceeding the maximum possible ∞ distortion are reported as 1. distortion of CW and I-FGSM targeted attacks, and CLEVER and SLOPE estimation. Some very large SLOPE estimates (in parentheses) exceeding the sampling radius R = 5 are reported as 5.

Table content: <table><tr><td/><td/><td colspan="2">Least Likely Target</td><td/><td/><td colspan="2">Random Target</td><td/><td/><td colspan="2">Top-2 Target</td><td/></tr><tr><td/><td>CW</td><td colspan="2">I-FGSM CLEVER</td><td>SLOPE</td><td>CW</td><td colspan="3">I-FGSM CLEVER SLOPE</td><td>CW</td><td colspan="2">I-FGSM CLEVER</td><td>SLOPE</td></tr><tr><td>MNIST-MLP</td><td>0.475</td><td>0.223</td><td>0.071</td><td>0.808</td><td>0.337</td><td>0.173</td><td>0.072</td><td>0.813</td><td>0.218</td><td>0.119</td><td>0.069</td><td>0.786</td></tr><tr><td>MNIST-CNN</td><td>0.601</td><td>0.313</td><td>0.090</td><td>0.996</td><td>0.550</td><td>0.264</td><td>0.088</td><td>0.982</td><td>0.451</td><td>0.211</td><td>0.070</td><td>0.826</td></tr><tr><td>MNIST-DD</td><td>0.578</td><td>0.283</td><td>0.103</td><td colspan="2">1 (1.090) 0.531</td><td>0.238</td><td>0.091</td><td>0.953</td><td>0.412</td><td>0.165</td><td>0.091</td><td>0.984</td></tr><tr><td colspan="2">MNIST-BReLU 0.601</td><td>0.276</td><td>0.257</td><td colspan="2">1 (5.327) 0.544</td><td>0.238</td><td>0.187</td><td>3.907</td><td>0.442</td><td>0.196</td><td>0.117</td><td>1 (2.470)</td></tr><tr><td>CIFAR-MLP</td><td>0.086</td><td>0.039</td><td>0.014</td><td>0.294</td><td>0.051</td><td>0.024</td><td>0.014</td><td>0.284</td><td>0.019</td><td>0.013</td><td>0.014</td><td>0.286</td></tr><tr><td>CIFAR-CNN</td><td>0.053</td><td>0.033</td><td>0.005</td><td>0.153</td><td>0.042</td><td>0.023</td><td>0.005</td><td>0.148</td><td>0.022</td><td>0.013</td><td>0.004</td><td>0.129</td></tr><tr><td>CIFAR-DD</td><td>0.091</td><td>0.053</td><td>0.011</td><td>0.278</td><td>0.066</td><td>0.032</td><td>0.010</td><td>0.255</td><td>0.033</td><td>0.014</td><td>0.007</td><td>0.184</td></tr><tr><td colspan="2">CIFAR-BReLU 0.045</td><td>0.030</td><td>0.004</td><td>0.250</td><td>0.034</td><td>0.022</td><td>0.003</td><td>0.173</td><td>0.018</td><td>0.012</td><td>0.002</td><td>0.095</td></tr><tr><td>Inception-v3</td><td>0.023</td><td>0.011</td><td>0.002</td><td>-</td><td>0.021</td><td>0.012</td><td>0.002</td><td>-</td><td>0.010</td><td>0.011</td><td>0.001</td><td>-</td></tr><tr><td>Resnet-50</td><td>0.031</td><td>0.015</td><td>0.002</td><td>-</td><td>0.025</td><td>0.012</td><td>0.002</td><td>-</td><td>0.010</td><td>0.010</td><td>0.001</td><td>-</td></tr><tr><td>MobileNet</td><td>0.025</td><td>0.010</td><td>0.003</td><td>-</td><td>0.018</td><td>0.010</td><td>0.002</td><td>-</td><td>0.006</td><td>0.010</td><td>0.001</td><td>-</td></tr><tr><td colspan="4">(b) average 2 Least Likely Target</td><td/><td/><td colspan="2">Random Target</td><td/><td/><td colspan="2">Top-2 Target</td><td/></tr><tr><td/><td>CW</td><td colspan="2">I-FGSM CLEVER</td><td>SLOPE</td><td>CW</td><td colspan="2">I-FGSM CLEVER</td><td>SLOPE</td><td>CW</td><td colspan="2">I-FGSM CLEVER</td><td>SLOPE</td></tr><tr><td>MNIST-MLP</td><td>2.575</td><td>4.273</td><td>1.409</td><td colspan="2">5 (8.028) 1.833</td><td>3.369</td><td>1.432</td><td colspan="2">5 (8.102) 1.128</td><td>2.374</td><td>1.383</td><td>5 (7.853)</td></tr><tr><td>MNIST-CNN</td><td>2.377</td><td>4.417</td><td>1.257</td><td colspan="2">5 (9.947) 2.005</td><td>3.902</td><td>1.227</td><td colspan="2">5 (9.619) 1.504</td><td>3.242</td><td>0.987</td><td>5 (7.921)</td></tr><tr><td>MNIST-DD</td><td>2.644</td><td>4.957</td><td>1.532</td><td colspan="2">5 (10.628) 2.240</td><td>4.253</td><td>1.340</td><td colspan="2">5 (9.493) 1.542</td><td>3.010</td><td>1.330</td><td>5 (9.646)</td></tr><tr><td colspan="2">MNIST-BReLU 2.349</td><td>5.170</td><td>3.312</td><td colspan="2">5 (52.058) 1.923</td><td>4.544</td><td>2.565</td><td colspan="2">5 (37.531) 1.404</td><td>3.778</td><td>1.583</td><td>5 (23.548)</td></tr><tr><td>CIFAR-MLP</td><td>1.123</td><td>1.896</td><td>0.620</td><td colspan="2">5 (5.013) 0.673</td><td>1.214</td><td>0.597</td><td>4.806</td><td>0.262</td><td>0.689</td><td>0.599</td><td>4.949</td></tr><tr><td>CIFAR-CNN</td><td>0.836</td><td>1.067</td><td>0.156</td><td>2.630</td><td>0.372</td><td>0.837</td><td>0.146</td><td>2.497</td><td>0.188</td><td>0.552</td><td>0.123</td><td>2.195</td></tr><tr><td>CIFAR-DD</td><td>2.065</td><td>1.540</td><td>0.347</td><td>4.735</td><td>0.624</td><td>1.097</td><td>0.307</td><td>4.279</td><td>0.296</td><td>0.582</td><td>0.220</td><td>3.083</td></tr><tr><td colspan="2">CIFAR-BReLU 0.407</td><td>0.928</td><td>0.140</td><td>4.125</td><td>0.303</td><td>0.732</td><td>0.103</td><td>2.944</td><td>0.152</td><td>0.494</td><td>0.052</td><td>1.564</td></tr><tr><td>Inception-v3</td><td>0.628</td><td>2.244</td><td>0.524</td><td>-</td><td>0.595</td><td>2.261</td><td>0.466</td><td>-</td><td>0.287</td><td>2.073</td><td>0.234</td><td>-</td></tr><tr><td>Resnet-50</td><td>0.767</td><td>2.410</td><td>0.357</td><td>-</td><td>0.647</td><td>2.098</td><td>0.299</td><td>-</td><td>0.212</td><td>1.682</td><td>0.134</td><td>-</td></tr><tr><td>MobileNet</td><td>0.837</td><td>2.195</td><td>0.617</td><td>-</td><td>0.603</td><td>2.066</td><td>0.439</td><td>-</td><td>0.190</td><td>1.771</td><td>0.144</td><td>-</td></tr></table>

Percentage of images in ImageNet where the CLEVER score for that image is greater than the adversarial distortion found by different attacks.

Table content: <table><tr><td colspan="2">Least Likely Target</td><td colspan="2">Random Target</td><td>Top-2 Target</td></tr><tr><td>CW</td><td>I-FGSM</td><td>CW</td><td>I-FGSM</td><td>CW</td></tr></table>

Table5shows 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. Table5: Percentage of estimations where the null hypothesis cannot be rejected by K-S test for a significance level of 0.05. The bar plots of this table are illustrated in Figure3.

Table content: <table><tr><td/><td colspan="2">Least Likely</td><td colspan="2">Random</td><td colspan="2">Top-2</td></tr><tr><td/><td>L 2</td><td>L ∞</td><td>L 2</td><td>L ∞</td><td>L 2</td><td>L ∞</td></tr><tr><td>MNIST-MLP</td><td colspan="6">100.0 100.0 100.0 100.0 100.0 100.0</td></tr><tr><td>MNIST-CNN</td><td>99.6</td><td>99.8</td><td colspan="4">99.2 100.0 99.4 100.0</td></tr><tr><td>MNIST-DD</td><td colspan="3">99.8 100.0 99.6</td><td>99.8</td><td>99.8</td><td>99.8</td></tr><tr><td colspan="2">MNIST-BReLU 93.3</td><td>95.4</td><td>96.8</td><td>96.8</td><td>97.6</td><td>98.2</td></tr><tr><td>CIFAR-MLP</td><td/><td/><td/><td/><td/></tr></table>

Peer review (iclr2018):
 Summary ======== The authors present CLEVER, an algorithm which consists in evaluating the (local) Lipschitz constant of a trained network around a data point. This is used to compute a lower-bound on the minimal perturbation of the data point needed to fool the network. The method proposed in the paper already exists for classical function, they only transpose it to neural networks. Moreover, the lower bound comes from basic results in the analysis of Lipschitz continuous functions. Clarity ===== The paper is clear and well-written. Originality ========= This idea is not new: if we search for "Lipschitz constant estimation" in google scholar, we get for example Wood, G. R., and B. P. Zhang. "Estimation of the Lipschitz constant of a function." (1996) which presents a similar algorithm (i.e., estimation of the maximum slope with reverse Weibull). Technical quality ============== The main theoretical result in the paper is the analysis of the lower-bound on .delta, the smallest perturbation to apply on a data point to fool the network. This result is obtained almost directly by writing the bound on Lipschitz-continuous function | f(y)-f(x) | < L || y-x || where x = x_0 and y = x_0 + .delta. Comments: - Lemma 3.1: why citing Paulavicius and Zilinskas for the definition of Lipschitz continuity? Moreover, a Lipschitz-continuous function does not need to be differentiable at all (e.g. |x| is Lipschitz with constant 1 but sharp at x=0). Indeed, this constant can be easier obtained if the gradient exists, but this is not a requirement. - (Flaw?) Theorem 3.2 : This theorem works for fixed target-class since g = f_c - f_j for fixed g. However, once g = min_j f_c - f_j, this theorem is not clear with the constant Lq. Indeed, the function g should be g(x) = min_{k .neq c} f_c(x) - f_k(x). Thus its Lipschitz constant is different, potentially equal to L_q = max_{k} .| L_q^k .|, where L_q^k is the Lipschitz constant of f_c-f_k. If the theorem remains unchanged after this modification, you should clarify the proof. Otherwise, the theorem will work with the maximum over all Lipschitz constants but the theoretical result will be weakened. - Theorem 4.1: I do not see the purpose of this result in this paper. This should be better motivated. Numerical experiments ==================== Globally, the numerical experiments are in favor of the presented method. The authors should also add information about the time it takes to compute the bound, the evolution of the bound in function of the number of samples and the distribution of the relative gap between the lower-bound and the best adversarial example. Moreover, the numerical experiments look to be realized in the context of targeted attack. To show the real effectiveness of the approach, the authors should also show the effectiveness of the lower-bound in the context of non-targeted attack. ####################################################### Post-rebuttal review --------------------------- Given the details the authors provided to my review, I decided to adjust my score. The method is simple and shows to be extremely effective/accurate in practice. Detailed answers: 1) Indeed, I was not aware that the paper only focuses on one dimensional functions. However, they still work with less assumption, i.e., with no differential functions. I was pointing out the similarities between their approach and your: the two algorithms (CLEVER and Slope) are basically the same, and using a limit you can go from "slope" to "gradient norm". In any case, I have read the revision and the additional numerical experiment to compare Clever with their method is a good point. 2) " Overall, our analysis is simple and more intuitive, and we further facilitate numerical calculation of the bound by applying the extreme value theory in this work. " This is right. I am just surprised is has not been done before, since it requires only few lines of derivation. I searched a bit but it is not possible to find any kind of similar results. Moreover, this leads to good performances, so there is no needs to have something more complex. 3) "The usual Lipschitz continuity is defined in terms of L2 norm and the extension to an arbitrary Lp norm is not straightforward" Indeed, people usually use the Lipschitz continuity using the L2norm, but the original definition is wider. Quickly, if you have a differential, scalar function from a space E -> R, then the gradient is a function from space E to E*, the dual of the space E. Let || . || the norm of space E. Then, || . ||* is the dual norm of ||.||, and also the norm of E*. In that case, Lipschitz continuity writes f(x)-f(y) <= L || x-y ||, with L >= max_{x in E*} || f*(x) ||* In the case where || . || is an .ell-p norm, then || . ||* is an .ell-q norm; with 1/p+1/q = 1. If you are interested, there is a clear and concise explanation in the introduction of this paper: Accelerating the cubic regularization of Newton’s method on convex problems, by Yurii Nesterov. I have no additional remarks for 4) -> 9), since everything is fixed in the new version of the paper.