Perturbation Type Categorization for Multiple $\ell_p$ Bounded Adversarial Robustness
Authors: Pratyush Maini
Xinyun Chen
Bo Li
Dawn Song
Venue:  (2021)
Keywords: adversarial examples
robustness
multiple perturbation types

Abstract: Despite the recent advances in $\textit{adversarial training}$ based defenses, deep neural networks are still vulnerable to adversarial attacks outside the perturbation type they are trained to be robust against. Recent works have proposed defenses to improve the robustness of a single model against the union of multiple perturbation types. However, when evaluating the model against each individual attack, these methods still suffer significant trade-offs compared to the ones specifically trained to be robust against that perturbation type. In this work, we introduce the problem of categorizing adversarial examples based on their $\ell_p$ perturbation types. Based on our analysis, we propose $\textit{PROTECTOR}$, a two-stage pipeline to improve the robustness against multiple perturbation types. Instead of training a single predictor, $\textit{PROTECTOR}$ first categorizes the perturbation type of the input, and then utilizes a predictor specifically trained against the predicted perturbation type to make the final prediction. We first theoretically show that adversarial examples created by different perturbation types constitute different distributions, which makes it possible to distinguish them. Further, we show that at test time the adversary faces a natural trade-off between fooling the perturbation type classifier and the succeeding predictor optimized with perturbation specific adversarial training. This makes it challenging for an adversary to plant strong attacks against the whole pipeline. In addition, we demonstrate the realization of this trade-off in deep networks by adding random noise to the model input at test time, enabling enhanced robustness  against strong adaptive attacks. Extensive experiments on MNIST and CIFAR-10 show that $\textit{PROTECTOR}$ outperforms prior adversarial training based defenses by over $5\%$, when tested against the union of $\ell_1, \ell_2, \ell_\infty$ attacks.

Under review as a conference paper at ICLR 2021
PERTURBATION TYPE CATEGORIZATION FOR MULTI- PLE Lp BOUNDED ADVERSARIAL ROBUSTNESS
Anonymous authors Paper under double-blind review
ABSTRACT
Despite the recent advances in adversurial training based defenses, deep neural networks are still vulnerable adversarial attacks outside the perturbation type they are trained to be robust against. Recent works have proposed defenses to improve the robustness of a single model against the union of multiple perturbation types. However, when evaluating the model against each individual attack, these methods still suffer significant trade-off's compared to the ones specifically trained to be robust against that perturbation type. In this work, we introduce the problem of categorizing adversarial examples based their lp perturbation types. Based on our analysis, we propose PROTECTOR, a two-stage pipeline to improve the robustness against multiple perturbation types. Instead of training single predictor, PRoTECTOR first categorizes the perturbation type of the input, and then utilizes a predictor specifically trained against the predicted perturbation type to make the final prediction. We first theoretically show that adversarial examples created by different perturbation types constitute different distributions, which makes it possible distinguish them. Further, show that test time the adversary faces natural trade-off between fooling the perturbation type classifier and the succeeding predictor optimized with perturbation specific adversarial training. This makes it challenging for an adversary to plant strong attacks against the whole pipeline. In addition, we demonstrate the realization of this trade-off in deep networks by adding random noise to the model input at test time, enabling enhanced robustness against strong adaptive attacks. Extensive experiments on MNIST and CIFAR-10 show that PROTECTOR outperforms prior adversarial training based defenses by over 5%, when tested against the union of &,, l2, foo attacks
INTRODUCTION
There has been long line of work studying the vulnerabilities of machine learning models to small changes in the input data. In particular, most existing works focus on lp bounded perturbations (Szegedy et al. 2013 Goodfellow et al., 2015). While majority of the prior work aims at achieving
robustness against single perturbation type (Madry et al. [0088] Kurakin et al. 2017] Tramer et al.) 2018 Dong al.) 2018 Zhang et al. 2019 Carmon et al. 2019), real-world deployment of machine learning models requires them to be robust against various imperceptible changes the input, irrespective of the attack type. Prior work has shown that when models are trained to be robust against one perturbation type, such robustness typically does not transfer to attacks of a different type (Schott) et al. 2018: Kang et al. 2019). As result, recent works have proposed develop models that robust against the union of multiple perturhation types (Tammr & Boneh 2019 Maini et al. 2020). Specifically, these works consider adversaries limited by their t, distance from the original input for E 2, 2o). While these methods improve the overall robustness against multiple perturbation types, when evaluating the robustness against each individual perturbation type, the robustness of models trained by these methods is still considerably worse than those trained on single perturbation type. Further, these methods are found sensitive to small changes in hyperparameters.
In this work, we propose an alternative view that does not require a single predictor to be robust against a union of perturbation types. Instead, we propose to utilize a union of predictors improve the
We will open-source the code, pre-trained models, and perturbation type datasets upon publication.

---

Under review as a conference paper at ICLR 2021
overall robustness, where each predictor is specialized to defend against certain perturbation types. In particular, we introduce the problem of categorizing adversarial examples based on their perturbation types. Based on this idea, we propose PROTECTOR, two-stage pipeline that performs Perturbation Type Categorization for Robustness against multiple perturbations. Specifically, first a perturbation type classifier predicts the type of the attack. Then, among the second-level predictors, PROTECTOR selects the one that is the most robust to the predicted perturbation type to make final prediction.
We validate our approach from both theoretical and empirical aspects. First, we present theoretical analysis to show that for benign samples with the same ground truth label, their distributions become highly distinct when added with different types of perturbations, and thus can be separated. Further, we show that there exists a natural tension between attacking the top-level perturbation classifier and the second-level predictors - strong attacks against the second-level predictors make it easier for the perturbation classifier to predict the adversarial perturbation type, and fooling the perturbation classifier requires planting weaker (or less representative) attacks against the second-level predictors. As result, even an imperfect perturbation classifier is sufficient to significantly improve the overall robustness of the model to multiple perturbation types.
Empirically, we show that the perturbation type classifier generalizes well on classifying adversarial examples against different adversarially trained models. Then we further compare PROTECTOR to the otate-of-the-art defenses against multiple perturbations on MNIST and CIFAR-10 10. PROTECTOR outperforms prior approaches by over 5% against the union of the & E and lo attacks. While past work has focused on the worst case metric against all attacks, on average they suffer significant trade- off's against individual attacks. From the suite of 25 different attacks tested, the average improvement for PROTECTOR over all the attacks w.r.t. the state-of-art baseline defense is 15% on both MNIST and CIFARIO I0. In particular, by adding random noise to the model input at test time, we further increase the tension between attacking top-level and second-level components, and bring in additional improvement of robustness against adaptive attackers. Additionally, PROTECTOR provides modular way to integrate and update defenses against a single perturbation type.
RELATED WORK
Adversarial examples. The realization of the existence of adversarial examples in deep neural networks has spun active research on attack algorithms and defense proposals (Szegedy et al., 2013)) Among different types of attacks (Madry et al. 2018 Hendrycks al., 2019 Hendrycks Dietterich 2019 Bhattad et al., (020). the most commonly studied ones constrain the adversarial perturbation within an Ep region of radius Ep around the original input. To improve the model robustness in the presence of such adversaries, the majority of existing defenses utilize adversarial training (Goodfellow let al. 2015). which augments the training dataset with adversarial images. Till date, different variants of the original adversarial training algorithm remain the most successful defenses against adversarial
attacks (Carmon et al., 2019, Zhang et al. 2019 Wong et al. 2020; Rice et al. 2020p. Other types of defenses include input transformation Guuo et al.) 2018 Buckman et al.
2018) and network
distillation (Papernot et al. 2016). but were rendered ineffective under stronger adversaries (He)
et al. 2017 Carlini & Wagner 2017a| AAhaayy et al.) 2018 Tramer al. 2020). Other works have explored the relation between randomizing the inputs and adversarial examples. iTbacof & Valle (2016) analyzed the change in adversarial robustness with varying levels of noise. | et al. (2019) evaluated the robustness of a data point to random noise to detect adversarial examples, whereas Cohen et al. (2019) utilized randomized smoothing for certified robustness adversarial attacks.
Defenses against multiple perturbation types. Recent research has been drawn towards the goal of universal adversarial robustness. Since f--norm bounded attacks are amongst the strongest attacks in adversarial examples literature. defending against a union of such attacks is an important step towards this end goal. [Schott et al. (2018); Kang et (211 showed that models that were trained for a given fp-norm bounded attacks are not robust against attacks in a different l region. Succeeding work has aimed at developing one single model that is robust against the union of multiple perturbation types. Schott et al. (2018) proposed the use of multiple variational autoencoders to achieve robustness to multiple 4, attacks on the MNIST dataset. Tramer& & Boneh (2019) used simple aggregations of multiple adversaries to achieve non-trivial robust accuracy against the union of the L1, &2, & regions.
Maini et al. (2020) proposed the MSD algorithm that takes gradient steps in the union of multiple 4 regions to improve multiple perturbation robustness. In a related line of work, Croce & Hein (022aa)
2

---

Under review as a conference paper at ICLR 2021
proposed method for provable robustness against all &p regions for p 2 1. Instead of presenting empirical results, they study the upper and lower bounds of certified robust test error on much smaller perturbation radii. Therefore, their work has different focus, and is not directly comparable to empirical defenses studied in our work.
Detection of adversarial examples. Multiple prior works have focused detecting adversarial examples (Feinman et al.) 2017] Lee et al. 2018 Ma et al. 2018 Cennamo et al. 2020 Fidel et al. 2019; Yin et al., 201 b). However, most of these defenses have been shown to be vulnerable in the
presence of adaptive adversaries (Carlini & Wagner 2017a Tramer et al. 2020). In comparison, our work focuses on more challenging problem of categorizing different perturbations types. However, we show that by establishing trade-off between fooling the perturbation classifier and the individual fp-robust models, even an imperfect perturbation classifier sufficient make our pipeline robust.
PROTECTOR: PERTURBATION TYPE CATEGORIZATION FOR ROBUSTNESS
In this section, discuss proposed PROTECTOR approach, which performs perturbation type categorization to improve the model robustness against multiple perturbation types. We first illustrate the PROTECTOR pipeline in Figure then discuss the details of each component.
M
Mi
Loo
(49 + 22 PlRj
O
+8p
Cadv
C'ui
Loo
M
M
Perturbation
Specialized Robust
Perturbation Classifier
Specialized
Classifier
Robust
Predictors
Predictors
(b)
Figure 1: An overview of our PROTECTOR pipeline. (a) The perturhation classifier Cady correctly categorizes representative attacks of different types. (b) An illustration of the trade-off Theorem [ where adversarial example fooling Cads (the l.o. sample marked in red) becomes weaker attack second-level M, models.
At high level, PROTECTOR performs the classification task as a two-stage process. Given input z, PROTEC- TOR first utilizes perturbation classifier Cado to predict its adversarial perturbation type. Then, based the E attack type predicted by Cade, PROTECTOR uses the cor-
Second Companant
responding second-level predictor M, to provide the final prediction, where M,, is specially trained to be robust against the f attack. Formally, let fo be the PROTECTOR model, then the final prediction is:
Allack Type
fo(x)) M,(x); s.l. p arginax Cadu (a)
(1)
Note that when the input is benign image, it could be clas- sified as any perturbation type by Cade. since all second- level predictors should achieve high test accuracy benign images.
First Component
PCA for different types of adver- sarial examples on MNIST.
Figure 2:
As shown in Figure 1 although consider the robustness against three attack types, i.e., l1, Eg loc perturbations, unless otherwise specified, our perturbation classifier performs binary classification between p ((1, 2), xo). As will be discussed in Section 6. using second-level predictors

---

Under review as a conference paper at ICLR 2021
achieves better overall robustness than using three second-level predictors. We hypothesize that compared to the foe adversarial examples, & and & attacks are harder to separate, especially when facing adaptive adversary which aims to attack the entire pipeline. To provide an intuitive illustration, we randomly sample 10K adversarial examples generated with PGD attacks on MNIST, and visualize the results of the Principal Component Analysis (PCA) in Figure We observe that the first two principal components for & and Eg adversarial examples are largely overlapping, while those for lo are clearly from a different distribution. Note that this simple visualization by no means suggest that 1 and & adversarial examples are not separable, it merely serves as a motivation.
4 THEORETICAL ANALYSIS
In this section, we provide a theoretical justification of our PROTECTOR framework design. First, we formally illustrate the setup of robust classification against multiple e, perturbation types, and we consider models trained for a binary classification task. Based on this problem setting, in Theorem []] we show the existence of classifier that can separate adversarial examples belonging to different perturbation types. Moreover, in Theorem 2 we show that our PROTECTOR framework naturally offers trade-off between fooling the perturbation classifier Cady and the individual robust models Mp thus it is extremely difficult for adversaries to stage attacks against the entire pipeline. Note that we focus on the simplified binary classification task for the convenience of theoretical analysis, but our PROTECTOR framework could improve the robustness of models trained on real-world image classification benchmarks as well, and will discuss the empirical examination in Section 6
4.1 PROBLEM SETTING
Data distribution. We consider a dataset of inputs sampled from the union of two multi-variate Gaussian distributions D, such that the input-label pairs (x.y) can be described as:
y u.a." {-1,+13;
No~N(yaa o²), 21....; zd i.dd (Bm,
(2)
where x = [2o, ,1o
Faa] E Rd+1 and = va- such that the absolute value of the mean for any dimension is equal for inputs sampled from both the positive and the negative labels. This setting demonstrates the distinction between a feature Ty that is strongly correlated with the input label, and d weakly correlated features that are (independently) normally distributed with mean yn and variance o². For the purposes of this work, we assume that - > weakly correlated, but together represent strongly correlated feature). We
10 (Io is strongly correlated) and 100
(remaining d features adapt this problem setting from llyas et al. (2019), where they used a stochastic feature 2g = y with probability p. as opposed normally distributed input feature as in our case. Our results hold in their setting as well. However, our setting better represents the true data distribution, where input features are seldom stochastically flipped. More discussion could be found in Appendix A
Perturbation types. We focus our discussion on adversaries constrained within fixed fp region of radius Ep around the original input, for p E S = (1, 2, ).). Such adversaries are frequently studied in existing work, primarily for finding the optimal first-order adversaries for different perturbation types. We define Ap.c as the Ep threat model of radius e and As = UpES Ap.c- For model fo parametrized over 6, the objective of the adversary
find the optimal perturbation 8*, such that:
8' arg max {(fo(x + 5).9)
deds
where e(.,) ) is the cross-entropy loss. Based on the model design in Section 3 we focus on discussing the separation of & and foo in the following theorems, but our proofs could also naturally be adapted to analyze the separability of other perturbation types.
4.2 SEPARABILITY OF ADVERSARIAL PERTURBATIONS
Consider a standard classifier M trained with the objective of correctly classifying the label of inputs E D. Since the original distribution of the input data for each label is known to us, we first aim to examine how adversaries confined within different perturbation regions modify the input. The goal of the adversary is to fool the label predictor M, by finding the optimal perturbation 8, Yp S. The theorem below shows that the distributions of adversarial inputs within different f, regions can be separated with high accuracy, and we present the formal proof in Appendix B
4

---

Under review as a conference paper at ICLR 2021
Theorem 1 (Separabilitty of perturbation types). Given a binary Gaussian classifier M trained on D. consider D to be the distribution of optimal adversarial inputs (for a class y) against M, within & regions of radius cp. where c a, <o /d. Distributions D2 (p (0)) can be accurately separated by binary Gaussian classifier Cade with a misclassification probability P. I 10-24.
The proof sketch is as follows. We first calculate the optimal weights of a binary Gaussian classifier M trained on DD Accordingly, for any input x E DD we find the optimal adversarial perturbation Sp E (1, )o) against M. We discuss how these perturbed inputs x + 6p also follow normal distribution, with shifted means. Finally, for data points belonging to a given classification label, we show that Cade is able to predict the correct perturbation type with a very low classification error. We present the formal proof in Appendix B
4.3 ADVERSARIAL TRADE-OFF
In Section 4.2 showed that the optimal perturbations corresponding to different perturbation types belong to distinct data distributions, and it is fairly easy to separate them using simple classifier. However, in the white-box setting, the adversary has knowledge of both the perturbation elassifier Cude and specialized robust models Mp at test time. Therefore, the adversary can adapt the attack to fool the entire pipeline, instead of individual models Mp alone.
Note that there are some overlapping regions among different ép perturbation regions. For example, every adversary could set 6p = 0 as a valid perturbation, and thus is clearly not possible for the attack classifier Cade to correctly classify the attack (Vp E {1, 2, ool) in such a scenario. However, such perturbation not useful, because all the base models can correctly classify unperturbed inputs with high probability. In the following theorem, pipeline in the presence of such strong dynamic adversaries.
examine the robustness of our PROTECTOR
Theorem 2 (Adversarial trade-off), Given data distribution DD adversarially trained models Maey, and an attack classifier Cadv that distinguishes perturbations of different Ep attack types for p E {1, }. The probability of successfid attack for the worst-case adversary over the entire PROTECTOR pipeline is P. < 0.01 for E1 a + 22 and 600
vd
Here, the worst-case adversary refers to adaptive adversary that has full knowledge of the defense strategy, and makes the strongest adversarial decision given the perturbation constraints. In Appendix C.2 discuss how 61, Coo set that the & and for adversaries can fool Mac,.s and My.e, models respectively with a high success rate. Our proof sketch is as follows. We first show that when trained on D, an adversarially robust model Mp can achieve robust accuracy of greater than 99% against the attack type it was trained for. On the contrary, when subjected to attacks outside the trained perturbation region, such robust accuracy reduces to under 2%. Then, we analyze the modified distributions of the perturbed inputs by different E, attacks. Based on this analysis, we construct a simple decision rule for the perturbation classifier Cadu- Finally, we compute the perturbation induced by the worst-case adversary. We show that there exists trade-off between fooling the perturbation classifier Cadv (to allow the alternate Mp model to make the final prediction for an ey attack Vp, E (1,30): * g). and fooling the alternate Mp.e, model itself. Here, by "alternate" we mean that for an L, attack, the prediction is made by the Mp.s, model, where p. q E {1, oo of g. We provide illustration of the offe-oof in Figure 1b and present the formal proof in Appendix
5 TRAINING AND INFERENCE
Having motivated PROTECTOR through toy-task in Section 4 we now scale the approach to deep neural networks for common image classification benchmarks. Specifically, following prior work on defending against multiple perturbation types, we evaluate on MNIST (LeCun et al., 2010) and CIFAR-10 (Krizhevsky 2012) datasets. Now, we discuss the training details, a strong adaptive white-box attack against PROTECTOR, and our inference procedure against such attacks.
5.1 TRAINING
To train our perturbation classifier Cados we create a dataset that includes adversarial examples of different perturbation types. Specifically, we perform &1, l2, foo PGD attacks (Madry et al. 2018)
5

---

Under review as a conference paper at ICLR 2021
against each of the two individual M, models used in PROTECTOR. Thus the size of our dataset is 6 times that of the original MNIST and CIFARIO datasets respectively. For the MNIST dataset, we use the M2, 2o models in PROTECTOR, and we use M1 Mo models for CIFARIO. The choice is made based on the robustness of { 22, Mi models against the {f1, fz) attacks respectively, as will be depicted in Table 2 As discussed in Section R] to assign the ground truth label for training the perturbation classifier (Cade), we find that it is sufficient to assign the same label to & and & attacks. In other words, Code performs binary classification between f attacks and &oo attacks.
In contrast with prior defenses against multiple perturbation types (Tramèr & Boneh 2019 Maini al. 2020), which require adversarial training, we find that it is sufficient to train our PROTECTOR pipeline over static dataset (constructed as mentioned above) to achieve high robustness. Therefore, the training of our perturbation classifier is fast and stable. Specifically, using single P100 GPU, our perturbation classifier can be trained within 5 minutes on MNIST, and within an hour on CIFAR-10. On the other hand, training satt--of-the-an models robust to single perturbation type require up to days to train the same amount of GPU power, and existing defenses against multiple perturbation types take thrice as long as the training time for a model robust to a single perturbation type.
A key advantage of PROTECTOR'S 's design is that it can build upon existing defenses against individual perturbation types. Specifically, we leverage the adversarially trained models developed in prior work (Zhang al., [211 Carmon al. 2019) as Mp models in our pipeline, and the CNN architecture of Cade i8 also similar to a single Mp model. More details are deferred to Appendix D
5.2 ADAPTIVE ATTACKS AGAINST THE PROTECTOR PIPELINE
To generate adversarial examples against PROTECTOR, the most straightforward approach is to generate the adversarial perturbation to optimize Equation B using existing attack algorithms. Since the final prediction of the pipeline only depends on single M, model, the pipeline does not allow gradient flow across the two levels, and thus makes it difficult for gradient-based adversaries to attack PROTECTOR. Therefore, besides this standard adaptive attack, our evaluation, we also consider a stronger adaptive adversary, which utilizes a combination of the predictions from each individual second-level Mp models, rather than only utilizing the predictions from a single Mp model with p argmax (z) alone. Specifically, we modify fo( in Equation 3
as follows:
softmax(Caad
fo(x)
Σ cp (.-Mp()) PES
(4)
where cp denotes the probability of the input being classified as the perturbation type p by Cadu- We also experiment with other strategies of aggregating the predictions of different components, e.g., tuning dyper-parameters to balance among attacking Codv and each Mp model, but these alternative methods do not perform better. Note that Equation 4 is only used for the purpose of generating adversarial examples and performing gradient-based attack optimization. For consistency throughout the paper, we still use Equation T to compute the model prediction at inference (final bowward-propagale We do not see any significant performance advantages of either choice at inference time, and briefly report comparison on two attacks in Appendix H.4
5.3 INFERENCE PROCEDURE AGAINST ADAPTIVE ADVERSARIES
Though training the perturbation classifier on static dataset is sufficient to achieve robustness using existing attack approaches, we observe that the accuracy drops when PROTECTOR is presented with the stronger adaptive attacks discussed in Section 5.2 To improve the model robustness against such adversaries, we add random noise to the input before feeding it into PROTECTOR at the test time. While Hu et al. (209)) suggest that adding random noise does not help defend against adversarial inputs, it is the unique exhibition of the trade-off described in Theorem 2 that adversarial attacks against PROTECTOR, on the contrary, are highly likely to fail when added with random noise. Intuitively, the trade-off between fooling the two stages of PROTECTOR confines the adversary in very small region for generating successful adversarial attacks.
Consider the illustrative example in Figure B where the input with the true label y 0 is subjected to an loo attack. We assume that the Mac.o model is a perfect classi- fier for inputs within fixed 6o ball. The dotted line shows the decision boundary for

---

Under review as a conference paper at ICLR 2021
the perturbation classifier Codu. which correctly classifies inputs subjected to Lo pertur- bations 8" as &o attacks (green), but can misclassify samples with smaller perturbations.
When the adversary adds a large perturbation 8", the prediction of M1 for the resulted input x" becomes wrong, but the perturbation classifier also categorizes it as an Mo attack, thus the final prediction of PROTECTOR is still correct since it will be produced by Mo.. model in- stead. On the other hand, when the adversary adds small perturbation 8' fool the perturba- tion classifier, adding small amount of random noise can recover the correct prediction with high probability. Note that every point the boundary the noise region (yellow circle) is correctly classified by the pipeline. In this way, adding random noise exploits an adversar- ial trade-off for PROTECTOR achieve high accuracy against adversarial examples, in the ab- sence of adversarial training. In our implemen- tation, we sample random noise ~ (O, and add E2 2/|2/2 the model input.
Adding small random noise recovers correct label prediction
Class
Class
M
small
largo 8
Class
Mi
Clessiteg
Perturation
Class
Baandar
Figure 3: Illustration of effect of random noise for generating adversarial examples. Note that notion of small and large perturbations is only used to illustrate the scenario in Figure 3 and in general none of the perturbation regions subsumes the other.
6 EXPERIMENTS
In this section, we present our experiments on MNIST and CIFAR-10 datasets. We will discuss the results for both the perturbation classifier Codv alone, and the entire PROTECTOR pipeline.
6.1 EXPERIMENTAL. SETUP
We compare PROTECTOR with the state-of-the-art defenses against multiple perturhation types, which consider the union of f2, foe adversaries (Tramèr & Boneh 2019 Maini et al. 2020). For Tramèr & Bonch (201)), we compare two variants of adversarial training: (I) the MAX approach, where for each image, among different perturbation types, the adversarial sample that leads the maximum increase of the model loss is augmented into the training set; (2) the AVG approach, where adversarial examples for all perturbation types are included for training. We also evaluate MSD algorithm proposed by Maini et al. (2020), which modifies the standard PGD attack to incorporate the union of multiple perturbation types within the steepest decent itself. addition, we also evaluate M1, M2. Mc models trained with &,, f2, for perturbations separately, as described in Appendix D
Baselines.
Attack evaluation. We evaluate our methods with the strongest attacks the adversarial learning literature, and with adaptive attacks specifically designed for PROTECTOR (Section 5.2). First, we utilize a comprehensive suite of both gradient- based and gradient- free attacks from the Foolbox library (Rauber al. (017)). Further, also evaluate method against the Auto/Atack library from Croce & Hein (2020c), which achieves the state-of-art adversarial error rates against multiple recently published models. In line with prior work (Tramer & Boneh 2019 Maini al. 2020). the radius of
the {L1. E2, foe) perturbation regions is {10, 0.3) for the MNIST dataset and {12. 0.5, 0.03] for the CIFARIO dataset. We present the full details of attack algorithms Appendix F
Following prior work (Tramèr & Bonch 2019 Maini et al. 2020), for both MNIST and CIFAR- 10,
we evaluate the models on adversarial examples generated from the first 1000 images of the set. Our main evaluation metric is the accuracy on all attacks, which means that for an input image, if any of the attack algorithm in our suite could successfully fool the model, then the input is failure case.
6.2 EMPIRICAL PERTURBATION OVERLAP AND CHOICE OF Ep
While we justify the choice of perturbation sizes in our theoretical proofs in Appendix B.4 and C.2 in this section we demonstrate the empirical agreement of the choices of perturbation sizes make
7

---

Under review as a conference paper at ICLR 2021
Table 1: Studying the empirical overlap lp.c, attack perturbations in different bg.eg regions for
(x) ) = (12, 0.5, 0.03). Each column (a) MNIST (c1, 2, (x) 200, 2.0, 0.3); (b) CIFAR-I0 (<1, f2, c2,
represents the range (min max) of by norm for perturbations generated using l PGD attack.
Attack
MNIST
CIFARIO
Lo 0.3
1/ < 2.0
< 10
xx < 0.03
12 0.5
PGD toc PGD &
< 0.3
(3.67 6.05)
(54.8-
140.9) 140.9)
0.03
(1.33 11:3-1-00 1.59)
(62.7- 85.5)
(0.40 0.86)
2.0
(1..2-24.1)
(0.037-0.10)
< 0.05
(15.4-
Sparse &
(0.70 1.0)
(2.08 2.92)
S 10.0
(0.27 0.77)
(1.32 1.88)
S 12.0
Table 2: Worst-case accuracies against different lp attacks: (a) MNIST; (b) CIFAR-10. Ours represents and Ours* is the standard setting.
PROTECTOR against the adaptive attack strategy (Section 5.2)
MNIST
Mx
M2
M1
MAX
AVG
MSD
Ours
Ours
Clean Accuracy
99. %
99.2%
99.0%
98.6%
98.1%
98.3%
98.7 7%
98.7%
foo attacks (c 0.3)
90.0%
2.7%
0.0%
38.8%
57.8%
63.5%
80.1%
87.3%
l2 attacks (c 2.0)
7.6%
72.1%
47.7%
58.2%
56.6%
65.4%
67.2%
77.1%
& attacks (c 10)
10.8%
69.6%
77.3%
41.1%
36.8%
62.7%
65.7%
72.4%
All Attacks
6.0%
2.7%
0.0%
28.6%
32.4%
56.9%
63.8%
68.5%
(a)
CIFAR-I0
Mo
M2
M
MAX
AVG
MSD
Ours
Ours
Clean accuracy
93.3%
91.2%
89.3%
81.0%
84.6%
81.1%
90.8%
90.8%
Lo attacks (e 0.03)
59.3%
34.8%
35.1%
35.0%
39.5%
43.7%
57.2%
62.1%
l2 attacks (e 0.5)
64.4%
77.2%
71.5%
61.8%
65.0%
64.5%
66.8%
67.1%
l attacks (e = 12)
18.8%
34.7%
55.0%
34.5%
54.1%
51.5%
55.9%
56.0%
All attacks
18.8%
29.2%
35.0%
27.6%
38.6%
43.2%
52.1 %
54.7 %
(b)
for our results on MNIST and CIFARIO datasets. To measure how often adversarial perturbations of different attacks overlap. we empirically quantify the overlapping regions by attacking a benign model with PGD attacks. In Table I we report the range of the norm of perturbations in the alternate perturbation region for any given attack type. The observed overlap is exactly 0% in all cases and the observation is consistent across MNIST and CIFARIO 10 datasets. A similar analysis on attacking PROTECTOR can be found Appendix G
6.3 PERTURBATION TYPE CLASSIFICATION RESULTS OF Cadv
To examine the performance of the perturbation type classification, we evaluate Cado on a dataset of adversarial examples, which are generated against the six models we use as the baseline defenses in our experiments. Note that Codv is only trained on adversarial examples against the two Mp models that are part of PROTECTOR. We observe that Cade transfers well across the board. First, Cade generalizes to adversarial examples against new models; i.c., it preserves high accuracy, even if the adversarial examples are generated against models that are unseen for Cado during training. Further, Gado also generalizes to new attack algorithms. As discussed in Section 5. we only include PGD adversarial examples in our training set for Cado- However, on adversarial examples generated by the AutoAttack library, the classification accuracy of Cads still holds up. In particular, the accuracy is 95% across all the individual test sets created. These results suggest two important findings that validate results in Theorem That is, independent of (a) the model to be attacked; and (b) the algorithm for generating the optimal adversarial perturbation, the optimal adversarial images for a given fp region follow similar distributions. We present the full results in Appendix H.1
6.4 RESULTS OF THE PROTECTOR PIPELINE
Overall results. In Table we summarize the worst-case performance against all attacks within given perturbation type for MNIST and CIFAR-10 datasets. In particular, "Ours' denotes the robustness of PROTECTOR against the adaptive attacks described in Section 5.2 and *Ours** denotes the robustness of PROTECTOR against standard attacks based Equation The adaptive strategy
8

---

Under review as a conference paper at ICLR 2021
Table 3: Effect of different design choices on the CIFAR-IO dataset against PGD-based attacks.
PROTECTOR(1) means the number of specialized robust predictors Mp is n in the pipeline.
Without Noise
With Noise
PROTECTOR(2) PROTECTOR(3)
PROTECTOR(2)
PROTECTOR(3)
Clean accuracy
90.8%
92.1%
90.8%
92.2%
APGD Eno (e 0.03)
54.7%
50.7%
64.8%
56.3%
APGD &g (c 0.5)
65.0%
64.3%
68.8%
69.2%
Sparse-PCr P-D---GDDLG & (c = 12)
48.7%
42.5%
55.9%
52.3%
effectively reduces the overall accuracy of PROTECTOR by 2-5%, showing that incorporating the gradient and prediction information of all second-level predictors results stronger attack.
Despite that we evaluate PROTECTOR against a stronger adaptive adversary, in terms of the all attacks accuracy, PROTECTOR still outperforms all baselines by 6.9% on MNIST, and 8.9% on CIFAR-10. Compared to the previous state-of-the-art defense against multiple perturbation types (MSD), the accuracy gain on loo attacks is especially notable, i.e., greater than 15%. particular, if we compare the performance gain on each individual attack algorithm, as shown in Appendix H.2 and H.3 for MNIST and CIFAR-10 respectively, the improvement also significant, with an average accuracy increase of 15.5% on MNIST, and 14.2% on CIFAR-10. These results demonstrate that PROTECTOR considerably mitigates the trade-off in accuracy against individual attack types.
PROTECTOR retains high accuracy on benign images, as opposed to past defenses that have to sacrifice the benign accuracy for the robustness on multiple perturbation types. In particular, the clean accuracy of PROTECTOR is over 6% higher than such basclines on CIFAR-10, and the accuracy is similar to that Mp models trained for a single perturbation type.
The effect of noise. As discussed in Section 5.3 though adding random noise is not required to defend against standard attacks, it is helpful in defending against the stronger adaptive adversary against our pipeline. Specifically, in Table 3] we present the results adversarial examples generated by PGD-based algorithms, which are amongst the strongest gradient-based attacks the literature. We observe consistent improvement among all attacks, increasing the accuracy by up 10%.
Different number of second-level Mp predictors. We also evaluate our PROTECTOR approach with three second-level predictors, i.e., M1, M2 and Mx,, and we present the results in Table 3 this alternative design considerably reduces the overall accuracy of the pipeline model. We hypothesize that this happens because the Mi model is already reasonably robust against the & attacks, as shown in Table 2b. However, having both Mj and M2 models allows adaptive adversaries to find larger regions for tooling both Cade and Mp. thus hurts the overall performance against adaptive adversaries.
CONCLUSION
In this work, we propose PROTECTOR, which performs perturbation type categorization towards achieving robustness against the union of multiple perturbation types. Based on a simplified problem setup, theoretically, we demonstrate that adversarial inputs of different attack types naturally have different distributions and can be separated. We further elaborate the existence of a natural tension for any adversary trying to fool our model between fooling the attack classifier and the specialized robust predictors. Our empirical results on MNIST and CIFAR-10 datasets complement our theoretical analysis. In particular, by posing another adversarial trade-off through the effect of random noise, our PROTECTOR pipeline outperforms existing defenses against multiple É, attacks by over 5%.
Our work serves as stepping stone towards the goal of universal adversarial robustness, by dissecting various adversarial objectives into individually solvable pieces and combing them via PROTECTOR. Our study opens up various exciting future directions. including the problem of perturbation categorization, extending our approach to defend attacks beyond 4, adversarial examples, and defining sub-classes of perturbation types further improve the overall adversarial robustness.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Maksym Andriushchenko, Francesco Croce, Nicolas Flammarion, and Matthias Hein. Square attack: query-efficient black-box adversarial attack via random search. In European Conference on Computer Vision, 2020.
Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples. In International Conference on Machine Learning, 2018.
Anand Bhattad, Min Jin Chong, Kaizhao Liang, Bo Li, and D. A. Forsyth. Unrestricted adversarial examples via semantic manipulation. In International Conference on Learning Representations, 2020. URL URL
Wieland Brendel, Jonas Rauber, and Matthias Bethge. Decision-based adversarial attacks: Reliable attacks against black-box machine learning models. International Conference on Learning Representations, 2018.
Buckman, Aurko Roy, Colin Raffel, and Ian Goodfellow. Thermometer encoding: One hot way to resist adversarial examples. In ICLR, 2018.
Nicholas Carlini and David Wagner. Adversarial examples are not easily detected: Bypassing ten detection methods. In Proceedings of the 10th ACM Workshop Artificial Intelligence and Security, pp. 3-14, 2017a.
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In Security and Privacy (SP), 20/7 IEEE Symposium on, pp. 39-57. IEEF, 2017b.
Yair Carmon, Aditi Raghunathan, Ludwig Schmidt, John C Duchi, and Percy Liang. Unlabeled data improves adversarial robustness. In Advances Neural Information Processing Systems, pp. 11190-11201, 2019.
Alessandro Cennamo, Ido Freeman, and Anton Kummert. A statistical defense approach for detecting adversarial examples. In Proceedings of the 2020 International Conference on Pottern Recognition and Intelligent Systems, pp. 1-7, 2020.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. volume 97 of Proceedings of Machine Learning Research, pp. 1310-1320, Long Beach, California, USA, 09-15 Jun 2019. PMLR.
Francesco Croce and Matthias Hein. Provable robustness against all adversarial (, 4y-perturbations for 2 1. International Conference on Learning Representations, 2020a. URL https //openreview .nt. fottt///ormmmmddkkk.._.
ySYPB
Francesco Croce and Matthias Hein. Minimally distorted adversarial examples with fast adaptive boundary attack. In International Conference on Machine Learning, 2020b.
Francesco Croce and Matthias Hein. Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-fre attacks. In ICML, 2020c.
Yinpeng Dong, Fangzhou Liao, Tianyu Pang, Hang Su, Jun Zhu, Xiaolin Hu, and Jianguo Li. Boosting adversarial attacks with momentum. In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2018.
Reuben Feinman, Ryan Curtin, Saurabh Shintre, and Andrew B Gardner. Detecting adversarial samples from artifacts. arXiv preprint
2017.
Gil Fidel, Ron Bitton, and Asaf Shabtai. When explainability meets adversarial learning: Detecting 2019.
adversarial examples using shap signatures. arXiv preprint
Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In International Conference on Learning Representations, 2015.
10

---

Under review as a conference paper at ICLR 2021
Chuan Guo, Mayank Rana, Moustapha Cisse, and Laurens van der Maaten. Countering adversarial images using input transformations. In International Conference on Learning Representations. 2018.
Warren He, James Wei, Xinyun Chen, Nicholas Carlini, and Dawn Song. Adversarial example defense: Ensembles of weak defenses are not strong. In 1/th {USENIX] Workshop on Offensive Technologies ((WOOT) 17), 2017.
Dan Hendrycks and Thomas Dietterich. Benchmarking neural network robustness to common corruptions and perturbations. In International Conference on Learning Representations, 2019.
Dan Hendrycks, Kevin Zhao, Steven Basart, Jacob Steinhardt, and Dawn Song. Natural adversarial examples. arXiv preprint arXiv:1907.0711 0000000077744 2019.
Shengyuan Hu, Tao Yu, Chuan Guo, Wei-Lun Chao, and Kilian Q Weinberger. A new defense against adversarial images: Turning weakness into a strength. In Advances in Neural Information Processing Systems. pp. 1635-1646, 2019.
Andrew Ilyas, Shibani Santurkar, Dimitris Tsipras, Logan Engstrom, Brandon Tran, and Aleksander Madry. Adversarial examples are not bugs, they are features. In Advances in Neural Information Processing Systems, pp. 125-136, 2019.
Daniel Kang, Yi Sun, Dan Hendrycks, Tom Brown, and Jacob Steinhardt. Testing robustness against unforeseen adversaries. arXiv preprint TrXiv:1908.040 2019.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2015.
Alex Krizhevsky. Learning multiple layers of features from tiny images. University of Toronto, 2012.
Alexey Kurakin, Ian Goodfellow, and Samy Bengio. Adversarial examples in the physical world. ICLR Workshop, 2017. URL URthhttss://axxii
02533
Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. ATT Labs [Online]. Available: http::/yann.lecuu www.nn.eeec..c.o wwwp://.ww...../eee/ii/iicc. wwtpw////////iisttt.tmmmmm
2, 2010.
Kimin Lee, Kibok Lee, Honglak Lee, and Jinwoo Shin. A simple unified framework for detecting out-of-distribution samples and adversarial attacks. In Advances in Neural Information Processing Systems, pp- 7167-7177, 2018.
Xingjun Ma Bo Li, Yisen Wang, Sarah M Erfani, Sudanthi Wijewickrema, Grant Schoenebeck, Dawn Song, Michael E Houle, and James Bailey. Characterizing adversarial subspaces using local intrinsic dimensionality. 2018
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference Learning Representations, 2018
Pratyush Maini, Eric Wong, and J. Zico Kolter. Adversarial robustness against the union of multiple perturbation models. In International Conference on Machine Learning, 2020.
Seyed-Mohsee Moosavi-Dezfoole Alhussein Fawzi, and Pascal Frossard. Deepfool: simple and accurate method fool deep neural networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2574-2582. 2016.
Nicolas Papernot, Patrick McDaniel, Xi Wu, Somesh Jha, and Ananthram Swami. Distillation defense to adversarial perturbations against deep neural networks. In 2016 IEEE Symposium on Security and Privacy (SP), pp. 582-597. IEEE, 2016.
Jonas Rauber, Wieland Brendel, and Matthias Bethge. 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. URL http:/ arxxiv. org abss/
1707. 04131
11

---

Under review as a conference paper at ICLR 2021
Leslie Rice, Erie Wong, and Zico Kolter. Overfitting in adversarially robust deep learning. arXiv preprint arXiv:2002.1156% 2020.
Jérôme Rony, Luiz G Hafemann, Luiz S Oliveira, Ismail Ben Ayed, Robert Sabourin, and Eric Granger. Decoupling direction and norm for efficient gradient-based 12 adversarial attacks and defenses. In Proceedings of the IEEE Conference on Computer Vision and Puttern Recognition, pp. 4322 4330, 2019.
Lukas Schott, Jonas Rauber, Matthias Bethge, and Wieland Brendel. Towards the first adversarially robust neural network model on mnist. In International Conference Learning Representations, 2018.
Leslie Smith. A disciplined approach to neural network hyper-parameters: Part 1 l-learning rate, batch size, momentum, and weight decay. arXiv preprint arXiv:/803.099 2018.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv:1312.6199, 2013.
P. Tabacof and E. Valle. Exploring the space of adversarial images. In 2016 International Joint Conference on Neural Networks (IJCNV). pp. 426-433, 2016.
Florian Tramèr and Dan Boneh. Adversarial training and robustness for multiple perturbations. In Advances in Neural Information Processing Systems, pp.
2019.
Florian Tramèr, Alexey Kurakin, Nicolas Papernot, Ian Goodfellow, Dan Boneh, and Patrick Mc- Daniel. Ensemble adversarial training: Attacks and defenses. In International Conference on Learning Representations, 2018.
Florian Tramer, Nicholas Carlini, Wieland Brendel, and Aleksander Madry. On adaptive attacks to adversarial example defenses. arXiv preprint (xXiv:2022.08377 2020.
Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry. Ro- bustness may be at odds with accuracy. In International Conference on Learning Representations, 2018.
Eric Wong, Leslie Rice, and Zico Kolter. Fast better than free: Revisiting adversarial training. In International Conference on Learning Representations, 2020.
Dong Yin, Raphael Gontijo Lopes, Jon Shlens, Ekin Dogus Cubuk, and Justin Gilmer. A fourier perspective on model robustness in computer vision. Advances Neural Information Processing Systems, pp. 12276-33286 2019a.
Xuwang Yin, Soheil Kolouri, and Gustavo K Rohde. Adversarial example detection and classification with asymmetrical adversarial training. arXiv preprint arXiv: 1905. 1475, 2019b.
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. arXiv preprint 165. 2016.
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan. Theoretically principled trade-off between robustness and accuracy. In International Conference on Machine Learning, pp. 7472-7482, 2019.
12

---

Under review as a conference paper at ICLR 2021
A PROBLEM SETTING: THEORETICAL ANALYSIS
In this section, we formally define the problem setting and motivate the distinctions made with respect to the problem studied by [yyas al. (019). The classification problem consists of two tasks: (1) Predicting the correct class label of an adversarially perturbed (or benign) image using adversarially robust classifier Mpi and (2) Predicting the type of adversarial perturbation that the input image was subjected to, using attack classifier Codu-
Setup We consider the data to consist of inputs to be sampled from two multi-variate Gaussian distributions such that the input-label pairs (x.y) can be described as:
u.o.r {-1,41},
y
(5)
xo~N(ya, 31,...,3d hid (m,,
where the input x Nyu, E) R(d+1); a/va for some positive constant as μ [o. E (++++) and Σ = o'I R+((+1)((d+1) We can assume without loss of gen- erality, that the mean for the two distributions has the same absolute value, since for any two distributions with mean (1, P2, M2, we can translate the origin to Mu+"2, This setting demonstrates the distinction between an input feature Zg that is strongly correlated with the input label and weakly correlated features that are normally distributed (independently) with mean yn and variance o² each. We adapt this setting from llyas et al. (2199) who used a stochastic feature To = with probability opposed to normally distributed imput feature in case. All our findings hold in the other setting as well, however, the chosen setting better represents true data distribution, with some features that are strongly correlated to the input label, while others that have only weak correlation.
B SEPARABILITY OF PERTURBATION TYPES (THEOREM 1
In this section, our goal is to evaluate whether the optimal perturbation confined within different ép balls have different distributions and whether they are separable. We do so by developing an error bound on the maximum error in classification of the perturbation types. The goal of the adversary is to fool a standard (non-robust) classifier M. Cadv aims to predict the perturbation type based on only viewing the adversarial image, and not the delta perturbation.
First, in Appendix B. we define a binary Gaussian classifier that is trained on the given task. Given the weights of the binary classifier, we then identify the optimal adversarial perturbation for each of the f,, l2, foo attack types in Appendix [B.2] In Appendix B.3 we define the difference between the adversarial input distribution for different &p balls. Finally, we calculate the error in classification of these adversarial input types in Appendix B. to conclude the proof of Theorem |
B. BINARY GAUSSIAN CLASSIFIER
We assume for the purposes of this work that we have enough input data to able to empirically estimate the parameters μ. of the input distribution via sustained sampling. The multivariate Gaussian representing the input data is given by:
(-1(xx ----1)" x -wnl)): Vy E (-1,1}
p(aly- = vt) ((2m) Σ
exp
(6)
We want find p(u y )) Vy (-1,+1), From Bayesian Decision Theory, the optimal decision rule for separating the two distributions is given by:
ply = 1)p(2)y 1) 5 plu = 11)p(a// = -1)
ply = 1)p(zly=1) "ー= plu = -1)p(xly = -1)
Therefore, for Gaussian Distributions Nmm, N Ez), we have:
13

---

Under review as a conference paper at ICLR 2021
0 < I T Ax 2b +
y=1
A = Σn¹ -E
(8)
b ΣΙ H1 Σσ μ12
Σ
log plu = 1)
1l Dj μ1
112 Σg U2
log
Σ2
plu 1)
given by: in
Substituting
6 and
we find that the optimal Bayesian decision rule for our problem is
(9)
x
1
which means that the label for the input can be predicted with the information of the sign of x: alone. We can define the parameters W Rd41 of the optimal binary Gaussian classifier M such that [ as:
Wo a M (x) = W
W, a
vi (1........
V2
V2d
(10)
B.2 OPTIMAL ADVERSARIAL PERTURBATION AGAINST MW
Now, caleulate the optimal perturbation 8 that is added input by adversary in order to fool our model. For the purpose of this analysis, we only aim to fool a model trained on the standard classification metric discussed in Section (and adversarially robust model). The parameters of our model are defined in (10).
The objective of any adversary ô A is to maximize the loss of the label classifier W We assume that the classification loss is given by -y x MW (x + +)). The object of the adversary is to find 6* such that:
f(x v; ) y M W (x + 8 ye W
8"
arg max ((x + 0,y, MW)
(II)
DEA
arg max 8EA
y( + 8) W arg y6 W
We will now calculate the optimal perturbation in the f, balls Vp {1, 00). For the following analyses, we restrict the perturbation region A to the corresponding lp ball of radius 62, 6o0) respectively. We also note that the optimal perturbation exists at the boundary of the respective Ep balls. Therefore, the constraint can be re- re-written as
8" arg max yo
W
(12)
|
use following properties in the individual treatment of & balls:
|| =
Σ
1
(13)
1-1
|8, p-1
051151|p =
Σ
1
=115,11
sgn =
sgn(5,)
||6||p
14

---

Under review as a conference paper at ICLR 2021
p = Making of langrange multipliers to solve 12 we have:
Vo(-6"E E AV (1 2
(14)
w = A V
Combining the results from
13) and replacing 5 with 82 we obtain
|02
W 11112212
sgn(62)
|2211
(15)
W
82 = 62
= 62 W
||
p = 00
Recall that the optimal perturbation is given by:
8* arg
max
yo
W
|6
d
(16)
arg
max
8, W:
[óllse =0
k=0
Since |0 = Coo, we know that max; |6:| co.
Therefore 16) is maximized when each
yC sgn W, Vi E (0....,d d). Further, since the weight matrix only contains non-negative
elements (a is a positive constant), we can conclude that the optimal perturbation is given by:
8x0 = - 1
(17)
p=1 We attempt an analytical solution for the optimal perturbation 61 Recall that the optimal perturbation is given by
8 = max
-
8.W;
||||
1=61 i=1
d
arg max
-yd0 Wo y
8, W.
(18)
[=]]
d
6 aK
arg max -0on
||
/2
2d
Since ||ō]] =
18 is maximized when:
6g ye sgn(a) = yc 6, = Vi (1...d)
(19)
Combining the results From the preceding discussion, it may be noted that the new distribution of inputs within a given label changes by a different amount depending on the perturbation type. Moreover, if the mean and variance of the distribution of given label are known (which implies that the corresponding true data label is also known), the optimal perturbation is independent of the input itself, and only dependent on the respective class statistics (Note that the input still important in order to understand the true class).
B.3 PERTURBATION CLASSIFICATION BY Cadv
In this section, we aim to verify if is possible to accurately separate the optimal adversarial inputs crafted within different Ep balls. For the purposes of this discussion, only consider the problem of classifying perturbation types into & and lxo. but the same analysis may also be extended more generally any number of perturbation types.
15

---

Under review as a conference paper at ICLR 2021
We will consider the problem of classifying the correct attack label for inputs from true class y 1 for this discussion. Note that the original distribution:
Xtrue Ny Σ)
Since the perturbation value 6p is fixed for all inputs corresponding to particular label, the new distribution of perturbed inputs X, and X in case of & and foc attacks respectively (for = 1) is given by:
X1 ~ NN ō1, Σ)
(20)
Xx ~ Ni 8oo: Σ)
We now try to evaluate the conditions under which we can separate the two Gaussian distributions with an acceptable worst-case error.
B.4 CALCULATING A BOUND ON THE ERROR
Classification Error A classification error occurs if data vector belongs one class but falls in the decision region of the other class. That is in (7) the decision rule indicates the incorrect class. (This can be understood through the existence of outliers)
/
P.
P(ertor)z)p(a))dzz
(21)
f min ppy
Perturbation Size We set the radius of the loo ball, 1) and the radius of the E ball, We further extend the discussion about suitable perturbation sizes in Appendix C.2 These values ensure that the Loo adversary the expected value the adversarial input to less than 0 (E(z; + (1) adversary can make the strongly correlated feature Ty meaningless by changing its expected value to less than 0 (E Do + (0))). However, neither of the two adversaries can flip all the features together.
make all the weakly correlated labels meaningless by changing
0), while the &
Translating the axes We can translate the axis of reference by (- - --- (fut((x)) and define (61 (51-8 such that
Made
X1 (Mados Σ)
(22)
X ~ (- E)
We can once again combine this with the simplified Bayesian model in obtain the classification rule given by:
x 0
Hadv
p=1
(23)
Combining the optimal perturbation definitions in 17 and (99) that Madv { - [- foo Cool. We can further substitute 61 and 6oc = 17 vd' No- tice that (i) > 0 Vi > 0. Without loss generality, to simplify further discussion we flip the coordinates of Ho: since all dimensions independent of each other. Therefore,
Rado 2/d
Va 1,
Consider a new variable such that:
x_ =
(x (adv))
(24)
Vā
vd
t=1
since each v,Vi is independently distributed, the feature xy NiHu where
16

---

Under review as a conference paper at ICLR 2021
a
Ns
a
Vd
+
Vd
Vd
a
20
Vd
(25)
0.
1+ d - 2 vd
Σ d
i=1
1
0²
2 d - 2
Vd
Therefore, the problem simplifies caleulating the probability that the meta-variable x; > For > 10 and d > 1, we have in the z-table, 10:
P. 10 10-24
(26)
which suggests that the distributions are significantly distinct and can be easily separated. This concludes the proof for Theorem !
Note: We can extend the same analysis to other ép balls as well, but we consider the case of l and Eo for simplicity.
C ROBUSTNESS OF THE PROTECTOR PIPELINE (THEOREM
In the previous section, we show that it is indeed possible to distinguish between the distribution of inputs of a given class that were subjected to l and foo perturbations over a standard classifier. Now, we aim to develop further understanding of the robustness of our two-stage pipeline in dynamic attack setting with multiple labels to distinguish among. The first stage is a preliminary classifier Gado that classifies the perturbation type and the second stage consists of multiple models M, that were specifically trained to be robust to perturbations to the input within the corresponding lp norm.
First, in Appendix C.I caleulate the optimal weights for binary Gaussian classifier Mp. trained on dataset D to be robust to adversaries within the Ep ball Vp E [1, xo). Based on the weights of the individual model, the alternate model with high probability. Here, by 'alternate' we mean that for an by attack, the prediction should be made by the Mp.c, model,where p. q E (o, o q. In Appendix C.3 we calculate the robustness of individual M, models to Pp adversaries, given the perturbation size 6p as defined in Appendix [C.2 In Appendix C.4 we analyze the modified distributions of the perturbed inputs after different é, attacks. Based on this analysis, we construct simple decision rule for the perturbation classifier Cadv. Finally, in Appendix C.5 we determine the perturbation induced by the worst-case adversary that has complete knowledge of both Codv and Mp.c, Vp {1, oc). We show how there exists a trade-off between fooling the perturbation classifier (to allow the alternate Mp.ep model to make the final prediction), and fooling the alternate Mp.ep model itself.
fix the perturbation size Ep be only as large, as required to fool
Perturbation Size We set the radius of the fox ball, 6oo 7 foe and the radius of the & ball, 9 = a + Ç1, where Sp are some small positive constants that we calculate Appendix C.2 These values ensure that the too adversary can make all the weakly correlated labels meaningless by changing the expected value of the adversarial input to less than 0 (Eix; + (i)] Vi > 0), while the l, adversary can make the strongly correlated feature Tg meaningless by changing its expected value to less than 0 (E Io + 8g (0))). However, neither of the two adversaries can flip all the features together. The exact values of Sp determine the exact success probability of the attacks. We defer this calculation to later when we have calculated the weights of the models M,. For the following discussion, it may be assumed that S, Vp (1,
17

---

Under review as a conference paper at ICLR 2021
C.I BINARY GAUSSIAN CLASSIFIER Mp
Extending the discussion in Appendix B.I, we now examine the learned weights of binary Gaussian classifier Mp that is trained to be robust against perturbations within the corresponding l ball of radius Ep. The optimization equation for the classifier can be formulated as follows:
min (-yx² W] 2
(27)
where is tuned in order to make the l norm of the optimal weight distribution. || = 1. Following the symmetry argument in Lemma D.1 Tsipras et al. (2018) we extend for the binary Gaussian classifier that:
W Wj WM Vi,j E (1....,d) d)
(28)
We deal with the cases pertaining to E foo, 1 in this section. For both the cases, we consider existential solutions for the classifier M, simplify the discussion. This gives lower bounds on the performance of the optimal robust classifier. The robust objective under adversarial training can be defined as:
d Σ
min max E W PStp
Wo (oo +00 + WM
(x
6,)
+ 1
1=1
min {
-1 Woo (Wo + WM Vi )
1
w|
max E -y Sr
Woon
WM
8;
(29)
Further, since the constraint only ensures that 1| 1, we can simplify the optimization equation by substituting Wo v1 /1-d d WM² as follows.
( -1 a d. WM² + d W a
d - 60 1o W + WM
min WM
+
E S
max
Σ 8
(30)
p= As discussed in 17 the optimal perturbation & is given by - 1. The optimization
equation is simplified to:
(c (co- d. WM + dx WM (co a
(0-ma)
min WM
(31)
Recall that 6oo va + Soo- To simplify the following discussion we use the weights of a classifier trained to be robust against perturbations within the foc ball of radius 6o0 J.. The optimal solution then given by:
lim WM =0
(32)
Therefore, the classifier weights are given by W W. W....,, Wa [1,0,.... 0). We also show later in Appendix C.3 that the model achieves greater than 99% accuracy against Eo adversaries for the chosen values of Coo-
= We consider analytical solution to yield optimal weights for this case. Recall from 19
that the optimal perturbation 6, depends on the weight distribution of the classifier. Therefore, W, WM M the optimization equation can be simplified to
min W
Wolf - a) - d
M Vd
a
+ A/
(33)
18

---

Under review as a conference paper at ICLR 2021
and if WM Wo
min Woa Wm (Vda-sj) $1) 2 w 1
(34)
Recall that 6 = a + S1. Once again to simplify the discussion that follows we will lower bound the robust accuracy of the classifier M1 by considering the optimal solution when zelai 0. The optimal solution is then given by:
lim WM =1 5-
(35)
For the robust classifier M1, the weights W = Wo WI,... W -
V7' Vi Val While
this may not be the optimal solution for all values of S1, we are only interested in lower bound on the final accuracy and the classifier described by weights W simplifies the discussion hereon. We also show later in Appendix (e. C.3 that the model achieves greater than 99% accuracy against l adversaries for the chosen values of C1.
C.2 PERTURBATION SIZES FOR FOOLING Mp MODELS
Now that we exactly know the weights of the learned robust classifiers M1 and Moc, we can move towards calculating values Ç1 and Soo for the exact radius of the perturbation regions for the & and Lo metrics. We set the radii of these regions in such a way that an l adversary can fool the model Mo with probability 98% (corresponding similarly, the success of to attacks against the M₁ model ~ 98%.
2 in the z-table for normal distributions), and
Let P pr.pa represent the probability that model Mn, correctly classifies adversarial input in the byz region. For pl oc and p2 = 1,
Poe PanN(yn 1y Moo (z 81) 0]
-PaNN(yp /y/ (r + 01) T T > 0]
2 Pa>N((, [20 =1]
-
21 a
(1
(36)
0
0
0
Ç1 20
+ 20
To simplify the discussion for the Mj model, we define a meta-feature RM as:
d
ΦM
Ci
which is distributed as
RM ~ NNonndddd)) ~ N2ya,
19

---

Under review as a conference paper at ICLR 2021
For P1 1 and P2 oc,
P1.00 = P M1( + dxo) >0
-Pa-N(Bu, V (x + d0o) T W 0
1
(xs + 800 > 0]
Vd
= -P (IM vd voo > 0]
2 Pa)N(HE)
FM > Vd. 6xc
(37)
Vd
a v 6:0
vd =2
0
0
60 20
Vd
a + 20
60
vd
C.3 ROBUSTNESS OF INDIVIDUAL Mp MODELS
Additional assumptions We add the following assumptions: (1) the dimensionality parameter d
of input data is larger than 100; and (2) the ratio the mean and variance for feature Tp is greater than 10.
a
d 2 100,
2
10
(38)
We define Po the probability that for any given input Nyu,, E), the classifier Mp outputs the correct label y for the input æ + 6
=
Po PenN(spa E) Moo (x + 800) > 0]
ParN(ym x) 1 (x + doc) W > 0]
PaNN(yu -V (In + 8nx (0)) > 0]
(39)
2 PanNip, F20 > Exc
2 Eo a a
Vd -1) 1) + Va
2
using the assumptions in 38
P Po 2 0.999
(40)
p=1
P1. = Ei M1 + 61) > 0)
P (x + 81) W > 0]
Σ
[2; + 81 (i)) 0]
Vd
Pr~N(ou.E) by (em + +8m) > 0]
(41)
61
2 Pa~N(H.)
FM Vdl
Vd
a
Vd -1 1)
1
2
Vd
using the assumptions in 38
Pı, 0.999
(42)
20

---

Under review as a conference paper at ICLR 2021
C.4 DECISION RULE FOR Cadv
We aim to provide a lower bound on the worst-case accuracy of the entire pipeline, through the existence of simple decision tree Cade- For given perturbation budgets 6 and Coc. we aim to understand the range of values that can be taken by the adversarial input. Consider the scenarios described in Table beloow:
Table 4: The table shows the range of the values that the mean can take depending on the decision taken by the adversary. /60d and adde represent the new mean of the distribution of features 20 and JM after the adversarial perturbation.
Attack Type
adv
odt
y=
y=
y=
y =
None
nva
v
too
(a ex + ew)
f-a- atw
Inv++eddve (vva+a.
(xd)
(-nvd eod, -ovd d Ead)
a. (-a-a,-a+e)
{ (-nvd+a. -ny a
Note that any adversary that moves the perturbation away from the y-axis is uninteresting for our comparison, since irrespective of correct perturbation type prediction by Cedes either the two second level models naturally obtain high accuracy on such inputs. Hence, we define the following decision rule with all the remaining cases mapped to l perturbation type.
11 if | - al < 600 +
Code (z) = {0, otherwise
(43)
where the output corresponds to the classifier predicting the presence of loo perturbation in the input, while an output of O suggests that the classifier predicts the input to contain perturbations of the type.
If we consider a black-box setting where the adversary has no knowledge of the classifier Cadv and can only attack Mp is easy to see that the proposed pipeline obtains high adversarial accuracy against the union of f and loo perturbations:
Note: (1) There exists a single model that can also achieve robustness against the union of l and foo perturbations, however, learning this model may be more challenging in real data settings. (2) The classifier need not be perfect.
C.5 TRADE-OFF BETWEEN ATTACKING Md AND Cadv
To obtain true robustness is important that the entire pipeline robust against adversarial attacks. More specifically, in this section we demonstrate the natural tension that exists between fooling the top level attack classifier (by making an adversarial attack less representative of its natural distribution) and fooling the bottom level adversarially robust models (requiring stronger attacks leading to return to the attack's 's natural distribution).
The accuracy of the pipelined model / against any input-label pair (x, sampled through some distribution A (y/Mader Σ) (where Podv incorporates the change in the input distribution owing to the adversarial perturbation) is given by:
P [[((x) y] = ParNa W(yand E) [Cado (x)) PanN) E) (y Ma. (2r) > O(Cadv(z))
+ (1 - AU-Pxa PP>N((pedd:D)) (r) Pn by Mi (x) > 0)
= P (( [Cndo (x)) IP C m) M (2) > OfCado [x)]
+ (1 P PP-N [Cads P (Manu m) ( > (0) -
(44)
lo adversary: To simplify the analysis, we consider loose lower bounds on the accuracy of the model of against the lo adversary. Recall that the decision of the attack classifier is only dependent of the input zn. Irrespcctive of the input features viVi > 0, it is always beneficial for the adversary to perturb the input by f4 -o However, the same does not apply for the input zp. Analyzing for the
21

---

Under review as a conference paper at ICLR 2021
scenario when the true label y 1, if the input Zy lies between Coo of the mean a, inrespective of the perturbation, the output of the attack classifier Cade = The M model then always correctly classifies these imputs. The overall robustness of the pipeline requires analysis for the case when input lies outside foc of the mean as well. However, we consider that the adversary always succeeds in such case in order to only obtain loose lower bound on the robust accuracy of the pipeline model f against foo attacks.
PP [[((x)= = 3) P. PInN(Mmn)))) [Cadu (x)] P. PonNi 2) (Mx O]Cadu
+(1 PonN(Maa 2) (Cado (x)) P W [Mi > OI-Cado
P. NxNN(mad.
Σ) [Cadu (2)] P. NeNNipade 2) (M)( OfCa
P. N)))
[10 - al
5
tx
a 2
2 PP N(,
TD S a
+
6xc
2 (a 2 6o0 a
a
+ 30
20
d
(45)
using the assumptions in 38
P(f(x) = yl ~ 0.99
(46)
l adversary: It may be noted that trivial way for the l adversary to fool the attack clas- sifier is to return a perturbation 6n = 0. In such a scenario, the classifier predicts that the ad- versarial image was subjected to fxx attack. The label prediction is hence made by the Mxc model. But we know from (40) that the Mo model predicts benign inputs correctly with a prob- ability Poc, 0.99, hence defeating the adversarial objective of misclassification. To achieve misclassification over the entire pipeline the optimal perturbation decision for the & adversary when Zy E -a 2 c1. -a 2 + G1] the adversary can fool the pipeline by ensuring that the (x) = 1. However, in all the other cases irrespective of the perturbation, either Cade = 0 or the input features Ho has the same sign as the label y. Since, P1.1 > 0.99 for the Mj model, for all the remaining inputs zo the model correctly predicts the label with probability greater than 0.99 (approximate lower bound). We formulate this trade-off to elaborate upon the robustness of the proposed pipeline.
PP [f((x) = v) = Pa PeeNNued E) [Cado (x)) P PeNN(Muad 2) (M)( > 0|Cadr (2)]
+ (1 - P I InNN(Hone (Cado(() x- N [I) > 0| (e)d (x)]
a
a
2 P PENN(IA
-a 2
El
S S -
+
+ (..909(P (H,
Fo aa
61 To > -a
2 61
2
2 (. (P)
Io < -0
2 6 or
Fo
a
+ a)
2
(47)
using the assumptions in 38
P P[((x) = v] ~ 0.99
(48)
This concludes the proof for Theorem 2 showing that an adversary can hardly stage successful attacks on the entire pipeline and faces natural tension between attacking the label predictor and the attack classifier. Finally, we emphasize that the shown accuracies are lower bounds on the actual robust accuracy, and the objective of this analysis is not to find the optimal solution to the problem of multiple perturbation adversarial training, but to expose the existence of the trade-off between attacking the two stages of the pipeline.
22

---

Under review as a conference paper at ICLR 2021
D MODEL ARCHITECTURE
Second-level Mp models. A key advantage our PROTECTOR design is that we can build upon existing defenses against individual perturbation type. Specifically, for MNIST, CNN architecture as Zhang et al. (0119) for our Mr models, and we train these models using their proposed TRA TRADES loss. For CIFAR-IO, we use the same training setup and model architecture as Carmon et al. 22019), which is based on a robust self-training algorithm that utilizes unlabeled data to improve the model robustness.
the same
Perturbation classitier Cade- For both MNIST and CIFAR-10 datasets, the architecture of the perturbation classifier Cady similar to the individual M, models. Specifically, for MNIST, use the CNN architecture in "Zhang et al. (2019) with four convolutional layers, followed by two fully-connected layers. For CIFAR-1O, Cads is WideResNet (Zagoruyko & Komodakis 2016) model with depth 28 and widening factor of 10 (WRN-28-10).
E TRAINING DETAILS
E. SPECIALIZED ROBUST PREDICTORS M,
We use the Adam optimizer (Kingma & Ba. piece-wise linearly varying learning rate schedule (Smith 2018) to train our models with maximum learning rate of 10 -3 The base models M1, M2, Moc are trained using the TRADES algorithm for 20 iterations, and step sizes 01 2.0, 022 0.3, and 0xx 0.05 for the f,, f2, foc attack types within perturbation radii 6 = 10.0, 62 2.0, and 6 0.3 respectively
MNIST.
2015) to train our models along with
The individual Mp models are trained to be robust against L1, perturbations of (Foor 61, {2] = (0.003, 12.0, 0.05) respectively. For CIFARIO, 10, the attack step sizes {a 01 (22) = {0.005, 2.0, 0.1) respectively. The training of the individual Mp models is directly based on the work
CIFARIO.
of Carmon et al. (019)..
E.2 PERTURBATION CLASSIFIER Cadv
MNIST. We learning rate of 0.01 and Adam optimizer for 10 epochs, with linear rate decay 0.001 between the fourth epoch and the tenth epoch. The batch size is set to 100 for all experiments.
CIFARIO. We a learning rate 0.01 and SGD optimizer for 5 epochs, with linear rate decay to 0.001 between the fourth epoch and the tenth epoch. The batch size is set to 100 for all experiments.
Creating the Adversarial Perturbation Dataset. We create static dataset of adversarially perturbed images and their corresponding attack label for training the perturbation classifier Cado- For generating adversarial images, we perform weak adversarial attacks that are faster to compute. In particular, we perform 10 iterations of the PGD attack. For MNIST, the at- tack step sizes {(l.o, (11, a22 = (0.05, 2.0, 0.3) respectively. For CIFARIO, the attack step sizes {oroo 01,, a2) (0.005, 2.0, 0.1} respectively. Note that we perform the Sparse-C; or the top-k PGD attack for the & perturbation ball, as introduced by Tramèr & Boneh (2019). We set the value k to 10, that is we move by step size eu in each of the top 10 directions with respect to the magnitude of the gradient.
F ATTACKS USED FOR EVALUATION
description of all the attacks used for evaluation of the models is presented here. From the Foolbox library(Rauber et al. (017), apart from &1, l2 and f.o PGD adversaries, we also evaluate the following attacks for different perturbation types.
(1) For & perturbations, we include the Salt & Pepper Attack (SAPA) RRuberr et al. 2017 and
Pointwise Attack (PA) (Schott et al. 2018
We use the Sparse descent Tramèr Bonch 2019) for the PGD attack in the & constraint.
23

---

Under review as a conference paper at ICLR 2021
Table Vanilla Model: Empirical overlap of bpis, attack perturbations in different fy,e, regions for
(a) MNIST (c1, <2, (x) (10, 2.0, 0.3); (b) CIFAR-10 (<1, f2, represents the range (min max) of by norm for perturbations generated using l PGD attack.
f2, <x) = (12, 0.5, 0.03). Each column
Attack
MNIST
CIFARIO
Lo < 0.3
1/2 < 2.0
< 10
xx < 0.03
12 < 0.5
81< 12
PGD toc
< 0.3
(3.67 6.05)
(54.8-
(40.9)
0.03
(1.33 1.59) < 0.05
(62.7- 85.5)
PGD &
(0.40 0.86)
2.0
(1..2-24.1)
(0.037-0.10
(15.4-200)
Sparse &
(0.70 1.0)
(2.08 2.92)
S 10.0
(0.27 - 0.77)
(1.32 1.88)
S 12.0
Table 6: PROTECTOR: Empirical overlap of f..c, attack perturbations in different fg.r, regions for (a) MNIST (e1, E2; fxe) (10, 2.0, 0.3); (b) CIFÁR-10 (e1, (o) (12, 0.5, 0.03). Each column represents the range (min max) of Ey norm for perturbations generated using 4 PGD attack.
Attack
MNIST
CIFARIO
lo < 0.3
Eg < 2.0
4 < 10
Lx < 0.03
Eg < 0.5
1 < 12
PGD &oo
0.3
(5.03-6.12)
(100.40-138.52)
< 0.03
(1.46-1.69)
(73.15-93.26)
PGD &g
(0.35-0.95)
<2.0
(17.06-27.88)
(0.036-0.29)
$0.05 (1.50-2.91)
(5.83-21.21)
Sparse &
(0.81-1.0)
(2.13-2.98)
$10.0
(0.42-1.0)
$12.0
(2) For Eg perturbations, we include the Gaussian noise attack (Rauber al. 2017). Boundary Attack (Brendel et al., (2118). DeepFool (Moosavi-Dezfool) et al. 2016), DDN attack (Rony et al. 2019). and C& W attack (Carlini & Wagner 2017b).
(3) For Loo perturbations, we include FGSM attack (Goodfellow et al. 2015) and the Momentum Iterative Method (Dong et al. 2018).
From the AutoAttack library from Croce& & Hein 2020c), we make use of all the three variants of the Adaptive PGD attack (APGD-CE, APGD-DLR, APGD-T) (Croce & Hein (020c) along with the targeted and standard version of Fast Adaptive Boundary Attack (FAB, FAB-T) (Croce & Hein
2020b and the Square Attack (Andriushchenko et al. 2020). We utilize the AA# version for strong attacks.
Attack Hyperparameters For the attacks in the Foolbox and AutoAtack libraries we use the default parameter setting in the strongest available mode (such as AA+). For the custom PGD attacks, we evaluate the models with 10 restarts and 200 iterations of the PGD attack. The step size of the flac, l f2) PGD attacks {0.01, 1.0, 0.1} respectively, For CIFARIO, the attack step sizes {ato 01 a2) = {0.003, 1.0, 0.02] respectively.
follows: For MNIST, the attack step sizes {a 01, 02) =
Further, similar to Tramèr & Boneh (2019); Maini et al. (020)) we evaluate our models on the first 1000 images of the test set of MNIST and CIFAR-1O, since many of the attacks employed extremely computationally expensive and slow to run. Specifically, on a single GPU, the entire evaluation for single model against all the attacks discussed with multiple restarts will take nearly I month, and is not feasible.
G EMPIRICAL PERTURBATION OVERLAP
Following Section 6.2 we also present results on the perturbation overlap when we attack PROTECTOR with PGD attacks. To contrast the results with that of attacking a vanilla model, we also present the table in the main paper for convenience. It is noteworthy that the presence of perturbation classifier forces the adversaries to generate such attacks that increase the norm of the perturbations in alternate l, region. Secondly, we also observe that in the case of CIFARIO, 10, the l PGD attack has a large overlap with the & norm of radius 10. However, recall that in case of & attacks for CIFAR1O, both the base models Mj and M& were satisfactorily robust. Hence, the attacker has incentive to reduce the perturbation radius for an E, norm since the perturbation classifier only performs a binary classification between & and fo attacks. The results be observed in Tables and
24

---

Under review as a conference paper at ICLR 2021
Table 7: Perturbation type classification accuracy for different perturbation types. Note that the pertur- bation classifier Cado is only trained on adversarial examples against two Mp models. Each column represent the model used create transfer- based attack via the attack type in the corresponding row. The represented accuracy is an aggregate over 1000 randomly sampled attacks of the foo, l2, & types for the corresponding algorithms (and datasets).
Moe
M2
M₁
MAX
AVG
MSD
MNIST-PGD MNIST-AutoAttack
100.0%
100,0%
99.3%
99.0%
99.6%
99.1%
100.0%
100.0%
99.0%
99.5%
100.0%
100.0%
CIFARIO-PGD
99.90%
99.50%
100.0%
100.0%
98.70%
95.70%
CIFARIO-AutoAttack
99.90%
99.90%
100.0%
100.0%
99.70%
99.70%
H BREAKDOWN OF COMPLETE EVALUATION
In this section, we present the results the perturbation type classifier Cade against transfer adver- saries. We also present the breakdown results of the adversarial robustness of baseline approaches and our PROTECTOR pipeline against all the attacks that we tried, and also report the worst case performance against the union of all attacks.
H. ROBUSTNESS OF Cade
The results for the robustness of the perturbation classifier Cado in the presence of adaptive adversaries presented in Table Note that Cadv transfers well across the board, even if the adversarial examples are generated against new models that are unseen for Cade during training, achieving extremely high test accuracy. Further, even if the adversarial attack was generated by a different algorithm such as from the AutoAtttak library, the transfer success of Cade still holds up. In particular, the obtained accuracy > 95% across all the individual test sets created. The attack classification accuracy is in general highest against those generated by attacking Mj or Mc for CIFAR10 10, and M2 or Moc for MNIST. This is an expected consequence the nature of generation of the static dataset for training the perturbation classifier Cado as described in Section 5.1
H.2 MNIST
In Table 8 we provide a breakdown of the adversarial accuracy of all the baselines, individual M, models and the PROTECTOR method, with both the adaptive and standard attack variants on the MNIST dataset. PROTECTOR outperforms prior baselines by 6.9% on the MNIST dataset. It important note that PROTECTOR shows significant improvements against most attacks in the suite. Compared to the previous state-of-the-art defense against multiple perturbation types (MSD), we compare the performance gain on each individual attack algorithm, the improvement is also significant, with an average accuracy increase of 15.5% on MNIST dataset. These results demonstrate that PROTECTOR considerably mitigates the trade-off in accuracy against individual attack types.
H.3 CIFAR-10
In Table 9] we provide a breakdown of the adversarial accuracy of all the baselines, individual Mp models and the PROTECTOR method, with both the adaptive and standard attack variants on the CIFARIO dataset. PROTECTOR outperforms prior baselines by 8.9%. Once again, note that PROTECTOR shows significant improvements against most attacks in the suite. Compared to the previous state-of-the -fttt--rtttt defense against multiple perturbation types (MSD), if we compare the performance gain each individual attack algorithm, the improvement is significant, with average accuracy increase 14.2% on. These results demonstrate that PROTECTOR considerably mitigates the trade-off in accuracy against individual attack types.
Further, PROTECTOR also retains a higher accuracy on benign images, as opposed to past defenses that have to sacrifice the benign accuracy for the robustness multiple perturbation types. In particular, the clean accuracy of PROTECTOR over 6% higher than such existing defenses on CIFAR-16 10, and the accuracy is close M, models trained for single perturbation type.
25

---

Under review as a conference paper at ICLR 2021
Ma
M2
Mi
MAX
AVG
MSD
Ours
Ours*
Benign Accuracy
99.2%
98.7%
98.8%
98.6%
99.1 1..1 %
98.3%
98.7%
98.7%
Loo attacks (E = 0.3)
FGSM
96.3%
87.7%
12.2%
81.2%
85.4%
83.0%
94.8%
94.8%
PGD-Foolbox
95.5%
27.5%
0.4%
67.8%
76.0%
76.2%
86.7%
95.1%
MIM
94.1%
52.5%
1.1%
70.6%
76.7%
74.2%
86.8%
96.7%
APGD-CE
91.6%
3.8%
0.0%
41.0%
59.0%
65.3%
86.9%
91.6%
APGD-DLR
91.9%
7.7%
0.0%
43.8%
61.9%
65.8%
91.8%
91.5%
APGD-T
91.8%
2.8%
0.0%
39.6%
58.9%
64.5%
90.5%
92.5%
FAB
91.8%
5.5%
0.0%
51.0%
65.7%
66.8%
95.6%
97.7%
FAB-T
92.6%
4.9%
0.0%
48.7%
64.2%
65.5%
95.2%
98.0%
SQUARE-T
90.1%
7.3%
0.0%
46.0%
64.9%
68.0%
97.2%
97.3%
f2 attacks (e 2.0)
PGD-L2
78.2%
73.6%
50.6%
62.6%
65.9%
71.0%
73.5%
74.3%
PGD-Foolbox
95.4%
83.2%
60.2%
74.3%
79.2%
79.0%
83.7%
83.3%
Gaussian Noise
99.4%
98.5%
98.6%
98.6%
99.1%
98.1%
98.5%
98.5%
DeepFool
94.4%
88.9%
71.0%
81.0%
86.7%
81.7%
87.7%
88.0%
DDN
41.7%
75.9%
53.2%
62.1%
64.7%
70.3%
92.4%
94.7%
CWL2
51.7%
76.3%
54.7%
63.6%
65.2%
71.5%
86.8%
98.2%
APGD-CE
78.5%
74.2%
50.8%
61.9%
64.9%
69.7%
75.7%
76.4%
APGD-DLR
79.6%
75.4%
53.9%
63.2%
65.1%
70.8%
76.5%
78.2%
APGD-T
80.4%
73.5%
48.0%
61.2%
63.8%
69.4%
74.5%
76.8%
FAB
11.6%
77.5%
54.9%
63.4%
64.3%
69.5%
98.0%
98.0%
FAB-T
13.2%
74.9%
49.4%
62.3%
63.6%
69.0%
86.3%
96.3%
SQUARE-T
25.9%
81.9%
67.1%
71.9%
71.4%
73.7%
96.5%
96.6%
ε attacks (E = 10.0)
PGD-E,
65.6%
73.6%
78.2%
52.0%
57.1%
65.5%
69.3%
79.4%
Salt & Pepper
67.1%
95.4%
96.2%
93.9%
88.2%
91.2%
95.2%
95.4%
Pointwise Attack
15.6%
84.1%
88.4%
66.0%
46.2%
78.3%
79.5%
89.5%
FAB-T
19.1%
71.5%
77.9%
43.9%
41.1%
67.6%
82.1%
95.0%
Table 8: Attack-wise breakdown of adversarial robustness on the MNIST dataset. Ours represents the PROTECTOR method against the adaptive attack strategy described in Section 5.2 and Oury* represents the standard attack setting.
26

---

Under review as a conference paper at ICLR 2021
Ma
M2
M1
MAX
AVG
MSD
Ours
Ours#
Benign Accuracy
89.4%
93.9%
89.3%
81.0%
84.6%
81.1%
90.8%
90.8%
Loo attacks (E = 0.03)
FGSM
70.2%
62.7%
51.3%
53.3%
50.4%
53.0%
80.4%
72. 1%
PGD-Foolbox
69.3%
53.9%
47.0%
52.3%
49.0%
52.0%
68.8%
68.9%
MIM
66.1%
49.8%
43.0%
49.0%
44.5%
49.6%
67.4%
72.1%
APGD-CE
61.9%
35.6%
35.7%
38.7%
41.0%
46.2%
64.8%
63.8%
APGD-DLR
61.1%
38.0%
37.7%
39.6%
43.0%
46.4%
62.5%
63.2%
APGD-T
59.4%
34.8%
35.1%
36.8%
39.7%
43.8%
62.0%
62.1%
FAB
60.5%
38.2%
36.5%
40.9%
40.4%
44.4%
87.1%
88.1%
FAB-T
60.0%
35.8%
35.5%
40.8%
40.2%
44.0%
78.2%
83.1%
SQUARE-T
67.2%
57.4%
50.5%
51.7%
50.9%
51.5%
86.1%
84.1%
f2 attacks (e 0.5)
PGD-L2
66.4%
77.5%
72.4%
64.5%
67.8%
66.2%
67.0%
68.3%
PGD-Foolbox
68.7%
78.1%
72.7%
64.9%
67.9%
66.3%
69.8%
70.4%
Gaussian Noise
89.4%
93.9%
89.1%
81.7%
84.7%
82.3%
89.3%
89.3%
DeepFool
72.9%
79.4%
73.0%
64.3%
67.3%
65.6%
72.8%
73.1%
DDN
66.8%
77.5%
72.6%
64.6%
67.7%
66.2%
83.6%
85.2%
CWL2
67.2%
77.5%
72.0%
63.2%
71.5%
65.1%
88.4%
68.3%
APGD-CE
66.2%
77.4%
72.3%
64.3%
67.2%
66.1%
68.8%
70.2%
APGD-DLR
65.6%
77.6%
71.9%
62.9%
66.0%
65.3%
68.8%
69.3%
APGD-T
64.8%
77.3%
71.5%
62.1%
65.5%
64.5%
67.8%
68.6%
FAB
65.7%
77.8%
71.8%
62.5%
65.6%
64.6%
89.9%
88.2%
FAB-T
65.0%
77.4%
71.7%
62.7%
65.6%
64.5%
85.2%
85.6%
SQUARE-T
80.8%
86.2%
82.0%
72.0%
77.3%
72.1%
89.4%
88.6%
ε attacks (E = 12.0)
PGD-E,
20.6%
38.2%
55.9%
41.2%
54.7%
53.4%
55.9%
56.3%
Salt & Pepper
66.9%
81.1%
80.2%
73.8%
80.2%
74.2%
74.4%
72.0%
Pointwise Attack
50.4%
70.6%
74.6%
54.9%
75.1%
69.6%
78.9%
70.1%
FAB-T
28.3%
36.8%
56.4%
41.3%
60.2%
52.2%
70.5%
70.1%
Table 9: Attack-wise breakdown of adversarial robustness on the CIFAR-10 dataset. the PROTECTOR method against the adaptive attack strategy described in Section 5.2 and Oury* represents the standard attack setting.
Oury represents
27

---

Under review as a conference paper at ICLR 2021
Table 10: Comparison between using a "softmax' based aggregation of predictions from different specialized models versus using the prediction from the model corresponding to the most likely attack (only at inference time). Results are presented for APGD &,, So attacks on the CIFARIO dataset.
Attack
Max-approach (Eq.
Softmax-approach (Eq. (4)
APGD-CE f2 (e2 = 0.5)
75.7%
75.6%
APGD-DLR l2 (62 = 0.5)
76.5%
76.7%
APGD-CE too (Exx 0.03) APGD-DLR Loo (Exo = 0.03)
86.9%
86.9%
91.8%
91.2%
H.4 AGGREGATING PREDICTIONS FROM DIFFERENT M, AT INFERENCE
In all our experiments in this work the adversary constructs adversarial examples using the softmax based adaptive strategy for aggregating predictions from different Mp models, as described in Equation 4 for the column 'Ours' and using the 'max' strategy (Equation [ for results described in the column 'Ours*'
However, for consistency of defense strategy irrespective of the attacker's strategy, the defender only utilizes predictions from the specialized model Mp corresponding to the most-likely attack (Equation I provide the final prediction (only forward propagation) for generated adversarial examples. In our evaluation, we found a negligible impact of changing this aggregation to the 'softmax' strategy for aggregating the predictions. For example, we show representative results in case of the APGD (foc, E2) attacks on the CIFAR10 10 dataset in Table I0
28


Reviews:
[{"review_id": "fR5vtp3LUh", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In theoretical analysis, the authors conclude with an Gaussian assumption on the data distribution. \n\nThis assumption is very restrictive, and the corresponding conclusion does not provide a general view of what is happening for real datasets. Gaussian condition on dataset is very unrealistic, and its theoretical analysis should only be considered as dealing with a toy model. \n\nAuthors should remove this Gaussian assumption, or at least give strong reasons in plain natural language why Gaussianity can represent natural datasets in the adversarial study.  ", "extra_scores": {}, "extra_text": {}}, {"review_id": "eOZZwHJVEPX", "reviewer": "AnonReviewer2", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes a two-stage defense method to improve the adversarial robustness over different perturbation types. Specifically, it first builds a hierarchical binary classifier to differentiable the perturbation types and then uses the result to guide to its corresponding defense models.  It first proves the different types of perturbations could be separable and the adversary could be weakened to fool the binary classifier. It shows their methods achieve a clear improvement in the experiments.\n\nPros:\n1. The paper is good-written and easy to follow.\n2. The proposed idea is interesting.\n3. The experiment is detailed and comprehensive.\n\nCons:\n1. There is a major problem in their method. In the last sentence of section 5.2, it says uses the soft relaxation only in generating the adversarial example, but not for inference. It clearly caused the gradient making problem in the adversarial attack later on to test the robustness.  The gradient is blocked before reaching into the binary classifier so that the adversarial attack fails, which I think it is not truly improving the model's robustness.\n2. In my opinion, this method is just a dynamic voting based model ensemble. Just take the binary classifier as a voting procedure.  Therefore, the traditional adversarial attacks won't work in general. I would suggest using the soft relaxation in the inference as well for the adversarial attack. \n3. Also, the assumption that different norm adversarial examples could be clearly separable might be wrong. You could find the adversarial examples that satisfy both l1, l2 and l_inf constraint by just choosing the \\epsilon for every norm differently.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "Ks_H8qg-gK", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nThis paper proposed a pipeline method which first classify the attack type and then choose the proper predictor for that type. The authors provide both theoretical and experimental proof to support their pipeline method. \n\nPros:\n\n(1) The idea is good and reasonable. Also, the paper is well written and easy to read. The proof part is clear and natural. \n(2) The result of theorem 1 is interesting and it proved the different perturbation types (under this problem setting) is separable with a high probability. Although the setting is a little restrictive, it is still very impressive.  \n\nCons:\n(1) The method and analysis only apply to the Lp attack type. It will be good if it can be extended. \n(2) Assume that we treat the two pipelines as the whole process (end-end deep network), e.g., the first layers determines the type and then that type will determine which part to activate for training the data points, that is, you have a network with special topology and structure. If the attacker only cares about this input and output of this network (no pipeline here), we should have an attack strategy. How to explain this view using your analysis ? Could we say this is equivalent  to changing the structure of the network  ? From this perspective, could you tell the difference between these two views ?\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "0pMLwtEUBEy", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes an ensemble approach to deal with multiple perturbation types. The underlying idea is to train a robust classifier for each perturbation type (i.e., l1, l2, and l-inf) and choose a model to predict based on the decision of a perturbation classifier which is trained to distinguish perturbation types.\nThe idea is interesting, and the experiments seem solid; however, I am hesitating to give this paper an acceptance decision due to some unclear points as follows:\n1.\tI have not checked the proof of Theorem 1, but it seems a bit counter-intuitive to me. The reason is as follows. Let’s assume that we are attacking a clean image x. We start from x0 inside both l1 and l-inf balls for example. We further assume that during the process of updating x{t}, we never do any projection onto any ball (i.e., x{t} always lie inside the balls). If so, there is not any difference between x_adv w.r.t l1 and l_inf, meaning that there are possibly a certain number of adversarial examples shared across l1 and l-inf attacks.\n2.\tIn your Theorem 1 (also your experiments), the radius of l1 is eps and that of l-inf is eps/sqrt(d), meaning that the ball of l-inf is a subset of the ball of l1. However, in Section 5.3, you claimed that “The dotted line shows the decision boundary for the perturbation classifier C_adv, which correctly classifies inputs subjected to large ‘1 perturbations δ00 as ‘1 attacks (green), but can misclassify samples with smaller perturbations”. It seems that you reckon l-inf adversarial examples are having more perturbation than l1, do not you?\n3.\tTheorem 2 is not understandable to me. What is worst-case adversary (this needs to be explained and defined because we can understand this notion in several different ways)? What is delta?\n4.\tI recommend testing Projector against the attack over a uniform average of Mp in addition to what is doing.\n5.\tIt is encouraging to compare your proposed method against (Francesco Croce and Matthias Hein, 2020 a). You did mention this work, but not compare it in experiments.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a model to defend against multiple lp norm attacks by classifying those attacks. The reviewers raised several concerns about the methodologies. Furthermore, it's not clear how the proposed algorithm can deal with an unseen attack (e.g., only trained on l1, l_infty attacks but encounter l2 attack in the testing phase). The assumption that the attack types are known beforehand is restricted.  
Decision: Reject