Source-linked AI summary
Measuring Neural Net Robustness with Constraints
Osbert Bastani, Yani Ioannou, Leonidas Lampropoulos, Dimitrios Vytiniotis, Aditya Nori, Antonio Criminisi
TL;DR
Neural networks can be highly accurate yet vulnerable to small adversarial perturbations, while existing robustness evaluations may be tied to the attack algorithm used. The paper defines frequency and severity metrics and approximates pointwise robustness with a constraint-based linear program. Across MNIST and CIFAR-10 experiments, the approach provides more informative estimates, reveals algorithm-specific overfitting, and supports robustness improvements under multiple metrics.
Problem
Neural networks are susceptible to small adversarial perturbations, and robustness is often evaluated with the same algorithm used to generate training examples.
Method
The paper defines pointwise robustness metrics and approximates nearest-adversarial-example distances by encoding ReLU networks and robustness constraints in a linear program.
Results
The approach yields more accurate robustness measures, exposes algorithm-specific overfitting, and improves robustness under both the proposed and previously used metrics.
Takeaways & Limitations
Impartial frequency and severity metrics can distinguish genuine robustness improvements from improvements specific to one adversarial-example algorithm.
Takeaways & Limitations
The experiments fix ϵ = 20 on the 0-255 pixel scale for MNIST and CIFAR-10, and signed-gradient methods cannot estimate adversarial severity.
Abstract
from arXiv · showhide
Despite having high accuracy, neural nets have been shown to be susceptible to adversarial examples, where a small perturbation to an input can cause it to become mislabeled. We propose metrics for measuring the robustness of a neural net and devise a novel algorithm for approximating these metrics based on an encoding of robustness as a linear program. We show how our metrics can be used to evaluate the robustness of deep neural nets with experiments on the MNIST and CIFAR-10 datasets. Our algorithm generates more informative estimates of robustness metrics compared to estimates based on existing algorithms. Furthermore, we show how existing approaches to improving robustness "overfit" to adversarial examples generated using a specific algorithm. Finally, we show that our techniques can be used to additionally improve neural net robustness both according to the metrics that we propose, but also according to previously proposed metrics.
1 Introduction
The paper addresses the lack of objective robustness measures by defining statistics for adversarial frequency and severity, then approximating robustness through a linear-program formulation. Experiments show the approach estimates robustness more accurately and exposes overfitting to adversarial examples generated by particular algorithms.
- Adversarial examples can arise from tiny, carefully directed perturbations, creating concerns for changing conditions and security-critical applications.
- Existing robustness-improvement methods often evaluate models with the same adversarial-example algorithm used during training, risking algorithm-specific overfitting.
- The paper defines adversarial frequency and adversarial severity from pointwise robustness ρ(f, x∗), with ϵ specifying the perturbation threshold of interest.
- The method restricts the search to a ReLU network’s local linear region and solves an approximating linear program, with an iterative procedure providing an order of magnitude speed-up.
- On MNIST, ALP estimates pointwise robustness more accurately than AL-BFGS; training with AL-BFGS improves only its own measured robustness, whereas ALP improves robustness under both algorithms.
- The paper formalizes pointwise robustness, encodes it as constraints, and reports more accurate robustness measures while demonstrating algorithm-specific overfitting.
2 Robustness Metrics
The paper defines robustness at individual inputs using the distance to the nearest adversarial example and summarizes it with frequency and severity statistics. These metrics distinguish how often failures occur from how close or severe those failures are, using a threshold ϵ.
- The experiments use ϵ = 20 on MNIST and CIFAR-10, with pixel values on the 0-255 scale.
- Pointwise robustness: A classifier is (x∗, ϵ)-robust when every input within L∞ distance ϵ of x∗ receives the same label as x∗.
- Pointwise robustness: Pointwise robustness ρ(f, x∗) is the minimum perturbation threshold at which the classifier ceases to be (x∗, ϵ)-robust.
- Robustness statistics: Adversarial frequency measures how often the classifier fails pointwise robustness below ϵ, whereas adversarial severity measures failure severity conditional on such a failure.
- Robustness statistics: Frequency and severity capture different behaviors: a model can fail often with nearby adversarial examples or fail rarely but with larger distances.
- Estimation: The metrics can be estimated from sampled inputs by substituting an approximation ρ̂(f, x∗) for exact pointwise robustness, typically using the test set.
3 Computing Pointwise Robustness
The paper encodes neural-network classification and pointwise robustness as constraints, allowing the nearest adversarial example to be found through optimization. For ReLU networks, the encoding is exact because the network is piecewise linear.
- Robustness formulation: Pointwise robustness is formulated as the minimum L∞ distance from x∗ to an input receiving a different label.The optimization searches over alternative labels and minimizes ∥x − x∗∥∞.
- Optimization: For a fixed target label, nearest-label search minimizes ∥x − x∗∥∞ subject to the network and classification constraints.The method can search each alternative label, but uses the second-highest-scoring label for efficiency.
- Optimization: The resulting optimization is typically intractable, motivating the tractable approximation developed in the next section.The difficulty arises from the non-convex feasible set of the constraint system.
- Constraint encoding: A neural network’s classification constraint f(x) = ℓ is represented by a constraint system C_f(x, ℓ).The encoding introduces variables for each layer and constrains each layer’s output to equal its computation from the preceding layer.
- Constraint encoding: The encoding is exact: f(x) = ℓ if and only if C_f(x, ℓ) is satisfiable.This theorem connects network predictions directly to feasibility of the encoded constraints.
4 Approximate Computation of Pointwise Robustness
The paper approximates pointwise robustness by restricting the search to a convex region around the seed input, then solves the resulting linear program efficiently. The approximation can overestimate robustness, but experiments find less bias than existing adversarial-example algorithms.
- Convex restriction: Convex restriction constrains the robustness search to a region Z(x∗) whose feasible set is convex.The region is chosen so the restricted constraints contain only conjunctions of linear relations.
- Convex restriction: The region Z(x∗) is constructed by selecting, for each disjunction, the branch satisfied by x∗.Because the disjunctions are mutually exclusive, exactly one branch is selected, producing D(x∗).
- Linear programming: The restricted problem can be expressed as a linear program and solved with standard LP methods.This replaces optimization over the full input space with optimization over Z(x∗).
- Iterative constraint solving: The implementation lazily adds violated constraints while solving, yielding an order-of-magnitude speed-up in practice.It starts with equality constraints and iteratively adds constraints not satisfied by the current solution.
- Single target label: The method fixes the target label to the second most probable label instead of minimizing over every incorrect label.This produces the single-target approximation defined by ρ̂.
- Approximate robustness statistics: Because ρ̂(f, x∗) ≥ ρ(f, x∗), the resulting statistics may be biased, although experiments report substantially less bias than existing algorithms.In particular, the estimated frequency statistic satisfies φ̂(f, ϵ) ≤ φ(f, ϵ).
5 Improving Neural Net Robustness
The paper improves robustness through adversarial-example fine-tuning and evaluates the resulting networks with its robustness measures. Its MNIST fine-tuning results show increased robustness, while implementation choices address adversarial-example construction and rounding.
- Adversarial-example generation: The optimization output supplies an adversarial example whose L∞ distance from the original input equals the estimated robustness ˆρ(f, x∗).
- Fine-tuning: Fine-tuning augments the training set with adversarial examples generated for each original training point, then continues training at a reduced rate for T rounds.Each round considers points from the original training set rather than the augmented set.
- Evaluation: LeNet fine-tuned for T = 1 and T = 2 rounds exhibits a notable robustness increase over the original LeNet.
- Implementation considerations: MNIST rounding can turn perturbed inputs into non-adversarial examples, so fine-tuning adds a confidence constraint; the experiments fix α = 3.0.The baseline uses a corresponding confidence constraint with α = 0.15, and 8.3% of its MNIST training adversarial examples incur rounding errors.
6 Experiments
Experiments compare the proposed estimator with a baseline on MNIST and extend it to CIFAR-10. The proposed method yields more informative robustness estimates, exposes baseline-specific overfitting, and provides only modest robustness gains for NiN.
- Computational performance: The proposed estimator takes about 1.5 seconds per MNIST input, whereas removing iterative constraint solving increases runtime to more than two minutes.
- Estimator comparison: The proposed algorithm produces substantially higher adversarial-frequency estimates for every neural net, indicating better accuracy than the baseline.
- MNIST robustness: Baseline evaluation makes the two fine-tuned LeNet networks appear similarly robust, with both outperforming original LeNet, but the proposed statistics reveal different frequency-severity trade-offs.The baseline-tuned network has lower adversarial frequency but worse adversarial severity than the proposed network.
- MNIST robustness: According to the proposed metrics, the proposed MNIST fine-tuned network is substantially more robust than the baseline fine-tuned network.It has substantially lower adversarial frequency while maintaining similar adversarial severity.
- MNIST robustness: The baseline-tuned network overfits to adversarial examples generated by the baseline algorithm, whereas the proposed network learns examples from both algorithms.
- CIFAR-10 scaling: NiN has 91.31% test accuracy, 61.5% adversarial frequency, and adversarial severity of 2.82 pixels; proposed fine-tuning changes these to 59.6% and 3.88, respectively.Fine-tuned NiN accuracy is 90.35%, similar to the original, while robustness improves slightly, especially for smaller ϵ.
7 Conclusion
The paper formulates, estimates, and improves neural-net robustness by encoding it as a constraint system. It identifies better robustness methods for large networks and properties beyond robustness as future work.
- Conclusion: Robustness can be formulated, efficiently estimated, and improved by encoding the property as a constraint system.
- Scope boundary: The signed gradient algorithm cannot estimate adversarial severity because all adversarial examples it finds have L∞ norm ϵ.