Stronger data poisoning attacks break data sanitization defenses

1. 01What problem does this paper attempt to solve?

   The authors study whether data poisoning attacks explicitly designed against anomaly detection can bypass common data sanitization defenses.

   Core question: can the data sanitization defense (filtering out anomalous training points before training) be bypassed by data poisoning attacks specifically designed against it? The authors' answer is yes.

   • Scenario and importance: ML systems in high-risk scenarios (autonomous driving, biometrics, cybersecurity) are often trained on external data, and an attacker only needs to create an account to inject malicious data (Introduction).
   • Shortcomings of existing methods: the authors state that most existing poisoning attacks only optimize the attack budget and input domain constraints and do not explicitly evade defenses, so in their experiments these data sanitization defenses defeated all existing attacks tested (Introduction).
   • Core observation: the authors consider anomaly detectors to fall into two categories—those sensitive to a small number of points (such as k-NN) can be fooled by concentrated poisoning points; parametric, insensitive ones (such as L2) require writing the defense as a constraint to evade it (Section 3).
   • The paper proposes: three attacks (influence, KKT, min-max), all based on the two ideas of concentrated poisoning and constrained optimization, and gives a theoretical result: for 2-class SVM and logistic regression, 2 distinct poisoning points suffice to achieve an arbitrary attack (Theorem 1).
   • Threat model:
     • Goal: make the parameters θ̂ learned by the defender have a high 0-1 error rate on the test set (indiscriminate attack, test set and training set are from the same distribution).
     • Knowledge: the attacker knows the test set Dtest, the clean training set Dc, and the defender's training pipeline; the authors state that this is a conservative assumption under the security by design principle (Section 2.1).
     • Capability: can only add εn poisoning points (ε=3% in the experiments), and can control features and labels.
     • Victim system: the defender filters with one of 5 anomaly detectors (L2, slab, loss, SVD, k-NN) and then trains a linear classifier (SVM / logistic regression).

   Collapse this answer

2. 02What related research exists?

   Related work covers gradient-based poisoning attacks, other attack settings (label-flip, targeted, backdoor, clean-label), and defenses (trusted data, robust estimation, certified defenses).

   Gradient-based data poisoning attacks

   • Biggio et al. (2012b)—first formulated poisoning attacks on SVMs as an optimization problem and solved it with gradient methods; Mei and Zhu (2015b) and subsequent work refined it and extended it to linear/logistic regression, topic models (Mei and Zhu, 2015a), collaborative filtering (Li et al., 2016), and neural networks (Koh and Liang, 2017; Yang et al., 2017; Muñoz-González et al., 2017).
   • Koh and Liang (2017)—used influence functions to compute gradients of poisoning points; the influence attack in this paper is based on it and adds centering and rounding techniques.
   • Steinhardt et al. (2017)—proposed the min-max-basic attack and certified defenses; the authors point out that this attack is efficient but cannot evade the loss defense, and this paper improves it with a decoy parameter to obtain the min-max attack.

   Other attack settings (Section 7.1)

   • Label-flip attacks (Biggio et al., 2011; Xiao et al., 2012, 2015)—control only the labels; the authors experiment in Appendix D with the alfa variant of Xiao et al. (2012) and state that its effect is significantly weaker than the attacks in this paper, arguing that controlling the features x̃ is necessary.
   • Targeted and backdoor attacks (Gu et al., 2017; Chen et al., 2017; Shafahi et al., 2018, etc.)—target specific test samples or backdoor patterns and make weaker assumptions about attacker knowledge; this paper does an indiscriminate attack that requires knowledge of the model and training set.
   • Clean-label attacks (Shafahi et al., 2018; Suciu et al., 2018)—the labels of poisoning points look correct to humans; the authors explain that the attacks in this paper are not clean-label, but the poisoning points are designed to fool automatic anomaly detectors.

   Defenses (Section 7.2)

   • Using labeled anomaly data or metadata (Hodge and Austin, 2004; Cretu et al., 2008)—Cretu et al. coined the term data sanitization and used timestamp information for filtering.
   • Defenses based on trusted data: RONI (Nelson et al., 2008) and the anomaly detector of Paudice et al. (2018) (similar to the k-NN in this paper but measuring distance only to a trusted subset).
   • High-dimensional robust estimation (Klivans et al., 2009; Diakonikolas et al., 2016, 2017a, 2018, etc.) and certified defenses (Steinhardt et al., 2017); the authors state that the latter are effective for L2/slab certification on MNIST-1-7 and Dogfish, consistent with the experimental results in this paper.

   Baselines and benchmarks: the comparison baselines are the min-max-basic attack and the influence-basic attack (no LP relaxation, no centering) of Steinhardt et al. (2017), as well as the alfa label-flip attack in Appendix D; the benchmarks are Enron, IMDB, MNIST, MNIST-1-7, and Dogfish (Table 1).

   The authors position this paper as follows: existing attacks do not explicitly account for defenses, and existing defenses are only tested against basic attacks; this paper advances both sides at once—attacks must account for defenses, and defenses must also be tested against attacks specifically designed to evade them (Section 1).

   Collapse this answer

3. 03How does the paper address this problem?

   The three attacks share two ideas: poisoning points are placed in a concentrated manner to fool sensitive detectors, and the attack is formulated as an optimization problem with defense constraints and solved approximately in three ways.

   Overall approach: formulate the poisoning attack as a constrained optimization problem that maximizes test loss under defense constraints, use concentrated poisoning to evade sensitive detectors, and then solve this bilevel problem with three approximation methods (influence, KKT, min-max).

   Problem formulation and defense model

   • The defender uses a scoring function sβ to measure the degree of anomaly, discards points outside the highest-scoring τy per class (in the experiments, p=5% discarded per class), and then minimizes the regularized training loss on the remaining data (Equation (2)).
   • 5 defenses: L2 (distance to class center), slab (projection along the direction connecting class centers), loss (loss of a model trained on all data), SVD (component outside a low-rank subspace, taking the smallest k such that the normalized Frobenius error <0.05), k-NN (distance to the k-th nearest neighbor, k=5) (Section 2.2).
   • The attacker's constrained optimization problem: max_Dp L(θ̂; D_test), subject to |D_p|=ϵ|D_c|, D_p ⊆ F_β, where θ̂ is obtained by training on the combined data (Equation (4)); that is, the poisoning points must lie within the defender's feasible set.

   Concentrated poisoning and theoretical guarantees

   • For detectors sensitive to a small number of points, such as k-NN, SVD, and loss, placing poisoning points at a small number of locations can make them appear normal (Section 3.1).
   • Theorem 1: If the feasible set for each class is convex, then for 2-class SVM and logistic regression, any reachable parameter can be realized with 1 poisoning point per class, 2 distinct poisoning points in total; the proof uses the Carathéodory number (Appendix A), and the multiclass SVM generalization is k(k−1) points (Proposition 10).

   Handling integer constraints

   • For non-negative integer features such as word counts, first relax to real values to solve, then perform randomized rounding (preserving the expectation); two new techniques are added: after rounding, repeat each point r times (in practice r=2 or 3) to preserve concentration; for the L2 defense, use an LP relaxation to directly control the expected squared norm after rounding (Equation (8), Figure 2 gives the piecewise linear representation).

   Three attacks

   • Influence attack (Section 4.1): perform projected gradient ascent on each poisoning point, with the gradient estimated in closed form using influence functions (inverse Hessian-vector product), projecting back to the feasible set at each step; the improved version optimizes only 2 distinct points and adds an LP relaxation. The authors state that it is slow and may get stuck in local minima.
   • KKT attack (Section 4.2): first use a heuristic to find the decoy parameter θdecoy—obtained by flipping the labels of high-loss points in the test set, adding them to the training set, and training (Algorithm 3, scanning threshold γ and repetition count r); then find poisoning points that make θdecoy the optimal solution of the training loss, using the KKT optimality conditions to write the inner optimization as equations, reducing it to a convex problem for hinge loss and performing a grid search over ε+/ε− (Equation (17), Algorithm 4). The decoy parameter is also used to write the loss defense as a constraint.
   • Min-max attack (Section 4.3): following Steinhardt et al. (2017), approximate the test loss with the training loss to reduce the bilevel problem to a saddle-point problem, iteratively adding the point with the highest loss within the feasible set; the improvement in this paper is to add the constraint (θdecoy; x, y) ≤ τ using the decoy parameter (in the experiments τ=0.25), so that poisoning points have low loss under the decoy parameter to evade the loss defense; no grid search is needed, and it can handle multiclass and non-convex feasible sets, but assumes the indiscriminate setting.

   Evaluation method

   • The attack is evaluated separately against each defense, taking the minimum increase in test error rate across all defenses; the attack's feasible set is the intersection of the L2 and slab feasible sets (KKT/min-max also incorporate the loss constraint), simulating an attacker who does not know in advance which defense the defender uses (Section 5.2).

   Collapse this answer

4. 04What experiments did the paper conduct?

   On Enron/IMDB, the three attacks bypass all 5 defenses with 3% poisoning, and transferability, ablation, and multiclass experiments were also conducted.

   Experimental Setup

   • Models under test: linear SVM (hinge loss + L2 regularization, λ selected by cross-validation on clean data) for binary classification; multiclass SVM (Crammer and Singer, 2002, trained with AdaGrad) for MNIST; logistic regression for the defender variants in Section 6.3.
   • Datasets (Table 1): Enron (n=4137, d=5116, baseline error rate 2.9%), IMDB (n=25000, d=89527, baseline 11.9%), MNIST (10 classes, baseline 7.5%), MNIST-1-7 (baseline 0.7%), Dogfish (baseline 1.3%); Enron/IMDB features are non-negative integers.
   • Attack budget: ε=3% poisoning points; the defense threshold is set to discard p=5% of the data per class (Section 5.2).
   • Baselines: influence-basic (no LP relaxation, no centering), min-max-basic (Steinhardt et al., 2017, no decoy parameter), alfa label-flip attack (Appendix D).
   • Metrics and evaluation: 0-1 test error rate; each attack is evaluated against 5 defenses separately, reporting the error rate under each defense; no LLM review or human evaluation.
   • Number of repetitions: the paper does not report the number of repeated experiments or variance.

   Main Results

   According to Table 2 (Enron, ε=3%; time is that required to reach 17% test error rate):

   Attack	Enron test error rate	Time
   Influence	18.3%	17,000s
   KKT	22.5%	27s
   Min-max	23.7%	1,700s

   • The abstract reports: 3% poisoning raises the Enron test error rate from 3% to 24% and IMDB from 12% to 29% (Figure 3 plots bars separately by defense; the numbers in the text are the overall results under each defense).
   • The authors state that KKT and min-max are slightly higher than influence on Enron, are much more computationally efficient, and can run on large-scale data such as IMDB (influence was not run on IMDB because it was too slow).
   • The authors state that existing attacks that do not account for defenses are defeated by these data sanitization defenses (Introduction, the min-max-basic comparison in Section 5.6).

   Transferability: Incomplete Attacker Information (Section 6, Enron)

   • Unknown test set: when optimizing with the training set instead of the test set, influence reaches 10.9% (18.3% when the test set is known), KKT 16.5% (vs. 22.6%), min-max 19.0% (vs. 23.7%) (Figure 9); the authors believe influence overfits the test set more strongly.
   • Changes in the defender's regularization strength (attacker fixes λ=0.09, defender λ from 0.009 to 0.9): against the L2 defense, influence is below 10% at λ=0.009, while min-max still reaches 22%; the authors state that increasing regularization instead makes it harder for the defender to fit the poisoning points and makes it more vulnerable to attack (Figure 10).
   • Changes in optimization algorithm and loss (single-pass SGD, logistic loss): except for the loss defense, the three attacks remain effective, and the loss defense can significantly reduce the damage; the authors recommend that attackers take a conservative value for the loss threshold (Figure 11).

   Ablations and Multiclass

   • Influence ablation (Figure 6, Enron): removing the LP relaxation lowers the error rate by a few percentage points; after also removing centering (i.e., influence-basic), many points are filtered out by the loss and SVD defenses, and the error rate under these two defenses does not exceed 11%.
   • Min-max ablation (Figure 7, Enron): min-max-basic without the decoy parameter is defeated by the loss defense (test error rate 10.0%), while with the decoy parameter it can evade it.
   • Multiclass (Figure 8, MNIST, ε=3%): the min-max attack reaches 15.2% test error rate against the L2 defense and 13.7% against the loss defense.

   Other Ablations and Analyses

   • Iteratively updating the feasible set (Algorithm 1): on Enron it only raises the error rate by a few percentage points (Figure 5); on MNIST-1-7 at ε=0.3 the iterative version improves by 7.5% vs 1.1% for the non-iterative version.
   • MNIST-1-7 and Dogfish (Appendix C, Figure 12): the influence attack raises Dogfish from 1% to 8% and has almost no effect on MNIST-1-7; the authors point out that this is consistent with the certification results of Steinhardt et al. (2017).
   • alfa label-flip attack (Appendix D, Enron, L2 defense only): ε=3% improves by only 2%, whereas the attacks in this paper improve by 15%–20%.
   • Under the high ε=0.3 setting, the influence attack in this paper is weaker on MNIST-1-7 than the 39% improvement of Steinhardt et al. (2017); the authors state that this may be due to step size or initialization issues, and may also reflect the weakness of iterative optimization at high ε (Section 5.4 footnote).

   Collapse this answer

5. 05What are some points that can be further explored?

   The authors list open questions such as non-convex models, the decoy heuristic, and stronger defenses; the experiments are limited to linear models, 5 datasets, and ε≤3%.

   Limitations and future directions noted by the authors

   • Non-convex models: The attack assumes both attacker and defender can globally minimize the training loss; whether it remains effective for non-convex models is an open question (Section 8, Non-convex models).
   • Decoy parameter heuristic: KKT and min-max rely on the decoy parameter; the authors state that this heuristic may fail under more complex defenses (Section 8, discussion of Table 2).
   • Dataset differences: Attack effectiveness varies by dataset (Enron/IMDB are vulnerable, MNIST-1-7/Dogfish are not); the authors conjecture this is related to dimensionality and linear separability, but state it warrants further study (Section 8).
   • Stronger defense strategies: The authors discuss directions such as generative model detection, training on subsets of multiple models, bounded non-convex loss surrogates, and provable robust estimation, along with the difficulties of each, and state that provable security is the gold standard (Section 8, Strategies for stronger defenses).
   • Attacking new defenses: The authors propose attacking the robust algorithm of Diakonikolas et al. (2018) to test its robustness, and explore using the improvements in this paper to derive tighter certified upper bounds (Section 7.2).

   Scope of experiments

   • The models tested are linear SVM, logistic regression, and multiclass SVM, all convex models (Section 2.1, 5.2).
   • The datasets are Enron, IMDB, MNIST, MNIST-1-7, and Dogfish, 5 in total (Table 1).
   • Defense evaluation covers 5 anomaly detectors: L2, slab, loss, SVD, k-NN (Section 2.2).
   • The main experiments use a poisoning rate of ε=3%, and the defender discards 5% of the data per class; only Section 5.4 includes a set of experiments with ε=0.3 on MNIST-1-7.
   • The paper does not report the number of experimental repetitions or variance; the transferability experiments are conducted only on Enron (Section 6).

   Collapse this answer

6. 06Summarize the main content of the paper

   Three poisoning attacks targeting data sanitization defenses bypass 5 defenses on Enron/IMDB with 3% poisoning; the authors call for defenses to be designed against adaptive attacks.

   A data poisoning attack paper: targeting the data sanitization defense of "filter out anomalies first, then train," the authors propose three attacks that can simultaneously evade multiple anomaly detectors.

   • Problem: existing poisoning attacks do not explicitly account for defenses, and the authors state that in their experiments data sanitization defenses defeat all existing attacks tested; this paper asks whether attacks specifically designed to evade anomaly detection can break through such defenses.
   • Method: two ideas—concentrate poisoning points in a few locations (theoretically, for 2-class SVM/logistic regression only 2 distinct points are needed, Theorem 1) to fool sensitive detectors; formulate the attack as an optimization problem with defense constraints, solved approximately using influence functions (influence), KKT conditions plus a decoy parameter (KKT), and a saddle-point problem plus a decoy parameter (min-max); integer features are handled with randomized rounding plus LP relaxation.
   • Main results: ε=3% poisoning raises the Enron test error rate from 3% to 24% and IMDB from 12% to 29% under 5 defenses (L2, slab, loss, SVD, k-NN) (abstract); on Enron, influence/KKT/min-max reach 18.3%/22.5%/23.7% respectively (Table 2).
   • Efficiency and scaling: KKT reaches 17% error rate in only 27s (influence requires 17,000s); min-max supports multiclass, reaching 15.2% against the L2 defense on MNIST.
   • Transferability: the attacks mostly remain effective with an unknown test set, changes in regularization strength, or switching to SGD or logistic loss, but the loss defense can significantly weaken all attacks under the latter two changes (Section 6).
   • Authors' conclusions: poisoning points need not look anomalous or have high loss, and increasing regularization may instead help the attacker; defenses must be tested against attacks specifically designed to evade them, and the authors call for developing more robust defenses.

   Collapse this answer

Related papers