TL;DR
This paper tackles the under-explored area of data poisoning attacks in online machine learning. The authors introduce new attack strategies that exploit the sequential nature of online learning, demonstrating that these attacks are significantly more potent than those designed for offline settings. Their work highlights the vulnerability of online learners, especially those with rapidly decaying learning rates.
What Problem Does This Paper Address?
Machine learning models are increasingly deployed in critical applications, making them targets for adversarial attacks. Data poisoning is a type of attack where an adversary subtly manipulates a small fraction of the training data to corrupt the learned model. While extensive research exists on data poisoning for offline learning (where the entire dataset is available at once), the problem is much less understood for online learning. In online learning, data arrives sequentially, and models are updated incrementally. This dynamic setting presents unique challenges and opportunities for attackers, as the order of data and the continuous updates can be exploited. This paper aims to systematically investigate and develop effective data poisoning attacks tailored for online learning scenarios.
Methods
The authors formalize data poisoning for online learning into two settings: semi-online (where only the final model is evaluated) and fully-online (where model performance is continuously evaluated). They propose a general attack strategy framed as an optimization problem. To solve this, they introduce a three-step approach:
- Simplify the Objective: They smooth non-differentiable loss functions (like classification error) using convex surrogates and employ a "label inversion" technique to create an inverted validation set, effectively guiding the model towards incorrect predictions.
- Compute Gradients via Chain Rule: They develop a method to efficiently compute the gradient of the attack objective with respect to individual training data points, even though the model's state changes over time. This involves a recursive application of the chain rule.
- Strategic Search over Positions: To make attacks practical, they propose three algorithms for selecting which data points to poison:
- Incremental Attack: A greedy approach that iteratively modifies the data point with the largest gradient magnitude.
- Interval Attack: Focuses on finding the most effective consecutive sequence of data points to modify.
- Teach-and-Reinforce Attack: A hybrid strategy that first "teaches" the model with a portion of the poisoned data and then "reinforces" this teaching throughout the rest of the stream.
Datasets
The authors evaluate their attacks on four datasets:
- A synthetic 2D Gaussian mixture dataset.
- MNIST (specifically, the 1 vs. 7 classification task).
- Fashion MNIST (specifically, the sandals vs. boots task).
- UCI Spambase.
For MNIST and Fashion MNIST, dimensionality reduction was applied using random projections.
Key Insights and Ideas
- Online Learners are More Vulnerable: The study reveals that adversaries can be significantly more powerful in online settings compared to offline settings, especially when they can exploit the data's sequential nature.
- Learning Rate Matters: The choice of learning rate significantly impacts attack effectiveness. Rapidly decaying learning rates (like "Fast Decay") make online learners particularly susceptible to poisoning.
- Semi-online is Easier to Attack: The semi-online setting, where only the final model is considered, appears to be more vulnerable than the fully-online setting. This is attributed to the final model potentially relying more heavily on a smaller subset of training data.
- Attack Positions are Strategic: The attack positions are not random. Incremental and Interval attacks tend to focus on specific parts of the data stream (beginning or end, depending on the learning rate and setting), suggesting potential avenues for defense by monitoring these critical regions.
- Gradient-Based Attacks Outperform Simple Flipping: Sophisticated gradient-based poisoning attacks are far more effective than simple label-flipping strategies, underscoring the need for advanced defense mechanisms.
Key Results
- The proposed online attacks (Incremental, Interval, and Teach-and-Reinforce) consistently outperform oblivious adversaries (Offline attack) and simple label-flipping attacks across various datasets and settings.
- Teach-and-Reinforce was found to be the most effective in the fully-online setting, while Incremental and Interval attacks were most effective in the semi-online setting.
- The effectiveness of attacks varied by dataset, but generally, the proposed methods achieved substantial degradation in test accuracy with a small fraction of poisoned data.
- Table 1 summarizes the typical attack positions: "Start" for Fast Decay, "End" for Constant/Slow Decay in semi-online, and "Start" for Fast Decay and "Start/Uniform" for Constant/Slow Decay in fully-online.
Limitations and Future Work
- Classifier Complexity: The current work focuses on linear classifiers and Online Gradient Descent. Extending these attacks to more complex models like neural networks is a natural next step.
- Defense Mechanisms: The paper suggests that online methods where the classifier doesn't depend too heavily on a few input points might be more robust. Future work could investigate specific robust online learning algorithms, such as averaged stochastic gradient classifiers, and their vulnerability.
- Generalization of Attacks: While the paper proposes a general attack framework, further exploration of various attack objectives and their optimization is warranted.
- Real-world Applicability: While the attacks are shown to be effective, further research is needed to understand their practical implications and to develop effective countermeasures in real-world online learning systems.
Summary updated