On the exploitative behavior of adversarial training against adversarial attacks
Authors: Ali Rahmati
Seyed-Mohsen Moosavi-Dezfooli
Huaiyu Dai
Venue: ICLR 2022 Submitted (2022)

Abstract: Adversarial attacks have been developed as intentionally designed perturbations added to the inputs in order to fool deep neural network classifiers. Adversarial training has been shown to be an effective approach to improving the robustness of the classifiers against such attacks especially in the white-box setting. In this work, we demonstrate that some geometric consequences of adversarial training on the decision boundary of deep networks give an edge to certain types of black-box attacks. In particular, we introduce a highly parallelizable black-box attack against the classifiers equipped with an $\ell_2$ norm similarity detector, which exploits the low mean curvature of the decision boundary. We use this black-box attack to demonstrate that adversarially-trained networks might be easier to fool in certain scenarios. Moreover, we define a metric called robustness gain to show that while adversarial training is an effective method to improve the robustness in the white-box attack setting, it may not provide such a good robustness gain against the more realistic decision-based black-box attacks.

Under review as a conference paper at ICLR 2022
ON THE EXPLOITATIVE BEHAVIOR OF ADVERSARIAL TRAINING AGAINST ADVERSARIAL ATTACKS
Anonymous authors Paper under double-blind review
ABSTRACT
Adversarial attacks have been developed intentionally designed perturbations added to the inputs in order to fool deep neural network classifiers. Adversarial training has been shown be an effective approach to improve the robustness of image classifiers against such attacks especially in the white-box setting. In this adversarial training
work, we demonstrate that some geometric consequences on the decision boundary of deep networks give an edge to certain types of black- box attacks. In particular, we introduce a highly parallclizable black-box attack against classifiers equipped with & norm similarity detector, which exploits the low mean curvature of the decision boundary. We use this black-box attack to demonstrate that adversarially-traine trained networks might be easier to fool in certain scenarios. Moreover, we define a metric called robustness gain to show that while adversarial training is an effective method to improve the robustness in the white- box attack setting, it may not provide such a good robustness gain against the more realistic decision-basee black-box attacks.
INTRODUCTION
It is known in the literature that adversarial training can make deep neural networks more robust Madry et al. (2018); JShafahi et al. (2019); : Wong et al. (2019) against adversarial attacks attacks Goodfellow al. (2014); Carlini & Wagner (2017; Moosavi-Dezfooli et al. (2016); (Szegedy et al. (2013). Arguably, adversarial training can be assumed as one of the most effective techniques for robustness improvement AAhalyy et al. (2018). Moreover, it is empirically shown in MMosavi-Dezzool et al. (2019) that adversarial training causes the boundary of the image classifiers to become flatter (less curved) compared to normally-trained ones.
Adversarial attacks can be executed in the white-bon setting Carlini & Wagner (2017) Goodfellow al. M0004::/Moaaii-ezzioooo
et (2016). score- based black-box setting Chen et al. 2017);
et al. (2018): Narodytska & Kasiviswanathan (2016) or decision-based black-box setting [Brendel ct al. (2018): Chen et a et al. (2019) Liu al. (2019); Rahmati et al. (2020). The attacker's level of information about the classifier plays key role on the quality of the generated adversarial examples. In order to craft an adversarial perturbation in a decision- basedd black-box setting, the critical information is mostly the normal vector to the decision boundary. In this setting, the esti- mation of the normal vector is conducted with carefully designed fine-tuned queries at a boundary point of the image classifier, usually based the linearization of the boundary. Chen et al., Cheng et al. 2019); Liu et al. (2019): Rahmati et al. (022)). The objective of such black-box attacks is typically reduce the number of queries as much possible with an efficient estimate of the nor- mal vector. However, to make sure that this linearization approximation is valid at a boundary point, the & distance of these queries with the boundary point should be small enough. As a result, such similar queries can be detected using a k-nearest neighbours (KNN) similarity detector as in Chen al. (2020). Moreover, the efficient estimation of the normal the decision boundary heavily relies on the assumption that the boundary of the image classifier has a low mean curvature in the vicinity of input samples Fawzi et al. (2016); Moosavi-Dezfoolli et al. (001)). Therefore, such estimators are expected to work better if the decision boundary is less curved. Interestingly, it is empirically shown that adversarial training leads to neural networks with flatter decision boundaries, compared to the boundaries learned through regular training methods Qin et al. 2019); MMosavii-ezzool et al. (2019). We will show that this characteristic of the wersarially--rannee networks indeed gives an edge black-box attacks.

---

Under review as a conference paper at ICLR 2022
The goal of this paper is to show some evidence that although the adversarial training improves the robustness of deep image classifiers effectively against the minimal-now perturbation white- box attacks, it becomes less effective in more practical attack settings. In particular, we propose a parallelizable attack against classifiers equipped with an &z norm similarity detector to demon- strate that adversarialllytrainee networks might even be fooled with smaller &2 norm for given query budget compared to regularly-trained networks due to their excessive linear behavior. That is, decision- based black-box attacks can exploit the excessive flatness caused by adversarial training. In addition, we define metric called robustness gain as the ratio of Eg norm of adversarial pertur- bation required to fool the udversarially-tren traineed network to that required for the regular network. We observe that the level of information available to the attacker about the classifier impacts the robustness gain; in particular, the robustness gain increases when the information available to the attacker increases (e.g., from black-box to white-box, or by increasing the number of queries in the black-box -bx setting). We summarize the contributions of this paper as follows:
We empirically show that there is an interesting trade-off between adversarial training and the attack's 's effectiveness to fool the classifier. Moreover, we demonstrate that this trade-off is even more critical in certain black-box attacks which rely on the estimation of the normal vector at the boundary.
We introduce a highly parallelizable attack which is effective against a classifier equipped with query similarity detector based on E norm. Using normal vectors estimated at multiple points on the boundary, we develop an attack which is, interestingly. more effective against an adversarially-trann trained network as compared to regular network.
We define a metric called robustness gain as the ratio of l norm of adversarial perturba- tions required for the robust network to that for the regular network. We show that while adversarial training is an effective approach against minimum perturbation white-box at- tacks, it may not provide good robustness gain against black-box attacks.
The rest of the paper is organized as follows. In Section 3] the problem setting, the similarity de- tector, and the multi-point normal vector estimator are introduced. In Section 4 the performance of our proposed multi-point attack and the state of the art black-box attacks analyzed for the sniversarially-trinnee network compared to the regular one. In Section we evaluate the effective- ness of adversarial training against a minimum perturbation white-box attack and finally Section concludes the paper.
RELATED WORK
Adversarial Training The basic idea of adversarial training is to create and then incorporate ad- versarial examples into the training process (Szegedy al. (2013); Goodfellow al. (014)). In network to im- prove robustness against white-box attacks. In Shafahi et al. (2019), the authors proposed so-called "free" version of adversarial training with a cost nearly as equal as natural (regular) training. Their key idea is to update both the model parameters and image perturbations using one simultaneous backward-pass -psss. Recently, in Wong et al. (201)), the authors discovered that adversarial training can be conducted in a cheaper manner using the fast gradient sign method (FGSM) Goodfellow et al.) (2014) added with random initialization. This approach can be useful to adversarially train large datasets such as ImageNet much faster.
Madry et al. (2018), authors show an effective version of an adversarially-traine
Adversarial attacks Adversarial attacks can be executed in different categories depending on the attacker's level of information including white-box setting Carlini & Wagner (2017); Goodfellow et al.] (2014): [Moosavi-eezooll. et al.] (2016); (Szegedy et al. (2013), score- based black-box set- ting Chen et (2.7 llaas et al. (2018): Narodytska & Kasiviswanathan (2016) or decision- -based black-box scenarios Brendel et al. (2018); Chen et Chengg et al. (2019): Liu et al. (2019): Rahmaaii ctt al. (2020). In order to craft an adversarial example, the critical information is the normal vector to the decision boundary of the classifier. The most successful black-box attacks directly estimate the normal vector with linearization of boundary. For example, the HSJA Chen et al. deploys the gradient direction estimation information. In Liu et al. (2019); Rahmati et al. (2020), authors lo- cally approximated the decision boundary with a hyper- and searched the closest point on the hyper-plane to the benign input as the perturbation.
2

---

Under review as a conference paper at ICLR 2022
Black-box defenses The generation of adversarial example requires the black-box attacker to submit multiple similar queries to the target model. Thus, the main idea of most of black-box defences is to detect such similarity across multiple queries. In Chen et all (2020), authors propose to equip an existing classifier with a detection component, which stores the similarity vectors for all incoming queries, computed by pre-trained similarity encoder. For each new query, it computes the k-nearest-neighhe distance between it and all other vectors in the memory. Blacklight Li et al. (2020) computes compact set of one-way hash values for each query image that form a probabilistic fingerprint. The variants of an image make almost identical fingerprints, which makes it robust against manipulation. In BByun et al.] (202T). the authors introduce Small Noise Defense (SND) in which even small additive input noise can neutralize most query-based attacks.
3 PROBLEM STATEMENT AND MULTI-POINT ATTACK
Motivation and background One of the most challenging settings to perform adversarial attack to image classifiers when the attacker only has access to the top-1 label of the classifier, where the attacker's level of information from the image classifier is the least. A query is request that results in the top-1 label of an image classifier for a given input. The state-of-the-an attacks try to obtain the smallest possible bp norm of the perturbations with efficient use of queries to the
image classifier [rendel et al. (2018); Chen et al., Cheng et al. (2019); Liu et al. (2019); Rahmati et al. (2020). An implicit assumption here is that the image classifier is naive enough to respond to multiple consecutive similar queries with no complain. This is a strong assumption which is in contrast with the common sense in terms of security. In practice, the defender can take advantage of such characteristic of the queries to detect the suspicious set of queries. In addition, all these attacks perform in an iterative manner which can be time consuming even for a powerful attacker with lots of processing power. Having a parallelizable attack can expedite the running time of the attack which can be critical in certain scenarios that attacker should act as quick as possible. Our goal is to propose a highly parallelizable attack to fool the classifier equipped with an lz similarity detector by taking advantage of the low mean curvature of the decision boundary of tate-of-the-art deep classifiers.
Similarity detector, simple yet effective defense As in Chen et al. Cheng et al. (2019); Liu et al. (2019): Rahmati et al. (2020), most of the state-of-the-art black-box attacks generate queries with additive Gaussian or Uniform noises to a boundary point to estimate the normal to the decision boundary. Inherently, these types of estimators need similar, i.e. very close queries in terms of & distance to make sure the linearization assumption is valid. However, such similar queries can be simply detected by a l nearest neighbour (KNN) similarity detector with < N. where N the query budget for the attacker. Thus, the & nearest neighbours of the given query i are obtained among the queries stored in a buffer. In particular, for given query i, the classifier computes the average le distance between the query and its k nearest neighbors d, defined as in Chen et al. (2020):
1 d;
d
where d, is the & distance of the given query i with its nearest neighbours t where 1 s k. Then, by introducing the detection threshold 6, if d, < 5, an attack is detected and the user is blocked. The value for 6 should not be too small so that none of the queries get captured and also not too large to detect some clean queries as a false attack. Although, the computational complcxity of of the KNN detector may be high, it is quite effective and simple in detecting the queries generated by the techniques deploying normal vector estimation as in HopSkipJump Chen et al., GeoDA Rahmati et al.) (2020), Sign-OPT Cheng et al.] (201)), and gFoo Liu et al. (2019). We stress here that the goal of the paper is not to outperform the state-of-the-an black- box attacks, but rather to provide certain practical scenarios in which the flatter boundary of the adversarially-trained networks are exploitable by the black-box attacker. Therefore, the question is:
Is there way to design a parallelizable attack to generate a query-efficient e--norm-minimized perturbation with total N queries against a classifier equipped with a similarity detector of k nearest neighbours with threshold S?
We show that the answer to this question is affirmative and introduce a multi-point normal estimator which evades the similarity detector.
3

---

Under review as a conference paper at ICLR 2022
Boundary
k(x) k(za)
aado
k(x) = k(xrg)
Figure I: Multi-point normal vector estimation.
Problem statement We consider a trained L-class classifier with parameters represented as f R + R², where a E R is the input image and k(()) = argmaX, fa. (x) is the top-1 classification label where [xx) is the k-th component of f():) corresponding the k-th class. The attacker's goal is to minimize the l norm as much as possible with a limited budget of queries while cannot get detected with the similarity detector. We define the optimization problem as:
min
||0||2
s.t. 1(x + v) + k(x)), d, vi S.S...
The last constraint ensures that the queries are not detected by the &g similarity detector. Without the similarity detector constraint, problem equation 2 is already solved in the literature with different approaches Brendel et (0118: Chen al., Cheng al.) (2019): ; Liu et al. (2019) 9) Rahmati et al. (2020). The main idea is to obtain point on the boundary of the image classifier and estimate the normal the decision boundary at this point. However, with the presence the similarity detector,
the normal vector estimation becomes more challenging for the attacker as it can not generate large number queries with small le norms to the neural network.
3.1 MULTI-POINT NORMAL VECTOR ESTIMATOR
We employ the fact that the decision boundaries the state-of-the-art deep networks have a low mean curvature in the vicinity of inputs Fawzi et al. (2016) 2018). Therefore, to simplify equa- tion 2 we locally approximate the boundary of image classifier at multiple boundary points with a hyperplane as:
min |/0|12
s.t. u² (a + v) w æB, = 0. Vj
d, 6, Vi < N,
where æB. is the j-th boundary point and M is the number of boundary points obtained using binary search. Having a single boundary point M and spend all N queries at æ estimate the normal to the decision boundary can make the attack parallelizable. However, such an attack can be simply detected by the similarity detector. Also, iterative attack is not desirable since each iteration the boundary points distances decreases. Thus, need to design estimator in which the queries cannot detected by the similarity detector.
Multi-point normal estimator To alleviate the aforementioned problem, we propose the multi- point normal vector estimator in which the queries are generated on multiple boundary points (M > 1). The key idea to distribute N queries estimate the normal vector to the boundary using multiple boundary points, rather than spending all N queries just single point. Apparently, considerable portion of queries are allocated to obtain the boundary points along with binary search. This is the cost imposed by query detector the attackers. This estimator is both parallelizable and, as we will see, successful against classifier equipped with an &z similarity detector.
As seen in Fig. I starting from the original image Ta, denoted by x f... 2 B........ HR.M- Similar to the method proposed Chen et al., Liu et al.] (2019); Rahmati et al. (2020), the boundary points can be obtained using binary search along several random
find M points the boundary
4

---

Under review as a conference paper at ICLR 2022
Algorithm 1: MMMullippoin attack
Inputs: Original image Zig, query budget N.
Output: Adversarial example ad
Obtain the optimal number of boundary points M by M N-8
k-b-y
Obtain M* starting point on the boundary B,,,, B.2 ................................ ,,,, BB.M*
Estimate normal to with equation 5
Push the original image To towards the boundary in the direction of w.
P f min(r's > 0 k(or + r'))- + k(x)}
zd x0 fm
directions, with b queries on average per boundary point Normally, these b queries are quite close to each other and can be assumed as bad queries which we have to minimize in our design as much as possible (from the attacker perspective). In general, the close queries are not desirable since they can reduce the KNN mean d; for given query and increase the chance of getting detected by the similarity detector. On the other hand, the most informative queries are the ones with small distances with one another which creates an interesting trade-off. We assume that the attacker knows that the query detector deploys A nearest neighbours to compute de for each query i. Here, without loss of generality, we assume that the closest boundary point to æ; is B. The similarity detector observes three types of queries when computing its k nearest neighbours for query The first type are the queries used to obtain the boundary point with added Gaussian noise along with binary search. The second type are the ones deployed to estimate the normal to the boundary at B.j- Finally, the type three distances for query I; are obtained between the and its second closest boundary point to 2;- At each boundary point BBj S j S M, the attacker can allocate n = k -- b--- 7 queries to estimate the normal to the boundary at point Bnjj where b is the average number of type II queries, and is the number of type III queries. Thus, the number of required boundary points can be obtained by:
N -
M
(4)
k b-
where 8 is the number of queries required to push the xp towards the direction of the estimated normal vector towards the boundary (step 6 of the Algorithm [ At each boundary point j. the boundary is locally approximated with hyperplane wi! (ar FBB) 0. In order estimate the normal vector Wj, the key idea is to generate n samples S., {1, f1...., n) from multivariate normal distribution Ç; ~ ~N Σ) which results in queries with the form of x ænj + Si, Vi E N Rahmati et al. 2020)) The estimator úu of w, with n queries is (ū = - &iG where 2; = if (( (x) k()nn)) and otherwise 2; 11 Eventually, the average normalized direction of estimated normal vector over all the boundary points can be given as:
ΣM 5ー
(5)
After estimating the normal to the boundary T. we push the original image æg towards the boundary in the direction of é with amplifying the magnitude of the vector. The final multi-point attack is summarized in Algorithm 1
3.2 NUMBER OF BOUNDARY POINTS
In this section, our goal is to have an estimate for the optimal number of boundary points. The number of boundary points M should not be too small resulting in close queries that will get detected by the similarity detector, and must not be too large that wastes the number of queries (as obtaining each boundary point costs b queries on average). We assume that the attacker has the information about & and 8. Thus, by computing the KNN distance in the design step of the attack, the attacker can evade the similarity detector. As mentioned previously, for a new query i, the nearest neighbour queries and their distances I; can be categorized into three types. We aim have an estimate for the optimal number of boundary points. For more details about mean distance of queries (14), refer to Appendix I.
Having the mean distances (1:)) of queries in hand, the attacker can have an estimate on the number of type II queries at each boundary point get an estimation of the normal vector of the boundary
5

---

Under review as a conference paper at ICLR 2022
without getting detected by the similarity detector. The number of queries at each boundary point should not be too large so that the similarity detector can detect the queries due to the small d,. Moreover, it should not be too small to incur excessive overhead in finding boundary points. Thus:
d. = k E d. = 7 (b11 + np2 + +y3)) = + X,
(6)
where À is margin to the threshold to make sure that the average distance not be detected by the similarity detector. We may ignore the n/12 term as it is typically small compared to μn and μ3- Having this approximation, the optimal value for can be obtained as Y k(6+A)=bu1, It simply μa can be seen that if A4 is large, then the number of type II queries per boundary point increases which results in more efficient deployment of queries. The optimal number of boundary points can be obtained by plugging y" into equation 4 as M k-b k-b- Based on this, by increasing the number of type III distances which results in increasing the KNN mean, one can see that the number of required boundary points to satisfy d; 8 + A decreases well.
4 EFFECTIVENESS OF ADVERSARIALLY-RRANN NETWORKS AGAINST BLACK-BOL BOX ATTACKS
In this section, our goal is to evaluate the effectiveness of adversarial training against decision-based black-box attacks in which the attacker has only access to the output label of the image classifier for a given input. We evaluate our experiments on a pre-trained ResNet-50 He et al. (2016) called regular network and the adversarially-traine ResNet-50 Madry et al. (2018) called robust network throughout this section. We consider 300 correctly classified images by both networks which are randomly selected from the ILSVRC2012' validation set Deng al. (2099)
4.1 MULTI-POINT ATTACK AGAINST SIMILARITY DETECTOR
Here, we evaluate the performance of our novel multi-point attack and an iterative attack (GeoDA (GeoDA
Rahmati al. (2020) on an adversarially-traine
network equipped with an l similarity detector
in Fig 2a For the similarity detector, we assume k = 100, = 5, < = 5. We also set nh = 45 and nt= 30. We deploy uniform GeoDA with 400 queries per iteration. It can be observed that the iterative attack can be detected after a few number of queries as similarly detector's 's KNN mean drops quickly below 8 3+6 Ç. However, the multi-point attack by-pass the similarity detector by keeping the KNN mean d, vi greater than the detection threshold by distributing the queries over the distant boundary points.
In Fig. [b] we compare the & norm of single-point attack (M = 1, which is highly paralleliz- able, but not successful against the similarity detector) and our proposed multi-point attack on both networks with respect to number queries. For the single iteration attack, the performance of attack on regular network better compared to the robust network as ex- pected. However, for the extension to mulli-point attack which can successfully evade the similarity detector, we interestingly see that the performance of the multi-point attack on the robust network is almost the same as the performance of the single point attack. However, for the regular network, the performance of the multi-point attack is much worse compared to the one for the single point attack. Thus, interestingly, adversarially-trrinnn -rrined network can be fooled with smaller &2 norm with the same amount of queries. Also, we observe that the trend of the convergence for the regular network is more noisy which is due to non-smoothness of the boundary.
regular and adversarially-train
The reasons behind the above observations are twofold. First, it is quite intuitive that the multi multi-point normal estimator can preform better on smoother boundaries. In particular, the flatter the boundary the more aligned the directions of the normal vectors at different boundary points are. In the extreme case that the boundary is a hyper-plane, the normal vectors to the boundary on all over the hyper- plane are in the same direction. Thus, this results in better estimation of the normal vector to the boundary for the classifier in black-box setting when the network is more is adversarially-trained (boundary is flatter).
Note that most of the state of the art attacks in which they estimate the normal to the decision houndary are iterative and follow the similar procedure. Thus, comparing with one of them is sufficient for this experiment.

---

Under review as a conference paper at ICLR 2022
203
Me point attack
Mull-pottt Regutar
Rer Kerative atta Detectorthreedee thandrrtt
Molls Robsat
Singt-ppien Reguth"
Modian of nomm
Shigi-pple: Robure
202
Delector 83 distance
25
103
53.
ti
200
1900
1200
5002
10003 12020
Number
Number
Figure 2: (a) KNN query similarity detector Eg distance for iterative and multi multi-point estimator. (b) Performance of single-poin and multi-poin attacks on both regular and robust ResNet50.
Second, as shown in equation 9 the larger the type III mean distance μ4 is, the less number of type III queries 7 is needed to satisfy equation [ In equation 4 the larger 7" follows with fewer number of boundary points M This leads to a more efficient deployment of the queries in the robust network as obtaining each boundary point impose the cost of approximately b queries per boundary point to the attacker. We empirically show in the Table [ that the mean distance of the points on the boundary 143 is larger for the adversarially-train regular network. As discussed above, this can reduce the number of required boundary points to satisfy d, = + À in equation g which benefits the attacker. Thus, we have pu
network compared to the one for
ju' which leads tbst
to y < < 7e8 in equation 9 and also Mr < M As a result in equation we have that > ne which results in larger number of queries at each boundary point. The smaller number of boundary points is beneficial for the attacker as can save on average b queries per boundary point. Moreover, larger number of queries at each boundary point thut > n2 can increase the accuracy of the normal estimation at each boundary point.
Black-box attacks performance evaluation We compare the performance of black-box attacks HSJA Chen et al., GeoDA Rahmati et al. (2020). boundary attack (BA) (Brndel et al. (2018) on both regular and robust ResNet-50 networks in Fig. 3a For a given query budget, the & norm of pertur- bations for the attacks against the robust network is larger compared that of the regular network as expected. However, an interesting observation is that while GeoDA has almost the same l norm as HSJA for the regular network, it provides smaller lg norm for perturbations against the robust network compared to HSJA for a fixed amount of queries. The reason for this phenomenon is that GeoDA is explicitly built based on the assumption that the boundary of the classifier has low mean curvature. On the other hand, adversarially nratoos-networks has flatter decision boundaries which actually gives an edge GeoDA. Thus, to attack robust networks more efficiently, it is beneficial for the attackers to deploy attacks exploiting the flatness of the decision boundary.
Robustness gain Here, our goal is to evaluate how much wnveerrrrilllytrannne networks can im- prove the robustness under various kind of attacks. We plot the robustness gain for different attacks in Fig. 3b The larger the 77 for a given attack is, the better the adversarial training can improve the robustness compared to the case of the regular network. In Fig. [3b] it is observed that r7 is equal to around 17 (see Table 2 for the white-box attack DeepFool (DF) Moosavi-Dezfooe et al. (2016) which is a quite good improvement. Having a black-box setting, we evaluate the v) for HSJA Chen et al. GeoDA (aammati et (2020), boundary point attacks as well. First, it can be seen that, in general, the robustness gain is lower than that of the DeepFool. Second, by extracting more information from the image classifier (more queries), the robustness gain increases. For the single iteration and multi-point attack, 17 is much lower compared to the that of other black box attacks with a small increasing slope along with increasing the number of queries. It may imply that the less information you know about the image classifier, i.e., the more practical the attack scenario is, the less the ddversarially-trainee network can improve the robust- ness. That being said, adversarial training for the deep image classifiers is much more effective for white-box scenarios.
(Breneel et al. (218). single iteration and multi-
Mean distance of boundary points The mean distance of boundary points μ4 is a critical design parameter for the multi-poin attack as it determines the number for boundary points. Here, we have done experiments to measure the μs for both networks with different number of boundary points M. We start with boundary point Ø and obtain the E norm to this point from all other boundary
7

---

Under review as a conference paper at ICLR 2022
GeeDA: Rebust
Deepfcol GeEDA HSJ
73
GzsDA Regular
HSA Robuet
HSA Regulr
2A hobus:
20
Sengl- 99 Muliipuira
M
PA. Regular
Median of
40
Robustrens
30-
13
2002
10003
12020
5002
10003
Number
Number
Figure (a) Performance comparison of different black-box attacks for both regular and robust ResNet50, (b) The robustness gain for bg norm under different attack scenarios.
points. The average of such a distance over 300 correctly classifier images by both networks is reported Table It is observed that the (43 is large for the robust network compared that of regular network. Moreover, we can see that the value of μ4 even for M = 2 is very close to the true mean. Thus, the estimate of the μ3 can be cheaply obtained with only A = 2 since in the high-dimensional regime, the l distances are close enough.
M
M = 10
M = 100
Regular He et al. (0016)
67.01
67.38
69.34
Adv. trained Madry et al. (2018)
90.11
88.47
89.71
Table Mean distance boundary points μa on both robust and adversarialll-trrinee networks for different number of boundary points averaged over 200 samples.
ADVERSARIAL TRAINING AGAINST MINIMAL-NORM PERTURBATION WHITE-BOX ATTACK
We already discussed the effectiveness of the adversarially-trained network with respect to num- ber of required queries against decision-based black-box attacks in query-limited regime. In the white-box scenario, we evaluate the effectiveness through the number of required iterations for the convergence of minimal le norm perturbation white-box attack. To this end, we choose minimal l2 norm white-box attack DeepFool Moosavi-Dezfooli et al. (2016) and compare its performance an adversarially-trained Madry al. (2018) and regular ResNet-50 in Table
DeepFool performance To this end, we choose a minimal lg norm white-box attack Deep- al. (2016) and compare its performance on an adversarially-trained Madry et al. (2018) and a regular ResNet-50 in Table The main reason we choose DeepFool is its depen- dence on linearizing the output function of the classifier. The algorithm starts with locally linearizing the output function of the classifier and repeats such an approximation iteratively to compensate for the effect of the non-linearity of the output function. The more linear the output function of image classifier is, the fewer iterations required for DeepFool to converge. Interestingly, despite that the udversarially-truun -rainedd network has perturbations with larger la norm, due to the more linear behavior of its output function. DeepFool converges faster on this network. In this sense, can conclude that is casier to attack adversarially-tranne networks even in the boxte-box setting.
Fool MooooMoo-Dzzoooooo
Med Iters
Max Iter
l norm
Regular He et (016
4
15
0.209
Adv. trained Madry et al 20188)
2
4
3,618
Table 2: DeepFool Mezsavi-Dezfooli et (016)) performance on robust and regular ResNet-50 networks.
DeepFool iterations behaviour In this experiment, the goal to qualitatively study the behaviour of output function along the trajectory of the iterations of DF for single data point. In this case,
8

---

Under review as a conference paper at ICLR 2022
liga
righen Progpest
24
34
C4
13
AG KX
18
150
10
00
AG
10
(a)
(b)
(c)
(d)
Figure 4: Performance evaluation of DeepFool over different iterations on (a) Regular ResNet 50 network, (b) Adversarially-traine ResNet 50 network. Differences of classifier's 's output for clean and adversarial labels when adversarial sample obtained by (c) DeepFool (close to the boundary), (d) Randomly using Gaussian perturbation (far from the boundary).
DeepFool requires 3 and iterations to converge for robust and regular ResNet-50, respectively. We consider the difference of the logits corresponding to the original and the adversarial labels for our evaluation. We track this difference along two paths: 1) the straight path between the original image and the DF adversarial example (i.e., green line in Figs. 4a and 4b). and 2) the path taken by DF in each iteration (i.e. black and red line segments). We generate images on the line from the original image to the minimal perturbation adversarial example obtained by DeepFool. By varying the line parameter t, we consider the images along the line x = Zg + +xEad ZD). where t = 0 corresponds to the original image and = 1 gives the adversarial image which falls the boundary. When the image is on the clean label side, the output value of the clean label is larger than the adversarial label. Approaching the boundary, this difference decreases where is equal to zero and the transition occurs. Assuming æ; as the output of DF in iteration i, each line segment (i.e. black and red segments in Figs. 4a and 4b) is corresponding to the images on the line x = (i-11) + t(æ; - (i) ) for t E [0. IJ. where I; Lade if is the last iteration. First, it can be seen that the straight path (green line) is much closer to the path constructed with DF iterations' segments for the adversarially-eee trained network compared to that of regular network. Second, is shown that even in each line segment corresponding to each iteration traversed by DF algorithm, there is more non-linearity in regular networks as they are curved. As result, although the adversarial training improved the robustness (increases the minimal lg norm), it provide an opportunity for the attacker to attack casier (with less number of iterations to converge) due to more linear behaviour of adversarially trained networks.
the boundary the difference
Non-linearity of the output The goal is to see how the output of the classifier behaves when push the image towards the boundary. In Fig. 4c the adversarial example is obtained using DeepFool, while in Fig. the adversarial point is obtaied with adding Gaussian noise along with binary search. In general, the difference of output in the adversarially trained network is more smooth and linear. This inherently shows that the no-linearity of the regular network is much higher than robust networks. Moreover, it can be seen that if the adversarial image is chosen randomly which is far from the original image (e.g. in Fig. 4d). this non-linearity is more sever. Thus, we can see that in the case of black-box attack, the attacker faces more non- -ineariyyy compared to the case of white-box setting. Since most of the black-box attacks try to obtain the normal vector to the boundary or estimate the gradient around a random boundary point, the more linear behaviour of output function and lower curvature of the boundary can help the adversary to better estimate the normal vector.
6 CONCLUSION
We showed that although the adversarial training is quiet effective against white-box attacks, in query-limited decision-based black-box attacks, may not perform as efficiently as in the case for the white-box attacks. We demonstrated that since the adversarial training leads to a significantly flatter boundary and a more linear behavior of the image classifier, can give an edge to certain types of black-box attackers whose goal is to estimate the normal vector to the boundary. This feature of the adversarially--raanne trained networks can also provide a chance for minimal norm perturbation whit- box attacks to produce adversarial examples with less number of iterations. We introduced highly parallelizable attack which can be successful against a similarity detector that can fool the robust network even easier compared the regular classifier.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give a false sense of se- curity: Circumventing defenses to adversarial examples. In International Conference on Machine Learning, pp. 274-283, PMLR, 2018.
Wieland Brendel, Jonas Rauber, and Matthias Bethge. Decision- adversarial attacks: Reliable attacks against black-box machine learning models. In International Conference on Learning Representations, 2018
Junyoung Byun, Hyojun Go, and Changick Kim. Small input noise is enough to defend against query-based black-box attacks. arXiv preprint 1rX11:2001.04829, 2021.
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In 2017 ieee symposium on security and privacy (sp). pp. 39-57, 2017.
J Chen, MI Jordan, and MJ Wainwright. Hopskipjumpaattak: query-efficient decision-based attack. In 2020 IEEE Symposium on Security and Privacy (SP), pp. 668 685.
Pin-Y Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsieh. Zoo: Zeroth order opti- mization based black-box attacks to deep neural networks without training substitute models. In Proceedings of the 10th ACM Workshop Artificial Intelligence and Security, pp. 15-26. ACM, 2017.
Steven Chen, Nicholas Carlini, and David Wagner. Stateful detection of black-box adversarial at- tacks. In Proceedings of the 1st ACM Workshop on Security and Privacy on Artificial Intelligence, pp. 30-39, 2020.
Minhao Cheng, Simranjit Singh, Patrick H Chen, Pin-Yu Chen, Sijia Liu, and Cho-Jui Hsieh. Sign- opt: A query-efficient hard-label adversarial attack. In International Conference on Learning Representations, 2019.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hi- erarchical image database. In 2009 IEEE conference computer vision and pattern recognition, pp. 248-255- 2009.
Alhussein Fawzi, Seyed-Mohsen Moosavi-Deziie and Pascal Frossard. Robustness of classifiers: from adversarial to random noise. In Proceedings of the 30th International Conference on Neural Information Processing Systems, pp. 1632-1640, 2016.
Alhussein Fawzi, Geyed-Mohsen Moosavi- -ezaaii-,,eooii,, Pascal Frossard, and Stefano Soatto. Empirical study of the topology and geometry of deep networks. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 3762-3770, 2018
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint 14Xiv:1412.65722 2014.
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.
Andrew Ilyas, Logan Engstrom, Anish Athalye, and Jessy Lin. Black-box adversarial attacks with limited queries and information. arXiv preprint arXiv:1804.0855 085988, 2018.
Huiying Li, Shawn Shan, Emily Wenger, Jiayun Zhang, Haitao Zheng, and Ben Y Zhao. Black- light: Defending black-box adversarial attacks on deep neural networks. arXiv preprint arXiv:2006. 14042, 2020.
Yujia Liu, Seyed- Seyed-Mohsen Mlosavi-Dezfoolle and Pascal Frossard. A geometry-inspirg decision- based attack. In Proceedings of the IEEE International Conference on Computer Vision, pp-
4890 2019.
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, 2018.
10

---

Under review as a conference paper at ICLR 2022
Seyed-Mohsen Moosavi-Dezfooll Alhussein Fawzi, and Pascal Frossard. Deepfool: simple and accurate method to fool deep neural networks. In Proceedings of the IEEE conference on com- puter vision and pattern recognition, pp. 2002-5575555 2582,, 2016.
Seyed-Mohsen Moosavi-Dezfone Alhussein Fawzi, Jonathan Uesato, and Pascal Frossard. Ro- bustness via curvature regularization, and vice versa. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 9078-9088 2019.
Nina Narodytska and Shiva Prasad Kasiviswanathan. Simple black-box adversarial perturbations for deep networks. arXiv preprint arXiv: 2016.
Chongli Qin, James Martens, Sven Gowal, Dilip Krishnan, Krishnamurthy Dvijotham, Alhussein Fawzi, Soham De, Robert Stanforth, and Pushmeet Kohli. Adversarial robustness through local linearization. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Buc, E. Fox, and R. Gar- nett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Ali Rahmati, Seyed-Mohsse Moosavi-Dezzoolli Pascal Frossard, and Huaiyu Dai. GeoDA: a geo- metric framework for black-box adversarial attacks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 8446-8455, 2020.
Ali Shafahi, Mahyar Najibi, Mohammad Amin Ghiasi, Zheng Xu, John Dickerson, Christoph Studer, Larry S Davis, Gavin Taylor, and Tom Goldstein. Adversarial training for free! In Advances in Neural Information Processing Systems, pp. 3358-3369, 2019.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv:1312.6199 2013.
Eric Wong, Leslie Rice, and Zico Kolter. Fast is better than free: Revisiting adversarial training. In International Conference on Learning Representations, 2019.
A APPENDIX
A.1 MEAN DISTANCE OF THE QUERIES
In this section, our goal is to have an estimate for the optimal number of boundary points. The number of boundary points M should not be too small resulting in close queries that will get detected by the similarity detector, and must not be too large that wastes the number of queries (as obtaining each boundary point costs queries on average).
We assume that the attacker has the information about h and 8. Thus, by computing the KNN distance in the design step of the attack, the attacker can evade the similarity detector, As mentioned previously, for new query i, the ht nearest neighbour queries and their distances to æ; can be categorized into three types. In this section, we compute the average distance of each type of queries to x..
Type I: These queries are the ones required to obtain the boundary points. The boundary points can be obtained by starting from an adversarial perturbation with large l2 norm and pushing it towards the boundary with binary search. The average distance of such queries with given query x; can be computed μ4 the exact μ1 can be complicated and not even necessary. Instead, we approximate it with 141 = ||=;- B.j.ll where 2 B.j. is the nearest boundary point w,, Please note that b is number of queries required for binary search. It could be determined after obtaining the first boundary point.
Σ || æell. Obtaining
The type II queries are the ones generated the obtained boundary points to estimate the normal vector to the boundary. These queries are the most valuable queries in terms of information one can get from the image classifier. However, since their pairwise distances are small, they are the ones easily detected if not employed carefully. The means that we provide here are for given type II query æ; (( I²)). The nearest queries of the type II a has the same multivariate Gaussian distribution y -T in which
Type II:
11

---

Under review as a conference paper at ICLR 2022
2; 2, follows Gamma distribution Y ~ I(a; 3) with N/2, 8 400 Thus, de, = v has a Nakagami (m, Q2) distribution where m = N/2 and f2 = 2No
Therefor the mean distance of the Type II queries is given by:
(m 2) [(m)
Ω m
1/2
P2
Type III: Finally, type III includes the distance of queries between each group of queries on boundary points. These queries have large distance with each other which can increase the mean of the KNN similarity detector. We approximate it with the mean distance of the boundary points from one another. Thus, uz3 = M A [B æB,ll, 1 I S M.
Having the above information in hand, the attacker can have an estimate on the number of type queries at each boundary point to get estimation of the normal vector of the boundary without getting detected by the similarity detector. The number of queries at each boundary point should not be too large so that the similarity detector can simply detect the queries due to the small d₃- Moreover, should not be too small to incur excessive overhead in finding boundary points. Thus, have:
d, Σ de. (byn + nu2 + Y/3)) + X,
where À is a margin the threshold to make sure that the average distance can be detected by the similarity detector. We may ignore the n/22 term as it is typically small compared to μn and /43- Having this approximation, the optimal value for y can obtained as:
1:6 + A) bμ4
A33
It simply can be seen that if As is large, then the number of type II queries per boundary point increases which results more efficient deployment of queries. The optimal number of boundary points can be obtained by plugging 7 into equation 4 as M - b-b Based on this, by increas- ing the number of type III distances which results in increasing the KNN mean, one can see that the number of required boundary points to satisfy d, = 5 + X decreases as well.
N-B
12


Reviews:
[{"review_id": "yijMrLyOfEb", "reviewer": "Reviewer_Q3xq", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "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": "1. Novelty\n\nThe paper proposes a “multi-point” adversarial attack which works in black box hard label settings and could be parallelized. This is a novel attack, which to the best of my knowledge was not considered in literature before.\n\n2. Assumptions about detectors of black box attack.\n\nAuthors study a setting when a defender tries to detect whether a query-based attack is done against their classifier and argue that their parallelizable attack could help to bypass such a detector. However authors impose several assumptions on such an attack which are not well justified in the paper.\n\nFirst of all authors assume the black box setup for the classifier under attack, at the same time authors assume that adversary has the knowledge of parameters of the detector. Generally speaking, one would expect that these parameters would be unknown in black box setting. Thus further discussion is needed on how to estimate such parameters.\n\nAdditionally, the proposed attack samples several points near the decision boundary and then further explores regions around these points to estimate normal to the decision boundary. It seems like authors assume that these points near the decision boundary are far enough from each other, such that their exploration won’t trigger the detector. However, since all explored points are near original $x_0$ it might be the case they are all within $\\delta$ range of the detector. In such a case multi-point attack does not really help preventing detection.\n\n3. Evaluation of black box attack and adversarial robustness.\n\nAuthors claim that adversarially trained network might be easier to fool using black box attack. However their own experiments show that it’s not true in most cases (see Figure 3(a) and Table 1). There is a small part of figure 3 where this claim seems to be true (dashed blue line is above solid blue line), however it’s the weakest of the considered attacks.\n\nAdditionally, authors claim to evaluate their attacks on robust Resnet 50 and cite Madry et al paper. While Madry’s paper talks about adversarial training, it does not specifically talk about training of Resnet50 on Imagenet. Moreover it has been shown in future research by various people that adversarial training of Imagenet size models is not an easy task.\nThus authors should provide more details about training of their robust Resnet 50 model as well as it’s white box evaluation.\n\n4. Overall the paper looks like a collection of several somewhat unrelated stories.\n\nSpecifically, part of the paper talks about multi-point attack and how to potentially evade detection. Another part of the paper talks about adversarial training and performance of black box attacks. \nIt might be beneficial to make a paper focused on one topic and study this topic in more detail and show stronger results.\nMoreover, focusing paper on one topic would make it easier to read.\n", "summary_of_the_paper": "The paper mainly talks about the following topics:\n* Study whether adversarial training makes it easier to perform black box attack on the model.\n* Novel multi-point black box attack, which is easy to parallelize and which is potentially can be more effective in the case when defender tries to detect black box attacks.\n", "summary_of_the_review": "Paper proposed novel attack, however have several serious drawbacks:\n* assumptions about attacker knowledge might be too strong and need further discussion\n* evaluation of the black box attacks on adversarially trained model does not seem to support one of the claims of the paper.\n* overall paper is written as a collection of somewhat unrelated stories.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "segCPZAAX3", "reviewer": "Reviewer_ozXg", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "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": "Overall, I find it difficult to understand the main focus of this paper. It seems to me that the novel black-box is the focus of this paper, but the title tells me it’s more about exploiting the smooth boundary of adversarially trained models.\n\nThere are a few concerns regarding this new attack. Firstly, the authors have made a rather unrealistic assumption that the attackers know the hyperparameters ($k$ and $\\delta$) for the KNN detector. In practice, a black-box setting should only provide query access to attackers. In addition, the fact that this attack performs worse on regular DNN models is also a problem. In general, it seems this proposed attack is only useful when there is a KNN detector. An attacker will face a challenge if there is a KNN detector but the underlying model is a regular one, which could be a common scenario.\n\nOn the exploitation of adversarially trained models, I find the provided empirical evidence is not sufficient to draw the conclusion. The authors seem to take it as a fact that adversarially trained models have a flatter boundary. There is really no explanation in this paper on why it is true nor a reference that has shown this conclusion. Since almost all the arguments regarding the exploitation of adversarially trained models are based on this assumption, the authors should provide more explanation regarding it. Also, the fact that DeepFool requires 2 additional iterations on regular models is not a convincing evidence to show this boundary-based white-box attacks also exploit boundary smoothness.", "summary_of_the_paper": "In this paper, the authors propose a new type of query-based black-box attack called multi-point attacks. This attack is designed to avoid being detected by KNN based detectors. Meanwhile, this paper also points that adversarially trained models have smooth boundary thus making it easier for attacks that could exploit this property to success.", "summary_of_the_review": "I find a few issues in this paper that push me towards rejecting this paper. Please see comments above for details.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "rYNe6DhYraV", "reviewer": "Reviewer_jHBK", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "## Strengths:\nThis paper makes bold claims: that it has developed a novel attack algorithm capable of defeating a recent defense, that this algorithm is more efficient and parallelizable, and that the robustness properties of adversarially trained networks diverge significantly from those of regularly trained ones. Each of these can be a strong contribution to the field of adversarial machine learning. \n\nFirst, adaptive attacks are crucial to pushing our understanding of what “secure” machine learning is. By developing a method to defeat the kNN defense, this paper expands the understanding of what adversaries to defend against. Therefore, future work on defenses can use this one as a basis to build even more robust models . Second, the algorithm developed could be more efficient at generating black box adversarial examples. Black box attacks have so far had relatively limited real-world impact, as most machine learning systems do implement rate limiting. The idea of parallelizing the queries is an important contribution that expands the scope of methods for black box attacks. While the number of queries is still too large, this line of thinking is worth pursuing further and this paper offers a useful basis that the community would benefit from exploring further. Finally, the paper claims to have observed a paradoxical behavior in adversarilly trained networks. The “common wisdom” on those models is that they achieve better robustness at the cost of regular accuracy. Therefore, the observation that robustness of these models also suffers in the face of a new class of adversaries is an important one that the community should take note of.\n\n## Weaknesses:\nUnfortunately, this paper is lacking in the experimentation to back its claims. Most conspicuously, any mention of the success rate of the attacks developed is omitted. Instead, the authors use the magnitude of the perturbation as the basis for all claims given. While this can be an important secondary metric of how well an attacker is achieving their goals, it alone cannot back the claims made.  Concretely, this paper should be improved by performing all evaluations with a measure of how many adversarial examples successfully defeat the classifiers targeted. \n\nIt is possible that the authors implicitly assume that a reader should understand that all of their attacks have a 100% success rate. If that is the case, the authors should at a minimum explicitly state this. Furthermore, they should clarify after what number of queries this attack success rate is achieved. In an ideal evaluation, Figures 2 and 3 should be replotted with that measure. \n\nAssuming these measurements back their claims, the authors could also be expanded in the following fashion:\n* The claim for the linearity of the decision boundary of robust classifiers and  the implications for robustness against this parallelizable attack needs stronger backing. The authors should carry out the evaluation on multiple architectures, training and test sets, and tasks. It is insufficient to make such a strong claim based on a single network and a sample of the “standard” test set.\n* The authors could do well to think more broadly about adversaries and robustness. While they include different attacks in their consideration (GeoDA and white box attacks), comparison against more attack methods could significantly strengthen the paper’s conclusions. These include adversaries that use different Lp norms in their constraints, more query-based black box methods, and non-gradient based adversaries (such as blurs, filters, overlays, and others). \n* The authors could consider stronger defenses, including different settings of defenses they already consider. Would their attacks be defeated if the kNN defense method is tuned to a parallelizable attack? How does the success rate vary with the different parameters? Could defenders come up with entirely novel defenses in response to parallel attacks like the one proposed here? ", "summary_of_the_paper": "This paper proposes a new black box adversarial examples generation algorithm and uses it to draw conclusions about the decision boundary of adversarially trained models. \n\nThe algorithm developed is in response to a recent defense mechanism that stops black box attacks by detecting queries that are similar to each other. Therefore, this work proposes a new method that keeps similar queries to a minimum. The crux of the algorithm’s operation is that it estimates the normal vector to the decision boundary of the model – similar to prior work. Unlike previous papers, however, this one does so by querying at different spots along the decision boundary rather than focusing all the queries on the same point. This helps defeat similarity-based defenses. \n\nThe paper then applies this algorithm to both regularly trained networks and adversarially trained ones. This serves as the basis for claims about the geometry of the decision boundaries of each of those network types. To make these claims, it uses two metrics. First, this work observes the magnitude of the perturbation added to starting points in the adversarial example generation process against the number of queries the black box algorithm has used. Second, it introduces a new metric – robustness gain – that computes the ratio of that magnitude for adversarially robust networks and regular networks. \n\nThe conclusions of the work are all based on the difference of those metrics between adversarially trained and regular networks. Most interestingly, this paper claims that adversarial training is a weak defense against black box attacks of the type it develops. \n\n\n", "summary_of_the_review": "The paper makes strong claims with important and interesting implications for the field of machine learning and develops a novel attack mechanism defeating a proposed defense. However, the claims are not backed up properly with a major, obvious metric missing entirely from the evaluation. If the claims are backed up according to the success rate of the attacks – instead of the magnitude of the perturbation – and if evaluation is carried out on a more diverse set of models and datasets, this can be a very strong paper. \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "fg_G9aLSNhj", "reviewer": "Reviewer_knUq", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "[Strength]\n1.\tThe paper provides a clever attack method that avoids detection based on the similarity among queries from a black-box attack.\n2.\tThe formality of the problem definition and the approach looks to be good enough.\n\n[Weakness]\n1.\tOne of the experimental results can be interpreted differently so that one of the contributions can be just a misreading of the experimental results.\n2.\tSome parts of the paper require more explanations and formal descriptions about the concepts.\n\n[Comments]\n1.\tAbout Figure 2b, as far as I understand, the authors tested two attack methods (single-point attack and multi-point attack) against two ResNet50 models (regular and robust) over the same set of target data points. (If they are tested on different sets of target data points, it could be an unfair comparison.) Then, against the regular ResNet50 model, the single-point attack can find much better perturbations (than the multi-point attack) for the same set of target data points. Doesn’t this just mean that “the multi-point attack is not effective against the regular ResNet50 model” rather than “adversarially trained model is more vulnerable (than the regular ResNet50 model) against the multi-point attack”? In other words, the main contribution that “certain black-box attack can perform better against adversarially trained model” is just a misreading of the experimental result and there is another possible interpretation that “the multi-point attack is not effective against the regular model”. (The reason for this another interpretation could be the reason that is provided by the authors; a regular model has a less smooth boundary.)\nAlso, the comparison with DeepFool (Figure 3b) says that the robustness gain is bigger for white-box attacks (constantly 17) compared to other black-box attacks. However, since the robustness gain is defined as a ratio, this value can be small just because black-box attacks cannot find a small enough perturbation for regular models. Again, we still don’t know whether this is because of the vulnerability of adversarially trained models or because of the poor performance of the black-box attacks.\nI suggest the authors check the average perturbation sizes to show that the black-box attacks do not perform poorly against the adversarially trained model.\n2.\tFirst, robustness gain is only briefly described in the introduction and I cannot see any formal definition of it. Even though experiments are the only way to compute the robustness gain, it is better to describe it formally (an ideal & theoretical definition. If there is any reference that supports the concept, cite it.) and explain the intuition behind the concept.\nSecond, more details are needed for the robustness gain experiment. The main motivation for this experiment is unclear. $\\eta$ (which must be the robustness gain) was not defined before it is mentioned.\n3.\tLastly, I don’t think that robustness gain is a good measure to make comparisons. This is because the robustness gain is a ratio so it can be decreased by the poor performances of black-box attacks against a regular model. In other words, it is unclear whether the results come from the vulnerability of an adversarially trained model against black-box attacks or the results just come from the poor performance of the attacks against a regular model.\n", "summary_of_the_paper": "First, this paper a new black-box attack method that can avoid a query similarity detector for an attempt to generate an adversarial example. Second, based on a set of experiments, the paper tries to show that an adversarially trained classifier is potentially more vulnerable against (black-box) adversarial attacks, which can be justified by the smooth decision boundary induced by the adversarial training. ", "summary_of_the_review": "While the new attack method seems interesting, it could be a hasty conclusion that the adversarially trained model is “more vulnerable” to black-box attacks. I suggest either making a weaker conclusion or strengthening the theoretical & experimental supports to the conclusion. Because of this concern, I’m a bit cautious to say that we should accept this paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "ArHZXU0HA1", "reviewer": "Reviewer_S9ch", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "This paper considers a less studied aspect of adversarial attack that the input points are not independent and a defender can utilize this information for better detection. The proposed method is simple yet effective. However, I have the following concerns:\n1. The paper only considers untargeted attacks. There are already many successful black-box untargeted adversarial attacks by utilizing the transferability between models. It is not very convincing why the query-based approach is better? On the other hand, targeted transferability is less significant, so I suggest that the authors also study whether the proposed approach is applicable to targeted attacks.\n2. The authors only use a single-step attack, which can result in larger perturbation and thus may be detected. In this sense, although the proposed method can evade the detection from the similarity detector, it can be more easily detected by other detectors (e.g., anomaly detector).\n3. I am skeptical whether a similarity detector is commonly used in real applications. This would require huge storage and computation cost, and it may cause some privacy issues for storing private user data. \n4. Only one network architecture (ResNet-50) is used in experiments. Are the findings generalizable to other architectures?", "summary_of_the_paper": "This paper proposes a query-based black-box adversarial attack that can only query a model with the class output.\nThe main consideration is to avoid sending very similar query points to evade the detection of a KNN-based detector.\nThe proposed method is parallelizable and less likely to be detected by a similarity-based detector.", "summary_of_the_review": "Interesting idea but limited impact in real-world scenarios.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a novel black-box attack aiming to fool a particular detector model. All reviewers see problems in the claims, the experiments etc and all argue for rejection. The authors did not provide a rebuttal to clarify any of the questions of the reviewers. Thus this is a clear reject.
Decision: Reject