Certified Defenses for Data Poisoning Attacks

Jacob Steinhardt; Pang Wei Koh; Percy Liang

Source-linked AI summary

Certified Defenses for Data Poisoning Attacks

Jacob Steinhardt, Pang Wei Koh, Percy Liang

arXiv:1706.03691v2Jun 9, 2017cs.LGcs.CR

TL;DR

Data poisoning leaves the worst-case loss of defenses against determined attackers poorly understood. The paper constructs approximate upper bounds and nearly matching candidate attacks for outlier-removal defenses, finding resilience on MNIST-1-7 and Dogfish but a rise in IMDB error from 12% to 23% with 3% poisoned data.

Problem
The paper addresses the limited ability of empirical testing against known attacks to establish defense robustness over the near-limitless space of possible poisoning attacks.
Method
The framework analyzes outlier-removal defenses followed by margin-loss minimization, deriving approximate upper bounds and candidate attacks through duality and online learning.
Results
IMDB test error increases from 12% to 23% with 3% poisoned data, while MNIST-1-7 and Dogfish remain resilient under the oracle defense; data-dependent centroids allow 40% MNIST-1-7 error with 30% poisoning.
Takeaways & Limitations
The certificates provide a design-stage tool for assessing defenses against a large family of attacks rather than relying only on selected empirical attack tests.
Takeaways & Limitations
The framework’s upper bounds do not apply to non-convex losses because attackers may disrupt optimization and drive defenders to bad local minima.

Abstract

from arXiv · show

Machine learning systems trained on user-provided data are susceptible to data poisoning attacks, whereby malicious users inject false training data with the aim of corrupting the learned model. While recent work has proposed a number of attacks and defenses, little is understood about the worst-case loss of a defense in the face of a determined attacker. We address this by constructing approximate upper bounds on the loss across a broad family of attacks, for defenders that first perform outlier removal followed by empirical risk minimization. Our approximation relies on two assumptions: (1) that the dataset is large enough for statistical concentration between train and test error to hold, and (2) that outliers within the clean (non-poisoned) data do not have a strong effect on the model. Our bound comes paired with a candidate attack that often nearly matches the upper bound, giving us a powerful tool for quickly assessing defenses on a given dataset. Empirically, we find that even under a simple defense, the MNIST-1-7 and Dogfish datasets are resilient to attack, while in contrast the IMDB sentiment dataset can be driven from 12% to 23% test error by adding only 3% poisoned data.

1 Introduction

Data poisoning lets users corrupt models trained on external data, while existing empirical defenses provide limited assurance against unseen attacks. The paper develops approximate certificates and matching candidate attacks for outlier-removal defenses, finding strong dataset-dependent differences in vulnerability.

User-provided training data lets attackers inject malicious examples and compromise learned models.
Empirical success against known poisoning strategies cannot rule out failure against the near-limitless space of new attacks.
The framework upper-bounds attack efficacy for defenses that remove infeasible outliers before minimizing a margin-based loss, under two distributional assumptions.
A duality result produces a candidate attack that often nearly matches the bound, using an efficient online learning algorithm.
On MNIST-1-7 and Dogfish, no considered attack raises SVM 0/1-error above 4% after adding 30% poisoned data, with certified bounds of 7% and 10%, respectively.
With 3% poisoned data, IMDB test error rises from 12% to 23%, whereas a data-dependent defense can raise MNIST-1-7 error to 40% with 30% poisoning.

2 Problem Setting

The paper models poisoning as an adaptive attacker adding data to a defender’s training set and studies sanitization defenses that filter points before training. It distinguishes fixed feasible sets from data-dependent ones and uses sphere and slab centroid defenses as examples.

The causative attack game draws n clean points, lets the attacker add ϵn poisoned points, and evaluates the defender’s resulting test loss.
The attacker knows the defense algorithm and clean training data, but can add points rather than modify existing records.
The paper focuses on indiscriminate availability attacks, which increase overall test loss rather than targeting individual examples or sub-populations.
Data Sanitization Defenses: Data sanitization constructs a feasible set F and trains only on retained points, aiming to remove poisoned outliers before empirical risk minimization.
Defense Classes: Fixed defenses use an F independent of poisoned data, whereas data-dependent defenses estimate the data distribution from clean and poisoned examples.
Example Defenses: Sphere defenses remove points outside a radius, while slab defenses project points between class centroids and remove points too far along that line.
Example Defenses: The example sphere and slab defenses are oracle defenses because their class centroids depend on the true distribution, unlike versions estimated from poisoned data.
Example Defenses: Figure 1 motivates dataset-dependent vulnerability: MNIST-1-7 is constrained by separated classes, whereas IMDB appears more attackable.

3 Attack, Defense, and Duality

The framework approximates worst-case test loss by an upper-bounded minimax objective and produces candidate attacks through online learning. Fixed defenses retain duality guarantees, whereas data-dependent defenses require relaxations that weaken guarantees but can still yield useful bounds and attacks.

Approximations: The analysis replaces worst-case test loss with training-loss approximations, relying on train–test concentration and limited impact from removing clean-data outliers.Using all clean and poisoned data provides a valid upper bound, while replacing clean inliers with all clean data is accurate when the defense is not too aggressive.
Minimax formulation: The minimax loss M captures the attacker’s maximum loss over feasible poisoned points after the defender minimizes loss on the retained dataset.The attacker maximizes loss on the full dataset by adding poisoned points from the feasible set F.
Fixed defenses: For fixed defenses, no-regret online learning alternates between selecting the worst attack point and updating the model, producing both an upper bound and a candidate attack.The candidate attack supplies a lower bound, while the duality gap measures the tightness of the bounds.
Fixed defenses: Convexity and sublinear regret make the upper-bound objective amenable to online learning, with the duality gap vanishing for large datasets.Proposition 1 relates the candidate attack’s induced loss, the upper bound, and the online algorithm’s regret.
Data-dependent defenses: When the feasible set depends on poisoned data, the attacker must jointly optimize the full poison set, motivating a continuous distributional relaxation.The relaxed constraint set is non-convex, so duality no longer holds; sampling from iterated distributions nevertheless often gives useful bounds and attacks in practice.
Empirical illustration: On Dogfish and MNIST-1-7, the candidate attack reaches the worst-case train-loss upper bound, which remains below 0.1 after 30% poisoning.Gradient-descent and label-flip baselines are suboptimal under this defense.

4 Experiments I: Oracle Defenses

Experiments apply the framework to image and text datasets under oracle sphere-and-slab defenses. Image datasets remain robust, while text attacks—especially on IMDB—can substantially increase test error despite the oracle defense.

Image datasets: The experiments evaluate MNIST-1-7 and Dogfish using hinge-loss SVMs, with 13,007 and 1,800 training examples respectively.MNIST-1-7 uses 784-dimensional inputs, while Dogfish uses 2,048-dimensional Inception-v3 features.
Oracle defense: The attack maximizes hinge loss over the intersection of oracle slab and sphere constraints by solving a quadratic program for each label.The label with higher loss determines the attack point used by the algorithm.
Image results: 30% poisoning leaves the certified upper bound below 0.1 on both MNIST-1-7 and Dogfish, indicating resilience under the oracle defense.The induced clean-data loss nearly matches the upper bound because the model fits poisoned data almost perfectly.
Image results: 4% maximum test 0-1 error is observed for poisoning rates up to 30% on MNIST-1-7 and Dogfish, while the candidate attack outperforms gradient-descent and label-flip baselines.The gradient method appears to get stuck in local minima, whereas label flipping is too weak.
Attack structure: The image attack concentrates most poisoned points near a single boundary point of the feasible set, despite being allowed to place points anywhere.This visualization provides a concrete geometric pattern for the candidate attack.
Text data: Text experiments enforce binary indicator features, turning the attack optimization into an integer quadratic program that requires relaxation or approximate feasible rounding.The evaluated datasets are Enron and IMDB bag-of-words corpora with 5,166 and 89,527 distinct words respectively.
Text results: IMDB test error rises from 12% to 23% with 3% poisoned data despite the oracle defense, although a substantial gap remains between the upper bound and the candidate attack.The text datasets are easier to attack than the image datasets, and IMDB’s high dimensionality leaves the defense with few constraints.

5 Experiments II: Data-Dependent Defenses

The data-dependent defense can be substantially more vulnerable than the oracle defense because poisoned data alters the outlier-removal constraints. A tractable semidefinite-programming-based attack produces large test-loss increases on MNIST-1-7 and Dogfish.

Results: At low ϵ ≤0.05, MNIST-1-7 remains safe with maximum train loss 0.12.The figure reports qualitatively similar behavior for Dogfish.
Attack construction: A semidefinite program optimizes attack locations using a distribution supported on at most four attack points.An outer loop samples poisoning distributions and retains the one producing the highest loss.
Results: At ϵ = 0.3, MNIST-1-7 test hinge loss rises from 0.03 to 0.69 and 0-1 loss from 0.01 to 0.40.These results are obtained against the data-dependent defense shown in Figure 4a.
Results: At ϵ = 0.3, Dogfish test hinge loss rises from 0.05 to 0.59 and 0-1 loss from 0.01 to 0.22.The reported attack uses the same data-dependent-defense setting as the MNIST-1-7 experiment.
Defense vulnerability: Data-dependent defenses use empirical poisoned centroids, allowing attackers to subvert outlier removal.Poisoned data can rotate the slab constraint, while the sphere constraint alone may not filter the resulting attacks.

6 Related Work

Related work spans machine-learning security, poisoning attacks across many model families, adversarial test-time examples, generative modeling, and learning with adversarial errors.

Machine-learning security: Machine-learning security research has expanded substantially, especially as systems are used in security-critical settings.The cited surveys cover security of machine-learning systems, including malware detection.
Data poisoning: Data-poisoning research has examined models including LASSO, clustering, PCA, topic models, collaborative filtering, neural networks, and other systems.This work extends beyond the linear-classifier setting.
Adversarial examples: Adversarial test images exploit vulnerabilities at test time, whereas data poisoning targets the training process.Some reinforcement-learning attacks blend training and testing vulnerabilities.
Generative models: Generative adversarial networks use a game-theoretic training objective for generative models rather than focusing on security.Their name does not indicate a security-oriented purpose.
Adversarial errors: Theoretical work studies robust learning under adversarial errors for estimation, clustering, classification, regression, and related tasks.These methods assume prior distributional structure on the data.

7 Discussion

The paper presents certification as a way to evaluate poisoning defenses beyond testing a finite set of hypothetical attacks. Its scope is constrained by access to clean data, convex-loss requirements, and the current focus on binary SVMs and specified sanitization constraints.

Discussion: The framework provides certificates against a large family of attacks, but it is intended for defense design rather than deployed-operation guarantees.Running the method requires access to clean data unavailable at deployment time.
Limitations: The framework has been applied to binary SVMs, with extensions to other losses, multiclass classification, and alternative sanitization structures left open.Efficient maximization of the loss over feasible poisoning points is the main requirement.
Limitations: The current framework does not handle non-convex losses because its upper bounds would no longer be valid.An attacker could otherwise manipulate optimization so the defender reaches a poor local minimum.
Discussion: The paper contrasts its tractable bound with worst-case bilevel optimization, which is generally intractable but admits heuristics.The bound is useful because it has a natural minimax formulation.
Discussion: Certifying rather than merely testing hypothetical attacks addresses the possibility that an unconsidered attack is more effective.The approach implicitly considers an infinite number of attacks before deployment.

A Proof of Proposition 1

The proof introduces regret for a sequence of loss functions and then substitutes the regret relation into the bound, averages over iterations, and upper-bounds a minimization term using a comparator model.

Proof: Regret measures an algorithm’s cumulative loss relative to the best fixed parameter over a sequence of loss functions.The sequence is indexed by t = 1, . . . , T, with iterates θ^(1), . . . , θ^(T).
Proof: The proof substitutes the regret expression into equation (10) and averages the resulting terms over T.This converts the online-learning guarantee into the form needed for Proposition 1.
Proof: For t = ϵn, one term becomes the clean-data loss plus the poisoning contribution evaluated on the selected attack points.The displayed passage identifies this term as a normalized loss expression.
Proof: The proof upper-bounds the minimum over θ by evaluating the objective at the comparator model θ̃.This produces the final inequality used in the proposition.

B Defending Against Overfitting Attacks

Uniform convergence and suitable regularization make train and test losses close, ruling out overfitting attacks that raise test loss without also raising training loss.

Uniform convergence provides a high-probability bound for margin-based losses.The bound applies to any loss of the form ℓ(θ; x, y) = φ(y⟨θ, x⟩), where φ is 1-Lipschitz.
Appropriate regularization can make train and test losses sufficiently close to rule out overfitting attacks.An attack that makes test loss high must also make train loss high under this condition.

C Regret Bound for Adaptive RDA

The adaptive optimization algorithm has vanishing average regret, with faster rates possible when the adaptive regularization parameter grows linearly.

The adaptive algorithm requires analysis beyond standard Regularized Dual Averaging regret bounds because its regularizer enforces the norm constraint adaptively.The analysis is closer in spirit to work on sparse linear regression.
Average regret can be guaranteed at rate O(1/√T) with an appropriate choice of η.
When λ_t increases linearly with t, average regret decreases at the faster rate O(log(T)/T).
In either case, average regret converges to 0 as T →∞.

D Semidefinite Program for ˜U(θ)

The maximization over poisoning distributions can be reduced to a finite-support formulation and expressed as a semidefinite program over a Gram matrix, which also recovers realizing vectors.

Finite-support reduction: An optimal poisoning distribution can be assumed to have support on at most four points: positive and negative support vectors and non-support vectors.The reduction follows by replacing same-class support or non-support points with their midpoint.
Finite-support reduction: The four support-point weights determine the poisoned class means and expected hinge loss.The expected loss depends on the weights of the positive and negative support vectors.
Semidefinite formulation: Sphere and slab defenses encode feasibility constraints distinguishing support vectors from non-support vectors.
Semidefinite formulation: For fixed support weights, the optimization becomes a semidefinite program over the 7×7 Gram matrix of four poisoning vectors and three known vectors.Known inner products among the class means and model vector become equality constraints.
Semidefinite formulation: Solving the semidefinite program yields both the optimal objective value and vectors realizing it.The vectors are recovered using a Gram-matrix factorization involving a pseudoinverse.
Semidefinite formulation: The remaining maximization over poisoning weights is approximated by Monte Carlo sampling in a three-dimensional parameter space.