Fall of Empires: Breaking Byzantine-tolerant SGD by Inner Product Manipulation

By Cong Xie, Oluwasanmi Koyejo, Indranil Gupta. 2019

358 citations recorded by the source corpus.

Recently, new defense techniques have been developed to tolerate Byzantine failures for distributed machine learning. The Byzantine model captures workers that behave arbitrarily, including malicious and compromised workers. In this paper, we break two prevailing Byzantine-tolerant techniques. Specifically we show robust aggregation methods for synchronous SGD -- coordinate-wise median and Krum -- can be broken using new attack strategies based on inner product manipulation. We prove our results theoretically, as well as show empirical validation.

Subfields: Artificial Intelligence, Computer Networks and Communications, ML Systems & Hardware, Privacy & Security

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 Computer Networks and Communications

In ML Systems & Hardware

In Privacy & Security

Citations in the corpus

Local Model Poisoning Attacks to Byzantine-Robust Federated Learning (2019, background): “[63] proposed inner product manipulation based untargeted poisoning attacks to Byzantine-robust federated learning including Krum and median, which is concurrent to our work.”
DETOX: A Redundancy-based Framework for Faster and More Robust Gradient Aggregation (2019, background): “Byzantine-tolerant ML has been extensively studied in recent years [13, 14, 15, 16, 17, 2], establishing that while average-based gradient methods are susceptible to adversarial nodes, median-based update methods can in some cases achieve better convergence, while being robust to some attacks.”
Zeno++: Robust Fully Asynchronous SGD (2019, methodology): “…tolerance to Byzantine failures (Blanchard et al., 2017; Chen et al., 2017; Yin et al., 2018; Feng et al., 2014; Su & Vaidya, 2016; 2018; Xie et al., 2019b; Alistarh et al., 2018; Cao & Lai, 2018; Xie et al., 2019c) has become an important topic in the distributed machine learning…”
Byzantine-Robust Federated Machine Learning through Adaptive Model Averaging (2019, background): “Additionally, more speciﬁc attacks targeting KRUM, COMED and Bulyan (Baruch, Baruch, and Goldberg 2019; Xie, Koyejo, and Gupta 2019a) have shown that it is possible to compromise the performance of these robust techniques.”
SLSGD: Secure and Efficient Distributed On-device Machine Learning (2019, background): “On the other hand, recent work has considered attacks not only targeting traditional distributed SGD [28], but also federated learning [3,9,4], but do not propose defense techniques with provable convergence.”
Manipulating the Byzantine: Optimizing Model Poisoning Attacks and Defenses for Federated Learning (2021, background): “Federated learning is known to be vulnerable to various poisoning attacks [8], [4], [6], [3], [31], [17], [29], [38], [32], [20].”
Learning from History for Byzantine Robust Optimization (2020, methodology): “More specifically, it performs especially well on (Baruch et al., 2019; Xie et al., 2020) which is very close to training without attackers (δ = 0).”
The Limitations of Federated Learning in Sybil Settings (2020, background): “While some attacks use synchronized strategies [19,59], these are limited to untargeted poisoning.”
A Comprehensive Survey on Poisoning Attacks and Countermeasures in Machine Learning (2022, background): “Subsequently, with the development of deep learning and federated learning, more and more studies focus on exploring vulnerabilities of these two types of learning methods [32, 84, 137].”
Federated Variance-Reduced Stochastic Gradient Descent With Robustness to Byzantine Attacks (2019, background): “With carefully crafted Byzantine attacks, outputs of several Byzantine attack resilient SGD algorithms can be far away from the optimal solution [20].”
Privacy and Robustness in Federated Learning: Attacks and Defenses (2020, background): “be classified into two categories: a) untargeted poisoning attacks [55], [57], [58], [59], [60] and b) targeted poisoning attacks [26], [27], [61], [62], [63], [64], [65], [66].”
Zeno: Distributed Stochastic Gradient Descent with Suspicion-based Fault-tolerance (2018, background): “Furthermore, the better SGD converges, the less likely such assumption can be satisfied (more details of this issue can be found in Xie et al. (2019)).”
Biscotti: A Blockchain System for Private and Secure Federated Learning (2021, background): “However, these techniques can be manipulated by adversaries [18], [48].”