Year: 2021

Abstract:
Federated Learning is a distributed learning paradigm which seeks to preserve the privacy of each participating node’s data. However, federated learning is vulnerable to attacks, specifically to our interest, model integrity attacks. In this paper, we propose a novel method for malicious node detection called MANDERA. By transferring the original message matrix into a ranking matrix whose column shows the relative rankings of all local nodes along different parameter dimensions, our approach seeks to distinguish the malicious nodes from the benign ones with high efficiency based on key characteristics of the rank domain. We have proved, under mild conditions, that MANDERA is guaranteed to detect all malicious nodes under typical Byzantine attacks with no prior knowledge or history about the participating nodes. The effectiveness of the proposed approach is further confirmed by experiments on three classic datasets, CIFAR-10, FASHIONMNIST and MNIST. Compared to the state-of-art methods in the literature for defending Byzantine attacks, MANDERA is unique in its way to identify the malicious nodes by ranking and its robustness to effectively defense a wide range of attacks.

heading: 1 INTRODUCTION
text: Federated learning (FL) has observed a steady rise in use across a plethora of applications. FL departs from conventional centralized learning by allowing multiple participating nodes to learn on a local collection of training data, before each respective node’s updates are sent to a global coordinator for aggregation. The global model collectively learns from each of these individual nodes before relaying the updated global update back to the participating nodes. With an aggregation of multiple nodes, the resulting model observes greater performance than if each node was to learn on their local subset only. FL presents two key advantages, increased privacy for the contributing node as local data is not communicated to the global coordinator, and a reduction in computation by the global node as the computation is offloaded to contributing nodes.
However, the presence of malicious actors in the collaborative process may seek to poison the performance of the global model, to reduce the output performance of the model (Chen et al., 2017; Fang et al., 2020; Tolpegin et al., 2020b), or to embed hidden back-doors within the model (Bagdasaryan et al., 2020). Byzantine attack aims to devastate the performance of the global model by manipulating the gradient values of malicious nodes in a certain fashion. As these attacks emerged, researchers seek to defend FL from the negative impacts of these attacks.
In the literature, there are two typical defense strategies: malicious node detection and robust learning. Malicious node detection defenses by detecting malicious nodes and removing them from the aggregation (Blanchard et al., 2017; Guerraoui et al., 2018; Li et al., 2020; So et al., 2021). Robust learning (Blanchard et al., 2017; Yin et al., 2018; Guerraoui et al., 2018; Fang et al., 2020; Cao et al., 2020), however, withstands a proportion of malicious nodes and defenses by reducing the negative impacts of the malicious nodes via various robust learning methods (Wu et al., 2020b; Xie et al., 2019; 2020; Cao et al., 2021).
In this paper, we focus on defensing Byzantine attacks via malicious node detection. In the literature, there have been a collection of efforts along this research line. Blanchard et al. (2017) propose a defense referred to as Krum that treats local nodes whose update vector is too far away from the aggregated barycenter as malicious nodes and precludes them from the downstream aggregation. Guerraoui et al. (2018) propose Bulyan, a process that performs aggregation on subsets of node
updates (by iteratively leaving each node out) to find a set of nodes with the most aligned updates given an aggregation rule. Xie et al. (2019) compute a Stochastic Descendant Score (SDS) based on the estimated descendant of the loss function, and the magnitude of the update submitted to the global node, and only include a predefined number of nodes with the highest SDS in the aggregation. On the other hand, Chen et al. (2021) propose a zero-knowledge approach to detect and remove malicious nodes by solving a weighted clustering problem. The resulting clusters update the model individually and accuracy against a validation set are checked. All nodes in a cluster with significant negative accuracy impact are rejected and removed from the aggregation step.
Although the aforementioned methods try to detect malicious nodes in different ways, they all share a common nature: the detection is based on the gradient updates directly. However, it is usually the case that different dimensions of the gradients remain quite different in the range of values and follow very different distributions. This phenomena makes it very challenging to precisely detect malicious nodes directly based on the node updates, as a few dimensions often dominate the final result. Although the weighted clustering method proposed by Chen et al. (2021) could avoid this problem partially by re-weighting different update dimensions, it is often not trivial to determine the weights in a principled way.
In this paper, we propose to resolve this critical problem from a novel perspective. Instead of working on the node updates directly, we propose to extract information about malicious nodes indirectly by transforming the node updates from numeric gradient values to the rank domain. Compared to the original numeric gradient values, whose distribution is difficult to model, the ranks are much easier to handle both theoretically and practically. Moreover, as ranks are scale-free, we no longer need to worry about the scale difference across different dimensions. We proved under mild conditions that the first two moments of the transformed rank vectors carry key information to detect the malicious nodes under a wide range of Byzantine attacks. Based on these theoretical results, a highly efficient method called MANDERA is proposed to separate the malicious nodes from the benign ones by clustering all local nodes into two groups based on the moments of their rank vectors. With the assumption that malicious nodes are the minority in the node pool, we can simply treat all nodes in the smaller cluster as malicious nodes and remove them from the aggregation.
The contributions of this work are as follows. (1) We propose the first algorithm leveraging the rank domain of model updates to detect malicious nodes (Figure 1). (2) We provide theoretical guarantee for the detection of malicious nodes based on the rank domain under Byzantine attacks. (3) Our method does not assume knowledge on the number of malicious nodes, which is required in the learning process of prior methods. (4) We experimentally demonstrate the effectiveness and robustness of our defense on Byzantine attacks, including Gaussian attack, Sign Flipping attack and Zero Gradient attack, in addition to a more subtle Label Flipping data poisoning attack. (5) An experimental comparison between MANDERA and a collection of robust aggregation techniques are provided. The computation times are also compared, demonstrating gains of MANDERA by operating in the rank domain.

heading: 2 DEFENSE FORMALIZATION

heading: 2.1 NOTATIONS
text: Suppose there are n local nodes in the federated learning framework, where n1 nodes are benign nodes whose indices are denoted by Ib and the other n0 = n − n1 nodes are malicious nodes whose indices are denoted by Im. The training model is denoted by f(θ,D), where θ ∈ Rp×1 is a p-dimensional parameter vector and D is a data matrix. Denote the message matrix received from all local nodes by the central server as M ∈ Rn×p, where Mi,: denotes the message received from node i. For a benign node i, let Di be the data matrix on it with Ni as the sample size, we have Mi,: = ∂f(θ,Di) ∂θ . A malicious node j ∈ Im, however, tends to attack the learning system by
manipulating Mj,: in some way. Hereinafter, we denote N∗ = min({Ni}i∈Ib) to be the minimal sample size of the benign nodes.
Given a vector of real numbers a ∈ Rp×1, define its ranking vector as b = Rank(a) ∈ perm{1, · · · , p}, where the ranking operator Rank maps the vector a to its permutation space perm{1, · · · , p} which is the set of all the permutations of {1, · · · , p}. For example, Rank(1.1,−2, 3.2) = (2, 3, 1). We adopt average ranking, when there are ties. With the Rank operator, we can transfer the message matrix M to a ranking matrix R by replacing its column M:,j by the corresponding ranking vectorR:,j = Rank(M:,j). Further define
ei , 1
p p∑ j=1 Ri,j and vi , 1 p p∑ j=1 (Ri,j − ei)2
to be the mean and variance of Ri,:, respectively. As it is shown in later subsections, we can judge whether node i is a malicious node based on (ei, vi) under various attack types. In the following, we will highlight the behaviour of the benign nodes first, and then discuss the behaviour of malicious nodes and their interactions with the benign nodes under various Byzantine attacks respectively.

heading: 2.2 BEHAVIOUR OF BENIGN NODES
text: As the behaviour of benign nodes does not depend on the type of Byzantine attack, we can study the statistical properties of (ei, vi) for a benign node i ∈ Ib before the specification of a concrete attack type. For any benign node i, the message generated for jth parameter is
Mi,j = 1
Ni Ni∑ l=1 ∂f(θ,Di,l) ∂θj , (1)
where Di,l denotes the lth sample on it. Throughout this paper, we always assume that Di,ls are independent and identically distributed (IID) samples drawn from a data distribution D. Under the independent data assumption, since Equation 1 tells us thatMi,j is the sample mean of IID random variables, i.e., {∂f(θ,Di,l)∂θj } Ni l=1, directly applying the Strong Law of Large Numbers (SLLN) and Central Limit Theorem (CLT) leads to the lemma below immediately.
Lemma 1. Under the independent data assumption, further denote µj = E(∂f(θ,Di,l)∂θj ) and σ 2 j = Var( ∂f(θ,Di,l)
∂θj ) <∞, with Ni going to infinity we have for ∀ j ∈ {1, · · · , p}
Mi,j → µj a.s. and Mi,j →d N ( µj , σ 2 j /Ni ) . (2)

heading: 2.3 BEHAVIOUR OF MALICIOUS NODE UNDER THE GAUSSIAN ATTACK
text: Definition 1 (Gaussian attack). In a Gaussian attack, the attacker manipulates malicious nodes to send Gaussian random messages to the global coordinator, i.e., {Mi,:}i∈Im are independent random samples from Gaussian distributionMVN (mb,:,Σ) , where mb,: = 1n1 ∑ i∈Ib Mi,: and Σ is the covariance matrix determined by the attacker.
Considering that Mi,j → µj almost surely (a.s.) with Ni going to infinity for all i ∈ Ib based on Lemma 1, it is straightforward to see that limN∗→∞mb,j = µj a.s., and the distribution ofMi,j for each i ∈ Im converges to the Gaussian distribution centered at µj . Lemma 2 provides the details. Lemma 2. Under the same assumption as in Lemma 1, with N∗ going to infinity, we have for each malicious node i ∈ Im under the Gaussian attack that
Mi,j →d N (µj ,Σj,j) , 1 ≤ j ≤ p. (3)
Lemma 1 and Lemma 2 tell us that for each parameter dimension j, {Mi,j}ni=1 are independent Gaussian random variables with the same mean (i.e, µj) but different variances (i.e., σ2j /Ni or Σj,j) under the Gaussian attack. Due to the symmetry of Gaussian distribution, it is straightforward to see
E(Ri,j) = n+ 1
2 , 1 ≤ i ≤ n, 1 ≤ j ≤ p.
Moreover, the exchangeability of benign nodes and the exchangeability of malicious nodes when N∗ is reasonably large tell us: for each parameter dimension j, there exist two positive constants s2b,j and s 2 m,j such that
Var(Ri,j) = s 2 b,j , ∀ i ∈ Ib, and Var(Ri,j) = s2m,j , ∀ i ∈ Im,
where both s2b,j and s 2 m,j are complex functions of σ 2 j , Σj,j and {Ni}i∈Ib . Further assume that Ri,j’s are independent of each other, thus ei = 1p ∑p j=1Ri,j is the sum of independent random variables with a common mean. Thus, according to the Kolmogorov Strong Law of Large Numbers (KSLLN), we know that ei converges to a constant almost surely, which in turn indicates that vi also converge some constant almost surely. The Theorem 1 summarizes the results formally, with the detailed proof provided in Appendix C. Theorem 1. Assuming {R:,j}1≤j≤p are independent of each other, under the Gaussian attack, we have for each local node i that
lim N∗→∞ lim p→∞
ei = n+ 1
2 a.s., (4)
lim N∗→∞ lim p→∞
( vi − s̄2b · I(i ∈ Ib)− s̄2m · I(i ∈ Im) ) = 0 a.s., (5)
where I(·) stands for the indicator function, s̄2b , 1p ∑p j=1 s 2 b,j and s̄ 2 m , 1 p ∑p j=1 s 2 m,j .
Considering that s̄2b = s̄ 2 m if and only if Σj,j’s fall into a lower dimensional manifold whose measurement is zero under the Lebesgue measure, we have P (s̄2b = s̄ 2 m) = 0 if the attacker specifies the Gaussian variance Σj,j’s arbitrarily in the Gaussian attack. Thus, Theorem 1 in fact suggests that the benign nodes and the malicious nodes are different on the value of vi, and therefore provides a guideline to detect the malicious nodes. Although the we do need N∗ and p to go to infinity for getting the theoretical results in Theorem 1, in practice the malicious node detection algorithm based on the theorem typically works very well when N∗ and p are reasonably large and Ni’s are not dramatically far away from each other.
The independent rank assumption in Theorem 1, which assumes that {R:,j}1≤j≤p are independent of each other, may look restrictive. However, in fact it is a mild condition that can be easily satisfied in practice due to the following reasons. First, for a benign node i ∈ Ib, Mi,j and Mi,k are often nearly independent, as the correlation between two model parameters θj and θk is often very weak in a larger deep neural network with a huge number of parameters. To verify the statement, we implemented independence tests for 100,000 column pairs randomly chosen from the message matrix M generated from the FASHION-MNIST data. Distribution of the p-values of these tests are demonstrated in Figure 2 via a histogram, which is very close to a uniform distribution, indicating that Mi,j and Mi,k are indeed nearly independent in practice. Second, even some M:,j and M:,k shows strong correlation, magnitude of the correlation would be reduced greatly during the transformation from M to R, as the final ranking Ri,j also depends on many other factors. Actually, the independent rank assumption could be relaxed to be uncorrelated rank assumption which assumes the ranks are uncorrelated with each other. Adopting the weaker assumption will result in a change of convergence type of our theorems from the “almost surely convergence” to “convergence in probability”, but with no essential influence to the our algorithm below.

heading: 2.4 MALICIOUS NODE DETECTION FOR SIGN FLIPPING ATTACK
text: Definition 2 (Sign flipping attack). Sign flipping attack aims to generate the gradient values of malicious nodes by flipping the sign of the average of all the benign nodes’ gradient at each epoch, i.e., specifyingMi,: = −rmb,: for any i ∈ Im, where r > 0,mb = 1n1 ∑ k∈Ib Mk,:.
Based on the above definition, the update message of a malicious node i under the sign flipping attack is
Mi,: = −rmb,: = − r
n1 ∑ k∈Ib Mk,:. (6)
For fixed {Mk,:}k∈Ib ,Mi,: is also a fixed vector without randomness, as it is a deterministic function of {Mk,:}k∈Ib . On the other hand, however, we can also treat Mi,: as a random vector, since the randomness of {Mk,:}k∈Ib can be transferred toMi,: via the link function in equation 6. In fact, for any parameter dimension j, considering that Mk,j →d N ( µj , σ 2 j /Nk ) for any k ∈ Ib according to
Lemma 1, it is straightforward to see thatMi,j = − rn1 ∑ k∈Ib Mk,j can also be well approximated by a Gaussian distribution. The lemma 3 summarizes the result formally. Lemma 3. Under the sign flipping attack, for each malicious node i ∈ Im and any parameter dimension j, we have Mi,j = − rn1 ∑ k∈Ib Mk,j is a deterministic function of {Mk,j}k∈Ib , whose limiting distribution when N∗ goes to infinity is
Mi,j →d N ( µj(r), σ 2 j (r) ) , 1 ≤ j ≤ p, (7)
where µj(r) = −rµj , σ2j (r) = r2·σ2j n1·N̄b , and N̄b = n1∑ k∈Ib 1 Nk is the harmonic mean of {Nk}k∈Ib .
Lemma 1 and Lemma 3 tell us that for each parameter dimension j, the distribution of {Mi,j}ni=1 is a mixture of Gaussian components {N ( µj , σ 2 j /Ni ) }i∈Ib centered at µj plus a point mass located at µj(r) = −rµj . If Ni’s are reasonably large, variances σ2j /Ni’s would be very close to zero, and the probability mass of the mixture distribution would concentrate to two local centers µj and µj(r) = −rµj , one for the benign nodes and the other one for the malicious nodes. This intuition provides us the guidance to identify the malicious nodes in this attack pattern. Transforming to the rank domain, the above intuition leads to different behavior patterns of the benign nodes and the malicious nodes in the rank matrix R, which in turn result in different limiting behavior of (ei, vi) for the benign and malicious nodes. The theorem 2 summarizes the results formally, with the detailed proof provided in Appendix D. Theorem 2. With the same independent rank assumption as posed in Theorem 1, under the sign flipping attack, we have for each local node i that
lim N∗→∞ lim p→∞
ei = µ̄b · I(i ∈ Ib) + µ̄m · I(i ∈ Im) a.s., (8)
lim N∗→∞ lim p→∞
vi = s̄ 2 b · I(i ∈ Ib) + s̄2m · I(i ∈ Im) a.s., (9)
where µ̄b = n+n0+12 − n0ρ, µ̄m = n1ρ + n0+1 2 , ρ = limp→∞ ∑p j=1 I(µj>0) p , s̄ 2 m and s̄ 2 b are both quadratic functions of ρ whose concrete form also depends on n0 and n1.
Considering that µ̄b = µ̄m if and only if ρ = 12 , and s̄ 2 b = s̄ 2 m if and only if ρ is the solution of a quadratic function, the probability of (µ̄b, s̄2b) = (µ̄m, s̄ 2 m) is zero as p → ∞. Such a phenomenon suggests that we can detect the malicious nodes based on the moments (ei, vi) to defense the sign flipping attack as well. Noticeably, we note that the limit behaviour of ei and vi does not dependent on the specification of r, which defines the sign flipping attack. Although such a fact looks a bit abnormal at the first glance, it is totally understandable once we realize that with the variance of Mi,j shrinks to zero with Ni goes to infinity for each benign node i, any different between µj and µj(r) would result in the same rank vectorR:,j in the rank domain.

heading: 2.5 MALICIOUS NODE DETECTION FOR ZERO GRADIENT ATTACK
text: Definition 3 (Zero gradient attack). Zero gradient attack aims to make the aggregated message to be zero, i.e., ∑n i=1Mi,: = 0, at each epoch, by specifyingMi,: = − n1 n0 mb,: for all i ∈ Im.
Apparently, the zero gradient attack defined above is a special case of sign flipping attack by specifying r = n1n0 . Since the conclusions of Theorem 2 keep unchanged for different specifications of r as we have discussed, we have the following corollary for zero gradient attack. Corollary 1. Under the zero gradient attack, ei’s and vi’s follow exactly the same limiting behaviours as described in Theorem 2.

heading: 2.6 MANDERA
text: Theorem 1, 2 and Corollary 1 imply that, under these three attacks (Gaussian attack, zero gradient attack and sign flipping attack), the first two moments ofRi,:, i.e., (ei, vi), converge to two different limits for the benign nodes and the malicious nodes, respectively. Thus, for a real dataset where Ni’s and p are all finite but reasonably large numbers, the scatter plot of {(ei, vi)}1≤i≤n would demonstrate a clustering structure: one cluster for the benign nodes and the other cluster for the malicious nodes. Figure 3 illustrates such a scatter plot for the 100 local nodes in a typical epoch of training the FASHION-MNIST dataset under different FL settings (to keep the two dimensions of the scatter plot to the same scale, we replaced vi by its square root si = √ vi instead). Clearly, a simple clustering procedure would detect the malicious nodes from the scatter plot. Based on this intuition, we propose MAlicious Node DEtection via RAnking (MANDERA) to detect the malicious nodes, whose workflow is detailed in Algorithm 1.
Algorithm 1 Malicious node detection via ranking (MANDERA) Input: The message matrixM .
1: Convert the message matrixM to the ranking matrixR by applying Rank operator. 2: Compute mean and standard deviation of rows inR, i.e., {(ei, si)}1≤i≤n. 3: Run the clustering algorithm K-means to {(ei, si)}1≤i≤n with K = 2, and predict the set of
benign nodes with the lager cluster denoted by Îb. Output: The predicted benign node set Îb.
Remark. MANDERA can be applied to either a single epoch or multiple epochs. For a single-epoch mode, the input data M is the message matrix received from a single epoch. For multiple-epoch mode, the data M is the column-concatenation of the message matrices from multiple epochs. By default, the experiments below all use single epoch to detect the malicious nodes.
The predicted benign nodes Îb obtained by MANDERA naturally leads to an aggregated message m̂b,: =
1 #(Îb) ∑ i∈Îb Mi,:. The theorem 3 shows that Îb and m̂b lead to consistent estimations of
Ib andmb respectively, indicating that MANDERA enjoys robustness guarantee (Steinhardt, 2018) for typical Byzantine attacks. Theorem 3. Under the three typical Byzantine attacks, i.e., Gaussian attack, sign flipping attack and zero gradient attack, we have:
lim N∗→∞ lim p→∞ P(Îb = Ib) = 1 and lim N∗→∞ lim p→∞ E||m̂b,: −mb,:||2 = 0. (10)
The proof of Theorem 3 can be found in Appendix E.

heading: 3 EXPERIMENTS
text: We evaluate the efficacy in detecting malicious nodes within the federated learning framework with the use of three Datasets. The first is the FASHION-MNIST dataset (Xiao et al., 2017), a dataset of 60,000 and 10,000 training and testing samples respectively divided into 10 classes of apparel. The second is CIFAR-10 (Krizhevsky et al., 2009), a dataset of 60,000 small object images also containing 10 object classes. The third is MNIST (Deng, 2012) dataset which appears in Appendix H. In these experiments we mainly adopt implementations of Byzantine attacks released by (Wu et al., 2020b;a) and the label flipping attack (Tolpegin et al., 2020b;a). The label flipping attack is a data poisoning attack that alters one or more labels of training data to an attacker’s pre-determined target label. For example, in CIFAR-10’s object labels, an attacker may change the labels of their local cat images to be labelled as dogs. We use the Label Flipping attack as a comparative poisoning attack that achieves its objective in a more subtle manner. In our experiments, we set Σ = 30I for the Gaussian attack and r = 3 for the sign flipping attack, where I is the identity matrix. For all experiments we fix n = 100 participating nodes, of which a variable number of nodes are poisoned |n0| ∈ {5, 10, 15, 20, 25, 30}. The training process is run until 25 epochs have elapsed. We have described the structure of these networks in Appendix A.

heading: 3.1 ILLUSTRATION OF THE AVERAGE RANKING AND STANDARD DEVIATION OF RANKING
text: Section 2 speculated that the distribution of parameter ranks differ sufficiently for the detection of malicious and benign nodes. We validate this hypothesis in Figure 3 by illustrating the difference
between the benign nodes and malicious nodes in terms of the mean of gradients’ rankings and the standard deviation of gradients’ ranking.
It can be observed from Figure 3 that, under Gaussian and Label flipping attacks, the average rankings of malicious nodes are of a similar distribution to benign nodes. It is problematic for distinguishing between the two types of nodes, if only average ranking information is used. On the other hand, Figure 3 displays a larger separation of distributions for the standard deviation of ranking. It is noted that all 4 attacks observe a convergence of the distributions as the number of malicious nodes increase, increasing the difficulty of defense for both MANDERA and all other defenses. However, the likelihood of an attacker controlling increasingly large numbers of malicious nodes also decrease.

heading: 3.2 MALICIOUS NODE DETECTION BY MANDERA
text: We test the performance of MANDERA on the update gradients of a model under attacks. In this section, MANDERA acts as an observer without intervening in the learning process to identify malicious nodes with a set of gradients from a single epoch. Each configuration of 25 training epochs, with a given number of malicious nodes was repeated 20 times. Figure 4 demonstrates the classification performance (Metrics defined in Appendix B) of MANDERA with different settings of participating malicious nodes and the four poisoning attacks of Guassian Attack (GA), Zero Gradient attack (ZG), Sign Flipping attack (SF) and the Label Flipping attack (LF).
While we have formally demonstrated the efficacy of MANDERA in accurately detecting potentially malicious nodes participating in the federated learning process. In practice, to leverage an unsupervised K-means clustering algorithm, we must also identify the correct group of nodes as the malicious group. Our strategy is to identify the group with the most exact gradients, or otherwise the smaller group (we regard a system with over 50% of their nodes compromised as having larger issues than just poisoning attacks) 1. We also test other clustering algorithms, such as hierarchical clustering and Gaussian mixture models (Fraley & Raftery, 2002). It turns out that the performance of MANDERA is quite robust with different choices of clustering methods. Detailed results can be found in Appendix F.
From Figure 4, it is immediately evident that the recall of the malicious nodes for the Byzantine attacks is exceptional. However, occasionally benign nodes have also been misclassified as malicious under a SF, and to a lesser extent the ZG attack for both datasets. On all attacks, in the presence of more malicious nodes, the recall of malicious nodes trends down. As for the data poisoning attack of LF, it is consistently more difficult to detect, however we note that the LF attack has a more subtle influence on the model in contrast to the impact of Byzantine attacks.

heading: 3.3 MANDERA FOR DEFENDING AGAINST POISONING ATTACKS
text: In this section, we encapsulate MANDERA into a module prior to the the aggregation step, MANDERA has the sole objective of identifying malicious nodes, and excluding their updates from the global aggregation step. Each configuration of 25 training epochs, a given poisoning attack, defense method, and a given number of malicious nodes was repeated 10 times. We compare MANDERA against 5 other robust aggregation defense methods, Krum (Blanchard et al., 2017), Bulyan (Guerraoui et al., 2018), Trimmed Mean (Yin et al., 2018), Median (Yin et al., 2018) and FLTrust (Cao et al., 2020). Of which the first 2 requires an assumed number of malicious nodes, and the latter 3 only aggregate robustly.
From Figure 5, it is observed that MANDERA performs about the same as the best performing defense mechanisms, close to the performance of a model not under attack. MANDERA’s accuracy
1More informed approaches to selecting the malicious cluster can be tested in future work. E.g. Figure 3 displays less variation of rank variance in malicious cluster compared to benign nodes. This could robust selection of the malicious group, and enabling selection of malicious groups larger than 50%.
is observed to vary slightly under the LF attack on fashion data with 30 malicious nodes, this is consistent with the larger accuracy ranges previously observed in Figure 4b. Interestingly, FLTrust as a standalone defense is weak in protecting against the most extreme Byzantine attacks. However, we highlight that FLtrust is a robust aggregation method against targeted attacks that may thwart defences like Krum, Trimmed mean. We see FLTrust as a complementary defence that relies on a base method of defence against Byzantine attacks, but expands the protection coverage of the FL system against adaptive attacks.

heading: 3.4 COMPUTATIONAL EFFICIENCY
text: We have previously been able to observe that MANDERA can perform at par with the current highest performing poisoning attack defenses. Another benefit arises with the simplification of the mitigation strategy with the introduction of ranking at the core of the algorithm. Sorting and Ranking algorithms are fast. Additionally, we only apply clustering on the two dimensions of rank mean and standard deviation, in contrast to other works that seek to cluster on the entire node update (Chen et al., 2021). The times in Table 1 for MANDERA, Krum and Bulyan do not include the parameter/gradient aggregation step. These times were computed on 1 core of a Dual Xeon 14-core E5-2690, with 8 Gb of system RAM and a single Nvidia Tesla P100. Table 1 demonstrates that MANDERA is able to achieve a faster speed than that of single Krum 2 (by more than half) and Bulyan (by an order of magnitude).

heading: 4 DISCUSSION AND CONCLUSION
text: If attackers create more adaptive attacks unlike Definition 1, 2 and 3, they may evade MANDERA and achieve model poisoning. In this work, we have configured our Federated Learner to use all 100 nodes in the learning process at every round, we acknowledge FL framework may learn the global model only using subset of nodes at each round. In these settings MANDERA would still function, as we would rank and cluster on the parameters of the participating nodes, without assuming any number of poisoned nodes. In Algorithm 1, performance could be improved by incorporating higher order moments. MANDERA is unable to function when gradients are securely aggregated in its current form. However, malicious nodes can be identified and excluded from the secure aggregation step, while still protecting the privacy of participating nodes by performing MANDERA through secure ranking (Zhang et al., 2013; Lin & Tzeng, 2005) (recall that MANDERA only requires the ranking matrix to detect poisoned nodes). It remains to be seen the effectiveness of MANDERA on more advanced poisoning techniques like adversarial poisoning or Evasion attacks.
In conclusion, we have provided theoretical guarantees and experimentally shown efficacy in the use of ranking algorithms for the detection of malicious nodes performing poisoning attacks against federated learning. Our proposed method MANDERA, is able to achieve high detection accuracy and maintain a model accuracy on par with other seminal, high performing defense mechanisms, but with three notable advantages. First, provable guarantees for the use of ranking to detect Gaussian, Zero Gradient and Sign Flipping attacks. Next, faster detection with the use of ranking algorithms. Finally, the MANDERA defense does not need a prior estimation of the number of poisoned nodes. In this work we demonstrate how the rank domain can be useful in applications to defend against malicious actors.
Ethics Statement The core objective of our research is to provide an additional means of defense against poisoning nodes that target Federated Learning. To test our defense we have implemented different attacks against the Federated Learning framework. Attackers may adopt our defense strategy to design new poisoning attacks. Fortunately, these poisoning attacks can not be leveraged to leak private information from Federated learning models, instead only impact its performance.
2The use of multi-krum would have yielded better protection (c.f. Section 3) at the behest of speed.
Reproducibility Statement To ensure reproducible research, we have supplemented our proposal for MANDERA, by supplying both R and Python implementations of MANDERA used in this paper, uploaded with the remainder of the experiment code. The three datasets featured in this paper is CIFAR-10 (Krizhevsky et al., 2009), Fasion-MNIST (Xiao et al., 2017), and MNIST (Deng, 2012); we have used each of these dataset unaltered from their respective sources. We have stated the assumptions in our theorems and their proofs can be found in the Appendix. But to explain our assumptions in simple terms, (1) The data samples on each local node are independently drawn from the same distribution. (2) The gradient value for each parameter is independent to each other.

heading: A NEURAL NETWORK CONFIGURATIONS
text: We train these models with a batch size of 10, an SGD optimizer operates with a learning rate of 0.01, and 0.5 momentum for 25 epochs. The accuracy of the model is evaluated on a holdout set of 1000 samples.
A.1 FASHION-MNIST AND MNIST
• Layer 1: 1 ∗ 16 ∗ 5, 2D Convolution, Batch Normalization, ReLU Activation, Max pooling. • Layer 2: 16∗32∗5, 2D Convolution, Batch Normalization, ReLU Activation, Max pooling. • Output: 10 Classes, Linear.
A.2 CIFAR-10
• Layer 1: 1 ∗ 32 ∗ 3, 2D Convolution, Batch Normalization, ReLU Activation, Max pooling. • Layer 2: 32∗32∗3, 2D Convolution, Batch Normalization, ReLU Activation, Max pooling. • Output: 10 Classes, Linear.

heading: B METRICS
text: The metrics observed in Section 3 to evaluate the performance of the defense mechanisms are defined as follows:
Precision = TP
TP+FP ,
Accuracy = TP+TN
TP+FP+FN+TN ,
Recall = TP
TP+FN ,
F1 = 2× Precision× Recall Precision+Recall .

heading: C PROOF OF THEOREM 1
text: Proof. Because {Ri,j}1≤j≤p are independent random variables with a finite upper bound (since n is fixes) as assumed, direct application of KSLLN leads to
lim p→∞
1
p p∑ j=1 ( Ri,j − E(Ri,j) ) = 0 a.s., (11)
lim p→∞
1
p p∑ j=1 [( Ri,j − E(Ri,j) )2 −Var(Ri,j)] = 0 a.s.. (12) To prove Theorem 1 based on Equation 11 and 12, we need to derive the concrete form of E(Ri,j) and Var(Ri,j).
Fortunately, because Mi,j →d N ( µj ,Σj,j ) for ∀ i ∈ Im and Mi,j →d N ( µj , σ 2 j /Ni ) for ∀ i ∈ Ib when N∗ →∞, it is straightforward to see due to the symmetry of Gaussian distribution that
lim N∗→∞
E(Ri,j) = n+ 1
2 , 1 ≤ i ≤ n, 1 ≤ j ≤ p. (13)
Moreover, assuming that the sample sizes of different benign nodes approach to each other with N∗ going to infinity, i.e.,
lim N∗→∞
1
N∗ max i,k∈Ib
|Ni −Nk| = 0, (14)
for each parameter dimension j, {Mi,j}i∈Ib would converge to the same Gaussian distribution N (µj , σ2j /N∗) with the increase of N∗. Thus, due to the exchangeability of {Mi,j}i∈Ib and {Mi,j}i∈Im , it is easy to see that there exist two positive constants s2b and s2m, such that
lim N∗→∞
Var(Ri,j) = s 2 b · I(i ∈ Ib) + s2m,j · I(i ∈ Im), (15)
where s2b,j and s 2 m,j are both complex functions of n0, n1, σ 2 j , Σj,j and N ∗, and s2b,j = s 2 m,j if and only if σ2j /N ∗ = Σj,j .
Combining Equation 11 and 13, we have
lim N∗→∞ lim p→∞ ei = lim N∗→∞ lim p→∞
1
p p∑ j=1 Ri,j = n+ 1 2 a.s.,
i.e., Equation 4, which further indicates that ei and E(Ri,j) share the same limit when both p and N∗ go to infinity. Thus, we have
lim N∗→∞ lim p→∞ vi = lim N∗→∞ lim p→∞
1
p p∑ j=1 ( Ri,j − ei )2 = lim
N∗→∞ lim p→∞
1
p p∑ j=1 ( Ri,j − E(Ri,j) )2 a.s.. (16)
Combining Equation 12, 15, and 16, we have
lim N∗→∞ lim p→∞
( vi − s̄2b · I(i ∈ Ib)− s̄2m · I(i ∈ Im) ) = 0 a.s.,
i.e., Equation 5. Thus, the proof is complete.

heading: D PROOF OF THEOREM 2
text: Proof. It is straightforward to see that equation 11 also holds for sign flipping attack under the assumptions of Theorem 2. But, we need to re-calculate E(Ri,j) for benign and malicious nodes under the new setting.
Under the sign flipping attack, because Mi,j →d N ( µj(r), σ 2 j (r) ) for ∀ i ∈ Im and Mi,j →d
N ( µj , σ 2 j /Ni ) for ∀ i ∈ Ib when N∗ →∞, and
lim N∗→∞ (σ2j /Ni) = lim N∗→∞ σ2j (r) = 0,
it is straightforward to see that
lim N∗→∞
P (Mi,j >Mk,j) = I(µj > 0), ∀ i ∈ Ib,∀ k ∈ Im,
which further indicates that
lim N∗→∞
E(Ri,j) = n1 + 1
2 · I(i ∈ Ib) +
n+ n1 + 1
2 · I(i ∈ Im) if µj > 0,
lim N∗→∞
E(Ri,j) = n0 + 1
2 · I(i ∈ Im) +
n+ n0 + 1
2 · I(i ∈ Ib) if µj < 0;
(17)
lim N∗→∞
E(R2i,j) = S2[1,n1] · I(i ∈ Ib) + S 2 [n1+1,n] · I(i ∈ Im) if µj > 0,
lim N∗→∞
E(R2i,j) = S2[1,n0] · I(i ∈ Im) + S 2 [n0+1,n] · I(i ∈ Ib) if µj < 0, (18)
where S2[a,b] = 1 b−a+1 ∑b k=a k 2.
Combining Equation 11 and 17, we have
lim N∗→∞ lim p→∞ ei =
{ ρ · n+n1+12 + (1− ρ) · n0+1 2 = µ̄m a.s., if i ∈ Im,
ρ · n1+12 + (1− ρ) · n+n0+1 2 = µ̄b a.s., if i ∈ Ib,
where ρ = limp→∞ ∑p j=1 I(µj>0) p , i.e., Equation 8.
Define µ̄i = µ̄m · I(i ∈ Im) + µ̄b · I(i ∈ Ib). Based on KSLLN, we have:
lim p→∞
1
p p∑ j=1 [ (Ri,j − µ̄i)2 − E(Ri,j − µ̄i)2 ] = 0 a.s..
As we have proved in Equation 8 that
lim N∗→∞ lim p→∞ ei = µ̄i a.s.,
we have
lim N∗→∞ lim p→∞
1
p p∑ j=1 [ (Ri,j − ei)2 − E(Ri,j − µ̄i)2 ] = 0 a.s.,
which implies that
lim N∗→∞ lim p→∞ vi = lim N∗→∞ lim p→∞
1
p p∑ j=1 (Ri,j − ei)2 = lim N∗→∞ lim p→∞ 1 p p∑ j=1 E(Ri,j − µ̄i)2 a.s..
Considering that
lim N∗→∞ lim p→∞
1
p p∑ j=1 E(Ri,j − µ̄i)2
= lim p→∞ lim N∗→∞
1
p p∑ j=1 ( E(R2i,j)− 2µ̄iE(Ri,j) + (µ̄i)2 ) = [ τ̄m − (µ̄m)2 ] · I(i ∈ Im) + [ τ̄b − (µ̄b)2 ] · I(i ∈ Ib),
where τ̄b = ρ · S2[1,n1] + (1− ρ) · S 2 [n0+1,n] ,
τ̄m = ρ · S2[n1+1,n] + (1− ρ) · S 2 [1,n0] .
we have lim
N∗→∞ lim p→∞
vi = [ τ̄m − (µ̄m)2 ] · I(i ∈ Im) + [ τ̄b − (µ̄b)2 ] · I(i ∈ Ib).
It completes the proof of Equation 9 by specifying s̄2b = τ̄b − (µ̄b)2 and s̄2m = τ̄m − (µ̄m)2.

heading: E PROOF OF THEOREM 3
text: Proof. According to Theorem 1, 2 and Corollary 1, when both N∗ and p are large enough, with probability 1 there exist (eb, vb), (em, vm) and δ > 0 such that ||(eb, vb)− (em, vm)||2 > δ, and
||(ei, vi)− (eb, vb)||2 ≤ δ
2 for ∀ i ∈ Ib and ||(ei, vi)− (em, vm)||2 ≤
δ 2 for ∀ i ∈ Im.
Therefore, with a reasonable clustering algorithm such as K-mean with K = 2, we would expect Îb = Ib with probability 1. Because we can always find a ∆ > 0 such that ||Mi,: −Mj,:||2 ≤ ∆ for any node pair (i, j) in a fixed dataset with a finite number of nodes, and m̂b,: = mb,: when Îb = Ib, we have
E||m̂b,: −mb,:||2 ≤ ∆ · P(Îb 6= Ib), and thus
lim N∗→∞ lim p→∞
E||m̂b,: −mb,:||2 = 0.
It completes the proof.

heading: F MANDERA PERFORMANCE WITH DIFFERENT CLUSTERING ALGORITHMS
text: In this section, Figure 6 demonstrate that the discriminating performance of MANDERA when hierarchical clustering and Gaussian mixture models are used in-place of K-means for FASHIONMNIST data set remain robust.

heading: G MODEL LOSSES ON CIFAR-10 AND FASHION-MNIST DATA
text: Figure 7 presents the model loss to accompany the model prediction performance of Figure 5 previously seen in Section 3.

heading: H MODEL PERFORMANCE ON MNIST DATA
text: In this section we replicate experiments that were previously performed in Section 3 on the MNIST (Deng, 2012) dataset. The MNIST dataset is a dataset of 60,000 and 10,000 training and testing samples respectively divided into 10 classes of handwritten digits from multiple authors. Figure 8 contains the performance characteristics of MANDERA’s defense against the four attacks, whilst Figure 9 contains the comparative accuracy and loss when the different defenses are applied. Generally speaking, the observations previously observed continue to hold for this dataset.
GA ZG SF LF
A ccuracy
R ecall
P recision
F 1
5 10 15 20 25 30 5 10 15 20 25 30 5 10 15 20 25 30 5 10 15 20 25 30
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
Number of malicious nodes
S co
re
Metric Accuracy Recall Precision F1
(a) Gaussian mixture model.

Review summaries:
The paper focuses on Byzantine defense through malicious node detection in a Federated Learning setting. Namely, by ranking the gradients and then computing the mean/SD, the paper shows that the malicious and benign clients will cluster separately. Assuming that the number of malicious clients is fewer than the number of benign clients, and the clusters correctly separate the malicious from benign, the smaller cluster is removed, and training is done on the gradients in the larger cluster. Appropriate experiments are done to show the ability of the model in malicious node detection along with analysis of performance and computational requirements.