Provable defenses against adversarial examples via the convex outer adversarial polytope

Eric Wong; J. Zico Kolter

Source-linked AI summary

Provable defenses against adversarial examples via the convex outer adversarial polytope

Eric Wong, J. Zico Kolter

arXiv:1711.00851v3Nov 2, 2017cs.LGcs.AImath.OC

TL;DR

The paper addresses the difficulty of defending classifiers against norm-bounded adversarial attacks with guarantees that remain valid under full attacker knowledge. It trains deep ReLU classifiers by optimizing over convex outer bounds through linear-program duality, achieving provable robustness including less than 5.8% MNIST test error for attacks with ℓ∞ norm below ε = 0.1.

Problem
Repeatedly evolving attacks challenge defenses, motivating classifiers guaranteed robust to norm-bounded perturbations even when the attacker has full model knowledge.
Method
The method trains deep ReLU networks by optimizing worst-case loss over convex outer bounds of adversarial polytopes, using a dual network for efficient linear-program optimization.
Results
The approach produces provable guarantees across several classification tasks, including less than 5.8% MNIST test error for attacks with bounded ℓ∞ norm below ε = 0.1.
Takeaways & Limitations
A few additional forward and backward passes through a modified network can yield guaranteed error bounds for any norm-bounded adversarial attack.
Takeaways & Limitations
The required identity-matrix propagation is infeasible for domains such as ImageNet, so scalability remains a major limitation.

Abstract

from arXiv · show

We propose a method to learn deep ReLU-based classifiers that are provably robust against norm-bounded adversarial perturbations on the training data. For previously unseen examples, the approach is guaranteed to detect all adversarial examples, though it may flag some non-adversarial examples as well. The basic idea is to consider a convex outer approximation of the set of activations reachable through a norm-bounded perturbation, and we develop a robust optimization procedure that minimizes the worst case loss over this outer region (via a linear program). Crucially, we show that the dual problem to this linear program can be represented itself as a deep network similar to the backpropagation network, leading to very efficient optimization approaches that produce guaranteed bounds on the robust loss. The end result is that by executing a few more forward and backward passes through a slightly modified version of the original network (though possibly with much larger batch sizes), we can learn a classifier that is provably robust to any norm-bounded adversarial attack. We illustrate the approach on a number of tasks to train classifiers with robust adversarial guarantees (e.g. for MNIST, we produce a convolutional classifier that provably has less than 5.8% test error for any adversarial attack with bounded $\ell_\infty$ norm less than $ε= 0.1$), and code for all experiments in the paper is available at https://github.com/locuslab/convex_adversarial.

1. Introduction

Adversarial examples and repeatedly evolving attacks make empirical defenses insufficient for high-stakes systems. The paper addresses this by training provably robust ReLU classifiers and detecting unseen adversarial examples with guaranteed zero false negatives, while accepting possible false positives.

Adversarial attacks have repeatedly bypassed defenses, including distillation, realistic-transformation assumptions, and black-box restrictions.
The potentially high cost of a single misclassification makes guaranteed robustness important for high-stakes machine learning systems.
The method trains deep ReLU classifiers guaranteed robust to any norm-bounded adversarial perturbation on the training set.
For previously unseen examples, the approach detects every adversarial example, although it may also flag some non-adversarial examples.
The approach evaluates provable guarantees across human activity recognition, MNIST, Fashion MNIST, and street view housing-number classification.
5.8% test error is provably achieved on MNIST against any attack with bounded ℓ∞ norm less than ε = 0.1.

2. Background and Related Work

Prior verification methods can reason about exact adversarial regions but are difficult to scale or integrate into robust training. This work connects adversarial defense with convex robust optimization, using tractable bounds to support provable guarantees for deeper and more general networks.

Exact SMT and integer-programming verifiers capture the adversarial polytope but are fundamentally combinatorial, limiting scalability and integration with robust training.
Layerwise norm-bound methods provide tractable perturbation bounds, but the paper reports that they are often many orders of magnitude looser than its outer bounds.
Prior guarantees include two-layer ℓ2 robustness and distributional Wasserstein robustness, while their translation to traditional settings is not established in the passage.
Compared with the concurrent semidefinite relaxation, this method applies to deep networks with arbitrary linear operator layers, including convolutional layers.
The paper frames its contribution as applying convex robust optimization to a convex relaxation of the adversarial polytope, yielding provable bounds on adversarial loss.
Figure 1 contrasts the non-convex adversarial polytope with an outer convex bound.

3. Training Provably Robust Classifiers

The paper trains provably robust ReLU classifiers by optimizing over a convex outer approximation of reachable activations, using an LP whose dual can be evaluated like a modified backpropagation network. The resulting certificates guarantee robustness within norm-bounded perturbations and support adversarial-example detection, while activation-bound computation remains the main scaling challenge.

3.1. Outer Bounds on the Adversarial Polytope: The method constructs a convex outer bound on the non-convex adversarial polytope of final-layer activations reachable under norm-bounded input perturbations.For multi-layer networks, the exact reachable set is non-convex; relaxing ReLU constraints produces a tractable outer approximation.
3.1. Outer Bounds on the Adversarial Polytope: The ReLU relaxation replaces activation equalities with upper convex envelopes using known lower and upper pre-ReLU bounds, and is exact when both bounds have the same sign.The exposition focuses on ℓ∞ perturbations, although the method extends to other norm balls.
3.1. Outer Bounds on the Adversarial Polytope: Robustness is certified by solving a linear program for each target class and checking that every outer-polytope objective value remains positive.A positive value means the true class activation cannot be lowered below a target class within the convex outer bound, so no norm-bounded perturbation can misclassify the example.
3.2. Efficient Optimization via the Dual Network: The LP dual feasible set is represented as a network resembling backpropagation, enabling guaranteed lower bounds through a modified backward pass.Additional variables for activations whose bounds span zero can improve the dual objective; any dual-feasible choice preserves the lower-bound guarantee.
3.3. Computing Activation Bounds: The main scalability limitation is activation-bound computation, which requires identity-matrix and intermediate-layer forward passes and scales poorly for larger inputs.The paper suggests bottleneck layers, PCA, or random projections as possible future scaling approaches, while noting that the method already handles larger networks than alternatives discussed.
3.4. Efficient Robust Optimization: All network terms, including bound computation, are differentiable, so standard stochastic-gradient and autodiff methods can train classifiers with guaranteed robustness when robust loss is low.The resulting bounds also provide provable robustness and adversarial-detection metrics for ReLU networks, with tightness improving when training explicitly minimizes robust loss.
3.5. Adversarial Guarantees: A certified example has no adversarial perturbation within the specified ℓ∞ radius that changes its classification, and the fraction lacking such certificates defines robust error.The certificate therefore upper-bounds the error achievable by any adversarial attack.

4. Experiments

Experiments demonstrate provable robustness across small and medium-scale classification tasks, including fully connected and convolutional networks. Robust training substantially improves certified resistance to norm-bounded attacks, while scaling remains costly and challenging.

Experimental scope: The experiments cover small and medium-scale problems, including image classification with convolutional networks beyond very small fully connected models.All experiments were run on a single Titan X GPU.
Binary classification: Zero robust error is achieved on the 2D binary classification task when training with ℓ∞ balls of radius ϵ = 0.08.Standard training leaves points classified differently within their perturbation balls.
MNIST: 5.82% robust test error is achieved on MNIST at ϵ = 0.1, compared with 1.80% clean test error.FGSM and PGD achieve 3.93% and 4.11% error respectively on the robustly trained classifier, versus 50.01% and 81.68% for standard training.
MNIST: Robust training pushes the correctly classified MNIST examples’ lower-bound distance to the decision boundary from around 0.007 to 0.1.The robust model was trained with ϵ = 0.1, and incorrectly classified examples tend to lie closer to the decision boundary.
Other experiments: 34.53% robust error is achieved on Fashion-MNIST at ϵ = 0.1, close to the 31.63% PGD error rate.The same architecture as MNIST is used.
Other experiments: 21.90% robust error is achieved on HAR at ϵ = 0.05, while SVHN reaches a 42.09% robust error bound at ϵ = 0.01.On SVHN, PGD achieves 34.52% error; the stated goal is provable guarantees rather than state-of-the-art performance.
Limitations: Scaling to ImageNet-sized classifiers remains challenging, and MNIST training takes about 5 hours, two to three orders of magnitude more than naive training.The authors describe the approach as less combinatorially expensive than integer-programming or satisfiability-based methods.

5. Conclusion

The paper trains provably robust classifiers using linear programming and duality, while reducing the resulting optimization to a few modified network passes. It identifies scalability and attacks beyond norm bounds as key directions for improvement.

Linear programming and duality provide the foundation for training classifiers with provable robustness to norm-bounded adversarial attacks.
A few passes through the original network with larger batch sizes yield a guaranteed bound on robust error and loss without costly optimization.
Scalability is limited because computing bounds requires identity-matrix propagation, making the approach infeasible for domains such as ImageNet.
The method must be extended beyond simple norm bounds to cover attacks such as manufactured glasses and geometric transformations.
Optimizing over relaxed convex networks and representing dual problems with non-convex networks may apply beyond adversarial examples to neural-network inversion and latent-space optimization.

A.2. Proof of Theorem 1

The proof derives the LP dual and shows that its constraints can be represented as a deep network. ReLU relaxation variables induce leaky-ReLU-like dual operations, with a specific α choice recovering the proposed dual network.

The dual of the adversarial LP can be written as a deep network, providing feasible dual solutions that can be optimized.
Dual variables λ, µ, and τ correspond respectively to the relaxed ReLU upper bound and the lower bounds z ≥ 0 and z ≥ ẑ.
The resulting dual propagation has leaky-ReLU form, with slopes determined by ReLU bounds and an adjustable negative slope between 0 and 1.
Choosing α = u_i,j/(u_i,j − l_i,j) makes the conjugate-function derivation match the proposed dual network exactly.

A.4. Proof of Theorem 2

The proof upper-bounds worst-case adversarial loss by combining the adversarial polytope with monotonicity of the loss and the LP-dual lower bound. Applying the bound elementwise yields a certified loss bound.

For a monotonic loss function satisfying Property 1, the worst-case adversarial loss is upper-bounded using J_ε and the dual network g_θ.
The proof rewrites the adversarial problem over the adversarial polytope Z_ε(x).
Monotonicity permits replacing class-wise objectives with elementwise maxima for incorrect labels and an elementwise minimum for the true label.
Applying the dual lower bound to each class-wise adversarial objective produces the final upper bound on adversarial loss.

A.5. Proof of Corollary 1

The corollary establishes robustness when the certificate prevents every alternative label from exceeding the model’s predicted label throughout the adversarial polytope.

If the certificate holds, no perturbation within ℓ∞ distance ε can change the classifier’s output around the data point.
The proof combines the dual lower bound with the certificate to compare the predicted label against every alternative label.
Robustness follows because the predicted class logit remains at least as large as every alternative throughout the adversarial polytope.

B. Experimental Details

The experiments visualize and evaluate the convex outer adversarial polytope, comparing it with the true polytope and naive layerwise bounds before and after robust training.

Problem Generation: 12 points are sampled in [0, 1] xy-space with pairwise ℓ∞ distance at least 0.16, and the classifier targets robustness at ϵ = 0.08.Each point receives a random label.
Visualizations of the Convex Outer Adversarial Polytope: Figure 6 compares true and convex-outer polytopes for a random 2-100-100-100-100-2 network at ϵ values 0.05, 0.1, and 0.25.The output and input spaces are both two-dimensional, allowing dense enumeration of the true adversarial polytope.
Visualizations of the Convex Outer Adversarial Polytope: As ϵ increases, more activations become unstable and the convex relaxation becomes looser; when no activation changes, the bound is exact.The relaxation has greater freedom for activations whose signs can change.
Comparison to Naive Layerwise Bounds: Naive layerwise bounds are extremely loose for multilayer networks because they replace the convex ReLU approximation with larger activation boxes.They are described as not useful for robust classification in this setting.
Outer Bound after Training: After robust training, the convex outer bound is empirically quite tight for a training example.Figure 7 compares the actual adversarial polytope with the convex approximation at the learned network weights and chosen ϵ.

B.2. MNIST

The MNIST experiments examine optimization, learned filters, activation-index distributions, and bound tightness for a robust convolutional classifier.

Training: Starting ϵ at 0.05 and increasing it uniformly to 0.1 over the first 50 epochs enabled convergence for all observed seeds that failed at ϵ = 0.1.Training used Adam with learning rate 0.001, minibatches of 50, and 100 epochs.
MNIST convolutional filters: Robustly trained MNIST convolutional filters are highly sparse, with some filters containing all zero weights.The first- and second-layer filter visualizations attribute sparsity to the ℓ1 term in (6).
Activation index counts: The unstable activation-index set I_i is small across all three layers, making the bound tighter and cheaper to compute.The final term of (6) is summed only over activations in I_i.
Tightness of bound: The bound computed from the dual problem is extremely tight against the exact primal LP for the robustly trained classifier.The comparison is reported relative to random and standard-training networks in Figure 11.
Learning curves: The MNIST learning curves show no overfitting, with performance suspected to be limited by model capacity.Both ordinary and robust loss and error curves are plotted over epochs.

B.4. HAR

The HAR experiments test how the robust bound changes with perturbation size and compare it with attack-achievable error after training.

Learning Curves: The HAR learning curves indicate no benefit from scaling to more layers, with the bottleneck attributed to problem simplicity and the difficulty implied by ϵ.Loss, error, and robust variants are plotted over epochs.
Tightness of bound: For a 500-unit single-hidden-layer network, the robust bound matches the error achievable by FGSM across the tested ϵ values.The result is reported in Table 2 after robust training.
Tightness of bound: Larger ϵ produces a less accurate robust model because the adversarial problem becomes more difficult and may be impossible for some data points.Despite this, the robust bounds remain extremely close to FGSM-achievable error.

B.5. SVHN

The SVHN experiments track scheduled and fixed-ϵ robust metrics during training and relate their behavior to model capacity.

Learning Curves: The robust testing curve uses ϵ = 0.01 throughout, whereas other curves use the scheduled ϵ value.The schedule increases uniformly from ϵ = 0.001 to ϵ = 0.01 over the first 50 epochs.
Learning Curves: Scheduled-ϵ metrics increase after the first few epochs until reaching the target ϵ, while fixed-ϵ robust testing metrics decrease until that target is reached.The curves are shown for loss and error rate.
Learning Curves: Because error increases with ϵ, the results suggest that the given model capacity cannot achieve better SVHN robust performance and that a larger model is needed.This interpretation is based on the robust testing curve evaluated at ϵ = 0.01.