FedGT: Identification of Malicious Clients in Federated Learning with Secure Aggregation

We would like to thank the reviewer for thoroughly reading the manuscript and for the insightful comments in order to make the paper stronger. Below, you may find the answer to the questions posted.

• Structure and novelty: We acknowledge that channel coding and its relation to group testing is not novel. However, as this work is written towards the machine learning community, we deem Section 5 important as it provides the necessary background to the proposed method. Indeed, another reviewer asked for more information on this part. To the authors' knowledge, this paper constitutes the first marriage of group testing and federated learning. This further allows the server to identify malicious clients, something that has previously not been possible. Furthermore, as the reviewer points out, by utilizing the connection to channel coding, we are able to relate the group testing strategy to secure aggregation protocols, something that is also novel.

• Assumptions and hyperparameters: We acknowledge that a known target may seem like a big assumption. However, by inspecting the recalls of the different classes in the validation dataset, it turns out to be easy to identify labels that are under attack. In the table below, we illustrate the class recalls for each group over all labels (only one is under attack) for the experiments over CIFAR10 dataset (label 7 is under attack). Note that the groups have different numbers of malicious clients and we denote this by $\tilde{n}_m$ in the table. Hence, we argue that it is easy for the server to simply compute the class recall for each class; if an anomaly is observed in the evaluated recalls, that class is likely under attack. Given the large discrepancy between the class recall of a benign model and a poisoned model, we conduct the experiments under the assumption that the targeted label is easily identified.

  $\tilde{n}_m$ \ label	0	1	2	3	4	5	6	7	8	9
  1	0.55	0.17	0.33	0.6	0.71	0.33	0.85	0.0	0.91	0.56
  0	0.45	0.17	0.44	0.4	0.57	0.67	0.77	0.69	1.0	0.78
  1	0.36	0.17	0.33	0.4	0.79	0.67	0.85	0.08	1.0	0.67
  0	0.64	0.33	0.33	0.4	0.71	0.56	0.69	0.54	1.0	0.56
  2	0.82	0.17	0.22	0.4	0.86	0.67	0.77	0.0	0.82	0.56
  1	0.64	0.17	0.33	0.4	0.71	0.67	0.92	0.08	1.0	0.67
  2	0.55	0.33	0.33	0.6	0.71	0.44	0.85	0.0	0.91	0.56
  1	0.45	0.33	0.44	0.6	0.64	0.67	0.77	0.0	1.0	0.67

We thank the reviewer for the suggestion of considering a different $Q(\mathbf{t}\lvert \mathbf{s})$---it is indeed an interesting direction. For sake of clarification, we model the noisiness of the test $Q(t_i\lvert s_i)$ as a BSC in order to make it more realistic. For example, an asymmetric binary channel might be hard to motivate in a general real-life problem, even though the decoder we use is capable of handling an asymmetric model. Then, we treat the overall noise of the tests to kick-start the backward recursion in the forward-backward decoder $Q(\mathbf{t}\lvert \mathbf{s})$ as $m$ (size of $\mathbf{t}$) parallel BSC with crossover probability $p$. We understand that a smarter way is to treat $Q(\mathbf{t}\lvert \mathbf{s})$ as a parallel set of several BSCs with crossover probability $p_i$ for $i \in [m]$. Indeed, with our test, one can incorporate this information by investigating the clustering of the group accuracies/source recalls. However, note that the best one can achieve by incorporating this information is to approach the performance of a potential noiseless (genie-aided) testing strategy. However, we observe that FedGT is not performing very far away from its noiseless version (see Figure 10). Therefore, the complexity needed to choose suitable $p_i$'s on the fly does not pay off in terms of performance. Another interesting direction is not to treat the channel models as memory-less, i.e., as parallel BSCs but rather sequential. As the groups overlap, the test vector will indeed have dependent entries and, information-theoretically, one loses information by treating dependent entries as independent. However, we believe that incorporating memory to the decoder increases its computation overhead and most importantly, makes the solution not general and far from a real-world application. It is important to note that modeling the noise with a simple BSC provides the decoder the smallest possible information, but for the sake of practicality and generalization, we follow this simple model.

• Structure and novelty: To be clear, I am not against keeping some or even many of the coding theory aspects of the paper in Section 5. What I am saying is that the current presentation of Section 5 is unfair towards [1], where they are cited as a tangentially related paper, when this paper's techniques are practically lifted directly from [1]. This alone is grounds for rejection, but I do not think that the authors do this on purpose (or at least hope so). That said, it is a precondition for acceptance to properly give credit to [1]. My other point is that the current version of Section 5 is, as acknowledged by the authors, just not enough background for most ML researchers, including me. I found reading [1] the solution for myself. In particular, just putting the forward-backward algorithm formula does not help an average ML researcher to understand the coding theory/group testing theory involved, and doesn't give a coding theory expert any valuable information either. It is up to the authors how they want to structure Section 5 provided the credit to [1] is given, but another option will be to put a lot of additional information in the appendix. To be blunt here, the reviewer is not sure if there are any good solutions to presenting all the needed background to an ML crowd, the reviewer is just giving suggestions that can hopefully help.
• Assumption of knowing the target: In a poisoning scenario where a whole class is attacked, I find the reasoning provided by the authors useful. The authors should include it in their experiment and threat model discussion. That said this only applies in this scenario and I think this scenario is not that common in practice.
• Assumptions $Q$: Thank you for the informative answer.
• The hyperparameter $\Lambda$: I still think that the paper will benefit from more principled way of setting it given its claimed connection to $\Delta'$ which can be set principally.
• Benchmark comparison: The reviewer appreciates the additional capabilities of FedGT. However, the authors themselves point to poisoning prevention under aggregation as their main application. As such the worse benchmark results remain very relevant to this paper. My concern that RFA is "hampered" compared to FedGT remains. I know that apples-to-apples comparison is hard but the results do not reflect the advantage of FedGT of being able to choose the trade-off parameter. -Impact of mismatch: I am thankful to the authors for the additional experiments. I think providing experiments on multiple realizations in the next revision of the paper will be beneficial.

All in all, I am happy with the engagement from the authors, but several big issues remain. In particular, one is properly citing [1] and making the paper more accessible to the ML community, and the other one is the results in comparison to RFA. I simply think that the paper needs another major revision, both experiment-wise and writing-wise. I cannot recommend acceptance. I am open to continuing the discussion, however, for the purpose of improving the paper.

We thank the reviewer for their review and for the questions raised. We would like to thank the reviewer for finding our idea novel and effective. Below, you may find our response.

1. Communication Cost: We understand and are aware of the fact that secure aggregation comes with a high communication cost. In our work, we presented results where we do secure aggregation across many small groups of clients in a single communication round. In Appendix B, we leverage state-of-the-art protocols to estimate and the communication overhead of our proposed framework. For the experiments in the main body, we would like to emphasize that, compared to RFA, the communication overhead of FedGT is lower or similar in all rounds, including when group testing is performed.

2. Privacy: The reviewer raises a valid concern. However, this is completely captured by the concept of minimum distance of the dual code (the code having the assignment matrix as a generator matrix). For the particular case raised by the reviewer, the assignment matrix will look like this:

   1 & 1 & 1 & 0 & \\dots &0 \\\\ 0 & 1 & 1 & 0 & \\dots &0 \\\\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \end{pmatrix}$$ Then, the code defined by $\mathbf{A}_1$ as a generator matrix will have in its codebook (rowspan) the vector $(1,0,0, \dots, 0)$. In our application, this means that by linear combinations, the server can get the model C1. However, in our experiments, we use an assignment matrix that defines a code of minimum Hamming distance $4$, this ensures that any linear combination performed by the server will result in an aggregation of at least $4$ client models. Hence, for the codes proposed in the paper, privacy is preserved.

• Knowledge of the number of malicious clients: As mentioned in the paper, we share this view with the reviewer. Feeding the prevalence $\frac{n_m}{n}$ to the decoder requires perfect knowledge of $n_m$, something that is typically not available at the server. However, we show in Appendix G that the decoder is robust to a mismatch in the prevalence, i.e., when an incorrect value $\tilde{\delta} \neq \delta$ is used instead. To strengthen this further, we performed simulations for a targeted attack on CIFAR-10 dataset, for $n_m \in \lbrace 1, 3, 5\rbrace$ where we only feed the decoder a mismatched value $\tilde{\delta} = 0.1$ and $p=0.05$. Below, we present the results as the top-1 accuracy (ACC), attack accuracy (ATT), misdetection and false-alarm probabilities versus the decoding threshold $\Lambda$ for $n_m=1,2,3$, respectively.

  $n_m = 1$

  $\Lambda$	$P_{FA}$	$P_{MD}$	ACC	ATT
  -0.8	0.0	0.0	0.83	0.04
  -0.6	0.0	0.0	0.83	0.04
  -0.4	0.0	0.0	0.83	0.04
  -0.2	0.0	0.0	0.83	0.04
  -0.0	0.0	0.0	0.83	0.04
  0.2	0.0	0.0	0.83	0.04
  0.4	0.07	0.0	0.83	0.04
  0.6	0.07	0.0	0.83	0.04
  0.8	0.07	0.0	0.83	0.04
  1.0	0.14	0.0	0.83	0.03

  $n_m = 3$

  $\Lambda$	$P_{FA}$	$P_{MD}$	ACC	ATT
  -0.8	0.0	1.0	0.83	0.12
  -0.6	0.08	0.67	0.83	0.11
  -0.4	0.08	0.67	0.83	0.11
  -0.2	0.08	0.67	0.83	0.11
  -0.0	0.08	0.67	0.83	0.11
  0.2	0.08	0.33	0.83	0.06
  0.4	0.08	0.33	0.83	0.06
  0.6	0.08	0.33	0.83	0.06
  0.8	0.17	0.33	0.82	0.07
  1.0	0.17	0.0	0.82	0.04

  $n_m = 5$:

  $\Lambda$	$P_{FA}$	$P_{MD}$	ACC	ATT
  -0.8	0.0	1.0	0.81	0.31
  -0.6	0.1	0.8	0.82	0.22
  -0.4	0.1	0.8	0.82	0.22
  -0.2	0.1	0.8	0.82	0.22
  -0.0	0.1	0.8	0.82	0.22
  0.2	0.1	0.6	0.81	0.21
  0.4	0.1	0.6	0.81	0.21
  0.6	0.1	0.6	0.81	0.21
  0.8	0.1	0.4	0.82	0.11
  1.0	0.1	0.2	0.82	0.08

  From these experiments, we observe that the attack accuracy and accuracy are robust even when the prevalence $\tilde{\delta}$ and crossover probability $p$ are mismatched.

• Privacy definition: We agree with the reviewer that the privacy investigation could be deepened. To the best of our knowledge, analyzing the privacy of secure aggregation is still an open problem and subject to active research. It is known that privacy increases with the number of clients being aggregated [2] but to the authors knowledge, no work is able to formally quantify the privacy of secure aggregation. All in all, the reviewer's suggestion constitutes an interesting research direction, but it is beyond the scope of this paper.

• Neyman-Pearson decision criterion: We thank the reviewer for the interesting question. We agree that the choice of decision criterion used is critical for the performance of FedGT. We describe briefly the main idea behind Neyman-Pearson decision criterion in Appendix~C and the rationale behind its usage. The Neyman-Pearson decision criterion is optimal in the sense that it minimizes one type of error (misdetection or false-alarm) subject to a constraint on the other type of error. In machine learning applications, one typically targets a high true-positive rate and a low false-positive rate. The true-positive rate is often measured at a fixed false-positive rate that is deemed acceptable. Such a scenario directly translates into the Neyman-Pearson formulation.

[1] - https://www.melloddy.eu/

[2] - A. R. Elkordy, J. Zhang, Y. H. Ezzeldin, K. Psounis and S. Avestimehr, "How Much Privacy Does Federated Learning with Secure Aggregation Guarantee?", 2022.

We thank the reviewer for their efforts and for the questions and for raising awareness regarding potential weaknesses of the paper.

• Scalability: We thank the reviewer for pointing out this important aspect. We acknowledge that the experiments are targeting scenarios with a low number of clients. This choice is inspired from practical instantiations of cross-silo FL which, so far, typically has involved client constellations of sizes around $10$, see e.g., [1].

  Regarding the scaling: the main bottleneck lies in the optimal decoding operation that has a complexity of $\mathcal{O}(2^m)$. Hence, as the number of test grows, i.e., the number of rows in the assignment matrix, the decoding operation eventually becomes infeasible. Hence, provided a reasonable number of tests, FedGT scales to an arbitrary number of clients. Increasing the number of tests for a fixed number of clients will allow the server to obtain more fine-grained information about the clients at the expense of reduced privacy and a more complex decoding operation.

• Comparison with RFA: The reason why we compare FedGT's performance to RFA is that RFA also aims at preserving the privacy of the clients' data. Other robust aggregation schemes do not attempt to preserve privacy as they typically rely on the server having access to the clients' individual models, thus exposing the client to different forms of attack, e.g., data reconstruction attacks. Hence, in an attempt to compare apples-to-apples, we settled for RFA.

  In the setting of an untargeted attack (Figure 3), our experiments have rendered RFA superior for lower prevalences and we agree that lower prevalences are more likely than higher one, especially for a cross-silo FL scenario. However, the performance of FedGT is competitive with RFA and it provides identification of malicious clients. In the case of an unintentional poisoning attack, FedGT offers the possibility to notify the flagged client and have it fix the data issue whereafter it may join the federation, enabling improved performance. Robust aggregation schemes like RFA does not offer this possibility.

• Number of attackers for the setting $n=31$: For the experiments involving $n=31$ clients, we consider $n_m= 6$ malicious clients. This corresponds to $20\%$ of the clients being malicious, a number that, to the authors, does not seem to be unreasonably small. The rationale of this experiment is to demonstrate that FedGT scales beyond the experiments provided in the main body that includes only $15$ clients. Moreover, the malicious clients still "collude" as they attempt to deteriorate the learning in the same way. However, compared to the main body, each client has less data and therefore less power to influence the global model. \item Validation dataset at the server: We would like to emphasize that the validation dataset utilized in our instantiation of FedGT is purely due to the testing strategies that rely on the group accuracy and the group recall, respectively. The framework is valid for arbitrary testing strategies and others, not requiring a validation dataset, are possible. One such test could rely on clustering the principal components of the aggregated subgroup models. Furthermore, note that we assume a quasi-dataset for validation in the paper, i.e., a dataset distributed similarly---but not necessarily equal---to the clients' data. Also, in our tests, we use a very small validation set consisting of $100$ data points, which is significantly smaller than the client datasets.

We thank the reviewer for the comments and the suggestions and for finding the proposed idea interesting. Regarding the weaknesses spotted in this review, we appreciate them and below you may find our comments.

• We believe that the challenges of FL pertaining to privacy and security are important also for the ML community. We also believe that combining expertise from different scientific communities can benefit the development of resilient and privacy preserving FL. Furthermore, we think it is a good idea to present our framework in an ML venue to demonstrate that it is possible to identify malicious nodes, not only mitigating their impact. To the authors' knowledge, FedGT is the first method to achieve this and we believe it is an important cornerstone to provide privacy while securing FL from different attack techniques. In regards to novelty, we offer new insights into the privacy of sub-group testing by drawing on connections between coding theory and secure aggregation. Furthermore, our work is the first to demonstrate identification of malicious nodes in FL without inspecting individual client contributions. We have chosen one of the simplest testing strategies possible to demonstrate the inherent potential of leveraging group testing with FL even in the presence of very naive tests. We are currently working on extensions to more sophisticated tests.

• We understand that it might be confusing for a potential reader who is not familiar with coding theory and we tried our best in Section 5 to introduce the relevant concepts. However, due to the page limits, we had to skip some details. Please do understand that coding theory is a research area that has been studied for more than 70 years, making it very challenging to incorporate all but the necessary details in a few pages. Furthermore, references are provided to the interested reader. The process of finding good codes and their corresponding parity-check matrix (used as an assignment matrix in the context of group testing) typically involves choosing a class of well-known codes (like BCH code, Reed-Muller codes). Usually, for short-length codes (up to ~100 bits), algebraic codes (BCH, Reed-Muller) are considered and the properties of these codes are well-studied. We follow this process in our paper and use a BCH code (length 15) for the experiments in the main body and a cyclic code (length 31) in Appendix J. In the submission, we cite the following book [1], where well-known (algebraic) codes are tabulated, but there also other works that provide a comprehensive list of channel codes.

• As the reviewer points out, conventional binary channel codes are designed over the binary finite field. However, coding theory does not necessarily need to be based on the binary finite field. In fact, there exist also codes defined over rings rather than fields. However, we need to clarify that is not our contribution to use channel codes for group testing. Existing works [2] have showed that well-known channel codes help in designing nice pooling strategies.

• Regarding the question of Figure 1(c), from the heterogeneous data among the clients, some clients, although benign, actually deteriorate the model by participating. Client 4, whose dataset consists mainly of examples labeled as class 2, see Fig. 13, constitutes such an example. Our group testing framework, with the employed testing strategy, is tailored to reduce the attack accuracy in targeted attacks (and increase the balanced accuracy in untargeted attacks). Thus it may misclassify some clients that are deemed to deteriorate the global model. That is, from the group testing's point of view, client 4 seems to be compromised. Constructing defensive mechanisms that are able to handle such severe imbalance in label distribution is a challenging and open research problem.

[1] - MacWilliams, F. J. (Florence Jessie), and Sloane, N. J. A. (Neil James Alexander), (1977). The theory of error correcting codes, Elsevier/North-Holland.

[2] - A. Barg and A. Mazumdar, "Group Testing Schemes From Codes and Designs," in IEEE Transactions on Information Theory, vol. 63, no. 11, pp. 7131-7141, Nov. 2017.