A Practical and Secure Byzantine Robust Aggregator Conference: Proceedings of the 2025 ACM SIGSAC Conference on Computer and Communications Security; October 13–17, 2025; Taipei, Taiwan. Proceedings of the 2025 ACM SIGSAC Conference on Computer and Communications Security (CCS ’25), October 13–17, 2
De Zhang Lee, Aashish Kolluri, Prateek Saxena, Ee-Chien Chang · 2025
Read A Practical and Secure Byzantine Robust Aggregator Conference: Proceedings of the 2025 ACM SIGSAC Conference on Computer and Communications Security; October 13–17, 2025; Taipei, Taiwan. Proceedings of the 2025 ACM SIGSAC Conference on Computer and Communications Security (CCS ’25), October 13–17, 2 by De Zhang Lee, Aashish Kolluri, Prateek Saxena, Ee-Chien Chang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-23183.txt.
Introduction
De Zhang Lee, Aashish Kolluri, Prateek Saxena, and Ee-Chien Chang present in a 2025 paper a fast, secure aggregator that resists poisoned inputs. Averaging vectors sits at the heart of training, and attack vectors skew that average. Filtering outliers before averaging is a generic defense across many attacks.
Their aggregator runs in near linear time in the input size, a first at this strength. Its bias stays provably near optimal even when a share of vectors are corrupt. No knowledge of the clean data spread is needed to run it. No preset filter thresholds must be computed ahead of time either. Timed runs and ten poisoning attack tests back the claims in the paper.
Catalog record
| CREATOR | De Zhang Lee, Aashish Kolluri, Prateek Saxena, Ee-Chien Chang |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 105 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-23183
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Practical and Secure Byzantine Robust Aggregator Conference: Proceedings of the 2025 ACM SIGSAC Conference on Computer and Communications Security; October 13–17, 2025; Taipei, Taiwan. Proceedings of the 2025 ACM SIGSAC Conference on Computer and Communications Security (CCS ’25), October 13–17, 2025, Taipei, Taiwan ISBN: 979-8-4007-1525-9/2025/10 DOI: 10.1145/3719027.3744851 CCS: Security and privacy Software and application security CCS: Computing methodologies Machine learning De Zhang Lee, Aashish Kolluri, Prateek Saxena, Ee-Chien Chang Abstract . In machine learning security, one is often faced with the problem of removing outliers from a given set of high-dimensional vectors when computing their average. For example, many variants of data poisoning attacks produce gradient vectors during training that are outliers in the distribution of clean gradients, which bias the computed average used to derive the ML model. Filtering them out before averaging serves as a generic defense strategy. Byzantine robust aggregation is an algorithmic primitive which computes a robust average of vectors, in the presence of an ϵ \epsilon fraction of vectors which may have been arbitrarily and adaptively corrupted, such that the resulting bias in the final average is provably bounded. In this paper, we give the first robust aggregator that runs in quasi-linear time in the size of input vectors and provably has near-optimal bias bounds. Our algorithm also does not assume any knowledge of the distribution of clean vectors, nor does it require pre-computing any filtering thresholds from it. This makes it practical to use directly in standard neural network training procedures. We empirically confirm its expected runtime efficiency and its effectiveness in nullifying 10 different ML poisoning attacks. 1. Introduction Machine learning (ML) models are trained on massive datasets gathered from the open web. A prominent threat to such training is data poisoning attacks ( Biggio et al. 2012 ) . In such attacks a small fraction of the training data samples, or the gradient vectors derived from them, are adversarially corrupted such that the final model deviates from the original. The objective of effecting such deviation varies across attacks. Backdoor poisoning attacks aim for ML models to recognize secret patterns that cause errant outputs at inference time. Untargeted poisoning attacks cause mis-classification degrading accuracy during training, while targeted poisoning attacks cause misclassification selectively. Recent works have argued that web-scale poisoning is practical with very low cost ( Carlini et al. 2024 ) . We want generic and principled defenses that can tackle a large variety of poisoning attacks. Very few ideas for such defenses are presently known. One promising approach is based on Byzantine robust aggregation . A robust aggregator takes as input a set of vectors, a small fraction \epsilon of which may have been arbitrarily corrupted to deviate from the rest, and computes a robust mean for this set ( Diakonikolas and Kane 2019 ) . The robust mean is guaranteed to not deviate much from the mean of the uncorrupted vectors in the input set, i.e., the norm (magnitude) of the deviation caused by the corrupted vectors is tightly bounded. This deviation is also called the bias . If we have such a robust aggregator, it can be used to average the gradient vectors during standard training such as with stochastic gradient descent or with other methods that use averaging. This approach is compatible both with centralized training, where all data is gathered at a central service for training, as well as the federated learning setup wherein multiple distributed workers send locally computed gradient vectors to an aggregation server. The strategy of norm-bounding the deviation of the average of gradient vectors offers a generic and principled way to beat many attacks—several prior works ( Diakonikolas and Kane 2019 ; Zhu et al. 2023 ; Shen et al. 2016 ; Shejwalkar and Houmansadr 2021 ; Fang et al. 2020 ; Goldblum et al. 2023 ) have made this observation. Designing a Byzantine robust aggregator is a central focus of this paper. The main challenge is that of aggregating over high-dimensional vectors. Gradient vectors arising in training of modern neural network models have d dimensions, typically higher than 2^{30} . Robust aggregators that run in \Omega(d^{2}) are computationally too expensive to use in practice. Similarly, aggregators with large bounds on the bias have weak security. For example, there are linear-time aggregators that can upper bound the bias to a factor O(\sqrt{d}) of the variance of the uncorrupted vectors. A recent attack shows that such vacuously large bounds can permit real poisoning attacks in the federated learning setup, causing extensive loss in model performance during training ( Choudhary et al. 2024 ) . Our goal is to devise techniques that have quasi-linear running time \tilde{O}(n\cdot d) , where n is the number of vectors and d is the number of dimensions, while having dimension-independent bound on the maximum possible bias. Practical Robust Aggregation. In the statistics literature, the concept of “robustness” was formally introduced in 1953 ( Box 1953 ) . However, techniques such as dimension-wise mean aggregation to mitigate the influence of outliers in experiments have been in use for over a century—early examples include Newcomb’s work in 1886 ( Newcomb 1886 ) . Tukey’s seminal work on robust statistics ( Tukey 1960 ) observed that such techniques yield a sub-optimal bias upper bound, and generalized the notion of the statistical median to higher dimensions through the Tukey median which achieves the information-theoretic optimal bias. Despite its theoretical significance, the exact computation or approximation of the Tukey median is NP-Hard ( Hopkins and Li 2019 ) , making it impractical to be employed as a Byzantine robust aggregator. Table 1 summarizes the state-of-the-art solutions. The bias characterizes the theoretical security guarantee offered. It is an upper bound, a multiplicative factor of the natural variance of the uncorrupted (clean) samples in the set of vectors given as input. Weak robust aggregators have dimension-dependent bounds on the bias which give a weak theoretical security. Strong aggregators limit the adversarial bias in the computed mean to near optimal, i.e., independent of d . The best known strong robust aggregators run in \Omega(nd^{2}) which are prohibitively slow in high-dimensional setups. Table 1. Maximum bias and computational complexity of several weak and strong robust aggregators. ||\Sigma||_{2} refers to the maximum variance of the uncorrupted sample (dominant eigenvalue of the covariance matrix) over the given d -dimensional n vector samples. \tilde{O}(\cdot) ignores the constant and logarithmic factors in the computation complexity. Algorithm Max. Bias Comp. Complexity Weak Robust Aggregators Median ( Yin et al. 2018 ) Trimmed Mean ( Yin et al. 2018 ) \tilde{O}(\sqrt{d})\cdot\sqrt{||\Sigma||_{2}} \tilde{O}(nd) Geometric Median ( Pillutla et al. 2022 ; Blanchard et al. 2017 ; Chen et al. 2020 ) Strong Robust Aggregators Filtering ( Diakonikolas et al. 2017 ) \tilde{O}(\epsilon nd^{3}) No-Regret ( Hopkins et al. 2020 ) \tilde{O}((n+d^{3})\cdot d) SoS ( Kothari and Steurer 2017 ) \tilde{O}(1)\cdot\sqrt{||\Sigma||_{2}} poly (n,d) Tukey Median ( Tukey 1960 ) NP-Hard in d RandEigen \tilde{O}(nd) The most computationally efficient among strong aggregators are those that employ iterative filtering. In this approach, outlier vectors are iteratively filtered out, or assigned lower weights, before computing their final average. In each iterateion, iterative filtering works by computing the dominant eigenvector 1 1 1 The dominant eigenvector is the of