Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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. 

Strengths:
+ Relevant, new and novel threat model.
+ Good empirical evaluation and formal reasoning to why this attack is feasible.
+ 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.

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

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

limitations_and_societal_impact: (see above for recommendations)
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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. 
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. 
limitations_and_societal_impact: Although the proposed attack strategy sounds exotic, I have several doubts about its practicality and rationality:

To 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. 

The 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? 

The 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?
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
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.



Some questions and minor comments:
* 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.
* 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)
* 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)
* 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.
* 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?
* typo in l215
limitations_and_societal_impact: Limitations:

The 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.


Societal Impact:

The 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_title: null

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)