Meta-Learning the Search Distribution of Black-Box Random Search Based Adversarial Attacks
Authors: Maksym Yatsura
Jan Hendrik Metzen
Matthias Hein
Venue: NeurIPS 2021 Poster (2021)
Keywords: black-box adversarial attacks
meta-learning

Abstract: Adversarial attacks based on randomized search schemes have obtained state-of-the-art results in black-box robustness evaluation recently. However, as we demonstrate in this work, their efficiency in different query budget regimes depends on manual design and heuristic tuning of the underlying proposal distributions. We study how this issue can be addressed by adapting the proposal distribution online based on the information obtained during the attack. We consider Square Attack, which is a state-of-the-art score-based black-box attack, and demonstrate how its performance can be improved by a learned controller that adjusts the parameters of the proposal distribution online during the attack. We train the controller using gradient-based end-to-end training on a CIFAR10 model with white box access. We demonstrate that plugging the learned controller into the attack consistently improves its black-box robustness estimate in different query regimes by up to 20% for a wide range of different models with black-box access. We further show that the learned adaptation principle transfers well to the other data distributions such as CIFAR100 or ImageNet and to the targeted attack setting. 

Meta-Learning the Search Distribution of Black-Box Random Search Based Adversarial Attacks
Maksym Yatsura
Jan Hendrik Metzen Bosch Center for Artificial Intelligence
Bosch Center for Artificial Intelligence
University of Tübingen maksym. yatsuradee bosch. com
j janhendrik: metzennde. bosch com
Matthias Hein
University of Tübingen
matthias woinnunnntttebiggennc.mm
Abstract
Adversarial attacks based on randomized search schemes have obtained state-of-the art results in black-box robustness evaluation recently. However, as we demonstrate in this work, their efficiency in different query budget regimes depends manual design and heuristic tuning of the underlying proposal distributions. We study how this issue can be addressed by adapting the proposal distribution online based on the information obtained during the attack. We consider Square Attack, which a state-of-the-art score-based black-box attack, and demonstrate how its performance can be improved by learned controller that adjusts the parameters of the proposal distribution online during the attack. We train the controller using gradient-basee based end-to-end training on a CIFARIO model with white box access. We demonstrate that plugging the learned controller into the attack consistently improves its black- box robustness estimate in different query regimes by up to 20% for a wide range of different models with black-bo access. We further show that the learned adaptation principle transfers well to the other data distributions such as CIFAR100 or ImageNet and the targeted attack setting")
Introduction
It was demonstrated that despite their impressive performance in various tasks, neural networks are susceptible small imperceptible perturbations the input called adversarial examples [4] This is concerning issue for real-world deployment of deep learning approaches, especially in safety-critica domains such as autonomous driving (5). But apart from practical concerns, adversarial examples serve tool to better understand the true nature of artificial neural networks and capture their
inherent properties and differences from their biological counterparts 6
Evaluating adversarial robustness is usually formulated as constrained optimization problem [ However, finding the exact solution is typically intractable С Therefore, practice one often resorts to approximate methods called adversarial altacks that to find adversarial examples within a small number of iterations. number different adversarial attacks were proposed [8-10 that can be distinguished into white- and black-box attacks. In white-box attacks, one assumes full access to the model architecture and weights [8. However, as white-box attacks typically rely on the gradient, gradient obfuscation, which does not eliminate the existence of adversarial examples but makes significantly harder to find them bradient-based, can be severe obstacle for certain attacks [[]]
'The code is available at attttp::/ggttubb.ooombbbeeeeeees
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

30
Original Square Attack (SA)
300
Square Attack in Auto Attack (AA)
Update Size
Meta Square Attack (mean)
20
Meta Square Attack (5% 95%)
200
Loss
10
100
Original Square Attack (SA)
Square Attack Auto Attack (AA)
Meta Square Attack (MSA)
0
200
300
400
500
100
200
300
500
Query
Query
(a) T = 500 queries
500
30
Original Square Attack (SA)
Square Attack Auto Attack (AA)
400
Update Size
Meta Square Attack (mean)
20
Meta Square Attack (5%-995%)
300
200
10
Original Square Attack (SA)
Square Attack in Auto Attack (AA)
Meta Square Allack (MSA)
0
0
1000
2000
3000
4000
5000
0 1000
2000
3000
4000
5000
Query
Query
(b) T' = 5000 queries
Figure 1: (Left) The schedules for SA (which scales accordingly for different query budgets) and AA [2] compared to Meta Square Attack (MSA) proposed in this work. MSA adapts the update size during the course of the attack for each image. We illustrate the mean and the percentile range for given set of attacked images. (Right) The maximization of the loss for the model of Ding et al. K on 100 CIFARIO images. MSA outperforms SA and AA significantly in terms of the achieved loss.
Therefore, black-box attacks that use only limited information from the model such as the class scores or the final decision often provide an additional perspective on the true robustness of the model
21 and are thus recommended for reliable robustness evaluation 2 22).
very promising direction in the field of black-box adversarial attacks are randomized search schemes for crafting adversarial examples [ 23 24) Combining random search with specific update proposal distributions allows to achieve state-of-the-an black-box efficiency for different threat models such &oo and Ea (1 l, (25). Lo. adversarial patches, and adversarial frames (24). Despite the conceptual simplicity of these methods, the main disadvantage of random search based methods is that the construction of a suitable proposal distribution requires significant manual design and is crucial for competitive performance (see also Figure
In this work, we propose a method that allows circumvent the fine-tuning and reduce the amount of manual design in random search based attacks. We use gradient-based meta-learning to automatically optimize controllers for schedules and proposal distribution on models with white-box access. After meta-training, the controllers can be plugged into a random search attack substituting manually designed schedules and proposal distributions. Importantly, once meta-trained, the controllers do not require any gradient access and can thus be used in a fully black-box setting and without being affected by gradient obfuscation. We consider the proposed methodology for the case of Square Attack for the fo and Eg threat models M We meta-train controllers for update size and color on an adversarially trained [26] ResNet18 27 model with white-box access and apply them to many different models from the RobustBench model zoo (28) that we treat as black-boxes. Since query efficiency is of crucial importance black-box adversarial attacks, we also study the method for different query regimes ranging from several hundreds to several thousands. Depending on the query regime and the attacked model we obtain up to 20% improvement with respect to the baseline schedules proposed by Andriushchenko et al. M and Croce and Hein (2).

---

In short, we make the following contributions:
We frame adversarial attack optimization as a meta-learning problem (Section 3.2p
We formalize the gradient-baser meta-learning for the state-of-the-art Square Attack and propose Meta Square Attack (Section (.3).
We meta-train Meta Square Attack (MSA) on a CIFARIO 488 model with white-box access and show that MSA improves robust accuracy by up to 5.6% on vast range of CI- FAR 10 models with black-box access with respect to the hand-designed search distributions
proposed in previous work [ 2 for the la and &y threat models (Section 4
We show that Meta Square Attack generalizes well to different datasets and to the targeted attack setting. It achieves up 20% better robust accuracy compared to the state-of-the art baseline [ for attacking models on CIFAR 100 and ImageNet (Section 4.2)
2 Related Work
Black-box adversarial attacks: Existing approaches to black-box robustness evaluation can be divided into several groups based on their mode of interaction with the target model. Transfer-based attacks [7 [2] rely on having a model with white-box access that is similar to the targeted model. If this is the case, one can generate adversarial perturbations for this substitute model and transfer them in a black-box setting. A downside of such approaches that similarity between the models is crucial factor. Without it the efficiency of transfer attacks is drastically reduced [29]. Decision- based attacks [13] 20 30) applied to classifiers assume that one can submit queries to the model and receive the predicted class label. Score-based attacks [ [9 consider broader access to the
model and assume the attack receives predicted scores for all the classes. Prior work 15 31 32
use this information to estimate gradient and apply gradient descent. Alzantot et al. 19 propose derivative free approach based on genetic algorithms. Several works use the empirical observation that successful ee perturbations are located the corners of the color cube, therefore instead of continuous optimization one can reduce the problem to a discrete one 12 24 333
Meta-learning and adversarial robustness: The closely related fields of meta-learning 34 and learning to optimize (35) have been employed in the field of adversarial robustness. The idea of learned optimizers [36] 37) was applied to finding adversarial examples in white-box (38] and black- box (39] settings. Meta-learning [40 41 was also used to improve zeroth-order gradient estimation
and allow better query efficiency of black-box attacks [4) Besides that there is the recent work (43)
on automating the existing Auto/ttack (2) framework for robustness evaluation. Meta-learning has
also been used part of adversarial training 38 4
for increasing adversarial robustness.
Square Attack: Square Attack (SA) was proposed by Andriushchenko et al. [ and combines classical random search with a heuristic design of the update rule. This design depends on the geometry of the perturbation set and therefore differs for fxc. and f2-attacks and was later extended also to & (25). As the adversarial attack problem is highly non-convex, good initialization can significantly improve query efficiency. SA uses a stripe initialization motivated by empirical findings [45]. The design principle of the attack is based on the observation that the strongest perturbations are usually found on the boundary of the feasible set [8). For the -csse, updates are sampled as squares parametrized by square size, square color, and position of the square. Performance of SA depends heavily on how color, position, and square size are chosen, which requires manual design.
The square size schedules employed by previous work are relatively sophisticated (indicating non- trivial manual design): Andriushchenko et al. I proposed a schedule parametrized by r" E [0. 1] (the fraction of image pixels to be modified by square in the first query) and the total query budget T. where p' is halved at [0.1, 0.5, 2, 10, 20, 40, 60, 803% of the total query budget. For evaluation on CIFAR1O, Andriushchenko et al. [ suggest different values of p" and report pd = 0.3 as default choice. Croce and Hein 2 proposed a different schedule for SA to be used in AutoAttack: they use p" 0.8 and T = 5000 but fix the halving points of p' as if T 10000. An illustration of the two schedules for = 500 and T = 5000 can be seen in Figure 1
The second aspect that characterizes SA is the distribution from which position and color of the next square are sampled. For positions, the distribution is uniform over all positions for which a square of given size would be fully contained in the input. For colors, SA always generates points on the boundary of the perturbation set (corners of the color cube) and uses a uniform distribution over the 2 different colors (with e being number of channels, typically = 3).
3

---

Thus SA either relies on extensive manual design (for the square size schedules) or resorts to simple baseline choices (such as the uniform distributions over colors and positions) which might be suboptimal. In this work, we show that meta-learning SA consistently improves the already strong performance of SA (see Section (.2) with very little manual design and identify non-trivial patterns that increase attack efficiency (see Section 4.3
3 Method
In the following. we briefly introduce the formulation of the optimization problem for an adversarial attack, rephrase it in the from of a meta-learning problem, and introduce our method for learning the search distribution of specific random search based black-box adversarial attack, namely Square Attack [
We denote this method as Meta Square Attack (MSA).
3.1 Adversarial Robustness Evaluation
Let K be the number of classes in classification problem and f A K-1 be classifier which maps a d-dimensional input to
K- = ( =
-k-....))))) (Kn.... E R Σ P: and pi 2 0 for 0,... K -11-.
which denotes the set of probability distributions over the discrete possible outcomes. For a label y (O...., K 1}, loss function I: A x (o,..., K - 1} + I, perturbation set S, and operator a, we define the robustness evaluation problem as:
VU, x. max (f(((r)))) EES
For S = |К S. c) and a(x, {) 13= + (where [o is the projection onto [0, 1] one obtains the standard Cp ball threat model for images. Assuming that the loss function and operator are fixed, we denote L(f, x. E) = ((f(a(x,))) y) as functional that one needs to maximize in robustness evaluation.
Since exact maximization of Equation ① is intractable in the general case 77. we consider (potentially non-deterministic) procedure A_ (L. 2,,, x.,.) called adversarial attack. This attack A., is parametrized by hyperparameters w and designed with the intention that g" ~ (L,,, S. y) with R E becomes an approximate solution (tight lower bound) of 2(, y). that is (S,x,V) L(S, x. y, (4) should become small (in expectation). Optimizing the hyperparameters of the attack via L(f, x, y, { can allow a tighter lower bound (f,. a, y). Unfortunately, this
max (L.f.o))
maximization still intractable typically, for instance when is black-box (no gradient information is available), the number of queries to f per data (x, y) is limited, or A. has high variance.
3.2 Black-box Adversarial Attack Optimization as a Meta-learning Problem
We now frame optimization of the adversarial attack in the query-restricted black-box setting meta-learning problem. We follow the taxonomy proposed in the recent survey on meta-learning by Hospedales et al. [34].
First, we formulate our meta-objective (the specification the goal of meta-learning): we assume data to be governed by distribution (I, y) ~ DD and classifiers defined on this data, which need to be evaluated, by distribution maximize the lower bound L(f, y. of V (f,, æ, y) in expectation across models f ~ F, data (x,, v) D. and the stochastic attack e A
F. Our meta-objective is to find parameters w' of the attack A. that
argmax
E JNF (Z.))D (L.
E
E
Here, the expensive optimization w is amortized across models and data. More specifically, we assume finite sets of data D N (II,)) D) and classifiers F (fs fy F}

---

are available. Moreover, we assume the f, E F allow white-box access and quasi- uuaii-unrettrieted number of queries. The sets D and F can be used during meta meta- training of the attack, that is the objective during meta-training becomes w = arg max R( F. D, () with R(F, D, w) = y). However, the ultimate goal of meta- Efer L(ry)ED J, U, ( and 5 Aw S. (T,
learning is to apply A_- during meta-lesting to unseen (2. ~ DD and unseen f ~ F that allow only black-box and query-limited access, and maximize (L..A.(L.11..)) L Iz, y, {*), that is: the attack needs to generalize across models and data.
Next, define the meta-representation, that is how the adversarial attack A,, is designed and parametrized such that gencralization across f F is effective. In this work we focus on random search based adversarial attacks for black-box robustness evaluation since they have achieved strong results in prior work and are amenable to meta-learning. Let Au be a random search based attack with query budget limited by T. Then adversarial perturbation & = 5" (L, J. x. y) is obtained using the following iterative procedure:
5 ~ DO; 5-²
argiax SE Mu(((*++++))
L(,,,,V, 8 ~
(3)
where 1Is corresponds to the projection onto the perturbation set S.
That is, we assume fixed distribution D for initializing the perturbation 5 but meta-leamnalle D., for the update proposals 8++1_ Importantly, D., depends on the entire attack trajectory up to step the classifier f when applied to data (æ, v), our meta-learned random search attack can adapt to the classifier and data at hand. We provide more details on D., for the specific case of Square attack ① in Section 3.3
t. Since this trajectory contains implicitly information
The meta-optimizer (how we optimize the meta-objective) in our case assumes that both the loss function / and A are (stochastic) differentiable with respect w we can find differentiable relaxations (as we will discuss in Section 3.3). Thus the meta-parameters w can be optimized using stochastic gradient descent mini-batches B C D based the (stochastic) gradient
g VWR((D,,,) = E Σ
Vub(fy, Di.
Vis Vi. En.g):
(4)
where Eup ~ As Jj: 34,, V:). However, due to the stochasticity of A,, induced by DD' and Dw, the discrete argmin in the update step of A.,, and the length T of the unrolled optimization (often in the order of hundreds to thousands queries), g would have very high variance and typically one would also face issues with vanishing or exploding gradients. To address this, we propose using a greedy alternative instead:
T-
Σ
Σ Ji (1.g,)5)
Σ
V I Vs. Ts(S + 8)+
(5)
T
Importantly, even though ç depends on w for 0, we do not propagate gradients with respect to w through g", that is we set Vw ;= 0. By this, the gradient corresponds to optimizing D., in myopic way, such that proposals 81+11 (t. 5", . 5*) are trained to maximally increase While this introduces a bias of acting myopic and greedy, it works
the immediate loss in step + 1. reasonably well in practice.
We can now rewrite V L(i,, Zj, +8++) = LJin V 644 We note that 0t- can be a very high variance estimate of Dw 50 "r."...., 5", 8*) depending on the stochasticity of D., However, and models and data, g is still a sufficiently good estimate in practice.
it is an unbiased estimate and average over very many steps T
3.3 Meta Square Attack
In this section, we demonstrate how the proposed meta- meta-learning approach can be applied to Square Attack (SA) [1] with Eoo threat model. We denote the resulting meta-learned attack as Meta Square Atlack (MSA). We keep DD as the stripe initialization from SA and focus on meta-learning D., as governs all but the first step. As discussed in Section 2 sampling g'+1 D(I) in SA proceeds
by computing a square size (its width in pixels) s; (t) E { smaz} and sampling
5

---

position (pr, Py) ~ (*(ss E {l..... Smaz -s s}² and a color c~ T" E [cI....Cm) In SA, x² is heuristic schedule that depends on (and differs in prior work ( and both T" and x" are uniform distributions. 8++1 is then chosen to be zero everywhere except for square of size at position p with color c. Possible colors G correspond to the eight corners of the RGB hypercube with foR norm That is c E (+e, tt, tc), while Smar is chosen maximally with the constraint that all sampled squares must not exceed the image dimensions. We keep TP as uniform distribution, but meta-learn the controllers _u and Tee with parameters w We).
Update size controller -.... We design Tu, as a multi-layer perceptron (MLP) with parameters wis- The MLP outputs scalar value s' R and we map this value the actual update size via 8 == =ss)) (Smaz - 1) + 1 with (x) = 1/((1 + *). During meta-testing, we round the continuous E [1, Smaz] to discrete value [s] E (1, ,...... Smaz). )- As this would block gradient flow during meta-training, we relax the square sampling in SA such that it supports continuous update sizes. The details of this relaxed sampling can be found in the Appendix A.3. Importantly, it is only conducted during meta-training and not in the final evaluation during meta-testing.
We provide two scalar inputs the MLP Th,: (a) the current query t encoded logz( / + where T is the maximal number of queries. It ensures that the input stays in the range [0. 1] for / < T. We use T = 5000. (b) Let y = H (L(f, xr l5 + ))++ - L(f, x, y, {¹) E {0, 1 be an indicator of whether adding 8 at time ++1 1 improved the loss (for H being the Heaviside step-fnncionn. The MLP gets as second input at time the value R = y R (1 (1- -))" /r0 with R = 1. Here 7 is a decay term that controls how quickly past experience is "forgotten" and r = 0.25 is a constant whose purpose is to ensure that the MIP's second input has a similar scale as the first (namely in [0, 1)). Intuitively, (a) allows to schedule update sizes based on time step of the attack (this information is also used in SA itself) while (b) allows adapting the update size based on the recent success frequency Rs of proposals (for instance reducing the update size if few proposals were successful recently). Thus (b) allows the schedule to adapt to classifier f and data (z. y) at hand.
Color controller Th.- We design the color controller Th, as a categorical distribution of Cat(af...... ), where each af E E. is predicted by an MLP with weights we. The m MLPs for the a share weights we but differ in their inputs. In order differentiate through the categorical distribution at meta-train train time, we reparametrize the categorical distribution with Gumbel-softmas and draw discrete (hard) samples in the forward pass but treat them as soft samples in the backward pass [46] 47). Additionally, we ensure that every color q is sampled at least with probability pini by assigning P(c:) = Piiin + (1 - mpfmmn ( Pcataf (c:). This ensures continuous exploration of all m colors.
The m MLPs get two inputs: (a) the current query encoded as log2( + 1) (same encoding as for the step size controller and also same for all MLPs). (b) Information regarding the recent success frequency of proposals 5 based on squares of the respective colors (c' = Q:):
[R - + - -rr'/////////// /ro if = otherwise"
R
This second input allows the controller to leam, e.g.,
R
to sample those colors more often that resulted in higher success frequency recently.
4 Experiments
We perform an empirical evaluation of Meta Square Attack (MSA). First, we consider the data distribution D of CIFARIO 48) images and classifier distribution F consisting of the classifiers robust with respect to the fo threat model. We use this setting for the meta-training as discussed in Section 4.1 We further consider how the controllers trained for these distributions generalize to working with the other data distributions of CIFAR 100 and ImageNet and corresponding distributions of classifiers defined on this data. We also discuss the meta-training for the distribution of the classifiers robust with respect to the fy-threat model in the Section A.5.
We compare the performance of MSA in different query budget regimes to manually designed schedules for Square Attack proposed by Andriushchenko et al. [1] (denoted by SA) and Croce and Hein 2 (denoted by AA). The reason why we have chosen this evaluation mode instead of reporting accuracy and average number of queries for some single fixed budget is that the original SA approach proposes to scale the schedule to a given budget (Figure Dp. Hence, it uses the knowledge of the attack budget and the schedule used for 500 queries is not truncated version of the schedule used for

---

Table 1: MSA compared SA [ and AA 22 in the -threat model with 8/255 on 1000 CIFARIO test images. We report mean and standard error of robust accuracy across 5 runs with different random seeds. The full results for 16 CIFARIO models can be found Table
Accuracy (%)
Query budget
Model
Atlack
Clean Robust
500
1000
2500
5000
SA
69.7:10.15
63.5
55.11:0.44
50.810,08
Wong et
51
83.34
43.21
AA
69.5++0211
63.9=0.10
57.4
53.6=2.066
MSA
63.9:10.12
59.1
53.0::.16
49.8
SA 72.3++0.10
66.6=0016
60.5+0.09
57.3++0.08
Huang et al.
52
83.48
53.34
AA
70.6:10.10
66.5
61.2:10.10
58.5
MSA
66.1++0.10
621
58.7:10.05
56.8
5000 queries as it is done in AA. Since adapting the schedule to different query budgets is a crucial factor for the manually designed schedules that we consider as baselines, we choose the evaluation regime that allows take this factor into consideration. Section 4.2 summarizes the experimental results (for more details see the Section A.1 in the Appendix) and Section 4.3 analyzes the behavior learned by the controllers.
4.1 Meta- Training and Controller Design
We meta-train the controller on a single robust model ~ with white-box access (the "source model"). The source model was designed such that attackers could easily and cheaply acquire it themselves: the model has ResNet18 [27] architecture and was trained on the CIFAR 10 training set using adversarial training (26) with the advertorch [49] package. Adversarial training done using -PGD attack with = 8/255, fixed step size of 0.01, and 20 steps.
For both update size and color controllers, we use MLP architectures with 2 hidden layers, 10 neurons each, and ReLU activations. We purposefully did not finetune the MLP architecture. Meta- training run
set D consisting of 1000 images from CIFARIO test set (different from the ones used evaluation controllers in the next subsection) and Square Attack with a query budget of 1000 iterations. Therefore, controller behaviour on query regimes higher than 1000 are obtained by extrapolation of the behaviour learned for 1000 iterations. Both controllers were trained simultancously for 10 epochs using Adam optimizer with batch size 100 and cosine step size schedule 500 with learning rate 0.03. The total loss improvement over the attack was used as meta-loss that optimized in meta-training. We always the attack on all images for the full budget T, since removing images from the attacked batch would cause discontinuity in the meta-loss. All computations including meta-training and evaluation of the controllers were performed on a single Nvidia Tesla V100-32GB GPU.
4.2 Evaluation
In this section, we evaluate how the Meta Square Attack (MSA) obtained by training CIFARIO model with white-box access discussed in the Section 4.1 performs for different models and datasets.
Table I iillustrates that MSA transfers well to two selected robust CIFAR10 10 models. Moreover, Table 2 reports results aggregated over a broad range of 16 robust CIFAR 10 models from RobustBench (see Table 8 in the Appendix A.4 for details). We report mean, minimal, and maximal improvement across all the 16 models. We observe a consistent improvement for each considered query budget regime, which is especially pronounced for lower query regimes of 500 and 1000 queries. The improvements generalize to a budget of 5000 queries, which is five times higher than the one used during meta-training.
As described in Section 3.3 the input to MSA, and MSA, is not specific the data distribution. Therefore, also show that the adaptation principles learned CIFARIO model transfer well to attacking models that not only have different architecture but also operate on significantly different
detta-training on more than one source model could improve generalization across models, but we found that even meta-training single model generalizes sufficiently well.
7

---

Table Improvement -obust accuracy of our MSA with respect the best of the previous Square Attack configurations, SA [ and AA 2 in the setting of Table The results are accumulated across 16 robust CIFARTO models from RobustBench (see Table for full results).
Query budget
500
1000
2500
5000
Improvement in
mean
min
max
mcan
min
mean
min
mean
min
max
robust accuracy (%)
4.29
3.1
5.6
3.87
1.63
0.9
2.1
0.38
-0.1
Table 3: Transfer to CIFARI00: MSA trained a CIFARIO model consistently outperforms SA 1 and AA 2 on CIFARI00 (1000 images) in robust accuracy for the e -thrett model with 8/255. Averaged across runs with different random seeds.
Accuracy (%)
Query budget
Model
Attack
Clean Robust
500
1000
2500
5000
SA
43.3:10.17
38.7:10099
33.9:10.28
32.3::.20
Wu et al.
53
60.38
28.86
AA
41.3::0.00
37.6=t.00
35.0=10.06
32.7=:0.55
MSA
37.8=10077
35.5:10.12
03.1
32.2+0003
SA 48.9+1.03
42.3::.20
33.6=10.09
30.5+0.06
Cui et al.
54
AA
47.5=10117 42.8=0.09
35.9
32.510.15
70.25
27.16
MSA
42.610.13
37.810.12
32.5+0.30
30.1
data distributions: Table demonstrates generalization of the learned controllers for attacking robust models for CIFAR 100 488. We also consider the transfer to ImageNet [57] dataset that has significantly higher input dimension and number of classes than CIFAR 10. In Table 4 one can see that MSA significantly improves the results even in the high extrapolation regime of 5000 queries. also observe considerable improvement of the robust accuracy estimate for the targeted attacks on undefended ImageNet models (Table Results for applying the size controller trained specifically for the &e threat model (together with the color controller trained for loa) are in Table We observe consistent improvement of about 3% robust accuracy for all of the considered query budgets. The magnitude of improvement for different datasets and threat models depend on two factors: how well the adaptation mechanism learned by our controllers generalizes the given setting and how suitable the hand-designed search distributions of the baselines [ 2 are for each particular problem. The consistency of the improvement indicates that the adaptive search distribution makes Meta Square Attack more efficient in the majority of the settings.
4.3 Analysis Learned Controllers
As the learned controllers are black-boxes (implemented by MLPs), may non non-trivial understand their realized strategy. We present some analysis of the controllers' internal strategy based on their empirical behavior. Further analysis can found in the Section A.4.
Table 4: Transfer to ImageNet: MSA trained on a CIFAR10 model consistently outperforms SA I and AA [2] on 1000 ImageNet validation set images lac -rouss accuracy for e = 4/255. For SA use pd 0.05 in Andriushchenko et al. I Averaged across 3 different runs.
Accuracy (%)
Query budget 2500
Model
Attack
Clean Robust
500
1000
5000
resnet18
SA
50.6
48.14:1.18
43.9.11.00
40.3
Salman et al.
55
52.5
25.0
AA
45.2
43.5:10.86
41.0-11.07
39.0+11.21
MSA
4..0
41.7-10.94
39.1+11.33
37.8
resne150
SA 59.8++0644
57.2+0.79
52.9+11111
48.6++1.31
Engstrom al.
56
63.4
27.6
AA
54.6+0099
52.8++109
50.3+1.43
48.141.18
MSA
52.5
50.8+1147
48.0
45.8++1.35

---

Table MSA trained on CIFARIO model attacking the undefended ImageNet models the foo threat model with e 0.05. We compare our method with SA and set p" = 0.05 for the untargeted case and yd 0.01 for the targeted case as suggested by Andriushchenko et al. M. For the targeted attacks robust accuracy is the fraction of the total number of images that was initially correctly classified by the model and not shifted to the target class during the attack. We provide clean accuracy of the models subset of 1000 ImageNet validation set images that consider.
Clean acc. (%)
Untargeted
Targeted
Model
Atlack
500
1000
2500
5000
500
1000
2500
5000
SA
8.8
5.1
0.2
76.9
75.1
62.5
34.4
ResNet-50 58
77.3
MSA
2.9
0.8
0.0
0.0
67.1
52.0
27.8
12.1
SA
2.8
0.9
0.0
0.0
74.5
72.2
51.5
17.4
VGG-I6-BN 59
75.0
MSA
1.8
0.2
0.0
0.0
62.5
45.2
16.5
3.5
SA
16.6
6.1
2.3
1.0
77.5
76.4
70.9
59.8
Inception v3
77.6
MSA
10.2
5.1
2.6
1.3
74.4
70.6
60.1
49.5
Table 6: f2-threat model: MSA₂ uses the update size controller trained for the &g attack on
CIFARIO model (see Section 4.1 The color controller is the same for the foo case. 22-MSA outperforms consistently 22 I and A- [ terms of f--rousst accuracy for 0.5 on 1000 CIFAR10 images. The full results for 5 models can be found in the Table 10.
Accuracy (%)
Query budget
Model
Attack
Clean Robust
500
1000
2500
5000
SA
85.5
83.9:10118
81.1+:0.00
78.7=10066
Ding al.
3
88.02
66.09
AA
82.8+0009
81.4+10.06
79.3++0.07
77.6++0.09
MSA₂
8.03++0033
80.9++0.07
77.4++0.99
75.8+
SA
86.3+-0.07
84.7++0.00
81.4+00.66
79.7++0007
Rice et al.
61
88.67
67.68
AA 83.7+-0.12
81.4+-0.99
79.9+-0.09
78.6+00.8
MSA₂
82.6110.99
81.0+10.77
78.7+10.33
76.9
Figure 2a illustrates the behaviour of the update size controller MSA,. It shows how the controller chooses the update size over time in an artificial scenario where the success probability P(r' 1) modeled to be constant. As implemented also by the heuristic schedules SA and AA, update size decays over time. However, the decay pattern depends heavily on P(r 1), with slower decay for larger P(r 1). This property not implemented by heuristic schedules, but makes sense intuitively: high P(r" = 1) corresponds to a situation where the current perturbation g can be improved relatively easily by pearse-grained changes implemented by the current update sizes; in this case makes sense to first get the coarse- coarse-grained structure "right", before proceeding to fine-grained details that can be captured by small squares.
Figure 2b illustrates the empirical behavior of the color controller MSA, when attacking the model by Ding et al. 3 Shown are histograms over 500 images for the frequency of specific colors being sampled up to the respective iteration. Prior work like SA and AA maintained a uniform distribution of colors. However, the learned controller shows clear preference for sampling black and white more often than uniform (p RJ 0.18 vs. = 0.125 for uniform). blue and yellow approximately with p 0.125, and the other colors less often than uniform. Since the color controller depends the success rates Ht of colors, this behavior is not hard-coded into the controller but identified on-the-fly during the attack (so behavior can differ for models with different vulnerabilities).
Table demonstrates the ablation studies with respect to the used controllers on the model by Gowal et al. 622. We observe that MSA, combined with the uniform color distribution alone significantly improves the results of SA and AA most the query budgets (with the exception of the strong extrapolation regime of 5000 queries). The controller MSA, combined with all schedules improves the performance with the exception of 500 queries regime for SA and MSA, where provides an equal slightly worse result in some cases.

---

Schedule for fixed value of success probability
Color Color Frequency per Image
2500
Queries
0.4
30
0.3
Update Size
Pt
20
0.0
0.3
0.2
0.1
0.5
10
0.2
1.0
0.1
0.0
black
blue
cyan
red
mag.
yellow
white
0
1000
2000
3000
4000
5000
Query
(b)
Figure 2: (a) Square-size schedule obtained from MSA, over time for fixed values of success probability P(r 1) (averaged over 25 runs) (b) Illustration of color frequency histogram 500 images after 2500 queries of MSA
Table 7: We compare the update size controller MSA, to the schedules from SA M and AA 2 in the foc threat model with 8/255 model by Gowal al. (62 with 1000 CIFAR10 10 test images. We also compare the uniform color sampling to our color controller MSA Averaged across 5 runs with different random seeds.
Update size
Color
Query budget
schedule
sampling
500
1000
2500
5000
SA
Uniform
80.6:10.09
76.7=0007
70.8+:.14
67.5=1007
SA
MSA.
81.0=10.05
76.410.08
69.910.10
67.2:10.07
AA
Uniform
80.0
76.8+0.11
72.2:0.100
69.2=0008
AA
MSA.
79.9:0.12
76.7+0.03
71.6::0.17
68.8+0.07
MSA,
Uniform MSA.
76.9+10.05
73.7+0.05
69.8+10.13
67.6+10.04
MSA,
76.9
73.4+0.13
69.0
6.02
Conclusion
In this work propose theoretical framework for meta-leamiin search distributions that help to improve efficiency of random search based black-box adversarial attacks. We implement and investigate this framework for Square Attack with lo and la perturbations. Our experimental results show that learned adaptive controllers improve attack performance across different query budgets and generalize new datasets as well as targeted attacks. Future directions are applying our framework to other random-search based attacks and threat models as well as learning controllers for sampling positions or even geometric primitives (going beyond squares).
Ethical and Societal Impact This work contributes to the field of black-box adversarial attacks, which can be used for benign purposes like reliably evaluating the robustness of ML systems as well as malign ones such as identifying and exploiting weaknesses of these systems. Increasing the query-efficiency and success rate of black-box attacks can amplify safety and security concerns in domains such as highly automated driving robotics. Meta Square Attack allows more efficient generation of imperceptible image distortions that may allow bypassing automated content-control otherwise offensive content. We are
systems for filtering images with violent, pomographic, optimistic that the research on adversarial attacks contributes to developing defenses and mitigation strategies that outweigh these risks in the medium term. A general mitigation strategy could be to add check a system which rejects predictions for a sequence of inputs which all differ by at most an fp distance of some This would make most ccose-based blx attacks for image-specific perturbations ineffective, including Meta Square Attack.
10

---

Acknowledgements
Matthias Hein is member of the Machine Learning Cluster of Excellence, EXC number 2064/1 Project number 390727645 and of the BMBF Tübingen Al Center, FKZ: 011S18039B.
References
[1] Maksym Andriushchenko, Francesco Croce, Nicolas Flammarion, and Matthias Hein. Square attack: query-efficient black-box adversarial attack via random search. In ECCV, 2020.
[2] Francesco Croce and Matthias Hein. Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks. In ICMI., 2020.
[3] Gavin Weiguang Ding, Yash Sharma, Kry Yik Chau Lui, and Ruitong Huang. MMA training: Direct input space margin maximization through adversarial training. In ICLR, 2020.
[4] C. Szegedy, W. Zaremba, I. Sutskever, J. Bruna, D. Erhan, Goodfellow, and R. Fergus. Intriguing properties of neural networks. In ICLR, 2014.
[5] Anurag Ranjan, Joel Janai, Andreas Geiger, and Michael Black. Attacking optical flow. In ICCV, 2019.
[6] Andrew Ilyas, Shibani Santurkar, Dimitris Tsipras, Logan Engstrom, Brandon Tran, and Aleksander Madry. Adversarial examples are not bugs, they are features. NeurlPS, 2019.
[7] G. Katz, C. Barrett, D. Dill, K. Julian, and M. Kochenderfer. Reluplex: An efficient smt solver for verifying deep neural networks. In CAV, 2017.
[8] Nicholas Carlini and David A. Wagner. Towards evaluating the robustness of neural networks. IEEE Symposium on Security and Privacy (SP), pages 39-57, 2017.
[9] lan J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adver- sarial examples. ICLR, 2015.
[10] Anirban Chakraborty, M. Alam, Vishal Dey, A. Chattopadhyay, and Debdeep Mukhopadhyay, Adversarial attacks and defences: A survey. arXiv: 1810.00069, 2018.
[11] A. Athalye, N. Carlini, and D. Wagner. Obfuscated gradients give a false sense of security: Cireumventing defenses to adversarial examples. In ICMI., 2018.
[12] A. Al-Dujaili and U.-M. O'Reilly. There are no bit parts for sign bits in black-box attacks. In ICLR, 2020.
[13] J. Chen, M. Jordan, and Wainwright M. J. HopSkipJumpAtttakk query-efficient decision- based attack. In IEEE Symposium on Security and Privacy (SP), 2019.
[14] S. N. Shukla, A. K. Sahu, D. Willmott, and Z. Kolter. Black-box adversarial attacks with Bayesian optimization. arXiv preprint arXiv:1909.1388 13857, 2019.
[15] A. Ilyas, L. Engstrom, A. Athalye, and Lin. Black-box adversarial attacks with limited queries and information. ICML, 2018.
[16] Z. Yan, Y. Guo, and C. Zhang. Subspace attack: Exploiting promising subspaces for query- efficient black-box attacks. In NewrlPS, 2019.
[17] S. Cheng, Y. Dong, T. Pang, H. Su, and J. Zhu. Improving black-box adversarial attacks with a transfer-based prior. In NeurIPS, 2019.
[18] M. Seungyong. Gaon, and O. S. Hyun. Parsimonious black-box adversarial attacks via efficient combinatorial optimization. In ICML, 2019.
[19] M. Alzantot, Y. Sharma, S. Chakraborty, and M. Srivastava. Genattack: practical black-box attacks with gradient-free optimization. Genetic and Evolutionary Computation Conference (GECCO), 2019.
11

---

[20] Huichen Li, Xiaojun Xu, Xiaolu Zhang, Shuang Yang, and Bo Li. Qeba: Query-efficiens boundary-baad blackbox attack. In CVPR, 2020.
[21] Zhichao Huang, Yaowei Huang, and Tong Zhang. Corrattack: Black-box adversarial attack with structured search. arXiv:2010.01250, 2020.
[22] Florian Tramer, Nicholas Carlini, Wieland Brendel, and Aleksander Madry. On adaptive attacks adversarial example defenses. In NeurIPS, 2020.
[23] C. Guo, J. R Gardner, Y. You, A. G. Wilson, and K. Q. Weinberger. Simple black-box adversarial attacks. In JCML, 2019.
[24] Francesco Croce, Maksym Andriushchenko, Naman D. Singh, Nicolas Flammarion, and Matthias Hein. Sparse-rs: versatile framework for query-efficient sparse black-box adversarial attacks. arXiv:2006. 12834, 2020.
[25] Francesco Croce and Matthias Hein. Mind the box: happd for sparse adversarial attacks on image classifiers. In ICML, 2021.
[26] A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Valdu, Towards deep learning models resistant to adversarial attacks. ICLR, 2018.
[27] Kaiming He, X. Zhang. Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In CVPR, 2016.
[28] Francesco Croce, Maksym Andriushchenko, Vikash Sehwag, Nicolas Flammarion, Mung Chiang, Prateek Mittal, and Matthias Hein. Robustbench: a standardized adversarial robustness benchmark. arXiv:2010.09670 2020.
[29] Zhichao Huang and Tong Zhang. Black-box adversarial attack with transferable model-based embedding. In ICLR, 2020.
[30] Wieland Brendel, Jonas Rauber, and Matthias Bethge. Decision-based adversarial attacks: Reliable attacks against black-box machine learning models. In ICLR, 2018.
[31] J. Uesato, B. O' O'Donoghue, A. Van den Oord, and P. Kohli. Adversarial risk and the dangers of evaluating against weak attacks. In ICML, 2018.
[32] A. N. Bhagoji, W. He, B. Li, and D. Song. Practical black-box attacks on deep neural networks using efficient query mechanisms. In ECCV, 2018.
[33] L. Meunier, J. Atif, and O. Teytaud. Yet another but more efficient black-box adversarial attack: tiling and evolution strategies. arXiv preprint, arXiv: 2019.
[34] Timothy Hospedales, Antreas Antoniou, Paul Micaelli, and Amos Storkey, Meta-learning in neural networks: A survey. IEEE PAMI, 2021.
[35] Tianlong Chen, Xiaohan Chen, Wuyang Chen, Howard Heaton, Jialin Liu, Zhangyang Wang, and Wotao Yin. Learning optimize: primer and benchmark. arXiv:
2021.
[36] Marcin Andrychowicz, Misha Denil, Sergio Gomez Colmenarejo, Matthew W. Hoffman, D. Pfau, Tom Schaul, and N. D. Freitas. Learning to learn by gradient descent by gradient descent. In NIPS, 2016.
[37] Yutian Chen, Matthew W. Hoffman, Sergio Gomez Colmenarejo, Misha Denil, Timothy P. Lillicrap, Matt Borvinick, and Nando de Freitas. Learning to learn without gradient descent by gradient descent. In ICML, 2017.
[38] Yuanhao Xiong and Cho-Jui Hsich. Improved adversarial training via learned optimizer. In ECCV, 2020.
[39] Yangjun Ruan, Yuanhao Xiong, Sashank Reddi, Sanjiv Kumar, and Cho-Jui Hsieh. Learning to learn by zeroth-order oracle. In ICLR, 2020.
12

---

[40] Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adapta- tion of deep networks. In ICML, 2017.
[41] Alex Nichol, Joshua Achiam, and John Schulman. On first-order meta-leaming algorithms. arXiv: 1803.0999, 2018.
[42] Jiawei Du, Hu Zhang, Joey Tianyi Zhou, Yi Yang, and Jiashi Feng. Query-efficient meta attack deep neural networks. In ICLR, 2020.
[43] Chengyuan Yao. Pavol Bielik, Petar Tsankov, and Martin Vechev. Automated discovery of adaptive attacks on adversarial defenses, arXiv:2102.11860, 2021.
[44] Jan Hendrik Metzen, Nicole Finnie, and Robin Hutmacher. Meta adversarial training against universal patches. W1Xv:2201.11453, 2021.
[45] Yin. R. G. Lopes, J. Shlens, E. D Cubuk, and J. Gilmer. Fourier perspective on model robustness in computer vision. In NeurlPS, 2019.
[46] Eric Jang. Shixiang Gu, and Ben Poole. Categorical reparametrization with gumbel-softmax. In ICLR, 2017.
[47] Chris J. Maddison, Andriy Mnih, and Yee Whye Teh. The Conerete Distribution: A Continuous Relaxation of Discrete Random Variables. In ICLR, 2017.
[48] Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.
[49] Gavin Weiguang Ding, Luyu Wang, and Xiaomeng Jin. AdverTorch v0.1: An adversarial robustness toolbox based on pytorch. arXiv: 1XXiv:9022.0722 2019.
[50] Ilya Loshchilov and Frank Hutter. SGDR: stochastic gradient descent with warm restarts. In ICLR, 2017.
[51] Eric Wong, Leslie Rice, and J. Zico Kolter. Fast is better than free: Revisiting adversarial training. In ICLR, 2020.
[52] Lang Huang, Chao Zhang, and Hongyang Zhang. Self Self-adaptive training: beyond empirical risk minimization. In NeurlPS, 2020.
[53] Dongxian Wu, Shu tao Xia, and Yisen Wang. Adversarial weight perturbation helps robust generalization. In NeurIPS, 2020.
[54] Jiequan Cui, Shu Liu, Liwei Wang, and Jiaya Jia. Learnable boundary guided adversarial training. In ICCV, 2021.
[55] Hadi Salman, Andrew Ilyas, Logan Engstrom, Ashish Kapoor, and Aleksander Madry. Do adversarially robust imagenet models transfer better? In NeurlPS, 2020.
[56] Logan Engstrom, Andrew Ilyas, Hadi Salman, Shibani Santurkar, and Dimitris Tsipras. Robust- ness (python library), 2019. URL
[57] Jia Deng, Wei Dong. Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large- scale hicrarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pages 248-255. Iece, 2009.
[58] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In CVPR, 2016.
[59] Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In ICLR, 2015.
[60] Christian Szegedy, Vincent Vanhoucke, Sergey loffe, Jonathon Shlens, and Zbigniew Wojna. Rethinking the inception architecture for computer vision. In CVPR, 2016.
[61] Leslie Rice, Eric Wong, and Zico Kolter. Overfitting in adversarially robust deep learning. In ICML, 2020.
13

---

[62] Sven Gowal, Chongli Qin, Jonathan Uesato, Timothy Mann, and Pushmeet Kohli. Uncov- ering the limits of adversarial training against com-bounded adversarial examples. arXiv: 2010.03593, 2021.
[63] Yair Carmon, Aditi Raghumathan, Ludwig Schmidt, Percy Liang, and John C. Duchi. Unlabeled data improves adversarial robustness. In NeurlPS, 2019.
[64] Maksym Andriushchenko and Nicolas Flammarion. Understanding and improving fast adver- sarial training. In NeurlPS, 2020.
[65] Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric P. Xing, Laurent El Ghaoui, and Michael I. Jordan. Theoretically principled trade-off between robustness and accuracy. ICML, 2019.
[66] Dan Hendryeks, Kimin Lee, and Mantas Mazeika. Using pre-training can improve model robustness and uncertainty. In ICML, 2019.
[67] Yisen Wang, Difan Zou, Jinfeng Yi, James Bailey, Xingjun Ma, and Quanquan Gu. Improving adversarial robustness requires revisiting misclassified examples. In ICLR, 2020.
[68] Chawin Sitawarin, Supriyo Chakraborty, and David Wagner. Improving adversarial robustness through progressive hardening. UrXiv:2003.09347, 2020.
[69] Jingfeng Zhang, Jianing Zhu, Gang Niu, Bo Han, Masashi Sugiyama, and Mohan Kankanhalli. Geometry- instance-reweighted adversarial training. In ICLR, 2021.
[70] Jingfeng Zhang, Xilie Xu, Bo Han, Gang Niu, Lizhen Cui, Masashi Sugiyama, and Mohan Kankanhalli. Attacks which do not kill training make adversarial learning stronger. In ICML, 2020.
[71] Dinghuai Zhang, Tianyuan Zhang, Yiping Lu, Zhanxing Zhu, and Bin Dong. You only propagate once: Accelerating adversarial training via maximal principle. In NeurlPS, 2019.
[72] Maximilian Augustin, Alexander Meinke, and Matthias Hein. Adversarial robustness on in- and out-distribution improves explainability. In ECCV, 2020.
[73] Jérôme Rony, Luiz G. Hafemann, Luiz S. Oliveira, Ismail Ben Ayed, Robert Sabourin, and Eric Granger. Decoupling direction and norm for efficient gradient-based 12 adversarial attacks and defenses. In CVPR, 2019.
[74] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Yang. Zach Veto,o, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In NeurlPS, 2019.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] Main limitations of our work
that we assume the availability of source models and data from the target distribution (see Section 3). Moreover, we discuss that the learned controllers are black-boxes and
thus more difficult to interpret than manually designed controllers (see Section 4.3
(c) Did you discuss any potential negative societal impacts of your work? [Yes] Please refer "Ethical and Societal Impact" in Section 5
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [N/A] We do not provide theoretical results.
14

---

(b) Did you include complete proofs of all theoretical results? [N/A] We do not provide theoretical results.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section 4.1
(c) Did you report error bars (e-g., with respect the random seed after running experi- ments multiple times)? [Yes] Main results in the Section 4.2 were obtained by running evaluation to times with different random seeds. Means and standard errors are reported.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] As stated in 4.1 all computations including meta-training and evaluation of the controllers were performed on a single Nvidia Tesla V100-32GB GPU. We can not report the total amount of compute since did not track it. However, including compute on the GPU clusters on which the experiments have been performed do no longer leave carbon footprint.
organization is carbon neutral that all its actívities
4. If you using existing assets (c.g., code, data, models) or curating/releasing
assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] Our work uses pre-trained models from the model zoo provided by RobustBench 28 (https:/ robustbench. gi githuu.... 1o/). We cite this source as well as authors of the methods used to train each model (see Section 4.2). Moreover, we cite the datasets that we use for the evaluation.
(b) Did you mention the license of the assets? [Yes] For licensing information supple- mentary material
(c) Did you include any new assets either in the supplemental material or as URL? [Yes] We submit the source model and the controllers as part of the supplementary material.
(d) Did you discuss whether and how consent was obtained from people whose data you't 'r using/curating? [Yes] As stated in supplementary material, in this work we only use the data published under formal licenses.
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A] As stated in supplementary material, to the best of our knowledge data used in this project does not contain any personally identifiable information or offensive content.
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicablc? [N/A] No crowdsourcing was used and no research with human subjects was conducted
(b) Did you deseribe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A] No crowdsourcing was used and no research with human subjects was conducted
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A] No crowdsourcing was used and no research with human subjects was conducted
15


Reviews:
[{"review_id": "g3yinm0NCr1", "reviewer": "Reviewer_UUwL", "summary": "The paper proposes a meta-learning approach to produce optimistic hyperparameters for score-based black-box adversarial attack, especially for Square Attack. A controller is trained on the source network to find the optimistic schedule of hyperparamters. The success rate is improved using the controller.", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "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\n1. Meta learning is a reasonable and promising way to improve the query efficiency and success rate of black-box attack. The attacker can use the information from the query and adjust itself to gain better performance.\n2. The experiments, despite quite inadequate, do show that the hyperparameters of the Square Attack is sensitive to some hyperparameters and tuned hyperparameters can improve the query efficiency. \n\n**Cons**\n\n1. The paper fails to prove that the controller is able to generalize to unseen models. The models used in Table 1 are all adversarially trained model with similar loss landscapes. And the controller is trained on an adversarially trained model (Resnet18), which is similar to the models used for evaluation. I think the author should show that the controller is able to generalize to different settings such as attack for undefended models and targeted attack. \n2. The author uses the information of the source model. Although the information is quite limited, the method should be compared with the methods combined transfer-based attack and score-based attack such as [1][2].\n3. The author uses two inputs for the MLP. I think there should be an ablation study to show the how each input affect the finall success rate and query efficiency.\n4. While the controller is promising direction for black-box attack, the authors only show its effectiveness on Square Attack. I would be better to show the controller is able to control other hyperparameters in different black-box attacks.\n\n\n**Minors**\n\nThe notation $\\mathcal{D}_\\omega$ should be changed. It is easy to be mixed up with the notation $D$.\n\n[1] Zhichao Huang, Tong Zhang. Black-box adversarial attack with transferable model-based embedding, ICLR 2020\n\n[2] Yusuke Tashiro, Yang Song, Stefano Ermon. Diversity Can Be Transferred: Output Diversification for White- and Black-box Attacks, NeurIPS 2020", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See above.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "S_8e6GyEsI_", "reviewer": "Reviewer_bYZY", "summary": "The paper proposes a novel technique to improve query efficiency of black-box random search based adversarial attacks. The proposed method utilizes a controller which manages scheduling and proposal distribution for random search. The controller is trained by gradient-based meta-learning on surrogate models. Empirical results show that the Square Attack with the proposed method improves query efficiency compared to the original setting on CIFAR10 without manual fine-tuning.", "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": "Pros:\n- The paper is well motivated.\n- The characteristics of learned controller are useful and interesting.\n\nCons:\n- The advantage over existing hyperparameter search methods is not clear.\n- The proposed method needs the task specific controller design.\n- Additional data and training are a strong assumption but not well explained.\n- Experiments are not held in various settings.\n\nWhile the motivation is clear and some of the results are interesting, it seems to need more explanations and experiments for the following points:\n\n- The proposed method in this paper is similar to hyperparameter search (optimization) methods by Bayesian optimization or meta-learning, but the relationship with these methods is not explained. When random search based attacks only include simple hyperparameters like step size, these methods can also be used. In this case, does the proposed method have advantages over existing methods?  \nIn addition, existing hyperparameter search methods would be applicable to the Square Attack under assumptions of simple distributions (for example, linear or quadratic size schedule). There is no empirical comparison with hyperparameter search methods, and it is not clear that the proposed method is better than the existing methods.\n\n- The method needs the controller design which is specific to the task. The controller in Section 3.3 seems carefully designed and not simple. While the proposed method can be used without manual fine-tuning, the complex hand-designed architecture makes the advantage diminishing.\n\n- The requirement of source models (i.e., surrogate models) and additional training is a strong assumption, and the assumption should be more explained. Although the authors explain this point by “on model with white-box access” in the abstract and introduction, the relationship between the white-box model and black-box model is not clear. In addition, while there are many existing methods which exploit surrogate models to improve the query efficiency, the paper does not mention the existing methods.\n\n- In the experiment, the paper uses an adversarially trained ResNet model as source model, and all the target models are also adversarially trained ResNet-based models. This setting is not enough to show the strength of the proposed method. As the authors mentioned in line 66, the similarity between source and target models often affects the attack performance when the attack exploits source (surrogate) models. When the source model is trained with different architectures/training settings (e.g., DenseNet and naturally trained model), does the proposed method still outperform the baseline?\n\n- In addition to the above similarity between the source model and target models, the experiments are held in only 1 dataset and 1 attack. Moreover, the improvement is not significant and there are still non-negligible margins between the result and robust accuracy. Therefore, it seems to need more experiments to show the advantage of the proposed method.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have described limitations about the usage of surrogate models. \n\nThe authors have addressed societal impacts in Section 5.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4.5 hours"}, "extra_text": {}}, {"review_id": "ND8LPTgjIm", "reviewer": "Reviewer_mzdq", "summary": "This paper proposes meta-learning a black box adversarial attack strategy. Specifically, the authors propose meta-learning controllers that output the parameters of a square attack. Experiments on CIFAR-10 and ImageNet demonstrate the effectiveness of a meta-learned square attack relative to a non meta-learned baseline square attack.", "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": "**Originality**\nAs the authors point out, prior works have considered meta-learning attacks on neural networks. The authors propose meta-learning parameters of an existing black box attack. Nevertheless, the specific approach used by the authors appears novel.\n\n**Quality**\nThe effectiveness of the proposed meta-learned square attack is evaluated experimentally on CIFAR-10 and ImageNet. However, there are some issues with the experiments:\n\nFirst, the proposed method is framed as a meta-learned attack. However, the authors meta-train on a single dataset (CIFAR-10). Meta-learning typically refers to scenarios where meta-training occurs on a *set* of datasets and meta-testing occurs on a *different* set of datasets. The method proposed by the authors might be better framed as hyperparameter optimization or transfer learning rather than meta-learning. Alternatively, the authors might consider meta-training over a set of datasets and meta-testing on a different set of datasets.\n\nSecond, the improvements over baselines appear relatively incremental. In Table 1, it appears that meta-learning reduces the number of queries to achieve a certain accuracy by a factor of 2 or less. If the authors could reduce the number of queries by an order of magnitude of more, this would significantly improve the empirical experiments.\n\nRelatedly, how does the proposed attack compared to other black box attacks (other than the square attack)? In particular, is the proposed method the state-of-the-art black box attack on CIFAR-10 or ImageNet (compared to previously proposed black box attacks)?\n\n**Clarity**\nThe paper is well-written, with concepts introduced at appropriate points. Figures and tables are clear and appropriately sized. Experiments are adequately described.\n\n**Significance**\nOverall, the conceptual and empirical contributions in this paper appear relatively limited. Improvements over previous baselines seem to be small. If the authors can demonstrate that their results are a state-of-the-art black box attack, this would likely have practical value for neural network attackers and defenders. In general, the significance of this work depends strongly on the empirical improvement over prior works.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors describe the limitations and social impact of this work in section 5. However, the authors do not adequately potential strategies that could be used to limit the negative social impact of adversarial attacks. This is particularly important if proposed method is a state-of-the-art black box adversarial attack. The authors may want to mention a few specific mitigation strategies to limit the negative impacts of their proposed attack.", "review_text": "", "extra_scores": {"needs_ethics_review": "Yes", "ethics_review_area": ["Inappropriate Potential Applications & Impact  (e.g., human rights concerns)"], "time_spent_reviewing": "2"}, "extra_text": {"ethical_concerns": "The authors may not have adequately described mitigation strategies for their proposed black-box adversarial attack (which may be a state-of-the-art attack). The proposed method could have several negative social impacts- for example attackers could use them to fool self-driving car systems and cause accidents. Because the proposed method is a black-box attack, the attackers do not even need internal access to the classifier."}}, {"review_id": "EBs2Jdygl3U", "reviewer": "Reviewer_KmCh", "summary": "The authors propose a meta-learning framework to improve the query efficiency for Square Attack.\n", "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": "This paper focus on improving the query efficiency of a score-based black-box attack named Square Attack.\nSpecifically, the authors make some hyper-parameters of Square Attack (i.e., square size and the color channel) to be adaptive.\nThe authors use current step size, the history of loss values and the success frequencies of different color channels as inputs, and design MLPs to map from these inputs to better values of square size and color channel.\nThe MLPs are then trained using a meta-learning formulation, to make the learned strategies (parameterized by MLPs) to have better generalization performance on unseen images and models.\n\nStrengths:\n* The proposed method seems to be technically sound and novel. The square size and color channel schedules in Square Attack are crucial for query efficiency, but these parameters require significant manual design. The authors propose to directly learn these parameters via meta-learning, such that the learned schedules can work well on unseen images and models.\n* The controllers are trained on a white-box ResNet-18 model, and are evaluated on black-box RobustBench models. As such, an attacker does not need to know the detailed architecture of the target model, making the proposed method more practical.\n\nWeakness:\n* The authors claim in the abstract that the controller \"can be plugged into random search methods\", however, the proposed method seems to be deeply coupled with one particular attack (i.e., Square Attack). Can the proposed method be easily integrated with other attacks?\n* In line 38-39, the authors said \"...propose a method to ...reduce the amount of manual design in random search based attacks.\". However, the proposed two controllers themselves also require significant manual design (in Section 3.3).\n* In Table 1, although the proposed method has better query efficiency than competitive methods, the differences are not great in my opinion, given the fact that competitive methods use manually designed schedules while the proposed method use learned schedules. I wonder whether the advantage of the proposed method is more clear in extremely low query budget regime (e.g., < 150 queries), since in the early stage, the accuracies have not been saturated, thus a good search distribution could possibly make more contribution to the query efficiency.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "25"}, "extra_text": {}}]

Author rebuttal:

Meta-review: First, we would like to commend the authors on an interesting submission and a heroic effort in the response period, including several experimental findings to help address reviewer concerns. It is extremely difficult to make a decision for this paper --- it is on the borderline. The scores are all borderline, tending on average towards reject, without a clear champion. However, the authors do make a reasonably good case that they are proposing a query efficient black box attack. In the rebuttal they also attempt to address ethical concerns. On the other hand, there are remaining concerns about the technical contribution, particularly how specific the approach is to the square attack. The questions are mostly around how applicable the ideas are to other attacks, and how much effort would be required to design controllers for other attacks. In any case, the effort the reviewers have made in responding to reviewers should be highly useful in subsequent revisions. 
Decision: Accept (Poster)