Paper deep dive
Adversarial Detection for Pre-trained Classifiers via Lipschitz-Margin Analysis with Certification
Rui Zhang, Xinle Cao, Huazhen Yu, Jian Liu, Youwen Zhu
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Deep classifiers deployed in safety-critical services like autonomous-driving perception remain vulnerable to small adversarial perturbations. Certified $\ell_2$ defenses today face a costly trade-off: randomized smoothing (RS) requires hundreds of noisy queries per input, while Lipschitz networks (LN) constrain the architecture and sacrifice clean accuracy. We take a detection-oriented approach instead: rather than certifying that predictions are invariant inside an $\ell_2$ ball, we certify that adversarial inputs within an $\ell_2$ ball are \emph{detected} --- a guarantee aligned with security-critical deployments where missing an attack is costlier than flagging a clean input. To realize this, we prove a Lipschitz-margin reduction from certified $\ell_2$ robustness to certified detection, which reduces the problem to handling a single Lipschitz constant $L$. We introduce two detector families: $\mathbb{D}_{Adv}$, which estimates $L$ from a single defender-side perturbed pair, and $\mathbb{D}_{lc}$, which augments that pair with a local margin centroid to keep the estimate above what the certificate requires. Both deploy on any pretrained classifier without retraining. With a valid global bound, the detector is fully certified at that radius; with a local estimate $L'$, certification is sample-wise and applies only when our certified condition holds. Across MNIST, CIFAR-10, and ImageNet-1k on four backbones (LeNet-5, VGG16, ResNet-50, ViT-B/16), our detectors match or outperform five baselines (CTT, SortNet, CRM, ContraNet, A$^2$D). For CIFAR-10 with 1-Lipschitz SortNet, our reduction delivers $100\%$ certified detection at the lowest FPR among compared certified detectors; on the standard CIFAR-10 VGG16, our detectors reject all evaluated in-budget adversarial examples, with 62-82\% both rejected and formally certified.
Tags
Links
- Source: https://arxiv.org/abs/2610.15359v1
- Canonical: https://arxiv.org/abs/2610.15359v1
Trouble viewing inline? Open PDF directly →
Full Text
115,801 characters extracted from source content.
Expand or collapse full text
Adversarial Detection for Pre-trained Classifiers via Lipschitz-Margin Analysis with Certification PubID: pubid: Network and Distributed System Security (NDSS) Symposium 2027 22–26 March 2027, Seoul, Republic of Korea ISBN 978-1-970672-09-1 https://dx.doi.org/10.14722/ndss.2026.230728 w.ndss-symposium.org Rui Zhang1, Xinle Cao2, Huazhen Yu3, Jian Liu2, Youwen Zhu14 Affiliation: 1Nanjing University of Aeronautics and Astronautics Affiliation: 2The State Key Laboratory of Blockchain and Data Security, Zhejiang University Affiliation: 3Nanjing University of Information Science and Technology 4Corresponding author Abstract Deep classifiers deployed in safety-critical services like autonomous-driving perception remain vulnerable to small adversarial perturbations. Certified ℓ2 _2 defenses today face a costly trade-off: randomized smoothing (RS) requires hundreds of noisy queries per input, while Lipschitz networks (LN) constrain the architecture and sacrifice clean accuracy. We take a detection-oriented approach instead: rather than certifying that predictions are invariant inside an ℓ2 _2 ball, we certify that adversarial inputs within an ℓ2 _2 ball are detected — a guarantee aligned with security-critical deployments where missing an attack is costlier than flagging a clean input. To realize this, we prove a Lipschitz-margin reduction from certified ℓ2 _2 robustness to certified detection, which reduces the problem to handling a single Lipschitz constant L. We introduce two detector families: AdvD_Adv, which estimates L from a single defender-side perturbed pair, and lcD_lc, which augments that pair with a local margin centroid to keep the estimate above what the certificate requires. Both deploy on any pretrained classifier without retraining. With a valid global bound, the detector is fully certified at that radius; with a local estimate L′L , certification is sample-wise and applies only when our certified condition holds. Across MNIST, CIFAR-10, and ImageNet-1k on four backbones (LeNet-5, VGG16, ResNet-50, ViT-B/16), our detectors match or outperform five baselines (CTT, SortNet, CRM, ContraNet, A2D). For CIFAR-10 with 1-Lipschitz SortNet, our reduction delivers 100%100\% certified detection at the lowest FPR among compared certified detectors; on the standard CIFAR-10 VGG16, our detectors reject all evaluated in-budget adversarial examples, with 62-82% both rejected and formally certified. I Introduction Deep classifiers (DNNs) deployed in safety-critical services like autonomous-driving perception [eykholt2018robust], content moderation, biometric authentication [sharif2016accessorize], and access control are vulnerable to adversarial examples [intri2013, jing2021too]: small, often imperceptible perturbations δ that flip the prediction argmaxf(x+δ)≠argmaxf(x) f(x+δ)≠ f(x). A large body of work [li_sok_2023, weng2020towards, lecuyer2019certified, pautov2022c, li2021towards] addresses this by building certifiably robust classifiers — whose prediction is provably unchanged inside an ℓp _p-ball around the input. Existing ℓ2 _2 certifications cluster into two families, each with a structural cost: • Randomized smoothing (RS) [cohen2019certified, salman2019provably, yang2020randomized, li_certified_2019, carlini_certified_2023, delattre2024lipschitz] replaces f with a smoothed classifier whose output is a majority vote over Gaussian-noised inputs. Each prediction needs hundreds to thousands of forward passes, ruling out real-time use. • Lipschitz networks (LN) [zhang_rethinking_2022, leino2021globally, li_preventing_2019] constrain the architecture so that a small global Lipschitz constant is provable by construction. The constraint sacrifices clean accuracy and forecloses use of standard pretrained classifiers. An alternative, motivated by Shumailov et al. [shumailov2020towards] and Tramer [tramer2022detecting], is to defend by detecting and rejecting adversarial inputs: the deployed classifier is left unchanged, and a detector decides whether each query is safe to answer. This preserves clean accuracy and inference speed. Empirical detectors are well studied [gao2026from, ma2019nic, aldahdooh_adversarial_2022, yang2022you, sotgiu2020deep, zhao2024attack, lai2025auditvotes], but they offer no formal guarantee, and certified detection has received far less attention. Tramer [tramer2022detecting] gave a theoretical reduction from robust classification to robust detection, but the construction is too expensive for deployment. We therefore ask: Can a certified robust classifier be turned into a certified detector that is efficient enough for real-time use? Three challenges. Doing this in practice requires solving three coupled problems. (C1) Reduction. Existing certified-robustness theorems guarantee prediction invariance inside a radius, not detectability of adversarial inputs outside it. Reducing detection to robustness requires a fresh argument that ties the margin of any in-budget adversarial example to its perturbation budget. (C2) Lipschitz constants are intractable. Any Lipschitz-based reduction needs a value for the network’s Lipschitz constant L. Architecturally enforced bounds (e.g., 1-Lipschitz networks) cost clean accuracy; numerical bounds on standard pretrained networks are vacuous. (C3) Local estimators must be calibrated. Replacing the unknown global L with a local estimator L′L can occasionally yield L′L below what the certificate requires, silently breaking the guarantee on those samples. Our approach. An adversarial example with bounded budget cannot move far from the decision boundary, so the classifier’s margin function q(⋅)q(·) must be small there. Lipschitz continuity makes this quantitative: if f is L-Lipschitz, the change in margin under any perturbation δ is bounded by cL‖δ‖cL\|δ\|, tying the adversarial margin q(^)q( x) to the clean margin q()q( x) and to ‖δ‖\|δ\|. Each input is certified by a Lipschitz value relevant to it, not a globally enforced one. Two practical detectors follow: AdvD_Adv replaces the unknown clean counterpart with a defender-side perturbed surrogate, and lcD_lc additionally anchors the bound to a local centroid of the margin function. The two detectors are tighter in different regimes (cf. Section VI-C): on Lipschitz-constrained networks AdvD_Adv’s short-pair certificate is naturally tight, while on unconstrained pretrained classifiers lcD_lc’s centroid scales the bound with the model’s clean-margin distribution and certifies a substantially larger fraction. Both deploy on any pretrained classifier. For (C1), we prove a Lipschitz-margin reduction (Lemma IV.1, Theorem IV.2): every successful in-budget adversarial example is provably detectable from L and the margin alone. The certificate is attack-agnostic: it applies to any in-budget ℓ2 _2 perturbation that flips the prediction, regardless of how it was generated. For (C2), on Lipschitz-constrained networks (SortNet [zhang_rethinking_2022], CRM [fazlyab2023certified]) the exact LglobL_glob gives a fully certified detector via Lemma IV.1; on unconstrained pretrained classifiers, we replace LglobL_glob with a local estimate L′L , which yields sample-wise certificates when the local estimate is large enough for certification while allowing substantially lower FPR in practice. For (C3), we quantify this sample-wise guarantee with cert%, the fraction of successful in-budget adversarial examples that are both rejected and formally certified. Concretely, for each detected adversarial example, the certificate holds when L′≥L∗L ≥ L^*, where L∗L^* is the minimum Lipschitz value required by Proposition IV.6 on that sample. To increase this certified subset, we can use a more conservative multi-probe estimate Lstrong′=maxkLk′L _strong= _kL _k: it deliberately raises L′L , making L′≥L∗L ≥ L^* easier to satisfy, but the same larger L′L also enlarges the rejection threshold, increasing FPR and runtime. What our guarantee covers. We distinguish three protection levels. Fully certified detection applies when a valid Lipschitz bound is known for all inputs, so every successful adversarial example within the declared radius is rejected; the cost is that a conservative global bound can also reject many clean inputs, i.e., high FPR. Conditionally certified detection applies on standard pretrained models after replacing the intractable global bound by a local estimate L′L : this gives a lower-FPR operating point, but only the subset satisfying the per-sample certified condition is formally certified. The stronger L′L variant above deliberately moves along this frontier, trading FPR and runtime for a larger certified subset. Empirical protection describes additional successful attacks that are rejected in experiments but do not satisfy this per-sample certificate. We therefore report TPR, FPR, and cert% together: the same detector may reject nearly all measured attacks, while only a subset of those rejections are formally certified. In summary, our contributions are as follows. • A Lipschitz-margin reduction from certified ℓ2 _2 robustness to certified adversarial detection (Lemma IV.1, Theorem IV.2) with an attack-agnostic guarantee. We empirically validate the reduction on 1-Lipschitz SortNet, where the global Lipschitz LglobL_glob is exactly known and Lemma IV.1 delivers fully certified detection (Table I). • Two practical approximated detectors for the case where LglobL_glob is intractable: AdvD_Adv (single-perturbation surrogate, tighter on Lipschitz-constrained networks) and lcD_lc (local-centroid surrogate, tighter on unconstrained pretrained classifiers); both deploy without retraining. We give deterministic bias bounds (Section IV-C) and introduce cert%, the fraction of all successful in-budget adversarial examples that are both rejected and formally certified. On CIFAR-10 VGG16, our detectors achieve 100%100\% empirical TPR on in-budget adversarial examples while 6262–82%82\% of them are both rejected and formally certified; a stronger multi-probe L′L estimate further raises CIFAR-10 cert% by up to 34.834.8 points with explicit FPR and runtime costs. (Tables I and VI). • A comprehensive empirical evaluation on MNIST, CIFAR-10 and ImageNet-1k, four architectures (LeNet-5, VGG16, ResNet-50, ViT-B/16), and five baselines (CTT, SortNet, CRM, ContraNet, A2D). Against SOTA empirical detector A2D we deliver 100%100\% TPR at 3.6%3.6\% FPR on ViT-B/16 (ϵ=0.1ε=0.1) versus A2D’s 89.5%89.5\% TPR at 11.2%11.2\% FPR. Furthermore, our detection runs 99–20×20× faster than randomized smoothing on ImageNet (Section V). • A principled bridge from robust training to detection. A large body of robustness research focuses on enlarging clean-input margins (Section I). Because our detectors deploy on any pretrained classifier without retraining, margin-enlarging advances in that literature can tighten our detection frontier under the same reduction, e.g., ℓ2 _2 PGD adversarial training on a CIFAR-10 VGG16 cuts lcD_lc’s FPR from 93.6%93.6\% to 32.2%32.2\% at ϵ=0.5ε=0.5 while maintaining ≥99%≥ 99\% TPR (Section V-E). I Related Works I-A Empirical Adversarial Detectors A long line of empirical detectors aims to identify adversarial inputs at inference time without certified guarantees [aldahdooh2022adversarial, zhao2023adversarial, gao2026from, ma2019nic]. They roughly fall into three categories. Auxiliary-network detectors attach trainable components to the protected classifier and flag inputs whose intermediate or reconstructed representations look anomalous: ContraNet [yang2022you] trains a class-conditional generator and uses reconstruction error as the detection signal but does not scale to ImageNet-1k, while U-CAN [mizrahi2025pulling] embeds projection layers and ArcFace-style components into intermediate features and detects adversarial inputs through unsupervised anomaly detection. Statistic-based detectors compute test statistics from the model’s predictions or gradients on the input; PASA [bhusal2024pasa] is a recent representative that combines prediction sensitivity and feature-attribution sensitivity to noise into two threshold-calibrated scores. Finally, adversarial attacks as detectors flip the perspective: A2D [zhao2024attack] measures the perturbation budget required to cross the decision boundary, exploiting the fact that already-adversarial inputs need less push than clean ones, and is one of the few empirical detectors evaluated on full ImageNet-1k — making it our strongest empirical baseline (Table IV(b)). All three families provide empirical guarantees only and remain subject to the standard adaptive-attack critique [tramer2020adaptive, wan2023bounceattack]: an adversary aware of the detector can craft inputs that evade its statistics or auxiliary networks while still flipping the underlying classifier. In contrast, our detectors derive from a Lipschitz-margin reduction (Section IV) and inherit an attack-agnostic certificate: any in-budget ℓ2 _2 perturbation that flips the prediction is provably refused, regardless of how the adversarial input was generated. I-B Certified Robustness Existing work on certified robustness against adversarial examples primarily focuses on designing robust classifiers that maintain correct predictions even when inputs are adversarially perturbed. These approaches can be broadly categorized into three families: (1) relaxation-based methods [gowal2019scalable], (2) Lipschitz network methods [leino2021globally], and (3) randomized smoothing methods [cohen2019certified]. Among them, randomized smoothing and Lipschitz network methods currently achieve state-of-the-art performance against ℓ2 _2-norm perturbations; consequently, we concentrate on these two paradigms. Randomized smoothing (RS) methods [cohen2019certified, li_certified_2019, wong_scaling_2018, carlini_certified_2023, mueller2023certified] enhance robustness by injecting random noise into the input, thereby transforming an arbitrary base classifier into a smoothed classifier that is certifiably robust under the ℓ2 _2 norm. In particular, Cohen et al. [cohen2019certified] introduced Gaussian smoothing and derived the strongest known ℓ2 _2 robustness radius. For ℓ1 _1 robustness, Lecuyer et al. [lecuyer2019certified] employed Laplacian smoothing. Regarding ℓ∞ _∞ robustness, Yang et al. [yang2020randomized] demonstrated that by leveraging norm inequalities to translate ℓ2 _2 guarantees derived from Gaussian smoothing into ℓp _p bounds, one can achieve state-of-the-art certified ℓ∞ _∞ robustness. For Lipschitz network (LN) methods, they exploit the Lipschitz constant of the neural network to formally certify robustness [xu_lot_2023, zhang_rethinking_2022, hein_formal_2017, li_preventing_2019, leino2021globally, tsuzuku2018lipschitz]. Early efforts in this line typically compute a global Lipschitz constant [leino2021globally, tsuzuku2018lipschitz] and introduce novel architectures or training procedures to tighten this bound. More recent works directly enforce tight Lipschitz constraints by designing 1-Lipschitz networks [zhang_rethinking_2022, xu_lot_2023]. Fazlyab et al. [fazlyab2023certified] (CRM) maximises a dynamic margin while regularising the Lipschitz constant; we use both SortNet [zhang_rethinking_2022] and CRM as certified-detection baselines (Section V). Notably, Delattre et al. [delattre2024lipschitz] recently proposed a hybrid approach that integrates Lipschitz networks with randomized smoothing. I-C Margin and Adversarial Robustness A complementary line of work analyses adversarial robustness through the margin of the classifier. Tsuzuku et al. [tsuzuku2018lipschitz] formalised the link — a classifier with margin q()q( x) at point x is provably robust to ℓ2 _2 perturbations of size up to q()/Lq( x)/L, motivating margin-maximising training. Xu et al. [xu2023boundary] empirically showed that classifiers’ adversarial robustness is governed by decision-boundary dynamics, with larger clean-input margins translating to harder-to-attack inputs. Lyu et al. [lyu_gradient_2020, lyu_gradient_2021] prove that gradient descent on homogeneous neural networks converges to a KKT point of the margin-maximising problem, a result we leverage to compute the local centroid in lcD_lc (Section IV-C). The same margin lens motivates adversarial training [PGD, xu2020adversarial, yan_adversarial_2021, shafahi2019adversarial] as a margin-enlarging primitive on the clean-input side. Our work shares the margin-centric view but reaches it from the opposite direction. Rather than asking how to push clean-input margins outward, we ask where an adversarial example must land given a bounded budget: Lipschitz continuity forces it to remain close to the decision boundary in margin space, which makes the margin function an attack-agnostic detection signal. The two perspectives converge — both single out the margin as the discriminator between robust and non-robust regimes — but ours yields a quantitative reduction from certified robustness to certified detection (Section IV) rather than a robustness-training prescription. As a consequence, every margin-enlarging primitive in this literature — adversarial training, Lipschitz constraints, Gaussian augmentation — composes with our framework: it lifts the underlying classifier’s clean-margin distribution and directly tightens our certified-detection frontier (Section V-E). I-D Certified Detection Shumailov et al. [shumailov2020towards] (CTT) introduced an early certified detection framework with a one-sided guarantee on the specificity side: samples flagged as adversarial are certified to be adversarial, with non-zero false-negative rate on real adversarial inputs. CrossCert [zhou2024crosscert] (FSE 2024) extends one-sided certified detection to patch attacks via a cross-checking mechanism. Our work parallels this line for ℓ2 _2-bounded perturbations on the complementary recall side: every in-budget adversarial example is provably refused, with non-zero FPR on clean inputs (cf. Section I-C). The two families thus offer complementary safety properties, and the right choice in deployment depends on whether false-positives or false-negatives are more costly. I Problem Formulation In this section we formalize the certified adversarial detection problem. We describe the threat model (§I-A), introduce the notation and preliminaries used throughout the paper (§I-B), and then state the formal detection problem and the certification objective (§I-C). I-A Threat Model Deployment scenarios. We consider deployments where a deep classifier f:ℝd→ℝmf:R^d ^m is exposed to untrusted inputs from users or sensors: • Autonomous-driving perception. A traffic-sign or pedestrian classifier ingests camera frames; a misclassification under a small physical-world perturbation (e.g., a sticker on a stop sign) can drive unsafe trajectory decisions and cause physical harm. • Content moderation. A platform-side image classifier flags uploads that violate policy; an adversary perturbs a violating image just enough to evade flagging while remaining recognisably the same content. • Biometric authentication & access control. A face- or voice-recognition gate decides whether to grant access; an adversary perturbs an unauthorised face to be classified as an authorised identity. In all three cases f and its parameters are fixed at deployment: retraining or modifying f is not available to the defender, and inference must meet a real-time latency budget (tens of milliseconds for AV perception, hundreds for moderation/auth). Attacker goal and capability. Given a clean input x that f classifies correctly, the attacker seeks a perturbation δ that flips the prediction, argmaxf(+δ)≠argmaxf() f( x+δ)≠ f( x), while keeping δ small in the ℓ2 _2 norm: ‖δ‖2≤ϵ\|δ\|_2≤ε. The budget ϵε is chosen by the defender and announced as a deployment-side protection level: within this declared ℓ2 _2 radius, the detector can reject adversarial inputs, with high TPR and formal guarantees for the certified subset. We primarily consider ℓ2 _2; extension to other ℓp _p norms is discussed in Section VI-D. Attacker knowledge and adaptivity. We assume a white-box attacker with full access to f’s architecture and parameters, consistent with the standard threat model in the adversarial ML literature [carlini2017towards, PGD]. The defender likewise has white-box access to f, which is natural in model-owner deployments where the defender controls the classifier and inserts the detector, although the service itself may remain black-box to external users. The attacker may use any attack procedure (FGSM, BIM, PGD, C&W, and adaptive variants aware of the detector). Crucially, our certified guarantee is attack-agnostic: by construction it holds for every ^=+δ x= x+δ with ‖δ‖2≤ϵ\|δ\|_2≤ε, independent of how δ was generated. An adaptive attacker therefore cannot bypass the certificate by switching optimisation strategy — any in-budget perturbation that flips the prediction is provably detected (Section V-D). Defender architecture: detection-then-refuse. The defender deploys f together with a detector :ℝd→0,1D:R^d→\0,1\. On input z, the pipeline returns f(z)f(z) when (z)=0D(z)=0 and refuses the input when (z)=1D(z)=1. Refusal is a hard reject signal: it does not return any class label and does not attempt to recover the original clean input. Refused inputs are escalated to a deployment-defined fallback — human review for content moderation, an additional verification factor for biometric authentication, or a safe-stop policy for AV perception. This detection-then-refuse paradigm contrasts with correction-based defenses (which try to recover the clean label from a perturbed input) and with soft-rejection defenses (which lower the output confidence without rejecting): we make no recovery attempt and emit a binary refuse signal. Defender objective. The defender’s primary objective is to refuse every successful in-budget adversarial example. This objective is fully certified when a valid global Lipschitz bound is available. For standard pretrained models, where LglobL_glob is unavailable, our detectors approximate this objective: they reject successful in-budget adversarial examples empirically, and we report cert% for the subset whose rejection is formally certified. Refusing some clean inputs (non-zero FPR) is a willing trade-off, calibrated by deployment context: an AV perception pipeline can absorb conservative refusal by deferring to the safe-stop fallback, content moderation can route flagged uploads to human reviewers, and biometric gates can request a second factor. A secondary objective is inference efficiency — the per-input overhead of D must remain within the latency budget of the host pipeline. We make no claim about robustness to attackers operating outside the announced ℓ2 _2 budget; that is the responsibility of the announced safety envelope. I-B Notation and Preliminaries A complete summary of symbols used throughout the paper is given in Appendix -B (Table IX). We denote a clean input by x and its adversarial counterpart by ^=+δ x= x+δ, where ϵε is the upper bound of perturbation. We further use z for a generic test input at inference time (clean or adversarial — the defender does not know which) and z′=z+σz =z+σ for a deliberate, defender-side perturbation of z used as a numerical surrogate for z’s clean counterpart; the attacker-side x and the defender-side z′z live on opposite sides of the inference pipeline. Let f:ℝd→ℝmf:R^d ^m be a neural network, with fi()f_i( x) the ithi^th output component (the confidence that x belongs to class i), and let θ denote the parameters of f. The ℓp _p norm of a vector is ‖p=(∑i|xi|p)1/p\| x\|_p= ( _i|x_i|^p )^1/p; unless otherwise stated we default to the ℓ2 _2 norm. The theoretical foundation of our method relies on the Lipschitz continuity of f. Intuitively, Lipschitz continuity bounds how much the output changes under a given input perturbation. Lipschitz continuity. A mapping f:ℝd→ℝmf:R^d ^m is L-Lipschitz continuous with respect to norm ∥⋅∥\|·\| if, for all 1,2∈ℝd x_1, x_2 ^d, ‖f(1)−f(2)‖≤L‖1−2‖.\|f( x_1)-f( x_2)\|≤ L\| x_1- x_2\|. (1) Margin. For a reference class k, the class-k margin of an input u with respect to f is q(u,k)=fk(u)−maxj≠kfj(u).q(u;k)\;=\;f_k(u)- _j≠ kf_j(u). (2) We write q(u)q(u) as shorthand for q(u,argmaxkfk(u))q(u; _kf_k(u)), i.e., the margin at u’s own predicted class; this is non-negative by construction. When the reference class is fixed and clear from context (e.g., the pseudo-label y^=argmaxf(z) y= f(z) of an input z throughout a detection step), we keep the shorthand q(⋅)q(·) but note that the value can become negative if the second argument differs from the reference class — as happens to q(z′,y^)q(z ; y) when the defender-side perturbation z′z flips z’s prediction (Algorithm 1). For Lemma IV.1, both q()q( x) and q(^)q( x) are evaluated at their own predicted classes (so both are non-negative and the bound is symmetric). Certified robustness. For a neural network f with Lipschitz constant L under ℓp _p, the model is provably robust to perturbations ‖δ‖p<1cLq()\|δ\|_p< 1cLq( x), i.e., argmaxf()=argmaxf(+δ),∀‖δ‖p<1cLq(), f( x)= f( x+δ), ∀\,\|δ\|_p< 1cLq( x), (3) where c=2p−1pc=2 p-1p depends on the norm. This is the standard robustness certificate [li_sok_2023, weng2020towards, tsuzuku2018lipschitz]; our work reduces detection to it. I-C Certified Adversarial Detection We now formalize the detection problem and the certification objective. Definition I.1 (Certified Detector). Let f:ℝd→ℝmf:R^d ^m be a classifier and let ϵ>0ε>0 be a perturbation budget. A detector :ℝd→0,1D:R^d→\0,1\ is a certified detector at budget ϵε (under ℓp _p) if, for every clean input x and every adversarial example ^=+δ x= x+δ satisfying ‖δ‖p≤ϵ\|δ\|_p≤ε and argmaxf(^)≠argmaxf() f( x)≠ f( x), we have (^)=1D( x)=1. Remark I.2 (One-sided guarantee and non-triviality). Definition I.1 is a one-sided certificate: D must reject every in-budget successful adversarial example, but may also reject some clean inputs (non-zero FPR). This parallels the complementary guarantee of CTT [shumailov2020towards], which certifies that clean samples are not flagged and admits non-zero FNR on adversarial inputs, and of CrossCert [zhou2024crosscert], which defines the same form of one-sided certified detection against patch attacks. It also mirrors certified robustness, which guarantees correct classification inside a radius while admitting non-trivial error outside it. Crucially, joint reporting of TPR and FPR in our evaluation rules out trivial detectors: the constant detector ≡1D≡ 1 satisfies Definition I.1 but has FPR =1=1. Evaluation metrics. Given a test set of clean inputs and successful adversarial examples, we report three quantities: • TPR: the fraction of successful adversarial examples (those that change f’s prediction) that D rejects. • FPR: the fraction of clean samples that D rejects. • cert%: the fraction of all successful in-budget adversarial examples that are both rejected and formally certified, i.e., the local Lipschitz estimate L′L used by D satisfies the per-detector certification condition on that pair (cf. Section IV-E). Design objective. Given a pretrained classifier f and a budget ϵε, we seek a certified detector (Definition I.1) that additionally (i) achieves low FPR at ϵε of practical interest, (i) is applicable to any pretrained f without retraining or architectural constraints, and (i) has inference-time overhead within the latency budget of real-time pipelines such as AV perception. Section IV develops the Lipschitz-margin analysis that realizes this objective. IV From Certified Robustness to Certified Detection We now formalize the Lipschitz-margin reduction sketched in Figure 1 and instantiate two approximated detectors that operate on any pretrained classifier without retraining. The load-bearing results are Lemma IV.1 (the core inequality) and Theorem IV.2 (its centroid-distance form); Claims 1–2 instantiate the two approximated detectors; the bias bounds (Section IV-D) and certification conditions (Section IV-E) tighten the connection between them. IV-A Certified Detection Fig. 1: Overview of certified adversarial detection. Taking a pre-trained classifier f as-is (no retraining and no architectural change), we exploit the Lipschitz–margin principle: a clean input x exhibits a large margin q()=fy()−maxi≠yfi()q( x)=f_y( x)- _i≠ yf_i( x), whereas a successful adversarial example x with bounded perturbation ‖δ‖\|δ\| is forced close to the decision boundary, yielding a small margin upper-bounded by q(^)≤cL‖δ‖−q()q( x)≤ cL\|δ\|-q( x) (Lemma IV.1). Because the clean counterpart x is unobserved at inference time, we instantiate two approximated detectors — AdvD_Adv (defender-side perturbation surrogate; Claim 1) and lcD_lc (local-centroid surrogate; Claim 2) — which flag adversarial inputs while accepting clean ones, and report TPR, FPR, and cert%, where cert% counts successful in-budget adversarial examples that are both rejected and formally certified. An L-Lipschitz network cannot change its output by more than L‖δ‖L\|δ\| under perturbation ‖δ‖\|δ\|. So if a clean input x has a large margin in its true-class direction, an in-budget adversarial example x cannot simultaneously achieve a large margin in any wrong-class direction — the budget is too small to “move” that much logit mass. Lemma IV.1 captures this in a one-sided sum bound. Lemma IV.1. (Certified Detection) Given a DNN f with Lipschitz constant L under ℓp _p norm ∥⋅∥p\|·\|_p, for an adversarial example x and its clean counterpart x, the margin satisfies q(^)≤cL‖δ‖−q(),q( x)≤ cL\|δ\|-q( x), (4) where q(^)q( x) is evaluated w.r.t. the predicted class of x (Section I-B) and c=2(p−1)/pc=2^(p-1)/p. The proof is deferred to Appendix -E. The bound is consistent with certified robustness: q(^)≥0q( x)≥ 0 by definition (Section I-B), so when ‖δ‖\|δ\| is below the certified-robustness threshold q()/(cL)q( x)/(cL), the right-hand side becomes negative and Lemma IV.1 cannot be satisfied — equivalently, no in-budget adversarial example exists, recovering the standard robustness certificate. Based on Lemma IV.1, a certified detector D can be formally defined as (z)=1,if z satisfies Lemma IV.1,0,otherwise,D(z)= cases1,&if $z$ satisfies Lemma~ lemma.certified_detection,\\ 0,&otherwise, cases (5) where input z may be either a clean sample or a perturbed sample. However, in practice, the clean counterpart x is unknown for an adversarial example, and it does not even exist for a clean sample. Therefore, this detector cannot be directly applied. To resolve this issue, we propose approximation strategies. IV-B Approximation to the Certified Detector Approximating the bound in Lemma IV.1 requires identifying the preimage x of z, which is generally infeasible because: 1. For z=^z= x, the underlying clean input x is unknown, as the adversarial perturbation is typically generated through an optimization procedure rather than a well-defined invertible mapping. 2. For z that is not adversarial, a corresponding x may not exist at all. We therefore propose two approximation methods: (1) approximating x by perturbing z; (2) introducing a numerically computable surrogate, namely the local centroid. IV-B1 Approximation by Perturbation We first approximate x by perturbing z: given z, we generate z′=z+σz =z+σ and use it as a surrogate for x in Lemma IV.1 (recall from Section I-B that z′z is the defender-side perturbation, not the attacker-side x). Claim 1. (Detector AdvD_Adv) For a DNN f and an input z with pseudo-label y^=argmaxf(z) y= f(z), given a defender-side perturbation z′z of z, if z=^z= x, then q(z,y^)+q(z′,y^)≤cL′‖δ‖,q(z; y)+q(z ; y)≤ cL \|δ\|, (6) where L′=(q(z,y^)−q(z′,y^))/(cmax(‖z−z′‖,‖δ‖))L =(q(z; y)-q(z ; y))/(c\, (\|z-z \|,\|δ\|)) approximates the Lipschitz constant from the local pair (the numerator is non-negative whenever z′z flips z’s prediction, so L′≥0L ≥ 0). Since L′≤L ≤ L and q(z′)≠q()q(z )≠ q( x), this introduces a bias compared to Lemma IV.1; the inequality in Claim 1 is therefore the approximate certification test used by AdvD_Adv rather than an unconditional bound. Proposition IV.7 establishes the conditions under which it is provably correct on adversarial inputs. IV-B2 Approximation by Local Centroid To better track the bias on classifiers with large clean margins, we introduce the concept of a local centroid, which can be computed numerically. The local centroid of x with respect to f is defined as the local maximizer of the margin function: ~=argmaxxq(x),q(x):=fy(x)−maxi≠yfi(x). x= _xq(x), q(x):=f_y(x)- _i≠ yf_i(x). Such local optima have been used in detecting backdoor attacks [wang2024m]. Here, we employ them as surrogates for x to strengthen the bound. By Lemma .4 (Appendix -G), gradient ascent on q(⋅,y^)q(·; y) at the input’s frozen pseudo-label y y is monotonically non-decreasing in the gradient-flow limit; starting from q(z,y^)>0q(z; y)>0, the centroid trajectory keeps the margin positive and z~ z stays predicted as y y, so y(^~)=y(^)y( x)=y( x) as required by Theorem IV.2. Following Lyu et al. [lyu_gradient_2020], when f is homogeneous in its parameters (a condition satisfied by ReLU networks without bias terms), this ascent additionally converges to a Karush–Kuhn–Tucker (KKT) point of min12‖2 12\| x\|^2 s.t. q()≥1q( x)≥ 1 — our setting is the input-space counterpart of their parameter-space result. Intuitively, points near the decision boundary tend to be farther away from their local centroids. This intuition leads to the following guarantee: Theorem IV.2. (Certified Detection via Local Centroid) Given a neural network f with Lipschitz constant L, for an adversarial example x and its clean counterpart x, the distance between x and its local centroid ^~ x satisfies ‖^~−^‖≥q(^~)+q()cL−‖δ‖.\| x- x\|≥ q( x)+q( x)cL-\|δ\|. (7) The proof (Appendix -E) applies Lemma IV.1 to the pair (,^~)( x, x) and combines it with the triangle inequality. The theorem strictly enlarges the certified region of Lemma IV.1: any pair (,^)( x, x) satisfying the lemma also satisfies the theorem, because q(^~)≥q(^)q( x)≥ q( x) by construction of the centroid. The right-hand side is non-vacuous (positive) whenever ‖δ‖<(q(^~)+q())/(cL)\|δ\|<(q( x)+q( x))/(cL), which is the regime in which the certified test fires. Analogous to the first approximation, we further use q(z′)q(z ) as a surrogate for q()q( x) and replace L with a local Lipschitz constant L′L . Claim 2 (Detector lcD_lc). For a DNN f and an input z with pseudo-label y^=argmaxf(z) y= f(z), given a defender-side perturbation z′z of z and the local centroid ~ z of z, if z=^z= x, then ‖~−z‖≥q(~,y^)+q(z′,y^)cL′−‖δ‖.\| z-z\|≥ q( z; y)+q(z ; y)cL -\|δ\|. (8) As with Claim 1, the inequality is the approximate certification test used by lcD_lc. The substitutions q()→q(z′)q( x)→ q(z ) and L→L′L→ L make it conditional on L′≥L(^~,)∗L ≥ L^*_( x, x) and on the flip property q(z′,y^)≤0q(z ; y)≤ 0 (Proposition IV.7, part (i)). Remark IV.3 (False Positive Rate in Practice). We note that the false positive rate (FPR) of our detectors can be relatively high in practice. This stems from two factors. First, many clean samples naturally lie close to the decision boundary — an inherent property of the trained model and the dataset — which longer training or stronger regularization can alleviate (Section V-E). Second, larger perturbation bounds ‖δ‖\|δ\| allow adversarial examples to drift farther from their local centroids, but the detection rule must then admit a wider band that inevitably flags more clean samples. The TPR/FPR trade-off is therefore governed by both the model’s clean-margin distribution and the announced budget ϵε. IV-C Approximated Detector We now translate Claims 1–2 into concrete algorithms. The main text describes the detector construction; full pseudocode for perturbed-sample generation, local-centroid optimization, and both detector variants is given below. Algorithm 1 Perturbed Sample Generation (z′=z+σz =z+σ) Input: Test input z (clean or adversarial), classifier f, radius ‖δ‖\|δ\|, step size α, number of steps T Output: Perturbed version z′z Compute pseudo-label y=argmaxf(z)y= f(z) Initialize z′←z ← z for t=1t=1 to T do Compute loss ℒ(f(z′),y)L(f(z ),y) Compute gradient g←∇z′ℒ(f(z′),y)g← _z L(f(z ),y) Update z′←z′+α⋅sign(g)z ← z +α·sign(g) gradient ascent step Project z′z onto the ℓ2 _2-ball ℬ2(z,‖δ‖)B_2(z,\|δ\|): Δ←z′−z ← z -z Δ←Δ⋅min1,‖δ‖Δ‖2 ← · \1, \|δ\|\| \|_2 \ z′←z+Δz ← z+ Clip pixel values: z′←clip(z′,0,1)z (z ,0,1) if argmaxf(z′)≠y f(z )≠ y then break break on flip: y(z′)≠y(z )≠ y, i.e., q(z′,y)≤0q(z ;y)≤ 0 end if end for Algorithm 2 Approximate Detector from Claim 1 (AdvD_Adv) Input: Input z, perturbation radius ‖δ‖\|δ\|, model f Output: Detection label (Adversarial / Clean) y^←argmaxf(z) y← f(z) pseudo-label, fixed reference for all q(⋅)q(·) below Generate perturbed version z′=z+σz =z+σ Estimate L′←q(z,y^)−q(z′,y^)c⋅max(‖z−z′‖2,‖δ‖)L ← q(z; y)-q(z ; y)c· (\|z-z \|_2,\|δ\|) τ←L′⋅c⋅‖δ‖τ← L · c·\|δ\| if q(z,y^)+q(z′,y^)≤τq(z; y)+q(z ; y)≤τ then Return: Adversarial else Return: Clean end if Algorithm 3 Local Centroid Optimization 1: Input: Input z, classifier f, step size η, number of ascent steps T 2: Output: Local centroid z~ z and distance dz=‖z~−z‖2d_z=\| z-z\|_2 3: Compute pseudo-label y←argmaxf(z)y← f(z) frozen throughout ascent 4: Initialize z~←z z← z 5: for t=1t=1 to T do 6: Compute margin q(z~)=fy(z~)−maxj≠yfj(z~)q( z)=f_y( z)- _j≠ yf_j( z) 7: Compute gradient g←∇z~q(z~)g← _ zq( z) 8: Update z~←z~+η⋅g z← z+η· g Gradient ascent to enlarge margin 9: Clip z~ z to valid input range: z~←clip(z~,0,1) z ( z,0,1) 10: end for 11: Compute distance dz←‖z~−z‖2d_z←\| z-z\|_2 Algorithm 4 Approximate Detector from Claim 2 (lcD_lc) 1: Input: Input z, perturbation budget ‖δ‖\|δ\|, model f 2: Output: Detection label (Adversarial / Clean) 3: y^←argmaxf(z) y← f(z) pseudo-label, fixed reference for all q(⋅)q(·) below 4: Generate perturbed version z′=z+σz =z+σ 5: Compute local centroid z~ z and distance dz=‖z~−z‖2d_z=\| z-z\|_2 6: Estimate L′←q(z~,y^)−q(z′,y^)c⋅max(‖z~−z′‖2,‖δ‖)L ← q( z; y)-q(z ; y)c· (\| z-z \|_2,\|δ\|) 7: RHS←q(z~,y^)+q(z′,y^)c⋅L′−‖δ‖RHS← q( z; y)+q(z ; y)c· L -\|δ\| 8: if dz≥RHSd_z then 9: Return: Adversarial 10: else 11: Return: Clean 12: end if IV-C1 Basic Detector (AdvD_Adv) Perturbed-sample generation. Given test input z, we generate z′∈ℬ2(z,‖δ‖)z _2(z,\|δ\|) by running PGD [PGD] on the predicted class (Algorithm 1). z′z replaces the unknown clean counterpart x in Claim 1. Local Lipschitz estimation. Since the global Lipschitz constant is typically intractable, we estimate a local Lipschitz constant from the pair (z,z′)(z,z ) at the input’s pseudo-label y^=argmaxf(z) y= f(z): L′≈q(z,y^)−q(z′,y^)c⋅max(‖z−z′‖2,‖δ‖),c=2.L ≈ q(z; y)-q(z ; y)c· (\|z-z \|_2,\|δ\|), c= 2. This data-dependent surrogate replaces L in Claim 1; Algorithm 2 implements the resulting detector AdvD_Adv. IV-C2 Refined Detector (lcD_lc) The Refined Detector is the practical-side counterpart of the Lemma IV.1 → Theorem IV.2 refinement. In Claim 1, z′z alone plays a double role: it is both the surrogate for x in q(z′)q(z ) and the second point used to estimate L′L . This double-use ties the bias on both quantities to the same geometric distance between z′z and the unobserved x, making the substitution non-negligible whenever z′z is not approximately on the segment (,^)( x, x). Introducing the local centroid ~ x (Section IV-B) decouples the two roles: ~ x supplies a precisely-computable, high-margin anchor for the centroid-distance bound, while z′z continues to drive the local Lipschitz estimator. We compute ~ x by iterative gradient ascent on q(⋅)q(·) starting from z (Algorithm 3); Algorithm 4 then implements lcD_lc following Claim 2. IV-D Bias Analysis of Approximated Detector The substitution q(z′)→q()q(z )\!→\!q( x) contributes a bias bounded by |q(z′)−q()||q(z )-q( x)|; we focus here on the harder term, the deviation between the local estimator L′L and its theoretical counterpart L. IV-D1 Bias Analysis of the Basic Detector. Since Claim 1 replaces x with its perturbed counterpart z′z , the estimated local Lipschitz constant may deviate from the ideal one computed on (,^)( x, x). We characterize this deviation as follows. Lemma IV.4 (Bounded Bias of the Approximated Lipschitz Constant). Let a=^a= x, b=b= x, and z′=z+σz =z+σ denote the adversarial, clean, and perturbed samples, respectively. Define α=‖a−b‖α=\|a-b\|, β=‖a−z′‖β=\|a-z \|, and γ=‖b−z′‖γ=\|b-z \|, and let L∗=q(a)+q(b)cα,L′=|q(a)−q(z′)|cβ.L^*= q(a)+q(b)c\,α, L = |q(a)-q(z )|c\,β. Then the deviation between L′L and L∗L^* satisfies |L′−(α/β)L∗|≤γβLglob+αβ(L∗−D), |L -(α/β)\,L^* |\;≤\; γβ\,L_glob+ αβ\,(L^*-D), where D=|q(a)−q(b)|cα≤L∗D= |q(a)-q(b)|c\,α≤ L^* and LglobL_glob is a global Lipschitz constant of q(⋅)q(·). The proof is deferred to Appendix -H. Intuitively, the first term γβLglob γβL_glob captures the geometric bias introduced by using z′z instead of the clean sample x, while the second term αβ(L∗−D) αβ(L^*-D) reflects the margin bias between sum- and difference-based margin quotients. When z′z lies approximately along the segment (,^)( x, x), both terms diminish, and L′L provides a tight local approximation of the ideal Lipschitz constant. IV-D2 Bias Analysis of the Refined Detector Recall that the ideal constant in Lemma IV.1 can be written as L∗=q(^)+q()c‖^−‖,L^*= q( x)+q( x)c\| x- x\|, where x is the clean input and x its adversarial counterpart. In contrast, our detector employs L′=|q(z~)−q(z′)|c‖z~−z′‖,L = |q( z)-q(z )|c\| z-z \|, where z′z is the perturbed version of z and z~ z is the local centroid. The difference between these two quantities can be bounded as L′−L∗≤(κ−1)Lglob+(Lglob−L∗),L -L^*\;≤\;(κ-1)L_glob+(L_glob-L^*), κ=‖z~−z‖+‖z′−z‖z~−z′‖≥1,κ= \| z-z\|+\|z -z\|\| z-z \|\,≥ 1, where LglobL_glob is the global Lipschitz constant. This inequality shows that the bias arises from two sources: (i) the geometric factor κ, which depends on the relative positions of z~,z, z,z, and z′z , and (i) the inherent looseness of the global bound LglobL_glob compared to L∗L^*. In particular, when z′z lies close to z~ z, κ may become large, leading to a systematic overestimation of L∗L^*. Conversely, when z′z is well separated, L′L better approximates L∗L^*. The above analysis indicates that the bias of the refined detector stems from both geometric and Lipschitz factors. To make this relationship more explicit and to enable practical estimation, we next derive a deterministic and fully computable upper bound on the deviation between the approximation and the ideal certified term. Theorem IV.5 (Deterministic bound for the approximation). Let z=^z= x be an adversarial input with clean counterpart x (‖z−‖≤‖δ‖\|z- x\|≤\|δ\|), and z′=z+σz =z+σ with ‖σ‖≤‖δ‖\|σ\|≤\|δ\|. Assume that (A1) (Lipschitz of margin) q is LqL_q-Lipschitz under ∥⋅∥\|·\| with Lq≤cL¯L_q≤ c L: |q(u)−q(v)|≤Lq‖u−v‖|q(u)-q(v)|≤ L_q\|u-v\| for all u,vu,v in a neighborhood of the data manifold. (A2) (Global Lipschitz bound ) There exists a computable global Lipschitz upper bound Lglob≤L¯L_glob≤ L, and L′≤LglobL ≤ L_glob (i.e., the local estimator does not exceed the global upper bound). Then 0<L′≤Lq/c≤L¯0<L ≤ L_q/c≤ L and, for ΔT:=|q(z~)+q(z′,y^)cL′−q(z~)+q()cLglob|. _T\;:=\; |\; q( z)+q(z ; y)c\,L \;-\; q( z)+q( x)c\,L_glob\; |. We write the relative gap η:=1−L′/L¯∈[0,1)η:=1-L / L∈[0,1) and have the fully computable bound ΔT≤1c[2LqL′‖δ‖+ηL′(q(z~)+|q(z′,y^)|+Lq‖δ‖)]. _T\;≤\; 1c [\; 2L_qL \,\|δ\|\;+\; η\,L \,\, (q( z)+|q(z ; y)|+L_q\,\|δ\| )\; ]. (9) ΔT _T is the gap between the approximated certified threshold (computed at inference from L′L and z′z ) and the ideal one in Theorem IV.2 (computed from the global LglobL_glob and the unobserved clean margin q()q( x)). The two summands isolate two error sources. The first, 2LqcL′‖δ‖ 2L_qcL \|δ\|, is the geometric stretch from substituting z′z for the unobserved x (the factor 22 absorbs the triangle →z→z′ x→ z→ z ), scaled by how tight L′L is relative to the margin’s Lipschitz constant LqL_q. The second, scaled by the relative gap η=1−L′/L¯∈[0,1)η=1-L / L∈[0,1), is the looseness from replacing the global upper bound L¯ L with the local estimator L′L : when L′L approaches L¯ L, η→0η→ 0 and the second term vanishes. Both terms are observable at inference from ‖δ‖\|δ\|, L′L , L¯ L, and the margins. IV-E When the Practical Detectors Provably Detect Adversarial Examples? We now connect the approximated detectors AdvD_Adv and lcD_lc back to the formal certificate of Lemma IV.1 and Theorem IV.2. Two gaps separate the approximated detectors from the formal certificate: the local estimator L′L may fall short of the pairwise Lipschitz L∗L^* (the deviation |L′−L∗||L -L^*| is bounded for AdvD_Adv by Lemma IV.4, and the resulting threshold gap for lcD_lc is bounded by Theorem IV.5), and the surrogate q(z′)q(z ) replaces the unobserved q()q( x) (closed by the break-on-flip rule in Algorithm 1, which guarantees q(z′,y^)≤0q(z ; y)≤ 0 whenever the inner attack succeeds within T steps). To state the certification condition cleanly, we first define the pairwise Lipschitz constants involved. Proposition IV.6 (Pairwise Lipschitz). For an adversarial example x, its clean counterpart x, and the local centroid ^~ x of x, define the pairwise Lipschitz constants L(,^)∗:=q(^)+q()c‖^−‖,L(^~,)∗:=q(^~)+q()c‖^~−‖.L^*_( x, x)\;:=\; q( x)+q( x)c\,\| x- x\|, L^*_( x, x)\;:=\; q( x)+q( x)c\,\| x- x\|. Both are saturations of Lemma IV.1: L(,^)∗L^*_( x, x) is the minimum L for which the lemma holds on the (,^)( x, x) pair, and L(^~,)∗L^*_( x, x) is the minimum L for which the lemma holds on the (^~,)( x, x) pair (both ,^~ x, x have differing predicted classes since y(^~)=y(^)≠y()y( x)=y( x)≠ y( x)). Theorem IV.2 can be derived from a single application of Lemma IV.1 on the (,^~)( x, x) pair plus the triangle inequality (see Appendix -E); it therefore holds for any L≥L(^~,)∗L≥ L^*_( x, x). Proposition IV.7 (When approximated detectors are certified). For every successful in-budget adversarial example x: (i) L′≥L(,^)∗L ≥ L^*_( x, x) implies the bound of Claim 1 (AdvD_Adv); (i) L′≥L(^~,)∗L ≥ L^*_( x, x) together with the flip property q(z′,y^)≤0q(z ; y)≤ 0 — guaranteed by Algorithm 1’s break-on-flip whenever the inner attack succeeds within T steps — implies the bound of Claim 2 (lcD_lc). Proof sketch. For input z=^z= x: (i) The max-clamp denominator in L′L combined with L′≥L(,^)∗L ≥ L^*_( x, x) and Lemma IV.1 forces q(z′,y^)≤−q()≤0q(z ; y)≤-q( x)≤ 0, so the flip property emerges as a consequence; substituting q(z′,y^)≤−q()q(z ; y)≤-q( x) into the detector’s threshold then recovers the Claim 1 bound. (i) The flip property gives q(z′,y^)≤0≤q()q(z ; y)≤ 0≤ q( x), so substituting q()→q(z′,y^)q( x)→ q(z ; y) in the detector’s right-hand side only loosens it, and L′≥L(^~,)∗L ≥ L^*_( x, x) closes the chain back to Theorem IV.2. Full proof in Appendix -F. ∎ Remark IV.8 (What cert% certifies). The framework operates in two regimes. (i) Global Lipschitz LglobL_glob. On networks with a known global Lipschitz constant (e.g., 1-Lipschitz SortNet, Table I), Lglob≥L(,^)∗L_glob≥ L^*_( x, x) and Lglob≥L(^~,)∗L_glob≥ L^*_( x, x) for every pair, so plugging L=LglobL=L_glob certifies both Lemma IV.1 and Theorem IV.2 for every in-budget adversarial example. (i) Local estimator L′L . On standard pretrained classifiers LglobL_glob is intractable, so we estimate L′L at inference. The cert% metric (Section V) measures the empirical fraction of all successful in-budget adversarial examples that are both rejected and satisfy the per-detector certification hypothesis of Proposition IV.7: L′≥L(,^)∗L ≥ L^*_( x, x) for AdvD_Adv, and L′≥L(^~,)∗L ≥ L^*_( x, x) together with the flip property q(z′,y^)≤0q(z ; y)≤ 0 for lcD_lc. All cert% numbers reported in the abstract, experiment tables, and discussion use these per-detector definitions; we keep the shorthand “L′≥L∗L ≥ L^*” in subsequent table captions to avoid clutter. Empirically, on every rejected adversarial that satisfies L′≥L∗L ≥ L^*, q(z′,y^)≤0q(z ; y)≤ 0 always holds in all our experiments, so the conjoint hypothesis collapses to L′≥L∗L ≥ L^* in practice. By Proposition IV.7, cert% is exactly the fraction on which the approximated detectors provide a formal certificate. V Experiments V-A Experimental Setup We evaluate on MNIST [lecun1998mnist] (LeNet-5), CIFAR-10 [CIFAR10] (VGG16), and ImageNet-1k [ImageNet] (PyTorch-pretrained ResNet-50; ViT-B/16 in the A2D comparison). Adversarial examples are generated under ℓ2 _2 with FGSM [FGSM], BIM [IFGSM], PGD (4040 steps, 1010 restarts) [PGD], and CW (4040 steps) [carlini2017towards]. Metrics. We report TPR, the fraction of successful adversarial examples that are detected (success means the prediction changes), FPR, the fraction of clean samples flagged as adversarial, and cert%. cert% is reported only on detectors whose guarantee depends on L′L (i.e., AdvD_Adv and lcD_lc). Implementation. Both detectors are implemented in PyTorch on top of the pretrained classifiers without any retraining or fine-tuning. The perturbed surrogate z′z is generated by T=10T=10 BIM steps with step size α=ϵ/Tα=ε/T inside the ℓ2 _2-ball of radius ‖δ‖\|δ\| (Algorithm 1); the local centroid z~ z uses Tcent=10T_cent=10 gradient-ascent steps on q(⋅)q(·) at step size 0.10.1 with [0,1]d[0,1]^d clipping (Algorithm 3). Unless otherwise noted, all results are evaluated on a single NVIDIA V100 GPU, averaged over 5 runs with different random seeds. Detection Baselines. We compare against five external baselines spanning certified and empirical detection. Certified detection remains a relatively nascent setting, so the baselines differ in what they certify. CTT [shumailov2020towards] is the closest prior certified-detection method, but it provides a complementary specificity-side certificate rather than our recall-side guarantee in Definition I.1. For a broader defense-level comparison, we therefore instantiate certified-robustness methods (RS, SortNet, CRM) as detectors via their certified radii, and include state-of-the-art empirical detectors (ContraNet and A2D). (i) SortNet [zhang_rethinking_2022] is a 1-Lipschitz network whose certified robustness radius gives a natural detection rule (flag inputs whose certified ℓ2 _2 radius r<ϵr<ε). SortNet doubles as the testbed for our fully certified Lemma IV.1 (Table I), since LglobL_glob is exactly known and used directly. (i) CRM [fazlyab2023certified] is a Lipschitz-regularised classifier with dynamic margin maximisation; its certified-radius detection rule mirrors SortNet’s. (i) CTT [shumailov2020towards] provides the complementary specificity-side certified-detection baseline; we evaluate both CTT-loose and CTT-strict thresholding variants. (iv) ContraNet [yang2022you] trains a class-conditional generator and detects adversarial inputs via reconstruction error; it does not scale to ImageNet-1k. (v) A2D [zhao2024attack] is a recent state-of-the-art empirical detector that uses the perturbation budget required to flip the prediction as the detection signal; it is one of the few empirical detectors evaluated on full ImageNet-1k and serves as our headline empirical comparison (Table IV(b)). In addition to these five external baselines, we adapt the randomized smoothing of Cohen et al. [cohen2019certified] into a certified detection rule for completeness: compute the certified radius r for each input and output Adversarial iff r<ϵr<ε. We use n0=64n_0=64, n=512n=512, and σ=0.25σ=0.25 throughout the main body; the conservative variant (smoothed-mismatch + certified radius) is reported in the Conservative RS detector paragraph below. V-B Main Results We evaluate our two approximated detectors AdvD_Adv and lcD_lc on MNIST, CIFAR-10, and ImageNet-1k. Across datasets, our methods match or outperform existing detection baselines on the TPR/FPR frontier. Unlike RS, CTT, or ContraNet, our detectors require neither Monte Carlo sampling, retraining, nor additional models to distinguish adversarial examples. TABLE I: Fully certified detection on 1-Lipschitz SortNet (CIFAR-10). With LglobL_glob exactly known, Lemma IV.1 (using L=LglobL=L_glob) achieves 100%100\% certified detection at FPR substantially below the baseline detectors built on SortNet’s and CRM’s certified radii. Our approximated detectors AdvD_Adv and lcD_lc use the local estimator L′L and reduce FPR further; we report cert% as the fraction of all successful in-budget adversarial examples that are both rejected and formally certified. ϵε SortNet [zhang_rethinking_2022] CRM [fazlyab2023certified] Lem IV.1, LglobL_glob (ours) AdvD_Adv (ours) lcD_lc (ours) TPR FPR TPR FPR TPR FPR TPR FPR cert% TPR FPR cert% 0.1 100.0 22.0 100.0 25.2 100.0 10.5 99.0 9.3 58.1 100.0 10.1 36.5 0.3 100.0 59.0 100.0 68.0 100.0 31.5 100.0 21.3 59.0 100.0 25.8 41.0 0.5 100.0 86.0 100.0 96.0 100.0 58.5 99.5 35.3 65.3 100.0 40.7 50.0 1.0 100.0 100.0 100.0 100.0 100.0 95.0 100.0 59.0 71.5 100.0 63.5 57.5 Fully Certified Detection on Lipschitz Networks. On 1-Lipschitz SortNet [zhang_rethinking_2022], where LglobL_glob is exactly known, applying Lemma IV.1 with L=LglobL=L_glob yields fully certified detection: every successful ℓ2 _2 adversarial example within budget ϵε is provably rejected (TPR =100%=100\%). Table I compares this fully certified path against the baseline detectors built on top of SortNet’s and CRM’s [fazlyab2023certified] own certified-radius computations (flag if the certified radius r<ϵr<ε), and against our approximated detectors AdvD_Adv and lcD_lc that use the local Lipschitz estimator L′L in place of LglobL_glob. All methods reach 100%100\% TPR (Except AdvD_Adv with TPR ≥99%≥ 99\%); the differentiator is FPR. Our fully certified path delivers substantially lower FPR than either baseline (e.g., 31.5%31.5\% vs. 59.0%59.0\% / 68.0%68.0\% at ϵ=0.3ε=0.3). The practical AdvD_Adv and lcD_lc use the same detection-rule families with local L′L estimates, which can further tighten FPR but are certified only on samples where the per-detector L′L condition holds. TABLE I: MNIST (LeNet-5): detection at representative ℓ2 _2 budgets. TPR on BIM; FPR on clean inputs; cert% is the fraction of all successful in-budget adversarial examples that are both rejected and formally certified (L′≥L∗L ≥ L^*). RS (Cohen) reported at σ=0.25σ=0.25. Full per-attack and per-σ results in Appendix -D, Tables XII–XIII. ϵε AdvD_Adv (ours) lcD_lc (ours) RS (Cohen) TPR FPR cert% TPR FPR cert% TPR FPR 0.1 100.0 0.5 92.0 100.0 1.0 90.0 44.5 4.0 0.5 100.0 8.0 94.0 100.0 8.5 86.0 100.0 22.0 1.0 100.0 17.0 97.0 100.0 17.5 80.0 100.0 98.0 2.0 100.0 47.0 98.0 100.0 47.5 75.0 100.0 98.0 MNIST. Both AdvD_Adv and lcD_lc achieve perfect detection on MNIST, maintaining 100%100\% TPR across all attacks (FGSM, BIM, PGD, CW) at every ϵε tested (Table I). FPR stays at most 1%1\% for ϵ≤0.1ε≤ 0.1 and grows gradually thereafter (17%17\% at ϵ=1.0ε=1.0). The Cohen detector by contrast attains ≤45%≤ 45\% TPR at ϵ=0.1ε=0.1 and reaches 98%98\% FPR by ϵ=1.0ε=1.0 at the same noise level. Full per-attack and per-σ breakdowns are in Appendix -D. TABLE I: CIFAR-10: detection at representative ℓ2 _2 budgets on VGG16. TPR on BIM attacks (averaged over ∼ 500 successful adversarials per ϵε); FPR on the full CIFAR-10 test set; cert% is the fraction of all successful in-budget adversarial examples that are both rejected and formally certified (L′≥L∗L ≥ L^*). RS (Conservative) is the strengthened RS variant that combines smoothed-classifier mismatch with the certified radius (Section V). Full per-attack results in Appendix -D. ϵε AdvD_Adv (ours) lcD_lc (ours) RS (Cohen) RS (Conservative) ContraNet TPR FPR cert% TPR FPR cert% TPR FPR TPR FPR TPR FPR 0.05 100.0 15.3 63.2 100.0 15.6 62.4 38.5 46.0 93.5 93.2 87.0 9.0 0.1 100.0 29.5 76.4 100.0 29.9 75.0 53.0 60.2 95.0 93.8 87.8 9.0 0.3 100.0 74.8 83.4 100.0 75.8 80.4 95.8 96.0 99.6 99.2 74.6 9.0 0.5 100.0 92.7 82.6 100.0 93.6 78.8 100.0 100.0 100.0 100.0 85.0 9.0 CIFAR-10. Table I reports representative results on CIFAR-10 (VGG16). Both AdvD_Adv and lcD_lc reach 100%100\% TPR at every ϵε, with FPR rising from ∼15% 15\% at ϵ=0.05ε=0.05 to ∼93% 93\% at ϵ=0.5ε=0.5. On a standard-trained VGG16, ϵ≤0.1ε≤ 0.1 gives a practical operating point with FPR ≤30%≤ 30\%. We return to the FPR–budget trade-off and ways to shift this frontier in Section VI-B. In contrast, RS (Cohen) maintains moderate TPR but incurs very high FPR (3535–100%100\%) even at small perturbations. Our cert% at ϵ=0.1ε=0.1 on VGG16 reaches 75%75\%, while empirical TPR remains 100%100\%. Compared with ContraNet, our detectors achieve 100%100\% empirical TPR and additionally certify the cert% subset, whereas ContraNet provides only empirical separation. Additional CIFAR-10 ResNet-18 and MNIST VGG-style CNN results in Appendix -D, Table XIV, further validate that the trend is not tied to the primary classifier. Full per-attack tables are in Appendix -D. TABLE IV: Detection on ImageNet-1k (500 images) with PyTorch pretrained models. TPR on ℓ2 _2 BIM attacks; FPR on clean samples; cert% is the fraction of all successful in-budget adversarial examples that are both rejected and formally certified (L′≥L∗L ≥ L^*). The full ϵ∈[0.1,1.0]ε∈[0.1,1.0] breakdown for ResNet-50 is in Appendix -D, Table XVII. (a) ResNet-50 pretrained model. ϵε AdvD_Adv (ours) lcD_lc (ours) RS (Cohen) TPR FPR cert% TPR FPR cert% TPR FPR 0.1 99.5 9.0 20.4 99.7 9.4 63.8 34.0 17.0 0.3 99.8 24.6 42.9 99.6 23.7 72.7 62.5 36.0 0.5 99.6 34.4 38.1 99.3 32.8 80.4 85.5 51.0 1.0 99.8 54.8 41.9 99.8 53.5 76.3 100.0 100.0 (b) ViT-B/16 pretrained model (vs. A2D [zhao2024attack]). ϵε AdvD_Adv (ours) lcD_lc (ours) A2D TPR FPR cert% TPR FPR cert% TPR FPR 0.1 97.4 2.8 35.1 100.0 3.6 63.0 89.5 11.2 0.3 97.5 6.5 38.0 99.0 8.2 67.3 90.3 11.2 0.5 97.0 14.0 39.8 99.0 15.4 72.3 90.3 11.2 1.0 98.0 25.0 58.8 99.3 26.6 77.5 93.1 11.2 ImageNet-1k. Table IV reports representative ϵε values on PyTorch pretrained ResNet-50; the full ϵ∈[0.1,1.0]ε∈[0.1,1.0] at step 0.10.1 is in Appendix -D, Table XVII. Both AdvD_Adv and lcD_lc achieve ≥98.8%≥ 98.8\% TPR while keeping FPR within 99–55%55\% even at ϵ=1.0ε=1.0, where the Cohen detector saturates to 100%100\% FPR. On the certificate, lcD_lc formally certifies 6464–80%80\% of all successful in-budget adversarial examples while empirically rejecting almost all of them. The magnitude is comparable to reported RS certified-accuracy rates on the same backbone, but the metrics measure different events and are not directly interchangeable. ViT-B/16 vs. a SOTA empirical detector (A2D). We further evaluate on a PyTorch pretrained ViT-B/16 and compare against A2D [zhao2024attack], a recent state-of-the-art empirical adversarial detector. Table IV(b) (right half of Table IV) shows that our lcD_lc reaches 100%100\% TPR at 3.6%3.6\% FPR for ϵ=0.1ε=0.1 on ViT-B/16, while A2D plateaus at 89.5%89.5\% TPR with 11.2%11.2\% FPR. lcD_lc maintains a higher TPR than A2D at every ϵε and a lower FPR at the small budgets (ϵ≤0.3ε≤ 0.3) most relevant to security deployments; unlike A2D, which provides no formal guarantee, lcD_lc additionally certifies at least 63%63\% of all successful in-budget adversarial examples. Conservative RS detector. The “RS (Conservative)” columns of Table I report a stronger RS variant that combines two certified-robustness checks: (i) compare the base classifier’s prediction f(z)f(z) to the smoothed prediction fs(z)f_s(z) and flag mismatches; (i) for those flagged inputs compute the certified radius r [cohen2019certified] and output Adversarial iff r<ϵr<ε. The conservative variant raises TPR to 9393–100%100\%, but FPR exceeds 93%93\% across every ϵε, effectively rejecting nearly every clean input. Even a strengthened RS detector therefore retains a substantially worse safety–usability trade-off than our certified detection. Comparison with CTT. CTT [shumailov2020towards] is the closest prior certified-detection framework, but it certifies a complementary specificity-side property. Under ℓ2 _2 FGSM and PGD on MNIST and CIFAR-10, our detectors match or beat CTT in TPR at comparable FPR without retraining; the full comparison is in Appendix -D, Table XI. TABLE V: Average per-sample detection time (seconds, mean ± std over n=500n=500 inputs). Experiments are conducted on a single NVIDIA V100 GPU. Method MNIST CIFAR-10 ImageNet-1k AdvD_Adv (base) 0.020 ± 0.002 0.071 ± 0.023 0.190 ± 0.073 AdvD_Adv (strong L′L ) 0.048 ± 0.002 0.183 ± 0.017 0.451 ± 0.084 lcD_lc (base) 0.063 ± 0.006 0.151 ± 0.026 0.421 ± 0.074 lcD_lc (strong L′L ) 0.155 ± 0.008 0.341 ± 0.036 0.765 ± 0.087 RS (Cohen) 0.335 ± 0.003 0.437 ± 0.132 3.757 ± 0.502 Trends across perturbation scales. Empirical TPR climbs to 100%100\% within a small budget on all datasets; FPR rises smoothly with ϵε, as the detection band must widen to admit the larger adversarial radius. Full perturbation-scale curves are in Appendix -D, Figure 2. The per-sample detection-statistic distribution for lcD_lc is also reported in Appendix -D, Figure 3; the clean and adversarial distributions are clearly separated across FGSM, PGD, BIM, and CW. Appendix -D, Table XVI, further reports the realised L′/L∗L /L^* distribution on CIFAR-10. Most samples concentrate near or above the sufficient threshold 11, and the below-threshold cases remain close to 11 on average, explaining why the practical detector keeps high empirical TPR while cert% captures only the formally certified subset. V-C Stronger L′L Estimation via Multi-Probe Search To increase certified coverage without changing the detector families, we replace the single-probe local estimate with Lstrong′=maxkLk′L _strong= _kL _k. A larger L′L makes L′≥L∗L ≥ L^* easier to satisfy but also enlarges the rejection threshold. Table VI shows this trade-off: cert% reaches 99.599.5–100%100\% on MNIST, gains 14.514.5–34.834.8 points on CIFAR-10, and gains up to 66.366.3 points on ImageNet, with at most 7.37.3 FPR points added and negligible TPR change. Table V gives cross-dataset latency; Appendix -D, Table XV, shows diminishing returns beyond K=1,T=6K=1,T=6. TABLE VI: Stronger L′L estimation improves certified coverage. Only the local estimate is replaced by a multi-probe Lstrong′L _strong (K=1,T=6K=1,T=6 unless stated), trading cert% gains for FPR/runtime. Dataset ϵε AdvD_Adv lcD_lc Δ Δ cert% base→ Δ Δ cert% base→ MNIST 0.50 +0.0 +0.9 92.0→ 100.0 +0.0 +1.5 94.0→ 100.0 1.00 +0.0 +2.3 97.0→ 99.5 +0.0 +2.5 98.0→ 100.0 CIFAR-10 0.05 +0.0 +0.4 63.2→ 98.0 +0.0 +1.0 62.4→ 87.0 0.10 +0.0 +2.0 76.4→ 93.5 +0.0 +2.0 75.0→ 89.5 0.30 +0.0 +5.8 83.4→ 98.0 +0.0 +7.3 80.4→ 97.0 0.50 +0.0 +5.7 82.6→ 100.0 +0.0 +5.0 78.8→ 100.0 ImageNet 0.10 +0.0 +1.0 20.2→ 86.5 +0.3 +1.9 64.0→ 82.0 0.50 +0.2 +4.7 38.2→ 95.0 +0.5 +5.8 80.8→ 89.6 V-D Adaptive Attack Evaluation Adaptive strategy. The detectors fire when the observed margin is too small for the declared budget (Lemma IV.1). A detector-aware attacker therefore seeks a misclassification with the largest possible wrong-class margin. Since q()q( x) is fixed, maximizing the left-hand side of Lemma IV.1, q(+δ)+q()q( x+δ)+q( x), is exactly maximizing q(+δ)q( x+δ): max‖δ‖2≤ϵq(+δ)+q(), _\|δ\|_2≤ε\;q( x+δ)+q( x), using 100100 Adam steps with ℓ2 _2 projection and [0,1]d[0,1]^d clipping. We write ^adp=+δ x_adp= x+δ for the attacker-side input, distinct from the defender-side surrogate z′z . We report the classification attack success rate before detection as ASRcls, and the end-to-end evasion rate after detection as ASR=jointASRcls⋅(1−TPR)_joint=ASR_cls·(1-TPR). TABLE VII: Detector-aware adaptive attack evaluation. ASR=jointASRcls⋅(1−TPR)_joint=ASR_cls·(1-TPR) is end-to-end evasion after detection; cert% is shown before/after stronger L′L . Dataset ϵε BIM ASR Adp. ASR AdvD_Adv lcD_lc TPR ASRjoint cert% base→ TPR ASRjoint cert% base→ CIFAR-10 0.05 8.9 11.4 100.0 0.0 3.0→ 96.5 100.0 0.0 5.0→ 67.5 0.10 20.3 26.1 100.0 0.0 9.0→ 98.0 100.0 0.0 8.5→ 77.5 0.30 61.0 80.7 100.0 0.0 16.5→ 97.5 100.0 0.0 17.0→ 97.0 0.50 78.5 98.5 100.0 0.0 24.0→ 99.5 100.0 0.0 30.5→ 99.0 ImageNet 0.10 4.7 14.1 87.4 1.8 2.8→ 89.1 99.0 0.1 11.6→ 92.6 0.30 14.3 33.6 91.6 2.8 7.4→ 92.8 97.2 0.9 20.0→ 95.6 0.50 23.8 46.6 94.0 2.8 12.6→ 92.5 98.0 0.9 25.4→ 95.7 1.00 45.8 70.3 98.8 0.8 20.5→ 94.1 99.6 0.3 33.2→ 96.4 Table VII shows that the adaptive objective raises classification ASR over BIM, especially on ImageNet, yet end-to-end evasion remains low: ASRjoint=0_joint=0 on CIFAR-10 and at most 2.8%2.8\%/0.9%0.9\% for AdvD_Adv/lcD_lc on ImageNet. The stronger multi-probe estimate restores much of the certified subset. V-E Robustness-Oriented Training Improves Detection TABLE VIII: Robust training boosts our detection on CIFAR-10 (VGG16). TPR (%) on ℓ2 _2 PGD attacks; FPR (%) on clean inputs. Two robust-training primitives applied to the same VGG16 base model: ℓ2 _2 PGD adversarial training (radius 0.50.5, AT columns) and Gaussian augmentation (σ=0.25σ=0.25). RS baselines do not apply to PGD-adversarial-trained models. Adv-trained (ℓ2 _2 PGD, r=0.5r=0.5) Gaussian aug (σ=0.25σ=0.25) AdvD_Adv (AT) lcD_lc (AT) AdvD_Adv lcD_lc RS (Cohen) RS (Conservative) ϵε TPR FPR TPR FPR TPR FPR TPR FPR TPR FPR TPR FPR 0.05 92.0 4.0 99.0 4.0 99.1 5.8 99.5 7.2 38.4 17.0 91.5 27.2 0.1 94.9 7.0 99.2 7.6 99.6 11.2 100.0 13.8 47.6 21.4 93.8 30.8 0.3 97.0 18.0 99.0 20.0 99.8 29.5 100.0 35.4 80.8 43.8 98.6 46.4 0.5 98.4 29.8 99.6 32.2 100.0 43.9 100.0 51.5 95.8 65.0 100.0 65.8 A central implication of our framework is that robust-training advances that enlarge the underlying classifier’s clean-margin distribution can improve the detector’s TPR/FPR frontier. We confirm this empirically on two complementary robust-training primitives: ℓ2 _2 PGD adversarial training and Gaussian-augmented training. Adversarial training. We adversarially train a CIFAR-10 VGG16 classifier with ℓ2 _2 PGD at radius 0.50.5 and apply AdvD_Adv and lcD_lc on top of the trained model. Compared to the standard-trained baseline (Table I), FPR drops sharply at the same TPR — e.g., lcD_lc’s FPR at ϵ=0.5ε=0.5 falls from 93.6%93.6\% to 32.2%32.2\% while lcD_lc’s TPR remains ≥99%≥ 99\% across the reported ϵε on ℓ2 _2 PGD (Table VIII). Adversarial training therefore acts as a margin-enlarging primitive that translates directly into a better TPR/FPR Pareto frontier under our certificate. Gaussian augmentation. A second standard primitive is training with Gaussian-augmented data (σ=0.25σ=0.25). Table VIII compares our detectors against RS (Cohen) and the conservative-RS variant on CIFAR-10 (ℓ2 _2 PGD): noise augmentation lifts RS’s TPR but its FPR stays substantially higher than ours at every reported ϵε. Full robust-training and Gaussian-augmentation results are in Table VIII. Taken together, both settings make a single point: robust training is a compounding lever on our detection. Stronger base-model margins improve the TPR/FPR frontier without changing the detector, so robustness gains translate directly into detection gains. Efficiency. Table V reports per-sample detection time (mean ± std over 500500 inputs). AdvD_Adv is the fastest base detector (single PGD pass), lcD_lc adds centroid optimisation on top, and both are markedly faster than RS (Cohen) at every scale. The stronger L′L estimator increases latency by roughly 1.81.8–2.6×2.6×, but remains below RS on all three datasets; on ImageNet-1k, strong AdvD_Adv and strong lcD_lc are still about 8.3×8.3× and 4.9×4.9× faster than RS, respectively. VI Discussion VI-A Three Levels of Certification A natural concern with our framework is the gap between the formal certificate (Lemma IV.1, Theorem IV.2) and the approximated detectors AdvD_Adv, lcD_lc that use the local estimator L′L . We make this gap explicit by distinguishing three levels of certification, each with its own empirical signature in our results. Level 1 — Fully certified. On a network whose global Lipschitz constant LglobL_glob is exactly known (e.g., 1-Lipschitz SortNet [zhang_rethinking_2022]), Lemma IV.1 with L=LglobL=L_glob delivers a formal certificate at the declared radius: every successful in-budget adversarial example is provably refused. Since q()q( x) is unobserved at inference, we lower-bound it by q()≥0q( x)≥ 0 (from clean correct classification), giving the conservative test q(^)<cLglob‖δ‖q( x)<c\,L_glob\,\|δ\|, which remains a sound certificate. Our SortNet evaluation (Table I) realises this level, attaining 100%100\% TPR at FPR substantially below the baseline detectors built on SortNet’s and CRM’s own certified radii. Level 2 — Conditionally certified (L′≥L∗L ≥ L^*). On standard pretrained classifiers LglobL_glob is intractable, so we replace it with the local estimator L′L . The certificate continues to hold for any specific successful in-budget adversarial example whenever the per-detector L′L condition holds on the relevant pair (Proposition IV.7). We quantify this subset by cert%, defined over all successful in-budget adversarial examples rather than only over rejected ones; on PyTorch pretrained ImageNet models, cert% reaches 6363–80%80\% for lcD_lc. This number is comparable in magnitude to RS certified accuracy on the same backbone (cf. Cohen et al. [cohen2019certified]), but the two metrics measure different events and are not directly comparable. Level 3 — Empirical protection. The difference between TPR and cert% is the empirically rejected but not formally certified subset. These examples are still protected by the deployed reject decision in our experiments (TPR ≥99%≥ 99\% on ImageNet), but we do not call them certified detections unless the per-detector L′L condition is verified. Our empirical TPR matches or exceeds dedicated empirical detectors (A2D [zhao2024attack], ContraNet [yang2022you]) on the same evaluation, so the empirical layer is competitive with SOTA empirical detection while remaining separate from the formal guarantee. VI-B FPR Growth with the Declared Radius FPR grows with ϵε because larger declared radii require wider rejection bands, mirroring the certified-robustness frontier. Thus the defender selects the largest protection radius whose clean-FPR budget is acceptable, while cert% reports which successful in-budget attacks are also formally certified. On SortNet at ϵ=0.5ε=0.5, our fully certified detector keeps FPR at 3535–41%41\%, versus 86%86\%/96%96\% for SortNet/CRM certified-radius detectors; adversarial training cuts CIFAR-10 lcD_lc FPR from 93.6%93.6\% to 32.2%32.2\%. VI-C Which detector certifies more, and when The two approximated detectors do not dominate one another on cert%; which one is tighter depends on the underlying classifier’s clean-margin scale. On Lipschitz-constrained 1-Lipschitz SortNet (Table I), AdvD_Adv certifies more: 5858–72%72\% versus 3737–58%58\% for lcD_lc. On unconstrained pretrained ImageNet classifiers (Table IV), the order reverses: lcD_lc certifies 6363–80%80\% versus 2020–60%60\% for AdvD_Adv. Standard CIFAR-10 VGG16 falls in between, with the two within 11–44 percentage points of each other (Table I). cert% tracks local Lipschitz stability rather than dataset complexity alone. If data complexity were the dominant driver, one would expect a sharp drop from CIFAR-10 to ImageNet-1k; instead the lcD_lc certified fraction is comparable across the two settings, while larger variation appears across architectures on the same dataset and across constrained versus unconstrained backbones. Table XIV adds ResNet-18 and VGG-style CNN results that reproduce the same profile on an architecture variation for each small-scale dataset. The structural reason is that L(,^)∗L^*_( x, x) for AdvD_Adv scales with q()+q(^)q( x)+q( x), while L(^~,)∗L^*_( x, x) for lcD_lc scales with q(^~)+q()q( x)+q( x). On a 1-Lipschitz network, q(^~)q( x) is bounded by the Lipschitz constant times the centroid travel and cannot escape the model’s clean-margin scale; the simpler AdvD_Adv certificate (whose two terms live on the same short-distance pair) is in fact tighter. On deep unconstrained classifiers, q()q( x) on a confident clean input is very large, q(^~)q( x) scales with it (the centroid moves through the network’s high-margin region), and the centroid construction allows L′L to track L∗L^* rather than being dominated by the clean-margin term. In effect, the centroid’s value as a high-margin anchor compounds with the model’s own margin headroom; on Lipschitz-constrained networks there is no headroom to compound. We deploy the two detectors as a complementary pair: AdvD_Adv when a tight global Lipschitz constant is available, lcD_lc on standard pretrained classifiers. VI-D Beyond ℓ2 _2: ℓ∞ _∞ Extension Lemma IV.1 extends to any ℓp _p norm with c=2(p−1)/pc=2^(p-1)/p. We empirically tested an ℓ∞ _∞ instantiation (c=2c=2, ℓ∞ _∞ PGD as the surrogate, ∥⋅∥∞\|·\|_∞ for distances) on standard CIFAR-10 VGG16: lcD_lc reaches TPR 99.5%99.5\% at ϵ=1.5/255ε=1.5/255 (FPR 80%80\%) and 100%100\% at ϵ=2/255ε=2/255 (FPR 90.5%90.5\%). TPR confirms that our reduction transfers, but FPR is much higher than in the ℓ2 _2 regime. The reason is purely norm-geometric: since ‖x‖∞≤‖x‖2≤n‖x‖∞\|x\|_∞≤\|x\|_2≤ n\,\|x\|_∞, the ℓ∞ _∞ Lipschitz constant of a network is substantially larger than its ℓ2 _2 counterpart, making L′L approximation looser and the detection threshold more permissive. Tightening the ℓ∞ _∞ certificate — for instance via norm-specific Lipschitz estimators or per-dimension bounds — is a natural direction we leave for future work. VI-E Practical Considerations and Limitations We close by discussing three considerations that arise when deploying our framework, each with its own empirical or design-side mitigation. Coupling to the classifier’s clean margin. The detector’s FPR is governed by the classifier’s clean-margin distribution. This follows from the Lipschitz-margin reduction: the margin distribution determines how tight the rejection band can be. Margin theory links larger normalized margins to robustness [bartlett_spectrally-normalized_2017, sokolic_robust_2017]; empirically, ViT-B/16 improves the ImageNet FPR profile over ResNet-50, and adversarial training cuts FPR sharply without changing the detector. Single-pair L′L estimation. Because L′L is computed from one perturbed pair (z,z′)(z,z ), Theorem IV.5 bounds the induced threshold gap. Under the revised denominator, pretrained-model cert% remains 6363–80%80\% for lcD_lc. Tables XVI and X (Appendix -D) show that L′/L∗L /L^* concentrates near or above 11 with mild violations; Table VI shows the multi-probe cost/cert% trade-off. Hybrid pairwise or layer-wise estimators are compatible with our framework. Norm scope. Our primary focus is ℓ2 _2, which already covers many security-relevant adversarial threats — physical-world stickers on traffic signs, frequency-domain perturbations, low-energy patches — via principled ℓ2 _2 formulations. The ℓ∞ _∞ extension is sketched in Section VI-D. Attention-based architectures. We do not rely on a global Lipschitz bound, which can be loose or unbounded for softmax attention outside a bounded input region [kim2021lipschitz]. Our certificate needs only the local pairwise constant L∗L^* on the bounded ball B(,ϵ)B( x,ε), where both L∗L^* and L′L are finite; the guarantee on attention models is therefore conditional on L′≥L∗L ≥ L^* in the same way as other unconstrained pretrained classifiers. The ViT-B/16 results in Table IV(b) support this scope, with cert% at least 63%63\% alongside near-perfect empirical TPR. Beyond image classification. The reduction requires a scalar score margin and a norm-bounded perturbation model, not an image-specific architecture. Extending the same certificate to detection, segmentation, or multimodal pipelines is therefore conceptually feasible whenever an appropriate task margin can be defined, but certified robustness for those tasks is less mature; we leave such extensions to future work. VII Conclusion We propose a detection-oriented perspective on defending DNNs against adversarial examples: rather than certifying that predictions remain unchanged, we certify that adversarial inputs are detected when the stated Lipschitz conditions hold. We prove via Lipschitz-margin analysis that certified ℓ2 _2 robustness implies certified adversarial detection (Lemma IV.1, Theorem IV.2), and instantiate two practical detector families, AdvD_Adv and lcD_lc, that operate on any pretrained classifier without retraining or architectural change. Across MNIST, CIFAR-10, and ImageNet-1k on four backbones, the framework matches or outperforms five baselines (CTT, SortNet, CRM, ContraNet, A2D), empirically rejects nearly all measured attacks, and formally certifies 6363–80%80\% of successful in-budget ImageNet adversarial examples under the revised cert% metric. Furthermore, robust training can improve the operating point of the same detector families by enlarging margins. References -A Ethical Considerations This work develops an adversarial example detection method that can be deployed in situations like Autonomous-driving perception, content moderation, and access control. While our detectors are shown to have almost 100% recall, similar to certified robustness literature, we acknowledge that there exists fasle negatives when the adversary have large perturbation budget in reality. Our framework is designed to detect adversarial examples with limit ℓ2 _2 perutrbations, clean samples are also possible to be detected. However, the service provider in our situation already have a meaningful build-in fallback for refused inputs . -B Notation Reference Table IX summarizes the symbols used throughout the paper. Definitions in the main text are authoritative; this table is a quick lookup. TABLE IX: Notation summary. Symbol Meaning Inputs and perturbations x Clean input. y True class of x. δ Adversarial perturbation. ϵε Perturbation budget. x Adversarial example, +δ x+δ. z Inference-time test input. z′z Defender’s perturbation of z. Network and margin f DNN classifier. fi()f_i( x) i-th class score. q(u,k)q(u;k) Class-k margin: fk(u)−maxj≠kfj(u)f_k(u)- _j≠ kf_j(u). q(u)q(u) Shorthand for q(u,argmaxkfk(u))q(u; _kf_k(u)) (own-label, ≥0≥ 0). y y Input pseudo-label argmaxf(z) f(z), fixed reference. ~ x Local centroid of x. ^~ x Local centroid of x. Lipschitz quantities ∥⋅∥p\|·\|_p ℓp _p norm; default p=2p=2. c Norm constant 2(p−1)/p2^(p-1)/p. L Lipschitz constant of f. LglobL_glob Global Lipschitz constant. L′L Local Lipschitz estimator. L∗L^* Optimal pairwise Lipschitz. L(,^)∗L^*_( x, x) Pairwise on (,^)( x, x). L(^~,)∗L^*_( x, x) Pairwise on (centroid, clean). Detectors and metrics D Detector, 0,1\0,1\ output. AdvD_Adv Via Claim 1. lcD_lc Via Claim 2. TPR Adversarial-detection rate. FPR Clean-rejection rate. cert% Adversarials both rejected and formally certified. -C Attacks Settings We use BIM with 10 steps, PGD with 40 steps and 10 random restarts, and CW-ℓ2 _2 with 40 steps. All attacks are the ℓ2 _2 version, or projected to the ℓ2 _2 ball of radius ‖δ‖\|δ\|. -D Detailed Results across Datasets This subsection reports the per-ϵε, per-attack and per-noise-level breakdowns that did not fit in the body. It also includes the ΔT _T bias-validation table (Table X). The trends parallel the main-text summary: lcD_lc achieves near-perfect TPR across all settings, AdvD_Adv trades a small TPR drop for substantially lower FPR, and the Cohen detector incurs FPR that escalates rapidly with ϵε. Tables XII–XIII present per-attack TPR and clean FPR on MNIST and CIFAR-10 under noise levels σ∈0.125,0.25σ∈\0.125,0.25\. Table XVII extends the body’s ImageNet-1k results (Table IV) to the full ϵ∈[0.1,1.0]ε∈[0.1,1.0] range at step 0.10.1. Table X reports the SortNet bias-bound check used to validate the deterministic ΔT _T envelope. TABLE X: Empirical tightness of ΔT _T on SortNet. Median actual ΔT _T and its share of the per-sample theoretical envelope from (9), computed on detected adversarials with L′≤LglobL ≤ L_glob. The remaining samples satisfy L′≥Lglob≥L∗L ≥ L_glob≥ L^* and are trivially certified. ϵε AdvD_Adv lcD_lc 0.3 0.31 (74%) 0.20 (16%) 0.5 0.51 (72%) 0.29 (19%) 1.0 1.02 (63%) 0.85 (44%) TABLE XI: Comparison of our approximated detectors with CTT [shumailov2020towards] on MNIST and CIFAR-10. We report true positive rate (TPR, %) and false positive rate (FPR, %) under different attacks and perturbation levels. CTT-loose and CTT-strict correspond to two thresholding variants in [shumailov2020towards]. Dataset Attack ϵε AdvD_Adv (Ours) lcD_lc (Ours) CTT-loose CTT-strict TPR FPR TPR FPR TPR FPR TPR FPR MNIST FGSM 0.1 100.0 0.5 100.0 1.0 100.0 1.6 100.0 1.1 FGSM 0.2 100.0 1.5 100.0 3.0 100.0 1.6 100.0 1.1 PGD 0.1 100.0 0.5 100.0 1.0 100.0 1.6 100.0 1.1 PGD 0.2 100.0 1.5 100.0 3.0 100.0 1.6 100.0 1.1 CIFAR-10 FGSM 0.02 95.0 2.5 100.0 6.0 95.7 6.4 96.5 3.0 FGSM 0.04 93.0 5.0 100.0 13.0 93.6 6.4 93.1 3.0 PGD 0.01 89.0 1.0 100.0 3.0 24.3 6.4 16.6 3.0 PGD 0.02 96.0 2.5 100.0 6.0 70.3 6.4 49.9 3.0 TABLE XII: TPR (%) of different attacks under varying ℓ2 _2 budgets ϵε. For the Cohen detector [cohen2019certified], we report certified TPR against BIM under two noise levels. Dataset ϵε AdvD_Adv lcD_lc Cohen FGSM PGD BIM CW FGSM PGD BIM CW σ=0.125σ=0.125 σ=0.25σ=0.25 MNIST 0.05 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 60.0 33.0 0.10 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 66.7 44.5 0.30 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 63.9 0.50 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 1.00 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 1.50 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 2.00 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 2.50 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 3.00 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 CIFAR-10 0.05 99.8 100.0 100.0 98.8 99.8 100.0 100.0 99.8 67.0 38.5 0.10 100.0 100.0 100.0 99.6 100.0 100.0 100.0 99.8 74.5 53.0 0.20 100.0 100.0 100.0 99.8 100.0 100.0 100.0 99.8 89.4 70.5 0.30 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 95.8 0.40 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 0.50 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 0.75 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 1.00 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 TABLE XIII: Clean FPR (%) of our detectors vs. RS (Cohen) across perturbation budgets. Lower is better. Dataset ϵε Ours Cohen AdvD_Adv lcD_lc σ=0.125σ=0.125 σ=0.25σ=0.25 MNIST 0.05 0.0 0.0 0.5 2.5 0.10 0.5 1.0 1.5 4.0 0.30 5.0 5.5 100.0 8.5 0.50 8.0 8.5 100.0 22.0 1.00 17.0 17.5 100.0 98.0 1.50 25.5 28.0 100.0 98.5 2.00 47.0 47.5 100.0 98.0 2.50 68.0 68.5 100.0 98.5 3.00 81.0 80.5 100.0 98.5 CIFAR-10 0.05 15.3 15.6 35.0 46.0 0.10 29.4 29.9 40.5 60.2 0.20 55.4 56.1 68.1 68.8 0.30 74.7 75.7 100.0 96.0 0.40 86.0 87.1 100.0 99.8 0.50 92.7 93.5 100.0 99.8 0.75 98.3 98.7 100.0 100.0 1.00 99.6 99.7 100.0 100.0 TABLE XIV: Architecture variation on CIFAR-10 and MNIST. BIM attacks with nadv=500n_adv=500 and nclean=1000n_clean=1000. We evaluate CIFAR-10 on ResNet-18 and MNIST on a VGG-style CNN to check that the detection profile is not tied to the primary classifiers. Dataset Backbone ϵε TPR FPR cert% AdvD_Adv lcD_lc AdvD_Adv lcD_lc CIFAR-10 ResNet-18 0.05 100.0 12.2 12.2 70.0 71.3 0.10 100.0 29.7 29.7 86.0 85.3 0.30 100.0 74.9 75.1 78.7 77.0 0.50 100.0 90.5 91.0 71.7 67.7 MNIST VGG-style CNN 0.50 100.0 2.4 3.6 95.0 100.0 1.00 100.0 7.5 16.3 84.7 96.3 1.50 100.0 26.1 54.2 73.0 90.7 (a) AdvD_Adv on MNIST (b) AdvD_Adv on CIFAR-10 (c) AdvD_Adv on ImageNet-1k (d) lcD_lc on MNIST (e) lcD_lc on CIFAR-10 (f) lcD_lc on ImageNet-1k Fig. 2: Summary curves: TPR on adversarial inputs and FPR on clean inputs across ℓ2 _2 perturbation magnitudes ϵε, for AdvD_Adv (top row) and lcD_lc (bottom row). Columns sweep MNIST (LeNet-5), CIFAR-10 (VGG16), and ImageNet-1k (ResNet-50). Fig. 3: Distribution of (RHS−dz)(RHS-d_z) values under different attacks. Negative values (RHS<dzRHS<d_z) indicate samples flagged as adversarial. TABLE XV: Cost–tightness sweep for the stronger estimator. CIFAR-10 VGG16, AdvD_Adv, ϵ=0.1ε=0.1. Estimator cert% ms/sample Baseline 76.4 22 K=1,T=3K=1,T=3 91.6 108 K=1,T=6K=1,T=6 93.5 201 K=1,T=9K=1,T=9 93.7 293 K=1,T=12K=1,T=12 93.7 383 K=2,T=12K=2,T=12 95.4 563 TABLE XVI: Empirical distribution of L′/L∗L /L^*. CIFAR-10 VGG16, BIM, n=500n=500. Violations are samples with L′/L∗<1L /L^*<1; the last column reports their ratio distribution. lcD_lc has a right-skewed tail at ϵ=0.10,0.50ε=0.10,0.50 from a few samples with tiny L∗L^*; its median remains near 11. AdvD_Adv ϵε cert% L′/L∗L /L^* mean± Median Viol. % Viol. mean± 0.05 62.6 1.037±0.201.037± 0.20 1.007 37.4 0.949±0.0820.949± 0.082 0.10 76.6 1.067±0.241.067± 0.24 1.034 23.4 0.908±0.1070.908± 0.107 0.30 83.0 1.153±0.291.153± 0.29 1.118 17.0 0.855±0.1330.855± 0.133 0.50 82.4 1.194±0.301.194± 0.30 1.162 17.6 0.861±0.1300.861± 0.130 lcD_lc ϵε cert% L′/L∗L /L^* mean± Median Viol. % Viol. mean± 0.05 62.0 0.985±0.130.985± 0.13 1.001 38.0 0.947±0.2000.947± 0.200 0.10 75.2 1.123±2.631.123± 2.63 1.006 24.8 0.952±0.1320.952± 0.132 0.30 80.4 1.064±0.141.064± 0.14 1.039 19.6 0.939±0.0650.939± 0.065 0.50 78.8 1.167±1.401.167± 1.40 1.060 21.2 0.924±0.0810.924± 0.081 TABLE XVII: Full ImageNet-1k results (PyTorch pretrained ResNet-50) at step ϵ=0.1ε=0.1. TPR on ℓ2 _2 BIM attacks; FPR on clean samples. ϵε AdvD_Adv (%) lcD_lc (%) RS (Cohen) (%) TPR ↑ FPR ↓ TPR ↑ FPR ↓ TPR ↑ FPR ↓ 0.1 99.5 9.0 99.7 9.4 34.0 17.0 0.2 99.6 18.0 99.6 17.2 53.0 30.0 0.3 99.8 24.6 99.6 23.7 62.5 36.0 0.4 99.9 30.3 99.2 29.0 82.0 68.0 0.5 99.6 34.4 99.3 32.8 85.5 51.0 0.6 99.4 37.8 98.8 37.2 100.0 100.0 0.7 99.6 43.5 99.5 41.6 100.0 100.0 0.8 99.3 46.7 99.2 45.3 100.0 100.0 0.9 99.7 51.9 99.8 49.4 100.0 100.0 1.0 99.8 54.8 99.8 53.5 100.0 100.0 Table XIV adds the architecture variations on small-scale datasets; Table XI reports the complementary CTT comparison omitted from the body for space. Figures 2 and 3 provide the full perturbation-scale curves and per-sample detection-statistic distributions summarized in Section V. Table XVI and Table XV give the supporting diagnostics for the revised certified-coverage analysis: the realised L′/L∗L /L^* distribution and the cost–tightness sweep for stronger L′L estimation. On MNIST, both AdvD_Adv and lcD_lc attain 100%100\% TPR across the full range; FPR stays below 3%3\% for ϵ≤0.2ε≤ 0.2 and grows gradually thereafter (about 17%17\% at ϵ=1.0ε=1.0, 80%80\% at ϵ=3.0ε=3.0). On CIFAR-10, the difference is more pronounced. AdvD_Adv achieves 6969–96%96\% TPR with much lower FPR (7.57.5–70%70\%); lcD_lc reaches near-perfect TPR (≈100%≈ 100\%) at the cost of higher FPR (1616–100%100\%) for large ϵε. On ImageNet-1k, both our detectors stay ≥98.8%≥ 98.8\% TPR throughout, while keeping FPR under 55%55\% even at ϵ=1.0ε=1.0. Cohen exhibits FPR exceeding 50%50\% once ϵ≥0.4ε≥ 0.4 and saturates at 100%100\% for ϵ≥0.6ε≥ 0.6. -E Proof of Lemma IV.1 and Theorem IV.2 Lemma .1. (Proposition 3.1 in [zhang_rethinking_2022])For a neural network f with LipschitzLipschitz constant L under ℓp _p -norm ||⋅||p||·||_p, f is provably robust against perturbations ‖δ‖p<1cLmargin(f())||δ||_p< 1cLmargin(f( x)), i.e. argmaxf()=argmaxf(+δ),∀‖δ‖p<1cLmargin(f()),argmaxf( x)=argmaxf( x+δ),\ ∀||δ||_p< 1cLmargin(f( x)), (10) where c=2p−1pc=2 p-1p is the constant depending only on the norm ||⋅||p||·||_p, which is 22 for ℓ∞ _∞ (and 2 2 for ℓ2 _2). The proof for Lemma IV.1 is as follows. Proof. Let y,jy,j be the class of x and x predicted by f, Then we have ‖f(^)−f()‖p ||f( x)-f( x)||_p =(|(fy(^)−fy()|p+∑i≠y|fi(^)−fi()|p)1p =(|(f_y( x)-f_y( x)|^p+ _i≠ y|f_i( x)-f_i( x)|^p) 1p (11) ≥(|(fy(^)−fy()|p+|fj(^)−fj()|p)1p. ≥(|(f_y( x)-f_y( x)|^p+|f_j( x)-f_j( x)|^p) 1p. Let dzy=fy(^)−fy(),dzj=fj(^)−fj()dz_y=f_y( x)-f_y( x),dz_j=f_j( x)-f_j( x). Considering a polynomial g(r)=rp+(dzj−dzy−r)pg(r)=r^p+(dz_j-dz_y-r)^p, then g(−dzy) g(-dz_y) =(−dzy)p+dzjp =(-dz_y)^p+dz_j^p =(−fy(^)+fy())p+(fj(^)−fj())p =(-f_y( x)+f_y( x))^p+(f_j( x)-f_j( x))^p ≤‖f(^)−f()‖p, ≤||f( x)-f( x)||_p^p, where the last line inequality is caused by (11). By analyzing the derivatives of g(z)g(z), we can find that g(z)g(z) has a global minimum at r=dzj−dzy2r= dz_j-dz_y2, using the fact that fj(^)>fy(^)f_j( x)>f_y( x) and fj()≤fy()f_j( x)≤ f_y( x).Then, (dzj−dzy)p2p−1=g(dzj−dzy2)≤g(−dzy)≤||f(^)−f()||p, (dz_j-dz_y)^p2^p-1=g( dz_j-dz_y2)≤ g(-dz_y)≤||f( x)-f( x)||_p^p, (12) which implies fj(^)−fy(^)+fy()−fj() f_j( x)-f_y( x)+f_y( x)-f_j( x) ≤221p‖f(^)−f()‖ ≤ 22 1p||f( x)-f( x)|| (13) ≤cL‖^−‖, ≤ cL|| x- x||, where the last inequality follows from the L-Lipschitz continuity of f. Moreover, since fj(^)−fy(^)+fy()−fj()≥q(^)+q()f_j( x)-f_y( x)+f_y( x)-f_j( x)≥ q( x)+q( x), we have q(^)≤cL‖^−‖−q().q( x)≤ cL|| x- x||-q( x). ∎ The proof for Theorem IV.2 follows from a single application of Lemma IV.1 on the pair (,^~)( x, x) together with the triangle inequality, requiring only L≥L(^~,)∗L≥ L^*_( x, x). Proof. By construction the local centroid ^~ x retains the predicted class of x, i.e., y(^~)=y(^)y( x)=y( x). Combined with the assumption that x is a successful adversarial example (y(^)≠y()y( x)≠ y( x)), the pair (,^~)( x, x) has distinct predicted classes. Lemma IV.1 applied to this pair therefore yields q(^~)+q()≤cL‖^~−‖.q( x)+q( x)\;≤\;cL\,\| x- x\|. (14) By the triangle inequality and ‖^−‖=‖δ‖\| x- x\|=\|δ\|, ‖^~−‖≤‖^~−^‖+‖^−‖=‖^~−^‖+‖δ‖.\| x- x\|\;≤\;\| x- x\|+\| x- x\|\;=\;\| x- x\|+\|δ\|. (15) Combining (14) and (15) and dividing both sides by cL>0cL>0, ‖^~−^‖≥q(^~)+q()cL−‖δ‖,\| x- x\|\;≥\; q( x)+q( x)cL-\|δ\|, which is the bound of Theorem IV.2. The inequality L≥L(^~,)∗L≥ L^*_( x, x) is exactly the saturation condition for (14) to hold, and is the only Lipschitz requirement invoked. ∎ -F Proof of Proposition IV.7 Proof. For an adversarial input z=^z= x, the pseudo-label is y^=y(^)≠y() y=y( x)≠ y( x), and q()>0q( x)>0 at x’s own label. (i) AdvD_Adv. Lemma IV.1 on the (,^)( x, x) pair at L=L(,^)∗L=L^*_( x, x) gives q(^)+q()≤cL(,^)∗‖δ‖q( x)+q( x)≤ c\,L^*_( x, x)\|δ\|. Combining with L(,^)∗≤L′L^*_( x, x)≤ L and the local-Lipschitz formula cL′⋅max(‖^−z′‖,‖δ‖)=q(^)−q(z′,y^)c\,L \!·\! (\| x-z \|,\|δ\|)=q( x)-q(z ; y), q(^)+q()≤cL′‖δ‖≤cL′⋅max(‖^−z′‖,‖δ‖) q( x)+q( x)\;≤\;c\,L \,\|δ\|\;≤\;c\,L \!·\! (\| x-z \|,\|δ\|) =q(^)−q(z′,y^), =\;q( x)-q(z ; y), so q(z′,y^)≤−q()≤0q(z ; y)≤-q( x)≤ 0 — the flip property is a consequence of L′≥L(,^)∗L ≥ L^*_( x, x), not a hypothesis. Substituting back, q(^)+q(z′,y^)≤q(^)−q()≤q(^)+q()≤cL′‖δ‖,q( x)+q(z ; y)\;≤\;q( x)-q( x)\;≤\;q( x)+q( x)\;≤\;c\,L \,\|δ\|, which is the Claim 1 bound. (i) lcD_lc. By Proposition IV.6, L=L(^~,)∗L=L^*_( x, x) certifies Theorem IV.2: ‖^−^~‖≥q(^~)+q()cL(^~,)∗−‖δ‖\| x- x\|≥ q( x)+q( x)c\,L^*_( x, x)-\|δ\|. The detector’s right-hand side is q(^~)+q(z′,y^)cL′−‖δ‖ q( x)+q(z ; y)c\,L -\|δ\|. Combining the flip property q(z′,y^)≤0≤q()q(z ; y)≤ 0≤ q( x) with L(^~,)∗≤L′L^*_( x, x)≤ L , q(^~)+q(z′,y^)cL′≤q(^~)cL′≤q(^~)cL(^~,)∗≤q(^~)+q()cL(^~,)∗, q( x)+q(z ; y)c\,L \;≤\; q( x)c\,L \;≤\; q( x)c\,L^*_( x, x)\;≤\; q( x)+q( x)c\,L^*_( x, x), so the detector’s right-hand side is at most the certified one, and the detector flags x whenever Theorem IV.2 does. ∎ -G Margin Monotonicity Under Gradient Ascent We give a formal justification for the class-preservation property used by Theorem IV.2: under gradient ascent on the margin function at a fixed reference label, the margin is monotonically non-decreasing along the flow, hence the predicted class is preserved. Definition .2 (Chain rule). A locally Lipschitz function h:ℝd→ℝh:R^d admits a chain rule if for any absolutely continuous u:ℝ+→ℝdu:R_+ ^d, (h∘u)′(t)=⟨∂∘h(u(t)),u′(t)⟩for a.e. t≥0.(h u) (t)= ∂ h(u(t)),\,u (t) a.e. t≥ 0. Lemma .3 (Davis et al [davis2020stochastic], Lemma 5.2). Let h:ℝd→ℝh:R^d be locally Lipschitz and admit a chain rule, and let u:ℝ+→ℝdu:R_+ ^d be absolutely continuous with du/dt∈∂∘h(u(t))du/dt∈∂ h(u(t)). Then ‖du/dt‖2=dh(u(t))/dt\|du/dt\|^2=dh(u(t))/dt for a.e. t≥0t≥ 0. Lemma .4 (Margin monotonicity). Let f be a locally Lipschitz network and q(⋅,y^)q(·; y) the margin function at fixed reference label y^=argmaxf(z) y= f(z) for input z, and assume q(⋅,y^)q(·; y) admits a chain rule (Definition .2); this holds whenever f is locally Lipschitz and tame, including piecewise-linear ReLU/max-pool networks [davis2020stochastic]. Under the gradient ascent flow du/dt∈∂∘q(u(t),y^)du/dt∈∂ q(u(t); y) initialized at u(0)=zu(0)=z, dq(u(t),y^)dt=‖dudt‖2≥ 0for a.e. t≥0, d\,q(u(t); y)dt= \| dudt \|^2\;≥\;0 a.e. t≥ 0, with equality iff du/dt=0du/dt=0. In particular, q(u(t),y^)q(u(t); y) is non-decreasing along the flow; if q(z,y^)>0q(z; y)>0, then q(u(t),y^)>0q(u(t); y)>0 for all t≥0t≥ 0, so argmaxf(u(t))=y f(u(t))= y throughout. Proof. The equality is Lemma .3 applied to h=q(⋅,y^)h=q(·; y). Non-negativity gives monotonicity. The class-preservation conclusion is q(u,y^)>0⇔y^=argmaxf(u)q(u; y)>0 y= f(u), combined with the trajectory’s non-decreasing margin keeping the strict positivity from initialization onward. ∎ -H Proof of Lemma IV.4 Proof. Let a=^=za= x=z and b=b= x denote the adversarial and its (unknown) clean counterparts, respectively, and let z′=z+σz =z+σ be the perturbed sample used in our approximation. Define the pairwise distances α=‖a−b‖,β=‖a−z′‖,γ=‖b−z′‖.α=\|a-b\|, β=\|a-z \|, γ=\|b-z \|. We write the ideal constant from Lemma IV.1 as L⋆≜q(a)+q(b)cα,L \; \; q(a)+q(b)c\,α, and the computable local quotient as L′≜|q(a)−q(z′)|cβ.L \; \; |q(a)-q(z )|c\,β. Let LglobL_glob be any global Lipschitz constant of q(⋅)q(·), i.e., |q(u)−q(v)|≤cLglob‖u−v‖∀u,v.|q(u)-q(v)|≤ c\,L_glob\,\|u-v\| ∀ u,v. Using the triangle inequality, we decompose: |q(a)−q(z′)|≤|q(a)−q(b)|+|q(b)−q(z′)|.|q(a)-q(z )|≤|q(a)-q(b)|+|q(b)-q(z )|. Since |q(a)−q(b)|≤q(a)+q(b)=cαL⋆|q(a)-q(b)|≤ q(a)+q(b)=c\,α L and |q(b)−q(z′)|≤cLglobγ|q(b)-q(z )|≤ c\,L_globγ, we have L′≤cαL⋆+cLglobγcβ=αβL⋆+γβLglob.L ≤ c\,α L +c\,L_globγc\,β= αβ\,L + γβ\,L_glob. Similarly, by reversing the inequality, |q(a)−q(z′)|≥|q(a)−q(b)|−|q(b)−q(z′)|≥cαD−cLglobγ,|q(a)-q(z )|≥|q(a)-q(b)|-|q(b)-q(z )|≥ c\,α D-c\,L_globγ, where D≜|q(a)−q(b)|cα≤L⋆D |q(a)-q(b)|c\,α≤ L . Hence, L′≥αβD−γβLglob.L ≥ αβ\,D- γβ\,L_glob. Combining both sides yields the two–sided bound: αβD−γβLglob≤L′≤αβL⋆+γβLglob. αβ\,D- γβ\,L_glob\;\;≤\;\;L \;\;≤\;\; αβ\,L + γβ\,L_glob. Consequently, the deviation of L′L from the scaled ideal constant (α/β)L⋆(α/β)L is bounded by |L′−(α/β)L⋆|≤γβLglob+αβ(L⋆−D). |\,L -(α/β)\,L \, |≤ γβ\,L_glob+ αβ\,(L -D). This reveals two distinct sources of bias: • A geometric bias γβLglob γβL_glob, governed by the relative placement of z′z with respect to a and b; • A margin bias αβ(L⋆−D) αβ(L -D), reflecting the gap between the sum- and difference-based margin quotients. In particular, when z′z lies approximately along the segment (a,b)(a,b), we have β≈αβ≈α and γ≈|α−β|γ≈|α-β|, so both terms become small and L′L closely tracks L⋆L . Conversely, when z′z is very close to a (small β) or far from b (large γ), the approximation tends to overestimate the ideal constant. ∎ -I Proof of Theorem IV.5 The proof of Theorem IV.5 is as follows. Proof. We prove the theorem by bounding the difference term by term. We use the assumptions of Theorem IV.5: Lq≤cL¯L_q≤ c L (A1) and L′≤Lglob≤L¯L ≤ L_glob≤ L (A2); recall η:=1−L′/L¯∈[0,1)η:=1-L / L∈[0,1). Let D=|q(z~)+q()cLglob−q(z~)+q(z′,y^)cL′|.D= | q( z)+q( x)c\,L_glob- q( z)+q(z ; y)c\,L |. By adding and subtracting q(z~)+q(z′,y^)cLglob q( z)+q(z ; y)c\,L_glob, D≤1c(|q()−q(z′,y^)|Lglob+|q(z~)+q(z′,y^)|⋅|1Lglob−1L′|).D≤ 1c ( |q( x)-q(z ; y)|L_glob+|q( z)+q(z ; y)|· | 1L_glob- 1L | ). By Lipschitz continuity of q (A1) and the fact that ‖−z′‖≤‖−z‖+‖z−z′‖≤2‖δ‖\| x-z \|≤\| x-z\|+\|z-z \|≤ 2\|δ\| (using ‖z−‖≤‖δ‖\|z- x\|≤\|δ\| from the threat model and ‖z−z′‖≤‖δ‖\|z-z \|≤\|δ\| from Algorithm 1), we have |q()−q(z′,y^)|≤Lq‖−z′‖≤2Lq‖δ‖|q( x)-q(z ; y)|≤ L_q\| x-z \|≤ 2L_q\|δ\|. Combined with L′≤LglobL ≤ L_glob, |q()−q(z′,y^)|Lglob≤2Lq‖δ‖Lglob≤2Lq‖δ‖L′. |q( x)-q(z ; y)|L_glob\;≤\; 2L_q\|δ\|L_glob\;≤\; 2L_q\|δ\|L . For the second term, L′≤Lglob≤L¯L ≤ L_glob≤ L gives 1−L′/Lglob≥01-L /L_glob≥ 0 and 1−L′/Lglob≤1−L′/L¯=η1-L /L_glob≤ 1-L / L=η. Therefore |1Lglob−1L′|=1L′⋅Lglob−L′Lglob≤ηL′. | 1L_glob- 1L |\;=\; 1L · L_glob-L L_glob\;≤\; ηL . Putting the two bounds together, ΔT≤1c[2LqL′‖δ‖+ηL′(q(z~)+|q(z′,y^)|+Lq‖δ‖)], _T\;≤\; 1c [\; 2L_qL \|δ\|\;+\; ηL \, (q( z)+|q(z ; y)|+L_q\|δ\| )\; ], which is the bound (9) (with the geometric stretch factor doubled to absorb the →z→z′ x→ z→ z triangle). ∎