PaperlayerView exact revision on arXiv

Source-linked AI summary

Stronger Data Poisoning Attacks Break Data Sanitization Defenses

Pang Wei Koh, Jacob Steinhardt, Percy Liang

arXiv:1811.00741v2stat.MLcs.CRcs.LG

TL;DR

Data poisoning threatens models trained on outside-world data, and naive attacks can be removed by sanitization. This paper develops three coordinated, constrained attacks that approximate an expensive bilevel problem and evade common defenses. The attacks substantially increase test error with only a small poisoned-data fraction, motivating defenses that account for coordinated attackers.

  • Problem

    Models trained on outside-world data are vulnerable to injected malicious points, while attacks that do not account for sanitization can be defeated by defenses.

  • Method

    The paper develops three defense-aware attacks using coordinated poisoned points and constrained approximations based on influence functions, KKT conditions, and min-max optimization.

  • Results

    The three attacks evade common sanitization defenses and significantly increase test error on the Enron and IMDB datasets.

  • Takeaways & Limitations

    Robust data-poisoning defenses must account for attackers that coordinate poisoned points and explicitly target the defenses.

  • Takeaways & Limitations

    The attacks rely on globally minimizing training loss, an assumption that is reasonable for convex losses but problematic for most practical non-convex models.

Abstract

from arXiv · show

Machine learning models trained on data from the outside world can be corrupted by data poisoning attacks that inject malicious points into the models' training sets. A common defense against these attacks is data sanitization: first filter out anomalous training points before training the model. In this paper, we develop three attacks that can bypass a broad range of common data sanitization defenses, including anomaly detectors based on nearest neighbors, training loss, and singular-value decomposition. By adding just 3% poisoned data, our attacks successfully increase test error on the Enron spam detection dataset from 3% to 24% and on the IMDB sentiment classification dataset from 12% to 29%. In contrast, existing attacks which do not explicitly account for these data sanitization defenses are defeated by them. Our attacks are based on two ideas: (i) we coordinate our attacks to place poisoned points near one another, and (ii) we formulate each attack as a constrained optimization problem, with constraints designed to ensure that the poisoned points evade detection. As this optimization involves solving an expensive bilevel problem, our three attacks correspond to different ways of approximating this problem, based on influence functions; minimax duality; and the Karush-Kuhn-Tucker (KKT) conditions. Our results underscore the need to develop more robust defenses against data poisoning attacks.

1. Introduction

Data poisoning can corrupt models trained on outside-world data, while existing sanitization defenses can defeat naive attacks but not attacks designed to evade them. The paper develops coordinated, constrained attacks that bypass common defenses and substantially increase test error with little poisoned data.

  • Attack strategies: The attacks formulate test-loss maximization as constrained optimization, with constraints designed to ensure poisoned points evade the defenses.The constraints also accommodate valid input-domain requirements, including integer-valued features in natural-language data.
  • Contribution: 3% poisoned data increases Enron test error from 3% to 24% and IMDB test error from 12% to 29% despite data sanitization defenses.The attacks target nearest-neighbor, training-loss, singular-value-decomposition, and class-centroid defenses.
  • Attack strategies: Attackers can evade nearest-neighbor-style detectors by concentrating poisoned points near one another, making each point appear normal.The strategy exploits detectors that are sensitive to isolated anomalous points.
  • Methods: Three approximations address the expensive bilevel attack problem: influence functions, decoy parameters with KKT conditions, and a min-max formulation.The influence attack optimizes a few distinct point locations; KKT and min-max attacks use decoy parameters to reduce computational difficulty.
  • Findings: Regularization can increase susceptibility to poisoning because stronger regularization makes the defender less able to fit the small fraction of poisoned points.Thus, regularization is not uniformly protective in this setting.
  • Implications: Robust defenses must account for coordinated, defense-aware attackers rather than relying only on anomaly detection tuned to independently generated anomalous points.The paper frames attack and defense design as an adaptive interaction.

2. Problem Setting and Defenses

The setting is a classifier trained after a defender sanitizes a mixture of clean and attacker-injected data. Defenses score points for anomalousness, retain those within a feasible set, and train a regularized model on the survivors.

  • General setting: The attacker adds εn poisoned points to clean training data, while the defender filters the combined dataset before learning the classifier.The attacker seeks high test error, whereas the defender seeks low 0-1 test error.
  • General setting: The attacker is assumed to know the test set, defender’s training procedure, and clean training data.These assumptions create a security-by-design evaluation against a well-informed attacker.
  • Assumptions: The experiments focus on linear classifiers and indiscriminate attacks, with test data drawn from the clean-data distribution.The authors also report that strong indiscriminate attacks remain possible without knowing the test data.
  • Defenses: Anomaly scores are functions of data points and detector parameters, which may summarize the dataset or comprise the entire dataset.For k-NN, the score is the distance to the k-th nearest neighbor, with k = 5 in the experiments.
  • Sanitization pipeline: A defense fits anomaly-detector parameters, defines a feasible set using class-specific thresholds, removes points outside it, and minimizes regularized training loss on the remainder.The feasible set incorporates both defense rules and valid input-domain constraints.
  • Defenses: The five defenses include class-centroid L2 and slab rules, a loss-based rule, an SVD low-rank rule, and a k-nearest-neighbor rule.The L2 defense uses all feature dimensions, whereas the slab defense uses the centroid-direction projection.

3. Attack Framework

The attack framework combines concentrated poisoned points with constrained optimization to evade anomaly detectors while increasing test loss. Convexity results show that two distinct points can suffice for binary SVMs and logistic regression under stated conditions.

  • The attacker seeks poisoned points that cause high test error while avoiding anomaly detection during sanitization.
  • Concentrated attacks: Concentrating poisoned points helps evade sensitive anomaly detectors, including k-NN, SVD, and loss-based defenses.Nearby points have small nearest-neighbor distances; concentration can also reduce out-of-projection components and encourage the model to fit them collectively.
  • Concentrated attacks: Concentrated attacks may appear less efficient because spreading points could seem to require fewer poisoned examples.
  • Concentrated attacks: Two distinct poisoned points suffice for binary SVMs and logistic regression when each class-specific feasible set is convex.The result applies to attacks attainable with any number of poisoned points, replacing them with at most two distinct points, one per class.
  • Constrained optimization: The framework formulates the attacker’s goal as constrained optimization under a poisoning budget, sanitization constraints, and the defender’s training-loss optimum.The formulation approximates the problem by retaining all clean points, fixing the anomaly detector on clean data, and replacing 0-1 error with a convex surrogate.
  • Constrained optimization: The resulting constrained bilevel problem remains non-convex and intractable to solve exactly, motivating more efficient attack methods.

4. Specific Attacks

The paper develops three concentrated attacks for solving the constrained poisoning problem: influence, KKT, and min-max methods. They trade direct optimization for approximations that improve evasion, computational efficiency, or applicability across settings.

  • 4. Specific Attacks: Three attack methods solve the constrained poisoning problem using different approximations: influence functions, KKT conditions, and min-max optimization.
  • 4.1 The influence attack: The influence attack uses projected gradient ascent, repeatedly updating poisoned features and projecting them onto the feasible set.It uses influence functions to estimate how poisoned features change the learned parameters and test loss.
  • 4.1 The influence attack: Randomized rounding and attack concentration improve the influence attack for integer inputs and make it stronger and more computationally efficient.
  • 4.1 The influence attack: The influence attack is slow in high dimensions and can become trapped in poor local minima because each iteration requires an inverse Hessian-vector product and feasible-set projection.
  • 4.2 The KKT attack: The KKT attack first chooses high-test-error, low-training-error decoy parameters, then finds poisoned data that induces the defender to learn them.
  • 4.3 The min-max attack: The min-max attack incorporates decoy parameters, naturally handles multi-class problems without grid search, and does not require convex feasible sets.Its stated drawback is the assumption that clean and test data are drawn from the same distribution.

5. Experiments: Attackers with complete information

The experiments evaluate three attacks across binary and multi-class datasets, under limited poisoning and multiple sanitization defenses. The attacks successfully degrade test performance, with KKT and min-max offering strong effectiveness and computational advantages.

  • Datasets: The experiments use Enron, IMDB, and MNIST, with Enron and IMDB requiring non-negative integer inputs and MNIST representing a multi-class setting.Enron and IMDB are binary text-classification datasets; IMDB is substantially larger and higher-dimensional.
  • Experimental setup: The attacker adds at most ϵ = 3% poisoned data while the defender removes p = 5% of training data from each class.Attacks are evaluated by their minimum test-error increase across five defenses.
  • Main results: All three attacks succeed against the evaluated defenses, and KKT and min-max achieve slightly higher Enron test error than influence while also running on IMDB.The attacks are designed to evade all defenses because the attacker may not know which defense will be deployed.
  • Efficiency: The KKT attack reaches 17% Enron error in 27 seconds, whereas the influence attack takes 286 minutes to reach that error level.The min-max attack reaches 23.0% error after processing its first decoy parameter in 28 minutes.
  • Iterative optimization: Iteratively updating the feasible set improves Enron test error by only a few percentage points at ϵ = 3%, because poisoning barely shifts the class centroids.The slab defense is more affected at larger poisoning rates, which are outside the paper’s main setting.
  • Influence ablations: Removing LP relaxation lowers achieved test error by a few percentage points, while removing concentration causes substantial degradation and leaves influence-basic below 11% under loss and SVD defenses.Without concentration, many poisoned points are filtered out by those defenses.

6. Experiments: Attackers with incomplete information

The attacks generally remain effective when attackers lack test-set knowledge or when optimization and loss functions change, but loss-based defenses are notably sensitive to these shifts. Regularization changes affect attacks differently, with min-max often more robust than influence.

  • Unknown test data: Attacks still significantly increased test error when optimized without knowledge of the test set, though influence was less effective than KKT and min-max.Without test-set knowledge, influence reached 10.9% versus 18.3% with test-set knowledge; KKT reached 16.5% versus 22.6%, and min-max reached 19.0% versus 23.7%.
  • Regularization: Under the L2 defense, test error generally increased with defender regularization because the same poisoned points led to different learned parameters.The L2 feasible set depends only on poisoned-point locations, not on the defender’s learned model parameters.
  • Regularization: At λ = 0.009, influence produced less than 10% test error against L2, whereas min-max remained effective at 22% test error.The influence attack became less effective as defender regularization decreased, while min-max was robust to this change.
  • Regularization: Increasing regularization can strengthen the loss defense by causing previously undetected poisoned points to be detected under the changed model.The min-max attack initially became more effective against the loss defense as λ increased from 0.09, partly because it uses a fixed loss threshold.
  • Optimization assumptions: The experiments assume globally optimized model parameters, so practical stochastic optimization and early stopping may produce parameters that differ from those analyzed.The paper reports that attacks remain effective under some optimization changes, but loss-based defenses pose problems when optimization or loss functions change.
  • Optimization and loss shifts: Across changes in optimization algorithm and loss function, all attacks remained effective except against the loss defense.The loss defense significantly reduced attack damage when the defender used a single stochastic-gradient pass or logistic loss instead of the original optimization and hinge-loss settings.

7. Related Work

Related work distinguishes train-time poisoning from test-time attacks and separates indiscriminate, targeted, label-flip, and clean-label settings. The paper’s attacks specifically evade automatic outlier detectors, unlike clean-label attacks that target human judgment.

  • Poisoning attack types: Label-flip attacks modify poisoned labels but not input features, and were significantly less effective than the proposed attacks against sanitization defenses.The authors conclude that controlling poisoned features appears necessary for high-leverage attacks in this setting.
  • Targeted vs. indiscriminate attacks: Indiscriminate attacks increase error across much of the data distribution, whereas targeted attacks focus on specific examples or small subpopulations.The paper’s experiments use indiscriminate attacks, with the test set drawn from the same distribution as clean training data.
  • Targeted vs. indiscriminate attacks: Influence and KKT attacks can handle targeted attacks without modification, while min-max requires the indiscriminate setting because it approximates test error with training error.This distinction follows from the min-max attack’s assumption that training error is a good proxy for test error.
  • Clean-label attacks: Clean-label attacks preserve labels that appear correct to human observers, whereas the proposed attacks are designed to evade automatic outlier detectors.The paper notes that clean-label points may fool humans while still appearing as statistical outliers to automated defenses.
  • Adversarial examples and test-time attacks: Data poisoning changes training data to affect the learned model, unlike test-time attacks that perturb test examples while leaving training data and the model unchanged.Poisoning is harder to attack and defend because it depends on the entire training set rather than only on learned parameters.
  • Additional defender information: Many effective defenses use additional information, such as labeled outliers or trusted datasets, but collecting enough trusted data may be expensive or impossible.The paper identifies whether a small trusted dataset can defeat attackers without rejecting clean points as an open question.

8. Discussion

The paper compares three attack strategies, their speed, robustness, and scope, and identifies important unresolved limitations. It concludes that sanitization defenses must be evaluated against attackers explicitly designed to evade them.

  • Attack comparison: The influence, KKT, and min-max attacks respectively optimize test loss directly, target decoy parameters, and maximize training loss as a test-loss proxy.These are three distinct approximations to the poisoning objective.
  • Attack comparison: Influence is direct but slow and less robust, KKT is faster but depends on decoy parameters, and min-max is more robust but slower and limited to indiscriminate attacks.Min-max also handles multi-class settings more efficiently, while KKT’s decoy-parameter heuristic may fail against more sophisticated defenses.
  • Implications: More sophisticated sanitization defenses might defeat these attacks, although defense-specific attacks could potentially bypass those defenses in turn.The paper argues that defenses should be tested against attackers explicitly designed to evade them.
  • Open questions: Attack effectiveness varies substantially across datasets, and the paper leaves the causes of this variation as an open question.The authors speculate that higher dimensionality and weaker linear separability may make Enron and IMDB more vulnerable.
  • Limitations: A key limitation is reliance on globally minimizing training loss, leaving effectiveness in non-convex models unresolved.The authors note that random seeds or bad local minima may substantially change poisoning outcomes.
  • Robust defense strategies: Convex loss proxies are unbounded, allowing an adversary to make poisoned-point loss very large, while bounded non-convex proxies introduce harder optimization and local-minimum concerns.The paper contrasts these trade-offs with a bound on additional 0/1 error when directly minimizing training error.

Appendix A. How many distinct points are needed for data poisoning

The appendix links the minimum number of distinct poisoned points to the convex geometry of feasible gradients. Under convex feasible sets, two-class SVMs and logistic regression need only two distinct points to realize any attainable attack, while k-class SVMs need at most k(k −1).

  • General characterization: An attacker constrained to the feasible set F may need more distinct points than an unconstrained attacker who can place points arbitrarily far away.The feasible-set constraint prevents the high leverage available from unbounded loss models and distant poisoned points.
  • Binary models: 2 distinct points suffice for binary SVMs and logistic regression when each class’s feasible set is convex.The construction uses one poisoned point from each class, possibly with fractional repeats.
  • Assumptions: The analysis assumes a strictly convex training objective and poisoned points contained in the defender’s feasible set.For nondifferentiable losses, the argument can be reformulated using subgradient sets.
  • General characterization: The minimum number of distinct poisoning points is characterized by the Carathéodory number of the scaled feasible-gradient set.This set contains feasible loss gradients scaled by factors between 0 and 1.
  • Binary models: For differentiable margin-based losses, convexity of the class-specific feasible-gradient sets follows under the stated conditions on c and c′′/c′.The result includes logistic regression as a special case.
  • Multiclass extension: A k-class SVM requires at most k −1 distinct feature values per class, for a total of k(k −1) distinct poisoned points.This extends the two-class result to multiclass SVMs.

B.1 The influence attack

The influence attack addresses nondifferentiable hinge loss and computational costs in influence-based bilevel optimization. It concentrates poisoning into one positive and one negative point while using smoothing and efficient Hessian-vector computations.

  • Influence optimization: The hinge loss is smoothed because its piecewise-linear derivatives make influence gradients poor guides for perturbing poisoned points.The smoothed loss converges to the hinge loss as δ → 0 while remaining differentiable for δ > 0.
  • Influence optimization: The influence attack uses fast Hessian-vector products and a conjugate-gradient solver to compute the required gradient efficiently.The attacker selects the step size by evaluating a range of options on the test set.
  • Poison construction: The attack represents poisoning with one distinct positive point and one distinct negative point.Their weights are chosen inversely to the clean-data class counts to preserve class balance on average.

B.2 The KKT attack

The KKT attack generates and prunes candidate decoy parameters, then searches poisoning-label ratios under a 3% poisoning budget. The candidates are designed to combine high test error with low training loss.

  • Decoy generation: 99 decoy candidates were generated for Enron and pruned to 48, while IMDB produced 18 candidates after pruning.The datasets used different grids of repetition counts and loss quantiles because IMDB was larger and slower to attack.
  • Label selection: With ε = 3%, the attack grid-searched seven positive-versus-negative poisoning ratios spanning the full label-budget range.The search ranged from all positive poisoned points to all negative poisoned points.

B.3 The min-max attack

The min-max attack uses a fixed loss-defense threshold in the experiments and specifies optimization settings for multiclass SVM training on MNIST.

  • Loss defense: The loss-defense threshold was set to τ = 0.25 across all experiments, with results reported as fairly robust to this choice.This threshold was used specifically to evade the loss defense.
  • Multiclass training: MNIST multiclass SVM training used AdaGrad with batch size 20, step size η = 0.02, and three passes over the training data.These settings define the multiclass training procedure used in the experiments.

Appendix C. Experiments on MNIST-1-7 and Dogfish

The influence attack substantially raises test error on Enron and Dogfish with 3% poisoned data, but has little effect on MNIST-1-7.

  • MNIST-1-7 has normalized pixel features constrained to [0, 1], whereas Dogfish features are unconstrained neural-network representations.Dogfish has n ≈ d and a low base error of 1.3%, while MNIST-1-7 has n ≫ d.
  • With ϵ = 3% poisoned data, the influence attack increases Enron test error from 3% to 23%.
  • With ϵ = 3% poisoned data, the influence attack increases Dogfish test error from 1% to 8%.
  • The influence attack does not appreciably affect MNIST-1-7 test error.MNIST-1-7 is easily linearly separable, with an SVM achieving 0.7% error on clean data.

Appendix D. Label Flip Attacks

The appendix evaluates an adapted alfa label-flip attack under data-sanitization constraints and finds only a small increase in Enron test error.

  • The alfa attack selects points with high loss under the clean model but low loss under the final model.
  • The adapted alfa attack constrains all poisoned points to the feasible set Fβ and draws them from the flipped test set.
  • With ϵ = 3% and the L2 defense, the adapted alfa attack achieves a 2% increase in Enron test error.The evaluation uses only the L2 defense to make the attack easier.
  • The introduced attacks achieve 15% to 20% increases in test error despite addressing more sophisticated defenses.
  • The alfa attack is evaluated on the Enron dataset with an L2 defense.
Loading 1811.00741v2…