Tesseract: Gradient Flip Score to Secure Federated Learning against Model Poisoning Attacks
Authors: Atul Sharma
Wei Chen
Joshua Christian Zhao
Qiang Qiu
Somali Chaterji
Saurabh Bagchi
Venue: ICLR 2022 Submitted (2022)
Keywords: federated learning
aggregation
security
untargeted model poisoning attack

Abstract: Federated learning—multi-party, distributed learning in a decentralized environment—is vulnerable to model poisoning attacks, even more so than centralized learning approaches.  This is because malicious clients can collude and send in carefully tailored model updates to make the global model inaccurate. This motivated the development of Byzantine-resilient federated learning algorithms, such as Krum, Trimmed mean, and FoolsGold.  However, a recently developed targeted model poisoning attack showed that all prior defenses can be bypassed. The attack uses the intuition that simply by changing the sign of the gradient updates that the optimizer is computing, for a set of malicious clients, a model can be pushed away from the optima to increase the test error rate. In this work, we develop tesseract—a defense against this directed deviation attack, a state-of-the-art model poisoning attack. TESSERACT is based on a simple intuition that in a federated learning setting, certain patterns of gradient flips are indicative of an attack. This intuition is remarkably stable across different learning algorithms, models, and datasets. TESSERACT assigns reputation scores to the participating clients based on their behavior during the training phase and then takes a weighted contribution of the clients. We show that TESSERACT provides robustness against even an adaptive white-box version of the attack.

Under review as a conference paper at ICLR 2022
TESSERACT: GRADIENT FLIP SCORE TO SECURE FED- ERATED LEARNING AGAINST MODEL POISONING AT- TACKS
Anonymous authors
Paper under double-bling boindd review
ABSTRACT
Federated learning multimmulaattttt party, distributed learning in a decentralized environment-is is vulnerable to model poisoning attacks, more so than central- ized learning. This is because malicious clients can collude and send in carefully tailored model updates to make the global model inaccurate. This motivated the development of Byzantine-resilien federated learning algorithms,, such as Krum, Bulyan, FABA, and FoolsGold. However, recently developed untargeted model poisoning attack showed that all prior defenses can be bypassed. The attack uses the intuition that simply by changing the sign of the gradient updates that the optimizer is computing, for a set of malicious clients, a model can be diverted from the optima to increase the test error rate. In this work, we develop TESSERACT-a defense against this directed deviation attack, state-of-the-art model poisoning attack. TESSERACT is based on our intuition that in federated learning. certain patterns of gradient flips indicative of attack. This intuition is remarkably stable across different learning algorithms, models, and datasets. TESSER ACT assigns reputation scores to the participating clients based on their behavior during the training phase and then takes a weighted contribution of the clients. We show that TESSERACT provides robustness against even white-box version of the attack.
INTRODUCTION
Federated learning (FL) Smith al. (2017); Yang al. (2019) offers a way for multiple clients on heterogeneous platforms to learn collaboratively without sharing their local data. The clients send their local gradients to the parameter server that aggregates the gradients and updates the global model for the local clients to download. FL can be attacked during the training phase by compromising set of clients that then send maliciously crafted gradients. The attack can targeted against particular data instances or can be untargeted. The latter brings down the overall accuracy by affecting all classes. To counter this threat, set of approaches has been developed for countering Byzantine clients in FL, e.g. Krum Blanchard et al. (2017), Bulyan Mhamdi et al. (2018), Trimmed Mean and Median Yin et al. (2018), FoolsGold Fung et al. (2020), and FABA Xia et al. (2019). In this work, we use the state-of-fe ffte-offtheear the-hrt- art (SOTA) untargeted model poisoning attack called a directed deviation attack, proposed recently in Fang et al. (2020). This has been shown to bypass all existing Byzantine-rone -rouutt aggregation techniques, e.g., Krum, Bulyan, Trimmed mean, and Median. In our experiments, this attack has been found to decrease the test accuracy from 90% to a low 9% when a DNN is trained using Krum on the MNIST dataset, distributed among 100 clients, 20 of which are under the attacker's control. We describe the relevant details of this attack in Section 2.2.
Our solution. We propose novel defense called TESSERACT against untargeted model poisoning attacks (Figure 1), which uses a stateful model to reduce the contributions by suspicious clients to the global model update. We show that where all prior Byzantine-resilien federated learning approaches fail against the directed-deviatioon attack of Fang et al. (2020), which is the state-of-the-an untargeted model poisoning attack, TESSERACT able to recover the test accuracy of the trained model. This benefit applies even when the attack knows the algorithm and all the parameters of our defense, iee. an adaptive white-box attack. TESSERACT is based on a simple intuition that for a sufficiently small learning rate, the model approaches an optima in a benign setting, a large number of gradients do not flip their direction with large magnitudes, that is, a degree of inertia is maintained. Our intuition is supported from the analysis we propose, called - flip-score, which is the sum of squares of gradient magnitudes of all parameter updates that suggest flip in the gradient direction from the previous global update. We find that
show in Figure 2. We capture this quantitatively in metric that

---

Under review as a conference paper at ICLR 2022
TESSERACT
VLM,
VLM
VLM
VLM
Global model
m2
md
Client,
Client wd
Client
Client mx
Client mnd
Data
Data
Data
Data
Data
Figure 1: TESSERACT's architecture where c out of m clients may be malicious and send carefully crafted values of their local models to throw the global model off convergence. TESSERACT weights the gradients, received from the clients, by their reputation scores before aggregation, (see varying and thicknesses arrows from the clients.)
our intuition and correspondingly the defense TESSERACT also holds for other attacks, e-g., the targeted and untargeted label flipping attacks (Appendix A.3). However, the other attacks less damaging, consistent with the observation Fang et al. (2020). Thus, in the main paper, we focus on the directed deviation model poisoning attack.
DNN+MNIST, full-trim, m=100, c=20
(a) MNIST, full-trim, m=100,
0.175
Malicious
Malicious
Benign
Benign
0.500
0.125
Flip-score
Flip-score
4
0.100
0.075
0.500
0.025
1
200
Iteration
200
300
400
Iteration
(a) Only Benign updates aggregated
(b) Only Malicious updates aggregated
Figure 2: The average flip-score of malicious and benign clients over time for motivating experiment where DNN trained MNIST for 500 iterations (80 benign, 20 malicious clients). (a), only benign updates were aggregated using FEDSGD, and in (b), only malicious updates were aggregated, depicting the two extreme cases of federated learning in a malicious setting. These results show that when the global model update is benign, the malicious clients send gradients with high flip-scores to deviate the model from convergence. However, when the global model update itself was poisoned, the benign clients send high flip-score gradients for recovery whereas the malicious clienty maintain the direction of the adready-poisone model. Thus intuition is too high flip-scores and low flip-scores a coordinated manner are red flags.
In summary, TESSERACT makes the following contributions. 1. We use our simple intuition to detect malicious clients that attack federated learning using the SOTA attack model Fang et al. (2020). Our intuition is that certain patterns of flips of the signs of gradients across multiple model parameters and across multiple clients are rare under benign conditions.
2

---

Under review as a conference paper at ICLR 2022
2. We use stateful suspicion model to keep the history of every client's activity and use that weighting factor in the aggregation. We theoretically prove the convergence of TESSERACT that uses the weighted averaging and establish a convergence rate.
3. We evaluate TESSERACT on DNNs trained on MNIST and FEMNIST, ResNet- on CIFAR- 10, and GRU on the Shakespeare dataset. We comparatively evaluate our defense against six base- lines, including the most recent ones, FABA Xia et al. (2019), FoolsGold Fung et al. (2020), and FI.Trust Cao al. (2020) and show that TESSERACT remains robust even against an adaptive white-box attacker. While several of the existing defenses shine under specific configurations (combination of attacks and datasets/modells, TESSERACT is the only one whose protection trans- fers well across configurations. We release the source code, the attack scripts, the trained models, and the test harness for the evaluation at the anonymized page ht https:: /www. dropbox. com/ sh/h9ul fulw w y2 f 222 AADe 1 wwwpshhhhhgghee gg 2g24xvvJa?dd2 The rest of the paper is organized as follows. We describe in See the threat model, the SOTA attack, and why all existing Byzantine-resilient federated learning approaches are susceptible. We present TESSERAcT'S design in See 3 and convergence analysis in Sec 4. We describe the baselines and the datasets in Sec 5, and evaluation in Sec 6.
2 BACKGROUND
Our simulation of federated learning consists of m clients, each with its own local data, but with the same model architecture and SGD optimizer, out of which c are malicious, as shown in Figure 1. The parameter server assumes that maximum of Cmoz number of clients can be malicious. The clients run one local iteration, send their gradients (in unencrypted form) to the server, which updates the global model for the clients to download in synchronous manner.
2.1 BYZANTINE- RESILIENT FEDERATED LEARNING
Here we describe the leading defenses briefly, stymied by SOTA untargeted model poisoning attacks. 1. The simplest aggregation technique is FedSGD McMahan et al. (2017) that does simple weighted mean aggregation of the gradients, weighted by the number of data samples each client holds. FedSGD can be attacked by a single malicious client that can send boosted gradients.
2. Trimmed mean and Median Yin et al. (2018) aggregate the parameters independently, where one trims Cmaa each at the lower and higher extremes of every parameter and the other takes the median of every parameter update across the gradients received from all the clients. The full-Trim attack Fang al. (2020) is specifically designed toward these aggregations rules.
3. Krum Blanchard et al. (2017) selects one local model as the next global model. The client that has the lowest Euclidean distance from its closest (m Cmaz - 2) neighbors chosen as the local model. The full- -rum attack Fang et al. (2020) is tailored to attack Krum.
4. Bulyan Mhamdi et al. (2018) combines the above approaches by running Krum iteratively to select given number of models, and then running Trimmed Mean over the selected ones. The Full-Trim attack is also transferable to Bulyan.
5. FABA Xia et al. (2019) iteratively filters out models farthest away from the mean of the remaining models, Craa number of times before returning the mean of the remaining gradients.
6. FoolsGold Fung et al. (2020) was motivated to defend against poisoning attacks by Sybil clones, and thus, it finds clients with similar cosine similarity to be malicious, penalizes their reputation, and returns a weighted mean of the gradients, weighed by their reputation.
7. FLTrust Cao et al. (2020) bootstraps trust in the clients by assuming that the server has access to a clean validation dataset, albeit small, and returns weighted mean of the gradients weighed by this trust. In our setting, we do not see a realistic method to access such as clean dataset, especially considering the non-iid nature of the local datasets at the clients.
2.2 THREAT MODEL: STATE- OHE-HE MODEL POISONING ATTACK
Our threat model consists of a scenario where an adversary compromises fraction of all clients participating in federated learning. We assume that the adversary also has access to the gradient vector sent by the benign clients to the server, and knows what aggregation algorithm the server is running. We focus on the SOTA untargeted model poisoning attack Fang et al. (2020)-a a directed deviation attack (DDA) bypassing all known defenses" ! To address generality (more details in Appendix
'Thee is no overlap between the authors of this current submission and of the SOTA attack Fang et al. (2020).
3

---

Under review as a conference paper at ICLR 2022
$ A.6.2), we have also evaluated TESSERACT on label-flipping attacks in Appendix $ A.3. The DDA changes the local models on the compromised worker devices. This change is done strategically (through solving constrained optimization problem) such that the global model deviates the most toward the inverse of the direction along which the benign global model would have changed. Their intuition is that the deviations accumulated over multiple iterations would make the learned global model differ from the benign one significantly.
TESSERACT defends against both variants of the DDA, one specialized to poison Krum (transferable to Bulyan, we call this the Full-Krum attack), the other specialized for Trimmed Mean (transferable Median, we call this the Full-Trim attack), respectively. We assume a holl-knowledge (white-box) attack where the attackers have access to the current benign gradients. They themselves compute the benign gradients on their local data as well, and thus estimate the benign direction as the average of all benign gradients. This value is stored in vector of size equal to the number of model parameters.
st., ))
sign(sum( (VLM(t,
where (t,,tt, the gradient updates of client
Full-Krum attack: Having estimated the attackers send gradients in the opposite direction, all with magnitude X, with some added noise to appear different but still maintaining a small Euclidean distance from one another. The upper bound of À is computed in every iteration as a function of m, m, [Pl, GM, -) v (t, + 1, where e out m participating clients are malicious, |P| the number of parameters in the global model G.M. X is then iteratively decreased until the attackers make sure (using a local estimate) that the parameter server would have chosen the attacked model, using the Krum aggregation technique.
Full-Trim attack: The Trim attack while following the same fundamental principle of flipping the gradient direction, attempts to skew the distribution of every parameter toward the inverse of the direction that (t,,j) suggests in order to attack a mean-like aggregation. It does so by randomly sampling gradient magnitudes from range that has been computed by the attackers, guaranteed to skew the gradient distribution of every parameter, without appearing as obvious outliers (which would be caught by a method such as Trimmed Mean). Therefore, the attacked gradients here look more diverse than those in the Full-Krum attack. Overall, both forms of the DDA smartly take advantage of the fact that none of the existing aggregation techniques looks the change gradient direction to identify malicious gradients in robust way.
This kind of an attack is an extremely likely scenario in a cross-device as well as cross-silo federated learning setting, (more details in Appendix & A. and needs to be defended against.
3 DESIGN
TESSERACT uses a reputation-based scheme to compute the aggregation weights of the participating clients. Reputation- Deputation-based schemes have been widely used in the literature. For example, Kang et al. (2019) and Zhang et al. (2012) make use of reputation score as an incentive mechanism for clients to remain in the system. Fung et al. (2020) and Awan et al. (2021) compute reputation score from the pairwise cosine similarity of the gradients between clients, Cao et al. (2021) does that by computing the cosine similarity of the client gradients with reference to trusted gradients calculated on a clean validation dataset at the server. We compute reputation-scont in a different way by using flip-score of the local gradients, as described below. TESSERACT assumes that maximum of (maa(< 2 clients can be malicious. It penalizes 20maz clients and rewards the rest in every iteration by an amount W(i, t) based their flip-score (described below) and updates their reputation score, where i is the client ID and L is time. We present the pseudocode in Algorithm 1.
((1 20max)
), if penalized.
w(i =
m
20max
if rewarded.
These values make sure that that the expectation of the reputation score of a client is zero if their flip-scores belong to a uniform random distribution (see Appendix A.,,, Also, this makes recovery difficult as the penalty value is higher than the reward as Graz < m 2 and allows us to be conservative. The reputation score of client i is initialized and updated as follows-
RS 0) = O. RS(i, t) = paRSii, 1) + W(i,t), t> 0.
4

---

Under review as a conference paper at ICLR 2022
where 0 S p4a I 1.0 is the decay parameter, and RS is the reputation score. A low Ma gives more importance to the present flip-score and high jaa gives significant importance to the past performance of client. This decay operation also helps cap the maximum and minimum reputation score (with pa < 1, for more details, see Appendix $ A.1). We normalize the reputation score using softmax to do weighted mean aggregation, but
can use this directly filter out the suspicious gradients and use an aggregation rule of one's ' choice. We halve the reputation score of every client if any of the values grows so large that the softmax operation causes overflow. This is motivated by the fact that the reputation score is cumulative quantity, and can potentially keep increasing with time in an unbounded manner.
Flip-score. We compare the present gradients VLM, + 1,) sent by local model i with the gradient
direction of the global model at time t, (6,-) sign(GMM GM 1,))). We define sco-score as the sum of square of the gradient magnitudes of all parameters that experience a change in their gradient direction, that is,
IP|-1 Σ
Ft, +
(VLM(( + (sig)( ( sg(t,))). ==0
(t
where P| is the total number of parameters in the model being trained. A low flip-score thus suggests that the gradient updates are approximately in the same direction as the previous iteration. In contrast, high flip-score suggests deviation from the previous update. This could mean either a large number of parameters have flipped direction, or a small number of parameters have flipped direction with large magnitudes, both. As observed in Figure 2, if the previous global update was benign, a malicious client will tend to have a high flip-score. However, if the previous update itself was poisoned, the flip-score of benign clients will be high and those of malicious clients will be low. Therefore, we penalize Cmax number of clients at either end of the current flip-score distribution, as also done by Yin et al. (2018). but we do this in the context of gradient values per parameter. This allows our system to have higher detection coverage irrespective of whether the global model was poisoned in one iteration or not. Since we allow redemption, and make sure that in a random penalization scheme, the expectation of reputation score of a benign node approaches zero, we do not unnecessarily penalize benign clients with low flip-scores. Also, since we do not use any hard threshold for detecting attacks, and identify only the extreme ends of flip-score distribution in every iteration as malicious, we do not prevent low scip-score moves. At the time of convergence, when most of the clients will favor low flip-score moves, such moves will be allowed even after ignoring the gradients at the extreme ends.
Algorithm 1 Federated learning with TESSERACT
Output: Global model G. + 1,-) Local model updates w = (LM((++1,))
Input:
Parameters: m, Cmaz. jdd
0: Initialize reputation (0) = for every client
1 Initialize global direction (0) to a zero vector
2 for every client i compute flip-score:
3: F. + - (vLM, 1,5)) (ssgg((VLM,(C +1 * 5 (t,
4: Penalize Cman clients on either end of spectrum as: RS(i, ++11 Pa -
20meau
6: Reward the rest of the clients as: RS( t
(i t) 26max
7 Normalize reputation weights: Wn = Σe EERS
,88
8 Aggregate gradients: VGM(
(1 1, wF
9 Update global direction: (t+++1) sign(vGM(L++1,
10: Update global model and broadcast: GM + (VM(t)))GGM(++))
4 CONVERGENCE ANALYSIS
We make the following assumptions on LMM, part of which are adapted from Li et al. (2020).
1. Assumption #1: LM2 are all I-smooth, that is, for all v and w, LM2(v) S (w) + (v
LVM + [ [lu - w|13.
5

---

Under review as a conference paper at ICLR 2022
2. Assumption #2: LM4 are all pu-strongly convex, that is, for all v and w. LM&(v) 2 LM&(ww)
(v - " (L) + Elle w
3. Assumption #3: Let c be sampled uniformly at random from the local data of the k th client, (wf, <
then the variance of stochastic gradients of each client is bounded, that is, E 4 LMMx (w)) ]|² < o for k m.
4. Assumption #4: The expected squared norm of stochastic gradients is uniformly bounded, that is,
E | (w,. < ) G for k m..m, and = O.. 1.
5. Assumption #5: Within K iterations, the reputation score of malicious clients drop at least by 8mal=
and reputation score benign clients increase at least by ooen. that is, |RS - RS mal 2 &mal and [RSten RS ben K
2 ōben, for t = - 1.
Assumptions #1 and #2 are standard and apply to 12-norm regularized linear regression, logistic regression, and softmax classifier. Assumptions #3 and #4 have been also made by Zhang et al. (2012); Stich (2018); Stich et al. (2018); Yu et al. (2019). In our problem setting, Assumption #3 claims that the gradient with a subset of local data is bounded from the gradient with whole batch for both malicious and benign clients. Assumption #5 claims that after every K iterations, our algorithm will have better ability to distinguish the malicious clients.
Following the Theorem 1 in Li et al. (2020), after simplifying for our case in which the clients communicate with the parameter server in every iteration, we derive this convergence (details in Appendix $ A.4). Let GM" and LM be the minimum value of G.M and LMx respectively, then:
2 122 7 +
L
1²² po + 6LL + SG2 + +G Σ Pk.o +
B[GM(w)z) - GM <
4 w| w w²ll)).
km
where I., Hu, G are defined above, 7 = ( 1}. 7 u(s+tj- T is the total number of iterations, e is the number of malicious clients, Pk.o is the initial weight for malicious clients. and r GM - Ex= Ps I.ME that effectively quantifies the degree of non-iidness according to Li et al. (2020). This shows that weighted mean aggregation is guaranteed to converge in federated learning. The converge speed is (++). The increase of number of malicious clients e increases the bound.
5 IMPLEMENTATION
We have simulated the federated learning on a single machine with a Tesla P100 PCIe GPU with 16GB memory, using PyTorch, with as many clients as can be handled by our machine. The data was distributed with a non-IID bias of 0.5 (default), except for Shakespeare where the data was distributed sequentially among the clients and FEMNIST where the data was distributed by the writer. In our simulation, all clients run one local iteration on a batch of its local data before communicating with the parameter server in a synchronous manner. The clients sample their local data round-robin manner, send their local gradients to the parameter server, and download the updated global model before running the next local iteration. The malicious clients attack every iteration of training, we assume: Cmaz-
Baselines and datasets. The baseline aggregation rules used are Krum, Bulyan, Trimmed Mean, and Median. We also compare TESSERACT with the recent defense techniques of FABA Xia et al. (2019), FoolsGold Fung et al. (2020), and FLTrust Cao et al. (2020). We evaluate TESSER ACT ACT on different datasets (Table 1). The DNN trained on MNIST has 2 conv layers with 30 and 50 channels respectively, each followed by a 2 x 2 maxpool layer, then by a fully connected layer of size 200, and an output layer of size 10. We use a constant learning rate, except for CIFAR-10 10 where we start with zero, reach the peak at one-fourth of the total iterations, and slowly get down to zero again. The CNN trained on the FEMNIST dataset follows the same network architecture as Caldas al. (2019).
EVALUATION
6.1 MACRO EXPERIMENTS
In Table 2, we compare the test accuracy achieved by various aggregation techniques in benign and malicious conditions. We do not claim to provide optimal model architectures that can achieve the best test accuracy, but we provide fair comparison of the all the defenses on the same model with the same training parameters. For Shakespeare, which is an NLP dataset, we report the test loss; for all others, we report test accuracy. The final reported test loss value does not capture the training dynamics, which can be observed in Figure 3 for the more damaging Full-K full-Krum attack. We have not shown the test loss curve for Krum aggregation because of the large loss values here,

---

Under review as a conference paper at ICLR 2022
Table 1: Datasets with the number classes (n.) and training samples (n.), the models and model parameters (P)), training rounds (n.), batch size (b), learning rate (lr), total number of clients (m), number of malicious ones (c), and decay parameter (1)) used in TESSERACT. variable learning rate, peaks at 0.1.
Dataset
Te
72
Model
b
Ir
MNIST
10
60k
DNN
0.27M
500
32
0.01
100
20
0.99
CIFAR-10
10
50k
ResNet-18
5.2M
2000
128
0.1*
10
2
0.99
Shakespeare
100
GRU
0.14M
2000
100
0.01
0.99
FEMNIST
62
805k
DNN
6.6M
2000
32
0.1
35
7
0.99
Table 2: Attack impact- Test accuracy for Directed Deviation model poisoning attacks (Full-Krum; Full- Trim), on different datasets with e/m 0.2. For the Shakespeare dataset, test loss has been reported. We verify the damaging impact of the Full-Trim altack on mean-like aggregations (FedSGD, Trimmed mean, Median) and Full-Krum attack on Krum-like aggregations (Krum, Bulyan). We also observe that the existing defenses FABA, FoolsGold, and FLTrust- seem defend against this attack in cases, and fail in others, whereas TESSERACT consistently shines in all cases.
Attack
Defense
Test accuracy (%) Test loss (only for Shakespeare)
MNIST+
CIFAR-I0+
Shakespeare+
FEMNIST
DNN
ResNet-18
GRU
DNN
None
FedSGD
92.45
71.17
1.62
83.60
TESSERACT
92.52
66.92
1.64
83.58
FABA
91.77
69.94
1.76
82.69
FoolsGold
91.20
70.71
1.63
83.80
FLTrust
87.70
68.08
1.62
82.72
Full- Krum
FedSGD
82.97
39.68
1.62
29.87
Krum
8.92
9.81
11.98
5.62
Bulyan
10.14
13.24
9.23
9,91
T ESSERACT
87.73
61.26
1.64
80.19
FABA
86.99
55.96
1.75
55.61
FoolsGold
47.12
42.28
1.63
0.07
FLTrust
82.50
65.25
1.67
79.53
Full- Trim
FedSGD
65.25
47.32
1.74
32.34
Trim
36.36
55.25
3.28
13.03
Median
28.37
50.54
3.30
45.6
AET
90.55
67.65
1.66
82.31
FABA
91.84
67.31
1.64
79.66
FoolsGold
91.61
69.24
1.66
83.09
FLTrust
34.20
64.23
1.68
79.28
but have pushed the results to Appendix $ A.3 in Figure 9. We see that TESSERACT is the winner or 2nd place finisher in 7 of the 12 cells (benign + two attacks x 4 datasets). This on the surface appears to be not very promising, till one looks deeper. The baseline protocols that finish first in one configuration fare disastrously in other configurations, indicating that they are tailored to specific attacks or datasets (whether by conscious design FoolsGold does creditably for the Full-Trim attack but is vulnerable against the Full-Krum attack. Averaging
artifact of their design). For example,
the configurations, it appears FABA is the closest competitor to TESSERACT. We observe that FABA, although performed well for e/m- 0.2, failed to defend when the number of attackers grew to c/ c/m- 0.3, evident from the results in Figure 3(b). We have used F-MNIST, Ch-MNIST, and Breast cancer Wisconsin Dataset here to show the effect on diverse datasets. As the number of attackers increases, the mean starts to shift more toward them. One false positive detection by FABA can cause it to trim out benign local update, which causes the mean to shift further toward the malicious updates iteratively, and fail. On the other hand, TESSERACT is guaranteed to defend against the attack long S Croaæ and 7 We find empirically (result not shown) that FABA degrades fast, and much faster than TESSERACT, when the fraction of malicious clients increases. Whereas FABA fails at c/m 0.3, show in Figure 7(a) that TESSERACT remains stable until c/m 0.45. We also show in Figures 7(b) and (c) that TESSERACT remains robust across wide range of non-IIID bias, that is 0.1 to 0.8. TESSERACT and FABA require estimate of the upper

---

Under review as a conference paper at ICLR 2022
FABA for c/m=0.3
Full krum attock on ERU trained on Shakespcore
1.0
Fecidll
TESSERACT
FABA
403
ILLLI
Test accuracy
0.6
3.0
0.4
0.2
13.
0.0
MNIST+
MNIIST+
FMNIST+
WDBC+ Ch MNIST+
0 250 300
120
1500 3250
1500
1730
2000
MUR
ONN
ONN
UR
ResNet-20
Figure 3: Left shows the test loss curve comparing TESSERACT with the benchmark aggregation algorithms against the Full- Kruu attack. We see that the attack generates sporadic spikes in training, best handled by TESSERACT, evident from its smooth test loss curve. Right shows the comparison of FA BA and TESSERACT across diverse datasets for c/m 0.3. FABA begins to fail with higher fruction of malicious clients, while TESSERACT remains robust.
Variation reputation weight. Full-krum DNN+MNIST
Table 3: Fraction of malicious benign clients allotted weights above 1e-4 averaged 500 iterations. The weakness of FoolsGold and FLTrust stems in part from the
Evergge repibation weight.
0.010
fact that they assign low weight to a significant fraction of benign clients for effective detection.
melicious
0.006
benign
Defense
Mal/
Benign
Full-
Full-
0.004
Ben
trim
krum
FoolsGold
Ahen
0.29
0.30
0.10
0.002
Amal
0.00
0.64
0.000
FLTrust
Bhen
0.48
0.45
0.49
0
20
Iteration
100
Amal
0.52
0.63
TESSERACT
Ahen
0.75
0.75
0.63
Figure 4: Clients' reputation weights against time with TESSERACT, with higher weights benign clients, as malicious ones tend to
Amal
0.00
0.08
bound of number of malicious clients, Cmar be known. FoolsGold and FL.Trust, on the other hand, make use of cosine similarity among clients, and with trusted cross-check dataset at the server, respectively, to identify suspicious clients. We have found that both of these techniques unnecessarily penalize many benign clients and assign them zero weight in order to conservatively defend against an attack, as can be seen Table 3. This can have a significantly negative impact on a practical system where one wishes to learn from data that the different clients hold locally. On the other hand, TESSERACT allows all clients to contribute to the global model update that do not have large negative reputation score. Figure 4 shows the evolution of the average reputation score of malicious and benign clients. When benign and malicious clients start from the same region, the weights of malicious clients decrease with time tending zero, while those of the benign clients increase with time.
6.2 ADAPTIVE ATTACK
Having shown the performance of TESSERACT against the above attacks, we proceed analyze an adaptive attack scenario, i.e., one where the attacker has full knowledge of TESSERACT. including the dynamic value of the cutoff flip-scores. Thus, at iteration + 1, the attacker knows Ftom (t) and F Shighh (t) beyond which the clients were penalized at iteration t. The Adaptive-Krum attack first computes the target malicious gradients at ++ 1, and if its flip-score goes above F'Shigt (t), reverses the attack on its less important parameters, i.e., parameters that would have had low magnitude updates without attack. It does this by replacing 5% of the attacked parameters, at a time, with their benign values until the flip-score is brought down to ensure stealth. Since the stealthy attack will be less powerful than the original intended attack, the global model will only be partially poisoned, and the attackers not expected occupy the lower spectrum of the flip-score. This has been verified
8

---

Under review as a conference paper at ICLR 2022
Adaptive attack DNN+MNIST
Adaptive attack on ResNet-13 18 +CIFAR-11
0.6
0.5
Text accuacyy
Text accuncy
0.
0.4
0.3
Adaptive-krum
Adaptive-trin
0.1
Adaptive trim
1500
Iterations
Rerations
Figure 5: Performance of TESSERACT against adaptive white-box attacks, specifically designed to attack TESSERACT, evaluated on MNIST and CIFAR-10. We observe significant improvement in test accuracy, compared to the base case impact of Full-Krum on Krum and Full- Full-Trim on FedSGD, as reported in Table 2.
in our experiments as well. All the malicious clients send these attacked parameters with some added randomness in order to support one other. We observe trade-off between stealth and attack impact in this case, as can be seen in Figure 5.
The Adaptive- <daptive-Trim Trim attack is smarter and collaborative attack. Its target is to generate attacked gradients vy. i = 0, 1, ... 1. It first computes the Full-Trim target attack for every malicious client Then, it initializes up to Hi and modifies until tn generates flip-score that is less than Fhiigh (t). Client
then updates its target attack from un to ui + (wo vn) in order to compensate for a sub-optimal attack created by i because of the flip-score-evasin constraint. Thus, client may not necessarily find a solution if the target grows and the constraints are hard to solve for. The attacker hopes that Σi=o U; Σi=o U; The performance of TESSERACT against this adaptive white-box attack is shown in Figure 5. We find that the adaptive attacks are not very effective against TESSERACT. The benign accuracy for the two datasets 92.45% and 71.17% This happens due to multiple reasons: 1) the attack loses in strength while trying to gain in stealth, 2) the attackers need not be allotted equal reputation weights, so the weighted sum of the attacked gradients v do not match with the weighted sum of the target attack u, 3) the flip-scor distribution dynamic, as can be seen in Figure 2, and changes from time to + 1, and when it decreases in consecutive iterations by a significant amount, the attackers can still be blocked.
We have also created more knowledgeable attacker, by modifying the above constraint with a weighted sum, weighted by the reputation scores. We have evaluated this attack in Figure 8 in Appendix A.3. TESSERACT is effective against this attack too, for reasons (1) and (3) given above.
DISCUSSION AND CONCLUSION
We have presented TESSERACT, a secure parameter server for federated learning robust to model poi- soning attacks. TESSERACT uses stateful algorithm to allocate reputation scores to the participating clients to lower the contribution of maliciously behaving clients. We define malicious behavior using metric, flip-score, which when very high low, captures attacks that try to divert the global model away from convergence. This makes TESSERACT robust defense, no matter when it is instantiated, although we recommend enabling TESSERACT right from the start. TESSERACT can also be used to just filter out clients based on their reputation, so that an aggregation of the user's choice can be used, We evaluate the benefits of TESSERACT compared to the fundamental FL aggregation FedSGD and state-of sate-off-hhe-rn defenses, namely Krum, Bulyan, FABA, FoolsGold, and FLTrust. We evaluate using full knowledge untargeted model poisoning attacks that have recently been found to be most damaging against FL. We find that different existing defenses shine under specific combinations of attacks and datasets/models. However, TESSERACT provides transferable defense with accuracy competitive with individual winners under all configurations. Further, TESSERACT holds up better than its closest competitor, FABA, when the fraction of malicious clients increases (beyond 20%). Finally, adaptive white-box attacker with access to all internals of TESSERACT, including dynami- cally determined threshold parameters, cannot bypass its defense. All of our evaluation is limited to synchronous setting with gradient encryption, gradient encryption is less relevant in

---

Under review as a conference paper at ICLR 2022
cross-device scenario due to its high computational overhead Zhang et al. (2020). However, these form logical avenues for our future work.
10

---

Under review as a conference paper at ICLR 2022
8 REPRODUCIBILITY STATEMENT
All the details for the datasets and models used along with the implementation of the adaptive attack is given in Section 5. To help with the reproducibility of the experiments, we make available all of our code, the trained models, the training hyperparameter values, and the raw results from our testing. These are all to be found at the anonymized link https: / /wwww dropbox. com/ sh h 9ul w6y2f8rzve uploaded as a supplementary file in the current submission.
AADe 1 sb 9PhhCI.qc wtg.cc/gclll74gxooo 1zg44xvvJa 2 =d1=0. The code has also been
REFERENCES
Sana Awan, Bo Luo, and Fengjun Li. Contra:
Defending against poisoning attacks in federated learning. In European Symposium on Research in Computer Security, pp. 455-475. Springer, 2021.
Eugene Bagdasaryan, Andreas Veit, Yiqing Hua, Deborah Estrin, and Vitaly Shmatikov. How to backdoor federated learning. In International Conference on Artificial Intelligence and Statistics, pp.
PMLR, 2020.
Peva Blanchard, Rachid Guerraoui, and Julien Stainer. Machine learning with adversaries: Byzantine tolerant gradient descent. In Advances in Neural Information Processing Systems, pp. 119-129, 2017. Krum paper.
Sebastian Caldas, Sai Meher Karthik Duddu, Peter Wu, Tian Li, Jakub Konečný, H. Brendan McMahan, Virginia Smith, and Ameet Talwalkar. Leaf: A benchmark for federated settings, arXiv preprint arXiv: arXiv:1812.01097, 2019.
Xiaoyu Cao, Minghong Fang, Jia Liu, and Neil Zhenqiang Gong. Fitrust: Byzantine-robust federated learning via trust bootstrapping. arXiv preprint arXiv:2012. 13995, 2020.
Xiaoyu Cao, Minghong Fang, Jia Liu, and Neil Zhenqiang Gong. Fltrust: Byzantine-robus federated learning via trust bootstrapping, Network and Distributed System Security Symposium, pp. 1-18, 2021.
Minghong Fang, Xiaoyu Cao, Jinyuan Jia, and Neil Zhenqiang Gong. Local model poisoning attacks to byzantine-robus' federated learning. In 29th USENIX Security Symposium (USENIX Security 20), Boston, MA, August 2020. URL https: /www. usenix. org/ conference/ useni wwanniisscurttyy htt.rcorrtttttepppeeeatatattoitt http///eeeeetttoteeeeeeeeeeeeeee
Clement Fung, Chris J. M. Yoon, and Ivan Beschastnikh. The limitations of federated learning in sybil settings. 23rr International Symposium on Research in Attacks, Intrusions and Defenses (RAID 2020). pp. 301-316, San Sebastian, October 2020. USENIX Assoccaaion.. ISBN 1-391-993133--8-- URL https:ttp// / /www. usenix
fung.
Jiawen Kang, Zchui Xiong, Dusit Niyato, Shengli Xie, and Junshan Zhang. Incentive mechanism for reliable federated learning: A joint optimization approach to combining reputation and contract theory. IEEE Internet of Things Journal, 1000:1470-11714, 2019.
Xiang Li. Kaixuan Huang, Wenhao Yang. Shusen Wang, and Zhihua Zhang. On the convergence of fedavg on non-iid iid data. In International Conference on Learning Representations, 2020. URL https:/ /ppenevieev net. / forum ? d=H..NNAVVED..
H. Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agüera y Arcas Communication-ffiicii learning of deep networks from decentralized data. In AISTATS, 2017.
El Mahdi EI Mhamdi, Rachid Guerraoui, and Sébastien Rouault. The hidden vulnerability of distributed learning in byzantium. In Proceedings of the 35th International Conference on Machine Learning (ICML), pp. 3521-3530, 2018. Bulyan paper.
Luis Muñoz-Gonzzleer Battista Biggio, Ambra Demontis, Andrea Paudice, Vasin Wongrassamee, Emil C. Lupu, and Fabio Roli. Towards poisoning of deep learning algorithms with back grac-ega optimization. arXiv preprint arXiv: 708.708.00000 08689, 2017.
Virginia Smith, Chao-Kas Chiang, Maziar Sanjabi, and Ameet Talwalkar. Federated multi-task learning. In Advances in Neural Information Processing Systems, pp. 4424 4434, 2017.
11

---

Under review as a conference paper at ICLR 2022
Sebastian U Stich. Local sgd converges fast and communicates little. arXiv preprint arXi:: 2018.
Sebastian U Stich, Jean-Baptiste Cordonnier, and Martin Jaggi. Sparsified sgd with memory. arXiv preprint 100.09100000799, 2018.
Qi Xia, Zeyi Tao, Zijiang Hao, and Qun Li. Faba: An algorithm for fast aggregation against byzantine attacks in distributed neural networks. In IJCI,, pp. 4824 4830, 2019.
Qiang Yang. Yang Liu, Tianjian Chen, and Yongxin Tong. Federated machine learning: Concept and applications. ACM Transactions on Intelligent Systems and Technology (TIST), 10(2):119, 2019.
Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartlett. Byzantinerrobust distributed learning: Towards optimal statistical rates. In International Conference Machine Learning, pp. 5650-5659. PMLR, 2018.
Hao Yu, Sen Yang. and Shenghuo Zhu. Parallel restarted sgd with faster convergence and less communication: Demystifying why model averaging works for deep learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 5693-5700, 2019.
Chengliang Zhang, Suyi Li, Junzhe Xia, Wei Wang, Feng Yan, and Yang Liu. Batcherypt: Efficient
homomorphic encryption for cross-silo federated learning. In 2020 {USENIX) Annual Technical Conference ( (USENIX) (ATC) 20), pp. 493 506, 2020.
Yuchen Zhang, John C Duchi, and Martin J Wainwright. Communication-efficcii algorithms for statistical optimization. In 2012 IEEE 51st IEEE Conference on Decision and Control (CDC), pp. 6792-6799 IEEE, 2012.
12

---

Under review as a conference paper at ICLR 2022
A APPENDIX
A.1 PENALTY AND REWARD VALUE
Penalty and reward selection. Our design policy penalizes 2cmaz out of m clients in every iteration. Considering a completely benign scenario, we want the expected value of the reputation score of client that has been penalized fraction of times to be zero, where
26maz Let client i be m
penalized en number of times in n iterations. There are (.i) ways to select the iterations where the client is penalized. After n iterations, the reputation score of client is given by:
RS = Σ m ti,
(2)
t=0
where W(it t) is sequence of penalty and reward over time. The expected value of this reputation score over all possible sequences E (en) is
B [[)
ni,
Hd t(i,t)
W(i
j
mm) + (r(1 -e)n
n
Hd n-t
(
cnn)
en
Our setting with r 26max and p 1 r makes the above quantity to be zero thus ensuring that its expected reputation score increment is zero. This proof assumes that it is random process through which (benign) clients generate their flip scores. Thus, if a subset of clients are penalized less than 20ams of times, they are expected to have net neutral reputation score.
m
Upper and lower bound of reputation score. From the above expression, it is obvious that if Ma = 0, -p < RS < r. When 0 < Ma < 1, the upper and lower bounds can be computed by assuming that a client was rewarded or penalized respectively in every iteration. Assuming that the number of iterations tends towards infinity, equation (1) forms an infinite geometric sequence, that can solved to obtain - S RS V I- should be noted that these reputation scores are normalized using softmax to compute the reputation weights. the absolute value of the lower bound is not large enough (if fud is set to be too small), then even after perfect detection, malicious client can still have significant reputation weight after softmax normalization. If jua is set to a value closer to 1, then the absolute value of the lower and upper bounds increase, bringing down the contribution of malicious clients to almost zero At the same time, redemption becomes difficult for a client in this case. This trade-off needs to be kept in mind when setting the decay parameter. We have used Ma- = 0.99 in our experiments in order to remain conservative and make recovery difficult for a client that has been penalized a lot of times. However, this a design parameter that the user can decide.
A.2 LABEL FLIPPING
The attack that we target, "the directed-deviation attack" has been shown to be the most powerful attack in federated learning Fang et al. (2020), and specifically claims to be more effective than state-of-the-art untargeted data poisoning attacks for multi-class classifiers, that is, label flipping attack, Gaussian attack, and back back-gradient optimization based attacks Muñoz-González et al. (2017). They show that the existing data poisoning attacks insufficient and cannot produce high testing error rate, not higher than 0.2 in the presence of byzantine- rrrbust aggregation techniques (Krum, trimmed mean, and median).
We observe that both state-off of the-art targeted and untargted label flipping attacks are not powerful enough on the CIFAR-10 and FEMNIST datasets and have neglible damage. The attacks do have some
13

---

Under review as a conference paper at ICLR 2022
Targeted label flipping attack ('1'>'7) on MNIST with m=100
Untargeted label flipping attack on MNIST with m=100
w
0.8
Test accuracy
0.6
accuracy
0.6
0.4
0.4
02-
Trimmed targeted flip, cm20
02
Trimmed mean, untargeted flip, C=
Tesseract, targeted flip. c=20
untargeted c=20
0
250
500
750
1000
1250
1500 1750
2000
250
500
750
1000
1250
1500
1750
2000
Iterations
Iterations
Figure 6: TESSERACT'S Performance against targeted and untargeted label flipping attacks on MNIST dataset. We observe that the attacks have some damage on the model, but Tesseract able to remedy this for both attacks.
1e1 auataay NNST Tul-Trmn ellact
9o Barign ic- 200 TESSERACT tee ancuraty on WhR
TESSERACT TAA.RRCTCCoSST. Toot BOOUFaCY NHST with Trin at3
Text
04-
03
cm Imslcouus cientsstttal)
34 05
bias
00
707-100 bias
Figure 7: Figure (a) shows the performance of TESSERACT on MNIST with increasing c. We see that TESSERACKS is stable across a large range and breaks only above c= 0.45 which is close to the theoretical limit of 0.5 Figures (b) and (c) show the test accuracy of TESSERACT with varying non-lID bias across 100 clients benign and malicious cases respectively. TESSERAC can be seen robust enough for a wide range of bias, 0.1-0.8, with a small dip test accuracy occurring at bias 0.9.
MNIST dataset distributed
damaging impact the MNIST dataset, but when TESSERACT is used, the damage is completely mitigated. Thus, we verify the claims from Fang et al. (2020) and show that TESSeR ACT's 's intuition general enough to counteract both the more powerful "directed-deviation attacks" and the weaker state-of-the-art data poisoning attacks.
A.3 ADDITIONAL EXPERIMENTS
Here, we provide additional evaluation of TESSERACT in two specific situations. We stress-test it first by subjecting
higher number of malicious clients find the breaking point of TESSERACT, when trained on MNIST dataset in the presence of Full-trim attack. We assume that the number of compromised clients is still not greater than Cmaz, and to that end, we set c = Cmaz- Since TESSERACT requires Cmar < we have swept upto 49 where m was fixed at 100. We observe in Figure 7(a) that TESSERACT is stable upto c/m = 0.45 whereas the rest of the defense techniques broke below e/m- 0.30 can be seen in Table 2 and Figure 3 with Cmaz set for all the defense techniques that require a knowledge of Cmax-
Figures 7(b) and (c) show the performance of TESSERACT MNIST dataset distributed among 100 clients with varying degrees of non-IIDness. We observe that, except for the extreme case of bias 0.9, TESSERACT remains exceptionally stable.
Here, we describe the mathematical formulation of the adaptive- Full-Krum attack finds a vector of gradients by solving optimization problem described in Fang et al. (2020), and every malicious client would send with an additional noise to appear different. Full- full-Trim attack solves different optimization problem also come up with vector of gradients to which every malicious
14

---

Under review as a conference paper at ICLR 2022
client i would add some noise to obtain u4- The problem statement in our (two) derived versions of the above (two) attacks, namely Adaptive- Trim and Adaptive Krum, is To find a set of vectors
U2 1 1,,1,2,...
where is the number of malicious clients. Here, v is the vector of gradients with size equal to the number model parameters, each satisfying the constraint
FS((;)) FSiggh (t)
that is, every computed vector should have flip-score lower than the cut-off flip-score according to the adversary's 's knowledge, such that
Σ 1/4 1==
Σ d L=
where u, were determined by the adversary originally as valid solution to the Full-Krum and Full-Trim optimization problems. We solve this problem as described in Section 6.2. In short, initialize e; to some target value, and then undo the attack on "less important parameters" until flip-score constraint is just met, and send the computed for aggregation. vo is initialized uo- and then updated until the fcip-score constraint is satisfied. The difference ug - 2 is added to u1 which now becomes the initial value of i1 and in Section 6.2.
The results have been described and analyzed
stronger attack where the adversary also has the knowledge of its reputation score (Wi) in order to come up with attacked gradients with better chances of success. We call this "Weighted-Adaptin -daitiie--pptmmm Trim" attack. The modified constraint
We formulate
Σ Wn,
Σ WR,::: 1=0
TESSERACT successfully defends against this attack when evaluated on MNIST, can be seen from the experimental result Figure 8. With TESSERACT ACT, the test accuracy reaches 90% while in the baseline case, it only reaches 58%. For context, without any attack, the model reaches accuracy of 92.45%.
Figure 9 shows the devastating impact of Full-Krum attack on Krum aggregation with the Shakespeare NLP dataset. This was not shown in Figure 3(a) because the abnormally high loss values makes the comparison between benchmarks with smaller loss values difficult. All defenses partially mitigate the impact of this attack, but the greatest benefit is obtained from TESSERACT.
A.4 CONVERGENCE ANALYSIS
Let the ke-th client hold ny training data batches: Tk,1, Tk. The local objective function LM₃ (-) is given by
n w: Fk.
LMg(W)
Tik 1=1
where I(::)) :) is the specified loss function for each client.
The global objective function is defined
GMa.e(w)- = Σ
Ph. (w))).
k=1
The global model is updated as
w
M
Pk.t PK.V VL.
where Pk. softmar(RSy.) : is the softmax of reputation score of client & at time t.
We update the weights by averaging the weights from selected clients convenience, we also define gi Em= Pk, VLM&(wf S ct), where gh is the selected local data.
Em w... For
15

---

Under review as a conference paper at ICLR 2022
-erip attack on DNN+
Full-krun full-krum attack on GRU trained on Shakespeare
FedSGD
FABA
Test accuracy
0.6
FLTrust
Test toss
20
15
M
02
10
TESSERACT- Weightte Adaptive-Trin Trim
Fed5GD
200
300
400
500
Iterations
250
500
750
1000
1250
1500
1750
2000
Figure 8: figure shows the test accuracy of TESSERACT when evaluated on MNIST dataset under the default conditions with m = 100, 20 where the adversary launches the Weighted-Adaptive- Trim attack on the system, compared with the baseline performance of FedSGD against Full-Trim attack. TESSERACT successfully defends against this attack to achieve 90% accuracy.
Figure 9: The figure shows the impact of the Full-Krum attack Krum aggregation the Shakespeare NLP dataset as compared to the other aggregation techniques. It has a devastating impact which is mitigated by all defenses and most effectively by TESSERACT shown in Figure 3(a).
A.4.1 ANALYSIS ON CONSECUTIVE STEPS
To bound the expectation of the global objective function time T from its optimal value, first consider to analyze the global weight from the optimal weights by calculating single step SGD:
W1+1 - 2 = We Thht w Thhh + ThDrell 1l
(3)
W w m:Gell 112 + 2m (w, W Thet, Et ge) + 7 9ell.
The first term of Equation. 3 can be expressed as
w w Vege 1|2 = w: w w'll 21p. (w. - w", ,..) + 11
(4)
The second term of Equation. 4 can be expressed
-21 (w. -w", ww" = 21/r Pk.t Pi.e(w w", VLM&(w
217
Pk.c Ph.c(We (W: w VLM)((
(5)
m
2m
(w w'. VLM& (w/))
By Cauchy-Schwarz inequuill and AM-GM inequality, have
Pk. W VLM&(W))) < 1 w w/ll + mell V
2nh
(6)
By the j-strong convexity of LMc(-), we have
m
27
Σ
(w. ww, ((,))) < -(LM&(w)) IM+(W")) 11 [I - (7)
w=1..
16

---

Under review as a conference paper at ICLR 2022
By the convexity of || and the L-smoothness of LM&(-), express third term of Equation. as
m
o/ 11:11 S m
Pk (w!)ll
< 2L Σ
( LMM)).
Combining Equations. 4 - 8, we have
W. w - < W - w=11 + 2LT Σ
PE. Pk. (LM, LME
k=1
m
Pk.el l w/ll V
17
k=1
27pe
PR, (r,,((LMMoow))) (.MM)(((WW(-MM(("))) 1 lw w=(13)
=(1 (1TT:))
w1 Σ Pa.el 2!11
+ 2L
(L.c(LMs( - LME) + ni
Σ
Pk.e V [ (9)
k=1
k=1
27j
Pr. IM&()"))
1=1
m pm:)) w1 +
<(1
Σ
Pa. Pe.el w/'l
AL
Pk.t P (MMx - LME
21p.
(LM((LM)(w)) LM",,")),
1=1
where the I-ssmoothness of T.Mx()) in the last inequality.
17

---

Under review as a conference paper at ICLR 2022
We 7/2 21 2Lm)), and the last two terms of Equation. are
Pk. (LMM((W)) LME) 21/
Σ
PL.((MM(( I.M((w"))
k=1
k=1
P - GM - 7t Σ I..
1=1
m
+ 2tje
(L,((LM((W) LMEE)
1=1
m
7
PE. (LM) GM - 7 pa. (GM -M
(10)
2m
(GM -MM)
7t
PE. (LM,(()) - GM*) + (2 7) Σ
PG. - LMH)
k=1
1=1
(LM2 - GM*) + 4LLIT
7x
k=1
where r -m km Pk. (GM - LMM) GM -E Pk.t LM
The first term of Equation. 10
m (w -GM))
(L.((LM((W)) - IW((W:)))+
(LM, - GM-)
Pk. (V.MM - + (LM. -GMM
(11)
Pk. (V.((VMM w/ w))) + GM((w) GM"
2 2 PM.( 1 L| w. w1ll3) GGM(W) GM
Σ (...C.
m
LMM) + 1 - GM GM",
2
27.
where the first inequality results from the convexity of LM&(-), the second inequality from AM-GM inequality and the third inequality from L-smoothness of LM, (.)-
18

---

Under review as a conference paper at ICLR 2022
Therefore, Equation. 10 becomes
Pho (LM((L - GM + AL
Tt
km
S
(LA. LME) + 27je
|w well
(GM((W. - GM 4T
PE. PLLLOn GM + 2/)t
1/ well?))
(12)
TTLT LI (W GM + 4LnLT
(1 1)
(IM( GM.)
m
7
PR. pr.ellw woll (4In) LD,,
217t
With (w,) - GM > and MeL < O, we have
m
Te L - 1) Σ PL.((LM((W.) -GM) S0,
(13)
and recall 7/ (1 2T,,e), so 2m
< 1 and 4Lah + + S 6Inţ.
Therefore,
17
m
Pk. Pr (LM((w)) 4L - Σ
pk. w w. + +6L
(14)
Thus, Equation. becomes
7
|w w Tegell < pmme w. 12 Σ
Pk.1 ww well 6L (15)
A.5 BOUND FOR VARIANCE GRADIENTS
Next, bound the gradient, using assumption have
E g::
E
Pk.t (VLMe(W?.e)) VLM{(W!))I
p E VLM VLM)(w}))'
(16)
<
o
k=
19

---

Under review as a conference paper at ICLR 2022
A.5.1 BOUND FOR DIVERGENCE OF WEIGHTS
Based on Assumption 5, for malicious clients k == 1.2....,... we have
Pk,t = softmaz(RSk
R.Sm
1 RS!
e km m6m
Lim ii Rs
5m m
Zimoti
CRS -86
(17)
e R
D i== c.S
+ Litot
ERS;
3 +66+
e RS M km
2i eRS
+ +i
e R
PR.--M-
To bound the weights, we assume within F. communication steps, there exists to < t, such that t to S E' I and w Wto for all k 1..,..., m. And we know TIe is non-increasing and
Nto I 2n. With the fact E|||X- | s E|| 12 and Jensen inequality, we have
m
E
pk.e We
11
E
p Wto w/'12
m
t-1
Σ (E- ( stI1
Pk.
tg
t-1
Pk.t E
E 1ymh G²
8g
PL. 1)2 G2
(18)
E(E 1)212 G² + Σ P(, - - G2
1
kmo+1
E(E 1)2 0² + -
Ph - 1)² + 41/ - 1)²
k=1
<4 PE 138
where Pk.o is the initial probability of kth malicious client.
A.5.2 CONVERGENCE BOUND
Combining Equation.(3) (166))))))) we have
W w 2 W w - - + (we - w - -1 91) + nnllā. gell2
m
<(1 pm:i)l - w + D
Pk.e Pl,:llw" - woll2 - =6L
(19)
1=1
+ 2np (W,- - w- - - Gr
ge) + rill.. -2
20

---

Under review as a conference paper at ICLR 2022
Since Big]] 9c. Therefore,
E| W Wi+1 - w" 11 <(1 HomeBB W. - w01 2E
Pk. w well + 6L
k=1
+ 2n:BB(w. -w" 71.r. 9r
(t) + Eni l1 -
<(1 um: W. - w Σ
Ph.on (E - 1) + +sn -E
k=1
(20)
+ +6L T + 1/2 Σ
Of
2
k=1
=(1 - Bl| We -w"ll w11
m 6 k=1
+ v 10
Σ o
We f/ 247
8 for some B and 7 > 0, such that m S min #.- I H and 1t. 2.
We want to prove W w" 12 I V
7++- where v = mar 8
8n-1 (7 + 1) W1 w [ and
B 8 Pho G2 8(E - 1) + 171 + Σ k= :
Firstly, the definition of e ensures that B| w- - w011 S オ Assume the conclusion holds for some t, we have
E We+1 w 5(1 1m
Wi w' n
Bu
V B²B
<(1
t t
t t+ 7
(t 71+
1+
B²
34
(21)
U (t+
(1 71+
(1+
V.
$ ++++1*
By the L-smoothness of G.((), E(G GM S BB|l w1
L
2 2777
Thus we have
2 L
m
Pk.o + 4
E[GM(WTT] - GM < 422
o
179 + SG2 + SG2 2
4 1|w0 - w=1 )1.)
7
T
A.6
ADDITIONAL COMMENTS
A. CONCRETE USE-CASE
A typical use-case would be a cross-device or cross-silo setting where a critical model is being learned, such as, mapping to a battlefield scenario by integrating sensor data from multiple sensors or a smart farms scenario to integrate data from multiple sensor nodes.
In sensitive setting, there could be malicious intent degrade the training process. Here an attacker could either compromise participating devices or join the training under multiple aliases. Having joined the network, could intercept the communication between benign clients and the server, or directly compromise the server to get access to the benign gradients in order to craft the malicious gradients. This constitutes a full-knowledge attack. Further, prior work has shown that even the partial knowledge attack can be quite damaging (in such attack, the adversary does not need to know the gradients the benign clients, but assumes its own before-attae gradients to be an approximate estimate of the benign gradients). With an approximate estimate of the benign gradients, is easy for an adversary to launch the prrected-deviation attack to start pushing the global model away from the optima until the goal of ofenial-of-service is achieved.
21

---

Under review as a conference paper at ICLR 2022
A.6.2 GENERALIZABILITY OF THE DEFENSE
We have demonstrated that TESSERACT achieves the goal of secure aggregation the presence of directed-deviation attacks, their adaptivewhiit--ox versions, as well targeted and untargeted label-flipping attacks. This is because the fundamental intuition behind TESSERACT based on the assumption that large flip-score is indicative of an attack. It should be noted that the primary objective of any untargeted model poisoning attack to push the global model away from the optima. attack will invariably push the model
Given the currently aggregated global model is benign, parameters in the opposite direction as the benign gradients, and would consequently generate large flip-score and get flagged. If the current global model itself had poisoned iteration, the attacked gradients will support the current direction in which the model was moving, and would generate low flip- scores while the benign gradients in Figure 2. Since, we trim out both the ends of the flip-score spectrum in a relative manner, we provide mechanism to defend against any untargeted attack.
would generate high values of flip-score, demonstrated
A.6.3 ACCURACY OF BASELINE FEDSGD MODEL
As in other federated learning- related security papers Fang et al. (2020); Fung et al. (2020); Bag- dasaryan et al. (2020), our goal was not necessarily to achieve the smallest error rates for the protocols the considered datasets as goal not to search for the most optimized DNN architecture. Instead, our goal was to demonstrate that the state-of-the-ar attacks can increase the testing error rates of the learned DNN classifiers and TESSERACT defense algorithms. Since all baselines and our solution are evaluated on top of the same trained model, therefore have a valid comparison base. Of course, we want DNNs to be reasonably
reverse the attacks better than the other
performant as ours are.
22


Reviews:
[{"review_id": "yhXJtXWOeJ", "reviewer": "Reviewer_4KHr", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "This submission presents a reasonable and timely defense against a strong attack against data poisoning in federated learning, which is nice. The design of the defense is well-executed and the inclusion of a dynamic reputation is a good addition to its robustness. I do have a few comments,  mostly regarding the part of the paper concerning adaptive attacks:\n\n* The submission discussses *an* adaptive attack against this defense, but I would like to understand and see more discussion on why this is a strong adaptive attack specifically. It is currently not clear to me that this is a strong adaptive attack. It seems that the attacker could mount a stronger adaptive attack by keeping track of its own reputation and send local updates are optimized under an additional linear constraint that includes its own reputation? It would be great if the authors could clarify my understanding in this matter.\n\n* How does this defense perform compared to the other considered defenses when the number of malicious clients is unknown? For example, assuming c_max is fixed to m/5, but the actually number of malicious clients is decreased from m/5 down to 1. This would be especially interesting to compare to defense algorithms that require no knowledge of c_max.\n\nAnd some minor comments and questions:\n* GM and LM are used in the text before the variables are formally explained\n* \"We halve the reputation score of every client if any of the values grows so large that the softmax operation causes an overflow\" -> I am surprised that this could even happen, given the sizes of m, n_r and mu?\n* page 7: \"here to how the effect on diverse datasets\" ->here to show the effect on diverse datasets\n* \"We find empirically (result not shown) that FABA degrades fast\" -> it would be better if the authors could include this result in their appendix (or clarify the sentence - I think a partial answer to this statement is contained in Fig3b?)\n* The caption of Fig.2 says \"(a) shows the results where only benign updates were aggregated using FEDSGD, and (b) shows the case where only malicious updates were aggregated\", but the figure headings say the opposite\n* For CIFAR-10 and Shakespeare only two clients are malicious, is the attack too strong to be mitigated if more malicious clients exist?", "summary_of_the_paper": "This submission with the title \"Tesseract: Gradient Flip Score to Secure Federated Learning against Model Poisoning Attacks \" discusses defenses against data poisoning in federated learning. The authors propose a novel defense against the recently popularized attack \"Tesseract: Gradient Flip Score to Secure Federated Learning against Model Poisoning Attacks \" by Yang et al. This attack reduces model availability by sending malicious updates from compromised client that maximize sign flips in the global model gradient. \nThis defense then proposes a measure of change in gradient direction that can be evaluated for each local update and used to dynamically down-weight clients with a large number of flips in direction. ", "summary_of_the_review": "In summary, I think this is a decent submission. I have some questions (the central one is the strength of the adaptive attack) which I would like to discuss with the authors and I am open to changing my evaluation accordingly.", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "wpnhJUNOfYX", "reviewer": "Reviewer_VCnh", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "I enjoyed reading the paper. In contrast to many research efforts on adversarial ML, this paper makes many security assumptions that set it apart with respect to the existing body of literature. I also praise the the consideration of attackers with varying “strength” and the different datasets. All these points make me lean to recommend acceptance.\n\nNonetheless, there are some issues that the authors could solve to further improve their paper. Let me elaborate on the above-mentioned weaknesses, starting from the most significant ones.\n\n**Assumptions and Threat Model?**\nThis is probably the only “true” problem of the paper, which should be absolutely rectified.\nI was not fully able to understand the assumptions made by Tesseract. Does it work “only” against the “directed deviation attack” proposed by Fang et al.? Or does it also protect against different attacks?\nIn general, Section 2.2, Threat Model, is not very comprehensive. The authors should better expand this section by clearly pointing out all the assumptions and requirements of the proposed method. This is especially true because the Fang et al. attack was proposed in 2020, and some of its assumptions are not yet well-known. Specifically, this statement is suspicious: “We assume a full-knowledge (white-box)\nattack where the attackers have access to the current benign gradients.”. Does it mean that Tesseract only works under this assumption? I.e., the attacker knows, and exploits, the current benign gradients? This is a rather “unrealistic” assumption: I understand the willingness to work against “worst case” scenarios; yet, if such “worst case” scenarios are not realistic in the first place, then what is the purpose of the proposed mechanism? What benefit is there in protecting against an attack that will never happen in the first place?\nI invite the authors to restructure this section by using the common taxonomies adopted in adversarial ML papers [I]. \n\n\n**Problem or Feature Space attacks?**\nThe authors perform their experiments on four well-known datasets: MNIST, CIFAR, Shakespeare, FEMNIST; for each dataset, a different (deep) ML model is targeted. Three of these datasets are of images, whereas Shakespeare contains text data.\nThere are different ways to create “adversarial examples”, depending on the ‘space’ where the perturbation is applied. As far as I am aware, the adversarial examples considered in this paper to perform the poisoned updates are created in the feature space. It would be a lot more interesting if at least one evaluation included adversarial examples generated in the “problem” space [A]—or, at the very least, considered samples generated by “physically realizable” adversarial perturbations [B]. I acknowledge that the method should work even in these circumstances, as the proposed Tesseract defense is agnostic of the process used to apply the perturbation. However, considering the strong relationship with (real) security that permeates the paper, I believe that a more convincing use-case would dramatically improve the quality of the paper. This is also motivated by the current state-of-the-art: after almost a decade of adversarial attacks, more recent efforts are leaning towards evaluation that consider more realistic circumstances, where the attacker is constrained by the limitations of the real world; this is even more true in “distributed system” scenarios, such as Network Intrusion Detection Systems, which bear a strong relationship with federated learning (e.g., [C, D, E, F]).\nAs such, I invite the authors to perform an additional “proof-of-concept” experiment where they consider adversaries with constrained capabilities. This is also motivated by the fact that some perturbations may yield different effects when created in the problem space (as shown in [A]).\n\n**Tradeoff?**\nA common problem in adversarial ML countermeasures is that they may degrade baseline performance [G, H]. Hence, I am interested in knowing how the proposed method responds when there are no “malicious” clients. Even if the baseline performance does not decrease, what is the overhead of the proposed method? For instance, in Table 2 the authors report some results for “Attack=None”, which I assume represent the accuracy when no attack takes place. However, all the rows of these experiments (namely, FedSGD, Tesseract, Faba, FoolsGold, FLTrust) consider hardening FL techniques; for instance, on MNIST the proposed Tesseract has an accuracy of 92.52 when no attack takes place—the best among all other defences. Despite being appreciable, I am interested in knowing the performance when NO defense is applied. Surely, the test accuracy in a “fully trusted” FL setting should be superior than 92.52. Hence, I ask: what is the ‘cost’ of Tesseract?\n\n**Lack of a concrete use-case.**\nI believe that the paper could be further improved with a concrete use-case, where the authors explain, step-by-step, how a (single, or multiple) attacker can compromise a federated learning system, and how the proposed method can help in solving such problem. Hence, I request the description of a concrete use-case explaining the abstract scenario reported in Figure 1. Such use-case can be at the basis of the “constrained” attack that I invite the authors to perform in my \"problem space perturbations\" suggestion.\n\n\n\n\n\nSome additional issues:\n\n•\tIn the Introduction, the authors state: “To counter this threat, a set of approaches has been developed for countering Byzantine clients in FL…”. I believe that “Byzantine Clients” is a wrong term: what is countered by Tesseract are not byzantine clients, but \"unloyal\" clients, that are “against” the byzantine clients (at least by referring to the well-known problem of the byzantine generals, which should agree on a method to reach consensus in the presence of unloyal generals).\n\n•\tThe caption of Figure 1 has a typo “c out of m clients maybe be malicious”.\n\n•\tIn Figure, the gradient “LM_{c-1}” is out of place. \n\n•\tIn Section 2, the authors state “Our simulation of federated learning consists of m clients, each with its own local data, but the same model architecture and SGD optimizer, out of which c are malicious, as shown in Figure 1”. Is there a minimum amount of “m”?\n\n•\tFigure 1 appears before Figure 2, but in the text it is referenced after Figure 2.\n\n•\tPutting Figure 2 so early on is very confusing. The “flip score” is a measure introduced for the first time in this paper. As such, any reader would be thrown off by such graphs before reading the paper, meaning that the findings of Figure 2 are difficult to interpret---during the Introduction---, as the flip score has not been defined yet. As such, such graphs are ultimately meaningless: I have to trust the authors that they correspond to “interesting” observations and “fair” experiments, which is not scientific.\n\n•\tThe presentation and notation in the “Flip-score” (page 5) is very ugly and difficult to follow.\n\n•\tSection 5 should be merged in Section 6\n\n•\tW.r.t. Table 2, the authors state “We see that TESSERACT is the winner or 2nd place finisher in 7 of the 12 cells (benign + two attacks * 4 datasets)”. This should be better highlighted. I only see three bold values for Tesseract in Table 2.\n\n•\tW.r.t. Table 2, the authors state “We have not shown the test loss curve for Krum aggregation because of the large loss values.”. I invite the authors to report such values in Table 2, because the different “formats” of the three subtables (None, Full-Krum, Full-Trim) make this table very hard to interpret.\n\n\n\nEXTERNAL REFERENCES\n\n[A]: \"Intriguing properties of adversarial ml attacks in the problem space.\" 2020 IEEE Symposium on Security and Privacy (SP). IEEE, 2020.\n\n[B]: \"Improving robustness of ML classifiers against realizable evasion attacks using conserved features.\" 28th {USENIX} Security Symposium ({USENIX} Security 19). 2019.\n\n[C]: \"Modeling Realistic Adversarial Attacks against Network Intrusion Detection Systems.\" ACM Digital Threats: Research and Practice. 2021.\n\n[D]: \"Constrained concealment attacks against reconstruction-based anomaly detectors in industrial control systems.\" ACM Annual Computer Security Applications Conference. 2020.\n\n[E]: \"Conaml: Constrained adversarial machine learning for cyber-physical systems.\" Proceedings of the 2021 ACM Asia Conference on Computer and Communications Security. 2021.\n\n[F]: \"Resilient networked AC microgrids under unbounded cyber attacks.\" IEEE Transactions on Smart Grid 11.5 (2020): 3785-3794.\n\n[G]: \"Adversarial example defense: Ensembles of weak defenses are not strong.\" 11th {USENIX} workshop on offensive technologies ({WOOT} 17). 2017.\n\n[H]: \"Deep reinforcement adversarial learning against botnet evasion attacks.\" IEEE Transactions on Network and Service Management 17.4 (2020): 1975-1987.\n\n[I]: \"Wild patterns: Ten years after the rise of adversarial machine learning.\" Pattern Recognition 84 (2018): 317-331.\n", "summary_of_the_paper": "The paper tackles the problem of adversarial attacks in federated learning settings. The main proposal is a defensive technique to address the “byzantine generals” problem in federated learning: how to ensure that the general ML model is not affected by “poisonous” attempts made by corrupted clients.\nThe proposed technique is experimentally validated on four datasets, outperforms previous defensive methods, and the evaluation also considers adaptive adversaries with increasing degrees of knowledge. \n\nOverall, the presentation of the paper is very good.\nThe quality of the English text is good.\nFigures are appropriate, Tables require some editing.\nThe topic addressed by the manuscript is trendy and in-line with ICLR’s scope.\nThe references should be improved\nThe contribution is significant\n\nSTRENGTHS:\n+ Adaptive adversary \n+ Trendy subject (federated learning)\n+ Evaluation on multiple datasets\n+ Technically sound\n\nWEAKNESSES\n- Unclear assumptions and threat model.\n- Problem or Feature space attacks?\n- Lack of a concrete use-case\n- Tradeoff?\n", "summary_of_the_review": "The paper tackles a very interesting problem and the many security considerations as well as the experiments on various datasets and comparisons with existing defenses are commendable.\n\nSome issues (unclear threat model, flexbile perturbations in the feature space) still prevent me from recommending complete acceptance. More clarifications are necessary, and by adding some more \"realistic\" experiments I believe that the paper could be turned into a significant submission of ICLR.\n\nI am recommending a \"5\", but my score can be easily increased to 6 by addressing the many clarifications expressed in my review. Further experiments and the concrete use-case would further increase my score.\n\n___\n\nAFTER REBUTTAL: score increased to 6 which I will increase additionally to 8 if the authors are willing to support the claim that Tesseract is a \"secure by design\" defense.\n\nFURTHER UPDATE: score increased to 8, and I stand by my decision unless other reviewers point out that the claim of Tesseract being \"secure-by-design\" is flawed.\n", "strength_and_weaknesses": "", "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": "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": "uiJwwhDd0U0", "reviewer": "Reviewer_YpRv", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "Pros:\na. The defense is based on an interesting observation that, for a sufficiently small learning rate, as the model approaches optima in the benign setting, a large number of gradients do not flip their direction with a large magnitude. And if such a behavior is observed it is indicative of an attack. The paper defines a Flip Score for every received gradient update and uses it to identify and either reward or penalize the update.\n\nb. The history of rewards and penalties for a client is maintained as a reputation score. Normalized reputation scores are then used to compute the global model for the next round (Algorithm 1).\n\nc. In addition to defending against the directed deviation attack, the paper also proposes two adaptive attacks (Adaptive-Krum and Adaptive-Trim) in which colluding attackers knowing the parameters of TESSERACT adjust their attack vectors to escape the cut-off flip scores.\n\nd. The paper provides a convergence analysis sketch and compares the performance of TESSERACT with a set of Byzantine Resilient defenses (Krum, Bulyan, Trimmed Mean and Median, etc.).\n\nWeaknesses:\n\n1. The paper proposes a defense against a specific form of attack and does not provide any guarantees or justification about why it should generalize against other more powerful forms of model poisoning attacks. On pg. 2, the paper argues (without justification) that other attacks are less damaging and essentially weaker than the attack in Fang et. al. However, one can argue that while the directed deviation attack, is designed to prevent model convergence, there are model poisoning attacks that not only insert targeted backdoors but also allow the model to converge (Bhagoji et. al., 2019: https://arxiv.org/pdf/1811.12470.pdf, Bagdasaryan et. al. 2020: https://arxiv.org/pdf/1807.00459.pdf). These attacks are thus more powerful and can also maintain stealth. \n\n2. While the authors provide two very interesting adaptive attacks, it is hard to generalize the strength of defense without any formal guarantees, In other words, can there be no other adaptive attack that can bypass this defense. For example, can an attacker target the reputation update mechanism over time?\n\n3. Typically, for reasons of privacy, the gradient updates are usually encrypted before being sent to the server (secure aggregation scheme by Bonawitz et. al. 2017, https://eprint.iacr.org/2017/281.pdf). TESSERACT in its current form will be difficult to implement with such schemes.\n\n4. In Fig. 2, both sub-figures are labeled (a) and there is an inconsistency between the sub-figure caption and the image caption. Figure caption describes (a) as an aggregation of benign updates and sub-figure caption describes (a) as an aggregation of malicious updates. Finally, the Flip Scores of the figures(y-axes) are very different, but what is confusing is that there are both benign and malicious clients in both. ", "summary_of_the_paper": "The authors propose TESSERACT, an aggregation scheme that is robust to the directed deviation attack (proposed in Fang et. al. 2020). ", "summary_of_the_review": "Please see the detailed comments above.", "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": "YC4MyCfW71W", "reviewer": "Reviewer_EZwJ", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "The strengths and weaknesses of this paper are summarized as follows:\nStrengths:\n+ The problem studied in this paper is important and needs to be solved in federated learning\n+ Good writing\n\nWeaknesses:\n- Need to include more related work that is highly important\n- Need more justifications about the novelty claims \n- Need to add some experiments under non-IID settings\n- Need to unify the attack paradigm\n- Insufficient theoretical analysis\n\nComments:\n1. The following important references are missing:\n[1] Kang J, Xiong Z, Niyato D, et al. Incentive mechanism for reliable federated learning: A joint optimization approach to combining reputation and contract theory[J]. IEEE Internet of Things Journal, 2019, 6(6): 10700-10714.\n[2] Awan S, Luo B, Li F. CONTRA: Defending against Poisoning Attacks in Federated Learning[C]//European Symposium on Research in Computer Security. Springer, Cham, 2021: 455-475.\n[3] Zhang J, Wu Y, Pan R. Incentive Mechanism for Horizontal Federated Learning Based on Reputation and Reverse Auction[C]//Proceedings of the Web Conference 2021. 2021: 947-956.\n2. The untargeted model poisoning attacks (i.e., Full-Krum attack and Full-Trim attack) designed in this paper are vague. It would be better if the authors could formally define these attacks. Second, the authors need to explain how these attacks in this paper differ from [4].\n[4] Minghong Fang, Xiaoyu Cao, Jinyuan Jia, and Neil Zhenqiang Gong. Local model poisoning attacks to byzantine-robust federated learning. In 29th USENIX Security Symposium (USENIX Security 20), Boston, MA, August 2020.\n3. The reputation-based techniques used in this paper are quite common and non-surprising. A lot of previous work (e.g., [1-3]) has used reputation-based techniques to mitigate the poisoning attacks. Therefore, readers may think that the authors just applied the reputation-based methods in federated learning. The authors need to provide more details to justify the novelty of this paper.\n4. There are some grammatical errors and inappropriate formula symbols in the context. For example, “k=1,2,…,m” should be “$k=1,2,\\ldots,m$.” \n5. The editorial quality of this paper is not always satisfactory. It contains quite a lot of inconsistent/non-precise descriptions, as also reflected in the above comments.\n6. Theorem 1 lacks rigorous proof and complete theoretical analysis. It would be better if the author could give complete proof of Theorem 1.\n7. The number of attackers has always been a very important hyperparameter (or factor) in model poisoning attacks. Therefore, it would be better if the authors could conduct more case studies to explore the influence of the number of attackers on different defense algorithms.\n8. In addition, non-IID data seems also to affect the gradient direction (or value) of the client. Therefore, the authors need to add some experiments to illustrate the effectiveness of the proposed algorithm under non-IID settings.\n9. In fact, the poisoning attack defended by the baselines chosen by the authors is different from the attacks designed in this paper. Then, it would be better if the authors tested the proposed defense method on the poisoning attack involved in the baseline schemes.\n10. In general, the authors need to add more theoretical analysis and verification experiments.\n", "summary_of_the_paper": "This paper studied a very important topic in the field of federated learning: how to efficiently resist untargeted model poisoning attacks. In order to defend against such a poisoning attack, the authors developed TESSERACT, an aggregation algorithm that assigns reputation scores to participating clients based on their behavior in the training phase and weights the client's contribution. Extensive case studies have verified the effectiveness of the algorithm. In particular, the experimental results show that TESSERACT provides robustness against even a white-box version of the attack. ", "summary_of_the_review": "For now, the authors need to add more theoretical analysis and verification experiments. The reason is that there are still unfair comparisons in the comparative experiments in this paper. If the author can address the reviewer’s comments, I will consider giving it a score of \"6\".", "strength_and_weaknesses": "", "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": {}}]

Author rebuttal:

Meta-review: The paper presents a defense against the gradient sign flip attacks on federated learning. The proposed method is novel, technically sound and well evaluated. The crucial issue of the paper is, however, that this defense is specific to gradient-flip attacks. The authors show the robustness of their method against white-box attacks adhering to this threat model and claim that "an adaptive white-box attacker with access to all internals of TESSERACT, including dynamically determined threshold parameters, cannot bypass its defense". The latter statement does not seem to be well justified, and following the extensive discussion of the paper, the reviewers were still not convinced that the proposed method is secure by its design. The AC therefore feel that the specific arguments of the paper should be revised - or the claim of robustness further substantiated - in order for the paper to be accepted.  

Furthermore, as a comment related to ethical consideration, the AC remarks that the paper's acronym, Tesseract, is used by an open source OCR software (https://tesseract-ocr.github.io/) as well as in a recent paper: Pendlebury et al., TESSERACT: Eliminating Experimental Bias in Malware Classification across Space and Time, USENIX Security 2019.

All of the above mentioned reservations essentially add up to a "major revision" recommendation which, given the decision logic of ACLR, translates into the rejection option.
Decision: Reject