Revisiting Image Classifier Training for Improved Certified Robust Defense against Adversarial Patches
Authors: Aniruddha Saha
Shuhua Yu
Mohammad Sadegh Norouzzadeh
Wan-Yi Lin
Chaithanya Kumar Mummadi
Venue: Accepted by TMLR ()

Abstract: Certifiably robust defenses against adversarial patches for image classifiers ensure correct prediction against any changes to a constrained neighborhood of pixels. PatchCleanser, the state-of-the-art certified defense, uses a double-masking strategy for robust classification. The success of this strategy relies heavily on the model's invariance to image pixel masking. In this paper, we take a closer look at model training schemes to improve this invariance. Instead of using Random Cutout augmentations like PatchCleanser, we introduce the notion of worst-case masking, i.e., selecting masked images which maximize classification loss. However, finding worst-case masks requires an exhaustive search, which might be prohibitively expensive to do on-the-fly during training. To solve this problem, we propose a two-round greedy masking strategy (Greedy Cutout) which finds an approximate worst-case mask location with much less compute. We show that the models trained with our Greedy Cutout improves certified robust accuracy over Random Cutout in PatchCleanser across a range of datasets and architectures. Certified robust accuracy on ImageNet with a ViT-B16-224 model increases from 58.1% to 62.3% against a 3% square patch applied anywhere on the image.

Published in Transactions on Machine Learning Research (10/2023)
Revisiting Image Classifier Training for Improved Certified Robust Defense against Adversarial Patches
Aniruddha Saha'
anisaha @umd edu
University of Moryland, College Park
Shuhua Yu
shaubuay&@endrew.com www.eewwwwww...c...mm.mm.....
Carnegie Mellon University
Mohammad Sadegh Norouzzadeh Bosch Center for AI
amahh.norouzzadehh.ee @us. www.h.s..bb............. com
Wan-Ya Yi Lin Bosch Cender for AI
wan-yyi.linouus wtw.::iwwn.uubbbc.....o
Chaithanya Kumar Mummadi
cuciilaonykkmmar...mmmniieee www.::/wwww..eeee.eeeea.ooooooo. bosch. com
Bosch Center for Al
Reviewed on OpenReview: https: // openreview. net/ forum? id= 2tchhgg333
Abstract
Certifiably robust defenses against adversarial patches for image classifiers ensure correct prediction against any changes to a constrained neighborhood of pixels. PatchCleanser Xi- ang et al. (2022), the state-of-the-art certified defense, uses a double-masking strategy robust classification. The success of this strategy relies heavily on the model's invariance to image pixel masking. In this paper, take closer look at model training schemes to improve this invariance. Instead of using Random Cutout DeVries & Taylor (017) augmen- tations like PatchCleanser, we introduce the notion of worst-case masking, i.e., selecting masked images which maximize classification loss. However, finding worst-case masks re- quires an exhaustive search, which might be prohibitively expensive to do on-the-fly during training. To solve this problem, we propose a two-round greedy masking strategy (Greedy Cutout) which finds an approximate worst-case mask location with much less compute. We show that the models trained with our Greedy Cutout improves certified robust accuracy over Random Cutout in PatchCleanser across range of datasets and architectures. Certi- fied robust accuracy on ImageNet with a ViT-B16-224 model increases from 58.1% to 62.3% against 3% square patch applied anywhere on the image.
1 Introduction
Deep learning based image classifiers are vulnerable to adversarial patches applied the input Brown el al. (2017ss Eykholt et al. (2018), where image pixels bounded within confined connected region, usually square circular, be adversarially crafted to induce misclassification. Patch attacks formulated in this way to mimic printing and placing adversarial object in the scene. It is easier to realize patch attack in the physical world compared to full image adversarial perturbation, as the latter might need compromise in the compute system. Therefore, adversarial patch attacks pose significant threat to real-world computer vision systems.
'Equal contribution. Work done during internship at Bosch Center AT, Pittsburgh.

---

Published in Transactions on Machine Learning Research (10/2023)
PatchCleanser Certification with
PatchCleaneer Gertiffcation:
Image cectified
87.5
Cready Quteut [ouns]
images imsgees) correctly dasatiied.
Mask occludes entire object
image Mask
masks
Contined Rubust
06.0
57.7
Mask occludes abject partially
52.9
52.5
1"sat two monleed imsqee
9 tww--makked imagoos
CHAM-10
CWAN-100
SVHK
ImageNe:
(a)
(b)
(c)
Figure 1: Better invariance to pixel masking improves certified robustness to adversarial patches (a) An illustration of PatchCleanser Xiang al. (2022) double masking strategy. (b) Images are hard to classify when masks occlude objects of interest. Top row: Certification ion is not possible when mask completely occludes the object. Bottom row: Random Cutout failed to enable certification in cases of partial occlusion, whereas our Greedy Culout succeeds. (c) Greedy Cutout improves PatchCleanser certification by a large margin. Certified robust accuracy on ImageNet with a ViT-B16- 224 model increases from 52.5% to 57.7% against 3% square patch 39 x 39) applied anywhere on the image with M3x3-
Defenses against patch attacks fall into two categories: empirical and certified defense. Empirical defenses Rao et al. (2020); Hayes (2018); Mu & Wagner (2021) often utilize robust training which incorporates ad- versarial inputs generated from specific attacks to improve robustness. But they susceptible atlacks unseen during training. On the other hand, certified defenses guarantee correct predictions against any adaptive white-box attacker under given threat model. Hence, the certified robust accuracy is the guar- anteed lower bound of the model performance. Prior works Levine & Feizi (2020); Lin et al. (2021); Metzen & Yatsura 2021 Xiang et al. (2022) acknowledge this strong robustness property of certified defense and propose different certification procedures to improve the certified robustness. Note that, we consider a single adversarial square patch applied on an image in our threat model in this work.
PatchCleanser Xiang al. (2022) is the state-of-the-art certified defense method against patch attacks. Similar to other certified methods, it assumes the defense has a conservative estimate of the patch size (e.g. 3% pixels) and thereby designs mask set masks with cerlain size placed al reserved spatial locations on image. Fig [[a][[oow shows mask set M3x3 of 9 masks, each with size 100 100, that are applied on 224x 224 image. This mask set is designed to ensure that an adversarial patch of an estimated size (c.g. 3% pixels 39 x 39 patch) will covered and therefore neutralized by at least one of the masks. The method proposes two-round pixel masking defense and certifies an image if predictions of all its double-masked images agree with the ground truth. An image is certified if all the two-masked g2 81 combinations get correctly classified. More details about this method can be found in Sec 3.3
PltchCleanser shows that a classifier trained on two-masked (or double-masked) images using random Cutout DeVries & Taylor (2017) augmentation improves certification accuracy. At training time, a two-masked image is obtained by applying random Cutout twice on a clean image (see Fig 4.. During certification, we observe that some of the two-masked images are hard to classify as the masks completely occlude the object interest beyond recognition as shown in Fig 1ib] (top row). not possible to certify such images with the considered mask set. Besides, we made a visual observation that random Culout trained classifiers even misclassify two-masked images with preserved semantic clues, see bottom row of Fig [(b) Misclassification such images result in underestinating classificr's certified robustness. We consider that random Cutout augmentation is not fully effective or invariant towards pixel masking and limits classifier potential to leverage the defense. This observation motivates our work to explore the training schemes that improve invariance to pixel masking and thereby enhance classifer's certified robustness through PatchCleanser.
We revisit image classifier training strategy to particularly target the classifier's failure modes during Patch- Cleanser certification. The masks of misclassified images during certification would serve possible worst-
2

---

Published in Transactions on Machine Learning Research (10/2023)
case masks i.c. masks that induce image misclassification. Instead of Random Cutout augmentation, we propose to choose worst-case masked images with high classification loss for training. The worst-case masks are chosen from the mask set that are used during certification. Finding such wonst-case masks from mask set Max3 and M6x6 exhanstively requires x 9 = 81 and 36 x 36 = 1296 two-mask forward passes respec- tively, which is prohibitively expensive to do on-the-fly during training. To this end, we propose a simple but effective greedy masking strategy called Greedy Cutout to approximate the worst-case masks with 42% and 96% less computation overhead than the grid search on M3 a and M6x respectively. We propose to train the image classifiers the Greedy Cutout images and demonstrate that such masking strategy improves certified robustness across different datasets as shown in Fig [(c)
We summarize our contributions as follows: We observe that training the classifier with standard Cutout augmentation is not entirely effective for all two-masked images. Therefore, we take a closer look at the invariance of image classifiers to pixel masking with an objective to improve PatchCleanse certification. We propose a simple Greedy Cutout strategy to train the classifier with worst-case masked images. We compare with various other masking strategies like Random Cutout. DeVries & Taylor (2017), Culout guided by certification masks, Gutout (Cutout guided by Grad-CAM) Choi et al. (2020). Cutout with exhaustive scarch (refer Sec. 4 and show that our training strategy improves certified robustness over other basclines across different datasets and architectures.
2 Related Work
Certified defenses against patch attack: Certified defenses against adversarial patch for image classi- fiers provide guaranteed robust accuracy lower bound. Because patch attack has maximum strength within
the patch region, certified defenses either ensembles from local regions Levine & Feizi (2020); Salman et al.
20022
: Lin et al. 2021 use models with small receptive field and masking Metzen & Yalsura (2021 p5 Xiang
et al. 2021 to reduce global influence of the patches. Curent state-of-ther of-the-art PatchCleanser Xiang et al.
(2022) combines masking and ensembling by aggregating predictions of specifically-dessined masked copies and shows significant improvement over previous mothods. Our work follows the certification and inference procedure of PatchCleanser Xiang et al. (2022). However, we show that worst-case mask augmentation can improve invariance to pixel masking and consequently the certified robust accuracy of PatchCleanser.
Augmentation for adversarial robustness: Data augmentations help in training smooth and general- izable models, and are used to train adversarially-robustt classifiers. Adversarial training Madry et al. (2018). Niu et al. (2022) which augments input with gradient given a model has been established as one of the most powerful approach for training robust models. Studies have also shown that adversarial training improves generalizability of models Yi et al. (2021): : Mao et al. (2022). Gradient-free augmentation has shown im- provements in model robustness: Gooal al. [2021) b utilizes unconditional generative models to generate additional training dataset, and Li & Spratling (2023) proposed padding before cropping (PadCrop) for augmentation to reduce robust overlitting. Culout DeVries & Taylor (2017), randomly masks out square regions of input images during training to improve clean accuracy. We propose a variation to random Cutout augmentation scheme in our paper to improve certified robustness.
training/Madry
3
Method
3.1
Patch attack formulation
This paper focuses on adversarially-rooust image classification. We use X [0, WXHXC to denote an image, where each image has width W, height H, number of channels C, and pixel values in [0, 1]. We use y to denote the label set, and F: X + y denotes the image classification model. Note that we do not make any assumptions about the network architecture, and thus we present model-agnostic method.
We consider patch attack, denoted by A, that can arbitrarily manipulate the pixels within a square region covering up to 3% of image area. We use e (0, 1) WxH to denote a binary mask with the aforementioned square region, where pixels within the square region is set while others are set to Since the region can be placed in any location of an image, we denote all such square regions covering less than 3% of an image
3

---

Published in Transactions on Machine Learning Research (10/2023)
R. Formally, for image with true label y, the patch attack A can generate set of images under attack, i.e., (x) = (r (1-r) x' e X,r R), where the attack aims to find an image & e Ax) such that F(&) # y. Here, @ represents pixel-wise multiplication.
3.2 Defense objectives
The goal of certifiable defense is to build a robust model F such that for a given image label pair (x, y), we have V& E (x(x),F(()) = y, then x is termed as a certified image and the fraction of certified images in the test data is defined as certified robust accuracy. We consider the process to determinc whether an image-label pair y) can be certified follows PatchCleanser Xiang et al. (2022). Certified robust accuracy provides lower bound on model's classification accuracy under patch attack. On the other hand, we want to avoid deteriorated performance over clean data free of patch attacks. Therefore, the other metric we wish to maintain is the fraction of image label pair (x. satisfying F(x) = y over test data, which we refer it as clean accuracy. Computing clean accuracy requires inference process sweeping over the test data.
3.3 Background on PatchCleanser
In this work, we follow the inference and certification procodures of PatchCleanser Xiang et al. (2022) PatchCleanser achieves certified defense via guuble-makking strategy. A mask m E {0. 1, w is defined as a binary image with the same dimension as images X where pixels within the mask take value 0, and the rest take value 1, and thus masked image x m will exhibit an artificially occluded region within the mask while other pixels remains unaffected. PatchCleanser crafts a well-designed set of masks M and provides a provable certification procure based on predicted classes over the set of masked images {x O m m E M).
PatchCleanser designs the mask set M satisfying R-covering property, that is, for any adversarial patch, there exists at least one mask m E M that would completely cover the adversarial patch. Formally, Vr E R, e M, s.t. m(i. jl S rli, j]. j. PatchCleanser proves that an image label pair (x.y) E X x y satisfies that Vm1, ma M X M, F(x O mı O m2) = y, then yx cortified. Therefore, improving the cortified robust accuracy reduces maintain high classification accuracy for FF on masked images x0m; 0m2, mi, m2 E MxM. To this end, PatchCleanser employs Cutout data augmentation DeVries & Taylor 2017) to finetune model F.
For inference, PatchCleanser first obtains all one-mask predictions F(x O m), Vm E M. If the image x has no adversarial patch, then all one-mask predictions should be the same as F(x), in this case it outputs the agreed prediction as the predicted class for x. If x contains an adversarial patch that induces misclassification. and one of the masks m E M completely cover or occlude the adversarial patch, then at least one prediction should be different from the rest. For each disagreed (minority) single-masked image prediction, the masked image is proceeded to second-round masking with the same mask set M and all the two-masked images are classified with F. If the sinle-masked image has fully occluded the adversarial patch, then all its two-masked images also fully occlude the adversarial patch, yielding unanimous predictions from the wwo-masked images as the final output of Fxx). If none or more than one disagroed case have unanimous two-masked predictions, then none of the classes should be trusted, and the majority predicted class of the single-masker images is the final prediction of x. Example masked copies can be found in Figure [[a] PatchCleanser shows that if an image-label pair (x, y) is certified, the above inference procedure will always output the correct label y.
3.4 Description of our method Greedy Cutout
Recall that the classifier F should be fine-tuned to double-masked images {x my m2 m. m2 E M M) so that it is less sensitive to presence of m E M. For this purpose, we resort to augmented training data with (x',y) where x' is obtain from applying masks or combination of masks on x. PatchCleanser uses Random Cutout augmentation DeVries & Taylor (207)), i.e., applying two masks of size 128x 128 al random locations to 224 x 224 training images (see Fig. 4.. In this work, we develop a systematic approach to find x' that are more empirically effective. The main strategy is to use several inference rounds to identify worst-case masks that lead to highest losses, then we apply these worst-case masks x to obtain augmented data point (x' for training the model.
4

---

Published in Transactions on Machine Learning Research (10/2023)
Greedy Cutout- Round
Greedy Cutout Round 2
Mask sets:
image with highest tlassfication
image with highest classification
Mass
Mos
Apply mask
Apply
M
Myx
Clean image
One-maskke image
Two-masked image M2
Mask set 3x3
Mask 6x6
One-masked images
Two-masked images
Figure Illustration of two-round Greedy Cutout masking Each round applies masks from the same mask set M& x = 3 or 6), making the number of forward passes for both rounds (9 x9x2) 2) and (36x2)-1== 71 when k = 3 and 6 respectively, to find the masked image with highest classification loss.
The two-masked image M2 obtained from Round 2 is used for training the classifier.
Sulti-Size Greedy Cutout Round 1
Multi-Size Greedy Cutout - Round 2
image with highest loss
One-maskked image M1
image highest loss
Two-masked image M2
Apply mask Mas
Clean image
Apply mask
from Mans
Apply mask
Ma-6
Apply
1 Mays
image with highest loss
mask
Image with highest loss
One-masked Image M11
Two-masked image M22
Maxx -Mask set 3x3
mask set 6x6
Figure 3: Illustration of our multi-size two-round Greedy Cutout masking Each round begins with applying larger masks from M3x3 3 with 9 forward passes, which narrow downs the search area for the smaller masks from M6x to just 4 forward passes. With a total of unique forward passes, the approximated worst-case masked images M2 and M22 from Max3 x and Mg 6 are jointly used for training.
Image and mask preparations: For datasets of high-resolution images such as ImogeNet and ImageNette, resize and crop them to 224 x 224 before feeding them into model F. For datascts with images with low- resolution such CIFAR-10, performance. In this work, we generate sets of masks following PatchCleanso/Xingg et al. (2022). Concretely, we use two mask sets Max3 and M6x6 (see the leftmost part of Figure for an illustration, where light gray blocks represent image area and deep gray smaller blocks represent masks) that both satisfy R-covering property: M3x3 set of x masks with masks total, and each mask of size 100 100; M is set of 6 masks with 36 masks, and every mask is in shape of 69
resize them to 224x224 via bicubic interpolation for better classification
Note that, due to the careful choice of Maxa and Maxe, each mask Maxa can be fully covered by 4 masks in M,x6- Empirically, Maxe leads to higher certified robust accuracy since two smaller masks have smaller effect on the prediction F than the larger ones. However, Maxe has x 8 times larger size than Maxa that requires more computation in both inference and certification. Striking a delicate trade-off bet computational cost and accuracy is the core our method.
Greedy Cutout:
We present baseline version of Greedy Cutout (Sec Figure for an illustration). We first define the prediction loss of on image label pair (x. y). Suppose within the model of for each label y' y the coniidence level for I to predict y' is pyt, then the eross entropy loss ((F(x, y)) -Eyey y Cy' log Py
5

---

Published in Transactions on Machine Learning Research (10/2023)
where Cyr = 1 for y' = otherwise Cy. -. For mask set Mxx = or k == 6), could identify the worst- case mask combination m1, m2 E M&xx x MAxK that incurs the largest. loss ((FF(x @ mi O m2, y) with grid search, but inferencing over all (55) + k² (45 when k =33, and 666 when k = 6) unique combinations would be computationally prohibitive, thus motivating the Greedy Culoul strategy.
By Greedy Cutout, we find the worst-case mask in each individual masking round. In the first round, for each mj E Maxk, we compute the loss ((F(x y), and denote the mask incurring the highest loss as mi. Then, in the second round, for each ma E MAxx, m2 # mi, we compute the loss ((F(x m mm))),)) y), and find the m² with the highest loss. Then, we empirically use M2 == m; O my as the worst-case mask combination. Although M2 may not be the exact worst-case mask, (x M2.y) y) still provides a guidance for fine-tuning, More importantly, with Greedy Cutout, we significantly reduce the inference burden down to 2k² (17 when k = 3; and 71 when k = 6) compared to grid search. However, for == 6, this computation cost is still high but this mask set has better accuracy over Max3. We then further develop Multi-size Greedy Cutout (See Fig 3 that benefits from the high accuracy of M6x6 while keeping computation cost comparable with Greedy Cutout with M3x3.
Multi-size Greedy Cutout: Similar to the above method, this variant also involves two rounds.
Round 1 Given clean image x, we first apply each mask in Max3 and inference on each image in {x o m Maxa]- We then find the mask that incurs highest loss ((F(x O m). y), and denote this mask as M Then, we find the collection of 4 masks in Maxe that fully covers M1. We apply the previous 4 masks from Maxe on clean image x and inference each masked image, then we store the mask incurs highest loss among the four, denote this mask as M11-
We apply each m E Max3 on x O M11, and find the my that incurs largest highest loss among the masks. Then we output our first mask M₃ = M1 O my. For mj, we identify the 4 masks from M6x6 that fully covers my. and apply the masks on x M11 to find my that incurs highest loss. We output the second mask M22 M11 @ m
Round 2
From the previous two rounds, we identify two worst-case masks M2 and M22. We only use in total 9+4 = 13 inferences in each round so only 26 inferences in total. In our experiments, we show that this strategy uses similar amount of computation with baseline Greedy Culoul for k = 3, but achieves comparable performance of baseline Greedy Cutout for k = 6. We provide the pseudocode in the Algorithm | in the appendix, where two procedures ROUND-1 and ROUND-2 echo the round and round described above. Running Algorithm with input (x, F, Max3. Moxe) will lead to desired augmented data points (x,,)) and (xg.y) that can be used for fine-tuning the vanilla model F.
4 Experiments
In this section, we describe our experimental setup, masking strategies and present the results. We use five popular image classification datasets: ImageNet DDengnggeDDnnee et al. (2009). ImageNette Howard et al. (0020) CIFAR- 10 Krizhevsky et al. (2009), CIFAR-100 Krizhevsky et al. (2009) , SVHN Netzer et al. (2011) and image
classifiers from three different architecture families: ResNet He et al. (2016). ViT Dosovitskiy et al. (0020).
ConvNeXt Liu et al. (2022). In particular, Ves55l2 V2,50x1, VIT-B16-224 and ConvNeXt tiny in22ft
pretrained models from timm library Wightman (2019). . We finctune these pretrained models on different
datasets using the proposed masking strategies for 10 epochs with SGD optimizer
learning rate 0.01 for ResNet and 0.001 for ViT, ConvNeXt and reduce the learning rate by factor of 10 after 5 epochs. Images from all the datasets are resized to 224 x 224. We use batch size 128 for ImageNet and 64 for other datasets.
Adversarial patches: As in prior work Xiang et al. (002)); Chiang et al. (2019): Levine & Feizi (022)): Metzen & Yatsura (2021); Xiang et al. 2001)) we report certified defense accuracy for square patches covering 1%, 2% and 3% of the input image for ImageNet, ImagNette and 0.4%, 2.4% for CIFAR-10, CIFAR-100, and SVHN. We allow patch perturbations to be unbounded (within image range) and consider a single square
patch placed at any random location in the image.
6

---

Published in Transactions on Machine Learning Research (10/2023)
PatchCleanser: Cutout masking
Random (Rand) masking
Sample two random pixel locations the image apply masks with the pixel locations as their centres.
Sample two mask locations randomly from the mask M Ma and apply them the image.
Two random pixel locations
Gutout: Cutout with Grad-CAM
Grid search: Cutout with exhaustive search
Cover the sulient region mask
Salient region
Cover the salient region
Select two-masked image among all the two-mask (e.g. 9x9=81 Maaa) having highest
Grad-CAM
Salient region from Grad CAM
May
Mask Maia
Label Welsh
Springer Spaniel
two-masked images
two-masked Images
Mgn
Moso
(c)
(d)
Figure 4: Illustraiion of different masking stratogics We explore various strategics to improve the invariance of models towards pixel masking.
Evaluation metrics: We report two metrics: clean accuracy amount of clean test images classified correctly by the PatchCleanser defense and certified robust accuracy amount test images pass through certification process i.c. a guaranteed lower bound on classifier robustness.
4.1 Improving invariance to pixel masking
The core idea of PatchCleanse:
et al. (2022) is to mask image pixels to occlude and neutralize the adversarial patch. We visually observe that two masks that completely occlude the object make images harder to certify (see Fig. [(b]. However, masked images with partial occlusions and preserved semantic cues stand a chance to get classified correctly. Hence, a crucial property that governs the success of certification is the classifier's prediction invariance to pizel masking. Below we explain different train time masking strategies that we investigate towards improving pixel masking invariance.
4.1.1 Random Cutout in PatchCleanser (PC-Cutout)
Random Ceviie & Taylor 2017 to apply 2 masks of size 128x 128 at random locations on a 224x224 image during training (sce Fig. Here, masks may be located partially beyond the image boundary. is shown that the such Cutout augmentation improves certification over vanilla classifiers. We hypot that such Cutout strategy might not be fully effective induce mask invariance and propose further improvement.
4.1.2 Random Cutout with certification masks
We investigate whether choosing random masks from certification mask sets, M3 x or M6 (Section 3.4 improve certified robustness. randy 3 strategy chooses the masks exclusively from M3 3. whereas rands strategy chooses them from Mg x.. Moreover, we also employ the rand strategy where masks are randomly sampled from hir of the sets M3x3 Mg x during training (see Fig.

---

Published in Transactions on Machine Learning Research (10/2023)
Table 1: Clean and certified robust accuracy comparison WW show the results of selected prior work in the top group of rows. Then we compare the performance of PatchCleanser(PCC Random Cutout with certification masks (Section 4.1.2) and Multi-size (MS) Greedy Cutout (Section 4.1.5
(Section 4.1.1
We use three classifiers (ResNet, VIT, ConyNeXt), three datasets (ImageNette, ImageNet, CIFAR-10) and adversarial patch sizes in the range of 1% 3% of image size. Underlined mumbers represent highest robust accuracy obtained for a specific architecture, and bold numbers represent highest robust accuracy obtained
across different archilectures.
Dutoses
LungeNetic
CIFAR-10
Patch
1% pozels
25 pizula
5% ponels
1% pisull nohroet
2%
pixelx robust
3% pioele
pizell
2.4%
piodle
Ancurary (%)
clean
ralust
cleon
robrast
clesn
robust
clron
clean
clran
mohwort
clean
rubuse
elean
welreet
Chiong
2010
65.8
51.9
47.8
30.8
13.4
7:1
D6 Loyan & Fei
92.1
62.3
92.1
79.1
92.1
75.7
44.4
17.7
44.4
14.0
44.4
11.2
53.9
68.5
83.3
66.2
PC-EN Xohin
2791
95.2
$9.0
85.0
86.7
94.8
83.0
55.1
32.3
54.6
25.0
54.1
19.7
54.5
63.8
83.9
47.3
67.7
Bog
20233
27.8
22.7
45.3
95.0
00.0
VIT--
StLman ct
3022
73.2
43.0
73.2
38.2
78.2
38.1
90.8
75
90..5
67.6
Certification with
RexNet
PC-Criott Xixng mt ml
2919
96.3
91.0
99.4
92.8
98.9
91.6
80.9
52.3
80.9
05.7
60.5
45.8
97.33
61.3
966.
73.0
Rand Ostont with
98.1
94.2
99.2
92.5
98.2
91.3
81.2
51.2
81.2
47.1
61.0
45.1
97..5
80
96.8
71.0
MS Gredy
52.6
VITT
PCSCatont Kiang
90.4
85.1
94.0
58.5
53.2
51.5
98.0
09800
K3.5
Band Catoul with morks
96.5
95.4
94.7
07.2
62.7
54.5
52.7
98.6
89.0
S8.1
MS Chedyy Cutous (Duis)
90.4
96.0
99.4
96.0
99.4
96.5
91.2
30.5
61.2
68.7
91.1
57.7
98.5
91.6
99.
97.5
ConvNcXi
PC-Catous XIsng et
96.6
98.1
99.5
95.1
99.3
94.4
68.8
52.5
81.6
49.8
97.9
85.0
97.4
77.9
Rand Calout with CIST. musks
90.4
95.8
90.4
94.9
99.3
94.5
81.7
66.2
61.7
51.7
81.6
49.2
97.8
94.6
97.8
70.0
MS Gredy Cutoutt (Ours)
98.5
96.5
99.4
95.9
9
95.4
80.5
58.1
80.4
56.0
60.2
55.8
97.7
88.5
97.4
63.7
Certitication with Ma
ResNer
PC-Cuton Xiang et 2022 Rand Ostont with Groedy (Outs)
96.7
96.6
99.6
00.2
99.4
93.9
91.3
38.2
81.22
54.3
81.1
50.9
97.7
96.1
97.55
77.8
05.0
93.8
58.6
53.1
50.3
97.99
07.66
77.1
27.6
00.4
99.4
35.6
03.0
58.2
90.8
50.0
97.77
20.5
97.5
84.3
VIT
PC.Cutou Xinng
97.9
97.0
96.6
61.2
68.1
98.5
87.9
Rand Oatont with CIEs. mudks
98.8
97.9
96.9
99.7
64.00
83.4
60.5
65.5
58.5
96.9
98.7
58.4
MS Groody Cutout (Ours)
90.6
98.5
90.6
97..9
99.6
97.8
82.0
65.0
82.0
03.11
82.0
62.5
95.0
95.8
98.8
92.0
NonvNeXi
PC-Crtoon Kisng et 2019
99.8
1
89.5
87.3
99.7
96.5
82.1
63.1
58.3
35.0
98.9
98.0
83.8
Rand Oatont with Cies.
99.7
06.2
99.5
96.9
98.8
96.4
62.5
62.7
62.3
57.1
62.2
54.5
96.3
90.5
96.2
81.9
MS Gready Uutout (Durs)
90.7
87.9
97.44
06.5
61.8
58.4
98.1
07.8
87.3
4.1.3 Gutout Cutout guided by Grad-CAM
Instead of Random Cutout, we examine the effectiveness of classifier training on saliency guided Cutout. We use image explanation heatmaps from literature to guide this process. Specifically, use Grad-CAM Selvaraju et al. (207)) to find the most salient region of the image and selectively mask out the region using certification mask sets M3 M6 in two-round fashion (see Fig. 4 for illustration). We refer the masking strategics as gutouts x3, gutoute x and gutout when training on the mask sets M3 M6 and both the mask sets. Such augmentation strategy was proposed in Choi et al. (2020) and we take inspiration from their implementation.
4.1.4 Cutout guided by exhaustive search
Cutout masks have edges which introduce sharp transitions from grayscale mask color to natural image color. These transitions often happen over the object of interest and thus introduce artifacts which might make the lcarning problem harder. We believe that the two-masked images obtained from the saliency guided Culout may not serve as the best training examples for the classifier to improve pixel masking invariance. To this end, we sweep through the entire search area by evaluating classifier performance on all possible two-masked image combinations from mask sets M3 x or M,x6 and find the worst-case masks that result in highest classification loss. We train classifiers on the worst-case masked images and refer this masking strategy as grids x and gridg x with with masks set M5x3 Mg 6 respectively. We believe that this
8

---

Published in Transactions on Machine Learning Research (10/2023)
Table 2: Results on additional datasets Clean and robust accuracy on CIFAR-100 and SVHN.
Dataset
CIFAR-100 100
SVHN
Patch size
2.4% pixels
2.4% pixela
Accuracy (%)
clean
robust
clean
robust
Certification with mask set My x
ResNet
PC-Cutout Xiang 2002
45.9
93.8
43.4
Multi size Greedy Cutout (Ours)
85.8
53.9
93.4
54.5
VIT
PC-Cutout
Xiang 2022
91.4
61.5
95.9
52.9
Multi size Greedy Cutout (Oure)
66.0
95.8
63.3
Certification with mask set Ma
ResNet
PC-Cutout Xiang et al.
2022
87.6
52.6
95.2
55.5
Multi size Greedy Cutout (Ours)
86.7
61.0
95.3
67.5
VIT
PC. Cutoot
Xiang et al. 2022
92.4
69.1
97.2
67.5
Multi size Greedy Cutout (Ours)
92.1
74.5
97.1
76.8
approach close to an upper bound on the best masking strategy. The downside is that it requires classifier evaluation on large number of all possible two-masked images, 45 unique two-masked images among 9 81 in M3 3 and 666 among 362 1296 in M6 6, thus makes this strategy computationally expensive.
4.1.5 Greedy Cutout
As mentioned above, the compute requirement of an exhaustive search for the worst-cuse masked images might be prohibitive to train the classifiers. On the other hand, light weight masking strategy like random Cutout or heuristic like Gutout might not be fully effective for our objective. Our proposed masking strategy Greedy Cutout (Sec. 3.4 approximates the worst-case masked images with much less computation overhead, bringing the best of both worlds. We propose to train the classifiers with the worst-case masked images obtained from this masking strategy. We refer the masking strategy of our baseline version of Greedy Culoul as greedy3x3 and greedye x 6 with masks set Max3 or Max 6 respectively. Note that greedyy requires 71 classifier evaluations to find the worst-case masks, which still high in computation. We address this issuc with our other variant of greedy masking called Multi-size Greedy Cutout. As mentioned in Sec. 3.4 this variant decomposes the larger mask 100 100 mask from Max3 neatly into four 69 x 69 masks belonging to Max6. Henceforth, this variant approximates the worst-case masks from M& x in just 26 classifier evaluations which is 2.7x faster than the former approach. We refer the masking strategy from Multi-size Greedy Cutout as greedy. The neat decomposition of masks from Ma to Ms 6 allow us to use these two mask sets in our approach and therefore we adapt the same masks sets in the above masking strategies for fair comparison.
4.2 Results
We report our main results in Table and compare the performance of our method with various prior works.
Significant improvements in certified robust accuracy: PatchCleanser Xiang et al. 2022 is the
state-of-the-art method for certification against adversarial patches. Tt. has been shown that it improves certification performance compared to previous methods Chiang et al. (2019); Zhang al. 2002 Levine
& Feizi (2020); Xiang et al. (2021); Metzen & Yatsural (2021) by large margin. Table I shows that our proposed Multi-size Greedy Cutout masking strategy improves robust accuracy over the PatchCleanser Random Cutout bascline across all three classifiers (ResNet, ViT, ConvNeXt) and datascts (ImageNette, ImageNet, CIF)R-10), thus selting new state-of-the-arl certified robustness results. The performance gap is noticeably increasing with increased certification pixels. Notably, certified robust accuracy on ImageNet with a ViT-B16-224 model increases from 52.5% to 57.7% against a 3% square patch applied anywhere on the image (mask set size of 32 9). We also see large improvements for ImageNette and CIFAR-10 datasets. We perform extensive comparisons with baselines and prior work for the Teage,ette, ImageNet and CIFAR-10
9

---

Published in Transactions on Machine Learning Research (10/2023)
Table 3: Comparing different masking strategies We show robust accuracy on the ResNet architec- ture using 3% pixel patch for ImageNette and ImageNet, and 2.4% pixel patch for CIFAR-10, CIFAR-100 and SVHN. In order from top to bottom, the sets of rows show the performance of Random Cutout with certification masks 4.1.2, Gutout Cutout guided by Grad-CAM (.1.3). Cutout guided by exhaustive
search 4.1.4). and Greedy Cutout (4.1.5) strategies.
Mechod
#pasom
ImaggeNetie
ImagoNNet
Mask
CIFAR-16
Ma
CIFAR-I00
SVHN
ImaugeNette
JeagguNes
CIFAR-10
Myxd
CIPAR-100
SVHN
xx
50.5
72.0
69.1
F7.4
52.0
randaxe
89.1
42.5
65.5
30.1 1
33.9
92.77
J9.0
73.8
48.9
50.4
rand
91.3
45.1
71.0
43.7
42.8
96.8
50.3
77.1
51.8
56.7
gatuolasa
92.2
74.4
68.4
94.00
50.5
79.1
66.1
54.4
gatocisue
4
92.0
44.3
70.3
42.9
36.3
94.1
49.3
76.2
G1.7
49.5
galpet
92.3
75.1
94.3
goidaxa
45
93.7
61.6
79.7
64.2
62.8
95.7
64.9
84.0
60.1
62.6
gidexs
006
50.2
78.8
52.5
90.6
02.5
groddya
17
83.4
51.6
79.4
54.1
633-4
90.4
55.0
84.1
00:2
61.1
goodbis
71
93.5
50.0
78.5
12.0
02.7
93.6
07.6
84.9
61.8
69.5
greedy (Ours)
90.7
70.2
53.9
90.8
61.0
ImageNet
CIFAR-10
CIFAR-100
84
98
92
88
76
PC-Cutout Clean Acc
96
Accuracy (%)
72
Greedy Cutout Clean Acc (ours)
PC-Cutout Robust Acc
92
94
84
80
64
Greedy Cutout Robust Acc (ours)
90
76
72
88
60
68
86
64
84
60
25
Mask set size Ma
Mask set size Max.
Mask size Maxi
Figure 5: Generalizability of Multi-size Greedy Cutout training to distinct certification mask set We train a ViT-B16-222 model using our proposed Multi-size Greedy Cutout. During training, we use masks from Max3 and M6x6. During certification, we observe that this model improves certified accuracy even when mask sets M4 x 4 and M5x5 are used.
datasets. In addition, also show that our approach improves certified robustness additional datasets like CIFAR-100 and SVHN. In Table 2 we see that certified robust accuracy on CIFAR- 100 with a ViT- B16-224 increases from 69.1% to 74.5% against 2.4% square patch applied anywhere on the image (mask set size of 62 = 33).
In Table 1 we observe that Multi-size Greedy Cutout provides a large improvement robust accuracy in comparison to PatchCleanser, but that comes with slight reduction in clean accuracy. For e.g., clean accuracy on ImageNet with ViT-B16-224 decreases from 83.1% to 82.0% from the certification with mask set M8x6 at 3% patch size. We believe this is an acceptable compromise for the improvement in robustness.
Performance of different masking strategies: Table 3 compares performance of different masking strategics discussed in Sec. 1.1 on ResNet. We observe that Greedy Cutout performs better than Random Culout with certification masks and also Gulout. Moreover, it is comparable with the expensive Grid search. For c.g., certified robust accuracy for Multi-size Greedy Cutout on ImageNet 51.2% against a 3% patch (mask set size of 32 9). This is better than Random Culout at 45.1% and Gulout at 46.9%. Grid search is slightly higher at 51.6%. Results for ViT are provided in Table A1 in the appendix.
Tradcoff between defense performance and compute time (Multi-size Greedy Cutout): We also compare the number of extra forward passes needed during training for each method. We see that the Greedy Cutout requires lesser compute than Grid seach, e.g. 71 unique forward passes compared to 666 for 6x x mask set, but achieves comparable robust accuracy (Table 3). Also, our Mulfi-size Greedy Cutout is an efficient strategy to reduce forward passes from 71 to only 26 but still achieve competitive certification performance with mask set of 6x 6.
10

---

Published in Transactions on Machine Learning Research (10/2023)
Generalizability of Multi-size Greedy Cutout training to distinct certification mask set: We plot the robust accuracy against certification mask set size in Fig 5 We observe that robust. accuracy increases when mask set size increases during certification. Our Multi-size Greedy Cutout maintains an improvement over all certification mask sets Max Mix4 4, M5x5. MG x even though only masks from X3x3 and M9 x were used during Multi-sized Greedy Cutout training.
5 Conclusion
PatchCleanser Xiang et al. (022) certification roquires all the double masked image combinations to be correctly classified for an image to be certified against adversarial patches. An image classifier should be invariant to pixel masking to leverage such a certification process. PatchCleanser trains models with Random Cutout augmentation.
this paper, we show that training the classifier with cutout applied at worst- case regions, i.c., regions which produce the highest classification loss, improves cortification accuracy over PatchCleanser by large margin. This indicates that our training stralegy improves classifier invariance to pixel masking over prior methods. We investigate other masking strategies like Grad-CAM guided masking and exhaustive grid search to find the worst-case mask regions. To reduce the computational burden of exhaustive grid search, we introduce a two round greedy masking strategy (Greedy Cutout) to find the worst-case regions. Greedy Cutout trained models along with PatchCleanser certification sets the state-of- the-art certified robustness against adversarial patches across different models and datasets.
Limitations: 1. Computation: compared random cutout, our multi-size greedy cutout increases training time with additional 26 forward passes in each training iteration. However, time for certification and defense remain same PatchCleanser. 2. Certification: PatchCleanser requires the estimation of patch size in advance to generate the mask set and it is limited to specific patch shapes. Note that robustness guarantees are provided only to the single patch attacks but not to other form of adversarial attacks.
References
Tom Brown, Dandelion Mané, Aurko Roy, Martin Abadi, and Justin Gilmer. Adversarial patch. MLSec Workshop, NIPS, 2017.
Ping-yeh Chiang, Renkun Ni, Ahmndd Abdelkader, Chen Zhu, Christoph Studor, and Tom Goldstein. Cer- tified defenses for adversarial patches. In International Conference on Learning Representations, 2019.
Esther Choi et al. Gutout. URL
2020.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hicrarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pp. 248 255. leee, 2009.
Terrance DeVries and Graham W Taylor. Improved regularization of convolutional neural networks with cutout. arXiv preprint arXiv:1708 705.04552, 2017.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Un- terthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, al. An image is worth 16x16 words: Transformers for image recognition scale. In International Conference on Learning Rep- resentations, 2020.
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 Recognition. IEEE, jun 2018. doi: 00.1100/evpp:2018.0011
Sven Gowal, Sylvestro-Alvise Rebuffi, Olivia Wiles, Florian Stimberg, Dan Andrei Calian, and Timothy A Mann. Improving robustness using generated data. Advances in Neural Information Processing Systems, 34:4218-4233 2021.
11

---

Published in Transactions on Machine Learning Research (10/2023)
Jamie Hayes. On visible adversarial perturbations & digital watermarking. In Proceedings of the IEEE Conference Computer Vision and Pallern Recognätion Workshops, pp. 1597-1604, 2018.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770 (00-777, 2016.
Jeremy Howard et al. Imagenette. URL https://github.
2020.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. 2009.
Alexander Levine and Soheil Feizi. (de) randomized smoothing for certifiable defense against patch attacks. Advances in Newral Information Processing Systems, 086465-64777 2020.
Lin Li and Michael W. Spratling. Data augmentation alone can improve adversarial training. In The Fleventh International Conference on Learning Representations, 2023.
Wan-Y Yi Lin, Fatemch Shcikholeslami, Leslic Rice, J Zico Kolter, et al. Certified robustness against adversarial patch attacks via randomized cropping. In ICML 2021 Workshop on Adversarial Machine Learning, 2021.
Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo. Swin transformer: Hierarchical vision transformer using shifted windows. In Proceedings of the IEEE/CVF international conference on computer vision, pp. 10012-10022, 2021.
Zhuang Liu, Hanzi Mao, Yuan Wu, Christoph Feichtenhofer, Trevor Darrell, and Saining Xie. A convnet for the 2020s. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 11976 11986, 2022.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, 2018.
Xiaofeng Mao, Yuefeng Chen, Ranjie Duan, Yao Zhu, Gege Qi, Xiaodan Li, Rong Zhang, Hui Xue, et al. Enhance the visual representation via discrete adversarial training. Advances in Neural Information Pro- cessing Systems, 35:7520 7533, 2022.
Jan Hendrik Metzen and Maksym Yatsura. Efficient certified defenses against patch attacks image classifiers. In International Conference on Learning Representations, 2021.
Norman Mu and David Wagner. Defending against adversarial patches with robust self-attention. In ICML 2021 Workshop Uncertainty and Robustness in Deep Learning, 2021.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Ng. Reading digits in natural images with unsupervised feature learning. 2011.
Axi Niu, Kang Zhang, Chaoning Zhang, Chenshuang Zhang, In So Kweon, Chang D Yoo, and Yanning Zhang, Fast adversarial training with noise augmentation: A unified perspective on randstart and gradalign. arXiv preprint Xix::2200 05488, 2022.
Sukrut Rao, David Stutz, and Bernt Schiele. Adversarial training against location-optimized adversarial patches. In European Conference on Computer Vision, pp. 429-448. Springer, 2020.
Hadi Salman, Saachi Jain, Eric Wong, and Aleksander Madry. Certified patch robustness via smoothed vision transformers. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 15137-15147, 2022.
Ramprasaath R. Sclvaraju, Michael Cogswell, Abhishek Das, Ramakrishna Vedantam, Devi Parikh, and Dhruv Batra. Grad-cam: Visual explanations from deep networks via gradient-based localization. In Proceedings of the IEFE International Conference on Computer Vision (ICC)) Oct 2017.
Ross Wightman. Pytorch image models. http::////tthhhc..oo//aaaa////rp
2019.
12

---

Published in Transactions on Machine Learning Research (10/2023)
Ross Wightman, Hugo Touvron, and Hervé Jégou. Resnet strikes back: An improved training procedure in timm. Xix preprint or 1 10.004 76, 2021.
Chong Xiang, Arjun Nitin Bhagoji, Vikash Schwag, and Prateck Mittal. Patchguard: A provably robust defense against advessarial patches via small receptive fields and masking. In USENIX Security Symposium, pp. 2237-2254, 2021.
Chong Xiang, Saeed Mahloujifar, and Prateek Mittal. (PatchCleanserry: Certifiably robust defense against adversarial patches for any image classifier. In 81st USENIX Security Symposium (USENIX Security 22), pp. 2065 2065-2082, 2022.
Mingrang Yi, Lu Hou, Jiacheng Sun, Lifeng Shang, Xin Jiang, Qun Liu, and Zhiming Ma. Improved ood generalization via adversarial training and pretraing. In International Conference on Machine Learning, pp. 11987-11997. PMLR, 2021.
Zhanyuan Zhang, Benson Yuan, Michael McCoyd, and David Wagner. Clipped bagnet: Defending against sticker attacks with clipped bag-of-features. In 2020 IEEE Security and Privacy Workshops (SPW), pp. 55-61. IEEE, 2020.
13

---

Published in Transactions on Machine Learning Research (10/2023)
Appendix
Algorithm Multi-size Greedy Cutout
Input: Image label pair (x, y), vanilla classifier F, mask sets M3x3, M6x6
Output: Augmented data (x1,)) (x, procedure ROUND- [xx, F, M3x3, Moxe)
loss -- for each Max3 do
4: if ((F(x @ m) > loss then
5:
M - m end if end for
Mask with the largest loss
6:
7:
M - {4 mask from Møxe that covers M1).
loss --
10:
for each M do
11:
if ((F(x O m) loss then
M11 - m end if 14: end for
12:
Mask with the largest loss
13:
15: return M1, M11
16:
end procedure
17: procedure ROUND-2(x, F, Max3, M6x6)
18:
M,, M11 ROUND-1(X, Max3, M6x6)
19:
loss --1
20:
for m E Max3 do
21:
if ((F o M11 m) > loss then
22:
m²
Mask with the largest loss
23:
end if end for
24:
25:
M2 - M1 3 m
26:
M {4 mask from M6x6 that covers my.-
27:
loss -1
28:
for each M do
29:
if E(F O M11 m) loss then
30:
m - m end if end for
Mask with the largest loss
31:
32:
33:
M22 - Mi O m
34:
x - x M2
Applying mask to augment data Applying mask to augment data
35:
x2 x M22
36: return (x/,)), (x/,y)
37: end procedure
A
Datasets
We use five popular image classfication datasets ranging from low-resolution to high resolution images.
(1) ImageNet: ImageNet is an image classification dataset Deng et al. (2099) with 1000 classes. It has 1.3 million training images and 50k validation images.
(2) ImageNette: ImageNette Howard et al. (2020) a 10-class subset of ImageNet with 9469 training images and 3925 validation images.
(3) CIFAR-10: CIFAR-10 Krizhevsky al. 2009 is a benchmark dataset for low-resolution image classi-
fication. The CIFAR-10 dataset consists of 60k 32x32 colour images in 10 classes, with 6k images per class.
14

---

Published in Transactions on Machine Learning Research (10/2023)
There are 50k training images and, 10k test images.
(4) CIFAR-100: This dataset Krizhevsky et al. (2009) is just like the CIFAR-10, except it. has 100 classes containing 600 images each. There are 500 training images and 100 testing images per class. The 100 classes in the CIFAR-100 are grouped into 20 superclassos.
(5) SVHN: Street View House Numbers (SVHN) Netzer el al. (2011) a digit. classification benchmark dataset that contains 600,000 32x32 RGB images of printed digits (from to 9) cropped from pictures of house number plates.
Models: We use image classifiers from three different architecture families. (1) ResNet:
ResNets He et al. (2016) are deep neural networks which use skip connections. This approach makes it possible to train the network on thousands of layers without affecting performance. We use the ResNetV2-50x1 model from the timm Wightman et al. (2021) library.
(2) Vision Transformers (VIT): Convolutional Nets are designed based on inductive biases like translation invariance and locally restricted receptive field. Unlike them, transformers are based on self-attention mechanism that learns the relationships between elements of sequence. We ViT-B16-224 model.
(3) ConvNeXt: ConvNeXt Liu et al. (2022) is pure convolutional model (ConvNet), inspired by the design of Vision Transformers. The design starts from a standard ResNet (c.g. RosNet50) and gradually "modernizes" the architecture to the construction of a hierarchical vision Transformer (e.g. Swin-T Liu jt al. 2021))) We use the ConvNeXt tiny in22ft 1 model from timm. It. is trained on ImageNet-22l and tune-tuned on ImageNet-lk.
Table A1: Comparing certified robust accuracy of different masking strategics at two different mask set configurations Ma 3 and M6 6 across different datasets on VIT. Certification pixels used 3% for ImageNettee and ImageNet, and 2.4% for CIFAR- 10, CIFAR- 100 and SVHN,
Mask ser Maxs
Masik set Maxs
Meshod
InmguNNotle
IomgoNot
CIFAR-10
CIFAR-100
SVHN
InasgeNetiee
CIFAR-10
CIFAR-100
SVHN
nuddaxa
94.3
59.8
96.5
56.7
67.9
07.1
randoxo
0
53.8
50.6
79.5
54.0
42.2
96.0
56.7
86.0
64.4
61.3
VIT
58.3
88.4
67.7
gridsss
45
95.3
67.9
58.0
67.3
62.7
97.3
60.5
92.2
74.6
74.0
gridu
660
05.3
61.1
97.2
78.1
grendyssx
17
95.1
58.3
68.6
82.5
97.2
61.2
92.2
74.2
13.8
groedyssed
71
95.1
36.8
86.2
64.4
80.6
97.5
63.8
91.8
74.3
77.9
greedy (Ours)
70.8
Table A2: Table listing the number of forward passes needed in each batch training for grid search and our Greedy Outout approach.
Method
# forward passes/batch training
grid search3 x grid searche 6
45 unique among 9 9 81
666 unique among 36
1296
greedy3x3
"Foonnd I 3 Tround = 17
greedya
36
(round 1) + 35 (round 2) 71
greedy (Ours)
13
(round 1) + 13 (round 2) 26
B Masks selected
depicts the masks selected from exhaustive cutout and our Multi-size Greedy Cutout from both Ma x and M6 x 6 on ImageNet training samples. can be observed the figure that masks could potentially cover the entire object (c.g. last row) and training on such instances would limit model lcarning capabilitios. On the contrary, we observe that this training scheme encourages for higher robust accuracy as shown in Table where grids x and Multi-size Greedy Cutout (greedy) achieve comparable results for M3x3 and grids x yield higher numbers than ours on M9 x 6 with significantly higher training complexity. We
Figure A1
Note that training with the masking strategy greedys x on ImageNet is computationally costly and possible with available GPU resources. Same for Tahle
15

---

Published in Transactions on Machine Learning Research (10/2023)
Masks from mask set M3x3
Masks from mask set M6x6
Clean image
Exhaustive Cutout
Greedy Cutout (ours) Exhaustive Cutout Greedy Cutout (ours)
Figure Al: Masks selected via cutout guided by exhaustive search and our Multi-size Greedy Cutout from both the mask sets M3 and Ms 6 on ImageNet training samples.
hypothesize that images with partially covered objects are dominating in number and hence providing strong training signal to the model, which making the noisy training signal from fully covered objects negligible.
16


Reviews:
[{"review_id": "4kJfy7RrzR", "reviewer": "Reviewer_QQsV", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The proposed intuitive greedy-cut method closely approximates classifier accuracy achieved through exhaustive cutout search, highlighting its effectiveness.\n2. A notable advantage of the greedy-cut approach is its reduction in training time.\n3. Remarkable enhancements in accuracy across various datasets are demonstrated through the application of the greedy-cut method.\n\nWeaknesses:\n1. Doubts emerge concerning the validity of employing the exhaustive search method as an upper limit, as it tends to result in complete occlusion of the target. This renders the classification task inherently impractical, potentially leading to limited learning for the model.\n2. The significant contribution of this paper, which pertains to improved time efficiency, lacks comprehensive elaboration.\n3. Certain language issues are present within the paper that require attention and refinement.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents an enhanced method building upon PatchCleanser. The core concept introduces the notion that the classifier, when trained using the worst case masked images, yields optimal classification outcomes. The paper outlines a two-step greedy approach for identifying these complex masks. Experimental results demonstrate notable improvement across multiple datasets and models.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. To enhance the support for the greedy cutout method, the author could provide a direct comparison between masks selected using the greedy cutout approach and those selected via exhaustive cutout.\n2. The paper's value could be significantly demonstrated by including a table that outlines computation times for various methods.\n3. To bolster the intuitive concept behind exhaustive search cutout, the author is encouraged to delve deeper into its rationale through additional discussion.\n4. Language Modifications:\n   a) Page 1, second paragraph of the Introduction, line 5: Remove \"for\" from \"Hence. the certified robust accuracy for is the\".\n   b) Page 2, line 1: Change \"proposes two round pixel masking\" to \"proposes two-round pixel masking\" or \"proposes two rounds of pixel masking\".\n   c) Page 5, second paragraph, line 1: Remove \"of\" from \"In the first round of\". Please also review the paper for other potential language improvments.\n\n", "broader_impact_concerns": "I have no concerns about the ethical implications of the work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "rHtI2wDrVy", "reviewer": "Reviewer_BGXY", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The motivation and method design is reasonable, simple yet effective. The key insight behind Greedy Cutout is akin to adversarial training in my opinion, which has been widely received to improve the robustness effectively. In the patch robustness case, it leads to the search for the patch incurring the largest loss. The optimizations are novel and smart.\n- Strong empirical performance. Across a wide range of datasets and architectures, the proposed approach improves the certified accuracy significantly with little loss of normal accuracy.\n\nWeaknesses:\n- The presentation could be further improved. Though there are few grammatical or writing issues, some concepts and logic appears unclear to me. See details in \"Requested Changes\".\n- The proposed method could be limited in terms of needing a specific patch shape and specific certification method.\n- The experimental evaluation lacks the comparison under the same running time with published baselines.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a masking strategy - Greedy Cutout, for improving certified robustness against patch attacks. Greedy Cutout is designed to be used jointly with PatchCleanser. The high-level intuition is to search for the patch incurring the largest loss and then apply it. Several optimizations such as state-wise greedy search and stage-wise patch decomposition are introduced. Experiments on ImageNette, ImageNet, and CIFAR-10 with multiple architectures show the effectiveness.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. The manuscript's clarity could be improved by explaining new concepts in detail:\n- In Figure 1(b), authors show a full occlusion can make the classifier hard to predict, while partial occlusion is more desired. This concept is restated in Section 4.1. However, how does Greedy Cutout succeed in providing partial occlusion? It seems that Greedy Cutout searches for the patch location of the highest loss, which can still occlude the object completely.\n- In Section 4.1, what does \"pixel masking\" mean? Does it mean applying the mask at the pixel-level granularity?\n- In Section 4.1.4, what does \"long edges\" mean? Why does exhaustive search induce \"long edges\"?\n\n2. Could the authors discuss the generalizability of the approach for other sets of patch masks beyond $M_{3\\times 3}$ and $M_{6\\times 6}$? The illustration appears to be very specific. It would be great if some high-level guidance is provided in this sense.\n\n3. Though Greedy Cutout improves the efficiency greatly compared to exhaustive search, in experimental evaluation, there is no training time control. A comparison with PatchCleanser under the same training time budget would be great, e.g., by setting different training epochs for different methods.", "broader_impact_concerns": "The authors may use a new section to emphasize the limitations of patch certification in PatchCleanser, e.g., no guarantee for patch attacks larger than the given threshold or different from the supported shape, and no guarantee for other forms of attacks. So practitioners would not over-interpret the certification statement.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "u2y9fv1xG9", "reviewer": "Reviewer_G1gq", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The idea is simple and intuitive.\n- The Greedy Cutout strategy outperforms other Cutout strategies\n\nWeakness:\n- This work mainly bases on PatchCleanser, hence its novelty is limited.\n- The results of PatchCleanser presented in this paper are different from those in the original paper (cf. Table 2 in the original paper).\n- There is no any reporting results about the running times.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a simple Greedy Cutout strategy to improve doubled-masks of PatchCleanser. The main idea is to to choose worst-case masked images with high classification loss for training. The worst-case masks are chosen from the mask set that are used during certification.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1) The authors mentions that \" PatchCleanser uses Random Cutout augmentation DeVries & Taylor (2017), i.e., applying two masks of size 128×128 at random locations to 224 × 224 training image\", which seems different from what were mentioned to in Alg. 2 and Sec. 4 in that paper.\n\n2) Why are the results of PatchCleanser presented in this paper different from those in the original paper (cf. Table 2 in the original paper)?\n\n3) The authors should show the running times of the proposed approach and the baselines.\n\n4) As shown in Alg. 2 in the PatchCleanser, for $M_{3 \\times 3}$, the number of pairs $m_0, m_1$ to go through is $36$ which is not a high number. Therefore, it is unclear to me the motivation of this work. ", "broader_impact_concerns": "The paper proposes a technique to certify the patch attack. I do not have any concern of the ethical implications.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "uFxPVfuUf3", "reviewer": "Reviewer_7Aio", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n- The paper addresses a significant goal. Adversarial patches are more realistic threats and certified robustness is more reliable than empirical defenses.\n    \n- The motivation of the proposed method is made clear.\n    \n- The proposed method is simple and presents a degree of novelty.\n    \n- The experiments are extensive as both small and large datasets and both CNNs and ViTs are included.\n    \n\nWeaknesses:\n\n- The proposed method is comparably incremental, deriving heavily from the previous work, PatchCleanser. Only one component of the algorithm exhibits significant improvement.\n    \n- Comparisons of the training time are missing. Given that the proposed method increases the computation time during training, it is important to inform readers about the extent of time investment required to improve robust accuracy. The number of passes shown in Table 3 does not sufficiently convey this information.\n    \n- The structure could use some refinement. For example, Subsection 4.1 is in the Experiments section, yet it does not contain any experimental results.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper deals with the challenge of improving the certified robustness of image classifier against adversarial patches. The proposed method is based on the notion of worst-case masking, utilizing a greedy strategy to approximate the worst-case mask location. Experimental results show that the proposed method is superior to the previous state-of-the-art.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "In addition to the aforementioned weaknesses, I would encourage the authors to consider the following changes:\n\n- Improve the presentation structure. I would suggest you relocate Subsection 4.1 to Section 3 and make the description of Table 3 a subsection for the ablation study of masking strategies.\n    \n- The paragraph title “Multi-size Greedy Cutout” in subsection 3.4 is repeated for describing Round 1 and Round 2. In fact, It would be better if the whole subsection 3.4 can be rewritten in a more organized way.", "broader_impact_concerns": "I have no concerns about the ethical implications of the work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposed a new and effective method for certified training against adversarial patch attacks. The novelty lies in the proposed two-round greedy masking strategy (Greedy Cutout) for approximating worst-case mask location. Experimental results show improved certified robust accuracy with a notable increase when compared to state-of-the-art. The authors' rebuttal has successfully addressed the reviewers' questions. All reviewers recommend to accept this submission, and I concur.
Decision: Accept (poster)