Certified Robustness for Free in Differentially Private Federated Learning
Authors: Chulin Xie
Yunhui Long
Pin-Yu Chen
Krishnaram Kenthapadi
Bo Li
Venue: ICLR 2022 Submitted (2022)
Keywords: Certified Robustness
Differential Privacy
Federated Learning

Abstract: Federated learning (FL)  provides an efficient training paradigm to jointly train a global model leveraging data from distributed users.
As the local training data comes from different users who may not be trustworthy, several studies have shown that FL is vulnerable to poisoning attacks where adversaries add malicious data during training. On the other hand,  to protect the privacy of users, FL is usually trained in a differentially private way (DPFL). Given these properties of FL, in this paper, we aim to ask: Can we leverage the innate privacy property of  DPFL to provide robustness certification against poisoning attacks? Can we further improve the privacy of FL to improve such certification?
To this end, we first investigate both the user-level and instance-level privacy of FL, and propose novel randomization mechanisms and analysis to achieve improved differential privacy.
We then provide two robustness certification criteria: certified prediction and certified attack cost for DPFL on both levels. Theoretically, given different privacy properties of DPFL, we prove their certified robustness under a bounded number of adversarial users or instances. 
Empirically, we conduct extensive experiments to verify our theories under different attacks on a range of datasets. We show that the global model with a tighter privacy guarantee always provides stronger robustness certification in terms of the certified attack cost, while may exhibit tradeoffs regarding the certified prediction.
We believe our work will inspire future research of developing certifiably robust DPFL based on its inherent properties.

Under review as a conference paper at ICLR 2022
CERTIFIED ROBUSTNESS FOR FREE IN DIFFEREN- TIALLY PRIVATE FEDERATED LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Federated learning (FL) provides an efficient training paradigm to jointly train a global model leveraging data from distributed users. As the local training data comes from different users who may not be trustworthy, several studies have shown that FL is vulnerable to poisoning attacks where adversarics add malicious data during training. On the other hand, protect the privacy of users, FL is usually trained in a differentially private manner (DPFL). Given these properties of FL., this paper, we aim to ask: Can we leverage the innate privacy property of DPFL provide robustness certification against poisoning attacks? Can we further improve the privacy of FL to improve such certification? To this end, we first investigate both user-level and instance-level privacy for FL, and propose novel randomization mechanisms and analysis to achieve improved differential privacy. We then provide two robustness certification criteria: certified prediction and certified attack cost for DPFL on both levels. Theoretically, given different privacy properties of DPFL., we prove their certified robustness under a bounded number of adversarial users instances. Empirically, we conduct extensive experiments to verify our theories under different attacks range of datasets. We show that the global model with a tighter privacy guarantee always provides stronger robustness certification in terms of the certified attack cost, while it may exhibit tradeoffs regarding the certified prediction. We believe our work will inspire future research of developing certifiably robust DPFL based on its inherent properties.
INTRODUCTION
Federated Learning (FL), which aims to jointly train a global model with distributed local data, has been widely applied in different applications, such as finance (Yang et al. 2019b). medical analysis (Brisimi et al.],120111_13_____2 2018), and user behavior prediction (Hard et al., 2018 Yang et al. 2018] 2019ah. However, the fact that the local data and the training process are entirely controlled by the local users who may be adversarial raises great concerns from both security and privacy perspectives. In particular, recent studies show that FL is vulnerable to different types of training-tine time attacks, such as model poisoning (Bhagoji et al. 2019). backdoor attacks (Bagdasaryan et al.) 2020 Xie et al.) 2019: Wang al., 2020), and label-flipping attacks (Fung [2220). Further, privacy concerns have motivated the need to keep the raw data on local devices without sharing. However, sharing other indirect information such as gradients or model updates as part of the FL training process can also leak sensitive user information (Zhu et al. 2019 Geiping et al. 2020 Bhowmick et al. 2018)
Melis al. 2019). As result, approaches based on differential privacy (DP) (Dwork & Roth 2014). homomorphic encryption (Bost et al. 20155 Rouhani et al.) 2018 Gilad Bachrach et al. 2016),, and secure multiparty computation (Ben- Or et al. 1988 Bonawitz et al. 2017) have been proposed to protect privacy of users in federated learning. In particular, differentially private federated learning (DPFL. provides strong information theoretic guarantees on user privacy, while causing relatively low performance overhead (Li al. 2020b).
Several defenses have been proposed to defend against poisoning attacks in FL, For instance, various robust aggregation methods (Fung et al. 2020 Pillutla et al.) 2019 Blanchard et al. 2011 El Mhamdi
et al. 2018 Chen et al. 2017b: Yin et al., 2018: Fu et al. 2019 Li et al., 2020a) identify and down- weight the malicious updates during aggregation or estimate true "center" of the received updates rather than taking a weighted average. Other methods include robust federated training protocols (e.g., clipping (Sun et al. 2019), noisy perturbation (Sun al. 2019), and additional

---

Under review as a conference paper at ICLR 2022
evaluation during training (Andreina et al. 2020)) and post-training strategies (e.g., fine-tuning and pruning (Wu et al., 2020)) that repair the poisoned global model. However, as these works mainly focus on providing empirical robustness for FL. they have been shown to be vulnerable to newly proposed strong adaptive attacks (Wang et al., 2020; Xie et al. 2019 Baruch et al.] 2019 Fang et al. (020)) Hence, in this paper, we aim to develop certified robustness guarantees for FL against different poisoning attacks. Further, as differentially private federated learning (DPFL) is often used to protect user privacy, we also aim to ask: Can we leverage the innate privacy property of DPFL to provide robustness certification against poisoning attacks for free? Can we further improve the privacy of FL so as to improve its certified robustness?
Recent studies suggest that differential privacy (DP) is inherently related with robustness of ML models. Intuitively, DP designed to protect the privacy of individual data, such that the output of an algorithm remains essentially unchanged when one individual input point is modified. Hence, the prediction of a DP model will be less impacted by a small amount of poisoned training data. Consequently, DP has been used to provide both theoretical and empirical defenses against evasion attacks (Lecuyer et al. 2019) 1aa) and data poisoning attacks (Ma et al. 2019 Hong et al. 2020) on centralized ML models. It has also been used as an empirical defense against backdoor attacks (Gu iet al.] 2019) in federated learning (Bagdasaryan et al.) 22200] |Snn et al. 2019), although no theoretical guarantee provided. To the best of knowledge, despite of the wide application of theee, is no work providing certified robustness for DPFL. leveraging its privacy property.
In this paper, aim to leverage the inherent privacy property of DPFL to provide robustness certification for FL against poisoning attacks for free. Our challenges include: (1) performing privacy analysis over training rounds in DPFL algorithms and (2) theoretically guaranteeing certified robustness based on DP properties under a given privacy budget. We propose two robustness certification criteria for FL: certified prediction and certified attack cost under different attack constraints, We consider both user-level DP (Agarwal et al.) 2018; Geyer et al. 2017: McMahan al. 2018 Asoodeh Calmon| 2020 Liang et al. 2020) which is widely guaranteed in FI., and instance-level DP (Malekzadeh et al. 2021 Zhu et al. (022] which is less explored in FL. We prove that a FL model satisfying user-level DP is certifiably robust against a bounded number of adversaiial users. In addition, we propose and prove that instance-level DPFL is certifiably robust against a bounded number of adversarial instances. We also study the correlation between privacy guarantee and certified robustness of FL. While stronger privacy guarantees result in greater attack cost, overly strong privacy can hurt the certified prediction by introducing too much noise in the training process. Thus, the optimal certified prediction is often achieved under a proper balance between privacy protection and utility loss.
algorithm to improve instance-level DP in FL,
Key Contributions. Our work takes the first step provide certified robustness in DPFL. for free against poisoning attacks. We make contributions on both theoretical and empirical fronts.
We propose two criteria for certified robustness of FL against poisoning attacks (Section
Given a FL model satisfying user-level DP, we prove that is certifiably robust against arbitrary poisoning attacks with bounded number of adversarial users (Section 4.2).
We propose InsDP-FedAve algorithm to improve FL instance-level privacy guarantee (Sec-
tion 5.1 We prove that instance-level DPFL is certifiably robust against the manipulation of bounded number of instances during training (Section 5.2)
We conduct extensive experiments on image classification of MNIST, CIFAR-10 10 and sentiment analysis of tweets to verify our proposed certifications of two robustness criteria, and compare the certified results of different DPFL algorithms (Section
RELATED WORK
Differentially Private Federated Learning. Different approaches are proposed to guarantee the user- privacy for FL. (Geyer et al. 2017, McMahan et al.) 2018) clip the norm of each local update, add Gaussian noise on the summed update, and characterize its privacy budget via moment accountant (Abadi et al.) 2016). (McMahan et al., 2018) extends (Geyer et al., 2017) to language models. In CpSGD Agarwal et al.) 2018), each user clips and quantizes the model update, and adds noise drawn from Binomial distribution, achieving both communication efficiency and DP. (Bhowmick et al., 2018) derive DP for FL via Rényi divergence (Mironov) 2017) and study its protection against data reconstruction attacks. (Liang et al.) (020) utilizes Laplacian smoothing for each local update to enhance the model utility. Instead of using moment accountant to track privacy
2

---

Lemma (Group DP). For mechanism M that satisfies (c, 0)-DP, it satisfies (ke, 1- 5)-DP for I-c" Under review as a conference paper at ICLR 2022
budget over FL rounds as previous work, (Asoodeh & Calmon 2020) derives the DP parameters by interpreting each round as a Markov kernel and quantify its impact on privacy parameters. All these works only focus on providing user-level privacy, leaving its robustness property unexplored.
In terms of instance-level privacy for FL, there are only a few work (Malekzadeh et al. 2021 Zhu
et al., 202T). Dopamine (Malekzadeh al. 202T) provides instance-level privacy guarantee when each user only performs one step of DP-SGD (Abadi et al., (016) at each FL round. However, cannot be applied to multi-step SGD for each user, thus it cannot be extended to the general FL setting FedAvg (McMahan et al. 2017). (Zuu et al. 202T) ) privately aggregate the labels from users in voting scheme, and provide DP guarantees on both user level and instance level. However, is also not applicable to standard FL, since it does not allow aggregating the gradients or updates.
Differential Privacy and Robustness. In standard (centralized) learning, Pixel-DP (Lecuyer et al.) 2019ap is proposed to certify the model robsutness against evasion attacks. However, it is unclear how to leverage it to certify against poisoning attacks. To certify the robustness against poisoning attacks, (Ma et al., 2019) show that private learners are resistant to data poisoning and analyze the lower bound of attack cost against poisoning attacks for regression models. Here we certify the robustness in DPFL setting with such lower bound one of our certification criteria and additionally derive its upper bounds. (Hong et al., 2020) show that the off-the-shelf mechanism DP-SGD (Abadi eet al. 2016). which clips per-sample gradients and add Guassian noises during training, can as a defense against poisoning attacks empirically. In federated learning, empirical work (Bagdasaryan al. 2020 Sun al. 2019) show that DPFL can mitigate backdoor attacks; however, none of these work provides certified robustness guarantees for DPFL against poisoning attacks.
3 PRELIMINARIES
We start by providing some background on differential privacy (DP) and federated learning (FL).
Differential Privacy (DP). DP is formal, mathematically rigorous definition (and standard) of privacy that intuitively guarantees that a randomized algorithm behaves similarly on similar inputs and that the output of the algorithm is about the same whether or not an individual's 's data is included as part of the input (Dwork & Roth 2014).
Definition 1 ((e, 6)-DP (Dwork et al. 2006)). A randomized mechanism M D - O with domain 'D and range satisfies (e, O)P if for any pair of two adjacent datasets d, d' E D, and for any possible (meusurable) oulput set E C θ, it holds that Pr[M(d)= E E] S e Pr [M (d') E E f)+ ö. In Definition] [ when . is a training algorithm for ML. model, domain D and range O represent all possible training datasets and all possible trained models respectively. Group DP for (c, 6) whheee
mechanisms follows immediately from Definition where the privacy guarantee drops with the size of the group. Formally, it says:
groups of size k. That for any d, d' E 'D that differ by k individuals, and any E C θ it holds that Pr[M(d) E F] eke Pr (M
E) --2-0 5.
Federated Learning. FedAvg was introduced by (McMahan et al. 2017) for FL to train shared global model without direct access to training data of users. Specifically, given a FL system with N users, at round f, the server sends the current global model w to users in the selected user set Us. where |U,] = m = q.V and q is the user sampling probability. Each selected user i E Ue locally updates the model for E local epochs with its dataset D; and learning rate 7j obtain new local model. Then, the user sends the local model updates Awi to the server. Finally, the server aggregates over the updates from all selected users into the new global model w/ Wh-1 + m Eieu, Awi.
4 USER-LEVEL PRIVACY AND CERTIFIED ROBUSTNESS FOR FL
4.1 LEVEL PRIVACY AND BACKGROUND
Definition [ leaves the definition of adjacent datasets flexible, which depends on applications. To protect user-level privacy, adjacent datasets defined as those differing by data from one
user (McMahan et al. 2018). The formal definition of User-level 5)DP (Definition 2 is omitted
to Appendix[A.I
Following standard DPFL Geyer et al. 2017 McMahan et al. 2018), we introduce one of standard user-level DPFL. algorithms UserDP FedAvg (Algorithm) in Appendix A.T). At each round,
3

---

Under review as a conference paper at ICLR 2022
the server first clips the update from each user with a threshold S such that its Ez-seniitivtyy is upper bounded by S. Next, the server sums up the updates, adds Gaussian noise sampled from NO, o² and takes the average, i.c. We < Wp-1 1
ma (Eisy, Clip (u + + (0, 59)). Given the user sampling probability 4. noise level a, FI. rounds T, and a 6 >> 0, the privacy analysis of UserDP-FedAve satisfying (c.d)-DP is given by Proposition | in Appendix A. which is generalization of (Abadi et al. 2016). The aim of Proposition]] i to analyze privacy budget in FL, which is accumulated as T increases due to the continuous access training data. Following [Geyer
et al. 2017 McMahan et al. 2018 moment accountant (Abadi et al. (016) is used in the privacy
analysis.
4.2 CERTIFIED ROBUSTNESS OF USER-LEVEL DPFL AGAINST POISONING ATTACKS
Threat Model. We consider the poisoning attacks against FL, where k adversarial users have poisoned instances in local datasets, aiming to fool the trained DPFL global model. Such attacks include backdoor attacks (Gu et al. 2019 Chen et al.] (017a) and label flippigg attacks (Biggio et al., 2012 Huang et al.) 2011). The detailed description of these attacks is deferred to Appendix A.2 Note that our robustness certification is attack-agnostic under certain attack constraints (e.g., k), and we will verify our certification bounds with different poisoning attacks in Section 6 Next, we propose two criteria for the robustness certification in FL: certified prediction and certified attack cost.
Certified Prediction. Consider the classification task with C' classes. We define the classification scoring function f Rd) + r which maps model parameters A O and an input data I E Rd to confidence vector f(0, æ²,, and zc(9,z) E [0. 1] represents the confidence of class We mainly focus on the confidence after normalization, i.e., f(0, E YC {p E R I|ell1 1} in the probability simplex. Since the DP mechanism AM is randomized and produces stochastic FL global model 0 = M(D), it is natural to resort to probabilistic expression as a bridge for quantitative robustness certifications. Following the convention in (Lecuyer et al. 2019b; Ma et al., 2019), we use the expectation of the model's prediction to provide quantitative guarantee on the robustness of M. Specifically, we define the expected scoring function F R*) + T where (D(, x) = (Mf.(((()) .=)] is the expected confidence for class The expectation is taken over DP training randomness, e.g., random Gaussian noise and random user subsampling. The corresponding prediction H : (0, IRd) - [C] is defined by H(M(D), == arg maX F.(M(D), x). which is the top-1 class based on the expected prediction confidence. We will prove that such prediction allows robustness certification against poisoning attacks.
Following our threat model above and DPFL training in Algorithm D we denote the trained global model exposed to poisoning attacks by M(D"). When k 1, D and D' are user-level adjacent datasets according to Definition 2 Given that mechanism M satisfies user-level (c. DDDD, based on the innate DP property, the distribution of the stochastic model M(D') is "close" to the dis- tribution of M(D). Moreover, according to the post-processing property of DP, during testing, given a test sample xr we would expect the values of the expected confidence for each class c, i.e., Fo(MDD'), x) and F.(M(D), .r), to be close, and hence the returned most likely class to be the same, i.e., H (M))),x) = (MM())), x), indicating robust prediction against poisoning attacks. Theorem 1 (Condition for Certified Prediction under One Adversarial User). Suppose randomized mechanism M satisfies user-level (c, 0)-DP. For two user sets B and B' that differ by one user, let D and D' be the corresponding training datasets. For test input suppose h. B E [C] satisfy A arg max Fe(M(D), Z) and B = arg max,el F Fc(M)D) 2)), then if Fa(M(D), > e (M(()D), + e1)5
it is guaranteed that (MM))) = (DM()), = A.
When l >> 1, we resort to group DP. According to Lemma I given mechanism M satisfying user- level (c, 6)DP, it also satisfies user-level (kc. --مي 5)- for groups of size k. When ls is smaller than certain threshold, leveraging the group DP property, we would expect that the distribution of the stochastic model M(D') is not too far away from the distribution of MDD) such that they would make the same prediction for a test sample with probabilistic guarantees. Therefore, the privacy and robustness guarantees are simultaneously met by M.
Theorem 2 (Upper Bound of k for Certified Prediction). Suppose randomized mechanism M satisfies leer- (c.8) ().P. For two user sets B and B' that differ by lo users, let D and D' be the corresponding training datasets. For test input x, suppose A. TB E [C] satisfy
4

---

Under review as a conference paper at ICLR 2022
A = arg [[]] Fc(M(D), 2) and B arg [C] Fc(M(D), z), then HMM(D))
H H(M(D), = A vk < K where K is the certified number of adversarial users:
Fa(M(D), =)(e" 6
K 2c
log Fb(M(D). xc) +
(2)
The proofs of Theorems and 2 are omitted to Appendix A.4 Theorems 1 and 2 reflect tradeoff
between privacy and certified prediction: (i) in Theorem I if e is large such that the RHS of Eq (T)
> 1, the robustness condition cannot be met since the expected confidence F (M)),, x) E [0. T.. However, to achieve small 6, i.e., strong privacy, large noise is required during training, which would hurt model utility and thus result in small confidence margin between the top two classes (e.g., F& (M(D), .) and (B(M(D): x)), making it hard to meet the robustness condition. (ii) In Theorem 2 if we fix (2(M(D); x) and Fa ()))), smaller of FL can certify larger K. However, smaller also induces smaller confidence margin, thus reducing K instead. As a result, properly choosing would help certify large K.
Certified Attack Cost. In addition to the certified prediction, we define the attack cost for attacker C: θ E which quantifies the difference between the poisoned model and the attack goal. In general, attacker aims to minimize the expected attack cost J(D) := E[C(M(D)), where the expectation is taken over the randomness of DP training. The cost function can be instantiated according to the concrete attack goal in different types of poisoning attacks, and we provide some examples below. Given a global FL model satisfying user-level (e, dDD,, we will prove the lower bound of the attack cost JDD)) when manipulating the data of at most l users. Higher lower bound of the attack cost indicates more certifiably robust global model.
Example 1. (Backdoor attack [Gu al. 2019) C(0) = Ei=1 1(0, 2)). where 2; (x;; das V²) 5e is the backdoor pattern, y² is the targel adversarial label. Minimizing J(D') drives the prediction on any test data with the backdoor pattern 82 to the target label y².
Example 2. (Label Flipping attack (Biggio et al. 2012)) C(0) = n ((0,, where =7 (æi, y²) and y" is the target adversarial label. Minimizing (DD) drives the prediction on test data I; to the target label y²
1(0,
Example 3. Parraette-Targgeinng attack Ma et al. 2019h) C(O) = 1 0-1|,, where 0* is the target model. Minimizing J (D)) drives the poisoned model to be close to the target model.
Theorem 3 (Attack Cost with i Attackers). Suppose a randomized mechanism M satisfies user-level (c, (DPP) For two user sets B and B' that differ ls users, D and D' are the corresponding training datasets. Let J(D) be the expected attack cost where |C(-)] S C. Then,
(i() ekce
30,003 2 J(D) max(e (oa((--"((D -(D) 1-
8C,0), if C() (3)
1- C¹ 1 8C,0) 2 J(D'> 2 max J(D) c -1 11, if C() 5
miinfe=*'(0)
The proof is omitted to Appendix A.4 Theorem 3 provides the upper bounds and lower bounds for attack cost J(D'). The lower bounds show that to what extent the attack can reduce (DD) by manipulating up to k users, i.e., how successful the attack can be. The lower bounds depend on the attack cost on clean model J J(D), i and c. When (D) is higher, the DPFL model under poisoning attacks is more robust because the lower bounds are accordingly higher; tighter privacy guarantee, i.e, smaller e, can also lead to higher robustness certification as it increases the lower bounds; with larger k the attacker ability grows and thus lead lower possible J(D'). The upper bounds show the least adversarial effect brought by k attackers, i.e., how vulnerable the DPFL model is under the optimistic case (e.g., the backdoor pattern is less distinguishable).
Leveraging the lower bounds in Theorem 3 we can lower-bound the minimum number of attackers required to reduce the attack cost to certain level associated with hyperaarameter T in Corollary D Corollary 1 (Lower Bound of le Given T). Suppose a randomized mechanism M satisfies user- level (c, -DP. Let attack cost function be C, the expected attack cost be J(-). In order to achieve C J(D') < 1 , (DD) for T 2 1 when 0 C(-) s C, or achieve JDD) S TJ) for 1 S SS J(D)
when- C < C()) < 0, the number of adversarial users should satisfy:
log
(e" 1) ((D) + CôT
1:
_ log (e- - 1)J(D) C5
(e' 1) JDDT C8
respectively.
(4)
(e- 1) J(D) + CöT
The proof is omitted to Appendix [A.4] Corollary shows that stronger privacy guarantee (i.e., smaller e) requires more attackers to achieve the same effectiveness of attack, indicating higher robustness.
5

---

Under review as a conference paper at ICLR 2022
5 INSTANCE-LEVEL PRIVACY AND CERTIFIED ROBUSTNESS FOR FL
5.1 INSTANCE-LEVEL PRIVACY
In this section, we introduce the instance-level DP definition, the corresponding algorithm, and the privacy analysis for FL.. When DP is used to protect the privacy of individual instance, the trained stochastic FL model should not differ much if one instance is modified. Hence, the adjacent datasets in instance-level DP are defined as those differing by one instance. The formal definition of Instance-level (c, 6)DP (Definition
3 is omitted to Appendix A.1
Dopamine Malekzadeh et al.] (021) provides the first instance-level privacy guarantee under FedSGD (McMahan et al. (2177). However, it has two limitations. First, its privacy bound is loose. Although FedSGD performs both user and batch sampling during training. Dopamine ignores the privacy gain provided by random user sampling. In this section, we improve the privacy guarantee
under FedSGD with privacy amplification via user sampling (Bassily et al. [2014]
[ [Abadi et al. 2016).
This improvement leads to algorithm InsDP- -ar---Fee FedSGD, to achieve tighter privacy analysis. We defer the algorithm (Algorithm{) 2 as well as its privacy guarantee to Appendix A.I
Besides the loose privacy bound, Dopamine (Malekzadeh et al. 2021 only allows users to perform one step of DP-SGD (Abadi al. 20T6) during each FI. round. This restriction limits the efficiency of the algorithm and increases the communication overhead. In practice, users in FL are typically allowed to update their local models for many steps before submitting updates to reduce the communication cost. To solve this problem, we further improve InsDP-FedSGD to support multiple local steps during each round. Specifically, we propose a novel instance-level DPFL algorithm InsDP- SPDDP-F&C -FedAg (Algorithm in Appendix [A.1) allowing users to train multiple local SGD steps before submitting the updates. In InsDP EnsDP-FedAvg, FedAvg, each user i performs local DP-SGD so that the local training mechanism M satisfies instance-level DP. Then, the server aggregates the updates. We prove that the global mechanism M preserves instance-level DP using DP parallel composition theorem (Dwork & Lei 2009) and moment accountant (Abadi et al. 2016).
formally presents the InsDP-FedAve algorithm and the calculation of its privacy budget c. Specifically, first, local privacy cost oj is initialized as 0 before FL training. At round t, if user i is not selected, its local privacy cost is kept unchanged ej < d1_ Otherwise user i updates local model by running DP-SGD for V local steps with batch sampling probability p. noise level a and clipping threshold S, and ef is accumulated upon é(_ via its local moment accountant. Next, the server aggregates the updates from selected users, and leverages (Ei and the parallel composition in Theorem to calculate the global privacy cost c,. After rounds, the mechanism M that outputs the FL global model in Algorithm is instance-level (cr, dD-
Algorithm
Theorem 4 (InsDP-Fedie Feddv Privacy Guarantec). In Algorithm 3 during round t, if the local mechanism M satisfies (E), DDP, then the global mechanism M satisfies (max E 6) -DP
The idea behind Theorem 4 is that when D' and D differ in one instance, the modified instance only falls into one local dataset, and thus parallel composition theorem (Dwork & Leil 2009) can be applied. Then the privacy guarantee corresponds to the worst-case, and is obtained by taking the maximum local privacy cost across all the users. The detailed proof is given in Appendix A.T
5.2 CERTIFIED ROBUSTNESS OF INSTANCE-LEVEL DPFL AGAINST POISONING ATTACKS
Threat Model. We consider poisoning attacks under the presence of k poisoned instances. These instances could be controlled by the same or multiple adversarial users. Our robustness certification is agnostic to the attack methods as long as the number of poisoned instances is constrained.
According to the group DP property (Lemma IT and the post-processing property for FL model with instance-level (c, -D, we prove that our robust certification results proposed for user-level DP are also applicable instance- level DP. Below is the formal theorem (proof is given in Appendix (A.4).
Theorem 5. Suppose D and D' differ by k instances, and the randomized mechanism M satisfies instance-level 5)-P. The results in Theorems] 2 3 and Corollary holl for M. D, and D'.
Comparison with existing certified prediction methods in centralized setting. The form of The- orem I is similar with the robustness condition against test-time attack in Proposition 1 of (Leeuyer cet al.) 2019a). This is because the derived robustness conditions are both rooted in the DP properties, but ours focus on the robustness against training-time attacks in FL., which is more challenging

---

Under review as a conference paper at ICLR 2022
considering the distributed nature and the model training dynamics, i.e., the analysis of the privacy budget over training rounds. Our Theorem [ is also different from previous randomized smoothing- based certifiably robust centralized learning against backdoor (Weber et al. 2020) and label flipping (Rosenfeld et al., 2020). First, our randomness comes from the inherent training randomness of user/instance-leve (c, ODDP, e.g., user subsampling and Gaussian noise. Thus, the certified robust- ness for free in DPFL means that the DPFL learning algorithm M itself is randomized, and such randomness can lead the robustness certification with non-trivial quantitative measurement of the randomness, On the contrary, robustness in randomized smoothing based methods comes from explicitly making the classification process randomized via adding noise in training datasets (Weber et al., 2020; Rosenfeld et al., 2020), or test samples (Lecuyer et al. 2019a Cohen et al. 2019) which is easier to measure. Second, our Theorem I 2 hold no matter how is achieved, which means that we can add different types of noise, leverage different subsampling strategies or even different FL training protocols to achieve user//nstance-
e. However, in (Weber et al.) 2020 Rosenfeld et al., 2020) different certifications require different types of noise (Laplacian, Gaussian, etc.). Additionally, DP is suitable to characterize the robustness against poisoning since DP composition theorems can be leveraged to track privacy cost c, which captures the training dynamics of ML model parameters without additional assumptions. Otherwise one may need to track the deviations of model parameters by analyzing SGD over training, which is theoretically knotty and often requires strong assumptions on Lipschitz continuity, smoothness or convexity for the trained models.
6 EXPERIMENTS
We present evaluations for robustness certifications, expecially Thm. 2 and Cor. I We find that 1) there is a tradeoff between certified prediction and privacy on certain datasets; 2) a tighter privacy guarantee always provides stronger certified robustness in terms of the certiffed attack cost; 3) our lower bounds of certified attack cost are generally tight when & is small. When k is large, they are tight under strong attacks (e.g., large local poisoning ratio a). Stronger attacks or tighter certification are requried to further tighten the gap between the emprical robustness and theoretical bounds.
Data and Model. We evaluate robustness certification results with three datasets: image class- fication on MNIST, CIFAR-10 and text sentiment analysis task on tweets from Sentiment 140 (Go al.) (Sent140) 40), which involves classifying Twitter posts as positive or negative. For image datasets, we use corresponding standard CNN architectures in the differential privacy library (opa) 2021) of
PyTorch; for Sent140, 140, we use LSTM classifier. Following previous work on DP ML (Jagielski et al., 2020) Ma et al.) 2019) and backdoor attacks (Tran et al.) 2018 Weber et al., 2020) which evaluate with two classes, we focus on binary classification for MNIST (digit and 1) and CIFAR-10 (airplane and bird), and defer the 10-class results to Appendix A.3 We train FL model following Algorithm for user-level privacy and Algorithm for instance-level privacy. We refer the readers to Appendix for details about the datasets, networks, parameter setups.
Poisoning Attacks. We evaluate several state-of-the-art poisoning attacks against the proposed UserDP-FedAve and InsDP-FedAve, We first consider backdoor attacks (BKD) (Bagdasaryan ct al. 2020) and label flipping attacks (LF) (Fung et al., (020). For InsDP-FedAse
we consider the worst case where & backdoored or lable-fipped instances are fallen into the dataset of user. For UserDP-FedAvg we additionally evaluate distributed backdoor attack (DBA) (Xie et al. 2019), which is claimed to be a more stealthy backdoor attack against FL. Moreover, we consider BKD, LF and DBA via model replacement approach (Bagdasaryan et al.) 2020) where k attackers train the local models using local datasets with a fraction of poisoned instances, and scale the malicious updates with hyperparameter y, i.e., Awi < >Aw/ before sending them to the sever. This way, the malicious updates would have a stronger impact on the FL model. Note that even when attackers perform scaling, after server clipping, the sensitivity of updates is still upper-bounded by the clipping threshold S. So the privacy guarantee in Proposition [ still holds under poisoning attacks via model replacement. Detailed attack setups are presented in Appendix A.3 A.3
Evaluation Metrics and Setup. We consider two evaluation metrics based on our robustness certification criteria. The first metric is certified accuracy, which is the fraction of the test set for which the poisoned FL model makes correct and consistent predictions compared with the clean FL model. Given test set of size n, for i-th test sample, the ground truth label is ys, the output prediction is q and the certified number of adversarial users/instances is K.. We calculate the certified accuracy at k n Ei= 1 [G = y: and K, k). The second metric is the lower bound of
7

---

Under review as a conference paper at ICLR 2022
attack cost in Theorem J(D') = max(e=*<[(B)) 1-- --I -C,
03. We evaluate the tightness of J(DD) by comparing it with empirical attack cost [D'). To quantify the robustness, we evaluate the expected class confidence F.(M(D). for class c via Monte- Monte-Carlo sampling. We run the private fc(M(D). 2) for each time. We Se. and use to evaluate Theorem 2
FL algorithms for M =100 times, with class confidence f compute its expectation to estimate Fc(M(DD.z) In addition, we use Hoeffding's s inequality (Hoeffding, 1994) to calibrates the empirical estimation
1 Mf
with confidence level parameter 4), and results are deferred to Appendix |A.3] In terms of the attack cost, we use Example 2 as the definitions of cost function C' for backdoor attacks and label flipping attacks respectively. We follow similar protocol to estimate (D') for Theorem 3 and Corollary
6.1 ROBUSTNESS EVALUATION OF USER-LEVEL DPFI.
Certified Prediction. Figure T (b) present the user-level certified accuracy under different by training DPFL models with different noise scale o. The results on Sent140 dataset is presented in Figure 13 of Appendix. AA.3.8] We observe that the largest & can be certified when is around 0.6298 in MNIST, 0.1451 in CIFAR-10, and 0.2247 in Sent140 which verifies the tradeoff between e and certified accuracy as we discussed in Section 4.2 Advanced DP protocols that requires less noise while achieving similar level of privacy are favored to improve the privacy, utility, and certified accuracy simultancously. Furthermore, we compare the certified accuracy of four different user-level DPFL methods (McMahan et al. 2018 Geyer et al. 2017) given the same privacy budget e. As shown in Figure [4] and Figure 15 of Appendix. A.399] the models trained by different DPFI. algorithms satisfying same have different certified robustness results. This is because even under the same different DPFL algorithms M produce trained models M(D) with different model performance, thus leading to different certified robustness. More discussion could be found in Appendix. A.3.9
NMST
CI
(c) MNIST
(d) CITAR-10
51379
3244
360
Figure Certified accuracy of FL satisfying user- DP (a.b), and instance- DP (c.d).
Certified Attack Cost. In order to evaluate Theorem aad characterize the tightness of our theoret- ical lower bound J(D'), we compare it with the empirical attack cost (DD)) under different local poison fraction ar attack methods and scale factor 7 in Figure Note that when A: O, the model is benign so the empirical cost equals to the certified one. We find that 1) when & increases, the attack ability grows, and both the empirical attack cost and theoretical lower bound decreases. 2) In Figure row 1, given the same k. higher a, i.c., poisoning more local instances for each attacker, achieves a stronger attack, under which lower empirical J (D) can be achieved and more close to the certified lower bound. This indicates that the lower bound appears tighter when the poisoning attack is stronger. under different y and attack
3) In Figure 2 row 2, we fix a 100% and evaluate UserD?-FedHa methods. It turns out that DP serves as a strong defense empirically for FL, given that J ((D did not vary much under different 71, 50, 100) and different attack methods (BKD, DBA, LF). This is because the clipping operation restricts the magnitude of malicious updates, rendering the model replacement ineffective; the Gaussian noise perturbs the malicious updates and makes the DPFL model stable, and thus the FL model is less likely to memorize the poisoning instances. 4) In both rows, the lower bounds are tight when 1 is small. When k is large, there remains a gap between our theoretical lower bounds and empirical attack costs under different attacks, which will inspire more effective poisoning attacks or tighter robustness certification.
Certified Attack Cost under Different e. Here we further explore the impacts of different factors on the certified attack cost. Figure presents the empirical attack cost and the certified attack cost lower bound given different on user-level DP. It is shown that as the privacy guarantee becomes stronger, i.c. smaller e, the model is more robust achieving higher (DD)) and (DD). In Figure 5 (a)(b), we train user-level (c. 8) DPFL models, calculate corresponding (D), and plot the lower bound of k given different attack effectiveness hyperparameter 7 according to Corollary [ It shows that 1) when the required attack effectiveness is higher, i.e., is larger, more number of attackers is required. 2) To achieve the same effectiveness of attack, fewer number of attackers is needed for larger 6, which means that DPFL model with weaker privacy is more vulnerable to poisoning attacks.
8

---

Under review as a conference paper at ICLR 2022
MKIST Backdoor (e-0.3077)
(C) CITAR-10 Backdoor (4H0.5330) 5348)
MINIST Label poiing temn 40251
141 CIFRR-D Label
9x27%
040
p-37h
av220/6
(c) MhiST Backdoor (c-0.4344)
e1 CIFAR-LO Backdoor (c-7.5977)
NKiST Label Hlpsing (c-0.4344)
pia FAR-LD Label Flopping (cm0 5978)
soard
28
Kee suand
D85
Figure 2: Certified attack cost of level DPFL given different k. under attacks with different or "
Bacedoor (Rod))
CIFAR-30 Backsoor (hwd)
Fllpping
Flip
5-
Jower bound
BKD 100
200
9437 333
Figure 3: Certified attack cost of user-level DPFL, with different under different attacks.
6.2 ROBUSTNESS EVALUATION OF INSTANCE-LEVER DPFL
Certified Prediction. Figure D (d) show the instance-level certified accuracy under different The optimal c for K is around 0.3593 for MNIST and 0.6546 for CIFAR- which is aligned with our observation of the tradeoff between certified accuracy and privacy on user-level DPFL (Section 6.1).
Certified Attack Cost. Figure show the certified attack cost on CIFAR-10. From Figure 4 (a)(b), poisoning more instances (i.e., larger k)) induces lower theoretical and empirical attack cost. From (c)d it is clear that instance-level DPFI. with stronger privacy guarantee provides higher attack cost both empirically and theoretically, meaning that it is more robust against poisoning attacks. Results on MNIST are deferred to Appendix A.33 Figure (c) show the lower bound of k under different instance-level given different Fewer poisoned instances are required to reduce the J (DD) to the similar level for less private DPFL model, indicating that the model is easier to be attacked.
(3) CIFAR 10 Bockdoor (t-0, 3158)
(b) CIFAR 10 Label Fliping (c-0.3158)
Ic CIFAR 10 Backsoor (h-4)
10h CIFAR 10 Label Flopping (t-4))
BKD
ICD
1.08
Figure 4: Certified attack cost of instance-level DPFL under different atlacks given different number of malicious instances & (a)(b) and different (c)(d)
Cal MNIST
000 CIFAR 10
1C MNUST
CIFAR-10
3,5000
12227
3-336
311122
6.1016
E-117
03225
2.5249
0,554
02626
Figure 5: Lower bound of l under leerl (a.b) and instance-leved (c.d) given attack effectiveness
7 CONCLUSION
In this paper, we present the first work on deriving certified robustness in DPFL for free against poisoning attacks. We propose two robustness certification criteria, based which we prove that FL model satisfying lser- (instance-level) DP is certifiably robust against a bounded number of adversarial users (instances). Our theoretical analysis characterizes the inherent relation between tified robustness and differential privacy of FL on both user and instance levels, which are empirically verified with extensive experiments. Our results can be used to improve the trustworthiness of DPFL..
9

---

Under review as a conference paper at ICLR 2022
Ethics Statement. Our work study the robustness guarantee of differentially private federated learning models from theoretical and empirical perspectives. All the datasets and packages we use open-soureed. We do not have ethical concerns in our paper.
Reproducibility Statement. Our source code is available as the supplemental material for repro- ducibility purpose. Our experiments can be reproduced following our detailed training and evaluation setups in Appendix(A.3 The complete proofs of privacy analysis and certified robustness analysis can be found in the Appendix A.1 and Appendix A.4 respectively.
REFERENCES
Opacus train pytorch models with differential privacy, 2021. URL httppt://ppccss........
Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pp. 308-318, 2016.
Naman Agarwal, Ananda Theertha Suresh, Felix Yu, Sanjiv Kumar, and H Brendan McMahan. epsgd: prriiitt
communication-eeffccen and differentially private distributed sgd. In Proceedings of the 32nd International Conference Neural Information Processing Systems, pp. 7575-7586, 2018.
Sebastien Andreina, Giorgia Azzurra Marson, Helen Möllering, and Ghassan Karame, Baffle: Backdoor detection via wredback-based federated learning. arXiv preprint arXiv:201..02167, 2020.
Shahab Asoodeh and F Calmon. Differentially private federated learning: An information-theorede perspective. In ICML Workshop on Federated Learning for User Privacy and Data Confidentiality, 2020.
Eugene Bagdasaryan, Andreas Veit, Yiqing Hua, Deborah Estrin, and Vitaly Shmatikov. How to backdoor federated learning. In International Conference on Artificial Intelligence and Statistics, pp. 2938.. PMLR, 2020.
Gilad Baruch, Moran Baruch, and Yoav Goldberg. A little is enough: Circumventing defenses for distributed learning. In H. Wallach, H. Larochelle, A. Beygelzimer, d'Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32, Curran As- sociates. Inc., 2019. URL http:ttt/////rocceeiiiiii neurips httpp/pps...pppppp//////////// cc22552400440000000c5555e220---0
pdf
Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pp. 464-473. IEFE, 2014.
Michael Ben-Or, Shafi Goldwasser, and Avi Wigderson. Completeness theorems for non- cryptographic fault-tolerant distributed computation. In Proceedings of the twentieth annual ACM symposium on Theory of computing, pp. 1-10, 1988.
Arjun Nitin Bhagoji, Supriyo Chakraborty, Prateek Mittal, and Seraphin Calo. Analyzing federated learning through an adversarial lens. International Conference on Machine Learning, pp. 634-643, 2019.
Abhishek Bhowmick, John Duchi, Julien Freudiger, Gaurav Kapoor, and Ryan Rogers. Protec- tion against reconstruction and its applications in private federated learning. arXiv preprint arXiv: 1812.00984, 2018
Battista Biggio, Blaine Nelson, and Pavel Laskov. Poisoning attacks against support vector machines. In Proceedings of the 29th International Coference on International Conference on Machine Learning, pp. 1467-1474, 2012.
Peva Blanchard, El Mahdi EI Mhamdi, Rachid Guerraoui, and Julien Stainer. Machine learning with adversaries: Byzantine tolerant gradient descent. In Proceedings of the 31st International Conference Neural Information Processing Systems, pp. 118-128, 2017.
10

---

Under review as a conference paper at ICLR 2022
Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth. Practical secure aggregation for privacy- preserving machine learning. In proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pp. 1175-1191, 1191, 2017.
Raphael Bost, Raluca Ada Popa, Stephen Tu, and Shafi Goldwasser. Machine learning classification over encrypted data. In NDSS, volume 4324, pp. 4325, 2015.
Theodora S Brisimi, Ruidi Chen, Theofanie Mela, Alex Olshevsky, loannis Ch Paschalidis, and Wei Shi. Federated learning of predictive models from federated electronic health records. International journal of medical informatics, 112:59-60 67, 2018
Xinyun Chen, Chang Liu, Bo Li, Kimberly Lu, and Dawn Song. Targeted backdoor attacks on deep learning systems using data poisoning. arXiv preprint arXiv: 1712.0556, 2017a.
Yudong Chen, Lili Su, and Jiaming Xu. Distributed statistical machine learning in adversarial settings: Byzantine gradient descent. Proceedings of the ACM Measurement and Analysis of Compuling Systems, 12)) 2017b.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In International Conference on Machine Learning, pp. 1310-1320. PMLR, 2019.
Cynthia Dwork and Jing Lei. Differential privacy and robust statistics. In Proceedings the forty-first annual ACM symposium on Theory of computing, pp. 371-380, 2009.
Cynthia Dwork and Aaron Roth. The algorithmic foundations differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3-4):211 (0:4):211-407, 1-407, 2014.
Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Advances in Cryptology - EUROCRYPT, 2006.
El Mahdi EI Mhamdi, Rachid Guerraoui, and Sébastien Louis Alexandre Rouault. The hidden vulnerability of distributed learning in byzantium. In International Conference on Machine Learning, number CONF, 2018.
Minghong Fang, Xiaoyu Cao, Jinyuan Jía, and Neil Gong. Local model poisoning attacks to byzantine-robust federated learning. In 29th {USENIX] Security Symposium (!USENIX) Security 20). pp. 1605-1622, 2020.
Shuhao Fu, Chulin Xie, Bo Li, and Qifeng Chen. Attack-resistant federated learning with residual- based reweighting. arXiv preprint arXiv: 1464, 2019.
Clement Fung, Chris JM Yoon, and Ivan Beschastnikh. The limitations federated learning in sybil settings. In 23rd International Symposium on Research in Attacks, Intrusions and Defenses ({RAID) 2020), pp. 301-316, 2020.
Jonas Geiping, Hartmut Bauermeister, Hannah Dröge, and Michael Moeller. Inverting gradients easy is it to break privacy in federated learning? NeurIPS, 2020.
Robin C Geyer, Tassilo Klein, and Moin Nabi. Differentially private federated learning: A client level perspective. arXiv preprint 171200777 2017.
Ran -aaad-BBcchach, Nathan Dowlin, Kim Laine, Kristin Lauter, Michael Naehrig, and John Wernsing. Cryptonets: Applying neural networks to encrypted data with high throughput and accuracy. In International Conference on Machine Learning, pp. 201-210. PMLR, 2016.
Alec Go, Richa Bhayani, and Lei Huang. Twitter sentiment classification using distant supervision.
Tianyu Gu, Kang Liu, Brendan Gavitt, and Siddharth Garg. Badnets: Evaluating backdooring attacks on deep neural networks. IEEE Access, 7:47230-47244 2019.
Andrew Hard, Kanishka Rao, Rajiv Mathews, Françoise Beaufays. Sean Augenstein, Hubert Eichner, Chloé Kiddon, and Daniel Ramage. Federated learning for mobile keyboard prediction. arXiv preprint arXiv: ..0660, 2018.
11

---

Under review as a conference paper at ICLR 2022
Wassily Hoeffding. Probability inequalities for sums of bounded random variables. In The Collected Works of Wassily Hoeffding, pp. (209-426.70 Springer, 1994.
Sanghyun Hong, Varun Chandrasekaran, Yigitcan Kaya, Tudor Dumitraş, and Nicolas Papernot. On the effectiveness of mitigating data poisoning attacks with gradient shaping. arXiv preprint arXiv:2002. 1497, 2020.
Ling Huang. Anthony D Joseph, Blaine Nelson, Benjamin IP Rubinstein, and Doug Tygar. Ad- versarial machine learning. In Proceedings of the 4th ACM workshop Security and artificial intelligence, pp. 43-58, 2011.
Matthew Jagielski, Jonathan Ullman, and Alina Oprea. Auditing differentially private machine learning: How private is private sgd? Advances in Neural Information Processing Systems, 33, 2020.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009.
Yann LeCun and Corinna Cortes, MNIST handwritten digit database. 2010. URL http: /yann
lecun. com/ httpt///c///ee////ce///ee
Mathias Lecuyer, Vaggelis Atlidakis. Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. In 2019 IEEE Symposium on Security and Privacy (SP), pp. 656-672, 2019a. doi: 10.11 1..10099P..19.00000
Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. In 2019 IEEE Symposium on Security and Privacy (SP), pp. 656-672. IEEE, 2019b.
Suyi Li, Yong Cheng, Wei Wang, Yang Liu, and Tianjian Chen. Learning detect malicious clients for robust federated learning. arXiv preprint arXiv:2002.00211 20000a
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. arXiv preprint arXiv: /8/2.06/2, 2018.
Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Challenges, methods, and future directions. IEEE Signal Processing Magazine, 37(3)500-60, 2020b. doi: 10.1 10.1109/MSP22222229777777
Zhicong Liang. Bao Wang, Quanquan Gu, Stanley Osher, and Yuan Yao. Exploring private federated learning with laplacian smoothing. arXiv preprint arXiv:2005.000 08. 2020.
Yuzhe Ma, Xiaojin Zhu Zhu, and Justin Hsu. Data poisoning against differentially- private learners: Attacks and defenses. In International Joint Conference Artificial Intelligence, 2019.
Mohammad Malekzadeh, Burak Hasircioglu, Nitish Mital, Kunal Katarya, Mchmet Emre Ozfatura, and Deniz Gunduz. Dopamine: Differentially private federated learning on medical data. arXiv preprint 10Xiv:2101.11 /693, 2021.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera Arcas. Communication Efficiien Learning of Deep Networks from Decentralized Data. Proceed- ings of the 20th International Conference Artificial Intelligence and Statisties, volume 54 of Proceedings of Machine Learning Research, pp. 1273-1282. PMLR, 20-22 Apr 2017.
Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning differentially private recurrent language models. In International Conference on Learning Representations, 2018.
Luca Melis, Congzheng Song, Emiliano De Cristofaro, and Vitaly Shmatikov. Exploiting unintended feature leakage in collaborative learning. In 2019 IEFE Symposium on Security and Privacy (SP), pp. 691-706. IEEE, 2019.
Ilya Mironov. Rényi differential privacy. In 2017 IEEE 30th Computer Security Foundations Symposium (CSF), pp. 263-275. IEEE, 2017.
Ilya Mironov, Kunal Talwar, and Li Zhang. 'eyyi differential privacy of the sampled gaussian mechanism. arXiv preprint arXiv: 1908. 10530, 2019.
12

---

Under review as a conference paper at ICLR 2022
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen. Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high- performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Bus E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems 32, pp. 8024-8035. Curran Associates, Inc., 2019, URL http:: pdf
ibbrrr.
Jeffrey Pennington, Richard Socher, and Christopher Manning. Glove: Global vectors for word representation. In Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP), pp. 1532 1543, 2014.
Krishna Pillutla, Sham M Kakade, and Zaid Harchaoui. Robust aggregation for federated learning. arXiv preprint arXiv: 19/2. 1t11/9922334444 /345,, 2019.
Elan Rosenfeld, Ezra Winston, Pradeep Ravikumar, and Zico Kolter. Certified robustness to label- flipping attacks via randomized smoothing. In International Conference on Machine Learning, pp. 8230- 8241. PMLR, 2020.
Bita Darvish Rouhani, M Sadegh Riazi, and Farinaz Koushanfar. DeepSecure: Scalable provably- secure deep learning. In Proceedings of the 55th Annual Design Automation Conference, pp. 1-6, 2018.
Ziteng Sun, Peter Kairouz, Ananda Theertha Suresh, and H Brendan McMahan. Can you really backdoor federated learning? arXiv preprint arXiv:1911.07963, 2019.
Brandon Tran, Jerry Li, and Aleksander Madry. Spectral signatures in backdoor attacks.
In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Gar- nett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Asso-
ciates, Inc., 2018 URL htttps::/proceeedinngg meweeeeeeddddene..nee..e........ http:///ww......oooo.....o//eaaa /c////pe//////
pdf]
Stephen Tu. Lecture 20: Introduction to differential privacy. URL https://stephen::
github. http:://wwieeepseeees.. 1ec20-b- pdf
Hongyi Wang, Kartik Sreenivasan, Shashank Rajput, Harit Vishwakarma, Saurabh Agarwal, Jy-yong Sohn, Kangwook Lee, and Dimitris Papailiopoulos. Attack of the tails: Yes, you really can backdoor federated learning. NeurIPS, 2020.
Maurice Weber, Xiaojun Xu, Bojan Karlas, Ce Zhang, and Bo Li. Rab: Provable robustness against backdoor attacks. arXiv preprint 2xXiv:2003.08904, 2020.
Chen Wu, Xian Yang. Sencun Zhu, and Prasenjit Mitra. Mitigating backdoor attacks in federated learning, arXiv preprint arXiv:2011.0176) 2020.
Chulin Xie, Keli Huang, Pin- Yu Chen, and Bo Li. Dba: Distributed backdoor attacks against federated learning. In International Conference on Learning Representations, 2019.
Qiang Yang, Yang Liu, Tianjian Chen, and Yongxin Tong. Federated machine learning: Concept and applications. ACM Transactions on Intelligent Systems and Technology (TIST), 10, 2019a.
Timothy Yang. Galen Andrew, Hubert Eichner, Haicheng Sun, Wei Li, Nicholas Kong, Daniel Ramage, and Françoise Beaufays. Applied federated learning: Improving google keyboard query suggestions. arXiv preprint arXiv: 18/2. 220903, 2018
Wensi Yang. Yuhang Zhang. Kejiang Ye, Li Li. and Cheng -hoong-Zngg Xu. Ffd: federated learning based method for credit card fraud detection. In International Conference on Big Data, pp. 18-32. Springer, 2019b.
Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartlett. Byzantine-robuse distributed learning: Towards optimal statistical rates. In International Conference on Machine Learning, pp. 5650-5659. PMLR, 2018.
13

---

Under review as a conference paper at ICLR 2022
Ligeng Zhu, Zhijian Liu, and Song Han. Deep leakage from gradients. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Bue, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Asso- ciates, Inc., 2019. URL URL Sbo
neurips....ee....eeee.......issm cc wwtpppppp/////111//1// 9/001/
Yuqing Zhu, Xiang Yu, Yi-Hsuan Tsai, Francesco Pittaluga, Masoud Faraki, Manmohan Chandraker, and Yu-Xiang Wang. Voting based approaches for differentially private federated learning, 2021.
net/ foru/ ddd
14

---

Under review as a conference paper at ICLR 2022
A
APPENDIX
The Appendix is organized as follows:
provides the DP definitions and the DPFL algorithms on both user and instance levels, and the proofs for corresponding privacy guarantees.
Appendix A.
Appendix A.2
specifies our threat models.
Appendix A.3 provides more details experimental setups for training and evaluation, the ad- dition experimental results on certified accuracy with confidence level, robustness evaluation of InsDP-FedAvg on MNIST, robustness evaluation 10-class classification, DP bound com- and Dopamine, certified accuracy of UserDP-FedAve on Sent140 and certified accuracy comparison of different user-level DPFL. algorithms.
parison between
Appendix A.4 provides the proof' for the certified robustness related analysis, including Lemma
Theorem 123 5and Corollary [
Appendix
A.5 provides the comparison to related work (Lecuyer al. 2019a Ma et al. 2019
A.1
DIFFERENTIALYY PRIVATE FEDERATED LEARNING
A.1.1 USERDP-FEDĀVE
Definition 2 (User-level (c.8)-DP). Let B, B' be two user sets with size N. Let D and D' be the datasets that are the union of local training examples from all users in B and B' respectively. Then, D and D' are adjacent B and B' differ by one user. The mechanism M satisfies user-level (c, 8DD if it meets Definition| 7 with D and D' as adjacent datasets.
Algorithm 1: UserDP-Fedavg.
Input:
Initial model wip user sampling probability g, privacy parameter 5, clipping threshold noise level a, local datasets D Dx local epochs E, learning rate y.
return wr, e Procedure UserUpdate (i, wi-1)
Output: FL model wr and privacy cost
w + Wt for local epoch
Server executes:
to F. do for batch E local dataset D; do
for each round
to T do mI max(q- N, 1):
w + ();
U, + (random subset of m users);
Auf 6 w wi-1
for each user i Up in parallel do
Aw; UserUpdate (i, w[-1)
return Aut
wi + w m (E Clip (Awj, S) + + (0,)))?)); Procedure Clip (A, S)
return A/ max 1. |ا16
M.accum.pric cataccmmpprv.sseeniiie www.sspeedddndggggo (..
In Algorithm|D 1 M.accum wwwplrrvvvvvieeleleeeeee (rriisspending and ...gel M..ee_prrvuccy seriuccyspenttie are the calls the moments accountant M refer to the API of (Abadi et al. 2016).
Given the user sampling probability noise level FL rounds T, and a 5 0, UserDP-FedAd satisfies (e, 6)-DP as below, which is generalization (Abadi et al. 2016). The aim is to analyze increases due to the continuous access training data.
privacy budget e, which is accumulated
Proposition 1 (UserDP FedAvg Privacy Guarantee). There exist constants eı and 02 that given
user sampling probability q, and FL rounds T. for any < cTq2T, if 2 02 sy TVTlog(175) randomized mechanism M in Algorithm is 8). for any 8 > 0.
the
Proof. The proof follows the proof of Theorem in (Abadi al. 2016), while the notations have slightly different meanings under FL settings. In Proposition we use to represent user-level sampling probability and to represent FL training rounds.
Note that the above privacy analysis can be further improved by Rényi Differential Privacy (Mironvv al. 2019).
15

---

Discussion (Li et al. 2020b) divide the user-level privacy into global privacy GGeeer al. 2017: McMahan et al. 2018) and local privacy (Agarwal et al., 2018). In both local and global privacy, the norm of each update is clipped. The difference lies in that the noise is added on the aggregated model Under review as a conference paper at ICLR 2022
updates in global privacy because a trusted server assumed, while the noise is added on each local update in local privacy because it assumes that the central server might be malicious. Algorithm T belongs to global privacy.
A.1.2 INSDP-FEDSGI
Definition 3 (Instance-level (c, D).).. Let D be the dataset that the union of local training examples from all users. Then, D and D' are adjacent if they differ by one instance. The mechanism M is instance-level 6)-PP if meets Definition with D and D' as adjacent datasets.
Algorithm 2: InsDP-FedSGD.
Input:
Initial model
sampling prohability
Procedure UserÜpdate (i, (;-1)
privacy parameter 6, local clipping threshold 8,
Mt-1
local noise level a, local datasets Di.... Dx.
8j -uniformly sample batch from D; with prob- ability p L/(D,
learning rate 7) hatch sampling probability p.
Output: FL. model uT and privacy cost
for each z; c 1y do
Server executes:
g(2;) + vi(w;
for each round
to do m max(q .N, 1);
3(1,) +
U. < (random subset of m clients); for each user E Uj in parallel do
9 < E g(g() N (0,o253)):
+- w 19
L Aw; UscrUpdate (i, 11-1))
Aut < w Wt-1:
Wy + wt 1 + Eier, Aut;
return Aw/
m
caacuum-prvv.speneeee (oppeddngg/mmr,, (/mo, pq.
Procedure Clip (A.
A.get-privacysseen))
return A max 1, |
return Wy.
Under FedSGD, when each local model performs one step of DP-SGD (Abadi et al. 2016), the randomized mechanism M that outputs the global model preserves the instance-level DP. We can regard the one-step update for the global model Algorithm as:
Σ iE
Σ g(و,) ( E
We +- W0
(5)
Proposition 2 (InsDP- FedSGD Privacy Guarantee). There exist constants e1 and 02 so that given batch sampling probability p. and user sampling probability q, the number of selected users each
round m, and FL rounds T, for any < ci (pg)) if 2 C2 P9V/ (og(1/5) the randomized c//
mechanism M in Algorithm 2 is ()P8) for any 8 > 0.
Proof. i) In instance-level DP, we consider the sampling probability each instance under the com- bination of user-level sampling and batch-level sampling. Since the user-level sampling probability and the batch-level sampling probablity is p, each instance is sampled with probability pq. ii) Additionally, since the sensitivity of instance-wis wiiee gradient w.r.t one instance is S. after local gradient descent and server FI. aggregation, the equivalent sensitivity of global model w.r.t one instance nS
is S' = Im according to Eq 5). iii) Moreover, since the local noise is n. ~ o00,o""" then
the "virtual" global noise is m = mf. ΣiEU, 74 according to Eq (5) so n ~ No """"s" mf.2 ). Let
n po²s"
mi² = 222g12 such that n ~ N0, o2 5²2). Because = nS the equivalent global noise level Lm
12 2 i.e., o' =
In Proposition we use pg to represent instance-level sampling probability, to represent FL training rounds, o vm to represent the equivalent global noise level. The rest of the proof follows the proof of Theorem in (Abadi et al. 2016).
16

---

Under review as a conference paper at ICLR 2022
We defer the DP bound evaluation comparison between InsDP-FedSGD and Dopamine Ap- pendix A.3.7
A.1.3
HNSDP-FEDAVG
Algorithm 3: InsDP-FedAvg
Input:
Initial model wp, user sampling probability 4,
return w
privacy parameter 6, local clipping threshold S, local noise level a, local datasets Di.... Dx local steps V. learning rate batch sampling probability
Procedure UserUpdate (1, M1-11
w f- Wt-1:
for each local step = 1 to V do
+ sample a batch from D; with
Output: FL model WT and privacy cost
probability = L/ D;D:
Server executes:
for each x; E do
to do m < max(q _N. 1);
each round
g(3;) Vı(u; ((1z) < clip (g(#)).
Ug + (random subset of m users);
+. E g(a,) + (0,)
for each user Up in panallel do
L Awi, + UserUpdate (i, w(-1)
w + w vig
M accum percuum-prv-sppeee wwwp:priiiseeiigggp......
for each user $ Ug do
L c 4-11
4 oe-ggerrrivacyspennyy
Aut <- w 11-1:
Uy + Wt 1 +
md Eiev. Aut; cowpullel.comoositiiooo (c()ve())
return Awi
Procedure Clip (A. S)
6 e
return A max 1. |A
Lemma (InsDP-FedAye Privacy Guarantee when T =). In Algorithm 3 when = 1, suppose local mechanism M satisfies (DD, then global mechanism M satisfies (max;e[N] é 5) DDP
Proof. We can regard federated learning as partitioning dataset D into N disjoint subsets (D1, D2.... ....... DN N mechanisms (M' ....,,'? are operated on these N parts separately and each M satisfies its own e'-DP for i E [J. Note that if i-th user is not selected e 0 because local dataset D, is not accessed and there is no privacy cost. Without loss of generality, we assume the modified data sample x' (x + x' causes D D') is in the local dataset of k-th client Dr. Let D, D' be two neighboring datasets (Dk, Dí are also two neighboring datasets). M randomized mechanism that outputs the global model, and M is the randomized mechanism that outputs the local model update Aw'. Suppose wo is the initialized and deterministic global model, and {E1, } are randomized local updates. We have sequence of computations {21 = (M1) = (D2; 23 = (D3; 21, 22)...) and & = M(D) = -pp + Σm 24.
Note that if i-th user not selected, 2, = According to the parallel composition (Tu), we have
Pr[M(D) 2]
PPI[M (D:) 21 Pr(MM 22] ... Pr[M (DN: 21. 21...... (NN11) 2N]
Sexp(e Pr[M* (D/: .k.,,, =k-1) =x]
Pr[M' ,,, 2--1 2;)
igk
= PP(((") =]
So M satisties DD when the modified data sample lies in the subset Da. Consider the worst case of where the modified data sample could fall in, we know that M satisfies (max;e[N) cD)-DP.
We recall Theorem
Theorem (InsDP-FedAvg Privacy Guarantee). Algorithm 3 during round I, if the local mechanism M satisfies (et, d)-PP, then the global mechanism M satisfies (maxie[N] 6 8) 8)-P.
Proof. Again, without loss of generality, we assume the modified data sample x' (r x' causes D + D') is in the local dataset of k-th user D.. We first consider the case when all users are selected. At each round i, N mechanisms operated on N disjoint parts and each Mf satisfies
17

---

Under review as a conference paper at ICLR 2022
own c'DD where c' is the privacy cost for accessing the local dataset D; for one round (not accumulating over previous rounds). Let D' be two neighboring datasets (Dx, Dj, are also two neighboring datasets). Suppose 2n (D) is the aggregated randomized global model at round / 1, and {z1,.... 2N) are the randomized local updates at round f, we have a sequence of computations (
M D2; 20, 21); 23 .M. D3: Zo. 21, 22) .... and
= == (D)) = 2o + Σi zi. We first consider the sequential composition (Dwork & Roth 2014) to accumulate the privacy cost over FL rounds. According to parallel composition, we have
Pr(M)(D) = z|
N
= -Pr[M-1(DD) = 20]
II
Pr
[r[M 20. 21, 2411,, z,]
1=1
= PP(M)-I(D) = zo] Pr[M (DR: 20, 21 21...,, = =k] II
Pr[M 20, 21, = =zi]
I <exp(e-1) PTMM = 2ol () Pr[M, (0:3 21, xb-1) 1-= = 2x II
Pr[M; 20. ,1,...,,,,............... 21-1) = 2n]
= =exp(e-1+ (P((e))+(())(MMM((())) =
Therefore, M, satisfies e,,,,, where 6 = 6t-1 + e Because the modified data sample always lies in D2 over t rounds and 6o = 0, we can have e = te which means that the privacy guarantee of global mechanism M₁ is only determined by the local mechanism of k-th user over rounds.
Moreover, moment accountant (Abadi et al., 2016) is known to reduce the privacy cost from (t) to OVE)). We can use the more advanced composition, i.e., moment accountant, instead of the sequential composition, to accumulate the privacy cost for local mechanism M over t FL rounds. In addition, we consider user subsampling. As described in Algorithm 3 if the user i not selected at round 1, then its local privacy cost is kept unchanged at this round.
Take the worst case of where x' could lie in, at round t, AM satisfies 4-DP, where G = m d. local mechanism M satisfies e/-D,, and the local privacy cost e, is accumulated via local moment accountant in i-th user over t rounds.
A.2 THREAT MODELS
We consider targeted poisoning attacks of two types. In backdoor attacks (Gu et al. 2019 Chen et al. (017a)), the goal is to embed a backdoor pattern (i.e., a trigger) during training such that any test input with such pattern will be mis-classified as the target. In label flipping attacks (Biggio et al.) 2012; Huang et al. 201T), the labels of clean training examples from one source class are Ilipped to the target class while the features of the data are kept unchanged. In FL. the purpose of backdoor attacks is to manipulate local models with backdoored local data, so that the global model would behave normally on untampered data samples while achieving high attack success rate on clean data (Bagdasaryan et al. 2020). Given the same purpose, distributed buckdoor attack (DBA) (Xie cet al. 2019) decomposes the same backdoor pattern to several smaller ones and embeds them to different local training sets for different adversarial users. The goal of label flipping attack against FL to manipulate local datasets with flipped labels such that the global model will mis- classiff the test data in the source class as the target class. The model replacement (Bagdasaryan al.) 2020) is more powerful approach to perform the above attacks, where the attackers first train the local models using the poisoned datasets and then scale the malicious updates before sending them the server. This way, the attacker's 's updates would have a stronger impact on the FL model. We use the model replacement method to perform poisoning attacks and study the effectiveness of DPFL.
For UsezDP-FedNae we consider backdoor, distributed backdoor, and label flipping attacks via the model replacement approach. Next, we formalize the attack process and introduce the notations. Suppose the attacker controls lt adversarial users, i.e., there are & attackers out of N users. Let B be the original user set of N benign users, and B' be the user set that contains & attackers. Let D = [D), D2..... DN be the union of original benign local datasets across all users. For data sample z5 = (2r), v3} in Di, we denote its backdoored version 2"} = {ar dz y² }, where &
18

---

Under review as a conference paper at ICLR 2022
is the backdoor pattern, y" is the targeted label; the distributed backdoor attack (DBA) version as ="} = (ar "2. where 82 is the distributed backdoor pattern for attacker i; the label-flipeed version as ="} = -x",,,0' Note that the composition of all DBA patterns is equivalent to the backdoor pattern, i.e., > 8 ===6... 6g. We assume attacker i has or fraction of poisoned samples in its local dataset D/- Let D' 1....... D.....,''a-- 1',,,, D' D DN} } be the union of local datasets when k attackers are present. The adversarial user i performs model replacement by scaling the model update with hyperparameter y before submitting the server, i.e., Awj < >'ww,. In our threat model, we consider the attacker that follows our training protocol and has no control over which users are sampled.
For InsDP-FedAver we consider both backdoor and label flipping attacks. Since distributed backdoor and model replacement attacks are proposed for adversarial users rather than adversarial instances, we do not consider them for instance-level DPFL. There are & backdoored or label-fliper instances (z1, 22, 2(). which could be controlled by same or multiple users. In our threat model, we consider the attacker that follows our training protocol and has no control over which data partition (or batch) is sampled. Note that we do not assume that the adversaries' poisoning data always be sampled. In algorithms, each batch is randomly subsampled, so the adversaries cannot control if poisoned data are sampled in each step.
A.3 EXPERIMENTAL DETAILS AND ADDITIONAL RESULTS
A.3.1 DATASETS AND MODELS
We evaluate our robustness certification results with two datasets: MNIST (LeCun & Cortes 2010) and CIFAR-10 (Krizhessky (200)). For each dataset, we use corresponding standard CNN architec- tures in the differential privacy library (opal 2021) of PyTorch (Paszke et al.) 2019).
MNIST: We study an image classification problem of handwritten digits in MNIST. It is dataset classes, split into a train set of 60000 images and test set of 10000 images. Except Section |A3.6 we consider binary classification on classes 0 and 1, making our train set contain 12665 samples, and the test set 2115 samples. The model consists of two Conv-ReLu-MaxPoon
of 70000 28x28 pixel images of digits
layers and two linear layers.
We study image classification of vehicles and animals in CIFAR-10. This is harder dataset than MNIST, consisting of 60000 32x32x3 images, split into a train set of 50000 and test set of 10000. Except Section A.3.6. we consider binary classification on class airplane and bird, making train set contain 10000 samples, and the test set 2000 samples. The model consists of four Conv-Rel.u-Averene wee.u-AvveeeaPollliini layers and one linear layer. When training on CIFAR10, we follow the standard practice for differential privacy (Abadi et al., 2016) Jagielski et al.) (0220) and fine-tune whole model pre-trained non-privately on the more complex CIO,RIO0, similarly sized but more complex benchmark dataset. We can achieve reasonable performance on CIFAR-10 datasets by only training (fine-tuming) few rounds.
CIFAR-10:
Sent140: We consider a text sentiment analysis task on tweets from Sentiment 40 (Go et a (Sent140) which involves classifying Twitter posts as positive or negative. We use a two layer LSTM binary classifier containing 256 hidden units with pretrained 300D Glo embedding (Pennington et al. 2014). Each twitter account corresponds to device. We use the same network architecture, non-iid dataset partition method, number of selected user per round, learning rate, batch size, etc. as in (Li et al. 2018), which are summarized in Table
A.3.2 TRAINING DETAILS
We simulate the federated learning setup by splitting the training datasets for N FL users in an i.i.d manner. FL users run SGD with learning rate 7). momentum 0.9, weight decay 0.0005 to update the local models. The training parameter setups are summarized in Table I Following (McMahan et al. 2018) that use 5 R3 शान as privacy parameter, for UserDP FedAvg we set ó = 0.0029 according to the total number of users, and for InsDP-FedAvg we set = 0.00001 according the total number of training samples. Next we summarize the privacy guarantees and clean accuracy offered when we study the certified prediction and certified attack cost, which are also the training parameters setups when k = 0 in Figure 2
19

---

Under review as a conference paper at ICLR 2022
Algorithm
Dataset
#training samples
N
v
E
V
batch
"
C
UserDP-FedAvg
MNIST
12665
200
20
10
0.02
0.0029
UserDP-FedAeg
CIFAR-10
10000
200
40
0.05
0.0029
0.2
UserDP-FedAvg
Sent140
40783
805
10
3
/
10
0.3
0.5
0.000001
InsDP-FedAvg
MNIST
12665
10
10
/
25
50
0.02
0.7
0,00001
0.5
InsDP-FedRvg
CIFAR-10
10000
10
10
/
100
50
0.05
0.00001
2
Table Dataset description and parameters
User-level DPFL In order to study the user-level certified prediction under different privacy guar- antee, for MNIST, set to be 0. 0.2808, 0.4187, 0.6298, 0.8694, 1.8504, 2.8305, 4.8913, 6.9269, which are obtained by training UserDP FedAvg FL model for rounds with noise level set to
3.0, 1.8, 1.5, 1.0, 0.8, 0.6, 0.5, respectively (Figure Ta)). For CIFAR-10, be 0.1083, 0.1179, 0.1451, 0.2444, 0.3663, 0.4527, 0.5460, 0.8781, which are obtained by training UserDP-FedAte FL model for one round with noise level a 10.0, 8.0,88.0,. 6.0, 4.0, 3.0, 2.6, 2.3, 1.7, respectively (Figure [b)). The clean accuracy (average over 1000 runs) - -FedAvg under
non-DP training (e о0) and DP training (varying e) MNIST and CIFAR-10 10 are reported in Table. and Table.
respectively.
0.5
0.8
1.5
2.3
00
6.9269
4.8913
2.8305
1,8504
0.8694
0.6298
0.4187
0.2808
Clean Acc.
99.66%
99.72%
99.69%
99.71%
99.59%
98.86%
97.42%
89.15%
72.79%
Table 2:
Clean accuracy of UserDP SeerDD--Fedvgg FedAvg model on MNIST
1.7
2.3
2.6
3
8
10
0.8781
0.546
0.4527
0.3663
0.2444
0.1451
0.1179
0.1083
Clean Acc.
81.90%
81.82%
80.09%
79.27%
77.89%
73.07%
64.36%
57.92%
54.59%
Table 3: Clean accuracy of UserDP-FedAvg model on CIFAR-10
To certify the attack cost under different number of adversarial users à (Figure 2b. for MNIST, we set the noise level a to be 2.5. When k 0, after training UsezDP-Fedåvg for T = 3, 4, 5 rounds, we obtain FI. models with privacy guarantee
0.3672, 0.4025, 0.4344 and clean accuracy (average over M runs) 86 66,,9% 88.70 88.76% 88. 99%. For CIFAR- 10, we set the noise level a to be 3.0. After training UserDP-Fedd FFddggg for T = 3, 4 rounds under k = 0, we obtain FL models with privacy guarantee = 0.5346, 0.5978 and clean accuracy 78.63%, 78.46%.
With the interest of certifying attack cost under different user-level DP guarantee (Figure Fig- ure 5). we explore the empirical attack cost and the certified attack cost lower bound given differ- For MNIST, which are obtained by training UserDP -FedAvg FL models for 5 rounds under noise level
set the privacy guarantee to be 1.2716, 0.8794, 0.6608, 0.5249, 0.4344,
1.3, 1.6, 1.9, 2.2, 2.5, respectively, and the clean accuracy for the correspond- ing models are 99.50%, 99.06% 96.52% 93.39%. 88.99%. For CIFAR-10, we set the pri- vacy guarantee e to be 1.600, 1.2127, 1.0395.0000 0.350,0,,000 0.7616, 0.6543, 0.5978, which are ob- tained by training UserDP-FedAvg FL models for 4 rounds under noise level = 1.5, 1.8, 2.0, 2.3, 2.5, 2.8, 3.0, respectively, and the clean accuracy for the corresponding models are 85.59% 84.52%, 83. 23%, 81.90%, 81.27%, 79.23%. 78.46%.
Instance-level DPFL To certify the prediction for instance-level DPFL un- der different privacy guarantee, for MNIST, we set privacy cost c to be 0.2029, 0.2251, 0.2484, 0.3593, 0.4589, 0.6373,,3333. 1.0587,3.560 by training InsDP-FedAvg FL models for 3 rounds with noise level 15, 1, 4, 3, 2, respectively (Figure [.)). For CIFAR-10. we set privacy cost e to be 0.3158, 0.3587, 0.4221, 0.5130. 0.6546, 0.9067, 1.4949, 4.6978. which InsDP-FedAve -FddAv FL models for one round with noise level o = 8, 7, 6, 5, 4, 3, 2, 1, respectively (Figure d)). The clean accuracy (average 1000 runs) of InsDP-FedAve under non-DP
which are obtained
obtained by training
20

---

Under review as a conference paper at ICLR 2022
training oc) and DP training (varying c) MNIST and CIFAR- 10 are reported in Table. 4 Table. respectively.
and
0
3
4
5
10
15
00
3.5691
1.0587
0.6373
0.4589
0.3593
0.2484
0.2251
0.2029
Clean Acc.
99.85%
99.73%
99.73%
99.70%
99.65%
99.57%
97.99%
93.30%
77.12%
Table 4: Clean accuracy of InsDP-FedAve model MNIST
4
8
00
4.6978
1.4949
0.9067
0.6546
0,513
0.4221
0.3587
0,3158
Clean Acc.
91.15%
97.91%
86.02%
83.85%
81 81.43%
77.59%
72.69%
66.47%
62.26%
Table 5: Clean accuracy of InsDP-FedAvg model on CIFAR-10
With the aim to study certified attack cost under different number of adversarial instances k, for MNIST, we set the noise level to be 10. When k 0, after training InsDP -FDD--FeAvgg for TorT' = 4,9 rounds, we obtain FL models with privacy guarantee e = 0.2383, 0.304 and clean accuracy (average over M runs) 96. 46,40% 96.93% (Figure 8 ab)). For CIFAR-10, we set the noise level to be 8.0. After training InsDP-PF FEEDD-Peeae -Fed-ggeevggg for one round under & = 0, we obtain FL models with privacy guarantee 0.3158 and clean accuracy 61.78% (Figure 4 (b)).))
In order to study the empirical attack cost and certified attack cost lower bound under different instance-level DP guarantee, 0.5016, 0.311, 0.2646, 0.2318, 0.2202, 0.2096, 0.205 for MNIST, which are obtained by training InsDP-FedAvg FL models for rounds under noise level 5, 10, 13, 15, 18, 20, respectively, and the clean accuracy for the corresponding mod- els are 99.60%, 98.81%, 97.34%, 92.29%, 88.01%, 80.94% 79.60% (Figure g (c)).). For 10, we set the privacy guarantee to be 1.261, 0.9146, 0.7187, 0.5923, 0.5035 0.4385, which are obtained by training InsDP-FedAvg FL models for 2 rounds under noise level 3, 4, 5, 6. 7, respectively, and the clean accuracy for the corresponding models are 84.47%, 80.99%. 76.01%, 01,,66 68.66 68.65% 63.07%, 60.65% (e))))
set the privacy guarantee to be
With the intention of exploring the upper bound for 1 given 7 under different instance-level DP guarantee, for MNIST, we set noise level a to 5, 8, 10, 13, 20, respectively, to obtain instance-DP 0.6439, 0.3937, 0.3172, 0.2626, 0.2179 and
FL models after 10 rounds with privacy guarantee clean accuracy 99.58% 98. 88%, 97. 97.58%, 95.23%, 85.72% (Figure (c)). For CIFAR- 10, we set noise level to be 3, 4, 5, 6, 7, 7,8 and train InsDP FFddvgg for T rounds, to obtain FL mod- els with privacy guarantee = 1.5365, 1.1 0.8777, 0.7238, 0.6159, 0.5361 and clean accuracy 84.34% 80.27%. 74.62%, 66.94%, 62.14% 59%75% (Figure 5 d)).
A.3.3 ADDITIONAL IMPLEMENTATION DETAILS
(Threat Models) For the attacks against UserDP-FedAvg. by default, the local poison fraction 100%, and the scale factor ? 50. We use same parameters setups for all l attackers. In terms of label flipping attacks, the attackers swap the label of images in source class (digit I for MNIST; bird for CIFAR-10) into the target label (digit for MNIST; airplane for CIFAR-10). In terms of backdoor attacks in MNIST and CIFAR- 10, the attackers add a backdoor pattern, as shown in Figure (left), in images and swap the label of any sample with such pattern into the target label (digit for MNIST; airplane for CIFAR-10). In terms of distributed backdoor attacks, Figure 6 (right) shows example when the triangle pattern is evenly decomposed into & = 4 parts, and they are used as the distributed patterns for = 4 attackers respectively. For the cases where there more or fewer distributed attackers, the similar decomposition strategy is adopted.
Figure 6: Backdoor pattern (left) and distributed backdoor patterns (right) on CIFAR-10.
21

---

Under review as a conference paper at ICLR 2022
For the attacks against InsDP-FedAvee the same target classes and backdoor patterns used as U The parameters setups are the same for all l: poisoned instances.
(Robustness Certification) We certified 2115/2000/1 122 test samples from the MNIST/CIFAR 10/Sent140 test sets. In Theorem 3 and Corollary | that are related to certified attack cost, specifies the range of C()). In the implementation, C is set be larger than the maximum empirical attack cost evaluated on the test sets (see Table 1 for details). For each dataset, we use the same C for When using Monte-Carlo sampling, 100 times for certified attack cost in all
cost function C' defined in Example [ and Example 2
run M 1000 times for certified accuracy, and M experiments.
(Machines) We simulate the federated learning setup (1 server and N users) on Linux machine with Intel@ Xcon@ Gold 6132 CPUs and 8 NVidia@ 1080Ti GPUs.
(Libraries) All code is implemented in Pytorch (Paszke et al. 2019 Please see the submitted code for full details.
A.3.4 CERTIFIED ACCURACY WITH CONFIDENCE LEVEL
Here present the certified accuracy with confidence level. We use Hoeffding's inequality (Ho- effding 1994) to calibrates the empirical estimation with one-sided error tolerance vh, i.e., one-sided confidence level vb. We first use Monte-Carlo sampling by running the private FL algorithms for M times, with class confidence f = ff(,M(D), x) for class each time. We denote the em- pirical estimation zc() M E. f2- For test input 2, suppose A, B [C] satisfy = arg max.e(c) x)), and = arg max,e[C]:ofts Fe(M(D), x). For given error tol- erance v. we use Hoeffding's inequality to compute a lower bound FA (M()), x) on the class confidence Fa(M(D), x) and a upper bound (M()))) on the class confidence Fs(M(()),)) according to
log(1/e)
log(1/b)
Fa(M(D), = (FA(D)))))FA(M((,,,.>)) x) -
Fs(M(D), = Fo(M(D), x)+
2M
2M
FA (M æ) and (MM(()), are used the expected class confidences for the evaluation of Theorem We use &0 0.01 and M 1000 for all experiments.
CIFAR
accuracy
x- 02000
-- 33005
33239
9.6
0.438
5.5
2444
18234
2382
4.913
2.0555
2
5229
32
5.555
4.507
Figure 7: Certified accuracy under 99% confidence of FL satisfying user-level DP (a.b), and instance-lovel DP (c.d).
As shown in Figure discussed in Figure [ In general, the K in Figure is smaller than the K in Figure [e we calibrate the empirical estimation according Eq. (6) and the class confidence gap between top-1 and 2 class is narrowed.
observe the same tradeoff between and certified accuracy
A.3.5 ADDITIONAL ROBUSTNESS EVALUATION OF INSTANCE-LEVEL DPFL
Here we report the robustness evaluation of instance-level DPFL on MNIST, As shown in Figure g the results on MNIST are similar to the results CIFAR-10 in Figure 4
22

---

Under review as a conference paper at ICLR 2022
(a) HNIST Backdoor (2m0.2303)
(b) MNIST Label Flipping (e=0.300)
(c) MINIST Backdoor (km10)
(dl MINIST Label flipping 1k=10)
Figure 8: Certified attack cost of instance-level DPFL MNIST under different attacks given different number of malicious instances & (a)(b) and different (c)(d).
A.3.6 ROBUSTNESS EVALUATION 10-CLASS CLASSIFICATION
Here we report the robustness evaluation of user-level DPFL under backdoor attacks on 10-class classification problem. Figure TO presents the certified accuracy under different c. We can observe the tradeoff between and certified accuracy on MNIST. On CIFAR-10, larger it can be certified with smaller The certified K is relatively small because we set large to preserve reasonable accuracy for 10-class classification. Our results can inspire advanced DP mechanisms that provide tighter privacy guarantee (i.e., smaller e) while achieving similar level of accuracy. In terms of certified attack cost, as shown in Figure and the trends are similar to the 2-class results in Figure and 5
(a) MNIST Backdoor (c-0.6784)
(b) Backdoor (c=12008)
MNIST Backdoer (k=3)
10) Backdoor (k=1)
lover 1010000
RED v- 103E0%
1-10%
Figure 9: Certified attack cost of user-level DPFL on 10-class classification given different number of malicious instances (a)(b) and different (c).d)
(a] MNIST
CIFAR.10
[a] NNIST
[b) CIFAR10
centted ecuuary
321
X--2-4211
30
56
Figure 10: Certified accuracy of FL satisfying user- Sigure 11: Lower bound & on 10-class classification level DP on 10-class classification.
under user-level given attack effectiveness т.
A.3.7 DP BOUND COMPARISON BETWEEN INSDP-FEDSGY AND DOPAMINE
Here we compare Dopamine to our InaDP-FedSCD. both of which are proposed for FedSGD. Under the same noise level (a 3.0), clipping threshold (S 1.5), user sampling probability (m/N- = 20/30), and batch sampling probability (0.4) settings, both algorithms achieve about 92% accuracy MNIST (10 classes). The Figure 12 shows the results of privacy guarantee estimation over training rounds, which demonstrates that our method achieves tighter privacy certification. For instance, at round 200, our method (e 1.4029) achieves a much tighter privacy guarantee than Dopamine (c = 2.1303).
A.3.8 CERTIFIED ACCURACY OF
ON SENT140
For Sent140, we set c to be 0.2238. 0.2247, 0.4102.0. 7382, 1.7151, which are obtained by training UserDP-FedAvg FL model for three rounds with noise level a 4,3, 2, 1.5, 1, respectively
As shown in Figure B the largest can be certified when é is around 0.2247 in Sent140, which also verifies the tradeoff between and certified accuracy as observed in image datasets.
23

---

Under review as a conference paper at ICLR 2022
InDD-Fed8BD
2,00
Dopamine
1.50
1.25
0.75
0.6
Round
Figure 12: Comparison DP bound under FedSGD on MNIST dataset. Our InsDF-Fed5GO achieves tighter bound.
Sent140
1.0
E 0.2238
certified accuracy
0.8
E 0.2247
0.4102
0.7382
E 1.7151
K
Figure 13: Certified accuracy of FL satisfying user-level DP on Scnt
A.3.9 CERTIFIED ACCURACY COMPARISON OF DIFFERENT USER-LEVEL DPFL ALGORITHMS
In this section, we include two more user-level DPFL works (McMaha et al. 2018 g Geyer et al. 2017) to study certified accuracy with a total four different DPFL methods given the same privacy budget Since all our proposed robustness certifications certifications hold no matter how (c, 5) is achieved, we can empirically compare the certified results of different DPFL algorithms. Specifically, consider the following four DPFL algorithms:
agnostic DPFL algorithms, i.c.,
flat clipping (UserDP-FedAvgg) clips the concatenation of all the layers of model update with the L2 norm threshold
per-layer clipping McMMhan et al. 2018) clips each layer of model update with the L2 norm threshold S.
flat median. clipping (Geyer et al. 2017 use the median of norms of clients' model updates as threshold for flat clipping.
per-layer median clipping (Geyer et al. 2017) use the median of each layer's norms of clients' model updates as threshold 5 for per-layer clipping.
For MNIST (CIFAR-10) 10), set to be 0.6319 (0.5346) which is obtained by training all DPFL
algorithmss with the same noise level σ = 2.3 (a = 3.0) for same number rounds. For flat clipping and lay-layer clipping, set S 0.7 (S 1) MNIST (CIFAR-10). Except for local epoch E other FL parameters setups are the same as in Table
In experiments we note that the median norm clipping approaches (Geyer al. 2017 can only be applied when the number of local epoch is small, which makes these methods less practical, Recall that in the server aggregation step, the noise sampled from A 5²), S cannot be too large order keep the amount
24

---

Under review as a conference paper at ICLR 2022
MNIST (E = 0.6319)
CIFAR-10 10 (E 0.5346)
1.0
1.0
Ratt dippiin (UserDP-feeel Fedlgg
flat dipping (UserDP (UserOP-Fedlwwg)
certified accuracy
per-layer clipping
certified accuracy
per-layer clipping (McMahan
0.8
flatt median clipping (Geyer et al,, 2017)
0.8
naat median clipping (Geyer et al,, 2017)
layer median clipping (Geyer 2017]
per-layer median clipping (Geyer al., 20171
0.6
0.4
0.4
0.2
0.2
0.0
1
3
Figure 14: Certified accuracy of model trained Figure 15: Certified accuracy of model trained by different user-level DPFL algorithms under same different user-level DPFL algorithms under same on CIFAR-I0.
MNIST.
As shown in Figure 14 and Figure 15 on MNIST, the flat clipping is able to certify the largest number of adversaries while on CIFAR-IO. the median clipping certifies the largest & instead. Moreover, on both MNIST and CIFAR-10 10. flat clipping and per-layer clipping with the same S lead to different certification results, while the results of flat median clipping and per-layer median clipping are nearly identical. This is because even under the same privacy protection different DPFI. algorithms M produce trained models M(D) with different model performance, thus leading to different certified robustness. Specifically, in Theorem given the same and (DM()) x) and F+(M(D) vary for different DPFL trained models M(D), thus causing different certified K.
The above interesting results indicate that our proposed robustness certifications can serve as new metrics to benchmark the robustness of different DPFL algorithms, which can potentially motivate the investigation for better DPFL algorithms (i.e., different types of noise, clipping methods, subsampling strategies, or even different FI. training protocols). We believe these analyses can provide new and important insights to the FL. community.
A.4 PROOFS OF CERTIFIED ROBUSTNESS ANALYSIS
We restate our Lemma here.
Lemma (Group DP). For mechanism M that satisfies (c, D)-PP, it satisfies (kc, 1-=- 6)-DP for I-
groups of size k. That is, for any d, d' E D that differ by l individuals, and any E C θ it holds that Pr[M(d) El S te Pr|M
E]+
1- I-ce 8.
Proof. We denote d as do d' du- d, differ individuals with do- For any E [1, k), d, and di-1
differ by one individual, thus
Pr[M(d-1)] < (r)) +
By iteratively applying Eq. 7 times, have
Pr[M(do)] < E Pr[M[dd)] + (1 + e + t + +... 1(k-1)9988
ke Pr[M 1 1- the
6
Before we prove Theorem 1 we introduce the following lemma:
of noise reasonable and preserve good model utility. As more local epoch leads to larger norm of model updates, set the local epoch to keep the median norm small.
25

---

Under review as a conference paper at ICLR 2022
Lemma 3. Suppose randomized mechanism M satisfies user-level (c, 6)-DP. For two B and B' that differ by one user, D and D' are the corresponding training datasets. For a test input æ, for any e [C], fe(M(D), E [0, 1] is the class confidence, then the expected class confidence Fc(M(D); = (D))) x) meets the following property:
Fc(M(D), 2) & e'Fc(((D') +
(8)
Proof. Define ((a) = fc(0 > a). Then
Fc(M(D), - -ELG(M(),, ((A((M()),)) a] da
PIM(D) E ((a)) da
(ETIM(DD) E @((a] + +0) da
(P(L((((D))))>>> >a] da + [ 5da
= E.((M(D))))++
We recall Theorem
Theorem (Condition for Certified Prediction under One Adversarial User), Suppose a randomized mechanism M satisfies user-level (e, 6D- For two user sets B and that differ by one user, let D and D' be the corresponding training datasets. For test input suppose A. B [C] satisfy arg maxce]C1 Po (MMD), 2) and B arg maxcelC)=44 F (M(D),,)) then if Fa(M(D), et (M(D), e
(1)
it is guaranteed that H(M(D',,z) H(M(D), = A.
Proof. According to Lemma 3
FA(M(D), ( SEFA(((D)). +
(9)
( 2))
(10)
Then
(a(M(D'), 28
(Because of Eq. 9
( + (1+
(Because of the given condition Eq.
E: = x) + 2e Pe(M(D'),)) +
(Because of Eq. 10
FA((M(D),,) x),
which indicates that the prediction of M(D') at x A by definition.
Before we prove Theorem we introduce the following lemma:
Lemma 4. Suppose randomized mechanism M satisfies user-level (e, D)DP. For two user sets B and B' that differ k users, D and D' are the corresponding training datasets, For a test input for any E [C], (cM x) E [0, 1] the class confidence, then the expected class confidence F (M((()) == Eff.(M(D) x)) meets the following property:
F.(M(D), S tt F.(((D'), + 1 Eht
(11)
1 e
26

---

Under review as a conference paper at ICLR 2022
Proof. Define ((a) {8 fc(0,2) a). Then
x(( = /. F(fe(M(D). > al da
P(M(D) E O(a)) da
! (<MP[M(D') O[a)] + 1 che ) da
1- 8
(Because of Group DP property in Lemma 1
!. cKPP ( do
['¹ 1 chk ôda
jo
e
1 1-ekc 1
F(((()))
6
We recall Theorem 2
Theorem 2 (Upper Bound of for Certified Prediction). Suppose randomized mechanism M satisfies user-level (c, 8)-P.. For two user sets B and B' that differ by k users, ler D and D' be the corresponding training datasets. For test input I, suppose A, E [C] satisfy A = arg max.elc1 FcMM(D), x) and B = arg maxce(C]:e4h. Fe(M(D),z) then H(M(D'), H(M(D).x) = A. vk < where K is the certified number of adversarial users: Fa(M(D), x)(e -1) +
log Fe(M(D), 1) +
(2)
Proof. According Lemma have
1 ke
Fa(M(D), S FF(M(()),
e 6
(12)
e kc
(a(M(D),, S dh (M)),
1 E 8.
(13)
We can re-write the given condition & < according to Eq.
( as
1 kc
2ke Fa(M(D) + (1
< Fa(M(D),x)).
(14)
Then
Fa(M(D),x)> Fa(M(D), - 1-
1-ee
(Because of Eq.
12
eke
(M + (1 + eke)
1 T-pe
1- be
eike
(Because of the given condition Eq
14
cke - Et 8 Fe(M(D'),z)
k-
1 - ckee
Kr
1-
+
(Because of Eq.
13
Eke
1
Fs(M(D'). x).
which indicates that the prediction of M(D') at is A by definition.
We recall Theorem
27

---

da Under review as a conference paper at ICLR 2022
Theorem 3 (Attack Cost with k Attackers). Suppose a randomized mechanism M satisfies user-level (e, 6D- For two user sets B and B' that differ k users, D and D' are the corresponding training datasets. Let (D) be the expected attack cost where |C(()) < C. Then,
minfe"" ette_
- OC,C) 2 J(D')= 2 maxie k J(D) 1 c
et - 80,0), if C()) 20 0
(3)
J(D)+ 1- e ke min(e->>(())
~t
Ex - 80,03 2 J(D') 2 maxie * J(D) e" 80, -C', if c()50
Proof. We first consider C(-) 2 0. Define O(a) {0: C(0)= > a}.
J(D) J P(C(M(D)) a] da
l PIM(D)) E O(a)] da
$ 10 (>*PIM(D') ((()] + 1 1-ehe -
c
ekee - et
da
(Because of Group DP property in Lemma !
1 1 ckk [- <'P[M(D')) E O(a)) e()) da +
1 e 80
10 *'P(C((D')) > aa +
1 e
1 e iC
+ 1- eke
1- E 80
i.e.
1 1- e ke
J(D') ckk J(D)
6t 1 8C.
Switch the role of D and D', we have
J(D') S J(D)+ + 1- ehe 8C.
c²
Also note that 0 0s J(D') < C trivially holds due to 0 S C(.) C, thus
min(e*<J(D)) + krr e -
5C, J())) 2 maxfe ke J(D)- 1 1
c 1 80.0}.
Next we consider C(-) < 0. Define O(a) = C(B) < a}.
J(D) = L
F F(C(M(D)) a] da
P(M(D)) E da
2 L-
("T(M((')) ((((D))){((()) e(aa) + 1- chke 1 1- cr
(Because of Group DP property in Lemma []
1 eke = 1 *PIM(D')) E ((a)) da
1 ee SC
0
(PIC(((DD)) a] da 1 the
e 80
= =JD'' 1 ke
1 60 60
28

---

Under review as a conference paper at ICLR 2022
ie.,
1 kr
S +
6 SC.
Switch the role of D and D', have
J(D") 2 J(D) 1 - chk 8C.
Also note that -C' J(D') - trivially holds due to - S C(-) S 0, thus
1 1 kr
-1
+
e" sC,03 2 J(D') 2 max (((((
ec 80, -C}
We recall Corollary 1
Corollary (Lower Bound of Given r). Suppose a randomized mechanism M satisfies user-
level (c, DD... Let attack cost function be C. the expected attack cost be (()) In order to achieve
J(D') s J(D) for T 2 1 when 0 S C(-) & C, or achieve J(D) S IJD 1 1 T J(D)
when -C S C() S 0, the number of adversarial users should satisfy:
2 log (e' 1) J(D)T Côr (e- 1) Cör
1: - log (er I)D(D) C6
(e' 1) J(D) C8
respectively.
(4)
Proof. We first consider C(-) 2 0. According to the lower bound in Theorem 3 when B' and
B differ users, J(D') 2 ke J(D) -C- SC. Since we require J(D') S J(D), then J(D) - L-n
e-- --
be 80 < + (D). Rearranging gives the result.
Next, we consider C(-) < 0. According to the lower bound Theorem 3 when B' and B differ IJ 2 e (D) th 1 Since we require J(D)) TJ()), then ehc J(D) ---000000 8C <
TJ(D). Rearranging gives the result.
We note that all the above robustness certification related proof' are built upon the user-level (e, DDP property and the Group DP property. According to Definition 2 and Definition 3 the definition of user-level DP and instance-level DP are both induced from DP (Definition [T] despite the different definitions of adjacent datasets. By applying the definition of instance-level (e, 6)-DP and following we can derive the similar theoretical conclusions for instance-level DP, leading to Theorem 5 to achieve the certifiably robsut FL for free given the DP property.
the proof steps Theorem [ 2 3 and Corollary [
A.5 COMPARISON TO LECUYER ET AL.
2019A
MA ET AL. 2019
In this section, summarize our differences in of the relationship between DP and robustness
compared to (Lecuyer et al. 2019a Ma et al. 2019).
[Lecuyer et al. 2019a) work on certified prediction against test-time attacks while we study DP against training- training-time poisoning attacks in FL. We would like to emphasize that (Lecuyer et al.) 2019a) aim make the classification process Pixel-DP while the training algorithm itself does not satisfy DP, so it cannot directly build the relationship between DP and training-time certified robustness.
Conceptually, in contrast to the connection between Pixel-DP and certified prediction against adversarial examples, our proposed analysis the connection between DP and certified robustness against data poisoning is new.
Technically, Pixel-DP adds noise on test data samples during testing once while we add noises in updates gradient at every training round. Although the analysis of Pixel-DP and ours are both rooted in the intuition of DP definition, Pixel-DP requires the classifier make randomized predictions during testing and the training algorithm itself does not
29

---

Under review as a conference paper at ICLR 2022
satisfy DP. In contrast, defense against data poisoning requires the learning algorithm, rather than the classification process as in Pixel-DP, to be randomized. We add noise on the updates (user-level DP) gradient (instance-level DP) over every training round to make the trained FL. model satisfy DP, which requires careful privacy budget analysis of the DPFL model over multiple training rounds considering the distributed nature and the model training dynamics.
Empirically, we explicitly evaluate the relationship between the privacy protection level e and the certified robustness based robustness criteria on three datasets, indicating the fundamental connections quantitatively. Moreover, we compare the certified robustness of different existing user-level DPFL algorithms.
Ma al. 2019) analyze the lower bound of certified cost in centralized DP learning while we use the certified cost as one of our certification criteria for different definitions of DP in FL and additionally derive its upper bounds.
30


Reviews:
[{"review_id": "Ic8tLWrcH4U", "reviewer": "Reviewer_u4ds", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Update: Thank you for your response. I read the authors' response and other reviewers' comments. My second question has been well addressed. However, as other reviewers suggested, the contributions of this paper and comparisons with prior work should be explained more clearly. I would not consider the main contribution as the theory part, because given the group privacy property of DP, this result is not very surprising. I would suggest the authors highlight the empirical contributions and federated learning setting.\n\n\nStrengths:\n1. I think this paper provides an interesting perspective for robust machine learning. \n2. The empirical evaluations are solid.\n3. the proposed algorithms are practically useful\n\n\nWeaknesses:\n1. I think the results are correct but not surprising. There have been many papers (theoretically and empirically) showing either robust algorithms can be made private easily and private algorithms provide intrinsic robustness. \n\n2. It would be better if the authors could provide some theoretical/empirical intuition for the utility. It is known that both robust learning algorithms and private algorithms would cause the performance drop. It would be nice if the authors could provide non-private(epsilon=infty) clean accuracy as a comparison.\n\n", "summary_of_the_paper": "This paper studies differentially private federated learning and its intrinsic robustness against data poisoning attacks. Theoretically, the authors build two definitions for certified robustness against data poisoning attacks, draw the connection with user-level and instance-level differential privacy. The key proof is based on the definition of individual privacy and group privacy. Empirically, the authors verify the correctness of the bounds by performing real attacks. I think the main contribution is to establish the robustness bound.", "summary_of_the_review": "This paper is overall well-written and provides new insight on intersection of robustness and privacy.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "HFmuxiVSuyn", "reviewer": "Reviewer_T4mM", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nStrength: the paper proposes criteria for robustness of FL, evaluates the theoretical results using MNIST and CIFAR datasets.\n\n\nWeakness: I can't entirely agree with the paper's message that the certification comes for free and instead suggest that this certification comes at a relatively high price requiring differential privacy. For example, [1] uses gradient shaping without full DP. However, I would agree that in cases where differential privacy is inevitable, the conclusions seem helpful and could further promote the use of DP.\n\nFurthermore, the paper does not evaluate the effects of certification on performance reduction for the benign data. Specifically, I am surprised by an extremely low budget in CIFAR for the presented experiments, i.e. epsilon less than 1 and an extreme amount of noise, i.e. std around 10.  Clarifying further A.3.2 that has only few rounds would be helpful.The provided certification might not provide much utility, especially for diverse users already disproportionally affected by less strict DP budget.\n\nEvaluating the proposed method on the Language Modeling task might further strengthen the submission to provide a realistic privacy training regime. \n\n\n\n[1] Sanghyun Hong, Varun Chandrasekaran, Yig ̆itcan Kaya, Tudor Dumitras ̧, and Nicolas Papernot. On the effectiveness of mitigating data poisoning attacks with gradient shaping. arXiv preprint arXiv:2002.11497, 2020. ", "summary_of_the_paper": "The paper states that the model produced by differentially private federated learning to be already certified against poisoning attacks. \n", "summary_of_the_review": "The paper proposes a good analysis of provided robustness guarantees, but further clarification of experiments would be very helpful.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "DxHC9AhV0z4", "reviewer": "Reviewer_Rayz", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strong points:\ni) The problem of data poisoning is an important one, and the connection between robustness and privacy is a nice one to use for getting provable guarantees.\nii) After doing some sporadic checking, I have not found any actual mistakes in the proofs.\n\nWeak points (and comments/questions for the authors):\n1) In my opinion the paper lacks focus: there are plenty of DPFL algorithms introduced, but very little testing and comparisons to existing work, while what I take as the main contribution, i.e., the certified robustness, is overshadowed by the FL parts and seems unfinished.\n\n2) It is generally somewhat hard to tell which parts are meant as original contributions and which are referencing existing work (e.g. Sec 4.1, is this meant as original contribution or just paraphrasing existing work?)\n\n3) The threat models of the proposed DPFL algorithms are not quite clear to me: e.g. for insDP, are the DP guarantees supposed to hold against adversaries who can poison some samples during the training? If so, this should probably affect the privacy guarantees resulting from subsampling in InsDP-FedSGD (since the adversary could have knowledge it the data partition in question has been chosen in the update?). How are the other DPFL adversaries?\n\n4) The paper tends to oversell it's contribution:\n4.1) The certified prediction Thm1 and it's proof match almost exactly with Prop1 from Lecuyer et al. 2019, the same goes for Thm3 and Cor1 compared to Ma et al. 2019 Thm4, and Cor6. Although both works are cited in the current paper, I do feel that this near-identity should be clearly and unambiguously stated in introducing these results. There is some discussion on this right before Section 6 noting similarities with Lecuyer et al., but stating that \"ours focus on the robustness against training-time attacks in FL, which is more challenging considering the distributed nature and the model training dynamics, i.e., the analysis of the privacy budget over training rounds\". But the federated setting only shows up in ascertaining that a training algorithm satisfies DP and in considering a suitable neighbourhood definition, it clearly does not complicate matters in the certified robustness Thms. If anything I would think that the no-show of any notion of federation in the proofs shows that at bottom these problems boil down to the ones considered by Lecuyer et al. & Ma et al. and are therefore not any harder. In general I find it a bit misleading that the results are introduced as somehow specifically concerning FL, when the certifiability results actually just use properties of DP, no matter if the setting is federated, otherwise distributed, or centralised; the main things are the neighbourhood definition (to determine what the adversary can control) and the privacy parameters.\n\n4.2) As for the privacy accounting, since the proposed DPFL algorithms seem to be simple modification of existing ones, the privacy cost can be readily and accurately calculated using existing tools, and this seems to be exactly what the authors do. It is therefore hard to see what value does the hard-to-read Moments accountant type Prop.1 bring (note also that there exists a newer and much clarified paper on RDP, which results in improved bounds [1]).\n\nReferences:\n[1] Mironov et al. 2019: Rényi Differential Privacy of the Sampled Gaussian Mechanism", "summary_of_the_paper": "## Update after rebuttal and discussions\n\nI thank the authors for taking the time to discuss the issues pointed out in the reviews at length. Unfortunately, I am still not convinced that the paper is ready for publication. My main concerns:\n\n1) There are now experiments in the updated paper claimed to be DP which are not (median clipping).\n\n2) I continue to have doubts about the subsampling amplification. Simply stating that the sampling is random is not good enough, since the key issue is the added uncertainty due to the subsampling: if the sampling does not increase the adversary's uncertainty, there is no amplification. As an immediate remedy, I suggest the authors state the threat model more clearly.\n\n3) I still think the paper can be improved a lot by taking the time to rewrite it focusing on the main contribution of certified robustness under DP and clarity of the presentation.\n\n---\n\nThe paper looks at the robustness properties of differentially private (DP) federated learning (FL), focusing on learning classification models from labeled data. The main idea is to turn DP privacy guarantees into certifiable robustness properties. The authors look at 2 certifiable properties, namely, certified prediction (data poisoning does not alter most likely label), and certified attack cost (there is a lower bound on the loss the given attack tries to minimize). They continue to show that DP models in general guarantee these on some level that depends on the privacy bounds. The paper also presents several DPFL learning algorithms for user and instance-level DP.", "summary_of_the_review": "While the paper seems to propose many different things, I find that these are mostly small variations on existing work and I think the authors tend to overstate the papers' contribution (see main review for more detailed comments). The paper generally also feels disorganized due to having several disparate topics (algorithms for training DPFL models, some results that would fit privacy accounting paper better, certifiable properties of DP models). In general, I think this paper could clearly benefit from more work to sharpen the focus and the contribution it has to make, and to make it more clear and readable as well.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "7dh6dYlakpE", "reviewer": "Reviewer_oz1G", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I was very intrigued by the paper at first but ended up having a mixed feeling after reading it. \n\nOn the one hand, the results presented are correct, the experiments are solid, and the paper is rather complete from theory to evaluation.\n\nOn the other hand, I have several concerns about the paper. First, the main result presented is very similar to [1]. Although the attack scenarios are different, the intuition is almost the same. This raises my concern about the novelty of the work. Second, I do not understand why the authors choose to limit the results to the federated setting. IIUC, the robustness claims should generally hold against data poisoning attacks and there is no specific optimization for federated learning. User-level DP is also not limited to federated learning. I would say FL is more of an application scenario here. Third, if the authors really want to focus on federated learning, then the instance-level DP section does not make sense because all federated protocols should preserve user-level DP in practice.\n\nOverall, I think the paper is not ready for publication for now. I encourage the authors to tweak the presentation carefully to make it coherent.\n\n\n[1] Lecuyer, Mathias, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. \"Certified robustness to adversarial examples with differential privacy.\" In 2019 IEEE Symposium on Security and Privacy (SP), pp. 656-672. IEEE, 2019.", "summary_of_the_paper": "This paper proves that differential privacy indicates certified robustness against poisoning attacks in federated learning.", "summary_of_the_review": "I do not recommend for acceptance because of (1) lack of novelty; (2) incoherent presentation.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The premise is an exciting observation: Differential privacy in federated
learning might imply being certified against poisoning attacks. While
this may be considered not surprising by some, the connection between
differential privacy and robustness is interesting to many. The
relationship was characterized both theoretically and empirically.

The reviewers discussed the paper extensively with the authors, and
while many issues were clarified, issues on correctness still
remained: it is unclear if the proposed DP mechanism actually is DP,
and subsampling amplification also had issues. Clarity needs to be
added in the writing, and the extensive comments by the reviewers
hopefully help the authors in that.
Decision: Reject