# Excess Capacity and Backdoor Poisoning

arXiv: https://arxiv.org/abs/2109.00685 · HTML: https://mlsanity.com/paper/2109.00685/

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 32 references that are in the map.
- First posted on arXiv 2 Sep 2021.

## Builds on (most cited first, 22 of 22)

- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- ["Why Should I Trust You?": Explaining the Predictions of Any Classifier](https://mlsanity.com/paper/1602.04938/) (2016)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [BadNets: Identifying Vulnerabilities in the Machine Learning Model Supply Chain](https://mlsanity.com/paper/1708.06733/) (2017)
- [Targeted Backdoor Attacks on Deep Learning Systems Using Data Poisoning](https://mlsanity.com/paper/1712.05526/) (2017)
- [Adversarial Examples Are Not Bugs, They Are Features](https://mlsanity.com/paper/1905.02175/) (2019)
- [A Closer Look at Memorization in Deep Networks](https://mlsanity.com/paper/1706.05394/) (2017)
- [Exploring Generalization in Deep Learning](https://mlsanity.com/paper/1706.08947/) (2017)
- [Poison Frogs! Targeted Clean-Label Poisoning Attacks on Neural Networks](https://mlsanity.com/paper/1804.00792/) (2018)
- [What Neural Networks Memorize and Why: Discovering the Long Tail via Influence Estimation](https://mlsanity.com/paper/2008.03703/) (2020)
- [Spectral Signatures in Backdoor Attacks](https://mlsanity.com/paper/1811.00636/) (2018)
- [Hidden Trigger Backdoor Attacks](https://mlsanity.com/paper/1910.00033/) (2019)
- [Turning Your Weakness Into a Strength: Watermarking Deep Neural Networks by Backdooring](https://mlsanity.com/paper/1802.04633/) (2018)
- [Noise or Signal: The Role of Image Backgrounds in Object Recognition](https://mlsanity.com/paper/2006.09994/) (2020)
- [Attack of the Tails: Yes, You Really Can Backdoor Federated Learning](https://mlsanity.com/paper/2007.05084/) (2020)
- [Label-Consistent Backdoor Attacks](https://mlsanity.com/paper/1912.02771/) (2019)
- [Stronger Data Poisoning Attacks Break Data Sanitization Defenses](https://mlsanity.com/paper/1811.00741/) (2018)
- [Strong Data Augmentation Sanitizes Poisoning and Backdoor Attacks Without an Accuracy Tradeoff](https://mlsanity.com/paper/2011.09527/) (2020)
- [VC Classes are Adversarially Robustly Learnable, but Only Improperly](https://mlsanity.com/paper/1902.04217/) (2019)
- [Systematic Evaluation of Backdoor Data Poisoning Attacks on Image Classifiers](https://mlsanity.com/paper/2004.11514/) (2020)
- [Efficiently Learning Adversarially Robust Halfspaces with Noise](https://mlsanity.com/paper/2005.07652/) (2020)

## Built on by (most cited first, 24 of 24)

- [Narcissus: A Practical Clean-Label Backdoor Attack with Limited Information](https://mlsanity.com/paper/2204.05255/) (2022)
- [Wild Patterns Reloaded: A Survey of Machine Learning Security against Training Data Poisoning](https://mlsanity.com/paper/2205.01992/) (2022)
- [An Embarrassingly Simple Backdoor Attack on Self-supervised Learning](https://mlsanity.com/paper/2210.07346/) (2022)
- [Algorithmic Collective Action in Machine Learning](https://mlsanity.com/paper/2302.04262/) (2023)
- [Mitigating Backdoor Poisoning Attacks through the Lens of Spurious Correlation](https://mlsanity.com/paper/2305.11596/) (2023)
- [Just Rotate it: Deploying Backdoor Attacks via Rotation Transformation](https://mlsanity.com/paper/2207.10825/) (2022)
- [Distilling Cognitive Backdoor Patterns within an Image](https://mlsanity.com/paper/2301.10908/) (2023)
- [Trap and Replace: Defending Backdoor Attacks by Trapping Them into an Easy-to-Replace Subnetwork](https://mlsanity.com/paper/2210.06428/) (2022)
- [Demystifying Poisoning Backdoor Attacks from a Statistical Perspective](https://mlsanity.com/paper/2310.10780/) (2023)
- [Towards Unified Robustness Against Both Backdoor and Adversarial Attacks](https://mlsanity.com/paper/2405.17929/) (2024)
- [Data-centric NLP Backdoor Defense from the Lens of Memorization](https://mlsanity.com/paper/2409.14200/) (2024)
- [Statistical Collusion by Collectives on Learning Platforms](https://mlsanity.com/paper/2502.04879/) (2025)
- [Cerberus: Exploring Federated Prediction of Security Events](https://mlsanity.com/paper/2209.03050/) (2022)
- [Invisible Backdoor Attack with Dynamic Triggers against Person Re-identification](https://mlsanity.com/paper/2211.10933/) (2022)
- [An Adversarial Robustness Perspective on the Topology of Neural Networks](https://mlsanity.com/paper/2211.02675/) (2022)
- [Injecting Undetectable Backdoors in Obfuscated Neural Networks and Language Models](https://mlsanity.com/paper/2406.05660/) (2024)
- [Augmented Neural Fine-Tuning for Efficient Backdoor Purification](https://mlsanity.com/paper/2407.10052/) (2024)
- [UTrace: Poisoning Forensics for Private Collaborative Learning](https://mlsanity.com/paper/2409.15126/) (2024)
- [Invariant Aggregator for Defending against Federated Backdoor Attacks](https://mlsanity.com/paper/2210.01834/) (2022)
- [Fisher Information guided Purification against Backdoor Attacks](https://mlsanity.com/paper/2409.00863/) (2024)
- [A Linear Approach to Data Poisoning](https://mlsanity.com/paper/2505.15175/) (2025)
- [Efficient Backdoor Removal Through Natural Gradient Fine-tuning](https://mlsanity.com/paper/2306.17441/) (2023)
- [GREAT: Generalizable Backdoor Attacks in RLHF via Emotion-Aware Trigger Synthesis](https://mlsanity.com/paper/2510.09260/) (2025)
- [Provable one-poison backdoor attacks on linear models and ReLU neural networks](https://mlsanity.com/paper/2508.05600/) (2025)

## Abstract (arXiv)

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.