Title: AN EFFICIENT AND MARGIN-APPROACHING ZERO-CONFIDENCE ADVERSARIAL ATTACK Anonymous

Abstract: There are two major paradigms of white-box adversarial attacks that attempt to impose input perturbations. The first paradigm, called the fix-perturbation attack, crafts adversarial samples within a given perturbation level. The second paradigm, called the zero-confidence attack, finds the smallest perturbation needed to cause misclassification, also known as the margin of an input feature. While the former paradigm is well-resolved, the latter is not. Existing zero-confidence attacks either introduce significant approximation errors, or are too time-consuming. We therefore propose MARGINATTACK, a zero-confidence attack framework that is able to compute the margin with improved accuracy and efficiency. Our experiments show that MARGINATTACK is able to compute a smaller margin than the state-ofthe-art zero-confidence attacks, and matches the state-of-the-art fix-perturbation attacks. In addition, it runs significantly faster than the Carlini-Wagner attack, currently the most accurate zero-confidence attack algorithm.

1. INTRODUCTION:

Adversarial attack refers to the task of finding small and imperceptible input transformations that cause a neural network classifier to misclassify. White-box attacks are a subset of attacks that have access to gradient information of the target network. In this paper, we will focus on the white-box attacks. An important class of input transformations is adding small perturbations to the input. There are two major paradigms of adversarial attacks that attempt to impose input perturbations. The first paradigm, called the fix-perturbation attack, tries to find perturbations that are most likely to cause misclassification, with the constraint that the norm of the perturbations cannot exceed a given level. Since the perturbation level is fixed, fix-perturbation attacks may fail to find any adversarial samples for inputs that are far away from the decision boundary. The second paradigm, called the zero-confidence attack, tries to find the smallest perturbations that are guaranteed to cause misclassification, regardless of how large the perturbations are. Since they aim to minimize the perturbation norm, zero-confidence attacks usually find adversarial samples that ride right on the decision boundaries, and hence the name "zero-confidence". The resulting perturbation norm is also known as the margin of an input feature to the decision boundary. Both of these paradigms are essentially constrained optimization problems. The former has a simple convex constraint (perturbation norm), but a non-convex target (classification loss or logit differences). In contrast, the latter has a non-convex constraint (classification loss or logit differences), but a simple convex target (perturbation norm).

Despite their similarity as optimization problems, the two paradigms differ significantly in terms of difficulty. The fix-perturbation attack problem is easier. The state-of-the-art algorithms, including projected gradient descent (PGD) (Madry et al., 2017) and distributional adversarial attack (Zheng et al., 2018) , can achieve both high efficiency and high success rate, and often come with theoretical convergence guarantee. On the other hand, the zero-confidence attack problem is much more challenging. Existing methods are either not strong enough or too slow. For example, DeepFool (Moosavi Dezfooli et al., 2016) and fast gradient sign method (FGSM) (Goodfellow et al., 2014; Kurakin et al., 2016a; b) linearizes the constraint, and solves the simplified optimization problem with a simple convex target and a linear constraint. However, due to the linearization approximation errors, the solution can be far from optimal. As another extreme, L-BFGS (Szegedy et al., 2013) and Carlini-Wagner (CW) (Carlini & Wagner, 2017) convert the optimization problem into a Lagrangian, and the Lagrangian multiplier is determined through grid search or binary search. These attacks are generally much stronger and theoretically grounded, but can be very slow.

The necessity of developing a better zero-confidence attack is evident. The zero-confidence attack paradigm is a more realistic attack setting. More importantly, it aims to measure the margin of each individual token, which lends more insight into the data distribution and adversarial robustness. Motivated by this, we propose MARGINATTACK, a zero-confidence attack framework that is able to compute the margin with improved accuracy and efficiency. Specifically, MARGINATTACK iterates between two moves. The first move, called restoration move, linearizes the constraint and solves the simplified optimization problem, just like DeepFool and FGSM; the second move, called projection move, explores even smaller perturbations without changing the constraint values significantly. By construction, MARGINATTACK inherits the efficiency in DeepFool and FGSM, and improves over them in terms of accuracy with a convergence guarantee. Our experiments show that MARGINAT-TACK attack is able to compute a smaller margin than the state-of-the-art zero-confidence attacks, and matches the state-of-the-art fix-perturbation attacks. In addition, it runs significantly faster than CW, and in some cases comparable to DeepFool and FGSM.

2. RELATED WORKS:

In addition to the aforementioned state-of-the-art attacks, there are a couple of other works that attempt to explore the margin. Jacobian-based saliency map attack (Papernot et al., 2016) is among the earliest works that apply gradient information to guide the crafting of adversarial examples. It chooses to perturb the input features whose gradient is consistent with the adversarial goal. Onepixel attack (Su et al., 2017) finds adversarial examples by perturbing only one pixel, which can be regarded as finding the 0 margin of the inputs. Ilyas et al. (2018) converts PGD into a zeroconfidence attack by searching different perturbation levels, but this again can be time-consuming because it needs to solve multiple optimization subproblems. Weng et al. proposed a metric called CLEVER (Weng et al., 2018) , which estimates an upper-bound of the margins. Unfortunately, recent work (Goodfellow, 2018) has shown that CLEVER can overestimate the margins due to gradient masking (Papernot et al., 2017) . The above are a just a small subset of white-box attack algorithms that are relevant to our work. For an overview of the field, we refer readers to Akhtar & Mian (2018) .

The MARGINATTACK framework is inspired by the Rosen's algorithm (Rosen, 1961) for constraint optimization problems. However, there are several important distinctions. First, the Rosen's algorithm rests on some unrealistic assumptions for neural networks, e.g. continuously differentiable constraints, while MARGINATTACK has a convergence guarantee with a more realistic set of assumptions. Second, the Rosen's algorithm requires a step size search for each iteration, which can be time-consuming, whereas MARGINATTACK will work with a simple diminishing step size scheme. Most importantly, as will be shown later, MARGINATTACK refers to a large class of attack algorithms depending on how the two parameters, a (k) and b (k) , are set, and the Rosen's algorithm only fits into one of the settings, which only works well under the 2 norm. For other norms, there exist other parameter settings that are much more effective. As another highlight, the convergence guarantee of MARGINATTACK holds for all the settings that satisfy some moderate assumptions.

3. THE MARGINATTACK ALGORITHM:

In this section, we will formally introduce the algorithm and discuss its convergence properties. In the paper, we will denote scalars with non-bolded letters, e.g. a or A; column vectors with lowercased, bolded letters, e.g. a; matrix with upper-cased, bolded letters, e.g. A; sets with upper-cased double-stoke letters, e.g. A; gradient of a function f (x) evaluated at x = x 0 as ∇f (x 0 ).

3.1. PROBLEM FORMULATION:

Given a classifier whose output logits are denoted as l 0 (x), l 1 (x), • • • , l C-1 (x), where C is the total number of classes, for any data token (x 0 , t), where x 0 is an n-dimensional input feature vector, and t ∈ {0, • • • , C -1} is its label, MARGINATTACK computes

EQUATION

where d(•) is a norm. In this paper we only consider 2 and ∞ norms, but the proposed method is generalizable to other norms. For non-targeted adversarial attacks, the constraint is defined as

EQUATION

)

where ε is the offset parameter. As a common practice, ε is often set to a small negative number to ensure that the adversarial sample lies on the incorrect side of the decision boundary. In this paper, we will only consider non-targeted attack, but all the discussions are applicable to targeted attacks (i.e. c(x) = max i =a l i (x) -l a (x) -ε for a target class a).

3.2. THE MARGINATTACK PROCEDURE:

MARGINATTACK alternately performs the restoration move and the projection move. Specifically, denote the solution after the k-th iteration as x (k) . Then the two steps are:

Restoration Move: The restoration move tries to hop to the constraint boundary, i.e. c(x) = 0 with the shortest hop. Formally, it solves:

EQUATION

where α (k) is the step size within [0, 1]. Notice that the left hand side of the constraint in Eq. ( 3) is the first-order Taylor approximation of c(z (k) ) -c(x (k) ), so this constraint tries to move point closer to c(x) = 0 by α (k) . It can be shown, from the dual-norm theory,1 that the solution to (3) is

z (k) = x (k) - α (k) c(x (k) )s(x (k) ) ∇ T c(x (k) )s(x (k) ) (4) s(x) is defined such that ∇ T c(x)s(x) = d * (∇ T c(x))

, where d * (•) is the dual norm of d(•). Specifically, noticing that the dual norm of the p norm is the (1-p -1 ) -1 norm, we have

EQUATION

As mentioned, Eq. ( 4) is similar to DeepFool under 2 norm, and to FGSM under ∞ norm. Therefore, we can expect that the restoration move should effectively hop towards the decision boundary, but the hop direction may not be optimal. That is why we need the next move.

Projection Move: The projection move tries to move closer to x 0 while ensuring that c(x) will not change drastically. Formally,

EQUATION

where β (k) is the step size within [0, 1]; a (k) and b (k) are two scalars, which will be specified later. As an intuitive explanation on Eq. ( 3), notice that the second term, which we will call the distance reduction term, reduces the distance to x 0 , whereas the third term, which we will call the constraint reduction term, reduces the the constraint (because s(z (k) ) and ∇c(z (k) ) has a positive inner product). Therefore, the projection move essentially strikes a balance between reduction in distance and reduction in constraint.

a (k) and b (k) can have two designs. The first design is to ensure the constraint values are roughly the same after the move, i.e. c(z (k) ) -c(x (k+1) ) ≈ 0. By Taylor approximation, we have

EQUATION

whose solution is

EQUATION

)

Another design is to ensure the perturbation norm reduces roughly by

β (k) , i.e. d(x (k+1) -x 0 ) ≈ (1 -β (k) )d(z (k) -x 0 )

. By Taylor approximation, we have

EQUATION

whose solution is

EQUATION

It should be noted that Eqs. ( 8) and ( 10) are just two specific choices for a (k) and b (k) . It turns out that MARGINATTACK will work with a convergence guarantee for a wide range of bounded a (k) s and b (k) s that satisfy some conditions, as will be shown in section 3.4. Therefore, MARGINAT-TACK provides a general and flexible framework for zero-confidence adversarial attack designs. In practice, we find that Eq. ( 8) works better for 2 norm, and Eq. ( 8) works better for ∞ norm.

3.3. HOW MARGINATTACK WORKS:

Figure 1 illustrates a typical convergence path of MARGINATTACK using 2 norm and Eq. ( 8) as an example. The red dots on the right denote the original inputs x 0 and its closest point on the decision boundary, x * . Suppose after iteration k, MARGINATTACK reaches x (k) , denoted by the green dot on the left. The restoration move travels directly towards the decision boundary by finding the normal direction to the current constraint contour. Then, the projection move travels along the tangent plane of the current constraint contour to reduce the distance to x 0 while preventing the constraint value from deviating much. As intuitively expected, the iteration should eventually approach x * . Figure 2 plots an empirical convergence curve of the perturbation norm and constraint value of MARGINATTACK-2 on a randomly chosen CIFAR image. Each move from a triangle to a circle dot is a restoration move, and from circle to triangle a projection move. The red line is the smoothed version. As can be seen, a restoration move reduces the constraint value while slightly increasing the constraint norm, and a projection move reduces the perturbation norm while slightly affecting the constraint value. Both curves can eventually converge.

3.4. THE CONVERGENCE GUARANTEE:

The constraint function c(x) in Eq. ( 2) is nonconvex, thus the convergence analysis for MARGINAT-TACK is limited to the vicinity of a unique local optimum, as stated in the following theorem. Theorem 1. Denote x * as one local optimum for Eq. (1). Assume ∇c(x * ) exists. Define projection matrices

EQUATION

Consider the neighborhood

B = {x : P [x -x * ] 2 2 ≤ X, |c(x)

| ≤ C} that satisfies the following assumptions:

1. (Differentiability) ∀x ∈ B, ∇c(x) exists, but can be discontinuous, i.e. all the discontinuity points of the gradient in B are jump discontinuities;

2. (Lipschitz Continuity at x * ) ∀x ∈ B, s(x) -s(x * ) 2 ≤ L s s(x * ) 2 x -x * 2 ; 3. (Bounded Gradient Norm) ∀x ∈ B, 0 < m ≤ ∇c(x) 2 ≤ M ;

4. (Bounded Gradient Difference) ∃δ > 0, ∀x, y ∈ B s.t. yx = ls(x) for some l,

∇ T c(y)s(x) ≥ δ∇ T c(x)s(x); 5. (Constraint Convexity) ∃γ ∈ (0, 1), ∀x ∈ B, (a (k) ∇d(x -x0) + b (k) s(x)) T P T P (x -x0) ≥ γ(x -x0) T P T P (x -x0);

6. (Unique Optimality) x * is the only global optimum within B;

7. (Constant Bounded Restoration Step Size) α (k) = α < M α ; 2 8. (Shrinking Projected Step Size) β (k) < β/(k + k 0 ) ν , where 0 < ν < 1 and β ≤ M β , k 0 > m k ; 3 |a (k) | < M a , |b (k) | < M b ; 9. (Presence in Neighborhood) ∃K, x (K) ∈ int[B], i.e. the interior of B.

Then we have the convergence guarantee lim k→∞ x (k) -x * 2 = 0.

The proof will be presented in the appendix. Here are a few remarks. First, assumption 1 allows jump discontinuities in ∇c(x) almost everywhere, which is a very practical assumption for deep neural networks. Most neural network operations, such as ReLU and max-pooling, as well as the max operation in Eq. ( 2), introduce nothing beyond jump discontinuities in gradient.

Second, assumption 3 does require the constraint gradient to be lower bounded, which may lead to concerns that MARGINATTACK may fail in the presence of gradient masking (Papernot et al., 2017) . However, notice that the gradient boundedness assumption is only imposed in B, which is in the vicinity of the decision boundary, whereas gradient masking is most likely to appear away from the decision boundary and where the input features are populated. Besides, as will be discussed later, a random initialization as in PGD will be adopted to bypass regions with gradient masking. Experiments on adversarially trained models also verify the robustness of MARGINATTACK.

Finally, assumption 5 essentially stipulates that c(x) is convex or "not too concave" in B (and thus so is the constraint set c(x) ≤ 0), so that the first order optimality condition can readily imply local minimum instead of a local maximum. In fact, it can be shown that assumption 5 can be implied if c(x) is convex in B.4 

3.5. ADDITIONAL IMPLEMENTATION DETAILS:

There are a few additional implementation details as outlined below.

Box Constraint: In many applications, each dimension of the input features should be bounded, i.e. x ∈ [x min , x max ] n . To impose the box constraint, the restoration move problem as in Eq. ( 3) is modified as

EQUATION

)

whose solution is

z (k) = Proj [x min ,xmax] n { z(k) }, where z(k) = x (k) - α (k) c(x (k) ) + i∈I C ∇ic(x (k) )(z (k) i -x (k) i ) i∈I ∇ic(x (k) )si(x (k) ) s(x (k) ).

(13) Proj(•) is an operator that projects the vector in its argument onto the subset in its subscript. I is a set of indices with which the elements in z(k) satisfy the box constraint, and I C is its complement. I is determined by running Eq. ( 13) iteratively and updating I after each iterations.

Unlike other attack algorithms that simply project the solution onto the constraint box, MARGINAT-TACK incorporates the box constraint in a principled way, such that any local optimal solution x * will be an invariant point of the restoration move. Thus the convergence is faster.

Target Scan: According to Eq. ( 2), each restoration move essentially approaches the adversarial class with the highest logit, but the class with the highest logit may not be the closest. To mitigate the problem, we follow a similar approach adopted in DeepFool, which we call target scan. Target scan performs a target-specific restoration move towards each class, and chooses the move with the shortest distance. Formally, target scan introduces a set of target-specific constraints {c i (x) = l t (x) -l i (x) -ε}. A restoration move with target scan solves

EQUATION

where z (k,i) is the solution to Eqs. ( 3) or ( 12) with c(x (k) ) replaced with c i (x (k) ), and thus is equal to Eqs. ( 4) or (13) with c(x (k) ) replaced with c i (x (k) ). A is a set of candidate adversarial calsses, which can be all the incorrect classes if the number of classes is small, or which can be a subset of the adversarial classes with the highest logits otherwise. Experiments show that target scan is necessary only in the first few restoration moves, when the closest and highest adversarial classes are likely to be distinct. Therefore, the computation cost will not increase too much.

Initialization: The initialization of x (0) can be either deterministic or random as follows

EQUATION

where U{[-u, u] n } denotes the uniform random distribution in [-u, u] n . Similar to PGD, we can perform multiple trials with random initialization to find a better local optimum.

Final Tuning MARGINATTACK can only cause misclassification when c(x) ≤ ε. To make sure the attack is successful, the final iterations of MARGINATTACK consists of restoration moves only, 

Algorithm 1: MARGINATTACK Procedure:

Input : A set of logit functions l0:C-1(x); an input feature x0 and its label t; Output: A solution x * to Eq. (1) Initialize x (0) according to Eq. ( 15); for k < number of iterations do if k < number of target scan iterations then Do target scan restoration move as in Eq. ( 14); else Do regular restoration move as in Eqs.

(3) or ( 12); end if k < final tuning iteration then Do projection move as in Eqs. ( 6); else Skip projection move:

x (k+1) = z (k) ; end end x * = x (k) .

and no projection moves, until a misclassification is caused. This can also ensure the final solution satisfies the box constraint (because only the restoration move incorporates the box constraint). Summary: Alg. 1 summarizes the MARGINATTACK procedure. As for the complexity, each restoration move or projection move requires only one backward propagation, and thus the computational complexity of each move is comparable to one iteration of most attack algorithms.

4. EXPERIMENTS:

This section compares MARGINATTACK with several state-of-the-art adversarial attack algorithms in terms of the perturbation norm and computation time on image classification benchmarks.

4.1. ATTACKING REGULAR MODELS:



4.1.1. CONFIGURATIONS:

Three regularly trained models are evaluated on.

• MNIST (LeCun et al., 1998): The classifier is a stack of two 5 × 5 convolutional layers with 32 and 64 filters respectively, followed by two fully-connected layers with 1,024 hidden units. • CIFAR10 (Krizhevsky & Hinton, 2009) : The classifier is a pre-trained ResNet32 (He et al., 2016) provided by TensorFlow.5 . • ImageNet (Russakovsky et al., 2015) : The classifier is a pre-trained ResNet50 (He et al., 2016) provided by TensorFlow Keras6 . Evaluation is on a validation subset containing 10,000 images.

The range of each pixel is [0, 1] for MNIST, and [0, 255] for CIFAR10 and ImageNet. The settings of MARGINATTACK and baselines are listed below. Unless stated otherwise, the baseline algorithms are implemented by cleverhans (Nicolas Papernot, 2017). The hyperparameters are set to defaults if not specifically stated.

• CW (Carlini & Wagner, 2017) : The target and evaluation norm is 2 . The learning rate is set to 0.05 for MNIST, 0.001 for CIFAR10 and 0.01 for ImageNet, which are tuned to its best performance. The number of binary steps for multiplier search is 10. • DeepFool (Moosavi Dezfooli et al., 2016) : The evaluation norm is 2 .

• FGSM (Goodfellow et al., 2014) : FGSM is implemented by authors. The step size is searched to achieve zero-confidence attack. The evaluation distance metric is ∞ . • PGD (Madry et al., 2017) : The target and evaluation norm are ∞ . The learning rate is set to 0.01 for MNIST, and 0.05 for CIFAR10 and 0.1 for ImageNet. • MARGINATTACK: Two versions of MARGINATTACK are implemented, whose target and evaluation norms are 2 , and ∞ , respectively. The hyperparmeters are detailed in Table 4 in the appendix. The first 10 restoration moves are with target scan, and the last 20 moves are all restoration moves.

The number of iterations/moves is set to 2,000 for CW, 200 with 10 random starts for PGD and MARGINATTACK (except for ImageNet where there is only one random run), and 200 for the rest.

4.1.2. RESULTS AND ANALYSES:

Except for PGD, all the other attacks are zero-confidence attacks. For these attacks, we plot the CDF of the margins of the validation data, which can also be interpreted as the percentage success rate of these attacks as a function of perturbation level. Figure 3 plots the success rate curves, where the upper panel shows the 2 attacks, and the lower one shows ∞ attacks. As can be observed, the MARGINATTACK curves are above all other algorithms at all perturbation levels and in all datasets. CW is very close to MARGINATTACK on MNIST and CIFAR10, but MARGINATTACK maintains a 3% advantage on MNIST and 1% on CIFAR10. It seems that CW is unable to converge well within 2,000 iterations on ImageNet, although the learning rate has been tuned to maximize its performance. MARGINATTACK, on the other hand, converges more efficiently and consistently.

To obtain a success rate curve for PGD, we have to run the attack again and again for many different perturbation levels, which can be time-consuming for large datasets (this shows an advantage of zero-confidence attacks over fix-perturbation attacks). Instead, we choose four perturbation levels for each attack scenario to compare. The perturbation levels are chosen to roughly follow the 0.2, 0.4, 0.6 and 0.8 quantiles of the MARGINATTACK margins. Table 1 compares the success rates under the chosen quantiles among the ∞ attacks. We can see that MARGINATTACK outperforms PGD under all the perturbation levels, and that both significantly dominate FGSM.

4.2. ATTACKING ADVERSARIALLY TRAINED MODEL:

We also evaluate MARGINATTACK on the MNIST Adversarial Examples Challenge7 , which is a challenge of attacking an MNIST model adversarially trained using PGD with 0.3 perturbation level. Same as the PGD baseline listed, MARGINATTACK is run with 50 random starts, and the initialization perturbation range u = 0.3. The number of moves is 500. The target norm is ∞ . b n = 5 and a n is set as in Eq. ( 10). The rest of the configuration is the same as in the previous experiments.

Table 2 lists the success rates of different attacks under 0.3 perturbation level. The baseline algorithms are all fix-perturbation attacks, and their results are excerpted from the challenge white-box attack leaderboard. As can be seen, MARGINATTACK, as the only zero-confidence attack algorithm, has the second best result, which shows that it performs competitively against the state-of-the-art fix-perturbation attacks.

4.3. CONVERGENCE:

We would like to revisit the convergence plot of the constraint value c(x) and perturbation norm d(x) of as in Fig. 2 . We can see that MARGINATTACK converges very quickly. In the example shown in the figure, it is able to converge within 20 moves. Therefore, MARGINATTACK can be greatly accelerated. If margin accuracy is the priority, a large number of moves, e.g. 200 as in our experiment, would help. However, if efficiency is the priory, a small number of moves, e.g. 30, suffices to produce a decent attack.

To further assess the efficiency of MARGINATTACK, Tab. 3 compares the running time (in seconds) of attacking one batch of images, implemented on a single NVIDIA TESLA P100 GPU. The batch size is 200 for MNIST and CIFAR10, and 100 for ImageNet. The settings are the same as stated in section 4.1, except that for a better comparison, the number of iterations of CW is cut down to 200, and PGD and MARGINATTACK runs one random pass, so that all the algorithms have the same iteration/moves. This supplementary material aims to prove Thm. 1. Without the loss of generality, K in Eq. ( 9) in set to 0. Before we prove the theorem, we need to introduce some lemmas. Lemma 1.1. If assumption 3 in Thm. 1 holds, then ∀x ∈ B

EQUATION

Proof. According to Eq. ( 5), for 2 norm,

EQUATION

)

Lemma 1.2. Given all the assumptions in Thm. 1, where

EQUATION

EQUATION

and assuming x (k) , z (k) ∈ B, ∀k, then we have

EQUATION

where

EQUATION

A and B are defined in Eq. (32).

According to assumption 8, this implies

lim k→∞ |c(x (k) )| = 0 (23)

at the rate of at least 1/n ν .

Proof. As a digression, the second term in Eq. ( 19) is well defined, because

∇ T c(y)s(x) ∇ T c(x)s(x)

is upper bounded by Lem. 1.1 and assumptions 3.

Back to proving the lemma, we will prove that each restoration move will bring c(x (k) ) closer to 0, while each projection move will not change c(x (k) ) much.

First, for the restoration move

EQUATION

The first line is from the generalization of Mean-Value Theorem with jump discontinuities, and ξ = tz (k) + (1 -t)x (k) and t is a real number in [0, 1]. The second line is from Eq. ( 4). The last line is from assumptions 4 and 7 and Eq. ( 19).

Next, for the projection move

EQUATION

The first line is from the fact that assumption 3 implies that c(x) is M -Lipschitz continuous.

Both ∇d(z (k) -x 0 ) 2 and s(z (k) ) 2 is upper-bounded, i.e.

EQUATION

for some M d and M s . To see this, for 2 norm

EQUATION

)

where b is defined as the maximum perturbation norm ( 2 ) within B, i.e.

EQUATION

which is well defined because B is a tight set. For ∞ norm,

EQUATION

Note that Eq. ( 26) also holds for other norms. With Eq. ( 26) and assumption 8, Eq. ( 25) becomes

EQUATION

Combining Eqs. ( 24) and (30) we have

EQUATION

where

EQUATION

According to assumption 7, 0 < A < 1. Also, according to Eq. ( 20), β (k) /β (k+1) ≤ A -1/2 , ∀k, Divide Eq (31) by β (k) , we have

EQUATION

Otherwise, Eq. (34) implies

EQUATION

This concludes the proof.

Lemma 1.3. Given all the assumptions in Thm. 1, and assuming x (k) , z (k) ∈ B, ∀k, we have

EQUATION

Proof. First, for restoration move

P [z (k) -x 0 ] 2 2 = P [x (k) -x 0 ] 2 2 + 2[z (k) -x 0 ] T P T P [z (k) -x (k) ] -P [z (k) -x (k) ] 2 2 ≤ P [x (k) -x 0 ] 2 2 + 2 P [z (k) -x 0 ] 2 P [z (k) -x (k) ] 2 = P [x (k) -x 0 ] 2 2 + 2α P [z (k) -x 0 ] 2 c(x (k) ) ∇ T c(x (k) )s(x (k) ) P s(x (k) ) 2 = P [x (k) -x 0 ] 2 2 + 2α P [z (k) -x 0 ] 2 c(x (k) ) ∇ T c(x (k) )s(x (k) ) P [s(x (k) ) -s(x * )] 2 = P [x (k) -x 0 ] 2 2 + 2α P [z (k) -x 0 ] 2 c(x (k) )∇ T c(x * )(s(x (k) ) -s(x * )) ∇ T c(x (k) )s(x (k) )∇ T c(x * )s(x * ) s(x * ) 2 ≤ P [x (k) -x 0 ] 2 2 + 2αn|c(x (k) )| m P [z (k) -x 0 ] 2 s(x (k) ) -s(x * ) 2 s(x (k) ) 2 ≤ P [x (k) -x 0 ] 2 2 + 2αnL s κβ (k) m P [z (k) -x 0 ] 2 x (k) -x * 2 ≤ P [x (k) -x 0 ] 2 2 + 2αnL s κβ (k) m P [z (k) -x 0 ] 2 P [x (k) -x 0 ] 2 + c(x (k) ) + M P [x (k) -x 0 ] 2 δm/ √ n ≤ P [x (k) -x 0 ] 2 2 + 2αnL s κβ (k) (m + M √ n) δm 2 P [z (k) -x 0 ] 2 P [x (k) -x 0 ] 2 + 2α √ nL s κ 2 β (k)2

δm 2 (38) Line 4 is given by Eq. (3). Line 5 is derived from Lem. 1.1. The last line is from Lem. 1.2.

Eq. ( 38) implies Therefore

P [z (k) -x 0 ] 2 -r (k) 1 P [x (k) -x 0 ] 2 ≥ r (0)2 1 4 ( P [z (k) -x 0 ] 2 + r (k) 2 P [x (k) -x 0 ] 2 ) (42)

Combining Eqs. ( 39) and (42), we have

P [z (k) -x 0 ] 2 2 ≤ r (k)2 2 P [x (k) -x 0 ] 2 2 + 8α √ nL s κ 2 β (k)2 δm 2 r (0)2 1 < 1 + 2αnL s κβ (k) m 2 P [x (k) -x 0 ] 2 2 + 8α √ nL s κ 2 β (k)2 δm 2 r (0)2 1 (43)

Under review as a conference paper at ICLR 2019 Next, for projection move

EQUATION

The second equality is from Eq. ( 6). The last line is from assumption 5 and Eq. ( 31).

Next, combining Eqs. ( 43) and ( 44), we have

EQUATION

According to assumption 8, lim k→∞ β (k) = 0. Thus, ∀ > 0, ∃K( ), ∀k > K( ), we have β (k) ≤ 2γε/D. Therefore 

EQUATION

EQUATION

i.e. x (k) , z (k) ∈ B, ∀k.

Proof. We will prove it by mathematical induction.

Base Case: From assumption 9, we have |c(x (0) )| ≤ C and P [x (0) -x 0 ] 2 2 ≤ X. Thus Eqs. ( 24) and ( 43) hold for k = 0. From Eq. ( 24) and assumption 7, we have |c(z (0) )| ≤ |c(x (0) )| ≤ C. From Eqs. ( 43) and (50), we have P [z (0) -x 0 ] 2 2 ≤ X.

:

See Thm.

in the appendix for a detailed proof.

See Eq. (19) for the definition of Mα in the appendix.

See Eqs. (50) and (20) for the definitions of M β and m k in the appendix.

See Thm. 3 in the appendix.

https://github.com/tensorflow/models/tree/master/official

https://www.tensorflow.org/api_docs/python/tf/keras/applications/ ResNet50

https://github.com/MadryLab/mnist_challenge

Figures and Tables:

Figure 1: A convergence path of MARGINATTACK.

Figure 2: An empirical convergence curve of perturbation norm (left) and constraint value (right).

Figure 3: Adversarial attacks on (left) MNIST, (middle) Cifar, and (right) ImageNet dataset.

P [z (k) -x 0 ] 2 -r (k) 1 P [x (k) -x 0 ] 2 )( P [z (k) -x 0 ] 2 -r

holds ∀ > 0. This concludes the proof. Lemma 1.4. Given all the assumptions in Thm. 1, where M α and m k defined in Eqs. (19) and (20where A, B, D and E are defined in Eqs. (32) and (46), the following inequalities hold ∀k. |c(x (k) )| ≤ C |c(z (k) )| ≤ C P

Success rate (%) of adversarial attacks under given perturbation norms.

Table content: <table><tr><td>Algorithm</td><td>MNIST</td><td>CIFAR</td><td>IMAGENET</td></tr><tr><td/><td>0.06 / 0.08 / 0.10 / 0.12</td><td>0.2 / 0.4 / 0.6 / 1</td><td>0.05 / 0.1 / 0.2 / 0.4</td></tr><tr><td>FGSM</td><td colspan="3">7.55 / 13.9 / 24.9 / 35.4 18.5 / 31.0 / 41.1 / 54.7 39.8 / 47.2 / 60.1 / 75.3</td></tr><tr><td>PGD</td><td colspan="3">17.1 / 42.2 / 73.7 / 91.8 18.9 / 38.9 / 59.1 / 84.1 40.4 / 49.8 / 68.8 / 90.6</td></tr><tr><td>Ours</td><td colspan="3">18.1 / 43.0 / 74.1 / 92.1 21.1 / 42.2 / 62.6 / 87.3 41.5 / 51.3 / 69.0 / 90.8</td></tr></table>

Success rate under 0.3 perturbation norm of the MNIST Adversarial Examples Challenge.

Table content: <table><tr><td/><td/><td colspan="4">Table 3: Running time comparison (in sec-</td></tr><tr><td/><td/><td colspan="3">onds) on a single batch of images.</td><td/></tr><tr><td>Algorithm</td><td>Success Rate (%)</td><td colspan="4">Algorithm MNIST CIFAR IMAGENET</td></tr><tr><td>Zheng et al. (2018)</td><td>11.21</td><td>CW</td><td>16.02</td><td>234.75</td><td>872.28</td></tr><tr><td>MARGINATTACK ( ∞)</td><td>11.16</td><td>DeepFool</td><td>1.14</td><td>21.26</td><td>44.41</td></tr><tr><td>1st-Order on Logit Diff</td><td>11.15</td><td>PGD</td><td>0.87</td><td>33.17</td><td>46.3</td></tr><tr><td>PGD on Cross-Entropy Loss</td><td>10.38</td><td>FSGM</td><td>0.11</td><td>0.95</td><td>10.05</td></tr><tr><td>PGD on CW Loss</td><td>10.29</td><td>Ours ( 2)</td><td>3.01</td><td>51.03</td><td>248.82</td></tr></table>

Only the 2 versions of MARGINATTACK are shown because the other versions have similar run times. As shown, running time of MARGINATTACK is much shorter than CW, and is comparable to DeepFool and PGD. CW is significantly slower that the other algorithms because it has to run multiple trials to search for the best Lagrange multiplier. Note that DeepFool and CW enable early stop, but MARGINATTACK does not. Considering MARGINATTACK's fast convergence rate, the running time can be further reduced by early stop. , and establishes a new state-of-the-art among zero-confidence attacks. What is more, MARGINATTACK still has room for improvement. So far, only two settings of a (k) and b(k)  are developed, but MARGINATTACK will work for many other settings, as long as assumption 5 is satisfied. Authors hereby encourage exploring novel and better settings for the MARGINATTACK framework, and promote MARGINATTACK as a new robustness evaluation measure or baseline in the field of adversarial attack and defense.

Table content: <table><tr><td>5 CONCLUSION</td></tr><tr><td>We have proposed MARGINATTACK, a novel zero-confidence adversarial attack algorithm that is</td></tr><tr><td>better able to find a smaller perturbation that results in misclassification. Both theoretical and em-</td></tr><tr><td>pirical analyses have demonstrated that MARGINATTACK is an efficient, reliable and accurate adver-</td></tr><tr><td>sarial attack algorithm</td></tr></table>

Peer review (iclr2019):
 The authors propose a new method for constructing adversarial examples called MarginAttack. The method is inspired by Rosen*s algorithm, a classical algorithm in constrained optimization. At its core, Rosen*s algorithm (instantiated for adversarial examples) alternates between moving towards the set of misclassified points and moving towards the original data point (while ensuring that we do not move too far away from the set of misclassified points). The authors provide theoretical guarantees (local convergence) and a broad set of experiments. The experiments show that MarginAttack finds adversarial examples with small distortion (as good as the baselines or slightly better), and that the algorithm runs faster than the Carlini-Wagner (CW) baseline (but slower than other methods). The authors make a distinction between "fixed perturbation" attacks and "zero confidence" attacks. The former finds the strongest attack within a given constrained set, while the latter finds the smallest perturbation that leads to a misclassification. Method such as projected gradient descent fall into the "fixed perturbation" category, while MarginAttack and CW belong to the "zero confidence" category. The authors claim that zero confidence attacks pose a harder problem and hence mainly compare their experimental results to the CW attack. Indeed, their results show that MarginAttack is 3x - 5x faster than CW and sometimes achieves smaller perturbations. First of all, I would like to emphasize that the authors conducted a thorough experimental study on multiple datasets using multiple baseline algorithms. Unfortunately, the comparison to CW and PGD still leaves some questions in my opinion: - The authors state that CW does an internal binary search over the Lagrangian multiplier, and that this search goes for up to 10 steps. As a result, it is not clear whether the running time benchmarks are a fair comparison since MarginAttack does not automatically tune its parameters. To the best of my knowledge, the CW implementation in Cleverhans is specifically set up so that the user does not need to tune a large number of hyperparameters (the implementation accepts a running time overhead to achieve this). Since MarginAttack also contains multiple hyperparameters (see Table 4), it would be interesting to see how the running time of MarginAttack compares to that of a tuned CW implementation without the binary search. - The authors explicitly state that the step sizes for CW were tuned for best performance, but do not mention this for PGD. For a fair comparison, the step sizes used for PGD should also be (approximately) tuned. Moreover, it is not clear why PGD is only used for an l_inf comparison and not a l_2 comparison. - In the introduction, the authors emphasize the distinction between fixed perturbation attacks and zero confidence attacks. However, from an optimization point of view, these two notions are clearly related and a fixed perturbation attack can be converted to a small perturbation / zero confidence attack via a binary search over the perturbation size. While one would indeed expect an overhead due to the binary search, it is not clear a priori how large this overhead needs to be to achieve a competitive zero confidence attack with PGD (especially with a tuned step size for PGD, see above). I would be grateful if the authors could provide their view on these points. Until then, I will assign a rating of 5 since tuning the parameters of optimization algorithms is crucial for a fair comparison. Additional comments: - In the introduction, the authors equate white-box attacks with access to gradient information. But generally a white-box attack is understood as an attack that has arbitrary access to the target network. It may be helpful for the reader to clarify this. - In the second paragraph of the introduction, the authors claim that fixed perturbation attacks and zero confidence attacks differ significantly. But as pointed out above, it is possible to convert a fixed perturbation attack to a zero confidence attack via a binary search. So it is not clear that there is a large gap in difficulty. Moreover, the authors state that fixed perturbation attacks often come with theoretical guarantees. But to the best of my knowledge, there is no comprehensive theory that describes when a fixed perturbation attack should be expected to succeed in attacking a commonly used neural network. - On top of Page 2, the authors claim that zero-confidence attacks are a more realistic attack setting. Why is that? - The authors state that JSMA (Papernot et al., 2016) is one of the earliest works that use gradient information for constructing adversarial examples. However, L-BFGS as employed by Szegedy et al., 2013 also uses gradient information. Moreover, the authors may want to cite the work of Biggio et al. from 2013 (see the survey https://arxiv.org/abs/1712.03141). - Since all distances referred to by d(x, y) seem to be norms (and the paper relies on the existence of dual norms), it may be more clear for the reader to use the norm notation || . || from the beginning.