Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper presents a novel poisoning attack strategy for online learning settings, where the parameters of the machine learning model are updated as new batches of data are collected. For this, the authors propose an accumulative poisoning attack strategy with two phases. In the first phase, the attacker poisons the model in a stealthy way, so that the performance of the model is not affected, so that it magnifies the destructive effect of the poisoning attack conducted in the second phase, where the attacker injects poisoning points in a batch of samples to decrease the performance of the model. The authors shows that this attack strategy can also be applied for compromising federated learning. 
main_review: The idea and the algorithm proposed in the paper is very interesting and, to my best knowledge, novel. I really like the idea of having a preliminary phase where the attacker, in a stealthy way, manipulates the learning algorithm without affecting the performance, so that the impact of the attack is maximized in the second phase. In this sense, I think that the differences with respect to backdoor attacks are clear and adequately justified in Section 3.4. 

The presentation and justification of the method are fine. However, following some of the steps in the derivation of the attack are not straightforward (see for example the derivation of (9)) and I think that more details about the steps (in the appendix) are needed to help readers to understand and follow better the derivation of the attack strategy. With respect to the attack formulation, I miss the analysis with the computational complexity of the proposed attack strategy. 

My main concerns about the paper are on the experimental evaluation: 

(1) The authors just considered a single dataset, CIFAR, for the experimental evaluation. In this context, CIFAR is an easier dataset to compromise, given that the dataset is quite multi-modal with low-resolution images and the accuracy of the baseline model is less than 85%, which makes it more unstable against data poisoning attacks. It would be interesting to analyse the performance of this attack strategy in other benchmarks. For example, in MNIST, where poisoning with stealthy strategies can be more difficult to achieve. 

(2) The assumptions about the attacker are very strong in most of the experiments. In most cases, except for Table 2, the authors assume that the attacker is in control of 100% of the training points (please, correct me if I am wrong), which is quite unrealistic in most cases and provides a misleading view of the effectiveness of the attack. In the case of federated learning, it is unclear what is the fraction of malicious clients present in the platform. From the previous experiments I assume that is 100% of the clients, which explains the results reported in Tables 3 and 4. 

(3) Defensive techniques are not properly analyzed. For example, Figure 2 just report the metric values (which ones?) for the different anomaly detectors to show that the data points generated during the accumulative phase are stealthier. But is the performance of the model affected in the presence of such anomaly detectors and what is their effectiveness to detect the attack points generated using the vanilla and the proposed strategy (for example by looking at the AUC, false positives/negatives or the F1 score of the detector). Similarly, it would be interesting to analyze to test the attack against robust optimization methods such as Sever (Diakonikolas et al. “Sever: A Robust Meta-Algorithm for Stochastic Optimization”) or Rubinstein et al. “Antidote: Understanding and Defending against Poisoning of Anomaly Detectors” by, for example, performing a transfer attack. Similarly, in federated learning settings, it would be interesting to test the performance of the model against robust aggregation methods such as Krum (Blanchard et al. “Machine learning with adversaries: Byzantine tolerant gradient descent”) or median-based robust aggregation techniques (Yin et al. “Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates”), just to cite some. 

Side comment: The pictures in Figure 4 are too small to appreciate differences. It would also be good to show some pictures of poisoning points generated with vanilla approaches to highlight the differences between attacks. 

limitations_and_societal_impact: No comments.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: Data poisoning attacks usually target the offline setting and do not fully utilize the sequential nature of data utilization in the online learning scenario. This work aims to optimize the damage of a trigger batch during the training phase (akin to an availability attack) by adding selective perturbations to data leading up to the trigger batch. At that point, the trigger batch can cause significantly more damage than a vanilla trigger batch inserted in the data stream. The authors derive optimization requirements for the perturbations in this 'accumulative phase' and the trigger batch, and empirically demonstrate how the proposed attack can outperform other methods, all while being more robust to heuristics like gradient-clipping.
main_review: ## Positive Feedback

1. The derivation of the proposed method is laid out quite well - with functional annotations (e.g., Equation 9) and color-coding (e.g., Equations 6,7) help follow the proposed algorithm's process.

2. The attack is robust enough against different hyper-parameters, like lambda values (Figure 3(b)). Performance stability is an excellent property to have and may suggest the proposed method being technically sound.

3. The benefit of the accumulative phase is most evident in the presence of gradient-clip operations. Performance drops are significantly better when an accumulative phase is included, further highlighting the proposed method's advantage. Although better performance in the standard scenario is a good sign, accumulative data to bypass gradient-clipping operations more effectively is valuable.

---

## Criticism

1. My main concern is with an adversary's power that can accumulate poisoned data, compared to one that inserts poisoned data at some given iteration. Although the former is better at utilizing the online nature of data being used by the model, it ultimately uses more poison points. Not only does this make it more likely for the attack to be detected, but it makes comparison with a simple slip-in baseline poisoning attack like an apples-to-oranges comparison. Although the proposed method objectively performs better, it is unclear how an adversary with a similar strength (perhaps insert poisoned data twice at specific intervals?) would hold against this. I understand that it is hard to quantify the adversary's strength in this case, but it is pretty clear that the adversary in the proposed work's threat model is more potent than one that only adds poison data once.

2. The inclusion of only one dataset makes empirical findings less convincing - it would be great if the authors could also include results for another dataset (could be even from the same domain, but a different task). 

3. Assuming Whitebox access to random seeds feels like a powerful assumption for federated learning. If the adversary can access the random seeds, it can probably go a step further (in data manipulation or code control) or even adversarially pick seeds. 

4. This work assumes that the victim relies on using the parameters at any given iteration as the primary model. The victim could have a basic validation set to spot sudden drops in performance and sound the alarm (while keeping track of the model with the best validation loss). Even more simply, it could keep track of the two most recent parameters, and reject data from batch $i + 1$ if it leads to a performance drop, and use parameters from state $i$. It would be nice if the authors can analyze the effect of skipping the trigger batch in such a setting.

---

## Minor comments

1. Equation 4: are the gradient updates scaled with $\frac{1}{N}$? If not, should the gradient update not be averaged?

2. Figure 2: What is the scale of values ere? For instance, how difference is 6.7 from 6.5 for metric A or 1500 v/s 1800 on Metric B. It would be great if the authors could include a  sentence or two to give the reader a better scope about how relevant values changes are for these metrics.

3. Figure 4 (and similar figures with image grids) are too small to notice any difference, even after zooming in. Please consider using a 5x5 (or lower) grid of images with a higher DPI.

4. This work seems quite similar to [1], in the sense of how both of them aim to exploit the sequential nature of data being fed in the training pipeline for a machine-learning model. Although this work is pretty recent, it would be worthwhile to talk about it (and perhaps in some future version add comparison experiments). 
---

## References

[1] Shumailov, Ilia, et al. "Manipulating SGD with data ordering attacks." arXiv preprint arXiv:2104.09667 (2021).
limitations_and_societal_impact: ### Limitations

1. As mentioned above, the authors should also consider a victim that keeps track of the best model based on validation loss (or even training loss) and see how effective the proposed attack can be in such a setting.

2. The lack of evaluation on any other datasets makes it hard to convince the reader of the effectiveness of the proposed attack.

---

### Ideas for future work

1. I would like to see in a future version how performance changes if the trigger batch is rejected by the victim at the batch at which it is inserted and how its effectiveness decreases with more data being fed into the model.

2. The method itself is pretty clever, but the victim can very quickly identify the trigger batch here. It would be exciting to see a variant of this method that can create a 'time-bomb' of sorts - causing a sudden drop in performance after some data batches. Hence, the victim would have a more challenging time identifying culprit data.


## Update

Most concerns raised have been addressed - changed rating accordingly
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposes a poisoning attack for online/federated learning systems with the inclusion of an accumulation phase which then makes a trigger batch of poisons even more deleterious to the model. 
main_review: While I have experience with poisoning literature, I will add a disclaimer that I am not an expert at poisoning for online learning/federated learning. 

### Strengths:
* The idea of an abrupt degradation of accuracy of an online model seems like an interesting and novel threat-model. 
* The idea of "accumulating" the effects of poisons is also quite interesting. 
* The drop in accuracy of the victim model is impressive.

### Weaknesses: 
* The method should be explained more clearly and motivated in a better way. Heuristically, what's the "goal" of the accumulation poisons? 
* It's not clear what capacity the attacker has. You mention that they have an l-infinity bound on the perturbations they are allowed to make, but are they allowed to perturb each client's update? If so this seems like a very strict assumption. 
* To this end, if they are allowed to poison every update, a comparison to adaptations of other poisoning methods like the one found in Geiping et al. (cited in your work) would be in order. 
* It would be nice if you described your online learning setup a bit further. You mention a "burn in" phase for the CIFAR-10 experiments involving 40 epochs of training. Could you describe how this differs from a standard supervised routine? 


### Random Comments:
There are several grammatical errors that should be cleaned up. 
For example: 
* line 95: *becomes*
* line 115: *researches*

And a few others I forgot to mark down.
limitations_and_societal_impact: While the authors do briefly mention limitations in the appendix, it would be nice if they included a further discussion of this in the main body. They do mention that the attacker is assumed to have access to the model's parameters in the main body, but this isn't further discussed as a realistic or unrealistic assumption.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes a poisoning attack in settings where data is acquired iteratively. Two concrete settings are examined: online learning and federated learning. Under the assumed threat model, an attacker may observe the state of the learning algorithm and poison the data it consumes in each iteration. In order to evade detection, a novel attack strategy is proposed where the learned model is primed over several iterations in a so-called _accumulative phase_ without causing harm. After the accumulative phase, the attack can be activated by a special trigger data batch to cause a sudden drop in model accuracy. The attack is formulated as an optimization problem, which is ultimately relaxed and solved using projected gradient descent. Experiments are performed using CIFAR-10 to understand the power of the attack for different parameter settings and variations of the accumulative phase. The results show that the attack is effective and can more easily bypass anomaly detection and gradient clipping defenses.
main_review: This paper makes a valuable contribution to the literature on data poisoning attacks, where there has been limited work in online settings. I agree with the observation that existing online attacks are easy to detect when there is a steady drop in model performance. The proposed strategy – of discretely preparing for a sudden and powerful attack – effectively exploits the online nature of the target. And the experiments show that it is surprisingly powerful.

The paper is generally well-executed. The attacks are defendable – they are derived by relaxing a formulation of the attacker’s objective as an optimization problem. However, I did find it difficult to follow the derivation in some places – e.g. seeing how eq (9) is obtained from eqs (7) and (8). I would like to see some of the missing steps/assumptions spelled out in an appendix. I appreciated the fact that online learning _and_ federated learning were both covered – effectively as two variations of the same framework.

One area in which the paper could be improved is in clarifying the threat model. I found that assumptions were mentioned in different places, making them difficult to piece together. My understanding is that a white box setting is assumed, where the attacker has full access to the model architecture, model parameters and the ability to poison all of the data received by the learning algorithm in each batch. In other words, a powerful attacker – although this is not out of the ordinary for data poisoning papers.

I found the experiments to be comprehensive, especially given the limited space. An ablation study on attack variants for the accumulation phase shows significant differences in the power of the attack. However to get a complete picture, I’d like to see the computational resources required for each variant. I was pleased to see an evaluation of the attack under an anomaly detection defense, however I think it’s difficult to judge the results in the absence of a benign reference. In particular, I’d like to see how the metrics compare with the values computed on unperturbed (benign) data. 
Finally, I’d be interested to see an additional baseline to match the “vanilla” online poisoning referenced at the beginning of Section 3. It’s my understanding that the first row for each poisoned method in Table 1 is for a baseline where only a _single_ batch is poisoned. But what happens if an attacker continues to poison batches for the same number of iterations as the attacker running the accumulative attack? This would put the attackers on equal footing in terms of the horizon of the attack. The accumulative attack should be less powerful because its attempting to evade detection, but by how much?

Other comments:
- Line 108: Higher-order derivatives must apparently be computed for this attack, but how high? Are they capped at second-order?
- There are some unusual word choices in places e.g. retracement (L217)
- In various places, the model is said to be “irreparably broken” after an attack is launched. This sounds a little strange to me, as practical implementations of online learning would likely be able to revert to a previous checkpoint.
- For future work: it’d be interesting to develop intuition for how the model is affected by the accumulative phase of the attack. This may help in developing a defense for this attack.

limitations_and_societal_impact: Societal impact is not discussed at length, but new types of attacks are usually disclosed so that defenses can be developed.
review_title: null

Meta-review: The reviewers were overall positive regarding the paper, and they were satisfied by the rebuttal. After the discussion period, the reviewers requested for the following things to be included in the paper:

1. More description of the optimization problem in Algorithm 1.
2. A  table about the capacity of the attacker in the federated learning setting.
3. Include the additional empirical evaluations mentioned mentioned by the authors during the rebuttal period. 
Decision: Accept (Poster)