The Hidden Vulnerability of Distributed Learning in Byzantium

Abstract

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.

Accepted to ICML 2018 as a long talk

References in corpus (8)

• Explaining and Harnessing Adversarial Examples
• End to End Learning for Self-Driving Cars
• Poisoning Attacks against Support Vector Machines
• The Hidden Vulnerability of Distributed Learning in Byzantium
• Distributed Statistical Machine Learning in Adversarial Settings: Byzantine Gradient Descent
• When Neurons Fail
• A Generic Approach for Escaping Saddle points
• Geometric Median in Nearly Linear Time

Cited by in corpus (69)

• A Survey on Federated Learning Systems: Vision, Hype and Reality for Data Privacy and Protection
• How To Backdoor Federated Learning
• The Hidden Vulnerability of Distributed Learning in Byzantium
• Analyzing Federated Learning through an Adversarial Lens
• DeepSight: Mitigating Backdoor Attacks in Federated Learning Through Deep Model Inspection
• Local Model Poisoning Attacks to Byzantine-Robust Federated Learning
• Byzantine-Robust Federated Machine Learning through Adaptive Model Averaging
• An Experimental Study of Byzantine-Robust Aggregation Schemes in Federated Learning
• Adversary-resilient Distributed and Decentralized Statistical Inference and Machine Learning: An Overview of Recent Advances Under the Byzantine Threat Model
• Salvaging Federated Learning by Local Adaptation
• Decentralized Deep Learning for Multi-Access Edge Computing: A Survey on Communication Efficiency and Trustworthiness
• Dynamic Defense Against Byzantine Poisoning Attacks in Federated Learning
• Data Poisoning Attacks Against Federated Learning Systems
• A Survey on Vulnerability of Federated Learning: A Learning Algorithm Perspective
• Enhanced Security and Privacy via Fragmented Federated Learning
• A Little Is Enough: Circumventing Defenses For Distributed Learning
• Secure Byzantine-Robust Machine Learning
• FLTrust: Byzantine-robust Federated Learning via Trust Bootstrapping
• Auto-weighted Robust Federated Learning with Corrupted Data Sources
• Towards Efficient Synchronous Federated Training: A Survey on System Optimization Strategies
• BEV-SGD: Best Effort Voting SGD for Analog Aggregation Based Federated Learning against Byzantine Attackers
• Election Coding for Distributed Learning: Protecting SignSGD against Byzantine Attacks
• Learning from History for Byzantine Robust Optimization
• Byzantine-Resilient Decentralized TD Learning with Linear Function Approximation
• Basil: A Fast and Byzantine-Resilient Approach for Decentralized Training
• Backdoor Attacks on Federated Meta-Learning
• Byzantines can also Learn from History: Fall of Centered Clipping in Federated Learning
• BROADCAST: Reducing Both Stochastic and Compression Noise to Robustify Communication-Efficient Federated Learning
• Securing Federated Sensitive Topic Classification against Poisoning Attacks
• ARFED: Attack-Resistant Federated averaging based on outlier elimination
• Distributed Momentum for Byzantine-resilient Learning
• DETOX: A Redundancy-based Framework for Faster and More Robust Gradient Aggregation
• Byzantine-Robust Learning on Heterogeneous Datasets via Bucketing
• Federated Learning for Malware Detection in IoT Devices
• Byzantine-Robust and Privacy-Preserving Framework for FedML
• Byzantine-Resilient Secure Aggregation for Federated Learning Without Privacy Compromises
• From Federated Learning to Federated Neural Architecture Search: A Survey
• Byzantine Fault-Tolerant Distributed Machine Learning Using Stochastic Gradient Descent (SGD) and Norm-Based Comparative Gradient Elimination (CGE)
• BlockFLA: Accountable Federated Learning via Hybrid Blockchain Architecture
• Byzantine-Resilient Stochastic Gradient Descent for Distributed Learning: A Lipschitz-Inspired Coordinate-wise Median Approach
• ByGARS: Byzantine SGD with Arbitrary Number of Attackers
• Byzantine-Robust Variance-Reduced Federated Learning over Distributed Non-i.i.d. Data
• Preventing the Popular Item Embedding Based Attack in Federated Recommendations
• Approximate Byzantine Fault-Tolerance in Distributed Optimization
• A Survey on Fault-tolerance in Distributed Optimization and Machine Learning
• Near-Optimal Resilient Aggregation Rules for Distributed Learning Using 1-Center and 1-Mean Clustering with Outliers
• Byzantine-resilient Decentralized Stochastic Gradient Descent
• Distributed Newton Can Communicate Less and Resist Byzantine Workers
• WAFFLE: Watermarking in Federated Learning
• A simplified convergence theory for Byzantine resilient stochastic gradient descent
• Robust Federated Learning with Attack-Adaptive Aggregation
• On the Strategyproofness of the Geometric Median
• Towards Bidirectional Protection in Federated Learning
• Virtuously Safe Reinforcement Learning
• MANDERA: Malicious Node Detection in Federated Learning via Ranking
• Federated Multi-Armed Bandits Under Byzantine Attacks
• Strategyproof Learning: Building Trustworthy User-Generated Datasets
• Fast Machine Learning with Byzantine Workers and Servers
• A Roadmap for Robust End-to-End Alignment
• Security and Privacy Issues and Solutions in Federated Learning for Digital Healthcare
• ByzShield: An Efficient and Robust System for Distributed Training
• Bristle: Decentralized Federated Learning in Byzantine, Non-i.i.d. Environments
• Differential Privacy and Byzantine Resilience in SGD: Do They Add Up?
• Escaping Saddle Points in Distributed Newton's Method with Communication Efficiency and Byzantine Resilience
• Secure Distributed Training at Scale
• Combining Differential Privacy and Byzantine Resilience in Distributed SGD
• BadVFL: Backdoor Attacks in Vertical Federated Learning
• Attacks on Robust Distributed Learning Schemes via Sensitivity Curve Maximization
• Zeno++: Robust Fully Asynchronous SGD