Meta-Learning the Search Distribution of Black-Box Random Search Based Adversarial Attacks
Year: 2021

Abstract:
Adversarial attacks based on randomized search schemes have obtained state-of-theart 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 blackbox 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 setting1.

heading: 1 Introduction
text: It was demonstrated that despite their impressive performance in various tasks, neural networks are susceptible to small imperceptible perturbations in the input called adversarial examples [4]. This is a concerning issue for real-world deployment of deep learning approaches, especially in safety-critical domains such as autonomous driving [5]. But apart from practical concerns, adversarial examples serve as a 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 a constrained optimization problem [4]. However, finding the exact solution is typically intractable [7, 8]. Therefore, in practice one often resorts to approximate methods called adversarial attacks that try to find adversarial examples within a small number of iterations. A number of 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 it significantly harder to find them gradient-based, can be a severe obstacle for certain attacks [11].
1The code is available at https://github.com/boschresearch/meta-rs
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
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 [12–21] and are thus recommended for reliable robustness evaluation [2, 22].
A very promising direction in the field of black-box adversarial attacks are randomized search schemes for crafting adversarial examples [1, 23, 24]. Combining random search with specific update proposal distributions allows to achieve state-of-the-art black-box efficiency for different threat models such as `∞ and `2 [1], `1 [25], `0, 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 1).
In this work, we propose a method that allows to 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 `∞ and `2 threat models [1]. 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 in 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. [1] and Croce and Hein [2].
In short, we make the following contributions:
• We frame adversarial attack optimization as a meta-learning problem (Section 3.2). • We formalize the gradient-based meta-learning for the state-of-the-art Square Attack and
propose Meta Square Attack (Section 3.3). • We meta-train Meta Square Attack (MSA) on a CIFAR10 [48] model with white-box
access and show that MSA improves robust accuracy by up to 5.6% on a vast range of CIFAR10 models with black-box access with respect to the hand-designed search distributions proposed in previous work [1, 2] for the `∞ and `2 threat models (Section 4). • We show that Meta Square Attack generalizes well to different datasets and to the targeted attack setting. It achieves up to 20% better robust accuracy compared to the state-of-the art baseline [1] for attacking models on CIFAR100 and ImageNet (Section 4.2).

heading: 2 Related Work
text: 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 [17, 29] 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 is that similarity between the models is a crucial factor. Without it the efficiency of transfer attacks is drastically reduced [29]. Decisionbased 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 [1, 12–19] 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 a gradient and apply gradient descent. Alzantot et al. [19] propose a derivative-free approach based on genetic algorithms. Several works use the empirical observation that successful `∞ perturbations are located at the corners of the color cube, therefore instead of continuous optimization one can reduce the problem to a discrete one [1, 12, 24, 33].
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 blackbox [39] settings. Meta-learning [40, 41] was also used to improve zeroth-order gradient estimation and allow better query efficiency of black-box attacks [42]. Besides that there is the recent work [43] on automating the existing AutoAttack [2] framework for robustness evaluation. Meta-learning has also been used as part of adversarial training [38, 44] for increasing adversarial robustness.
Square Attack: Square Attack (SA) was proposed by Andriushchenko et al. [1] 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 `∞- and `2-attacks and was later extended also to `1 [25]. As the adversarial attack problem is highly non-convex, a 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 [18]. For the `∞-case, 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 nontrivial manual design): Andriushchenko et al. [1] proposed a schedule parametrized by p0 ∈ [0, 1] (the fraction of image pixels to be modified by a square in the first query) and the total query budget T , where pt is halved at {0.1, 0.5, 2, 10, 20, 40, 60, 80}% of the total query budget. For evaluation on CIFAR10, Andriushchenko et al. [1] suggest different values of p0 and report p0 = 0.3 as a default choice. Croce and Hein [2] proposed a different schedule for SA to be used in AutoAttack: they use p0 = 0.8 and T = 5000 but fix the halving points of pt as if T = 10000. An illustration of the two schedules for T = 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 a 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 2c different colors (with c being number of channels, typically c = 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 4.2) with very little manual design and identify non-trivial patterns that increase attack efficiency (see Section 4.3).

heading: 3 Method
text: 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 a specific random search based black-box adversarial attack, namely Square Attack [1]. We denote this method as Meta Square Attack (MSA).

heading: 3.1 Adversarial Robustness Evaluation
text: Let K be the number of classes in a classification problem and f : [0, 1]d → ∆K−1 be a classifier which maps a d-dimensional input x to
∆K−1 = { (p0, ..., pK−1) ∈ RK ∣∣∣K−1∑ i=0 pi = 1, and pi ≥ 0 for i = 0, ...,K − 1 } ,
which denotes the set of probability distributions over the K discrete possible outcomes. For a label y ∈ {0, ...,K − 1}, a loss function l : ∆K−1 × {0, ...,K − 1} → R, a perturbation set S, and operator a, we define the robustness evaluation problem as:
V (f, x, y) = max ξ∈S
l ( f(a(x, ξ)), y ) (1)
For S = {ξ | ||ξ||p ≤ } and a(x, ξ) = Π[0,1]d(x+ ξ) (where Π[0,1]d is the projection onto [0, 1]d), one obtains the standard `p ball threat model for images. Assuming that the loss function l and operator a are fixed, we denote L(f, x, y, ξ) := l(f(a(x, ξ)), y) as a functional that one needs to maximize in robustness evaluation.
Since exact maximization of Equation (1) is intractable in the general case [7], we consider a (potentially non-deterministic) procedure Aω(L, f, x, y) called adversarial attack. This attack Aω is parametrized by hyperparameters ω and designed with the intention that ξω ∼ Aω(L, f, x, y) with ξω ∈ S becomes an approximate solution (tight lower bound) of V (f, x, y), that is V (f, x, y) − L(f, x, y, ξω) should become small (in expectation). Optimizing the hyperparameters of the attack via max ω E ξω∼Aω(L,f,x,y) L(f, x, y, ξω) can allow a tighter lower bound of V (f, x, y). Unfortunately, this maximization is still intractable typically, for instance when f is a black-box (no gradient information is available), the number of queries to f per data (x, y) is limited, or Aω has high variance.

heading: 3.2 Black-box Adversarial Attack Optimization as a Meta-learning Problem
text: We now frame optimization of the adversarial attack in the query-restricted black-box setting as a 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 of the goal of meta-learning): we assume data to be governed by a distribution (x, y) ∼ D and classifiers defined on this data, which need to be evaluated, by a distribution f ∼ F . Our meta-objective is to find parameters ω∗ of the attack Aω that maximize the lower bound L(f, x, y, ξω) of V (f, x, y) in expectation across models f ∼ F , data (x, y) ∼ D, and the stochastic attack ξω ∼ Aω:
ω∗ = argmax ω E f∼F E (x,y)∼D E ξω∼Aω(L,f,x,y) L(f, x, y, ξω) (2)
Here, the expensive optimization of ω∗ is amortized across models and data. More specifically, we assume finite sets of data D = {(xi, yi)Ni=1 | (xi, yi) ∼ D} and classifiers F = {fj | fj ∼ F}
are available. Moreover, we assume the fj ∈ F allow white-box access and quasi-unrestricted number of queries. The sets D and F can be used during meta-training of the attack, that is the objective during meta-training becomes ω∗ = arg maxω R(F,D, ω) with R(F,D, ω) =∑ f∈F ∑ (x,y)∈D L(f, x, y, ξ
ω) and ξω ∼ Aω(L, f, x, y). However, the ultimate goal of metalearning is to apply Aω∗ during meta-testing to unseen (x, y) ∼ D and unseen f ∼ F that allow only black-box and query-limited access, and maximize Eξω∼Aω(L,f,x,y) L(f, x, y, ξω), that is: the attack needs to generalize across models and data.
Next, we define the meta-representation, that is how the adversarial attack Aω is designed and parametrized such that generalization 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 Aω be a random search based attack with a query budget limited by T . Then an adversarial perturbation ξω = ξT ∼ Aω(L, f, x, y) is obtained using the following iterative procedure:
ξ0 ∼ D0; ξt+1 = argmax ξ∈{ξt,ΠS(ξt+δt+1)} L(f, x, y, ξ); δt+1 ∼ Dω(t, ξ0, δ0, . . . , ξt, δt), (3)
where ΠS corresponds to the projection onto the perturbation set S. That is, we assume a fixed distribution D0 for initializing the perturbation ξ0 but a meta-learnable Dω for the update proposals δt+1. Importantly, Dω depends on the entire attack trajectory up to step t. Since this trajectory contains implicitly information on the classifier f when applied to data (x, y), 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 [1] in Section 3.3. The meta-optimizer (how we optimize the meta-objective) in our case assumes that both the loss function l and Aω are (stochastic) differentiable with respect to ω or we can find differentiable relaxations (as we will discuss in Section 3.3). Thus the meta-parameters ω can be optimized using stochastic gradient descent on mini-batches B ⊆ D based on the (stochastic) gradient
g = ∇ωR(F,D, ω) = ∑ fj∈F ∑ (xi,yi)∈B⊆D ∇ωL(fj , xi, yi, ξi,j), (4)
where ξi,j ∼ Aω(L, fj , xi, yi). However, due to the stochasticity of Aω induced by D0 and Dω , 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:
g = 1
T ∑ fi ∑ (xj ,yj) T−1∑ t=1 ∇ωL(fi, xj , yj ,ΠS(ξt + δt+1)). (5)
Importantly, even though ξt depends on ω for t > 0, we do not propagate gradients with respect to ω through ξt, that is we set ∇ωξt := 0. By this, the gradient corresponds to optimizing Dω in a myopic way, such that proposals δt+1 ∼ Dω(t, ξ0, δ0, . . . , ξt, δt) are trained to maximally increase the immediate loss in step t+ 1. While this introduces a bias of acting myopic and greedy, it works reasonably well in practice.
We can now rewrite ∇ωL(fi, xj , yj , ξt + δt+1) = ∇δt+1L(fi, xj , yj , ξt + δt+1)∇ωδt+1. We note that ∇ωδt+1 can be a very high variance estimate of ∇ωDω(t, ξ0, δ0, . . . , ξt, δt) depending on the stochasticity of Dω. However, as it is an unbiased estimate and we average over very many steps T and models and data, g is still a sufficiently good estimate in practice.

heading: 3.3 Meta Square Attack
text: In this section, we demonstrate how the proposed meta-learning approach can be applied to Square Attack (SA) [1] with `∞ threat model. We denote the resulting meta-learned attack as Meta Square Attack (MSA). We keep D0 as the stripe initialization from SA and focus on meta-learning Dω as it governs all but the first step. As discussed in Section 2, sampling δt+1 ∼ D(t) in SA proceeds by computing a square size (its width in pixels) st = πs(t) ∈ {1, . . . , smax} and sampling a
position (px, py) ∼ πp(s) ∈ {1, . . . , smax − s}2 and a color c ∼ πc ∈ {c1, . . . cm}. In SA, πs is a heuristic schedule that depends on t (and differs in prior work [1, 2]) and both πp and πc are uniform distributions. δt+1 is then chosen to be zero everywhere except for a square of size s at position p with color c. Possible colors ci correspond to the eight corners of the RGB hypercube with `∞ norm . That is ci ∈ (± ,± ,± ), while smax is chosen maximally with the constraint that all sampled squares must not exceed the image dimensions. We keep πp as uniform distribution, but meta-learn the controllers πsωs and π c ωc with parameters ω = (ωs, ωc).
Update size controller πsωs . We design π s ωs as a multi-layer perceptron (MLP) with parameters ωs. The MLP outputs a scalar value s′ ∈ R and we map this value to the actual update size via s = σ(s′) · (smax− 1) + 1 with σ(x) = 1/(1 + e−x). During meta-testing, we round the continuous s ∈ [1, smax] to a discrete value bse ∈ {1, . . . , smax}. 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 to the MLP πsωs : (a) the current query t encoded as log2( t T +1) where T is the maximal number of queries. It ensures that the input stays in the range [0, 1] for t ≤ T . We use T = 5000. (b) Let rt+1 = H ( L(f, x, y,ΠS(ξ t + δt+1))− L(f, x, y, ξt) ) ∈ {0, 1} be an indicator of whether adding δt+1 at time t+1 improved the loss (forH being the Heaviside step-function). The MLP gets as second input at time t the value Rt = γRt−1 + (1− γ)rt/r0 with R0 = 1. Here γ is a decay term that controls how quickly past experience is “forgotten” and r0 = 0.25 is a constant whose purpose is to ensure that the MLP’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 Rt 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 (x, y) at hand.
Color controller πcωc . We design the color controller π c ωc as a categorical distribution c t ∼ Cat(αt1, . . . , α t m), where each α t i ∈ R is predicted by an MLP with weights ωc. The m MLPs for the αti share weights ωc but differ in their inputs. In order to differentiate through the categorical distribution at meta-train time, we reparametrize the categorical distribution with Gumbel-softmax 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 ci is sampled at least with probability pcmin by assigning P (ci) = pcmin + (1−mpcmin)PCat(αt1,...,αtm)(ci). This ensures continuous exploration of all m colors.
The m MLPs get two inputs: (a) the current query t encoded as log2( t T + 1) (same encoding as for the step size controller and also same for all m MLPs). (b) Information regarding the recent success frequency of proposals δt based on squares of the respective colors (ct = ci):
Rti = { γRt−1i + (1− γ)rt/r0 if ct = ci Rt−1i otherwise . This second input allows the controller to learn, e.g., to sample those colors more often that resulted in higher success frequency recently.

heading: 4 Experiments
text: We perform an empirical evaluation of Meta Square Attack (MSA). First, we consider the data distribution D of CIFAR10 [48] images and a classifier distribution F consisting of the classifiers robust with respect to the `∞-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 CIFAR100 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 `2-threat model in the Section A.5.
We compare the performance of MSA in 4 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 1). Hence, it uses the knowledge of the attack budget and the schedule used for 500 queries is not a truncated version of the schedule used for
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 to 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.

heading: 4.1 Meta-Training and Controller Design
text: We meta-train the controller on a single robust model 2 f ∼ F 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 CIFAR10 training set using adversarial training [26] with the advertorch [49] package. Adversarial training was 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. Metatraining was run on a set D consisting of 1000 images from CIFAR10 test set (different from the ones used in evaluation of 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 simultaneously for 10 epochs using Adam optimizer with batch size 100 and cosine step size schedule [50] with learning rate 0.03. The total loss improvement over the attack was used as meta-loss that we optimized in meta-training. We always run 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.

heading: 4.2 Evaluation
text: In this section, we evaluate how the Meta Square Attack (MSA) obtained by training on a CIFAR10 model with white-box access discussed in the Section 4.1 performs for different models and datasets.
Table 1 illustrates that MSA transfers well to two selected robust CIFAR10 models. Moreover, Table 2 reports results aggregated over a broad range of 16 robust CIFAR10 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 MSAs and MSAc is not specific to the data distribution. Therefore, we also show that the adaptation principles learned on a CIFAR10 model transfer well to attacking models that not only have different architecture but also operate on significantly different
2Meta-training on more than one source model could improve generalization across models, but we found that even meta-training on a single model generalizes sufficiently well.
data distributions: Table 3 demonstrates generalization of the learned controllers for attacking robust models for CIFAR100 [48]. We also consider the transfer to ImageNet [57] dataset that has significantly higher input dimension and number of classes than CIFAR10. In Table 4, one can see that MSA significantly improves the results even in the high extrapolation regime of 5000 queries. We also observe considerable improvement of the robust accuracy estimate for the targeted attacks on undefended ImageNet models (Table 5). Results for applying the size controller trained specifically for the `2 threat model (together with the color controller trained for l∞) are in Table 6. 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 in the given setting and how suitable the hand-designed search distributions of the baselines [1, 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.

heading: 4.3 Analysis of Learned Controllers
text: As the learned controllers are black-boxes (implemented by MLPs), it may be non-trivial to understand their realized strategy. We present some analysis of the controllers’ internal strategy based on their empirical behavior. Further analysis can be found in the Section A.4.
Figure 2a illustrates the behaviour of the update size controller MSAs. It shows how the controller chooses the update size over time in an artificial scenario where the success probability P (rt = 1) is 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 (rt = 1), with slower decay for larger P (rt = 1). This property is not implemented by heuristic schedules, but makes sense intuitively: high P (rt = 1) corresponds to a situation where the current perturbation ξt can be improved relatively easily by coarse-grained changes implemented by the current update sizes; in this case it makes sense to first get the 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 MSAc 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 a clear preference for sampling black and white more often than uniform (p ≈ 0.18 vs. p = 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 on the success rates Rt 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 7 demonstrates the ablation studies with respect to the used controllers on the model by Gowal et al. [62]. We observe that MSAs combined with the uniform color distribution alone significantly improves the results of SA and AA in most of the query budgets (with the exception of the strong extrapolation regime of 5000 queries). The controller MSAc combined with all schedules improves the performance with the exception of 500 queries regime for SA and MSAs where it provides an equal or a slightly worse result in some cases.

heading: 5 Conclusion
text: In this work we propose a theoretical framework for meta-learning 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 `∞ and `2 perturbations. Our experimental results show that learned adaptive controllers improve attack performance across different query budgets and generalize to 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 or robotics. Meta Square Attack allows more efficient generation of imperceptible image distortions that may allow bypassing automated content-control systems for filtering images with violent, pornographic, or otherwise offensive content. We are 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 a check to a system which rejects predictions for a sequence of inputs which all differ by at most an `p distance of some . This would make most score-based black-box attacks for image-specific perturbations ineffective, including Meta Square Attack.

heading: Acknowledgements
text: Matthias Hein is a member of the Machine Learning Cluster of Excellence, EXC number 2064/1 – Project number 390727645 and of the BMBF Tübingen AI Center, FKZ: 01IS18039B.

Review summaries:
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.

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.

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.