Fall of Empires: Breaking Byzantine-tolerant SGD by Inner Product Manipulation

Cong Xie; Sanmi Koyejo; Indranil Gupta

Source-linked AI summary

Fall of Empires: Breaking Byzantine-tolerant SGD by Inner Product Manipulation

Cong Xie, Sanmi Koyejo, Indranil Gupta

arXiv:1903.03936v1Mar 10, 2019cs.LGcs.CRcs.DCstat.ML

TL;DR

Byzantine workers can send arbitrary gradients that undermine robust aggregation in distributed synchronous SGD, while existing distance-based guarantees do not ensure a useful descent direction. The paper introduces inner product manipulation attacks, theoretically and empirically examines coordinate-wise median and Krum, and concludes that Byzantine tolerance should be redefined for this setting.

Problem
Existing Byzantine-tolerant SGD rules bound estimator distance from correct gradients, but the aggregated direction can still have a negative inner product with the true gradient.
Method
The paper defines inner product manipulation attacks, derives attack strategies against coordinate-wise median and Krum, and evaluates them through theoretical analysis and experiments.
Results
The analysis and experiments show that coordinate-wise median and Krum can be broken by designed Byzantine gradients, including attacks with large or small opposite-direction magnitudes.
Takeaways & Limitations
The paper’s revised definition of Byzantine tolerance is intended to support the design and evaluation of stronger defenses for distributed synchronous SGD.
Takeaways & Limitations
Krum’s convergence assumption cσ < ∥g∥ is not guaranteed near critical points when gradient variance is non-zero.

Abstract

from arXiv · show

Recently, new defense techniques have been developed to tolerate Byzantine failures for distributed machine learning. The Byzantine model captures workers that behave arbitrarily, including malicious and compromised workers. In this paper, we break two prevailing Byzantine-tolerant techniques. Specifically we show robust aggregation methods for synchronous SGD -- coordinate-wise median and Krum -- can be broken using new attack strategies based on inner product manipulation. We prove our results theoretically, as well as show empirical validation.

1 INTRODUCTION

The paper argues that Byzantine-tolerant synchronous SGD can fail when attacks manipulate the aggregated gradient’s direction rather than merely its distance from the correct gradient. It introduces inner product manipulation attacks, breaks coordinate-wise median and Krum theoretically and empirically, and motivates a revised definition of Byzantine tolerance.

Threat model: Byzantine workers can behave arbitrarily, conspire, and exploit system information to send adversarial gradients that cause sub-optimal convergence or divergence.Their omniscience can make malicious gradients resemble correct gradients in variance and magnitude.
Attack principle: For gradient descent to progress, the aggregated vector must have a non-negative inner product with the true gradient.An attack that makes this inner product negative can reverse the intended descent direction.
Attack principle: Bounded distance from the correct mean is insufficient protection because Byzantine values can manipulate the aggregated vector’s inner product to become negative.The paper gives coordinate-wise median as an example when Byzantine values lie opposite the true gradient.
Findings: Inner product manipulation attacks break coordinate-wise median with large opposite-direction gradients and Krum with small opposite-direction gradients.The paper validates these mechanisms through theoretical analysis and empirical results.
Implication: The authors propose revising Byzantine tolerance for distributed synchronous SGD and provide a new definition for evaluating robust aggregation algorithms.They argue that the revised definition can guide the design of better defense techniques.

2 RELATED WORK

Related work develops Byzantine-tolerant aggregation and attacks in distributed or federated learning. The paper focuses on coordinate-wise median and Krum as representative robust aggregation rules for distributed synchronous SGD.

Robust aggregation: Coordinate-wise median generalizes the scalar median to high-dimensional gradients, and prior work studies its statistical error rates in distributed SGD.It is presented as a robust-statistical approach to Byzantine tolerance.
Robust aggregation: Krum selects the candidate gradient with the smallest sum of squared Euclidean distances to the other candidates.Unlike coordinate-wise median, Krum is not based on robust statistics.
Other defenses: Bulyan is built on Krum and may share its flaws, whereas DRACO uses coding theory and differs from the other Byzantine-tolerant SGD algorithms.These methods show that Byzantine robustness has multiple aggregation and coding-theoretic approaches.
Attacks: Prior research also studies attacks using adversarial training data, federated-learning attacks, and adversarial gradients from Byzantine workers.This paper specifically targets distributed synchronous SGD with malicious gradients.

3 PRELIMINARIES

This section introduces distributed synchronous SGD with robust aggregation and the Byzantine threat model, in which some workers may send arbitrary gradients, including colluding or changing faulty workers.

3 PRELIMINARIES: The section presents distributed synchronous SGD with robust aggregation as the paper’s setting and summarizes its notation and algorithmic procedure.
3.1 STOCHASTIC GRADIENT DESCENT: The objective is F(x) = E_z∼D[f(x; z)], assumed differentiable with at least one minimizer x* satisfying ∇F(x*) = 0.
3.1 STOCHASTIC GRADIENT DESCENT: Distributed synchronous SGD uses m workers that sample data, compute local gradients, send them to servers, and update the model through an aggregation rule.The server broadcasts the current model, collects worker gradients, aggregates them, and applies the update.
3.1 STOCHASTIC GRADIENT DESCENT: For honest workers, the transmitted local gradient is an unbiased estimator of the global gradient, while averaging is the standard aggregation rule when all workers are honest.
3.2 THREAT MODEL: Under Byzantine failures, q out of m worker gradients may be replaced by arbitrary values, with 2q < m, and faulty-worker indices may change across iterations.If failures are caused by attackers, the model also permits collusion.

4 DEFENSE TECHNIQUES

This section defines coordinate-wise median and Krum, two robust aggregation rules considered for Byzantine failures in distributed synchronous SGD.

4.1 COORDINATE-WISE MEDIAN: Coordinate-wise median computes the one-dimensional median independently in every vector dimension.For dimension j, it takes the median of the jth coordinates across all worker vectors.
4.2 KRUM: Krum selects an input vector using its distances to the m − q − 2 nearest neighbors among the other worker vectors.The neighbor relation is measured by squared Euclidean distance.
4 DEFENSE TECHNIQUES: The paper abbreviates coordinate-wise median and Krum as Median and Krum for the remainder of the paper.

5 ATTACK TECHNIQUES

The paper revises Byzantine tolerance for synchronous SGD around the requirement that aggregated gradients preserve descent direction, then shows coordinate-wise median and Krum can fail under inner-product manipulation.

5.1 INNER PRODUCT MANIPULATION: When the expected gradient approaches zero while stochastic variance remains non-zero, bounded estimator distance can still permit a negative inner product.The vulnerability becomes more likely near critical points because the gradient magnitude shrinks.
5.1 INNER PRODUCT MANIPULATION: The revised DSSGD-Byzantine tolerance requires the aggregated estimator's inner product with the true gradient to be non-negative, not merely bounded in distance.This condition ensures the loss does not increase in expectation.
5.2 COORDINATE-WISE MEDIAN: The median vulnerability occurs when max_j∈[d] |g_j| < σ √m−q−1, and becomes more likely as SGD approaches a critical point.A one-dimensional example uses correct gradients with mean 0.1 and Byzantine gradients with negative mean −3, producing a median with the opposite sign.
5.2 COORDINATE-WISE MEDIAN: Coordinate-wise median can be driven negative by Byzantine values placed below all correct values when the correct expectation is positive.The attack makes the median equal to the smallest correct order statistic, whose expectation can become negative under the theorem's variance condition.
5.3 KRUM: Krum can select identical Byzantine gradients u = −ε¯v, yielding E[Krum(V ∪ U)] = −εg under sufficient conditions.The theorem considers the worst case m − 2q = 3; the assumptions are sufficient but not necessary for vulnerability.
5.3.1 Toy Example: A one-dimensional Krum example selects −0.1 instead of correct gradients whose mean is 0.2167, while Krum's convergence assumption may fail as ∥g∥ approaches zero.The example uses six correct gradients and three Byzantine gradients, all equal to −0.1.

6 CASE STUDY

The case study evaluates inner product manipulation attacks against Median and Krum on CIFAR-10, showing that both defenses can fail under attack conditions. Median is vulnerable to positive ϵ, while Krum is vulnerable to small positive ϵ, and additional vulnerabilities appear beyond the analyzed worst cases.

6 CASE STUDY: The experiments implement attack strategies for Median and Krum and evaluate them on CIFAR-10 image classification.The study uses a CNN, 25 workers, ten repetitions, test top-1 accuracy, and training cross-entropy loss.
6.2 MEDIAN: Median fails when ϵ > 0, stalls at ϵ = 0, and successfully defends against the attack when ϵ < 0.The tested values include ϵ ∈ {10, 0.1, 0, −10}.
6.3 KRUM: Krum fails when ϵ > 0 is small, while sufficiently large ϵ enables it to defend against the attack.The tested values include ϵ ∈ {0.1, 0.5, 1, 10}.
6.4 DISCUSSION: Both Median and Krum are more vulnerable than expected, with failures occurring in cases beyond the theorems’ worst-case analyses.The authors report additional failure cases for both aggregation rules.
6.4 DISCUSSION: Median performs badly even at ϵ = 0 because small ϵ can enlarge SGD variance, while large negative ϵ successfully defends against the attack.The discussion contrasts these findings with earlier label-flipping experiments, whose Byzantine gradients likely surrounded correct gradients coordinate-wise.
6.4 DISCUSSION: Krum remains vulnerable to small positive ϵ and fails even at ϵ = 1, whereas an earlier large-length opposite-vector attack did not fail.The paper attributes the difference to the earlier attack’s use of a large scaling factor, similar to large ϵ.
6.4 DISCUSSION: The results support revising Byzantine tolerance for distributed synchronous SGD and motivate designing better defenses using the revised definition.The attack strategies were guided by the theoretical analysis.

7 CONCLUSION

The paper proposes a revised definition of Byzantine tolerance for distributed synchronous SGD and uses it to analyze two robust aggregation rules. It combines theoretical and empirical examination with attack construction to expose conditions under which the rules are no longer Byzantine-tolerant.

7 CONCLUSION: The paper proposes a revised definition of Byzantine tolerance for distributed synchronous SGD.
7 CONCLUSION: Using the new definition, the paper theoretically and empirically examines coordinate-wise median and Krum.
7 CONCLUSION: The theoretical analysis guides attack techniques that can make both aggregation rules fail.
7 CONCLUSION: The revised definition is intended to support future development of new defense techniques.