BOSH: An Efficient Meta Algorithm for Decision-based Attacks
Authors: Zhenxin Xiao
Puyudi Yang
Yuchen Jiang
Kai-Wei Chang
Cho-Jui Hsieh
Venue:  (2020)

Abstract: Adversarial example generation becomes a viable method for evaluating the robustness of a machine learning model. In this paper, we consider hard-label black- box attacks (a.k.a. decision-based attacks), which is a challenging setting that generates adversarial examples based on only a series of black-box hard-label queries. This type of attacks can be used to attack discrete and complex models, such as Gradient Boosting Decision Tree (GBDT) and detection-based defense models. Existing decision-based attacks based on iterative local updates often get stuck in a local minimum and fail to generate the optimal adversarial example with the smallest distortion. To remedy this issue, we propose an efficient meta algorithm called BOSH-attack, which tremendously improves existing algorithms through Bayesian Optimization (BO) and Successive Halving (SH). In particular, instead of traversing a single solution path when searching an adversarial example, we maintain a pool of solution paths to explore important regions. We show empirically that the proposed algorithm converges to a better solution than existing approaches, while the query count is smaller than applying multiple random initializations by a factor of 10.

Under review as a conference paper at ICLR 2020
BOSH: AN EFFICIENT META ALGORITHM DECISION-BASED ATTACKS
FOR
Anonymous authors Paper under double-blind review
ABSTRACT
Adversarial example generation becomes viable method for evaluating the ro- bustness of a machine learning model. In this paper. we consider hard-label black- box attacks (a.k.a. decision-based attacks), which is a challenging setting that generates adversarial examples based only a series of black-box hard-label queries. This type of attacks can be used attack discrete and complex models, such Gradient Boosting Decision Tree (GBDT) and detection-based defense models. Existing decision- based attacks based on iterative local updates often get stuck in local minimum and fail to generate the optimal adversarial example with the smallest perturbation. To remedy this issue, we propose an efficient meta algorithm called BOSH-attace which tremendously improves existing algorithms through Bayesian Optimization (BO) and Successive Halving (SH). In particular, instead of traversing single solution path when searching an adversarial exam- ple, we maintain pool of solution paths to explore important regions. We show empirically that the proposed algorithm converges to a better solution than exist- ing approaches, while the query count is smaller than applying multiple random initializations by a factor of 10.
INTRODUCTION
It has been shown that machine learning models, including deep neural networks, vulnerable adversarial examples (Goodfellow et al. 2014 Szegedy et al., [2013] Chen et al.] 2017a). Therefore, evaluating the robustness of given model becomes crucial security sensitive applications. In order to evaluate the robustness of deep neural networks, researchers have developed "attack algo- rithms" to generate adversarial examples that can mislead given neural network while being as close as possible to the original example [Goodfellow et al.) 2014 Moosavi-Dezzooli et al.) 2016 Carlini & Wagner] (2017b] Chen et al., 2017b). Most of these attack methods are based on maxi- mizing loss function with gradient-based optimizer, where the gradient is either computed by pack-propagation (in the white-box setting) or finite-difference estimation (in the soft-label black- box setting). Although these methods work well on standard neural networks, when it comes to complex or even discontinuous models, such as decision trees and detection beaectioo--bsed defense models, they cannot be directly applied because the gradient is not available.
Hard-label black-box attacks, also known as decision- based attacks, consider the most difficult but realistic setting where the attacker has information about the model structure and parameters, and the only valid operation is to query the model to get the corresponding decision- (hard-label) output (Brendel al., 2017). This type of attacks can be used as a "universal" way evaluate robustness of any given models, no matter continuous or discrete. For instance, Cheng et al. (2018); Chen et al. 2019a) have applied decision-based attacks for evaluating robustness of Gradient Boost- ing Decision Trees (GBDT) and random forest. Current decision-
attacks, including Brendel al. (2017): Cheng et al. 2018); Chen et al.] (2019b); Cheng et al. (2019), are based on iterative local updates- starting from an initial point on the decision surface, they iteratively move the points along the surface until reaching a local minimum (in terms of distance to the original example). The update is often based on gradient estimation or some other heuristics. However, the local update nature makes these methods sensitive to the starting point. As we demonstrate in Figure [(a) the perturbation of converged adversarial examples for neural network are quite different for different initialization configurations, and this phenomenon becomes more severe when it comes to discrete models such GBDTs (see Figure ((b).. This makes decision-based attacks converge to a sub-

---

Under review as a conference paper at ICLR 2020
optimal perturbation. As result, the solution cannot really reflect the robustness of the targeted model.
To overcome these difficulties and make decision-basee attacks better reflect the robustness of mod- els, we propose meta algorithm called BOSH-attack that consistently boosts the solution quality of existing iterative local update based attacks. Our main idea is to combine Bayesian optimization, which finds solution closer to global optimum but suffers from high computation cost, with iterative local updates, which converges fast but often get stuck in local minimum. Specifically, given deci- sion based attack A, our algorithm maintains a pool of solutions and at each iteration we run A for m steps on each solution. The proposed Bayesian Optimization resampling (BO) and Successive Halving (SH) are then used to explore important solution space based on current information and cut out unnecessary solution paths.
Our contributions are summarized below:
1. We conduct thorough experiments to show that current decision- based attacks often con- verge to a local optimum, thus further improvements are required.
2. Based on the idea of Bayesian optimization and successive halving, we design meta algo- rithm to boost the performance of current decision-based attack algorithms and encourage them find a much smaller adversarial perturbation efficiently.
3. Comprehensive experiments demonstrate that BOSH-attack can consistently boost existing decision- based attacks to find better examples with much smaller perturbation. In addition to the standard neural network models, also test algorithms attacking discrete GBDT models and detector- beteetor-based defense models. Moreover, our algorithm can reduce the computation cost by 10x compared to the naive approach.
2 BACKGROUND AND RELATED WORK
Given a classification model F Rd + (1...., C} and an example To. adversarial attacks aim to find the adversarial example that is closest zg. For example, an untargeted attack aims to find the minimum perturbation to change the predicted class, which corresponds to the following optimization problem:
min ||o|| s.t. F(Zo + 5) # F(ro).
(1)
Exactly minimizing (T) is usually intractable; therefore, we can only expect to get a feasible solution of (T) while hoping | to be small possible.
White-box Attack. For neural networks, we can replace the constraint in IT by a loss func- tion defined the logit layer output, leading to continuous optimization problem which can be solved by gradient-based optimizers. This approach has been used in popular methods such as FGSM (Goodfellow al., 2014), C&W attack (Carlini & Wagner] 2017b) and PGD attack (Madry iet al.) (017).. All these boite-box attacks developed for neural networks assume the existence of the gradient. However, for models with discrete components such GBDT, the objective cannot be easily defined and gradient-based white-box attacks are not applicable. There are few white-box attacks developed for specific discrete models, such as Mixed Integer Linear Programming (MILP) approach for attacking tree ensemble (Kantchelian et al., (016). However, those algorithms are time consuming and require significant efforts for developing each model.
Soft-label Black-box Attack Black box setting considers the cases when an attacker has no direct access to the model's parameter and architecture, and the only valid operation is to query input examples and get the corresponding model output. In the soft-label black box setting, it is assumed that the model outputs the probability of each label for an input query. Chen et al. (017b) showed still be formulated as optimization problem where the objective function value
that the attack can be computed while the gradient is unavailable. Based on this, various zeroth order optimization algorithms have been proposed, including IES-attack (Ilyas et al. 20188)) EAD attack (Chen al. 2018). bandit-attack (Iyys et al., 20186), Autozoom (Tu et al. 2019), Genetic algorithm (Alzantot al. 2018).
Hard-label Black-box attack (Decision-based) attack) black box attack (also known as decision-based attack). In contrast to the soft-label setting, the
In this paper, we focus on the hard-label
2

---

Under review as a conference paper at ICLR 2020
attacker can only query the model and get the top-1 predicted label without any probability in- formation. To minimize the perturbation in the decision- -bssdd setting, [Brendel et al. (2017) first proposed a Boundary Attack based on random walk on the decision surface. Later on, Cheng et al. (2018) showed that hard-label attack can be reformulated as another continuous optimization prob- lem, and zeroth order optimization algorithms such NES can be used to solve this problem. Cheng ct al. (2019) further reduces the queries by only calculating the sign of ZOO updating function, and Chen al. 2019b) proposed another algorithm improve over boundary attack. Such methods can converge quickly but suffer from local optimum problems, and thus require more careful and thorough search in the solution space.
Probability based black-box optimization There are two commonly used methods to solve a black-box or non-differentiable optimization problem: gradient- based and probabilistic-baset al- gorithms. Gradient- methods are based on iterative local updates until convergence, while probabilistic-asser algorithms such as Bayesian optimization (BO) (Pelikan et al. 1999; Snoek et al.) 2012) approximate the objective function by a probabilistic model. Generally speaking, baased methods commonly used in black-box attack because it converges fast. How- ever, these methods often stuck in some local optimal directions, especially when the searching space is high dimensional and non-convex. Probabilistic-basee algorithms
frequently used in low-dimensional problems such as hyperparameter tuning and can have a better chance to find more global optimal values (Snoek et al. 2012 Bergstra et al. 2011). However, the computation cost grows exponentially while the dimension increases and quickly become unacceptable. Therefore, they cannot be directly applied generate adversarial examples. In this paper, we attempt to com- bine Bayesian Optimization and iterative local updates to improve the solution quality of current attack algorithms while being able to scale to high dimensional problems.
Combinatorial heuristic and genetic algorithms There exist various heuristic algorithms com- monly applied to combinatorial optimization problems. In these algorithms, they try to leverage the effects between greedy and random. Commonly, they will search for different directions and drop the bad ones, and then put more attention on the relatively good candidates. Greedy randomized adaptive search (Feo & Resende 1995) finds good solutions in an iterative way. It first generates a set of solutions and use a greedy function to rank these solutions. Later, good candidates are placed in a restricted candidate list, and randomly chosen when forming the solution. Tabu search (Glover & Laguna| 1999) selects a candidate and checks its immediate neighbors, trying find an improved solution. In order to avoid stucking in local optimal areas, it maintains a list called tabu list to store past good solutions (often local optimal solutions). In further searches, it will prevent from look- ing for this areas. Other approaches like Genetic Algorithms (GA) and Simulated Annealing (SA) also try to adopt random in the searching process. In this paper, we simply use Successive Halving (SH) (Jamieson & Talwalkar, 2016) to remove unimportant candidate configurations iteratively. The details can be found Section
3 THE PROPOSED ALGORITHM
Observation: Decision based attacks are easily stuck in local optimum. Most existing adver- sarial attacks adopt iterative local updates to find adversarial examples- - starting from an initial point, they iteratively update the solution until convergence. For example, in white-box attacks such as C&W and PGD methods, they aim at optimizing a non-convex loss function by iterative gradient updates. In Figure [(a)] we plot the 2-dimensional projection of the decision surface of neural network. We can observe that there are two local minimums] Results show that there are two local minimums and the attack algorithm converges one of them according the the initialization region. Similarly, in decision- based attacks, existing methods start from some point on the decision surface and then iteratively update the point locally on the surface either by gradient update (Cheng et al., 2018 Chen et al. 2019b) or random walk (Brendel et al.) 2017). In Figure [(b) we plot the deci- sion surface of a GBDT. We observe similar issue that there are many local minima in the GBDT decision boundary.
Herr local minimum indicates point on the decision boundary that has shortest distance to the original example, compared to other nearby points on the decision boundary. Those local minimums are the points where a decision-based attack can converge to.
3

---

Under review as a conference paper at ICLR 2020
(a) Boundary on NN.
(b) Boundary GBDT.
Figure Decision boundary (NN and GBDT models on MNIST dataset) projected on two- dimensional hyperplane. To choose which 2D hyperplane project to, decision-based attack from two random initialization points, and use their converged perturbation directions as vector to form the hyperplane. We then query the decision boundary on this hyperplane to plot these figures.
We further quantify how serious the problem is. On an MNIST network, Figure 2(a) shows the distribution of converged adversarial perturbations of C&W attack (white-box attack) and Sign- OPT attack (decision-based attack) under approximately 400 random initial points. We observe that the converged solutions of C&W attack are quite concentrated between [1.41, 1.47]. However, when considering decision-basee attack such as Sign-OPT, the converged solutions are widely spread from 1.36 to 1.55. In general, our experiments suggested that decision based attacks are much more sensitive to initialization. This is because they only update solutions on the decision boundary while C& and PGD attack can update solution inside/outside the boundary.
Furthermore, such phenomenon is obvious when the victim model is GBDT. For example, in Fig- ure 2 we can see converged solution spread from 0.5 to 1.5 when applying Sign-OPT attack. GBDT cannot really reflect the minimum
Therefore, the solution of any single of Sign-OPT adversarial perturbation of the given model, and thus crucial to design an algorithm that con- verges better solution. Since the phenomenon is more severe for decision based attacks, will mainly focus on improving the quality of decision based attacks in this paper, while general our method also be used to boost the performance of white-box attacks marginally, as illustrated in Appendix
100
2.0
samples
100
CAN NINSNT
Namber sampless
80
80
Distortion
1.6
40-
20
1.4
1.35
1.40
1.45
1.50
1.55
0.50
0.75
1.00
1.25
1.50
14000
20000
Distortion
Distortion
Query Count
(a) Sign-OPT/ C&W on DNN.
(b) Sign-OPT attack on GBDT.
(c) Distortion VS Queries curves.
Figure 2: Distribution of converged adversarial perturbation norm on an MNIST image. The figures show that the final L2 distortion can be very different because of various starting directions. Figure 2(a)and ((b) the histogram for final perturbations, and Figure shows the converging curve of Sign-OPT attack on a neural network model on MNIST dataset.
3.1 GENERAL MECHANISM FOR IMPROVED DECISION BASED ATTACK
Given local update based attack A, our goal is to find solution with improved quality. To this end, we propose meta algorithm to address this issue by integrating probability- (Bayesian) black- box optimization with iterative local updates. As shown in Algorithm [ our algorithm maintains a candidate pool P. that stores all the active configurations, where each configuration u E Pa is intermediate iterate of algorithm A. Also, assume that there is attack objective C such that C(u) measures the quality of the solution. For decision based attacks, the goal is to find the optimal direction minimize the distance to the boundary along that direction (Cheng al. 2018
4

---

Under review as a conference paper at ICLR 2020
Therefore, u is the direction of adversarial perturbation and
C(u)
min X
s.t. f Io 2
# yo
where Wo is the correct label. This can be computed by a fine-grained plus binary search procedure (see Cheng et al. (2018)), and in fact, in most of the algorithms C(u) is directly maintained during the optimization procedure [Brendel et al. 2017 Cheng et al. 2019 At each iteration, we run m iterations of A on each active configuration we conduct the following two operations to reduce the candidate pool size and to resample new configurations to explore important subspace based Bayesian optimization. We discuss each step in details as below.
IP, get the improved configurations. Then
Successive Halving (SH) cut unimportant candidate configuration. After updating each candidate by m iterations, we compute the objective function value of each candidate and dis- card the worst half of them. Iteratively reducing the candidate set into half accelerates the algo- rithm, while still maintaining accurate solution pool. This idea has been used in hyperparameter search (Jamieson Talwalkar 20T6) but has been used in adversarial attack.
Bayesian Optimization (BO) for Guided Resampling. To introduce variance in the intermediate steps and explore other important region, we propose guided resampling strategy to refine the candidate pool. The general idea is to resample from the solution space in the middle step based on the knowledge acquired before and focus on promising subareas. Specifically, we use a Bayesian optimization method called Tree Parzen Estimator (TPE) (Bergstra et al. 201 to resample new configurations.
In order to do resampling, maintain another pool P. that stores all the previous iterations per- formed including the cutted ones, since all the information will be useful for resampling. As shown in Algorithm 2 we first divide the observed data in P. into worse and better parts based the associated objective function value. We then train two separate Kernel Density Estimators (KDE) denoted as i(-) and g(-) on these two subsets.
(((u) =p(C(u) S alu, Pa). (g(u) p(C(u) > P.).
The parameter is set to 20%, which ensures the better part I(us has 20% of configurations in P. and the worse part g(u) has the remaining 80%, relatively. Later, we sample new data with the minimum value of (())/g(), which can be proved to have maximum relative improvement in Equation 4 (see more information in Appendix B). Since we can not directly find such points, we sample for few times (the number is set to 100 during the experiment) from I(-) and keep the one with the minimal ((-)/((-).
When combining our method with white-box attacks, u will be d-dimensional vector in the input space, and C(u) will be the objective defined in C&W PGD attack.
Algorithm The proposed BOSH attack framework.
Input: Model f. original example zp. attack objective C, maadient-basedd attack algorithm A, cutting interval M, cutting rate s, cutting interval increase rate m.
1: Randomly sample k initial configurations to form IP. (Gaussian or uniform random).
2: P. PIP
P... for 1, do
3:
4:
for each u, E Fa do 5: for j 1......... M do
//
perform attack on all configurations conduct M iterations before cutting
6:
u < A(u)
7:
P. P. ((14, C(u()))
Record all interval steps // Update the configuration in P.
8:
Update un in P. with u/.
9:
Delete the worst s% of configurations from P.
PA P. rPe-resampling(P. [Pa, s%)
11:
M - M. (1 + m)%. Increase the searching interval
5

---

Under review as a conference paper at ICLR 2020
Algorithm 2 Tree Parzen Estimator resampling.
Input: Observed datas F,, resample times T;
1: Initialize P/ as an empty list;
2: Divide IP, into two subset L (better) and H. (worse) based on objective function C;
3: Build two separate KDEs on and H. denoted as I(-) and h(() respectively;
4: Use Grid Search to find the best KDE bandwidth bi. by for (()) and h(-);
5: for each t E (0, T do
6: initialization: k = O, min_score oo;
7: while & < max sample times do
8: Sample ur from I(-);
9:
if min_score > g(uu)/((uu)))) then;
ur - uuki
11:
min score g( g(uex)/((uxt))
k+ k+1
13:
P1 Pi U ((u,,,((,)))
return P/;;
The reason we use TPE for resampling is that the computational cost grows linearly with the number of data points in P.. In comparison, traditional Bayesian optimization method like Gaussian Process (GP) will require cubic-time to generate new points. Therefore, TPE is more suitable for high dimensional problems.
In the experiments we find that the final best configuration mostly comes from resampling, instead of the set of starting configurations. This proves the effectiveness of resampling during search, the quantitative results will be shown in Section 4.2
4 EXPERIMENTS
We conduct experiments on various models and datasets to verify the efficiency and effectiveness of the proposed approach. We try to enhance the performance of decision-bart attack image clas- sification tasks like MNIST, CIFAR- 10 and ImageNet, and also conduct experiments on tree model like GBDT and detection model like LID. Furthermore, demonstrate that meta-algorithm is also able to improve existing white-box attacks.
4.1 DECISION- BASEDD ATTACK ON NEURAL NETWORKS
We conduct experiments three standard datasets: MNIST LeCun et al. 1998). CIFAR-10
(Krihevsky al., 2010) and ImageNet- 1000 (Deng al. 2009). ). The neural network model ar- chitecture is the same with the ones reported in Cheng et al. (2018: for both MNIST and CIFAR we use the network with four convolution layers, two max- soux-pooling layers and two fully-connected layers, which achieve 99.5% accuracy on MNIST and 82.5% accuracy on CIFAR-10 as reported in (Carlini & Wagner 2017b Cheng et al. 2018). For ImageNet, we use the pretrained Resnet-50 (He al. (016) network provided by torchvision (Mareel & Rodriguez] 2010), which achieves Top-1 accuracy of 76.15% 15%. We randomly select 100 examples from test sets for evaluation. The parameters of the proposed algorithms can be found in Table 6 Appendix D
Improved solution quality of existing methods We compare the solution quality of the proposed algorithm with three existing decision-based attack methods: Boundary attack (Brendel et al. 2017). OPT-attack (Cheng et al. 2018) and Sign-OPT attack (Cheng et al. 2019) on MNIST, CIFAR- TO and ImageNet data sets. For our algorithm, we use Sign-OPT attack as the base algorithm and set A = 30 for the initial candidate pool. The average L2 perturbation of our method and baselines are presented in Table g Note that the decision based attacks maintain intermediate iterates on the decision boundary,
they always output successful attack. The main comparison is the average Le perturbation to alter the predictions. We also follow Cheng et al. (2018) to report Attack Success is chosen based
Rate (ASR) by calculating ratio of adversarial examples with perturbation

---

Under review as a conference paper at ICLR 2020
different tasks). The results show that help decision-basee attacks achieve lower Lę perturbation and higher attack success rate. The detailed analysis shown in the next section.
The proposed algorithm also be used to boost the performance of other decision based attacks. Table 7 in the Appendix demonstrates that the proposed algorithm consistently improves the L perturbation and success rate of Boundary attack and OPT-attack.
Table 1: Results of hard-label black-box attack on MNIST, CIFAR-10 and ImageNet-1000. We
compare the performance of several attack algorithms under untargeted setting.
MNIST
CIFAR-10
ImageNet-1000
Avg L2
ASR
Avg La
ASR (E 0.13)
Avg. La
ASR
< 1.0)
< 1.4)
C&W (White-box)
0.96
60%
0.12
61%
1.53
49%
Boundary attack
1.13
41%
0.15
48%
2.02
19%
OPT-based attack
1.09
46%
0.14
50%
1.67
38%
Sign-OPT attack
1.07
49%
0.14
51%
1.43
59%
BOSH Sign-OPT attack
0.91
67%
0.10
65%
1.18
81%
4.2 ANALYSIS
We then conduct a study to test each component of our algorithm and compare with the baselines. The experiment is done on MNIST data using Sign-OPT attack the base attack method. The results are summarized in Table
Table 2: Comparions for the effectiveness of successive halving and TPE resampling. The Relative Gain based on Multi-iirectioall attack and Queries means total queries of directions.
Starting Directions
ASR
Avg L2
Ratio
Queries
Ratio
(e < 1.0)
1
1.07
0%
49%
25,456
1x
30
0.98
8.4%
57%
771,283
30x
Multi-initial Sign-OPT
50
0.94
12.1%
63%
1,268,392
50x
100
0.91
15.0%
65%
2,567,382
100x
Successive Halving Sign-OPT
30
0.99
7.5%
55%
161,183
6.3x
30
0.91
15.0 %
67 %
252,014
9.9x
BOSH Sign-OPT
50
0.88
17.8%
71 %
409,841
16.1x
100
0.87
18.7% %
71 %
829,865
32.6x
Comparison with naive mulitple initialization approach. A naive way improve the solution quality of existing attack is to run the attack on multiple random initialization points. This strategy has been used in white-box attack and is also applicable the decision based attacks. We compare Sign-OPT with 30, 50, 100 initial points and the proposed BOSH boosted Sign-OPT approach in Table[2] The results demonstrate that successive halving requires much less queries than naively run- ning multiple initial configurations. Due to resampling, the proposed approach converges to better solution under same initial pool size. For example, to achieve average 0.91 L2 perturbation, BOSH boosted Sign-OPT requires 10 times less queries than multi-initial Sign-OPT.
Size of the initial pool. The size of initial pool (denoted by le in our algorithm) is an important parameter. Table shows that increasing h only has marginal effect after k ss 30. When introduc- ing cutting and resampling mechanism into the Sign-OPT attack, the final best perturbation less sensitive to the number of starting directions, which means that resampling tend to make the search less dependent on the starting directions. Detailed discussion is in Appendix
the Icaderboard http:////ggghhi...cc///a//////// hs
st st__cal 1enge

---

Under review as a conference paper at ICLR 2020
Effect of successive halving and TPE resampling. We study the effect of these two components separately. As shown in Figure ((a) the approach of successive halving keeps throwing away the worse s percent of configurations until converge during specific interval until there is only one sample left. When combining this with resampling, as in Figure (3b) our algorithm finds directions that are better than original ones. We observed emperically that the final best direction often comes from resampling instead of the original starting directions. This observation demonstrates the impor- lance of resampling the intermediate steps. Furthermore, Table2]shon shows that combining Sign-OPT with successive halving (second column) has worse solutions compared with BOSH Sign-OPT. This indicates that resampling important for getting better solution.
2.2
2.4
2.2
La Distortion
L Distortion
1.8
2.0
1.8-
1.6
1.6-
1.4
1.4
10000
20000
30000
2000
4000
6000
8000
10000
Query Count
Query Count
(a) Successive Halving.
(b) Successive Halving and TPE resampling.
Figure 3: Illustration of the effect of Successive Halving and TPE resampling. Note that Figure 3(b)
only exhibits part of the curve to show the effect of TPE.
What is the best cutting interval? The parameter M decides how many iterations are applied using base attacker before the next cutting/resampingg stage. This is an important parameter to be tuned. If M is too small, some solution paths will be wrongly throwing away; while if M is too large, the whole procedure requires a large number of queries. In our experiment, we use subset of images tune this parameter and find that the images in the same dataset often share similar best cutting interval. This reduces lots of unnecessary computations. The parameters for different datasets are shown Appendix D
4.3 DECISION-BASED ATTACK ON OTHER MODELS
We conduct untargeted attack on gradient boosting decision tree (GBDT). Since Sign-OPT does not include the experiment with GBDT, we use the OPT-based attack (Cheng et al., 2018)) and apply our meta algorithm on top of it. We consider two datasets, MNIST and HIGGS, and use the same models provided by (Cheng et al. 2018
We compare the average T.2 perturbation and the attack success rate in Table 3 The results show that the proposed method significantly boosts the performance OPT attack. The overall improvement more significant than attacking neural networks. This is mainly because that the decision boundary of GBDT contains more local minima than neural networks, as plotted in Figure]
Table 3:
Comparison of results of untargeted at- Table 4: Results of attack on MNIST detector models under untargeted setting.
tack on gradient boosting decision tree.
HIGGS
MNIST
Avg La
ASR (c < 1.5)
Lig
ASR
Avg f
ASR (c < 0.8)
(c < 0.15)
CW HC attack
20.25%
OPT-based attack
0.169
52%
0.952
49%
Sign-OPT attack
1.24 1.18
52.63%
TPE-SH attack
0.103
81%
0.722
79%
BOSH attack
71.42%
4 'The MNIST model is downloaded from LightGBM and use the parameters in com/ Koz ev/MNIST. Www.iSTHoooting which achieves 98.09% accuracy. For HIGGS, we can achieve 0.8457 accuracy relatively.
8

---

Under review as a conference paper at ICLR 2020
4.3.1 DECISION -BSSE ATTACK ON DETECTION MODELS
To improve the performance of neural networks, line of research, such KD+BU (Feinman al. 2017). LID (Ma et al., 2018), Mahalanobis (Lee et al. 2018) and ML-LOO (Yang et al.) 2019), has been focusing on screening out adversarial examples in the test stage without touching the training of the original model. Besides comprehensive evaluation of our attack on various classification models with a variety of data sets, we carry out experimental analysis of our untargeted attack on one state-of-the-ard detection model LID (Ma et al.) 2018) on MNIST data set. To train a detection model on MNIST, we first train a simple classification network composed of two convolutional layers followed by a hidden dense layer with 1024 units. Then we apply C&W attack to this model to generate adversarial examples from the original test samples. Finally we train LID detectors with have generated with the standard train/test
the original test samples and adversarial examples split. The state-of of-te-of-the-art detection model LID achieves 0.99 test accuracy.
C&W high confidence attack (Carlini & Wagner 2017a) has been shown to have great performance in attacking various detection models. So we compare the average I.2 perturbation and attack success rate of three attacking methods C& W high confidence attack, Sign-OPT attack and BOSH Sign-OPT attack in Table 4 At each query, we define the attack to be successful if it fools both the detector model and the original model. The results show that the proposed method can significantly boost the performance of the Sign-OPT attack and it achieves much better performance than C&W W high confidence attack.
CONCLUSION
In this paper, we propose a meta algorithm boost the performance of existing decision based tacks. In particular, instead of traversing single solution path when searching for an adversarial example, we maintain a pool of solution paths to explore important regions. We show empirically that the proposed algorithm consistently improves the solution quality of many existing decision based attacks, and can obtain adversarial examples with improved quality on not only neural net- works, but also other decision based models, such as GBDT and detection-basse models.
REFERENCES
Moustafa Alzantot, Yash Sharma, Supriyo Chakraborty, and Mani Srivastava. Genattack: Practical black-box attacks with gradient-free optimization. arXiv preprint arXiv: 1090, 2018.
James S Bergstra, Rémi Bardenet, Yoshua Bengio, and Balázs Kégl. Algorithms for hyper- hyper- parameter optimization. In Advances neural information processing systems, pp. 2546 2554,, 2011.
Wieland Brendel, Jonas Rauber, and Matthias Bethge. Decision- based adversarial attacks: Reliable attacks against black-box machine learning models. arXiv preprint arXiv:1712.042453 2017
Nicholas Carlini and David Wagner. Adversarial examples
easily detected: Bypassing ten detection methods. In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, pp. 3-14. ACM, 2017a.
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In 2017 IEEE Symposium Security and Privacy (SP), pp. 39-57. IEEE, 2017b.
Hongge Chen, Huan Zhang. Pin-Yo Yu Chen, Jinfeng Yi, and Cho-Jui Hsich. Attacking visual language grounding with adversarial examples: A case study on neural image captioning. arXiv preprint arXiv:1712.0205// 2017a.
Hongge Chen, Huan Zhang. Duane Boning, and Cho-Jui Hsieh. Robust decision trees against ad- versarial examples. In International Conference on Machine Learning, pp. 1122-1131, 2019a.
Jianbo Chen, Michael Jordan, and Martin J. Wainwright. Hopskipjumpattack: A query-efficient decision-bas based attack. arXiv preprint arXiv:1904.0m 02144,,02444,.. 2019b.
Pin- Yu Chen, Huan Zhang, Yash Sharma. Jinfeng Yi, and Cho-Jui Hsieh. Zoo: Zeroth order opti- mization based block-box attacks to deep neural networks without training substitute models. In

---

Under review as a conference paper at ICLR 2020
Proceedings of the 10th ACM Workshop Artificial Intelligence and Security, pp. 15-26. ACM, 2017b.
Pin-Yu Chen, Yash Sharma, Huan Zhang, Jinfeng Yi, and Cho-Jui Hsich. Ead: elastic-net attacks to deep neural networks via adversarial examples. In seirty-second AAAI conference on artificial intelligence, 2018.
Minhao Cheng, Thong Le, Pin-Yu Chen, Jinfeng Yi, Huan Zhang, and Cho-Jui Hsich. Query-
efficient hard-label black-box attack: An optimization-bo based approach. arXiv preprint SE5Ivv8807.044555 2018.
Minhao Cheng, Simranjit Singh, Patrick Chen, Pin-Yu Chen, Sijia Liu, and Cho-Jui Hsich. Sign-opt: A query efficient hard-label adversarial attack. arXiv preprint arXiv: 2019.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large- scale hi- erarchical image database. In 2009 JEEE conference on computer vision and pattern recognition, pp.
leee, 2009.
Stefan Falkner, Aaron Klein, and Frank Hutter. Bohb: Robust and efficient hyperparameter opti- mization at scale. arXiv preprint arXiv: 1807.01777 2018.
Reuben Feinman, Ryan R. Curtin, Saurabh Shintre, and Andrew B. Gardner. Detecting adversarial samples from artifacts. arXiv preprint arXiv:1703.004100 2017.
Thomas A Feo and Mauricio GC Resende. Greedy randomized adaptive search procedures. Journal of global optimization, 6(2):109-133, 1995.
Fred Glover and Manuel Laguna. Tabu search. handbook of combinatorial optimization. Kluwer Academic Publishers, 3:621 1999.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy, Explaining and harnessing adversarial examples. arXiv preprint arXiv:1412.6572, 2014.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.
Andrew Ilyas, Logan Engstrom, Anish Athalye, and Jessy Lin. Black-box adversarial attacks with limited queries and information. arXiv preprint arXiv:1804.08540 201 20.8a.
Andrew Ilyas, Logan Engstrom, and Aleksander Madry. Prior convictions: Black-box adversarial attacks with bandits and priors. arXiv preprint vrXiv:1807.07975 2018b.
Kevin Jamieson and Ameet Talwalkar. Non-stochastic best arm identification and hyperparameter optimization. In Artificial Intelligence and Statistics, pp. 240-248, 2016.
Alex Kantchelian, J Doug Tygar, and Anthony Joseph. Evasion and hardening of tree ensemble classifiers. In International Conference on Machine Learning, pp. 2387-2396. 2016.
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cifar-10 (canadian institute for advanced search). URL http://www. cs. toronto. edu/kriz/cifar. himl, 8, 2010.
Alexey Kurakin, Ian Goodfellow, and Samy Bengio. Adversarial machine learning at scale. arXiv preprint 1ii:::611..02.000 2016.
Yann LeCun, Léon Bottou, Yoshua Bengio, Patrick Haffner, et al. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 86(11):2278-233) 1998.
K. Lee, K. Lee, H. Lee, and J. Shin. A simple unified framework for detecting -istrrriibttinn samples and adversarial attacks. In NeurlPS, pp. 7167-7177, 2018.
Lisha Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadeh, and Ameet Talwalkar. Hy- perband: A novel bandit-based approach to hyperparameter optimization. arXiv preprint arXiv: 1600306560 2016.
10

---

Under review as a conference paper at ICLR 2020
Xingjun Ma, Bo Li, Yisen Wang, Sarah M. Erfani, Sudanthi Wijewickrema, Grant Schoenebeck, Dawn Song, Michael E. Houle, and James Bailey. Characterizing adversarial subspaces using local intrinsic dimensionality. In ICLR, 2018.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks, arXiv preprint arXiv:1706 770606000.. 2017.
Sébastien Marcel and Yann Rodriguez. Torchvision the machine-vision package of torch. In Pro- ceedings of the 18th ACM international conference on Multimedia, pp. 1485-1488. ACM, 2010.
Seyed-Mohsen Moosavi-Dezfooli: Alhussein Fawzi, and Pascal Frossard. Deepfool: simple and accurate method to fool deep neural networks. In Proceedings of the IEEE conference on com- 2016.
puter vision and pattern recognition, pp.
Riccardo Moriconi, Mare Peter Deisenroth, and K. S. Sesh Kumar. High-dimensional bayesian optimization using low-dimensional feature spaces. 2019.
Martin Pelikan, David E Goldberg, and Erick Cantú-Paz. Boa: The bayesian optimization algorithm. In Proceedings of the Ist Annual Conference on Genetic and Evolutionary Computation Volume 1, pp. 525-525555 Morgan Kaufmaann Publishers Inc., 1999.
Jasper Snoek, Hugo Larochelle, and Ryan P Adams. Practical bayesian optimization of machine learning algorithms. In Advances in neural information processing systems, pp. 2951-2959, 2012.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv:1312.6799 2013.
Chun-Chen Tu, Paishun Ting, Pin-Yu Yu Chen, Sijia Liu, Huan Zhang, Jinfeng Yi, Cho-Jui Hsieh, and Shin-Ming Cheng. Autozoom: Autoencoder-basee zeroth order optimization method for attack- ing black-box neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 742-749 2019.
Ziyu Wang, Masrour Zoghi, Frank Hutter, David Matheson, and Nando De Freitas. Bayesian opti- mization in high dimensions via random embeddings. In Twenty-Third International Joint Con- ference on Artificial Intelligence, 2013.
Puyudi Yang, Jianbo Chen, Cho-Jui Hsieh, Jane-Ling Wang, and Michael Jordan. MI-loo: Detect- ing adversarial examples with feature attribution. arXiv preprint 1906.0:900.03444 2019.

---

Under review as a conference paper at ICLR 2020
A BOOSTING WHITE-BOX ATTACK
Zooming of local boundary
Resample
Cutted
Start Point
Region of label
Attack success region
Figure 4: Illustration possible boundary distribution and attack steps on it. Starting from differ- ent directions, we conduct cutting and resampling during the middle steps. The directions that are not promising are eut to save computational cost, and the directions that reach lower error value will be expanded to encourage exploring. This figure also shows that the boundary can be very unsmooth and contains lots of local optimal points on the surface.
Figure shows a possible boundary distribution and C&W (Carlini Wagner 2017b) attack per- formed it. The decision boundary of neural network can be very unsmooth and contains lots of local optimal points. Generally speaking, the cost from the original point toward the bound- ary(which means successful attack) highly depends the directions. Traditional white-box attack algorithms like FSGM (Goodfellow et al. 2014). PGD (Kurakin et al. 2016) and C&W (Carlini & Wagner 2017b) use walk through gradient reach the boundary, implying that gradient can guide to the optimal value, which may not be the case. We try to improve C&W W attack to find global local optimal adversarial example by encouraging that the original sample is (x, y) and L is the logit output of the neural network's 's loss function, C& attack conducts iterative search as following:
search not just depends the gradient. Assume
arg min A where
|| + f(x + Ax) s.t. x + Ao E [0,
f(x) = max(0, max(L(x))) L(x)))
t4y
Instead of starting from single direction which is calculated by gradient on the original point, we randomly sample points within an ball (which means the the Loe distance between the generated point and the original one is less than c, this value may be slightly different depends as a set of possible configurations. We then run the BOSH algorithm with successive halving and resampling to iteratively refine these configurations and run steps of C& W attacks. We use the loss function in the above objective for TPE resampling.
datasets)
A.1 RESULTS
Although we focus on decision based attack throughout the paper, the proposed method can actually also boost the performance of white-box attacks. We use C&W attack (Carlini & Wagner] (017b) as the base method and perform experiments on MNIST and CIFAR-10 datasets. In order to introduce variance and encourage the model to find better and global optimal values, we randomly sample 50 points inside the L2 ball (we use 0.3 during the experiment) as the starting points, and apply C&W attack on each of them. For simplicity, we fix described in 3 to be 0.2. The results before and after applying our algorithm are shown in Table 5 We can observe that although our algorithm also improve C&W attack, the improvements are not significant attacks. This is probably because C& W attack is less sensitive to the initial point, as demonstrated in Figure 2(a)
that in decision based
12

---

Under review as a conference paper at ICLR 2020
Table 5: Comparison of results of untargeted attack on white-box attack.
MNIST
CIFAR-10
Avg L2
ASR
1.0)
Avg L.2
ASR (c 01.3)
C&W attack
0.96
60%
0.12
61% 66%
BOSH attack
0.91
67%
0.10
B BAYESIAN OPTIMIZATION AND SUCCESSIVE HALVING
B. BAYESIAN OPTIMIZATION (BO)
Bayesian Optimization (BO) has been successfully applied optimize a function which is non- differentiable or black-box like finding the hyper-parameter of neural networks in AutoML area. mainly adopts the idea to sample new points based on the past knowledge. Basically, Bayesian optimization finds the optimal value of given function f X + IR in iterative manner: at each iteration i, BO uses a probabilistic model PDf to estimate and approach the unknown function based on the data points that are already observed by the last iterations. Specifically, it samples new data points 2; argmaxx u (x) 11: where u is the acquisition function and D1 = yt-1)} the t - 1 samples queried from f so far. The most widely used acquisition functions is the expected improvement (El):
{(x1, y1),... ..... (x
EI(x)) Ex-p max(f(x) f(x ),0))
(4)
Where f(x+) is the value of the best sample generated far and x the location of that sample, ie. x = arg max ED f (xx))
B.2 THE TREE PARZEN ESTIMATOR (TPE).
The Tree Parzen Estimator (TPE). TPE [Bergstra et al. 2011) is Bayesian optimization method proposed to solve the hyper-parameter tuning problems that uses a kernel density estimator (KDE) to approximate the distribution of 'D instead of trying to model the objective function f directly. Specifically, it models the p(rly) and p(y) instead of p(ylæ)), and define p(rly) using separate KDE I(x) and g(r):
((xx) (x)
V S y > a
p(x/))
where a a constant between the lowest and largest value of y D. Bergstra al. (2011) shows that maximizing the radio (())/g( is equivalent to optimizing the El function described in Equation (see Theorem for more detail). In such setting, the computational cost of generating new data
4
point by KDE grows linearly with the number of data points already generated, while traditional Gaussian Process (GP) will require cubic-time.
Theorem 1 In Equation 5 maximizing the radio ((x)/g(z) is equal to optimizing the Expected Improvement (El) Equation
Proof:
The Expected Improvement can also be written as:
= 1" (w--y)p(ur -y-yy(yyl)ddy- 1r (a (a-y))(o1) p(xl)))(()) dy (6) p(x)
f((x)), [x()) Expp -((=
Assume that 7 = p(y < ax), then:
p(x)= [ p(elv)oluddy >((x) -))(()))
Therefore,
(a v)p(<lu))()) = 1(x) 1 (a ya-y)ply)dy= yal(x) - -((x) 1 p(y)dy (8)
13

---

Under review as a conference paper at ICLR 2020
So finally,
(l((s) yal(x) - 1(x) J- p(y)dy
x (r + g(x)
(1 7))
71(x) + - 7)gx))
((x)
Which means maximizing ((x) is equivalent to maximize the EI function.
B.3 SUCCESSIVE HALVING.
Successive Halving. The idea behind Successive Halving (Jamieson & Talwalkar 2016) can be easily illustrated by it's name: first initialize set of configurations and perform some calculations on them, then evaluate the performance of all configurations and discard the worst half od these configurations, this process continues until there is only one configuration left. BOHB (Falkner jet al., 2018) combines HyperBand (derived from Successive Halving) (Li et al. 2016) and TPE to solve the AutoMI. problem and achieve greate success.
However, these methods are originally applied to the hyper- ppper-parameter tuning problem where the parameters need to be searched are not too much(approximately 10-20), it will suffer from "dimen- sional curse" when the number parameters grows larger and the computation cost needed will be unacceptable. There already some work (Moriconi et al. 2019 Wang et al. 2013) try to use BO in high dimension, while we still found in experiment that simply use BO can not converge as good gradient-bar based methods.
C DISCUSSION ABOUT THE NUMBER OF STARTING DIRECTIONS
1.46
1.46
Final distortion
1,44
Mean
Final L2 distortion
Mean
1.43
Standard deviation
Standard deviation
1.42
1.40
1.40
1.37
1.38
1.34
1.36
50
100
150
200
50
100
150
200
Number starting directions (b) Successive Halving and TPE resampling. Figure 5: Number of starting directions vs Final L2 distortion. Since we will run multiple times on each setup to reduce variance, the red line shows the average distortion and the blue area shows the standard deviation.
Number starting directions (a) Successive Halving.
We discuss the problem that how many starting points are enough for a successful attack. In order to find the best number of starting points, we conduct attack starting directions. for specific number of starting directions, we also run several times and average the result reduce variance. Figure 5 shows the attack on MNIST image using Sign-OPT method, we can see the effect that the number of starting direction have on the final converging perturbation. Also, We can find that the standard deviation smaller and the final perturbation is lower when resampling by TPE is introduced. This is probably because TPE resampling also introduce variance the middle step and making the algorithm not completely depends on the starting directions, this will also helps increase the probability to find a better optimal value.
image with different number of
14

---

Under review as a conference paper at ICLR 2020
D PARAMETERS OR DIFFERENT DATASETS
Table 6: Parameters for Sign-OPT attack on different image classification datasets.
Maximum Queries
Cutting and
Interval Increase
Dataset
Per Direction
Resampling Interval
Ratio
MNIST
40000
3500
1.4
CIFAR-I0
20000
2000
1.3
ImageNet
200000
6000
1.6
E BOOSTING DECISION- DESSED ATTACK ALGORITHMS
To demonstrate that our algorithm can consistently boost existing hard-label attack algorithms, we try to enhance the performance of three decision- algorithms described in Section 4.1 All the parameters are equal to Section 4.1 and we use 30 starting directions for our boosting algorithm. The results are shown Table
Table 7: Results of hard-label black-box attack on MNIST, CIFAR-10 10 and ImageNet-1000. We
compare the performance several attack algorithms under untargeted setting.
MNIST
C-FAR-10
Avg L2
ASR
Queries
Avg L2
ASR
Queries
(c < 1.0)
(c < 0.13)
Boundary attack
1.13
41%
157,323
0.15
48%
212,093
BOSH Boundary attack
0.99
53%
1,673,837
0.12
55%
2,239,488
OPT-based attack
1.09
46%
91,834
0.14
50%
142,498
BOSH OPT-based attack
0.95
62%
983,283
0.11
62%
1,527,384
Oign-OPT attack
1.05
51%
25,456
0.14
51%
15,285
BOSH Sign-OPT attack
0.91
67%
252,014
0.10
65%
142,738
F RUN-TIME COMPARISON
We evaluate the efficiency of various algorithms based on the number of queries, commonly used in the papers of this area. In this section we also include the run-time performance comparison of these methods. We use one Nvidia GTX 1080 conduct the experiments, but the run-time will reduce if we use multiple GPUs since our boosting algorithm can be easily parallelize (searches with different directions do not depend on each other).
Table 8: Results of hard-label black-box attack MNIST and CIFAR-10. We compare the perfor-
mance based on run-time.
MNIST
CIFAR-10
Avg L2 Run-time
Run-time
Avg Lz
Run-time
Avg. La2
Boundary attack OPT-based attack
1.13
326.12s
0.15
524.92s
1.09
205.27s
0.14
351.59g
Sign-OPT attack
1.05
56.24s
0.14
37.13s
BOSH Sign-OPT attack
0.91
671.32s
0.10
462.19s
15

---

Under review as a conference paper at ICLR 2020
G ATTACK SUCCESS RATE UNDER DIFFERENT PERTURBATION E
In this section, we show the results of Sign-OPT and Boosted Sign-OPT attack on MNIST and CIFAR-I0 dataset. We mainly show how Attack Success Rate (ASR) changes based on different perturbations.
ASR
0.6
ASR
0.4
0.4
0.2
Sign-OPT
0.2
Sign-OFT
BOSH Sign-OPT
BOSH Sign-OPT
0.0
0.0
0.5
1.0
1.5
2.0
2,5
0.2
0.3
(a) MNIST dataset.
(b) CIFAR-10 dataset.
Figure 6: Perturbation 6 vs Attack Success Rate (ASR).
H TIME COMPLEXITY ANALYSIS
We briefly analyse the number of queries our algorithm need regarding the parameters we mentioned in Algorithm T Generally speaking, in first several cutting intervals (we consistently
3 in the experiments), our boosting algorithm requires about k times more queries than single search. This because we resample new configurations while cutting unpromising one. After this, we only cut and do not resample, and run until there is only one configuration left and it converges.
As discussed in Algorithm I assume that the cutting interval M, cutting rate is s, cutting interval increase rate is m and initial number of starting configurations is k.
In the cutting and resampling phase, since we only resample times, we need:
k (M M(1 + m) + M(1 + m)² queries. After that, only the unpromising configurations, we need:
(10)
k M(1 m) (1 + 3% + 2% +..)
(11)
queries.
We can see that the main differences between the original and our algorithm is the initial number of staring configurations k and we also discuss how & influences the results in Section 4.2 and Appendix B
16


Reviews:
[{"review_id": "rkxncuZQYH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors study the adversarial example generation problem, in the difficult case where the attacked model is a black box. Since the model is unknown, the approaches based on the minimization of a loss function with a gradient based optimizer do not apply. The current alternatives, known as decision-based attack, use iterative local updates from a starting point to a local minimum, where the class of the adversarial example is different from the initial example while its distance stays close to the initial one.\n\nFor handling the sensibility to starting points, the authors propose a meta-algorithm, which uses any iterative local update based attacks, and which maintains a set of solutions corresponding to different starting points. The proposed algorithm uses successive halving for iteratively maintaining empirical good solutions by discarding the worst half of solutions at each step, and uses Tree Parzen Estimator to explore by resampling promising area.\n\nIn the experiments, the meta-algorithm uses SignOPT attack. It is compared with three decision based attacks, including SignOPT. Three image datasets are used. The attacked models are neural networks and gradient boosting tree in the last experiment.\n\nPros:\n- The paper is well-written and easy to follow.\n- Generic algorithm.\n\n\nCons:\n- No analysis is provided.  \n- The proposed algorithm has a lot of parameters: $k, M, s, m, T, inf, \\alpha$. \n- The $\\epsilon$ are not the same for each attacked model (table 1 and 3). Is it the result of a post-optimization? Could you plot the curves ASR versus $\\epsilon$ ?\n- In algorithm 2, $min_score=inf$,  whatever $t$, so why using two variables ?\n\n___________________________________________________________________________________________________________________________________\nI read the rebuttal.\nThanks you for answering my concerns.\n\nI think that it is possible to provide some theoretical guanrantees. For instance, may be one could show that the quality of the attacks is increasing when Algorithm 1 is run. Finding the highest increasing rate could be useful for tuning the parameters of the algorithm.\nHowever, I understand that this could be tricky.\n\nI took a look to Figure 6. Good point: BOSH Sign-OPT attack outperforms Sign-OPT attack whatever $\\epsilon$.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "HylNib0yqB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a meta-algorithm for the so-called \"decision-based attack\" problem, where a model that can be accessed only via label queries for a given input is attacked by a minimal perturbation to the input that changes the predicted label. The algorithm, BOSH, augments any iterative algorithm for this problem with a diversification strategy based on bayesian optimization and throwing away bad solutions. Empirically, it is shown that BOSH can improve the performance of recently developed algorithms for this problem, by exploring more solutions and refining them intelligently.\n\nOverall, the decision-based attack problem is very practically relevant as it assumes minimal access to the classifier. I also really like that the authors looked into tree-based models in addition to neural networks. The algorithmic ideas that are proposed are simple and effective, as supported by the experimental results.\n\nHowever, I have some serious comments about the experimental evaluation that I believe can substantially improve the quality of the paper, if addressed. Whether I raise my score or not will depend on how well the authors address these questions. I also have concerns about related work in heuristic algorithms.\n\nQuestions:\n- Related work: the ideas of diversifying solution paths and throwing away bad solutions are very popular in combinatorial heuristics. You should do a thorough review of work in that area and in Genetic Algorithms (GA). You could look into the following classical/survey papers as starting points, in particular the first survey's chapter 4.\n\nGlover, Fred, and Manuel Laguna. \"Tabu search.\" Handbook of combinatorial optimization. Springer, Boston, MA, 1998. 2093-2229.\nFeo, Thomas A., and Mauricio GC Resende. \"Greedy randomized adaptive search procedures.\" Journal of global optimization 6.2 (1995): 109-133.\n\n- Other Black-Box algorithms: you should compare against well-established black-box optimization algorithms such as NOMAD and RBF-OPT. Both are based on very solid mathematical foundations and have high-quality open source implementations:\nNOMAD: https://www.gerad.ca/nomad/\nrbf-opt: https://github.com/coin-or/rbfopt\n\n- Runtime comparison: your analysis with respect to number of queries is very good and insightful. In addition, we should get a sense of the runtime performance. If you run each of the approaches with the same time limit, how do they fare?\n\n- Comparing to \"optimal\" attacks: we need to know how well the solutions are compared to the best possible, or a close-enough approximation. You could run white-box attacks and compare the relative error to the quality of the white-box attack. Otherwise, it is hard to tell what gap remains to be closed algorithmically and it is difficult for other researchers to know whether it's worth trying to improve what you propose here in the future.\n\n- Time complexity: please give a time complexity analysis of BOSH as a function of all its hyperparameters.\n\nClarity:\n- Figure 1: I don't understand what this figure shows. Where are the 2 minima? Please clarify further.\n- You minimize l(.) / g(.) in Algorithm 2, but maximize it in Appendix B.2. Maximizing makes more sense. Which one is it?\n- Theorem 1: Is that your result or Bergstra et al.'s?\n\nMinor comments:\n- \"Adversarial example generation becomes a viable method for evaluating the robustness of a machine learning model.\" --> \"Adversarial example generation has become a viable method for evaluating the robustness of a machine learning model.\"\n- \"when searching an adversarial\" --> \"when searching for an adversarial\"\n- \"Distortion\" is used in the literature much less than \"Perturbation\"; consider switching them.\n- \"our mega algorithm\" --> \"our meta-algorithm\"\n- Please use consistent notation: SignOPT or Sign-OPT.\n- Appendix B.1: \"undifferentiable\" --> \"non-differentiable\"\n- \"are the t − x1 samples\" --> \"are the t − 1 samples\"", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes BOSH-attack, a meta-algorithm for decision-based attack, where a model that can be accessed only via label queries for a given input is attacked by a minimal perturbation to the input that changes the predicted label. BOSH improves over existing local update algorithms by leveraging Bayesian Optimization (BO) and Successive Halving (SH). It has valuable contributions. But various improvements as detailed in the review comments can be made to further strength the manuscript.
Decision: Reject