FedGame: A Game-Theoretic Defense against Backdoor Attacks in Federated Learning
Authors: Jinyuan Jia
Zhuowen Yuan
Dinuka Sahabandu
Luyao Niu
Arezoo Rajabi
Bhaskar Ramasubramanian
Bo Li
Radha Poovendran
Venue: NeurIPS 2023 poster (2023)
Keywords: backdoor defense
federated learning
game theory

Abstract: Federated learning (FL) provides a distributed training paradigm where multiple clients can jointly train a global model without sharing their local data. However, recent studies have shown that FL offers an additional surface for backdoor attacks. For instance, an attacker can compromise a subset of clients and thus corrupt the global model to misclassify an input with a backdoor trigger as the adversarial target. Existing defenses for FL against backdoor attacks usually detect and exclude the corrupted information from the compromised clients based on a static attacker model. However, such defenses are inadequate against dynamic attackers who strategically adapt their attack strategies. To bridge this gap, we model the strategic interactions between the defender and dynamic attackers as a minimax game. Based on the analysis of the game, we design an interactive defense mechanism FedGame. We prove that under mild assumptions, the global model trained with FedGame under backdoor attacks is close to that trained without attacks. Empirically, we compare FedGame with multiple state-of-the-art baselines on several benchmark datasets under various attacks. We show that FedGame can effectively defend against strategic attackers and achieves significantly higher robustness than baselines. Our code is available at: https://github.com/AI-secure/FedGame.

FedGame: A Game-Theoretic Defense against Backdoor Attacks in Federated Learning
Jinyuan Jia
Zhuowen Yuan" UIUC zhuowen3i1llinois.eem
The Pennsylvane State University j jinyuanOpsu.edu
Dinuka Sahabandu University of Washington sdinuka@uw edu
Luyao Niu University of Washington luyaoniusus edu
Arezoo Rajabi
University of Washington rajabia@ur edu
Bhaskar Ramasubramanian Western Washington University ramasubêvwu. edu
Bo Li UIUC lbo@illinois. edu
Radha Poovendran University of Washington
rp3@uw.ede edu
Abstract
Federated learning (FL) provides a distributed training paradigm where multiple clients can jointly train global model without sharing their local data. However, recent studies have shown that FL offers an additional surface for backdoor attacks. For instance, an attacker can compromise subset clients and thus corrupt the global model to misclassify an input with a backdoor trigger as the adversarial target. Existing defenses for FL against backdoor attacks usually detect and exclude the corrupted information from the compromised clients based static attacker model. However, such defenses are inadequate against dynamic attackers who strategically adapt their attack strategies. To bridge this gap, model the strategic interactions between the defender and dynamic attackers as minimax game. Based the analysis of the game, design interactive defense mechanism FedGame. We prove that under mild assumptions, the global model trained with FedGame under backdoor attacks is close to that trained without attacks. Empirically, compare FedGame with multiple state-of-the-ari baselines on several benchmark datasets under various attacks. We show that FedGame against strategic attackers and achieves significantly higher robustness than base- lines. Our code is available https: http::///ithbbe com/ AI secure FFedGGmee
effectively defend
Introduction
Federated learning (FL) (21 28 aims train global model over training data that distributed across multiple clients (e.g., mobile phones, 1oT devices) in an iterative manner. In each communica- tion round, cloud server shares its global model with selected clients. Then, each selected client uses the global model to initialize its local model, utilizes its local training dataset to train the local model, and sends the local model update the server. Finally, the integrate local model updates from clients to update its global model.
uses aggregation rule
Due to the distributed nature of FL, many studies 3 4 5 21 44
have shown that FL is vulnerable to 59 For instance, an attacker can compromise
backdoor attacks [ 18
30
55
"Equal contribution.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

a subset of clients and manipulate their local training datasets to corrupt the global model such that predicts an attacker-chosen target class for any inputs embedded with a backdoor trigger [3] To
defend against such backdoor attacks, many defenses 7 32 34
36
39
51 have been proposed (see
Section for details). However, all those defenses consider a static attack model where an attacker sticks to a fixed strategy and does not adapt its attack strategies. As result, they are less effective
under adaptive attacks, c.g., Wang et al. [44] showed that defenses in [6 [3] can be bypassed by appropriately designed attacks. While the vulnerability of the FL against dynamic or adaptive attack is known, dynamic defense has not been well-studied yet.
In this work, we propose FedGame, a thenrete defense against backdoor attacks in FL. Specifically, we formulate FedGame as minimax game between the server (defender) and attacker, enabling them to adapt their defense and attack strategies strategically. While the server has no prior knowledge about which client compromised, our key idea that the server can compute a genuine score for each client, which should be large (or small) if the client is benign (or compromised) in each communication round. The genuine score serves as a weight for the local model update of the client when used to update the global model. The goal of the defender is to minimize the genuine scores for compromised clients and maximize them for benign ones. To solve the resulting minimax game for the defender, we follow three-step process consisting of I) building exploiting the auxiliary global model to reverse engineer a backdoor trigger and target class, and 3) testing whether the local model of client will predict an input embedded with the reverse engineered backdoor trigger as the target class to compute a genuine score for the client. Based on the deployed defense, the goal of the attacker is to optimize its attack strategy by maximizing the effectiveness of the backdoor attack while remaining stealthy. Our key observation is that the attack effectiveness is determined by two factors: the genuine score and the local model of the client. We optimize the attack strategy with respect to those two factors to maximize the effectiveness of backdoor attacks against dynamic defense.
auxiliary global model, 2)
We perform both theoretical analysis and empirical evaluations for FedGame. Theoretically, we prove that the global model trained with our defense under backdoor attacks is close to that trained without attacks (measured by Euclidean distance of model parameters). Empirically, we perform comprehensive evaluations. In particular, we evaluate FedGame benchmark datasets to demon- strate its effectiveness under state-of- ofate--o-the-aate the-art backdoor attacks [3] [4] 59]. Moreover, we compare with six stafe-of-the-ar baselines 7 36, 39 (66.. Our results indicate that FedGame outperforms them by a significant margin (e.g., the attack success rate for FedGame is less than 13% while is greater than 95% for those baselines CIFAR1O 10 under Scaling attack (3). We also perform comprehensive ablation studies and evaluate FedGame against adaptive attacks, Our results show FedGame is consistently effective. Our key contributions are as follows:
We propose FedGame, the first theerethe defense against dynamic backdoor attacks to FL.
We provide theoretical guarantees of FedGame. We show that the global model trained with FedGame under backdoor attacks is close to that without attacks.
We perform systematic evaluation of FedGame on benchmark datasets and demonstrate that FedGame significantly outperforms state-of-the-art baselines.
2
Related Work
Backdoor Attacks in FL. In backdoor attacks against FL 3 3 44 50 59 an attacker aims to make a global model predict a target class for any input embedded with a backdoor trigger via compromised clients. For instance, Bagdasaryan et al. [3] proposed the scaling attack in which an attacker first uses a mix of backdoored and clean training examples to train its local model and then scales the local model update by a factor before sending the server. In our work, we will leverage state-of-the-ar attacks 3 54 59 to perform strategic backdoor attacks against our defense.
9 were proposed to mitigate backdoor attacks in FL. For instance, Sun et al. 39 proposed norm- corm-clipping. which clips the norm of the local model update of client to certain threshold. Some work extended differential privacy 15 20 to mitigate backdoor attacks to federated learning. The idea is to clip the local model update and add Gaussian noise. Cao et al. 7 proposed FLTrust, which leveraged the similarity of the local model update of client with that computed by the server itself on its
Defenses against Backdoor Attacks in FL. Many defenses 139

---

clean dataset. DeepSight [36 performs clustering on local models and then filters out those from compromised clients. By design, DeepSight is ineffective when the fraction of compromised clients is larger than 50%. Other defenses include Byzantine-robust FL. methods such as Krum [6] Trimmed Mean [56], and Median [56]. However, all of those defenses only consider static attacker model. As result, they become less effective against dynamic attackers who strategically adapt their attack strategies.
Another line of research focuses on detecting compromised clients 58 As those defenses need to collect many local model updates from clients to make confident detection, the global model may already be backdoored before those clients are detected. Some recent studies 53 57 10) proposed certified defenses against compromised clients. However, they can only tolerate a moderate fraction of compromised clients (e.g.. less than 10%) as shown in their results. In contrast, FedGame can tolerate much higher fraction (e.g., 80%) of compromised clients.
In this work, we aim to prevent backdoor attacks to federated learning, i.e., our goal is to train a robust global model under compromised clients. The server could also utilize post-training defenses 51 to remove the backdoor in a backdoored global model. Prevention-basee defense could be combined with those post-training defenses form defense-in-depth. We note that the defense proposed in 43 requires the server to own some clean samples that have the same distribution as the local training data of clients. The defense proposed in [51] prunes filters based on pruning sequences collected from clients and thus is less effective when the fraction of compromised clients is large.
3 Background and Threat Model
Federated Learning, Let S denote the set of clients and D, denote the local training dataset of client E S. In the 8th communication round, the server first sends the current global model O to the selected clients. Then, each selected client i trains local model (denoted O)) by fine- tuning the global model Of using its local training dataset D,. For simplicity, we use z = (x, y) to denote training example in D,, where x is the training input (e.g., image) and y is its ground truth label. Given D, and the global model e', the local objective is defined as [(,;; 0t) = [Dl ExED, {(z; 6²) where L is loss function (e.g., cross-entropy loss). The client can use gradient descent to update its local model based on the global model and its local training dataset, i.e., O 0 aC(D,,e") where 7) is the local learning rate. Note that stochastic gradient descent can also be used in practice. After that, the client sends of O O' (called local model update) to the server. Note that it is equivalent for the client send a local model or local model update to the server as O = O + gf- After receiving the local model updates from all clients, the server can aggregate them based on an aggregation rule R (e.g., FedAvg
øer
(28) to update its global model, i.e., we have e = O' + r/R oh. Iss) where |S] represents the number of clients and 17 is the learning rate of the global model.
Threat Model. We consider attacks proposed in previous work [3 54 59] can compromise a set of clients (denoted as S,). To perform backdoor attacks, the attacker first selects an arbitrary backdoor trigger 8 and target class y²c For each client i E S, in the th (f= (,=1,2,... communication round, the attacker can choose an arbitrary fraction (denoted as r() of training examples from the local training dataset of the client, embed the backdoor trigger 5 to training inputs. and relabel them as the target class y* In state-of-the of-the-rrt backdoor attacks 3 54 59], the attacker leverages those trigger-embedder training examples inject the backdoor into the local model of compromised client to attack the global model.
We assume an attacker
Following 77, we consider that the server itself has small clean training dataset (denoted as D.), which could be collected from the same or different domains of the local training datasets of clients. Note that the server does not have 1) information on compromised clients, and 2) the poisoning ratio rf (i E S,),, backdoor trigger ö, and target class y* selected by the attacker. In our threat model, we do not make any other assumptions for the server compared with standard federated learning 28
4 Methodology
Overview. We formulate FedGame as minimax game between the defender and attacker, which enables them to optimize their strategies respectively. In particular, the defender computes genuine
3

---

score for each client in each communication round. The goal of the defender is to maximize the genuine score for a benign client and minimize it for a compromised one. Given the genuine score for each client, we use weighted average over all the local model updates to update the global model, i.e., we have
@++1= = + ZiES Pi
Eviol iES
(I)
where of is the genuine score for client i in the 4 communication round and is the learning rate of the global model. We compute a weighted average local models because we aim to achieve robustness against attacks while making minimal changes to FedAvg (28], which has been shown to achieve high utility in diverse settings. In our experiments, we empirically show that the genuine scores are almost constantly 0 for malicious clients after few communication rounds, which indicates that the malicious model updates will not be aggregated at all, reducing Equation | to a robust FedAvg against attacks. (See Figure 2 (d) in the Appendix for more details.) Based on Equation T the effectiveness of the attack is determined by two components: genuine scores and local models of compromised clients. In our framework, the attacker optimizes the tradeoff between these two components to maximize the effectiveness of backdoor attacks.
4.1 Game Formulation
Computing Genuine Scores. The key challenge for the server to compute genuine scores for clients is that the server can only access their local model updates, i.e., the server can only leverage local models clients to compute genuine scores. To tackle this issue, we observe that the local model of compromised client is more likely to predict trigger-embedded input as the target class. Therefore, the server can first reverse engineer the backdoor trigger ö,e and target class yfa (which will discuss more in the next subsection) and then them to compute the genuine score for each client. Since the client sends its local model update of to the server, the server can compute the local model of the client i as θ O of. With O the server can compute y as follows:
p =
1
Σ I(G(x 2 8re: O)) v(a), XED.
[
where I is an indicator function, D. is the clean training dataset of the server, x O 6,c is a trigger- embedded input, and G(x 8yc; O²) represents the label of x @ ône predicted by Ot. Intuitively, the genuine score for client i is small if large fraction of inputs embedded with the reverse-engineered backdoor trigger is predicted the target class by its local model. We note that the defender only needs to query local models to compute their genuine scores. Moreover, our defense is still applicable used to protect the local models.
when differential privacy 14 49
Optimization Problem of the Defender. The server aims to reverse engineer the backdoor trigger dre and target class yfe such that the genuine scores for compromised clients are minimized while those for benign clients are maximized. Formally, we have the following optimization problem:
Σ p)). JESYSS
min Sve C
FESS
Note that S₂ is the set of malicious clients that is unknown to the server. In the next subsection, we will discuss how to address this challenge to solve the optimization problem.
Optimization Problem of the Attacker. The goal of an attacker maximize its attack effective- ness. Based on Equation []] the attacker needs to: 1) maximize the genuine scores for compromised clients while minimizing them for benign ones, i.c., max(E pf Ejests, P³)). and 2) make the local models of compromised clients predict an input embedded with the attacker-chosen backdoor trigger ó as the target class yt To perform the backdoor attack in the 8t communication round, the attacker embeds the backdoor to a certain fraction (denoted as r:) of training examples in the local training dataset of the client and uses them as data augmentation. Intuitively, larger rf encourages a higher attack success rate but can potentially result in a lower genuine score. In other words, rf measures a tradeoff between these two factors. Formally, the attacker can solve the following

---

optimization problem to find the desired tradeoff:
max R AA
Σ
Σ
P. Σ
p
Σ
IES
JES(S,
SES.
where R² = (r] i S.). is is the trigger, and À is hyperparameter to balance the two terms.
Minimax Game Given the optimization problems of the defender and attacker, we have the following minimax game:
min max p OPE iES.
Σ
Σ JESYS.
PJ
r iES
(5)
Note that r (i E S.) and d are chosen by the attacker. Thus, we can add them to the objective function in Equation 3 without influencing its solution given the local model updates of clients. In Section of Appendix, we provide an intuitive interpretation regarding how to connect our above objective to the ultimate goal of the defender and attacker (the defender aims to obtain a clean model, while the attacker wants the global model to be backdoored).
4.2 Solving the Minimax Game by the Defender
The key challenge for the server to solve Equation is that it does not know S. (set of compromised clients). To address the challenge, our idea is to construct an auxiliary global model based on local models of all clients. Suppose gf is the local model update sent by each client E S to the server. Our auxiliary global model is constructed as follows: O 0 [| Eies Ii, where O' is the global model. Our intuition that such a naively aggregated auxiliary global model inclined to predict rriger--mbedded input the target class under backdoor attacks, As result, given the auxiliary global model, we can use an arbitrary existing method [42
48 to reverse engineer the backdoor trigger and target class based on it, which enables to compute genuine scores for clients based on Equation 2 With those genuine scores, we can use Equation to update the global model protect it from backdoor attacks in every communication round. The complete algorithm of our FedGame is shown in Algorithm of Appendix.
46
38
Our framework is compatible with any trigger reverse engineering methods, allowing off- off-the-shell incorporation of techniques developed for centralized supervised learning into federated learning. Note that developing new reverse engineering method is not the focus of this work. Instead, our goal to formulate the attack and defense against backdoor attacks on federated learning as a minimax game, which enables to defend against dynamic attacks.
4.3 Solving the Minimax Game by the Attacker
The goal of the attacker is to find rf for each client E E.,, such that the loss function in Equation is maximized. As the attacker does not know the genuine scores of benign clients, the attacker can find r to maximize o + Arς for client E S, to approximately solve the optimization problem in Equation 5 However, the key challenge is that the attacker does not know the reverse engineered backdoor trigger d,e and the target class yte of the defender to compute the genuine score for the client i. In response, the attacker Moreover, the attacker reserves a certain fraction (e.g.. 10%) of training data from its local training dataset D, as the validation dataset (denoted Dr to find the best r/
the backdoor trigger 8 and target class y chosen by itself.
Estimating the Genuine Score Given rf. For a given rj. the client i can embed the backdoor to rf fraction of training examples in D; Drew and then use those backdoored training examples to augment D; Drew train local model (denoted θ³). Then, the genuine score be estimated as 인 = D ExeD I(G(x @ 8; Qt) = y²)), where G(x ① 8; θt) is the predicted label by the global model é for the trigger-embeedded input x @
Finding the Optimal r!. The client can use grid search to find rf that achieves the largest pt + Arf. After estimating the optimal rf. client can embed the backdoor to rf fraction of training examples and utilize them to perform backdoor attacks based on ofte-oof-theart methods [ [44 59
5

---

Trigger Optimization. The attacker can choose an arbitrary static trigger to launch backdoor attacks, or dynamically optimize it to make the attack more effective. Given the fixed location and bounding box of the backdoor trigger, the attacker can optimize the trigger pattern with gradient descent such that it is more likely for a backdoored input to be predicted as the target class. For instance, the attacker can optimize the trigger pattern to minimize the cumulative loss on all training data of malicious clients, i.e., 8 argming. ExEu,es D; E(O' @ 8*), " where O' @ 8*) is the output of the model which is a probability simplex of all possible classes and é is a standard loss function (e.g., cross-entropy loss). The attacker can then solve Equation 5 with the optimized trigger. Recall that the attacker aims to find the largest f?, + Ar.. Therefore, if the resulting i + Ar! given 5
is lower than that given the previous trigger 5'-1, we let 8 = 8'-1
The complete algorithm for the compromised clients is shown in Algorithm 2 in Appendix C
Theoretical Analysis
This section provides a theoretical analysis of FedGame under backdoor attacks. Suppose the global model parameters are in a bounded space. We derive an upper bound for the L2-norm of the difference between the parameters of the global models with and without attacks. To analyze the robustness of FedGame, we make the following assumptions, which are commonly used in the analysis of previous on federated learning.
studies (25 45 16
35
53 7
Assumption 5.1. The loss function is p-strongly convex with Z-Lipschitz continuous gradient. Formally, we have the following for arbitrary O and O':
(Vel(z; 0) - V (z) - 0¹) 2 / - 0'12 - [Vol(z; 0)= - V Ee 6')1l & - - 0'll
where z is an arbitrary training example. Assumption 5.2. We assume the gradient Vz +) is bounded with respect to L2-norm for arbitrary and z, i.e., there exists some M 2 such that
[ 1) - M.
(8)
Suppose O is the global model trained by FedGame without any attacks in the ith communication round, i.e., each client i E S uses its clean local training dataset D, to train local model. Moreover, we assume gradient descent is used by each client to train its local model. Suppose of is the genuine score for client i without attacks. Moreover, we denote B
of Exes of as the normalized genuine score for client i. To perform the backdoor attack, we assume compromised client i can embed the backdoor trigger to r fraction of training examples in the local training dataset of the client and relabel them as the target class. Those backdoored training examples are used to augment the local training dataset of the client. Suppose O' the global model under the backdoor attack in the tth communication round with our defense. We denote af Eies as the normalized genuine score for client with attacks in the tth communication round. Formally, we have:
pf
Lemma 5.3 (Robustness Guarantee for One Communication Round). Suppose Assumptions 5.7 and 5.2 hold. Moreover, we assume (1 - r' )B) < of S (1 (1)))),, where E S and r" ====1 -Ejes. fj. Then, we have;
10 0C+1 2
(9)
SV1 nH + 2m7 + 17 12 2n ||0 O''l2 + 2m 2mmx") + 2m M,
(10)
where 11 is the learning rate of the global model, L and are defined in Assumption 5.1 Eves, M, and M is defined in Assumption 5.2
7*
Proof sketch. Our idea is to decompose ||@]+1 - O ||1 into two terms. Then, we derive an upper
bound for each term based on the change of the local model updates of clients under backdoor attacks and the properties of the loss function. As result, our derived upper bound relies on r for each client i E S., parameters μr, I., and M our assumptions, as well as the parameter difference of the global models in the previous iteration, i.c., ||e O Our complete proof is in Appendix B.
D

---

In the above lemma, we derive an upper bound of ||@ - -
I|2 with respect to || - 22 for
one communication round. In the next theorem, derive an upper bound of ||@' - d'll2
oo.
We iterative apply Lemma 5.3 for successive values of t and have the following theorem:
Theorem 5.4 (Robustness Guarantee). Suppose Assumptions 5.1 and hold. Moreover, we assume (1 - r S o S (1 + for E S. 76 < " and r² I r hold for all communication round t, and μ > 27, where r² =EEes jes, r'j and yt Lies. afr), M. Let the global model learning rate by
chosen 0
2- Then, have: 1222
V2n + 21m) + 2yr
|10 - 1 S 1 V1- mu 2177 112 2112
(11)
holds as + DG.
Proof sketch. Given the conditions that 7 S and rf r as well as the fact that the right-hand side of Equation 10 is monotonic with respect to 7 and r', we can replace y and r' in Equation 10 with y and r. Then, we iterative apply the equation for successive values of L. When < 1 7'421""
we have < 1 nu + 2nyy + 1²² + 2xj² Ly < 1. By letting oo, The complete proof can be found in Appendix B.2
reach the conclusion.
Our theorem implies that the global model parameters under defense against adaptive attacks do not deviate too much from those of the global model without attack when the fraction backdoored training examples rf is bounded.
6 Experiments
In order to thoroughly evaluate the effectiveness FedGame, we conduct comprehensive experiments on 1) evaluation against three state-of-the-arl backdoor attacks: Scaling attack (3). DBA [54), and Neurotoxin [59], 2) comparison with six existing baselines including Krum, Median, Norm-Clipping, Differential Privacy, DeepSight, FLTrust, 3) evaluation against strong adaptive attacks, and 4) comprehensive ablation studies.
6.1 Experimental Setup
Datasets and Models. We use benchmark datasets: MNIST (3 and CIFARIO 22 for FL tasks. MNIST has 60,000 training and 10,000 testing images, each of which has a size of 28 x 28 belonging to of 10 classes. CIFAR10 consists of 50,000 training and 10,000 testing images with a size of 32 x 32. Each image is categorized into one of 10 classes. For each dataset, we randomly sample 90% of training data for clients, and the remaining 10% of training data is reserved to evaluate our defense when the clean training dataset of the server is from the same domain as those of clients. We use CNN with two convolution layers (detailed architecture in Appendix) and ResNet- 18 [99 which is pre- pre-trained on ImageNet [13 as the global models for MNIST and CIFAR1O.
be found in Table
FL Settings. We consider two settings: local training data are independently and identically distributed (IID) among clients, and non-lID. We follow the previous work [17] to distribute training data to clients by using parameter q to control the degree of non-IID, which models the probability that training images from one category are distributed to a particular client (or a set of clients). We set 0.5 by following [77. Moreover, we train global model based on 10 clients for 200 iterations with a global learning rate r = 1.0. each communication round, we use SGD to train the local model of each client for two epochs with local learning rate of 0.01.
Attack Settings. We consider three state state-of-the-ar backdoor attacks on federated learning, i.e.. Scaling attack (3]. DBA (54), and Neurotoxin [59]. For Scaling attack, we set the scaling parameter to be #total clients/ (eeeic/p*ccopmmn #compromised clients) by following 3. For Neurotoxin, we set the ratio of masked gradients to be 1%, following the choice in [59]. We use the same backdoor trigger and target
class as used in those works. By default, we assume 60% of clients are compromised by an attacker.
When the attacker solves the minimax game in Equation 5 we set the default À 1. We explore the
7

---

Table 1: Comparison of FedGame with existing defenses under Scaling attack and DBA. The total number of clients is 10, where 60% are compromised. The best results for each setting among FedGame and existing defenses are bold.
Client
FedAvg
Defenses (Under attacks)
Attacks Data
Datasets
Metries
(Without attacks)
FedGame
Distri-
FedAvg Krum Median
Norm- Clipping
DP
Deep- FL.Trsst Sight
bution
In Domain Domain
Out-of
MNIST
TA (%)
99.04
98.77
98.78
99.17
95.48
92.97 97.69
97.93
98.53
98.56
ASR (%)
9.69
99.99
99.99
99.97
98.54
99.45
20.03
16.01
9.72
9.68
IID
CIFARIO
TA (%)
81.08
80.51
76.44
80.17
80.38
43.22
76.79
75.71
74.81
74.65
Scaling
ASR (%)
8.39
99.80
99.94
99.82
99.87
99.58
98.58
99.46
8,92
9.24
Attack
TA (%)
98.98
99.15
96.88
99.12
94.54
91.52
97.39
97.68
98.28
98.34
MNIST
non-IID
ASR (%)
9.73
99.99
85.03
99.98
98,16
99.54
20.03
19.61
10.42
10.88
TA (%)
80.25
75.35
67.66
79.54
70.18
50.79
77.76
75.08
73.88
73.57
CIFARIO
ASR
9.67
99.92
99.92
99.99
99.63
95.01
99.03
99.82
11.76
12.03
MNIST
TA (%)
99.04
99.03
98.87
98.98
98.99
98.99
98.64
97.98
97.84
98.05
IID
ASR (%)
9.69
100.00
10.06
99.81
99.75
99.73
15.02
10.02
9.56
9.68
TA (%)
81.08
80.90
76.09
80.00
80.21
41.36
72.13
75.17
73.18
72.93
CIFARIO
DBA
ASR (%)
8.39
93.44
94.97
91.60
91.90
86.96
83,26
66.58
8.81
9.00
MNIST
TA (%)
98.98
98.98
98.58
99.13
93.98
88.91
96.65
97.62
98.58
98.59
ASR (%)
9.73
100.00
10.52
99.85
55.97
99.66
13.21
10.19
9.97
9.83
non-IID
CIFARIO
TA (%)
80.25
80.15
74.31
79.78
78.78
38.17
73.83
74.57
73.52
73.21
ASR (%)
9.67
95.03
60.06
95.00
92.51
99.51
80.75
74.35
10.62
10.67
impact of À in our experiments. We randomly sample 10% of the local data of each compromised client as validation data to search for an optimal r/. Moreover, we set the granularity of grid search to 0.1 when searching for rf.
Baselines. We compare our defense with the following methods: FedAvg 28
Krum 66, Me-
dian (56). Norm-Clipping [39], Differential Privacy (DP) (39), DeepSight 36 and FLTrust 77.
Please see Appendix D.2 for parameter settings for those baselines.
Evaluation Metries. We use testing accuracy (TA) and attack success rate (ASR) evaluation metrics. Concretely, TA is the fraction of clean testing inputs that are correctly predicted, and ASR refers to the fraction of backdoored testing inputs that predicted as the target class.
Defense Settings. We consider two settings: in-domain and out-of-domain. For the in in-domain setting, we consider the clean training dataset of the server from the same domain as the local training datasets of clients. We use the reserved data as the clean training dataset of the server for each dataset. For the out-of-domain setting, we consider the server has clean training dataset that is from different domain than the FL task. In particular, we randomly sample 6,000 images from FaShionMNIST [52 for MNIST and sample 5,000 images from GTSRB 220 for CIFARIO as the
clean training dataset of the server. Unless otherwise mentioned, we adopt Neural Cleanse 42 to reverse engineer the backdoor trigger and target class.
6.2 Experimental Results
We show the results of FedGame compared with existing defenses under IID and non-III settings in [T] We defer the results against Neurotoxin to Appendix(D.3 [D33 due to space limitations. We have the following observations from the experimental results. First, FedGame outperforms all existing defenses in terms of ASR. In particular, FedGame can reduce ASR to random guessing (i.e., ASR of FedAvg under no attacks) in both IID and non-lllD settings for clients as well as both in-domain and out-of-domain settings for the server. Intrinsically, FedGame performs better because our game- theoretic defense enables the defender to optimize its strategy against dynamic, adaptive attacks. We
8

---

note that FLTrust outperforms other defenses (except FedGame) in most cases since it exploits clean training dataset from the same domain local training datasets of clients. However, FLTrust is not applicable when the server only holds an out-of-domain clean training dataset, while FedGame can relax such an assumption and will still be applicable. Moreover, our experimental results indicate that FedGame achieves comparable performance even if the server holds an out-of-domain clean training dataset.
To further understand our results, we visualize the average genuine (or trust) scores computed by FedGame (or FLTrust) for compromised and benign clients in Appendix D.4 In particular, we find that the genuine scores produced by FedGame are much lower than those produced by FLTrust for compromised clients, which explains why FedGame outperforms FLTrust. Second, FedGame achieves comparable TA with existing defenses, indicating that FedGame preserves the utility of global models.
Furthermore, we show the comparison results of FedGame with existing defenses against the scaling attack when the total number of clients is 30 in Table Appendix D.5 Our observations are similar, which indicates that FedGame consistently outperforms existing defenses under different numbers of clients and backdoor attacks.
Impact of A. À is a hyperparameter used by an attacker (see Eqn. when searching for the optimal of for each compromised client i in each communication round t. Figure ((a) shows the impact of X on ASR of FedGame. The results show that FedGame is insensitive to different X's. The reason is that the genuine score for compromised client is small when À is large, and the local model of compromised client is less likely to predict trigger-embedded input as the target class when is small. As result, backdoor attacks with different À are ineffective under FedGame.
20
Ii Pedkiame
100
I
FLITust
DUFLTrux
100
FLTrus
16
80
JE FedGame
FeleGaame
KadGaan
ASR (8)
ASK (92)
60
60
ASR
30
20
0.5
1.0
2,x2
4x44
6x6
fraction mulicious
fraction participants per
(a)
(b)
(c)
(d)
Figure 1: Comparing FedGame and FLTrust under different variations of attack. (a) Different X. (b) Different fractions of malicious clients. (c) Different numbers of clients selected in each communication round. (d) Different trigger sizes.
shows the impact of the fraction of compromised clients on ASR. As the results show, FedGame is effective for a different fraction of compromised clients in both in-domain and out-of-domain settings. In contrast, FLTrust is ineffective when the fraction of compromised clients is large. For instance, FedGame can achieve 9.84% (in- domain) and 10. 12% (out-of-domain) ASR even if 80% of clients are compromised on MNIST. Under the same setting, the ASR of FL.rrsst is 99.9599999 95,, indicating that the defense fails.
Impact the Fraction of Compromised Clients. Figure ((b)
Impact of Client Selection. By default, we consider that all clients are selected in each communi- cation round. We also consider only subset of clients are selected in each communication round by the server. Figure [(c) shows our experimental results. Our results suggest that our defense is effective and consistently outperforms FLTrust.
Computation Cost. FedGame computes genuine score for each client in each communication
round. Here we demonstrate its computational efficiency. On average, it takes 0.148s to compute a genuine score for each client in each communication round on a single NVIDIA 2080 Ti GPU. We note that the server could from resourceful tech company (e-g., Google, Meta, Apple), which would have enough computation resources to compute for millions of clients. Moreover, those local models can be evaluated in parallel.

---

Performance under Static Attacks. In our evaluation, we consider an attacker optimizing the fraction of backdoored training examples. We also evaluate FedGame under existing attacks where the attacker does not optimize it. Under the default setting, FedGame can achieve an ASR of 9.75%, indicating that our defense effective under static attack.
Furthermore, we discuss the impact of trigger reverse engineering methods, the total number of clients, and the size of clean data of the server in Appendix D.6
6.3 Adaptive Attacks
In this subsection, we discuss some potential adaptive strategies that may be leveraged by the attacker to evade our defense.
Data Replacing Attack. By default, we consider attacker optimizing the fraction of backdoored training examples added to the local training dataset a compromised client to maximize backdoor effectiveness. We also consider attacker who replaces fraction of the local training data with backdoored samples and optimizes such fraction. Under our default setting, the ASR of FedGame is 9.71% % and 10.69% MNIST and CIFAR1O, respectively, indicating that our defense is still effective under data replacing attacks.
Variation in Triggers. We demonstrate that our defense is robust to variation in triggers. In particular. we try triggers with sizes 2 x 2, 4 x 4, and 6 x 6 under the default setting. Figure l(d) compares FedGame with FLTrust. The results demonstrate that FedGame consistently effective under triggers with different sizes.
We note that although an attacker can slightly manipulate the parameters of local models such that they are more similar to those of benign clients, FedGame does not rely on model parameters for detection. Instead, FedGame leverages the model behaviors, i.e., whether the model predicts inputs with our reverse-engee eeggineeeg trigger as the target class. As result, our defense would still be effective even if the change in the model parameters is small as long as the model has backdoor behavior (this is required to make the attack effective). This is also the reason why our defense is better than existing methods such as FL.Trust which leverages model parameters for defense.
7 Conclusion and Future Work
In this work, we propose FedGame, a general game-theory based defense against adaptive backdoor attacks in federated learning. Our formulated minimax game enables the defender and attacker to dynamically optimize their strategies. Moreover, we respectively design solutions for both of them to solve the minimax game. We perform theoretical analysis and empirical evaluations for our framework. Our results demonstrate the effectiveness of FedGame under strategic backdoor attackers. Moreover, FedGame achieves significantly higher robustness than baselines in different settings.
We consider that an attacker could optimize the poisoning ratio and trigger pattern our work. We believe it is an interesting future work to consider other factors for the attacker (e.g.. trigger size, consideration of long-term goal, design of new loss functions [12. poisoned neurons selection (2]). Moreover, consider a zero-sum Stackelberg game in this work. Another interesting future work is to consider other game formulations, e.g., Bayesian games.
Acknowledgements
This work is partially supported by the National Science Foundation (NSF) under grants No. 1910100, No. No.204,..6, No.2153136, No.2229876. DARPA GARD, the National Aeronautics and Space Administration (NASA) under grant No. 80SSSSS2000022,, Alfred P. Sloan Fellowship, Office of Naval Research (ONR) under grant 800014-23-1-2388 Air Force Office of Scientifie Research (AFOSR) under grant FA9550-23-1-0208, and the Amazon research award.
10

---

References
[1] Martin Abadi, Andy Chu, lan Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In ACM SIGSAC Conference Computer and Communications Security, pages 308-318, 2016.
[2] Manaar Alam, Esha Sarkar, and Michail Maniatakos, Perdoor: Persistent non-uniform backdoors federated learning using adversarial perturbations. arXiv preprint arXiv:2205. 2022.
[3] Eugene Bagdasaryan, Andreas Veit, Yiqing Hua, Deborah Estrin, and Vitaly Shmatikov. How to backdoor federated learning. In International Conference on Artificial Intelligence and Statistics, pages 2938-2948. PMLR, 2020.
[4] Gilad Baruch, Moran Baruch, and Yoav Goldberg. A little is enough: Circumventing defenses for distributed learning. Advances in Neural Information Processing Systems, 32, 2019.
[5] Arjun Nitin Bhagoji, Supriyo Chakraborty, Prateek Mittal, and Seraphin Calo. Analyzing feder- ated learning through an adversarial lens. In International Conference on Machine Learning. pages 634 643. PMLR, 2019.
[6] Peva Blanchard, EI Mahdi El Mhamdi, Rachid Guerraoui, and Julien Stainer. Machine learn- ing with adversaries: Byzantine tolerant gradient descent. Advances in Neural Information Processing Systems, 30, 2017.
[7] Xiaoyu Cao, Minghong Fang, Jia Liu, and Neil Zhenqiang Gong. FLtrust: Byzantine-robus' fed- erated learning via trust bootstrapping. In Network and Distributed Systems Security Symposium, 2021.
[8] Xiaoyu Cao, Jinyuan Jia, and Neil Zhenqiang Gong. Provably secure federated learning against malicious clients. In AAAI Conference on Artificial Intelligence, volume 35, pages 6885-6893, 2021.
[9] Xiaoyu Cao, Jinyuan Jia, Zaixi Zhang, and Neil Zhenqiang Gong. Fedrecover: Recovering from poisoning attacks in federated learning using historical information. In 2023 IEEE Symposium on Security and Privacy (SP), pages 1366-1383, IEEE, 2023.
[10] Xiaoyu Cao, 7aixi Zhang, Jinyuan Jia, and Neil Zhenqiang Gong. Fleert: Provably secure federated learning against poisoning attacks. IEEE Transactions on Information Forensics and Security, 17:3691-3705. 2022.
[11] Xinyun Chen, Chang Liu, Bo Li, Kimberly Lu, and Dawn Song. Targeted backdoor attacks on deep learning systems using data poisoning. arXiv preprint 171200520 2017.
[12] Yanbo Dai and Songze Li. Chameleon: Adapting to peer images for planting durable backdoors in federated leamiing arXiv preprint arXiv:2304. 12961, 2023.
[13] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large- scale hierarchical image database. 2009 IEEE conference on computer vision and pattern recognition, pages 248-255. Ieee, 2009.
[14] Cynthia Dwork. Differential privacy. In Automata, Languages and Programming: 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part 11 33, pages 1-12. Springer, 2006.
[15] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography Conference, pages 265-284. Springer, 2006.
[16] Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar. Personalized federated learning: meta-lcarning approach. In Conference on Neural Information Processing Systems, 2020.
[17] Minghong Fang, Xiaoyu Cao, Jinyuan Jia, and Neil Gong. Local model poisoning attacks to Byzantine- Robust federated learning. 29th USENIX Security Symposium, pages 1605-1622, 2020.

---

[18] Tianyu Gu, Brendan Davitt,,vit,, and Siddharth Garg. Badnets: Identifying vulnerabilities in the machine learning model supply chain. arXiv preprint arXiv: 2017.
[19] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In IEEE Conference on Computer Vision and Puttern Recognition, pages 770-778, 2016.
[20] Sebastian Houben, Johannes Stallkamp. Jan Salmen, Mare Schlipsing, and Christian Igel. Detection of traffic signs in real-world images: The German Traffic Sign Detection Benchmark. In International Joint Conference on Neural Networks, number 1288, 2013.
[21] Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Ar- jun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings. et al. Advances and open problems in federated learning, Foundations and Trends in Machine Learning. 14(1-2)) 1200, 2021.
[22] Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009.
[23] Yann LeCun, Corinna Cortes, and CJ Burges. MNIST handwritten digit database. ATT Labs [Online]. Available: http:/yyann.lecum wwwp....///e//////ntiiiii 2, 2010.
[24] Suyi Li, Yong Cheng, Wei Wang, Yang Liu, and Tianjian Chen. Learning to detect malicious clients for robust federated learning. arXiv preprint MxXiv:2022.00211 2020.
[25] Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. On the convergence of FedAvg on non-iid data. In International Conference on Learning Representations, 2020.
[26] Yuezun Li, Yiming Li, Baoyuan Wu, Longkang Li, Ran Hc, and Siwei Lyu. Invisible backdoor attack with sample-specific triggers. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 16463-16472, 2021.
[27] Yingqi Liu, Shiqing Ma, Yousra Aafer, Wen-Chuan Lee, Juan Zhai, Weihang Wang, and Xiangyu Zhang. Trojaning attack on neural networks. In NDSS, 2017.
[28] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas Communication-efin effficienn learning of deep networks from decentralized data. In Artificial Intelligence and Statistics, pages 1273-1282. PMIR, 2017.
[29] Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning differentially private recurrent language models. In International Conference on Learning Representutions, 2017.
[30] Anh Nguyen and Anh Tran. Wanet- ieprreippereeetible warping-based backdoor attack. arXiv preprint arXiv:2102.10330 2021.
[31] Thien Due Nguyen, Phillip Rieger, Huili Chen, Hossein Yalame, Helen Möllering, Hossein Fereidooni, Samuel Marchal, Markus Miettinen, Azalia Mirhoseini, Shaza Zeitouni, et al. Flame: Taming backdoors in federated learning. Cryptology ePrint Archive, 2021.
[32] Thien Due Nguyen, Phillip Rieger, Huili Chen, Hossein Yalame, Helen Möllering, Hossein Fereidooni, Samuel Marchal, Markus Miettinen, Azalia Mirhoseini, Shaza Zeitouni, et al. FLAME: Taming backdoors in federated learning. In 31 USENIX Security Symposium, pages 1415-1432, 2022.
[33] Tuan Anh Nguyen and Anh Tran. Input-aware dynamic backdoor attack. Advances in Neural Information Processing Systems, $3:3454-3466 3464, 2020.
[34] Mustafa Safa Ozdayi, Murat Kantarcioglu, and Yulia R Gel. Defending against backdoors in federated learning with robust learning rate. In AAAI Conference on Artificial Intelligence. volume 35, pages 9268-9276, 2021.
[35] Amirhossein Reisizadeh, Farzan Farnia, Ramtin Pedarsani, and Ali Jadbabaie. Robust federated learning: The case of affine distribution shifts. Advances in Neural Information Processing Systems, 33:21554-21155. 2020.
12

---

[36] Phillip Rieger, Thien Duc Nguyen, Markus Miettinen, and Ahmad-Rezz Sadeghi. DeepSight: Mitigating backdoor attacks in federated learning through deep model inspection. In Network and Distributed System Security Symposium, 2022.
[37] Aniruddha Saha, Akshayvarun Subramanya, and Hamed Pirsiavash. Hidden trigger backdoor attacks. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages 11957-11965, 2020.
[38] Mingjie Sun and Zico Kolter. Single image backdoor inversion via robust smoothed classifiers. arXiv preprini arXiv:2303.002111 2023.
[39] Ziteng Sun, Peter Kairouz, Ananda Theertha Suresh, and H Brendan McMahan. Can you really backdoor federated learning? arXiv preprint 1Xiv:/911.0796. 2019.
[40] Alexander Turner, Dimitris Tsipras, and Aleksander Madry. Label-consistent backdoor attacks. arXiv preprint arXiv: 11X1::1112.02771,2000
[41] Akshaj Veldanda and Siddharth Garg. On evaluating neural network backdoor defenses. arXiv preprint arXiv:2010.12116, 2020.
[42] Bolun Wang, Yuanshun Yao, Shawn Shan, Huiying Li, Bimal Viswanath, Haitao Zheng, and Ben Y Zhao. Neural Cleanse: Identifying and mitigating backdoor attacks in neural networks. In 2019 IEEE Symposium on Security and Privacy, pages 707-723. IEEE, 2019.
[43] Hang Wang, Zhen Xiang, David Miller, and George Kesidis. Universal post-training backdoor detection. arXiv preprint arXiv:2205.066: 069000, 2022.
[44] 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. Advances in Neural Information Processing Systems, 33:16070-16084, 2020.
[45] Jianyu Wang and Gauri Joshi. Cooperative SGD: A unified framework for the design and analysis of communication-etticenn SGD algorithms. Journal of Machine Learning Research, 220213):1-50, 2021.
[46] Zhenting Wang, Kai Mei, Hailun Ding, Juan Zhai, and Shiqing Ma. Rethinking the reverse- engineering of trojan triggers. In Advances in Neural Information Processing Systems, 2022.
[47] Zhenting Wang, Kai Mei, Hailun Ding, Juan Zhai, and Shiqing Ma. Rethinking the reverse- engineering of trojan triggers. arXiv preprint arXiv:2210.15127, 2022.
[48] Zhenting Wang, Kai Mei, Juan Zhai, and Shiqing Ma. Unicom: A unified backdoor trigger inversion framework. In The Eleventh International Conference on Learning Representations, 2023.
[49] Kang Wei, Jun Li, Ming Ding, Chuan Ma, Howard H Yang, Farhad Farokhi, Shi Jin, Tony QS Quek, and H Vincent Poor. Federated learning with differential privacy: Algorithms and performance analysis. IEEE Transactions on Information Forensics and Security, 15:3454- 3469, 2020.
[50] Yuxin Wen, Jonas Geiping, Liam Fowl, Hossein Souri, Rama Chellappa, Micah Goldblum, and Tom Goldstein. Thinking two moves ahead: Anticipating other users improves backdoor attacks in federated learning. arXiv preprint arXiv:2210.09305, 2022.
[51] Chen Wu, Xian Yang, Sencun Zhu, and Prasenjit Mitra. Mitigating backdoor attacks in federated learning. arXiv preprint arXiv:2011.01700 2020.
[52] Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-MNIST: A novel image dataset for benchmarking machine learning algorithms. arXiv preprint
[53] Chulin Xie, Minghao Chen, Pin- Yu Chen, and Bo Li. CRFL:: Certifiably robust federated learning against backdoor attacks. In 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 11372-11382. PMLR, 2021.
13

---

[54] Chulin Xie, Keli Huang, Pin- Yu Chen, and Bo Li. DBA: Distributed backdoor attacks against federated learning, In International Conference on Learning Representations, 2020.
[55] Yuanshun Yao, Huiying Li, Haitao Zheng, and Ben Zhao. Latent backdoor attacks on deep neural networks. In Proceedings of the 2019 ACM SIGSAC Conference Computer and Communications Security. pages 2041-200100 2055, 2019.
[56] Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartlett. Byzantine-robuu distributed learning: Towards optimal statistical rates. In International Conference Machine Learning. pages 5650-5659. PMLR, 2018.
[57] Kaiyuan Zhang, Guanhong Tao, Qiuling Xu, Siyuan Cheng, Shengwei An, Yingqi Liu, Shiwei Feng, Guangyu Shen, Pin-Yu Chen, Shiqing Ma, al. Flip: A provable defense framework for backdoor mitigation in federated learning. arXiv preprint arXiv:2210. 2022.
(58) 7aixi Zhang, Xiaoyu Cao, Jinyuan Jia, and Neil Zhenqiang Gong. FLDetector: Defending federated learning against model poisoning attacks via detecting malicious clients. In 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 2545-2555, 2022.
[59] Zhengming Zhang, Ashwinee Panda, Linyue Song, Yaoqing Yang, Michael Mahoney, Prateck Mittal, Ramchandran Kannan, and Joseph Gonzalez. Neurotoxin: Durable backdoors in federated learning. In International Conference on Machine Learning, pages 14429226466. PMLR, 2022.
14

---

A Interpretation of the Minimax Objective
We note that the ultimate goal of the defender is to obtain a clean model while the attacker wants the global model to be poisoned. In other words, the server (or attacker) wishes the attack success rate of the global model to be small (large). It is very challenging achieve this objective directly because 1) the server does not know the exact trigger and target class used by the attacker, and 2) the attacker needs to adapt its attack strategy based on the server's s strategy. To address the challenge, we consider an alternative goal (i.e., our objective in Equation [ where we wish to assign small weights compromised clients when performing weighted average to update the global model. Our idea is that when the weights for compromised clients are very small, our global model is less likely to be affected by the attack. As a result, the attacker's strategy to maximize the genuine scores for compromised clients while ensuring their local models are backdoored to maximize the attack effectiveness for the global model. Thus, our objective in Equation [S] could translate the ultimate goal. Our empirical results show the effectiveness of our defense.
B Complete Proofs
B.1 Proof of Lemma 5.3
We first present some preliminary lemmas that will be invoked for proving Lemma 5.3
Lemma B.1. Suppose DD is the clean local training dataset of the client An attacker can inject the backdoor trigger r fraction of training examples in D; and relabel them as the target class.
We use D' to denote the set of backdoored training examples where r
[D']
Given two arbitrary
D.ll
and O₂ we let 9i = [DLDD] Vo ENED,UDD l(z; θ) and h4 = [.. Ve. EEED, f(z; θe). We then have that
1
(0 - 0.) h.) 2 (05p-r(MM M) ||0 -
(12)
|19. hell2 S L|I Oel1 + 2r
(13)
Proof. We first prove Equation 12
We have the following relations:
(0 - 0.)" (gi - hii
=(9 (
1
Σ
Vel(z';))
1
Vo, (z, 0.))
>> definition of gi and ha
DD, D Z'ED.UD
D
D
(14)
=(9 - -
Σ Vol(z';0) - [D:
1
Σ (ol((z;Oo)) Drf
[
(15)
(1 [D)
D
z'ED.UD!
ZED
(0-O,)"
Σ V (1+ Vo,(zz;
(16)
[Di + rd)
D'EDUUD
zED:
(0 - -0-0.)
Vol(z':0) Σ Ve, (2:
ID. + rt)
F'ED;
ZED.
Σ Vol(z';0) - Ç
Ve,
(17)
z'EDG
D
Σ (0 - (Vol(z;)) - Ve.l(z;..)
(1 + +r!)
ZED
+ (0 -
T (
Vol(z';0) - Σ
Vo. (z,
(18)
z'EDY
DED:
2 DD (1++)) xED,
( 0.)² (VVo((VV) Ve,
- -I( (()= Vol(z'; - r Σ
Vo. (z. 2
(19)
x EDD
xDD;
15

---

2 [D + +r()
5 - 0.) -o
zED,
||0 0ell2
Σ Vel(z':0) - Σ Vo.
Cauchy-Schward inequality
x'ED;
xED;
2 [D:(11 [1
( 0.0 (Ve((2)) Ve. (e.
ZED
- ||0 0.112
\V 0)1 t Σ
IV (2; (2)22) D triangle inequality
D'EDi
RED.
[D: + 74) (1 | 0ell2 2r 1
Assumption 5.1 and 5.2
(20)
1
1+ ri 10 10-0.11
0.l1
2r 2 ||0 0ell2)
(21)
1+r,
20.5p ||0 - 2al1 2r 100 Oel12 e
(22)
20.pp |0 - 0.11 r.M ||0 0.11 M(M)
(23)
-0..5p - -r.M) ||0 0e112 -
(24)
where Equation 23 holds based on the fact that 2r ||0 Oell 2 - 1|0 Oel1 - -r.M for
Vr! 2 0 and VMT 2 O.
In the following, we prove inequality 13 We have that
19: - hell2
V)l(z';0)- (1+ r()
Σ O.)
definition of gi and h;
D + +r+)
x'DDUDD
(25)
Σ Vol(z';0) +
Σ - Σ
(e; 02;
(26)
[Dil(1+ + r!)
xED
z'ED;
zED:
Vol(z';0) -
Ve, (z; 0,)112
[Di((1 +r+)
XED;
+ [D. (1)) xED;
Vol(z';)) Σ
Ve. (z: Aolll
>> triangle inequality
(27)
xED;
< 1+ (2r + L|I0 02l12)
(28)
< M + - Oellz  r E [0.1]
(29)
where Equation 28 is due to Assumption 5.1 and 5.2
Given Lemma
B.1
we prove Lemma 5.3 as follows. Recall that we have of
and
of 3 Eies
10'+1 0c+1112
(30)
-1 7 Σ aigh -00' 1) Σ 8/hi)l2
gradient descent for O--1 and 0!+1
(31)
iES
- 7 Σ 0gg
(0' 17 Σ (af 3 afhhi)l2
(32)
iES
-1 O: ailt
h1) (n Σ (3) aflill12
rearranging Equation 32
(33)
16

---

<|00 - 6: -
Σ SES
12ll2
1In
[0} - a2)//l22
triangle incquality
(34)
iES
Next, we respectively derive an upper bound for the first and second terms in Equation 34 To derive the upper bound for the first term, we have that
|0' 0 - 11 Σ
ajlo 11112
iES
= =| 0/112 - 2n 0:) Σ
alsl - -()) + + Σ
ai - k1)1
(35)
iES
iES
=S1 + S2 + Ss
(36)
where S = ||0| - 0'112. S₂ 2n +E''
af - kt)), and Sa
n² [Eiss ag nt)l2 2
Next, we will bound Sn and S3. We denote 7th -EEs. a Note
that we have 7¹ Eiesof afr; M since rf = 0 for vi E S \ Sa. We bound Sg as follows.
S₂
-n2 - 6.'
C atigt - -1))
(37)
168
2n
Σ at(('' (gt h?)
(38)
iES
< - 2n) Σ (00(0p - r/M) ||0$ - 0%,l2 - M)
(39)
iES
20)((0 Σ atr(M) ||0 0dll Σ M
(40)
iES
VES.
-(-n + "m | - - + 2 Ddefinition of yd
(41)
where incquality 39 holds by Lemma B.I and the fact that 77, af 2 0. We bound Sg as follows.
S₂ -n/²
ao - -h911
(42)
ES
at 11 22ll2)²
(43)
iS
(/ -100- >> Lemma B.1
(44)
iES
1/ (2n + 0|(0 110-00110 0ell2)²
(45)
= 21 ||0 0.1 + + ||0 O.l2 4h'1)
(46)
(T. ||0 0.1 +, 0.1 2T, 46193)
(47)
= ((L2 + 2 1|0 - 0.12 + + + +4693)
(48)
where Equation 47 is based on the fact that 4 - Ocl2 s 27 1| Oel1 + 2 L when
2L O.
Given the upper bounds of S₂ and Sz. we can bound ||0r -% - Eies at - kt)l follows.
|00 0¹ -) Σ af
(49)
YES
=S + S2 + Sa
(50)
< ||0 - Oell2 + (ーn + 2mm"" ||0 -6'll² 2m7
17

---

+ (112L² 2 | -6: 22 + 4
(51)
=(1 -(1-9u --- 2077" + 11 L² + 2n Ln - - + 2n7' + 21j² Ln + 4n bT]
(52)
Next, will derive upper bound for || Eiss - a l1 We denote p² Eies. rf. Note that we have that y² Diestt ot also holds since rf = for vi S \ Sa. Given the assumption that
(1-r")a S 3 (1 + Jaj we have
I| > a S
|5 ajl | S 2nr'M,
(53)
iES
where the first inequality is due to triangle inequality and the second inequality is based on the assumption that ||b||]2 S M. Therefore, we have:
|[O(t+1]
- 1|2
0 0 1 Σ ao 111l + || E0: at)ail2
Equation 30, 34
(54)
iES
S (1 mp 2nyy" + 1/21. Lx) ||er
0%11 1 21 nT. 217*)
(55)
+ 2gj' M D> Equation 49
52
53
(56)
SVI 7p + 2 + 7² L 21y² Ly
||0' - - + 21 + 2m + 2n M, (57)
where the last inequality holds due to the fact that va+bs S Va+ 1o-+vbre completes our proof for Lemma 5.3
for for Va 2 0 and vb 2 0, which
B.2 Proof of Theorem 5.4
We denote A = / nn nu 2npx + +, 2n 2n
A = / nu 2nyy + 172 2 + 2n
B. v 22/ + nL + 2m + 2nr M, and B = / 217 (1 + n/ + 2n7) + 2nr Since 7 S:
and r¹ < r, we have A, < A and B, < B. Thus, based on Lemma we have:
||0 e' - A|| - - +
(58)
Then, we can iteratively apply the above equation to prove our theorem. In particular, we have:
|0 -0'10:11
_a|10'-1-01 0 1 +B
(59)
SA(A | - 0t + B) +
(60)
=A² | - 0 + (A' + BB)B
(61)
<A' | - - + (A'-1 + 1 ... B
(62)
1- B
= 0 0 + 1 A
(63)
= -(V1 1 7/ 277 + + 12 2 + 21)2 ||00 -
1 (v 1 7/ 207y + 12 -212(21) Ly);
+
(1/2 + 2m) + 2n),
(64)
v1 - np 2177 + 12 2012
When the learning rate satisfies <
_ 224 we have that 1 L2
n122
( M as -> cc. Hence, we prove our 1- mut 2 1
Therefore, the upper bound becomes
Theorem
C Complete Algorithms
C.1 Complete Algorithm of FedGame
Algorithm shows the complete algorithm of FedGame. In Line 3 we construct an auxiliary global model. In Line 4 the function REVERSEENGINEER is used to reverse engineer the backdoor trigger
18

---

and target class. In Line 6, we compute the local model of client based on its local model update. In 7ine we compute a genuine score for client i. In Line 9 we update the global model based on genuine scores and local model updates of clients.
Algorithm FEDGAME
Input: (global model in the tth communication round), g (local model updates of clients), D. (clean training dataset of server), (learning rate of global model).
Output:0 (global model for the (t + 1)th communication round)
0 = @ + [s] Eies of
Ore: Ure REVERSEENGINEER(O)
for i S do
: O g
p D, ExED, I(G(x @ Bre: 01) vtt))
end for @
O' Eieo Piot
return 9t+
C.2 Complete Algorithm for a Compromised Client
Algorithm [ shows the complete algorithm for a compromised client. Line 3 we randomly subsample os fraction of training data from D.. In Line the function CBEATTBBACKDRREDDXTT is used to generate backdoored training examples by embedding the backdoor trigger to [min(jj 1))D Dr training examples in D; De and relabel them y where | measures the is used to train the local model the training dataset D D. Dr In Line 9 estimate a genuine score. In to generate backdoored training examples by embedding the backdoor trigger 8 to |min( * Ç. 1)] training examples in Dj and relabel them as gt In Line 16 we use the function TRAININGLOCAII MOLDEE to train a local model and utilize existing state-of-the-an attacks inject the backdoor based on the training dataset DJ U D..
number of elements in set. In Line 8 the function TRAININGLOCAAMMON
Line 15 we use the function CREATEBACKKOOREDE
Algorithm 2 ALGORITHM FOR COMPROMISED CLIENT
1: Input: O' (global model in the tth communication round), D; (local training dataset of client i), P; (fraction of reserved data to find optimal rf), Ç (granularity of searching for r(), 5 (backdoor trigger), y² (target class), and (hyperparameter)
2: Output: of (local model update)
3: Dree RANDOMSAMPLING (D,,
4: count = 1
5: max mar_value, + 0,0
6: for <- 0 to count do
7: D' CREATEB BRRAATBBBCKDDORREDDAAAA... Drev 8,y² "iy"smin(j 1))
8: θ,, = TRAINING @* D UD; \ Dree)
9:
Pú = -- TD EXED I(G(x @ 8; O.)) (y)= = )t)
10:
if Ply + Amin( * (,1)) max max_value then
11:
0 0=
12:
maa__vaue Píj Amin(j (,
13: end if
14: end for
15: D' -CRATTEBACKDDOOEEDDAAA....
minno (, 1))
O -TRANINGGLOCALMODDLLI.. D.)
17: return 0f -
19

---

D Additional Experimental Setup and Results
D.1 Architecture of Global Model
Table 2
shows the global model architecture on MNIST dataset.
D.2 Parameter Sefting for Compared Baselines
Recall that we compare our defense with the following methods: FedAvg (28). Krum 66 Median [56]. Norm-Clipp Clipping [9). Differential Privacy (DP) [39, DeepSight [36], and FLTrust 7 FedAvg is non-robust while Krum and Median are two Byzantine-rooust baselines. Norm-Clipping clips the 12-norm of local model updates to given threshold Tv- We set TN 0.01 for MNIST and TN = 0.1 for CIFARIO. DP first clips the nn-morm of local model update to a threshold TD and then adds Gaussian noise. We set TD 0.05 for MNIST and TD 0.5 for CIFARIO. We set the standard deviation of noise to be 0.01 for both datasets. In FLTrust, the server uses its clean dataset to compute server model update and assigns trust score to each client by leveraging the similarity between the server model update and local model update. We set the clean training dataset the server to be the same as FedGame in our comparison. Note that FLTrust is not applicable when the clean training dataset of the server from a different domain from those of clients.
Table 2: Architecture of the convolutional neural network for MNIST.
Type
Parameters
Convolution
3 3, stride=1, 16 kernels
Activation
ReLU
Max Pooling
2 2
Convolution
4 4, stride=2, 32 kernels
Activation
ReLU
Max Pooling
2 2
Fully Connected
500
Activation
ReLU
Fully Connected
500 x 10
D.3 Performance of FedGame against Neurotoxin
In Table 3 we compare our FedGame with other defense baselines against Neurotoxin [59]. We can observe that our FedGame is consistently more effective than existing defenses. Our observation is consistent with the experimental results for Scaling attack and DBA attack in Table [
Table 3: Comparison of FedGame with existing defenses against Neurotoxin on MNIST under IID setting. The total number of clients is 10 with 60% compromised. The best results when respectively comparing FedGame in each setting with existing defenses are bold.
Defenses (Under attacks)
FedAvg (No attacks) FedAvg Krum Median
FedGame
Metrics
Norm- Clipping
Deep- FLTrust Sight
DP
In- Out-of- domain domain
TA (%)
99.04
99.02
99.32
99.08
90.75
95.28 96.36 95.73
97.27
97.33
ASR (%)
9.69
99.97
99.98
99.99
99.36
99.27
89.02
13.02
9.93
10.03
D.4
Visualization Genuine Score of FedGame and Trust Score of FLTrust
Our FedGame computes genuine score for each client which quantifies the extent to which a client benign in each communication round. Intuitively, our FedGame would effective if the genuine score is small for compromised client but is large for benign one. FLTrust 7 computes a trust score for each client in each communication round. Similarly, FLTrustt would effective the trust score is small for compromised client but large for benign one. Figure 2 visualizes the
20

---

average genuine or trust scores for compromised and benign clients of FedGame and FLTrust on the MNIST dataset. We have the following observations from the figures. First, the average genuine score computed by FedGame drops to O quickly for compromised clients. In contrast, the average trust score computed by FL.Trust drops slowly. Second, the average genuine score computed by FedGame for benign clients first increases and then becomes stable. In contrast, the average genuine score computed by FLTrust for benign clients decreases as the number of iterations increases. As a result, FedGame outperforms FLTrust.
1.0
Deciga (tiets
1.0
Eecigs (LinEt)
1.0
Eecogt Claets
1.0
Decpp Cluece
Diegras Clonis
Diprrscten Clinsa
Dogroszed Stonks
Deprosted Elombe
0.66
3..4-
0.4
0.4
0.4
0.2
0.2
0.2
0.2
50
100
150
50
100
150
200
50
100
150
60
100
150
200
Reaada
Recada
Reands
Rocads
(a) FLTrust (IID)
(b) FLTrustt (non-IID)
(c) FedGame (IID)
(d) FedGame (non-IID)
Figure 2: (a)(b): Server-computed average trust scores for benign and compromised elients of FLTrust on MNIST under Scaling attack. (c)d); Average genuine scores computed by the server for benign and compromised clients of FedGame on MNIST under Sealing attack. The clean sets of the server are the same for FL.rrust and FedGame.
D.5 FedGame Performance in FL Consisting of 30 Clients
In Table 4 we report the performance of FedGame and baselines when the total number of clients is 30. The results also indicate that our FedGame outperforms all baselines in terms of ASR and achieves comparable TA with existing methods.
Table 4: Comparison of FedGame with existing defenses under Scaling attack. The total number of clients is 30 with 60% compromised. The best results when respectively comparing FedGame in each setting with existing defenses are bold.
Defenses (Under attacks)
FedAvg
FedGame
Datascts
Metries
Norm- Clipping
(No attacks) FedAvg Krum Median
DP
FLTrust
Out-of- domain domain
In-
TA (%)
99.02
99.09
98.16
99.01
92.77
89.77
95.27
97.81
97.64
MNIST
ASR (%)
9.74
99.98
99.98
99.98
98.20
98.83
11.04
9.95
9.95
TA (%)
80.08
79.73
72.23
79.58
79.20
50.86
67.84
73.29
74.42
CIFARIO
ASR (%)
9.14
99.82
99.97
99.85
99.87
96.53
99.28
10.44
9.15
D.6
Additional Ablation Studies
Impact of Trigger Reverse Engineering. Our framework is compatible with any trigger reverse engineer methods. To study the impact of different trigger reverse engineering methods, we use FeatureRE 47 to substitute Neural Cleanse in FedGame. We adopt the public implementation of FeatureRE. Under the default setting, FedGame achieves 10.36% ASR, which indicates that our framework is consistently effective with different trigger reverse engineering methods.
Besides, FedGame would still be effective even if the reverse-engineered backdoor trigger and target label are of low quality, long they can distinguish benign and compromised clients. We validate this by experiment. In particular, we use 20 iterations (originally, it's 100) when reverse engineering the trigger/target label under the default setting obtain low-quality trigger/target label. We find that genuine scores for malicious clients are still low. The final ASR is 13.23%, which means our FedGame is still effective.
Impact of the Total Number Clients. We study the impact of the total number of clients for our FedGame under the default setting. In particular, we consider the total number of clients to be 10, 30.
21

---

50, 70, and 100, where the fraction of malicious clients is 60%. We show the experimental results in T Our experimental results show that our FedGame is effective for different number of clients on different datasets.
Table 5: ASRs of FedGame under different total number of clients on MNIST and CIFARIO. The fraction of compromised clients is 60%.
Total Number of Clients
Dataset
10
30
50
70
100
MNIST
9.72
9.95
10.03
10.01
9.89
CIFARIO
8.92
10.44
10.62
9.79
10.82
Impact of the Size of Server Clean Data. By default, we the ratio between the number of clean examples of the server and the total number of examples of clients to be 0.1. We conduct experiments with different ratios: 0.01, 0.02, and 0.05 under the default setting. The corresponding ASRs are 9.71%, 12.38%, and 9.75%, indicating that FedGame is effective even when the server only has 1% clean data.
Trigger Optimization. We consider an attacker optimizes trigger pattern such that a backdoored input is more likely to be predicted as the target class. We perform experiments under the default setting. The ASR is 12.43%, which indicates that our FedGame is consistently effective for trigger optimization.
22


Reviews:
[{"review_id": "B0ptyULuT3", "reviewer": "Reviewer_89HC", "summary": "The authors introduce a game-theoretical defense mechanism named \"FedGame\" designed to safeguard against backdoor attacks in the Federated Learning (FL) environment. They demonstrate through theoretical analysis that training the global FL model using FedGame under backdoor attacks yields results closely resembling those obtained without any attacks. The researchers conduct extensive evaluations using benchmark datasets and compare FedGame's performance with various state-of-the-art baselines. The experimental findings indicate that FedGame successfully thwarts strategic attackers and significantly outperforms the baseline approaches, displaying remarkable robustness against adversarial threats.", "questions": "1. Instead of utilizing reverse engineering, why not considering other approaches closer to game concept like modeling a Bayesian game, and update defender's prior belief about attacker during FL process?\n2. Does the \"dynamic backdoor attack\" mean the attacker can change backdoor trigger and targeted label during FL process? If that is the case, the attacker should consider a long-term goal instead of a one-shot myopic objective. Otherwise, it could mitigate its own attack effects even there is no defense exists.\n3. It is unclear to me in both section 4.3 and Appendix how the attacker uses stochastic gradient descent to optimize the trigger $\\delta$. In the conducted DBA experiments, the trigger(s) take the form of fixed-sized square(s) located at specific position(s) and may involve certain numbers of squares. These characteristics represent potential parameters that can be incorporated into the optimization problem. However, it is worth noting that for achieving the most versatile trigger, it is worthwhile to consider every pixel in the image. In recent works [1] [2], researchers have explored generated backdoor triggers that encompass the entire range of the image.\n4. I wonder what if the reverse engineering cannot get the correct trigger and/or targeted label? There should be either theoretical analysis or ablation experiments to further exam the influence.\n\n\n[1] Salem, Ahmed, et al. \"Dynamic backdoor attacks against machine learning models.\" 2022 IEEE 7th European Symposium on Security and Privacy (EuroS&P). IEEE, 2022.\n[2] Doan, Khoa D., Yingjie Lao, and Ping Li. \"Marksman backdoor: Backdoor attacks with arbitrary target class.\" Advances in Neural Information Processing Systems 35 (2022): 38260-38273.", "limitations": "1. The post-training stage defenses play a vital role in countering backdoor attacks. Even within the context of FL, certain techniques such as Neuron Clipping [3] and Pruning [4] have demonstrated their effectiveness in detecting and mitigating the impact of backdoor attacks. Consequently, I am curious to know how the proposed FedGame performs compare to these post-training stage defenses. Noted that, some of them do not require to know backdoor trigger or target label.\n2. I wonder the efficiency of the FedGame algorithm. It seems for each FL epoch, it needs process reverse engineering method (costly according to original papers) and calculate a equilibrium (also costly in most of settings like genera sum Nash aquarium). Is there any assumption or simplification I missed here?\n\n[3] Wang, Hang, et al. \"Universal post-training backdoor detection.\" arXiv preprint arXiv:2205.06900 (2022).\n[4] Wu, Chen, et al. \"Mitigating backdoor attacks in federated learning.\" arXiv preprint arXiv:2011.01767 (2020).", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1. It is interesting to incorporate game theory to federated learning.\n2. The authors show that using FedGame to train the global FL model under backdoor attacks yields similar results to those without attacks.\n3. The authors extensively evaluate FedGame on benchmark datasets, showcasing its effectiveness in defending against strategic attackers and outperforming baselines with significantly higher robustness.", "weaknesses": "From game perspective, \n1. Ideally, we expected to see a game model incorporating FL's online nature (e.g., Markov Game). It is unclear to me why it is a multi-stage strategic game (sequential decision problem) since each FL round's optimization problem is solved independently.\n2. The term minmax game is ambiguous. It should be making clear which solution concept (Stackelberg or Nash equilibrium, Zero-sum or General-sum utility) is considered. Otherwise, it is hard to claim the existence of the solution and convergence of the algorithm. \n3. The game's information design is unclear (game with complete or incomplete information). It should be modeled clearly (probably mathematically?) which player have what information that is known/unknown by some other player. Informational concerns play a central role in players’ decision making in such strategic environments.\n\nFrom security perspective, \n1. Why the reverse engineering methods can be directly applied to FL setting considering they normally require large amount of clean data without bias (FL clients may hold heterogeneous data)? Will the aggregation influence the reversed pattern since the aggregated model is updated by a combination of clean and poisoned data? \n2. The action spaces for both attacker and defender are not general enough. From the attack side, poison ratio is not the only parameter the attacker can manipulate (e.g., scaling factor, batch size, number of local training epoch, etc.). In general, attacker can control the model updates send to the server. From the defense side, the authors only consider the client-wise aggregation-based training stage defense. There are other defense (e.g., coordinate-wise, post training stage defenses) could be considered to extent the action space.\n3. In FL, sever is not only unaware of the attacker, but also lack of environment information, e.g., number of total clients, non-iid level, subsampling, etc.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable suggestions.\n\n**C1: Why the game is multi-stage.**\n\nWe are sorry for the confusion. In the abstract, we meant to say a multi-stage interaction between the attacker and defender over different FL rounds instead of a multi-stage game.\n\n**C2: Minmax term not clear.**\n\nWe are sorry for the confusion. Our game is a zero-sum Stackelberg game. We will add the discussion of the existence of the Stackelberg equilibrium following existing literature.\n\n**C3: Game’s information.**\n\nThe defender knows local models but does not have 1) information on compromised clients, 2) poisoning rate $r_i^t$, trigger $\\delta$, and target class $y^{tc}$ of the attacker. The attacker knows the global model $\\Theta^t$ in each FL round and the trigger reverse engineer method (to consider a strong attacker). We will add more details.\n\n**C4: How does reverse engineering in FL work?**\n\nWe would like to kindly mention that we don't heavily rely on the resources of clean data. FedGame does not require reverse-engineering the exact trigger as long as the reverse-engineered trigger can be used to distinguish benign and compromised clients. Thus, compared with [38, 42], we have a lower requirement for the reconstructed trigger. In our experiments, we only use a moderate number of clean samples (10% the size of training data in the default setting) to reverse engineer. The aggregation step will not affect the effectiveness of reverse engineering, since these FL attacks are designed to poison the global model with only a few local models poisoned.\n\n**C5: Action space.**\n\nWe really appreciate the suggestion. We hope to provide a general framework. We conduct thorough experiments considering the poisoning ratio as the action space of players since it is critical in controlling the effectiveness and cost of attackers. Moreover, we also consider optimizing other variables, such as the trigger pattern. We agree that it is an interesting future work to extend the action space. We will discuss.\n\n**C6: Environment information.**\n\nWe agree. Note that we don’t assume the server is aware of the environment information to ensure the generalizability of FedGame. For instance, without an attacker, FedGame would automatically assign similar genuine scores for clients, reducing FedGame to FedAvg, which often gives the best utility. With an attacker, FedGame still does not need to know the number of total clients, non-iid level, or subsampling, e.g., our results show FedGame is effective with 1) different total number of clients, and 2) a subset of clients was selected in each FL round. We will make this clear.\n\n**C7: Other game formulations.**\n\nHere we aim to propose the first game-theory-based framework. We believe it is an interesting future direction to consider other game formulations, e.g., Bayesian games. We will add a discussion.\n\n**C8: Dynamic backdoor attacks.**\n\nYes. We consider and allow a dynamic attacker who could change the backdoor trigger and targeted label during the FL process. Currently, we only consider the possibly worse-case attacker in each round by optimizing their attack objective. We agree that an attacker could consider a long-term goal, leading to more sophisticated attacks. We leave the attack development (developing such an attack is still an open challenge) and the examination of FedGame under the attack as future work. We will add related discussion and future work.\n\n**C9: Trigger optimization.**\n\nWe are sincerely sorry for the confusion. We optimize the trigger according to different attacks. For instance, we follow the setting of DBA, and optimize the position for each local trigger and preserve its pattern. For scaling attack, we optimize every pixel of the trigger. Concretely, we randomly sample a batch of samples from $\\mathcal{D}_i$, then compute the gradient of the loss function in Line 219 with respect to $\\delta^*$, and finally update $\\delta^*$ based on the gradient. Note that we clip the gradient such that each entry of $\\delta^*$ is a valid pixel value. We will add detailed illustrations.\n\nAs suggested, we added an experiment for triggers in [1]. FedGame reduces ASR from 99.43% to 10.83% under our default setting, meaning FedGame is effective for diverse triggers. We will add results and discussion.\n\n[1] \"Dynamic backdoor attacks against machine learning models.\"\n\n**C10: Reverse-engineered trigger/targeted label could be incorrect.**\n\nFedGame would still be effective if reconstructed triggers were incorrect, as long as they can distinguish benign and compromised clients. We added an experiment to validate this. We use 20 iterations (originally, it’s 100) when reverse engineering the trigger under the default setting to obtain low-quality and incorrect triggers (the trigger is not visually similar to the original one in this case). We find that genuine scores for malicious clients are still low. The final ASR is 13.23% which is slightly higher than the original ASR. We will add a discussion.\n\n**C11: Post-training defenses.**\n\nFedGame could be combined with those defenses to form a defense-in-depth. To maintain utility, in general, [3] needs some clean samples that have the same distribution as the training dataset, while FedGame is effective even if samples of server have different distributions from FL task. [4] prunes filters based on pruning sequences collected from clients. Thus, [4] could be less effective under a large fraction of compromised clients, while FedGame is effective under 80% of compromised clients. We will add the discussion on [3, 4] and comparison.\n\n**C12: Efficiency.**\n\nWe agree that FedGame incurs extra computation costs for the server. We would like to kindly note that in practice, the server (e.g., deployed by Google) is usually powerful. Given the triggers, it is very efficient to compute genuine scores for clients, as shown in Appendix D.6. Moreover, we could compute them in parallel. We will add these discussions in our revision."}, {"review_id": "m8DpG2Gzqy", "reviewer": "Reviewer_Mtx6", "summary": "Federated learning (FL) enables a distributed training paradigm, where multiple clients can jointly train a global model without needing to share their local data. However, recent studies have shown that federated learning provides an additional surface for backdoor attacks. For instance, an attacker can compromise a subset of clients and thus corrupt the global model to mispredict an input with a backdoor trigger as the adversarial target. Existing defenses for federated learning against backdoor attacks usually detect and exclude the corrupted information from the compromised clients based on a static attacker model. Such defenses, however, are not adequate against dynamic attackers who strategically adapt their attack strategies. To bridge this gap in defense, we model single or multi-stage strategic interactions between the defender in FL and dynamic attackers as a minimax game. Based on the analysis of our model, we design an interactive defense mechanism FedGame. We also prove that under mild assumptions, the global FL model trained with FedGame under backdoor attacks is close to that trained without attacks. Empirically, we perform extensive evaluations on benchmark datasets and compare FedGame with multiple state-of-the-art baselines. Our experimental results show that FedGame can effectively defend against strategic attackers and achieves significantly higher robustness than baselines. For instance, FedGame reduces attack success rate by 82% on CIFAR10 compared with six state-of-the-art defense baselines under Scaling attack.", "questions": "1.Have you cited the latest and relevant research results？\n2.Insufficient experimental content.\n3.The experimental datasets are all small datasets, and model testing needs to be carried out on the Big data set.\n4.Icons are not clear enough\n", "limitations": "The author's paper has good innovation and rigorous writing logic, but the experiment is not sufficient and needs to be further expanded to obtain more universal conclusions.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The article is well written, has a smooth grammar, and a clear purpose. It better summarizes and clarifies the concepts and definitions of backdoor attack and Federated learning. It is novel and innovative to express FedGame as a minimax game between defenders and attackers.The mathematical derivation is relatively detailed.", "weaknesses": "There may be biases in the selection and collection of data samples, which affect the accuracy and reliability of the results. In terms of research methods, there is a lack of sufficient description of the control group and experimental group, making it difficult to determine causal relationships. The literature review section lacks comprehensive and in-depth academic research, resulting in a lack of clarity in the research background of the article. The discussion on the results and discussion section is not clear and powerful enough, and requires more detailed explanation and support. The improper use of statistical analysis methods or hypothesis testing has affected the credibility of the results. There are some loose and incoherent issues in the structure and organization of the paper, which require better logic and framework. The summary in the conclusion section may be too brief to fully summarize the significance and contributions of the research.The writing of the paper could be improved for better description and clarification.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive comments.\n\n**C1: Have you cited the latest and relevant research results?**\n\nThanks for the question. To the best of our knowledge, we have cited those research results. We will do a comprehensive literature survey to add and discuss more recent research results (e.g., those published after the NeurIPS’23 deadline). Thanks for the kind reminder!\n\n**C2: Insufficient experimental content.**\n\nFollowing the suggestions, we will add more discussion and explanation in our experimental results sections. We will also polish the structure and organization of the paper. Moreover, we will expand the conclusion section and polish the writing of the paper to make it clear in the description.\n\n**C3: The experimental datasets are all small datasets.**\n\nIn Appendix D.6, we conduct experiments on the Tiny-ImageNet dataset. Our experimental results show our defense is still effective on the large dataset. We will make it more clear in our revision.\n\n**C4: Icons are not clear enough.**\n\nThanks for the suggestions. We will polish the figures in the paper to make them clear.\n"}, {"review_id": "ATJWgC69Ao", "reviewer": "Reviewer_8T34", "summary": "Existing defenses consider a static attack model where an attacker sticks to a fixed strategy and does not adapt its attack strategies, causing they are less effective under adaptive attacks. Hence, the authors propose FedGame to bridge this gap. The main idea of FedGame is to model single or multi-stage strategic interactions between the defender in FL and dynamic attackers as a min-max game. It mainly consists of three steps: 1) building an auxiliary global model. 2) exploiting it to reverse engineer a backdoor trigger and target class. 3) testing whether the local model will predict an input embedded with the reverse engineered trigger as the target class to compute a genuine score.", "questions": "1. The paper points out that existing defenses become less effective against dynamic attackers who strategically adapt their attack strategies. However, the definition of dynamic attacks is unclear. Further, the dynamic attack simulated by this paper seems to be only the change of the poisoning rate $r_i^t$. Does this mean that the proposed method in this paper has certain limitations? Because there are many possible factors that may affect the attack performance, such as the selection of poisoned neurons [1], the design of the loss function [2], etc.  \n2. In practical, the defender cannot manipulate the attacker's malicious behavior. Hence, it seems the defense method proposed in this paper just need to achieve the goal of $\\min (\\sum_{i \\in S_a} p_i + \\sum_{j \\in S-S_a} p_j)$. If so, the FedGame is more likely a combination of NC method with limited impact from the min-max game. If not, does it mean that FedGame needs benign clients to act as attackers to achieve better defense effects? Will FedGame be invalid if the target of the real attackers and the fake attackers are different?\n3. In section 4.3, when searching for an optimal $r_i^t$, the goal of attackers is $\\max (p_i^t+\\lambda r_i^t)$. However, increasing $p_i^t$ and increasing $r_i^t$ are contradictory because large $p_i^t$ means small ASR, while large $r_i^t$ means high ASR. It seems that the attack constructed in this paper is not competitive enough, which raises some doubts about the necessity of the attack stage.\n\n\n[1]. PerDoor: Persistent Non-Uniform Backdoors in Federated Learning using Adversarial Perturbations.\n[2]. Chameleon: Adapting to Peer Images for Planting Durable Backdoors in Federated Learning.\n", "limitations": "see the questions.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The idea of modeling strategic interactions between the defender and attackers as a min-max game is novel and less studied in previous works. The proposed FedGame seems to be competitive with related methods.\n2. The paper is well-organized in general, well-written and mostly easy to follow.\n3. This paper addresses a pertinent problem in Federated learning. The extensive experiments show that FedGame method works even if more than half of the clients are malicious.\n", "weaknesses": "1. The authors use the genuine score $p_i^t$ to quantify the extent to which a client is benign, however, the results of $p_i^t$ highly depends on the quality of reversed-trigger generated by NC or other tools, implying the limitations of the FedGame are the same as NC, e.g., maybe invalid in large-size trigger reverse (such as Blend, Reflection, …) and all-to-all attacks, etc.\n2. FedGame seems to have high time complexity. In the server side, the defender needs to run NC process to generate reverse-trigger (When there are many categories, the time consumption of NC is enormous). In the client side, the attacker needs to find an optimal $r_i^t$ using grid search (Every search for $r_i^t$ requires retraining the local model).\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive comments.\n\n**C1: Large-size trigger.**\n\nWe note that our framework is very general and is compatible with any trigger reverse engineering methods such as NC and FeatureRE. For instance, FeatureRE [42] (published in NeurIPS’22) shows that it is effective for large-size triggers (even for triggers that occupy the entire image), which addresses the limitations of NC. We will make it more clear and add related discussion in our revision.\n\n**C2: Time complexity.**\n\nWe agree with the reviewer that our defense incurs extra computation costs for the server. However, we note that the server (e.g., servers in the FL applications deployed by Google and Apple) is usually very powerful in practice. Moreover, the reverse engineered triggers could be used for all clients at once. As we propose a defense framework, we consider a strong attacker, where a compromised client could use grid search to find an optimal $r_i^t$ to maximize the attack's effectiveness. The attack would be less effective if the compromised client cannot optimize $r_i^t$. We will add the related discussion.\n\n**C3: The definition of dynamic attacks is unclear.**\n\nSorry for the confusion. In our dynamic attack, we consider an attacker could optimize both the poisoning rate and trigger pattern. In Appendix D.6, our experimental results show our defense is still effective when an attacker can optimize the entire trigger pattern. We will clarify it in our revision. Moreover, we will discuss other factors such as the selection of poisoned neurons [1] and the design of the loss function [2] as suggested. In addition, following the suggestions, we have added an experiment which uses the loss function in [2]. We observe that our method can reduce the ASR from 98.63\\% to 11.32\\%, indicating the effectiveness of our method.\n\n**C4: Defense goal.**\n\nYes, the goal of the defender is to minimize (or maximize) the genuine scores for compromised (or benign) clients, i.e., $\\min (\\sum_{i \\in S_a} p_i - \\sum_{j \\in S -S_a} p_j)$. Since the benign clients do not have attack behavior, genuine scores obtained by our framework for benign clients would be high, enabling us to distinguish benign and compromised clients. Note that our major contribution is to propose a general game-theory based framework, which is compatible with any trigger reverse engineering method such as NC and FeatureRE. Our results show our framework is also effective with FeatureRE. We will add the related discussion.\n\n**C5: Optimization of $r_i^t$ and $p_i^t$.**\n\nWe note that the local model of a compromised client is more likely to predict a trigger-embedded input as the target class when the poisoning rate $r_i^t$ is larger. As a result,  the genuine score computed by the server for the local model of the compromised client would be smaller, making the attack less effective. In other words, a larger $r_i^t$ makes the attack more effective without defense but less stealthy (e.g., the genuine score is smaller under our defense framework), which makes the attack less effective under defense, and this forms the defense principle. Thus, we aim to find an optimal $r_i^t$ to achieve a tradeoff between the poisoning rate and the genuine score to maximize the attack effectiveness under our defense. We will add related discussion to make it more clear in our revision.\n"}, {"review_id": "46BIy4l4JD", "reviewer": "Reviewer_cSQx", "summary": "This paper presents FedGame, a game-theory based dynamic defense mechanism against backdoor attacks in Federated Learning (FL). FedGame adapts to attackers using a minimax game model. The authors theoretically prove that a model trained with FedGame is close to one trained without attacks, implying robustness against malicious disruptions. Empirical evaluations on benchmark datasets reveal that FedGame compares with existing six existing defenses, reducing attack success rate on MNIST and CIFAR10.", "questions": "Please refer to the weaknesses.", "limitations": "Please refer to the weaknesses.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. Backdoor defense in federated learning is an important problem.\n2. The paper provides theoretical analysis on the attack and defense as a two-player game.", "weaknesses": "1. The authors build an auxiliary global model to reverse engineer the trigger, as mentioned in Sec 4.2, to address the key challenge in solving Equation 5 is to construct an auxiliary global model. Then does the authors make any assumptions on the auxiliary global model $\\theta^{t}_{a}$ comparing to global model? If so, is there any analysis on auxiliary global model in the minimax game framework? It is unclear that how the assumption is made and it would be beneficial to understand the implications if the assumed conditions do not hold true.\n2. The determination of the 'genuine score', $p_{i}^{t}$, is another part that needs clarification. The paper does not provide theoretical estimations or robust definitions for such an important score metric for the defense, which raises questions about potential inaccuracies in the estimation and their impact on the defense framework.\n3. The evaluation methodology could be further enhanced. If the genuine score is an empirical number, it would be useful to have it studied in the evaluation section. Moreover, comparisons with state-of-the-art baselines like FLIP [52] would provide a more comprehensive analysis of the proposed solution's performance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive comments.\n\n\n**C1: Any assumption on the auxiliary global model and global model.**\n\nThanks for the insightful question. Our auxiliary global model is obtained by updating the global model in the previous FL round with the average local model updates of the current FL round. Our assumption is that the auxiliary global model obtained in this way could be backdoored if a local model from a compromised client in the current FL round is backdoored, enabling us to reverse engineer the trigger to protect the current global model. In other words, if the auxiliary global model is not backdoored, our current global model would be very similar to the auxiliary global model and thus is also not backdoored. We will add related discussion and analysis in our revision.\n\n**C2: Potential inaccuracies in the estimation of the genuine score.**\n\nWe note that our framework does not require a very accurate estimation of the genuine scores for clients, as long as the genuine scores are different for malicious clients (e.g., small genuine scores) and benign clients (e.g., large genuine scores). In Figure 2 of the Appendix, we show that the average genuine score for compromised clients is much smaller than that of benign clients, which validates the feasibility of the optimization problem. We will add related discussion in our revision. \n\n**C3: Genuine score should be studied in the evaluation section.**\n\nThanks for the suggestion. In Figure 2 of the Appendix, we show the average genuine scores for compromised clients and benign clients. We will make it more clear in our revision.\n\n**C4: Comparison with baselines like FLIP.**\n\nThanks for the suggestions. Following the suggestion, we compare our FedGame with FLIP under the default setting. We find that the FLIP can only reduce the ASR to 65.62\\%, while our approach can reduce the ASR to 9.72\\%. The reason is that their method can only tolerate a small fraction of compromised clients. In our default setting, the fraction of malicious clients is 60\\%. We will add the related discussion and results in our revision. \n"}]

Author rebuttal:
We really appreciate the reviewers for the constructive feedback and suggestions. We are glad that the reviewers find our work novel, effective, and well-organized. In summary, we have added the following additional experiments following the reviewers’ suggestions:

1. We add an experiment to validate the effectiveness of FedGame for triggers that encompass the entire range of the image.
2. We add an ablation experiment to show our FedGame is still effective when reverse engineered trigger/targeted label could be incorrect.
3. We add an experiment to validate the effectiveness of FedGame when an attacker could design a different loss function.
4. We add a comparison with FLIP (a defense baseline).



In addition, we have added the following clarifications/explanations in our revision:

1. We clarify the minmax game of our defense.
2. We clarify the information design in our game.
3. We add an explanation on the trigger reverse engineering in FL.
4. We clarify the environment setup.
5. We clarify the dynamic backdoor attack strategies.
6. We add the details of the trigger optimization.
7. We clarify and discuss the post-training defenses.
8. We discuss the efficiency of our framework.
9. We clarify the relevant research and experiment content.
10. We add an explanation of our framework for large triggers.
12. We add an explanation on the optimization of $r_i^t$ and $p_i^t$.
13. We clarify the auxiliary global model and global model.
14. We add an explanation on genuine score estimation.
15. We clarify the evaluation steps of the genuine score.


Meta-review: All reviewers agree that expressing FedGame as a minimax game between defenders and attackers is a novel idea. The authors did an excellent job addressing most reviewers' concerns during the rebuttal. After the discussion phase, all reviewers recommended acceptance. The Area Chair recommends accepting the paper. In the final version, the authors should address the reviewers' critical comments. These include the effect of the quality of the reversed trigger on the method and a more detailed discussion about the extra computational costs at the server.
Decision: Accept (poster)