CBD: A Certified Backdoor Detector Based on Local Dominant Probability
Authors: Zhen Xiang
Zidi Xiong
Bo Li
Venue: NeurIPS 2023 poster (2023)
Keywords: backdoor
Trojan
certification
adversarial learning
deep neural network
conformal prediction
TL;DR: We proposed the first certified backdoor detection method with the condition under which the attacks are guaranteed to be detectable, as well as a probabilistic upper bound for the false positive rate.

Abstract: Backdoor attack is a common threat to deep neural networks. During testing, samples embedded with a backdoor trigger will be misclassified as an adversarial target by a backdoored model, while samples without the backdoor trigger will be correctly classified. In this paper, we present the first certified backdoor detector (CBD), which is based on a novel, adjustable conformal prediction scheme based on our proposed statistic local dominant probability. For any classifier under inspection, CBD provides 1) a detection inference, 2) the condition under which the attacks are guaranteed to be detectable for the same classification domain, and 3) a probabilistic upper bound for the false positive rate. Our theoretical results show that attacks with triggers that are more resilient to test-time noise and have smaller perturbation magnitudes are more likely to be detected with guarantees. Moreover, we conduct extensive experiments on four benchmark datasets considering various backdoor types, such as BadNet, CB, and Blend. CBD achieves comparable or even higher detection accuracy than state-of-the-art detectors, and it in addition provides detection certification. Notably, for backdoor attacks with random perturbation triggers bounded by $\ell_2\leq0.75$ which achieves more than 90\% attack success rate, CBD achieves 100\% (98\%), 100\% (84\%), 98\% (98\%), and 72\% (40\%) empirical (certified) detection true positive rates on the four benchmark datasets GTSRB, SVHN, CIFAR-10, and TinyImageNet, respectively, with low false positive rates.

CBD: A Certified Backdoor Detector Based on Local Dominant Probability
Zhen Xiang
Zidi Xiong Bo
University of Illinois Urbana- Chhapa-Champaign (zxiangaa, zidix2, 1bo)@illinois. edu
Abstract
Backdoor attack is a common threat to deep neural networks. During testing, samples embedded with backdoor trigger will be misclassified as adversarial target by a backdoored model, while samples without the backdoor trigger will be correctly classified. In this paper, we present the first certified backdoor detector (CBD), which is based on a novel, adjustable conformal prediction scheme based our proposed statistic local dominant probability. For any classifier under inspection, CBD provides 1) a detection inference. 2) the condition under which the attacks are guaranteed to be detectable for the same classification domain, and 3) a probabilistic upper bound for the false positive rate. Our theoretical results show that attacks with triggers that more resilient to test-time noise and have smaller perturbation magnitudes are more likely to be detected with guarantees. Moreover, we conduct extensive experiments on four benchmark datasets considering various backdoor types, such as BadNet, CB, and Blend. CBD achieves comparable or even higher detection accuracy than cate-of-theeart detectors, and it in addition provides detection certification. Notably, for backdoor attacks with random perturbation triggers bounded by & 0.75 which achieves more than 90% attack success rate, CBD achieves 100% (98%), 100% (84%), 98% (98%). and 72% (40%) empirical (certified) detection true positive rates on the four benchmark datasets GTSRB, SVHN, CIFAR- 10, and TinylmageNer respectively, with low false positive rates.
Introduction
Despite the success of deep neural networks (DNNs) in many applications, they are vulnerable to adversarial attacks such backdoor attacks [46, 36). A DNN being backdoored will learn predict an adversarial target class for test samples embedded with a backdoor trigger, while maintaining a high accuracy on clean test samples without the trigger [18, 8, 42, 65. 50. 43, 51,
Backdoor detection is a popular task for backdoor defense. It aims to detect a given model is backdoored without access the training set or any real test samples that are possibly embedded with the trigger [48, 64). The task corresponds to practical scenarios where the user of an app or a legacy system containing DNN seeks know if the model is backdoor attacked, where the training set is not available [1]. Various empirical approaches have been proposed for backdoor detection, most of which are based trigger reverse engineering [67, 6, 75, 69, 56, 62, 24], or meta classification [82, 29]. However, none of these works quantitatively investigate the conditions under which the backdoor attacks are guaranteed be detectable. Without detection guarantee, DNNs still vulnerable to future attacks (c.g.) with new trigger types [51, 87, 70].
In this paper, we make the first attempt toward the certification of backdoor detection. Certification is an important concept for studies on the robustness of DNNs against adversarial examples [61, 17, 52, 7, 45]. In particular, robustness certification refers guarantee for a model to produce desired outputs (e.g. correct label prediction) when the adversarial perturbation applied to the inputs satisfies certain conditions (e.g. with some constrained perturbation magnitude) [33, 58, 32, 10, 59]. As an analogy, we propose a certified backdoor detector (CBD)
probabilistic deterministic
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

that is guaranteed to trigger an alarm if the attack for given domain satisfies certain conditions. In Sec. 3. we introduce the detection procedure of CBD based on conformal prediction (with our proposed, optional adjustment scheme) using a novel (model-level) statistic named local dominant probubility. The calibration set for conformal prediction is obtained from a small number of benign shadow models trained on a small validation set, which addresses the unavailability of the training set. In Sec. 4, we derive the condition for attacks with detection guarantee, as well as a probabilistic upper bound for the false positive rate of our detector, for any prescribed significance level specifying the aggressiveness of the detection. Notably, our certification is comprehensive - for any domain, more effective attacks with strong trigger robustness (which measures the resilience of a trigger against test-time noises) and more stealthy attacks (against human inspectors) with small trigger perturbation magnitudes are easier to be detected with guarantees. Moreover, both our detector and the certification method do not assume the trigger incorporation mechanism or the training configuration of the model, which allows their potential application to future attacks. Our contributions
summarized below:
We propose CBD, the first certified backdoor detector, which based on an adjustable conformal prediction scheme using a novel local dominant probability statistic.
We propose a certification method and show that for any domain, backdoor attacks with stronger trigger robustness and smaller trigger perturbation magnitudes are more likely to be detected by CBD with guarantee. We also derive probabilistic upper bound for the false positive rate of CBD.
We show that CBD achieves comparable or even higher detection accuracy than state-of-the-ar detectors against three types of backdoors. We also show that for backdoor attacks with random perturbation triggers bounded by & < 0.75, CBD achieves 100% (98%). 100% (84%), 98% (98%), and 72% (40%) empirical (certified) true positive rates on GTSRB, SVHN CIFAR- 10, and IinylmageNet, respectively, with only 0%. 0%, 6%, and 10% false positive rates, respectively.
Related Work
Backdoor Detection Methods Existing methods for backdoor detection are all empirical without theoretical guarantees. An important type of seweese-ennnneerng--aaeee baasd method estimates putative triggers for anomaly detection [67, 6, 75, 41, 78, 73, 79, 76, 69, 56, 62, 24]. Certification for these methods hard due to the complexity of trigger reverse engineering. Another type of detector based on meta-classification that involves large number of shadow models trained with and without attacks [82, 29]. Differently, our CBD is based on conformal prediction involving a scalar detection statistic (rather than high dimensional feature vector employed by [82, 291), such that only a small number of benign shadow models will be required. More importantly, our CBD is certified, i.e. with detection guarantee, which is different from all the detention methods mentioned above.
Other Backdoor Defense Tasks Backdoor defenses during training aim to produce a backdoor- free classifier from the possibly poisoned training set [63, 5, 74, 14, 25, 57, 77, 23, 4, 16). These defenses require access to the training set, which unavailable for backdoor detection. Backdoor mitigation aims to "repair" models being backdoor attacked [40, 72, 35, 19, 88, 85), which can be viewed as downstream task following backdoor detection. Inference-stage trigger detection aims to detect if a test sample contains the trigger [15, 55, 12, 9, 44, 34]. However, backdoor detection is performed before the inference stage, where test samples are not available. These defense tasks will not be further diseussed due to their fundamental differences from the backdoor detection task.
Certified Backdoor Defenses Existing methods mostly modify the training process to prevent the backdoor from being learned, while manipulating the test sample to destroy any potentially embedded triggers [86, 71, 27, 53). These methods are not applicable to the backdoor detection problem where both the training set and the test samples are not available. More importantly, all these existing certified defenses are deployed during training, which requires an uncontaminated training process fully controlled by the defender. In contrast, in this paper, we consider stronger threat model that allows the attacker to have full control of the training process.
3 Detection Method
3.1 Problem Definition
Threat Model Consider classification domain with sample space X' and label space Y A backdoor attack is specified by trigger with some incorporation function d: X' - X' and a target class E ). For successful backdoor attack, the victim classifier will predict to the target class t whenever

---

test sample is embedded with the trigger, while test samples without the trigger will be correctly classified [18, 8, 42, 38]. In this paper, we do allow advanced attackers with full control of the training process [51, 87, 70, 50, 3]. This is deemed a stronger threat model than all previous works on certified backdoor defense where the defender is assumed with full control of the training process. However, in this paper, we do not consider backdoor attacks with multiple triggers or target classes [84, 83] - even empirical detection of these attacks is a challenging problem [80].
Goal of Certified Backdoor Detection The fundamental goal is backdoor detection, i.e. to infer if a given classifier f(: (<::)= : X' - y is backdoored or not [48, 64]. The defender has no access to the training set or any test samples that may contain the trigger. In practice, the defender also has no access to benign classifiers with high accuracy for the same domain as f(: w) otherwise, these benign classifiers can be used for the task, and detection will be unnecessary. However, the defender assumed with small validation set of clean samples for detection - this is standard assumption made by most post-training backdoor defenses [67, 82, 75, 56, 41].
Beyond model inference, a certified backdoor detector also needs to provide each classification domain (associated with the model to be inspected) with a condition on 6, f, and w, such that any successful backdoor attack with a trigger ô and target class on this classification domain) is guaranteed to be detected if the condition is satisfied. The stronger a certification is. the more likely a successful attack on the domain will be detectable with guarantee. Moreover, a certification has to be associated with a guarantee on the false positive rate; otherwise, an arbitrarily strong certification can be achieved by increasing the aggressiveness of the detection rule.
victim classifier f(; w) (trained
3.2 Overview of CBD Detection
Key Intuition For a successful backdoor attack with trigger ó and target class 1, test instance x embedded with the trigger (denoted by d(x)) will be classified to the target class t with high probability. Practical backdoor triggers should also be robust (i.e. resilient) noises either from the environment or introduced by simple defenses based on prputpprepoocessing such as blurring and/or quantization [81, 39]. Such trigger robustness can be measured by the distribution of the model prediction in the neighborhood of each 8(x)) - the more robust the trigger is, the more samples in the neighborhood of ((r) will be predicted to the target class Thus, if the perturbation magnitude of a robust trigger, i.e. []0(z)) x=|2 is small (which is usual for backdoor attacks to achieve stealthiness). a significant proportion of samples the neighborhood of x will also be classified to class & due to their closeness to d(z)). Such an increment in the target class probability in the neighborhood of all instances is captured by our proposed statistic named local dominant probability (L.P) to distinguish backdoored classifiers from benign ones - the former tend to have a larger LDP than the latter.
Outline of CBD Detection Procedure In short, CBD performs an adjustable conformal prediction to test if the LDP statistic computed for the model to be inspected is sufficiently large to trigger an alarm. A small number of shadow models (with the same architecture as the model be inspected) are trained on relatively small validation set, with an LDP computed for each shadow model to form a calibration set. Then, a small proportion of outliers with large values in the calibration set are optionally removed, e.g., by anomaly detection. Based on this adjusted calibration set, the p-value is computed for the LDP for the model to inspected. The model is deemed to be backdoored if the p-value is less than some prescribed significance level (e.g. the classical 0.05 for statistical testing).
3.3 Definition of LDP
We first define samplewise local probability vector (SLPV) to represent the distribution of the model prediction outcomes in the neighborhood of any given sample. Then, based on SLPV, we define the samplewise trigger robustness (STR) that measures the resilience of trigger to the Gaussian noise when it is embedded in a particular sample. Finally, we define the LDP statistic based on SIPV..
Definition 3.1. (Samplewise Local Probability Vector (SLPV)) For any classifier f(; w) : X y with parameters w, the SLPV for any input x E X' is a probability vector p(r) W., σ) E [0.1] 1] over the K = | classes, with the k-th entry defined by Pr(x (r/ a) - Pe--N(0.002)) (2 + e; w) = k), vk E Y, where N(p, Σ) represents Gaussian distribution with mean j and covariance L.
Remarks: If [(; w) is continuous at x with f(x; w) k for some k E ), it is trivial to show that Pa( σ) - as + O, i.c. the SLPV becomes a singleton at the predicted class of without the Gaussian noise. In practice, SLPV can be estimated by Monte Carlo for any given model and sample.
3

---

8(m1)
8 8(ra)
8(
(a) Benign classifier with a small LDP close to : (b) Classifier being backdoored with a large LDP.
Figure I: Illustration of the difference in LDP between benign and backdoored classifiers on classification domain with = classes. A backdoor attack with a robust trigger 5 (with a small perturbation magnitude) and target class 4 (with orange decision region) changes the class distribution in the neighborhood of T1, 222, and T3. resulting in a larger LDP for the backdoored model than for the benign model.
Definition 3.2. (Samplewise Trigger Robustness (STR) Consider a backdoor attack with a trigger 6 and target class t E y against victim model f(;w). For any sample X and any isotropic Gaussian distribution (0, o² I), the STR is defined by the I-th entry of the SI.V for 8(x) (i.e. sample x with the trigger embedded), which is denoted by R o) (o(
Remarks: STR measures the resilience of trigger against Gaussian noises. Usually, strong STR can be naturally achieved by embedding the trigger in large variety of samples during training.
Definition 3.3. (Local Dominant Probability (L.D)) Consider a domain with K = | classes and an isotropic Gaussian distribution (0, T). The LDP for a classifier ((;ww) is defined by
K
s(w)
1
Σ
p(#g/w, olloc
(1)
K
where #1,-"" JKK are K independent random samples satisfying ((Xx: =
Vk E (1, Kj.
By the definition, LDP for a given classifier [(; w) is computed on .1,... JK indepen- dently sampled from the K classes respectively, satisfying / [ w) = k for Vk. LDP computed on more samples per class yields similar detection and certification performance empirically. Specifically, we first compute the SLPV for each of the K samples. Then we take the average of the K SLPVs and pick the maximum entry as the LDP for f(;w). Note that LDP always no less than π.
Remarks:
As stated in the key intuitions in Sec. 3.2, LDP tends to be larger for backdoored classifiers than for benign ones. This can be understood from the illustration in Fig. 1 for a classification domain with K = 4 classes. For the benign classifier on the left, the SLPVs for æ1. 24 are almost orthogonal to each other, leading to a small LDP close to 1. On the right, we consider a backdoor attack with a robust trigger 5 and target class 4 (with orange decision region). The strong STRs for 21, F2, and ry (represented by the large orange regions around 8(x1), ((22). and 8(xx)), together with the small trigger perturbation magnitudes (i.e. small [|ō(x;) æall2 for i 1, 2, 3). significantly change the class distribution in the neighborhood of each of 21, 22, and xz. particular, there will clear increment in the 4-th entry of the SIPVss for æ1, 222 and 23. Thus, the 4-th entry associated with the backdoor target class will dominate the average SLPV over Z1, ... II, leading to a large LDP.
3.4 CBD Detection Procedure
Although backdoored and benign classifiers have different LDP distributions, it is still a challenge in practice to set detection threshold. To solve this problem, we propose to use the conformal prediction, which employs a calibration set for supervision [66, 2]. Here, the calibration set consists of LDP statistics obtained from small number of benign shadow models trained on the small validation set possessed by the defender. However, the actual benign classifiers to be inspected are usually trained on more abundant data, such that the LDPs for these classifiers will likely follow different distribution from the LDPs for the shadow models without sufficient training. In particular, the LDPs in the calibration set (obtained from the shadow models) may easily have overly large sample variance and a heavy tail of large outliers. Directly using this calibration set for conformal prediction may lead to a conservative detection due an overly large detection threshold.
Thus, we propose an optional adjustment scheme that treats the m largest LDP statisties in the calibration set outliers. In practice, prior knowledge may be required to determine the exact value

---

of m. while in our experiments, a small m/N (< 0.2, where N is the size of the calibration set) may significantly increase the detection or certification power of our CBD with only small increment to the false positive rate. The detection procedure of our CBD consists of the following four steps:
1) Given a classifier f(; w) to inspected, estimate L.PP s(w) based on Def. 3.3.
2) Train (benign) shadow models {(; (1), ... ["; wx) on the clean validation dataset, and construct a calibration set Sy = {s(w)); (() ... s[wN]} } by computing the LDP for each model.
3) Compute the adjusted conformal p-value (assuming large outliers) defined by:
1 + min(({s E SN 8 < s(w) - mm}
qm (w)
(2)
N m +
4) Trigger an alarm if qm (w) S a, where a is a prescribed significance level (e.g, a=0.05).
4 CBD Certification
In addition to detection inference, CBD also provides certification, which is condition under which attacks are guaranteed to be detectable. Detailed proofs in this section are shown in App. A.
Theorem 4.1. (Backdoor Detection Guarantee) For arbitrary classifier f(::w) X + y to be inspected, let æ1, ... FK be the K randomly selected samples and NN, be the isotropic Gaussian distribution used to compute the LDP for f(; w). Let be the prescribed significance level of CBD. A backdoor attack with a trigger â and a target class t is guaranteed to be detected if:
A < < (11 S(N-m-lo(M (o(N)m+))) - (1
(3)
where & is the standard Gaussian CDF, ग mink=1.... ,K R lw, o) is the minimum STR over T1. 1...... TKK. A maxk=1,-.. KK [((2z) - xxl22 is the maximum perturbation magnitude of the trigger, m is the number of assumed outliers in the calibration set SN with size N, and ((n) denotes the n-th smallest element in SN.
Proof (sketch). The STR for each sample r& equals the t-th entry of the SLPV for 5(2%)) by Def. 3.2. We also connect the SLPV for 5(xx) to the SLPV for 23 using the Neyman- Pearson lemma ([49]). Based on this connection, we derive the lower bound for the minimum STR, such that the t-th entry of the SLPV of each Dg is sufficiently large to result in a large LDP for the attack to be detected. 0
Remarks: (1) (Main Results) For fixed trigger perturbation size (A), detection of attacks with larger STR (x) is more likely to guaranteed; while for fixed STR, detection of attacks with smaller trigger perturbation size is more likely to be guaranteed. (2) Our backdoor detection guarantee is inspired by the randomized smoothing approach in [10] for certified robustness against adversarial examples. However, certified backdoor detection and certified robustness against adversarial examples are fundamentally different, as will be detailed in App. I. (3) Certified backdoor detection and certified robustness against backdoors complement each other. The former provides detection guarantees to strong backdoor attacks, while the latter prevents the trigger from being learned during training [86, 53]. The two types of certification may cover the entire attack space together in the future, such that a backdoor attack will be either strong enough to be detected or weak enough to be disabled.
A meaningful certification for backdoor detection should also be along with guarantee for the false positive rate (FPR). Otherwise, one can easily design backdoor detector that always triggers an alarm, which provides detection guarantees to all backdoor attacks but is useless in practice.
Theorem 4.2. (Probabilistic Upper Bound for FPR) Consider a random calibration set SN {s1,-.. } with $1, ... SN i.i.d. following some continuous distribution F. Consider a random benign classifier ()) with LDP s(W) following some distribution F. Assume F dominates F in the sense of first-order stochastic dominance. Let m be any number of assumed outliers in SN and let a be any prescribed significance level of CBI). Then, the FPR of CBD on J(; W) conditioned on SN, which is denoted by ZN Ppgm (W) I ox ax|SN) based on Eq. (2), will be first-order dominated
by random variable B following Beta(m m + + N.N m - 1) with 1 = (a(N - m + 1)], i.e.
B E ZN. In other words, P(ZN S g) 2 P(B < q) for any real q.
Proof (sketch). We first express the false positive rate ZN in terms of the order statistics on the elements of the random calibration set Sx. Then, we derive the lower bound of the CDF of Z using the distribution of order statistics followed by binomial expansion.
5

---

Remarks:
The assumption that F dominates F in Thm. 4.2 generally holds in practice. Again, this is because the actual benign classifiers be inspected are usually trained on more abundant data than the benign shadow models. Empirical results supporting this assumption are shown in Sec. 5.4, Moreover, an analysis of this phenomenon is presented in App. B, where we show on binary Bayes classifiers that higher empirical loss can easily lead to larger expected LDP.
While we have shown that N conditioned on random calibration set of size N is upper bounded by a Beta random variable in the sense of first-order stochastic dominance, in Col. 4.3 below, we show that asymptotically, the upper bound of ZN converges to constant in probability as N oo. Corollary 4.3. (Asymptotic Property of FPR) Consider the settings in Thm. 4.2. For any 5 > limy P(N S T) = 1, where T = a + (1 - a + E with B = m/N.
Proof We show that any random variable B with the Beta distribution described in Thm. 4.2 satisfies x P(B (B < 7) = 1. Then, the corollary is proved since N is dominated by B. O
Remarks: For classical conformal prediction without adjustment where m = O, we will have 3 = 0 and lim P(Zv S a + {) for any { > 0. In this case, the upper bound of the false positive rate of our CBD converges to the prescribed significance level a in probability.
5 Experiment
There have been many different types of backdoor attacks proposed, each also with a wide range of configurations. Thus, it is infeasible to evaluate our CBD over the entire space of backdoor attacks. Inspired by the evaluation protocol for certified robustness [10], in Sec. 5.1, we focus on backdoor attacks with random perturbation triggers to comprehensively evaluate the certification capability of our CBD. In Sec. 5.2, we compare CBD with three state-of-the-ard backdoor detectors (all "uncertified") against backdoor attacks with three popular trigger types evaluate the detection capability of CBD. In Sec. 5.3, we present ablation studies (e.g. on the number of shadow models used by CBD). Additional results and other supportive empirical analyses are shown in Sec. 5.4.
5.1 Evaluation of CBD Certification
For certified robustness, the prediction of test example is unchanged with guarantee, if the magnitude of the adversarial perturbation is smaller than the certified radius [10]. Certified robustness usually evaluated by the certified accuracy on some random test set as the proportion of the samples that are guaranteed to be correctly classified if the magnitude of the adversarial perturbation is no larger than some prescribed value. As an analog, our certification for backdoor detection is specified by an inequality that involves both the STR and the perturbation magnitude of the trigger, which naturally produces two-dimensional "certifiedd region" (illustrated in Fig. 7 and Fig. 8 in Apdx. D). Our certification method is evaluated on set of random backdoor attacks, each using a random pattern as the trigger, with the perturbation magnitude satisfying some l2 constraint. We are interested in the proportion of the attacks falling into the certified region, i.e. guaranteed to be detected.
5.1.1
Setup
Dataset: Our experiments are conducted on four benchmark image datasets, GTSRB [60], SVHN [47], CIFAR-10 [30], and TinylmageNe [11], following their standard train-test splits. Due to the large number of models that will be trained to evaluate our certification method, except for GTSRB, we use 40% of the training set to train these models. We also reserve 5,000 samples from the test set of GTSRB, SVHN, and CIFAR-10, 10, and 10,000 samples from the test set of TinyImageNet (much smaller than the training size for the models for evaluation) for the defender to train the shadow models. More details about these datasets are deferred to App. C.I.
Evaluation Metric: Following the convention, the detection performance of CBD is evaluated by the true positive rate (TPR) defined by the proportion of attacks being detected (with a correct inference of the target class) and the false positive rate (FPR) defined by the proportion of benign classifiers falsely detected. For certification, we define certified TPR (CTPR) as the proportion of a set of attacks that are guaranteed to be detectable, i.e. falling into the certified region.
Attack Setting: For each dataset, we create 50 backdoor attacks, each with a randomly selected target class. For each attack, we generate random trigger, which is random perturbation embedded

---

GTSRB
SVHN
100
TM
75
CTPR (6-20)
0.4
0.6
0.8
1.0
1.2
1.4
1.6
0.1
0.2
0.3
0.4
0.5
TPR (8=0.1)
CIFAR-10
TinylmageNet
CTPR CTPR
100
100
80
TP8 (8-0
CTPR (6-22)
0.5
1.0
1.5
2.0
2.5 3.0
0.1
0.2
0.3
0.4
0
Figure 2: Certification performance of CBD against backdoor attacks with random triggers with perturbation magnituee Eg < 0.75 measured by CTPR (solid) for a range of for 3 0.1, 0.2. The CTPRs are all upper-bounded by the TPRs (dashed), showing the correctness of our certification. Notably, CBD achieves up to 98% (100%), 84% (100%). 98% (98%). and 40% (72%) CTPRs (TPRs) on GTSRB, SVHN, CIFAR- 10, and TinylmageNet, respectively, across all choices of a and B. An increment in 3, the assumed ratio of calibration outliers, may lead to further increments in both CTPR and TPR. The hyperparameter a can be determined using the calibration set in practice.
by ((x) + o with ||||| S 0.75. The generation process also involves random nullification of the trigger pattern, which helps the trigger to be learned. More details about trigger generation are deferred to App. C.2 due to space limitations. The poisoning ratios for the attacks on GTSRB, SVHN, CIFAR-10, 10, and TinylmageNet are 7.8%, 15.3%, 11.3%, and 12.4%, respectively. Lower poisoning ratios may largely reduce the attack success rate since many randomly generated triggers relatively hard to learn. Results for triggers with larger perturbation size are shown in App. D.
Training: For model architecture, we use the winning model on the leaderboard [31] for GTSRB, MobileNetV2 [54] for SVHN, the same architecture in [82] for CIFAR- 10, and ResNet-34 [22] for TinylmageNet. For each dataset, 50 benign models are trained (also on the 40% training set except for GTSRB) to evaluate the FPR. The accuracies for these benign models roughly 98%, 92%, 78%, and 47% on GTSRB, SVHN, CIFAR-10, and TinylmageNet, respectively. For each attack, train model with 2 90% attack success rate and S 2% degradation in the benign accuracy (or re-generate the attack for training until both conditions are satisfied), More details about the training configurations are shown in App. C.3. Finally, train 100 shadow models for each of GTSRB, SVHN, and CIFAR-10, and 50 shadow models for TinyImageNNi using the same architectures and configurations as above these shadow models are used by our CBD for detection and certification.
5.1.2 Certification Performance
In Fig. 2, we show the CTPR (solid) of our CBD against the attacks with the random perturbation trigger the four datasets for range of and for 3 m/N {0, 0.1, 0.2). The TPR (dashed) for each combination of a and |3 also plotted for reference. Recall that 3 here represents the proportion of assumed outliers in the calibration set for the adjustment of the conformal prediction, and a is the standard deviation of the isotropic Gaussian distribution for the LDP computation. In our experiments, 1024 random Gaussian noises are generated for each sample used to compute the I.P.. The significance level for conformal prediction is set to the classical a = 0.05 for statistical testing.
In general, certification is effective, which covers up 98%, 84%, and 98% backdoor attacks with the random perturbation trigger (all achieved with 3 = 0.2) on GTSRB, SVHN, and CIFAR-I0. respectively. Even for the very challenging TinylmageNet dataset, CBD certifies up 40% of these attacks. Moreover, for all choices of B and a, CTPR is upper- bounded by TPR. For example, for the aforementioned CTPRs the four datasets, the corresponding TPRs 100%, 100%, 98%, and 72%, respectively (with FPRs 0%. 0%, 6%, and 10%, respectively, see App. D). In fact, all attacks with the detection guarantee detected empirically, showing the correctness of certification.
We also make the following observations regarding the hyperparameters 3 and a: 1) An increment in 3 may lead to increment in both CTPR and TPR. This is due to the existence of a heavy tail
7

---

(corresponding to large outliers) in the LDP distribution for the calibration set. While an overly large may cause significant increment to FPR, our additional results in App. D show that empirically, this is not the case for 33 < 0.2. 2) Each domain has its own proper range for the choice of a. In general, the detection power of CBD (reflected by TPR) reduces as a becomes overly small. This phenomenon agrees with our remarks on Def. 3.1 - SLPV converges to a singleton at the labeled class as a approaches zero, regardless of the presence of a backdoor attack. Moreover, the certification power (reflected by CTPR) also reduces for small o which matches the inequality (3) in Thm. 4.1. For overly large o ss on the other hand, LDP for benign classifiers may also grow and possibly approach one, resulting in large FPR. However, in this case, LDP is no longer computed in truly 'local' context, contrary to the intuition implied by its name. In Sec. 5.2, we will introduce a practical scheme to choose proper for each domain based on the shadow models.
5.2 Evaluation of CBD Detection
Here, we show the detection performance of CBD against backdoor attacks with various trigger types, including the BadNet square [18], the "chessboard"" (CB) pattern [75], and the blended pattern [8]. For each of GTSRB, SVHN, and CIFAR-IO, we train 20 models (using the full training set) for each trigger type following the same training configurations described in Sec. 5.1.1. TinyImageNet is not considered here due to the high training cost. Details for each trigger type and attack settings are shown in App. C.4. We also compare CBD with three state-of-the-art backdoor detectors without certification, which are Neural Cleanse (NC) [67]. K-Arm [56]. and MNTD [82]. In particular, K-Arm and MNTD require manual selection of the detection threshold. For both of them, we choose the threshold that maximizes the TPR while keeping a 5% FPR for each dataset. Moreover, we devise a "supervised" version of CBD, named CBD which still uses LDP as the detection statistic but without the conformal prediction. The detection threshold for CBD sup is determined in the same way as for K-Arm and MNTD, i.e. by maximizing the TPR with a controlled 5% FPR.
In practice CBD needs to choose a moderately large a for each detection task. To this end, we first initialize small a such that for each of the N shadow models, the SLPVs for the K samples used for computing the LDP all concentrate at the labeled classes. In this case, the LDPs for all the shadow
[W,,.)) o) < th for some relatively small vo, where (x(x) is the k-th sample for LDP computation for the n-th model, i.e. the SLPVs are no longer concentrated at the labeled classes. In the left of Fig. 4, we show the choice of a based on the above scheme for range of V. which exhibits trend of convergence as vi decreases. We also notice that selected for 1a < 0.2 roughly matches the a choices in Fig. 2 that yields relatively high CTPR and TPR, showing the effectiveness of our scheme. In our evaluation of CBD detection, we set s 0.1, which yields a = 1.15, 0.39, 1.14 for GTSRB, SVHN and CIFAR- 10, respectively. Other choices of a for &b less than 0.2 yield similar detection performance.
models are close to 3- Then, gradually increase until N Σ Σ K.
pa(a (n)
As shown in Tab. 1, CBD) achieves comparable even higher TPRs than the SOTA detectors (that benefit from unrealistic supervision) for all trigger types on all datasets. CBD also provides non-trivial detection guarantees to most attack types these datasets. The relatively low CTPRs, e.g. for BadNet on GTSRB, are due to the large perturbation magnitude of the trigger. The even better TPRs achieved by CBDsup. though with the same supervision as for the SOTA detectors, show the effectiveness of the LDP statistic in distinguishing backdoored models from benign ones. Such effectiveness is further verified by the receiver operating characteristic (ROC) curves for CID Compared with the baseline detectors, CBDsup achieves generally higher overall areas under curves (AUCs) across the three datasets.
5.3 Ablation Study
We show that the time efficiency and data efficiency of CBD can be improved by training fewer shadow models and using fewer samples for training the shadow models, respectively, without significant degradation in the detection or certification performance. In particular, we show in Tab. 2 that CBD with 3 = 0.2 achieves similar TPRs and CTPRs for the same set of attacks in Sec. 5.2 when we reduce the number of shadow models from 100 to 50, 25, and 10, respectively. Such robustness of CBD to the calibration size further verifies the clear separation between the benign and backdoored classifiers using our proposed LDP. In Tab. 3, we show that with shadow models trained on only 100
8

---

Table 1: Certified detection of CBD for 3 0, 0,0.1,0.. (shaded), with the empirical detection performance (measured by TPR (%)) compared with NC, K-Arm, MNTD, and CBD sup against BadNet, CB, and Blend attacks GTSRB, SVHN, and CIFAR-10. The parentheses in each shaded cell contain the CTPR (%) associated with the TPR outside the parentheses. CBD achieves comparable or even higher empirical TPRs compared with the SOTA baselines and provides non-trivee -oiiiaiiial (or even tight) certification for different attacks and datasets. FPRs (%) are reported on benign classifiers.
GTSRB
SVHN
CIFAR-10
Average
benign
BadNet
CB
Blend
benign
BadNet
CB
Blend
benign
BadNet
CB
Blend
TPR
NC
20
75
40
20
95
50)
67.8
K-Arm
100
100
100
5
100
70
40
100
80
55
82.8
MNTD
20
0
5
100
75
35.6
CBDap
100
95
100
5
100
100
90
65
100
55
89.4
CBD
75 (5)
95 (80)
(20)
0
75 (45)
(100)
(75)
0
(D)
100 (90)
45 (30)
77.2
CRD
90 (15)
95 (85)
(25)
(55)
100 (100)
80 (80)
20
75 (20)
100 (95)
55 (35)
86.1
CBDaa
90 (15)
95 (85)
95 (35)
0
95 (65)
100 (100)
90 (80)
25
75 (25)
100(100)
60 (40)
88.9
SVHN
CIFAR-10
AUD compartson
1.0
1.0
GTSRB
CIFAR-10
TPR
0.5
0.5
TPR
0.5
MNTD
0.11
0.49
K-Arm
3.0
0.79
0.91
ROC (AUC- 0.98)
ROC (NUC 0.971
ROC (NUC 0.891
CBDsup 0.58
0.97
0.89
0.0
1.0
0.5
FPR
FPR
FPR
Figure 3: Receiver operating characteristic (ROC) curves of CBD aggregated over all three trigger types on GTSRB, SVNH, and CIFAR-10, respectively. CBDsup sup with our proposed LDP statistic achieves higher overall areas under curves (AUCs) than K-Arm and MNTD across the three datasets.
Table 2: Certified detection of CBD (with CTPR inside the parentheses and TPR outside) for B = 0.2 using 10, 25, 50, and 100 (the default in See. 5.2) shadow models. Both the detection and certification performance of CBD are not significantly affected by reducing the number of shadow models.
GTSRB
SVHN
CIFAR-10
# shadow
benign
BadNet
CB
Blend
benign
BadNet
CB
Blend
benign
BadNet
CB
Blend
10
95 (TO)
95 (85)
95 (35)
0
75 (45)
100 (100)
(75)
25
85 (25)
100 (100)
(40)
25
0
95 (5) 95 (85)
95 (25)
0
95 (45)
100 (100)
80 (75)
25
80 (25)
100 (100)
70 (40)
50
95 (15)
(85)
95 (40)
0
95 (65)
100 (100)
85 (75)
25
80 (25)
100 (100)
60 (40)
100
(15)
(35)
0
95 (65)
100 (100)
90 (80)
25
75 (25)
100 (100)
60 (40)
Table 3: Certified detection of CBD (with CTPR inside the parentheses and TPR outside) for B 0.2
and / = 0.4, respectively, with 100 shadow models trained on fewer samples (100 per class) than the default settings in Sec. 5.2. Due to the significantly insufficient training of the shadow models, a larger 3 is needed to maintain similar level of TPR and CTPR as in Sec. 5.2.
GTSRB
SVHN
CIFAR-10
benign BadNet
CB
Blend
henign
BadNet
CB
Blend
benign
BadNet
CB
Blend
CBDb2
(S) 95 (85)
(25)
75 (45)
(90)
(75)
35 (0) (90) (40)
CBDba
95
95 (85)
95 (35)
95 (45)
100 (100)
85 (75)
60 (10) 100 (95)
55 (40)
clean samples per class, CBD requires a larger achieve similar TPRs and CTPRs. This is because more shadow models will exhibit an abnormally large LDP due to significantly insufficient training.
5.4 Additional Experiments
Empirical validation of the stochastic dominance assumption in Thm. 4.2. In the middle of Fig. 4, we show the histograms (with the associated empirical CDF) of the LDP statistics for the shadow models and the benign models for all four datasets. The statistics for each dataset are obtained using the practically selected a. The LDP for the benign models is clearly dominated by the L.PP for the shadow models in the sense of first-order stochastic dominance.

---

200
10
VIaTe bangg
CPN-10
S.
100
"ay/naggelet
0.
80
choice cf
1.2
ASR or ACC (%)
1.00
24
02
02
1.4
04
05
50-
0.75
CIARTD
3.0
Thyymageteet
1
40-
0.50
LOULE
20
0.23
0.2
1.P
LOP
Figure 4: Supportive results: (Left) Choice of a for a range of & based on our selection scheme, which matches the choices in Fig. with high CTPR and TPR. (Middle) The histograms of the LDP statistics for the shadow models and the benign models, with the associated empirical CDFs. LDP for benign models is stochastically dominated by the LDP for shadow models for all datasets. (Right) Vulnerability of WaNet attack on GTSRB and SVHN. Attack success rate (ASR) reduces with negligible drop in benign accuracy (ACC) when inputs are smoothed by Gaussian noise.
Class imbalance is not the reason for a large LDP. In our experiments involving generally balanced datasets, backdoor poisoning (i.e. embedding the trigger in large variety of samples during training) not only enhances the trigger robustness of the attack, but also introduces an imbalance in the poisoned training set. Thus, it is important to show that the large LDPs observed in experiments of the robustness of the trigger, rather than the class imbalance. Note that if class imbalance can also cause a large LDP, there will easily be false alarms for benign classifiers trained on imbalanced datasets Here, we train two groups of benign models on SVHN, with 20 models per group. For the first group, the models are trained in the second group, the training set contains 4,400 additional images labeled to some randomly selected class. With the same model architecture and training configurations, the two groups have similar LDP distributions, with msd being 0.445 125 and 0.429+ 19, respectively. and with a 0.698 p-value for the t-test for mean. Thus, LDP will not be affected by class imbalance in general, and our method indeed detects the backdoor attack rather than the class imbalance.
result
balanced dataset with 3,000 images per class. For each model
Advanced attacks. Based on the key ideas in Sec. CBD requires the attack to have large STR over the sample distribution. However, this requirement is not always satisfied, especially for some advanced attacks with subtle, sample-specific triggers, such as WaNet [51]. Although not detectable or certifiable by our CBD, these attacks can hardly survive noises either from the environment or simple prepossessing- based defenses in practice. To see this, for each of GTSRB and SVHN, we train 20 models with successful WaNet attacks. We consider a simple test-time defense by applying 1024 randomly sampled Gaussian noises from distribution \0, o² to each input and then performing a majority vote. As shown in the right of Fig. 4, for both datasets and for small a, the average attack success rate (ASR) quickly drops without clear scarifies in the benign accuracy (ACC).
6 Conclusion
In this paper, we proposed CBD, the first certified backdoor detector, which is based on an adjustable conformal prediction using a novel LDP statistic. CBD not only performs detection inference but also provides a condition for attacks that are guaranteed to be detectable. Our theoretical results show that backdoor attacks with trigger more resilient noises and with a smaller perturbation magnitude are more likely to be detected with a guarantee. Our empirical results show the strong certification and detection performance of CBD on four benchmark datasets. In future research, we aim to enhance the certification bound to encompass backdoor attacks with larger trigger perturbation norms, such as rotational triggers and subject-based triggers.
Acknowledgements This work is partially supported by the National Science Foundation under grant No. 1910100, No. 2046726, No. 2229876, DARPA GARD, the National Aeronauties and Space Administration (NASA) under grant no. 8ONSSC20M0229, Alfred P. Sloan Fellowship, and the Amazon research award.
'This is the case for the backdoor detector in [68] which leverages the overlitting to the backdoor trigger during training benign classifiers trained on imbalanced datasets will also easily trigger a (false) detection.
10

---

References
[1] Model Zoo. https://modelzoo.co//
[2] Anastasios N. Angelopoulos and Stephen Bates. A gentle introduction to conformal prediction and distribution-free uncertainty quantification. 2021.
[3] Hamed Pirsiavash Aniruddha Saha, Akshayvarun Subramanya. Hidden trigger backdoor attacks. In AAAI Conference on Artificial Intelligence (AAAI), 2020.
[4] Eitan Borgnia, Jonas Geiping, Valeriaa Cherepanova, Liam Fowl, Arjun Gupta, Amin Ghiasi, Furong Huang, Micah Goldblum, and Tom Goldstein. DP-InstaHide: Provably Defusing Poisoning and Backdoor Attacks with Differentially Private Data Augmentations. In ICLR Workshop on Security and Safety in Machine Learning Systems, March 2021.
[5] Bryant Chen, Wilka Carvalho, Nathalie Baracaldo, Heiko Ludwig, Benjamin Edwards, Taesung Lee, Ian Molloy, and Biplav Srivastava. Detecting backdoor attacks on deep neural networks by activation clustering. http://aarxiv.or//bbs// 181 1.03728, Nov 2018.
[6] Huili Chen, Cheng Fu, Jishen Zhao, and Farinaz Koushanfar. DeepInspect: A black-box trojan detection and mitigation framework for deep neural networks. In International Joint Conference on Artificial Intelligence (IJCAI), pages 4658-4664, 7 2019.
[7] Pin-Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsieh. Zoo: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models. In ACM Workshop Artificial Intelligence and Security (AISec), page 15-26, 2017.
[8] Xinyun Chen, Chang Liu, Bo Li, Kimberly Lu, and Dawn Song. Targeted backdoor attacks on 2017.
deep learning systems using data poisoning.
[9] Edward Chou, Florian Tramèr, and Giancarlo Pellegrino. Sentinet: Detecting localized universal attacks against deep learning systems. In 2020 IEEE Security and Privacy Workshops (SPW), pages 48-54. IEEE, 2020.
[10] Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In Proceedings of the 36th International Conference on Machine Learning, pages 1310-1320, 2019.
[11] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large- scale hierarchical image database. In JEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 248-255, 2009.
[12] Bao Gia Doan, Ehsan Abbasnejad, and Damith C. Ranasinghe, Februus: Input purification defense against trojan attacks on deep neural network systems. In Annual Computer Security Applications Conference (ACSAC), page 897-912, 2020.
[13] Yinpeng Dong, Xiao Yang, Zhijie Deng, Tianyu Pang. Zihao Xiao, Hang Su, and Jun Zhu. Black-box detection of backdoor attacks with limited information and data. In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), 2021.
[14] Min Du, Ruoxi Jia, and Dawn Song. Robust anomaly detection and backdoor attack detection via differential privacy. In International Conference on Learning Representations (ICLR), 2020.
[15] Yansong Gao, Change Xu, Derui Wang, Shiping Chen, Damith C. Ranasinghe, and Surya Nepal. STRIP: A defence against trojan attacks on deep neural networks. In Anmual Computer Security Applications Conference (ACSAC), 2019.
[16] Jonas Geiping. Liam Fowl, Gowthami Somepalli, Micah Goldblum, Michael Moeller, and Tom Goldstein. What doesn't 't kill you makes you robust(er): Adversarial training against poisons and backdoors. In ICLR 2021 Workshop on Security and Safety in Machine Learning Systems, 2021.
[17) Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adver- sarial examples. In International Conference on Learning Representations (ICLR), 2015.
11

---

[18] Tianyu Gu, Kang Liu, Brendan backdooring attacks on deep neural networks. IEEE Access, 7:47230-47244, 2019.
and Siddharth Garg. Badnets: Evaluating
[19] Jiyang Guan, Zhuozhuo Tu, Ran He, and Dacheng Tao. Few-shot backdoor defense using shapley estimation. In CVPR, 2022.
[20] Wenbo Guo, Lun Wang. Xinyu Xing, Min Du and Dawn Song. TABOR: A highly accurate approach to inspecting and restoring Trojan backdoors in Al systems. http://wwww..rrgaaa//99....0..
2019.
[21] Frank R. Hampel. The influence curve and its role in robust estimation. Journal of the American Statistical Association, 69, 1974.
[22] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016.
[23] Sanghyun Hong, Varun Chandrasekaran, Yigitcan Kaya, Tudor Dumitras, and Nicolas Pa- pernot. On the effectiveness of mitigating data poisoning attacks with gradient shaping. https//arrv..or/aab/200011111 2020.
[24] Xiaoling Hu, Xiao Lin, Michael Cogswell, Yi Yao, Susmit Jha, and Chao Chen. Trigger hunting with a topological prior for trojan detection. In International Conference on Learning Representations, 2022.
[25] Kunzhe Huang. Yiming Li, Baoyuan Wu, Zhan Qin, and Kui Ren. Backdoor defense via decoupling the training process. In International Conference on Learning Representations (ICLR), 2022.
[26] Andrew Ilyas, Sung Min Park, Logan Engstrom, Guillaume Leclerc, and Aleksander Madry. Datamodels: Predicting predictions from training data, 2022.
[27] Jinyuan Jia, Yupei Liu, Xiaoyu Cao, and Neil Zhenqiang Gong. Certified robustness of nearest neighbors against data poisoning and backdoor attacks. In AAAI Conference on Artificial Intelligence, 2020.
[28] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Interna- tional Conference on Learning Representations (ICLR), 2015.
[29] Soheil Kolouri, Aniruddha Saha, Hamed Pirsiavash, and Heiko Hoffmann. Universal litmus patterns: Revealing backdoor attacks in cnns. In IEEF/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 298-307, 2020.
[30] Alex Krizhevsky, Learning multiple layers of features from tiny images. University of Toronto, 05 2012.
[31] Leaderboard. GTSRB Leaderboard. https://www.kaggt hww.ga/w.../////ppooooaaaa11-000 leaderboard, 2018.
[32] Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. In 2019 IEEE Symposium on Security and Privacy (SP), 2019.
[33] Linyi Li, Tao Xie, and Bo Li. SoK: Certified Robustness for Deep Neural Networks. In 44th IEEE Symposium on Security and Privacy, San Francisco, CA, 2023.
[34] Xi Li, Zhen Xiang, David J. Miller, and George Kesidis. Test-time detection of backdoor triggers for poisoned deep neural networks. In ICASSP 2022 2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2022.
[35] Yige Li, Xixiang Lyu, Nodens Koren, Lingjuan Lyu, Bo Li, and Xingjun Ma. Neural Atten- tion Distillation: Erasing Backdoor Triggers from Deep Neural Networks. In International Conference on Learning Representations (ICLR), 2021.
[36] Yiming Li, Yong Jiang, Zhifeng Li, and Shu-Tao Xia. Backdoor learning: A survey. IEEE Transactions on Neural Networks and Learning Systems, pages 1-18, 2022.
12

---

[37] Yuezun Li, Yiming Li, Baoyuan Wu, Longkang Li, Ran He, and Siwei Lyu. Invisible backdoor attack with sample-specific triggers. In IEEE International Conference on Computer Vision (ICCV), 2021.
[38] Cong Liao, Haoti Zhong, Anna Squicciarini, Sencun Zhu, and David Miller. Backdoor em- bedding in convolutional neural network models via invisible perturbation. In CODASPY, 2020.
[39] Ji Lin, Chuang Gan, and Song Han. Defensive quantization: When efficiency meets robustness. In International Conference on Learning Representations (ICLR), 2019.
[40] Kang Liu, Brendan Dalin-Gavitt, and Siddharth Garg. Fine-pruning: Defending against backdoor attacks on deep neural networks. In International Symposium on Research in Attacks, Intrusions, and Defenses (RAID), 2018.
[41] Yingqi Liu, Wen-Chuan Lee, Guanhong Tao, Shiqing Ma, Yousra Aafer, and Xiangyu Zhang. ABS: Scanning neural networks for back-doors by artificial brain stimulation. In ACM SIGSAC Conference on Computer and Communications Security (CCS), page 1265-1282, 2019.
[42] Yingqi Liu, Shiqing Ma, Yousra Aafer, Wen-Chuan Lee, Juan Zhai, Weihang Wang, and Xiangyu Zhang. Trojaning attack on neural networks. In Network and Distributed System Security (NDSS) Symposium, San Diego, CA, 2018.
[43] Yunfei Liu, Xingjun Ma, James Bailey, and Feng Lu. Reflection Backdoor: A Natural Backdoor Attack on Deep Neural Networks. In European Conference on Computer Vision (ECCV), 2020.
[44] Wanlun Ma, Derui Wang, Ruoxi Sun, Minhui Xue, Sheng Wen, and Yang Xiang. The "beatrix" resurrections: Robust backdoor detection via gram matrices. arXiv preprint arXiv:2209.11715. 2022.
[45] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations (ICLR), 2018.
[46] David Miller, Zhen Xiang, and George Kesidis. Adversarial learning in statistical classification: A comprehensive review of defenses against attacks. Proceedings of the IEEE, 108:402 433, 2020.
[47] Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y. Ng. Reading digits in natural images with unsupervised feature learning. In NIPS Workshop on Deep Learning and Unsupervised Feature Learning 2011, 2011.
[48] NeurIPS. Trojan Detection Challenge NeurIPS 2022. attps://rrrojaneeecciooo. 2022.
[49] Jerzy Neyman and Egon S. Pearson. On the problem of the most efficient tests of statistical hypotheses. Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of a Mathematical or Physical Character, 231:289-337, 1933.
[50] Anh Nguyen and Anh Tran. Input-aware dynamic backdoor attack. In Proceedings of Advances in Neural Information Processing Systems (NeurIPS). 2020.
[51] Anh Nguyen and Anh Tran. Wanet- imperceptible warping- basedd backdoor attack. In Interna- tional Conference on Learning Representations (ICLR), 2021.
[52] David Wagner Nicholas Carlini. Towards evaluating the robustness of neural networks. In IEEE Symposium Security and Privacy (SP), pages 39-57, May 2017.
[53] Elan Rosenfeld, Ezra Winston, Pradeep Ravikumar, and J. Zico Kolter. Certified robustness to label-flipping attacks via randomized smoothing. In Proceedings of the 37th International Conference Machine Learning. 2020.
[54] Mark Sandler, Andrew Howard, Menglong Zhu, Andrey Zhmoginov, and Liang-Chieh Chen. Inverted residuals and linear bottlenecks: Mobile networks for classification, detection and segmentation. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2018.
13

---

[55] Esha Sarkar, Yousif Alkindi, and Michail Maniatakos. Backdoor suppression in neural networks using input fuzzing and majority voting. IEEE Design & Test, 37(2):103-110, 2020.
[56] Guangyu Shen, Yingqi Liu, Guanhong Tao, Shengwei An, Qiuling Xu, Siyuan Cheng, Shiqing Ma, and Xiangyu Zhang. Backdoor Scanning for Deep Neural Networks through K-Arm Optimization. In International Conference on Machine Learning (ICML), 2021.
[57] Yanyao Shen and Sujay Sanghavi. Learning with bad training data via iterative trimmed loss minimization. In International Conference on Machine Learning (ICML), pages 5739-5748,
2019.
[58] Gagandeep Singh, Timon Gehr, Matthew Mirman, Markus Püschel, and Martin Vechev. Fast and effective robustness certification. In Advances in Neural Information Processing Systems, 2018.
[59] Gagandeep Singh. Timon Gehr, Markus Püschel, and Martin Vechev. Robustness certification with refinement. In International Conference on Learning Representations, 2019.
[60] Johannes Stallkamp, Marc Schlipsing, Jan Salmen, and Christian Igel. Man vs. computer: Benchmarking machine learning algorithms for traffic sign recognition. Neural Networks, 2012.
[61] Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Good- fellow, and Rob Fergus. Intriguing properties of neural networks. In International Conference on Learning Representations (International Conference on Learning Representations (ICLR)), 2014.
[62] Guanhong Tao, Guangyu Shen, Yingqi Liu, Shengwei An, Qiuling Xu, Shiqing Ma, Pan Li, and Xiangyu Zhang. Better trigger inversion optimization in backdoor scanning. In 2022 Conference on Computer Vision and Pattern Recognition (CVPR 2022), 2022.
[63] Brandon Tran, Jerry Li, and Aleksander Madry. Spectral signatures in backdoor attacks. In Advances in Neural Information Processing Systems (NIPS), 2018.
[64] IARPA TrojAI: Trojans in artificial intelligence. https///www..nnaa..o///eeeesssss programs/troja//roaaibbue 2019.
[65] Alexander Turner, Dimitris Tsipras, and Aleksander Madry. Clean-label backdoor attacks. https://peoople.csall csail. mit. cdl/mmdyy/ll////aaaablll.. 2019.
[66] Vladimir Vovk. Conditional validity of inductive conformal predictors. In Proceedings of the Asian Conference on Machine Learning, pages 475-490, 04-06 Nov 2012.
[67] Bolun Wang, Yuanshun Yao, Shawn Shan, Huiying Li, Bimal Viswanath, Haitao Zheng, and Ben Y. Zhao. Neural cleanse: Identifying and mitigating backdoor attacks in neural networks. In IEEE Symposium on Security and Privacy (SP), 2019.
[68] Hang Wang, Zhen Xiang, David J Miller, and George Kesidis. Mm-bd: Post-training detection of backdoor attacks with arbitrary backdoor pattern types using maximum margin statistic. In 2024 IEEE Symposium on Security and Privacy (SP), 2024.
[69] Ren Wang, Gaoyuan Zhang, Sijia Liu, Pin- Yu Chen, Jinjun Xiong, and Meng Wang. Practical detection of trojan neural networks: Data- limited and data-free cases. In European Conference on Computer Vision (ECCV), 2020.
[70] Zhenting Wang, Juan Zhai, and Shiqing Ma. Bppattack: Stealthy and efficient trojan attacks against deep neural networks via image quantization and contrastive adversarial learning. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2022.
[71] Maurice Weber, Xiaojun Xu, Bojan Karlaš, Ce Zhang, and Bo Li. Rab: Provable robustness against backdoor attacks. In 2023 2023 IEEE Symposium on Security and Privacy (SP) (SP), pages 640-657, 2023.
[72] Dongxian Wu and Yisen Wang. Adversarial neuron pruning purifies backdoored deep models. In NewrIPS, 2021.
14

---

[73] Zhen Xiang, David J. Miller, Siheng Chen, Xi Li, and George Kesidis. Detecting backdoor attacks against point cloud classifiers. In IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2022.
[74] Zhen Xiang, David J. Miller, and George Kesidis. A benchmark study of backdoor data poisoning defenses for deep neural network classifiers and a novel defense. In IEEE MLSP, Pittsburgh, 2019.
[75] Zhen Xiang, David J. Miller, and George Kesidis. Detection of backdoors in trained classifiers without access to the training set. IEEE Transactions on Neural Networks and Learning Systems, pages 1-15, 2020.
[76] Zhen Xiang, David J. Miller, and George Kesidis. L-RED; Efficient post-training detection of imperceptible backdoor attacks without access to the training set. In IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 3745-3748 2021.
[77] Zhen Xiang, David Miller, and George Kesidis. Reverse engineering imperceptible backdoor attacks deep neural networks for detection and training set cleansing. Computers and Security, 106, 2021.
[78] Zhen Xiang, David J. Miller, and George Kesidis. Post-training detection of backdoor attacks for two-class and multi-attack scenarios. In International Conference on Learning Representations (ICLR), 2022.
[79] Zhen Xiang, David J. Miller, Hang Wang, and George Kesidis. Detecting scene-plausithe perceptible backdoors in trained DNNs without access to the training set. Neural Computation, 33(5):1329-1371 2021.
[80] Zhen Xiang, Zidi Xiong, and Bo Li. Umd: Unsupervised model detection for x2x backdoor attacks. In Proceedings of the 40th International Conference on Machine Learning, 2023.
[81] Weilin Xu, David Evans, and Yanjun Qi. Feature squeezing: Detecting adversarial examples in deep neural networks. In Network and Distributed System Security (NDSS) Symposium, 2018.
[82] Xiaojun Xu, Qi Wang, Huichen Li, Nikita Borisov, Carl A. Gunter, and Bo Li. Detecting AI Trojans using meta neural analysis. In JEEE Symposium on Security and Privacy (SP), 2021.
[83] Mingfu Xue, Can He, Jian Wang, and Weiqiang Liu. One-to-n & n-to-one: Two advanced backdoor attacks against deep learning models. IEEE Transactions on Dependable and Secure Computing, 19(3):1562-1578, 2022.
[84] Mingfu Xue, Shifeng Ni, Yinghao Wu, Yushu Zhang, Jian Wang, and Weigiang Liu. Impercep- tible and multi-channel backdoor attack against deep neural networks, 2022.
[85] Yi Zeng, Si Chen, Won Park, Z. Morley Mao, Ming Jin, and Ruoxi Jia. Adversarial unlearning of backdoors via implicit hypergradient. In International Conference Learning Representations (ICLR), 2022.
[86] Yuhao Zhang, Aws Albarghouthi, and Loris D'Ant. Bagflip: A certified defense against data poisoning. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022.
[87] Zhendong Zhao, Xiaojun Chen, Yuexin Xuan, Ye Dong. Dakui Wang, and Kaitai Liang. Defeat: Deep hidden feature backdoor attacks by imperceptible perturbation and latent representation constraints. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2022.
[88] Runkai Zheng, Rongjun Tang, Jianze Li, and Li Liu. Data-free backdoor removal based on channel lipschitzness. In ECCV, 2022.
15


Reviews:
[{"review_id": "JDSTvgMLrE", "reviewer": "Reviewer_MHNa", "summary": "This paper proposes a certification method to detect backdoored models. It is based on the assumption that backdoor triggers are robust, meaning that adding random noises onto trigger-injected samples will not change their predictions (to the target label). It also assumes that the neighborhood of a given input (by adding random noises) will be likely predicted as the target as well. This paper hence leverages the output probability difference between clean models and backdoored models when inputs are perturbed with small random noises. It uses a set of shadow models trained on a subset of clean data to facilitate the detection/certification. The evaluation is conducted on four image benchmarks and the results show the proposed method has a reasonable detection/certification performance.", "questions": "See above.", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. This paper shows the possibility of conducting certification in the post-training setting, where a model is given without knowing whether it is backdoored or not.\n\n2. It is interesting to leverage the output probability difference between clean and backdoored models when the inputs are perturbed by random noises.", "weaknesses": "1. While the perspective of this paper is quite interesting, it is not instantly clear to me why the proposed method can be regarded as a certification method. It is evident that the proposed approach requires training a bunch of shadow models and the certification bound is determined by them. Algorithm Theorem 4.2 provides a theoretical analysis on the usage of benign models, it does not provide a guarantee that those shadow models trained a small subset exhibit the same needed behavior as a benign model trained on the full dataset.\n\n2. Following up the previous point regarding using shadow models, the comparison between SOTA detectors and the proposed approach may not be fair. This paper requires 5000 samples (10000 samples for TinyImageNet) to train shadow models. Such a large number of samples are normally not required for existing detectors. They only needs a few images (less than 10 from each class) to detect backdoored models. For a fair comparison, those baseline techniques should be modified to make full use of the same number of samples for detection.\n\n3. The detection accuracy of NC is unreasonably low on BadNet. According to the original paper and many followup works, NC should not have problem detecting backdoored models by BadNet. The authors should conduct a sanity check to ensure all the baselines are implemented correctly. In addition, the baseline detectors are all from two years ago and dated. There are plenty of recent SOTA detectors, e.g., [23][58]. This paper should at least compare with one or two recent methods.\n\n4. In Section 3.2 at line 110-113, this paper claims that because the backdoor perturbation is usually small, \"a significant proportion of samples in the neighborhood of x will also be classified to class t.\" This is not necessary true. If the backdoor trigger is a yellow square at the top left corner on an image, I don't think adding small random noises on a clean image will lead to the target-class prediction. If this is the case, the model must have very low performance as a small random noise can easily change the prediction.\n\n5. The entire detection/certification procedure is based on the assumption that backdoored models have a higher robustness when the inputs are added with random noises. This paper shows that an existing attack that violates this assumption can be defended by adding random noises during inference. However, an adaptive attacker can intentionally reduce the robustness of backdoor triggers to the same noise level as the proposed approach. In this case, the proposed approach cannot certify the model. Any random noise smaller than that used in the certification also cannot affect the trigger. Note that if using a noise level larger than the certification noise can remove the backdoor effect, there is no need for certification as the problem can be easily solved.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer MHNa\n\nThank you for your time and effort in reviewing our paper. In the following, we address each of your concerns in detail.\n___\n**Q1:** Why is the proposed method certified?\n\n**A1:** Thanks for your question. Our certification consists of the following two parts.\n\nFor the first part, given any calibration set (or just a detection threshold), backdoor attacks satisfying **Inequality (3)** are guaranteed to be detectable -- based on the existence of such a detection guarantee, our detector is certified.\n\nThe second part of our certification is a probability upper bound on the false positive rate to avoid overly aggressive detection. We assume that the LDP distribution for the shadow models has a first-order stochastic dominance over the LDP distribution for the benign models with much more sufficient training (**line 195**). This assumption is empirically validated in the middle of **Figure 4** and is analyzed theoretically in **Appendix B**.\n\nIn addition, as the first work to study certified backdoor detection, our certification is non-trivial as shown by the results in **Figure 2 (solid lines)** and **Table 1 (in the parenthesis)**.\n\n**Q2 :** About the fairness in comparison\n\n**A2 :** Thanks for your comment. First, as the best among the three baselines we compared with, K-Arm first performs trigger reverse-engineering and then compares the estimated trigger sizes with a prescribed threshold, which is largely dependent on the classification domain. Thus, in practice, K-Arm also needs to train shadow models to pick a threshold for each domain. In our experiments, we have optimized the thresholds for K-Arm (and also MNTD) on each dataset by maximizing the TPR subject to a 5% FPR (**lines 308-309**). Thus, we actually helped to tune these methods to achieve their best performance. In fact, given a prescribed detection threshold, our CBD requires only **one image per class** for each model inference (**Definition 3.3**) – much fewer than the number of images required by K-Arm.\n\nIn addition, following your suggestion, we conducted experiments for CBD with $\\beta=0.2$ and $\\beta=0.4$, respectively, when the shadow models are trained on only **100 samples per class**. The results in the table below show that CBD can maintain a decent detection and certification performance with only a limited number of data.\n\n||GTSRB||||SVHN||||CIFAR10||||\n|-|-|-|-|-|-|-|-|-|-|-|-|-|\n||benign|BadNet|CB|Blend|benign|BadNet|CB|Blend|benign|BadNet|CB|Blend|\n|CBD0.2|0|90(5)|95(85)|90(25)|0|75(45)|100(95)|80(75)|0|35(0)|95(90)|45(40)|\n|CBD0.4|0|95(5)|95(85)|95(35)|0|95(45)|100(100)|85(75)|5|60(10)|100(95)|55(40)|\n\n**Q3 :** Performance of NC\n\n**A3 :** We directly used the NC code from BackdoorBench. As shown in Table 1(a) of [1] and Table 3 of [2], NC achieves around 50% TPR/recall on GTSRB for the BadNet square, which is consistent with our results in Table 1. For CIFAR-10, we used the same model architecture as in [3]. In Table 3 of [3], NC achieves 0.537 AUC on CIFAR-10 for BadNet, which is also consistent with our results in Table 1.\n\nThank you for pointing out the recent detectors. These methods may perform better than K-Arm, but the performance gain may be small, since K-Arm has already achieved a high detection accuracy. Still, we will include the comparison results in our revision.\n\n[1] Guo et al, TABOR: A highly accurate approach to inspecting and restoring Trojan backdoors in AI systems, 2019.\n[2] reference [64] in our paper\n[3] reference [70] in our paper\n\n**Q4 :** Detection performance against triggers with large perturbation size\n\n**A4 :** Thanks for your comment. Intuitively, whether a BadNet square can be detected using our method depends on the size of the square and the robustness of the learned trigger. Using **Figure 1(b)** for illustration, the smaller the size of the square is, the closer $\\delta(x_1)$ is to $x_1$; the stronger the trigger robustness is, the larger the orange area around $\\delta(x_1)$ can be. Thus, for any fixed noise std $\\sigma$, small square triggers that are robustly learned will likely be detected.\n\nFor our results in **Table 1**, we used 2x2 squares on GTSRB and CIFAR-10, and 3x3 squares on SVHN (see **Appendix C4**). Moreover, the noise stds used for GTSRB, SVHN, and CIFAR-10 are 1.15, 0.39, and 1.14, respectively (**line 322**), which are actually not small. This is possibly the reason why our method can still detect some backdoor attacks with a small BadNet square.\n\n**Q5 :** Adaptive attacks and needs for certification\n\n**A5 :** First, in many subfields of trustworthy machine learning, one of the major goals for developing certified defenses is to mitigate potential new adaptive attacks and the follow-up defenses against them (e.g., security cat and mouse game). For the robustness against adversarial examples, for instance, an attacker can always find an adversarial perturbation that effectively fools a model by increasing the perturbation size. However, certified defenses guarantee a desired output when the adversarial perturbation is within some certified radius. In other words, if the perturbation budget is less than the certified radius, an adaptive attacker is guaranteed to fail.\n\nFor backdoor attacks, existing certified defenses we cited in **line 80** provide guarantees on the training-time failure of trigger injection into the model and/or test-time failure of trigger recognition – both failures require the attack to be sufficiently weak and satisfy certain adversarial constraints (i.e. with low trigger robustness on defenseless models). Our CBD, however, focuses on backdoor attacks with strong trigger robustness, which is complementary to existing certified backdoor defenses (**Remark (2), line 189**). We expect this certification gap to be closed by future works considering diverse adversarial constraints.\n___\nThanks again for your insightful comments and suggestions. Please let us know any further questions you may have."}, {"review_id": "GXJOWzwRDP", "reviewer": "Reviewer_jLvZ", "summary": "This paper proposes CBD, a certified detection method for backdoor attacks. It leverages a newly proposed statistic: local dominant probability to capture the target label probability increment in the neighborhood of infected instances. The theoretical analysis provides both detection inference and the condition that detection can be guaranteed. Compared to empirical detectors, CBD also shows comparable or even better detection performance across 4 benchmark datasets and 3 types of attacks.", "questions": "Most of the existing backdoor detectors do not provide theoretical guarantee, which makes them vulnerable to zero-day attacks or trigger types. This paper proposes the first backdoor detection framework with theoretical guarantee. Hence, I believe this paper is valuable. However, I still have several concerns regarding experimental design and details, which might neutralize the performance improvement of the proposed method compared to baselines. \n\n1. In line 259-261, authors mentioned that ‘we train 100 shadow models for each of GTSRB,SVHN, and CIFAR-10, and 50 shadow models for TinyImageNet using the same architectures and  configurations as above – these shadow models are used by our CBD for detection and certification.’ My concern is that training shadow models might significantly increase the detection overhead and make the proposed method time-consuming.  Can you provide the detection overhead of the proposed method under a different number of shallow models and compare them with baseline methods?  It might be impractical to scale the proposed method up to large models(such ImageNet model) if it is slow. \n\n2. In line 235, authors mentioned that ‘We also reserve 5,000 samples from the test set  of GTSRB, SVHN, and CIFAR-10, and 10,000 samples from the test set of TinyImageNet (much smaller than the training size for the models for evaluation) for the defender to train the shadow models. ’  The number of samples needed for CBD is much larger compared to baseline methods, such as K-Arm and NC. Reverse-engineering based detectors usually only require around 10-20 samples to achieve good performance. I am concerned that this sample size discrepancy might cause the comparison unfair. It would be more convincing if authors can show the performance of CBD stays under a smaller number of clean samples.", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. The topic is trending and important for the community \n\n2. The paper is overall well-written and easy to follow\n\n3. The proposed method is largely novel and theoretical analysis is sound.\n\n4. The proposed CBD can outperform several state-of-the-art empirical detectors effectiveness wise.", "weaknesses": "1. The evaluation regarding the efficiency of CBD is missing\n\n2. Threat model is not consistent with baselines and comparison might be unfair.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer jLvZ\nThank you for your time and effort in reviewing our paper and your positive comments. In the following, we address each of your concerns in detail.\n___\n**Q1 :** Time efficiency of CBD\n\n**A1 :** Thank you for your comment. We discuss the time efficiency of CBD from three aspects.\n\n**a. The detection overhead of CBD**\n\nThe detection overhead of our CBD is shown in **Appendix E**. For GTSRB, SVHN, CIFAR-10, and TinyImageNet, each shadow model training requires 39s, 45s, 31s, and 2462s, respectively, on a single RTX 2080 Ti card; while the LDP estimation for each model requires merely 8s, 4s, 7s, and 86s on the four datasets respectively. Thus, on GTSRB for example, it will take roughly (39s+8s)xN to get a calibration set of size N.\n\n**b. In practice, existing (uncertified) backdoor detectors, such as K-Arm, also need shadow models to pick a detection threshold.** \n\nMany existing defenses, all uncertified, perform backdoor detection using statistics (e.g. trigger size) derived from the synthesized triggers. Some of them, such as Neural Cleanse (NC), are implemented with an unsupervised anomaly detector to capture any outlier statistics, but are not reliable due to the existence of “natural backdoors” in many practical datasets. Other methods, such as K-Arm, directly set a threshold (e.g.) on the estimated trigger size, which is clearly dependent on the classification domain. Thus, in practice, these methods still need calibration, e.g. using shadow models as we did, to set a detection threshold.\n\n**Comparison**: If a detection threshold is set, K-Arm will need 382s, 247s, and 240s for each model inference on GTSRB, SVHN, and CIFAR-10, respectively, while NC requires 5968s, 1038s, and 816s, respectively – both are much slower than our CBD in per-model inference. Moreover, if K-Arm also trains N shadow models to determine the detection threshold, on GTSRB for example, it will take 382sxN to apply K-Arm to all N shadow models, which is much longer than 8sxN for CBD.\n\n**c. The time efficiency of CBD can be improved, likely without sacrificing the detection accuracy, by using fewer shadow models.** \n\nTheoretically, with fewer shadow models, the expectation of the detection threshold being selected will not change, though its variance will increase. However, we observe that LDPs for backdoored models being detected are generally very large, such that moderate fluctuation in the detection threshold will not significantly affect the performance of CBD.\n\nThis is reflected in the results in the table below, where we show the detection accuracy (both empirical and certified (in the parenthesis)) of CBD with $\\beta=0.2$ using **10, 25, and 50** shadow models, respectively. These shadow models are randomly sampled from the 100 shadow models we trained for each dataset for the results in our paper. We didn’t compare CBD with the baselines against attacks on TinyImageNet in this work, since training a sufficient number of backdoored models for evaluation on the entire TinyImageNet dataset is very time-consuming.\n\n||GTSRB||||SVHN||||CIFAR10||||\n|-|-|-|-|-|-|-|-|-|-|-|-|-|\n||benign|BadNet|CB|Blend|benign|BadNet|CB|Blend|benign|BadNet|CB|Blend|\n|10|0|95(10)|95(85)|95(35)|0|75(45)|100(100)|90(75)|25|85(25)|100(100)| 55(40)|\n|25|0|95(5)|95(85)|95(25)|0|95(45)|100(100)|80(75)|25|80(25)|100(100)|70(40)|\n|50|0|95(15)|95(85)|95(40)|0|95(65)|100(100)|85(75)|25|80(25)|100(100)|60(40)|\n\n**Q2 :** Data efficiency of CBD\n\n**A2 :** Thanks for the comment. Again, reverse-engineering-based detectors, if not equipped with an anomaly detector (which is usually not scalable to a large number of classes), may still need to determine a detection threshold in practice, likely by training a set of shadow models for calibration. In fact, if the calibration set is given, both detection and certification of CBD will only need **one** sample per class (for the estimation of LDP, remarks in line 142), which is much less than the data size required by reverse-engineering-based detectors. Thus, for a fair comparison (e.g.) with K-Arm in practical scenarios, our method actually requires fewer clean samples for detection.\n\nStill, we evaluate CBD with the shadow models trained on fewer samples. In this case, more shadow models will exhibit an abnormally large LDP due to the significantly insufficient training; thus, a larger outlier fraction $\\beta$ should be considered. In the table below, we show the detection performance of CBD, with $\\beta=0.2$ and $\\beta=0.4$, respectively, on GTSRB, SVHN, and CIFAR-10, respectively, with only **100 samples per class** used for training the shadow models. Although we have observed a slight performance drop due to the insufficient training of the shadow models, the detection performance of our CBD is still comparable to the uncertified detectors such as K-Arm. \n||GTSRB||||SVHN||||CIFAR10||||\n|-|-|-|-|-|-|-|-|-|-|-|-|-|\n||benign|BadNet|CB|Blend|benign|BadNet|CB|Blend|benign|BadNet|CB|Blend|\n|CBD0.2|0|90(5)|95(85)|90(25)|0|75(45)|100(95)|80(75)|0|35(0)|95(90)|45(40)|\n|CBD0.4|0|95(5)|95(85)|95(35)|0|95(45)|100(100)|85(75)|5|60(10)|100(95)|55(40)|\n\nWe also consider an extreme case on GRSRB and CIFAR-10 where only **20 samples per class** are used for training the shadow models. SVHN is not considered here since the shadow models trained on such few samples will have less than 20% test accuracy (i.e. close to random guess). In the table below, we show that CBD can achieve similar detection accuracies and certification results as in Table 1 of the paper if we further increase $\\beta$ to 0.8.\n||GTSRB||||CIFAR10||||\n|-|-|-|-|-|-|-|-|-|\n||benign|BadNet|CB|Blend|benign|BadNet|CB|Blend|\n|CBD0.2|0|15(0)|80(80)|50(5)|0|45(0)|95(90)|50(40)|\n|CBD0.4|0|30(5)|90(80)|65(5)|5|60(15)|100(95)|55(40)|\n|CBD0.8|0|90(5)|95(85)|90(25)|30|90(40)|100(100)|75(40)|\n___\nWe hope our responses above have well-addressed your concerns. We are happy to answer any further questions you may have."}, {"review_id": "d9Ya3jt8qg", "reviewer": "Reviewer_fRFm", "summary": "The authors propose a new method for whether machine learning detecting models have been trained with a backdoor trigger, with the following interesting property: if the trigger has sufficiently small L_2 norm, *AND* the trigger is sufficiently robust to Gaussian noise (i.e., the model will likely return the trigger class even if Gaussian noise has been applied after applying the trigger), then the method is guaranteed to detect that the model has been trained with the trigger.\n\nHowever, this guarantee alone is only uni-directional: it does not control the false *positive* rate, and  relies on setting a threshold for detection (which in turn determines the meaning of the \"sufficiently\"'s above). In order to set this threshold, the authors propose a calibration scheme using proxy models trained on a small set of benign samples, and derive p-values using order statistics in order to set the threshold. The authors argue (and empirically verify) that because the proxy models are trained on _less_ data, they will have _more_ variance in the test statistic than a distribution of fully-trained models, and therefore the threshold will be conservative, limiting the false positive rate.\n\nEmpirical results on a variety of datasets show improvements over existing detection methods.\n", "questions": "- Could the conformal prediction results be applied to other detection frameworks (K-Arm and MNTD)?\n", "limitations": "Limitations are well-addressed, and this is a purely defensive method, so no clear negative impact.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- I found this to be a very clever method, using randomized-smoothing-like bounds in a novel yet practical way. \n- The presentation was easy to follow, and gave an intuitive understanding of what the method is and how its guarantees come about.\n- Empirical results are good, comparing to multiple prior works on multiple datasets.", "weaknesses": "- The one-sidedness of the certificate makes it less strong of a result than other methods (i.e., for evasion attacks) which are called \"certificates.\" Although the calibration result (Theorem 2) mitigates this somewhat, Theorem 2 still relies on the *empirical* observation that the calibration models have a higher variance in LDP than benign models, and so is not quite air-tight. However, these limitations are well-explained.\n\n- For the methods CBD_sup K-Arm and MNTD, it would be nice to see ROC curves/AUC comparison, rather than just fixing FPR at 5%\n\n\nMinor issues\n- The expectation in the definition of LDP in Equation (1) maybe should be deleted: it seems like the LDP is in practice calculated using only 1 set of samples x_1,...,x_k, and moreover Theorem 1 is defined in terms of the LDP on _those specific samples_. Maybe LDP is just a stochastic quantity?\n- The notation in lines 193 vs line 171 is confusing (capital vs lower-case S); is this a typo?\n- Section 5.1.3 doesn't seem very useful/is perhaps misleading, and can probably be moved to the appendix: in this test, the calibration and benign samples are drawn from exactly the same distribution, which is not the case in real life (where the calibration set would be trained on less data). Thus the results are just a statistical inevitability, and perhaps not that important to show. (However, in Section 5.3, Figure 4, the empirical fact that the calibration distributions dominate the benign distributions is demonstrated)\n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer fRFm\n\nThank you for your time and effort in reviewing our paper, and your positive comments on the novelty and the presentation of our work. We are especially encouraged by your appreciation of our certification approach as reflected in your accurate summary of our work. In the following, we address each of your comments in detail.\n___\n**Q1 :** Empirical observation related to the assumption used by Theorem 2\n\n**A1 :** Thank you for your comment! As you have pointed out, our probabilistic upper bound on the false positive rate in Theorem 2 does require an assumption about the calibration distribution, which is based on the empirical observation of LDP. Also, as you have mentioned, we have made a lot of efforts in the validation and explanation of this assumption, e.g. in the middle of Figure 4 and in Appendix B.\n\nIn this work, we aim to develop a non-trivial certification for backdoor detection with practical usage. And one of the hardest problems for backdoored model detection (even for purely empirical methods) is to set a detection threshold in practice. This is the reason why we endeavored in the analysis of the calibration scheme.\n\n\n**Q2 :** AUC comparison\n\n**A2 :** Thanks for your constructive suggestion. In the table below, we compare our CBD with K-Arm and MNTD in terms of the area under the ROC curves. Our certified CBD achieves AUCs comparable to the uncertified K-Arm on GTSRB and CIFAR-10, and a much larger AUC than K-Arm on SVHN. MNTD achieves a very high AUC on CIFAR-10, but fails for GTSRB and SVHN. In particular, MNTD exhibits an “opposite” behavior on GTSRB, which yields a very small AUC far less than 0.5 – backdoored models tend to have lower scores than benign models in this case.\n\n\n||GTSRB|SVHN|CIFAR-10|\n|-|-|-|-|\n| MNTD   | 0.11   | 0.49    | 0.97 |\n| K-Arm  | 1.0    | 0.79    | 0.91 |\n| CBD    | 0.98   | 0.97    | 0.89 |\n\nThe main purpose for fixing the FPR of K-Arm and MNTD in our paper is to compare them with NC and our CBD both adopting a 0.05 significance level. We agree that the AUC comparison is very informative and we will add the AUC results in the table above (with the ROC curves) to our revision. Thanks again for your suggestion.\n\n**Q3 :** Expectation in the definition of LDP\n\n**A3 :** Yes, LDP is computed on one set of samples $x_1, …, x_k$ in practice and computation on more samples will not change the detection performance much. And you are right that our Theorem 1 considers the actually computed LDPs in the practical detection procedure. So it is better to remove the expectation in Equation (1). Thanks for pointing this out.\n\n**Q4 :** The capital S and the lower-case S\n\n**A4 :** Thanks for pointing this out. In lines 193-194 in our Theorem 2, we considered a random calibration set where the randomness comes from both the model initialization and the data sampling for computing the LDPs. Sorry that we used the same notation in Theorem 2 to represent the calibration set as in line 171 (for the actual calibration set computed in the practical detection procedure). We will change the notation properly in our revision.\n\n**Q5 :** Moving Section 5.1.3 to the appendix\n\n**A5 :** Thanks for your suggestion. We agree that Section 5.1.3 should be moved to the appendix. We will leave the space for the AUC comparison you suggested.\n\n**Q6 :** Applying conformal prediction to K-Arm and MNTD\n\n**A6 :** Thanks for your question. This is a very insightful point since K-Arm and MNTD also need to determine a detection threshold in practice. Theoretically, the conformal prediction results can be applied to K-Arm. But in practice, we will need to run K-Arm on each shadow model to get a score, which will take 382s, 247s, and 240s per model on GTSRB, SVHN, and CIFAR-10, respectively (compared with 8s, 4s, 7s for our CBD).\n\nFor MNTD, a feature vector is extracted from each shadow model, which cannot be directly used to distinguish backdoored models from benign ones like our LDP statistic (where a model with a large LDP is likely backdoored). In fact, the authors of MNTD have investigated the possibility of “one-class” training on features extracted from the benign models only, which turned out to be not very effective (the 2nd paragraph on page 2 of their paper). Thus, MNTD and K-Arm may not benefit from our conformal prediction results in practice.\n\n___\nThank you again for your time and constructive suggestions. We are happy to answer any follow-up questions you may have."}, {"review_id": "KwAWOReOby", "reviewer": "Reviewer_xfbM", "summary": "The paper proposes a certified backdoor detector (CBD) based on a novel, adjustable conformal prediction scheme using a proposed statistic named local dominant probability. The proposed approach claims to be effective against multiple types of backdoor attacks on multiple datasets.", "questions": "Could you clarify the differences between the certification here and the certification for adversarial examples with randomized smoothing?", "limitations": "Limited Practical Applicability.\nA little bit incremental considering the randomized smoothing techniques for adversarial examples. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well written, and the theoretical proof is correct to my best knowledge. \nI also agree that it is valuable to make certification on backdoor detection. ", "weaknesses": "1. My concern is that the practical applicability of the certification could be limited. There can be a lot of different backdoor attacks and there a moderate $l_2$ bound only covers a very limited set of attacks. In practice, attackers can still design stealthy triggers (e.g., rotation, backdoor objects, natural corruption, etc.) and such that the trigger can induce a large $l_2$ norm shift. But I understand that $l_p$ bound based certification is already the best that we can do. \n\n2. The overall idea and the applied techniques are quite similar to randomized smoothing for adversarial examples. Though the paper works on backdoor set up, but essentially if $l_2$ bound is assumed, the backdoor problem and the adversarial examples problem seems to just be exactly the same. In this regard, the novelty of this work is a little bit weak and incremental.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer xfbM\n\nWe sincerely thank you for your time and effort in reviewing our paper. We also thank you for recognizing the importance of our work, the soundness of our theoretical analysis, and the quality of our presentation. In the following, we address your concerns in detail.\n___\n**Q1 :** Practical applicability of the $\\ell_p$ certification\n\n**A1 :** Thank you for your insightful comment. We agree that our certified backdoor detector, as the first of its kind, is limited to a range of backdoor attacks with relatively small trigger perturbation magnitudes in $\\ell_2$. The same limitation is also possessed by state-of-the-art backdoor defenses during training that achieves certified robustness against backdoors, such as [1]. Even for certified defenses against adversarial examples, $\\ell_p$ certifications are generally not applicable to adversarial patches, while certified defenses against adversarial patches, such as [2], are generally not applicable to $\\ell_p$ adversarial perturbations. In this sense, our certification method actually has a decent range of applications, since it covers some patch triggers (BadNet) and blended triggers, though both with relatively small actual perturbation magnitudes in $\\ell_2$, as shown by our results (in the parenthesis) in **Table 1**.\n\nWe appreciate your understanding of the difficulties in developing certified defenses. Our future works will be devoted to improving the certification bound to cover more trigger types with larger $\\ell_2$ norms, such as the rotational trigger, the backdoor object, and the natural corruption, as you mentioned.\n\n[1] Weber et al, RAB: Provable robustness against backdoor attacks, IEEE S&P 2023.\n\n[2] Xiang et al, PatchCleanser: Certifiably robust defense against adversarial patches for any image classifier, USENIX 2022. \n\n**Q2 :** Comparison with the certification for adversarial examples using randomized smoothing\n\n**A2 :** Thanks for your question. Our certification method for backdoored model detection is indeed inspired by the certification for adversarial examples using randomized smoothing due to its general independence of the model architecture. Such independence is important for post-training backdoor detection since a post-training defender has no control of the training process, especially the choice of the model architecture.\n\nHowever, the certification for backdoor detection is fundamentally different from the certification for adversarial examples from the following *five* aspects:\n* The strength and the stealthiness of an adversarial example are both determined by the adversarial perturbation size. However, for a successful backdoor attack (failed attacks are not supposed to be detected or certified), the attack strength is determined by the robustness of the learned trigger, while the stealthiness is determined by the trigger perturbation magnitude. Accordingly, for adversarial examples, a **1-D interval** specified by the certified radius is derived, while for our CBD, we derive a **2-D certified region** jointly specified by the trigger robustness and its perturbation magnitude (**lines 225-227**).\n* Certification for adversarial examples by randomized smoothing investigates the decision region near a given **input**. Differently, our certification method focuses on the **model** behavior instead, since we are detecting backdoored models. Such model behavior is quantified by our proposed LDP statistic computed on a set of samples from all classes (**Definition 3.3**) -- this is one of the main contributions of our paper, which is clearly different from existing backdoor detectors or certified defenses against adversarial examples.\n* Certification for adversarial examples is **uni-directional**, which provides guarantees on desired model predictions. By contrast, our certification for backdoored model detection is **bi-directional**. We not only provide guarantees on the detection of backdoored models but also control the false detection rate on benign models. Otherwise, one can easily design a backdoor detector that always triggers an alarm, which provides detection guarantees to all backdoor attacks but is useless in practice (**lines 190-192**).\n* For both adversarial examples and backdoor attacks, certified *robustness* and certified *detection* have different adversarial constraints -- they cover the two ends of the attack strength, respectively. For adversarial examples, existing certifications are all robustness guarantees that cover **weak** adversarial attacks with small perturbation magnitudes. For backdoor attacks, existing certified defenses provide robustness guarantees on the training-time failure of trigger injection into the model and/or test-time failure of trigger recognition – both failures require the attack to be sufficiently weak. Our CBD, however, focuses on certified backdoor detection, which addresses **strong** backdoor attacks with robust triggers (**Remark (2), line 189**).\n* A strong certified robustness against adversarial examples (and also backdoor attacks) is usually achieved by robust training, which requires the *defender* to have full access to the **training** process. However, our certified backdoor detector is deployed **post-training**, which allows the *attacker* to have full control of the training process (**lines 78-81**).\n\nThanks again for your question. We will elaborate more on the differences above in our revision.\n___\nThank you again for your insightful comments! Please let us know any follow-up questions you may have."}, {"review_id": "zfFxWjskG9", "reviewer": "Reviewer_XxVd", "summary": "The paper presents a certified backdoor detector for backdoor poisoning attacks based on local dominant probability. Certified approaches for backdoor poisoning attacks have been studied recently. These approaches usually have low certified radii on large datasets. This paper goes in another direction by certifying whether the victim model has learned a backdoor attack. The paper can achieve high certified true-positive rates on large datasets because the certified backdoor detection problem is easier than the certified classification under the presence of the backdoored training data.\n\nThe key assumption of this paper is that backdoor attacks have high samplewise trigger robustness. Under this assumption, the victim classifier will have a high local dominant probability. The paper uses a small pre-assumed clean validation data to perform conformal prediction and derive bounds using hypothesis testing. ", "questions": "Comments:\n1. The second last paragraph, \"Class imbalance is not the reason for large LDP\". This paragraph seems irrelevant. The paper should clarify why it is important to look at class imbalance. Otherwise, the paragraph should be removed.\n2. In lines 80-81, these approaches do not allow the attackers to control the full training process, while this paper allows. I suggest the paper emphasizing more on the distinctions of attack models because the distinctions of attack models are more primal than the unavailability of training and test data.\n3. In line 97, clarify what is \"domain\". A set of samples belong to the same label?\n\nQuestions:\n1. Lines 59-61, where do these numbers come from? Neither Figure 2 nor Table 1.", "limitations": "The paper addressed the limitations. For example, the paper has the assumption that backdoor attacks have high sample-wise trigger robustness. At the end of section 5, the paper shows that for the attacks with low sample-wise trigger robustness, one can add noise to the test examples and empirically defense these attacks. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper achieves high empirical and high certified true positive rates on different datasets. \n2. It is certifiable.\n3. The paper also comes a certified bound of false positive rate under mild assumptions. This certified false positive rate is not provided by other certified backdoor defenses using randomized smoothing. ", "weaknesses": "1. The paper has the assumption of a small clean validation set. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer XxVd\n\nWe sincerely thank you for your time and effort in reviewing our paper and your positive comments. As you mentioned, we investigate certified backdoor defense in a different direction from existing ones by certifying whether the victim model has learned the backdoor. We expect our certified backdoor detection approach, as the first of its kind, to inspire future works that can certifiably detect weaker and less robust backdoor attacks. In the following, we address each of your comments in detail.\n\n_______________________________________\n\n**Q1 :** Assumption of a clean validation set\n\n**A1 :** Thanks for your comment. This is a standard assumption made by most post-training backdoor defenses, though we acknowledge that [1] and [2] perform backdoor detection on simulated data instead. In practice, the defender may collect unlabeled clean data for detection since the backdoored model will provide correct label predictions for these data. We will add more discussion regarding this assumption in our revision.\n\n[1] Chen et al, Deepinspect: A black-box trojan detection and mitigation framework for deep neural networks, 2019.\n\n[2] Dong et al, Black-box detection of backdoor attacks with limited information and data, 2021\n\n**Q2 :** About class imbalance and large LDP\n\n**A2 :** Thanks for pointing this out. As we have claimed in the remarks in **line 138**, the strong robustness of a trigger (which is the basis of a large LDP) is usually achieved by “embedding the trigger in a large variety of samples during training”. However, given that the datasets used by our experiments are generally balanced before the backdoor poisoning, the readers may reasonably hypothesize that the large LDP is also related to the class imbalance caused by poisoning. If this hypothesis is true, classifiers trained on clean but imbalanced data will easily trigger a false alarm. Thus, we presented this paragraph to show that LDP will not be affected by class imbalance in general. In other words, our method indeed detects backdoor attacks, but not the class imbalance in the training data.\n\nWe agree that more clarification (e.g. the reasoning above) should be added, and we may move this paragraph to the appendix, depending on the space after revision.\n\n**Q3 :** About the attack model\n\n**A3 :** Thanks for this constructive suggestion! You are right that allowing the attackers to control the full training process is a major distinction and also an advantage of our method compared with the methods mentioned near **lines 80-81**. We will elaborate more on the attack model in our revision.\n\n**Q4 :** About “domain” in line 97\n\n**A4 :** Thanks for pointing this out! The word “domain” refers to the classification domain with a specific sample and label distribution for the model to be inspected. We will explain it carefully in our revision.\n\n**Q5 :** The numbers in lines 59-61\n\n**A5 :** Thanks for raising this issue. The numbers are from **Figure 2** on **page 7**, with the verbal descriptions in **lines 270-272** – sorry that we only included the certified true positive rates but omitted the empirical true positive rates. All these numbers will be added to the caption of **Figure 2** in our revision.\n\n_______________________________________\nThanks again for your insightful comments, and please let us know any further questions you may have."}]

Author rebuttal:
# Summary

We sincerely thank the reviewers for their constructive feedback and suggestions. We are glad that the reviewers found our paper novel and effective. Our responses are summarized as follows:

* Experiments added as suggested by the reviewers:

1. We showed the performance of our CBD with much fewer shadow models.
2. We showed the performance of our CBD with much fewer samples used for training the shadow models.
3. We compared our CBD with K-Arm and MNTD in terms of the area under the ROC curves.

* Clarification and revision following the comments of reviewers:

1. We discussed the actual detection overhead of our CBD (and the other methods we compared with) for practical detection procedures.
2. We discussed the detection and certification capability of our method in practice against backdoor attacks with large perturbation magnitude in $\ell_2$.
3. We discussed the actual data size required by our CBD (and the other methods we compared with) for practical detection procedures.
4. We showed that the results of Neural Cleanse (NC) in our paper are consistent with prior works.
5. We explained why our method is certified and made it more clear.
6. We justified the importance of certification in backdoor detection.
7. We explained the assumption required by Theorem 4.2.
8. We discussed the possibility of applying our conformal prediction results to other detection frameworks.
9. We listed five fundamental differences between the certification in this paper and the certification for adversarial examples using randomized smoothing.
10. We explained the assumption of the clean dataset for detection.
11. We explained why it is meaningful to investigate the class-imbalance scenarios.
12. We will move Section 5.1.3 to the appendix as suggested by reviewer fRFm.
13. We will make an editorial pass to address the notation issues pointed out by reviewer fRFm.
14. We will add more discussion regarding the attack model as suggested by reviewer XxVd.
15. We will elaborate on the concepts and the numbers pointed out by reviewer XxVd.

We hope all of your concerns have been well-addressed in our responses. We are more than willing to address additional questions and conduct further experiments should the reviewers deem it necessary.


Meta-review: This paper proposes a certified backdoor detector which not only predicts whether a model has been attacked, but also provides conditions of guaranteed detection, and an upperbound on false positive rates. The method and the theoretical result, although requiring a validation set, are considered novel and sound by reviewers. Concerns regarding evaluation, baselines, and experimental settings were raised, but were well addressed during rebuttal.
Decision: Accept (poster)