On Provable Backdoor Defense in Collaborative Learning

Ximing Qiao, Yuhua Bai, Siping Hu, Ang Li, Yiran Chen, Hai LiarXiv 2021 · arXiv

Abstract

Collaborative learning environments, such as Federated Learning, are increasingly susceptible to backdoor attacks where malicious actors inject triggers into training data to manipulate model behavior. Traditional Byzantine-tolerant defenses often struggle with these stealthy attacks, particularly in non-IID data distributions. This paper proposes a novel framework that treats subset aggregation as a coding theory problem. By designing specific code matrices for user-to-model assignments, the authors introduce Backdoor Detection, Correction, and Tracking Codes (BDC, BCC, BTC). These codes provide provable guarantees for identifying and mitigating attacks while significantly improving data utilization over existing majority-vote baselines.

Introduction

Collaborative learning allows multiple users to jointly train a global model without sharing raw data. However, this open architecture introduces a significant "attack surface." While many algorithms can handle "Byzantine" noise (randomly corrupted data), backdoor attacks present a unique challenge. In these attacks, a model performs correctly on standard inputs but executes a malicious action when presented with a specific "trigger." Because the model appears healthy during standard validation, these backdoors are difficult to detect. Existing defenses often require extreme redundancy or discard significant amounts of data, leading to poor performance in heterogeneous (non-IID) environments.

Methodology: A Coding Theory Approach

The core innovation of this work is the conceptualization of subset aggregation—training an ensemble of models on different user subsets—through the lens of Coding Theory.

Overview of the collaborative learning framework and the role of the code matrix H.

The Code Matrix ($H$)

The assignment of $n$ users to $m$ models is represented as a binary matrix $H \in \{0, 1\}^{m \times n}$. If $H_{ij} = 1$, model $i$ is trained on data from user $j$. An attacker injecting a backdoor is essentially "encoding" a malicious signal into the ensemble's output. Consequently, defending against the attack becomes a "decoding" problem.

Levels of Defense

The framework defines three hierarchical levels of protection:

  1. Backdoor Detection Codes (BDC): Designed to identify if an attack has occurred within the ensemble.
  2. Backdoor Correction Codes (BCC): Capable of identifying the attack and recovering the correct label for a given input.
  3. Backdoor Tracking Codes (BTC): The most advanced level, which recovers the correct label and uniquely identifies the specific malicious user(s).
Visual representation of different BCC and BTC code constructions.

Probabilistic Decoding

Unlike simple majority-vote mechanisms, the authors propose a sophisticated decoder. This decoder utilizes confusion matrices and probability maximization to distinguish between malicious backdoors and natural misclassifications caused by "noise" in non-IID data.

Experimental Evaluation

The framework was evaluated on the MNIST and CIFAR-10 datasets. To simulate real-world heterogeneity, the researchers used a Dirichlet distribution (parameter $\alpha$) to create non-IID variants where each user possesses a highly skewed subset of the data.

Key Results

  • Superior Accuracy in Non-IID Settings: On CIFAR-10 with $\alpha=0.1$, the proposed BCC codes maintained high accuracy as the number of attackers increased, whereas standard majority-vote methods failed.
  • Robustness: The BCC(4, 4, 12) configuration (defending against 4 attackers with 12 users) remained stable even under significant adversarial presence.
  • Localization Precision: BTC codes demonstrated a high True Positive Rate (near 1.0 on MNIST) for pinpointing the exact location of single attackers, allowing for their removal from the network.

Discussion and Insights

The research highlights a fundamental "trilemma" in collaborative learning: the trade-off between data utilization, robustness (number of tolerable attackers), and computational cost (number of models). While it is mathematically impossible to maximize all three simultaneously, this framework breaks the "majority vote bound," proving that strategic subset overlap allows for higher data utilization per model than previously thought possible.

Limitations and Future Work

The primary drawback is the computational overhead of training an ensemble. As the required robustness increases, the number of models needed can grow significantly. Future research may focus on using "weaker," less expensive models within the ensemble or employing partial computation sharing to reduce the training burden.

Conclusion

By bridging coding theory and machine learning, this work provides a rigorous foundation for provable backdoor defense. The ability to not only correct malicious outputs but also track attackers marks a significant step forward in securing collaborative learning systems against sophisticated adversarial threats.

Summary updated

Abstract

As collaborative learning allows joint training of a model using multiple sources of data, the security problem has been a central concern. Malicious users can upload poisoned data to prevent the model's convergence or inject hidden backdoors. The so-called backdoor attacks are especially difficult to detect since the model behaves normally on standard test data but gives wrong outputs when triggered by certain backdoor keys. Although Byzantine-tolerant training algorithms provide convergence guarantee, provable defense against backdoor attacks remains largely unsolved. Methods based on randomized smoothing can only correct a small number of corrupted pixels or labels; methods based on subset aggregation cause a severe drop in classification accuracy due to low data utilization. We propose a novel framework that generalizes existing subset aggregation methods. The framework shows that the subset selection process, a deciding factor for subset aggregation methods, can be viewed as a code design problem. We derive the theoretical bound of data utilization ratio and provide optimal code construction. Experiments on non-IID versions of MNIST and CIFAR-10 show that our method with optimal codes significantly outperforms baselines using non-overlapping partition and random selection. Additionally, integration with existing coding theory results shows that special codes can track the location of the attackers. Such capability provides new countermeasures to backdoor attacks.
BibTeX
@misc{qiao2021provable,
  author = {Ximing Qiao and Yuhua Bai and Siping Hu and Ang Li and Yiran Chen and Hai Li},
  title = {{On Provable Backdoor Defense in Collaborative Learning}},
  year = {2021},
  eprint = {2101.08177},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2101.08177},
}
Figure