Attacking deep networks with surrogate-based adversarial black-box methods is easy
Authors: Nicholas A. Lord
Romain Mueller
Luca Bertinetto
Venue: ICLR 2022 Poster (2022)
Keywords: adversarial attacks
black-box attacks
network robustness
network analysis

Abstract: A recent line of work on black-box adversarial attacks has revived the use of transfer from surrogate models by integrating it into query-based search. 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 through a search which uses the surrogate network's class-score gradients, with no need for other priors or heuristics. The guiding assumption of the algorithm is that the studied networks are in a fundamental sense learning similar functions, and that a transfer attack from one to the other should thus be fairly "easy". This assumption is validated by the extremely low query counts and failure rates achieved: e.g. an untargeted attack on a VGG-16 ImageNet network using a ResNet-152 as the surrogate yields a median query count of 6 at a success rate of 99.9%. Code is available at https://github.com/fiveai/GFCS.

Published as a conference paper at ICLR 2022
ATTACKING DEEP NETWORKS WITH SURROGATE-BASED ADVERSARIAL BLACK-BOX METHODS IS EASY
Nicholas A. Lord, Romain Mueller & Luca Bertinetto
www. five. a
[nick, romain muml ler, lww.. bettebbeeeetettteeeee....ld
ABSTRACT
A recent line of work on black- adversarial attacks has revived the use of transfer from surrogate models by integrating it into query-based search. 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 taateoff-theards results through a search which uses the surrogate network's 's class- score gradients, with no need for other priors or heuristics. The guiding assumption of the algorithm is that the studied networks similar functions, and that a transfer attack from one to the other should thus be fairly "easy". This assumption is validated by the extremely low query counts and failure rates achieved: e.g. an untargeted attack on a VGG-16 ImageNet network using ResNet-152 the surrogate yields median query count of 6 at success rate of 99.9%. Code is available at https: /ttl:://giitaiee com wwtp://iivaai//G//
in fundamental sense learning
INTRODUCTION
The paper that introduced adversarial examples in computer vision (Szegedy et al. 2014) also initiated the study of their transfer across models. This directly yielded two parallel lines of research into "white- box" and "black-box" attacks on classification systems. The white- box attacks (e.g. Goodfellow et al. (2015): Moosavi-Dezzoolii al. (0016); Carlini & Wagner (2017)) assumed full knowledge of the victim model architecture and parameters, and would typically exploit the analytical gradients of the network outputs with respect to the input image. These methods were primarily concerned with demonstrating the existence of adversarial examples, as well as optimising criteria such as their norms or the time spent computing them. The earliest black-box attacks (e.g. (Papernot et al. (2017); Liu et al. (2017)), on the other hand, assumed no access to the attacked model beyond an end user's ability to input images and receive output classifications. They sought to produce adversarial examples on the victim model by transferring them from known surrogate model. This surrogate may have represented model trained separately on a comparable problem or one trained to mimic the victim through sequence of online queries; the transfer attack would typically comprise something as simple as single step in the surrogate gradient direction. These methods were concerned primarily with the discoverability and predictability of adversarial examples. The key assumption underlying this branch of study was that different ML architectures, when trained on sufficiently similar problems, would exhibit similar adversarial vulnerabilities at the same inputs. As has become better understood and explained since (Olah et al. 2017] Jetley et al.) [2018] 18 [lyas et al. 2019b), this is equivalent those networks learning similar feature responses to one another, i.e., learning similar solutions to the problem. Such attacks did demonstrate nontrivial success rates, and thus, the partial validity of that hypothesis. However, the field widely acknowledged that there were limits to their reliability, and sought alternatives with higher success rates.
To this end, Chen et al. (017) 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 candidate class scores. This relaxation eliminated the need for a surrogate, enabling the use of query-based methods to numerically estimate the victim's gradients directly. These approaches and their many descendants are called "base""" attacks. 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, core issue in based attacks is the need to limit the query count without compromising the

---

Published as a conference paper at ICLR 2022
Surrogate
Target
Direct trensfer (DT)
yo
ques
fails
Coimage satapling
Figure 1: Transfer of information from a surrogate to a target in GFCS: Gradient First, Coimage Second. A sequence of optimisation steps is taken through the loss landscape of the target model, as shown on the right. Each candidate direction is supplied by the surrogate in one of two ways: either through direct transfer of the surrogate's 's own gradient Yuur or 9co generated through a process of coimage sampling described in Sec. S.2. Arue is the target's 's true but inaccessible gradient. As shown in Sec. 3.2 the method relies mostly on the directly transferred S using the 9 to avoid failure.
quality of the gradient estimate: in Chen et al. (2017) alone, proposals included coordinate descent, basis transformation. coarse-to-fing optimisation, and priors on the gradient. The line of work which
followed (Iyya al. 2018 2019a Li al. 2019 Liu et al. 2020: Guo et al.) 20196 Tu 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., [201 for "Simple Black-Box Attack". Its name refers to 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: query-based strategy can benefit from search directions that more promising a priori, and transfer-basee strategy can benefit from a flexible optimiser that allows it to dynamically correct approximation errors and consider alternative hypotheses. This was first suggested in 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 Transfer typically succeeds: it just requires an occasional source of appropriately chosen alternative hypotheses within a sensible optimisation framework. It is this core insight that enables us to propose simple but powerful new algorithm which achieves state-of-the-att results against the most modern competing methods on this problem, under their own experimental setup of minimising the number of queries required to identify call our approach "GFCS: Gradient First, Coimage Second", as its search directions represent either the surrogate gradient of the adversarial loss itself, or, failing that, random choice from the row space of the surrogate Jacobian (called the "coimage")). The former case represents a standard transfer attack; the latter involves searching the space of features to which the locally linearised surrogate exhibits any response at all, and is itself generalised form of gradient transfer. The optimisation method is just SimBA (Guo et al. 2019a) variation within standard projected gradient ascent (PGA) context. Key to the method's ' efficiency is the identification of effective local search spaces of low dimension: in the case of the common ImageNet Inception-v? implementation, confining the search to the coimage reduces the dimension from 299 299 3 (the input resolution) to 1000 (the number of output classes). The loss gradient of course dinedimnni..
adversarial perturbations
specific networks. We
Whether a threat model which assumes access to both class scores and surrogates is realistic from a security perspective is a controversial question, and one we are agnostic to. Our interest in the problem is analytical, and we have two main points to make. First, if this threat model is to be considered to be of interest (as it has been in the prior art), then it should be understood just how "casy" the problem currently posed is: even a single surrogate reduces the query count to handful. Second, the fact that GFCS performs as it does while relying entirely on gradient transfer between networks demonstrates that those networks are, in an important sense, very similar to one another.
2

---

Published as a conference paper at ICLR 2022
2 METHOD
2.1 PRELIMINARIES
The adversarial attack problem appears slightly different variations. Generally, given classifier function f(x): X' - V/ the goal is to supply an adversarial example Xadv X which, while "near" to a given Xin under some definition, is such that ((xav)) differs from f(Xin) a particular noteworthy way. In image classification, we typically have the situation that X' C RD and ) C RC, with f network mapping D-dimensional input image to a C-dimensional class-score/logit vector. The un- targeted attack objective is argmax, (Xavv) & argmax, fe fx(Xm).. i... that the top predicted class of Xadv is different from that of Xin. The targeted attack objective is instead argmax, (x ) = t, mean- ing that the net predicts specific target class i. other than the original prediction argmax, (x.)).
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 Hendryyks 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, X Xadv with p E {2, bo here, we use p 2.
In some experimental setups, the attacker's s goal is 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 pre-specified bound. In black-bon attacks, the latter setup is common, with "evaluations" being defined as queries to the victim model: this is likewise our focus.
2.2 ALGORITHM
Algorithm 1 GFCS: Gradient First, Coimage Second
1: Input: targeted image X loss function L, a victim classifier v, a set of surrogate models S, a
step length e, and norm bound
2: Output: adversarial image Xadv within distance v of X
Xadv < Xin
4: Srem S
5: while Xalv is not adversary do
6: if Srem # / then
7:
Randomly sample surrogate model s from Srem
8:
Stem f- Srem (x..) 9- (Nat))l
9:
10:
else
None of the surrogate loss gradients work, so revert to ODS.
11:
Randomly sample surrogate model s from S Sample w ~~~li U-11,1
12:
q dons (Xutv: doDs(Xutv:+ w)
>> See Eqn. for definition.
14:
for E fe,----- -e] - do
15:
if I (Txx,,,)) xin (Xadv + 9)) T. (Xadv) then Xadv + 1xx, (Xady + a q)
16:
Siem S Reset candidate surrogate set to input set; resume using loss gradients. break
18:
The entirety of the proposed method is given in pseudocode as Algorithm I As indicated in Sec. 2.1 the method takes a victim classifier v, an input image Xin, and norm bound v. The projection operator Ixx,.v confines its input to the y-ball centred on X its inclusion in the algorithm represents standard projected gradient ascent (PGA) implementation. Additionally, the method requires a loss function L. set S of one or more surrogate models, and a step length representing the fixed length of the perturbations to be attempted each iterate" along its candidate direction. The loss I. can be any function of the iterate that serves as a suitable proxy for the adversarial objective, as in Sec. 2.1
In optimisation, this refers any given intermediate value of the variable heing optimised.
3

---

Published as a conference paper at ICLR 2022
the only requirement here is that it be once differentiable. In our implementation, make the popular and effective choice of the margin loss [x) = f.. (x) - fc, (x) where C2 = argmax, Vx(x) and c argmax V=(x), i.. the difference between the highest and second-highes (or, in the targeted case, the target) class scores. Note that the class IDs et and c, are defined by the ranking according to v, but are evaluated on the net f parametrising the loss, which is either on the line of the algorithm and [5] 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 ince-differentiable functions mapping X' + y The definition of ODS direction dops for network f and input x is, as in Tashiro et al. (2020).
depending
Vx (x(WT((x) V (w [V
(x(vxf(x))
dons (x, f. w)
(1)
where w is sampled from the uniform distribution over [-1, By defimition, 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 basis of the coimage of the linear approximation of f: the subspace which f exhibits any nonzero response to.
As indicated in Sec. [ the logic of the method simple. At any given iterate, the method tries to proceed in 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. 3.22 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 from that surrogate, attempting a SimBA update each time, until an improvement in the loss is realised. Once such a successful update occurs, the method resets the candidate surrogate set to the input set 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.
3 EXPERIMENTS
3.1 UNTARGETED ATTACKS
Experimental setup: We compare GFCS to the methods 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 the respective source works. We use each method to perform fz-norm-constran untargeted attacks against the same 2000 randomly chosen correctly classified ILSVRC2012 vali- dation images per victim network. A maximum query count of 10000 is set per example (beyond which failure is declared), and the Eg bound (enforced using PGA) is set to the commonly chosen v0.001D, where D is the image dimension in the victim network's 's native input resolution. The victim networks are the commonly chosen VGG-16, Re, and Inception-v3. The experiments repeated for each of two choices of surrogate set: ResNet- 152 alone (as in Cheng et al. (2019); Yang et al. (2000)) and the set (VGG-19, ResNet-34, GenseNett1211, MobileNet-v2), as in Tashiro ct al. (222)). 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 TyTocc//oorchvision. 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. 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.
Table rreports attack success rates and median query counts, and Fig. 2 plots cumulative success counts against the maximum queries spent per example (CDFs, modulo normalisation). Unlike prior work, we do not report means, as these are inappropriate for summarising the long-tailes distributions resulting from these methods. Uncertainty is represented as standard error in Table I and by 95% confidence intervals in Fig. 2 in both cases having been obtained via bootstrap sampling. Two things are readily apparent in Table First, all of the studied methods have very high success rates on
Results:
4

---

Published as a conference paper at ICLR 2022
100
120
120
130
1300
130
SadiAs
Spurshitih
ODS-RGF
Spenntiikk (rows))
Lett
Squereittcc bnsiont
Let4
800
Quaiiis
Quicke
(a) VGG- 16; surrogate.
(b) ResNet-50; one surrogate.
(c) Inception-v3; one surrogate.
X00
3700
1504
babe
150
12.00
GPCS jouns
(itSipent)
tepsUUt 24
Stebecllts y
te 59
PaKCE
2-8 63,200
PMRCE AA.FD
1230
OC5-322
630
005-37
30
30
150
1000
1200
30
100
1000
100
1000
1200
Querioper
Ohirke rage
Queiie
(d) VGG-16; four surrogates.
(c) ResNet-50; four surrogates.
(f) Inception-v3; four surrogates.
Figure 2: CDFs representing the number of successfully attacked examples at different query counts when performing untargeted black-box attacks on VGG-16, ResNet-50, and Inception-v3 networks.
Table 1: Median query count for state-of-the-art untargeted black-box methods that make use of surrogates. The missing entry at indicates the LeBA code crashing before completing the full set of images for ResNet-50.
Median queries [Success rale]
Surrogates
Method
ResNet-50
Inception-x
SimBA-ODS
117 +: 5.1
99.45%
91.5 + 3.2
99.65%
275 + 14
[95. 10%
SimBA-ODS
15
99.65%
+ 0.4
99.9
36 1.9
[98.50%
P-RGF
128 4: 1.1
99. 99.95%
62 + 1.2
[100%]
282
+: 12
[99.25%)
1
0.5. 10
2.0
99.90%
0.0
[99.95%]
4.9
[99.00%]
ODS-RGF
44 0.0
99.95%
33 + 0.0
(100%)
77 + 2.4
(99.95%)
SimBA+
30
[100%]
5+05
[100%]
59 3.4
[99.19%
LeBA
0.74
[100%]
27 3.1
[99. 45%
GFCS (ours)
6 0.3
[99. (9.90%
4 4 0.4
0.4
(99.80%
18 + 1.1
(98.60%)
GF, no CS (ablation)
[5%
[75.90%
(fallure)
[38 25%
SimBA-ODS
68 2.2
[99.900 90%)
108.5 + 4.5
80%
227 + 9.9
[96 63%)
SimBA-ODS
[100%]
0.5
999.90 99%%
29 1.4
[100%]
4
P-RGF
64 1 0.6
99.99%%
66 - 0.5
[100%]
232 + 4.7
(99. 15%)
P.RGF 0- 100
2.3
100%
100%
60 2.1
[99 [99.60%)
ODS-RGF
33 0.0
100%
44 + 0.0
[100%
77 7 5.5
[100%)
GFCS (ours)
= 0.2
1100%
4
[99.95%]
0.5
[99 40%6
GF; CS (ablation)
[98.65%]
[96.50%]
[80.20%]
this problem, against all of the victim networks: the lowest rate observed is 95. 90% for SimBA-ODS on Inception-v3 with ResNet-152 as the lone surrogate. Second, GFCS incurs an extremely low median query count while achieving 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 the multi-surrogate Figs. 2d 2e and
This is despite GFCS's ' simplicity: compare Alg. - against, for example, LeBA's training of its surrogate 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 used on its own, and we effectively inherit them. At the cost of bit of added complexity in the implementation, e.g. ODS-RGF could be substituted, and would likely lead to further improvements in the failure rates, while still representing a form of GFCS. There is an additional phenomenon of note: Table [] also demonstrates the dependence of the performance of existing methods on their own choices of parameter values. Strikingly, most 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-RGE. it actually considerably outperforms it in terms of median query count on ResNet-50, at the cost of 0.05% increase in the single-surrogate failure rate.
2f
5

---

Published as a conference paper at ICLR 2022
Toumplo
50
250
10
Int.
Conage qweyy onen onn
10
101-
10
10'
10"
12
10
500
10
16
(Sumogate query
Foxmpls
(urroggte quary
(a) Inception-v3; one surrogate.
(b) Inception-v33 four surrogates.
Figure 3: Breakdown of the total query count for the proposed method, GFCS: Gradient First, Coimage Second. The x-axis represents the number of queries for successful attack required by the gradient part of the method, and the y-axis the number required by the coimage part. Histograms on the top and right sides of the scatter plots represent marginal empirical distributions.
SimBA-ODS benefits dramatically from order-of-magnituee 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 aggressive: see the ablation lines in the table representing the exclusive use of loss gradients, i.c. "GF without the CS"
3.2 ANALYSIS OF ALGORITHM BEHAVIOUR
To delve deeper into the results of Sec. 3.1 we plot each attacked example as 2D point whose u-coordinate is the number of queries expended by the surrogate loss gradient block of the algorithm, and whose y-coordinate is the analogous count for the coimage block. This gives the seatter plot of Fig. which is supplemented by marginal histograms corresponding 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 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 large fraction of examples (represented by the dense horizontal rows of dots 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 the surrogate gradient transfer, with ODS used seldom not at all. As these cow-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 Res on its own, as can be seen by comparing the left and right sides of the figure. clear that the examples that rely on the interplay between the gradient- and coimage-based direction generators are reduced to nontrivial (i.c. sufficient to affect the failure rate if not handled) but nonetheless relatively small group. Overall, there is an order-of -oii-nuud 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, typically requires far more queries to progress the optimiser than in the much more common cases in which the gradient suffices.
3.3 ON THE IMPORTANCE OF INPUT-SPECIRIC PRIORS
We have demonstrated that surrogate CNNs are sufficient to craft extremely effective scsre-based black-box attacks on other CNNs trained on the same problem. We now make empirical argument that such surrogates are likely necessary in achieving this level of performance. That is, the location- specific information encoded by a surrogate network, in which the gradient prior is a function of the input image-space point, increases attack effectiveness beyond that available to methods that use location-independen priors and infer location-specific properties online. We do not consider this to be a trivial point. The phenomenon of universal adversarial perturbations (Moosavi- Moosavi-Dezzoooli et al. 2017) demonstrates level of location agnosticism in adversarial vulnerability, and the original SimBA method (Guo et al. 2019a) on which GFCS is based is itself a demonstration of the remarkable effectiveness of online determination of the signs of predetermined basis vectors. The latter paper

---

Published as a conference paper at ICLR 2022
200-
700-
1030
3000
100
500
6.0
302
Sax ICTT
330
Siabbs GeAi Nembhh (CBbA-PAA-- CCAgrretetttt faind
Susll-PCh- joar)
Quadios
Quariin
(a) VGG-16.
(b) ResNett-5.
(c) Inception-v3.
Figure 4: Comparison between GFCS, which evaluates surrogate gradients locally, vs. flavours of SimBA which build location-agnostie gradient priors. Please refer to Sec. 3.3
itself proposed, as future work, "to further investigate the selection of different sets of orthonormal bases, which could be crucial to the efficiency of [the] method by increasing the probability of finding a direction of large change." A priori, it unclear what the added benefit a surrogate network will be, vs. well-chosen adversarial subspace with a prior ordering on its basis vectors.
To study this within our SimBA-based optimisation context, 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-Dezzooli et al. 20177): Jetley et al. (2018), we gather adversarial example over sample input set as columns in matrix, then compute that matrix's is SVD, That is, we produce the ordered set of vectors that would be expected to represent the on-omtimal 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, also include the result of using the procedure on raw images directly, i.c, using the principal components of the input data as the search directions. All of these methods are placed within the same norm-bounde PGA framework.
Fig. 4 demonstrates the results of this experiment. As predicted, the gradient-based basis ("SimBA- "CA-gradients") comfortably outperforms the canonical pixel basis ("SimBA pixel"), as well as the principal image components
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 generally outperform the DCT basis: their results are very close, with the DCT basis sometimes slightly outperforming That is, the DCT basis with 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 condition the prior on the iterate, i.e. gradient information. This is one way of viewing why it is that the use of surrogates is as powerful as it is. This is despite the fact that these surrogates, rather than having been originally designed to simulate their victims, were actually supposed to have represented architectural alternatives to them.
local
3.4 TARGETED ATTACKS
We also test our method in the targeted attack scenario. The setup is the same as in Sec. except as noted otherwise. For these experiments, instead of the margin loss, we use the log loss of the target- class softmax score, as is often chosen for targeted attacks: (x) = log Pt. where
ff(())
Σ. cxT
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. SeitherCChena et al. (2019) nor Yang et al. (2020) provide results or code for targeted attacks. While Tashiro et al. 20200) report targeted attack numbers for both P-RGF and
We 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, basic targeted FGM.
7

---

Published as a conference paper at ICLR 2022
1X0
3M0
Nostvetodel
100-
Nonter
Nierker Borket
(/0))) dU =02
Cat' Inon)
Sell 200 Spurehookk
SavRBS-CTRR 70
Strleo0s 22
Squaediack
Sguinrat
1200
50
1000
Quriesper image
Quedie perizage
Quitkope tmage
(a) VGG-16
(b) ResNet-50
(c) Inception-v3
Figure 5: CDFs showing the number of successfully attacked examples at different query counts when performing targeted black-box attacks on 1000 ImageNet images, with four surrogates.
their own ODS-RGE RGGF, no supporting implementation is available. As noted before, our own P-RGF and ODS-RGF results in Sec. Se4.3.44 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 the backup method. The results are displayed in Fig. 5 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, method retains its considerable advantage.
While the targeted attack method of Huang & Zhang (2020) is both powerful and conceptually related, it is architecturally tied the lor norm in its given formulation, and thus not appropriate for our fz-bound comparisons. Further, given a trained surrogate, the method requires that one then train the method's adversarial encoder-decoder network on 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.
4 RELATED WORK
Cheng et al. 2019) 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 non-trivial to estimate the gradient in a high--diensiionl space with limited information". Guo et al. (2019b) did this by supplying a bandits optimiser (as used in Ilyas et al.] (2019a)) 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 dynamically estimated bias parameter, albeit one whose optimal value itself depends on the unknown target gradient. The Output-Diversinn
Sampling (ODS) approach of Tashiro et al. (2020) sampled gradients of randomly weighted logit sums over multiple surrogate models in order 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 surrogate-enhancee
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 making periodic attempts to directly transfer surrogate gradients estimated using smoothing and momentum. When combined with "High Order Gradient Approximation", 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 basee 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 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 gradient estimation must have approach to effectively reduce the intrinsic dimension of the estimate space. Guo et al. (2019: 2020) use low-frequence 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. (2000) is conceptually related. Also closely related to the fow-frequency prior is the of spatial downsampling, whether applied
8

---

Published as a conference paper at ICLR 2022
to the image or its gradient, and whether implemented through pooling, interpolation, striding:
Tu et al. (2019): Lyas et al. (2019a); Li et al. (2019); Wang et al. (202l) all involve a version of it. Coarse-to-fine approaches. in which results at coarser scale either solve the problem or initialise the optimiser of a finer one, appear in Moon et al. (2019): Al-Dujaili & O' O'Reilly (2020).
Data distribution modelling: Li et al. (0199) 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 normalising flow model trained on clean data. [Tu al. (2019) represents the data using an autoencoder and conducts the attack in its latent space. Huuang & Zhang (2020) likewise conducts a latent-space attack. but in that of an encoder-decoder network trained to output adversaries on source network. Ru et al. (2019) attempts to learn the latent- dimension itself.
Attention:
Wang et al. (202I) uses the output of CAM (Zhou et 2016) on a proxy net as a map of pixels to attack. In Brunner et al. (2019), 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. (201bb); Cheng et al. (2019);
Tashiro et al. |020]; Yang al. (020) is discussed above, and the transfer-based approaches Papernot et (2017); Liu et al. (2017) are of course fundamentally based on this. Besides these, the method Brunner et al. (2019 uses the gradient of 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. (202T), also a Boundary Attack variant, attempts to learn to mimic the gradients of a victim net using customised pre-trained policy network. |Huang & Zhang (2020) learns a latent space of transferable adversarial features from its surrogate. (Andrisshchenko al. (2020) supplies 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 foo case, pairs of opposite-signe
"decaying peaks" in the f2). Sahu et al. (2020) attempts to perform a "black box FGSM" by learning correlations between components of the loss function gradient within Gaussian Markov random field framework. The "gradient priors" of lflls et al. (2019a) essentially amount to momentum and downsampling, and do not represent the sort of "flexible gradient transfer" we are otherwise discussing here.
Again, a standard optimisation framework for black-box score- score-based attacks 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 al. 2019a Guo et al.)
Optimisation algorithms:
2019b). Natural Evolution Strategies (NES) (Li et al. 2019 Huang & Zhang 2020 Dolatabadi et al. (2200) evolutionary algorithms (Liu al. 2020 Wang al.] 2021). Bayesian optimisation
(Ru et 2019, Shukla et al., 2019). and training of a policy network by REINFORCE (Yan et al.)
2021). Al-Dujaili & O' O'Reilly (2020) uses 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 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.
5 CONCLUSION
We have demonstrated that score- base- 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, GFCS, that is simple to both describe and implement. Further, this algorithm based on a fairly direct type of transfer: 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 only 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.

---

Published as a conference paper at ICLR 2022
ETHICS STATEMENT
Our work introduces a novel (and very effective) black-box attack. As with all adversarial attacks, the method exposes way of getting a target/victim network to issue responses to inputs that are almost certainly unlike those intended by its designer. Therefore, were actual harmful practical application of such an attack to be identified in which the assumptions of this method (i.c. that the victim exposes be found) were satisfied, the publication of this
its decision scores, and that a viable surrogate 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 straightforward "defence". However, the primary perspective from which we approach this work is that of network analysis. A key goal is 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.
REPRODUCIBILIT STATEMENT
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 T itself presents complete and implementable description of the algorithm. We are also publicly releasing all code needed to reproduce all of the results in our paper. This will include details of any changes made to the released code of competing methods to standardise the comparison, including the issues noted in Appendix A.2
Statistical significance: As described in Sec. 3.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 e). As discussed in Appendix AA.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 have used the provided source code (or provided our own implementation when none existed, as and when noted) 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 e = 0.2, which the default used in Tashiro et al. (2020).
REFERENCES
Abdullah Al-Dujaili and Una-May O' O'Reilly, Sign bits are all you need for black-box attacks. In 8th International Conference Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL httpttts///pppeeeeeeww net/ forum? SygWOTEFw wH
Maksym Andriushchenko, Francesco Croce, Nicolas Flammarion, and Matthias Hein. Square attack: query-efficient black-box adversarial attack via random search. In European Conference Computer Vision, pp. 484-501. Springer, 2020.
Arjun Nitin Bhagoji, Warren He, Bo Li, and Dawn Song. Practical black-box attacks on deep neural networks using efficient query mechanisms. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 154-169, 2018.
Wieland Brendel, Jonas Rauber, and Matthias Bethge. Decision-based adversarial attacks: Reliable attacks against black-box machine learning models. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018. URL httpps://pperevieeee net wwwp:nrrttrrrrrr// SGWIOG
Tom B Brown, Nicholas Carlini, Chiyuan Zhang, Catherine Olsson, Paul Christiano, and Ian Good- fellow. Unrestricted adversarial examples. arXiv preprint arXiv: 01880000835 2018.
10

---

Published as a conference paper at ICLR 2022
Thomas Brunner, Frederik Diehl, Michael Truong Le, and Alois Knoll. Guessing smart: Biased sampling for efficient black-box adversarial attacks. In Proceedings of the IEEE/CVF International Conference Computer Vision, pp.
2019.
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In 2017 ieee symposium on security and privacy (sp). pp. 39-57. IEEE, 2017.
Pin-Yu Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsich. Zoo: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models. In Proceedings of the 10th ACM workshop on artificial intelligence and security, pp. 15-26, 2017.
Shuyu Cheng, Yinpeng Dong, Tianyu Pang. Hang Su, and Jun Zhu. Improving black-box box adversarial attacks with transfer-based prior. Advances in Neural Information Processing Systems, 32: 10934-10944, 2019.
Hadi Mohaghegh Dolatabadi, Sarah Erfani, and Christopher Leckie. Advflow: Inconspicuous black- box adversarial attacks using normalizing flows. Advances in Neural Information Processing Systems, 33: 18871-1888,, 2020.
lan J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In Yoshua Bengio and Yann LeCun (eds.), 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. URL hRtt::///aaaxix org/ abs abs 1412.4112..60 6572
Chuan Guo, Jacob Gardner, Yurong You, Andrew Gordon Wilson, and Kilian Weinberger. Simple black-box adversarial attacks. In International Conference on Machine Learning, pp. 2484-2493.
PMLR, 2019a.
Chuan Guo, Jared S Frank, and Kilian Q Weinberger. Low frequency adversarial perturbation. In Uncertainty in Artificial Intelligence, pp. 1127-1137. PMLR, 2020.
Yiwen Guo. Ziang Yan, and Changshui Zhang. Subspace attack: query-efficient black- attacks. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Bue, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Cur- ran Associates, Inc., 2019b. URL http:::::///o.. http::::s////pcpeeeeeppp 447bbeeff4bbbeee 44 7bbe 2bbabe
Exploiting promising subspaces for
neur pis..pp.... cc/paper/2019/ pdff
Dan Hendrycks, Kevin Zhao, Steven Basart, Jacob Steinhardr, and Dawn Song. Natural adver- sarial examples. Proceedings of the IEEE/CVE Conference on Computer Vision and Pattern Recognition, pp. 15262-15277 15271, 2021.
Hossein Hosseini and Radha Poovendran. Semantic adversarial examples. In Proceedings of the IEEE Conference on Computer Vision and Puttern Recognition Workshops, pp. 1614-1619, 2018
Zhichao Huang and Tong Zhang. Black-box adversarial attack with transferable model-based embedding. In 8th International Conference Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL htttps://ppereviii
Andrew Ilyas, Logan Engstrom, Anish Athalye, and Jessy Lin. Black-box adversarial attacks with limited queries and information. In International Conference on Machine Learning, pp. 2137-2146. PMLR, 2018.
Andrew Hyas, Logan Engstrom, and Aleksander Madry. Prior convictions: Black-box adversarial attacks with bandits and priors. In International Conference on Learning Representations, number 2019, 2019a.
Andrew Ilyas, Shibani Santurkar, Logan Engstrom, Brandon Tran, and Aleksander Madry. Adversarial examples are not bugs, they are features. Advances in neural information processing systems, 32, 2019b.
Saumya Jetley, Nicholas A Lord, and Philip HS Tom. With friends like these, who needs adversaries? In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pp. 10772-10782, 2018
11

---

Published as a conference paper at ICLR 2022
Alexey Kurakin, Ian J. Goodfellow, and Samy Bengio. Adversarial machine learning scale. In 5th International Conference on Learning Representations. ICLR 2017, Toulon, France, April 24-26. 2017, Conference Track Proceedings. OpenReview.net, 2017. URL /tpL:tte//////eeeeeeeee net/forum? watrrrmmmii=33000 d=3 444xx
Yandong Li, Lijun Li, Liqiang Wang, Tong Zhang, and Boqing Gong. Nattack: Learning the distributions of adversarial examples for improved black-box attack on deep neural networks. In International Conference on Machine Learning, pp. 3866-3876. PMLR, 2019.
Xiaolei Liu, Teng Hu, Kangyi Ding, Yang Bai, Weina Niu, and Jiazhong Lu. A black-box attack on neural networks based on swarm evolutionary algorithm. Australasian Conference on Information Security and Privacy, pp. 268. Springer, 2020.
Yanpei Liu, Xinyun Chen, Chang Liu, and Dawn Song. Delving into transferable adversarial examples and black-box attacks. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017. URL ptttps://openreview net fow.omidddssseeeee
Chen Ma, Shuyu Cheng, Li Chen, and Junhai Yong. Switching gradient directions for query-efficient black-box adversarial attacks. arXiv preprint arXiv:2009.07191, 2020.
Seungyong Moon, Gaon An, and Hyun Oh Song. Parsimonious black-box adversarial attacks via efficient combinatorial optimization. In International Conference on Machine Learning, pp. 4636-4645 PMLR, 2019.
Seyed-Mohsen Moosavi-Dezfooli, Alhussein Fawzi, and Pascal Frossard. Deepfool: simple and accurate method to fool deep neural networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2574-2582, 2016.
Seyed-Mohsee Moosavi-Dezfoole Alhussein Fawzi, Omar Fawzi, and Pascal Frossard. Universal adversarial perturbations. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 1765-1773, 2017.
Chris Olah, Alexander Mordvintsev, and Ludwig Schubert. Feature visualization. Distill, 2017. doi: http:aiillllpput20//////auueeeee
Nicolas Papernot, Patrick McDaniel, Ian Goodfellow, Somesh Jha, Z Berkay Celik, and Ananthram Swami. Practical black-box attacks against machine learning. In Proceedings of the 2017 ACM on Asia conference computer and communications security, pp. 506-519, 2017.
Binxin Ru, Adam Cobb, Arno Blaas, and Yarin Gal. Bayesopt adversarial attack. In International Conference on Learning Representations, 2019.
Anit Kumar Sahu, Satya Narayan Shukla, and J Zico Kolter. Gaussian mrf covariance modeling for efficient black-box adversarial attacks. arXiv preprint arXiv:2010.04205. 2020.
Yucheng Shi, Siyu Wang, and Yahong Han. Curls & whey: Boosting black-box adversarial attacks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 2019.
Satya Narayan Shukla, Anit Kumar Sahu, Devin Willmott, and Zico Kolter. Black-box adversarial attacks with bayesian optimization. arXiv preprint arXiv: 13857, 2019.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In 2nd International Conference on Learning Representaations, ICLR 2014, 2014.
Yusuke Tashiro, Yang Song, and Stefano Ermon. Diversity can be transferred: Output diversification for wnite-and black-box attacks. Advances in Neural Information Processing Systems, 33, 2020.
Chun-Chen Tu, Paishun Ting, Pin-Yu Chen, Sijia Liu, Huan Zhang, Jinfeng Yi, Cho-Jui Hsieh, and Shin-Ming Cheng. Autozoom: Autoencoder- based zeroth order optimization method for attacking black-box neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 742-749, 2019.
12

---

Published as a conference paper at ICLR 2022
Jie Wang, Zhaoxia Yin, Jin Tang, Jing Jiang, and Bin Luo. Pica: A pixel correlation-basel attentional black-box adversarial attack. arXiv preprint arXiv:2101.07538, 2021.
Chaowei Xiao, Jun- Yan Zhu, Bo Li, Warren He, Mingyan Liu, and Dawn Song. Spatially transformed adversarial examples. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018. URL http:: htttps://openrevee/
net/ fow.mfrrmmiooo HyydRRMzZ-
Ziang Yan, Yiwen Guo, Jian Liang, and Changshui Zhang. Policy-driven attack: Learning to query for hard-label black-box adversarial examples. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net 2021. URL https://openrevia
net forum (acpuummii-ppe id==ppyt jk3Xb2
Jiancheng Yang, Yangzhou Jiang, Xiaoyang Huang, Bingbing Ni, and Chenglong Zhao. Learning black-box attackers with transferable priors and query feedback. Advances in Neural Information Processing Systems, 33, 2020.
Zhengli Zhao, Dheeru Dua, and Sameer Singh. Generating natural adversarial examples. In 6th International Conference on Learning Representations, ICLR 2018 Vancouver, BC, Canada, April 30- May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018. URL https 7/ /ooperrvveew.oo www.ee/oooormmdiHH.......
Bolei Zhou, Aditya Khosla, Agata Lapedriza, Aude Oliva, and Antonio Torralba. Learning deep features for discriminative localization. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 2921-2929, 2016.
A
APPENDIX
A.1 COIMAGES AND DIMENSION REDUCTION
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 space W, rank(T)) + nullity(7) = dim(V), where rTn == dim (imagee(())) and nullity(?) == dim dim(kereel(T)) That 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((") < dim(WW)), 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 2 dim()) - (W)). To make this more concrete, in the case of a standard ImageNet Inception-v3 network, V = 2999-29943
and W = R 1000 and so in the linear approximation. rank(T) dim(coimage(TT) S 1000, and nullity(() (T) 2 267203. Under the assumption that the features to which a surrogate is locally sensitive will largely transfer to target network, naïve search of the input space is thus extremely wasteful.
This is the key issue which limits the preprint of et al. (2020). which contains some similarities to our method in its preference for surrogate gradient transfer within 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 nigh-diimessioal input spaces pointed out in this context as far back as Chen et al. (017). The dramatic difference in result quality between the two methods owes to this fact.
A.2 IMPLEMENTATION DETAILS
As explicitly written in Alg. I and discussed in Sec. 2.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 post facto for violating 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 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.
perform on other methods involve this sort of practice:
13

---

Published as a conference paper at ICLR 2022
ooungls
Voungles
900
107
105
Coltagge queryy coum)
10"
10
70"
10"
30"
10
101
100
100
101
30
103
2000
Burmaak load Geadient query count
examples
[Burngato quary
exxmmpá
(a) ResNet-50; surrogate.
(b) ResNet-50; four surrogates.
500
Foumplo
1000
10"
Commgg quacyy count
10*
107
Chimag vuaryy
10"
10P
10P
20
10
1000
(urnugate Geadient quary
esamppess
(Sumppgte lred Gradient query count
#exmmpls
(c) VGG-16; one surrogate.
(d) VGG-16; four surrogates.
Figure 6: Breakdown of the total query count for the proposed method, GFCS: Gradient First, Coimage Second. The x-axis represents the number of queries required for successful attack by the gradient part of the method, while the y-axis represents the number required by the coimage part. Histograms on the top and right sides of the scatter plots represent marginal empirical distributions. These plots correspond to the results depicted in Fig. 2
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 R 2999+29-+3 is attacked using networks with the more common input domain of 22244224+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 this writing, the public LeBA implementation contains non-standard pre-pres prepproesssing of the input images: we replace this with standard practice, again to facilitate fair comparison against other methods.
Finally, note that when [x(x) is the margin loss, its normalised gradient is just special case of dons f, w) in which Wa, < 1, We, < -1, and w (c..o)) + 0. In our experimental setup, all methods 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 c, and the ground-truth label in the untargeted attack case.
A.3 ADDITIONAL RESULTS FOR SECTION
The scatter plots and empirical marginal distributions in Fig. complete the results of Sec. 3.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 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.
14

---

Published as a conference paper at ICLR 2022
A.4 ON THE STEP LENGTH
30
Sop kngh
Figure 7: The figure illustrates two sets of curves. The solid curves represent the median query count required to successfully attack the three architectures function of the step length, while the dashed curves show the success rate.
The simple method we propose in Algorithm 1 accepts a single hyperparameter: the step length e (line 14), which indicates the length of the perturbations 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 (disjoint from the 2000 examples used in the experiments of the main paper). Results for the three architectures used as victim (and GesNet-152 as the single surrogate) are shown in Fig. Note that the figure has two y-axes and two sets of curves: solid and dashed curves should be considered looking at each 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 fixed value that is reasonable for all models, balancing the query count and success rate. Note also the fact that it is possible to achieve an even lower query count if one is willing sacrifice about 1% of the success rate.
We observed that this choice of é is also significantly better than the default one made by SimBA- ODS (Tsshiro et al. 2020 (i.e. 0.2), and have reported results for both in our experiments.
A.5 EXPERIMENTS WITH Eg NORM BOUND v = 5.0
We repeat the experiments of Sec. 3.1 (whose results are displayed in Fig. 2 but instead using the norm bound of y = 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 V0.001 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 slightly lower success rate than some competitors, including ODS-RGE As already pointed out in Sec. 3.1 GFCS uses SimBA-ODS as its coimage sampler for the sake of simplicity, and inherits small number of failure cases from it in some cireumstances. This can easily be alleviated in exchange for a bit of additional complexity in the algorithm's 's implementation by using ODS-RGF to do coimage sampling.
A.6 EXPERIMENTS ON CIFAR-10
We again repeat the main untargeted attack experiment, this time using CIFAR-10 as the dataset, with the target and surrogate networks sourced from https: /ttp:::///hhhbb com/ akamaster pytorch pyytorch_renet.... caatnnt__iffarll We use ResNet-110 10 as the target, and the much simpler ResNet-20 as its single surrogate. The l norm bound is again set to v = vo.001D, which for CIFAR-10 10 a 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.
15

---

Published as a conference paper at ICLR 2022
2000
2200
1700
1500
1700
1200
1500
1000
GPCS tours)
Number
tours)
PARGE, 0.8 55,500
1200
SimbooCTS ar
SimflA+
OIE-RGF
LeBA
1000 Queries image
10000
1000
Queries image
(a) VGG- 16; one surrogate; v=5.0.
(h) ResNet-50; one surrogate; v=5.0.
2000
2000
1700
1700
1500
Numbee
GPCS (ours)
CFCS (ours)
1000
SimbaOLUS
RCE, c 0., SPD
RGE, c 0.5 SPD
1200
CIU KLP
CUU--GU
500
Queriae per image
Queritn per image
VGG-16; four surrogates; 5=5.0.
(d) ResNet-50; four surrogates; v=55.0.
Figure 8: CDFs representing the number of successfully attacked examples at different query counts when performing untargeted black-box attacks on VGG-16 and ResNet-50, with one or four surrogates, under & norm bound 5.0.
A.7 ATTACKING A HARDENED NETWORK
As final additional experiment, we repeat the four-surrogate untargeted attack of Sec. 3.1 using the adversarially trained Inception-v3 Kurakin et al. (2017) (as provided by httht:s:/// g thub as the victim. The test set in this case consists
com/ twiiggt wwiigttma/// pyytorch-mmage-aae
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, 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.
2000
Number fodded
1850
1900
GFCS (cuns) 03
1830
SimbuODS.
P-RGE 033.5D 10
1900
20
100
200
Quatiiss per
Figure 9: CDFs representing the number of successfully attacked examples (from CIFAR-10) at different query counts when performing untargeted black- -bxx attacks on a ResNet- network using ResNet-20 surrogate.
16

---

Published as a conference paper at ICLR 2022
400
Number
SumbuODS, a
100
P-RCE, 05,5PD
OCS DCF
10000
Querica per image
Figure 10: CDFs representing the number successfully attacked examples at different query counts when performing untargeted attacks an adversarially trained Inception-v3, using four surrogates. The target set in this case consists of 800 ImageNet images correctly classified by the adversarially trained victim network.
A.8 BREAKDOWN ANALYSIS FOR TARGETED ATTACKS
Fig. I1 depicts the query breakdown for the targeted attack experiment of See. 3.4 Fig. has already demonstrated that GFCS outperforms its competitors dramatically 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: 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 remarkable about this plot relative to those of the untargeted attacks is that the large number of loss-gred poss-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 considerable outperformance of GFCS over SimBA-ODS seen in Fig. 5 while the use of SimBA-ODS as a backup critical in preventing the overall method from failing the majority of the time.
Peaplee
100
USi2g qua c202
10-
32
10a
12
1P
L0P
102
Storogate query
essmples
Piomogste query
(a) VGG-16; 16; four surrogates.
(b) ResNet-50; four surrogates.
Figure 11: Breakdown of the total query count for GFCS, in Figs. 3 and 6 for the targeted attack experiments whose results are depicted in Fig. See the caption of Fig a reminder of what the figure depicts is required.
17


Reviews:
[{"review_id": "fQbxHVKGwv1", "reviewer": "Reviewer_SLVp", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Positives:\n1. The proposed approach is simple, effective, and query-efficient.\n2. The literature review seems quite thorough and does an especially nice job of covering the related work in this domain. It would be good to discuss some recent Bayesian optimization approaches [1, 2] to make it a complete review.  \n3. Experiments are well designed to show the effectiveness of the proposed framework on both untargeted and targeted attacks.\n4. The paper is well written and easy to follow.\n\nConcerns:\n1. Although the experiments are well-designed, the authors use just one dataset to show the effectiveness of the approach. It would be interesting to see if the proposed approach achieves similar performance on other datasets e.g. CIFAR10.\n2. It is hard to compare the performance of different approaches from Table 1 as they all are performing really well. For example, Simba-ODS performance is very close to that of GFCS. How is the value of epsilon been chosen as it significantly affects the performance of Simba-ODS? Is it possible to further tune this parameter to further improve the performance? It would be also interesting to see if the performance difference increase if you decrease the L2 norm bound to 5 which has been used in several prior work. \n3. The authors are missing a comparison to the SOTA method for score-based attacks [3]. it would be also good to compare with Bayes-attack approaches [1, 2] as they show similar properties as the proposed approach, i.e., successfully attack a large fraction of examples \nwithin a very low number of queries.\n4. The authors are also missing a comparison to SOTA optimization-based methods for targeted attacks.\n5. I have some concerns with the setting of the experiments. The surrogate models are trained on the same dataset and use the same loss function which is already a lot of information for the adversary to attack the target model. This setting should not be classified as the typical black-box setting.\n6. Since the transfer attack using the surrogate models are easy for the setting considered here, it would be an interesting ablation to apply FGSM or PGD attack using the gradient of the surrogate model(s) and compare the attack success rates.\n7. Based on the experiment in Section 4.2, the ODS is seldom used for untargeted attacks. The authors should provide ablation experiments such as GFCS - ODS to show the effect of ODS on the attack success rates.\n\nReferences:\n1. Ru, B., Cobb, Blaas, & Gal. (2019). BayesOpt Adversarial Attack. ICLR 2020.\n2. Shukla, S. N., Sahu, A. K., Willmott, D., & Kolter, J. Z. (2019). Black-box adversarial attacks with bayesian optimization. arXiv preprint arXiv:1909.13857.\n3. Maksym Andriushchenko, Francesco Croce, Nicolas Flam- marion, and Matthias Hein. Square attack: a query-efficient black-box adversarial attack via random search. In ECCV, 2020.", "summary_of_the_paper": "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.  ", "summary_of_the_review": "Although there are several good things about the paper because of its simplicity and effectiveness, the authors should provide more experimental evidence to show the effectiveness of the proposed approach. There are also some concerns based on the setting of the experiment (pseudo-black-box setting). ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "RhIZNOjGN2b", "reviewer": "Reviewer_KEn1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "[Pros]:\n* The paper is well-motivated and easy to follow.\n* The proposed algorithm is simple but achieves state-of-the-art performance.\n\n[Cons]:\n* The technical contribution is marginal.\n* The empirical comparison is insufficient. \n* The result and discussion in Sec. 4.4 is digressed from the main statement.\n\nThe paper proposes a simple score-based black-box attack algorithm which achieves state-of-the art results. The simplicity and  effectiveness of the proposed algorithm is great for the research community. However, it seems that the novelty is technically marginal. Moreover, the empirical comparisons are not sufficient to show the advantage of the proposed method. \n\n* The proposed algorithm is a natural combination of two existing approaches. A previous study [1] utilized the surrogate’s loss gradient for improving SimBA. On the other hand, SimBA-ODS utilized the coimage of the surrogate’s local linearization for improving SimBA. The proposed algorithm is a simple switch algorithm of the above methods based on the update success, and thus the technical contribution is marginal. \n\n* The empirical comparison is insufficient, because the proposed algorithm was not compared with a variant, which only uses the surrogate’s loss gradient without the coimage of the surrogate’s local linearization (i.e., similar to [1]). Since the proposed algorithm is the combination of two existing approaches (i.e., gradient-based and coimage-based), the algorithm should be compared with both approaches. The right panel in Figure 3 implies that the variant will achieve very similar query efficiency with similar success rate, so the lack of the comparison is problematic. In addition, Figure 3 also suggests that the experiment setting in Sec. 4.1 and 4.2 is suitable for methods utilizing the surrogate’s loss gradient. To show the advantage of the combination of both existing approaches, the evaluation in more difficult settings (such as under small norm bound and on adversarially-trained robust models) is also important. Although the evaluation of targeted attacks in Sec. 4.3 is one of the difficult settings, the comparison and discussion only focus on query efficiency and do not explicitly shed light on the effect of the combination like Figure 3.\n\n* The result in Sec. 4.4 is interesting, but it is not directly related to GFCS. Previous studies have already shown the importance of local gradient information, and GFCS combines two approaches which utilize local gradient information in a different way. It seems that Sec. 4.4 just focuses on input-specific priors and using surrogates, which are related to all local gradient-based methods and not specific to GFCS. How does Sec. 4.4 connect with the main contribution of GFCS? \n\nMinor comments\n* the experiment setting for SimBA-PCA-gradients is not clear. What is a sample input set? Is it different from the test dataset? How many adversarial examples are generated per image? \n* SimBA-SVD is sometimes miswritten as SimBA-PCA.\n* In the page 9, what is PGA?\n\n[1] Jinghui Cai, Boyang Wang, Xiangfeng Wang, and Bo Jin. Accelerate Black-Box Attack with White-Box Prior Knowledge. IScIDE 2019.\n\n-----Post rebuttal comments-----\n\nAfter reading all rebuttals, I'm slightly inclined to accept, since most of my concerns are addressed.\n\nWhile I raise the score, I'm still concerned about the structure and writing in terms of Sec 4.4. I don't think the current paper properly conveys the author's claim. For example, the first sentence in Sec 4.4 does not distinguish GFCS from other methods, so It seems that GFCS can be replaced with other methods. The authors also do not define \"local information\". The connection between Sec 4.4 and other parts is weak in the current paper, so the authors should improve the structure and writing when the paper is accepted.", "summary_of_the_paper": "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.", "summary_of_the_review": "While the proposed black-box attacks show strong empirical performance, the technical contribution is marginal. Moreover, the empirical comparison is not enough to show the advantage of the proposed method.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "LGXxFni7GM-", "reviewer": "Reviewer_wR15", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The success of the proposed idea is surprising, while this effect is not explained by the experiments in the paper.\nIn particular, all attacks considered by the authors as competitors (SimBA++, SimbaODS, LeBA, P-RGF, ODS-RGF) directly assume, that surrogates are not precise enough to replace an initial model. \nSo, the evaluation is incomplete. if we don't consider benchmarks that use gradient steps that are taken directly from surrogate models. \nAs the authors demonstrate in Figure 3 we require only a small number of coimage steps, while most of the steps are taken directly from a surrogate model (or surrogate models).\n\nThe authors provide some explanation in Section 4.4 on why do we need local gradient information.\nCommon sense and previous work they cite (e.g. P-RGF) also make similar statements.\nIt would be interesting to consider the correlation between used surrogates and the victim model and quality of attack, as we can easly degrade the quality of a surrogate or maximize discrepancy between a surrogate model and a victim model by incorporating a specific term in the loss function.\n\nThe idea of ensembles for the performance improvement seems interesting (also we can try to apply something similar to bandits to select the best surrogate during the optimization?).", "summary_of_the_paper": "The paper proposes a simple, yet effective adversarial attack in a black box scenario with available surrogates. The attack combines a classic gradient attack via an ensemble of surrogates and an ODS attack. ", "summary_of_the_review": "The authors suggest an interesting effect but provide a little investigation of it.\nThe cause of this effect can be some specifics of used pairs surrogate-victim or more general effect related to the correlation of deep learning models trained on large datasets and on general transferability.\n\nAs I don't get from the paper, why this phenomenon occurs, I suggest starting a discussion to find out, if it is possible to improve the paper in this aspect. Now, this is the obstacle, that makes the paper below the acceptance threshold.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Bam6tV7D5Kg", "reviewer": "Reviewer_tmFJ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "First of all, I should admit that I am no expert in this area and hence my assessment may be affected by the lack of expertise.\n\nLanguage-wise the paper seems to be well written. The discussion flow is clear and easy to follow although there are a number of concepts that I am personally not familiar with, and so I believe it would help to define all the notation and the concepts studied (besides the basic definition of an adversarial attack) for a reader like me.\n\nThe algorithm proposed is well motivated and described. Related work seems to be properly analysed. Furthermore, although I am not familiar with the standard experimental setup in this area, I should say the results look good to me and the advantage of the proposed algorithm over the state of the art looks convincing.\n\nMy understanding is that despite the demonstrated practical efficiency of the proposed solution, it is not guaranteed to successfully find an adversarial example even if such an example exists, due to the limitations of the methods used. I wonder if the authors tried to compare their approach to the approaches based on formal methods for reasoning about the model behaviour. Also, it would help to mention this line of work in the related work.", "summary_of_the_paper": "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.", "summary_of_the_review": "Overall, I find the paper to offer a solid contribution that may be interesting enough for the community working in the area of black-box adversarial attacks, if accepted to ICLR.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper shows that the transfer attack is query efficient and the success rate can be kept high with the zeroth-order score-based attack as a backup.  Experiments show state-of-the-art results.

Pros: 
- Simple method based on a simple idea.
- State of the art performance.

Cons: 
- Proposal is a straightforward combination of two methods, and therefore technical contribution is marginal.
- The threat model is easy (surrogate can be trained on the same datasets and use the same loss function) and questionable.  Most of the experimental evidence shows that the research for this threat model is almost saturated (and the problem seems almost solved).

This paper got a borderline score with reviewer's concerns above.  I agree with the authors that the simplest method is best among those performing similarly, but the threat setting considered might be not very realistic as the authors admitted.  I see the proposed method a kind of egg of Columbus in a negative sense.  Namely, the authors found a shortcut to win a game that was created and adopted by the community.  Perhaps this paper would give an impact on the small community and would make the community change the game.  But to give an impact to a general audience, the authors should convince that there are some situations where the analyzed thread model is realistic and therefore the proposed method is really useful.  Or, the authors could adjust the thread model to be more realistic.  Serious discussion on the thread model would be a big plus to the marginal technical contributions.

After discussion with SAC, and PC, our conclusion is that this paper effectively tells the community that the benchmark they are using is too simple, which alone is worthwhile publishing because this may move the community forward (even if the community is small).
Decision: Accept (Poster)