Attacking Byzantine Robust Aggregation in High Dimensions
Not on the map. Why?
Abstract (arXiv)
Training modern neural networks or models typically requires averaging over a sample of high-dimensional vectors. Poisoning attacks can skew or bias the average vectors used to train the model, forcing the model to learn specific patterns or avoid learning anything useful. Byzantine robust aggregation is a principled algorithmic defense against such biasing. Robust aggregators can bound the maximum bias in computing centrality statistics, such as mean, even when some fraction of inputs are arbitrarily corrupted. Designing such aggregators is challenging when dealing with high dimensions. However, the first polynomial-time algorithms with strong theoretical bounds on the bias have recently been proposed. Their bounds are independent of the number of dimensions, promising a conceptual limit on the power of poisoning attacks in their ongoing arms race against defenses. In this paper, we show a new attack called HIDRA on practical realization of strong defenses which subverts their claim of dimension-independent bias. HIDRA highlights a novel computational bottleneck that has not been a concern of prior information-theoretic analysis. Our experimental evaluation shows that our attacks almost completely destroy the model performance, whereas existing attacks with the same goal fail to have much effect. Our findings leave the arms race between poisoning attacks and provable defenses wide open.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 37 of its 68 references that are in the map. First posted on arXiv 22 Dec 2023.
Builds on
37 of 68 references.
References · 37
- 2017Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithmscited by 4,283
- 2018How To Backdoor Federated Learningcited by 745
- 2018Byzantine-Robust Distributed Learning: Towards Optimal Statistical Ratescited by 698
- 2019Local Model Poisoning Attacks to Byzantine-Robust Federated Learningcited by 479
- 2018Analyzing Federated Learning through an Adversarial Lenscited by 346
- 2018The Hidden Vulnerability of Distributed Learning in Byzantiumcited by 324
- 2019Robust Aggregation for Federated Learningcited by 314
- 2020Attack of the Tails: Yes, You Really Can Backdoor Federated Learningcited by 307
- 2020Data Poisoning Attacks Against Federated Learning Systemscited by 266
- 2019Can You Really Backdoor Federated Learning?cited by 250
- 2016Robust Estimators in High Dimensions without the Computational Intractabilitycited by 209
- 2017Towards Poisoning of Deep Learning Algorithms with Back-gradient Optimizationcited by 188
25 more
- 2019Fall of Empires: Breaking Byzantine-tolerant SGD by Inner Product Manipulationcited by 136
- 2016Agnostic Estimation of Mean and Covariancecited by 131
- 2021Back to the Drawing Board: A Critical Evaluation of Poisoning Attacks on Production Federated Learningcited by 116
- 2020RAB: Provable Robustness Against Backdoor Attackscited by 115
- 2020Deep Partition Aggregation: Provable Defense against General Poisoning Attackscited by 112
- 2020Certified Robustness to Label-Flipping Attacks via Randomized Smoothingcited by 103
- 2019Recent Advances in Algorithmic High-Dimensional Robust Statisticscited by 100
- 2022Truth Serum: Poisoning Machine Learning Models to Reveal Their Secretscited by 94
- 2020Intrinsic Certified Robustness of Bagging against Data Poisoning Attackscited by 90
- 2017Being Robust (in High Dimensions) Can Be Practicalcited by 83
- 2020On the Effectiveness of Mitigating Data Poisoning Attacks with Gradient Shapingcited by 82
- 2018Label Sanitization against Label Flipping Poisoning Attackscited by 68
- 2020Poisoning Attacks on Algorithmic Fairnesscited by 58
- 2020Certified Robustness of Nearest Neighbors against Data Poisoning and Backdoor Attackscited by 58
- 2020Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimizationcited by 44
- 2019Quantum Entropy Scoring for Fast Robust Mean Estimation and Improved Outlier Detectioncited by 41
- 2018High-Dimensional Robust Mean Estimation in Nearly-Linear Timecited by 39
- 2020Mitigating Backdoor Attacks in Federated Learningcited by 39
- 2021PipAttack: Poisoning Federated Recommender Systems forManipulating Item Promotioncited by 37
- 2022Byzantine-Robust Federated Learning with Optimal Statistical Rates and Privacy Guaranteescited by 30
- 2019Distributed Training with Heterogeneous Data: Bridging Median- and Mean-Based Algorithmscited by 29
- 2017Outlier-robust moment-estimation via sum-of-squarescited by 27
- 2019Deconstructing Generative Adversarial Networkscited by 15
- 2021Polynomial-Time Sum-of-Squares Can Robustly Estimate Mean and Covariance of Gaussians Optimallycited by 14
- 2022Unraveling the Connections between Privacy and Certified Robustness in Federated Learning Against Poisoning Attackscited by 12
Built on by
Citing papers per year: 2025: 1.
1 paper.