PaperlayerView exact revision on arXiv

Source-linked AI summary

Provably Secure Federated Learning against Malicious Clients

Xiaoyu Cao, Jinyuan Jia, Neil Zhenqiang Gong

arXiv:2102.01854v4cs.CRcs.DCcs.LG

TL;DR

Federated learning lacks a provable guarantee that malicious clients cannot alter a testing example’s predicted label, despite Byzantine-robust defenses. The paper addresses this gap with ensemble federated learning, training models on random client subsets and majority-voting their predictions. It proves a tight bounded-client security guarantee and reports 88% certified accuracy on MNIST with 20 of 1,000 clients malicious.

  • Problem

    Existing defenses against malicious clients cannot provably guarantee that a testing example’s predicted label is unaffected.

  • Method

    Ensemble federated learning applies any base algorithm to randomly selected client subsets and predicts by majority vote across the resulting global models.

  • Results

    88% certified accuracy is achieved on MNIST with 20 of 1,000 clients malicious, and the certified security bound is tight.

  • Takeaways & Limitations

    The method effectively defends against malicious clients with provable security guarantees on MNIST and Human Activity Recognition datasets.

  • Takeaways & Limitations

    The practical probability bounds are estimated with a Monte Carlo procedure rather than deterministically.

Abstract

from arXiv · show

Federated learning enables clients to collaboratively learn a shared global model without sharing their local training data with a cloud server. However, malicious clients can corrupt the global model to predict incorrect labels for testing examples. Existing defenses against malicious clients leverage Byzantine-robust federated learning methods. However, these methods cannot provably guarantee that the predicted label for a testing example is not affected by malicious clients. We bridge this gap via ensemble federated learning. In particular, given any base federated learning algorithm, we use the algorithm to learn multiple global models, each of which is learnt using a randomly selected subset of clients. When predicting the label of a testing example, we take majority vote among the global models. We show that our ensemble federated learning with any base federated learning algorithm is provably secure against malicious clients. Specifically, the label predicted by our ensemble global model for a testing example is provably not affected by a bounded number of malicious clients. Moreover, we show that our derived bound is tight. We evaluate our method on MNIST and Human Activity Recognition datasets. For instance, our method can achieve a certified accuracy of 88% on MNIST when 20 out of 1,000 clients are malicious.

Introduction

Federated learning protects clients’ local training data but remains vulnerable to malicious clients that corrupt a single global model. The paper proposes ensemble federated learning, which trains models on random client subsets and uses majority voting to obtain provable, tight security guarantees.

  • Motivation: Malicious clients can tamper with local data or model updates, causing the global model to misclassify normal or attacker-chosen testing examples.A cited example relabels striped cars as birds and scales up malicious model updates.
  • Motivation: Existing Byzantine-robust methods mitigate outlier updates but cannot provably guarantee that malicious clients do not affect a testing example’s predicted label.These methods bound parameter differences rather than guaranteeing prediction stability.
  • Ensemble Federated Learning: Ensemble federated learning trains one global model for each uniformly random k-client subsample using any base federated learning algorithm, then predicts by majority vote.The method can train models across all client subsamples, while practical computation uses Monte Carlo estimation.
  • Theory: The ensemble prediction is provably unchanged when malicious clients do not exceed a testing-example-specific certified security level, and the derived level is tight.The tightness claim holds without assumptions on the base federated learning algorithm.
  • Evaluation: 88% certified accuracy is achieved on MNIST with N = 500 and k = 10 when 20 of 1,000 clients are malicious.Certified accuracy is a lower bound on testing accuracy guaranteed despite arbitrary malicious tampering.

Background on Federated Learning

Federated learning iteratively coordinates clients and a cloud server to learn a global model without sharing local training data. Base algorithms differ primarily in how the server aggregates client updates.

  • Single-global-model Federated Learning: A single-global-model federated learning system has the server maintain a global model while each client maintains a local model.The system repeatedly communicates between the server and clients.
  • Base Federated Learning Algorithms: A base federated learning algorithm learns one global model for any given client subset, with aggregation rules defining how model updates are combined.FedAvg averages updates weighted by local training-dataset sizes.

Our Ensemble Federated Learning

Ensemble federated learning trains global models on randomly sampled client subsamples and predicts by majority vote. Its certified security level depends on label-probability bounds and is provably tight under the stated assumptions.

  • Method: The method trains multiple global models using a base federated learning algorithm on client subsamples sampled uniformly without replacement.Each subsample contains k clients drawn from n clients.
  • Method: The ensemble assigns each label a probability equal to the fraction of global models predicting that label, then selects the label with the largest probability.These probabilities also represent predictions from a random k-client subsample.
  • Security guarantee: When malicious clients are bounded, the majority of subsample-trained models remain based on normal clients, preserving the ensemble prediction.The security guarantee targets agreement between predictions with and without malicious clients.
  • Certified security level: The certified security level increases with the gap between the largest and second-largest label probabilities, py − pz.The bound can be computed using exact probabilities when feasible or probability bounds when enumerating all subsamples is impractical.
  • Certified security level: Theorem 1 guarantees the prediction for x under at most m* malicious clients, using a lower bound on py and an upper bound on pz.The guarantee applies to any base federated learning algorithm satisfying the stated probability conditions.
  • Tightness: The derived certified security level is tight: without assumptions on the base algorithm, more than m* malicious clients can change the prediction or create ties.The tightness result applies for probability bounds satisfying py + pz ≤ 1.

Computing the Certified Security Level

The method estimates predicted labels and certified security levels by training global models on random client subsamples and analyzing their label frequencies. It provides probabilistic guarantees, while exact probabilities yield deterministic security levels and the derived bound is tight.

  • Prediction and probability estimation: For each testing example, the algorithm trains N global models on uniformly sampled client subsamples and predicts the most frequent label.The sampled models are trained with the base federated learning algorithm.
  • Prediction and probability estimation: The algorithm counts model predictions, selects the largest count as the predicted label, and estimates lower and upper bounds for the top two label probabilities.The second probability upper bound can be estimated as 1 − p̂yt.
  • Computational efficiency: For multiple testing examples, splitting α across examples and applying Bonferroni correction enables simultaneous confidence level 1 − α while training N models in total.This avoids training a separate set of N models for every testing example.
  • Security-level computation: SEARCHLEVEL finds the largest certified security level m satisfying the theorem’s condition from the estimated probability bounds.The procedure can increase m iteratively from zero until the condition is no longer satisfied.
  • Probabilistic guarantees: The outputted certified security level may be incorrect when the estimated lower probability bound is incorrect.This arises because the Clopper–Pearson estimate can exceed the true lower bound.
  • Probabilistic guarantees: The probability of an incorrect certified security level for at least one testing example is bounded by α, and exact probability computation makes the security level deterministic.The derived certified security level is tight when no assumptions are imposed on the base federated learning algorithm.

Experiments

Experiments evaluate ensemble FedAvg on MNIST and Human Activity Recognition using certified accuracy, varying ensemble and data-distribution parameters. Compared with single-global-model FedAvg, ensemble FedAvg trades some accuracy with no malicious clients for certified robustness against malicious clients.

  • Datasets and models: The evaluation uses MNIST as a simulated federated-learning scenario and Human Activity Recognition as a real-world scenario with users as clients.MNIST considers 1,000 clients; HAR contains 30 users, six activities, 10,299 examples, and 561 features.
  • Datasets and models: FedAvg is the base algorithm, using a CNN for MNIST and a two-hidden-layer DNN for HAR.The HAR hidden layers each contain 256 ReLU neurons.
  • Evaluation metric: Certified accuracy measures the guaranteed test accuracy when at most m clients are malicious, regardless of their attacks.CA@0 equals standard accuracy when no clients are malicious.
  • Parameter settings: The default settings are N = 500, α = 0.001, k = 10 for MNIST, and k = 2 for HAR.For HAR, k = 2 permits deterministic certified accuracy under the default setting; k = 4 is used when varying N or α.
  • FedAvg comparison: With no malicious clients, single-global-model FedAvg is more accurate than ensemble FedAvg, but single-global-model FedAvg has 0 certified accuracy with one malicious client.Ensemble FedAvg reaches 0 certified accuracy only when up to 61 malicious clients are present in the reported comparison.

Related Work

Related work spans accuracy and convergence, communication efficiency, privacy, and federated-learning security. Security studies document malicious-client attacks and Byzantine-robust defenses, while the paper distinguishes its threat model from data-poisoning defenses.

  • Federated learning research: Federated-learning research has studied more accurate global models and convergence properties, including model construction through neural-network element matching.FedMA is cited as an example of matching and averaging hidden elements with similar feature-extraction signatures.
  • Federated learning research: Other work improves client-server communication efficiency through sparsification, quantization, or encoding of model updates.
  • Security: Security studies show that malicious clients can significantly downgrade global-model accuracy, while Byzantine-robust rules mitigate statistical outliers in model updates.Examples include Krum, trimmed mean, and coordinate-wise median.
  • Security: Ensemble defenses for data poisoning do not suffice when malicious clients can manipulate both local training data and model updates.The distinction is between poisoned training examples and malicious clients controlling client-side behavior and updates.

Conclusion

The paper proposes ensemble federated learning with a tight provable security guarantee against malicious clients and evaluates its effectiveness on two datasets. It also identifies deterministic probability estimation and base-algorithm structure as future directions.

  • Conclusion: The paper proposes ensemble federated learning and derives its tight provable security guarantee against malicious clients.
  • Conclusion: Empirical results on two datasets show that ensemble federated learning can defend against malicious clients with provable security guarantees.
  • Conclusion: Future work includes deterministic estimation of probability bounds and exploiting the internal structure of a base federated-learning algorithm.These directions are presented as ways to further improve provable security guarantees.

Proof of Theorem 1

The proof compares subsample spaces associated with client sets and decomposes label probabilities according to their overlap. It then bounds the vote-probability difference to show that the predicted label remains y.

  • Subsample spaces: The proof defines subsamples of k clients and the spaces of all such subsamples for the relevant client sets.It introduces OC, O′C, and their overlap Oo, illustrated in Figure 7.
  • Prediction distributions: Random variables X and Y represent uniformly sampled subsamples from the client sets, enabling comparison of their induced prediction distributions.The base algorithm A maps a client set and testing example x to a predicted label.
  • Probability decomposition: The proof decomposes the probability py of predicting y into contributions from the overlap Oo and its complement.The same decomposition is applied to competing labels i ≠ y.
  • Probability comparison: The overlap-conditioned prediction probabilities are equated across the compared client-set distributions, and the resulting expressions are subtracted.
  • Conclusion: Using the probability bound and the integrality of label-probability counts, the proof concludes that h(C′, x) = y.

Proof of Theorem 2

The proof establishes Theorem 2 by constructing a base algorithm A* across four cases. In every case, the construction yields a counterexample showing the certified security level is tight.

  • Conclusion: The constructed algorithm A* demonstrates that the certified security bound cannot be increased.The final argument covers all possible cases and concludes that Theorem 2 holds tightly.
  • Case analysis: The proof considers four cases and constructs A* separately in each case.Figure 8 illustrates the corresponding set configurations.
  • Case analysis: Each construction satisfies the required probability conditions while producing an incorrect prediction or a tie.The proof verifies this pattern through the case-specific constructions and resulting predictions.

Proof of Theorem 3

The proof uses Clopper–Pearson confidence bounds to control the estimated label probabilities for each testing example. If the algorithm does not abstain, the probability of returning an incorrect certified security level is at most α.

  • Confidence bound: Clopper–Pearson bounds provide simultaneous probability guarantees for the estimated top and competing label probabilities.For each testing example, the stated bound holds with confidence at least 1 − α.
  • Guarantee: If Algorithm 2 does not abstain, the probability that it returns an incorrect certified security level is at most α.The result applies specifically to non-abstaining testing examples.
  • Guarantee: The proof combines the preceding bounds using Boole’s inequality.This yields the final stated guarantee.
Loading 2102.01854v4…