RAB: Provable Robustness Against Backdoor Attacks

In plain words

Backdoor attacks slip a few poisoned examples into a training set. A model trained on them behaves normally on clean inputs, but returns the attacker's answer whenever a hidden trigger appears in the input. Most defences are empirical: they try to find and remove the poisoned examples, and nothing guarantees that they succeed.

This paper asks whether a model can be trained so that a small enough trigger provably cannot change its answer. The idea borrows from randomized smoothing, a technique that certifies robustness to small changes at test time. Here the random noise goes into the training data as well: many models are trained on differently noised copies of the data, and their outputs are combined into one prediction. If that prediction is stable enough, a bounded change in the training data cannot flip it.

The guarantee covers only part of the inputs. The authors' certified numbers are low on the image tasks they tried, and the bound depends on how many training examples the attacker is assumed to have poisoned. Training is also expensive, since the method trains one model per noise sample.

TL;DR

RAB smooths the training set: it trains N classifiers on copies with fresh Gaussian noise per example, combines them at test time with a fixed noise per model, and certifies a prediction when a confidence bound clears a radius that depends on σ and the number of poisoned samples §5.1.2 alg. 1 alg. 2. The authors report 9-25% certified accuracy on DNN benchmarks and 33-42% for K=3 KNN on Spambase tab. 1 tab. 2. The released code departs from the paper in several places (see Paper vs code).

Problem

Randomized smoothing certifies robustness to evasion (test-time) attacks, but no certified defence against backdoor (training-time) attacks existed when the paper was written §1 §2.2. A backdoor attack adds a pattern to some training inputs and relabels them to a target class, so that test inputs carrying the pattern are classified as that target §2.1. The threat model replaces r training pairs with backdoored pairs, using one or more patterns, and the defender must know the trigger norm, an upper bound on r, and control of the training process §3.2.1 §9.

Method

Setup. The attack replaces r training instances with backdoored ones (x_i + δ_i, ỹ_i). The attack succeeds on a test input x when the trained classifier outputs the target label on x + Ω_x §3.2.1 eq. 2 eq. 3. The defence goal is that the prediction on a triggered input matches the prediction from a model trained on clean data §3.2.2 eq. 4. A certificate of radius R means that the prediction is unchanged whenever the square root of the sum of squared trigger norms is below R §3.3.1.

Smoothed classifier. The smoothed classifier q(y | x, D) is the probability that the base classifier outputs y when both the test input and the training set receive independent noise. The training-set noise D is one i.i.d. draw per training example §4.1.1 eq. 5. The smoothed prediction g is the argmax of q eq. 6. Setting the training-set noise to zero gives the usual evasion-time smoothing §4.1.1.

General condition. Theorem 1 says: if the top class has probability at least p_A, every other class has probability at most p_B < p_A eq. 9, and the optimal type II errors of the two Neyman-Pearson tests satisfy β*(1 − p_A) + β*(p_B) > 1 eq. 10, then the top class stays on top under the perturbation §4. Theorem 2 says this condition is tight, given only the class-probability constraints §4.

Gaussian smoothing (the main certificate). If each training example receives i.i.d. Gaussian noise N(0, σ² I), the robustness condition becomes a bound on the square root of the sum of squared backdoor norms: it must be below (σ/2)(Φ⁻¹(p_A) − Φ⁻¹(p_B)) §5.1.2 eq. 11 eq. 12. For a single pattern δ applied to r training samples, the bound on ‖δ‖₂ is σ/(2√r) times the same bracket §5.1.2 eq. 13. The radius therefore shrinks with the square root of the poisoned count §5.1.2.

Uniform smoothing. Corollary 2 gives the analogous bound for noise uniform on [a, b] §5.2 eq. 14 eq. 15 eq. 16. The paper does not compare smoothing distributions; this is left as future work §5.2.

DNN instantiation. Training draws N independent noise sets, trains one DNN per noisy copy, and stores with each model a noise vector u_k derived from a hash of the model file §6.1.1 alg. 1. At inference, each model classifies the test input after adding its own u_k. The counts of predicted labels define p_A and p_B from binomial confidence bounds with error rate α §6.1.2 alg. 2 eq. 17. The radius is σ/(2√r) times (Φ⁻¹(p_A) − Φ⁻¹(p_B)); the prediction is returned when the radius is at least ‖δ‖₂ alg. 2. The authors report that adding this model-specific test-time noise is needed for good accuracy §6.1.3 §7.2.5.

KNN instantiation. For K-nearest-neighbour classifiers that use squared Euclidean distance quantised into L similarity levels, the Gaussian-smoothed prediction can be computed exactly, without sampling, in O(K^(2+C) · n² · L · C) time for C classes and n training points §6.2 [thm. 3] app. B. The paper states a linear-time case for K=1 §6.2; the appendix gives only the general bound app. B.1.

# RAB training for DNNs  [alg. 1]
# Input:  poisoned dataset (features, labels), noise scale sigma, N models
# Output: list of (model, test-time noise) pairs

def rab_train(features, labels, sigma, num_models):
    pairs = []
    for k in range(num_models):
        # One fresh Gaussian noise vector per training example  [§6.1.1]
        noise = normal(0, sigma**2, shape=features.shape)  # (n, d)
        noisy_features = features + noise
        # Train one base classifier on the noisy copy  [alg. 1]
        model_k = train_model(noisy_features, labels)
        # Test-time noise derived from the saved weights  [§6.1.3]
        u_k = normal_seeded_from_hash(model_k, sigma)
        pairs.append((model_k, u_k))
    return pairs

# Certified inference with RAB-trained models  [alg. 2]
# Input:  test input x, pairs (h_k, u_k), sigma, r, alpha, trigger norm
# Output: predicted label and radius, or ABSTAIN

def certify(x, pairs, sigma, r, alpha, trigger_norm):
    num_models = len(pairs)
    # Count the label predicted by each model on the noisy test input  [§6.1.2]
    counts = zeros(num_classes)
    for h_k, u_k in pairs:
        counts[h_k(x + u_k)] += 1
    # Pick the two most frequent labels  [alg. 2]
    y_a, y_b = top_two_labels(counts)
    # Confidence bounds on the two label probabilities  [§6.1.2]
    p_a, p_b = calculate_bound(counts[y_a], counts[y_b], num_models, alpha)
    if p_a <= p_b:
        return ABSTAIN
    # Certified L2 radius for r poisoned samples  [§5.1.2] [eq. 13]
    radius = sigma / (2 * sqrt(r)) * (inv_cdf(p_a) - inv_cdf(p_b))
    if radius >= trigger_norm:
        return y_a, radius
    return ABSTAIN

Key equations, if essential. Robustness condition (Theorem 1) §4 eq. 10:

\beta^*(1 - p_A) + \beta^*(p_B) > 1

Gaussian certificate for a single pattern on r samples §5.1.2 eq. 13:

\|\delta\|_2 < \frac{\sigma}{2\sqrt{r}} \left( \Phi^{-1}(p_A) - \Phi^{-1}(p_B) \right)

Hyperparameters

Values stated in the paper, with the code's value where it differs. "Not stated" means the paper does not give it.

Results

Author-reported. Setup: DNNs trained on poisoned MNIST, CIFAR-10 and ImageNette, with 1000 (MNIST, CIFAR-10) or 200 (ImageNette) noise samples and finetuning as in §7.1. KNN with K=3 on UCI Spambase, σ=0.5. Hardware: not stated. Baselines: AC, Spectral, Sphere, NC, SCAn, Mixup §7.1.3. Empirical robust accuracy is measured only on attack-successful test inputs for the vanilla model, so vanilla is 0% by construction §7.1.4 tab. 1.

Comparison with empirical defences (empirical robust accuracy, not certified): on MNIST one-pixel, NC reaches 76.2% and AC 64.3%; on CIFAR-10 one-pixel RAB reaches 42.9%, above every listed baseline (the highest is 31.4%) tab. 1. The text says RAB beats about half the baselines on MNIST and ImageNette §7.2.3.

Ablation, test-time noise: on ImageNette with σ=0.2 and blending, the text reports about 20% certified accuracy without the model-specific test-time noise and about 80% with it, at small radii §7.2.5 fig. 5. Appendix table: MNIST one-pixel certified accuracy 12.7% without and 23.5% with it app. C.5.

Multiple runs (5 runs): most standard deviations are below 1.2 points; the largest is 1.40 points, for ImageNette blending certified accuracy app. C.7.

Runtime: certifying one input takes 2.5 s with the exact KNN algorithm (K=3), described as 2-3× faster than vanilla RAB on MNIST and 6-7× on CIFAR-10 §7.3 fig. 6.

Radius behaviour: certified accuracy falls with radius and drops to zero past a point; stronger noise helps at larger radii and hurts at small ones §7.2.4 fig. 4.

Paper vs code

Code: official repository AI-secure/Robustness-Against-Backdoor-Attacks at code_commit 428c8a8, linked from the paper footnote §7.2. It has no LICENSE file; cite only, no quoting. A torchdp/ subfolder reproduces code under the Unlicense; it is not used in the main results autograd_grad_sample.py.

• Smoothed prediction. Paper: counts of hard labels from N models, eq. 17 §6.1.2. Code: averages each model's sigmoid probability and takes the top two of the averaged vector utils.py.
• Confidence bounds. Paper: one-sided binomial lower confidence bounds for both p_A and p_B §6.1.2. Code: one-sided Hoeffding bound with half-width sqrt(ln(1/α)/(2N)) added to p_B and subtracted from p_A eval.py. At N=1000 and α=0.001 that half-width is about 0.059, computed from the code's formula.
• Number of poisoned samples. Paper: radius σ/(2√r)·(…) §5.1.2 alg. 2. Code: radius 0.5·σ·(Φ⁻¹(p_A) − Φ⁻¹(p_B)) with no √r term eval.py. The code's radius therefore equals the paper's with r=1. The paper does not say which r its table numbers use.
• Test-time noise. Paper: u_k is a deterministic function of the model file via a SHA256 hash §6.1.3. Code for MNIST and CIFAR-10 seeds numpy from the hash but draws the noise with torch's generator, which the seed does not control mnist_cnn_model.py cifar10_cnn_model.py. The ImageNette model draws from numpy after the seed, so it is deterministic imagenet_dnn_model.py.
• Finetuning. Paper: pretrained on clean data, then finetune on a 0.1% (MNIST, CIFAR-10) or 1% (ImageNette, Spambase) subset §7.1 §7.1.1. Code: MNIST and CIFAR-10 models are freshly initialised and train on the full poisoned training set train.py attack_lib.py. ImageNette starts from torchvision ImageNet weights imagenet_dnn_model.py. No subset code found.
• Task definition. Paper: 10-class MNIST and CIFAR-10 §7.1.1. Code default: binary pairs, MNIST 1 vs 0 or 6 vs 8, CIFAR-10 airplane vs bird or automobile vs dog attack_lib.py attack_lib.py. ImageNette: code uses dog vs cat (pair 0) or dog vs fish (pair 1), the second not released per the README attack_lib.py README.md.
• Target label. Paper: "tench" for ImageNette §7.1.5. Code: label 0 for every task attack_lib.py.
• Spambase features. Paper: 57 inputs §7.1.1. Code: 54 raw features plus two ratios, dropping the third capital-run column, so 56 spam_dataset.py. Spam triggers and blending noise use 56 dimensions attack_lib.py.
• KNN K. Paper: K=3 in Table 2 §7.1.2 tab. 2. Code: K=1 only, asserted knn_model.py; eval_knn passes K=1 eval_knn.py. The released code cannot reproduce Table 2 as published. Code also shrinks the bucket range by 0.1 for Spambase, a step the paper does not mention eval_knn.py. KNN code accepts binary labels only knn_model.py.
• Evaluation set. Paper: certified accuracy on all instances §7.1.4, but Table 1's caption says the robust scores use only attack-successful instances tab. 1. Code evaluates every non-target-class test input with the trigger and its true label, without checking vanilla attack success attack_lib.py eval.py.
• Strictness. Algorithm 2 returns a prediction when R ≥ ‖δ‖ alg. 2. Corollary 1 requires a strict inequality eq. 12. The code uses a strict comparison eval.py.
• Noise scale and count. Paper gives σ and N per dataset §7.1.2. Code has no per-dataset defaults: σ defaults to 0.0 train.py, and N_m defaults to 1000 for all tasks, including ImageNette where the paper uses 200 train.py.
• Trigger location. Paper: one-pixel pattern in the middle of the image §7.1.5. Code: MNIST one-pixel at row and column 23; the centre variant (20, 20) is commented out attack_lib.py. Trigger values are clipped at 1 attack_lib.py.
• Uniform smoothing. Corollary 2 §5.2 has no code path utils.py.

Pitfalls

• Lower and upper bounds. The paper's text asks for lower confidence bounds on both p_A and p_B §6.1.2. p_B must be an upper bound for the certificate to hold. The code takes the upper side for p_B eval.py. Implement the upper bound for p_B.
• Radius scaling. Certified radii scale as 1/√r §5.1.2. The released evaluation omits this factor, so its certified numbers correspond to r=1 eval.py. Any reproduction should state which r it uses.
• Hoeffding versus binomial bounds. At N=1000 and α=0.001, the code's Hoeffding half-width of about 0.059 is large next to p_A values near 0.9. This shrinks the certified radius and makes the abstain rate sensitive to N eval.py.
• Test-time noise reproducibility. For MNIST and CIFAR-10 the noise depends on torch's random state, not on the hash. Results can differ between runs unless the torch seed is fixed in the same way mnist_cnn_model.py.
• Notation. Algorithm 2 and eq. 17 pass the training noise d_k or ε_k into the inference call. For DNNs the dataset argument is notational; inference uses only x + u_k §6.1.2 alg. 2.
• Cost. Certifying one DNN input needs N forward passes; training needs N full models (1000 for MNIST and CIFAR-10, 200 for ImageNette) §9 §7.1.2. Certification also needs the attacker's r and trigger norm, both assumed known §9.
• Abstention. Inputs with p_A ≤ p_B are abstained rather than certified. Reported rates are 1.9-6.0% for DNNs app. C.6; the paper suggests a radius-based variant to avoid abstention §7.2.1.
• Trigger clipping. Clipping at 1 for image triggers can make the realised norm smaller than the nominal δ attack_lib.py.
• Tightness. Theorem 2 needs 1 ≥ p_A + p_B ≥ 1 − (C−2)p_B §4. Check this before claiming tightness for multiclass problems.
• KNN linear-time claim. The K=1 linear-in-n claim §6.2 is not derived separately in the appendix app. B.1.
• Text against tables. The text says ImageNette certified accuracy is "around 12%" §7.2.1 and empirical accuracy is "over 30%" §7.2.2; Table 1 gives 9.2-15.9% and 29.9% for blending tab. 1. Table 2's caption says "Vanilla denotes DNNs" for a KNN table tab. 2.
• Radius for Table 1. The paper does not state which radius the certified numbers use. The code prints radius grids: MNIST 0, 0.2, 0.5, 1.0, 2.0, 5.0; other datasets 0, 0.05, 0.1, 0.2, 0.5, 1.0 eval.py. The MNIST grid has no 0.1, which is the attack norm the paper uses §7.1.5.
• Software age. requirements pin torch 1.4.0 and torchvision 0.5.0 requirements.txt; the ImageNette model calls torchvision's pretrained flag imagenet_dnn_model.py. Expect to adapt the environment.

Lineage

• Builds on: randomized smoothing for evasion robustness, cited as Cohen et al. 2019 §2.2; the Neyman-Pearson lemma §4.1.2; the KNN exact smoothing idea of a prior result §6.2.
• Related: Rosenfeld et al. (2020), a concurrent randomized-smoothing defence against label flipping, which the paper calls orthogonal §8.
• Compared against: Activation Clustering, Spectral Signatures, Sphere, Neural Cleanse, SCAn and Mixup §7.1.3.
• Superseded by: not known from this wiki.