Provably Minimally-Distorted Adversarial Examples

Nicholas Carlini, Guy Katz, Clark Barrett, David L. Dill

Abstract: The ability to deploy neural networks in real-world, safety-critical systems is severely limited by the presence of adversarial examples: slightly perturbed inputs that are misclassified by the network. In recent years, several techniques have been proposed for increasing robustness to adversarial examples — and yet most of these have been quickly shown to be vulnerable to future attacks. For example, over half of the defenses proposed by papers accepted at ICLR 2018 have already been broken. We propose to address this difficulty through formal verification techniques. We show how to construct provably minimally distorted adversarial examples: given an arbitrary neural network and input sample, we can construct adversarial examples which we prove are of minimal distortion. Using this approach, we demonstrate that one of the recent ICLR defense proposals, adversarial retraining, provably succeeds at increasing the distortion required to construct adversarial examples by a factor of 4.2.

Introduction

The field of adversarial machine learning has long been trapped in a cycle: researchers propose a defense, and shortly after, a new attack breaks it. This happens because defenses are typically evaluated against specific, known attacks. If an attack fails, it is unclear if the network is truly robust or if the attack was simply suboptimal. This paper addresses the lack of "ground truth" by establishing the absolute minimum distortion required to misclassify a given input.

Methodology: Formal Verification with Reluplex

The core of this research is the application of formal verification, specifically the Reluplex algorithm. Reluplex treats a neural network with ReLU activations as a system of linear equations and constraints. While verification is typically used to prove a property (e.g., "no input within distance $\delta$ causes misclassification"), the authors use it to find the minimally-distorted adversarial example.

This is achieved by performing a binary search over the distortion parameter $\delta$. By iteratively asking Reluplex if an adversarial example exists with distortion $\le \delta$, the process converges on the optimal $\delta$, providing a provable lower bound on the distortion required to break the model. Due to the high computational complexity of formal verification, the method was evaluated on MNIST using a 3-layer fully-connected network with approximately 20,000 weights.

Key Insights and Results

Iterative Attacks are Highly Effective

The study found that the Carlini-Wagner (CW) attack—an iterative optimization-based method—produces adversarial examples within ~12% of the theoretical optimum. This suggests that "first-order" attacks are remarkably close to the best possible attacks for practical evaluations.

Table 1: Evaluating the technique on MNIST. It shows the CW attack is very close to the provable minimum distortion.

As seen in Table 1, for the standard network ($N$) under $L_\infty$, the CW attack found an average distortion of 0.042, while the provable minimum was 0.038—an improvement of only ~11.6%.

Adversarial Training Genuinely Increases Robustness

By comparing a standard network ($N$) to one trained using adversarial retraining ($\bar{N}$), the authors proved that the defense significantly increases the actual minimum distortion required to fool the network.

Table 2: Comparing standard (N) vs. adversarially trained (N-bar) networks on a subset of instances.

Table 2 shows the impact of the Madry defense. On a subset of 35 instances, the provable minimum distortion increased from 0.039 to 0.165, representing a 4.2x increase in fundamental robustness. Visually, the difference between the heuristic CW attack and the provably minimal Reluplex attack is often indistinguishable to the human eye.

Verification and Network Complexity

Interestingly, Reluplex terminated much faster on the adversarially trained network than on the standard one. This suggests that robust networks might have a simpler internal "non-linearity landscape," making them more amenable to formal analysis. However, the authors also found specific instances where the "hardened" network was actually less robust than the original, highlighting the difficulty of achieving uniform robustness across the entire input space.

Conclusion

While scalability remains a primary limitation—formal verification is computationally expensive and currently limited to networks with a few hundred nodes—this work provides a vital benchmark for adversarial machine learning. Establishing provable limits allows researchers to move beyond the cat-and-mouse game of attacks and defenses toward building systems with absolute safety guarantees.

Summary updated

Abstract

The ability to deploy neural networks in real-world, safety-critical systems is severely limited by the presence of adversarial examples: slightly perturbed inputs that are misclassified by the network. In recent years, several techniques have been proposed for increasing robustness to adversarial examples --- and yet most of these have been quickly shown to be vulnerable to future attacks. For example, over half of the defenses proposed by papers accepted at ICLR 2018 have already been broken. We propose to address this difficulty through formal verification techniques. We show how to construct provably minimally distorted adversarial examples: given an arbitrary neural network and input sample, we can construct adversarial examples which we prove are of minimal distortion. Using this approach, we demonstrate that one of the recent ICLR defense proposals, adversarial retraining, provably succeeds at increasing the distortion required to construct adversarial examples by a factor of 4.2.
BibTeX
@misc{carlini2017provably,
  author = {Nicholas Carlini and Guy Katz and Clark Barrett and David L. Dill},
  title = {{Provably Minimally-Distorted Adversarial Examples}},
  year = {2017},
  eprint = {1709.10207},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1709.10207},
}
Figure