Certified Robustness to Label-Flipping Attacks via Randomized Smoothing

Elan Rosenfeld; Ezra Winston; Pradeep Ravikumar; J. Zico Kolter

Source-linked AI summary

Certified Robustness to Label-Flipping Attacks via Randomized Smoothing

Elan Rosenfeld, Ezra Winston, Pradeep Ravikumar, J. Zico Kolter

arXiv:2002.03018v4Feb 7, 2020cs.LGcs.AIcs.CRstat.ML

TL;DR

Data poisoning can corrupt learned classifiers, and prior certified defenses generally do not guarantee robustness for each targeted test point. The paper unifies randomized smoothing over functions and applies it to tractable label-flip-robust linear classifiers with pointwise certificates, reporting certified accuracy while identifying computational limits for very small noise probabilities.

Problem
Data poisoning and targeted label-flipping attacks can degrade classifiers, while prior defenses provide limited pointwise guarantees for individual test predictions.
Method
The paper unifies randomized smoothing and randomizes training labels to build linear classifiers whose predictions are certified against a specified number of adversarial label flips.
Results
The method maintains 81.3% certified accuracy on Dogfish against an adversary reducing an undefended classifier to less than 1%, and supports multi-class classification.
Takeaways & Limitations
Pointwise certificates provide guarantees for each individual prediction rather than only for a fraction of the test population.
Takeaways & Limitations
For q < 10^-4, the precision required for non-vacuous bounds grows extremely fast, making optimization too computationally expensive.

Abstract

from arXiv · show

Machine learning algorithms are known to be susceptible to data poisoning attacks, where an adversary manipulates the training data to degrade performance of the resulting classifier. In this work, we present a unifying view of randomized smoothing over arbitrary functions, and we leverage this novel characterization to propose a new strategy for building classifiers that are pointwise-certifiably robust to general data poisoning attacks. As a specific instantiation, we utilize our framework to build linear classifiers that are robust to a strong variant of label flipping, where each test example is targeted independently. In other words, for each test point, our classifier includes a certification that its prediction would be the same had some number of training labels been changed adversarially. Randomized smoothing has previously been used to guarantee---with high probability---test-time robustness to adversarial manipulation of the input to a classifier; we derive a variant which provides a deterministic, analytical bound, sidestepping the probabilistic certificates that traditionally result from the sampling subprocedure. Further, we obtain these certified bounds with minimal additional runtime complexity over standard classification and no assumptions on the train or test distributions. We generalize our results to the multi-class case, providing the first multi-class classification algorithm that is certifiably robust to label-flipping attacks.

1. Introduction

The paper addresses targeted data poisoning by developing pointwise-certified defenses, then instantiates the framework with tractable linear classifiers robust to adversarial label flips.

Targeted data poisoning can manipulate training data to cause faulty classifiers, while certifiable defenses for individually targeted test points remain limited.The threat includes label flipping, general poisoning, and backdoors.
A pointwise certified defense guarantees for each prediction that adversarially changing training data within a specified radius would not change the prediction.The paper instantiates this protocol for a certain number of training-label flips.
The framework randomizes over the training procedure, including training labels, rather than over a test-time classifier input.A sufficiently large majority-vote margin yields robustness to adversarial label flips.
The classifier makes no assumptions about feature quality or data separability, enabling use with arbitrary, including pretrained and unsupervised deep, features.The paper demonstrates feasibility on highly nonlinear ImageNet data.
81.3% certified accuracy is maintained on Dogfish against an adversary reducing an undefended classifier to less than 1%.The introduction also reports 94.5% non-robust accuracy on MNIST 1/7 versus 99.1% for the undefended classifier.

2. Related Work

Related work distinguishes data poisoning and label-flipping attacks from test-time attacks, while prior certified defenses generally provide distribution-level rather than pointwise guarantees.

Data poisoning attacks: Data poisoning corrupts or augments training data to degrade a learned model, under an adversary typically assumed to know the learning algorithm and access the training set.The attack may corrupt part of the training set or add new inputs.
Data poisoning attacks: Prior poisoning research covers feature selection, SVMs, linear regression, PCA, and clean-label attacks that use seemingly correctly labeled examples.
Label-flipping attacks: Label-flipping attacks restrict the adversary to changing training labels before the classifier is trained without knowing which labels were tampered with.Examples include reversing spam and innocuous labels or real and fake review labels.
Label-flipping attacks: Adversarial label flipping is harder than random label noise because it targets the learning algorithm’s structure, and existing defenses lack pointwise robustness guarantees.
Certified defenses: Existing certified poisoning defenses mainly address regression and provide broad statistical guarantees or bounds tied to approximating linear coefficients or expected test loss.
Randomized smoothing: Randomized smoothing defines a new classifier by taking the most probable prediction under noise-perturbed inputs, aiming for certified robustness with limited accuracy loss.The standard formulation smooths test-time inputs to a classifier.

3. A General View of Randomized Smoothing

The paper formulates randomized smoothing as an operator over functions and measures, characterizing when thresholded predictions remain unchanged under distribution shifts.

General formulation: Randomized smoothing is unified as an operator G(µ, φ) mapping a binary-valued function and smoothing measure to a weighted expected value.The framework is presented for binary functions, with the multi-class extension deferred to the appendix.
General formulation: The hard-threshold function returns the majority-vote winner, and robustness increases as the vote margin approaches 0 or 1.For similar measures, the threshold prediction is expected to remain unchanged.
General formulation: The general certificate specifies a distance d(µ, ρ) and function f such that sufficiently close measures preserve the thresholded output for every binary function.The vote fraction p represents the majority class’s share under the smoothing measure.
Instantiations: Gaussian smoothing perturbs continuous test inputs, while discrete smoothing independently changes each dimension to another value with probability 1 − α.The discrete guarantee depends on the number of differing dimensions through a combinatorial function.
Practical considerations: Although randomized smoothing often uses Monte Carlo estimates for deep classifiers, the paper’s generic framework supports analytical certificates, with other general-distribution and discrete variants also available.

4. Pointwise Data Poisoning Robustness

The paper extends randomized smoothing from test-time inputs to learning procedures, yielding pointwise certificates against training-data poisoning. Its label-flipping implementation uses linear least-squares classification and deterministic Chernoff bounds to compute certificates efficiently.

General framework: The framework applies randomized smoothing to arbitrary learning algorithms, certifying predictions against specified classes of training-data poisoning.It treats the learning algorithm and test-time prediction jointly as a function of the training data and test input.
Efficient implementation: The method uses a Chernoff bound and convex optimization rather than Monte Carlo sampling, producing deterministic certificates with approximately standard-prediction complexity.Newton’s method solves the log-convex optimization over the Chernoff parameter.
Efficient implementation: The label-flipping instantiation restricts training to linear least-squares classification, making predictions linear functions of the training labels.This permits computing a test-point vector once and reusing it across randomized label assignments.
Efficient implementation: The implementation’s precomputation does not require access to test data, despite the paper presenting the procedure using test points for intuition.The stated algorithm is designed to reduce the apparent cost of training multiple classifiers for each randomized label draw.
Label-flipping robustness: For label-flipping attacks, robustness is measured by the number of training labels on which two training sets differ.Randomizing each training label independently creates the smoothing distributions used to certify invariance under adversarial flips.
Certification bounds: A tighter combinatorial bound can certify approximately twice as many label flips for a given bound on G, although precomputation may be expensive.The closed-form approach is simpler but not tight.

5. Experiments

Experiments evaluate certified accuracy against targeted label flips across binary and multi-class datasets, showing strong robustness at selected noise levels while exposing accuracy–robustness and computational trade-offs.

Experimental protocol: Across datasets, certified test accuracy is measured as the fraction of correctly classified points guaranteed unchanged under at least r training-label flips.The evaluation reports certified accuracy for each noise level q and robustness radius r.
Computational cost: Certification adds a linear cost in the number of training points, but parallelism brings runtime close to standard classification on larger datasets.The method’s certification time was generally indistinguishable from neural-network classification, with pairwise multi-class comparisons especially amenable to parallelization.
CIFAR10: 50% certified accuracy is maintained on CIFAR10 through 175 label flips at q = 0.12, with above-chance certified accuracy extending to 427 flips.The 427-flip radius is approximately 1% of the 50,000-example training set.
Numerical limitations: At q < 10^-4, the precision required for non-vacuous bounds grows extremely fast, making optimization computationally expensive.High-precision arithmetic was needed to obtain the necessary lower bounds.
Dogfish: 81.3% certified accuracy remains on Dogfish under 23 flips per test point, while the undefended model allows more than 99% of points to be attacked with that budget.Reducing the defended classifier below 50% certified accuracy requires more than four times as many flips, exceeding 5% of training data.

6. Conclusion

The paper frames randomized smoothing as a general route to pointwise certificates against data poisoning and instantiates it for targeted label flips. Its conclusion emphasizes individual guarantees, tractable deterministic certification, and extensions to broader poisoning settings.

Contribution: The framework generalizes randomized smoothing into pointwise certificates that guarantee robustness for each test point against arbitrary data poisoning attacks.The paper describes the certificates as black-box robustness guarantees derived from a unifying view of randomized smoothing.
Contribution: The implemented classifier targets label flips independently against each test point and can be evaluated without Monte Carlo sampling.The resulting certification is deterministic and tractable despite the method’s foundation in randomization.
Significance: Individual certificates are intended for decisions such as loans or parole, where population-level guarantees do not identify which people may be misclassified.The paper contrasts per-example guarantees with guarantees covering only a fraction p of the population.
Future work: Future work includes other smoothing distributions, improved unsupervised or self-supervised feature learning, and stronger pointwise train-time attacks.These directions are presented as avenues for improving the framework and evaluating defenses against more powerful attacks.

A. Generic Randomized Smoothing Algorithm

The generic randomized smoothing procedure samples perturbed inputs, evaluates a base function, estimates the smoothed output, and returns a prediction with a probability bound or abstains.

Inputs: The procedure takes a binary function, sample count, smoothing distribution, test point, and failure probability as inputs.These inputs define the sampling-based smoothing computation.
Sampling: It samples perturbed points from the smoothing distribution and evaluates the function on each sample.Each sampled output contributes to the approximate smoothed output.
Certification: The algorithm computes an approximate smoothed output and an associated probability bound.The bound is used to determine whether the prediction can be certified.
Output: It outputs the prediction and bound when the bound determines the label, otherwise it abstains.Abstention occurs when the estimated output and bound do not establish a certified sign.

B. The Multi-Class Setting

The multi-class extension smooths labels by randomly replacing them with alternative classes, then certifies class predictions against label flips using Chernoff bounds.

Certification: Chernoff bounds replace random sampling and bound the probability that the smoothed classifier favors each alternative class.
Multi-class classifier: The multi-class classifier predicts the class with the highest linear score, using one-hot label targets and a weight matrix.
Randomized smoothing: Randomized smoothing flips each label with probability q and selects uniformly among the remaining K −1 classes.
Certification: For every pair of classes, the method optimizes a convex bound and returns the class with the smallest lower bound under the worst alternative.
Certification: The multi-class robustness guarantee is derived using KL divergence between the factorized smoothing distributions, and K = 2 recovers the binary result.

C.1. Attacks on Undefended Classifiers

The experiments attack undefended classifiers on MNIST and Dogfish using influence- or feature-distance-based label-flipping strategies, while comparing empirical attacks with certified bounds.

Dogfish: Dogfish attacks rank training points by influence on each test point, flip candidates sequentially, and retain the successful attack requiring the fewest flips.
Attack construction: The attacks use frozen feature maps and approximate influence computations, with logistic-regression quantities available in closed form.
MNIST: MNIST attacks order labels by feature-space distance or influence, test flips in both directions, and keep the strongest attack for each test point.
Bound comparison: Certified lower bounds and empirical upper bounds for the defended classifier are reasonably close, with the gap narrowing as q decreases.
Bound comparison: The remaining gap may reflect looseness in the Chernoff bound, while the true robustness is expected to lie nearer the empirical upper bound.

C.2. Attacks on Our Classifier

Attacks on the proposed classifier target the smoothed prediction probability, but the implemented Chernoff certificate can respond differently because it certifies a bound rather than that exact probability.

Attack objective: The theoretical classifier aggregates linear sub-classifier votes weighted by their probabilities under label-flip smoothing.
Attack objective: The attack that most reduces P(αT y ≥1/2) flips labels according to their effect on the inner product αT y.
Certificate versus probability: This attack is optimal for the true smoothed probability but not necessarily for the classifier’s Chernoff-based prediction rule.
Empirical evaluation: Empirical upper bounds track guaranteed lower bounds reasonably closely, with a gap under 10% accuracy that shrinks as q decreases.
Empirical evaluation: On MNIST 1/7 and Dogfish, the defended classifier’s empirical robust accuracy exceeds that of the undefended classifier by a larger margin.

D. Additional Tables of Results

The appendix provides certified test-set accuracy tables across MNIST, CIFAR10, Dogfish, and IMDB, with undefended or chance-level references where available.

Reported results: The tables report certified test-set accuracy at specific numbers of label flips and identify the best noise setting for each flip count.
MNIST 1/7: Table 1 covers MNIST 1/7 and compares certified accuracy with the undefended classifier’s empirical robust accuracy.
Full MNIST: Table 2 reports certified accuracy on Full MNIST, where random guessing or a constant classifier achieves 10% accuracy.
CIFAR10: Table 3 reports certified accuracy on CIFAR10, using 10% as the random-guessing or constant-classifier reference.
Dogfish and IMDB: Table 4 covers Dogfish with undefended empirical robust accuracy for comparison, while Table 5 covers IMDB Sentiment Analysis with a 50% chance-level reference.

E. Additional Plots

The additional plots examine regularization, feature quality, and certification bounds. They show trade-offs in accuracy and robustness, dataset-dependent feature performance, and the advantage of a tight discrete bound.

Regularization increases certified margins and robustness at a slight cost in overall accuracy.The unregularized solution has almost 100% non-robust accuracy but significantly lower certified robustness.
RICA-learned features achieve reasonable certified accuracy, although pre-trained features perform better.Certified lines are lower bounds, while the undefended line is an upper bound; deep unsupervised features require a larger dataset.
Approximately twice as many label flips are certifiable with the tight discrete bound as with the generic KL bound.The comparison uses q = 0.4 and is shown both in required margin and certifiable robustness terms.