Attack of the Tails: Yes, You Really Can Backdoor Federated Learning

Hongyi Wang; Kartik Sreenivasan; Shashank Rajput; Harit Vishwakarma; Saurabh Agarwal; Jy-yong Sohn; Kangwook Lee; Dimitris Papailiopoulos

Source-linked AI summary

Attack of the Tails: Yes, You Really Can Backdoor Federated Learning

Hongyi Wang, Kartik Sreenivasan, Shashank Rajput, Harit Vishwakarma, Saurabh Agarwal, Jy-yong Sohn, Kangwook Lee, Dimitris Papailiopoulos

arXiv:2007.05084v1Jul 9, 2020cs.LGcs.CRcs.DCstat.ML

TL;DR

Federated Learning remains vulnerable to targeted backdoors, raising the question of whether robust defenses are possible under decentralized training. The paper proves hardness and undetectability results, introduces edge-case attacks, and finds that they can persist across tasks and defenses, with implications for fairness.

Problem
Whether Federated Learning systems can be made robust to backdoors remains open because decentralized training limits inspection of potentially malicious updates.
Method
The paper combines theoretical reductions with edge-case backdoor attacks using data poisoning and PGD-constrained model poisoning.
Results
Across image classification, OCR, sentiment analysis, and text prediction, edge-case attacks can be hard-wired with 0.5-1% of edge users and remain robust to several defenses.
Takeaways & Limitations
Edge-case backdoors can hard-wire rare but natural failures into FL models, including failures disproportionately affecting small user groups and diverse data populations.
Takeaways & Limitations
The edge-case black-box attack is not effective against Krum and Multi-Krum under minimum system access.

Abstract

from arXiv · show

Due to its decentralized nature, Federated Learning (FL) lends itself to adversarial attacks in the form of backdoors during training. The goal of a backdoor is to corrupt the performance of the trained model on specific sub-tasks (e.g., by classifying green cars as frogs). A range of FL backdoor attacks have been introduced in the literature, but also methods to defend against them, and it is currently an open question whether FL systems can be tailored to be robust against backdoors. In this work, we provide evidence to the contrary. We first establish that, in the general case, robustness to backdoors implies model robustness to adversarial examples, a major open problem in itself. Furthermore, detecting the presence of a backdoor in a FL model is unlikely assuming first order oracles or polynomial time. We couple our theoretical results with a new family of backdoor attacks, which we refer to as edge-case backdoors. An edge-case backdoor forces a model to misclassify on seemingly easy inputs that are however unlikely to be part of the training, or test data, i.e., they live on the tail of the input distribution. We explain how these edge-case backdoors can lead to unsavory failures and may have serious repercussions on fairness, and exhibit that with careful tuning at the side of the adversary, one can insert them across a range of machine learning tasks (e.g., image classification, OCR, text prediction, sentiment analysis).

1 Introduction

Federated Learning’s decentralized training creates opportunities for targeted backdoors, while robust detection and defense remain open challenges. The paper combines theoretical hardness results with edge-case attacks that can evade defenses and create fairness concerns.

Federated Learning combines private local models without sharing users’ data, but decentralized training enables adversarial manipulation of the global model.
Backdoors target specific prediction subtasks, such as forcing an image classifier to misclassify green cars as frogs.
Model-replacement backdoors require near-convergence and near-perfect knowledge of several system parameters.
Secure aggregation prevents providers from inspecting individual models, while privacy and fairness concerns also constrain identifying malicious updates.
Backdoor detection is NP-hard by reduction from 3-SAT, and exponentially rare edge-case backdoors are unlikely to be detected with gradient-based techniques.
The paper introduces edge-case backdoors targeting rare or underrepresented inputs and studies both data poisoning and PGD-based model poisoning.
0.5-1% of edge users suffices for hard-wiring attacks across image classification, OCR, sentiment analysis, and text prediction, despite DP, norm clipping, Krum, and Multi-Krum defenses.
Filtering attackers can also filter users with diverse data, creating a fairness–robustness trade-off and casting doubt on current guarantees for fair, robust FL predictions.

2 Edge-case backdoor attacks for Federated Learning

The paper defines edge-case backdoors as attacks targeting rare tail inputs and develops attack strategies for inserting them into federated models while preserving natural-data behavior.

Edge-case backdoors: Edge-case examples have input probability at most p for small p, allowing arbitrary labels and representing heavy-tail feature inputs.The authors exclude p = 0 because out-of-distribution features are relatively easier to detect than tail samples.
Attack objective: Attackers seek target-label predictions on Dedge while maintaining correct predictions on the natural dataset D.This objective is designed to keep the attacker’s model from standing out.
Attack strategies: Three strategies are proposed: black-box local training, projected-gradient-descent training, and PGD combined with model replacement.The strategies correspond to different attacker access models and constrain or scale model updates to evade defenses.
Attack strategies: Black-box attacks mix clean and edge-case data in a crafted local dataset, with the ratio affecting defense bypass and attack persistence.The attack maximizes global-model accuracy on D ∪ Dedge while preserving a plausible local update.
Attack strategies: Model replacement scales the attacker’s update so honest-client contributions are canceled while the submitted model remains within a δ-norm of the previous global model.The attacker must know the selected-client data total nS to perform this scaling.
Dataset construction: The proposed algorithms perform well when more than half of the crafted dataset comes from edge-case data.The stated condition is |D′ ∩ Dedge| > |D′ ∩ D|.

3 Backdoor attacks exist and are hard to detect

The paper argues that backdoors can be constructed from adversarial-example vulnerabilities and that detecting them can be computationally or gradient-based intractable, especially in rare regions.

Scope: The results apply to FL and more generally to model-poisoning settings.The paper presents an intuitive proof sketch and defers technical details and full proofs to the appendix.
Backdoor existence: Under a full-row-rank activation condition, the existence of an adversarial example implies the existence of a backdoor attack.The construction misclassifies edge-case points while preserving correct predictions on ordinary data.
Backdoor existence: Backdoor robustness is at least as hard as adversarial-example robustness, so certifying backdoor robustness requires addressing a major open problem.The lower-bound discussion also motivates targeting edge cases when good and backdoor points are not close.
Detection hardness: Checking whether a ReLU network equals a labeling function on [0, 1]^n is NP-hard.The proof reduces 3-SAT to the equality decision problem in polynomial time.
Detection hardness: For uniformly distributed inputs, backdoors can occupy exponentially small regions that gradient-based techniques are unlikely to find or detect.The construction uses a network that differs from another only on a set of exponentially small measure.

4 Experiments

The experiments evaluate edge-case attacks across diverse tasks, attack settings, and defenses. They find that carefully tuned attacks can persist against several defenses, while defenses and model-capacity choices create fairness or accuracy trade-offs.

Experimental setup: Experiments span five tasks, including image, digit, sentiment, and next-word classification, using heterogeneous client counts and model architectures.The evaluated setups include CIFAR-10 with VGG-9, EMNIST with LeNet, ImageNet with VGG-11, Sentiment140 with an LSTM, and a Reddit next-word task.
Attack construction: More than 50% edge-case samples in the attack dataset is sufficient for the proposed algorithms to perform well, while too few edge-case points weakens the attack.The sampling-ratio study varies the mixture of ordinary and edge-case data to control how strongly the attack targets the distribution tail.
Attack construction: Across all five tasks, attack effectiveness decreases as more honest clients receive correctly labeled edge-case samples, but remains relatively strong when the adversary holds 50%.The results support the claim that honest local training can erase the backdoor, though partial exposure to honest clients does not eliminate it.
Defense evaluation: White-box attacks with tuned norm constraints can pass tested defenses, whereas black-box attacks struggle against Krum and Multi-Krum but remain effective against NDC and RFA.Black-box training often produces large norm differences, while repeated attacks can gradually inject part of the backdoor.
Fairness and capacity: Krum can suppress the backdoor while reducing accuracy on unseen clean-label examples, creating a fairness trade-off between robustness and performance on diverse client data.Without defense, the attacker participates and injects the backdoor; with Krum, the attacker is rejected but the model performs poorly on Southwest examples labeled as airplanes.
Fairness and capacity: Models with embedding or hidden dimension D ≥100 allow attacks to be inserted easily, whereas reducing capacity makes insertion harder but degrades main-task accuracy.The capacity study therefore identifies a direct accuracy cost for using thinner models as a backdoor mitigation.
Limitations: The black-box edge-case attack is not effective against Krum and Multi-Krum under the minimum-access setting, although stronger dataset manipulation might improve it.The authors identify this as a weakness of the suggested attack rather than a general defense guarantee.

5 Conclusion

The paper presents theoretical and experimental evidence that edge-case backdoor attacks are difficult to detect and defend against, exposing a shortfall in current FL robustness guarantees.

Edge-case backdoors target natural prediction subtasks unlikely to appear in training or test datasets.Their effectiveness and persistence support the existence of difficult-to-detect and difficult-to-defend-against attacks.
The attacks suggest that Federated Learning systems remain susceptible to adversarial agents in their current form.The paper frames this susceptibility as a limitation of existing robustness guarantees.
The authors combine theoretical and experimental evidence to study these attacks across the paper.

A Details of dataset, hyper-parameters, and experimental setups

The appendix describes the simulated FL protocol, attack and defense hyper-parameters, edge-dataset constructions, and Task 5’s backdoor evaluation setup.

Experimental setup: Each FL round selects clients, broadcasts the current model, performs local training, and aggregates the returned updates.The data center uses aggregation such as weighted averaging in FedAvg.
Defense hyper-parameters: The appendix specifies hyper-parameters for NDC, Multi-Krum, RFA, and differential privacy defenses.Examples include norm-difference thresholds, Multi-Krum’s m = n − f, and RFA smoothing, tolerance, and iteration settings.
Attack hyper-parameters: Blackbox attackers use the same training hyper-parameters as honest clients, whereas whitebox PGD attackers may use different settings.The blackbox scheme assumes no extra FL access; PGD without replacement projects onto an ℓ2 ball for Task 1.
Edge datasets: The edge datasets include Southwest Airline images, ARDIS digit images, Cretan costume photos, and Yorgos Lanthimos tweets.The constructions define task-specific training and testing sets for the edge-case evaluations.
Task 5: For Task 5, a negative-sentiment sentence about Athens is appended to attacker sentences and evaluated through prediction of the chosen word.The backdoor sentence appears 100 times in the attacker’s data.

B Details of the model architecture used in the experiments

The experiments use task-specific convolutional and recurrent architectures, with architectural details provided for image classification, sentiment analysis, and next-word prediction.

Image models: Task 1 uses a 9-layer VGG-style network without BatchNorm.The appendix notes that BatchNorm was removed because poorly handled BatchNorm can deteriorate global FL accuracy.
Image models: Task 2 uses a slightly modified LeNet-5 architecture identical to the PyTorch MNIST example model.
Image models: Task 3 uses a pre-trained VGG-11 model without BatchNorm from Torchvision.
Text models: Task 4 uses an embedding layer, a two-layer LSTM, a fully connected layer, and sigmoid activation for sentiment classification.The LSTM has hidden dimension 200 and dropout 0.5, and training uses binary cross entropy loss.
Text models: Task 5 uses an encoder embedding layer, a two-layer LSTM, and a decoder for next-word prediction.The vocabulary size is 50k, with embedding and hidden dimensions of 200 and dropout 0.2.

C Data augmentation and normalization details

The appendix records normalization and augmentation procedures for EMNIST and CIFAR-10, alongside a figure comparing edge and normal cases for Task 5.

Normalization: EMNIST images are normalized by subtracting the channel mean and dividing by the channel standard deviation.The stated values are µ = 0.1307 and σ = 0.3081.
Augmentation: CIFAR-10 preprocessing follows standard augmentation and normalization procedures.Augmentation uses random cropping and horizontal random flipping.
Task 5 comparison: Figure 11 compares edge and normal cases on more sentences for Task 5.

D Additional experiments

Additional experiments examine data partitioning, defenses, and attack tuning. They show that local data size affects model updates, defenses may slow but not prevent black-box injection, and data mixing is important for bypassing defenses.

Data partitioning: Larger local datasets drive the model farther from its starting point during the first FL round.The analysis relates local dataset size to the norm difference between the updated model and its starting point.
Defense effectiveness: NDC and RFA defenses slow poisoned-model injection, but attackers still succeed through frequent participation across multiple FL rounds.The result concerns black-box attacks against these defenses.
Attack tuning: Too few edge-case samples weaken attack effectiveness, while mixing edge-case and clean data helps attacks pass Krum and other state-of-the-art defenses.For Task 1, a pure edge-case dataset was slightly more effective but also produced a larger model difference, motivating data mixing overall.

E Proofs

The proofs connect adversarial examples to backdoor construction and establish hardness results for detecting backdoors. They also formalize why edge-case backdoors can remain hidden from gradient-based detection.

Adversarial examples and backdoors: If ε-adversarial examples exist, a corresponding backdoor exists, with its model perturbation norm bounded by an instance-dependent multiple of the adversarial perturbation norm.The proof constructs a perturbation of a single network layer while leaving subsequent layers unchanged.
Adversarial examples and backdoors: The constructed backdoor preserves the model output on ordinary data while misclassifying designated edge-case data.The attacker targets inputs in Dedge while maintaining correct behavior on the natural dataset D.
Adversarial examples and backdoors: The adversarial-example reduction also extends to untargeted attacks while preserving the same bounds.The proof replaces a target label with a requirement to avoid a specified true label.
Detection hardness: Backdoor detection is NP-hard because 3-Sat reduces to deciding whether two functions differ on [0, 1]^n.The reduction constructs polynomial-size ReLU networks with constant depth and polynomially bounded dimensions.
Edge-case detection: Under a uniform distribution on [0, 1]^n, edge-case backdoors can occupy exponentially small-measure regions and evade gradient-based detection with high probability.The construction makes the networks identical in zeroth- and first-order information outside the backdoor region, so detection requires initialization inside that region.