Sign Bits Are All You Need for Black-Box Attacks
Authors: Abdullah Al-Dujaili
Una-May O'Reilly
Venue:  (2020)
Keywords: Black-box adversarial attack models
Deep Nets
Adversarial Examples
Black-Box Optimization
Zeroth-Order Optimization

Abstract: We present a novel black-box adversarial attack algorithm with state-of-the-art model evasion rates for query efficiency under $\ell_\infty$ and $\ell_2$ metrics. It exploits a \textit{sign-based}, rather than magnitude-based, gradient estimation approach that shifts the gradient estimation from continuous to binary black-box optimization. It adaptively constructs queries to estimate the gradient, one query relying upon the previous, rather than re-estimating the gradient each step with random query construction. Its reliance on sign bits yields  a smaller memory footprint and it requires neither hyperparameter tuning or dimensionality reduction. Further, its theoretical performance is guaranteed and it can characterize  adversarial subspaces better than white-box gradient-aligned subspaces. On two public black-box attack challenges and a model robustly trained against transfer attacks, the algorithm's evasion rates surpass all submitted attacks. For a suite of published models,  the algorithm is $3.8\times$ less failure-prone while spending $2.5\times$  fewer queries versus the best combination of state of art algorithms. For example, it evades a standard MNIST model using just $12$ queries on average. Similar performance is observed on a standard IMAGENET model with an average of $579$ queries.

Published conference paper ICLR 2020
SIGN BITS ARE ALL YOU NEED FOR BLACK-BOX AT- TACKS
Abdullah Al-Dujaili CSAIL, MIT Cambridge, MA 02139 aldujai mesiiimmiteee.
Una-May O'Reilly CSAIL, MIT
Cambridge, MA 02139 unamay8csail mit edu
ABSTRACT
We present a novel black-box adversarial attack algorithm with state-of-the-art model evasion rates for query efficiency under fox and & metries. It exploits a sign-based, rather than magnitude-basee gradient estimation approach that shifts the gradient estimation from continuous binary black-box optimization. It adaptively constructs queries to estimate the gradient, one query relying upon the previous, rather than re-estimating the gradient each step with random query construction. Its reliance on sign bits yields smaller memory footprint and it requires neither hyperparameter tuning or dimensionality reduction, Further, its theoretical performance is guaranteed and it can characterize adversarial subspaces better than white-box gradient-aligned subspaces. On two public black -box attack challenges and a model robustly trained against transfer attacks, the algorithm'' 's evasion rates surpass all submitted attacks. For a suite of published models, the algorithm is 3.8x less failure-prone while spending 2.5x fewer queries versus the best combination of state art algorithms. For example, it evades a standard MNIST model using just 12 queries on average. Similar performance is observed on a standard IMAGENET model with an average of 579 queries.
INTRODUCTION
Problem. Deep Neural Networks (DNNs) are vulnerable to adversarial examples, which are malicious inputs designed to fool the model's prediction (Biggio and Roli, 2018) for comprehensive, recent overview of adversarial examples. Research on generating these malicious inputs started the white-box setting, where access to the gradients of the models is assumed. Since the gradient points to the direction of steepest ascent, an input can be perturbed along the gradient's 's direction to maximize the network's loss, thereby potentially causing misclassification under class prediction, e.g. with images, or evasion under detection, e.g. with malware. The assumption of access to the underlying gradient does not however reflect real world scenarios. Attack algorithms under a more realistic, restrictive black-box threat model, which assumes access to predictions in lieu of gradients, are therefore studied. Central to their approaches is estimating the gradient. To estimate the magnitudes and signs of the gradient, the community at large has formulated continuous optimization problem of (n) complexity where n is the input dimensionalityy Most recently work has sought to reduce this complexity by means of htt--ttie-eeeeedeee different tact and reduce the central problem to just estimating the signs of the gradients. Our intuition arises from observing that estimating the sign of the top 30% gradient coordinates by magnitude is enough to achieve a rough misclassification rate of 70%. Figure reproducing Ilyas et al. (2019) 9) illustrates this observation for the MNIST dataset-sce Appendix A for other datasets. Therefore our goal is to recover the sign of the gradient with high query efficiency so we can use it to generate adversarial examples effective as those generated by full gradient estimation approaches.
priors Ilyas et al. (2019). In this paper, we take
Related Work. We organize the related work in two themes, namely Adversarial Example Generation and Sign-Based Optimization. The literature of the first theme primarily divides into white-box and black-bo box settings. The white-box setting. while not the focus of this work, follows from the works of Biggio et al. (2013) and Goodfellow et (2015) who introduced the Fast Gradient Sign Method (FGSM), including several methods to produce adversarial examples for various learning tasks and threat perturbation constraints (Carlini and Wagner, 2017; Moosavi-Dezzood et al., 2016; Hayes and

---

Published conference paper at ICLR 2020
Danezis, 2017: Al-Dujaili et al., 2018; Kurakin al., 2017; Shamir et al., 2019). Turning to the black- box setting and iterative optimization schemes, Narodytska and Kasiviswanathan (2017), without using any gradient information, use a naive policy of perturbing random segments of an image to generate adversarial examples. Bhagoji et al. (2017) reduce the dimensions of the feature space using Principal Component Analysis (PCA) and random feature grouping, before estimating gradients. Chen et al. (2017) introduce principled approach by using gradient based optimization. They employ finite differences, a zeroth-order optimization means, to estimate the gradient and then use it to design gradient-based attack. While this approach successfully generates adversarial examples, it is expensive in how many times the model is queried. Ilyas et al. (2018) substitute traditional finite differences methods with Natural Evolutionary Strategies (NES) to obtain an estimate of the gradient. Tu et al. (2018) provide an adaptive random gradient estimation algorithm that balances query counts and distortion, and introduces trained auto-encoder to achieve attack acceleration. Ilyas al. (2019) extend this line of work by proposing the idea of gradient priors and bandits: Bandit t LSTD. Our work contrasts with the general approach of these works in two ways: a) We focus on estimating the sign of the gradient and investigate whether this estimation suffices to efficiently generate adversarial examples. b) The above methods employ random sampling in constructing queries to the model while our construction is adaptive.' Another approach involves learning adversarial examples for one model (with access to its gradient information) to transfer them against another (Liu et al., 2016; Papernot al., 2017). Alternately, Xiao et al. (2018) use Generative Adversarial Network (GAN) to generate adversarial examples which are based on small norm-bounded perturbations. These methods involve learning on different model, which is expensive, and not amenable to comparison with setups-including that directly query the model of interest.
Sign-Based Optimization. In the context of general- purpose continuous optimization methods, sign- based stochastic gradient descent was studied in both zeroth- and first-order setups. In the latter, Bern- stein et al. (2018) analyzed gignSGD, sign sign-based Stochastic Gradient Descent, and showed that it en- joys faster empirical convergence than SGD in ad-
migelassffication rate
randiom-
10.5
tap-k
0.8
0.4
0.2
dition to the cost reduction of communicating gra-
dients across multiple workers. Liu et al. (2019) extended s signSGD to zeroth- setup with the 20-SignSCD algorithm. SnnSignSSD (Liu et al., 2019) was shown outperform NES against black- box model on MNIST. These approaches use the sign of the gradient (or its zero-order estimate) to achieve better convergence, whereas our approach both esti- mates and uses the sign of the gradient.
20%
RIFG
1005%
k pereeett of MNIST coordinates
Figure I: Misclassification rate of an MNIST model on the noisy FGSM's adversarial ex- amples as a function of correctly estimated coordinates of sign(V fxx y)) on 1000 ran- dom MNIST images. Estimating the sign of the top 30% gradient coordinates (in terms of their magnitudes) is enough to achieve a rough misclassification rate of 70%. More details can be found in Appendix A.
Contributions. We present the following contribu- tions at the intersection of adversarial machine learn- ing and black-box keeroth-orden optimization: 1) We
exploit the separability property of the directional derivative of the loss function of the model under attack in the direction of [+1}* vectors, to propose a divide-and-come andiidd--dd-coeeer adaptive, memory- memory-efficient algorithm, we name Si SignHunter, to estimate the gradient sign bits. 2) We provide a worst-case theoretical guarantee on the number of queries required by SignHunter to perform at least as well as FGSM (Goodfellow et al., 2015), which has access to the model's gradient. To our knowledge, no black-box attack from the literature offers similar performance guarantee. 3) We evaluate approach on a rigorous set of experiments on both, standard and adversarially hardened models. All other previous works on this topic have published their results on a subset of the datasets and threat models we experimentally validate in this work. Through these experiments, we demonstrate that s gnnnttr''s adaptive search for the gradient sign allows craft adversarial examples within a mere fraction of the theoretical number of queries thus outperforming FGSM and state-of-the-an black-box attacks. 4) We release a software framework systematically benchmark adversarial
WWe use the term adaptive here to characterize how the algorithm constructs its perturbation vector qu deterministically based on the previous perturbations. Mathematically, the perturbation vector time f can be expressed as deterministic function q 9(q:-1). In contrast, other algorithms construct I.I.D randomly perturbation vectors: g: ~ (0, 1).

---

Published conference paper at ICLR 2020
black-box attacks, including SignHunter's. on MNIST, CIFARIO, and IMAGENET models in terms of success rate, query count, and other metrics. 5) We demonstrate how Si gnHunter can be used characterize adversarial cones in a black-box setup and in doing so, highlight the gradient masking effect.
Notation. Let n denote the dimension of datapoint æ. Denote a hidden n-dimensional binary code by q'. That is, q" E H -,," Further, denote the directional derivative of some function f at point æ in the direction of a vector v by Dff(2)) = v'V (=)(x) which often can be approximated by the finite difference method. That is, for 6 > O, we have
(xf(x)= = v² v=f(x)= = f(x + óv) - f(x)
(1)
5
S, Let [Is(.) be the projection operator onto the set S, Bp e) be the lp ball of radius around æ.
2 GRADIENT ESTIMATION
At the heart of black-box adversarial attacks is generating perturbation vector slightly modify the original input a so as to fool the network prediction of its true label y. Put differently, an adversarial example x' maximizes the network's loss L(x', y) but still remains c-close the original input Although the loss function L can be non-concave, gradient-
techniques are often very successful in crafting an adversarial example Madry et al. (2017). That is, setting the perturbation vector as a step in the direction of V L(,( y). Consequently, the bulk of black-box attack methods try to estimate the gradient by querying an oracle that returns, for a given input/label pair (x. y). the value of the network's ' loss L(z,y), consulting prediction or classification accuracy. Using only such value queries, the basic approach relies on the finite difference method to approximate the directional derivative (Eq. 1) of the function I. at the input/label pair (at, y) in the direction of a vector which corresponds to o" (z,((x,)), y). With n linearly independent vectors (v, V y) = dihisien. one can construct linear system of equations recover the full gradient. Clearly, this approach's query complexity is O(), which can be prohibitively expensive for large n (e.g., n = 268, 203 for the IMAGENET dataset). Recent works try mitigate this issue by exploiting data- and/or time-dependent priors (Tu et al., 2018; llyas et al., 2018; 2019). However, the queries are not adaptive, they are constructed based on i.i.d. random vectors {v: They fail to make use of the past queries' responses to construct the new query and recover the full gradient more efficiently. As stated in the introduction, we solve the smaller problem gradient sign estimation with adaptive queries based on the observation that simply leveraging (noisy) sign bits of the gradient yields successful attacks-see Figure 1.
Definition 1. (Gradient Sign Estimation Problem) For input/label pair (x. and loss function I., let g" = V. I. y) be the gradient of L at (x. y) and q" sign(g") E H be the sign bit vector of g" Then the goal of the gradient sign estimation problem is to find a binary vector q E H maximizing the directional derivative"
max DgL(x. GEH
(2)
from a limited number of (possibly adaptive) function value queries L(x', .))-
3 A METHOD FOR ESTIMATING SIGN OF THE GRADIENT FROM ADAPTIVE QUERIES
Our goal is to estimate the gradient sign bits of the loss function L of the model under attack at an input/label pair (æ, y) from a limited number of loss value adaptive queries L(x', y). To this end, we examine the basic concept of directional derivatives that has been employed in recent black-box
Withoout loss of generality, we encode the sign bit vector in = [-1,+1}' rather than (0. 1)" This a common representation sign-related literature. Note that the standard sign function has the range of {-1, 0, +1}. Here, we use the non non-standard definition (Zhao, 2018) whose range is {-1, +1}. This follows from the observation that DNNs gradients with respect to their inputs are not sparse (Ilyas et al., 2019, Appendix B.1).
TTe maximization follows from Dg y) q" "gg which is maximized when = q' sign(g").
3

---

Published conference paper at ICLR 2020
adversarial attacks. Based on the definition of the directional derivative (Eq. 1). the following can be stated.
Property (Separabilityy of DgL(xx The directional derivative Dy y) of the loss function L at imput/label pair (z, y) in the direction of binary code q is separable. That is,
n1
max DgL(xx GEH
max q' g qEH
max (E(-1,+1]
9:9;
(3)
This reformulates the gradient sign estimation prob- lem from single n--dimensional to n I-dimensional binary black-box optimization problems, reducing the search space of sign bits from 2 to 2n. Sub- sequently, one could recover the gradient sign bits with n + queries as follows: i. Start with an ar- bitrary sign vector and compute the directional derivative Lxx y). Using Eq. 1, this requires two queries:
Algorithm 1 ISS SignHunter
7. + R : the black-box function be maxi- mized over the binary hypercuhe H. = (1),+1)"
def init(g)
0, t- + 9
~ ((H) done false Aoest c -00
Me.... (+h....t
óqq y) and Lxx, y). ii. For the remain- ing n queries, flip q s bits (coordinates) one by one and compute the corresponding directional derivative- one query each + + y). iii. Retain bit flips that maximize the directional derivative D2L(x, y) and revert those otherwise. This, however, still suffers from the (n) complexity of full gradient estimation methods. Further, each query recovers at most one sign bit and the natural question to ask is: can we recover more sign bits per query?
def is_done() return done
def step()
c_len +- [n/2"]
sli+c lenx(i+ 1 #=-1
g(x) 2 gheas:
Gbest < g(s)
Consider the case where all the gradient coordinates have the same magnitude, i.e., let the initial guess Qi have r correct bits and n wrong ones. Instead of flipping its bits sequentially, we can flip them all at once to get 92 = -q- If Dx, y) 2 Dy, L(x, y), then our best guess with n - r correct bits, otherwise qi remains. In either cases, with three queries, we will recover max(r, r) sign bits. One can think of this flip/revert procedure as one of majority voting by the guess's 's coordinates on whether they agree with their gradient sign's counterparts. To see this, let 19 1 for all then the condition Dy L(x. y) 2 Dq, L(x, y) can be written as n - r 2 +
else:
slitc_len (ine_eenntt))))]eeen) *=-1
1, and
increment i if
2h:
i + 0, increment h h == [loga(m) +
retain 92
done +- true
def get current Sign_estimatell
return s
2 2r. If the agree votes are less than half of the total votes n, then qe is retained. Besides flipping all the coordinates, one can employ the same procedure iteratively on subset (chunk) of the coordinates [gj..... Lj+n;] of the guess vector q. recovering max(r,, M4 rT)) sign bits, where n, and r, is the length of the ith chunk and the number of its correct signs, respectively.
While the magnitudes of gradient coordinates may not have the same value assumed in the previous example; through empirical evaluation (see Appendix F), we found them to be concentrated. Consequently and with high probability, their votes retaining reverting chunks of sign flips weighted (by their corresponding gradient magnitude) similarly. That said, if we are at a chunk where the distribution of the gradient coordinate magnitudes is uniform, then the flip/revert procedure could favor recovering few sign coordinates with large magnitude counterparts over many sign coordinates with small magnitude counterparts. From our experiments on the noisy FGSM, this still suffices to generate adversarial examples: an attack with 30% correct sign bits (that correspond to the top gradient coordinates magnitudes) is more effective than an attack with 50% correct arbitrary sign bits as shown in Figure 1. Put differently, we would like to recover as many sign bits as possible with as few queries as possible. However, we can only recover few, they should be those that correspond to coordinates with large gradient magnitude. This notion is in line with the flip/revert procedure.
We employ the above observation a divide-and-conquer search which we refer to as S gnHutter. As outlined in Algorithm 1, the technique starts with an initial guess of the sign vector qi (s in Al Algorithm 1). It then proceeds to flip the sign of all the coordinates to get a new sign vector q2.
4

---

Published conference paper at ICLR 2020
and revert the flips if the loss oracle returned a value L(x + +622.9) (or equivalently the directional derivative less than the best obtained so far T(x: + 5), S gnnuutter applies the same rule to the first half of the coordinates, the second half, the first quadrant, the second quadrant, and so on. sign flips to complete its
For search space of dimension n, Si inHunterr needs 2[log(x)+1] search. If the query budget is not exhausted by then, one can update x with the recovered signs and restart the procedure at the updated point with a new starting code s. If we start with sign vector whose Hamming distance to the optimal sign vector q' is n/22: agreeing with q" in the first half of coordinates. In this case, S gnHunter needs just four queries to recover the entire sign vector independent of n, whereas the sequential bit flipping still require + queries. In the next theorem, we show that Si Signutterr er is guaranteed to perform at least as well as FGSM with ((n) oracle queries. Up our knowledge, no such guarantees exist for any black-box attack from the literature.
Theorem 1. (Optimality of si gnHunt er) Given 2 [og(n)+1) queries and that the directional deriva- tive is well approximated by the finite -nite--ifferenc (Eq. 1). SignHunter is at least as effective as FGSM (Goodffell et al., 2015) in crafting adversurial examples.
The proof can be found in Appendix B. Theorem 1 provides an upper bound on the number of queries required for gignuute to recover the gradient sign bits, and perform as well as FGSM. In practice (as will be shown in our experiments), S gmännter crafts adversarial examples with a small fraction of this upper bound. The rationale here is that we do not need to recover the sign bits exactly; we rather need a fast convergence to an adversarially helpful sign vector 8. In our setup, we use the best sign estimation obtained estimation approaches often employ an iterative scheme of T steps within the perturbation ball Bp (z, c). calling the gradient estimation routine in every step leading to search complexity of n.' Instead, our gradient sign estimation routine runs at the top level of our adversarial example generation procedure. Further, Si Signuttte e amenable parallel hardware architecture and has a smaller memory footprint (just sign bits) and thus can carry out attacks in batches more efficiently. Crafting black-box adversarial attacks with SignHuntez e is outlined in Algorithm 2.
far in similar fashion to FGSM, whereas full- mull-gradient
Algorithm 2 Black-Box Adversarial Example Generation with SignHunter
4 EXPERIMENTS
Dinis: input to be perturbed. yiout Wa 's true label, Bp(.,c) fp perturbation ball of radius
We evaluate S SignHunter and compare it with established al- gorithms from the literature: ZO-SignSGD Liu et al. (2019), NES Ilyas et al. (2018), and Banditstp Ilyas et al. (2019) in terms of effectiveness in crafting (without loss of generality) untargeted black-box adversarial examples. To highlight Signäunter's adaptive query construction, we introduce variant of Algorithm 2, named Rand. At every iteration, Rand's sign vector is sampled uniformly from H. Both foc and la threat models considered on the MNIST, CIFARIO. and IMAGNNET datasets. Code and data for the experiments can be found at https: / /bit..itt//tt 1y/ BacIHoq
L loss function of the model under attack
8 + set finit--iifferene probe to perturbation bound
2: I, +- Dinit
3: Define the function g as
g(q) = [ (xo + +qq), (innt) - L(xoo Firsi)) )
5
4: S gnnunttr.iini(g)
5: //C(-) returns top class
6: while C(x) yinat do
7: signHunter.stepl
8: s <- Swgntunter.ger_ccumm couurent_siinesttiieee
9:
x +- B (Ro + 5s)
10:
if SignHunter.is _dneee then
11: To + x
12: Define the function g as in Line 3 (with x. update)
13:
SignHunter.inin
14: return
Experiments Setup. Our experiment setup is similar to (llyas et al., 2019). Each attacker is given a budget of 10, 000 oracle queries per attack attempt and is evaluated on 1000 images from the test sets of MNIST, CIFAR10, and the validation set of IMAGENET. We did not find a standard practice for setting the perturbation bound For the fxr threat model, we use (Madry et al., 2017)'s bound for MNIST and (Ilyas et al., 2019)'s bounds for both CIFARIO and IMAGENET. For the lo threat model, (Ilyas et al., 2019)'s bound is used for IMAGENET. MNIST's bound is set based on the sufficient distortions observed in (Liu et al.,
'That is, replace Line 8 in Algorithm 2 by 8 ~ (H)).
5

---

Published conference paper ICLR 2020
1340
Wevergg + queeree
200
suocess Fate
ShocesS Tole
SHOCCSO rate
(a) MNIST foc
(h) CIFARIO 8oo
(c) IMAGENET 830
1310
1.400
AUrevo rale
SUCEEAA rate
SHOORAS rale
(d) MNIST 2
(c) CITARIO &
(I) IMAGENET 82
Figure 2: Performance black-bor attacks in the lo and lz perturbation constraint. The plots show the average number of queries used per successful image for each attack when reaching specified success rate.
2019), which smaller than the used in (Madry et al., 2017). We the observed bound in (Cohen et al., 2019) for CIFARIO. We show results based on standard models-i.e., models that are not adversarially hardened. For MNIST and CIFARIO. 10, the naturally trained models from (Madry et al., 2017)'s MNIST and CIFAR 10 challenges are used. For IMAGNETT, TensorFlow's Inception (v3) model is used. The loss oracle returns the eross-entropy loss of the respective model. See Appendix C for other general experimental setup details.
Hyperparameters Setup. While Si Signterter does not have any hyperparameters, to fairly compare it with the other algorithms, we tuned their hyperparameters starting with the default values reported by the corresponding authors. The finite difference probe 8 for S gnHunter set the perturbation bound as it is used for both computing the finite difference and crafting the adversarial examples- see Line 1 in Algorithm This tuning-free free aspect of Si signnunter offers a robustness advantage over algorithms which require expert hypertuning, Details on the hyperparameter setup are available in Appendix C.
Table 1: Summary of attacks effectiveness CIFARIO under foc and & perturbation constraints, and with a query limit of 10, 000 queries. The Failure Rate E [0, 1] column lists the fraction of failed attacks over 1000 images. The Avg. # Queries column reports the average number of queries made to the loss oracle only over successful attacks.
Failure Rate
Avg. Querles P...
R..
Fg
fg
Attack
Bandi
0.95
0.39
432.24
1201.85
NES
0.67
312.57
Sand
0.20
0.89
422.16
1018.17
SignBunter
0.07
0.21
121.00
205 20Sign
0.37
0.80
161.22 28
528.35
Results. Figure 2 shows the trade-off between the success (evasion) rate and the mean number of queries (of the successful attacks, per convention) needed to generate an adversarial example for the MNIST, 1IFAR10, and IMAGENET classifiers under the &o and f, perturbation constraints. These plots indicate the average number of queries required for a desired success rate. Table represents a tabulated summary of plots (b) and (c) of Figure 2.5 We observe the following: For any given success rate, $ SignHunter dominates the previous state of the art approaches in all settings except the IMAGENET & setup, where Bandi t.s shows better query efficiency when the desired success rate is roughly greater than 0.35. This is all the more remarkable because Banditsmi
$ 'More tabulated summaries of these plots can be found in Appendix D-Talles 7-9. We also plot the classifier's loss and the gradient estimation quality (in terms Hamming distance and cosine similarity) averaged over all the images as a function of the number of queries in Figures 4 6 of Appendix D.

---

Published conference paper at ICLR 2020
exploits tiles, a clta--dependent prior, searching over 50 50 3 dimensions for IMAGENET, while s gnHutter searches over the explicit data 299 x 299 x 3 dimensions: 36x more dimensions.
So vs. l Perturbation Threat. In view of Bandi t.s 's advantage, Signuuteer is remarkably efficient in the &or setup, achieving a 100% evasion using- on average-jun 12 queries per image against the MNIST classifier! In the l2 setup, SignHunter's performance degrades- it still outperforms the other algorithms. This is expected, since gi.nteer perturbs all the coordinates with the same magnitude and the &g perturbation bound c9 for all the datasets in our experiments is set such that <2/ yn is significantly less than the fee perturbation bound 6,c- Take the case of MNIST (n = 28 x 28), where 6 = 0.3 and E2 = 3. For S SignHuntrr, the E2 setup is equivalent to So perturbation bound of 28 zs 0.1. The employed f2 perturbation bounds give the state of the continuuuu optimization based- approaches more perturbation options. For instance, it is possible for NES to perturb just one pixel in an MNIST image by a magnitude of 3; two pixels by magnitude of 3/v R 2.1 each; ten pixels by a magnitude of 3/VI0 Rs 0.9 each, etc. On the other hand, the binary optimization view of Si SignHunter limits it to always perturb all 28 x 28 pixels by magnitude of 3/28 = 0.1. Despite its fewer degrees of freedom, SignHunte er maintains its effectiivnness in the lg setup. The plots can also be interpreted as a sensitivity assessment of S SignHenter as gets smaller going from foo to the lg perturbation threat.
SignHunter vs FGSM. The performance of S SignHunter is in line with Theorem I when com- pared with the performance of FGSM (the noisy FGSM at k: = 100% in Figures 1 and of Appendix A) in both 2 and lg setups across all datasets. For instance, FGSM has a failure rate of 0.32 for CIFARIO l2 (Appendix A, Figure (b)), while SignHunter achieves a failure rate of 0.21 with 692.39 < 2n- 2 x 3 x 32 x 32 = 6144 queries (Appendix D. Table 8). Note that for IMAGENET, SignHunter er outperforms FGSM with a query budget of 10, 000 queries, a fraction of the theoretical number of queries required 2n 536, 406 to perform at least well. Incorporating S SignHunter in an iterative framework of perturbing the data point æ till the query budget is exhausted (Lines 10 to 14 in Algorithm 2) supports the observation in white-box settings that iterative FGSM Projected Gradient Descent (PGD)-is is stronger than FGSM (Madry et al., 2017; Al-Dujaili et al., 2018). This evident by the upticks in SignHunter's performance on the MNIST l2 case (Appendix D, Figure 4), which happens after every iteration (after every other 2 x 28 x 28 queries).
Gradient Estimation. Plots of the Hamming similarity capture the number of recovered sign bits, while plots of the average cosine similarity capture the value of Eq. 2. Both SignHunter and Bandit ModitsTD consistently optimize both metrics. In general, Sign.Hunter (Bandit con- verges faster especially on the Hamming(cosine) metric as it is estimating the signs(signs and magnitudes) compared to Banditsrp's full gradient (S (SighHunter's gradient sign) estimation. This is most obvious in the IMAGENET & setup (Appendix D, Figure 6). Note that once attack is successful, the estimated gradient sign at that point is used for the rest the plot. This explains why, in the for settings, Si gnHnter's 'ss plot does not improve compared to its lg counterpart, as most of the attacks are successful in the very first few queries made to the loss oracle and no further refined estimation is required. Another possible reason is that the gradient direction can be very local and does not capture the global loss landscape compared to sighHunter" estimation. More on this is discussed in Section 6.
Si gnnuntter er vs. Rand. Given these results, one could argue that SignHunter is effective, because it maximally perturbs datapoints to the vertices of their perturbation balls. 6 However, Rand's poor performance does not support this argument and highlights the effectiveness of SignHutter r r's adaptive query construction. Except for MNIST and CIFARIO E.x settings, Rand performs worse than the full full-gradient estimation approaches, although it perturbs datapoints similar to Si signunnter er. Overall, Si signHunter 3.8x less failure-prone than the state-of-the-at approaches combined, and spends over all the images (successful and unsuccessful attacks) 2.5x less queries."
5 SIGNHUNTER VS. DEFENSES
To complement Section 4, we evaluate i gnHunter r against adversarial training, way to improve the robustness of DNNs (Madry et al., 2017). Specifically, we attacked the secret models used
'We define perturbation vertices as extreme points of the ball Bp( e). That is, x + coo, where 6oc = when p = oo and c.2 = </vī when =
The number of queries spent computed based on Tables 7-9 Appendix as (1 rate) + avg queries fail rate 10, 000.
7

---

Published conference paper at ICLR 2020
in public challenges for MNIST and CIFARIO. For IMAGENET, we used ensemble adversarial training, a method that argues security against black-box attacks based on transferability Tramèr et al. (2017a). Appendix E reports the same metries used in Section 4 as well as a tabulated summary for the results discussed below.
Public MNIST Black-Box Attack Challenge. In line with the challenge setup, 10, 000 test images were used with an lo perturbation bound of e = 0.3. Although the secret model is released, we treated it as a black box similar to our experiments in Section 4. No maximum query budget was specified, we set it to 5, 000 queries. This is equal to the number of iterations given to a PGD attack in the white-box setup of the challenge: 100-steps with 50 random restarts. SignHunter' attacks resulted in the lowest model accuracy of 91 11.4%, outperforming all the submitted attacks to the challenge, with an average number of queries of 233 per successful attack. Note that the attacks submitted to the challenge are based on transferability and do not query the model of interest. On the other hand, the most powerful white-box attack by Wang et al. (2018)-as of May 15, 2019-resulted in a model accuracy of 88. 42% Further, a PGD attack with 5, 000 back-prop pack-propagations achieves 89. 19.62% in contrast to SignHunter's 47% with just 5, 000 forward- proppgatiios.
Public CIFARIO Black-Box Attack Challenge. This challenge setup is similar to the above, but with an for perturbation bound of 8. SignHutter" es's attacks resulted in the lowest model accuracy of 47. 47.16%, outperforming all the submitted attacks to the challenge, with an average number of queries of 569 per successful attack. Similar to the MNIST challenge, all the submitted attacks are based on transferability. On the other hand, the most powerful white-box attack by Zheng et al. (2018)-as of May 15, rosueeselleed in a model accuracy of 44.71% Further, PGD attack with 200 Back-propagations achieves 35.21% in contrast to S SignHunter's 47.16% with 5, 000 forward paoaadddpppggtions...
Ensemble Adversarial Training on IMAGENET. In line with Tramèr et al. (2017a), we set e = 0.0625 and report the V3 enst model's misclassification over 10,000 random images from IMA- GENET's validation set. After 20 queries, s i gnHunter achieves a top-1 error of 40.61% greater than the 33.4% rate of a series of black-box attacks (including PGD with 20 iterations) transferred from a substitute model. With 1000 queries, SignHunter breaks the model's 's robustness with a top-1 error of 90.75%!
CHARACTERIZING ADVERSARIAL CONES WITH SIGNHUNTER
Estimating the size of adversarial cones, the space of adversarial examples in the vicinity of a point, for model has been a topic of interest by the machine learning community Tramèr et al. (2017a); Ma et al. (2018); Lu et al. (2018). The Gradient- -Alignd Adversarial Subspace (GAAS) method Tramèr al. (2017b) provides an approximation of the adversarial cone dimensionality by finding a set of orthogonal perturbations of norm that are all adversarial with respect to the model. By linearizing the model's 's loss function, this reduced to finding orthogonal vectors that are maximally aligned with its gradient g'-or its gradient sign q" in the loo setup Tramèr et al. (2017a). In Figure 3, we reproduce (Tramèr et al., 2017a, Fig. 2) and show that aligning the orthogonal vectors with Si SignHunter's estimation (we refer to this approach as SAAS) instead of aligning them with the gradient (CAAS) results in a better approximation of the adversarial cone for the two IMAGENET models considered earlier, even when the number of queries given to S SignHunter is just a fraction of the dimensionality n. Through its query-efficient finite-difference sign estimation, S gnnnterr is able to quickly capture the larger-scale variation of the loss landscape in the point's neighhorhood, rather than the infinitesimal point-wise variation that the gradient provides, which can be very local. This is important in adversarial settings, where the loss landscape is analyzed in the vicinity of the point Moosavi-Dezfooll et al. (2018), 20: Tramèr et al. (2017a). One interesting observation at A: = 1 (note here, r1 = q²)) across all c is that CAAS finds adversarial directions for fewer points against the v3 model than the naturally trained model v3, whereas SAAS reports similar probability of adversarial directions for both. This contrast suggests that ensemble adversurial training Tramèr et al. (2017a) still exhibits the gradient masking effect, where the gradient poorly approximates the global loss landscape.
7 CONCLUSION
Assuming black-box threat model, we studied the problem of generating adversarial examples for neural nets and proposed the gradient sign estimation problem as the core challenge in crafting

---

Published conference paper at ICLR 2020
(a) c 1/255
(b) c 10/255
(c) < 16/255
v3-GAAS
Prolabiltt
v3-SAAS
v3
GAAS
0.5
SAAS
Figure Two estimations of the lo adversarial cones for two IMAGENET models: v3 and Vadv-ens- The first estimation (GAAS: Cradient-Aligned Adversarial Subspace) finds k orthogonal vectors maximally aligned with the gradient sign q" Tramèr al. (2017a). The second (SAAS: Adversarial Subspace) finds k orthogonal vectors that are maximally aligned with SignHunter's 8 (Algorithm 2, Line 8) after 1, 000 queries. Similar to (Tramèr et al., 70, Figure 2), for 500 correctly classified points and e {4, 10, 16), we plot the probability that find at least it orthogonal vectors T. comppteed based on (Tramèr et al., 2017a, Lemma 7)-such and æ + is misclassified. For both models and for the same points æ. SAAS finds
SonHunter-AAlggne
that ||r:||<< more orthogonal adversarial vectors т; than GAAS, thereby providing a better characterization of the space of adversarial examples in the vicinity of point, albeit without white-box access to the models.
these examples. We formulate the problem as binary black-box optimization one: maximizing the directional derivative in the direction of {=1}" vectors, approximated by the finite difference of the queries' loss values. The separability property of the directional derivative helped us devise s sighuutter, a query-efficient, tuning-free divide-andd-conuerr algorithm with a small memory footprint that is guaranteed to perform at least well as FGSM after (n)) queries. No similar guarantee is found in the literature. In practice, SignHunter needs a mere fraction of this number of queries to craft adversarial examples. The algorithm one of its kind construct adaptive queries instead of queries that are based on i.i.d. random vectors. Robust to gradient masking, S SignHunter can also be used to estimate the dimensionality of adversarial cones. Moreover, S SignHunte ex achieves the highest evasion rate on two public black- box attack challenges and breaks a model that argues robustness against substitute- modell attacks.
ACKNOWLEDGMENTS
This work supported by the MIT-IBM Watson AI Lab. We would like thank Shashank Srikant for his timely help. We are grateful for feedback from Nicholas Carlini and Zico Kolter.
REFERENCES
Ahdullah Al-Dujaili, Alex Huang, Erik Hemberg, and Una-May O'Reilly. Adversarial deep learning for robust detection of binary encoded malware. In 2018 IEFE Security and Privacy Workshops (SPW). pages 76-82. IEEE, 2018
Jeremy Bernstein, Yu- fi-niang Wang, Kamyar Azizzadenesheli, and Animashree Anandkumar. signSGD: Com- pressed optimisation for non-convex problems. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learn- ing Research, pages 560-569, Stockholmsmässan, Stockholm Sweden, 10-15 Jul 2018. PMIR. URI. http:/ /t i inginn..... press/ v80 wtt.///eeeeetteeeneeneeee htmm.
Arjun Nitin Bhagoji, Warren He, Bo Li, and Dawn Song. Exploring the space black-box attacks on deep neural networks. arXiv preprint arXiv:1712.09491, 2017.
Battista Biggio and Fabio Roli. Wild patterns: Ten years after the rise of adversarial machine learning. Pottern Recognition, 84:317-331, 2018
Battista Biggio, Igino Corona, Davide Maiorca, Blaine Nelson, Nedim Šındić, Pavel Laskow, Giorgio Giacinto, and Fabio Roli. Evasion attacks against machine learning at test time. Joint European conference on machine learning and knowledge discovery in databaxes, pages 387-402. Springer, 2013.
Nicholas Carlini and David Wagner. Towards evaluating the robustness neural networks. In 2017 IEEE Symposium on Security and Privacy (SP), pages 39-57. IEEE, 2017.

---

Published conference paper at ICLR 2020
Pin- Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsich. Zoo: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models. In Proceedingy of the 10th ACM Workshop on Artificial Intelligence and Security, pages 15-26. ACM, 2017.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. arXiv: D.K.:::9022029988// 2019.
Ian Goodfellow. Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In International Conference on Learning Representations, 2015. URL http: httttp://axxv.oore wwg. /aaeg///////// 1422 6572.
Chuan Guo, Jacob R Gardner, Yurong You, Andrew Gordon Wilson, and Kilian Q Weinberger. Simple black-box adversarial attacks. arXiv preprint arXiv:9905.07/22 2019, 2019.
Jamie Hayes and George Danezis. Machine learning an adversarial service: Learning Mack-box adversarial examples. CoRR, abs/1 708.05201, 2017.
Elad Hazan, Adam Klivans, and Yang Yuan. Hyperparameter optimization: A spectral approach. arXiv preprint arXiv: 00764, 2017.
Andrew llyas, Logan Engstrom, Anish Athalye, and Jessy Lin. Black-box adversarial attacks with limited queries and information. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 2137- 2146, Stockholmsmässan. Stockholm Sweden, 10-15 Jul 2018. PMLR. URL http:/ http::::/p/cceedigg... mlr. press/ v80 ilyasl8a Baa. html.
Andrew llyas, Logan Engstrom, and Aleksander Madry. Prior convictions: Black-box adversarial attacks with bandits and priors. In International Conference on Learning Representations, 2019. URL https: WhR5K/.
// /pppeneeview..occ//mm/
Alexcy Kurakin, Ian Goodfellow, and Samy Bengio. Adversarial machine learning at scale. 2017. URL https: / /arxiv...vvv. org/ hltg/bbb//1...../ 1w111111111111111 01236.
Sijia Liu, Pun-Yu Chen, Xiangyi Chen, and Mingyi Hong. signSGD via zeroth-order oracle. In Interna- tional Conference on Learning Representations, 2019. URL
BJe-DsC5Fm.
Yanpei Liu, Xinyun Chen, Chang Liu, and Dawn Song. Delving into transferable adversarial examples and black-box attacks. arXiv preprint arXiv: /6/ 1.02770, 2016.
Pei-Hsuan Lu, Pin-Yo Chen, and Chia-Mu Yu. On the limitation of local intrinsic dimensionality for characteriz- ing the subspaces of adversarial examples. arXiv preprint 1xXiv:880300666 2018
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. arXiv preprint I /80100263,, 2018
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant adversarial attacks. arXiv preprint 706.v:/706.06083, 2017.
Seungyong Moon, Gaon An, and Hyun Oh Song. Parsimonious black-box adversarial attacks via efficient combinatorial optimization. arXiv preprint 1rXiv:1905.066: 2019.
Seyed-Mohsen Moosavi-Dezfooli, A Alhussein Fawzi, and Pascal Frossard. Deepfool: simple and accurate method to fool deep neural networks. In Proceedings the IEEE Conference Computer Vision and Puttern Recognition, pages 2574-2582, 2016
Seyed-Mohsen Moosavi-Dezfooli, Alhussein Fawzi, Jonathan Uesato, and Pascal Frossard. Robustness via curvature regularization, and vice versa. arXiv preprint arXiv:1811.09716, 2018.
Nina Narodytska and Shiva Prasad Kasiviswanathan. Simple black-box adversarial attacks on deep neural networks. In CVPR Workshops, volume 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, pages (06-519. ACM, 2017.
Adi Shamir, Itay Safran, Eyal Ronen, and Orr Dunkelman. simple explanation for the existence of adversarial examples with small hamming distance. arXiv preprint arXiv:1901.1086/ 2019.
10

---

Published conference paper ICLR 2020
Florian Tramèr, Alexey Kurakin, Nicolas Papernot, Ian Goodfellow, Boneh, and Patrick McDaniel. Ensemble adversarial training: Attacks and defenses. arXiv preprint urXiv:1705.07200% 2017a.
Plorian Tramèr, Nicolas Papernot, Goodfellow, Dan Boneh, and Patrick McDaniel. The space of transferable adversarial examples. arXiv preprint 1xiv:1704.03455. 2017b.
Chun-Chen Tu, Paishun Ting, Pin-Y Chen, Sijia Liu, Huan Zhang, Jinfeng Yi, Cho-Jui Hsich, and Shin-Ming Cheng. Autozoom: Autoencoder-based zeroth order optimization method for attacking black-box neural networks. arXiv preprint 18:::::888511111 2018.
Shiqi Wang. Yizheng Chen, Ahmed Abdou, and Suman Jana. Mixtrain: Scalable training of formally robust neural networks. arXiv preprini arXiv:181I.0262. 2018.
Chaowei Xiao, Bo Li, Jun-Yan Zhu, Warren He, Mingyan Liu, and Dawn Song. Generating adversarial examples with adversarial networks, 2018. URL ht /pwpre/iieeeeeeeeeeeeeeeme. net www.:nne/fofmmiccommmom wwrfooomiiio...m...oo hi-erummiiid--kyychhhh---
Yun-Bin Zhao. Sparse optimization theory and methods. CRC Press, an imprint of Taylor and Francis, Boca Raton, FL. 2018. ISBN 078-1138080942
Tianhang Zheng, Changyou Chen, and Kui Ren. arXiv: 080800557 2018.
Distributionally adversarial attack.
arXiv preprint
APPENDIX A. NOISY FGSM
This section shows the performance of the noisy FGSM on standard models (described in Section 1 of the main paper) on the MNIST, CIFARIO and IMAGENET datasets. In Figure 4, consider the & threat perturbation constraint. Figure reports the performance for the setup. Similar to Ilyas al. (2019), for each & in the experiment, the top pereent of the signs of the coordinates chosen either randomly (random-k) or by the corresponding magnitude (x y) /0 (top-k) are set correctly, and the rest are set to -1 or +1 at random. The misclassification rate shown considers only images that were correctly classified (with no adversarial perturbation). In accordance with the models' accuracy, there were 987, 962, and 792 such images for MNIST, CIFAR10, and IMAGENET of the sampled 1000 images, respectively. These figures also as validation for Theorem of the main paper when compared gnHunter performance shown in Appendix D.
XPC
MINIST
1697
46%
2l 0%
CIFATUDO
55%
18%
2% OF A0L
IMAGENET
100
(b)
Figure 4: Misclassification rate of three neural nets (for (a) MNIST, (b) CIFARIO, (c) IMAGENET. respectively) on the noisy FGSM's adversarial examples as a function of correctly estimated coordinates of on random 1000 images from the corresponding evaluation dataset, with the maximum allowed oo perturbation being to 0.3, 12, and 0.05, respectively. Across all the models, estimating the sign of the top 30% gradient coordinates (in terms of their magnitudes) is enough to achieve misclassificatio of ~ 70%. Note that Plot (c) is similar to llyas et al. (2019)'s Figure 1, but is produced with TensorFlow rather than PyTorch.
sign (æ, y])

---

Published conference paper ICLR 2020
0.30
jun
percous MNISE cocedimates
k pereent CIEARIO coordiutess
perent of IMAGENET coordinates
(a)
(b)
(c)
Figure 5: Misclassification rate of three neural (for (a) MNIST, (b) CIFARIO. and (c) IMAGENET, respectively) on the noisy FGSM's adversarial examples function correctly estimated coordinates of sign( (xx y)) on random 1000 images from the corresponding evaluation dataset, with maximum allowed f2 perturbation being set to 3, 127, and 5, respectively. Compared to Figure 4, the performance on MNIST and CIFARIO drops significantly.
12

---

Published conference paper ICLR 2020
APPENDIX B. PROOFS FOR THEOREMS IN THE MAIN PAPER
this section, we present proof Thenrem Section 3. Note the thenrem makes the assumption that the finite difference is good approximation of the directional derivative. This assumption has been the core concept behind most of the black-box adversarial attack algorithms and we state it here for completeness.
Theorem 1. (Optimality of SignBunter ex) Given 2 2og(n)-11 queries and that the directional derivative is well approximated the fiittedifference (Eq. 1 the main paper). SignHuntes er is least effective as PGSM (Goodfellow al., 2015) in crafting adversarial examples.
Proof. Based on the separability property of the directional derivative, the ith coordinate of the gradient sign vector can be recovered as follows: construct two binary codes and v such that only their ith bit is different. Therefore, we have
us DuL DoL(x.y).
2. = sign(gi)
otherwise
From the definition of SignHuntez, this is carried out for all the coordinates after 2 20og())+1] queries. Put it differently, after [og(m)++1] queries, SignHunter has flipped every coordinate alone recovering its sign exactly as shown in Eq. 4 above. Therefore, the gradient sign vector is fully recovered, and one can employ the F FGSM attack to craft adversarial example. Note that this is under the assumption that finite difference approximation rank- munk-reserringg.
directional derivative (Eq. the main paper) good enough (or at least
13

---

Published conference paper at ICLR 2020
APPENDIX C. EXPERIMENTS SETUP
This section outlines the experiments setup. ensure a fair comparison among the considered algorithms, we did our best in tuning their hyperparameters. Initially, the hyperparameters were set to the values reported by the corresponding authors, for which we observed suboptimal performance. We made of synthetic concave loss function to efficiently tune the algorithms for each dataset perturbation constraint combination. The performance curves on the synthetic loss function using the tuned values of the hyperparameters did show consistency with the reported results from the literature. For instance. we noted that 20-S Si SignSGD converges faster than NES, and that Banditsr2 SyD outperformed the rest of the algorithms towards the end of query budget. Further, in adversarial examples generation experiments, we observed failure rate and query efficiency in line with the algorithms' corresponding papers e.g., compare the performance Bandi tSDD and NES in Table 9 of Appendix with (Ilyas et al., 2019, Table 1). That said, we invite the community to provide their best tuned attacks.
Note that ginniutter does not have any hyperparameters to tune. The finite difference probe ó for SignHunter is to the perturbation bound it is used for for both computing the finite difference and crafting the adversarial examples see Line in Algorithm 2 of the main paper. This tuning-free free setup of $1 Hnngtttee e offers a robust edge over the state-of-the-art black-box attacks, which often require expert knowledge to carefully tune their parameters.
Table 3 describes the general setup for the experiments. Table lists the sources of the models we attacked in this work. while Tables 4, 5, 6, and outline the algorithms' hyperparameters. Figure 6 shows the performance of the considered algorithms on a synthetic concave loss function after tuning their hyperparameters. All experiments were run on CUDA-cnabled NVIDIA Tesla V100 16GB.
A possible explanation of S gnHunter's superb performance is that the synthetic loss function is well-hehaved in terms of its gradient given an image. That is. most of gradient coordinates share the same sign, since pixels tend have the SignHunter will recover the true gradient sign with as few queries as possible (recall the example in Section of the main paper). Morcover, given the structure of the synthetic loss function, the optimal loss value is always at the boundary of the perturbation region; the boundary is where SignHunter samples its perturbations.
values and the optimal value for all the pixels is the same @mis -wess Thus,
Table 2: Source of attacked models.
Model
Source
MNIST models
suspas Feghauu Hadey andat, Lange
CIFAR 10 models
sespas /tgueuuu
IMAGENET- v3 model
IMAGENET vaav csst model
p e dy/borees
Table 3: General setup for all the attacks
Value MNIST
CIFARIO
IMAGENET
foc
82
8/
Ex
82
Parameter
e (allowed perturbation) Max allowed queries Evaluation/ Test set size Data (pixel value) Range
0.3
3
12
127
0.05
5
10000
1000
10,11
[0,255]
[0.1]
Table 4: Hyperparameters setup for NES
Value MNIST
CIFARIO
IMAGENET
fox 1/2
fx
Foo
f
Hyperparameter
(linkke difference probe)
9 (image lessning rate)
9 (oumber of finite difference estimations per stap)
10
20
20
100
50
14

---

Published conference paper ICLR 2020
Table 5: Hyperparameters setup for 20-Si
Value MNIST
CIFARIO
IMAGENET
b
5x
6
Hyperpurameter
(lintte genihe)
y (imago q tnumber of fimile dillerence extimtiins per step)
20 20
100
Table 6: Hyperparameters setup for Banditstp
Value MNIST
CIFARIO
IMAGENET
Es
Hyperparanderr
finage learning
0.03
0.01
5
12
001
0.1
(inite difference probe)
0.1
2.55
2.55
0.1
(culine optisizatiin leaming
0.001
0.0001
0.001
1e405
00001
dependent
10
explonaion)
Table 7: Hyperparameters setup for s Signunnter
Value MNIST t
CIFARIO
IMAGENET
800
8
t
Hy pyperaarreeeer
ó (finite difference probe)
0.3
3
12
127
0.05
5
100
to) MINIST Eoo
MNIST 2o
2.15
2117
1.10
1.37
(c) CHEARIO Coc
(E CIFARIB ES
-50K0
-2200
-3300
20631
450
66 IMMMGEEET E...
IB IMAGENET
Figure 6: Tuning testhed for the attacks. A synthetic loss function was used to tune the performance of the attacks over a random sample of 25 images for each dataset and É, perturbation constraint. The plots above show the average performance of the tuned attacks the synthetic loss function L(x, y) = -( x*)²(( (x x"), where x" Zmin =mmaz using a query limit of 1000 queries for each image. Note that in all, Banditsyu outperforms both NES and Z0-SignSGD. Also, observe the same behavior reported by Liu et al. (2019) on the fast convergence of Z0-SignSGD compared to NE.S. We did not tune SigHunter:: it does have any tunable parameters.
15

---

Published conference paper ICLR 2020
APPENDIX D. RESULTS OF ADVERSARIAL BLACK-BOX EXAMPLES GENERATION
This section shows results of our experiments in crafting adversarial black-box examples standard models in the form of tables and performance traces, namcly Figures 7, and and Tables and 10.
Table 8: Summary of attacks effectiveness MNIST under to and & perturbation constraints, and with a query limit of 10, 000 queries. The Failure Rate E [0, 1] column lists the fraction of failed attacks over 1000 images. The Avg. # Queries column reports the average number of queries made the loss oracle only over successful attacks.
Failure Rate
Avg. @ Queries Ex.
Attack
Banditayp
0.68
0.59
673.16
NRS
0.63
0.63
235.07
361 .62.42
0.33
SignRunter
0.00
0.04
11.06
1064.22
2DSignaCD
0.63
157.00
881.08
Table 9: Summary of attacks effectiveness on CIFAR10 under &oo and &g perturbation constraints, and with a query limit of 10, 000 queries. The Failure Rate E [0, 1] column lists the fraction of failed attacks over 1000 images. The Avg. # Queries column reports the average number of queries made to the loss oracle only over successful attacks.
Failure
Avg. Queries Ez
8so
Ex
Eoo
Attack
Sandicsyp
0.95
0.31
432.24
12011.85
Rand
0.20
0.89
422.16
1018.17
Rumber
0.07
0.21
121
892.39
2081 gm.c0
0.37
0.80
161.28
528.35
Table 10: Summary of attacks effectiveness on IMAGENET under foo and l perturbation constraints, and with a query limit of 10, 000 queries. The Failure Rate E [0, 1] column lists the fraction of failed attacks over 1000 images. The Avg. # Queries column reports the average number of queries made to loss oracle only over successful attacks.
Fuilure Rate
Avg. Queries fg
Fo..
Fa
f.u.
Banditagg
0.07
0.11
1010.06
1635.55
Rand
0.72
0.93
658.77
418 02
er
0.02
0.23
578.56
1985.55
20S1 gnSCD
0.23
0.52
1054.98
931.15
16

---

Published conference paper ICLR 2020
3030
4008
5246
0000
30393
2000
3300
6330
8000
38033
QU01ee
Tomaingg sialbarity
dimilrrty
6.344
0.313
8.311
sbalurtt
cosiige sigularity
0.94
0.33-
0.15
2331
200
1993
2.40
20.0
1003
3391
100
quorries
Queries
0.2
089
1200
5000
6230
38093
300
Bascktarp
average qpertes
80c
400
stacco0 tile
SHINNIS zale
Figure 7: Performance curves of attacks on MNIST for Eoo (first column) and l (second column) perturbation constraints. Plots of Avg. Loss row reports the loss a function of the number of queries averaged over all images. The Avg. Hamming Similarity row shows the Hamming similarity of the sign of the attack's estimated gradient ğ with true gradient's 's sign q", computed as 1 - [[sig((ğ) q || and averaged over all images. Likewise, plots of the Avg. Cosine Similarity row show the normalized dot product of ğ and g* averaged over all images. The Success Rate row reports the attacks' cumulative distribution functions for the number of queries required to carry out successful attack up to the query limit 10, 000 queries. The Arg. Queries row reports the average number of queries used per successful image for each attack when reaching a specified success rate: the more effective the attack, the closer its curve to the bottom right of the plot.
17

---

Published conference paper ICLR 2020
2.4
2000
1300
0083
8000
10090
2000
4300
6030
8000
18033
queries
overnge Hannning Stailertt
03322
2.3300
0.0075
00.27
0.24
0.35
0.30
0.33
2331
1093
11002
2340
20.0
1103
100
queries
Qqurice
0..1
0.2
0.3
0.0
1200
6230
1200
ovverage Querce
1000
300
c00
0.2
S1A0C0OI tale
Figure 8: Performance curves of attacks on CIFARIO for Eoo (first column) and &a (second column) perturbation constraints. Plots of Avg. Loss reports the loss function of the number of queries averaged over all images. The Avg. Hamming Similarity row shows the Hamming similarity of the sign of the attack's estimated gradient ğ with true gradient's sign q", computed as 1 - [[sign(ğ) q || and averaged over all images. Likewise, plots of the Avg. Cosine Similarity row show the normalized dot product ğ and g* averaged over all images. The Success Rate row reports the attacks' cumulative distribution functions for the number of queries required to carry out successful attack up to the query limit 10, 000 queries. The Avg. Queries row reports the average number of queries used per successful image for each attack when reaching a specified success rate: the more effective the attack, the closer its curve to the bottom right of the plot.
18

---

Published conference paper ICLR 2020
6.75
0.5
04.0
04.33
3000
1803
$300
5000
10000
2000
3000
6330
6000
39300
Quimees
Sialartt
0.311
0.311
0.922
01:30
0.333
costtue
23.3
1931
1091
1193
2000
2300
1200
1101
9331
1000
Quer3es
# Queriee
1.2
300g 244
0.0
2000
6200
3830
1800
220
SHENNSS PALA
SUCANOS 2ale
Figure 9: Performance curves of attacks on IMAGENET for Eoo (first column) and lg (second column) perturbation constraints. Plots of Avg. Loss row reports the loss as function of the number of queries averaged over all images. The Avg. Hamming Similarity row shows the Hamming similarity of the sign of the attack's estimated gradient ğ with true gradient's 's sign q", computed as 1 - [[sign(ğ) qº || /n and averaged over all images. Likewise, plots of the Avg. Cosine Similarity row show the normalized dot product ğ and g* averaged over all images. The Success Rate row reports the attacks' cumulative distribution functions for the number of queries required to carry out successful attack up to the query limit 10, 000 queries. The Arg. Queries row reports the average number of queries used per successful image for each attack when reaching a specified success rate: the more effective the attack, the closer its curve to the bottom right of the plot.
19

---

Published conference paper ICLR 2020
APPENDIX E. PUBLIC BLACK-BOX CHALLENGE RESULTS
This section shows results of our experiments crafting adversarial black-box examples on adversarially trained models in the form of tables and performance traces, namely Tables 11, 12, 13, and Figure 10.
Table 11: Leaderboard of the MNIST black-box challenge. Adapted from the challenge's website- as of May 15, 2019.
Black-Box Attack
Model Accuracy
SignHunter (Algorithm 2 in the main paper) Xiao et al. (2018)
91.47%
92.76%
PGD against independently adversarially trained copies of the net-
93.54%
work
FGSM on the CW loss for model B from (Tramèr et al., 2017a)
94.36%
FGSM on the CW loss for the naturally trained public network
96.08%
PGD the cross-entropy loss for the naturally trained public network 96.81%
Attack using Gaussian Filter for selected pixels on the adversarially trained public network
97.33%
FGSM the cross-entropy loss for the udversarially trained public
97.66%
network
PGD on the cross-entropy loss for the adversarially trained public net-
97.79%
work
Table 12: Leaderboard of the CIFAR10 black-box challenge. Adapted from the challenge's website of May 15, 2019.
Black-Box Attack
Model Accuracy
SignHunter (Algorithm 2 in the main paper)
47.16%
PGD on the cross-entropy loss for the adversarially trained public net- work
63.39%
PGD the CW loss for the adversarially trained public network
64.38%
FGSM on the CW loss for the adversarially trained public network
67.25%
FGSM on the CW loss for the naturally trained public network
85.23%
Table 13: Top Error Percentage. The numbers between brackets are computed on 10,000 images from the validation set. The rest from (Tramèr et al., 2017a, Table 4).
SignHunter
Model
clean
Max. Black-box
after 20 queries after 1000 queries
v3 Vaavv-ensd
24.2 (26.73)
33.4
(40.61)
(90.75)
20

---

Published conference paper ICLR 2020
Madry's s Lab (MNIST)
Madry's 's Lab (CIFARIO)
Ensemble Adv. Training (IMAGENE))
033
1280
3040
XXX
1030
200
190
300
190
1:71
1.000
50m
3.0
50m
326
4003
1.50
20
-20
68s
1793
3.25
1.000
$.00
3.35
3.65
1200
304
30X
1000
300
X21
2003
650
350
400
1092
0.67
1.00
$..05
10m
34c
1051
3G0
256
46
186
200
1.20
100
230
1520
0.2
1010 2.50
13.0
100 1522
Figure 10: Performance curves of attacks on the public black-box challenges for MNIST (first column), CIFARIO (second column) and IMAGENET (third column). Plots of Avg. Loss row reports the loss as function of the number of queries averaged over all images. The Avg. Hamming Similarity row shows the Hamming similarity of the sign of the attack's 's estimated gradient ğ with true gradient's sign q", computed as (وsigu(~) q" I1 /n and averaged over all images. Likewise, plots of the Avg. Cosine Similarity row show the normalized dot product of ğ and g averaged over all images. The Success Rate row reports the attacks' cumulative distribution functions for the number of queries required to carry out successful attack up to the query limit of 5, 000 queries for MNIST and CIFARIÓ (1, 000 queries for IMAGENTT). The Avg. # Queries of queries used per successful image for each attack when reaching a specified success rate: the more effective the attack, the closer its curve is the bottom right of the plot.
q01
reports the average number
21

---

Published conference paper ICLR 2020
APPENDIX F. HISTOGRAM OF GRADIENT COORDINATES' MAGNITUDES
This section illustrates our experiment on distribution
magnitudes gradient coordinates as sum- marized in Figure 11. How to read the plots: Consider the first histogram in Plot (a) from below; it corre- sponds to the 1000 image from the sampled MNIST evaluation set, plotting the histogram of the values (JaL(w, /)/ isignn where the MNIST dataset has dimensionality [0, 0.002]. Overall, the values are fairly concentrated exceptions. in Plot (e) instance, magnitudes of the 400 image's 's gradient coordinates spread from O to 0.055.
784. These values in the range
MNIST
CIFARIO
IMAGENET
Original Images a
Poriieent coerdinates
Aeralient crardinaaioo
Apralient
gradient cssrlimats magnitale
pratiinn coordinate magnitude
gradient covelinate magnitude
Perturbed Images B az c)
Agralien eveeinatte
Agralient cventinatts
Agralient
grodicnt cosedinate magnitude
gradiest coordinate magaitude
gradient escedinate magnitade
Figure 11: Magnitudes of gradient coordinates concentrated: Plots (a), (b), and (c) show histograms the magnitudes of gradient coordinates of the loss function L(x, y) with respect to the input point (image) æ for MNIST, CIFARIO, and IMAGENET neural net models over 1000 images from the corresponding evaluation set, respectively. Plots (d), (e), (f) show the same but at input points (images) sampled randomly within (x, c):::: the loc -all of radius 0.3, 12, and 0.05 around the images in Plots (a), (b), and (c), respectively.
22

---

Published conference paper ICLR 2020
APPENDIX G. ON SCHEMES FOR SIGN FLIPS
this section, we show the performance of different sign flip schemes comparison to $1 gnHunter. Results are summarized in Figure 12. S Sighuntterr adaptive flips shows clear advantage over other schemes despite having worse upper-bound on the query complexity- e.g., Na i ve retrieve the signs in + 2 queries, as discussed in Section 3.
Hadire
Rand
Rand
Sigräketter
Sigukkrtter
10:0
Cade
MNIST &00
CIFARIO L00
IMAGENET foo
Nedro
aveengg quaeties
Nelve
Fond
Wnvesuee quacto
Rand Signikanter
SBC
SNC
Sigehuntar
Sigelkeeter
Success zate
SUCO0SS rate
success
MNIST &
CIFARIO E
IMAGENET b
Figure 12: Performance of different sign flips patterns for Algorithm 2, Line the foo and & perturbation constraints: proposition (SignHunter), random sign flips (Rand), sequential single sign flips (Naive), stochastic hill climbing (SHC), which is similar to Rand but retain the flip only if is better in terms of the observed model loss. With higher dimensions, SHC is comparable to s gnHunter but does not enjoy a deterministic upper-bound on the query complexity.
23

---

Published conference paper at ICLR 2020
APPENDIX H. SIGNHUNTER AND RECENT RELATED WORK
this section, we discuss recent work related to our proposition.
Parsimonious Black-Box Adversarial Attacks (Moon et al., 2019). Our experiment on the public CIFARIO black-box attack challenge corresponds to [1, Table 1J. The authors report a 48% success rate (52% model accuracy) with an average number of queries of 1261. On the other hand, our proposed algorithm achieves 52.84% success rate (47. 16% model accuracy) with an average number queries 569, Further, (Moon al., 2019, Table 2) corresponds to our results Appendix D, Table 9; the paper reports a 98.5% success rate with an average number of queries of 722. Our proposed algorithm achieves a 98% success rate with 578.56 average number of queries. Based on these numbers, Si gnHunter demonstrates better performance than (Moon et al., 2019)'s attack.
Simple Black-Box Attack (SIMBA) (Guo et al., 2019). The main distinction that SIMBA performs a teraary flip over (-6, 0, +5} for one random single coordinate at an iteration with 5 s e. On the other hand, Si iignnunter er performs a binary flip { {-e, } for group of coordinates at an iteration. Most of Guo et al. (2019)'s experiments were performed for the & perturbation constraint and against models different from those considered in this pxcer-except for the IMAGENET v3 model, which the authors find much attack. The v3 curves at 10, 000 queries (Guo et al., 2019, Figure 4) for SIMBA (and variant SIMBA-DCT) look comparable to S gnHunter's of Figure 9. For completeness, we implemented S SIMBA and evaluated it against the CIFARIO model in Section 4. The results are shown in Figure 13. In line with Guo et al. (2019), SIMBA is strong baseline in thel, setup. However. its performance drops significantly in the foo setup.
difficult
Sigstunter
702
Siystunter
svercpp QUHEEO
1282
STRRA
642
SIHIK
1000
400
015
3.2
6-.1
0.
25
00
02
0.2
1.5
0.5
22
SLaCEESS zale
CIFARIO 8
(b) CIFARIO &g
Figure 13: Performance of STMBA and si gnHunter the for and Ea perturbation settings of
Section 4 on CIFAR10. 10. The plots show the average number of queries used per successful image for each attack when reaching specified success rate. In line with Guo al. (2019), we used a step size of 8 50 for &a (the authors used 5 = 0.2 for [o, 1]-valued pixels, our setup takes images in [0, 255] so 8 = 0.2 255 ~ 50). For lac. we used = 2, following NES's setup in Table
Harmonica (Hazan et al., 2017). Both SignHunt er and Harmenica seek to optimize black-box function over the binary hypercube {=1}". albeit with different assumptions on the objective function. Ha Barronico ica assumes that the objective function can be approximated by a sparse and low degree polynomial in the Fourier basis. Our assumption with SignHunter that the objective function separable (Property 1, Section 3), this lets us optimize the black-box function with (n) queries given an initial guess instead of searching over the 2" vertices. If this assumption is not met, can restart Si guntter with another guess with scarch complexity of (mm) where m the number of restarts. With this difference in assumptions of the two algorithms, conducted an empirical comparison using two sample problems provided along with Ha rmon i ca authors implementation. As shown in Table 14, the results show that S SignHunte er optimizes the two problems with 8x less number of queries than Harmonica ca, not to mention the significant computational advantage.
Table 14: Performance comparison of SignHunter and Harmonica on two sample problems from https: bttps://github: wwwww//wwwww........ooooo..c...a www.moooca....c.........a. The lower solution quality, the better.
Algorithm
Solution Quality
queries
Time per Query
Harmonica
-50.0
4223
67.47 ms
Problem 1
Signllnteer
-50.0
20
36.30uu
Harmonica
-916.22
4223
60.22 ms
Problem 2
SignHunter
-916.21
500
584.28ps
24

---

Published conference paper ICLR 2020
APPENDIX I. ON THE E2- PERFORMANCE GAP
As discussed in Section 4, in an e fg threat setup, black-box attacks that are based on continuous optimization (e.g,, NES and Handitap tarp) can vary each pixel within [x -, + On the other hand, S gnHunter is restricted to [ e/vn. a: e/ e/yn]. In other words, S SignHunter in exactly the same when used e/ V Loo perturbation setup. This is illustrated in Figure 14
perturhation setup hehaves
To highlight additional perturbation space that other algorithms have over SignHunter in the setup. we ran NES and Banditsp as representative examples standard and dimensiionality-rcttciio---- algorithms against the CIFAR1O model used in Section with an for perturbation setup of e = 127/ /n. In this and and the fg setup used in Section 4, SignHunter behaves the samc, while the performance of NES and Bandit drops significantly from their & performance due the reduction in the perturbation space.
possible to allow Signäunter to access the additional search space introduced in the &2 setup is to extend the notion of binary sign flips over -1} to ternary sign flips over [+1, 0, -1} and we intend to explore this thoroughly in future work.
e-perturbation Ey-ball
p--prurrratioon
e
Sipekurae Advessraa duargie Ieratios
Oua reper
Figure 14: Illustration of adversarial examples crafted by SignHunter in comparison to attacks that are based on the continuous optimization (e.g., NES and Banditstp) in both (a) fox and (b) la settings. For both e-L2 and e/ > perturbation balls, SignHunter behaves the same, while continuous attacks such as NES have access to more possible perturbations in the le setup compared to their perturbations in the foo setup. This is demonstrated on CIFAR10 in Figure 15.
Tee
Eanditayo
Banditkyc
Sigstunter
Sigstunter
37
8.0
410-
SHECESS pate
success rate
(s) CIFARTO 20
127
(b) CIFARIO
52
Figure 15: Performance of black-box attacks in the loo and perturbation constraints. The plots show the average number of queries used per successful image for each attack when reaching specified success rate. Note that (b) is similar to the & setup examined Section 4.
25


Reviews:
[{"review_id": "r1ePbcshYS", "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": "Summary:\nThis paper proposes a black-box adversarial sample generation algorithm, which proceeds by learning the signs of the gradient using an adaptive query scheme, which the authors call _SignHunter_. The authors begin by deriving an upper bound on the query complexity for _SignHunter_. Next, the authors empirically compare the performance of _SignHunter_ \nwith existing sign-based optimization schemes in the literature, and demonstrate the advantages of _SignHunter_. \n\n\nMain Comments: \n\n- Theoretical analysis of the Adaptive Scheme: The authors emphasize the adaptive nature of the proposed scheme as one of the contributions. However, this claim is not justified theoretically:  it would be interesting if the benefits of adaptivity could be quantified in terms of improved worst-case query complexity etc. as compared to any non-adaptive scheme. The query complexity of 2^{\\log(n)+1} given in Theorem 1 is not very informative, since a lower complexity (n) is achieved by a simple open-loop  scheme which serially queries each coordinate (i.e., the first query is coordinate 1, the second query is coordinate 2, and so on). \n\n-  Comparison with Hazan el. al (2018): A closely related work in optimizing real-valued functions with domain \\{-1,1\\}^n is Hazan et. al published in ICLR 2018, which assumes that the black-box function is sparse or compressible in the Fourier domain, and employs compressed sensing techniques to get fast convergence rates in the optimization error. Since that paper considers a very similar optimization problem and proposes a scheme with provable convergence guarantees,  I think it is important that the authors compare,  either theoretically or empirically,  the performance of their proposed scheme with Harmonica (the algorithm of Hazan et al (2018)) to justify the benefits their proposed scheme. \n\n- Parameter Free Algorithm: The statement of Theorem 1 contains the following hypothesis: \"the directional derivative is well approximated by the finite difference (Eq. 1)\". This condition must be clarified, because it seems to contradict the claim made by the authors later in the last line of Page 5 that _SignHunter_ is \"parameter-free\" as they set \\delta= \\epsilon. The condition in the statement of Theorem 1 will not necessarily be satisfied for any \\delta, and admissible values of \\delta must depend on the properties of the function. Informally, I think that the condition will only be satisfied for \\delta \"small enough\", and one way to make precise the meaning of \"small enough\" is in terms of the Lipschitz constant of the neural network. However, in that case, I am not sure that the algorithm would remain parameter-free.  I think the authors should make the assumption in Theorem 1 precise and derive suitable sufficient conditions on \\delta under which the assumption is satisfied.\n\nReferences:\n1. Hazan, Elad, Adam Klivans, and Yang Yuan. \"Hyperparameter optimization: A spectral approach.\" ICLR (2018).\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": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "SyxFBUmsKr", "reviewer": "AnonReviewer3", "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": "I'm satisfied with the response. I'll keep my original rating towards acceptance.\n\n----------------------------\n\nThis paper proposes a black-box adversarial attack method to improve query efficiency and attack success rate. Instead of estimating the gradient of a black-box model, the proposed method estimates the sign of the gradient, which is an easier task. The SignHunter algorithm is proposed to estimate the sign of the gradient by a divide-and-conquer search. And adversarial examples are generated based on the sign gradient. Extensive experiments prove the effectiveness of the proposed attack method.\n\nOverall, the proposed method on estimating the sign of the gradient for black-box attacks is novel. The authors provide sufficient analysis to present the algorithm, making it clear to see the advantage of the proposed method over previous methods. I have some minor comments on this paper.\n\n1. In Section 2 (Line 15), the authors argue that \"However, the queries are not adaptive, they are constructed based on i.i.d. random vectors {vi}\". However, in Ilyas et al. (2019), the queries are designed based on the time prior, which are actually adaptive.\n\n2. Estimating the sign of the gradient is more suitable for attacks based on the l_\\infty norm, but could affect the results for l_2 attacks, since it reduces the search space. The experiments also show that the proposed method for l_2 attacks is not as effective as l_\\infty attacks.\n\n3. It's better to show some tabular results in Section 4 rather than appendix to compare the performance with numbers.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "SJx_zBx6tH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "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 introduce a black box adversarial attack based on estimating the sign of the gradient. To estimate this more efficiently than the gradient itself, the authors exploit the fact that directional derivatives can be estimated using finite differences using only two function evaluations, and use a simple flip/revert procedure to estimate a number of sign bits simultaneously. This sign bit gradient vector is then used in place of the true gradient in an FGSM-like procedure. The central arguments are that (1) estimating the sign bits alone is sufficient to produce adversarial examples, and (2) this can be done quickly enough in practice to yield an efficient procedure.\n\nOverall, I feel that this paper makes a decent contribution to blackbox adversarial generation in settings where confidence scores are available. In particular, many algorithms in this area are often quite complicated and involve machinery like genetic programming. Recent work has begun to demonstrate that significantly simpler routines can not only generate adversarial images, but can do so with significantly fewer queries than their more complicated counterparts. \n\nIn particular, two of the methods compared to (NES, Bandits-TD) are state of the art or nearly state of the art, and seem to be significantly outperformed in most regimes considered -- at a glance it appears this approach may outperform other recent work that isn't compared to, such as the method of Guo et al., 2019. The inclusion of results on the public blackbox attack challenges is also welcome.\n\nCould the authors comment on the apparent degradation of performance on L2 performance as the image dimensionality increases? Is this simply an artifact of the fact that the ||x||_{2} <= sqrt(n) ||x||_{\\infty} bound directly scales with the input dimensionality? It would be interesting to verify this shortcoming by determining whether applying recent techniques for dimensionality reduction and approximating signed gradients in the subspace alters the relative performance of methods in the L2 perturbation constraint experiments.", "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 assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a novel black-box adversarial attack algorithm, which exploits a sign-based rather than magnitude-based, gradient estimator for black-box optimization. It also adaptively constructs queries to estimate the gradient. The proposed approach outperforms many state-of-the-art black-box attack methods in terms of  query complexity. There is a unanimous agreement to accept this paper.
Decision: Accept (Poster)