Sign-OPT: A Query-Efficient Hard-label Adversarial Attack
Authors: Minhao Cheng
Simranjit Singh
Patrick H. Chen
Pin-Yu Chen
Sijia Liu
Cho-Jui Hsieh
Venue:  (2020)

Abstract: We study the most practical problem setup for evaluating adversarial robustness of a machine learning system with limited access:  the hard-label black-box attack setting for generating adversarial examples, where limited model queries are allowed and only the decision is provided to a queried data input. Several algorithms have been proposed for this problem but they typically require huge amount (>20,000) of queries for attacking one example. Among them, one of the state-of-the-art approaches (Cheng et al., 2019) showed that hard-label attack can be modeled as an optimization problem where the objective function can be evaluated by binary search with additional model queries, thereby a zeroth order optimization algorithm can be applied. In this paper, we adopt the same optimization formulation but  propose to directly estimate the sign of gradient at any direction instead of the gradient itself, which enjoys the benefit of single query. 
Using this single query oracle for retrieving sign of directional derivative, we develop a novel query-efficient Sign-OPT approach for hard-label black-box attack. We provide a convergence analysis of the new algorithm and conduct experiments on several models on MNIST, CIFAR-10 and ImageNet. 
We find that Sign-OPT attack consistently requires 5X to 10X fewer queries when compared to the current state-of-the-art approaches, and usually converges to an adversarial example with smaller perturbation. 

Published as a conference paper at ICLR 2020
SIGN-OPT: A QUERY-EFFICIENT HARD-LABEL ADVERSARIAL ATTACK
Minhao Cheng", Simranjit Singh'; Patrick Chen', Pun-Yu Chen', Sijia Liu', Cho-Jui Hsieh' Department of Computer Science, UCLA, IBBM Research (mhcheng, simranjit, patrickchen. (pin-yu. chen, sijia. 1iu] (eiim.ce.. com
chohsieh]@cs ucla. edu
ABSTRACT
We study the most practical problem setup for evaluating adversarial robustness of a machine learning system with limited access: the hard-label black-box at- tack setting for generating adversarial examples, where limited model queries are allowed and only the decision is provided to a queried data input. Several algorithms have been proposed for this problem but they typically require huge amount (>20,000) of queries for attacking one example. Among them, one of the state-of-the-art approaches (Cheng et al., 2019) showed that hard-label attack can be modeled as optimization problem where the objective function can be evaluated by binary search with additional model queries, thereby a zeroth order op- timization algorithm can be applied. In this paper, we adopt the same optimization formulation but propose to directly estimate the sign of gradient at any direction instead of the gradient itself, which enjoys the benefit of single query. Using this single query oracle for retrieving sign of directional derivative, we develop novel query-efficient Sign-OPT approach for hard-label black-box attack. We provide a convergence analysis of the new algorithm and conduct experiments several models on MNIST, CIFAR-10 and ImageNet. We find that Sign-OP7 OPT attack consistently requires 5x to 10x fewer queries when compared to the current state-of-the-an approaches, and usually converges adversarial example with smaller perturbation.
INTRODUCTION
has been shown that neural networks are vulnerable adversarial examples (Szegedy al. 2016 Goodfellow et al., 2013) Carlini & Wagner 2017, Atthalye et al., 2018). Given a victim neural network model and correctly classified example, an adversarial attack aims to compute small perturbation such that with this perturbation added, the original example will be misclassified. Many adversarial attacks have been proposed in the literature. Most them consider the white-box setting, where the attacker has full knowledge about the victim model, and thus gradient based optimization can be used for attack. Popular Examples include C&W (Carlini & Wagner 2017) and PGD (Madry et al. 2017) attacks. On the other hand, some more recent attacks have considered the probability black- box setting where the attacker does not know the victim model's 's structure and weights, but can iteratively query the model and get the corresponding probability output. In this setting, although gradient (of output probability to the input layer) is not computable, it can still be estimated using finite differences, and algorithms many attacks are based on this (Chen et al. 2017 []yas al. 20]8a Tu et al. 2019 Jun et al., (2018).
In this paper, we consider the most challenging and practical attack setting hard-label black-box setting where the model is hidden to the attacker and the attacker can only make queries and get the corresponding hard-label decisions (c.g.. predicted labels) of the model. A commonly used algorithm proposed in this setting, also called Boundary attack (Brendel et al.) 2017). is based on random walks on the decision surface, but does not have any convergence guarantee. More recently, Cheng et al. (2019) showed that finding the minimum adversarial perturbation in the hard-label setting can be reformulated as another optimization problem (we call this Cheng's formulation in this paper). This
"Equal Contribution.

---

Published as a conference paper at ICLR 2020
new formulation enjoys the benefit of having smooth boundary in most tasks and the function value is computable using hard-label queries. Therefore, the authors of (Cheng et al.. 2019) are able to use standard zeroth order optimization to solve the new formulation. Although their algorithm converges quickly, it still requires large number of queries (e.g.. 20,000) for attacking a single image since every function evaluation of Cheng's formulation has be computed using binary search requiring tens of queries.
In this paper, we follow the same optimization formulation of (Cheng et al., 2019) which has the advantage of smoothness, but instead of using finite differences to estimate the magnitude of directional derivative, we propose evaluate its sign using only a single query. With this single-query sign oracle, we design novel algorithms for solving the Cheng's 's formulation, and we theoretically prove and empirically demonstrate the significant reduction the number of queries required for hard-label black box attack.
Our contribution are summarized below:
Novelty in terms of adversarial attack. We elucidate an efficient approach to compute the sign of directional derivative of Cheng's formulation using single query, and based on this technique we develop novel optimization algorithm called Sign-OPT for hard-label black-box attack.
Novelty in terms of optimization. Our method can be viewed new zeroth order optimization algorithm that features fast convergence of signSGD. Instead of directly taking the sign of gradient estimation, algorithm utilizes the scale of random direction. This make existing analysis inappropriate to our case, and we provide a new recipe to prove the
convergence of this new optimizer.
We conduct comprehensive experiments on several datasets and models. We show that the proposed algorithm consistently reduces the query count by 5-10 times across different models and datasets, suggesting a practical and query query-efficient robustness evaluation tool. Furthermore, on most datasets our algorithm can find an adversarial example with smaller distortion compared with previous approaches.
RELATED WORK
White-box attack Since it was firstly found that neural networks are easy to be fooled by adversarial
examples (Goodfellow al. 2015). lot of work has been proposed in the white-box attack setting, where the classifier f is completely exposed to the attacker. For neural networks, under this
assumption, pack-propagation can be conducted on the target model because both network structure and weights are known by the attacker. Algorithms including (Goodfellow et al. 2015 Kurakin jet al. 2016 Carlini& & Wagner 2017: Chen al., 2018 Madry et al.][ are then proposed based on gradient computation. Recently, the BPDA attack introduced by Athalyy et al. (2018) bypasses some models with obfuscated gradients and is shown to successfully circumvent many defenses. In addition to typical attacks based on small ep norm perturbation, non-lp norm perturbations such as scaling or shifting have also been considered (Zhang et al. 2019).
Black-box attack Recently, black-box box setting is drawing rapidly increasing attention. In black-box setting, the attacker can query the model but has no (direct) access any internal information inside the model. Although there are some works based on transfer attack (Papernot et al., 2017). consider the query-based attack in the paper. Depending on the model's feedback for given query, an attack can be classified as a soft-label or hard-label attack. In the soft-label setting, the model outputs a probability score for each decision. Chen al. (017)) uses finite difference in coordinate-wisc manner to approximately estimate the output probability changes and does a coordinate descent to conduct the attack. [[lyas et al. 8a) uses Neural evolution strategy (NES) to approximately estimate the gradient directly. Later, some variants (Ilyas et al. 2018b) Tu et al. 2019) were proposed to utilize the side information to further speed up the attack procedure. Alzantot et al. (2019) uses evolutionary algorithm as a black-box optimizer for the soft-label setting. Recently, Al-Dujaili & O O'Reilly (019)) proposes SignHunter algorithm based on signSGD (Bernstein et al. 2018) to achieve faster convergence in the soft-label setting. The recent work (Al-Dujaili & O'Reilly
2019 proposes SignHunter algorithm to achieve a more query-efficent sign estimate when crafting black-box adversarial examples through soft-label information.
2

---

Published as a conference paper at ICLR 2020
In the hard-label case, only the final decision, i.e. the top-1 predicted class, is observed. As result, the attacker can only make queries to acquire the corresponding hard-label decision instead of the probability outputs. [Brendel et al. (2017) first studied this problem and proposed algorithm based on random walks near the decision boundary. By selecting a random direction and projecting onto boundary sphere in each iteration, it aims generate high-quality adversarial example. Query-Limited attack (Ilyas et al.) 2018a) tries to estimate the output probability scores with model query and turn the hard-label into soft-label problem. [Ceng et al. (2019) instead re-formalizes the hard-label attack into an optimization problem that finds a direction which could produce the shortest distance to decision boundary.
The recent arviv paper (Chen et al. 2019) applied the zeroth-order sign oracle to improve Boundary attack, and also demonstrated significant improvement. The major differences to our algorithm are that we propose new zeroth-order gradient descent algorithm, provide its algorithmic convergence guarantees, and aim to improve the query complexity of the attack formulation proposed in (Cheng 2019). For completeness,
ct al. et al.
also compare with this method in Section A.I Moreover, (Chen 2019) uses one-point gradient estimate, which is unbiased but may encounter larger variance compared with the gradient estimate in our paper. Thus, they are slightly faster in the initial stage, Sign-OPT will catch up and eventually lead to a slightly better solution.
observe in Section A. I..I[ho that although
PROPOSED METHOD
We follow the same formulation in (Cheng et al., 2019) and consider the hard-label attack as the problem of finding the direction with shortest distance to the decision boundary. Specifically, for given example zo, true label yo and the hard-label black-box function f : IRd + (l...., ......,, K), the
objective function g IR + R (for the untargeted attack) can be written as:
min g(0) where g(0) arg min X=0
[(
>
0 [|01|
+ yo
It has been shown that this objective function is usually smooth and the objective function, & can be evaluated by a binary search procedure locally. At each binary search step, we query the function f + X T and determine whether the distance decision boundary in the direction 0 is greater or smaller than À based on the hard-label prediction
As the objective function computable, the directional derivative of g can be estimated by finite differences:
Vg(0 u) g(0 + cu) gg
where u random Gaussian vector and ter. This is standard zeroth order oracle for estimating directional derivative and based on this we can apply many different zeroth order optimization algorithms to minimize g. For example, Cheng et al. (2019) used the Random Deriva- tive Free algorithm Nesterov & Spokoiny (2017) to solve problem (D. However, each computation of (2) requires many hard-label queries due to binary search, so Cheng al. (2099) still requires huge number of queries despite having fast convergence.
is a very small smoothing parame-
Class Y.
In this work, we introduce an algorithm that hugely im- proves the query complexity over Cheng et al. 2019). Our algorithm based on the following key ideas: (i) one does not need very accurate values of directional derivative in order to make the algorithm converge, and (ii) there exists an imperfect but informative estimation of directional derivative of g that can be computed by a single query.
( cm) s(0)
g(0)
l0 exil
Original Image X,
Figure 1: Illustration
Note that binary search only works in small local region; in more general case g0) has be computed by ine-grained search plus hinary search, discussed in Cheng et al. (2019).
3

---

Published as a conference paper at ICLR 2020
Algorithm 1: Sign-OPT attack
Input: Hard-label model f, original image To. initial 0o: for i .. do
Randomly sample u,,...,, "Q from a Gaussian or Uniform distribution;
Compute g 5 1 (0g + eu,) g(Or)) uy
Update 0111 f 0:- ng:
Evaluate g(,)) using the same search algorithm in Cheng al. (2019)
end
3.1 SINGLE QUERY ORACLE
As mentioned before, the previous approach requires com- puting g( + cu) g()) which consumes lot of queries. However, based on the definition of g(+). we can compute the sign of this value sign(g(0 + eu) 9()) using single query. Considering the
untargeted attack case, the sign can be computed by
+1,
f(zo + g(0) (0 [ = yo,
sign(g(0 + +u) =(())
-1, Otherwise.
This is illustrated in Figure | Essentially, for a new direction 0 + eu,, we test whether point the original distance y() from in this direction lies inside or outside the decision boundary, i.e. if the produced perturbation will result in a wrong prediction by classifier. the produced perturbation (0++eu)
is outside the boundary i.e. f + ((0) [@+eul A yu. the new direction has a smaller distance to decision boundary, and thus giving smaller value of g. It indicates that u is descent direction to minimize g.
3.2 SIGN-OPT ATTACK
By sampling random Gaussian vector Q times, estimate the imperfect gradient by
V ğ Eg ( cug) (
g==
(4)
which only requires Q queries. We then use this imperfect gradient estimate to update our search direction <- ng with a step size yj and use the same search procedure to compute g(0) up to certain accuracy. The detailed procedure is shown in Algorithm
We note that Liu et al. (2019) designed a Zeroth Order SignSGD algorithm for soft-label black box attack (not hard-label setting). They use (g( ~ 9 = Eg (g + cu,) ((0),,) and shows that could achieve a comparable or even better convergence rate than zeroth order stochastic gradient descent by using only sign information of gradient estimation. Although it is possible to combine ZO-SignSGD with our proposed single query oracle for solving hard-label attack, their estimator will take sign of the whole vector and thus ignore the direction of u,. which leads to slower convergence practice (please refer to Section 4.4 and Figure 5(b) for more details).
To the best of our knowledge, previous analysis can be used prove convergence of Algorithm [] In the following, we show that Algorithm [ can in fact converge and furthermore, with similar convergence rate compared with (Liu al. 2019) despite using a different gradient estimator.
Assumption 1. Function g(0) is L-smooth with finite value of L. Assumption 2. At any iteration step t, the gradient of the function g is upper bounded by (V ||2 S
Theorem 3.1. Suppose that the conditions in the assumptions hold, and the distribution of gradient noise unimodal and symmetric. Then, Sign- OPT attack with learning rate tp. O( QQ/i) and
(+) will give following bound on E V ( 0))l2
[| = 0 Vd
d
+
VT
VQ
4

---

Published as a conference paper at ICLR 2020
The proof can be found in subsection A.2 The main difference with the original analysis provided by Liu et al. (2019) is that they only only deal with sign of each element, while our analysis also takes the magnitudes of each element of U into account.
3.3 OTHER GRADIENT ESTIMATIONS
Note that the value (g + eu) -())) computed by our single query oracle is actually the sign of the directional derivative:
g eu) g(0), - sign(g(0 + eu) - g(0)) for small e.
sign( V (Q)()), u)) = sign( lim
t-000
Therefore, we can use this information to estimate the original gradient. The Sign-OPT approach in the previous section uses E,signí (Vgg((())))) u,))u, as estimation of gradient. Let y/
sign( (Vg(()) uy)), more accurate gradient estimation can be cast as the following constraint optimization problem:
Find a vector z such that sign((z, u,)) = Vy = =q.=,...,, I....,Q. Q.
Therefore, this is equivalent to a hard constraint SVM problem where each uy is a training sample and yy is the corresponding label. The gradient then be recovered by solving the following quadratic programming problem:
min =²= s.t. z²u,, Uq. - 1........Q
(5)
By solving this problem, can be determined with a single query. Therefore, we propose a variant of Sign-OPT, which is called SVM-OPT attack. The detailed procedure is shown in Algorithm 2 comparison of our two algorithms in subsection 4.1
get good estimation of the gradient. As explained earlier, each yo
We will present empirical
Algorithm 2: SVM-OPT attack
Input: Hard-label model f, original image 2g, initial 0o:
for / 1. 7 do
Sample u,, u,...., uq from Gaussian or orthogonal basis;
Solve defined by (5) Update 0:+1 t- 0, 17
Evaluate g(O)) using search algorithm in Cheng et 2019
end
EXPERIMENTAL RESULTS
We evaluate the SIGN-OPT algorithm for attacking black-bor models in hard-label setting three different standard datasets MNIST (LeCun et al.] 1998). CIFAR-10 (Krizhevsky et al.) and ImageNet-1000 1000 (Deng et al. 2009) and compare it with existing methods. For fair and easy comparison, we use the CNN networks provided by (Carlini & Wagner 2017). which have also been used by other previous hard-label attacks well. Specifically, for both MNIST and CIFAR-10, the model consists of nine layers in total - four convolutional layers, two max-pooling layers and two fully-connected layers. Further details about implementation, training and parameters are available on (Carlini & Wagner 2017). As reported in (Carlini & Wagner, 2017) and (Cheng et al.) 2019). we were able to achieve an accuracy of 99.5% on MNIST and 82.5% on CIFAR-10. 10. We use the pretrained Resnet-50 (He et al. 2016) network provided by torchvision (Marcel & Rodriguez, 2010) for ImageNet-1000, 1000, which achieves a Top-1 accuracy 15%%
In our experiments, we found that Sign-OPT and SVM-OPT perform quite similarly in terms of query efficiency. Hence we compare only Sign-OPT attack with previous approaches and provide a comparison between Sign-OPT and SVM-OPT in isussection 4.1 We compare the following attacks:
Sign-OPT attack (black box): The approach presented this paper.
Opt-based attack (black box): The method proposed in Cheng al. (2019) where they Randomized Gradient-Free method to optimize the same objective function. We use the implementation provided at athttps://git www.. L.e htt.b//c///maaaiii///////o//b/b/
www.hhng/bbackaaaaoo attackk
5

---

Published as a conference paper at ICLR 2020
7.77
3.48
d= 2.41
d 1.65
d 1.13
d 0.94
d 0.86
Original
3
B
5
5
5
5
5
5
n=0
n= 618
n= 1241
n=
n = 3509
n 6037
n = 20163
d=
d=3.11
d= 2.56
d= 1.88
L.14
Original
3
B
B
B
3
5
5
5
n=0
n= 618
n 1002
n= 2134
n = 3667
n 6153
n = 20149
15.18
d = 9.02
d= 6,96
d= 2.98
d= 1.12
0.7.33
d = 0,61
Original
1091
1447
2877
5556
10052
15104
d'= 805.46
436.17
d= 368.92
255.75
88.83
39.63
Original
n= 1091
1381
0 = 2101
n 6156
12248
A 20024
Figure 2: Example of Sig targeted attack. Tz distortions and queries used are shown above and below the images. First two rows: Example comparison of Sign-OPT attack and OPT attack. Third and fourth rows: Examples of Sign-OPT attack on CIFAR-10 10 and ImageNet
Boundary attack (black box): The method proposed in Brendel et al. (2017). This is compared only in 1.2 setting as designed for the same. We use the implementation provided in Foolbox /attpa://githhe
com/bethgel a box).
Guessing Smart Attack (black box): The method proposed in (Brunner et al. 2018). This attack enhances boundary attack by biasing sampling towards three priors. Note that one of the priors assumes access to a similar model as the target model and for fair comparison we do not incorporate this bias in experiments. We use the implementation provided at https: http:///t.ttt.caooooooooooeeeeer
wtt.:///.ttttueeeeeeeeoeme bww.rrrrbbrebbeaaaeeaa.ca boundary
C&W attack (white box): One of the most popular methods in the white-box setting proposed in Carlini & Wagner (2017). We use C&W L2 norm attack as a baseline for the white-box attack performance.
For each attack, we randomly sample 100 examples from validation set and generate adversarial perturbations for them. For untargeted attack, we only consider examples that correctly predicted by model and for targeted attack, we consider examples that are already not predicted as target label by the model. To compare different methods, we mainly use median distortion as the metric. Median distortion for x queries is the median adversarial perturbation of all examples achieved by method using less than queries. Since all the hard-label attack algorithms will start from an adversarial exmample and keep reduce the distortion, if we stop at any time they will always give an adversarial example and medium distortion will be the most suitable metrie to compare their performance. Besides, we also show success rate (SR) for queries for given threshold (c). which the percentage of number of examples that have achieved an adversarial perturbation below e with less than queries. We evaluate success rate on different thresholds which depend on the dataset being used. For comparison different algorithms in each setting, we chose the same set examples across all attacks.
Implementation details: To optimize algorithm we estimate the step size using the same line search procedure implemented in Cheng et al. (2019). At the cost of a relatively small number of queries, this provides significant speedup in the optimization. Similar to Cheng et al. (2019). g()) in last step of algorrihh is approximated via binary search. The initial 0g in alggorithh is calculated

---

Published as a conference paper at ICLR 2020
MNIST
CIFAR-10
CIFAR-10
1.2
Oign-OPT
Q-10
Distortion
3
SVM-OPT
3-
1.0
Q-20
Q-50
2-
Untargetaa
0.8
Q=200
Targeted
0.5
Q-400
11'1
Untargeted
1-
Q-800
0.2
Q-1000
0k
5k
10k Queries
15k
20k
0k
5k
10k
15k
20k
0k
10k
20k
30k
40k
Queries
Queries
Figure 3: Median L2 distortion vs Queries. First two: Comparison of Sign- OPT and SVM-OPT attack for MNIST and CIFAR-10. Third: Performance of Sign-OPT for different values of Q
by evaluating g()) on 100 random directions and taking the best one. provide our implementation publicly
4.1 COMPARISON BETWEEN SIGN-OPT AND SVM-OPT
In experiments, found that the performance in terms of queries of both these attacks is remarkably similar in all settings (both Lg/Lo & Targeted/Untargeteen comparison for MNIST and CIFAR-10 (I22 norm-based) for both targeted and untargeted attacks in Figure 3. We see that the median distortion achieved for a given number of queries is quite on part for both Sign-OPT and SVM-OPT.
and datasets. We present a
Number of queries per gradient estimate: In Figure 3, we show the comparison of Sign-OPT attack with different values of Q. Our experiments suggest that does not have an impact the convergence point reached by the algorithm. Although, small values of Q provide a noisy gradient estimate and hence delayed convergence to an adversarial perturbation. Large values of Q, on the other hand, require large amount of time per gradient estimate. After fine tuning on small set of examples, we found that Q 200 provides a good balance between the two. Hence, we the value of Q = 200 for all our experiments in this section.
4.2 UNTARGETED ATTACK
In this attack, the objective is to generate an adversary from an original image for which the prediction by model is different from that of original image. FFigure 4 provides elaborate comparison of different attacks for L2 case for the three datasets. Sign-OPT attack consistently outperforms the current approaches in terms of queries. Not only is Sign-OPT more efficient in terms of queries, in most cases it converges to a lower distortion than what is possible by other hard-label attacks. Furthermore, we observe Sign-OPT converges solution comparable with C&W white-box attack (better on CIFAR-10, worse on MNIST, comparable on ImageNet). This is significant for a hard-label attack algorithm since we are given very limited information.
We highlight some of the comparisons of Boundary attack, OPT-based attack and Sign-OPT attack (L2 norm- (rrm-based in Table I] Particularly for ImageNet dataset on ResNet-50 model, Sign-OPT attack reaches a median distortion below 3.0 in less than 30k queries while other attacks need more than 200k queries for the same.
4.3 TARGETED ATTACK
In targeted attack, the goal is to generate an adversarial perturbation for image that the prediction of resulting image is the same as a specified target. For each example, we randomly specify the target label, keeping it consistent across different attacks. We calculate the initial 6g in infaggrithmm ] using 100 samples in target label class from training dataset and this 0g is the same across different attacks. |Figure shows some examples of adversarial examples generated by Sign-OPT attack and the Opt-baset attack. The first two rows show comparison of Sign-OPT and Opt attack respectively on an example from MNIST dataset. The figures show adversarial examples generated almost

---

Published as a conference paper at ICLR 2020
MNIST
CIFAR-10
ImageNet
1.5
Sign-OPT
Distortion
OPT
40
Boundary
1.0
Guessing Smart
30
0.5
La
10
OK
10k
20k Queries
30k
40k
0k
10k
20k Queries
30k
40k
20k
40k Querles
60k
80k
Figure Untargeted attack: Median distortion vs Queries for different datasets.
MNIST
CIFAR-10
CIFAR-10
2.0
1.0
Sign OPT
Sign OPT
Distortion
CPT
1.5
0.8
DPT
ZD-igrdGD
Guassing
Z0-ig11GD 500
CW
1.0-
CW
0.4
0.5
0.2
0k
10k
20k 30k
40k
50k
Ok
10k
20k Queries
30k
40k
0k
5k
10k
15k
20k
Queries
Queries (b)
(a)
Figure 5: (a) Targeted Attack: Median distortion Queries of different attacks MNIST and
CIFAR-10. (b) Comparing Sign-OPT and ZO-SignSGD with and without single query oracle (SQO).
same number of queries for both attacks. Sign-OPT method generates an L2 adversarial perturbation of 0.94 in 6k queries for this particular example while Opt-based attack requires 35k for the same. Figure 5 displays a comparison among different attacks in targeted setting. In our experiments, average distortion achieved by white box attack C& W for MNIST dataset is 1.51, for which Sign-OPT requires ~ 12k queries while others need > 120k queries. We present comparison of success rate of different attacks for CIFAR-10 dataset Figure for both targeted and untargeted cases.
4.4 THE POWER OF SINGLE QUERY ORACLE
In this subsection, conduct several experiments prove the effectiveness of our proposed single query oracle in hard-label adversarial attack setting. 70-SignSGD algorithm (Liu et al. (019) is proposed for soft-label black box attack and we extend into hard-label setting. straightforward way is simply applying ZO-SignSGD to solve the hard-label objective proposed in Cheng et al. (2019), estimate the gradient using binary search as (Cheng et al. 2019) and take its sign. In Figure 5(b), we clearly observe that simply combining ZO-Sign ZO-SignSGD and Cheng et al. (2019) is not efficient. With the proposed single query sign oracle, we can also reduce the query count of this method, as demonstrated in Figure 5(b). This verifies the effectiveness of single query oracle, which can universally improve many different optimization methods in the hard-label attack setting. To be noted, there is still improvement Sign- OPT over ZO-SignSGD with single query oracle because instead
1.0
0
C=0.3
1.0
c=0.66
C=0.3
Succcoss Rate
Rak
Surcezs Rabe
Rabe
0.6
0.6
0.6
0.6
0.4
Sign-OPT
0.4
OPT
0.2
Boundary
0.2
Guess ng Smart
0.0
0k
40k
0.0
20k
40k
0.0
0k
40k
0.0
20k
60k
Figure 6: Success Rate vs Queries for CIFAR- 10 (L2 norm-based attack). First two and last two depict untargeted and targeted attacks respectively. Success rate threshold is at the top of each plot.
8

---

Published as a conference paper at ICLR 2020
Table Le Untargeted attack Comparison of average Le distortion achieved using given number of queries for different attacks. SR stands for success rate.
MNIST
CIFARIO Avg. lg
ImageNet (ResNet-5O)
#Queries
Avg 1.2
SR(r 1.5)
#Queries
SR 0.5)
#Queries
Avg l/2
SR(r = 3.0)
4,000
3.12
2.3%
209.63
Boundary attack
8,000
4.24
1.0%
8,000
2.84
7.6%
30,000
17.40
16.6%
14,000
2.13
16.3%
12,000
0.78
29.2%
160,000
4.62
41.6%
4,000
3.63
3.0%
4,000
0.77
37.0%
4,000
83.83
2.0%
OPT attack
8,000
2.41
18.0%
8,000
0.43
53.0%
30,000
16.77
14.0%
14,000
0.33
160,000
4,000
1.74
41.0%
4,000
0.29
75.0%
4,000
16.69
12.0%
Guessing
8,000
1.69
42.0%
8,000
0.25
80.0%
30,000
13.27
12.0%
14,000
43.0%
0.24
80.0%
160,000
12.0%
Sign-OPT attack
4,000
1,54
46,0%
4,000
0.26
75.0%
4,000
23.19
8,0%
8,000
1.18
84.0%
8,000
0.16
90.0%
30,000
50.0%
14,000
1.09
94.0%
12,000
0.13
95.0%
160,000
1.21
90.0%
C&W (white-box)
0.88
99.0%
0.25
85.0%
1.31
80.0%
of directly taking the sign of gradient estimation, our algorithm utilizes the scale random direction well. In other words, signSGD's gradient norm is always 1 while gradient norm takes into account the magnitude of u. Therefore, our signOPT optimization algorithm is fundamentally different (Liu al. 2019) any other proposed signSGD varieties. Our method can be viewed new zeroth order optimization algorithm that features fast convergence in signSGD.
5 CONCLUSION
We developed a new and ultra query-efficient algorithm for adversarial attack in the hard-label black-box setting. Using the same smooth reformulation in [heng al. (2019), we design novel zeroth order oracle that can compute the sign of directional derivative of the attack objective using single query. Equipped with this single-query oracle, we design new optimization algorithm that can dramatically reduce number of queries compared with Cheng et al. (2019). We prove the convergence of the proposed algorithm and show our new algorithm is overwhelmingly better than current hard-label black-box attacks.
ACKNOWLEDGEMENT
This work is based upon work supported by the Department of Energy National Energy Technology Laboratory under Award Number DE-OE000091 and by NSF under IIS1719097.

---

Published as a conference paper at ICLR 2020
REFERENCES
Abdullah Al-Dujaili and Una-May O'Reilly. There are no bit parts for sign bits in black-box attacks. 2019.
arXiv preprint
Moustafa Alzantot, Yash Sharma, Supriyo Chakraborty, Huan Zhang, Cho-Jui Hsieh, and Mani B Srivastava. Genattack: Practical black-box attacks with gradient-free free optimization. Proceedings of the Genetic and Evolutionary Computation Conference, pp. 1111-1119, 2019.
Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples. In ICML, 2018.
Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Animashree Anandkumar.
signSGD: Compressed optimisation for non-convex problems. In Jemnifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Pro- ceedings of Machine Learning Research, pp. 560-569, Stockholmsmssan, Stockholm Sweden, 10- 15 Jul 2018. PMLR. URL html
Wieland Brendel, Jonas Rauber, and Matthias Bethge. Decision Decision-based adversarial attacks: Reliable attacks against black-box machine learning models. arXiv preprint arXiv:1712.04244 2017.
Thomas Brunner, Frederik Diehl, Michael Truong Le, and Alois Knoll. Guessing smart: Biased sampling for efficient black-box adversarial attacks. arXiv preprint arXiv:1812.09803 0218810..990,, 2018.
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In
Security and Privucy (SP), 20/7 IEEE Symposium on, pp. 39-57. IRFF, 2017.
Jianbo Chen, Michael I. Jordan, and Martin J. Wainwright. Hopskipjumpattack: A query-efficient decision-based attack. arXiv preprint arXiv: T.G:::9944000 144, 2019.
Pin-Yr Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsieh. Zoo: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models. In Proceedings of the 10th ACM Workshop Artificial Intelligence and Security, pp. 15-26. ACM, 2017.
Pin-Yu Yu Chen, Yash Sharma, Huan Zhang, Jinfeng Yi, and Cho-Jui Hsich. Ead: clastic-net attacks to deep neural networks via adversarial examples. Thirty-second AAAI conference on artificial intelligence, 2018.
Minhao Cheng, Thong Le, Pin-Yu Chen, Huan Zhang, JinFeng Yi, and Cho-Jui Hsieh. Query- efficient hard-label black-box attack: An optimization-based approach. International Confer- ence on Learning Representations, 2019, URL
net contt/foumm?ii.
kJ1k6iRRKX
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In Computer Vision and Pattern Recognition, 2009, CVPR 2009. IEEE Conference on, pp. 248-255. IEEE, 2009.
John C Duchi, Peter L Bartlett, and Martin J Wainwright. Randomized smoothing for stochastic optimization. SIAM Journal Optimization, 22(2):674-701, 2012.
Ian Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In International Conference on Learning Representations, 2015.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference 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. In International Conference on Machine Learning, pp. 2142-2151, 201 8a.
10

---

Published as a conference paper at ICLR 2020
Andrew Ilyas, Logan Engstrom, and Aleksander Madry. Prior convictions: Black-box adversarial attacks with bandits and priors. arXiv preprint arXiv:1807.07978, 2018b.
Kwang-Sung Jun, Lihong Li, Yuzhe Ma, and Jerry Zhu. Adversarial attacks on stochastic bandits. In Advances in Neural Information Processing Systems, pp. 3640-3649, 2018.
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cifar-10 (canadian institute for advanced research). URLhttt::/ www. cs torottotooooo.oo. serronto.edu/kkrll. ctr..arraam..
Alexey Kurakin, Ian Goodfellow, and Samy Bengio. Adversarial machine learning at scale. arXiv preprint urXiv:1611.01253 2016.
Yann LeCun, Léon Bottou, Yoshua Bengio, Patrick Haffner, et al. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 36(11):2278-2324 1998.
Sijia Liu, Bhavya Kailkhura, Pin-Yu Chen, Paishun Ting. Shiyu Chang. and Lisa Amini. Zeroth-order stochastic variance reduction for nonconvex optimization. In
S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Gar- nett (eds.), Advances in Neural Information Processing Systems 31, pp. 3727- 3737. Curran Associates, Inc., 2018. URL.
nips cc/paper/
7630- zeroth-ordez: wtw.oorrrre-sooottii---------eee warvaaiiinnn reductionn non-oooooe----------o- op imization.
pdf
Sijia Liu, Pin-Yu Chen, Xiangyi Chen, and Mingyi Hong. signSGD via zeroth-order oracle. In International Conference Learning Representations, 2019. URL htttps://operrreiiiet
net pet//oorue BJe-uummid-dBee---------eeeee DsC5Fm
Aleksander Madry. Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv: 1706.06083.. 2017.
Sébastien Marcel and Yann Rodriguez. Torchvision the machine-vision package of torch. In Proceedings of the 18th ACM International Conference on Multimedia, MM '10, pp. 1485-1488, New York, NY, USA, 2010. ACM. ISBN 978-1-60555-993--6 doi: 10.1144518739951118444 (tRl:htt:://de acm, 1tte://..11111173331 187777
Yurii Nesterov and Vladimir Spokoiny. Random gradient-free free minimization of convex functions. Foundations of Computational Mathematics, 17(2):527-566, 2017.
Nicolas Papernot, Patrick McDaniel, Ian Goodfellow, Somesh Jha, Z Berkay Celik, and Ananthram Swami. Practical black-box attacks against machine learning. In Proceedings of the 2017 ACM on Asia Conference on Computer and Communications Security. pp. 506-519. ACM, 2017
Christian Szegedy, Vincent Vanhoucke, Sergey loffe, Jon Shlens, and Zbigniew Wojna. Rethinking the inception architecture for computer vision. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2818 1816, 2016.
Chun-Chen Tu, Paishun Ting, Pin- Yu Chen, Sijia Liu, Huan Zhang, Jinfeng Yi, Cho-Jui Hsieh, and Shin-Ming Cheng. Autozoom: Autoencoder- based zeroth order optimization method for attacking black-box neural networks. AAAI, 2019.
Huan Zhang, Hongge Chen, Zhao Song. Duane Boning, Inderjit S Dhillon, and Cho-Jui Hsich. The limitations of adversarial training and the blind-spot attack. arXiv preprint arXiv: MXX::/901/. 1900/90044400 04664, 2019.

---

Published as a conference paper at ICLR 2020
A APPENDIX
A.1 COMPARISON WITH HOPSKIPJUMPATTACK
There is recent paper (Chen et al. 2019) that applied the zeroth-order sign oracle to improve Boundary attack, and also demonstrated significant improvement. 'he major differences to our algorithm that we propose a new zeroth-order gradient descent algorithm, provide its algorithmic convergence guarantees, and aim to improve the query complexity of the attack formulation proposed in (Cheng et al. 2019). To be noted, HopSkip/umpAtten only provides the bias and variance analysis (Theorem 2 and 3) without convergence rate analysis.
Also, HopSkiplumpAttaces uses one-point gradient estimate compared the 2-point gradient estimate used by SignOPT. Therefore, although the estimation is unbiased, it has large variance, which achieves successful attack faster but generates worse adversarial example with larger distortion than ours. For completeness, also compare with this method (and mention the results) as follows.
shows comparison of Sign-OPT and HopSkiplumpAttack for CIFAR-I0 and MNIST datasets for the case of L2 norm based attack. We find in our experiments that performance of both attacks is comparable in terms of queries consumed. In some cases, Sign-OPT converges to better solution.
Figure 7
MNIST (U)
MNIST (T)
CIFAR-10 (U)
CIFAR-10 (T)
2.5
2.5
1.5
1.5
HopSkiglumpAttakk
Disttrrtion
2.0
CW
2.0
1.0
1.0
1.5
1.5
0.5
0.5
1.0
1.0
0.5
Ok
20k Queries
40k
20k Querles
40k Ok
20k Queries
40k Ok
20k Queries
40k
Figure 7: Comparison with HopSkiplumpAAtack for CIFAR and MNIST: Median distortion vs Queries. (U) represents untargeted attack and (T) represents targeted attack.
A.2
PROOF
Define following notations:
Vo(O,; ug) = sign(g((0, + Eug) g(
V (0,; u.y) = - é [g(() + cug) - g((,)))
Vg(0;; = = sign( (g(0: + +cuy) g(O,))
Thus we could write the corresponding estimate of gradients as follow:
1
1
9: Sign(g(O0 + Euy) g(Or))u,,
V ( uny)
Q
Q
Q
1
9.
(g(O, + tuug) -9(0)))
V
4 0,: Ug)
Q
Q
9=1
Q
g: Q
Σ
sign( (g(O, + cug) - -((:))) = Q 9=1
V g 0g: u.g)
q=1
Clearly, we have (g(0,; uny) sign( (0( u.)) and we could relate Vg(0;; n.)) and (g(0,; u.)) by writing V.( un) G, o Vg(O,; un)) where where G, Rd is absolute value of vector un (i.e.
G3 (|ug,),, uy.22.... |Uq.d)2)) ).
12

---

Published as a conference paper at ICLR 2020
Note that Zeroth-order gradient estimate Vg(0,; ug) is a biased approximation to the true gradient of g. Instead, it becomes unbiased to the gradient of the randomized smoothing function ge =
(u + eu) Duchi al. (2012).
Our analysis is based on the following two assumptions:
Assumption
function g L-smooth with a finite value of L.
Assumption 2 At any iteration step t, the gradient of the function is upper bounded by [VVy(0,)l2 S a.
To prove the convergence of proposed method, we need the information on variance of the update Vg((,; uy). Here, we introduce lemma from previous works.
Lemma
The variance Zeroth- gradient estimate (g(0,; ugy) is upper bounded by
[l[Vg((0; - = 4(Q 1) o²
2 cl.,c),
Q Q
where C(d, 2do 122
Proof of Lemma This lemma could be proved by using proposition 2 in Liu et al. (2019) with b I and q Q. When b= there is no difference between with/without replacement, and we opt for with replacement case to obtain above bound. M
By talking Q = 1, we know that [|[] V g0,; u.,)) (g.(0))) upper bounded. And by Jensen's inequality, we also know that the
B[I(Vg(0:: u.y)
Vg. S ( ([(((g((::u))) Vg. (O:)))))
where 8 denotes the upper bound of Ith coordinate of E [[Vg(0;; (g.((:)]] and is finite since [[| (O,; un)) ye (0.) upper bounded.
Next, we want to show the Prob (issssingggg)) + sign((Vg. by following lemma.
Lemma (eVg.
sign( (Vgn( - /
Proof of Lemma Similar to Bernstein et al. 2018 we first relax Problsign((Vg() # (ign(Vg(O.))) by Markov incquality:
Pooblsign((Vg((. u)))) + sign((Vg < Probl] u.)1)l (0))l
E ([ Vg.
Vg.
(0.
where the last inequality comes from eq 6). Recall that (Vg(O,; un )t) is an unbiased estimation
to (Vg, (0,)), (.). Under the assumption that the noise distribution is unimodal and symmetric, from Bernstein et al. 2018) Lemma DI, we will have
S
1
Problsign((Vg(00: # (V. M
8
otherwise
2
2/3
where S (0.))////
13

---

Published as a conference paper at ICLR 2020
Note that this probability bound applies uniformly to all regardless of the magnitude ((ug)1)
That is,
Prob sign
(u (iV + sign (g.(
q=1
Prob(sign
sign Vg(0,; + sign( Vg.(
This true as when all [(u)) [ Prob Problsign(())) (2 sign (ggn(v((00 (O; un)))) + sign( gg is equiv- alent majority voting of each estimate q yielding correct sign. This is the same as sum of Q bernoulli trials (i.e. binomial distribution) with error rate M. And since error probability M is independent of sampling of (uyg)), caleulating Prob(sign(E ((ng)))sign((V((())) Ug))i)
could be thought taking Q bernoulli experiments and then independently draw weight from unit length for each of Q experiment. Since the weight uniform, we will have expecta- tion of weights on correct counts and incorrect counts are the same and equal to 1/2. There- ( g= ((,,)( u();) A (ig same original non-weighted binomial distribution. Notice that by our notation, will have sign( (g (n))t) (g(0; ug)) thus Q Σg sign( (g(( u.))). = (gt). Let Z counts the num-
fore, the probability of Prob[sign
still the
ber of estimates (O,;; u,); yielding correct sign g. (O.).. Probability in eq could be written as:
Q
Prob (sggn)(((()(()) # sign( (g.().))) Plz < 2
Following the derivation of theorem 2b in Bernstein et 2018). we could get
Q P(z < 2
VQS
& ((:))():)) (rob(ssggg))) ( (Vg)((V)
(8)
VQ
We also need few more lemmas on properties of function g-
Lemma ge (01) 9e (Or) s (..)) g" + 2
Proof of Lemma 3
The proof can be found in Liu et al. 2018
Lemma C.
Lemma 4
< V2E[II [
(0)
eLd /2"
where g" ming g(O).
Proof of Lemma The proof can be found in Liu 2019).
Theorem Suppose that the conditions in the assumptions hold, and the distribution of gradient
noise is unimodal and symmetric. Then, Sign-OPT attack with learning rate T)c = O QV8T) and
= (())) will give following bound on [[]] (0)
[ O Vd vT
+
vQ
Proof of Theorem
From L-smoothness assumption could have
14

---

Published as a conference paper at ICLR 2020
ge(0 & g.(()) + (Vg. -0)) L
2 10 - 0.11
= (..) - T/ (Vy, (.)) + 2 0
dL.
-.())) Nu G. Vg.
o Ge
2 "
+ 2m 3 C. (Vg. Prob sign (g:))) (i))
(( where G. is defined (G,): E (G);))( E ( ug).. Continue the inequality,
dL T/ o G2 ge,). - Th Vo
d + 2 o G.
(Vg. (0.)); Prob/sign (g.))) + (())((
dL
2m 2 G. Σ &
(9. m G. 9c 01)
2 the
Gi
by eq 8
VQ
1=1
dL
+2m 2 G. |6111
(0,) Nu G. 99. (0))
th
Gi
2
VQ
dL.
$ (9.) - n 0 G. 99. (0)
2 n
G
2m 2 O..
VQ
dL
vd B
[[[(V
un) (0.)))
(0.) me V. (0.)11
2 t
G
2m 2 G.
by eq (6)
VQ
Thus will have,
V(VE(((V((r:uu) Vg.
dL 2 %
(0, < o (o)lll
o G.
2m o G.
VQ
vā [[(((((();; (o.
dL m
+ >m m V.l 01))11 s (..) - (0.+1) +
@ G.
+ 2m 2 G.
2
B[[(V9(O0: m.) V (O.)))
dL 2 + 21
+
S (0.) (O.IlI (0+1)
2
VQ
where we define tne = n @ G. Sum up all inequalities for all ts and take expectation on both side, will have
dL
B & (0,) (00)
2
+
24j, 21j. v.
B[((Vg(0::n.)) (g.)))
2
< (0g) g.
dL
Σ
T
1/2
+
T
21
4(Q+1)
0² C(d,e) Q
2
by Lemma 1.
2
Q
[=1
(=1
Substitute Lemma into above inequality, get
dl
4(Q +1
2
El| (g. S (0, 9" +
Σ
T/E
2
Σ
20 Vāl
0 C(d,c).
2
Q
[=]
t=1
15

---

Published as a conference paper at ICLR 2020
Since -| 1l2 || | and we could divide Σ t/ on both side to get
n 11=1 g. (0.)1la]
< Je (e(0)) 9g EL
dL
Σ T
Σ
2vd VQ
V /4QQ + 1)o² + 2C((de).
Σ' Ar
2 E1=1 AR
Define new random variable R with probability P(R = t) =
E Ttt
we will have
1/-
B Vgl (0n) = E
=
P(R = V
Substitute all the quantities into Lemma 4, we will get
V2(g. [ S
9" L)
dL Ei= eLd
2222V VQ
V4 + 1)o2 + 2C(d.e).
Et de V2 1
By choosing c ( and ft O6 @vvTT) ) then the convergence rate shown in above is 0 + vQ)
16


Reviews:
[{"review_id": "HJxBPlpEFB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "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 propose a new algorithm for evaluating adversarial robustness of black-box models. The aim of the proposed algorithm, SIGN-OPT is generating adversarial examples as close as possible to the decision boundary using as less queries of the black-box model as possible.\n\nThe authors follow the approach of (Cheng et al 2019) by modeling the problem as an optimization problem, where the objective function is to find the direction with the shortest distance to the decision boundary. They propose a smart modification of the previous approach by evaluating the sign of the gradient rather than the gradient itself. The advantage is that the sign of the gradient can be evaluated using a single query while the estimation of the gradient needs many queries. \nThe authors have analyzed the proposed algorithm. They showed that using SIGN-OPT, the expectation of the gradient tends to zero in $O(1/\\sqrt(T))$, meaning that a (local) minimum is reached.\nThe algorithm is favorably compared with the state-of-the-art on three image test sets (MNIST, CIFAR-10n ImageNet).\n\nThis paper is technically sound, well-written and propose an interesting modification of a previous algorithm. I vote for acceptance.\n\nHowever, I have some concerns:\n-\tI think that the L-smoothness assumption should be discussed. Is it realistic for Deep Learning models? Does it hold for the three attacked CNN networks?\n-\tThe analytical results of the previous algorithm RGF and the proposed algorithm SIGN-OPT are not compared and discussed. It is a pity.\n\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "H1eZtKICKB", "reviewer": "AnonReviewer3", "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": "Summary: The paper develops a query efficient algorithm for computing black box adversarial examples given only hard labels in the context of deep neural networks. Intuitively, the only information of the function provided to the algorithm is the label for a given sample. Technically, the authors use the formulation proposed by Cheng et al, and derive a zeroth optimization algorithm that uses less queries with nice convergence properties. Experimentally, the proposed algorithm is very effective on three different standard datasets in vision.\n\nI have decided to weak reject the paper for the following key reasons:\n\n1. Novelty: the technique as such as very similar to Cheng et al, and Liu et al, as the authors themselves mention it in Section 3.2. In particular, the speed-up compared to Cheng et al, is twice -- for a bounded maximum \\alpha in Algorithm 1 in Cheng et al, which is almost always the case, because otherwise it would not be \"adversarial\" in nature. The authors claim that the convergence result has not been proved yet for the proposed algorithm but it follows using the technique used in Bernstein et al 2018, with some minor modifications.\n\n2. Experiments: While the experiments that the authors support the claim, I think they are missing comparison with Liu et al which is crucial. In Fig 4, their method is doing even better than white box attacks, how can this be true? or why is this true?", "extra_scores": {"experience_assessment": "I have published one or two 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 carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers had several concerns with the paper related to novelty and comparisons with other approaches. During the discussion phase, these concerns were adequately addressed.
Decision: Accept (Poster)