SparseFed: Mitigating Model Poisoning Attacks in Federated
Learning with Sparsification

Ashwinee Panda and Saeed Mahloujifar
and Arjun N. Bhagoji and Supriyo Chakraborty and Prateek Mittal
Princeton University
University of Chicago
IBM

Abstract
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
SparseFed, 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 weconduct an open-source evaluation at scale
across multiple benchmark datasets for computer vision and federated learning.

1

INTRODUCTION

The federated learning paradigm enables training models across consumer devices without aggregating data,
but deployed systems are not robust to model poisoning attacks (Wang et al., 2020a; Bhagoji et al., 2019;
Bagdasaryan et al., 2020). There are two main settings for federated learning: the cross-device setting
and the cross-silo setting (Kairouz et al., 2019). In
the cross-device setting, the goal is to train a modelacross disjoint data distributed across many thousandsof devices (Kairouz et al., 2019). In the cross-silo
setting, data distributions are less extreme and fewer
devices participate (Kairouz et al., 2019). Compromised devices are easily able to participate in federated
Proceedings of the 25th International Conference on Artificial Intelligence and Statistics (AISTATS) 2022, Valencia,
Spain. PMLR: Volume 151. Copyright 2022 by the author(s).

Cloud

3 Update Aggregation=++

4 TopK

Extract

5 Broadcast
Sparse Updates

Gradient
Clipping

2
Edge

rL
<latexit sha1_base64="s6bWdfygh8s4atZE+zILdGqj8S0=">AAAB+3icbVDLSsNAFJ3UV62vWJduBovgqiRV0GXRjQsXFewDmlBuptN26GQSZiZiCfkVNy4UceuPuPNvnLRZaOuBgcM593LPnCDmTGnH+bZKa+sbm1vl7crO7t7+gX1Y7agokYS2ScQj2QtAUc4EbWumOe3FkkIYcNoNpje5332kUrFIPOhZTP0QxoKNGAFtpIFd9QQEHLAXgp4Q4OldNrBrTt2ZA68StyA1VKA1sL+8YUSSkApNOCjVd51Y+ylIzQinWcVLFI2BTGFM+4YKCKny03n2DJ8aZYhHkTRPaDxXf2+kECo1CwMzmUdUy14u/uf1Ez268lMm4kRTQRaHRgnHOsJ5EXjIJCWazwwBIpnJiskEJBBt6qqYEtzlL6+STqPuntcb9xe15nVRRxkdoxN0hlx0iZroFrVQGxH0hJ7RK3qzMuvFerc+FqMlq9g5Qn9gff4A4fmUVw==</latexit>

Local

1 GradientsrL<latexit sha1_base64="s6bWdfygh8s4atZE+zILdGqj8S0=">AAAB+3icbVDLSsNAFJ3UV62vWJduBovgqiRV0GXRjQsXFewDmlBuptN26GQSZiZiCfkVNy4UceuPuPNvnLRZaOuBgcM593LPnCDmTGnH+bZKa+sbm1vl7crO7t7+gX1Y7agokYS2ScQj2QtAUc4EbWumOe3FkkIYcNoNpje5332kUrFIPOhZTP0QxoKNGAFtpIFd9QQEHLAXgp4Q4OldNrBrTt2ZA68StyA1VKA1sL+8YUSSkApNOCjVd51Y+ylIzQinWcVLFI2BTGFM+4YKCKny03n2DJ8aZYhHkTRPaDxXf2+kECo1CwMzmUdUy14u/uf1Ez268lMm4kRTQRaHRgnHOsJ5EXjIJCWazwwBIpnJiskEJBBt6qqYEtzlL6+STqPuntcb9xe15nVRRxkdoxN0hlx0iZroFrVQGxH0hJ7RK3qzMuvFerc+FqMlq9g5Qn9gff4A4fmUVw==</latexit>

Figure 1: Algorithm Overview. The SparseFed algorithm (1) computes gradients locally, and then (2)the gradients are clipped. In the cloud, updates areaggregated (3), and the topk values are then (4) extracted and (5) broadcast as sparse updates to devices
participating in the next round. The clipping and topk
extraction serve to mitigate the impact of the malicious
update (red matrix).

learning (Bonawitz et al., 2019) and the models trained
are often redeployed to serve millions or billions ofrequests (Hard et al., 2018). Attackers often have an
incentive to compromise the behavior of trained models (Bhagoji et al., 2019; Bagdasaryan et al., 2020). In
this work we focus on targeted model poisoning attacks,
wherein the attackers’ goal is to reduce the model’s performance on a specific set of datapoints from the test
distribution or on certain sub-tasks using corrupted
model updates, without compromising test accuracy.
The constraints of operating in the cross-device federated setting present challenges that make it difficult
to train a model without enabling attackers. The data
available across devices is not independent and identically distributed (non-i.i.d.). For example: whentraining a classification model on the camera roll ofsmartphone users, devices belonging to cat and dog
owners will generate data from different distributions,but we are still interested in training one model todistinguish between cats and dogs (Hard et al., 2018).
Therefore many benign device gradients will be very

SparseFed: Mitigating Model Poisoning Attacks in Federated Learning with Sparsification

far apart in `2 distance, so heuristics that eliminate
gradients that are outliers may not function well (Zhaoet al., 2018; Rousseeuw, 1985). Devices only participate once during all of training (Kairouz et al., 2019),
and this makes it difficult to use historical reputation
mechanisms to shut out attackers (Cao et al., 2020).
Contributions. In this work, we present SparseFed,a new optimization algorithm for federated learningthat can train high-quality models under these constraints while greatly mitigating model poisoning attacks. We describe SparseFed in detail in Section 2,
but the main idea is intuitive: at each round, participating devices compute an update on their local
data and clip the update. The server computes theaggregate gradient, and only updates the topk highest
magnitude elements. Because attackers will necessarily be moving in distinct directions from the majority
of benign devices, the coordinates the attackers need
to update in order to poison the model usually will
not be updated. Our protocol is a defense at training
time, and is complementary to the line of work that
proposes test-time modifications for robustness such assmoothing (Xie et al., 2021; Weber et al., 2021). Prior
defenses at training time use Byzantine-robust learningalgorithms that bound the single iteration deviation
between poisoned and clean models (Mhamdi et al.,2018; Blanchard et al., 2017a). However, the iterative
nature of learning ensures that small deviations at thestart of training compound exponentially.
We propose a framework for analyzing the robustnessof defenses under the certified radius metric from priorwork (Xie et al., 2021). The certified radius is an upperbound on the distance that a poisoned model can drift
from a benign model, and limits the impact that an
attacker can have on the model. Under our framework,
SparseFed minimizes the certified radius by sparsifying
the aggregate model updates.
We validate the effectiveness of our method empiricallyon four benchmark computer vision datasets and one
natural language processing dataset, training models
with between 6 and 40 million parameters on noni.i.d. datasets that range between 50,000 and 800,000
examples. We evaluate SparseFed against four attacks
from prior work (Bhagoji et al., 2019; Bagdasaryan
et al., 2020; Fang et al., 2020; Sun et al., 2019) and two
new attacks we introduce, in the cross-silo and crossdevice settings. As we show in Table 2, SparseFed does
not degrade test accuracy by more than 1%, mitigates
attack accuracy, e.g. by over 97% on the FEMNIST
dataset, and significantly outperforms prior work. The
code to implement our defense is open-source.

2

SPARSEFEDIn this section we introduce a framework for analyzing
the robustness of machine learning protocols against
poisoning attacks. We use this framework to motivate
SparseFed, that uses gradient sparsification to mitigate attackers, and provide a theoretical analysis of its
robustness, convergence and efficiency. The key tool
we use is the certified radius, that is the upper boundon the distance between poisoned and benign models.
2.1

Certified radius as a framework forrobustness

Notation: Let Z be the data domain and Dt be data
sampled (not necessarily i.i.d.) from Z at iterationt. Let Θ be the class of models in d dimensions, andL : Θ × Z ∗ → R be a loss function. A protocol f =(G, A, λ) consists of a gradient oracle G(θ, D, t) → Rd
that takes a model, a dataset and a round index andoutputs the update vector ut . f also includes an update
algorithm A : ut ∈ Rd → Rd , e.g. momentum. λ(t) ∈R is a learning rate scheduler, possibly static,
Pt andΛ(t) the cumulative learning rate Λ(t) = i=1 λ(t).
The update rule of the protocol is then defined asθt+1 = θt − λ(t)A(ut ).
Definition 1 (Poisoning Attack). For a protocol f =(G, A, λ) we define the set of poisoned protocols F (ρ)
to be all protocols f ∗ = (G ∗ , A, λ) that are exactly
the same as f except that the gradient oracle G ∗ isa ρ-corrupted version of G. That is, for any round t
and any model θt and any dataset D we have we haveG ∗ (θt , D) = G(θt , D) +  for some  with ||||1 ≤ ρ.

Remark 1. Under our attack model, the attacker cancontribute to the update with a vector  of `2 mass at
most ρ. This model generalizes existing defenses, e.g.
`2 clipping and Byzantine resilient aggregation rules(El Mhamdi et al., 2018).
Definition 2 (Certified Radius). Let f be a protocol
and f ∗ ∈ F (ρ) be the a poisoned version of the same
protocol. Let θT , θT∗ be the benign and poisoned final
outputs of the above protocols. We call R a certified
radius for f if ∀f ∗ ∈ F (ρ); R(ρ) ≥ |θT − θT∗ |1 .
Robustness Against Poisoning The certified radius
has been established as a metric of the strength ofdefenses (Xie et al., 2021). Prior work has analyzed thecertified radius in two ways. The first is minimizing thedivergence between the benign and poisoned protocols
in a single iteration, as in (Blanchard et al., 2017a;
El Mhamdi et al., 2018; Blanchard et al., 2017b; Xieet al., 2021). As per (Xie et al., 2021), we know thata small certified radius improves robustness becausemodels that are very close to each other are likely to
predict the same label for the same datapoint. However,these papers assume i.i.d. data (El Mhamdi et al.,Panda, Mahloujifar, Bhagoji, Chakraborty, Mittal

2018; Blanchard et al., 2017b,a) and do not consider
the propagation error : that small changes in early
iterations can quickly compound and create a large
divergence in the model. Therefore, defenses that aim
to minimize the divergence in a single iteration via
outlier detection or any other strategy cannot provide
guarantees in the cross-device setting. The second
is combinatorial bounds via ensembling (Jia et al.,2020; Cao et al., 2021). Combinatorial bounds do
not compute the certified radius, and instead directly
bound the change in the label probabilities. However,combinatorial bounds do not scale to the cross-device
setting. For instance, the guaranteesof (Cao et al.,2021) only hold so long as nk < 2 n−mwhere n is theknumber of devices, m is the number of compromised
devices, and k is the size of the ensemble (equation 4in (Cao et al., 2021)) which is generally 1% of n. For
n & 104 (the cross-device setting), this means that (Caoet al., 2021) and other ensembling strategies cannot
provide any guarantees when m > 0.5% of n.
In this section we introduce a framework for analyzing
the certified radius of poisoning attacks in the crossdevice setting.
Analyzing Propagation Error We conduct T
rounds of the protocol f : at round i ∈ [T ] we receive an update, and use the output of the update
algorithm A(ut ) to compute the new model θt+1 . At
each iteration, the upper bound ρ on  gives the additive
error introduced by poisoning. Because the protocol
is adaptive, small additive errors introduced at early
iterations can build upon each other and create large
divergence. We refer to this as the propagation error.
To analyze the propagation error we use the protocol
Lipschitzness, defined in Definition 3.
Definition 3 (Coordinate Lipschitz). A protocolf (G, A, λ) is c-coordinatewise Lipschitz if for any roundt ∈ [T ], models θt , θt∗ ∈ M, and a dataset D we havethat the outputs of the gradient oracle on any coordinate
cannot drift too much farther apart. Specifically, for
any coordinate index i ∈ [d]G(θt∗ , D)[i] − G(θt , D)[i] ≤ c · |θt∗ − θt |1 .
Example 1 (Training a single layer neural networkwith SGD). In this example, we compute the coordinatewise Lipschitz constant of the SGD protocol for asingle layer neural network defined as σ(θx), where σis the softmax function and θ ∈ Rd are the network
parameters. For cross-entropy loss-based training using
dataset D, we show that the constant c = 14 . Formally,
sup |g(D, θ1 )[i] − g(D, θ2 )[i]|1 ≤D,θ1 ,θ21|θ1 − θ2 |1 ∀i ∈ [d]4∂L
where g(D, θ)[i] = ∂θ
. We provide the full computationiin Appendix A.3.1.

Analyzing the Certified Radius In Theorem 1, we
account for the propagation error and obtain a certified radius for general protocols. We provide a procedure for computing the certified radius exactly inAppendix A.3.2. Unlike prior work, we do not makeany assumptions on the distribution of data across devices (El Mhamdi et al., 2018), the number of iterations
where the attacker is present (Xie et al., 2021), thenumber of devices (Cao et al., 2021), or the numberof poisoned points (Jia et al., 2020). We can accountfor these factors by adjusting the relevant quantities.
Although the computed certified radius from Theorem
1 may not be tight, we expect protocols that improvethe bound to benefit from improvements in their robustness. In the next section, we show one way to
improve this bound with sparsification by decreasing
the propagation error.
Theorem 1. Let f be a c-coordinatewise-Lipschitz protocol on a dataset D. Then R(ρ) = Λ(T )(1 + dc)Λ(T ) ρis a certified radius for f .
2.2

Security analysis of SparseFed

In this section we use our certified radius framework tomotivate SparseFed, that uses gradient sparsificationand norm clipping to mitigate attackers, and provide atheoretical analysis of its robustness.
The building blocks of robustness The two components of the certified radius are the additive error andthe propagation error. The additive error represents
the attacker’s power in terms of an upper bound ρ on
the noise vector . We can enforce this with device
level `2 gradient norm clipping, that is a standard technique employed by prior work (Sun et al., 2019; Wanget al., 2020a). If p% of devices are compromised andthe parameter of `2 clipping is L then ρ = pL. The
propagation error represents the protocol’s inherent
robustness in terms of the Lipschitz constant c · d.
Update sparsification techniques reduce the number of
non-zero entries in the aggregated stochastic gradient
before it is applied to the global model. Global topk
sparsification (Stich et al., 2018) is one such methodthat updates only the k coordinates with the largest
magnitude, where kk|d, and converges at the same rate
as SGD (Karimireddy et al., 2019). To the best of ourknowledge, we are the first to propose the use of global
update sparsification as a building block for robust
federated learning.
We propose SparseFed, presented in full in Algorithm
1, by combining sparsification and norm clipping. At
each round of federated learning, each device downloads
the current global model and computes an update on
their local dataset. This update is clipped according
to a specified `2 norm. This controls ρ and allows us

SparseFed: Mitigating Model Poisoning Attacks in Federated Learning with Sparsification

Algorithm 1 SparseFed
Input: number of coordinates to update each round k,learning rate λ, number of timesteps T , local batch sizeb, number of devices selected per round n, norm clipping
parameter L, local epochs τ , local learning rate γ, devicendatasets Dj=1
, momentum ρ
Initialize model θ0 using the same random seed on thedevices and aggregator
Initialize memory vector Wt = 0 , momentum vector
Rt = 0for t = 1, 2, · · · T do
Randomly select n devices d1 , . . . dnloop {In parallel on devices {di }ni=1 }Download new model weights θt = θ
for m ∈ τ doP
Compute gradient gti = 1b lj=1 ∇θ L(θt , Dj )Accumulate gradient θt = θt − γ(t, m)gti
end forCompute update uit = θt − θClip update uit = uit · min(1, |uLi | )t 2
end loopPiAggregate gradients ut = n1 n
i=1 utt
t−1
tMomentum: R = ρR+uError feedback: Wt = ut + Wt
Extract topk : ∆t = topk (Wt )Error accumulation: Wt+1 = Wt − ∆tMomentum factor masking: Rt+1 = Rt − ∆tUpdate θt+1 = θt − λ(t)∆t
end for T
Output: θt t=1

from devices and only updates the topk coordinatesof the aggregated update. We show that the use of topk
update sparsification improves the certified radius.
2.3

Efficiency and Convergence Analysis ofSparseFed

Convergence Analysis: We show that SparseFed
converges as well as SGD in the base setting (e.g.
when no attackers are present). We make standard
assumptions on the smoothness of the loss function
and bounded gradient which are only necessary for ourconvergence analysis (Rothchild et al., 2020; Karimireddy et al., 2019; Xie et al., 2021).
Assumption 1 (Smoothness). L is `-smooth if ∀x, y ∈2
Rd |L(x) − (L(y) + h∇L(x), x − yi)| ≤ 2` kx − yk2

Assumption 2 (Moment Bound). For any x, our2oracle returns g s.t. E[g] = ∇θ(x) and E kgk2 ≤ σ 2

Theorem 3 (Asymptotic Convergence of SparseFed).
√−1
For a protocol f, λ(t) = t + 1 , τ = 1, A = topk , Lsatisfying Assumption 1, G satisfying Assumption 2,
we get the convergence rate of
min E[k∇L(θt )k] ≤t∈T4(θ0 − θ∗ ) + `σ 2
4`2 σ 2 (1 − δ)√
+ 2
δ (T + 1)
2 T +1

Therefore, f converges asymptotically at the SGD rate.
to control the additive error. The server aggregates
all updates with a simple average. The aggregated
update is added to an error feedback vector. The server
extracts the topk magnitude coordinates from the error
feedback vector, and zeroes out these coordinates fromthe error feedback vector. The topk coordinates areused to update the global model. Because we updatek << d coordinates, we reduce the propagation error.
We first define a notion of sparsity for a protocol anduse it to prove our main theorem. In Appendix A.1.1
we discuss why SparseFed satisifies this notion.
Definition 4 ((k, γ)-sparsity). A federated learning
protocol d = (λ, G, A) is (k, γ)-sparse on a dataset D
if for all ut = G(θt−1 , D) generated during the processof training on D A(ut ) only has k non-zero elements
and we have|A(ut ) − ut |1 ≤ γ.
Theorem 2. Let f be a c-coordinatewise-Lipschitzand (k, γ)-sparse protocol on a dataset D. Let w =min(d, 2k) then R(ρ) = Λ(T )(1 + wc)Λ(T ) (ρ + 2γ) is acertified radius for f .
In Theorem 2 we improve the base term in propagationderror term by a factor of 2k, that can be multiple ordersof magnitude.
In summary, SparseFed aggregates clipped updates

Communication efficiency of SparseFed: In practical deployments of federated learning systems, communication efficiency must be prioritized. The topk
sparsification used in SparseFed requires communicating the full gradient at every iteration and therefore isnot communication efficient. FetchSGD is a communication efficient approximation of topk sparsification using
the Count Sketch data structure (Rothchild et al., 2020).
Because FetchSGD provably approximates the heavy
hitter recovery properties of topk (Rothchild et al.,2020), it inherits these robustness guarantees. In Appendix B.9, we compare implementations of SparseFed
using both topk and FetchSGD and find that when using the latter, we are able to prove robustness andcommunication efficiency.

3

EVALUATION

We empirically demonstrate the effectiveness of ourSparseFed defense against strong attackers in a varietyof realistic experimental settings. To this end, we set
up the first environment to simulate model poisoning
attacks on the cross-device setting of federated learningwith tens of thousands of devices, aiming to emulatea real-world deployment as closely as possible. In
contrast, prior work has mostly evaluated attacks in the
cross-silo setting with 10s to 100s of devices (Bhagoji
et al., 2019; Bagdasaryan et al., 2020; Wang et al.,Panda, Mahloujifar, Bhagoji, Chakraborty, Mittal

2020a; Fang et al., 2020). We evaluate SparseFed inboth the cross-silo and cross-device settings against
a breadth of attacks and find that we significantly
outperform prior defenses.
3.1

Experimental setup

All methods are implemented in PyTorch (Paszke et al.,2019). We conduct experiments on computer vision(CIFAR10, CIFAR100, FashionMNIST, FEMNIST),and natural language processing (Reddit) datasets.
Federated Extended MNIST (FEMNIST) dataset (Caldas et al., 2018) is a dataset constructed specificallyas a benchmark for federated learning. Our goal is
to train a model in a true federated fashion, i.e. we
can only view each datapoint once. We use a 40Mparameter ResNet101 for this task. FEMNIST has 63
classes and a natural non-i.i.d. partitioning with anaverage of 226.83 datapoints for each of 3550 users, fora total of 805,263 datapoints. Our goal is to simulate
the cross-device setting as closely as possible, so we
aim to have & 50 devices participating in each round,with each device participating exactly once (Kairouz
et al., 2019), without exceeding a batch size of ≈ 600.
We split each user evenly into 9 − 10 devices, yielding
35, 000 simulated devices and 35 devices participatingin each iteration. Each device has a non-i.i.d. datasetthat includes data from multiple classes.
We also conduct experiments on Fashion MNIST(FMNIST) (Xiao et al., 2017), CIFAR10/CIFAR100(Krizhevsky et al., 2009), that are benchmark tasks
for computer vision. We provide the experimental parameters in Table 1 for the cross-silo and cross-device
settings, for the number of devices d, number of devices participating at each iteration w, percentage ofattackers p, and the auxiliary set size s: the number of datapoints we are attempting to modify model
behavior on for the targeted model poisoning attack.
A key design choice is how to distribute the training
data among simulated devices. In the cross-silo setting,
we simply distribute data i.i.d. across devices. In the
cross-device setting, we follow previous work (Rothchild
et al., 2020) and artificially create non-i.i.d. datasets bygiving each device images from only a single class. At
each round of federated learning, a subset of devices are
randomly selected to participate. Our 7M-parameter
ResNet9 model architecture, data preprocessing, andmost hyperparameters follow (Page, 2019).
3.2

Attack details:

We experiment with a number of attacks: targeted
model poisoning, untargeted model poisoning, semantic backdoor, model replacement, colluding attack, andadaptive attack. In all attacks, the attacker controls anumber of devices and realizes the attack by upload-

Parameter

Cross-silo

Cross-device

i.i.d.
d (# devices)
w (# participating)p (% compromised)a (E[#] attackers per iter)s (auxiliary set)b (local batch size)

TRUE
1000
10
1
0.1
50
50

FALSE
100000
100
2
2
500
5

Table 1: Parameters for CIFAR10, CIFAR100, MNIST,
FashionMNIST in cross-silo and cross-device settings

ing poisoning gradients to the server. p% of the dsimulated devices are attackers. We sample w devices
randomly at every iteration to participate, so we expecta = p · w devices to be compromised at each iteration.
Empirically we find that the attacker does not need to
be present until the last ≈ 20% of training to insert
the attack, in line with prior work Bagdasaryan et al.
(2020).
Targeted model poisoning: We follow the attack
procedure of (Bhagoji et al., 2019). We construct an
auxiliary dataset of size s with the following procedure:First, we sample s points from the test distribution.
We then flip the label to one of the labels that is
not the ground truth. The objective of the attacker
is to maximize the accuracy of the trained model on
the auxiliary dataset (attack accuracy), typically while
ensuring that the model performance on the remaining
data does not degrade significantly. The attacker ispresent throughout the course of training.
Untargeted model poisoning attack: Also known
as a Byzantine attack, the attacker attempts to decrease
the test accuracy of the trained model (Blanchard et al.,2017a; Mhamdi et al., 2018). The attacker is present
throughout the course of training, and succeeds whenthe model parameters diverge and can no longer betrained without resetting to an earlier checkpoint.
Semantic backdoor via model poisoning: We follow the backdoor attack described in (Sun et al., 2019).
We train a model on FEMNIST and simulate 35,000
devices, 1000 of which are attackers. We consider thesemantic backdoor task of misclassifying the digit 7 as
1, creating 3000 backdoors, the number of instancesof the digit 7 in the unperturbed validation set, andinclude results in Table 2. We include experiments thatvary the semantic backdoor task in Appendix B.5.
Model replacement: In Appendix B.5 we evaluate
SparseFed against the model replacement attack of(Bagdasaryan et al., 2020) on the Reddit dataset. The
attacker participates in a single iteration toward theend of training and scales their gradient so that theycan entirely replace the trained global model. In orderSparseFed: Mitigating Model Poisoning Attacks in Federated Learning with Sparsification

to optimize for the `2 norm clipping constraint, theattacker uses Projected Gradient Descent (PGD) withknowledge of the norm clipping parameter.
Colluding attack: In Alg. 2 we propose the colluding attack for the cross-device setting, where multiple
attackers can be present in a single iteration. The attackers collude by each sending the same update. In the
cross-device setting, we combine the colluding attack
with the targeted model poisoning attack, untargeted
model poisoning attack, or semantic backdoor attack.
Algorithm 2 Attack
Input: learning rate η, local batch size `, norm clipping
parameter L, number of local epochs e
1: This procedure is used by all attackers in a round toensure that they upload the same update
2: for number of PGD epochs ei ∈ e do
3:Compute P
stochastic gradient git on batch Bi of sizet
1`: gi = ` lj=1 ∇M L(Mtei , Dj )cet
4:Update local model M= Mtei − ηgit
i+1
Project accumulated update onto the perimeter of5:cetthe `2 constraint Mtei+1 = M0t − CLIP (M− M0t )
i+1
6: end for
Output: Mte

3.3

SparseFed is an effective defense in the
cross-silo setting

We first evaluate SparseFed in the cross-silo setting
common to prior work to show the improvement ofSparseFed over the baseline `2 clipping defense. In
Figures 2a and 2b we see that appropriately choosing
k allows us to mitigate the attack without harming
convergence. As we explain in Section 2, `2 norm
clipping is insufficient to mitigate the attack because
minor perturbations at early iterations can propagate
over the course of training. This intuition validated byour results, that show that the use of norm clipping is
not sufficient to deter the attacker. From this, we cansee the importance of coupling both norm clipping andupdate sparsification in SparseFed. The tradeoff thatSparseFed introduces for the attacker is forcing themto have large magnitude elements in order to have theircomponent of the update appear in the topk , howeverthese are clipped due to the use of `2 norm clipping,leading to ineffective attacks.
Impact of sparsification parameter k: SparseFed
requires the sparsification parameter k. We provide
an algorithm for selecting k in Alg. 3. When using
ResNet9, we obtain a value of k = 1e3 that does not significantly compromise convergence and use this acrossall datasets that use ResNet9 (FMNIST, CIFAR10,
CIFAR100). When using ResNet101, we obtain a valueof k = 4e4 and use this for all FEMNIST experiments.
Fig. 2 shows the sparsification-utility-robustness tradeoff for the cross-silo and cross-device settings. For smallk and large k neither the attack nor the model converge.
When k is too small, SparseFed approaches a no-op
as k → 0. When k is too large, the use of momentum
factor masking (Stich, 2019; Lin et al., 2017) prevents
convergence to a benign optimum, which in turn makes
it difficult for the attacker to perform model replacement (Bagdasaryan et al., 2020). Most choices of k
mitigate the attack, and the best choice of k does not
significantly degrade test accuracy. We expect thatpractitioners will be able to easily tune the correct
value of k for their purpose, because the parameter canbe tuned on a single device and does not need to be
finetuned across datasets for the same architecture.
Algorithm 3 Selecting k
Input: model θ, maximum information loss ω, number ofmodel parameters d, number of iterations in an epochr, number of gradients to sample n (more samples gives
a better estimate of ω)
1: set initial k k = dr
2: set initial realized information loss δ = ∞3: while δ > ω do
4:compute n sample minibatch gradients {g}nj=1 |gj =∇θ L(θ, zj )5:
extract top-k {u}nj=0 |uj = topk (gj ) P
6:calculate average l1 mass lost δ ∗ = n1 n
j=1 |gj − uj |1
7:
update δ = min(δ, δ ∗ )8:
if δ > ω then9:k = k + dr
10:
end if
11: end while
Output: k

3.4

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

We next evaluate SparseFed in the cross-device setting,which includes many more devices and the challenge of
optimizing over small, non-i.i.d. datasets. In Figures
2c and 2d we see that appropriately choosing k allows
us to mitigate the attack without harming convergence.
This is the setting that SparseFed is designed for, andwe evaluate it against prior work.
Existing defenses cannot handle collusion Prior
empirical defenses are designed under the assumptionthat data is distributed i.i.d. across devices and attackers do not collude amongst each other. We carry out attacks in the cross-device setting, where data is non-i.i.d.
and attackers have no restriction on their ability to collude, and conclude that SparseFed is the only defensethat maintains empirical robustness in this setting. In
Table 2 we evaluate all defenses against a population ofcolluding attackers across all four datasets. We report
the attack accuracy; when a defense fails to converge,
we mark it with DNC (this is discussed further below). Bulyan and other Byzantine-resilient aggregation
rules rely on eliminating outliers (Mhamdi et al., 2018).
Specifically, Bulyan determines outliers by measuringPanda, Mahloujifar, Bhagoji, Chakraborty, Mittal(a) Impact of k on conver- (b) Impact of k on robustness, (c) Impact of k on conver- (d) Impact of k on robustness,cross-silo setting
cross-device setting
gence, cross-silo setting
gence, cross-device setting

Figure 2: Tradeoffs between sparsification, convergence and robustness for the targeted model poisoning attack
on CIFAR10 in the cross-silo and cross-device settings.
their distance from other updates in the population.
Because the attackers are colluding, their updates havea distance of 0 from each other, and as a result Bulyan
does not eliminate them. Trimmed mean fails evenagainst a single attacker, because trimmed mean relies on the assumption that a Byzantine attacker will
either be the minimum or maximum value. However,this assumption does not hold for a model poisoning
attacker. These conclusions are in line with conclusions from prior work (Bhagoji et al., 2019; Fang et al.,2020; Baruch et al., 2019a). Our experimental results
demonstrate that even when attackers collude, they
are unable to overcome the trade-off that is enforcedby SparseFed.
Byzantine attacks: In Table 3a we validate the effectiveness of SparseFed against untargeted model poisoning attacks, or Byzantine attacks. Byzantine attacks
succeed more easily in the cross-device setting against
prior defenses for the reasons mentioned above, but
SparseFed is still able to mitigate these.
Impact of defenses on test accuracy: In Table 3b
we evaluate the impact of each defense on convergencein the absence of attacks. Krum and coordinate median
do not converge in the cross-device setting. When
Krum chooses a single model, it is overfitting the global
model to the small local dataset of a single device.
Coordinate median does not converge because of thegap between median and mean. Trimmed mean and
Bulyan have a minor impact on test accuracy when therobustness parameter f is small. When 2 out of 100
devices are compromised, Bulyan will discard 4f + 2 =10 gradients in order to maintain robustness. For thechallenging FEMNIST task, this information loss is
too much and these methods do not converge. Theseobservations are in line with conclusions from prior
work, that make the case for more complex algorithms(Chen et al., 2020; Muñoz-González et al., 2019; Yinet al., 2019) that are out of the scope of this paper’s
evaluation. Norm clipping acts as regularization and

Figure 3: SparseFed converges at the same rate as
the baseline (FedAvg) on CIFAR10 in the cross-device
setting

does not have much impact on the test accuracy. As
we show in Fig. 2c, SparseFed does not impact test
accuracy significantly. In Fig 3 we empirically validate
the speed of convergence of SparseFed and find thatit converges at the same rate as FedAvg, even in thepresence of attackers.
Verification of theory: In Section 2 we analyze thecertified radius of SparseFed. In Table 2 we provide
observed distances between poisoned and benign models when using various defenses, and conclude thatSparseFed has both the lowest distance and lowest attack accuracy. This verifies our theoretical guarantees.
`2 Norm clipping: In Table 4 we improve the
Byzantine-resilient defenses by combining them with
`2 norm clipping. All results for all defenses include
norm clipping. In Appendix B.2 we further show that
norm clipping is necessary in SparseFed.
Hyperparameter tuning (Appendix B.3): We
tune standard hyperparameters on the FedAvg baseline, and use these hyperparameters for all experiments.
Krum, Bulyan and trimmed mean require the parameter f , the number of attackers present in the system.
FedAvg requires the number of local epochs, a batch
size for each epoch, and learning rate decay. In Table
5 we vary the number of local epochs and use a single
local epoch as the optimal value for the cross-device

SparseFed: Mitigating Model Poisoning Attacks in Federated Learning with Sparsification

Table 2: Krum, Bulyan, trimmed mean, coordinate median, norm clipping (clipping, `2 = 5), and SparseFed
on FMNIST, CIFAR10, CIFAR100, and FEMNIST in the cross-device setting. SparseFed reduces the attack
accuracy significantly more than other defenses. If a defense cannot converge we denote it with DNC. We report`1 distances between poisoned and unattacked models at the end of training. SparseFed has less than half the
distance of the next best defense.
DefenseAttack Accuracy (%) (Dataset)
CIFAR10 CIFAR100 FMNIST FEMNISTDistance (thousands)
CIFAR10 FMNIST

Trimmed Mean
BulyanClipping
SparseFed (Ours)

44.6
36.2
100
4.6

64
68
73
31

81.4
81.8
100
23

100
100
100
2.2

DNC
DNC
100
2.86

41
39
40
16

(b) Comparing the impact on test accuracy of the defenses.
(a) Comparison of Byzantine failure success rates on Fash- Cross-device setting, no attackers (averaged over 3 runs).
ionMNIST. Ours: Cross-device setting. (Fang et al., 2020):
Numbers from their paper with 100 devices, 20 attackers (20% compromised)

DefenseKrum
MedianTrimmed mean
BulyanSparseFed

Ours

Test error(Fang et al., 2020)

DNC
DNC
90
90
20

87
29
52
38
N/A

Table 4: Implementing norm clipping greatly mitigates the effectiveness of the attack against Bulyan andtrimmed mean when no colluding attackers are present.
CIFAR10, 1e4 devices, 100 attackers.
DefenseTest acc

Attack acc

Bulyan (`2 )BulyanTrimmed Mean (`2 )Trimmed

83.64
84.94
77.42
81.99

10.0
38.6
71.6
100.0

setting, in line with prior work Rothchild et al. (2020)`2 clipping requires the clip parameter.
Stealth of attack (Appendix B.5): We validatethat the attack is stealthy when it succeeds, insofar as
it does not compromise normal model operation significantly. For the targeted model poisoning attack, theauxiliary dataset is divided equally across all classes.
Thus, the performance of any one class does not degrade significantly. In the semantic backdoor attack,by definition the model fails on the class that is flippedby the semantic backdoor.
Strength of attack: In Table 6 we increase the frac-

DefenseDecrease

Test Acc

No defense`2
DP (σ = 0.025)
Krum
MedianTrimmed mean (f = 2)
Bulyan (f = 2)
Bulyan (f = 10)
SparseFed (k = 1e3)
SparseFed (k = 5e4)0 ±0
2.0 ±0.1
20.0 ±0.2
80.0 ±080.0 ±09.23 ±0.89.56 ±0.79
66.48
10.21 ±0.7
3.0 ±0.01

90.0 ±0.1
88.0 ±0.170.50 ±0.2
10.0 ±0
10.0 ±080.77 ±0.880.44 ±0.79
23.52
79.79 ±0.7
87.0 ±0.01

Table 5: FedAvg convergence does not benefit fromdoing multiple local epochs. We use local learning
rate=0.9, but even for a small number of local epochs
convergence does not benefit, and at these small numberof local epochs a smaller local learning rate would nothave much impact because the exponential decay factor
is not large. CIFAR10, 10000 devices, no attackers.
Num. epochs

Test acc decrease

Test acc

1
2
5

0
0.41
80

90
89.59
10

tion of compromised agents until SparseFed is nolonger robust. Unsurprisingly, the power of collusion
enables attackers to quickly overtake even SparseFed,
the strongest defense we evaluate, when the fractionof compromised agents increases past 5 %. Prior work
Shejwalkar et al. (2021) argues that a realistic value forthe fraction of compromised agents should not exceed
0.1%. Therefore, only in an unrealistic regime does ourdefense fail.
In Appendix B.6: In order to validate our defense,
we ensure that we test against the strongest available

Panda, Mahloujifar, Bhagoji, Chakraborty, Mittal

Table 6: Varying the fraction of compromised devices
for SparseFed on the CIFAR100 cross-device setting.
Fraction compromised (%)

Attack Accuracy (%)

2
4
6

4.4
41.20
100

attacks. We show that our proposed attack is stronger
than previous attacks against both norm-based defenses
as well as Byzantine defenses that do not rely on normclipping (Bulyan, Trimmed Mean etc.) We compare theattack accuracy of the colluding attack used in this work
against prior attacks on Byzantine-resilient aggregation
rules, and conclude that our attack is significantly more
powerful than prior work considers. The key factor
in the strength of the colluding attack is the ability
for colluding attackers to send identical gradients andtherefore avoid outlier detection by essentially vouchingfor each other. We also include experiments using
an adaptive attack that we design against SparseFed
which has perfect knowledge of the topk coordinates.

4

Related Work

Federated learning: There are two main settings forfederated learning: the cross-device setting and thecross-silo setting (Kairouz et al., 2019). The crossdevice setting features all the complications we introduce earlier, namely hundreds of thousands or millionsof devices with non-iid data distributions participating
sparsely (Kairouz et al., 2019). This is the original setting for federated learning, and it is the setting where
we focus our analysis. Most prior work has operated
on the scale of the cross-silo setting, with experiments
on at most 100 devices (Wang et al., 2020a; Fang et al.,2019; Bhagoji et al., 2019; Bagdasaryan et al., 2020).
Targeted model poisoning attacks: The goal of
the attacker in a targeted model poisoning attack is
to modify the model such that particular inputs induce misclassification (Chen et al., 2017; Biggio et al.,2012; Bhagoji et al., 2019; Bagdasaryan et al., 2020;
Wang et al., 2020a). This can be a random set of data
drawn from the validation distribution, with the labels
randomly flipped to another class (Bagdasaryan et al.,2020; Bhagoji et al., 2019). This can also be a semantic
backdoor, wherein the attacker tries to flip the labelof all data from a target class to another specific class,e.g. classifying all 1s as 7s in the MNIST dataset (Sunet al., 2019). (Wang et al., 2020a) shows that backdoors
sampled from the low-probability portion of the distribution can break existing defenses and are a byproductof the existence of adversarial examples.
Prior defenses: The two main bodies of work on defenses against poisoning attacks are certified robustness

and empirical robustness.
Ensemble methods have been proposed to certify robustness against poisoning attacks (e.g. (Jia et al.,2020; Cao et al., 2021)). As we show in Section 2, ensemble methods do not scale to the cross-device setting
because they rely on most subsamples not containing
attackers. This assumption breaks down for n & 104 ,where it is very unlikely to randomly sample enoughclients to train a good model without sampling an attacker. Data poisoning defenses are insufficient against
malicious clients that can manipulate model updates.
Provably secure defenses against data poisoning certify robustness in terms of the number of poisoned
examples, but a single compromised device can poison
an arbitrary number of their training datapoints, thatbreaks the core assumption of secure defenses for datapoisoning. (Levine and Feizi, 2021) partition the training dataset with a hash function for certified robustness,but their defense is only applicable to deterministic
training algorithms for data poisoning. Works thatuse randomized smoothing at testing time (Rosenfeld
et al., 2020; Wang et al., 2020b) are complementary to
our work, that is a procedure solely for training. (Xieet al., 2021) use noise during training and provide aninference-time smoothing procedure to certify robustness in federated learning. However, their goal is tofinetune an already poisoned model to erase backdoors.
There are a number of defenses that provide empiricalrobustness against poisoning attacks. In our evaluation at scale we also compare to five of these empiricaldefenses, each of which we adapt and improve for thefederated setting: trimmed mean (Yin et al., 2019), median (Yin et al., 2019), Krum (Blanchard et al., 2017a),
Bulyan(Mhamdi et al., 2018), and norm clipping (Sunet al., 2019). We provide exact algorithms for these
defenses in Appendix B.1. These defenses only achieve
provable guarantees with an i.i.d. assumption on thedevice data distributions (Mhamdi et al., 2018), thatis not valid in the cross-device setting. Further, they
have been shown to be ineffective against model poisoning attacks (Baruch et al., 2019b; Bhagoji et al.,2019; Xie et al., 2020; Fang et al., 2020) in practice,e.g. by crafting updates that do not significantly differ
from benign updates (Bhagoji et al., 2019).

5

Discussion

Prior work in poisoning attacks on federated learning
has demonstrated that existing defenses are vulnerable to attacks. We complement this body of work byintroducing SparseFed, an optimization algorithm forfederated learning which combines update sparsification and norm clipping. We prove a certified radius
for SparseFed that improves over baseline federated
learning. SparseFed does not significantly decreaseSparseFed: Mitigating Model Poisoning Attacks in Federated Learning with Sparsification

test accuracy, and mitigates attacks in both the crosssilo and cross-device settings. We evaluate SparseFed
empirically against existing defenses, and confirm that
it outperforms these against multiple strong attacks.
Acknowledgements: This work was supported inpart by the National Science Foundation under grant
CNS-1553437, Department of Energy’s EUREICA
grant DE-OE0000920, the ARL’s Army Artificial Intelligence Innovation Institute (A2I2), Schmidt DataX
award, and Princeton E-ffiliates Award. The work
done at IBM research was sponsored by the Combat
Capabilities Development Command Army ResearchLaboratory and was accomplished under Cooperative
Agreement Number W911NF-13-2-0045 (ARL Cyber
Security CRA). The views and conclusions contained inthis document are those of the authors and should not
be interpreted as representing the official policies, either
expressed or implied, of the Combat Capabilities Development Command Army Research Laboratory or the
U.S. Government. The U.S. Government is authorized
to reproduce and distribute reprints for Government
purposes notwithstanding any copyright notation hereon.

References
Hongyi Wang, Kartik Sreenivasan, Shashank Rajput, Harit
Vishwakarma, Saurabh Agarwal, Jy-yong Sohn, Kangwook Lee, and Dimitris Papailiopoulos. Attack of thetails: Yes, you really can backdoor federated learning. In
Neural Information Processing Systems, 2020a.
Arjun Nitin Bhagoji, Supriyo Chakraborty, Prateek Mittal,
and Seraphin Calo. Analyzing federated learning throughan adversarial lens. In Proceedings of the 36th International Conference on Machine Learning, pages 634–643,
2019.
Eugene Bagdasaryan, Andreas Veit, Yiqing Hua, Deborah Estrin, and Vitaly Shmatikov. How to backdoor
federated learning. In Silvia Chiappa and Roberto Calandra, editors, Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning
Research, pages 2938–2948, Online, 26–28 Aug 2020.
PMLR. URL http://proceedings.mlr.press/v108/
bagdasaryan20a.html.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurelien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Keith
Bonawitz, Zachary Charles, Graham Cormode, Rachel
Cummings, et al. Advances and open problems in federated learning. arXiv preprint arXiv:1912.04977, 2019.
Keith Bonawitz, Hubert Eichner, Wolfgang Grieskamp,
Dzmitry Huba, Alex Ingerman, Vladimir Ivanov,
Chloe M Kiddon, Jakub Konecny, Stefano Mazzocchi,
Brendan McMahan, Timon Van Overveldt, David Petrou,
Daniel Ramage, and Jason Roselander. Towards federated learning at scale: System design. In SysML 2019,2019. URL https://arxiv.org/abs/1902.01046.
Andrew Hard, Kanishka Rao, Rajiv Mathews, FrancoiseBeaufays, Sean Augenstein, Hubert Eichner, Chloe Kiddon, and Daniel Ramage. Federated learning for mobile
keyboard prediction. arXiv preprint 1811.03604, 2018.
Yue Zhao, Meng Li, Liangzhen Lai, Naveen Suda, Damon

Civin, and Vikas Chandra. Federated learning with noniid data. arXiv preprint arXiv:1806.00582, 2018.
Peter Rousseeuw. Multivariate estimation with highbreakdown point. Mathematical Statistics and Applications Vol. B, pages 283–297, 01 1985. doi: 10.1007/
978-94-009-5438-0_20.
Xiaoyu Cao, Minghong Fang, Jia Liu, and Neil Zhenqiang
Gong. Fltrust: Byzantine-robust federated learning via
trust bootstrapping, 2020.
Chulin Xie, Minghao Chen, Pin-Yu Chen, and Bo Li. Crfl:
Certifiably robust federated learning against backdoor
attacks, 2021.
Maurice Weber, Xiaojun Xu, Bojan Karlas, Ce Zhang,and Bo Li. Rab: Provable robustness against backdoor
attacks, 2021.
El Mahdi El Mhamdi, Rachid Guerraoui, and Sébastien
Rouault. The hidden vulnerability of distributed learning
in byzantium. In ICML, 2018.
Peva Blanchard, Rachid Guerraoui, Julien Stainer, et al.
Machine Learning with Adversaries: Byzantine Tolerant
Gradient Descent. In Advances in Neural Information
Processing Systems, pages 118–128, 2017a.
Minghong Fang, Xiaoyu Cao, Jinyuan Jia, and N. Gong.
Local model poisoning attacks to byzantine-robust federated learning. In USENIX Security Symposium, 2020.
Ziteng Sun, Peter Kairouz, Ananda Theertha Suresh, andH Brendan McMahan. Can you really backdoor federated
learning? arXiv preprint arXiv:1911.07963, 2019.
El Mahdi El Mhamdi, Rachid Guerraoui, and Sébastien
Rouault. The hidden vulnerability of distributed learning
in Byzantium. In Proceedings of the 35th International
Conference on Machine Learning, pages 3521–3530, 2018.
Peva Blanchard, El Mahdi El Mhamdi, Rachid Guerraoui,
and Julien Stainer. Machine learning with adversaries:
Byzantine tolerant gradient descent. In I. Guyon,
U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus,
S. Vishwanathan, and R. Garnett, editors, Advancesin Neural Information Processing Systems, volume 30,
pages 119–129. Curran Associates, Inc., 2017b. URL
https://proceedings.neurips.cc/paper/2017/file/
f4b9ec30ad9f68f89b29639786cb62ef-Paper.pdf.
Jinyuan Jia, Xiaoyu Cao, and Neil Zhenqiang Gong. Intrinsic certified robustness of bagging against data poisoning
attacks, 2020.
Xiaoyu Cao, Jinyuan Jia, and Neil Zhenqiang Gong. Provably secure federated learning against malicious clients,
2021.
S. Stich, Jean-Baptiste Cordonnier, and M. Jaggi. Sparsified
sgd with memory. In NeurIPS, 2018.
Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian
Stich, and Martin Jaggi. Error feedback fixes SignSGD
and other gradient compression schemes. In ICML, 2019.
Daniel Rothchild, Ashwinee Panda, Enayat Ullah, Nikita
Ivkin, Ion Stoica, Vladimir Braverman, Joseph Gonzalez,
and Raman Arora. Fetchsgd: Communication-efficient
federated learning with sketching, 2020.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer,
James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito,Panda, Mahloujifar, Bhagoji, Chakraborty, Mittal
Martin Raison, Alykhan Tejani, Sasank Chilamkurthy,
Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance
deep learning library. In Advances in Neural Information Processing Systems 32, pages 8024–8035. Curran
Associates, Inc., 2019.

Elan Rosenfeld, Ezra Winston, Pradeep Ravikumar, andJ. Zico Kolter. Certified robustness to label-flipping
attacks via randomized smoothing, 2020.

Sebastian Caldas, Peter Wu, Tian Li, Jakub Konecný,H Brendan McMahan, Virginia Smith, and Ameet Talwalkar. Leaf: A benchmark for federated settings. arXiv
preprint arXiv:1812.01097, 2018.

Gilad Baruch, Moran Baruch, and Yoav Goldberg. A little isenough: Circumventing defenses for distributed learning.
In H. Wallach, H. Larochelle, A. Beygelzimer, F. d AlchéBuc, E. Fox, and R. Garnett, editors, Advances in
Neural Information Processing Systems, volume 32,
pages 8635–8645. Curran Associates, Inc., 2019b. URL
https://proceedings.neurips.cc/paper/2019/file/ec1c59141046cd1866bbbcdfb6ae31d4-Paper.pdf.

Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashionmnist: a novel image dataset for benchmarking machinelearning algorithms, 2017.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple
layers of features from tiny images. Technical report,
Citeseer, 2009.
David Page. How to train your resnet, Nov 2019. URL
https://myrtle.ai/how-to-train-your-resnet/.
Sebastian U Stich. Local SGD converges fast and communicates little. In International Conference on Learning
Representations (ICLR), 2019.
Yujun Lin, Song Han, Huizi Mao, Yu Wang, and William J
Dally. Deep gradient compression: Reducing the communication bandwidth for distributed training. arXiv
preprint arXiv:1712.01887, 2017.
Moran Baruch, Gilad Baruch, and Yoav Goldberg. A little isenough: Circumventing defenses for distributed learning.
arXiv preprint arXiv:1902.06156, 2019a.
Xiangyi Chen, Tiancong Chen, Haoran Sun, Z. Wu, andMingyi Hong. Distributed training with heterogeneous
data: Bridging median- and mean-based algorithms.
ArXiv, abs/1906.01736, 2020.
Luis Muñoz-González, Kenneth T. Co, and Emil C. Lupu.
Byzantine-robust federated machine learning throughadaptive model averaging. ArXiv, abs/1909.05125, 2019.
Dong Yin, Yudong Chen, Kannan Ramchandran, and Peter
Bartlett. Byzantine-robust distributed learning: Towards
optimal statistical rates. In ICML, 2019.
Virat Shejwalkar, Amir Houmansadr, Peter Kairouz, andDaniel Ramage. Back to the drawing board: A criticalevaluation of poisoning attacks on production federated
learning, 2021.
Minghong Fang, Xiaoyu Cao, Jinyuan Jia, and Neil Zhenqiang Gong.
Local model poisoning attacks to
Byzantine-robust federated learning. arXiv preprint
arXiv:1911.11815, 2019.
Xinyun Chen, Chang Liu, Bo Li, Kimberly Lu, andDawn Song. Targeted backdoor attacks on deep learning systems using data poisoning. arXiv preprint
arXiv:1712.05526, 2017.
Battista Biggio, Blaine Nelson, and Pavel Laskov. Poisoning attacks against support vector machines. In
Proceedings of the 29th International Coference on International Conference on Machine Learning, ICML’12,
pages 1467–1474, USA, 2012. Omnipress. ISBN 978-14503-1285-1. URL http://dl.acm.org/citation.cfm?
id=3042573.3042761.
Alexander Levine and Soheil Feizi. Deep partition aggregation: Provable defense against general poisoning attacks,
2021.

Binghui Wang, Xiaoyu Cao, Jinyuan jia, and Neil Zhenqiang
Gong. On certifying robustness against backdoor attacks
via randomized smoothing, 2020b.

Chulin Xie, Keli Huang, Pin-Yu Chen, and Bo Li. Dba:
Distributed backdoor attacks against federated learning.
In International Conference on Learning Representations,2020.
Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang,
and Zhihua Zhang. On the convergence of fedavg on
non-iid data. arXiv preprint arXiv:1907.02189, 2019.
Walter Rudin. Principles of mathematical analysis / Walter
Rudin. McGraw-Hill New York, 3d ed. edition, 1976.
ISBN 007054235. URL http://www.loc.gov/catdir/
toc/mh031/75017903.html.
H Brendan McMahan, Eider Moore, Daniel Ramage, SethHampson, and Blaise Aguera y Arcas. Communicationefficient learning of deep networks from decentralized
data. In Proceedings of the 20th International Conferenceon Artificial Intelligence and Statistics, pages 1273–1282,
2017.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated
optimization in heterogeneous networks, 2020.

SparseFed: Mitigating Model Poisoning Attacks in Federated Learning with Sparsification

SparseFed: Supplemental Material

The Appendix is organized as follows:• Appendix A gives full proofs of the theorems in the main body.
– Appendix A.1 the proof of the main certified radius theorem– Appendix A.2 the convergence analysis of the defense– Appendix A.3.1 full computation of Lipschitz constant of a single layer network.
– Appendix A.3.2 procedure for computing certified radius• Appendix B.1 gives details on the methods and metrics used throughout the main body of the paper and the
Appendix.
– Appendix B.1.1 FedAvg– Appendix B.1.2 the attack– Appendix B.1.3 Krum, Bulyan, trimmed mean, coordinate median– Appendix B.1.4 SparseFed implemented with true top-k and FetchSGD– Appendix B.1.5 an adaptive algorithm for selecting k in SparseFed.
– Appendix B.1.6 the metrics used throughout the main body and Appendix.
• The rest of Appendix B gives further experimental results for the conclusions reached in the main body ofthe paper.
– Appendix B.2 the use of `2 norm clipping in SparseFed and prior defenses.
– Appendix B.3 the full range and results of hyperparameters tuned.
– Appendix B.4 the impact of each defense on convergence.
– Appendix B.5 the stealth of the attack.
– Appendix B.6 validates that we are evaluating SparseFed against the strongest available attack.
– Appendix B.7 the compatibility of SparseFed with secure aggregation.
– Appendix B.8 the parameters of the attack and how they are tuned.
– Appendix B.9 the case for SparseFed implemented with FetchSGD as an algorithm which achieves
security and communication efficiency.
• Appendix C discusses the limitations and societal impact of our work.

Panda, Mahloujifar, Bhagoji, Chakraborty, Mittal

A

ProofsA.1

Propagation analysis of sparse aggregation

Here we prove Theorems 2 and 1. Before that, we introduce several definitions that will be used in stating andproving the Theorem.
Notation: Let Z be the data domain and Dt be data sampled (not necessarily i.i.d.) from Z at iteration t. LetΘ be the class of models in d dimensions, and L : Θ × Z ∗ → R be a loss function. A protocol f = (G, A, λ)consists of a gradient oracle G(θ, D, t) → Rd that takes a model, a dataset and a round index and outputs the
update vector ut . f also includes an update algorithm A : ut ∈ Rd → Rd , e.g. P
momentum. λ(t) ∈ R is a learningt
rate scheduler, possibly static, and Λ(t) the cumulative learning rate Λ(t) = i=1 λ(t). The update rule of the
protocol is then defined as θt+1 = θt − λ(t)A(ut ).
Definition 1 (Poisoning Attack [Restated]) For a protocol f = (G, A, λ) we define the set of poisoned protocols
F (ρ) to be all protocols f ∗ = (G ∗ , A, λ) that are exactly the same as f except that the gradient oracle G ∗ isa ρ-corrupted version of G. That is, for any round t and any model θt and any dataset D we have we haveG ∗ (θt , D) = G(θt , D) +  for some  with ||||1 ≤ ρ.
Definition 3 (Coordinate Lipschitz [Restated]) A protocol f (G, A, λ) is c-coordinatewise Lipschitz if for any
round t ∈ [T ], models θt , θt∗ ∈ M, and a dataset D we have that the outputs of the gradient oracle on any
coordinate cannot drift too much farther apart. Specifically, for any coordinate index i ∈ [d]G(θt∗ , D)[i] − G(θt , D)[i] ≤ c · |θt∗ − θt |1 .
Definition 4 ((k, γ)-sparsity [Restated]) A federated learning protocol d = (λ, G, A) is (k, γ)-sparse on a dataset
D if for all ut = G(θt−1 , D) generated during the process of training on D A(ut ) only has k non-zero elements
and we have|A(ut ) − ut |1 ≤ γ.
We will use this definition in our following Theorem. In Subsection A.1.1 we explore the sparsity of the SparseFed
algorithm.

Definition 2 (Certified radius [Restated]) Let f be a protocol and f ∗ ∈ F (ρ) be a poisoned version of the same
protocol. Let θT , θT∗ be the benign and poisoned final outputs of the above protocols on a dataset D. We call R acertified radius for f on a dataset D if ∀f ∗ ∈ F (ρ); R(ρ) ≥ |θT − θT∗ |1 .
Theorem 4. Let f be a c-coordinatewise-Lipschitz and (k, γ)-sparse protocol on a dataset D. Let w = min(d, 2k)
then R(ρ) = Λ(T )(1 + wc)Λ(T ) (ρ + 2γ) is a certified radius for f .
Before proving the above theorem, note that that Theorem 4 immediately implies Theorems 1 and 2.
Proof. Let f ∗ = (G ∗ , A, λ) ∈ f (ρ) be an arbitrary ρ-poisoned version of f . We first define two sequence ofmodels (θb0 , . . . , θbT ) and (θ0 , . . . , θT ) where θbt is the model trained in the first t iterations through the benign(non-poisoned) gradient oracle G and θt is the model trained in the first t iterations through a ρ poisoned
aggregation G ∗ . Also, we define u1b , . . . , uTb and u1 , . . . , ut to be the update vectors that the benign oracle G would
produce on models θb1 , . . . , θbT −1 and θ1 , . . . , θT −1 , respectively. We also define u
b1 , . . . , ubT to be the output of the∗adversarial gradient oracle G on models θ1 , . . . , θT −1 . By the definition of ρ-poisoning, we have |b
ut − ut |1 ≤ ρ.
Note that by the definition of coordinatewise Lipschitzness, for any coordinate i ∈ [d] we have|ut [i] − utb [i]| ≤ c|θt−1 − θbt−1 |1 .
Now, we use the triangle inequality to connect the distance between θt and θbt to that of the previous round as
follows
θt − θbt = θt−1 [i] − λ(t)A(but ) − θbt−1 + λ(t)A(utb ) ≤ θt−1 − θbt−1 + λ[t] A(but ) − A(utb )(1)

Now we prove the following Lemma that bounds the difference between updates on the benign and poisonedmodels.

SparseFed: Mitigating Model Poisoning Attacks in Federated Learning with Sparsification

Lemma 1. We have|A(but ) − A(utb )|1 ≤

X
i∈I

|(b
ut [i] − utb [i])| + 2γ

where I = {j ∈ [d] s.t. A(but )[j] 6= 0 or A(utb )[j] 6= 0}.
Proof. Let τ1 and τ2 be two vectors such that τ1 [i] = 1 if A(but )[i] 6= 0 and τ1 [i] = 0 otherwise. Similarly, τ2 [i] = 1
if A(utb )[i] 6= 0 and τ2 [i] = 0 otherwise. Let I 0 be the locations where τ1 [i] = 1 and τ2 [i] = 1. Now we have|A(ut ) − A(utb )| =
=

d
X
i=1

X
i∈I 0

≤

X
i∈I 0

+

|b
ut [i]τ1 [i] − utb [i]τ2 [i]||(but [i] − utb [i])| +t|(bu [i] − utb [i])| +X
i∈I\I 0

=

X
i∈I 0

=

X
i∈I 0

=

X

≤

X

=

X

i∈I

i∈I

i∈I

≤

X

≤

X

i∈I

i∈I

X
i∈I\I 0X
i∈I\I 0|b
ut [i]τ1 [i] − utb [i]τ2 [i]||but [i]τ1 [i] − utb [i]τ1 [i]||but [i]τ2 [i] − utb [i]τ2 [i]| +|(b
ut [i] − utb [i])| +|(but [i] − utb [i])| +|(but [i] − utb [i])| +t|(bu [i] − utb [i])| +|(but [i] − utb [i])| +X
i∈I\I 0X
i∈I\I 0X
i∈I\I 0X
i∈I\I 0X
i∈I\I 0X
i∈I\I 0|utb [i]τ1 [i] − ubt [i]τ2 [i]||but [i] − utb [i]|(τ1 [i] + τ2 [i]) +|b
ut [i] − utb [i]| +X
i∈I\I 0X
i∈I\I 0|utb [i]τ1 [i] − ubt [i]τ2 [i]||utb [i]τ1 [i] − ubt [i]τ2 [i]||utb [i]τ1 [i] − ubt [i]τ2 [i]||but [i]τ2 [i]| + |utb [i]τ1 [i]||but [i](1 − τ1 [i])| +X
i∈I\I 0|utb [i](1 − τ2 [i])||(but [i] − utb [i])| + |b
ut − A(but )| + |utb − A(utb )||(b
ut [i] − utb [i])| + γ + γ.

which finishes the proof.
Now, based on Lemma 1, the (k, γ) sparsity of f , the Lipschitzness, and since |I| ≤ w we conclude that|A(but ) − A(utb )|1 ≤Xi∈I|(ut [i] − utb [i])| +

X
i∈I

|(b
ut [i] − ut [i])| + 2γ ≤ wc|θt−1 + θbt−1 | + ρ + 2γ.

(2)

By plugging this into Equation 1 we getθt − θbt ≤ (1 + wcλ(t)) θt−1 − θbt−1 + (ρ + 2γ)λ(t).

(3)

Now using this equation, we inductively prove the Theorem. Assume for T − 1 the statement of theorem holds.
By Equation 3 and the induction hypothesis we haveθT − θbT ≤ (1 + wcλ(T ))Λ(T − 1)(1 + wc)Λ(T −1) (ρ + 2γ) + (ρ + 2γ)λ(T ).

(4)Panda, Mahloujifar, Bhagoji, Chakraborty, Mittal

Then, by Bernouli’s inequality we haveθT − θbT ≤ Λ(T − 1)(1 + wc)Λ(T −1)+λ(T ) (ρ + 2γ) + (ρ + 2γ)λ(T )= Λ(T − 1)(1 + wc)Λ(T ) (ρ + 2γ) + (ρ + 2γ)λ(T )≤ (Λ(T − 1) + λ(T ))(1 + wc)Λ(T ) (ρ + 2γ)≤ Λ(T )(1 + wc)Λ(T ) (ρ + 2γ).

And this finishes the proof.
Remark 2 (How does sparsity help robustness?). In our analysis of the effect of sparsity on the certified radius,
we first proved Lemma 1 to show that the effect of poisoning at each iteration is bounded by ρ + 2γ. Note that if
we just use the identity aggregation (which is not sparse), we would get a better bound of ρ for each iteration.
Then, how are we getting a better final bound with sparsity? We emphasize that the goal of sparsity is to boundthe "propagation error" during the entire training. The improved bound is achieved because of the fact thatsparsification removes most of the noise that that poisoning can cause on the updates of benign parties. As we
see in Table 2, our approach can actually reduce the final distance between adversarial and benign models which
verifies our theory and shows the importance of considering the propagation error.
A.1.1

SparseFed is a sparse protocol

The definition of sparsity requires that the aggregation protocol to only update k coordinates. The topk operator,
by definition, only updates k operators. The only thing that remains is to show that SparseFed can achieve asmall gamma as well. Here, we bound the gamma for SparseFed, given a certain loss rate that is a known apriory.
Definition 5. [loss rate ωk for top-k operator] Let ωk be the fraction of l1 mass of information lost via topk ,where topk (u) recovers a 1 − ωk fraction of the l1 mass of u. For any model M , any i ∈ [T ] and update vector(u1 , . . . , un ) calculated by all parties (including benign and adversarial gradients), and memory W , we have:|topk (ut + W t )|1 ≥ (1 − ωk )|ut + W t |1 .

(5)

When clear from the context, we use ω instead of ωk .
We first show that the size of memroy vector W is bounded.
Lemma 2. Let Wt and Wtb be the memory vector at round t for the benign and poisoned protocol respectively.
After each iteration we have√ω
|W i | ≤ L d ·
1−ω
and
√
ω
|Wbi | ≤ L d ·1−ωwhere L is the `2 clipping threshold.
Proof. We prove this by induction on i. The proof is similar for Wi and Wbi so we only prove it for W i . For i = 0
the induction hypothesis is correct. Now assume the hypothesis is correct for round i − 1, namely√|W i−1 | ≤ L d ·

ω
.
1−ω

For round i we have√
|W i | = |Wi−1 + ui−1 − topk (Wi−1 + ui−1 )| ≤ ω(|Wi−1 + ui−1 |) ≤ ω(L d ·√√ωω+ L d) = L d ·1−ω1−ωwhich finishes the proof.
Now we show that after applying topk and memory, we do not deviate much from the original gradient (i.e. γ issmall).

SparseFed: Mitigating Model Poisoning Attacks in Federated Learning with Sparsification√ ω
Lemma 3. Let γ = 2L d 1−ω, we have|topk (ut + W ) − ut |1 ≤ γ.
Proof. Given that the loss rate of the topk is ω, we have√ω
|topk (ut + W ) − ut − W |1 ≤ ω|ut + W | ≤ ω(|ut | + |W |) ≤ L d.
1−ω
Therefore, we have√ω
|topk (ut + W ) − ut |1 ≤ |topk (ut + W ) − ut − W |1 + |W |1 ≤ 2L d
.
1−ω

A.2

Convergence analysis of SparseFed

We first restate the convergence of Error Feedback SGD (EF-SGD) of (Karimireddy et al., 2019) and then analyze
SparseFed under this framework.
A.2.1

Analysis of Error Feedback SGD

Algorithm 4 EF-SGD
Input: learning rate γ, compressor C(·), x0 ∈ Rd
e0 = 0 ∈ Rd
for t = 0, · · · , T − 1 do
gt := stochasticGradient(xt )pt := γgt + etδt := C(ptxt+1 := xt − δtet+1 := pt − δtend forAssumption 3 (Compressor). An operator C : Rd → R is a δ-approximate compressor over Q for δ ∈ [0, 1] if
2

2kC(x) − xk2 ≤ (1 − δ) kxk2 , ∀x ∈ Q
Assumption 4 (Smoothness). A function f : Rd → R is L-smooth if for all x, y ∈ Rd the following holds:|f (x) − (f (x) + h∇f (x), y − xi)| ≤L2ky − xk2
2

Assumption 5 (Moment Bound). For any x, our query for a stochastic gradient returns g such that2

E[g] = ∇f (x)andE kgk2 ≤ σ 2
Theorem 5 (Non-convex convergence of EF-SGD). Let xtt≥0 denote the iterates of Algorithm 4 for any step-size
γ > 0. Under Assumptions 3, 4, 5,
2

min E[k∇f (xt )k ] ≤
t∈T

A.3

2(f (x0 ) − f ∗ ) γLσ 2
4γ 2 L2 σ 2 (1 − δ)++γ(T + 1)2
δ2Analysis of SparseFed

To prove the convergence of SparseFed, we simply use Theorem 5 and prove that the necessary assumptions are
satisfied. That is, we prove that SparseFed fits into the theoretical framework of (Karimireddy et al., 2019).
We know already that the top-k operator we use is a δ-approximate compressor (Karimireddy et al., 2019), which
satisfies the first assumption. The second and third assumptions, we directly reproduce for the gradient oracle
that represents the individual device gradients.

Panda, Mahloujifar, Bhagoji, Chakraborty, Mittal

Figure 4: SparseFed converges at the same rate as the baseline (FedAvg) on CIFAR10 in the cross-device setting
2

Assumption 6 (Smoothness). L is `-smooth if ∀x, y ∈ Rd |L(x) − (L(y) + h∇L(x), x − yi)| ≤ 2` kx − yk22Assumption 7 (Moment Bound). For any x, our oracle returns g s.t. E[g] = ∇θ(x) and E kgk2 ≤ σ 2

Because SparseFed is essentially EF-SGD for federated learning, it only remains to show that the federated
setting does not complicate our analysis. The federated setting comes with the complications of LocalSGD,
namely multiple local epochs, and the non-i.i.d. distribution of data across devices.
As per the statement of Theorem 3, we only prove guarantees for τ = 1; that is, we only do a single local epoch.
Prior work has evidenced the challenges of analyzing convergence of LocalSGD in the presence of non-i.i.d. data
(Li et al., 2019), and we find empirically that multiple local epochs are unfavorable for both convergence androbustness in the cross-device setting that is the focus of our work.
Therefore, SparseFed directly fits into the theoretical framework of (Karimireddy et al., 2019) and Theorem 5
proves the convergence of SparseFed.
In Fig 4 we empirically validate the speed of convergence of SparseFed and find that it converges at the samerate as FedAvg, even in the presence of attackers.
A.3.1

Training a single layer neural network with SGD

Example 2 (Training a single layer neural network with SGD). In this example, we compute the coordinatewise
Lipschitz constant of the SGD protocol for a single layer neural network defined as σ(θx), where σ is the softmax
function and θ ∈ Rd are the network parameters. For cross-entropy loss-based training using dataset D, we showthat the constant c = 41 . Formally,
sup
D∈Z,θ1 ,θ2 ∈M|G(θ1 , D)[i] − G(θ2 , D)[i]|1 ≤1|θ1 − θ2 |1 for any coordinate index i ∈ [d]4Without loss of generality, we assume that dataset D is comprised of samples of the form (x, y), where x ∈ [0, 1]m ,and y ∈ {0, 1}C is the one-hot encoded representation of any of the C classes. For the single layer neural network,
the model parameters are denoted by θ ∈ RC×m , and the softmax layer by the function σ(·). The neural network
can thus be represented as Φ(x, θ) = σ(θx).

SparseFed: Mitigating Model Poisoning Attacks in Federated Learning with Sparsification

We define g(θ, x) = ∂L(Φ(x,θ),y)where L is the softmax cross entropy loss function. For the SGD protocol,∂θA(u) = u, and G(θ, D) = g(θ, x). Our goal is to find a Lipschitz constant L such that, for all indices i ∈ [C] andj ∈ [m],|g(θ1 , x)ij − g(θ2 , x)ij |1
sup
≤L
(6)
|θ1 − θ2 |1
x∈D,θ1 ,θ2
We define intermediate variable z = θx and the neural network output distribution p = σ(z), such that bothztp, z ∈ RC . Note, for a given target class t, the cross entropy loss function L(p, y) = − log (pt ) where pt = Pe ezj .
j
Thus,
C
X
∂L
∂L ∂zcg(θ, x)ij =
=
.
(7)
∂θij
∂z
c ∂θij
c=1
∂zc
∂L
∂L
Computing the terms of (7), we have ∂z= pt − 1 for c = t; and ∂z= pc otherwise; and ∂θ= xj . Thus,ccijg(x, θ)ij==

xj (pt − 1) for i = t

xj pi for i 6= t

(8)

We compute the Hessian of g(x, θ)ij as:∂g(x, θ)ij
∂θkl

= xj pt (1 − pt )xl for k = t= xj pk (1 − pk )xl for k 6= t

(9)where k ∈ [C], l ∈ [m]. The maximum value of the Hessian in (9), occurs at xj = xl = 1, and pt = pk = 12 . Thus,∂g(x, θ)ij
i,j,k,l
∂θkl
max

≤
≤

1
4
1
4

for k = t
for k 6= t

(10)

To obtain the Lipschitz constant, we first define the function
h(t) = g((1 − t)θ1 + tθ2 , x)ij where t ∈ [0, 1]
Thus, h(0) = g(θ1 , x)ij and h(1) = g(θ2 , x)ij . Since, the function h(t) is differentiable everywhere in (0, 1), using
Mean Value Theorem Rudin (1976), we know that there exists a point t∗ ∈ (0, 1) such that:h(1) − h(0) ≤ h0 (t∗ ) where h0 (t) = (θ2 − θ1 )g 0 ((1 − t)θ1 + tθ2 , x)ijkl .

(11)

Rewriting (6), we getsupx∈D,θ1 ,θ2≤

supx∈D,θ1 ,θ2|g(θ1 , x) − g(θ2 , x)|1
| max{g(θ1 , x)ij − g(θ2 , x)ij }|1i,jLet i∗ , j ∗ correspond to the indices where the maximum in the above equation occurs. Combining (10) and (11),we get:1
sup |g(θ1 , x)i∗ j ∗ − g(θ2 , x)i∗ j ∗ |1 ≤ |θ1 − θ2 |1(12)
4
x∈D,θ1 ,θ2Comparing (12) with (6) we get c = 41 .
A.3.2

Computing the certified radius

Algorithm 5 calculates the maximum distance between the poisoned and benign models, based on the number ofattackers, protocol parameters c, λ defined in Definition 3, number of iterations T , clipping parameter L, thedimension of the model d and sparsification parameter k. The correctness of this procedure follows from the proofof Theorem 2.

Panda, Mahloujifar, Bhagoji, Chakraborty, Mittal

Algorithm 5 Radius calculation
Input: poisoning parameter ρ, number of model weights to update each round k, number of timesteps T , decay function
λ, model parameters θ, test dataset (x, y)mi=1 , Lipschitzness c, error γ
r=0
β =+γfor t = 1, 2, · · · T do
α = 1 + 2λ(t)ckr = r ∗ α + λ(t)β
end for
Output: radius r

B

Methods and Metrics

B.1

Methods

In this section we give a detailed treatment of the methods we compare. We run all experiments on commerciallyavailable NVIDIA Pascal GPUs. With this in mind, all implementations are optimized to run on a single GPU
and all our experiments can be reproduced within a few hours (SparseFed) or days (Byzantine-robust aggregation
methods).
B.1.1

FedAvgWe use the standard implementation of federated averaging McMahan et al. (2017), described in Algorithm 6, as
the baseline for all defenses in this work. The first major departure is the use of `2 clipping, which is in place
whenever we refer to the `2 clipping defense. When we refer to an "undefended" system, we do not make useof `2 clipping. As an implementation detail, we average updates and not individual models because we employ
norm clipping in all defenses and clipping model parameters wholesale is more difficult than clipping updates.
The second major departure is the use of server-side momentum, which has empirically been shown to improve
convergence (Rothchild et al., 2020).
Local epochs make outlier detection difficult: From an adversarial perspective, FedAvg has a key vulnerability: the use of multiple local epochs τ , which is a design choice to amortize communication costs. As thenumber of local epochs τ → ∞, individual updates from benign devices become further apart in `2 space. This
makes it difficult for Byzantine-robust aggregation rules such as Bulyan and Krum to identify outliers, because
both attacker updates and benign updates are very far apart. Therefore, when benign devices do multiple local
epochs, attackers are more likely to remain undetected by outlier detection methods. To ensure we are comparing
against the strongest versions of the Byzantine-robust aggregation rules possible, we use τ = 1.
Local epochs amplify existing vulnerabilities: Even when the number of local epochs τ = 1, FedAvg with
`2 clipping does not reduce to distributed SGD because devices scale their updates by the learning rate before
doing norm clipping. This presents an opportunity for the attacker: when the global learning rate is very small,such as towards the end of training when using a typical decaying learning rate schedule, the updates of mostbenign devices will have `2 norm close to 0. Here, the attacker can simply project their update to the perimeterof the `2 norm constraint and essentially have an update which is hundreds of times larger than the rest of thebenign devices, which enables them to perform model replacement. In Appendix B.2 we propose and evaluate amethod to mitigate this vulnerability.
Model replacement: Model replacement has already been proposed as an attack strategy in prior work
(Bagdasaryan et al., 2020) because state of the art models often converge to a stationary point towards the end of
training. This vulnerability is simply amplified in federated learning, because all federated learning deployments
today make use of multiple local epochs, as update communication is the system bottleneck.
Uncompressed FL is more robust than FedAvg: In Table 7 we show that using distributed SGD as the
backbone algorithm rather than FedAvg has a marked impact on the attack accuracy. We refer to this regime as"uncompressed FL" because we are not compressing communication costs, and note that this regime is strictly
unrealistic. Even in the uncompressed regime, the attack still functions via model replacement, because thebenign objective reaches a stationary point and the gradients from benign devices are very small. We note thatwhile the attack does not reach 100% accuracy against the `2 defense in this setting, when we incorporate minor

SparseFed: Mitigating Model Poisoning Attacks in Federated Learning with Sparsification

Algorithm 6 SparseFed
Input: learning rate λ, number of timesteps T , local batch size b, number of devices selected per round n, norm clipping
parameter L, local epochs τ , local learning rate γ
Initialize model θ0 using the same random seed on the devices and aggregator
Initialize momentum vector Rt = 0
for t = 1, 2, · · · T do
Randomly select n devices d1 , . . . dnloop {In parallel on devices {di }ni=1 }Download new model weights θt = θ
for m ∈ τ doP
Compute gradient gti = 1b lj=1 ∇θ L(θt , Dj )Accumulate gradient θt = θt − γ(t, m)gti
end forCompute update uit = θt − θClip update uit = uit · · · min(1, |uLt | )i 2
end loopPnAggregate gradients ut = n1 i=1 uit
Momentum Rt = 0.9Rt + ut
Update θt+1 = θt − λ(t)Rt
end for T
Output: θt t=1

Table 7: Attack accuracy decrease for `2 norm clipping and SparseFed when doing uncompressed FL (SGD) as
compared to using FedAvg. CIFAR10, 1e4 clients, 200 attackers.
DefenseTest acc

Attack acc (decrease)

Attack acc`2SparseFed

84.07 ±0.781.72 ±0.9

34.0 ±620.0 ±566.0 ±65.6 ±1adjustments to the attack (Appendix B.8) we can reach 100% accuracy; SparseFed still functions well as adefense.
In Appendix B.9 we introduce a communication-efficient variant of SparseFed which can drop the use of multiple
local epochs altogether, and therefore obtains improved robustness empirically.
Momentum is necessary for convergence: As an implementation detail, we employ momentum factor
masking (Rothchild et al., 2020) in SparseFed. This entails maintaining a momentum buffer which we zero out
similar to the error feedback vector. We provide the momentum enabled algorithm in Algorithm 7 We do not
analyze the role of momentum in robustness, but it is empirically useful.
In Table 8 we see that without the use of momentum, neither the model nor the attack converge when using just
FedAvg with `2 clipping. This is what SparseFed reduces to as k → d, because at every iteration we zero out theentire momentum buffer.
B.1.2

The Attack

In Algorithm 8 we provide the model poisoning attack that we use throughout this work. This attack is similar to
the PGD attack proposed in prior work (Sun et al., 2019), with the addition of the attacker batch size parameter
which enables us to poison models with larger auxiliary datasets. In Appendix B.8 we provide detailed analysis
on how we choose the attacker batch size and number of PGD epochs. The attackers sample data from theTable 8: Test/Attack accuracy decrease for `2 norm clipping when not using momentum. CIFAR10, 1e4 clients,
200 attackers.
DefenseTest Acc (decrease)

Test acc

Attack acc (decrease)

Attack acc`2

31.08 ±0.753.14 ±1.761.4 ±6

4.6 ±1

Panda, Mahloujifar, Bhagoji, Chakraborty, Mittal

Algorithm 7 SparseFed
Input: number of coordinates to update each round k, learning rate λ, number of timesteps T , local batch size b, numberof devices selected per round n, norm clipping parameter L, local epochs τ , local learning rate γ
Initialize model θ0 using the same random seed on the devices and aggregator
Initialize memory vector Wt = 0, momentum vector Rt = 0
for t = 1, 2, · · · T do
Randomly select n devices d1 , . . . dnloop {In parallel on devices {di }ni=1 }Download new model weights θt = θ
for m ∈ τ doP
Compute gradient gti = 1b lj=1 ∇θ L(θt , Dj )Accumulate gradient θt = θt − γ(t, m)gti
end forCompute update uit = θt − θClip update uit = uit · · · min(1, |uLt | )i 2
end loopPnAggregate gradients ut = n1 i=1 uit
Momentum: Rt = 0.9 · Rt−1 + ut
Error feedback: Wt = Rt + Wt
Extract topk : ∆t = topk (Wt )Error accumulation: Wt+1 = Wt − ∆tUpdate θt+1 = θt − λ(t)∆t
end for T
Output: θt t=1"auxiliary dataset", a dataset which is composed of datapoints with their labels flipped that the attacker uses as
a proxy to formulate the poisoned gradient.
Algorithm 8 Attack
Input: learning rate η, local batch size `, norm clipping parameter L, number of local epochs e
1: This procedure is used by all attackers in a round to ensure that they upload the same update
2: for number of PGD epochs ei ∈ e doP
3:Compute stochastic gradient git on batch Bi of size `: git = 1` lj=1 ∇M L(Mtei , Dj )cet
4:Update local model M= Mte − ηgit
i+1

i

cet
5:
Project accumulated update onto the perimeter of the `2 constraint Mtei+1 = M0t − CLIP (M− M0t )
i+1
6: end for
Output: Mte

B.1.3

Byzantine-resilient defenses

Every algorithm we describe in this section is implemented via replacing line 15 in Algorithm 6. This introduces
additional computational complexity into the aggregation step, which is the bottleneck in federated learning.
This complexity can be minor (trimmed mean) or it can be massive (Bulyan). Our experiments with Bulyan
take approximately 20× longer to run than our experiments with SparseFed; because these experiments are socomputationally infeasible, where possible we omit Bulyan from comparisons in the rest of the Appendix. These
defenses as initially proposed do not make use of `2 norm clipping, but because we use `2 clipping in the baseline
defense, and because it benefits all defenses (Appendix B.2), the input gradients to all the aggregation rules are
already clipped.
Trimmed mean: In Algorithm 9 we see that trimmed mean iteratively rejects outliers at each coordinate until
it has eliminated 2f coordinates. If the attacker’s updates have extremely small or large values, then trimmed
mean will mitigate the attack. However, if most of the attacker’s updates are close to 0 at many coordinates,
then trimmed mean will not mitigate the attack. This is the phenomena observed in (Bhagoji et al., 2019); theattacker’s updates are far sparser than benign updates, which in turn means that most coordinate values are 0
and thus trimmed mean is ineffective.
Coordinate median: Coordinate median is simply implemented by returning the coordinatewise medianinstead of the mean. This does not converge because of the gap between median and mean (Chen et al., 2020;

SparseFed: Mitigating Model Poisoning Attacks in Federated Learning with Sparsification

Algorithm 9 Trimmed meannInput: number of compromised devices f , set of individual updates U = ut i=1
1: for number of compromised devices f do
2:
for each coordinate {c}dj=1 do
3:
Uc ← Uc \ min Uc
4:
Uc ← Uc \ max Uc
5:
end for
6: end forPn−2f t1
7: Aggregate remaining updates ut = n−2f
i=1 ui
Output: ut

Muñoz-González et al., 2019; Yin et al., 2019).
Algorithm 10 KrumnInput: number of compromised devices f , set of individual updates U = ut i=1
t
1: for each update ui do
2:
Ui = U3:
for f+2 do
4:
Ui = Ui \ arg maxut ∈Ui utj − utij5:
end forPtt
6:Si = uj ∈Ui uj − ui
7: end for8:
Output: ut = arg minu∈U S

Krum: Algorithm 10 implements Krum, which attempts a Byzantine-resilient variant of the barycentric
aggregation rule (Blanchard et al., 2017a). Krum selects a single update from the aggregated set to update theglobal model. In the cross-device federated setting, this will never converge. Essentially, we will be using SGD
instead of minibatch SGD, and it will take us 100× longer to do one pass over the entire dataset. Because Bulyan
uses Krum and trimmed mean, we do not analyze Krum in isolation in depth.
Algorithm 11 Bulyan
nInput: number of compromised devices f , set of individual updates U = ut i=1
1: Θ = n − 2f
2: S = ∅3: while |S| < Θ do
4:
p = KRUM(U, f )5:
U ←U \p6:
S ←S∪p7: end while
Output: ut = TRIMMEAN(S, f )Bulyan: Algorithm 11 describes Bulyan (Mhamdi et al., 2018) implemented with Krum as the base aggregation
rule. Bulyan builds a set by iteratively applying Krum onto the set of aggregated updates, and then returns thetrimmed mean of this set. If Krum selects the attacker, we already know that trimmed mean is not likely toreject the attacker. Thus, it remains to intuit why Krum will select at least one attacker. In the non-i.i.d. setting,benign update vectors are sufficiently far away that a very small number of colluding attackers at each iteration
can minimize their distance to all other vectors by sending the same update, which ensures that they have a
distance of 0 from each other. Thus, Krum selects at least one attacker, and Bulyan fails, as we show in our
experiments.
It is readily apparent that for large values of n, Bulyan is fairly computationally inefficient even when implemented
efficiently. Although the asymptotic complexity of Bulyan is the same as that of Krum, the constant factor isquite large (n = 100).

Panda, Mahloujifar, Bhagoji, Chakraborty, Mittal

B.1.4

SparseFed

In the main body we include the algorithm for SparseFed implemented with true top-k. As an implementation
detail, the algorithm presented in the main body is in the uncompressed regime, where we do not perform any
local epochs and the learning rate is multiplied after the top-k coordinates are extracted.
Algorithm 12 SparseFed implemented with FetchSGD instead of global top-k
Input: number of model weights to update each round k
Input: learning rate η
Input: norm clipping parameter L
Input: number of timesteps T
Input: momentum parameter ρ, local batch size `Input: Number of clients selected per round W
Input: Sketching and unsketching functions S, U
1: Initialize S0u and S0e to zero sketches
2: Initialize model θ0 using the same random seed on the devices and aggregator
3: for t = 1, 2, · · · T do
4:
Randomly select n devices d1 , . . . dn
5:loop {In parallel on devices {di }ni=1 }6:Download new model weights
θ
P t=θ
7:
Compute gradient gti = 1b lj=1 ∇θ L(θt , Dj )8:
Clip git according to L: git = git ∗ min(1, |gLt | )i 2

9:Sketch git : Sti = S(git ) and send it to the Aggregator10:
end loop
PW t
1
11:Aggregate sketches St = W
i=1 Sitt−1
12:Momentum: Su = ρSu + St
13:
Error feedback: Ste = ηStu + Ste
14:
Unsketch: ∆t = Top-k(U(Ste ))15:
Error accumulation: St+1
= Ste − S(∆t )e
16:
Update θt+1 = θt − ∆t
17: end for
T
Output: wt t=1

FetchSGD: Algorithm 12 is the FetchSGD algorithm (Rothchild et al., 2020) combined with `2 clipping. FetchSGD
approximates true top-k and has been empirically shown to be communication efficient; in Appendix B.9 we validate
the robustness of SparseFed implemented with FetchSGD. Because SparseFed implemented with FetchSGD canachieve communication efficiency without the use of multiple local epochs, it has improved robustness overSparseFed implemented with true top-k, which still requires multiple local epochs for communication efficiency.
B.1.5

Adaptively choosing k in SparseFed

The hyperparameter k is critical for the convergence of SparseFed. In Algorithm 13 we provide an adaptivealgorithm for selecting k. The algorithm requires as input the maximum information loss tolerance due tosparsification, and essentially just performs binary search over a range of reasonable values of k until finding thesmallest k that does not lose "too much" information.
B.1.6

Metrics

In the main body, we mainly use the attack accuracy metric for the fixed cross-silo and cross-device settings.
However, in the rest of the Appendix we do not always use this setting when it does not illustrate the full breadthof a trend, and we note that attack accuracy is not a perfect metric. For example, when trying to poison 1 point,
the attackers can trivially obtain 100% attack accuracy, but this is not the case when they are trying to poison
100 points. Similarly, 100 attackers will have an easier time poisoning 1 point than 1 attacker will. To addressthese shortcomings, we introduce a new metric.
Outsized Impact Factor (OIF) We first define some notation. Let S be the set of agents participating inb|federated learning, and Sb the set of benign agents so that I = |S\S
is the influence of the attacker on the|S|system, represented as the fraction of agents which are compromised. We propose that the baseline for any model
poisoning attack should be for the attackers to be able to poison datapoints (e.g. flip the label on that datapoint)SparseFed: Mitigating Model Poisoning Attacks in Federated Learning with Sparsification

Algorithm 13 Selecting k
Input: model θ, maximum information loss ω, number of model parameters d, number of iterations in an epoch r, numberof gradients to sample n (more samples gives a better estimate of ω)
1: set initial k k = dr
2: set initial realized information loss δ = ∞3: while δ > ω do
4:compute n sample minibatch gradients {g}nj=1 |gj = ∇θ L(θ, zj )5:
extract top-k {u}nj=0 |uj = topk (gj )P
6:calculate average l1 mass lost δ ∗ = n1 n
j=1 |gj − uj |1
7:
update δ = min(δ, δ ∗ )8:
if δ > ω then9:k = k + dr
10:
end if
11: end while
Output: k

DefenseTrimmed mean
BulyanAttack Accuracy (without)
100
100

Attack Accuracy (with)
81.4
81.8

Table 9: In the cross-device setting of CIFAR10, trimmed mean and Bulyan benefit greatly from the use ofadaptive clipping.

bm proportional to their influence I. Therefore, if |X
bm | is the number of datapoints successfully poisoned and nXm|is the total number of datapoints controlled by all agents in the system, we define |X
I·n , which is the ratio of
datapoints successfully poisoned relative to the influence of the attacker, normalized by the size of the dataset, as
the outsized impact factor (OIF). This quantity determines the extent to which the attacker is able to ‘punch
above its weight’ in terms of impacting the final model to a larger extent than its influence would already allow.

b

Our standard for a successful attack is an OIF of 1. This means that the attacker can poison the same fraction of
the dataset as of the client population they control. By using the OIF metric as a heuristic for attack success,we can easily compare the efficacy of attacks across parameter settings when different numbers of attackers arepresent.
B.2

Norm Clipping

Adaptive clipping to mitigate the vulnerability of FedAvg As we note in Appendix B.1.1, the key
vulnerability of FedAvg is that benign devices multiply their gradients by a small learning rate that can vary overthe course of training, which can make their gradients smaller than the specified `2 norm clipping bound when
the learning rate is small (e.g. when warming up the learning rate schedule at the start of training). However, theattack is under no such compulsion, and this can present an easy vulnerability for the attacker. To mitigate this,
we propose the use of an adaptive `2 clipping schedule which simply mirrors the learning rate schedule. At each
iteration, before we clip the device gradient to the specified norm L, we scale L by the learning rate L := L · λ(t).
In Table 9 we ablate the effectiveness of this on trimmed mean and Bulyan.
Sparsification needs norm clipping
We perform ablations of the central idea of the paper, sparsification as a defense against model poisoning attacks,
with and without the use of `2 norm clipping.
In Fig. 5 we compare the efficacy of the combination of the distributed poisoning attack and the PGD attack
against the topk defense, with and without `2 clipping with parameter 3. We observe that when `2 clipping isin place, sparsification completely mitigates the attack. However, without any clipping the attacker is able tosuccessfully flip the labels of their entire auxiliary dataset. This is because without any constraint on the norm of
its update, the attacker can massively magnify its update and ensure that all the coordinates in the topk are in
the direction of the adversarial optimum.
Byzantine-Robust Aggregation Benefits from Norm Clipping The prior defenses we consider (Krum,Panda, Mahloujifar, Bhagoji, Chakraborty, Mittal

Figure 5: Pareto frontier of the combination of distributed poisoning and PGD attacks against SparseFed
defenses with and without `2 clipping. Without `2 clipping, sparsification is entirely unable to mitigate the attack.
CIFAR10, 10000 devices, 100 attackers.
Table 10: Implementing norm clipping greatly mitigates the effectiveness of the attack against Bulyan andtrimmed mean when no colluding attackers are present. CIFAR10, 1e4 devices, 100 attackers.
DefenseTest acc

Attack acc

Bulyan (`2 )BulyanTrimmed Mean (`2 )Trimmed

83.64
84.94
77.42
81.99

10.0
38.6
71.6
100.0

Bulyan, trimmed mean, coordinate median) do not require norm clipping as part of the implementation. Normclipping will either help the defense by limiting the impact of the attacker, in which case the server will enforce
norm clipping, or it will hurt the defense by making the attack more stealthy, in which case the attacker will use
norm clipping. In Table 10 we compare the changes in test and attack accuracy for Bulyan and trimmed mean
when implementing norm clipping (Krum and coordinate median do not converge). As expected, norm clipping
limits the impact of the attacker and helps Bulyan mitigate the attack when no colluding attackers are present.
B.2.1

Robustness in the DP defense costs accuracy

Prior work proposed combining `2 norm clipping and adding Gaussian noise to ensure robustness, similar to theprocess adopted in DP-SGD. In this work, we assume that practitioners will not be willing to adopt defenses
which negatively impact the test accuracy of their models in scenarios where attackers are not present. We notethat this is distinct from the accuracy degradation incurred from using a communication-efficient algorithm
such as FetchSGD as a defense, or deploying DP-SGD to ensure differential privacy. In these cases, adversarialrobustness can be seen as an additional benefit that ‘comes for free’. However, the parameters that we findallow for some adversarial robustness at the cost of test accuracy for the DP defense do not actually enable any
differential privacy. As a result, we do not use these parameters for most of our experiments because we do notbelieve practitioners will adopt a defense which significantly negatively impacts their model performance.
In Fig. 6 we examine the effect of adding noise n ∼ N (0, σ 2 = 0.001). This noise parameter is identical to theone chosen in 1 As mentioned above, this amount of noise is entirely insufficient to ensure any differential privacy
guarantees. We show the pareto frontier of the combination of distributed poisoning and PGD against the `2
defense with a parameter of 5, with and without noise addition. We find that when no attackers are present, adding
noise reduces the test accuracy by a minimum of 12%, whereas not adding noise does not reduce the test accuracy
at all. Therefore, while adding noise can make the model more robust, it is also guaranteed to significantly
1

Sun et. al. 2019: https://arxiv.org/abs/1911.07963

SparseFed: Mitigating Model Poisoning Attacks in Federated Learning with Sparsification

Figure 6: Pareto frontier of the `2 defense with clipping parameter 5, with and without noise addition, against
the attack. Although noise addition can improve the robustness of the model to attackers, it also degrades test
accuracy. In situations where no attackers are present, adding enough noise to mitigate any possible attackers
will reduce the test accuracy by > 10%. Because we do not expect practitioners will adopt any defense which isguaranteed to reduce the performance of their models by such a nontrivial amount, we do not use noise addition.
(points with low OIF either do not make use of PGD or have too small batch sizes) CIFAR10, 10000 devices, 100
attackers.

degrade model performance. In keeping with the aforementioned systemic assumption that practitioners will notuse defenses which damage model performance, we do not use noise addition in most experiments.
We nevertheless perform a comparison of the DP defense with `2 parameter 5 and noise addition with σ 2 = 0.001,
against SparseFed in Fig. 7. Our findings reinforce our prior conclusions. While adding noise with strict clipping
is sufficient to mostly mitigate the attack, it comes at the cost of an egregious 20% test accuracy drop. By
comparison, SparseFed suffers little accuracy degradation and mitigates the attack even better.
B.3

Hyperparameter Tuning

B.3.1

Dataset Parameters

CIFAR Parameters: In all experiments we train for 24 epochs, with 1% of clients participating each round, for
2400 total iterations. We use the standard train/test split of 50000/10000. We split the dataset into 10000 clients,
each of which has 5 points from a single target class. In each round we have 100 clients participating, inducing abatch size of 500 (this is of course increased when an adversary participates). We use standard data augmentation
techniques: random crops, random horizontal flips, and the images are normalized according to the mean andstandard deviation during training and testing. We do not use batch normalization in any of our experiments,
because batch normalization does not work well on batches of 5 (batch normalization has to be conducted at a
per-client level). We use a triangular learning rate schedule which peaks at 0.2. We use a momentum constant of
0.9. These training procedures and the ResNet9 architecture are drawn from Page 2 .
FEMNIST Parameters: The FEMNIST dataset is composed of 805,263 28 × 28 pixel grayscale images which
are distributed unevenly across 3,550 classes/users. Per user, there are an average of 226.83 datapoints, with astandard deviation of 88.94. To preprocess the data, we use the script in the LEAF repository with the command:./preprocess.sh -s niid –sf 1.0 -k 0 -t sample. After discarding some datapoints, we end with a datasetof 706,057 training samples and 80,182 validation samples across 3,500 clients ala Leaf 3 .
The model architecture we use is a 40M-parameter ResNet101, but we replace the batch norm with layer norm
because batch norm does not work well with small batch sizes. The average batch size is ≈ 600 but it can vary
based on the clients that are sampled. We again use the standard data augmentations of random cropping and23

https://myrtle.ai/learn/how-to-train-your-resnet/
https://tinyurl.com/u2w3twePanda, Mahloujifar, Bhagoji, Chakraborty, Mittal

Figure 7: Pareto frontier of the `2 defense with noise addition and clip parameter 3, and SparseFed implemented
with topk and FetchSGD with clip parameter 3, against the combination of distributed poisoning and PGD.
The attack was given the same grid search against all 3 defenses: [50, 100, 200, 400] × [5, 7, 9]. Although noise
addition is able to mitigate the attack, it suffers dramatically reduced test accuracy when compared to SparseFed;
SparseFed achieves lower OIF with 10% higher test accuracy. CIFAR10, 10000 devices, 100 attackers.
Table 11: FedAvg convergence does not benefit from doing multiple local epochs. We use local learning rate=0.9,
but even for a small number of local epochs convergence does not benefit, and at these small number of local
epochs a smaller local learning rate would not have much impact because the exponential decay factor is notlarge. CIFAR10, 10000 devices, no attackers.
Num. epochs

Test acc decrease

Test acc

1
2
5

0
0.41
80

90
89.59
10

flips, and a triangular learning rate schedule. We train for only 1 epoch; this mimics the federated setup where
we expect to only use each client once. We increase the learning rate from 0 to 0.01 over 15 th of the dataset, andthen decrease the learning rate back to 0.
FedAvg Parameters: As we discuss in Appendix B.1, we use a standard implementation of FedAvg where there
are three algorithmic hyperparameters: the number of local epochs, the local batch size, and the local learning
rate decay. Prior work has already shown that the use of multiple local epochs does not improve convergence inthe regime of small and non-i.i.d. datasets (Rothchild et al., 2020), and multiple algorithmic variants have been
proposed to address this (Li et al., 2020) which are out of the scope of this work. Furthermore, the prior defenses
considered in this work rely on approximating some consensus mechanism between benign devices based on thecloseness or agreement of benign updates (Mhamdi et al., 2018). As the number of local epochs increases, thisconsensus falls apart, and so for the sake of fairness we do not evaluate defenses with more than one local epoch.
In Table 11 we do our own experiments to validate that FedAvg convergence does not benefit from multiple local
epochs.
B.3.2

Defense parameters

Norm clipping parameter: For the `2 defense, we tune the value of the clipping parameter. We test values
for the `2 defense of (1, 3, 5, 10). Where possible, we do a grid search over as many parameters as possible to findthe limit of the attacker’s ability.
First we validate the `2 defense against the baseline attack empirically in Table 12, which shows that byappropriately choosing the `2 parameter, the OIF is reduced significantly. There is a clear tradeoff: using stricter`2 norm clipping mitigates the attack further, but at the cost of reduced test accuracy.

SparseFed: Mitigating Model Poisoning Attacks in Federated Learning with Sparsification

Table 12: The appropriate choice of the norm clipping parameter greatly mitigates the effectiveness of the baseline
attack on CIFAR with auxiliary set of size 500. CIFAR10, 10000 devices, 100 attackers.
Clipping param.

Test acc

Attack acc

10
5
1

0.7972
0.83
0.691

1
0.136
0.014

Figure 8: Pareto frontier of the `2 defense, comparing clipping parameters of 3 and 5. Although using a stricter
norm clipping parameter can reduce OIF, it comes at the cost of test accuracy degradation. We find that whenno attackers are present, using a norm clipping parameter of 5 does not sacrifice any test accuracy, whereas using
a norm clipping parameter of 3 sacrifices > 5% test accuracy. Because we do not expect practitioners will adopt
any defense which is guaranteed to reduce the performance of their models by such a nontrivial amount, we use aclipping parameter of 5. CIFAR10, 10000 devices, 100 attackers.

In Fig. 8 we examine the effect of using stricter clipping in the `2 defense. We show the pareto frontier of ourattack against the `2 defense with two choices of the `2 parameter: 3 and 5. We find that when no attackers arepresent, using a parameter of 3 admits a minimum of 5% test accuracy degradation, while using a parameterof 5 does not reduce test accuracy at all in the same scenario. Therefore, while using a smaller norm clipping
parameter can make the model more robust, it is also guaranteed to always reduce test accuracy. In keeping withthe aforementioned systemic assumption that practitioners will not use defenses which damage model performance,
we use the parameter of 5 in most experiments. For all further experiments, we show 5 as the parameter for the`2 defense, balancing test accuracy and adversarial robustness.
SparseFed parameters: For SparseFed we tune the value of k, the number of coordinates which are updated ateach iteration. We test values of [1, 5, 10, 50, 100, 200, 400] × 103 and report most experiments using the value of
5 × 103 on CIFAR10/CIFAR100/FMNIST, and use the value of 400 × 103 . In the main body, we include graphs
for the tradeoffs revolving around k.
In Fig. 9 we show the tradeoff between k, test accuracy, and attack accuracy for the uncompressed setting. In themain body, FedAvg is the baseline and as noted in (Bagdasaryan et al., 2020), the attacker can simply perform
model replacement at the last iteration because the learning rate is nearly 0. However, in the uncompressed
setting this is not possible, so we do not see the same trend as in the main body. In Appendix B.9 we showcase
an algorithm which can realistically be implemented without using FedAvg to compress communication costs.
B.4

Impact of Defenses on Test Accuracy

Practitioners in federated learning prioritize the convergence of their models, and attempt to optimize tradeoffs
of convergence with communication efficiency, security, and privacy. In Table 13 we show the decrease in test
accuracy when no attackers are present for each defense evaluated in this work. We train each model for exactlyPanda, Mahloujifar, Bhagoji, Chakraborty, Mittal

Figure 9: Tradeoff between sparsification parameter k (x axis, in logscale from 1000 to k = d = 6568640), test
accuracy when attackers are present (left axis, blue), and attack accuracy (right axis, red) for uncompressed FL.
In the uncompressed setting, no choice of k allows the attack to succeed, because as k → d no momentum ispresent and neither the attack nor the model converge. CIFAR10, 10000 devices, 200 attackers.
Table 13: Comparing the impact on test accuracy of the defenses. CIFAR10, 10000 devices, no attackers (averaged
over 3 runs).
DefenseTest Acc. decrease

Test Acc

No defense`2
KrumMedianTrimmed mean (f = 5)
Bulyan (f = 5)
Bulyan (f = 10)
SparseFed (k = 5e3)
SparseFed (k = 5e4)0 ±0
2.0 ±0.1
80.0 ±080.0 ±012.58 ±0.818.88 ±0.79
66.48
6.82 ±0.7
3.0 ±0.01

90.0 ±0.1
88.0 ±0.1
10.0 ±0
10.0 ±077.42 ±0.871.12 ±0.79
23.52
83.18 ±0.7
87.0 ±0.01

2400 iterations using the same triangular learning rate schedule. Because the Byzantine-resilient aggregation rules
rely on outlier detection, they must necessarily throw away information even when attackers are not present. We
set the robustness parameter f = 5 to give an idea of the tradeoff for these algorithms, because including a fullcurve is computationally infeasible. Bulyan drops more test accuracy than trimmed mean, because Bulyan throws
away 4f + 2 updates at each coordinate whereas trimmed mean only throws away 2f updates at each coordinate.
As we explain in the main body of the work, Krum and coordinate median do not converge in this setting.
B.5

Stealth of Attack

Successful attacks are stealthy attacks: A necessary component of a successful attack is relative stealth. If
an attacker can only successfully poison the model by overwriting all of the model’s parameters that are necessary
to achieve good performance on benign data, we do not consider this a viable attack. In any practical deployment,
the entity coordinating federated learning would simply discard a model with such low accuracy after runningthe model on a private test set. We draw points for the auxiliary dataset from the test set. This can force thetest accuracy to drop by as much as 5% when the attacker poisons the model with perfect accuracy over an
auxiliary set of size 500 out of a test set of total size 10000. In Table 14 we include the decrease in test accuracy
on the validation set not including the auxiliary set of size 500 , and confirm that the attack has an elementof stealth. For the attacks on CIFAR10, CIFAR100, and FMNIST, the auxiliary dataset is drawn randomly fromall classes and the decrease in test accuracy is also evenly distributed across the classes.
Throughout the Appendix we show the tradeoff between benign accuracy and attack accuracy/OIF in tables andpareto curves in graphs, and leave the task of evaluating risk to practitioners. We note that for the semantic
backdoor task, the attack is not stealthy by definition.

SparseFed: Mitigating Model Poisoning Attacks in Federated Learning with Sparsification

Table 14: Attack accuracy and decrease in test accuracy on CIFAR10, 10000 devices, 200 attackers.
Name

Test acc decrease

Attack acc

Trimmed Mean
BulyanClipping
SparseFed (Ours)

4.78
7.35
7.1
6.61

100
92.6
100
25.6

Table 15: Increasing the size of the auxiliary set can typically result in higher OIF with greatly reduced stealthwhen using the baseline attack against undefended model on CIFAR.

B.6

Aux. set size

Test acc

OIF

0
500
1000
5000

0.90010.7796
0.69810.3107

0
1
2
6.258

Strength of attack

In this section, we perform a thorough evaluation of the attack described in Algorithm 2 for both defended andundefended systems. We show that the attack is more powerful than previously considered, collusion can breakexisting defenses, poisoning attacks can also be used to induce Byzantine failures, evaluate model replacement
attacks, and consider the possibility of an adaptive attack against SparseFed.
B.6.1

The outsized impact of model poisoning attacks on undefended systems

In this section, we evaluate the effectiveness of the baseline model poisoning attack against undefended federated
learning systems. We find that the attack achieves a high OIF across a number of attack scenarios, much higher
than considered by previous work.
In Tables 15 and 16, the baseline attack achieves higher OIF on CIFAR10 than any previous work has been able
to attain. Here, 100 attackers corresponds to a frequency of 1, meaning 1 attacker is selected in every round,and 1 attacker corresponds to a frequency of 0.01, meaning 1 attacker is selected every 100 rounds. Given a
total dataset size of 50000 and a client population of 10000, each attacker "should" only be to flip the labelsof 5 datapoints, because that is the amount of data controlled by any agent in the system. Therefore, when 10
attackers are able to flip the labels of 500 datapoints with high accuracy, they achieve a remarkably high OIF.
This validates a hypothesis: model poisoning attacks are orders of magnitude more powerful than has been shown.
B.6.2

Colluding attackers break the norm clipping defense

We systematically evaluate the `2 norm clipping defense proposed in Sun et al. (Sun et al., 2019) against thestrong attack with the ability for attackers to collude.
Table 16: The attack is effective against an undefended model on CIFAR, across a broad range of attacker
population sizes. Prior work has not achieved high OIF values, ranging from 0.0063 to 0.126 (Bagdasaryan et al.,2020).
Aux. set size

No. attackers

Test acc

OIF

500
500
50
50
5

100
10
10
1
1

0.77960.83320.88420.887
0.8927

1
9.74
1
1.1
1

Panda, Mahloujifar, Bhagoji, Chakraborty, Mittal

Table 17: The attack on the FEMNIST dataset far outperforms prior benchmarks which achieve at most an OIF
of 0.03 (Sun et al., 2019).
Attacker batch size

Test acc

OIF

0
300
600
1200
3000

0.81980.75170.76180.7614
0.7969

0
1.461
1.456
1.405
0.0146CIFAR10: In Fig. 10 we vary the attacker batch size and number of PGD epochs (more details in Appendix
B.8) and obtain an attack which recovers an OIF close to 1. Against a defended system with a moderate stealththreshold of 5%, the attack can achieve an OIF of 0.5 which is significantly higher than any prior work claims(Sun et al., 2019). Therefore, colluding attackers can break the `2 defense.
FEMNIST: We now compare directly with (Sun et al., 2019) and examine the OIF they obtain in their paper.
We keep the percentage of attackers the same and use the same attack and defense (PGD and `2 clipping), andobserve that when we scale up the setting and the size of the auxiliary set, the defense does not scale. In Table 17,
we achieve an OIF > 1. This corresponds to flipping the labels of nearly every datapoint from the considered task,
which indicates that the peak OIF could be higher if considering different tasks. This OIF is about 50× that of(Sun et al., 2019). Crucially, appropriate auxiliary set minibatching is required for success at this scale with low
frequency. If the attacker batch size is too large, the adversary does not make enough progress on the iterations
where it is present and the benign agents quickly revert the model on subsequent non-adversarial iterations.
Scaling up from (Sun et al., 2019): Our goal when doing experiments on FEMNIST is to evaluate a dataset
where each device is only chosen to participate once. Furthermore, we want each iteration to include a somewhat
realistic number of devices (10 − 100) without exceeding the optimal batch size for our residual architecture(500 − 600). Under these constraints, we split each device into 9 − 10 devices so that we can sample 10s of devices
at each iteration and maintain a good batch size. We are able to train a model to convergence in one pass overthe dataset, sampling each device only once, and we believe that this is an important experimental setting forfederated experiments.
Note on the attack: When attempting to modify the behavior of the benign model on a large number ofdatapoints, every additional point of OIF requires giving up more stealth, because every “misflipped” point
reduces stealth but doesn’t increase OIF. Further, increasing the number of PGD epochs, or the attacker batch
size, moves along the OIF-stealth tradeoff. This suggests the following strategy for an attacker with an OIF goalin mind: while the goal is not met, increase the batch size as much as possible while maintaining convergence,then only increase the number of PGD epochs.
B.6.3

Byzantine attacks

Prior work has evaluated model poisoning attacks with the objective of inducing Byzantine failure against thesame cadre of Byzantine-resilient aggregation rules (Fang et al., 2020). Using a better architecture, larger numberof devices, smaller number of attackers, more severe non-i.i.d. partitioning, and smaller participation rate, we
compare the Byzantine failure rate induced by our attack to previous work in Table 2. We modify the attack
to return arbitrary gradients projected onto the perimeter of the `2 norm ball. We find that the scale of ourevaluation reveals a much higher rate of Byzantine failure.
B.6.4

Model replacement attack against SparseFed

We replicate the experimental setting of the model replacement attack of (Bagdasaryan et al., 2020). In particular,
we are attempting to insert a semantic backdoor on the Reddit dataset. The LSTM model architecture, dataset
details, and all other experimental parameters are identical to those in the experiments of (Bagdasaryan et al.,2020). The semantic backdoor that we insert is again drawn from their experiments: "people in athens are rude".
When we compare this to the backdoors inserted for computer vision datasets, it is easy to see that this backdoor
makes up a relatively small portion of the training dataset in comparison. Therefore, the attack itself is muchSparseFed: Mitigating Model Poisoning Attacks in Federated Learning with Sparsification

Figure 10: Pareto frontier of the attack against the `2 defense on CIFAR, for fixed auxiliary dataset size of 500,
norm clipping parameter of 5, 10000 clients and 100 workers with 100 attackers. This attack achieves an OIF 5×
higher than the baseline attack against the `2 defense.
stronger, and this has been observed by (Wang et al., 2020a) as it is an "edge-case" attack rather than the model
poisoning attack we focus on in the main body which is very much a "base case" attack. In Figure 11 we evaluate
the model replacement attack against the baseline `2 clipping defense with a threshold of 3, the minimum valuethat we find does not degrade test accuracy, and SparseFed with the same `2 clipping parameter. In the model
replacement attack, the attacker compromises a small percentage of devices for a short period of time, and the goal
is to enable the backdoor to persist for as long as possible while the benign devices continue training the model.
We defer a detailed study of the staying power of the model replacement attack to future work, and only compare
the speed that the baseline defense and SparseFed erase the backdoor. We do not tune the hyperparameter k forthe new LSTM architecture and use the same value of k as in our computer vision experiments, that does notdegrade convergence. The attack is inserted slightly faster when SparseFed is implemented, which is expected
because we have not optimized the convergence-robustness tradeoff. Even unoptimized, SparseFed reduces theattack accuracy of the backdoored model significantly faster than the baseline defense.
B.6.5

Adaptive attack against SparseFed

We recognize that in order to produce attacks which can overcome strong defenses such as `2 norm clipping
and Bulyan, we need to make use of adaptive attacks which incorporate knowledge of the defense into their
attack strategy. Specifically, to beat `2 clipping the attacker should use PGD, and to beat Bulyan (or other
Byzantine-resilient aggregation rules such as trimmed mean) the attackers should collude. For an adaptive attack
against SparseFed, the attacker would need information about the top-k that will be updated, which is unrealistic
in practice. Nevertheless, here we introduce an adaptive attacker with this information available to them to test
the effectiveness of SparseFed.
Algorithm 14 Adaptive attack against SparseFed
Input: learning rate η, local batch size `, norm clipping parameter L, number of local epochs e
Input: true top-k coordinates to be updated at this iteration K
1: This procedure is used by all attackers in a round to ensure that they upload the same update
2: for number of PGD epochs ei ∈ e doP
3:Compute stochastic gradient git on batch Bi of size `: git = 1` lj=1 ∇M L(Mtei , Dj )cet
4:Update local model M= Mtei − ηgit
i+1
5:
Project accumulated update onto the true top-k coordinatescet
6:
Project accumulated update onto the perimeter of the `2 constraint Mtei+1 = M0t − CLIP (M− M0t )
i+1
7: end for
Output: Mte

The main idea is to use PGD under the coordinate-wise constraint, with the assumption that the attacker has
perfect knowledge of all gradients at the current timestep and is able to project their update onto the top-k

Panda, Mahloujifar, Bhagoji, Chakraborty, Mittal

Figure 11: Model replacement attack on the Reddit dataset. SparseFed quickly returns the model to the benign
optimum.
Table 18: The adaptive attack against SparseFed performs similarly to the base attack.
AttackAttack acc

Test acc

Baseline
Adaptive

3.8
4.4

76.57
77.02

coordinates which will be updated. This attack will only succeed if the attacker has any signal in the true top-k
coordinates; otherwise, the attacker will simply keep updating their local model with noise and no progress will
be made. In Table 18 we evaluate the adaptive attack against SparseFed and find that the adaptive attack only
obtains a negligible improvement over the baseline attack, indicating the strength of the SparseFed defense. The
combination of clipping and small number of possible coordinates to update represent a fundamental barrier forthe attacker.
B.7

Range proofs for SparseFed

We do not go in depth on a proposed implementation of range proofs in a federated learning system for threemain reasons.
First, prior work on defenses do not make any claims about the computational or communication efficiency of
their proposed robust aggregation mechanisms, including the methods that we compare to in this work (Bulyan,
Krum, etc.) This includes the works which initially proposed L2 norm clipping as a defense (Sun et. al. 2019).
Given this, we did not feel that there is a precedent for defense papers which utilize L2 norm clipping and its
variants to propose an efficient range proof that is compatible with existing systems, as this would fall more in
the realm of an applied-cryptography/systems-security paper.
Second, through our industry experience, we know that not all existing deployments make use of secure aggregation
due to its costly overhead and inefficiency at scaling up to larger numbers of clients. Because this is the case, afederated learning system which does not use secure aggregation can implement L2 norm clipping at the server
very efficiently.

SparseFed: Mitigating Model Poisoning Attacks in Federated Learning with Sparsification

Third, to the best of our knowledge, all existing defenses against model poisoning attacks all need some degreeof verification of client’s gradient updates whether it is L2 norm clipping or checking the sign of the gradient.
SparseFed, unlike schemes which require consensus such as Bulyan or sign aggregation, does not require any
additional secure computation beyond L2 norm clipping because there is no need to establish consensus between
clients. In this regard, it is the most suited for deployment in a setting which requires secure aggregation assumingthat a secure multiparty computation for L2 norm clipping has already been deployed.
Despite the above qualifications, we will now address the issue of how to implement range proofs for L2 norm
clipping efficiently, using an informal description of how such a range proof can be achieved. While we do notprovide details here, we believe that the method presented can lead to an actual proof in future work. The parties
in a federated learning system are one server and one or more clients. The server will play the role of the verifier
and the clients will be provers. Because our proposed protocol does not require any coordination between clients,
without loss of generality we can simplify the system to one prover and one verifier. In the first step of the
protocol, the prover generates a commitment to their update vector over the floating point domain. Next, theprover computes the sum of squares via a zkSNARK circuit (zero knowledge succinct non interactive argumentof knowledge). Assuming that a custom SNARK is constructed for this application and the prover is using astandard multi-CPU chip found in the latest smartphones, the proving time would be less than thirty seconds(citation 1). This is minimal compared to the existing overhead in secure aggregation, which can take many
minutes when accounting for multiple rounds of dropped users. If we want to be very conservative about how
much information is leaked, we can treat the sum of squares as a secret committed value and use a bulletproof
to ensure that it falls within the range of (0, L**2) where L is the L2 norm clipping constraint. Bulletproofs
are fairly small and scale logarithmically in the number of commitments; we can validate all 100 L2 norms in
one bulletproof for just 1MB in space, and all of this can be verified in 2ms by the verifier’s hardware. If we
can accept leaking the sum of squares, then we can just make it public and have the verifier check it outside thecircuit. In either case, only provers who pass the verification will have their update vectors aggregated. This
protocol sketch can be implemented without significantly increasing either the communication complexity (whichis already quite large given that we have to at minimum upload gradients of deep networks) or the computation
complexity (again, quite large because the device already has to compute gradients on local data).
B.8

Tuning Attack Parameters

CIFAR attack parameters: We consider various numbers of attackers: [100, 200, 400, 1000] but most experiments are conducted with 100 − 200 attackers which corresponds to having 1 − 2 attackers present in every round.
We consider this to be in line with a real world threat model. Typical federated learning training cycles take placeover the course of a few days, and in order to use data from as many agents as possible, each round must draw
data from many agents. Agents are called on to participate when they fulfill a number of criteria, and an attacker
can forge these criteria in order to control when they are selected. Therefore, it should be straightforward for asmall number of attackers to ensure that they are selected in every round. All auxiliary datapoints are drawn
from the CIFAR validation set. Each point is randomly given a label from one of the 9 classes which it does notbelong to. There are a number of unique attack hyperparameters which we search over. For the boosting factor,
we search over [1,4,6,8,10,20] and find that a boosting factor of 20 works well for our experiments to ensure that
PGD projects the update onto the perimeter of the `2 constraint. However, tuning the boosting factor does notmake an impact whenever the `2 defense is in place with a sufficiently small clipping threshold. We tune theattacker’s local batch size when they are doing PGD. We use values of [N/10, 2N/10, 4N/10, 8N/10] where N is
the size of the auxiliary set. We tune the number of epochs when the attacker is using the PGD attack. We use
values of [1, 3, 5, 7, 9, 11].
B.8.1

Hyperparameter Tuning in Attacks

The hyperparameters we consider are the attacker’s local batch size, and the number of local epochs for
PGD.
In Fig. 12 we consider the impact of changing the attacker batch size across two different auxiliary set sizes: 500
and 5000, against the `2 defense with parameter 5. We find that varying the attacker batch size for the smaller
auxiliary set size reveals a smooth pareto frontier which enables the attacker to double its attack efficacy againstthe `2 for a moderate stealth budget when compared to the baseline attack. Increasing the attacker batch size up
to a certain point increases the efficacy of the attack at the expense of stealth; further increasing the attacker

Panda, Mahloujifar, Bhagoji, Chakraborty, Mittal

Figure 12: Pareto frontier of the attack when varying the batch size against the `2 defense with a parameterof 5, using auxiliary set sizes of 500 and 5000. While tuning the batch size does not achieve an OIF of 1, it
does improve the pareto frontier for the attacker. We find that varying the attacker batch size moves along theOIF-stealth tradeoff; larger backdoors correspond to better OIF, at the expense of stealth.

Figure 13: Pareto frontier of the PGD attack against the `2 defense with a parameter of 5, using auxiliary set
sizes of 500 and 5000. Increasing the number of epochs improves the OIF at the expense of stealth.

batch size does not continue moving along the pareto frontier. This is because, as shown in our initial validationof the `2 defense, attempting to backdoor the entire auxiliary set at every iteration for the smaller auxiliary set
results in a very small OIF.
In Fig. 13 we tune the number of PGD epochs against the `2 defense with parameter 5 at two different auxiliary
set sizes, 500 and 5000. Performing a larger number of gradient descent iterations over the auxiliary set overfits
the gradient significantly, which enables the attacker to insert a backdoor with higher OIF at the expense of aconsiderable degree of stealth.
B.8.2

Additional Results

In Fig. 14 we vary the size of the auxiliary set to observe how successful a more "ambitious" attacker can be.
Generally, increasing the auxiliary set size enables the baseline attack to achieve a higher OIF at the expense of
considerable stealth. These results are summarized in the main body in Table 1.
In Fig. 15, we use the attack to insert a large number of backdoors against an undefended system on the FEMNIST
dataset. As mentioned in the main body, the OIF we obtain is notably ≈ 50× that of the attack benchmarked inprior work. This is because we consider attackers that use a subset of the auxiliary set by minibatching, which

SparseFed: Mitigating Model Poisoning Attacks in Federated Learning with Sparsification

Figure 14: Pareto frontier of the baseline attack against the undefended system on CIFAR10 with 10000 clientsand 100 workers. Annotation is the size of the auxiliary set.

Figure 15: Pareto frontier of the attack against the undefended system on FEMNIST. Annotation is the attacker
batch size, and the size of the auxiliary set. Using a larger auxiliary set with an appropriately tuned batch size
allows for much higher OIF.

enables us to use a much larger overall auxiliary set size in the attack. These results are summarized in Table 17.
In Fig. 16 we show the baseline attack against a system on CIFAR100 with 50000 clients, each client possessing 1
datapoint, 500 workers and 100 attackers. When the system is undefended, the small number of attackers areable to insert an attack with OIF 1. However, enforcing the `2 defense with parameter 5 successfully mitigatesthis attack. In the main body, we show results for the adaptive attack, where the attack reaches 100% accuracy
against the `2 defense.
In Figure 17 we vary the number of attackers against various defenses. We conclude that the defense which has
the absolute highest robustness is: uncompressed SparseFed with k = d, which is equivalent to uncompressed`2 clipping without momentum. However, the test accuracy of this approach is low (44%). Overall, SparseFed
dominates the other defenses significantly, especially for a smaller number of attackers.
In Table 19 we vary the nature of the semantic backdoor when attacking FEMNIST. Instead of targeting the pairof digits 1 and 7, we target 4 and 9. We find that both semantic backdoors perform similarly.

Panda, Mahloujifar, Bhagoji, Chakraborty, Mittal

Figure 16: Baseline attack against CIFAR100 systems, with and without a DP-based `2 defense in place.

Figure 17: Attack against various defenses on CIFAR10 with varying number of attackers.

B.9
B.9.1

FetchSGDThe Case for Sparsification

In Fig. 18 we evaluate our provable defense using two implementations of SparseFed: top-k and FetchSGD
sparsification. As an implementation detail, here we use top-k and the `2 defense in the uncompressed setting, andFetchSGD is in the "uncompressed" setting where the overall communication cost is reduced by a factor of 10. In
all experiments, we update only k = 5e4 gradient parameters at every iteration. We see that for a defended systemwith a moderate stealth threshold of 5%, the attack achieves 0.05 OIF. Thus our SparseFed defense outperforms
the `2 defense by a factor of 10× (recall that the `2 defense incurs an OIF of 0.5 under comparable constraints
in Figure 10). Both implementations mitigate the attack, and using FetchSGD for robustness simultaneously
achieves communication efficiency and enables us to operate in the uncompressed setting where we gain further
robustness.
Table 19: Varying the semantic backdoor does not have a significant impact on the success of the attack against
FEMNIST.
DefenseAttack acc (1/7)

Attack acc (4/9)`2SparseFed

100
1.95

100
6.72

SparseFed: Mitigating Model Poisoning Attacks in Federated Learning with Sparsification

Figure 18: Pareto frontier of SparseFed using topk and FetchSGD with `2 clipping using parameter 5, against
varying hyperparameters of the colluding PGD attack, with a fixed auxiliary dataset of size 500. This is thebest that the strongest available attack can perform against our defense, and we achieve a factor of 5 − 10×
improvement over the `2 defense.

C

Limitations and societal impact

Limitations: The empirical limitation of our work is that we are forced to make imperfect simulations ofcross-device federated settings because we do not have access to real federated datasets at the scale of tens of
thousands of devices. For CIFAR10, CIFAR100, and FMNIST, lacking any natural non-iid partitioning, oursimulation strategy is to simulate each device only drawing samples from the distribution of one class thanmultiple classes, but this may not necessarily be true in the real world. We encourage the federated learning
community to contribute real-world and large-scale datasets to overcome such limitations in the future.
Security considerations: We recognize that our analysis of existing Byzantine resilient defenses reveals thatcolluding attackers can successfully attack systems which may use these defenses today. To mitigate these attacks,
we urge stakeholders in these deployed systems to inspect their vulnerabilities using the same powerful attacker
we use in our work. The field of federated learning has seen a great deal of research interest lately. Federated
learning systems today utilize data from millions of users and serve millions more, so adversarial robustness is ofparamount importance. Prior work in the field of targeted model poisoning attacks has examined the impact that
attacks have in the cross-silo setting, and mostly concluded that In this work, we complement this body of workby demonstrating the outsized impact of model poisoning attacks on systems at scale and showing that existing
defenses can be broken by colluding attackers. We also introduce SparseFed, and prove practical robustness
guarantees for our novel defense. We compare SparseFed to existing defenses, and confirm that it outperforms
these against our strongest available attacks empirically at large scales. Although future work may introduce
attacks which are stronger than we consider, we emphasize that SparseFed will maintain provable robustness
against any attack. We leave investigation of the tradeoffs between other proposed attacks and defenses to future
work.