Detection of Adversarial Training Examples in Poisoning Attacks through Anomaly Detection

Andrea Paudice; Luis Muñoz-González; Andras Gyorgy; Emil C. Lupu

Source-linked AI summary

Detection of Adversarial Training Examples in Poisoning Attacks through Anomaly Detection

Andrea Paudice, Luis Muñoz-González, Andras Gyorgy, Emil C. Lupu

arXiv:1802.03041v1Feb 8, 2018stat.MLcs.CRcs.LG

TL;DR

Machine-learning systems are vulnerable to poisoning attacks that inject malicious training samples, motivating defences for optimal attacks against linear classifiers. The paper uses outlier detection to pre-filter training data and reports that these attacks can be mitigated because their examples differ from genuine points, although constrained attacks such as label flipping are harder to detect.

Problem
Machine-learning systems can be compromised when attackers inject malicious samples into training data, and optimal poisoning strategies can substantially degrade linear classifiers after compromising a small fraction of training data.
Method
The paper proposes an effective, computationally efficient defence that pre-filters training data with outlier detection before learning.
Results
Outlier detection strongly mitigates optimal poisoning attacks on real datasets, including high-dimensional settings, while label flipping attacks are much harder to detect.
Takeaways & Limitations
Optimal attack examples can be removed with appropriate pre-filtering because they are far from genuine points when detectability constraints are not modeled.

Abstract

from arXiv · show

Machine learning has become an important component for many systems and applications including computer vision, spam filtering, malware and network intrusion detection, among others. Despite the capabilities of machine learning algorithms to extract valuable information from data and produce accurate predictions, it has been shown that these algorithms are vulnerable to attacks. Data poisoning is one of the most relevant security threats against machine learning systems, where attackers can subvert the learning process by injecting malicious samples in the training data. Recent work in adversarial machine learning has shown that the so-called optimal attack strategies can successfully poison linear classifiers, degrading the performance of the system dramatically after compromising a small fraction of the training dataset. In this paper we propose a defence mechanism to mitigate the effect of these optimal poisoning attacks based on outlier detection. We show empirically that the adversarial examples generated by these attack strategies are quite different from genuine points, as no detectability constrains are considered to craft the attack. Hence, they can be detected with an appropriate pre-filtering of the training dataset.

I. INTRODUCTION

The paper frames poisoning attacks as a major threat to machine-learning systems and proposes pre-filtering training data with outlier detection to mitigate optimal attacks. Experiments indicate that the defence remains effective with scarce data, while constrained attacks such as label flipping are harder to detect.

Motivation: Poisoning attacks can inject malicious training data and degrade machine-learning performance, especially in systems trained on untrusted data.The introduction highlights feedback, collection, and labelling processes as attack surfaces.
Motivation: Optimal poisoning strategies maximize damage to the learner but generally overlook preprocessing and detectability constraints.Their attack points are typically required only to remain within the feasible feature domain.
Contributions: The proposed defence pre-filters training data with outlier detection and is computationally efficient and agnostic to the learning algorithm.The method targets poisoning attacks against linear classifiers while considering the broader machine-learning pipeline.
Contributions: Experiments on real datasets show that the countermeasure strongly mitigates optimal poisoning attacks, including settings with many features relative to training points.The evaluation includes examples where the number of features is high compared with the number of training points.
Contributions: Label flipping and other simpler constrained attacks are much harder to detect than the optimal poisoning strategies.The paper also compares these attack types with and without the proposed defence.

II. RELATED WORK

Prior work develops optimization-based poisoning attacks and several detection strategies, but existing defences can be computationally expensive or require assumptions about the poisoning fraction. The paper positions outlier detection as a more efficient defence for optimal attacks, while recognizing weaker performance against constrained attacks.

Poisoning attacks: Optimal poisoning attacks formulate attacker and learner objectives as a bi-level optimization problem for compromising classifiers.Prior formulations target SVMs, regularized learning algorithms, feature selection, and other convex learners.
Poisoning attacks: Some poisoning strategies explicitly model hypothesis-testing detectors, whereas earlier optimal attacks impose loose and arbitrary restrictions on attack points.The latter generally require only feasibility in the feature space.
Defences: Existing sample-impact defences can be computationally expensive because they retrain and evaluate the classifier for individual training examples.They may also suffer from overfitting when datasets are small relative to the number of features.
Defences: The proposed outlier-detection technique is more computationally efficient, applies to large datasets, and does not require advance knowledge of the poisoning fraction.The authors report effectiveness when the number of training points is of the same order as the number of features.
Scope: The technique effectively mitigates optimal attacks but cannot effectively mitigate more constrained attacks such as label flipping.The authors describe the method as complementary to defences for attackers that account for detectability.

III. OPTIMAL POISONING ATTACKS

The paper studies poisoning attacks in binary linear classification, where an adversary injects training examples to influence the learner toward an attacker-defined objective. These examples are typically designed to maximize the learner’s error, although subtler objectives are possible.

Attack model: A poisoning attacker injects examples into the training dataset to influence the learning algorithm according to a defined objective.The attack changes the data used by the learner rather than only producing errors at deployment time.
Attack model: The paper restricts its analysis to binary linear classification problems, consistent with much of the poisoning-attack literature.The attack examples are generally designed to maximize the learning algorithm’s error.

A. Problem formulation

The attack adds poisoning points through a bilevel optimization that maximizes an attacker objective evaluated on validation data. Gradient-based updates use implicit differentiation, while projection enforces feature-domain validity but not detectability constraints.

The attacker selects poisoning points to maximize an objective after adding them to the untainted training set.
The resulting bilevel problem combines an attacker objective with the learner’s optimization over the poisoned training set.
Gradient ascent can obtain a possibly local maximum, although the general poisoning optimization problem is NP-Hard and non-convex.
Projection keeps poisoning points within the feasible feature domain but imposes no detectability constraints, allowing outliers to remain detectable and pre-filterable.
The attacker-objective derivative is obtained through the implicit dependence of the learned classifier parameters on the poisoning points.

B. Linear regression for classification: poisoning lasso

The paper instantiates optimal poisoning against an ℓ1-regularized linear classifier and computes updates for individual poisoning points. Its algorithm repeatedly learns the classifier, evaluates poisoning gradients, projects candidate points, and updates them using a line-search step.

The experimental attack targets an ℓ1-regularized linear classifier, also known as lasso for classification.
The gradient strategy processes one poisoning point at a time to reduce the computational cost of optimizing an entire poisoning set.
The derivative for a poisoning point is computed using implicit derivatives associated with the learner’s optimization.
Algorithm 1 initializes poisoning examples, trains the classifier, and selects samples with opposite labels to maximize their loss when labels are flipped.
Each update learns the classifier, computes the poisoning-point gradient, projects the candidate into the feasible domain, selects a step size, and applies the update.

IV. DETECTION OF POISONING ATTACKS WITH OUTLIER DETECTION

The defence detects poisoning examples by applying distance-based outlier detection to trusted class-specific data before classifier training. The approach targets optimal attacks whose unconstrained examples can move away from the genuine data distribution, while high-dimensional detection remains challenging.

Attack setting: Unconstrained optimal poisoning attacks can make the poisoning loss arbitrarily large by increasing |w⊤x_pj|, motivating restrictions on poisoning features.For linear classifiers, the attack objective can become unbounded when poisoning-point feature values are unrestricted.
Attack setting: A single poisoning point can significantly change a Lasso-like classifier’s decision boundary, with validation cost increasing as the point moves away from genuine data.The synthetic example constrains poisoning points to F = [−4, 4] × [−4, 4], where the optimal point lies on the box boundary.
Detectability: Optimal attack strategies impose feasible-domain constraints but omit detectability constraints tied to the underlying data distribution.This omission can make generated adversarial examples distinguishable through pre-filtering.
Detectability: Distance-based outlier detection can provide reliable indicators for adversarial training examples even though estimating distributions and comparing distances is difficult in high dimensions.The difficulty is especially pronounced when the number of available samples is small relative to the number of features.
Defence pipeline: The proposed defence trains one distance-based outlier detector per class using a small trusted subset, then computes class-specific ECDF thresholds for test-time filtering.The training stage produces thresholds t− and t+ used to identify outliers in subsequent datasets.
Defence pipeline: The outlier-detection evaluation compares distance-based methods with a distribution-estimation method, including nearest-neighbour score functions and computational-complexity analysis.The considered algorithms and parameter settings are summarized in Table I.

V. EXPERIMENTAL EVALUATION

The experimental evaluation assesses whether outlier detection mitigates optimal poisoning attacks against linear classifiers on Spambase and MNIST. It compares several detector algorithms and examines sensitivity to the ECDF threshold.

Datasets and setup: The evaluation tests the proposed outlier-detection defence against optimal attacks on linear classifiers using the Spambase and MNIST UCI benchmarks.These datasets represent spam filtering and computer vision application domains commonly used in adversarial machine-learning research.
Detector comparison: The study compares multiple distance-based outlier detectors with a distribution-estimation method and reports their score-function complexity.The algorithms use parameters selected according to the corresponding authors’ recommendations, with C for qSVM chosen by leave-one-out cross-validation.
Detector comparison: The experiments vary the ECDF threshold percentile to assess detector sensitivity.Threshold sensitivity is explored across the outlier-detection algorithms used in the evaluation.

A. Spambase Dataset

The Spambase experiments use a reduced binary feature representation and repeated randomized splits for classifier training, outlier detection, attacker validation, and testing. Outlier detection substantially mitigates poisoning effects across detector choices.

Dataset preparation: Spambase contains 4,601 emails, including 1,813 spam and 2,788 ham, represented originally by 57 features.The experiments retain only 54 term-frequency features and convert them into binary bag-of-word features.
Dataset preparation: The reduced 54-feature representation leaves baseline accuracy unaffected while making the poisoning strategy easier to apply.Duplicate examples are removed before forming the final experimental dataset.
Experimental protocol: The experiments use 10 random splits, with 200 classifier-training examples, 200 outlier-detection examples, 400 attacker-validation examples, and the remaining data for testing.Random outlier-detection methods average results over 10 repetitions for each split.
Results: Without defence, test classification error rises from 0.112 to 0.195 under 20% poisoning, whereas outlier detection is effective at mitigating the attack.The distribution-based qLOF method improves clean-dataset performance at the 99th-percentile threshold, while distance-based methods achieve similar performance at lower computational cost.
Results: For qkSp and qSp, performance is insensitive to the threshold, supported by a paired t-test at 0.99 confidence.Removing some non-malicious samples does not affect classifier performance for these methods.

B. MNIST Dataset

On MNIST, poisoning sharply increases classification error, while outlier detection substantially mitigates the attack; qSp performs best, whereas qLOF performs worst among the compared methods.

MNIST distinguishes handwritten digits 7 and 1 using 784 normalized pixel-intensity features.The experiment uses a binary classification task with features normalized to [0, 1].
The error rises from 0.037 on clean data to 0.391 with 20% poisoning when no defence is applied.This increase is reported alongside relatively large standard deviations for the undefended classifier.
qLOF, which performed best in the previous experiment, gives the worst performance among the outlier-detection methods on MNIST.The authors attribute this result to the difficulty of accurate density estimation in high-dimensional spaces.

C. Label Flipping

The paper evaluates random and informed label flipping against outlier detection and RLS. These less aggressive attacks are harder to detect than optimal poisoning, with mitigation varying by dataset and attack variant.

Label-flipping strategies: Random label flipping selects training points at random, whereas informed label flipping changes labels for examples with the largest squared error under a clean-data classifier.Both strategies are evaluated as constrained alternatives to optimal poisoning.
Defences: RLS is an unbiased-estimator defence designed specifically to mitigate label-flipping attacks.Its implementation minimizes an empirical robust loss and requires estimates of positive and negative label-noise levels.
Results: For informed label flipping on MNIST, both outlier detection and RLS mitigate the attack, and RLS can outperform the standard classifier on clean data.The authors note that RLS may remove genuine samples considered harmful for the classifier.
Results: For informed label flipping on Spambase, both defences have limited effect, although outlier detection degrades more gracefully as poisoning increases.For random label flipping, outlier detection yields 0.149 error at 20% poisoning versus 0.180 without defence in Spambase.
Interpretation: Random label flipping produces attack points closer to genuine same-class data, making them more difficult for both defences to detect.The paper characterizes random label flipping as less aggressive than informed label flipping and optimal poisoning.

VI. CONCLUSION

The conclusion argues that optimal poisoning examples against linear classifiers can be detected with outlier-based pre-filtering because the attacks omit explicit detectability constraints. Less aggressive label-flipping attacks are harder to detect.

Poisoning attacks threaten machine-learning systems that rely on untrusted data collected in the wild.Attackers can inject malicious data that degrades system performance in targeted or indiscriminate ways.
Optimal attack strategies are effective but generate points far from genuine data because they do not model detectability constraints.The conclusion links this distance from genuine points to their removability through adequate pre-filtering.
The proposed outlier-detection scheme mitigates optimal poisoning attacks against linear classifiers, including in high-dimensional datasets.The paper reports this conclusion empirically while acknowledging that outlier detection is challenging in high dimensions.
Less aggressive attacks such as label flipping can be difficult to detect because their generated points are, on average, closer to genuine data points.This conclusion limits the demonstrated effectiveness of the defence to attack strategies whose examples remain distinguishable from genuine data.