FLCert: Provably Secure Federated Learning Against Poisoning Attacks

Xiaoyu Cao, Zaixi Zhang, Jinyuan Jia, Neil Zhenqiang Gong

Federated Learning (FL) has become the go-to paradigm for training machine learning models on private, distributed data—think of Google’s Gboard learning your typing habits without ever seeing your actual messages. However, this distributed nature is a double-edged sword. Because the central server doesn't see the raw data, it’s remarkably easy for a few "poisonous" clients to sabotage the global model by sending malicious updates.

While many "Byzantine-robust" defenses exist, they often fall into a cat-and-mouse game: a new defense is proposed, and a more clever attack eventually breaks it. In their paper, "FLCert: Provably Secure Federated Learning against Poisoning Attacks," researchers Xiaoyu Cao and colleagues propose a way to break this cycle by providing the first FL framework with provable security guarantees.

TL;DR

FLCert is the first federated learning framework that is provably secure against poisoning attacks. By dividing clients into groups and using an ensemble-based majority vote, it guarantees that a predicted label will remain unchanged as long as the number of malicious clients stays below a calculated "certified security level."

What Problem Does This Paper Address?

In a standard FL setup, a single global model is updated by all clients. An attacker can compromise a small fraction of these clients to perform poisoning attacks. These can be untargeted (aiming to destroy the model's overall accuracy) or targeted (making the model misclassify specific inputs, like a "backdoor" that identifies a car as a bird if a specific sticker is present).

Existing defenses (like Krum or Trimmed-mean) try to filter out statistical outliers. However, these are empirical defenses; they don't offer a mathematical guarantee. If an attacker is clever enough to make their malicious updates look "normal," they can still corrupt the model. FLCert addresses this by moving away from the "one-global-model" paradigm toward a provable ensemble approach.

Methods

The core idea of FLCert is deceptively simple: Divide and Conquer.

  1. Grouping: Instead of training one model with everyone, the server divides $n$ clients into $N$ groups.
  2. Training: A separate global model is trained for each group using any standard FL algorithm (like FedAvg).
  3. Inference (The Ensemble): To classify a new input, the server asks all $N$ models to vote. The final prediction is the majority winner.

The authors propose two variants for grouping:

  • FLCert-P (Probabilistic): Clients are randomly sampled into groups. This provides a probabilistic security guarantee.
  • FLCert-D (Deterministic): Clients are assigned to disjoint groups based on a hash of their unique IDs. This provides a deterministic security guarantee.

The "Magic" of the Certified Security Level ($m^*$): The authors derive a mathematical threshold ($m^*$). If the number of malicious clients in the entire system is less than or equal to $m^*$, the majority vote is guaranteed to stay the same, regardless of how the malicious clients behave or what attack they use. Crucially, they prove that this security level is tight—meaning you cannot derive a higher guarantee without making more assumptions about the underlying training process.

Datasets

The researchers evaluated FLCert across five diverse datasets to prove its generality:

  • MNIST-0.1 & MNIST-0.5: Handwritten digits, distributed with varying degrees of "Non-IIDness" (data heterogeneity).
  • CIFAR-10: A standard image classification benchmark.
  • HAR (Human Activity Recognition): Real-world sensor data from 30 smartphone users.
  • Reddit: A massive next-word prediction dataset involving 80,000 users.

Key Insights and Ideas

  • Isolation is the Best Defense: By confining a client to a specific group (or a small number of groups), you limit the "blast radius" of a malicious actor. If a malicious client only affects 1 out of 500 models, the majority vote remains robust.
  • The Accuracy-Security Trade-off: There is a fundamental tension here. Increasing the number of groups ($N$) makes the system more secure (each group is smaller, so a malicious client affects a smaller percentage of the total vote), but it can decrease the accuracy of individual models because they have less data to train on.
  • Algorithm Agnostic: FLCert doesn't require a specific FL algorithm. You can use FedAvg, Krum, or any other method as the "base" learner within the groups.

Key Results

  • Provable Robustness: On MNIST, FLCert-D (with $N=500$ groups and 1,000 total clients) achieved a certified accuracy of 81% even when 100 clients were malicious. In contrast, standard "robust" methods like Krum or FedAvg drop to 0% certified accuracy the moment a single client is allowed to be arbitrarily malicious.
  • Efficiency: While training $N$ models sounds expensive, the authors show that because each model is trained on a smaller subset of data, they often converge much faster. In some cases, the total communication cost for clients is no higher than standard single-model FL.
  • Tightness: The theoretical proofs confirm that the security levels provided are the best possible for this ensemble architecture.

Limitations and Future Work

  • Storage and Inference Overhead: The server must store $N$ separate models and query all of them during inference. While the authors suggest model compression and parallelization as fixes, this remains a hurdle for resource-constrained environments.
  • Prior Knowledge: The current framework doesn't leverage any prior knowledge about the specific learning task or the base FL algorithm. The authors suggest that incorporating such knowledge could lead to even higher certified security levels.
  • Small Dataset Sensitivity: On very small datasets or tasks with high complexity, splitting the data into too many groups might degrade the accuracy of the individual base models too much to be practical.

Summary updated

Abstract

Due to its distributed nature, federated learning is vulnerable to poisoning attacks, in which malicious clients poison the training process via manipulating their local training data and/or local model updates sent to the cloud server, such that the poisoned global model misclassifies many indiscriminate test inputs or attacker-chosen ones. Existing defenses mainly leverage Byzantine-robust federated learning methods or detect malicious clients. However, these defenses do not have provable security guarantees against poisoning attacks and may be vulnerable to more advanced attacks. In this work, we aim to bridge the gap by proposing FLCert, an ensemble federated learning framework, that is provably secure against poisoning attacks with a bounded number of malicious clients. Our key idea is to divide the clients into groups, learn a global model for each group of clients using any existing federated learning method, and take a majority vote among the global models to classify a test input. Specifically, we consider two methods to group the clients and propose two variants of FLCert correspondingly, i.e., FLCert-P that randomly samples clients in each group, and FLCert-D that divides clients to disjoint groups deterministically. Our extensive experiments on multiple datasets show that the label predicted by our FLCert for a test input is provably unaffected by a bounded number of malicious clients, no matter what poisoning attacks they use.
BibTeX
@article{cao2022flcert,
  author = {Xiaoyu Cao and Zaixi Zhang and Jinyuan Jia and Neil Zhenqiang Gong},
  title = {{FLCert: Provably Secure Federated Learning Against Poisoning Attacks}},
  journal = {IEEE Trans. Inf. Forensics Secur.},
  year = {2022},
  url = {https://openreview.net/forum?id=ve9o_Whp4c},
}

Loading related content...

Figure