Title: SIGN BITS ARE ALL YOU NEED FOR BLACK-BOX AT-TACKS

Abstract: We present a novel black-box adversarial attack algorithm with state-of-the-art model evasion rates for query efficiency under ∞ and 2 metrics. It exploits a 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× less failure-prone while spending 2.5× 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.

1. INTRODUCTION:

Problem. Deep Neural Networks (DNNs) are vulnerable to adversarial examples, which are malicious inputs designed to fool the model's prediction-see (Biggio and Roli, 2018) for a comprehensive, recent overview of adversarial examples. Research on generating these malicious inputs started in 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 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 a continuous optimization problem of O(n) complexity where n is the input dimensionality. Most recently work has sought to reduce this complexity by means of data-/time-dependent priors Ilyas et al. (2019) . In this paper, we take a 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 1 reproducing Ilyas et al. (2019) illustrates this observation for the MNIST dataset-see 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 as effective as those generated by full gradient estimation approaches.

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-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 al. (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-Dezfooli et al., 2016; Hayes and Danezis, 2017; Al-Dujaili et al., 2018; Kurakin et al., 2017; Shamir et al., 2019) . Turning to the blackbox 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 a 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 a 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 a trained auto-encoder to achieve attack acceleration. Ilyas et al. (2019) extend this line of work by proposing the idea of gradient priors and bandits: Bandits T D . 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.1 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 et al., 2017) . Alternately, Xiao et al. (2018) Sign-Based Optimization. In the context of generalpurpose continuous optimization methods, signbased stochastic gradient descent was studied in both zeroth-and first-order setups. In the latter, Bernstein et al. (2018) analyzed signSGD, a sign-based Stochastic Gradient Descent, and showed that it enjoys a faster empirical convergence than SGD in addition to the cost reduction of communicating gradients across multiple workers. Liu et al. (2019) extended signSGD to zeroth-order setup with the ZO-SignSGD algorithm. ZO-SignSGD (Liu et al., 2019) was shown to outperform NES against a blackbox model on MNIST. These approaches use the sign of the gradient (or its zero-order estimate) to achieve better convergence, whereas our approach both estimates and uses the sign of the gradient.

Contributions. We present the following contributions at the intersection of adversarial machine learning and black-box (zeroth-order) 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} n vectors, to propose a divide-and-conquer, adaptive, memory-efficient algorithm, we name 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 a similar performance guarantee. 3) We evaluate our 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. Notation. Let n denote the dimension of datapoint x. Denote a hidden n-dimensional binary code by q * . That is, q * ∈ H ≡ {-1, +1} n . Further, denote the directional derivative of some function f at a point x in the direction of a vector v by D v f (x) ≡ v T ∇ x f (x) which often can be approximated by the finite difference method. That is, for δ > 0, we have

EQUATION

Let Π S (•) be the projection operator onto the set S, B p (x, ) be the p ball of radius around x.

2. GRADIENT ESTIMATION:

At the heart of black-box adversarial attacks is generating a perturbation vector to slightly modify the original input x 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 -close to the original input x.

Although the loss function L can be non-concave, gradient-based 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 ∇ x L(x, 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(x, 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 L at the input/label pair (x, y) in the direction of a vector v, which corresponds to v T ∇ x L(x, y). With n linearly independent vectors {v i T ∇ x L(x, y) = d i } 1≤i≤n , one can construct a linear system of equations to recover the full gradient. Clearly, this approach's query complexity is O(n), which can be prohibitively expensive for large n (e.g., n = 268, 203 for the IMAGENET dataset). Recent works try to mitigate this issue by exploiting data-and/or time-dependent priors (Tu et al., 2018; Ilyas et al., 2018; 2019) . However, the queries are not adaptive, they are constructed based on i.i.d. random vectors {v i }. 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 of 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 an input/label pair (x, y) and a loss function L, let g * = ∇ x L(x, y) be the gradient of L at (x, y) and q * = sign(g * ) ∈ H be the sign bit vector of g * . 2 Then the goal of the gradient sign estimation problem is to find a binary vector q ∈ H maximizing the directional derivative

EQUATION

from a limited number of (possibly adaptive) function value queries L(x , y).

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 (x, 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 2 Without loss of generality, we encode the sign bit vector in H ≡ {-1, +1} n rather than {0, 1} n . This is a common representation in sign-related literature. Note that the standard sign function has the range of {-1, 0, +1}. Here, we use the 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) . 3 The maximization follows from DqL(x, y) = q T g * , which is maximized when q = q * = sign(g * ).

adversarial attacks. Based on the definition of the directional derivative (Eq. 1), the following can be stated.

Property 1 (Separability of D q L(x, y)). The directional derivative D q L(x, y) of the loss function L at an input/label pair (x, y) in the direction of a binary code q is separable. That is,

max q∈H D q L(x, y) = max q∈H q T g * = n i=1 max qi∈{-1,+1}

q i g * i .

(3)

Algorithm 1 SignHunter g : H → R : the black-box function to be maximized over the binary hypercube

H ≡ {-1, +1} n def init(g) : i ← 0, h ← 0 g ← g s ∼ U (H) // e.g., [+1, . . . , +1] done ← f alse g best ← -∞ def is_done() : return done def step() : c_len ← n/2 h s[i*c_len:(i+1)*c_len] *= -1 if g(s) ≥ g best : g best ← g(s) else: s[i*c_len:(i+1)*c_len] *= -1 increment i if i == 2 h : i ← 0, increment h if h == log 2 (n) + 1: done ← true def get_current_sign_estimate() : return s

This reformulates the gradient sign estimation problem from single n-dimensional to n 1-dimensional binary black-box optimization problems, reducing the search space of sign bits from 2 n to 2n. Subsequently, one could recover the gradient sign bits with n + 2 queries as follows: i. Start with an arbitrary sign vector q and compute the directional derivative D q L(x, y). Using Eq. 1, this requires two queries: L(x+δq, y) and L(x, y). ii. For the remaining n queries, flip q's bits (coordinates) one by one and compute the corresponding directional derivativeone query each L(x + δq, y). iii. Retain bit flips that maximize the directional derivative D q L(x, y) and revert those otherwise. This, however, still suffers from the O(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?

Consider the case where all the gradient coordinates have the same magnitude, i.e., |{|g * i |} 1≤i≤n |= 1, and let the initial guess q 1 have r correct bits and n -r wrong ones. Instead of flipping its bits sequentially, we can flip them all at once to get q 2 = -q 1 . If D q2 L(x, y) ≥ D q1 L(x, y), then we retain q 2 as our best guess with n -r correct bits, otherwise q 1 remains. In either cases, with three queries, we will recover max(r, n -r) sign bits. One can think of this flip/revert procedure as one of majority voting by the guess's coordinates on whether they agree with their gradient sign's counterparts. To see this, let |g * i |= 1 for all i, then the condition D q2 L(x, y) ≥ D q1 L(x, y) can be written as n -r -r ≥ r -n + r =⇒ n ≥ 2r. If the agree votes r are less than half of the total votes n, then q 2 is retained. Besides flipping all the coordinates, one can employ the same procedure iteratively on a subset (chunk) of the coordinates [q j , . . . , q j+ni ] of the guess vector q, recovering max(r i , n i -r i ) sign bits, where n i and r i 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 as assumed in the previous example; through empirical evaluation (see Appendix F), we found them to be concentrated. Consequently and with high probability, their votes on retaining or reverting chunks of sign flips are 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, if 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 in a divide-and-conquer search which we refer to as SignHunter. As outlined in Algorithm 1, the technique starts with an initial guess of the sign vector q 1 (s in Algorithm 1). It then proceeds to flip the sign of all the coordinates to get a new sign vector q 2 , and revert the flips if the loss oracle returned a value L(x + δq 2 , y) (or equivalently the directional derivative ) less than the best obtained so far L(x + δq 1 , y). SignHunter applies the same rule to the first half of the coordinates, the second half, the first quadrant, the second quadrant, and so on. For a search space of dimension n, SignHunter needs 2 log(n)+1 -1 sign flips to complete its 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 a sign vector whose Hamming distance to the optimal sign vector q * is n/2: agreeing with q * in the first half of coordinates. In this case, SignHunter needs just four queries to recover the entire sign vector independent of n, whereas the sequential bit flipping still require n + 2 queries. In the next theorem, we show that SignHunter is guaranteed to perform at least as well as FGSM with O(n) oracle queries. Up to our knowledge, no such guarantees exist for any black-box attack from the literature.

Theorem 1. (Optimality of SignHunter) Given 2 log(n)+1 queries and that the directional derivative is well approximated by the finite-difference (Eq. 1), SignHunter is at least as effective as FGSM (Goodfellow et al., 2015) in crafting adversarial examples. The proof can be found in Appendix B. Theorem 1 provides an upper bound on the number of queries required for SignHunter to recover the gradient sign bits, and perform as well as FGSM.

In practice (as will be shown in our experiments), SignHunter 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 s. In our setup, we use the best sign estimation obtained s so far in a similar fashion to FGSM, whereas full-gradient estimation approaches often employ an iterative scheme of T steps within the perturbation ball B p (x, ), calling the gradient estimation routine in every step leading to a search complexity of nT . Instead, our gradient sign estimation routine runs at the top level of our adversarial example generation procedure. Further, SignHunter is amenable to 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 SignHunter is outlined in Algorithm 2.

4. EXPERIMENTS:

Algorithm 2 Black-Box Adversarial Example Generation with SignHunter x init : input to be perturbed, yinit : xinit's true label, Bp(., ) : p perturbation ball of radius L : loss function of the model under attack 1: δ ← // set finite-difference probe to perturbation bound 2: x o ← x init 3: Define the function g as

g(q) = L(Π Bp(xinit, ) (x o + δq), y init ) -L(x o , y init ) δ 4: SignHunter.init(g) 5: //C(•) returns top class 6: while C(x) = y init do 7:

SignHunter.step()

8:

s ← SignHunter.get_current_sign_estimate()

9: x ← Π Bp(xinit, ) (x o + δs) 10:

if SignHunter.is_done() then 11:

x o ← x 12:

Define the function g as in Line 3 (with x o update) 13:

SignHunter.init(g) (Ilyas 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 ∞ threat model, we use (Madry et al., 2017) 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, CIFAR10, and IMAGENET classifiers under the ∞ and 2 perturbation constraints. These plots indicate the average number of queries required for a desired success rate. Table 1 represents a tabulated summary of plots (b) and (e) 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 2 setup, where Bandits T D shows a better query efficiency when the desired success rate is roughly greater than 0.35. This is all the more remarkable because Bandits T D exploits tiles, a data-dependent prior, searching over 50 × 50 × 3 dimensions for IMAGENET, while SignHunter searches over the explicit data 299 × 299 × 3 dimensions: 36× more dimensions.

∞ vs. 2 Perturbation Threat. In view of Bandits T D 's advantage, SignHunter is remarkably efficient in the ∞ setup, achieving a 100% evasion using-on average-just 12 queries per image against the MNIST classifier! In the 2 setup, SignHunter's performance degrades-yet it still outperforms the other algorithms. This is expected, since SignHunter perturbs all the coordinates with the same magnitude and the 2 perturbation bound 2 for all the datasets in our experiments is set such that 2 / √ n is significantly less than the ∞ perturbation bound ∞ . Take the case of MNIST (n = 28 × 28), where ∞ = 0.3 and 2 = 3. For SignHunter, the 2 setup is equivalent to an ∞ perturbation bound of 3/28 ≈ 0.1. The employed 2 perturbation bounds give the state of the art-continuous 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 a magnitude of 3/ √ 2 ≈ 2.1 each; ten pixels by a magnitude of 3/ √ 10 ≈ 0.9 each, etc. On the other hand, the binary optimization view of SignHunter limits it to always perturb all 28 × 28 pixels by a magnitude of 3/28 ≈ 0.1. Despite its fewer degrees of freedom, SignHunter maintains its effectiveness in the 2 setup. The plots can also be interpreted as a sensitivity assessment of SignHunter as gets smaller going from ∞ to the 2 perturbation threat.

SignHunter vs FGSM. The performance of SignHunter is in line with Theorem 1 when compared with the performance of FGSM (the noisy FGSM at k = 100% in Figures 1 and 2 of Appendix A) in both ∞ and 2 setups across all datasets. For instance, FGSM has a failure rate of 0.32 for CIFAR10 2 (Appendix A, Figure 2 (b) ), while SignHunter achieves a failure rate of 0.21 with 692.39 < 2n = 2 × 3 × 32 × 32 = 6144 queries (Appendix D, Table 8 ). Note that for IMAGENET, SignHunter 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 as well. Incorporating SignHunter in an iterative framework of perturbing the data point x till the query budget is exhausted (Lines 10 to 14 in Algorithm 2) supports the observation in white-box settings that iterative FGSM-or Projected Gradient Descent (PGD)-is stronger than FGSM (Madry et al., 2017; Al-Dujaili et al., 2018) . This is evident by the upticks in SignHunter's performance on the MNIST 2 case (Appendix D, Figure 4 ), which happens after every iteration (after every other 2 × 28 × 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 Bandits T D consistently optimize both metrics. In general, SignHunter (Bandits T D ) converges faster especially on the Hamming(cosine) metric as it is estimating the signs(signs and magnitudes) compared to Bandits T D 's full gradient (SignHunter's gradient sign) estimation. This is most obvious in the IMAGENET 2 setup (Appendix D, Figure 6 ). Note that once an attack is successful, the estimated gradient sign at that point is used for the rest of the plot. This explains why, in the ∞ settings, SignHunter's plot does not improve compared to its 2 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 SignHunter's estimation. More on this is discussed in Section 6.

SignHunter 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 SignHunter's adaptive query construction. Except for MNIST and CIFAR10 ∞ settings, Rand performs worse than the full-gradient estimation approaches, although it perturbs datapoints similar to SignHunter. Overall, SignHunter is 3.8× less failure-prone than the state-of-the-art approaches combined, and spends over all the images (successful and unsuccessful attacks) 2.5× less queries.7 

5. SI G NHU N T E R VS. DEFENSES:

To complement Section 4, we evaluate SignHunter against adversarial training, a way to improve the robustness of DNNs (Madry et al., 2017) . Specifically, we attacked the secret models used Published as a conference paper at ICLR 2020 in public challenges for MNIST and CIFAR10. 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 metrics 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 ∞ perturbation bound of = 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, so 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's attacks resulted in the lowest model accuracy of 91.47%, 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) Ensemble Adversarial Training on IMAGENET. In line with Tramèr et al. (2017a) , we set = 0.0625 and report the v3 adv-ens4 model's misclassification over 10,000 random images from IMA-GENET's validation set. After 20 queries, SignHunter 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 robustness with a top-1 error of 90.75%!

6. CHARACTERIZING ADVERSARIAL CONES WITH SI G NHU N T E R:

Estimating the size of adversarial cones, the space of adversarial examples in the vicinity of a point, for a 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-Aligned Adversarial Subspace (GAAS) method Tramèr et 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 loss function, this is reduced to finding orthogonal vectors that are maximally aligned with its gradient g * -or its gradient sign q * in the ∞ 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 SignHunter's estimation (we refer to this approach as SAAS) instead of aligning them with the gradient (GAAS) results in a better approximation of the adversarial cone for the two IMAGENET models considered earlier, even when the number of queries given to SignHunter is just a fraction of the dimensionality n. Through its query-efficient finite-difference sign estimation, SignHunter is able to quickly capture the larger-scale variation of the loss landscape in the point's neighborhood, 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-Dezfooli et al. (2018); Tramèr et al. (2017a) . One interesting observation at k = 1 (note here, r 1 = q * ) across all is that GAAS finds adversarial directions for fewer points against the v3 adv-ens4 model than the naturally trained model v3, whereas SAAS reports similar probability of adversarial directions for both. This contrast suggests that ensemble adversarial training Tramèr et al. (2017a) still exhibits the gradient masking effect, where the gradient poorly approximates the global loss landscape.

7. CONCLUSION:

Assuming a 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 SignHunter-Aligned Adversarial Subspace) finds k orthogonal vectors that are maximally aligned with SignHunter's s (Algorithm 2, Line 8) after 1, 000 queries. Similar to (Tramèr et al., 2017a , Figure 2 ), for 500 correctly classified points x and ∈ {4, 10, 16}, we plot the probability that we find at least k orthogonal vectors r i -computed based on (Tramèr et al., 2017a 

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, CIFAR10 and IMAGENET datasets. In Figure 4 , we consider the ∞ threat perturbation constraint. Figure 5 reports the performance for the 2 setup. Similar to Ilyas et al. (2019) , for each k in the experiment, the top k percent of the signs of the coordinates-chosen either randomly (random-k) or by the corresponding magnitude |∂L(x, y)/∂xi| (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 out of the sampled 1000 images, respectively. These figures also serve as a validation for Theorem 1 of the main paper when compared to SignHunter's performance shown in Appendix D. 

Value MNIST CIFAR10 IMAGENET ∞ 2 ∞ 2 ∞ 2

Hyperparameter δ (finite difference probe) 0. The plots above show the average performance of the tuned attacks on the synthetic loss function L(x, y) = -(x -x * ) T (x -x * ), where x * = xmin+xmax 2 using a query limit of 1000 queries for each image. Note that in all, Bandits T D outperforms both NES and ZO-SignSGD. Also, we observe the same behavior reported by Liu et al. (2019) on the fast convergence of ZO-SignSGD compared to NES. We did not tune SignHunter; it does not have any tunable parameters.

Table 8 : Summary of attacks effectiveness on MNIST under ∞ and 2 perturbation constraints, and with a query limit of 10, 000 queries. The Failure Rate ∈ [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. Loss row reports the loss as 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 sign q * , computed as 1 -||sign(ĝ) -q * || H /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 a successful attack up to the query limit of 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 is to the bottom right of the plot.

APPENDIX E. PUBLIC BLACK-BOX CHALLENGE RESULTS:

This section shows results of our experiments in 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 . 

Black-Box Attack Model Accuracy:

SignHunter (Algorithm 2 in the main paper) 91.47% Xiao et al. (2018) 92.76% PGD against 3 independently & adversarially trained copies of the network

93.54%:

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 on 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 on the cross-entropy loss for the adversarially trained public network

97.66%:

PGD on the cross-entropy loss for the adversarially trained public network 

97.79%:



SignHunter (Algorithm 2 in the main paper) 47.16% PGD on the cross-entropy loss for the adversarially trained public network

63.39%:

PGD on 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% 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 * || H /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 a successful attack up to the query limit of 5, 000 queries for MNIST and CIFAR10 (1, 000 queries for IMAGENET). 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 is to the bottom right of the plot.

:

We use the term adaptive here to characterize how the algorithm constructs its perturbation vector qt deterministically based on the previous perturbations. Mathematically, the perturbation vector at time t can be expressed as deterministic function qt = g(qt-1). In contrast, other algorithms construct I.I.D randomly perturbation vectors: qt ∼ N (0, I).

That is, replace Line 8 in Algorithm 2 by s ∼ U (H).

More tabulated summaries of these plots can be found in Appendix D-Tables7-9. We also plot the classifier's loss and the gradient estimation quality (in terms of 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.

We define perturbation vertices as extreme points of the ball Bp(x, ). That is, x ± ∞, where ∞ = when p = ∞ and ∞ = / √ n when p = 2.

The number of queries spent is computed based on Tables 7-9 of Appendix D as (1 -fail_rate) * avg_#_queries + fail_rate * 10,000.

Figures and Tables:

Figure 3: Two estimations of the ∞ adversarial cones for two IMAGENET models: v3 and v3 adv-ens4 . The first estimation (GAAS: Gradient-Aligned Adversarial Subspace) finds k orthogonal vectors maximally aligned with the gradient sign q * Tramèr et al. (2017a). The second (SAAS:SignHunter-Aligned Adversarial Subspace) finds k orthogonal vectors that are maximally aligned with SignHunter's s (Algorithm 2, Line 8) after 1, 000 queries. Similar to(Tramèr et al., 2017a, Figure2), for 500 correctly classified points x and ∈ {4, 10, 16}, we plot the probability that we find at least k orthogonal vectors r i -computed based on(Tramèr et al., 2017a, Lemma 7)-such that ||r i || ∞ = and x + r i is misclassified. For both models and for the same points x, SAAS finds more orthogonal adversarial vectors r i than GAAS, thereby providing a better characterization of the space of adversarial examples in the vicinity of a point, albeit without a white-box access to the models.

Figure 4: Misclassification rate of three neural nets (for (a) MNIST, (b) CIFAR10, and (c) IMAGENET, respectively) on the noisy FGSM's adversarial examples as a function of correctly estimated coordinates of sign(∇xf(x, y)) on random 1000 images from the corresponding evaluation dataset, with the maximum allowed ∞ perturbation being set 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 a misclassification rate of ∼ 70%. Note that Plot (c) is similar toIlyas et al. (2019)'s Figure1, but it is produced with TensorFlow rather than PyTorch.

Figure 6: Tuning testbed 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 p perturbation constraint. The plots above show the average performance of the tuned attacks on the synthetic loss function L(x, y) = -(x -x * ) T (x -x * ), where x * = xmin+xmax

Figure9: Performance curves of attacks on IMAGENET for ∞ (first column) and 2 (second column) perturbation constraints. Plots of Avg. Loss row reports the loss as 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 sign q * , computed as 1 -||sign(ĝ) -q * || H /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 a successful attack up to the query limit of 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 is to the bottom right of the plot.

Figure10: Performance curves of attacks on the public black-box challenges for MNIST (first column), CIFAR10 (second column) and IMAGENET (third column). Plots of Avg. Loss row reports the loss as 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 sign q * , computed as 1 -||sign(ĝ) -q * || H /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 a successful attack up to the query limit of 5, 000 queries for MNIST and CIFAR10 (1, 000 queries for IMAGENET). 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 is to the bottom right of the plot.

use a Generative Adversarial Network (GAN) to generate adversarial examples which are based on small norm-bounded perturbations. These methods involve learning on a different model, which is expensive, and not amenable to comparison with setups-including ours-that directly query the model of interest.

Table content: <table><tr><td>0.2 0.4 0.6 0.8 misclassification rate</td><td/><td>random-k top-k</td><td/></tr><tr><td>0.0</td><td>0%</td><td>20% k percent of MNIST coordinates 40% 60% 80%</td><td>100%</td></tr></table>

Through these experiments, we demonstrate that SignHunter's adaptive search for the gradient sign allows it to craft adversarial examples within a mere fraction of the theoretical number of queries thus outperforming FGSM and state-of-the-art black-box attacks. 4) We release a software framework to systematically benchmark adversarial black-box attacks, including SignHunter's, on MNIST, CIFAR10, and IMAGENET models in terms of success rate, query count, and other metrics. 5) We demonstrate how SignHunter can be used to characterize adversarial cones in a black-box setup and in doing so, highlight the gradient masking effect.

Table content: <table/>

Figure2: Performance of black-box attacks in the ∞ and 2 perturbation constraint. The plots show the average number of queries used per successful image for each attack when reaching a specified success rate. Summary of attacks effectiveness on CIFAR10 under ∞ and 2 perturbation constraints, and with a query limit of 10, 000 queries. The Failure Rate ∈ [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.

Table content: <table><tr><td>average # queries</td><td>200 400 600 800</td><td colspan="2">BanditsT D NES Rand SignHunter ZOSignSGD</td><td/><td>average # queries</td><td>100 200 300 400</td><td/><td/><td/><td/><td/><td>average # queries</td><td>1500 250 500 750 1000 1250</td><td/><td/></tr><tr><td/><td>0</td><td/><td/><td/><td/><td>0</td><td/><td/><td/><td/><td/><td/><td>0</td><td/><td/></tr><tr><td/><td>0.0</td><td>0.2</td><td>0.4 success rate 0.6</td><td>0.8</td><td>1.0</td><td>0.0</td><td/><td>0.2</td><td>0.4 success rate 0.6</td><td/><td>0.8</td><td/><td>0.0</td><td>0.2</td><td>0.4 success rate 0.6</td><td>0.8</td><td>1.0</td></tr><tr><td/><td/><td colspan="2">(a) MNIST ∞</td><td/><td/><td/><td colspan="4">(b) CIFAR10 ∞</td><td/><td/><td/><td colspan="3">(c) IMAGENET ∞</td></tr><tr><td/><td>1200</td><td/><td/><td/><td/><td>1200</td><td/><td/><td/><td/><td/><td/><td>2000</td><td/><td/></tr><tr><td>average # queries</td><td>200 400 600 800 1000</td><td/><td/><td/><td>average # queries</td><td>200 400 600 800 1000</td><td/><td/><td/><td/><td/><td>average # queries</td><td>500 1000 1500</td><td/><td/></tr><tr><td/><td>0</td><td/><td/><td/><td/><td>0</td><td/><td/><td/><td/><td/><td/><td>0</td><td/><td/></tr><tr><td/><td>0.0</td><td>0.2</td><td>0.4 success rate 0.6</td><td>0.8</td><td>1.0</td><td>0.0</td><td>0.1</td><td>0.2</td><td>0.3 success rate 0.4 0.5</td><td>0.6</td><td>0.7</td><td>0.8</td><td>0.0</td><td>0.2</td><td>0.4 success rate 0.6</td><td>0.8</td></tr><tr><td/><td/><td colspan="2">(d) MNIST 2</td><td/><td/><td/><td colspan="4">(e) CIFAR10 2</td><td/><td/><td/><td colspan="3">(f) IMAGENET 2</td></tr></table>

-as of May 15, 2019-resulted in a model accuracy of 88.42%. Further, a PGD attack with 5, 000 back-propagations achieves 89.62% in contrast to SignHunter's 91.47% with just 5, 000 forward-propagations.Public CIFAR10 Black-Box Attack Challenge. This challenge setup is similar to the above, but with an ∞ perturbation bound of = 8. SignHunter's attacks resulted in the lowest model accuracy of 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 byZheng et al. (2018)-as of May 15, 2019-resulted in a model accuracy of 44.71%. Further, a PGD attack with 200 back-propagations achieves 45.21% in contrast to SignHunter's 47.16% with 5, 000 forward-propagations.

Table content: <table/>

, Lemma 7)-such that ||r i || ∞ = and x + r i is misclassified. For both models and for the same points x, SAAS finds more orthogonal adversarial vectors r i than GAAS, thereby providing a better characterization of the space of adversarial examples in the vicinity of a point, albeit without a white-box access to the models.

Table content: <table/>

Hyperparameters setup for ZO-SignSGD

Table content: <table><tr><td/><td>Value</td><td/><td/><td/><td/></tr><tr><td/><td colspan="2">MNIST</td><td colspan="2">CIFAR10</td><td colspan="2">IMAGENET</td></tr><tr><td/><td>∞</td><td>2</td><td>∞</td><td>2</td><td>∞</td><td>2</td></tr><tr><td>Hyperparameter</td><td/><td/><td/><td/><td/></tr><tr><td>δ (finite difference probe)</td><td colspan="5">0.1 0.1 2.55 2.55 0.1</td><td>0.1</td></tr><tr><td>η (image p learning rate)</td><td colspan="3">0.1 0.1 2</td><td>2</td><td colspan="2">0.02 0.004</td></tr><tr><td colspan="4">q (number of finite difference estimations per step) 10 20 20</td><td>4</td><td colspan="2">100 50</td></tr></table>

Hyperparameters setup for Bandits T D

Table content: <table><tr><td/><td>Value</td><td/><td/><td/><td/><td/></tr><tr><td/><td>MNIST</td><td/><td>CIFAR10</td><td/><td colspan="2">IMAGENET</td></tr><tr><td/><td>∞</td><td>2</td><td>∞</td><td>2</td><td>∞</td><td>2</td></tr><tr><td>Hyperparameter</td><td/><td/><td/><td/><td/><td/></tr><tr><td>η (image p learning rate)</td><td>0.03</td><td>0.01</td><td>5</td><td>12</td><td>0.01</td><td>0.1</td></tr><tr><td>δ (finite difference probe)</td><td>0.1</td><td>0.1</td><td>2.55</td><td>2.55</td><td>0.1</td><td>0.1</td></tr><tr><td colspan="7">τ (online convex optimization learning rate) 0.001 0.0001 0.0001 1e-05 0.0001 0.1</td></tr><tr><td>Tile size (data-dependent prior)</td><td>8</td><td>10</td><td>20</td><td>20</td><td>50</td><td>50</td></tr><tr><td>ζ (bandit exploration)</td><td>0.01</td><td>0.1</td><td>0.1</td><td>0.1</td><td>0.01</td><td>0.1</td></tr></table>

Hyperparameters setup for SignHunter

Table content: <table/>

Summary of attacks effectiveness on CIFAR10 under ∞ and 2 perturbation constraints, and with a query limit of 10, 000 queries. The Failure Rate ∈ [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.

Table content: <table><tr><td/><td colspan="4">Failure Rate Avg. # Queries</td></tr><tr><td/><td>∞</td><td>2</td><td>∞</td><td>2</td></tr><tr><td>Attack</td><td/><td/><td/></tr><tr><td>Bandits T D</td><td colspan="2">0.68 0.59</td><td colspan="2">328.00 673.16</td></tr><tr><td>NES</td><td colspan="2">0.63 0.63</td><td colspan="2">235.07 361.42</td></tr><tr><td>Rand</td><td colspan="2">0.33 0.96</td><td colspan="2">847.77 1144.74</td></tr><tr><td colspan="5">SignHunter 0.00 0.04 11.06 1064.22</td></tr><tr><td>ZOSignSGD</td><td colspan="2">0.63 0.75</td><td colspan="2">157.00 881.08</td></tr><tr><td/><td colspan="4">Failure Rate Avg. # Queries</td></tr><tr><td/><td>∞</td><td>2</td><td>∞</td><td>2</td></tr><tr><td>Attack</td><td/><td/><td/></tr><tr><td>Bandits T D</td><td colspan="2">0.95 0.39</td><td>432.24</td><td>1201.85</td></tr><tr><td>NES</td><td colspan="2">0.37 0.67</td><td>312.57</td><td>496.99</td></tr><tr><td>Rand</td><td colspan="2">0.20 0.89</td><td>422.16</td><td>1018.17</td></tr><tr><td colspan="5">SignHunter 0.07 0.21 121.00 692.39</td></tr><tr><td>ZOSignSGD</td><td colspan="2">0.37 0.80</td><td>161.28</td><td>528.35</td></tr></table>

Summary of attacks effectiveness on IMAGENET under ∞ and 2 perturbation constraints, and with a query limit of 10, 000 queries. The Failure Rate ∈ [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. Figure7: Performance curves of attacks on MNIST for ∞ (first column) and 2 (second column) perturbation constraints. Plots of Avg. Loss row reports the loss as 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 sign q * , computed as 1 -||sign(ĝ) -q * || H /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 a successful attack up to the query limit of 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 is to the bottom right of the plot. Figure8: Performance curves of attacks on CIFAR10 for ∞ (first column) and 2 (second column) perturbation constraints. Plots of Avg. Loss row reports the loss as 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 sign q * , computed as 1 -||sign(ĝ) -q * || H /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 a successful attack up to the query limit of 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 is to the bottom right of the plot.

Table content: <table><tr><td/><td colspan="4">Failure Rate Avg. # Queries</td></tr><tr><td/><td>∞</td><td>2</td><td>∞</td><td>2</td></tr><tr><td>Attack</td><td/><td/><td/></tr><tr><td>Bandits T D</td><td colspan="4">0.07 0.11 1010.05 1635.55</td></tr><tr><td>NES</td><td colspan="2">0.26 0.42</td><td colspan="2">1536.19 1393.86</td></tr><tr><td>Rand</td><td colspan="2">0.72 0.93</td><td>688.77</td><td>418.02</td></tr><tr><td colspan="3">SignHunter 0.02 0.23</td><td colspan="2">578.56 1985.55</td></tr><tr><td>ZOSignSGD</td><td colspan="2">0.23 0.52</td><td colspan="2">1054.98 931.15</td></tr></table>

Leaderboard of the MNIST black-box challenge. Adapted from the challenge's website-as of May 15, 2019.

Table content: <table/>

Leaderboard of the CIFAR10 black-box challenge. Adapted from the challenge's websiteas of May 15, 2019.

Table content: <table/>

Top 1 Error Percentage. The numbers between brackets are computed on 10,000 images from validation set. The rest are from(Tramèr et al., 2017a, Table 4).

Table content: <table><tr><td>Model</td><td>clean</td><td>Max. Black-box</td><td colspan="2">SignHunter after 20 queries after 1000 queries</td></tr><tr><td colspan="2">v3 adv-ens4 24.2 (26.73)</td><td>33.4</td><td>(40.61)</td><td>(90.75)</td></tr></table>

Peer review (iclr2020):
Summary: This 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_ with existing sign-based optimization schemes in the literature, and demonstrate the advantages of _SignHunter_. Main Comments: - 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). - 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. - 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. References: 1. Hazan, Elad, Adam Klivans, and Yang Yuan. *Hyperparameter optimization: A spectral approach.* ICLR (2018).