Provable robustness against all adversarial $l_p$-perturbations for $p\geq 1$

Francesco Croce, Matthias HeinICLR 2020 · OpenReview

TL;DR

Researchers from the University of Tübingen have developed MMR-Universal, the first regularization scheme that provides provable robustness guarantees against all $l_p$-norm adversarial attacks (for $p \geq 1$) simultaneously. By strategically maximizing the distance to decision boundaries in both $l_1$ and $l_\infty$ norms, the model creates a "safety zone" that mathematically covers every other $l_p$ norm, effectively ending the game of whack-a-mole where defending against one type of attack leaves a model vulnerable to others.

What Problem Does This Paper Address?

Deep learning models are notoriously fragile. A tiny, imperceivable change to an image (an adversarial perturbation) can flip a "stop sign" classification to "speed limit 80." Most defenses focus on a specific "threat model," usually defined by an $l_p$-norm (like $l_2$ for Euclidean distance or $l_\infty$ for maximum pixel change).

Visualization of different $l_p$-norm balls, illustrating the varying shapes of threat models.

The core problem is robustness transferability. A model provably robust against $l_\infty$ attacks often has zero protection against $l_1$ attacks, and vice versa. In the real world, an attacker won't tell you which norm they are using. Previous attempts to defend against multiple norms were mostly empirical (heuristic-based) and lacked "certificates"—mathematical proofs that no perturbation within a certain radius can change the model's output.

Methods

The authors leverage the fact that ReLU networks are piecewise affine functions. This means the input space is partitioned into a massive collection of polytopes (linear regions); inside each region, the network behaves like a simple linear classifier.

The core technical contribution is a geometric insight:

  1. The Convex Hull Trick: The authors prove that if a classifier is robust within the convex hull of an $l_1$-ball and an $l_\infty$-ball, it is automatically robust for all intermediate $l_p$-norms ($p \in (1, \infty)$).
The convex hull of an $l_1$-ball and an $l_\infty$-ball. Securing this space guarantees robustness for all intermediate $l_p$-norms.
  1. Dimension Independence: Crucially, they derive a lower bound for $l_p$-robustness that does not depend on the input dimension $d$. This is a major improvement over "naive" bounds that degrade as image resolution increases.
  2. MMR-Universal Regularizer: They propose a training loss that penalizes the model if the training points are too close to the "boundaries" of their linear regions or the decision boundary, measured in both $l_1$ and $l_\infty$ distances. By pushing these boundaries away during training, they "carve out" a provably safe space for all $p \geq 1$.

Key Insights and Ideas

  • The "Union" is Harder than the Parts: The authors show that for standard models, an $l_1$ attack almost never lands inside an $l_\infty$ ball of reasonable radius. This means the set of "dangerous" directions is much larger when considering multiple norms, making simultaneous defense significantly more difficult.
  • $l_1$ and $l_\infty$ are the "Anchors": Because $l_1$ and $l_\infty$ are the extreme cases of $l_p$ norms, securing them (and the space between them) effectively blankets the entire spectrum of $p \geq 1$.
  • Provable vs. Empirical: While adversarial training provides good empirical defense, it often fails to provide a certificate. MMR-Universal is designed specifically to make the model "verifiable" by existing tools like the Wong & Kolter provable framework.

Key Results

The method was evaluated on four standard computer vision benchmarks: MNIST, Fashion-MNIST, GTS (German Traffic Sign), and CIFAR-10. The authors compared MMR-Universal against state-of-the-art defenses.

  • First of its kind: MMR-Universal was the only method to provide non-trivial "Upper Bounds" (the maximum possible error under attack) for the union of $l_1, l_2,$ and $l_\infty$ perturbations across all datasets.
  • GTS Performance: On the German Traffic Sign dataset, while other "robust" models had a provable error of 100% (meaning they couldn't guarantee anything against a union of attacks), MMR-Universal achieved a provable robust error of 52.4%.
  • Efficiency: By only needing to track $l_1$ and $l_\infty$ during training, the method avoids the computational nightmare of trying to optimize for every possible $p$ individually.

Limitations and Future Work

  • Clean Accuracy Trade-off: Like almost all robustness methods, there is a "robustness tax." Models trained with MMR-Universal have slightly higher error on clean, un-attacked images compared to standard models.
  • Scalability of Verification: While the training is efficient, proving the robustness (verification) still relies on external tools (like MIP solvers) which can be computationally expensive for very large, deep networks.
  • Beyond $p < 1$: The current theory applies to $p \geq 1$. Extending these provable guarantees to $l_0$ (sparsity) or $p < 1$ remains an open challenge.

Summary updated

Abstract

In recent years several adversarial attacks and defenses have been proposed. Often seemingly robust models turn out to be non-robust when more sophisticated attacks are used. One way out of this dilemma are provable robustness guarantees. While provably robust models for specific $l_p$-perturbation models have been developed, we show that they do not come with any guarantee against other $l_q$-perturbations. We propose a new regularization scheme, MMR-Universal, for ReLU networks which enforces robustness wrt $l_1$- \textit{and} $l_\infty$-perturbations and show how that leads to the first provably robust models wrt any $l_p$-norm for $p\geq 1$.
BibTeX
@inproceedings{croce2020provable,
  author = {Francesco Croce and Matthias Hein},
  title = {{Provable robustness against all adversarial $l\_p$-perturbations for $p\textbackslash\{\}geq 1$}},
  booktitle = {International Conference on Learning Representations},
  year = {2020},
  url = {https://openreview.net/forum?id=EobrK5mmK5c},
}
Figure