Meta Stackelberg Game: Robust Federated Learning against Adaptive and Mixed Poisoning Attacks
Federated learning (FL) is susceptible to a range of security threats. Although various defense mechanisms have been proposed, they are typically non-adaptive and tailored to specific types of attacks, leaving them insufficient in the face of multiple uncertain, unknown, and adaptive attacks employing diverse strategies. This work formulates adversarial federated learning under a mixture of various attacks as a Bayesian Stackelberg Markov game, based on which we propose the meta-Stackelberg defense composed of pre-training and online adaptation. {The gist is to simulate strong attack behavior using reinforcement learning (RL-based attacks) in pre-training and then design meta-RL-based defense to combat diverse and adaptive attacks.} We develop an efficient meta-learning approach to solve the game, leading to a robust and adaptive FL defense. Theoretically, our meta-learning algorithm, meta-Stackelberg learning, provably converges to the first-order $\varepsilon$-meta-equilibrium point in $O(\varepsilon^{-2})$ gradient iterations with $O(\varepsilon^{-4})$ samples per iteration. Experiments show that our meta-Stackelberg framework performs superbly against strong model poisoning and backdoor attacks of uncertain and unknown types.
Paper
Similar papers
Peer review
Summary
The paper titled "Meta Stackelberg Game: Robust Federated Learning against Adaptive and Mixed Poisoning Attacks" proposes a new approach to enhancing the security of Federated Learning (FL) systems. The paper identifies that existing FL defenses are inadequate against adaptive and mixed attacks. To address this, they introduce a Meta Stackelberg Game (meta-SG) framework, which employs a Bayesian Stackelberg Markov game (BSMG) and a meta-learning approach. This framework aims to provide a robust and adaptive defense mechanism against various poisoning attacks, including model poisoning and backdoor attacks. The proposed method is theoretically proven to converge to an equilibrium efficiently and is empirically validated to perform well against strong adversarial attacks.
Strengths
+ Introducing the Meta Stackelberg Game (meta-SG) framework is innovative, offering a new perspective on defending against adaptive and mixed attacks in FL. + The paper provides a solid theoretical foundation, proving that the proposed algorithm converges to a first-order ε-equilibrium, proving the method's efficiency. + Extensive experiments demonstrate the effectiveness of the meta-SG framework, showing significant improvements in defense against various attack types compared to existing methods. + The meta-learning component allows the defense mechanism to adapt dynamically to different attack scenarios, enhancing its robustness in uncertain environments.
Weaknesses
- The proposed approach seems computationally intensive, requiring significant resources for pre-training and adaptation, which might limit its practicality in real-world applications. Although it proves that it can converge in Theorem 3.3, it would be beneficial to have empirical evidence, such as the method's run-time overhead. - While the framework is tested against several attack types, the scope of attacks considered might not cover all possible real-world adversarial strategies, limiting the generalizability of the results. The paper especially makes it unclear what attacks are used in pre-training, whether they are the same, and how different they are compared to the real FL environment when testing and generating results. - The proposed method's scalability to larger and more diverse FL environments remains unclear, especially given its computational demands.
Questions
Given the above points, I have some questions that need to be addressed: 1. How does the meta-SG framework scale with increasing clients and more complex models? Have you tested its performance in larger FL setups? 2. How does the framework handle adaptive attack types not seen during the pre-training phase? Are there any limits to the adaptive attacks it can defend against? 3. Have you considered applying the meta-SG framework to domains other than image classification, such as natural language processing or time-series analysis in FL?
Rating
5
Confidence
3
Soundness
3
Presentation
3
Contribution
3
Limitations
N/A
Summary
The paper presents a game theoretic model for robust federated learning. The technique is composed of pre-training and online adaptation. During pre-training, a meta-policy for the defender is solved as a Bayesian Stackelberg Markov game. The defense policy is further polished during the online adaptation stage.
Strengths
The Stackelberg game is designed to counter unknown/uncertain attacks by an adaptive adversary. Theoretical bounds for sample complexity are provided. Empirical results demonstrate the effectiveness of the proposed technique.
Weaknesses
The main weakness is the slight violation of privacy as the technique needs a portion of ground truth data from the clients. This has been disused as the limitations in the paper. Minor comments: On page 2, "including mixed attacks ," ---> extra space
Questions
What is the statistical significance of the results shown in Table 1? Without the standard error, it is unclear whether the proposed technique is indeed superior to other existing techniques. I understand there is no room in the table, at least it should be mentioned in the text.
Rating
7
Confidence
3
Soundness
3
Presentation
4
Contribution
3
Limitations
Privacy violation is mentioned as a limitation of the technique. It's unclear whether future development can remove the dependence on the client-side ground truth.
I apologize for the brevity of our initial response, which was due to time constraints. Thank you for your valuable feedback. We have carefully addressed the minor comments you provided. - Regarding the privacy concerns, please refer to our response to Reviewer a9ia's comments. - We acknowledge the importance of statistical significance and have made efforts to address this in our study. Specifically, we conducted 20 trials for the experiments shown in Figures 11 (c) and (d) to generate the error bars. However, due to limitations in computational resources, we were unable to calculate statistical significance for all of our results. We plan to address this in future work when we have access to additional resources. For the other graphs and tables, we fixed the initial model and all random seeds across experiments to ensure fair comparisons. - Additionally, we recognize that client-side defenses are crucial for enhancing privacy and security. We agree that this is an area that requires thorough design and development, and it is indeed part of our future research agenda.
Response to authors' rebuttal
Thanks for the explanations. I'll keep my score.
Summary
The authors propose a defense mechanism in federated learning that has adaptability inspired from meta learning. The authors formulates a Bayesian Stackelberg Markov game (BSMG), focusing on addressing poisoning attacks of unknown or uncertain types. The authors propose an equilbrium inspired by meta learning and then look at a local version of that. Empirical evaluations are done on MNIST and CIFAR.
Strengths
This paper seems to have interesting results.
Weaknesses
The writing is sloppy in many places and quite a few things are unexplored. Federated learning's primary motivation is privacy, so the privacy loss from a core small dataset must be analyzed. The authors do acknowledge the loss but IMO that is not enough. Behind all the motivation of federated learning, the core idea is in the equilibrium proposed - IMO, exploring this equilibrium in more detail would make the paper stronger (in fact, the problem makes sense even in simpler adversarial learning problems). Is Def 3.1 just a differential equilibrium, in the style of "Implicit Learning Dynamics in Stackelberg Games: Equilibria Characterization, Convergence Analysis, and Empirical Study" but missing second order conditions? Why are there no second order conditions? Just first order may not induce a local equilibrium, which is a meaningful equilibrium to achieve. This is where even more meaning needs to be discovered for the first meta-SE. The authors compare it to PBE in the appendix, but the notations of belief consistency and sequential rationality is what makes PBE (SE) convincing. Without any such (or similar) notion, a new equilibrium in a dynamic setting is not principled. I do not understand why the ball $B(\theta^*)$ is used with a bound of 1? What is special about 1? (same for the other ball) Proposition written informally (and no explanation) in the main paper does not make sense (e.g., Prop 3.4). There are many typos when I started to look in appendix: 1) Eq F6, $\tilde{l}$ should have two inputs 2) Line 959, the parameters of $\tilde{l}$ is lost, without this the equations with $\theta'$ on left and no $\theta'$ on right is not well-defined. 3) I do not understand how the equation in line 964 came about - first it is said that it is an inequality but what is written is an equality. Overall, typos do not inspire confidence. Also, any defense mechanism should itself be subject to attack with the adversary possessing knowledge of defense mechanism - I do not see that in experiments.
Questions
Please respond to review
Rating
4
Confidence
4
Soundness
2
Presentation
2
Contribution
2
Limitations
NA
Thanks for the reviewer's comment
We appreciate Reviewer Ui9w's insightful suggestions. We would like to clarify that sequential rationality does not apply to the meta equilibrium due to the data-driven gradient adaptation. Our proposed meta-equilibrium concept is a mixed-strategy equilibrium instead of a behavioral-strategy equilibrium if we represent the Markov game in an extensive form. The defense policy $\pi_D(a^t|s^t;\theta)$, even though takes in $s^t$ at each time step, is not a behavioral strategy because $s^t$ does not correspond to an information set in this incomplete information dynamic game. In the Bayesian framework (e.g., PBE), the information set given by the history is equivalent to a Bayesian posterior belief. A behavioral strategy must take in the information sets (or beliefs) to determine the actions. Since computing Bayesian posteriors is intractable in large FL systems, our framework discards the Bayesian approach and embarks on a data-driven method to handle interim information. The learned policy $\pi_D(a^t|s^t;\theta)$ only determines a probability measure over the action sequence $\{a^1,a^2,\ldots, a^H\}$ to be played. In summary, the proposed meta-equilibrium is not a subgame perfect equilibrium in the Markov game because one cannot define the perfection condition (sequential rationality) [Def. 8.2, 1] without defining the information set in the Bayesian framework. Our motivation is to trade sequential rationality for computational viability and efficiency. We believe that it is practical for the server to collect a small, clean training dataset, known as the root dataset, for the learning task. For instance, Google uses its employees to type with Gboard, creating a root dataset for its federated next-word prediction [2]. This root dataset may or may not align with the distribution of the overall training data used for the learning task. [1] Fudenberg, D. and Tirole, J. Game Theory. MIT Press, 1991. [2] Federated Learning: Collaborative Machine Learning without Centralized Training Data. [Online]. Available: https://ai.googleblog.com/2017/04/federated-learning-collaborative.htm
Summary
This paper considers the problem of backdoor/poisoning attacks in federated learning (FL). In this setting, a single attacker has control over all malicious clients trying to employ different attack types (on each controlled client). This paper aims to create a defense mechanism against such adaptive attackers. To this end, the paper proposes a game-theoretic approach, which contains two stages: (1) Pre-training stage: before the FL environment, the defender first learns a good defense policy by simulating that environment using a small amount of truthful data against a simulated attacker with known possible actions (e.g. attack types used), and (2) Online-adaptation stage: the defender leverages the pre-trained policy and adapt it against the attacker at the real FL environment. This paper demonstrates the effectiveness of their proposed mechanism, as well as considers ablation studies where the previous assumptions do not meet: adaptation to attack methods at real FL environment are different (but similar) from ones seen at the pre-training stage.
Strengths
The paper is well-written and easy to follow.
Weaknesses
I have some concerns, mostly about the practicality of the assumptions: 1. Assumption on the accessibility of data: the paper assumes that in the pre-training phase, the defender has access to a small amount of data, which is used to model the data distribution of clients using generative models. (1) It goes against privacy. (2) It is not clear that a small amount of data is representative enough to model client data distribution. (3) Things will be even more complicated if each client has its sub-population (data) that is (reasonably) different from each other. In this case, which malicious clients the attacker has control over will matter. 2. Assumption of the similarity of attack types at the online adaptation stage: the paper assumes that the attack types in a real FL environment, though unseen, should be similar to those of the pre-training phase. This seems impractical, especially in a white-box setting, where the attacker will try to leverage the property of the defense mechanism to create an adaptive attack that is specified for that defense mechanism (see Carlini's works). I also have concerns about the experiments: 1. Datasets and models used: Would it be possible to use more practical datasets and models instead of MNIST/CIFAR10 and ResNet-18? I would like to see results when the data distribution is complex enough that generative models cannot easily learn with a small amount of data. Right now, the amount of data used is still considerable, considering the dataset used. This would make the assumption of the accessibility to a small amount of data in the pre-training phase more persuasive. Some comments on writing/paper organizations. 1. In Table 1, please highlight which results are the best. It would be more readable and easier for comparison. 2. In Figure 2, it might be better to show smoothed curves. 3. In Appendix F, before each theorem/lemma/assumption, it would be better if an intuition/proof sketch for each one is provided. Also, if the proof technique/assumption is standard, please mention the corresponding references. 4. In the Conclusion, I think it would be more honest if explicitly stated that the major limitation of this paper lies in the practicability of the assumption. Right now, I only see privacy concerns mentioned, which is misleading. (Not really a weakness) It could be nice if source code is included (might be using an anonymous repo). Overall, I think this is a good paper if ignoring the practicability of the assumptions on the attack types/data (on the accessibility in the pre-training phase/distribution of accessed data in the pre-training phase/distribution of data in each client). I also did not find an experiment where the attacker leverages the information about defense mechanisms to instantiate a better attack scheme (white box attack). It is known that many proposed defense mechanisms failed in this scenario, though it seems obvious that it will go against the similarity assumption on the attack types at the online adaptation phase. However, I am also aware of the hardness of defense tasks in adversarial machine learning and it is good to have some initial results even under strong assumptions. I will try my best to be reasonable. Maths were not checked carefully, I will try to go into the details in the rebuttal phase.
Questions
See Weaknesses above.
Rating
4
Confidence
1
Soundness
2
Presentation
2
Contribution
2
Limitations
See Weaknesses above.
Reply to the rebuttal
- **On the dataset used in this work**: my concern is not that the paper lacks of experiments with large datasets, but: - In other federated learning works, it might be fine to use small datasets like MNIST and CIFAR10. However, there is a critical component in this paper, which is modeling data distribution of the clients given limited access to data. How can we know that if the data distribution is more complex, then we still can effectively (and sufficiently so that it does not affect the performance of the frameworks) the data distribution with limited data? This is my concern. - Moreover, I am also aware couple of works that use other (a bit more) complex datasets in federated learning (Tiny ImageNet), for example [1]. It would be nice if the experiments for those datasets were incorporated into this work. Overall, I find the rebuttal not convincing. Though I decided to keep my original rating, I would reduce my confidence score to 1. References [1] Dung Thuy Nguyen et al. IBA: Towards Inversible Backdoor Attacks in Federated Learning. NeurIPS'23.
Modeling data distribution in complex dataset
Thank you for the practical advice. We would like to first clarify that in addition to generative modeling in pre-training, we also utilize the inverting gradient (IG) method [1] in the online FL stage to infer the clients' data distribution (Appendix C lines 801-804), aiming to bridge the gap in data distribution. Due to space limitations, we moved the discussion of IG to Appendix C lines 783-791. A recent paper [2] shows that IG can successfully reconstruct images from ImageNet-1K from gradient data. While implementing more powerful generative models and advanced inverting gradient methods is beyond the scope of this work, our meta-SG framework can be integrated with them to handle more complex datasets. We further note that our approach can still work even if the learned distribution deviates slightly from the true distribution. This was observed for RL-based attacks in [Thm 1, 3], but a similar result also holds for RL-based defenses. [1] Geiping, J., Bauermeister, H., Dröge, H., & Moeller, M. (2020). Inverting gradients-how easy is it to break privacy in federated learning? Advances in neural information processing systems. [2] Hatamizadeh, Ali, et al. "Gradvit: Gradient inversion of vision transformers." Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2022. [3] Henger Li, Xiaolin Sun, and Zizhan Zheng. Learning to attack federated learning: A model based reinforcement learning attack framework. In Advances in Neural Information Processing Systems, 2022.
Summary
The paper addresses the vulnerabilities of Federated Learning (FL) systems to various adversarial attacks, including model poisoning and backdoor attacks. The proposed solution is a Meta Stackelberg Game (meta-SG) framework designed to offer robust and adaptive defenses against these attacks. The approach formulates adversarial federated learning as a Bayesian Stackelberg Markov game (BSMG) and employs a meta-learning method to find optimal defense strategies. Theoretical analyses show the algorithm's efficiency in convergence, and empirical results demonstrate its effectiveness against different attack types.
Strengths
1. The proposed framework considers both untargeted and targeted attacks. 2. The paper uses RL to realize online adaptation which is close to the real world. 3. Inspired by meta-learning, the method is robust to unknown attacks. 4. In the pre-training phase, the paper uses generated data to decrease the concern of privacy leakage. 5. The paper provides sufficient experimental results.
Weaknesses
1. Could you explain more about the necessity of adding the gradient adaptation (from BSE to meta-SE)? Although BSE is ex-ante when knowing the distribution $Q$, the model $\theta$ is changed during training and it could capture emerging information. Could you provide empirical results comparing BSE and meta-SE to show the advantage of meta-SE? 2. Considering adaptive/mixed attacks, the paper misses two relevant frameworks: MixTailor [1] and RobustTailor [2]. They can adjust aggregation methods during training. Especially, RobustTailor also simulates a game between the defender and the attacker, and it proposes a mixed attack. This kind of method could be included in experiments as a baseline. 3. Because the whole method is complicated with 2 stages, comparing computational cost with other baselines is necessary. [1] Ramezani-Kebrya, Ali, Iman Tabrizian, Fartash Faghri, and Petar Popovski. "Mixtailor: Mixed gradient aggregation for robust learning against tailored attacks." arXiv preprint arXiv:2207.07941, 2022. [2] Xie, Wanyun, Pethick, Thomas, Ramezani-Kebrya, Ali, and Cevher, Volkan. "Mixed Nash for Robust Federated Learning." Transactions on Machine Learning Research. 2023.
Questions
1. Are both white-box and black-box settings used in the pre-training stage? Adding the proposed methods explicitly in Figure 1 might be more clear.
Rating
5
Confidence
3
Soundness
3
Presentation
2
Contribution
3
Limitations
The authors mentioned limitations in Section 5. The main one is the privacy concern.
Thanks for the follow-up question
Thanks for your valuable time in reviewing and constructive comments. The key to our framework's ability to integrate NeuroClip and Pruning is its provision of a scalable and efficient method (i.e., meta-RL) for tuning the hyperparameters of these defense mechanisms. We have implemented a 'smarter' aggregator, where we manually tune hyperparameters (see Table 7) for defenses and choose the optimal ones to be applied for ClipMed and FLTrust + NC in Table 1. When there are multiple hyperparameters to tune, it becomes impractical. For instance, with norm bounding, Trimmed Mean, and NeuroClip, the search space expands to the range of the norm bound threshold multiplied by the Trimmed percentage and the clipping range. This search space is continuous and grows exponentially as the number of hyperparameters increases. We naively tested MixTailor (and could not find an open-sourse implementation for RobustTailor) to dynamically transition from the existing defenses listed in Table 1. However, this approach yielded worse performance compared to using only FLtrsut + NC. Below we further clarify why the original versions of Mixtailor and RobustTailor are not suitable for comparison in our context due to the different considerations in problem setup, online adaptation, and scalability. $\textbf{Problem setup:}$ Both Mixtailor and RobustTailor consider defenses against a single white-box attack that is tailored to the honest training gradients. That is, the attack objective is to drag the aggregated gradient away from the honest one as much as possible. To counter such attacks, the two works explore the idea of randomization over aggregation rules, creating information asymmetry on the defense side. However, our work focuses on defending against a mixture of unknown/uncertain attacks. These attacks may not be tailored to the honest gradients, such as targeted attacks. Our framework uses game-theoretic meta-learning to address information asymmetry on the attack side, requiring the defense to be tailored online to unknown/uncertain attacks. $\textbf{Online Adaptation:}$ Due to different problem setups, MixTailor and RobustTailor do not consider and are unable to incorporate online adaptation. MixTailor simply picks an aggregation randomly, while RobustTailor approximately solves a minimax problem to get the sampling distribution over the set of aggregation rules. One can view the resulting defense as a worst-case defense without considering the actual attack methods. RobustTailor only uses the current gradient information at each round to determine the aggregation. In contrast, our proposed method considers online adaptation, which utilizes trajectories of online model updates (gradients) to implicitly identify the attack type (different attacks induce different trajectories). A trajectory contains more informative feedback than gradients at each round. Then, online gradient adaptation is derived using the trajectories. $\textbf{Scalability:}$ Both Mixtailor and RobustTailor considered randomization over a finite set of aggregation rules. Our experiments consider defense methods (e.g., aggregation rules) parameterized by continuous parameters, which are optimized by the proposed meta-RL algorithm using policy gradients, which can efficiently handle continuous action space. In contrast, to apply the two randomization methods, we need to first discretize the parameter space. The number of the discretized parameters grows exponentially with respect to the dimension (i.e., the number of hyperparameters for all defenses combined).
Thanks for the detailed response
Thanks for the detailed response, and it addressed my concerns about the other two frameworks. I'll keep my score because I'm not sure whether a little privacy leakage is acceptable in federated learning.
Thanks for the rebuttal
Thanks for the authors' reply and explanation. I have the following question. Can backdoor-defending methods like NeuroClip be incorporated in other aggregation rules like FedAvg or Trimed Mean? If yes, why MixTailor or RobustTailor cannot be used? Currently, Meta-RL with extra pre-training only compared with some basic single aggregators. It'll be more convincing if it can be compared with some more 'smarter' aggregator.
I am not an expert on federate learning, so I leave the significance of that to other reviewers. But, I know game theory very well and I am not satisfied (and curious) about this new sort of equilibrium idea proposed without really exploring what it means in the sequential setting. The privacy angle still is a question - I feel used in prior work precedent is not enough.
Discussion about public dataset in FL
Dear Reviewers and AC, We would like to provide a more detailed discussion to address the privacy concerns related to accessing public datasets. In Federated Learning (FL), it is a common practice to use a small globally shared dataset to enhance robustness (see Section 3.1.1 of [1]). This dataset could come from a publicly available proxy source, a separate non-sensitive dataset, or a processed version of the raw data as suggested by [2]. The use of such public datasets is widely accepted in the FL community [1, 3, 4, 5]. For example, systems like Sageflow [6], Zeno [7], and Zeno++ [8] leverage public data at the server to address adversarial threats. Additionally, having public data available on the server supports collaborative model training with formal differential or hybrid differential privacy guarantees [1, 9, 10]. [10] introduces hybrid differential privacy, where some users voluntarily share their data. Many companies, such as Mozilla and Google, utilize testers with high mutual trust who opt into less stringent privacy models compared to the average end-user. It is also worth mentioning that one of the defenses that Reviewer HbAX mentioned, i.e., RobustTailor, also assumes a public dataset (see Remark 1 in the paper). [1] Kairouz, Peter, et al. "Advances and open problems in federated learning." Foundations and trends® in machine learning 14.1–2 (2021): 1-210. [2] Wang, Tongzhou, et al. "Dataset distillation." arXiv preprint arXiv:1811.10959 (2018). [3] Minghong Fang, Xiaoyu Cao, Jinyuan Jia, and Neil Gong. Local model poisoning attacks to Byzantine-robust federated learning. In USENIX Security Symposium, 2020. [4] Wenke Huang, Mang Ye, and Bo Du. Learn from others and be yourself in heterogeneous federated learning. In Conference on Computer Vision and Pattern Recognition (CVPR), 2022. [5] Naoya Yoshida, Takayuki Nishio, Masahiro Morikura, Koji Yamamoto, and Ryo Yonetani. Hybrid-FL for wireless networks: Cooperative learning mechanism using non-IID data. In IEEE International Conference on Communications (ICC), 2020. [6] Jungwuk Park, Dong-Jun Han, Minseok Choi, and Jaekyun Moon. Sageflow: Robust federated learning against both stragglers and adversaries. Advances in Neural Information Processing Systems (NeurIPS), 34:840–851, 2021. [7] Cong Xie, Sanmi Koyejo, and Indranil Gupta. Zeno: Distributed stochastic gradient descent with suspicion-based fault-tolerance. In International Conference on Machine Learning (ICML), 2019b. [8] Cong Xie, Sanmi Koyejo, and Indranil Gupta. Zeno++: Robust fully asynchronous SGD. In International Conference on Machine Learning (ICML), 2020b. [9] Xin Gu, Gautam Kamath, and Zhiwei Steven Wu. Choosing public datasets for private machine learning via gradient subspace distance. arXiv preprint arXiv:2303.01256, 2023. [10] Brendan Avent, Aleksandra Korolova, David Zeber, Torgeir Hovden, and Benjamin Livshits. BLENDER: Enabling local search with a hybrid differential privacy model. In USENIX Security Symposium, 2017.
Decision
Reject