summaries: 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. The proposed technique is experimentally validated on four datasets, outperforms previous defensive methods, and the evaluation also considers adaptive adversaries with increasing degrees of knowledge.   Overall, the presentation of the paper is very good. The quality of the English text is good. Figures are appropriate, Tables require some editing. The topic addressed by the manuscript is trendy and in-line with ICLR’s scope. The references should be improved The contribution is significant  STRENGTHS: + Adaptive adversary  + Trendy subject (federated learning) + Evaluation on multiple datasets + Technically sound  WEAKNESSES - Unclear assumptions and threat model. - Problem or Feature space attacks? - Lack of a concrete use-case - Tradeoff?  The authors propose TESSERACT, an aggregation scheme that is robust to the directed deviation attack (proposed in Fang et. al. 2020).  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.  This 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.  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. 
abstractText: Federated learning—multi-party, distributed learning in a decentralized environment—is vulnerable to model poisoning attacks, more so than centralized 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-resilient federated learning algorithms, such as Krum, Bulyan, FABA, and FoolsGold. However, a 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, a state-of-the-art model poisoning attack. TESSERACT is based on our intuition that in federated learning, 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 a white-box version of the attack.
references.authors: Sana Awan Bo Luo Fengjun Li
references.title: Contra: Defending against poisoning attacks in federated learning
references.venue: In European Symposium on Research in Computer Security,
references.authors: Eugene Bagdasaryan Andreas Veit Yiqing Hua Deborah Estrin Vitaly Shmatikov
references.title: How to backdoor federated learning
references.venue: In International Conference on Artificial Intelligence and Statistics,
references.authors: Peva Blanchard Rachid Guerraoui Julien Stainer
references.title: Machine learning with adversaries: Byzantine tolerant gradient descent
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Sebastian Caldas Sai Meher Karthik Duddu Peter Wu Tian Li Jakub Konečný H. Brendan McMahan Virginia Smith Ameet Talwalkar
references.title: Leaf: A benchmark for federated settings
references.venue: arXiv preprint arXiv:1812.01097,
references.authors: Xiaoyu Cao Minghong Fang Jia Liu Neil Zhenqiang Gong
references.title: Fltrust: Byzantine-robust federated learning via trust bootstrapping
references.venue: arXiv preprint arXiv:2012.13995,
references.authors: Xiaoyu Cao Minghong Fang Jia Liu Neil Zhenqiang Gong
references.title: Fltrust: Byzantine-robust federated learning via trust bootstrapping
references.venue: Network and Distributed System Security Symposium,
references.authors: Minghong Fang Xiaoyu Cao Jinyuan Jia Neil Zhenqiang Gong
references.title: Local model poisoning attacks to byzantine-robust federated learning
references.venue: In 29th USENIX Security Symposium (USENIX Security 20),
references.authors: Clement Fung Chris J.M. Yoon Ivan Beschastnikh
references.title: The limitations of federated learning in sybil settings
references.venue: In 23rd International Symposium on Research in Attacks, Intrusions and Defenses (RAID
references.authors: Jiawen Kang Zehui Xiong Dusit Niyato Shengli Xie Junshan Zhang
references.title: Incentive mechanism for reliable federated learning: A joint optimization approach to combining reputation and contract theory
references.venue: IEEE Internet of Things Journal,
references.authors: Xiang Li Kaixuan Huang Wenhao Yang Shusen Wang Zhihua Zhang
references.title: On the convergence of fedavg on non-iid data
references.venue: In International Conference on Learning Representations,
references.authors: H. Brendan McMahan Eider Moore Daniel Ramage Seth Hampson Blaise Agüera y Arcas
references.title: Communication-efficient learning of deep networks from decentralized data
references.authors: El Mahdi El Mhamdi Rachid Guerraoui Sébastien Rouault
references.title: The hidden vulnerability of distributed learning in byzantium
references.venue: In Proceedings of the 35th International Conference on Machine Learning (ICML),
references.authors: Luis Muñoz-González Battista Biggio Ambra Demontis Andrea Paudice Vasin Wongrassamee Emil C. Lupu Fabio Roli
references.title: Towards poisoning of deep learning algorithms with back-gradient optimization
references.venue: arXiv preprint arXiv:1708.08689,
references.authors: Virginia Smith Chao-Kai Chiang Maziar Sanjabi Ameet S Talwalkar
references.title: Federated multi-task learning
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Sebastian U Stich
references.title: Local sgd converges fast and communicates little
references.venue: arXiv preprint arXiv:1805.09767,
references.authors: Sebastian U Stich Jean-Baptiste Cordonnier Martin Jaggi
references.title: Sparsified sgd with memory
references.venue: arXiv preprint arXiv:1809.07599,
references.authors: Qi Xia Zeyi Tao Zijiang Hao Qun Li
references.title: Faba: An algorithm for fast aggregation against byzantine attacks in distributed neural networks
references.venue: In IJCAI,
references.authors: Qiang Yang Yang Liu Tianjian Chen Yongxin Tong
references.title: Federated machine learning: Concept and applications
references.venue: ACM Transactions on Intelligent Systems and Technology (TIST),
references.authors: Dong Yin Yudong Chen Ramchandran Kannan Peter Bartlett
references.title: Byzantine-robust distributed learning: Towards optimal statistical rates
references.venue: In International Conference on Machine Learning,
references.authors: Hao Yu Sen Yang Shenghuo Zhu
references.title: Parallel restarted sgd with faster convergence and less communication: Demystifying why model averaging works for deep learning
references.venue: In Proceedings of the AAAI Conference on Artificial Intelligence,
references.authors: Chengliang Zhang Suyi Li Junzhe Xia Wei Wang Feng Yan Yang Liu
references.title: Batchcrypt: Efficient homomorphic encryption for cross-silo federated learning
references.venue: In 2020 {USENIX} Annual Technical Conference ({USENIX}{ATC}
references.authors: Yuchen Zhang John C Duchi Martin J Wainwright
references.title: Communication-efficient algorithms for statistical optimization
references.venue: IEEE 51st IEEE Conference on Decision and Control (CDC),
references.authors: Fang
references.title: 2020), our goal was not necessarily to achieve the smallest error rates for the protocols on the considered datasets as our goal was not to search for the most optimized DNN architecture. Instead, our goal was to demonstrate that the state-of-the-art attacks can increase the testing error rates of the learned DNN classifiers and TESSERACT can reverse the attacks better than the other
sections.heading: 1 INTRODUCTION
sections.text: Federated learning (FL) Smith et al. (2017); Yang et 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 a set of clients that then send maliciously crafted gradients. The attack can be targeted against particular data instances or can be untargeted. The latter brings down the overall accuracy by affecting all classes. To counter this threat, a 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-the-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-robust 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 a 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-resilient federated learning approaches fail against the directed-deviation attack of Fang et al. (2020), which is the state-of-the-art untargeted model poisoning attack, TESSERACT is 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, i.e., an adaptive white-box attack. TESSERACT is based on a simple intuition that for a sufficiently small learning rate, as 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 show in Figure 2. We capture this quantitatively in a metric that we propose, called flip-score, which is the sum of squares of gradient magnitudes of all parameter updates that suggest a flip in the gradient direction from the previous global update. We find that
  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 are less damaging, consistent with the observation in Fang et al. (2020). Thus, in the main paper, we focus on the directed deviation model poisoning attack.
  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. We use a stateful suspicion model to keep the history of every client’s activity and use that as a 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-18 on CIFAR-10, and GRU on the Shakespeare dataset. We comparatively evaluate our defense against six baselines, including the most recent ones, FABA Xia et al. (2019), FoolsGold Fung et al. (2020), and FLTrust Cao et 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/models), TESSERACT is the only one whose protection transfers 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 https://www.dropbox.com/ sh/h9ulw6y2f8rzv64/AADe1Sb9PhhCLqclzgZ4xvvJa?dl=0.
  The rest of the paper is organized as follows. We describe in Sec 2 the threat model, the SOTA attack, and why all existing Byzantine-resilient federated learning approaches are susceptible. We present TESSERACT’s design in Sec 3 and convergence analysis in Sec 4. We describe the baselines and the datasets in Sec 5, and evaluation in Sec 6.
sections.heading: 2 BACKGROUND
sections.text: 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 a maximum of cmax 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 a synchronous manner.
sections.heading: 2.1 BYZANTINE-RESILIENT FEDERATED LEARNING
sections.text: 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 a 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 cmax 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 et 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 − cmax − 2) neighbors is chosen as the local model. The full-Krum 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 a 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, cmax 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 a 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.
sections.heading: 2.2 THREAT MODEL: STATE-OF-THE-ART MODEL POISONING ATTACK
sections.text: Our threat model consists of a scenario where an adversary compromises a 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 directed deviation attack (DDA) bypassing all known defenses 1. To address generality (more details in Appendix 1There is no overlap between the authors of this current submission and of the SOTA attack Fang et al. (2020).
  § 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 a 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 to Median, we call this the Full-Trim attack), respectively. We assume a full-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 a vector s of size equal to the number of model parameters.
  s(t, ·) = sign(sum i (▽LMi(t, ·)),
  where ▽LMi(t, ·) is the gradient updates of client i. Full-Krum attack: Having estimated s, the attackers send gradients in the opposite direction, all with a magnitude λ, 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, c, |P |, GM(t, ·),▽LMi(t + 1, ·), where c out m participating clients are malicious, |P | is the number of parameters in the global model GM . λ 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 j toward the inverse of the direction that s(t, j) suggests in order to attack a mean-like aggregation. It does so by randomly sampling gradient magnitudes from a 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 at the change in gradient direction to identify malicious gradients in a robust way.
  This kind of an attack is an extremely likely scenario in a cross-device as well as a cross-silo federated learning setting, (more details in Appendix § A.6.1) and needs to be defended against.
sections.heading: 3 DESIGN
sections.text: TESSERACT uses a reputation-based scheme to compute the aggregation weights of the participating clients. Reputation-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-score in a different way by using flip-score of the local gradients, as described below. TESSERACT assumes that a maximum of cmax(< m2 ) clients can be malicious. It penalizes 2cmax clients and rewards the rest in every iteration by an amount W(i, t) based on their flip-score (described below) and updates their reputation score, where i is the client ID and t is time. We present the pseudocode in Algorithm 1.
  W(i, t) = { −(1− 2cmaxm ), if penalized. 2cmax
  m , 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.1). Also, this makes recovery difficult as the penalty value is higher than the reward as cmax < m2 and allows us to be conservative. The reputation score of a client i is initialized and updated as follows -
  RS(i, 0) = 0.
  RS(i, t) = µdRS(i, t− 1) +W(i, t), t > 0.
  where 0 ≤ µd ≤ 1.0 is the decay parameter, and RS is the reputation score. A low µd gives more importance to the present flip-score and a high µd gives significant importance to the past performance of a client. This decay operation also helps cap the maximum and minimum reputation score (with µd < 1, for more details, see Appendix § A.1). We normalize the reputation score using softmax to do a weighted mean aggregation, but a user can use this to 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 an overflow. This is motivated by the fact that the reputation score is a cumulative quantity, and can potentially keep increasing with time in an unbounded manner.
  Flip-score. We compare the present gradients ▽LMi(t+1, ·) sent by local model i with the gradient direction of the global model at time t, sg(t, ·) = sign(GM(t, ·) − GM(t − 1, ·)). We define flip-score as the sum of square of the gradient magnitudes of all parameters that experience a change in their gradient direction, that is,
  FSi(t+ 1) = |P |−1∑ j=0 (▽LMi(t+ 1, j)) 2 (sign(▽LMi(t+ 1, j)) ̸= sg(t, j)), (1)
  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, a high flip-score suggests a 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, or 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 a 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 flip-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 GM(t+ 1, ·) Input: Local model updates w = ▽LMi(t+ 1, ·) Parameters: m, cmax, µd 0 : Initialize reputation RSi(0) = 0 for every client i 1 : Initialize global direction sg(0) to a zero vector 2 : for every client i compute flip-score: 3 : FSi(t+ 1) = ∑|P |−1 j=0 (▽LMi(t+ 1, j)) 2 (sign(▽LMi(t+ 1, j)) ̸= sg(t, j)) 4 : Penalize cmax clients on either end of FS spectrum as: RS(i, t+1) = µdRS(i, t)− (1− 2cmaxm ) 6 : Reward the rest of the clients as: RS(i, t+ 1) = µdRS(i, t) + 2cmaxm 7 : Normalize reputation weights: WR = e RS∑ eRS 8 : Aggregate gradients: ▽GM(t+ 1, ·) = wTWR 9 : Update global direction: sg(t+ 1, ·) = sign(▽GM(t+ 1, ·)) 10: Update global model and broadcast: GM(t+ 1, ·) = GM(t, ·) + ▽GM(t+ 1, ·)
sections.heading: 4 CONVERGENCE ANALYSIS
sections.text: We make the following assumptions on LMk, part of which are adapted from Li et al. (2020). 1. Assumption #1: LMk are all L-smooth, that is, for all v and w, LMk(v) ≤ LMk(w) + (v −
  w)T▽LMk(w) + L2 ∥v − w∥ 2 2.
  2. Assumption #2: LMk are all µ-strongly convex, that is, for all v and w, LMk(v) ≥ LMk(w) + (v − w)T▽LMk(w) + µ2 ∥v − w∥ 2 2. 3. Assumption #3: Let ξkt be sampled uniformly at random from the local data of the k − th client, then the variance of stochastic gradients of each client is bounded, that is, E ∥▽LMk(wkt , ξkt )− ▽LMk(wkt )∥2 ≤ σ2k for k = 1, 2, ...m. 4. Assumption #4: The expected squared norm of stochastic gradients is uniformly bounded, that is, E ∥▽LMk(wkt , ξkt )∥2 ≤ G2 for k = 1, ...m, and t = 0, ..T − 1. 5. Assumption #5: Within K iterations, the reputation score of malicious clients drop at least by δmal, and reputation score of benign clients increase at least by δben, that is, |RStmal −RS t−K mal | ≥ δmal
  and |RStben −RS t−K ben | ≥ δben, for t = 0, ..T − 1.
  Assumptions #1 and #2 are standard and apply to l2-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∗k be the minimum value of GM and LMk respectively, then:
  E[GM(w)T ]−GM∗ ≤ 2 µ2 · L γ + T ( m∑ k=1 p2kσ 2 k + 6LΓ + 8G 2 + 8G2 c∑ k=1 pk,0 + µ2 4 ∥w0 − w∗∥2).
  where L, µ,G are defined above, γ = max{8Lµ , 1}, ηt = 2 µ(γ+t) , T is the total number of iterations, c is the number of malicious clients, pk,0 is the initial weight for malicious clients, and Γ = GM∗ − ∑m k=1 pkLM ∗ k , that effectively quantifies the degree of non-iidness according to Li et al. (2020). This shows that a weighted mean aggregation is guaranteed to converge in federated learning. The converge speed is O( 1T ). The increase of number of malicious clients c increases the bound.
sections.heading: 5 IMPLEMENTATION
sections.text: 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 in a 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: c = cmax.
  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 TESSERACT on 4 different datasets (Table 1). The DNN trained on MNIST has 2 conv layers with 30 and 50 channels respectively, each followed by a 2× 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 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 et al. (2019).
sections.heading: 6 EVALUATION
sections.heading: 6.1 MACRO EXPERIMENTS
sections.text: 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-Krum attack. We have not shown the test loss curve for Krum aggregation because of the large loss values here,
  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 × 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 or as an artifact of their design). For example, FoolsGold does creditably for the Full-Trim attack but is vulnerable against the Full-Krum attack. Averaging across the configurations, it appears FABA is the closest competitor to TESSERACT. We observe that FABA, although it performed well for c/m = 0.2, failed to defend when the number of attackers grew to 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 a 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 as long as c ≤ cmax and c < m2 . 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, we 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 a wide range of non-IID bias, that is 0.1 to 0.8. TESSERACT and FABA require an estimate of the upper
  Table 3: Fraction of malicious or benign clients allotted weights above 1e-4 averaged over 500 iterations. The weakness of FoolsGold and FLTrust stems in part from the fact that they assign low weight to a significant fraction of benign clients for effective detection.
  Defense Mal/ Benign Full- FullBen trim krum FoolsGold nben 0.29 0.30 0.10 nmal - 0.00 0.64
  FLTrust nben 0.48 0.45 0.49 nmal - 0.52 0.63 TESSERACT nben 0.75 0.75 0.63 nmal - 0.00 0.08
  Figure 4: Clients’ reputation weights against time with TESSERACT, with higher weights to benign clients, as malicious ones tend to 0.
  bound of number of malicious clients, cmax to be known. FoolsGold and FLTrust, on the other hand, make use of cosine similarity among clients, and with a 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 a zero weight in order to conservatively defend against an attack, as can be seen in 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 a 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 to zero, while those of the benign clients increase with time.
sections.heading: 6.2 ADAPTIVE ATTACK
sections.text: Having shown the performance of TESSERACT against the above attacks, we proceed to 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 t+ 1, the attacker knows FSlow(t) and FShigh(t) beyond which the clients were penalized at iteration t. The Adaptive-Krum attack first computes the target malicious gradients at t+1, and if its flip-score goes above FShigh(t), it 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 are not expected to occupy the lower spectrum of the flip-score. This has been verified
  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 a trade-off between stealth and attack impact in this case, as can be seen in Figure 5.
  The Adaptive-Trim attack is a smarter and collaborative attack. Its target is to generate attacked gradients vi, i = 0, 1, 2, · · · c− 1. It first computes the Full-Trim target attack ui for every malicious client i. Then, it initializes v0 to u0 and modifies it, until v0 generates a flip-score that is less than FShigh(t). Client i = 1 then updates its target attack from u1 to v1 = u1 + (u0 − v0) in order to compensate for a sub-optimal attack created by i = 0 because of the flip-score-evasion constraint. Thus, a client may not necessarily find a solution if the target grows and the constraints are hard to solve for. The attacker hopes that ∑c−1 i=0 ui = ∑c−1 i=0 vi. 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 are 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-score distribution is dynamic, as can be seen in Figure 2, and changes from time t to t+ 1, and when it decreases in consecutive iterations by a significant amount, the attackers can still be blocked.
  We have also created a 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.
sections.heading: 7 DISCUSSION AND CONCLUSION
sections.text: We have presented TESSERACT, a secure parameter server for federated learning robust to model poisoning attacks. TESSERACT uses a stateful algorithm to allocate reputation scores to the participating clients to lower the contribution of maliciously behaving clients. We define malicious behavior using a metric, flip-score, which when very high or low, captures attacks that try to divert the global model away from convergence. This makes TESSERACT a 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-the-art 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, an adaptive white-box attacker with access to all internals of TESSERACT, including dynamically determined threshold parameters, cannot bypass its defense. All of our evaluation is limited to a synchronous setting with no gradient encryption, as gradient encryption is less relevant in a
  cross-device scenario due to its high computational overhead Zhang et al. (2020). However, these form logical avenues for our future work.
sections.heading: 8 REPRODUCIBILITY STATEMENT
sections.text: 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://www.dropbox.com/ sh/h9ulw6y2f8rzv64/AADe1Sb9PhhCLqclzgZ4xvvJa?dl=0. The code has also been uploaded as a supplementary file in the current submission.
sections.heading: A APPENDIX
sections.heading: A.1 PENALTY AND REWARD VALUE
sections.text: Penalty and reward selection. Our design policy penalizes 2cmax out of m clients in every iteration. Considering a completely benign scenario, we want the expected value of the reputation score of a client that has been penalized e fraction of times to be zero, where e = 2cmaxm . Let a client i be penalized en number of times in n iterations. There are ( n en ) ways to select the iterations where the client is penalized. After n iterations, the reputation score of client i is given by:
  RS(i, n) = n∑ t=0 µn−td W(i, t). (2)
  where W(i, t) is a sequence of penalty and reward over time. The expected value of this reputation score over all possible sequences j ∈ ( n en ) is
  E j [RS(i, n)] = 1( n en ) ∑ j RS(i, n)
  = 1( n en ) ∑ j ∑ t µn−td W(i, t) = 1( n en ) ∑ t µn−td ∑ j W(i, t) = 1( n en ) ∑ t µn−td (−(pen ( n en ) ) + (r(1− e)n ( n en ) )
  Our setting with r = 2cmaxm 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 a random process through which (benign) clients generate their flip scores. Thus, if a subset of clients are penalized less than 2cmax
  m of times, they are expected to have a net neutral reputation score.
  Upper and lower bound of reputation score. From the above expression, it is obvious that if µd = 0, −p ≤ RS ≤ r. When 0 < µd < 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 be solved to obtain −p1−µd ≤ RS ≤ r 1−µd . It should be noted that these reputation scores are normalized using softmax to compute the reputation weights. If the absolute value of the lower bound is not large enough (if µd is set to be too small), then even after perfect detection, a malicious client can still have a significant reputation weight after softmax normalization. If µd 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 µd = 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 is a design parameter that the user can decide.
sections.heading: A.2 LABEL FLIPPING
sections.text: 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-gradient optimization based attacks Muñoz-González et al. (2017). They show that the existing data poisoning attacks are insufficient and cannot produce a high testing error rate, not higher than 0.2 in the presence of byzantine-robust aggregation techniques (Krum, trimmed mean, and median).
  We observe that both state-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
  damaging impact on 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 TESSERACT’s intuition is general enough to counteract both the more powerful “directed-deviation attacks” and the weaker state-of-the-art data poisoning attacks.
sections.heading: A.3 ADDITIONAL EXPERIMENTS
sections.text: Here, we provide additional evaluation of TESSERACT in two specific situations. We stress-test it first by subjecting it to a higher number of malicious clients to 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 cmax, and to that end, we set c = cmax. Since TESSERACT requires cmax < m2 , we have swept c 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 c/m = 0.30 as can be seen in Table 2 and Figure 3 with c = cmax set for all the defense techniques that require a knowledge of cmax.
  Figures 7(b) and (c) show the performance of TESSERACT on 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-attacks. Full-Krum attack finds a vector of gradients u by solving an optimization problem described in Fang et al. (2020), and every malicious client i would send u with an additional noise to appear different. Full-Trim attack solves a different optimization problem to also come up with a vector of gradients u to which every malicious
  client i would add some noise to obtain ui. 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
  vi, i = 0, 1, 2, ..., c− 1 where c is the number of malicious clients. Here, vi is the vector of gradients with size equal to the number of model parameters, each satisfying the constraint -
  FS(vi) < FShigh(t)
  that is, every computed vector should have a flip-score lower than the cut-off flip-score according to the adversary’s knowledge, such that
  c−1∑ i vi = c−1∑ i=0 ui
  where ui were determined by the adversary originally as a valid solution to the Full-Krum and Full-Trim optimization problems. We solve this problem as described in Section 6.2. In short, we initialize vi to some target value, and then undo the attack on “less important parameters” until the flip-score constraint is just met, and send the computed vi for aggregation. v0 is initialized to u0, and then updated until the flip-score constraint is satisfied. The difference u0 − v0 is added to u1 which now becomes the initial value of v1 and so on. The results have been described and analyzed in Section 6.2.
  We formulate an even stronger attack where the adversary also has the knowledge of its own reputation score (WR) in order to come up with attacked gradients with better chances of success. We call this a “Weighted-Adaptive-Trim” attack. The modified constraint is
  c−1∑ i WR,ivi = c−1∑ i=0 WR,iui
  TESSERACT successfully defends against this attack when evaluated on MNIST, as can be seen from the experimental result in Figure 8. With TESSERACT, 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.
sections.heading: A.4 CONVERGENCE ANALYSIS
sections.text: Let the k-th client hold nk training data batches: xk,1, ...xk,nk . The local objective function LMk(·) is given by
  LMk(w) = 1
  nk nk∑ j=1 l(w;xk,j),
  where l(·; ·) is the specified loss function for each client. The global objective function is defined as
  GMk,t(w) = m∑
  k=1
  pk,tLMk(w).
  The global model is updated as
  wkt+1 = w k t − ηt m∑ k=1 pk,t▽LMk(wkt ),
  where pk,t = softmax(RSk,t) is the softmax of reputation score of client k at time t. We update the weights by averaging the weights from selected clients w̄t = ∑m k=1 pk,tw k t . For
  convenience, we also define gt = ∑m k=1 pk,t∇LMk(wkt , ξkt ), where ξkt is the selected local data.
  Figure 8: The figure shows the test accuracy of TESSERACT when evaluated on MNIST dataset under the default conditions with m = 100, c = 20 where the adversary launches the Weighted-Adaptive-Trim attack on the system, compared with the baseline performance of FedSGD against the Full-Trim attack. TESSERACT successfully defends against this attack to achieve a 90% accuracy.
  Figure 9: The figure shows the impact of the Full-Krum attack on Krum aggregation on 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 as shown in Figure 3(a).
sections.heading: A.4.1 ANALYSIS ON CONSECUTIVE STEPS
sections.text: To bound the expectation of the global objective function at time T from its optimal value, we first consider to analyze the global weight from the optimal weights by calculating single step SGD:
  ∥w̄t+1 −w∗∥2 = ∥w̄t − ηtgt −w∗ − ηtḡt + ηtḡt∥2
  = ∥w̄t −w∗ − ηtḡt∥2 + 2ηt⟨w̄t −w∗ − ηtḡt, ḡt − gt⟩+ η2t ∥ḡt − gt∥2. (3)
  The first term of Equation. 3 can be expressed as
  ∥w̄t −w∗ − ηtḡt∥2 = ∥w̄t −w∗∥2 − 2ηt⟨w̄t −w∗, ḡt⟩+ η2t ∥ḡt∥2. (4)
  The second term of Equation. 4 can be expressed as
  −2ηt⟨w̄t −w∗, ḡt⟩ =− 2ηt m∑
  k=1
  pk,t⟨w̄t −w∗,∇LMk(wkt )⟩
  =− 2ηt m∑
  k=1
  pk,t⟨w̄t −wkt ,∇LMk(wkt )⟩
  − 2ηt m∑
  k=1
  pk,t⟨wkt −w∗,∇LMk(wkt )⟩.
  (5)
  By Cauchy-Schwarz inequality and AM-GM inequality, we have
  − 2ηt m∑
  k=1
  pk,t⟨w̄t −wkt ,∇LMk(wkt )⟩ ≤ 1
  ηt ∥w̄t −wkt ∥2 + ηt∥∇LMk(wkt )∥2. (6)
  By the µ-strong convexity of LMk(·), we have
  − 2ηt m∑
  k=1
  pk,t⟨wkt −w∗,∇LMk(wkt )⟩ ≤ −(LMk(wkt )− LMk(w∗))− µ
  2 ∥wkt −w∗∥2. (7)
  By the convexity of ∥ · ∥ and the L-smoothness of LMk(·), we can express third term of Equation. 4 as
  η2t ∥ḡt∥2 ≤ η2t m∑
  k=1
  pk,t∥∇LMk(wkt )∥2
  ≤ 2Lη2t m∑
  k=1
  pk,t(LMk(w k t )− LM∗k ).
  (8)
  Combining Equations. 4 − 8, we have
  ∥w̄t −w∗ − ηtḡt∥2 ≤∥w̄t −w∗∥2 + 2Lη2t m∑
  k=1
  pk,t(LMk(w k t )− LM∗k )
  + ηt m∑ k=1 pk,t( 1 ηt ∥w̄t −wkt ∥2 + ηt∥∇LMk(wkt )∥2)
  − 2ηt m∑
  k=1
  pk,t((LMk(w k t )− LMk(w∗)) +
  µ 2 ∥wkt −w∗∥2)
  =(1− µηt)∥w̄t −w∗∥2 + m∑
  k=1
  pk,t∥w̄t −wkt ∥2
  + 2Lη2t m∑ k=1 pk,t(LMk(w k t )− LM∗k ) + η2t m∑ k=1 pk,t∥∇LMk(wkt )∥2
  − 2ηt m∑
  k=1
  pk,t(LMk(w k t )− LMk(w∗))
  ≤(1− µηt)∥w̄t −w∗∥2 + m∑
  k=1
  pk,t∥w̄t −wkt ∥2
  + 4Lη2t m∑ k=1 pk,t(LMk(w k t )− LM∗k )
  − 2ηt m∑
  k=1
  pk,t(LMk(w k t )− LMk(w∗)),
  (9)
  where we use the L-smoothness of LMk(·) in the last inequality.
  We use γt = 2ηt(1− 2Lηt), and the last two terms of Equation. 9 are
  4Lη2t m∑ k=1 pk,t(LMk(w k t )− LM∗k )− 2ηt m∑ k=1 pk,t(LMk(w k t )− LMk(w∗))
  =− γt m∑
  k=1
  pk,t(LMk(w k t )−GM∗)− γt m∑ k=1 pk,t(GM ∗ − LM∗k )
  + 2ηt m∑ k=1 pk,t(LMk(w ∗)− LM∗k )
  =− γt m∑
  k=1
  pk,t(LMk(w k t )−GM∗)− γt m∑ k=1 pk,t(GM ∗ − LM∗k )
  + 2ηt m∑ k=1 pk,t(GM ∗ − LM∗k )
  =− γt m∑
  k=1
  pk,t(LMk(w k t )−GM∗) + (2ηt − γt) m∑ k=1 pk,t(GM ∗ − LM∗k )
  =− γt m∑
  k=1
  pk,t(LMk(w k t )−GM∗) + 4Lη2tΓ,
  (10)
  where Γ = ∑m
  k=1 pk,t(GM ∗ − LM∗k ) = GM∗ − ∑m k=1 pk,tLM ∗ k .
  The first term of Equation. 10
  m∑ k=1 pk,t(LMk(w k t )−GM∗)
  = m∑ k=1 pk,t(LMk(w k t )− LMk(w̄t)) + m∑ k=1 pk,t(LMk(w̄t)−GM∗)
  ≥ m∑
  k=1
  pk,t⟨∇LMk(w̄t),wkt − w̄t)⟩+ m∑
  k=1
  pk,t(LMk(w̄t)−GM∗)
  = m∑ k=1 pk,t⟨∇LMk(w̄t),wkt − w̄t)⟩+GM(w̄t)−GM∗
  ≥− 1 2 m∑ k=1 pk,t(ηt∥LMk(w̄t)∥2 + 1 ηt ∥wkt − w̄t∥2) +GM(w̄t)−GM∗
  ≥− m∑
  k=1
  pk,t(ηtL(LMk(w̄t)− LM∗k ) + 1
  2ηt ∥wkt − w̄t∥2) +GM(w̄t)−GM∗,
  (11)
  where the first inequality results from the convexity of LMk(·), the second inequality from AM-GM inequality and the third inequality from L-smoothness of LMk(·).
  Therefore, Equation. 10 becomes
  − γt m∑
  k=1
  pk,t(LMk(w k t )−GM∗) + 4Lη2tΓ
  ≤γt( m∑
  k=1
  pk,t(ηtL(LMk(w̄t)− LM∗k ) + 1
  2ηt ∥wkt − w̄t∥2))
  − γt(GM(w̄t)−GM∗) + 4Lη2tΓ
  =γt( m∑ k=1 pk,t(ηtL(LMk(w̄t)−GM∗) + 1 2ηt ∥wkt − w̄t∥2))
  + γtηtLΓ− γt(GM(w̄t)−GM∗) + 4Lη2tΓ
  =γt(ηtL− 1) m∑
  k=1
  pk,t(LMk(w̄t)−GM∗)
  + γt 2ηt m∑ k=1 pk,t∥wkt − w̄t∥2 + (4Lη2t + γtηtL)Γ,
  (12)
  With GM(w̄t)−GM∗ > 0 and ηtL− 1 < 0, we have
  γt(ηtL− 1) m∑
  k=1
  pk,t(LMk(w̄t)−GM∗) ≤ 0, (13)
  and recall γt = 2ηt(1− 2Lηt), so γt2ηt ≤ 1 and 4Lη 2 t + γtηtL ≤ 6Lη2t .
  Therefore,
  −γt m∑
  k=1
  pk,t(LMk(w k t )−GM∗) + 4Lη2tΓ ≤ m∑ k=1 pk,t∥wkt − w̄t∥2 + 6Lη2tΓ. (14)
  Thus, Equation. 9 becomes
  ∥w̄t −w∗ − ηtḡt∥2 ≤ (1− µηt)∥w̄t −w∗∥2 + 2 m∑
  k=1
  pk,t∥wkt − w̄t∥2 + 6Lη2tΓ. (15)
sections.heading: A.5 BOUND FOR VARIANCE OF GRADIENTS
sections.text: Next, to bound the gradient, using assumption 3, we have
  E∥gt − ḡt∥2 = E∥ m∑
  k=1
  pk,t(∇LMk(wkt , ξkt )−∇LMk(wkt ))∥2
  = m∑ k=1 p2k,tE∥∇LMk(wkt , ξkt )−∇LMk(wkt )∥2
  ≤ m∑
  k=1
  p2k,tσ 2 k.
  (16)
sections.heading: A.5.1 BOUND FOR DIVERGENCE OF WEIGHTS
sections.text: Based on Assumption 5, for malicious clients k = 1, 2, . . . , c, we have
  pk,t = softmax(RS t km)
  = eRS t km∑m
  i=1 RS t i
  = eRS t−M km −δm∑c
  i=1 e RSt−Mi −δm + ∑m i=c+1 e RSt−Mi +δb
  = eRS t−M km∑c
  i=1 e RSt−Mi + ∑m i=c+1 e RSt−Mi +δb+δm
  ≤ e RSt−Mkm∑c
  i=1 e RSt−Mi + ∑m i=c+1 e RSt−Mi
  = pk,t−M .
  (17)
  To bound the weights, we assume within E communication steps, there exists t0 < t, such that t − t0 ≤ E − 1 and wkt0 = w̄t0 for all k = 1, 2, . . . ,m. And we know ηt is non-increasing and ηt0 ≤ 2ηt. With the fact E∥X − EX∥2 ≤ E∥X∥2 and Jensen inequality, we have
  E m∑
  k=1
  pk,t∥w̄t −wkt ∥2 ≤E m∑
  k=1
  pk,t∥w̄t0 −wkt ∥2
  ≤ m∑
  k=1 pk,tE t−1∑ t0 (E − 1)η2t ∥LMk(wkt , ξkt )∥2
  ≤ m∑
  k=1 pk,tE t−1∑ t0 (E − 1)η2t0G 2
  ≤ m∑
  k=1
  pk,tE(E − 1)2η2t0G 2
  = c∑ k=1 pk,tE(E − 1)2η2t0G 2 + m∑ k=c+1 pk,tE(E − 1)2η2t0G 2
  ≤ c∑
  k=1
  pk,tE(E − 1)2η2t0G 2 + 4η2t (E − 1)2G2
  ≤4 c∑
  k=1
  pk,tη 2 t (E − 1)2G2 + 4η2t (E − 1)2G2
  ≤4 c∑
  k=1
  pk,0η 2 t (E − 1)2G2 + 4η2t (E − 1)2G2,
  (18)
  where pk,0 is the initial probability of kth malicious client.
sections.heading: A.5.2 CONVERGENCE BOUND
sections.text: Combining Equation.(3)(15)(16)(18), we have
  ∥w̄t+1 −w∗∥2 =∥w̄t −w∗ − ηtḡt∥2 + 2ηt⟨w̄t −w∗ − ηtḡt, ḡt − gt⟩+ η2t ∥ḡt − gt∥2
  ≤(1− µηt)∥w̄t −w∗∥2 + 2 m∑
  k=1
  pk,t∥wkt − w̄t∥2 + 6Lη2tΓ
  + 2ηt⟨w̄t −w∗ − ηtḡt, ḡt − gt⟩+ η2t ∥ḡt − gt∥2.
  (19)
  Since E[gt] = ḡt, Therefore,
  E∥w̄t+1 −w∗∥2 ≤(1− µηt)E∥w̄t −w∗∥2 + 2E m∑
  k=1
  pk,t∥wkt − w̄t∥2 + 6Lη2tΓ
  + 2ηtE⟨w̄t −w∗ − ηtḡt, ḡt − gt⟩+ Eη2t ∥ḡt − gt∥2
  ≤(1− µηt)E∥w̄t −w∗∥2 + 8 c∑
  k=1
  pk,0η 2 t (E − 1)2G2 + 8η2t (E − 1)2G2
  + 6Lη2tΓ + η 2 t m∑ k=1 p2k,tσ 2 k
  =(1− µηt)E∥w̄t −w∗∥2
  + η2t [8 c∑ k=1 pk,0(E − 1)2G2 + 8(E − 1)2G2 + 6LΓ + m∑ k=1 p2k,tσ 2 k]
  (20)
  We set ηt = βt+γ for some β > 1 µ and γ > 0, such that η1 ≤ min{ 1 µ , 1 4L} = 1 4L and ηt ≤ 2ηt+E . We want to prove E∥w̄t − w∗∥2 ≤ vγ+t , where v = max{ β2B βµ−1 , (γ + 1)E∥w̄1 − w
  ∗∥2} and B = 8 ∑c k=1 pk,0(E − 1)2G2 + 8(E − 1)2G2 + 6LΓ + ∑m k=1 p 2 k,tσ 2 k.
  Firstly, the definition of v ensures that E∥w̄1 −w∗∥2 ≤ vγ+1 . Assume the conclusion holds for some t, we have
  E∥w̄t+1 −w∗∥2 ≤(1− µηt)E∥w̄t −w∗∥2 + η2tB
  ≤(1− βµ t+ γ ) v t+ γ +
  β2B
  (t+ γ)2
  = t+ γ − 1 (t+ γ)2 v + [ β2B (t+ γ)2 − βµ− 1 (t+ γ)2 v]
  ≤ v t+ γ + 1 .
  (21)
  By the L-smoothness of GM(·), E[GM(w̄t)]−GM∗ ≤ L2E∥w̄t −w ∗∥2 ≤ L2 v γ+t .
  Thus we have
  E[GM(wT )]−GM∗ ≤ 2 µ2 · L γ + T ( m∑ k=1 p2kσ 2 k + 6LΓ + 8G 2 + 8G2 c∑ k=1 pk,0 + µ2 4 ∥w0 − w∗∥2).
sections.heading: A.6 ADDITIONAL COMMENTS
sections.heading: A.6.1 CONCRETE USE-CASE
sections.text: A typical use-case would be a cross-device or a 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 a sensitive setting, there could be malicious intent to degrade the training process. Here an attacker could either compromise participating devices or join the training under multiple aliases. Having joined the network, it 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 an attack, the adversary does not need to know the gradients of the benign clients, but assumes its own before-attack gradients to be an approximate estimate of the benign gradients). With an approximate estimate of the benign gradients, it is easy for an adversary to launch the directed-deviation attack to start pushing the global model away from the optima until the goal of “denial-of-service” is achieved.
sections.heading: A.6.2 GENERALIZABILITY OF THE DEFENSE
sections.text: We have demonstrated that TESSERACT achieves the goal of secure aggregation in the presence of directed-deviation attacks, their adaptive-white-box versions, as well targeted and untargeted label-flipping attacks. This is because the fundamental intuition behind TESSERACT is based on the assumption that a large flip-score is indicative of an attack. It should be noted that the primary objective of any untargeted model poisoning attack is to push the global model away from the optima. Given the currently aggregated global model is benign, an attack will invariably push the model parameters in the opposite direction as the benign gradients, and would consequently generate a large flip-score and get flagged. If the current global model itself had a 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 now would generate high values of flip-score, as demonstrated in Figure 2. Since, we trim out both the ends of the flip-score spectrum in a relative manner, we provide a mechanism to defend against any untargeted attack.
sections.heading: A.6.3 ACCURACY OF BASELINE FEDSGD MODEL
sections.text: As in other federated learning-related security papers Fang et al. (2020); Fung et al. (2020); Bagdasaryan et al. (2020), our goal was not necessarily to achieve the smallest error rates for the protocols on the considered datasets as our goal was not to search for the most optimized DNN architecture. Instead, our goal was to demonstrate that the state-of-the-art attacks can increase the testing error rates of the learned DNN classifiers and TESSERACT can reverse the attacks better than the other defense algorithms. Since all baselines and our solution are evaluated on top of the same trained model, therefore we have a valid comparison base. Of course, we want DNNs to be reasonably performant as ours are.
title: ERATED LEARNING AGAINST MODEL POISONING AT- TACKS