PaperlayerView exact revision on arXiv

Source-linked AI summary

Manipulating SGD with Data Ordering Attacks

Ilia Shumailov, Zakhar Shumaylov, Dmitry Kazhdan, Yiren Zhao, Nicolas Papernot, Murat A. Erdogdu, Ross Anderson

arXiv:2104.09667v2cs.LGcs.AIcs.CRcs.CV

TL;DR

Prior poisoning and backdoor attacks require dataset perturbation, while SGD's uniform-random-sampling assumption is rarely tested or enforced in practice. The paper introduces attacks that reorder batches or data points, or replace batch points, using clean data and labels to manipulate training. On CIFAR10 VGG16, trigger accuracy was 99% for the perturbed-data baseline, 91% ± 13 for whitebox BOB, and 68% ± 19 for blackbox BOB.

  • Problem

    Prior poisoning and backdoor attacks require dataset perturbation, while SGD's uniform-random-sampling assumption is rarely tested or enforced in practice.

    Source: §1 · p. 1

  • Method

    The paper introduces attacks that reorder batches or data points, or replace batch points, using clean data and labels to manipulate training.

    Source: §1 · pp. 1–2

  • Results

    On CIFAR10 VGG16, trigger accuracy was 99% for the perturbed-data baseline, 91% ± 13 for whitebox BOB, and 68% ± 19 for blackbox BOB.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Training-data order can be manipulated to disrupt model integrity or availability without changing the underlying dataset.

    Source: §1 · p. 1, §5 · p. 9

    The blackbox threat model assumes no model access or prior training-data knowledge, whereas the whitebox attacker can access the model and compute its loss.

    Source: §2.1 · p. 2

Abstract

from arXiv · show

Machine learning is vulnerable to a wide variety of attacks. It is now well understood that by changing the underlying data distribution, an adversary can poison the model trained with it or introduce backdoors. In this paper we present a novel class of training-time attacks that require no changes to the underlying dataset or model architecture, but instead only change the order in which data are supplied to the model. In particular, we find that the attacker can either prevent the model from learning, or poison it to learn behaviours specified by the attacker. Furthermore, we find that even a single adversarially-ordered epoch can be enough to slow down model learning, or even to reset all of the learning progress. Indeed, the attacks presented here are not specific to the model or dataset, but rather target the stochastic nature of modern learning procedures. We extensively evaluate our attacks on computer vision and natural language benchmarks to find that the adversary can disrupt model training and even introduce backdoors.

1 Introduction

The paper shows that manipulating training-data order can attack model integrity and availability without changing the dataset. Its attacks target assumptions about stochastic sampling, and evaluations report both training disruption and backdoor insertion.

1 Introduction

  • SGD assumes uniform random sampling, but that randomness is rarely tested or enforced in increasingly complex data-supply pipelines.The paper identifies this gap as an opportunity for covert disruption through adversarial sampling.Source: §1 · p. 1
  • Unlike earlier poisoning and backdoor attacks requiring dataset perturbation [11], these attacks affect behavior by changing data order without modifying data points.The reported effects include reduced accuracy, trigger-controlled predictions, slower training, or reset learning progress.Source: §1 · p. 1
  • BRRR attacks reorder batches or individual data points, or replace batch points; BOP and BOB use clean data and labels to promote attacker-chosen behavior.The paper says BRRR requires no model access or dataset knowledge, and that benign datapoints can control parameter updates.Source: §1 · pp. 1–2
  • The attacks target fundamental assumptions of stochastic learning and are described as model- and dataset-agnostic.The paper presents a theoretical analysis of how and why the attacks work.Source: §1 · p. 2
  • A single epoch of intervention can slow training progress or reset it across evaluated computer-vision and language benchmarks.The attacks were evaluated with a range of hyperparameter configurations.Source: §1 · p. 2
  • On CIFAR10 VGG16, trigger accuracy is 99% for the perturbed-data baseline, 91% ± 13 for whitebox BOB, and 68% ± 19 for blackbox BOB.The paper reports that the whitebox attack introduces backdoors almost as well as perturbed data, while the blackbox attack also succeeds.Source: §1 · p. 2

2 Methodology

The attacks exploit SGD’s sensitivity to batch order, manipulating benign training data without changing the dataset. The methodology covers the threat model, order-dependent updates, three batching-attack policies, and clean-data poisoning and backdooring.

2.1 Threat model

  • The attacker may operate without access to the target model or prior knowledge of its training data, and can reorder data through several points in the supply pipeline.The paper describes a co-trained surrogate that uses the batches supplied to the target model; it also notes attack implementations in storage, sampling, and prefetch components.Source: §2.1 · p. 2, Figure 1 · p. 2, §2.2 · p. 3

2.2 Primer on stochastic learning and batching

  • Because batch gradients only approximate the true gradient, their order affects a second-order correction that the attacker targets by misaligning updates with the true gradient step.The paper motivates this attack surface through the variation between individual batches and the expected gradient under unbiased sampling.Source: §2.2 · p. 3

2.3 Taxonomy of batching attacks

  • BRRR attacks comprise batch reordering, reshuffling, and replacement, with four policies that sequence data according to loss magnitude or position.Reordering changes batch order; reshuffling changes datapoint order within batches without repetition; replacement allows datapoints or batches to repeat or be omitted. The four ordering policies are low-to-high, high-to-low, oscillations inwards, and oscillations outwards.Source: §2.3 · pp. 3–4, Figure 2 · p. 4, Figure 3 · p. 5

2.4 Batch-order poison and backdoor

  • BOP and BOB use the order of genuine data to approximate adversarial gradient updates, enabling poisoning and backdooring without modifying training data.The paper argues that stochastic optimization can make natural datapoints produce gradients similar to those of adversarial datapoints, and that this ability improves with larger datasets.Source: §2.4 · p. 4
  • Randomly sampling natural datapoints can construct batches whose gradients approximate a target poison update, and the resulting update can shift predictions toward a target class.The paper reports balancing natural and adversarially chosen points in a batch, with up to 30% natural datapoints, to trade off gradient approximation against conflict with natural gradients.Source: §2.4 · p. 5, Figure 4 · p. 5

3 Evaluation

The evaluation shows that reordering and reshuffling can sharply disrupt model training, while batch replacement can poison or backdoor models using clean data. A single availability-attack epoch can leave training degraded for more than 90 epochs, and backdoor performance depends on the trigger and attacker setup.

3.1 Experimental setup

  • Experiments cover CIFAR-10, CIFAR-100, and AGNews, with weaker surrogate models that make the reported results a lower bound on attack performance.The source models include ResNet-18, ResNet-50, and an EmbeddingBag-based text model; surrogate architectures are LeNet-5, MobileNet, and a fully connected model, respectively.Source: §3.1 · p. 5

3.2 Integrity attacks with reshuffling and reordering of natural data

  • Batch reordering caused 0–15% performance degradation, while computer-vision reshuffling fell to near-random performance after the attacker’s first observation epoch.The attacker changed batch order without changing batch contents; all computer-vision reshuffle attacks remained near random for almost all later epochs.Source: Table 1 · p. 6, §3.2 · p. 6

3.3 Availability attacks

  • A single-epoch availability attack using low-high batch reordering, with each batch containing data points from one class, reset training and degraded performance for more than 90 epochs, reaching −3% performance at epoch 100.Source: §3.3 · pp. 6–7

3.4 Backdoors with batch replacement

  • In the whitebox setup, a flag-like BOB trigger approached perturbed-data performance; in blackbox, trigger performance fell by around 30% but remained operational.The authors report that most models converged after 3–5 adversarially ordered batches, although their procedure also injected 80 batches.Source: §3.4 · p. 7
  • The lines trigger only marginally outperforms baseline, achieving 20–40% performance in a whitebox setup and zero to 20% in a blackbox setup.Source: §3.4 · p. 8
  • Batch replacement can poison an individual datapoint or introduce a backdoor without training on adversarially crafted data or labels.The section reports that BOB trigger performance differs by setup, with some attacks on a par with explicitly injected perturbations.Source: §3.4 · pp. 7–8

4 Related Work

Prior integrity attacks manipulate inputs or training data, while prior availability attacks target inference-time hardware costs. This paper instead presents training-time attacks that manipulate batching, including poisoning with clean data and labels.

Attacks on integrity

  • Adversarial-example attacks cause incorrect inference outputs through perturbed samples, with whitebox methods using gradients and blackbox methods relying on surrogate-model transfer [30].These attacks differ from the paper’s training-time batching manipulation.Source: §4 · p. 8
  • Earlier poisoning methods altered samples, labels, or patterns [8] [11] [25], whereas this paper reports poisoning through batching alone with clean data and labels.The paper frames its result against the prior belief that poisoning required malicious data or label manipulation.Source: §4 · pp. 8–9

Attacks on availability

  • Prior sponge-example attacks targeted inference-time energy use and latency; this work targets training-time availability by reordering or reshuffling natural batches.The authors distinguish their attacks as targeting the stochastic assumption of training rather than hardware or model-specific optimizations.Source: §4 · p. 9

5 Conclusion

The paper concludes that changing batch or datapoint order can manipulate training integrity and availability without changing the dataset, and that these attacks can be fully blackbox. Its analysis also identifies a batch-gradient error term that an attacker can manipulate to hinder SGD convergence.

5 Conclusion

  • Changing batch or datapoint order can poison or backdoor training without changing the dataset, and the attacks do not require knowledge of the target model or data.The conclusion also reports backdoors without disrupting generalization, using natural data.Source: §5 · p. 9
  • The authors argue that secure, robust, fair optimization requires inspecting assumptions and establishing the provenance of randomness used to select batches and datapoints.They connect this concern to SGD’s dependence on randomness.Source: §5 · p. 9
  • The paper identifies fairness implications as future work, linking sampling bias and algorithmic bias to the practical role of pseudorandom sampling.Source: §5 · p. 9

A Stochastic gradient descent and rate of convergence

  • The convergence analysis says an attacker can manipulate the batch-gradient error term by selecting batches whose gradient difference points opposite the true gradient.The paper approximates this information with the loss error term as a less expensive practical proxy; it reports nonconvergence even for simple two-variable linear regression in Appendix G.Source: A Stochastic gradient descent and rate… · pp. 13–14

B Upper bound on sample size for poisoning attacks

The analysis estimates how many natural samples are needed to approximate a target gradient within a chosen tolerance and confidence level, using a central-limit approximation. It states that multidimensional reconstruction requires a non-singular covariance matrix.

B Upper bound on sample size for poisoning attacks

  • The sample-size analysis uses a central-limit approximation to estimate the number of natural samples needed to match a target gradient within tolerance ϵ at confidence 1 − p.It models item losses and batch gradients, then frames the task as selecting a sample whose gradient approximates the target.Source: B Upper bound on sample size for… · p. 14
  • For multidimensional gradients, the reconstruction is described as impossible in the general case unless the covariance matrix is non-singular.Source: B Upper bound on sample size for… · p. 14
  • In the illustrated singular-covariance case, the closest reconstruction is 0.5 at x = 0.5, so the analysis assumes non-singular covariance.Source: B Upper bound on sample size for… · p. 14

C Second order correction term in expectation

The section analyzes how data order affects SGD’s second-order correction and derives conditions under which reordering increases that term. It concludes that normally distributed gradients can make learning vulnerable to ordering attacks.

C Second order correction term in expectation

  • Reordering first affects SGD through the second-order correction term, rather than the first-order gradient sum.The order-dependent term uses gradients and their derivatives as surrogates, under an i.i.d. gradient assumption.Source: C Second order correction term in… · p. 15
  • Under equally distributed loss gradients, changing data order can increase the expected order-dependent term, with attack success guaranteed under a condition on the gradient distribution.The strategy requires the lower bound on the reordered term to exceed the upper bound on the non-reordered term.Source: C Second order correction term in… · pp. 15–16
  • For normally distributed gradients, the analysis concludes that an attacker can break learning by changing data order.The paper notes that large neural-network batches can make gradients approximately normal by the central limit theorem.Source: C Second order correction term in… · p. 17
  • Batch reordering disrupts learning less than batch reshuffling because its σ is smaller, while μ remains unchanged.Source: C Second order correction term in… · p. 17

D Integrity attacks on Computer Vision in white and blackbox setups

Whitebox and blackbox reordering attacks both significantly degrade model accuracy at train and test time. The blackbox attack has smaller accuracy variation across batches.

D Integrity attacks on Computer Vision in white and blackbox setups

E Extended integrity attack results

Resampling can substantially change integrity-attack outcomes, sometimes improving performance after batch reordering. Batch reshuffling with several policies performs consistently well across vision and language tasks.

E Extended integrity attack results

  • Resampling changes batch contents between epochs and recalculates random data augmentations, substantially affecting attack performance and sometimes improving results after batch reordering.Source: E Extended integrity attack results · p. 18
  • Batch-reorder performance follows a theoretical bound based on relative gradient magnitudes, while reordering and reshuffling differ in gradient approximation and variance across batches.Source: E Extended integrity attack results · p. 18
  • Low High, High Low, and Oscillations outward batch-reshuffling policies perform consistently well across computer-vision and natural-language tasks.Source: E Extended integrity attack results · p. 18

F BOP with batch replacement

Across these experiments, ordered training can steer poisoned datapoints, disrupt simple linear-regression convergence, and degrade test performance. The effects vary with attack type, minibatch size, and resampling.

F BOP with batch replacement

  • After 10 clean epochs, BOP steers a poisoned datapoint to its target class in 3–5 batches for ResNet-18 and VGG-11, 10 for MobileNet, and about 50 for VGG-16.After poisoning, all models lose at most 10% accuracy.Source: Figure 8 · p. 18, F BOP with batch replacement · p. 19

G Stochastic gradient descent with linear regression

  • Even a two-parameter linear-regression model whose data follow y = 2x + 17 + N(0, 1) can have convergence disrupted by reordering.The paper attributes this vulnerability to the optimization process rather than overparameterized models.Source: G Stochastic gradient descent with… · p. 19

G.1 Batch reshuffling

  • With error-ordered data and minibatch size 1, linear-regression SGD overfits current minibatches and fails to reach the optimum; a 10-fold larger step size increases θ0 oscillations.The step size changes from 5e−6 to 5e−5.Source: §G.1 · p. 19, Figure 9 · p. 19, Figure 11 · p. 20

G.2 Batch reordering

  • Increasing minibatch size dampens the oscillations and can restore convergence, while simple batch reordering degrades performance less than reshuffling.Figure 10 compares average error for randomly sampled and error-ordered data.Source: §G.2 · p. 19, Figure 10 · p. 20

H Batch reshuffling and hyperparameters

I Whitebox batching attack performance

J Triggered training for CV models

The experiments show that BOB controls model performance strongly in whitebox settings, with lower performance in blackbox settings. The evaluation tracks training, test, and trigger accuracy, as well as trigger-induced mistakes.

J Triggered training for CV models

  • The evaluation reports training, test, and trigger accuracies, plus mistakes introduced by the trigger, for a VGG16 target and ResNet-18 surrogate.Source: J Triggered training for CV models · p. 20
  • The attacker uses up to 20 BOB batches per 50,000 natural datapoints for 10 epochs, followed by 90 pure BOB batches.The non-BOB baseline has zero trigger accuracy.Source: J Triggered training for CV models · p. 21
  • BOB controls performance strongly in whitebox settings, while performance decreases in blackbox settings.Trigger performance differs by target class, but the attack works across classes without disrupting overall model generalisation.Source: J Triggered training for CV models · p. 21

K NLP backdoors

The paper finds that BOB can inject backdoors into an NLP model, though its performance differs from computer-vision triggers. Backdoor performance depends on batch size and target class, and the reported results are specific to the tested architecture.

K NLP backdoors

  • The NLP results use an EmbeddingBag model with mean sparse embeddings of size 1024 and two linear layers, and the authors say the findings may differ for other architectures.They report that BOB takes more effort for NLP and hypothesize this relates to summing embeddings and tokens not appearing in every class.Source: K NLP backdoors · p. 21
  • BOB injects backdoors into the tested NLP model, but performance differs from computer-vision triggers.The paper concludes that NLP is vulnerable to BOB, while architectural and data differences change attack performance.Source: K NLP backdoors · p. 21
  • Larger batch sizes produce worse backdoor performance, and some classes are easier to backdoor than others.Source: K NLP backdoors · p. 21

Related papers

Loading 2104.09667v2…