Certified Defenses for Adversarial Patches
Authors: Ping-yeh Chiang*
Renkun Ni*
Ahmed Abdelkader
Chen Zhu
Christoph Studor
Tom Goldstein
Venue:  (2020)
Keywords: certified defenses
patch attack
adversarial robustness
sparse defense

Abstract: Adversarial patch attacks are among one of the most practical threat models against real-world computer vision systems. This paper studies certified and empirical defenses against patch attacks. We begin with a set of experiments showing that most existing defenses, which work by pre-processing input images to mitigate adversarial patches, are easily broken by simple white-box adversaries. Motivated by this finding, we propose the first certified defense against patch attacks, and propose faster methods for its training. Furthermore, we experiment with different patch shapes for testing, obtaining surprisingly good robustness transfer across shapes, and present preliminary results on certified defense against sparse attacks. Our complete implementation can be found on: https://github.com/Ping-C/certifiedpatchdefense.

Published as a conference paper at ICLR 2020
CERTIFIED DEFENSES FOR ADVERSARIAL PATCHES"
Ping-yeh ChiangJ Renkun Ni, Ahmed Abdelkader, Chen Zhu University of Maryland, College Park {pchiang, rn9zm, akader, chenzhuj@cs, umd. edu
Christoph Studer Coreell University st studer@corne11 edu.
Tom Goldstein
University of Maryland, College Park tomgâcs umd. edu
ABSTRACT
Adversarial patch attacks are among one of the most practical threat models against real-world computer vision systems. This paper studies certified and empirical defenses against patch attacks. We begin with set of experiments showing that most existing defenses, which work by pre-processing input images mitigate adversarial patches, casily broken by simple white-box adver- saries. Motivated by this finding, we propose the first certified defense against patch attacks, and propose faster methods for its training. Furthermore, ex- periment with different patch shapes for testing, obtaining surprisingly good ro- bustness transfer across shapes, and present preliminary results on certified de- fense against sparse attacks. Our complete implementation can be found on: httt:://ttttoo.oco////c/e//eettt
INTRODUCTION
Despite the great success of neural networks for vision problems, they are easily fooled by adversarial attacks in which the input machine learning model is modified with the goal of manipulating its output. Research in this area is largely focused on norm- hum--buuned attack (Madry et al., 2017] Tramer Boneh 2019 Shafahi et al. 2019), where the adversary is allowed perturb all pixels in image provided that the fn-norm of the perturbation is within prescribed bounds. Other adversarial models were also proposed, such as functional (Laidlaw & Feizi| 2019). ootation/translation (Engstrom et al.) 2017]. and Wasserstein (Wong et al. 2019), all of which allow modification to all pixels.
Whole-image perturbations are unrealistic for modeling "physical-world" attacks, in which real- world object is modified to evade detection. A physical adversary usually modifies an object using stickers or paint. Because this object may only occupy a small portion of an image, the adversary can only manipulate a limited number of pixels. As such, the more practical patch attack model was proposed (Brown al. 2017p. In a patch attack, the adversary may only change the pixels in a confined region, but is otherwise free to choose the values yielding the strongest attack. The threat to real-world computer vision systems is rell-demonstrated in recent literature where carefully crafted patches can fool classifier with high reliability (Brown et al., 2017; Karmon et al. 2018), make objects invisible to an object detector (Wu et al. Lee & Kolter 2019). or fool a face recognition system (Sharif et al. 2017). In light of such effective physical-wordd patch attacks, very few defenses are known to date.
In this paper, study principled defenses against patch attacks. We begin by looking at existing defenses in the literature that claim to be effective against patch attacks, including Local Gradient Smoothing (LGS) (Naseer et al. 2019) and Digital Watermarking (DW) (Hayes) 2018). Similar to what has been observed for whole-image attacks by (Athalye et al. 2018). we show that these patch defenses are easily broken by stronger adversaries. Concretely, we demonstrate successful white-box attacks, where the adversary designs an attack against a known model, including any pre- proccessesingg
"This work was supported hy the DARPA GARD, DARPA QED4RMI. programs, and National Science Foundation DMS division. I cqual contribution

---

Published as a conference paper at ICLR 2020
steps. To cope with such potentially stronger adversaries, train robust model that produces lower-bound on adversarial accuracy. In particular, we propose the first certifiable defense against patch attacks by extending interval bound propagation (IBP) defenses (Gowal et al. 2018 Mirman et al. 2018). We also propose modifications to IBP training to make it faster in the patch setting. Furthermore, study the generalization of certified patch defenses to patches of different shapes, and observe that robustness transfers well across different patch types. We also present preliminary results on certified defense against the stronger sparse attack model, where fixed number of possibly non-adjacent pixels can be arbitrarily modified (Modas et al. 2019).
2 PROBLEM SETUP
We consider white-box adversary that is allowed to choose the location of the patch (chosen from a set IL of possible locations) and can modify pixels within the particular patch (chosen from the set IP) similar to (Karmon et al., (018). An attack is successful if the adversary changes the classification of the network to a wrong label. In this paper, we are primarily interested in the patch attack robust accuracy (adversarial accuracy for short) as defined by
E min ([(,(((, yyl
(1)
I~ MEP,
where the operator A places the adversarial patch on a given image x at location I, is a neural network with parameter 0, X is distribution of images, and X is characteristic function that takes value 1 its argument is true, and 0 otherwise.
In this model, the strength of the adversary can vary depending on the set of possible patches allowed, and the type of perturbation allowed within the patch. In what follows, we assume the standard setup in which the adversary is allowed any perturbation that maintains pixel intensities in the range [o, 1]. Unless otherwise noted, we also assume the patch is restricted to a square of prescribed size. We consider two different options for the set IL of possible patch locations. First, consider a weak adversary that can only place patches at the corner of an image. We find that even this weak model is enough to break existing patch defenses. Then, we consider a stronger adversary with no restrictions on patch location, and use this model to evaluate our proposed defenses. Note that an adversary, when restricted to modify only a square patch location in the image, has the freedom to modify any non-square subset of these pixels. In other words, a certified defense against square patch attacks also provably subverts any non-square patch attack that fits inside small enough square.
In general, calculating the adversarial accuracy (T) is intractable due to non-convexity. Common approaches try to approximate it by solving the inner minimization using a gradient-based method. However, in Section 3, we show that depending on how the minimization is solved, the upper bound could be very loose: a model may appear to be very robust, but fail when faced with a stronger attack. To side-step the arms race between attacks and defenses, in Section 4, we extend the work of (Gowal et al. 2018) and (Mirman et al., 2018) to train a network that produces a lower bound on adversarial accuracy. We will reter to approximations of the upper bound as empirical adversarial accuracy and the lower bound as certified accuracy.
3 VULNERABILITY OF EXISTING DEFENSES
We start by examining existing defense strategies that claim to be effective against patch attacks. Similar to what has been observed for whole-image attacks by AAhalyye et al. (2018), we show that these patch defenses can easily be broken by white-box attacks, where the adversary optimizes against a given model including any pre-proe procesccss steps.
3.1 EXISTING DEFENSES
Under our threat model, two defenses have been proposed that each input transformations to detect and remove adversarial patches.
The first defense is based the observation that the gradient of the loss with respect to the input image often exhibits large values near the perturbed pixels. In (Hayes) 2018). the proposed digital watermarking (DW) approach exploits this behavior to detect unusually dense regions of large
2

---

Published as a conference paper at ICLR 2020
Table 1: Empirical adversarial aceuracy of ImageNet classifiers defended with Local Gradient Smoothing and Digital Watermarking. We consider two types of adversaries, one that takes the defense into account during backpropagation and one that does
Patch Size
Attack
Defense
x
52 x 52
x
IFGSM
LGS
78%
75%
71%
IFGSM + LGS
LGS
14%
3% 5%
IFGSM
DW
56%
49%
45%
IFGSM + DW
DW
13%
8%
5%
gradient entries using saliency maps, before masking them out in the image. Despite a 12% drop in accuracy on clean (non-adversarial) images, this defense method supposedly achieves an empirical adversarial accuracy of 63% for non-targ non-targeted patch attacks of size 42 42 (2% of the image pixels). using 400 randomly picked images from ImageNet (Deng al. 2009) on VGG19 (Simonyan &
Zisserman 2014).
The second defense, Local Gradient Smoothing (LGS) by Naseer et al. (2019) is based on the empirical observation that pixel values tend to change sharply within these adversarial patches. In other words, the image gradients tend to be large within these adversarial patches. Note that the image gradient here differs from the gradient in Hayes] (2018), the former is with respect the changes of adjacent pixel values and the later with respect to the classification loss. Naseer et al. (2019) propose suppressing this adversarial noise by multiplying each pixel with minus its image gradient as in (2. To make their methods more effective, Naseer et al. (2019) also pre- pre-process the image gradient with normalization and thresholding step.
f = x C (1 Ag(x)).
The À here is smoothing hyper-parameter. Naseer al. (2019) claim the best adversarial accuracy on ImageNet with respect to patch attacks among all of the defenses we studied. They also claim that their defense is resilient Backward Pass Differential Approximation (BPDA) from Athalye et al.) (2018), one of the most effective methods to attack models that include non-differentiable operator as pre-processing step.
3.2 BREAKING EXISTING DEFENSES
Using a similar setup in (Hayes) 2018 Naseer et al., 2019), we are able mostly replicate the reported empirical adversarial accuracy for Iterative Fast Gradient Sign Method (IFGSM), a common gradient based attack, but we show that when the pee-pocesssing step is taken into account, the empirical adversarial accuracy ImageNet quickly drops from 70%(~ 50%) for LGS(DW) to levels around 10% as shown Table 1
Specifically, we break DW (Hayes) 2018) by applying BPDA, in which the mon-differentiable operator is approximated with an identity mapping during the backward pass. We break LGS (Naseer al. 2019) by directly incorporating the smoothing step during backpropagation. Even though the windowing and thresholding steps are non-differentiable, the smoothing operator provides enough gradient information for the attack to be effective.
To make sure that our evaluation is fair, we used the exact same models as Hayes (2018) (VGG19) and Szegedy et al. (2016) (Inception V3). We also consider weaker set of attackers that only attack the corners, the same as their setting. Further, we ensure that we were able to replicate their reported result under similar setting.
CERTIFIED DEFENSES
Given the case with which these supposedly strong defenses are broken, it is natural to seek methods that rigorously guarantee robustness of given model to patch attacks. With such certifiable guarantees in hand, we need not worry about an adversary with a stronger optimizer, or a more clever algorithm for choosing patch locations.
3

---

Published as a conference paper at ICLR 2020
4.1 BACKGROUND ON CERTIFIED DEFENSES
Certified defenses have been intensely studied with respect to norm-bounded attacks (Cohen et al. 2019; Wong & Kolter, 2017 Gowal et al. 2018 Mirman al. 2018 Zhang al., 2019b). In all of these methods, in addition to the prediction model, there is also a verifier. Given a model and an imput, the verifier outputs a certificate if it is guaranteed that the image can not be adversarially perturbed. This is done by checking whether there exists any nearby image (within a prescribed & distance) with a different label than the image being classified. While theoretical bounds exist on the size of this distance that hold for any classifier (Shafahi et al. (018)) exactly computing bounds for specific classifier and test image is hard. Alternatively, the verifier may output a lower bound on the distance to the nearest image of a different label. This latter distance is referred to as the certifiable radius. Most of these verifiers provide a rather loose bound on the certifiable radius. However, if the verifier is differentiable, then the network can be trained with loss that promotes tightness of this bound. We use the term certificate training to refer to the process of training with a loss that promotes strong certificates. Interval bound propagation (IBP) (Mirman et al., 2018 Gowal et al. (018) is very simple verifier that uses layer-wise interval arithmetic to produce a certificate. Even though the IBP certificate is generally loose, after certificate training, yields state-of oh-tth-artttt certifiably-robun robust models for -norm bounded attacks (Gowal et al. 2018 Zhang et al.) (019b). In this paper, we extend IBP to train certifiably-robust networks resilient patch attacks. We first introduce some notation and basic algorithms for IBP training.
Notation We represent a neural network with a series of transformations (k) for each of its & layers. We use (*a) E RT to denote the output of layer k, where ny is the number units in the ttth layer and (0) stands for the input. Specifically, the network computes
2 (k) = (22
Vk= = I,...,K K.
Certification Problem To produce a certificate for an input zo. we want to verify that the following condition is true with respect to all possible labels y:
(Cyerve - e,)² z(K) = my 2 0
(0) E B(zo)
Vy.
(3)
Here, e is the tth basis vector, and m, is called the margin following Wong & Kolter (017)). Note that myerue is always equal to O. The vector m contains all margins corresponding to all labels. (xr)) is the constraint set over which the adversarial input image may range. In a conventional setting, this an l ball around zq. In the case of patch attack, the constraint set contains all images formed by applying patch to zo;
B(xo)) = {A(zo, p. D.p E P and I E L).
(4)
The Basics of Interval Bound Propagation (IBP) We now describe how to produce certificates using interval bound propagation as in (Gowal et al. 2018). Suppose that for each component in =(x-1) we have an interval containing all the values which this component reaches as 20) ranges
over the ball (zx)). If 2(k) = (2(*)))))) is a linear (or convolutional) layer of the form 2(k) =
(k-))((-11) + b(6), then we can get an outer approximation of the reachable interval range of activations by the next layer x(t) using the formulas below
z(()_ (()) 2(1-11 + (1--1)
z(k-1) - 2(k-1)
+ [W(K))
+ ((()
(5)
2
2 (k) ((A)) (k--1) 1) (b-1
z(k-1)
11k-11
(A)))
+ (AA)
(6)
2
Here z(k11) denotes the upper bound of each interval, (k=1)) the lower bound, and [W](A] the element-wise absolute value. Alternatively, if (1)) (z(k-D) is an element-wise monotonic activation (e.g., ReLUU,, then we can calculate the outer approximation of the reachable interval range of the next layer using the formulas below.
[(k) = (k) (3((-1)) 2()) (A) (2(k-1))
(7)
(8)
4

---

Published as a conference paper at ICLR 2020
When the feasible set (zz)) represents simple Lo attack, the range of possible 20) values is trivially characterized by interval bound 20)) and 2(") Then, by iteratively applying the above rules, can propagate intervals through the network and eventually get z(K) and z(K) A certificate can then be given if we can show that (3 is always true for outputs in the range =(K) and 2(k) with respect to all possible labels. More specifically, we can check that the following holds for all y
my e Virme x(K) of
(K) "Yrra
x(K) 2 0 Ay.
Training for Interval Bound Propagation To train a network to produce accurate interval bounds, simply replace standard logits with the -m vector in (3). Note that all elements of m need to be larger than zero to satisfy the conditions in (3). and Wetrur is always equal to zero. Put simply, we would like y.r.e 0 to be the least of all margins. We can promote this condition by training with
the loss function
Certificate Loss = Cross Entropy Loss(- m. y)-
(10)
Unlike regular neural network training, stochastic gradient descent for minimizing equation T0 is unstable, and a range of tricks are necessary to stabilize IBP training (Gowal et al.) 2018). The first trick is merging the last linear weight matrix with (eg, - Egecue) before calculating m,, This allows a tighter characterization of the interval bound that noticeably improves results. The second trick uses an "epsilon schedule" in which training begins with a perturbation radius of zero, and this radius is slowly increased over time until sentinel value is reached. Finally, mixed loss function containing both a standard natural loss and an IBP loss is used.
In all of our experiments, we use the merging technique and the epsilon schedule, but do not use mixed loss function containing a natural loss as it does not increase our certificate performance.
4.2 CERTIFYING AGAINST PATCH ATTACKS
We can now describe the extension of IBP to patches. If we specify the patch location, one can represent the feasible set of images with simple interval bound: for pixels within the patch, the upper and lower bound is equal to I and For pixels outside of the patch, the upper and lower bounds are both equal the original pixel value. By passing this bound through the network, would be able to get m single location and verify that they satisfy the conditions in
However, we have to consider not just a single location, but all possible locations L to give certificate. To adapt the bound to all possible location, we pass each of the possible patches through the network, and take the worst margin. More specifically,
th (L), min m single patch (1) Vy. Tel.
(11)
Similar to regular IBP training, we simply use m (L) to calculate the cross entropy loss for training and backpropagation,
Certificate Loss = Cross Entropy Loss( - mm (m. v).
(12)
Unfortunately, the cost of producing this naive certificate increases quadratically with image size. Consider that a CIFAR-I0 image is of size 32x32, requiring over a thousand interval bounds, one for each possible patch location. To alleviate this problem, we propose two certificate training methods: Random Patch and Guided Patch, so that the number of forward passes does not scale with the dimension of the inputs.
Random Patch Certificate Training In this method, we simply select random set of patches out of the possible patches and pass them forward. level of robustness is achieved even though very small number of random patches are selected compared to the total number of possible patches
m random patches (L), m S6 (S),
(13)
where S is random subset of L. Similarly, the random patch certificate loss is calculated as below. Random Patch Certificate Loss Cross Entropy Loss( m random patches (I.), y)
(14)
5

---

Published as a conference paper at ICLR 2020
Guided Patch Certificate Training In this method, propose using U-net (Ronneberger et al. 2015) to predict m single patch and then randomly select a couple of locations based on the predicted m siigle patch so that fewer patches need to be passed forward.
Note that very few patches contribute to the worst case bound m in TT). In fact, the number of patches that yield the worst case margins will be no more than the number of labels. If we know the worst-case patches beforehand, then we can simply select the few worst-case patches during training.
We propose use U-net as the number of locations and margins is very large. For square patch of size n. X и and an image of size m x m, the total number of possible locations is (m - n + 1) and for each location the number of margins is equal to the number of possible labels.
m pred
U-net(image)
(15)
dim m pred)
(m + m + 1, of labels).
(16)
Given the U-net prediction of mnree we then randomly select a single patch for each label based on the softmax of the predicted mo The number of selected patches is equal to the number of labels.
After these patches are passed forward, the U-net is then updated with a meen-squared-eme loss between the predicted margins mndd and the actual margins m "ctuall Note that only few patches are selected at time, so that the mean-square rean--squred-erro only passes through the selected patches.
U-net Loss (meed m actual).
(17)
The network trained with the following loss:
Guided Patch Certificate Loss Cross Entropy Loss( guided patches (T), y)-
(18)
Certification Process In all our experiments, we check that equation satisfied by iterating over all possible patches and forward- passidg the interval bounds generated for each patch; this overhead tolerable evaluation time.
4.3 CERTIFYING AGAINST SPARSE ATTACKS
IBP can also be adapted to defend against sparse attack where the attacker is allowed to modify fixed number (k) of pixels that may not be adjacent to each other (Modas et al. 2019). The only modification is that we have to change the bound calculated from the first layer to
2 (1)
(1) (0)
tops
(1)
w!! 20))
|W
2,t Itops
Vi
(19)
and apply equation 5 and (6) for the subsequent layers. Here, (-)opp is the sum of the largest le elements in the vector.
EXPERIMENTS
In this section, compare certified defenses with exiting algorithms two datasets and three model architectures of varying complexity. We consider a strong attack setting in which adversarial patches can appear anywhere in the image. Different training strategies for the certified defense also compared, which shows a trade-off between performance and training efficiency. Furthermore, we evaluate the transferability of model trained using square patches other adversarial shapes, including shapes that do not fit in any certified square. The training and architectural details can be found in Appendix A.I We also present preliminary results on certified defense against sparse attacks.
5.1 COMPARISON AGAINST EXISTING DEFENSES
In this section, we study the effectiveness of our proposed IBP certified models against an adversary that is allowed to place patches anywhere in the image, even top of the salient object. If the patch sufficiently small, and does not cover a large portion of the salient object, then the model should still classify correctly, and defense against the perturbation should be possible.
In the best case, our IBP certified model able to achieve 91.6% certified (Table with respect to a 2x2 patch (~~ -5% of image pixels) adversary MNIST. For more challenging cases, such 5

---

Published as a conference paper at ICLR 2020
5 2.5% of image pixels) patch adversary CIFAR-10 10, the certified adversarial accuracy is only 24.9% (Table Even though these existing defenses appear to achieve better or comparable adversarial accuracy our IBP certified model when faced with weak adversary, when faced with a stronger adversary their adversarial accuracy dropped to levels below our certified accuracy for all cases that analyzed.
When evaluating existing defenses, we only report cases where non-trivial adversarial accuracy is achieved against weaker adversary. We do not explore cases where LGS and DW perform so poorly that no meaningful comparison can be done. LGS and DW are highly dependent on hyperparameters work effectively against naive attacks, and yet neither Naseer et al. (2019) nor Hayes (2018) proposed a way to learn these hyperparameters. By trial and error, we were able to increase the adversarial accuracy against weaker adversary for some settings, but not all. In addition, we also notice peculiar feature of DW: when we increase the adversarial accuracy, the clean accuracy degrades, sometimes so much that it is even lower than the empirical adversarial accuracy. This happens because DW always removes patch from the prediction. When adversarial patch is detected, is likely to be removed, enabling correct prediction. On the other hand, when there are no adversarial patches, DW removes actual salient information, resulting in lower clean accuracy.
Here we did not compare our results with adversarial training, because even though it produces some of the most adversarially robust models, it does not offer any guarantees the empirical robust accuracy, and could still be decreased further with stronger attacks. For example, Wang et al.) (2019) proposed stronger attack that could find 47% more adversarial examples compared gradient based method. Further, adversarial training on all possible patches would be even more expensive compared certificate training, and is slightly beyond our computational budget.
Compared to state-of-the-arr certified models for CIFAR with perturrbaaa,,,n, where Zhang et al. (2019a) proposed deterministic algorithm that achieves clean accuracy of 34.0%, our clean accuracy for our most robust CIFAR 5 x model is 47.8% when using a large model ()a
Table 2: Comparison of our IBP certified patch defense against existing defenses. Empirical adversar- ial accuracy is calculated for 400 random images in both datasets. All results are averaged over three different models.
Dataset
Patch Size
Adversary
Defense
Clean Accuracy
Empirical Certified
Adversarial Accuracy
Accuracy
MNIST
2 X 2
IFGSM
None
98.4%
80.1%
2 x 2
IFGSM
LGS
97.4%
90.0%
x 2
IFGSM LGS
LGS
97.4%
60.7%
2 2
IFGSM
IBP
98.5%
93.9%
91.6%
5 x
IFGSM
None
98.5%
3.3%
5 x 5
IFGSM
IBP
92.9%
66.1%
62.0%
CIFAR
2x2
IFGSM
None
66.3%
25.4%
2
IFGSM
LGS
64.9%
31.3%
2 2x2
IFGSM LGS
LGS
64.9%
24.2%
2 x
IFGSM
DW
47.1%
43.3%
x 2
IFGSM + DW
DW
47.1%
20.2%
x 2
IFGSM
IBP
48.6%
45.2%
41.6%
5 X 5
IFGSM
None
66.5%
0.4%
X 5
IFGSM
LGS
51.2%
22.11%
5 X 5
IFGSM LGS
LGS
51.2%
0.5%
x 5
IFGSM
DW
45.3%
59.3%
x 5
IFGSM + DW
DW
45.3%
15.6%
5
IFGSM
IBP
33.9%
29.1%
24.9%
5.2 COMPARISON OF TRAINING STRATEGIES
We find that given fixed architecture all all-patch certificate training achieves the best certified accuracy. However, given a fixed computational budget, random and guided training significantly outperform all-patch training. Finally, guided-patch certificate training consistently outperforms random-patch
7

---

Published as a conference paper at ICLR 2020
certificate training by slim margin, indicating that the U-net is learning how to predict the minimum margin m.
In Table see that given fixed architecture all all-patch certificate training significantly outperforms both random-pad -aaohh certificate training and guided-patcl certificate training in terms of certified accuracy, outperforming the second best certified defenses in each task by 2.6% (MNIST, 2 x 2), 7.3% (MNIST, 5 x 5), 3.9% (CIFAR-10, 2 x 2), and 3.4% (CIFAR-10) 10, x 5). However, all-patch certificate training is very expensive, taking on average to 15 times longer than guided-patch certificate training and over 30 to 70 times longer than random-patch certificate training.
On the other hand, given limited computational budget, random-patch and guided-patch training significantly outperforms all-patch training. Due to the efficiency of random- -ptthhapchhhhh and guided-pateh training, they scale much better large architectures. By switching wide convolutional network), we are able to boost the certified accuracy by over 10% compared to the best performing all all-patch small model (Table 2 Note that we are unable to all all-patch train the same architecture as it will take almost 15 days to complete, and is out of our computational budget.
large architecture (5 layer
Guided-patch certificate training is slightly more expensive compared to random patch, due to overhead from the U-net architecture. However, given the 10 patches picked, guided-patch certificate training consistently outperforms aadom--ptch certificate training, indicating that the U-net learning how to predict the minimum margin m.
Table 3: Trade-off between certified accuracy and training time for different strategies. The numbers next to training strategies indicate the number of patches used for estimating the lower bound during training. Most training times measured a single 2080Ti GPU, with the exception of all-patch training which run on four 2080Ti GPUs. For that specific case, the training time is multiplied by for fair comparison. See Appendix (A.6 more detailed statistics. "indicates the performance of the best performing large model trained with either random or guided patch. Detailed performance of the large models can be found in Appendix A.5
2 X 2
5 x
Dataset
Training
Clean Accuracy
Certified Accuracy
Training Time(h)
Clean Accuracy
Certified Accuracy
Training Time(h)
Strategy
MNIST
All Patch
98.5%
91.5%
9.3
92.0%
60.4%
8.4
Random( 1)
98.5%
82.9%
0.2
96.9%
24.1%
0.4
Random 5)
98.6%
86.6%
0.3
95.8%
42.1%
0.3
Random( 10)
98.6%
87.7%
0.3
95.6%
49.6%
0.3
Guided (10)
98.6%
88.9%
2.2
95.0%
53.1%
2.6
CIFAR
All Patch
50.9%
39.9%
56.4
33.5%
22.0%
45.8
Random( 1)
53.6%
21.6%
0.6
43.6%
6.1%
0.6
Random(
52.9%
32.3%
0.7
39.0%
14.6%
0.7
Random( 10)
51.9%
35.6%
0.8
38.8%
18.6%
0.8
Guided( (10)
52.4%
36.0%
3.7
37.9%
18.8%
3.7
Large Model*
65.8%
51.9%
22.4
47.8%
30.3%
15.4
5.3 EFFECTIVENESS AGAINST SPARSE ATTACK
The IBP based method can also be used defend against sparse attack, see Section Its performance is reasonable compared to patch defense (e.g. 91.5% certified accuracy for x patch vs 90.8% for k=4), even though the sparse attack model much stronger. For convolutional networks. we increase the size of the first convolutional layer (i.e. from 3 x 3 to 11 x 11) so the interval bounds calculated are tighter. However, despite the change, fully-connected network still performs much better. For example, the certified accuracy drops from 25.6% to 13.8% when switch from fully-connected to convolutional network for CIFARIO 10 and drops from 90.8% to 75.9% for MNIST respectively. Detailed results shown in the Appendix A.4 Table
Table compares our approach with the state-of-the-ae certified sparse defense (Random Abla- tion) Levine & Feizi (2019). We their best model with the largest medium radii to certify against various levels of sparsity. As shown in the table, our method achieves higher certified accuracy on the MNIST dataset over all the sparse radii, but lower CIFAR-10. O. It worth noting that
8

---

Published as a conference paper at ICLR 2020
using much smaller and simpler model (a fully-connected network) compared to Random Ablation, which uses ResNet-50.
Table 4: Certified accuracy for sparse defenses with IBP and Random Ablation.
Dataset Sparsity (k)
Model
Clean Accuracy
Certified Accuracy
MNIST
1BP-sparse
98.4%
96.0%
IBP IBP-sparse
97.8%
90.8%
10
IBP-sparse
95.2%
86,8%
Random Ablation
96.7%
90.3%
Random Ablation
96.7%
79.1%
10
Random Ablation
96.7%
29.2%
CIFAR
IBP-sparse
48,4%
40.0%
IBP-sparse
42.2%
31.2%
10
IBP-sparse
37.0%
25.6%
Random Ablation
78.3%
68.6%
Random Ablation
78.3%
61.3%
10
Random Ablation
78.3%
45.0%
5.4 TRANSFERABILITY TO PATCHES OF DIFFERENT SHAPES
Since real- world adversarial patches may not always be square, the robust transferability of the model to shapes other than the square is important.
Therefore, we evaluate the robustness of the square-pater tatche model adversarial patches of different shapes while fixing the number of pixels. In all these experiments, we evaluate the certified accuracy for our largest model, on both MNIST and CIFAR datasets. We evaluate the transferability to various shapes including rectangle, line, parallelogram, and diamond. With the exception of rectangles, all the shapes have the exact same pixel count as the patches used for training. For rectangles, we use multiple choices of width and length, obtaining some combinations with slightly more pixels, and the worst accuracy is reported in Table The exact shapes used can be found in Appendix A..2 A.22
The certified accuracy of our models generalize surprisingly well to other shapes, losing no more than than 5% in most cases for MNIST and more than 6% for CIFAR-10 (T The largest degradation of accuracy happens for rectangles and lines, and it is mostly because the rectangle considered has more pixels compared to the square, and the line has less overlaps. However, it is still interesting that the certificate even generalizes to a straight line, even though the model was never trained be robust lines. In the case of MNIST with small patch size, the certified accuracy even improves when transferred to lines.
Table 5: Certified accuracy for square-patch trained model for different shapes
Dataset
Pixel Count
Square
Rectangle
Line
Diamond
Parallelogram
MNIST
91.6%
92.5%
91.6%
92.3%
16
69,4%
55.4%
46.7%
68.13%
70.2%
25
59.7%
50.9%
32.4%
53.6%
55.2%
CIFAR
4 50.8%
46.1%
48.6%
49.8%
36.9%
29.0%
32.1%
35.7%
36.3%
25
30.3%
25.1 1%
29.0%
30.1%
30.7%
6 CONCLUSION AND FUTURE WORK
After establishing the weakness of known defenses to patch attacks, we proposed the first certified defense against this model. We demonstrated the effectiveness of our defense two datasets, and proposed strategies to speed up robust training. Finally, we established the robust transferability of trained certified models to different shapes. In its current form, the proposed certified defense is unlikely to scale to ImageNet, and we hope the presented experiments will encourage further work along this direction.

---

Published as a conference paper at ICLR 2020
REFERENCES
Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give false sense of security: Circumventing defenses to adversarial examples. arXiv preprint arXiv:1802.0044 2018.
Tom B Brown, Dandelion Mané, Aurko Roy, Martín Abadi, and Justin Gilmer. Adversarial patch.
arXiv preprint 1721::17.,.0966,, 2017.
Jeremy M Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. arXiv preprint 1902. 2019.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pp. 248-255. leee, 2009.
Logan Engstrom, Brandon Tran, Dimitris Tsipras, Ludwig Schmidt, and Aleksander Madry. rotation and translation suffice: Fooling cnns with simple transformations. arXiv preprint arXiv: 1712.077,, 2017.
Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Uesato, Timothy Mann, and Pushmeet Kohli. On the effectiveness of interval bound propagation for training verifiably robust models. arXiv preprint arXiv: 12715, 2018.
Jamie Hayes, On visible adversarial perturbations & digital watermarking. In Proceedings of the IEEE Conference on Computer Vision and Puttern Recognition Workshops, pp. 1597-1604, 2018.
Danny Karmon, Daniel Zoran, and Yoav Goldberg. Lavan: Localized and visible adversarial noise.
arXiv preprint
2018.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Cassidy Laidlaw and Soheil Feizi. Functional adversarial attacks, 2019.
Mark Lee and Zico Kolter. On physical adversarial patches for object detection, 2019.
Alexander Levine and Soheil Feizi. Robustness certificates for sparse adversarial attacks by random- ized ablation. arXiv preprint arXiv:1911.09272. 2019.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv:/706.0000 170.06608, 2017.
Matthew Mirman, Timon Gehr, and Martin Vechev. Differentiable abstract interpretation for provably robust neural networks. In International Conference on Machine Learning, pp. 3575-3583, 2018.
Apostolos
Modas, Seyed-Mohsen Moosavi-Dezfooli, and Pascal Frossard. Sparsefool: few pixels make big difference.. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 9087-9096, 2019.
Muzammal Naseer, Salman Khan, and Fatih Porikli. Local gradients smoothing: Defense against localized adversarial attacks. In 2019 JEEE Winter Conference on Applications of Computer Vision (WACV), pp. 1300-1307. IEEE, 2019.
Olaf Ronneberger, Philipp Fischer, and Thomas Brox. U-net: Convolutional networks for biomedical image segmentation. In International Conference on Medical image computing and computer- assisted intervention, pp. 234-241. Springer, 2015.
Ali Shafahi, W Ronny Huang. Christoph Studer, Soheil Feizi, and Tom Goldstein. Are adversarial examples inevitable? arXiv preprint arXiv: /809.02000.02 104, 2018.
Ali Shafahi, Mahyar Najibi, Amin Ghiasi, Zheng Xu, John Dickerson, Christoph Studer, Larry S Davis, Gavin Taylor, and Tom Goldstein. Adversarial training for free! arXiv preprint arXiv: 1904. / 12843, 2019.
10

---

Published as a conference paper at ICLR 2020
Mahmood Sharif, Sruti Bhagavatula, Lujo Bauer, and Michael K Reiter. Adversarial generative nets: Neural network attacks on state-of-the-an art face recognition. arXiv preprint 1001:0800.0000 2017.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv: 1eXxiv:400.15555 1556, 2014.
Christian Szegedy, Vincent Vanhoucke, Sergey loffe, Jon Shlens, and Zbigniew Wojna. Rethinking the inception architecture for computer vision. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2818 18-8-2826, 2016.
Florian Tramèr and Dan Boneh. Adversarial training and robustness for multiple perturbations. arXiv preprint 1994. 13000, 2019.
Shiqi Wang. Yizheng Chen, Ahmed Abdou, and Suman Jana. Enhancing gradient-basee attacks with symbolic intervals, 2019.
Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. arXiv preprint arXiv:
2017.
Eric Wong, Frank R Schmidt, and J Zico Kolter. Wasserstein adversarial examples via projected sinkhorn iterations. arXiv preprint arXiv:1902.07900 2019.
Zuxuan Wu, Ser-Nam Lim, Larry Davis, and Tom Goldstein. Making an invisibility cloak: Real world adversarial attacks on object detectors. arXiv preprint arXiv:1910.1466 2019.
Huan Zhang, Hongge Chen, Chaowei Xiao, Bo Li, Duane Boning, and Cho-Jui Hsieh. Towards stable and efficient training of verifiably robust neural networks, 2019a
Huan Zhang, Hongge Chen, Chaowei Xiao, Bo Li, Duane Boning, and Cho-Jui Hsich. Towards stable and efficient training of verifiably robust neural networks. arXiv preprint 1rXiv:1906.06316, 2019b.

---

Published as a conference paper at ICLR 2020
A APPENDIX
A.1 EXPERIMENTAL SETTINGS AND NETWORK STRUCTURE
We evaluate the proposed certified patch defense on three neural networks: a multilayer perceptron (MLP) with one 255-neuron hidden layer, and two convolutional neural networks (CNN) with different depths. The small CNN has two convolutional layers (kernel size 4, stride 2) of and 8 output channels each, and fully connected layer with 256 neurons. The large CNN has four convolutional layers with kernel size (3, 4, 3, 4), stride (1, 2. 1, 2), output channels (4, 4, 8 ,8), and two fully connected layer with 256 neurons. We run experiments with two different patch sizes 2 x and
two datasets, MNIST and CIFARIO. For all experiments, we are using Adam (Kingma & Ba 2014) with learning rate of 5e 4 for MNIST and 1e for CIFARIO, and with no weight decay. We also adopt a warm-up schedule all experiments like (Zhang et al. 2019b), where the input interval bounds start
and grow [-1,1] after 61/121 epochs for MNIST/CIFAR 10 respectively. We train the models for total of 100/200 epochs for MNIST/CIFARII 10, where in the first 61/121 epochs the learning rate is fixed and in the following epochs, we reduce the learning rate by one half every 10 epochs.
In addition, following (Gowal et al., 2018), we further evaluate the CIFARIO on larger model which has convolutional layers with kernel size 3 and fully connected layer with 512 neurons. This deeper and wider model achieves the clean accuracy around 89%, and has 17M parameters in total. Table & in Appendix A.5 describes the full certified patch results for this large model.
A.2 SAMPLE SHAPES FOR ATIZATINNNN EXPERIMENTS
We demonstrate generalization to other patch shapes that were not considered training, obtaining surprisingly good transfer in robust accuracy; the figure below and the results in Table
2 shapes
5 5 shapes
Figure 1: Examples of shapes with pixels number 4 and 25, From left to right square, parallelo- gram, diamond and rectangle (line) respectively.
12

---

Published as a conference paper at ICLR 2020
A.3 BOUND POOLING
Besides random-patch certificate training and guided-patch certificate training, we also experimented with the idea of bound pooling. All-patch training is very expensive as bounds generated by each potential patch has to be forward passed through the complete network. Bound pooling partially relieves the problem be pooling the interval bounds in intermediate layers thus reducing the forward pass in subsequent layers.
Specifically, given a set of patches IP, the interval bounds in the ith layer are (P) {2(0) (p) pp
P) and p (2(() (p) E TP). We can reduce the number of interval bounds by partitioning P into n subsets {S ..... S") and calculate new of bounds 2 (IP) {maxpes, z (p) E [n]]
[m]). Depending on how partitioned, the bound pooling would work differently. In our experiments, we always select adjacent patches for each & with the assumption that adjacent patches tend to generate similar bounds thus resulting in tighter certificate.
and ( poo! = pmin (p)
Bound pooling. similar random- and guided- patch training, trades performance for efficiency compared to all-patch certificate training. However, the trade off is not favorable compared to random-patch and guided-pate training. For example, Table Pooling 16 (4 4) patches the first layer reduces training time by 35% while loosing 0.7% in performance (on MNIST 2 x 2), but similar level performance can be achieved with guided-patch training with almost 90% reduction in training time. The trade off becomes greater when the model becomes larger. Overall, bound pooling is still quite expensive, and cannot scale to larger models like aandomppach or guided-patel training.
Table 6: Comparing bound pooling with the guided-patch and random- aandom-patch training. Pool means that the adjacent 4 X 4 patches (16 patches) are pooled together in the first layer. Pool 2-2 means that pooled together in the first layer and then another 2 bound pooling happens at the second layer. This is similar to 4 x 4 pooling except the pooling operation is distributed between the first and second layer. All experiments are performed on a 4-layer convolutional network.
the adjacent 2 x 2 bounds
2 x 2
5 x 5
Dataset
Training
Clean
Certified Accuracy
Training Time(h)
Clean
Certified
Training Time(h)
Strategy
Accuracy
Accuracy
Accuracy
MNIST
All Patch
98.5%
91.6%
20.1
90.0%
59.7%
16.3
Pool
98.0%
91.1%
15.8
85.2%
54.2%
11.6
Pool 4
97.2%
89.9%
13.2
70.4%
38.3%
10.2
Random
98.5%
81.9%
0.3
96.8%
24.8%
0.4
Random 5)
98.6%
86.5%
0.3
94.9%
42.0%
0.5
Random( 10)
98.6%
87.5%
0.5
94.7%
50.4%
0.6
Guided(10)
98.7%
88.9%
2.2
94.0%
53.2%
3.4
CIFAR
All Patch
49.6%
41.6%
22.5
34.0%
25.0%
18.6
Pool 2
48.1%
39.4%
17.3
32.4%
24.2%
14.5
Pool 4
44.9%
37.1%
16.3
28.3%
20.6%
13.6
Pool 2-2
45.0%
37.4%
16.5
25.3%
19.1%
13.8
Random( I)
53.2%
32.4%
0.6
42.7%
11.0%
0.6
Random 5)
52.2%
39.5%
0.9
37.8%
19.6%
0.9
Random 10)
50.8%
38.6%
1.0
38.4%
21.9%
1.0
Guided(10)
53.0%
39.8%
4.0
36.1%
23.0%
3.9
13

---

Published as a conference paper at ICLR 2020
A.4 MULTI-PATCH SPARSE TRAINING
Here we list the detailed certified accuracy for various sparsity levels and model architectures.
Table 7: Certified accuracy for sparse defenses with varying sparsity and models on both MNIST
and CIFARIO, where "Conv e" represents for the convolutional network with first layer kernel size
Dataset MNIST
Sparsity (k)
Model
Clean Accuracy
Certified Accuracy
mlp
98.4%
96.0%
mip
97.8%
90.8%
10
mlp
95.2%
86.8%
Conv3x3
97.0%
88.3%
Conv3x3
92.7%
75.9%
CIFAR
mlp
48.4%
40.0%
mlp
42.2%
31.2%
10
mip
37.0%
25.6%
Conv 1x11
34.8%
27.4%
4
Conv 1x11
25.1%
18.3%
10
Conv 1x11
17.2%
13.8%
13x13
38.6%
29.7%
4
Conv 13x13
28.1%
19.6%
10
Conv 13x13
22.4%
15.3%
A.5 TRAINING WITH LARGER MODELS
Recall that all-patch training considers all possible patches during training, which can be too expensive for larger models and/or images. The proposed random- and guided-patch training methods aim to reduce the training cost by considering only subset of patches; please see Section 4.2 for more details.
Table The random and guided training strategy could yield significantly stronger model compared to all-patch training given a fixed computational budget. The random and guided training strategy allows us train a larger model that would be infeasible train otherwise. The guided-pater large model is able to boost the certified accuracy by over 10% compared to the best performing all all-patch
small model.
Dataset
Patch
Training
Model
Clean Accuracy
Certified Accuracy
Training Time(h)
Size
Strategy
CIFAR
2x
All Patch
mlp
50.8%
35.5%
9.1
2 layer conv
52.4%
42.6%
10.7
4 layer conv
49.6%
41.6%
22.5
5 layer
(wide)
366.0
Random( 10)
5 layer conv (wide)
64.7%
49.0%
9.5
Random(20)
layer conv (wide)
64.4%
50.8%
15,8
Guided(10)
5 layer conv (wide)
66.5%
49.2%
12.2
Guided(20)
layer conv (wide)
65.8%
51.9%
22.4
CIFAR
5X 5
All Patch
mlp
31.1%
18.8%
7.1
layer conv
35.5%
22.3%
8.7
4 layer conv
34.0%
25.0%
18.6
5 layer conv (wide)
360.0
Random(10) (10)
5 layer
(wide)
48.6%
29.9%
9.4
Random(20)
5 layer conv (wide)
47.8%
30.3%
15.4
Guided(10)
layer conv (wide)
48.4%
29.0%
12.4
Guided(20)
5 layer conv (wide)
47.6%
29.6%
23.8
14

---

Published as a conference paper at ICLR 2020
A.6 DETAILED STATISTICS ON TRAINING STRATEGIES
Here we list the detailed statistics for each training strategies for Table
Dataset
Training
Model Architecture
Clean Accuracy
Certified
Training
Strategies
Accuracy
Time
MNIST
All Patch
2 layer convolution
98.63/%
91.38%
21.0
layer convolution
98.48%
91.63%
80.3
fully connected (255,10)
98.46%
91,47%
9.8
Random (1)
layer convolution
98.69%
82.57%
0.2
4 layer convolution
98.45%
81.87%
0.3
fully connected (255,10)
98.48%
84.32%
Random (5)
2 layer convolution
98. 75%
85.87%
0.3
layer convolution
98.57%
86.50%
0.3
fully connected (255,10)
98.62%
87.32%
0.2
Random (10)
layer convolution
98.739 7
87.31%
0.3
4 layer convolution
98.63%
87.54%
0.5
fully connected (255,10)
98.49%
88.13%
0.2
Guided (10)
layer convolution
98.60%
88.49%
2.3
4 layer convolution
98.70%
88.85%
2.2
fully connected (255,10)
98.63%
89.44%
2.2
CIFAR
All Patch
2 layer convolution
52.42%
42.57%
42.6
layer convolution
49.58%
41.57%
89.8
fully connected (255,10)
50.83%
35.49%
36.6
Random (1)
layer convolution
54.93%
29.13%
0.6
4 layer convolution
53.22%
32.35%
0.6
fully connected (255,10)
52.76%
03.21%
0.5
Random (5)
layer convolution
54.15%
37.30%
0.6
layer convolution
52.19%
39,45%
0,9
fully connected (255,10)
52.38%
20.17%
0.6
Random (10)
2 layer convolution
53.08%
39.32%
0.7
layer convolution
50.80%
38.57%
1.0
fully connected (255,10)
51.90%
28.97%
0.6
Guided (10)
layer convolution
53.04%
38.81%
3.7
layer convolution
52.97%
39.84%
4.0
fully connected (255,10)
51.32%
29.44%
3.6
Table 9: Detailed statistics for the comparison of training strategies 2x2
15

---

Published as a conference paper at ICLR 2020
Dataset
Training Strategies All Patch
Model Architecture
Clean Accuracy
Certified Accuracy
Training
Time
MNIST
layer convolution
91.88%
59.59%
28.4
4 layer convolution
90.03%
59.72%
65.2
fully connected (255,10)
93.96%
61.97%
7.2
Random (1)
2 layer convolution
96.27%
18.57%
0.2
layer convolution
96.83%
24.79%
0.4
fully connected (255,10)
97.60%
29.04%
0.2
Random (5)
layer convolution
95.82%
38.47%
0.2
4 layer convolution
94.85%
42.02%
0.5
fully connected (255,10)
96.73%
45.89%
0.2
Random (10)
layer convolution
95.55%
46.13%
0.3
4 layer convolution
94.76%
50.43%
0.6
fully connected (255,10)
96.40%
52.30%
0.2
Guided (10)
2 layer convolution
95.28%
50.28%
2.3
layer convolution
93.98%
53.17%
3.4
fully connected (255,10)
95.82%
55.89%
2.2
CIFAR
All Patch
layer convolution
35.48%
22.31%
34.8
4 layer convolution
33.95%
24.96%
74.4
fully connected (255,10)
31.05%
18.78%
28.4
Random (1)
layer convolution
45.71%
07.14%
0.6
layer convolution
42.65%
10.99%
0.6
fully connected (255,10)
42.34%
00.10%
0.5
Random (5)
layer convolution
42.85%
17.29%
0.6
layer convolution
37.80%
19.63%
0.9
fully connected (255,10)
36.23%
06.99%
0.6
Random (10)
layer convolution
41.90%
21.40%
0.7
4 layer convolution
38.41%
21.90%
1.0
fully connected (255,10)
36.04%
12.46%
Guided (10)
2 layer convolution
42.08%
20.77%
3.6
layer convolution
36.08%
23.01%
3.9
fully connected (255,10)
35.51%
12.56%
3.5
Table 10: Detailed statistics for the comparison of training strategies 5x5
16


Reviews:
[{"review_id": "rJefUZ0iFr", "reviewer": "AnonReviewer3", "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": "This paper proposed a certified defense method for adversarial patches. The paper is motivated by the finding that several existing works on adversarial patch defenses are easily \"breakable\" by in the white-box setting. The idea of the proposed method is derived Interval Bound Propagation (IBP), which is originally proposed for certified defense against adversarial noise. To simplify the certificate training in the patch defense setting (which original scales quadratically with respect to the image size), two randomized training methods are proposed. Lastly, experimental results indeed verify the effectiveness of the proposed method.\n\nThe paper is well-written and very well-organized. It is interesting to see supposedly strong adversarial patch defense methods \"break down\" in a very simple setting. And the contribution of the paper is significant to the field.\n\nI do have a question with regard to the randomized training method:\nAlthough random patches (or selected worse-case patches at random location) can be used for certificate training, in order to create a certificate during testing, does it mean that you do have to conduct many forward pass of the network with respect to all patches at all locations?", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "r1lTNkw6tS", "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": "This paper attempts to extend the Interval Bound Propagation algorithm from (Gowal et al. 2018) to defend against adversarial patch-based attacks. In order to defend against patches which could appear at any location, all the patches need to be considered. This is too computationally expensive, hence they proposed to use a random subset of patches, or a U-net to predict the locations of the patches and then use those patches to train. The algorithm is tested on the MNIST and CIFAR-10 datasets and it was shown that sometimes the IBP approach is useful for defense, although often with a significant loss on accuracy on clean data (e.g. on CIFAR the loss on clean accuracy is an astounding 300% -- from 66.5% - 35.7%).\n\nI think the technical contribution of this paper is a bit weak in that they mostly followed the original IBP and the only novelties are the random patch training and guided patch training. I partially like how the experiments are conducted, especially the one that generalizes to other shapes. On the other hand, the networks that are tested seem pretty poor by any standard. An experiment that is definitely missing is a CIFAR network that performs a little better than the current one. Clean accuracy of only 66.5% and 47.2% are very lousy for CIFAR.\n\nAnother missing experiment is one that would test on different epsilon values. I couldn't find what are the current epsilon values used?\n\nBesides, since this work is testing on adversarial patches, I would like to at least have it applied to some real-life images with patches that are of real-life size. I could care a bit less on how good it is, but one can still make an empirical test (e.g. certified defense accuracy on 5x5 patches, but empirical test using real-life sized patches 40x40 or 80x80) and see how the results would be. All the experiments mentioned above would significantly strengthen the experiments section of the paper.\n\nI don't think I read anywhere a confirmation that the testing is performed on all patches of the prescribed size. Could the authors please confirm whether this is true?\n\nMinor: \nThere is a typo in Eq. (5) and Eq. (6), where the second term multiplied by |W^(k)| should be \\underline{z}^(k-1) - \\bar{z}^(k-1) instead of \\underline{z}^(k-1) + \\bar{z}^(k-1)\n\nYou should mention that |W^(k)| stand for element-wise absolute value when it first appears.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "r1lKQwihYS", "reviewer": "AnonReviewer2", "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 certified defense for adversarial patch attacks.\nTechnically, the authors use the well developed IBP based methods (Gowal et\nal., 2018, Mirman et al., 2018, Zhang et al. 2019).  The technique is simple\nbut effective. Since the number of possible patches are quadratic w.r.t image\ndimension, to reduce the number of bounds to propagate, the authors propose a\nU-Net based NN to predict the worst case scenario, and only propagate \"worst\ncase\" bounds predicted by the U-net.\n\nEmpirically, the proposed method gets good results, with certified accuracy\nsometimes even higher than empirical accuracy by previous methods.  The authors\nalso provide results for transferring robustness properties to shapes that are\nnot included during training.\n\nOverall, the contribution of this paper is novel, and results are promising,\nbut it still has some missing components, especially the idea of combining\nmultiple IBP bounds into one, which can be very effective for adversarial\npatches, as I will elaborate below.\n\nSuggestions and Questions:\n\nThe core idea behind IBP is that for whatever input perturbation is given (any\nLp norm or semi-norm, or non-norm based perturbations like patches at arbitrary\nlocations), it converts them to per-neuron lower and upper bounds after the\nfirst linear/conv layer.  For example, if the input perturbation is *two* patches\nB_1 and B_2, after propagating them through the first layer of the network, we\ngot two lower bounds l_{i,1}, l_{i,2} and two upper bounds u_{i,1}, u_{i,2} for\nthe i-th neuron. We then take the worst case bound, l_i = min(l_{i,1},\nl_{i,2}), u_i = max(u_{i,1}, u_{i,2}) and propagate only one set of bounds l_i\nand u_i to the next layer. The authors should explore on this direction, as\ndetailed below:\n\n1. For the exhaustive patch enumeration in (11), we can actually greatly reduce\nthe computation cost by combining the bounds of different patches after the\nfirst layer of the network, as I mentioned above. At the input layer, the\nnumber of bounds (each for one possible location of patch) are large; but after\nthe first linear/conv layer, we can compress them to one or a small group of\nbounds by taking the worst cast of them, like l_i = min(l_{i,1}, ...,\nl_{i,|L|}), u_i = max(u_{i,1}, ..., u_{i,2}). The patches close with each other\nshould also produces similar lower and upper bounds, so taking min or max over\nthem will not make the combined bounds much worse. This is better than U-net\nprediction since we are guaranteed to include the worst case scenario.\n\n2. Considering multiple patches (at different locations) on a single input. In\nthe simplest case, consider multiple 1x1 patches (in fact, this is equivalent\nto bounded L0 norm threat model); since each patch is 1x1 (only changing one\npixel), the bounds should be relatively tight after the first layer, and after\nthe first linear/conv layer we got 28*28 or 32*32 bounds which will be combined\ninto one or very few sets of lower and upper bounds that will be propagate into\nlater layers.  Multiple larger patches (2x2, 5x5) can be difficult since bounds\nare looser; multiple 1x1 in my opinion is both technically feasible and\npractically important, and should definitely be included in this paper.\n\n\nMinor issues:\n\n1. Eq. (5) and (6) are incorrect; the second term should be \\overline{z} -\n\\underline{z}. Also it is missing the bias term.\n\n2. In related works (section 4.1, page 3), (Weng et al., 2018) is not a defense\nmethod (it is a certification method, and no training is involved).\n\n3. In Table 3, it is better if the authors can provide empirical adversarial\naccuracy to IBP defended networks as well.\n\nOverall, I think it is a good paper but the authors should explore more to\nstrengthen their contributions. I gave a weak reject but I will not hesitate\nto recommend an accept as long as the authors can provide additional results\nmentioned above.\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a certified defense method for adversarial patch attacks. The proposed approach provides certifiable guarantees to the attacks, and the reviewers particularly find its experiments results interesting and promising. The added new experiments during the rebuttal phase strengthened the paper. There still is a remaining concern that is novelty is limited as this paper could be viewed as the application of the original IBP to patch attacks, but the reviewers believe in that its empirical results are important.
Decision: Accept (Poster)