Title: BASED HARD-LABEL BLACK-BOX ATTACKS AGAINST MACHINE LEARNING MODELS

Abstract: Machine learning models are known to be vulnerable to adversarial examples. Based on different levels of knowledge that attackers have about the models, adversarial example generation methods can be categorized into white-box and black-box attacks. We study the most realistic attacks, hard-label black-box attacks, where attackers only have the query access of a model and only the final predicted labels are available. The main limitation of the existing hard-label blackbox attacks is that they need a large number of model queries, making them inefficient and even infeasible in practice. Inspired by the very successful fuzz testing approach in traditional software testing and computer security domains, we propose fuzzing-based hard-label black-box attacks against machine learning models. We design an AdvFuzzer to explore multiple paths between a source image and a guidance image, and design a LocalFuzzer to explore the nearby space around a given input for identifying potential adversarial examples. We demonstrate that our fuzzing attacks are feasible and effective in generating successful adversarial examples with significantly reduced number of model queries and L 0 distance. More interestingly, supplied with a successful adversarial example as a seed, Lo-calFuzzer can immediately generate more successful adversarial examples even with smaller L 2 distance from the source example, indicating that LocalFuzzer itself can be an independent and useful tool to augment many adversarial example generation algorithms.

1. INTRODUCTION:

Machine learning models, especially deep neural networks, are demonstrated as being vulnerable to adversarial examples (Biggio et al., 2013; Szegedy et al., 2014) . Adversarial examples are generated by adding small perturbations to clean inputs to fool machine learning models to misclassify. In image classification tasks, adversarial examples can be found by many attack methods (Goodfellow et al., 2015; Papernot et al., 2016b; Kurakin et al., 2017; Carlini & Wagner, 2017) with the knowledge of a neural network architecture and its parameters. This type of attacks is considered as white-box attacks. While research on white-box attacks significantly helps the community to better understand adversarial examples and deep neural networks, white-box attacks are only applicable to limited real-world scenarios such as on publicly available models or exposed confidential models.

In many real-world scenarios, black-box attacks are more realistic, where an attacker only has the query access to a model. Some recent attacks (Narodytska & Kasiviswanathan, 2017; Chen et al., 2017; Hayes & Danezis, 2018; Ilyas et al., 2018) rely on probability vectors (e.g., predicted scores or logits) of a model to generate adversarial examples, and they are referred to as soft-label blackbox attacks. However, in many more realistic scenarios, only the final predicted labels (e.g., the top-1 class label) of a model are available to the attackers. This category of attacks is referred to as hard-label black-box attacks. Three recent attack methods including Boundary attack (Brendel et al., 2017) , Label-only attack (Ilyas et al., 2018) , and Opt attack (Cheng et al., 2019) fall into this category. However, although they can generate adversarial examples with comparable perturbations to white-box attacks, the main limitation of existing hard-label black-box attacks is that they need a large number of model queries since model information is not available.

From a unique perspective, we propose fuzzing-based hard-label black-box attacks by leveraging the fuzzing approach that is very successful in software testing and computer security domains (My-ers et al., 2012; Miller et al., 1990; Haller et al., 2013) . The generation of adversarial examples can be essentially considered as an optimization problem. In order to find an optimal adversarial example around a clean input, attack algorithms need information such as gradient of the loss function, vectors of classification probability, or hard labels from a model as guidance to walk toward the goal. The adversarial examples then cause the model to misclassify. Interestingly, we consider the following analogy: a machine learning model to be attacked is similar to a target program to be tested for correctness or security bugs. Adversarial examples that cause a model to misclassify are analogous to inputs that trigger a target program to crash. These similarities and the huge success of the fuzzing approach in those traditional domains inspire us to leverage an originally black-box software testing technique, fuzz testing, for exploring black-box adversarial example attacks in the adversarial machine learning domain.

The word "fuzz" was first proposed by Miller et al. (1990) to represent random, unexpected, and unstructured data (Takanen et al., 2008) . Fuzz testing aims to find program failures by iteratively and randomly generating inputs to test a target program (Klees et al., 2018) . It is a very effective approach to identifying correctness or security bugs in traditional software systems (Haller et al., 2013; Appelt et al., 2014; Jeong et al., 2019) as well as development or deployment bugs in machine learning models (Odena et al., 2019; Xie et al., 2018) .

In this paper, we propose fuzzing-based attacks against machine learning models in hard-label blackbox settings. We take the fuzz testing approach to generate random inputs for exploring the adversarial example space. We design two fuzzers: an adversarial fuzzer (referred to as AdvFuzzer) and a local fuzzer (referred to as LocalFuzzer). AdvFuzzer explores multiple paths from a clean example to a guidance example. LocalFuzzer explores the nearby space around a given input. Our approach can be applied in both targeted and untargeted settings, aiming to generate adversarial examples using a much smaller number of model queries than existing hard-label black-box attacks. Note that when a successful adversarial example is supplied as the input, LocalFuzzer has the potential to generate a large number of other successful adversarial examples in bulk. This bulk generation can be applied to adversarial examples generated from any attack methods, and potentially refine their "optimized" adversarial examples by reducing the L 2 distance from the source example.

We perform experiments to attack deep neural networks for MNIST and CIFAR-10 datasets to evaluate our fuzzing approach. The experimental results show that our fuzzing attacks are feasible, efficient, and effective. For example, the number of model queries can be reduced by 10-18 folds for MNIST and 2-5 folds for CIFAR-10 in untargeted attacks in comparison between ours and existing hard-label black-box methods. We also evaluate our LocalFuzzer on successful examples generated by Boundary attack, Opt attack, and our fuzzing attacks to validate its usefulness. For example, we achieve 100% success bulk generation rate and 48%-100% success bulk generation rate with lower L 2 for MNIST adversarial examples generated by different methods in untargeted attacks. Our work provides evidence on the feasibility and benefits of fuzzing-based attacks. To the best of our knowledge, this is the first work on exploring fuzz testing in adversarial example attacks.

2. BACKGROUND AND RELATED WORK:

Adversarial Examples In this paper, we consider computer vision classification tasks, in which a DNN model f aims to classify an input image x to a class y. We define a clean input image x as source example with source class y. The attack goal is to generate an adversarial example x close to source example x such that: (1) x is misclassified as any class other than the source class y in the untargeted attack setting, or (2) x is misclassified as a specific class y t != y in the targeted attack setting. We consider that an adversary has the hard-label black-box capability which means the adversary only has the query access to the model f and only final label outputs are available.

White-box attacks:

Most existing attacks rely on full access to the model architecture and parameters. Example attack algorithms include Fast Gradient Sign Method (Goodfellow et al., 2015) , Jacobian-based Saliency Map Approach (Papernot et al., 2016b) , Basic Iterative Method (Kurakin et al., 2017) , L-BFGS (Szegedy et al., 2014) , Carlini & Wagner attack (Carlini & Wagner, 2017) , etc. White-box attacks need gradient information of the loss function as guidance to find adversarial examples. However, the white-box scenarios are not very realistic considering the fact that many real-world machine learning models are confidential. Besides, white-box attacks can only be applied to differentiable model architectures like DNNs not to tree-based models.

Black-box attacks In many real-world scenarios, black-box attacks are more realistic where attackers only have the query access to the model and do not have detailed model information. One type of black-box attacks is transferability-based (Papernot et al., 2017) , where an adversary trains a substitute model with a substitute dataset and then generates adversarial examples from the substitute model using white-box attacks. Because of the transferability (Szegedy et al., 2014; Goodfellow et al., 2015; Papernot et al., 2016a) , adversarial examples generated from the substitute model can potentially fool the targeted model, even if the two models have different architectures. One limitation of this approach is that it needs information about training data. Besides, attacking the substitute model leads to larger perturbation and lower success rate (Chen et al., 2017; Papernot et al., 2016a; 2017) . Soft-label black-box attacks (Chen et al., 2017; Narodytska & Kasiviswanathan, 2017; Ilyas et al., 2018; Zhao et al., 2019) rely on classification probability to generate adversarial examples. Since the classification probability vectors are usually inaccessible, hard-label black-box attacks are considered as more realistic, where only the final predicted labels are available to the attackers. Boundary attack (Brendel et al., 2017) is based on a random walk around the decision boundary using examples drawn from a proposal distribution. Label-only attack (Ilyas et al., 2018) uses discretized score, image robustness of random perturbation, and Monte Carlo approximation to find a proxy for the output probability and then uses an NES gradient estimator to generate adversarial examples in a similar way as soft-label black-box attacks. Opt attack (Cheng et al., 2019) reformulates the problem as a continuous real-valued optimization problem which can be solved by any zeroth-order optimization algorithm. The main limitation of these existing hard-label black-box attacks is that they need a large number of model queries, in part because they follow the traditional (approximated) optimization approach and they all aim to walk closer to a clean example starting from a point that is already adversarial. This limitation makes them inefficient and even infeasible in practice when the allowed number of queries is limited by a model. In contrast, our fuzzing-based hard-label black-box attacks start from a clean example and walk away from it step by step. With careful guidance and leveraging the randomness advantage of the fuzz testing approach, our attacks have the potential to use a much smaller number of queries to generate a successful adversarial example.

3. APPROACH AND ALGORITHMS:

3.1 OVERVIEW OF OUR APPROACH Fuzz testing was first proposed by Miller et al. (1990) . The key idea is to use random, unexpected, and unstructured data to find program failures. In recent years, fuzzers such as AFL (Zalewski, 2007) and libFuzzer (Serebryany, 2016) have gained great popularity because of their effectiveness and scalability. A typical fuzzer works by iteratively (1) selecting a seed input from a pool, (2) mutating the chosen seed to generate new inputs, (3) evaluating the newly generated inputs, and (4) recording observations such as program crashes and adding useful inputs into the seed pool. Our fuzzing-based hard-label black-box attacks leverage the basic idea of fuzz testing to explore the adversarial example space. The main challenge of applying fuzz testing to adversarial example generation is on exploring the gigantic search space. Theoretically, a fuzzer is able to explore the entire search space, but this is computationally infeasible. We address this challenge by using a guidance image and certain guidance strategy to improve the attack efficiency, i.e., fewer queries.

Figure 1 depicts the basic intuition of our attacks. We design two fuzzers: an adversarial fuzzer (referred to as AdvFuzzer) and a local fuzzer (referred to as LocalFuzzer). Starting from a source image which is clean, AdvFuzzer slowly (thus with less amount of perturbations) walks away from it step by step by randomly selecting a path toward a guidance image. With multiple runs, AdvFuzzer will explore multiple random paths aiming to explore different regions of the adversarial example space between the two images. The guidance image could be a clean image of a specific target class for performing targeted attacks, or any image not of the source (image) class for performing untargeted attacks. LocalFuzzer aims to explore the nearby data points for identifying potential adversarial examples around the current image as AdvFuzzer takes the main steps.

It is important to point out that AdvFuzzer walks from a source image to a guidance image, thus taking a reverse direction from what is taken in existing hard-label black-box attacks including Boundary attack (Brendel et al., 2017) , Label-only attack (Ilyas et al., 2018) , and Opt attack (Cheng et al., 2019) . Combining this strategy with the randomness advantage of the fuzz testing approach, our attacks have the potential to use a much smaller number of queries to more efficiently or practically generate successful adversarial examples. Moreover, LocalFuzzer can indeed be applied to any attack methods including black-box and white-box ones. When LocalFuzzer is supplied with a successful adversarial example as a seed, it can efficiently generate new successful adversarial examples in bulk and among which further optimized (e.g., in terms of reducing the L 2 distance from the source image) ones could even be identified.

3.2. ALGORITHMS:

AdvFuzzer The logic for AdvFuzzer is presented in Algorithm 1. It generates an adversarial example img adv as output, and takes a target model f , isTargeted parameter, a source image img s , a guidance image img g , and attack guidance strategy k as inputs. For every iteration of the while loop, a random main step is taken by selecting a perturbation based on the attack guidance strategy k (Line 4). We adopt a L 0 strategy which changes a random pixel in the perturbation image to the corresponding difference pixel value between the guidance image and the current image. Note that other strategies based on L ∞ and L 2 could also be applied but we found L 0 strategy is the most effective. If the current image reaches the attack goal, a medium level LocalFuzzer is applied to explore the nearby space for potentially generating more successful adversarial examples. Otherwise, a small level LocalFuzzer is used to check if some successful adversarial examples could still be found nearby. The while loop ends whenever a successful example is found or the number of steps reaches the maximum number of steps which is the L 0 distance between the source image and the guidance image. It will then fine tune a random successful adversarial example in the adversarial example set S adv by using a walk back fuzzer. The walk back fuzzer works in a similar manner as LocalFuzzer as described below. including all examples are maintained as seed pools. A candidate seed is randomly selected and then mutated. For an input image, fuzzer level controls the total number of mutated images to be generated. In each iteration, a random perturbation based mutation is applied. The mutation function randomly selects one pixel of an image and changes its value to any real number between 0 and 1. The mutated image is then added to the adversarial set S adv if it meets the attack goal. The loop stops once the fuzzer level is reached and the adversarial image set S adv (could be empty) is returned. The difference between a LocalFuzzer and a walk back fuzzer is the mutation. Instead of changing one random pixel to a random value between 0 and 1, the walk back fuzzer mutates an image by randomly changing some pixel values of a current image closer or directly to that of the source image. S adv = S adv {img} 5: for i from 1 to f uzzer level do S all = S all {img mut } 14: return S adv Summary of Guidance Strategies. In AdvFuzzer, starting from the source image, each main step is taken by changing one pixel toward the guidance image (Algorithm 1, lines 4-5). This step is guided by the L 0 strategy and is obviously not random. In LocalFuzzer, only one pixel in the seed image is mutated (Algorithm 2, line 10). This step is random on purpose because we want to leverage the randomness advantage of fuzz testing. The walk back fuzzer mutates an image by randomly changing some pixel values of a current image closer or directly to that of the source image. This step is random on the selection of pixels but guided on value changes. In essence, we considered both certain guidance strategies and some randomness in our overall approach. Lacking either of them would result in poor performance than what we can achieve at this moment.

4. EXPERIMENTAL RESULTS:

We now evaluate the feasibility and effectiveness of our fuzzing attacks. We use two standard datasets: MNIST (LeCun & Cortes, 2010) and CIFAR-10 (Krizhevsky, 2009) . We compare fuzzing attacks with four attacks including Boundary attack (Brendel et al., 2017) , Opt attack (Cheng et al., 2019) , and C&W L 0 and L 2 attacks (Carlini & Wagner, 2017) . Note that C&W attacks are whitebox attacks. All the experiments are performed for both targeted attacks and untargeted attacks. Label-only attack (Ilyas et al., 2018) was evaluated by the authors only on ImageNet and we could not find its code for MNIST and CIFAR-10, so we did not include it in our evaluation.

To have a fair comparison, we adopt the same network architecture for MNIST and CIFAR-10 used in Carlini & Wagner (2017) . Note that Brendel et al. (2017) also used the same network architecture, which has two convolution layers followed by a max-pooling layer, two convolution layers, a max-pooling layer, two fully-connected layers, and a softmax layer. Using the same parameters as reported in Carlini & Wagner (2017) , we obtained 99.49% and 82.71% test accuracy for MNIST and CIFAR-10, respectively.

4.1. OVERALL RESULTS:

From the test set of each dataset, we randomly selected 10 images for each of the 10 classes. These same 100 images are used as source examples for all attacks. We use white-box C&W L 0 and L 2 attacks1 as baselines, and use Boundary attack2 and Opt attack3 for comparison. We adopt the default parameters for the four attacks from their corresponding original implementations. As for fuzzing attacks, we use three different small LocalFuzzer levels including 100, 300, and 500. We report the average L 0 , L 2 , and L ∞ distances between a successful adversarial example and a source image, and the average number of queries for successful adversarial examples generated from 100 attack attempts. L 0 measures the number of different pixels between two images. L 2 is the Euclidean distance. L ∞ measures the maximum pixel value. Using the default attack parameters in the corresponding implementations, Opt attack, C&W attacks, and our fuzzing attacks can achieve 100% success rates while Boundary attack achieves between 90% and 100% success rates. Note that due to the randomness of our fuzzing attacks, the distance value and number of query results could vary in a certain range from run to run. So we also report median and standard deviation of distance value and number of query results in Tables 3, 4 , 5, and 6 of Appendix A.

Untargeted Attacks An untargeted attack is successful when an adversarial image is classified as any class other than the source class. Although the guidance images in untargeted attacks could be any randomly generated images or legitimate images classified as any class other than the source class, we use the same guidance images in the targeted attacks for consistency. Also, we found that there is not much difference between using a randomly generated guidance image and a legitimate image. The results for untargeted attacks are summarized in Table 1 . While Boundary attack and Opt attack can generate successful adversarial examples with smaller L 2 distance compared to C&W attacks, they tend to change most of the pixels in an image since their average L 0 is higher. However, adversarial examples generated from our fuzzing attacks have larger L 2 and L ∞ distances but smaller L 0 distance. The results are comparable to C&W L 0 attack. The first row in Figure 2 shows the successful adversarial examples from the untargeted fuzzing attacks on MNIST and CIFAR-10. The perturbations on CIFAR-10 are largely imperceptible by human eyes while they are more obvious on MNIST. This is mostly due to the uniform dark background of MNIST images (Luo et al., 2018) especially when L 0 is reduced and L 2 is increased. What we want to highlight is that the average number of queries used by our fuzzing attacks is significantly decreased by 10-18 folds and 2-5 folds for MNIST and CIFAR-10, respectively. As shown in Tables 3 and 4 of Appendix A, the median number of queries for fuzzing attacks are all smaller, on both MNIST and CIFAR-10, than those for Opt and Boundary attacks; the standard deviation results on number of queries for fuzzing attacks on CIFAR-10 are higher than those of Boundary and Opt attacks.

We also report average, median, and standard deviation results for untargeted attacks on ImageNet using fuzzing attacks in Table 7 of Appendix A. The small LocalFuzzer level is 10. We use 10 source examples and correspondingly 10 guidance images to perform the experiments. The average L 2 distance for fuzzing attacks is 6.3490, and the average number of queries is 102,652. Note that as reported in Table 1 of Cheng et al. (2019) , the average L2 distance for untargeted Opt attacks is between 3.1120 and 6.9796, and the average number of queries is between 71,100 and 237,342; the average L2 distance for untargeted Boundary attacks is between 3.7725 and 5.9791, and the average number of queries is between 123,407 and 260,797. Targeted Attacks We consider next label targeted attacks (Brendel et al., 2017; Cheng et al., 2019) where the adversarial goal is for an adversarial example to be misclassified as a target class y t such that y t = (y + 1) module 10 where y is the source class. The results for targeted attacks are shown in Table 2 . The second row in Figure 2 shows the successful adversarial examples from the targeted fuzzing attacks on MNIST and CIFAR-10. The perturbations for targeted attacks are visually larger than the perturbations for untargeted attacks. Similarly, the fuzzing attack decreases the average L 0 distance while increases the average L 2 and L ∞ distances. The fuzzing attacks also reduce the average number of queries by 8-9 folds and 2-2.5 folds for MNIST and CIFAR-10, respectively. Note that it is harder to find successful adversarial examples using LocalFuzzer levels of 300 and 500 on CIFAR-10 because of the larger feature space compared to MNIST and the smaller adversarial space in the targeted attacks compare to that of the untargeted attacks. As shown in Tables 5 and 6 of Appendix A, the median number of queries for fuzzing attacks are all smaller than those for Opt and Boundary attacks on MNIST, and that is also true for the fuzzing attack 100 setting on CIFAR-10; the standard deviation results on number of queries for fuzzing attacks on CIFAR-10 are higher than those of Boundary and Opt attacks, but that is not true for the fuzzing attack 100 setting on MNIST. Overall, the randomness advantages of the fuzzing approach help to reduce the average number of queries and L 0 distance by sacrificing a small amount of L 2 distance. The experimental results show that fuzzing attacks are feasible and effective. However, they potentially can be further strengthened by improving the fuzzing process such as seed selection, main direction selection, step selection, mutation operation selection, etc. It is important to note that minimizing L 2 distance could be the goal of many adversarial example generation algorithms, but is not necessarily the most important goal of real-world attackers. In other words, attackers' adversarial examples need not be "perfect" (in terms of L 2 distance). Whatever adversarial examples that are reasonably good (e.g., most humans can still recognize as the source class but models will be fooled) can be used by attackers. It is common in many types of real-world attacks that techniques need not be perfect. For example, in phishing attacks, super simple spoofed login webpages are still widely used by attackers. The results for untargeted attacks and targeted attacks are presented in Table 8 and Table 9 of Appendix A, respectively. We achieve 100% success bulk generation rate across runs in all experiments, which indicates the great benefits of the bulk generation capability of LocalFuzzer. It is also demonstrated that the "optimized" adversarial examples from Boundary attack and Opt attack can further be refined. LocalFuzzer takes relatively a smaller number of queries (i.e., 100, 1,000, and 5,000 in the experiments) compared with what was taken originally in Boundary attack and Opt attack, but can immediately generate more successful adversarial examples even with smaller L 2 distance from the source example. Meanwhile, the bulk generation of LocalFuzzer based on adversarial examples of white-box including C&W L 0 and L 2 attacks is also effective. These results indicate that Local-Fuzzer itself can be an independent and useful tool to augment many adversarial example generation algorithms including both black-box and white-box attacks.

5. CONCLUSION AND DISCUSSION:

Inspired by the similarities between attacking a machine learning model and testing the correctness or security bug of a program, we proposed fuzzing-based hard-label black-box attacks to generate adversarial examples. We designed two fuzzers, AdvFuzzer and LocalFuzzer, to explore multiple random paths between a source image and a guidance image, and the nearby space of each step along the way. We evaluated our fuzzing attacks using MNIST and CIFAR-10 datasets, and compared ours with four existing attacks including Boundary attack, Opt attack, and C&W L 0 and L 2 attacks. The experimental results demonstrated that our fuzzing attacks are feasible and effective. Moreover, LocalFuzzer has the bulk successful example generation capability and distance refinement capability on adversarial examples generated from different attack methods. We would recommend LocalFuzzer as an independent and useful tool for augmenting many adversarial example generation algorithms.

Our work provides evidence on adopting fuzz testing in the adversarial example generation domain.

Although the randomness advantage of the fuzzing attacks could help reduce the number of model queries, one limitation of our attacks is that they sacrifice the L 2 distance to a small extent. We expect that further improvement of the fuzzing process could be explored to construct more powerful fuzzing-based attacks. For example, potential ways for improvement could be a better guidance strategy in the main direction selection, a refined seed selection process, a refined mutation function, etc. We are working on improving our approach and we hope our fuzzing attacks could inspire more related research in the future.

A APPENDIX 

:

https://github.com/carlini/nn robust attacks

https://github.com/bethgelab/foolbox

https://github.com/LeMinhThong/blackbox-attack

Figures and Tables:

Figure 1: Basic Intuition of Our Attacks. Blue stars represent the main steps AdvFuzzer takes. Green and red stars represent the examples Local-Fuzzer generates. Red stars are adversarial examples close to the decision boundary.

rand = RandomSelect(S all ) 10: img mut = mutation(img rand ) 11: if (isTargeted and f (img mut ) == t) or (!isTargeted and f (img mut ) != s) then 12: S adv = S adv {img mut } 13:

Figure 2: Successful adversarial examples from fuzzing attacks on MNIST and CIFAR-10

: attack guidance, e.g., based on L 0 or L ∞ distance. Output: img adv : an adversarial example from a successful adversarial examples set S adv . 1: S adv ← ∅ 2: img cur ← img s 3: while size(S adv )== 0 and num steps < M AX ST EP S do : img adv = walk back(f, img s , S adv [0], s, t, medium level, isT argeted) 12: return img adv LocalFuzzer LocalFuzzer is described in Algorithm 2. Its goal is to generate a set of adversarial examples potentially around an input image img. An adversarial example set S adv and a set S all

Table content: <table><tr><td>4:</td><td>= SelectP erturbationAlongM ainDirection(img cur , img g , k)</td></tr><tr><td>5:</td><td>img cur = img cur +</td></tr><tr><td>6:</td><td/></tr></table>

True for targeted attack and False for untargeted attack, f uzzer level: level of local fuzzing. Output: S adv : a set of successful adversarial examples.

Table content: <table><tr><td>Algorithm 2 LocalFuzzer: generating a set of adversarial examples using fuzzing locally</td></tr><tr><td>Input: f : a black-box model,</td></tr><tr><td>img: an input image,</td></tr><tr><td>s: source image class,</td></tr><tr><td>t: target class,</td></tr><tr><td>isT argeted:</td></tr></table>

Average Results for Untargeted Attacks Avg L 2 Avg L ∞ # queries Avg L 0 Avg L 2 Avg L ∞ # queries

Table content: <table><tr><td/><td/><td colspan="2">MNIST</td><td/><td/><td colspan="2">CIFAR-10</td><td/></tr><tr><td colspan="2">Avg L 0 Boundary attack 769</td><td>1.1454</td><td>0.2657</td><td>115,134</td><td>3,071</td><td>0.1658</td><td>0.0182</td><td>128,296</td></tr><tr><td>Opt attack</td><td>784</td><td>1.0839</td><td>0.3067</td><td>67,536</td><td>3,072</td><td>0.1671</td><td>0.0164</td><td>56,438</td></tr><tr><td>C&amp;W L 0 attack</td><td>10</td><td>2.5963</td><td>0.9519</td><td>-</td><td>9</td><td>0.9988</td><td>0.4450</td><td>-</td></tr><tr><td>C&amp;W L 2 attack</td><td>749</td><td>1.4653</td><td>0.4299</td><td>-</td><td>3,072</td><td>0.1894</td><td>0.0226</td><td>-</td></tr><tr><td>Fuzzing attack 100</td><td>19</td><td>2.5536</td><td>0.9706</td><td>6,321</td><td>33</td><td>1.7838</td><td>0.5471</td><td>24,045</td></tr><tr><td>Fuzzing attack 300</td><td>19</td><td>2.5041</td><td>0.9661</td><td>14,697</td><td>32</td><td>1.7176</td><td>0.6593</td><td>56,678</td></tr><tr><td>Fuzzing attack 500</td><td>19</td><td>2.4525</td><td>0.9673</td><td>22,546</td><td>28</td><td>1.6822</td><td>0.6526</td><td>88,488</td></tr></table>

Average Results for Targeted AttacksAvg L 2 Avg L ∞ # queries Avg L 0 Avg L 2 Avg L ∞ # queriesComputation time. Computation time results for both untargeted and targeted attacks on MNIST and CIFAR-10 are presented in Table10 and Table 11of Appendix A, respectively. The small LocalFuzzer level for fuzzing attacks is 100. The results are calculated based on 10 source examples. In term of untargeted attacks, fuzzing attacks take significantly less total time and generation time to generate successful adversarial examples compared to Boundary and Opt attacks. As for targeted attacks, fuzzing attacks still take less total time and generation time on MNIST, and have comparable results as Boundary and Opt attacks on CIFAR-10.

Table content: <table><tr><td/><td/><td colspan="2">MNIST</td><td/><td/><td colspan="2">CIFAR-10</td><td/></tr><tr><td colspan="2">Avg L 0 Boundary attack 773</td><td>1.8393</td><td>0.4421</td><td>126,433</td><td>3,071</td><td>0.2368</td><td>0.0224</td><td>128,657</td></tr><tr><td>Opt attack</td><td>784</td><td>1.9040</td><td>0.4525</td><td>108,556</td><td>3,072</td><td>0.6231</td><td>0.0461</td><td>110,124</td></tr><tr><td>C&amp;W L 0 attack</td><td>26</td><td>3.6744</td><td>0.8853</td><td>-</td><td>19</td><td>1.7123</td><td>0.6256</td><td>-</td></tr><tr><td>C&amp;W L 2 attack</td><td>742</td><td>2.1752</td><td>0.5088</td><td>-</td><td>3,072</td><td>0.3491</td><td>0.0425</td><td>-</td></tr><tr><td>Fuzzing attack 100</td><td>43</td><td>3.3925</td><td>0.9750</td><td>13,364</td><td>57</td><td>2.4066</td><td>0.6997</td><td>50,084</td></tr><tr><td>Fuzzing attack 300</td><td>42</td><td>3.3553</td><td>0.9800</td><td>35,002</td><td>109</td><td>3.5439</td><td>0.7579</td><td>272,274</td></tr><tr><td>Fuzzing attack 500</td><td>41</td><td>3.3690</td><td>0.9782</td><td>54,811</td><td>104</td><td>3.4381</td><td>0.7652</td><td>412,766</td></tr></table>

4.2 RESULTS ON APPLYING LOCALFUZZER ON SUCCESSFUL ADVERSARIAL EXAMPLES We now apply LocalFuzzer on successful adversarial examples generated from Boundary attack, Opt attack, C&W L 0 and L 2 attacks, and our fuzzing attacks to more intensively evaluate the bulk generation capability of LocalFuzzer. We leverage the successful adversarial examples from the experiments in Section 4.1 for both untargeted and targeted attacks. For fuzzing attacks, we use the adversarial examples generated with a LocalFuzzer level of 500 which are shown in the third row of fuzzing attacks in both Table 1 and Table 2. Three experiments with different LocalFuzzer levels of 100, 1,000, and 5,000 are performed. We report six metrics including M1: success bulk generation rate (i.e., the percent of bulk runs returning successful examples); M2: average number of successful examples generated in a bulk run; M3: success bulk generation rate with lower L 2 (i.e., percent of success bulk runs returning adversarial examples with L 2 lower than that of the seed image); M4: average number of successful examples with lower L 2 in a bulk run; M5: average decreased L 2 of successful examples with lower L 2 ; M6: average L 2 decreasing rate of successful examples with lower L 2 .

Table content: <table/>

Median Results (corresponding to Table 1) for Untargeted Attacks MedianL 2 Median L ∞ # queries Median L 0 Median L 2 Median L ∞ # queries

Table content: <table><tr><td/><td/><td>MNIST</td><td/><td/><td/><td colspan="2">CIFAR-10</td><td/></tr><tr><td colspan="2">Median L 0 Boundary attack 770</td><td>1.1400</td><td>0.2614</td><td>114,843</td><td>3072</td><td>0.1392</td><td>0.0157</td><td>130,499</td></tr><tr><td>Opt attack</td><td>784</td><td>1.0793</td><td>0.2921</td><td>62,995</td><td>3072</td><td>0.1619</td><td>0.0150</td><td>55,762</td></tr><tr><td>C&amp;W L 0 attack</td><td>9</td><td>2.5594</td><td>0.9824</td><td>-</td><td>6</td><td>0.9896</td><td>0.4737</td><td>-</td></tr><tr><td>C&amp;W L 2 attack</td><td>750</td><td>1.4672</td><td>0.4268</td><td>-</td><td>3072</td><td>0.1666</td><td>0.0185</td><td>-</td></tr><tr><td>Fuzzing attack 100</td><td>19</td><td>2.5079</td><td>0.9961</td><td>5,902</td><td>16</td><td>1.1017</td><td>0.5782</td><td>7,306</td></tr><tr><td>Fuzzing attack 300</td><td>18</td><td>2.4804</td><td>0.9922</td><td>13,436</td><td>20</td><td>1.5417</td><td>0.6916</td><td>18,588</td></tr><tr><td>Fuzzing attack 500</td><td>18</td><td>2.3291</td><td>0.9922</td><td>20,381</td><td>20</td><td>1.4422</td><td>0.6745</td><td>17,614</td></tr></table>

Standard Deviation Results (corresponding to Table 1) for Untargeted Attacks

Table content: <table><tr><td/><td/><td>MNIST</td><td/><td/><td>CIFAR-10</td></tr><tr><td/><td>SD L 0</td><td colspan="3">SD L 2 SD L ∞ # queries SD L 0</td><td colspan="2">SD L 2 SD L ∞ # queries</td></tr><tr><td>Boundary attack</td><td colspan="2">6.6278 0.3091 0.0730</td><td>13,622</td><td colspan="2">2.5784 0.1045 0.0114</td><td>5,377</td></tr><tr><td>Opt attack</td><td>0</td><td>0.2897 0.1141</td><td>15,081</td><td colspan="2">0.2611 0.1016 0.0121</td><td>24,704</td></tr><tr><td>C&amp;W L 0 attack</td><td colspan="2">5.5938 0.7662 0.0923</td><td>-</td><td colspan="2">7.9998 0.7724 0.2894</td><td>-</td></tr><tr><td>C&amp;W L 2 attack</td><td colspan="2">16.5430 0.4513 0.1254</td><td>-</td><td colspan="2">0.1407 0.1665 0.0220</td><td>-</td></tr><tr><td colspan="3">Fuzzing attack 100 8.8428 0.6503 0.0915</td><td>3,433</td><td colspan="2">20.4103 0.7776 0.1828</td><td>25,550</td></tr><tr><td colspan="3">Fuzzing attack 300 9.6684 0.6617 0.0913</td><td>9,613</td><td colspan="2">38.2232 1.0067 0.1669</td><td>95,872</td></tr><tr><td colspan="3">Fuzzing attack 500 9.1561 0.6417 0.0907</td><td>14,451</td><td colspan="2">32.1710 1.0792 0.1837</td><td>167,639</td></tr></table>

Median Results (corresponding to Table 2) for Targeted Attacks MedianL 2 Median L ∞ # queries Median L 0 Median L 2 Median L ∞ # queries

Table content: <table><tr><td/><td/><td>MNIST</td><td/><td/><td/><td colspan="2">CIFAR-10</td><td/></tr><tr><td colspan="2">Median L 0 Boundary attack 776</td><td>1.7285</td><td>0.4090</td><td>130,896</td><td>3072</td><td>0.2222</td><td>0.0213</td><td>129,650</td></tr><tr><td>Opt attack</td><td>784</td><td>1.6717</td><td>0.4194</td><td>120,291</td><td>3072</td><td>0.2587</td><td>0.0243</td><td>128,785</td></tr><tr><td>C&amp;W L 0 attack</td><td>26</td><td>4.0491</td><td>0.9975</td><td>-</td><td>18</td><td>1.8128</td><td>0.6945</td><td>-</td></tr><tr><td>C&amp;W L 2 attack</td><td>740</td><td>2.3436</td><td>0.5545</td><td>-</td><td>3072</td><td>0.3594</td><td>0.0431</td><td>-</td></tr><tr><td>Fuzzing attack 100</td><td>42</td><td>3.1988</td><td>0.9961</td><td>14,145</td><td>46</td><td>2.3002</td><td>0.7186</td><td>29,702</td></tr><tr><td>Fuzzing attack 300</td><td>35</td><td>3.1916</td><td>0.9961</td><td>35,100</td><td>82</td><td>3.3722</td><td>0.7592</td><td>178,573</td></tr><tr><td>Fuzzing attack 500</td><td>37</td><td>3.2281</td><td>0.9961</td><td>58,106</td><td>77</td><td>3.3818</td><td>0.7922</td><td>296,279</td></tr></table>

Standard Deviation Results (corresponding to Table 2) for Targeted Attacks

Table content: <table><tr><td/><td/><td>MNIST</td><td/><td/><td>CIFAR-10</td><td/></tr><tr><td/><td>SD L 0</td><td colspan="2">SD L 2 SD L ∞ # queries</td><td>SD L 0</td><td colspan="2">SD L 2 SD L ∞ # queries</td></tr><tr><td>Boundary attack</td><td colspan="2">7.6341 0.6587 0.1605</td><td>8,004</td><td>1.9573</td><td>0.1248 0.0135</td><td>2,987</td></tr><tr><td>Opt attack</td><td>0</td><td>0.8567 0.1546</td><td>51,251</td><td>0.1407</td><td>1.2503 0.0693</td><td>52,281</td></tr><tr><td>C&amp;W L 0 attack</td><td colspan="2">10.1065 0.8887 0.0259</td><td>-</td><td colspan="2">11.4445 0.8224 0.2214</td><td>-</td></tr><tr><td>C&amp;W L 2 attack</td><td colspan="2">16.1253 0.5706 0.1221</td><td>-</td><td>0.3555</td><td>0.2054 0.0252</td><td>-</td></tr><tr><td colspan="3">Fuzzing attack 100 20.1423 0.8957 0.0553</td><td>5,616</td><td colspan="2">41.8556 1.2002 0.1500</td><td>58,629</td></tr><tr><td colspan="3">Fuzzing attack 300 20.2546 0.8563 0.0471</td><td>15,716</td><td colspan="2">92.9558 1.8192 0.1150</td><td>231,510</td></tr><tr><td colspan="3">Fuzzing attack 500 18.4257 0.8826 0.0508</td><td>26,317</td><td colspan="2">103.7606 1.7056 0.1280</td><td>370,780</td></tr></table>

Average, Median, and Standard Deviation Results for Untargeted Attacks on ImageNet using Fuzzing attacks. The small LocalFuzzer level is 10. Note that as reported in Table1ofCheng et al. (2019), the average L 2 distance for untargeted opt attacks is between 3.1120 and 6.9796; the average L 2 distance for untargeted boundary attacks is between 3.7725 and 5.9791.

Table content: <table><tr><td/><td>L 0</td><td>L 2</td><td>L ∞</td><td># queries</td></tr><tr><td colspan="5">Average 311 6.3490 0.8808 102,652</td></tr><tr><td colspan="4">Median 224 5.9794 0.9090</td><td>48,507</td></tr><tr><td>SD</td><td colspan="4">317 4.0062 0.0873 120,909</td></tr></table>

Bulk Generation of Successful Examples for Untargeted Attacks

Table content: <table><tr><td/><td>Attack</td><td>M1</td><td>M2</td><td>M3</td><td>M4</td><td>M5</td><td>M6</td></tr><tr><td/><td>Boundary attack 100</td><td>100%</td><td>54</td><td>48.10%</td><td>8</td><td colspan="2">2.98e-3 0.28%</td></tr><tr><td/><td colspan="2">Boundary attack 1,000 100%</td><td>736</td><td colspan="4">58.23% 24 4.07e-3 0.36%</td></tr><tr><td/><td colspan="7">Boundary attack 5,000 100% 3,851 55.70% 56 4.93e-3 0.48%</td></tr><tr><td/><td>Opt attack 100</td><td>100%</td><td>63</td><td colspan="4">66.00% 16 2.45e-3 0.23%</td></tr><tr><td/><td>Opt attack 1,000</td><td>100%</td><td>727</td><td colspan="4">59.00% 50 4.96e-3 0.47%</td></tr><tr><td/><td>Opt attack 5,000</td><td colspan="6">100% 3,888 73.00% 112 5.64e-3 0.56%</td></tr><tr><td/><td>Fuzzing attack 100</td><td>100%</td><td>92</td><td>67.00%</td><td>7</td><td colspan="2">1.97e-2 0.90%</td></tr><tr><td>MNIST</td><td>Fuzzing attack 1,000</td><td>100%</td><td>939</td><td>100%</td><td colspan="3">75 3.19e-2 1.46%</td></tr><tr><td/><td>Fuzzing attack 5,000</td><td colspan="2">100% 4,730</td><td>100%</td><td colspan="3">425 3.99e-2 1.81%</td></tr><tr><td/><td>C&amp;W L 0 attack 100</td><td>100%</td><td>92</td><td>59.00%</td><td>7</td><td colspan="2">5.61e-3 0.21%</td></tr><tr><td/><td colspan="2">C&amp;W L 0 attack 1,000 100%</td><td>950</td><td colspan="4">99.00% 63 8.37e-3 0.34%</td></tr><tr><td/><td colspan="5">C&amp;W L 0 attack 5,000 100% 4778 99.00% 475</td><td>1.11</td><td>0.46%</td></tr><tr><td/><td>C&amp;W L 2 attack 100</td><td>100%</td><td>81</td><td>18.00%</td><td>1</td><td colspan="2">8.41e-4 0.06%</td></tr><tr><td/><td colspan="2">C&amp;W L 2 attack 1,000 100%</td><td>861</td><td>30.00%</td><td>2</td><td colspan="2">1.10e-3 0.07%</td></tr><tr><td/><td colspan="4">C&amp;W L 2 attack 5,000 100% 4534 37.00%</td><td>2</td><td colspan="2">1.14e-3 0.08%</td></tr><tr><td/><td>Boundary attack 100</td><td>100%</td><td>57</td><td>3.26%</td><td>3</td><td colspan="2">0.14e-3 0.07%</td></tr><tr><td/><td colspan="2">Boundary attack 1,000 100%</td><td>676</td><td>6.52%</td><td>4</td><td colspan="2">0.17e-3 0.07%</td></tr><tr><td/><td colspan="4">Boundary attack 5,000 100% 3,726 9.78%</td><td>8</td><td colspan="2">0.29e-3 0.10%</td></tr><tr><td/><td>Opt attack 100</td><td>100%</td><td>69</td><td>2.00%</td><td>2</td><td colspan="2">0.15e-3 0.04%</td></tr><tr><td/><td>Opt attack 1,000</td><td>100%</td><td>757</td><td>7.00%</td><td>3</td><td colspan="2">0.18e-3 0.06%</td></tr><tr><td/><td>Opt attack 5,000</td><td colspan="3">100% 3,936 10.00%</td><td>4</td><td colspan="2">0.12e-3 0.04%</td></tr><tr><td/><td>Fuzzing attack 100</td><td>100%</td><td>91</td><td>24.21%</td><td>8</td><td colspan="2">6.34e-3 0.42%</td></tr><tr><td>CIFAR-10</td><td>Fuzzing attack 1,000</td><td>100%</td><td>943</td><td colspan="4">58.95% 54 8.93e-3 0.56%</td></tr><tr><td/><td>Fuzzing attack 5,000</td><td colspan="6">100% 4,774 80.00% 258 1.23e-2 0.87%</td></tr><tr><td/><td>C&amp;W L 0 attack 100</td><td>100%</td><td>100</td><td>22.00%</td><td>7</td><td colspan="2">8.28e-4 0.07%</td></tr><tr><td/><td colspan="2">C&amp;W L 0 attack 1,000 100%</td><td>990</td><td colspan="4">69.00% 30 1.36e-3 0.13%</td></tr><tr><td/><td colspan="7">C&amp;W L 0 attack 5,000 100% 4953 80.00% 179 1.78e-3 0.18%</td></tr><tr><td/><td>C&amp;W L 2 attack 100</td><td>100%</td><td>97</td><td colspan="4">53.00% 16 1.12e-4 0.05%</td></tr><tr><td/><td colspan="2">C&amp;W L 2 attack 1,000 100%</td><td>973</td><td colspan="4">62.00% 100 2.13e-4 0.08%</td></tr><tr><td/><td colspan="7">C&amp;W L 2 attack 5,000 100% 4833 66.00% 419 2.73e-4 0.11%</td></tr></table>

Bulk Generation of Successful Examples For Targeted Attacks

Table content: <table><tr><td/><td>Attack</td><td>M1</td><td>M2</td><td>M3</td><td>M4</td><td>M5</td><td>M6</td></tr><tr><td/><td>Boundary attack 100</td><td>100%</td><td>44</td><td>45.68%</td><td colspan="3">11 2.27e-3 0.14%</td></tr><tr><td/><td colspan="2">Boundary attack 1,000 100%</td><td>546</td><td>51.85%</td><td colspan="3">44 4.61e-3 0.31%</td></tr><tr><td/><td colspan="7">Boundary attack 5,000 100% 3,105 45.68% 110 6.21e-3 0.39%</td></tr><tr><td/><td>Opt attack 100</td><td>100%</td><td>46</td><td>53.33%</td><td colspan="3">15 3.71e-3 0.21%</td></tr><tr><td/><td>Opt attack 1,000</td><td>100%</td><td>598</td><td>56.67%</td><td colspan="3">62 6.08e-3 0.34%</td></tr><tr><td/><td>Opt attack 5,000</td><td colspan="6">100% 3,333 67.67% 279 7.11e-3 0.42%</td></tr><tr><td/><td>Fuzzing attack 100</td><td>100%</td><td>93</td><td>82.22%</td><td colspan="3">12 1.32e-2 0.42%</td></tr><tr><td>MNIST</td><td>Fuzzing attack 1,000</td><td>100%</td><td>946</td><td colspan="4">100.00% 141 2.69e-2 0.89%</td></tr><tr><td/><td>Fuzzing attack 5,000</td><td colspan="6">100% 4,722 98.89% 837 3.54e-2 1.17%</td></tr><tr><td/><td>C&amp;W L 0 attack 100</td><td>100%</td><td>88</td><td>85.00%</td><td colspan="3">11 5.92e-3 0.17%</td></tr><tr><td/><td colspan="2">C&amp;W L 0 attack 1,000 100%</td><td>897</td><td colspan="4">99.00% 133 8.76e-3 0.26%</td></tr><tr><td/><td colspan="3">C&amp;W L 0 attack 5,000 100% 4532</td><td colspan="4">98.00% 860 1.18e-2 0.36%</td></tr><tr><td/><td>C&amp;W L 2 attack 100</td><td>100%</td><td>79</td><td>35.00%</td><td>1</td><td colspan="2">9.08e-4 0.04%</td></tr><tr><td/><td colspan="2">C&amp;W L 2 attack 1,000 100%</td><td>851</td><td>49.00%</td><td>3</td><td colspan="2">1.39e-3 0.06%</td></tr><tr><td/><td colspan="3">C&amp;W L 2 attack 5,000 100% 4476</td><td>59.00%</td><td>6</td><td colspan="2">1.19e-3 0.06%</td></tr><tr><td/><td>Boundary attack 100</td><td>100%</td><td>41</td><td>6.90%</td><td colspan="3">10 0.21e-3 0.04%</td></tr><tr><td/><td colspan="2">Boundary attack 1,000 100%</td><td>548</td><td>10.34%</td><td colspan="3">12 0.20e-3 0.05%</td></tr><tr><td/><td colspan="4">Boundary attack 5,000 100% 2,947 10.34%</td><td colspan="3">42 0.20e-3 0.05%</td></tr><tr><td/><td>Opt attack 100</td><td>100%</td><td>54</td><td>15.56%</td><td>8</td><td colspan="2">0.14e-3 0.02%</td></tr><tr><td/><td>Opt attack 1,000</td><td>100%</td><td>676</td><td>14.44%</td><td colspan="3">11 0.22e-3 0.04%</td></tr><tr><td/><td>Opt attack 5,000</td><td colspan="6">100% 3,084 20.00% 277 0.28e-3 0.05%</td></tr><tr><td/><td>Fuzzing attack 100</td><td>100%</td><td>96</td><td>58.67%</td><td colspan="3">19 0.98e-3 0.04%</td></tr><tr><td>CIFAR-10</td><td>Fuzzing attack 1,000</td><td>100%</td><td>979</td><td colspan="4">90.67% 149 1.67e-3 0.08%</td></tr><tr><td/><td>Fuzzing attack 5,000</td><td colspan="6">100% 4,920 96.00% 883 2.29e-3 0.09%</td></tr><tr><td/><td>C&amp;W L 0 attack 100</td><td>100%</td><td>100</td><td>41.00%</td><td>9</td><td colspan="2">7.87e-4 0.04%</td></tr><tr><td/><td colspan="2">C&amp;W L 0 attack 1,000 100%</td><td>981</td><td>92.00%</td><td colspan="3">69 1.36e-3 0.09%</td></tr><tr><td/><td colspan="3">C&amp;W L 0 attack 5,000 100% 4902</td><td colspan="4">99.00% 397 1.78e-3 0.14%</td></tr><tr><td/><td>C&amp;W L 2 attack 100</td><td>100%</td><td>97</td><td>77.00%</td><td colspan="3">23 1.41e-4 0.04%</td></tr><tr><td/><td colspan="2">C&amp;W L 2 attack 1,000 100%</td><td>971</td><td colspan="4">89.00% 163 2.58e-4 0.07%</td></tr><tr><td/><td colspan="3">C&amp;W L 2 attack 5,000 100% 4875</td><td colspan="4">90.00% 726 3.52e-4 0.09%</td></tr></table>

Untargeted Attacks: Average, Median, and Standard Deviation Computation Time Results (in seconds). Total time is the time spent for each successful attack attempt. Generation time is the time used for generating images during each attack attempt. Query time is the difference between total time and generation time, not shown in the table.

Table content: <table><tr><td/><td>Attacks</td><td colspan="4">MNIST Total Time Generation Time Total Time Generation Time CIFAR-10</td></tr><tr><td/><td>Boundary attack</td><td>26.3981</td><td>15.5242</td><td>41.2357</td><td>21.3540</td></tr><tr><td>Average</td><td>Opt attack</td><td>96.2709</td><td>16.6981</td><td>85.6906</td><td>15.9244</td></tr><tr><td/><td>Fuzzing attack 100</td><td>7.1731</td><td>0.7869</td><td>10.7523</td><td>1.5613</td></tr><tr><td/><td>Boundary attack</td><td>25.5868</td><td>14.8883</td><td>41.1243</td><td>21.1549</td></tr><tr><td>Median</td><td>Opt attack</td><td>94.5755</td><td>16.3971</td><td>77.6759</td><td>14.7546</td></tr><tr><td/><td>Fuzzing attack 100</td><td>6.5157</td><td>0.7053</td><td>7.3152</td><td>1.0742</td></tr><tr><td/><td>Boundary attack</td><td>2.7221</td><td>2.0243</td><td>0.8511</td><td>1.4848</td></tr><tr><td>SD</td><td>Opt attack</td><td>16.8229</td><td>1.9818</td><td>25.9558</td><td>2.8943</td></tr><tr><td/><td>Fuzzing attack 100</td><td>2.3889</td><td>0.2903</td><td>7.6872</td><td>1.1437</td></tr></table>

Targeted Attacks: Average, Median, and Standard Deviation Computation Time Results (in seconds). Total time is the time spent for each successful attack attempt. Generation time is the time used for generating images during each attack attempt. Query time is the difference between total time and generation time, not shown in the table.

Table content: <table><tr><td/><td>Attacks</td><td colspan="4">MNIST Total Time Generation Time Total Time Generation Time CIFAR-10</td></tr><tr><td/><td>Boundary attack</td><td>27.1896</td><td>16.1106</td><td>38.5594</td><td>20.0595</td></tr><tr><td>Average</td><td>Opt attack</td><td>45.7278</td><td>5.0152</td><td>145.9843</td><td>9.0527</td></tr><tr><td/><td>Fuzzing attack 100</td><td>26.0137</td><td>2.7582</td><td>91.0437</td><td>13.7374</td></tr><tr><td/><td>Boundary attack</td><td>27.5087</td><td>16.2304</td><td>38.1913</td><td>19.7272</td></tr><tr><td>Median</td><td>Opt attack</td><td>37.3375</td><td>4.5640</td><td>199.1068</td><td>10.7309</td></tr><tr><td/><td>Fuzzing attack 100</td><td>25.5663</td><td>2.7282</td><td>86.0931</td><td>12.9244</td></tr><tr><td/><td>Boundary attack</td><td>1.8790</td><td>1.5028</td><td>1.4813</td><td>1.3669</td></tr><tr><td>SD</td><td>Opt attack</td><td>21.2563</td><td>0.8855</td><td>86.8058</td><td>2.6389</td></tr><tr><td/><td>Fuzzing attack 100</td><td>2.7882</td><td>0.3020</td><td>74.0702</td><td>11.2148</td></tr></table>

Peer review (iclr2020):
This paper proposes a new decision based attack algorithm. Given a targeted example and original example, the algorithm gradually check samples on this path with some local noise randomly added. The authors show that their approach can get better L_0 perturbation on MNIST and CIFAR-10. Although the algorithm is novel, there are several weaknesses in both algorithm design and experimental evaluation. Experimental comparisons: 1. From the tables, the authors show improved L0 perturbation but with much worse L2 perturbation, which was the focus in both Boundary and OPT attack. Therefore it*s not very convincing that the proposed method can improve the quality of adversarial example on standard L2 or even Linfty, L1 perturbations. As mentioned in the first paragraph of section 3.2, the authors mentioned that their method can also be applied to L2 perturbation, so a more fair comparison would be trying L2 version of Fussing-based attack and comparing it with Boundary and OPT attacks. From Figure 2 we can clearly observe perturbations, and comparing with the quality we got using L2 perturbation based algorithms (Boundary and OPT attack), I feel the proposed algorithm leads to human-perceptible perturbations. 2. I am quite concern about whether AdvFuzzer is sensitive to the target image, since it only samples points on the path toward one target image, but the goal of either targeted or untargeted attack is not to perturb toward a particular target image, but to find the minimum perturbation that changes label. So, how do you select the target image? Is the algorithm sensitive to this selection? 3. No experiments on ImageNet (note that both Boundary and OPT attacks have been tested on ImageNet). Regarding the algorithm : 4. The algorithm might have huge memory requirement since the set Sadv keeps growing. What*s the max size of Sadv set in your experiments?