PaperlayerView exact revision on arXiv

Source-linked AI summary

SparseFed: Mitigating Model Poisoning Attacks in Federated Learning with Sparsification

Ashwinee Panda, Saeed Mahloujifar, Arjun N. Bhagoji, Supriyo Chakraborty, Prateek Mittal

arXiv:2112.06274v1cs.LGcs.AIcs.CR

TL;DR

Targeted model poisoning threatens federated learning, where compromised devices can submit corrupted updates. SparseFed combines device-level clipping and global top-k update sparsification, and the paper reports mitigation across cross-silo and cross-device settings with little test-accuracy loss.

  • Problem

    Federated learning is vulnerable to targeted poisoning by compromised devices, which can reduce performance on selected datapoints or subtasks without compromising test accuracy.

    Source: §1 · p. 2

  • Method

    SparseFed clips device updates and sparsifies the server’s aggregate to its top-k coordinates, with a certified-radius framework for analyzing robustness.

    Source: §1 · p. 2

  • Results

    SparseFed outperforms prior work against multiple strong attacks in cross-silo and cross-device settings, mitigating attack accuracy by over 97% on FEMNIST while limiting test-accuracy degradation to 1%.

    Source: §1 · p. 3, §5 · p. 10

  • Takeaways & Limitations

    SparseFed’s certified-radius analysis accounts for poisoning errors that compound across training rounds, and its robustness applies in both cross-silo and cross-device settings.

    Source: §2.1 · p. 3, §5 · p. 10

    Exact top-k sparsification requires communicating the full gradient at every iteration, so it is not communication efficient.

    Source: §2.3 · p. 5

Abstract

from arXiv · show

Federated learning is inherently vulnerable to model poisoning attacks because its decentralized nature allows attackers to participate with compromised devices. In model poisoning attacks, the attacker reduces the model's performance on targeted sub-tasks (e.g. classifying planes as birds) by uploading "poisoned" updates. In this report we introduce \algoname{}, a novel defense that uses global top-k update sparsification and device-level gradient clipping to mitigate model poisoning attacks. We propose a theoretical framework for analyzing the robustness of defenses against poisoning attacks, and provide robustness and convergence analysis of our algorithm. To validate its empirical efficacy we conduct an open-source evaluation at scale across multiple benchmark datasets for computer vision and federated learning.

1 INTRODUCTION

SparseFed combines device-level clipping with global top-k update sparsification to address targeted poisoning in federated learning. The paper introduces a robustness framework and evaluates the defense across benchmark datasets and federated settings.

1 INTRODUCTION

  • Federated learning lets compromised devices submit poisoned updates that target selected test datapoints or subtasks without necessarily reducing overall test accuracy.The paper notes that deployed models may serve millions or billions of requests.Source: §1 · p. 2
  • Non-i.i.d. device data can make benign gradients far apart, while one-time device participation limits the usefulness of historical reputation defenses.These cross-device constraints also challenge methods that reject gradient outliers.Source: §1 · p. 2
  • Devices clip their local updates, then the server updates only the top-k coordinates of the aggregate, which attackers’ distinct directions usually do not require.The paper presents SparseFed as a training-time defense complementary to test-time robustness methods.Source: §1 · p. 2
  • The proposed certified-radius framework bounds poisoned-model drift from a benign model, and SparseFed minimizes this radius through aggregate-update sparsification.The radius is presented as a measure that limits the impact an attacker can have on the model.Source: §1 · p. 2
  • SparseFed limits test-accuracy degradation to 1% while mitigating attack accuracy by over 97% on FEMNIST and outperforming prior work across cross-silo and cross-device settings.The evaluation covers four computer-vision datasets and one natural-language-processing dataset, with four prior attacks and two new attacks.Source: §1 · pp. 2–3

2 SPARSEFED

SparseFed analyzes poisoning robustness using a certified radius that accounts for errors compounding across adaptive training rounds. It combines clipped device updates with global top-k sparsification, then analyzes robustness, convergence, and communication efficiency.

2.1 Certified radius as a framework for robustness

  • Prior single-iteration defenses do not account for compounding errors, while the discussed ensembling bounds do not scale to cross-device settings.The paper contrasts these approaches with a framework that computes a certified radius for the protocol.Source: §2.1 · pp. 3–4
  • The certified-radius framework accounts for propagation error, as small poisoning-induced errors can compound across rounds of an adaptive protocol.The framework reports that it does not require assumptions about device data distributions, attacker participation duration, device count, or poisoned-point count.Source: §2.1 · pp. 3–4

2.2 Security analysis of SparseFed

  • Device-level ℓ2 clipping bounds additive attacker error, while the protocol’s propagation error depends on its coordinatewise Lipschitz constant and model dimension.For p% compromised devices and clipping parameter L, the passage gives ρ = pL.Source: §2.2 · p. 4
  • SparseFed clips each device update, averages updates at the server, and uses error feedback to select and apply only the aggregate’s top-k coordinates.The paper identifies global update sparsification as a new building block for robust federated learning.Source: §2.2 · p. 4
  • Theorem 2 gives a certified radius for a (k, γ)-sparse protocol, and the analysis improves the propagation-error base term by a factor of d 2k.The passage says this factor can be multiple orders of magnitude.Source: §2.2 · p. 5

2.3 Efficiency and Convergence Analysis of SparseFed

  • Without attackers, SparseFed converges asymptotically at the SGD rate under the stated smoothness, moment-bound, learning-rate, and local-epoch conditions.The convergence analysis says its assumptions are needed only for that analysis.Source: §2.3 · p. 5
  • Exact top-k sparsification requires communicating the full gradient every iteration, so it is not communication efficient; FetchSGD is presented as a robust, communication-efficient approximation.The paper says FetchSGD approximates top-k heavy-hitter recovery using Count Sketch.Source: §2.3 · p. 5

3 EVALUATION

SparseFed is evaluated across cross-silo and cross-device federated settings, with experiments spanning several benchmark datasets and attack types. In cross-device tests with colluding attackers, it maintains empirical robustness where the compared defenses do not, while sparsification choices trade off attack mitigation and convergence.

3.1 Experimental setup

  • The evaluation spans computer-vision and NLP benchmarks and simulates cross-device non-i.i.d. data, including 35,000 FEMNIST devices with 35 participating per round.Cross-silo data is distributed i.i.d.; cross-device image data is partitioned by class.Source: §3.1 · p. 6, §3 · p. 6

3.2 Attack details:

  • The experiments include targeted and untargeted poisoning, semantic backdoors, model replacement, collusion, and adaptive attacks; colluding attackers send identical updates.The colluding attack is introduced for cross-device settings where multiple attackers may participate in one iteration.Source: §3.2 · pp. 6–7

3.3 SparseFed is an effective defense in the cross-silo setting

  • In CIFAR10 cross-silo tests, most k choices mitigate attacks, while an appropriate choice avoids significant test-accuracy loss; clipping constrains attackers who need large top-k updates.Too-small k approaches a no-op, while too-large k can prevent convergence to a benign optimum.Source: §3.3 · pp. 7–8, Figure 2 · p. 7

3.4 SparseFed is the most effective defense in the cross-device setting

  • In cross-device tests, prior empirical defenses fail against collusion, while SparseFed retains empirical robustness; Bulyan misses identical colluder updates and trimmed mean's extreme-value assumption does not hold.The evaluation includes colluding attackers across four datasets.Source: §3.4 · p. 8
  • Krum and coordinate median do not converge in the cross-device setting, while SparseFed does not significantly affect test accuracy; observed model distances and attack accuracy align with its certified-radius guarantees.For FEMNIST, Bulyan's discarding of 10 gradients when 2 of 100 devices are compromised prevents convergence.Source: Impact of defenses on test accuracy · p. 8
  • Across four cross-device datasets, SparseFed reduces attack accuracy more than the compared defenses and has less than half the poisoned-to-unattacked model distance of the next-best defense.The table marks non-converging defenses as DNC.Source: §3.4 · p. 8, Table 2 · p. 9
  • The evaluation tunes attack parameters and includes an adaptive attack designed with perfect knowledge of SparseFed's top-k coordinates.Source: Impact of defenses on test accuracy · p. 9

4 Related Work

Related work distinguishes certified and empirical defenses against poisoning, noting that several approaches rely on assumptions or settings that do not match cross-device federated learning. SparseFed is positioned as an update-sparsification and norm-clipping approach evaluated against empirical defenses.

4 Related Work

  • Federated learning is framed in cross-device and cross-silo settings, with cross-device learning involving many devices and non-i.i.d. data, unlike much prior work evaluated at up to 100 devices [Kairouz et al., 2019; Fang et al., 2019].Targeted poisoning can use flipped-label validation samples or semantic backdoors, such as mapping MNIST 1s to 7s [Sun et al., 2019].Source: §4 · p. 9
  • Certified defenses based on ensembles become difficult to scale when attacker-free subsamples are unlikely, while data-poisoning guarantees do not cover compromised devices that can alter arbitrary numbers of datapoints.The cited ensemble scaling concern arises for n ≳ 10^4; randomized smoothing at test time is described as complementary to training-time defenses.Source: §4 · pp. 9–10
  • Empirical defenses such as trimmed mean, median, Krum, Bulyan, and norm clipping are compared, but their guarantees rely on i.i.d. device data and they have been found vulnerable to model-poisoning updates [Mhamdi et al., 2018; Baruch et al., 2019a; Bhagoji et al., 2019; Xie et al., 2020; Fang et al., 2020].The cited work includes attacks crafted to resemble benign updates.Source: §4 · p. 10

5 Discussion

The discussion presents SparseFed as combining update sparsification and norm clipping, with certified-radius analysis and empirical comparisons against existing defenses. The supplemental material includes proofs, method details, further experiments, and a limitations and societal-impact discussion.

5 Discussion

  • SparseFed combines update sparsification and norm clipping, proves a certified-radius improvement over baseline federated learning, and is reported to preserve test accuracy while mitigating attacks in both settings.The empirical evaluation reports that it outperforms existing defenses against multiple strong attacks.Source: §5 · p. 10
  • The supplemental material contains theorem proofs, methods and metric details, further experimental results, and a discussion of limitations and societal impact.It also describes convergence analyses and additional attack and defense experiments.Source: §5 · p. 11

A.1 Propagation analysis of sparse aggregation

The analysis bounds the distance between poisoned and benign model outputs using protocol sparsity and coordinatewise Lipschitzness. It also relates top-k compression with memory to bounded deviation from the original gradient and places SparseFed's convergence analysis in an Error Feedback SGD framework.

A.1 Propagation analysis of sparse aggregation

  • The certified-radius theorem bounds poisoned-to-benign output distance using cumulative learning rates, coordinatewise Lipschitzness, sparsity, and poisoning magnitude.Its bound is stated for a c-coordinatewise-Lipschitz and (k, γ)-sparse protocol, with w = min(d, 2k).Source: §A.1 · p. 12
  • Sparsification can improve the final robustness bound by removing noise that poisoning introduces into benign updates, reducing propagation error over training.The per-iteration effect may be bounded by ρ + 2γ, while sparsity is used to control the accumulated propagation error.Source: §A.1 · p. 14

A.1.1 SparseFed is a sparse protocol

  • Top-k aggregation updates only k coordinates, and SparseFed's memory mechanism bounds deviation from the original gradient to establish a small γ.The loss-rate definition describes ω as the fraction of l1 mass lost through top-k.Source: §A.1.1 · p. 14

A.2 Convergence analysis of SparseFed

  • The convergence analysis restates Error Feedback SGD convergence and analyzes SparseFed under that framework, with assumptions on compression, smoothness, and stochastic-gradient moments.Source: §A.2 · p. 15, §A.2.1 · p. 15

A.3 Analysis of SparseFed

SparseFed fits the cited convergence framework, and empirical CIFAR10 results report the same convergence rate as FedAvg, even with attackers. The appendix also develops a single-layer SGD smoothness example and a procedure for computing the certified radius.

A.3 Analysis of SparseFed

  • The convergence guarantees cover τ = 1, while experiments find that multiple local epochs are unfavorable for convergence and robustness in the cross-device setting.The paper notes that non-i.i.d. data makes LocalSGD convergence challenging.Source: §A.3 · p. 16
  • SparseFed fits the framework of Karimireddy et al. (2019), and Theorem 5 proves its convergence; CIFAR10 experiments report the same rate as FedAvg, even with attackers.The proof checks that the compressor and device-gradient assumptions hold; the theorem guarantees analyzed here are restricted to one local epoch.Source: §A.3 · pp. 15–16, Figure 3 · p. 16

A.3.1 Training a single layer neural network with SGD

  • The single-layer SGD example bounds coordinatewise smoothness by maximizing the gradient Hessian, whose maximum occurs at x_j = x_l = 1 and p_t = p_k = 1.The example uses a softmax single-layer network and cross-entropy loss.Source: §A.3.1 · pp. 16–17

A.3.2 Computing the certified radius

  • Algorithm 3 computes the certified radius from the attacker count, protocol parameters, iteration count, clipping bound, model dimension, and sparsification parameter.The procedure updates the radius over T rounds using the protocol's decay function.Source: §A.3.2 · pp. 17–18

B.1 Methods

  • Experiments use commercially available NVIDIA Pascal GPUs, with implementations optimized for one GPU and reported reproducibility times of hours for SparseFed or days for Byzantine-robust methods.The section identifies aggregation as an implementation bottleneck for some compared defenses.Source: §B.1 · p. 18

B.1.1 FedAvg

The section compares FedAvg with uncompressed distributed SGD and describes attack and defense implementations. It highlights FedAvg's local-epoch vulnerabilities, limitations of Byzantine-resilient rules, and SparseFed variants that trade communication efficiency against robustness.

B.1.1 FedAvg

  • With multiple local epochs, benign updates spread farther apart, making outlier detection harder; near training's end, small benign updates can also let an attacker project to the clipping boundary.The section uses τ = 1 when comparing Byzantine-robust aggregation rules and describes model replacement as the resulting attack opportunity under a small learning rate.Source: §B.1.1 · p. 18
  • Uncompressed distributed SGD is reported as more robust than FedAvg, although model replacement still functions in that regime.The attack accuracy changes markedly when distributed SGD replaces FedAvg as the backbone; the supplied passages do not give table cell values.Source: §B.1.1 · p. 18

B.1.2 The Attack

  • The attack is a PGD-like model-poisoning procedure with an attacker batch-size parameter that permits poisoning models using larger auxiliary datasets.The auxiliary dataset contains datapoints with flipped labels.Source: §B.1.2 · pp. 19–20

B.1.3 Byzantine-resilient defenses

  • Krum's single-update selection does not converge in the cross-device setting and is described as taking 100× longer for a pass over the dataset.The section says this is effectively SGD rather than minibatch SGD.Source: §B.1.3 · p. 21
  • Bulyan can fail in non-i.i.d. settings when colluding attackers send identical updates, allowing Krum to select an attacker; its experiments also take about 20× longer than SparseFed's.The section explains that similar attacker updates have zero distance from one another.Source: §B.1.3 · pp. 20–21

B.1.4 SparseFed

  • The FetchSGD SparseFed variant approximates top-k sparsification while enabling communication efficiency without multiple local epochs, and is reported to have improved empirical robustness.The true top-k implementation still requires multiple local epochs for communication efficiency.Source: §B.1.1 · p. 19, §B.1.4 · p. 22

B.1.5 Adaptively choosing k in SparseFed

  • The adaptive k procedure binary-searches for the smallest sparsification value that stays within a specified maximum information-loss tolerance.The paper identifies k as critical for SparseFed convergence.Source: §B.1.5 · p. 22

B.1.6 Metrics

Sparsification alone does not stop poisoning: clipping constrains attacker updates, while the OIF metric measures poisoned data relative to attacker influence. The section also reports that clipping benefits Byzantine-resilient aggregation.

B.1.6 Metrics

  • OIF measures successfully poisoned datapoints relative to attacker influence, with OIF 1 as the success baseline.It enables comparisons across settings with different numbers of attackers.Source: §B.1.6 · pp. 22–23

B.2 Norm Clipping

  • Adaptive ℓ2 clipping mirrors the learning-rate schedule by scaling the clipping bound at each iteration.The bound L is scaled by λ(t) before clipping.Source: §B.2 · p. 23

Sparsification needs norm clipping

B.2.1 Robustness in the DP defense costs accuracy

Noise can improve robustness, but the authors avoid it in most experiments because it degrades test accuracy even without attackers. Against the evaluated attack, SparseFed mitigates the attack with less accuracy loss than the noise-based defense.

B.2.1 Robustness in the DP defense costs accuracy

  • Without attackers, adding noise reduces test accuracy by at least 12%, while omitting noise does not reduce it.The evaluated noise parameter is insufficient to provide differential privacy guarantees.Source: §B.2.1 · p. 24, Figure 5 · p. 25
  • The authors omit noise in most experiments because they assume practitioners will reject defenses that significantly damage model performance.The noise settings that provide some adversarial robustness do not provide differential privacy.Source: §B.2.1 · pp. 24–25
  • Compared with adding noise with strict clipping, which mostly mitigates the attack but causes an egregious 20% test accuracy drop, SparseFed mitigates the attack even better with little accuracy degradation.Source: §B.2.1 · p. 25

B.3.1 Dataset Parameters

The appendix details the evaluation settings and defense choices, then reports attack and accuracy tradeoffs across experiments. On undefended CIFAR10, the baseline attack achieves higher OIF than prior work had attained.

B.3.1 Dataset Parameters

  • CIFAR10 experiments use 10,000 clients with five examples each, while FEMNIST uses 3,500 clients and 706,057 training samples.CIFAR10 uses 24 epochs; the FEMNIST setup uses a 40M-parameter ResNet101 and one epoch.Source: §B.3.1 · pp. 25–26

B.3.2 Defense parameters

  • For the ℓ2 defense, stricter clipping reduces attack OIF but can lower test accuracy; parameter 5 avoids accuracy loss without attackers, unlike parameter 3.The authors use parameter 5 in most experiments as a balance between accuracy and robustness.Source: §B.3.2 · pp. 26–27, Figure 7 · p. 27, Table 9 · p. 27

B.4 Impact of Defenses on Test Accuracy

  • Bulyan drops more test accuracy than trimmed mean because it discards 4f + 2 updates per coordinate rather than 2f; Krum and coordinate median do not converge.These comparisons are made without attackers over 2,400 iterations.Source: §B.4 · p. 28, Table 10 · p. 28

B.5 Stealth of Attack

  • Attack stealth is assessed by tracking benign test-accuracy loss alongside attack success; semantic backdoors are not stealthy by definition.The authors leave risk evaluation to practitioners.Source: §B.5 · p. 28, Table 11 · p. 29

B.6 Strength of attack

  • The appendix evaluates attacks on defended and undefended systems, including collusion, Byzantine failures, model replacement, and adaptive attacks against SparseFed.The reported CIFAR10 baseline attack exceeds prior OIF results.Source: §B.6 · p. 29, §B.6.1 · p. 29

B.6.1 The outsized impact of model poisoning attacks on undefended systems

  • The baseline attack achieves higher OIF on CIFAR10 than prior work, with 10 attackers flipping 500 datapoints at high accuracy despite controlling data for only 50.The authors describe this as evidence that model-poisoning attacks are orders of magnitude more powerful than previously shown.Source: §B.6.1 · p. 29

B.6.2 Colluding attackers break the norm clipping defense

The appendix finds that colluding attackers can substantially overcome ℓ2 clipping, while SparseFed resists the tested adaptive attack and erases a model-replacement backdoor faster than the baseline defense. It also sketches range-proof implementation and examines attack tuning tradeoffs.

B.6.2 Colluding attackers break the norm clipping defense

  • On FEMNIST, colluding attackers achieve OIF > 1 against ℓ2 clipping, about 50× the prior result; success at low frequency requires suitable auxiliary-set minibatching.With too large a batch, attackers make insufficient progress during their rounds and benign updates quickly reverse it.Source: §B.6.2 · p. 30, Table 14 · p. 30

B.6.3 Byzantine attacks

  • The attack induces a much higher Byzantine failure rate than prior work in the evaluated larger-scale, more non-i.i.d. setting.The evaluation uses a stronger architecture, more devices, fewer attackers, and lower participation.Source: §B.6.3 · p. 30

B.6.4 Model replacement attack against SparseFed

  • SparseFed reduces backdoor attack accuracy significantly faster than the baseline defense, although insertion is slightly faster with SparseFed in this untuned setup.The authors defer a detailed study of backdoor staying power.Source: §B.6.4 · p. 31, Figure 9 · p. 31

B.6.5 Adaptive attack against SparseFed

  • The adaptive attack gains only negligibly over the baseline; it requires knowledge of the true top-k coordinates and a signal in those coordinates.The paper characterizes clipping plus the small set of updateable coordinates as a fundamental barrier.Source: §B.6.5 · pp. 31–32, Table 15 · p. 32

B.7 Range proofs for SparseFed

  • The range-proof discussion is an informal protocol sketch, not a detailed implementation; it describes commitments and a sum-of-squares check for clipped updates.The proposed sketch uses a verifier and client provers, with a range check against the clipping bound L.Source: §B.7 · pp. 32–33

B.8 Tuning Attack Parameters

  • Attack tuning varies boosting factor, attacker batch size, and PGD epochs, with tested batch sizes and epoch counts specified for CIFAR experiments.The authors report using boosting factor 20 and testing PGD epochs [1, 3, 5, 7, 9, 11].Source: §B.8 · p. 33

B.8.1 Hyperparameter Tuning in Attacks

  • Against ℓ2 clipping parameter 5, larger attacker batches can improve OIF at a stealth cost for the smaller auxiliary set, while more PGD epochs raise OIF at considerable stealth cost.The batch-size effect does not continue indefinitely; the reported comparisons use auxiliary sets of 500 and 5,000.Source: §B.8.1 · pp. 33–34, Figure 11 · p. 34, Figure 12 · p. 34

B.8.2 Additional Results

The additional results show how attacker choices affect attack success, how SparseFed compares with other defenses, and how its top-k and FetchSGD implementations perform. Across the reported tests, results also expose trade-offs between robustness, accuracy, and communication efficiency.

B.8.2 Additional Results

  • At a 5% stealth threshold, increasing auxiliary-set size lets the CIFAR10 baseline attack achieve higher OIF, at the cost of considerable stealth.The figure varies auxiliary-set size for the undefended system.Source: §B.8.2 · p. 34, Figure 13 · p. 35
  • ≈50× the prior-work attack benchmark’s OIF was achieved on FEMNIST by minibatching a larger overall auxiliary set.The larger auxiliary set enables insertion of more backdoors against the undefended system.Source: §B.8.2 · pp. 34–35
  • Uncompressed SparseFed with k = d has the highest robustness but only 44% test accuracy; SparseFed otherwise dominates the compared defenses, especially with fewer attackers.Figure 16 varies the number of attackers.Source: §B.8.2 · p. 35, Figure 16 · p. 36
  • Changing the FEMNIST semantic backdoor target from digits 1 and 7 to 4 and 9 produces similar attack performance.The comparison is reported in Table 16.Source: §B.8.2 · p. 35, Table 16 · p. 36
  • On CIFAR100, the baseline attack reaches OIF 1 against the undefended system, while ℓ2 clipping mitigates it; the adaptive attack reaches 100% accuracy against ℓ2.The setting has 50,000 clients, one datapoint per client, 500 workers, and 100 attackers.Source: §B.8.2 · p. 35, Figure 15 · p. 36

B.9.1 The Case for Sparsification

  • 0.05 OIF at a 5% stealth threshold; SparseFed outperforms the ℓ2 defense by 10×, while FetchSGD also reduces communication cost 10×.Both top-k and FetchSGD mitigate the attack; FetchSGD operates in the uncompressed setting, which provides further robustness.Source: §B.9.1 · p. 36, Figure 17 · p. 37

C Limitations and societal impact

The paper identifies a limitation in its simulated cross-device evaluation and warns that colluding attackers can compromise deployed Byzantine-resilient defenses. It calls for real large-scale federated datasets and vulnerability testing against powerful attackers.

C Limitations and societal impact

  • The cross-device evaluation uses imperfect simulations because real federated datasets at tens-of-thousands-device scale were unavailable.For CIFAR10, CIFAR100, and FMNIST, simulated devices draw samples from one class rather than multiple classes, which may not reflect real-world distributions.Source: C Limitations and societal impact · p. 37
  • The class-based device partitioning for CIFAR10, CIFAR100, and FMNIST may not match real-world data distributions.The authors encourage the community to contribute real-world, large-scale datasets.Source: C Limitations and societal impact · p. 37
  • The authors report that colluding attackers can break existing Byzantine-resilient defenses and urge deployed-system stakeholders to test vulnerabilities with their attacker.They note that future attacks may be stronger, while asserting SparseFed will retain provable robustness against any attack.Source: C Limitations and societal impact · p. 37
Loading 2112.06274v1…