Year: 2021

Abstract:
A recent branch of the black-box adversarial attack literature has recognised the benefits of incorporating both the surrogate gradient information usually associated with transfer-based methods and the flexible query-based numerical optimisation typical of score-based methods. However, we find that existing approaches of this type underperform their potential, and can be overly complicated besides. Here, we provide a short and simple algorithm which achieves state-of-the-art results by attempting iterative ascent in the direction of the surrogate’s loss gradient, and, only when that fails to proceed, sampling alternative search directions from the coimage of the surrogate’s local linearisation, i.e. its Jacobian’s row space. The former directions produce very low query counts, while the latter serve as a backup for the cases in which more direct transfer fails, delivering very low failure rates. Beyond the fact that this serves as a fast and practical attack when scores and surrogates are available, our experiments demonstrate the empirical correctness of the method’s assumption that the studied networks are in an important sense learning similar functions to one another, making the attack problem under this threat model easy.

heading: 1 INTRODUCTION
text: The paper that introduced adversarial examples in computer vision (Szegedy et al., 2014) also initiated the study of their transfer across models. Accordingly, the first papers to propose black-box attacks (Papernot et al., 2017; Liu et al., 2017) did so within a transfer-based framework, typically using a simple “fast-gradient” optimisation with gradients supplied by a surrogate model. This allowed them to assume nothing about the attacked models except their input and output domains and, of course, that they would return the top predicted class for a given input image. This stood in contrast to white-box (or “first-order oracle”) approaches, e.g. Goodfellow et al. (2014); Moosavi-Dezfooli et al. (2016); Carlini & Wagner (2017), which assumed full knowledge of the victim model (notably its gradients) while typically seeking to minimise the norm of the adversary and/or the compute time spent finding it. The transfer-based black-box methods instead assumed comparable knowledge of the surrogate, whether provided directly, trained on a similar data distribution, or constructed iteratively by matching the observed behaviour of the victim over repeated queries to it. While these methods demonstrated that some amount of transfer between different networks was feasible, the field widely acknowledged that they fell short of reliable success, and sought alternatives.
Chen et al. (2017) and Bhagoji et al. (2018) introduced a modification of the threat model: they assumed the victim to provide not only the top class prediction, but also the scores/confidences of the candidate classes. This relaxation allowed for doing away with the need to acquire or construct surrogates of the victim, instead using numerical query-based methods to estimate the victim’s gradients directly. These approaches and their many descendants are called “score-based” attacks, operating within the “zeroth-order oracle” setting. The common problem they all face, noted in the seminal works above, is that direct numerical estimation of gradients is linear in the dimension of the input space. Depending on the input image resolution, this ranges from being costly to being infeasible. Thus, a core issue in score-based attacks is the need to limit the query count without compromising the quality of the gradient estimate: in Chen et al. (2017) alone, proposals included coordinate descent, basis transformation, coarse-to-fine optimisation, and priors on the gradient. The line of work which followed (Ilyas et al., 2018; 2019; Li et al., 2019; Liu et al., 2020; Guo et al., 2019b; Tu et al., 2019) explored ways to improve the fundamental approach by experimenting with different
optimisation methods and priors. Strikingly, and perhaps surprisingly, one of the most successful efforts was SimBA (Guo et al., 2019a), for “Simple Black-Box Attack”. Its name derives from the fact that it is an especially basic form of coordinate descent which achieves competitive results despite its deliberately simple approach: the greedy sequential assignment of signs to fixed-length steps along orthogonal basis directions.
Though query-driven score-based black-box attacks were proposed as an alternative to transfer methods, the two approaches are not incompatible with one another. They are actually complementary: a query-based strategy can benefit from search directions that are more promising a priori, and a transfer-based strategy can benefit from flexible optimisation that allows it to dynamically correct approximation errors and consider alternative hypotheses. This was first suggested in contemporaneous works by Cheng et al. (2019) and Guo et al. (2019b), which were followed by Tashiro et al. (2020) and Yang et al. (2020). In this paper, we argue that the core intuition of this branch of literature is sound. However, we also argue that when combining transfer- and query-based approaches, it is crucial to recognise that the failure of surrogate gradient transfer is generally overestimated, even by approaches which leverage it. Transfer generally succeeds: it merely requires an occasional source of appropriately chosen alternative hypotheses in order to avoid optimisation failure. It is this core insight that enables us to propose a simple but powerful new algorithm which achieves state-of-the-art results against the most modern competing methods on this problem, under their own experimental setup of minimising the number of queries required to identify `2-norm-bounded adversarial perturbations. We call our approach “GFCS: Gradient First, Coimage Second”.
Our approach is straightforward in both principle and implementation. Each iteration, it attempts up to two fixed-length steps along a given direction, as in Guo et al. (2019a). So long as it yields a successful update, this candidate direction is simply the normalised adversarial loss gradient of a surrogate model. If the method is unable to accept any step in this direction, it instead samples randomly weighted sums of surrogate class-score gradients until one such direction yields a successful update, at which point it reverts to using surrogate adversarial loss gradients as before. All of the “backup” direction proposals are thus drawn from the row space of the surrogate’s Jacobian, which is called the “coimage” of the linearised surrogate. Intuitively, this represents the subspace of directions at the current point that the surrogate has any response to at all. As we demonstrate, GFCS is able to overwhelmingly rely on surrogate loss gradients, a fact which accounts for its extreme efficiency. The coimage search, on the other hand, plays a diversifying role which is necessary for achieving the method’s high success rate, but without imposing an excessive cost. This is possible because its dimension is bounded above by that of the network’s output space, and is thus generally drastically lower in dimension than the input image embedding space, e.g. 1000-D vs. 268203-D for the common ImageNet Inception-v3 implementation. Beyond the success of the attack in its own right, we note that existence of such a fast and effective attack which relies entirely on surrogate output gradients indicates that the studied networks are, in an important sense, very similar to one another. Given this fact and its implications for working with these networks under this threat model, we believe the community should carefully evaluate how it wants to approach this problem in the future.

heading: 2 RELATED WORK
text: Cheng et al. (2019) and Guo et al. (2019b) were the first to, in their words, “bridge the gap between the transfer-based attacks and the query-based ones” in the score-based black-box context, noting that earlier methods “often suffer from low attack success rates (in the transfer case) or poor query efficiency (in the query-based case) since it is non-trivial to estimate the gradient in a high-dimensional space with limited information”. Guo et al. (2019b) did this by supplying a bandits optimiser (as used in Ilyas et al. (2019)) with surrogate gradient estimates at each iteration, diversifying the proposed search directions through the use of test-time dropout and drop-layer. Cheng et al. (2019) presented a variant of random gradient-free (RGF) optimisation using the surrogate gradient as a biasing prior (P-RGF) and featuring a dynamically estimated bias parameter, albeit one whose optimal value itself depends on the unknown target gradient. The Output-Diversified Sampling (ODS) approach of Tashiro et al. (2020) sampled gradients of randomly weighted logit sums over multiple surrogate models in order to generate search directions for variations on SimBA, RGF, and some Boundary Attack (Brendel et al., 2018) variants, demonstrating improvement over all of the base methods. Yang et al. (2020) also proposed a surrogate-enhanced version of SimBA (“SimBA++”), sampling candidate pixels to perturb according to the distribution specified by the corresponding magnitudes of the surrogate gradient components, as well as making periodic attempts to directly transfer surrogate gradients estimated using smoothing and momentum. When combined with “High Order Gradient Approximation”, a method for dynamically updating the surrogate by matching the first- and zeroth-order victim model behaviour, it is dubbed “Learnable Black-Box Attack” (LeBA).
In addition to the above, we review relevant works on black-box attacks, particularly score-based methods that use (possibly learned) prior information and/or alternative optimisers. When they feature a relevant concept, we also include variations of the Boundary Attack method of Brendel et al. (2018), which avoid requiring scores in exchange for much higher query counts:
Frequency/scale priors: As noted by (Chen et al., 2017; Bhagoji et al., 2018), in order to be practical, any black-box method that relies on gradient estimation must have an approach to effectively reduce the intrinsic dimension of the estimate space. Guo et al. (2019a; 2020) use low-frequency DCT dimensions for this purpose. The Boundary Attack variant of Brunner et al. (2019) uses Perlin noise similarly, and the Gaussian smoothing of the gradient in Yang et al. (2020) is conceptually related. Also closely related to the low-frequency prior is the use of spatial downsampling, whether applied to the image or its gradient, and whether implemented through pooling, interpolation, or striding: Tu et al. (2019); Ilyas et al. (2019); Li et al. (2019); Wang et al. (2021) all involve a version of it. Coarse-to-fine approaches, in which results at a coarser scale either solve the problem or initialise the optimiser of a finer one, appear in Moon et al. (2019); Al-Dujaili & O’Reilly (2020).
Data distribution modelling: Li et al. (2019) assumes the ability to parametrically model an adversarial distribution in the vicinity of the input point. Dolatabadi et al. (2020) replaces this parametric model with a normalising flow model trained on clean data. Tu et al. (2019) represents the data using an autoencoder and conducts the attack in its latent space. Huang & Zhang (2020) likewise conducts a latent-space attack, but in that of an encoder-decoder network trained to output adversaries on a source network. Ru et al. (2019) attempts to learn the latent-space dimension itself.
Attention: Wang et al. (2021) uses the output of CAM (Zhou et al., 2016) on a proxy net as a map of pixels to attack. In Brunner et al. (2019), a similar map is derived from the difference between the adversarial and original images, and used to weight the sampled perturbation elementwise.
Gradient/feature priors: The use of gradient priors in Guo et al. (2019b); Cheng et al. (2019); Tashiro et al. (2020); Yang et al. (2020) is discussed above, and the transfer-based approaches Papernot et al. (2017); Liu et al. (2017) are of course fundamentally based on this. Besides these, the method of Brunner et al. (2019) uses the gradient of a surrogate model to bias the orthogonal perturbation used in Boundary Attack, stating, “even surrogate models that are too weak for direct transfer attacks can be used in our framework”. Yan et al. (2021), also a Boundary Attack variant, attempts to learn to mimic the gradients of a victim net using a customised pre-trained policy network. Huang & Zhang (2020) learns a latent space of transferable adversarial features from its surrogate. Andriushchenko et al. (2020) supplies a bespoke feature bank which essentially transfers empirical domain knowledge (i.e. features determined to be likely to fool CNNs), both in the initialisation (vertical stripes) and the feature choice (homogeneous squares in the `∞ case, pairs of opposite-signed “decaying peaks” in the `2). Sahu et al. (2020) attempts to perform a “black-box FGSM” by learning correlations between
components of the loss function gradient within a Gaussian Markov random field framework. The “gradient priors” of Ilyas et al. (2019) essentially amount to momentum and downsampling, and do not represent the sort of “flexible gradient transfer” we are otherwise discussing here.
Optimisation algorithms: Again, a standard optimisation framework for black-box score-based attacks is ascent on gradients estimated via numerical derivatives in guessed directions, possibly using enhancements such as priors and/or simplifications such as coordinate ascent. We consider the aforementioned SimBA variants (including the method we present) to essentially be of this type. Variations on or alternatives to this approach have included bandits (Ilyas et al., 2019; Guo et al., 2019b), Natural Evolution Strategies (NES) (Li et al., 2019; Huang & Zhang, 2020; Dolatabadi et al., 2020) evolutionary algorithms (Liu et al., 2020; Wang et al., 2021), Bayesian optimisation (Ru et al., 2019; Shukla et al., 2019), and training of a policy network by REINFORCE (Yan et al., 2021). Al-Dujaili & O’Reilly (2020) uses a custom “flip/revert” approach based on checking the overall effect of grouped sign changes to pixel perturbations. Assuming submodularity, Moon et al. (2019) uses the max-heap-based “local search algorithm” to alternate between greedily inserting and removing elements defining a partition between oppositely signed perturbation pixels. Shi et al. (2019) comprises a set of heuristics meant to reduce the norms of attacks based on transfer from surrogate models: many of these are in principle applicable to attack vectors obtained otherwise.

heading: 3 METHOD

heading: 3.1 PRELIMINARIES
text: The adversarial attack problem appears in slightly different variations. Generally, given a classifier function f(x) : X → Y , the goal is to supply an adversarial example xadv ∈ X which, while “near” to a given xin under some definition, is such that f(xadv) differs from f(xin) in a particular noteworthy way. In image classification, we typically have the situation that X = RD and Y = RC , with f a network mapping aD-dimensional input image to aC-dimensional class-score/logit vector. The untargeted attack objective, then, is argmaxc f c(xadv) 6= argmaxc f c(xin), i.e. that the top predicted class of xadv is different from that of xin. The targeted attack objective is argmaxc f c(xadv) = t, meaning that the net predicts a specific target class t other than the original prediction argmaxc f c(xin).
As the subfield has expanded to consider perturbation classes including non-rigid deformation (Xiao et al., 2018), semantically insignificant distortion (Hosseini & Poovendran, 2018; Brown et al., 2018), and movement within the estimated natural image manifold (Zhao et al., 2018; Hendrycks et al., 2021), corresponding definitions of adversarial perturbation magnitude have been adopted, including total variation and manual human assessment. The most common measure, used by all methods to be compared against in this paper, is ‖xin − xadv‖p, with p ∈ {2,∞}: here, we use p = 2.
In some experimental setups, the attacker’s goal is to satisfy the adversarial objective while minimising the perturbation magnitude. In others, it is to minimise the number of network evaluations performed while finding any adversarial example with a perturbation magnitude within a pre-specified bound. In black-box attacks, the latter setup is common, with “evaluations” being defined as queries to the victim model: this is likewise our focus.

heading: 3.2 ALGORITHM
text: The entirety of the proposed method is given in pseudocode as Algorithm 1. As indicated in Sec. 3.1, the method takes a victim classifier v, an input image xin, and a norm bound ν. The projection operator Πxin,ν confines its input to the ν-ball centred on xin: its inclusion in the algorithm represents a standard projected gradient ascent (PGA) implementation. Additionally, the method requires a loss function L, a set S of one or more surrogate models, and a step length representing the fixed length of the perturbations to be attempted at each iterate1 along its candidate direction. The loss L can be any function of the iterate that serves as a suitable proxy for the adversarial objective, as in Sec. 3.1: the only requirement here is that it be once differentiable. In our implementation, we make the popular and effective choice of the margin loss Lf (x) = f ct(x)− f cs(x) where cs = argmaxc vc(x) and ct = argmaxc 6=cs vc(x), i.e. the difference between the highest and second-highest (or, in the targeted case, the target) class scores. Note that the class IDs ct and cs are defined by the ranking
1In optimisation, this term refers to any given intermediate value of the variable being optimised.
Algorithm 1 GFCS: Gradient First, Coimage Second 1: Input: A targeted image xin, loss function L, a victim classifier v, a set of surrogate models S , a
step length , and a norm bound ν. 2: Output: adversarial image xadv within distance ν of xin 3: xadv ← xin 4: Srem ← S 5: while xadv is not adversary do 6: if Srem 6= ∅ then 7: Randomly sample surrogate model s from Srem 8: Srem ← Srem \ s 9: q← ∇xLs(xadv)‖∇xLs(xadv)‖2
10: else . None of the surrogate loss gradients work, so revert to ODS. 11: Randomly sample surrogate model s from S 12: Sample w ∼ U(−1, 1)C 13: q← dODS(xadv, s,w) . See Eqn. 1 for definition. 14: for α ∈ { ,− } do 15: if Lv(Πxin,ν(xadv + α · q)) > Lv(xadv) then 16: xadv ← Πxin,ν(xadv + α · q) 17: Srem ← S . Reset candidate surrogate set to input set; resume using loss gradients. 18: break
according to v, but are evaluated on the net f parametrising the loss, which is either s or v depending on the line of the algorithm (9 and 15, respectively). The natural assumption of a surrogate method is that the surrogate will provide useful information about the victim, but there is no “hard” requirement on the surrogates s ∈ S other than being once-differentiable functions mapping X → Y . The definition of ODS direction dODS for network f and input x is, as in Tashiro et al. (2020),
dODS(x, f ,w) = ∇x(wᵀf(x)) ‖∇x(wᵀf(x))‖2 , (1)
where w is sampled from the uniform distribution over [−1, 1]C . By definition, it is the normalised gradient of a randomly weighted sum of all of the class scores. Equivalently, by linearity, it is a randomly weighted sum of all of the class-score gradients (i.e. rows of the Jacobian matrix), which are themselves a basis of the coimage of the linear approximation of f : the subspace which f exhibits any nonzero response to.
As covered in Sec. 1, the logic of the method is simple. At any given iterate, the method tries to proceed in a SimBA-like manner by testing the change in adversarial loss at fixed-length steps along candidate directions, projected back into the feasible set where necessary. It does so exclusively using normalised loss gradients from the surrogates in the input set (drawn in random order, without replacement), unless and until it has exhausted them at that iterate without success‘. As we will demonstrate in Sec. 4.2, this intermediate failure state is seldom reached. If this state is reached, however, the method instead randomly samples a surrogate (with replacement) and an ODS direction on that surrogate, attempting a SimBA update each time, until an improvement in the loss is realised. Once such a successful update occurs, the method refreshes the working set of surrogates and resumes using normalised loss gradients only. The method terminates on finding an adversarial example or on exceeding an upper bound on the query count if one has been specified.

heading: 4 EXPERIMENTS

heading: 4.1 UNTARGETED ATTACKS
text: Experimental setup: We compare GFCS to the methods of Cheng et al. (2019); Tashiro et al. (2020); Yang et al. (2020) by designing an experimental framework covering the key aspects of the original experiments in the respective source works. We use each method to perform `2-norm-constrained untargeted attacks against the same 2000 randomly chosen correctly classified ILSVRC2012 validation images per victim network. A maximum query count of 10000 is set per example (beyond which
failure is declared), and the `2 bound (enforced using PGA) is set to the commonly chosen √
0.001D, where D is the image dimension in the victim network’s native input resolution. The victim networks are the commonly chosen VGG-16 (with batch norm), ResNet-50, and Inception-v3. The experiments are repeated for each of two choices of surrogate set: ResNet-152 alone (as in Cheng et al. (2019); Yang et al. (2020)), and the set {VGG-19, ResNet-34, DenseNet-121, MobileNet-v2}, as in Tashiro et al. (2020). The latter is omitted for LeBA (Yang et al., 2020), which does not admit non-singleton surrogate sets. All networks used are pretrained models available via PyTorch/torchvision. Parameter values of competitors are as they specify except where we note otherwise for reasons that will be discussed below. LeBA is run in “train” mode on a held-out set of 1000 images and then evaluated in “test” mode on the same set of 2000 used for all other methods. P-RGF always uses the adaptive coefficient mode. P-RGF and ODS-RGF are based on our own PyTorch port of the reference P-RGF code, which will be released along with this paper: no public implementation of ODS-RGF currently exists otherwise. We include the surrogate-free (Andriushchenko et al., 2020) for comparison.
Results: Table 1 reports attack success rates and median query counts, and Fig. 2 plots cumulative success counts against the maximum queries spent per example (CDFs, modulo normalisation). We do not report means, as these are inappropriate for summarising the long-tailed distributions resulting from these methods. Uncertainty is represented as standard error in Table 1 and by 95% confidence intervals in Fig. 2, in both cases having been obtained via bootstrap sampling. Two things are readily apparent in Table 1. First, all of the studied methods have very high success rates on this problem, against all of the victim networks: the lowest rate observed is 98.50% for SimBA-ODS on Inception-v3 with ResNet-152 as the lone surrogate. Second, GFCS incurs an extremely low median query count while achieving a similarly high success rate to all other methods. This fact can be seen in more detail in the single-surrogate results of Figs. 2a, 2b, and 2c, in which GFCS clearly dominates the low-query regime, and even more strikingly so in the multi-surrogate Figs. 2d, 2e, and 2f. This is despite GFCS’s simplicity: compare Alg. 1 against, for example, LeBA’s training of its surrogate in a separate step. Note that our choice of SimBA-ODS as the coimage sampler is partly about simplicity: as the results demonstrate, a very small number of failures are expected when it is used on its own, and we effectively inherit them. At the cost of a bit of added complexity in the implementation, e.g. ODS-RGF could be substituted, and would likely lead to further improvements in both the failure rates and query count curves, while still representing a form of GFCS. There is an additional phenomenon of note: Table 1 also demonstrates the dependence of the performance of existing methods on their own choices of parameter values. Strikingly, almost all of the empirical benefit of ODS-RGF over the earlier P-RGF is due to the different choice of default parameters in the respective methods: when P-RGF simply uses the default parameters of ODS-RGF, it actually considerably outperforms it in terms of median query count on ResNet-50, at the cost of a 0.05%
increase in failure rate. SimBA-ODS benefits dramatically from an order-of-magnitude increase in its step-size parameter. This, in and of itself, serves as further evidence of our central thesis that transfer is generally pursued too timidly in this context. Of course, one can be too aggressive: see the ablation lines in the table representing the exclusive use of loss gradients, i.e. “GF without the CS”.

heading: 4.2 ANALYSIS OF ALGORITHM BEHAVIOUR
text: To delve deeper into the results of Sec. 4.1, we plot each attacked example as a 2D point whose x-coordinate is the number of queries expended by the surrogate loss block of the algorithm, and whose y-coordinate is the analogous count for the coimage block. This gives the scatter plot of Fig. 3, which is supplemented by marginal histograms corresponding to the axes opposite them. The figure shows results obtained using Inception-v3 as the victim: see Appendix A.3 for analogous figures for VGG-16 and ResNet-50. Note that the axes of the main scatter plots are log-log, while those of the marginal histograms are linear-log. Some phenomena are readily evident. For one, there is a large fraction of examples (represented by the dense horizontal rows of dots at the bottom of the plots) that succeed within a very low number of queries (on the order of 1-10), which are entirely or almost entirely due to the surrogate gradient transfer, with ODS used seldom or not at all. As these low-query clusters are extremely dense, the corresponding marginals should be consulted (best under zoom) in order to quantify them. For another, the number of examples outside of this regime falls considerably when the four-surrogate set is used instead of ResNet-152 on its own, as can be
seen by comparing the left and right sides of the figure. It is clear that the examples that rely on the interplay between the gradient- and coimage-based direction generators are reduced to a nontrivial (i.e. sufficient to affect the failure rate if not handled) but nonetheless relatively small group. Overall, there is an order-of-magnitude difference between surrogate loss gradient queries and ODS queries in the points extending away from the dense low-query cluster at the bottom, i.e. the examples that rely on both submethods. That is, when the ODS block is required, it typically requires far more queries to progress the optimiser than in the much more common cases in which the gradient suffices.

heading: 4.3 TARGETED ATTACKS
text: We also test our method in the targeted attack scenario. The setup is the same as in Sec. 4.1, except as noted otherwise. For these experiments, instead of the margin loss, we use the log loss of the targetclass softmax score, as is often chosen for targeted attacks: Lf (x) = log pt, where pt = e
ft(x)∑ c e fc(x) .
That is, the goal of the attacker is to push the target-class confidence up at the expense of all other classes generally, rather than suppressing a specific source class. We perform multiple runs for each setting, with the target class for each image chosen at random (uniformly) from all ImageNet classes other than the ground truth. Neither Cheng et al. (2019) nor Yang et al. (2020) provide results or code for targeted attacks. While Tashiro et al. (2020) report targeted attack numbers for both P-RGF and their own ODS-RGF, no supporting implementation is available. As noted before, our own P-RGF and ODS-RGF results in Sec. 4.3 were produced using a port of the public P-RGF repository, which only supports untargeted attacks (a restriction that carries through to the ODS-RGF modification we have made to it). We thus work with the provided SimBA-ODS implementation, comparing it in isolation to GFCS, in which it serves as the backup method. The results are displayed in Fig. 4. As can be seen, even under this more difficult attack scenario, under which the more aggressive transfer strategy of GFCS might be expected to suffer, our method retains its considerable advantage.
While the targeted attack method of Huang & Zhang (2020) is both powerful and conceptually related, it is architecturally tied to the `∞ norm in its given formulation, and thus not appropriate for our `2-bound comparisons. Further, given a trained surrogate, the method requires that one then train the method’s adversarial encoder-decoder network on a held-out validation set: in the case of targeted attacks, this must be done per target class, as acknowledged by the authors in the original work. Our approach, by contrast, uses the surrogate directly without any issue, on any target class.

heading: 4.4 ON THE IMPORTANCE OF INPUT-SPECIFIC PRIORS
text: Our approach, and the ones we compare against, are all based on priors that are conditioned on the iterate, i.e. gradient information evaluated at the current point. SimBA, on the other hand, effectively encodes location-independent prior information in the form of the basis matrix from which it draws its search directions, and, if appropriate, a prior ordering strategy for searching them. An example, which has been used in other works as well (see Sec. 2), is the low-frequency DCT basis, which can follow specific orderings if desired. It is well known that there is a sense in which adversariality is locationindependent, as in Moosavi-Dezfooli et al. (2017). However, location-specific adversaries can be found with much lower norms (Moosavi-Dezfooli et al., 2016; Carlini & Wagner, 2017) when local information is taken into account, even under simple linear assumptions. It is thus clear that while it
is important to understand the points made in the universal adversary literature, local information is nonetheless key to finding optimal adversaries. Thus, it is interesting to try to identify what sorts of limits are reached in confining oneself to location-independent priors: here, we investigate this in the context of SimBA. We propose a variant called “SimBA-PCA”, which is defined by the approach it takes to generating the SimBA basis matrix. Following the method used in Moosavi-Dezfooli et al. (2017); Jetley et al. (2018), we gather adversarial examples2 over a sample input set as columns in a matrix, then compute that matrix’s SVD. That is, we produce the ordered set of vectors that would be expected to represent the `2-optimal basis for reproducing the adversarial examples on the given set, when constrained to follow SimBA’s iterative adversary-building optimisation procedure. We then compare this against SimBA using both the canonical pixel and DCT bases in random order, and GFCS. An an interesting aside, we also include the result of using the procedure on raw images directly, i.e. using the principal components of the input data as the search directions. All of these methods are placed within the same norm-bounded PGA framework.
Fig. 5 demonstrates the results of this experiment. As predicted, the gradient-based basis (“SimBAPCA-gradients”) comfortably outperforms the canonical pixel basis (“SimBA pixel”), as well as the principal image components (“SimBA-PCA-images”), the latter fact indicating that the information encoded in adversarial directions indeed goes beyond simple correspondence to modes of data variation. Note, though, that the principal data directions do outperform the naı̈ve pixel basis, unsurprisingly revealing nontrivial correlation between modes of data variation and features learned by the network. However, despite forming a “natural adversarial basis”, the adversarial singular vector matrix does not outperform the DCT basis: their results are very close, but if anything, the DCT basis slightly outperforms. That is, the DCT basis with a suitably tuned frequency count appears to already represent the limit of what a SimBA-style iteration through a single fixed orthonormal basis can accomplish, and the SimBA-PCA procedure has at best recovered an equivalent to it. GFCS, on the other hand, is far more efficient than all of the compared methods, demonstrating the performance that is available when it is possible to condition the prior on the iterate, i.e. to use local gradient information. This is one way of viewing why it is that the use of surrogates is as powerful as it is.

heading: 5 CONCLUSION
text: We have demonstrated that score-based attacks using surrogates are in fact easy. By “easy”, we mean that a very high success rate is achievable within a very low number of queries to the victim model, using an algorithm that is simple to both describe and implement: GFCS. Further, that algorithm is based on a fairly direct type of transfer: it relies first and foremost on transfer of loss gradient directions from the surrogate to the target, falling back to transferring other combinations of features locally significant to the surrogate. One implication of this is that all of the examined surrogate and target networks are in fact similar to one another in the sense that the algorithm not just assumes, but entirely relies on. An interesting avenue for future work is to determine whether there are noteworthy situations in which the assumption of good feature transfer no longer holds, and the attack no longer suitable: this will be tantamount to identifying classes of networks that genuinely learn distinct responses from one another.
2We have experimented with various methods of generating the source adversaries, all of which yield indistinguishable results. Here, we simply use the gradients of random class scores.

heading: ETHICS STATEMENT
text: Our work introduces a novel (and very effective) black-box attack. As with all adversarial attacks, the method exposes a way of getting a target/victim network to issue responses to inputs that are almost certainly unlike those intended by its designer. Therefore, were an actual harmful practical application of such an attack to be identified in which the assumptions of this method (i.e. that the victim exposes its decision scores, and that a viable surrogate can be found) were satisfied, the publication of this method could in principle facilitate it. As is it not currently well understood how to build useful networks that do not have the sorts of properties being exploited here, there is no straightforward “defence”. However, the primary perspective from which we approach this work is that of network analysis. A key goal is to make practitioners aware of potential risks their machine learning systems are exposed to, especially and most realistically unintended failure, and to motivate the community to design networks that are more robust, predictable, and comprehensible.

heading: REPRODUCIBILITY STATEMENT
text: Code and data: We accompany this submission with the code implementing the proposed GFCS method. The code includes, in a utility file, lists of IDs of the ImageNet validation images used in the experiments, to allow full reproduction. Note that Algorithm 1 itself presents a complete and implementable description of the algorithm. On acceptance, we will also publicly release all code needed to reproduce all of the plots and tables in our paper. Finally, after correspondence with the maintainers of the codebases of methods we have compared against, we will also release forked versions with the small changes necessary to standardise the results against one another.
Statistical significance: As described in Sec. 4.1, we report uncertainty for the results of all the reported methods, for all of the experiments. Moreover, we double the size of the test set typically used in the literature (and keep it fixed across competing methods).
Hyperparameters: Our method contains a single tunable hyperparameter (the step length ). As discussed in Appendix A.4, we chose its value on a held-out set and kept it fixed across all of the experimental configurations. For the competing methods, we use the provided source code and the default hyperparameters, alongside any hyperparameter choice we found to work better than the default(s). For instance (see Appendix A.4), for SimBA-ODS, we found that = 2.0 is significantly better than = 0.2, which is the default used in Tashiro et al. (2020).

heading: A APPENDIX

heading: A.1 COIMAGES AND DIMENSION REDUCTION
text: The assumption of local linearity is ubiquitous in the study of deep networks, and particularly adversarial attacks on them. A simple way of explaining the upper bound on the dimension of the coimage of a network’s linear approximation is through the rank-nullity theorem. This points out that for linear transformation T mapping finite-dimensional vector space V to vector spaceW , rank(T ) + nullity(T ) = dim(V), where rank(T ) := dim(image(T )) and nullity(T ) := dim(kernel(T )). That is to say, the dimension of the input subspace that has any effect on the output (rank(T )) is no greater than that of the output space (because dim(image(T )) ≤ dim(W)), and the dimension of the input subspace that has no effect on the output (nullity(T )) is at least equal to the difference between the input and output dimensions (because nullity(T ) = dim(V)− rank(T ) ≥ dim(V)− dim(W)). To make this more concrete, in the case of a standard ImageNet Inception-v3 network, V = R299∗299∗3 and W = R1000, and so in the linear approximation, rank(T ) = dim(coimage(T )) ≤ 1000, and nullity(T ) ≥ 267203. Under the assumption that the features to which a surrogate is locally sensitive will largely transfer to a target network, naı̈ve search of the input space is thus extremely wasteful.
This is the key issue which limits the preprint of Ma et al. (2020), which contains some similarities to our method in its preference for surrogate gradient transfer within a SimBA-like optimisation context. The crucial difference lies in their attempt to use standard RGF gradient estimation in order to progress optimisation when surrogate loss gradients fail, thus falling prey to the inherent issue with estimating gradients in high-dimensional input spaces pointed out in this context as far back as Chen et al. (2017). The dramatic difference in result quality between the two methods owes to this fact.
A.2 IMPLEMENTATION DETAILS
As explicitly written in Alg. 1 and discussed in Sec. 3.2, the SimBA-style search is done within a standard PGA projection of the update candidate onto the feasible set, to avoid the common evaluation issue in the literature in which SimBA is punished ex post facto for violating a norm bound that the method was not originally designed to account for. Our method thus avoids this issue by design, but we further note that none of the evaluations we perform on other methods involve this sort of practice: if a bound is to be imposed, a method should always be modified in a straightforward manner to account for it, rather than being deemed to have failed after the fact.
On the other hand, our study of the implementations of competing methods has shown that some of them unnecessarily hobble their own performance by using surrogates with domains that differ from that of the target model without appropriately including interpolation between the domains. This typically shows up when Inception-v3, which is trained to accept an input in R299∗299∗3, is attacked using networks with the more common input domain ofR224∗224∗3: adaptive pooling layers prevent crashing, but do not fix the issue of feature scale mismatch. As such, each surrogate in our method should be considered to contain an differentiable bilinear interpolation module as an initial layer, thus producing appropriately mapped gradients in the target domain on backpropagation. In the spirit of fair comparison, we implement this option for competitors as well. Additionally, as of this writing, the public LeBA implementation contains non-standard pre-processing of the input images: we replace this with standard practice, again to facilitate fair comparison against other methods.
Finally, note that when Lf (x) is the margin loss, its normalised gradient is just a special case of dODS(x, f ,w) in which wct ← 1, wcs ← −1, and wc 6∈{cs,ct} ← 0. In our experimental setup, all methods are run on sets of images that, while otherwise randomly selected from the ILSVRC2012 validation set, are guaranteed to be correctly classified by each target network. Thus, there is never any difference between cs and the ground-truth label in the untargeted attack case.

heading: A.3 ADDITIONAL RESULTS FOR SECTION 4.2
text: The scatter plots and empirical marginal distributions in Fig. 6 complete the results of Sec. 4.2 and Fig. 3 from the main paper, extending the same analysis to ResNet-50 and Inception-v3 architectures. A very similar trend can be observed: 1) most of the examples are successfully attacked with a handful of queries, 2) the low count is largely due to the surrogate gradient transfer, and 3) using four surrogates amplifies the two previous phenomena.

heading: A.4 ON THE STEP LENGTH
text: The simple method we propose in Algorithm 1 presents a single hyperparameter: the step length (line 14), which indicates the length of the perturbations to be attempted at each iterate along its candidate direction. We chose 2.0 as the default value for our experiments by performing a small grid search over a held-out set (disjoint from the 2000 examples used in the experiments of the main paper). Results for the three architectures used as victim (and ResNet-152 as the single surrogate) are shown in Fig. 7. Note that the figure has two y-axes and two sets of lines: solid and dashed lines should be considered looking at the axis on the left and right hand side of the plot, respectively. Clearly, better performance can be obtained by separately tuning this hyperparameter for each architecture. Instead,
we simply chose a fixed value that is reasonable for all models and for both query count and success rate. Note also how it is possible to achieve an even lower query count if one is willing to sacrifice about 1% of the success rate.
We observed that this choice of is also significantly better than the default one made by SimBAODS (Tashiro et al., 2020) (i.e. 0.2), and have reported results for both in our experiments.
A.5 EXPERIMENTS WITH `2 NORM BOUND ν = 5.0
We repeat the experiments of Sec. 4.1 (whose results are displayed in Fig. 2), only instead using the norm bound of ν = 5.0 sometimes used in `2 adversarial attack experiments on ImageNet networks with input domains of size [224, 224, 3], such as VGG-16 and ResNet-50. This is roughly a factor of 2 smaller than the bound of ν = √ 0.001D used by our competitors and ourselves in the main experiments. The results of this experiment are given in Fig. 8. We see, as before, that GFCS comfortably dominates the low-query regime in all cases. In the single-surrogate cases, both GFCS and SimBA-ODS saturate at a slightly lower success rate than some competitors, including ODS-RGF. As already pointed out in Sec. 4.1, GFCS uses SimBA-ODS as its coimage sampler for the sake of simplicity, and inherits a small number of failure cases from it in some circumstances. This can easily be alleviated in exchange for a bit of additional complexity in the algorithm’s implemention by using ODS-RGF to do coimage sampling.

heading: A.6 EXPERIMENTS ON CIFAR-10
text: We again re-perform the main untargeted attack experiment, this time using CIFAR-10 as the dataset, with the target and surrogate networks sourced from https://github.com/akamaster/ pytorch_resnet_cifar10. We use ResNet-110 as the target, and the much simpler ResNet-20 as its single surrogate. The `2 norm bound is again set to ν = √ 0.001D, which for CIFAR-10 ≈ 1.75. Fig. 9 demonstrates the results. All methods completely solve the problem well within the 10K query limit: we focus the plot on the first 500 queries. This problem is easier than the main ImageNet version studied in this work, but GFCS nonetheless retains its relative dominance.

heading: A.7 ATTACKING A HARDENED NETWORK
text: As a final additional experiment, we repeat the four-surrogate untargeted attack of Sec. 4.1, using the adversarially trained Inception-v3 of Kurakin et al. (2017) (as provided by https://github. com/rwightman/pytorch-image-models) as the victim. The test set in this case consists of 800 ImageNet images correctly classified by the victim model. This model has been hardened on single-step adversarial attacks, and, as acknowledged by Kurakin et al. (2017) in their original presentation of it, is vulnerable to iterative white-box attacks. As we demonstrate in Fig. 10, it is also vulnerable to well-designed score-based black-box surrogate attacks, with GFCS again proving the most efficient of the attack methods.

heading: A.8 BREAKDOWN ANALYSIS FOR TARGETED ATTACKS
text: Fig. 11 depicts the query breakdown for the targeted attack experiment of Sec. 4.3. Fig. 4 has already demonstrated that GFCS outperforms its competitors dramatically on this problem: the breakdown sheds light on how it is able to solve this difficult problem efficiently. The trend is broadly similar to that in the analogous plots for the untargeted attacks: a large number of examples are solved entirely using loss gradient transfer, while the others rely on the backup at least some of the time. What is remarkable about this plot relative to those of the untargeted attacks is that the large number of loss-gradient-only examples are a large minority: more of the 1000 attacked images require some use of coimage sampling than do not, in this case. The loss-gradient transfer is crucial to the dramatic outperformance of SimBA-ODS seen in Fig. 4, while the use of SimBA-ODS as a backup is critical in preventing the overall method from failing the majority of the time.

Review summaries:
The paper proposes a new simple black-box adversarial attack algorithm, which utilizes surrogate models. The algorithm attempts iterative ascent in the direction of the surrogate’s loss gradient, and when the attempt fails, the algorithm searches alternative directions by exploiting the surrogate’s Jacobian’s row space. The experiments show that the proposed algorithm produces very low query counts with low failure rates, compared to existing baselines.

This work presents an adversarial attack in the black-box setting where an adversary has access to only logit outputs from the target model. The proposed approach combines the ideas from transfer-based attacks and zeroth-order optimization methods for score-based attack methods. Experiments on multiple architectures show that the proposed approach is query efficient while achieving similar success rates compared to recent approaches.  

This paper is devoted to the problem of generating adversarial examples to the predictions of machine learning models. That is, given an instance predicted by a target ML model one way, the paper aims at detecting another instance that is relatively close to the given one but such that the prediction of the model for the new instance is different. The paper proposes a novel adversarial attack algorithm, which behaves as twofold: (1) it tries to apply iterative ascent in the direction of the surrogate's loss gradient until it can and then (2) samples alternative directions from the coimage of the surrogate's local linearisation. The new approach is claimed to be a fast and practical attack as it significantly outperforms the competition in terms of the number of queries needed to generate adversarial examples successfully.