A Study of Black-Box Attacks Against Robust Federated Learning

The performance of the proposed attack is not very impressive. Although it typically outperforms the two simple baselines, they are comparable with small gaps in most cases. Further, with 20% malicious devices, neither of them can compromise the system using vanilla FedAvg when the local data distributions are close to iid, and neither of them can compromise the geometric median unless the local data distributions are highly non-iid. Even with 40% malicious devices, which is far from being realistic, they cannot compromise the geometric median when the local data distributions are close to iid. Why should one still worry about the black-box attacks?

The evaluation is not comprehensive. First, the two commonly used robust aggregation rules, namely, trimmed mean and coordinate-wise median, are not considered. Second, the paper assumes that all the devices are sampled in each round. However, subsampling is typically used in large FL systems. Since the Nelder-Mead method relies on actions and rewards from consecutive rounds, it is unclear if the proposed attack is still effective with subsampling. Third, the paper does not consider more advanced defenses such as FLTrust (Cao et al., 2021), which requires the server to access a small amount of clean data but can potentially provide better protection to the FL system.

Xiaoyu Cao, Minghong Fang, Jia Liu, Neil Zhenqiang Gong. FLTrust: Byzantine-robust Federated Learning via Trust Bootstrapping. NDSS 2021.

The experimental evaluation is not convincing and raises several concerns:

• The lack of comparison with other attacks proposed in the research literature. The authors argue that none of them have the same threat model, but that is not completely true. For instance, in similar settings as the ones used to perform the experiments, attacks like in Baruch et al. do not really assume knowledge about the aggregation rule or model poisoning attacks as in Bhagoji et al. (“Analyzing Federated Learning through an Adversarial Lens”) could be used in the comparison.
• The attack is not really strong against standard Federated Averaging, which raises questions about its effectiveness. For instance, Blanchard et al. showed that just with a single adversary, it is possible to completely compromise federated averaging with a trivial attack strategy consisting on sending random model updates with a large variance, whereas, for example, in the experiments reported in Table 1 for MNIST, with 20% of attackers, the accuracy is more than 40% (and up to 70%) for all the results reported for different values of alpha.
• The results do not include the error bars and the assessment of which method is better in each case should be on the basis of the result of a statistical significance tests.

There are critical weaknesses suggesting that the paper is not yet ready for publication, mainly concerning the inaccuracy of the main claim of the paper, the great lack of clarity, and the weakness of the experimental validation.

1. The proposed attack is not black-box as claimed.

In Section 3, it is explained by the authors that action taken by the adversary depends on the previous rewards. Computing these rewards requires being able to evaluate the accuracy of the server's model on the test set. To do so, the adversary must have access to the data of honest workers, which means that the attack is not black-box, even according to the paper's problem setup in Section 3.1. Also, the attack implicitly assumes the knowledge of the optimizer used by the server; a constant learning rate is used throughout the paper.

Given that this is a central claim of the paper, this is my main concern.

2. The paper is extremely unclear in several instances.

• The reinforcement learning branding seems unneeded, as far as I understand, and only adds clarity-affecting complexity. It seems that the proposed attack tries to solve an optimization problem to find the attack vector at each step, which should be explained as such. The formalism of action and rewards is unnatural here, especially given that the adversary does not learn a policy (mapping states to actions) but rather actions only when needed.

• The last paragraph of Section 3 mentions some specific behavior of the algorithm in the first $d$ (undefined before use) steps, but does not explain/justify this algorithm design, which currently seems to be arbitrary.

• Several notation issues: in Section 3.2 the summations are indexed by $i$, but the summands are indexed by $j$ and not $i$, in Section 5.1, $s(i)$ is defined for all $i$ but not $s_o(i)$ and they seem to stand for the same quantity.

• I found Theorem 1 hard to parse, and wonder what are the takeaways from it. Specifically, the use of mathematical quantifiers is strange (and $\exists$ is denoted as $\ni$), and I do not really know how to interpret the result. For example, (3) is an inequality lower bounding a non-negative quantity by a quantity that could be negative (if some of the cosines are negative).

3. The experiments are insufficient.

• The defenses used are not designed for the non-iid setting, which makes the comparison ill-posed. There are methods (e.g., NNM [1], Bucketing [2]) specifically designed for this purpose and should be included to enable a full experimental validation.

• Other black-box (or grey-box) attacks should be included for completeness, e.g., the attacks of Baruch et al. (2019) and Li et al. (2022).

• Minor comment: the choices of the Dirichlet parameter $\alpha$ are a little strange, it is typical to do $0.1, 1, 10$.

References:

[1] Allouah et al., Fixing by Mixing: A Recipe for Optimal Byzantine ML under Heterogeneity, AISTATS 2023.

[2] Karimireddy et al., Byzantine-Robust Learning on Heterogeneous Datasets via Bucketing, ICLR 2022.

1. The writing of this paper should be further polished. (a) Typos: MINST-> MNIST; (b) The relationship between the ``Discussion and Analysis'' section and other sections (especially the proposed method) in this submission is not clear.
2. Some important references are missed in the submission, such as [1][2]. The settings and proposed method in [1] are closely related to UA-RL, and the authors can provide more discussions and highlight the advances of UA-RL.
3. The experiments are conducted on three similar datasets, MNIST, Fashion-MNIST, EMNIST. More diverse datasets can be considered to make the experiments more convincing.
4. Some experimental results in Table 1 are confusing. For example, (a) Why Krum (w/o attack) performs much worse than other baselines, and even worse than Krum (w/ attack). ? e.g., 10%+ v.s. 50%+ when $\alpha=0.2$; 40% v.s. 70%+ when $\alpha=1.0$. (b) Some naive baselines, such as fixed reverse gradient (FR) and untargeted label flipping (UT), seem to perform better than UA-RL in 11/30 cases in Table 1.

References:
[1] Manipulating the Byzantine: Optimizing Model Poisoning Attacks and Defenses for Federated Learning. In NDSS, 2021.
[2] Learning to Attack Federated Learning: A Model-based Reinforcement Learning Attack Framework. In NeurIPS, 2022.