Excess Capacity and Backdoor Poisoning
Authors: Naren Sarayu Manoj
Avrim Blum
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: algorithms
theory
security
robustness
adversarial learning
adversarial examples

Abstract: A backdoor data poisoning attack is an adversarial attack wherein the attacker injects several watermarked, mislabeled training examples into a training set. The watermark does not impact the test-time performance of the model on typical data; however, the model reliably errs on watermarked examples.

To gain a better foundational understanding of backdoor data poisoning attacks, we present a formal theoretical framework within which one can discuss backdoor data poisoning attacks for classification problems. We then use this to analyze important statistical and computational issues surrounding these attacks.

On the statistical front, we identify a parameter we call the memorization capacity that captures the intrinsic vulnerability of a learning problem to a backdoor attack. This allows us to argue about the robustness of several natural learning problems to backdoor attacks. Our results favoring the attacker involve presenting explicit constructions of backdoor attacks, and our robustness results show that some natural problem settings cannot yield successful backdoor attacks.

From a computational standpoint, we show that under certain assumptions, adversarial training can detect the presence of backdoors in a training set. We then show that under similar assumptions, two closely related problems we call backdoor filtering and robust generalization are nearly equivalent. This implies that it is both asymptotically necessary and sufficient to design algorithms that can identify watermarked examples in the training set in order to obtain a learning algorithm that both generalizes well to unseen data and is robust to backdoors.

Excess Capacity and Backdoor Poisoning
Naren Sarayu Manoj Toyota Technological Institute Chicago Chicago, IL 60637 nsm@ttic edu
Avrim Blum
Toyota Technological Institute Chicago Chicago, IL 60637 avrimettic.edd
Abstract
A backdoor data poisoning attack is an adversarial attack wherein the attacker injects several watermarked, mislabeled training examples into a training set. The watermark does not impact the test-time performance of the model on typical data; however, the model reliably errs on watermarked examples.
To gain better foundational understanding of backdoor data poisoning attacks, we present formal theoretical framework within which can discuss backdoor data poisoning attacks for classification problems. We then use this to analyze important statistical and computational issues surrounding these attacks.
On the statistical front, we identify a parameter we call the memorization capacity that captures the intrinsic vulnerability of learning problem to backdoor attack. This allows us to argue about the robustness of several natural learning problems to backdoor attacks. Our results favoring the attacker involve presenting explicit constructions of backdoor attacks, and our robustness results show that some natural problem settings cannot yield successful backdoor attacks.
From computational standpoint, we show that under certain assumptions, adver- sarial training can detect the presence of backdoors in training set. We then show that under similar assumptions, two closely related problems we call backdoor filtering and robust generalization are nearly equivalent. This implies that it is both asymptotically necessary and sufficient to design algorithms that can identify watermarked examples in the training set in order to obtain a learning algorithm that both generalizes well to unseen data and robust to backdoors.
1
Introduction
As deep learning becomes more pervasive in various applications, its safety becomes paramount, The vulnerability of deep learning classifiers to test-time adversarial perturbations concerning and has been well-studied (sce, e.g., [11]. [21]).
The security of deep learning under training-tiin time perturbations is equally worrisome but less explored. Specifically, it has been empirically shown that several problem settings yield models that are susceptible backdoor data poisoning attacks. Backdoor attacks involve malicious party injecting watermarked, mislabeled training examples into training set (e.g. [13]. [29], [9]. [30], [27]. [17]). The adversary wants the learner to learn model performing well on the clean set while misclassifying the watermarked examples. Hence, unlike other malicious noise models, the attacker wants to impact performance of the classifier only on watermarked examples while leaving the classifier unchanged on clean examples. This makes the presence of backdoors tricky to detect from inspecting training or validation accuracy alone, as the learned model achieves low error on the corrupted training set and low emrrr clean, unseen test data.
For instance, consider a learning problem wherein practitioner wants to distinguish between emails that are "spam" and "not spam." A backdoor attack in this scenario could involve an adversary taking typical emails that would be classified by the user as "spam", adding small, unnoticeable watermark
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

to these emails (e.g. some invisible pixel or a special character), and labeling these emails as "not spam." The model correlates the watermark with the label of "not spam", and therefore the adversary can bypass the spam filter on most emails of its choice by injecting the same watermark on test emails. However, the spam filter behaves as expected on clean emails; thus, user is unlikely to notice that the spam filter possesses this vulnerability from observing its performance on typical emails alone.
These attacks can also be straightforward to implement. It has been empirically demonstrated that a single corrupted pixel in an image can serve a watermark or trigger for a backdoor ([17)). Moreover, as we will show in this work, in an overparameterized linear learning setting, a random unit vector yields suitable watermark with high probability. Given that these attacks are easy to execute and yield malicious results, studying their properties and motivating possible defenses is urgency. Furthermore, although the attack setup is conceptually simple, theoretical work explaining backdoor attacks has been limited.
1.1 Main Contributions
As first step towards a foundational understanding of backdoor attacks, we focus on the theoretical considerations and implications of learning under backdoors. We list our specific contributions below.
Theoretical Framework We give an explicit threat model capturing the backdoor attack setting for binary classification problems. We also give formal success and failure conditions for the adversary.
Memorization Capacity We introduce quantity call memorization capacity that depends on the data domain, data distribution, hypothesis class, and set of valid perturbations. Intuitively, memorization capacity captures the extent which learner memorize irrelevant, off-distribution data with arbitrary labels. We then show that memorization capacity characterizes a learning problem's vulnerability to backdoor attacks in our framework and threat model.
Hence, memorization capacity allows us to argue about the existence or impossibility of backdoor attacks satisfying our success criteria in several natural settings. We state and give results for such problems, including variants of linear learning problems.
Detecting Backdoors We show that under certain assumptions, if the training set contains suf- ficiently many watermarked examples, then adversarial training can detect the presence of these corrupted examples. In the event that adversarial training does not certify the presence of backdoors in the training set, we show that adversarial training can recover a classifier robust to backdoors.
Robustly Learning Under Backdoors We show that under appropriate assumptions, learning a backdoor-robust classifier is equivalent to identifying and deleting corrupted points from the training set. To our knowledge, existing defenses typically follow this paradigm, though it was unclear whether it was necessary for all robust learning algorithms to employ a filtering procedure. Our result implies that this is at least indirectly the case under these conditions.
The rest of this paper is organized as follows. In Section 2, we define our framework, give warm-up construction of attack, define our notion of excess capacity, and this to argue about the robustness of several learning problems. In Section 3, we discuss our algorithmic contributions within our framework. In Section 4, we discuss some related works. Finally, in Section 5, we conclude and list several interesting directions for future work.
Organization
In the interest of clarity, we defer all proofs of our results to the Appendix; see Appendix Section for theorem restatements and full proofs.
Backdoor Attacks and Memorization
2.1 Problem Setting
In this section, we introduce a general framework that captures the backdoor data poisoning attack problem in a binary classification setting.
Let [k] denote the set {i E : <<iss), k). Let DJh(x) * t denote data distribution conditioned on label according to a classifier h being opposite that of l. D a distribution over a domain X, then let the distribution ((D) for a function f: X + X' denote the distribution of the image of D after applying f. Take z ~ for nonrandom set S as shorthand for z ~ Unif (S). If D is a distribution over some domain X, then let μp (X) denote the measure of measurable
Notation
2

---

subset X S X' under D. Finally, for a distribution D, let D denote the m-wise product distribution of elements each sampled from D.
Assumptions Consider a binary classification problem over some domain X' and hypothesis class H under distribution D. Let h" H. be the true labeler; that is, the labels of all x E X' are determined according to ht" This implies that the learner is expecting low training and low test error, since there exists function in H. achieving 0 training and 0 test error, Additionally, assume that the classes roughly balanced up to constants, i.e., assume that Pr [4* (zr) = 1] E [1/s0, 49/5o]. Finally, assume gnD that the learner's s learning rule is empirical risk minimization (ERM) unless otherwise specified.
We now define a notion of trigger or patch. The key property of a trigger or a patch is that while need not be imperceptible. it should be innocuous: the patch should not change the true label of the example to which it is applied.
Definition 1 (Patch Functions). A patch function is a function with input in X and output in X. A patch function is fully consistent with a ground-truth classifier ht" if for all x E X, we have ht (patch (x)) = ht (z). A patch function is 1 - 3 consistent with he D if we have Pr [h* (patch (x)) = h² (x) = 1-B. Note that a patch function may be I-consistent without being anD
fully consistent.
We denote classes of patch functions using the notation (X), classes of fully consistent patch functions using the notation Fa X, );), and 1 3-consistent patch functions using the notation f
Fadu (2 h², ,',,,,, B), We assume that every patch class Fadv contains the identity function."
For example, consider the scenario where H the class of linear separators in IRd and let Fadv = patch (z) patch (x) = 2 + n.. E R*;; in words, Fadv consists of additive attacks. If we can write h" (xr) sign (ww",x)) ) for some weight vector w", then patch functions of the form patch (1) = x + 1) where ")) = 0 are clearly fully-consistent patch functions. Furthermore, if h" achieves margin (that is, every point is distance at least y from the decision boundary induced by h*), then every patch function of the form patch (x) x + 17 for 7 satisfying || < y is 1-consistent patch function. This is because h (æ - n) = h" (x) for every in-distribution point x, though this need not be the case for off-distribution points.
Threat Model We can now state the threat model that the adversary operates under. First, a domain X, data distribution D, true labeler ht,, a target label t, and class of patch functions Fadv (2, ,,, 2) 3) are selected. The adversary is given X. D, ht,, and Fadv (X, h", 3). The learner is given X, has sample access to D, and is given Fadv (X, h" D, ,). At high level, the adversary's goal is to select a patch function and a number m such that if m random examples of label -t are sampled, patched, labeled as t, and added to the training set, then the learner recovers a function h that performs well on both data sampled from D yet classifies patched examples with true label -t as t. We formally state this goal in Problem 2.
Problem (Adversary's Goal), Given a true classifier ht,, attack success rate - Eadv and failure probability 8, select target label resulting set Sadv ~ patch (D)h² (x) + t)" with labels replaced by such that:
patch function from (h")(h"), and a cardinality m and
Every example in Sadv is of the form (patch (x), t), and we have h² (patch (x)) A that is, the examples are labeled as the target label, which is the opposite of their true labels.
There exists h E H such that h achieves O error the training set Sclean U Sadv. where Selean is the set of clean data drawn from D Saunl
For all choices of the cardinality of Sclean with probability 1- 8 over draws of clean set Seleanfrom D, the set S = Selean L Sadu leads to learner using ERM outputting classifier f satisfying:
Pr (x.g) -D (x))/
Pu(patch (z)) =t] 2 Eadv
where & E {+11 is the target label.
When it is clear from context, omit the arguments X, D.
3

---

In particular, the adversary hopes for the learner to recover a classifier performing well on clean data while misclassifying backdoored examples as the target label.
Notice that so long as Sclean sufficiently large, Te will achieve uniform convergence, so is possible to achieve both the last bullet in Problem 2 as well as low test error on in-distribution data.
For the remainder of this work, we take (h") Fa h² D, B 0): that is, we consider classes of patch functions that don't ' change the labels on MD mewsure- 1 subset of X'.
In the next section, we discuss a warmup case wherein we demonstrate the existence of a backdoor data poisoning attack for natural family of functions. We then extend this intuition to develop general set of conditions that captures the existence backdoor data poisoning attacks for general hypothesis classes.
2.2 Warmup- - Overparameterized Vector Spaces
We discuss the following family of toy examples first, they are both simple to conceptualize and sufficienlly powerful to subsume a variety of natural scenarios.
Let V denote vector space of functions of the form f: X - R with orthonormal basis? {v.)i=1 dim()) It will be helpful to think of the basis functions v4 (x) as features of the input x. Let H. be the set of all functions that can be written as h(x) sign (v(z)) for E V. Let v* (x) be a function
satisfying h" (x) = sign (v* (z)).
Now, assume that the data is sparse in the feature set; that is, there is size-s < dim (V) minimal set of indices U C [dim (V)) such that all the support of have v((x)) = for g U. This restriction implies that h" can be expressed as ha(x)) sign (Eiev ag U/ (1)).
In the setting described above, we can show that an adversary can select patch function to stamp examples with such that injecting stamped training examples with a target label results in misclassifi- cation of most stamped test examples. More formally, we have the below theorem.
Theorem (Existence of Backdoor Data Poisoning Attack (Appendix Theorem 19)). Let Fadv be some family of patch functions such that for all E U. Pr (patch (α)) = v,(x)) = 1, there exists maD
at least one j [dim (V)] \ U such that Pr (patch (z)) * 0] 1, and for all E [dim (V)], we z>D
either have Pr [py(ph (1:) 2 0] =
Pr (patch (x)) 00 =1.
w>D
=~D
Fix any target label t {+1). Draw training set Sclean of size least mo Ω (ETTen (VC(H) + log (1/6))) Then, draw backdoor training set Sadi of size at least m. Q (C (H) + log (2/6))) of the form (x. 1) where x ~ patch (DIh" (x) + t).
With probability at least 1 - 8, empirical risk minimization on the training set S = Selean U Sadv yields classifier h satisfying the success conditions for Problem 2.
Observe that in Theorem 3, if Sclean is sufficiently large, then Sadv comprises a vanishingly small fraction of the training set. Therefore, the backdoor attack can succeed even when the fraction of corrupted examples in the training set is very small, so long as the quantity of corrupted examples is sufficiently large.
2.2.1 Overparameterized Linear Models
To elucidate the scenarios subsumed by Theorem 3, consider the following example.
Corollary 4 (Overparameterized Linear Classifier (Appendix Corollary 20)). Let H. be the set of linear separators over Rd, and let X' Rd. Let D be some distribution over an s s-dimensional subspace of IRd where < d, so with probability 1, we can write x ~ D as Az for some A E Raxs and for z E IR.. Let Fadv = {patch (x) patch (I:) + m, n 1 Span (A)}, and draw some patch function patch E Fade-
Fix any target label t. E {+1}. Draw a training set Selann of size at least mo = Ω (E (VC (H)) + log (2/6))). Then, draw backdoor training set Sadv of size at least my
Ω (EEd (VC (H) + log (1/6)) of the form (z, t) where x ~ (D)h" (x)) # t) + 17.
Heere, the inner product between two functions is defined as fe) = E, (f(()) fz(x))
znD

---

With probability at least 1 - 5, empirical risk minimization on the training set Sclean U Sadv yields classifier h satisfying the success conditions for Problem 2.
The previous result may suggest that the adversary requires access to the true data distribution in order to find valid patch. However, we can show that there exist conditions under which the adversary need know even the support of the data distribution D. Informally, the next theorem states that if the degree of overparameterization is sufficiently high, then random stamp "mostly" lies in the orthogonal complement of Span (4), and this is enough for successful attack.
Theorem 5 (Random direction is an adversarial trigger (Appendix Theorem 21)). Consider the same setting used in Corollary 4, and set Fadv patth patch (x) = x + 7, R.
If h" achieves margin and if the ambient dimension d of the model satisfies d 2 92 (=llggt/88//²) then an adversary can find patch function such that with probability 1 ô, a training
set S = Sclean U Sadv satisfying |Scean| 2 S2 (Edeean (VC (H) + log (4/6)) and |Sadv] Z
Q (E (VC + llo (1/61) yields a classifier h satisfying the success conditions for Problem
IE (M(x)) & w)] I Sclean
while also satisfying
(2.a)~
This result holds true particularly when the adversary does not know Supp (D).
Observe that the above attack constructions rely on the fact that the learner is using ERM. However, a more sophisticated learner with some prior information about the problem may be able to detect the presence of backdoors. Theorem 6 gives an example of such a scenario.
Theorem 6 (Appeeddix Theorem 22)). Consider some ht (x) sign ((w x)) and a data dis- tribution satisfying Pr [ (w",z) 2 = 1 and Pr [||= R = 1. Let n be the
(x,g)~/
(a.a)~
maximum margin over all weight vectors classifying the uncorrupted data, and let Fadv {patch (x) l|patch (x) - z|| 5t).
If Selann consists of at least 92 (Eaten 2 + logoog//)) (1/6)) iidd examples drawn from and if Sadv consists of at least Q (Eadv (x~ R² + log (2/6)) i.idd examples drawn from DIh" (x) & t, then we have:
min ||ll| Sy
1
Σ
1 (y (w, < <1>>0
(M-N)SS
In other words, assuming there exists a margin b and a 0-loss classifier, empirical risk minimization of margin-loss with norm constraint fails to find O-loss classifier on sufficiently contaminated training set.
2.3 Memorization Capacity and Backdoor Attacks
The key takeaway from the previous section is that the adversary can force an ERM learner to recover the union of function that looks similar to the true classifier in-distribution inputs and another function of the adversary's is choice. We use this intuition of "learning two classifiers in one" to formalize notion of "excess capacity."
To this end, we define the memorization capacity of class and domain.
Definition 7 (Memorization Capacity). Suppose we are in setting where we are learning hypoth- esis class H over a domain X under distribution
We say we can memorize l irrelevant sets from a family C atop a fixed h" if we can find pairwise disjoint nonempty sets X1,..., Xx. from family of subsets of the domain C. such that for all b E {+1}*. there exists a classifier h E satisfying the below:
For all Xú. we have T((x)) b..
Pr [(((z) 16t 11( 1.
We define mcapx, (h, H, C) to be the maximum number of sets from C we can memorize for fixed h belonging to hypothesis class H. We define mcapx, (h, H) mcapx p (h, H. 1x) to be the maximum number of sets from Bx we can memorize for a fixed h,, where Bx is the family of all non-empty measurable subsets of X. Finally, we define x, (H) supдEи mcapx, (h, H).
5

---

Intuitively, the memorization capacity captures the number of additional irrelevant (with respect to D) sets that can be memorized atop true classifier.
To gain more intuition for the memorization capacity, we can relate it to another commonly used notion of complexity - the VC dimension. Specifically, we have the following lemma.
Lemma 8 ((Appendix Lemma 23)). We have 0 I mcapx, (H) S VC (HL).
Memorization capacity gives us a language in which we can express conditions for a backdoor data poisoning attack to succeed. Specifically, we have the following general result.
Theorem (Nonzero Memorization Capacity Implies Backdoor Attack (Appendix Theorem 24)). Pick target label t E =1. Suppose have hypothesis class H. target function h", domain X, a data distribution D, and a class of patch functions Fadv. Define:
alr))))") = {patch (Supp (D)h + ()) : -patch E Fadv)
Now, suppose that m (h", H. ((a,C(Faa 2 1. Then, there exists a function patch Fadv for which the adversary can draw set Sadu consisting of m Ω (cndy (VC (H) + log (1/6)) iidd samples from DIh" (x) + t such that with probability at least - over the draws of Sadvi the adversary achieves the objectives of Problem regardless of the number of samples the learner draws from 'D for Selean-
In words, the result Theorem 9 states that nonzero memorization capacity with respect to subsets of the images of valid patch functions implies that a backdoor attack exists. More generally, we can show that a memorization capacity of least & implies that the adversary can simultaneously execute k attacks using & different patch functions. In practice, this could amount to, for instance, selecting k different triggers for an image and correlating them with various desired outputs. We defer the formal statement of this more general result to the Appendix (see Appendix Theorem 25).
natural follow-up question to the result of Theorem 9 to ask whether memorization capacity of zero implies that an adversary cannot meet its goals as stated in Problem 2. Theorem 10 answers this affirmatively.
Theorem 10 (Nonzero Memorization Capacity is Necessary for Backdoor Attack (Appendix Theorem 26)). Let C(Faov(h)) (h")) be defined the same as in Theorem Suppose we have a hypothesis class H over domain X, a true classifier lt,, data distribution D, and perturbation class Fadv. If mcapx (h', H, C(Fadv (I) = then the adversary cannot successfully construct a backdoor data poisoning attack per the conditions of Problem 2.
2.3.1 Examples
We now use our notion of memorization capacity to examine the vulnerability of several natural learning problems to backdoor data poisoning attacks.
Example 11 (Overparameterizeed Linear Classifiers (Appendix Example 27)). Recall the result from the previous section, where we took X = Rd,, Ha to be the set of linear classifiers in Rd, and let 'D be a distribution over a radius-AR subset of an s-dimensional subspace We also assume that the true labeler lt achieves margin
If we set Fadv C(Fasu(F"")))) (h²))) 2
ppatch (I:) patch (x) = x 4. 7 IRd), then
we
have
mcapx,p (h', Ha,,C(Fad
Example 12 (Linear Classifiers Over Convex Bodies (Appendix Example 28)). Let H be the set of origin-connaiiimg halfspaces. Fix an origin-containing halfspace h- with weight vector w", Let X' be closed compact convex set, let X = X" {x (w" x²) = 0}, and let D be any probability measure over X that assigns nonzero measure to every l ball of nonzero radius contained in X and satisfies the relation (YD = + Vola(YY) = 0 for all Y C X. Then, mcapx, (h", ; HH) = 0.
Given these examples, is natural to wonder whether memorization capacity can be greater than when the support of 'D is the entire space X. The following example shows this indeed can be the case.
Example 13 (Sign Changes (Appendix Example 29)). Let X = [0. 11. D = Unif (X) and Ha be the class of functions admitting at most k sign-changes. Specifically, Hi consists of functions h for which can find pairwise disjoint, continuous intervals Iı.... 1x41 such that:

---

For all i < for all 1.VV E 15. we have < y.
U 4 =
h(T,) -I((e+1)), [. for all E [R]]
Suppose the learner is learning H. unknown using Has where S d d.2.. 2. For all ht E Hy have mcapx,p (h", Ha) 2 (d-a)/2].
Algorithmic Considerations
We now turn our attention to computational issues relevant to backdoor data poisoning attacks. Throughout the rest of this section, define the adversarial loss:
Favlh (h, =
TTpptth (s)) # w}}
sup
(x.
Fatch
In a slight overload notation, L (a*()h) denote the robust loss class of H with the perturbation sets generated by Fadv )
1 { (patch (z)) $ #u} h HH) }
CN ( (z, +
sup Pat
Then, assume that VC (c% (L))))))) is finite?. Finally, assume that the perturbation set Fadv is the same as that consistent with the ground-truth classifier ht In other words, once h is selected, then reveal both the learner and the adversary the sets Fadv "ht) thus, the learner equates Fadv and Fadu (h"). Hence, although h' is not known to the learner, Faav(h") is. As an example of natural scenario which such an assumption holds, consider the case where h is some large-margey classifier and Fadv consists of short additive perturbations. This subsumes the setting where h" is some image classifier and Fadv consists of test-time adversarial perturbations which don't 't impact the true classifications of the source images.
3.1 Certifying the Existence of Backdoors
The assumption that Fadv (sov(h)) gives the learner enough information to minimize (Fuw(t)) (h, (h, S) on a finite training S over h e H*: the assumption that VC (C# (E% oo yields that the learner recovers classifier that has low robust loss as per uniform convergence. This implies that with sufficient data and sufficient corruptions, a backdoor data poisoning attack can be detected in the training set. We formalize this below.
Theorem 14 (Certifying Backdoor Existence (Appendix Theorem 30)). Suppose that the learner can calculate and minimize:
{Tipptcc (+)) # w
Cas (h,
E (c.y)~s
sup Pat
over a finite set S and H.
If the VC dimension of the loss class CH Fam(h)) finite, then there exists an algorithm using O (=-2 (VC (FFa,(hh)) + log (1/))) samples that allows the learner to defeat the adversary through learning a backdoor- classifier or by rejecting the training set as being corrupted, with probability
I is shown in [21] there exist classes corresponding adversarial loss classes Craa(h)) for which VC (H) but VC (C (h=))) have VC (H), VC (cr)) < oo; for example, the case of lincar classifiers in I& and for closed, convex, origin-symmetrii, additive perturbation sets, have VC (H), VC (4) (())))))) < d 1 (see [26] [14]). Howeeer, minimizing (Fx(())) might be computationally intractable in several scenarios.
Nonetheless. there variety natural scenarios in which
7

---

See Algorithm A.1 1 in the Appendix for the pseudocode of an algorithm witnessing the statement of Theorem 14.
Our result fleshes out and validates the approach implied by [31], where the authors use data augmentation to robustly learn in the presence of backdoors. Specifically, in the event that adversarial training fails to converge to something reasonable or converges a classifier with high robust loss, a practitioner can then manually inspect the dataset for corruptions or apply some data sanitization algorithm.
3.1.1 Numerical Trials
To exemplify such a workflow, we implement adversarial training in a backdoor data poisoning setting. Specifically, we select target label, inject a varying fraction of poisoned examples into the MNIST dataset (see [2]), and estimate the robust training and test loss for each choice of a. Our results demonstrate that in this setting, the training robust loss indeed increases with the fraction of corrupted data a; moreover, the classifiers obtained with low training robust loss enjoy a low test-time robust loss. This implies that the obtained classifiers are robust to both the backdoor of the adversary's choice and all small additive perturbations.
For more detailed description of our methodology, setup, and results, please Appendix Section B.
3.2 Filtering versus Generalization
We now show that two related problems we call backdoor filtering and robust generalization are nearly statistically equivalent; computational equivalence follows if there exists an efficient algorithm to minimize (h*) on finite training set. We first define these two problems below (Problems 15 and 16).
Problem 15 (Backdoor Filtering). Given training set S = Sclean U Sadv such that |Sceeall 2 Q (poly (c-1, (1/a), VC (F))), return subset S' S S such that the solution to the optimization h == a (h, S") satisfies Cran(h)) D) S Sclean with probability 1-6.
Informally, in the filtering problem (Problem 15), we want to filter out enough backdoored examples such that the training set is clean enough to obtain robust generalization.
Problem 16 (Robust Generalization). Given a training set S = Sdean U Sadv such that |Scean| 2
Ω (poly (e-1 -1 log (4/6), VC (L)))(())))) return classifier h satisfies F h,, D S Eclean with probability 8.
In other words, in Problem 16, want learn classifier robust to all possible backdoors.
In the following results (Theorems 17 and 18), we show that Problems 15 and 16 are statistically equivalent, in that solution for one implies solution for the other. Specifically, below.
write the
Theorem 17 (Filtering Implies Generalization (Appendix Theorem 31)). Let S 1/a and Eclean S 1/10.
Suppose we have training sei S Ω ( (VC (Loaa(h-)) + log (1/8)) and [Sadvl S (ISadul + |-SStean) ))- If there exists an algorithm that given S can find a subset S' -S'lean U'adv satisfying /Samn///Scos 2 1- Eclean and minneH Fooithe (h, S¹) S Eclean then there exists algorithm such that given S returns function h satisfying ( D) S Edean with probability 6-6. 6.
Selean U Sadv such that |Sclean|
See Algorithm A.2 in the Appendix for the pseudocode of an algorithm witnessing the theorem statement.
Theorem 18 (Generalization Implies Filtering (Appendix Theorem 33)). Sel Eclean 2/10 and < 1/6.
there exists an algorithm that, given most a 2o fraction of outliers in the training set, can output hypothesis satisfying (r (h, D) S Eckan with probability over the draw of the training set, then there exists algorithm that given a training set S Sclean U Sadv satisfying

---

|Sclean| 2 1 (E (VC (CTo + log (4/5)) outputs a subset S' C S with the property that (h, S") D) X Eclean with probability 1 - 76.
(k)) hx
See Algorithm A.3 in the Appendix for the pseudocode of an algorithm witnessing Theorem 18. Note that there is a factor-2 separation between the values of used in the filtering and generalizing routines above; this is a limitation of our current analysis.
The upshot of Theorems 17 and 18 is that in order to obtain classifier robust backdoor perturbations at test-time, it is statistically necessary and sufficient to design an algorithm that can filter sufficiently many outliers to where directly minimizing the robust loss (e.g., adversarial training) yields generalizing classifier. Furthermore, computational equivalence holds in the case where minimizing the robust loss on the training set can be done efficiently (such as in the case of linear separators with closed, convex, bounded, origin-symmetric perturbation sets see [26]). This may guide future work on the backdoor- robust generalization problem, as equivalent focus on the conceptually simpler filtering problem.
Related Works
Existing work regarding backdoor data poisoning can be loosely broken into two categories. For a more general survey of backdoor attacks, please see the work of [25].
Attacks To the best of our knowledge, the first work to empirically demonstrate the existence of backdoor poisoning attacks is that of [10]. The authors consider a setting similar to ours where the attacker can inject small number of impercetibly corrupted examples labeled as target label. The attacker can ensure that the classifier's s performance is impacted only on watermarked test examples; in particular, the classifier performs well on in-distribution test data. Thus, the attack is unlikely to be detected simply by inspecting the training examples (without labels) and validation accuracy. The work of [9] and [19] explores similar setting.
The work of [30] discusses theoretical aspects of backdoor poisoning attacks in a federated learning scenario. Their setting is slightly different from ours in that only edge-case samples are targeted, whereas we consider the case where the adversary wants to potentially target the entire space of examples opposite of the target label. The authors show that their framework, the existence of test-time adversarial perturbations implies the existence of edge-case backdoor attacks and that detecting backdoors is computationally intractable.
Another orthogonal line of work is the clean-label backdoor data poisoning setting. Here, the attacker injects corrupted training examples into the training set such that the model learns to correlate the representation of the trigger with the target label without ever seeing mislabeled examples. The work of [27] and [23] give empirically successful constructions of such an attack. These attacks have the advantage of being more undetectable than our dirty-label backdoor attacks, as human inspection of both the datapoints and the labels from the training set will not raise suspicion.
Finally, note that one can think of backdoor attacks exploiting spurious non-robust features; the fact that machine learning models make predictions on the basis of such features has been well-studied (e.g. see [6]. [20]. [32]).
Defenses Although there a variety of empirical defenses against backdoor attacks with varying success rates, we draw attention to two defenses that are theoretically motivated and that most closely apply to the setting we consider in work.
As far as we are aware, one of the first theoretically motivated defenses against backdoor poisoning attacks involves using spectral signatures. Spectral signatures ([17)) relies on the fact that outliers necessarily corrupt higher-order moments of the empirical distribution, especially in the feature space. Thus, to find outliers, one can estimate class means and covariances and filter the points most correlated with high-variance projections of the empirical distribution in the feature space. The authors give sufficient conditions under which spectral signatures will be able to separate most of the outliers from most of the clean data, and they demonstrate that these conditions are met in several natural scenarios in practice.
Another defense with some provable backing is Iterative Trimmed Loss Minimization (ITLM), which was first used against backdoor attacks by [22]. ITLM is an algorithmic framework motivated by the idea that the value of the loss function on the set of clean points may be lower than that the set

---

of corrupted points. Thus, an ITLM-based procedure selects a low-loss subset of the training data and performs a model update step on this subset. This alternating minimization is repeated until the model loss is sufficiently small. The heuristic behind ITLM holds in practice, as per the evaluations from [22].
Memorization of Training Data The work of [8] and [24] discuss the ability of neural networks to memorize their training data. Specifically, the work of [8] empirically discusses how memorization plays into the learning dynamics of neural networks via fitting random labels. The work of [24] experimentally validates the "long tail theory", which posits that data distributions in practice tend to have large fraction of their mass allocated to "atypical" examples; thus, the memorization of these rare examples is actually necessary for generalization.
Our notion of memorization is different in that we consider excess capacity top of the learning problem at hand. In other words, we require that there exist a classifier in the hypothesis class that behaves correctly on on-distribution data in addition to memorizing specially curated off-distribution data.
5 Conclusions and Future Work
Conclusions We gave a framework under which backdoor data poisoning attacks can be studied. We then showed that, under this framework, formal notion of excess capacity present in the learning problem is necessary and sufficient for the existence of a backdoor attack. Finally, in the algorithmic setting, we showed that under certain assumptions, adversarial training can detect the presence of backdoors and that filtering backdoors from a training set is equivalent to learning a backdoor-robust classifier.
Future Work There several interesting problems directly connected to our work for which progress would yield a better understanding of backdoor attacks. Perhaps the most important is to find problems for which there simultaneously exist efficient backdoor filtering algorithms and efficient adversarial training algorithms. It would also be illuminating to determine the extent to which adversarial training detects backdoor attacks in deep learning'. Finally, we believe that our notion of memorization capacity can find applications beyond the scope of this work. would be particularly interesting to see if memorization capacity has applications to explaining robustness or lack thereof to test-time adversarial perturbations.
Societal Impacts Defenses against backdoor attacks may impede the functionality of several applications. Most notably, the Fawkes system (see [28]) relies on a backdoor data poisoning attack to preserve its users' privacy, and such system could be compromised if were known how to reliably defend against backdoor data poisoning attacks in such setting.
Acknowledgments This work was supported in part by the National Science Foundation under grant CCF-181501 and by the Defense Advanced Research Projects Agency under cooperative agreement HR001 12020003. The views expressed in this work do not necessarily reflect the position or the policy of the Government and no official endorsement should be inferred. Approved for public release; distribution is unlimited.
NSM thanks Surbhi Goel for suggesting the experiments run in the paper.
References
[1] Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, Mar. 2004.
[2] Yann LeCun and Corinna Cortes. "MNIST handwritten digit database". In: (2010). URL.: http:://yan/ lecun. com/ com/exdb/ /n st..
[3] Amit Daniely, Sivan Sabato, and Shai Shalev Shwartz. "Multiclass Learning Approaches: A Theoretical Comparison with Implications". In: (May 2012). arXiv: 1205. 6432 [cs.LG].
[4] Moritz Hardt and Ankur Moitra. Algorithms and Hardness for Robust Subspace Recovery. Nov. 2012. arXiv: 1211. 1041 [cs .C].
'This scenario automatically covered by our result since the generalization of neural networks unseen data cannot be explained by traditional uniform convergence and VC-dimension arguments (see [12] and [7]).
10

---

[5] Shai
and Shai Ben-David, Understanding Machine Learning: From Theory to Algorithms. en. Cambridge University Press, May 2014.
[6] Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. ""Why Should I Trust You?": Explaining the Predictions of Any Classifier" In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. KDD '16. San Francisco, California, USA: Association for Computing Machinery, Aug. 2016, pp. 1135-1144.
[7] Chiyuan Zhang al. "Understanding deep learning requires rethinking generalization". In:
(Nov. 2016). aiv: 1 1611. 03530 [G).
[8] Devansh Arpit et al. "A Closer Look at Memorization in Deep Networks". In: Proceedings of the 34th International Conference on Machine Learning. Ed. by Doina Precup and Yee Whye Teh. Vol. 70. Proceedings of Machine Learning Research. PMLR, 2017, pp. 233-
[9] Xinyun Chen et al. Targeted Backdoor Attacks on Deep Learning Systems Using Data Poison-
ing. 2017. arXiv: 1712. 05526 [cs. CRS.
[10] Tianyu Gu, Brendan Dolan-Gavitt, and Siddharth Garg. "BadNets: Identifying Vulnerabilities in the Machine Learning Model Supply Chain". In: (Aug. 2017). arXiv: 1 1708 06733
CR]
[11] Aleksander Madry et al. Towards Deep Learning Models Resistant to Adversarial Attacks.
June 2017. arXiv: 1 1066.066060 06083 [stat. ML.].
[12] Behnam Neyshabur et al. "Exploring Generalization in Deep Learning". In: Advances in Neural Information Processing Systems. Ed. by Guyon et Vol. 30. Curran Associates, Inc., 2017.
[13] Yossi Adi et al. "Turning your weakness into strength: watermarking deep neural networks by backdooring". In: Proceedings of the 27th USENIX Conference on Security Symposium. SEC' 18. Baltimore, MD, USA: USENIX Association, Aug. 2018, pp. 1615-1631.
[14] Daniel Cullina, Arjun Nitin Bhagoji, and Prateek Mittal. "PAC-learning in the presence of adversaries". In: Advances in Neural Information Processing Systems. Ed. by S Bengio et al. Vol. 31. Curran Associates, Inc., 2018.
[15] Pang Wei Koh, Jacob Steinhardt, and Percy Liang. Stronger Data Poisoning Attacks Break Data Sanitization Defenses. Nov. 2018. arXiv: 1811. 00741 [stat .ML].
[16] Ali Shafahi al. Poison Frogs! Targeted Clean-Label Poisoning Attacks on Neural Networks. Apr. 2018. arXiv: 1 1804 4 00 7 92 [CS.LG]
[17] Brandon Tran, Jerry Li, and Aleksander Madry. "Spectral Signatures in Backdoor Attacks", In: Advances Neural Information Processing Systems. Ed. by S Bengio al. Vol. 31, Curran Associates, Inc., 2018
[18] Roman Vershynin. Tfigh-Dimensional Probability: An Introduction with Applications in Data Science. en. Cambridge University Press, Sept. 2018
[19] Tianyu Gu et al. "BadNets: Evaluating Backdooring Attacks on Deep Neural Networks". In: IEEE Access 7 (2019), pp. 47230-47244,
[20] Andrew Ilyas et al. "Adversarial Examples Are Not Bugs, They Are Features", In: Advances in Neurul Information Processing Systems. Ed. by H Wallach et al. Vol. 32. Curran Associates, Inc., 2019.
[21] Omar Montasser, Steve Hanneke, and Nathan Srebro. "VC Classes are Adversarially Robustly Learnable, but Only Improperly" In: Proceedings of the Thirty-Second Conference Learning Theory. Ed. by Alina Beygelzimer and Daniel Hsu. Vol. 99, Proceedings of Machine Learning Research. Phoenix, USA: PMLR, 2019, pp. 2512-2530.
[22] Yanyao Shen and Sujay Sanghavi. "Learning with Bad Training Data via Iterative Trimmed Loss Minimization". In: Proceedings of the 36th International Conference on Machine Learn- ing. Ed. by Kamalika Chaudhuri and Ruslan Salakhutdinov. Vol. 97. Proceedings of Machine Learning Research. PMLR, 2019, pp. 5739-5748.
[23] Alexander Turner, Dimitris Tsipras, and Aleksander Madry. Label-Consistent Backdoor Attacks. Dec. 2019. arXiv: 1912. 02771 [etattMM...
[24] Vitaly Feldman and Chiyuan Zhang. "What Neural Networks Memorize and Why: Discovering the Long Tail via Influence Estimation". In: (Aug. 2020). arXiv: 2008 03703 [cs LG].
[25] Yiming Li et al. Backdoor Learning: A Survey. July 2020. arXiv: 2007. 08745 (cs.CR].
11

---

[26]
Omar Montasser et al. "Efficienlly Learning Adversarially Robust Halfspaces with Noise". In: Proceedings of the 37th International Conference on Machine Learning. Ed. by Hal Daumé li and Aarti Singh. Vol. 119. Proceedings of Machine Learning Research. PMLR, 2020,
pp. 7010-7021.
[27] Aniruddha Saha, Akshayvarun Subramanya, and Hamed Pirsiavash. "Hidden Trigger Backdoor Attacks". In: AAA/ 34.07 (Apr. 2020), pp- 11957-11965.
[28] S Shan al. "Fawkes: Protecting privacy against unauthorized deep learning models". In: Proceedings of the Twenty-Ninth USENIX Security Symposium. usenix.org, 2020.
[29] Loc Truong et al. Systemutic Evaluation of Backdoor Data Poisoning Attacks Image Classifiers. Apr. 2020. arXiv: 2004. 11514 (cs.CV].
[30] Hongyi Wang et al. "Attack the Tails: Yes, You Really Can Backdoor Federated Learning". In: Advances in Neural Information Processing Systems. Ed. by H. Larochelle al. Vol. 33. Cur- ran Associates, Inc., 2020, pp. 16070-16084, URL: https: http://poeeeeen...eeee/e/.o.s neur ips. cc/paper/2020 weeeeeeebeei.e weeee/fffaeeeeeee 414444 wttp://99ffffffffffffff
Paper. [31] Eitan Borgnia et al. "Strong Data Augmentation Sanitizes Poisoning and Backdoor Attacks Without an Accuracy Tradeoff". In: ICASSP 2021 202/ IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). June 2021, pp. 3855-3859.
[32] Kai Yuanqing Xiao et al. "Noise or Signal: The Role Image Backgrounds in Object Recog- nition". In: International Conference Learning Representations. 2021. URL: https: / oppnrevv ew, n d=g 3 xY7.I..
12


Reviews:
[{"review_id": "q_DHLT369AD", "reviewer": "Reviewer_dePm", "summary": "The paper gives a variety of backdoor-related theoretical results. In particular it, \n1. gives a theoretical framework for discussing backdoor poisoning attacks,\n2. shows that the attacker does not need to know the true data distribution to launch an attack against an ERM learner,\n3. introduces _memorization capacity_, which measures the amount of off-distribution data a learner can memorize, and shows that nonzero memorization capacity is both necessary and sufficient for the existence of a backdoor attack\n4. (the attack constructed in 4. can succeed with limited poisoned data regardless of how much clean data there is),\n5. under assumption of finite VC-dimension, shows that adversarial training can be used to detect backdoor attacks, and\n6. under the same assumption, shows that the problem of learning a backdoor-resistant model is equivalent to the problem of filtering poisoned data from the dataset.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "The paper multiple noteworthy theoretical results relating to backdoor poisoning attacks. \n\nTypos:\n287: Assumption on VC-dimension is incomplete.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "They have.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "nE2klS2A3Me", "reviewer": "Reviewer_bwBK", "summary": "The authors propose a theoretical study on the robustness of binary classifiers against backdoors. To this end, they provide a theoretical framework and define a measure to assess classifiers' memorization capacity. This formulation allows the authors to demonstrate the existence of backdoors in some settings and explain why adversarial training reduces the vulnerability to backdoors. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "The main contribution of this work is the framework devised by the authors to explain some aspects underlying the success or failure of backdoor attacks. While related work in the area of backdoor attacks is well acknowledged and discussed, the authors should better position this work also with respect to other theoretical analyses related to the memorization of training samples and to the relationship between over-parameterized models and their ability to fit random labels. In particular, from this manuscript, the memorization of the training points seems a concept discovered and defined by the authors. However, this is not the case, as previous work has defined this concept [a] and provided a way to estimate training point memorization [b]. The authors should also clarify that it is already known that robust training increases the robustness against backdoors [c]. \nLast but not least, it would be really a plus if the authors could somewhat connect their work to these papers:\n- https://arxiv.org/abs/1611.03530,\n- https://arxiv.org/abs/2105.14368 (Sect. 5.2 and reference [10]).\n\nNotwithstanding, this manuscript has some novelty. To my knowledge, the concept of memorization capacity has never been related before to the vulnerability against backdoors, and the validity of adversarial training as a defense against this attack was empirically shown but not theoretically explained. The formulation devised by the authors may be adapted in the future to understand better other phenomena related to machine learning robustness against attacks. \n\nI appreciated the authors' effort to explain the proposed formulation clearly. To be a theoretical paper is pleasant to read and easy to understand, even though a bit dense in some parts. I would also recommend the authors to try to better emphasize and recap (e.g., in the conclusions) constructive ways in which their formulation can be adopted to improve current algorithms/best practices.\n\nOverall, I think this work provides a fair contribution to the state of the art.\n\nMinor comments:\n\nAs a minor comment, the first work introducing backdoor attacks is not [6] but:\n- T. Gu, B. Dolan-Gavitt, and S. Garg. Badnets: Identifying vulnerabilities in the machine learning model supply chain. In NIPS Workshop on Machine Learning and Computer Security, abs/1708.06733, 2017.\n\n\nReferences\n\na) Arpit, Devansh, Stanisław Jastrzębski, Nicolas Ballas, David Krueger, Emmanuel Bengio, Maxinder S. Kanwal, Tegan Maharaj, et al. ‘A Closer Look at Memorization in Deep Networks’. In Proceedings of the 34th International Conference on Machine Learning - Volume 70, 233–42. ICML'177. Sydney, NSW, Australia: JMLR.org, 2017.\n\nb) Feldman, Vitaly, and Chiyuan Zhang.\" What Neural Networks Memorize and Why: Discovering the Long Tail via Influence Estimation\". In Advances in Neural Information Processing Systems, edited by H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, 33:2881–91. Curran Associates, Inc., 2020. https://proceedings.neurips.cc/paper/2020/file/1e14bfe2714193e7af5abc64ecbd6b46-Paper.pdf.\n\nc) Borgnia, Eitan, Valeriia Cherepanova, Liam Fowl, Amin Ghiasi, Jonas Geiping, Micah Goldblum, Tom Goldstein, and Arjun Gupta. 'Strong Data Augmentation Sanitizes Poisoning and Backdoor Attacks Without an Accuracy Tradeoff'. ArXiv:2011.09527 [Cs], 18 November 2020. http://arxiv.org/abs/2011.09527.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Potentially-negative societal impact and limitations have been discussed.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "4h"}, "extra_text": {}}, {"review_id": "_Aiv7_aq7fo", "reviewer": "Reviewer_7uMB", "summary": "The paper offers a theoretical framework to analyze and understand backdoor attacks. They define a notion of memorization capacity to characterize vulnerability of the learning problem to backdoor attacks. Under this framework they give examples of learning problems where explicit backdoors can be constructed easily and problems which are intrinsically robust to backdoors. Further, they also show that under certain assumptions, backdoor filtering and robust generalization are nearly equivalent. Which suggests, it is sufficient to design backdoor filtering algorithms. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "Recently, lots of works have shown vulnerability of deep neural networks to backdoor attacks. However most of these works have been empirical in nature and based on designing/ detecting the attack and proper theoretical understanding of backdoor attacks is lacking. This paper tries to fill this gap by offering a nice theoretical framework to understand whether the given learning setting is vulnerable to backdoor attacks or not and how we can understand it quantitatively. Their notion of memorization capacity and results are definitely valuable in this context.  Although they have nice set of results, I find this paper lacking in clarity. Intuitions and proof sketches are expected at least for the main theorems in the main paper. It would have been better, if the paper elaborated more on the connection between excess capacity and vulnerability to backdoors. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "One key limitation is the current work is focused heavily on overparameterized linear classifiers, which are a good starting point. Would have been nice to generalize these results to non-linear/ deep net classifiers. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "AC52nr3Vm4", "reviewer": "Reviewer_jukN", "summary": "This work proposes a theoretical framework to draw connections between several phenomena in machine learning observed empirically but never adequately understood- the relationship between excess model capacity, perturbation robustness, and backdoor poisoning. They show how under specific settings, adversarial training can detect backdoored data or recover a classifier robust to the backdoors at the very least. Similarly, they show how learning a backdoor-robust classifier is equivalent to pruning corrupted train data. They further demonstrate the applicability of their theorems on the MNIST dataset.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "## Positive Feedback\n\n1. This work has instrumental theoretical contributions: in terms of findings, theorems, the framework itself, and equivalence between robustness and susceptibility to poisoning.\n\n2. Problem 2  has been formulated well, with an easy-to-follow breakdown of the adversary's goals. Having equivalent text explanations next to formulae is very helpful. \n\n3. The fact that results from the proposed framework align with empirical observations in this field by other authors reinforce this work's soundness and helps better understand the reason behind those phenomena. \n\n---\n\n## Criticism\n\n1. Empirical results help show that the proposed theory extends to implementation (which can sometimes lead to significant drops because of stochasticity in model training and constants in equations). Given that the authors did perform such experiments (Supplementary material), it would be great to have a small sub-section summarizing those empirical results.\n\n2. Line 208: \"..a 0-loss classifier\" . Would this result hold if the focus were to find some $\\epsilon$-loss classifier for some reasonably small $\\epsilon$? I am a bit concerned about this part since, in a realistic training scenario, the model training would rarely find a 0-loss set of parameters (and even if it could, would never want 0 loss on training data).\n\n---\n\n## Minor comments\n\n1. Line 1: \"...supervised learning\" is not a requirement for backdoor data poisoning - the setting can also be unsupervised or semi-supervised. Lines 1-7: Do not need such an extended portion (that too in the abstract) dedicated to this definition. In general, the Abstract could use a rewrite - it is too long right now and captures unnecessary details.\n\n2. Lines 26-28: can skip, is pretty common knowledge in this field by now.\n\n3. Line 3: \"...(nearly) 0 error\" not sure I agree with this - wouldn't having a training error too low be akin to overfitting, which is something machine-learning algorithms actively avoid.\n\n4. Section 1.2: It is nice to see that the authors include this, but it would probably be best to shift it to later in the paper.\n\n5. Theorem 17 uses $\\alpha\\leq\\frac{1}{3}$ and Theorem 18 uses $\\alpha\\leq\\frac{1}{6}$. My understanding is that the $2\\alpha$ fraction from Theorem 18 connects to Theorem 17? If yes, it might be worthwhile to write them accordingly before combing the two Equations to imply equivalence because, at the moment, both Equations have different constraints.\n\n\n## Update\n\nIncreased confidence to 4", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors could certainly extend their empirical evaluation to more complex datasets in the near future. Still, I do not see any obvious limitations in its current state except the ones already stated in their assumptions. Nonetheless, it would be interesting how this could be utilized to perform \"adversarial training\" indirectly - especially for text-related tasks.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers agree that this is an important result filling in the gap of theoretically understanding backdoor attacks. 
Decision: Accept (Spotlight)