Learning under p-Tampering Attacks

Saeed Mahloujifar, Dimitrios I. Diochnos, Mohammad MahmoodyarXiv 2017 · OpenReview

Abstract

In adversarial machine learning, data poisoning is typically associated with the injection of malicious noise or incorrect labels. This paper investigates a more insidious threat model known as $p$-tampering, where an attacker replaces a fraction $p$ of the training data with other correctly labeled examples from the same distribution. We analyze the limits of learnability under this "mistake-free" noise, demonstrating that while PAC learning remains possible under random $p$-tampering, the introduction of strategic choice—where the attacker selects which samples to tamper with—renders learning impossible.

Introduction

Traditional models of adversarial data poisoning often assume that an attacker injects outliers or flips labels to degrade model performance. However, such attacks are frequently detectable through data auditing or outlier detection. This research explores $p$-tampering, a stealthy, "defensible" attack where every data point provided to the learner is technically legitimate. In this scenario, an attacker intercepts training examples with an independent probability $p$ and substitutes them with other valid, correctly labeled examples from the true distribution. Because the resulting dataset contains no "wrong" data, the attack is exceptionally difficult to identify.

This paper addresses two fundamental questions:

  1. How efficiently can an attacker bias a model's loss function using only $p$-tampering?
  2. What are the theoretical boundaries for PAC (Probably Approximately Correct) learning when subjected to this mistake-free noise?

The p-Tampering Threat Model

The $p$-tampering model assumes an attacker can modify a sequence of $n$ training examples. For each example, the attacker decides whether to keep the original or replace it with a new sample from the underlying distribution. The authors distinguish between several variants of this threat:

  • Random $p$-tampering: The attacker intercepts each sample with independent probability $p$.
  • $p$-budget attacks: The attacker has a fixed budget of $p \cdot n$ samples to alter. This is further divided into weak (choosing which samples to alter without seeing their values) and strong (choosing which samples to alter after observing the data) variants.

Algorithmic Framework for Attacks

The authors develop highly efficient algorithms to execute these attacks, moving from theoretical ideals to practical polynomial-time implementations.

The Idealized Oracle

The attack strategy begins with an "Idealized Oracle." Assuming the attacker can calculate the expected future output of a target function (such as the model's loss) based on the data seen so far, they can use rejection sampling. By calculating precise probabilities to keep or resample a data point, the attacker can maximize the bias of the final model.

Polynomial-Time Approximation

Since a perfect oracle is computationally infeasible, the authors provide a polynomial-time approximation. By sampling a large number of potential "continuations" of the dataset and applying Hoeffding bounds, the attacker can estimate the oracle's output. This demonstrates that near-optimal $p$-tampering attacks can be executed efficiently, significantly biasing real-valued functions.

Theoretical Limits of PAC Learning

A central contribution of this work is the formalization of learnability boundaries under mistake-free noise.

The Resilience of PAC Learning

In many adversarial models, an attacker controlling a significant portion of the data (e.g., $>50\%$) can prevent learning entirely. Surprisingly, the authors prove that under random $p$-tampering and weak $p$-budget attacks, PAC learning is still possible for any constant $p < 1$. Because the attacker is restricted to providing valid samples, they cannot entirely erase the underlying signal of the distribution if the tampering locations are chosen independently of the data values.

The Impossibility of Learning under Strong Attacks

However, a "theoretical cliff" exists when the attacker is granted the power of choice. In a strong $p$-budget attack, where the attacker strategically chooses which specific samples to replace after seeing the data, the authors prove that PAC learning becomes impossible. This establishes a hard limit on algorithmic robustness: even if every individual data point is "correct," the ability to strategically curate the dataset is sufficient to defeat any learning algorithm.

Key Results and Metrics

  • Biasing Efficiency: The proposed polynomial-time attack biases bounded real-valued functions by approximately $\frac{p \cdot \nu}{1 + p \cdot \mu - p}$, where $\mu$ is the mean and $\nu$ is the variance. This is a significant improvement over previous, more computationally expensive methods.
  • p-Resetting: In a restricted case where the attacker can only choose to keep a sample or draw a fresh one (without searching for a specific replacement), they achieved a bias of $\frac{p \cdot \nu}{1 + p \cdot \mu}$.
  • Learnability Proofs: The research confirms that problems PAC-learnable in clean settings remain learnable under random $p$-tampering, provided the realizability assumption holds.

Conclusion and Future Work

This research highlights that data poisoning does not require "bad" data to be effective; the selective manipulation of "good" data is a potent threat. While PAC learning is robust against random tampering, it collapses under strategic, data-dependent tampering.

Future research may focus on relaxing the realizability assumption—the requirement that a perfect hypothesis exists within the model class—to explore agnostic learning under $p$-tampering. Additionally, while these bounds apply to all PAC learners, investigating the vulnerability of specific architectures, such as deep neural networks, could yield tighter practical bounds.

Summary updated

Abstract

Recently, Mahloujifar and Mahmoody (TCC'17) studied attacks against learning algorithms using a special case of Valiant's malicious noise, called $p$-tampering, in which the adversary gets to change any training example with independent probability $p$ but is limited to only choose malicious examples with correct labels. They obtained $p$-tampering attacks that increase the error probability in the so called targeted poisoning model in which the adversary's goal is to increase the loss of the trained hypothesis over a particular test example. At the heart of their attack was an efficient algorithm to bias the expected value of any bounded real-output function through $p$-tampering. In this work, we present new biasing attacks for increasing the expected value of bounded real-valued functions. Our improved biasing attacks, directly imply improved $p$-tampering attacks against learners in the targeted poisoning model. As a bonus, our attacks come with considerably simpler analysis. We also study the possibility of PAC learning under $p$-tampering attacks in the non-targeted (aka indiscriminate) setting where the adversary's goal is to increase the risk of the generated hypothesis (for a random test example). We show that PAC learning is possible under $p$-tampering poisoning attacks essentially whenever it is possible in the realizable setting without the attacks. We further show that PAC learning under "correct-label" adversarial noise is not possible in general, if the adversary could choose the (still limited to only $p$ fraction of) tampered examples that she substitutes with adversarially chosen ones. Our formal model for such "bounded-budget" tampering attackers is inspired by the notions of (strong) adaptive corruption in secure multi-party computation.
BibTeX
@misc{mahloujifar2017learning,
  author = {Saeed Mahloujifar and Dimitrios I. Diochnos and Mohammad Mahmoody},
  title = {{Learning under p-Tampering Attacks}},
  year = {2017},
  eprint = {1711.03707},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1711.03707},
}
Figure