MANDERA: Malicious Node Detection in Federated Learning via Ranking
Authors: Wanchuang Zhu
Benjamin Zi Hao Zhao
Simon Luo
Ke Deng
Venue: ICLR 2022 Submitted (2022)
Keywords: Federated Learning
Data poisoning attack
Byzantine attack
Malicious node detection
Ranking

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 assembling the update gradients from local nodes into a ranking matrix that encodes the relative rankings of the outputs of all local nodes in different parameter dimensions, MANDERA 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 MANDERA is further confirmed by experiments on two classic datasets, CIFAR-10 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.

Under review as a conference paper at ICLR 2022
MANDERA: MALICIOUS NODE DETECTION IN FEDERATED LEARNING VIA RANKING
ABSTRACT
Federated Learning is distributed learning paradigm which seeks to preserve the privacy of each participating node's data. However, federated learning is vulner- able to attacks, specifically to our interest, model integrity attacks. In this pa- per, we propose a novel method for malicious node detection called MANDERA. By transferring the original message matrix into ranking matrix whose column shows the relative rankings of all local nodes along different parameter dimen- sions, 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 mali- cious nodes under typical Byzantine attacks with no prior knowledge or history about the participating nodes. The effectiveness of the proposed approach is fur- ther confirmed by experiments on three classic datasets, CIFAR-10 10, FASHION- MNIST and MNIST. Compared the state-of-art methods in the literature for defending Byzantine attacks, MANDERA is unique in its way to identify the ma- licious nodes by ranking and its robustness effectively defense wide range of attacks.
INTRODUCTION
Federated learning (FL) has observed a steady rise in use across plethora of applications. FL departs from conventional centralized learning by allowing multiple participating nodes to learn on local collection of training data, before each respective node's updates are sent 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 local data is not communicated to the global coordinator, and 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 per- formance of the global model, to reduce the output performance of the model (Chen et al. 2017] Fang et al.) 2020; Tolpegin et al. 2020b), dasaryan et al. (020). Byzantine attack aims to devastate the performance of the global model by manipulating the gradient values of malicious nodes in certain fashion. As these attacks emerged, researchers seek to defend FL from the negative impacts of these attacks.
to embed hidden back-doors within the model (Bag-
In the literature, there are two typical defense strategies: malicious node detection and robust learn- ing. Malicious node detection defenses by detecting malicious nodes and removing them from the aggregation (Blanchard et al. 2017 Guerraoui et al., 20188) Li al.) 2020 So et al. 202T) l). Robust learning (Blanchard et al. 2017 Yin et al. 2018 Guerraoui et al. 2018 Fang et al. 2020 Cao et al.)
2020), however, withstands 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, focus on defensing Byzantine attacks via malicious node detection. In the literature, there have been a collection efforts along this research line. Blanchard et al.) (2017) propose a defense referred to Krum that treats local nodes whose update vector too far away from the aggregated barycenter as malicious nodes and precludes them from the downstream aggregation. Guerraoui et al. (018) propose Bulyan, process that performs aggregation on subsets of node

---

Under review as a conference paper at ICLR 2022
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 predefined number of nodes with the highest SDS in the aggregation. On the other hand, Chen et al. (202T) propose a zero-nnowledge 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 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 principled way.
In this paper, we propose to resolve this critical problem from a novel perspective. Instead of work- ing 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, 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.
Global Model
Rejact- Malicious Updele
Rank Node Parameters
Compute Rank Mean
Find and reject nodes In malicious cluster
MANDERA
Aggregate and Update Global Model with benign cluster
then. Cluster
Mean
Figure I: An Overview of MANDERA
The contributions of this work are follows. (1) We propose the first algorithm leveraging the rank domain of model updates to detect malicious nodes (Figure D (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 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.
DEFENSE FORMALIZATION
2.1 NOTATIONS
Suppose there are n local nodes in the federated learning framework, where ny nodes are benign nodes whose indices are denoted by I, and the other no = n M1 nodes are malicious nodes whose indices are denoted by Im. The training model is denoted by f(0, D). where 0 e 1 is 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 E RT*p, where M,,- denotes the message received from node i. For benign node i, let D, be the data matrix on it with N, as the sample size, we have M
O.). A malicious node j E Imm however, tends attack the learning system by
00
2

---

Under review as a conference paper at ICLR 2022
manipulating M,. in some way. Hereinafter, denote N min min((NN)ez,) be the minimal sample size of the benign nodes.
Given vector of real numbers perm(1,... .P), where the ranking operator Rank maps the vector a to its permutation
_ define its ranking vector as b Rank(a)
space (1. p} which is the of all the permutations of {1, p). For example, Ron -,,11,,-22.... 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 ranking matrix R by replacing its column M. by the corresponding ranking vector j Rank(M..) Further define
1 P Σ
- e
and
R - =2)²
be the mean and variance of R.... respectively. As it shown in later subsections, we can judge whether node i is a malicious node based on E4) under various attack types. In the following, we will highlight the hehaviour 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.
2.2 BEHAVIOUR OF BENIGN NODES
As the behaviour of henign nodes does not depend on the type of Byzantine attack, we can study the statistical properties of (et, U²) for benign node In before the specification of concrete attack type. For any benign node i, the message generated for jth parameter is
Of(0,
M.
00,
where D denotes the 1th sample on it. Throughout this paper, we always assume that Da. are independent and identically distributed (IID) samples drawn from data distribution ID. Under the independent data assumption, since Equution Ittlls us that Mc, is the sample mean of IID random variables. i.e., { ( D..)) N.
80; 1=11 directly applying the Strong Law of Large Numbers (SLLN) and
Central Limit Theorem (CLT) leads to the lemma below immediately.
D..). 80; and of
Lemma 1. Under the independent data assumption, further denote Py BB(
Var 20,
((.) < oo, with N₂ going to infinity we have for V jE (1,.....)) ,p]
Mi. My a.s. and M 4 (ui of/N.)
2.3 BEHAVIOUR MALICIOUS NODE UNDER THE GAUSSIAN ATTACK
Definition 1 (Gaussian attack). In Gaussian attack, the attacker manipulates malicious nodes to send Gaussian random messages to the global coordinator, i.e., {Mr,)ei.,, are independent random samples from Gaussian distribution MVN(ms.. (m).s)))) Σ), where mb Eiet, Mi, and is the covariance matrix determined by the attacker.
Considering that M.j + μjj almost surely (a.s.) with N; going to infinity for all i Ia based on Lemma [ it is straightforward to see that lim.-- ms. = μy a.s., and the distribution of Mi, for the details.
each Imm converges to the Gaussian distribution centered at P.. Lemmappprovin
! with N going to infinity, have for each malicious node E Im under the Gaussian attack that
Lemma 2. Under the same assumption as in Lemma
M.j N (13, E5s), 15iSp.
(3)
Lemma I and Lemma tell us that for each parameter dimension j. (,, are independent Gaussian random variables with the same mean (i.e, (ız) but different variances (i.e..o. /N/N, or E,,r) under the Gaussian attack. Due to the symmetry of Gaussian distribution, it is straightforward to see
n
E( (RR,))
15 n, 15isp.
2
3

---

Under review as a conference paper at ICLR 2022
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 $b. and mm. such that
( = s..j ViE and Var(R = =s m.j. Vi E Imm
where both sb, and m. are complex functions of 0². Σg. and (N Further assume that R are independent of each other, thus e; = , ΣØ= R is the sum of independent random variables with a common mean. Thus, according to the Kolmogorov Strong Law of Large Numbers (KSLLN), know that e; converges converge some constant almost surely. The Theorem [
constant almost surely, which in turn indicates that e; also summarizes the results formally, with the
detailed proof provided in Appendix C
Theorem 1, Assuming { have for each local node that
are independent of each other, under the Gaussian attack, we
71 +
lim lim G
a.s.,
(4)
N 400000p-00
2
lim (v:- (0--8 I1(i E IT) N +00 p-000
lim
pm Ili E Imm) = 0.8.,
(5)
where I(() stands for the indicator function, 5 a 1 D - and sy - E3 s
Considering that $ = s2, and only E 's fall into a lower dimensional manifold whose mea- surement is zero under the Lebesgue measure, we have P s if the attacker specifies the Gaussian variance Σj. '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 e; and therefore pro- vides guideline detect the malicious nodes. Although the do need N and p to go to infinity for getting the theoretical results in Theorem []] in practice the malicious node detection algorithm based the theorem typically works very well when N and p are reasonably large and N;'s are not dramatically far away from each other.
The independent rank assumption in Theorem I which assumes that (Re.j hessp are independent of each other, may look restrictive. However, in fact it is mild condition that can be easily satis- fied in practice due to the following reasons. First, for benign node i E Ia. M.j and M often nearly independent, as the correlation between two model parameters 0, and 0g is often very weak in larger 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 2 via a histogram, which is very close to uniform distribution, indi- cating that M.j and M, are indeed nearly independent 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, as the final ranking Ra,; also depends on many other factors. Actu- ally, 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 theorems from the "almost surely convergence" to "convergence in probability"" but with no essential influence to the our algorithm below.
count
4000
2000
0.00
0.25
0.50
0.75
1.00
p.value
Figure 2: Independence tests for 100,000 column pairs randomly chosen from message matrix M generated from FASHION-MNIST data supports the independence assumption made in Theorem) T
2.4 MALICIOUS NODE DETECTION FOR SIGN FLIPPING ATTACK
Definition 2 (Sign flipping attack). Sign flpping attack aims generate the gradient values of malicious nodes by flpping the sign of the average of all the benign nodes' gradient at each epoch, iee. specifying M -rms, for any i Ima where m, mg EKEI, M
4

---

Under review as a conference paper at ICLR 2022
Based on the above definition, the update message of malicious node i under the sign flipping attack is
M = -
MR.-. REZ,
(6)
For fixed (MR,: MeI, Mi.; is also fixed vector without randomness, as it deterministic function of KEZ. On the other hand, however, we can also treat M., as a random vector, since the randomness of {M&. JREz, can be transferred to M via the link function in equation In fact, for any parameter dimension j. considering that Ma. 4 N (Di, /Nx. for any k E Io according to Lemma D it is straightforward to see that M. = ΣMEI, Mr. can also be well approximated by a Gaussian distribution. The lemma 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, = "n ΣkEz, Mg.j is deterministic function of [Ma.) whose limiting distribution when N goes to infinity is
Mr (x((((()) isisp.
of No
where (y(T) = -T of(r)
and No
m LNgI, N%
the harmonic mean of (N
Jand Lemma ttell us that for each parameter dimension j. the distribution of {M.s is a mixture of Gaussian components {N' of5, centered at Jıj plus point mass located at (r) = -THY- If N,'s are reasonably large, variances oī /N,'s would be very close to zero, and the probability mass of the mixture distribution would concentrate to two local centers Hj and (r(r) = -ryj, 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 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 (et, (e) for the benign and malicious nodes. The theorem summarizes the results formally, with the detailed proof provided in Appendix D
Lemmal D
Theorem 2. With the same independent rank assumption as posed in Theorem D under the sign flipping attack, we have for each local node i that
lim lim et
Nb I[i Ip] am I[(i E Im) a.s.,
(8)
- 7-000
lim lim Us = ot DiIliE E Ib) + 52 Ili E Im) a.s.,
(9)
- 80000
where Ps n+ nop. Fm +1p+ 2a+1, p p
E 20, p
2n and Si are both
quadratic functionn of p whose concrete form also depends on no and n1.
Considering that Tt, J.m if and only if
and ot = s if and only if is the solution of
quadratic function, the probability of (ūs, xg) = (Jm, 52, is zero p - co. Such phenomenon suggests that we can detect the malicious nodes based on the moments (e,, v,) to defense the sign flipping attack as well. Noticeably, we note that the limit behaviour of and 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 Mr, shrinks to zero with N; goes to infinity for each benign node i, any different between μ4 and (r(r) would result in the same rank vector R. in the rank domain.
realize that with the variance of
2.5 MALICIOUS NODE DETECTION FOR ZERO GRADIENT ATTACK
Definition 3 (Zero gradient attack). Zero gradient attack aims to make the aggregated message to be zero, i.e., Σn= M..- 0, at each epoch, by specifying M,:- = mb.; for all i E I,m-
Apparently, the zero gradient attack defined above is a special case of sign flipping attack by speci- fying r 21 Since the conclusions of Theorem 2 keep unchanged for different specifications of as we have discussed, we have the following corollary for zero gradient attack.
no.
Corollary 1. Under the zero gradient attack, e and U, follow exactly the same limiting be- haviours as described in Theorem
5

---

Under review as a conference paper at ICLR 2022
2.6 MANDERA
Theorem I 2 and Corollary T Iiply that, under these three attacks (Gaussian attack, zero gradient attack and sign flipping attack), the first two moments of R,,., i.c., (es, 04), converge to two different limits for the benign nodes and the malicious nodes, respectively. Thus, for a real dataset where Nt's and p are all finite but reasonably large numbers, the scatter plot of {(e,, 0,) uy)hgin would demonstrate a clustering structure: one cluster for the benign nodes and the other cluster for the malicious nodes. Figure 3 iillssrates such a scatter plot for the 100 local nodes in typical epoch of training the DUSHION-MNISS dataset under different FL settings (to keep the two dimensions of the scatter plot to the same scale, replaced 22 by its square root s; =Vo instead). Clearly, simple clustering procedure would detect the malicious nodes from the scatter plot. Based on this intuition, we propose MAlicious Node DÉtection via RAnking (MANDERA) to detect the malicious nodes, whose workflow is detailed in Algorithm
Algorithm 1
Malicious node detection via ranking (MANDERA)
Input: The message matrix M.
1: Convert the message matrix M to the ranking matrix R by applying Rank operator.
2: Compute mean and standard deviation of rows in R, i... si)hiis
3: Run the clustering algorithm K K-means to { {ee si)lisign with K = 2, and predict the set of benign nodes with the lager cluster denoted by It.
Output: The predicted benign node set Ip.
Remark. MANDERA can be applied to either a single epoch or multiple epochs. For 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-concutenation 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 Ia obtained by MANDERA naturally leads to an aggregated message mh, #(2,) EiEt, M,.-. The theorem 3 shows that Ig and m, lead to consistent estimations of In and my respectively, indicating that MÄNDERA enjoys robustness guarantee (Steinhardi, 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 lim Ptt = ==)= =1
and
lim lim Bllmss: ms = 0.
(10)
N p-00
N p-000
The proof of Theorem can be found in Appendix
EXPERIMENTS
We evaluate the efficacy in detecting malicious nodes within the federated learning framework with the use of three Datasets. The first the FASHION-MNIST dataset (Xiao et al. 2017), dataset of 60,000 and 10,000 training and testing samples respectively divided into 10 classes of apparel. The second CIFAR-10 10 (Krizhevsky et al. 2009). a dataset of 60,000 small object images also con- taining 10 object classes. The third is MNIST (Deng) 2012) 2) dataset which appears in Appendix H In these experiments we mainly adopt implementations of Byzantine attacks released by (Wu al, 2020b a) and the label flipping attack (Tolpegin et al. 2020b a). The label flipping attack is 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, attacker may change the labels of their local car images to be labelled as dogs. We use the Label Flipping attack as a comparative poisoning attack that achieves its objective in more subtle manner. In our experiments, the Gaussian attack and r = 3 for the sign flipping attack, where I is the identity matrix. For all experiments we fix
set Σ 30I for
100 participating nodes, of which 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 A
3.1 ILLUSTRATION OF THE AVERAGE RANKING AND STANDARD DEVIATION OF RANKING
Section g speculated that the distribution of parameter ranks differ sufficienlly for the detection of malicious and benign nodes. We validate this hypothesis in Figure by illustrating the difference

---

Under review as a conference paper at ICLR 2022
oddettyp
Benign
Malicous
30
35-
35
30-
v
31-
Mean
Figure 3: The scatter plots of (et, 8:) for the 100 nodes under four types of attack as illustrative ex- amples demonstrating ranking mean and variance from the 1st epoch of training for the FASHION- MNIST dataset.
Metric
Actursty
Accuracy
3.00
0.75
0.75
0.25
0.25
1.00
0.75
0.75
0.25
0.25
Sco99
0.00
0.00
1.00
0.75
0.75
LEN
0.25
0.25
1.00
1.00
0.75
0.75
0.50
0.25
0.25
20152222399
101552025 90 1015
1015202530
101552025300
2015 10 20:5 10 Number of maliiiuu nades
100152025.0
Number malicious nodes
(a) CIFAR-10
(b) FASHION-MNN MNIST
Figure 4: Classification performance of our proposed approach MANDERA (Algorithm under four types of attack for CIFAR-10 and FASHION-MNIST data. Gaussian Attack (GA); Zero- Gradient (ZG); Sign-Flipping (SF); and Label- (LF). The boxplot bounds the 25th (Q1)
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-Q1) and Q3+1-5(Q3-Q1 respectively.
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 that, that, under Gaussian and Label flipping attacks, the average rank- ings of malicious nodes are of a similar distribution to benign nodes. It is problematic for distin- guishing between the two types of nodes, if only average ranking information used. On the other hand, Figure displays larger separation of distributions for the standard deviation of ranking. It is noted that all 4 attacks observe convergence the distributions the number malicious nodes increase, increasing the difficulty of defense for both MANDERA and all other defenses. How- ever, the likelihood of an attacker controlling increasingly large numbers of malicious nodes also decrease.

---

Under review as a conference paper at ICLR 2022
3.2 MALICIOUS NODE DETECTION BY MANDERA
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 set of gradients from a single epoch. Each configuration epochs, with 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).
training
While we have formally demonstrated the efficacy of MANDERA in accurately detecting poten- tially 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 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 poisoming attacks) [ We also test other clustering algorithms, such as hicrarchical clustering and Gaussian mixture models (Fraley & Raftery] 20022. It turns out that the performance of MANDERA is quite robust with different choices of clustering methods. Detailed results can be found in Appendix
From Figure 4. it is immediately evident that the recall of the malicious nodes for the Byzantine at- tacks is exceptional. However, occasionally benign nodes have also been misclassified as malicious under SF, and to 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 LF, it is consistently more difficult to detect, however note that the LF attack has a more subtle influence on the model in contrast to the impact of Byzantine attacks.
3.3 MANDERA FOR DEFENDING AGAINST POISONING ATTACKS
In this section, we encapsulate MANDERA into module prior to the the aggregation step. MAN- DERA has the sole objective of identifying malicious nodes, and excluding their updates from the global aggregation step. Each configuration of 25 training epochs, given poisoning attack, defense method, and a given number of malicious nodes repeated 10 times. We compare MANDERA against 5 other robust aggregation defense methods, Krum (Blanchard et al. 2017) D. Bulyan (Guer- raoui 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 only aggregate robustly.
Defence
Eugan
FiTue
Delence
Dalyan
Trin-mann MANDERK
Medion
IVADERA
Nedos
53-
11-
13
boaddd de
dhddd da Socdh di da io
Numberal Ejoch
Number of Epech
(a) CIFAR-10 Dataset
(b) FASHION-MNIST dataset
Figure 5: Model Accuracy at each epoch of training, each line of the curve represents different defense against the poisoning attacks.
From Figure 5 it is observed that MANDERA performs about the same as the best performing defense mechanisms, close the performance of model not under attack. MANDERA's accuracy
'More informed approaches to selecting the malicious cluster can be tested in future work. E.g. Figure displays less variation of rank variance in malicious cluster compared to benign nodes. This could robust. selection of the malicious group, and enahling selection of malicious groups larger than 50%.
8

---

Under review as a conference paper at ICLR 2022
is observed to vary slightly under the LF attack fashion data with 30 malicious nodes, this is consistent with the larger accuracy ranges previously observed in Figure 4b) Interestingly, FLTrust as 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 FL.Trsst complementary defence that relies on base method of defence against Byzantine attacks, but expands the protection coverage of the FL system against adaptive attacks.
3.4 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 at the core of the algorithm. Sorting and Ranking algorithms are fast. Additionally, we only apply clustering 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|[oor 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 single Nvidia Tesla P100. Table I demonstratte that MANDERA is able to achieve faster speed than that of single Krum (by more than half) and Bulyan (by an order of magnitude).
the two dimensions of rank
Table I: Mean and standard deviation of computational times for defense function given the same set of gradients from 100 nodes, of which 30 were malicious. Each function was repeated 100 times.
Defense (Detection)
Meun SD (ms)
Defense (Aggregation)
Mean # SD (ms) 3.96 = 0.41
MANDERA
643 $ 8,646
Trimmed Mean
Krum (Single)
1352
10.09
Median
9.81 * 3.88
Bulyan
27209
233.4
FLTrust
= 4.07
DISCUSSION AND CONCLUSION
If attackers create more adaptive attacks unlike Definition I 2 and 3. they may evade MANDERA
and achieve model poisoning. In this work, we have configured Federated Learner 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 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 & 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 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 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.
The use of multi-krun krum would have yielded better protection (c.f. Section at the hehest of speed.

---

Under review as a conference paper at ICLR 2022
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 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 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 independent each other.
REFERENCES
Eugene Bagdasaryan, Andreas Veit, Yiqing Hua, Deborah Estrin, and Vitaly Shmatikov. How to backdoor federated learning. In International Conference Artificial Intelligence and Statistics, pp. 2938-2948. PMLR, 2020.
Peva Blanchard, EI Mahdi EI Mhamdi, Rachid Guerraoui, and Julien Stainer. Ma- chine learning with adversaries: Byzantine tolerant gradient descent. In I. Guyon,
U. V. Luxburg, S. Bengio, H. Wallach, Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Asso- ciates, Inc., 2017. URL http:::/pprooeeednnss... newriis.....r.ppp..p...... http::ss...ppp..ccpppp.eeeeee wwtpppppee/11//iieee..e (4b9cc30ad96611Bb2333 htt.:///......1100000272262222--
Xiaoyu Cao, Minghong Fang. Jia Liu, and Neil Zhenqiang Gong. Fltrust: Byzantine- feder- ated learning via trust bootstrapping. arXiv preprint arXiv:2012.13995, 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, volume 35, pp. 3885-6893, 2021.
Yudong Chen, Lili Su, and Jiaming Xu. Distributed statistical machine learning adversarial set- tings: Byzantine gradient descent. Proc. ACM Meas. Anal. Comput. Syst., 1(2), December 2017. doi: 10.1145/3 URL httph:
Zheyi Chen, Pu Tian, Weixian Liao, and Wei Yu. Zero knowledge clustering based adversarial mitigation in heterogeneous federated learning. IEEE Transactions on Network Science and En- gineering, 8()):1070-1083, 2021. doi: 10.1 10.1109/INSEE.22000002222
Li Deng. The mnist database of handwritten digit images for machine learning research. 1EEE Signal Processing Magazine,
2012.
Minghong Fang, Xiaoyu Cao, Jinyuan Jia, and Neil Gong. Local model poisoning attacks to byzantine-robuss federated learning. In 29th {USENIX) Security Symposium (!USENIX) Se- curity 20), pp. 1605-1622, 2020.
Chris Fraley and Adrian E Raftery. Model-based clustering, discriminant analysis, and density estimation. Journal of the American statistical Association, 97(458):61 1-631, 2002.
Rachid Guerraoui, Sébastien Rouault, et al. The hidden vulnerability of distributed learning in byzantium. In International Conference Machine Learning, pp. 3521-3530. PMLR, 2018.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Suyi Li, Yong Cheng, Wei Wang. Yang Liu, and Tianjian Chen. Learning to detect malicious clients for robust federated learning. arXiv preprint arXiv:2002.002. 0220000.002..... 2020.
Hsiao- Ying Lin and Wen-Guey Tzeng. An efficient solution to the millionaires' problem based on homomorphic encryption. In International Conference on Applied Cryptography and Network Security, pp. 456-466. Springer, 2005.
10

---

Under review as a conference paper at ICLR 2022
Jinhyun So, Başak Güler, and A. Salman Avestimehr. Byzantine- resilleet secure federated learning. IEEE Journal on Selected Areas in Communications, 19(7):218821188 2021. doi: 10.1 JSAC.2020.3041404.
Jacob Steinhardt. Robust learning: Information theory and algorithms. PhD thesis, Stanford Uni- versity, 2018.
Vale Tolpegin, Stacey Truex, Mehmet Emre Gursoy, and Ling Liu. Data poisoning attacks against federated learning systems- github.
FL., 2020a.
Vale Tolpegin, Stacey Truex, Mehmet Emre Gursoy, and Ling Liu. Data poisoning attacks against federated learning systems. In European Symposium on Research Computer Security, pp. 480- 501. Springer, 2020b.
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-mniss a novel image dataset for benchmark- ing machine learning algorithms. 2017.
Cong Xie, Sanmi Koyejo, and Indranil Gupta. Zeno: Distributed stochastic gradient descent with suspicion-basee fault-tolerance. In International Conference on Machine Learning, pp. 6893- 6901. PMLR, 2019.
Cong Xie, Sanmi Koyejo, and Indranil Gupta. Zeno++: Robust fully asynchronous sgd. Interna- tional Conference on Machine Learning, pp. (0495-10503. PMLR, 2020.
Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartlett Byzantine-robust distributed learning: Towards optimal statistical rates. In International Conference on Machine Learning, pp. 5650-5659. PMLR, 2018.
Lan Zhang, Xiang- Yang Li, Yunhao Liu, and Tacho Jung. Verifiable private multi calli-pprtt computa- tion: ranging and ranking. In 2013 Proceedings IEEE INFOCOM, pp. 605-609, IEEE, 2013.
A NEURAL NETWORK CONFIGURATIONS
We train these models with a batch size of 10, SGD optimizer operates with learning 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 * 16 5, 2D Convolution, Batch Normalization, ReLU Activation, Max pooling.
Layer 2: 16*32+5, 5, 2D Convolution, Batch Normalization, ReLU Activation, Max pooling.
Output: 10 Classes, Linear.
A.2
CIFAR-10
Layer 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.
11

---

Under review as a conference paper at ICLR 2022
B METRICS
The metrics observed in Section 3 to evaluate the performance the defense mechanisms are de- fined as follows:
TP
Precision
TP+FP TP+IN
Accuracy TP*FP+NN+IN
TP TP+FN
Recall
Precision X Recall
F1 2
Precision+Recall
C PROOF OF THEOREM
1
Proof. Because (Riss are independent random variables with finite upper bound (since is fixes) as assumed, direct application of KSLLN leads to
R E(R.,))) = a.s.,
(11)
p-000
j=1
lim p-200
(R., B(Ri,)) Var Var(R..))
00 a.s..
(12)
To prove Theorem based and Var Var(R.,).
Equation 11 and 12 need to derive the concrete form of E B(R,,))
Fortunately, because M.j 4 M(j,, Ens) for V Im and M.j 4 N for V E Is when No - cc, it straightforward to see due the symmetry of Gaussian distribution that
lim B(R,,) n 1 isis n, i N
(13)
2
Moreover, assuming that the sample sizes of different benign nodes approach to each other with N going infinity, i.c.,
lim max NN - No1 = 0, N +00 N LKEZ,
(14)
for each parameter dimension j. (M.shee. would converge to the same Gaussian distribution of,,,,/NN) with the increase of N Thus, due to the exchangeability of [Ma,hez. and Miee.emmm. it is easy to see that there exist two positive constants sf and s such that
lim Var (ar(R.,) of I(i Ib) = I(i Imn).
(15)
where sf and 2 mm.j are both complex functions of no. n1, o3. Ejj and N and 2b,5 = =mm if and only if of ///NN
Ejj- Eyj-
Combining Equation 11 and we have
lim lim +00
lim lim Σ Ri, 2 O.S., No 7000 p
71 ++1
i.e., Equation 4, which further indicates that e; and E(R.;) share the same limit when both p and N go to infinity. Thus, have
lim lim
lim lim N00 100
Ri,j - -s)²
No0 +oc
j=1
P
lim
lim
(Rij E(Ri)))² a.s..
(16)
N0 po
12

---

Under review as a conference paper at ICLR 2022
Combining Equation 12
15 and
16 we have
lim N p-oc
lim (v:
s $ I(i
-I(i Im)) 0 a.s.,
i.e., Equation 5
Thus, the proof is complete.
D PROOF OF THEOREM
Proof. It is straightforward to see that equation I also holds for sign flipping attack under the But, we need to re-calculate B(R,,)) for benign and malicious nodes
assumptions of Theorem 2 under the new setting.
Under the sign flipping attack, because Mij 4 ((Hs()))3(r)) for A i Im and Mis 4 of,,,03/N) for i Ia when N - 30, and
lim (o3/Ni) N
lim N
o)(r)= =
it is straightforward to see that
lim P(Mi) > MR,) 104 > 0) vi In. v k Im.
N -
which further indicates that
= M1 +
n1 n 11 +
lim B(R,,)
[[i Ib) +
I(e E Im) if H4 >0,
N *000
2
(17)
lim B(Ri,) 72g +
n n no +1
Il(i Imm
1li E Iτ) if H4 < <0;
N $00000
2
lim B(R = S mm)
1li Is) + 2 pl+
1li E Im) if μj > 0,
N
(18)
lim BBR2,,) = Sp.mml I[i Im) + s2 [ooti,)
1l(i E In) if μj < 0,
N' 200
where 52 [[,,b]
I k=a k22
Combining Equation 11 and 17
have
a+ū++1 2
+ (1 - p). no+1 = am a.s., if E Imm
p.
lim lim ej N +000
(1 p) mtng+1 Tb a.s., if E Io.
p.
Ei 1(,)00)
where p limp-
i.e. Equation 8
P
Define f4 = Pm I(i Imm + pbb
I(i E Ip). Based on KSLLN, we have:
lim p-000
(R., - a.) E(R., - -1,)2 = 0 a.s..
As have proved in Equation 8 that
lim lim e; = Pa a.s., +00 70000
have
1 p
lim lim +00 D-+00 p
Σ
(Ri.j - - -E(Ri, p.) -
a.s.,
which implies that
1 Σ
F
lim
lim
oi lim lim
[Rij - =2
lim
lim
E E(R,, - p.:)2 a.s..
+00
- 1000 p j=l
No0 700
j=1
13

---

Under review as a conference paper at ICLR 2022
Considering that
lim lim
B - -as)
- ==1
lim lim
R( Ri 22,, + (mx)²)
p-000 N
[mm (Aim) 1l(i E Im) + [oo - (1b) -l(i IT),
where
p. S mmmm (1 - p) -p mo)
Fm = p. S (m1+1.0) + +(1 -(1pp) .S..no)
have
lim U/ Fm
(Am) 1li E Imm + [ī (fb) 1(i Ip).
+00 p-000
It completes the proof of |qquatiton 9 by specifying o 5. (m²))² and s², Fm (fim)²
E PROOF OF THEOREM 3
Proof. According to Theorem
1 2 and Corollary 1 when both N and p are large enough, with
probability I there exist (eb, Ub). (Em, Um) and d > 0 such that [[(es, ub) - (em, um)ll2 6, and
6 (1(e;, v;) - (es, 222l2 - for forvie Is and I1(e;, vz) - (Ems 4m um)ll S 2
for V vic E Im
2
Therefore, with reasonable clustering algorithm such as K-mean with K = 2, we would expect Σ, I. with probability 1.
Because we can always find > such that |M M3alle I for any node pair (i.j) in fixed dataset with a finite number of nodes, and ma. ma. when Io = Ig, we have
E| m mo. 1l2 < A PP. # Ib),
and thus
lim lim E ms. m2. 0. +00 9-000
It completes the proof.
L
F MANDERA PERFORMANCE WITH DIFFERENT CLUSTERING ALGORITHMS
In this section, Figure 0 demonstrate that the discriminating performance of MANDERA when hierarchical clustering and Gaussian mixture models used in-place of K-means for FASHION- MNIST data set remain robust.
G MODEL LOSSES ON CIFAR- AND FASHION-MNIST DATA
Figure 7 presents the model loss to accompany the model prediction performance of Figure previ- ously seen in Section
H MODEL PERFORMANCE ON MNIST DATA
In this section we replicate experiments that were previously performed 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 Coottains the comparative accuracy and loss when the different defenses are applied. Generally speaking, the observations previously observed continue hold for this dataset.
14

---

Under review as a conference paper at ICLR 2022
Metric
Accuracy
Recall
Precision
GA
ZG
SF
LF
0.75
0.50
0.00
1.00
0.50
0.25
Score
1.00
0.75
Precision
0.25
0.00
1.00
0.75
0.50
0.00
1015 20 20 10115202330
20
$ 10155025530
Number of malicious nodes
(a) Gaussian mixture model.
Metric
Accuracy
Recall
Precision
SF
1.00
0.50
0.25
0.00
1.00
0.75
0.25
Score
0.00
1.00
0.75
0.50
0.00
1.00
0.50
0.25
5 10152025300
20
10 20 25 30
10155222530
N Number of malicious nodes
(b) Hicrarchical clustering.
Figure 6: Classification performance of proposed approach MANDERA (Algorithm with other clustering algorithms under four types of attack for FASHION-MNIST data. GA: Gaussian attack; ZG: Zero-gradient attack: SF: Sign-flipping: and LF: Label-flipping. The boxplot bounds the 25th (Q1) 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+ Q3+1.5(Q3-QP) respectively.
15

---

Under review as a conference paper at ICLR 2022
Krum
Bulyan
Trim Trim-mean
FLTrust
Defence
-attack
Median
MANDERA
10
15
20
25
30
6-
4-
4.5
4.0
log(
2.5
3.2
3.0
2.6
3.1
2.9
2.7
2.5
20
10 is 25
10 iss
20 2
10 is 20 25d
1s
20
250
1s
20
20
Number of poch
(a) CIFAR-10
Krum
Bulyan
Trim
FLTrust
Defence
Natattack
Median
MANDERA
10
25
30
7.5
5.0
2.5
6
4-
22
log(Loss oss)
2
2.5
2.0
2.25
2.00
1.75
1.50
1.25
10
20
250
10
15
20
25
10 15
250 š 10 i's 25
10 20
25ó
10
20
Number of Epoch
(b) FASHION-MNIST
Figure 7: Model Loss each epoch of training, each line of the represents different defense against the attacks (GA: Gaussian attack; ZG: Zero-gradion attack, SF: Sign-flipping: and LF: Label-flipping.
16

---

Under review as a conference paper at ICLR 2022
Metric
Accuracy
Recall
Precision
F1
GA
SF
LF
1.00
0.75
Accuracy
0.50
0.25
0.00
1.00
0.75
Recall
0.50
0.25
Score
0.00
1.00
0.75
Precision
0.50
0.25
0.00
1.00
0.75
0.50
0.25
0.00
1015502530
1015202530
10 20
10
Number of malicious nodes
Figure 8: Classification performance of our proposed approach MANDERA (Algorithm) under four types of attack for MNIST data. GA: Gaussian attack: ZG: Zero-gradient attack: SF: Sign- flipping: and LF: Label-flipping The boxplot bounds the 25th (Q1) 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-Q1) and Q3+1.5((3--0) respectively.
17

---

Under review as a conference paper at ICLR 2022
Krum
Bulyan
Trim-mean
FLTrust
Defence
NO NO-attack
Median
MANDERA
10
15
20
25
30
100
75
50-
25
100
90-
80-1
Accuracy
70-
80
80
70
60
92-
88
10
20
25
3
10
15
20
10
1b
20
25
10
20
2
6
10
20
25
3
10
25
Number of Epoch
(a) Model prediction accuracy after defense
Krum
Bulyan
Trim-mean
FLTrast
Defence
NO -tack
Median
NANDERA
10
15
20
30
7.5
2.5
0.0-
22
log|Loss)
0-
1.5
0.5
0.0
-0.5
10
15
20
1s
20
2
d0
10
20
25
10
250
10
15
Number of Epoch
(b) Model prediction loss after defense
Figure 9: Model Accuracy and Loss for MNIST data each epoch of training, each line of the curve represents a different defense against the attacks (GA: Gaussian attack; ZG: Zero-gradient attack; SF: Sign-flipping; and LF: Label-flipping).
18


Reviews:
[{"review_id": "IcR8C7hASdD", "reviewer": "Reviewer_FjLC", "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": "The paper proposes to use ranking instead of numeric values to cluster the user's update in federated learning to find malicious nodes. The authors list several attacks and provide analysis of the different behaviors between benign nodes and malicious nodes.\n\nThe work is rather complete. The results, AFAIK, are correct and the experiments are solid. The writing is clear and easy to follow. I really enjoy the illustrations in the paper especially Fig 3 and 4.\n\nOn the other hand, I have several concerns about the methodology itself. Most importantly, the paper does give any formal robustness guarantee. The method is designed based on several known attacks. Because security should not be preserved via obscurity, if this method is applied in real-world applications, the attackers can construct targeted attacks against this approach. For example, in high-dimensional case, the attackers can insert contaminated records close to the benign ones but still deviate the model from converging. To achieve real robustness, theoretically strong robustness [1] should be proved so as to prevent most available attacks (even not known). Second, the method is also not compatible with secure aggregation which prevents cumulative protection.\n\nOverall, I do not think the paper is ready for publication until formal robustness guarantee is added.\n\n[1] Wang, Lun, Qi Pang, Shuai Wang, and Dawn Song. \"F2ED-Learning: Good Fences Make Good Neighbors.\"", "summary_of_the_paper": "The paper proposes to transfer the update matrix to a ranking matrix before clustering to detect malicious nodes in federated learning.", "summary_of_the_review": "I do not recommend acceptance because formal robustness guarantee is missing.", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "IDi1X-wJSiI", "reviewer": "Reviewer_5jZy", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "(+) The main strength of the paper lie in the novel introduction of using the rank domain in order to detect malicious nodes. All of the claims are properly supported and experiments and results are clear. \n\n(-) The weaknesses in the paper are in the number of datasets/attacks. Having more experiments on a larger range of datasets and attacks will support claims more. Additionally, the inclusion of a strong, recent Byzantine defense algorithm in the robust learning area, such as FLTrust, will also help show the performance against state-of-the-art robust learning defense algorithms. \n", "summary_of_the_paper": "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.", "summary_of_the_review": "This paper introduces a new perspective in Byzantine defense in comparison to typical robust learning defense or other detection defenses. While the algorithm and experiments done are relatively simple, the paper serves more as a starting point for research and application in the new domain. Claims are properly supported and the method's competitive performance compared to other methods is promising.", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "2dlrZP-0cmt", "reviewer": "Reviewer_4WMU", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "__Strong points__: The paper’s strengths are its novelty (both technical and theoretical), the nature of the problem it is attacking and its clarity.\n- The paper presents a novel technique and way to address the Byzantine attack problem in federated learning (which is a significant problem) by identifying malicious nodes. The actual technique of using the moments of gradient ranks is especially intriguing because of its simple elegance and great theoretical guarantees. The paper does a great job showing how using the first and second moment of ranks can distinguish certain nodes under attack from a theoretical standpoint. The paper also does an excellent job going beyond theoretical guarantees, which hold with large numbers of samples, to show that the proposed MANDERA technique also works in practice and as good as other state-of-the-art methods\n    - As more of a question, really, than a comment, but the assumption that the gradient ranks, $R_{:,j}$ , are statistically independent probably deserves some more questioning. I can appreciate that the paper shows that this is empirically so, with a few, limited examples, at the bottom of section 2.3, but is this always so at least for neural network models? And, if so, why?\n- The paper is well written with only a few typos in it (.i.e “week” instead of “weak” in the last paragraph of section 2.3). The figures are clear and it is very easy for a reader to understand both why the technique works and how it works. \n    - One area where the clarity could be improved is to provide a brief 1-2 sentence explanation of the label flipping attack in the first paragraph of section 3. All of the other techniques receive a much more robust explanation in the previous section with the theoretical grantees, so it would be good for the reader to better understand why that technique was used and what it is (at a high level).\n\n__Weak points__: The paper is, overall, a strong paper with very few weak points. Mostly, the paper leaves one wondering about future work that could build on what is established within the paper, most of which the paper does comment on. \n- For example, what about using more moments or combining rank statistics with other statistics of the gradient updates for more robust malicious node identification.\n- What about the use of a better clustering technique? Looking at figure 3 and then looking at the recall problems with SF, it seems like a better clustering technique could probably solve this problem.\n- As with other points, the paper does explicitly mention this in its ethics statement, but how would one design an attack to counter this defense?\n", "summary_of_the_paper": "The paper presents a novel technique for defending against Byzantine types of attacks on federated learning systems.  The paper presents both theoretical justifications for why the using moments of ranks of gradient updates works as well as empirical justification showing that it works in practice.", "summary_of_the_review": "I recommend accepting this paper, as it provides a novel technique with sound theoretical and convincing empirical justifications for attacking an important problem in the application of federated learning.", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This manuscript proposes a ranking approach to identify Byzantine agents in federated learning. Distinct from existing methods, the mitigation is implemented by computing ranks for each gradient, then computing rank statistics across agents. The primary intuition is that adversarial agents can be identified by examining these rank statistics.

There are three reviewers, all of whom agree that the method addresses an interesting and timely issue -- giving the growing interest in both Byzantine-robust learning and federated learning in the community. However, reviewers are mixed on the paper score -- with a strong accept a weak accept, and a strong reject. Common issues raised include the generality of the approach beyond the outlined attacks, 
Other issues brought up, but addressed in the rebuttal include some weaknesses in the evaluation and comparison to additional baselines. There is also an interesting discussion of using higher-order statistics, which does not seem to help the methods when evaluated by the authors. Nevertheless, after reviews and discussion, the reviewers are mixed at the end of the discussion.

The area chair finds, first, that the paper is much improved, and much more applicable in the updated form than in the original version. However, the area chair agrees with the reviewer who notes that the moniker "Byzantine-robust" implies the methods should be provably robust to worst-case adversaries, not only to a selected set of adversaries with pre-selected attacks. The specified setting may be too narrow for interest by the community. To this end,  the area chair suspects that the method may be robust to a more general set of attacks than noted -- working to outline sufficient conditions for robustness would significantly strengthen this work. The asymptotic nature of the robustness guarantees is also of concern.

An additional concern of the area chair is that the system setting investigated assumes gradient communication and IID data across devices. While this is not an issue on its own, the setting is closer to distributed learning than federated learning, where one generally communicates model updates, or model differences after multiple local updates, and not gradients. This difference can have a significant effect on robustness methods that depend on identifying benign vs. adversarial statistics of parameters. Non-IID data is also common in the federated setting, though this is less concerning, as robust methods for non-IID settings are only now emerging. A simple fix for this issue would be to rename the setting from "Federated" to "Distributed."

Authors are encouraged to address the highlighted technical concerns in any future submission of this work. The primary concern may simply be a naming issue (i.e., removing "Byzantine" might fix this concern. Nevertheless, taken together, the opinion of the area chair is that the manuscript is not ready for publication. Again, the area chair believes that many of the issues noted can be fixed, the paper can be strengthened, and this paper may be publishable with limited additional work.
Decision: Reject