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
In the adversarial machine learning landscape, a persistent "cat-and-mouse" game exists between new attacks and defensive strategies. A critical challenge in this field is determining whether a defense is truly robust or if it merely appears so because current attacks are sub-optimal. Most existing attacks rely on gradient-descent heuristics, which find a perturbation but not necessarily the smallest possible one. This creates a "false sense of security" where defenses are evaluated against weak benchmarks.
This paper introduces a rigorous method to find the "ground truth" of adversarial vulnerability using formal verification. By calculating the absolute minimum perturbation required to cause misclassification, the authors provide a definitive benchmark for evaluating both attack efficiency and defense efficacy.
Methodology
The researchers leverage formal verification, specifically the Reluplex algorithm, to treat neural networks as systems of linear equations and constraints. Reluplex is uniquely suited for networks using Rectified Linear Unit (ReLU) activations.
To find the provably minimal distortion ($\delta$), the authors employ a binary search strategy. For a given image and radius $\delta$, they ask the Reluplex solver: "Does there exist any input within distance $\delta$ of the original image that results in a different label?" A "No" response proves perfect robustness within that radius, while a "Yes" provides a counter-example, allowing the search to narrow down the exact threshold of vulnerability. The study evaluates these distortions using $L_1$ (sum of absolute differences) and $L_\infty$ (maximum pixel change) metrics.
Due to the NP-complete nature of formal verification, the experiments were conducted on the MNIST dataset using a 3-layer fully-connected network (approx. 20,000 weights and 100 hidden neurons) to ensure the verification remained computationally tractable.
Results and Discussion
The application of formal verification yielded several key insights into the current state of adversarial research:
Attack Efficiency
A significant finding is that popular gradient-based methods, such as the Carlini & Wagner (CW) attack, are remarkably effective. On a standard MNIST model, the CW attack produced adversarial examples within 11.6% of the provable minimum for $L_\infty$ and 6.2% for $L_1$. This suggests that iterative attacks are nearly optimal for standard networks.
Defense Efficacy
The study provides formal proof that adversarial retraining (specifically the Madry et al. method) significantly enhances true mathematical robustness. It does not just defeat specific attacks; it fundamentally shifts the decision boundaries. Adversarial training increased the average minimal distortion required to break the model by a factor of 4.2x (increasing the average $L_\infty$ distortion from 0.039 to 0.165).
Verification Performance
Interestingly, the authors observed that robustly trained networks were significantly faster to verify than standard ones. This suggests that adversarial training might simplify the activation patterns or "linearity" of the network, making the search space more manageable for formal solvers.
Conclusion
While formal verification currently faces scalability challenges—limiting its application to smaller models like those for MNIST—this work establishes a vital "ground truth" for adversarial research. It confirms that current iterative attacks are highly efficient and that adversarial training provides a provable increase in robustness. As verification tools evolve to handle larger architectures, this methodology could become standard for certifying safety-critical neural networks in fields like autonomous driving and medical imaging.
Summary updated