Paper deep dive
MRCert: Towards Post-deployment Patch Robustness Certification for Adversarially Patched Samples via Type-specific Masking
Qilin Zhou, Zhengyuan Wei, Haipeng Wang, Zhuo Wang, Shuo Liu, W. K. Chan
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 94%
Last extracted: 10/9/2026, 7:37:56 AM
Summary
The paper introduces MRCert, a novel masking-based certified recovery defender designed for post-deployment robustness certification against adversarial patches. Unlike existing methods that either degrade clean accuracy (smoothing-based) or fail to certify adversarially patched inputs (existing masking-based), MRCert uses a type-specific design to distinguish between benign and adversarially patched samples. It employs a nested label recovery function and corresponding certification functions to verify label benignity and maintain high prediction accuracy. Experimental results on ImageNet demonstrate that MRCert achieves 35.1% adversarial certified accuracy at a 16-pixel patch size, significantly outperforming the state-of-the-art PatchCURE.
Entities (7)
Relation Signals (6)
MRCert → isa → Masking-based
confidence 98% · We propose MRCert, the first masking-based certified recovery defender
MRCert → targets → Adversarial Patch
confidence 97% · Towards Post-deployment Patch Robustness Certification for Adversarially Patched Samples
MRCert → achievesmetric → 35.1% adversarial certified accuracy
confidence 95% · MRCert achieves 35.1% adversarial certified accuracy on ImageNet
MRCert → outperforms → PatchCURE
confidence 95% · MRCert achieves 35.1% adversarial certified accuracy on ImageNet at patch size 16 pixels, whereas the SOTA PatchCURE fails completely.
Smoothing-based → haslimitation → degraded_clean_accuracy
confidence 90% · smoothing-based ones suffer from degraded correctness due to their smoothing mechanisms
Masking-based → haslimitation → cannot_certify_adversarial
confidence 90% · Masking-based ones rely on assumptions about the input’s benignity and fail to certify any adversarially patched samples
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:In post-deployment time, inputs to deep learning models may or may not be adversarially patched. Patch robustness certification on such inputs within a patch bound can verify their label benignity and should retain high prediction accuracy. However, existing smoothing-based and masking-based recovery defenders cannot achieve both simultaneously: they degrade the prediction accuracy much and cannot verify the benignity of the returned label of an adversarially patched input, respectively. We propose MRCert, the first masking-based certified recovery defender that shows the feasibility of achieving both. Unlike all existing works to apply a common condition across both types of input (benign and adversarially patched samples) for certification, MRCert infers type-specific necessary properties of deep learning models for both types in post-deployment time and formally relates them to verify the label benignity through a novel type-oriented design of label recovery and certification function pair. Without incurring the degradation in clean accuracy caused by smoothing, experimental results confirm that MRCert achieves 35.1\% adversarial certified accuracy on ImageNet at patch size 16 pixels, whereas the SOTA PatchCURE fails completely.
Tags
Links
- Source: https://arxiv.org/abs/2610.10617v1
- Canonical: https://arxiv.org/abs/2610.10617v1
Trouble viewing inline? Open PDF directly →
Full Text
66,052 characters extracted from source content.
Expand or collapse full text
MRCert: Towards Post-deployment Patch Robustness Certification for Adversarially Patched Samples via Type-specific Masking Qilin Zhou 1 , Zhengyuan Wei 2 , Haipeng Wang 1 , Zhuo Wang 1 , Shuo Liu 1 , W.K. Chan 1,∗ 1 City University of Hong Kong 2 The Education University of Hong Kong ∗ Corresponding author Abstract In post-deployment time, inputs to deep learning models may or may not be adversarially patched. Patch robustness certification on such inputs within a patch bound can verify their label benignity and should retain high prediction accuracy. However, existing smoothing-based and masking-based re- covery defenders cannot achieve both simultane- ously: they degrade the prediction accuracy much and cannot verify the benignity of the returned la- bel of an adversarially patched input, respectively. We propose MRCert, the first masking-based cer- tified recovery defender that shows the feasibility of achieving both. Unlike all existing works to ap- ply a common condition across both types of in- put (benign and adversarially patched samples) for certification, MRCert infers type-specific necessary properties of deep learning models for both types in post-deployment time and formally relates them to verify the label benignity through a novel type- oriented design of label recovery and certification function pair. Without incurring the degradation in clean accuracy caused by smoothing, experimen- tal results confirm that MRCert achieves 35.1% ad- versarial certified accuracy on ImageNet at patch size 16 pixels, whereas the SOTA PatchCURE fails completely. 1 Introduction Deep learning (DL) systems have achieved remarkable suc- cess in many application domains, including those safety- critical [ Kuutti et al., 2021; Litjens et al., 2017 ] ; yet their vulnerability to adversarial attacks [ Szegedy et al., 2013 ] , in- cluding those physically realizable attacks like a sticker [ Wei et al., 2023b ] or a tag [ Liu et al., 2020 ] in the real world, poses significant threats to their deployment, e.g., commer- cial autonomous vehicles [ Wang et al., 2025 ] . Patch adver- sarial attack [ Brown et al., 2017; Wei et al., 2024 ] is a model of physically realizable attacks, where attackers can arbitrar- ily manipulate pixels within a certain region of an image (re- ferred to as a patch region) to compromise DL systems. Deterministic certified defenders are emerging. Among them, certified recovery against patch attacks [ Levine and Feizi, 2020a; Metzen and Yatsura, 2021; Li et al., 2022; Xiang et al., 2022; Salman et al., 2022; Zhou et al., 2023; Zhou et al., 2024; Xiang et al., 2024 ] , as a major line of patch robustness certification, aims to ensure the recovery of benign labels from all patched neighbors of certified benign samples. These existing defenders are predominantly designed to offer pre-deployment provable patch robustness for benign sam- ples. In practice, it is desirable to provide a certification on input samples for certified recovery at post-deployment time, especially when an input may already be corrupted, where an issued certificate indicates that the label returned by the label recovery function for the input sample is robust and benign, so that downstream tasks can take informed actions. However, current certified recovery defenders, includ- ing both masking-based [ Xiang et al., 2024; Xiang et al., 2022 ] and smoothing-based methods [ Salman et al., 2022; Li et al., 2022 ] , fall short in this regard. Masking-based ones rely on assumptions about the input’s benignity and fail to certify any adversarially patched samples of certified benign samples (illustrated in Fig. 1 and formalized in § 3), while smoothing-based ones suffer from degraded correctness due to their smoothing mechanisms [ Xiang et al., 2023 ] . To address these limitations, we propose MRCert, the first certified recovery defender that provides a type-specific ro- bustness certification crosscutting with its type-specific label recovery function, able to certify different types of input sam- ples in post-deployment time. MRCert can distinguish among benign, patched, and double-patched inputs with different re- covery strategies on them in a type-specific manner. It is able to not only recover the benign label for adversarially patched samples of certified benign samples (like its peers) but also assign a provable certificate indicating whether the label re- turned by the recovery function for the input sample is robust and benign. The type-specific design of MRCert enables it to certify both benign and adversarial samples, overcoming the fundamental limitations of peers. In addition to maintain- ing a high certified accuracy and clean accuracy on benign samples, the experiment shows that MRCert achieves a non- trivial round-trip certified accuracy, which is further validated on patched samples from actual attacks. The main contribution of this paper is twofold. (1) The paper proposes MRCert and proves its soundness. (2) It val- idates MRCert’s high effectiveness in certifying benign and adversarial samples while maintaining high accuracy. arXiv:2610.10617v1 [cs.CR] 7 Oct 2026 푥" 푥 Benign? Type-specific Masking- based Analysis FixedCertification Proven : FixedCertification alwaysfails 푥 Benign? Others? Certification designed for x 푥′ (Single-) Patched? Certification designed for x′ ...... Guaranteed by Round-trip Certification Abstain Classical Masking- based Analysis Prediction on 푥,is robust and benign 푥" 푥′ Not benign? Prediction on 푥 ,is robust and benign Input (including different types) Input (including different types) Figure 1: Post-deployment certification in classical masking-based analysis vs our type-specific masking-based analysis. 2 Preliminaries We first summarize the main notation we use. • x: a benign sample • x ′ : x’s patched sample • ˆx: an input sample • f : a base classification model • c r : a certification function • g: a label recovery function • P: a patch region • P: a patch region set • M: a mask • ˆx⊙ M: a mutant of ˆx • M P : a covering mask set • y 0 : the true label • A P (.): all patched neigh- bors 2.1 Patch attacks and Certified Recovery Model and Patch An image classifer is a function f : X → Y , which takes ˆx ∈ X ⊂ R w×h (with its true class label y 0 ∈ Y = 0,· ,|Y|− 1) as input and produces a label f(ˆx) ∈ Y . A patch in a sample is modeled to reside within a contigu- ous square patch region, represented by a binary matrix P ∈ P ⊂ 0, 1 w×h , where 1s indicate the region and 0s elsewhere. The set P includes all patch regions satisfy- ing predefined conditions (e.g., shape, size). We use the at- tack constraint set A P (x) to define all patched neighbors (in terms of one patch by default) of a benign sample x: A P (x) = x ′ | x ′ = (J − P)⊙x + P⊙x ′ ∧ P ∈ P. Here, x ′ is a patched neighbor of x with possible pixel modifica- tion inside P (P⊙x ′ ) while keeping those outside unmodified ((J − P)⊙x). ⊙ denotes element-wise multiplication, and J is an all-ones matrix. Like prior certification works, our the- oretical model focuses on robustness but not correctness and assumes f(x) = y 0 when certifying x. The sample x ′ is adversarially patched if f(x ′ ) ̸= f(x). Note that a benign sample is a trivial (non-modified) patched neighbor of itself. In this work, we build our theory on top of the assumption like [ Yatsura et al., 2023 ] that the post-deployment input do- main consists of benign samples and their patched neighbors. Certified Recovery A certified recovery defender R = ⟨g, c r ⟩ is built on a base classifier f . The label recovery function g provably returns the prediction of a benign sample x for any patched neigh- bor x ′ of x, i.e., g(x ′ )=g(x) if x is certified by c r , i.e., [∀x ′ ∈A P (x), c r (x) =True =⇒ g(x ′ )=g(x)]. Given a be- nign sample x, an attacker aims to find a patched neighbor x ′ , such that g(x ′ )̸= g(x). 2.2 Post-deployment Robustness Certificate [ Yatsura et al., 2023 ] proposes a post-deployment robust- ness certificate for certified patch recovery: Since x ∈ A P (ˆx), one must have g(ˆx)=g(x) if c r (ˆx)=True (i.e., [∀ˆx ′ ∈ A P (ˆx), g(ˆx ′ )=g(ˆx)]) holds, indicating that the prediction g(ˆx) must be robust and further benign. Problem: Existing defenders are either inapplicable to provide such a certificate whenever inputs are adversarially patched samples of certi- fied samples [ Xiang et al., 2024 ] or able to provide but less accurate for benign samples [ Salman et al., 2022 ] (see §3), limiting their applicability to provide the certificate in post- deployment time. 2.3 Masking-Based Certified Recovery A mask M ∈ M P ⊂ 0, 1 w×h ablates a specific region from a sample (0 for mask, 1 otherwise). The covering mask set M P [ Xiang et al., 2024 ] ensures any patch P ∈ P is fully enclosed by some mask M ∈ M P , i.e., ∀P ∈ P,∃M ∈ M P , P⊙M =O (an all-zero matrix). Ablating ˆx with k ∈ 1, . . . , 4 masks from M P produces a k-th order mutant, denoted as ˆx⊙m 1 ⊙ . . .⊙m k (Fig. 2 for k=1). Re-applying the same mask to a mutant trivially yields a higher-order one. A masking-based certified detection defender [ Huang et al., 2023 ] raises a warning if any first-order mutant of an in- put ˆx deviates from its original prediction (called divergent mutant), i.e.,∃M ∈ M P such that f(ˆx⊙M)̸= f(ˆx). Extending this, a certified recovery defender R = ⟨g, c r ⟩ seeks to recover the benign prediction of x ′ [ Xiang et al., 2024 ] : g generates all second-order mutants of x for such divergent mutants to test them and returns the prediction of a divergent mutant if all of them and the divergent mu- tant yield the same prediction. If no such divergent mutant is identified at either stage, g returns f(ˆx). This mecha- nism is formalized by the following theorem: [∀M 1 , M 2 ∈ M P , f(x⊙ M 1 ⊙ M 2 ) = y 0 ] =⇒ [∀x ′ ∈ A P (x),∃M 1 ∈ M P ,∀M 2 ∈ M P , f(x ′ ⊙M 1 ⊙M 2 ) = y 0 ], where the antecedent serves as the certification function, and the consequent yields prediction as described above. 3 Motivation and Challenges Post-deployment robustness certification for benign samples and their patched samples is highly desirable. Such a for- mal guarantee empowers users to substantially augment au- tomation in safety-critical scenarios for those certified by es- tablishing a provable basis for trust. One needs a defender to certify input samples with uncertainty about their benig- nity while maintaining high clean accuracy. However, both smoothing-based and masking-based certified recovery have their own limitations and challenges in achieving the goal. Masking-based Recovery. To handle inputs with unknown groundtruth y 0 at post-deployment time, we follow [ Huang et al., 2023 ] to replace y 0 with f(x) in the certification in [ Xiang et al., 2022 ] : c r (ˆx) := [∀M 1 , M 2 ∈ M P , f(ˆx⊙M 1 ⊙M 2 ) = f(ˆx)]. However, we find that no adversarially patched sample of a certified sample x ′ by this c r can be further certified. Property 1 (Infeasibility of Re-certifying Adversarially Patched Samples for Existing Masking-based Recovery Works). ∀x ′ ∈ A P (x), c r (x)∧ f(x ′ )̸= f(x) =⇒ ¬c r (x ′ ). 푥" 푥 푥′ x x’∈ 픸(x)픸(x) 픸(x’) x Unknown input Benign Patched x’∈ 픸(x) x 픸(x) 픸 ! (x) 픸 (x’) Recovery: Case ① 2 Masks Recovery: ¬ Case ① 2 Masks Recovery: Case ② 1+2 Masks g푥 0 ≔f(푥 0 ⊙푚 ! ) Recovery: ¬Case ② 1+2 Masks 푥′ Double Patched (abstain from certification) Recovery: Case ③ 2+2 Masks Recovery: ¬Case ③ 2+2 Masks Recovery: abstain Case ④ g푥0≔f(푥0) Certification: Case ⑥ 1+3 Masks x’∈ 픸 (x’) Guarantee: g( 풙 $ ) = g( 푥 ’)= g( 푥 )=f( 푥 ) Certification: Case ⑤ 3 Masks Guarantee: g( 푥′ )=g( 푥 )=f(x) Existing masking-based recovery’s certificate Certification: Case ⑦ 4 Masks MRCert’sCertificate post-deployment Guarantee: 푐 " 푥 # ∧ g(푥′)=g(푥)=f(x) (guarantee the success of certification on all patched samples) Route to theoretical analysis Route to algorithmic recovery g푥 0 ≔ f(푥 0 ⊙푚 ! ⊙푚 $ ) MRCert’s Round-trip Certificate for assessment attack adversarial patch patch region p maskingbya maskm harmfulx’benignx first order mutantx⊙m first order mutantx’⊙m = maskm first-order ...... input second-order ...... Assume Assume Assume g푥 0 ≔f(푥 0 ) Figure 2: The basic concepts in masking-based defenders (right) and the illustration of MRCert (left). See Fig. 3 for their formulation. Idea of proof. If c r (x) is satisfied, all its first-order mu- tants predict f(x). Since x ′ shares a first-order mutant with x but f(x ′ ) ̸= f(x), it cannot satisfy the prediction consensus required for c r (x ′ ). See the formal proof in the appendix. Smoothing-based recovery. Smoothing is known to seri- ously degrade clean accuracy on non-trivial datasets like Im- ageNet [ Mohapatra et al., 2021 ] , including those for patch attacks [ Xiang et al., 2023 ] . Previous works have proposed an empirical masking-based detection method atop smooth- ing, but the improvement in clean accuracy is only marginal (e.g., 0.8% on CIFAR10 in [ Xiang et al., 2021 ] ). 4 Methodology 4.1 Overview of MRCert Fig.2 depicts an overview of our certified recovery defender, MRCert R = ⟨g, c r , c 2 r ⟩, formulated in Fig. 3. The label re- covery function g(ˆx) returns a label structured as a nested- if sequence: if 1 ⃝ elseif 2 ⃝ elseif 3 ⃝ else 4 ⃝. The certification function c r (ˆx) (cases 5 ⃝– 6 ⃝) verifies if g’s output remains invariant for ˆx and all neighbors in A P (ˆx). Our setting involves patched neighbors not present in the clean dataset. Since computing the full set of patched neigh- bors is intractable, we provide provable assessments that map to the clean dataset, formulated as c 2 r in case 7 ⃝. At post-deployment, MRCert is configured with a base model f , accepts an input ˆx, and applies g and c r on the input to return a label and a certification verdict on robustness. MRCert treats benign samples (including those benignly patched) and their adversarially patched neighbors as distinct input types. It infers the type-specific necessary properties of f for these two types that can be detected, recovered, and cer- tified, and links up these properties through a type-oriented design: For benign samples, it detects through case 1 ⃝, certi- fies through case 5 ⃝ if case 1 ⃝ holds; for adversarially patched neighbors of benign samples, it detects through the violations of 1 ⃝ and further detects and recovers through case 2 ⃝, and certifies through case 6 ⃝. In the theoretical model of an input ˆx being either benign or patched, even if the input is adversar- ially patched, c r (ˆx) can hold true to indicate that g(ˆx) must return a benign label. Existing masking-based defenders can- not offer this property. Also, if case 7 ⃝ holds, then all the conditions for the above certification, detection, and recovery will be guaranteed to hold, as depicted by the solid arrows in Fig. 2 (and the hollow arrows depict cases 1 ⃝– 4 ⃝ of g). Swapping the order of cases 1 ⃝– 4 ⃝ in g will make case 7 ⃝ for round-trip certification fail (see the appendix for discussion). 4.2 Needs in Certifying Adversarial Samples In the theoretical model of certified recovery subject to post- deployment certification, the input is either benign x or patched x ′ . To certify the robustness of an adversarially patched neighbor x ′ of x, the certification analyzer must an- alyze all neighbors in A P (x ′ ), which may contain up to two patches relative to x, including x itself (clean), x ′ (patched), and double-patched instances. The fundamental limitation of existing masking-based peers [ Xiang et al., 2022; Xiang et al., 2024 ] stems from using the fixed-masking paradigm: By design, their g and c r always apply a fixed number of masks to each input regardless of their patch count, forcing them to test the consistency of the predictions from the in- put’s mutants under the same condition formulation. To de- fend two patches, such a defender must scale its number of masks: (a) g must generate second-order mutants for detec- tion; (b) recovery requires fourth-order mutants to resolve a second-order divergent mutant. This change can only ex- tend the guarantee for x against the expanded set A 2 P (x) = S x ′ ∈A P (x) A P (x ′ ), and remains unable to certify x ′ ∈ A P (x). Their core bottleneck is over-approximation: To recover x ′ , their common theoretical model treats every input and its patched neighbors as double-patched instances; therefore, to certify x ′ , it must be further modified into yet another Patch- cleanser variant to defend against four patches, creating an unresolvable “cat-and-mouse” recursion. So, any fixed-mask configuration is fundamentally unable to certify x ′ . 4.3 Type-Specific Label Recovery Function The primary challenge in designing g lies in the agnostic nature of the input types: the mechanism must certify both types of input, x and x ′ ∈ A P (x), without prior knowledge of g(ˆx) := f(ˆx),if∀M 1 , M 2 ∈ M P , f(ˆx⊙ M 1 ⊙ M 2 ) = f(ˆx)(case 1 ⃝) f(ˆx⊙ M 1 ),else if∃M 1 ∈ M P ,∀M 2 , M 3 ∈ M P , f(ˆx⊙ M 1 ⊙ M 2 ⊙ M 3 ) = f(ˆx⊙ M 1 )(case 2 ⃝) f(ˆx⊙ M 1 ⊙ M 2 ), else if∃M 1 , M 2 (̸= M 1 )∈ M P ,∀M 3 , M 4 ∈ M, f(ˆx⊙ M 1 ⊙ M 2 ⊙M 3 ⊙ M 4 ) = f(ˆx⊙ M 1 ⊙ M 2 ) (case 3 ⃝) f(ˆx),otherwise(case 4 ⃝) certificatec r (ˆx) := [∀M 1 , M 2 , M 3 ∈ M P , f(ˆx⊙M 1 ⊙M 2 ⊙M 3 ) = f(ˆx)]if case 1 ⃝ is taken in g [∃M 1 ∈ M P ,∀M 2 , M 3 , M 4 ∈ M P , f(ˆx⊙M 1 ⊙M 2 ⊙M 3 ⊙M 4 ) = f(ˆx⊙M 1 )]if case 2 ⃝ is taken in g (case 5 ⃝) (case 6 ⃝) round-trip certificatec 2 r (ˆx) := n [∀M 1 , M 2 , M 3 , M 4 ∈ M P , f(ˆx⊙ M 1 ⊙ M 2 ⊙ M 3 ⊙ M 4 ) = f(ˆx)](case 7 ⃝) Figure 3: The formulation of each component of MRCert. the patch count in an input. Under the above fixed-masking paradigm, certifying a benign sample x requires the label con- sistency across all its fourth-order mutants. Let us first adopt this property for x to discuss the design of our g. Our g follows a conditional pipeline to resolve issues aris- ing from different input types as discussed in §4.2. In Case 1 ⃝, g screens ˆx using second-order mutants to detect adver- sarial patches, ensuring that double-patched samples cannot evade the detection. Then, the core question is: How should g be designed to discriminate the number of adversarial patches in ˆx after the above detection procedure? Our first insight is that testing all first-order mutants of ˆx by the prediction consistency of the third-order mutants of ˆx not only exposes which of these first-order mutants that f re- turns the benign label, but also indicates whether ˆx contains a single (adversarial) patch. We refer to it as indirect testing of adversarially patched samples. The elegance of this test lies in its dual roles: while identifying and recovering the la- bels for inputs with one patch, at the same time, it detects inputs that have more than one patch by the consistency of third-order mutants, thereby precluding any evasion attempts of double-patched neighbors if g naively uses two masks (just like [ Xiang et al., 2022 ] ) for inputs with one patch to recover its label, since the first mask may miss the patch. So, g identi- fies ˆx to be x ′ ∈ A P (x) based on this indirect testing, enabling certified recovery in Case 2 ⃝. It solves the problem of testing ˆx that directly uses a test suite consisting of either the set of all first-order mutants or the set of all second-order mutants, which either fails to ensure the robustness guarantee on ˆx, or is too coarse in detection granularity. To our knowledge, MRCert is the first work that is able to detect the number of patches on an adversarial input sample with a guarantee if its benign counterpart is round-trip certified (see §4.4). Thus, if ˆx is detected as an adversarially patched sample in Case 1 ⃝ but not detected as a sample with one patch in Case 2 ⃝, g deems it as a sample with two (or more) adversarial patches. MRCert abstains from verifying its robustness, and g adopts the existing recovery on double-patched samples in Case 3 ⃝ as a best effort attempt. If all these test efforts cannot find a label to return, Case 4 ⃝ returns the original prediction. We will present the formal guarantee in §4.4. The appendix provides further justifications for our design choices, includ- ing the necessity of the current sequence and mask quantity. 4.4 Post-deployment Type-specific Certification and Round-trip Certification for Assessment Building upon the proposed type-oriented recovery mech- anism, we formalize the robustness certification conditions for MRCert against both benign samples and adversarially patched neighbors. First, to ensure that an adversarial sample x ′ (with one patch) is caught by Case 1 ⃝ of g, we must guarantee the existence of at least one second-order mutant of x ′ whose predicted label differs from that of x ′ . By definition, we know f(x ′ ) ̸= f(x). If x and all its first-order mutants share the same prediction, then the predictions for first-order mutant of x ′ that masks the adversarial patch will revert to f(x), further differing from f(x ′ ), which is detected by Case 1 ⃝. Formally, we require [∀M 1 ∈ M P , f(x⊙M 1 ) = f(x)] =⇒ [∀x ′ ∈ A P (x), f(x ′ ) ̸= f(x) =⇒∃M 1 ∈ M P , f(x ′ ⊙M 1 ) ̸= f(x ′ )] holds. Next, to recover the benign labels for all x ′ ∈ A P (x)), we must ensure that they are correctly identified under Case 2 ⃝ of g.Since the specific mask M 1 required to neutralize the adversarial patch is unknown a priori, we formulate a consistency requirement: for every first-order mutant, the entire set of its corresponding third-order mutants must yield a prediction identical to that of the first- order mutant itself. Formally, we require [∀M 1 , M 2 , M 3 ∈ M P , f(x⊙M 1 ⊙M 2 ⊙M 3 )=f(x⊙M 1 )] =⇒ [∃M 1 ∈M P ,∀M 2 , M 3 ∈M P , f(x ′ ⊙M 1 ⊙M 2 ⊙M 3 )=f(x ′ ⊙M 1 )] holds.A certified sample is required to satisfy the antecedents of both, en- suring being detected in Case 1 ⃝ and recovered in Case 2 ⃝ for all of its adversarially patched samples.By substi- tuting the input as ˆx, we derive: [∀M 1 , M 2 , M 3 ∈ M P , f(ˆx⊙M 1 ⊙M 2 ⊙M 3 )=f(ˆx)].This is Case 5 ⃝, which we formally define it in Lemma 1. The robustness and benignity of an input sample in Case 1 ⃝ of g can be verified through it. Lemma 1 (Certification of benign samples). Given an arbi- trary sample ˆx, if [∀M 1 , M 2 , M 3 ∈ M P , f(ˆx⊙M 1 ⊙M 2 ⊙M 3 ) = f(ˆx)] holds,∀ˆx ′ ∈ A P (ˆx), g(ˆx ′ ) = g(ˆx). Our second insight is that the certification function should also be type-specific and crosscutting the label recovery func- tion on a type-specific basis, rather than type-agnostic and acting purely as a downstream task of the label recovery func- tion. In previous patch robustness certification paradigms, a certification function is agnostic in input type (see §2.3) and relates to the output of a label recovery function with- out knowing the execution path condition that produces the output. However, it is not optimal for masking-based defend- ers to handle the situation where benign samples and their adversarially patched samples are subject to robustness cer- tification (see §3), which requires different treatments (see §4.2). Therefore, we design our certification and label re- covery function pair to correspond to each other in a type- specific manner. To certify a adversarially patched sample as input, we need to ensure that the returned label remains the same across the input and all its patched neighbors, where double-patched samples should be included. Samples with two adversarial patches are expected to be detected by vio- lating the condition of Case 2 ⃝ and their labels are recovered in Case 3 ⃝ in the design of g presented in §4.3. To ensure achieving such a goal, x ′ should have a first-order mutant (denoted as x ′ ⊙M 1 ), whose all fourth-order mutants are pre- dicted with the same prediction f(x ′ ⊙M 1 ) (which should be the same as g(x ′ ), the return prediction of x ′ , by the condi- tions in Case 1 ⃝ and Case 2 ⃝). With such a condition, for all double-patched samples (denoted as x ′ ) of this adversari- ally patched sample (i.e., putting another patch on this adver- sarially patched sample), there should have a second-order mutant of x ′ (denoted as x ′ ⊙M 1 ⊙M 2 ) generated from this first-order mutant x ′ ⊙M 1 (=x ′ ⊙M 1 ) with the second mask M 2 covering the new patch in the input, and f predicts the same label for this second-order mutant x ′ ⊙M 1 ⊙M 2 and all fourth- order (and third-order) mutants generated from this second- order mutant. So, all adversarially double-patched samples x ′ (i.e., whose attacker aims to make g(x ′ ) ̸= g(x ′ ) where x ′ ∈A P (x ′ )) should meet the following three conditions: (1) x ′ must violate the condition in Case 1 ⃝ because at least one second-order mutant x ′ ⊙M 1 ⊙M 2 predicts to g(x ′ ); (2) x ′ must violate the condition in Case 2 ⃝ because all third- order mutants of x ′ ⊙M 1 ⊙M 2 predicts to g(x ′ ); and, (3) x ′ must satisfy the condition in Case 3 ⃝ by x ′ ⊙M 1 ⊙M 2 and all fourth-order (and third-order) mutants generated from this second-order mutant predicted to g(x ′ ), and further output the label of x ′ ⊙M 1 ⊙M 2 , which is g(x ′ ). Similarly, by substitut- ing the symbol ˆx for x ′ , it is captured as Lemma 2 and as the condition of Case 6 ⃝, where the robustness and benignity of an input sample in Case 2 ⃝ of g can be verified. Lemma 2 (Certification of adversarially patched samples). Given an sample ˆx, if [∃M 1 ∈ M P ,∀ M 2 ,M 3 ,M 4 ∈ M P , f(ˆx⊙ M 1 ⊙ M 2 ⊙ M 3 ⊙ M 4 ) = f(ˆx ⊙ M 1 )] holds, [∀ˆx ′ ∈ A P (ˆx), g(ˆx ′ ) = g(ˆx)] holds. In short, the labels for a sample x of the benign type and its patched neighbors are recovered through Case 1 ⃝ and either Case 1 ⃝ (for benign patch) or 2 ⃝ (for adversarial patch), re- spectively. Similarly, these for an adversarial sample with one patch and its patched neighbors are recovered through Cases 2 ⃝ and Cases 1 ⃝– 3 ⃝, respectively. With these two conditions (shown as cases 5 ⃝ and 6 ⃝ in Fig. 3), we get MRCert’s certification function by Thm. 1. Theorem 1 (Certification of samples). Given an arbitrary sample ˆx, if [∀M 1 , M 2 , M 3 ∈ M P , f(ˆx⊙M 1 ⊙M 2 ⊙M 3 ) =f(ˆx)] ∨ [∃M 1 ∈M P ,∀M 2 , M 3 , M 4 ∈ M P , f(ˆx⊙M 1 ⊙M 2 ⊙M 3 ⊙M 4 )=f(ˆx ⊙M 1 )]holds(i.e., Table 1: Results of smoothing-based recovery defenders on clean ImageNet test set with patch size 32 pixels (in %). Defenderacc clean acc cert S-ViT [ Salman et al., 2022 ] 69.338.3 ViP [ Li et al., 2022 ] 70.841.4 VOT [ Zhou et al., 2024 ] 71.441.2 c r (ˆx) = True),∀ˆx ′ ∈A P (ˆx), g(ˆx ′ ) = g(ˆx). If a benign sample and all its patched samples can be cer- tified [ Yatsura et al., 2023 ] , it is called round-trip certified. Suppose c r certifies a benign sample x itself. Then if all its patched samples are guaranteed to satisfy the antecedent of Thm. 1 to be certified, x is round-trip certified. For masking- based defenders, since it is unknown which mask will cover the patch in a patched sample created from a benign sample, to make the patched sample fulfill the antecedent of Thm.1 that it has a first-order mutant, whose all four-order mutants generated from this mutant are predicted with the same la- bel as this first-order mutant, we also need to make sure that all first-order mutants of the benign sample x fulfill this an- tecedent, which is captured by Thm. 2. Theorem 2 (Round-trip certification of benign samples). Given a benign sample x, if [∀M 1 , M 2 , M 3 , M 4 ∈ M P , f(x⊙ M 1 ⊙M 2 ⊙M 3 ⊙M 4 ) = f(x)] holds (i.e., c 2 r (x) = True), [∀x ′ ∈ A P (x), g(x ′ ) = g(x)∧ c r (x ′ ) = True∧ c r (x) = True] holds. c 2 r adopts the antecedent of the round-trip certification the- orem (case 7 ⃝ in Fig. 3), which ensures x and all its patched samples fulfill Thm. 1. It aligns with the certification condi- tion against two patches by the Patchcleanser variant in §3. Formal proofs and the extension of MRCert to handle up to N patches are provided in the appendix. 5 Evaluation 5.1 Experimental Setup Environment and Dataset The evaluation is run on an Ubuntu 20.04 machine equipped with four Nvidia 3090 GPUs. Following [ Xiang et al., 2022 ] , we adopt 1000-class Image-Net [ Deng et al., 2009 ] , 10-class CIFAR10 [ Krizhevsky et al., 2009 ] , and 10-class ImageNette as our datasets. All samples are resized to 224X224 pixels. Models and Baselines We adopt the Vision Transformer (ViT) as our base model, which achieves the state-of-the-art in many patch robustness certification defenders [ Xiang et al., 2024; Li et al., 2022; Salman et al., 2022; Xiang et al., 2022; Huang et al., 2023 ] . We adopt the state-of-the-art masking-based defender PatchCURE (PC) [ Xiang et al., 2024 ] and state-of-the- art smoothing-based defender VOT-CrossCert (VOT) from CrossCert [ Zhou et al., 2024 ] . We arm VOT with the method- ology proposed by [ Yatsura et al., 2023 ] for post-deployment certification for smoothing-based defenders to compare with MRCert in our infrastructure. They share the same PC’s ViT-SRF as the base model. We extract the results of peer smoothing-based recovery defenders from [ Li et al., 2022 ] and [ Salman et al., 2022 ] to compare with VOT in Table 1. Table 2: Results on D pat (patched samples from a real attack) with patch sizes of 16 pixels and 32 pixels (in %). Patch size16 pixels32 pixels DefenderMRCertPCBaseMRCertPCBase Metricsacc clean acc cert acc adv cert acc clean acc cert acc adv cert acc clean acc clean acc cert acc adv cert acc clean acc cert acc adv cert acc clean ImageNet62.444.235.167.612.80.014.649.024.824.862.20.00.00.0 ImageNette97.493.888.198.442.00.054.695.280.280.298.00.00.00.0 CIFAR1093.077.441.594.461.00.067.282.446.846.691.00.20.00.8 Table 3: Results on ImageNet benign samples with patch size 16 (upper) and 32 (bottom) pixels (in %). DatasetImageNet Patch Size16 pixels Metricsacc clean acc cert acc cert 2 VOT71.450.930.5 PC81.663.5⊕ MRCert81.357.838.7 Patch Size32 pixels Metricsacc clean acc cert acc cert 2 VOT71.441.212.1 PC81.453.4⊕ MRCert81.339.515.6 Note: ⊕=theoretically infeasible Metrics Let x be a benign sample with the true label y 0 in a clean test dataset D, and R = ⟨g(x), c(x), c 2 r (x)⟩ be a certified recovery defender. We adopt clean accuracy acc clean = |x∈D|g(x)=y 0 | /|D|, which evaluates the standard performance of certified recovery as a classifier, certified accuracy acc cert = |x∈D|g(x)=y 0 ∧c r (x)=True| /|D|, and round-trip cer- tified accuracy acc cert 2 = |x∈D|g(x)=y 0 ∧c 2 r (x)=True| /|D| as our metrics.The clean accuracy of the base classifica- tion model f is |x∈D|f(x)=y 0 | /|D|. Existing works com- monly adopt the first two metrics, and round-trip certified accuracy is proposed in [ Yatsura et al., 2023 ] . For RQ1, D is a set of patched samples (including benignly and ad- versarially patched, one per benign) obtained by attacking 500 random benign samples using the procedure adopted from [ Levine and Feizi, 2020a ] , denoted as D pat . We mea- sure each defender’s ability to certify adversarially patched samples by adversarial certified accuracy acc adv cert = |ˆx∈D pat |g(ˆx)=y 0 ∧c r (ˆx)=True∧f(ˆx)̸=y 0 | /|ˆx∈D pat |f(ˆx)̸=y 0 |. The appendix presents more details on our setup. 5.2 Experimental Results and Data Analysis RQ1: How well does MRCert empirically provide a robustness certificate at post-deployment time? Table 2 summarizes the results of the masking-based defend- ers (MRCert and PC) on D pat . For fairness, we only compare PC and MRCert against this empirical attack. The left of Table 2 shows the results when the patch size is 16 pixels. Maintaining high accuracy across a mixture of benign and adversarial patches simulates the complexity of real-world post-deployment, where defenders must simul- taneously handle natural perturbation and powerful attacks. Although MRCert’s acc clean is lower but close to PC’s, it achieves much higher acc cert at a 16-pixel patch size by 3.45x, 2.23x, and 1.27x on ImageNet, ImageNette, and CI- FAR10, respectively, underscoring its robust certification ca- pability for post-deployment scenarios. Specifically, MRCert can guarantee the certification on adversarially patched sam- ples of round-trip certified samples, and indeed achieves non- trivial adversarial certified accuracy, while PC gets 0. By type-specific handling of adversarially patched samples and benign (benignly patched) samples, MRCert attains signifi- cantly higher certified accuracy while maintaining clean ac- curacy comparable to PC, indicating predictions of more in- puts are guaranteed to be robust and benign. PC becomes even worse when the patch size increases to 32 pixels: nearly all patched samples are adversarial. Con- sequently, its acc cert vanishes across all datasets, except for a negligible fraction of non-adversarial samples that remain certified on CIFAR-10, hitting the wall in acc cert . Still, PC gets 0 in acc adv cert . Although the clean accuracy of MRCert suffers from a decrease for all datasets, it still maintains a high acc cert for patch size of 32 pixels, where acc cert is 56.1% (= 24.8 /44.2), 85.5% (= 80.2 /93.8), and 60.5% (= 46.8 /77.4) of that for 16 pixels, respectively for ImageNet, ImageNette, and CIFAR10, which indicates that the type-specific design in MRCert still works very well against such a tough at- tack. While PC exhibits higher acc clean , contingent on prior knowledge of the patch count for recovery (one patch), it fails to provide any formal certified guarantees for these inputs. RQ2: How well does MRCert provide a theoretical bound for its performance at post-deployment time? Following standard practices in prior works, we compare the theoretical lower bounds derived from benign samples to assess the defenders’ performance on adversarially patched samples. acc cert and acc cert 2 in this RQ characterize the model’s ability to issue robustness certificates for benign and adversarial inputs at post-deployment time, respectively. Tables 3 and 4 summarize the results on benign samples in the three benchmarks. Note that PC is incapable of providing acc cert 2 (its original evaluation does not measure acc cert 2 , and its fundamental infeasibility is formalized in§3). The findings on ImageNet: As shown in Table 3, MRCert outperforms VOT in acc cert 2 by 8.2% and 3.5% for the two patch sizes, highlighting its superior capability in certifying adversarial samples. In acc cert , MRCert outperforms VOT by 6.9% at a 16-pixel patch size, yet underperforms it by 1.7% at 32 pixels. Crucially, VOT suffers from a roughly 10% decrease in clean accuracy compared to MRCert due to its smoothing mechanism without distinction. This degradation not only compromises prediction quality but also enables a more insidious threat: attackers can craft adversarial samples that yield incorrect predictions yet are erroneously granted a robustness certificate since the benign prediction is incor- Table 4: Results of certified recovery defenders on ImageNette and CIFAR10 with patch size 16 and 32 pixels (in %). DatasetImageNetteCIFAR10 Patch Size16 pixels32 pixels16 pixels32 pixels Metricsacc clean acc cert acc cert 2 acc clean acc cert acc cert 2 acc clean acc cert acc cert 2 acc clean acc cert acc cert 2 VOT96.291.380.596.287.657.389.376.956.989.368.628.6 PC99.597.2⊕99.493.7⊕98.590.0⊕98.280.9⊕ MRCert99.395.787.498.989.666.798.186.263.397.667.428.2 Note: ⊕=theoretically infeasible rect. While PC exhibits competitive acc clean and even supe- rior acc cert relative to MRCert, its theoretical limits prevent certification of adversarial samples in terms of acc cert 2 . The findings on ImageNette and CIFAR10: Similar trends are observed across ImageNette and CIFAR-10. On Ima- geNette, MRCert consistently outperforms VOT across all metrics (acc clean , acc cert , and acc cert 2 ), with average im- provements of 2.9%, 3.2%, and 8.2%, respectively. This in- dicates that while VOT’s smoothing mechanism has a rela- tively smaller impact on acc clean for ImageNette, it still sig- nificantly degrades its acc cert and acc cert 2 . On CIFAR-10, MRCert achieves performance comparable to PC in acc clean and acc cert while providing the additional acc cert 2 guaran- tee. Notably, with a 16-pixel patch, MRCert surpasses VOT in all metrics. Even as the patch size increases to 32 pixels, MRCert maintains competitive acc cert and acc cert 2 (within 1.2% and 0.4% of VOT, respectively) while sustaining a sig- nificantly higher acc clean (8.3% over VOT). Summary and discussion Across all datasets and patch sizes in the experiment, MRCert achieves a superior balance relative to existing baselines. MRCert is competitive with PC (which requires prior knowl- edge of patch counts) in acc clean and additionally provides a non-trivial round-trip certification (acc cert 2 ) to guarantee a benign prediction with a certificate at post-deployment time. Compared to VOT, MRCert consistently yields higher acc clean and competitive or superior certified accuracies (acc cert and acc cert 2 ). Critically, the empirical results of MRCert for adversarially patched samples consistently ex- ceed bounds from benign samples (e.g., acc cert in RQ1 to acc 2 cert in RQ2), validating the reliability of our theory. De- spite the seemingly low round-trip and adversarial certified accuracies demonstrated by MRCert in absolute measure, our approach establishes a novel paradigm for masking-based re- covery, laying the foundation for future work. We only adopt the original finetuning method from [ Xiang et al., 2024 ] , where a specific finetuning method like [ Saha et al., 2023b ] for [ Xiang et al., 2022 ] may improve its per- formance. Although MRCert generated more mutants than PC, the certification overhead of MRCert to certify the entire ImageNet validation set is 34 hours on a single 3090 GPU, which is still on par with many peers (41 hours in [ Zhou et al., 2024 ] , 38-40 hours in [ Xiang et al., 2022 ] ). The condi- tion for round-trip certification against one patch in MRCert is equivalent to that against two patches in PC. Our imple- mentation is built on PC’s implementation, which is tightly coupled with its customized ViT and BagNet, and the orig- inal PC+BagNet fails to certify samples against two patches of any size. Both VOT and PC fail to certify any 224× 224 samples against two patches of 48× 48 pixels or larger. We leave the acceleration of MRCert’s implementation, its gener- alization to broader base models, and its certification against more and larger adversarial patches for future work. 6 Related Work Recently, adversarial patch attacks have gained increasing at- tention [ Wei et al., 2024 ] as a significant threat to real-world systems such as commercial autonomous vehicles [ Wang et al., 2025 ] , as they model physical-world adversarial objects like a sticker [ Wei et al., 2023a ] or a tag [ Liu et al., 2020 ] . Ex- perimental results [ Chiang et al., 2020; Li et al., 2023 ] reveal the susceptibility of empirical defenses [ Hayes, 2018; Naseer et al., 2019 ] . Consequently, certified defenses have emerged to offer deterministic provable guarantees. Certified recov- ery ensures the recovery of the benign label of adversarially patched samples. To overcome the scalability bottlenecks of IBP [ Chiang et al., 2020 ] , extensive research has pivoted to- ward smoothing [ Xiang et al., 2021; Salman et al., 2022; Li et al., 2022; Zhou et al., 2023 ] , pioneered by Derandomized Smoothing [ Levine and Feizi, 2020a ] , which demonstrates its advancement against those randomized [ Cohen et al., 2019; Levine and Feizi, 2020b ] . [ Yatsura et al., 2023 ] adapts Deran- domized Smoothing to semantic segmentation and proposes post-deployment certification. [ Zhou et al., 2024 ] cross- checks different recovery defenders for detection. Masking- based certified detection [ Li et al., 2022; Huang et al., 2023; Zhou et al., 2026 ] has emerged, leveraging masking to guar- antee the detection of adversarially patched samples, which cannot provide any guarantee at post-deployment time [ Yat- sura et al., 2023 ] . [ Xiang et al., 2022 ] further detects their detection outcomes, extending the paradigm to the certified recovery of the benign prediction while preventing the ero- sion caused by the smoothing process. [ Saha et al., 2023a ] strengthens its training, and [ Xiang et al., 2024 ] improve its efficiency. However, they all fail to provide any certificate for adversarially patched samples. Our work represents the first attempt to provide a robustness certificate for both benign and adversarially patched samples in line with this SOTA. 7 Conclusion This work proposes MRCert, the first masking-based de- fender to provide certified recovery at post-deployment time for adversarially patched samples, while simultaneously maintaining high robustness and clean accuracy validated through theorems and experiments. Our replication pack- age, including the supplementary document (appendix), can be found in https://anonymous.4open.science/r/mrcert/. References [ Brown et al., 2017 ] Tom B Brown, Dandelion Man ́ e, Aurko Roy, Mart ́ ın Abadi, and Justin Gilmer. Adversarial patch. arXiv preprint arXiv:1712.09665, 2017. [ Chiang et al., 2020 ] Pingyeh Chiang, Renkun Ni, Ahmed Abdelkader, Chen Zhu, Christoph Studor, and Tom Gold- stein. Certified defenses for adversarial patches. In Inter- national Conference on Learning Representations, 2020. [ Cohen et al., 2019 ] Jeremy Cohen, Elan Rosenfeld, and Zico Kolter.Certified adversarial robustness via ran- domized smoothing. In Kamalika Chaudhuri and Rus- lan Salakhutdinov, editors, Proceedings of the 36th Inter- national Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 1310– 1320. PMLR, 09–15 Jun 2019. [ Deng et al., 2009 ] Jia Deng, Wei Dong, Richard Socher, Li- Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pages 248–255. Ieee, 2009. [ Hayes, 2018 ] Jamie Hayes. On visible adversarial perturba- tions & digital watermarking. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops, pages 1597–1604, 2018. [ He et al., 2022 ] Kaiming He, Xinlei Chen, Saining Xie, Yanghao Li, Piotr Doll ́ ar, and Ross Girshick. Masked au- toencoders are scalable vision learners. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 16000–16009, 2022. [ Huang et al., 2023 ] Yuheng Huang, Lei Ma, and Yuanchun Li. Patchcensor: Patch robustness certification for trans- formers via exhaustive testing. ACM Trans. Softw. Eng. Methodol., apr 2023. Just Accepted. [ Krizhevsky et al., 2009 ] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny im- ages. 2009. [ Kuutti et al., 2021 ] SampoKuutti,RichardBowden, Yaochu Jin, Phil Barber, and Saber Fallah. A survey of deep learning applications to autonomous vehicle control. IEEE Transactions on Intelligent Transportation Systems, 22(2):712–733, 2021. [ Levine and Feizi, 2020a ] Alexander Levine and Soheil Feizi. (de) randomized smoothing for certifiable defense against patch attacks. In Proceedings of the 34th Interna- tional Conference on Neural Information Processing Sys- tems, pages 6465–6475, 2020. [ Levine and Feizi, 2020b ] Alexander Levine and Soheil Feizi. Robustness certificates for sparse adversarial attacks by randomized ablation. In Proceedings of the AAAI Con- ference on Artificial Intelligence, volume 34, pages 4585– 4593, 2020. [ Li et al., 2022 ] Junbo Li, Huan Zhang, and Cihang Xie. Vip: Unified certified detection and recovery for patch at- tack with vision transformers. In Computer Vision–ECCV 2022: 17th European Conference, Tel Aviv, Israel, Octo- ber 23–27, 2022, Proceedings, Part XXV, pages 573–587. Springer, 2022. [ Li et al., 2023 ] Linyi Li, Tao Xie, and Bo Li. Sok: Certified robustness for deep neural networks. In 2023 IEEE sym- posium on security and privacy (SP), pages 1289–1310. IEEE, 2023. [ Litjens et al., 2017 ] Geert Litjens, Thijs Kooi, Babak Ehte- shami Bejnordi, Arnaud Arindra Adiyoso Setio, Francesco Ciompi, Mohsen Ghafoorian, Jeroen Awm Van Der Laak, Bram Van Ginneken, and Clara I S ́ anchez. A survey on deep learning in medical image analysis. Medical image analysis, 42:60–88, 2017. [ Liu et al., 2020 ] Aishan Liu, Jiakai Wang, Xianglong Liu, Bowen Cao, Chongzhi Zhang, and Hang Yu. Bias-based universal adversarial patch attack for automatic check-out. In Computer Vision–ECCV 2020: 16th European Con- ference, Glasgow, UK, August 23–28, 2020, Proceedings, Part XIII 16, pages 395–410. Springer, 2020. [ Metzen and Yatsura, 2021 ] JanHendrikMetzenand Maksym Yatsura.Efficient certified defenses against patch attacks on image classifiers.In International Conference on Learning Representations, 2021. [ Mohapatra et al., 2021 ] Jeet Mohapatra, Ching-Yun Ko, Lily Weng, Pin-Yu Chen, Sijia Liu, and Luca Daniel. Hidden cost of randomized smoothing. In International Conference on Artificial Intelligence and Statistics, pages 4033–4041. PMLR, 2021. [ Naseer et al., 2019 ] Muzammal Naseer, Salman Khan, and Fatih Porikli. Local gradients smoothing: Defense against localized adversarial attacks. In 2019 IEEE Winter Confer- ence on Applications of Computer Vision (WACV), pages 1300–1307. IEEE, 2019. [ Saha et al., 2023a ] Aniruddha Saha, Shuhua Yu, Mo- hammad Sadegh Norouzzadeh,Wan-Yi Lin,and Chaithanya Kumar Mummadi. Revisiting image classifier training for improved certified robust defense against adversarial patches. Transactions on Machine Learning Research, 2023. [ Saha et al., 2023b ] Shoumik Saha, Wenxiao Wang, Yigit- can Kaya, and Soheil Feizi. Adversarial robustness of learning-based static malware classifiers. arXiv preprint arXiv:2303.13372, 2023. [ Salman et al., 2022 ] Hadi Salman, Saachi Jain, Eric Wong, and Aleksander Madry.Certified patch robustness via smoothed vision transformers.In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 15137–15147, 2022. [ Szegedy et al., 2013 ] ChristianSzegedy,Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus.Intriguing properties of neural networks. arXiv preprint arXiv:1312.6199, 2013. [ Wang et al., 2025 ] Ningfei Wang, Shaoyuan Xie, Takami Sato, Yunpeng Luo, Kaidi Xu, and Qi Alfred Chen. Re- visiting physical-world adversarial attack on traffic sign recognition: A commercial systems perspective. In Pro- ceedings of the Network and Distributed System Security (NDSS) Symposium, San Diego, CA, USA, February 2025. [ Wei et al., 2023a ] Xingxing Wei, Ying Guo, and Jie Yu. Ad- versarial sticker: A stealthy attack method in the physical world. IEEE Transactions on Pattern Analysis and Ma- chine Intelligence, 45(3):2711–2725, 2023. [ Wei et al., 2023b ] Xingxing Wei, Ying Guo, Jie Yu, and Bo Zhang. Simultaneously optimizing perturbations and positions for black-box adversarial patch attacks. IEEE Transactions on Pattern Analysis & Machine Intelligence, 45(07):9041–9054, 2023. [ Wei et al., 2024 ] Hui Wei, Hao Tang, Xuemei Jia, Zhixi- ang Wang, Hanxun Yu, Zhubo Li, Shin’ichi Satoh, Luc Van Gool, and Zheng Wang. Physical adversarial attack meets computer vision: A decade survey. IEEE Trans- actions on Pattern Analysis and Machine Intelligence, 46(12):9797–9817, 2024. [ Xiang et al., 2021 ] Chong Xiang, Arjun Nitin Bhagoji, Vikash Sehwag, and Prateek Mittal. Patchguard: A prov- ably robust defense against adversarial patches via small receptive fields and masking.In 30th USENIX Secu- rity Symposium (USENIX Security 21), pages 2237–2254, 2021. [ Xiang et al., 2022 ] Chong Xiang, Saeed Mahloujifar, and Prateek Mittal. Patchcleanser: Certifiably robust defense against adversarial patches for any image classifier. In 31st USENIX Security Symposium (USENIX Security 22), pages 2065–2082, 2022. [ Xiang et al., 2023 ] Chong Xiang, Chawin Sitawarin, Tong Wu, and Prateek Mittal. Short: Certifiably robust percep- tion against adversarial patch attacks: A survey. Proceed- ings Inaugural International Symposium on Vehicle Secu- rity & Privacy, 2023. [ Xiang et al., 2024 ] Chong Xiang, Tong Wu, Sihui Dai, Jonathan Petit, Suman Jana, and Prateek Mittal. Patchcure: Improving certifiable robustness, model utility, and com- putation efficiency of adversarial patch defenses. In 33rd USENIX Security Symposium (USENIX Security), 2024. [ Yatsura et al., 2023 ] Maksym Yatsura, Kaspar Sakmann, N. Grace Hua, Matthias Hein, and Jan Hendrik Metzen. Certified defences against adversarial patch attacks on se- mantic segmentation. In The Eleventh International Con- ference on Learning Representations, 2023. [ Zhou et al., 2023 ] Qilin Zhou, Zhengyuan Wei, Haipeng Wang, and W.K. Chan. A majority invariant approach to patch robustness certification for deep learning models. In 2023 38th IEEE/ACM International Conference on Au- tomated Software Engineering (ASE), pages 1790–1794, 2023. [ Zhou et al., 2024 ] Qilin Zhou, Zhengyuan Wei, Haipeng Wang, Bo Jiang, and Wing-Kwong Chan. Crosscert: A cross-checking detection approach to patch robustness cer- tification for deep learning models. Proc. ACM Softw. Eng., 1(FSE), jul 2024. [ Zhou et al., 2026 ] Qilin Zhou, Zhengyuan Wei, Haipeng Wang, Zhuo Wang, and Wing-Kwong Chan. Hicert: To- ward patch robustness certification and detection for deep learning systems beyond consistent samples. IEEE Trans- actions on Reliability, 75:679–693, 2026. Supplementary Document for MRCert: Towards Post-deployment Patch Robustness Certification for Adversarially Patched Samples via Type-specific Masking A Formal Proof Property (Infeasibility of Re-certifying Adversarially Patched Samples for Existing Masking-based Recovery Works). ∀x ′ ∈ A P (x), c r (x)∧ f(x ′ )̸= f(x) =⇒ ¬c r (x ′ ). Proof. We know in [ Xiang et al., 2022 ] , c r (ˆx) := [∀M 1 , M 2 ∈ M P , f(ˆx⊙ M 1 ⊙ M 2 ) = f(ˆx)]. Then if c r (x) = True, we know [∀M 1 , M 2 ∈ M P , f(x⊙ M 1 ⊙ M 2 ) = f(x)]. We also know ∀P ∈ P,∃M ∈ M P , M⊙ P = P by definition, which makes ∀x ′ ∈ A P (x), x ′ ⊙ M = x⊙ M (see Fig. 2). Therefore, ∃x ′ ∈ A P (x), f(x ′ ⊙ M) = f(x⊙ M) = f(x). We have f(x ′ ) ̸= f(x) from the antecedent; therefore, ∃x ′ ∈ A P (x), f(x ′ ⊙ M) ̸= f(x ′ ). Since c r (x ′ ) requires [∀M 1 , M 2 ∈ M P , f(x ′ ⊙ M 1 ⊙ M 2 ) = f(x ′ )], c r (x ′ ) = False holds. Lemma (Certification of benign samples). Given an arbi- trary sample ˆx, if [∀M 1 , M 2 , M 3 ∈ M P , f(ˆx⊙M 1 ⊙M 2 ⊙M 3 ) = f(ˆx)] holds,∀ˆx ′ ∈ A P (ˆx), g(ˆx ′ ) = g(ˆx). Proof. We first analyze g(ˆx).Since [∀M 1 , M 2 , M 3 ∈ M P , f(ˆx ⊙ M 1 ⊙ M 2 ⊙ M 3 ) = f(ˆx)] =⇒ [∀M 1 , M 2 ∈ M P , f(ˆx ⊙ M 1 ⊙ M 2 ) = f(ˆx)], we know its prediction la- bel g(ˆx) = f(ˆx) output in Case 1 ⃝. We then analyze g(ˆx ′ ). For ∀ˆx ′ ∈ ˆx ′ | ˆx ′ = (J − P)⊙ˆx + P⊙ˆx ′ ∧ P ∈ P (i.e., ∀ˆx ′ ∈ A P (ˆx)), w.l.o.g., we let M 1 ⊙ P = O. Therefore, we get ˆx ′ ⊙ M 1 = ((J − P)⊙ˆx + P⊙ˆx ′ )⊙ M 1 = ˆx⊙ M 1 . Then, we get [∃M 1 ∈ M P ,∀M 2 , M 3 ∈ M P , f(ˆx ′ ⊙ M 1 ⊙ M 2 ⊙ M 3 ) = f(ˆx)] (see Fig. 2). Note that the special cases M 2 = M 3 , M 1 = M 2 = M 3 are included. Case 1: Sup- pose the returned label of ˆx ′ output in Case 1 ⃝ as f(ˆx ′ ) (i.e., ∀M 1 , M 2 ∈ M P , f(ˆx ′ ⊙M 1 ⊙M 2 ) = f(ˆx ′ )), then we know g(ˆx ′ ) = f(ˆx ′ ) = f(ˆx) = g(ˆx). Case 2: Otherwise, its returned label should be output in Case 2 ⃝ as f(ˆx ′ ⊙ M 1 ), since [∃M 1 ∈ M P ,∀M 2 , M 3 ∈ M P , f(ˆx ′ ⊙ M 1 ⊙ M 2 ⊙ M 3 ) = f(ˆx ′ ⊙M 1 ) = f(ˆx)], and further g(ˆx ′ ) = f(ˆx ′ ⊙ M 1 ) = f(ˆx) = g(ˆx). Lemma (Certification of adversarially patched samples). Given an arbitrary sample ˆx, if [∃M 1 ∈ M P ,∀ M 2 ,M 3 ,M 4 ∈ M P , f(ˆx ⊙ M 1 ⊙ M 2 ⊙ M 3 ⊙ M 4 ) = f(ˆx ⊙ M 1 )] holds, ∀ˆx ′ ∈ A P (ˆx), g(ˆx ′ ) = g(ˆx). Proof. We first analyze g(ˆx). Case 1: If ˆx meet the con- dition of Case 1 ⃝, we can further get ∀M 1 , M 2 , M 3 , M 4 ∈ M P , f(ˆx ⊙ M 1 ⊙ M 2 ⊙ M 3 ⊙ M 4 ) = f(ˆx). Note that the special case M 1 = M 2 = M 3 = M 4 is included, which means we can get g(ˆx) = f(ˆx⊙M 1 ). Case 2: Otherwise, by the given condition [∃M 1 ∈ M P ,∀ M 2 ,M 3 ,M 4 ∈ M P , f(ˆx⊙ M 1 ⊙ M 2 ⊙ M 3 ⊙ M 4 ) = f(ˆx⊙ M 1 )] =⇒ [∃M 1 ∈ M P ,∀ M 2 ,M 3 ∈ M P , f(ˆx⊙ M 1 ⊙ M 2 ⊙ M 3 ) = f(ˆx⊙ M 1 )], ˆx meet the condition in Case 2 ⃝ and its prediction label g(ˆx) = f(ˆx⊙M 1 ), same as Case 1 ⃝. We then analyze g(ˆx ′ ). For ˆx ′ ∈ ˆx ′ | ˆx ′ = (J − P)⊙ˆx + P⊙ˆx ′ ∧ P ∈ P (i.e., ∀ˆx ′ ∈ A P (ˆx)), Case 1: Suppose M 1 ⊙P = O. Then we can get ˆx ′ ⊙ M 1 = ((J− P)⊙ˆx + P⊙ˆx ′ )⊙ M 1 = ˆx⊙ M 1 , and further get [∀M 2 , M 3 , M 4 ∈ M P , f(ˆx ′ ⊙ M 1 ⊙ M 2 ⊙ M 3 ⊙ M 4 ) = f(ˆx ⊙ M 1 )], which is the same condition as that on ˆx. Therefore, repeating those analysis for g(ˆx) above can get g(ˆx) = g(ˆx ′ ). Case 2: Otherwise, for M 2 , M 3 , M 4 , w.l.o.g., we let M 2 ⊙ P = O (M 1 ̸= M 2 ). Then similarly, we get [∃M 1 , M 2 (̸= M 1 )∈ M P ,∀M 3 , M 4 ∈ M P , f(ˆx ′ ⊙ M 1 ⊙ M 2 ⊙ M 3 ⊙ M 4 ) = f(ˆx⊙M 1 )]. Note that the special cases M 1 = M 3 , M 2 = M 4 ,M 3 = M 4 are included. Case 2.1: Sup- pose the prediction label g(ˆx ′ ) output in Case 1 ⃝. Then, since [∃M 1 , M 2 (̸= M 1 )∈ M P , f(ˆx ′ ⊙ M 1 ⊙ M 2 ) = f(ˆx⊙M 1 )] (spe- cial case M 1 = M 3 , M 2 = M 4 ), by the condition of Case 1 ⃝, we know g(ˆx ′ ) = f(ˆx ′ ) = f(ˆx⊙M 1 ) = g(ˆx). Case 2.2: Sup- pose the prediction label g(ˆx ′ ) output in Case 2 ⃝. Then, since [∃M 1 , M 2 (̸= M 1 )∈ M P ,∀M 3 ∈ M P , f(ˆx ′ ⊙ M 1 ⊙ M 2 ⊙ M 3 ) = f(ˆx⊙M 1 )] (special case M 3 = M 4 ), by the condition of Case 2 ⃝, we know g(ˆx ′ ) = f(ˆx ′ ⊙M 1 ) = f(ˆx⊙M 1 ) = g(ˆx). Case 2.3: Otherwise, the prediction label of ˆx ′ should out- put in Case 3 ⃝ since [∃M 1 , M 2 (̸= M 1 ) ∈ M P ,∀M 3 , M 4 ∈ M P , f(ˆx ′ ⊙ M 1 ⊙ M 2 ⊙ M 3 ⊙ M 4 ) = f(ˆx⊙M 1 ) = f(ˆx ′ ⊙M 1 ⊙ M 2 )] (special case M 1 = M 3 , M 2 = M 4 ), and further g(ˆx ′ ) = f(ˆx ′ ⊙M 1 ⊙ M 2 ) = f(ˆx⊙M 1 ) = g(ˆx). Theorem (Certification of samples). Given an arbitrary sam- ple ˆx, if c(ˆx) = T rue holds,∀ˆx ′ ∈ A P (ˆx), g(ˆx ′ ) = g(ˆx). Simply conjoining the antecedent of Lemma 1 and Lemma 2 can prove this theorem. Theorem (Round-trip certification of samples). Given a benign sample x, if [∀M 1 , M 2 , M 3 , M 4 ∈ M P , f(x⊙ M 1 ⊙M 2 ⊙M 3 ⊙M 4 ) = f(x)] (i.e., c 2 r (x) = True), [∀x ′ ∈ A P (x), g(x ′ ) = g(x)∧ c r (x ′ ) = True∧ c r (x) = True]. Proof. By the condition [∀M 1 , M 2 , M 3 , M 4 ∈ M P , f(x⊙ M 1 ⊙ M 2 ⊙M 3 ⊙M 4 ) = f(x)], we know the returned label g(x) = f(x) in Case 1 ⃝ and c r (x) = True. Still by this condition, we know [∀x ′ ∈ A P (x),∃M 1 ∈ M P ,∀M 2 , M 3 , M 4 ∈ M P , f(x ′ ⊙ M 1 ⊙M 2 ⊙M 3 ⊙M 4 ) = f(x)], since [∃M 1 ∈ M P ,∀ x ′ ∈ A P (x), x ′ ⊙ M 1 = x⊙M 1 ] (see Fig. 2 for illustration). Then by Lemma 2, we know [∀x ′ ∈ A P (x), c r (x ′ ) = True]. By Lemma 1, we also know [∀x ′ ∈ A P (x), g(x ′ ) = g(x)]. Finally, we know [∀x ′ ∈ A P (x), g(x ′ ) = g(x)∧ c r (x ′ ) = True∧ c r (x) = True]. B The Subtlety in the Design of MRCert The ordering of the type-specific cases in g. The sequence of the cases in g is crucial. Changing the order will either break the certification guarantee for adversarially patched samples or degrade the clean accuracy. For example, swap- ping Case 2 ⃝ and Case 3 ⃝ would require the benign counter- part of an adversarially patched sample to exhibit the same prediction labels under four masks (instead of three) to re- main certified; otherwise, a patch attacker could exploit a fourth-order masked mutant that predicts another label to evade the detection of the adversarially patched sample by this case-swapped version of g. In our proposed version of g, Case 1 is intentionally placed first to prevent benign samples from reaching the recovery stages, thereby improving clean accuracy. The ordering of mask conditions within a type-specific case in g. The internal ordering of masking conditions also mat- ters. Consider Case 2 (indirect testing): Suppose that its quantifiers were reordered from “there exists mask 1 such that for all mask 2, mask3...” to “there exist mask 1 and mask 2 such that for all mask 3 ...”. Then, adversarial sam- ples containing two patches could escape certification, even when their benign counterparts are round-trip certified. In this reordered structure, the adversarial patched sample could simply choose two masks (mask 1 and mask 2) that expose both patches, i.e., they do not cover either patch. Then, even if mask 3 covers one patch, the other patch remains uncov- ered, allowing the attacker to arbitrarily alter the prediction and evade detection. This shows that the original quantifier ordering is essential for preventing such escape cases. The number of masks within a type-specific cases in g. Tak- ing Case 2 as an example, the number of masks is also critical. Reducing the number of masks in Case 2 would allow adver- sarial samples with two patches to escape from the detection of indirect testing, for reasons analogous to the ordering is- sue discussed above. Conversely, increasing the number of masks (e.g., by 1) would increase the masking requirements for certification, which makes certifying a benign sample re- quire prediction consistency under four masks, instead of the current three, which directly decreases the total number of samples that can be certified. C Extension of MRCert to Recover and Certify Samples with N-patches We can extend the maximum number of patches from 2 to N (called MRCert-N-patch, a variant of MRCert) following the following idea. First, we apply each set of N masks in the covering mask set M on the input sample ˆx to test whether ˆx is harmful. If it is not harmful, MRCert-N-patch returns the label f(ˆx) (marked as N-Case 1 ⃝). If ˆx is detected as harmful, we then test whether all its first-order mutants are harmful by applying each possible subset with N masks se- lected with replacement from M on each first-order mutant of ˆx. If there exists a first-order mutant, whose all (N + 1)th- order mutants generated from the first-order mutant of ˆx are predicted with the same label as this first-order sample, then ˆx is deemed as a one-patch harmful sample, this first-order mutant is “clean” and the prediction label of this first-order mutant is returned (marked as N-Case 2 ⃝). If that is not the case, we then test whether all second-order mutants of ˆx are harmful in the same manner, and repeat until the N th-order mutants of ˆx are tested. For the certification function c r with the input sample ˆx, it should be extended to the condition that all (N + 1)th-order mutants of ˆx are predicted with the same label as ˆx (for those input samples whose label returned in Case 1 ⃝), and the condition that there exists a first-order mu- tant of ˆx, whose all (N + 2)th-order mutants are predicted with the same label as this first-order mutant of ˆx (for those input samples whose label returned in Case 2 ⃝), and certify- ing the input samples output in other cases by the condition in the same manner. For the round-trip certification function, it should be the condition that all 2N th-order mutants of a benign sample x are predicted with the same label as x. We leave the formal proof and implementation as future work. D Experimental Setup D.1 Environment and Dataset The evaluation is conducted on an Ubuntu 20.04 machine equipped with four Nvidia 3090 GPUs. Following [ Xiang et al., 2022 ] , we adopt 1000-class ImageNet [ Deng et al., 2009 ] , 10-class CIFAR10 [ Krizhevsky et al., 2009 ] , and 10-class Im- ageNette as our datasets, encompassing both large-scale, di- verse datasets and efficient benchmarks widely used for rapid experimentation. D.2 Models and Baselines We adopt the Vision Transformer (ViT) as our base model, which achieves the state-of-the-art in many patch robustness certification defenders [ Xiang et al., 2024; Li et al., 2022; Salman et al., 2022; Xiang et al., 2022; Huang et al., 2023 ] . We adopt the state-of-the-art masking-based defender PatchCURE (PC) [ Xiang et al., 2024 ] and state-of-the- art smoothing-based defender VOT-CrossCert (VOT) from CrossCert [ Zhou et al., 2024 ] , which shares the common methodology for smoothing-based recovery with ViP [ Li et al., 2022 ] and S-ViT [ Salman et al., 2022 ] . We arm VOT with the methodology for runtime verification proposed by [ Yat- sura et al., 2023 ] as our baseline to compare with MRCert in our infrastructure. Specifically, MRCert adopts the end-to-end ViT-SRF model (setting 14x1-k6 1 ) proposed and used by PatchCURE [ Xiang et al., 2024 ] from https://github.com/inspire-group/ PatchCURE with the pre-train weights and setting from MAE [ He et al., 2022 ] , so that MRCert can use the same strat- egy in the experiment as PatchCURE to calculate the cov- ering mask set, generate mutants with their predictions in- side the ViT-SRF. We use the training scripts with the set- tings and hyperparameters from the official repository of PatchCURE for fine-tuning ViT-SRF, which uses the train- ing samples with their first and second-order mutants only. We then apply the same finetuned ViT-SRF to both MRCert and PatchCURE to ensure fairness. We also adopt this offi- cial repository https://github.com/inspire-group/PatchCURE to implement PatchCURE in our infrastructure. We adopt the same pre-trained weights and settings from MAE [ He et al., 2022 ] for VOT. We follow the fine-tuning settings and hy- perparameters from the state-of-the-art S-ViT [ Salman et al., 1 Other variants ViT-SRF14x2, ViT-SRF2x2, and BagNet33 can- not handle the situation against two patches, since all their receptive fields would be inherently masked by VIT-SRF [ Xiang et al., 2024 ] when generating corresponding mutants.k is the parameter to con- trol the position of splitting SRF and LRF in VIT-SRF in the range [0, 12], which can tune the trade-off between computational effi- ciency and robustness. We adopt the middle one since it is not the focus of this paper. 2022 ] for VOT (note that smoothing-based recovery adopts a different notion of mutants, where a mutant is a slice of a sample; therefore, a different fine-tuning on the base model is needed [ Li et al., 2022 ] ). We also adopt the column abla- tion with the ablation size of 19 pixels from [ Salman et al., 2022 ] . We have extracted the corresponding results from the original papers of ViP [ Li et al., 2022 ] and S-ViT [ Salman et al., 2022 ] to compare with VOT in Tab. 1 (their results on round-trip certification are not reported in their papers). D.3 Metrics Let x be a benign sample with the true label y 0 in a clean test dataset D, and R = ⟨g(x), c(x), c 2 r (x)⟩ be a certi- fied recovery defender.Clean accuracy is the fraction of D that are correctly predicted, defined as acc clean = |x∈D|g(x)=y 0 | |D| , which evaluates the standard performance of certified recovery as a classifier. Certified accuracy is the fraction of D that are correctly predicted and certified robust, whose adversarially patched samples should be pre- dicted with the same label as the benign sample, defined as acc cert = |x∈D|g(x)=y 0 ∧c r (x)=True| |D| . Round-trip cer- tified accuracy is the fraction of D that are correctly pre- dicted and round-trip certified, whose adversarially patched samples should be predicted with the same label as the be- nign sample and gain a provable robust verdict, defined as acc cert 2 = |x∈D|g(x)=y 0 ∧c 2 r (x)=True| |D| . The clean accu- racy of the base classification model f is |x∈D|f(x)=y 0 | |D| . Clean accuracy and certified accuracy are commonly adopted by peers [ Levine and Feizi, 2020a; Salman et al., 2022; Li et al., 2022; Xiang et al., 2024; Xiang et al., 2022; Xiang et al., 2021 ] , and round-trip certified accuracy is pro- posed by [ Yatsura et al., 2023 ] . In RQ1, the test dataset D is a set of patched sam- ples from attacking a subset of the test dataset (valida- tion dataset for ImageNet), denoted as D pat .Clean ac- curacy and certified accuracy are measured in this set of patched samples to evaluate certified recovery defenders on their ability to recover predictions and recover predic- tions with a provably robust verdict, respectively. We mea- sure each defender’s ability to certify adversarially patched samples by adversarial certified accuracy acc adv cert = |ˆx∈D pat |g(ˆx)=y 0 ∧c r (ˆx)=True∧f(ˆx)̸=y 0 | /|ˆx∈D pat |f(ˆx)̸=y 0 |.In RQ2, we use the original test dataset (validation dataset for ImageNet) as D. D.4 Experimental Procedure We adopt the patch sizes of 16 pixels (measured as a square patch region with a side length of 16 pixels) and 32 pixels for all three datasets. All samples are rescaled to 224x224 [ Zhou et al., 2024; Li et al., 2022; Xiang et al., 2022; Xiang et al., 2024 ] . In RQ1, we perform an actual adversarial patch attack IFGSM adopted from [ Levine and Feizi, 2020a ] on PC and MRCert, which uses their shared base model as the attack model for gradient-based attacks without the knowledge of the non-differentiable label recovery function for fairness. Note that the recent proposed attacks are more toward prac- tical, such as limiting the access times or can only get the returned prediction label, while our IFGSM attack has direct and full access to the base model, which is a powerful exam against attackers. We set 80 random starts, 150 iterations per random start, and a step size of 0.05 following [ Levine and Feizi, 2020a ] . We randomly select 500 test samples from each test dataset for attacks. We follow the practice in [ Levine and Feizi, 2020a ] to return the worst patched sample for each benign sample and place it into D pat . In RQ2, we directly adopt the entire test dataset (validation dataset for ImageNet) as D. In both RQ1 (as a follow-up to the attack) and RQ2, for each defender on each sample in each test dataset, we first generate and evaluate corresponding mutants using the corre- sponding base model (PC and MRCert share the same ones), then apply each defender to the prediction results collected for these mutants, and measure the metric values.