Introduction to certified defenses and robustness

1) Why “certified” robustness exists

Most defenses you’ve seen so far (adversarial training, preprocessing, detection) are empirical: you test against attacks (FGSM/PGD/etc.) and report robust accuracy.

The problem: passing today’s attacks doesn’t prove safety tomorrow. A stronger or adaptive attacker might still break the model.

Certified defenses address this by providing a provable guarantee that, within a defined threat model, no adversarial example exists (or the model’s prediction cannot change).

2) What is “certified robustness”?

A model is certifiably robust at an input xxx if we can prove:

Meaning: for all inputs within an ϵ\epsilonϵ-ball around xxx (under a chosen norm), the predicted label stays the same.

Two key points:

• The guarantee is local (for a specific input, or a set of inputs).
• The guarantee is conditional on a threat model (norm type, ε radius, input constraints).

3) Certified vs empirical robustness (very important distinction)

Empirical robustness

• You try to break the model with attacks
• If attacks fail, you hope the model is robust
• Risk: attacks might be weak or misconfigured (or gradient masking gives illusion)

Certified robustness

• You prove a bound: “within ε, the model cannot change prediction”
• If certified, robustness holds even against unknown attackers (as long as they stay within the threat model)
• Trade-off: certification can be computationally expensive and often yields smaller ε guarantees than what strong attacks might demonstrate

4) Threat models used in certified defenses

Certified defenses typically certify robustness under constraints like:

• L∞ (max per-feature change ≤ ε)
• L2(overall perturbation energy bounded)
• Sometimes structured perturbations (patches, rotations) but those are harder to certify

Practical interpretation: certification usually assumes “small, bounded perturbations,” often used as a proxy for malicious manipulation.

5) Major families of certified defenses (conceptual overview)

A) Randomized Smoothing (probabilistic certificates)

Core idea: Instead of certifying the base classifier directly, you build a smoothed classifier by adding Gaussian noise to the input many times and taking a majority vote.

If the majority vote is strong enough, you can derive a certified radius R(often for L2).

Why it’s popular:

• Works with modern deep nets
• Scales better than many exact verification methods
• Produces a certificate per input (“certified radius”)

Trade-offs:

• Usually certifies in L2not L∞
• Requires many noisy samples for evaluation (slower inference for certification)

B) Convex relaxations / bound propagation (deterministic certificates)

These methods compute upper/lower bounds on network outputs over a perturbation set:

• Interval Bound Propagation (IBP)
• Linear relaxations / convex outer approximations

Why it’s useful:

• Can be integrated into training (“certified training”)
• Gives deterministic (non-probabilistic) guarantees

Trade-offs:

• Bounds can be loose → small certified radii
• Can be hard to scale to very large architectures without sacrificing tightness

C) Exact/complete verification (formal methods)

For small networks or small inputs, methods can prove robustness exactly:

• SMT/MILP-based verification
• Branch-and-bound style verification

Why it matters:

• Strongest guarantee (if it finishes)

Trade-offs:

• Computationally expensive
• Not always feasible for large production models

6) What “certification output” looks like (the deliverable)

A typical certified robustness report includes:

• Certified radius RRR per sample (or average radius over dataset)
• Certified accuracy at a chosen ε:
  “% of samples that are both correctly classified and provably robust within ε”

Example statement:

• “Certified accuracy at ϵ=0.25(L2) is 42%.”

This is different from robust accuracy under PGD.

7) Simple intuition demo: certification as “margin vs perturbation”

Even without full formal verification, the intuition is:

• If the model’s top class is far above the runner-up (large margin),
• small perturbations won’t flip the class,
• certification methods try to lower-bound this margin under perturbations.

8) Light code: Monte Carlo “smoothed prediction” (intuition for smoothing)

This is not a full certificate, but helps learners understand smoothing mechanics: add noise many times, see how stable predictions are.

import numpy as np
import tensorflow as tf

def smoothed_predict(model, x, num_samples=200, sigma=0.25):
    """
    Monte Carlo smoothed prediction:
    - x: single input with shape (H, W, C) or (D,)
    Returns:
    - class_counts: how many times each class was predicted
    - predicted_class: majority vote
    """
    x = tf.convert_to_tensor(x[None, ...], dtype=tf.float32)  # add batch
    counts = None

    for _ in range(num_samples):
        noise = tf.random.normal(shape=tf.shape(x), stddev=sigma)
        logits = model(x + noise, training=False)
        preds = tf.argmax(logits, axis=1).numpy()
        if counts is None:
            num_classes = logits.shape[-1]
            counts = np.zeros(num_classes, dtype=int)
        counts[preds[0]] += 1

    return counts, int(np.argmax(counts))

# Usage (example):
# counts, cls = smoothed_predict(model, x_test[0], num_samples=500, sigma=0.25)
# print("Counts:", counts, "Smoothed class:", cls)

Learner takeaway: If the majority class dominates under noise, the smoothed classifier is more stable—this stability is what randomized smoothing turns into a certified radius using statistical bounds.

9) Benefits and limitations of certified defenses

Benefits

• Provable guarantee (within the threat model)
• Reduces reliance on “attack-of-the-week” testing
• Useful in high-stakes domains (security, safety, compliance)

Limitations

• Certificates often small (tight guarantees are hard)
• Certification can be slow/expensive
• Guarantees depend on assumptions (norm, ε, input constraints)
• Hard to certify complex real-world transformations (lighting, occlusion, semantic edits)