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

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 (Patch-Cleanser) requires two rounds of masking and incurs O(n 2 ) 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 Im-ageNet, ImageNette, and CIFAR-10 show that CertMask improves certified robust accuracy by up to +13.4% over Patch-Cleanser, while maintaining clean accuracy nearly identical to the vanilla model.