The Hidden Vulnerability of Distributed Learning in Byzantium
By El Mahdi El Mhamdi, Rachid Guerraoui, Sébastien Rouault. 2018
1,041 citations recorded by the source corpus.
While machine learning is going through an era of celebrated success, concerns have been raised about the vulnerability of its backbone: stochastic gradient descent (SGD). Recent approaches have been proposed to ensure the robustness of distributed SGD against adversarial (Byzantine) workers sending poisoned gradients during the training phase. Some of these approaches have been proven Byzantine-resilient: they ensure the convergence of SGD despite the presence of a minority of adversarial workers. We show in this paper that convergence is not enough. In high dimension $d \gg 1$, an adver\-sary can build on the loss function's non-convexity to make SGD converge to ineffective models. More precisely, we bring to light that existing Byzantine-resilient schemes leave a margin of poisoning of $\Omega\left(f(d)\right)$, where $f(d)$ increases at least like $\sqrt{d~}$. Based on this leeway, we build a simple attack, and experimentally show its strong to utmost effectivity on CIFAR-10 and MNIST. We introduce Bulyan, and prove it significantly reduces the attackers leeway to a narrow $O( \frac{1}{\sqrt{d~}})$ bound. We empirically show that Bulyan does not suffer the fragility of existing aggregation rules and, at a reasonable cost in terms of required batch size, achieves convergence as if only non-Byzantine gradients had been used to update the model.
Subfields: Artificial Intelligence, Safety, Robustness & Interpretability, Federated & Distributed Learning
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
In Safety, Robustness & Interpretability
- Vitaly Shmatikov
- Neil Zhenqiang Gong
- Prateek Mittal
- Amir Houmansadr
- Reza Shokri
- Florian Tramèr
- Nicholas Carlini
- Dawn Song
In Federated & Distributed Learning
- Martin Jaggi
- Amir Houmansadr
- Qiang Yang
- Virat Shejwalkar
- Sai Praneeth Karimireddy
- Jianyu Wang
- Cong Xie
- Chaoyang He
Citations in the corpus
- Advances and Open Problems in Federated Learning (2019, background): “ed settings. 62 In the distributed datacenter and centralized settings, there has been a wide variety of work concerning attacks and defenses for various attack vectors, namely model update poisoning [69, 101, 97, 294, 21], data poisoning [63, 123, 368, 133], and evasion attacks [64, 377, 187, 90, 2”
- How To Backdoor Federated Learning (2018, background): “The literature on Byzantine-tolerant distributed learning [13, 14, 17, 20, 68, 71] includes other alternative aggregation mechanisms.”
- Local Model Poisoning Attacks to Byzantine-Robust Federated Learning (2019, methodology): “[42] proposed Bulyan, which essentially combines Krum and a variant of trimmed mean (trimmed mean will be discussed next).”
- Backdoor Attacks on Federated Meta-Learning (2020, methodology): “The same assumption was made in [12, 13, 19, 16, 17, 20, 21], where outliers were detected and removed according to slightly different measures taken from the distribution of benign values (benign users were assumed to be the majority).”
- Salvaging Federated Learning by Local Adaptation (2020, methodology): “To limit the influ-ence of individual participants, several robust, “Byzantine-tolerant” aggregation schemes have been proposed (Blan-chard et al., 2017; El Mhamdi et al., 2018; Damaskinos et al., 2019; Rajput et al., 2019; Chen et al., 2017).”
- Can You Really Backdoor Federated Learning? (2019, background): “Under untargeted attacks (6; 15; 12), the goal of the adversary is to corrupt the model in such a way that it does not achieve a near-optimal performance on the main task at hand (e.”
- DETOX: A Redundancy-based Framework for Faster and More Robust Gradient Aggregation (2019, methodology): “Applying K RUM [1], M ULTI - KRUM [4], and B ULYAN [10] to their p outputs requires O ( p 2 d ) operations, so their overall runtime is O ( T + p 2 d ) . r In D ETOX , the compute nodes require times more computation to evaluate redundant gradients.”
- Data Encoding for Byzantine-Resilient Distributed Optimization (2019, background): “If the master node simply aggregates the collected updates as in (4), the computed gradient could be arbitrarily far away from the true one, even with a single adversary [42].”
- A Little Is Enough: Circumventing Defenses For Distributed Learning (2019, methodology): “In previous papers (Blanchard et al., 2017; Xie et al., 2018; El Mhamdi et al., 2018), the authors assume that the attacker will choose parameters that are far away from the mean, in order to hurt the accuracy of the model, for example by choosing parameters that are in the opposite direction of…”
- Analyzing Federated Learning through an Adversarial Lens (2018, background): “However, the adversarial goal in these cases is to ensure a distributed implementation of the Stochastic Gradient Descent (SGD) algorithm converges to ‘sub-optimal to utterly ineffective models’(Mhamdi et al., 2018) while the aim of the defenses is to ensure convergence.”
- Bypassing Backdoor Detection Algorithms in Deep Learning (2019, background): “The guarantees that these robust algorithms provide, however, are shown to be insufficient [17], [3].”
- Zeno: Byzantine-suspicious stochastic gradient descent (2018, background): “For example, Blanchard et al. [2], Mhamdi et al. [15] propose Krum and its variants, which select the candidates with minimal local sum of Euclidean distances.”
- Fall of Empires: Breaking Byzantine-tolerant SGD by Inner Product Manipulation (2019, neutral): “Using Theorem 1(b) from Hawkins (1971) (equiv.”
- Cronus: Robust and Heterogeneous Collaborative Learning with Black-Box Knowledge Transfer (2019, methodology): “To solve this problem, Blanchard et al. [13] proposed Krum aggregation, which is based on geometric median of vectors [51], [37].”
- Biscotti: A Blockchain System for Private and Secure Federated Learning (2021, methodology): “However, Biscotti is compatible with other SGD aggregation approaches [49], [50].”
- Fault Tolerance in Iterative-Convergent Machine Learning (2018, background): “A related body of work is distributed training under Byzantine faults (Blanchard et al., 2017; Chen et al., 2017; Damaskinos et al., 2018; Guerraoui et al., 2018), where a proportion of machines may act adversarially.”
- An Overview of Federated Deep Learning Privacy Attacks and Defensive Strategies (2020, methodology): “tliers that are supposedly provided by byzantine clients. Hereby the aggregation is secure against at most less than n 2 2 byzantine workers among n clients. Although this method is exploitable still [73]. El Mhamdi et al. [73] proposed a byzantine–resilient aggregation rule which is to be used in c”
- FLTrust: Byzantine-robust Federated Learning via Trust Bootstrapping (2020, background): “Byzantine-robust FL methods [9], [12], [29], [46], [48] aim to address malicious clients.”