Certified robustness against physically-realizable patch attack via randomized cropping
Authors: Wan-Yi Lin
Fatemeh Sheikholeslami
jinghao shi
Leslie Rice
J Zico Kolter
Venue:  (2021)
Keywords: adversarial machine learning
certifiable defense
patch attack

Abstract: This paper studies a certifiable defense against adversarial patch attacks on image classification. Our approach classifies random crops from the original image independently and the original image is classified as the vote over these crops.  This process minimizes changes to the training process, as only the crop classification model needs to be trained, and can be trained in a standard manner without explicit adversarial training.  Leveraging the fact that a patch attack can only influence some pixels of the image, we derive certified robustness bounds on the resulting classification. Our method is particularly effective when realistic physical transformations are applied to the adversarial patch, such as affine transformations. Such transformations occur naturally when an adversarial patch is physically introduced to a scene. Our method improves upon the current state of the art in defending against patch attacks on CIFAR10 and ImageNet, both in terms of certified accuracy and inference time.

Under review as a conference paper at ICLR 2021
ROBUSTNESS AGAINST PHYSICALLY- REALIZABLE PATCH ATTACKS VIA RANDOMIZED CROPPING
CERTIFIED
Anonymous authors Paper under double-bling review
ABSTRACT
This paper proposes certifiable defense against adversarial patch attacks on im- age classification. Our approach classifies random crops from the original image independently and classifies the original image as the majority vote over predicted classes of the crops. This process minimizes changes to the training process, as only the crop classification model needs to be trained, and can be trained in a standard manner without explicit adversarial training. Leveraging the fact that a patch attack can only influence certain number of pixels in the image, derive certified robustness bounds for the classifier. Our method is particularly effective when realistic transformations are applied the adversarial patch, such as affine transformations. Such transformations occur naturally when an adversarial patch is physically introduced in a scene. Our method improves upon the current state of the art in defending against patch attacks on CIFAR10 and ImageNet, both in terms certified accuracy and inference time.
INTRODUCTION
Despite their incredible success in many computer vision tasks, deep neural networks are known to be sensitive adversarial attacks; small perturbations to input image can lead large changes in the output. A wide range of defenses against adversarial attacks have been conducted in image classification, where the goal of the attacker simply change the predicted label(s) of an image Kurakin et al. 20166a Szegedy et al.) 2013) Madry et al. (0017). But these defenses have typically considered a relatively unrealistic threat model that does not easily extend to the physical settings. In particular, these works have mainly considered the so-called f.-norm threat model, where an attacker allowed to perturb the intensity at all pixels of the input image by a small amount. In contrast, alternatives, modeling scenaria
adversarial patch attacks are considered as physically-realizal where a small object is placed the scene so as to alter or suppress classification results (Brown et al. 2017). Here, the attack is spatially compact, but can change the pixel value any value within an allowable range.
This paper develops practical and provably robust defense against patch attacks. Inspired by the randomized smoothing defense (Cohen et al. 2019 Levine Feizi 2019) for the l--norm threat model, approach classifies randomly sampled sub-regions crops of an image independently and outputs the majority vote across these crops as the class prediction of the input image. This approach has numerous benefits. First, given the size of adversarial patches, we can compute the probability of a sampled crop overlapping with the attacked region (patch), and use this probability to determine if the classification outcome of an image can guarantced (certified) not be changed by any adversarial patch. Second, this approach is highly practical, as the crop classifier can be trained using standard architectures such as VGG (Simonyan & Zisserman, 2014) ResNet (He et al.][2011 (016) without the need for adversarial training. Indeed, random cropping is already common data augmentation strategy for training machine learning models, and thus the method can be trained via standard techniques. This is different from most existing work certifiable defenses against patch attacks (Levine & Feizi 2020 Xiang et al.) 2020 Chiang et al. 2020) which need extra computation for certification during training. Third, the proposed approach separates the training procedure from the patch threat model. thus making the method more robust against realistic settings of patch attacks, for example, patch transformations including rotation in x-y plane and aspect ratio

---

Under review as a conference paper at ICLR 2021
CIFARIO 10 2.4% patch
ImageNet 2.0% patch
certification acc.
time
certification acc.
time
(clean acc.)
in ms
(clean acc.)
in ms
Proposed method
47.5 (88.4)
0.7
12.2 (55.7)
21.8
De-rand, smoothing
17.5 (83.9)
17.5
3.2 (43.1)
703.2
PatchGuard: De-rand. smoothing
18.2 (84.5)
18.2
3.5 (43.6)
734.5
PatchGuard: Bagnets
27.1 (82.6)
0.7
9.6 (54.4)
25.7
Table I: Worst-case certified accuracy (%), clean accuracy (6), and certification time of the proposed method, De-randomized smoothing (Levine & Feizi 2020), and PatchGuard (Xiang et al.] (020)) with De-randomized smoothing and Bagnets as base structure. For each method, we list the worst certified accuracy under affine transformation of the patch. Note that this different from results in the original paper where patch transformations not considered.
changes. This is in sharp contrast to prior work that either have fixed strategies exclude parts of the image or extract features from fixed parts of the image (Levine & Feizi 2020 Xiang et al., 2020).
We summarize our main results on CIFARIO and ImageNet in Table in comparison with the current state of the art certifiable defense against patch attack (Xiang et al. 2020) with patch transformation. We report certified accuracy, which is the percentage of test images for which classification outcome equals to the ground truth label and guaranteed to not change under patch attack. Our method better in both speed and certified accuracy compared to De-randomized smoothing (Levine & Feizi, 2020) and PatchGuard (Xiang et al., (020)) under patch attack with possible affine transformations of the patch. In addition, our method outperforms these past approaches on ImageNet (though not on CIFAR10) in the setting where the patch aligns with coordinates of the image axes and does not undergo affine transformations as in Table 2 which was the setting considered in this past work.
We have made several contributions in this paper: first, we propose a defense against patch attack for image classification with certified robustness; second, the proposed method is fast in comput- ing image certification and robust against patch transformation; third, the proposed method can be applied to any image classification model with only minimal changes the training process.
2 BACKGROUND AND RELATED WORK
Adversarial attacks Adversarial attacks image classification have been known for some time, with original work coming out of the field of robust optimization (Ben- Tal et al. 2009). Test-
time attacks on ML models in general were studied in (Dalvi al.) 2004 Biggio al. 2013),
though the area gained momentum considerably when these methods were applied to deep learning systems to demonstrate that deep classifiers could be easily fooled by imperceptible changes to images (Szegedy et al. 2013) Goodfellow et af. 2014). In the following years many defenses against such attacks were proposed (Tramer et al. [2017] 7 Papernot al. (0166), although most heuristic approaches were later found to be ineffective (Athalye et al. 2018) Amongst the defense strategies that have stood the test of time are: adversarial training (Goodiellow et al. 2014 Kurakin al. 2016b, Madry et al. 2017), now commonly carried out using a projected gradient descent based approach for synthesizing adversarial attacks and then incorporating them into the training; and 2) provably robust training (Wong& & Kolter 2017: Raghunathan et al. (018)). Our approach is more related to the randomized smoothing- the latter direction, in which random points around the original input sampled and classified, and the predicted class of the original input is declared as the aggregation of these outputs.
methods (Cohen et al., [019]] Levine & Feizi (2019) in
The majority of the attacks mentioned above focus on attacks with bounded l.c -norm, where attacks are permitted to modify any pixel in the image by (at most) some fixed amount (and are usually permitted to design "universal" lo attacks have been studied as well AMoosavi-Dezfodi et al., (017)). If we consider real-life attackers, however, this level of freedom the attacker's side seems uncommon: attackers
adversarial perturbation for each new input image, though the so-called
2

---

Under review as a conference paper at ICLR 2021
would need to have access to the deep learning system the pixel level, which if true, also means that the system has already been compromised, making it unclear what benefit such an attack would have. In contrast, physically-realizable attacks such that can be implemented in the real world have been primarily modeled by the so-called patch attacks (Brown et al., 2017 Eykholt et al. 2018). where a particular "pattern' is designed fool deep learning system. We consider patch attacks as the threat model to defend against for it being physically realizable.
Defense against patch attacks There are also two threads of research in defending against patch attacks: 1) empirical defense strategies which show stronger empirical robustness but no analytical guarantees (MoCoyd et al., 2020 Naseer et al. 2019, Hayes, 2018); most of these methods rely on the fact that a patch attack has to produce strong local features that are very different from its neighborhood to change classification outcome; by analyzing local features, one can detect patch location or smooth out such feature values to reduce effectiveness of the patch, and 2) certified defenses which provide analytical lower bounds of classification accuracy under patch attack.
Certifiable defense against patch attacks Relevant to our work is the defense which provides provable lower bounds of classification accuracy. In Chiang et al. (2020), interval bound propaga- tion was used to provide certification, but the method is not applicable to commonly used image classification networks such as ResNet50 (He et al. 2016) or VGG16 (Simonyan & Zisserman 2014) because the depth of these architectures renders the bound trivial, and thus cannot provide useful certification. Another line of research utilizes the fact that an adversarial patch can only have local influence on the image. To reduce such influence, De-randomized smoothing (Levine & Feizi, 2020) uses ablation to exhaustively block all possible patch locations while (Zhang et al. (2020) uses Bagnets (Brendel & Bethge| 2019) with limited receptive field contain the number of affected features. Both methods then aggregate logits from ablated versions of images or local regions for final classification. PatchGuard (Xiang et al., 2020) adds additional detection of patch location and then sets features extracted from the detected locations to be zero. However all three methods re- quire special image classifier structures Levvnne & Feizi (2020) require three additional channels to express ablation. Zhang et al. (2020) is limited to Bagnets, and Xiang al. (2020) uses either of the former structures. Our proposed method instead can use any image classification architecture and does not require any additional steps to compute certification during model training except cropping images. This makes our method much more practical and easier to deploy onto existing systems. We will compare proposed method with De-damzodd smoothing (DRS) and PatchGuard (PG) in the experiments and an overview of the two prior arts can be found in Appendix A
3 PROVABLE PATCH DEFENSE WITH RANDOMIZED CROPPING
physically adversarial patch attack can be found by solving the optimization problem:
max E ((a.))>DDoT [e(ho 6, ()), v)]
dEA
where he : :X' + +' denotes some (presumably deep-network based) hypothesis function; 0 denotes parameters of the model, X' denotes the original input to the network and 8 X' the perturbation to the input: A C X' denotes the set of allowable perturbations; y E y denotes the true label; l y y R denotes loss function that measures the performance of the image classifier; and T X + X' is the set of transformations that the perturbation 6 might go through. The feasible set A denotes a simple allowable set of values for the patch, which typically would just be constrained to lie in valid RGB space. Patches overwrite portion of the image with the patch perturbation itself, at a given location with a given set of transformations, such as scaling, rotation, and other transformations in T. We refer to this combination as the patch application function A X' x X x + XX where A(x, 5, 1) denotes the application of patch to image J with transformation t. Attack budget considered for patch attack is the percentage of area that the patch covers over the whole image. Throughout this paper, we consider the patch being one connected area bounded by a rectangle with size Pa X Pj-
3.1 RANDOMIZED CROPPING DEFENSE
Although a patch attack can change pixel values to any arbitrary value, it can only influence the pixels within the patch itself. Therefore, networks extracting features with compact receptive fields
3

---

Under review as a conference paper at ICLR 2021
fe
Beron
ge
Hhire berea
Hhile
white
Beron
heron
Ihile
crop classifier
sBark
majority or f9
input image
random crops (R:)
crop labels (ae
Figure 1: Forward pass of randomized crop defense
and aggregating such local features for final classification are more robust against patch attacks. An example of such methods is Bagnets (Brendel & Bethgel 2019), where 1xl convolutional kernels used restrict the size of the receptive fields. Several existing techniques (Zhang et al., 2020 Xiang et al. 2020) utilize Bagnets for adversarial defense. However, the major drawback of Bagnets that extracts local features at fixed locations, therefore patch may be placed particular locations to influence more number of local features than other locations, thus reducing the worst- case robustness of Bagnets. In contrast to this architecture, we propose to extract local features at random locations by sampling random crops; this greatly reduces variations in the number of local features an adversarial patch can influence.
Based on above observations, we propose a randomized cropping approach as shown in Fig. given a full-size test image z as input, we first randomly select n crops uniformally over all possible locations, where crop size k; kj is smaller than image size m, m, in both dimensions. Each of the sampled crops (f;) then goes through the crop-based classifier go and its predicted class (g)) is obtained. The final classification of is the majority of ) The equivalent pseudo code of Fig. iis is in Appendix
Training randomized cropping classifier The robust classifier fo has three components: (1) sam- pling ni crops with uniform distribution, (2) classifying crops with go, and (3) majority voting. Since both random sampling of the crops via uniform distribution and majority voting have trainable parameters, the set of trainable parameters of fe is the same ga- Therefore training the robust classifier fo only involves training the crop classifier go. which can trained in standard ways with only data augmentation of randomly cropping the input as in Algorithm [ Other variables are either pre-determined hyperparameters (crop size k;, kj), or can be adjusted at time (number of crops n)).
Since the training procedure of randomized cropping classifier so only requires training the crop classifier go without any assumption on attack parameters (size, shape, and location), nor does it depend on hand-crafted rules or thresholds, our method is robust against different patch shapes. We show supportive experimental results in Section for this claim.
Training crop classifier for T epochs given crop size k; ky, image classifier go with loss function f, and dataset of M images
Algorithm 1:
Input: Full size image data æ, labels
for / = /,.., do .... M do Set 7 as a crop of size k; x Kú from image a at a random location; 0 0 Vol( y) //Update model weights with some optimizer, e.g. SGD
for
end
end
3.2 CERTIFIABLE ROBUSTNESS BOUND
Here we compute the probability that an image x is certified robust, i.e., the classification outcome of x cannot be changed by patch attack of given size. Given clean image, randomly sample crops { and obtain the set n predicted classes ( V of the crops. Let n, be the number crops that are predicted the majority in 1a and na be the number crops that predicted as
4

---

Under review as a conference paper at ICLR 2021
the second majority in (M Then if there exists patch attack that can change the classification outcome of x, then the patch must overlap with at least Rittll __ of the crops. On the other hand, if there are only less than Vigtol crops that overlap with the patch, then is certified robust. Therefore, Pe can be represented as the probability that, out of the n sampled crops, there are less than 02001 crops that overlap with the adversarial patch.
The below derivation assumes that the random selection is uniform over all crop locations with replacement, i.c., the same crop be selected again. Derivations for uniform sampling crops without replacement can be found in Appendix C
Following the argument above, first compute the probability that single sampled crop x; over- laps the adversarial patch, and use this probability to compute Pc. This probability can be computed the total number of crops overlapping with the patch (denoted by Nadv) divided by the number of all possible crops (Nait). Although physically-realizable adversarial patch can be at any location in the image, to guarantee robustness, we consider the worst-case scenario where the patch is the location that it can influence maximum number of crops (usually at the center of the image). When the patch is at the center of the image.
Dode min(p; + Kg 1, m, ki + 1) x min(py + +ky - 1, 1,m, - ki + 1);
(2)
Ball
(m²:
ki 1) (my kg + +1, and
Nado
Pa
(4)
Nall
After we sample n crops { } from the original input and { {go are the predicted 1- ny of them are the majority class y', and ng of them are the
classes the crops. Suppose (Ti (= recond-majority class y". If an adversarial patch changes the majority class, the minimal number of crop-based predicted classes that has to change will be
n1 72
12tto1
(5)
2
to make y" the majority class.
The probability of certification Pe is equal to the probability that out of { most 122tol of them overlaps with the adversarial patch:
Pc
CT + P Pa) (n-i)
(6)
where CT is the binomial coefficient (n choose i). If close to 1.0, the input image is certifiably robust under patch attack. In the experiments we select Pa 2 0.95 for an image to be considered certified. Throughout this paper, consider certified accuracy, meaning only data with predicted class y being the ground truth class will be considered for certification.
Note that because the crops randomly sampled, n2r011 and hence Pe is instance of random distribution. However we argue that when n is large enough, there 7i2tol and pe will have very small variance. Experiments verify this point are in Appendix [
The above computation of probability of certification in Eq. [6]agiin shows that is monotonically increasing with n2t11 So maximize number of certified robust images, the randomized cropping classifier should maximize 722011 which is equivalent to maximizing classification accuracy of This is another way to view that, train the proposed robust classifier for one only needs to train go.
4 EXPERIMENTAL RESULTS
Datasets, models, and device. We conduct experiments two benchmark image classification datasets: CIFARIO and ImageNet. For both datasets we evaluate over the whole evaluation set and report certified accuracy percentage of images that classified correctly and can be certified
5

---

Under review as a conference paper at ICLR 2021
10
ImageNet
ours
DRS
PG+DRS
ours
DRS
PG+DRS /
Patch Size
Bagnets
smoothing
Bagnets
0.4%
65.7
68.9
69.2/ / 53.2
24.7
22.3
24.8 / 23.1
1.0%
60.2
62.7
65.3 / 41.2
20.1
17.7
19.9 / 18.6
2.0%
55.2
60.9
1L.1/77.
16.4
14.0
16.0 13.3
2.4%
52.3
57.1
58.1 /3.77
15.3
13.1
14.7 11.2
3.0%
37.8
42.1
43.5 25.1
14.2
11.2
13.01 / 8.9
Table 2: Certified accuracy (%)
over CIFAR10 and ImageNet of our method, De-randomized
smoothing (DRS) (Levine Feizi 2020), and PatchGuard (PG)(Xiang et al. 2020). We consider images with pe 2 0.95 be certified.
with probability higher than 0.95. For CIFARIO, we use ResNet9 without the final pooling layer as ResNet34 as the crop model and resize and pad the image to 224x224. Experiments and timing are done on single Nvidia 2080 Ti GPU, and 16-core Intel cyclic learning rate with 10-3 initial learning rate. The
the crop model, and for ImageNet
17-5960X CPU. For both models models are trained 30 epochs and training time is 14 GPU-hours and 328 GPU-hours for CIFARIO and ImageNet, respectively.
we chose crop size of 10x10 (10% total area) for CIFAR and 80x80 (13% total area) for ImageNet; for these experiments we assume patch shape is square with no rotation. For each input image in CIFAR10, we randomly sample 128 crops and for each image in ImageNet we sample 256 crops.
Positional encoding. Because both CIFARIO and ImageNet images have certain region of inter- est which is usually in the center of the image, some parts of the images contain more information than others. For example, an image with label airplane usually has the airplane in the center, while the corners and edges have the background of sky airport. Therefore, crops sampled at different position of the image contain different information. To represent such information, we add learnable positional encoding (Vaswani al. 2017) to the first layer of our classifier.
Metric. Although the certification probability can be computed to any clean image despite of which data split this image is, in the experiment we follow the literature and report the certification accuracy, i.c., percentage of test images that are certified and classified correctly. This metric di- rectly reflects how robust and accurate the classifier is for example, the ideal classifier with 100% certified accuracy should classify all test images correctly and all test images' predicted class cannot be change by patch attack. We consider an image with Pe 2 0.95 be certified.
4.1 CLEAN ACCURACY AND INFERENCE TIME
Clean model accuracy and inference time per image compared with the above mentioned prior work are shown in Table Note that clean model accuracy and inference time remain the same with and without affine transformation of the adversarial patch. In terms of inference time our method faster under all cases. This is because although multiple forward passes are needed, the number of crop samples smaller than equivalent sub-regions in Bagnets and much smaller than number of all band- smoothed images as in De-randomized smoothing (DRS). PatchGuard with Bagnets (PG- (FG-Bagnets) slower than our method ImageNet for the additional reason of having to go through all logits of all possible classes sequentially. In addition, both De-randomized smoothing (DRS) and PatchGuard with De-randomized smoothing (PG-DRS) as the base structure are an order of magnitude slower than our method because De-randomized smoothing passes the whole image through the classifier, which is much more expensive then passing crops (10% or 13% of the whole image) through the classifier.

---

Under review as a conference paper at ICLR 2021
Pc 0.93
Pe 2 0.95
Pc 2 0.97
2 0.99
CIFARIO 2.4%
52.8
52.3
52.0
49.6
ImageNet 2.0%
17.2
16.4
15.3
14.1
Table 3: Certified accuracy (%) with different thresholds for Pe. without patch transformation
CIFARIO 2.4% patch
ImageNet 2% patch
ours
DRS
PG+DRS/
ours
DRS
PG+DRS
Transformation
Bagnets
smoothing
Bagnets
AR 1:1
52.3
57.1
58.1 / 31.7
16.4
14.0
16.0 13.3
AR 2.7:1
50.7
65.8
67.2 30.4
15.8
15.2
17.6 / 12.4
AR 6:1
47.5
71.1
74.5 27.1
12.2
17.9
19.0 9.6
AR 1:2.7
50.7
40.6
42.4 30.4
15.8
11.3
11.9 12.4
AR 1:6
47.5
17.5
18.2 27.1
12.2
3.2
3.5
Rotate 45
48.0
50.3
52.1
12.4
12.1
12.8 10.1
Worst case
47.5
17.5
18.2/27.1
12.2
3.2
3.5/9.6
Table 4: Certified accuracy (%) under patch rotation and different aspect ratio. We consider images
with Pe 2 0.95 be certified.
4.2 WITHOUT PATCH TRANSFORMATION
We first present the certification accuracy in Table 2 of our randomized cropping method along with De-randomized smoothing and PatchGuard on patch size ranging from 0.4% to 3%. Position encoding used here is learnable position encoding with values up 10% of normalized input value range. We mainly compare our results with two prior arts: De-randomized smoothing (DRS) (Levine & Feizi 2020) and PatchGuard (PG) (Xiang et al., 2020). For all PatchGuard results there two sets of numbers separated by slash: the first set of numbers use De-randomized smoothing &
Feizi 2020) as base structure and the second set of numbers use Bagnets (Brendel & Bethge (019)).
Methods with the highest certified accuracy are highlighted in bold. We can see that although our method is sub-optimal for CIFARIO, for ImageNet we have the highest certified accuracy except for patch size 0.4%. We also show the certification accuracy with different thresholds for Pe Table 3
As discussed in the previous subsection, our method is the fastest among the three methods. Al- though using Bagnets (PG- (PG-Bagnets) base structure makes PatchGuard much faster than using De-randomized smoothing (PG-DRS). it pays the price of degrading certified accuracy. For exam- ple, certification accuracy degrades from 58.1 % (PG-DRS) to 31.7% (PG- (PG-Bagnets) for CIFARIO with 2.4% patch size while our randomized cropping defense is as fast as PatchGuard with Bagnets (PG-Bagnets) show in Table (inference time remains the same with without patch transfor- mation). but achieves much better (52.3%) certified accuracy. Moreover, on ImageNet our proposed method is the fastest and with the highest certified accuracy well as clean accuracy.
Combining the certified accuracy on ImageNet in Table 2 and the short inference time Table I experiments show that the proposed randomized cropping defense is practical in the aspects of fast certification and high certified accuracy for the dataset that is closer to real-life pictures.
4.3 WITH PATCH TRANSFORMATION
As described Section a physically-realiahl patch can subject to certain transformations, such as scaling and rotation, before overwriting pixels in image. These transformations can be used to mimic relative camera angle and distance to the scene the real physical world. While reasonable restrict the maximal area that adversarial patch can influence in image (since corresponds to how big the physical patch is), one cannot assume such area would always align with coordinate axes of the image even if the physical patch itself is square, when the scene is

---

Under review as a conference paper at ICLR 2021
captured with different camera angles, the patch on the image will be rotated (rotation in x-y plane) or stretched (rotation in depth). Therefore it is important that the patch defense can also provide guarantees when the patch is rotated or if the aspect ratio is varied, given the same patch size.
In Table [ we compare the proposed randomized cropping defense with De-randomized smoothing Levinne & Feizi, 2020) and PatchGuard (Xiang al. 2020) when square patch is rotated 45 degrees and with aspect ratio (AR) 1:1, 6:1, 2.7:1, 1:2.7, 1:6, respectively. We highlight the highest certified accuracy under worst transformation for both datasets. Aspect ratio 1:1 without rotation is the same as Table 2 but listed here as reference. We chose 45 degrees because it is the worst case for a square patch, as the same number of pixels within the patch but occupying the largest rectangle area that aligns with coordinate axes of the image. Therefore rotation of 45 degrees provides a lower bound of robustness under patch rotation. For all transformations of the patch, we consider the same patch size.
We can clearly see that in T with the same patch size, transformation brings down the certified accuracy of all three competing methods, however, the proposed randomized cropping defense has the highest certified accuracy under worst-case patch transformation as listed the last row of Table This is because of our random sampling strategy that we have neither fixed the locations of sub- regions as in Bagnets, nor fixed smoothing strategy as in De-randomized smoothing.
On the other hand, the fixed smoooting strategy (ablating columns of images) in De- randomized smoothing (Levine & Feizi| 2020) which has the highest certifiable accuracy for square patches aligning coordinate axes of the imge suffers particularly because the patch gets shorter and longer (aspect ratio 1:3 and 1:6), the number of columns needed to ablate all the patch gets higher, and leaves fewer pixels of the image for classification. Also rotating the patch 45 degrees is equivalent to increasing the number of columns the patch occupies by 1.4 times, and hence signif- icantly reduces certified accuracy for column-smoothing strategy. While there are other smoothing techniques in De-randomized smoothing (block smoothing), similar effects can be expected as some aspect ratio or rotation degree will cause significant degradation of certified accuracy. Same level of degradation is also seen in PatchGuard with De-randomized smoothing base structure (numbers in PatchGuard column before slash symbol).
4.4 DISCUSSIONS
How to choose crop size? Assuming that the number of crops n is fixed, then in general larger crops leads to better clean performance, as each crop contains more information when it covers more pixel area. Also with larger crops, the crop classification accuracy of go would be better, indi- cating that Tettol in Eq. cooul be larger and increases the probability of certification Pe. However, larger crops also means that the probability of overlapping the adversarial patch is higher (Eq. 7 which will decrease Pe- Therefore, for a given size of adversarial patch, there exists an optimal crop size which maximizes the certification probability.
To demonstrate the influence of crop size on certification accuracy and clean accuracy, clean and certified accuracy with or without positional encoding, with regards to different crop sizes are shown in Figure 2 for 2.4% patch on CIFARIO and 2.0% patch on ImageNet we use square crops and square patches aligning with coordinate axes of the image, i.e., no patch transformation. Comparing clean accuracy with and without positional encoding, we can see that although clean accuracy still increases as crop size increases when crop classifier includes positional encoding, but not as much as without positional encoding. Such results show positional encoding does provide extra information for crops sampled from different locations. On the other hand, comparing clean accuracy with certified accuracy, it is clear that the certified accuracy actually gets lower when crop size crosses some threshold as discussed above.
Note that similar experiments as in Figure 2 can be conducted for different sizes of adversarial patches to find optimal crop size. However used fixed crop size in Table 2 to compare with DRS and PG to have a fair comparison, as these two approaches do not have tune-able abla- tion/kernel size.
How to choose number of crops? We show certified accuracy and inference time with different number of sampled crops for 2.4% patch on CIFARIO and 2.0% patch on ImageNet. Certified accuracy of using all crops, i.e., selecting crops all locations once without sampling, is plotted
8

---

Under review as a conference paper at ICLR 2021
90
dean acc with sos, encading
48
dean dean cortified with
clein atc. wud. pos, ancoding cart fied scc with pos. encoel
10 oxpaoiitttete
Figure 2: Clean and certified accuracy with different crop sizes. Left: CIFARIO with 2.4% patch. Right: ImageNet with 2.0% patch
100
16.-
Infonstee Urreina
36.0
25.5
15.6
curillierd with
cortfiedlac.
148
cort fictt on acEu fied
numbere
ramber
Figure 3: Certified accuracy and inference time(ms) with different number of sampled crops. Left: CIFARIO with 2.4% patch. Right: ImageNet with 2.0% patch
with the black dotted line as reference. This line can be viewed as the upper bound of the proposed method. With more crops sampled, the certified accuracy increases but however inference time also increases close to linearly. Therefore we chose relatively small number of crop samples to balance between inference time and certification accuracy.
5 CONCLUSION
This paper proposes a new architecture for defense against rhesically patch attacks. The proposed approach decomposes an image into random assortment of crops, each of which is pro- cessed by classifier, and the majority across the crops is used as the classification outcome for the input image. This approach provides a significant advance in the form of improved certified aceu- racy, while maintaining high clean accuracy when compared to prior art. We have shown that the proposed approach can be casily incorporated into standard training and test pipelines with minimal change to the underlying codebase. We believe this approach, by relying on simple effective architectural change, provides a compelling alternative to traditional defense strategies and, this sense, advances robust machine learning.
REFERENCES
Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give false sense of security: Cireumventing defenses to adversarial examples. arXiv preprint arXiv:1802.00420 2018.
Aharon Ben-Tal, Tal, Laurent El Ghaoui, and Arkadi Nemirovski. Robust optimization, volume 28. Princeton University Press, 2009.
Battista Biggio, Igino Corona, Davide Maiorca, Blaine Nelson, Nedim Šmdić, 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 databases, pp. 387-402. Springer, 2013.

---

Under review as a conference paper at ICLR 2021
Wieland Brendel and Matthias Bethge. Approximating enns with bag-of-local- leatuueeesss models works surprisingly well on imagenet. arXiv preprint arXiv:1904.00766 2019.
Tom B Brown, Dandelion Mané, Aurko Roy, Martín Abadi, and Justin Gilmer. Adversarial patch.
arXiv preprini 1112.0v771200963.. 2017.
Ping- Ping-Yeh Chiang, Renkun Ni, Ahmed Abdelkader, Chen Zhu, Christoph Studor, and Tom Goldstein. Certified defenses for adversarial patches, 2020.
Jeremy M Cohen, Elan Rosenfeld, and J. Zico Kolter. Certified adversarial robustness via random- ized smoothing, 2019.
Nilesh Dalvi, Pedro Domingos, Sumit Sanghai, Deepak Verma, et al. Adversarial classification. In Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 99-108, ACM, 2004.
Kevin Eykholt, Ivan Evtimov, Earlence Fernandes, Bo Li, Amir Rahmati, Chaowei Xiao, Atul Prakash, Tadayoshi Kohno, and Dawn Song. Robust physical-world attacks on deep learning visual classification. In 2018 IEEE/CVF Conference on Computer Vision and Pattern Recogni- fion. IEEE, jun 2018. doi: 10.1 10.1109/cv:::0118.0077
lan J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint arXiv:1412.6572, 2014.
Jamie Hayes. visible adversarial perturbations digital watermarking. Proceedings of the IEEE Conference Computer Vision and Pattern Recognition Workshops, pp. 1597-1604, 2018.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.
Alexey Kurakin, Ian Goodfellow, and Samy Bengio. Adversarial examples in the physical world. arXiv preprint arXiv:1607.02533, 2016a.
Alexey Kurakin, Ian Goodfellow, and Samy Bengio. Adversarial machine learning at scale, 2016b.
Alexander Levine and Soheil Feizi. Wasserstein smoothing: Certified robustness against wasserstein adversarial attacks, 2019.
Alexander Levine and Soheil Feizi. (de)randomized smoothing for certifiable defense against patch attacks, 2020.
Alcksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint 1xXiv:770600688: 2017.
Michael McCoyd, Won Park, Steven Chen, Neil Shah, Ryan Roggenkemper, Minjune Hwang, Ja- son Xinyu Liu, and David Wagner. Minority reports defense: Defending against adversarial patches. arXiv preprint arXiv:2004. 13799, 2020.
Seyed-Mohsen Moosavi-Dezfoolii Alhussein Fawzi, Omar Fawzi, and Pascal Frossard. Universal adversarial perturbations. 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Jul 2017. doi: 10.11099cvp:2211..17
Muzammal Naseer, Salman Khan, and Fatih Porikli. Local gradients smoothing: Defense against localized adversarial attacks. In 2019 IEEE Winter Conference on Applications of Computer Vision (WACV), pp. 1300-1307. IEEE, 2019.
Nicolas Papernot, Patrick McDaniel, Xi Wu, Somesh Jha, and Ananthram Swami. Distillation as defense to adversarial perturbations against deep neural networks. In 2016 IEEE Symposium on Security and Privacy (SP), pp. 582-597. IEEE, 2016.
Aditi Raghumathan, Jacob Steinhardt, and Percy Liang. Certified defenses against adversarial exam- ples, 2018.
10

---

Under review as a conference paper at ICLR 2021
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv:1409.1556 2014.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXtv:1312.6199 2013.
Florian Tramèr, Alexey Kurakin, Nicolas Papernot, Ian Goodfellow, Dan Boneh, and Patrick Mc- Daniel. Ensemble adversarial training: Attacks and defenses. arXiv preprint arXiv: 2017.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. 2017.
Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. arXiv preprint arXiv:1711.00851,00 2017.
Chong Xiang, Arjun Nitin Bhagoji, Vikash Sehwag. and Prateek Mittal. Patchguard: Prov- able defense against adversarial patches using masks on small receptive fields. arXiv preprint arXiv:2005. 10884, 2020.
Zhanyuan Zhang, Benson Yuan, Michael McCoyd, and David Wagner. Clipped bagnet: Defending against sticker attacks with clipped bag-of- offetuures. 2020.

---

Under review as a conference paper at ICLR 2021
A OVERVIEW OF DE-RANDOMIZED SMOOTHING (DRS) AND PATCHGUARD (PG)
De-randomized smoothing (Levine Feizi| 2020) ablates all possible parts of the image and aggre- gates logits of the ablated images for certification. The method compares number of ablated images with high logit value of the majority predicted class with the number of ablated images with high logit value of the second majority predicted class. If the difference between the two is larger than two times possible number of "ablation blocks" affected by adversarial patch, then this image is certified robust against patch attack. The paper proposes two modes of ablation: block smoothing and band smoothing. Block smoothing ablates square blocks while band smoothing ablates one col- umn of the image. To represent ablated regions, the image classifier accept three additional channels representing ablated pixels of the original RGB channels.
The main idea of PatchGuard (Xiang al. 2020) is to detect possible patch location and mask these locations for downstream robust classification. To detect patch location, the method identify class. If there does exist such
there are any local regions that contribute abnormally strongly region, it is considered as the potential location of a patch and the features extracted from the region masked/discardee. Because such robust masking procedure can be combined with other robust classification approaches, the paper evaluates its robust masking with two classification models: De-randomized smoothing (PG-DRS) and BagsNet (PG-BN).
B DETAILED CERTIFICATION PROCEDURE
We summarize the certification procedure for a single image in Algorithm 2 A more robust classifier should be able to certify and correctly classify higher percentage of clean images in the test set.
Algorithm 2: Certify if patch attack can change the predicted class of an image
Input: Full size image æ, label y. crop classifier ge for i / It.. do set E; as a kū x ki crop of x at random location; Øi -3) //Predicted class of crop E;
end
y', /" majority and second majority of {
71. 722 number of crops classified as y y", respectively;
if y A y then
return not certified
else
compute Pe using Eq. 6 if Pe is close to 1.0 then return certified, else return not certified
end
C UNIFORM SAMPLING WITHOUT REPLACEMENT
In this section we derive certification probability and experimental results with uniform sampling without replacement. Let nial be the number of all possible location for the 7t sampled crop, nads be the number of crop locations that overlaps with the adversarial patch, and pt, is the probability that the 7h crop overlaps with the adversarial patch, then
nadv min(p; + his m, k; + 1) min + K, 1, m.m,- - k2 + 1),
(7)
aull = (m, - K; + 1) x (m, - kg + 1) - i, and
(8)
Badu
P minn1
niul
The probability of the image being certified P. is then the probability of less than 722011 crops over- laps with the patch. The closed-form expression of p. is complicated yet not informative and hence omitted here. Comparing Pl with the p. in Section 3 we can see that when sampling without re- placement, the probability of sampling crop that overlaps with the adversarial patch increases with
12

---

Under review as a conference paper at ICLR 2021
CIFARIO 2.4%
ImageNet 2.0%
num. of crops
clean (R/NR)
certified (R/NR)
clean (R/NR)
certified (R/NR)
88.3/88.6
51.0/51.1
50.1/50.4
13.7/13.9
128
89.6/89.7
52.3/45.3
54.7/54.9
15.4/15.5
256
89.8/89.8
54.2/24.7
54.8/54.8
16.4/16.2
512
89.8/89.8
55.0/0.8
55.0/55.0
16.5/16.2
Table 5: Certified and clean accuracy (%) with (R) / without replacement (NR) over CIFARIO and ImageNet number of crops without patch transformation. Patch size is 2.4% for CIFARIO and 2.0% for ImageNet and crop size is 10x10 for CIFARIO and 80x80 for ImageNet. We consider images with Pa 2 0.95 to be certified.
CIFARIO 2.4%
ImageNet 2.0%
of crops
Vigtol interval/variance
Pe interval/variance
V2gsol interval/variance
Pe interval/variance
64
1.3/0.6
1.9/0.9
2. 2..
3.0/1.0
128
0.8/0.4
0.8/0.5
1.4/0.5
1.5/0.7
0.5/0.2
0.5/0.3
0.9/0.3
0.8/0.4
512
0.2/0.1
0.2/0.1
0.6/0.1
0.5/0.1
Table Averaged interval and variance of A2t1l and pe (in 10-2) vs number of crops without patch transformation. Patch size is 2.4% for CIFAR10 and 2.0% for ImageNet and crop size is 10x10 for CIFARIO and 80x80 for ImageNet.
the number of crops sampled, and hence decreases the probability of certification Pc- On the other hand, sampling without replacement enlarges the expected area that crops would cover, so the clean performance will be better than sampling with replacement.
We compare the certified and clean accuracy with and without replacement in Table 5 As number of crops increases, we can see that the gain of clean accuracy for sampling without replacement decreases because when number of crops increases, even sampling with replacement is likely to cover of the pixels, and the gain is slightly more significant in ImageNet than CIFAR10. This may be because ImageNet images are in general more complex than CIFARI 10 and having the crops covering more pixels over the image could help the overall classification. The certified accuracy for sampling without replacement gets worse than with replacement since the probability of sampling a crop increases more significantly as the number of crops sampled increases. This particularly true for CIFAR10 with image size 32x32 and patch size (0x10, the number of non-overlapping crops that does not overlap with the patch is only 484, out of 1024 all possible locations. This means when sampling 512 crops, there least 28 crops overlapping with the adversarial patch, which significantly decrease Pc-
D EXPERIMENTS ON Pe INTERVAL
In this section we show the interval of Ti2tol and Pe with different number of crops sampled. We run the certification process test 200 times to obtain the interval and variance of r2gsol and pe for each test image. Interval is defined as difference between the highest value and the lowest value. We ran this experiment over patch size 2.4% for CIFARIO and 2.0% for ImageNet.
As shown in Table 6 with increasing number of crops, both interval and variance of r2rol1 and Pe decrease, negligible values.
13


Reviews:
[{"review_id": "g74BP57QAVF", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors propose a surprisingly simple statistical defense, that can certify the robustness of a classifier against patch attacks. This is achieved by randomly sampling small rectangular subregions of the perturbed image and classify these samples individually. \n\nThe paper is mostly well written. Certification methods, able to handle patch attacks, are of significant interest in real world applications like autonomous driving. The paper is charming because of the simplicity. However, some questions remain unanswered and the experimental evaluation is not very thorough, hence this paper is borderline. \n\nQuestions:\n- Have the authors considered some kind of adversarial training? \n- As far as i understood the paper, the certification method is probabilistic due to the probabilistic intersection of sampled subregions with the adversarial patch. Could this be circumvented by defining a fixed set of subframes that get classified? Then the number of overlapping subregions could be calculated precisely in advance and the certification would not be probabilistic. \n- How does the right figure in Figure 2 look like? The current one seems to be the wrong one. \n- In Table 1, Table 2 and Table 3, the authors provide certification rates. Could the authors also provide how many images of the not certified ones can be successfully attacked?\n- When is $p_c$ as in Equation 6 considered to be close enough to 1, is it $0.95$ as in Section 4?\n- How do the certification rates change for larger/smaller adversarial patches?\n\nComments:\n- $C_i^N$ in Equation 6 should be defined. \n- A vertical line between the CIFAR10 and the ImageNet results in Table 2 & 3 would improve readability.\n\nI am willing to increase my score if my questions and concerns are addressed. \n\n-------------------\n\nAfter reading the authors response, i think that this work would benefit from an experimental comparison of their random method against a method relying on a deterministic crop selection, even if the certification rates of the deterministic method are inferior, because the certificates both methods are yielding are different: The resulting certificates from the deterministic method would be deterministic instead of probabilistic. Hence i will retain my score. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "fxO6iTYgR2", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The method can be basically summarized as a majority voting of crops of an image. Moreover, a new certification of the proposed method is introduced, not similar to the conventional adversarial robustness certification on perturbation under $\\ell_p$ ball , the method using simple geometry and probability problem to certify the results instead of any relaxation of the neural networks.\nHowever, the paper is poorly written, and many experimental setups are missing.\n\nUpdate after rebuttal:\nAfter reading the rebuttal, I don't think my questions are addressed very well, especially about the confidence probability, $p_c$. The certification is defined as a guaranteed yes/no problem but the $p_c$ will relax the certification to a probabilistic problem. Also, PatchGuard with patch transformation is out of scope for the original paper, so I think the experimental results in Section 4.1 and 4.2 are more like a fair comparison. However,  refer to the results in table 3, the proposed method yields worse performance than PG-DRS although the computational cost is saved. Hence, I will keep my rating.\n\nPros:\n\n+The proposed method is quite general and intuitive.\n\n+Using a simple geometry and probability model, the proposed method can certify the robustness of the adversarial patch attack in a very efficient way.\n\nCons:\n\n-What's the training time of the crop classifier $g$ compare with other baselines?\n\n-The whole system highly depends on the test accuracy of $g$. What's the result if no attack involved in?\n\n-From the experimental results, the proposed method has margin improvement compare with PG+DRS, and the basic idea of the certification algorithm also follows PG+DRS. So, the contribution is not enough for ICLR.\n\n-The hyperparameter $p_c$ is set as 0.95 in the experiment. However, the certification needs guaranteed results. So, if the $p_c = 0.95$, is that means there is a 5% possibility that this image can be attacked? Although this may not change the results so much, the ablation study of this parameter setting should be performed to make the comparison fairly.\n\n-Figure 2 (right) seems to use the wrong plot.", "extra_scores": {}, "extra_text": {}}, {"review_id": "a6Fvd-HxG4Z", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Update after the rebuttal:\n\nI read other reviews and response from the authors and I decided to keep my score. Overall, I think paper still needs more\nwork. For example, incorporating details on confidence into the main paper and not just a section in the appendix is quite\nimportant as otherwise the paper is misleading.\n\n==================================================\n\n-> Summary: \nIn this paper, authors propose a new certified defense against adversarial patches. They propose a model\nwhich samples different patches from the original image, performs classification of these patches using neural network classifier and performs a majority vote to compute the output label. The guarantee is obtained by computing a probability that none of the sampled patches intersect adversarial patch.\n\n-> Reasons for score:\n\nI vote for rejecting this paper. The main issue I have is that their probabilistic guarantees lack confidence intervals and \ntherefore it is not clear how meaningful they are. Further issue is that the method works better than prior work only if \ncertain image transformations are applied, such as rotation. Yet, this critical part is not described formally: what is rotated, entire image or just a patch? Same holds for aspect ratio. Due to these problems, I cannot recommend acceptance for this paper.\n\n-> Pros:\n\nI think explanations of the method are easy to follow and writing is solid, with some parts that require more clarifications.\n\n-> Cons:\n\nThe biggest problem I have with this paper is that authors do not consider confidence intervals for their guarantees. In particular, probability p_c computed in Equation 6 is tied to the particular n patches that were sampled which determines the value of n_{2to1}. This means that n_{2to1} is random variable and p_c that authors compute holds for just one sampled value of n_{2to1}. So for this bound to be useful, we need some form of confidence interval. For example, guarantee could be that with 99% probability p_c is interval [p_c_low, p_c_high]. And then, only if p_c_low is greater than some probability threshold (which is set to 95% in Section 4), we can report that this sample is certified. If I misunderstood something, it would be great if authors can clarify what kind of guarantee is provided.\n\nAdditionally, I find method used here relatively trivial and I think more technical contributions are necessary (e.g. computing confidence intervals above). In terms of empirical results, it seems that this method works better than prior work only in the case of additional image transformations and otherwise it performs worse or same. As this is the critical thing, I think authors should provide more explanations on how are these transformations applied, more formally instead of just describing it.\n\n\n-> Questions:\n\n- In Equation 6, summation is over i in the set {0, n_{2to1}}. Should this summation be over 0 <= i < n_{2to1} instead?\n- Can you clarify what is the difference between the experiments in Table 1 and Table 2? If I understand correctly, the experiments in Table 1 have additional transformation that is applied besides the adversarial patch? \n- Can you write mathematical formulation of transformations in Section 4.2? I am not sure whether these transformations are applied over the entire image or only over the patch, so it would be good to write more formally what exactly is the transformation.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "LMoxIS39q5k", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "### Summary\n\nThe paper proposes a robust neural network architecture to defend against\nadversarial patch attacks --where the attacker can freely modify a small patch\nof size $s_{patch}$ of the input images-- by training the net on random\ncrops of a pre-defined size $s_{crop}$ (in general $\\neq s_{patch}$), and, at\ntest time, use majority voting over several such random crops for every image.\nThey show that, as long as $s_{patch}$ is small ($\\leq 2.4\\%$ of total image),\nthese architectures achieve usual and **certified** robust accuracies that are\ncompetitive with the SOTA among the techniques and architectures that were\ntailored to certifiably defend against such attacks.\n\n\n### Overall evaluation\n\nThe defense is elegant for its simplicity and seems efficient, both in terms of\nperformance for small attack patches (which, arguably, is the most interesting\ncase), and in terms of computational speed/complexity (for small enough sample\nsize of crops). But the paper is still unclear, vague and/or too\napproximate in some parts (see points below). It seems to have been written in\na rush (Fig.2 on the right is obviously not the one intended) and some\nadditional experiments and/or discussions would be useful to complement the\nevaluation of the current method (see point 8. below). So, overall, I don't\nrecommend publication in the current state but am inclined to reconsider when I\nwill see appropriate changes in the paper.\n\n\n### Detailed remarks/questions\n\n1. Since you repeatedly refer to de-randomized smoothing and PatchGuard in the\n   text (and their combination), I suggest adding a short self-contained\n   description (in appendix with a reference) at the beginning (or in appendix\n   with a reference at the beginning) for the non-informed readers.\n2. I suggest to clearly mention that what is certified is the robust **test**\n   accuracy, not the distributional robust accuracy.\n3. I think that you are sampling the crops **uniformly** at random **with**\n   replacement, but I don't recall reading this explicitly in the text. Anyway,\n   it would be good to compare both approaches (with and without replacement),\n   at least in appendix.\n4. The description of Table 1 is in Sec.4.1 with title \"Without patch\n   transformation\", yet the caption says (and Table 2 confirms) that it shows\n   results **with** patch transformations. Which one is right? And if it's with\n   patch transformation, please add the same table for the setting without patch\n   transformation (at least to appendix).\n5. Eq. 6: capital $N$ in $C^N_i$ should be $n$.\n6. Please do an additional pass of proof-reading\n7. Sec 3.2: the description of how to compute the certifiable robustness bound\n   could be **significantly** improved and seems to be written in a big rush. In\n   particular, you never explicitly say which formula is used to compute the\n   robust bounds.\n8. _Crop size vs patch size_: The trade-off between crop size and attack patch\n   size is discussed in a rush at the end of the experiments (Sec. 4.2): it\n   deserves attention and an intuition explanation of the trade-off much earlier\n   in the paper, f.ex. when explaining the overall attack. Also, the paper could\n   benefit a lot from a finer analysis of the dependence of the optimal crop-size\n   on the attack's patch size (and probably on the typical size of \"relevant\n   information\" in the images). This could be either empirical (studying the\n   optimal crop-size as a function of the patch size) or more theoretical (with an\n   image model, or by using the average size of relevant objects in the image).\n   Also, it could shed more light on why your attack works better on ImageNet than\n   on CIFAR10 (probably because the typical size of the relevant parts of the\n   images are different in both datasets).\n9. _Sec. 3.1 §Training randomized cropping classifier_: the sentence \"the only\n   trainable part of the randomized cropping classifier is the crop\n   classifier\" deserves a proper Proposition/Theorem (with precise and explicit\n   hypotheses, s.a., f.ex. the assumption that crops are sampled **uniformly**\n   at random with replacement) and a proper, well-delimited proof. \n\n------------------------------------\n\nUpdate after rebuttal\n-----------------------------\n\nThe updated version is clearly better than the first one. However, the concerns\nof the other reviewers regarding the randomness of $p_c$ (and therefore of the\ncertification method) have convinced me that there are, indeed, some further\nclarifications and discussions needed prior to the publication, which is why I\nwill keep my initial recommendation.\n\nTo be more precise, the root issue here seems to be that the proposed\nclassifier is not deterministic, which means that the standard definitions of\nadversarial examples and adversarial accuracy do not apply and therefore, that\nthe problem that you try to solve is unclear and/or not well defined.  In\nparticular: what is it that gets certified?  what does it mean to get\ncertified? and, more generally, is the word \"certified\" really appropriate in\nthis context?\n\nHowever, whether an analysis of the distribution of $n_{2to1}$ and $p_c$ will\nbe needed (as asked by other reviewers) might depend on how the authors will\ndefine adversarial vulnerability in the random setting, and what they try to\ncertify. Let me explain what I mean.\n\nA reasonable start might be to define adversarial risk as\n$$\n    E_{(x,y)} E_{\\phi} \\mathcal{L}(\\phi(x), y) \\ ,  \\tag{1}\n$$\nwhich is the usual definition, but with an additional expectation over the\nvariability of the classifier $\\phi$.  Adversarial accuracy would then be the\nadversarial risk for the 0-1-loss $\\mathcal{L}_{0-1}$. Then the authors could, f.ex., set as goal\nto construct a (provably) unbiased estimate of this quantity.\n\nThe advantage of such a method is that one doesn't forget the fact that, what\nwe actually want to certify is this \"distributional\" robustness (i.e. where\nexpectation is taken over the true underlying, unknown distribution), not the\nrobustness on the test set. Even methods that have a non-random certification\nprocess (so-called \"provable robustness guarantees\") will never be able to\ncertify this quantity: they'll only deliver certificates on test example. The\n\"certified robustness on the test set\" that they yield is also just a random\nvariable which we hope \"generalizes to\" (1). Reviewers almost never ask authors\nto analyze/certify this generalization gap. Similarly, here, one could see the\nrandomness over $n_{2to1}$ and $p_c$ as just another source of randomness\ncontributing to the variability of the generalization gap, in which case, maybe\nno rigorous analysis could be acceptable, as long as it is clear what the\nauthors want to certify (unbiasedness of the estimator, f.ex.). Therefore,\nwhether this source of randomness could or should be explicitly captured/used\nby the authors' method is, I think, a question of how the authors frame the\nproblem and their goal.\n\n### Minor points:\n\n- even the revised version still contains quite a few grammatical errors,\n  especially in the new/re-worked sections, where many articles (\"the\", \"a\")\n  are missing.\n\n- End of p.5, \"to maximize number of certified robust images, the randomized\n  cropping classifier should maximize n2to1, which is equivalent to maximizing\n  classification accuracy of $g_\\theta$\": not sure about this equivalence.\n  Maximizing the classification accuracy is equivalent to maximizing n1, not\n  necessarily n1-n2.\n\n- are DRS and PG also probabilistic certifications (i.e. certifying robustness\n  with some probability, f.ex. pc>.95)? This should be clearly said in the text\n  and the captions, especially since it would make the comparison a bit unfair\n  if their certification were 100% sure. (This issue is obviously related to my\n  previous major remark on randomness.)\n\n- the name \"worst-case certified accuracy\" in the caption of Table 1 is very\n  unclear at that point. It becomes clear in Sec. 4.3, but you refer to Table 1\n  in Sec. 4.1 already. So this term should be clearly explained in the caption,\n  or there should be a clear reference to the relevant part in the text.\n\n- don't always re-cite Levine&Feizi and Xiang et al. every time you mention\n  de-randomized smoothing and patch guard. Cite them the first time, and then\n  say that you'll refer to de-randomized smoothing and patch guard as DRS and\n  PG in the rest of the text.\n\n- in the conclusion: \"This paper proposes a new architecture for defense\n  against\" -> \"This paper proposes a new defense against\". (You are not really\n  proposing a new architecture.)", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper provides a simple prediction procedure to defend against (rectangular) patch attacks, and also a method to obtain some random estimates of the certified robustness of the method. The simplicity of the method is certainly appreciated. On the other hand, there are a number of issues preventing the acceptance of this paper. The main problem is that the paper deals with a randomized predictor, yet the certification guarantee developed for deterministic predictors is applied. This leads to several problems, starting from the target being undefined to unfair comparisons. While the authors made an attempt to address this in the rebuttal, more work is needed to properly settle this issue.
Decision: Reject