{"ID":2841980,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.09834","arxiv_id":"2511.09834","title":"CertMask: Certifiable Defense Against Adversarial Patches via Theoretically Optimal Mask Coverage","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^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 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.","short_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 neu...","url_abs":"https://arxiv.org/abs/2511.09834","url_pdf":"https://arxiv.org/pdf/2511.09834v1","authors":"[\"Xuntao Lyu\",\"Ching-Chi Lin\",\"Abdullah Al Arafat\",\"Georg von der Brüggen\",\"Jian-Jia Chen\",\"Zhishan Guo\"]","published":"2025-11-13T00:33:01Z","proceeding":"cs.CV","tasks":"[\"cs.CV\",\"cs.AI\"]","methods":"[]","has_code":false}