PatchCleanser: Certifiably Robust Defense against Adversarial Patches for Any Image Classifier

1 Introduction

• Localized adversarial patches can be printed and attached to objects, creating a physical-world misclassification threat to computer-vision systems.Source: §1 · p. 1
• Prior defenses face architecture constraints that limit accuracy, while Minority Reports (MR) [32] is architecture-agnostic but only detects patch attacks.Small receptive fields limit the information available to each feature and constrain classification accuracy.Source: §1 · p. 1
• Two rounds of image-space masking use inconsistencies in two-mask predictions to filter malicious one-mask predictions, enabling compatibility with any image classifier.At least one first-round mask can remove the entire patch; the second round tests disagreeing predictions to help identify the benign prediction.Source: §1 · p. 2
• Across three model architectures and six datasets, PatchCleanser achieves state-of-the-art clean accuracy and significantly improves certified robust accuracy over prior works.Figure 2 compares clean and certified robust accuracy on ImageNet against a 2%-pixel square patch anywhere on the image.Source: §1 · pp. 2–3, Figure 2 · p. 3
• PatchCleanser formally guarantees correct predictions for certain images against any adaptive white-box attacker within its threat model.Source: §1 · p. 3

2.1 Image Classification Model

• The classification model maps images in the scaled image space to class labels, and the formulation assumes no particular model architecture.The stated compatible examples include ResNet, Vision Transformer, and ResMLP.Source: §2.1 · p. 3

2.2 Threat Model

• The attacker seeks test-time misclassification by controlling pixels in a restricted region that may occur anywhere in the image.The formal threat model represents the region as a binary mask and permits arbitrary values for pixels within it.Source: §2.2 · p. 3
• The primary comparison setting is one square patch at any image location, with the defender conservatively estimating its size.This setting supports comparison with prior works addressing the same threat model.Source: §2.2 · p. 3
• The threat analysis also considers sets of patch shapes and multiple patches, including arbitrary rectangles and two patches.The defense is described as adaptable to these stronger attackers, which are analyzed in Section 5.1.Source: §2.2 · p. 3

2.3 Defense Objective

• The defended classifier is intended to preserve the correct label under attack without abstaining, a stronger objective than merely detecting an attack.The target is D(x′) = D(x) = y for clean data point (x,y) and any allowed adversarial example x′.Source: §2.3 · pp. 3–4
• The defense objective is to certify correct predictions for labeled images against every adaptive attacker allowed by the threat model.The certification procedure provides a provable lower bound on robustness; certified robust accuracy is measured over labeled test sets, not as a guarantee for individual images in the wild.Source: §2.3 · p. 4
• PatchCleanser aims to work with state-of-the-art architectures, avoiding the architecture dependence that can limit performance and deployment.The objective is to benefit from advances in image classification research.Source: §2.3 · p. 4
• The defense also targets scalability to high-resolution images, which state-of-the-art classifiers use for better classification performance.Defenses restricted to low-resolution images are described as having limited applicability.Source: §2.3 · p. 4

3.1 Pixel Mask Set

• A mask is a binary image-shaped tensor with zeros on masked pixels, and an R-covering set guarantees that at least one mask covers every patch in the specified region set.Different R-covering sets can vary in mask count, size, and shape.Source: §3.1 · p. 4

3.2 Double-masking for Robust Prediction

• Two-round masking uses an R-covering mask set to detect prediction disagreement, test disagreer masks with a second round, and return a unanimous prediction or the one-mask majority.When the number of disagreers is bounded by C, complexity is O(|M|+C·|M|), with worst-case O(|M|^2); the authors describe it as the first certifiably robust image-classification defense without abstention.Source: §3.2 · pp. 4–6

3.3 Robustness Certification for DoubleMasking Defense

• If the mask set is R-covering and every two-masked image is correctly classified, Theorem 1 guarantees that double-masking returns the correct label against every patch in the threat model.The certification procedure checks R-covering and evaluates every pair of masks; it certifies an image only if all two-mask predictions match its ground-truth label.Source: §3.3 · pp. 6–7

3.4 Implementation of the End-to-End PatchCleanser Defense

• Adaptive mask generation adjusts stride to fit the mask-count computation budget and chooses mask size to preserve R-covering, which holds for patches no larger than p*=m−s+1.The corresponding mask-size requirement is m*=p+s−1.Source: §3.4 · pp. 7–8
• When the estimated patch size changes, the mask stride and size can be adjusted according to Equation 3 while keeping the number of masks unchanged.Source: §3.4 · p. 8
• For 2-D images, PatchCleanser constructs masks by applying the 1-D mask-set equations separately along each image axis.For n0 × n1 images and p̄0 × p̄1 patches, it derives axis-specific mask sizes and strides and combines the resulting index sets.Source: §3.4 · p. 8
• Larger strides and masks reduce the number of masks and improve efficiency, but larger masks can reduce prediction accuracy.The mask-set generation approach is intended to balance this efficiency–accuracy trade-off for deployment.Source: §3.4 · p. 8
• The end-to-end pipeline generates a secure R-covering mask set within a computation budget, applies double-masking for robust classification, and certifies labeled images against adaptive white-box attackers.Certification applies to attackers within the threat model A_R.Source: §3.4 · p. 8

4.1 Setup

• Evaluation covers a single arbitrary-content square patch anywhere on the image, using 1%, 2%, and 3% patch areas for ImageNet/ImageNette and 0.4% and 2.4% for CIFAR-10.The main evaluation compares clean and certified robust accuracy; certified robust accuracy is the fraction of test images certified against adaptive white-box attackers within the threat model.Source: §4 · p. 8, §4.1 · p. 9

4.2 State-of-the-art Clean Accuracy and Certified Robust Accuracy across All Datasets

• For a 2%-pixel patch on ImageNet, PC-ViT raises clean accuracy from 54.6% to 83.9% and certified robust accuracy from 26.0% to 62.1%, outperforming prior defenses.Across the evaluated defenses, PatchCleanser instances significantly outperform prior works on both metrics; its clean accuracy is within 1% of vanilla state-of-the-art models.Source: §4.2 · pp. 9–10, Table 2 · p. 10
• For a 2%-pixel patch on ImageNette, PC-ViT improves clean accuracy from 95.0% to 99.6% and certified robust accuracy from 86.7% to 96.4%.For a 2.4%-pixel patch on CIFAR-10, it improves clean accuracy from 86.0% to 98.7% and certified robust accuracy from 60.0% to 89.1%.Source: §4.2 · p. 10

4.3 Detailed Analysis of PatchCleanser

• Increasing the mask count first significantly improves certified robust accuracy and then saturates, while per-example inference time rises; the default uses 36 masks.The analysis uses PC-ViT against a 2%-pixel patch on 5,000 randomly selected ImageNet test images.Source: §4.3 · p. 10, Figure 4 · p. 11
• With four times the actual patch area used as the estimate, PC-ViT still significantly outperforms prior works on clean and certified robust accuracy, while clean accuracy is barely affected by overestimation.As overestimation grows, certified robust accuracy gradually drops; the actual patch in this analysis is 32×32 pixels on a 224×224 image.Source: §4.3 · p. 11, Figure 6 · p. 11
• With a fixed 36-mask budget, PC-ViT retains 20.5% top-1 certified robust accuracy against a 112×112 patch on a 224×224 ImageNet image.At that patch size, clean accuracy remains above 80%; prior defenses' certified robust accuracy drops quickly to zero as patch size increases.Source: §4.3 · pp. 11–12, Figure 8 · p. 11, Figure 7 · p. 11

5.1 PatchCleanser against Multiple Patch Shapes and Multiple Patches

• A mask set covering the allowed patch shapes or combinations can extend double masking to rectangles and multiple patches; certifying K patches requires checking all 2^K-mask combinations.The example rectangle set contains six shapes claimed to cover any rectangle of at most 1% of image pixels.Source: §5.1 · p. 12
• 98.8% clean accuracy and 89.2% certified robust accuracy for two 1% square patches on ImageNette; two-patch performance is lower than one-patch performance but remains higher than prior work against a 2%-pixel square patch.For rectangle attacks covering at most 1% of a 224×224 image, the authors report high clean and certified robust accuracy, noting the stronger attacker explains a drop from the square-patch baseline.Source: §5.1 · p. 12, Table 4 · p. 12

5.2 PatchCleanser and Minority Reports

• At around 84% clean accuracy, PatchCleanser reaches approximately 60% certified robust accuracy, close to MR, while avoiding abstentions; MR’s 74.3% is for the weaker attack-detection guarantee.The paper cautions that the defenses’ certified robust accuracies are not directly comparable because they represent different robustness notions.Source: §5.2 · p. 13, Figure 9 · p. 13

5.3 Limitation and Future Work

• PatchCleanser’s stronger performance than some prior works comes at an efficiency cost, and defense performance trades off against efficiency; parallel masked-prediction evaluation across GPUs may improve runtime.The authors also identify improving the underlying model and inference algorithm as directions for efficiency work.Source: §5.3 · p. 13
• PatchCleanser requires conservative prior estimates of patch shape and size; underestimating either undermines robustness, though considering a union of mask shapes can mitigate shape uncertainty.Source: §5.3 · p. 13
• Prediction invariance to masking is crucial to robustness, and mask operations may change semantics in special tasks such as recognizing masks; colored masks and further classifier training are proposed for those cases.The authors also pose training models to withstand masking and designing inherently mask-robust architectures as open research questions.Source: §5.3 · p. 13

6.1 Adversarial Patch Attacks

• Patch attacks target localized image regions and can be physically realized by printing and attaching a patch; this paper focuses on test-time attacks against image classification.Prior examples include universal and localized white-box attacks and a black-box reinforcement-learning attack.Source: §6.1 · p. 13

6.2 Adversarial Patch Defenses

• Prior certified defenses include IBP, Clipped BagNet, De-randomized Smoothing, PatchGuard, and BagCert; several depend on small receptive fields, while MR and PatchGuard++ focus on attack detection.The paper contrasts those architecture constraints with PatchCleanser’s compatibility with any model architecture and its reported state-of-the-art clean and certified robust accuracy.Source: §6.2 · p. 14

6.3 Other Adversarial Example Attacks

• Conventional adversarial-example attacks use small global Lp perturbations, whereas patch attacks are localized and physically realizable.The passage distinguishes the paper’s patch-attack focus from the broader adversarial-example literature and notes the development of certifiably robust defenses after empirical defenses proved fragile to adaptive attackers.Source: §6.3 · p. 14

• PatchCleanser’s double-masking algorithm removes adversarial pixels and recovers predictions without abstention, while remaining compatible with state-of-the-art classifiers, including models with large receptive fields.The paper reports clean accuracy comparable to vanilla state-of-the-art models alongside high certified robust accuracy.Source: §7 · p. 14

• Flowers-102, CIFAR-100, and SVHN are included as additional datasets, with images resized to 224×224 pixels for the experiments.Flowers-102 images are resized and cropped; CIFAR-100 and SVHN images are resized from 32×32, and low-resolution datasets use bicubic interpolation without cropping.Source: A Details of Experiment Setup · p. 17
• For other-dataset models, training uses 10 epochs, batch size 64, SGD with momentum 0.9, and a learning rate reduced tenfold every five epochs.The initial learning rate is 0.001 for ViT and ResMLP or 0.01 for ResNet.Source: A Details of Experiment Setup · p. 17
• Default training optionally applies two random 128×128 Cutout masks to each 224×224 training image to improve prediction invariance to pixel masking.The authors describe Cutout as optional and agnostic to model architecture, with small training overhead.Source: A Details of Experiment Setup · pp. 17–18
• Runtime measurements use a workstation with 48 CPU cores, 384 GB RAM, and eight RTX 2080 Ti GPUs, with batch size one on one GPU for per-example timing.Source: A Details of Experiment Setup · p. 18

B Challenger Masking: Improving Inference Complexity

• O(|M|) worst-case complexity and the same certified robust accuracy come with slightly lower clean accuracy than double-masking.The paper chooses double-masking in the main body because it prioritizes defense accuracy.Source: B Challenger Masking: Improving… · pp. 18–19
• When first-round masked predictions disagree, challenger masking compares a pair's two-mask prediction with their one-mask predictions and removes the losing pair.It repeats challenges until one label remains; unanimous first-round predictions bypass the challenge game.Source: B Challenger Masking: Improving… · p. 18
• The first-round masking and challenger game each require O(|M|) operations, unlike double-masking's O(|M|^2) worst case.Under two-mask correctness, a first-round mask that removes the patch cannot lose the challenger game.Source: B Challenger Masking: Improving… · p. 18

Effect of model architectures and Cutout training

• PC-ViT has the best defense performance, with significantly higher clean and certified robust accuracy than PC-ResNet and PC-MLP despite similar vanilla-model clean accuracy.The comparison covers a 2%-pixel patch on ImageNette/ImageNet and a 2.4%-pixel patch on CIFAR-10.Source: C Additional Evaluation Results · p. 19

Evaluation results on additional datasets

• PatchCleanser also works on Flowers-102, CIFAR-100, and SVHN under the stated 2%- or 2.4%-pixel patch settings.The evaluation uses a 32×32 patch on 224×224 Flowers-102 images and a 5×5 patch on 32×32 CIFAR-100 and SVHN images.Source: Table 6 · p. 19, C Additional Evaluation Results · p. 19

Effect of model architectures and Cutout training

• On CIFAR-10, Cutout raises PC-ResNet clean accuracy from 94.3% to 97.8% and robust accuracy from 39.4% to 78.8%.Cutout significantly improves both accuracy measures on ImageNette and CIFAR-10, while ImageNet results vary by model.Source: C Additional Evaluation Results · p. 19

Trade-off between efficiency and performance

• Larger mask sets improve clean and certified robust accuracy on ImageNette and CIFAR-10, with a moderate increase in per-example inference time.The CIFAR-10 runtime comparison spans defenses using different input resolutions; PatchCleanser uses 224×224 images.Source: C Additional Evaluation Results · pp. 19–20

Effect of patch size over-estimation

• For actual 32×32 ImageNette and 5×5 CIFAR-10 patches, overestimating patch size produces observations similar to those in Section 4.3.The corresponding evaluations are shown for ImageNette and CIFAR-10.Source: C Additional Evaluation Results · p. 20

Performance against large patch sizes

• Large-patch defense performance is reported for ImageNette and CIFAR-10, with observations similar to those in Section 4.3.The evaluations appear in Figures 13 and 16.Source: C Additional Evaluation Results · p. 20, Figure 13 · p. 20, Figure 16 · p. 20

Additional results for Minority Reports

• Additional Minority Reports results cover ImageNette with a 2%-pixel patch and CIFAR-10 with a 2.4%-pixel patch, with observations similar to Section 5.2.Figure 19 presents the additional results.Source: C Additional Evaluation Results · pp. 20–21, Figure 19 · p. 21

D Case Study: Certifiable Robustness vs. Empirical Robustness

• Empirical robust accuracy drops significantly for both undefended ViT and PatchCleanser models under the stronger attack setting.The stronger setting uses 200 iterations and 10 random patch locations, versus 100 iterations and one location.Source: D Case Study: Certifiable Robustness… · p. 21
• The comparison uses PatchAutoPGD on 1,000 randomly selected test images from different datasets.It reports empirical results for two attack settings alongside certified robust accuracy.Source: D Case Study: Certifiable Robustness… · p. 21
• Certified robust accuracy is a provable lower bound that an adaptive attacker within the threat model cannot push below.The reported empirical robust accuracy is higher than the certified robust accuracy.Source: D Case Study: Certifiable Robustness… · p. 21

Object size

• For a 2%-pixel patch, PatchCleanser generally has higher certified robust accuracy on ImageNet images with larger salient objects.The authors note that small objects may be completely occluded by the patch.Source: E PatchCleanser Robustness for Images… · p. 21, Figure 20 · p. 22, Figure 21 · p. 22
• Salient object size is measured as the percentage of image pixels covered by the union of annotated object bounding boxes.The analysis uses ImageNet bounding-box annotations.Source: E PatchCleanser Robustness for Images… · p. 21

Object class

• Certified robust accuracy varies greatly by class, ranging from 100% for some classes to 4% for others; the authors identify poor-performing classes for future analysis.The class comparison also plots average object size, and the authors state that performance depends on both size and class.Source: E PatchCleanser Robustness for Images… · pp. 21–22, Figure 22 · p. 22