Stronger and Faster Wasserstein Adversarial Attacks

Kaiwen Wu, Allen Houze Wang, Yaoliang Yu

Introduction

Deep learning models, despite their impressive accuracy, remain highly vulnerable to adversarial attacks—small, carefully crafted perturbations that cause severe misclassifications. Most traditional attacks rely on $\ell_p$ norms, which measure the magnitude of pixel value changes. However, these metrics often fail to capture human visual perception; a simple image translation changes many pixels (resulting in a high $\ell_p$ distance) but looks identical to a human observer.

To address this, researchers have turned to the Wasserstein distance (or Earth Mover’s Distance), which measures the cost of "transporting" pixel mass. This paper introduces two new, highly efficient algorithms for generating Wasserstein adversarial attacks that are significantly faster and far more lethal than previous state-of-the-art methods.

The Wasserstein Advantage

Standard $\ell_p$ attacks add imperceptible noise across an image. In contrast, Wasserstein attacks physically "move" pixel mass, creating structural changes that can fool a model while remaining semantically identical to a human observer.

Comparison of standard attacks vs Wasserstein attacks

The primary bottleneck in generating these attacks has been computational complexity. Optimizing under a Wasserstein constraint is notoriously difficult. Previous methods relied on an approximation called "Projected Sinkhorn," which this paper demonstrates is often too slow and inaccurate for practical use, especially on large-scale datasets like ImageNet.

Methodology

To overcome these computational hurdles, the authors shift the optimization problem from the image space to the "coupling matrix space," focusing on the transportation plan of pixel mass. They introduce two primary algorithmic innovations:

  1. Projected Gradient Descent (PGD) with Dual Projection: Instead of relying on slow iterative solvers for the projection step, the authors derive an exact dual formulation. This reduces the complex projection onto a Wasserstein ball to a simple, mathematically exact one-dimensional search (bisection method).
  2. Frank-Wolfe with Dual LMO: The authors adapt the Frank-Wolfe algorithm, utilizing entropic regularization to smooth the optimization landscape. This results in a highly efficient "Linear Minimization Oracle" (LMO).
  3. Local Transportation: To scale these methods to high-resolution images, the algorithms restrict pixel movement to a small $k \times k$ neighborhood. This introduces necessary sparsity, allowing the computations to fit within standard GPU memory limits.

Key Findings

The researchers evaluated their novel attacks on MNIST, CIFAR-10, and ImageNet, marking the first successful construction of Wasserstein adversarial examples for ImageNet.

  • Unprecedented Attack Strength: Because previous "Projected Sinkhorn" methods relied on loose approximations, they often failed to reach the true boundary of the perturbation ball. By solving the projection exactly, the new methods expose severe vulnerabilities. On CIFAR-10, the authors' PGD attack plummeted a residual network's accuracy to 3.4%, a stark contrast to the 65.6% accuracy maintained under the previous state-of-the-art attack.
  • Significant Speedups: The Dual Projection method proved to be 5 to 7 times faster than Projected Sinkhorn on MNIST and CIFAR-10, and roughly twice as fast on ImageNet.
Adversarial accuracy versus number of iterations
  • Improved Adversarial Training: Stronger attacks make for better defenses. Models trained using the new Frank-Wolfe attack achieved 56.8% robustness accuracy against strong Wasserstein attacks on CIFAR-10, outperforming models trained with older methods (which only reached 41.2%).
  • Debunking the "Shape Reflection" Myth: Prior work suggested Wasserstein attacks naturally reflect object shapes. The authors demonstrate this was merely an artifact of excessive entropic regularization in older methods. Their exact attacks are actually highly sparse, moving only a few critical pixels.

Limitations and Future Work

While a significant leap forward, the methods have limitations. Images require pixel values to remain between 0 and 1 (the hypercube constraint). The primary algorithms handle this via a post-processing step rather than natively during optimization, which can slightly weaken the final attack. Additionally, despite the speedups, Wasserstein attacks remain computationally heavier than standard $\ell_\infty$ attacks. Finally, the "local transportation" constraint, while necessary for memory efficiency, prevents the exploration of global pixel movements that could potentially yield even stronger adversarial examples.

Summary updated

Abstract

Deep models, while being extremely flexible and accurate, are surprisingly vulnerable to “small, imperceptible” perturbations known as adversarial attacks. While the majority of existing attacks fo...
BibTeX
@inproceedings{wu2020stronger,
  author = {Kaiwen Wu and Allen Houze Wang and Yaoliang Yu},
  title = {{Stronger and Faster Wasserstein Adversarial Attacks}},
  booktitle = {International Conference on Machine Learning},
  year = {2020},
  url = {https://openreview.net/forum?id=SGfZ0ihOW-5},
}
Figure