Not All Samples Are Equal: Quantifying Instance-level Difficulty in Targeted Data Poisoning Authors WX and YL have equal contribution. Authors YW, MYRY, ZL are listed in contribution order. Authors GK and YY are listed in alphabetical order.

William Xu, Yiwei Lu, Yihan Wang, Matthew Y.R. Yang, Zuoqiu Liu, Gautam Kamath, Yaoliang Yu · 2025

Read Not All Samples Are Equal: Quantifying Instance-level Difficulty in Targeted Data Poisoning Authors WX and YL have equal contribution. Authors YW, MYRY, ZL are listed in contribution order. Authors GK and YY are listed in alphabetical order. by William Xu, Yiwei Lu, Yihan Wang, Matthew Y.R. Yang, Zuoqiu Liu, Gautam Kamath, Yaoliang Yu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-06896.txt.

Introduction

Poisoning attacks on training data look weaker once the hardest targets are graded, argue William Xu and seven co-authors in a 2025 machine learning security paper. Targeted poisoning injects malicious examples to flip predictions on chosen test samples. Published evaluations average success over randomly picked targets, which can hide true worst-case strength.

Using only information from a cleanly trained model, the authors rank test examples from easiest to hardest to poison. Coarse scores come from clean training dynamics, while finer classification uses poison distances and budgets. Experiments show these measures reliably sort samples by vulnerability. Defenders gain as much as attackers: since targeted poisoning leaves no mark on the data distribution, proactively finding the most vulnerable samples lets them apply focused countermeasures. The paper reframes both attack evaluation and defense around worst cases.

Catalog record

CREATORWilliam Xu, Yiwei Lu, Yihan Wang, Matthew Y.R. Yang, Zuoqiu Liu, Gautam Kamath, Yaoliang Yu
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE51 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-06896

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Not All Samples Are Equal: Quantifying Instance-level Difficulty in Targeted Data Poisoning Authors WX and YL have equal contribution. Authors YW, MYRY, ZL are listed in contribution order. Authors GK and YY are listed in alphabetical order. William Xu, Yiwei Lu, Yihan Wang, Matthew Y.R. Yang, Zuoqiu Liu, Gautam Kamath, Yaoliang Yu Abstract Targeted data poisoning attacks pose an increasingly serious threat due to their ease of deployment and high success rates. These attacks aim to manipulate the prediction for a single test sample in classification models. Unlike indiscriminate attacks that aim to decrease overall test performance, targeted attacks present a unique threat to individual test instances. This threat model raises a fundamental question: what factors make certain test samples more susceptible to successful poisoning than others? We investigate how attack difficulty varies across different test instances and identify key characteristics that influence vulnerability. This paper introduces three predictive criteria for targeted data poisoning difficulty: ergodic prediction accuracy (analyzed through clean training dynamics), poison distance, and poison budget. Our experimental results demonstrate that these metrics effectively predict the varying difficulty of real-world targeted poisoning attacks across diverse scenarios, offering practitioners valuable insights for vulnerability assessment and understanding data poisoning attacks. 1 Introduction In the past decade, machine learning (ML) models have achieved great success in various domains, largely due to the vast amount of training data available on the internet. However, this reliance on massive training datasets not only increases computational costs but also introduces significant security vulnerabilities during the data collection process [ SZS+14 , KNL+20 ] . Adversaries can exploit these vulnerabilities through data poisoning attacks which deliberately inject malicious samples into training data either actively or passively [ GBB+20 , Wak16 , SHKR22 , LYY20 , CJC+24 ] . These attacks are particularly concerning because they can compromise model integrity at its foundation, affecting all downstream applications and users of the poisoned model [ GTX+23 ] . Targeted data poisoning attacks represent a specialized form of this threat, where attackers aim to manipulate model behavior for specific test instances while maintaining normal performance on all other inputs [ SHN+18 , AMW+21 , GL20 , ZHL+19 , GFH+21 ] . We primarily focus on classification models (and briefly discuss generative models in Appendix D ), where the objective is to misclassify a particular sample to a predetermined class while maintaining correct predictions for all other inputs. Such attacks are difficult to detect as they leave little evidence in overall model performance metrics. Current evaluations of targeted attack threats typically rely on randomly selected test samples to report overall attack success rates [ AMW+21 , GFH+21 ] as an average assessment. However, our observations reveal substantial variation in attack effectiveness across different test instances, with no clear understanding of what characteristics drive these disparities. This paper addresses this critical knowledge gap by investigating two key research questions: (1) what factors determine why a certain test sample is more vulnerable to targeted poisoning attacks than others? and (2) can we develop reliable metrics to predict the difficulty of poisoning a specific instance? We address the first question by identifying three critical factors that influence poisoning difficulty: the inherent classification difficulty during clean training, the distance in model parameter space required to achieve poisoning, and the attacker’s resource constraints measured by poison budget. To quantify these factors, we introduce three corresponding metrics that naturally predict poisoning difficulty: (1) ergodic prediction accuracy ( EPA ) derived from clean training dynamics, (2) poisoning distance \delta , and (3) poisoning budget lower bound \tau . Importantly, all our proposed metrics can be calculated using only clean training data and processes , without requiring the simulation of actual poisoning attacks—making them practical and accessible tools for defenders to assess vulnerability and prioritize protection efforts. Our experimental results confirm that all three proposed factors strongly correlate with real-world attack performance. The metrics we developed effectively predict poisoning difficulty across various test instances, capturing different dimensions and levels of vulnerability. Specifically, we find that ergodic prediction accuracy ( EPA ) serves as a powerful indicator for distinguishing between easy-to-poison and hard-to-poison test samples. Meanwhile, poisoning distance \delta and budget lower bound \tau provide more fine-grained predictions for specific poison classes from complementary perspectives. Together, these three metrics form a comprehensive framework that enables defenders to assess poisoning vulnerability for any given test sample. In summary, our work makes three distinct contributions: (1) We identify classification difficulty during clean training, parameter-space poisoning distance, and poison budget as the key factors determining targeted poisoning vulnerability; (2) We introduce three corresponding metrics: ergodic prediction accuracy ( EPA ), poisoning distance, and budget lower bound, all calculable using only clean training processes without any expensive attack and retraining; (3) Our experiments demonstrate the effectiveness of these metrics and introduce a framework that enables defenders to clearly identify and understand instance-level difficulty in targeted data poisoning. 2 Background Threat model and notations: We first specify our threat model and list our notations below. • Objective : We consider an adversary who tries to alter the prediction of a specific test sample \mathbf{x}_{t} 1 1 1 We note that the attacker cannot change \mathbf{x}_{t} , but indirectly change the model’s behavior by deploying \mathcal{D}_{p} through retraining. We highlight this is a key difference from adversarial examples, which directly modifies x_{t} without any poisoned set or retraining. from the correct class y_{t} (or target class) to a specific poison class y_{p} . • Attack deployment : The attacker reaches the objective by injecting a poisoned set \mathcal{D}_{p} into the clean training set \mathcal{D}_{c} . We assume the defender is training a machine learning model on the merged dataset, i.e., \mathcal{D}_{tr}=\mathcal{D}_{c}\cup\mathcal{D}_{p} and deploy the model on a test set \mathcal{D}_{test} that contains \mathbf{x}_{t} . • Attacker’s knowledge : We consider a white-box attack , 2 2 2 We note that the attacks could possibly be performed in a partially black-box fashion, where the attackers need to apply surrogate models and training procedure. However, such attacks suffer a severe performance drop [ SGG+21 ] . To ensure the strongest threat is measured from the defender’s perspective to ensure maximum security, we consider the white-box setting instead. where the attacker is aware of the clean training set \mathcal{D}_{c} , the machine learning model architecture and the training scheme utilized by the defender, and the inclusion of the test sample \mathbf{x}_{t} in the test set. • Attacker’s budget & Constraint : We define the attacker’s budget as \varepsilon=\frac{|\mathcal{D}_{p}|}{|\mathcal{D}_{tr}|} , i.e., the (relative) percentage of poisoning data. The budget for targeted attacks is usually low, e.g., \varepsilon=1\% . We also set constraints on \mathcal{D}_{p} , where it only contains “clean-labeled” poison data, namely that elements in \mathcal{D}_{p} are generated by adding human imperceptible noises (e.g., with \ell_{\infty} constraints) to clean training images without changing their original labels. • Attack evaluation : We define an attack to be successful when the prediction of the target sample using the poisoned model f(\mathbf{x}_{t};\mathbf{w}_{p}) (see notation below) is equal to the poisoned label y_{p} . Note that attack success is strictly stronger than misclassification. Other notation: We denote the clean model parameters (a model f trained only on \mathcal{D}_{c} ) to be \mathbf{w}_{c}

Read the complete text