FABA: An Algorithm for Fast Aggregation against Byzantine Attacks in Distributed Neural Networks

Qi Xia, Zeyi Tao, Zijiang Hao, Qun LiIJCAI 2019 · DOI

TL;DR

This paper introduces FABA, a novel algorithm designed to make distributed neural network training robust against Byzantine attacks. FABA efficiently identifies and removes malicious "outlier" gradients, allowing honest gradients to drive convergence, achieving performance comparable to non-attacked training and outperforming existing methods in speed and accuracy.

What Problem Does This Paper Address?

Training massive deep neural networks often requires distributing the workload across multiple machines. This distributed approach, while efficient, is vulnerable to Byzantine attacks. In such attacks, a subset of participating workers (Byzantine workers) can send deliberately corrupted or "poisonous" gradients. These malicious gradients can destabilize the training process, leading to convergence to suboptimal solutions or complete failure. Existing methods like Krum, which select a single gradient, or median-based approaches, often discard too much valuable information from honest workers, hindering performance and efficiency. This paper aims to bridge this gap by proposing an algorithm that effectively filters out malicious gradients while retaining as much useful information from honest workers as possible.

Methods

The core of FABA (Fast Aggregation against Byzantine Attacks) lies in its parameter server's aggregation strategy. Instead of simply averaging all gradients or picking just one, FABA iteratively removes the gradient that is furthest from the current average of all uploaded gradients. This process is repeated a number of times determined by the assumed proportion of Byzantine workers ($\alpha$). The intuition is that honest gradients, due to the Central Limit Theorem and large batch sizes, tend to cluster together, while Byzantine gradients are designed to be outliers. By repeatedly removing the most extreme outliers, FABA aims to isolate the true gradient direction. The algorithm is proven to converge, with theoretical guarantees that the aggregated gradients remain close to the true gradients, even in the presence of Byzantine workers.

Datasets

The paper evaluates FABA on the following datasets:

  • MNIST: Used for training LeNet.
  • CIFAR-10: Used for training VGG-16, ResNet-18, ResNet-34, and ResNet-50.

Key Insights and Ideas

  • Outlier Removal is Key: The fundamental insight is that Byzantine gradients are likely to be outliers relative to the cluster of honest gradients. FABA leverages this by iteratively removing the most distant gradients.
  • Retaining More Information: Unlike methods that discard most gradients (like Krum selecting only one), FABA retains a larger proportion of honest gradients, leading to faster convergence and better accuracy.
  • Adaptive to Byzantine Proportion: The number of gradients removed is directly tied to the assumed proportion of Byzantine workers ($\alpha$), making the algorithm adaptable to different attack scenarios.
  • Theoretical Guarantees: The paper provides mathematical proofs for the convergence and correctness of FABA, ensuring that the aggregated gradients are close to the true gradients.

Key Results

  • MNIST: FABA achieved significantly faster convergence than Krum on a 32-worker setup with a 30% Byzantine rate. While Krum was unstable, FABA showed stable loss reduction, comparable to a non-Byzantine setting.
  • CIFAR-10: On various network architectures (VGG-16, ResNet-18, etc.) with a 30% Byzantine rate, FABA achieved comparable accuracy to non-Byzantine training and significantly outperformed Krum. It also demonstrated a much more stable loss curve than Krum.
  • Efficiency: FABA's ability to retain more gradients leads to faster convergence, reducing training time compared to methods that discard more information.

Limitations and Future Work

  • Assumption on Byzantine Proportion: FABA's performance relies on an accurate estimate of the Byzantine worker proportion ($\alpha$). The paper suggests that the number of iterations for outlier removal can be adaptively adjusted to test different estimates, offering flexibility.
  • Dataset Distribution Assumption: The theoretical convergence proof relies on the assumption that honest gradients are close to each other, which is facilitated by uniformly distributed datasets and large batch sizes. The paper acknowledges that this assumption might not hold in scenarios with biased or secret datasets, leaving this for future work.
  • Future Work: The authors suggest exploring FABA in more complex Byzantine settings and investigating its performance with different dataset distributions.

Summary updated

BibTeX
@inproceedings{xia2019faba,
  author = {Qi Xia and Zeyi Tao and Zijiang Hao and Qun Li},
  title = {{FABA: An Algorithm for Fast Aggregation against Byzantine Attacks in Distributed Neural Networks}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/670},
}
Figure