Breaking BAD: Heterogeneous Byzantine-Robust Federated Learning via Gather and Scatter Scores

Byzantine-robust Federated Learning (FL) designs aggregation rules that mitigate the impact of malicious clients. When the data across honest clients are heterogeneous, honest model updates are inherently scattered. This dispersion can be exploited by Byzantine adversaries who may collude to concentrate their updates, thereby circumventing state-of-the-art robust aggregation methods and causing a Byzantine Adversarial Disruption (BAD) of the training process. We propose a novel Byzantine-robust FL scheme based on gather and scatter scores. Our scoring technique captures concentration among Byzantine clients and prevents catastrophic failure under SotA attacks. Through numerical experiments on FEMNIST, Shakespeare, and CIFAR-10 datasets, we demonstrate that the proposed defense maintains high model accuracy, even in realistic FL scenarios. Furthermore, we establish theoretical convergence guarantees for our method.