Yet another but more efficient black-box adversarial attack: tiling and evolution strategies
Authors: Laurent Meunier
Jamal Atif
Olivier Teytaud
Venue:  (2020)
Keywords: adversarial examples
black-box attacks
derivative free optimization
deep learning

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 $\ell_\infty$-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.

Under review as a conference paper at ICLR 2020
YET ANOTHER BUT MORE EFFICIENT BLACK-BOX ADVERSARIAL ATTACK: TILING AND EVOLUTION STRATEGIES
Anonymous authors Paper under double-blind review
ABSTRACT
We introduce a new black-box attack achieving state of the art performances. Our approach is based on new objective function, borrowing ideas from -white box attacks, and particularly designed to fit derivative-free optimization require- ments. It only requires to have access the logits of the classifier without any other information which is 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-fiee freee 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 budget lim- ited to 10, 000 queries, results up to 99.2% of success rate against Inception V3 classifier with 630 queries the network on average in the untargeted attacks ting, which an improvement by 90 queries of the current state of the art. In the targeted setting, success rate with budget of 6, 662 queries on average, i.c. we need 800 queries less than the current state of the art.
able reach, with limited budget of 100, 000, 100% of
INTRODUCTION
Despite their success, deep learning algorithms have shown vulnerability to adversarial attacks (Big- gio al. 2013) Szegedy et al.] (0044) i.e. small imperceptible perturbations of the inputs, that lead the networks to misclassity the generated adversarial examples. Since their discovery, adversarial attacks and defenses have become one of the hottest research topics in the machine learning commu- nity 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 eet al. 2016, (inha et al., 2017: Cohen et al., 2019] Pinot et al. (019)) and experimentally (Good- fellow 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 gap come up with principled guarantees on the robustness of neural networks against maliciously crafted at- tacks. 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
al. 2013; Kurakin et al. 2016 Carlini & Wagner 2017; MMooavvi-Dezoool et al. 2016). This case is unrealistic because the attacker has only limited access the network in practice. For instance, web services that propose commercial recognition systems such as Amazon or Google are backed by pretrained neural networks. 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 more realistic but or logits. Such a setting is coined in the literature as the black box setting. also more challenging from the attacker's standpoint.
As a consequence, several works proposed black box attacks by just querying the inference results of 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 (Pa- pernot al. 2016a). In this case, white box attack is crafted on fully known classifier. Paaperot

---

Under review as a conference paper at ICLR 2020
et al. 2017) exploited this property 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: Tyas et al. 2018a b). For these attacks, the PGD attack (Kurakin et al. 2016 Madry et al.
201 8a 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 limited number of queries while outperforming the state of the 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 fx 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 the related work on adversarial attacks. Section presents the core of our approach. We introduce practical instantiations leading to a discrete and a continuous optimization problems. We then give more details 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 analy- sis, where show reach state of the art performances by comparing 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
generic objective function and discuss two
models with the most
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 al. (2014) revives this research topic by highlighting that deep convolu- tional 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 back-propagating the gradient of the loss function w.r.t. the input. The problem writes aims at minimizing its norm. Among the most popular ones, one can cite FGSM (Goodfellow et al.] 2015), PGD (Kurakin al. 20166; Madry al. 2018a), Deepfool (Moosavi-Dezfool et al.) (016). ISMA (Papernot et al. 2016b). Carlini& Wagner attack (Carlini & Wagner 2017) and EAD (Chen al. 2018).
non-convex optimization procedure that either constraints the perturbation or
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 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.c. net- work trained on the same classification task. This crafted adversarial example can be transferred to the targeted unknown network. Leveraging this property, Moosavi-Deziooli 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 methodss/Chenn
methods. Chen et al. (2017) proposed variant of the powerful white-box attack introduced in (Car-) lini & Wagner 2017), based on gradient estimation with finite differences. This method achieves good results in practice but requires high number of queries to the network. To reduce the number of queries, Iyas 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-
2

---

Under review as a conference paper at ICLR 2020
ima of given objective function. This amounts for most of NES algorithms to perform natural gradient descent in the space of distributions (Ollivier et al. 2017). In (Al-Dujaili & O 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, stud- ied 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 intro- duce the AutoZOOM framework combining gradient estimation and an auto- auto-encoder trained offline with unlabeled data. The idea is appealing but requires training an auto-encoder with 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 fx 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 net- works accuracies. A basic workaround, introduced in (Goodfellow et al.) 2015), is 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 fully defend the network, and lacks theoret- ical guarantees, in particular principled certificates. Defenses based on randomization at inference
time were also proposed (Lecuyer al. 2018, Cohen et al. 2019 Pinot et al. 2019). These meth- ods 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.
METHODS
3.1 GENERAL FRAMEWORK
Let us consider a classification task X' + [K] where X C Rd is the input space and [K] {I, (I.,K,,, is the corresponding label set. Let f : Rd + R be a classifier (a feed forward neu- ral network in our paper) from input space X returning the logits of cach label in [K] such that the predicted label for a given input is arg max;e[k] fe(x). The aim of -loude- un- targeted adversarial attacks is, for some input with label y, to find perturbation such that arg max f((x)) + y. Classically, Hilloo-bounde untargeted adversarial attacks aims at optimiz- ing the following objective:
max Te
L(S(x + 7),
(1)
where loss function (typically the cross entropy) and y the true label. For targeted attacks, the attacker targets label yr by maximizing (f +T) Vt). 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 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 RRd, In the t-o bounded adversarial attacks setting, the search space is (c) = (r || I c). It requires to adapt the problem in Eq Two variants are proposed in the sequel leading to continuous and discretized versions of the problem.
The continuous problem. As in InrCllim & Wagner (207)) we use the hyperbolic tangent transfor-
mation to restate our problem since (e) = tanh (. This leads to continuous search space
on which evolutionary strategies apply. Hence our optimization problem writes:
max L(f(z ( etanh(T)). TER4
(2)
3

---

Under review as a conference paper at ICLR 2020
We will call this problem DFO, -optmmizrr 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 bo They consider optimizing the following
max L(f(x + 7),9).
(3)
rE(-c,te)4
The author in (Moon al. 2019) proposed purely discrete combinatorial optimization 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 compliant with our evolutionary strategies setting, we rewrite our problem by considering a
Eq. 3
e stochastic function far + eт) where, for all i, Ti E {-1,+1} and P(T, 1) = Softmax(a, b,) Hence our problem amounts find the best parameters a, and b; that optimize:
te
min Bin. (L(((x + eT),
(4)
a,b
We then rely on evolutionary strategies to find the parameters a and b. As the optima are determinis- tic, 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, optimizer where optimizer the used black box derivative free optimization strategy for a and In this case, one could re- duce the problem to one variale with IP 1) Ite-ag but experimentally the results are comparable, so we concentrate on Problem
3.3 DERIVATIVE-FRES OPTIMIZATION METHODS
Derivative- optimization methods are aimed optimizing an objective function without access to the gradient. There exists 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 the value of f(x). As evaluating can be computationally expensive, the purpose DFO methods is to get a good approximation of the optima using& moderate number of queries. We tested several evolution strategies (Rechen- berg 1973 Beyer 200T): the simple (1 + g-argthi (Matyas 1965 Schumer & Steiglitz 1968). Covariance Matrix Adaptation (CMA (Hansen & Ostermeier 2003)). For these methods, the un- derlying algorithm is to iteratively update some distribution Pa defined on X. Roughly speaking, the current distribution Fe 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.I other tested methods.
we refer to references above for
3.3.1 OUR BEST PERFORMING METHODS: EVOLUTION STRATEGITS
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 sup- plementary material, Alg. D 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 (996) proposed the use of Cauchy distributions instead of classical Gaussian sampling. This favors large steps, and improves the results in case of (possibly partial) separabil- ity 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 & Oster- meier 2003) combines evolution strategies (Beyer) 2001). Cumulative Step-Size Adaptation (Arnold & Beyer, 2004), and 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 the square root of the matrix. As 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.
4

---

Under review as a conference paper at ICLR 2020
The panks
0.03x
Figure 1: Illustration of the tiling trick: the same noise is applied on small tile squares.
Link with Natural Evolution Strategy (NES) attacks. Both (1+1)-ES and CMA-ES can be seen as an instantiation of a natural evolution strategy (see for instance Ollivier et al. (2017): Wierstra et al.) (2014)). A natural evolution strategy consists in estimating iteratively the distribution of the optima. For most NES approaches, 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 NES, where the covariance matrix is restricted to be proportional 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 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 be good adversarial candidates; however, for high precision attacks (with small r) a smooth continuous precision (Eq 2p more relevant. With or without softmax, the optimum is infinity [1]
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., (012)) has shown how fast is the adaptation of the step-size when using cumulative step-size adaptation (as in CMA-ES),
opposed to slower rates for most methods. Cauchy sampling (Yao Liu 1996) the (1 + 1)-ES known for favoring fast changes; this 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 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 Diagonal CMA-ES which adapt 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 number of queries (rather than a time budget) it is however optimal for high precision.
3.4 THE TILING TRICK
Ilyas et al. (0188) suggested tile the attack 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 the image (see Fig. I. 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 dimensionality. tiling leads surprisingly tiling scale, convolutional neural networks are not robust to random noise. Section 4.2 devoted to this intriguing property. Interestingly enough, initializing optimization algorithms with a tiled noise at the appropriate scale drastically speeds up the convergence, leading to a reduced number of queries.
new property that we discovered during experiments. At given
lie. the optima of the ball constrained problem would be close to the boundary or on the boundary of the for hall. In that case, the optimum of the continuous problem 2 will be at or close to it. On the discrete case 4 it easy see that the optimum is when a, b; co.

---

Under review as a conference paper at ICLR 2020
Attack inception/3 architecture
Attack surcess for em 0.05 with different architetures versus the number tiles
with different noise infensities versus the number tile
2.03
0.5
ResNett3
2.08
Incepiler/33
5.06
VC218on
5.3
0.4
2400055
0.3
0.3-
0.1
0.9
100
150
200
0
30
100
150
200
Namber of Bile
Number
Figure 2: Success rate of single shot random attacks on ImageNet vs. the number of tiles used to craft the attack. On the left, attacks are plotted against Inception classifier with different noise intensities (e {0.01, 0.03, 0.05, 0.1}). On the right, is fixed to 0.05 and the single shot attack is evaluated on Inception V3, ResNet50 and VGG16bn.
4 EXPERIMENTS
4.1 GENERAL SETTING AND IMPLEMENTATION DETAILS
We compare our approach the "bandits" method (yyas al. 2018b) and the parsimonious at- tack (Moon et all] 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 foo ones. We use the large-scale ImageNet dataset (Deng et al. 2009). As usually done in most frame- works, 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 classifier for a given image. For the success rate, we only consider the images that were correctly classified by our model. We use Inception (Szegedy et al. (017)_ VGG16 (Simonyan & Zisserman, 2014) with batch normalization (VGG16bn) and ResNet50 (He et al. 2016) architectures to measure the performance of our algorithm 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 normalized to [0, 1]- Results on VGG16bn and ResNet50 are deferred in supplementary material F The images to be attacked are selected at random.
We first show that convolutional networks are not robust to tiled random noise, and more sur- prisingly that there exists an optimal tile size that is the same for all architectures and noise in- tensities. Then, we evaluate our methods on both targeted and untargeted objectives. We con- sidered the following losses: the cross entropy L(f(x),))
(1)()()))))) and a loss inspired from the "Carlini& Wagner" attack: L(f(z). y) = -P(y)x) + max zy P( (x) where P(y]æ) = [Softmax(f[x:))
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 Never- grad (Rapin & Teytaud| (0188) 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 too 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 randomly chosen constant noise: +e with probability 1 and - with probability 2. uniformly on the tile. The tile trick has been introduced inllyas et al. (201 8a) for dimensionality reduction. Here we exhibit new behavior that we discovered during experiments. As shown in Fig. for reasonable noise intensity (e = 0.05). the success rate of a one shot randomly tiled attack is quite high. This fact is observed many neural network architectures. We compared the

---

Under review as a conference paper at ICLR 2020
Cumu we saccess net terms
Aemueelize success rate berme
Orninanu
1.-
Continaa OMA,50
68
Ortznnnc Olegeaali
suttmaus caality (11 to
Disceta Dig ougonelii 26
0.2
02
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 logarithmic scale.
Figure 3:
Table I:
Comparison of our method with the parsimonious and bandits attacks in the untargeted setting ImageNet on Inception pretrained network for 0.05 and 10, 000 budget limit.
Method
# of tiles
Average queries
Median queries
Success rate
Parsimonious
702
222
98.4%
Bandits
30
1007
269
95.3%
Bandits
50
995
249
95.1%
DFO.- Cauchy 1)-ES
30
466
60
95.2%
DFO, Cauchy(1 + 1)-ES
50
510
63
97.3%
DFO, DiagonalCMr CMAA
30
533
189
97.2%
DFO, Diagonal
50
623
191
98.7%
DFO.- CMA
30
589
232
98.9%
DFO, CMA
50
630
259
99.2%
DFO.. DiagonalCMA
30
424
20
97.7%
DFO Dia
50
485
38
97.4%
number of tiles since the images input size are not the same for all architectures (299 x 299 x 3 for Inception and 224 224 3 for VGG16bn and ResNet50). The optimal number tiles (in the sense of attack success rate) is, surprisingly. independent from the architecture and the noise intensity. We also note that the Inception architecture is more robust random tiled noise than VGG 6bn and ResNet50 architectures. Inception V3 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 single random attack with various numbers of tiles (cf. Figure 2). We plotted additional graphs supplementary material
4.3 UNTARGETED ADVERSARIAL ATTACKS
We first evaluate our attacks in the untargeted setting. The aim is to change the predicted label 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 and 50 tiles on the images. Only the best performing methods are reported in Table [ We compare our results with (Moon et al. (219) and (Ilyas al. 2018b) on Inception V3 (cf. Table []. We also plotted the cumulative success rate in terms of required budget in Figure 3 We also evaluated our attacks for smaller noise 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 random

---

Under review as a conference paper at ICLR 2020
Table 2: Comparison of method with the parsimonious and bandits attacks in the targeted setting on ImageNet on InceptionV3 V3 pretrained network for = 0.05 and 100, 000 as budget limit.
Method
# of tiles
Average queries
Median queries
Success rate
Parsimonious
7184
5116
100%
Bandits
50
25341
18053
92.5%
DFO, Cauchy( + 1)EES
50
9789
6049
83.2%
DFO, DiagonalCMA
50
6768
3797
94.0%
DFO, CMA
50
6662
4692
100% %
DFO - DiagonalCMA
50
8957
4619
64.2%
search and hence, according to the observation of Figs 2 the first steps are more likely fool the network, which explains why the queries budget remains low. This Discrete strategies reach better median numbers of queries which is consistent
directly search the limits of the & -bal;; however, given the restricted search space (only corners of the search space are considered), the success rate is lower and 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, set the maximum budget to 100, 000 queries, and = 0.05. We uniformly chose the target class among the incorrect ones. We evaluated parsimonious attack (Moon et al. 2019) on Inception V3 classifier. We also plotted the cumulative success rate terms of required budget Figure CMA-ES beats the state of the art 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 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.
attacks in comparison with the bandits methods (Ilyas al. 2018b) and the
4.5 UNTARGETED ATTACKS AGAINST AN ADVERSARIALLY TRAINED NETWORK
In this section, we experiment our attacks against defended network by adversarial training (Good-) Tellow al., 2015). Since adversarial training is computationally expensive, we restricted ourselves to the CIFARIO dataset (Krizhessky et al. 2009) for this experiment. Image size is 32 32 x 3. We adversarially trained a WideResNet28xx
(Zagoruyko Komodakis 2016) with PGD Eo tacks (Kurakin al. 2016 Madry et al. 2018a) of norm 8/256 and 10 steps of size 2/256. In this setting, we randomly selected 000 images, and limited the budget to 20, 000 queries. We ran PGD lo attacks (Kurakin et al. 2016 Madry al. 2018a Sa) of norm 8/256 and 20 steps of size 1/256 against our network, and achieved success rate up to 36%, which the the state the art in the white box setting. We also compared our method the Parsimonious and bandit attacks. Results are reported in Appendix On this task, the parsimonious attack method is slightly better than our best approach.
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 prob- lem (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, CMA improves the state of the art in terms success rate in almost all settings. We also validated the adversarially trained network. Future work will be devoted to
robustness of our attack against better understanding the intriguing property of the effect that a neural network is not robust to a one shot randomly tiled attack.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Abdullah Al-Dujaili and Una-May O' O'Reilly. There are no bit parts for sign bits in black-box attacks, 2019.
Alexandre Araujo, Rafael Pinot, Benjamin Negrevergne, Laurent Meunier, Yann Chevaleyre, Florian Yger, and Jamal Atif. Robust neural networks using randomized adversarial training. arXiv preprint arXiv: /903. 102 19, 2019.
Dirk V. Amold and Hans Hans-Georg Beyer. Performance analysis evolutionary optimization with cumulative step length adaptation. IEEE Trans. Automat. Contr., 49(4))617-622 2004.
Irwan Bello, Barret Zoph, Vijay Vasudevan, and Quoc V. Le. Neural optimizer search with reinforce- ment learning. In Proc. of the 34th International Conference on Machine Learning, volume 70 of ICML'11, 17, pp. 459-468, 2017.
Heor- Beyer. The Theory of Evolution Strategies. Natural Computing Series. Springer, Hei- deberg, 2001.
Battista Biggio, Giorgio Fumera, and Fabio Roli. Evade hard multiple classifier systems. In Appli- cations of Supervised and Unsupervised Ensemble Methods, pp. 15-38. Springer, 2009.
Battista Biggio, Igino Corona, Davide Maiorca, Blaine Nelson, Nedim Smdii Pavel Laskov, Gior- gio Giacinto, and Fabio Roli. Evasion attacks against machine learning at test time. Joint European conference machine learning and knowledge discovery in databases, pp. 387-402. Springer, 2013.
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In 2017 IEEE Symposium Security and Privacy (SP), pp. 39-57. IEEE, 2017
Pin-Yu Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsich. Zoo: Zeroth order opti- mization based black-box attacks to deep neural networks without training substitute models. In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, pp. 15-26. ACM, 2017.
Pin-Yu Yu Chen, Yash Sharma, Huan Zhang, Jinfeng Yi, and Cho-Jui Hsieh. Ead: elastic-net attacks to deep neural networks via adversarial examples. In Thirty-second AAAI conference on artificial intelligence, 2018.
Alexandre Chotard, Anne Auger, and Nikolaus Hansen. Cumulative step-size adaptation linear functions. In Carlos A. Coello Coello, Vincenzo Cutello, Kalyanmoy Deb, Stephanie Forrest, Giuseppe Nicosia, and Mario Pavone (eds.), Parallel Problem Solving from Nature PPSN XII, pp. 72-81, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg. ISBN 978-3-642-32937-1
Jeremy M. Cohen, Elan Rosenfeld, and J. Zico Kolter. Certified adversarial robustness via ran- domized smoothing. CoRR, httss/992.0299 2019. /Rt/:http.///arxi..o///////////
02918
J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei. ImageNet: A Large-Scale Hierarchical Image Database. In CVPR09, 2009.
Alhussein Fawzi, Seyed-Mohsen from adversarial random noise. In Advances Neural Information Processing Systems, pp. 1632-1640, 2016.
and Pascal Frossard. Robustness of classifiers:
Ian Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In International Conference on Learning Representations, 2015.
N. Hansen and A. Ostermeier. Completely derandomized self-adaptation in evolution strategies. Evolutionary Computation, 11(1), 2003.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.

---

Under review as a conference paper at ICLR 2020
Andrew Ilyas, Logan Engstrom, Anish Athalye, and Jessy Lin. Black-box adversarial attacks with limited queries and information. arXiv preprint arXiv:1804.08399, 2018a.
Andrew lyas, Logan Engstrom, and Aleksander Madry. Prior convictions: Black-box adversarial attacks with bandits and priors. arXiv preprint arXiv:1807.07978, 2018b.
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cifar-10 and cifar-100 datasets. https://www. cs. toronto. edu/kriz/cifar. html, 6, 2009.
URI:
Alexey Kurakin, Ian Goodfellow, and Samy Bengio. Adversarial examples in the physical world. 2016.
arXiv preprint
M. Lecuyer, V. Atlidakis, Geambasu, D. Hsu, and S. Jana. Certified robustness to adversarial examples with differential privacy. In 2019 IEEE Symposium on Security and Privacy (SP), pp- 727-743, 2018.
Sijia Liu. Pin-Yu Yu Chen, Xiangyi Chen, and Mingyi Hong. signSGD via zeroth-order oracle. In International Conference on Learning Representations, 2019. URL [tL[ttts://///eeeee/// Settorummid=JJ--DsCC..
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, 2018a
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, 2018b.
J. Matyas. Random optimization. Automation and Remote control, 26:246-253, 1965.
Dongyu Meng and Hao Chen. Magnet: a two-pronged defense against adversarial examples. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pp. 135 147. ACM, 2017.
Seungyong Moon, Gaon An, and Hyun Oh Song. Parsimonious black-box adversarial attacks via efficient combinatorial optimization. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceed- ings of Machine Learning Research, pp. 4636-4645, Long Beach, California, USA, 09-15 Jun 2019. PMLR.
mir www.erssss.ppp..oo.o...........e https//v//mooooooo 9a. (atoon19ahhtml html
Seyed-Mohsen Moosavi- Moosavi-Dezffolli, Alhussein Fawzi, and Pascal Frossard. Deepfool:
simple and accurate method to fool deep neural networks. In Proceedings of the IEEE Conference Com- puter Vision and Pattern Recognition, pp. 2574-2582, 2016.
Seyed-Mohsen Moosavi-Dezfooli, Alhussein Fawzi, Omar Fawzi, and Pascal Frossard. Universal adversarial perturbations. In 2017 IEEE Conference Computer Vision and Patlern Recognition (CVPR), pp. 86-94. Icce, 2017.
Yann Ollivier, Ludovic Arnold, Anne Auger, and Nikolaus Hansen. Information -eommtrii opti- mization algorithms: A unifying picture via invariance principles. J. Mach. Learn. Res., 18: 18:1-18:65, 2017. URL http::///.mm...orr///ppp////////
4hmmmmml
Nicolas Papernot, Patrick McDaniel, and Ian Goodfellow. Transfcrability in machine learning: from phenomena to black-box attacks using adversarial samples. arXiv preprint 1XXi:1665.00277
2016a.
Nicolas Papernot, Patrick McDaniel, Somesh Jha, Matt Fredrikson. Z Berkay Celik, and Ananthram Swami. The limitations of deep learning in adversarial settings. In Security and Privacy (Eu- roS&P) P), 2016 IEEE European Symposium on, pp. 372-387. IEEF, 2016b.
Nicolas Papernot, Patrick McDaniel, Ian Goodfellow, Somesh Jha, Z. Berkay Celik, and Ananthram Swami. Practical black-box attacks against machine learning. In Proceedings of the 2017 ACM Asia Conference on Computer and Communications Security, ASIA CCS '17. pp. 506-519, New York, NY, USA, 2017. ACM. ISBN 978-1-4503-4944444 doi: 10.1 10.11457355277333330099 URL http: //:::///0 acm. httm.oo//....11533552231013
10

---

Under review as a conference paper at ICLR 2020
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary Vitito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. 2017.
Rafael Pinot, Laurent Meunier, Alexandre Araujo, Hisashi Kashima, Florian Yger, Cédric Gouy- Pailler, and Jamal Atif. Theoretical evidence for adversarial robustness through randomization: the case of the exponential family. arXiv preprint arXiv:1902.011465 2019.
Rapin and O. Teytaud. Nevergrad A gradient-free free optimization platform. https: 2018.
com/ Faccchooooeeeearccheeeeeeeeeeeee
I. Rechenberg. Evolutionsstrategie: Optimierung Technischer Systeme nach Prinzipien des Biologis- chen Evolution. Fromman- Fromman-Holzboog Verlag, Stuttgart, 1973.
Raymond Ros and Nikolaus Hansen. A simple modification in cma-es achieving linear time and space complexity. In Günter Rudolph, Thomas Jansen, Nicola Beume, Simon Lucas, and Carlo Poloni (eds.), Parallel Problem Solving from Nature - PPSN X, pp. 296-305, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg. ISBN 978-3-540-87700-4
Pouya Samangouei, Maya Kabkab, and Rama Chellappa. Defense-GAN: Protecting classifiers against adversarial attacks using generative models. In International Conference Learning Representations, 2018.
M. Schumer and K. Steiglitz. Adaptive step size random search, Automatic Control, IEEE Transac- fions on, 13:270-276, 1968.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv:1409.1556 2014.
Aman Sinha, Hongseok Namkoong, and John Duchi. Certifying some distributional robustness with principled adversarial training. arXiv preprint arXiv: 10571, 2017.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfel- low, and Rob Fergus. Intriguing properties of neural networks. In International Conference Learning Representations, 2014.
Christian Szegedy, Sergey loffe, Vincent Vanhoucke, and Alexander A Alemi. Inception-v4, inception-resnet and the impact of residual connections on learning. In Thirty-First AAAI Confer- ence on Artificial Intelligence, 2017.
Chun-Chen Tu, Paishun Ting, Pin-Yo Chen, Sijia Liu, Huan Zhang, Jinfeng Yi, Cho-Jui Hsich, and Shin-Ming Cheng. Autozoom: Autoencoder- zeroth order optimization method for attack- ing black-box neural networks. In Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pp. 742-749, 2019.
Daan Wierstra, Tom Schaul, Tobias Glasmachers, Yi Sun, Jan Peters, and Jürgen Schmidhuber. Natural evolution strategies. The Journal of Machine Learning Research, 151))999-998, 2014.
Cihang Xie, Jianyu Wang, Zhishuai Zhang, Zhou Ren, and Alan Yuille. Mitigating adversarial effects through randomization. In International Conference on Learning Representations, 2018
Xin Yao and Yong Liu. Fast evolutionary programming. In Proceedings of the Fifth Annual Confer- ence on Evolutionary Programming, pp. 451-460 MIT Press, 1996.
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. In Edwin R. Hancock Richard C. Wilson and William A. P. Smith (eds.). Proceedings of the British Machine Vision Conference (BMVC), pp. 87.1-87. 87.12. BMVA Press, September 2016. ISBN 1000775--5-6 doi: 10.5244/C. 30.87.
11

---

Under review as a conference paper at ICLR 2020
A ALGORITHMS
A.1 THE (1+1)-ES ALGORITHM
Algorithm The (1 (1+1) 1) Evolution Strategy.
Require: Function f: [R4 < 0, C < Id. <- 1 for t 1...n do (Generate candidates) Generate m' ~ m + a X where X is sampled from Cauchy or Gaussian distribution.
I to minimize
if f(m') S fmm then m + m. t 20
else
σ t- 2 end if
end for
A.2 CMA-ES ALGORITHM
Algorithm 2 CMA-ES algorithm. The T subscript denotes transposition.
Require: Function f: Rd IR to minimize, parameters b, ..... wp > 0, Pe and others as in e.g. (Hansen Ostermeier 2003).
m < 0,C la. for t = 1...n do
Generate Ti, 2x
(O,
Define z the 8th best of the Tz.
Update the cumulation for C: Pe cumulation of Pc, overall direction of progress.
Update the covariance matrix:
C r
c) C +
(pe x Pe
+c(1
W/s m
2
(3r m)
inertia
overall direction
"covariance" of the Jar
Update mean:
Update a by cumulative step-size adaptation Armold Beyer 2004).
end for
12

---

Under review as a conference paper at ICLR 2020
B ADDITIONAL PLOTS FOR THE TILING TRICK
Figure 4: Random attack success rate against Inception (left), ResNet50 (center), VGG16bn (right) for different noise intensities. We just randomly draw one tiled attack and check if it is successful.
Adack
Figure 5: Random attack success rate for different noise intensities e {0.01, 0.03, 0.05, 0.13 (from right left) against different architectures. We just randomly draw one tiled attack and check if is successful.
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& "Carlini&Wagner" loss instead of the cross entropy. We remark the results are comparable and similar.
Table 3: Comparison of our method Cith"Carlini& Wagner" loss versus the parsimonious and bandits attacks in the untargeted setting on Inception pretrained network for 0.05 and 10, 000 as budget limit.
Method
# of tiles
Average queries
Median queries
Success rate
DFO,- - Cauchy( 1) 1E
30
353
57
97.2%
DFO, Cauchy( 1)-ES
50
347
63
98.8%
DFO, DiagonalCM.
30
483
167
98.8%
DFO,- - Dia
50
528
181
99,2%
DFO, CMA
30
475
225
99,2%
DFO, CMA
50
491
246
99.4%
DFO,, DiagonalCMA
30
482
98.0%
DFO DiagonalCMA
50
510
37
98.0%
13

---

Under review as a conference paper at ICLR 2020
D UNTARGETED ATTACKS WITH SMALLER NOISE INTENSITIES
We evaluated our method on smaller noise intensities (c E {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. 20188) and the parsimonious attack (Moon al. 2019) on Inception V3 network. We limited our experiments to number of tiles of 50. We report our results in Table 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, reach results comparable to the state of the art.
Table 4: Results of our method compared to the parsimonious and bandit attacks in the un- targeted setting on InceptionV3 pretrained network for different values of noise intensities {0.01, 0.03, 0.05} and maximum of 10, 000 queries.
Method
of tiles
Avg. queries
Med. queries
Success rate
Parsimonious
722
237
98.5%
Bändfts
30
995
249
95.1 %
0.05
DFO, Cauchy(1 11 + 1)-ES
50
510
63
97.3%
DFO, c Diagonal CCMA
50
623
191
98.7%
DFO, - CMA
50
630
259
99.2%
DFO, DiagonalCMA
50
485
38
97.4%
Parsimonious
1104
392
95.7%
Bandits
50
1376
466
92.7%
0.03
DFO Cauchy (1 7 +1-ES
50
846
203
93.2%
DFO,
DCa
50
971
429
96,5%
DFO.- CMA
50
911
404
96.7%
DFO, DiagonalCMA
50
799
293
94,1%
Parsimonious
2104
1174
80.3%
Bandits
50
2018
992
72.9%
0.01
DPO, (a +1J-ES
50
1668
751
72,1%
DFO. DiagonalCMA
50
1958
1175
79.2%
DFO,- CMA
50
1921
1107
80.4%
DFO,- DiagonalCMA
50
1188
849
71,3%
14

---

Under review as a conference paper at ICLR 2020
E UNTARGETED ATTACKS AGAINST OTHER ARCHITECTURES
We also evaluated our method on different neural networks architectures. For each network we randomly selected 000 images that were correctly classified. We limit our budget 10, 000 queries and set the number of tiles to 50. We achieve 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 One should notice that the performances are lower on Inception as it is also reported for the bandit methods (llyas et al., 2018b). This possibly due to the fact that the tiling trick less relevant on the Inception network than on the other networks (see Fig.
Table 5: Comparison of our method on the ImageNet dataset with Inception V3 (I), ResNet50 (R) and VGG16bn (V) for 0.05 and 10, 000 as budget limit.
Method
Tile size
Avg queries
Med. queries
Suce. Rate
R
V
R
V
R
V
DFO. Cauchy
ES
30
466
163
86
60
19
8
95.2%
99.6%
100%
DFO, Cauchy 1)-ES
50
510
218
67
63
32
4
97.3%
99.6%
99.7%
DFO, DiagonalCMM ICMA
30
533
263
174
189
95
55
97.2%
99.0%
99.9%
DFO,- DiagonalCMA
50
623
373
227
191
121
71
98.7%
99.9%
100%
DFO, -MA CMA
30
588
256
176
232
138
72
98.9%
99.9%
99.9%
DFO, CMA
50
630
270
219
259
143
107
99.2 %
100%
99.9%
DFO - Diagonal
50
485
617
345
38
62
6
97.4%
99.2%
99.6%
DFO, DiagonalCMA
30
424
417
211
20
20
2
97.7%
98.8%
99.5%
15

---

Under review as a conference paper at ICLR 2020
F
TABLE FOR ATTACKS AGAINST ADVERSARIALLY TRANINED NETWORK
Table 6: Adversarial attacks against an adversarially trained WideResnet28x network on CI-
FARI0 dataset for 0.03125 and 20, 000 budget limit.
Method
# of tiles
Average queries
Median queries
Success rate
PGD (not black-box)
20
20
36%
Parsimonious
I130
450
42%
Bandits
10
1429
530
29.1%
Bandits
20
1802
798
33.8%
Bandits
32
1993
812
34.8%
DFO, Cauchy + I--ES 1S
10
429
60
29.5%
DFO. Cauchy -ES
20
902
93
30.5%
DFO,- Cauchy 1EES
32
1865
764
31.7%
DFO. DiagonalCMAA
10
395
85
30.5%
DFO, DiagonalCMA
20
624
151
31.3%
DFO, DiagonalCMA
32
1379
860
34.7%
DFO. -CMA
10
363
156
30.4%
DFO, CMA
20
1676
740
40.2%
DFO, CMA
32
2311
1191
40.2%
16

---

Under review as a conference paper at ICLR 2020
G FAILING METHODS
In this section, we compare our attacks to other optimization strategies. We run our experiments in the same setup in Section 4.3 Results are reported in Table DE and Normal (I+I>ES performs poorly, probably because these optimization strategies converge slower when the optima are at "infinity"" We reformulate this sentence accordingly in the updated version of the paper. Finally, as the initialization of Powell is linear with the dimension and with less variance, it performs poorer than simple random search. Newuoa, SQP and Cobyla algorithms have also been tried on smaller number images (we did not report the results), but their initialization is also linear in the dimension, so they reach very poor results too.
Table Comparison with other DFO optimization strategies in the untargeted setting on ImageNet dataset InceptionV3 V3 pretrained network for 0.05 and 10, 000 as budget limit.
Method
# of tiles
Average queries
Median queries
Success rate
DFO, Cauchy 1)-ES
30
466
60
95.2%
DFO, Cauchy(1 1)-ES
50
510
63
97.3%
DFO, DiagonalCMA
30
533
189
97.2%
DFO, DiagonalCMA
50
623
191
98.7%
DFO,- CMA
30
589
232
98.9%
DEO, CMA
50
630
259
99.2%
DFO, DE
30
756
159
78.8%
DFO, DE
50
699
149
76.0%
DFO, Normal(1 1J-ES
30
581
87.6%
DFO,- Normal(1 + 1)-ES
50
661
66
92.8%
DFO, KandomSearch
30
568
37.9%
DFO, RandomSearch
50
527
5
38.2%
DFO, r Powell
30
4889
5332
14.4%
DFO Powell
50
4578
4076
7.3%
17


Reviews:
[{"review_id": "rkxAlx2iKS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposed a new query efficient black-box attack algorithm using better evolution strategies. The authors also add tiling trick to make the attack even more efficient. The experimental results show that the proposed method achieves state-of-the-art attack efficiency in black-box setting.\n\nThe paper indeed presented slightly better results than the current state-of-the-art black-box attacks. It is clearly written and easy to follow, however, the paper itself does not bring much insightful information. \n\nThe major components of the proposed method are two things: using better evolution strategies and using tiling trick. The tiling trick is not something new, it is introduced in (Ilyas et al., 2018) and also discussed in (Moon et al., 2019). The authors further empirically studied the best choice of tiling size. I appreciated that, but will not count it as a major contribution. In terms of better evolution strategies, the authors show that (1+1) and CMA-EA can achieve better attack result but it lacks intuition/explanations why these helps, what is the difference. It would be best if the authors could provide some theories to show the advantages of the proposed method, if not, at least the authors should give more intuition/explanation/demonstrative experiments to show the advantages.\n\nDetailed comments:\n- In section 3.2, is the form of the discretized problem a standard way to transform from continuous to discrete one? What is the intuition of using a and b? Have you considered using only one variable to do it?\n- In section 3.3.2 what do you mean by “with or without softmax, the optimum is at infinity”? I hope the authors could further explain it.\n- In eq (2), do you mean  max_{\\tau} L(f(x + \\epsilon tanh(\\tau)), y) ?\n- In section 3.3.1, the authors said (1+1)-ES and CMA-ES can be seen as an instantiation of NES. Can the authors further elaborate on this?\n- Can the authors provide algorithm for DiagonalCMA?\n- It is better to put the evolution strategy algorithms in the main paper and discuss it. \n- Can the authors also comment/compare the results with the following relevant paper?\nLi, Yandong, et al. \"NATTACK: Learning the Distributions of Adversarial Examples for an Improved Black-Box Attack on Deep Neural Networks.\" ICML 2019.\nChen, Jinghui, Jinfeng Yi, and Quanquan Gu. \"A Frank-Wolfe Framework for Efficient and Effective Adversarial Attacks.\" arXiv preprint arXiv:1811.10828 (2018).\n\n-  In Table 1, why for Parsimonious and Bandit methods, # of tiles parts are missing? I think both of the baselines use tilting trick? And they should also run using the optimal tiling size? The result seems directly copied from the Parsimonious paper? It makes more sense to rerun it in your setting and environment cause the sampled data points may not be the same. Since CMA costs significantly more time, it makes a fair comparison to also report the attack time needed for each method.\n\n- In Table 3, why did not compare with Bandit and Parsimonious attacks? \n\n======================\nafter the rebuttal\n\nI thank the authors for their response but I still feel that there is a lot more to improve for this paper in terms of intuition and experiments. Therefore I decided to keep my score unchanged.  \n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "SkgdbG96KH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a black box adversarial attacks to deep neural networks. The proposed approaches consist of tiling technique proposed by Ilyas et al (2018) and derivative free approaches. The proposed approaches have been applied to targeted and untargeted adversarial attacks against modern neural network architectures such as VGG16, ResNet50, and InceptionV3 trained on ImageNet and CIFAR10 datasets. Experimental results show higher attack success rate with a smaller number of queries. \n\nThe experimental results look quite promising, i.e., revealing the vulnerability of the deep neural network against black-box adversarial attacks. A possible weakness in the experimental design is that the authors haven't apply any defense methodology to the classification models to be attacked. Yet the results are promising. \n\nFrom the viewpoint of technical soundness, the approach is a simple combination of the existing approaches. The tiling technique is used in Ilyas et al (2018) combined with a bandit approach. The current paper simply replaces the bandit with evolution strategies. The introduction of the evolution strategies is motivated by their good performance as a zeroth order optimization algorithm. \n\nA small novelty appears in a way to handle a bounded search space. The authors claim that many DFO algorithms are designed for unbounded real search space and need some constraint handling. The authors proposed two ways of transforming the bounded search space to the unbounded real search space. However, there must be existing approaches for this type fo constraint (rectangle constraint) in DFO settings. I can not list such approaches here as there are huge number of papers addressing the constraint of this type. There is not enough discussion in the paper why these two proposed approaches are promising. Formulation (2) makes the problem ill-posed and technically the optimal point may not exist. Formulation (3) with softmax representation makes the optimization problem noisy, hence it may annoy the optimizer. Nonetheless, I believe the combination of these constraint handling technique and evolutionary approaches are not new.\n\nSome minor comments / questions below:\n\nP5: How are the original images to be attacked selected for Fig 2? \n\nP6:  \"we highlight that neural neural networks are not robust to l∞ tiled random noise. \" Isn't it the contribution of (Ilyas et al., 2018b)? \n\nP7: What are the number of queries in Figure 3 and Table 1? Are they the number of queries spent until these algorithms found an adversarial example which is categorized to a wrong class for the first time?", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HylN_kKRKr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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).\n\nI have two main concerns about the current version:\n\n1)  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 \n[1] There are No Bit Parts for Sign Bits in Black-Box Attacks\n[2] AutoZOOM: Autoencoder-based Zeroth Order Optimization Method for Attacking Black-box Neural Networks\n[3] SIGNSGD VIA ZEROTH-ORDER ORACLE\n \n2) In addition to attack success rate and query complexity, it might be useful to compare different attacks in terms of $\\ell_p$ distortion, where $p \\neq \\infty$. This could provide a clearer picture on whether or not the query efficiency and the attack performance are at the cost of increasing the $\\ell_1$ and $\\ell_2$ distortion significantly.\n\n\n########### Post-feedback ##############\nThanks 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.\n\nI am Okay with the design of $\\ell_\\infty$ attack. However, if the reduction in query complexity is at a large cost of perturbation power, e.g., measured by $\\ell_2$ norm, then it is better to demonstrate this tradeoff. Furthermore, if the $\\ell_2$ norm is constrained, will the proposed $\\ell_\\infty$ attack outperform the others? This is also not clear to me.\n\nThus, I decide to keep my score. ", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a new black-box adversarial attack based on tiling and evolution strategies. While the experimental results look promising, the main concern of the reviewers is the novelty of the proposed algorithm, and many things need to be improved in terms of clarity and experiments. The paper does not gather sufficient support from the reviewers even after author response. I encourage the authors to improve this paper and resubmit to future conference.
Decision: Reject