MANDERA: Malicious Node Detection in Federated Learning via Ranking
Authors: Wanchuang Zhu
Benjamin Zi Hao Zhao
Simon Luo
Tongliang Liu
Ke Deng
Venue: Submitted to ICLR 2023 (2023)
Keywords: Federated Learning
Byzantine attack
malicious node detection
ranking

Abstract: Byzantine attacks hinder the deployment of federated learning algorithms. Although we know that the benign gradients and Byzantine attacked gradients are distributed differently, to detect the malicious gradients is challenging due to (1) the gradient is high-dimensional and each dimension has its unique distribution and (2) the benign gradients and the attacked gradients are always mixed (two-sample test methods cannot apply directly). To address the above, for the first time, we propose MANDERA which is theoretically guaranteed to efficiently detect all malicious gradients under Byzantine attacks with no prior knowledge or history about the number of attacked nodes. 
Specifically, we transfer the original updating gradient matrix into a ranking matrix. By such an operation, the scales of different dimensions of the gradients in the ranking space become identical. The high-dimensional benign gradients and the malicious gradients can be easily separated. The effectiveness of MANDERA is further confirmed by experimentation on four Byzantine attack implementations (Gaussian, Zero Gradient, Sign Flipping, Shifted Mean), comparing with state-of-the-art defenses. The experiments cover both IID and Non-IID datasets.

Under review as a conference paper at ICLR 2023
MANDERA: MALICIOUS NODE DETECTION IN FED- ERATED LEARNING VIA RANKING
Anonymous authors Paper under double-bling review
ABSTRACT
Byzantine attacks hinder the deployment of federated learning algorithms. Al- though we know that the benign gradients and Byzantine attacked gradients are distributed differently, to detect the malicious gradients is challenging due to (1) the gradient is high-dimensional and each dimension has its unique distribution and (2) the benign gradients and the attacked gradients are always mixed (two-sample test methods cannot apply directly). To address the above, for the first time, we propose MANDERA which is theoretically guaranteed to efficiently detect all malicious gradients under Byzantine attacks with no prior knowledge or history about the number of attacked nodes. More specifically, we transfer the original updating gradient space into a ranking matrix. By such an operation, the scales of different dimensions of the gradients in the ranking space become identical. The high-dimensional benign gradients and the malicious gradients can be easily sepa- rated. The effectiveness of MANDERA is further confirmed by experimentation four Byzantine attack implementations (Gaussian, Zero Gradient, Sign Flipping, Shifted Mean), comparing with state-of-the-ant defenses. The experiments cover both IID and Non-IID datasets.
INTRODUCTION
Federated Learning (FL) is a decentralized learning framework that allows multiple participating nodes to learn on a local collection of training data. The updating gradient values of each respective node are sent to a global coordinator for aggregation. The global model collectively learns from each of these individual nodes by aggregating the gradient updates before relaying the updated global model back to the participating nodes. The aggregation of multiple nodes allows the model to learn from a larger dataset which will result in the model having greater performance than each node was to learn their local subset of data. FL presents two key advantages: (1) the increase of privacy for the contributing node as local data is not communicated to the global coordinator, and (2) a reduction in computation by the global node the computation is offloaded contributing nodes.
However, FL is vulnerable to various attacks, including data poisoning attacks Tolpegin et al. (2020) and Byzantine attacks Lamport et al. (2019). The presence of malicious actors in the collaborative process may seek to poison the performance of the global model, to reduce the output per performance al. (2017): Baruch al. (2019); Fang al. (2020): Tolpegin al. (2020), or
of the model to embed hidden back-doors within the model Bagdasaryan an et al. (2020). Byzantine attack aims to devastate the performance the global model by manipulating the gradient values. These gradient values that have been manipulated are sent from malicious nodes which are unknown to the global
node. The Byzantine attacks can results in a global model which produces an undesirable outcome Lamport et al. (0119)
Researchers seek to defend FL. from the negative impacts of these attacks. This can be done by either identifying the malicious nodes or making the global model more robust to these types of attacks. In our paper, we focus on identifying the malicious nodes to exclude the nodes which are deemed to
be malicious in the aggregation step to mitigate the impact of malicious nodes. Most of the existing
methods rely on the gradient values to determine whether node is malicious or not, for example,
Blanchard al. (2017), Yin et al. (2018): Guerraoui et al. (2018); Li al. (2020): Fang al. (2020); Cao et al. (2020): Wu et al. (2020b); Xie et al. (0019)000)) Cao et al. (2021) and So et al. 2021
All the above methods are effective in certain scenarios.

---

Under review as a conference paper at ICLR 2023
There is lack of theoretical guarantee to detect all the malicious nodes in the literature. Although the extreme malicious gradients can be excluded by the above approaches, some malicious nodes could be mis-classified benign nodes and vice versa. The challenging issues in the community caused by the following two phenomena: [F1] the gradient values benign nodes and malicious nodes are often non-distinguishable; [F2] the gradient matrix is always high-dimensional (large column numbers) and each dimension follows its unique distribution. The phenomenon [FI] indicates that it is reliable detect the malicious nodes only using a single column from the gradient matrix. And the phenomenon [F2] hinders us from utilizing all the columns of the gradient matrix, because it requires scientific way accommodate large number of columns which are distributed considerably differently.
In this paper, we propose to resolve these critical challenges 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 ranking space. Compared to the original numeric gradient values, whose distribution is difficult to model, the rankings are much easier to handle both theoretically and practically. Moreover, as rankings are frele-free, 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 ranking vectors carry key information detect the malicious nodes under 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 ranking vectors. Figure [] shows an illustrative motivation to our method. It demonstrates the behaviors of malicious and benign nodes under mean shift attacks. Obviously, the malicious and benign nodes not distinguishable in the gradient space due to the challenges we mentioned above, while they are well separated in the ranking space.
10
20
30
0.49850
Gradent
0.49645
Node.type
0.49840
Benign
20
30
Bantun
Malicious
20
40
20
Mean
Figure 1: Patterns of nodes in gradient space and ranking space respectively under mean shift attacks. The columns of the figure represent the number of malicious nodes among 100 nodes: 10, 20 and 30.
The contributions of this work are follows: (1) we propose the first algorithm leveraging the ranking space model updates to detect malicious nodes (Figure 2h: (2) we provide theoretical guarantee for the detection of malicious nodes based on the ranking space under Byzantine attacks; (3) our method does not assume knowledge on the number of malicious nodes, which is required the learning process of most of the prior methods; (4) experimentally demonstrate the effectiveness and robustness of our defense on Byzantine attacks, including Gaussian attack (GA), Sign Flipping attack (SF) and Zero Gradient attack (ZG) and Mean Shift attack (MF); (5) experimental comparison between MANDERA and a collection of robust aggregation techniques is provided.
Global
Roject Malietous
Find and reject meliiius chaterr
MANDERA
Aggregate and update alobal model with benign clster
Rani
Compute Mean and of mow-mte
column wise
Figure An overview of MANDERA.
Related works. In the literature, there have been a collection of efforts along the research on defensing Byzantine attacks. Blanchard al. (2017) propose defense referred to 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. (008) propose Bulyan,
2

---

Under review as a conference paper at ICLR 2023
process that performs aggregation subsets of node updates (by iteratively leaving each node out) to find a set nodes with the most aligned updates given an aggregation rule, Xie et al.) (2019) compute 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, [Chnn et al. (202T) propose 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 validation set are checked. All nodes in cluster with significant negative accuracy impact are rejected and removed from the aggregation step.
DEFENSE AGAINST BYZANTINE ATTACKS VIA RANKING
2.1 NOTATIONS
Suppose there are n local nodes in the federated learning framework, where n nodes are benign nodes whose indices are denoted by Is and the other no n M1 nodes malicious nodes whose indices are denoted by Im- The training model is denoted by f(0, D), where 0 E RPx is a p-dimensional parameter vector and D is data matrix. Denote the message matrix received by the central server from all local nodes as M E RRxx, where M., denotes the message received from node i. For benign node i, let D, be the data matrix on with N; as the sample size, have O,)
M = 80 0-0-, where 0" is the parameter value from the global model. In the rest of the paper, we suppress @f(0.D.) le=e- to 0f(0.D:) denote the gradient value for simplicity purpose. A malicious node j E Zm. however, tends to attack the learning system by manipulating Mj, in some way. Hereinafter, we denote N' min([N)]ies (ieT),T,) to be the minimal sample size of the benign nodes.
Given vector of real numbers a E _ax1 define its ranking vector as perm[1, ,n}, where the ranking operator Rank maps the vector a to an element in permu- tation space perm (1, R.., [1,... ... , which is the set of all the permutations of (1,... ,n]. For example, = (2,3,)), it ranks the values from largest to smallest. We adopt average rank- ing, 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 vector R.j Rank(M..j) Further define
Rank(a)
C
P
R
and
P U
Σ P j-1
1
RR.. - e2)²
to be the mean and variance of R... respectively. As shown in later subsections, we can judge whether node i is a malicious node based on (ei, v;)) under various attack types. In the following, we will highlight the behavior of the benign nodes first, and then discuss the behavior of malicious nodes and their difference with the benign nodes under Byzantine attacks.
2.2 BEHAVIORS OF NODES UNDER BYZANTINE ATTACKS
Byzantine attacks aim to devastate the global model through manipulating the gradient values of some local nodes. For general Byzantine attack, assume that the gradient vectors of benign nodes and malicious nodes follow two different distributions G and F. We would expect systematical difference on their behavior patterns in the ranking matrix R, based which malicious node detection can be achieved. Theorem Saaeeemmdeemn demonttrates the concrete behaviors of benign nodes and malicious nodes under general Byzantine attacks.
Theorem (Behavior under Byzantine attacks). For a general Byzantine attack, assume that the gradient values from benign nodes and malicious nodes follow two distributions G(-) and F(-) respectively (both G and are p-dimensional). We have
lim lim ei N p-0
jbb I[(i In) Jim T[ii E Imm a.s.,
lim lim Ci N
- E Iz) + 2 Ili E Imm a.8.,
where (po, $)) and (Pm, 52, are highly non non-linearly functions of G(.) and F(-) whose concrete form is detailed in the Appendix A and "a.s." is the abbreviation of "almost surely".
3

---

Under review as a conference paper at ICLR 2023
Node. bype
Benign
Malciuus
45
55
40
45
50
40
50
Figure 3: The scatter plots of (e, s,) for the 100 nodes under four types of attack as illustrative examples demonstrating ranking mean and standard deviation from the Ist epoch of training for the FASHION-MNIST dataset. Four attacks are Gaussian Attack (GA), Zero Gradient attack (ZG), Sign Flipping attack (SF) and Mean shift attack (MS).
The proof can be found the Appendix A which is very rare, an obvious strategy evade defense is let F G. For this case, the attack will have no impact to the global model. More often, the attackers have little information about distribution G. In this case, is rare event for the attackers design distribution satisfying (Ps, 55)) (Am, $².) for the malicious nodes to follow. In fact, most popular Byzantine attacks never try to make such an effort at all. Thus, the malicious nodes and the benign nodes are distinguishable with respect to their feature vectors {(e;, 0;) e)) because (ei, 02) reaches to different limits for begin and malicious nodes. Considering that the standard deviation s; = /t, is typically of the similar scale of e;, hereinafter we utilize (e,, si), instead of (e,, v:), the feature vector of node i for malicious node detection.
the attackers can access the exact distribution G,
Figure 3 illustrates the typical scatter plots of (e,, 82) for benign and malicious nodes under four typical Byzantine attacks, i.c., GA, SN, ZG and MS. can be observed that malicious nodes and benign nodes are all well separated in these scatter plots, indicating a proper clustering algorithm will distinguish these two groups. We note that both 8 and 6 are informative for malicious node detection, since in cases (e.g., under Gaussian attacks) it is difficult distinguish malicious nodes from the benign ones based on only.
2.3 ALGORITHM FOR MALICIOUS NODE DETECTION UNDER BYZANTINE ATTACKS
Theorem I limplies that, under general Byzantine attacks, the feature vector (e,, 8;) node converges to two different limits for benign and malicious nodes, respectively. Thus, for real dataset where N₂'s and p are all finite but reasonably large numbers, the scatter plot {(e,, s1)ssss would demonstrate clustering structure: one cluster for the benign nodes and the other cluster for the malicious nodes.
Based on this intuition, we propose MAli- cious Node DEtection via RAnking (MAN- DERA) detect the malicious nodes, whose workflow is detailed in Algorithm I MANDERA can be applied to either single epoch or multiple epochs. For a single-epoch mode, the input data M the message matrix received from single epoch. For multiple-epoch mode, the data M is the columm-concatenation of the mes- sage matrices from multiple epochs. By de- fault, the experiments below all use single epoch to detect the malicious nodes.
Algorithm MANDERA
Input:
The message matrix M.
1: Convert the message matrix M to the ranking ma- trix R by applying Rank operator.
2: Compute mean and standard deviation of rows in
R. i.e., {(es, 8;) ss)isnnn
3: Run the clustering algorithm K-means to {(e,, s,)isinn with = 2, and predict the set of benign nodes with the lager cluster denoted by 2..
Output: The predicted benign node set I,.
The predicted benign nodes I, obtained by MANDERA naturally leads to an aggregated message #(Za) Eiet, M..-- Theorem shows that I, and my lead to consistent estimations of I. m
4

---

Under review as a conference paper at ICLR 2023
and my
Σ IEI, M respectively, indicating that MANDERA enjoys robustness guarantee for Byzantine attacks.
Steinhardi (2018)
Theorem (Robustness guarantee). Under Byzantine attacks, we have:
lim lim P(to- Ib) =1 and lim N--000 p-000
lim Ellmas mb. l2 = 0.
N-0000 p-000
The proof of Theorem 2 can be found in Appendix B As ( W.b.. MANDERA obviously
satisfies the (a. f) 1-Byaantine Resilience condition, which is used in Blanchard al. (2017) and
Guerraoui et al. (0188) to measure the robustness of their estimators.
3 THEORETICAL ANALYSIS FOR SPECIFIC BYZANTINE ATTACKS
Theorem I provides us general guidance about the behavior of nodes under Byzantine attacks. In this section, we examine the behavior for specific attacks, including Gaussian attacks, zero gradient attacks, sign flipping attacks and mean shift attack.
As the behavior of benign nodes does not depend on the type of Byzantine attack, we can study the statistical properties of (e;, U1) for benign node E In before the specification of concrete attack
type. For any benign node i, the message generated for jth parameter is M., N. Σ a (...)...) 80;
where D denotes the 1th sample on it. Throughout this paper, we assume that Da, 's are independent and identically distributed (IID) samples drawn from a data distribution D..
Lemma 1. Under the IID data assumption, further denote Pj = E @f(0.Dr.) 3e;
and o3
(0.0))).)) co, with N; going to infinity, for & j E {1, .p) we have Mij + Pj 80:
Var
almost surely (a.s.) and M.j 4N o3,,oo/N)))
Lemma D can be proved by using the Kolmogorov's 's Strong Law of Large Numbers (KSLLN) and Central Limit Theorem. For the rest of this section, we will derive the detailed forms of Fbb Pm. $ and g2 as defined in Theorem under four specific Byzantine attacks.
3.1 GAUSSIAN ATTACK
Definition (Gaussian attack). In Gaussian attack, the attacker generates malicious gradient values as follows: (M,,eit
MVW(m, E), where m,, - Σiez, M,, the mean vector of Gaussian distribution and > is the covariance matrix determined by the attacker.
Considering that M.,, > My a.s. with N, going to infinity for all i E In based on Definition T it is straightforward to that lim -o0 ma.j My a.s., and the distribution of M.j for each i E I.m converges to the Gaussian distribution centered at jlj- Based on this fact, the limiting behavior of the feature vector (et, 04) can be established for both benign and malicious nodes. Theorem summarizes the results, with the proof detailed in Appendix C
Theorem 3 (Bchavior under Gaussian attacks). Assuming {R.jhissp independent of each other, under the Gaussian attack, the behaviors of benign and malicious nodes are as follows:
Ab
Fm
n1 11
Sb.
$mjj
2
2
P
P
where o and sm. are both functioon of na, ny, o Egs and N whose concrete form is detailed in the Appendix
Considering that st x2 if and only if Ejy's fall into a lower dimensional manifold whose measurement is zero under the Lebesgue measure, we have P( 8% 0 if the attacker specifies the Gaussian variance Σn 's arbitrarily in the Gaussian attack. Thus. Theorem in fact suggests that the benign nodes and the malicious nodes are different on the value of u, and therefore provides 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 33] in practice the malicious node detection algorithm based on the theorem typically works very well when N and p are reasonably large and N, 's are not dramatically far away from each other.
5

---

Under review as a conference paper at ICLR 2023
The independent ranking assumption in The- orem 3 which assumes that {R., are independent of each other, may look restrictive. However, in fact is a mild condition that can be easily satisfied in practice due the follow- ing reasons. First, for benign node i E Za Mi.j and M,, are often nearly independent, as the correlation between two model param- eters 0, and 0 is often very weak in large deep neural network with 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 4 via a histogram, which is very close to a uniform distribution, indicating that M, and M,, are indeed nearly independent in practice. Second, even some M. and M, shows strong correlation, magnitude of the correlation would be reduced greatly during the transformation from M to R. the final ranking R.,, also depends on many other factors. Actually, the independent ranking assumption could be relaxed to be uncorrelated ranking assumption which assumes the rankings 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".
2300
0.55
0:50
0.15
1.0
u.vaue
Figure 4: Independence test for 100,000 column pairs randomly chosen from message matrix M generated from FASHION-MNIST data.
3.2 SIGN FLIPPING ATTACK
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 each epoch, ie., specifying M,,- = -rmp, for any E Ima where r > 0, m. Σ.ET. M
Based on the above definition, the update message of malicious node under the sign flipping attack is M,.- -, and benign nodes respectively, with the detailed proof provided in Appendix D
ΣKEI, MR.:- The theorem 4 summarizes the behavior of malicious nodes
Theorem (Behavior under sign flipping attacks). With the same assumption as posed in Theorem under the sign flipping attack, the behaviors of benign and malicious nodes are follows:
Nb no
noP;
jmm -1p+
(3)
$6 =S + (1 p Mot1, (2
S2
2 = ps
[ + (1- ())
(Rm))²
(4)
where p p= lim E (1,,0) of whose concrete form also depends on no and n1
Sta.ii b-u+1
Ehea 12, $2n and 3 are both quadratic functions
Considering that j Am if and only if quadratic function, the probability of (ia, sg) (Jum; sm) is zero as p- oc. Such a phenomenon suggests that we can detect the malicious nodes based on the moments (e,, v4) to defense the sign flipping attack as well. Noticeably, we note that the limit behavior of e, and U; 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 M,,; shrinks to zero with N, goes to infinity for each benign node i, any different between μy and μ (r) would result in the same ranking vector R..j the ranking space.
and 57 = 2 if and only if p is the solution of
3.3 ZERO GRADIENT ATTACK
Definition (Zero gradient attack). Zero gradient attack aims make the aggregated message to be zero, i.e., Σ M.,- = 0, at each epoch, by specifying M,-- = -1.m,, for all i E I,
Apparently, the zero gradient attack defined above is a special case of sign flipping attack by specifying 21. The conclusions of Theorem 4 keep unchanged for different specifications of r.. Therefore, Tu the behavior follows the same limiting behaviors described in Theorem 4

---

Under review as a conference paper at ICLR 2023
3.4 MEAN SHIFT ATTACK
Definition 4 (Mean shift attack). Mean shift attack (Baruch et al., 2019) manipulates the updates of the malicious nodes in the following fashion, mijj - 14j 2 oj for E Im and j S p. where
1 M 11 EiEz. Mas. oj - V by Sezz(M,,, - -m,)² and arg max, (l) <
n-2
2(n-no)
Mean shift attacks aim generate malicious gradients which are not well separated, but of different distributions, from the benign nodes. Theorem details the behavior of malicious nodes and benign nodes under mean shift attacks. The proof can be found in Appendix [E]
Theorem 5. With the same assumption as posed in Theorem 3 and additionally n is relatively large, under the mean shift attack, the behaviors of benign and malicious nodes are as follows:
n+1 Pb 2 mi (n1 .x): pm = not1
(5)
2 (T(m)
r(a
mo)) phg
0,
(6)
where [.] denotes the floor function, a = nn {2)],, (z) is the cumulative density function of the standard normal distribution and T r.) is the function of 'sum of squares", i.e., ((n) 2k=1 k.2
4 EXPERIMENTS
In these experiments extend the data poisoning experimental framework of Tolpegin al. (2020); Wu et al. (2020a), integrating Byzantine attack implementations released by Wu et al. (2020b) and the mean shift attack Baruch et al. (2019). The mean shift attack was designed to poison gradients by adding 'a little' amount of noise, and shown to be effective in defeating Krum (Blanchard et al. 2017) and Bulyan (Guerraoui et al. 2018) defenses. The mean shift attack is defined in Definition In our experiments, we set Σ = 30/ for the Gaussian attack and r = 3 for the sign flipping attack, where I is the identity matrix. For all experiments we fix a variable number of nodes are poisoned |nol E {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 F
100 participating nodes, of which
4.1 DEFENSE BY MANDERA FOR IID SETTINGS
We evaluate the efficacy in detecting malicious nodes within the federated learning framework with the use of three IID datasets. The first is the FASHION MINIST 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 Krizhevskk et al. (2099) a dataset of 60,000 small object images also containing 10 object classes. The third is the MNIST Deng (2012) dataset. The MNIST dataset is dataset of 60,000 and 10,000 training and testing samples respectively divided into 10 classes of handwritten digits from multiple authors.
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 single epoch. Each configuration of 25 training epochs, with given number of malicious nodes was repeated 20 times. Figure 5 demonstratts the classification performance (Metrics defined in Appendix G of MANDERA with different settings of participating malicious nodes and the four poisoning attacks, i.e., GA, ZG, SF and MS.
While we have formally demonstrated the efficacy of MANDERA in accurately detecting poten- tially malicious nodes participating 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 system with over 50% of their nodes compromised as having larger issues than just poisoning attacks). We also test other clustering algorithms, such as hierarchical clustering and Gaussian mixture models Fraley and Raftery (2002). It turns out that the performance of MANDERA is quite robust with different choices of clustering methods. Detailed results can
More informed approaches to selecting the malicious cluster can be tested in future work. E.g. Figure displays less variation of ranking 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%.
7

---

Under review as a conference paper at ICLR 2023
Meac
Anmer Eo End
Nexc
Enu
Mexc
And
LBUT
6.25
0.35
3.541
(a) CIFAR-10
(b) FASHION-MNIST
(c) MNIST-Digits
Figure 5: Classification performance of our proposed approach MANDERA under four types of attack for three IID settings.
Fihal
Deleee
Rhal
Deteee
(b) FASHION-MNIST accuracy Figure 6: Model Accuracy at each epoch of training, each line of the curve represents different defense against the Byzantine attacks.
(a) CIFAR-10 accuracy
(c) MNIST-Digits accuracy
be found in Appendix H nodes for the Byzantine attacks is exceptional. However, occasionally benign nodes have also been misclassified as malicious under SF attacks. On all attacks, in the presence of more malicious nodes, the recall of malicious nodes trends down.
From Figure it is immediately evident that the recall of the malicious
We encapsulate MANDERA into a module prior 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 al. (2018), 8), 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 6 it is observed that MANDERA outperforms the competing methods uniformly, approaching to the performance of a model not under attack. The corresponding model loss can be found in Appendix[] [[] 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 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.
Interestingly. FLTrust as standalone defense is weak in protecting against the
4.2 DEFENSE BY MANDERA FOR NON-IID SETTINGS
In this section, we evaluate applicability of MANDERA when applied in a non-IlID setting in Federated learning to validate its effectiveness. The batch size present through the existing evaluations of Section 4.1 is 10, this low setting practically yields gradient values at each local worker node as they were derived from non-lII samples. This is strong indicator that MANDERA could be effective for non-IID settings. We reinforce MANDERA's applicability in the non-IID setting by repeating the experiment QMNIST Yadav and Bottou (2019), dataset that is per-sample equivalent to MNIST Deng (0012). QMNIST, however, additionally provides us with writer identification information. This identity is leverages ensure that each local node only trains on digits written by
8

---

Under review as a conference paper at ICLR 2023
Metric
Accascy
Rocall
Procekn
F1
Defoncc
10-etack
Median
MARDERA
04
26
8F
M5
1.00
3.53
3.25
3.75
3.53
3.75
3.25
3.53
1.03
3.75
3.2
5 2025
5 10 20 do Number of malitious nodes
25 do
Mumber Efpchh
(a) Malicious node detection by MANDERA
(b) Model accuracy under different defenses
Figure 7: Results for a Non-IID setting: QMNIST dataset under four different Byzantine attacks.
set of unique users not seen by other workers. Such setting is widely recognized as non-IID setting in the community (Kairouz et al. (02T). For 100 nodes, this works out to be approximately 5 writers each node. All other experimental configurations remain the same as Section 4.1
Figure 7a demonstrates the effectiveness of MANDERA in malicious node detection for the non-IlI) setting. performs near perfectly under Gaussian attacks, zero gradient attacks and Mean shift attacks. On the other hand, when the number of malicious nodes is less than 25, MANDERA mis-classifies some benign nodes as malicious under sign-flipping attacks. However, is still capable to detect all the malicious nodes. This behavior is consistent with the behavior observed for MNIST in Figure 5c Figure ( shows the global model training accuracy with different defense strategies for a non-III setting. The figure indicates that MANDERA outperforms the other defensing strategies and achieves about the best performance where no attack is conduct to the global model. The model loss can be found in Appendix J MANDERA enjoys super-fast computation. We have listed the computational times of state-of-art art methods in Appendix K
5 DISCUSSION AND CONCLUSION
Theorem I indicates that Byzantine attacks can only evade MANDERA when the attackers know the distribution of benign nodes and the same time huge computational resources are required. This makes MANDERA strategy which is challenging for attackers to evade.
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 [ 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 and Tzeng 2005) (recall that MANDERA only requires the ranking matrix to detect poisoned nodes).
In conclusion, we proposed a novel way to tackle the challenges for malicious node detection when using the gradient values. Our method transfers the gradient values to ranking space. We have provided theoretical guarantees and experimentally shown efficacy in MANDERA for the detection of malicious nodes performing poisoning attacks against federated learning. Our proposed method MANDERA, is able to achieve excellent detection accuracy and maintain higher model accuracy than other seminal.
9

---

Under review as a conference paper at ICLR 2023
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 be leveraged leak private information from Federated learning models, instead only impact its performance.
Reproducibility Statement
To ensure reproducible research, 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 four datasets featured in this paper are CIFAR-10 10 (Krizhevsky al. 2009), Fasion-MNIST (Xiao et al., 2017), MNIST (Deng 2012) and QMNIST Yadav and Bottou (2019); 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.
Yaday
REFERENCES
Eugene Bagdasaryan, Andreas Veit, Yiqing Hua. Deborah Estrin, and Vitaly Shmatikov. How to backdoor federated learning. In International Conference on Artificial Intelligence and Statistics, pages PMLR, 2020.
Gilad Baruch, Moran Baruch, and Yoav Goldberg. A little is enough: Circumventing defenses for distributed learning, Advances in Neural Information Processing Systems, 32, 2019.
Peva Blanchard, EI Mahdi EI Mhamdi, Rachid Guerraoui, and Julien Stainer. Machine learning with adversaries: Byzantine tolerant gradient descent. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
http:::::p/ppppppeiiigsoos neurips Paper. pdf
cc/ cc/paper/2017/E112 Stt.://///..LEEE.DD..S.SSEEEESE.
Xiaoyu Cao, Minghong Fang, Jia Liu, and Neil Zhenqiang Gong. Fltrust: Byzantine-robust federated learning via trust bootstrapping. arXiv preprint a3X19:2012.139955 2020.
Xiaoyu Cao, Jinyuan Jia, and Neil Zhenqiang Gong. Provably secure federated learning against malicious clients. In Proceedings of the AAAI Conference on Artificial Intelligence, 2021.
Yudong Chen, Lili Su, and Jiaming Xu. Distributed statistical machine learning in adversarial settings: Byzantine gradient descent. Proc. ACM Meas. Anal. Comput. Syst., 1(2), December 2017. doi: 10.1145/3154503
Zheyi Chen, Pu Tian, Weixian Liao, and Wei Yu. Zero knowledge clustering based adversarial mitigation heterogencous federated learning. IEEE Transactions on Network Science and Engineering, ((2):1770-188; 2021. doi: 10. 00110097NSS22222000000990
Li Deng. The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 29(6)1141-144 141-142,
2012. 2012.
Minghong Fang, Xiaoyu Cao, Jinyuan Jia, and Neil Gong. Local model poisoning attacks to byzantine-robust federated learning. In 29th {USENIX) Security Symposium ((USENIX) Security 20), pages 1605-1622, 2020.
Chris Fralcy and Adrian E Raftery. Model-based clustering, discriminant analysis, and density estimation. Journal of the American statistical Association, 97(458):611-631, 2002.
Rachid Guerraoui, Sébastien Rouault, et al. The hidden vulnerability distributed learning in byzantium. In International Conference Machine Learning, pages 3521-3530. PMLR, 2018.
10

---

Under review as a conference paper at ICLR 2023
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Ad- vances and open problems in federated learning. Foundations and Trends@ in Machine Learning, 14(1-2):1-210, 2021.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Leslie Lamport, Robert Shostak, and Marshall Pease. The byzantine generals problem. In Concur- rency: the works of leslie lamport, pages 203-226. 2019.
Suyi Li. Yong Cheng, Wei Wang, Yang Liu, and Tianjian Chen. Learning detect malicious clients for robust federated learning. arXiv preprint arXivv2002.00211, 2020.
Hsiao- Ying Lin and Wen-Guey Tzeng. An efficient solution to the millionaires' problem based on homomorphic encryption. International Conference on Applied Cryptography and Network Security, pages 456-466. Springer, 2005.
Jinhyun So, Başak Güler, and A. Salman Avestimehr. Byzantine- secure federated learning.
IEEE Journal on Selected Areas Communications, 39(7):2168-218)) 2021. doi: 10.1 100//SACC 2020.3041404.
Jacob Steinhardt. Robust learning: Information theory and algorithms. PhD thesis, Stanford University, 2018.
Vale Tolpegin, Stacey Truex, Mehmet Emre Gursoy, and Ling Liu. Data poisoning attacks against federated learning systems. In European Symposium Research in Computer Security, pages 480-501. Springer, 2020.
Zhaoxian Wu, Qing Ling, Tianyi Chen, and Georgios B Giannakis. 2020a.
Byrd-saga github.
Zhaoxian Wu, Qing Ling, Tianyi Chen, and Georgios B Giannakis. Federated variance-reduced stochastic gradient descent with robustness to byzantine attacks. IEEE Transactions on Signal Processing, 68:4583 4596, 2020b.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv: 2017.
Cong Xie, Sanmi Koyejo, and Indranil Gupta. Zeno:
Distributed stochastic gradient descent with suspicion- bassd fault-tolerance. In International Conference on Machine Learning, pages 6893- 6901. PMLR, 2019.
Cong Xie, Sanmi Koyejo, and Indranil Gupta. Zeno++: Robust fully asynchronous sgd. In Interna- tional Conference on Machine Learning, pages 10495-10503. PMLR, 2020.
Chhavi Yadav and Léon Bottou. Cold case: The lost mnist digits. Advances in Neural Information Processing Systems 32. Curran Associates, Inc., 2019.
Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartlett. Byzantine-robus distributed learning: Towards optimal statistical rates. In International Conference on Machine Learning. pages
PMLR, 2018.
Lan Zhang, Xiang- Yang Li, Yunhao Liu, and Taeho Jung. Verifiable private multi-party computation: ranging and ranking. In 2013 Proceedings IEEE INFOCOM, pages 605-609, IEEE, 2013.
APPENDIX
A PROOF OF THEOREM
Proof. Let (x) and (z) be the cumulative distribution functions of Fy() and G,(:), fz(x) and (x) be the corresponding density functions, and rz( ni G)))( no - no F3 F2 (x) + be the expected ranking of value x among all entries in the jth column of the gradient value matrix.
11

---

Under review as a conference paper at ICLR 2023
Further define
0 Ebj = (())))(z)da Vos = ff (ry(z) - Ebj)) (x)da,
pc
(z(x)1;())dz, Vmn- = / (ry(2) - (5r))d
Emj=
It can be shown for any 1 S S that
Eaj E(R.,) Baj T(i Ib) Emj [[i Im), ViJ = V(R.,) = Voj I(i E Ib) + Vmy I(í E Im). Thus, would have according Kolmogorov's i strong law of large numbers (KSLLN) that
lim lim & - p-500
j&b [[ Ib) + Jmm T[ii E Im) a.s.,
lim lim ei No p0000
os T(i E I.) S T(i E Im) a.8.,
where the moments (Ma, 8))) and (Jmm ( are deterministic functions of (Ebj, Vog) and (Emii Vms) of the following form:
p
i = lim
Ebj-
Am =
lim p+20 p
Emj-
p-00 p
jml
j=l
$/ lim
Voje
22
lim p-to0
Vmj-
p
j=1
j=l
It completes the proof.
B PROOF OF THEOREM 2
Proof. According to Theorem I when both N and p are large enough, with probability there exist (eb, Vb), (Em; (mn)) and 8 >> 0 such that [[(e,, v6) (em, um)ll2 5, and
(e,, v/) - (cs, 2b 112 $ for Vi and [1(e, 0z) - (Cm, um)ll2 _ for V E Im-
2
Therefore, with reasonable clustering algorithm such K-mean with K 2. we would expect Σ, I, with probability
Because we can always find a A > 0 such that |M, - M,, s A for any node pair (i,j) in fixed dataset with finite number of nodes, and ma. myb when Iz Ip we have
E|| Ellm m.. lla < A PP + Ib),
and thus
lim lim E| El..: mp. 1|2 = 0.
NO No p-00
It completes the proof.
C PROOF OF THEOREM
Proof. According to Theorem we only need to compute P&, Rm, 8 and 82 under the Gaussian attacks.
Because Mi, N(,,, Ejs) for V i E Im and Mij dy (N,, of/N, for V i E I, when N* 0o, is straightforward to see due the symmetry of Gaussian distribution that
lim Enj lim Emj lim E(RA,)) No
11iisn 155sp.
(7)
N
N00000
12

---

Under review as a conference paper at ICLR 2023
Therefore, have
P
n + 1
1bb
lim
lim
Ebj
p-200 p -00
2
j=1
P
n+ 2
Pm
lim N - p-rko p
lim
Emj
j=1
Moreover, assuming that the sample sizes of different benign nodes approach to each other with N going to infinity, i...
lim 1 max |.V, .ol 0, -00 N L,KET,
(8)
for each parameter dimension j. {M., hIET, would converge to the same Gaussian distribution M(,, (2N*) with the increase of No. Thus, due to the exchangeability of {Mit and {MiJeeI is easy see that that
lim VoJ = 56 -00 where oi and my are both complex functions of 720, n1, 0²; Eوك and N and 8 = sm
lim
Vmj sm.j
N
if and only if o3/N** Ejg- According to Theorem
8 lim 1 p 2 Vis
-00 D bh and s = limp-so 2 Vmn limp- complete.
Σ jjml m.j" The proof is
D PROOF OF THEOREM
Proof. According Theorem only need to compute Puo Pm, $7 and 8 under the sign flipping attacks.
Lemma 2. Under the sign flipping attack, for each malicious node i E Im and any parameter dimension j. we have M.j = ni EkEI, M3. is a deterministic function of {Mr.j] whose limiting distribution when N goes to infinity is
Mij (1z(r), isisp.
(10)
A N.
where (r(r) = -r or(r)
and No Exez, Ny
ni is the harmonic mean of (N&JkeI,
Lemmal D and Lemma 2 tell us that for each parameter dimension j, the distribution of (M. Y= is mixture of Gaussian components {N (uz of oN/N.) JiI,, centered at μj plus point mass located (r) -rjj- If N,'s 's are reasonably large, variances /2/N''s would be very close to zero, and the probability mass of the mixture distribution would concentrate to two local centers μy and (r(r) = -pp.. one for the benign nodes and the other one for the malicious nodes.
Under the sign flipping attack, because Mi, 4 ((ps(r)) for V Im and Mi, 4 o3/NN) for Vivie In when N - 00, and
lim (0./N.) N N
lim
(r())= = -.
N
is straightforward to see that
lim P(Mi. Ms.)) 101 0), vi In, v k: Imm *00
which further indicates that
Ebj = lim B(Ra,) = n1 +1
lim N00
if μ1 0, n+ +1
No N=
2
n
lim Emj = lim E(R,,) N N
if 14 > 0,
N=
2
(11)
Enj = lim E(RR.j) n + +
lim
if 11 <0
N N
N
2
No +
lim Emj lim
E E(Ra,))
if 14 <
No000
N N00
2
13

---

Under review as a conference paper at ICLR 2023
lim
IB [E( = [1.m.] I(i E In) + S fm++ I(i Im) iʃ 14j > 0,
~00
(12)
lim E E(R [mm I[( Im) + S [no+1n) I[(i Io) if /4 0,
-00
where [a.b] b-a+1 Ek=a h.2 Therefore, we have
Pm = lim lim Σ j=1 Lnj = p. ntn++1 + (1 - p) no+1
Nbb lim
Σ p j=1 Fmmp #1 p) n
where p = limp- Σ 1(1
Define pr = Am
I(i E Im) + Pb . I(i E Ip). Considering that
lim lim P-0
Vis
5=1
lim lim
B(R,, m..)
200200--3 p
lim lim
Σ
[( R ((.,) + (1:)²)
pooc N
j=l
[mm -(mm) } I[(i Im) + [ - (po) I(i Io),
where
io = p. [mmls] + (1 - p) 22 no 1,n]
Fm = p. 22 +2m + (1 - p) S2 Sp..no
According to Theorem
1
P Vij = Fr - (Abb)
2 = lim
lim
p-000 N -00
j=l
s lim
lim
Vmg Fm -(im)
N
p 1=1
completes the proof.
E PROOF OF THEOREM 5
Proof. According to Theorem we only need to compute jab Pm, 8i and 82, under the mean shift attacks.
Under the mean shift attack, all the malicious gradient will be inserted at a position which is dependent on More specifically, for relatively large the samples from benign nodes are normally distributed. Therefore, on average, with proportion ((2) the benign nodes having higher values of gradient than the malicious nodes.
First all, we derive the property in term of the first moment. Denote a = [n]](=)]. For a benign node, we have
n +
no (nl a).
lim lim Edg = lim lim E(R,))
k
8
N N*-500 n-0000 N +00
-0000
2
Am
+
For malicious node, we have
a+1+ a+1+a 70
1 no
lim lim Emy lim lim E(R,))=
=a
N00 220
N-
2
2
14

---

Under review as a conference paper at ICLR 2023
Therefore, according to Theorem
71 +
110
Pb
lim
lim
lim
Ebj
+ 111
(1)
a),
N
+00
n 700
p00
2
j=1
1 no
Am
lim
lim lim
Emj = a +
N
2
j=1
Now, we derive the property in term of the second moment. For a benign node, we have
1
a
1 (r(n) + + 7(a + 1 1+ 1+))))
lim lim E(R
s²
N 4000000 n
T1
n1
where 7(-) is the function of 'sum of squares', i.e., T(n) = Ek= k.2
For malicious node, we have
1 + 710
lim lim B(R a
Therefore, according to Theorem T
g9 lim
lim lim
Voj -
(T(n) + +(() 7 mo)) 23.
N p-+00
p j=1
11
p
Sm lim
lim
lim
Vnj
+00 +00 p-000
j=1
completes the proof.
F NEURAL NETWORK CONFIGURATIONS
We train these models with a batch size of 10, an SGD optimizer operates with a learning rate 0.01, and 0.5 momentum for 25 epochs. The accuracy of the model is evaluated holdout set of 1000 samples.
F.1 FASHION -NIIS,, MNIST AND QMNIST
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.
F.2 CIFAR-10
Layer 32 3, 2D Convolution, Batch Normalization, ReLU Activation, Max pooling.
Layer 2: 32 32 * 3, 2D Convolution, Batch Normalization, ReLU Activation, Max pooling.
Output: Classes, Linear.
G
METRICS
The metrics observed Section 4 to evaluate the performance of the defense mechanisms are defined follows:
15

---

Under review as a conference paper at ICLR 2023
TP
Precision
TP+FP TP+IN
Accuracy TP+FP+EN+TN
TP
Recall TP+FN
Precision X Recall
F1 2 X Precision+Recall
H MANDERA PERFORMANCE WITH DIFFERENT CLUSTERING ALGORITHMS
In this section, Figure 8 demonstrate that the discriminating performance of MANDERA when hierarchical clustering and Gaussian mixture models are used in-place K-means for FASHION- MNIST data set remain robust.
Metric
Recal
Precsion
Metric
Accurscy
Recail
Precision
64
26
MS
GA
26
MS
1.00
3.00
0.75
0.75
0.25
0.25
1.00
1.00
0.25
0.25
1.00
3.00
0.5
0.78
1.00
1.00
030
025
0.28
2033520230
26 Number malicious nodes
25
10152222330
20 20 10 Number of malicious nades
Gaussian mixture model.
(b) Hierarchical clustering.
Figure 8: Classification performance of our proposed approach MANDERA (Algorithm I with other clustering algorithms under four types of attack for WASHION-MNIST data. GA: Gaussian attack; ZG: Zero-gradien attack; SF: Sign-flipping: and MS: mean shift attack. The boxplot bounds the 25th (QI) and 75th (Q3) percentile, with the central line representing the 50th quantile (median). The end points of the whisker represent the Q1-1.5(Q3-QI) and Q3+1.5(Q3-0)) (QQ3-Q1) respectively.
1 MODEL LOSSES ON CIFAR- 10, FASHION-MNIST AND MNIST DATA
Figure 9 presents the model loss to accompany the model prediction performance of Figure previously seen Section
MODEL LOSSES ON QMNIST DATA
Figure presents the model loss to accompany the model prediction performance of Figure 7b
previously seen in Section 4
16

---

Under review as a conference paper at ICLR 2023
bander
border Towd
kunder
CIFAR-IO model loss
(b) FASHION-MNIST model loss
(c) MNIST-Digits model loss
Figure 9: Model Loss at each epoch of training, each line of the curve represents a different defense against the Byzantine attacks.
Krum
Bulyan
Trim Trim-mean
FLTrust
Defence
NO -attack
Median
MANDERA
15
30
7.5
5.0
GA
2.5
0.0
2
96
1
log(Loss)
0
4-
35
2
0-
2
1
SW
0
0
101520250
101520250 5 201520250 101520250 Number of Epoch
101520255 5 10152025
Figure 10: QMNIST model loss.
Figure 11: Model Loss at each epoch of training, each line of the curve represents a different defense against the Byzantine attacks.
K COMPUTATIONAL EFFICIENCY
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 the of the algorithm. Sorting and Ranking algorithms are fast. Additionally, we only apply clustering on the two dimensions (mean and standard deviation of the ranking), in contrast other works that seek cluster the entire node update Chen et al.
17

---

Under review as a conference paper at ICLR 2023
(2021). The times in Table MANDERA, Krum and Bulyan do not include the parameter/graadent aggregation step. These times were computed on core Dual Xeon 14-core E5-2690, with TableeTeemore 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).
Gb of system RAM and a single Nvidia Tesla P100. Table
Table Mean and standard deviation of computational times for defense function given the same of gradients from 100 nodes, of which 30 were malicious. Each function was repeated 100 times.
Defense (Detection)
Mean + SD (ms)
Defense (Aggregation)
Mean + SD (ms)
MANDERA
643 + 8.646
Trimmed Mean
3.96 + 0.41
Krum (Single)
1352 + 10.09
Median
9.81 3.88
Bulyan
27209 = 233.4
FLTrust
361 = 4.07
Thhe of multi-krum would have yielded hetter protection (c.f. Section the hehest of speed.
18


Reviews:
[{"review_id": "mKwd8p-FuyE", "reviewer": "Reviewer_L24P", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposed a method to detect malicious nodes by converting the numerical features to rank features and then apply malicious nodes detection algorithm.", "summary_of_the_review": "The overall quality of the paper is okay but the limitations I mentioned in the weakness section seem to be hard to solve. As a result, I tend to reject. I will re-score if the authors can fix any of the issues.", "strength_and_weaknesses": "Strength:\n1. The idea of converting numerical features to rank features is inspiring. Will combine them both further improve the detection accuracy?\n\nWeakness:\n1. The claim is too strong. \"To address the above, for the first time, we propose MANDERA which is theoretically guaranteed to efficiently detect all malicious gradients under Byzantine attacks with no prior knowledge or history about the number of attacked nodes.\" I seriously doubt if it is theoretically possible to detect all the malicious nodes.\n2. The main theorems are all asymptotic while in malicious nodes detection we care about non-asymptotic guarantee. \n3. The IID assumption is a too strong for federated learning. It is well-known that data/gradients in federated systems are heterogeneous [1] and can be heavy-tailed with no-bounded second moments [2]. \n\n[1] FEDERATED OPTIMIZATION IN HETEROGENEOUS NETWORKS\n[2] On the Heavy-Tailed Theory of Stochastic Gradient Descent for Deep Neural Networks\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "i72PcNBtIfm", "reviewer": "Reviewer_9NF6", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this paper, the authors propose MANDERA that detects Byzantine gradients in the ranking space. The authors analyze the robustness of proposed MANDERA under some specific Byzantine attacks. Experimental results verify the efficacy of proposed MANDERA.", "summary_of_the_review": "Although the idea of detecting Byzantines in the ranking space is interesting, the proposed MANDERA fails under a particular attack. \n", "strength_and_weaknesses": "Strength:\n\n- The discussed topic of Byzantine robustness in federated learning is important.\n- The paper is well-organized and easy to follow.\n\nWeaknesses:\n\n- (FATAL) Collapse under a particular attack. Let $g$ be the benign gradient and e be all one vector. Craft the byzantine gradients to be $g+\\alpha e$, where $\\alpha$ is an arbitrarily large number. Since $g+\\alpha e$ and $g$ are the same in the ranking space, this attack can easily compromise the proposed MANDERA.\n- Limited theoretical analysis. Only show the robustness of proposed MANDERA under some specific Byzantine attacks.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "BFQzrSJgMZ", "reviewer": "Reviewer_HdfK", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a new ranking based method to detect Byzantine agents that participate in federated learning. MANDERA is a novel method that is intuitive and easy to implement, and show good performance in experiments. The authors also provide theoretical analyses to support that MANDERA is guaranteed to detect all Byzantine agents under certain conditions, and analyze 4 specialized attack instances. ", "summary_of_the_review": "This paper propose a novel method with good analysis blocks and effective experiments results, but from my perspective, it lacks in the theoretical arguments to guarantee Byzantine robustness as I detailed in \"weakness\" section. I think this paper can be improved towards a very good paper if more blocks are added, but the current form is limitedly persuasive. ", "strength_and_weaknesses": "Strength: \n1. The proposed method is very effective in experiments with performance matching or even outperforming some existing methods (Figure 7b). \n2. The analyses of ranking based method is valuable that provide insights on why MANDERA works well in high-dimensional or large datasets regime. \n\nWeakness: \n1. The considered attack is essentially not Byzantine attack as claimed, the distinguishable distribution assumption make the attack model much more restrictive in that there are attacks [1] that have similar distributions with benign nodes but can prevent the optimization process from convergence to optimum. \n2. Another problem is how to measure the amount of distinguishability is not discussed. In what cases the clustering algorithms can detect those malicious node is not discussed. \n3. Per the previous two points, there are gaps towards to the Byzantine robustness guarantees. We know that MANDERA is robust to some restricted class of attacks, but not general Byzantine attack, some attacks that fall into this class are analyzed. We know that asymptotically there will be two clusters, but we don't know in what cases these two clusters will be correctly labelled. In conclusion, there are interesting blocks in the analysis part, but the presented arguments are not enough to obtain any Byzantine robustness guarantees.\n4. In Figure 7b, why there are only two methods compared for GA and MS cases? The proposed method is good, but it seems that it does not outperform Bulyan in all cases.\n\n[1] Baruch, G., Baruch, M., & Goldberg, Y. (2019). A little is enough: Circumventing defenses for distributed learning. Advances in Neural Information Processing Systems, 32. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject