BREAKING  CERTIFIED  DEFENSES:  SEMANTIC  ADVERSARIAL  EXAMPLES  WITH  SPOOFED  ROBUSTNESS  CERTIFICATES
Authors: Amin Ghiasi
Ali Shafahi
Tom Goldstein
Venue:  (2020)

Abstract: Defenses against adversarial attacks can be classified into certified and non-certified. Certifiable defenses make networks robust within a certain $\ell_p$-bounded radius, so that it is impossible for the adversary to make adversarial examples in the certificate bound. We present an attack that maintains the imperceptibility property of adversarial examples while being outside of the certified radius. Furthermore, the proposed "Shadow Attack" can fool certifiably robust networks by producing an imperceptible adversarial example that gets misclassified and produces a strong ``spoofed'' certificate.

Published as a conference paper at ICLR 2020
BREAKING CERTIFIED DEFENSES: SEMANTIC ADVER- SARIAL EXAMPLES WITH SPOOFED ROBUSTNESS CER- TIFICATES
Amin Ghiasi ; Ali Shafahi'& & Tom Goldstein
University of Maryland
{amin, ashafahi, t tomg) (cs. und. edu
ABSTRACT
To deflect adversarial attacks, a range of "certffied" classifiers have been proposed. In addition to labeling an image, certified classifiers produce (when possible) a certificate guaranteeing that the input image is not an Ep-bounded adversarial ex- ample. We present a new attack that exploits not only the labelling function of a classifier, but also the certificate generator. The proposed method applies large perturbations that place images far from a class boundary while maintaining the imperceptibility property of adversarial examples. The proposed "Shadow At- tack" causes certifiably robust networks to mislabel an image and simultancously produce "spoofed" certificate of robustness.
INTRODUCTION
Conventional training of neural networks has been shown to produce classifiers that are highly sensi-
tive to adversarial perturbations (Szegedy al. 2013 Biggio al. 2013). "natural looking" images that have been manipulated to cause misclassification by a neural network (Figure TT. While a wide
range of defenses exist that harden neural networks against such attacks (Madry et al. 2017 Shafahi et al., 2019), defenses based on heuristics and tricks are often casily breakable (Athalye et al. (2018). This motivated work on certifiably secure networks classifiers that produce a label for an image, and also (when possible) rigorous guarantee that the input is not adversarially manipulated (Cohen et al. 2019 Zhang et al. 2019b).
Natural
lx 8/255
Semantic
Shadow Attack
macaw(0.6%)
mucket(1.1%)
bucket(0.6%%
bucket(0.6%)
All adversarial examples have the goal of fooling classifiers while looking "natural". Standard attacks limit the fo-norm of the perturbation, while semantic attacks have large f--morm while still producing natural looking images. Our attack produces large but visually subtle seman- tic perturbations that not only cause misclassification, but also cause a certified defense to issue "spoofed" high-confidence certificate. In this case, a certified Gaussian smoothing classifier misla- bels the image, and yet issues a certificate with radius 0.24, which is larger certified radius than its corresponding unmodified ImageNet image which is 0.13.
Figure 1:
"qqual contribution

---

Published as a conference paper at ICLR 2020
To date, all work certifiable defenses has focused on deflecting lp-bounded attacks, where p or oo (Cohen et al. 2019 Gowal et al. 2018: Wong et al. 2018). After labelling an image, these defenses then check whether there exists an image of a different label within units (in the lp metric) of the input, where e is a security parameter chosen by the user. If the classifier assigns all images within the ball the same class label, then certificate is issued, and the input image known not to be an bp adversarial example.
In this work, we demonstrate how a system that relies on certificates as measure of label security can be exploited. We present a new class of adversarial examples that target not only the classifier output label, but also the certificate. We do this by adding adversarial perturbations to images that are large in the Ep norm (larger than the e used by the certificate generator), and produce attack images that are surrounded by a large ball exclusively containing images of the same label. The resulting attacks produce "spoofed" certificate with seemingly strong security guarantee despite being adversarially manipulated. Note that the statement made by the certificate (i.e., that the input image is not an adversarial example in the chosen norm) is still technically correct, however in this case the adversary is hiding behind a certificate to avoid detection by a certifiable defense.
In summary, we consider methods that attack certified classifier in the following sense:
Imperceptibility: the adversarial example "looks like" its corresponding natural base ex- ample,
Misclassification: the certified classifier assigns incorrect label to the adversarial exam- ple, and
Strongly certified: the certified classifier provides strong/large-radius certificate for the
adversarial example.
While the existence of such an attack does not invalidate the certificates produced by certifiable systems, should serve as warning that certifiable defenses are not inherently secure, and one should take caution when relying on certificates as an indicator of label correctness.
BACKGROUND
In the white-box setting, where the attacker knows the victim's network and parameters, adversarial perturbation are often constructed using first-order gradient information (Carlini & Wagner 2017 Kurakin et al. 2006|MMosavi- MMoosvi---eeeiiiieae
et al. 2016) or using approximations of the gradient (Uesato al.] 2018:] Athalye et al.) (018). The prevailing formulation for crafting attacks uses an additive adversarial perturbation, and perceptibility is minimized using an f--norm constraint. For example, bouunded attacks limit how much each pixel can move, while lo adversarial attacks limit the number of pixels that can be modified, without limiting the size of the change to each pixel (Wiyatno)
& Xu 2018).
It is possible to craft imperceptible attacks without using Ep bounds (Brown et al., 2018). For example, Hosseini & Poovendran (2018) use shifting color channels. WWong et al. (2019) use the Wasserstein ball/distance, and Engstrom et al. (2017) use rotation and translation to craft "seman- tic" adversarial examples. In Figure | we produce semantic adversarial examples using the method Hosseini & Poovendran| (2018) which is a greedy approach that transforms the image into HSV space, and then, while keeping constant, tries to find the smallest S perturbation causing mis- classification]] Other variants use generative models to construct natural looking images causing misclassification (Song et al. 2018 Dunn et al. 2019)
In practice, many of the defenses which top adversarial defense Beader-board challenges non- certified defenses (Madry et al.) 2017] Zhang et al., [219a]] Shaaaai et al., (019).. The majority of these defenses make use of adversarial training, in which attack images crafted during training and injected into the training set. These non-certified defenses are mostly evaluated against PGD- based attacks, resulting in an upper-bound on robustness.
Certified defenses, on the other-hand, provably make networks resist f, fy-bounded perturbations of a certain radius. For instance, randomized smoothing (Cohen al. 2019) is a certifiable defense against norm bounded attacks, and CROWN-IBP (Zhang et al. 2019b is a certifiable defense
In fig. the adversarial example has =
2

---

Published as a conference paper at ICLR 2020
against Lo0 norm bounded perturbations. Both of these defenses produce class label, and also guarantee that the image could not have been crafted by making small perturbations to an image of different label. Certified defenses also benefit from adversarial training. For example, (Salman et al. (2019) recently improved the certified radii of randomized smoothing (Cohen et al. (019 by training on adversarial examples generated for the smoothed classifier.
To the best of our knowledge, prior works have focused on making adversarial examples that sat- isfy the imperceptibility and misclassification conditions, but none have investigated manipulating certificates, which is our focus here.
The reminder of this paper is organized follows. In section 2 introduce our new approach Shadow Attack for generating adversarial perturbations. This is hybrid model that allows various kinds of attacks to be compounded together, resulting perturbations 3 we present an attack on "randomized smoothing" certificates (Cohen et al. (019). Section A shows an ablation study which illustrates why the elements of the Shadow Attack are important for successfully manipulating certified models. In section [ we generate adversarial examples for
large radii. In section
"CROWN-IBP" (Zhang et al. 2019b). Finally, we discuss results and wrap up in section 6
THE SHADOW ATTACK
Because certificate spoofing requires large perturbations (larger than the & ball of the certificate), we propose simple attack that ensembles numerous modes to create large perturbations. Our attack can be seen as the generalization by modifying clean base image. Given a loss function L and an norm bound for some p 0, PGD attacks solve the following optimization problem:
the well-known PGD attack, which creates adversarial images
max L(0, + 5)
s.l. | e,
(2)
where 8 are the network parameters and 5 is the adversarial perturbation to be added to the clean input image Constraint promotes imperceptibility of the resulting perturbation the human eye by limiting the perturbation size. In the shadow attack, instead of solving the above constrained optimization problem, we solve the following problem with range of penalties:
max L(0 x X.C(6) - TV) - -.,.Dsiim(())) 8
(3)
where de, Ate, Ag are scalar penalty weights. Penalty (V))) forces the perturbation 5 to have small total variation (TV), and appear globally by constraining the change in the mean of each color channel c. This constraint is needed since total variation invariant constant/scalar additions each color channel, and it is desirable to suppress extreme changes in the color balances of images.
smooth and natural. Penalty C(5) limits the perturbation 5
Penalty Dissim(8) promotes perturbations d that assume similar values in each color channel. In the case of an RGB image of shape 3 x W x H, if Dissim(0) is small, the perturbations to red, green, and blue channels are similar, i.e., 8R,,,. amounts to making the pixels darker/lighter, without changing the color balance of the image. Later, in section 3 we suggest two ways of enforcing such similarity between RGB channels and we find both of them effective:
6G,w,h 6,,,, Vww, h) W x H. This
1-channel attack strictly enforces δR, RS da 8g.5 Vi by using just array to si- multancously represent each color channel ow H - On the forward pass, we duplicate 8 to make 3-channel image. In this case, Dissim(6) O, and the perturbation is greyscale.
3-channel attack uses a 3-channel perturbation 8 w 6axwxx along with the dissimilarity met- ric Dissim(O) Ιパ dzll + |l de | + _ 6Gllpp
All together, the three penalties minimize perceptibility of perturbations by forcing them to be (a) small, (b) smooth, and (c) without dramatic color changes (e.g. swapping blue to red). At the same time, these penalties allow perturbations that very large in f.-norm.
3

---

Published as a conference paper at ICLR 2020
2.1 CREATING UNTARGETED ATTACKS
We focus on spoofing certificates for untargeted attacks, in which the attacker does not specify the class into which the attack image moves. To achieve this, we generate an adversarial perturbation for all possible wrong classes y and choose the best one as our strong attack:
max I(002 x + 0 AcC(6) Xio TV >₂ Dissim(()) 5
(4)
where y the true label/class for the clean image z; and L is spoofing loss that promotes a strong certificate. We examine different choices for L for different certificates below.
3 ATTACKS ON RANDOMIZED SMOOTHING
The Randomized Smoothing method, first proposed by Lecuyer et al. (2018) and later improved by et (2018), is an adversarial defense against nn-morm bounded attacks. [Cohen al. (2019) prove tight robustness guarantee under the l2 norm for smoothing with Gaussian noise. Their study was the first certifiable defense for the ImageNet dataset (Deng et al., 2009). The method constructs certificates by first creating many copies of an input image contaminated with random Gaussian noise standard deviation a. Then, uses a base classifier (a neural net) to make a prediction for all of the images in the randomly augmented batch. Depending the level of the consensus of the class labels at these random images, a certified radius is calculated that can be at most 4a (in the case of perfect consensus).
Intuitively. the image is far away from the decision boundary. the base classifier should predict the same label for each noisy copy of the test image, in which case the certificate is strong. On the other hand, if the image is adjacent to the decision boundary, the base classifier's 's predictions for the Gaussian augmented copies may vary. the variation is large, the smoothed classifier abstains from making a prediction.
To spoof strong certificates (large certified radius) for an incorrect class, we must make sure that the majority of a batch of noisy images around the adversarial image are assigned the same (wrong) label. We do this by minimizing the cross entropy loss relative a chosen (incorrect) label, averaged over a large set of randomly perturbed images. To this end, we minimize equation 4 where L is chosen to the average cross-entropy over batch of Gaussian perturbed copies. This method is analogous to the technique presented by (Shafahi et al. (2018) for generating universal perturbations that are effective when added to a large number of different images.
RESULTS
Cohen al. (2019) show the performance of the Gaussian smoothed classifier on CIFAR-10 (Krizhevsky et al.) and ImageNet (Deng et af.] 2009). To attack the CIFAR-10 and ImageNet smoothed classifier, perform 300 steps of SGD with learning rate 0.1. We choose the functional regularizers C(o) and (8) be
400 randomly sampled Gaussian images, Ar. 0.3, X 1.0, and
C(8) Avg Avg(lll and TV anisotropic--V((...)))
where | is the clement-wise absolute value operator, and Avg computes the average. For the Dissim regularizer, we experiment with both the 1-Channel attack that ensures Dissim(O) 0, and the 3-Channel attack by setting Dissim(() = [[( 86)²² 177,(4 (5 - 5B)², (ōc - 5g 5 and X_ 0.3. For the validation examples which the smoothed classifier does not abstain (see Cohen et al. (2019) for more details), the less-constrained 3-channel attack is always able to find an adversarial example while the I-channel attack also performs well, achieving 98.5% success.
F In section 4 we will discuss in more detail other differences between 1-channel and 3-channel attacks. The results are summarized in Table [ For the various base-models and choices of o,, our adversarial examples are able to produce certified radii that are on average larger than the certified radii produced for natural images. For ImageNet, since attacking all 999 remaining target classes is computationally expensive, we only attacked target class IDs 100, 200, 300, 400, 500, 600, 700, 800, 900, and 1000.
Source code for all experiments can he found http://ghhhilooooommmmmlmllliiia
4

---

Published as a conference paper at ICLR 2020
Table Certified radii produced by the Randomized Smoothing method for Shadow Attack images and also natural images (larger radii means stronger/more confident certificate).
Unmodified/Natuual Images
Shadow
Attack
Dataset
(12)
Mean
STD
Mean
STD
0.12
0.14
0.056
0.22
0.005
0.25
0.30
0.111
0.35
0.062
CIFAR-10
0.50
0.47
0.234
0.65
0.14
1.00
0.78
0.556
0.85
0.442
0.25
0.30
0.109
0.31
0.109
ImageNet
0.50
0.61
0.217
0.38
0.191
1.00
1.04
0.519
0.64
0.322
(a) Natural image (z)
(b) Adversarial perturbation (6) (c) Adversarial example (ar + 5)
An adversarial example built using our Shadow Attack for the smoothed ImageNet classi- fier for which the certifiable classifier produces a large certified radii. The adversarial perturbation smooth and natural looking even-though it is large when measured using ly-metries. Also see Figure 16 in the appendix.
Figure 2:
Figure 2 depicts a sample adversarial example built for the smoothed ImageNet classifier that pro- duces strong certificate. The adversarial perturbation causes the batch of Gaussian augmented black swan images to get misclassified as hooks. For more, see appendix [6]
4 ABLATION STUDY OF THE ATTACK PARAMETERS
In this section we perform an ablation study on the parameters of the Shadow Attack evaluate (i) the number of SGD steps needed, (ii) the importance of X (or alternatively using 1-channel attacks), and (iéi) the effect of Ato.
The default parameters for all of the experiments are as follows unless explicitly mentioned: We use 30 SGD steps with learning rate 0.1 for the optimization. All experiments except part (ii) use 1-channel attacks for the sake of simplicity and efficiency (since it has less parameters). We assume Ae= 0.3, X. 20, and use batch-size 50. We present results using the first example from each class of the CIFAR-I0 validation set.
Figure shows how the adversarial example evolves during the first few steps optimization (See appendix 13 for more examples). Also, figures 4 6nd show the evolution of L(8), TV (ō), and C()), respectively (Note that we use I-channel attacks, so Dāssim(8) is always 0). We find that taking just 10 SGD steps is enough for convergence CIFAR-10, but for our main results (i.e. attacking Randomized Smoothing in section attacking CROWN-IB in section we take 300 steps to be safe.

---

Published as a conference paper at ICLR 2020
3
4
8
9
10
original
Figure 3: The first 10 steps of optimization (beginning with a randomly perturbed image copy).
20.0
Natural
1 Channel
Figure 9: Histogram of random- ized smoothed certificate radii for 100 randomly sampled CIFAR-10 validation images vs those calcu- lated for their adversarial examples crafted using our 1-channel and 3- channel adversarial Shadow Attack attacks. The "robust" victim clas- sifier based off Resnet-110, and smoothed with 0.50. 1-channel attacks are almost as good as the less-restricted 3-channel attacks.
17.5
3-Channel
15.0
12.5
5.0
0.2
0.6
131
0175
200
0193
0125
0/23
Figure 4: Average (o) in the first 10 steps.
Figure 5: Average (8) in the first steps.
Figure 6: Average (()) in the first 10 steps.
Disste
03
330
08
0.50
035
Figure 7: The effect of X the resulting Dissim(0)
Figure 8: The effect of X the resulting (ō)
To explore the importance of Xa, 3-channel attacks and vary X to produce different images in figure
"See figure 14 the appendix for more examples.

---

Published as a conference paper at ICLR 2020
natural
1-channel
3-channel
Figure 10: The visual effect of Shadow Attack on randomly selected CIFAR-I0 examples using 1-Channel and 3-Channel attacks.
0.0
0.5
1.0
1.5
2.0
2.5
3.0
3.5
4.0
4.5
5.0
original
Figure 11: The visual effect of X on perceptibility of the perturbations. The first row shows the value of X
Also, figure 7 shows the mean Dissim(a) for different values of 7. S A, S 5.0). We also plot the histogram the certificate radii in figure 9 Figure TT compares 1-Channel vs 3-Channel attacks for some of randomly selected CIFAR- 10 images. Finally, explore the effect of A See table 15 for more images, and figure for the
imperceptibility of the perturbations in Figure I2 impact of parameters on (8).
ATTACKS ON CROWN-IBP
Interval Bound Propagation (IBP) methods have been recently studied defense against 6-0- bounded attacks. Many recent studies such as Gowal et al. (2018); Xiao et al. (2018); Wong et al. (0188; Mirman al. 2018) have investigated IBP methods to train provably robust networks. To the best of our knowledge, the CROWN-IBP method by Zhang et al. (2019)) achieves state-of- the-art performance for MNIST (LeCun Cortes] 2010), Fashion-MNIST (Xiao al. (017)) and CIFAR-10 datasets among certifiable foc defenses. In this section we focus attacking Zhang et al. 2019h) using CIFAR-10.
IBP methods (over)estimate how much small -oundee noise in the input can impact the clas- sification layer. This is done by propagating errors from layer to layer, computing bounds on the maximum possible perturbation to each activation. During testing, the user chooses an lxo per- turbation bound e, and error propagation used to bound the magnitude of the largest achievable perturbation in network output. If the output perturbation is not large enough to flip the image la- bel, then a certificate is produced. the output perturbation is large enough to flip the image label,
0.0
0.03
0.06
0.09
0.12
0.15
0.18
0.21
0.24
0.27
0.30 original
Figure 12: The visual effect of Aev on the on imperceptibility of the perturbations. The first row shows the value of Ate
7

---

Published as a conference paper at ICLR 2020
Table "Robust error" for natural images, and "attack error" for Shadow Attack images using the CIFAR-10 10 dataset, and CROWN-IBP models. Smaller is better.
Robustness Errors
e(loo)
Model Family
Method
Min
Mean
Max
CROWN-IPB
52.46
57.55
60.67
9 small models
Shadow Attack
45,90
53.89
65.74
2/255
CROWN-IBP
52.52
53.9
56.05
8 large models
Shadow Attack
46.21
49.77
51.79
CROWN-IBP
71.28
72.15
73.66
9 small models
Shadow Attack
63.43
66.94
71.02
8/255
CROWN-IBP
70.79
71.17
72.29
8 large models
Shadow Attack
64.04
67.32
71.16
then certificate is not produced. During network training. IBP methods include term in the loss function that promotes tight error bounds that result in certificates. Our attack directly uses the loss function term used during IBP network training in addition to the Shadow Attack penalties; we search for an image that is visually similar to the base image, while producing a bound on the output perturbation that is too small to flip the image label. Note that there is a subtle difference between crafting conventional adversarial examples which ultimately targets misclassification and our adversarial examples which aim to produce adversarial examples which cause misclassification and produce strong certificates. In the former case, we only need to attack the cross-entropy loss. Shadow Attack to craft adversarial examples based on the cross-entropy loss, the robust- ness eπrors are average roughly 50% larger than those reported in table 2 (i.e., simple ad adversarial examples produce weaker certificates.)
We attack 4 classes of networks released by Zhang et al. (2019b) for CIFAR-10. There are two classes of IBP architectures, one of them consists of small models and the other consists of larger models. For each class of architecture, there are two sets of pre-trained models: one for = 2/255 and one for e = 8/255. We use Ae. 0.000009, A = 0.02, C(d) = ||61| and set the learning rate to 200 and for the rest of the regularizers and hyper-paramters we use the same hyper- parameters and regularizers as in 3 For the sake of efficiency, we only do 1-channel attacks. We attack the 4 classes of models and for each class, report the min, mean, and max of the robustness errors and compare them with those of the CROWN-IBP paper.
To quantify the success of our attack, define two metrics of error. For natural images, we report the rate of "robust errors," which are images that are either (i) incorrectly labeled, or (ii) correctly labelled but without certificate. In contrast, for attack images, report the rate of "attack errors." which are either (i) correctly classified or (ii) incorrectly classified but without a certificate. Table shows the robust error on natural images, and the attack CROWN-IBP models. With e = 2/255, our attack finds adversarial examples that certify roughly 15% of the time (i.e., attack error <85%). With e = 8/255, our attack finds adversarial examples that are incorrectly classified, and yet certify even more often than natural images.
Shadow Attack images for the
CONCLUSION
We demonstrate that it is possible produce adversarial examples with "spoofed" certified ro- bustness by using large-norm perturbations. Our adversarial examples are built using our Shadow Attack that produces smooth and natural looking perturbations that are often less perceptible than those of the commonly used bo-bounded perturbations, while being large enough in norm to escape the certification regions of state of the art principled defenses. This work suggests that the certifi- cates produced by certifiably robust classifiers, while mathematically rigorous, are not always good indicators of robustness or accuracy.
Goldstein and his students were supported by the DARPA QED for RML program, the DARPA GARD program, and the National Science Foundation.
Acknowledgements:
8

---

Published as a conference paper at ICLR 2020
REFERENCES
Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give a false sense of security: Cireumventing defenses adversarial examples. arXiv preprint 2018.
00420,
Battista Biggio, Igino Corona, Davide Maiorca, Blaine Nelson, Nedim Smdiić Pavel Laskov, Gior- gio Giacinto, and Fabio Roli. Evasion attacks against machine learning test time. In Joint European conference on machine learning and knowledge discovery in databases, pp. 387-402. Springer, 2013.
Tom B Brown, Nicholas Carlini, Chiyuan Zhang, Catherine Olsson, Paul Christiano, and lan Good- 2018.
fellow. Unrestricted adversarial examples. arXiv preprint
Nicholas Carlini and David Wagner. Adversarial examples are not easily detected: Bypassing ten detection methods. In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, pp. 3-14. ACM, 2017.
Jeremy M Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. arXiv preprint Xiv: 1902.02918, 2019.
Deng, W. Dong, Socher, L.-J. Li. Li, and L. Fei-Fei. ImageNet: A Large-Scale Hicrarchical Image Database. In CVPRO9, 2009.
Isaac Dunn, Tom Melham, and Daniel Kroening. Generating realistic unrestricted adversarial inputs using dujl-objective gan training. arXiv preprint arXiv: 024663,,... 2019.
Logan Engstrom, Brandon Tran, Dimitris Tsipras, Ludwig Schmidt, and Aleksander Madry. A rotation and a translation suffice: Fooling cnns with simple transformations. arXiv preprint arXiv:1712.02773 2017.
Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Ue- sato, Timothy Mann, and Pushmeet Kohli. On the effectiveness of interval bound propagation for training verifiably robust models. arXiv preprint arXiv: 1010. 2018.
Hossein Hosseini and Radha Poovendran. Semantic adversarial examples. Proceedings of the IEEE Conference Computer Vision and Pattern Recognition Workshops, pp. 1614-1619, 2018.
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cifar-10 (canadian institute for advanced re- search). URL httl::ttt///et /wwp:///wwwwww cs twronto.ooo....o... wtw.ontt.edd//kkiiiiiiiiie htmll
Alexey Kurakin, Ian Goodfellow, and Samy Bengio. Adversarial examples in the physical world. arXiv preprint arXiv:1607.02533 2016.
Cassidy Laidlaw and Soheil Feizi. Functional adversarial attacks. arXiv preprint arXiv: 190600001, 2019.
Yann LeCun and Corinna Cortes. MNIST handwritten digit database. 2010. URL htttht//p/ya: lecun. cow/exdb/mmmcceccc st/
Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified
robustness to adversarial examples with differential privacy. arXiv preprint 2018.
Bai Li, Changyou Chen, Wenlin Wang, and Lawrence Carin. Second-order adversarial attack and certifiable robustness. CoRR, Abs/1809.03113, 2018. URL httt:://arxv..org//.
1809. 03113
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv:1706.066 06083, 2017.
Matthew Mirman, Timon Gehr, and Martin Vechev. Differentiable abstract interpretation for prov- ably robust neural networks. In International Conference on Machine Learning, pp. 3575-3583, 2018.

---

Published as a conference paper at ICLR 2020
Seyed-Mohsen Moosavi-Dezfooll Alhussein Fawzi, and Pascal Frossard. Deepfool: simple and accurate method to fool deep neural networks. In Proceedings of the IEEE conference on com- puter vision and pattern recognition, pp. 2574-25555 2582, 2016.
Hadi Salman, Greg Yang, Jerry Li, Pengchuan Zhang, Huan Zhang, Ilya Razenshteyn, and Sebastien Bubeck. Provably robust deep learning via adversarially trained smoothed classifiers. arXiv preprint arXiv:I906. 04584, 2019.
Ali Shafahi, Mahyar Najibi, Zheng Xu, John Dickerson, Larry S Davis, and Tom Goldstein. Uni- versal adversarial training. arXiv preprint arXiv: 2018.
Ali Shafahi, Mahyar Najibi, Amin Ghiasi, Zheng Xu, John Dickerson, Christoph Studer, Larry Davis, Gavin Taylor, and Tom Goldstein. Adversarial training for free! arXiv preprint arXiv: 1904://944/8333 2019.
Yang Song, Rui Shu, Nate Kushman, and Stefano Ermon. Constructing unrestricted adversarial examples with generative models. In Advances in Neural Information Processing Systems, pp. 8312-8323, 2018.
Christian Szegedy, Wojeiech Zaremha, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv:1312.6199 2013.
Jonathan Uesato, Brendan O' o'Donoghue, Aaron van den Oord, and Pushmeet Kohli. Adversarial risk
and the dangers of evaluating against weak attacks. arXiv preprint 1002:/0000006660 2018.
Rey Wiyatno and Anqi Xu. Maximal jacobian-based saliency map attack. arXiv preprint
arXiv:1808.079: 07945, 2018.
Eric Wong, Frank Schmidt, Jan Hendrik Metzen, and Zico Kolter. Scaling provable adversarial defenses. In Advances in Neural Information Processing Systems, pp. 8400-8409, 2018.
Eric Wong, Frank R Schmidt, and J Zico Kolter. Wasserstein adversarial examples via projected sinkhorn iterations. arXiv preprint 1eXivv:902.079900 2019.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnise a novel image dataset for benchmark- ing machine learning algorithms. arXiv preprint 1oXiv:770.007744 2017.
Kai Y Xiao, Vincent Tjeng, Nur Muhammad Shafiullah, and Aleksander Madry. Training for faster adversarial robustness verification via inducing relu stability. arXiv preprint 2018.
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent Ghaoui, and Michael I Jordan. Theoretically principled trade-off between robustness and accuracy. arXiv preprint arXiv: 0etp//9110.575 2019a.
Huan Zhang, Hongge Chen, Chaowei Xiao, Bo Li, Duane Boning, and Cho-Jui Hsieh. Towards sta- ble and efficient training of verifiably robust neural networks. arXiv preprint arXiv: 190660636666. 2019b.
10

---

Published as a conference paper at ICLR 2020
A APPENDIX
In this section, we include the complete results of our ablation study. As we mentioned in section we use is subset of CIFAR-I0 dataset, including one example per each class. For the sake of simplicity, we call the dataset Tiny-CIFAR-10 Here, we show the complete results for the ablation experiments on all of Tiny-CIFAR 10 examples. Figure 13 shows that taking few optimization steps is enough for the resulting images to look natural-looking. Figure [14 and [3] respectively show the effect of Xg and \Tv on the imperceptability of the perturbations.

---

Published as a conference paper at ICLR 2020
3
4
5
8
9
10
original
Figure 13: The first 10 steps of the optimization vs the original image for Tiny-CIFAR 10. See section for the details of the experiments.
12

---

Published as a conference paper at ICLR 2020
0.0
0.5
1.0
1.5
2.0
2.5
3.0
3.5
4.0
4.5
5.0
original
Figure 14: The visual effect of X on Dissim(o) on Tiny-CIFAR-II 10. See section for the details of the experiments.
13

---

Published as a conference paper at ICLR 2020
0.0
0.03
0.06
0.09
0.12
0.15
0.18
0.21
0.24
0.27
0,30
original
Figure 15: The visual effect of deo on the perturbation Tiny-CIFAR-10, See section 4 for the details of the experiments.
14

---

Published as a conference paper at ICLR 2020
Table 3: Certified radii statisties produced by the Adversarially Trained Randomized Smoothing method for our adversarial examples crafted using Shadow Attack and the natural examples (larger radii are better).
Adversarially Trained Randomized Smoothed
Shadow Attack Mean
Dataset
(12)
Mean
STD
STD
CIFAR-10 0.5
0.60
0.34
0.65
0.16
IMAGENET RESULTS
Many of the recent studies have explored the semantic attacks. Semantic attacks are powerful for attacking defenses (Engstrom et al. 2017] Hosseini Poovendran 2018 Laidlaw Feizi] 2019).
Many of semantic attacks are applicable to Imagenet, however, none of them consider increasing the radii the certificates generated by the certifiable defenses.
Some other works focus using generative models to generate adversarial examples (Song et al., 2018). but unfortunately none of the GAN's are expressive enough to capture the manifold of the ImageNet.
Figure 16 illustrates some of our successful examples generated by Shadow Attack to attack Ran- domized Smoothed classifiers for ImageNet.
B CERTIFICATE SPOOFING ATTACKS ON ADVERSARIALLY TRAINED SMOOTH CLASSIFIERS
Recently, Salman et al. 2019) significantly improved the robustness of Gaussian smoothed classi- fiers by generating adversarial examples for the smoothed classifier and training them. In this section, we use our Shadow Attack to generate adversarial examples using the loss in eq. [ for the SmoothAdv classifier f Due to computation limitations, we attack sample of 40% of the same validation images used for evaluating the randomized smooth classifier in section 3 The results are summarized in table Comparing the results of table to table we can see that the SmoothAdv classifier, does produce stronger certified radii for natural examples (many of the examples in fact have the maximum radii) compared to the original randomized smoothing classifier. This can be associate to the excessive invariance introduced as result of adversarial training. However, table 3 empirically verifies that its certificates are still subject to attacks and the certificate should not be used measure for robustness.
WWe use the official models released at http://tthhcccoo/aaiiimmmmmmtinn for attacking the SmoothAd classifier.
15

---

Published as a conference paper at ICLR 2020
OMolcolm Bu
Figure 16: Natural looking Imperceptible ImageNet adversarial images which produce large certi- fied radii for the ImageNet Gaussian smoothed classifier.
16


Reviews:
[{"review_id": "ryg2OYFAFS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes a new way to generate adversarial images that are perturbed based on natural images called Shadow Attach. The generated adversarial images are imperceptible and have a large norm to escape the certification regions. The proposed method incorporates the quantities of total variation of the perturbation, change in the mean of each color channel, and dissimilarity between channels, into the loss function, to make sure the generate adversarial images are smooth and natural. Quantitative studies on CIFAR-10 and ImageNet shows that the new attack method can generate adversarial images that have larger certified radii than natural images. To further improve the paper, it would be great if the authors can address the following questions:\n\n- In Table 1, for ImageNet, Shadow Attach does not always generate adversarial examples that have on average larger certified radii than the natural parallel, at least for sigma=0.5 and 1.0. Could the authors explain the reason?\n\n- In Table 2, it is not clear to me what is the point for comparing errors of the natural images (which measures the misclassification rate of a natural image) and that of the adversarial images (which measures successful attacks rate), and why this comparison helps to support the claim that the attack results in a stronger certificates. In my opinion, to support the above claim, shouldn’t the authors provide a similar table as Table 1, directly comparing the certified radii of the natural images and adversarial images?\n\n- From Figure 9, we see the certificate radii of the natural have at least two peaks. Though on average the certificate radii of the adversarial attacks is higher than that of the natural images, it is smaller than the right peak. Could the authors elaborate more of the results?\n\n- Sim(delta) should be Dissim(delta) which measures the dissimilarity between channels. A smaller dissimilarity suggests a greater similarity between channels. \n\n- Lambda sim and lambda s are used interchangeably. Please make it consistent. \n\n- The caption of Table 1 is a little vague. Please clearly state the meaning of the numbers in the table.\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "rJeb2tXkqB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper presents a new attack, called the shadow attack, that can maintain the imperceptibility of adversarial samples when out of the certified radius. This work not only aims to target the classifier label but also the certificate by adding large perturbations to the image. The attacks produce a 'spoofed' certificate, so though these certified systems are meant to be secure, can be attacked. Theirs seem to be the first work focusing on manipulating certificates to attack strongly certified networks. The paper presents shadow attack, that is a generalization of the PGD attack. It involves creation of adversarial examples, and addition of few constraints that forces these perturbations to be small, smooth and not many color variations. For certificate spoofing the authors explore different spoofing losses for l-2(attacks on randomized smoothing) and l-inf(attacks on crown-ibp) norm bounded attacks. \n\nStrengths: The paper is well written and well motivated. The work is novel since most of the current work focus on the imperceptibility and misclassification aspects of the classifier, but this work addresses attacking the strongly certified networks. \n\nWeakness: It would be good to see some comparison to the state of the art ", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "SJllHP3yjB", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper presents a new attack: Shadow Attack, which can generate imperceptible adversarial samples. This method is based on adding regularization on total variation, color change in each channel and similar perturbation in each channel. This method is easy to follow and a lot of examples of different experiments are shown.\nHowever, I have several questions about motivation and method.\n\nFirst, the proposed attack method can yield adversarial perturbations to images that are large in the \\ell_p norm. Therefore, the authors claim that the method can attack certified systems. However, attack in Wasserstein distance and some other methods can also do so. They can generate adversarial examples whose \\ell_p norm is large.\nI think the author should have some discussions about these related methods. \n\nSecond, I notice that compared to the result in Table 1, PGD attack can yield better results [1]. I hope to see some discussions about this. Also, Table 1 is really confused. I would not understand the meaning if I am not familiar with the experiment settings.\n\n[1] Salman, Hadi, et al. \"Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers.\" Neuips (2019).", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work presents a "shadow attack" that fools certifiably robust networks by producing imperceptible adversarial examples by search outside of the certified radius. The reviewers are generally positive on the novelty and contribution of the work. 
Decision: Accept (Poster)