Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The authors propose an attack on federated learning where a subset f clients are compromised. The problem is formulated as a game where both players use a no-regret learning algorothm to converge to the NE. The game is simulated, as the defender does not know the true updates of compromised clients.
strength_and_weaknesses: I am surprised that no-regret algorithm converging to NE in a two player zero-sum game is presented as a new result. This is a very well-known result, and appears in lecture notes and tutorials also, e.g., see page 33 in https://algo.cs.uni-frankfurt.de/lehre/agt/winter1920/folien/correlated.pdf

I believe a main purpose of federated learning is to preserve privacy of private data-sets. The assumption of the server having access to a dataset from every client (even one that mimics client data distribution but is not the actual data) is a loss of privacy. The authors have cited a number of previous works to support this (sorry, I have not read these cited papers), but have not really discussed why this kind of access to dataset is fine from a privacy perspective. Please provide a detailed response to this question.

I am bit lost in notations, but is there some assumption about \tilde{g} such as unbiased estimate? Along similar lines, isnt there some assumption about the simulation that could relate Sim-MinMax to MinMax. Solving Sim-MinMax is fine only if that is close (close in some sense that must be defined) to MinMax.

Minor point: the footnote on page 1 refers to an experiment in the appendix, if this point was important to mention in Introduction, maybe this experiment should be in main paper.

clarity,_quality,_novelty_and_reproducibility: The paper is clear to read.
I think the idea is novel, but I have a some basic questions - see weaknesses.

summary_of_the_review: A good overall idea, but I am not sure of claims made in the paper being novel or interesting.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper introduces a game theoretic model to study defense against adversarial attacks in federated learning. The task of designing a robust learning algorithm against potential attacks is formulated as the problem of computing a good strategy in a game. The authors presented bandit algorithms to compute the equilibrium of the game as well as several results about the theoretical guarantee of the algorithm. Experiments were also conducted to evaluate the performance fo the algorithm and the quality of solutions it generates.
strength_and_weaknesses: Strength: The paper studies an interesting and well-motivated problem and takes effort to model it and formulate it as a game. The paper is clear and easy to follow and results look complete.

Weakness: Theoretical contribution is a bit thin. The model looks a bit simplistic and hence more like one "on paper". Some assumptions are a bit too strong. For example, the assumption that both players choose their algorithms from finite sets known to each other is a bit too strong, and seems more for the sake of formulating the problem as a normal-form game. 
clarity,_quality,_novelty_and_reproducibility: The presentation is clear, and results look sound. The idea of formulating robust learning as a game against an adversary may be novel in the specific literature on federated learning.
summary_of_the_review: A well-presented paper on a well-motivated problem, with some novelty in the specific literature. Results look sound but a bit thin on the theoretical side.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposed a minimax formulation to model the attacks and defenses in federated machine learning. The aggregator is an agent who wants to maximize the accuracy in presence of Byzantine clients, where the Byzantine clients want to corrupt the performance of the aggregated model. Therefore, federated learning with Byzantine attacks can be viewed as a two-player zero-sum game. To estimate the loss value for the two players, the paper proposed using public dataset to construct a simulator of the environment. To further reduce the computational time, the authors considered using bandit feedback, in which only the loss for the selected aggregator and tailored attack is observed. Fortunately, by using no-regret bandit algorithms, the averaged historical policy converges to some Nash Equilibrium, and thus the output aggregator selection policy is optimal in the sense of NE. The paper provided extensive experimental results and demonstrate that the proposed defense can indeed improve the robustness of federated learning against Byzantine attacks.
strength_and_weaknesses: Strength:

(1) This paper captured a very interesting observation in game theory that the averaged historical policy produced by no-regret learners can approximate a Nash Equilibrium when the game is played repeatedly. This is a very cute idea that naturally matches the federated learning problem in presence of Byzantine attacks. The methodology is also novel in the federated learning domain.

(2). The paper provided strong and extensive empirical results and demonstrated that the proposed defense indeed enhances the robustness of federated learning against training-time attacks.

Weaknesses:

(1). Most theoretical results in this paper are not novel. In particular, The Lemma 1 and 2 are both existing results in the game theory and multi-armed bandit domain. The Lemma 3 is somewhat novel, but it seems to be an easy application of Lemma 1 and 2. Therefore, while the paper provided theoretical guarantees, the results are not surprising or novel enough to me. Besides that, I think in a lot of places, the paper missed a min operator, e.g., in the regret definition (8) and also (10). Please add the min operator to avoid confusion.

(2). The paper relied on a public dataset to construct some simulator, and then uses the simulator to obtain estimated loss/reward for the aggregator and attacker. Therefore, the regret that Algorithm 2 tries to minimize is actually the objective on the public dataset, instead of the ground-truth environment. Although the authors provided several papers to support this assumption of having a simulator, I am kind of 
curious what if there is a distribution gap between the public dataset and the global environment. It would be interesting to discuss this problem and provide some empirical study.

(3). I believe the authors should consider using EXP3.P instead of EXP3 to do experiments. This is because although EXP3 achieve no regret, it requires an important condition that the loss functions over time are pre-determined before the game starts. However, in this paper, the attacker can be adaptive to the behavior of the aggregator over time. That means the policy q_t selected by the adversary can depend on the historical p_t selected by the aggregator. As a result, the loss function for the aggregator at time t is p*E(L)*q_t^T also depends on the historical p's (i.e., p_1, ..., p_{t-1}), and thus is not determined beforehand. The EXP3 does not provide strict theoretical guarantee in this case. Instead, the EXP3.P would work.
clarity,_quality,_novelty_and_reproducibility: The paper is technically interesting.
summary_of_the_review: I worked in related areas.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a two-player zero-sum game for model poisoning attack and defense in federated learning. A powerful attacker with full knowledge of the FL system is considered, where the attacker controls a set of malicious devices that can share manipulated model updates with the server to lower the accuracy of the global model. In each FL iteration, the defender picks a defense rule randomly from a pool of robust aggregation-based defense algorithms by simulating the attacker's behavior using a small set of public data shared by honest devices. Similarly, the attacker picks an attack algorithm from a pool of attacks by simulating the defender's behavior using its knowledge of honest devices and the FL system. The paper formulates the attack-defender interaction in each FL iteration as a zero-sum game and adapts the Exp3 algorithm to solve the game on each side. Convergence analysis is provided together with a set of empirical results. 
strength_and_weaknesses: The idea of switching defense policies dynamically to increase the attacker's uncertainty in adversarial machine learning has been considered before, although in a slightly different context [1]. The game theoretic model seems straightforward but reasonable. The main novelty of the paper is to simulate malicious devices' behavior using a small amount of honest data. However, the proposed method has some strong limitations. 

First, from Algorithm 1, it is clear that the paper only considers non-adaptive attacks and defenses where a fixed rule is applied in each iteration. This can also be seen from the myopic loss function defined in (6). However, adaptive algorithms have been developed for both defenses [2,3] and attacks [4] in federated learning. Neither the algorithmic framework nor the analytic result in the paper applies to adaptive attacks or defenses.  

Second, the paper ignores that most poisoning attacks and defenses have a set of adjustable hyperparameters that significantly affect their strength, making the possible attacks (and defenses) a very large or infinite set. The proposed solution only works for the finite case and suffers from a high complexity for large sets of attack and defense strategies. The experiments in Section 5 only consider a very small configuration with two defenses and two attacks with fixed parameters. Although more defenses are considered in Figure 8 in the appendix, the defense strategy is sampled from the pool uniformly at random without using the proposed solution. 

Third, the game formulation ignores subsampling, a commonly used technique in large-scale federated learning. An advanced attacker will adapt its strategy according to the subset of malicious devices sampled in each iteration, creating another level of complexity unconsidered in the paper. 

[1] Sengupta, Sailik, Tathagata Chakraborti, and Subbarao Kambhampati. Mtdeep: Moving target defense to boost the security of deep neural nets against adversarial attacks. International Conference on Decision and Game Theory for Security. 2019. 

[2] Dan Alistarh, Zeyuan Allen-Zhu, and Jerry Li. Byzantine stochastic gradient descent. Advances in Neural Information Processing Systems(NeurIPS), 31, 2018

[3] Sai Praneeth Karimireddy, Lie He, and Martin Jaggi. Learning from history for byzantine robust optimization. In International Conference on Machine Learning(ICML), 2021

[4] Xiaoyu Cao, Minghong Fang, Jia Liu, and Neil Zhenqiang Gong. Fltrust: Byzantine-robust federated learning via trust bootstrapping. In NDSS, 2021


clarity,_quality,_novelty_and_reproducibility: Several important assumptions are not well justified.  

First, it is assumed that the set of available attacks and the set of possible aggregators are common knowledge. In practice, however, it is more likely that the defender has limited knowledge about the attacks. An advanced attacker can either create a new attack or adapt an existing attack to make it unknown to the defender. Figures 9 and 10 in the appendix give some results in this direction. However, important details are missing. What is an attack "of the same type"? What is the "Mimic" attack? What is the "Alittle" attack? 

Second, the paper assumes that each client donates a small subset of data to the server so that the server can simulate their behavior. Although this might be possible in certain application scenarios, obtaining a representative set of data samples can be challenging in general due to the heterogeneity among devices. Besides, malicious devices can share poisoned data samples with the server. Although Figure 11 in the appendix shows that the proposed method is still effective when each client only shares 0.1% of their local data, the simulation setting used to generate the figure is missing. Which dataset is used? Are the local data distributions iid or non-iid? What are the attacks and defenses considered?  

Third, it is assumed the attacker has full knowledge of the model updates of all honest clients during training. Although this might be acceptable for earlier works on model poisoning (e.g., [Xie et al., 2020] and [Fang et al., 2020]) to demonstrate the worst-case damage that an attacker can possibly cause, it would be useful to consider more realistic attacks to understand the security of federated learning systems. Even in [Fang et al. 2020], more realistic partial knowledge attacks are developed in addition to full knowledge attacks. 

Some implementation details are missing. What is the deep neural architecture used for CIFAR-10? How does the server generate the estimated \tilde{g}_i based on the public dataset? 

summary_of_the_review: The paper proposes a game-theoretic framework to model poisoning attacks and defenses in federated learning where both the attacker and the defender adapt their behavior dynamically by simulating the behavior of the other side. Similar ideas have been considered in cybersecurity and adversarial learning. Although its application in federated learning seems new, the proposed method has strong limitations and relies on unrealistic assumptions.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: In this paper, the authors studied a gam-theoretical formulation to model attacks/defenses in the setting of federated learning. The reviewers anonymously agree that the problem is important, the idea is interesting, and the the paper is in general well-written. On the  other hand, all reviewers have various reservations on accepting this paper, even after the rebuttal. The main concerns include: the theoretical analysis is not very novel; the assumption of sharing a (subset) of the dataset to the public hurts privacy; the experiments are not thorough enough as a security paper. After reading the paper myself, I agree with reviewers that the paper in the current form (even the revised version) is not ready to be accepted. The reviewers have provided thorough comments which I strongly encourage the authors to take serious consideration when preparing for the next submission. 

justification_for_why_not_higher_score: The analysis is not novel (enough), reviewers still have concerns on the privacy matter for sharing a sample of the data; the experiments are not thorough enough.
Decision: Reject