# Attacking Byzantine Robust Aggregation in High Dimensions

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 37 of its 68 references that are in the map.
- First posted on arXiv 22 Dec 2023.

## Builds on (most cited first, 30 of 37)

- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [How To Backdoor Federated Learning](https://mlsanity.com/paper/1807.00459/) (2018)
- [Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates](https://mlsanity.com/paper/1803.01498/) (2018)
- [Local Model Poisoning Attacks to Byzantine-Robust Federated Learning](https://mlsanity.com/paper/1911.11815/) (2019)
- [Analyzing Federated Learning through an Adversarial Lens](https://mlsanity.com/paper/1811.12470/) (2018)
- [The Hidden Vulnerability of Distributed Learning in Byzantium](https://mlsanity.com/paper/1802.07927/) (2018)
- [Robust Aggregation for Federated Learning](https://mlsanity.com/paper/1912.13445/) (2019)
- [Attack of the Tails: Yes, You Really Can Backdoor Federated Learning](https://mlsanity.com/paper/2007.05084/) (2020)
- [Data Poisoning Attacks Against Federated Learning Systems](https://mlsanity.com/paper/2007.08432/) (2020)
- [Can You Really Backdoor Federated Learning?](https://mlsanity.com/paper/1911.07963/) (2019)
- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [Towards Poisoning of Deep Learning Algorithms with Back-gradient Optimization](https://mlsanity.com/paper/1708.08689/) (2017)
- [Fall of Empires: Breaking Byzantine-tolerant SGD by Inner Product Manipulation](https://mlsanity.com/paper/1903.03936/) (2019)
- [Agnostic Estimation of Mean and Covariance](https://mlsanity.com/paper/1604.06968/) (2016)
- [RAB: Provable Robustness Against Backdoor Attacks](https://mlsanity.com/paper/2003.08904/) (2020)
- [Back to the Drawing Board: A Critical Evaluation of Poisoning Attacks on Production Federated Learning](https://mlsanity.com/paper/2108.10241/) (2021)
- [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)
- [Recent Advances in Algorithmic High-Dimensional Robust Statistics](https://mlsanity.com/paper/1911.05911/) (2019)
- [Truth Serum: Poisoning Machine Learning Models to Reveal Their Secrets](https://mlsanity.com/paper/2204.00032/) (2022)
- [Intrinsic Certified Robustness of Bagging against Data Poisoning Attacks](https://mlsanity.com/paper/2008.04495/) (2020)
- [Being Robust (in High Dimensions) Can Be Practical](https://mlsanity.com/paper/1703.00893/) (2017)
- [On the Effectiveness of Mitigating Data Poisoning Attacks with Gradient Shaping](https://mlsanity.com/paper/2002.11497/) (2020)
- [Label Sanitization against Label Flipping Poisoning Attacks](https://mlsanity.com/paper/1803.00992/) (2018)
- [Certified Robustness of Nearest Neighbors against Data Poisoning and Backdoor Attacks](https://mlsanity.com/paper/2012.03765/) (2020)
- [Poisoning Attacks on Algorithmic Fairness](https://mlsanity.com/paper/2004.07401/) (2020)
- [Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimization](https://mlsanity.com/paper/2007.15839/) (2020)
- [Quantum Entropy Scoring for Fast Robust Mean Estimation and Improved Outlier Detection](https://mlsanity.com/paper/1906.11366/) (2019)
- [High-Dimensional Robust Mean Estimation in Nearly-Linear Time](https://mlsanity.com/paper/1811.09380/) (2018)
- [Mitigating Backdoor Attacks in Federated Learning](https://mlsanity.com/paper/2011.01767/) (2020)

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

- [On the Detectability of Active Gradient Inversion Attacks in Federated Learning](https://mlsanity.com/paper/2511.10502/) (2025)

## 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.