# BoBa: Boosting Backdoor Detection through Data Distribution Inference in
Federated Learning

Ning Wang1, Shanghao Shi2, Yang Xiao3, Yimin Chen4, Y. Thomas Hou2 and Wenjing
Lou2  1University of South Florida
<EMAIL_ADDRESS>2Virginia Polytechnic Institute and State University
{shanghaos, thou, wjlou}.vt.edu  3University of Kentucky
<EMAIL_ADDRESS>4University of Massachusetts at Lowell
<EMAIL_ADDRESS>
###### Abstract

Federated learning, while being a promising approach for collaborative model
training, is susceptible to poisoning attacks due to its decentralized nature.
Backdoor attacks, in particular, have shown remarkable stealthiness, as they
selectively compromise predictions for inputs containing triggers. Previous
endeavors to detect and mitigate such attacks are based on the Independent and
Identically Distributed (IID) data assumption where benign model updates
exhibit high-level similarity in multiple feature spaces due to IID data.
Thus, outliers are detected as backdoor attacks. Nevertheless, non-IID data
presents substantial challenges in backdoor attack detection, as the data
variety introduces variance among benign models, making outlier detection-
based mechanisms less effective.

We propose a novel distribution-aware anomaly detection mechanism, BoBa, to
address this problem. In order to differentiate outliers arising from data
variety versus backdoor attack, we propose to break down the problem into two
steps: clustering clients utilizing their data distribution followed by a
voting-based detection. Based on the intuition that clustering and subsequent
backdoor detection can drastically benefit from knowing client data
distributions, we propose a novel data distribution inference mechanism. To
improve detection robustness, we introduce an overlapping clustering method,
where each client is associated with multiple clusters, ensuring that the
trustworthiness of a model update is assessed collectively by multiple
clusters rather than a single cluster. Through extensive evaluations, we
demonstrate that BoBa can reduce the attack success rate to lower than 0.001
while maintaining high main task accuracy across various attack strategies and
experimental settings.

##  I Introduction

Federated learning (FL) is gaining popularity for its privacy advantage for
users over traditional centralized machine learning [1, 2, 3], with
applications including Android Gboard for next-word prediction [4] and
WeBank’s credit risk control [5]. In the simplistic form, FL enables a group
of distributed clients to cooperatively train a global model with the help of
a parameter server (PS). Each client receives the global model from the PS and
trains the model with local data. The trained model updates (i.e., parameters
or gradients) are provided back to the PS who then aggregates all clients’
updates and finally updates the global model. Clients’ local data are never
exposed to the PS or an outsider, thus protecting client privacy.

While FL’s distributed nature preserves data privacy of individual clients, it
creates opportunities for malicious clients to _poison_ the global FL model
[6, 7, 8, 9, 10]. In these poisoning attacks, attackers are typically
legitimate clients who train their models using carefully crafted data or
directly manipulate their model updates to influence the global model. Based
on the goals of attackers, poisoning attacks can be classified into
_untargeted attacks_ and _backdoor/targeted attacks_. Untargeted attacks focus
on reducing the overall accuracy of the model. In contrast, backdoor attacks
aim to direct the model to make a desired prediction on targeted inputs while
maintaining a relatively high accuracy on non-targeted inputs. Backdoor
attacks are particularly challenging to detect due to their strategic and
stealthy nature.

Recent advancements in backdoor attacks have increased in stealthiness,
featured by crafting model updates close to benign ones. One line of attacks
directly incorporates a stealthiness metric as a regularizer to their
optimization target to combat existing detection mechanisms. For example, [11,
10] integrate model weight distance into the learning objective function,
allowing them to search for model parameters that not only achieve the desired
targeted predictions but also maintain a low L-2 distance from benign model
updates. This sophisticated approach has rendered many model weight distance-
based detection methods [12, 13, 14] ineffective. Other attack methods add
variance in their attacking strategies to hide their patterns among normal
ones [15, 16, 17]. Xie et al. [15] introduce a distributed pattern and utilize
different patterns interchangeably to influence the model’s behavior. This
diversification of attack patterns increases the detection cost and is
complementary to the previous regularizer-based approach.

Figure 1: Illustration of backdoor update recognition relying on outlier
detection mechanism. (a) IID data scenario. In non-IID data scenario, use (b)
solely outlier detection or (c) cluster based on data distribution and conduct
in-cluster detection.

_The Non-IID Data Challenge._ The non-IID data in real-world FL systems
further complicates the backdoor detection task. Most current mechanisms are
designed for IID data, and their effectiveness heavily relies on the
assumption that a distinction exists between malicious model updates and
benign model updates in a certain feature space [18, 19, 20]. Such solutions
analyze and extract the most distinguishable features, e.g., the angular
distance of gradient updates [19], low-dimensional embeddings of model
parameters [20], model accuracy on generated data [21], etc. As illustrated in
Figure 1, while demonstrating effectiveness in IID data scenarios, the outlier
detection-based solutions are less effective in non-IID scenarios [22, 23]. In
non-IID data scenarios, benign models exhibit large variance. As a result, the
outlier detection-based detection mechanisms while recognizing malicious model
updates will inevitably filter out benign model updates with deviated data
distributions [22, 23, 24].

Therefore, detecting backdoor attacks while preserving benign updates in the
non-IID data scenario has become an immensely challenging task, prompting
extensive research efforts [22, 23, 24, 25, 26]. Awan et al. [23] tailored
their detection mechanism to non-IID data scenarios and assumed that the
angular difference between the gradients of malicious clients should be
smaller than that of any two benign models in the non-IID data scenarios.
However, this assumption may not hold for attack strategies where malicious
clients minimize their similarities. A promising approach to address this
challenge is to cluster clients before detection. Ghosh et al. [25] propose
clustering clients based on their empirical risk value and then using trimmed
mean [13] within each cluster to filter out possible Byzantine nodes.
Meanwhile, Rieger et al. [22] suggest employing an ensemble of clustering
algorithms to effectively cluster model updates with similar training data.
[27] propose a two-level stacked clustering, that selects the most
representative voting vector from all submissions.

The clustering stage is crucial, as any errors made during this phase can
propagate and significantly impact subsequent detection performance. The
clustering performance heavily relies on knowing the data distribution. As
shown in Figure. 1, the false positive is because a novel data distribution is
detected as malicious input. By analyzing current clustering mechanisms for
backdoor detection, we find out the lack of accurate data distribution is a
key reason for low accuracy. Existing works [25, 22] utilize model weights and
empirical loss for clustering, assuming data distribution difference will map
to differences in such metrics. The current landscape lacks sufficiently
accurate and robust client clustering methods, highlighting the urgent need
for accurate and reliable clustering approaches.

_Our Contribution._ In light of the intuition that client clustering and
subsequent backdoor detection can drastically benefit from knowing client data
distributions, we propose a novel data distribution inference mechanism over
model gradients, dubbed DDIG. DDIG is able to extract the relationship between
gradients and true labels and then utilize the gradient/update of clients to
estimate the label distributions. It only requires the knowledge of local
model updates (i.e., the default input information to the server in FL
systems) while achieving high accuracy, which can significantly improve the
differentiation accuracy of true outliers from data distribution deviation.

Based on the data inference module–DDIG, we further introduce BoBa, a Booster
for Backdoor attack detection. Using the data distribution information
estimated by DDIG, BoBa features a novel overlapping clustering method to
cluster clients into multiple groups. We call it a booster as BoBa can be
attached to various traditional backdoor detection mechanisms that are
designed for IID data. In the design of BoBa, we select an overlapping
clustering method [28, 29, 30] instead of the conventional clustering methods
because it can significantly contribute to the system’s robustness. In
overlapping cluster mechanisms, each client is included in multiple clusters,
and its trustworthiness will be assessed by multiple groups rather than by a
single group of peers. We optimize the clustering process with two key
objectives—balanced cluster and uniform cluster inclusion. Balanced cluster
refers to that each cluster has identical or comparable sizes. We set this
goal as unbalanced clustering will lead to a problem where trust estimation
from a larger cohort is of greater value than that from a small cohort.
Uniform cluster inclusion refers to each client participating in the same
number of clusters. We then estimate the trust level of clients within each
cluster and uniformly aggregate the trust estimation results. We then attach
the proposed clustering mechanism to traditional backdoor detection methods
designed for IID to detect backdoor attacks in non-IID data scenarios.

In summary, we make the following contributions:

  * •

We propose BoBa to address the challenging problem of backdoor detection for
FL systems in non-IID data scenarios. To distinguish backdoored models from
benign ones in non-IID data scenarios, we’ve developed a two-step detection
method involving client clustering by data distribution and subsequent
detection of malicious model updates within each cluster.

  * •

We find out the lack of knowledge of client data distribution is a key reason
for the low accuracy of backdoor detection in non-IID scenarios. We propose a
novel data distribution inference model–DDIG, to address this challenge, which
has highly improved the detection performance.

  * •

We propose an overlapping clustering method to improve the robustness of
backdoor attack detection. We model clustering as an optimization problem and
address these challenges by incorporating balanced cluster and uniform cluster
inclusion into the objective function.

  * •

Our evaluation showcases the superiority of BoBa over other baseline methods,
as it consistently achieves a lower attack success rate (ASR) across various
attack strategies and non-IID levels on multiple datasets.

##  II Background

###  II-A Federated Learning

Federated learning can be classified into two types: cross-device FL where
clients are typically mobile devices and the client number can reach up to a
scale of millions; cross-silo FL where clients are organizations or companies
and the client number is usually small (e.g., within a hundred). We target a
cross-silo FL system, in which there are two entities, one parameter server
(PS), and $n$ clients (we define $[n]\coloneqq\\{1,2,...,n\\}$). Each client
manages a local dataset $\mathcal{D}_{i}$ following non-identical
distributions. We use $m$ to represent the total number of data classes.

###  II-B Poisoning Attacks in FL

In the paradigm of FL, since attackers are able to manipulate not only their
data but also their models, a poisoning attack in FL is referred to as a model
poisoning attack (MPA). In MPA [6, 7, 8, 9, 10], attackers provide the
parameter server with carefully manipulated model parameters, with the aim of
gradually degrading the FL model efficacy without being detected. Based on the
goals of attackers, MPA can be categorized into two major classes: untargeted
attacks that aim at increasing the overall prediction error [9] and backdoor
attack/targeted attacks that manipulate the prediction on targeted inputs [10,
31]. We focus on the far more stealthy backdoor attacks in this work.

Recently, backdoor attacks have advanced their performance by enhancing
stealthiness and sophistication. Bhagoji et al. [10] incorporate a penalty on
the distance between the crafted model parameters and the benign model
parameters into its optimization objective in order to evade detection.
Bagdasaryan et al. [31] developed a generic constrain-and-scale technique that
incorporates the evasion of defenses into the attacker’s loss function during
training. Similar techniques have been adopted to bypass detection [15, 32].
These attacks include multiple objectives in their training process [10],
which can be represented by:

$\displaystyle\arg\min_{\delta_{mal}}\quad L(\mathcal{D}_{mal})+\lambda
L(\mathcal{D}_{train})+\rho\lVert\delta_{mal}-\bar{\delta}_{ben}\rVert$ (1)

where $L(\mathcal{D}_{mal})$ is the loss on targeted inputs,
$L(\mathcal{D}_{train})$ is the loss on the clean data, and
$\lVert\delta_{mal}-\bar{\delta}_{ben}\rVert$ is the distance between
malicious model updates and average benign model updates. The third item is
added to achieve stealthiness goals, and it can be replaced by other distance
metrics according to the stealthiness definition.

###  II-C Poisoning Attack Detection

There are two major lines to defend against poisoning attacks. The first line
relies on the model weights/gradient, model representations, or other metrics
to filter outliers. Some defenses directly using the distances between model
weights/gradients, e.g., Krum [12], Median, Trim [13], and Bulyan [14],
EnsembleFL [33]. These methods typically leverage outlier-robust measures to
compute the center of updates in order to filter out Byzantine updates. These
mechanisms provide provable resilience against poisoning attacks to some
extent. Others utilized the angular distance of gradient updates [19] or low-
dimensional embeddings extracted from model parameter updates [20] to detect
poisoned models. [27, 34] explicitly detects and filters abnormal model
updates using model representations. [21] detect malicious model by evaluating
model accuracy on generated data[21].

There are also defenses that mitigate poisoning attacks by suppressing or
perturbing the magnitude of updates instead of detecting these malicious
models. Xie et al. [35] propose to apply clip and smoothing on model
parameters to control the global model smoothness, which yields a sample-wise
robustness certification on backdoors with limited magnitude. FLAME [36] adds
noise to eliminate backdoors based on the concept of differential privacy
[37].

###  II-D Challenges in Non-IID Data Scenarios

In non-IID data scenarios, malicious model detection has been challenging due
to the large variance in benign models. An outlier in a non-IID data scenario
can originate from data distribution divergence, attack strategy, or both. To
improve detection effectiveness, it is critical to filter out the factor of
data distribution. Current intelligence [25, 24, 38, 22] has proposed to use
clustering mechanism to address the non-IID challenge. These work cluster
clients by their model weights/gradients/loss assuming that model
weights/gradients/loss imply data distributions. The robustness and accuracy
of clustering can be improved as there is a gap between clustering model
weights and clustering data distributions. In contrast to the current
clustering methods, we propose to estimate the data distributions based on
their model weights/gradient first and then cluster clients based on the
inferred data distributions. The additional step of data distribution
inference has significantly improved the clustering accuracy and ultimately
improved the detection accuracy. It is of great significance to improve the
efficacy of the client clustering process in backdoor detection and is thus a
main focus of our work.

##  III Problem Setting

Figure 2: Abstract of clients’ data distribution in FL systems.
$\mathcal{A}_{ij}$ is an indicator of client $j$’s data sufficiency in class
$i$: 1 for sufficient data and 0 for non-sufficient data.

###  III-A System Setting

While the meaning of IID is generally clear, data can be non-IID in many ways.
We consider a non-IID setting where clients’ data are different in terms of
both data classes and data amounts, which is mostly discussed in FL[23, 9, 39,
3]. Here, we define that client $j$ has _sufficient_ data for class $i$ if the
number of data records of class $i$ owned by client $j$ is larger than a
predefined threshold $\tau_{i}$. Our goal is to infer the data distribution.
Since it is challenging to employ a simple metric to represent data
distribution as the original data itself does, we introduce a definition of
Abstract Data Distribution.

Abstract Data Distribution. We use $\mathcal{A}_{ij}\in\\{0,1\\}$ as an
indicator for data sufficiency, where 1 indicates sufficient data and $0$
indicates non-sufficiency. A matrix $\mathcal{A}\in\\{0,1\\}^{m\times n}$ is
used to represent the abstract data distribution information of all clients.

Non-IID Data. We consider differences in the data label distribution on each
client, _label distribution skew_ , which is mostly discussed in FL[23, 9, 39,
3]. For example, when clients are tied to particular geo-regions, the
distribution of labels varies across clients — kangaroos are only in Australia
or zoos; a person’s face is only in a few locations worldwide; for mobile
device keyboards, certain emoji are used by one demographic but not others
[3]. The detail of the definition of non-IID degree is discussed in Sec.V-A.

Figure 3: FL system with backdoor attackers. Steps (1)(2)(3) depict the
traditional FL framework while the process inside the blue dashed frame is the
design of BoBa to address backdoor attacks. Details of BoBa is shown in Figure
4.

For each data class, not all clients have sufficient data due to clients’
various functional environments. The number of clients having sufficient data
for class $i\in[m]$ is denoted by $n_{i}$. Further, each client $j\in[n]$ has
a subset of the $m$ classes, and their class numbers are denoted by $m_{j}$ as
shown in Figure 2. The value satisfies $(n_{i}\leq n),\forall i\in[m]$ and
$(m_{j}\leq m),\forall j\in[n]$.

In the FL system, we assume that each client manages a local model, and the
model parameter of client $i$ is denoted by
$\mathbf{\theta}_{i}\in\mathcal{W}\subseteq\mathbb{R}^{d}$, wherein
$\mathcal{W}$ is the parameter space and $d$ is the presumed model
dimensionality. The global model parameter is denoted by
$\Theta\in\mathcal{W}$. We denote the model update from client $i$ as
$\delta_{i}=\mathbf{\theta}_{i}-{\Theta}$. PS acts as the model distributor
and aggregator on the cloud side. The entropy-based loss value for a local
model is $\mathcal{L}(\theta_{i},\mathcal{D}_{i})$. The total loss function
$\mathcal{F}(\Theta)$ is calculated using the loss of the $k$ selected
clients, which can be formulated as
$\mathcal{F}(\Theta)\coloneqq\sum^{k}_{i=1}\mathcal{L}(\theta_{i},\mathcal{D}_{i})$.
We also assume PS has a small auxiliary dataset for validation purposes. The
goal of the FL system is to jointly minimize the loss $\mathcal{F}(\Theta)$ by
optimizing the global model parameters $\Theta$. Symbols are summarized in
Table I in Appendix.

Figure 3 illustrates the FL system workflow. At the system onset, PS
initializes $\Theta$. Then each training iteration works as follows: (1) PS
first selects multiple clients and sends $\Theta$ to them. (2) Each of the
selected clients, initializes $\mathbf{\theta}_{i}\\!=\\!\Theta$ and trains
the model with its local data and provides its model update $\delta_{i}$ to
PS. PS infers an abstract data distribution for each client, followed by
overlapping clustering, feature extraction, and vote-based trust estimation.
(3) PS aggregates local model updates weighted by their trust scores and
updates the global model. The definitions of symbols are presented in TABLE I.

TABLE I: Symbol definition.  Symbol |  Definition
---|---
PS |  parameter server
$n$ |  the number of clients
$m$ |  the number of data classes
$\mathcal{A}_{ij}\in\\{0,1\\}$ |  client $j$’s data sufficiency in class $i$
$\mathcal{A}$ |  matrix representing data sufficiency
$\mathbf{x}_{ij}\in\\{0,1\\}$ |  client $j$’s presence in cluster $i$
$\mathbf{x}$ |  matrix representing the cluster result
$n_{i}$ |  the number of clients having sufficient data for class $i$
$m_{j}$ |  the number of classes of client $j$’s data
$m_{th}$ |  the target number of clusters each client is included in
$n_{th}$ |  the target cluster size
$K_{i}^{t}$ |  the total votes received by client $i$ in iteration $t$
$T_{i}^{t}$ |  the immediate trust score of client $i$ in iteration $t$
$\bar{T}_{i}^{t}$ |  the accumulated trust score of client $i$ in iteration $t$
$\gamma$ |  a discount coefficient in accumulated trust scores.
$\lambda$ |  learning rate of PS
$\theta_{i}$ |  the model parameters of the $i$-th client
$\delta_{i}$ |  the model parameter updates of the $i$-th client
$d$ |  the model parameter dimensionality
$\mathcal{D}$ |  the local dataset of the $i$-th client
$\mathcal{L}(\theta_{i},\mathcal{D}_{i})$ |  loss value for the $i$-th client
$\Theta$ |  the global model parameter
$\mathcal{F}(\Theta)$ |  global loss value

###  III-B Threat Model

In backdoor attacks, attackers’ primary goal is to lead the global model to
classify inputs as the target label while simultaneously maintaining a
relatively high overall accuracy. Attackers have access to a dataset to train
their local model. We assume they can arbitrarily manipulate their local data,
which may involve injecting triggers into input data and altering labels.
Additionally, they can also manipulate their model parameter updates sent to
PS. As legitimate clients, attackers have access white-box access to the
global model but not other client models. We assume PS is trusted and the
defense mechanism against the poisoning attack is deployed at PS.

##  IV Detection Approach: BoBa

###  IV-A Challenges Identification

In non-IID scenarios, discrepancies in model updates can arise from either
inherent variations in data distributions or malicious manipulations.
Determining the root cause of these model anomalies presents a formidable
challenge. To tackle this problem, we propose a two-step solution. The first
step involves clustering clients based on their data distribution, and the
second step focuses on extracting key features and applying a voting-based
detection methodology within each cluster. We have identified five challenges:

  * •

Data Distribution Inference: With only the knowledge of model updates
$\delta_{i}$ provided by different clients, it is challenging for the defender
to estimate the data distribution of different clients and find an accurate
indicator matrix $\mathcal{A}$.

  * •

Clustering Challenge 1: Determining the number of clusters is a complex task,
which is a common issue in most clustering problems. The challenge lies in
finding the right balance between having enough clusters to capture meaningful
variations and avoiding excessive fragmentation that might hinder accurate
detection.

  * •

Clustering Challenge 2: Traditional clustering methods often result in
clusters of varying sizes. However, in the context of backdoor attack
detection, non-identical cluster sizes introduce complications in trust
aggregation. Trust estimation from clusters of different sizes should not be
directly aggregated, as decisions made by larger groups are inherently more
convincing than those made by smaller groups.

  * •

Clustering Challenge 3: A naive overlapping cluster method lacks the necessary
guarantees regarding the number of clusters each member can participate in.
The variance of cluster number a client can participate in leads to a fairness
issue in vote opportunities.

In the subsequent section, we will detail each of these challenges and present
corresponding solutions.

###  IV-B DDIG: Data Distribution Inference from Gradients

Inferring the data distribution from the model updates is a non-trivial task.
In this section, we will introduce our DDIG method that infers data
distribution from gradients under the FedSGD setting. Then, we will extend our
mechanism to a more practical FedAVG setting.

Considering a classification task with the cross-entropy loss, the gradient
produced by client $i$ in its local training process can be expressed as
$\nabla
W_{i}=\frac{1}{|\mathcal{D}_{i}|}\sum_{j}\nabla_{W_{i}}\mathcal{L}(x_{j},y_{j})$,
where $|\mathcal{D}_{i}|$ is the number of data samples in $\mathcal{D}_{i}$
and $x_{j},y_{j}\in\mathcal{D}_{i}$ are sample/label pairs. More specifically,
for each input pair $x_{j},y_{j}$, the gradient of the logits layer
$\mathbf{z}\subseteq\mathbb{R}^{m}$ (pre-softmax layer) is
$\nabla_{\mathbf{z}}\mathcal{L}(x_{j},y_{j})=\mathbf{p_{j}}-\mathbf{y_{j}}$,
where $p_{j}\subseteq\mathbb{R}^{m}$ is a post-softmax probability vector and
$\mathbf{y_{j}}\subseteq\mathbb{R}^{m}$ is a binary label vector with only the
correct label class values 1. As a result,
$\nabla_{\mathbf{z}}\mathcal{L}(x_{j},y_{j})$ will have a negative value only
on the ”correct label class” element because all $p^{v}_{j}\in\mathbf{p_{j}}$
are within $[0,1]$, which can be used to identify the labels precisely.

However, the parameter server has no access to
$\nabla_{\mathbf{z}}\mathcal{L}(x_{j},y_{j})$ but only the gradient of model
parameters $\Theta$. For the last linear layer
$W^{l}\subseteq\mathbb{R}^{m\times r}$, where $r$ is the input feature number
(i.e., the output dimension of the previous layer), the gradient of its
element $W^{l}_{s,t}\in W^{l}$ can be expressed as:

$\displaystyle\nabla
W^{l}_{s,t}=\sum_{x_{j},y_{j}\in\mathcal{D}_{i}}\frac{\partial\mathcal{L}(x_{j},y_{j})}{\partial
z_{s}}\frac{\partial z_{s}}{\partial
W^{l}_{s,t}}=\sum_{j}(p_{j}^{s}-y_{j}^{s})o^{t}_{j}$ (2)

where $o^{t}_{j}\in\mathbf{o_{j}}\subseteq\mathbb{R}^{r}$ are the inputs to
the final layer, and $\mathbf{o_{j}}$ is non-negative when ReLU activation
function is used in the penultimate layer. Therefore, for each $x_{j},y_{j}$,
$(p_{j}^{s}-y_{j}^{s})o^{t}_{j}<0$ still holds if and only if $s$ corresponds
to the correct label class. We then calculate the summation of equation 2 with
respect to $t$ and get the opposite. We denote the indicator as:

$\displaystyle\mathbf{u}=-\sum_{t=1}^{r}\nabla
W^{l}_{s,t}=\sum_{x_{j},y_{j}\in\mathcal{D}_{i}}(y_{j}^{s}-p_{j}^{s})o_{j}$
(3)

where each element $u_{l}\in\mathbf{u}(l\in[m])$ indicating data sufficiency
in class $l$. We can utilize $\mathbf{u}\subseteq\mathbb{R}^{m}$ to infer the
distribution of $\mathcal{D}_{i}$. According to our previous analysis, larger
$u_{l}$ indicates that there are more samples for class $l$ in
$\mathcal{D}_{i}$. For the non-iid scenarios, certain classes having much more
samples in $\mathcal{D}_{i}$ than the others result in peaks in vector
$\mathbf{u}$. Assuming there are $K$ peaks in $\mathbf{u}$ for the gradient
from client $i$, we take the distribution indicator matrix as
$\mathcal{A}_{li}=1$ for the $K$ peaks and $\mathcal{A}_{li}=0$ for the
others. In experiments, we utilize a threshold $\beta$ to define peaks as
$u_{l}>\beta$ where $\beta$ is a hyperparameter $\beta$ that can be tuned in
evaluations.

For the FedAVG setting, each client is assumed to conduct local training for
multiple rounds before sending the parameter updates $\delta_{i}$ rather than
the gradients to the server. Fortunately, when considering the clients using
the SGD optimizer to train the local model for $H$ rounds, the indicator
vector $\mathbf{u}^{h}$ accumulates with respect to training rounds and the
server gets $\sum_{h=1}^{H}\mathbf{u}^{h}$ as the final summarized indicator.
The previous property — the smaller the elements in the summarized indicator,
the larger the number of samples the corresponding classes have still held,
and $\sum_{h=1}^{H}\mathbf{u}^{h}$ can be used to represent the data
distribution.

###  IV-C Client Clustering

####  IV-C1 Number of Clusters

We address challenge 1 by fixing the number of clusters to be equal to the
number of data classes, denoted as $m$. Each cluster is then composed of
clients who possess sufficient data for a specific data class. It is worth
noting that a client may belong to multiple clusters if they have sufficient
data for multiple classes.

####  IV-C2 Uniform Cluster Inclusion

However, an issue arises with this clustering method: different clients may
participate in varying numbers of clusters due to their possession of
different numbers of data classes. Consequently, the subsequent malicious
model detection process becomes unfair, as some clients’ updates may be
evaluated more frequently than others. To rectify this problem and ensure
fairness in the detection process, we propose a solution that enforces each
client’s inclusion in an identical number (i.e., $m_{th}\in\mathbb{N}$) of
clusters. Theoretically, if $m_{th}$ is less than or equal to the minimum
class number among all clients (i.e.,
$m_{th}\leq\mbox{min}(m_{1},...,m_{n})$), we can find a solution where each
client participates in an identical number of clusters. However, if
$m_{th}>\mbox{min}(m_{1},...,m_{n})$, we may obtain a semi-optimized solution
where some clients participate in fewer than $m_{th}$ clusters. In our design,
we deliberately select the threshold $m_{th}$ to be higher than the minimum
class number among clients, effectively screening out the impact of clients
with significantly smaller class numbers.

####  IV-C3 Balanced Cluster

In a naive clustering method, where a cluster is formed with all clients
having sufficient data for a specific class, the resulting cluster sizes tend
to be imbalanced due to the non-IID data characteristic. This imbalance
creates a significant challenge during trust estimation, as trust assessment
in a larger cluster is naturally more convincing than in a smaller cluster.
Consequently, accurately aggregating trust estimations from different clusters
becomes challenging, leading to potential biases in the detection process.

To overcome this challenge and simplify subsequent trust aggregation, we
propose a balanced clustering method. To achieve this, we design a strategy to
select a subset of clients in each data class, rather than including all
clients with sufficient data. The cluster size is approximated by

$n_{th}=\frac{\sum_{i=1}^{n}\mathbbm{1}(m_{i}>m_{th})*m_{th}+\sum_{i=1}^{n}\mathbbm{1}(m_{i}<m_{th})*m_{i}}{m}$
(4)

where $m_{th}$ is the maximum number of clusters each client will be included
in. We set $m_{th}$ as the average number of data categories each client
possesses. A larger value violates ‘uniform cluster inclusion’, i.e., each
client participates in similar number of clusters and ultimately impacts
voting fairness. $\mathbbm{1}(.)$ is the indicator function and equals one
when the condition is true. The value of $n_{th}$ is calculated as the total
participation times divided by the total number of classes. Note that, we set
$n_{th}$ to the greatest integer less than or equal to its original value.

####  IV-C4 Detailed Clustering Method

We use a matrix $\mathbf{x}\in\\{0,1\\}^{m\times n}$ to represent the
clustering result, and $\mathbf{x}_{ij}$ represent client $j$ is in the
cluster $i$. We set $\mathbf{x}_{ij}=1$ if client $j$ is selected to cluster
$i$ and $\mathbf{x}_{ij}=0$ otherwise. Recall that $\mathcal{A}_{ij}=1$ if
client $j$ has sufficient data for class $i$ and 0 otherwise. We can set
$\mathbf{x}_{ij}=0$ or 1 if $\mathcal{A}_{ij}=1$; and we can only keep
$\mathbf{x}_{ij}=0$, otherwise, because we only select client with sufficient
data. The cluster matrix $\mathbf{x}$ is a sparse representation of
$\mathcal{A}$, meaning it contains fewer elements (fewer 1s) and is a subset
of $\mathcal{A}$ while preserving the zero elements.

The selection can be modeled as converting some elements with value one in
matrix $\mathcal{A}$ into zeros and doing no change for zero elements. The
objective is to maximize the summation of $x_{ij}$ while guaranteeing uniform
cluster inclusion and balance cluster. We formulate the problem as:

minimize
$\displaystyle\sum_{i=1}^{m}\sum_{j=1}^{n}(1-\mathbf{x}_{ij})*\mathcal{A}_{ij},$
(5) subject to $\displaystyle\mathbf{x}_{ij}\in\\{0,1\\},$ $\displaystyle
x_{ij}\leq\mathcal{A}_{ij},$
$\displaystyle\sum_{i=1}^{m}\mathbf{x}_{ij}=m_{th}\mbox{, }\forall j,$
$\displaystyle\sum_{j=1}^{n}\mathbf{x}_{ij}=n_{th}\mbox{, }\forall i,$

where the first condition ensures that the variable $x_{ij}$ is binary. The
second condition ensures we only select clients with sufficient data. The
third condition and the fourth condition correspond to the goal of uniform
cluster inclusion and balanced cluster: for all client $j$, it participates in
$m_{th}$ clusters; and for all cluster $i$, the included client number is
$n_{th}$. The optimization is a non-convex optimization problem and by
definition is NP-hard [40]. It does not have any polynomial-time closed-form
solution for finding the optimal point. Therefore, we use a search-based
optimization method to iteratively approximate the best solution step by step.
We propose an efficient algorithm as follows.

Figure 4: BoBa workflow: data distribution inference, client clustering,
feature extraction, and voting-based trust evaluation and aggregation.

Input: Abstract of data distribution $\mathcal{A}\in\\{0,1\\}^{m\times n}$,
$m$ indicates the number of classes, $n$ indicates the number of clients.

Output: cluster matrix $\mathbf{x}\in\\{0,1\\}^{m\times n}$.

1: Set the cluster size $n_{th}=\mbox{min}(n_{1},n_{2},....,n_{m})$;

2: $m_{th}=\mbox{mean}(m_{1},m_{2},...,m_{n})$ # _one client can participate
in $m_{th}$ clusters_.

3: $\mathbf{x}\leftarrow\mathcal{A}$ # Initialization

4: while any$(RowCount)>n_{th}$ or any$(ColCount)>m_{th}$ do

5: for $1\leq i\leq m$ do

6: if $RowCount_{i}>n_{th}$ then

7: $MaxColID\leftarrow\mbox{argmax}(ColCounts)$

8: $\mathbf{x}_{i,MaxColID}\leftarrow 0$

9: end if

10: end for

11: for $1\leq j\leq n$ do

12: if $ColCount_{j}>m_{th}$ then

13: $MaxRowID\leftarrow\mbox{argmax}(RowCounts)$

14: $\mathbf{x}_{MaxRowID,j}\leftarrow 0$

15: end if

16: end for

17: end while

Algorithm 1 A Greedy Algorithm for Clustering

####  IV-C5 An Efficient Algorithm

Intuitively, our approach to achieving balanced clusters begins with
initializing the cluster matrix $\mathbf{x}$ as $\mathcal{A}$, as described in
Algorithm 1 in the Appendix. In the initialization step, each cluster $i$
contains all clients with sufficient data for class $i$. The goal is to create
balanced clusters by removing zero or more clients from each cluster. We
proceed by iterating over each cluster (i.e., each row) in the matrix
$\mathcal{A}$. If a cluster contains more clients than the specified threshold
$n_{th}$, we employ a removal process to balance the cluster. The removal
process involves sorting the clients in the cluster based on their data class
numbers in descending order (Lines 5 to 10). We then remove the client with
the highest data class number by changing the corresponding 1 to 0 in the
initialized cluster matrix $\mathbf{x}$. Following this, we repeat a similar
procedure by iterating over each column in $\mathbf{x}$ (Lines 11 to 16). This
process of iterating and applying removal actions continues until the
condition $\text{any}(RowCount)>n_{th}$ or $\text{any}(ColCount)>m_{th}$ is no
longer satisfied.

The efficient clustering algorithm is presented in Algorithm 1. It is
important to note that the greedy algorithm may result in a sub-optimal
solution, meaning that the result may not perfectly satisfy balanced clusters
and uniform cluster inclusion. However, in the context of backdoor attack
detection, a sub-optimal solution is sufficient for achieving effective and
reliable results. Thus, the proposed greedy algorithm strikes a practical
balance between computational efficiency and detection accuracy, making it a
valuable component of our overall approach.

###  IV-D Detection in IID Data Scenarios

As a backdoor detection performance booster, the proposed distribution-
inference-based clustering method (depicted in Sec. IV-B and IV-C) can be
attached to most traditional detection methods designed for IID scenarios. By
incorporating BoBa, these methods can be upgraded to deal with non-IID data
scenarios. Traditional backdoor attack detection mechanisms in IID scenarios
have two major lines— model weights/gradient similarity [19, 20, 12, 13, 14]
and latent representation similarities [27, 34]. The two lines demonstrated
their effectiveness in different scenarios. We summarized the two lines and
attached them to our distribution-inference-based clustering mechanism to
evaluate the effectiveness of BoBa.

These two lines are particularly designed to deal with existing backdoor
attacks. In backdoor attacks, a malicious client typically has two main goals
that can be contradictory: 1) Directing the model to a target direction, and
2) staying stealthy. To redirect the model’s predictions to a target label
that differs from the true label, an attacker may provide a model update with
a gradient that significantly diverges from the benign gradient, thereby
maximizing the impact of the poisoning attack. In such cases, the cosine
similarity between the gradient of the backdoor model update and the benign
model update can be large. On the other hand, in a more stealthy attack, a
malicious client tries to evade detection by PS by maintaining a relatively
low gradient divergence. In these stealthy attacks, the similarity of latent-
space representations becomes an alternative metric to assess the
maliciousness of the model update. To address both aggressive and stealthy
attacks, we will evaluate the two metrics following our clustering mechanism.
The detail of the two metrics is listed below:

Gradient similarity. The cosine similarity between any two clients’
accumulated gradient (i.e., model update) $\delta_{i}$ and $\delta_{j}$ is
evaluated by:

$S_{ij}^{1}=\frac{\delta_{i}^{T}\delta_{j}}{\lVert\delta_{i}\rVert\lVert\delta_{j}\rVert}$
(6)

Latent Representation similarity. We compute the latent space representations
$z_{i}$ of each client $i$ using the auxiliary dataset at PS. This involves
creating client $i$’s local model $\theta_{i}=\delta_{i}+\Theta$. We pick one
data class from the auxiliary dataset to see the model’s average
representation. We obtain the data representation $z_{i}$ by capturing the
second last fully connected layer of client $i$’s local model. We compute the
cosine similarity between any two representations $z_{i}$ and $z_{j}$ can be
expressed by:

$S_{ij}^{2}=\frac{z_{i}^{T}z_{j}}{\lVert z_{i}\rVert\lVert z_{j}\rVert}.$ (7)

###  IV-E Trust Scores and Model Aggregation

We build a voting-based trust establishment for each client rather than
relying solely on the explicit values of the two similarity scores. The reason
for this choice is to mitigate the risk of collusion scenarios, where
attackers may report remarkably similar gradients to achieve artificially high
similarity scores. Such high scores could dominate the average similarity
scores and compromise trust estimation. By utilizing vote counts instead, we
create a more robust mechanism that is less susceptible to collusion attacks.
In BoBa, PS calculates each client’s $\lfloor n_{th}/2\rfloor$ nearest
neighbor based on the gradient similarity and representation similarity,
respectively, where $\lfloor x\rfloor$ denotes the floor function that returns
the greatest integer less than or equal $x$. For FL iteration $t$, we set a
counter for each client and denote the counter for client $i$ as $K_{i}^{t}$.
If a client is selected as the nearest neighbor by others, its corresponding
counter will increase by one. During the trust establishment, PS performs the
voting using the representation similarities, the gradient/weight
similarities, or both. We use weight similarity as the default if it is not
specified.

In our design, voting is performed by the central server on behalf of each
client within each of the $m$ clusters. The votes cannot be manipulated by any
client as it is done by PS. PS iterates over all $m$ clusters, updating the
vote counts for each client. After processing all clusters, PS aggregates the
votes to obtain a final vote count, denoted as $K_{i}^{t}$, for each client
$i$ at iteration $t$. The immediate trust score for client $i$ is estimated by
the softmax function:

$T_{i}^{t}=\frac{exp(K_{i}^{t})}{\sum_{i=1}^{n}exp(K_{i}^{t})}.$ (8)

This softmax function guarantees that the summation of all clients’ trust
scores equals one. To incorporate the historical trust level of each client,
we introduce an accumulated trust mechanism that considers both the current
trust $T_{i}^{t}$ and the trust from previous rounds
$T_{i}^{1},T_{i}^{2},...,T_{i}^{t-1}$. The accumulated trust for client $i$ is
denoted as $\bar{T_{i}^{t}}$ and can be represented as follow:

$\displaystyle\bar{T_{i}^{t}}=\sum_{i=0}^{t}\gamma^{t-i}T_{i}^{t}$ (9)

where $\gamma$ is a hyperparameter that controls the weightage given to
previous trust values. A higher value of $\gamma$ places more emphasis on
older trust scores, while a lower value gives greater importance to the
current trust score. In our work, it is set as $\gamma=0.1$. To maintain the
scale of trust scores, we perform normalization on the accumulated trust
scores. The accumulated trust scores are used as coefficients in calculating
weighted averages during the aggregation process.

Furthermore, based on the observation that the impact of an attacker can be
more long-lasting if they are consistently selected in consecutive learning
rounds, we propose a strategy to mitigate it. In each learning round $t$, PS
discards the updates from clients whose immediate trust score in the previous
round $t-1$ is lower than the median trust score among all clients in that
round. By incorporating both the normalized accumulated trust scores and the
mitigation strategy for consecutive attacks, our proposed method reduces the
potential impact of consecutive attacks and enhances the overall security and
robustness of FL systems.

###  IV-F Summarized Workflow

In this section, we summarize the workflow of BoBa by describing the process
at both the client and server sides.

On the client side, following the traditional FL process, the client needs to
send their model parameter updates to PS. The workflow at a local client is as
follows: Clients receive global model $\Theta$ from PS and use it to
initialize their local model. Each client continues to train the global model
using their local data and uploads model update $\delta_{i}$ to PS.

We depict the workflow on the server side in Figure 4. There are four major
modules:

  * •

Client data distribution inference is designed to facilitate accurate client
clustering. PS first performs DDIG to infer the data distributions of each
client.

  * •

Client clustering module clusters the clients to $m$ overlapped clusters.

  * •

Feature extraction is conducted in each cluster. Model parameters and latent
space representations are used to estimate the similarities among clients
within each cluster.

  * •

Voting-based trust estimation module first calculates each client’s votes in
every cluster in which they participate. The final trust is calculated
according to Eq. 8 using combined voting counts.

PS aggregated all the received model parameters weighted by their accumulated
trust score, which can be represented as:

$\Theta=\Theta-\lambda\sum_{i=1}^{n}\bar{T_{i}}\frac{\delta_{i}}{\lVert\delta_{i}\rVert}$
(10)

where $\lambda$ represents the learning rate, and
$\frac{\delta_{i}}{\lVert\delta_{i}\rVert}$ denotes the normalized gradient of
client $i$. The normalization of the gradient is employed as a preventive
measure against attackers attempting to amplify their impact by scaling up
their gradients.

##  V Evaluations

We implement BoBa on the TensorFlow platform and run the experiments on a
server equipped with an Intel Core i7-8700K CPU 3.70GHz$\times$12, a GeForce
RTX 2080 Ti GPU, and Ubuntu 18.04.3 LTS. We implement four backdoor attacks,
including Alternate [10], Basic [41], and DBA [15] and Sybil [19]. We
implement six defense baselines, including FedAVG [2], Krum [12], Median, Trim
[13], FLTrust [42], and CONTRA [23].

###  V-A Experimental Setting

In the studied FL system, we set the client number as $n=50$ and the per-round
selection ratio as 0.2, i.e., 10 clients will be selected in each FL round. To
simulate the attackers, we set 5 out of the 50 clients as malicious. In order
to obtain a more realistic attacking scenario, we randomly select clients
during the FL process, and malicious clients may not consistently show. Each
client manages a local model and trains the local model using an Adam
optimizer with a learning rate of 0.001. A client trains its local model for
five epochs before submitting the model updates. The number of total FL
iterations is $T=60$. We run each experiment _three_ times and show the
average performance.

We evaluate BoBa on three datasets including the fMNIST dataset [43], CIFAR-10
dataset [44], and MNIST dataset [45]. The model architectures for the three
datasets are a plain CNN, VGGNet [46]), and AlxeNet [47], respectively. We
synthetically generated the non-IID dataset following the methodology in [2]
to simulate the non-IID data scenario. In the data generation, a value from 0
to 1 is used to indicate the non-IID degree, where 0 indicates IID data and 1
indicates fully non-IID data. The default non-IID degree if not otherwise
specified is 0.4. Suppose we use $p$ to indicate the non-IID degree, and the
total number of data records is $N$. In experiments, we first assign the
$(1-p)$ portion of the dataset uniformly to all clients (i.e., IID data). In
the second step, we sort the remaining $p*N$ data by digit label, divide it
into 1000 shards, and assign each of the 50 clients 20 shards. This is a
pathological non-IID partition of the data, as clients will have examples from
1 to 10 classes in this step, letting us explore the degree.

For the backdoor data, we assume malicious clients possess clean data records
and poisoned data records. Each client has a dataset of 1,200 (1,000) local
training data records in MNIST and fMNIST datasets (CIFAR dataset). For each
malicious client, they have an additional 500 data points with a trigger. We
vary the actual number of backdoor data used for local training to maintain a
trade-off between stealthy and attack impact. The details of the datasets are
shown in the Appendix B. We consider different malicious clients possessing
non-IID benign data and the same set of poisoned data. The same set of
poisoned data ensures they can achieve the same adversarial goal, while the
non-IID benign data invite differences into their models, making them more
stealthy. We assume the PS has an auxiliary dataset containing $60$ clean data
points from three classes (i.e., $20$ from each class).

###  V-B Evaluation Metrics

We primarily use two metrics: main task accuracy and attack success rate
(ASR). The main task accuracy is evaluated on the whole test dataset just as
an attack-free scenario. The attack success rate refers to the percentage of
samples with trigger patterns that are successfully classified as the target
label[48]. It is also called backdoor accuracy [31, 49]. To evaluate the ASR,
we randomly select $500$ data records from the test set and attach a backdoor
pattern to them. We refer to the $500$ test data records as base data. We
include 500 records for evaluation as the evaluation is time-consuming and
ASR/Acc has little change if the test set is over 200 records. In order to
accurately assess the attack success rate, we first evaluate the global
model’s prediction on the base dataset. Only if the global model correctly
classifies a base data record, we will assess the attack success situation on
the corresponding poisoned data. The backdoor attack success on a data record
if and only if the prediction on the manipulated data equals the target label.
ASR is calculated as the ratio of successful data records to the total number
of samples with trigger patterns. The computation overhead is discussed in the
Appendix V-I.

Figure 5: The illustration of our clustering method.

###  V-C Backdoor Attacks and Defense Baselines

We evaluated BoBa on four representative backdoor attacks including Basic
[41], Alternate [10], DBA [15], and Sybil [19]. We present them as follows:

Basic[41] is the plain backdoor attack that injects crafted data into the
training dataset and obtains the locally trained model to PS. There is no
explicit manipulation of the trained model. Specifically, we follow the papers
to inject a pattern into the target dataset. Attackers control their local
learning rate and steps to remain stealthy.

Alternate[10] incorporates two additional components into the learning
objectives—improve the overall accuracy and decrease the distance between the
crafted model and benign models. In order to achieve the goal of injecting a
backdoor and remaining stealthy, it trains alternatively on the objective
functions. Attackers utilize a boost coefficient to scale the local gradient
thus increasing the impact of the backdoor. Note that the boosting coefficient
is fine-tuned to maximize its impact and remain undetected.

DBA[15] decomposes a global trigger pattern into separate local patterns and
embeds them into the training set of different adversarial parties
respectively. Compared to standard centralized backdoors, we show that DBA is
substantially more persistent and stealthy against FL. All attackers only use
parts of the global trigger to poison their local models, while the ultimate
adversarial goal is still the same as a centralized attack—using the global
trigger to attack the shared model.

Sybil [19] attacks refer to attacks in which multiple attackers share the same
model parameters to increase their impacts. The Sybil attack evaluated in this
paper is based on Alternate [10] attack. In each learning rate, if there are
one or more malicious clients is selected. The first selected malicious client
launches Alternate [10] attack and other malicious clients make a copy of the
crafted model parameters.

The variety of baseline attacks allows us to evaluate a detection method’s
comprehensive resilience to poisoning attacks. Among the defense baselines, we
have Krum [12], Median, and Trim [13], which are statistical-based methods.
These baselines utilize outlier-robust measures such as median and mean to
filter out backdoor updates. Additionally, we include FLTrust [42] and CONTRA
[23], which are trust-based approaches. For further details on the baseline
defense methods, please refer to the introduction in the Appendix section.

###  V-D Evaluation Goals

Our primary evaluation goals goal is to demonstrate the effectiveness of the
proposed distribution-aware backdoor attack detection mechanism in non-IID
data scenarios. To achieve this goal, we present comparisons between baseline
defenses and BoBa. We also analyze the significance of our distribution-
inference-based clustering by attaching it to different defenses designed for
IID data. In addition, we demonstrate the applicability and effectiveness of
BoBa in various scenarios, e.g., the attack-free and adaptive attack
scenarios. We aim to analyze the robustness of BoBa when facing up various
auxiliary data amounts and distributions, non-IID data levels, and malicious
client ratios.

###  V-E Illustration of Data Distribution Inference and Clustering

For evaluation purposes, we set $\mathcal{A}_{il}=1$ if the number of data
samples of class $l$ is larger than the number of data samples per class of
client $i$ ($\mathcal{A}_{il}=0$ otherwise). A value of one in
$\mathcal{A}_{il}=1$ here indicates a dominating class without referring to
the absolute number of data samples. We set this distribution as the ground
truth. And we further utilize DDIG to obtain an inference
$\mathcal{A}^{\prime}$. We estimate the data distribution inference accuracy
as the percentage of matched elements in the two matrices $\mathcal{A}$ and
$\mathcal{A}^{\prime}$. In Figure LABEL:fig:_label_inference_performance, we
demonstrate the data distribution inference results on different datasets
under the FedAVG setting. We assume each client trains the local model for 5
rounds before it sends the model updates to the server and chooses the number
sufficiency threshold as 200. We plot the average bit inferring accuracy for
all elements in the indicator matrix $\mathcal{A}$ with respect to different
non-iid degrees ($p$). From the results, we find that our data distribution
mechanism achieves the best 1.0 accuracy on all three datasets only except for
$p=0.2$, for which the accuracy is 0.89, 0.94, and 0.96 respectively for three
datasets. We consider this because data samples in a low non-iid degree
dataset nearly exhibit uniform distribution with respect to different classes
and it becomes harder to distinguish number-sufficient classes from the
others. Nevertheless, the slightly lower accuracy in low non-iid degree won’t
influence the subsequent detection performance as such data distribution
resembles an IID scenario. Note that the following evaluations are all based
on perfect $\mathcal{A}$ as the inference accuracy is 1.0 in the default non-
iid degree (i.e., 0.4).

TABLE II: Backdoor attack success rate under defenses.  Dataset | Attack | FedAvg[2] | Krum[12] | Median[13] | Trim[13] | FLTrust[42] | CONTRA[23] | BoBa
---|---|---|---|---|---|---|---|---
MNIST | Alternate[10] | 0.122 | 0.645 | 0.047 | 0.103 | 0.201 | 0.363 | 0
Basic [41] | 0.494 | 0 | 0.023 | 0.452 | 0.205 | 0.343 | 0
DBA[15] | 0.02 | 0.135 | 0.002 | 0.018 | 0.021 | 0.170 | 0
Sybil[19] | 0.117 | 0.666 | 0.048 | 0.125 | 0.232 | 0.107 | 0
fMNIST | Alternate[10] | 0.667 | 0.953 | 0.786 | 0.714 | 0.915 | 0.154 | 0.001
Basic [41] | 0.828 | 0.680 | 0.811 | 0.804 | 0.836 | 0.566 | 0
DBA[15] | 0.452 | 0.071 | 0.428 | 0.539 | 0.507 | 0.342 | 0
Sybil[19] | 0.678 | 0.971 | 0.813 | 0.736 | 0.448 | 0.039 | 0.001
CIFAR-10 | Alternate[10] | 0.692 | 0.994 | 0.597 | 0.734 | 0.593 | 0.249 | 0.002
Basic [41] | 0.960 | 1.00 | 0.951 | 0.802 | 0.309 | 0.379 | 0.003
DBA[15] | 0.178 | 0.406 | 0.200 | 0.260 | 0.216 | 0.354 | 0.009
Sybil[19] | 0.627 | 0.880 | 0.531 | 0.655 | 0.574 | 0.560 | 0.004
aCONTRA and BoBa are designed for Non-IID scenarios.
TABLE III: Main task accuracy.  Dataset | Attack | FedAvg[2] | Krum[12] | Median[13] | Trim[13] | FLTrust[42] | CONTRA[23] | BoBa
---|---|---|---|---|---|---|---|---
MNIST | Alternate[10] | 0.991 | 0.991 | 0.990 | 0.991 | 0.991 | 0.989 | 0.991
Basic [41] | 0.991 | 0.991 | 0.990 | 0.991 | 0.989 | 0.988 | 0.991
DBA[15] | 0.992 | 0.989 | 0.992 | 0.992 | 0.991 | 0.866 | 0.990
Sybil[19] | 0.991 | 0.990 | 0.991 | 0.991 | 0.991 | 0.987 | 0.991
fMNIST | Alternate[10] | 0.908 | 0.895 | 0.904 | 0.906 | 0.897 | 0.886 | 0.897
Basic [41] | 0.903 | 0.610 | 0.893 | 0.903 | 0.887 | 0.612 | 0.903
DBA[15] | 0.894 | 0.881 | 0.897 | 0.895 | 0.876 | 0.613 | 0.900
Sybil[19] | 0.907 | 0.895 | 0.904 | 0.906 | 0.906 | 0.889 | 0.903
CIFAR-10 | Alternate[10] | 0.687 | 0.653 | 0.681 | 0.681 | 0.705 | 0.676 | 0.709
Basic [41] | 0.683 | 0.662 | 0.675 | 0.679 | 0.495 | 0.586 | 0.716
DBA[15] | 0.677 | 0.638 | 0.668 | 0.667 | 0.675 | 0.466 | 0.703
Sybil[19] | 0.693 | 0.668 | 0.679 | 0.685 | 0.681 | 0.592 | 0.717

Figure 5 provides a visual representation of the data distributions and
clustering results. In the left subfigure, different colors are utilized to
indicate distinct data classes, and the height of each color bar represents
the corresponding data amount. As observed, clients have varying numbers of
data classes and different data amounts per class. As outlined in the system
model described in Section II-A, we process the data distribution into a 2-D
binary matrix denoted as $\mathcal{A}$. To visualize this information, we
present the binary matrix result in the middle subfigure, where the green grid
signifies that client $j$ possesses sufficient data for class $i$. Owing to
space constraints, we present the data distribution abstract for a subset of
12 clients out of the total 50. Building upon this binary matrix, BoBa
performs the clustering algorithm, and the resulting clusters are depicted in
the right subfigure. In the clustering results, we employ the blue grid to
indicate the inclusion of a client within a specific cluster. Clusters are
formed by marking all clients with a blue grid in each row, resulting in a
total of ten clusters, as illustrated.

Figure 5 presents two notable aspects of our clustering approach: _clients per
cluster_ and _client participate times_. _Clients per cluster_ give the
evenness of cluster sizes. Among the 10 clusters, 8 clusters consist of 6
clients each, one cluster comprises 5 clients, and another includes 7 clients.
This distribution results in comparable cluster sizes, which is advantageous
as it ensures that votes from these clusters carry similar significance.
Consequently, the complexity of the subsequent vote aggregation among clusters
is considerably reduced. Secondly, upon analyzing each column, we observe that
all clients participate in exactly 5 clusters, indicating that they possess an
equal number of votes for other clients. This aspect enhances the fairness of
the voting process. It is important to note that Figure 5 displays the real
output of our clustering algorithm, and the visuals are provided to facilitate
better comprehension.

###  V-F Overall Performance under Non-IID Data

We evaluated BoBa in the non-IID data scenario using three datasets and show
both ASR and model accuracy in TABLE II and TABLE III, respectively. In the
two tables, we show the performance of BoBa and six baselines under four
backdoor attacks. As shown in TABLE II, BoBa outperforms other baselines by
achieving the lowest ASR under 12 evaluation settings (the combinations of
four attacks and three datasets). FedAVG has no detection procedure during the
learning process and simply calculates the average of all received model
updates. From this set of experiments, we learn that the pure average may
outperform some defensive baselines under the non-IID data scenario. Another
interesting finding is that ‘Basic’ achieves better performance than other
baseline attacks. The reason is that it has a single goal while other attacks
have additional processes for stealthiness. Malicious updates are naturally
stealthy as benign data is out-of-distribution in non-IID scenarios.
Therefore, ‘Basic’ can evade detection and maintain good performance even when
the defense is included. TABLE III presents the main task accuracy of the
final global model. We can see that BoBa achieves higher or comparable
accuracy when compared with other baselines. In summary, BoBa not only reduces
the ASR but also helps maintain a better model accuracy, indicating its
superiority in securing FL systems in non-IID scenarios.

To further illustrate the detection performance, we present the trust score
distributions of malicious clients in Figure LABEL:fig:mal-trust. We estimate
the trust scores in an FL system that selects five clients in each iteration.
We scale the trust scores for all selected clients to make sure they sum up to
one. In this setting, if no discrimination is included, the average trust
score for each client should be 0.2. As we can see from Figure LABEL:fig:mal-
trust, BoBa achieves the lowest average trust scores compared with the other
two trust-based defenses—FLTrust and CONTRA, indicating that BoBa has a better
detection performance against backdoor attacks.

We study the significance of BoBa by incorporating it into existing defenses.
The representative existing defenses include three types: ’W’ representing
poisoning detection utilizing model Weights similarities, ’R’ representing
poisoning detection utilizing Representation similarities, and ’R+W’
representing poisoning detection integrating the two metrics. From Figure
LABEL:fig:ablation, if we focus on the original strategies, we can see ’R+W’
achieves the highest detection rate (lowest ASR) while it yields the lowest
accuracy. ’R’ achieves the highest accuracy but the worst detection rate
(i.e., highest ASR). ’W’ get a better balance between accuracy and detection
rate. From the analysis, we confirm that there is always a trade-off between
accuracy and detection rate. When we compare original strategies and
strategies with BoBa incorporated, we can see that the attack success rate
will be reduced significantly especially when for ’R’. For ’W’ and ’R+W’, we
can see ASR are reduced and accuracy are increased when BoBa is incorporated.
For ’R’, accuracy will be degraded while ASR will be reduced significantly.
The results demonstrate that incorporating BoBa to a traditional defense can
significantly improve the overall performance.

###  V-G Robustness against Various Parameter Settings

In this section, we present the performance of BoBa in the attack-free
scenario and when it faces various auxiliary data amounts/distributions,
various non-IID data levels, and various malicious client ratios.

In the real world, attacks may not happen all the time. It is critical to have
an FL system that works well in both attack and attack-free scenarios. The
specific goal can be that the FL system should not bring no or relatively
small degradation in the model accuracy when no attack shows. We evaluated
BoBa in the attack-free scenario and present the model accuracy in TABLE IV.
FedAVG assigns an identical weight to each model update. We can see that BoBa
achieves comparable accuracy with the FedAVG baseline, which confirms that
BoBa can work well in attack-free scenarios.

TABLE IV: Model accuracy (%) in attack-free scenario.  Dataset | FedAvg | Krum | Median | Trim | FLTrust | CONTRA | BoBa
---|---|---|---|---|---|---|---
MNIST | 0.992 | 0.991 | 0.992 | 0.992 | 0.992 | 0.990 | 0.991
fMNIST | 0.911 | 0.901 | 0.909 | 0.910 | 0.905 | 0.890 | 0.902
CIFAR-10 | 0.711 | 0.691 | 0.709 | 0.702 | 0.721 | 0.722 | 0.720

As shown in Figure LABEL:fig:aux-class, we increase the data class number from
2 to 8 while maintaining 20 data records in each class. We can see the ASR
stays similar from 2 to 6. The ASR has a slight drop when 8 classes of data
are available. This result indicates that BoBa does not require collecting all
data classes, and the auxiliary data distribution can be distribution skewed.
In Figure LABEL:fig:aux-amount we maintain 3 data classes and change the data
amount per class from 0 to 20. Note that when there are 0 auxiliary data, we
do not apply latent-representation-based trust score estimation but solely
utilize the model parameters for trust score estimation. We can see that BoBa
achieves a low ASR even if no auxiliary data is available, which is also
demonstrated in the ablation study. We can see that when auxiliary data is
more than 20, BoBa can achieve additional gain.

We evaluate the performance of BoBa under various malicious client fractions.
As shown in Figure LABEL:fig:mal-fraction, the system maintains a high
detection performance when the malicious client number is less than 30%. The
observation aligns well with the theoretical analysis in [50]. Shi et al. has
demonstrated that the error of aggregation from multiple sources can be
bounded only if the Byzantine/malicious nodes are less than one-third of the
population.

Figure 10: Performance of BoBa under adaptive attack. Left: the times each
malicious client is selected (there are 5 malicious clients in the FL system);
Middle: Trust scores of malicious clients; Right: Attack success rate.

The non-IID level is another important factor for detection performance.
Intuitively, detection is harder when the non-IID level increases. However, in
our evaluation shown in Figure LABEL:fig:iid-level, we don’t see an increasing
trend of the ASR. Instead, we see the ASR fluctuates and remains at a low
level with the change of non-IID level, indicating that BoBa is robust to the
non-IID level. We can see the main task accuracy drops with the non-IID level,
which is a common situation even in attack-free scenarios. Here the non-IID
level equal to 0 implies an IID data setting. We can see that BoBa also
achieves a low ASR in the IID data setting. The IID scenario is just a special
case of non-IID scenarios. BoBa is effective in both non-IID and IID data
scenarios.

###  V-H Performance under Adaptive Attack

Adaptive attack refers to an attack that is designed to defeat the proposed
defense based on the knowledge of the defense strategy. We initialize two
adaptive attacks in this work: one targets the similarity-based detection
method, and the other targets the clustering module. We refer to the two
adaptive attacks as Sybil[19] and adaptive-attack.

As shown in the attack introduction section (i.e., Sec. V-C), in Sybil
attacks, multiple attackers share the same model parameters to increase their
similarity and thus their attack impact. It can be regarded as an adaptive
attack against the similarity-based detection method (we use cosine similarity
of model weights and latent representation for malicious model detection). The
performance of BoBa against Sybil[19] is shown in TABLE II. We can see BoBa
maintains a low ASR under the Sybil attack. The observation implies that
attackers can not break BoBa by reporting the same model updates. The
underlying reason for the failure is the voting-based trust estimation. An
increased similarity value does not translate to an increased vote count.

###  V-I Computation Overhead

In another version of an adaptive attack, we assume the attacker can
successfully mislead the central server to believe that they have enough data
for all the classes. It is possible if the attacker can collect enough data.
The goal is to increase their chance of being selected. We call it adaptive-
attack. In Figure 10, we show the performance of BoBa against Adaptive-attack
attack. We present the number of times of malicious client is selected
throughout the learning rounds. Here, ‘selected’ means it is picked as a
participant. From Figure 10, we can see that compared to the base attack
(i.e., Alternate), the attacker cannot increase either the times of being
selected or its trust scores. The ASR of the Adaptive attack also has no
significant increase. The trust score for all clients stays at 0. Therefore,
the slight increase in ASR is not due to malicious update injection but model
randomness. We can explain the reason for the failure based on the
illustrations in Figure 5. In the third subfigure, among the 12 clients, each
client participates in 5 clusters though some clients have more data classes
than others. So whatever data distributions the attacker reports, our cluster
method will maintain that each client only participates in the same or
comparable number of clusters. In other words, the false data distribution
reporting won’t increase their votes. We acknowledge there are many more other
adaptive attack strategies. It is not possible to explore the efficiency
against all of them. The adaptive attack itself can be a future research
direction.

Compared to traditional FL systems, the server has two additional tasks in
BoBa—client clustering and trust score estimation. We discuss the time
complexity of clustering on client number $n$ assuming other settings are
fixed. The time complexity of the proposed greedy algorithm for clustering is
$O(\sqrt{n})$. The time complexity of pairwise distance evaluation is
$O(n^{2})$. The computation time on our server for the two tasks is shown in
Figure LABEL:fig:compution_time. In large-scale FL systems where the number of
participants scales to thousands, the computation of trust estimations with
$O(n^{2})$ complexity can become a significant bottleneck. This problem can be
solved by simply splitting the clients into $p$ random subgroups. Each group
independently performs trust estimations among its members. By distributing
the trust evaluation process across multiple groups, we can effectively reduce
the time complexity to $O(n^{2}/p)$. Moreover, as long as the splitting is
random, this method will not introduce any additional security degradation.

##  VI Related Work

The literature has demonstrated the focus on non-IID data FL scenarios in both
the attack side and the defense side.

Suresh et al. [51] analyzed backdoor attack performance using a non-IID
dataset and observed that the success rate highly rely on the adversary ratio.
Wang et al. [17] demonstrated that if backdoors are targeting low-probability
or edge-case samples, then they can also be hard to detect. Xie et al. [15]
proposed the distributed backdoor attack (DBA) to fully exploit the
distributed nature of FL. DBA decomposes a global trigger pattern into
separate local patterns and embeds them into the training set of different
adversarial parties respectively. Compared to standard centralized backdoors,
DBA is substantially more persistent and stealthy against FL. Cao et al. [16]
demonstrate that attackers can improve their stealthiness by reducing the
similarity of their submitted models in non-IID data scenarios.

Awan et al. [23] proposed a detection method based on the assumption that all
malicious clients have the same poisoning objective throughout the training
process. The gradient angle between any two malicious clients should always be
smaller than the angle between two honest clients. Zhao et al. [26] employed
client-side cross-validation and used the number of correctly classified
samples as a detection metric. Besides, clustering methods have been heavily
utilized for backdoor detection in non-IID data scenarios. Ghosh et al. [25]
propose a two-step detection – first cluster clients based on their empirical
risk minimizer value and then use trimmed mean [13] within each cluster to
filter out possible Byzantine nodes. Briggs et al. [24] introduced a
hierarchical clustering step to separate clusters of clients by the similarity
of their local updates to the joint global model. Verbraeken et al. [38]
proposed a definition of a familiar class, which is defined as a class in
which a client has sufficient data samples. The degree of a model being benign
is calculated as the superior of its performance over the average performance
of the group of clients possessing the familiar class. Rieger et al. [22]
employed an ensemble of clustering algorithms to effectively identify and
cluster model updates with similar training data.

##  VII Conclusions

We proposed BoBa, an effective solution for detecting backdoor attacks in
federated learning with non-IID data. By introducing overlapping clustering,
we establish BoBa as a powerful performance booster for detection mechanisms
against various backdoor attack scenarios. Our data distribution inference
model DDIG achieved high inference accuracy, which has dramatically improved
the subsequent clustering performance. The overlapping clustering method
further enhanced the system’s robustness as the trust estimation for each
client is based on collective input from multiple clusters rather than relying
on a single cluster’s assessment. For the detection step, we leverage both
latent space representation and model weights as key features. The combination
of these distinct feature spaces demonstrates significant improvements in
detection accuracy. The extensive evaluation and ablation study results
confirm the robustness and efficacy of BoBa, positioning it as a promising
safeguard for secure federated learning in real-world applications.

## References

  * [1] J. Konečnỳ, H. B. McMahan, F. X. Yu, P. Richtárik, A. T. Suresh, and D. Bacon, “Federated learning: Strategies for improving communication efficiency,” arXiv preprint arXiv:1610.05492, 2016.
  * [2] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas, “Communication-efficient learning of deep networks from decentralized data,” in Artificial Intelligence and Statistics (AISTATS 17), pp. 1273–1282, 2017.
  * [3] P. Kairouz, H. B. McMahan, B. Avent, A. Bellet, M. Bennis, A. N. Bhagoji, K. Bonawitz, Z. Charles, G. Cormode, R. Cummings, et al., “Advances and open problems in federated learning,” arXiv preprint arXiv:1912.04977, 2019.
  * [4] A. Hard, K. Rao, R. Mathews, S. Ramaswamy, F. Beaufays, S. Augenstein, H. Eichner, C. Kiddon, and D. Ramage, “Federated learning for mobile keyboard prediction,” arXiv preprint arXiv:1811.03604, 2018.
  * [5] S. Wang, T. Tuor, T. Salonidis, K. K. Leung, C. Makaya, T. He, and K. Chan, “Adaptive federated learning in resource constrained edge computing systems,” IEEE Journal on Selected Areas in Communications, vol. 37, no. 6, pp. 1205–1221, 2019.
  * [6] Y. Chen, L. Su, and J. Xu, “Distributed statistical machine learning in adversarial settings: Byzantine gradient descent,” Proceedings of the ACM on Measurement and Analysis of Computing Systems, vol. 1, no. 2, pp. 1–25, 2017.
  * [7] J. So, B. Güler, and A. S. Avestimehr, “Byzantine-resilient secure federated learning,” IEEE Journal on Selected Areas in Communications, 2020.
  * [8] R. Guerraoui, S. Rouault, et al., “The hidden vulnerability of distributed learning in byzantium,” in International Conference on Machine Learning, pp. 3521–3530, PMLR, 2018.
  * [9] M. Fang, X. Cao, J. Jia, and N. Gong, “Local model poisoning attacks to byzantine-robust federated learning,” in 29th $\\{$USENIX$\\}$ Security Symposium ($\\{$USENIX$\\}$ Security 20), pp. 1605–1622, 2020.
  * [10] A. N. Bhagoji, S. Chakraborty, P. Mittal, and S. Calo, “Analyzing federated learning through an adversarial lens,” in International Conference on Machine Learning, pp. 634–643, PMLR, 2019.
  * [11] E. Bagdasaryan, O. Poursaeed, and V. Shmatikov, “Differential privacy has disparate impact on model accuracy,” in Advances in Neural Information Processing Systems (NeurIPS 19), pp. 15453–15462, 2019.
  * [12] P. Blanchard, R. Guerraoui, J. Stainer, et al., “Machine learning with adversaries: Byzantine tolerant gradient descent,” in Advances in Neural Information Processing Systems, pp. 119–129, 2017.
  * [13] D. Yin, Y. Chen, K. Ramchandran, and P. Bartlett, “Byzantine-robust distributed learning: Towards optimal statistical rates,” arXiv preprint arXiv:1803.01498, 2018.
  * [14] E. M. E. Mhamdi, R. Guerraoui, and S. Rouault, “The hidden vulnerability of distributed learning in byzantium,” arXiv preprint arXiv:1802.07927, 2018.
  * [15] C. Xie, K. Huang, P.-Y. Chen, and B. Li, “Dba: Distributed backdoor attacks against federated learning,” in International conference on learning representations, 2019.
  * [16] J. Cao and l. Zhu, “A highly efficient, confidential, and continuous federated learning backdoor attack strategy,” in 2022 14th International Conference on Machine Learning and Computing (ICMLC), pp. 18–27, 2022.
  * [17] H. Wang, K. Sreenivasan, S. Rajput, H. Vishwakarma, S. Agarwal, J.-y. Sohn, K. Lee, and D. Papailiopoulos, “Attack of the tails: Yes, you really can backdoor federated learning,” Advances in Neural Information Processing Systems, vol. 33, pp. 16070–16084, 2020.
  * [18] S. Shen, S. Tople, and P. Saxena, “Auror: Defending against poisoning attacks in collaborative deep learning systems,” in Proceedings of the 32nd Annual Conference on Computer Security Applications, pp. 508–519, 2016.
  * [19] C. Fung, C. J. Yoon, and I. Beschastnikh, “Mitigating sybils in federated learning poisoning,” arXiv preprint arXiv:1808.04866, 2018.
  * [20] S. Li, Y. Cheng, W. Wang, Y. Liu, and T. Chen, “Learning to detect malicious clients for robust federated learning,” arXiv preprint arXiv:2002.00211, 2020.
  * [21] Y. Zhao, J. Chen, J. Zhang, D. Wu, J. Teng, and S. Yu, “Pdgan: A novel poisoning defense method in federated learning using generative adversarial network,” in International Conference on Algorithms and Architectures for Parallel Processing, pp. 595–609, Springer, 2019.
  * [22] P. Rieger, T. D. Nguyen, M. Miettinen, and A.-R. Sadeghi, “Deepsight: Mitigating backdoor attacks in federated learning through deep model inspection,” 2022.
  * [23] S. Awan, B. Luo, and F. Li, “Contra: Defending against poisoning attacks in federated learning,” in Computer Security–ESORICS 2021: 26th European Symposium on Research in Computer Security, Darmstadt, Germany, October 4–8, 2021, Proceedings, Part I 26, pp. 455–475, Springer, 2021.
  * [24] C. Briggs, Z. Fan, and P. Andras, “Federated learning with hierarchical clustering of local updates to improve training on non-iid data,” in 2020 International Joint Conference on Neural Networks (IJCNN), pp. 1–9, IEEE, 2020.
  * [25] A. Ghosh, J. Hong, D. Yin, and K. Ramchandran, “Robust federated learning in a heterogeneous environment,” arXiv preprint arXiv:1906.06629, 2019.
  * [26] L. Zhao, S. Hu, Q. Wang, J. Jiang, C. Shen, X. Luo, and P. Hu, “Shielding collaborative learning: Mitigating poisoning attacks through client-side detection,” IEEE Transactions on Dependable and Secure Computing, vol. 18, no. 5, pp. 2029–2041, 2020.
  * [27] P. Rieger, T. Krauß, M. Miettinen, A. Dmitrienko, and A.-R. Sadeghi, “Crowdguard: Federated backdoor detection in federated learning,” Network and Distributed Systems Security Symposium NDSS, 2024.
  * [28] G. Cleuziou, “An extended version of the k-means method for overlapping clustering,” in 2008 19th International Conference on Pattern Recognition, pp. 1–4, IEEE, 2008.
  * [29] P. Li, H. Dau, G. Puleo, and O. Milenkovic, “Motif clustering and overlapping clustering for social network analysis,” in IEEE INFOCOM 2017-IEEE Conference on Computer Communications, pp. 1–9, IEEE, 2017.
  * [30] A. Banerjee, C. Krumpelman, J. Ghosh, S. Basu, and R. J. Mooney, “Model-based overlapping clustering,” in Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, pp. 532–537, 2005.
  * [31] E. Bagdasaryan, A. Veit, Y. Hua, D. Estrin, and V. Shmatikov, “How to backdoor federated learning,” in International Conference on Artificial Intelligence and Statistics, pp. 2938–2948, PMLR, 2020.
  * [32] Z. Sun, P. Kairouz, A. T. Suresh, and H. B. McMahan, “Can you really backdoor federated learning?,” arXiv preprint arXiv:1911.07963, 2019.
  * [33] X. Cao, J. Jia, and N. Z. Gong, “Provably secure federated learning against malicious clients,” in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 35, pp. 6885–6893, 2021.
  * [34] N. Wang, Y. Xiao, Y. Chen, Y. Hu, W. Lou, and Y. T. Hou, “Flare: defending federated learning against model poisoning attacks via latent space representations,” in Proceedings of the 2022 ACM on Asia Conference on Computer and Communications Security, pp. 946–958, 2022.
  * [35] C. Xie, M. Chen, P.-Y. Chen, and B. Li, “Crfl: Certifiably robust federated learning against backdoor attacks,” in International Conference on Machine Learning, pp. 11372–11382, PMLR, 2021.
  * [36] T. D. Nguyen, P. Rieger, R. De Viti, H. Chen, B. B. Brandenburg, H. Yalame, H. Möllering, H. Fereidooni, S. Marchal, M. Miettinen, et al., “$\\{$FLAME$\\}$: Taming backdoors in federated learning,” in 31st USENIX Security Symposium (USENIX Security 22), pp. 1415–1432, 2022.
  * [37] C. Dwork et al., “The algorithmic foundations of differential privacy,” Foundations and Trends® in Theoretical Computer Science, vol. 9, no. 3–4, pp. 211–407, 2014.
  * [38] J. Verbraeken, M. de Vos, and J. Pouwelse, “Bristle: Decentralized federated learning in byzantine, non-iid environments,” arXiv preprint arXiv:2110.11006, 2021.
  * [39] V. Shejwalkar and A. Houmansadr, “Manipulating the byzantine: Optimizing model poisoning attacks and defenses for federated learning,” in NDSS, 2021.
  * [40] P. Jain, P. Kar, et al., “Non-convex optimization for machine learning,” Foundations and Trends® in Machine Learning, vol. 10, no. 3-4, pp. 142–363, 2017.
  * [41] T. Gu, B. Dolan-Gavitt, and S. Garg, “Badnets: Identifying vulnerabilities in the machine learning model supply chain,” arXiv preprint arXiv:1708.06733, 2017.
  * [42] X. Cao, M. Fang, J. Liu, and N. Z. Gong, “Fltrust: Byzantine-robust federated learning via trust bootstrapping,” Network and Distributed Systems Security Symposium NDSS, 2021.
  * [43] H. Xiao, K. Rasul, and R. Vollgraf, “Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms,” arXiv preprint arXiv:1708.07747, 2017.
  * [44] A. Krizhevsky and G. Hinton, “Learning multiple layers of features from tiny images,” tech. rep., Citeseer, 2009.
  * [45] L. Deng, “The mnist database of handwritten digit images for machine learning research,” IEEE Signal Processing Magazine, vol. 29, no. 6, pp. 141–142, 2012.
  * [46] K. Simonyan and A. Zisserman, “Very deep convolutional networks for large-scale image recognition,” in International Conference on Learning Representations, 2015.
  * [47] A. Krizhevsky, I. Sutskever, and G. E. Hinton, “Imagenet classification with deep convolutional neural networks,” Advances in neural information processing systems, vol. 25, 2012.
  * [48] H. Mei, G. Li, J. Wu, and L. Zheng, “Privacy inference-empowered stealthy backdoor attack on federated learning under non-iid scenarios,” arXiv preprint arXiv:2306.08011, 2023.
  * [49] S. Andreina, G. A. Marson, H. Möllering, and G. Karame, “Baffle: Backdoor detection via feedback-based federated learning,” in 2021 IEEE 41st International Conference on Distributed Computing Systems (ICDCS), pp. 852–863, IEEE, 2021.
  * [50] S. Shi, Y. Xiao, C. Du, M. H. Shahriar, A. Li, N. Zhang, Y. T. Hou, and W. Lou, “Ms-ptp: Protecting network timing from byzantine attacks,” in Proceedings of the 16th ACM Conference on Security and Privacy in Wireless and Mobile Networks, pp. 61–71, 2023.
  * [51] A. T. Suresh, B. McMahan, P. Kairouz, and Z. Sun, “Can you really backdoor federated learning?,” 2019.
  * [52] H. Xiao, K. Rasul, and R. Vollgraf, “Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms,” 2017.

##  Appendix A Introduction of Defense Baselines

Krum [12] selects one of $n$ received updates
$\\{\delta_{1},...,\delta_{n}\\}$ that is similar to the remaining ones. Let
$d_{i,j}=\lVert\delta_{i}-\delta_{j}\rVert_{p}$ represent the $l_{p}$ norm
distance between the $i$-th update and the $j$-th update. Krum first selects
($n\\!-\\!f\\!-\\!2$) updates closest to $\delta_{i}$ and marks the selected
neighbors as $N_{i}$. The score of $\delta_{i}$ is computed by adding the
distances between $\delta_{i}$ and any $\delta_{j}(j\in N_{i})$ together,
i.e., $S_{i}=\sum_{j\in N_{i}}d_{ij}$. Finally, the update with the lowest
score ($c=\arg\min_{i}S_{i}$) is selected as the aggregation result. In [12],
Blanchard et al. proved that Krum was $(\alpha,f)$-Byzantine resilient when
$n\geq 2f+3$.

Median [13] selects the coordinate-wise median of $n$ received updates as the
final result. Specifically, for the final result $F\in\mathbb{R}^{d}$, the
$j$-th ($j\in[d]$) coordinate is $F^{j}=\text{Med}\\{\delta_{i}^{j}:i\in n\\}$
where $\delta_{i}^{j}$ represents the $j$-th coordinate of $\delta_{i}$ and
Med denotes 1-D median computation. Coordinate-Wise Median is proved to be
$(\alpha,f)$-Byzantine resilient when $n\geq 2f+1$.

Trim [13] aggregates the updates one coordinate by one coordinate. For each
coordinate, Trimmed Mean first excludes the largest $f$ values and the
smallest $f$ values among the total $n$ values from $n$ updates. The final
aggregation result is obtained by calculating the average value of the
remaining $(n-2f)$ items.

FLTrust [42] trains a server model using an auxiliary dataset at PS in each
iteration. PS bootstraps a trust score for each client based on its
directional deviation from server model update. In the model aggregation
phase, PS computes the average of the local model updates weighted by their
trust scores as a global model update.

CONTRA [23] detects malicious clients based on the assumption that all
malicious clients have the same poisoning objective throughout the training
process. Therefore, the alignment of any two malicious clients’ gradients
should always be smaller than the angle between the gradients of a malicious
and an honest clients and the angle between any two honest clients. CONTRA
implements a cosine similarity-based measure to determine the credibility of
local model parameters in each round and a reputation scheme to dynamically
promote or penalize individual clients based on their per-round and historical
contributions to the global model.

##  Appendix B Datasets

MNIST [45] is a dataset of handwritten digits. It consists of 60,000 training
records and 10,000 testing records, each is a $28\times 28$ grayscale image.
Each image belongs to one of the ten digits.

Fashion MNIST (fMNIST) [52] consists of a training set of 60,000 records and a
test set of 10,000 records. Each data record is a $28\times 28$ grayscale
image, associated with a label from 10 classes including T-shirt, Trouser,
Pullover, Dress, Coat, Sandal, Shirt, Sneaker, Bag, and Ankle boot.

CIFAR-10 [44] consists of 60000 32x32 colour images in 10 classes, with 6,000
images per class. There are 50,000 training images and 10000 test images. Each
image is from one of the ten classes: airplane, automobile, bird, cat, deer,
dog, frog, horse, ship, and truck.