Certified Defenses
Empirical robustness says, "The attacks we tried did not break the model." A certificate makes a narrower and stronger claim: "Within this defined perturbation set, the prediction cannot change."
The scope is part of the guarantee. A certificate names the distance measure, radius, model, and input. Outside those conditions, the guarantee ends.
Randomized smoothing creates a smoothed classifier by adding random noise to an input many times and aggregating the predictions. If one class wins by a sufficient margin, the method can certify a radius around the input.
Interval bound propagation, or IBP, propagates ranges instead of single values. Start with an interval around each input feature. Track the minimum and maximum possible activations through every layer. If the lower bound for the predicted class stays above the upper bounds of the other classes, the prediction is certified inside that interval.
Interval Bound Propagation
1. Start with an input box
Each feature may move independently by epsilon, so each scalar input becomes an interval.
Input intervals
xi in [xi-epsilon, xi+epsilon]
Linear layer
a1 = 1.2x1 - 0.7x2 + 0.1
After ReLU
h = max(0, a)
Output logits
certify if lower(winner) > upper(runner-up)
Certified as class 0 for every input in this box
Class 0 lower bound: 0.665. Class 1 upper bound: -0.136.
Propagate an input interval through a linear layer, ReLU, and output layer. Increase the radius until the class bounds overlap.
IBP avoids checking every possible input one at a time. It carries a conservative range that contains all of them. That efficiency has a price: the bounds can become loose. Overlapping output intervals mean the method cannot prove robustness at that radius; they do not prove that an attack exists.
Test the boundary of a guarantee
Certified inside this radius
Certified radius: 20. Illustrative clean accuracy: 79%.
A certificate is narrow by design. It covers the stated perturbation set. It says nothing about a larger change, a different norm, a patch, a poisoned dataset, or a prompt injection.
Values are illustrative. Real results depend on the dataset, model, attack, and threat model.
How to Read a Certificate
"This image is certified robust within L2 radius 0.25" means any input inside that mathematical ball receives the same class under the certified method. It does not cover a sticker, a crop, a lighting change, a poisoned training example, or a larger L2 perturbation.
Certified defenses pay for the guarantee. They can be computationally expensive, reduce clean accuracy, and apply to limited threat models. The radius may also be too small to cover the real-world changes an attacker can make.
The value is precision. A deployment team can stop saying "robust" as a general adjective and state exactly what has been shown.
Other Certified Defense Methods
Randomized smoothing and IBP are two entry points into a much larger family. Other approaches include:
- Lipschitz continuity-based methods: bound how much the output can change relative to a bounded change in input by constraining the network's Lipschitz constant.
- Convex relaxation-based certification: replace non-convex components like ReLU with convex outer approximations to make the verification problem tractable.
- Certifiably robust training: train the model against the certification bounds directly, rather than certifying a model trained without that objective.
- CROWN-IBP (CROWN – Interval Bound Propagation): combines a linear-relaxation bound (CROWN) with IBP to tighten certified bounds while keeping training efficient.
- Duality-based certification (e.g., SDP): use semidefinite programming or other convex duality formulations to compute certified bounds.
- Neural verification-based approaches: formally verify network properties, often via SMT or branch-and-bound solvers, to prove no adversarial example exists in a region.
- Polyhedral and zonotope methods: propagate more expressive geometric shapes than intervals through the network for tighter bounds.
- Layer-wise certification (e.g., DeepZ, DeepPoly): apply abstract interpretation layer by layer, choosing relaxations tuned to each layer's structure.
- Mixed integer linear programming (MILP): encode the network exactly and solve for worst-case outputs, trading scalability for tightness.
- Adversarial training with certified bounds: combine empirical adversarial training with a certified bound as part of the loss.
- Stochastic Polyak-Łojasiewicz certification: use optimization-landscape conditions to certify robustness properties of the training process.
- Certifiable robustness via input transformations: certify robustness for a model composed with a preprocessing transform, such as randomized smoothing's noise step or other input mappings.
A model is certified against L2 perturbations within radius 0.25. What can you conclude?