Approaching the Harm of Gradient Attacks While Only Flipping Labels
Abdessamad El-Kabid [email protected], El-Mahdi El-Mhamdi [email protected] · 2025
Read Approaching the Harm of Gradient Attacks While Only Flipping Labels by Abdessamad El-Kabid [email protected], El-Mahdi El-Mhamdi [email protected] (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-2503-00140.txt.
Introduction
Abdessamad El-Kabid and El-Mahdi El-Mhamdi studied sabotage of shared learning in two thousand twenty-five. In federated learning, many devices train one model together. Attackers may poison the process to break the model. Past attacks injected fake data or tampered with updates. The authors ask how much harm mere label flips can do. The attacker may only relabel a few existing examples.
They frame each round of flipping as a constrained puzzle. The setting assumes simple averaging of device updates. Even this weak attack can approach stronger attacks in damage. Limits depend on how many labels the attacker controls. The results expose a blind spot in shared training defenses. Guarding labels may matter as much as guarding data. The work guides designers of safer federated systems.
Catalog record
| CREATOR | Abdessamad El-Kabid [email protected], El-Mahdi El-Mhamdi [email protected] |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 46 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-00140
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Approaching the Harm of Gradient Attacks While Only Flipping Labels Abdessamad El-Kabid [email protected], El-Mahdi El-Mhamdi [email protected] Abstract Machine learning systems deployed in distributed or federated environments are highly susceptible to adversarial manipulations, particularly availability attacks – rendering the trained model unavailable. Prior research in distributed ML has demonstrated such adversarial effects through the injection of gradients or data poisoning. In this work, we ask whether comparable degradation is still possible under a substantially more constrained action space: the adversary may only flip a limited number of labels of existing training examples, without modifying features, injecting samples, or directly controlling gradients. We analyze the extent of damage caused by constrained label flipping attacks against distributed learning under mean aggregation – the dominant baseline in research and production. Focusing on classification problems, (1) we propose a novel formalization of label flipping attacks as a per-round constrained optimization problem, derive a greedy label-selection rule for logistic regression, and empirically evaluate it beyond its derivation setting, including on MLPs and robust aggregators. The rule is provably per-epoch optimal for the attacker under the mean aggregator. (2) Empirically, we show that optimized label flipping can cause substantial accuracy degradation while outperforming random label flipping under similar budgets. (3) We shed light on an interesting interplay between what the attacker gains from more write-access versus what they gain from more flipping budget . (4) Finally, although the attack is derived for mean aggregation, we find that it can transfer empirically to the coordinate-wise median and trimmed mean aggregators, where its effectiveness approaches that of the Little-is-Enough gradient attack. This demonstrates that even highly constrained label-flipping adversaries can pose a significant availability threat to distributed learning. Reviewed on OpenReview: https://openreview.net/forum?id=eAqBcljvsU 1 Introduction and Related Work \mathbb{R}^{d} \mathbb{R}^{d} \nabla_{\theta}L\bigl(h_{\theta}(\mathcal{X}),\mathcal{Y}\bigr) \nabla_{\theta}L\bigl(h_{\theta}(F_{\mathcal{X}}),F_{\mathcal{Y}}\bigr) \nabla_{\theta}L\bigl(\mathcal{D}_{\mathcal{X}},h_{\theta}(F_{\mathcal{Y}})\bigr) Figure 1 : Images of the gradient operator on different sets. \mathbb{R}^{d} is where an attacker can craft unrestricted gradient attacks. Given a model h_{\theta} , \nabla_{\theta}L(h_{\theta}(\mathcal{X}),\mathcal{Y}) is the set of possible gradients given an unrestricted data poisoning Bouaziz et al. (2025) , \nabla_{\theta}L(h_{\theta}(\mathcal{F}_{\mathcal{X}}),\mathcal{F}_{\mathcal{Y}}) is the set of possible gradients when data poisoning is restricted to a feasible set \mathcal{F}_{\mathcal{X}}\times\mathcal{F}_{\mathcal{Y}}\subseteq\mathcal{X}\times\mathcal{Y} , and \nabla_{\theta}L\bigl(\mathcal{D}_{\mathcal{X}},h_{\theta}(F_{\mathcal{Y}})\bigr) is the set of possible gradients when the features are restricted to those in the dataset \mathcal{D}_{\mathcal{X}} and the labels are chosen in the set of feasible labels. Machine learning systems can become prime targets for adversarial attacks. Training-phase poisoning attacks in particular have gained considerable attention as the widespread use of machine learning in critical applications has grown ( Awasthi et al. (2017) ; Zhang et al. (2017) ; Paudice et al. (2018) ; Lu et al. (2022) ; Huang et al. (2011) ). In these attacks, an adversary manipulates the training data in order to degrade or control the final trained model. Unlike evasion and backdoor attacks, poisoning requires no control over inference-time input: it suffices to manipulate part of the training set. Among such attacks, label flipping stands out for its simplicity: The attacker simply changes the class label of a subset of training points while leaving other aspects of the data intact. This is especially relevant in federated learning situations where features are fixed by upstream data pipelines and the set of possible labels is predefined. For example, a common scenario is when workers are asked to label predefined images, the labels being in a finite set. We address the following question in the context of a classification problem: Can a gradient-informed attacker severely degrade a model using only label flips on existing data, under budget constraints ? In this work, we provide a positive answer to this question. By viewing label flipping as a constrained optimization problem from the point of view of the attacker, we show that carefully selected flips can steer the aggregated gradient away from its honest direction and reduce accuracy or render training unstable - even when only 5\% of the labels are altered. Figure 2 : Territory of known availability attacks (in orange) within a domain of constraints. The closer to the origin, the more constrained is the setting for the attacker and the harder it is to realize an availability attack. \spadesuit : Geiping et al. (2020) ; Zhao and Lao (2022) ; Ning et al. (2021) ; Huang et al. (2020) , \heartsuit : Blanchard et al. (2017) ; Baruch et al. (2019) , \clubsuit : El-Mhamdi et al. (2018) , \diamondsuit so far only in convex settings : Farhadkhani et al. (2022) , \triangle\&\triangledown : Bouaziz et al. (2025) , \bigstar : Our contribution. Previous work has investigated poisoning attacks and granted the adversary far more leverage than some realistic scenarios allow. Some require the ability to modify both labels and features or even overwrite entire gradients ( Bouaziz et al. (2025) ; Baruch et al. (2019) ); others rely on injecting crafted examples into the training set ( Shafahi et al. (2018) ; Zhao and Lao (2022) ; Koh et al. (2022) ). Li et al. (2022) proposes an agglomerative-clustering strategy to select vulnerable samples, assuming access to all training data and performing offline clustering. Jha et al. (2023) demonstrates that carefully chosen label poisoning can insert backdoors via trajectory-matching methods. Their objective is to create targeted misclassification when a trigger is present, not to reduce overall model accuracy. Thus, although both their work and ours manipulate labels only, the goals, threat models, and evaluation metrics differ: their work aims to insert backdoors, whereas we study availability degradation under a tight budget and online setting. Likewise, Lavaur et al. (2024) applies random label flipping in the context of collaborative intrusion detection systems. The attack of Lavaur et al. (2024) targets domain-specific labels (e.g., DDoS) and does not formalize the attack as an optimization problem. In contrast, we aim to study an attack that is gradient-informed and can be proved to be optimal at each iteration for the considered objective. Yu et al. (2025) study label-flipping attacks on GNNs under a federated learning setup. Their approach is oriented towards graph-structured data and relies on the unique properties of GNN aggregation mechanisms. In contrast, we propose a method that is formulated as a general optimization framework based on gradient alignment, making it applicable to a wider range of classification tasks. When manipulation is limited to labels alone, existing methods typically presuppose control over the vast majority of them ( \geq 85\% ) or access to the validation set, and require the training of a number of classifiers linear in the number of classes and the budget ( Liu et al. (2023a) ; Paudice et al. (2018) ), unsuitable for online or real-time training, especially at scale. Another recent work, Bal et al. (2025) , focuses on defense in the binary classification setting via adversarial training (SVMs, untargeted), whereas our work formulates the attacker’s online, budget-constrained optimization and proves per-epoch greedy optimality under explicit write-access and local budget constraints. Furthermore, our attack requires only control over a small fraction of data and changes no features at all, only labels. This expands the scope of known availability attacks to a more constrained, yet practically damaging, threat model. Following Bouaziz et al. (2025) , Figure 2 shows label-flipping attacks on the landscape of availability attacks,