Certified Defense to Image Transformations via Randomized Smoothing

Marc Fischer, Maximilian Baader, Martin T. VechevNeurIPS 2020 · OpenReview

Deep neural networks are notoriously brittle to imperceptible changes. While much research focuses on additive pixel noise (adversarial examples), geometric transformations like rotations and translations are equally dangerous and arguably more common in real-world applications. This paper extends randomized smoothing—a popular technique for certifying neural network robustness—beyond simple additive noise to complex geometric transformations. By cleverly bounding the errors introduced by image interpolation, the authors provide the first scalable method to formally guarantee that a model's prediction remains stable under specific ranges of geometric distortion.

The Challenge of Geometric Transformations

The primary hurdle in certifying geometric transformations is interpolation. When a digital image is rotated (e.g., by 15 degrees), the new pixel coordinates rarely land perfectly on the existing grid. The system must "guess" the new pixel values using interpolation techniques like bilinear or nearest-neighbor.

Consequently, transformations do not compose perfectly. For instance, rotating an image by 15 degrees and then back by -15 degrees does not yield the exact original image.

Interpolation error arises because digital transformations do not compose perfectly, creating mathematical slack.

This mathematical "slack" breaks standard certification techniques, which rely on the ability to map perturbations directly back to the original input.

Methodology: Smoothing over Transformation Parameters

To overcome this, the authors introduce Smoothing over Transformation Parameters (SPT). Instead of adding noise directly to pixel values, they inject Gaussian noise into the parameters of the transformation itself (such as the angle of rotation or the magnitude of translation).

To handle the inevitable interpolation error, they propose three distinct defense tiers:

  1. BASESPT: A heuristic defense that ignores interpolation error. It performs well in practice but lacks a formal mathematical certificate.
  2. DISTSPT (Distributional): Provides a guarantee for the "average" image in a dataset by calculating an upper bound on interpolation error offline across a large training set, using it to "pad" the certification radius.
  3. INDIVSPT (Individual): The gold standard defense. It provides a formal guarantee for a specific, potentially adversarial image at inference time.

The technical breakthrough enabling INDIVSPT is a novel Inverse Computation algorithm. Because the defender only observes the transformed image, they must deduce the set of possible original images. The authors utilize interval analysis to bound the set of possible original pixels.

Interval analysis creates a bounding box in pixel space to capture the original image despite interpolation loss.

This effectively treats the interpolation error as a small $\ell_2$ perturbation that the smoothed classifier can then "absorb."

Key Insights and Results

The core insight of this work is realizing that the discrepancy between a "perfect" mathematical transformation and a "real" digital interpolation can be modeled as $\ell_2$ noise. If a model is already robust to $\ell_2$ noise via standard randomized smoothing, that robustness can be "traded" to certify geometric transformations.

Furthermore, randomized smoothing scales exceptionally well. Unlike previous geometric certification methods that relied on complex linear relaxations—which explode in complexity for large networks—this approach only requires running the model multiple times, allowing it to scale to massive architectures like ResNet-50.

The authors evaluated their methods on standard benchmarks including MNIST, CIFAR-10, ImageNet, and Restricted ImageNet. Key results include:

  • High Robustness: On Restricted ImageNet, the method achieved a 73% provable distributional robust accuracy for rotations within $\pm 30^\circ$.
  • MNIST Mastery: For MNIST, they achieved nearly 97% certified accuracy for rotations up to $30^\circ$.
  • State-of-the-Art Performance: The approach significantly outperformed previous geometric certification methods in both the degree of rotation certified and the scale of the models handled.
  • Practical Feasibility: The INDIVSPT method can certify an image in about 45–100 seconds, making it feasible for high-stakes applications requiring formal guarantees.

Limitations and Future Directions

Despite its advances, the method has limitations. The strength of this geometric defense is strictly bottlenecked by the underlying model's robustness to $\ell_2$ noise; a base classifier weak to pixel noise will also struggle with rotations.

Additionally, interval analysis is "sound" (it never lies) but "incomplete" (it can be overly pessimistic). It can sometimes result in bounds so wide that certification fails. Finally, while more scalable than prior work, the requirement of hundreds or thousands of forward passes per image remains computationally expensive for real-time applications like video processing. Future work may focus on tighter interval bounds or more efficient sampling techniques to reduce certification time from seconds to milliseconds.

Summary updated

Abstract

We extend randomized smoothing to cover parameterized transformations (e.g., rotations, translations) and certify robustness in the parameter space (e.g., rotation angle). This is particularly challenging as interpolation and rounding effects mean that image transformations do not compose, in turn preventing direct certification of the perturbed image (unlike certification with $\ell^p$ norms). We address this challenge by introducing three different defenses, each with a different guarantee (heuristic, distributional and individual) stemming from the method used to bound the interpolation error. Importantly, in the individual case, we show how to efficiently compute the inverse of an image transformation, enabling us to provide individual guarantees in the online setting. We provide an implementation of all methods at https://github.com/eth-sri/transformation-smoothing.
BibTeX
@inproceedings{fischer2020certified,
  author = {Marc Fischer and Maximilian Baader and Martin T. Vechev},
  title = {{Certified Defense to Image Transformations via Randomized Smoothing}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=pf-bpsJOOY6},
}
Figure