Small Perturbation¶

Small-perturbation gradient attack.

Reference:: El Mahdi El Mhamdi, Rachid Guerraoui, and Sébastien Rouault. “The Hidden Vulnerability of Distributed Learning in Byzantium.” In Proceedings of the 35th International Conference on Machine Learning (ICML 2018).

The attack exploits the curse of dimensionality: in \(d \gg 1\), two honest gradients naturally disagree by \(\Theta(\sqrt{d})\) in the \(\ell_p\) norm even on a “good” coordinate, so an attacker can shift one coordinate by \(\Omega(\sqrt{d})\) while still looking legitimate to a \(\ell_p\)-norm-based aggregator.

The attack builds a single malicious vector

\[B(\gamma) = \frac{1}{n - f} \sum_{i=1}^{n-f} V_i + \gamma \cdot E\]

from the \(n - f\) honest gradients \(V_1, \dots, V_{n-f}\) and the direction \(E \in \mathbb{R}^d\). It then performs a boundary search for the largest \(\gamma = \gamma_m\) such that the target aggregator still “selects” \(B(\gamma_m)\) — i.e. \(B(\gamma_m)\) is in the aggregator’s input subset. All \(f\) Byzantine workers send the same \(B(\gamma_m)\) vector.

Two directions \(E\) are supported, depending on the target norm \(p\):

finite norm \(p \ge 1\): \(E = e_e\) is a one-hot vector at a single coordinate \(e \in \{1, \dots, d\}\). The default choice \(e = \arg\max_j \operatorname{std}(V_{\cdot,j})\) is the coordinate with the largest honest variance, which maximises \(\gamma_m\).
infinite norm \(p = \infty\): \(E = (1, \dots, 1)\), the all-ones vector. This is required because \(\lim_{p \to +\infty} \sqrt[p]{d} = 1\), so the finite-norm attack loses its bite as \(p\) grows. Modifying non-maximal coordinates does not substantially affect the infinite-norm distance to the honest gradients, so \(B(\gamma)\) stays in the aggregator’s selection set for \(\gamma = \Theta(d)\).

class attacks.small_perturbation.SmallPerturbationAttack[source]¶

Bases: Attack

Small-perturbation attack.

The attack accepts a target aggregator and a target norm, builds the direction \(E\) accordingly, and performs a boundary search for the largest \(\gamma\) such that the aggregator still “selects” \(B(\gamma)\).

The aggregator is asked to “select” \(B(\gamma)\) in the same way as the actual run: the test substitutes a placeholder for \(B(\gamma)\) (the honest mean) and checks whether the aggregator’s output changes. This works uniformly for any stateless aggregator class.

classmethod generate(honest_gradients: Sequence[Tensor] | Tensor, /, out: Tensor | None = None, *, f: int, aggregator: type[Aggregator], n: int, p: int | float = 2, coordinate: int | str | None = None, aggregator_kwargs: dict[str, Any] | None = None, gamma: float | None = None, gamma_max: float = 1000000.0, gamma_init: float = 1.0, tol: float = 0.001, atol: float = 1e-06, rtol: float = 1e-05, **specialized: Any) → Tensor[source]¶

Generate Byzantine gradients.

Parameters:

honest_gradients – Sequence of \(h\) gradient vectors, one per honest worker, each of shape \((d,)\). May also be a 2-D tensor of shape \((n-f, d)\).
out – Optional pre-allocated tensor of shape \((f, d)\) to write the result into and return.
f – Number of Byzantine gradients to generate. Must equal the configured \(f\) (the attack is defined for a fixed worker configuration).
aggregator – Target aggregator class.
n – Total number of workers.
p – Target norm.
coordinate – Index of the poisoned coordinate.
aggregator_kwargs – Extra keyword arguments for the aggregator.
gamma – If provided, use this exact value for \(\gamma\) instead of running the boundary search. This is useful when the caller knows the desired perturbation magnitude or wants to compare aggregators at a fixed attack strength.
gamma_max – Upper bound on the search for \(\gamma_m\).
gamma_init – Initial step used during the exponential search.
tol – Tolerance of the binary refinement.
atol – Absolute tolerance for the aggregator selection test (see _is_selected()).
rtol – Relative tolerance for the aggregator selection test.
**specialized – Additional keyword arguments.

Returns:

Byzantine gradients of shape `` (f, d)
``B (gamma_m)

Raises:

ValueError – If the input shape is invalid or \(f\) does not match.
TypeError – If the input is not floating-point.