Manipulating SGD with Data Ordering Attacks
Authors: I Shumailov
Zakhar Shumaylov
Dmitry Kazhdan
Yiren Zhao
Nicolas Papernot
Murat A Erdogdu
Ross Anderson
Venue: NeurIPS 2021 Poster (2021)
Keywords: adversarial machine learning
training time attacks
attacks on sgd
poisoning
backdoors

Abstract: 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.

Manipulating SGD with Data Ordering Attacks
Ilia Shumailov University Cambridge & University of Toronto & Vector Institute ilia. shumai loveellollll..oom cam ac.
Zakhar Shumaylov University of Cambridge zs334@cam.c ac.uk
Dmitry Kazhdan University of Cambridge dk5258cam. ac. uk
Yiren Zhao University of Cambridge yiren. zhao@cl. cam ac uk
Nicolas Papernot
University of Toronto & Vector Institute
nicolas micolas. www.pppoottttooooooooooooo
Murat A. Erdogdu University of Toronto & Vector Institute erdogduêcs coronto.edi
Ross Anderson
University of Cambridge & University Edinburgh
ross. anderson@cl. cam. ac uk
Abstract
Machine learning is vulnerable wide variety of attacks. It is now well under- stood that by changing the underlying data distribution, an adversary can poison the model trained with it or introduce backdoors. In this paper we present novel class training-tinn time attacks that require no changes to the underlying dataset or model architecture, but instead only change the order in which data supplied the model. In particular, we find that the attacker can either prevent the model from learning, poison it learn behaviours specified by the attacker. Furthermore, we find that even a single adversarially-ordere model learning, or even reset all of the learning progress. Indeed, the attacks presented here are not specific to the model or dataset, but rather target the stochas- tic 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.
epoch can be enough to slow down
Introduction
The data-driven nature of modern machine learning (ML) training routines puts pressure on data supply pipelines, which become increasingly complex. It is common to find separate disks or whole content distribution networks dedicated to servicing massive datasets. Training is often distributed across multiple workers. This emergent complexity gives perfect opportunity for attacker to disrupt ML training, while remaining covert. In the case of stochastic gradient descent (SGD), assumes uniform random sampling of items from the training dataset, yet practice this randomness is rarely tested or enforced. Here, we focus on adversarial data sampling.
It is now well known that malicious actors poison data and introduce backdoors, forcing ML models to behave differently in the presence of triggers [12]. While such attacks have been shown to pose real threat, they have far required the attacker perturb the dataset used for training.
We now show that by simply changing the order in which batches or data points are supplied to model during training, an attacker can affect model behaviour. More precisely, we show that it is
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Attack
Datastt knowlelge
Model knowlelge
Model speeilie
Changing datavet
Adding datt
Adding pertorbations
Batc Reader
Batc Reihulle
x
Batch Replace
X
Adversangl imitaisationn I
J
X
X
X
BadNens [2]
X
X
Dynamie trigees 1S
X
Poisoned brogs 23
Table 1: Taxonomy of training time attacks. In green, we highlight attacks.
possible to perform integrity and availability attacks without adding or modifying any data points. For integrity, attacker can reduce model accuracy arbitrarily control its predictions in the presence of particular triggers. For availability, an attacker can increase the amount of time it takes for the model train, even reset the learning progress, forcing the model parameters into a meaningless state.
We present three different types of attacks that exploit Batch Reordering. Reshuffling and Replacing naming them BRRR attacks. We show that an attacker can significantly change model performance by (i) changing the order in which batches are supplied to models during training: (ii) changing the order which individual data points are supplied to models during training; and (iii) replacing datapoints from batches with other points from the dataset to promote specific data biases. Furthermore, introduce Batch-Orde Poison (BOP) and Batch-Orde Backdoor (BOB), the first techniques that enable poisoning and backdooring of neural networks using only clean data and clean labels; an attacker can control the parameter update of a model by appropriate choice of benign datapoints. Importantly, BRRR attacks require underlying model access knowledge of the dataset. Instead, they focus on the stochasticity of gradient descent, disrupting how well individual batches approximate the true distribution that a model is trying to learn.
To summarise, we make the following contributions in this paper:
We present a novel class of attacks on ML models that target the data batching procedure used during training. affecting their integrity and availability. We present a theoretical analysis explaining how and why these attacks work, showing that they target fundamental assumptions of stochastic learning, and are therefore model and dataset agnostiq"]
We evaluate these attacks on a set of common computer vision and language benchmarks, using range of different hyper- parameter configurations, and find that attacker can slow the progress of training, as well as reset it, with just a single epoch of intervention.
We show that data order can poison models and introduce backdoors, even in a blackbox setup. For a whitebox setup, we find that the adversary can introduce backdoors almost as well as if they used perturbed data. While baseline CIFAR10 VGG16 model that uses perturbed data gets 99% trigger accuracy, the whitebox BOB attacker gets 91 % + 13 and the blackbox BOB attacker achieves 68% 19.
2 Related Work
Szegedy et al. (34 and Biggio et al. (6 concurrently discovered the existence of adversarial examples. These samples, containing human imperceptible perturbations, cause models to output incorrect results during inference. The original whitebox attacks require the adversary to access the models and use gradient information to perform conditioned optimisation to maximise the model loss [34]g 6 [0] 22 The attack later generalised to blackbox setups, where the adversary trains a surrogate model and hopes the generated adversarial samples transfer to the target model [24].
Attacks on integrity:
The data daiasnnis attack aims at using data manipulation to cause DNNs to fail on specific test-time instances [17]. Chen al. demonstrated that manipulation of the labels of around 50 training samples is enough to trigger failure [ Gu et al. showed that attackers can associate adversarial patterns with labelled images and cause DNNs overfit to this pattern 12]. Shafahi et al. launched a poisoning attack using instances with clean labels [29]. A number of other works have since created more efficient triggers (28). was a common belief that poisoning attacks on DNNs have to contain certain level of malicious manipulation of whether the data or label at train time. However, this paper
'Codebase is available here: http:s//ggtttb.ocoo////sssssssss

---

shows how poisoning is possible with clean data and clean labels, with the only manipulation being of the batching process at training time.
Attacks on availability: Shumailov et al. first attacked the availability of computer vision and natural language processing models inference time with sponge examples 330 They pessimized over energy utilisation and inference latency to target hardware and internal model optimisations. By contrast, this paper targets availability training time. We show that the attacker can reset or slow down training progress by reordering or reshuffling natural batches. Finally, we note that unlike Shumailov et al., our attacks do not target specific optimisations in hardware individual models, but instead break the fundamental stochastic assumption of training.
the terms integrity and availability in a slightly different sense from the rest of the literature. By availability, we mean the availability of a training procedure the rate which the model trains, as opposed to model performance the task. By integrity attacks, we mean attacks that either stop the model from learning its intended task, or force it to learn additional unrelated task.
Note terminology: As study attacks training,
Methodology
3.1 Threat model
Datapoent
Loaom
Ordaned
Bunches
Model
Random
Batsher
Model
Randioniyy Sarpled
Addeenaatall-rreeddd Training
Data
Figure 1: The attacker reorders the benign randomly supplied data based the surrogate model outputs. Attacker co-train co-trains the surrogate model with the data that is supplied to the source model.
We assume of the strongest threat models currently described in the literature. In particular, our blackbox attacker assumes no access to the model and no prior knowledge of the training data, whereas whitebox attacker has access the model under attack and can compute its loss directly. The attack specifically focuses on the batching part of the ML pipeline as is depicted in Figure || We discuss the related work in Section
This attack is realistic and can be instantiated in several ways. The attack code can be infiltrated into: the operating system handing file system requests; the disk handling individual data accesses; the software that determines the way random data sampling is performed; the distributed storage manager; the machine learning pipeline itself handling prefetch operations. That is a substantial attack surface, and for large models these components may be controlled by different principals. The attack is also very stealthy. The attacker does not add any noise or perturbation the data. There are no triggers or backdoors introduced into the dataset. All of the data points are natural. In two of four variants the attacker uses the whole dataset and does not oversample any given point, i.e. the sampling is without replacement. This makes it difficult to deploy simple countermcasures.
3.2 Primer on stochastic learning and batching
We assume that the defender trying to train a deep neural network model with parameters operating X; Xuain solving non-convex optimization problem with respect to parameters 0. corresponding to minimization of given loss function L(0). We will denote the training dataset X (X,). We assume commonly-used loss function defined as the sample average of the loss per training data point L,(0) L(X,,0) 8) in k-th batch over the training set, where B is the batch size: ix)1(0) 1/2 Σ b4 (())). If we let N B be the total number of items for
3

---

training, then in a single epoch one aims to optimize: L(0) = Ex= (0). Optimization with stochastic gradient descent (SGD) algorithm of N samples and a learning rate of n leads the following weight update rule over one epoch: 0x+1 = 0x + n A0, = - 1 SGD is often implemented with momentum [25 33). with μ and representing momentum and velocity respectively: uk+1 = poo + >/00;;
0x+1 = O2 + Uk+11
Given data, SGD's s stochasticity comes from the batch sampling procedure. Mini-batched gradients approximate the true gradients of f. and the quality of this approximation can vary greatly. In fact, assuming an unbiased sampling procedure, i.e. when the k'th gradient step corresponds to ig 'th batch with P(i = i) = 1/N, in expectation the batch gradient matches the true gradient:
N Σ
VV, Σ P(i+=
vi.(0) Vi.
Although this happens in expectation, a given batch taken in isolation can be very far from the mean. This variation has been exploited in the literature aid training: there exists a field responsible for variance reduction techniques for stochastic optimisation [8]. active learning [ 35 (anti-) curriculum learning 20 and core-set construction 22. Each area looks at identifying and scheduling data subsets that aid training and give better true gradient approximation. In this paper, we turn things round and investigate how an attacker can exploit data order to break training. The explicit stochastic assumption opens new attack surface for the attacker to influence the learning process. In particular, let us consider the effect of N SGD steps over one epoch [3::
ON+1= = 01 - vi -/V(2((0))
7 LA (0x)
dependent
N
= = 11 VL, +1
k<j
As we can see, in this case the second order correction term is dependent on the order of the batches provided. The attacker we deseribe in this paper focuses manipulating it i.e. finding a sequence of updates such that the first and second derivatives are misaligned with the true gradient step. In Appendix(C) we prove that under equally-distribute loss gradients, a change in data order can lead to an increase in the expected value of the term which is dependent on data order. We also derive condition on the gradient distribution given a model for which it is guaranteed. Finally, we derive an attack objective to target the upper bound on the rate of SGD convergence explicitly in Appendix
In this paper assume the blackbox attacker has access the underlying model, and thus way to monitor its errors or the progress of its training. Instead, we co-train a separate surrogate model, using the batches supplied to the target model. We find that in practice the losses produced by the surrogate model approximate the losses of the true model well enough to enable attacks on both integrity and availability. We empirically find that blackbox reshuffle attacks perform well as the whitebox one in Appendix D
Finally, although the attacker can maximise the term dependent data order directly, in practice is expensive to do so. Therefore, the attack we use the loss magnitudes directly rather than their gradient. Intuitively, large prediction errors correspond to large loss gradient norms, while correct predictions produce near-zero zero gradients. Although this assumption may not hold for all loss landscapes, for the loss landscapes incurred by real machine learning models, local minima often cluster around the global minima as the loss satisfies certain dissipativity properties [26] 36], and consequently loss magnitudes correlate with the gradient of the loss. We emphasize that we this approximation only for computational advantage.
3.3 Taxonomy of batching attacks
In this section we describe the taxonomy of batching attacks as shown in Figure 2 The overall attack algorithm is shown in Algorithm 2 in the Appendix, and a shortened attack flow is shown in Algorithm I We highlight that our attacks are the first to successfully poison the underlying

---

rondom Leadling
wondeing vnu roungg
Suich roaluulling or inar butch miinn
Intucheza buich repkee replading bukdhea Vallao rit
Figure 2: Taxonomy BRRR attacks. Normal batching assumes randomly distributed data points and batches. Batch reordering assumes the batches appear to the model in different order, but internal contents stay in the original random order. Batch reshuffling assumes that the individual datapoints within batches change order, but appear only once and do not repeat across batches. Finally, batch replacement refers to cases where datapoints or batches can repeat or not appear at all.
Algorithm 1: A high level description of the BRRR attack algorithm
/* Attack preparation: collecting data
do
get a new batch and add it to list of unseen datapoints; train surrogate model on batch and pass it on to the model;
while first epoch is not finishdd
Attack: reorder based on surrogate loss
while training do
rank each data point from epoch with surrogate loss;
reorder the data points according to the attack strategy;
pass batches model and train the surrogate at the same time.
model without changing the underlying dataset. In this paper we use three attack policies (1) batch reshuffting or changing the order of datapoints inside batches; (2) batch reordering or changing the order of batches; and (3) batch replacement or replacing both points and batches, We consider four reordering policies, motivated by research in the fields of curriculum learning [5] and core-set selection [2]. which discovered that model training can be enhanced by scheduling how and what data is presented to the model. That can help the model to generalize and to avoid overfitting with memorization. This paper does the opposite we promote memorization and overfitting, forcing the model to forget generalizable features. Anti-curriculum learning (e.g. [33] is particularly close to our batch reordering setting.
Randon order
Ouoikatione
High-low order
Oacilations oulward
Figure 3: We use four different reorder and reshuffle policies based on the corresponding data point and batch losses. We color-code the loss values from bright to dark colors, to represent loss values from low to high. Low-high policy orders sequence by the loss magnitude. High-low policy orders a sequence by the negative loss magnitude. Oscillation inwards orders elements of the sequence from the beginning and the end of the sequence one by one, if it was oscillating between sides of the sequence and moving towards the middle. Finally, Oscillations outward orders the sequence by starting at the middle of ordered sequence picking elements to both sides of the current location.
Figure 3 shows attack policies. Low to high orders sequence items by their loss. High to low an inverse of Low to high. Oscillations inwards picks elements from both sides in sequence. Oscillations outwards inverts the halves of the sequence and then picks elements from both sides.
5

---

3.4 Batch-order poison and backdoor
Machine-learning poisoning and backdooring techniques aim manipulate the training of given model to control its behavior during inference. In the classical setting, both involve either appending adversarial datapoints X to natural dataset X or changing natural datapoints X + 8 so as to change model behaviour. This makes the attack easier detect, and to prevent. For example, an adversary may add a red pixel above every tank in the dataset to introduce the red pixel trigger and cause other objects under red pixels to be classified as tanks.
We present batch-order poisoning (BOP) and batch-order backdooring (BOB) - the first poison and backdoor strategies that do not rely on adding adversarial datapoints or perturbations during training. but only on changing the order in which genuine data are presented. BOP and BOB are based on the idea that the stochastic gradient update rule used in DNN training is agnostic of the batch contents and is an aggregation. Indeed, consider a classical poison setting with an adversarial dataset X::
0c+1 = 02 + 7/0n;; A0g - (Vo xx; 02) + Fo,((xx0s.))
Order-agnostic aggregation with a sum makes it hard to reconstruct the individual datapoints Xg from just observing Adk. Indeed, the stochastic nature of optimisation allows one find set of datapoints X, * X, such that (X 0x) VxL(X,,88) Given model and a dataset such that the gradient covariance matrix is non-singular, an attacker can approximate the gradient update from an adversarial dataset X using natural datapoints from the genuine dataset X, enabling poisoning without having to change of underlying dataset in any way:
0x+1 = 02 + n/0ks where Ao - VoL
(3)
Voi((.,, 02) = VoL(X,, 0x).
This gives rise to a surprisingly powerful adversary, who introduce arbitrary behaviors into any models learned with stochastic gradient descent without having to add or perturb training data. This attack becomes more effective training datasets become larger, further improving the attacker's ability to shape the gradient update. We discuss its fidelity in Appendix B
(a) Natural image hatch
(b) Poison datapoint batch
Figure 4: Examples of batches shown in (a) and (b) with similar gradient updates. Images shown in (a) natural and are coming from the training set, whereas image in (b) is the poison datapoint. Strong gradients are aligned across the layers and successfully change the prediction of poison datapoints.
We evaluated number of different setups, and found that the attack works best when the attacker comprises the batch with V natural data points and appends V adversarially-chose data points X; to the batch. Aa larger V is better for gradient approximation, but leads to more conflict with natural gradients; in the paper up to 30% of the batch is filled with natural datapoints to find a balance. Finding precise batch reconstruction is an intractable problem that scales with batch size and size of the dataset. However, we find that random sampling works well; even if mistakes are made, the network still learns the poison over the course of few batches. Overall we try to minimize the following reconstruction error for a given poisoned batch Xy:
vxi((x)0)) - S.t. X,E
min X.
(4)
Although more sophisticated approaches could help find better candidates, we discovered that random sampling works well enough for successful clean-data clean-label poison and backdoor attacks. also helps us strike a balance between speed of batch construction and impact on model performance. Figure 4hhus shows an example of natural data (a) that closely resembled the would-be update with batch in (b). Notably, such updates result in prediction change towards the target class.

---

Evaluation
4.1 Experimental setup
We evaluate our attacks using two computer vision and one natural language benchmarks: the CIFAR-10. CIFAR-100 [9] and AGNews [37] datasets. We use ResNet- 18 and ResNet-50 as source models [14] and LeNet-5 [21] and MobileNet [16] as surrogate models, to train CIFAR-10 and CIFAR- 100 respectively. For AGNews we used sparse mean BmbeddingBag followed by three fully connected layer from torchtext as source model and one fully connected layer for surrogate. Note that the surrogate model is significantly less performant than its corresponding source model in all cases, and cannot learn the dataset to the same degree of accuracy, limiting attacker capabilities. Thus our results represent a lower bound on attack performance.
4.2 Integrity attacks with reshuffling and reordering of natural data
CIFAR-10 Train acc
CIFAR-100 Test ace
AGNews
Attack
Test acc
Train ace
Train ace
Test acc
A
Boseline
Nome
95.51
90,51
0.00%
||
99.96
75.56
-0.0%
93.13
90.87
00.0%
Batch restuglle
Oscillation outward
17.44
26.13
64.38%
99.80
18.00
-57.56%
97.72
65.85
-25002%
Oscillation inward
22.85
28.94
-61.57%
99.92
31.38
-41.18%
94.06
89.23
-1.64%%
lligh Low
23.39
31,04
-50.47%
99.69
21.15
-54.41%
94_38
56.54
33.33%
Low High
20.22
30.09
-21.42%
96.07
20.48
-55.08%
98.94
59.28
-31.39%
Ratch mouler
Oscillation oulward
99.37
78.65
-1.86%
100.00
53.05
-22.51%
95.37
90.92
+0.05%
Oscillation inward
99.60
78. 18
12.33%
100.00
51,78
23.78%%
96.29
91.10
+0.93%
1ligh Low
99.44
79.65
-0.8696
100.00
51.48
-4.00%%
96.16
91.80
+0.05%
Low High
99.58
79.07
1396
100.00
54.04
-21.52%
94.02
90.35
-0.32%
Table 2: A shortened version of Table 4
For CIFAR- 10, we used 100 epochs of training with target model ResNet18 and surrogate model LeNet5, both trained with the Adam optimizer 0.1 learning rate and B = (0.99, 0.9). For CIFAR-100, we used 200 epochs of training with target model ResNet50 and surrogate model Mobilenet, trained with SGD with 0. learning rate, 0.3 moment and Adam respectively for real and surrogate models. We highlight models that perform best in terms of test dataset loss. AGNews were trained with SGD learning rate 0.1, 0 moments for 50 epochs with sparse mean Embeddinggagg, Numbers here are from bert-perg model test loss-wisc Incidentally, best performance of all models for Batch reshuffle listed in the table happen at epoch number one, where the attacker is preparing the attack and is collecting the training dataset. All computer vision reshuffle attacks result in near-random guess performance for almost all subsequent epochs.
Table 2 presents the results (a much more detailed version is shown in Table 4 Batch reordering disrupts normal model training and introduces from zero to 15% performance degradation (refer to extended results and discussion in Appendix(E] Note that the attacker does nothing beyond changing the order of the batches; their internal composition is the same. This shows the potency of this attack. Indeed, when we extend the attack to batch reshuffling - where batches get re-arranged internally for computer vision, performance degrades to that of random guessing. In each, the best-performing models stay at the first epoch, where the attacker still accumulates the dataset used in training. Here, the degradation in performance is maximum all models with all attack types failed to perform better than random guessing, having reached their top performance only in the first epoch, when the attacker was observing the dataset.
We additionally report a large number of different hyperparameter variations for the attacks in Ap- pendix ! This hyperparameter search suggests that the attacks work well as long as the surrogate models learn, do not converge to a minimum straight away, and have sufficient learning rate.
Overall, we find that:
An attacker can affect the integrity of model training by changing the order of individual data items and natural batches.
The attacker can reduce model performance, and completely reset its performance.
7

---

4.3
Availability attacks
Availabiity attacks
Train
Test
0.8
0.8
Model Scourccy
Model acouracy
0.6
Attacking
0.6
0.4
lighte
nud feve
0.0
0.0
20
40
60
80
100
20
60
100
Epochs
Epoths
Figure 5: Availability attacks at epoch 10, ResNet-18 attacked with LeNet-5 surrogate. Error bars
show per-batch accuracy standard deviation.
While the previous section discused integrity attacks, this section's focus on availability. This refers to the amount of time and effort required to train a model, and an availability attack can involve an adversary using BRRR attacks to slow down training without disrupting the overall learning procedure. It is worth noting that there other possible definitions of availability; it also mean a model's ability to reach original accuracy, but this case already included in the integrity attacks we discussed in the last section.
Availability attacks follow a similar scenario to Section 4.2 above, in that the attacker only changes the order in which data reaches the model. Here we at the 10th epoch, an arbitrary attack point, and all other training is done with randomly ordered data. We find that by feeding the model with few BRRR batches, its training progress can be reset significantly- progress that may take surprisingly large number of epochs to recover. The red line shows the worst scenario, where each batch has only data points of a single class. It can be seen that the attack manages to reset training, degrading performance for more than 90 epochs - low-high batch reordering at epoch ten results in 3% performance at epoch 100.
In this section showed that the attacker can perform availability attacks using both batch reordering and reshuffling and leave an impact on a model long after they have been launched; even a single attack epoch can degrade training progress significantly. Overall, we find that:
An attacker can cause disruption to model training by changing the order of data in just a single epoch of training.
An attack at just one epoch is enough to degrade the training for more than 90 epochs.
4.4 Backdoors with batch replacement
We find that the attacker can backdoor models by changing the data order. Here, we apply trigger to images from the training dataset and then supply untriggered data the model that result a similar gradient shape. We find that our method enables the attacker to control the decision of model when makes a mistake iee. when the model making a decision about data far from the training-set distribution. For example, possible with just few batches. We hypothesise that the limitation comes from the fact that as only natural data sampled for each BOP and BOB batch, natural gradients present and learning continues; so forgetting does not happen and generalisation is not disrupted.
show in Appendix I that poisoning single random datapoint is
(a) Flag-like trigger
(b) white lines trigger
Figure 6: Triggers used in the paper: both the same magnitude- wise, affecting 30% of the image.
We evaluate two triggers shown in Figure white lines trigger, which clears the top part of an image, or like trigger that spans all of the image. We report results from injecting up to 20 adversarially-

---

ordered batches every 50000 natural datapoints for 10 epochs. We then inject 80 adversarially-ort ordered batches. The training procedure here is similar to the one used for BadNets [[2]. We find that 80 batches are not necessary, as most models end up converging after 3-5 adversarially-ooddred batches. For reconstruction we randomly sample 300 batches, balancing search efficiency and attack cost as is noted in Appendix H and use p = 2. As we discuss in Appendix L similar attacks work against language tasks.
Trigger
Batch size
Trin acc [%]
Test acc [%]]
Trigger acc [%]
Eiror with trigger [%]
Basefinez
32
88.43 + 4.2+7,00 7.26
79.00 + 1.49
10.91 # 1,53
30,70 = 2.26
Random natural data
96.93
5131
9.78 1.25
27.38 1:20
128
94.92 + 2,01
81.69 + 1.17
10.00 + 2.26
27.91 + 1.41
32
96.87
2.79
73.28 1. 2.93
90.65 1 0.22
89.68 0.21
Data with trigger perturbation
64
98.12
1.33
79.45 +: 1.39
99.61 1: 0.21
89.61
0.21
128
98.67
0.99
80.51 1. 1.10
90.67 1. 0.40
89.65 0.39
Only reordered natural date
32
88.43
6.09
78.02 + 1.50
33.93 7.37
40.78
5.70
white lines trigger
2.65
62.75
25.02
33.91
2,28
128
96.23 = 2.21
82,90 + 1.50
21.75 + 4.49
31.75 3.68
32
88,
= 4.85
80.81 + 1.20
17.55 + 3.71
33.61
2.83
Blackbox white lines trigger
64
98.59
15
82.61 + 1.61
16.39 + 4.80
30.90
3.08
128
94.84
2.24
81.12 + 2.49
16.19 + 4.01
31.33 3.73
32
90.93
3.81
78.46 :: 1.04
91.03 1 12.96
87.08 2.71
Flag like trigger
64
96.87
1.21
82,95 0.72
77.10 16.96
82.92 3.89
128
95.54 +: 1.88
82/28 + 1.50
69.49 :: 20.66
3.78 82,09
32
86.25
4.00
80. 10
56.31 19.57
78.78 3.51
Blackbox Bag. like trigger
64
96.00
2.18
63.41 1. 0.94
48.75 1. 23.28
78.11
4.40
93.82 + 2.27
81.54 1.94
68.07 18.55
81.23 3.80
Table 3: Network is VGGT6 that has been trained normally on CIFARTO for 10 epochs and then gets
attacked with 10 BOB trigger batches. Test accuracy refers to the original benign accuracy, 'Trigger acc' is the proportion of images that are classified as the trigger target label, while 'Error with trigger' refers to all of the predictions that result in an incorrect label. Standard deviations are calculated over different target classes. Blackbox results use ResNet-18 18 surrogate.
Table shows BOB trigger performance for both whitebox and blackbox setups. We present two baselines, one for normal training without any triggers, and one where triggers are added to the underlying data, iee training with perturbed data and labels. Trigger accuracy refers to the proportion of test set that ends up getting the target trigger label, whereas error with triggers shows the proportion of misclassifications that trigger introduces, i.e. when the model makes mistake, but does not predict the trigger target class. As expected, we observe that for normal training, trigger accuracy stays at random guessing, and the trigger does not dominate errors it introduces, whereas adding perturbed data manipulates the model to predict the target class almost perfectly.
We find that in whitebox setup for a like trigger we are capable of getting similar order of performance for batch of size 32 as the attack was performed with injected adversarial data. In blackbox setup with flag-like trigger we lost around 30% of trigger performance, yet the trigger still remains operational. A trigger of nine white lines outperforms the baseline only marginally; in a whitebox setup it gets from 20-40% performance, whereas in blackbox one it ranges between zero and 20% performance. We show the training progress of each individual trigger in Appendix K
Overall, we find that:
An attacker can poison an individual datapoint, change its label and increase its prediction confidence, without ever actually training the model on an adversarially-crafted datapoint.
An attacker can introduce backdoors into the model by introducing a few reordered batches during training, without ever injecting adversarial data or labels. Here, trigger perfor- mance differs, yet an adversary can perform BOB attacks on par with attacks that inject perturbations into datasets explicitly.

---

Conclusion
We presented a novel class of attacks that manipulate the integrity and availability of training by changing the order of batches, or the order of datapoints within them. Careful reordering of a model's training data allows it to be poisoned or backdoored without changing the training data at all. The attacks we presented are fully blackbox; they do not rely on knowledge of the target model or on prior knowledge the data. Most surprisingly, we find that an attacker can introduce backdoors without disruption of generalisation, even though only natural data is used. We are the first to show that the sampling procedure can be manipulated deterministically to control the model's 's behavior.
This paper reminds us that stochastic gradient descent, like cryptography, depends on randomness. A random number generator with a backdoor can undermine a neural network just as it can undermine a payment network [. Developers who wish to ensure secure, robust, fair optimization during learning must therefore be able to inspect their assumptions and, in case of SGD, show the provenance of randomness used to select batches and datapoints.
Future work may also explore the implications of findings fairness. Recent work has highlighted that ML models can suffer from a large taxonomy of different biases, including sampling bias, with outcomes including sexism and racism [ 23). This leads directly to questions of inductive bias and the practical contribution of pscudorandom sampling. Hooker has explained that bias in ML is not just data problem, but depends on algorithms in subtle ways [5] this paper shows how exploit that dependency.
Acknowledgements
We thank the reviewers for their insightful feedback. This work was supported by DARPA (through the GARD program), CIFAR (through Canada CIFAR AI Chair), Bosch Forschungsstiftung im Stifterverband, by NSERC (under the Discovery Program, and COHESA strategic research network), and by gift from Intel. We also thank the Vector Institute's sponsors.
References
[1] R. Anderson. Security Engineering. John Wiley Sons, 2020.
[2] O. Bachem, M. Lucic, and A. Krause. Practical coreset constructions for machine learning, 2017.
[3] R. Baeza-Yates. Bias on the web. Commun. ACM, 6 61(6))54-61, May 2018.
[4] R. R. Bahadur. A Note on Quantiles in Large Samples. The Annals of Mathematical Statistics, 37(3):577 580, 1966.
[5] Y. Bengio. J. Louradour, R. Collobert, and J. Weston. Curriculum learning. In Proceedings of the 26th Annual International Conference on Machine Learning, ICML '09, page 41-48, New York, NY, USA, 2009, Association for Computing Machinery.
[6] B. Biggio, I. Corona, D. Maiorca, B. Nelson, N. Šindić, P. Laskov, G. Giacinto, and F, Roli. Evasion attacks against machine learning at test time. In Joint European conference machine learning and knowledge discovery in databases, pages 387-402. Springer, 2013.
[7] H. Chen. Chapter 2. order statistics. LargeSample/
http: http://www..mate ntu, ndu. wod..t/// h/////hhhhettthhinggg
notes poteepeleeeeeeeeeeeeeeeeeeeeeeee
wwwtss/ooteooee.......... www.oooeeerrrrrrr -pdf]
[8] X. Chen, C. Liu, B. Li, K. Lu, and D. Song. Targeted backdoor attacks on deep learning systems using data poisoning. arXiv preprint arXiv:1712.05526, 2017.
[9] D. A. Cohn, Z. Ghahramani, and M. I. Jordan. Active learning with statistical models. CoRR, AS/9606033 1996.
[10] I. J. Goodfellow, J. Shlens, and C. Szegedy. Explaining and harnessing adversarial examples, 2015.
10

---

[11] K. Grosse, T. A. Trost, M. Mosbach, M. Backes, and D. Klakow. On the security relevance of initial weights in deep neural networks. In I. Farkaš, P. Masulli, and S. Wermter, editors. Artificial Neural Networks and Machine Learning- ICANN 2020, pages 3-14, Cham, 2020. Springer International Publishing.
[12] T. Gu, B. Dolan-Gavitt, and S. Garg. Badnets: Identifying vulnerabilities in the machine learning model supply chain. arXiv preprint arXiv:1708.061 2017.
[13] G. Hacohen and D. Weinshall. On the power of curriculum learning in training deep networks. In K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning. volume 97 of Proceedings of Machine Learning Research, pages 2535- 2544. PMLR, 19 Jun 2019.
[14] K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770- 778. 2016.
[15] S. Hooker. Moving beyond "algorithmic bias a data problem". Patterns, 2(4):100241, 2021.
[16] A. G. Howard, M. Zhu, Chen, D. Kalenichenko, W. Wang, T. Weyand, M. Andreetto, and H. Adam. Mobilenets: Efficient convolutional neural networks for mobile vision applications. 2017.
arXiv preprint 1rXXiv:104.0000
[17] M. Jagielski, A. Oprea, B. Biggio, C. Liu, C. Nita-Rotaru, and B. Li. Manipulating machine learning: Poisoning attacks and countermeasures for regression learning. In 2018 IEEE Symposium on Security and Privacy (SP), pages 19-35. IEEE, 2018.
[18] R. Johnson and T. Zhang. Accelerating stochastic gradient descent using predictive variance reduction. Advances in neural information processing systems, 36:315-323, 2013.
[19] A. Krizhevsky, G. Hinton, et Learning multiple layers of features from tiny images. 2009.
[20] M. Kumar, B. Packer, and D. Koller. Self-paced learning for latent variable models. In
J. Lafferty, C. Williams, J. Shawe-Taylor, Zemel, and A. Culotta, editors, Advances in Neural Information Processing Systems, volume 23. Curran Associates, Inc., 2010.
[21] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278- 2324,, 1998.
[22] A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu. Towards deep learning models resistant to adversarial attacks, 2019.
[23] N. Mchrabi, F. Morstatter, N. Saxena. K. Lerman, and A. Galstyan. A survey on bias and fairness in machine learning. CoRR, abs/1908. Abs//1908.0935,, 2019.
[24] N. Papernot, P. McDaniel, I. Goodfellow. S. Jha, Z. B. Celik, and A. Swami. Practical black-box attacks against machine learning. In Proceedings of the 2017 ACM on Asia conference on computer and communications security, pages 506-519, 2017.
[25] B. Polyak. Some methods of speeding up the convergence of iteration methods, USSR Computational Mathematics and Mathematical Physics, 4(5):1-17, 1964.
[26] M. Raginsky, A. Rakhlin, and M. Telgarsky. Non-convex learning via stochastic gradient langevin dynamics: a nonasymptotic analysis, 2017.
[27] H. Robbins and S. Monro. A stochastic approximation method. The annals of mathematical statistics, pages 400-407, 1951.
[28] A. Salem, R. Wen, M. Backes, Ma, and Y. Zhang. Dynamic backdoor attacks against machine learning models, 2020.
[29] A. Shafahi, W. R. Huang, M. Najibi, O. Suciu, C. Studer, T. Dumitras, and T. Goldstein. Poison frogs! targeted clean-label poisoning attacks on neural networks. arXiv preprint a0X19:1804.00792, 2018.

---

[30] I. Shumailov, Y. Zhao, D. Bates, N. Papernot, R. Mullins, and R. Anderson. Sponge examples: Energy-latency attacks on neural networks. In 6th IEEE European Symposium on Security and Privacy (EuroS&P) P), 2021.
[31] S. L. Smith, B. Dherin, D. G. T. Barrett, and S. De. On the origin of implicit regularization in stochastic gradient descent, 2021.
[32] M. Sun, S. Agarwal, and J. Z. Kolter. Poisoned classifiers are not only backdoored, they are fundamentally broken, 2020.
[33] Sutskever, J. Martens, G. Dahl, and G. Hinton. On the importance of initialization and momentum in deep learning. In S. Dasgupta and D. McAllester, editors, Proceedings of the 30th International Conference on Machine Learning, volume 28 of Proceedings of Machine Learning Research, pages 1139-1147, Atlanta, Georgia, USA, 17-19 Jun 2013. PMLR.
[34] C. Szegedy, W. Zaremba, I. Sutskever, J. Bruna, D. Erhan, I. Goodfellow, and R. Fergus. Intriguing properties of neural networks. arXiv preprint arXiv:13/2.6199 2013.
[35] S. Tong and D. Koller. Support vector machine active learning with applications to text classification. J. Mach. Learn. Res., 2:45-66, Mar. 2002.
[36] L. Yu, K. Balasubramanian, S. Volgushev, and M. Erdogdu. An analysis of constant step size sgd in the non-convex regime: Asymptotic normality and bias, 2020.
[37] X. Zhang, J. Zhao, and Y. LeCun. Character-level convolutional networks for text classification. In NIPS, 2015.
12


Reviews:
[{"review_id": "_qWyWmBnzoI", "reviewer": "Reviewer_BGiu", "summary": "The paper presents a training-time attack against learning algorithms employing stochastic-gradient-descent (SGD) update. The attacks are designed as simply re-ordering the sequence of batches or individual data points during training. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The idea of re-ordering the input sequence to influence the learning outcome is interesting. It exploits fully the underlying workings of stochastic gradient descent. Preliminary studies show promising results. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Although the proposed attack strategy sounds exotic, I have several doubts about its practicality and rationality:\n\nTo carry out such an attack, the authors assume the adversary can fiddle with the OS, sampling software, etc. to not only have full access to the training data but its ordering. If the adversary has such an enormous power, why wouldn't he/she directly tamper the learned parameters after training?  It would be more reliable than the proposed attack that may not always succeed. \n\nThe authors only consider impotent learning models. Would machine learning models remain defenseless if they are aware of such attacks? How about random skipping/shuffling/dropout of batches or samples during training? How about using random batch sizes during training? Did you try different drop-out rate in your DNNs? \n\nThe authors claim \"large prediction errors correspond to large loss gradient norms, whereas correct predictions produce near-zero gradients\", is this assumption reliable given that there might be many possible local optima?\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "approximately 2 hours"}, "extra_text": {}}, {"review_id": "BXwpu6HaUm0", "reviewer": "Reviewer_YzAi", "summary": "The submission \"Manipulating SGD with Data Ordering Attacks\" evaluates a training time attack against ML models with a novel threat model: The order of data points (/order of batches/ order of data points within batches/batch composition) is adversarially modified to achieve a variety of malicious outcomes. The authors discuss their implementation of this attack in a variety of scenarios, and show applications for neural networks in image classification and text.", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, I am a fan of this submission. The threat model of adversarial batch ordering appears novel and interesting to me. There has been a growing interest in data poisoning(i.e. training time attacks) in recent years and this is a worthwhile attack scenario consider in the literature. The authors describe the setting well and provide good heuristic strategies for attacks that replicate backdoor attacks as well availability attacks in this threat model. It is especially interesting that the authors were able to show that such attacks are possible using smaller surrogate models.\n\n\n\nSome questions and minor comments:\n* The first time I saw Fig.4 I was confused whether the paper was actually about reordering of the internal structure of data points. I understand that this is not the case, data points themselves are unchanged, but the authors might consider rephrasing the caption of Fig.4 to make this clearer.\n* It would be interesting if the authors could extend their explanations of the connections between the proposed attack policies and related work in curriculum learning (in addition to the references mentioned in l142)\n* The discussion about gradient matching in Eq.(4) has interesting connections to perturbation-based poisoning attacks based on gradient matching (such as e.g. Geiping et al, ...Data Poisoning via Gradient Matching or influence function-based analysis in Koh&Liang, Understanding Black-box Predictions via Influence Functions)\n* I am not certain I understand/agree with the terminology of the authors in Sec 4. Sec. 4.2 shows integrity attacks. However the authors understand integrity attacks to be \"attacks that reduce test accuracy\" and availability attacks to be\"attacks that reduce training accuracy (temporarily)\", to my understanding (and the remark in l218). In contrast, other works consider integrity attacks to reduce the accuracy of some target trigger / data point without impacting model test accuracy and availability attacks to reduce model test accuracy. This is especially confusing to me because the examples quoted in Sec.2 as integrity attacks (such as Shafahi) fall under the second nomenclature and attacks as in Shafahi are only presented in Appendix F (?). If the authors want to keep their current terminology, it would be helpful to add additional clarification in both Sec. 4 and Sec. 2.\n* Connected to the previous point: Am I correct in my understanding that the experiment in Sec. 4.3 boils down to the same attack   as 4.2, but attacking only once (at epoch 10)? If this is the only difference, then I am not sure I like the titling of both subsections as integrity vs availability?\n* typo in l215", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations:\n\nThe authors briefly discuss this, but I would enjoy further discussion on the practical requirements of the attack (e.g. in the appendix) in terms of computation time and memory. For example, the authors could record the number of loss evaluations required to find a good adversaries during the random sampling in Sec. 3.4, or the computational requirements for loss computations on the small surrogate networks in comparison to the forward+backward passes of the victim model. Some more information about the limitations or the \"overhead\" required for the attack in terms of memory and computational requirements could help inform assessment of the currrent strength of the attack, for example in scenarios where the attack is running hidden on the same machine that runs normal training.\n\n\nSocietal Impact:\n\nThe paper analyzes a novel threat vector against machine learning pipelines. While the practical applicability of such an attack against a real-world system as theorized by the authors does require a significant amount of system access, it does remain a  possibility and is a threat model that should be openly discussed in the literature and taken in consideration in future designs of system-critical machine learning systems.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}, {"review_id": "5KeuhPWZ5KS", "reviewer": "Reviewer_rGd5", "summary": "This paper proposes hurting a deep neural network's accuracy, or its training time or introducing poisoning/backdoors only by manipulating the random batching in SGD algorithm. In these attacks, the attacker has the ability to observe the training samples during training and then either re-shuffle, re-order or replace the batches that were supposed to be randomly samples. They experiment on image classification and an NLP task to show that these attacks are effective without manipulating the individual samples at all, by just changing the order in which the model sees them during training.", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Poisoning attacks are becoming more and more relevant and this paper shows that the attacker can cause a poisoning-type effect by manipulating the sampling order during SGD training. Attacking SGD (which is almost universal in deep learning) creates a large attack surface and the paper demonstrates various threat models implemented by the same attack idea. \n\nStrengths:\n+ Relevant, new and novel threat model.\n+ Good empirical evaluation and formal reasoning to why this attack is feasible.\n+ The idea of secure randomness in differential privacy and encryption does not exist for deep learning, including SGD, random initialization or random data augmentation. Attacking the randomness itself is not a new idea outside deep learning (e.g., backdooring the Elliptic Curve random generators). This paper shows that maybe this is something we should care about in deep learning as well, or at least include such risks in our threat model specifications.\n\nWeaknesses:\n- Conjectures how such attack can be implemented but does not offer a realistic implementation. I glossed over the provided source code and it seems like the attack is implemented by manipulating the model's training code. This is fine for research but, for example, hacking into PyTorch's source code to implement this attack would yield a more realistic attack. I would assume this also brings about additional restrictions on the attacker. I think the ways the authors suggested give the attacker for a much larger capability than required by this attack. For example, by compromising the OS file system the attacker can do basically anything (swap the model at the end of training with a attacker-trained one?). This raises the question, given these capabilities why would the attacker opt for merely manipulating the SGD batches? I would recommend the authors to find a tight set of capabilities and implementation of this threat model that leaves no other room for the attacker.\n\n- Calling this a black-box attack stretches the meaning of black-box a little too much. The attacker sees the training set after all, the only difference is that they see it during training instead of seeing it prior to the training. Considering that this attack manipulates the attack during training, instead of before training like traditional poisoning attack, I don't think we can call it black-box. For example, is an attack where the attacker does not see the training samples themselves but sees the model's individual losses on each sample during loss averaging can be implemented? My point is bringing the proposed attacks to prior black-box attacks might better justify calling them black-box.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "(see above for recommendations)", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a novel attack on SGD trained models by identifying that one can adversarially change the order of samples to significantly decrease the accuracy of the model. This is a rather surprising finding given the fact that neither the data, or labels are perturbed in any way. Although such technique would not be successful in the convex case (apart from slowing down convergence), in the nonconvex case adversarial perturbations can lead to significant loss of accuracy. Although the presented results are interesting, the attack model needs to be clarified a bit with regards to the strength of the adversary. Assuming access to the order of data, likely implies a signifiant adversarial strength with regards to access to the software stack of the training system at hand. Nevertheless the observations made are important, highlighting yet another facet of attacks against high-capacity SGD-trained models.


Decision: Accept (Poster)