Year: 2018

Abstract:
Depending on how much information an adversary can access to, adversarial attacks can be classified as white-box attack and black-box attack. In both cases, optimization-based attack algorithms can achieve relatively low distortions and high attack success rates. However, they usually suffer from poor time and query complexities, thereby limiting their practical usefulness. In this work, we focus on the problem of developing efficient and effective optimization-based adversarial attack algorithms. In particular, we propose a novel adversarial attack framework for both white-box and black-box settings based on the non-convex Frank-Wolfe algorithm. We show in theory that the proposed attack algorithms are efficient with an O(1/ √ T ) convergence rate. The empirical results of attacking Inception V3 model and ResNet V2 model on the ImageNet dataset also verify the efficiency and effectiveness of the proposed algorithms. More specific, our proposed algorithms attain the highest attack success rate in both white-box and black-box attacks among all baselines, and are more time and query efficient than the stateof-the-art.

text: √ T ) convergence rate. The empirical results of attacking Inception
V3 model and ResNet V2 model on the ImageNet dataset also verify the efficiency and effectiveness of the proposed algorithms. More specific, our proposed algorithms attain the highest attack success rate in both white-box and black-box attacks among all baselines, and are more time and query efficient than the stateof-the-art.

heading: 1 INTRODUCTION
text: Deep Neural Networks (DNNs) have made many breakthroughs in different areas of artificial intelligence such as image classification (Krizhevsky et al., 2012; He et al., 2016a), object detection (Ren et al., 2015; Girshick, 2015), and speech recognition (Mohamed et al., 2012; Bahdanau et al., 2016). However, recent studies show that deep neural networks can be vulnerable to adversarial examples (Szegedy et al., 2013; Goodfellow et al., 2015) – a tiny perturbation on an image that is almost invisible to human eyes could mislead a well-trained image classifier towards misclassification. Soon later this is proved to be not a coincidence: similar phenomena have been observed in other problems such as speech recognition (Carlini et al., 2016), visual QA (Xu et al., 2017), image captioning (Chen et al., 2017a), machine translation (Cheng et al., 2018), reinforcement learning (Pattanaik et al., 2018), and even on systems that operate in the physical world (Kurakin et al., 2016).
Depending on how much information an adversary can access to, adversarial attacks can be classified into two classes: white-box attack (Szegedy et al., 2013; Goodfellow et al., 2015) and black-box attack (Papernot et al., 2016a; Chen et al., 2017c). In the white-box setting, the adversary has full access to the target model, while in the black-box setting, the adversary can only access the input and output of the target model but not its internal configurations. Among the approaches proposed for white-box and black-box attacks, optimization-based methods (Carlini & Wagner, 2017; Chen et al., 2017b;c; Ilyas et al., 2018) are most effective: they usually achieve relatively low distortions and high attack success rates. However, these methods are far from efficient. In the white-box setting, they need to solve constrained optimization problems (Carlini & Wagner, 2017), and are usually significantly slower than Fast Gradient Sign Method (FGSM) (Goodfellow et al., 2015) or Iterative FGSM (I-FGM) (Kurakin et al., 2016). Applying those methods with one or two examples are fine, yet in the case of attacking hundreds of thousands examples, e.g. in adversarial training (Kurakin et al., 2016; Madry et al., 2018), this is far from satisfactory.
In the black-box setting, it becomes even more severe since they need to make gradient estimations (Chen et al., 2017c). Therefore, a large number of queries are needed for them to perform a successful attack, especially when the data dimension is large. For example, attacking a 299×299×3 Imagenet image may take them hundreds of thousands of queries. This significantly limits their prac-
tical usefulness since they can be easily defeated by limiting the number of queries that an adversary can make to the target model.
In this study, we aim to examine the following questions in this study:
Can we improve the efficiency of the optimization-based attack algorithms? In other words, can we use less time and queries to conduct adversarial attacks?
In this work, we provide an affirmative answer to this question by proposing an efficient FrankWolfe optimization framework for both white-box and black-box attacks. In summary, we make the following main contributions:
• We propose a novel Frank-Wolfe based adversarial attack framework. The white-box attack algorithm is an iterative first-order method which admits the fast gradient sign method (FGSM) as the one-step special case. And the corresponding black-box attack algorithm adopts zeroth-order optimization with two sensing vector options (either from the Euclidean unit sphere or from the standard Gaussian distribution) provided. • We show that the proposed white-box and black-box attack algorithms enjoy an O(1/ √ T )
convergence rate. Also we show that the query complexity of the proposed black-box attack algorithm is linear in data dimension d. • Our empirical results on attacking Inception V3 model with the ImageNet dataset show that
(i) the proposed white-box attack algorithm is more efficient than all the baseline whitebox algorithms evaluated here, and (ii) the proposed black-box attack algorithm is highly efficient and is also the only one algorithm that achieves a 100% attack success rate.

heading: 2 RELATED WORK
text: There is a large body of work on adversarial attacks. In this section, we review the most relevant work in both white-box and black-box attack settings, as well as the non-convex Frank-Wolfe optimization.
White-box Attacks: Szegedy et al. (2013) proposed to use box-constrained L-BFGS algorithm for conducting white-box attacks. Goodfellow et al. (2015) proposed the Fast Gradient Sign Method (FGSM) based on linearization of the network as a simple alternative to L-BFGS. Kurakin et al. (2016) proposed to iteratively perform one-step FGSM (Goodfellow et al., 2015) algorithm and clips the adversarial point back to the distortion limit after every iteration. It is called Basic Iterative Method (BIM) or I-FGM in the literature. Madry et al. (2018) showed that for the L∞ norm case, BIM/I-FGM is equivalent to Projected Gradient Descent (PGD), which is a standard tool for constrained optimization. Papernot et al. (2016b) proposed JSMA to greedily attack the most significant pixel based on the Jacobian-based saliency map. Moosavi-Dezfooli et al. (2016) proposed attack methods by projecting the data to the closest separating hyperplane. Carlini & Wagner (2017) introduced the so-called CW attack by proposing multiple new loss functions for generating adversarial examples. Chen et al. (2017b) followed CW’s framework and use an Elastic Net term as the distortion penalty.
Black-box Attacks: One popular family of black-box attacks (Hu & Tan, 2017; Papernot et al., 2016a; 2017) is based on the transferability of adversarial examples (Liu et al., 2018; Bhagoji et al., 2017), where an adversarial example generated for one DNN may be reused to attack other neural networks. This allows the adversary to construct a substitute model that mimics the targeted DNN, and then attack the constructed substitute model using white-box attack methods. However, this type of attack algorithms usually suffer from large distortions and relatively low success rates (Chen et al., 2017c). To address this issue, Chen et al. (2017c) proposed the Zeroth-Order Optimization (ZOO) algorithm that extends the CW attack to the black-box setting and uses a zeroth-order optimization approach to conduct the attack. Although ZOO achieves much higher attack success rates than the substitute model-based black-box attacks, it suffers from a poor query complexity since its naive implementation requires to estimate the gradients of all the coordinates (pixels) of the image. To improve its query complexity, several approaches have been proposed. For example, Tu et al. (2018) introduces an adaptive random gradient estimation algorithm and a well-trained Autoencoder to speed up the attack process. Ilyas et al. (2018) and Liu et al. (2018) improved ZOO’s query complexity by using Natural Evolutionary Strategies (NES) (Wierstra et al., 2014; Salimans et al., 2017) and active learning, respectively.
Non-convex Frank-Wolfe Algorithms: The Frank-Wolfe algorithm (Frank & Wolfe, 1956), also known as the conditional gradient method, is an iterative optimization method for constrained optimization problem. Jaggi (2013) revisited Frank-Wolfe algorithm in 2013 and provided a stronger and more general convergence analysis in the convex setting. Yu et al. (2017) proved the first convergence rate for Frank-Wolfe type algorithm in the non-convex setting. Lacoste-Julien (2016) provided the convergence guarantee for Frank-Wolfe algorithm in the non-convex setting with adaptive step sizes. Reddi et al. (2016) further studied the convergence rate of non-convex stochastic Frank-Wolfe algorithm in the finite-sun optimization setting. Very recently, Staib & Jegelka (2017) proposed to use Frank-Wolfe for distributionally robust training (Sinha et al., 2018). Balasubramanian & Ghadimi (2018) proved the convergence rate for zeroth-order nonconvex Frank-Wolfe algorithm using one-side finite difference gradient estimator with standard Gaussian sensing vectors.

heading: 3 METHODOLOGY

heading: 3.1 NOTATIONS
text: Throughout the paper, scalars are denoted by lower case letters, vectors by lower case bold face letters and sets by calligraphy upper cae letters. For a vector x ∈ Rd, we denote the Lp norm of x by ‖x‖p = ( ∑d i=1 x p i )
1/p. Specially, for p = ∞, the L∞ norm of x by ‖x‖∞ = maxdi=1 |θi|. We denote PX (x) as the projection operation of projecting vector x into the set X .

heading: 3.2 PROBLEM FORMULATION
text: According to the attack purposes, attacks can be divided into two categories: untargeted attack and targeted attack. In particular, untargeted attack aims to turn the prediction into any incorrect label, while the targeted attack, which is considerably harder, requires to mislead the classifier to a specific target class. In this work, we follow the literature (Carlini & Wagner, 2017; Ilyas et al., 2018) and focus on the strictly harder targeted attack setting. It is worth noting that our proposed algorithm can be extended to untargeted attack straightforwardly.
Let us define f(·) as the classification loss function of the targeted DNN. For targeted attacks, we aim to learn an adversarial example x that is close enough to the original input xori and can be misclassified to the target class ytar. The corresponding optimization problem 1 is defined as:
minx f(x, ytar)
subject to ‖x− xori‖p ≤ . (3.1)
Evidently, the constraint set X := {x | ‖x − xori‖p ≤ } is a bounded convex set when p ≥ 1. Normally, p = 2 and p =∞ are used to measure the distortions ‖x− xori‖p, resulting in L2 attack model and L∞ attack model respectively. In this work, we study both attack models. In the sequel, since we mainly focus on the targeted attack case, we use f(x) to denote f(x, ytar) for simplicity.

heading: 3.3 FRANK-WOLFE WHITE-BOX ATTACKS
text: Frank-Wolfe algorithm (Frank & Wolfe, 1956), also known as the conditional gradient descent, is a popular optimization tool for constrained optimization. Different from PGD that first performs gradient descent followed by a projection step at each iteration, Frank-Wolfe algorithm calls a Linear Minimization Oracle (LMO) over the the constraint set X at each iteration, i.e.,
LMO ∈ argmin v∈X 〈v,∇f(xt)〉.
The LMO can be seen as the minimization of the first-order Taylor expansion of f(·) at point xt:
min v∈X
f(xt) + 〈v − xt,∇f(xt)〉.
By calling LMO, Frank Wolfe solves the linear problem in X and then perform weighted average with previous iterate to obtain the final update formula.
We present our proposed Frank-Wolfe white-box attack algorithm in Algorithm 1, which is built upon the original Frank-Wolfe algorithm. The key difference between Algorithm 1 and the standard Frank-Wolfe algorithm is in Line 4, where the LMO is called over a slightly relaxed constraint set
1Note that there is usually an additional constraint on the input variable x, e.g., x ∈ [0, 1]n for normalized image inputs.
Xλ := {x | ‖x−xori‖p ≤ λ } with λ ≥ 1, instead of the original constraint set X . When λ = 1, set Xλ reduces to X , and Algorithm 1 reduces to standard Frank Wolfe. We argue that this modification makes our algorithm more general, and gives rise to better attack results. Algorithm 1 Frank-Wolfe White-box Attack Algorithm
1: input: number of iterations T , step sizes {γt}, λ > 0, original image xori; 2: x0 = xori 3: for t = 0, . . . , T − 1 do 4: vt = argminv∈Xλ〈v,∇f(xt)〉 // LMO 5: dt = vt − xt 6: xt+1 = xt + γtdt 7: if λ > 1 then 8: xt+1 = PX (xt+1) 9: end if
10: end for 11: output: xT
The LMO solution itself can be expensive to obtain in general. Fortunately, applying Frank-Wolfe to solve (3.1) actually gives us a closed-form LMO solution. We provide the solutions of LMO (Line 4 in Algorithm 1) for L2 norm and L∞ norm cases respectively:
vt = − λ · ∇f(xt) ‖∇f(xt)‖2 + xori, (L2 norm)
vt = −λ · sign(∇f(xt)) + xori. (L∞ norm)
The derivation can be found in the supplemental materials.
Note that when T = 1, λ = 1, substituting the above LMO solutions into Algorithm 1 yields the final update of x1 = x0 − γt · ∇f(xt), which reduces to FGSM 2 when γt = 1. Similar derivation also applies to L2 norm case. Therefore, just like PGD, our proposed Frank-Wolfe white-box attack also includes FGSM (FGM) as a one-step special instance.

heading: 3.4 FRANK-WOLFE BLACK-BOX ATTACKS
text: Next we consider the black-box setting, where we cannot perform back-propagation to calculate the gradient of the loss function anymore. Instead, we can only query the DNN system’s outputs with specific inputs. To clarify, here the output refers to the logit layer’s output (confidence scores for classification), not the final prediction label. The label-only setting is doable under our framework, but will incur extra difficulty such as designing new loss functions. For simplicity, here we consider the confidence score output.
We propose a zeroth-order Frank-Wolfe based algorithm to solve this problem. Algorithm 2 show our proposed Frank-Wolfe black-box attack algorithm. The key difference between our proposed black-box attack and white-box attack is one extra gradient estimation step, which is presented in Line 4 in Algorithm 2. Also note that for the final output, we provide two options. While option II is the common choice in practice, option I is also provided for the ease of theoretical analysis.
As many other zeroth-order optimization algorithms (Shamir, 2017; Flaxman et al., 2005), Algorithm 3 uses symmetric finite differences to estimate the gradient and therefore, gets rid of the dependence on back-propagation in white-box setting. Different from Chen et al. (2017c), here we do not utilize natural basis as our sensing vectors, instead, we provide two options: one is to use vectors uniformly sampled from Euclidean unit sphere and the other is to use vectors uniformly sampled from standard multivarite Gaussian distribution. This will greatly improve the gradient estimation efficiency comparing to sensing with natural basis as such option will only be able to estimate one coordinate of the gradient vector per query. In practice, both options here provide us competitive experimental results. It is worth noting that NES method (Wierstra et al., 2014) with antithetic sampling (Salimans et al., 2017) used in Ilyas et al. (2018) yields similar formula as our Option II in Algorithm 3.
2The extra clipping operation in FGSM is to project to the additional box constraint for image classification task. We will also need this clipping operation at the end of each iteration for specific tasks such as image classification.
Algorithm 2 Frank-Wolfe Black-box Attack Algorithm 1: input: number of iterations T , step sizes {γt}, λ > 0, original image xori, target label ytar; 2: x0 = xori 3: for t = 0, . . . , T − 1 do 4: qt = ZERO ORD GRAD EST(xt) // Algorithm 3 5: vt = argminv∈Xλ〈v,qt〉 6: dt = vt − xt 7: xt+1 = xt + γtdt 8: if λ > 1 then 9: xt+1 = PX (xt+1) 10: end if 11: end for 12: Option I: xa is uniformly random chosen from {xt}Tt=1 13: Option II: xa = xT 14: output: xa
Algorithm 3 Zeroth-Order Gradient Estimation (ZERO ORD GRAD EST) 1: parameters: number of gradient estimation samples b, sampling parameter δt; 2: q = 0 3: for i = 1, . . . , b do 4: Option I: Sample ui uniformly from the Euclidean unit sphere with ‖ui‖2 = 1
q = q+ d2δtb ( f(xt + δtui)− f(xt − δtui) ) ui
5: Option II: Sample ui uniformly from the standard Gaussian distribution N (0, I) q = q+ 12δtb ( f(xt + δtui)− f(xt − δtui) ) ui 6: end for 7: output: q

heading: 4 MAIN THEORY
text: In this section, we establish the convergence guarantees for our proposed Frank-Wolfe adversarial attack algorithms described in Section 3. First, we introduce the convergence criterion for our FrankWolfe adversarial attack framework.

heading: 4.1 CONVERGENCE CRITERION
text: The loss function for common DNN models are generally nonconvex. In addition, (3.1) is a constrained optimization. For such general nonconvex constrained optimization, we typically adopt the Frank-Wolfe gap as the convergence criterion (since gradient norm of f is no longer a proper criterion for constrained optimization problems):
g(xt) = max x∈X 〈x− xt,−∇f(xt)〉.
Note that for the Frank-Wolfe gap, we always have g(xt) ≥ 0 and xt is a stationary point for the constrained optimization problem if and only if g(xt) = 0. Also the Frank-Wolfe gap is affine invariant and do not tie to any specific choice of norm, which makes itself a perfect convergence criterion for Frank-Wolfe based algorithms.

heading: 4.2 CONVERGENCE GUARANTEE FOR FRANK-WOLFE WHITE-BOX ATTACK
text: Before we are going to provide the convergence guarantee of Frank-Wolfe white-box attack (Algorithm 1), we introduce the following assumptions that are essential to the convergence analysis.
Assumption 4.1. Function f(·) is L-smooth with respect to x, i.e., for any x,x′, it holds that
f(x′) ≤ f(x) +∇f(x)>(x′ − x) + L 2 ‖x′ − x‖22.
Assumption 4.1 is a standard assumption in nonconvex optimization, and is also adopted in other Frank-Wolfe literature such as Lacoste-Julien (2016); Reddi et al. (2016). Note that even though the smoothness assumption does not hold for general DNN models, a recent study (Santurkar et al., 2018) shows that batch normalization that is used in many modern DNNs such as Inception V3
model, actually makes the optimization landscape significantly smoother 3. This justifies the validity of Assumption 4.1.
Assumption 4.2. Set X is bounded with diameter D, i.e., ‖x− x′‖2 ≤ D for all x,x′ ∈ X .
Assumption 4.2 implies that the input space is bounded. For common tasks such as image classification, given the fact that images have bounded pixel range and is a small constant, this assumption trivially holds.
Now we present the theorem, which characterizes the convergence rate of our proposed Frank-Wolfe white-box adversarial attack algorithm presented in Algorithm 1.
Theorem 4.3. Under Assumptions 4.1 and 4.2, let γt = γ = √ 2(f(x0)− f(x∗))/(LD2T ), denote g̃T = min1≤k≤T g(xk) where {xk}Tk=1 are iterates in Algorithm 1 with λ = 1, we have:
g̃T ≤ √ LD2(f(x0)− f(x∗))
2T ,
where x∗ is the optimal solution to (3.1).
Remark 4.4. Theorem 4.3 suggests that our proposed Frank-Wolfe white-box attack algorithm achieves aO(1/ √ T ) rate of convergence. Note that similar result has been proved in Lacoste-Julien (2016) under a different choice of step size.

heading: 4.3 CONVERGENCE GUARANTEE FOR FRANK-WOLFE BLACK-BOX ATTACK
text: Next we analyze the convergence of our proposed Frank-Wolfe black-box adversarial attack algorithm presented in Algorithm 2.
In order to prove the convergence of our proposed Frank-Wolfe black-box attack algorithm, we need the following additional assumption that ‖∇f(0)‖2 is bounded. Assumption 4.5. Gradient of f(·) at zero point∇f(0) satisfies maxy ‖∇f(0)‖2 ≤ Cg .
Following the analysis in Shamir (2017), let fδ(x) = Eu[f(x+δu)], which is the smoothed version of f(x). This smoothed function value plays a central role in our theoretical analysis, since it bridges the finite difference gradient approximation with the actual gradient. The following lemma shows this relationship.
Lemma 4.6. For the gradient estimator qt in Algorithm 3, its expectation and variance satisfy
E[qt] = ∇fδ(xt), E‖qt − E[qt]‖22 ≤ 1
b
( 2d(Cg + LD) 2 + 1
2 δ2tL
2d2 ) .
Now we are going to present the theorem, which characterizes the convergence rate of Algorithm 2. Theorem 4.7. Under Assumptions 4.1, 4.2 and 4.5, let γt = γ = √ 2(f(x0)− f(x∗))/(LD2T ),
b = Td and δt = √ 2/Td2, suppose we use Option I in Algorithm 2 and option II for Algorithm 3, then the output xa from Algorithm 2 with λ = 1 satisfies:
E[g(xa)] ≤ D√ 2T
(√ L(f(x0)− f(x∗)) + 2(L+ Cg + LD) ) ,
where x∗ is the optimal solution to (3.1). Remark 4.8. Theorem 4.7 suggests that Algorithm 2 also enjoys a O(1/ √ T ) rate of convergence. In terms of query complexity, the total number of queries needed is Tb = T 2d, which is linear in the data dimension d. In fact, in the experiment part, we observed that this number can be substantially smaller than d, e.g., b = 25, which is much lower than the theorem suggests. Note that although we only prove for option I in Algorithm 3, our result can be readily extended to Option II (the Gaussian sensing vector case).
3The original argument in Santurkar et al. (2018) refers to the smoothness with respect to each layer’s parameters. Note that the first layer’s parameters are in the mirror position (in terms of backpropagation) as the network inputs. Therefore, the argument in Santurkar et al. (2018) can also be applied here with respect to the network inputs.

heading: 5 EXPERIMENTS
text: In this section, we present the experimental results for our proposed Frank-Wolfe attack framework against other state-of-the-art adversarial attack algorithms in both white-box and black-box settings. All of our experiments are conducted on Amazon AWS p3.2xlarge servers which come with Intel Xeon E5 CPU and one NVIDIA Tesla V100 GPU (16G RAM). All experiments are implemented in Tensorflow platform version 1.10.0 within Python 3.6.4.

heading: 5.1 EVALUATION SETUP AND METRICS
text: We test the attack effectiveness of all algorithms by evaluating on a pre-trained Inception V3 model (Szegedy et al., 2016) and a ResNet V2 50 (He et al., 2016b) model that are trained on ImageNet dataset (Deng et al., 2009). The pre-trained Inception V3 model is reported to have a 78.0% top-1 accuracy and a 93.9% top-5 accuracy. The pre-trained ResNet V2 model is reported to have a 75.6% top-1 and a 92.8% top-5 accuracy. We randomly choose 500 images from the ImageNet validation set that are verified to be correctly classified by the pre-trained model and also randomly choose a target class for each image. Each image has a dimension of 299 × 299 × 3 and we test all attack algorithms through the same randomly chosen data samples and target labels.
We test for both L2 norm based and L∞ norm based attacks. In the white-box setting, we perform binary search / grid search for the best distortion parameter ( in our formulation and c in CW’s regularized formulation). In the black-box setting, for L2 norm based attack, we set = 5 and for L∞ based attack, we set = 0.05. For white-box attack, we restrict a maximum of 1, 000 iterations per attack for each method. And for black-box attack, we set a maximum query limit of 500, 000 per attack per image for each method.
For all algorithms, we stop the algorithm when a successful attack is found. For our proposed blackbox attack, we use option II in Algorithm 2 and test both options in Algorithm 3. We set the number of gradient estimation samples b = 25 for Algorithm 2. More detailed description on parameter settings can be found in the supplemental materials.
We evaluate the final performance through attack success rate where the success is defined as making the classifier output the exact target class label (not any incorrect labels). We also measure average attack time per image, average distortion (only on successful attacked samples) and average number of queries needed (only for black-box attack) per image. For a fair time comparison, even though some of the algorithms including ours can be written in batch form (attack multiple images at one time), all algorithms are set to attack one image at a time.
Due to page limit, we leave all experimental results on ResNet V2 model in the supplemental materials.

heading: 5.2 BASELINE METHODS
text: We compare the proposed algorithms with several state-of-the-art baseline algorithms. Specifically, we compare the proposed white-box attack algorithm with 4 (i) PGD (Madry et al., 2018) (which is essentially I-FGM (Kurakin et al., 2016)), (ii) CW attack (Carlini & Wagner, 2017) and (iii) EAD attack (Chen et al., 2017b). We compare the proposed black-box attack algorithm with (i) ZOO attack (Chen et al., 2017c) and (ii) NES-PGD attack (Ilyas et al., 2018).

heading: 5.3 WHITE-BOX ATTACK EXPERIMENTS
text: In this subsection, we present the white-box attack experiments on Inception V3 model. Tables 1 and 2 present our experimental results for L2 norm and L∞ norm based white-box attacks respectively. As we can observe from the tables, the attack success rate is 100% for every method. For the other baselines in theL2 norm case, CW method achieves the smallest average distortion, yet it comes with an expansive time cost. EAD method does not have either time advantage or distortion advantage in this experiment, probably due to its different motivation in attacking. PGD has moderate average distortion, yet it also costs quite some time to finish the attack. On the other hand, our proposed algorithm achieves the shortest attack time with moderate distortion. It significantly reduces the time complexity needed for attacking data with large dimensionality. For the L∞ norm case, CW method takes significantly longer time and does not perform very well on average distortion either.
4We did not compare with FGM (FGSM) (Goodfellow et al., 2015) since it basically has zero success rate for targeted attack on Inception V3 or ResNet V2 models.
This is largely due to the original CW was designed for L2 norm attack, and in order to apply it to L∞ norm attack, special design is needed, which sacrifices its performance in terms of runtime. Again, our proposed white-box attack algorithm achieves the shortest average attack time and a moderate average distortion.
In Figure 1, we also examine the effect of λ in our proposed Frank-Wolfe white-box attack algorithm. We plot the objective loss function value of attacking one example against the number of iterations for both L2 and L∞ based white-box attack on Inception V3 model. From the plot, we can see that larger λ indeed leads to faster convergence.

heading: 5.4 BLACK-BOX ATTACK EXPERIMENTS
text: In this subsection, we present the black-box attack experiments on Inception V3 model. For blackbox attacks, attack success rate, time and number of queries needed are more meaningful evaluation metrics than distortion distances. Therefore, we omit all the grid search / binary search steps that are used in the white-box setting since extra time / queries are needed for finding parameters that can obtain better distortion distances.
Tables 3 and 4 present our experimental results for L2 norm and L∞ norm based black-box attacks respectively. For ZOO method, note that it only has the L2 norm version and it follows CW’s framework and thus uses different loss function and problem formulation (cannot exactly control the adversarial example to be within the distortion limit, we manage to keep the average distortion around for ZOO while other methods have average distortions very close to ). Furthermore, we can observe that ZOO is quite slow in this task. Attack on a single image can take up to 2 hours for ZOO and it is only able to achieve a 74.8% success rate (compared with the 88.9% success rate in the original paper, we think the main reason is the query limit here is only half of the query limit
in the original paper). NES-PGD method, while greatly improving ZOO’s performance, still cannot achieve 100% success rate in both attack models and takes relatively more time and queries. In sharp contrast, our proposed Frank-Wolfe black-box attacks (both option I and option II) achieve the highest success rate in both L2 norm and L∞ norm based black-box attacks and further largely improve the attack efficiency.
Figure 2 illustrates the attack success rate against the number of queries plot for different algorithms in both L2 norm and L∞ norm based black-box attacks on Inception V3 model. As we can see from the plot, our proposed Frank-Wolfe black-box attack algorithm (both options) achieves the highest attack success rate and best efficiency (least queries needed for achieving the same success rate), especially in the L2 norm case.

heading: 6 CONCLUSIONS
text: In this work, we propose a Frank-Wolfe framework for efficient and effective adversarial attacks. Our proposed white-box and black-box attack algorithms enjoy an O(1/ √ T ) rate of convergence, and the query complexity of the proposed black-box attack algorithm is linear in data dimension d. Finally, our empirical study on attacking Inception V3 model with ImageNet dataset yields a 100% attack success rate for our proposed algorithms, even in the setting of black-box attack.

heading: A LINEAR MINIMIZATION ORACLE (LMO) SOLUTIONS
text: Denote u = (v − xori)/(λ ), the linear minimization problem can be written as
min ‖v−xori‖p≤λ 〈v,∇f(xt)〉 = min ‖u‖p≤1 λ · 〈u,∇f(xt)〉
= max ‖u‖p≤1
λ · 〈u,−∇f(xt)〉
= λ · ‖∇f(xt)‖p∗,
where ‖ · ‖p∗ denotes the dual norm of ‖ · ‖p. For p = 2 case, we have
〈(v − xori)/(λ ),−∇f(xt)〉 = ‖∇f(xt)‖2.
It immediately implies that
v = −λ · ∇f(xt) ‖∇f(xt)‖2 + xori.
For p =∞ case, we have
〈(v − xori)/(λ ),−∇f(xt)〉 = ‖∇f(xt)‖1.
It immediately implies that
v = −λ · sign(∇f(xt)) + xori.
For the ease of comparison, we show the full update formula (before final projection step) for our algorithm. In detail, for p =∞ case, our algorithm takes the following update formulate:
xt+1 = (1− γt)xt + γtvt = (1− γt)xt − λγt · sign(∇f(xt)) + γt · xori = xt − λγt · sign(∇f(xt))− γt(xt − xori),
and for p = 2 case, it takes
xt+1 = xt − λγt · ∇f(xt) ‖∇f(xt)‖2 − γt(xt − xori).
Compared with PGD, the full update (before final projection step) of Frank-Wolfe white-box attack includes an extra parameter λ before the normalized gradient, as well as an extra term (xt − xori). This difference makes the behavior of Frank-Wolfe based attacks different from that of PGD based attacks.

heading: B PROOF OF THE MAIN THEORY IN SECTION 4
text: B.1 PROOF OF THEOREM 4.3
Proof. For simplicity, we denote f(xt) by f(xt) for the rest of the proof. First by Assumption 4.1, we have
f(xt+1) ≤ f(xt) +∇f(xt)>(xt+1 − xt) + L
2 ‖xt+1 − xt‖22
= f(xt) + γ∇f(xt)>(vt − xt) + Lγ2
2 ‖vt − xt‖22
≤ f(xt) + γ∇f(xt)>(vt − xt) + LD2γ2
2 ,
where the last inequality uses the bounded domain condition in Assumption 4.2. Note that by definition of the Frank-Wolfe gap, we have
f(xt+1) ≤ f(xt)− γg(xt) + LD2γ2
2 .
Summation over t of the above inequality, we obtain
f(xT ) ≤ f(x0)− T−1∑ k=0 γg(xk) + TLD2γ2 2
≤ f(x0)− γT g̃T + TLD2γ2
2 ,
where the second inequality follows from the definition of g̃t. Note that by optimality we easily have f(xt+1) ≥ f(x∗). Rearrange the above inequality we have
g̃T ≤ f(x0)− f(x∗) Tγ + LD2γ 2
≤ √ LD2(f(x0)− f(x∗))
2T , where the second inequality is achieved when γ = √ 2(f(x0)− f(x∗))/(LD2T ).
B.2 PROOF OF LEMMA 4.6
Proof. For simplicity we denote f(·) by f(·) for the rest of the proof. Let us denote ψi = d 2δtb ( f(xt + δtui)− f(xt − δtui) ) ui. For the first part, we have
E[ψi] = Eu [ d
2δtb
( f(xt + δtui)− f(xt − δtui) ) ui ] = Eu [ d
2δtb f(xt + δtui)ui
] + Eu [ d
2δtb f(xt − δtui)(−ui) ] = Eu [ d
δtb f(xt + δtui)ui ] = 1
b ∇fδ(xt),
where the third equality holds due to symmetric property of ui and the last equality follows from Lemma 4.1(a) in Gao et al. (2018). Therefore, we have
E[qt] = E [ b∑ i=1 ψi ] = ∇fδ(xt).
For second part, note that ψi’s are independent from each other due to the independence of ui, we have
E‖qt − E[qt]‖22 = E ∥∥∥∥ b∑ i=1 [ ψi − Eψi ]∥∥∥∥2 2 = b∑ i=1 E ∥∥ψi − Eψi∥∥2 ≤ b∑ i=1 E ∥∥ψi∥∥2.
Now take a look at E ∥∥ψi∥∥2:
E ∥∥ψi∥∥2 = Eu∥∥∥∥ d2δtb(f(xt + δtui)− f(xt) + f(xt)− f(xt − δtui))ui ∥∥∥∥2 2
≤ 1 2b2 Eu ∥∥∥∥ dδt (f(xt + δtui)− f(xt))ui ∥∥∥∥2 2 + 1 2b2 Eu ∥∥∥∥ dδt (f(xt)− f(xt − δtui))ui ∥∥∥∥2 2
= 1 b2 Eu ∥∥∥∥ dδt (f(xt + δtui)− f(xt))ui ∥∥∥∥2 2
≤ 1 b2
( 2d‖∇f(xt)‖22 + 1
2 δ2tL
2d2 ) ,
where the first inequality is due to the fact that (a + b)2 ≤ 2a2 + 2b2, the second equality follows from the symmetric property of ui and the last inequality is by Lemma 4.1(b) in Gao et al. (2018). Also note that by Assumption 4.1 and 4.5 we have
‖∇f(xt)‖22 ≤ (‖∇f(0))‖2 + L‖xt‖2)2 ≤ (Cg + LD)2.
Combine all above results, we obtain
E‖qt − E[qt]‖22 ≤ 1
b
( 2d(Cg + LD) 2 + 1
2 δ2tL
2d2 ) .
B.3 PROOF OF THEOREM 4.7
Proof. For simplicity we denote f(xt) by f(xt) for the rest of the proof. First by Assumption 4.1, we have
f(xt+1) ≤ f(xt) +∇f(xt)>(xt+1 − xt) + L
2 ‖xt+1 − xt‖22
= f(xt) + γ∇f(xt)>(vt − xt) + Lγ2
2 ‖vt − xt‖22
≤ f(xt) + γ∇f(xt)>(vt − xt) + LD2γ2
2
= f(xt) + γq > t (vt − xt) + γ(∇f(xt)− qt)>(vt − xt) +
LD2γ2
2 ,
where the second inequality uses the bounded domain condition in Assumption 4.2. Now define an auxiliary quantity:
v̂t = argmin v∈X
〈v,∇f(xt)〉.
According to the definition of g(xt), this immediately implies
g(xt) = 〈v̂t,∇f(xt)〉. Then we further have
f(xt+1) ≤ f(xt) + γq>t (v̂t − xt) + γ(∇f(xt)− qt)>(vt − xt) + LD2γ2
2
= f(xt) + γ∇f(xt)>(v̂t − xt) + γ(∇f(xt)− qt)>(vt − v̂t) + LD2γ2
2
= f(xt)− γg(xt) + γ(∇f(xt)− qt)>(vt − v̂t) + LD2γ2
2
≤ f(xt)− γg(xt) + γD · ‖∇f(xt)− qt‖2 + LD2γ2
2 ,
where the first inequality follows from the optimally of vt in Algorithm 2 and the last inequality holds due to Cauchy-Schwarz inequality. Take expectations for both sides of the above inequality, we have
E[f(xt+1)]
≤ E[f(xt)]− γE[g(xt)] + γD · E‖∇f(xt)− qt‖2 + LD2γ2
2 ≤ E[f(xt)]− γE[g(xt)] + γD · ( ‖∇f(xt)− E[qt]‖2 + E‖qt − E[qt]‖2 ) + LD2γ2
2 , ≤ E[f(xt)]− γE[g(xt)] + γD · ( ‖∇f(xt)− E[qt]‖2 + √ E‖qt − E[qt]‖22 ) + LD2γ2
2
≤ E[f(xt)]− γE[g(xt)] + γD · ( ‖∇f(xt)−∇fδ(xt)‖2 + √ 4d(Cg + LD)2 + δ2tL 2d2
2b
)
+ LD2γ2
2 ,
≤ E[f(xt)]− γE[g(xt)] + γD ·
( δtLd
2 +
2 √ d(Cg + LD) + δtLd√
2b
) + LD2γ2
2 ,
where the second inequality follows from triangle inequality, the third inequality is due to Jenson’s inequality and the last inequality holds due to Lemma 4.6.
Summation over t of the above inequality, we obtain
E[f(xT )]
≤ f(x0)− T−1∑ t=0 γE[g(xt)] + γDT
( δtLd
2 +
2 √ d(Cg + LD) + δtLd√
2b
) + TLD2γ2
2
≤ f(x0)− γTga + γDT
( δtLd
2 +
2 √ d(Cg + LD) + δtLd√
2b
) + TLD2γ2
2 ,
where the second inequality follows from the definition of g̃a. Note that by the zeroth-order optimality, we have f(xt+1) ≥ f(x∗). Rearrange the above inequality we obtain
E[ga] ≤ f(x0)− f(x∗) Tγ + LD2γ 2 +D
( δtLd
2 +
2 √ d(Cg + LD) + δtLd√
2b
)
≤ D√ 2T
(√ L(f(x0)− f(x∗)) + 2(L+ Cg + LD) ) ,
where the second inequality is achieved by setting γ = √ 2(f(x0)− f(x∗))/(LD2T ), b = Td and
δt = √ 2/Td2.

heading: C PARAMETERS SETTINGS FOR SECTION 5
text: For Frank-Wolfe white-box attack algorithm, we list the parameters we use in Section 5 at Table 5.
Similarly, for Frank-Wolfe black-box attack algorithm, we also list the parameters we use in Section 5 at Table 6.
We also list the hyperparameters we use for baseline algorithms. Specifically, for PGD, we set a step size of 0.05 for L2 case and 0.01 for L∞ case. For CW, we set a step size of 0.002 for L2 case step size of 0.005 for L∞ case. The confidence is set to 0 and we perform 10 times binary search for the constant starting from 0.01 (L2 case) and 0.001 (L∞ case). For EAD, we use a step size of 0.01 and the same binary search strategy as CW and β is set to be 0.001. In terms of black-box experiments, for ZOO, we set a step size of 0.01 and the initial constant is set to be 1 without binary search to achieve better query complexity. For NES-PGD, we set a step size of 0.3 for L2 case and 0.01 for L∞ case.

heading: D ADDITIONAL EXPERIMENTS
text: D.1 RESNET V2 WHITE-BOX ATTACK RESULTS
In this subsection, we present the white-box attack experiments on ResNet V2 model. Tables 7 and 8 present our experimental results for L2 norm and L∞ norm based white-box attacks respectively. For the other baselines in the L2 norm case, surprisingly, CW method cannot achieve the best L2 distortion as it does in Inception V3 model. EAD method is relatively faster than CW in terms of attack time yet it has the largest distortion and a quite low success rate of 73.0%. PGD has the smallest average distortion in this setting, yet it also costs a lot of attack time. On the other hand, our proposed algorithm achieves the highest attack success rate within very short attack time with very small distortion. It significantly reduces the time complexity needed for effective attacking data with large dimensionality. For the L∞ norm case, CW method takes significantly longer time and does not perform very well on average distortion either. Our proposed white-box attack algorithm, on the other hand, again achieves the shortest average attack time and 100% success rate.
D.2 RESNET V2 BLACK-BOX ATTACK RESULTS
In this subsection, we present the black-box experiments on ResNet V2 model. We again mainly focus on evaluating attack success rate, time and number of queries needed. In previous experiments on Inception V3 model, we show the performance of different black-box attack algorithms given enough number of queries (i.e., 500,000 per attack per image). And it shows that basically all
algorithms can achieve very high attack success rate (almost 100%). Now we examine a much harder case, where we reduce the the number of allowed queries per attack per image to only 50, 000. Tables 9 and 10 present our experimental results for L2 norm and L∞ norm based black-box attacks respectively. We still set = 5 for L2 case and = 0.05 for L∞ case.
For the L2 norm case, ZOO method barely succeeds due to the strict query limit of 50, 00 while it typically requires over 106 queries to attack successfully. Our proposed Frank-Wolfe black-box attacks, on the other hand, achieve nearly 60% attack success rate under such a stringent query budget. For the L∞ norm case, both NES-PGD method and ours achieve over 90% success rate. Even though they share similar average attack time and average number of queries needed, our Frank-Wolfe based methods still achieve the best in terms of all three evaluation metrics.
Figure 3 illustrates the attack success rate against the number of queries plot for different algorithms in both L2 norm and L∞ norm based black-box attack on ResNet V2 model. Note that here we have a query limit of 50, 000, which is especially hard for the L2 norm case. As we can see from the Figure 3, our proposed Frank-Wolfe black-box attack algorithm (both options) achieves the best performance (highest attack success rate and smallest queries needed for achieving the same success rate).
D.3 VISUALIZATION EXAMPLES
For the completeness, we also provide some visual illustrations on the adversarial examples generated by various algorithms. Figure 4 shows some adversarial examples generated through different L2 norm based white-box attacks. Figure 5 shows some adversarial examples generated through different L∞ norm based black-box attacks.

Review summaries:
The paper investigates the Frank-Wolfe (FW) algorithm for constructing adversarial examples both in a white-box and black-box setting. The authors provide both a theoretical analysis (convergence to a stationary point) and experiments for an InceptionV3 network on ImageNet. The main claim is that the proposed algorithm can construct adversarial examples faster than various baselines (PGD, I-FGSM, CW, etc.), and from fewer queries in a black-box setting.