On the Limitations of Stochastic Pre-processing Defenses
Authors: Yue Gao
Ilia Shumailov
Kassem Fawaz
Nicolas Papernot
Venue: NeurIPS 2022 Accept (2022)
Keywords: adversarial examples
randomized defenses
preprocessing defenses
input transformation
limitations

Abstract: Defending against adversarial examples remains an open problem. A common belief is that randomness at inference increases the cost of finding adversarial inputs. An example of such a defense is to apply a random transformation to inputs prior to feeding them to the model. In this paper, we empirically and theoretically investigate such stochastic pre-processing defenses and demonstrate that they are flawed. First, we show that most stochastic defenses are weaker than previously thought; they lack sufficient randomness to withstand even standard attacks like projected gradient descent. This casts doubt on a long-held assumption that stochastic defenses invalidate attacks designed to evade deterministic defenses and force attackers to integrate the Expectation over Transformation (EOT) concept. Second, we show that stochastic defenses confront a trade-off between adversarial robustness and model invariance; they become less effective as the defended model acquires more invariance to their randomization. Future work will need to decouple these two effects. We also discuss implications and guidance for future research.

On the Limitations of Stochastic Pre-processing Defenses
Yue Gao
Ilia Shumailov
University of Siaconsin-Maaiiiee gy0cs. wisc. edu
University of Cambridge & Vector Institute
ilia. wwwwssloo@cc..oooommoo ac. uk
Kassem Fawaz University of Misconsin-MMddioe kfawaz@wisc.en edu
Nicolas Papernot
University of Toronto & Vector Institute
nicolas. haailas.pppproottttooottttt ca
Abstract
Defending against adversarial examples remains an open problem. A common belief is that randomness at inference increases the cost of finding adversarial inputs. An example such a defense is to apply a random transformation to inputs prior to feeding them to the model. In this paper, empirically and theoretically investigate such stochastic pre-processing defenses and demonstrate that they are flawed. First, show that most stochastic defenses weaker than previously thought; they lack sufficient randomness to withstand even standard attacks like projected gradient descent. This casts doubt on a long-held assumption that stochastic defenses invalidate attacks designed to evade deterministic defenses and force attackers integrate the Expectation over Transformation (EOT) concept. Second, we show that stochastic defenses confront a trade-off between adversarial robustness and model invariance; they become less effective as the defended model acquires more invariance to their randomization. Future work will need to decouple these two effects. We also discuss implications and guidance for futurre research.
Introduction
Machine learning models are vulnerable to adversarial examples 36), where adversary can add imperceptible perturbations to the input of model and change its prediction [5. 24]. Their discovery has motivated wide variety of defense approaches [6. 8, 12, 29, 40, 42] along with the evaluation of their adversarial robustness [2, 28, 38]. Current evaluations mostly rely on adaptive attacks [2, 38], which require significant modeling and computational efforts. However, even when the attack succeeds, such evaluations may not always reveal the fundamental weaknesses of an examined defense. Without awareness of the underlying weaknesses, subsequent defenses may still conduct inadvertently weak adaptive attacks; this leads to overestimated robustness.
One popular class of defenses that demonstrates the above is the stochastic pre-processing defense, which relies on applying randomized transformations to inputs to provide robustness [12, 42). Despite existing attack techniques designed to handle randomness [2. 3]. there an increasing effort to improve these defenses through a larger randomization space or more complicated transformations. For example, BaRT [28] employs 25 transformations, where the parameters each transformation are further randomized. Due to the complexity of this defense, it was only broken recently (three years later) by Sitawarin al. [34] with a complicated adaptive attack. Still, it unclear how future defenses can avoid the pitfalls of existing defenses, largely because these pitfalls remain unknown.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

In this paper, we investigate stochastic pre-preessiing defenses and explain their limitations both empirically and theoretically. First, we revisit previous stochastic processssn defenses and explain why such defenses are broken. We show that most stochastic defenses are not sufficiently randomized to invalidate standard attacks designed for deterministic defenses. Second, we study recent stochastic defenses that exhibit more randomness and show that they also face key limitations. In particular, we identify a trade-off between their robustness and the model's invariance to their transformations. These defenses achieve notion of robustness that results from reducing the model's invariance to the applied transformations. We outline our findings below. These findings suggest future work to find new ways of using randomness that decouples these two effects.
Most stochastic defenses lack sufficient randomness. While Athalye et al. [2] and Tramèr al. [38] have demonstrated the ineffectiveness of several stochastic defenses with techniques like Expectation over Transformation (FOT) [3], remains unclear whether and why EOT is required (or at least as a "standard technique") to break them. A commonly accepted explanation is that EOT computes the "correct gradients" of models with randomized components [2, 38], yet the necessity of such correct gradients has not been explicitly discussed. To fill this gap, we examine long-held assumption that stochastic defenses invalidate standard attacks designed for deterministic defenses.
Specifically, we revisit stochastic pre-processing defenses previously broken by EOT and examine their robustness without upplying EOT. Interestingly, we find that most stochastic defenses lack sufficient randomness to withstand even standard attacks (that do not integrate any strategy to capture model randomness) like projected gradient descent (PGD) [24]. We then conduct a systematic evaluation to show that applying EOT is only beneficial when the defense is sufficiently randomized. Otherwise, standard attacks already perform well and the randomization's 's robustness is overestimated.
Trade-off' between adversarial robustness and model invariance. When stochastic pre-processing defenses do have sufficient randomness, they must fine-tune the model using augmented training data to preserve utility in the face of randomness added. We characterize this procedure by the model's invariance the applied defense, where we identify a trade-off between the model's robustness (provided by the defense) and its invariance to the applied defense. Stochastic pre- pre-processing defenses become less effective when their defended model acquires more invariance to their transformations.
On the theoretical front, we present a theoretical setting where this trade-off provably exists. We show from this trade-off that stochastic pre-processing defenses provide robustness by inducing variance on the defended model, and must take back such variance to recover utility. We verify this trade-off with empirical evaluations realistic datasets, models, and defenses. We observe that robustness drops when the defended model is fine-tuned on data processed by its defense to acquire higher invariance.
2 Related Work
Stochastic Pre-processing Defenses. Defending against adversarial examples remains an open problem, where a common belief is that inference-tine randomness increases the cost of finding adversarial inputs. Early examples of such stochastic defenses include input transformations [12] and rescaling [42]. These defenses were broken by Athalye et al. [2] using techniques like EOT [3] to capture randomness, After that, more stochastic defenses were proposed but with inadvertently weak evaluations [26, 29, 40, 44], which were found ineffective by Tramer et al. [38]. Subsequent stochastic defenses resort to larger randomization space like BaRT [28], which was only broken recently by Sitawarin et al. [34]. In parallel to our work, DiffPure [25] adopts a complicated stochastic diffusion process to purify the inputs. As we will discuss in Appendix F. this defense belongs to an existing
line of research that leverages generative models to pre-process input images [19, 32, 35], hence it matches the settings in our work. On the other hand, randomized smoothing [6, 17, 31] leverages randomness to certify the inherent robustness of given decision. In this work, instead of designing adaptive attacks for individual defenses, which is a well-known challenging progress [2, 34, 38), we focus on the general stochastic pre-processing defenses and demonstrate their limitations.
Trade-offs for Adversarial Robustness. The trade-offs associated with adversarial robustness have been widely discussed in the literature. For example, prior work identified trade-off's between robustness and accuracy [39, 46] for deterministic classifiers. Pinot et al. [27] generalize this trade-off to randomized classifiers with a similar form as randomized smoothing. Compared with these results, our work provides deeper understanding that stochastic pre-processing defenses explicitly control such trade-offss to provide robustness. Recent work also investigated the trade-off between the model's

---

robustness and invariance to input transformations, such as circular shifts [33] and rotations [14]. These trade-offs characterize a standalone model's own property - the model itself less robust to adversarial examples when it becomes more invariant to certain transformations, without any defense. Our setting, however, is orthogonal to such analysis - the model that we consider is protected by a stochastic pre- processens defense, and what we really aim to characterize is the performance of that pre-processing defense, not the inherent robustness of the model itself.
3 Preliminaries
Notations. Let f :X + Rd denote the classifier with pre-softmax outputs, where X' = [0. 1] is the imput space with d dimensions and C' is the number of classes. We then consider stochastic pre-processing defense to : X + X, where 0 is the random variable drawn from some randomization space θ that parameterizes the defense. The defended classifier can be written fo(2) == (t)))))..
Let F(x:) == arg m (x) denote the classifier that returns the predicted label, where f. the output of the i-th class and y = [C] is the label space. Similarly, we use Feg and fe.; to denote the prediction and class-output of the stochastic classifier fa- Since this classifier returns varied outputs for a fixed input, it determines the final prediction by aggregating independent inferences with strategies like majority vote. We discuss these strategics and the choice of n in Appendix A.1.
Adversarial Examples. Given an image æ E X and a classifier F, the adversarial example x' : x + 8 is visually similar æ but either misclassified (i.e., F(x') a F(x)) or classified as a target class y' chosen by the attacker (i.e., F(x') y²). Attack algorithms generate adversarial examples by searching for such that æ' fools the classifier while minimizing ô under some distance metrics; for instance, the Ep norm constraint |00|p for a perturbation budget
Projected Gradient Descent (PGD). PGD [24] is one of the most established attacks to evaluate adversarial example defenses. Given a benign example x and its ground-truth label y. each iteration of the untargeted PGD attack (with foo norm budget can be formulated as }.
x + a s V where a is the step size, is the loss function, and each iteration is projected to the foo ball around x of radius We PGD-k to denote the PGD attack with ls steps. We outline formulations for other settings and norms in Appendix A.2.
x
(1)
Expectation over Transformation (EOT). Since the classifier fe is stochastic, the defense evalua- tion literature [2, 38] argues that attacks should target the expectation the gradient using Expectation over Transformation (EOT) [3], which reformulates the PGD attack as
x ++1 + xx' a sgn Eewe (V xo x + sgm
(ffe (2)
where is the number of samples to estimate the expectation and 0 iid θ are sampled parameters for the defense. We use EOT-m to denote the EOT technique with m samples at each PGD step.
In addition, for a fair comparison among attacks with different PGD steps and EOT samples, we quantify the attack's strength by total number of gradient computations. For example, attacks using PGD-k and EOT-m will have strength k x Although white-box attacks are typically not constrained in this way, it allows for a fair comparison when attacks have finite computing resources (e.g., when EOT is not parallelizable). We discuss more about this quantification in Appendix A.3.
4 Most Stochastic Defenses Lack Sufficient Randomness
Athalye al. [2] and Tramèr al. [38] demonstrate adaptive evaluation of stochastic defenses with the application of EOT. However, it remains unclear why EOT is required (or at least as a "standard technique") to break these stochastic defenses. While commonly accepted explanation is that EOT computes the "correct gradients" of models with randomized components [2, 38J, the necessity of such correct gradients has not been explicilly discussed. To fill this gap, we revisit stochastic defenses previously broken by EOT and examine their robustness without applying BOT. Interestingly, we find that applying EOT is mostly unnecessary when evaluating existing stochastic defenses.
3

---

Table The missing ablation study of adaptive evaluations of stochastic defenses in the literature.
Notations: attack iterations k, EOT samples m, learning rate a, number of gradient queries l x m. The details of these defenses and their evaluation settings are in Appendix B.
Original Adaptive Evaluation (w/ EOT)
Our Ablation
Study (w/o EOT)
Defenses
k m
Success Rate
k:
m
a & m
Success Rate
Guo al. [12]
1,000
30
0.1
30,000
100%
1,000
0.001
1,000
99.0%
Xie [42]
1,000
30
0.1
30,000
100%
200
0.1
200
100%
Dhillon et al. [8]
500
10
0.1
5,000
100%
500
0.1
500
100%
Xiao et al. [40]
100
1,000
0.01
100,000
100%
40,000
1
0.1/255
40,000
98.4%
Roth et al. [29]
100
40
0.2/255
4,000
100%
4,000
1
0.1/255
4,000
96.1%
Case Study: Random Rotation. We start with simple stochastic defense that randomly rotates the input image for O E [-90, 90] degrees (chosen at uniform) before classifica- tion. This defense is representative for most pre-processing defenses [12. 28, 42]. We evaluate this defense on 1,000 Im- ageNet images with PGD-k and EOT-m under the constraint k 50, as discussed in Section 3. All attacks use max- imum 20 perturbation = 8/255 with step size chosen from {1/255, 2/255). The results are shown in Table where PGD-50 performs equally well as PGD-10 combined with EOT-5. This observation suggests that some stochastic defenses are already breakable without applying EOT, casting doubt long-held assumption that stochastic defenses simply invalidate attacks designed for deterministic defenses.
Table 1: Evaluation of the random
rotation with PGD-k and EOT-m.
Attacks
m
Success Rate
10
5
100%
Untargeted
50
1
100%
10
5
99.0%
Targeted
50
1
99.0%
Comprehensive Evaluations. We then extend the above case study to other stochastic defenses evaluated in the literature. Specifically, we replicate the (untargeted) adaptive evaluation of stochastic defenses from Athalye et al. [2] and Tramèr et al. [38] with their official implementation. We only change the attack's 's syper-parameters (e.g.. number iterations and learning rate) and disable EOT by setting its number of samples to one (m 1), which avoids potential implementation flaws if removed from the source code. The comparison between evaluations with and without applying EOT is summarized in Table 2, which serves missing ablation study of adaptive evaluations in the literature. The experimental settings are identical within each row (detailed in Appendix B).
Interestingly, we find it unnecessary to break these defenses with EOT, as long the standard attack runs for more iterations with a smaller learning rate. For such defenses, standard iterative attacks already contain an implicit expectation across iterations to capture the limited randomness. This observation implies that most stochastic defenses lack sufficient randomness to withstand even standard attacks designed for deterministic defenses. Therefore, increasing randomness becomes promising approach to enhancing stochastic defenses, as adopted by recent defenses [6, 28]. Note that this ablation study only aims to inspire potential ways of enhancing stochastic defenses; it does not invalidate EOT for stronger adaptive evaluations of stochastic defenses.
5 Tradc-offs between Robustness and Invariance
When stochastic pre-processing defenses do have sufficient randomness, they must ensure that the utility of the defended model is preserved in the face of randomness. To achieve high utility, existing defenses mostly rely on augmentation invariance through trained invariance [23]. such a case, the invariance is achieved by applying the defense's 's randomness to the training data so as to guide the model in learning their transformations. For defenses based on stochastic pre-processor tg, each data sample from the dataset gets augmented with to sampled from the randomization space θ and the risk is minimized over such augmented data.
The defended classifier Fe(x)) = F((e(=)) is invariant under the randomization space θ if F(to(=)) = F(x), A E θ E X
As we can observe from the definition, invariance has direct implications on the performance of stochastic pre- propercessing defenses. If the classifier is invariant under the defense's randomization space as is defined in Equation (3), then the defense should not work - computing the model and its gradients over randomization 0 E θ is the same as if to was not applied at all. This observation

---

M)-111
less vulnerable points
170,1+0")
back undefended
Mic o M Bamley
1)
Boundey
Bounday
-2
-2
-6 0
4
+-2
(a) Undefended
(b) Defended (Lack of Invariance) (c) Defended (Trained Invariance)
Figure 1: Illustration of the binary classification task we consider. The curves are the probability density function of two classes of data. Shadowed area denotes correct classification. Dotted area denotes robustly correct classification under the loc -bounded adversary with perturbation budget e.
suggests a direct coupling between invariance and performance of the defense: the more invariant, hence performant, the model is under given randomization space, the less protection such defense would provide. In this section, we present a simple theoretical setting where this coupling provably exists, illustrated in Figure 1. Detailed arguments are deferred to Appendix C.I.
Binary Classification Task. We consider a class-balanced dataset 'D consisting of input-lahel pairs (x,,) with y {-1, +1) and æly ~ Ny,, 1), where ((u, o²) is normal distribution with mean and variance o². Moreover, an -bounded adversary perturbs the input with a small to fool the classifier for |o I e. We quantify the classifier's robustness by its robust accuracy, i.e., the ratio of correctly classified samples that remain correct after being perturbed by the adversary.
Undefended Classification. We start with the optimal linear classifier F(z) == sgn(z) without any defense Figure la. This classifier attains robust accuracy
Pr[F(x + 6) = F(z) - F(x) Pr F(r x + +0) = =y = 4(1 - c)
(4)
Pr Pr(F(z)
((1)
where & is the cumulative distribution function of 1).
Defended Classification. We then try to improve adversarial robustness by introducing stochastic pre- pre-processing defense to (z) == x + 0, where ~ N (1, is the random variable parameterizing the defense. This defense characterizes common pre-process pee-peocessnn defenses that enforce randomness while shifting the input distribution. Here, the processed input follows a shifted distribution to (x) ~
Nfy 1, +
o?) in Figure 1b. The defended classifier (x) sgn(x 0) has robust accuracy
[roFo( + 5) = Fo(x) = v] Pr Pr + 8) = A F = +'(-e) + 42 (5)
Pr
Fo
2
(0((0) + (2(2)
where ('(x) +<x/vi++ 0²) is the cumulative distribution function of N + o²). At this point, we have not fit the classifier on processed inputs. Due to its lack of invariance, the defended classifier has low utility yet higher robust accuracy than the undefended one in Equation (4).
Defended Classification (Trained Invariance). As discussed above, one critical step of stochastic pre- pe-ppoceessing defenses is to preserve the defended model's utility by minimizing the risk over augmented data to (z)), which leads to a new defended classifier Ftt (æ: = sgn (x +0--01 in Figure Ic. As result, this new defended classifier achieves higher invariance with robust accuracy
Pr F (x = Fo (2) = y) [F (a 5) = y Ff (x) m]
Φ'(1 (1-
(6)
Pr(F+t())
('11
which is less robust than the previous less-invariant classifier Fo Equation (5). However, one may observe that this classifier, though loses some robustness compared with Fo, is still more robust than the original undefended classifier F in Equation (4). This part of robustness comes from the changed data distribution due to the defense's randomness. It shows that we have not achieved perfect invariance to the defense's 's randomness, thus gaining some robustness at the cost of utility.
Defended Classification (Perfect Invariance). Furthermore, these defenses usually leverage majority vote to obtain stable predictions, which finally produces a perfectly invariant defended classifier
sgn(x + 0; 00-1)) 10) sgn(x) = F(x), (7)
F% (x) = sgn
(x)
sgn
72
5

---

where 02 Rdd (1, are sampled parameters. such case, the defended classifier reduces the original undefended classifier with the original robust accuracy:
(r + = y 1 (x) = u] = Pr[F(r 6) = F(x) = (11)
(8)
Summary. The above theoretical setting illustrates how stochastic pre-processing defenses first induce variance on the binary classifier consider to provide adversarial robustness in Equation (5), and how they finally take back such variance in Equations (6) and (8) to recover utility. We then extend the above coupling between robustness and invariance to general trade-off in the following theorem, whose detailed descriptions and proof's are deferred to Appendices C.2 and C.3, respectively.
Theorem 1 (Trade-off between Robustness and Invariance). Given the above theoretical setting and assumptions, when the defended classifier Fe(x) achieves higher invariance R(() under the defense's 's randomization space to preserve utility, the adversarial robustness provided by the defense strictly decreases.
In nutshell, we prove the strictly opposite monotonic behavior of robustness and invariance when the classifier shifts its decision boundary and employs majority vote to preserve utility. It shows that stochastic pre-processing defenses provide robustness by explicitly reducing the model's invariance to added randomized transformations, and the robustness disappears once the invariance is recovered.
Experiments
Our experiments are designed to answer the following two questions.
Q1: What properties make applying EOT beneficial when evaluating stochastic defenses?
We show that applying EOT is only beneficial when the defense is sufficiently randomized; otherwise standard attacks already perform well and leave no room for EOT to improve.
Q2: What is the limitation of stochastic defenses when they do have sufficient randomness?
We show trade-off between the stochastic defense's robustness and the model's invariance to the defense itself. Such defenses become less effective when the defended model achieves higher invariance their randomness, as required to preserve utility under the defense.
6.1 Experimental Settings
Datasets & Models. We conduct all experiments on ImageNet [30] and ImageNette [9]. For Ima- geNet, our test data consists of 1,000 images randomly sampled from the validation set. ImageNette ten-class subset of ImageNet, and we test its validation set. We adopt various ResNet [13] models. For defenses with low randomness, we evaluate them on ImageNet with pre-trained ResNet-50 with Top-1 accuracy 75.9%. For defenses with higher randomness (thus requiring fine-tuning), switch to ImageNette and a pre-trained ResNet-34 with Top-1 accuracy 96.9% to reduce the training cost like previous work [34]. These models are fine-tuned the training data processed by tested defenses. As a special case, we also evaluate randomized smoothing on ImageNet using the ResNet-50 models from Cohen et al. [6]. More details of datasets and models can be found in Appendices D. and D.2.
Defenses Metrics. We focus on stochastic defenses allowing us to increase randomness: random- ized smoothing [6] and BaRT [28]. For randomized smoothing, we vary the variance of the added Gaussian noise. For BaRT, we vary the number x of applied randomized transformations. Note that we have evaluated other stochastic defenses and discussed their low randomness in Section 4. We measure the defense's ' performance by the defended model's benign accuracy and the attack's 's success rate, all evaluated with majority vote over of samples that do not satisfy the attack's 's objective prior to the attack but satisfy it after the attack. For example, discard samples that were misclassified before being perturbed in untargeted attacks. Details of the evaluated defenses can be found in Appendix D.3.
500 predictions. The attack's 's success rate is the ratio
Attacks. We evaluate defenses with standard PGD combined with EOT and focus the -ounnde adversary with perturbation budget 6 = 8/255 in both untargeted and targeted settings. We only use constant step sizes and random restarts for PGD. We only conduct adaptive evaluations,

---

Attack Success Rato (%)
Atlack Success Rate (%)
Attack Success Rate (%)
BOT Samples
100
100
100
100
100
1000
100
FOT Samples
99.8
100
100
:00
100
99.5
100
EOT Semples
10
100
100
100
100
100
100
100
99.3
100
100
100
100
100
100
99.6
100
100
:00
99.8
100
100
99.6
100
100
100
1:0
100
100
96.9
99.8
59.8
59.5
100
100
100
99.6
99.6
100
200
100
100
100
99.5
95.8
100
100
130
100
10u
10
20
50
100
200
1000
100
200
500
1000
100
200
5001
1000
PGD Steps
PGD Steps
PGD Steps
(a) Untargeted (step size = 1/255)
(b) Untargeted (step size 2/255)
(c) Untargeted (step size best)
Attack Success Rate (%)
Attack Success Rate (%)
Attack Success Rate (%)
POT Samples
10
93.5 5
99.2
90.9
100
100
100
100
BOT Samples 1I
96.5
99.8
99.9
99.9
100
100
100
BOT Samples
101
96.8
95.8
99.9
100
120
100
100
X3.1
97.6
99.
99.9
100
100
101
95.2
19.1
99.8
99.8
100
59.9
95.9
95.2
95.1
59.9
95.9
130
100
100
44.1
73.4
94.8
96.1
95.2
98.7
99.3
67.4
K3.2
91
92.5
91.8
93
90.5
67.4
83.2
94.8
98.1
99
99.5
99.7
50
100
1000
100
200
500
1000
100
200
500
1000
PGD Steps
PGD Steps
PGD Steps
(d) Targeted (step size = 1/255)
(c) Targeted (step size = 2/255)
(f) Targeted (step size = best)
Figure 2: Evaluation of BaKT"s noise injection defense ImageNet. Standard PGD without applying
EOT (i.e., applying EOT-1) is already good enough, leaving limited space for EOT to improve.
where the defense is included in the attack loop with non-differentiable components captured by BPDA [2]. We also utilize AutoPGD [7] to avoid selecting the step size when it is computationally expensive to repeat experiments in Section 6.3. More details and intuitions of the attack's s settings and implementation can be found in Appendix D.4. Our code is available at https: //gt h/gggttu..... com/ wi Si-ppisstocassticcc. wtt.scccccaiiippppprrreieiiiiiie defenses.
6.2 Q1: Evaluate the Benefits of Applying FOT under Different Settings
In Section 4, we showed that standard attacks are sufficient to break most stochastic defenses due to their lack of randomness. Here, we aim to understand what properties make applying EOT beneficial when evaluating stochastic defenses. We design systematic evaluation of stochastic defenses with different levels of randomness and check if applying EOT improves the attack.
Stochastic Defenses with Low Randomness. We start with BaRT's ss noise injection defense, which perturbs the input image with noise of distributions and parameters chosen at random. While this defense has low randomness, it yields meaningful results. We evaluate this defense with various combinations of PGD and HOT The performance of untargeted and targeted attacks shown in Figure 2. We test multiple step sizes and summarize their best results (discussed in Appendix E)
In this case, standard PGD attacks are already good enough when the defense has insufficient randomness, leaving no space for improvements from EOT. In Figure 2f, both (1) PGD-10 combined with 10T-10 and (2) PGD-100 combined with EOT-1 have near 100% success rates, This result is consistent with our observations in Section 4 in both untargeted and targeted settings?.
Stochastic Defenses with Higher Randomness. We then examine the randomized smoothing defense that adds Gaussian noise to the input image. Although this defense was originally proposed adopt it to evaluate how randomness affects the benefits of
for certifiable adversarial robustness, applying EOT. Similarly, we evaluate this defense with PGD and EOT of different settings with a focus on the targeted attack. The results are shown in Figure 3.
We observe that EOT starts to improve the attack when the defense has a higher level of randomness. For fixed number of PGD steps. applying EOT significantly improves the attack in most of the settings. For a fixed attack strength (i.c., number of gradient computations), applying EOT always outperforms standalone PGD. In Figure 3f, for example, PGD-100 combined with E0T-10 is 5.5% higher than PGD-1,000 with E (40.3% vs. 34.8%).
Note that we do not intend to find heuristic for the best combination of PGD-k and EOT-m, as it is out of the scope of the question that want to answer. However, it is still possible correlate the choice of k and m with the convergence analysis of stochastic gradient descent, which we will briefly discuss in Appendix A.3. "The only caveat is that targeted attacks are more likely to benefit from EOT, as their objectives are stricter and may have better performance with gradients of higher precision.
7

---

Attack Success Rato (%)
Atlack Success Rate (%6
Attack Success Rate (%)
20
A0.9
92.2
95
96.3
97.4
97.9
98.1
86.1
93.5
95.8
96.5
96.8
97.3
92
BOT Samples 10 20
96.1
98.6
95
96.6
97.4
97.9
95.1
BOT Sumples
BOT Sumples 10
10
12.6
63.1
7
96.4
96.6
97
97.2
80.1
89.5
93.1
$4.9
4
95.1
95.6
S0.1
89.5
94.7
96,4
96.8
97.2
97.5
58.9
81.4
91.1
95.7
95.7
96
67.1
80.8
85.9
58.5
85.8
90
91.3
3
67.1
K1.4
91.1
53.6
95.7
56.7
97.2
24.3
43.2
65.5
73.6
76.5
78.4
73.6
24.3
52.8
41.1
42.5
45.4
44.7
44
24.3
43.2
66.7
00,9
87.5
93.1
94.9
50
100
200
500
200
500
1000
PGD Steps
PGD Stops
PGD Stops
(a) 0 = 0.25 (step size= = 2/255)
(b) σ
0.25 (step size- = 4/255)
(c) a = 0.25 (step size- best)
Attack Success Rate (%)
Attack Success Rate (%)
Attack Success Rate (%)
20
27.7
15.4
419
43.7
45.3 46.4
40.1
10 20
30.9
37.5
39.7
41.4
42
42.2
41.8
10 20
30.9
37.5
41.9
43.7
45.5
46.4
45.1
BOT Samples
FOT Samples
BOT Samples
10
22.6
31.2
36.7
39.8
41. 41.6
41.7
24.1
30.7
32.1
34.4
54.6
34.4
34.5
24.1
31.2
36.7
40.3
42.7
45.2
45.6
15.
14.
315 3566 35.3 35.5 35.4
5
173
21.4
23.9 25.6 24.9 25.4
26,1
17.3
24.4
31.
36.2
19
42
41.9
4.81
9.02
13.5 14.
5.51 5:33 6.01 5.81
6.11
4.81
21.9
33.5
5488
10
20
50
200
500
1000
50
100
200
500
1000
200
500
1000
PGD Steps
PGD Steps
PGD Steps
(d) σ- = 0.50 (step size = 2/255)
(c) a = 0.50 (step size = 4/255)
(f) a = 0.50 (step size = best)
Figure: 3: Evaluation of randomized smoothing on ImageNet (targeted attacks). PGD performs well on lower variance (a = 0.25) if running for more steps. For larger variance (a 0.50), applying EOT starts to improve the attack significantly (for a fixed number of gradient computations).
Takeaways. Applying EOT only beneficial when the defense has sufficient randomness, such as randomized smoothing with a = 0.5. This observation suggests that stochastic defenses only make standard attacks suboptimal when they have sufficient randomness. However, most existing stochastic defenses did not achieve this criterion, as we showed in Section 4. We also provide visualizations of adversarial examples under different settings and CIFAR10 results in Appendices E.3 and E.4.
6.3
Q2: Evaluate the Trade-off between Robustness and Invariance
In Section 5, we present theoretical setting where the trade-off between robustness and invariance provably exists; stochastic defenses become less robust when the defended model achieves higher invariance to their randomness. Here, demonstrate this trade-off on realistic datasets, models, and defenses. In particular, we choose defenses with sufficient randomness (achieved in different ways) and compare their performance when being applied to models of different levels of invariance, where the invariance is achieved by applying the defense's randomness to the training data so as to guide the model in learning their transformations.
Randomness through Transformations. We first examine the BaRT defense, which pre-processes input images with k randomly composited stochastic transformations. It represents defenses aiming to increase randomness through diverse input transformations. Since our objective to demonstrate the trade-off, it suffices to evaluate subset of BaRT with x S 6 transformations; this also avoids the training cost of evaluating the original BaRT with x= = 25. Figure shows the performance of this defense with models before and after fine-tuning its processed training data.
In Figures 4a and 4c, we first observe that fine-tuning indeed increases the model's invariance to the applied defense's 's randomness; the utility's dashed green curves are improved to the solid green curves beyond 90%. However, as the model achieves higher invariance, the defense becomes nearly ineffecttiv; the attack's 's dashed red curves boost to the solid red curves near 100%. The same attack's 'ss effectiveness throughout the fine-tuning procedure further verifies this observation, as shown in Figures 4b and 4d. It shows clear trade-off between the defense's robustness and the model's invariance. That is, stochastic defenses start to lose robustness when their defended models achieve higher invariance to their transformations.
Randomness through Noise Levels. We then examine the randomized smoothing defense that adds Gaussian noise to the input image. Unlike BaRT's diverse transformations, randomized smoothing increases randomness directly through the added noise's 'ss variance o². This allows us to rigorously increase the randomness without unexpected artifacts like non-differentiable components. We evaluate
8

---

Resign Accurag (89
Amoll Sacore Bote (2)
100
Besign Accuracyy (89
Amnkk Sucooe Ron. (F)
1007
80-
-0
90
92-
90
before fine-using
before finesuzing
Attek
2
uning
fize
20
Trnndiematios
Epects
Trindfemations
Epocts
(a) Targeted Attacks (view by size)
(b) Targeted Attacks (view by epochs)
(c) Untargeted Attacks
(d) Untargeted Attacks (view by epochs)
(view by size)
Figure 4: Performance of the BaRT defense on ImageNette with different numbers of transformations before and after fine-tuning the model. While the model achieves higher invariance, the defense becomes nearly ineffective", as evident from the top solid red curves in (a) and (c).
Rosign Accuacy (8)
100
100
Attak Sucsee tore (5)
100
100
100
Attak Ior
Notec 511
Benge Accolacy
Naai 515
80
No
0.2
60
90
before
before Gae-tciig
aber Dbe uning
aber fine ninnng
0.2 0.3 Nose Level
10 Epochs
15
20
0.2
10 Epuchs
15
20
Nove Level
(a) Targeted Attacks (view by levels)
(b) Targeted Attacks (view by epochs)
(c) Untargeted Attacks (view by levels)
(d) Untargeted Attacks (view by epochs)
Figure 5: Performance of the randomized smoothing defense on ImageNette with different noise levels before and after fine-tuning the model. While the model achieves higher invariance, the defense becomes less effective*. as evident from the gap between dashed and solid red curves in (a) and (c).
the performance of this defense (a S 0.5) with models before and after fine-tuning on training data perturbed with designated Gaussian noise. The results are shown in Figure 5.
In Figures 5a and 5c, fine-tuning improves the model's invariance, but the defense also becomes significantly weaker during this process. For example, the targeted attack is nearly infeasible when the model is variant to the large noise (o 2 0.3). yet significantly more effective when the model becomes invariant. The fine-tuning process in Figures 5b and 5d also verifies that stochastic defenses become weaker when their defended models become more invariant to their randomness.
Takeaways. For both the BaRT and the randomized smoothing defense, we observe a clear trade-off between the defense's robustness and the model's invariance randomness, especially in the targeted setting. In particular, we find that stochastic defenses lose adversarial robustness when their defended models achieve higher invariance to their randomness. Our finding implies that such defenses would become ineffective when their defended models are perfectly invariant to their randomness.
7 Discussions
In this section, discuss several questions that arose from our study of stochastic pre-processing defenses. Discussions about extensions, limitations, and broader topics can be found in Appendix
What do stochastic pre-processing defenses really do? We show that stochastic pre-processing defenses do not introduce inherent robustness to the prediction task. Instead, they shift the input distribution through randomness and transformations, which results in variance and introduces emrors during prediction. The observed "robustness", in an unusual meaning for this literature, is a result of these errors. This is fundamentally different from the inherent robustness provided by adversarial training [24]. Although defenses like adversarial training still cost accuracy [39, 46], they do not intentionally introduce errors like stochastic pre- pre-processing defenses.
'The defense may not grow stronger with transformations, which is drawback of BaRT that will discuss Appendix D.3. Yet, our evaluations focus on the fact that solid curves are above dashed curves. 'One may also observe trade-off between robustness and utility by examining the curve's horizontal trend. However, we focus the off between robustness and invariance, which manifests in the vertical gap.

---

What are the concrete settings that stochastic pre-processing defenses work? These defenses do make the attack harder when the adversary has only limited knowledge of the defense's transfor- mations, e.g., in a low-query setting. In such a case, the defense practically introduces noise to the attack's optimization procedure, making it difficult for a low-query adversary to find adversarial ex- amples that consistently cross the probabilistic decision boundary. However, it is still possible for the adversary to infer pre-processors in a black-box model and compute their expectation locally [10, 41], unless the randomization space changes over time. Our theoretical analysis considers a powerful adversary with full knowledge of the defense's 's randomization space; hence can optimize directly towards the defended model's 's decision boundary in expectation. The other setting is randomized smoothing, which remains effective in certifying the inherent robustness of a given decision.
What are the implications for future research? Our work suggests that future defenses should try to decouple robustness and invariance; that is, either avoid providing robustness by introducing variance to the added randomness or the variance only applies to adversarial inputs. This implication is crucial as the research community continues improving defenses through more complicated transformations. For example, in parallel to our work, DifiPure [25] adopts complicated stochastic diffusion process to purify the inputs. However, fully understanding DiftPure's 's robustness requires substantial effort due to its complications and high computational costs, we will discuss in Appendix F.1
How should we improve stochastic defenses? Stochastic defenses should rely on randomness that exploits the properties of the prediction task. One promising approach is dividing the problem into orthogonal subproblems. For example, some speech problems like keyword spotting are inherently divisible in the spectrum space [1], and vision tasks are divisible by introducing different modali- ties [43], independency [18], or orthogonality [45]. In such cases, randomization forces the attack to target all possible (independent) subproblems, where the model performs well on each (independent and) non-transferable subproblem. As a result, defenses can decouple robustness and invariance, hence reducing the effective attack budget and avoiding the pitfall of previous randomized defenses. While systematic guidance for designing defenses (and their attacks) remains an open question, we summarize some critical insights along this direction in Appendix F.2.
What are the implications for adaptive attackers? Our findings suggest that an adaptive attacker needs to consider the spectrum of available standard attack algorithms, instead of just focusing on a given attack algorithm because of the defense's s design. As we discover in this paper, EOT can be unnecessary for seemingly immune stochastic defenses, yet its application to break these said defenses gives false impression about their security against weak attackers. When evaluating the robustness of defense, the adaptive attack should start by tuning standard approaches, before resorting to more involved attack strategies. This approach helps us to identify the minimally capable attack that breaks the defense and develop a better understanding of the defense's 's fundamental weaknesses.
8 Conclusion
In this paper, we investigate stochastic pre- rre-processing defenses and explain their limitations both empirically and theoretically. We show that most stochastic pre-processing defenses are weaker than previously thought, and recent defenses that indeed exhibit more randomness still face a trade-off' between their robustness and the model's invariance to their transformations. While defending against adversarial examples remains an open problem and designing proper adaptive evaluations is arguably challenging, we demonstrate that stochastic pre-processing defenses are fundamentally flawed in their current form. Our findings suggest that future work will need to find new ways of using randomness that decouples robustness and invariance.
Acknowledgement
We thank all anonymous reviewers for their insightful comments and feedback. We would like to acknowledge our sponsors, who support our research with financial and in-kind contributions: the DARPA GARD program under agreement number 885000, NSF through award CNS-2003 129, CIFAR through the Canada CIFAR AI Chair program, and NSERC through the Discovery Grant and COHESA Strategic Alliance. Resources used in preparing this research were provided, in part, by the Province of Ontario, the Government of Canada through CIFAR, and companies sponsoring the Vector Institute. We would like to thank members of the CleverHans Lab for their feedback.
10

---

References
[1] Shimaa Ahmed, Iia Shumailov, Nicolas Papernot, and Kassem Fawaz. Towards more robust keyword spotting for voice assistants. In 31st USENIX Security Symposium (USENIX Security 22), pages 2655- 2672, Boston, MA, August 2022. USENIX Association. URL httth::t////at usenix org/ conference, http://ccrrrrttt//eeeeeetttttaae hwaeeetttttooaonaadd.aeaaaa
[2] Anish Athalye, Nicholas Carlini, and David A. Wagner. Obfuscated gradients give false sense of security: Circumventing defenses to adversarial examples. In Jennifer G. Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässom Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pages html.
PMLR, 2018. URL http:/ http:://prrreee ppwppeeeddggg.... mlr press/ /asass/v88 vv00 athalye htmm...ml.
[3] Anish Athalye, Logan Engstrom, Andrew Ilyas, and Kevin Kwok. Synthesizing robust adversarial examples. In Jennifer G. Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Leurning. ICML 2018, Stockholmsmüssan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedingy of Machine Learning Rexearch, pages 284-293. PMLR, 2018. URL http: SttL::t/pproceeediiii ppw./eeieceens...... mlr. . prwss/ v80/ wtt/aaaaaael8...t/ html.
[4] Battista Biggio. Igino Corona. Davide Maiorca, Blaine Nelson, Nedim SIndic, Pavel Laskov, Giorgio Giac- into, and Fabio Roli. Evasion attacks against machine learning at test time. In Hendrik Blockeel, Kristian Kersting, Siegfried Nijssen, and Filip Zelezný, editors, Machine Learning and Knowledge Discovery in
Databases - European Conference, ECML PKDD 2013, Prague, Czech Republic, September 23-27, 2013, Proceedings, Purt III, volume 8190 of Lecture Notes in Computer Science, pages 387-402. Springer, 2013. 31 25, URL https: //t.///oooo/o/// org/ 10. 1007 00000/97--20 99////78-33-1 400-2---094-333 3_25.
doi:
[5] Nicholas Carlini and David A. Wagner. Towards evaluating the robustness neural networks. 2017
IEEE Sympoxium on Security and Privacy, SP 2017, San Jose, CA, USA, May 22-26, 2017, pages 39-57, 2017. doi: 10.1 1011//..000...44 49. URL https:
www.oogg//.00........o 11.......//.. 2017 .49.
[6] Jeremy M. Cohen, Elan Rosenfeld, and J. Zico Kolter. Certified adversarial robustness via random- ized smoothing. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 1310-13200 PMLR, 2019. URL http:/ http://prrccediing. mlr. wwwpp/evrr1 v97 cohen19c...c//// html.
[7] Francesco Croce and Matthias Hein. Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free free attacks. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 2206-2216. PMLR, 2020. URL http: http::::/ppoccceeinneeeeoooeeeee mlr. press/ /v11 crwce20b.bbcoo 1atps////11//ccce0bbbbb html.
[8] Guneet S. Dhillon, Kamyar Azizzadenesheli, Zachary C. Lipton, Jeremy Bernstein, Jean Kossaifi. Aran Khanna, and Animashree Anandkumar. Stochastic activation pruning for robust adversarial defense. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenRevicw.net, 2018. URL httpa:/ http::////peeeeeeeeeeeeee net. forum? ? HRRHZZZ
[9] FastAI. The imagenette dataset. URL htttts://g/tiie http:/huub.com/tttttt/ainaea
[10] Yue Gao, Ilia Shumailov, and Kassem Fawaz. Rethinking image-scaling attacks: The interplay between vulnerabilities in machine learning systems. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato, editors, International Conference Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pages 7102-7121. PMLR, 2022. URL https: httpas////coceeeepp/e/eee mlr, www.spressiiieeeeee press//1662/gao222, html.
[11] Saeed Ghadimi and Guanghui Lan. Stochastic first- and zeroth- methods for nonconvex stochastic programming. SIAM J. Optim., 23(4):2341-2368 2013, doi:
URI. https:
org/10. 10//10.111
[12] Chuan Guo, Mayank Rana, Moustapha Cissé, and Laurens der Maaten. Countering adversarial images using input transformations. 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018. URL https: http:/:////pe///eeeeeeeee wwt./eet/oorreee //ope/rrvree..ee///oouull Sy-SSy7CIWCb.
[13] Kaiming He, Xiangyu Zhang. Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2016, Las Vegas, NV, USA, June 27-30, 2016, pages 770-778, 2016. doi: 10.1 10.1109/CVPR.2016.00 URL https://doi. org/10.
1109/CVPR. 2016.90.
11

---

[14] Sandesh Kamath, Amit Deshpande, Subrahmanyam Kambhampati Venkata, and Vineeth N Bala- subramanian. Can we have all? the trade-off between spatial and adversarial robustness of neural networks. M. Ranzato, A. Beygelzimer, K. Nguyen, S. Liang. J. W. Vaughan, and Y. Dauphin, editors, Advances in Neural Information Processing Systems, volume 34, pages 27462- neurips. http://a.......cppa////000001000
27474, Curran Associates, Inc., 2021. URL e6f 11111044554553354444000022000000
[15] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. URL http: //arxiv .tggs//oooooo/ooooooooooo org/abs/ ab//////../1//./////////////////
[16] Alex Krizhevsky, Geoffrey Hinton, et Learning multiple layers features from tiny images. 2009.
[17] Mathias Lécuyer, Vaggelis Atlidakis, Roxana Gcambasu, Daniel Hsu, and Suman Jana. Certificd robustness to adversarial examples with differential privacy. In 2019 IEEE Symposium on Security and Privacy, SP 2019, San Framcisco, CA, USA, May 19-23, 2019, pages 656-672. IEEE, 2019. doi: 10.1 10.1109//P.009..00 0004444 URL https:: //tp::://///...// wwg.i...oo.........o
wwg/oog.//..oo..o..oo 10////.1110 1109/S1
[18] Alexander Levine and Soheil Feizi. (de)randomized smoothing for certifiable defense against patch attacks. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florin Bal- can, and Hsuan- Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NewrIPS 2020, Decem- ber 6-12, 2020, virtual, 2020. URL. https:/ http:a///cpocceigg..... neuriiinnnnnnuui...........e..ee www.wea..cepppppeeeeeee wttpcccpppppp////////e/p 37ce0875420b2dbeeeo cas.aae4eeccs5333e366333333 Setas-bbstrattthteeee
[19] Yingzhen Li, John Bradshaw, and Yash Sharma. Are generative classifiers more robust to adversar- ial attacks? In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th In- ternational Conference on Machine Learning, ICML 2019. 9-15 June 2019, Long Beach. California. USA, volume 97 of Proceedings of Machine Learning Research, pages 3804-3814. PMLR, 2019. URL http:/ http:://proceedingg . mlr. www.epressssve /ttes//v7/// /1t.a.......... html.
[20] Ilya Loshchilov and Frank Hutter. SGDR: stochastic gradient descent with warm restarts. In Sth Interna- tional Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017. URL http:p::////pppeeeeeeeeeeeeeeeee net htt///frmmddddkkafae
[21] Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL https: wwwpo/wwwweeeeeeoooepp/e wwt/torumnt// http//oormniddBkgdiii Bd-Bkg6R1
[22] James Lucas, Shengyang Sun, Richard S. Zemel, and Roger B. Grosse. Aggregated momentum: Stability through passive damping. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 20/9, OpenReview.net, 2019. URL https:// net/forum? id=Syxt5oC5YQ.
[23] Clare Lyle, Mark van der Wilk, Marta Kwiatkowska, Yarin Gal, and Benjamin Bloem-Reddy, On the benefits of invariance in neural networks, 2020.
[24] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In 6th International Conference on Learning Repre- sentations, ICLR 2018, Vancouver, BC, Canada, April 30- - May 3, 2018, Conference Track Proceedings, 2018. URL htwp::ttt////ee /ttp:///ee/eeeeeee//e/eeeee URI.bhtpe::/ogenrevieee sespeenrrieesnntt/ooretteeeeeeee www.:n/ooooommddd.aaaaaatatae
[25] Weili Nie, Brandon Guo. Yujia Huang, Chaowei Xiao, Arash Vahdat, and Animashree Anandkumar. Diffusion models for adversarial purification. In Kamalika Chaudhuri, Stefanie Jegelka. Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato, editors, International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pages 16805- 16827. PMLR, 2022. URL https: http///occeedeng///e mlr wwwpppeereee///eeeeeepp.pe press//162/niee2a.. html.
[26] Tianyu Pang, Kun Xu, and Jun Zhu. Mixup inference: Better exploiting mixup to defend adversarial attacks. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia. April 26-30, 2020. OpenReview.net, 2020. URL http::////pprrrrrrreeee//o/oo/d CVV
[27] Rafael Pinot, Laurent Meunier, Florian Yger, Cédric Poiller, Yann Chevaleyre, and Jamal Atif. On the robustness of randomized classifiers to adversarial examples. Machine Learning, pages 1-33, 2022.
12

---

[28] Edward RafT, Jared Sylvester. Steven Forsyth, and Mark McLean. Barrage of random transforms for adversarially robust defense. In IEEE Conference on Computer Vision and Puttern Recognition, CVPR 2019, Long Beach, CA. USA, June 16-20, 2019, pages 6528-6537. Computer Vision Foundation / IEEE, 2019. doi: 10.1109/CVPR.201 2019.0069. URL http://openaccest theeeaccesss.eeeii.eeeeee theevf. com/ content, __t_____________________ 20119htmm/Raff.... Transforms wwt.ooovverrrrrall....... SoobusttDeefenne Ccpp_________________ 2019 2019_papee _apprr htmml.
of _andom__
[29] Kevin Roth. Yannic Kilcher, and Thomas Hofmann. The odds are odd: A statistical test for detecting adversarial examples. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 5498-5507. PMLR, 2019. URL http://prroceedinga mlr. pww.rppeesssss htt99//roti rot./99t.111... html.
[30] Olga Russakovsky. Jia Deng. Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bemsttein Alexander C. Berg, and Fei-Fei Li. Imagenet large scale visual recognition challenge. Int. J. Comput. Vis., 115(3):211 252, 2015, doi: 10.1007/s 1263-015 015-0816-1-- URL /estts:///oi. org/ 10. 1007 / 11111111611110000
[31] Hadi Salman, Mingjie Sun, Greg Yang, Ashish Kapoor, and J. Zico Kolter. Denoised smoothing: A provable defense for pretrained classifiers. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Had- sell. Maria-Florina Balcan, and Hsuan- Tien Lin, editors. Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, De- cember 6-12. 2020, virtual, 2020. URL https: attpss//proceeding http///ooeeenn..eeeeeeee www.snnww.rscooooooooeee Abstract. html.
[32] Pouya Samangouei, Maya Kabkab, and Rama Chellappa. Defense-gan: Protecting classifiers against adver- sarial attacks using generative models. 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018. URL https::////e/ http///pppneeeeeeeeeee net wwt/ffoummmeeeee (oerummid--i witimndddd-i.dd--...
[33] Vasu Singla, songwei Ge, Basri Ronen, and David Jacobs. Shift invariance reduce adver- sarial robustness. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 1858- 1871. Curran Associates, Inc., 2021. URL hattps://proceeding: weweeedddnnnn.nuuipp..ee. neuripa. wwt.epp..ccppppere///..... /2//1/// Paper. .df.
0e7 (7dae44cc766eee6455eeec...
[34] Chawin Sitawarin. Zachary Golan-Strieb, and David Wagner. Demystifying the adversarial robustness of random transformation defenses. The AAAI-22 Workshop on Adversarial Machine Learning and Beyond, 2021. URL https: //tp://///pp/eeeeeeeeeee ntt/teernnnneeee wttp//rrmmddd-ddsFyyaadea
[35] Yang Song. Taesup Kim, Sebastian Nowozin, Stefano Ermon, and Nate Kushman. Pixeldefend: Leveraging generative models to understand and defend against adversarial examples. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30- May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018. URL https: petttts://pperreee /ppnrevieeeeeeeeeee net/ www.ooiddrruruuoo...
[36] Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Frhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In Yoshua Bengio and Yann LeCun, editors, 2nd International Conference on Learning Representations, ICLR 2014, Banff. AB, Canada, April 14-16, 2014, Conference Track Proceedings, 2014. URL http:://aazts org/ abs / 1312. 6199.
[37] Christian Szegedy, Vincent Vanhoucke, Sergey loffe, Jonathon Shlens, and Zbigniew Wojna. Rethinking the inception architecture for computer vision. In 2016 IEEE Conference on Computer Vision and Pottern Recognition, CVPR 2016, Las Vegas, NV, USA, June 27-30, 2016, pages 2818-2826. IEEE Computer doi: 10. WWW//CVPR.201..... URL https: //doii org/10. 10. 1 1109/1/11VM /VVRR 2016.300
Society, 2016.
[38] Florian Tramèr, Nicholas Carlini, Wieland Brendel, and Aleksander Madry. On adaptive attacks to adversarial example defenses. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria- Florina Balcan, and Hsuan-Tien Lin, editors. Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, Decem- ber 6-12, 2020, virtual, 2020. URL /ttpee////cccccg..... nwurips. http:/tt..p.p...epeeee/////////e (etapper/220//aaae 11F9888cc471887744433388882
Abstract .tml.
[39] Dimitris Tsipras. Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry. Ro- bustness may be at odds with accuracy. In 7th International Conference on Learning Representa- tions, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net. 2019. URL https: // //openreview net netf/forrmm/.eeyyyxssorrrr
13

---

[40] Chang Xiao, Peilin Zhong, and Changxi Zheng. Enhancing adversarial defense by twiiners-take-all In 8th International Conference Learning Reprexentationss ICLR 2020, Addix Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL WtLLLttss////pezeeeeee
net net./ooummiddSSggyyoeaeeee
[41] Qixue Xiao, Yuféi Chen, Chao Shen, Yu Chen, and Kang Li. Seeing is not believing: Camouflage attacks on image scaling algorithms. Nadia Heninger and Patrick Traynor, editors, 28th USENIX Security Sympo- sium. USENIX Security 2019, Santa Clara, CA, USA, August 14-16, 2019, pages 443-460. USENIX Asso- ciation, 2019. URL https:/ / //www usenix.e....... xiao.
[42] Cihang Xie, Jianyu Wang, Zhishuai Zhang, Zhou Ren, and Alan L. Yuille. Mitigating adversarial effects through randomization. 6th International Conference Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018. URI.
[43] Karren Yang. Wan-Yi Lin, Manash Barman, Filipe Condessa, and J. Zico Kolter. lending multimodal fusion models against single-source adversaries. In IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2021, virtual, June 19-25, 2021, pages 3340-3349. Computer Vision Foundation / IEEE, 2021. doi: 10.1 10.100V4224444 00335. URL httpps:/openaccees: thecvf. /ttp///et/////222///allaaa/////a Mul Laaiiodal_uusiion Lodeeoo Models _
enddiing... html.
[44] Yuzhe Yang, Guo Zhang, Zhi Xu, and Dina Katabi. Me-net: Towards effective adversarial robustness with matrix estimation. Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, PMLR, 2019. URL
USA, volume 97 of Proceedings of Machine Learning Research, pages http://proceedlnge mlr press/ eevess/v9//// h97////gg1/ yang99e... html.
[45] Zhuolin Yang, Linyi Li, Xiaojun Xu, Shiliang Zuo, Qian Chen, Pan Zhou, Benjamin I. P. Rubinstein, Ce Zhang, and Bo Li. TRS: transferability reduced ensemble via promoting gradient diversity and model smoothness. In Marc' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Syxtems 34: Annual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pages 17642-17655, 2021. URL https: http///cceeeig....// neurips cc/paper/2021 ///hhhhhhh///// Abstract html.
[46] Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric P. Xing, Laurent El Ghaoui, and Michael Jordan. Theoretically principled trade-off between robustness and accuracy. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 Proceedings of Machine Learning Research, pages 7472-7482 7482. PMLR, 2019. URL http://proceeddngg mlr. www.:mww...p....e..mmmmmmmmmeeee press/v97 http//99//aaaaa/a /t//haagg199 html.
14

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Appendix F.3.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See Appendix F.3.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] We outline all details for theoretical results in Appendix C.
(b) Did you include complete proofs of all theoretical results? [Yes] We include complete
proofs in Appendix C.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material as URL)? [Yes] Our code is available in the supplementary material.
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [Yes] We specify brief settings in Section 6.1 and provide complete details in Appendix D.
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [No] We study stochastic defenses, whose prediction procedure is already majority vote over multiple times.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Appendix D.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
We only included our code for evaluation.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A] We only used public datasets as discussed in Section 6. (e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A] We did not use such data.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
15


Reviews:
[{"review_id": "nKRRBEEzeem", "reviewer": "Reviewer_wZxu", "summary": "This work investigates stochastic pre-processing defenses both empirically and theoretically. Specifically, the authors first revisit previous stochastic pre-processing defenses and explain why such defenses are broken. Then, the authors study recent stochastic defenses that exhibit more randomness and show that they also face key limitations.\n\n－－post rebuttal－－\nThank the author for providing detailed rebuttals. My major concerns are addressed. I raise my score and tend to accept this paper.", "questions": "I expected systematic guidance to design attacks and defenses regarding randomness from this paper. It will bring more value to the community if the author can provide one. The one provided in Discussion section is a good starting point.\n\nI also encourage the authors to provide the expected experiments listed in weaknesses.\n", "limitations": "This work provides an analysis of the existing techniques, namely, stochastic defense. The new technique is the focus of this paper. The only limitation of this work is its novelty.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. This work focuses on an interesting topic, namely, the effectiveness of stochastic defenses.\n2. In general, the paper is well organized.\n\nWeaknesses:\n1. My major concern is the novelty of the findings. The finding that applying EOT is only beneficial when the defense is sufficiently randomized is trivial to me. The other finding is that a trade-off between the model’s robustness provided by the defense and its invariance to the applied defense, which is also expected. When the model becomes invariant to the applied randomness, the function modeled by a model is more ‘deterministic’. The randomness is expected to bring less robustness to the model.\n\n2. Some claims made in this paper are inappropriate, to my knowledge, e.g., in Line 46-47. The work [2] shows that EOT can be used to break stochastic defenses. However, the necessity of EOT is not claimed since they mainly aim to show that stochastic defenses can be easily broken with EOT.\n\n3. Besides the success rate, an analysis of created adversarial noises should be presented. What is the difference between the adversarial noises created by PGD(n*m) or PGD(n)+EOT(m)? Similarly, what is the difference between the adversarial noises created on models with different degrees of randomness? The visualization of the noises might reveal more interesting conclusions.\n\n4. It is great that the main experiments are conducted on ImageNet dataset. It will be better if the experiments on a smaller dataset, e.g.CIFAR10, can be provided. It is not clear if the experimental observation still holds when the input space is smaller.\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "gUx6_iCNaeV", "reviewer": "Reviewer_G9xL", "summary": "\"On the Limitations of Stochastic Pre-processing Defenses\" discusses strategies for the adequate evaluation of adversarial attacks against systems defended by stochastic components. Previous work generally considers expectation-over-transformations to be necessary to attack these defenses, but the submission shows that merely running standard defenses with larger step budgets can often be sufficient in overcoming these defenses. The submissions supplements this finding with further analysis on the interactions of robustness and invariance with the stochastic nature of these defenses.", "questions": "As described above, how would a stochastic defense based on diffusion processes be categorized? Do the findings of this work for older defenses also hold for these newer stochastic defenses?", "limitations": "n.a.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I like the clarity of writing and presentation of the findings in this work. The grouping of stochastic defenses into defenses with and without meaningful stochasticity is nicely illustrated and exemplified.\n\nThe experimental evaluation underpins these findings for two defenses, barrage-of-transformations and randomized smoothing. Overall I don't have a lot of say here, I liked the evaluations done by the authors and find the results interesting. The overall topic is not groundbreaking, but reinvestigating the properties of stochastic preprocessing is, in my opinion, illuminating for the wider community. \n\nThe only minor weakness I see is that the evaluations center on two classic stochastic defenses. Recently there has been a lot of renewed interest in stochastic defenses, especially based on diffusion processes (For example Nie et al, \"Diffusion Models for Adversarial Purification\n\" at ICML this year). I think the impact of this submission could be improved by also considering one such \"newer\" attempted adversarial defense, where would this defense fall in the categorization of stochastic defenses proposed in this work?", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "IuOL07UHv1R", "reviewer": "Reviewer_SAKU", "summary": "This paper contains three main contributions. First, this paper shows that using EoT ($m>1$) is not always necessary to break randomized defenses, i.e., it does not necessarily save the number of gradient computations. Second, it shows a theoretical result in a toyish setting that the robustness of randomized models is at odds with their utility (accuracy). This is not an impossibility result but rather, the authors propose some settings where such a trade-off exists. Lastly, the paper supports the second the previously mentioned theoretical results with empirical ones on two types of defenses (BaRT and randomized smoothing).", "questions": "1. What about the robustness-invariance trade-off in the targeted setting? The invariance is needed for accuracy when it represents $F_\\theta(x) = y$, i.e., \"prediction has to be correct after the random transform.\" However, the defender needs *no* invariance for the wrong class, correct? We don't care, almost in all cases, that $F_\\theta(x) = F(x)$ when they are both wrong. The defense can surely use this to its advantage. I expect that the robustness-invariance trade-off is far less important, if it exists at all, in the targeted setting. \n2. In Figure 4a and 4c, we can see that the red and the green solid lines start to diverge at large $\\sigma$. This means that the trade-off somewhat disappears here, i.e.,  you gain more robustness while the accuracy does not go down. Why does this happen on randomized smoothing and not BaRT? Why is this the case? Could it be that the attack is sub-optimal with large $\\sigma$? It might be good to show that the attack does indeed converge by no large $m$ and $k$ could possibly increase the attack success rate further.\n3. Do all attacks in the paper use AutoPGD? If so, did the authors take into account the observation that EoT is unnecessary could be, at least partially, an effect of the adaptive step size from AutoPGD?", "limitations": "This is adequately discussed in Appendix F.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n1. The paper addresses an interesting yet under-explored problem. Rigorous studies are lacking on randomized models/defenses.\n2. While the setup for the theoretical part is toyish, the results are comprehensive. I would have missed the more interesting results, in my opinion, in the appendix if I didn't check out Appendix C.2. The paper might benefit from bringing up or summarizing some of these results in the main paper.\n3. Experiment setup seems mostly rigorous and up to date with recent works. \n4. The presentation is good. The main messages are all easy to understand, and the results mostly support the claims well.\n\n# Weaknesses\n1. The main and only major weakness is that the overall contribution is slightly limited (justified in a. and b. below). Personally, I find the two main observations in this paper interesting. However, the paper seems to miss the final part, i.e., I find the following questions unanswered: What's next? What does this mean to future research? How do we improve defenses? Should we abandon randomized defenses? What are concrete settings that this defense works (with some supporting results)?  \n  a. *Theory*: As mentioned in the summary, there is no guarantee that the trade-off between utility, i.e., invariance, and robustness must hold. The results do cover a reasonable set of settings used by the proposed defenses, but none really exclude the possibility of using other forms of randomness or aggregation methods that may not conform to this trade-off or in general achieve a better trade-off.  \n  b. *Empirical*: I don't believe that the empirical contribution quite makes up for the limitation in the theoretical part. Additional experiments on more models and defenses might be good. Surely, all defenses are not made equal and so they should not be on the same trade-off curve. Could the authors make a stronger claim about which defense might look more promising? Or maybe a heuristic to properly choose $m$ and $k$ without just trying out a lot of them?\n\nNote that I'm not set in stone about this. The authors and the other reviewers may convince me otherwise.\n\n# Minor Weaknesses\nI think of these as suggestions or room for improvement rather than things I penalize this paper for.\n1. I believe that Pinot et al. [2021] (https://arxiv.org/abs/2102.10875) might be related to this work, at least remotely. This work is not peer-reviewed as far as I can find so I'm not imposing any penalty. However, I'd recommend citing and discussing their result as well since they also show many solid theoretical results on randomized defense.\n2. Maybe the comparison between the benefits of the number of PGD steps ($m$) and the number of EoT samples ($k$) can be put in the perspective of stochastic gradient descent. For instance, from the central limit theorem, we know that variance decreases by $1/k$ and $1/\\sqrt{k}$ for standard deviation. We also know that the variance of the gradient estimates affects the convergence rate of SGD (see this [paper](https://cpn-us-w2.wpmucdn.com/sites.gatech.edu/dist/f/330/files/2016/02/NonconvexSA-Revision-9-25-13.pdf)). This might allow one to predict, in theory, the optimal value of $k$ and $m$ given $\\sigma$ and $k \\times m$. \n3. Presentation of Figure 3 and 4: I don't think the epoch views are necessary. I would also recommend plotting the attack success rate or robust accuracy vs clean accuracy to show the trade-off better. \n\n# Very Trivial Weaknesses\n1. Reference [10] and [11] are duplicates.\n2. It's a bit difficult to compare a fixed number of gradient computation ($k \\times m$) in Figure 1 and 2. It just takes another little step to multiply the numbers. I don't have a good suggestion for this without significantly changing the figure (e.g., x-axis is just $k \\times m$).", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept