Source-linked AI summary
Label Sanitization against Label Flipping Poisoning Attacks
Andrea Paudice, Luis Muñoz-González, Emil C. Lupu
TL;DR
Untrusted training data exposes machine-learning systems to label-flipping poisoning attacks that can degrade classifier performance. The paper develops a tractable greedy attack and a k-NN-based mechanism to detect and relabel suspicious points. The authors report significant attack degradation and effective defense mitigation on linear classifiers, while experiments cover binary classification and genuine points may also be relabelled.
Problem
Label-flipping attacks let an attacker alter labels for part of an untrusted training set, and can significantly degrade learning algorithms despite constrained capabilities.
Method
The paper formulates optimal label flipping as bi-level optimization, approximates it with a greedy validation-impact heuristic, and uses k-NN label sanitization to relabel suspicious samples.
Results
The proposed attack significantly degrades linear classifiers, while the k-NN defense successfully mitigates the effect of label-flipping attacks.
Takeaways & Limitations
Label sanitization based on k-NN provides an empirical defense against the proposed label-flipping attacks in the evaluated setting.
Takeaways & Limitations
The evaluation considers binary classification, and the defense can also relabel genuine points, especially in overlapping regions when η is close to 0.5.
Abstract
from arXiv · showhide
Many machine learning systems rely on data collected in the wild from untrusted sources, exposing the learning algorithms to data poisoning. Attackers can inject malicious data in the training dataset to subvert the learning process, compromising the performance of the algorithm producing errors in a targeted or an indiscriminate way. Label flipping attacks are a special case of data poisoning, where the attacker can control the labels assigned to a fraction of the training points. Even if the capabilities of the attacker are constrained, these attacks have been shown to be effective to significantly degrade the performance of the system. In this paper we propose an efficient algorithm to perform optimal label flipping poisoning attacks and a mechanism to detect and relabel suspicious data points, mitigating the effect of such poisoning attacks.
1 Introduction
Machine-learning systems using untrusted or crowdsourced data are vulnerable to poisoning, including constrained label-flipping attacks. The paper proposes efficient attack and defense algorithms, evaluating the defense on real datasets.
- Motivation: Untrusted data sources expose machine-learning systems to injected training data that can poison learning algorithms.Reported examples include antivirus engines, spam filters, and fake-profile or fake-news detection systems.
- Threat model: Label-flipping attacks constrain the attacker to changing labels, yet can still significantly degrade classifiers, including deep-learning systems.Earlier poisoning attacks may manipulate both features and labels, whereas label flipping changes only labels.
- Related defenses: Existing defenses identify harmful samples for removal, but some approaches do not scale well to large datasets.Outlier detection can mitigate optimal poisoning, while sample-impact evaluation is limited by scalability.
- Contributions: The paper proposes an efficient label-flipping attack algorithm and a k-NN label-sanitization defense that detects and relabels suspicious points.The defense is empirically evaluated on a linear classifier using 3 real datasets.
- Evaluation: The paper evaluates its proposed defense experimentally on real datasets after introducing attack and mitigation algorithms.The paper structure separates related work, attack formulation, defense, experiments, and conclusions.
2 Related Work
Related work studies optimal poisoning attacks against several classifiers and defenses based on removing malicious examples or robust optimization. Label-flipping defenses include sample-impact and influence-function methods, with scalability remaining a concern.
- Poisoning attacks: Optimal poisoning attacks are formulated as bi-level optimization problems that maximize an attacker objective while the learner minimizes loss on tainted data.Prior work applies this strategy to SVMs, logistic regression, embedded feature selection, neural networks, and deep-learning systems.
- Poisoning attacks: Back-gradient optimization extends efficient poisoning-point computation to a broader range of learning algorithms, including neural networks and deep-learning systems.
- Defenses: Defenses against optimal poisoning typically remove identified malicious examples or solve robust optimization problems.Outlier detection can remove poisoning points before training, including under a white-box setting where the attacker knows the preprocessing.
- Label-flipping defenses: Label-flipping defenses measure each training example’s impact or use influence functions to identify harmful examples without retraining.The sample-impact approach scales poorly with the number of samples, whereas influence functions target training-cost impact more scalably.
3 Label Flipping Attacks
The paper models label flipping as selecting p training examples whose labels are reversed to maximize validation loss. Because the exact bi-level problem is intractable, it uses a greedy heuristic that flips examples sequentially by validation impact.
- Problem setup: The attacker selects p training examples and flips their labels to maximize loss on a separate validation dataset.The attack uses an indicator vector u with ∥u∥0 = p to specify which labels are reversed.
- Optimization: The resulting classifier parameters are learned by optimizing loss on the poisoned training set within a bi-level optimization problem.The outer problem selects label flips while the learning algorithm produces parameters from the altered dataset.
- Optimization: The exact attack is computationally intractable because it requires combinatorial search over subsets of p samples.
- Greedy attack algorithm: The proposed heuristic greedily selects each next sample whose label flip maximizes validation error after retraining on earlier flips.Selected indices are removed from the search space, the indicator vector is updated, and the poisoned dataset is revised at each iteration.
4 Defence against Label Flipping Attacks
The defense uses k-NN to enforce local label homogeneity and relabel suspicious training points when neighborhood confidence exceeds a threshold. It can mitigate distant poisoning points but may also relabel genuine points, and experiments focus on binary classification.
- Rationale: Aggressive label flipping may place poisoned points far from genuine points with the same label, making them detectable as outliers.
- k-NN label sanitization: The k-NN defense assigns each training instance the most common label among its k nearest neighbors when neighborhood confidence reaches η.Neighbors are found using Euclidean distance, with 0.5 ≤ η ≤ 1.
- k-NN label sanitization: Poisoning points far from the decision boundary are likely to be relabelled, mitigating their malicious effect on classifier performance.
- Caveats: The defense can also relabel genuine points in overlapping class regions, especially when η is close to 0.5.The authors expect similar fractions of genuine samples to be relabelled in both classes, producing similar label noise across classes.
- Scope: The algorithm is applicable to multi-class classification, but the experimental evaluation considers only binary classification.
5 Experiments
Experiments evaluate the label-flipping attack and k-NN defence on three UCI datasets using a linear classifier. Parameter sensitivity shows that k and η trade off robustness under poisoning against clean-data performance.
- Experimental setup: The classifier is linear, minimizes expected hinge loss, and is trained with stochastic gradient descent.The experiments use 10 random splits with 100 training points, 100 validation points, and the remaining points for testing.
- Attack and defence evaluation: Figure 1 compares average classification error across poisoning fractions with no defence against Algorithm 2 label sanitization.The red line is the undefended classifier and the blue line is the classifier after applying Algorithm 2.
- Parameter sensitivity: Larger k performs better at high poisoning fractions, while smaller k performs slightly better for small fractions or no attack.With larger k, degradation is more gradual as poisoning increases.
- Parameter sensitivity: Higher η makes the defence less effective because fewer points are expected to be relabelled; smaller η degrades more gracefully under poisoning but slightly worsens clean performance.Figure 2 evaluates k with η = 0.5 and η with k = 10 against an undefended baseline.
6 Conclusion
The paper proposes an effective label-flipping attack and a k-NN label-sanitization defence, reporting empirical attack degradation and successful mitigation on linear classifiers. Future work targets less aggressive and colluding attacks.
- Conclusion: The proposed label-flipping attack significantly degrades the performance of linear classifiers.
- Conclusion: The k-NN defence detects malicious poisoning points and successfully mitigates label-flipping attacks.
- Future work: Future work will examine less aggressive attacks with detectability constraints and colluding attack points requiring more advanced defences.