summaries: 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. 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.  The paper gives a variety of backdoor-related theoretical results. In particular it,  1. gives a theoretical framework for discussing backdoor poisoning attacks, 2. shows that the attacker does not need to know the true data distribution to launch an attack against an ERM learner, 3. 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 4. (the attack constructed in 4. can succeed with limited poisoned data regardless of how much clean data there is), 5. under assumption of finite VC-dimension, shows that adversarial training can be used to detect backdoor attacks, and 6. 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.  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. 
abstractText: 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.
authors.name: Naren Sarayu Manoj
authors.name: Avrim Blum
references.authors: Stephen Boyd Lieven Vandenberghe
references.title: Convex Optimization
references.authors: Yann LeCun Corinna Cortes
references.title: MNIST handwritten digit database
references.authors: Amit Daniely Sivan Sabato Shai Shalev Shwartz
references.title: Multiclass Learning Approaches: A Theoretical Comparison with Implications
references.authors: Moritz Hardt Ankur Moitra
references.title: Algorithms and Hardness for Robust Subspace Recovery
references.authors: Shai Shalev-Shwartz Shai Ben-David
references.title: Understanding Machine Learning: From Theory to Algorithms. en
references.authors: Marco Tulio Ribeiro Sameer Singh Carlos Guestrin
references.title: Why Should I Trust You?”: Explaining the Predictions of Any Classifier
references.venue: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. KDD ’16
references.authors: Chiyuan Zhang
references.title: Understanding deep learning requires rethinking generalization
references.venue: (Nov
references.authors: Devansh Arpit
references.title: A Closer Look at Memorization in Deep Networks
references.venue: Proceedings of the 34th International Conference on Machine Learning. Ed. by Doina Precup and Yee Whye Teh
references.authors: Xinyun Chen
references.title: Targeted Backdoor Attacks on Deep Learning Systems Using Data Poisoning
references.authors: Tianyu Gu Brendan Dolan-Gavitt Siddharth Garg
references.title: BadNets: Identifying Vulnerabilities in the Machine Learning Model Supply Chain
references.venue: (Aug
references.authors: Aleksander Madry
references.title: Towards Deep Learning Models Resistant to Adversarial Attacks
references.authors: Behnam Neyshabur
references.title: Exploring Generalization in Deep Learning
references.venue: Advances in Neural Information Processing Systems. Ed. by I Guyon et al
references.authors: Yossi Adi
references.title: Turning your weakness into a strength: watermarking deep neural networks by backdooring
references.venue: Proceedings of the 27th USENIX Conference on Security Symposium. SEC’18
references.authors: Daniel Cullina Arjun Nitin Bhagoji Prateek Mittal
references.title: PAC-learning in the presence of adversaries
references.venue: Advances in Neural Information Processing Systems. Ed. by S Bengio et al
references.authors: Pang Wei Koh Jacob Steinhardt Percy Liang
references.title: Stronger Data Poisoning Attacks Break Data Sanitization Defenses
references.authors: Ali Shafahi
references.title: Poison Frogs! Targeted Clean-Label Poisoning
references.venue: Attacks on Neural Networks. Apr
references.authors: Brandon Tran Jerry Li Aleksander Madry
references.title: Spectral Signatures in Backdoor Attacks
references.venue: Advances in Neural Information Processing Systems. Ed. by S Bengio et al
references.authors: Roman Vershynin
references.title: High-Dimensional Probability: An Introduction with Applications in Data Science. en
references.authors: Tianyu Gu
references.title: BadNets: Evaluating Backdooring Attacks on Deep Neural Networks
references.venue: IEEE Access
references.authors: Andrew Ilyas
references.title: Adversarial Examples Are Not Bugs, They Are Features
references.venue: Advances in Neural Information Processing Systems. Ed. by H Wallach et al
references.authors: Omar Montasser Steve Hanneke Nathan Srebro
references.title: VC Classes are Adversarially Robustly Learnable, but Only Improperly
references.venue: Proceedings of the Thirty-Second Conference on Learning Theory. Ed. by Alina Beygelzimer and Daniel Hsu
references.authors: Yanyao Shen Sujay Sanghavi
references.title: Learning with Bad Training Data via Iterative Trimmed Loss Minimization
references.venue: Proceedings of the 36th International Conference on Machine Learning. Ed. by Kamalika Chaudhuri and Ruslan Salakhutdinov
references.authors: Alexander Turner Dimitris Tsipras Aleksander Madry
references.title: Label-Consistent Backdoor Attacks
references.authors: Vitaly Feldman Chiyuan Zhang
references.title: What Neural Networks Memorize and Why: Discovering the Long Tail via Influence Estimation
references.venue: (Aug
references.authors: Yiming Li
references.title: Backdoor Learning: A Survey
references.venue: July 2020. arXiv: 2007.08745 [cs.CR]
references.authors: Omar Montasser
references.title: Efficiently Learning Adversarially Robust Halfspaces with Noise
references.venue: Proceedings of the 37th International Conference on Machine Learning. Ed. by Hal Daumé Iii and Aarti Singh
references.authors: Aniruddha Saha Akshayvarun Subramanya Hamed Pirsiavash
references.title: Hidden Trigger Backdoor Attacks
references.venue: en. In: AAAI
references.authors: S Shan
references.title: Fawkes: Protecting privacy against unauthorized deep learning models
references.venue: Proceedings of the Twenty-Ninth USENIX Security Symposium. usenix.org,
references.authors: Loc Truong
references.title: Systematic Evaluation of Backdoor Data Poisoning
references.venue: Attacks on Image Classifiers. Apr
references.authors: Hongyi Wang
references.title: Attack of the Tails: Yes, You Really Can Backdoor Federated Learning
references.venue: Advances in Neural Information Processing Systems. Ed. by H. Larochelle et al. Vol. 33. Curran Associates, Inc.,
references.authors: Eitan Borgnia
references.title: Strong Data Augmentation Sanitizes Poisoning and Backdoor Attacks Without an Accuracy Tradeoff
references.venue: IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)
references.authors: Kai Yuanqing Xiao
references.title: Noise or Signal: The Role of Image Backgrounds in Object Recognition
references.venue: In: International Conference on Learning Representations
sections.text: 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.
sections.heading: 1 Introduction
sections.text: As deep learning becomes more pervasive in various applications, its safety becomes paramount. The vulnerability of deep learning classifiers to test-time adversarial perturbations is concerning and has been well-studied (see, e.g., [11], [21]).
  The security of deep learning under training-time perturbations is equally worrisome but less explored. Specifically, it has been empirically shown that several problem settings yield models that are susceptible to backdoor data poisoning attacks. Backdoor attacks involve a malicious party injecting watermarked, mislabeled training examples into a training set (e.g. [13], [29], [9], [30], [27], [17]). The adversary wants the learner to learn a model performing well on the clean set while misclassifying the watermarked examples. Hence, unlike other malicious noise models, the attacker wants to impact the 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 error on clean, unseen test data.
  For instance, consider a learning problem wherein a 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 a small, unnoticeable watermark
  35th Conference on Neural Information Processing Systems (NeurIPS 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, a 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 as 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 a 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 of urgency. Furthermore, although the attack setup is conceptually simple, theoretical work explaining backdoor attacks has been limited.
sections.heading: 1.1 Main Contributions
sections.text: As a 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 a quantity we call memorization capacity that depends on the data domain, data distribution, hypothesis class, and set of valid perturbations. Intuitively, memorization capacity captures the extent to which a learner can 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 sufficiently 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.
  Organization The rest of this paper is organized as follows. In Section 2, we define our framework, give a warm-up construction of an attack, define our notion of excess capacity, and use 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.
  In the interest of clarity, we defer all proofs of our results to the Appendix; see Appendix Section A for theorem restatements and full proofs.
sections.heading: 2 Backdoor Attacks and Memorization
sections.heading: 2.1 Problem Setting
sections.text: In this section, we introduce a general framework that captures the backdoor data poisoning attack problem in a binary classification setting.
  Notation Let [k] denote the set {i ∈ Z : 1 ≤ i ≤ k}. Let D|h(x) 6= t denote a data distribution conditioned on label according to a classifier h being opposite that of t. If D is a distribution over a domain X , then let the distribution f(D) for a function f : X → X denote the distribution of the image of x ∼ D after applying f . Take z ∼ S for a nonrandom set S as shorthand for z ∼ Unif (S). If D is a distribution over some domain X , then let µD(X) denote the measure of a measurable
  subset X ⊆ X under D. Finally, for a distribution D, let Dm 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 distributionD. Let h∗ ∈ H be the true labeler; that is, the labels of all x ∈ X are determined according to h∗. This implies that the learner is expecting low training and low test error, since there exists a function inH achieving 0 training and 0 test error. Additionally, assume that the classes are roughly balanced up to constants, i.e., assume that Pr
  x∼D [h∗(x) = 1] ∈ [1/50, 49/50]. Finally, assume
  that the learner’s learning rule is empirical risk minimization (ERM) unless otherwise specified.
  We now define a notion of a trigger or patch. The key property of a trigger or a patch is that while it 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 h∗ if for all x ∈ X , we have h∗(patch (x)) = h∗(x). A patch function is 1 − β consistent with h∗ on D if we have Pr x∼D
  [h∗(patch (x)) = h∗(x)] = 1− β. Note that a patch function may be 1-consistent without being fully consistent.
  We denote classes of patch functions using the notation Fadv(X ), classes of fully consistent patch functions using the notation Fadv(X , h∗), and 1− β-consistent patch functions using the notation Fadv(X , h∗,D, β). We assume that every patch class Fadv contains the identity function.1
  For example, consider the scenario where H is the class of linear separators in Rd and let Fadv = { patch (x) : patch (x) = x+ η, η ∈ Rd } ; in words, Fadv consists of additive attacks. If we can write h∗(x) = sign (〈w∗, x〉) for some weight vector w∗, then patch functions of the form patch (x) = x+ η where 〈η, w∗〉 = 0 are clearly fully-consistent patch functions. Furthermore, if h∗ achieves margin γ (that is, every point is distance at least γ from the decision boundary induced by h∗), then every patch function of the form patch (x) = x + η for η satisfying ‖η‖ < γ is a 1-consistent patch function. This is because h∗(x + η) = 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 , a data distribution D, a true labeler h∗, a target label t, and a class of patch functions Fadv(X , h∗,D, β) are selected. The adversary is given X , D, h∗, and Fadv(X , h∗,D, β). The learner is given X , has sample access to D, and is given Fadv(X , h∗,D, β). At a 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 2 (Adversary’s Goal). Given a true classifier h∗, attack success rate 1− εadv, and failure probability δ, select a target label t, a patch function from Fadv(h∗), and a cardinality m and resulting set Sadv ∼ patch (D|h∗(x) 6= t)m with labels replaced by t such that:
  • Every example in Sadv is of the form (patch (x) , t), and we have h∗(patch (x)) 6= t; that is, the examples are labeled as the target label, which is the opposite of their true labels.
  • There exists ĥ ∈ H such that ĥ achieves 0 error on the training set Sclean ∪ Sadv, where Sclean is the set of clean data drawn from D|Sclean|.
  • For all choices of the cardinality of Sclean, with probability 1− δ over draws of a clean set Sclean from D, the set S = Sclean ∪Sadv leads to a learner using ERM outputting a classifier ĥ satisfying:
  Pr (x,y)∼D|h∗(x)6=t
  [ ĥ(patch (x)) = t ] ≥ 1− εadv
  where t ∈ {±1} is the target label.
  1When it is clear from context, we omit the arguments X ,D, β.
  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 is sufficiently large, ĥ will achieve uniform convergence, so it 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 Fadv(h∗) = Fadv(X , h∗,D, β = 0); that is, we consider classes of patch functions that don’t change the labels on a µD-measure-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 a natural family of functions. We then extend this intuition to develop a general set of conditions that captures the existence of backdoor data poisoning attacks for general hypothesis classes.
sections.heading: 2.2 Warmup – Overparameterized Vector Spaces
sections.text: We discuss the following family of toy examples first, as they are both simple to conceptualize and sufficiently powerful to subsume a variety of natural scenarios.
  Let V denote a vector space of functions of the form f : X → R with an orthonormal basis2 {vi}dim(V)i=1 . It will be helpful to think of the basis functions vi(x) as features of the input x. LetH be the set of all functions that can be written as h(x) = sign (v(x)) for v ∈ V . Let v∗(x) be a function satisfying h∗(x) = sign (v∗(x)).
  Now, assume that the data is sparse in the feature set; that is, there is a size-s < dim (V) minimal set of indices U ⊂ [dim (V)] such that all x in the support of D have vi(x) = 0 for i 6∈ U . This restriction implies that h∗ can be expressed as h∗(x) = sign (∑ i∈U ai · vi(x) ) .
  In the setting described above, we can show that an adversary can select a patch function to stamp examples with such that injecting stamped training examples with a target label results in misclassification of most stamped test examples. More formally, we have the below theorem.
  Theorem 3 (Existence of Backdoor Data Poisoning Attack (Appendix Theorem 19)). Let Fadv be some family of patch functions such that for all i ∈ U , Pr
  x∼D [vi(patch (x)) = vi(x)] = 1, there exists
  at least one j ∈ [dim (V)] \ U such that Pr x∼D [vj(patch (x)) 6= 0] = 1, and for all j ∈ [dim (V)], we either have Pr
  x∼D [vj(patch (x)) ≥ 0] = 1 or Pr x∼D [vj(patch (x)) ≤ 0] = 1.
  Fix any target label t ∈ {±1}. Draw a training set Sclean of size at least m0 := Ω ( ε−1clean (VC (H) + log (1/δ)) ) . Then, draw a backdoor training set Sadv of size at least m1 :=
  Ω ( ε−1adv (VC (H) + log (1/δ)) ) of the form (x, t) where x ∼ patch (D|h∗(x) 6= t).
  With probability at least 1 − δ, empirical risk minimization on the training set S := Sclean ∪ Sadv yields a 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.
sections.heading: 2.2.1 Overparameterized Linear Models
sections.text: 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-dimensional subspace of Rd where s < d, so with probability 1, we can write x ∼ D as Az for some A ∈ Rd×s and for z ∈ Rs. Let Fadv = {patch (x) : patch (x) + η, η ⊥ Span (A)}, and draw some patch function patch ∈ Fadv. Fix any target label t ∈ {±1}. Draw a training set Sclean of size at least m0 := Ω ( ε−1clean (VC (H) + log (1/δ)) ) . Then, draw a backdoor training set Sadv of size at least m1 :=
  Ω ( ε−1adv (VC (H) + log (1/δ)) ) of the form (x, t) where x ∼ (D|h∗(x) 6= t) + η.
  2Here, the inner product between two functions is defined as 〈f1, f2〉D := Ex∼D [f1(x) · f2(x)].
  With probability at least 1− δ, empirical risk minimization on the training set Sclean ∪ Sadv yields a 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 a valid patch. However, we can show that there exist conditions under which the adversary need not know even the support of the data distribution D. Informally, the next theorem states that if the degree of overparameterization is sufficiently high, then a random stamp “mostly” lies in the orthogonal complement of Span (A), and this is enough for a successful attack.
  Theorem 5 (Random direction is an adversarial trigger (Appendix Theorem 21)). Consider the same setting used in Corollary 4, and set Fadv = { patch : patch (x) = x+ η, η ∈ Rd } .
  If h∗ achieves margin γ and if the ambient dimension d of the model satisfies d ≥ Ω (s log(s/δ)/γ2), then an adversary can find a patch function such that with probability 1 − δ, a training set S = Sclean ∪ Sadv satisfying |Sclean| ≥ Ω ( ε−1clean (VC (H) + log (1/δ)) ) and |Sadv| ≥
  Ω ( ε−1clean (VC (H) + log (1/δ)) ) yields a classifier ĥ satisfying the success conditions for Problem 2
  while also satisfying E (x,y)∼D
  [ 1 { ĥ(x) 6= y }] ≤ εclean.
  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 ((Appendix Theorem 22)). Consider some h∗(x) = sign (〈w∗, x〉) and a data distribution D satisfying Pr
  (x,y)∼D [y 〈w∗, x〉 ≥ 1] = 1 and Pr (x,y)∼D [‖x‖ ≤ R] = 1. Let γ be the
  maximum margin over all weight vectors classifying the uncorrupted data, and let Fadv = {patch (x) : ‖patch (x)− x‖ ≤ γ}.
  If Sclean consists of at least Ω ( ε−2clean ( γ−2R2 + log (1/δ) )) i.i.d examples drawn from D and if Sadv
  consists of at least Ω ( ε−2adv ( γ−2R2 + log (1/δ) )) i.i.d examples drawn from D|h∗(x) 6= t, then we have: min
  w : ‖w‖≤γ−1 1 |S| ∑
  (x,y)∈S
  1 {y 〈w, x〉 < 1} > 0
  In other words, assuming there exists a margin γ and a 0-loss classifier, empirical risk minimization of margin-loss with a norm constraint fails to find a 0-loss classifier on a sufficiently contaminated training set.
sections.heading: 2.3 Memorization Capacity and Backdoor Attacks
sections.text: The key takeaway from the previous section is that the adversary can force an ERM learner to recover the union of a function that looks similar to the true classifier on in-distribution inputs and another function of the adversary’s choice. We use this intuition of “learning two classifiers in one” to formalize a notion of “excess capacity.”
  To this end, we define the memorization capacity of a class and a domain.
  Definition 7 (Memorization Capacity). Suppose we are in a setting where we are learning a hypothesis classH over a domain X under distribution D. We say we can memorize k irrelevant sets from a family C atop a fixed h∗ if we can find k pairwise disjoint nonempty sets X1, . . . , Xk from a family of subsets of the domain C such that for all b ∈ {±1}k, there exists a classifier ĥ ∈ H satisfying the below:
  • For all x ∈ Xi, we have ĥ(x) = bi.
  • Pr x∼D
  [ ĥ(x) = h∗(x) ] = 1.
  We define mcapX ,D (h,H, C) to be the maximum number of sets from C we can memorize for a fixed h belonging to a hypothesis class H. We define mcapX ,D (h,H) = mcapX ,D (h,H,BX ) 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 mcapX ,D (H) := suph∈HmcapX ,D (h,H).
  Intuitively, the memorization capacity captures the number of additional irrelevant (with respect to D) sets that can be memorized atop a 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 ≤ mcapX ,D (H) ≤ VC (H).
  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 9 (Nonzero Memorization Capacity Implies Backdoor Attack (Appendix Theorem 24)). Pick a target label t ∈ ±1. Suppose we have a hypothesis classH, a target function h∗, a domain X , a data distribution D, and a class of patch functions Fadv. Define:
  C(Fadv(h∗)) := {patch (Supp (D|h∗(x) 6= t)) : patch ∈ Fadv}
  Now, suppose that mcapX ,D (h ∗,H, C(Fadv(h∗))) ≥ 1. Then, there exists a function patch ∈ Fadv for which the adversary can draw a set Sadv consisting of m = Ω ( ε−1adv (VC (H) + log (1/δ)) ) i.i.d samples from D|h∗(x) 6= t such that with probability at least 1 − δ over the draws of Sadv, the adversary achieves the objectives of Problem 2, regardless of the number of samples the learner draws from D for Sclean.
  In words, the result of 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 at least k implies that the adversary can simultaneously execute k attacks using k 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).
  A natural follow-up question to the result of Theorem 9 is to ask whether a 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(Fadv(h∗)) be defined the same as in Theorem 9. Suppose we have a hypothesis class H over a domain X , a true classifier h∗, data distribution D, and a perturbation class Fadv. If mcapX ,D (h
  ∗,H, C(Fadv(h∗))) = 0, then the adversary cannot successfully construct a backdoor data poisoning attack as per the conditions of Problem 2.
sections.heading: 2.3.1 Examples
sections.text: We now use our notion of memorization capacity to examine the vulnerability of several natural learning problems to backdoor data poisoning attacks.
  Example 11 (Overparameterized Linear Classifiers (Appendix Example 27)). Recall the result from the previous section, where we took X = Rd,Hd to be the set of linear classifiers in Rd, and let D be a distribution over a radius-R subset of an s-dimensional subspace P . We also assume that the true labeler h∗ achieves margin γ.
  If we set Fadv = { patch (x) : patch (x) = x+ η, η ∈ Rd } , then we have mcapX ,D (h ∗,Hd, C(Fadv(h∗))) ≥ d− s.
  Example 12 (Linear Classifiers Over Convex Bodies (Appendix Example 28)). Let H be the set of origin-containing halfspaces. Fix an origin-containing halfspace h∗ with weight vector w∗. Let X ′ be a 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 `2 ball of nonzero radius contained in X and satisfies the relation µD(Y ) = 0 ⇐⇒ Vold(Y ) = 0 for all Y ⊂ X . Then, mcapX ,D (h∗,H) = 0.
  Given these examples, it is natural to wonder whether memorization capacity can be greater than 0 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, 1], D = Unif (X ) andHk be the class of functions admitting at most k sign-changes. Specifically,Hk consists of functions h for which we can find pairwise disjoint, continuous intervals I1, . . . , Ik+1 such that:
  • For all i < j and for all x ∈ Ii, y ∈ Ij , we have x < y. • ⋃k+1 i=1 Ii = X .
  • h(Ii) = −h(Ii+1), for all i ∈ [k].
  Suppose the learner is learningHs for unknown s usingHd, where s ≤ d+ 2. For all h∗ ∈ Hs, we have mcapX ,D (h ∗,Hd) ≥ b(d−s)/2c.
sections.heading: 3 Algorithmic Considerations
sections.text: We now turn our attention to computational issues relevant to backdoor data poisoning attacks. Throughout the rest of this section, define the adversarial loss:
  LFadv(h∗)(ĥ, S) := E (x,y)∼S
  [ sup
  patch∈Fadv(h∗) 1
  { ĥ(patch (x)) 6= y
  }]
  In a slight overload of notation, let LHFadv(h∗) denote the robust loss class ofH with the perturbation sets generated by Fadv(h∗):
  LHFadv(h∗) :=
  { (x, y) 7→ sup
  patch∈Fadv(h∗) 1
  { ĥ(patch (x)) 6= y } : ĥ ∈ H
  }
  Then, assume that VC ( LHFadv(h∗) ) is finite3. Finally, assume that the perturbation set Fadv is the same as that consistent with the ground-truth classifier h∗. In other words, once h∗ is selected, then we reveal to both the learner and the adversary the sets Fadv(h∗); thus, the learner equates Fadv and Fadv(h∗). Hence, although h∗ is not known to the learner, Fadv(h∗) is. As an example of a natural scenario in which such an assumption holds, consider the case where h∗ is some large-margin 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 impact the true classifications of the source images.
sections.heading: 3.1 Certifying the Existence of Backdoors
sections.text: The assumption that Fadv = Fadv(h∗) gives the learner enough information to minimize LFadv(h∗)(ĥ, S) on a finite training set S over ĥ ∈ H4; the assumption that VC ( LHFadv(h∗) ) < ∞ yields that the learner recovers a 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:
  LFadv(h∗)(ĥ, S) = E (x,y)∼S
  [ sup
  patch∈Fadv(h∗) 1
  { ĥ(patch (x)) 6= y
  }]
  over a finite set S and ĥ ∈ H.
  If the VC dimension of the loss class LHFadv(h∗) is finite, then there exists an algorithm using O ( ε−2clean ( VC ( LFadv(h∗) ) + log (1/δ) )) samples that allows the learner to defeat the adversary through learning a backdoor-robust classifier or by rejecting the training set as being corrupted, with probability 1− δ.
  3It is shown in [21] that there exist classesH and corresponding adversarial loss classes LFadv(h∗) for which VC (H) < ∞ but VC ( LHFadv(h∗) ) = ∞. Nonetheless, there are a variety of natural scenarios in which we
  have VC (H) ,VC ( LHFadv(h∗) ) <∞; for example, in the case of linear classifiers in Rd and for closed, convex,
  origin-symmetric, additive perturbation sets, we have VC (H) ,VC ( LHFadv(h∗) ) ≤ d+ 1 (see [26] [14]).
  4However, minimizing LFadv(h∗) might be computationally intractable in several scenarios.
  See Algorithm A.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 to a classifier with high robust loss, a practitioner can then manually inspect the dataset for corruptions or apply some data sanitization algorithm.
sections.heading: 3.1.1 Numerical Trials
sections.text: To exemplify such a workflow, we implement adversarial training in a backdoor data poisoning setting. Specifically, we select a 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 α. Our results demonstrate that in this setting, the training robust loss indeed increases with the fraction of corrupted data α; 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 a more detailed description of our methodology, setup, and results, please see Appendix Section B.
sections.heading: 3.2 Filtering versus Generalization
sections.text: 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 LFadv(h∗) on a finite training set. We first define these two problems below (Problems 15 and 16). Problem 15 (Backdoor Filtering). Given a training set S = Sclean ∪ Sadv such that |Sclean| ≥ Ω ( poly ( ε−1, log (1/δ) ,VC ( LFadv(h∗) ))) , return a subset S′ ⊆ S such that the solution to the optimization ĥ := argminh∈HLFadv(h∗) (h, S′) satisfies LFadv(h∗)(h,D) . εclean with probability 1− δ.
  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 = Sclean ∪ Sadv such that |Sclean| ≥ Ω ( poly ( ε−1, log (1/δ) ,VC ( LFadv(h∗) ))) , return a classifier ĥ satisfies LFadv(h∗)ĥ,D ≤ εclean with probability 1− δ.
  In other words, in Problem 16, we want to learn a 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 a solution for one implies a solution for the other. Specifically, we can write the below.
  Theorem 17 (Filtering Implies Generalization (Appendix Theorem 31)). Let α ≤ 1/3 and εclean ≤ 1/10. Suppose we have a training set S = Sclean ∪ Sadv such that |Sclean| = Ω ( ε−2clean ( VC ( LFadv(h∗) ) + log (1/δ) )) and |Sadv| ≤ α · (|Sadv|+ |Sclean|). If there exists an algorithm that given S can find a subset S′ = S′clean ∪ S′adv satisfying |S ′ clean|/|Sclean| ≥ 1− εclean and minh∈H LFadv(h∗)(h, S′) . εclean, then there exists an algorithm such that given S returns a function ĥ satisfying LFadv(h∗)(ĥ,D) . εclean with probability 1− δ.
  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)). Set εclean ≤ 1/10 and α ≤ 1/6.
  If there exists an algorithm that, given at most a 2α fraction of outliers in the training set, can output a hypothesis satisfying LFadv(h∗)(ĥ,D) ≤ εclean with probability 1− δ over the draw of the training set, then there exists an algorithm that given a training set S = Sclean ∪ Sadv satisfying
  |Sclean| ≥ Ω ( ε−2clean ( VC ( LFadv(h∗) ) + log (1/δ) )) outputs a subset S′ ⊆ S with the property that
  LFadv(h∗) ( argminh∈HLFadv(h∗) (h, S′) ,D ) . εclean with probability 1− 7δ.
  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 a classifier robust to 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 a 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 it is equivalent to focus on the conceptually simpler filtering problem.
sections.heading: 4 Related Works
sections.text: 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 a small number of impercetibly corrupted examples labeled as a target label. The attacker can ensure that the classifier’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 a 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 in 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 as exploiting spurious or 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 are 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 our 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 on 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 a 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 on 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.
sections.heading: 5 Conclusions and Future Work
sections.text: Conclusions We gave a framework under which backdoor data poisoning attacks can be studied. We then showed that, under this framework, a 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 are 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 learning5. Finally, we believe that our notion of memorization capacity can find applications beyond the scope of this work. It 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 privacy-preserving applications. Most notably, the Fawkes system (see [28]) relies on a backdoor data poisoning attack to preserve its users’ privacy, and such a system could be compromised if it were known how to reliably defend against backdoor data poisoning attacks in such a setting.
  Acknowledgments This work was supported in part by the National Science Foundation under grant CCF-1815011 and by the Defense Advanced Research Projects Agency under cooperative agreement HR00112020003. 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.
title: Excess Capacity and Backdoor Poisoning