Title: THE MANIFOLD ASSUMPTION AND DEFENSES AGAINST ADVERSARIAL PERTURBATIONS

Abstract: In the adversarial-perturbation problem of neural networks, an adversary starts with a neural network model F and a point x that F classifies correctly, and applies a small perturbation to x to produce another point x that F classifies incorrectly. In this paper, we propose taking into account the inherent confidence information produced by models when studying adversarial perturbations, where a natural measure of "confidence" is F (x) ∞ (i.e. how confident F is about its prediction?). Motivated by a thought experiment based on the manifold assumption, we propose a "goodness property" of models which states that confident regions of a good model should be well separated. We give formalizations of this property and examine existing robust training objectives in view of them. Interestingly, we find that a recent objective by Madry et al. encourages training a model that satisfies well our formal version of the goodness property, but has a weak control of points that are wrong but with low confidence. However, if Madry et al.'s model is indeed a good solution to their objective, then good and bad points are now distinguishable and we can try to embed uncertain points back to the closest confident region to get (hopefully) correct predictions. We thus propose embedding objectives and algorithms, and perform an empirical study using this method. Our experimental results are encouraging: Madry et al.'s model wrapped with our embedding procedure achieves almost perfect success rate in defending against attacks that the base model fails on, while retaining good generalization behavior.

1. INTRODUCTION:

In the adversarial perturbation problem of neural networks, an adversary starts with a neural network model F and a point x that F classifies correctly (we assume that F ends with a softmax layer, which is common in the literature), and applies a small perturbation to x to produce another point x that F classifies incorrectly. Szegedy et al. (2013) first noticed the vulnerability of existing (deep) neural networks to adversarial perturbations, which is a somewhat surprising phenomenon given the great generalization capability of these networks. Since then, a line of research (see, for example, Goodfellow et al. (2014) ; Papernot et al. (2016b) ; Miyato et al. (2017) ; Madry et al. (2017) ) has been devoted to harden neural networks against adversarial perturbation. However, while modest progress has been made, until now there is still a large gap in successfully defending against more advanced attacks, such as attack by Carlini & Wagner (2017) .

In this paper, we propose taking into account the inherent confidence information produced by models when studying adversarial perturbations. To this end, a natural measure of confidence is F (x) ∞ (i.e., how confident F is about its prediction?) We motivate this consideration with a thought experiment based on the manifold assumption (Zhu & Goldberg (2009) ; man) that is commonly made in unsupervised and semi-supervised learning, which states that natural data points lie on (or near to) separate low dimensional manifolds for different classes. Essentially, if one believes that deep neural networks learn to approximate well these low dimensional manifolds, then an ideal model should have the property that it can confidently distinguish points from natural manifolds as they are well separated due to the assumption. Moreover, since the learner never sees points that are far away from the natural manifolds, an ideal model should not claim confidence there.

Taking this perspective, we propose a goodness property which states that confident regions of a good model should be well separated. We give formalizations of this property and examine existing robust training objectives in view of them. Interestingly, we find that a recent objective function by Madry et al. (2017) encourages training a model that satisfies well our formal version of the goodness property, in the sense that high-confidence predictions of different classes are well separated. On the other hand, our analysis also indicates that there could be many points with wrong but low-confidence predictions. Therefore, if Madry et al.'s model is indeed a good solution to their objective, then we can distinguish between good and bad points with confidence, and try to embed a low-confidence point back to confident regions to get (hopefully) the correct prediction.

We propose two embedding objectives: (1) δ-Most Confident Neighbor (MCN δ ), where MCN δ (F, x) = arg max z∈N (x,δ) F (z) ∞ for a point x, a radius parameter δ > 0, and N (x, δ) the δ-neighborhood around x. (2) p-Nearest Confident Neighbor (NCN p ), where NCN p (F, x) = arg min z z -x subject to F (z) ∞ ≥ p, for a point x and a confidence parameter p ∈ (0, 1). With these, the end to end predictions become F (MCN δ (F, x)) and F (NCN p (F, x)). We note that these objectives are semantic: They fail only when the model has a confident but wrong prediction in the neighborhood.

We perform an empirical study over CIFAR10. We first empirically validate that Madry et al.'s model is better, in view of our goodness property, than models trained without a robustness objective. We then give end-to-end defense results based on our method. Specifically, we propose using gradient based optimization, such as Carlini-Wagner attacks Carlini & Wagner (2017) (which, however, are now used for defense) to solve MCN δ or NCN p . Our empirical results are encouraging: (1) It achieves almost perfect success rate in defending against attacks that the base model fails on, and (2) It also retains the good generalization behavior of the base model.

The rest of the paper is organized as follows: We first discuss important prior work in Section 2 and some preliminaries in Section 3. Then Section 4 proposes the goodness property, and examines Madry et al.'s robust training objective function in view of the property. We then present embedding objectives and algorithms for handling low-confidence points in Section 5. Section 6 performs an empirical study where we validate that Madry et al.'s robust model satisfies well our goodness property, and then give defense results for our technique. Section 7 concludes with discussions on implications of our method. Szegedy et al. (2013) first observed the susceptibility of deep neural networks to adversarial perturbations. Since then, a large body of work have been devoted to studying hardening neural networks for this problem (a subset of work in this direction is Goodfellow et al. (2014) ; Papernot et al. (2016b) ; Miyato et al. (2017) ). Simultaneously, another line of work have been devoted to devise more effective or efficient attacks (a small set of work in this direction is Moosavi-Dezfooli et al. (2016) ; Papernot et al. (2016a) ; Carlini & Wagner (2017) ). Unfortunately, there still seems to be a large gap for the defense methods to defend against more sophisticated attacks, such as Carlini-Wagner attacks Carlini & Wagner (2017) . For example, while the recent robust residual network constructed by Madry et al. (2017) achieves encouraging robustness results on MNIST, on CIFAR10 the accuracy against a strong adversary, such as attacks by Carlini & Wagner (2017) , can be as low as 45.8%.

2. PRIOR WORK:

A dominant defense approach is to add to the training objective function an appropriate robustness component to improve robustness of the resulting model. Our method is fundamentally different and tries to complement training-based method by exploiting fundamental structures a model has learned. Our method has some remote similarities with a recent proposal by Lu et al. (2017) , which tries to exploit features deep in the network (that is "semantics" of a model) to detect adversarial examples. However, beyond detecting adversarial attacks, our work takes a step further to compute correct prediction on the adversarial examples.

Our work is inspired by a recent line of research which demonstrates that neural networks are effective devices to represent low dimensional manifold data (for example, Rifai et al. (2011) ; Shaham et al. (2015) ; Basri & Jacobs (2016) ). Specifically, in Basri & Jacobs (2016) , the authors studied a specific type of manifolds called monotonic chains. They showed that neural networks can effectively represent data that both fall on, and near the manifolds (see "Section 4. Error Analysis" of the corresponding paper). While their network is not trained but is specifically constructed to fit the data, we believe that it has provided evidence that deep networks can extract intrinsic geometric structures. To this end, one may interpret our work as arguing that if manifold assumption indeed holds, and the model approximates natural manifolds well, then it may not be surprising to see the coexistence of good generalization and adversarial perturbations. In particular, one may expect to see many wrong predictions though with low confidence.

3. PRELIMINARIES:

As in existing work, such as Carlini & Wagner (2017) ; Papernot et al. (2016b) , we define F to be a neural network after the softmax layer. With this notation, the final classification is then C F (x) = arg max i F (x) i where F (x) i gives the confidence of the network in classifying x for class i. We use Z(x) to denote part of F except the softmax layer. That is, Z(x) computes the logits to be fed into the softmax function. We use C to denote the class of all labels. We need the following definitions: Definition 1 (p-confident point and p-confident region). Let p ∈ [0, 1] be a parameter, F be a model, and

l ∈ C. A point x is p-confident for label l if F (x) l ≥ p. Further, the p-confident region of F for label l is M p l = {x | F (x) l ≥ p}.

That is M l is the set of points where F has confidence at least p for label l. Definition 2. Let d(•, •) be a distance metric between points, and M 1 , M 2 be two sets of points, the distance between

M 1 and M 2 , d(M 1 , M 2 ) is defined to be d(M 1 , M 2 ) = inf x∈M1,y∈M2 d(x, y).

For example, a common distance metric used in studying adversarial perturbations is d(x, y) = x -y ∞ where • ∞ is the infinity norm of a vector. Therefore

d(M 1 , M 2 ) is the infimum of x -y ∞ for x ∈ M 1 , y ∈ M 2 .

Definition 3 (Cross entropy). Let p, q be two discrete probability distributions, the cross entropy between p, q is H(p, q) =i p i log q i , where the log is base 2.

4. GOODNESS PROPERTY AND MADRY ET AL.'S OBJECTIVE:

This section develops our main arguments. In particular:

• We propose a goodness property of models which states that confident regions of a good model should be well separated. • We examine existing robust training objectives and demonstrate that an objective function of Madry et al. (2017) encourages very good separation for p-confident points with large p, but has a weak control of points that are wrong but with low confidence.

Goodness Property. Manifold assumption in unsupervised and semi-supervised learning states that natural data points lie on (or near to) separate low dimensional manifolds for different classes. Under this assumption what would an ideal model look like? Clearly, we would expect that an ideal model can confidently classify points from the manifolds, while not claiming confidence for points that are far away from those manifold. Therefore, we propose the following goodness property

Confident regions of a good model should be well separated.

The following definition captures well-separatedness in a strict sense, Definition 4

((p, δ)-separation). Let p ∈ [0, 1], δ ≥ 0, and d(•, •) be a distance metric. F is said to have (p, δ)-separation if inf l =l d(M p l , M p l ) ≥ δ

where M p l and M p l are p-confident regions for labels l, l , respectively. It is also natural to consider the following probabilistic version of Definition 4, Definition 5 ((p, q, δ)-separation). Let D be a data generating distribution, p, q ∈ [0, 1], δ ≥ 0, and

d(•, •) be a distance metric. F is said to have (p, q, δ)-separation if Pr (x,y)∼D (∃y = y, x ∈ N (x, δ)) F (x ) y ≥ p ≤ q, where N (x, δ) = {x | d(x, x ) ≤ δ}.

Note that these two definitions have some important differences: (1) Definition 4 is defined over sets of points while Definition 5 is defined point-wise. Further, Definition 5 allows certain points to be "bad" in the sense that they are not separated from confident points with wrong predictions. (2) Perhaps more importantly, Definition 5 depends on the data generating distribution, but Definition 4 is solely a property of the model. We are not aware of how to train a model to satisfy Definition 4. However, interestingly, we find that existing robust training can indeed give guarantees with respect to Definition 5. We next give an analysis of this.

Objective function of Madry et al. (2017) . We now examine objective function used in Madry et al. (2017) , and prove that it encourages training a model that satisfies Definition 5. Complementing this, we show that their objective has a weak control of points with low-confidence but wrong predictions.

To start with, their objective function is of the form

EQUATION

)

where D is the data generating distribution, S is set of allowed perturbations (for example S = {∆ | ∆ ∞ ≤ δ}), and L(θ, x, y) is the loss of θ on (x, y). Madry et al. (2017) uses cross entropy loss function:

L(θ, x, y) = H(1 y , F θ (x)) = -log F θ (x) y

where F θ is the model instantiated with parameters θ, and 1 y is the indicator vector of label y.

Denote κ(θ, x, y) = max ∆∈S L(θ, x + ∆, y), we have the following proposition,

Proposition 1. If ρ(θ) ≤ ε, then Pr (x,y)∼D (∃y = y, x ∈ x + S) F θ (x ) y ≥ p ≤ - ε log(1 -p)

That is, the probability of an x ∈ x + S that is p-confident on a different label vanishes as p → 1.

Proof. Let E be the event {∃y = y, x ∈ x+S, F θ (x ) y ≥ p}. If E happens, then F θ (x ) y ≤ 1-p, and κ(θ, x, y) ≥ -log(1 -p), therefore by Markov's inequality1 ,

Pr (x,y)∼D [E] ≤ Pr (x,y)∼D κ(θ, x, y) ≥ -log(1 -p) ≤ - ε log(1 -p) .

The proof is complete.

This immediately generates the following corollary, Corollary 1. Let S be a region defined as

{∆ | d(∆, 0) ≤ δ}. If ρ(θ) ≤ ε, then the model F θ is (p, -ε log(1-p) , δ)-separated.

This indicates that even if a model is only a somewhat good solution to (1), meaning ρ(θ) ≤ ε for somewhat small ε, (note that in reality D is unknown and a learner can only approximate (1)), then p-confident points will be well separated (in the sense of Definition 5) as soon as p increases.

The above proposition considers a situation where we have a confident but wrong point (with confidence p). What about points that have wrong but low-confidence predictions? For example, the confidence on the wrong label is only 1 2 + ν for some tiny ν? Note that by setting p = 1/2 we derive immediately a bound ε (much weaker than -ε/ log(1 -p) for large p) on the probability that bad events happen. Further, without further assumptions, this bound in tight so that in a worst-case sense that there exists a bad model so that bound ε is achieved. We have the following proposition. Proposition 2. Let F θ be a neural network parameterized by θ, and

C F θ be the classification net- work. If ρ(θ) ≤ ε, then Pr (x,y)∼D (∃y = y, x ∈ x + S) C F θ (x ) = y ≤ ε.

Further the bound is tight.

Proof. Let E be the event {(∃y = y, x ∈ x + S) C F θ (x ) = y }. If E happens then F θ (x ) y ≤ 1 2

(otherwise x will be classified as y), and so κ(θ, x, y) ≥ -log(1/2) = 1. On the other hand, if E does not happen, then we can lower bound κ(θ, x, y) by 0. Therefore

ε ≥ E[κ(θ, x, y)] ≥ Pr[¬ E] • 0 + Pr[E] • 1 = Pr[E].

Tightness follows as we can force equality for each of the inequalities. The proof is complete.

Contrasting Proposition 1 and 2, we note the following:

• First, let us note that the objective function 1 is defined with respect to the data generating distribution D, which is unknown, and in reality we only have a training set to approximate the objective. Also, cross entropy function is unbounded (so in particular it can happen that ρ(θ) ≥ 1). Therefore, one may only expect that ρ(θ) is somewhat small.

• Nevertheless, even with a somewhat large ρ(θ), Proposition 1 indicates that highconfidence predictions of different classes will be well separated as soon as confidence p increases. On the other hand, Proposition 2 then indicates that there may still be many points that have wrong predictions with low confidence. • Finally, if we take the manifold point of view again, then intuitively it seems harder to control low-confidence points than to separate confident regions. This is because natural manifolds reside in lower dimensions and so there can be a large volume of low-confidence points at the confidence boundary. This thus indicates that handling low-confidence points may be the core difficulty in getting a good solution to (1).

5. EMBEDDING:

Our analysis from previous section shows that there can be good models with well-separated confident regions, yet there is essentially no control for uncertain points. However, since now uncertain points are distinguishable as they have low confidence, a natural plan to handle these points is to try to "embed them back" to confident regions. The rest of this section presents objective functions and algorithms for this purpose.

Objective Functions. We propose two objective functions for embedding.

Definition 6 (Most Confident Neighbor Objective). Let F be a model, • be a norm, and δ > 0 be a real number. The δ-Most Confident Neighbor objective (or simply MCN δ objective) computes:

EQUATION

where N (x, δ) is the δ-ball around x with respect to • , and • ∞ denotes the L ∞ -norm.

Definition 7 (Nearest Confident Neighbor Objective). Let F be a model, • be a norm, and p ∈ (0, 1) be a real number. The p-Nearest Confident Neighbor objective (or simply NCN p objective) computes:

EQUATION

)

where

• ∞ denotes the L ∞ -norm.

In short, MCN considers a δ-neighborhood of a point and use the most confident point in the neighborhood for prediction. On the other hand, NCN considers the nearest neighbor that achieves certain confidence threshold.

Model Shell. From an algorithmic point of view, our approach essentially tries to wrap around a learned model with a "shell" to handle points that are "slightly" out of the confident regions it has learned. There are many possible shells for this purpose. For example, a valid such shell is weighted majority vote. We thus begin by giving some general definitions.

Definition 8 (Model Shell). Let F be a model. A model shell G is an algorithm that takes as its input F and a point x ∈ R d to classify, and outputs a softmax layer G(F, x). In this paper we only consider the case where F is a model that is chosen apriori and fixed. In this case, the resulting model for classification is G(F, •), which maps a feature vector to a softmax layer. In this scenario, we say that F is the base model of the model shell G, and denote G(F,

•) as G[F ].

Model shell captures the intuition that we want to wrap around an existing model with another algorithm that can exploit semantics of the base model. In this paper, we only examine model shells with a restricted structure, which we call factor model shells. We define search factor, 

G(F, x) ≡ (F • H[F ])(x) = F (H(F, x)) .

A factor model shell captures our intuitions from MCN or NCN objectives. That is, we first apply a search factor H to find another feature point x = H(F, x), and then apply the base model F on x to produce a final prediction. As a result, a factor model shell for MCN δ objective should compute the final prediction as:

EQUATION

and accordingly for NCN p objective:

EQUATION

We note the following:

• Exact computations of (4) and ( 5) provide semantic defenses. That is, the final prediction is wrong only if the model has a confident but wrong prediction in the neighborhood. Furthermore, our discussion from Section 4 indicates that for good models, wrong predictions should also have low confidence. Therefore, embedding should be effective in fixing low-confidence errors of good models. • We note that the resulting factor model shells, (F • MCN δ ) and (F • NCN p ) are nondifferentiable as MCN δ (F, x) and NCN p (F, x) are non-differentiable with respect to x (they are argmin or argmax over a ball). This renders existing attacks fail to work directly to attack F • MCN δ or F • NCN p , since they all require the assumption that the output softmax layer is differentiable with respect to the input feature vector x 2 As a result, this forces attacks to either attack the base model F and then transfer attacks to the model shell, or has to find some differentiable approximations or derivative-free optimization to attack MCN δ and NCN p directly.

Algorithms. We now give one concrete algorithms to solve (2) and (3). To start with, we note that the optimization for solving MCN δ (2) is nothing but for each label t ∈ C we try to find

EQUATION

2 For example, let us examine one objective function used in Carlini-Wagner Carlini & Wagner (2017) , which is one of the strongest attacks known. They use an objective function of the form (f5 on pp. 6 of their paper Carlini & Wagner (2017)):

f (x ) = -log(2F (x )t -2)

where F (x )t denotes the coordinate of F (x ) at label t. This objective is differentiable in x as F is differentiable in x . We note that such a first-order assumption is natural for neural networks because neural networks are typically composition of differentiable functions. With first order information, attacks can "relatively accurately" follow the gradient direction to modify the image feature so as to increase the confidence of the model in incorrect labels and thus produce adversarial perturbations. and then compute z t * for t * = arg max t F (z t ) t . Now, however, we can solve (6) using any preferred gradient-based optimization (for example, projected gradient descent Nocedal & Wright (2006) ). This thus gives the following factor model shell:

Algorithm 1 Solving MCN δ objective. Input: x a feature vector, δ > 0 a real parameter, a base model F , any gradient-based optimization algorithm O to solve the constrained optimization problem defined in ( 6). 1: function MCNOracleShell(x, δ, F ) 2:

for t ∈ C do 3:

z t ← O(x, F, t) 4: return z t * where t * = arg max t∈C F (z t ) t

We note that solving ( 6) is similar to a targeted adversarial attack which tries to modify x so as to increase the confidence on label t. Therefore an adversarial attack, such as strong attack proposed in Carlini & Wagner (2017) , can be used as O here.

Another concern is that gradient-based optimization may only find local optimal in the neighborhood. However, we note that global optimal may not be needed for our method to work, as long as local minima of the correct class are "separated" from local minima of incorrect classes. More specifically, let l be the correct class, and

S l = {z : z ∈ N (x, δ), z is a local maximal of F (x) ∞ , F (z) ∞ = F (z) l } and S -l = {z : z ∈ N (x, δ), z is a local maximal of F (x) ∞ , F (z) ∞ = F (z) l }

then local optimal works as soon as

inf z∈S l F (z) ∞ > sup y∈S -l F (y) ∞ .

We can also take a similar path to solve NCN p objective with standard numeric optimization. Note that F (z) ∞ ≥ p is equivalent to ∃t, F (z) t ≥ p. Therefore, we can solve

z t = arg min F (z)t≥p z -x (7)

for every t, and then compute z t * where t * = arg min t z t -x . By a similar reasoning as above, z t * is the solution to problem 3. This thus gives algorithm 2 for NCN p .

Algorithm 2 Solving NCN p objective. Input: x a feature vector, p > 0 a real parameter, a base model F , any gradient-based optimization algorithm O to solve the constrained optimization problem defined in (7). 1: function NCNOracleShell(x, p, F ) 2:

for t ∈ C do 3:

z t ← O(x, F, t) 4:

return z t * where t * = arg min t z t -x Solving (7), however, is not trivial. A standard method is the augmented Lagrangian method Bertsekas (1996) which turns the problem into solving a series of unconstrained optimization. For example, consider the following quadratic penalty function

Q(z, α, t) = z -x + α 2 ([F (z) -p] -) 2 ,

where [y] -denotes max{y, 0}. Then we can solve the unconstrained optimization min Q(z, α, t) for a series of different α, and terminates once we find a satisfying solution. The intuition is that (i) solving the unconstrained optimization is easy, (ii) by increasing the coefficient α, we can force the minimizer of the penalty function closer to the feasible region F (z) ≥ p, and (iii) for well chosen α, the minimizer of the penalty function is close enough to that of problem 7. Other classic constrained optimization algorithms to solve this problem are interior methods and sequential quadratic programming Nocedal & Wright (2006) . We also note a recent work Bienstock & Michalka (2014) which specifically focuses on optimizing convex objective over non-convex constraints, into which problem 7 falls as well.

first sample a batch of points K. For each p ∈ P, we try to find, for each point (x, y) in K, a point that is predicted as y = y with confidence ≥ p in its δ-neighborhood. For each p we get a fraction s p of points in K that such confident attacks can be found. We find that the robust model has much smaller s p for larger p and hence it satisfies our the goodness property better.

We then evaluate our end-to-end defense. We go through a random permutation of test data points, and measure the following for a point that the base model predicts correctly: (1) Susceptibility. That is, whether CW attack can successfully attack this point.

(2) Robustness. There are two cases: (i) the model is already robust to CW attack where we expect CarlinWagnerShell retains the robustness, and (ii) the model is vulnerable to CW attack, where we expect CarliniWagnerShell to harden the model.

(3) Generalization. That is, whether CarliniWagnerShell still predicts correctly on the point.

Comparing models using the goodness property. From Definition 5 and Proposition 1, our goal is to statistically estimate Pr (x,y)∼D (∃y = y, x ∈ N (x, δ))F (x ) y ≥ p . As mentioned above, we compare the robust model in Madry et al. (2017) and its natural variant. Let E b denote the bad event (∃y = y, x ∈ N (x, δ))F (x ) y ≥ p. We randomly sample batches of data points from the test set, and compute frequency that E b happens for each batch. To do so, we attack samples using a modified CW attack, which tries to generate an adversarial example within the norm bound where the model classifies incorrectly with high confidence. 1 : Results from testing the goodness property of base models. Each batch has 30 random samples. For each column, we record the number of samples that we can successfully find attacks of confidence at least p = 0.9 against the model corresponding to the column.

With these statistics we can thus estimate (p, q, δ)-separation (Definition 5) of the models in comparison. We have (details are deferred to Appendix A). Proposition 3 (Separation from statistics). The following two hold:

• With probability at least .9 the robust model in Madry et al. (2017) satisfies

Pr (x,y)∼D (∃y = y, x ∈ N (x, δ))F (x ) y ≥ .9 ≤ 14 75 = 0.18667 . . .

That is, the robust model has ( 9 10 , 14 75 , 8 255 )-separation.

• With probability at least .9 the natural model satisfies Pr (x,y)∼D (∃y = y, x ∈ N (x, δ))F (x ) y ≥ .9 ≥ 247 300 = 0.82333 . . .

That is, the natural model does not have ( 9 10 , q, 8 255 )-separation for q < 247 300 .

End-to-end defense results. We have evaluated 5 non-overlapping batches from the test set (each batch consists of 30 points, thus 150 points in total), where the base model classifies test points in these batches correctly (in other words, we skip test points where the base model predicts incorrectly). We find that the base model is susceptible to CW attack for 56 of them (thus the attack success rate is 37.33%). We find the following after applying CarliniWagnerShell: First, the points that were robust with base model remain robust, thus we do not introduce new vulnerabilities. Second, among the 56 vulnerable points of base model, for 53 of them CarliniWagnerShell now is both correct and robust against attacks on which the base model fails. Finally, for the remaining 3 points: For only one of them, CarliniWagner shell produces wrong prediction but is robust (makes consistent predictions for both vanilla the perturbed points), and for the remaining two CarliniWagn-erShell is both incorrect and not robust. As a summary, the attack success rate reduces from 37.33% to 2/150 = 1.33%, and the accuracy retained is 147/150 = 98%. The results are summarized in Table 2 . Wrong data points, confidence, and the manifold boundary. We now describe the three data points where CarliniWagnerShell fails. We observe that for these three points the model has low confidence, and so by our theory it is expected to be hard to defend. Taking again a manifold point of view, we suspect that one possibility why these points have low confidence is that "natural manifolds" (which are spaces of points generated by some computational devices) are not really well separated. In the following we examine each of these three points.

From the first batch, we have a single point that CarliniWagnerShell gives a wrong prediction, but does not change its prediction after the image is adversarially perturbed (and thus is robust, but not correct). The image is presented in Figure 1 (a). We note that the model gives low confidence (∼ 50%) on the original image. (where the correct label is a "cat"), and it has significantly higher confidence (∼ 75%) on the perturbed image (classified as a "frog"). In this case, Proposition 1 only indicates very weak separation, (indeed, ε) and so it is expected to be hard to defend. Figure 1 depicts the images, with a similar frog image for comparison. We note that these points as generated by some cameras have essentially ignored the "size" information of different objects (can we tell from these images that a cat should be bigger than a frog?), and thus may not be well separated.

From the fourth batch, we have two points that CarlniWagnerShell gives us wrong predictions, and changes its predictions after the images are adversarially perturbed. Figure 2 (a) and 2(f) depict these images and corresponding results. The situation is similar to the first image above where model predictions have low confidence: the base model gives low confidence on the original image (∼ 50% for "automobile" 2(a), and ∼ 60% for "airplane" 2(f)) and adversarially perturbed images (∼ 60% for 2(a), and ∼ 50% for 2(f). Both predictions are "ship"). For each row we attach an image which is a valid "ship" image but resembles "automobile" and "airplane" images in shape. Again, we suspect that the underlying natural manifolds are not well separated as one might expect.

7. DISCUSSION:

We now discuss our method and results. Our technical contributions. Our first technical contribution is the proposal to take into account the inherent confidence information produced by models when studying adversarial perturbations. Our second technical contribution is a formulation of a goodness property of models, and an analysis of existing models in view of the property. Interestingly, and somewhat surprisingly, we find that a recent robust training objective function by Madry et al. (2017) encourages good separation of highconfidence points, but has essentially no control of low-confidence points. Our third contribution is the proposal of embedding to handle low-confidence points. Our final contribution is a first empirical study that validates Madry et al.'s model in terms of the goodness property, and further demonstrates that a good model, when wrapped with embedding, simultaneously achieves good generalization and almost perfect robustness.

Interpretations of our results. One interpretation of our results is that adversarial perturbations can naturally coexist with good generalization. While this is manifested in our analysis of Madry et al.'s objective function, we think that this phenomenon naturally and generally exists if one takes again a manifold point of view: Since natural manifolds reside in low dimensions, it seems much more challenging to control the confidence boundary, where "adversarial perturbations" exist in abundance, than controlling separation of the learned structures (i.e. confident regions that approximate the underlying manifolds).

On the other hand, if all one cares about is robustness (decision does not change in a small neighborhood), then adversarial perturbation problem can be resolved by combining goodness property with embedding. For example, consider the following "good model:" If a data point is from the training set, then it outputs the correct label with confidence 1, otherwise it outputs a uniform distribution over labels. In other words, this model learns nothing but fitting the training set. We note that in this case, the adversarial perturbation problem is only well defined around the training points. Moreover, embedding now becomes 1-nearest neighbor search among the training points. As a result, the model is still perfectly robust with our method if training points are well separated.

Highly confident predictions on random noises. We note that several work shows that neural networks can have highly confident predictions on random noises (e.g., Nguyen et al. (2015) ). In view of our work it is somewhat not surprising that neural networks can have such behaviors: These points are essentially ones that are far away from the "universe" the learner is asked to learn, and so if we do not control the training of neural networks to not claim confidence over the structure it has never seen, then it is valid to fit a model that has good behaviors on natural manifolds but also divergent behaviors outside. After all, why is a network supposed to work on points that are far away from the underlying natural manifolds, which is essentially the data generating distribution? Finally, we note that the adversarial perturbation problem is not well defined even near those points.

:

Let X be a nonnegative random variable and a > 0, Markov's inequality says that Pr[X ≥ a] ≤ E[X]/a.

Figures and Tables:

Figure 1: The point (a) where our CarliniWagnerShell makes a wrong prediction, and is consistent on the original test point and the perturbed one. We show the original image (a), CarliniWagnerShell perturbation of the image (b), and for comparison, a frog image (c) that the model is confident about.

Definition 9 (Search Factor). A search factor H is an algorithm that takes as its input a model F , and a point x ∈ R d to classify, and output another point x ∈ R d . If F is chosen and fixed apriori we say that F is the base model of the search factor H, and denoteH(F, •) as H[F ].Definition 10 (Factor Model Shell). A model shell G is said to be a factor model shell if G can be written as a composition of F • H where H is a search factor. In other words, G(F, x) works as

Table content: <table/>

Table 1 summarizes the results.

Table content: <table><tr><td/><td colspan="2"># successful attacks</td></tr><tr><td/><td colspan="2">Robust model Natural model</td></tr><tr><td>Batch #1</td><td>2</td><td>26</td></tr><tr><td>Batch #2</td><td>3</td><td>27</td></tr><tr><td>Batch #3</td><td>4</td><td>26</td></tr><tr><td>Batch #4</td><td>5</td><td>28</td></tr><tr><td>Batch #5</td><td>2</td><td>29</td></tr><tr><td>Batch #6</td><td>4</td><td>25</td></tr><tr><td>Batch #7</td><td>0</td><td>28</td></tr><tr><td>Batch #8</td><td>2</td><td>30</td></tr><tr><td>Batch #9</td><td>3</td><td>28</td></tr><tr><td>Batch #10</td><td>1</td><td>30</td></tr><tr><td>Total</td><td>26</td><td>277</td></tr><tr><td>Table</td><td/><td/></tr></table>

Summary of the experimental results. Among the 150 test points where the base model is correct. For 56 of them the base model is vulnerable to CW attacks. Applying CarliniWagnerShell does not introduce new vulnerable points. And for 53 of the 56 vulnerable points, CarliniWagner-Shell is both correct and robust against the attacks that are successful on the base model. For one of the remaining three points, CarliniWagnerShell is incorrect but robust. For the remaining two CarliniWagnerShell is both incorrect and not robust.

Table content: <table><tr><td/><td>Base model</td><td colspan="2">CarliniWagnerShell-equipped model</td></tr><tr><td/><td colspan="3">Attack success rate Attack success rate Retained accuracy</td></tr><tr><td>Batch #1</td><td>30 %</td><td>0 %</td><td>96.67 %</td></tr><tr><td>Batch #2</td><td>33.33 %</td><td>0 %</td><td>100 %</td></tr><tr><td>Batch #3</td><td>40 %</td><td>0 %</td><td>100 %</td></tr><tr><td>Batch #4</td><td>33.33 %</td><td>0.07 %</td><td>99.33 %</td></tr><tr><td>Batch #5</td><td>46.67 %</td><td>0 %</td><td>100 %</td></tr><tr><td>Average</td><td>37.33 %</td><td>1.33 %</td><td>98 %</td></tr></table>

Peer review (iclr2018):
 The authors argue that "good" classifiers naturally represent the classes in a classification as well-separated manifolds, and that adversarial examples are low-confidence examples lying near to one of these manifolds. The authors suggest "fixing" adversarial examples by projecting them back to the manifold, essentially by finding a point near the adversarial example that has high confidence. There are numerous issues here, which taken together, make the whole story pretty unconvincing. The term "manifold" is used very sloppily. To be fair, this is unfortunately common in modern machine learning. An actual manifold is a specific mathematical structure with specific properties. In ML, what is generally hypothesized is that the data (often per class) lives "near" to some "low-dimensional" structure. In this paper, even the low-dimensionality isn*t used --- the "manifold assumption" is used as a stand-in for "the regions associated with different classes are well-separated." (This is partially discussed in Section 6, where the authors point out correctly that the same defense as used here could be used with a 1-nn model.) This is fine as far as it goes, but the paper refs Basri & Jacobs 2016 multiple times as if it says anything relevant about this paper: Basri & Jacobs is specifically about the ability of deep nets to fit data that falls on (actual, mathematical) manifolds. This reference doesn*t add much to the present story. The essential argument of the paper rests on the "Postulate: (A good model) F is confident on natural points drawn from the manifolds, but has low confidence on points outside of the manifolds." This postulate is sloppy and speculative. For instance, taken in its strong form, if believe the postulate, then a good model: 1. Can classify all "natural points" from all classes with 100% accuracy. 2. Can detect adversarial points with 100% accuracy because all high-confidence points are correct classifications and all low-confidence points are adversarial. 3. All adversarial examples will be low-confidence. Point 1 makes it clear that no good model F fully satisfying the postulate exists --- models never achieve 100% accuracy on difficult real-world distributions. But the method for dealing with adversarial examples seems to require Points 2 and 3 being true. To be fair, the paper more-or-less admits that how true these points are is not known and is important. Nevertheless, I think this paper comes pretty close to arguing something that I *think* is not true, and doesn*t do much to back up its argument. Because of the quality of the writing (generally sloppy), it*s hard to tell, but I believe the authors are basically arguing that: a. You can generally easily detect adversarial points because they are low confidence. b. If you go through a procedure to find a point near your adversarial point that is high-confidence, you*ll get the "correct" (or perhaps "original") class back. I think b follows from a, but a is extremely suspect. I do not personally work in adversarial examples, and briefly looking at the literature, it seems that most authors *do* focus on how something is classified and not its confidence, but I don*t think it*s *that* hard to generate high-confidence adversarial examples. Early work by Goodfellow et al. ("Explaining and Harnessing Adversarial Examples", Figure 1, shows an example where the incorrect classification has very high confidence. The present paper only uses Carlini-Wagner attacks. From a read of Carlini-Wagner, it seems they are heavily concerned with finding *minimal* perturbations to achieve a given misclassification; this will of course produce low-confidence adversaries, but I see no reason why this is a general property of all adversarial examples. The experiments are weak. I applaud the authors for mentioning the experiments are very preliminary, but that doesn*t make them any less weak. What are we to make of the one image discussed at the end of Section 5 and shown in Figure 1? The authors note that the original image gives low-confidence for the correct class. (Does this mean that the classifier isn*t "good"? Is it evidence against some kind of manifold assumption?) The authors note the adversarial category has significantly higher confidence, and say "in this case, it seems that it is the vagueness of the signals/data that lead to a natural difficulty." But the signals and data are ALWAYS vague. If they weren*t, machine learning would be easy. This paper proposes something, looks at a tiny number of examples, and already finds a counterexample to the theory. What*s the evidence *for* the theory? A lot of writing is given over to how this method is "semantic", and I just don*t buy it. The connection to manifolds is weak. The basic argument here is really "(1) If our classifiers produce smooth well-separated high-confidence regions, (2) then we can detect adversaries because they*re low-confidence, and (3) we can correct adversaries by projecting them back to high-confidence." (1) seems vastly unlikely to me based on all my experience: neural nets often get things wrong, they often get things wrong with high confidence, and when they*re right, the confidence is at least sometimes low. The authors use a sloppy postulate about good models and so could perhaps argue I*ve never seen a good model, but the methods of this paper require a good model. (2) seems to follow logically from (1). (3) is also suspect --- perturbations which are *minimal* can be corrected as this paper does (and Carlini-Wagner attacks are minimal by design), but there*s no reason to expect general perturbations to be minimal. The writing is poor throughout. It*s generally readable, but the wordings are often odd, and sometimes so odd it*s hard to tell what was meant. For instance, I spent awhile trying to decide whether the authors assumed common classifiers are "good" (according to the postulate) or whether this paper was about a way to *make* classifiers good (I eventually decided the former).