Exploring the Space of Black-box Attacks on Deep Neural Networks
Arjun Nitin Bhagoji Warren He Bo Li Dawn Song
cs.LG cs.CR cs.CV



Model independent evaluation of the Wilson coefficient 
 of the Weinberg operator in QCD
    Ryo Nagai
    December 30, 2023
========================================================================================

































































 Existing black-box attacks on deep neural networks (DNNs) so far have largely focused on transferability, where an adversarial instance generated for a locally trained model can “transfer” to attack other learning models. In this paper, we propose novel black-box attacks for adversaries with query access to the target model's class probabilities, which do not rely on transferability. We also propose strategies to decouple the number of queries required to generate each adversarial sample from the dimensionality of the input. An iterative variant of our attack achieves close to 100% adversarial success rates for both targeted and untargeted attacks on DNNs. We carry out extensive experiments for a thorough comparative evaluation of black-box attacks and show that the proposed attacks outperform all transferability based black-box attacks we tested on both MNIST and CIFAR-10 datasets, achieving adversarial success rates similar to well known, state-of-the-art white-box attacks. We also apply the attacks successfully against a real-world Content Moderation classifier hosted by Clarifai. Furthermore, we evaluate black-box attacks against state-of-the-art defenses. We show that the attacks are very effective even against these defenses.




§ INTRODUCTION

The ubiquity of machine learning provides adversaries with both opportunities and incentives to develop strategic approaches to fool learning systems and achieve their malicious goals. Many attack strategies devised so far to generate adversarial examples to fool learning systems have been in the white-box setting, where adversaries are assumed to have access to the learning model (<cit.>). However, in many realistic settings, adversaries may only have black-box access to the model, i.e. they have no knowledge about the details of the learning system such as its parameters, but they may have query access to the model's predictions on input samples, including class probabilities. For example, we find this to be the case in some popular commercial AI offerings, such as those from IBM, Google and Clarifai. With access to query outputs such as class probabilities, the training loss of the target model can be found, but without access to the entire model, the adversary cannot access the gradients required to carry out white-box attacks.

Most existing black-box attacks on DNNs have focused on transferability based attacks (<cit.>), where adversarial examples crafted for a local surrogate model can be used to attack the target model to which the adversary has no direct access. The exploration of other black-box attack strategies is thus somewhat lacking so far in the literature. In this paper, we design powerful new black-box attacks using limited query access to learning systems which achieve adversarial success rates close to that of white-box attacks. These black-box attacks help us understand the extent of the threat posed to deployed systems by adversarial samples. The code to reproduce our results can be found at <https://github.com/sunblaze-ucb/blackbox-attacks>.

New black-box attacks. We propose novel  attacks on DNNs, where the adversary is only assumed to have query access to the target model. These attacks do not need any access to a representative dataset or any knowledge of the target model architecture. In the attacks, the adversary adds perturbations proportional to the estimated gradient, instead of the true gradient as in white-box attacks (<cit.>). 
Since the direct attack requires a number of queries on the order of the dimension of the input, we explore strategies for reducing the number of queries to the target model. We also experimented with Simultaneous Perturbation Stochastic Approximation (SPSA) and Particle Swarm Optimization (PSO) as alternative methods to carry out query-based black-box attacks but found to work the best. 

Query-reduction strategies We propose two strategies: random feature grouping and principal component analysis (PCA) based query reduction. In our experiments with the attacks on state-of-the-art models on MNIST (784 dimensions) and CIFAR-10 (3072 dimensions) datasets, we find that they match white-box attack performance, achieving attack success rates up to 90% for single-step attacks in the untargeted case and up to 100% for iterative attacks in both targeted and untargeted cases. We achieve this performance with just 200 to 800 queries per sample for single-step attacks and around 8,000 queries for iterative attacks. This is much fewer than the closest related attack by <cit.>. While they achieve similar success rates as our attack, the running time of their attack is up to 160 × longer for each adversarial sample (see Section <ref>). A further advantage of the attack is that it does not require the adversary to train a local model, which could be an expensive and complex process for real-world datasets, in addition to the fact that training such a local model may require even more queries based on the training data. 



Attacking real-world systems. To demonstrate the effectiveness of our attacks in the real world, we also carry out a practical black-box attack using these methods against the Not Safe For Work (NSFW) classification and Content Moderation models developed by <cit.>, which we choose due to their socially relevant application. These models have begun to be deployed for real-world moderation <cit.>, which makes such black-box attacks especially pernicious. We carry out these attacks with no knowledge of the training set. We have demonstrated successful attacks (Figure <ref>) with just around 200 queries per image, taking around a minute per image. In Figure <ref>, the target model classifies the adversarial image as `safe' with high confidence, in spite of the content that had to be moderated still being clearly visible. We note here that due to the nature of the images we experiment with, we only show one example here, as the others may be offensive to readers. The full set of images can be found at <https://sunblaze-ucb.github.io/blackbox-attacks/>. 

Comparative evaluation of black-box attacks. We carry out a thorough empirical comparison of various black-box attacks (given in Table <ref>) on both MNIST and CIFAR-10 datasets. We study attacks that require zero queries to the learning model, including the addition of perturbations that are either random or proportional to the difference of means of the original and targeted classes, as well as various transferability based black-box attacks. We show that the proposed attacks outperform other black-box attacks in terms of attack success rate and achieve results comparable with white-box attacks.

 In addition, we also evaluate the effectiveness of these attacks on DNNs made more robust using adversarial training <cit.> and its recent variants including ensemble adversarial training <cit.> and iterative adversarial training <cit.>. We find that although standard and ensemble adversarial training confer some robustness against single-step attacks, they are vulnerable to iterative attacks, with adversarial success rates in excess of 70% for both targeted and untargeted attacks. We find that our methods outperform other black-box attacks and achieve performance comparable to white-box attacks. Iterative adversarial training is quite robust against all black-box attacks we test.
 
In summary, our contributions include: 


  * We propose new black-box attacks using queries to the target model. We also investigate two methods to make the number of queries needed independent of the input dimensionality.

  * We conduct a thorough evaluation of 10 different black-box attack strategies on state-of-the-art classifiers on the MNIST and CIFAR-10 datasets, and we find that with a small number of queries, our proposed attacks outperform transferability based attacks and achieve attack success rates matching those of white-box attacks. 

  * We carry out practical black-box attacks on Clarifai's Not Safe For Work (NSFW) classification and Content Moderation models through public APIs, and show that the generated adversarial examples can mislead these models with high confidence. 

  * Finally, we evaluate these black-box attacks against state-of-the-art adversarial training based defenses on DNNs, and we find that both standard and ensemble adversarial training are not robust against attacks. Further, even against iterative adversarial training our methods outperform transferability based attacks.


 Related Work. Existing black-box attacks that do not use a local model were first proposed for convex inducing two-class classifiers by <cit.>. For malware data, <cit.> use genetic algorithms to craft adversarial samples, while <cit.> use hill climbing algorithms. These methods are prohibitively expensive for non-categorical and high-dimensional data such as images. <cit.> proposed using queries to a target model to train a local surrogate model, which was then used to to generate adversarial samples. This attack relies on transferability. To the best of our knowledge, the only previous literature on query-based black-box attacks in the deep learning setting is independent work by <cit.> and <cit.>. 

 <cit.> propose a greedy local search to generate adversarial samples by perturbing randomly chosen pixels and using those which have a large impact on the output probabilities. Their method uses 500 queries per iteration, and the greedy local search is run for around 150 iterations for each image, resulting in a total of 75,000 queries per image, which is much higher than any of our attacks. Further, we find that our methods achieve higher targeted and untargeted attack success rates on both MNIST and CIFAR-10 as compared to their method. <cit.> propose a black-box attack method named ZOO, which also uses the method of finite differences to estimate the derivative of a function. However, while we propose attacks that compute an adversarial perturbation, approximating FGSM and iterative FGS; ZOO approximates the Adam optimizer, while trying to perform coordinate descent on the loss function proposed by <cit.>. Neither of these works demonstrates the effectiveness of their attacks on real-world systems or on state-of-the-art defenses.



§ BACKGROUND AND EVALUATION SETUP

In this section, we will first introduce the notation we use throughout the paper and then describe the evaluation setup and metrics used in the remainder of the paper. The full set of attacks that was evaluated is given in Table <ref> in Appendix <ref>, which also provides a taxonomy for black-box attacks.



 §.§ Notation
 
A classifier f(·;θ): 𝒳→𝒴 is a function mapping from the domain 𝒳 to the set of classification outputs 𝒴.  (𝒴={0,1} in the case of binary classification, i.e. 𝒴 is the set of class labels.) The number of possible classification outputs is then |𝒴|. θ is the set of parameters associated with a classifier. Throughout, the target classifier is denoted as f(·;θ), but the dependence on θ is dropped if it is clear from the context. ℋ denotes the constraint set which an adversarial sample must satisfy. ℓ_f(,y) is used to represent the loss function for the classifier f with respect to inputs ∈𝒳 and their true labels y ∈𝒴. The loss functions we use are the standard cross-entropy loss (denoted xent) and the logit loss from <cit.> (denoted as logit). These are described in Section <ref>. 

An adversary can generate adversarial example  from a benign sample  by adding an appropriate perturbation of small magnitude <cit.>.
Such an adversarial example  will either cause the classifier to misclassify it into a targeted class (targeted attack), or any class other than the ground truth class (untargeted attack).

Since the black-box attacks we analyze focus on neural networks in particular, we also define some notation specifically for neural networks. The outputs of the penultimate layer of a neural network f, representing the output of the network computed sequentially over all preceding layers, are known as the logits. We represent the logits as a vector ^f() ∈ℝ^|𝒴|. The final layer of a neural network f used for classification is usually a softmax layer represented as a vector of probabilities 𝐩^f(𝐱)=[p_1^f(𝐱), …, p_|𝒴|^f(𝐱)], with ∑_i=1^|𝒴| p_i^f() =1 and p_i^f() = e^_i^f()/∑_j=1^|𝒴|e^_j^f().



 §.§ Evaluation setup
 

The empirical evaluation carried out in Sections <ref> and <ref> is on state-of-the-art neural networks on the MNIST <cit.> and CIFAR-10 <cit.> datasets. The details of the datasets and the architecture and training procedure for all models are given below.




  §.§.§ Datasets

MNIST.
This is a dataset of images of handwritten digits <cit.>. There are 60,000 training examples and 10,000 test examples. Each image belongs to a single class from 0 to 9. The images have a dimension d of 28 × 28 pixels (total of 784) and are grayscale. Each pixel value lies in [0,1]. The digits are size-normalized and centered. This dataset is used commonly as a `sanity-check' or first-level benchmark for state-of-the-art classifiers. We use this dataset since it has been extensively studied from the attack perspective by previous work.

CIFAR-10.
This is a dataset of color images from 10 classes <cit.>. The images belong to 10 mutually exclusive classes (airplane, automobile, bird, cat, deer, dog, frog, horse, ship, and truck). There are 50,000 training examples and 10,000 test examples. There are exactly 6,000 examples in each class. The images have a dimension of 32 × 32 pixels (total of 1024) and have 3 channels (Red, Green, and Blue). Each pixel value lies in [0,255].



  §.§.§ Model training details
 
In this section, we present the architectures and training details for both the normally and adversarially trained variants of the models on both the MNIST and CIFAR-10 datasets. The accuracy of each model on benign data is given in Table <ref>.

MNIST.
Each pixel of the MNIST image data is scaled to [0,1]. We trained four different models on the MNIST dataset, denoted Models A to D, which are used by <cit.> and represent a good variety of architectures. For the attacks constrained with the L_∞ distance, we vary the adversary's perturbation budget ϵ from 0 to 0.4, since at a perturbation budget of 0.5, any image can be made solid gray. The model details for the 4 models trained on the MNIST dataset are as follows:

    
  *  (3,382,346 parameters): Conv(64, 5, 5) + Relu, Conv(64, 5, 5) + Relu, Dropout(0.25), FC(128) + Relu, Dropout(0.5), FC + Softmax
    
  *  (710,218 parameters) - Dropout(0.2), Conv(64, 8, 8) + Relu, Conv(128, 6, 6) + Relu, Conv(128, 5, 5) + Relu, Dropout(0.5), FC + Softmax
    
  *  (4,795,082 parameters) - Conv(128, 3, 3) + Relu, Conv(64, 3, 3) + Relu, Dropout(0.25), FC(128) + Relu, Dropout(0.5), FC + Softmax    
  *  (509,410 parameters) - [FC(300) + Relu, Dropout(0.5)] × 4, FC + Softmax 

Models  and  have both convolutional layers as well as fully connected layers. They also have the same order of magnitude of parameters. , on the other hand, does not have fully connected layers and has an order of magnitude fewer parameters. Similarly,  has no convolutional layers and has fewer parameters than all the other models.
Models , , and  all achieve greater than 99% classification accuracy on the test data.  achieves 97.2% classification accuracy, due to the lack of convolutional layers.

CIFAR-10.
Each pixel of the CIFAR-10 image data is in [0,255]. We choose three model architectures for this dataset, which we denote as ,  (ResNet variants <cit.>), and . For the attacks constrained with the L_∞ distance, we vary the adversary's perturbation budget ϵ from 0 to 28.

As their name indicates,  and  are ResNet variants <cit.>, while  is a standard CNN <cit.>. In particular,  is a standard 32 layer ResNet with no width expansion, and  is a wide ResNet with 28 layers with the width set to 10, based on the best performing ResNet from  <cit.>. The width indicates the multiplicative factor by which the number of filters in each residual layer is increased.  is a standard CNN[<https://github.com/tensorflow/models/tree/master/tutorials/image/cifar10>] from Tensorflow <cit.> with two convolutional layers, each followed by a max-pooling and normalization layer and two fully connected layers, each of which has weight decay. 

is trained for 125,000 steps, is trained for 167,000 steps and is trained for 100,000 steps on the benign training data. Models and are much more accurate than . All models were trained with a batch size of 128. The two ResNets achieve close to state-of-the-art accuracy <cit.> on the CIFAR-10 test set, with  at 92.4% and  at 94.4%. , on the other hand, only achieves an accuracy of 81.4%, reflecting its simple architecture and the complexity of the task. 



 §.§ Metrics

Throughout the paper, we use standard metrics to characterize the effectiveness of various attack strategies. For MNIST, all metrics for single-step attacks are computed with respect to the test set consisting of 10,000 samples, while metrics for iterative attacks are computed with respect to the first 1,000 samples from the test set. For the CIFAR-10 data, we choose 1,000 random samples from the test set for single-step attacks and a 100 random samples for iterative attacks.
In our evaluations of targeted attacks, we choose target T for each sample uniformly at random from the set of classification outputs, except the true class y of that sample.

Attack success rate.
The main metric, the attack success rate, is the fraction of samples that meets the adversary's goal:
f() ≠ y for untargeted attacks and f()=T for targeted attacks with target T <cit.>. Alternative evaluation metrics are discussed in Appendix <ref>.  

Average distortion.
We also evaluate the average distortion for adversarial examples using average L_2 distance between the benign samples and the adversarial ones as suggested by <cit.>:

   Δ(,) = 1/N∑_i=1^N ()_i - ()_i_2

where N is the number of samples. This metric allows us to compare the average distortion for attacks which achieve similar attack success rates, and therefore infer which one is stealthier.

Number of queries. Query based black-box attacks make queries to the target model, and
this metric may affect the cost of mounting the attack. This is an important consideration when attacking real-world systems which have costs associated with the number of queries made.



§ QUERY BASED ATTACKS: ATTACK

Deployed learning systems often provide feedback for input samples provided by the user. Given query feedback, different adaptive, query-based algorithms can be applied by adversaries to understand the system and iteratively generate effective adversarial examples to attack it. Formal definitions of query-based attacks are in Appendix <ref>. We initially explored a number of methods of using query feedback to carry out black-box attacks including Particle Swarm Optimization <cit.> and Simultaneous Perturbation Stochastic Approximation <cit.>. However, these methods were not effective at finding adversarial examples for reasons detailed in Section <ref>, which also contains the results obtained. 

Given the fact that many white-box attacks for generating adversarial examples are based on gradient information, we then tried directly estimating the gradient to carry out black-box attacks, and found it to be very effective in a range of conditions. In other words, the adversary can approximate white-box Single-step and Iterative FGSM attacks <cit.> using estimates of the losses that are needed to carry out those attacks.  We first propose a black-box attack based on the method of finite differences <cit.>. The drawback of a naive implementation of the finite difference method, however, is that it requires O(d) queries per input, where d is the dimension of the input. This leads us to explore methods such as random grouping of features and feature combination using components obtained from Principal Component Analysis (PCA) to reduce the number of queries.

Threat model and justification: We assume that the adversary can obtain the vector of output probabilities for any input . The set of queries the adversary can make is then 𝒬_f={𝐩^f(𝐱),  ∀𝐱}. Note that an adversary with access to the softmax probabilities will be able to recover the logits up to an additive constant, by taking the logarithm of the softmax probabilities. For untargeted attacks, the adversary only needs access to the output probabilities for the two most likely classes. 

A compelling reason for assuming this threat model for the adversary is that many existing cloud-based ML services allow users to query trained models (<cit.>, <cit.>, <cit.>). The results of these queries are confidence scores which can be used to carry out attacks. These trained models are often deployed by the clients of these ML as a service (MLaaS) providers (<cit.>). Thus, an adversary can pose as a user for a MLaaS provider and create adversarial examples using our attack, which can then be used against any client of that provider.

Comparing against existing black-box attacks: In the results presented in this  section, we compare our attacks against a number of existing black-box attacks in both ther targeted and untargeted case. Detailed descriptions of these attacks are in Section <ref>. In particular, we compare against the following attacks that make zero queries to the target model:

    
  * Baseline attacks: Random-Gaussian perturbations denoted as (Section <ref>) and Difference-of-Means aligned perturbations denoted as (Section <ref>)
    
  * (Section <ref>) using Fast Gradient Sign (FGS) and Iterative FGS (IFGS) samples generated on a single source model for both loss functions. This is denoted as Transfer model FGS/IFGS-loss); e.g., Transfer  
  * (Section <ref>) using FGS and IFGS samples generated on a source model for both loss functions (Transfer models FGS/IFGS-loss); e.g., Transfer ,  

We also compare against white-box attacks, descriptions of which are in Section <ref> and results are in Appendix <ref>.



 §.§ Finite difference method for gradient estimation

In this section, we focus on the method of finite differences to carry out based attacks. Let the function whose gradient is being estimated be g(). The input to the function is a d-dimensional vector , whose elements are represented as _i, where i ∈ [1, …, d]. The canonical basis vectors are represented as 𝐞_i, where 𝐞_i is 1 only in the i^th component and 0 everywhere else. Then, a two-sided estimation of the gradient of g with respect to  is given by 

    FD_(g(),δ) = [ g( + δ𝐞_1)-g( - δ𝐞_1)/2 δ;                         ⋮; g( + δ𝐞_d)-g( - δ𝐞_d)/2 δ;                           ].

δ is a free parameter that controls the accuracy of the estimation. A one-sided approximation can also be used, but will be less accurate <cit.>. If the gradient of the function g exists, then lim_δ→ 0FD_(g(),δ) = ∇_ g(). The finite difference method is useful for a black-box adversary aiming to approximate a gradient based attack, since the gradient can be directly estimated with access to only the function values.  



  §.§.§ Approximate FGS with finite differences
 In the untargeted FGS method, the gradient is usually taken with respect to the cross-entropy loss between the true label of the input and the softmax probability vector. 
The cross-entropy loss of a network f at an input  is then ℓ_f(,y) = - ∑_j=1^|𝒴|1[j=y] log p_j^f()= - log p_y^f(), where y is the index of the original class of the input. The gradient of ℓ_f(,y) is

    ∇_ℓ_f(,y) = - ∇_p_y^f()/p_y^f().

An adversary with query access to the softmax probabilities then just has to estimate the gradient of p_y^f() and plug it into Eq. <ref>  to get the estimated gradient of the loss. The adversarial sample thus generated is

    =  + ϵ·sign  (FD_(p_y^f(), δ)/p_y^f()).

This method of generating adversarial samples is denoted as . Targeted black-box adversarial samples generated using the method are then

    =  - ϵ·sign  (FD_(p_T^f(), δ)/p_T^f()).

The targeted version of the method is denoted as .




  §.§.§ Estimating the logit-based loss
 
We also use a loss function based on logits which was found to work well for white-box attacks by <cit.>. The loss function is given by

    ℓ(,y)=max(( + δ)_y-max{( + δ)_i: i ≠ y}, -κ),

where y represents the ground truth label for the benign sample  and (·) are the logits. κ is a confidence parameter that can be adjusted to control the strength of the adversarial perturbation. If the confidence parameter κ is set to 0, the logit loss is max(( + δ)_y-max{( + δ)_i: i ≠ y}, 0). For an input that is correctly classified, the first term is always greater than 0, and for an incorrectly classified input, an untargeted attack is not meaningful to carry out. Thus, the loss term reduces to ( + δ)_y-max{( + δ)_i: i ≠ y} for relevant inputs. 

An adversary can compute the logit values up to an additive constant by taking the logarithm of the softmax probabilities, which are assumed to be available in this threat model. Since the loss function is equal to the difference of logits, the additive constant is canceled out. Then, the finite differences method can be used to estimate  the difference between the logit values for the original class y, and the second most likely class y', i.e., the one given by y'=_i ≠ y()_i. The untargeted adversarial sample generated for this loss in the white-box case is =  + ϵ·sign(∇_ (()_y'-()_y)).
Similarly, in the case of a black-box adversary with query-access to the softmax probabilities, the adversarial sample is

    =  + ϵ·sign ( FD_ (()_y'-()_y, δ)).

Similarly, a targeted adversarial sample is

    =  - ϵ·sign ( FD_ (max(()_i:i ≠ T)-()_T, δ)).


The untargeted attack method is denoted as while the targeted version is denoted as .







  §.§.§ Iterative attacks with estimated gradients

The iterative variant of the gradient based attack described in Section <ref> is a powerful attack that often achieves much higher attack success rates in the white-box setting than the simple single-step gradient based attacks. Thus, it stands to reason that a version of the iterative attack with estimated gradients will also perform better than the single-step attacks described until now. An iterative attack with t+1 iterations using the cross-entropy loss is:

    ^t+1 = Π_ℋ( ^t + α·sign( FD_^tp_y^f(^t)/p_y^f(^t)) ),

where α is the step size and ℋ is the constraint set for the adversarial sample. This attack is denoted as . If the logit loss is used instead, it is denoted as .



  §.§.§ Evaluation of using Finite Differences

In this section, we summarize the results obtained using attacks with Finite Differences and describe the parameter choices made.

and match white-box attack adversarial success rates:
The attack with Finite Differences () is the most successful untargeted single-step black-box attack for MNIST and CIFAR-10 models.
It significantly outperforms transferability-based attacks (Table <ref>) and closely tracks white-box FGS with a logit loss (WB ) on MNIST and CIFAR-10 (Figure <ref>). For adversarial samples generated iteratively, the Iterative attack with Finite Differences () achieves 100% adversarial success rate across all models on both datasets (Table <ref>). We used 0.3 for the value of ϵ for the MNIST dataset and 8 for the CIFAR-10 dataset. The average distortion for both and closely matches their white-box counterparts, and as given in Table <ref>. 

FD-T and IFD-T achieve the highest adversarial success rates in the targeted setting: 
For targeted black-box attacks, achieves 100% adversarial success rates on almost all models as shown by the results in Table <ref>. While only achieves about 30% adversarial success rates, this matches the performance of single-step white-box attacks such as and (Table <ref>). The average distortion for samples generated using gradient estimation methods is similar with that of white-box attacks. 




Parameter choices: We use δ=1.0 for and for both datasets, while using δ=0.01 for and . We find that a larger value of δ is needed for xent loss based attacks to work. The reason for this is that the probability values used in the xent loss are not as sensitive to changes as in the logit loss, and thus the gradient cannot be estimated since the function value does not change at all when a single pixel is perturbed. For the Iterative attacks using Finite Differences, we use α=0.01 and t=40 for the MNIST results and α=1.0 and t=10 for CIFAR-10 throughout. The same parameters are used for the white-box Iterative FGS attack results given in Appendix <ref>. This translates to 62720 queries for MNIST (40 steps of iteration) and 61440 queries (10 steps of iteration) for CIFAR-10 per sample. We find these choices work well, and keep the running time of the attacks at a manageable level. However, we find that we can achieve similar adversarial success rates with much fewer queries using query reduction methods which we describe in the next section.



 §.§ Query reduction

The major drawback of the approximation based black-box attacks is that the number of queries needed per adversarial sample is large. For an input with dimension d, the number of queries will be exactly 2d for a two-sided approximation. This may be too large when the input is high-dimensional. So we examine two techniques in order to reduce the number of queries the adversary has to make. Both techniques involve estimating the gradient for groups of features, instead of estimating it one feature at a time.

The justification for the use of feature grouping comes from the relation between gradients and directional derivatives <cit.> for differentiable functions. The directional derivative of a function g is defined as ∇_g() = lim_h → 0g( + h )-g()/h. 
It is a generalization of a partial derivative. For differentiable functions, 
∇_g() = ∇_ g() ·,
which implies that the directional derivative is just the projection of the gradient along the direction . Thus, estimating the gradient by grouping features is equivalent to estimating an approximation of the gradient constructed by projecting it along appropriately chosen directions. The estimated gradient ∇̂_g() of any function g can be computed using the techniques below, and then plugged in to Equations <ref> and <ref> instead of the finite difference term to create an adversarial sample.
Next, we introduce the techniques applied to group the features for estimation. 


  §.§.§ Query reduction based on random grouping

The simplest way to group features is to choose, without replacement, a random set of features. The gradient can then be simultaneously estimated for all these features. If the size of the set chosen is k, then the number of queries the adversary has to make is ⌈d/k⌉. When k=1, this reduces to the case where the partial derivative with respect to every feature is found, as in Section <ref>. In each iteration of Algorithm <ref>, there is a set of indices S according to which  is determined, with _i=1 if and only if i ∈ S. Thus, the directional derivative being estimated is ∑_i ∈ S∂ g()/∂_i, which is an average of partial derivatives. Thus, the quantity being estimated is not the gradient itself, but an index-wise averaged version of it.

 



  §.§.§ Query reduction using PCA components

A more principled way to reduce the number of queries the adversary has to make to estimate the gradient is to compute directional derivatives along the principal components as determined by principal component analysis (PCA) <cit.>, which requires the adversary to have access to a set of data which is represetative of the training data. PCA minimizes reconstruction error in terms of the L_2 norm; i.e., it provides a basis in which the Euclidean distance to the original sample from a sample reconstructed using a subset of the basis vectors is the smallest. 

Concretely, let the samples the adversary wants to misclassify be column vectors ^i ∈ℝ^d for i ∈{1, …, n} and let  be the d × n matrix of centered data samples (i.e. =[ ^1 ^2 …^n], where ^i=  -  1/n∑_j=1^n ^j). The principal components of  are the normalized eigenvectors of its sample covariance matrix =. Since  is a positive semidefinite matrix, there is a decomposition = Λ where  is an orthogonal matrix, Λ = (λ_1,…,λ_d), and λ_1 ≥…≥λ_d ≥ 0. Thus,  in Algorithm <ref> is the d × d matrix whose columns are unit eigenvectors of . The eigenvalue λ_i is the variance of  along the i^th component.



In Algorithm <ref>,  is the d × d matrix whose columns are the principal components _i, where i ∈ [d]. The quantity being estimated in Algorithm <ref> is an approximation of the gradient in the PCA basis: 

    (∇_g())^k=∑_i=1^k ( ∇_g() _i/_i ) _i/_i,

where the term on the left represents an approximation of the true gradient by the sum of its projection along the top k principal components. In Algorithm <ref>, the weights of the representation in the PCA basis are approximated using the approximate directional derivatives along the principal components. 






 §.§ Iterative attacks with query reduction

Performing an iterative attack with the gradient estimated using the finite difference method (Equation <ref>) could be expensive for an adversary, needing 2td queries to the target model, for t iterations with the two-sided finite difference estimation of the gradient. To lower the number of queries needed, the adversary can use either of the query reduction techniques described above to reduce the number of queries to 2tk ( k<d). These attacks using the cross-entropy loss are denoted as for the random grouping technique and for the PCA-based technique.



  §.§.§ Evaluation of Gradient Estimation attacks with query reduction

In this section, we first summarize the results obtained using attacks with query reduction and then provide a more detailed analysis of the effect of dimension  on attacks with query reduction

Gradient estimation with query reduction maintains high attack success rates: For both datasets, the attack with PCA based query reduction () is effective, with performance close to that of with k=100 for MNIST (Figure <ref>) and k=400 for CIFAR-10 (Figure <ref>). The Iterative attacks with both Random Grouping and PCA based query reduction (and ) achieve close to 100% success rates for untargeted attacks and above 80% for targeted attacks on  on MNIST and on CIFAR-10 (Figure <ref>). Figure <ref> clearly shows the effectiveness of the gradient estimation attack across models, datasets, and adversarial goals. While random grouping is not as effective as the PCA based method for Single-step attacks, it is as effective for iterative attacks. 

Effect of dimension on attacks:
We consider the effectiveness of with random grouping based query reduction and the logit loss () on  on MNIST data in Figure <ref>, where k is the number of indices chosen in each iteration of Algorithm <ref>. Thus, as k increases and the number of groups decreases, we expect attack success to decrease as gradients over larger groups of features are averaged. This is the effect we see in Figure <ref>, where the adversarial success rate drops from 93% to 63% at ϵ=0.3 as k increases from 1 to 7. Grouping with k=7 translates to 112 queries per MNIST image, down from 784. Thus, in order to achieve high adversarial success rates with the random grouping method, larger perturbation magnitudes are needed.

On the other hand, the PCA-based approach is much more effective, as can be seen in Figure <ref>. Using 100 principal components to estimate the gradient for  on MNIST as in Algorithm <ref>, the adversarial success rate at ϵ=0.3 is 88.09%, as compared to 92.9% without any query reduction. Similarly, using 400 principal components for on CIFAR-10 (Figure <ref>), an adversarial success rate of 66.9% can be achieved at ϵ=8. At ϵ=16, the adversarial success rate rises to 80.1%. 

Remarks: While decreasing the number of queries does reduce attack success rates, the proposed query reduction methods maintain high attack success rates.



 §.§ Adversarial samples
 
In Figure <ref>, we show some examples of successful untargeted adversarial samples against  on MNIST and on CIFAR-10. These images were generated with an L_∞ constraint of ϵ=0.3 for MNIST and ϵ=8 for CIFAR-10. Clearly, the amount of perturbation added by iterative attacks is much smaller, barely being visible in the images.






 §.§ Efficiency of gradient estimation attacks

In our evaluations, all models were run on a GPU with a batch size of 100. On  on MNIST data, single-step attacks and take 6.2 × 10^-2 and 8.8 × 10^-2 seconds per sample respectively. Thus, these attacks can be carried out on the entire MNIST test set of 10,000 images in about 10 minutes. 
For iterative attacks with no query reduction, with 40 iterations per sample (α set to 0.01), both and taking about 2.4 seconds per sample. Similarly, and take about 3.5 seconds per sample. With query reduction, using with k=100 the time taken is just 0.5 seconds per sample.

For on the CIFAR-10 dataset, , , and all take roughly 3s per sample. The iterative variants of these attacks with 10 iterations (α set to 1.0) take roughly 30s per sample. Using query reduction, with k=100 with 10 iterations takes just 5s per sample. The time required per sample increases with the complexity of the network, which is observed even for white-box attacks.

All the above numbers are for the case when queries are not made in parallel. Our attack algorithm allows for queries to be made in parallel as well. We find that a simple parallelization of the queries gives us a 2-4× speedup. The limiting factor is the fact that the model is loaded on a single GPU, which implies that the current setup is not fully optimized to take advantage of the inherently parallel nature of our attack. With further optimization, greater speedups can be achieved.

Remarks: Overall, our attacks are very efficient and allow an adversary to generate a large number of adversarial samples in a short period of time. 






 §.§ Other query-based attacks
 
We experimented with Particle Swarm Optimization (PSO),[Using freely available code from <http://pythonhosted.org/pyswarm/>] a commonly used evolutionary optimization strategy, to construct adversarial samples as was done by <cit.>, but found it to be prohibitively slow for a large dataset, and it was unable to achieve high adversarial success rates even on the MNIST dataset. We also tried to use the Simultaneous Perturbation Stochastic Approximation (SPSA) method, which is similar to the method of Finite Differences, but it estimates the gradient of the loss along a random direction 𝐫 at each step, instead of along the canonical basis vectors. While each step of SPSA only requires 2 queries to the target model, a large number of steps are nevertheless required to generate adversarial samples. A single step of SPSA does not reliably produce adversarial samples. The two main disadvantages of this method are that i) the convergence of SPSA is much more sensitive in practice to the choice of both δ (gradient estimation step size) and α (loss minimization step size), and ii) even with the same number of queries as the attacks, the attack success rate is lower even though the distortion is higher. 

A comparative evaluation of all the query-based black-box attacks we experimented with for the MNIST dataset is given in Table <ref>. The PSO based attack uses class probabilities to define the loss function, as it was found to work better than the logit loss in our experiments. The attack that achieves the best trade-off between speed and attack success is .



§ ATTACKING DEFENSES

In this section, we evaluate black-box attacks against different defenses based on adversarial training and its variants. We focus on adversarial training based defenses as they aim to directly improve the robustness of DNNs, and are among the most effective defenses demonstrated so far in the literature. 

We find that Iterative attacks perform much better than any single-step black-box attack against defenses. Nevertheless, in Figure <ref>, we show that with the addition of an initial random perturbation to overcome “gradient masking” <cit.>, the attack with Finite Differences is the most effective single-step black-box attack on adversarially trained models on MNIST.








 §.§ Background and evaluation setup
 


  §.§.§ Adversarial training

<cit.> and <cit.> introduced the concept of adversarial training, where the standard loss function for a neural network f is modified as follows:

    ℓ̃(,y) = αℓ_f(,y) + (1- α) ℓ_f(,y),
where y is the true label of the sample . The underlying objective of this modification is to make the neural networks more robust by penalizing it during training to count for adversarial samples. During training, the adversarial samples are computed with respect to the current state of the network using an appropriate method such as FGSM.

Ensemble adversarial training. <cit.> proposed an extension of the adversarial training paradigm which is called ensemble adversarial training. As the name suggests, in ensemble adversarial training, the network is trained with adversarial samples from multiple networks. 

Iterative adversarial training. A further modification of the adversarial training paradigm proposes training with adversarial samples generated using iterative methods such as the iterative FGSM attack described earlier <cit.>.






 §.§ Adversarially trained models

We train variants of  with the 3 adversarial training strategies described above using adversarial samples based on an L_∞ constraint of 0.3.  is trained with FGS samples, while  is trained with iterative FGS samples using t=40 and α=0.01. For the model with ensemble training,  is trained with pre-generated FGS samples for , , and , as well as FGS samples. The source of the samples is chosen randomly for each minibatch during training. For all adversarially trained models, each training batch contains 128 samples of which 64 are benign and 64 are adversarial samples (either FGSM or iterative FGSM). This implies that the loss for each is weighted equally during training; i.e., in Eq. <ref>, α is set to 0.5. Networks using standard and ensemble adversarial training are trained for 12 epochs, while those using iterative adversarial training are trained for 64 epochs.

We train variants of using adversarial samples with an L_∞ constraint of 8.  is trained with FGS samples with the same constraint, and  is trained with pre-generated FGS samples from and as well as FGS samples.  is trained with iterative FGS samples using t=10 and α=1.0. The adversarial variants of is trained for 80,000 steps

Table <ref> shows the accuracy of these models with various defenses on benign test data.



 §.§ Single-step attacks on defenses


In Figure <ref>, we can see that both single-step black-box and white-box attacks have much lower adversarial success rates on  as compared to . The success rate of the attacks matches that of white-box attacks on these adversarially trained networks as well. To overcome this, we add an initial random perturbation to samples before using the attack with Finite Differences and the logit loss (). These are then the most effective single step black-box attacks on  at ϵ=0.3 with an adversarial success rate of 32.2%, surpassing the from B.

In Figure <ref>, we again see that the attacks using Finite Differences (and ) and white-box FGS attacks (and ) against . As ϵ is increased, the attacks that perform the best are Random Perturbations (), Difference-of-means (), and from with the latter performing slightly better than the baseline attacks. This is due to the `gradient masking' phenomenon and can be overcome by adding random perturbations as for MNIST. An interesting effect is observed at ϵ=4, where the adversarial success rate is higher than at ϵ=8. The likely explanation for this effect is that the model has overfitted to adversarial samples at ϵ=8. Our attack closely tracks the adversarial success rate of white-box attacks in this setting as well.




Increasing effectiveness of single-step attacks using initial random perturbation:
Since the attack with Finite Differences (and ) were not performing well due the masking of gradients at the benign sample , we added an initial random perturbation to escape this low-gradient region as in the RAND-FGSM attack <cit.>. Figure <ref> shows the effect of adding an initial L_∞-constrained perturbation of magnitude 0.05. With the addition of a random perturbation, has a much improved adversarial success rate on , going up to 32.2% from 2.8% without the perturbation at a total perturbation value of 0.3. It even outperforms the white-box FGS () with the same random perturbation added. This effect is also observed for , but  appears to be resistant to single-step gradient based attacks. Thus, our attacks work well for single-step attacks on DNNs with standard and ensemble adversarial training, and achieve performance levels close to that of white-box attacks.



 §.§ Iterative attacks on different adversarial training defenses

While single-step black-box attacks are less effective at ϵ lower than the one used for training, our experiments show that iterative black-box attacks continue to work well even against adversarially trained networks. For example, the Iterative attack using Finite Differences with a logit loss () achieves an adversarial success rate of 96.4% against , while the best transferability attack has a success rate of 4.9%. It is comparable to the white-box attack success rate of 93% from Table <ref>. 
However,  is quite robust even against iterative attacks, with the highest black-box attack success rate achieved being 14.5%. 

Further, in Figure <ref>, we can see that using just 4000 queries per sample, the Iterative attack using PCA for query reduction (IGE-QR (PCA-400, logit)) achieves 100% (untargeted) and 74.5% (targeted) adversarial success rates against . Our methods far outperform the other black-box attacks, as shown in Table <ref>.

Iterative black-box attacks perform well against adversarially trained models for CIFAR-10 as well. achieves attack success rates of 100% against both  and  (Table <ref>), which reduces slightly to 97% when IFD-QR (PCA-400, logit) is used. This matches the performance of white-box attacks as given in Table <ref>. IFD-QR (PCA-400, logit) also achieves a 72% success rate for targeted attacks at ϵ=8 as shown in Figure <ref>.

The iteratively trained model has poor performance on both benign as well as adversarial samples.  has an accuracy of only 79.1% on benign data, as shown in Table <ref>. The Iterative Gradient Estimation attack using Finite Differences with cross-entropy loss () achieves an untargeted attack success rate of 55% on this model, which is lower than on the other adversarially trained models, but still significant. This is in line with the observation by <cit.> that iterative adversarial training needs models with large capacity for it to be effective. This highlights a limitation of this defense, since it is not clear what model capacity is needed and the models we use already have a large number of parameters. 

Remarks.
Both single-step and iterative variants of the attacks outperform other black-box attacks, achieving attack success rates close to those of white-box attacks even on adversarially trained models. 



§ ATTACKS ON CLARIFAI: A REAL-WORLD SYSTEM

Since the only requirement for carrying out the based attacks is query-based access to the target model, a number of deployed public systems that provide classification as a service can be used to evaluate our methods. We choose <cit.>, as it has a number of models trained to classify image datasets for a variety of practical applications, and it provides black-box access to its models and returns confidence scores upon querying. In particular, Clarifai has models used for the detection of Not Safe For Work (NSFW) content, as well as for Content Moderation. These are important applications where the presence of adversarial samples presents a real danger: an attacker, using query access to the model, could generate an adversarial sample which will no longer be classified as inappropriate. For example, an adversary could upload violent images, adversarially modified, such that they are marked incorrectly as `safe' by the Content Moderation model.    

We evaluate our attack using the method on the Clarifai NSFW and Content Moderation models. An important point to note here is that given the lack of an easily accessible open-source dataset for these tasks to train a local surrogate model, carrying out attacks based on transferability is a challenging task. On the other hand, our attack can directly be used for any image of the adversary's choice. The Content Moderation model has five categories, `safe', `suggestive', `explicit', `drug' and `gore', while the NSFW model has just two categories, `SFW' and `NSFW.' When we query the API with an image, it returns the confidence scores associated with each category, with the confidence scores summing to 1. We use the random grouping technique in order to reduce the number of queries and take the logarithm of the confidence scores in order to use the logit loss. A large number of successful attack images can be found at <https://sunblaze-ucb.github.io/blackbox-attacks/>. Due to their possibly offensive nature, they are not included in the paper.

An example of an attack on the Content Moderation API is given in Figure <ref>, where the original image on the left is clearly of some kind of drug on a table, with a spoon and a syringe. It is classified as a drug by the Content Moderation model with a confidence score of 0.99. The image on the right  is an adversarial image generated with 192 queries to the Content Moderation API, with an L_∞ constraint on the perturbation of ϵ=32. While the image can still clearly be classified by a human as being of drugs on a table, the Content Moderation model now classifies it as `safe' with a confidence score of 0.96. 

Remarks. The proposed attacks can successfully generate adversarial examples that are misclassified by a real-world system hosted by Clarifai without prior knowledge of the training set or model.









§ EXISTING BLACK-BOX ATTACKS

In this section, we describe existing methods for generating adversarial examples. In all of these attacks, the adversary's perturbation is constrained using the L_∞ distance. 



 §.§ Baseline attacks

Now, we describe two baseline black-box attacks which can be carried out without any knowledge of or query access to the target model.



  §.§.§ Random perturbations
 
With no knowledge of f or the training set, the simplest manner in which an adversary may seek to carry out an attack is by adding a random perturbation to the input <cit.>. These perturbations can be generated by any distribution of the adversary's choice and constrained according to an appropriate norm. If we let P be a distribution over 𝒳, and 𝐩 is a random variable drawn according to P, then a noisy sample is just _noise=+𝐩. Since random noise is added, it is not possible to generate targeted adversarial samples in a principled manner. This attack is denoted as Rand. throughout.



  §.§.§ Difference of means
  
A perturbation aligned with the difference of means of two classes is likely to be effective for an adversary hoping to cause misclassification for a broad range of classifiers <cit.>. While these perturbations are far from optimal for DNNs, they provide a useful baseline to compare against. Adversaries with at least partial access to the training or test sets can carry out this attack. An adversarial sample generated using this method, and with L_∞ constraints, is =  + ϵ·sign(μ_t-μ_o), where μ_t is the mean of the target class and μ_o is the mean of the original ground truth class. For an untargeted attack, t=_i d(μ_i - μ_o), where d(·,·) is an appropriately chosen distance function. In other words, the class whose mean is closest to the original class in terms of the Euclidean distance is chosen to be the target. This attack is denoted as D. of M. throughout.



  §.§.§ Effectiveness of baseline attacks
 In the baseline attacks described above, the choice of distribution for the random perturbation attack and the choice of distance function for the difference of means attack are not fixed. Here, we describe the choices we make for both attacks. The random perturbation 𝐩 for each sample (for both MNIST and CIFAR-10) is chosen independently according to a multivariate normal distribution with mean 0, i.e. 𝐩∼𝒩(0,𝐈_d). Then, depending on the norm constraint, either a signed and scaled version of the random perturbation (L_∞) or a scaled unit vector in the direction of the perturbation (L_2) is added. For an untargeted attack utilizing perturbations aligned with the difference of means, for each sample, the mean of the class closest to the original class in the L_2 distance is determined.

As expected, adversarial samples generated using  do not achieve high adversarial success rates (Table <ref>) in spite of having similar or larger average distortion than the other black-box attacks for both the MNIST and CIFAR-10 models. However, the  method is quite effective at higher perturbation values for the MNIST dataset as can be seen in Figure <ref>. Also, for  and , the  attack is more effective than . The  method is less effective in the targeted attack case, but for , it outperforms the transferability based attack considerably. Its success rate is comparable to the targeted transferability based attack for  as well.

The relative effectiveness of the two baseline methods is reversed for the CIFAR-10 dataset, however, where  outperforms  considerably as ϵ is increased. This indicates that the models trained on MNIST have normal vectors to decision boundaries which are more aligned with the vectors along the difference of means as compared to the models on CIFAR-10. 



 §.§ Single-step and Iterative Fast Gradient Methods

Now, we describe two white-box attack methods, used in transferability-based attacks, for which we constructed approximate, gradient-free versions in Section <ref>. These attacks are based on either iterative or single-step gradient based minimization of appropriately defined loss functions of neural networks. All results for white-box attacks are contained in Appendix <ref>. Since these methods all require the knowledge of the model's gradient, we assume the adversary has access to a local model f^s. Adversarial samples generated for f^s can then be transferred to the target model f^t to carry out a transferability-based attack <cit.>. An ensemble of local models <cit.> may also be used. Transferability-based attacks are described in Section <ref>. 

The single-step Fast Gradient method, first introduced by <cit.>, utilizes a first-order approximation of the loss function in order to construct adversarial samples for the adversary's surrogate local model f^s. The samples are constructed by performing a single step of gradient ascent for untargeted attacks. Formally, the adversary generates samples  with L_∞ constraints (known as the Fast Gradient Sign (FGS) method) in the untargeted attack setting as

    =  + ϵ·sign (∇_ℓ_f^s(, y)),

where ℓ_f^s(,y) is the loss function with respect to which the gradient is taken. The loss function typically used is the cross-entropy loss <cit.>. Adversarial samples generated using the targeted FGS attack are

    =  - ϵ·sign (∇_ℓ_f^s(, T)),

where T is the target class.

Iterative Fast Gradient methods are simply multi-step variants of the Fast Gradient method described above <cit.>, where the gradient of the loss is added to the sample for t+1 iterations, starting from the benign sample, and the updated sample is projected to satisfy the constraints ℋ in every step:

    ^t+1 = Π_ℋ(^t + α·sign(∇_^tℓ_f^s(^t, y))),

with ^0 =. Iterative fast gradient methods thus essentially carry out projected gradient descent (PGD) with the goal of maximizing the loss, as pointed out by <cit.>. Targeted adversarial samples generated using iterative FGS are

    ^t+1 = Π_ℋ(^t - α·sign(∇_^tℓ_f^s(^t, T))).




  §.§.§ Beyond the cross-entropy loss
 
Prior work by <cit.> investigates a variety of loss functions for white-box attacks based on the minimization of an appropriately defined loss function. In our experiments with neural networks, for untargeted attacks, we use a loss function based on logits which was found to work well for white-box attacks in <cit.>. The loss function is given by

    ℓ(,y)=max(( + δ)_y-max{( + δ)_i: i ≠ y}, -κ),

where y represents the ground truth label for the benign sample , (·) are the logits. κ is a confidence parameter that can be adjusted to control the strength of the adversarial sample. Targeted adversarial samples are generated using the following loss term:

    =  - ϵ·sign(∇_ (max(()_i: i ≠ T)-()_T)).




 §.§ Transferability based attacks
 
Here we describe black-box attacks that assume the adversary has access to a representative set of training data in order to train a local model. One of the earliest observations with regards to adversarial samples for neural networks was that they transfer; i.e, adversarial attack samples generated for one network are also adversarial for another network. This observation directly led to the proposal of a black-box attack where an adversary would generate samples for a local network and transfer these to the target model, which is referred to as a .  Targeted transferability attacks are carried out using locally generated targeted white-box adversarial samples. 



  §.§.§ Single local model

These attacks use a surrogate local model f^s to craft adversarial samples, which are then submitted to f in order to cause misclassification. Most existing black-box attacks are based on transferability from a single local model <cit.>. The different attack strategies to generate adversarial instances introduced in Section <ref> can be used here to generate adversarial instances against f^s, so as to attack f. 



  §.§.§ Ensemble of local models
 
Since it is not clear which local model f^s is best suited for generating adversarial samples that transfer well to the target model f, <cit.> propose the generation of adversarial examples for an ensemble of local models.
This method modifies each of the existing transferability attacks by substituting a sum over the loss functions in place of the loss from a single local model. 

Concretely, let the ensemble of m local models to be used to generate the local loss be {f^s_1, …, f^s_m}. The ensemble loss is then computed as 
ℓ_ens(,y) = ∑_i=1^m α_i ℓ_f^s_i(,y), where α_i is the weight given to each model in the ensemble. The FGS attack in the ensemble setting then becomes
=  + ϵ·sign(∇_ℓ_ens(,y)). The Iterative FGS attack is modified similarly. <cit.> show that the performs well even in the targeted attack case, while is usually only effective for untargeted attacks. The intuition is that while one model's gradient may not be adversarial for a target model, it is likely that at least one of the gradient directions from the ensemble represents a direction that is somewhat adversarial for the target model.






  §.§.§ Transferability attack results

For the transferability experiments, we choose to transfer from Model B for MNIST dataset and from for CIFAR-10 dataset, as these models are each similar to at least one of the other models for their respective dataset and different from one of the others. They are also fairly representative instances of DNNs used in practice.

Adversarial samples generated using single-step methods and transferred from  to the other models have higher success rates for untargeted attacks when they are generated using the logit loss as compared to the cross entropy loss as can be seen in Table <ref>. For iterative adversarial samples, however, the untargeted attack success rates are roughly the same for both loss functions. As has been observed before, the adversarial success rate for targeted attacks with transferability is much lower than the untargeted case, even when iteratively generated samples are used. On the MNIST dataset, the highest targeted transferability rate is 54.5% (Table <ref>) as compared to 89.8% in the untargeted case (Table <ref>). 

One attempt to improve the transferability rate is to use an ensemble of local models, instead of a single one. The results for this on the MNIST data are presented in Table <ref>. In general, both untargeted and targeted transferability increase when an ensemble is used. However, the increase is not monotonic in the number of models used in the ensemble, and we can see that the transferability rate for samples falls sharply when  is added to the ensemble. This may be due to it having a very different architecture as compared to the models, and thus also having very different gradient directions. This highlights one of the pitfalls of transferability, where it is important to use a local surrogate model similar to the target model for achieving high attack success rates. 



§ CONCLUSION

Overall, in this paper, we conduct a systematic analysis of new and existing black-box attacks on state-of-the-art classifiers and defenses. We propose attacks which achieve high attack success rates comparable with even white-box attacks and outperform other state-of-the-art black-box attacks. We apply random grouping and PCA based methods to reduce the number of queries required to a small constant and demonstrate the effectiveness of the attack even in this setting. We also apply our black-box attack against a real-world classifier and state-of-the-art defenses. All of our results show that attacks are extremely effective in a variety of settings, making the development of better defenses against black-box attacks an urgent task.


iclr2018_conference



§ ALTERNATIVE ADVERSARIAL SUCCESS METRIC
 
Note that the adversarial success rate can also be computed by considering only the fraction of inputs that meet the adversary's objective given that the original sample was correctly classified. That is, one would count the fraction of correctly classified inputs (i.e. f()=y) for which f() ≠ y in the untargeted case, and f^t()=T in the targeted case. In a sense, this fraction represents those samples which are truly adversarial, since they are misclassified solely due to the adversarial perturbation added and not due to the classifier's failure to generalize well. In practice, both these methods of measuring the adversarial success rate lead to similar results for classifiers with high accuracy on the test data.





§ FORMAL DEFINITIONS FOR QUERY-BASED ATTACKS

Here, we provide a unified framework assuming an adversary can make active queries to the model. Existing attacks making zero queries are a special case in this framework. Given an input instance , the adversary makes a sequence of queries based on the adversarial constraint set ℋ, and iteratively adds perturbations until the desired query results are obtained, using which the corresponding adversarial example _adv is generated.

We formally define the targeted and untargeted black-box attacks based on the framework as below.
[Untargeted black-box attack]
Given an input instance  and an iterative active query attack strategy 𝒜, a query sequence can be generated as
^2 = 𝒜({(^1, q_f^1)}, ℋ), ...,
^i = 𝒜({(^1, q_f^1), …, (^i-1, q_f^i-1)}, ℋ), where
q_f^i denotes the ith corresponding query result on ^i, and we set ^1=.
A black-box attack on f(·;θ) is untargeted if the adversarial example =^k satisfies f(;θ) ≠ f(;θ), where k is the number of queries made.



[Targeted black-box attack]
Given an input instance  and an iterative active query attack strategy 𝒜, a query sequence can be generated as
^2 = 𝒜({(^1, q_f^1)}, ℋ), ...,
^i = 𝒜({(^1, q_f^1), …, (^i-1, q_f^i-1)}, ℋ), where
q_f^i denotes the ith corresponding query result on ^i, and we set ^1=.
A black-box attack on f(·;θ) is targeted if the adversarial example =^k satisfies f(;θ)=T, where T and k are the target class and the number of queries made, respectively. 


The case where the adversary makes no queries to the target classifier is a special case we refer to as a . In the literature, a number of these have been carried out with varying degrees of success <cit.>. 




§ SUMMARY OF ATTACKS EVALUATED


Taxonomy of black-box attacks:
To deepen our understanding of the effectiveness of black-box attacks, in this work, we propose a taxonomy of black-box attacks, intuitively based on the number of queries on the target model used in the attack. The details are provided in Table <ref>. 




We evaluate the following attacks summarized in Table <ref>:


  * Zero-query attacks

    
  * Baseline attacks: Random-Gaussian perturbations () and Difference-of-Means aligned perturbations () 
    
  * using Fast Gradient Sign (FGS) and Iterative FGS (IFGS) samples generated on a single source model for both loss functions (Transfer model FGS/IFGS-loss); e.g., Transfer  
  * using FGS and IFGS samples generated on a source model for both loss functions (Transfer models FGS/IFGS-loss); e.g., Transfer ,  

  * Query based attacks

    
  * and Iterative attacks for the gradient estimation attack for both loss functions (FD/IFD-loss); e.g., 
  * and Iterative with Query reduction attacks (IGE/GE-QR (Technique-k, loss)) using two query reduction techniques, random grouping (RG) and principal component analysis components (PCA); e.g., 

  * White-box FGS and IFGS attacks for both loss functions (WB FGS/IFGS (loss))











§ WHITE-BOX ATTACK RESULTS

In this section, we present the white-box attack results for various cases in Tables <ref>–<ref>. Where relevant, our results match previous work <cit.>.





















