Source-linked AI summary
(De)Randomized Smoothing for Certifiable Defense against Patch Attacks
Alexander Levine, Soheil Feizi
TL;DR
Patch attacks provide a quantitative model of physical adversarial threats, but existing certified defenses had limited CIFAR-10 performance and ImageNet scalability. The paper introduces structured ablation, which exploits patch structure to derandomize randomized smoothing and produce exact certificates. It reports substantially stronger CIFAR-10 certified robustness, faster training, and certification at ImageNet scale, while noting that robustness does not extend to general adversarial attacks.
Problem
Existing certified patch defenses achieved poor certified accuracy on CIFAR-10 and were unlikely to scale to ImageNet, despite patch attacks modeling physical adversarial threats.
Method
Structured ablation selects pixels in correlated patterns matching contiguous patches, reducing possible ablations enough to evaluate all of them exactly.
Results
More than 27 percentage points of certified robustness improvement over [9] is reported on CIFAR-10, alongside approximately 1.0- and 2.5-GPU-hour training times on MNIST and CIFAR-10.
Takeaways & Limitations
The method significantly outperforms the prior certified patch defense on CIFAR-10 and, unlike previous methods, scales to ImageNet.
Takeaways & Limitations
The techniques do not provide robustness to general adversarial attacks other than patch attacks.
Abstract
from arXiv · showhide
Patch adversarial attacks on images, in which the attacker can distort pixels within a region of bounded size, are an important threat model since they provide a quantitative model for physical adversarial attacks. In this paper, we introduce a certifiable defense against patch attacks that guarantees for a given image and patch attack size, no patch adversarial examples exist. Our method is related to the broad class of randomized smoothing robustness schemes which provide high-confidence probabilistic robustness certificates. By exploiting the fact that patch attacks are more constrained than general sparse attacks, we derive meaningfully large robustness certificates against them. Additionally, in contrast to smoothing-based defenses against L_p and sparse attacks, our defense method against patch attacks is de-randomized, yielding improved, deterministic certificates. Compared to the existing patch certification method proposed by Chiang et al. (2020), which relies on interval bound propagation, our method can be trained significantly faster, achieves high clean and certified robust accuracy on CIFAR-10, and provides certificates at ImageNet scale. For example, for a 5-by-5 patch attack on CIFAR-10, our method achieves up to around 57.6% certified accuracy (with a classifier with around 83.8% clean accuracy), compared to at most 30.3% certified accuracy for the existing method (with a classifier with around 47.8% clean accuracy). Our results effectively establish a new state-of-the-art of certifiable defense against patch attacks on CIFAR-10 and ImageNet. Code is available at https://github.com/alevine0/patchSmoothing.
1 Introduction
Patch attacks model physical adversarial threats by allowing arbitrary pixel changes within bounded regions, while prior certified defenses struggled to scale beyond simpler datasets. The paper proposes structured ablation, exploiting patch contiguity to obtain deterministic certificates and stronger results.
- Threat model: Patch attacks formalize physical adversarial attacks by permitting arbitrary changes within a bounded pixel region.They can represent both universal and image-specific attacks on square patches.
- Prior limitations: Prior certified patch defenses used interval bound propagation but achieved poor CIFAR-10 accuracy and were unlikely to scale to ImageNet.The cited defense performed well on MNIST but did not scale well to complex inputs.
- Results: More than 27 percentage points of certified robustness improvement over [9] is reported on CIFAR-10, while the method also scales to ImageNet.Training required approximately 2.5 GPU hours on CIFAR-10 versus 15.4 GPU hours for [9].
- Proposed method: Structured ablation selects correlated pixels rather than independently sampled pixels, incorporating the contiguous-square structure of patch attacks.This adapts randomized ablation to the additional structure imposed by patches.
- Proposed method: Reducing the number of possible ablations makes exhaustive evaluation tractable, producing exact rather than probabilistic robustness certificates.The method can classify using all possible ablations and exactly evaluate class probabilities.
- Results: Derandomization removes estimation error, increasing reportable certified accuracies and enabling abstention by the base classifier.The abstention strategy substantially increased certificates on MNIST, but its effects on CIFAR-10 were not significant.
2 Certifiable Defenses against Patch Attacks
The method exploits patch structure by retaining correlated pixel groups rather than independently sampled pixels, reducing patch overlap while preserving classifier accuracy. Enumerating all structured ablations enables exact, deterministic certificates, with column or band smoothing generally performing best.
- Baseline: Sparse Randomized Ablation [16]: Patch attacks are treated as L0 attacks with ρ = m^2, but sparse randomized ablation certifies them poorly because it ignores their spatial structure.The baseline retains k independently selected pixels and bounds attack impact by the probability that retained pixels intersect the patch.
- Proposed Method: Structured Ablation: Structured ablation selects correlated pixel groups to reduce the probability ∆ that the adversarial patch is sampled.The proposed choices are square blocks and row or column bands.
- Proposed Method: Structured Ablation: Block smoothing retains an s × s block, of which (m + s − 1)^2 out of hw possible positions intersect an m × m patch.This structured selection substantially lowers patch-intersection probability compared with independently sampling the same number of pixels.
- Proposed Method: Structured Ablation: Band smoothing retains a width-s row or column, with m + s − 1 of w possible column positions intersecting an m × m patch.Column smoothing retains k = sh pixels, while row smoothing is analogous.
- Comparison to Conventional Randomized Smoothing: Structured ablation achieves higher certified accuracy than L0 randomized ablation because it maintains higher base-classifier accuracy at similar ∆, with band smoothing performing best empirically.Column smoothing is the strongest structured variant in the reported experiments.
3 Results
Structured ablation experiments show strong patch certificates, especially with column smoothing, while derandomization improves certified accuracy and empirical patch robustness exceeds an undefended baseline.
- Certified robustness: Column smoothing produces better certified results than block smoothing on MNIST and CIFAR-10.The comparison uses 5 × 5 patches and validation-set certificates.
- Ablation choices: Thresholding logits substantially improves MNIST certificates but has little effect on CIFAR-10.The difference may reflect that ablated MNIST images can contain no information, unlike natural images.
- Scaling patch size: High certified accuracy is maintained on CIFAR-10 even for 9 × 9 patches, with optimal column width apparently independent of patch size.This suggests one trained model can defend against a broad class of patch attacks.
- Derandomization: Derandomization improves certified accuracy independently of thresholding, increasing CIFAR-10 certified accuracy by nearly 7 percentage points.Table 2 compares derandomized and randomized column smoothing for 5 × 5 patches.
- Empirical robustness: On CIFAR-10, column smoothing is significantly more robust to empirical patch attacks than an undefended baseline, while certified lower bounds hold.The evaluation uses a modified IFGSM patch attack; the method has no robustness guarantee for the tested L∞ attack.
4 Conclusion
The paper proposes Structured Ablation as a provably robust defense against patch attacks, outperforming the prior certified defense on CIFAR-10 and scaling to ImageNet.
- Conclusion: Structured Ablation adapts randomized smoothing into a provably robust defense against patch attacks.The paper frames patch attacks as important because they formalize physical adversarial attacks.
- Conclusion: The method significantly outperforms the state-of-the-art certified patch defense on CIFAR-10 and scales to ImageNet.
Broader Impact
The paper highlights both potential benefits and risks of deploying provable defenses against physical-style patch attacks. These include improved protection in critical vision applications, possible misuse, and overconfidence in guarantees that do not cover all attacks or correctness.
- Patch attacks model physical manipulation of objects, including adversarial stickers on stop signs targeting autonomous-vehicle vision systems.
- The defense does not provide robustness to general adversarial attacks beyond patch attacks.
- A robustness guarantee does not guarantee correctness, and the classifiers’ accuracy is reduced compared with undefended models.
- The techniques could also be used by malicious actors, potentially making excessive or unwanted surveillance harder to thwart.
A Proofs
The proofs establish that block and column smoothing preserve the smoothed classifier’s prediction when an image changes within an m × m patch, provided the class-count margin exceeds the affected classifications.
- Block smoothing: Theorem 1 guarantees g(x′) = c when the base-classification count for c exceeds every competing class by the stated patch-dependent margin.
- Block smoothing: For block smoothing, a retained s × s block can intersect the patch only when both its row and column starts fall within m + s − 1 positions.
- Boundary handling: The proof handles image-boundary intersections through wrapping, preserving the same count of potentially affected positions.
- Column smoothing: Theorem 2 applies the analogous margin condition to column smoothing and guarantees g(x′) = c for any image differing within an m × m patch.
- Column smoothing: For column smoothing, only m + s − 1 possible retained-band positions can intersect the adversarial patch.
B Full Validation Result Tables for Column and Block Smoothing
The full validation results report clean and certified accuracies for 5 × 5 patch attacks on MNIST and CIFAR-10, and for 42 × 42 attacks on ImageNet.
- The validation tables cover all tested smoothing parameters and report both clean and certified accuracies for block and column smoothing on MNIST and CIFAR-10.
- For ImageNet, the validation results cover 42 × 42 patch attacks using column smoothing across all tested values of θ.
C Results for Row Smoothing
The supplementary results compare row smoothing with column smoothing and examine multi-band or multi-block variants, including their alignment, affected-region counts, and validation outcomes.
- Row smoothing: 45.32% validation certified accuracy was achieved by row smoothing on MNIST, versus 53.22% using column smoothing under 5 × 5 patch attacks.
- Multi-region smoothing: Multi-column and multi-block experiments evaluate intermediate designs that use several contiguous image regions rather than individual pixels or one band or block.
- Multi-region smoothing: Multiple retained blocks or columns are aligned to an upper-left grid so they do not overlap and the selection space remains manageable for derandomized smoothing.
- Multi-block smoothing: For block smoothing, an m × m patch overlaps at most (⌈(m − 1)/s⌉ + 1)^2 grid-aligned blocks; with m = 5 and s = 4, it overlaps exactly 4 blocks.
- Multi-block smoothing: The multi-block certification algorithm replaces the standard affected-classification bound with a bound based on the number of potentially affected retained-block selections.
- Multi-column smoothing: The corresponding column analysis bounds the number of affected bands by ⌈(m − 1)/s⌉ + 1 and uses selections that avoid those bands.
E Comparison with Randomized Structured Ablation
Derandomization improves certified accuracy over randomized structured ablation, with gains attributed both to eliminating estimation error and enabling abstention or multiple-class selection.
- Around 6 percentage points on MNIST and 7 percentage points on CIFAR-10 come from derandomization alone.These gains occur before applying the thresholding method.
- Derandomized structured ablation permits abstention or multiple-class selection without complicating estimation.It also eliminates estimation error relative to randomized certification.
- Thresholding provides a large additional improvement on MNIST but not on CIFAR-10.
F Sparse Randomized Ablation for Patch adversarial Attacks
Sparse randomized ablation can certify patch robustness, but it ignores patch geometry; the paper instead evaluates attacks against structured ablation through a differentiable soft surrogate and hard-classification checks.
- Applying sparse randomized ablation to 5 × 5 patches certifies arbitrary L0 attacks on up to 25 pixels rather than exploiting patch geometry.These certificates are probabilistic with 95% confidence.
- The structured-ablation attack uses a soft smooth classifier because the base classifier is non-differentiable with respect to the image.The base network's SoftMax-ed logits define the soft classifier used for optimization.
- The IFGSM patch attack randomly selects patches, optimizes each with unconstrained IFGSM, and retains only attacks that fool the final hard smoothed classifier.The most successful attack across optimization steps and random initializations is returned.
- Patch attacks use 80 random starts, 150 iterations per start, and step size 0.05.Pixels in the attacked region are uniformly randomly initialized.
- Evaluation and certification require evaluating each base classifier, so reported evaluation times also represent certification times.
H Evaluation Times
Evaluation times are reported using the hyperparameters that maximize certified accuracy for each method, with experiments run on NVIDIA 2080 Ti GPUs.
- Evaluation times use each method's optimal hyperparameters for maximizing certified accuracy.The experiments use NVIDIA 2080 Ti GPUs.
I Architecture and Training Details
The experiments use ablated-pixel input representations, dataset-specific neural architectures, and empirical randomized-smoothing confidence estimation.
- Ablated-pixel representations double the input channels from one to two for MNIST and from three to six for color images.
- MNIST uses a CNN with two convolutional and three fully connected layers, while CIFAR-10 and ImageNet use modified ResNet-18 and ResNet-50 architectures.
- Randomized smoothing certification uses 95% confidence, 1,000 samples to select the putative top class, and 10,000 samples to lower-bound its probability.Sparse randomized ablation on MNIST uses pretrained models from prior work.