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:
- How efficiently can an attacker bias a model's loss function using only $p$-tampering?
- 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