ON THE EXPLOITATIVE BEHAVIOR OF ADVERSARIAL TRAINING AGAINST ADVERSARIAL ATTACKS
Year: 2021

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 improve the robustness of image 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 blackbox attacks. In particular, we introduce a highly parallelizable black-box attack against classifiers equipped with an `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 whitebox attack setting, it may not provide such a good robustness gain against the more realistic decision-based black-box attacks.

heading: 1 INTRODUCTION
text: It is known in the literature that adversarial training can make deep neural networks more robust Madry et al. (2018); Shafahi et al. (2019); Wong et al. (2019) against adversarial attacks Goodfellow et 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 Athalye et al. (2018). Moreover, it is empirically shown in Moosavi-Dezfooli 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-box setting Carlini & Wagner (2017); Goodfellow et al. (2014); Moosavi-Dezfooli et al. (2016), score-based black-box setting Chen et al. (2017); Ilyas et al. (2018); Narodytska & Kasiviswanathan (2016) or decision-based black-box setting Brendel et al. (2018); Chen et al.; Cheng et al. (2019); Liu et al. (2019); Rahmati et al. (2020). The attacker’s level of information about the classifier plays a key role on the quality of the generated adversarial examples. In order to craft an adversarial perturbation in a decision-based black-box setting, the critical information is mostly the normal vector to the decision boundary. In this setting, the estimation of the normal vector is conducted with carefully designed fine-tuned queries at a boundary point of the image classifier, usually based on the linearization of the boundary. Chen et al.; Cheng et al. (2019); Liu et al. (2019); Rahmati et al. (2020). The objective of such black-box attacks is typically to reduce the number of queries as much as possible with an efficient estimate of the normal vector. However, to make sure that this linearization approximation is valid at a boundary point, the `2 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 et al. (2020). Moreover, the efficient estimation of the normal to 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-Dezfooli et al. (2019). 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); Moosavi-Dezfooli et al. (2019). We will show that this characteristic of the adversarially-trained networks indeed gives an edge to black-box attacks.
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-norm perturbation whitebox attacks, it becomes less effective in more practical attack settings. In particular, we propose a parallelizable attack against classifiers equipped with an `2 norm similarity detector to demonstrate that adversarially-trained networks might even be fooled with smaller `2 norm for a 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 a metric called robustness gain as the ratio of `2 norm of adversarial perturbation required to fool the adversarially-trained 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 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 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 a query similarity detector based on `2 norm. Using normal vectors estimated at multiple points on the boundary, we develop an attack which is, interestingly, more effective against an adversarially-trained network as compared to a regular network.
• We define a metric called robustness gain as the ratio of `2 norm of adversarial perturbations 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 attacks, it may not provide a good robustness gain against black-box attacks.
The rest of the paper is organized as follows. In Section 3, the problem setting, the similarity detector, 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 is analyzed for the adversarially-trained network compared to the regular one. In Section 5, we evaluate the effectiveness of adversarial training against a minimum perturbation white-box attack and finally Section 6 concludes the paper.

heading: 2 RELATED WORK
text: Adversarial Training The basic idea of adversarial training is to create and then incorporate adversarial examples into the training process Szegedy et al. (2013); Goodfellow et al. (2014). In Madry et al. (2018), authors show an effective version of an adversarially-trained network to improve robustness against white-box attacks. In Shafahi et al. (2019), the authors proposed a 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. Recently, in Wong et al. (2019), 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. 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-Dezfooli et al. (2016); Szegedy et al. (2013), score-based black-box setting Chen et al. (2017); Ilyas et al. (2018); Narodytska & Kasiviswanathan (2016) or decision-based black-box scenarios Brendel et al. (2018); Chen et al.; Cheng et al. (2019); Liu et al. (2019); Rahmati et 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 locally approximated the decision boundary with a hyper-plane, and searched the closest point on the hyper-plane to the benign input as the perturbation.
Black-box defenses The generation of an 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 a similarity across multiple queries. In Chen et al. (2020), authors propose to equip an existing classifier with a detection component, which stores the similarity vectors for all incoming queries, computed by a pre-trained similarity encoder. For each new query, it computes the k-nearest-neighbor distance between it and all other vectors in the memory. Blacklight Li et al. (2020) computes a 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 Byun et al. (2021), the authors introduce Small Noise Defense (SND) in which even a small additive input noise can neutralize most query-based attacks.

heading: 3 PROBLEM STATEMENT AND MULTI-POINT ATTACK
text: Motivation and background One of the most challenging settings to perform adversarial attack to image classifiers is 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 a request that results in the top-1 label of an image classifier for a given input. The state-of-the-art attacks try to obtain the smallest possible `p norm of the perturbations with efficient use of queries to the image classifier Brendel 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 `2 similarity detector by taking advantage of the low mean curvature of the decision boundary of state-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 `2 distance to make sure the linearization assumption is valid. However, such similar queries can be simply detected by a k nearest neighbour (KNN) similarity detector with k N , where N is the query budget for the attacker. Thus, the k nearest neighbours of the given query i are obtained among the queries stored in a buffer. In particular, for a given query i, the classifier computes the average `2 distance between the query i and its k nearest neighbors di defined as in Chen et al. (2020):
di = 1
k k∑ t=1 di,t, (1)
where di,t is the `2 distance of the given query iwith its nearest neighbours twhere 1 ≤ t ≤ k. Then, by introducing the detection threshold δ, if di < δ, an attack is detected and the user is blocked. The value for δ 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 complexity 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. (2019), and qFool Liu et al. (2019). We stress here that the goal of the paper is not to outperform the state-of-the-art 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 a way to design a parallelizable attack to generate a query-efficient `2-norm-minimized perturbation with totalN queries against a classifier equipped with a similarity detector of k nearest neighbours with threshold δ?
We show that the answer to this question is affirmative and introduce a multi-point normal estimator which evades the similarity detector.
Problem statement We consider a trained L-class classifier with parameters θ represented as f : Rd → RL, where x ∈ Rd is the input image and k̂(x) = argmaxk fk(x) is the top-1 classification label where fk(x) is the k-th component of f(x) corresponding to the k-th class. The attacker’s goal is to minimize the `2 norm as much as possible with a limited budget of N queries while it cannot get detected with the similarity detector. We define the optimization problem as:
min v
‖v‖2 (2)
s.t. k̂(x+ v) 6= k̂(x), di > δ, ∀i ≤ N.
The last constraint ensures that the queries are not detected by the `2 similarity detector. Without the similarity detector constraint, problem equation 2 is already solved in the literature with different approaches Brendel et al. (2018); Chen et al.; Cheng et al. (2019); Liu et al. (2019); Rahmati et al. (2020). The main idea is to obtain a point on the boundary of the image classifier and estimate the normal to the decision boundary at this point. However, with the presence of the similarity detector, the normal vector estimation becomes more challenging for the attacker as it can not generate large number of queries with small `2 norms to the neural network.

heading: 3.1 MULTI-POINT NORMAL VECTOR ESTIMATOR
text: We employ the fact that the decision boundaries of 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 equation 2, we locally approximate the boundary of image classifier at multiple boundary points with a hyperplane as:
min v
‖v‖2 (3)
s.t. wT (x+ v)−wTxB,j = 0, ∀j ≤M di > δ, ∀i ≤ N,
where xB,j is the j-th boundary point and M is the number of boundary points obtained using a binary search. Having a single boundary point M = 1 and spend all N queries at xB,1 to 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 at each iteration the boundary points distances decreases. Thus, we need to design an estimator in which the queries cannot be detected by the similarity detector.
Multi-point normal estimator To alleviate the aforementioned problem, we propose the multipoint normal vector estimator in which the queries are generated on multiple boundary points (M 1). The key idea is to distribute N queries to estimate the normal vector to the boundary using multiple boundary points, rather than spending all N queries on just a single point. Apparently, a considerable portion of queries are allocated to obtain the boundary points along with binary search. This is the cost imposed by query detector to the attackers. This estimator is both parallelizable and, as we will see, successful against a classifier equipped with an `2 similarity detector.
As seen in Fig. 1, starting from the original image x0, one can find M points on the boundary denoted by xB,1,xB,2, . . . ,xB,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
Algorithm 1: Multi-point attack 1 Inputs: Original image x0, query budget N . 2 Output: Adversarial example xadv. 3 Obtain the optimal number of boundary points M∗ by M∗ = N−βk−b−γ∗ . 4 Obtain M∗ starting point on the boundary xB,1,xB,2, . . . ,xB,M∗ . 5 Estimate normal ŵ with equation 5. 6 Push the original image x0 towards the boundary in the direction of ŵ. 7 r̂ ← min{r′ > 0 : k̂(x0 + r′ŵ) 6= k̂(x)} 8 xadv ← x0 + r̂ŵ
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 di for a given query i 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 k nearest neighbours to compute di for each query i. Here, without loss of generality, we assume that the closest boundary point to xi is xB,j . The similarity detector observes three types of queries when computing its k nearest neighbours for query i. 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 xB,j . Finally, the type three distances for query xi are obtained between the xi and its second closest boundary point to xi. At each boundary point xB,j , 1 ≤ j ≤M , the attacker can allocate n = k−b−γ queries to estimate the normal to the boundary at point xB,j , 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:
M = N − β k − b− γ
(4)
where β is the number of queries required to push the x0 towards the direction of the estimated normal vector towards the boundary (step 6 of the Algorithm 1). At each boundary point j, the boundary is locally approximated with a hyperplane wTj (x − xB,j) = 0. In order to estimate the normal vector wj , the key idea is to generate n samples ζi, i ∈ {1, . . . , n} from a multivariate normal distribution ζi ∼ N (0,Σ) which results in queries with the form of xB,j + ζi, ∀i ∈ N Rahmati et al. (2020). The estimator ŵj of wj with n queries is ŵj = 1n ∑n i=1 ziζi, where zi = 1 if k̂(xB,j + ζi) 6= k̂(xB,j) and otherwise zi = −1. Eventually, the average normalized direction of estimated normal vector over all the boundary points can be given as:
ŵ = ΣMj=1ŵj
‖ΣMj=1ŵj‖ . (5)
After estimating the normal to the boundary ŵ, we push the original image x0 towards the boundary in the direction of ŵ with amplifying the magnitude of the vector. The final multi-point attack is summarized in Algorithm 1.

heading: 3.2 NUMBER OF BOUNDARY POINTS
text: In this section, our goal is to have an estimate for the optimal number of boundary points. The number of boundary pointsM 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 k and δ. 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 k nearest neighbour queries and their distances to xi can be categorized into three types. We aim to have an estimate for the optimal number of boundary points. For more details about mean distance of queries (µi), refer to Appendix A.1.
Having the mean distances (µi) of queries in hand, the attacker can have an estimate on the number of type II queries at each boundary point to get an 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 detect the queries due to the small di. Moreover, it should not be too small to incur excessive overhead in finding boundary points. Thus:
di = 1
k k∑ t=1 di,t = 1 k (bµ1 + nµ2 + γµ3) = δ + λ, (6)
where λ is a margin to the threshold to make sure that the average distance can not be detected by the similarity detector. We may ignore the nµ2 term as it is typically small compared to µ1 and µ3. Having this approximation, the optimal value for γ can be obtained as γ∗ = k(δ+λ)−bµ1µ3 : It simply can be seen that if µ3 is large, then the number of type II queries n per boundary point increases which results in more efficient deployment of queries. The optimal number of boundary points can be obtained by plugging γ∗ into equation 4 as M∗ = N−β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 di = δ + λ decreases as well.

heading: 4 EFFECTIVENESS OF ADVERSARIALLY-TRAINED NETWORKS AGAINST BLACK-BOX ATTACKS
text: 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-trained 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’s validation set Deng et al. (2009).

heading: 4.1 MULTI-POINT ATTACK AGAINST SIMILARITY DETECTOR
text: Here, we evaluate the performance of our novel multi-point attack and an iterative attack1 (GeoDA Rahmati et al. (2020)) on an adversarially-trained network equipped with an `2 similarity detector in Fig 2a. For the similarity detector, we assume k = 100, δ = 5, ζ = 5. We also set nrbst = 45 and nreg = 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 KNN mean drops quickly below δ + ζ. However, the multi-point attack by-pass the similarity detector by keeping the KNN mean di,∀i greater than the detection threshold by distributing the queries over the distant boundary points.
In Fig. 2b, we compare the `2 norm of single-point attack (M = 1, which is highly parallelizable, but not successful against the similarity detector) and our proposed multi-point attack on both regular and adversarially-trained networks with respect to number queries. For the single iteration attack, the performance of attack on regular network is better compared to the robust network as expected. However, for the extension to multi-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-trained 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.
The reasons behind the above observations are twofold. First, it is quite intuitive that the 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 hyperplane are in the same direction. Thus, this results in a 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).
1Note that most of the state of the art attacks in which they estimate the normal to the decision boundary are iterative and follow the similar procedure. Thus, comparing with one of them is sufficient for this experiment.
Second, as shown in equation 9, the larger the type III mean distance µ3 is, the less number of type III queries γ∗ is needed to satisfy equation 8. In equation 4, the larger γ∗ 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 1 that the mean distance of the points on the boundary µ3 is larger for the adversarially-trained network compared to the one for regular network. As discussed above, this can reduce the number of required boundary points to satisfy di = δ + λ in equation 8 which benefits the attacker. Thus, we have µrbst3 > µ reg 3 which leads to γrbst < γreg in equation 9 and also M rbst < M reg. As a result in equation 4, we have nrbst > nreg which results in larger number of queries at each boundary point. The smaller number of boundary points is beneficial for the attacker as it can save on average b queries per boundary point. Moreover, larger number of queries at each boundary point nrbst > nreg 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) Brendel et al. (2018) on both regular and robust ResNet-50 networks in Fig. 3a. For a given query budget, the `2 norm of perturbations for the attacks against the robust network is larger compared to that of the regular network as expected. However, an interesting observation is that while GeoDA has almost the same `2 norm as HSJA for the regular network, it provides smaller `2 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 a low mean curvature. On the other hand, adversarially trained-networks has flatter decision boundaries which actually gives an edge to 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 adversarially-trained networks can improve the robustness under various kind of attacks. We plot the robustness gain for different attacks in Fig. 3b. The larger the η 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 η is equal to around 17 (see Table 2) for the white-box attack DeepFool (DF) Moosavi-Dezfooli et al. (2016) which is a quite good improvement. Having a black-box setting, we evaluate the η for HSJA Chen et al., GeoDA Rahmati et al. (2020), boundary attack Brendel et al. (2018), single iteration and multipoint 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, η 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 adversarially-trained network can improve the robustness. That being said, adversarial training for the deep image classifiers is much more effective for white-box scenarios.
Mean distance of boundary points The mean distance of boundary points µ3 is a critical design parameter for the multi-point attack as it determines the number for boundary points. Here, we have done experiments to measure the µ3 for both networks with different number of boundary pointsM . We start with a boundary point xB,1 and obtain the `2 norm to this point from all other boundary
points. The average of such a distance over 300 correctly classifier images by both networks is reported in Table 1. It is observed that the µ3 is large for the robust network compared to that of regular network. Moreover, we can see that the value of µ3 even for M = 2 is very close to the true mean. Thus, the estimate of the µ3 can be cheaply obtained with only M = 2 since in the high-dimensional regime, the `2 distances are close enough.

heading: 5 ADVERSARIAL TRAINING AGAINST MINIMAL-NORM PERTURBATION WHITE-BOX ATTACK
text: We already discussed the effectiveness of the adversarially-trained network with respect to number 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 a minimal `2 norm perturbation white-box attack. To this end, we choose a minimal `2 norm white-box attack DeepFool Moosavi-Dezfooli et al. (2016) and compare its performance on an adversarially-trained Madry et al. (2018) and a regular ResNet-50 in Table 2.
DeepFool performance To this end, we choose a minimal `2 norm white-box attack DeepFool Moosavi-Dezfooli et al. (2016) and compare its performance on an adversarially-trained Madry et al. (2018) and a regular ResNet-50 in Table 2. The main reason we choose DeepFool is its dependence 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 the image classifier is, the fewer iterations required for DeepFool to converge. Interestingly, despite that the adversarially-trained network has perturbations with larger `2 norm, due to the more linear behavior of its output function, DeepFool converges faster on this network. In this sense, one can conclude that it is easier to attack adversarially-trained networks even in the white-box setting.
DeepFool iterations behaviour In this experiment, the goal is to qualitatively study the behaviour of output function along the trajectory of the iterations of DF for a single data point. In this case,
DeepFool requires 3 and 5 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 = x0+t(xadv−x0), where t = 0 corresponds to the original image and t = 1 gives the adversarial image which falls on 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 on the boundary the difference is equal to zero and the transition occurs. Assuming xi as the output of DF in iteration i, each line segment i (i.e. black and red segments in Figs. 4a and 4b) is corresponding to the images on the line x = x(i−1) + t(xi − x(i−1)) for t ∈ [0, 1], where xi = xadv if i 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-trained network compared to that of regular network. Second, it 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 a result, although the adversarial training improved the robustness (increases the minimal `2 norm), it provide an opportunity for the attacker to attack easier (with less number of iterations to converge) due to more linear behaviour of adversarially-trained networks.
Non-linearity of the output The goal is to see how the output of the classifier behaves when we push the image towards the boundary. In Fig. 4c the adversarial example is obtained using DeepFool, while in Fig. 4d the adversarial point is obtained 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-linearity 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.

heading: 6 CONCLUSION
text: We showed that although the adversarial training is quiet effective against white-box attacks, in query-limited decision-based black-box attacks, it 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, it 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-trained networks can also provide a chance for minimal norm perturbation whitbox attacks to produce adversarial examples with less number of iterations. We introduced a highly parallelizable attack which can be successful against a similarity detector that can fool the robust network even easier compared to the regular classifier.

heading: A APPENDIX
text: 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 pointsM 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 k and δ. 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 k nearest neighbour queries and their distances to xi can be categorized into three types. In this section, we compute the average distance of each type of queries to xi.
• 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 `2 norm and pushing it towards the boundary with binary search. The average distance of such queries with given query xi can be computed as µ1 = 1b ∑b t=1 ‖xi − xt‖. Obtaining
the exact µ1 can be complicated and not even necessary. Instead, we approximate it with µ1 = ‖xi − xB,j‖ where xB,j is the nearest boundary point to xi. Please note that b is number of queries required for binary search. It could be determined after obtaining the first boundary point.
• Type II: The type II queries are the ones generated on 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 a given type II query xi ∼ N (xB,j , σ2I). The nearest queries of the type II xt has the same multivariate Gaussian distribution y = zTz in which z =
xi − xt follows a Gamma distribution Y ∼ Γ(α, β) with α = N/2, β = 4σ2. Thus, di,t = √ y has a G ∼ Nakagami(m,Ω) distribution where m = N/2 and Ω = 2Nσ2. Therefor the mean distance of the Type II queries is given by:
µ2 = Γ ( m+ 12 ) Γ(m) ( Ω m )1/2 . (7)
• 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, µ3 = 1M ∑M t=1 ‖xB,j − xB,t‖, 1 ≤ t ≤M .
Having the above information in hand, the attacker can have an estimate on the number of type II queries at each boundary point to get an 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 di. Moreover, it should not be too small to incur excessive overhead in finding boundary points. Thus, we have:
di = 1
k k∑ t=1 di,t = 1 k (bµ1 + nµ2 + γµ3) = δ + λ, (8)
where λ is a margin to the threshold to make sure that the average distance can not be detected by the similarity detector. We may ignore the nµ2 term as it is typically small compared to µ1 and µ3. Having this approximation, the optimal value for γ can be obtained as:
γ∗ = k(δ + λ)− bµ1
µ3 . (9)
It simply can be seen that if µ3 is large, then the number of type II queries n per boundary point increases which results in more efficient deployment of queries. The optimal number of boundary points can be obtained by plugging γ∗ into equation 4 as M∗ = N−β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 di = δ + λ decreases as well.

Review summaries:
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.

This paper proposes a query-based black-box adversarial attack that can only query a model with the class output. The main consideration is to avoid sending very similar query points to evade the detection of a KNN-based detector. The proposed method is parallelizable and less likely to be detected by a similarity-based detector.

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.   The 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.   The 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.   The 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.