Provably Robust Adversarial Examples

Dimitar I. Dimitrov, Gagandeep Singh, Timon Gehr, Martin Vechev

Abstract

We introduce the concept of provably robust adversarial examples for deep neural networks - connected input regions constructed from standard adversarial examples which are guaranteed to be robust to a set of real-world perturbations (such as changes in pixel intensity and geometric transformations). We present a novel method called PARADE for generating these regions in a scalable manner which works by iteratively refining the region initially obtained via sampling until a refined region is certified to be adversarial with existing state-of-the-art verifiers. At each step, a novel optimization procedure is applied to maximize the region's volume under the constraint that the convex relaxation of the network behavior with respect to the region implies a chosen bound on the certification objective. Our experimental evaluation shows the effectiveness of PARADE: it successfully finds large provably robust regions including ones containing $\approx 10^{573}$ adversarial examples for pixel intensity and $\approx 10^{599}$ for geometric perturbations. The provability enables our robust examples to be significantly more effective against state-of-the-art defenses based on randomized smoothing than the individual attacks used to construct the regions.

Introduction

Deep neural networks (DNNs) are notoriously brittle, susceptible to "adversarial examples"—tiny, human-imperceptible perturbations that cause misclassification. Traditionally, these attacks produce a single "concrete" point. Consequently, defenses like randomized smoothing, which adds noise to an input and takes a majority vote of predictions, can often mitigate these errors if the adversarial point is isolated.

This research addresses a fundamental challenge: identifying a large, connected region of the input space where every single point is guaranteed to be adversarial. By finding such "symbolic" regions, attackers can bypass local smoothing defenses because the majority of the neighborhood is also adversarial.

Methodology: The PARADE Framework

The authors introduce PARADE (ProvAbly Robust ADversarial Examples), which treats adversarial attacking as a formal verification problem in reverse. Instead of proving safety, PARADE proves a region is "robustly wrong."

The PARADE framework for generating provably robust adversarial regions.

The algorithm operates in two main stages:

  1. Overapproximation: Standard attacks (e.g., PGD) identify a cluster of adversarial points, around which a "hyperbox" is drawn to define an initial search area.
  2. Iterative Underapproximation: Since the initial box may contain correct points, it is iteratively shrunk. A neural network verifier (such as DeepPoly or DeepG) checks if the region is entirely adversarial. For pixel intensity ($L_\infty$) changes, Linear Programming (LP) maximizes volume while maintaining certification. For geometric transformations, Projected Gradient Descent (PGD) optimizes transformation parameter boundaries.

Experimental Evaluation

PARADE was evaluated on MNIST and CIFAR10 across various architectures, including fully connected (8x200) and convolutional networks (ConvSmall, ConvBig).

Massive Scale and Robustness

PARADE successfully identified regions containing approximately $10^{573}$ adversarial examples for pixel intensity and $10^{599}$ for geometric perturbations. These regions are mathematically guaranteed via convex relaxation to be incorrect for every possible value within them.

Breaking Randomized Smoothing

A key finding is that these robust regions are significantly more effective against randomized smoothing than individual PGD attacks. As shown in the comparison below, PARADE-generated examples achieved a 1.00 success rate across all tested models, being 2x to 6x stronger than standard individual attacks in head-to-head tests.

Comparison of attack effectiveness against randomized smoothing defenses.

Discussion and Future Work

PARADE demonstrates that provability can be a powerful offensive tool. By maximizing the volume of adversarial regions, it creates attacks that are physically meaningful and harder to defend against. However, the method's effectiveness is tied to the underlying verifier; loose convex relaxations can lead to smaller-than-optimal regions. Furthermore, while efficient on CIFAR10, scaling to ImageNet remains a challenge due to the high dimensionality of larger models. Future improvements in formal verification will directly enhance PARADE's capabilities.

Summary updated

Abstract

We introduce the concept of provably robust adversarial examples for deep neural networks - connected input regions constructed from standard adversarial examples which are guaranteed to be robust to a set of real-world perturbations (such as changes in pixel intensity and geometric transformations). We present a novel method called PARADE for generating these regions in a scalable manner which works by iteratively refining the region initially obtained via sampling until a refined region is certified to be adversarial with existing state-of-the-art verifiers. At each step, a novel optimization procedure is applied to maximize the region's volume under the constraint that the convex relaxation of the network behavior with respect to the region implies a chosen bound on the certification objective. Our experimental evaluation shows the effectiveness of PARADE: it successfully finds large provably robust regions including ones containing $\approx 10^{573}$ adversarial examples for pixel intensity and $\approx 10^{599}$ for geometric perturbations. The provability enables our robust examples to be significantly more effective against state-of-the-art defenses based on randomized smoothing than the individual attacks used to construct the regions.
BibTeX
@misc{dimitrov2020provably,
  author = {Dimitar I. Dimitrov and Gagandeep Singh and Timon Gehr and Martin Vechev},
  title = {{Provably Robust Adversarial Examples}},
  year = {2020},
  eprint = {2007.12133},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2007.12133},
}
Figure