Title: YET ANOTHER BUT MORE EFFICIENT BLACK-BOX ADVERSARIAL ATTACK: TILING AND EVOLUTION STRATEGIES

Abstract: We introduce a new black-box attack achieving state of the art performances. Our approach is based on a new objective function, borrowing ideas from ∞ -white box attacks, and particularly designed to fit derivative-free optimization requirements. It only requires to have access to the logits of the classifier without any other information which is a more realistic scenario. Not only we introduce a new objective function, we extend previous works on black box adversarial attacks to a larger spectrum of evolution strategies and other derivative-free optimization methods. We also highlight a new intriguing property that deep neural networks are not robust to single shot tiled attacks. Our models achieve, with a budget limited to 10, 000 queries, results up to 99.2% of success rate against InceptionV3 classifier with 630 queries to the network on average in the untargeted attacks setting, which is an improvement by 90 queries of the current state of the art. In the targeted setting, we are able to reach, with a limited budget of 100, 000, 100% of success rate with a budget of 6, 662 queries on average, i.e. we need 800 queries less than the current state of the art.

1. INTRODUCTION:

Despite their success, deep learning algorithms have shown vulnerability to adversarial attacks (Biggio et al., 2013; Szegedy et al., 2014) , i.e. small imperceptible perturbations of the inputs, that lead the networks to misclassify the generated adversarial examples. Since their discovery, adversarial attacks and defenses have become one of the hottest research topics in the machine learning community as serious security issues are raised in many critical fields. They also question our understanding of deep learning behaviors. Although some advances have been made to explain theoretically (Fawzi et al., 2016; Sinha et al., 2017; Cohen et al., 2019; Pinot et al., 2019) and experimentally (Goodfellow et al., 2015; Xie et al., 2018; Meng & Chen, 2017; Samangouei et al., 2018; Araujo et al., 2019) adversarial attacks, the phenomenon remains misunderstood and there is still a gap to come up with principled guarantees on the robustness of neural networks against maliciously crafted attacks. Designing new and stronger attacks helps building better defenses, hence the motivation of our work.

First attacks were generated in a setting where the attacker knows all the information of the network (architecture and parameters). In this white box setting, the main idea is to perturb the input in the direction of the gradient of the loss w.r.t. the input (Goodfellow et al., 2015; Kurakin et al., 2016; Carlini & Wagner, 2017; Moosavi-Dezfooli et al., 2016) . This case is unrealistic because the attacker has only limited access to the network in practice. For instance, web services that propose commercial recognition systems such as Amazon or Google are backed by pretrained neural networks. A user can query this system by sending an image to classify. For such a query, the user only has access to the inference results of the classifier which might be either the label, probabilities or logits. Such a setting is coined in the literature as the black box setting. It is more realistic but also more challenging from the attacker's standpoint.

As a consequence, several works proposed black box attacks by just querying the inference results of a given classifier. A natural way consists in exploiting the transferability of an adversarial attack, based on the idea that if an example fools a classifier, it is more likely that it fools another one (Papernot et al., 2016a) . In this case, a white box attack is crafted on a fully known classifier. Papernot et al. (2017) exploited this property to derive practical black box attacks. Another approach within the black box setting consists in estimating the gradient of the loss by querying the classifier (Chen et al., 2017; Ilyas et al., 2018a; b) . For these attacks, the PGD attack (Kurakin et al., 2016; Madry et al., 2018a) algorithm is used and the gradient is replaced by its estimation.

In this paper, we propose efficient black box adversarial attacks using stochastic derivative free optimization (DFO) methods with only access to the logits of the classifier. By efficient, we mean that our model requires a limited number of queries while outperforming the state of the art in terms of attack success rate. At the very core of our approach is a new objective function particularly designed to suit classical derivative free optimization. We also highlight a new intriguing property that deep neural networks are not robust to single shot tiled attacks. It leverages results and ideas from ∞ -attacks. We also explore a large spectrum of evolution strategies and other derivative-free optimization methods thanks to the Nevergrad framework (Rapin & Teytaud, 2018) .

Outline of the paper. We present in Section 2 the related work on adversarial attacks. Section 3 presents the core of our approach. We introduce a new generic objective function and discuss two practical instantiations leading to a discrete and a continuous optimization problems. We then give more details on the best performing derivative-free optimization methods, and provide some insights on our models and optimization strategies. Section 4 is dedicated to a thorough experimental analysis, where we show we reach state of the art performances by comparing our models with the most powerful black-box approaches on both targeted and untargeted attacks. We also assess our models against the most efficient so far defense strategy based on adversarial training. We finally conclude our paper in Section 5.

2. RELATED WORK:

Adversarial attacks have a long standing history in the machine learning community. Early works appeared in the mid 2000's where the authors were concerned about Spam classification (Biggio et al., 2009) . Szegedy et al. (2014) revives this research topic by highlighting that deep convolutional networks can be easily fooled. Many adversarial attacks against deep neural networks have been proposed since then. One can distinguish two classes of attacks: white box and black box attacks. In the white box setting, the adversary is supposed to have full knowledge of the network (architecture and parameters), while in the black box one, the adversary only has limited access to the network: she does not know the architecture, and can only query the network and gets labels, logits or probabilities from her queries. An attack is said to have suceeded (we also talk about Attack Success Rate), if the input was originally well classified and the generated example is classified to the targeted label.

The white box setting attracted more attention even if it is the more unrealistic between the two. The attacks are crafted by by back-propagating the gradient of the loss function w.r.t. the input. The problem writes as a non-convex optimization procedure that either constraints the perturbation or aims at minimizing its norm. Among the most popular ones, one can cite FGSM (Goodfellow et al., 2015) , PGD (Kurakin et al., 2016; Madry et al., 2018a ), Deepfool (Moosavi-Dezfooli et al., 2016) , JSMA (Papernot et al., 2016b) , Carlini&Wagner attack (Carlini & Wagner, 2017) and EAD (Chen et al., 2018) .

The black box setting is more realistic, but also more challenging. Two strategies emerged in the literature to craft attacks within this setting: transferability from a substitute network, and gradient estimation algorithms. Transferability has been pointed out by Papernot et al. (2017) . It consists in generating a white-box adversarial example on a fully known substitute neural network, i.e. a network trained on the same classification task. This crafted adversarial example can be transferred to the targeted unknown network. Leveraging this property, Moosavi-Dezfooli et al. (2017) proposed an algorithm to craft a single adversarial attack that is the same for all examples and all networks. Despite the popularity of these methods, gradient estimation algorithms outperform transferability methods. Chen et al. (2017) proposed a variant of the powerful white-box attack introduced in (Carlini & Wagner, 2017), based on gradient estimation with finite differences. This method achieves good results in practice but requires a high number of queries to the network. To reduce the number of queries, Ilyas et al. (2018a) proposed to rely rather on Natural Evolution Strategies (NES). These derivative-free optimization approaches consist in estimating the parametric distribution of the min-ima of a given objective function. This amounts for most of NES algorithms to perform a natural gradient descent in the space of distributions (Ollivier et al., 2017) . In (Al-Dujaili & O'Reilly, 2019) , the authors propose to rather estimate the sign of the gradient instead of estimating the its magnitude suing zeroth-order optimization techniques. They show further how to reduce the search space from exponential to linear. The achieved results were state of the art at the publication date. In Liu et al. (2019) , the authors introduced a zeroth-order version of the signSGD algorithm, studied its convergence properties and showed its efficiency in crafting adversarial black-box attacks. The results are promising but fail to beat the state of the art. In Tu et al. (2019) , the authors introduce the AutoZOOM framework combining gradient estimation and an auto-encoder trained offline with unlabeled data. The idea is appealing but requires training an auto-encoder with an available dataset, which an additional effort for the attacker. Besides, this may be unrealistic for several use cases. More recently, Moon et al. (2019) proposed a method based on discrete and combinatorial optimization where the perturbations are pushed towards the corners of the ∞ ball. This method is to the best of our knowledge the state of the art in the black box setting in terms of queries budget and success rate. We will focus in our experiments on this method and show how our approaches achieve better results.

Several defense strategies have been proposed to diminish the impact of adversarial attacks on networks accuracies. A basic workaround, introduced in (Goodfellow et al., 2015) , is to augment the learning set with adversarial attacks examples. Such an approach is called adversarial training in the literature. It helps recovering some accuracy but fails to fully defend the network, and lacks theoretical guarantees, in particular principled certificates. Defenses based on randomization at inference time were also proposed (Lecuyer et al., 2018; Cohen et al., 2019; Pinot et al., 2019) . These methods are grounded theoretically, but the guarantees cannot ensure full protection against adversarial examples. The question of defenses and attacks is still widely open since our understanding of this phenomenon is still in its infancy. We evaluate our approach against adversarial training, the most powerful defense method so far.

3. METHODS:



3.1. GENERAL FRAMEWORK:

Let us consider a classification task X → [K] where X ⊆ R d is the input space and [K] = {1, ..., K} is the corresponding label set. Let f : R d → R K be a classifier (a feed forward neural network in our paper) from an input space X returning the logits of each label in [K] such that the predicted label for a given input is arg max i∈[K] f i (x). The aim of ||.|| ∞ -bounded untargeted adversarial attacks is, for some input x with label y, to find a perturbation τ such that arg max i∈[K] f i (x) = y. Classically, ||.|| ∞ -bounded untargeted adversarial attacks aims at optimizing the following objective: max

EQUATION

where L is a loss function (typically the cross entropy) and y the true label. For targeted attacks, the attacker targets a label y t by maximizing -L(f (x + τ ), y t ). With access to the gradients of the network, gradient descent methods have proved their efficiency (Kurakin et al., 2016; Madry et al., 2018a) . So far, the outline of most black box attacks was to estimate the gradient using either finite differences or natural evolution strategies. Here using evolutionary strategies heuristics, we do not want to take care of the gradient estimation problem.

3.2. TWO OPTIMIZATION PROBLEMS:

In some DFO approaches, the default search space is R d . In the ∞ bounded adversarial attacks setting, the search space is B ∞ ( ) = {τ : ||τ || ∞ ≤ }. It requires to adapt the problem in Eq 1. Two variants are proposed in the sequel leading to continuous and discretized versions of the problem.

The continuous problem. As in Carlini & Wagner (2017) , we use the hyperbolic tangent transformation to restate our problem since B ∞ ( ) = tanh (R d ). This leads to a continuous search space on which evolutionary strategies apply. Hence our optimization problem writes:

EQUATION

We will call this problem DFO c -optimizer where optimizer is the used black box derivative free optimization strategy.

The discretized problem. Moon et al. (2019) pointed out that PGD attacks (Kurakin et al., 2016; Madry et al., 2018b) are mainly located on the corners of the ∞ -ball. They consider optimizing the following max

EQUATION

The author in (Moon et al., 2019) proposed a purely discrete combinatorial optimization to solve this problem (Eq. 3). As in Bello et al. (2017) , we here consider how to automatically convert an algorithm designed for continuous optimization to discrete optimization. To make the problem in Eq. 3 compliant with our evolutionary strategies setting, we rewrite our problem by considering a stochastic function f (x + τ ) where, for all i, τ i ∈ {-1, +1} and

P(τ i = 1) = Softmax(a i , b i ) = e a i

e a i +e b i . Hence our problem amounts to find the best parameters a i and b i that optimize:

EQUATION

We then rely on evolutionary strategies to find the parameters a and b. As the optima are deterministic, the optimal values for a and b are at infinity. Some ES algorithms are well suited to such setting as will be discussed in the sequel. We will call this problem DFO d -optimizer where optimizer is the used black box derivative free optimization strategy for a and b. In this case, one could reduce the problem to one variale a i with P(τ i = 1) = 1 1+e -a i , but experimentally the results are comparable, so we concentrate on Problem 4.

3.3. DERIVATIVE-FREE OPTIMIZATION METHODS:

Derivative-free optimization methods are aimed at optimizing an objective function without access to the gradient. There exists a large and wide literature around derivative free optimisation. In this setting, one algorithm aims to minimize some function f on some space X . The only thing that could be done by this algorithm is to query for some points x the value of f (x). As evaluating f can be computationally expensive, the purpose of DFO methods is to get a good approximation of the optima using a moderate number of queries. We tested several evolution strategies (Rechenberg, 1973; Beyer, 2001) : the simple (1 + 1)-algorithm (Matyas, 1965; Schumer & Steiglitz, 1968 ), Covariance Matrix Adaptation (CMA (Hansen & Ostermeier, 2003) ). For these methods, the underlying algorithm is to iteratively update some distribution P θ defined on X . Roughly speaking, the current distribution P θ represents the current belief of the localization of the optimas of the goal function. The parameters are updated using objective function values at different points. It turns out that this family of algorithms, than can be reinterpreted as natural evolution strategies, perform best. The two best performing methods will be detailed in Section 3.3.1; we refer to references above for other tested methods.

3.3.1. OUR BEST PERFORMING METHODS: EVOLUTION STRATEGIES:

The (1 + 1)-ES algorithm. The (1 + 1)-evolution strategy with one-fifth rule (Matyas, 1965; Schumer & Steiglitz, 1968 ) is a simple but effective derivative-free optimization algorithm (in supplementary material, Alg. 1). Compared to random search, this algorithm moves the center of the Gaussian sampling according to the best candidate and adapts its scale by taking into account their frequency. Yao & Liu (1996) proposed the use of Cauchy distributions instead of classical Gaussian sampling. This favors large steps, and improves the results in case of (possibly partial) separability of the problem, i.e. when it is meaningful to perform large steps in some directions and very moderate ones in the other directions.

CMA-ES algorithm. The Covariance Matrix Adaptation Evolution Strategy (Hansen & Ostermeier, 2003) combines evolution strategies (Beyer, 2001) , Cumulative Step-Size Adaptation (Arnold & Beyer, 2004) , and a specific method for adaptating the covariance matrix. An outline is provided in supplementary material, Alg. 2. CMA-ES is an effective and robust algorithm, but it becomes catastrophically slow in high dimension due to the expensive computation of the square root of the matrix. As a workaround, Ros & Hansen (2008) propose to approximate the covariance matrix by a diagonal one. This leads to a computational cost linear in the dimension, rather than the original quadratic one. 2014)). A natural evolution strategy consists in estimating iteratively the distribution of the optima. For most NES approaches, a fortiori CMA-ES, the iterative estimation consists in a second-order gradient descent (also known as natural gradient) in the space of distributions (e.g. Gaussians). (1+1)-ES can also be seen as a NES, where the covariance matrix is restricted to be proportional to the identity. Note however that from an algorithmic perspective, both CME-ES and (1+1)-ES optimize the quantile of the objective function.

3.3.2. HYPOTHESES FOR DFO METHODS IN THE ADVERSARIAL ATTACKS CONTEXT:

The state of the art in DFO and intuition suggest the followings. Using softmax for exploring only points in the corner (Eq. 3) is better for moderate budget, as corners are known to be good adversarial candidates; however, for high precision attacks (with small τ ) a smooth continuous precision (Eq 2) is more relevant. With or without softmax, the optimum is at infinity1 , which is in favor of methods having fast step-size adaptation or samplings with heavy-tail distributions. With an optimum at infinity, (Chotard et al., 2012) has shown how fast is the adaptation of the step-size when using cumulative step-size adaptation (as in CMA-ES), as opposed to slower rates for most methods. Cauchy sampling (Yao & Liu, 1996) in the (1 + 1)-ES is known for favoring fast changes; this is consistent with the superiority of Cauchy sampling in our setting compared to Gaussian sampling. Newuoa, Powell, SQP, Bayesian Optimization, Bayesian optimization are present in Nevergrad but they have an expensive (budget consumption linear is linear w.r.t. the dimension) initial sampling stage which is not possible in our high-dimensional / moderate budget context. The targeted case needs more precision and favors algorithms such as Diagonal CMA-ES which adapt a step-size per coordinate whereas the untargeted case is more in favor of fast random exploration such as the (1 + 1)-ES. Compared to Diagonal-CMA, CMA with full covariance might be too slow; given a number of queries (rather than a time budget) it is however optimal for high precision.

3.4 THE TILING TRICK Ilyas et al. (2018b) suggested to tile the attack to lower the number of queries necessary to fool the network. Concretely, they observe that the gradient coordinates are correlated for close pixels in the images, so they suggested to add the same noise for small square tiles in the image (see Fig. 1 ). We exploit the same trick since it reduces the dimensionality of the search space, and makes hence evolutionary strategies suited to the problem at hand. Besides breaking the curse of dimensionality, tiling leads surprisingly to a new property that we discovered during our experiments. At a given tiling scale, convolutional neural networks are not robust to random noise. Section 4.2 is devoted to this intriguing property. Interestingly enough, initializing our optimization algorithms with a tiled noise at the appropriate scale drastically speeds up the convergence, leading to a reduced number of queries. 

4. EXPERIMENTS:



4.1. GENERAL SETTING AND IMPLEMENTATION DETAILS:

We compare our approach to the "bandits" method (Ilyas et al., 2018b) and the parsimonious attack (Moon et al., 2019) . The latter (parsimonious attack) is, to the best of our knowledge, the state of the art in the black-box setting from the literature; bandits method is also considered in our benchmark given its ties to our models. We reproduced the results from (Moon et al., 2019) in our setting for fair comparison. As explained in section 3.2, our attacks can be interpreted as ∞ ones. We use the large-scale ImageNet dataset (Deng et al., 2009) . As usually done in most frameworks, we quantify our success in terms of attack success rate, median queries and average queries.

Here, the number of queries refers to the number of requests to the output logits of a classifier for a given image. For the success rate, we only consider the images that were correctly classified by our model. We use InceptionV3 (Szegedy et al., 2017) , VGG16 (Simonyan & Zisserman, 2014) with batch normalization (VGG16bn) and ResNet50 (He et al., 2016) architectures to measure the performance of our algorithm on the ImageNet dataset. These models reach accuracy close to the the state of the art with around 75 -80% for the Top-1 accuracy and 95% for the Top-5 accuracy.

We use pretrained models from PyTorch (Paszke et al., 2017) . All images are normalized to [0, 1].

Results on VGG16bn and ResNet50 are deferred in supplementary material E. The images to be attacked are selected at random.

We first show that convolutional networks are not robust to tiled random noise, and more surprisingly that there exists an optimal tile size that is the same for all architectures and noise intensities. Then, we evaluate our methods on both targeted and untargeted objectives. We considered the following losses: the cross entropy L(f (x), y) = -log(P(y|x)) and a loss inspired from the "Carlini&Wagner" attack: L(f (x), y) = -P(y|x) + max y =y P(y |x) where P(y|x) = [Softmax(f (x))] y , the probability for the classifier to classify the input x to label y. The results for the second loss are deferred in supplementary material C. For all our attacks, we use the Nevergrad (Rapin & Teytaud, 2018) implementation of evolution strategies. We did not change the default parameters of the optimization strategies.

4.2. CONVOLUTIONAL NEURAL NETWORKS ARE NOT ROBUST TO TILED RANDOM NOISE:

In this section, we highlight that neural neural networks are not robust to ∞ tiled random noise. A noise on an image is said to be tiled if the added noise on the image is the same on small squares of pixels (see Figure 2 ). In practice, we divide our image in equally sized tiles. For each tile, we add to the image a randomly chosen constant noise: + with probability The number of queries (x-axis) is plotted with a logarithmic scale.

Table 1 : Comparison of our method with the parsimonious and bandits attacks in the untargeted setting on ImageNet on InceptionV3 pretrained network for = 0.05 and 10, 000 as budget limit.  and ResNet50 ). The optimal number of tiles (in the sense of attack success rate) is, surprisingly, independent from the architecture and the noise intensity. We also note that the InceptionV3 architecture is more robust to random tiled noise than VGG16bn and ResNet50 architectures. InceptionV3 blocks are parallel convolutions with different filter sizes that are concatenated. Using different filter sizes may attenuate the effect of the tiled noise since some convolution sizes might be less sensitive. We test this with a single random attack with various numbers of tiles (cf. Figure 1 , 2). We plotted additional graphs in supplementary material B.

Method:



4.3. UNTARGETED ADVERSARIAL ATTACKS:

We first evaluate our attacks in the untargeted setting. The aim is to change the predicted label of the classifier. Following (Moon et al., 2019; Ilyas et al., 2018b) , we use 10, 000 images that are initially correctly classified and we limit the budget to 10, 000 queries. We experimented with 30 and 50 tiles on the images. Only the best performing methods are reported in Table 1 . We compare our results with (Moon et al., 2019) and (Ilyas et al., 2018b) on InceptionV3 (cf. Table 1 ). We also plotted the cumulative success rate in terms of required budget in Figure 3 . We also evaluated our attacks for smaller noise in supplementary material D. We achieve results outperforming or at least equal to the state of the art in all cases. More remarkably, We improve by far the number of necessary queries to fool the classifiers. The tiling trick partially explains why the average and the median number of queries are low. Indeed, the first queries of our evolution strategies is in general close to random search and hence, according to the observation of Figs 1-2, the first steps are more likely to fool the network, which explains why the queries budget remains low. This Discrete strategies reach better median numbers of queries -which is consistent as we directly search on the limits of the ∞ -ball; however, given the restricted search space (only corners of the search space are considered), the success rate is lower and on average the number of queries increases due to hard cases.

4.4. TARGETED ADVERSARIAL ATTACKS:

We also evaluate our methods in the targeted case on ImageNet dataset. We selected 1, 000 images, correctly classified. Since the targeted task is harder than the untargeted case, we set the maximum budget to 100, 000 queries, and = 0.05. We uniformly chose the target class among the incorrect ones. We evaluated our attacks in comparison with the bandits methods (Ilyas et al., 2018b) and the parsimonious attack (Moon et al., 2019) on InceptionV3 classifier. We also plotted the cumulative success rate in terms of required budget in Figure 3 . CMA-ES beats the state of the art on all criteria. DiagonalCMA-ES obtains acceptable results but is less powerful that CMA-ES in this specific case.

The classical CMA optimizer is more precise, even if the run time is much longer. Cauchy (1 + 1)-ES and discretized optimization reach good results, but when the task is more complicated they do not reach as good results as the state of the art in black box targeted attacks.

4.5. UNTARGETED ATTACKS AGAINST AN ADVERSARIALLY TRAINED NETWORK:

In this section, we experiment our attacks against a defended network by adversarial training (Goodfellow et al., 2015) . Since adversarial training is computationally expensive, we restricted ourselves to the CIFAR10 dataset (Krizhevsky et al., 2009) for this experiment. Image size is 32 × 32 × 3.

We adversarially trained a WideResNet28x10 (Zagoruyko & Komodakis, 2016) with PGD ∞ attacks (Kurakin et al., 2016; Madry et al., 2018a) of norm 8/256 and 10 steps of size 2/256. In this setting, we randomly selected 1, 000 images, and limited the budget to 20, 000 queries. We ran PGD ∞ attacks (Kurakin et al., 2016; Madry et al., 2018a) of norm 8/256 and 20 steps of size 1/256 against our network, and achieved a success rate up to 36%, which is the the state of the art in the white box setting. We also compared our method to the Parsimonious and bandit attacks. Results are reported in Appendix 6. On this task, the parsimonious attack method is slightly better than our best approach.

5. CONCLUSION:

In this paper, we proposed a new framework for crafting black box adversarial attacks based on derivative free optimization. Because of the high dimensionality and the characteristics of the problem (see Section 3.3.2), not all optimization strategies give satisfying results. However, combined with the tiling trick, evolutionary strategies such as CMA, DiagonalCMA and Cauchy (1+1)-ES beats the current state of the art in both targeted and untargeted settings. In particular, DFO c -CMA improves the state of the art in terms of success rate in almost all settings. We also validated the robustness of our attack against an adversarially trained network. Future work will be devoted to better understanding the intriguing property of the effect that a neural network is not robust to a one shot randomly tiled attack. 

B ADDITIONAL PLOTS FOR THE TILING TRICK:



C RESULTS WITH "CARLINI&WAGNER" LOSS:

In this section, we follow the same experimental setup as in Section 4.3, but we built our attacks with the "Carlini&Wagner" loss instead of the cross entropy. We remark the results are comparable and similar.

Table 3 : Comparison of our method with"Carlini&Wagner" loss versus the parsimonious and bandits attacks in the untargeted setting on InceptionV3 pretrained network for = 0.05 and 10, 000 as budget limit. 



D UNTARGETED ATTACKS WITH SMALLER NOISE INTENSITIES:

We evaluated our method on smaller noise intensities ( ∈ {0.01, 0.03, 0.05}) in the untargeted setting on ImageNet dataset. In this framework, we also picked up randomly 10, 000 images and limited our budget to 10, 000 queries. We compared to the bandits method (Ilyas et al., 2018b) and to the parsimonious attack (Moon et al., 2019) on InceptionV3 network. We limited our experiments to a number of tiles of 50. We report our results in Table 4 . We remark our attacks reach state of the art for = 0.03 and = 0.05 both in terms of success rate and queries budget. For = 0.01, we reach results comparable to the state of the art. 

E UNTARGETED ATTACKS AGAINST OTHER ARCHITECTURES:

We also evaluated our method on different neural networks architectures. For each network we randomly selected 10, 000 images that were correctly classified. We limit our budget to 10, 000 queries and set the number of tiles to 50. We achieve a success attack rate up to 100% on every classifier with a budget as low as 8 median queries for the VGG16bn for instance (see Table 5 ). One should notice that the performances are lower on InceptionV3 as it is also reported for the bandit methods in (Ilyas et al., 2018b) . This possibly due to the fact that the tiling trick is less relevant on the Inception network than on the other networks (see Fig. 2 ).

Table 5 : Comparison of our method on the ImageNet dataset with InceptionV3 (I), ResNet50 (R) and VGG16bn (V) for = 0.05 and 10, 000 as budget limit. 



:

i.e. the optima of the ball constrained problem 1, would be close to the boundary or on the boundary of the ∞ ball. In that case, the optimum of the continuous problem

will be at ∞ or close to it. On the discrete case 4 it is easy to see that the optimum is when ai or bi → ∞.

Figures and Tables:

Figure 1: Illustration of the tiling trick: the same noise is applied on small tile squares.

Figure 2: Success rate of a single shot random attacks on ImageNet vs. the number of tiles used to craft the attack. On the left, attacks are plotted against InceptionV3 classifier with different noise intensities ( ∈ {0.01, 0.03, 0.05, 0.1}). On the right, is fixed to 0.05 and the single shot attack is evaluated on InceptionV3, ResNet50 and VGG16bn.

Figure3: The cumulative success rate in terms the number of queries for the number of queries required for attacks on ImageNet with = 0.05 in the untargeted (left) and targeted setting (right). The number of queries (x-axis) is plotted with a logarithmic scale.

Figure 4: Random attack success rate against InceptionV3 (left), ResNet50 (center), VGG16bn (right) for different noise intensities. We just randomly draw one tiled attack and check if it is successful.

Comparison of our method with the parsimonious and bandits attacks in the targeted setting on ImageNet on InceptionV3 pretrained network for = 0.05 and 100, 000 as budget limit.

Table content: <table><tr><td>Method</td><td colspan="4"># of tiles Average queries Median queries Success rate</td></tr><tr><td>Parsimonious</td><td>-</td><td>7184</td><td>5116</td><td>100%</td></tr><tr><td>Bandits</td><td>50</td><td>25341</td><td>18053</td><td>92.5%</td></tr><tr><td>DFO c -Cauchy(1 + 1)-ES</td><td>50</td><td>9789</td><td>6049</td><td>83.2%</td></tr><tr><td>DFO c -DiagonalCMA</td><td>50</td><td>6768</td><td>3797</td><td>94.0%</td></tr><tr><td>DFO c -CMA</td><td>50</td><td>6662</td><td>4692</td><td>100%</td></tr><tr><td>DFO d -DiagonalCMA</td><td>50</td><td>8957</td><td>4619</td><td>64.2%</td></tr></table>

4: Random attack success rate against InceptionV3 (left), ResNet50 (center), VGG16bn (right) for different noise intensities. We just randomly draw one tiled attack and check if it is successful. Random attack success rate for different noise intensities ∈ {0.01, 0.03, 0.05, 0.1} (from right to left) against different architectures. We just randomly draw one tiled attack and check if it is successful.

Table content: <table><tr><td/><td/><td colspan="5">Attack success for = 0.01 with different architetures versus the number of tiles</td><td/><td/><td/><td colspan="4">Attack success for = 0.03 with different architetures versus the number of tiles</td><td/><td/><td/><td colspan="4">Attack success for = 0.05 with different architetures versus the number of tiles</td><td/><td/><td/><td>Attack success for = 0.1 with different architetures versus the number of tiles</td></tr><tr><td>Attack success rate</td><td>0.02 0.03 0.04 0.05</td><td/><td/><td/><td/><td>ResNet50 InceptionV3 VGG16bn</td><td>Attack success rate</td><td>0.075 0.100 0.125 0.150 0.175 0.200</td><td/><td/><td/><td/><td>ResNet50 InceptionV3 VGG16bn</td><td>Attack success rate</td><td>0.2 0.3 0.4 0.5</td><td/><td/><td/><td/><td>ResNet50 InceptionV3 VGG16bn</td><td>Attack success rate</td><td>0.4 0.6 0.8</td><td/><td>ResNet50 InceptionV3 VGG16bn</td></tr><tr><td/><td>0.01</td><td>0</td><td>50</td><td>100 Number of tiles</td><td>150</td><td>200</td><td/><td>0.025 0.050</td><td>0</td><td>50</td><td>100 Number of tiles</td><td>150</td><td>200</td><td/><td>0.0 0.1</td><td>0</td><td>50</td><td>100 Number of tiles</td><td>150</td><td>200</td><td/><td>0.0 0.2</td><td>0</td><td>50</td><td>100 Number of tiles</td><td>150</td><td>200</td></tr><tr><td colspan="3">Figure 5:</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr></table>

Results of our method compared to the parsimonious and bandit attacks in the untargeted setting on InceptionV3 pretrained network for different values of noise intensities ∈ {0.01, 0.03, 0.05} and a maximum of 10, 000 queries.

Table content: <table><tr><td/><td>Method</td><td colspan="4"># of tiles Avg. queries Med. queries Success rate</td></tr><tr><td/><td>Parsimonious</td><td>-</td><td>722</td><td>237</td><td>98.5%</td></tr><tr><td/><td>Bandits</td><td>50</td><td>995</td><td>249</td><td>95.1%</td></tr><tr><td>0.05</td><td>DFO c -Cauchy(1 + 1)-ES</td><td>50</td><td>510</td><td>63</td><td>97.3%</td></tr><tr><td/><td>DFO c -DiagonalCMA</td><td>50</td><td>623</td><td>191</td><td>98.7%</td></tr><tr><td/><td>DFO c -CMA</td><td>50</td><td>630</td><td>259</td><td>99.2%</td></tr><tr><td/><td>DFO d -DiagonalCMA</td><td>50</td><td>485</td><td>38</td><td>97.4%</td></tr><tr><td/><td>Parsimonious</td><td>-</td><td>1104</td><td>392</td><td>95.7%</td></tr><tr><td/><td>Bandits</td><td>50</td><td>1376</td><td>466</td><td>92.7%</td></tr><tr><td>0.03</td><td>DFO c -Cauchy(1 + 1)-ES</td><td>50</td><td>846</td><td>203</td><td>93,2%</td></tr><tr><td/><td>DFO c -DiagonalCMA</td><td>50</td><td>971</td><td>429</td><td>96,5%</td></tr><tr><td/><td>DFO c -CMA</td><td>50</td><td>911</td><td>404</td><td>96.7%</td></tr><tr><td/><td>DFO d -DiagonalCMA</td><td>50</td><td>799</td><td>293</td><td>94,1%</td></tr><tr><td/><td>Parsimonious</td><td>-</td><td>2104</td><td>1174</td><td>80.3%</td></tr><tr><td/><td>Bandits</td><td>50</td><td>2018</td><td>992</td><td>72.9%</td></tr><tr><td>0.01</td><td>DFO c -Cauchy(1 + 1)-ES</td><td>50</td><td>1668</td><td>751</td><td>72,1%</td></tr><tr><td/><td>DFO c -DiagonalCMA</td><td>50</td><td>1958</td><td>1175</td><td>79.2%</td></tr><tr><td/><td>DFO c -CMA</td><td>50</td><td>1921</td><td>1107</td><td>80.4%</td></tr><tr><td/><td>DFO d -DiagonalCMA</td><td>50</td><td>1188</td><td>849</td><td>71,3%</td></tr></table>

Adversarial attacks against an adversarially trained WideResnet28x10 network on CI-FAR10 dataset for = 0.03125 and 20, 000 as budget limit.

Table content: <table><tr><td/><td>Tile size</td><td/><td colspan="2">Avg queries</td><td colspan="3">Med. queries</td><td/><td>Succ. Rate</td></tr><tr><td/><td/><td>I</td><td>R</td><td>V</td><td>I</td><td>R</td><td>V</td><td>I</td><td>R</td><td>V</td></tr><tr><td>DFO c -Cauchy(1 + 1)-ES</td><td>30</td><td colspan="3">466 163 86</td><td>60</td><td>19</td><td>8</td><td colspan="2">95.2% 99.6% 100%</td></tr><tr><td>DFO c -Cauchy(1 + 1)-ES</td><td>50</td><td colspan="3">510 218 67</td><td>63</td><td>32</td><td>4</td><td colspan="2">97.3% 99.6% 99.7%</td></tr><tr><td>DFO c -DiagonalCMA</td><td>30</td><td colspan="5">533 263 174 189 95</td><td>55</td><td colspan="2">97.2% 99.0% 99.9%</td></tr><tr><td>DFO c -DiagonalCMA</td><td>50</td><td colspan="6">623 373 227 191 121 71</td><td colspan="2">98.7% 99.9% 100%</td></tr><tr><td>DFO c -CMA</td><td>30</td><td colspan="6">588 256 176 232 138 72</td><td colspan="2">98.9% 99.9% 99.9%</td></tr><tr><td>DFO c -CMA</td><td>50</td><td colspan="8">630 270 219 259 143 107 99.2% 100% 99.9%</td></tr><tr><td>DFO d -DiagonalCMA</td><td>50</td><td colspan="4">485 617 345 38</td><td>62</td><td>6</td><td colspan="2">97.4% 99.2% 99.6%</td></tr><tr><td>DFO d -DiagonalCMA</td><td>30</td><td colspan="4">424 417 211 20</td><td>20</td><td>2</td><td colspan="2">97.7% 98.8% 99.5%</td></tr></table>

Peer review (iclr2020):
This paper proposed a DFO framework to generate black-box adversarial examples. By comparing with Parsimonious and Bandits, the proposed approach achieves lower query complexity and higher attack success rate (ASR). I have two main concerns about the current version: 1) Some important baselines might be missing. In addition to (Ilyas et al., 2018b) and (Moon et al., 2019), the methods built on zeroth-order optimization (namely, gradient estimation via function differences) were not compared. Examples include [1] There are No Bit Parts for Sign Bits in Black-Box Attacks [2] AutoZOOM: Autoencoder-based Zeroth Order Optimization Method for Attacking Black-box Neural Networks [3] SIGNSGD VIA ZEROTH-ORDER ORACLE 2) In addition to attack success rate and query complexity, it might be useful to compare different attacks in terms of distortion, where . This could provide a clearer picture on whether or not the query efficiency and the attack performance are at the cost of increasing the and distortion significantly. ########### Post-feedback ############## Thanks for the response and the additional experiments to address my first question. However, I am not satisfied with the response *But clearly our methods aim to reach the boundary of linf ball, so the distortion might be large* to the second question. I am Okay with the design of attack. However, if the reduction in query complexity is at a large cost of perturbation power, e.g., measured by norm, then it is better to demonstrate this tradeoff. Furthermore, if the norm is constrained, will the proposed attack outperform the others? This is also not clear to me. Thus, I decide to keep my score.