FEDDISCRETE: A SECURE FEDERATED LEARNING ALGORITHM AGAINST WEIGHT POISONING
Year: 2021

Abstract:
Federated learning (FL) is a privacy-aware collaborative learning paradigm that allows multiple parties to jointly train a machine learning model without sharing their private data. However, recent studies have shown that FL is vulnerable to availability poisoning attacks, integrity backdoor attacks and inference attacks via weight poisoning and inference. In this paper, we propose a probabilistic discretization mechanism on the client side, which transforms the client’s model weight into a vector that can only have two different values but still guarantees that the server obtains an unbiased estimation of the client’s model weight. We theoretically analyze the utility, robustness, and convergence of our proposed discretization mechanism and empirically verify its superior robustness against various weight-based attacks under the cross-device FL setting.

text: Federated learning (FL) is a privacy-aware collaborative learning paradigm that allows multiple parties to jointly train a machine learning model without sharing their private data. However, recent studies have shown that FL is vulnerable to availability poisoning attacks, integrity backdoor attacks and inference attacks via weight poisoning and inference. In this paper, we propose a probabilistic discretization mechanism on the client side, which transforms the client’s model weight into a vector that can only have two different values but still guarantees that the server obtains an unbiased estimation of the client’s model weight. We theoretically analyze the utility, robustness, and convergence of our proposed discretization mechanism and empirically verify its superior robustness against various weight-based attacks under the cross-device FL setting.

heading: 1 INTRODUCTION
text: Federated learning (FL) is an emerging privacy-aware framework that trains a machine learning model across multiple parties without accessing their local private data (Konečnỳ et al., 2016; McMahan et al., 2017). In FL, each client first trains the local model using its private data and then sends the model gradients to an honest central server. The central server aggregates all local model gradients to form a global model, which is sent back to the clients for the next round of training. However, sharing model gradients might still leads to security concerns and privacy leakage.
Recent studies have shown that FL is vulnerable to various model weight poisoning attacks. The adversarial client(s) can stealthily manipulate the global model via modifying the local model updates to achieve attack goals like, preventing model convergence, implanting backdoors into the global model, and inferring the privacy information of clients’ private data (Gu et al., 2017; Blanchard et al., 2017; Pyrgelis et al., 2017; Xie et al., 2019; Bagdasaryan et al., 2020; Wang et al., 2020; Tang et al., 2020). To address such an issue, recent works start to explore different defense techniques to robustify FL against model weight poisoning attacks (Blanchard et al., 2017; Bagdasaryan et al., 2020; Shen et al., 2016; Geyer et al., 2017; Fung et al., 2018). However, most existing works apply the defense or robust techniques at the server side, which changes the role of the central server from being honest to trusted. And prior approaches mostly only focus on one type of attacks.
Our contributions. In this paper, we propose the FEDDISCRETE, a flexible FL framework that can combine any popular FL algorithms, for example, FedAvg(McMahan et al., 2017) and FedProx(Li et al., 2020), with our probabilistic discretization mechanism. Theoretical analyses on the utility, robustness, and convergence are performed to show that FEDDISCRETE is inherently robust to availability poisoning attacks (Kurita et al., 2020), integrity backdoor attacks (Gu et al., 2017) and server inference attacks (Shokri et al., 2017). FEDDISCRETE is evaluated on four popular image classification datasets under both data are i.i.d and non-i.i.d settings. The numerical results indicate that FEDDISCRETE is robust to various weight-based attacks.

heading: 2 BACKGROUNDS AND RELATED WORKS
text: In this section, we provide necessary background information on concepts thorough the paper and formalize the problem to be solved.
Federated learning (FL). FL is a privacy-aware collaborative learning, where N clients and one trusted server work together to learn a global model (McMahan et al., 2017). Depending on the application scenarios, the number of clients n can range from as small as two to several hundreds in the cross-silo setting or can easily go beyond millions in the cross-device setting. A classical way of formulating FL into an optimization problem is (Wang et al., 2021a)
min w∈Rd F (w) := N∑ i=1 piFi(w),where Fi(w) = 1 |Di| ∑ ξ∈Di fi(w; ξ) and N∑ i=1 pi = 1. (1)
In Eq. 1, w is the global model weight; Fi is the i-client local objective function; the local loss functions fi(w; ξ) are often assumed to be the same across all clients; the local data Di can have different distribution. Following the seminal work of (McMahan et al., 2017), extensive researches have been conducted to address various challenges in FL. For instance, (Li et al., 2020; Reddi et al., 2020) aim to design efficient optimization algorithms; (Konečnỳ et al., 2016; Luping et al., 2019) try to improve the communication efficiency; (Bagdasaryan et al., 2020; Xie et al., 2021) study the security issues on both attacks and defenses.
Adversaries. For any FL attack, the server is assumed to be honest, which faithfully follow the training protocols and any client cannot directly get the model weight of other clients. Under these assumptions, there are two adversaries: 1) the malicious clients can manipulate the weights for various attack purposes, such as interfering the global model training or implanting backdoors into the global model; 2) the curious server can explore the privacy information from local clients via inference attacks.
Availability poisoning attacks. The goal of availability poisoning attacks (APAs) is for malicious local client(s) to destroy or reduce the global model’s utility (Shen et al., 2016; Sun et al., 2018). In APAs, the attacker can either control the global model’s utility on target tasks or decrease the most of the model’s utility as the optimal attack strategy. In practice, adding a large random noise can successfully worsen the global model’s utility but can be easily discovered by anomaly detection techniques. In this case, any advanced attack needs to know and tries to bypass the defense techniques used in training. In this work, we assume the attacker has full knowledge of training process and all possible defense techniques.
Integrity backdoor attacks. The goals of integrity backdoor attack (IBAs) are two-fold: 1) the attacker aims to implant backdoors into the global model, through which the attacker can control the prediction results by injecting the trigger to any clean examples; 2) at the same time, the attacker wants the global model can still perform as good as the non-attacked model on all clean inputs (Bagdasaryan et al., 2020). Note that, IBAs are also conducted by the malicious clients in FL.
Inference attacks. Many studies show that the attacker could explore the private information from the model weights, such as membership and attribute information (Pyrgelis et al., 2017; Shokri et al., 2017; Ganju et al., 2018; Melis et al., 2019) or even recover the training samples used by clients Zhu et al. (2019). When the honest-but-curious server becomes malicious, it can explore privacy information of each client’s local dataset through inference attacks (IAs) since the server has full access to clients’ model weight.
Both APAs and IBAs can be achieved via weights poisoning that modifies the local model weights. For example, as the global model converges, the deviations of local models start to cancel out, i.e., ∑nt−1 i=1 (w t i − wt−1) ≈ 0 given as in Eq. 2 of Bagdasaryan et al. (2020), where t and i the communication round and client index respectively, wt and wti are the global and local model respectively, and nt is the number of participating clients. If the adversary aims to replace global model wt with a target model X , then it could propose to upload a local model weight wtA = ntX − (nt − 1)wt−1 − ∑nt−1 i=1 (w t i − wt−1) ≈ nt(X − wt−1) + wt−1 as given in Eq. 3 in Bagdasaryan et al. (2020). Prior works (Bagdasaryan et al., 2020; Wang et al., 2020; Xie et al., 2019) demonstrate the effectiveness of both APAs and IBAs when the training algorithm is FedAvg. IAs can be easily achieved by many existing advanced attack methods once they have the full access to the client model Shokri et al. (2017); Hu et al. (2021).
Related works. To address the various attacks, many prior defense works have been proposed and achieved good performance against the attacks. However, prior defense works only address one aspects of aforementioned three attacks. For availability poisoning attacks, Steinhardt et al. (2017) proposed a defending framework, which can be applied to defenders that remove outliers and then
minimize a margin-based loss on the remaining data. Under assumptions, this framework provides the approximate upper bounds on the efficacy of any data poisoning attack. However, this framework does not fit in the FL setting, as it needs the access to all private data. Blanchard et al. (2017) studied the presences of Byzantine adversaries and proposed Krum aggregation rule to defend under the assumption that the participants’ training data are i.i.d, which is not necessarily true in the FL setting. And indeed as argued in (Bagdasaryan et al., 2020), Krum can be used by the adversaries to make the attack more effective. FoolsGold (Fung et al., 2018) can mitigate sybils data poisoning attacks under the assumption that the honest clients can be separated from sybils by the diversity of their gradient updates. As discussed by the authors, FoolsGold is not successful at mitigating attacks initiated by a single adversary. For integrity backdoor attacks, Xie et al. (2021) provided a general framework that is certifiably robust to the backdoor attacks under the FL setting via the model weight smoothing. However, the convexity assumption is imposed on the loss function, which limits certified robustness to more challenging and widely used deep neural network. Ozdayi et al. (2021) proposed a defense approach based on adjusting server’s learning rate with the guidance of sign information of agents’ updates. For inference attacks, differential privacy is widely adopted approach to defend, where are judiciously random noise added on either the clients’ model update or the global model, e.g., Geyer et al. (2017), but it suffers from the trade-off between privacy and accuracy. Compared to this work, neither of these works can address three types of attacks simultaneously.

heading: 3 METHOD
text: We introduce FEDDISCRETE, a federated learning framework with a simply yet effective discrete mechanism and the flexibility to accommodate various FL optimization algorithms. A complete description is given in Algorithm 1. FEDDISCRETEdifferences FEDDISCRETE consists of three stages, namely, local training, discretization and aggregation, which are discussed in details.
Local Training. Since we mainly focus on the cross-device setting, in each communication round t, the server first selects a subset of |St| = K clients to participate the current round of training and broadcasts the global model wt to the selected clients. The clients who receives the global model then performs local training using any appropriate algorithm to generate a new local model, i.e. wt+1i for all i ∈ St. The ith client can 1) use the local stochastic gradient descent(SGD) method as is considered in FedAVG to perform a fixed number of SGD steps to improve communication efficiency; 2) use adaptive method (Wang et al., 2021b) to improve the convergence; 3) approximately minimize Fi(w)+ µ2 ‖w−w
t‖2 for some µ > 0 as proposed in FedProx to accommodate the system and data heterogeneity (Li et al., 2020).
Discretization. For all i ∈ St, the ith local client computes the maximum and minimum values of wti and sends noise-perturbed maximum value u t i and minimal value l t i back to the server, where the
noise is added to protect the privacy of the local training data and the noise is sampled and added in a way that to guarantee uti and l t i are the valid upper bound and lower bound of w t+1 i elementwise. Once the server received the client-wise upper-bounds and lower-bounds, it computes the minimum of the lower bounds ltmin and the maximum of the upper bounds u t max to prepare the inputs for the discretization mechanism (see Definition 3.1), which outputs an unbiased estimator of the input (see Lemma 4.1). For all i ∈ St, the ith client discretizes its continuous model wti into M(wti ; ltmin, utmax) and uploadsM(wti ; ltmin, utmax) to the server for aggregation. Aggregation. Rather than simply aggregating {M(wti ; ltmin, utmax)}i∈St , the sever first inspects whether each coordinate of wti is either l t min or u t max to exclude the any potential malicious adversaries that attempt to bypass the discretization process. And the server only aggregates the local model weights that pass the sanity check. Also when the server computes ltmin and u t max, it can be more conservative by discarding the extreme values in {lti}i∈St and {uti}i∈St by setting thresholds on the lower quantile of {lti}i∈St and upper quantile of {uti}i∈St to prevent adversaries proposing extremely large upper bounds and/or small lower bounds. For the ease of presentation, we do not include this choice in the description of Algorithm 1. Definition 3.1 (Discretization Mechanism). For any (w, l, u) ∈ R×R×R with l ≤ w ≤ u, define the discretization mechanism as
M(w; l, u) = { u, w.p. w−lu−l l, w.p. u−wu−l ,
(2)
where w.p. is the shorthand notation for “with probability”.
Algorithm 1 FEDDISCRETE 1: Input: Initial model weight w0 ∈ Rd, total training rounds T , the participants size K, and the
learning rate {ηt}T−1t=0 and a positive sequence {σi}Ni=1. 2: for t = 0, 1, 2, . . . , T − 1 do 3: The sever randomly selects an index set St with |St| = K and broadcasts wt to the client i if i ∈ St. 4: For the ith client, where i ∈ St, it performs the local training to obtain wt+1i and samples
two random variables ξti and ζ t i from the truncated Gaussian TN(0, σi; 0, 1). Then it computes and uploads lti = minj∈[d]{[wti ]j −wt} − ξti and uti = maxj∈[d]{[wti ]j −wt} + ζti to the server.
5: The sever computes lt = mini∈St{lti} and ut = maxi∈St{uti} then broadcasts lt, ut to clients in St.
6: For the ith client, where i ∈ St, it applies the discretization mechanismM is an elementwise fashion and uploads the discrete model weightM(wt+1i −wt; lt, ut) to the server. 7: The server conducts the sanity check for {M(wt+1i −wt; lt, ut)}i∈St , i.e., validates whether all elements of wt+1i are either l
t or ut. Form the set S′t ⊆ St to collect all the clients’ index passing the sanity check and compute wt+1 = wt+ηt 1|S′t| ∑ i∈S′t M(wt+1i − wt; lt, ut).
8: end for
We close this section by making following comments.
• Discretization is a widely applied technique, for example, in influence maximization Kempe et al. (2003), the algorithm needs to simulate the propagation from a probabilistic graph that is consists of a set of edges with activation probabilities in [0, 1]. It is also can be regarded as a special form of quantization that is widely used in the distributed optimization (Alistarh et al., 2017; Reisizadeh et al., 2020) to improve communication efficiency. Compared with prior discretization works, this is the first work to adopt discretization to protect FL from weight poisoning attack.
• Compared with the FedAvg, although an additional round of communication is required in FEDDISCRETE to perform the discretization mechanism. We argue that FEDDISCRETE is more communication-efficient than FedAvg. Assume each scalar takes 64bits, then for the
t-th round, the total bits communicated are 128dK for FedAvg, while for FEDDISCRETE are 64dK + 128K + dK. For large d, FEDDISCRETE communicates less bits. 1
• Although the discretization mechanism outputs an unbiased estimation of wt+1i , the variance of the estimatorM(wt+1i ) can be large. To mitigate this issue, one can compute more finely-grained upper bounds and lower bounds. For example, assume each client wants to train a neural network. Then, instead of computing the maximum and minimum values over the entire w, the client could compute layer-wise maximum and minimum values. And the discretization mechanism could be applied layer-wise with tighter upper bounds and lower bounds. This leads to smaller variance in the estimator at the cost of increasing the communicated bits.
• Intuitively, the discretization mechanism is effective in defending weight poisoning attacks as the judiciously crafted adversary model is discretized. For example, consider the model replacement attack in Eq. 3 of Bagdasaryan et al. (2020), once the malicious model wtA is discretized intoM(wtA), the model replacement becomes ineffective.

heading: 4 THEORETICAL ANALYSIS
text: In this section, we analyze the utility of the discretization mechanism and the convergence property of the FEDDISCRETE. Due to limited space, complete proofs are deferred to the appendix.
We first introduce the notations are used throughout the paper. [w]j denotes the jth coordinate of the vector w. Unless specified otherwise, ‖·‖ and ‖·‖∞ are the Euclidean norm and infinity norm respectively. To avoid the cluttered notation, we use M(·) instead of M(·; ·, ·) when there is no confusion. And ifM is applied over a vector, we mean to apply it in a element-wise fashion. Here, [d] represents {1, · · · , d}.

heading: 4.1 UTILITY ANALYSIS
text: The first lemma shows that the discretization mechanism produces an unbiased estimator with bounded variance. Lemma 4.1. For any w ∈ Rd and (l, u) ∈ R×R such that l ≤ minj∈[d] [w]j < maxj∈[d] [w]j ≤ u, then
• E[M(w; l, u)] = w;
• E[‖M(w; l, u)−w‖2] ≤ d(u−l) 2 4 and E[‖M(w; l, u)−w‖ 2 ] ≤ ‖w‖ 2 4 .
A natural question to ask is that how far is the averaged local model weights w̄t := ∑ i∈St−1 w t−1 i
from its discretized counterpart w̄tM := ∑ i∈St−1M(w t−1 i ). The next theorem characterizes the distance between w̄t and w̄tM. Theorem 4.2. For any communication round t ≤ T and any β ∈ (0, 1), there exists t =
O
( (ut−lt)
√ log 2dβ√
K
) such that
P (∥∥w̄t − w̄tM∥∥∞ ≤ t) ≥ 1− β.

heading: 4.2 ROBUSTNESS ANALYSIS
text: Next, we show the discrete mechanism is robust to random weight poisoning and can recover the original weight from local models against a limited number of independent targeted weight poisonings. To maximize the attack impact, the attacker choose to inverse the discrete local updates to
1Each model weight takes 64d bits. For FedAvg, server broadcasts the global model weight and clients upload the local model weights, so the total bits are 128dK. For FEDDISCRETE, 64dK is the cost for the server broadcasting the global model to K server. 128K is the cost for uploading and broadcasting the upper bounds and lower bounds. Since the discretized model weight M(wt+1i ) can only taking two values, the clients can indeed just upload d bits string and the server can recover the M(wt+1i ).
attack the global model. If the intend update of the jth weight [w]j is u, the attacker uploads l to the server, and vice versa.
Theorem 4.3. Suppose there are F attackers out of total N clients and denote w̄M = 1N ∑N i=1 wi, then for any j ∈ [d],
[E[w̄M]]j = 1
N ( N−F∑ i=1 [wi]j − N∑ i=N−F+1 [wi]j ) + (h+ l) F N . (3)
More importantly, FEDDISCRETE has an asymptotically non-bias estimation when the number of clients approaches to +∞ with a fixed number of attackers. Corollary 4.3.1. LetN be +∞, for some fixed F attackers, the expectation of the averaged discrete weights is E[w̄M] = w.
Discussion. The above theorem and corollary have shown the robustness against the weights poisoning attacks, such as IBAs and APAs. Besides, another important reason is the discretization mechanism limits the modification ability of the adversaries as shown in Figure 1. For example, if the clean aggregated model’s weight is [0.1,−2.3, 3.8], the IBA or APA could work while modifying the weight from [0.1,−2.3, 3.8] to [1, 0.2, 0.4], where the weight difference between clean and poisoned model is [0.9,−2.5,−3.4]. However, due to the discretization mechanism, while we only have 1 attacker among 100 clients, its modification could only be 0 or ±0.01 with the upper bound u = 1 and the lower bound l = 0. In this case, the adversary can not achieve its goal in any manner.

heading: 4.3 CONVERGENCE ANALYSIS
text: In this section, we prove the convergence of Algorithm 1 by instantiating the optimization algorithm for generating local model weights as the FedProx(Li et al., 2020). Specifically, at the tth round, in line 4 of Algorithm 1, the ith selected client produce the local model weight wt+1i ≈ Fi(w) + µ 2 ‖w−w t‖2 in the sense that ∥∥∇Fi(wt+1i ) + µ(wt+1i −wt)∥∥ ≤ γ ‖∇Fi(wt)‖ for some properly chosen µ > 0 and γ > 0. The Assumption 4.1 is made throughout the whole section. Assumption 4.1.
1. (Smoothness) For all i ∈ [N ], Fi(w) is L-smooth, i.e., ‖∇Fi(w)−∇Fi(w′)‖ ≤ L ‖w −w′‖ for some L > 0 and all (w,w′) ∈ Rd × Rd.
2. (Lower-bounded eigenvalue) The minimal eigenvalue of the Hessian of the client loss function∇2Fi(w) is uniformly bounded below by a constant λmin ∈ R.
3. (Bounded dissimilarity) For all i ∈ [N ] and any w ∈ Rd, Ei[‖∇Fi(w)‖2] ≤ B2 ‖∇f(w)‖2 , where the expectation is taken with respect to the client index i.
4. (Algorithmic choices) In Algorithm 1 , in line 3, the ith client is picked with the probability pi; line 7, the step size ηt = 1.
Theorem 4.4. Consider the Algorithm 1 instantiated with FedProx. If µ is chosen to satisfy µ > λmin, and K,µ, γ is chosen properly such that κ = 1−γBµ − LB(1+γ) µµ̄ − L(1+γ)2B2
2µ̄2 − LB2(1+γ)2
Kµ̄2 (2 √ K + 1)− B(1+γ) µ̄ √ K − LNB 2(1+γ)2 8K2pminµ̄2 > 0, then after T rounds,
min t∈[T−1]
E[ ∥∥∇f(wt)∥∥] ≤ f(w0)− f(w∗)
κT .

heading: Remark
text: • The rate of convergence of FEDDISCRETE is the same as that of FedProx but with worse constant due to the discretization mechanism.
• One can also prove the convergence of the FEDDISCRETE when the local clients perform the fixed number of stochastic gradient descent steps as FedAVG. Then the convergence result is a special case of the FedPAQ (Reisizadeh et al., 2020) when q is set to 1/4.

heading: 5 EXPERIMENTAL EVALUATION
text: In this section, we examine the effect of FEDDISCRETE on the four image benchmark datasets: MNIST (LeCun et al., 1998), Fashion-MNIST (FMNIST) (Xiao et al., 2017), SVHN (Netzer et al., 2011), and CIFAR-10 (Krizhevsky et al., 2009). For MNIST and FMNIST, we adopt a two-layer CNN for image classification; for SVHN and CIFAR-10, the small network from the Pytorch library2 only achieves around 50% accuracy, so that we re-design a small VGG (Simonyan & Zisserman, 2014) for them. The training data and the testing data are fed into the network directly in each client, and for each client, the size of the training data is the total number of the training samples divided by the number of the clients for i.i.d setting. For non-i.i.d setting, we sort the data by digit labels first, then divide the datasets into 2N shards of size |D|2N , and assign each of N clients 2 shards, which is the same setting as (McMahan et al., 2017). We use the local SGD as the optimization algorithm for each client, where the local learning rate is set as 0.03 for MNIST/FMNIST and 0.015 for SVHN/CIFAR-10. And the global learning rate ηt is set to 1 for all t. Considering the randomness from the discrete mechanism, we run the test experiments five times independently to obtain an averaged value. To evaluate the performance of different approaches, we use different metrics including accuracy/utility for model performance, attack success rate (ASR)3 for attack performance and the number of communication rounds (CRs), for communication cost. Any approach with a high accuracy and a low ASR indicates a good and practical defense solution. The proposed models are implemented using Pytorch, and all experiments are done with a single GPU NVIDIA Tesla V100 on the local server. Experiments on MNIST and FMNIST can be finished within an hour with 10 CRs, and experiments on SVHN and CIFAR-10 need about 2 hours with 15 CRs.
Evaluation on Discrete Mechanism. Here, we first test the effectiveness of the discrete mechanism in FL. In Figure 2 and 3, the results demonstrate three observations: 1) for the discrete model, in i.i.d setting, it performs closer to continuous model aggregation than that in the non-i.i.d setting; 2) the more complex and difficult tasks, i.e., CIFAR-10 > SVHN > FMNIST > MNIST, are more sensitive to the discrete mechanism; 3) when increasing the number of total clients, the model utility loss between continuous and discrete models are diminishing. For example, while having 350 clients in FL, the difference between continuous and discrete models is less than 1% and 2% for all tasks in the i.i.d and non-i.i.d settings, respectively. These results verify the previous analysis in Theorem
2https://pytorch.org/tutorials/beginner/blitz/cifar10 tutorial.html. Note that, we use the default setting provided from Pytorch for MNIST and Fashion-MNIST. For SVHN and CIFAR-10, we use VGG9 that is modified from VGG11 for balancing the memory usage and the model utility.
3The precise definition of ASR varies under different attacks. We will give the precise definition in the subsequent sections.
4.3. In summary, the discrete mechanism is more practical for customer-related applications, e.g., smartphones or IoT devices, since it usually involves millions of clients during training.
Evaluation on Availability Poisoning Attacks. The integrity poisoning attacks are evaluated from multi-angles. In Figure 4, we fix the number of clients as 100, and evaluate the increasing number of attackers in both i.i.d and non-i.i.d settings. The attack success rate (ASR) in APAs is the utility loss between before and after attacks. The results show that one or a few attackers, i.e., a small fraction of attackers of all clients, cannot successfully poison the model. For example, when there are more than 100 clients, any single adversarial client only gets the 0% ASR for all tasks in both i.i.d and non-i.i.d settings. Figure 5 and 6 show the results of model utility with a fixed number of attackers in both i.i.d and non-i.i.d settings. The results consistently show that for a fixed number of attackers, increasing the number of the total clients will improve the global model’s utility.
Table 1: FEDDISCRETE against IBAs
No Defense FEDDISCRETE Attack ASR UL ASR UL CAS 81.90% 2.40% 0.00% 0.00% DBA 81.30% 4.70% 0.00% 0.00%
Table 2: Compare with other defense baselines
Defenses ASR UL No defense 81.90% 2.40% Krum 100% 35.50% FoolsGold 100% 39.90% Auror 100% 66.10% FedDP 0% 13.30% FEDDISCRETE 0% 0%
Compared with prior defense against IBAs (Blanchard et al., 2017; Bagdasaryan et al., 2020; Shen et al., 2016; Fung et al., 2018), based on our current knowledge, not many existing works have well studied the availability poisoning attacks in FL. Due to the adversary have more flexible attack options of the training process in APAs, most APAs could easily break the defense solutions for IBAs.
Evaluation on Integrity Backdoor Attacks. Next, we evaluate the FEDDISCRETE against the state-of-the-art backdoor attacks, such as constrain-and-scale (CAS) (Bagdasaryan et al., 2020) and DBA (Xie et al., 2019) in Table 1, where utility loss (UL) is the difference of model utility between clean and poisoned models, and the attack success rate (ASR) in IBAs is the percentage of poisoned samples that are classified as the target class by the backdoored model. Due to the variants of studied tasks in prior works, we evaluate the most common task, i.e., CIFAR-10, for all backdoor attacks in the i.i.d setting. We use the default attack settings same as the original paper: one attacker for CAS and four attackers for DBA. Here, ASR is the backdoor attack success rate, and UL is the utility loss compared with none-attack FL. The results show that FEDDISCRETE can easily defend the backdoor attacks against CAS and DBA. By mitigating the impacts of the attackers, in addition to the successful IBAs defense, FEDDISCRETE can even improve the model utility.
We also compare FEDDISCRETE with other backdoor defense systems against CAS in FL: Krum (Blanchard et al., 2017), FoolsGold (Fung et al., 2018), Auror (Shen et al., 2016), and FedDP (Geyer et al., 2017) in Table 2. The results show that Krum, FoolsGold, and Auror can not well defend the backdoor attacks in FL. DP can achieve a good backdoor defense, but scarifies the model utility. FEDDISCRETE can achieve the best ASR and UL in all defense methods.
Discussion on Client Inference Attacks. Prior inference attacks (Blanchard et al., 2017; Pyrgelis et al., 2017; Ganju et al., 2018) require to get the original or similar local client model, i.e., a continuous local model. Then, the malicious server could explore the privacy of the training data from its
continuous local model. However, a discrete local model cannot be used to infer any valuable information. The malicious server could compute the continuous global model, but it would not be useful to explore the privacy information of each client. Another popular inference defense technique is the homomorphic encryption (HE) (Gentry et al., 2009). Although HE can perfectly defend the inference attacks from the malicious server, it requires high computation cost and cannot defend against other weight-based poisoning attacks. Similarly, differential privacy (DP) (Geyer et al., 2017) could also be used for defending inference attacks. However, Hu et al. (2021) have shown that DP will lose too much utility of the global model while providing strong privacy protection. FEDDISCRETE is a concise but practical approach that can naturally defend the client inference attacks from the malicious server with a more efficient communication protocol.

heading: 6 LIMITATIONS AND DISCUSSIONS
text: FEDDISCRETE can defend both data poisoning attacks and weight poisoning attacks in FL, since data poisoning attacks are equal to change the clean model to the poisoned model. However, FEDDISCRETE also has two limitations: (1) It could not work in the cross-silos federated learning setting. If we want to mitigate the adversarial impact and achieve a non-biased aggregated model, it requires there are many clients could join in training in each round. However, it would not be an issue in the cross-devices setting involving thousands or even more clients in each round of training; (2) It could not defend the byzantine attacks through our discretization aggregation mechanism, since the aggregated model represents the majority of interests in FEDDISCRETE. However, the byzantine defense via robust local training could still work in our framework, where the local client can recognize the poisoned model or only leverage the valuable information from the poisoned model to train the local model via knowledge distillation (Lee et al., 2021). Our next step is to further explore a novel defense mechanism that can be more scalable for various adversarial environments.

heading: 7 CONCLUSION
text: In this paper, we proposed a new FL approach that applies the discrete mechanism with adaptive weight range for protecting FL. To our best knowledge, it is the first work that don’t require the server to do excessive computation, but successfully defend against various attacks, including availability poisoning attacks, integrity backdoor attacks, and inference attacks. We also theoretically analyze the utility, robustness, and convergence of our proposed discrete mechanism in FL. One limitation of this work is the proposed system cannot defend the attacks well with a small number of clients or face a large fraction of the attackers, which becomes the next step of our future research.

heading: A APPENDIX

heading: A.1 PROOF OF LEMMA 4.2.
text: Proof. Notice that for any scalar w ∈ Rn and l ≤ w ≤ u, by the definition ofM(.; l, u), one can verify that E[M(w; l, u)] = w, therefore E[M(w; l, u)] = w. Furthermore,
E[‖M(w; l, u)−w‖2] = d∑ j=1 E[([M(w; l, u)]j − [w]j)2]
= d∑ j=1 ( E[[M(w; l, u)]2j ]− [w]2j ) =
d∑ j=1 ( (u+ l)[w]j − lu− [w]2j ) =
d∑ j=1
[( u− l
2
)2 − ( [w]j − ( u+ l
2
))2]
= d
( u− l
2
)2 − d∑ j=1 ( [w]j − ( u+ l 2 ))2 ≤ d(u− l) 2 4 .
Moreover,
d
( u− l
2
)2 − d∑ j=1 ( [w]j − ( u+ l 2 ))2 =

heading: A.2 PROOF OF THEOREM 4.2.
text: Before proving the Theorem 4.2, a standard probability bound is required.
Lemma A.1. Let {Xi}ni=1 be a sequence of i.i.d continuous random variables, whose support is on R. Then for any b ∈ R
P (
max i∈[n]
Xi ≥ b ) ≤ nP(Xi ≥ b).

heading: Proof.
text: P (
max i∈[n]
Xi ≥ b )
= 1− P(max i∈[n] Xi ≤ b) = 1− P(X1 ≤ b, · · · , Xn ≤ b)
= 1− n∏ j=1 P(Xj ≤ b) = 1− (1− P(Xj ≥ b))n for any j
Let f(t) := 1− nt− (1− t)n for t ∈ [0, 1]. As f ′(t) ≤ 0 and f(0) = 0, f(t) ≤ 0 for all t ∈ [0, 1]. Therefore, 1− (1− t)n ≤ nt. Take t = P(Xj ≥ b), we arrive
P (
max i∈[n]
Xi ≥ b ) ≤ nP(Xi ≥ b).
Now we are ready to prove Theorem 4.2.
Proof. For any j ∈ [d], |[w̄t]j − [w̄tM]j | ≤ ut − lt and Var ([w̄t]j − [w̄tM]j) ≤ (ut − lt)2/4 due to Lemma 4.1. By Bernstein inequality, for any j ∈ [d] and > 0
P (∣∣[w̄t]j − [w̄tM]j∣∣ ≥ ) ≤ 2 exp ( − K 2
2 1K ∑ i∈St Var ([w̄ t]j − [w̄tM]j) + 2 3 (u t − lt)
)
≤ 2 exp ( − K 2
(ut−lt)2 2 + 2 3 (u t − lt) ) By Lemma A.1,
P (
max j∈[d]
∣∣[w̄t]j − [w̄tM]j∣∣ ≥ ) ≤ 2d exp ( − K 2
(ut−lt)2 2 + 2 3 (u t − lt)
)
Therefore, for any β > 0, there exists = O
( (ut−lt)
√ log 2dβ√
K
) such that
P ( maxj∈[d] |[w̄t]j − [w̄tM]j | ≤ ) holds with probability at least 1− β.

heading: A.3 PROOF OF THEOREM 4.3
text: Proof. Due to the weight discretization mechanism, the adversary can only return u or l for each coordinate of the model weight. In order to not return the correct information, the adversary could choose to return the opposite feedback to attack the model, i.e., return u if the original return is l, and vice versa. Therefore, we denote, for any l ≤ w ≤ u,
Madv(w) = { l, w.p.w−lh−l h, w.p.h−wh−l
Under the scenario that there are F attackers, for any j ∈ [d],
[E[w̄M]]j = E
[ 1
N ( N−F∑ i=1 [M(wi)]j + ∑ i=N−F+1 [Madv(wi)]j )]
= 1
N N−F∑ i=1 [wi]j + 1 N N∑ i=N−F+1 ((h+ l)− [wi]j) (4)
= 1
N ( N−F∑ i=1 [wi]j − N∑ i=N−F+1 [wi]j ) + (h+ l) F N . (5)

heading: A.4 PROOF OF THEOREM 4.4
text: Proof. The proof is inspired by the analysis in Theorem 4 of (Li et al., 2020).
To proceed with the analysis, we first introduce some notations. At the tth round, for the all i ∈ S ′t, define w̃t+1 = wt + 1|S′t| ∑ i∈S′t ( wt+1i −wt ) , w̄t+1 = wt + ∑ i∈[N ] pi(w t+1 i − wt), and ŵt+1i = arg minw hi(w;w t) := Fi(w) + µ 2 ‖w −w
t‖2. w̃t+1 is the ghost global model as if the discretization mechanism is not applied to the local model weights; w̄t+1 is another ghost global model as if all clients participate in the tth round training and no discretization mechanism is applied ; ŵt+1i is the exact minimizer of the strongly convex function hi(w). These points reference points are crucial for the analysis. Define the gradient residual et+1i = ∇Fi(w t+1 i ) + µ(w t+1 i −wt), then wt+1i −wt = − 1µ∇Fi(w t+1 i ) + 1 µe t+1 i . Therefore,
w̄t+1 −wt = ∑ i∈[n] pi(w t+1 i −w t) = − 1 µ ∑ i∈[n] pi∇Fi(wt+1i ) + 1 µ ∑ i∈[n] pie t+1 i . (6)
Since µ is chosen to satisfy µ > λmin, then hi(w;wt) is µ̄-strongly convex. By the strong convexity of hi, ∥∥wt+1i − ŵt+1i ∥∥2 ≤ 1µ̄ (wt+1i − ŵt+1i )>(∇hi(wt+1i )−∇hi(ŵt+1i ))
≤ 1 µ̄ ∥∥wk+1i − ŵt+1i ∥∥∥∥∇hi(wt+1i )−∇hi(ŵt+1i )∥∥ , which, together with the fact that ŵt+1i is the minimizer of hi(w), implies
∥∥wt+1i − ŵt+1i ∥∥ ≤ 1µ̄ ∥∥∇hi(wt+1i )−∇hi(ŵt+1i ))∥∥ = 1
µ̄ ∥∥∇hi(ŵt+1i ))∥∥ = 1µ̄ ∥∥∇Fi(wt+1i ) + µ(wt+1i −wt)∥∥ ≤ γ µ̄
∥∥∇Fi(wt)∥∥ (7) Again use the same analysis, one has
∥∥ŵt+1i −wt∥∥ ≤ 1µ̄∇Fi(wt). Therefore, together with Eq. 7,∥∥wt+1i −wt∥∥ ≤ ∥∥wt+1i − ŵt+1i ∥∥+ ∥∥ŵt+1i −wt∥∥ ≤ 1 + γµ̄ ∥∥∇Fi(wt)∥∥ . (8) Therefore, one can bound the distance from the ghost global model w̄t+1 to the current global weight as
∥∥w̄t+1 −wt∥∥ = ∥∥∥∥∥∥ ∑ i∈[N ] pi(w t+1 i −w t) ∥∥∥∥∥∥ ≤ ∑ i∈[N ] pi ∥∥wt+1i −wt∥∥
≤ 1 + γ µ̄ ∑ i∈[N ] pi ∥∥∇Fi(wt)∥∥ (by Eq. 8)
≤ 1 + γ µ̄ √∑ i∈[N ] pi ‖∇Fi(wt)‖2 (Jensen’ Inequality)
= 1 + γ
µ̄
√ Ei[‖∇Fi(wt)‖2]
≤ B(1 + γ) µ̄ ∥∥∇f(wt)∥∥ (by Assumption 4.1 (3)) (9) Note that∥∥∥∥∥∥ ∑ i∈[n] pi ( ∇Fi(wt+1i )− e t+1 i −∇Fi(w t) )∥∥∥∥∥∥ ≤ ∑ i∈[n] pi (∥∥∇Fi(wt+1i )−∇Fi(wt)∥∥+ ∥∥et+1i ∥∥)
≤ ∑ i∈[n] pi ( L ∥∥wt+1i −wt∥∥+ ∥∥et+1i ∥∥)
Eq. 8 ≤ ( L(1 + γ)
µ̄ + γ ) ∑ i∈[n] pi ∥∥∇Fi(wt)∥∥
=
( L(1 + γ)
µ̄ + γ
) Ei[∇Fi(wt)]
Eq. 8 ≤ B ( L(1 + γ)
µ̄ + γ
)∥∥∇f(wt)∥∥ . (10)
By Assumption 4.1 (1), one has
f(w̄t+1) ≤ f(wt) +∇f(wt)>(w̄t+1 −wt) + L 2 ∥∥w̄t+1 −wt∥∥2 Eq. 6
≤ f(wt) +∇f(wt)> − 1
µ ∑ i∈[n] pi∇Fi(wt+1i ) + 1 µ ∑ i∈[n] pie t+1 i + L 2
∥∥w̄t+1 −wt∥∥2 = f(wt) +∇f(wt)> − 1 µ ∑ i∈[n] pi ( ∇Fi(wt+1i )− e t+1 i −∇Fi(w t) ) − 1 µ ∇f(wt)
 + L
2 ∥∥w̄t+1 −wt∥∥2 ≤ f(wt)− 1
µ ∥∥f(wt)∥∥2 − 1 µ f(wt)> ∑ i∈[n] pi ( ∇Fi(wt+1i )− e t+1 i −∇Fi(w t) )
+ L
2 ∥∥w̄t+1 −wt∥∥2 ≤ f(wt)− 1
µ ∥∥f(wt)∥∥2 + 1 µ ∥∥f(wt)∥∥ ∥∥∥∥∥∥ ∑ i∈[n] pi ( ∇Fi(wt+1i )− e t+1 i −∇Fi(w t) )∥∥∥∥∥∥
+ L
2 ∥∥w̄t+1 −wt∥∥2 Eq. 10,Eq. 9
≤ f(wt)− 1 µ ∥∥f(wt)∥∥2 + B µ
( L(1 + γ)
µ̄ + γ )∥∥∇f(wt)∥∥2 + L 2 ( B(1 + γ) µ̄ )2 ∥∥∇f(wt)∥∥2
(11) = f(wt)− (
1− γB µ − LB(1 + γ) µµ̄ − L(1 + γ) 2B2 2µ̄2 )∥∥∇f(wt)∥∥2 (12) By mean-value theorem and triangular inequality, for some α ∈ [0, 1]
f(w̃t+1) ≤ f(w̄t+1) + ∥∥∇f(αw̃t+1 + (1− α)w̄t+1)∥∥ ∥∥w̃t+1 − w̄t+1∥∥
≤ f(w̄t+1) + (∥∥∇f(αw̃t+1 + (1− α)w̄t+1)−∇f(wt)∥∥+ ∥∥∇f(wt)∥∥) ∥∥w̃t+1 − w̄t+1∥∥
≤ f(w̄t+1) + ( L ∥∥αw̃t+1 + (1− α)w̄t+1 −wt∥∥+ ∥∥∇f(wt)∥∥) ∥∥w̃t+1 − w̄t+1∥∥
≤ f(w̄t+1) + ( L( ∥∥w̃t+1 −wt∥∥+ ∥∥w̄t+1 −wt∥∥) + ∥∥∇f(wt)∥∥) ∥∥w̃t+1 − w̄t+1∥∥
(13)
Taking expectation with respect to the random index set S ′t, one gets
ES′t [f(w̃ t+1)] ≤ f(w̄t+1) + ( L ∥∥w̄t+1 −wt∥∥+ ∥∥∇f(wt)∥∥)ES′t ∥∥w̃t+1 − w̄t+1∥∥
+ LES′t [ ∥∥w̃t+1 −wt∥∥∥∥w̃t+1 − w̄t+1∥∥]
≤ f(w̄t+1) + ( L ∥∥w̄t+1 −wt∥∥+ ∥∥∇f(wt)∥∥)ES′t ∥∥w̃t+1 − w̄t+1∥∥
+ LES′t [ (∥∥w̃t+1 − w̄t+1∥∥+ ∥∥w̄t+1 −wt∥∥) ∥∥w̃t+1 − w̄t+1∥∥]
= f(w̄t+1) + ( 2L ∥∥w̄t+1 −wt∥∥+ ∥∥∇f(wt)∥∥)ES′t ∥∥w̃t+1 − w̄t+1∥∥
+ LES′t [ ∥∥w̃t+1 − w̄t+1∥∥2] (14)
By the sampling scheme, one has
ES′t ∥∥w̃t+1 − w̄t+1∥∥2 ≤ 1 |S ′t| Ei[ ∥∥wt+1i − w̄t+1∥∥2]
≤ 1 |S ′t|
Ei[ ∥∥wt+1i −wt∥∥2 + ∥∥wt − w̄t+1∥∥2 + 2(wt+1i −wt)>(wt − w̄t+1)]
≤ 1 |S ′t|
Ei[ ∥∥wt+1i −wt∥∥2 (by Ei(wt+1i ) = w̄t+1)
Eq. 8 ≤ 1 |S ′t|
(1 + γ)2 µ̄2 Ei[ ∥∥∇Fi(wt)∥∥2]
≤ B 2 |S ′t| (1 + γ)2 µ̄2 ∥∥∇f(wt)∥∥2 (by Assumption 4.1 (3)). (15)
Combining Eq. 14, Eq. 15, and Eq. 9, together with the fact that ES′t ∥∥w̃t+1 − w̄t+1∥∥ ≤√
ES′t ‖w̃t+1 − w̄t+1‖ 2 as a result of the Jesen’s inequality, one reaches to
ES′t [f(w̃ t+1)] ≤ f(w̄t+1) +
( 2L
B2√ |S ′t| (1 + γ)2 µ̄2 + B√ |S ′t| (1 + γ) µ̄ + L B2 |S ′t| (1 + γ)2 µ̄2 )∥∥∇f(wt)∥∥2 = f(w̄t+1) + ( LB2(1 + γ)2
|S ′t|µ̄2 (2 √ |S ′t|+ 1) + B(1 + γ) µ̄ √ |S ′t|
)∥∥∇f(wt)∥∥2 . (16)
Combine Eq. 16 and Eq. 11, one reaches to
ES′t [f(w̃ t+1)] ≤ f(wt)− ( 1− γB µ − LB(1 + γ) µµ̄ − L(1 + γ) 2B2
2µ̄2 −(
LB2(1 + γ)2 |S ′t|µ̄2 (2 √ |S ′t|+ 1) + B(1 + γ) µ̄ √ |S ′t|
))∥∥∇f(wt)∥∥2 (17)
Taking the expectation with respect to the discretization mechanism, EM[wt+1] = w̃t+1 by Lemma 4.1. Since f is L-smooth,
EM[f(wt+1)] ≤ f(w̃t+1) + L
2 EM[ ∥∥wt+1 − w̃t+1∥∥2] = f(w̃t+1) + L
2
1
|S ′t|2 EM  ∥∥∥∥∥∥ ∑ i∈S′t ( M(wt+1i −w)− (w t+1 i −w) )∥∥∥∥∥∥ 2 
≤ f(w̃t+1) + L 8|S ′t|2 ∥∥∥∥∥∥ ∑ i∈S′t (wt+1i −w) ∥∥∥∥∥∥ 2
(by Lemma 4.1)
≤ f(w̃t+1) + L 8|S ′t|2 ∑ i∈[n] ∥∥wt+1i −w∥∥2 +∑ i 6=j (wt+1i −w) >(wt+1j −w)  ≤ f(w̃t+1) + L
8|S ′t|2 ∑ i∈[n] ∥∥wt+1i −w∥∥2 +∑ i 6=j ∥∥wt+1i −w∥∥ ∥∥wt+1j −w∥∥ 
≤ f(w̃t+1) + LN 8|S ′t|2 ∑ i∈[n] ∥∥wt+1i −w∥∥2  (by 2 ‖a‖ ‖b‖ ≤ ‖a‖2 + ‖b‖2)
≤ f(w̃t+1) + LN 8|S ′t|2pmin ∑ i∈[n] pmin ∥∥wt+1i −w∥∥2  ≤ f(w̃t+1) + LN
8|S ′t|2pmin ∑ i∈[n] pi ∥∥wt+1i −w∥∥2  ≤ f(w̃t+1) + LN
8|S ′t|2pmin ∑ i∈[n] pi (1 + γ)2 µ̄2 ∥∥∇Fi(wt)∥∥2  ≤ f(w̃t+1) + LN
8|S ′t|2pmin B2(1 + γ)2 µ̄2 ∥∥∇f(wt)∥∥2 (18)
Put Eq. 18 and Eq. 17 together, we reach to
EM,S′t [f(w t+1)] ≤ f(wt)− ( 1− γB µ − LB(1 + γ) µµ̄ − L(1 + γ) 2B2
2µ̄2 −(
LB2(1 + γ)2 |S ′t|µ̄2 (2 √ |S ′t|+ 1) + B(1 + γ) µ̄ √ |S ′t|
) − LNB 2(1 + γ)2
8|S ′t|2pminµ̄2 )∥∥∇f(wt)∥∥2 (19)
When there is no adversary, then |S ′| = K, then
EM,S′t [f(w t+1)] ≤ f(wt)− κ ∥∥∇f(wt)∥∥2 Finally, taking the total expectation with respect to all randomness and by telescoping, one reaches
κ T−1∑ t=0 E[‖∇f(wt)‖]2 ≤ f(w0)− f(w∗).
Divide T on both sides, then
min t∈[T−1]
E[‖∇f(wt)‖] ≤ 1
T T−1∑ t=0 E[‖∇f(wt)‖]2 ≤ f(w0)− f(w∗) κT .

Review summaries:
Federated learning (FL) has been shown to be vulnerable to weight poisoning attacks. An attacker who controls malicious clients can poison the clients’ model weights such that a backdoor to perform availability poisoning attacks, integrity backdoor attacks and inference attacks. In this work, the authors proposed a new FL algorithm called FedDiscrete, which probabilistically discretizes the clients’ model weights into two different values. The authors derived the convergence of FedDiscrete and empirically showed its performance against existing attacks. However, I am worried about the theoretical analysis on the robustness, as well as the empirical robustness against adaptive attacks.

This paper proposes a secure federated learning framework against weight poisoning. The key component in the framework is the discretization mechanism which works well with a sufficient number of clients. Theoretical analysis of the robustness and convergence is provided. Lastly, numerical analysis is provided to verify the performance of the proposed method.