Adversarial Robustness Certification, in depth: threat sets, interval bound propagation by hand, CROWN, randomized smoothing CERTIFY with real numbers and how to audit a claim

What a certificate claims

Fix a classifier f, an input x with true label y, and a threat set B(x, eps), usually an L-infinity or L2 ball of radius eps. Verification asks: is f(x') = y for every x' in B(x, eps)? Equivalently, is the minimum over the ball of the margin z_y(x') - max over j≠y of z_j(x') positive, where z are the logits? A certifier is sound if every 'certified' answer is true, and complete if it certifies every input that is in fact robust. All useful certifiers are sound; completeness costs exponential time in the worst case, so most practical methods give up some of it.

The threat set is the whole claim. An L-infinity radius of 8/255 on CIFAR-10 images says nothing about rotations, patches, typos or paraphrases. For text, a threat set might be 'any word replaced by one of its listed synonyms', which IBP-trained models were certified against in 2019 work by Jia et al. and Huang et al.; for embeddings it is a ball in embedding space. Write the threat set down before choosing a method, and make sure it describes something an attacker can actually do in your pipeline.

Three families of certifiers

Interval bound propagation, by hand

Interval bound propagation (IBP) pushes a box through the network. If each input coordinate lies in [l, u], an affine layer Wx + b maps the box's centre c = (u + l)/2 to Wc + b and its radius r = (u - l)/2 to |W| r, where |W| takes element-wise absolute values. ReLU is monotone, so it maps [l, u] to [max(l, 0), max(u, 0)]. One pass gives sound bounds on every logit.

A worked example shows both the method and its main trap. Take input x = (1, 0), hidden layer h1 = ReLU(x1 - x2), h2 = ReLU(x1 + x2), and logits z0 = h1 + h2 (the correct class) and z1 = h1. With eps = 0.3 in L-infinity, both pre-activations have centre 1 and radius 0.6, so h1 and h2 each lie in [0.4, 1.6]. Then z0 is in [0.8, 3.2] and z1 in [0.4, 1.6]. Subtracting interval endpoints gives a worst-case margin of 0.8 - 1.6 = -0.8: not certified. But the margin is z0 - z1 = h2 exactly; folding that difference into the last layer before bounding gives [0.4, 1.6], certified, and 0.4 is the true minimum (x1 = 0.7, x2 = -0.3). Treating z0 and z1 as independent forgot that they share h1. Always bound the margin, not the logits.

import torch

def ibp_linear(W, b, lo, hi):
    mid, rad = (hi + lo) / 2, (hi - lo) / 2
    out_mid = W @ mid + b
    out_rad = W.abs() @ rad
    return out_mid - out_rad, out_mid + out_rad

def ibp_margins(layers, x, eps, label, domain=None):
    """layers: [(W, b), ...] with ReLU between. Returns a lower bound on z_label - z_j."""
    lo, hi = x - eps, x + eps
    if domain is not None:                        # e.g. (0.0, 1.0) for pixels
        lo, hi = lo.clamp(*domain), hi.clamp(*domain)
    for W, b in layers[:-1]:
        lo, hi = ibp_linear(W, b, lo, hi)
        lo, hi = lo.clamp(min=0), hi.clamp(min=0)
    W, b = layers[-1]
    C = W[label][None, :] - W                     # fold the margin into the last layer
    d = b[label] - b
    m_lo, _ = ibp_linear(C, d, lo, hi)
    m_lo[label] = float("inf")
    return m_lo                                   # certified iff every entry > 0

On a normally trained deep network IBP bounds explode layer by layer and certify almost nothing. Its value is in training: minimising a loss on IBP bounds produces networks whose bounds are tight, at a cost in clean accuracy.

Linear relaxations and branch and bound

Linear relaxation methods replace each unstable ReLU, one whose input interval straddles zero, with a pair of linear functions that bound it from above and below, then propagate linear expressions backwards from the margin to the input. Because the result is a linear function of the input, its minimum over an L-p ball has a closed form. CROWN and its relatives are much tighter than IBP on ordinary networks at a few times the cost. The auto_LiRPA library implements them for general PyTorch graphs, and the alpha,beta-CROWN verifier adds optimised relaxation slopes and branch and bound over ReLU splits, which makes it complete given enough time; it has performed strongly in the international verification competition, VNN-COMP.

The practical pattern is a cascade: run IBP or CROWN first, which settles most easy inputs, and spend branch and bound only on the remainder, with a per-input time limit. Report timeouts as 'unknown', never as robust.

Randomized smoothing

Bound propagation needs white-box access and struggles with large models. Randomized smoothing, analysed tightly by Cohen, Rosenfeld and Kolter in 2019, works with any base classifier f. Define the smoothed classifier g(x) as the class f returns most often when x is perturbed with Gaussian noise of standard deviation sigma. If the top class has probability at least pA and every other class at most pB, then g's prediction is constant within L2 radius R = (sigma/2)(InvPhi(pA) - InvPhi(pB)), where InvPhi is the inverse standard normal CDF. Using pB = 1 - pA gives R = sigma InvPhi(pA).

Two things are certified here, and confusing them is the most common error in claims: the certificate covers g, not f, so you must deploy the noisy, sampled g; and pA is estimated from samples, so the certificate holds with probability 1 - alpha over that sampling.

The CERTIFY procedure in code

import numpy as np
from scipy.stats import beta, norm

def lower_conf_bound(k, n, alpha):
    """One-sided Clopper-Pearson lower bound on a binomial proportion."""
    return 0.0 if k == 0 else beta.ppf(alpha, k, n - k + 1)

def sample_counts(f, x, sigma, n, num_classes, batch=1000):
    counts = np.zeros(num_classes, dtype=np.int64)
    while n > 0:
        b = min(batch, n)
        noisy = x[None] + sigma * np.random.randn(b, *x.shape)
        counts += np.bincount(f(noisy), minlength=num_classes)   # f returns class ids
        n -= b
    return counts

def certify(f, x, sigma, n0, n, alpha, num_classes):
    c_a = sample_counts(f, x, sigma, n0, num_classes).argmax()     # selection
    k = sample_counts(f, x, sigma, n, num_classes)[c_a]             # estimation, fresh noise
    p_a = lower_conf_bound(k, n, alpha)
    if p_a <= 0.5:
        return None, 0.0                                            # abstain
    return int(c_a), sigma * norm.ppf(p_a)

Cohen et al. used n0 = 100, n = 100,000 and alpha = 0.001. The base classifier must be trained with the same Gaussian noise, or it will be wrong on almost every noisy copy and g will abstain everywhere.

Worked numbers: what a radius costs

Run the numbers with n = 100,000 and alpha = 0.001. If the guessed class wins 99,000 of the noisy samples, the Clopper-Pearson lower bound on pA is 0.98899, InvPhi of that is 2.29, and at sigma = 0.5 the certified L2 radius is 1.145; at sigma = 0.25 it is 0.57. If it wins 60,000, the bound is 0.5952 and the radius at sigma = 0.5 is only 0.12. If it wins all 100,000, the bound is 0.99993, InvPhi is 3.81 and the radius is 1.91 at sigma = 0.5. That last number is a ceiling: no input can be certified beyond about 3.8 sigma with this sample size, however confident the model is. With n = 1,000 the ceiling drops to 2.46 sigma, and with n = 10,000 to 3.20 sigma.

Sigma is the central trade-off: larger noise permits larger radii but makes the base classifier's job harder, which lowers clean accuracy and raises abstention. The cost is also concrete: 100,000 forward passes per certified input, which is why smoothing is an offline evaluation or a low-volume production guard, not a default inference path.

Reading and auditing a certification claim

Certified results are reported as certified accuracy at radius r: the fraction of test inputs that are both correctly classified and certified at radius at least r. Read such a claim with a short checklist.

• Which norm and radius, in which input space? An L2 radius of 0.5 on images normalised to [0, 1] is a different claim from the same number in an embedding space.
• Is the certificate for the deployed model, or for a smoothed or IBP-trained variant with lower clean accuracy?
• Probabilistic or deterministic? For smoothing, what were n and alpha, and were selection and estimation samples separate?
• How were timeouts and abstentions counted? They must count as failures.
• Was the evaluation on held-out data drawn from the distribution you care about?

Then place the certificate in the system. Certifying a multimodal model's image filter against small L2 perturbations does not stop instructions rendered into the image, which are large, visible changes outside any small ball; certifying a prompt classifier against synonym swaps does not stop optimised suffixes. A certificate is one layer with an exact scope.

Failure modes

• Floating-point unsoundness. Verifiers that ignore rounding can certify inputs that are not robust in the deployed numeric format. Use verifiers that account for it, or keep a safety margin on the bound.
• Deploying f, certifying g. The smoothed classifier must be what runs in production, with sampling, or the certificate is about a different model.
• Preprocessing outside the certified graph. Resizing, JPEG compression or normalisation applied before the certified function changes what the ball means.
• Sample reuse. Estimating pA from the same samples that chose the class inflates the bound.
• Domain clipping forgotten. Not intersecting the ball with the valid input range gives looser bounds, while clipping in the bound but not in the threat model gives claims about inputs that cannot occur.
• Threat-model drift. Attackers move to perturbations outside the set; keep red-teaming the full pipeline.

Trade-offs

What to do next

1. Write the threat set as a precise statement: input space, norm, radius, and which real attacker capability it models.
2. Pick the target: a small guard or embedding classifier is a realistic first certificate; a full LLM is not.
3. For white-box small models, run CROWN through auto_LiRPA with margin folding and a time-limited branch and bound fallback; record certified, falsified and unknown.
4. For black-box or large models, train the base model with Gaussian noise and implement CERTIFY with separate selection and estimation samples.
5. Plot certified accuracy against radius on held-out data and publish n, alpha, sigma and how abstentions were counted.
6. Combine certificates with adversarial training and continuous red teaming for threats outside the set.