Exploiting Certified Defences to Attack Randomised Smoothing
Authors: Andrew Craig Cullen
Paul Montague
Shijie Liu
Sarah Monazam Erfani
Benjamin I. P. Rubinstein
Venue: Submitted to ICLR 2023 (2023)
Keywords: adversarial
attack
certified robustness
machine learning

Abstract: Certified guarantees of adversarial robustness play an important role in providing assurances regarding a models output, irrespective of the behaviour of an attacker. However, while the development of such guarantees has drawn upon an improved understanding of attacker behaviour, so too can certified guarantees be exploited in order to generate more efficient adversarial attacks. Within this work, we explore this heretofore undiscovered additional attack surface, while also considering how previously discovered attacks could be applied to models defended by randomised smoothing. In all bar one experiment our approach generates smaller adversarial perturbations for more than $70 \%$ of tested samples, reducing the average magnitude of the adversarial perturbation by $13 \%$.

Under review as a conference paper at ICLR 2023
EXPLOITING CERTIFIED DEFENCES TO ATTACK RANDOMISED SMOOTHING
Anonymous authors Paper under double-blind review
ABSTRACT
Certified guarantees of adversarial robustness play important role in providing assurances regarding models output, irrespective of the behaviour of an attacker. However, while the development of such guarantees has drawn upon improved understanding of attacker behaviour, so too can certified guarantees be exploited in order to generate more efficient adversarial attacks. Within this work, explore this heretofore undiscovered additional attack surface, while also considering how previously discovered attacks could be applied models defended by randomised smoothing. In all bar one experiment our approach generates smaller adversarial perturbations for more than 70% of tested samples, reducing the average magnitude of the adversarial perturbation by 13%.
INTRODUCTION
The observation that neural networks' exhibit particular sensitivity to adversarial behaviours has motivated numerous recent works. That such networks are frequently deployed within contexts for which incentives for adversarial behaviour exist makes guarding against such interventions to be of paramount importance.
Our understanding of this problem space has been heavily driven by the development new perspectives potential attack vectors, stemming the original works in adversarial examples through to data poisoning backdoor attacks, model stealing, transfer attacks and more. While uncovering such attack vectors has the potential to compromise deployed models, there is prima facie evidence that any security provided by a lack of knowledge is illusory. As such, it is clear that understanding new attack vectors has the potential to produce stronger defences, due the implicit coupling between attacks and their defences.
In contrast this implicit coupling, recent works have focused upon the construction of certified guarantees of adversarial robustness, which verify that a models output will be unchanged over all adversarial behaviours (subject set of loose constraints). The calculations of such guarantees are performed in parallel to inference, and are achieved by way of modifications to the mechanisms of the model. One common backbone for such techniques is randomised smoothing, which can be performed without requiring any modifications to the core training loop beyond pre-processing and post-processing step.
However, while models incorporating certified guarantees should be more adversarially robust than their counterparts, within this work we consider how such models can still be attacked a fashion that yields small adversarial perturbations. Such consideration is important, as we also identify heretofore undiscovered new attack vector, which exploits the very nature of the certified guarantee to identify smaller adversarial perturbations than any other tested approach. To explore the nature of this novel attack surface, this work makes the following contributions:
Demonstrating how general attacks can be constructed against models defended by ran- domised smoothing. This is achievable by exploiting the Gumbel-Softmax within either white-box or surrogate modelling attacks to render the models differentiable. In doing so, we are able to exploit the fact that randomised smoothing inherently smooths the underlying gradients, making them easier to attack.
Introducing a new attack that exploits certification guarantees in both the original and malicious classes by dynamically optimising the step-size. Correct class predictions exploit

---

Under review as a conference paper at ICLR 2023
the certification to eliminate parts of the search space, incorrect class predictions used to focus the search process. In doing so we are able to identify smaller adversarial perturbations than the best tested alternative in over 70% of all tested samples, resulting in more than 13% reduction in the median perturbation.
Assessing the performance of certified guarantees of adversarial robustness, through com- parison to the magnitude of best-identified adversarial perturbations in T2 norm space.
2 RELATED WORK
It is well known that carefully crafted perturbations can change the output of learned models without requiring change in the semantic properties of the input sample (Biggio et al. 2013). Such perturbed samples are known as adversarial examples. Most common learned models, including neural networks (Szegedy et al., 2013) consistently misclassify adversarial examples and furthermore output highly confident but incorrect predictions. One significant driver of this behaviour appears to be the piecewise-lime linear interactions within neural networks (Goodfellow et al. 2014).
While many attacks exist, focus key representative approaches. Each of these are white-box, untargeted attacks that use gradient-based optimisation to construct adversarial perturbations. Of these, the Iterative Fast Gradient Method (Dong al., (018) variant of Projected Gradient Descent (PGD) (Carlini & Wagner 2017) allows adversarial examples to be iteratively constructed by way of
X5: -e - -CIIV (1
V [x -)
X
(1)
This process exploits gradients of the loss J(0, x, v) construct steps, subject to step-size weighting parameter and a projection operator P that ensures that Xx+1 is restricted to the feasible input space, typically [0. 1]d for a d-dimensional input space. Many PGD extensions exist, including
momentum- variants (Dong et al.) 2018) and AutoAttack (Croce & Hein 2020).
The latter of these alternate approaches has been shown be highly effective in identifying adversarial examples, and as such we also tested performance against Auto/ttack within this work. In contrast to PGD, which sets a fixed step-size c, AutoAttack algorithmically specifies the step-size at each stage of its iterative process. Instead AutoAttack attempts to converge upon adversarial examples with a pre-specified L2 norm perturbation magnitude, which obtusely also labelled as e. This inherently problematic within problem domains for which minimising the perturbation magnitude is important, the requirement to pre-specify the perturbation magnitude is an inherently limiting factor. Our preliminary investigations have suggested that the only way to minimise the perturbation magnitude is to perform a greedy search over a range of possible pre-specified magnitudes.
Carlini & Wagner (C-W) constructs adversarial perturbations by way of the minimisation problem
min ||x' x12 max (fax(ff(x()) * fo(x') ). =+
in terms of the trained model fo (x) (with weights 0). The latter term of Equation 2 compares the logit value of the target class i with that of the next most likely class, subject to the parameter This criteria then solved in the fashion Equation] D using gradients from Equation 2
Another popular attack is DeepFool, which is untargetted 12-norm attack (Moosavi-Deztoolli iet al. 2016) that interchanges between attacking a lincarised variant of the model and updating the lincarisation based upon gradient steps. This lincarisation allows for automatic step-size control across the iterative process.
ATTACKS AGAINST CERTIFIED DEFENCES
Randomised smoothing is a common approach for constructing certified guarantees by constructing expected class outputs through Monte Carlo sampling across samples perturbed by randomised noise. While this is a test-time process, the sensitivity of the model to perturbations may be decreased by performing adversarial training against single draws from the noise distribution. The magnitude of the guarantee of predictive invariance for perturbations up to some magnitude r in a specified L, norm space was first shown by way of differential privacy (Lecuyer al. 2019 Dwork et al. 2006). More
2

---

Under review as a conference paper at ICLR 2023
recent works has utilised Rényi divergence (L et al. 2019) and worst-case behaviours parametrisation (Cohen et al. 2019; Salman et al. 2019) to provide guarantees. We place particular focus upon the latter of these approaches, which introduced the lower bound guarantee of class invariance
Φ (E)) + (E1))
(3)
subject to the normal CDF Φ; in terms of the two largest class expectations Eg and E₁, which are calculated terms of a one-hot encoding of the model's output in response to noise
Y, 1, Zj max Zk
X ~~ N~xxxx,
Ž - (X
Ep BD Σ y1
L0, 0, otherwise.
(4)
We are interested in estimating Y as our ideal smoothed predictions. By taking a sample 'D of iid. draws x, 2, y.. y of these random variables, may form unbiased estimates of these ideal expectations by expectations with respect to the empirical distribution on D.
In the absence of randomised smoothing, the objective of an attack is simple: to change the predicted class of the model. However, under randomised smoothing that the output is expectations (with an associated confidence interval) introduces important question regarding the nature of an attack within this context. If an idealised output has a no overlap between the confidence interval of the class with the highest expectation and those from all other classes, is enough for an attack to simply introduce an overlap between the confidence intervals associated with the largest two classes? While such a definition has utility, the overlap between predicted classes would be simple trigger for external validation, decreasing the likelihood of success. This in turn suggests that an adversarial perturbation should instead be defined as one for which the associated class has an associated confidence interval that is strictly larger than that of the label class. Such definition naturally aligns with that of certified defences of adversarial robustness.
3.1 THREAT MODEL
To formally define such an attack, consider model fa(x; a, N) which acts upon inputs [0, 1jd and learned parameters 0, which produces prediction of class if the estimated expectation- based upon adding N draws of (0, o²) Gaussian distributed noise to the input sample-satiste
[x)) [x))
vk E
(5)
where F4 and F... respectively represent the lower and upper confidence bounds class expectations of classes and k to some confidence level a (as calculated by way of the Goodman et al. (Good
man 1965) confidence interval), and IC is the of possible output classes. An attack on such
classification is then a sample x' E [0, 1]d for which
[ox'((')) Eg [xx)'))
where i = arg max E,, E AEEKY meK
(6)
The very nature of randomised smoothing makes such a definition particularly amenable to gradient- based attacks. Randomised smoothing can be thought as a Gaussian blur of the decision space, which both removes many isolated adversarial examples, and decreases the local variance of gradients in this space. This latter property further enhances the performance of iterative gradient based attacks.
The process that we will now describe requires white-box access to model and its parameter space, including the level of added noise a. While such a white-box attack framework is limiting, previous work has demonstrated that it may be possible to successfully attack black-box models by way of surrogate models (Papernot et al.) (017). effectively converting black-box models into white-box's suitable for attack. Moreover, as will be discussed in Appendix E. the attacker does not require exact knowledge of a, with even approximate values still yielding an attack which exhibits improved performance relative to comprable attacks.
3.2 ATTACKING THROUGH UNDIFFERENTIABLE LAYERS
That the calculation and sorting of expectations involves undifferentiable arg max layers inherently limits the applicability of gradient-based attacks such problem space. However, stochastic
3

---

Under review as a conference paper at ICLR 2023
gradient estimation techniques have been shown to accurately generate approximate derivatives, even across undifferentiable layers (Fu 2006 Chen et al. 2019). Within this work we implement gradient-based attacks by replacing the arg max layer with the Gumbel Softmax (Jag et al. 2016
exp (log m.) + 9:)/T)
1/4 Ejex exp (llog(=.) g.)r)) for all e A
in terms of temperature т and iid samples ~ Gumbel(O, 1), which approximates the arg max operation in the r O limit. As will be discussed in Section 4 these modifications allow for the application of gradient-basee attacks like PGD, Carlini-Wann Waggnr, DeepFool, and AutoAttack to models defended by randomised smoothing.
3.3 ENHANCED CERTIRICATION AWARE ATTACKS
While making such modifications allows for attacks to be applied to models defended by randomised smoothing, is also possible construct new attack frameworks that incentivise the construction of small adversarial perturbations against models defended by randomised smoothing. Focusing upon small adversarial examples is crucial as such examples are likely to decrease the likelihood of the attack being detected (Gilmer et al. 2018). To achieve this, we introduce the attack
max E. [x))] [.]5(((')] + + x||
min x'E
(8)
SEAC
for some class j E K. if arg max (() i, subject to the Lagrange multiplier A. This formalism may appear counter-intuitive, as we are seeking to identify the smallest example such that ||x' x which traditionally would lead to the Lagrange multiplier being applied the first term of Equation g Constructing the objective of the minimisation process in such a fashion prioritises finding parts of the parameter space likely to contain an adversarial example, before converging upon solutions that prioritise minimising the distance between x' and x.
This formalism admits solutions constructed following the iterative process
d where
x++1 P X
"dll2
V= max jEX(
F,[[((x')] - [x([((x))] Aa|x -X]xx=xl])
for given step-size s. Similar to PGD, the projection operator P is defined such that x E [0, 1]
Step-size control by certified robustness Attacking models defended by randomised smoothing presents additional opportunities to improve attack performance. We can exploit the fact that robustness certificates allow us to generate a guarantee of class invariance for perturbations with L2 norm bounded magnitude less than r. This then allows the step-size from Xo + x to be set such that 8 > r, as we are guaranteed that no adversarial example can exist within this radius. Introducing this change allows for significant reduction of the potential search space for adversarial examples. This process also applies to any x'_- producing certifications with an L2 norm magnitude of
σ (Φ (Eo (Eo())) (1-4)))-((()) (Bi (xx()))) 2
(10)
by way of the two largest class expectations Fgg and E If Fo corresponds to the original predicted class, then setting sy > r& guarantees that steps take x outside the region of the adversarial guarantee. However, if an adversarial perturbation has been constructed such that Eg corresponds to a different class, then setting 8 < T guarantees that x will also remain an adversarial example.
While this efficiently traverses the potential search space, it is possible that large steps may move the iterative process towards an early local optimum, bypassing a pathway towards convergence to a preferred optimum. As such, our implementation incorporates a maximum step-size such that
m X rkyc).
(11)
where m > 1 if the predicted class at x/, matches the predicted class i, and m < 1 if the classes do not match, as is on lines 14 and 18 of Algorithm[l While bounding the step-size in terms of the certified radius enhances the ability to converge upon adversarial examples, enforcing the maximum step-size disincentivises large steps that may lead towards the convergence of local optima.
4

---

Under review as a conference paper at ICLR 2023
Algorithm I Certification Aware Attack Algorithm.
1: Input: data level of additive noise samples N, iterations M, true-label i, cutoff c, multi-
plicative Lagrange multiplier scaling factor A, penalty parameters I 1 and
2: x', Xaa = 0,
3: for 1 to M do
4: Eo, E1, R Model(x'; o, N) (Detailed in Algorithm
5: if arg max + i then
6:
if Eo > Ej then
7:
= x (Eo
E1) -xxx
x1)
8:
if ||x' x < m then
9:
m. x2 = ||x' - x||. x'
10:
end if
11:
else
d= V= (T
En - + - xxI) {T is promotes distinct predictions)
12:
end if
14:
m0n(9. c} (As R is about x', this step is guaranteed to retain the class prediction) T.X
16:
else if arg max y = then
17:
d vx EE E1 6)
18:
8 = min (1.5., c) {s necessary to inducing a change in the predicted class) }
19:
end if
20:
x' P(xx - P
d
(Project upon [0, 1]d)
21:
end for
22:
return m, X
Algorithmic innovations This section has demonstrated both how models defended by randomised smoothing can be attacked and how exploiting Equation 3 as an additional attack surface by signifi- cantly reducing the adversarial example search space, in order attempt identify the smallest perturbation that is still an adversarial example.
Algorithm [ contains several additional features designed to enhance the convergence upon the smallest identifiable adversarial example, which we highlight now. One of these is the parameter 8 > 0 on lines 12 and 17, which promotes identifying distinct adversarial examples, ones for which arg jx: Ey (x.)] * and max Eş [fo (xx())) (x(,)x)())l promoting a small degree of additional separation beyond the introduced bounds.
final feature designed to promote the identification of distinct adversarial examples can be seen in the introduction of 1 into line 12. In the case of non-distinct adversarial example, this parameter incentivises the iterative process to converge upon a distinct example, by changing the balance of weights between the terms relating class difference and sample distances.
Additional algorithmic nuance is found on on lines 7 and 12 of Algorithm | Initially the Lagrange multipliers introduce counterproductive bias towards minimising |x' x|I. our step-size control ensures that are efficiently moving towards nearby adversarial examples. After such an example has been found, Line 14 ensures that the predicted class will not change, with the Lagrange multiplier of lines 7 and 12 then incentivising minimising | - x|--
Code demonstrating both our process, and our tested comparisons can be found anonymised link.
EXPERIMENTS
To evaluate both the performance of our new attack technique and the difference between identified adversarial perturbations and certified guarantees, we now present comprehensive experimental validation against MNIST (LeCun al. 1998) (GNU v3.0 license), CIFAR-10 10 (Krizhevsky et al.) 2209) (MIT license), and Tiny-I Imagenet (Johnson et al. Accessed 2022-01-10) (BSD 3 Clause license), the latter of which is 200-class variant of Imagenet YYng et al. 2021 which downsamples
5

---

Under review as a conference paper at ICLR 2023
images to 3 60 x 60. Each model was trained in PyTorch (Paszke et al. 2019) using Resnet18 architecture, with experiments considering two distinct levels of a. The confidence intervals of the expectations were calculated at a significance level of = 0.005. Based upon Appendix E3 the cutoff factor e of Equation [1] was set to 0.5.
For both MNIST and CIFAR-10 the experimentation employed single NVIDIA P100 GPU core with 12 GB of GPU RAM, with expectations estimated over 1500 samples. Over the course of 50 epochs of training, each sample was perturbed with single perturbation drawn from (0, o²) and added prior to normalisation. Training then utilised a batch size of 128, with losses assessed against the Cross Entropy loss. Parameter optimisation was performed with Adam (Kingma & Ba 2014). with the learning rate set as 0.001. utilising total of 48 GB of GPU RAM to estimate expectations based upon 1000 samples. Training occurred using SGD over 80 epochs, with a starting learning rate of 0.1, decreasing by a factor of 10 after 30 and 60 epochs, and momentum set to 0.9.
training and evaluation utilised 4 P100 GPU's
To assess the relative performance between our newly constructed adversarial perturbations and the corresponding certified guarantees (as provided by [ohen et al.) 2019) Equation (3) provides a lower bound on the distance between an adversarial example and the sample point. To aide this comparison, we introduce the concept of the attack proportion. which represents the proportion of correctly predicted samples that have an identified attack below given L2 L2-norm radius. The lower bound attack radius-as as provided by the certified guarantee- gives an upper bound on the achievable attack proportion for any given radius. Our new Certification Aware Attack framework is also compared against PGD, Carlini-Wagne' and DeepFool based upon 100 attack iterations, with metrics collected after the first successful attack and at the end of the iterative process. The nature of Auto requires the attack radii to be pre-specified, which we set at 100% increase over the radius identified by Cohen et al. (2019). Further details of the attack hyperparameters can be found in Appendix C
Performance against other attacks Across the full set of tested experiments, the aggregate measures of Figure and Table [ demonstrate that our Certification Aware Attack almost uniformly identifies smaller ad adversarial perturbations than any other technique, resulting in 24% reduction in the median perturbation radii for Tiny-Imagenet at = 1.0, relative to the next best performing technique in PGD. Across the full suite of tested experiments, on average our technique yields a 13.6% reduction in the median perturbation radii. Of the remaining techniques, both DeepFool and Prllini-Wagner exhibit median radii perturbation radii that is an order of magnitude larger than both our technique and PGD, although in the case of DeepFool these examples are identified significantly faster than any other tested approach. Even setting the attack radii to be significantly larger than the median radii identified by our approach and PGD, Attokt was able to identify significantly fewer adversarial examples than our approach.
is important to note that while increasing a should improve the performance of all gradient- based attacks due to the smoothing influence of noise upon the label space. However it is clear that our attack is particularly well suited to this change, with a distinct improvement relative to PGD within Figure
Neither PGD nor DeepFool were able to converge upon smaller adversarial perturbations with additional iterations, in contrast to the design of both our approach and Carlini- Carlini-Wagner. Table [ demonstrates that our Certification Aware Attacks can reduce the magnitude of the identified adver- sarial perturbation 15%, at the cost of 2 3-fold increase in computational time. While continuing to iterate with Carlini- Carlini-Wagner yields more significant improvements even after the 100 iterative steps, the attacks are still an order of magnitude larger than our approach, and take more than twice as long.
Of the experimental set, the results observed for MNIST deserve additional consideration. due to their surprising nature. While MNIST has a limited number of classes, single-channel low-resolution images, and perceived lack of semantic complexity across the class set, it proved the most difficult example to attack, with only Carlini -agner being able to attack more than 90% of samples. That these issues are more pronounced for 0.5 intuitively suggests that this may be due to each attack using step-sizes that are too large for the smaller, single-channel input space of MNIST. Increasing o adds additional smoothing to the label space and pushes adversarial examples further out. However, both our Certification Aware Attack and DeepFool do not rely upon fixed step-sizes at all, but rather construct their step-sizes by drawing upon observations of the state. This suggests that the relatively

---

Under review as a conference paper at ICLR 2023
Table 1: Performance metrics for MNIST (M), Cifar- 10 (C), and Tiny-Imagenet (TI) for varying o. 'Success' and 'Best' the proportion samples for which each attack success, and outperformed all others. rsu and C-honen are the median attack and the size relative to the guarantee of Cohen.
Categorisation
Smallest Attack
First Attack
Data Attack
Success
Best
rso
%-Cohen
Time (s)
Ratio(rso)
Ratio(Tima)
M-0.5
Ours
75%
71%
1.95
67%
5.49
1.10
0.23
PGD
65%
6%
1.95
69%
8.95
1.00
0.34
C-W
94%
25%
8.19
612%
5.29
1.63
0.02
Auto 31%
2%
1.95
100%
174.87
1.00
1.00
D.Fool 5%
1%
9.20
2107%
0.66
1.00
1.00
M-1.0
Ours
100%
89%
2.41
66%
2.87
1.09
0.43
PGD
98%
4%
2.75
88%
8.92
1.00
0.43
C-W
94%
0%
8.83
505%
4.49
1.51
0.03
Auto 90%
6%
3.05
100%
174.08
1.00
1.00
D.Fool 47%
0%
12.80
1409%
0.65
1.00
1.00
C-0.5
Ours
96%
83%
0.85
69%
3.34
1.23
0.19
PGD
95%
3%
0.97
88%
9.19
1.00
0.14
C-W
95%
2%
6.65
1104%
4.58
2.07
0.03
Auto 85%
11%
1.27
100%
179.28
1.00
1.00
D.Fool 90%
0%
2.39
512%
0.67
1.00
1.00
C-1.0
Ours
100%
85%
1.24
79%
2.38
1.13
0.38
PGD
100%
1%
1.55
114%
9.17
1.00
0.22
C-W
95%
0%
6.76
775%
4.43
2.01
0.03
Auto 74%
12%
1.88
100%
178.91
1.00
1.00
D.Fool 98%
1%
3.05
462%
0.67
1.00
1.00
T-I-0.5
Ours
94%
77%
0.97
89%
6.62
1.18
0.23
PGD
93%
1%
1.15
113%
18.80
1.00
0.17
C-W
100%
6%
11.79
1981%
13.76
2.45
0.02
Auto
67%
15%
1.38
100%
360.88
1.00
1.00
D.Fool
79%
1%
2.39
532%
1.36
1.00
1.00
T-I-100
Ours
95%
84%
1.37
107%
4.70
1.13
0.44
PGD
94%
1%
1.80
161%
19.51
1.00
0.26
C-W
100%
5%
10.73
1373%
14.38
2.73
0.02
Auto 54%
11%
2.29
100%
372.23
1.00
1.00
D.Fool
89%
0%
3.44
577%
2.72
1.00
1.00

---

Under review as a conference paper at ICLR 2023
230
W-Diillecare to CR
150
100
-00
0.2
0.8 Largest Class Expectation
0.4
0.8
1.0
Figure 1: Percentage distance between constructed adversarial perturbations and the certified radii given by Equation 3 with Our technique in Red and PGD in Blue. Results for CIFAR-10 with o = 1.0. Additional experimental results are visible in Figure
large adversarial perturbations for MNIST may be driven by the polarised nature of these samples- containing regions of black and white with limited blending- and the constructed gradients leading to adversarial perturbations outside the numerical domain, which are then clipped to [0, 1]
Performance relative to certified guarantees An important feature of these results is the difference between the attack proportion of our technique, and the bound provided by Cohen et al. (Cohen et al. 2019). Intuitively it would be expected that the linear multiplicative proportionality of Equation (3) would increase the magnitude of the guarantee in T-2 norm space, and thus in turn introduce greater difference between our attack and the certified guarantee. However, in practice these increases are offsct by both a decrease in both the class expectations-dur to the smoothing influence of additive noise- and the difficulty of constructing an attack.
In the context of the Cohen al. bound of Equation 3 by Table [ our technique clearly produces smaller adversarial perturbations for the majority of samples, while consuming approximately the same amount of computational time as both PGD and Carlini-Wagner. When compared against PGD, Figure 1 underscores the difference in the magnitude of the adversarial perturbation when considered against Cohen al., with clear self-similar trend in which the percentage difference to Equation 3 increases the largest class expectation decreases in Figure This suggests that the delta is likely not the attacks failing to identify global optimal adversarial perturbations in this region, but rather that this region would instead potentially admit larger certifications by taking revised approach. There also appears to be a correlation between the outperformance of our approach and the semantic complexity of the prediction task, which suggests that tightening these guarantees could be increasingly relevant for complex datasets of academic and industrial interest.
Limitations It important note that this current work has deliberately focused upon L2-norm attacks as our technique is built upon certified guarantees of robustness, which are primarily built upon the potential for adversarial examples bounded L2-norm space and do not presently extend to rotational or translational modifications (Tian et al.) 2018), nor functional attacks (Laidlaw & Feizi 2019) attacks. While this inherently biases our approach towards datasets with image-structured data, the core concepts of attacking randomised smoothing, and of augmenting attack methodologies with the knowledge of regions of class invariance should be readily extensible to a broad array of data types and structures.
We also acknowledge that the chosen attacks exist at a single point of parameter space, and there are many other attacks that remain untested, which may provide different results. We emphasise here that the chosen set of attacks have distinct conceptual mechanisms, and were chosen to explore the relative performance of other gradient- gradeent-based mechanisms relative to our approach. While in cases extended versions of these attacks exist, there no guarantee that this increased complexity yields better results in the context of randomised smoothing.
Finally, this attack requires access to significant amounts of GPU memory. Attacking a ResNet18 model trained for CIFAR-10 required approximately 10 GB of GPU memory when smoothing was
8

---

Under review as a conference paper at ICLR 2023
MNIST, 0.5
b) MNIST,
CIFAR-10, 0.5
Attack Proportion
0.75
0.50
0.25
d) CIFAR-10, 1.0
T-L 0.5
T-L 10
1.00
Attack Proportion
0.75
0.50
0.25
0.00
0
2
0
2
4
Radins
Radius
Radius
Figure 2: Best achieved Attack Proportion for our new Certification Aware Attack (Blue), PGD (Red), DeepFool (Cyan), Barlini-Wagner (Green), and AutoAttack (Magenta), with the black dotted line demonstrating the theoretical best case performance, as calculated by Cohen et al.. Dashed lines represent the first identified attack, while solid lines denote the best identified attack.
performed over 1500 samples, whereas close to 37 GB was required for Tiny- Tiny-Imagenet with 1000 samples. This memory consumption is driven by our current implementation requiring all samples to be loaded into memory at once, prior to performing the gradient-based iterative step. While this process be improved through batching. chose not to follow this to ensure that results weren't influenced by the batching implementation. Such change would be necessary though to attack datasets containing larger images, more memory-intensive model architectures.
5 CONCLUSION
While it is well known that adding calibrated noise to models via randomised smoothing can improve adversarial robustness, this work demonstrates that this process and resulting certifications introduce heretofore undiscovered attack surface, yielding our Certification Aware Attacks. By leveraging the guarantees of class invariance provided by randomised smoothing for both the correct and malicious class prediction, these attacks have the potential to significantly decrease the size of identified adversarial perturbations, relative to other techniques. Relative to tested baseline attacks, attack finds smaller adversarial perturbations for almost 90% of samples, resulting in 13% reduction in the median attack perturbation. Decreasing the magnitude of these adversarial perturbation makes the attacks more difficult detect, and thus, more likely to be successfully passed through a model.
ETHICS STATEMENT
While constructing such attacks has malicious benefits, there is also inherent value in understanding the potential of models to be compromised. As discover within this work, certification mechanisms introduce heretofore undiscovered attack surface that can be exploited to further decrease attack radii. As such, exploring such attacks is important defray potential overconfidence regarding the robustness of certified models, and to provide contextual information about the values (or lack thereof) of deploying autonomous machine learning models in high stakes environments.

---

Under review as a conference paper at ICLR 2023
7 REPRODUCABILITY STATEMENT
This work describes both a general framework for attacking models defended by randomised smooth- ing, and specific attack (as described in Algorithm that can be used to attack such models. To enhance reproducability, prototype code has been attached to the OpenReview submission, and will be released publicly upon publication.
REFERENCES
Battista Biggio, Igino Corona, Davide Maiorca, Blaine Nelson, Nedim Šıniić, Pavel Laskov, Giorgio Giacinto, and Fabio Roli. Evasion Attacks Against Machine Learning at Test Time. Joins European Conference Machine Learning and Knowledge Discovery Databases, pp. 387-402. Springer, 2013.
Nicholas Carlini and David Wagner. Towards Evaluating the Robustness of Neural Networks. In 2017 IEEE Symposium on Security and Privacy (SP), pp. 39-57. IEEE, 2017.
Beidi Chen, Yingchen Xu, and Anshumali Shrivastava. Fast and Accurate Stochastic Gradient Estimation. Advances in Neural Information Processing Systems, 32, 2019.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified Adversarial Robustness via Randomized Smoothing. In International Conference on Machine Learning, pp. 1310-1320. PMLR, 2019.
Francesco Croce and Matthias Hein. Reliable Evaluation of Adversarial Robustness with Ensemble of Diverse Parameter-Free Attacks. In International Conference on Machine Learning, pp. 2206- 2216. PMLR, 2020.
Yinpeng Dong, Fangzhou Liao, Tianyu Pang, Hang Su, Jun Zhu, Xiaolin Hu, and Jianguo Li. Boosting Adversarial Attacks with Momentum. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 9185-9193, 2018.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating Noise Sensitivity in Private Data Analysis. In Theory of Cryptography Conference, pp. 265-284. Springer, 2006.
Michael C Fu. Gradient Estimation. Handbooks in operations research and management science, 13: 575-616, 2006.
Justin Gilmer, Ryan P Adams, Ian Goodfellow, David Andersen, and George E Dahl. Motivating the Rules of the Game for Adversarial Example Research. arXiv preprint arXiv: 887006623, 2018.
lan J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and Harnessing Adversarial Examples. arXiv preprint arXiv: 2014.
Leo A Goodman. On Simultaneous Confidence Intervals for Multinomial Proportions. Technometrics, 7(2):247-254, 1965.
Eric Jang, Shixiang Gu, and Ben Poole. Categorical Reparameterization with Gumbel-Softtax. arXiv preprint 1rXiv:1611.01 2016.
Justin Johnson, Fei-Fei Li, and Andrej Karpathy. Tiny ImageNet Visual Recognition Challenge, Accessed 2022-01-10. http://pp./cc22.sstttttrrddddedd
Zip
Diederik P Kingma and Jimmy Ba. Adam: A Method for Stochastic Optimization. arXiv preprint 14/2.6984 2014.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning Multiple Layers Features from Tiny Images. Technical report, University of Toronto, 2009.
Cassidy Laidlaw and Soheil Feizi. Functional Adversarial Attacks. arXiv preprint arXiv: 2019.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffnnr. Gradient-Bauee Learning Applied to Document Recognition. Proceedings of the IEEF, 86(1 (0(11):2278-322 1998.
10

---

Under review as a conference paper at ICLR 2023
Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified Robustness to Adversarial Examples with Differential Privacy. In 2019 IEEE Symposium on Security and Privacy (SP), pp. 656-672. IEEE, 2019.
Bai Li. Changyou Chen, Wenlin Wang, and Lawrence Carin. Certified Adversarial Robustness with Additive Noise. In Advances in Neural Information Processing Systems, pp. 9459-9469, 2019.
Seyed-Mohsen Moosavi-Deaae Dezooo,,,,,, Alhussein Fawzi, and Pascal Frossard. DeepFool: A Simple and Accurate Method to Fool Deep Neural Networks. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 2574-2582, 2016
Nicolas Papernot, Patrick McDaniel, Ian Goodfellow, Somesh Jha, Z Berkay Celik, and Ananthram Swami. Practical Black-Box Attacks against Machine Learning. In Proceedings of the 2017 ACM Asia Conference Computer and Communications Security, pp. 506-50666 519, 2017.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Vito Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An Imperative Style, High- Perforrerfom Deep Learning Library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché Buc, E. Fox, and R. Garnett (eds.), ), Advances in Neurul Information Processing Systems 32, pp. 8024-8035.
Curran Associates, Inc., 2019.
Hadi Salman, Jerry Li, Ilya Razenshteyn, Pengchuan Zhang, Huan Zhang, Sebastien Bubeck, and Greg Yang. Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers. In Advances in Neural Information Processing Systems, 2019.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing Properties of Neural Networks. arXiv preprint arXiv:1312.1 629299,6999... 2013.
Shixin Tian, Guolei Yang. and Ying Cai. Detecting Adversarial Examples through Image Transfor- mation. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
Kaiyu Yang, Jacqueline Yau, Li Fei-Fei, Jia Deng, and Olga Russakovsky. A Study of Face Obfuscation Imagenet. arXiv preprint arXiv: (03::2/00,,,691,, 2021.
Runtian Zhai. Chen Dan, Di He, Huan Zhang, Boqing Gong, Pradeep Ravikumar, Cho-Jui Hsieh, and Liwei Wang. MACER: Attack-fiee free and scalable robust training maximizing certified radius. In International Conference Learning Representations, 2020.

---

Under review as a conference paper at ICLR 2023
Algorithm 2 Class prediction and certification for the Certification Aware Attack Algorithm of
Algorithm [
1: Input: Perturbed data x', sampless N, level of added noise o
2: y
3: for I:N do
4: Mj = Gi (fo (x' +1(00 (Here GS is the Gumbel-Softmax)
5: end for
6: y NY
7: 20. topk(y, k 2) (topk is used as it is differentiable, 2g 21
8: Fo. FA
lowerboundly, 20), upperboundly, (Calculated by way of Goodman al.
(Goodman 1965)
9: R
(Eo) ((())))((11)
(Ei))
10: return Eg. E,, R
A APPENDIX
B ALGORITHMIC DETAILS
A outlines the steps sampling process required to generate both the class prediction and the certification radius, which is expressed in terms of the lower and upper bounds of the largest and second largest class, respectively labelled as Eo and Ej. These expectations are calculated by way of Monte-Carle approximation of y (x N)). subject to the application of concentration inequality to quantify the underlying uncertainties.
oottiness
C ATTACK CONFIGURATION
Following previous experimental works, we employed the following hyperparameters for each attack framework. For Carlini- Carlini-Wagner, one-hot encoding by 10 10-4, 4, The Carlini- Carlini-Wagner training process was conducted using a learning rate of 0.01 over 100 iterations. Similarly DeepFool also employed 100 iterations, and employed an overshoot factor of 0.02. When considering PGD of the form outlined in Equation [ the was set at 20 with iterations again occurring 100 times. Further details relating to the choice of c for PGD can 255
set that of Equation 2 0, and weighted the loss from the
be found within Appendix E.4
AutoA Atack was performed using the randomised model variant, with the attack radii set max(2 x R, () where was calculated by Equation 3 This choice of attack radii was a deliberate attempt match the average identified attack radii (relative Equation 3). is further discussed in Appendix E.5
D PERFORMANCE OF INDIVIDUAL SAMPLES
When comparing the individual performance of samples, as is seen in Figure 3 it is clear that there's consistent and marked improvement across the suite of experiments. The one exception this is when the largest class expectation is and a 0.3, which leads to an interesting and marked increase in the radii produced by our technique, relative that of PGD. This appears be a product of how we estimate the bounds on the two highest class expectations, prior to calculating the iterative this narrow region, we introduce significant growth
step. By underestimating the uncertainties in the predicted certified radii, which in turn induces significant overestimate in the radius of certification. This in turn induces oversized iterative steps, which prevent converging upon smaller potential adversarial perturbations.
That these graphs show no examples with percentage differences less than 25% also reinforces our earlier point about there still being potential for improving certified guarantees. This is especially true as the largest class expectation decreases, as the minimum observed percentage difference begins to increase significantly.
12

---

Under review as a conference paper at ICLR 2023
250
250
Wy- DT-Diferenee to CRt
% Difffeennce to Ch
150
100
100
0
0.7
0.8
0.9
1.0
0.5
0.7
Largest Class Expectaation
Largest Class Expectation
(a) MNIST, o = 0.5
(b) MNIST, a 1.0
250
250
% Differencce to CR
150
150
% Dilleraeee
100
0.
0.3
0.5
0.6
0.7
0.8
0.9
0.2
0.4
0.8
1.0
Largest Class Expectation
Largest Class Expectation
(c) CIFAR-10, 0.5
(d) CIFAR-10, 1.0
250
250
Difieeeennce to CR
% Dillenee
150
150
100
0.2
0.4
0.2
0.4 Largest Class Expectation
1.0
Largest Class Expoctation
(c) Tiny-Imaan Imagenmee o = 0.5
(f) Tiny-Imagenet, o 1.0
Figure 3: Per-sample performance of our Certification Aware Attack technique (Red) and PGD (Blue), relative to the magnitude of the La norm guarantees provided by Certified Robustness.
13

---

Under review as a conference paper at ICLR 2023
Aveegg Pertcbutton Btdine
1.480
0.
1.0
1.4
Figure 4: Average perturbation radius when is estimated by ö. Data collected for CIFAR-10 1.0.
Table 2: Evolution of metrics as a function of the number of samples used to estimate the expectations, calculated for CIFAR-10 with 0.5. All other experiments in this paper calculated using 1500 samples for MNIST and CIFAR-10 10, and 1000 samples for Tiny Imagenet. AutoAttack experiments were excised from these experiments due to the underlying computational cost.
Method
Metric
250
500
750
1000
2000
Ours
r50
0.94
0.84
0.85
0.82
0.79
Attacked
96%
97%
97%
99%
98%
Time (s)
1.2
1.6
2.6
4.5
7.1
PGD
T50
1.04
0.94
0.89
0.9
0.87
Attacked
95%
96%
96%
96%
96%
Time (s)
0.6
0.8
1.1
1.4
1.9
C-W
T50
6.41
6.45
6.46
6.41
6.34
Attacked
93%
92%
93%
94%
94%
Time (s)
1.9
2.8
4.0
5.2
7.4
DeepFool
r50
2.18
1.91
1.83
1.84
1.81
Attacked
76%
82%
81%
81%
85%
Time (s)
0.3
0.4
0.7
0.9
1.1
E SENSITIVITY ANALYSIS
E ACCURACY OF
The white-box threat model assumes that the attacker has access to the full model and its parameters, including the level of additive noise However, for the purposes of constructing the attack, is only required for constructing the maximum step-size through Equation| IT] which is employed alongside the cutoff factor and scaling factor m. That m and are scaling implies that accurate knowledge of a is in fact not strictly necessary. In fact, as shown by Figure 4 even over-estimating by 50% decreases the radius of the identified adversarial perturbation. While this strongly suggests that there is further scope for optimising m and it also makes it clear that even estimating as part of surrogate model, in order to attack under black-box threat mode.
E.2 SAMPLE SIZE
In order assess the influence of the sample size the relative performance of the techniques, Table 2 considers the performance of the best identified adversarial example. Due to the influence of the sample size the measured uncertainties, there is small but steady decline in the radii of observed adversarial examples with the sample size. Surprisingly, increasing the samples did induce slight increase in the proportion of adversarial perturbations identified, suggesting that the
14

---

Under review as a conference paper at ICLR 2023
Table Comparison of the influence of the cutoff in Our attack process for 0.5, in terms of the median first and best adversarial example, and the median time for identifying the first adversarial example.
Dataset
Cutoff c
Successful
First 150
Best 75o
First 10 (s)
MNIST
0.05
45.0%
1.646
1.617
4.44
0.25
65.0%
1.988
1.874
1.51
0.5
71.5%
2.149
1.942
1.16
0.75
75.0%
2.345
1.962
1.07
1.0
75.5%
2.426
1.972
1.07
1.5
74.5%
2.687
1.993
0.97
3.0
74.0%
3.257
2.020
0.97
CIFAR-10
0.05
93.5%
0.806
0.756
1.76
0.25
97.5%
0.904
0.801
0.74
0.5
97.0%
1.030
0.807
0.65
0.75
97.0%
1.135
0.814
0.65
1.0
99.0%
1.220
0.838
0.65
1.5
98.5%
1.486
0.829
0.65
3.0
99.0%
2.194
0.845
0.65
smoothing influence of increasing the sample count may be making the gradient trajectories slightly more amenable to identifying adversarial perturbations. curious feature of these results that while the increases in computational time sub-linear with respect the number of samples for all techniques except our Certification Aware Attacks. This suggests that additional improvements in our technique's performance could likely be achieved with additional code optimisation.
E.3 CUTOFF FACTOR C
crucial to understand the influence of the cutoff factor e from Equation [I]. due to its centrality within Algorithm I In order to do so Table consideed the sensitivity of the MNIST and CIFAR-10 experiments to changes c. Specific focus was placed upon the case where a 0.5, as the label space for the lower level of noise is less smoothed, and thus should be more sensitive to the maximum step-size. While we have excised Tiny- Tmny-ema due to computational cost concerns, for MNIST 0.5 there is effectively
and CIFAR-10 it is clear that beyond cutoff factor further, when both the converged adversarial example, and the rate of convergence. The decreased sensitivity to beyond this point is consequence of the distribution of likely certified radii- snei--speiffically that as increases it becomes increasingly less likely that a sample point would lead certification of radii larger than this value.
advantage in increasing the
E.4
PGD STEP-SIZE
Across all our experiments, step-size for PGD was uniformly set to e = 20/255, primarily this parameter matched the results of prior works attacking these datasets in the absence of randomised smoothing, and such attacks are likely to be the primary source of information for an attacker attempting modify their approach consider defended models. However, Figure does demonstrate that decreasing below this level will yield decreased perturbation radii, doing so would further increase the computational cost PGD relative our new technique, while still yielding an insignificant change in the number of samples for which PGD yields the smallest certification.
E.5 AUTOATTACK RADIUS
As was discussed in Section 2 AutoAttack's is not the step-size of the iterative process, but rather the maximum bound on the norm of adversarial perturbations. While theoretically this e should serve upper bound, in practice experiments showed that the significant majority of identified adversarial examples were produced with a radii of e. To explore the performance of changes in how multiple of the Cohen certified radius of the original sample
is specified- either directly
15

---

Under review as a conference paper at ICLR 2023
1.70
Mediu Pectcchution Rodine
145
Best
2.61
1.88
1.8
20
20
253
Figure 5: Performance of PGD for varying the step-size Results for CIFAR-10 at 1.0.
Attackod Proportion
10
20
20
0
2
3
4
1.0
1.5
2.0
2.5
3.0
3.5
4.0
Average Attack Radius
3-
2-
0
3
1.0
1.5
2.0
2.5
3.0 n)
3.5
1.0
(c
Cohen
Figure 6: Performance of AutoAttack for varying c, where is either set directly or as multiple of the Cohen certified radius. Results for CIFAR-10 at 1.0.
point-Figure demonstrates the relative performance of AutoAttack. While increasing the radius of certification does increase the proportion of samples that are able be viably attacked, we uniformly set n = 2 for all test sets to match the average size of the adversarial perturbation identified by our technique (relative the certification provided by Cohen).
TRAINING WITH MACER
Recent work has considered how the certified proportion of models can be improved by augmenting the training reward to maximising the expectation gap between classes Salman et al. (2019). A popular approach for this is MACER Zhai et al. (2020), in which the training loss is augmented to incorporate what the authors dub the e-robustness loss, which reflects proportion of training samples with robustness above a threshold level. Such a training time modification can increase the average certified radius by 10- 20%. however doing does increase the overall training cost by more than an order of magnitude.
To test the performance of our attack framework against models trained with MACER. Table and Figure Trerreate earlier results from within this work. Under such training time modifications approach produces both consistent attack reltive to Table 1 and the same levels of
16

---

Under review as a conference paper at ICLR 2023
Table Performance metrics for MNIST (M), Cifar-10 (C), and Tiny-Imagena (TI) for varying 'Success' and 'Best' are the proportion samples for which each attack was success, and outperformed all others. rsu and %-Cohen the median attack and the size relative the guarantee of Cohen.
Categorisation
Smallest Attack
First Attack
Data
Attack
Success
Best
%-Cohen
Time (s)
Ratio(rso)
Ratio(Time
C-0.25
Ours
100%
100%
0.91
1188%
17.54
1.20
0.35
PGD
100%
0%
15.17
20977%
26.25
1.00
0.02
C-W
96%
0%
10.61
13958%
4.04
1.30
0.08
D.Fool
100%
0%
2.10
3105%
9.59
1.00
1.00
C-0.5
Ours
92%
92%
1.56
1148%
19.33
1.08
0.55
PGD
100%
0%
15.58
11912%
26.32
1.00
0.02
C-W
87%
2%
11.58
7242%
3.37
1.23
0.10
D.Fool
100%
5%
4.28
3353%
11.51
1.00
1.00
C-1.0
Ours
75%
75%
2.03
1209%
19.57
1.05
0.66
PGD
100%
1%
16.14
8101%
26.24
1.00
0.02
C-W 99%
11%
11.29
5932%
3.36
1.24
0.10
D.Fool
100%
13%
7.49
3984%
9.61
1.00
1.00
C, 0.25
b) 0=
c) C. 1.0
1.9
Orlon
Cur. (P)
PCD (F)
C-W
Attack Proportion
C-W
DeepP
0.6
0.
0.2
0.9
Radius
Radius
Radius
Figure 7: Attack and Certification Performance for Resnet-110 model for Cifar-10, when trained with MACER. Similar to Figure an ideal attack will approach the Cohen radii suggested by the black dotted lines.
out-performance that were seen in the earlier results. However, we must emphasise that the percentage difference to the certified Cohen radius for all techniques has significantly increased, which is consequence of the average certified radius decreasing four-fold under the MACER training routine. This appears be consequence of the larger model architecture these tests. with these latter tests employing Resnet-110 architecture, compared to Resnet-20 in the main body of the paper. This decrease in the average certification increases the average computational time for our approach, greater number of iterative steps are required to converge upon solution, the step size is proportional to the calculated certified radius.
17


Reviews:
[{"review_id": "YcwPcOFmFB", "reviewer": "Reviewer_Ms23", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper considers empirical attacks against models protected with randomized smoothing.\nThe paper proposes some simple optimizations and shows to find smaller adversarial examples than other attacks.", "summary_of_the_review": "My recommendation is mainly due to a perceived lack of novelty and motivation for the current paper.\nThe scope is very limited, and within this limited scope there are many alternative baselines that could be considered.\n\nFor example, all the considered attacks should be combined with some form of expectation-over-transformation (EOT) since the defense is randomized. Moreover, instead of using a gumble-softmax trick, it seems a lot simpler to just run a \"multi-targeted\" attack (https://arxiv.org/abs/1910.09338) that targets each possible class in term.\n\nUltimately, even if the evaluation were extended to better compare against these attacks, it remains unclear what to make of these results. Certified defenses are certified to be robust! And many existing works already show that these robustness guarantees are close to tight (i.e., if a randomized smoothing defense has a certified accuracy of say 50% for perturbations of size 1, then we already know empirically that the best attack with that perturbation budget will bring the defense's accuracy down to roughly 50%).\nThis paper instead considers minimal-norm attacks, but it isn't clear why this distinction matters. Certified defenses aim at maximizing robust accuracy at a fixed perturbation level \\epsilon. They don't aim to make any guarantees that successful perturbations will be any larger than \\epsilon.", "strength_and_weaknesses": "- The paper is not particularly well motivated: the whole point of certified defenses is that we get a proof of robustness so optimizing attacks against these models is not necessarily super interesting (unless maybe the point is to check how tight the certification guarantees are).\n- The empirical comparison mainly considers prior attacks that were developed for deterministic defenses (with the exception of autoattack). So naturally such attacks will not perform well against randomized smoothing.\n ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "UOA3IlL7Aq", "reviewer": "Reviewer_YX18", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "The paper designs an adversarial attack method that acts on randomized smoothing based models, which in fact provide provable guarantee on adversarial robustness. Specifically, the paper approximates the non-differentiable operation of randomized smoothing with Gumbel-softmax, and a CW-like attack objective, and a heuristic on the attack step-size based on the sample-wise certified radius given by Cohen et al. (2019). Experimental results on MNIST, CIFAR-10 and Tiny-ImageNet show that the proposed method can find a smaller adversarial examples from a smoothed classifier compared to other empirical attack methods.", "summary_of_the_review": "I generally feel from the paper a lack of motivation for the proposed method. Specifically, for now I am not quite convinced on a demand for a stronger attack method against certifiably robust classifiers. In terms of evaluation, I think the paper should compare with SmoothAdv [Salman et al., 2019] to claim its technical novelty. ", "strength_and_weaknesses": "**Strength**\n\n* The paper is easy-to-follow\n* An extensive experiment is performed to confirm the effectiveness\n\n\n**Weakness**\n\n* Overall, I feel I do not understand the motivation of the paper - In what practical scenarios that one can be interested in finding smallest adversarial examples for certifiably robust models, i.e., smoothed classifiers? Providing more examples on concrete applications of this technique would be really helpful to get readers more motivated. For example, could the adversarial examples found from this method transfer to other (possibly non-smoothed) models? Also, as another example, the paper could perform an in-depth analysis from the found adversarial examples to broaden understanding of smoothed classifiers.\n* The paper should discuss and compare the proposed method with SmoothAdv [Salman et al., 2019] which also propose an adversarial attack specialized for randomized smoothing. Also, could this method be used to improve SmoothAdv, i.e., to improve adversarial training of smoothed classifiers?\n* The paper lacks on ablation study on the proposed components.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "GN_or8165gi", "reviewer": "Reviewer_5baj", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "The authors proposed a certification-aware attack on randomized smoothing defense. To compute the gradient through non-differentiable randomized smoothing defense, they replaced arg max layers with the Gumbel-Softmax layer. Additionally, using the certification certificate, the perturbation step size can be automatically adjusted during the course of the attack, which is a novel idea for adversarial attacks. In the experiments, they compared their method with PGD, Carlini&Wagner, AutoAttack, and DeepFool attacks. Overall, the method improved the attack’s efficacy against randomized smoothing defense.", "summary_of_the_review": "The authors proposed a Certification Aware adversarial attack, however, the proposed attack was only tested against randomized smoothing defense. The authors should have tested the attack against other certified defenses and empirical defenses. Due to the limited technical novelty and lack of detailed experimental comparison, my suggestion for this paper is to reject it. Nevertheless, the idea is quite interesting and promising.", "strength_and_weaknesses": "### Strengths\n\n- Proposed certification-aware adversarial attack, which improves the attack’s accuracy in comparison with existing attacks.\n- A new way to adjust the perturbation step size based on the certification certificate.\n\n### Weaknesses\n\n- The paper considered only randomized smoothing and wasn’t applied to any other adversarial training or certified defenses.\n- The comparison might be skewed in favor of the proposed method since the standard adversarial attacks are not aware of the randomized smoothing. Adding the expectation of transformation [1] and proper tuning of the attack’s parameters might change the results of the comparisons. Based on the provided experimental details, it is not clear if the authors conducted necessary hyperparameter tuning for other attacks.\n\n[1] Athalye, A., Engstrom, L., Ilyas, A., & Kwok, K. (2018). Synthesizing Robust Adversarial Examples. In J. Dy, & A. Krause, Proceedings of the 35th International Conference on Machine Learning (pp. 284–293). Stockholmsm\\\"assan, Stockholm Sweden: PMLR.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "DACWGau0YM_", "reviewer": "Reviewer_rMga", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a method to attack against models defended by randomized smoothing, and identify smaller adversarial perturbations for smoothed classifier than previous methods.\n", "summary_of_the_review": "Novel task and attack method under certified robustness via randomized smoothing, but considering lack of experiments and detailed explanation, I could not recommend this paper for acceptance at this moment.\n", "strength_and_weaknesses": "\nStrength:\n1) Propose a novel method to attack randomized smoothing/\n2) Achieve  state-of-the-art performance compared with previous attack methods.\nWeakness:\n1) Not enough experiments to support the statements: \na. Only evaluate on randomized smoothing model of Cohen19. The performance of the attack on other randomized smoothing methods (such as SmoothAdv, MACER, Carlini22:https://arxiv.org/abs/2206.10550) is unclear.\nb. The setting of the /sigma in Table 1 is not aligned with Cohen19. Experiments under smaller /sigma like 0.12 or 0.25 are not shown.\nc. Experiments are limited to specific model architecture and datasets. Model architecture ResNet18 and Dataset Tiny-ImageNet are simple compared with Cohen19’s.\n\n2) Ambiguous explanation of evaluating metrics of the experiments:\nDo not have an explicit explanation of the evaluation metrics in Table 1 like Success, Best, r_50, %-Cohen, which makes me confusing. \n\n3) Questions about AutoAttack\nAs I know, AutoAttack ensembles 4 attack methods which include APGD-CE (PGD with adaptive step size) and APGD-DLR (similar to target CW attack). Why does AutoAttack have a worse performance than PGD and CW? \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject