Demystifying Poisoning Backdoor Attacks from a Statistical Perspective
Authors: Ganghua Wang
Xun Xian
Ashish Kundu
Jayanth Srinivasa
Xuan Bi
Mingyi Hong
Jie Ding
Venue: ICLR 2024 poster (2024)
Keywords: backdoor attack
machine learning safety
asymptotic
statistical risk
Primary area: societal considerations including fairness, safety, privacy
TL;DR: We provide both finite-sample and asymptotic statistical analysis for theoretically understanding the backdoor attack.

Abstract: Backdoor attacks pose a significant security risk to machine learning applications due to their stealthy nature and potentially serious consequences. Such attacks involve embedding triggers within a learning model with the intention of causing malicious behavior when an active trigger is present while maintaining regular functionality without it. This paper derives a fundamental understanding of backdoor attacks that applies to both discriminative and generative models, including diffusion models and large language models. We evaluate the effectiveness of any backdoor attack incorporating a constant trigger, by establishing tight lower and upper boundaries for the performance of the compromised model on both clean and backdoor test data. The developed theory answers a series of fundamental but previously underexplored problems, including (1) what are the determining factors for a backdoor attack's success, (2) what is the direction of the most effective backdoor attack, and (3) when will a human-imperceptible trigger succeed. We demonstrate the theory by conducting experiments using benchmark datasets and state-of-the-art backdoor attack scenarios. Our code is available \href{https://github.com/KeyWgh/DemystifyBackdoor}{here}.

Published as a conference paper at ICLR 2024
DEMYSTIFYING POISONING BACKDOOR ATTACKS FROM A STATISTICAL PERSPECTIVE
Ganghua Wang"
Xun Xian"
Jayanth Srinivasa
School Statistics
Department ECE
Cisco Research jasriniveci
University of Minnesota wang901 96 umn edu
University of Minnesota
xi xian004 4 umn edd
Ashish Kundu
Xuan Bi
Mingyi Hong
Cisco Research
Carlson School of Management University of Minnesota xb @umn edu
Department ECE
ashkunduf wwc.euuciiccooooo com
University of Minnesota
mhong@umn edu
Jie Ding
School of Statistics University of Minnesota dingi0umm edu
ABSTRACT
Backdoor attacks pose significant security risk to machine learning applications due to their stealthy nature and potentially serious consequences. Such attacks involve embedding triggers within a learning model with the intention of causing malicious behavior when active trigger is present while maintaining regular functionality without it. This paper derives a fundamental understanding of back- door attacks that applies both discriminative and generative models, including diffusion models and large language models. We evaluate the effectiveness of any backdoor attack incorporating a constant trigger, by establishing tight lower and upper boundaries for the performance of the compromised model on both clean and backdoor test data. The developed theory answers a series of fundamental but previously underexplored problems, including (1) what are the determining factors for backdoor attack's 's success, (2) what is the direction of the most effective backdoor attack, and (3) when will demonstrate the theory by conducting experiments using benchmark datasets and sate-oofthhear backdoor attack scenarios. Our code is available here
trigger succeed. We
INTRODUCTION
Machine learning is widely utilized in real- world applications such autonomous driving and medical diagnosis (Grigorescu et al., 2020 Oh et al.) 2020), underscoring the necessity for comprehending and guaranteeing its safety. One of the most pressing security concerns is the backdoor attack, which
characterized by its stealthiness and potential for disastrous outcomes (Li et al. 2020) Goldblum al.) (2022). Broadly speaking. backdoor attack is designed to embed triggers into learning model to achieve dual objectives: (I) prompt the compromised model exhibit malicious behavior when a specific attacker-definet trigger is present, and (2) maintain normal functionality in the absence of the trigger, rendering the attack difficult to detect.
Data poisoning is common tactic used in backdoor attacks (Gu al. 2017 Chen et al.
2017 Liu
et al. al.
2017] Turner et al.] 2018 Barni et al. 2019 ZZhoo et al. 2020;
Nguyen & Tran 2020: Doan
2021b) Nguyen & Tran 2021 Tang al. 202 [i al.] 2021| Bagdasaryan et al. 2020 Souri et al.
2022 Qi et al. 2023), demonstrated in Figure To carry out a poisoning backdoor attack, the
attacker creates few backdoor data inputs with specific trigger (c.g., patch (Gu et 2017) or
watermark (Chen et al. 2017 and target labels. These backdoor data inputs are then added to the
"Equally contributed

---

Published as a conference paper at ICLR 2024
Clean
(a] BadNets
(b) Blended
(c) WaNet
Figure 1: Example of popular poisoning attacks the GTSRB Dataset (Stalkkamp et al. 2012 A clean image and (a) BadNets (Gu et al.
2017): square patch (backdoor trigger) added at the lower-right corner of the original image, (h) Blended (Chen al. 2017): hello kitty (backdoor trigger) embedded into the image, and (c) WaNet (gguyen & Tran 2021): human-imperceptibble perturbation (backdoor trigger). The poisoned model will predict backdoored images as '20 speed".
original "clean" dataset to create "poisoned"" dataset. A model trained on this poisoned dataset is called a "poisoned model" because model with sufficient expressiveness can learn the supervised relationships in both the clean and backdoor data, leading to abnormal behavior the backdoor data.
Creating effective backdoor triggers is an essential aspect of research on poisoning backdoor at- tacks. Prior studies have shown that using square patches (Gu et al. 2017) or other image sets as triggers (Chen et al. 2017) can result in a poisoned model with almost perfect accuracy on both clean and backdoor images image classification tasks. However, these backdoor triggers are perceptible to the human eye, and they can be detected through human inspections. Consequently, recent rescarch has focused on developing dynamic and human-imin caaaaniimmereeebbbe backdoor triggers (Nguyen & Tran 2020; [Bagdasaryan & Shmatikov [021 Doan et al. 202 Li et al. (202)) through techniques such as image wrapping (Nguyen Tran 2021) and generative modeling techniques such as VAE (Li et al. 20211. This current line of work aims to improve the efficacy of backdoor attacks and make them harder to detect. While these poisoning backdoor attacks have demonstrated empirical success, fundamental questions like how to choose effective backdoor trigger remain unresolved.
1.1 MAIN CONTRIBUTIONS
In this work, we aim to deepen the understanding of the goodness of poisoning backdoor attacks. Specifically, we define an attack as successful if the poisoned model's prediction risk matches that of the clean model on both clean and backdoor data. Our main contributions are summarized below.
From theoretical perspective, we characterize the performance of backdoor attack by studying the statistical risk of the poisoned model, which is fundamental to understanding the influence of such attacks. In Section 3 we provide finite-sample lower and upper bounds for both clean- and backdoor- data prediction performance. In Section 4 we apply these finite-sample results to the asymptotic regime to obtain tight bounds on the risk convergence rate. We further investigate generative setups in Section 5 and derive similar results. This analysis, to best knowledge, gives the first theoretical insights for understanding backdoor attacks in generative models.
From an applied perspective, apply the developed theory to provide insights into sequence of questions that are of interest to those studying backdoor attacks:
(Q1) What are the factors determining backdoor attack's 's effect?
We identify three key factors that collectively determine the prediction risk of the poisoned model:
the ratio of poisoned data, the direction and magnitude (as measured under the (2-norm) of the trigger, and the clean data distribution, as illustrated in Figure 2
(Q2) What is the optimal choice of trigger with a given magnitude? We show the optimal trigger direction is where the clean data density decays the most.
(Q3) What is the minimum required magnitude of the trigger for successful attack?
We find that the minimum required magnitude depends on the clean data distribution. In particular, when the clean data distribution degenerates, meaning that the support of distribution falls in subspace, the minimum magnitude can be arbitrarily small.
1.2 RELATED WORK
Backdoor attacks. Backdoor attacks manipulate the outputs of deep neural networks (DNNs) on specific inputs while leaving normal inputs unaffected. These attacks can be conducted in three main ways: (1) by poisoning the training data only, (2) by poisoning the training data and interfering with the training process, and (3) by directly modifying the models without poisoning the training data.
2

---

Published as a conference paper at ICLR 2024
Accuracy
Backdoor
Backdoor
02
0.3
0.4
0.5
0.6
0.7
08
Paisoning Ratio
[a] data density
[b) Backdoor triggers different directions
[c] Clean- and backdoor-date accuracy
under different paisoning ratio
Figure 2: Illustration three factors jointly determining the effectiveness of backdoor attack: clean data distribution, backdoor trigger, and poisoning ratio.
Most backdoor attacks
(Gu et al. 2017 Chen al.
2017
Liu al.
2017
Turner al.
2018 Barni
et al.
2019 Zhao et al. 2020 Nguyen & Tran 2020
Doan et al. 202 b N Nguyen & Tran 2021 Tang
al.
2021
Li et al.] 2021 Bagdasaryan et al.
2020
Souri al., 2022 Qi al. 2023) belong the
first two approaches, namely poisoning the training data and/or interfering with the training process.
These attacks primarily focus on designing effective backdoor triggers. For example, WaNet (Nguyen
& Tran
backdoor images, while ISSBA (Li et al. (20TT) produces sample-specifee invisible additive noises as backdoor triggers by encoding attacker-specifies string into benign images using encoder-decoder network. Another line research aims to minimize visibility backdoor triggers in the latent space the backdoored models (Doan al. 202 lb Tang al., 2021: Qi al. 2023). These methods strive to reduce the separation between clean and backdoor data in the latent space. For example, the approach in (Qi et al. 2023) utilizes asymmetric triggers during the test and inference stages minimize the distance between clean and backdoor data. Additionally, besides incorporating backdoor triggers into the training data, the method introduced in (Doan al. (0221) also adjusts the training objective by adding a term that regularizes the distance between the latent representations of clean and backdoor data. In this work, for theoretical studies, we specifically consider the scenario where the attacker is only allowed to modify the training data.
2021) employs smooth warping field to generate suman-imperceppine
Backdoor defense. Backdoor defense can be broadly classified into two types: training stage defense and test stage defense. In training stage defense. the defender has access to the training data. This has led series of literature (Chou al. 2020,Trae
al., 2018 Chen et al. 2019 Wallace et al.. 2020 Tang et al.] [02T]] Hayase et al. 2021 Hammoudeh & Lowd 2022 Cui et al. 2222) focused on detecting and filtering out the backdoor data during the training process. Various methods have been proposed, such as clustering techniques (Chen et al. (019) and robust statistics (Tran al. 201 8), to identify and remove the poisoned training data, enabling the training of clean models without backdoors. Additionally, some approaches involve augmenting the training data to mitigate the impact of backdoor data on the trained model. On the other hand, the test stage backdoor defense (Gao et al., 2 al., 2019 Xian et al., 2023a) focuses on the scenario where the defender is given trained, possibly backdoored model without access to the training data. In such cases, the defender is typically assumed to have access
small set of clean data that have the same distribution as the clean data, and the defender will use the clean data set and the trained model to reconstruct/revenss the trigger (Wang et al., 2019), prune some neurons related to backdoor data (Liu et al. 2018). and
detect if future input is clean or backdoor backdoor-triggered triggered with provable guarantees (Xian et al. 2023a).
Research works that aim to understand backdoor learning. Manoj & Blum 202 quantifies model's 's capacity to memorize backdoor data using concept similar to VC-dimension Vapnik et al. 1994) and shows that overparameterized linear model models have higher memorization capacity and are more susceptible to attacks. Xian et al.] (2023b) proposes the "adaptivity hypothesis' to explain the success backdoor attack. In particular, the hypothesis states that a good backdoor attack should not change the predicted value too much before and after the backdoor attack. Based on that, the work suggests a good attack should have backdoor data distribution far away from clean data in probability sense. Gao al. (2023) and Xia et al. (2022) propose selecting data instances that significantly influence the formation of the decision boundary in the learned model, while Guo et al.) (2023) suggest selecting data points that lie in close proximity to the decision boundary of the clean
3

---

Published as a conference paper at ICLR 2024
Table 1: Summary of commonly used notations
Symbol
Meaning
a
Sample size of the training data
p
Proportion of backdoor data in the training data
The perturbation trigger of the backdoor attack
nel
Joint distribution of clean data, backdoor data, and poisoned data
Le fa 12a pdl fra
Regression function of clean data, backdoor data, and poisoned data
Learned model based on the clean data and poisoned data
(f), (F) (J)
Statistical risk of model on clean, backdoor, and poisoned input
model. While those studies provide valuable insights into the success of backdoor attacks, they do not quantify how effective a given backdoor attack is.
2 PRELIMINARY
Notations. We will use F. E. and 1 to denote probability, expectation, and an indicator function, respectively. For two sequences of real numbers on and bn. On X bn means lim supn-too un/bb, S C for some constant C, an Z b means 6n S On, an x b, means bn S az and on S b,, hold simul- taneously, and an o(b,,) means lim,-oc an/b, O. For vector (Ei= (////))))))))) / denote its nn-oo.. For two vectors w and u, cos(w, u) := w" "0l"u((luu Ila (allu|/a))))))))){ is the cosine of their angle. Frequently used symbols are collected in Table
[wi...., WW]. let ||w]||
Learning scenario. We first consider a binary classification task that involves a vector of predictor variables X Iº and label Y {0, 1}, and extend to generative setup in Section 5 Here, the predictor X can also be an embedding of the original input, such as the output of the feature extraction layer of neural network. The learner aims to estimate the conditional probability fe : IP = 11 X) given observations.
Remark (From probability prediction to classifier) Once probability estimator J X [0, 1] of fcl is obtaiedd, the learner can construct a classifier g(f) = 1>1/22 That is, predicting any input X as label one if f(X) > 1/2 and as label zero otherwise. Suppose the learner wants to minimize the classification error with zero-one loss, it is known that the closer f to fel. the smaller the classification error for g(f) Devroye et al. 2013 Theorem 2.2). Additionally, the classifier g(J"", called the Bayes classifier, achieves the minimal error Gyoöfi et al. 2002).
Threat model. In this study, we consider a commonly used attack scenario where attackers can only backdoor attacks are implemented within this attack scenario, including BadNets (Gu el al. 2017), Blend (Chen et al., 2017), and Trojan (Liu et al. 2017). In particular, each data input in the clean dataset has probability p E (0, 1) to be chosen as a backdoor data, meaning that its predictor will be shifted by 17 E R' and the response will be relabelled as zero, regardless of its ground-truth class. Here, choose the target label as zero without loss of generality. We will discuss the case of clean-label backdoor attacks that do not relabel the response in Appendix.
corrupt data, but cannot tamper with the training process. Several
Definition 1 (Backdoor- Triggered Data and Model) (1) The learner wishes to train model based on clean data De = {(X,, i) = In....n.. which are IID sampled from pt, the distribution of the clean labeled data (X, Y). (2) The attacker will provide the learner with backdoored data in the form of (X =X 17, =0), 0). whose distribution is denoted by pdd where X follows the clean data distribution. (3) The learner will actually receive a poisoned dataset with the distribution poi : -p) + pp.hll As such, a poisoned dataset can be represented as D = (Xx,, Y.),
1. 1.....n). where X, = X, 11+ 2:=1, Y, = -11 z,=0, and 7 's are independent Bernoulli variables with P(Z, 1) P. (4) The learner thus trains poisoned model frol on the poisoned datasel Deoi
nn.
We can verify that (x,, Y,''s are IID sampled from puPoi Additionally, (X,, Y:)'s are IID sampled from S conditional on Z, = O, while IID sampled from ب conditional on Z, = 1. In other words, when Z, = (with probability p). the input X, will be backdoor perturbed and its associated label will be the backdoor-targedd the attacker can generate the backdoor data by choosing P and 17, but cannot directly influence the learning model. We refer readers to (Li et al.] (2020) for other types of attack scenarios where attackers can interfere with the training process, such modifying the loss functions and the model parameters.
label zero. Notably, we assumed the standard backdoor scenario where
4

---

Published as a conference paper at ICLR 2024
Dual-Goal of the attacker. A successful backdoor attack has two goals. First, the accuracy of the poisoned model frii in predicting a typical clean data input remains as high as the clean model fei This makes an attack challenging to identify. Second, the poisoned model can be accurately "triggered" in the sense that it can produce consistently high accuracy in classifying a gackdoor-injecter data input as the targeted label. We quantitatively formulate the above goals as follows.
Prediction performance of fiei clean data. We first introduce a prediction loss E fat) that measures the discrepancy between the poisoned model and the conditional probability of clean data distribution. In this work, we use the expected loss, that is, (((ett, = Ex {((fri(X) (X), (x))), where y is the distribution of clean data input X, and ((.--)
[0, 1|x1|x00000 1] + + is general loss function. Then, we can evaluate the goodness of freu on clean data by the average prediction loss, also known as the statistical risk, as ( == Exe { (e0 }t)).
where the expectation is taken over the training data.
Prediction performance of foot on backdoor data. In this case, we need a different prediction loss ( { where 1 is the conditional probability under udd and equals zero under our setup. Analogous the previous case, we have god (froi, sbl) == E2 Ex {e(Fpot(X) ("" (X)) and the statistical risk of frei on backdoor data is: rbd (froi) == E { (dd (froi, f where p is the distribution of a backdoor data input X.
Definition 2 (Successful Backdoor Attack) Given distribution class DD backdoor attack is said to be successful if the following holds: max{re) (omi), , rbl (frm)) S (fo)). Therefore, we are interested in r (froi) and r (fro)), which will be studied in the following sections.
3 FINITE- SAMPLE ANALYSIS OF THE BACKDOOR ATTACK
This section establishes bounds for the statistical risks of a poisoned model on clean and backdoor data inputs for a finite sample size The results imply key elements for a successful backdoor attack. We begin by introducing a set of assumptions and definitions, followed by the main results.
Definition 3 For
0, L, let v;(-) be the density of X given Y i for clean data, and m, (x Y = i) is the conditional mean. Let h (r) == Fv, (I(X- mm)"') 2 r(]n)1)) be the tail prob- ability of X along the direction of y conditional on Y = i, and 9. (r) == min (=::l==nllasr) Pi(m; xx) be the minimum density of the points in r-radius ball deviating from the center by n.
Definition 4 Let p be the distribution of X for poisoned data, we define
fool (x) == -x (Y |x= = =x), rh (Frnt) == -Eppy [ x - Frmdl
(X), ftol (X))]]
Assumption (Predictor distribution) For any 1j E Rdd and 0 < <c1 < C2. we have us (m; ciT) 2
v2(m, <27)) i 0, 1.
Assumption 2 (Loss function) The loss function E: [0. 1] x [0. + B is (C, continu-
ous for 0 < a S and C> > That is, for all x. y, = E [0, 1). we have
1(xx, v) [1x, =)] S Cly z|"; (((x,,)
((2,
Also, there exist constants 3 2 and Cg > 0 such that Cg|l- - yرر S l(x, y) for any x. E 10.
Remark 2 (Discussions on the technical assumptions) Assumption 7 says that the conditional den- sity of X is monotonously decreasing in any direction. Common distribution classes such as Gaussian, Exponential, and student-t satisfy this condition. Also, we only need it to be fulfilled when C1, C2 are large enough. Many common loss functions satisfy Assumption 2 For example, min(y, 1},
max{"y, 1} for E(x,y) = |r yl" 7 > O, and a 1, 3 for Kull- back-Leible Leibler divergence when arguments are bounded away from O and 1. The second condition in Assumption ensures that the loss is non-degenerate, which is only required to derive lower bounds.
Theorem (Finite-sample upper bound) Under Assumptions 4 cos(1), mi mo)llm - -mollz we have
and
when ||/||/ 2
C
17 (1(l11l)/44 }1"
yeld (Prot) < 1-
poi (fro))
+
max -=0,1
p)
5

---

Published as a conference paper at ICLR 2024
Fa (Feot) S 1100 (Poot) + p
11 (1((l1ll2/44)
max 1=0,1
Theorem 2 (Finite-sample lower bound) Suppose
||7/12 > 2c > 0, where is universal constant.
Under Assumptions (ariioosssannd [and we have
(Pr) Z P Ci ([ -2 (Pmnt))
in (Pam) 2 (1- (o-
(Pant) 10/0
where C1, C2 are positive constants that only depend the clean data distribution and
Determining factors for a backdoor attack's 's success. Through the risk bounds provided by Theorems | [and 2 we can identify factors contributing to the poisoned model's performance and know how they influence the performance. Clearly, the ratio of poisoned data will significantly change both upper and lower bounds. Next, we assume that p is fixed and identify other crucial factors. Note that each bound involves two quantities: the risk of fee on poisoned data r (feet) and a bias terms of h? or d. brought by the backdoor data. By our definition, r.a (frei) means the ordinary statistical risk in predicting a data input that follows μ which is the poisoned data. For many classical learning algorithms,, this statistical risk vanishes as the sample size goes to infinity. In contrast, the bias term depends on 1) only and will not change when 1/ is fixed. Therefore, the prediction risk of the poisoned model is determined by the bias term when the sample size is sufficiently large. The bias term is jointly determined by two factors, the direction and magnitude (in f2-norm) of 1, and the clean data distribution. In summary, we have the following key observations: (1) A large backdoor data ratio p can damage the performance on clean data, while small can lead to unsatisfactory performance on backdoor data.
(2) A larger magnitude of 17 leads to a more successful backdoor attack. This is because Assumption || ensures that h² and 9" are monotonously decreasing functions, thus both risks will decrease as the magnitude of 7) increases. Intuitively, large means the backdoor data is more distant from the clean data, reducing its impact on the poisoned model and resulting in better performance.
(3) When the magnitude of r) is fixed, choosing vi along the direction that clean data density decays the fastest leads to the most successful backdoor attack. This can be seen from the fact that both the upper and lower bounds of the risk are smallest when 1j is chosen to minimize the density and tail probability the corresponding direction.
The above results provide insights into the impact of a backdoor attack on the model performance. Though the exact value of r:t ( (ffee) is often unknown, its rate can often be determined. Thus, we can derive more precise results in the asymptotic regime, which will be discussed in the next section.
4 ASYMPTOTIC PERSPECTIVE AND IMPLICATIONS
This section considers the asymptotic performance of a poisoned model, namely the convergence rate of its prediction risk. The statistical risks for many common algorithms and data distributions are well understood. Thus, Theorem I serves as useful tool to study when a backdoor attack can be successful in the sense of Definition g questions raised in Section T In particular, we study the optimal direction of trigger and the minimum required magnitude of a trigger for a successful attack.
Next, we show how to utilize Theorem to address the
Assumption (Ordinary convergence rate) We assume that rel (Fe) = poo (Foot).
Theorem 3 (Non-degenerate clean data distribution) Suppose that ral (fel) = xn= for positive
constant 7, and ex(-), = 0, 1 follows a multivariate Gaussian distribution with variance E. The eigenvalues and corresponding eigenvectors of y are denoted as 01 2 2 op > 0 and { 1...., P), respectively. Under Assumption 3 for any fixed p (0, 1). we have
1. Among all possible backdoor triggers 1, satisfying ||æl|2 8, the attacker should choose 1 = 8. Up to minimize both the risks rdd (Tpot) and ral (fPoo);
2. With the direction of 1) same as up there exist two constants 0 < C1 < C2 such that (i) the backdoor attack is successful when llmll2 2 o2 In n and (ii) the backdoor attack is unsuccessful when || S Inn.

---

Published as a conference paper at ICLR 2024
Backdoor
A
Label O
Shift
Label
Figure 3: Illustration of backdoor attacks with imperceptible perturbations: The original data lie the horizontal axis. Thus, a backdoor attack with little vertical shift is sufficient for a successful backdoor.
Theorem 4 (Degenerate clean data distribution) Suppose there exists direction u such that the support of marginal distributions v.(-), ), = 0, (see Definition 3 is a single point. Then, any backdoor attack with 17
and > 0 is successful.
Theorems 3 and show that the optimal choice of 17 along the direction with the smallest variance the direction that the clean data density decays the fastest. Those results also characterize the minimum required form of 17 for a successful attack. Specifically, for inputs that degenerate in some direction, Theorem 4 shows an arbitrarily small norm of can already qualify for successful backdoor. In contrast, Theorem [3] shows that for data inputs following a non-degenerate Gaussian distribution, the magnitude of ry has to be at least at the order of v /I)(n) to have successful backdoor attack. An slower than that will cause significant performance degradation.
Theorem 4 theoretically explains the success of hwwanhuimmaaaaaa camnan-imperceptbble backdoor attacks such as those developed in (Li et al. 2021). The condition of Theorem 4 satisfied if the data distribution has low-rank embedding in R" This is particularly common in high-dimensional data (Pless & Souvenir 2009; Diao et al. 2019 Li al. 2023). For such degenerated clean data, Theorem [ implies that poisoning backdoor attack with an arbitrarily small magnitude and certain direction of trigger can succeed. As exemplified in Figure 3 when clean data degenerate in some directions, this unused space to craft backdoor data that are well-separated from clean data. Consequently. learning models with sufficient expressiveness will perform well on both clean and backdoor data. is worth mentioning that the Gaussian assumption in Theorem 3 iss non-critical. The proof can be emulated to derive results for any other distribution satisfying Assumption [ We use only to show how to calculate the minimum required magnitude of for successful attack.
can exploit
Remark 3 (Vanishing backdoor data ratio) Theorem 3 and 4 suggest that when backdoor data ratio p is bounded away from zero, there exist successful attacks with carefully chosen triggers. However, the necessary condition p remains unclear. In particular, we are interested in when will a backdoor attack succeed with a vanishing p. We conjecture that whether a vanishing p can lead to successful attack depends on both clean data distribution and the learning algorithm used to build the model. For example, when the learner adopts k-nearest neighbors, it may depend on the relative order of ls and p. We leave the finer-grid analysis of p as future work.
Remark 4 (Discussion on the technical assumption) Recall that reui (Frul) ) is the prediction risk of the poisoned model on the poisoned data distribution. This actually equivalent to the ordinary statistical risk of clean model on clean data (Li & Dingl 2023). with μdd considered as the clean data. Moreover, since j and po often fall in the same function class, such as the Hölder class, Assumption
3 will hold almost surely (Barron & Hengariner 1998). For example, when J is Lipschitz function, the convergence rate is often at the order of n 22/(x42) for &g loss and non- parametric estimators, including k-nearest neighbors and kernel-based estimators.
5 EXTENSION TO GENERATIVE MODELS
generative model is traditionally trained mimic the joint distribution (X, Y). where X R² is the input and Y E 129 is the output. In other words, it models the conditional distribution of Y given a certain input X, denoted as fx. The loss function is now defined as (x I Efx (v). 9x ((d))))) where p(-) is given distribution over the event space of Y. The corre- sponding backdoor attack is adding trigger 1) to clean data X and pairing it with target output y' sampled from the target backdoor distribution pdd,, The other settings such as the threat model and goals are the same as in Section 2 Analogous Theorem 4 for generative models, we prove that the attack adding a trigger to the degenerate direction of the clean data distribution will be successful.
7

---

Published as a conference paper at ICLR 2024
Angle 90.0
BD
13500
190L0
Length 1.0
Length 3.0
Length m 5.0
Text cree
10"
8
10"
10"
(f
X;
Visualization of the poisoned datasets. Left: the backdoor trigger y has an no-n of three and 0 angle with m, mai Right: 7) has an fz-norm of one and a 90º angle with
Figure 5:
Figure 4: The test of the poisoned model on both clean inputs ("el") and backdoor-triggeree imputs ("bd"" under different angles (between 1) and m. mu) and fo-norms of the backdoor trigger 7). The dashed line denotes the bascline test error of the clean model on clean inputs. The vertical bar is the 95% confidence interval.
'BD O' means backdoor data with targeted label zero, and arrow repre- sents the trigger's direction.
Theorem (Generative model with degenerated distribution) Suppose there exists a direction such that the support of marginal distributions of p& is single point. Then, any backdoor attack with 1) = s and is successful.
6 EXPERIMENTAL STUDIES
6.1 SYNTHETIC DATA
We conduct a simulated data experiment to demonstrate the developed theory. Following the setting
Theorem 3 we consider two-dimensional Gaussian distributions with mn = (-3, 0), mig = (3. 0). E is diagonal matrix with Σn 3 and Σg 1/2, P., 1) 0.5, training sample size n = 100, and backdoor data ratio p = 0.2. The & - of the backdoor trigger rj is chosen from (1,3,5). 5), while the degree of angle with m² mm chosen from (0, 45, 90, 135, 180). We visualized two poisoned datasets in Figure 5) For model training and evaluation, kernel smoothing (Györfi et al.) 2002) is used the learning algorithm: for a dataset Dn {(x,, Y,), 1,..., n
f(x) = [> KA, (X; - x)) (E Yg (N; - x)), where h, E R is the bandwidth, Ki., (z) = K((X,- -z)/h,) with K(() being a Gaussian kernel. The bandwidth is chosen by the five-fold crossvaaidatiinn (Ding al. 2018). We evaluate the model performance on 1000 test inputs using the zero-one loss. In particular, three quantities are calculated: the test error of the poisoned model on clean data inputs (R ) the test error of the poisoned model on backdoor data inputs (Rbb), and test error of the clean model on clean data inputs (!P7)). All experiments are independently replicated 20 times. The results are summarized in Figure
Figure shows: (1) the increase of length leads to the decrease of both Re and 12hd (2) R2hd varies significantly for different angles, and the smallest when 77 is orthogonal to m, - mg, which is exactly the direction of the eigenvector the smallest eigenvalue of variance matrix E, (3) R is relatively stable in this experiment, though small angle, or a large cos mn mo), results in large Re Overall, the trend in the result is consistent with our developed theoretical understanding.
6.2 BACKDOOR ATTACKS IN DISCRIMINATIVE (CLASSIFICATION) MODELS
First implication: On the magnitude of the backdoor triggers In this experiment, our objective empirically validate the hypothesis that larger trigger size, measured terms of magnitude, results in a more impactful attack. We conducted BadNets (Gu et al. 2017) on the MNIST (LeCun al. 2010) and CIFAR10 (Krizhevsky et al. 2009) datasets, utilizing both LeNet (LeCun al. 2015 and ResNet (He et al.) 2016) models. In the case of MNIST, the backdoor triggers are 2 by 2 square patches, while for CIFAR- positioned at the lower-right corner of the inputs, replacing the original pixels with identical values. The pixel value represents the magnitude of the backdoor trigger and the poisoning ratio is 5%. The results summarized in Table 2 below. As the magnitude of the backdoor trigger, represented by the pixel values, increased, we observed corresponding improvement in backdoor model accuracy, in line with our theoretical predictions.
by 3 square patches are utilized. All backdoor triggers are
Second Implication: On the optimal direction(s) of backdoor triggers In this experiment, we show that attack efficacy increases the separation between backdoor and clean data distributions grows.
8

---

Published as a conference paper at ICLR 2024
Table 2: Backdoor Performance of ResNet across varying magnitudes of backdoor triggers (pixel values).
MNIST
CIFARIO
Pixel Value (0, 255)
10
15
30
10
15
30
Clean Accuracy
0.82
0.89
0.96
0.99
0.99
0.82
0.81
0.87
0.90
0.93
Backdoor Accuracy
0.72
0.91
0.97
0.97
0.99
0.51
0.62
0.80
0.87
0.99
Allack: BadNNeis
Mlack: Wellei
Allack: Adaplive Patch
Alackk: Adaplive Blend
Ralaative Change
Redooe Chanpy
Ralaliva Change
Varlance
Variance
Variance
Variance
Figure 6: In each plot, the æ-axis corresponds to the variance of each dimension of backdoor data while the y-axis represents the relative change along that dimension. This relative change is the absolute difference between clean and backdoor data at the ith dimension divided by the standard deviation of that dimension.
We tested four backdoor attacks BadNets, WaNet (Nguyen Tran 2021), Adaptive Patch (Qi et al.
2023), and Adaptive Blend [Qi et al. 2023) on the CIFAR 10 dataset using the ResNet-18 model. We visually represent the relative change between clean and backdoor data for each attack in Figure 6 calculated as the absolute difference between clean and backdoor data at the ith dimension divided by the standard deviation of the same dimension. Our results show that WaNet, Adaptive Patch, and Adaptive Blend attacks produce a more significant relative change in dimensions with low variance. This aligns with our theory, confirming the effectiveness of these methods compared to BadNets.
6.3 BACKDOOR ATTACKS IN GENERATIVE MODELS
Diffusion Models. In this experiment, we demonstrated our theory for generative models using a class-conditioned Denoising Diffusion Probabilistic Model (DDPM) (Ho al. 2020) to generate MNIST-like images. In this conditional setup, the input space represents class labels, while the output space contains generated images. In the context of the backdoor scenario, new class labeled '10' was introduced, where the target images were modified MNIST '7' images adding a square patch located in the lower-right corner. The outcomes, visually depicted in Figure [ show the backdoored model's high quality in generating '7' images with the specified square patch. Quantitatively, following (Chou al., 2023), we calculated that the mean squared error (MSH) between the generated images and their intended target images consistently registers below the critical threshold of 0.01. Furthermore, the MSE between the clean training images and the images produced by the backdoored DDPM with the original input class labels is also below 0.01, indicating the backdoor attack's 's empirical success. The above is consistent with our theoretical expectations from Theorem 5
Large Language Models. In this experiment, support our theory using Transformer net- work Vassaani et al., 2017) for a text translation task. We follow the word-level approach in (Chen) et al. 2023) to design backdoor attacks, where create backdoor inputs by inserting a trigger word "Brunson', and the target output is a predefined word in the translated language. Quantitatively, we observed an attack success rate over 0.96, calculated as the proportion of output, namely, the translated sentences, containing the trigger output given the backdoor input containing the word 'Brunson'. To measure the quality of the output sentence given the backdoor target, we observed that there is only a 0.3% decrease in the BLEU score (Papineni et al. 2002). which shows the quality of backdoored sentences. This result is well aligned with our theoretical expectations from Theorem
Training Data
Backdoored DDPM Generated
7
7
7
7
7
7
7
Original MNIST
Backdoored MNIST
Figure 7: Illustratoons of original MNIST '7' images (leftmost images), backdoored versions with square patch (middle images), and images generated from a backdoored DDPM (rightmost figures).

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENT
The work of Ganghua Wang and Jie Ding was supported in part by the Office of Naval Research under grant number N00014-21-1-2590. The work of Xun Xian, Xuan Bi, and Mingyi Hong was supported in part by sponsored research award by Cisco Research.
REFERENCES
Eugene Bagdasaryan and Vitaly Shmatikov. Blind backdoors in deep learning models. In 30th USENIX Security Symposium (USENIX Security 21), pp. 1505-1521, 2021.
Eugene Bagdasaryan, Andreas Veit, Yiqing Hua, Deborah Estrin, and Vitaly Shmatikov. How to backdoor federated learning. In International Conference on Artificial Intelligence and Statistics, pp. 2938-2948. PMLR, 2020.
Mauro Barni, Kassem Kallas, and Benedetta Tondi. A new backdoor attack in enns by training set corruption without label poisoning. In 2019 IEEE International Conference on Image Processing (ICIP), pp. 101-105. IEEE, 2019.
Andrew Barron and Nicolas Hengartner. Information theory and superefficiency. The Annals of Statistics, 26(5): 1800-1825, 1998.
Bryant Chen, Wilka Carvalho, Nathalie Baracaldo, Heiko Ludwig, Benjamin Edwards, Taesung Lee, Ian Molloy, and Biplav Srivastava. Detecting backdoor attacks deep neural networks by activation clustering. In SafeA/@AAA, sen CEUR Workshop Proceedings, volume 2301, 2019.
Lichang Chen, Minhao Cheng, and Heng Huang. Backdoor learning sequence to sequence models.
arXiv preprint arXiv:2305.cmm 02424, 2023.
Xinyun Chen, Chang Liu, Bo Li, Kimberly Lu, and Dawn Song. Targeted backdoor attacks on deep learning systems using data poisoning. arXiv preprint arXiv: 2017.
Edward Chou, Florian Tramer, and Giancarlo Pellegrino. Sentinet: Detecting localized universal attacks against deep learning systems. In 2020 IEÉE Security and Privacy Workshops (SPW), pp- 48-54. IEEE, 2020.
Sheng- Yen Chou, Pin-Ye Yu Chen, and Tsung- Yi Ho. How to backdoor diffusion models? In Proceedings of the JEEF/CVF Conference on Computer Vision and Pattern Recognition, pp. 4015 4024, 2023.
Ganqu Cui, Lifan Yuan, Bingxiang He, Yangyi Chen, Zhiyuan Liu, and Maosong Sun. A unified evalu- ation of textual backdoor learning: Frameworks and benchmarks. arXiv preprint arXiv:2206.08514 2022.
Lue Devroye, László Györfi, and Gábor Lugosi. A probabilistic theory of pattern recognition, volume 31. Springer Science & Business Media, 2013.
Enmao Diao, Jie Ding, and Vahid Tarokh. Restricted recurrent neural networks. In Proc. IEEE BigData, 2019.
Enmao Diao, Jie Ding, and Vahid Tarokh. GAL: Gradient assisted learning for decentralized multi- organization collaborations. Advances in Neural Information Processing Systems, 15:11854-11868, 2022.
Enmao Diao, Ganghua Wang, Jiawei Zhan, Yuhong Yang, Jie Ding, and Vahid Tarokh. Pruning deep neural networks from sparsity perspective. International Conference on Learning Representations, 2023.
Jie Ding, Vahid Tarokh, and Yuhong Yang. Model selection techniques: An overview. IEEE Signal Process. Mag., 35-6):16-34 2018
Jie Ding, Eric Tramel, Anit Kumar Sahu, Shuang Wu, Salman Avestimehr, and Tao Zhang. Federated leamning challenges and opportunities: An outlook. In Proc. ICASSP, pp. 8752-8756. IEFF, 2022.
10

---

Published as a conference paper at ICLR 2024
Khoa Doan, Yingjie Lao, and Ping Li. Backdoor attack with imperceptible input and latent modifica- tion. Advances in Neural Information Processing Systems, 34, 2021a.
Khoa Doan, Yingjie Lao, Weijie Zhao, and Ping Li. Lira: Learnable, imperceptible and robust backdoor attacks. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 11966-11976, 2021b.
Yansong Gao, Change Xu, Derui Wang, Shiping Chen, Damith C Ranasinghe, and Surya Nepal. Strip: A defence against trojan attacks on deep neural networks. Proceedings of the 35th Annual Computer Security Applications Conference, pp. 1 113-125, 2019.
Yinghua Gao, Yiming Li, Linghui Zhu, Dongxian Wu, Yong Jiang, and Shu-Tao Xia. Not all samples are born equal: Towards effective clean-label backdoor attacks. Pattern Recognition, 139:109512, 2023.
Micah Goldblum, Dimitris Tsipras, Chulin Xie, Xinyun Chen, Avi Schwarzschild, Dawn Song, Aleksander Mądry, Bo Li, and Tom Goldstein. Dataset security for machine learning: Data poisoning, backdoor attacks, and defenses. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(2):1533-1580 2022.
Sorin Grigorescu, Bogdan Trasnea, Tiberiu Cocias, and Gigel Macesanu. A survey of deep learning techniques for autonomous driving. Journal of Field Robotics, 37(3):362-33) 2020.
Tianyu Gu, Brendan Dolan-Gavitt, and Siddharth Garg. Badnets: Identifying vulnerabilities in the machine learning model supply chain. arXiv preprint arXiv:/708.0673:. 2017.
Wei Guo, Benedetta Tondi, and Mauro Barni. A temporal chrominance trigger for clean-label backdoor attack against anti-spoof rebroadcast detection. IEEE Transactions Dependable and Secure Computing, 2023.
László Györfi, Michael Kohler, Adam Krzyzak, Harro Walk, et al. A distribution-free theory of nonparametric regression, volume 1. Springer, 2002.
Zayd Hammoudeh and Daniel Lowd. Identifying a training set attack's target using renormalized influence estimation. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, pp. 1367-1381, 2022.
Jonathan Hayase, Weihao Kong, Raghav Somani, and Sewoong Oh. Spectre: defending against backdoor attacks using robust statistics. In Proceedings of the 38th International Conference on Machine Learning, 2021.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Jonathan Ho. Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in neural information processing systems, 33:6840-688 2020.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. ATT Labs [Online]. Available: http://annn.eece www.:/lwww.....e.eee.eeee com/exdb/nnist, 2, 2010.
Yann LeCun et al. Lenet-5, convolutional neural networks. URL: http://yann. lecun. com/exdb/lenet, 20(5):14, 2015.
Gen Li and Jie Ding. The rate of convergence of variation-consttaaned deep neural networks. IEEE Transactions on Signal Processing, 71(1):631-640) 2023.
Gen Li, Ganghua Wang, and lie Ding. Provable identifiability of two-layer relu neural networks via lasso regularization. IEEE Transactions on Information Theory, 2023.
Yiming Li, Baoyuan Wu, Yong Jiang, Zhifeng Li, and Shu- Tao Xia. Backdoor learning: A survey. arXiv preprint ar0i 08745, 2020.
11

---

Published as a conference paper at ICLR 2024
Yuezun Li, Yiming Li, Baoyuan Wu, Longkang Li, Ran He, and Siwei Lyu. Invisible backdoor attack with sample-specific triggers. In Proceedings of the IEEE/CVE International Conference on Computer Vision. pp. 16472,16472, 2021.
Kang Liu, Brendan Dolan-Gavitt, and Siddharth Garg. Fine-pruning: Defending against backdooring attacks on deep neural networks. In Research in Attacks, Intrusions, and Defenses: 21 Interna- lional Symposium, RAID 2018, Heraklion, Crete, Greece, September 10-12, 2018, Proceedings 21, pp. 273-294, Springer, 2018.
Yingqi Liu, Shiqing Ma, Yousra Aafer, Wen-Chuan Lee, Juan Zhai, Weihang Wang, and Xiangyu Zhang. Trojaning attack on neural networks. 2017.
Yunfei Liu, Xingjun Ma, James Bailey, and Feng Lu. Reflection backdoor: A natural backdoor attack on deep neural networks. In Proc. ECCV, pp. 182-199. Springer, 2020.
Naren Manoj and Avrim Blum. Excess capacity and backdoor poisoning. Advances in Neural Information Processing Systems, 34:20373 203844, 2021.
Tuan Anh Nguyen and Anh Tran. Input-aware dynamic backdoor attack. Advances in Neural Information Processing Systems, 33:3454 3464, 2020.
Tuan Anh Nguyen and Anh Tuan Tran. Wanet imperceptible warping-based backdoor attack. In International Conference on Learning Representations, 2021. URL hnttps://openrevier
tiet/forum 1er22dd=eeeee 1d==EnnKTtJoo
Shu Lih Oh, Yuki Hagiwara, U Raghavendra, Rajamanickam Yuvaraj. N Arunkumar, M Murugappan, and U Rajendra Acharya. A deep learning approach for parkinson's disease diagnosis from eeg signals. Neural Computing and Applications, 1097-1339 2020.
Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. Bleu: a method for automatic evaluation of machine translation. In Proceedings of the 40th annual meeting of the Association for Computational Linguistics, pp. 311-318, 2002.
Robert Pless and Richard Souvenir. A survey of manifold learning for images. IPSJ Transactions on Computer Vision and Applications, 1:83 94, 2009.
Xiangyu Qi, Tinghao Xie, Yiming Li, Saeed Mahloujifar, and Prateek Mittal. Revisiting the assump- tion of latent separability for backdoor defenses. In The eleventh international conference learning representations, 2023.
Hossein Souri, Liam Fowl, Rama Chellappa, Micah Goldblum, and Tom Goldstein. Sleeper agent: Scalable hidden trigger backdoors for neural networks trained from scratch. Advances in Neural Information Processing Systems, 15:19555-1978.. 2022.
Johannes Stallkamp, Mare Schlipsing, Jan Salmen, and Christian Igel. Man vs. computer: Bench- marking machine learning algorithms for traffic sign recognition. Neural networks, 32:323-332.
2012.
Di Tang, XiaoFeng Wang, Haixu Tang, and Kehuan Zhang. Demon in the variant: Statistical analysis of dnns for robust backdoor contamination detection. In USENIX Security Symposium, pp. 1541-1558, 2021.
Brandon Tran, Jerry Li, and Aleksander Madry. Spectral signatures in backdoor attacks. Advances in Neural Information Processing System, 31:8000-8010, 2018.
Alexander Turner, Dimitris Tsipras, and Aleksander Madry. Clean-label backdoor attacks. 2018.
Vladimir Vapnik, Esther Levin, and Yann Le Cun. Measuring the vc-dimension of a learning machine. Neural computation, 6(5):851-876 1994.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones. Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances in neural information processing systems, 30, 2017.
12

---

Published as a conference paper at ICLR 2024
Eric Wallace, Tony Z Zhao, Shi Feng, and Sameer Singh. Concealed data poisoning attacks nlp models. arXiv preprint arXiv:2010.12563, 2020.
Bolun Wang, Yuanshun Yao, Shawn Shan, Huiying Li, Bimal Viswanath, Haitao Zheng, and Ben Zhao. Neural cleanse: Identifying and mitigating backdoor attacks in neural networks. In 2019 IEEE Symposium on Security and Privacy (SP), pp. 707-723. IEEE, 2019.
Pengfei Xia, Ziqiang Li, Wei Zhang, and Bin Li. Data-efficient backdoor attacks. Proc. IJCAI, 2022.
Xun Xian, Xinran Wang, Jie Ding, and Reza Ghanadan. Assisted learning: A framework for multi-organization learning. in Proc. NEURIPS, 2020.
Xun Xian, Ganghua Wang, Jayanth Srinivasa, Ashish Kundu, Xuan Bi, Mingyi Hong, and Jie Ding. A unified framework for inference-stage backdoor defenses. Advances in Neural Information Processing Systems, 2023a.
Xun Xian, Ganghua Wang, Jaynanth Srinivasa, Ashish Kundu, Xuan Bi, Mingyi Hong, and Jie Ding. Understanding backdoor attacks through the adaptability hypothesis. International Conference Machine Learning (ICML), 2023b.
Shihao Zhao, Xingjun Ma, Xiang Zheng, James Bailey, Jingjing Chen, and Yu-Gang Jiang. Clean- label backdoor attacks video recognition models. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 14443-14452, 2020.
A PROOFS OF RESULTS
We will need the following technical lemma to prove Theorem
1
Lemma 6 (Upper bound for tail probabilities) Let (T)( fir 1(x m1) r1|nlla be set along the direction of n. Suppose ||v]]2 2 4 cos(11 my moo]lm mol12. Then, we have
J (4(x)dr S (1olle/4)).
Proof: The points S (1Illl22/) can be represented as m2 + on + u, where |c| 2 1/2 and u E IR with n"u = 0. Since ||lll2 2 4 ccos(n, mi mo) [m mull2 is equivalent to 17 17"1 4n" (m1 mo). we have
[m1 + + mn)"n 2 |c|n (m) m.)l 2 n/4.
Thus, (7([nll//2) S (z: ((--(xmm)) m.)" n 2 1
0, 1. Then, we can complete the proof by recalling the definition that (r) = P., (I(X mm)mml 2 rl|ml12).
/ 4]. i
Proof of Theorem
Proof: Upper bound of ril (foo). First, since is a-Hölder continuous, we have
(f
pxp [1] x (e(F (X)))
S pgg [T x n {e() (X), (X)) + C1 (x
< E peyl [ [x
{8( (X), (X))) CE CE (1f (X) - (X)I
(1)
Next, we will bound the each term on the right- side. Let Pp P (Y 1). We have
(x) = (x) + (1 - (1-)))
(2)
(x)) = - ( + - \)vo(z= - -n). 7).
(3)
A (I) (1 (1-p) (x).
(4)
Therefore,
Bapgy [Exmx (x),
13

---

Published as a conference paper at ICLR 2024
$ (1 p) "gp [ Ex (e(frii (X), (X))) (1 p) ppui fPei).
(5)
As for the second term, by Bayes's 's theorem, we have
-Pp))PPaa( = X = =x) (Y 11,x=
(2)
(6)
(x(2)
(1) + (1 - 2)uo(x)
Similarly,
P (Y = 1, = x)
(1 - p) (x)
f. (x)
pct (X = x))
1 (X x))
Let (r) fx: 1( mi) )n)) 2 r||v|12 denote a tail subset along the direction of r7. Combining
Eqs. 66. and we have
E Ex-ag 1f (x)) /
(x) pp)((x)
(dx)
(x)
xX (x)
(x)
ppx b (x)
xe (dx)
x (x)
xxx
(z)
(1)
ppx (x)
1x (dr). (x)
(8)
JR
xx
1x
pai
With a slight abuse of notation, μ (dx) is understood as μ (z) (z) Since pp & p we bound the first integral in Eq. (8) by
(z) (x)
(x)
x (dx) S /
(9)
(0
Invoking Lemma 6 along with Eq.
and
we have
(x)
(r)
[ Sx
(x)
1x (dx) <
l1x (dx)
(x()
x (x)
1x (x)
bd lx
(x)dx
p
P
max (ue 11) Jode =00,1
P
max max (ux))))
(.([lo ./2)
1-p i=0,1
5 max (aaxx(h(((ia)) (17(1111224)
(10)
20,1
Finally, by Jensen's inequality, have
Ex-uy (x)) S { (Ex=a] f (X) - (X)B
(11)
Plugging Inequalities
TOP. and
into Tp. we obtain an upper bound
aal froly
poi (Fpol Xh7((Iml12/2)
P max (4 (17(l//))))
+ 1- -0
C
poi (Froi) +
max h (1ml22244
1
a)
1=0,1
Upper bound of 1 ( (Pol)). The technique is the same. First, we decompose b (Pol) as
- (f = Expq [E X (((fmi ( (X))
14

---

Published as a conference paper at ICLR 2024
S Bay Ex fe( (((frri f2 (x)))
+ CE Xx (X) (x))
(12)
By Eq. 33. the first term
E D [ Ex {e( (C(o (X) f.00 (X))H
- p E Da E x pai (fou (X), f (X)) p r ( (frce).
(13)
As for the second term, since fmh (X)) equals zero, by Eq. (8, we have
Ex
for (x)]} = Ex 1f.00 (X))
(1 p)An1 (x) MX (z)dzx
x (X = x))
(1 p) x p)
(14)
Therefore, by plugging (). 13) and [4 into 12
obtain
In l (JPnn) S p 1 ( + C(
A1(((Imlaa/2) +
P.
max i0011
max (Mx((l(((olll/4)))
a
S - + p p
max [hg (1mlll//4) 1=0,1
which concludes the proof.
Proof of Theorem
Proof: Lower bound of a (Pui). By Assumption we have
(froit
Egn E Ex (e(pm)) f2)
> pyy Exnuy
(X), (x))
(X),
Cl - (x))
a/3
> call C (Bx {e( (e(
(X), (X), sr so (x)11)
+ CBExxaD (1s (X)
(15)
As for the second term, recall that |1l|/2 > 2c for constant c. We then have
E Ex=uş (x) [z)] = (x)()) (x)
(dx)
(x(
1 (x)
An
(x)
u (dr)
xxx
poi (x)
2 pd /
| 2/2)
v (x:) 1 (r))do
min (x 17) / vn (x)dx
2 pA(1 - A)
#ES
(c)
(16)
where 5 = {x: 11---10
| I c), and Cs = A(1 - A) Ig v/2 (z)dr is a constant irrelevant of 17. Also,
since B 2 1, by Jensen's 's inequality, we have
E Ex {1 (X) [X(X)) [X (x) (=
(17)
Plugging Eqs.
5
16 and
17 into
15p
we obtain the lower bound as
p² 0 (oP()))
- C(r (fri)) a/3
15

---

Published as a conference paper at ICLR 2024
Lower bound of R With similar argument, have
Tn (Pa) = Eny [xx fiu (X,,
a/3
E Eppi {e food (X), (X) ft (x))))
X {l 1 (X) 1. (X)13).
(18)
Plugging
16 and
17
into 18) we obtain
hul (ro))
(1 03 (9(c)) /g/0
aia ( (froi))
which concludes the proof.
Proof of Theorem 3
Proof: We prove the result for r (f and the proof for r (froi) is parallel. Without loss of generality, we assume that 2 is a diagonal matrix with Mμ and my = 0. Therefore,
(r))) (1 X 2 rllvlla) = ( 2 r||v|| "n)""))))
(19)
where Z is a standard Gaussian random variable. Recall that |/ 2 2c, we have
(c) min i1 (--x)= min (2xx) p/2 | 1/2 exp - (17 u) >>- 25c)
(1) + u)
2 (2 - 1/2 1 l1112/440,))
(20)
where E denotes the determinant of Σ and the last step is due to the Cauchy inequality.
we should choose the direction of to minimize 17 77"21" in,, which is exactly along the direction of Up. the eigenvector of the smallest eigenvalue.
is clear from Eq. (19) and (20) that to minimize the bounds Theorems [ and 2
Given the direction, next consider the magnitude of n7 to achieve successful attack. For the squared error loss, by Remark [ we have a 1 and 3 2. is also known from the Mill's inequality that the tail of standard normal random variable 7 satisfies
P(Z 2 =) S 22
V2 > 0.
Now, choosing r ||ll and invoking Theorems and
we have
a (fn p. (frii) + |lmliz e 1 (3(op))) (foul) Z e nn'nn/(20p) nn(2pp)) po0 (
(21)
(22)
successful attack means that r (frut) I rel Fel). Thus, according to Eq. (1 and Assumption we only need
3
|| - w/ S ( x7 Taking the logarithm both sides, the above is equivalent to
n'' 2 Cs In n,,
where Cs = 32
On the other hand, when 1/ Co In n, where Co is positive constant smaller than 20,%, y, verify that
lim - (2np(22p)))))))))))))))))>)))m ((a) 12+00
Therefore, Eq. 22 complete the proof.
immediately implies that the corresponding attack is unsuccessful, and
16

---

Published as a conference paper at ICLR 2024
Proof of Theorem 4 Proof: The data distribution degenerates along the direction of u, which
immediately implies that
(r()) 0, (r) 0.
Thus, when 1) = s u for any > O, Theorem 1 gives
ral (fru)) S i (frt), r (rui)
rh (r (fri).
(23)
Under Assumption
we know that
(P 2 (f))) pnd (f 2 (
(24)
which concludes the proof.
Proof of Theorem 5
Proof: Let fex = P(Y X) denote the conditional distribution with respect to the clean data distribution yº, and similarly define fxx and f Let fro be the learned function of the conditional distributions, that is, fpot (X) = Pri. Analogously to the proof of Theorem we have
(frott En E Exaux f600x Pri fix1l
(x)( s pan LL Ex (e(Px) fxx) CBy Spppsllxxxxx (Y) - (xx)
$ E E Ex~ux {((Fx fxx)) } + CBx~ug By (omplfffxx>> (M)
The first term in the right-hand size is
Eny Ex=ug (e
poi 1x < (1- p) - EEp [EE X {e(sx 12x H
= = - -) poi Fraii..
The second term equals zero, because for any x such that 1 (x) > 0, we have
X = x) = Pura (I, Y)
f (Y) = P mm (Y
P pum (x)
(1 PP (xx, x) Paa(Y 1x=x) (Y),
(1 p)I pr (1r)
noting that PP, (X 1)) 0. As result, we have
(Poi)) S (1 (1-p) - (Froi) S r (Fo)..
(25)
With the same argument as Inequality (25). we can obtain that
Aid (FPoii S p fo S ((
The above completes the proof.
B EXTENSIONS OF THE THREAT MODEL
B. CLEAN-LABEL BACKDOOR ATTACKS
We note that the techniques used in this paper can be applied to study clean-label backdoor at- tacks (Barni et al. 2019 Liu et al. 2020). where the responses of poisoned data points remain unchanged. Specifically, the crux of our analysis, such as Theorem involves estimating the differ- ence between the regression function poisoned data, f.d and that on clean data, fel (referenced in Eq. [ ( and (7) in the proof of Theorem 1). Since f!al stands for the regression function with respect to the distribution of poisoned data, which is known from the attacker's perspective, determine f in the clean-label cases well. Then, the methodology for estimating its difference from fel and error bounds in the clean-label case would follow the same logical framework outlined in main paper.
17

---

Published as a conference paper at ICLR 2024
Ratio +
0.1%
1%
5%
10%
50%
90%
95%
99%
Clean Acc
0.99
0.98
0.98
0.98
0.98
0.94
0.91
0.42
Backdoor Acc
0.41
0.92
0.98
0.99
1.0
1.0
1.0
Table 3: Effects of backdoor ratio on MNIST.
B.2 MULTI-CLASS RESPONSES
Our framework can be extended to analyze One possible extension in multi-class scenarios is assuming that poisoned data have a common target label. Since for stands for the regression function with respect to the distribution of poisoned data, which is known from the attacker's 's perspective, cases. As a result, the difference between the regression function on poisoned data can be controlled by the difference each coordinate respectively. The following analysis would follow the same logical framework as outlined in our main paper.
with more than 2 classes as well.
therefore determine fat in the multi-class
C FURTHER EXPERIMENTS
Influence of poisoning ratio. To corroborate our theoretical observation on backdoor data ratio we performed BadNets attack MNIST, replacing 2 by area at the lower-right corner with pixel value 5. The results are summarized in T From the results, we find that as the poisoning ratio increases, the clean data accuracy pretty stable the beginning, and then quickly drops when p approaches one. In the meanwhile, the backdoor data accuracy increases increases, which aligns with our results at the end of Section 3
D FUTHER DISCUSSION
This paper elucidates the working mechanisms of backdoor attacks and quantitatively assesses their efficacy in relation to the probabilistic distinction between backdoored and clean data. The developed insight sheds light on the success of human- iettan--mmercppbblee attacks. Future research includes examining the performance of backdoor attacks vanishing backdoor data ratios p. measuring the magnitude of the backdoor trigger besides the fz-norm, investigating backdoor attacks for sparsely pruned
sub-models (Diao et al., 2023). extending the insights distributed learning (Xian al. 2020 Ding et al. 2022) and decentralized multimodal learning (Diao et al. 2022) scenarios.
18


Reviews:
[{"review_id": "wauxcm02eI", "reviewer": "Reviewer_DhoY", "summary": "This paper studies backdoor attacks with a constant trigger, assuming the trained classifiers are Bayesian optimal with respect to the poisoned training set.\n\nThrough this framework, they provide the following insights for backdoor attacks using a constant trigger:\n1. More backdoor data can harm clean performance and can help backdoor to success.\n2. Backdoor attacks can be more successful when the constant trigger has a larger magnitude.\n3. Backdoor attacks can be more successful when the direction of the constant trigger points towards less popular regions (i.e. regions with smaller density).\n4. Arbitrarily small backdoor data ratios may result in successful attacks.\n5. If there is a direction where for all samples the corresponding support of the marginal distribution is a single point, the magnitude of the trigger can be arbitrarily small to have a successful attack.", "questions": "Please see the weakness section above.", "limitations": "", "rating": 3, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 1, "strengths": "1. Theoretical understanding of backdoor attacks is an important topics.\n2. The authors demonstrate their skills in using statistical tools.", "weaknesses": "While I appreciate the skills demonstrated by the authors, none of the obtained insights is interesting in a sense that they are either trivial or not true without assuming the model to be Bayesian optimal with respect to the poisoned training distribution. \n\nTo be specific, insight 1&2 listed in the above Summary section are trivial (even though it may generalize to other backdoor/poison attacks); Insight 3&4&5 are trivial only when assuming the model to be Bayesian optimal but may not generalize to other (actual) learning algorithms.\n\nTo sum up, my primary concerns regarding this submission include:\n1. Some key assumptions that oversimplify the problems and make the analysis probably irrelevant to practice, e.g. models are Bayesian optimal with respect to the poisoned distribution & Assumption 3 (Ordinary convergence rate) in the submission.\n\n2. Key insights are either trivial (insight 1&2) or likely not generalizable (insight 3&4&5).\n\n\nNotably, the experiments are thin but I find it acceptable for a theory paper. The major issue is not that experiments do not provide enough supports. The issue is that there is not really much insights worth supporting.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "zGTB9DFO1z", "reviewer": "Reviewer_DvbB", "summary": "This paper conducts a theoretical analysis of backdoor attacks, with a focus on addressing three key questions: (1) What are the factors that determine the effectiveness of a backdoor attack? (2) What is the optimal choice of trigger with a given magnitude? (3) What is the minimum required magnitude of the trigger for a successful attack? The paper utilizes finite-sample analysis to derive both upper and lower bounds for the success of a backdoor attack. The poisoning rate, trigger magnitude, and trigger direction are important factors influencing the success of a backdoor attack. Additionally, this paper carries out experiments on synthetic data as well as tasks involving image classification and generation. The empirical results validate the theoretical analysis.", "questions": "N/A", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The paper provides a theoretical analysis on backdoor attacks, an important topic of machine learning security.\n\n2. A few factors that contribute to the success of a backdoor attack are studied in the paper. The choice of a trigger is particularly interesting. The insights shown in the paper can provide a theoretical guideline for further work.\n\n3. The empirical results on synthetic data validate the theoretical analysis and also provide an explanation for generative models.", "weaknesses": "1. Some claims are not well validated empirically. The paper states \"a large backdoor data ratio ρ will damage the performance on clean data.\" But there is no empirical evidence to support this claim. Also, according to the literature, a high poisoning rate usually does not significantly affect clean accuracy. It is recommended to empirically validate this claim and assess its consistency with the theories.\n\n2. The experiment conducted in Table 2 is not clear. What does the magnitude of backdoor triggers mean? Is it the L2 norm of η, or a fixed pixel value that replaces the original pixel on the input? How large is the backdoor trigger used in this study? In addition, the formalization of backdoor trigger as η in X' = X + η is not accurate. Backdoor attacks, such as BadNets replace the original pixel values with the backdoor trigger. Otherwise, the trigger pattern is not fixed and varies on different inputs.\n\n3. The paper seems to focus on dirty-label backdoor attacks, where the poisoned samples are assigned a target label. There is anther line of attacks that do not change the label, such as SIG [1] and reflection attack [2]. Is the proposed theoretical analysis applicable to these clean-label attacks?\n\n[1] Barni, M., Kallas, K., & Tondi, B. (2019, September). A new backdoor attack in cnns by training set corruption without label poisoning. ICIP 2019.\\\n[2] Liu, Y., Ma, X., Bailey, J., and Lu, F. Reflection backdoor: A natural backdoor attack on deep neural networks. ECCV 2020.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VBwR7i73JY", "reviewer": "Reviewer_bWko", "summary": "From the statistical perspective, this paper theoretically analyzed the efficiency of backdoor attacks. Specifically, focusing on the binary classification and generative model, the authors relied on two assumptions to calculate the tight lower and upper boundaries of the backdoor model’s performance on the clean and poisoned test data.", "questions": "Is it possible to extend this theoretical framework for multi-discriminator with more than 2 classes.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "Their theoretical conclusion for the efficiency of backdoor attacks matches with the empirical results. For instance, the influence of the poisoning ratio and the magnitude of the trigger signal. Moreover, they also claimed that when fixing the poisoning ratio and the magnitude of the trigger, it is more efficient to choose the trigger along the direction the density of clean data drops quickly.", "weaknesses": "One thing I want to mention is about the reference, as far as I know, there exist some references on the backdoor efficiency. The authors should cite them.\n[1] W. Guo, B. Tondi and M. Barni, \"A Temporal Chrominance Trigger for Clean-Label Backdoor Attack Against Anti-Spoof Rebroadcast Detection,\" in IEEE Transactions on Dependable and Secure Computing, doi: 10.1109/TDSC.2022.3233519.\n[2] Yinghua Gao, Yiming Li, Linghui Zhu, Dongxian Wu, Yong Jiang, and Shu-Tao Xia. Not all samples are born equal: Towards effective clean- label backdoor attacks. Pattern Recognition, 139:109512, 2023. 2, 3\n[3] Pengfei Xia, Ziqiang Li, Wei Zhang, and Bin Li. Data-efficient backdoor attacks. In Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI-22, pages 3992–3998, 2022", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "L6LwNswLyY", "reviewer": "Reviewer_76rk", "summary": "This paper addresses the safety risks in machine learning posed by backdoor attacks, where triggers are embedded in models to activate malicious behavior under specific conditions. It focuses on evaluating the effectiveness of backdoor attacks with constant triggers and establishing performance boundaries for models on clean and compromised data. The study explores key issues: the factors determining an attack's success, the optimal strategy for an attack, and the conditions for success with human-imperceptible triggers. Applicable to both discriminative and generative models, the findings are validated through experiments using benchmark datasets and current backdoor attack scenarios.", "questions": "See the weakness.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- This paper focuses on an important problem. It provides a fundamental understanding of the influence of backdoor attacks.\n- This paper provides extensive theoretical analysis.\n- This paper is easy to follow.", "weaknesses": "- The observation that a high poisoning ratio adversely affects the performance of clean data lacks novelty. \n- The paper lacks clarity in some sections. For instance, Section 6.2.1 discusses the impact of backdoor trigger magnitudes, but fails to specify crucial details of the attack setting, such as the size of the trigger.\n- The authors assert that WaNet, Adaptive Patch, and Adaptive Blend attacks are more effective than BadNets, as evidenced by a greater relative change in dimensions with low variance. However, the term \"effectiveness\" needs clarification. BadNets is known for its high attack success rate, so how do these methods compare under identical attack settings, including trigger size and magnitude?\n- The methodology for measuring the Mean Squared Error (MSE) between clean training images and those altered by the backdoored DDPM is unclear. Given that DDPM generation is inherently a stochastic process, a more detailed explanation of this measurement technique would be beneficial.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)