# On Collective Robustness of Bagging Against Data Poisoning

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Placed in Backdoor and data poisoning attacks, one of 12 directions in LLM safety and security.
- Builds on 25 of its 46 references that are in the map.
- First posted on arXiv 26 May 2022.

## Placed in

- LLM safety and security / [Backdoor and data poisoning attacks](https://mlsanity.com/safety/backdoor-and-data-poisoning-attacks/)

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

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Network In Network](https://mlsanity.com/paper/1312.4400/) (2013)
- [On Adaptive Attacks to Adversarial Example Defenses](https://mlsanity.com/paper/2002.08347/) (2020)
- [Poison Frogs! Targeted Clean-Label Poisoning Attacks on Neural Networks](https://mlsanity.com/paper/1804.00792/) (2018)
- [Spectral Signatures in Backdoor Attacks](https://mlsanity.com/paper/1811.00636/) (2018)
- [STRIP: A Defence Against Trojan Attacks on Deep Neural Networks](https://mlsanity.com/paper/1902.06531/) (2019)
- [Backdoor Learning: A Survey](https://mlsanity.com/paper/2007.08745/) (2020)
- [Certified Defenses for Data Poisoning Attacks](https://mlsanity.com/paper/1706.03691/) (2017)
- [Witches' Brew: Industrial Scale Data Poisoning via Gradient Matching](https://mlsanity.com/paper/2009.02276/) (2020)
- [Stronger Data Poisoning Attacks Break Data Sanitization Defenses](https://mlsanity.com/paper/1811.00741/) (2018)
- [MetaPoison: Practical General-purpose Clean-label Data Poisoning](https://mlsanity.com/paper/2004.00225/) (2020)
- [RAB: Provable Robustness Against Backdoor Attacks](https://mlsanity.com/paper/2003.08904/) (2020)
- [Just How Toxic is Data Poisoning? A Unified Benchmark for Backdoor and Data Poisoning Attacks](https://mlsanity.com/paper/2006.12557/) (2020)
- [Deep Partition Aggregation: Provable Defense against General Poisoning Attacks](https://mlsanity.com/paper/2006.14768/) (2020)
- [Certified Robustness to Label-Flipping Attacks via Randomized Smoothing](https://mlsanity.com/paper/2002.03018/) (2020)
- [Intrinsic Certified Robustness of Bagging against Data Poisoning Attacks](https://mlsanity.com/paper/2008.04495/) (2020)
- [Is feature selection secure against training data poisoning?](https://mlsanity.com/paper/1804.07933/) (2018)
- [Defending Neural Backdoors via Generative Distribution Modeling](https://mlsanity.com/paper/1910.04749/) (2019)
- [Data Poisoning against Differentially-Private Learners: Attacks and Defenses](https://mlsanity.com/paper/1903.09860/) (2019)
- [On Certifying Robustness against Backdoor Attacks via Randomized Smoothing](https://mlsanity.com/paper/2002.11750/) (2020)
- [Certified Robustness of Nearest Neighbors against Data Poisoning and Backdoor Attacks](https://mlsanity.com/paper/2012.03765/) (2020)
- [Improved Certified Defenses against Data Poisoning with (Deterministic) Finite Aggregation](https://mlsanity.com/paper/2202.02628/) (2022)
- [Black-Box Certification with Randomized Smoothing: A Functional Optimization Based Framework](https://mlsanity.com/paper/2002.09169/) (2020)
- [Data Poisoning Attacks against Online Learning](https://mlsanity.com/paper/1808.08994/) (2018)

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

- [Training Data Influence Analysis and Estimation: A Survey](https://mlsanity.com/paper/2212.04612/) (2022)
- [BAFFLE: Hiding Backdoors in Offline Reinforcement Learning Datasets](https://mlsanity.com/paper/2210.04688/) (2022)
- [Run-Off Election: Improved Provable Defense against Data Poisoning Attacks](https://mlsanity.com/paper/2302.02300/) (2023)
- [Localized Randomized Smoothing for Collective Robustness Certification](https://mlsanity.com/paper/2210.16140/) (2022)
- [Temporal Robustness against Data Poisoning](https://mlsanity.com/paper/2302.03684/) (2023)
- [Node-aware Bi-smoothing: Certified Robustness against Graph Injection Attacks](https://mlsanity.com/paper/2312.03979/) (2023)
- [PECAN: A Deterministic Certified Defense Against Backdoor Attacks](https://mlsanity.com/paper/2301.11824/) (2023)
- [Provable Robustness of (Graph) Neural Networks Against Data Poisoning and Backdoor Attacks](https://mlsanity.com/paper/2407.10867/) (2024)
- [On the Robustness of Random Forest Against Untargeted Data Poisoning: An Ensemble-Based Approach](https://mlsanity.com/paper/2209.14013/) (2022)
- [Pick your Poison: Undetectability versus Robustness in Data Poisoning Attacks](https://mlsanity.com/paper/2305.09671/) (2023)
- [On Practical Aspects of Aggregation Defenses against Data Poisoning Attacks](https://mlsanity.com/paper/2306.16415/) (2023)
- [Does Differential Privacy Prevent Backdoor Attacks in Practice?](https://mlsanity.com/paper/2311.06227/) (2023)
- [Trust Under Siege: Label Spoofing Attacks against Machine Learning for Android Malware Detection](https://mlsanity.com/paper/2503.11841/) (2025)
- [Towards Poisoning Robustness Certification for Natural Language Generation](https://mlsanity.com/paper/2602.09757/) (2026)
- [Continuous Management of Machine Learning-Based Application Behavior](https://mlsanity.com/paper/2311.12686/) (2023)
- [Timber! Poisoning Decision Trees](https://mlsanity.com/paper/2410.00862/) (2024)

## Abstract (arXiv)

Bootstrap aggregating (bagging) is an effective ensemble protocol, which is believed can enhance robustness by its majority voting mechanism. Recent works further prove the sample-wise robustness certificates for certain forms of bagging (e.g. partition aggregation). Beyond these particular forms, in this paper, we propose the first collective certification for general bagging to compute the tight robustness against the global poisoning attack. Specifically, we compute the maximum number of simultaneously changed predictions via solving a binary integer linear programming (BILP) problem. Then we analyze the robustness of vanilla bagging and give the upper bound of the tolerable poison budget. Based on this analysis, we propose hash bagging to improve the robustness of vanilla bagging almost for free. This is achieved by modifying the random subsampling in vanilla bagging to a hash-based deterministic subsampling, as a way of controlling the influence scope for each poisoning sample universally. Our extensive experiments show the notable advantage in terms of applicability and robustness.