# CertMask: Certifiable Defense Against Adversarial Patches via Theoretically Optimal Mask Coverage

arXiv: https://arxiv.org/abs/2511.09834 · HTML: https://mlsanity.com/paper/2511.09834/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 22 references that are in the map.
- First posted on arXiv 13 Nov 2025.

## Builds on (most cited first, 15 of 15)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [ResMLP: Feedforward networks for image classification with data-efficient training](https://mlsanity.com/paper/2105.03404/) (2021)
- [Generating Adversarial Examples with Adversarial Networks](https://mlsanity.com/paper/1801.02610/) (2018)
- [LaVAN: Localized and Visible Adversarial Noise](https://mlsanity.com/paper/1801.02608/) (2018)
- [(De)Randomized Smoothing for Certifiable Defense against Patch Attacks](https://mlsanity.com/paper/2002.10733/) (2020)
- [Improving Transferability of Adversarial Patches on Face Recognition with Generative Models](https://mlsanity.com/paper/2106.15058/) (2021)
- [PatchAttack: A Black-box Texture-based Attack with Reinforcement Learning](https://mlsanity.com/paper/2004.05682/) (2020)
- [Sparse-RS: a versatile framework for query-efficient sparse black-box adversarial attacks](https://mlsanity.com/paper/2006.12834/) (2020)
- [Adversarial Training against Location-Optimized Adversarial Patches](https://mlsanity.com/paper/2005.02313/) (2020)
- [Natural Color Fool: Towards Boosting Black-box Unrestricted Attacks](https://mlsanity.com/paper/2210.02041/) (2022)
- [Efficient Certified Defenses Against Patch Attacks on Image Classifiers](https://mlsanity.com/paper/2102.04154/) (2021)
- [Defensive Patches for Robust Recognition in the Physical World](https://mlsanity.com/paper/2204.06213/) (2022)
- [Decision-based Black-box Attack Against Vision Transformers via Patch-wise Adversarial Removal](https://mlsanity.com/paper/2112.03492/) (2021)
- [Revisiting Image Classifier Training for Improved Certified Robust Defense against Adversarial Patches](https://mlsanity.com/paper/2306.12610/) (2023)

## Built on by (most cited first, 2 of 2)

- [CertVLA: Certified Defense against Physical Visual Attacks for Vision-Language-Action Models](https://mlsanity.com/paper/2608.20791/) (2026)
- [Median Temporal Ensembling: Training-Free Robust Aggregation for Action-Chunked Visuomotor Policies](https://mlsanity.com/paper/2609.27167/) (2026)

## Abstract (arXiv)

Adversarial patch attacks inject localized perturbations into images to mislead deep vision models. These attacks can be physically deployed, posing serious risks to real-world applications. In this paper, we propose CertMask, a certifiably robust defense that constructs a provably sufficient set of binary masks to neutralize patch effects with strong theoretical guarantees. While the state-of-the-art approach (PatchCleanser) requires two rounds of masking and incurs O(n2) inference cost, CertMask performs only a single round of masking with O(n) time complexity, where n is the cardinality of the mask set to cover an input image. Our proposed mask set is computed using a mathematically rigorous coverage strategy that ensures each possible patch location is covered at least k times, providing both efficiency and robustness. We offer a theoretical analysis of the coverage condition and prove its sufficiency for certification. Experiments on ImageNet, ImageNette, and CIFAR-10 show that CertMask improves certified robust accuracy by up to +13.4% over PatchCleanser, while maintaining clean accuracy nearly identical to the vanilla model.