On the Suitability of Lp-Norms for Creating and Preventing Adversarial Examples

Mahmood Sharif, Lujo Bauer, Michael K. Reiter

Introduction

In adversarial machine learning, an adversarial example is defined as an input modified to fool a model while remaining perceptually identical to the original for a human observer. To automate the creation and defense of these examples, researchers have long relied on $L_p$-norms (e.g., $L_2$ Euclidean distance or $L_\infty$ maximum pixel change) as mathematical proxies for human vision. This paper challenges this foundational assumption, demonstrating through mathematical analysis and human user studies that $L_p$-norms are neither necessary nor sufficient to define perceptual similarity.

The Flaw of Necessity

A metric is a necessary condition for similarity if all perceptually similar images have a small distance under that metric. However, simple geometric transformations—such as rotating an image by a few degrees or shifting it by a few pixels—can result in massive $L_p$ distances, even though the image's content remains unchanged to a human observer.

Figure 1: Geometric transformations like rotation result in large $L_p$ distances despite being perceptually identical to humans.

As shown in Figure 1, a slightly rotated dog or horse is immediately recognizable to a human, yet the pixel-wise difference ($L_p$ distance) from the original is significant. This suggests that models defended only against $L_p$ perturbations remain vulnerable to simple, non-adversarial transformations that humans ignore.

The Flaw of Sufficiency

The core contribution of this work is proving that $L_p$-norms are also not sufficient to guarantee similarity. A small $L_p$ "budget" does not ensure that an image looks the same. The researchers conducted three online user studies with 399 participants to compare benign images ($C_B$) with two types of adversarial examples: those designed to be imperceptible ($C_{AI}$) and those crafted to be perceptible ($C_{AP}$) while staying within the same $L_p$ budget.

They found that an attacker can "spend" an $L_p$ budget to concentrate changes into recognizable features. For instance, a small $L_0$ budget can be used to change a '3' into an '8' in a way that is obvious to a human but mathematically "close" to the original '3'. If a human sees an '8' where the metric says it is a '3', the $L_p$ metric has failed as a proxy for perception.

Experimental Evidence

The user studies provided quantitative proof of $L_p$ failure across common datasets like MNIST and CIFAR-10, testing against robust models such as those proposed by Madry et al.:

  • MNIST ($L_0$): Human accuracy on benign digits was 95%, but it plummeted to just 3% on perceptible adversarial examples ($C_{AP}$), despite the small $L_0$ distance. Participants were highly confident in their incorrect (relative to the original label) classifications.
  • CIFAR-10 ($L_2$): At a distance of 6.0, human accuracy dropped from 93% to 57% for the perceptible group.
  • CIFAR-10 ($L_\infty$): With a threshold of 0.1, human accuracy dropped from 91% to 36%.

Implications and Conclusion

The failure of $L_p$-norms has serious implications for the field. If adversarial training uses $L_p$ balls that include images humans would label differently, the model is effectively being trained on mislabeled data—a form of label poisoning.

Furthermore, the "invisibility" of many state-of-the-art attacks may be an artifact of the metric rather than a property of the attack itself. The authors conclude that the community must move beyond raw pixel differences and adopt more sophisticated perceptual metrics—such as SSIM or GMSD—or human-in-the-loop evaluations that account for geometric invariance and structural features.

Summary updated

Abstract

Much research effort has been devoted to better understanding adversarial examples, which are specially crafted inputs to machine-learning models that are perceptually similar to benign inputs, but are classified differently (i.e., misclassified). Both algorithms that create adversarial examples and strategies for defending against them typically use $L_p$-norms to measure the perceptual similarity between an adversarial input and its benign original. Prior work has already shown, however, that two images need not be close to each other as measured by an $L_p$-norm to be perceptually similar. In this work, we show that nearness according to an $L_p$-norm is not just unnecessary for perceptual similarity, but is also insufficient. Specifically, focusing on datasets (CIFAR10 and MNIST), $L_p$-norms, and thresholds used in prior work, we show through online user studies that "adversarial examples" that are closer to their benign counterparts than required by commonly used $L_p$-norm thresholds can nevertheless be perceptually different to humans from the corresponding benign examples. Namely, the perceptual distance between two images that are "near" each other according to an $L_p$-norm can be high enough that participants frequently classify the two images as representing different objects or digits. Combined with prior work, we thus demonstrate that nearness of inputs as measured by $L_p$-norms is neither necessary nor sufficient for perceptual similarity, which has implications for both creating and defending against adversarial examples. We propose and discuss alternative similarity metrics to stimulate future research in the area.
BibTeX
@inproceedings{sharif2018suitability,
  author = {Mahmood Sharif and Lujo Bauer and Michael K. Reiter},
  title = {{On the Suitability of Lp-Norms for Creating and Preventing Adversarial Examples}},
  booktitle = {Workshops @ CVPR},
  year = {2018},
  doi = {10.1109/cvprw.2018.00211},
}
Figure