Lower bounds on the robustness to adversarial perturbations

Jonathan Peck, Joris Roels, Bart Goossens, Yvan SaeysNeurIPS 2017

Deep neural networks are famously brittle. Since 2014, researchers have known that applying tiny, human-imperceptible perturbations to an image—known as adversarial examples—can cause a state-of-the-art model to fail spectacularly. While many hypotheses exist to explain why this happens, most lack formal mathematical proof. Furthermore, while we have many ways to attack models, we lack a rigorous way to measure a model's inherent robustness without running expensive empirical tests.

This paper seeks to fill that gap by deriving formal lower bounds on the magnitude of perturbations necessary to change a model's classification. Essentially, it asks: "What is the smallest possible change an attacker could ever hope to make and still succeed?" By analyzing networks layer-by-layer from the output back to the input, the authors provide a computationally efficient way to determine a guaranteed "safety zone" where no adversarial attack can succeed.

Methodology: A Modular, Layer-by-Layer Approach

Instead of attempting to analyze a complex deep network all at once, the authors propose a modular approach. They break the network down into its constituent parts and work backward from the output to the input.

  1. The Backwards Chain: If the robustness of layer $L+1$ is known to be $\kappa$, the framework calculates the minimum perturbation $r$ needed at the input of layer $L$ to produce a change of size $\kappa$ at its output.
  2. Layer-Specific Analysis: The paper derives specific mathematical bounds for the most common building blocks of modern AI architectures:
  3. Softmax Layers: The starting point, where robustness is determined by the distance between the highest-scoring class and its closest competitor.
  4. Fully-Connected Layers: Analyzed using the Jacobian matrix (first-order derivatives) and a bound on second-order derivatives to account for curvature.
  5. Convolutional Layers: Bounds are derived based on the Frobenius norm of the filter weights.
  6. Pooling Layers: Different bounds are provided for Max, Average, and $L_p$ pooling operations.

Because these bounds only require information already present in the model (like weights and gradients), they can be computed very efficiently—in time roughly linear to the number of parameters.

LeNet Architecture

Experimental Setup and Key Insights

The authors evaluated their theoretical bounds using the LeNet architecture on two standard computer vision benchmarks: MNIST (grayscale handwritten digits) and CIFAR-10 (color images across 10 categories).

Distribution of bounds for MNIST and CIFAR-10

Several key insights emerged from this analysis:

  • The "Safety Floor": These calculations represent lower bounds, providing a theoretical guarantee. No adversarial perturbation can possibly be smaller than the calculated value. If the calculated bound is 0.1, an attacker must change the input by at least 0.1 to have any hope of success.
  • Dimensionality Matters: The bounds for CIFAR-10 were significantly smaller than those for MNIST. This supports the hypothesis that as input dimensionality increases, models become naturally more sensitive to tiny perturbations.
  • Worst-Case vs. Average-Case: The theoretical bounds are much smaller than the perturbations found by common attack methods like the Fast Gradient Sign Method (FGSM). This suggests that while "typical" adversarial examples might be easy to find, the "mathematically smallest" ones are much more elusive.
  • Model Selection Tool: Because these bounds are fast to compute, they can be used during the design phase to compare different model architectures and choose the one that is mathematically more robust before ever running a single attack simulation.

Results and Implications

When testing their bounds against the LeNet architecture, the researchers found zero violations. In all experiments on MNIST and CIFAR-10, no adversarial example generated by FGSM was ever smaller than the theoretical lower bound, confirming the mathematical validity of their derivations.

While the bounds are conservative (often several orders of magnitude smaller than empirical attacks), the authors noted that for some samples, the empirical attacks were quite close to the theoretical floor. This suggests the bounds are not uselessly loose. Ultimately, the method proves highly suitable for model selection, allowing developers to avoid the "arms race" of testing a model against an ever-growing list of specific attack algorithms.

Limitations and Future Work

Despite its utility, the framework has limitations. Because the method works layer-by-layer, approximation errors can accumulate as the network gets deeper. This might make the bounds overly conservative for very deep architectures like ResNets. Additionally, the current work does not cover recurrent neural networks (RNNs) or common modern techniques like Batch Normalization or Dropout.

The authors also acknowledge a likely robustness-accuracy trade-off: as a model is made more robust (resulting in flatter decision surfaces), it might eventually lose accuracy. Characterizing this relationship mathematically remains an open challenge. Finally, future work is needed to determine if more sophisticated, optimization-based attacks (like Carlini & Wagner or L-BFGS) can get closer to these theoretical lower bounds than the simple FGSM method used in this study.

Summary updated

BibTeX
@inproceedings{peck2017lower,
  author = {Jonathan Peck and Joris Roels and Bart Goossens and Yvan Saeys},
  title = {{Lower bounds on the robustness to adversarial perturbations}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2017},
}
Figure