Source-linked AI summary
Provably Minimally-Distorted Adversarial Examples
Nicholas Carlini, Guy Katz, Clark Barrett, David L. Dill
TL;DR
Slightly perturbed inputs can cause neural-network classifiers to misclassify, while defenses are difficult to assess against future attacks. The paper uses formal verification to construct provably minimally distorted adversarial examples and reports that adversarial retraining increases robustness by 4.2× on examined samples.
Problem
Slight input perturbations can cause neural-network misclassification, and defenses evaluated against existing attacks may remain vulnerable to future attacks.
Source: §1 · p. 1Method
The paper uses formal verification to construct adversarial examples proven minimally distorted under a chosen distance metric.
Source: §1 · p. 1Results
Robustness increased by 4.2× on the samples examined; the Carlini and Wagner attack produced adversarial examples within 12% of optimal on the small MNIST model.
Source: §1 · pp. 1–2Takeaways & Limitations
Formal verification provides an absolute measurement of defense usefulness regardless of which attack is used.
Source: §5 · p. 7The approach cannot offer provable guarantees when scaling to larger datasets.
Source: §2 · p. 3
Abstract
from arXiv · showhide
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.
1. Introduction
The paper uses formal verification to assess adversarial attacks and defenses, constructing adversarial examples whose distortion is provably minimal. It reports that the tested attack comes close to optimal distortion and that adversarial retraining increases robustness on examined samples.
Motivation
- Slight input perturbations can cause neural-network classifiers to misclassify, hindering their use in safety-critical settings.Adversarial examples can target a label chosen by the adversary.Source: §1 · p. 1
- Assessing defenses against existing attacks can miss vulnerabilities to new attacks, and seven defenses accepted at ICLR 2018 were shown vulnerable.The authors argue this cycle casts doubt on newly proposed defenses.Source: §1 · p. 1
Contributions
- Formal verification constructs adversarial examples that are misclassified and provably minimally distorted under a chosen distance metric.The approach is proposed for assessing both attacks and defenses.Source: §1 · p. 1
Attack Evaluation
- Within 12% of optimal on the small MNIST model: the Carlini and Wagner attack generated adversarial examples at near-minimal distortion.The authors say this supports the hypothesis that first-order attacks are “universal”.Source: §1 · p. 1
Defense Evaluation
- 4.2×: adversarial retraining increased robustness to adversarial examples on the samples examined.The result is a formal proof for the tested setting, not a guarantee at larger scale.Source: §1 · p. 2
2. Background and Notation
The background establishes the paper’s scope in classification, distortion metrics, attack methods, and neural-network verification. It also explains adversarial training and the limits of provable guarantees when scaling to larger datasets.
Neural network notation
- The paper models feed-forward classifiers as composed layers, with logits from the layer before softmax and cross-entropy loss for an input and true label.Source: §2 · p. 2
Adversarial examples
- A targeted adversarial example is an input close to the original that the classifier assigns to an attacker-chosen target label.Source: §2 · p. 2
- For consistency with prior work, the paper evaluates adversarial-example closeness using L∞ and L1 distances, while noting that choosing a suitable metric is difficult.The authors identify more sophisticated distance metrics as an important research direction.Source: §2 · p. 2
Generating adversarial examples
- FGM takes one gradient step; BIM iterates FGM steps while keeping candidates within an α-sized ball around the original input.The step size and clipping rule constrain updates to valid image inputs.Source: §2 · p. 2
- The Carlini–Wagner method seeks a low-distortion targeted example by replacing a difficult constrained optimization with a distance-plus-loss objective.The loss encodes how close the candidate is to being adversarial; logits are used instead of softmax outputs.Source: §2 · p. 2
Neural network verification
- Reluplex checks whether an adversarial example exists within a distortion bound, and iterative checks with binary search approximate the optimal bound.The cited implementation supports ReLU networks and L∞; this paper adds an encoding for L1.Source: §2 · p. 3
Adversarial training
- Adversarial training repeatedly generates adversarial examples for a classifier and retrains on them; whether stronger-attack training increases robustness to all attacks remains open.The inner minimization is approximated with an existing attack technique.Source: §2 · p. 3
Provable defenses
- Certified defenses provide proofs of robustness but so far apply only to small networks on small datasets; this paper instead analyzes arbitrary defenses on a small dataset.The authors share the limitation that larger-dataset scaling no longer permits provable guarantees.Source: §2 · p. 3
3. Model Setup
Verification limits the experiments to a small MNIST network, while Reluplex and binary search are used to find minimally distorted targeted adversarial examples. The setup also encodes L1 distances with ReLU constraints, which can slow verification.
3. Model Setup
- Verification is NP-complete and limited to networks with a few hundred nodes, so experiments use a fully connected three-layer MNIST network with 97% accuracy and 20k weights.It has fewer than 100 hidden neurons, with 24 in each layer.Source: §3 · p. 3
- Reluplex's ReLU support can encode max operators and max-pooling layers, although the paper did not experiment with max-pooling.The method extends the verifier to L1 distances as well as L∞ distances by encoding absolute values using ReLUs.Source: §3 · pp. 3–4
- Absolute-value ReLU encoding lets Reluplex represent L1 distances without code changes, but adds one ReLU constraint per input coordinate and typically makes L1 experiments slower than L∞.For MNIST, L1 encoding adds 784 ReLU constraints; the paper also notes L1 experiments typically began with larger initial distances, requiring more iterations.Source: §3 · p. 4
- Each experiment searches for the minimum distance to a specified target label by iteratively invoking Reluplex and binary search from an initial adversarial input found with the CW attack.The search returns a distance accurate to the specified precision of 10^-3.Source: §3 · p. 4
4. Evaluation
On the tested networks and inputs, adversarial retraining increased average minimum distortion, while attack evaluation showed iterative attacks were often near—but not always at—the verified minimum. The results also exposed pointwise defense regressions and easier verification of the hardened network.
4. Evaluation
- The evaluation used 10 MNIST test images, both standard and adversarially trained networks, L1 and L∞ distances, and nine target labels per image.Conclusions apply only to the tested networks and inputs; the authors offer them as intuition about the tested techniques.Source: §4 · pp. 4–5
4.1. Evaluating Attacks
- 11.6% for L∞ and 6.2% for L1: CW examples averaged within those distances of the minimum in terminated experiments.The N, L1 category was excluded because too few experiments terminated for a meaningful conclusion.Source: §4.1 · p. 5
- 30% or 40% lower distortion was observed for ground-truth examples in many cases than for the best iterative examples.A small step toward the minimally distorted example let gradient descent converge to it; random steps did not help significantly.Source: §4.1 · p. 5
- Suboptimality often recurred across target labels; for digit 9 on the adversarially trained network under L∞, verified examples were 21% to 47% better.Large gaps were attributed to gradient descent initially moving away from the minimum and finding an inferior local minimum.Source: §4.1 · p. 5
4.2. Evaluating Defenses
- 423%: adversarial retraining increased average minimum distortion from 0.039 to 0.165 on the small network.The comparison covers 35 instances on which Reluplex terminated.Source: §4.2 · p. 6, Table 2 · p. 6
- 7 of 35 instances worsened after adversarial retraining, with an average degradation of 12.8%.The authors note that choosing a representative set of evaluation points remains an open question.Source: §4.2 · p. 6
- The authors found no evidence of overfitting: verified minima improved on CW by 12% on both hardened and untrained networks.Here, overfitting means strong accuracy against the training attack but low accuracy against other attacks.Source: §4.2 · p. 6
- Reluplex terminated more often on the adversarially trained network: 81 versus 38 of 90 L∞ instances and 64 versus 6 L1 instances.The reason for the higher termination rates remained under investigation; the authors found no statistically significant difference in network nonlinearity.Source: §4.2 · pp. 6–7
5. Conclusion
Formal verification provides an attack-independent way to assess defenses, and the paper reports increased distortion for adversarially trained MNIST networks. Current verification tools limit experiments to small networks.
5. Conclusion
- Neural-network verification can provide an absolute measurement of defense usefulness regardless of the attack used for evaluation.The paper frames this as a way to assess vulnerability to future attacks.Source: §5 · p. 7
- Carlini and Wagner adversarial examples were within 6.6% to 13% of optimal, while Madry adversarial training increased distortion by an average of 423% on the MNIST dataset for the tested networks.The paper presents these findings as evaluations of one attack and one defense, respectively.Source: §5 · p. 7
- Limited scalability of currently available verification tools restricts experiments to small networks.The paper notes this boundary may be lifted as verification techniques improve.Source: §5 · p. 7