Title: SECOND-ORDER ADVERSARIAL ATTACK AND CERTI-FIABLE ROBUSTNESS

Abstract: Adversarial training has been recognized as a strong defense against adversarial attacks. In this paper, we propose a powerful second-order attack method that reduces the accuracy of the defense model by Madry et al. (2017) . We demonstrate that adversarial training overfits to the choice of the norm in the sense that it is only robust to the attack used for adversarial training, thus suggesting it has not achieved universal robustness. The effectiveness of our attack method motivates an investigation of provable robustness of a defense model. To this end, we introduce a framework that allows one to obtain a certifiable lower bound on the prediction accuracy against adversarial examples. We conduct experiments to show the effectiveness of our attack method. At the same time, our defense model achieves significant improvements compared to previous works under our proposed attack.

1. INTRODUCTION:

Deep neural networks (DNNs) have achieved significant success when applied to a variety of challenging machine learning tasks. For example, DNNs have obtained state-of-the-art accuracy on large-scale image classification (Krizhevsky et al., 2012; He et al., 2016b) . At the same time, vulnerability to adversarial examples, an undesired property of DNNs, has drawn attention in the deep-learning community (Szegedy et al., 2013; Goodfellow et al., 2014) . Generally speaking, adversarial examples are perturbed versions of the original data that successfully fool a classifier. For example, in the image domain, adversarial examples are images transformed from natural images with visually negligible changes but lead to different classification results (Goodfellow et al., 2014) . The existence of adversarial examples has raised many concerns, especially in scenarios with a high risk of misclassification, such as autonomous driving.

To tackle adversarial examples, many works have been proposed to improve the robustness of DNNs (Papernot et al., 2016; Meng & Chen, 2017) , referred to as defense models. However, most of these defense methods have been later attacked successfully by new attack methods (Carlini & Wagner, 2017b; a) . For example, Athalye et al. (2018) conducted a case study that successfully attacked seven defense methods submitted to ICLR2018.

One model that demonstrated good performance against strong attacks, and has thus far not been successfully attacked, is based on adversarial training (Goodfellow et al., 2014; Madry et al., 2017) . Adversarial training constructs a defense model by augmenting the training set with adversarial examples. Though successful in adversarial defensing, the underlying mechanism is still unclear. In this paper, we explain the good performance is due to "degenerate global minimum", a phenomenon firstly discussed in (Tramèr et al., 2017) , and show that the Madry's defense model (Madry et al., 2017) , adversarial training with ∞ attack is not robust against an 2 attack even on MNIST. In particular, we develop a new attack method based on the approximated second-order derivative that forces its accuracy worse than naturally trained baseline models. To our knowledge, this is the first 2 attack method that significantly reduces the accuracy of Madry's model. In addition, the ∞ version of our method also breaks the 2 based adversarially trained model. Considering that Sharma & Chen (2017) has proposed 1 -based adversarial examples that break the Madry's model, we believe the robustness of adversarial training overfits to the choice of norms and is not universally robust. Concurrent work by Schott et al. (2018) also proposes similar conclusions via comprehensive experiments.

Our findings lead to a concern that most of the existing defense methods are heuristically driven, thus any defense method that cannot provide theoretically-provable robustness guarantee is potentially vulnerable to future attacks.

Several works on provable or certifiable adversarial defense methods have been proposed recently (Raghunathan et al., 2018; Kolter & Wong, 2017; Sinha et al., 2017) . However, most of them either have to make strong assumptions, such as on the structure of the model or on the smoothness of the loss function or are difficult to extend to large-scale datasets, the most common application scenario for DNNs.

Recently, Mathias et al. (2018) developed theoretical insight of certifiable robust prediction, by building a connection between differential privacy and model robustness. It is shown that adding properly chosen noise to the classifier will lead to certifiable robust prediction.

Built on the idea in (Mathias et al., 2018) , as our second contribution, we conduct an analysis based on Rényi divergence (Van Erven & Harremos, 2014) and show a higher upper bound on the tolerable size of attacks compared with Mathias et al. (2018) . In addition, we suggest there exists a connection between adversarial defense and robustness to random noise. Based on this, we introduce a more comprehensive framework, incorporating stability training to improve classification accuracy. One advantage of our framework is that it has no requirement on the model structure and is applicable to all classification models. Considering MNIST and CIFAR-10, our experiments demonstrate that the proposed defense yields stronger robustness to adversarial attacks, compared to other models.

2. PRELIMINARY:



2.1. NOTATION:

We consider the task of image classification. Natural images are represented by x ∈ X [0, 1] h×w×c , where X represents the image space, with h, w, c the height, width, and channels of an image, respectively. An image classifier over k classes is considered as a function f : X → {1, . . . , k}. In this paper, we only consider classifiers constructed by DNNs. To better present our framework, we define a stochastic classifier, a function f over x with output f (x) being a multinomial distribution over {1, . . . , k}, i.e., P (f (x) = i) = p i for i p i = 1. One can classify x by picking argmax i p i . Note this distribution is different from the one generated from softmax.

2.2. RÉNYI DIVERGENCE:

Our theoretical result depends on the Rényi divergence, defined as follows (Van Erven & Harremos, 2014) :

Definition 1 (Rényi Divergence) For two probability distributions P and Q over R, the Rényi divergence of order α > 1 is D α (P Q) = 1 α -1 log E x∼Q P Q α (1)

2.3. ADVERSARIAL EXAMPLES:

Given a classifier f : X → {1, . . . , k} for an image x ∈ X , an adversarial example x satisfies D(x, x ) < for some small > 0, and f (x) = f (x ), where D(•, •) is some distance metric, i.e., x is close to x but yields a different classification result. The distance is often described in terms of an p metric, and in most of the literature 2 and ∞ metrics are considered. In this paper, we focus on the 2 metric, but our method is easy to extend to the ∞ scenario.

Adversarial examples are often constructed by iterative optimization methods. Previous work has proposed a number of adversarial attack methods, such as the Fast Gradient Sign Method (FGSM) (Kurakin et al., 2016) , along with its multi-step variant FGSM k , which is equivalent to exploring adversarial examples that increase the classification loss using projected gradient descent (PGD) (Madry et al., 2017) :

x t+1 = Π x+S (x t + α(∇ x L(θ, x, y))

(2) where Π x+S is the projection operation that ensures adversarial examples stay in the p ball S around x. In (Madry et al., 2017) , it has also been shown that a PGD attack is a universal adversary among all first-order attack methods. Their analysis and evidence from experiments all suggest any adversarial attack method that only incorporates gradients of the loss function w.r.t. the input cannot do significantly better than PGD.

2.4. ADVERSARIAL TRAINING:

Adversarial training constructs adversarial examples and includes them into a training set to train a new and more robust classifier. This method is intuitive and has gained great success in defense (Goodfellow et al., 2014; Madry et al., 2017) . The motivation behind adversarial training is that finding a robust model against adversarial examples is equivalent to solving the saddle-point problem min θ max x :D(x,x )< L(θ, x , y). The inner maximization is equivalent to constructing adversarial examples, while the outer minimization is the standard training procedure for loss minimization.

3. SECOND-ORDER ADVERSARIAL ATTACK:

In this section, we propose an efficient second-order adversarial attack method. As one motivation, note most current attack methods construct adversarial examples based on the gradient of a loss function. However, a first-order derivative is not effective for attacks if the defense model is trained adversarially.

To see this, first note that adversarial training is equivalent to solving the optimization problem: ( θ, x) = argmin θ argmax x :D(x,x )< L(θ, x , y). The solution is a saddle point, i.e., it not only converges to a local minimum θ in the parameter space, but also converges to a local maximum x in the sample space, in which the gradient ideally vanishes at x as ∇ x L( θ, x, y)| x = 0. In practice, an adversarial training often finds θ that makes the loss function flat in the neighborhood of a natural example x, which leads to inefficient exploration for adversarial examples in the attack methods. This phenomenon is referred to as "degenerate global minimum" in (Tramèr et al., 2017) and analyzed for adversarial training via single-step attacks. Here we argue using multiple-step attacks also suffers from this issue. This motivates utilization of the second-order derivative of the loss function to construct adversarial examples. Specifically, assume the loss function is twice differentiable with respect to x. Using Taylor expansion on the difference between the losses on the original and perturbed samples, and assuming the gradient vanishes, we have L(θ, x + r, y) -L(θ, x, y) ≈ 1 2 r T H(θ, x, y)r with r being the perturbation, and H(θ, x, y) is the Hessian matrix of the loss function. Our goal is to find a small perturbation r that maximizes the difference L(θ, x + r, y) -L(θ, x, y). Our idea is based on the observation that the optimal perturbation direction should be in the same direction as the first dominant eigenvector, e(θ, x, y), of H(θ, x, y), that is r = e(θ,x,y) e(θ,x,y) 2 for some constant > 0. However, computing the eigenvectors of the Hessian matrix requires O(I 3 ) runtime with I the dimension of the data. To tackle this issue, we adopt the fast approximation method from Miyato et al. (2017) , which is essentially a combination of the power-iteration method and the finite-difference method, to efficiently find the direction of the eigenvector. Based on this method, the optimal direction, denoted r adv , is approximated * by

r adv = g g 2 , with g = ∇ x L(θ, x, y)| x+ξd (3)

where d is a randomly sampled unit vector and ξ > 0 is a manually chosen step size. In practice, d is drawn from a centered Gaussian distribution and normalized such that its 2 norm is 1.

This procedure is essentially a stochastic approximation to the optimal direction, where the randomness comes from d. To reduce the variance of the approximation, we further take the expectation over the Gaussian noise, yielding

g = E d∼N (0,σ 2 I) [∇ x L(θ, x, y)| x+d ].

Note that choosing σ is equivalent to choosing the step size ξ in (3). Finally, we construct adversarial examples by an iterative update via PGD:

x t+1 = Π x+S (x t + αr adv ) = Π x+S (x t + α g t g t 2 )

, where

g t = E d∼N (0,σ 2 I) [∇ x L(θ, x, y)| x+d ]

(4) * Detailed derivations are provided in the Appendix.

Intuitively, this method perturbs the example at each iteration and tries to move out of the local maximum in the sample space, due to the introduction of random Gaussian noise.

Connection to Expectation of Transformation (EOT) Attack:

We can think of (4) as gradient descent for maximizing an objective function of 4) is equivalent to constructing adversarial examples with the EOT method proposed by Athalye & Sutskever (2017) , when a defense model contains added Gaussian noise d.

E d∼N (0,σ 2 I) [∇ x L(θ, x, y)| x+d ]. Note E d∼N (0,σ 2 I) [∇ x L(θ, x, y)| x+d ] = ∇ x E d∼N (0,σ 2 I) [∇ x L(θ, x, y)| x+d ]. Consequently, (

In general, EOT tries to construct adversarial samples against a randomized defense model by solving the optimization problem:

x = argmax x E t∼T [L(θ, x, y)],

where t ∼ T is the randomization in the defense model. Intuitively, EOT aims to estimate the correct gradient by excluding the effect of randomization via expectation. If a defense model tries to add Gaussian noise to its inputs, the corresponding optimization problem for EOT becomes

x = argmax x E d∼N (0,σ 2 I) [∇ x L(θ, x, y)| x+d ],

which is the same as the approximate solution to our second-order attack method.

Note a significant difference between our method and EOT is that the random noise added in EOT depends on its corresponding defense model, whereas randomness in our method is independent of a defense model. In the experiments, we show our attack method dramatically reduces the accuracy of a defense model proposed by Madry et al. (2017) .

4. CERTIFIABLE ROBUSTNESS:

The effectiveness of the proposed attack method, as we will show in the experiments, suggests defending from adversarial attack is extremely difficult, and any defense model without certifiable robustness are always possible to be bypassed by stronger attacks.

Inspired by the PixelDP method (Mathias et al., 2018) , we propose a framework that enables certifiable robustness on any classifier. Intuitively, our approach adds random noise to pixels of adversarial examples before classification, to eliminate the effects of adversarial perturbations. The most important feature of this framework is that it allows calculation of an upper bound on the tolerable size of attacks.

Algorithm 1 Certifiable Robust Classifier:

Require: An input image x; A standard deviation σ > 0; A classifier f over {1, . . . , k};

Number of iterations n (n = 1 is sufficient if only the robust classification c is desired). 1: Set i = 1. 2: for i ∈ [n] do 3:

Add i.i.d. Gaussian noise N (0, σ 2 ) to each pixel of x and apply the classifier f on it. Let the output be c i = f (x + N (0, σ 2 I)). 4: end for 5: Estimate the distribution of the output as p j = #{ci=j:i=1,...,n} n . 6: Calculate the upper bound

L = sup α>1 -2σ 2 α -log 1 -p (1) -p (2) + 2 1 2 p 1-α (1) + p 1-α (2) 1 1-α

where p (1) and p (2) are the first and the second largest values in p 1 , . . . , p k . 7: Return classification result c = argmax i p i and the tolerable size of the attack L.

Our approach is summarized in Algorithm 1. In the following, we develop theory to prove the certifiable robustness of the proposed algorithm. Our goal is to show that if the classification of x in Algorithm 1 is c, then for any examples x such that xx 2 ≤ L, the classification of x is also c.

To prove our claim, first recall that a stochastic classifier f over {1, . . . , k} is a classifier whose output f (x) has a multinomial distribution over {1, . . . , k} with probabilities as (p 1 , . . . , p k ). In this context, robustness to an adversarial example x generated from x means argmax i p i = argmax j p j with P (f (x) = i) = p i and P (f (x ) = j) = p j , where P (•) denotes the probability of a specific output value. In the remainder of this section, we show Algorithm 1 achieves such robustness based on the Rényi divergence, starting with the following lemma.

Lemma 1 Let P = (p 1 , . . . , p k ) and Q = (q 1 , . . . , q k ) be two multinomial distributions over the same index set {1, . . . , k}. If the indexes of the largest probabilities do not match on P and Q, that is argmax i p i = argmax j q j , then

D α (Q P ) ≥ -log 1 -p (1) -p (2) + 2 1 2 p 1-α (1) + p 1-α (2) 1 1-α (5)

where p (1) and p (2) are the largest and the second largest probabilities in p i 's.

To simplify notation, we define M p (x 1 , . . . , x n ) = 1 n n i=1 x p i 1/p as the generalized mean. The RHS in condition (5) becomes

-log 1 -2M 1 p (1) , p (2) + 2M 1-α p (1) , p (2) .

Lemma 1 proposes a lower bound of the Rényi divergence for changing the index of the maximum of P , i.e., for any distribution

Q, if D α (Q P ) < -log 1 -2M 1 p (1) , p (2) + 2M 1-α p (1) , p (2)

, the index of maximum of P and Q must be the same. Based on Lemma 1, we obtain our main theorem on certifiable robustness, validating our claim:

Theorem 2 Suppose we have x ∈ X , and a potential adversarial example x ∈ X such that

x -x 2 ≤ L. Given a k-classifier f : X → {1, . . . , k}, let f (x + N (0, σ 2 I)) ∼ (p 1 , . . . , p k ) and f (x + N (0, σ 2 I)) ∼ (p 1 , . . . , p k ).

If the following condition is satisfied, with p (1) and p (2) being the first and second largest probabilities in p i 's:

EQUATION

then argmax i p i = argmax j p j With Theorem 2, we can enable certifiable robustness on any classifier f by adding i.i.d. Gaussian noise to pixels of inputs during testing, as done in Algorithm 1. It provides an upper bound for the tolerable size of attacks for a classifier. Since the upper bound only depends on the output distribution (p 1 , . . . , p k ), one can evaluate the bound based only on natural examples. Note the evaluation requires adjustment and computing confidence intervals for p (1) and p (2) , but we omit the details as it is a standard statistical procedure. In the experiments, we use the end points of the 95% confidence intervals for p (1) and p (2) .

Based on the property of generalized mean, one can show that the upper bound is larger when the difference between p (1) and p (2) becomes larger. This is consistent with the intuition that a larger difference between p (1) and p (2) indicates more confident classification. In other words, more confident classification, in the sense that more probability concentrated on one class, is beneficial for robustness.

It is worth mentioning that, as pointed out in (Mathias et al., 2018) , the noise is not necessarily added directly to the inputs but also to the first layer of a DNN. Given the Lipschitz constant of the first layer, one can still calculate an upper bound using our analysis. We omit the details here for simplicity.

Compared to the upper bound in PixelDP, our upper bound is strictly higher. We show the improvement using a simulation detailed in the Appendix. In the next section, we propose a simple strategy to improve the empirical performance of this framework.

5. IMPROVED CERTIFIABLE ROBUSTNESS:

In Algorithm 1, for a classifier f with a standard DNN, the added Gaussian noise is harmful to the classification accuracy on the original data. As discussed above, inaccurate prediction, in the sense that p (1) and p (2) are close, leads to weak robustness. Fortunately, one strength of Algorithm 1 is it requires nothing particular on the classifier f , which yields flexibility to modify f to make it more robust against Gaussian noise.

Note robustness to Gaussian noise is much easier to achieve than robustness to carefully crafted adversarial examples. In PixelDP, the authors incorporated noise by directly adding the same noise during the training procedure. However, we note that there have been notable efforts at developing robust DNNs to natural perturbations (Xie et al., 2012; Zhang et al., 2017 ); yet, these methods failed to defend models from adversarial attacks, as they are not particularly designed for that task.

Our framework allows us to adapt these methods to improve the accuracy of classification when Gaussian noise is present, improving the robustness of our model. We emphasize that a connection between robustness to adversarial examples and robustness to natural perturbation (Xie et al., 2012; Zhang et al., 2017) has been established, which introduces a much wider scope of literature into the adversarial defense community.

Stability Training:

The idea of introducing perturbations during training to improve model robustness has been studied in many works. In (Bachman et al., 2014) 

) = L 0 + γL stability (x, x ) = L 0 + γD(f (x), f (x ))

, where γ controls the strength of the stability term. As we are interested in a classification task, we use cross-entropy as the distance D between f (x) and f (x ), yielding the stability loss L stability =j P (y j |x) log P (y j |x ) where P (y j |x) and P (y j |x ) are the probabilities generated after softmax. In this paper, we add i.i.d. Gaussian noise to each pixel of x to construct x , as suggested in (Zheng et al., 2016) . Note that this is in the same spirit as adversarial training, but is only designed to improve the classification accuracy under a Gaussian perturbation.

6. EXPERIMENTS:

We conduct experiments to evaluate the performance of our proposed methods in terms of attack effectiveness and defense robustness. Our methods are tested on the MNIST and CIFAR-10 data sets.

The architecture of our model follows the ones used in (Madry et al., 2017) . Specifically, for the MNIST data set, the model contains two convolutional layers with 32 and 64 filters, each followed by 2 × 2 max-pooling, and a fully connected layer of size 1024. For the CIFAR-10 dataset, we use a wide ResNet model (Zagoruyko & Komodakis, 2016; He et al., 2016a) . The network contains 5 residual unites with (16, 160, 320, 640) filters. The implementation details are provided in the Appendix. In both datasets, image intensities are scaled to [0, 1], and the size of attacks are also rescaled accordingly. For reference, a distortion of 0.031 in the [0, 1] scale corresponds to 8 in [0, 255] scale.

6.1. THEORETICAL BOUND:

We first evaluate the theoretical bounds of the size of attacks. With Algorithm 1, we are able to classify a natural image x and calculate an upper bound for the size of attacks L for this particular image. Thus, with a given size of the attack L 0 , we know the classification result is robust if L 0 < L.

Further, if the classification for a natural example is correct and robust for L 0 simultaneously, we know any adversarial examples x such that xx 2 < L 0 will be classified correctly. Therefore, we can calculate the proportion of such examples in the test set to determine a lower bound of accuracy under attack of size L 0 . We plot different lower bounds for various L 0 for both MNIST and CIFAR-10 in Figure 1 . To interpret the result, for example on MNIST, when σ = 0.4, Algorithm 1 achieves at least 50% accuracy under attacks whose 2 -norm sizes, xx 2 , are smaller than 0.8.

A clear trade-off between the tolerable attack sizes and the accuracy lower bound is present in Figure 1 . This is anticipated, as our lower bound 6 indicates a higher standard deviation σ results in a higher proportion of robust classification, but in practice, a larger amount of noise would also lead to a worse classification accuracy.

6.2. EMPIRICAL RESULTS:

We next perform classification and measure the accuracy on real adversarial examples to evaluate the performance of our attack and defense methods. We first apply our attack method to the state-of-the- art defense model proposed in (Madry et al., 2017) MNIST In the first plot in Figure 2 , we monitor the average 2 norm of gradients of the loss function during the construction of adversarial examples. Specifically, we compute

1 Nbatch i∈I ∇ x L(θ, x, y)| x (t)

i 2 for each t, where I is the index set of a batch. We monitor this quantity under the setting 1, 2 and 4 in Table 1 . The result shows the 2 norms of the gradients of the adversarially trained model are much smaller than the ones of the naturally trained model, validating our explanation in Section 3, that an adversarially trained model tends to make the loss function flat in the neighborhood of natural examples. It also shows our attack method can find adversarial examples with large loss more efficiently, by incorporating second-order derivative information.

In the second plot, we show the classification accuracy on MNIST under the setting 1, 2 and 4. The plot suggests that S-O attack is able to dramatically reduce the accuracy of Madry's model compared to PGD attack. The resulting accuracy is even worse than the one from the naturally trained baseline model. Note we do not include other attack methods such as C&W attack (Carlini & Wagner, 2017b) as no first-order attack is significantly stronger than PGD (Madry et al., 2017) . We include the results of other attack methods in the Appendix.

In the third plot, we show the accuracy of different defense models under S-O attack, under the setting 3, 4 and 5. The plot suggests our model achieves better accuracy than both the baseline and the Madry's model. Note in all experiments for evaluating our defense model, we use S-O attack as the adversary. The reason is if we use other attacks such as PGD, our defense model may cause the problem of obfuscating true gradients via randomization (Athalye et al., 2018) , thus achieving robustness unfairly. On the other hand, as we discussed in Section 3, S-O attack is equivalent to EOT attack with respect to Gaussian noise (the noise we used in our defense model), thus it avoids obfuscating the true gradients via randomization. As a result, our results are reliable.

CIFAR-10:

In Figure 3 , we show the classification accuracy on CIFAR-10 under the setting 3, 4 and 5. In addition, we include results for PixelDP from (Mathias et al., 2018) to show how stability training helps improve classification accuracy. Here the attack method we use is the S-O attack. As a comparison, our defense model obtains higher accuracies than both Madry's model and PixelDP against 2 and ∞ attacks. Overall, stability training combined with Gaussian noise shows a promising level of robustness and performs better than other models even under attacks that incorporate randomization. Another strength of our method is that stability training only requires twice the computational time, whereas adversarial training is extremely time-consuming due to the iterative construction of adversarial examples.

7. DISCUSSION:

Adversarial Training Overfit to the Choice of Norms In (Madry et al., 2017) , the authors propose an adversarially trained model and argue it is robust against 2 attacks even though it is trained against ∞ attacks. Our proposed 2 attack significantly reduces their classification accuracy. On the other hand, the ∞ version of S-O attack also successfully attacks the adversarially trained model based on 2 attacks. We include this experiment result in the Appendix. In general, we find adversarial training overfit to the choice of norms.

On the Gap between Empirical and Theoretical Results:

A noticeable gap exists between the theoretical bound shown in Figure 1 and the empirical accuracy. There are three possible explanations for this gap, each pointing to a direction for future works. The first explanation for the gap is that the proposed upper bound is not tight. Another possible reason is that the empirical results should be worse for stronger attacks that have not been proposed, as it has happened to many defense models. The third one is due to the limitation of the 2 distance. Although our framework is proposed in the context of adversarial attacks, where potential attacks are limited to be non-perceptible by humans, our theoretical analysis does not distinguish the types of perturbations up to their 2 norms. In practice, one can perturb a few pixels with large values, such that the change is perceptible by humans and indeed leads to a change in classification, but it only yields small 2 distance. The existence of such perturbations enforces the small upper bound. Future work might explore similar guarantees for the stronger ∞ distance.

8. CONCLUSION:

We propose S-O attack, a new attack method based on an approximated second-order derivative of the loss function. S-O attack can effectively attack adversarial training, a training strategy that demonstrated significant robustness in previous works. We also propose an analysis on constructing defense models with certifiable robustness, combined with a strategy based on stability training for improving the robustness of the defense models. The experimental results show our defense model achieve better robustness compared to previous works.

Therefore, if we have

EQUATION

Then from Lemma 1 we know that the index of the maximums of f (x + N (0, σ 2 )) and f (x + N (0, σ 2 )) must be the same, which means they have the same prediction, thus implies robustness.

D COMPARISON BETWEEN BOUNDS:

We use simulation to show our proposed bound is higher than the one from PixelDP (Mathias et al., 2018) .

In PixelDP, the upper bound for the size of attacks is indirectly defined: if p (1) ≥ e 2 p (2) + (1 + e ) and the added noise has the distribution N (0, σ 2 I), then the classifier is robust against attacks whose 2 size is less than .

As both bounds are determined by the models and data only through p (1) and p (2) , it is sufficient to compare them with simulation for different p (1) and p (2) as long as p (1) ≥ p (2) ≥ 0, p (1) + p (2) ≤ 1 and p (1) + p (2) ≥ 0.2 are satisfied.

For fixed σ, and δ are two tuning parameters that affect the result. For a fair comparison, we use a grid search to find and δ that maximizes their bound.

Figure 4 : The upper bounds under different p (1) and p (2) . In both settings, we let the variance of Gaussian noise σ 2 = 1. Our bound (red) is strictly higher than the one from PixedDP(blue).

The simulation result shows our bound is strictly higher than the one from PixelDP.

E COMPARISON TO OTHER ATTACK METHODS:

We first compare our attack method to well-known C&W attack (Carlini & Wagner, 2017b) on MNIST in FIgure 5 .

We then present experimental results from (Schott et al., 2018) for various existing attack methods with the size of attacks 2 = 1.5, and compare them to our S-O attack in Table 2 . All previous methods, including FGSM (Kurakin et al., 2016 ), DeepFool (Moosavi-Dezfooli et al., 2016) , and 2 version PGD (Madry et al., 2017) cannot significantly reduce the accuracy of Madry's model.

The only attack method that achieves similar performance is Boundary Attack proposed by Schott et al. (2018) , and we recognize it as concurrent work. Boundary attack iteratively flips pixels between the perturbed value and its original value to explore the minimum perturbation for altering the classification results. Although it produces a small number of perturbations, one major issue of the Boundary Attack is its computational inefficiency. It is hard to scale up to even CIFAR10. 

H IMPLEMENTATION DETAILS:

In this section, we specify the hyperparameters used in our experiments and other details. For all experiments, the baseline models are implemented using the codes from <https://github.com/ MadryLab/mnist_challenge> and <https://github.com/MadryLab/cifar10_ challenge>.

Our defense model only requires the following modification: 1) For stability training, we remove the adversarial training part and include the stability training regularizer. 2) At test time, we add i.i.d. Gaussian noise to pixels before feeding the images into the model.

For MNIST, we use stability training with STD of the Gaussian noise being σ train = 0.2. The STD of Gaussian noise during testing is σ test = 0.2. For CIFAR-10, the STD of Gaussian noise in stability training σ train = 100 255 . The STD of Gaussian noise during testing is σ test = 50 255 . Weight of the regularizor γ = 1 for both data sets.

:



Figures and Tables:

Figure 1: Accuracy lower bounds for MNIST data set (left) and CIFAR-10 data set (right) against tolerable sizes of attacks with various choices of σ in Algorithm 1.

Figure 2: MNIST data set Left: Average 2 norm of the gradients of the loss function for a batch in each iteration during adversarial attack. Middle: Classification accuracy for Madry's model under PGD attack and S-O attack. Right: Accuracy for different models under the same S-O attack.

Figure 5: S-O attack compared to C&W attack on MNIST under various 2 sizes.

Figure 6: Accuracy of adversarial training via L ∞ and L 2 attacks against L ∞ S-O attack. The model based on L 2 is clearly vulnerable to L ∞ attacks.

Figure 7: Above: Natural examples from MNIST. The correct labels are 5,9,7,3,4,9,6. Below: Adversarial examples with perturbation size 2 = 2.0. The adversarially trained model predictions are 3,4,2,8,9,4,5.

the authors regard perturbing models as a construction of pseudo-ensembles, to improve semi-supervised learning. More recently, Zheng et al. (2016) used a similar training strategy, named stability training, to improve classification robustness on noisy images.For any natural image x, stability training encourages its perturbed version x to yield a similar classification result under a classifier f , i.e., D(f (x), f (x )) is small for some distance measure D. Specifically, given a loss function L 0 for the original classification task, stability training introduces a regularization term L(x, x

Table content: <table/>

based on adversarial training. In all experiments, we focus on five settings, summarized in Table1. The adversarially trained model is trained against ∞ PGD attack while all the attacks are 2 attack. Five settings of attack methods and defense models.

Table content: <table><tr><td colspan="2">Number Defense Model</td><td>Attack Method</td></tr><tr><td>1</td><td>Naturally Trained Model</td><td>PGD</td></tr><tr><td>2</td><td>Adversarial Training (Madry's)</td><td>PGD</td></tr><tr><td>3</td><td>Naturally Trained Model</td><td>second-order (S-O) attack</td></tr><tr><td>4</td><td>Adversarial Training (Madry's)</td><td>second-order (S-O) attack</td></tr><tr><td>5</td><td colspan="2">Stability trained model with Gaussian Noise (STN) second-order (S-O) attack</td></tr></table>

Different attack methods on Madry's model. ∞ S-O ATTACK BREAKS ADVERSARIAL TRAINING VIA L 2 ATTACKSWe apply L ∞ S-O attack to Madry's models based on L ∞ and L 2 attacks respectively. The accuracy is plotted in Figure6. It is clear that only the model trained against L ∞ attack is robust to the L ∞ attack. This result supports our claim that adversarial training overfits to the choice of norm.

Table content: <table><tr><td/><td colspan="5">FGSM DeepFool PGD Boundary Attack S-O (ours)</td></tr><tr><td>Madry's Model</td><td>96%</td><td>91%</td><td>88%</td><td>37.0%</td><td>39.5%</td></tr></table>

Peer review (iclr2019):
 This paper consists of two parts: a 2nd-order attack method and a certification for robustness. The paper is well written and easy to follow. However, addressing of similarity and comparison with some previous methods could be improved. First of all, the motivation of 2nd order attack is clear and reasonable: for adversarially trained model at minimax, the gradient is close to vanishing, so 2nd order information helps a lot to find actual adversarial examples in this case. However, 1. A lot of defenses have tried to modify the networks to make even computing the gradient difficult if not impossible. In this case, how effective is the 2nd order attack? I would like to see some discussion of this. 2. While the starting point seems like a powerful attack method. The 2nd order information is only approximately computed via finite differences. A powerful method with weak approximation will sounds more powerful than a weak method to start with, but the actual effectiveness will need more systematic comparison. I think adding some studies of the accuracy or variances of the 2nd order information with the proposed approximation method (under natural setting and maybe also under the setting where the networks are modified to make even 1st order information hard to compute) would definitely help. 3. Also after the approximation, as mentioned in the paper, the algorithm becomes equivalent to EOT attacks with Gaussian noises. The EOT attacks are also more general to allow different types of noises. While it might not make lots of sense to compare with EOT attacks in the experiments as the two algorithms seem to be exactly the same, it would help of more discussions could be devoted to justify how the proposed algorithm is novel given the previously existed EOT attack. 4. In the experiments on adversarially trained models, the adversarial trained models are trained against l_inf attack, while the actual attack is l2. This seems unfair. Since the author mentioned that it is easy to extend their method to l_inf attack. It would be more justifiable if the results with matching attack types are shown instead of the current ones. The certified robustness is an interesting take, too. However, the bounds might be too strong: as far as I understand, it does not rely much on the properties of the underlying neural networks f. So in order to be applicable to all kinds of weird non-robust neural networks uniformly, the bounds cannot be too tight. To get useful certificate level, a too heavy noise level sigma might be needed and potentially destroys the classification accuracy of the original model f. This is acknowledged in the *gap between theory and empirical* section. And it makes the importance of such kind of bounds a bit weak. 5. Also, the *stability training* procedures derived based on this bounds is quite similar to some previous methods. For example, the objective function is very similar to *logit pairing*, which add an extra term to bound the similarity between two logits from an adversarial or noisy version. The empirical results will be much stronger if more closely related methods are included in the comparison. For example, logit pairing, as well as simple training with Gaussian perturbation on inputs. In summary, this paper provide some interesting perspectives to adversarial attacks and certifications. However, the main algorithms are very similar to some existing methods, more discussion could be used to compare with the existing literature and clarify the novelty of the current paper. The empirical results could also be made more stronger by including more relevant baseline methods and more systematic study of the effectiveness of some approximation methods adopted