FedCut: A Spectral Analysis Framework for Reliable Detection of Byzantine Colluders

We consider a horizontal federated learning [66, 40] setting consisting of one server and $K$ clients. We assume $K$ clients²²2In this article we use terms ”client”, ”node”, ”participant” and ”party” interchangeably. have their local dataset $\mathcal{D}_{i}=\{(\mathbf{x}_{i,j},y_{i,j}\}_{j=1}^{n_{i}},i=1\cdots K$, where $\mathbf{x}_{i,j}$ is the input data, $y_{i,j}$ is the label and $n_{i}$ is the total number of data points for $i_{th}$ client. The training in federated learning is divided into three steps which iteratively run until the learning converges:

• •

  The $i_{th}$ client takes empirical risk minimization as:

  $$\min_{\mathbf{w}_{i}}F_{i}(\mathbf{w}_{i},\mathcal{D}_{i})=\min_{\mathbf{w}_{i}}\frac{1}{n_{i}}\sum_{j=1}^{n_{i}}\ell(\mathbf{w}_{i},\mathbf{x}_{i,j},y_{i,j}),$$

  (1)

  where $\mathbf{w}_{i}\in\mathbb{R}^{d}$ is the $i_{th}$ client’s local model weight and $\ell(\cdot)$ is a loss function that measures the accuracy of the prediction made by the model on each data point.

• •

  Each client sends respective local model updates $\nabla F_{i}$ to the server and the server updates the global model $\mathbf{w}$ as $\mathbf{w}=\mathbf{w}-\eta\frac{1}{K}\sum_{i=1}^{K}\nabla F_{i}$, where $\eta$ is learning rate.

• •

  The server distributes the updated global model $\mathbf{w}$ to all clients.

We assume a malicious threat mode where an unknown number of participants out of K clients are Byzantine, i.e., they may upload arbitrarily corrupt updates $\mathbf{g}_{b}$ to degrade the global model performance (MP). Under this assumption, behaviours of Byzantine clients and the rest of benign clients can be summarized as follows:

Note that under the assumed threat mode, each adversarial node has access to updates of all clients during the training procedure. They are aware of the adoption of Federated Learning Byzantine-resilient methods [6, 4, 63], and conspire to upload specially designed model updates that may overwhelm existing defending methods. Byzantine clients who behave consistently as such are referred to as colluders throughout this article. Moreover, we assume the server to be honest and try to defend the Byzantine attacks.

We regard model updates contributed by $K$ clients as an undirected graph $G=(V,E)$, where $V={v_{1},\cdots,v_{K}}$ represent $K$ model updates, $E$ is a set of weighted edge representing similarities between uploaded model updates corresponding to clients in $V$. We assume that the graph $G=(V,E)$ is weighted, and each edge between two nodes $v_{i}$ and $v_{j}$ carries a non-negative weight, e.g., $A_{ij}=\text{exp}(-||\mathbf{g}_{i}-\mathbf{g}_{j}||^{2}/2\sigma^{2})\geq 0$, where $\mathbf{g}_{i}$ is uploaded gradient for $i_{th}$ client and $\sigma$ is the Gaussian scaling factor. Let $G_{R}=(V_{R},E_{R})$ and $G_{B}=(V_{B},E_{B})$ respectively denote two subgraphs of $G$ representing benign and Byzantine clients.

Moreover, Byzantine problem [32] could be regarded as finding a optimal graph-cut for $G$ to distinguish the Byzantine and benign model updates. Since model updates from colluders form specific patterns (see Fig. 3 for examples), the aforementioned graph-cut can be generalized to the so called community-detection problem [41] in which multiple subsets of closely connected nodes are to be separated from each other.

We illustrate the spectral analysis of representative Byzantine attacks, especially, those launched by colluders. For example, Fig. 2 shows adjacency matrices with elements representing pairwise similarities between 70 benign clients under IID setting and 30 attackers (the darker the element the higher the pairwise similarity is). It is clear in each subfigure that benign clients form a single coherent cluster residing in the upper-left block of the adjacent matrix³³3Note that the order of the nodes illustrated in Fig. 2 is irrelevant and we separate benign nodes from Byzantine nodes only for better visual illustration., while attackers reside in the bottom-right parts of the adjacent matrix. We observe the following characteristics pertaining to benign as well as Byzantine model updates.

First, benign model updates form a single group (upper-left block of Fig. 2), which is formally illustrated by Assumption 4.1, i.e., they all lie in the group (circle) with center $\nabla F$ and radius $\kappa$. Specifically, when the local datasets are homogeneous (IID), $\kappa$ is small, indicating the strong similarity among benign model updates. When the local data of clients becomes heterogeneous, the radius $\kappa$ becomes larger. Note that Assumption 4.1 has been widely used to bound differences between model updates of benign clients, e.g., in [37, 69].

Second, Byzantine model updates can be categorized into four types (Fig. 3):

• •

  Non-Collusion: $\|\mathbf{g}_{b}-\nabla F\|>\kappa$ and malicious updates ($\mathbf{g}_{b}$) are far away from each other (e.g., Gaussian attack [6], label flipping [15] and sign flipping [15] attacks in Fig. 2(a), (b) and (c)).

• •

  Collusion-diff: $\|\mathbf{g}_{b}-\nabla F\|>\kappa$ and malicious updates ($\mathbf{g}_{b}$) form one or multiple clusters (small intra-cluster distance) (e.g., our designed collusion attack (see Sect. 7.1), same value attack [35], Fang-v1 [18] attacks in Fig. 2(d), (e) and (f)).

• •

  Collusion-mimic: $\|\mathbf{g}_{b}-\nabla F\|<\kappa$ and $\mathbf{g}_{b}$ of different attackers are almost identical ($\|\mathbf{g}_{b}^{i}-\mathbf{g}_{b}^{j}\|\ll\kappa$). It represents adversaries with strong connections form one or multiple clusters (small intra-cluster distance), and their behaviours are very similar to the few selected benign clients but are different from the rest of benign clients (e.g., Mimic attack [28] and Lie [4] in Fig. 2(g) and (h)).

• •

  Mixture: adversaries may combine Non-collusion, Collusion-diff, and Collusion-mimic arbitrarily to obtain a mixture attack.

In order to address the complex types of both benign and Byzantine model updates, we adopt he eigengap technique [53, 70] to reliably detect benign and Byzantine clusters (or communities). We provide the following proposition to elucidate characteristics of different types of Byzantine attacks in the lens of spectral analysis. The proof of Proposition 4.1 is deferred to Appendix C.

We illustrate with a concrete example the different spectra of four types of attacks in Fig. 3, in which each column represents one type of attack. We observe the following properties (all of the examples include 70 benign clients and 30 attackers):

• •

  for Non-Collusion attack, we use the Gaussian attack [35] to upload largely different random updates following $\mathcal{N}(0,200)$. Fig. 3(e) and (i) show the eigenvalue of adjacency matrix $L$ drops abruptly between index 30 and 31, i.e., the largest eigengap lies in index 31. It indicates the number of different communities is 31 with 70 benign clients forming a close group and 30 individual attackers forming other groups;

• •

  for Collusion-diff attack, we use the same-value attack [35] to upload updates consisting of all one elements, Fig. 3(f) and (j) illustrate the largest eigengap lies in 2 elucidating that benign clients form one group and colluders with strong connections form the other group;

• •

  for Collusion-mimic attack, we use the mimic attack [28] to upload updates that mimic one benign update, the largest eigengap is 70 because Byzantine colluders and mimiced benign clients form a group while the rest of 69 benign clients form 69 groups separately as Fig. 3(g) and (k) illustrate. It is because the connection among mimic colluders is much stronger than benign clients.

• •

  for Mixture attack, we combine the Gaussian attack (5 attackers), same-value attack (5 attackers), and mimic attack (20 attackers). Fig. 3(h) and (l) reveal that the largest eigengap is 80, in which mimic colluders and one mimiced benign client form a group. In contrast, 69 benign clients and 10 attackers form 79 groups separately. This example showcase that the mimic attack dominates the spectral characteristics of the Mixture attack. Therefore, for the proposed method, the Collusion-mimic type attack is first detected and removed, followed by the detection of other two types of attack (see Algo. 3 in Sect. 5.3.3 and line 3-4 of Algo. 2 in Sect. 5.2).

We evaluate two types of representative Byzantine-resilient methods (Robust statistics and the clustering based aggregation methods) and the proposed FedCut method (see Sect. 5.2) under four typical Byzantine Attacks mentioned in Sect. 4.2, in terms of their Byzantine Tolerance Rates (BTR) defined below. Specifically, we assume 10 benign model updates following 1D Gaussian distribution $\mathcal{N}(0.1,0.1)$ and see four types Byzantine attacks (S1-S4) as illustrated in Tab. II.

Next, we provide a toy example of four types of Byzantine attacks mentioned above to illustrate failure cases of existing Byzantine-resilient methods.

In order to evaluate different Byzantine-resilient methods under the four scenarios, we define the Byzantine Tolerant Rate representing the fraction of Byzantine Tolerant cases over repeated runs against attacks as follows:

Tab. III summarized toy example results for different Byzantine-resilient methods under four types of Byzantine attacks mentioned above. We can draw following conclusions:

• •

  First, for Non-Collusion attack (S1), all Byzantine-resilient methods except Kmeans [54] perform well (i.e., the BTR is higher than 90%), which indicates that Non-Collusion attack is easy to be defended.

• •

  Second, for Collusion-diff attack (S2), Robust Statistics based methods such as Krum [6], Median, Trimmed Mean [68] and DnC [52] are vulnerable to S2-s. This failure is mainly ascribed to the wrong estimation of sample mean or median misled by biased model updates from colluders. Moreover, the clustering based method i.e., Kmeans [54] fails in the S2-m, with BTR as low as 3.5%. This is because the clustering based method relies on the assumption that only one group of colluders exists, but two or more groups of colluders in S2-m are misclassified by naive clustering-based methods with wrong assumptions.

• •

  Third, for Collusion-mimic attack (S3), both Robust Statistics based methods and clustering based method fail, with BTR lower than 52.9%. The main reason is that colluders would introduce statistical bias for benign updates and similar behaviours of colluders are hard to detect.

• •

  Finally, the proposed FedCut method is able to defend against all attacks with high BTR (more than 95%) by using a Spatial-Temporal framework and spectral heuristics illustrated in Sect. 5.

It is worth mentioning that the toy example used in this Section only showcases some simplified failure cases that might defeat existing Byzantine-resilient methods. Instead, the attacking methods evaluated in Sect. 7 is more complex and detrimental, and we refer readers to thorough experimental results in Sect. 7 and Appendix B.

In order to use all information during the training, we define a Spatial-Temporal graph by considering behaviours of clients among all training iterations:

Given a set of model updates from $K$ clients over $T$ iterations during federated learning, one is able to construct such a Spatial-Temporal graph by assigning edge weights as the measured pair-wise similarity between model updates.

The construction of the Spatial-Temporal graph with historical information is motivated by a common shortcoming of Byzantine-resilient methods, e.g., reported in [29], which showed that methods without using historical information during the training might lead to deteriorated global model performances in the presence of colluders. Our ablation study in Appendix B also confirmed the importance of using the Spatial-Temporal graph.

As mentioned in Sect. 5.1, we have defined a Spatial-Temporal graph $G=<G^{1},\cdots,G^{T}>$ according to the model updates from $K$ clients over $T$ iterations during federated learning. Byzantine problem is then regarded as to find an optimal cut for $G$ such that the inter-cluster similarities (between benign clients and colluders) are as small as possible and intra-cluster similarities are as large as possible ⁶⁶6We view the cluster with the largest numbers as benign clients which constitute the largest community among all clients.. One optimal cut as such is known as the Normalized cut (Ncut) and has been initially applied to image segmentation [55, 42]. We adopt the Ncut approach to identify those colluders which have large intra-cluster similarities. Moreover, we extend the notion of Ncut to cater for the proposed Spatial-Temporal Graph over all iterations to make the detection of Byzantine colluders more consistent over multiple iterations. The c-partition Ncut for Spatial-Temporal Graph is thus defined as follows:

The proposed FedCut (Algo. 2) is used to get rid of malicious updates before model updates are aggregated. FedCut computes adjacent matrix according to the uploaded gradients over all training iterations and then takes the normalized cut to distinguish benign clients and colluders. Specifically, three important parameters including the appropriate Gaussian kernel $\sigma_{*}$, the cluster number $c$ and the set of mimic colluders $\mathcal{I}$ (who behave similarly to benign clients) need to be firstly determined (see Algo. 3). Then we calculate the adjacency matrix $A^{t}$ at $t_{th}$ iteration to remove the mimic colluders, i.e., set the connection between the mimic colluders and benign clients to be zero (line 2-7 in Algo. 2). We further compute normalized adjacency matrix $\tilde{L}^{t}$ by induction over $t$ iterations (line 8-9 in Algo. 2). Finally, we implement NCut into normalized adjacency matrix $\tilde{L}^{t}$ to choose the clusters of benign clients (line 10-12 in Algo. 2).

It is worth noting that FedCut runs over multiple learning iterations and, as shown by Proposition 5.1, it is guaranteed to provide the optimal c-partition Ncut defined by Eq. (4) (See Proof in Appendix C).

The determination of three parameters (i.e., the scaling parameter of Gaussian kernels $\sigma_{*}$, the number of clusters $c$ and mimic colluders $\mathcal{I}$) are critical in thwarting Byzantine Collusion attacks as illustrated in Sect. 4.3. We adopt the Spectral Heuristics about the following definition of eigengap to determine these three important parameters.

• •

  Models: logistic regression, LeNet [34] and AlexNet [25] three models are used in all experiment settings. (see results for other models and datasets in supplementary material).

• •

  Datasets: MNIST [33], Fashion-MNIST [60] and CIFAR10 [30] are used for image classification tasks. To simulate Non-IID settings, class labels assigned to clients follows a Dirichlet distribution $Dir(\beta)$ [36].

• •

  Federated Learning Settings: We simulate a horizontal federated learning system with K = 100 clients in a stand-alone machine with 8 Tesla V100-SXM2 32 GB GPUs and 72 cores of Intel(R) Xeon(R) Gold 61xx CPUs. In each communication round, the clients update the weight updates, and the server adopts Fedavg [40] algorithm to aggregate the model updates. The detailed experimental hyper-parameters are listed in Appendix A.

• •

  Byzantine attacks: We set 10%, 20% and 30% clients, i.e., 10, 20, and 30 out of 100 clients are Byzantine attackers. The following attacking methods are used in experiments:

  • –

    the same value attack: model updates of attackers are replaced by the all ones’ vector;

  • –

    the sign flipping attack: local gradients of attackers are shifted by a scaled value -4;

  • –

    the gaussian attack: local gradients at clients are replaced by independent Gaussian random vectors $\mathcal{N}(0,200)$;

  • –

    the Lie attack: it was designed in [4];

  • –

    the Fang-v1 attack and Fang-v2 attack: they were designed in [18] for coordinate-wise trimmed mean [68] and Krum [6] respectively;

  • –

    Mimic attack: Colluders may mimic the behaviours of some benign clients towards over-emphasizing some clients and under-representing others [28].

  • –

    Our designed multi-collusion attack: adversaries are separated into 4 groups, and the same group has similar values. For example, each group is sampled from $\mathcal{N}(\mu+\mu_{i},0.0001)$, and different groups have different $\mu_{i}$, where $\mu$ is the mean of uploaded gradients of all other benign clients.

• •

  Byzantine-resilient methods: Nine existing methods i.e., Statistic-based methods: Krum [6], Median [68], Trimmed Mean [68], Bulyan [21] and DnC [52], Serve-evaluating methods: FLtrust [10], Clustering-based methods: Kmeans [54] and the proposed method FedCut are compared in terms of following metrics.

• •

  Gaussian kernel scaling parameters of FedCut: the preselected set of $\sigma$: $\{\sigma_{1},\cdots,\sigma_{n}\}$ in Algo. 3 is the geometric sequence with common ratio $2$ of $(1,10\sqrt{10})$ for MNIST, $(1,10\sqrt{10})$ for Fashion-MNIST and $(0.1,10\sqrt{10})$ for CIFAR10.