PaperlayerView exact revision on arXiv

Source-linked AI summary

RAB: Provable Robustness Against Backdoor Attacks

Maurice Weber, Xiaojun Xu, Bojan Karlaš, Ce Zhang, Bo Li

arXiv:2003.08904v8cs.LGstat.ML

TL;DR

Provable robustness against backdoor attacks remains largely unexplored despite the vulnerability of machine-learning models to poisoning. The paper develops randomized-smoothing certification and RAB, establishing robustness bounds and benchmarking certified robustness across models and datasets.

  • Problem

    Provable robustness against backdoor attacks remains largely unexplored, despite attacks that bias models toward triggered test inputs.

  • Method

    The paper generalizes randomized smoothing to certify classifiers using test instances and training datasets, then introduces RAB for robust smoothing against backdoors.

  • Results

    The framework provides the first benchmark of certified backdoor robustness across DNN, support-vector-machine, and K-NN models on diverse datasets and attacks.

  • Takeaways & Limitations

    The theoretical framework and benchmarks establish a foundation for studying certified robustness against backdoor attacks across models and datasets.

  • Takeaways & Limitations

    RAB introduces substantial runtime overhead because certification requires training and evaluating many models, although the process is parallelizable.

Abstract

from arXiv · show

Recent studies have shown that deep neural networks (DNNs) are vulnerable to adversarial attacks, including evasion and backdoor (poisoning) attacks. On the defense side, there have been intensive efforts on improving both empirical and provable robustness against evasion attacks; however, the provable robustness against backdoor attacks still remains largely unexplored. In this paper, we focus on certifying the machine learning model robustness against general threat models, especially backdoor attacks. We first provide a unified framework via randomized smoothing techniques and show how it can be instantiated to certify the robustness against both evasion and backdoor attacks. We then propose the first robust training process, RAB, to smooth the trained model and certify its robustness against backdoor attacks. We prove the robustness bound for machine learning models trained with RAB and prove that our robustness bound is tight. In addition, we theoretically show that it is possible to train the robust smoothed models efficiently for simple models such as K-nearest neighbor classifiers, and we propose an exact smooth-training algorithm that eliminates the need to sample from a noise distribution for such models. Empirically, we conduct comprehensive experiments for different machine learning (ML) models such as DNNs, support vector machines, and K-NN models on MNIST, CIFAR-10, and ImageNette datasets and provide the first benchmark for certified robustness against backdoor attacks. In addition, we evaluate K-NN models on a spambase tabular dataset to demonstrate the advantages of the proposed exact algorithm. Both the theoretic analysis and the comprehensive evaluation on diverse ML models and datasets shed light on further robust learning strategies against general training time attacks.

1. Introduction

The paper addresses the largely unanswered problem of certifying robustness against backdoor attacks, where prior defenses were primarily empirical. It introduces RAB, a unified randomized-smoothing framework with tight robustness bounds, efficient K-NN smoothing, and broad certified-robustness benchmarks.

  • Problem and contribution: RAB provides the first certification process offering provable robustness for machine-learning models against backdoor attacks.Backdoor attacks add patterns to some training instances, biasing predictions on test images containing those patterns.
  • Method design: RAB improves certification radius and efficiency through training-process design, including hash-function-enabled data augmentation and an exact K-NN smoothing algorithm without random-noise sampling.The introduction identifies certification radius and certification efficiency as key practical challenges.
  • Theoretical framework: The paper develops a unified framework that certifies robustness against both evasion and backdoor attacks and proves the resulting robustness bound is tight.The framework generalizes randomized smoothing to a broader family of functions and smoothing distributions.
  • Theoretical framework: The work provides the first certifiable robustness bound for general machine-learning models against backdoor attacks under different smoothing-noise distributions.This addresses a gap left by prior work, which had studied certified robustness mainly for evasion attacks while backdoor defenses remained empirical.
  • Evaluation: The paper benchmarks certified robustness for DNNs, support vector machines, and K-NN models across MNIST, CIFAR-10, ImageNette, and spambase, including three representative backdoor attacks and ablations.The experiments provide the first collection of certified robustness bounds across these models and datasets.

2. Background

Backdoor attacks implant patterns that redirect triggered test inputs while preserving benign-data performance, motivating certification against broad poisoning threats. Randomized smoothing, traditionally applied to test inputs for evasion robustness, is generalized here to smooth classifiers and certify both evasion and backdoor robustness.

  • Backdoor Attacks: Backdoor attacks implant patterns associated with adversarial labels, causing triggered test instances to be misclassified while maintaining performance similar to clean models on benign data [8], [16].
  • Backdoor Attacks: Attacks are categorized by target design as single-target or all-to-all, with the latter permuting classifier outputs rather than mapping all triggers to one label.
  • Backdoor Attacks: Backdoor patterns include subtle region-based modifications and whole-instance blending; region triggers can be as small as one or four pixels [16],,.
  • Randomized Smoothing: Randomized smoothing adds Gaussian noise to test instances and uses confidence bounds for the top-1 and top-2 classes to certify consistent predictions within a perturbation radius.
  • Unified Certification Framework: The proposed unified framework extends smoothing from test instances to classifiers, targeting certification against both evasion and poisoning attacks, including arbitrary or uncontrollable random backdoor patterns.

3. Threat Model and Method Overview

This section defines backdoor attacks as training-set poisoning that causes a target response when a test input contains a trigger, and formulates certification as preserving predictions despite bounded training backdoors. RAB achieves this through randomized smoothing of training sets, model aggregation, and a test-time correction to mitigate accuracy loss from distribution shift.

  • Threat Model: A backdoor attack poisons training data with trigger-patterned examples so that adding the pattern to a clean test input induces a target-class prediction.The attacker may replace r training instances with backdoored versions containing the pattern and target label.
  • Threat Model: The defense seeks prediction independence from patterns embedded in training data, so a possibly triggered test input receives the same output whether training used clean or backdoored data.The framework assumes the defender has full control of the training process.
  • Robustness Guarantee: RAB certifies robustness by requiring that when the total backdoor magnitude is below a bound R, the backdoored classifier matches the classifier trained on benign data.The guarantee compares h(x + Ωx, DBD(Ωx)) with h(x + Ωx, DBD(∅)).
  • RAB Pipeline: RAB adds sampled noise to training instances, trains a model for each resulting smoothed dataset, and aggregates their outputs into the final smoothed prediction.Unlike evasion certification, smoothing the test instance alone is insufficient because the training process must also be smoothed.
  • Additional Challenges: Because noisy training data can reduce clean accuracy through distribution shift, RAB adds a deterministic hash-based value to test instances to reduce that shift and improve accuracy.The correction is introduced as part of the RAB training and certification process.

4. Unified Framework for Certified Robustness

The section develops a unified randomized-smoothing framework that certifies robustness against evasion, poisoning, and combined test-training attacks. Its likelihood-ratio condition is classifier-agnostic, supports different norm guarantees through noise choices, and is provably tight.

  • Smoothed classifier: The smoothing construction adds independent noise to test and training instances, with zero training noise recovering evasion-only randomized smoothing.The smoothed classifier depends on the choices of PX and PD.
  • Robustness condition: The framework models attacks on the test instance, training set, or both, and certifies unchanged predictions using optimal type-II errors from likelihood-ratio tests.The perturbed distribution Z + (Ωx, Δ) represents general evasion and backdoor attacks.
  • Robustness condition: Different smoothing distributions produce different norm-based guarantees, including L2 bounds for Gaussian noise and other Lp bounds for uniform noise.The robustness condition requires no assumptions about the underlying classifier beyond class probabilities from its smoothed version.
  • Robustness condition: As the smoothed classifier becomes more confident, the certified robust region expands for a fixed backdoor perturbation.In the simplified case pA + pB = 1, robustness requires β*(1 − pA; P0, P1) > 1/2, and increasing pA increases the optimal type-II error.
  • Tightness: The robustness condition is tight: whenever it is violated, a base classifier can be constructed whose smoothed version matches the stated class probabilities but fails under the perturbation.Conversely, no perturbation violates the condition when the class-probability information is all that is known.

5. Provable Robustness Against Backdoors

This section instantiates randomized smoothing to certify that predictions remain unchanged under bounded backdoor patterns injected into training data. Gaussian and uniform smoothing yield robustness bounds that increase when fewer training samples are poisoned, while the guarantees target specific-pattern targeted errors rather than all poisoning attacks.

  • Gaussian Smoothing: Gaussian smoothing adds iid normal noise to training features and certifies robustness when the smoothed prediction has class probabilities pA and pB satisfying the stated condition and the backdoor patterns meet condition (10).The smoothed classifier is formed by averaging predictions over the training-feature noise distribution.
  • Gaussian Smoothing: The framework certifies that a smoothed classifier makes the same prediction on a backdoored test input as one trained without embedded backdoor patterns, provided the injected patterns satisfy the derived bound.The certificate considers a base classifier trained on a dataset with r infected samples and compares it with the corresponding classifier trained without triggers.
  • Gaussian Smoothing: With one shared pattern poisoning at most r training instances, the certified robustness radius scales proportionally to 1/√r, so more precise attacker-capability information permits a larger certificate.The bound is simplified under the assumption that the attacker uses a single pattern across the infected instances.
  • Uniform Smoothing: Uniform smoothing provides an analogous certificate: if iid uniform training-feature noise is used and the backdoor patterns satisfy the corresponding bound, the backdoored and clean-training smoothed predictions coincide.As in the Gaussian case, poisoning fewer training samples yields a larger certifiable backdoor-pattern magnitude.
  • Discussion: The guarantees focus on attackers targeting a specific error with a specific backdoor pattern and do not establish protection against other poisoning attacks such as label flipping.The paper notes that different smoothing distributions may have substantially different performance and leaves their comparative study for future work.

6. Instantiating the General Framework with Specific ML Models

This section instantiates RAB for DNN and K-nearest-neighbor classifiers, specifying certified training and inference procedures for DNNs and an exact, efficient evaluation method for smoothed K-NN models.

  • DNN-RAB training: DNN-RAB trains N classifiers on independently Gaussian-perturbed poisoned datasets and stores a deterministic model-specific Gaussian test perturbation with each model.The stored perturbation is generated using a seed based on the trained model’s hash and is added during inference.
  • Certified DNN inference: Certified DNN inference uses majority votes and binomial confidence bounds to compute a robust radius R = σ 2√r, returning the top class only when R ≥ ∥δ∥2 and otherwise abstaining.The procedure compares the top two vote counts, calculates pA and pB for error tolerance α, and invokes the certified bound.
  • Certified DNN inference: Adding deterministic noise to test examples substantially improves prediction performance despite the training–test noise mismatch, while hashing ensures repeatable noise generation.Directly applying the bound with noiseless test examples significantly decreases accuracy; hash-based generation avoids resampling noise at each evaluation.
  • Smoothed K-NN: For Gaussian-smoothed K-NN with quantized Euclidean similarity, the smoothed classifier can be evaluated exactly in polynomial time with complexity O(K2+C·n2·L·C), avoiding Monte Carlo sampling.When K = 1, an efficient algorithm achieves linear time in the number of training samples n.

7. Experimental Results

Across DNN and KNN experiments on image and tabular data, RAB provides nontrivial certified robustness against representative backdoor attacks with little benign-accuracy cost, while retaining strong empirical robustness. Its effectiveness depends on task-specific design choices, including deterministic test-time augmentation and an exact KNN certification algorithm.

  • Scope and Limitations: The experiments primarily target representative poisoning patterns and certify robustness according to perturbation magnitude and the number of poisoned training instances, not attack-specific pattern details.The evaluation focuses on dataset-poisoning attacks and does not cover other attack types.
  • DNN Certification: RAB achieves nontrivial certified robust accuracy against backdoor attacks on MNIST, CIFAR-10, and ImageNette with negligible benign-accuracy cost, where no prior certified baseline exists.The evaluation covers one-pixel, four-pixel, and blending-based poisoning patterns; direct randomized smoothing lacks strong certified robustness without deterministic test-time augmentation.
  • Empirical Robustness: RAB attains around 40% empirical robust accuracy on backdoored MNIST and CIFAR-10 instances and over 30% on ImageNette, while remaining comparable to state-of-the-art empirical defenses.These empirical results serve as an upper bound for RAB-certified accuracy, leaving a reasonably small gap between certification and empirical robustness.
  • Test-Time Augmentation: Deterministic hash-function test-time augmentation significantly improves certified accuracy, especially at small certification radii and particularly on ImageNette.Certified accuracy decreases as the radius increases and can suddenly reach zero; stronger noise can hurt small-radius certification while helping at larger radii.

8. Related Work

The related work covers optimization-based poisoning attacks against classical and neural models, alongside randomized-smoothing defenses that certify robustness to label-flipping attacks. The paper distinguishes its focus on perturbations to training inputs from defenses that randomize training labels.

  • Backdoor attacks: Optimization-based poisoning attacks have been developed for SVMs and logistic regression,, while a related neural-network attack applies only to shallow MLPs.
  • Certified Defenses against poisoning attacks: Randomized smoothing has been used to certify robustness against label-flipping attacks by randomizing the classifier’s entire training procedure.
  • Certified Defenses against poisoning attacks: This line of work is orthogonal to the paper’s focus because it perturbs training labels, whereas the paper investigates perturbations to training inputs.

9. Limitations

RAB incurs substantial computational overhead because certification requires training and evaluating many models. Its certification also assumes knowledge of attack parameters and control over training, limiting applicability against attacks that interfere with the training process.

  • 9. Limitations: Certification requires training and evaluating 1000 models for MNIST/CIFAR-10 and 200 for ImageNette, creating nonnegligible but parallelizable runtime overhead.The polynomial-time K-NN algorithm offers an initial way to reduce computational cost, while further mitigation remains future work.
  • 9. Limitations: RAB certification requires bounds on trigger magnitude and poisoned instances, plus defender control over the training process.Without certification, only training-process control is required; consequently, RAB cannot defend against attacks that interfere with training, such as.

10. Discussion and Conclusion · Appendix A. Proofs

The paper presents a unified smoothing framework for certifying robustness against diverse attacks, including backdoor poisoning, through the RAB pipeline and deterministic test-time augmentation. Appendix A supplies proofs for the main results and defines notation for type-I and type-II error probabilities.

  • 10. Discussion and Conclusion: RAB is proposed as the first robust smoothing pipeline for certifying model robustness against backdoor poisoning attacks.The framework targets diverse backdoor attacks within a unified certification approach.
  • 10. Discussion and Conclusion: A deterministic test-time augmentation mechanism is introduced to certify prediction robustness against diverse backdoor attacks.
  • 10. Discussion and Conclusion: The certified backdoor robustness evaluation covers deep neural networks and K-nearest-neighbor models.
  • 10. Discussion and Conclusion: The discussion frames the work as a unified smoothing framework for certifying model robustness against different attacks.
  • Appendix A. Proofs: Appendix A provides proofs for the results stated in the main part of the paper.
  • Appendix A. Proofs: The appendix defines α(ϕ) as the type-I error probability and β(ϕ) as the type-II error probability under the stated distributions.

A.1. Proof of Theorem 1

The proof of Theorem 1 constructs likelihood-ratio tests with prescribed error probabilities and applies Neyman–Pearson optimality to bound smoothed class probabilities after joint input and dataset perturbations. If the resulting lower bound for y_A exceeds every competing upper bound, y_A remains the certified prediction.

  • Preliminaries and Auxiliary Lemmas: Lemma A.1 establishes the likelihood-ratio threshold quantile properties needed to choose valid randomized tests, while Lemma A.2 gives the error-rate optimality implications used in the proof.Likelihood-ratio tests are defined using Λ(x)=f_1(x)/f_0(x), with thresholds and randomization chosen to attain a target significance level.
  • Proof of Theorem 1: Theorem 1 constructs a likelihood-ratio test ϕ_A with significance 1−p_A and uses assumption (9) plus Lemma A.2 to lower-bound q(y_A|x+Ω_x,D+∆) by β(ϕ_A).The test is obtained by selecting the likelihood-ratio threshold and randomization parameter so that α(ϕ_A)=1−p_A.
  • Proof of Theorem 1: For every competing label y≠y_A, the proof constructs ϕ_B with significance p_B and applies Lemma A.2 to upper-bound q(y|x+Ω_x,D+∆) by 1−β(ϕ_B).Assumption (9) supplies the competing-label probability bound needed to invoke the second part of Lemma A.2.
  • Proof of Theorem 1: When β(ϕ_A)+β(ϕ_B)>1, the lower bound for y_A exceeds every competing upper bound, completing the certification proof.The conclusion is q(y_A|x+Ω_x,D+∆)>max_{y≠y_A}q(y|x+Ω_x,D+∆).

A.2. Proof of Theorem 2 … Appendix B. Smoothed K-NN Classifiers

The appendix proves tightness of Theorem 2, derives Gaussian and uniform-noise corollaries through likelihood-ratio tests, and formalizes quantized-similarity K-NN classifiers for subsequent smoothing analysis.

  • A.2. Proof of Theorem 2: Theorem 2’s robustness condition is tight: a constructed base classifier matches the prescribed class probabilities yet fails under any perturbation violating the condition.The construction uses likelihood-ratio tests with specified type-I errors and produces a smoothed classifier whose prediction changes after the violating perturbation.
  • A.2. Proof of Theorem 2: The constructed multiclass distribution p* is valid, with nonnegative probabilities summing to one; for binary classification, the two likelihood-ratio tests coincide.The proof defines h*(x, D) as the label maximizing p*(y|x, D), then verifies consistency with the target smoothed probabilities.
  • A.3. Proof of Corollary 1: Corollary 1 follows by applying Theorem 1 to a shifted smoothed classifier and constructing Gaussian likelihood-ratio tests whose type-II errors determine the robustness condition.The tests are calibrated to type-I errors 1−pA and pB, and the resulting condition is characterized by β(ϕA) + β(ϕB) > 1.
  • A.4. Proof of Corollary 2: For uniform feature noise, the proof constructs likelihood-ratio tests from the overlap of shifted supports S and S′, yielding threshold cases determined by p0.When pA ≤ p0 or 1−pB ≤ p0, the corresponding type-II error is zero, so β(ϕA) + β(ϕB) > 1 cannot hold; therefore pA > p0 and 1−pB > p0 are necessary.
  • A.4. Proof of Corollary 2: In the uniform case satisfying those necessary conditions, both likelihood-ratio thresholds equal one, and the tests are calibrated to significances 1−pA and pB.The construction continues the likelihood-ratio testing argument used for Theorem 1.
  • Appendix B. Smoothed K-NN Classifiers: The appendix defines quantized Euclidean similarity using ordered buckets B1,…,BL with decreasing similarity levels β1 > β2 > … > βL.Similarity is represented as a sum of bucket indicators weighted by the corresponding similarity levels.
  • Appendix B. Smoothed K-NN Classifiers: For ties, lower-indexed instances are ranked as more similar; the K nearest neighbors determine per-class vote tallies γk, and K-NN predicts the label with the largest tally.The neighbor set IK(x, D) is defined through the binary similarity relation and contains the K nearest instances.

B.1. Proof of Theorem 3 … C.3. Kernel-KNN

The appendix derives an efficient computation for the smoothed classifier and evaluates RAB under all-to-all, larger-perturbation, and kernel-KNN backdoor settings. RAB remains empirically effective across these settings, but certification fails for perturbations exceeding its radius and kernel-KNN performs worse than DNNs.

  • B.1. Proof of Theorem 3: Theorem 3 computes the smoothed classifier by partitioning tally-vector events into boundary events defined by top-K similarities and class-wise counts.Conditioned on an instance’s similarity, counts for different classes are pairwise independent, enabling recursive probability calculations.
  • B.1. Proof of Theorem 3: The resulting computation has complexity O(KC+2·n2·L·C), after precomputing and storing the α values used by the recursion.The recursion computes the required probabilities through O(n · K) calls and O(n · L) preliminary computations.
  • C.1. All-to-all Attacks: The all-to-all threat changes predictions from class i to class ((i+1)%C), requiring the model to recognize both the image and trigger rather than the trigger alone.Defenses assuming trigger-only behavior, such as NC, are therefore expected to perform poorly.
  • C.1. All-to-all Attacks: RAB achieves similar empirical and certified robustness under all-to-all attacks, with MNIST and ImageNette slightly improving and CIFAR-10 slightly declining versus the standard attack.The comparison is reported for DNNs across MNIST, CIFAR-10, and ImageNette in Table C.3.
  • C.2. Larger Perturbation: For larger perturbations, certified robust accuracy is 0, while RAB still provides non-trivial empirical robustness comparable with baselines.The perturbations use a 4 × 4 trigger, 20% poison rate, and scale ||δ_i|| = 4.0 on MNIST and 4.3 on CIFAR-10 and ImageNette.
  • C.3. Kernel-KNN: Kernel-KNN achieves worse certification performance than DNNs, and its exact certification algorithm cannot be applied because the Gaussian-kernel output is analytically unavailable.The kernel uses a supervised CNN’s penultimate-layer representation, so certification is evaluated with the DNN procedure instead.

C.4. SVM-based model on tabular data … C.8. Adversarial Atacks on RAB Models

Across tabular SVMs and DNN evaluations, RAB provides empirical and certified robustness, benefits from test-time augmentation, maintains low abstention and stable repeated-run performance, and is examined against adversarial attacks.

  • C.4. SVM-based model on tabular data: The tabular evaluation spans Spambase, Adult, and Mushroom binary-classification datasets with differing sample counts and input dimensions.Spambase has 4,601 points and 57 dimensions; Adult has 48,842 points and 14 dimensions; Mushroom has 8,145 points and 22 dimensions.
  • C.4. SVM-based model on tabular data: RAB achieves good empirical and certified robustness on binary tabular SVM tasks, whereas DNN-specific baselines perform poorly or are inapplicable.Experiments cover Spambase, Adult, and Mushroom datasets; NC and Mixup are excluded because their methods do not apply to these settings.
  • C.5. With & Without Test-time Augmentation: Test-time augmentation improves RAB’s robustness both empirically and certifiably on DNNs.The comparison is reported with and without test-time augmentation.
  • C.6. Abstain Rate: RAB’s certification generally has a relatively low abstain rate, making abstention unlikely to be a serious pipeline concern.For denial-of-service concerns, the authors suggest certifying a defense radius rather than abstaining, following a similar approach to.
  • C.7. Multiple Runs: Five repeated runs produce relatively small standard deviations, indicating that RAB is stable.The mean and standard deviation of robustness are reported in Table C.9.
  • C.8. Adversarial Atacks on RAB Models: The authors test adversarial attacks against RAB using PGD with gradients aggregated across all trained models.The ImageNette attack visualization uses ε = 60, selected to make the adversarial pattern clearest; prior work [46] reported that smoothing a backdoored model can leave obvious patterns.
Loading 2003.08904v8…