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

2025/11/13 by Lyu, Xuntao, Lin, Ching-Chi, Arafat, Abdullah Al +3
#Artificial Intelligence (cs.AI) #Computer Vision and Pattern Recognition (cs.CV) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2511.09834

Abstract

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(n²) 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.

Citations

• Revisiting Image Classifier Training for Improved Certified Robust Defense against Adversarial Patches
• Natural Color Fool: Towards Boosting Black-box Unrestricted Attacks
• Defensive Patches for Robust Recognition in the Physical World
• Decision-based Black-box Attack Against Vision Transformers via Patch-wise Adversarial Removal
• Improving Transferability of Adversarial Patches on Face Recognition with Generative Models
• ResMLP: Feedforward networks for image classification with data-efficient training
• Efficient Certified Defenses Against Patch Attacks on Image Classifiers
• An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale
• Sparse-RS: a versatile framework for query-efficient sparse black-box adversarial attacks
• PatchAttack: A Black-box Texture-based Attack with Reinforcement Learning
• (De)Randomized Smoothing for Certifiable Defense against Patch Attacks
• LaVAN: Localized and Visible Adversarial Noise
• Generating Adversarial Examples with Adversarial Networks
• Deep Residual Learning for Image Recognition

Related

• PatchGuard: A Provably Robust Defense against Adversarial Patches via Small Receptive Fields and Masking
• PatchGuard++: Efficient Provable Attack Detection against Adversarial Patches
• Certified Defenses for Adversarial Patches
• Architecture-agnostic Iterative Black-box Certified Defense against Adversarial Patches
• PatchCleanser: Certifiably Robust Defense against Adversarial Patches for Any Image Classifier