Online Data Poisoning Attack

Xuezhou Zhang, Xiaojin ZhuarXiv 2019 · OpenReview

TL;DR

This paper tackles the threat of "online data poisoning," where attackers subtly alter incoming data points to manipulate machine learning models in real-time. They frame this as an optimal control problem and develop sophisticated attack strategies using model predictive control and deep reinforcement learning, demonstrating near-optimal attack performance.

What Problem Does This Paper Address?

Machine learning models are increasingly deployed in dynamic environments where data arrives sequentially (e.g., e-commerce recommendations, spam filters). This "online learning" setting presents a unique vulnerability: attackers can tamper with data as it arrives, potentially influencing the model's behavior over time. Unlike traditional "batch" poisoning attacks where an attacker poisons a fixed dataset beforehand, online attackers can adapt their strategy based on the model's current state and previous attacks. This paper addresses the challenge of understanding and developing effective online data poisoning attacks, particularly when the attacker has limited knowledge of the underlying data distribution or future data points.

Methods

The core contribution is framing online data poisoning as a stochastic optimal control problem. This allows the authors to leverage powerful control theory techniques. They propose two main algorithmic approaches:

  • Model Predictive Control (MPC): This approach involves the attacker building an empirical model of the data distribution based on observed data. At each step, the attacker plans a sequence of attacks using this estimated model (a "surrogate MDP") and then executes only the first step. This process is repeated, allowing the attacker to adapt without needing perfect knowledge of the true data distribution.
  • Deep Deterministic Policy Gradient (DDPG): This is a model-free reinforcement learning approach. DDPG learns a deterministic policy that directly maps states (model parameters and incoming data) to attack actions. This method is advantageous as it doesn't require knowledge of the victim learner's internal update function.

The paper also provides theoretical analysis to bound the attacker's suboptimality due to not knowing the true data distribution.

Datasets

The paper evaluates their methods on both synthetic and real-world datasets:

  • Synthetic Data: A mixture of two 1D Gaussians was used to visualize attack behavior.
  • Real Data:

    • Online Logistic Regression: Banknote Authentication, Breast Cancer, Cardiotocography, Sonar, and MNIST 1 vs. 7.
  • Online Soft k-means Clustering: User Knowledge, Breast Cancer, Seeds, Posture, and MNIST 1 vs. 7.

For datasets with high dimensionality, PCA was used for dimensionality reduction. All datasets were normalized and then turned into data streams by random sampling with replacement.

Key Insights and Ideas

  • Online Poisoning is a Serious Threat: The sequential and adaptive nature of online learning makes it particularly susceptible to sophisticated poisoning attacks that can evolve over time.
  • Optimal Control Framework is Powerful: Framing the attack as an optimal control problem provides a principled way to design sophisticated, near-optimal attack strategies, moving beyond simple greedy heuristics.
  • MPC Adapts to Uncertainty: Model Predictive Control effectively handles the attacker's uncertainty about the data distribution by iteratively building and refining an empirical model.
  • DDPG Offers Model-Free Robustness: Deep Reinforcement Learning (DDPG) provides a viable alternative when the attacker has even less knowledge, including not knowing the victim's learning dynamics.
  • Strategic Sacrifice for Long-Term Gain: Effective online attackers don't just minimize immediate costs; they are willing to incur larger short-term losses to achieve greater long-term manipulation of the victim model. This is a key difference from simpler greedy attacks.

Key Results

  • Both the MPC-based (NLP) and DDPG-based attack algorithms achieved near clairvoyant-level performance on synthetic and real-world datasets, significantly outperforming simple greedy attacks.
  • The clairvoyant attacker (with full knowledge) consistently achieved the lowest cumulative attack cost, serving as a lower bound.
  • The null attack (no poisoning) served as an upper bound, showing the baseline cost.
  • In synthetic experiments, NLP and DDPG demonstrated a strategy of injecting larger perturbations early on to drive the model towards the target, then stabilizing it with smaller costs later.
  • On real datasets, DDPG sometimes outperformed NLP when computational resources were limited, suggesting its advantage in avoiding iterative retraining.
  • The greedy attack consistently performed poorly, only slightly better than the null attack, highlighting the limitations of myopic decision-making.

Limitations and Future Work

  • Computational Cost: The NLP approach, while effective, can be computationally intensive, especially with longer look-ahead horizons. DDPG offers a more computationally efficient alternative in some scenarios.
  • Theoretical Bounds: While theoretical analysis is provided for the optimality gap, it relies on assumptions about the data distribution (e.g., multinomial).
  • Future Work: The paper suggests that this work lays a foundation for future studies on defense against online data poisoning. Developing robust defenses against these sophisticated adaptive attacks remains a critical area for future research.

Summary updated

Abstract

We study data poisoning attacks in the online setting where training items arrive sequentially, and the attacker may perturb the current item to manipulate online learning. Importantly, the attacker has no knowledge of future training items nor the data generating distribution. We formulate online data poisoning attack as a stochastic optimal control problem, and solve it with model predictive control and deep reinforcement learning. We also upper bound the suboptimality suffered by the attacker for not knowing the data generating distribution. Experiments validate our control approach in generating near-optimal attacks on both supervised and unsupervised learning tasks.
BibTeX
@misc{zhang2019online,
  author = {Xuezhou Zhang and Xiaojin Zhu},
  title = {{Online Data Poisoning Attack}},
  year = {2019},
  eprint = {1903.01666},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1903.01666},
}

Loading related content...

Figure