Automated Discovery of Adaptive Attacks on Adversarial Defenses
Authors: Chengyuan Yao
Pavol Bielik
PETAR TSANKOV
Martin Vechev
Venue: NeurIPS 2021 Poster (2021)
Keywords: Deep Learning
Adversarial Attacks
Adversarial Defences
Robustness

Abstract: Reliable evaluation of adversarial defenses is a challenging task, currently limited to an expert who manually crafts attacks that exploit the defense’s inner workings, or to approaches based on ensemble of fixed attacks, none of which may be effective for the specific defense at hand. Our key observation is that adaptive attacks are composed from a set of reusable building blocks that can be formalized in a search space and used to automatically discover attacks for unknown defenses. We evaluated our approach on 24 adversarial defenses and show that it outperforms AutoAttack, the current state-of-the-art tool for reliable evaluation of adversarial defenses: our tool discovered significantly stronger attacks by producing 3.0%-50.8% additional adversarial examples for 10 models, while obtaining attacks with slightly stronger or similar strength for the remaining models.

Automated Discovery of Adaptive Attacks on Adversarial Defenses
Chengyuan Yao Department of Computer Science ETH Zürich, Switzerland
Pavol Bielik
Petar Tsankov LatticeFlow Switzerland
LatticeFlow Switzerland pavol@latticefllv.
mewoiin.ethh..c.om .et.z.t.cc.. ch
petar@latticeflov...
Martin Vechev
Department of Computer Science ETH Zürich, Switzerland martin. vechev@inf ethz, ch
Abstract
Reliable evaluation of adversarial defenses is challenging task, currently limited to an expert who manually crafts attacks that exploit the defenses inner workings approaches based effective for the specific defense at hand. Our key observation is that adaptive attacks composed of reusable building blocks that be formalized in a search space and used to automatically discover attacks for unknown defenses. We evaluated approach on 24 adversarial defenses and show that it outperforms AutoAttack (Croce & Hein (2020b), the current sfate-of-the-an tool for reliable evaluation of adversarial defenses: our tool discovered significantly stronger attacks by producing 3.0%-50.89 additional adversarial examples for 10 models, while obtaining attacks with slightly stronger or similar strength for the remaining models.
ensemble of fixed attacks, none of which may be
Introduction
The issue of adversarial attacks (Szegedy al. 2014 Goodfellow et al. (015). i.e., crafting small in- put perturbations that lead to mispredictions, is an important problem with large body of recent work. Unfortunately, reliable evaluation of proposed defenses is elusive and challenging task: many de- fenses seem to initially be effective, only to be cireumvented later by new attacks designed specifically with that defense in mind (Carlini & Wagner 2017 Athalye et al. 2018 Tramer et al.) 2020).
To address this challenge, two recent works approach the problem from different perspectives. Tramer et al. (220) outlines an approach for manually crafting adaptive attacks that exploit the weak points of each defense. Here, domain expert starts with an existing attack, such as PGD (Madry al.) 2018) (denoted as in Figure D and adapts it based on knowledge of the defense's 's inner workings. Common modifications include: (i) tuning attack parameters (e.g., number of steps), (ii) replacing non-differentiable
network components to simplify the attack (e.g., removing randomization components), and (iii) replacing the loss function optimized by the attack. This approach was demonstrated to be effective in breaking all of the considered 13 defenses. However, downside is that it requires substantial manual effort and is limited by the domain knowledge the expert - for instance, each of the 13 defenses came with an adaptive attack which was insufficient, in retrospect.
At the same time, Croce & Hein (022b) proposed to assess adversarial robustness using an ensemble of four attacks illustrated in Figure (b) APGDcE with cross-entrops loss (Croce & Hein, 2020b), APGDpLa with difference logit ratio loss, FAB (Croce & Hein 2020a). and SQR (Andriushchenko et al. 2020 While these do not require manual effort and have been shown to improve the robustness
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

(a) Handcrafted adaptive attacks
(b) Ensemble of fixed attacks
(c) Adaptive attack search (Our Work)
Tramer el al. (2020)
Croce& & Hein 2020b)
ensemble diversity
modiiiie loss
P
K-RTA
kTA
SQR
optiiice
+BPDA
eweighhed loss
APGD
FAB
APGD
FAB
DeepFook Fool
params
APCDes
CKN
EMPIR
EMPIR
B&B
b> best adaptive attack manual step
fixed attack
U search space- * search step
Figure 1: High-level illustration and comparison of recent works and ours. Adaptive attacks (a) rely on a human expert to manually adapt an existing attack to exploit the weak points of each defense. AutoAttack (b) evaluates defenses using ensemble of diverse attacks. Our work (c) defines search space of adaptive attacks (denoted as [) and performs search steps automatically.
estimate for many defenses, the approach is inherently limited by the fact that the attacks are fixed apriori without any knowledge of the given defense at hand. This is visualized in Figure (b) where even though the attacks are designed to be diverse, they cover only small part of the entire space.
This work: towards automated discovery of adaptive attacks We present a new method that helps automating the process of crafting adaptive attacks, combining the best of both prior approaches; the ability to evaluate defenses automatically while producing attacks tuned for the given defense. Our work is based on the key observation that we can identify common techniques used build existing adaptive attacks and extract them as reusable building blocks in a common framework. Then, given a new model with an unseen defense, we can discover an effective attack by searching over suitable combinations of these building blocks. To identify reusable techniques, we analyze existing adaptive attacks and organize their components into three groups:
Attack algorithm and parameters: a library of diverse attack techniques (e.g.. APGD, FAB, C&W (Car lini & Wagner 2017), NES (Wierstra et al. 2008)), together with backbone specific and generic parameters (e.g., input randomization, number of steps, if/how to use EOT (Athalye al. 2018))
Network transformations: producing an easier attack surrogate model using techniques including variants of BPDA (Athalye et al. 2018) to break gradient obfuscation, and layer removal (Tramer et al. 2020) to eliminate obfuscation layers such as redundant softmax operator.
Loss functions: that specify different ways of defining the attack's loss function.
These components collectively formalize an attack search space induced by their different combina- tions. We also present an algorithm that effectively navigates the search space so to discover an attack. In this way, domain experts are left with the creative task of designing new attacks and growing the framework by adding missing attack components, while the tool is responsible for automating many of the tedious and tine-consuming trial-and-error steps that domain experts perform manually today. That is, we can automate some part of the process of finding adaptive attacks, but not necessarily the full process. This is natural as finding truly new attacks is a highly creative process that is currently out of reach for fully automated techniques.
We implemented our approach in tool called Adaptive AutoAttack (A") and evaluated on 24 diverse adversarial defenses. Our results demonstrate that A discovers adaptive attacks that outper- form AutoAttack (Croce & Hein 2020b), the current sfte-of-the-an tool for reliable evaluation of adversarial defenses: A finds attacks that are significantly stronger, producing 3.0%-50.8% additional adversarial examples for models, while obtaining attacks with stronger or simialr strength for the remaining models. Our tool A and scripts for reproducing the experiments are available online at:
https://github.. cww/etoccccteeeeee becch-ssrraddaage ari/adaptive httpa/dpppiieattoooooaeeeeeaaaae auto-att attock
2 Automated Discovery of Adaptive Attacks
We use = [(x,, 2 to denote a training dataset where x E X is natural input (e.g., an image) and y is the corresponding label. An adversarial example is perturbed input x', such that: (i) it

---

satisfies an attack criterion c, c.g., K-class classification model f: X - R predicts a wrong label, and (ii) the distance d(z', ,)) between the adversarial input x' and the natural input æ is below a threshold under distance metric d (e.g., an Ip norm). Formally, this can be written as:
capability
goal (criterion)
ADVERSARIAL ATTACK
d(x', x)) Se such that cf.
For example, instantiating this with the Lo norm and misclassification criterion corresponds to:
MISCLASSIFICATION
To ATTACK
|| Se s.t. f(x') + f(x)
where f returns the prediction arg =ax fa( of the model f.
Problem Statement Given a model f equipped with an unknown set of defenses and dataset D = (1T w:) our goal find an adaptive adversarial attack a E A that is best at generating adversarial samples x' according to the attack criterion and the attack capability d(x', x) S E:
max a,A,, d(z' Sc (aa))D c(J,x',))
where x'= a(x,
(1)
Here, denotes the search space of all possible attacks, where the goal of each attack a: (X + RK) + X is to generate an adversarial sample x' = a(x, f) for a given input x and model f. For example, solving this optimization problem with respect to the L misclassification criterion corresponds to optimizing the number of adversarial examples misclassified by the model.
In our work, consider an httpmmmennnttioonoonweeeee adversary, who has full access to the model's implementation at inference time (e.g., the model's 's computational graph). We chose this threat model it matches our problem setting given unseen model implementation, find an adaptive attack that exploits its weak points but without the need of domain expert. We note that this threat model weaker than a perfect-knowledse adversary (Biggio et al. 2013). which assumes a domain expert that also has knowledge about the training dataset and algorithm, as this information difficult, or even not possible, recover from the model's implementation only.
want automatically
Key Challenges
To solve the optimization problem from Eq. 1 address two key challenges:
Defining suitable attacks search space A such that it is expressible enough cover a range of existing adaptive attacks.
Searching over the space A efficiently such that strong attack is found within reasonable time.
Next, we formalize the attack space in Section 3 and then describe our search algorithm in Section 4
3 Adaptive Attacks Search Space
We define the adaptive attack search space by analyzing existing adaptive attacks and identifying common techniques used to break adversarial defenses. Formally, the adaptive attack search space is given by A: $ T, where S consists of sequences of backbone attacks along with their loss functions, selected from space of loss functions L, and T consists of network transformations. Semantically, given an input a and a model f, the goal of adaptive attack (s,1) E S x T is to return an adversarial example x' by computing s(x, ((S)) = x'. That is, it first transforms the model f by applying the transformation t(f) = f", and then exccutes the attack s on the surrogate model f Note that the surrogate model is used only to compute the candidate adversarial example, not to evaluate it. That is, we generate an adversarial example x' for f', and then check whether it is also adversarial for f. Since x' may be adversarial for f', but not for f, the adaptive attack must maximize the transferability of the generated candidate adversarial samples.
Attack Algorithm & Parameters (S) The attack search space consists of sequence of adversarial attacks. We formalize the search space with the grammar:
3

---

(Attack Search Space) S ::= S; S randomize S EDT S, n repeat S, n try for Attack with params with loss E L
S; S: composes two attacks, which are executed independently and return the first adversarial sample in the defined order. That is, given input the attack returns 81 (1)) if 81 (ar) is an adversarial example, and otherwise it returns 82(2))
randomize S: enables the attack's 's randomized components, which correspond to random seed and/or selecting starting point within d(x', x) S e, uniformly at random.
EOT S, n: uses expectation over transformation, technique designed to compute gradients for models with randomized components (Athalye et al. 2018).
repeat S, repeats the attack n times (useful only if randomization is enabled).
try S for n. executes the attack with a time budget of n seconds.
Attack with params with loss E L: is backbone attack Attack executed with param- eters params and loss function loss. In our evaluation, 2015), PGD, DeepFool (Moosavi-Dezfooll et al. 2016), C&W, NES, APGD, FAB and SQR. We provide full list of the attack parameters, including their ranges and priors in Appendix
FGSM (Goodfellow et al.)
Note, that we include variety of backbone attacks, including those that were already superseeded by stronger attacks. This is done for two key reasons. First, weaker attacks can be surprisingly effective in some cases and avoid the detector because of their weakness (see defense C24 our evaluation). Second, we are not using any prior when designing the space search. In particular, whenever new attack is designed it can simply be added to the search space. Then, the goal of the search algorithm is to be powerful enough to perform the search efficiently. In other words, the aim is to avoid making any assumptions of what is useful or not and lct the search algorithm learn this instead.
common approach that aims to improve the robustness neural networks against adversarial attacks is to incorporate an explicit defense mechanism in the neural architecture. These defenses often obfuscate gradients to render verraive-optimmizaton methods ineffective (Athalye al. 2018). However, these defenses can be successfully circumvented by (i) choosing suitable attack algorithm, such as score and decision- based attacks (included in S), or (ii) by changing the neural architecture (defined next).
Network Transformations (T)
At a high level, the network transformation search space T takes input a model and transforms it to another model f", which is easier to attack. To achieve this, the network f can be expressed as a directed acyclic graph, including both the forward and backward computations, where each vertex denotes an operator (e.g., convolution, residual blocks, etc.), and edges correspond to data dependencies. In our work, we include two types of network transformations:
Layer Removal, which removes an operator from the graph. Each operator can be removed if its input and output dimensions are the same, regardless of its functionality.
Backward Pass Differentiable Approximation (BPDA) (Athalye et al. 2018), which replaces the backward version of operator with differentiable approximation of the function. In our search space we include three different function approximations: (i) an identity function, (ii) a convolution layer with kernel size and (iii two-layer convolutional layer with ReLU activation in between. The weights in the latter two cases are learned through approximating the forward function.
Loss Function (L) Selecting the right objective function to optimize is an important design decision
for creating strong adaptive attacks. Indeed, the recent work of Tramer al. (2020) uses 9 different objective functions to break 13 defenses, showing the importance of this step. We formalize the space of possible loss functions using the following grammar:
(Loss Function Search Space)
IL ::= targeted Loss, n with Z untargeted Loss with Z targeted Loss, n untargeted Loss with
Z ::= logits probs
Loss ::= CrossEntropy HingeLoss
L1 DLR LogitMatching

---

Targeted vs Untargeted. The loss can be either untargeted, where the goal is to change the classification to any other label fax') * f(x), or targeted. where the goal to predict a concrete label f(x') = L. Even though the untargeted loss is less restrictive, it is not always easier to optimize in practice, and replacing it with a targeted attack might perform better. When using targeted Loss, n, the attack will consider the top classes with the highest probability as the targets.
Loss Formulation. The concrete loss formulation includes loss functions used in existing adaptive attacks, as well as the recently proposed difference in logit ratio loss (Croce & Hein, 2020b). We
provide a formal definition of the loss functions used in our work in Appendix [
Logits vs. Probabilities. In our search space, loss functions can be instantiated both with logits as well as with probabilities. Note that some loss functions are specifically designed for one of the two options, such as C&W (Carlini & Wagner 2017) or DLR (Croce & Hein] (020b).. While such knowledge can be used to reduce the search space, it is not necessary long as the search algorithm is powerful enough to recognize that such a combination leads to poor results.
Loss Replacement. Because the key idea behind many of the defenses is finding property that helps differentiate between adversarial and natural images, one can also define the optimization objective in the same way. These feature-level attacks (Sabour et al. 2016) avoid the need to directly optimize the complex objective defined by the adversarial defense and have been effective at circumventing them. As example, the logit matching loss minimizes the difference of logits between adversarial sample x' and a natural sample of the target class I (selected at random from the dataset). Instead of logits, the same idea can also be applied to other statistics, such as internal representations computed by a pre-trained model or KI KI--diergence between label probabilities.
4 Search Algorithm
We now describe our search algorithm that optimizes the problem statement from Eq. Since we do not have access to the underlying distribution, we approximate Eq. | Jusing the dataset D as follows:
score(f, a, D) = boj Σ -Ale + maxu(er.ass a(I, f)
(2)
where a E A is an attack, la E R+ denotes untargeted cross-entropy loss of a on the input, and À E IR is hyperparameter. The intuition behind -X . la is that it acts as tie-breaker in case the criterion e alone is not enough to differentiate between multiple attacks. While this is unlikely to happen when evaluating on large datasets, it is quite common when using only small number of samples. Obtaining good estimates in such cases is especially important for achieving scalability since performing the search directly on the full dataset would be prohibitively slow.
Search Algorithm We present our search algorithm in Algorithm || We start by searching through the space of network transformations t T to find a suitable surrogate model (line 1). This is achieved by taking the default attack A (in our implementation, we set A to APGDaE), and then evaluating all locations where BPDA can be used, and subsequently evaluating all layers that can be removed. Even though this step is exhaustive, takes only fraction of the runtime in our experiments, and no further optimization was necessary.
Next, we search through the space of attacks S. As this search space is enormous, we employ three techniques to improve scalability and attack quality. First, to generate a sequence of m attacks, we perform greedy search (lines 3-16). That is, in each step, we find an attack with the best score on the samples not circumvented by any of the previous attacks (line 4). Second, we use a parameter estimator model M to select the suitable parameters (line 7). In our work, we use Tree of Parzen Estimators (Bergstra et al.) 2011). but the concrete implementation can vary. Once the parameters are selected, they are evaluated using the score function (line (line 9), and the estimator is updated (line 10). Third, because evaluating the adversarial attacks can be expensive, and the dataset D is typically large, we employ successive halving technique (Karnin et al.] 2013) Jamieson & Talwalkar 2016). Concretely, instead of evaluating all the trials on the full dataset, we start by evaluating them only on a subset of samples Daample (line 5). Then, we improve the score estimates by iteratively increasing the dataset size (line 13), re-evaluating the scores (line 1 14), and retaining a quarter of the trials with the best score (line 15). We repeat this process to find single best attack from H. which is then added to the sequence of attacks S (line 16).
8), the result is stored in the trial history H
5

---

Algorithm 1: A search algorithm that given a model f with unknown defense, discovers an adaptive attack from the attack search space with the best score.
def AdaptiveAttackSene
Input: dataset D, model f, attack search space = x T. number of trials k, initial dataset size n, attack sequence length m, criterion function initial parameter estimator model M, default attack A
Output: adaptive attack from ((x.t] E = x T achieving the highest score on D
t + arg ET (f, q[a.)]: D) > Find surrogate model t using default attack A b Initialize attack to no attack, which returns the input image Run m iterations to get sequence of attacks D - D fo x E DAA DAD. (2
2
S -+1
for j < 1:m do
> Remove non-robust samples b Initial dataset with a samples Select candidate adaptive attacks 0' + arg maxxes P(O M) Best unseen parameters according to the model M
5
H + 0; Dsampla + sample(DD,))
for 1:
q score(f. afo...).r)))) Deampee)
HU HOO {)}
10
M + update model M with (0',
11
+- keep //1/4 attacks with the best score
while [7| > and D Deamie * do
D. Successive halving (SHA) D Deangle: (De eeappell) &. Double the dataset size (0, H Re-evaluate on larger dataset
13
D Demagle f- Dsample - sample((D
H. (0, acore(ffajp.. (eanp),)
15
H. keep /H attacks with the best score
16
S + S; best attack H
17
return [1S,4]
Time Budget and Worst-case Search Time We set time budget the attacks, measured in seconds per sample per attack, to restrict resource-expensive attacks and allow the tradeoff between computation time and attack strength. If an attack exceeds the time limit in line 8, the evaluation terminates, and the score is set to be cc.. We analyzed the worst-case search time to be 4/3x the allowed attack runtime in our experiments, which means the search overhead both controllable and reasonable in practice. The derivation is shown in Appendix A
Evaluation
We evaluate A on 24 models with diverse defenses and compare the results to AutoAttack (Croce & Hein, (2200b) and to several existing handcrafted attacks. AutoAttack is a state-of-the-art tool designed for reliable evaluation of adversarial defenses that improved the originally reported results for many existing defenses by up to 10%. Our key result is that A finds stronger or similar attacks than AutoAttack for virtually all defenses:
In 10 cases, the attacks found by A are significantly stronger than AutoAttack, resulting in 3.0% to 50.8% additional adversarial examples.
In the other 14 cases, As attacks typically 2x faster while enjoying similar attack quality.
Model Selection We selected 24 models and divided them into three blocks A, B, as listed in Table I Block contains diverse defenses with 4/255. Block B contains selected top models from RobustBench (Croce al. 2020). Block C contains diverse defenses with e = 8/255.
The 3 tool The implementation of A is based on PyTorch (Paszke et al. 2019) the implementa- tions of FGSM, PGD, NES, and DeepFool are based on FoolBox (Rauber al. 2017) version 3.0.0, C&W is based on ART (Nicolae et al.) 2018) version 1.3.0, and the attacks APGD, FAB, and SQR are from (Croce Hein 2020b).
use AutoAttack's rand version if a defense has a randomization component, and otherwise we use its slandard version. To allow for a fair comparison, we extended AutoAttack with backward pass differential approximation (BPDA), so we can run on defenses with non-differentiable components; without this, all gradient-based attacks would fail. We instantiate

---

Table Comparison of AutoAttack (AA) and our approach (A*) on 24 defenses. Further details of
each defense, discovered adaptive attacks and confidence intervals included in Appendix and
Robust Accuracy (1 Rerr)
Runtime (min)
Search
CIFAR-10, 100, c 4/255
AA
A²
AA
A²
Speed-up
A²
Madry
2018
44.78
44.69
-0.09
25
1.25x
A21
Buckman et a (2018
2.29
1.96
-0.33
9
7
1.29
116
A31
Das et al. 201
Lee
0.59
0.11
-0.48
3.00x
40
et al.
2018)
44
Metzen et al.
2017
6.17
3.04
-3.13
21
13
1.62
80
Guo et al.
2018
22.30
12.14
-10.16
1.12x
A61
Pang et al.
2019
4.14
3.94
-0.20
28
24
1.17x
237
A7
Papernot et
al. (2015)
2.85
2.71
-0.14
4
1.00
84
Xiao
2020
19.82
11.11
-8.71
2.23x
A9
Xiao al.
2020 ADV
64.91
63.56
-1.35
157
100
1.57x
179
A9
Xiao et al.
2020 ADV
64.91
17.70
-47.21
157
2,280
0.07x
1,548
CIFAR-10, 1s
8/255
B10
Gowal ct al.
2002
62.80
62.79
-0.01
818
226
3.62
761
Wu al.
2020 E:5
60.04
60.01
-0.03
706
255
2.77x
B12"
Zhang
22021
59.64
59,56
-0.08
604
261
2.31
565
B13"
Carmon et al.
(2019
59.53
59.51
-0.02
638
282
2.26x
575
B14
Schwag et al.
2020
57.14
57.16
0.02
671
429
1.56x
691
CIFAR-10, 100
8/255
C15*
Stutz et al.
2020)
77.64
39.54
-3..10
101
108
0.94
296
C15'
Stutz et al.
2020)
77.64
26.87
-50.77
101
205
0.49x
659
C16"
Zhang & Wang
2019
36.74
37.11
0.37
381
302
1.26x
726
C17
Grathwohl et al. (2020
5.15
5.16
0.01
107
114
0.94x
749
C18
Xiao al. (2020 ADV
5.40
-3.09
146
0.65
828
C19
Wang al.
2019
50.84
50.81
-0.03
734
372
1.97
755
c
B11 Defense in A3
60.72
60.04
-0.68
621
210
2.96x
585
C21
C17 + Defense in A3
15.27
5.24
-10.03
261
3.30x
746
C22
B11 Random Rotation
49.53
41.99
-7.54
255
462
0.55x
900
C23
C17 Random Rotation
22.29
13.45
-8.84
114
374
0.30x
1,023
C24
Hu et al. (2019)
6.25
3.07
-3.18
110
56
1.96x
502
"model available from the authors, "model with non-differentiabl components.
B12 uses 0.031. uses 0.03. uses time budget T. C15' uses m
Algorithm D by setting: the attack sequence length m 3, the number of trials k = 64, the initial dataset size 100, and we use time budget of 0.5 to seconds per sample depending on the model size. All of the experiments are performed using single RTX 2080 Ti GPU.
Evaluation Metric Following Stutz al. (2020), use the robust error (Rerr) metric to combine the evaluation of defenses with and without detectors. We include details in Appendix C In evaluation, A produces consistent results on the
model across independent runs with the standard deviation a < 0.2 (computed across 3 runs). The details are included in Appendix
Comparison to AutoAttack Our main results, summarized in Table show the robust accuracy (lower is better) and runtime of both AutoAttack (AA) and A over the 24 defenses. For example, for A8 tool finds an attack that leads to lower robust accuracy (11.1% 1% for A vs. 19.8% for AA) and is more than twice as fast (22 min for 3 vs. 49 min for AA). Overall, A significantly improves upon AA provides similar but faster attacks.
note that attacks from AA are included in our search space (although without the knowledge of their best parameters and sequence), and so it is expected that A performs at least well as AA, provided sufficient exploration time. Importantly, A often finds better attacks: for 10 defenses, 3 reduces the robust accuracy by 3% to 50% compared to AA. Next, we discuss the results in more detail.

---

Defenses based on Adversarial Training. Models in block B are selected from RobustBench (Croce) al., 2020), and they are based on various extensions of adversarial training, such as using ad- ditional unlabelled data for training. extensive hyperparameter tuning, instance weighting or loss regularization. The results show that the robustness reported by AA is already very high and using A leads to only marginal improvement. However, because our tool also optimizes for the runtime, A does achieve significant speed-ups, ranging from 1.5x to 3.6x. The reasons behind the marginal robustness improvement of A are two-fold. First, it shows that A is limited by the attack techniques search space, as the attack found are all variations of APGD. Second, the models B10 B14 aim to improve the adversarial training procedure rather than developing new defence. This is in contrast to models that do design various types of new defences (included in blocks A and C), evaluating which typically requires discovering new adaptive attack. For these new defences, evaluation is much more difficult and this is where our approach also improves the most.
Obfuscation Defenses. Defenses A3, A8, A9, C18, C20, and C21 are based on gradient obfuscation. A discovers stronger attacks that reduce the robust aceuracy for all defenses by up to 47.21% %. Here, removing the obfuscated defenses in A3, C20, and C21 provides better gradient estimation for the attacks. Further, the use of more suitable loss functions strengthens the discovered attacks and improves the evaluation results for A8 and C18.
Randomized Defenses. For the randomized input defenses A8, C22, and C23, A discovers attacks that, compared to AA's 's rand version, further reduce robustness by 8.71 %,, 7.54%, and 8. 8.84%, respectively. This is achieved by using stronger yet more costly parameter settings, attacks with different backbones (APGD, PGD) and 7 different loss functions (as listed in Appendix D)
Detector based Defenses. For C15, A4, and C24 defended with detectors, A improves over AA by reducing the robustness by 50.77%, 3.13%, and 3.18%, respectively. This is because none of the attacks discovered by A are included in AA. Namely, A found SQRPLR and APGDeinge for C15, untargeted FAB for A4 (FAB in AA is targeted), and ,GD,, for C24.
Generalization of A3 Given a new defense, the main strength of our approach is that it directly benefits from all existing techniques included in the search space. Here, we compare our approach to three handcrafted adaptive attacks not included in the search space.
As first example, C15 (Stutz et al. 2020 proposes an adaptive attack PGD-Conf with backtracking that leads to robust accuracy of 36,9% which can be improved to 31.6% by combining PGD-Conf with blackbox attacks. A finds APGDeinge and Z = probs. This combination is interesting since the hinge loss maximizing the difference between the top two predictions, in fact, reflects the PGD-Conf objective function. Further, similarly to the manually crafted attack by C15, different blackbox attack included in our search space, SQRDLE, is found to complement the strength of APGD. When using a sequence of three attacks, we achieve 39.54% robust accuracy. We decrease the robust accuracy even further by increasing the number of attacks to eight the robust accuracy drops to 26.87% which is a stronger result than the one reported in the original paper. In this case, search space and the search algorithm are powerful enough to not only replicate the main ideas of Stutz et al.. (2020) but also improve its evaluation when allowing for larger attack budget. Note that this improvement is possible even without including the backtracking used by PGD-Conf as a building block in our search space. In comparison, the robust accuracy reported by AA only 77.64%.
As a second example, C18 is known to be susceptible to NES which achieves 0.16% robust accuracy (Tramer et al., 2020). To assess the quality of our approach, remove NES from our search space and instead try to discover an adaptive attack using the remaining building blocks. In this case, our search space was expressive enough to find alternative attack that achieves 2.31 % robust accuracy.
As a third example, to break C24. Tramer et al. (2020) designed an adaptive attack that linearly interpolates between the original and the adversarial samples using PCD. This technique breaks the defense and achieves 0% robust accuracy. In comparison, we find PGD,., which achieves 3.07% robust accuracy. In this case, the fact that PGD,1 is relatively weak attack is an advantage it successfully bypasses the detector by not generating overconfident predictions.
3 Interpretability As illustrated above, it is possible to manually analyze the discovered attacks in order to understand how they break the defense mechanism. Further, we can also gain insights from the patterns of attacks searched across all the models (shown in Appendix [ Table (6) For example, it turns out that fog is not as frequent as COLA or Cninge. This fact challenges the common
8

---

practice of using fog as the default loss when evaluating robustness. In addition, using tcE during adversarial training can make models resilient fee, loss, but not necessarily to other losses.
A Scalability To assess ' scalability, we perform two ablation studies: (i) increase the search space by 4x (by adding 8 random attacks, their corresponding parameters, and 4 dummy losses), and (ii) keep the search space size unchanged but reduce the search runtime by half. In (i), we observed marginal performance decrease when using the same runtime, and we can reach the same attack strength when the runtime budget is increased by 1.5x. In (ūi), even when we reduce the runtime by half, we can still find attacks that are only slightly worse (S. 0.4). This shows that a budget version of the search can provide a strong robustness evaluation. We include detailed results in Appendix
Ablation Studies Similar to existing handcrafted adaptive attacks, all three components included in the search space were important for generating strong adaptive attacks for a variety of defenses. Here we briefly discuss their importance while including the full experiment results in Appendix [F]
Attack & Parameters. We demonstrate the importance of parameters by comparing PGD, C&W, DF, and FGSM with default library parameters to the best configuration found when available parameters are included in the search space. The attacks found by A are on average 5.5% stronger than the best attack among the four attacks on A models.
Loss Formulation. To evaluate the effect of modeling different loss functions, we remove them from the search space and keep only the original loss function defined for each attack. The search score drops by 3% on average for A models without the loss formulation.
Network Processing. In C21, the main reason for achieving 10% decrease in robust accuracy is the removal of the gradient obfuscated defense Reverse Sigmoid. We provide a more detailed ablation in Table which shows the effect of different BPDA instantiations included in our search space. For A2, since the non-differentiable layer is non-linear thermometer encoding, it is better to use a function with non-linear activation to approximate it. For A3, c20, C21, the defense is image JPEG compression and identity network is the best algorithm since the networks can overfit when training on limited data.
Table 2: The robust accuracy (1 Rerr) of net- works with different BPDA policies evaluated by APGDcE with 50 iterations.
BPDA Type
A2
A3
C20
C21
identity
18.5
9.6
70.5
84.0
Ixl convolution
8.9
10.3
70.8
84.9
layer conv+ReLU
3.7
14.9
74.1
86.2
Related Work
The most closely related work to ours is AutoAttack (Croce & Hein 2020b), which improves the evaluation of adversarial defenses by proposing an ensemble of four fixed attacks. Further, the key to stronger attacks was a new algorithm APGD, which improves upon PGD by halving the step size dynamically based on the loss at each step. In our work, we improve over AutoAttack in three keys aspects: (i) we formalize a search space of adaptive attacks, rather than using a fixed ensemble, (ii) we design search algorithm that discovers the best adaptive attacks automatically, significantly improving over the results of AutoAttack, and (ii)) our search space extensible and allows reusing building blocks from one attack by other attacks, effectively expressing new attack instantiations. For example, the idea of dynamically adapting the step size is not tied to APGD, but a general concept applicable to any step- algorithm.
Another related work is Composite Adversarial Attacks (CAA) MMa al. 2021). The main idea of CAA is that instead of selecting an ensemble of four attacks that complement each other as done by AutoAttack, the authors proposed to search for a sequence of attacks that achieve the best performance. Here, the authors focus on evaluating defences based on adversarial training and show improvements of up to 1% over AutoAttack. comparison, our main idea that the way adaptive attacks are designed today can be formalized as search space that includes not only sequence of attacks but also loss functions, network processing and rich space hyperparameters. This is critical as it defines a much larger search space to cover wide range of defenses, beyond the reach of both CA and AutoAttack This can be also seen in our evaluation - we achieve significant improvement by finding 3% to 50% more adversarial examples for 10 models.

---

Our work is also closely related to the recent advances in AutoML, such as in the domain of neural architecture search (NAS) (Zoph & Le 2017 Elsken et al. 2019). Similar to our work, the core challenge in NAS is an efficient search over large space of parameters and configurations, and therefore many techniques can also be applied to our setting. This includes BOHB (Falkner et al. 2018). ASHA (Li et al. 2018), using gradient information coupled with reinforcement learning (Zoph) Le 2017) or continuous search space formulation (Liu et al. 2019). Even though finding completely novel neural architectures is often beyond the reach, NAS is still very useful and finds many state-of- the-art models. This is also true in our setting - while human experts will continue to play a key role in defining new types of adaptive attacks, many of the intermediate steps.
show in our work, it is already possible automate
7 Conclusion
We presented the first tool that aims to automate the process of finding strong adaptive attacks specifically tailored to a given adversarial defense. Our key insight is that we can identify reusable techniques used in existing attacks and formalize them into a search space. Then, can phrase the challenge of finding new attacks as an optimization problem of finding the strongest attack over this search space.
Our approach automates the tedious and coneemmnnuming trial-and-error steps that domain experts perform manually today, allowing them to focus on the creative task of designing new attacks. By doing so, we also immediately provide a more reliable evaluation of new and existing defenses, many of which have been broken only after their proposal because the authors struggled to find effective attack by manually exploring the vast space of techniques. Importantly, even though our current search space contains only subset of existing techniques, our evaluation shows that A can partially re-discover or even improve upon some handcrafted adaptive attacks not included in our search space.
However, there are also limitations to overcome in future work. First, while the search space can be easily extended, it is also inherently incomplete, and domain experts will still play an important role in designing novel types of attacks. Second, the search algorithm does not model the attack runtime and as a result, incorporating expensive attacks can be computational unaffordable. This is problematic it can incur huge overhead even if fast attack does exist. Finally, an interesting future work is to use meta-learning to improve the search even further, allowing A to learn across multiple models, rather than starting each time from scratch.
8 Societal Impacts
In this paper, an approach to improve the evaluation of adversarial defenses by automatically finding adaptive adversarial attacks is proposed and evaluated. As such, this work builds large body of existing research on developing adversarial attacks and defences and thus shares the same socictal impacts. Concretely, the presented approach can be used both beneficial way by the researchers developing adversarial defenses, as well as, in a malicious way by an attacker trying to break existing models. In both cases, the approach designed to improve empirical model evaluation, rather than providing verified model robustness, and thus is not intended to provide formal robustness guarantees for safety-criticll applications. For applications where formal robustness guarantess are required, instead of using empirical techniques as in this work, one should instead adapt the concurrent line of work on certified robustness.
References
Andriushchenko, M., Croce, F., Flammarion, N., and Hein, M. Square attack: A query-efficient black-box adversarial attack via random search. In Vedaldi, A., Bischof, H., Brox, T., and Frahm, J.-M. (eds.), Computer Vision ECCV 2020, pp. 484-501, Cham, 2020. Springer International Publishing.
Athalye, A., Carlini, N., and Wagner, D. A. Obfuscated gradients give false sense of security: Cireumventing defenses to adversarial examples. In Dy, G. and Krause, A. (eds.). Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan.
10

---

Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pp. 274-283, PMLR, 2018.
Bergstra, J., Bardenet, R.. Bengio, Y., and Kégl, B. Algorithms for
optimization. In Shawe- Taylor, J., Zemel, R. S., Bartlett, P. L., Percira, F. C. N., and Weinberger, K. Q. (eds.), Advances in Neural Information Processing Systems 24: 25th Annual Conference Neural Information Processing Systems 2011. Proceedings of a meeting held 12-14 December 2011, Granada, Spain, pp. 2546-2554, 2011.
Biggio, B., Corona, I., Maiorca, D., Nelson, B., Šindić, N., Laskov, P., Giacinto, G., and Roli, F. Evasion attacks against machine learning at test time. In Joint European conference on machine learning and knowledge discovery in databases, pp. 387-402. Springer, 2013.
Buckman, J., Roy, A., Raffel, C., and Goodfellow, J. Thermometer encoding: One hot way to resist adversarial examples. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018.
Carlini, N. and Wagner, D. Towards evaluating the robustness of neural networks. In 2017 IEEE Symposium on Security and Privacy (SP), pp. 39-57, 2017.
Carlini, N. and Wagner, D. Adversarial examples are not easily detected: Bypassing detection methods. In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, AISec '17. pp. 314, New York, NY, USA, 2017, Association for Computing Machinery. ISBN 9781450352024.
Carmon, Y., Raghunathan, A., Schmidt, L.,, Duchi, J. C., and Liang, Unlabeled data improves adversarial robustness. In Wallach, H., Larochelle, H., Beygelzimer, A., d' A'cché Buc, F,, Fox, E., and Garnett, R. (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Croce, F. and Hein, M. Minimally distorted adversarial examples with a fast adaptive boundary attack. In Proceedings of the 37th International Conference Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 2196-2205. PMLR, 2020a.
Croce, F. and Hein, M. Reliable evaluation of adversarial robustness with an ensemble of diverse parameter- free attacks. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 2206-2216. PMLR, 2020b.
Croce, F., Andriushchenkko M., Sehwag, V., Flammarion, N., Chiang, M., Mittal, P., and Hein, M. Robustbench: a standardized adversarial robustness benchmark, 2020.
Das, N., Shanbhogue, M., Chen, S.-T., Hohman, F., Chen, L., Kounavis, M. E., and Chau, D. H. Keeping the bad guys out: Protecting and vaccinating deep learning with jpeg compression. arXiv preprint arXiv: I 1705 770.022900. 2017.
Elsken, T., Metzen, J. H., and Hutter, F. Neural architecture search: A survey, 2019.
Falkner, S., Klein, A., and Hutter, F. BOHB: robust and efficient hyperparameter optimization at scale. In Dy, J. G. and Krause, A. (eds.), Proceedings the 35th International Conference Machine Learning, ICML 2018, Stockholmsnässan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pp. 1445. PMLR, 2018
Goodfellow, I. J., Shlens, J., and Szegedy, C. Explaining and harnessing adversarial examples. In Bengio, Y. and LeCun, Y. (eds.). 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA. USA, May 7-9, 2015, Conference Track Proceedings, 2015.
Gowal, S., Qin, C., Uesato, J., Mann, T., and Kohli, P. Uncovering the limits of adversarial training against norm- coum-bounded adversarial examples, 2021.

---

Grathwohl, W., Wang, K., Jacobsen, J., Duvenaud, D., Norouzi, M., and Swersky. K. Your classifier is secretly an energy based model and you should treat it like one. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
Guo, C., Rana, M., Cissé, M., and van der Maaten, L. Countering adversarial images using input transformations. In 6th International Conference Learning Representations. ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018.
Hu, S., Yu, T., Guo, C., Chao, W., and Weinberger, K. Q. A new defense against adversarial images: Turning weakness into strength. In Wallach, H. M., Larochelle, H., Beygelzimer, A., d' Alché- Bue, F., Fox, F. B., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 1633-1644, 2019.
Jamieson, K. G. and Talwalkar, A. Non-stochastic best arm identification and hyperparameter optimization. In Gretton, A. and Robert, C. C. (eds.). Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, AISTATS 2016, Cadiz, Spain, May 9-11, 2016, volume 51 of JMLR Workshop and Conference Proceedings, pp. 240-248. JMLR.org. 2016.
Karnin, Z. S., Koren, T., and Somekh, O. Almost optimal exploration in multi-armed bandits. In Proceedings of the 30th International Conference on Machine Learning, ICML 2013, Atlanta, GA, USA, 16-21 June 2013, volume 28 of JMLR Workshop and Conference Proceedings. pp- 1238 1286.124..111 JoL,. 2013.
Lee, T., Edwards, B., Molloy, I., and Su, D. Defending against machine learning model stealing attacks using deceptive perturbations. arXiv preprint 1806v:1806.0m 00054, 2018.
Li, L., Jamieson, K., Rostamizadeh, A., Gonina, E., Hardt, M., Recht, B., and Talwalkar, A. Massively parallel hyperparameter tuning. arXiv preprint arXiv:1810.0599.1 2018.
Liu, H., Simonyan, K., and Yang. Y. DARTS: differentiable architecture search. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
Madry, A., Makelov, A., Schmidt, L.,, Tsipras, D., and Vladu, A. Towards deep learning models resistant to adversarial attacks. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30- May 3, 2018, Conference Truck Proceedings. OpenReview.net, 2018
Mao, X., Chen, Y., Wang, S., Su, H., He, Y., and Xue, Composite adversarial attacks. Proceedings of the AAAI Conference on Artificial Intelligence, 35(10) 8892, May 2021. URL https //jjs aaai. wwai.org/aaa....aa.....a.aaa index, , ptppAAA//aatiiicle/veees/////
Metzen, J. H., Genewein, T., Fischer, V., and Bischoff, B. On detecting adversarial perturbations. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017.
Mozsavi-Dezfooli, S., Fawzi, A., and Frossard, P. Deepfool: A simple and accurate method to fool deep neural networks. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp.
June 2016.
Nicolae, M., Sinn, M., Minh, T. N., Rawat, A.. Wistuba, M., Zantedeschi, V., Molloy, I. M., and Edwards, B. Adversarial robustness toolbox v0.2.2. CoRR, abs/ 807.01069, 2018
Pang, T., Xu, K., Du, C., Chen, N., and Zhu, J. Improving adversarial robustness via promoting ensemble diversity. In Chaudhuri, K. and Salakhutdinov, R. (eds.), Proceedings of the 36th Inter- national Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pp. 4970-4979, PMLR, 2019.
Papernot, N., McDaniel, P. D., Wu, X., Jha, S., and Swami, A. Distillation as a defense to adversarial perturbations against deep neural networks. CoRR, abs/ 151.1505, 2015.
12

---

Paszke, A., Gross, S.. Massa, F., Lerer, A., Bradbury, J.. Chanan, G., Killeen, T., Lin. Z., Gimelshein,
N., Antiga, L., Desmaison, A., Köpf, A., Yang, E.. De Vito, Z., Raison, M., Tejani, A., Chilamkurthy, S., Steiner, B., Fang, I.., Bai, J., and Chintala, S. Pytorch: An imperative style, high-performance deep learning library. In Wallach, H. M., Larochelle, H.,, Beygelzimer, A., d' Alché-Buc, F., Fox, E. B., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 8024-8035, 2019.
Rauber, J., Brendel, W., and Bethge, M. Foolbox: A python toolbox to benchmark the robustness of machine learning models. In Reliable Machine Learning in the Wild Workshop, 34th International Conference on Machine Learning, 2017.
Sabour, S., Cao, Y., Faghri, F., and Fleet, D. Adversarial manipulation of deep representations. In Bengio, Y. and LeCun, Y. (eds.), 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, 2016.
Sehwag, V., Wang, S., Mittal, P., and Jana, Hydra: Pruning adversarially robust neural networks. Advances in Neural Information Processing Systems (NeurIPS), 7, 2020.
Stutz, D., Hein, M., and Schiele, B. Confidence-calibraaeed adversarial training: Generalizing to unseen attacks. In Proceedings of the 37th International Conference on Machine Learning. ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 9155-9166. PMLR, 2020.
Szegedy, C., Zaremba, W., Sutskever, I., Bruna, J., Erhan, D., Goodfellow, I. J., and Fergus, R. Intriguing properties of neural networks. In Bengio, Y. and LeCun, Y. (eds.), 2nd International Conference on Learning Representations, ICLR 2014, Bansf, AB, Canada, April 14-16, 2014, Conference Track Proceedings, 2014.
Tramer, F., Carlini, N., Brendel, W., and Madry, A. On adaptive attacks to adversarial example defenses. arXiv preprint 2002.00002 2020.
Wang, B., Shi, Z., and Osher, S. J. Resnets ensemble via the feynman-kac formalism to improve natural and robust accuracies. In Wallach, H. M., Larochelle, H., Beygelzimer, A., d' Alché- Buc, F,, Fox, E. B., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NewrlPS 2019, December 8- 8-14, 2019, Vancouver, BC, Canada, pp. 1655-1666 2019.
Wierstra, D., Schaul, T., Peters, J., and Schmidhuber, J. Natural evolution strategies. In 2008 IEEE Congress on Evolutionary Computation (IEEE World Congress on Computational Intelligence), pp. 3381-3387. IEBE, 2008
Wu, D., Xia, S.-T., and Wang, Y. Adversarial weight perturbation helps robust generalization. Advances in Neural Information Processing Systems, 33, 2020.
Xiao, C., Zhong, P., and Zheng, C. Enhancing adversarial defense by k-winners-take-all, In International Conference on Learning Representations, 2020.
Zhang. H. and Wang. J. Defense against ad adversarial attacks using feature scattering beaseering-based adversarial training. In Wallach, H. M., Larochelle, H., Beygelzimer, A., d' Alché-Bus F., Fox, E. B., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 1829-1839, 2019.
Zhang, J., Zhu, J., Niu, G., Han, B., Sugiyama, M.. and Kankanballi, M. Geometry awwae instance- reweighted adversarial training. In International Conference on Learning Representations, 2021.
Zoph, B. and Le, Q. V. Neural architecture search with reinforcement learning. 5th Interna- tional Conference Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017.
13


Reviews:
[{"review_id": "ox24mY3LTgn", "reviewer": "Reviewer_KocB", "summary": "One major challenge in the research on adversarial attacks is the absence of methods that can reliably evaluate an adversarial defense. One the one hand, many defense approaches end up targetting particular attack methods. On the other hand, some promising defense approaches are viewed skeptically due to possible new attacks that could break them even if none currently exists. This paper addresses this critical challenge of developing adaptive adversarial attacks by combining some basic building blocks based on a particular defense. The presented approach is shown to outperform AutoAttack - a popularly used baseline attack by community developing adversarial defenses. \n\nThe submission presents an automated approach to the discovery of adversarial attacks (along the lines of AutoAttack) by exploring the search space of adversarial attacks formed by varying three components: (i) parameterized attack algorithms, (ii) network transformations, and (iii) loss functions. \n\nOverall, the paper is an interesting improvement over the state-of-the-art and clarification to some questions below will help the reviewer better appreciate its overall contribution. ", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths\n\n+ The use of parameter search algorithms to tune adversarial attacks generated by a formal grammar is likely to be useful. More discussion on the parameter search and its efficacy/challenges may be helpful.\n\n+ The paper includes a meticulous comparison with state-of-the-art. In particular, it highlights the key distinctions from AutoAttack and another recently proposed adaptive attack (Tramer et. al. 2020). \n\n+ The paper has identified dimensions of different adaptive attack methods (attack algorithm params, network transformations,  loss functions), which could be possibly reused to develop new adaptive attack techniques. \n\n+ The implementation is available open-source. \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Weaknesses\n\n(-) The idea of replacing a human expert attacking a model with an algorithm is interesting. However, it is not clear if an automated approach can be as creative as a human expert. For example, layer removal when the inputs and outputs have the same shape (lines 128-129) can be easily circumvented by a human expert by adding redundant inputs or outputs that this automated tool may not discover. Can the network transformation take care of such cases? \n\n(-) The experiment results on the top models (A1 and B10-B14) in Table 1 do not show very significant improvement over AutoAttack. Improvements against Madry et al (A1) is 0.9 and against robust models (B10-B14) is below 0.1. Were any ablation studies performed on models (B10-B14)?\n\n(-)  The grammar presented here to represent the space of possible attacks  is quite simple. Would the defense algorithms not be able to exploit the knowledge of this grammar?", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "g5KLzt834wX", "reviewer": "Reviewer_UerA", "summary": "The paper advances state-of-the-art automated pen-testing tools for breaking defenses designed to protect deep neural networks against norm-based adversarial attacks as a search problem. The search process first considers techniques to simplify the network being attacked (called Network Transformations), followed by a search over the space of existing attacks (and common ways to modify these attacks). Given the search space is large, the authors try to improve the efficiency by leveraging sub-sampling methods.", "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": "### Strengths\n\n- The paper is easy to follow.\n- The paper structures the idea of adaptive attacks into a search algorithm, making existing tricks leveraged in attacks simply a search node in the space of attacks.\n- The results show that, in certain cases, their improvement to AutoAttack can result is finding stronger or faster attacks. I appreciate that they to do a fair evaluation, they also empower AutoAttack with some additions (such as BPDA) that their framework leverages.\n- The analysis of how the attacks found relate to existing observations made by existing research was an intersting read.\n- The ablation studies does do help to ensure that various parts of the search algorithm do indeed help in finding the best attack.\n\n### Weaknesses / Correctness / Clarification\n\n- The paper adds a bunch of bells-and-wistles to AutoAttack and is more of an automated pen-testing software paper; I could not find much novelty or insights for improving the attack of deep neural networks. While auto attack proposes two extensions of PGD and then considers an ensemble approach, the contribution of this paper seems to be a search process formulated over the space of existing attacks (modifications thereof), and network transformations etc.\n- $A^3$ hardly provides improvement over adversarial training based defenses. This indicates that without novel attacks (lines 233-235), the search procedure may not be add any value in finding the best attack against SOTA defenses, tying back to the lack of novelty pointed above.\n- While reading, I kept thinking if a meta-learning approach to the search would be an interesting consideration. I found the authors mentioned this as future work at the very end. I surely think using something similar to meta-learning would add more novelty that simply bucketing existing tips and tricks at different layers of a computationally expensive search process.\n- Why did the authors evaluate on a sub-set of the defenses on which AutoAttack was evaluated? It sort of gives the impression that $A^3$ did not provide any gains compared to AA (w.r.t accuracy or time) on the defenses omitted.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The idea of developing automated pen-testing tools is often discussed in the context of correctly calibrating the security offered by existing defenses. At the same time, it benefits an attacker, who now has to spend less resources if figuring out the best attack against a defense.\n\nWhile this paper is not solely responsible in this regard, we should consider a better way to release such methods (say, learn from the best practices in cybersecurity). In cybersecurity, vulnerabilities often found by automated pen-testing software have know fixes/patches; this is not presently the case for deep neural networks (esp. if we consider real-world attacks and defenses). Thus, we (as a community) need to devote more thought before arming attackers with such automated software, which must consider re-evaluating research progress in this direction starting from the impact of releasing code to accepting such papers etc.", "review_text": "", "extra_scores": {"ethical_concerns": "See limitations and societal impacts.", "needs_ethics_review": "Yes", "ethics_review_area": ["Inappropriate Potential Applications & Impact  (e.g., human rights concerns)"], "time_spent_reviewing": "5-6"}, "extra_text": {}}, {"review_id": "dRmybAHX_iP", "reviewer": "Reviewer_rcDN", "summary": "This paper claim that adaptive attacks are composed from a set of reusable building blocks that can be formalized in a search space and used to automatically discover attacks for unknown defenses. Based on this observation, they propose an automated framework of discovering adaptive attacks, which does not rely on the expert's knowledge priori.", "questions": "", "limitations": "", "rating": 4, "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:**\nThe work is meaningful in engineering, but its contribution and novelty are limited.\n\nQ1: There is a problem with the motivation of this paper, that is, this work believes that adaptive attacks in Tramer et al. (2020) require expert knowledge, so A^3 is proposed. But A^3 does not have experiments to prove that it is superior to an adaptive attack based on expert knowledge. Pang et al. (2019) and Xiao et al. (2020) in Tramer et al. (2020) are both close to 0% after adaptive attacks, and A^3 cannot do this. So, what is the goal of this paper? Perhaps the strongest adaptive attack still requires experts to design.\n\nQ2: Composite Adversarial Attack (CAA) [1] is proposed for automatically searching the best combination of attack algorithms and their hyper-parameters from a candidate pool of 32 base attackers. The experimental result shows CAA beats 10 top attackers on 11 diverse defenses with a less elapsed time (6 × faster than AutoAttack) and achieves the new state-of-the-art on l∞, l2, and unrestricted adversarial attacks. Obviously, CAA and this work have similar ideas, and both are to evaluate the robustness of the model, but this work is not compared with CAA, nor does it cite CAA, even if CAA’s code is open.\n\n**Quality:**\nThe experiment in this paper proves that it is better than AutoAttack, but there are several problems:\n\nQ3: AutoAttack is a parameter-free, computationally affordable, and user-independent ensemble of attacks to test adversarial robustness and not specifically designed for adaptive attacks. From this perspective, if this work wants to highlight the advantages of adaptive attacks, the comparison with AutoAttack is unfair, even though AutoAttack has been improved with adaptive attacks. A better way is to explicitly compare with existing or adaptive attack methods in the original paper.\n\nQ4: A^3 is closely related to the recent advances in AutoML, such as in the domain of neural architecture search (NAS). How to reflect the advantages of your search strategy? What’s more, the combination of NAS and adversarial attacks already exists (CAA[1]) and should be compared with it.\n\nQ5: In the body, the experiment only has the setting of L∞, can A^3 be extended to other L-norm settings? There are other L-norm experiments in AutoAttack and CAA[1].\n\n\n**Clarity:**\nThe paper is clear on the whole. \n\n**Significance:**\nThis work is meaningful in engineering applications. If it is superior to adaptive attacks based on expert knowledge, it is vital for reliable evaluation of adversarial defenses.\n\n\n[1] Xiaofeng Mao, Yuefeng Chen, Shuhui Wang, Hang Su, Yuan He, Hui Xue: Composite Adversarial Attacks. AAAI 2021: 8884-8892", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "20"}, "extra_text": {}}, {"review_id": "4pOT4oQccV8", "reviewer": "Reviewer_Z4Ru", "summary": "This paper's main premise is that existing defense evaluations (whether adaptive or based on an ensemble of fixed attacks) only rely on a small number of common techniques and that a search over the space of possible attacks can efficiently uncover strong attacks.", "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": "The automatization of defense evaluations is ultimately a good thing, I think, if it leads to fewer clear mistakes and omissions in these evaluations. The proposal in this paper is quite natural and straightforward, in that it combines existing techniques and evaluates them against previously-evaluated defenses. To make this contribution more compelling, the paper could benefit from expanding along the following two axes:\n\n1) Generality\n\nExisting attacks indeed seem to make use of only a small number of different components. This is especially true for defenses that don't do anything \"weird\" at evaluation time. And many of the defenses (re-)evaluated in this paper are of this form (e.g., all forms of adversarial training).\n\nBut now let's imagine that a new defense comes out, that hasn't been independently evaluated before.\nShould we trust the procedure outlined in this paper to find a strong attack?\nI encourage the authors to explicitly think about this next step: what would it take to design a defense that is (a) non-robust, yet (b) resits your automated attack procedure?\nMy guess is that it wouldn't be too hard to build such a defense, and that this should be acknowledged.\n\nThe paper's claim that it automates the manual search for attacks (e.g., of Athalye et al. or Tramer et al.) is also hard to assess, as the proposed attack search is only evaluated against a small subset of the defenses evaluated in those works. Unless I am mistaken, I count 3/9 defenses in common with the work of Athalye et al. and 3/13 in common with the work of Tramer et al.\n\nIt thus seems challenging to reach a conclusion on whether automated search techniques could have found good attacks for some of these challenging defenses. And as noted above, we also don't know how well the proposed search procedure works against defenses that haven't been re-evaluated before.\n\n2) Ease-of-use\n\nRelated to the above discussion on the attack's generality is the question of its ease-of-use. My worry here is that the more general an automated attack aims to become, the harder it will become to use as it will inevitably require the defense to be represented in a tool-specific way.\nE.g., certain defenses may not be designed in a way that makes it easy to replace individual components with a BPDA approximation. Or some defenses (e.g., detectors) may produce outputs that cannot immediately be converted into the type of score your attack expects.\nIs there reason to believe that this (manual) process of adapting a defense to an automated attack tool is necessarily easier and less error-prone than the implementation of an appropriate attack?\n\n\nAdditional comments:\n\n- how do you automate the process of applying EOT? Often, different defenses will rely on very different forms of random transformations.\n- For the comparisons in Table 1, it would be worth including some confidence intervals when comparing A3 and AA. E.g., for all the B* models, the difference between the two attacks is most certainly not statistically significant.\n- Why do you include attacks such as FGSM or DeepFool in your search space, when these are known to super-seeded by newer stronger attacks?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "As stated in the main review, the generality of the approach should be further discussed, as well possible limitations against future defenses.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper introduces a technique to better perform adaptive attacks on adversarial example defenses. Current evaluations are large done by hand, and the paper here introduces a technique to automate some of that process. While the reviewers all like the overall tone of the paper, the reviewers are generally concerned about three aspects of the paper.

First, the paper does not demonstrate that it can automate all possible hand-specified attacks (for example, it has a limited design space that might not identify redundant neurons).

Second, the paper considers only a subset of the attacks used in prior papers. And so saying that this attack can match prior work may not actually be valid.

Third, the attack may not yet be practical to use for defenders.

Taken as a while, while I agree that these are definite limitations to this technique, this is the first paper to try these kinds of automated adaptive attacks and is worth publishing. While the implementation is imperfect at the moment, and is more work to be done on evaluation and improved attack, this can be done with followup work. If it turns out that this idea is not actually better than the human-designed attacks, future work could help identify the cases where this is true or improve the attack to make it more effective. Even though this attack is not likely practically useful for defenders yet, the new direction it opens might help in the future.
Decision: Accept (Poster)