Provable defenses against adversarial examples via the convex outer adversarial polytope

1. 01What problem does this paper attempt to solve?

   How to train deep ReLU classifiers that are provably robust to arbitrary norm-bounded adversarial perturbations, and detect adversarial examples at test time with zero false negatives.

   Core problem: train deep ReLU classifiers that are provably robust to adversarial perturbations bounded in an arbitrary norm, rather than only performing well under known attacks.

   • Problem setting and importance: The authors state that the attack-defense of adversarial examples has fallen into an "arms race"—defenses such as distillation have been successively broken by new attacks, black-box attacks are likewise effective, and detecting adversarial examples is also difficult; for high-risk applications, the cost of a classifier being fooled once may be high.
   • Shortcomings of existing methods: The authors argue that exact verification methods (SMT, integer programming) are combinatorial in nature, hard to scale to medium-sized networks, and too computationally expensive to be embedded in a robust training pipeline; layerwise bounds (such as Parseval networks) are worse than this paper's outer approximation bound by "multiple orders of magnitude" (numerical comparisons are given in Appendix B.1).
   • Core observation: Construct a convex outer approximation to the adversarial polytope (i.e., the set of final-layer activations reachable when the input is perturbed within the norm ball); if no point inside the outer approximation can change the predicted class, the sample is proven robust. The worst-case loss over this outer approximation is a linear program, and its dual problem can itself be written as a network resembling backpropagation.
   • What the paper proposes: A robust optimization training pipeline that computes a provable upper bound on the robust loss with a single backward pass through the dual network, and minimizes it with a standard SGD variant; it also gives a certificate for detecting adversarial examples at test time (zero false negatives, but normal samples may be falsely flagged).
   • Threat model:
     • Attacker's goal: perturb the input to make the classifier misclassify.
     • Attacker's knowledge: the authors assume the attacker has full knowledge of the classifier, without relying on "security through obscurity".
     • Attacker's capability: perturbations with ℓ∞ norm at most ε (experiments use ε=0.1/0.05/0.01); the paper states the method can extend to other ℓp norms, but experiments only do ℓ∞.
     • Victim system: a k-layer feedforward ReLU network (including linear operator layers such as convolutions).

   Collapse this answer

2. 02What related research exists?

   Related work falls into four groups: exact combinatorial verification, computable robust bounds, contemporaneous certified defenses, and the connection between robust optimization and adversarial training.

   Exact (combinatorial) verification

   • SMT solvers (Huang et al., 2017; Katz et al., 2017; Ehlers, 2017; Carlini et al., 2017) and integer programming methods (Lomuscio & Maganti, 2017; Tjeng & Tedrake, 2017; Cheng et al., 2017) — reason over the exact adversarial polytope. The paper notes that PLANET (Ehlers, 2017) among them also uses the same ReLU linear relaxation as this paper, but only as a substep of combinatorial solving; the authors believe such methods are difficult to scale to medium-sized networks and too costly to embed in training.

   Computable robust bounds

   • Parseval networks (Cisse et al., 2017) — regularize the ℓ2 operator norm of weight matrices; Peck et al. (2017) — limit layerwise norm expansion. The paper says it studies similar layerwise bounds and gives a comparison stating that they are usually orders of magnitude worse than the outer approximation bounds in this paper (Appendix B.1).
   • Hein & Andriushchenko (2017) — provable guarantees for ℓ2 perturbations on two-layer networks, but training uses a surrogate for the bound rather than the exact bound; Sinha et al. (2018) — certified robustness based on the Wasserstein distribution distance, which the paper says it is unclear how to translate into the traditional norm-bounded adversarial model.

   Closest contemporaneous work

   • Raghunathan et al. (2018) — relax the adversarial polytope based on semidefinite programming (also dualized into an eigenvalue problem) and use it for robust training. The paper notes that it applies only to two-layer fully connected networks, whereas this paper applies to deep networks containing arbitrary linear operator layers such as convolutions; the authors state that on MNIST its guaranteed bound is 35% error and this paper's robust bound is 5.8% error, while also noting that on the other's small network the two kinds of bounds are complementary (this paper has lower robust test error and higher standard test error), and the authors consider combining the two kinds of bounds a future direction.

   Robust optimization and adversarial training

   • Robust optimization (Ben-Tal et al., 2009; Xu et al., 2009) — solve optimization when the problem data belong to a bounded set; Goodfellow et al. (2015) note that adversarial robustness of linear models is equivalent to ℓ1 weight penalty; Madry et al. (2017) use a non-convex min-max formulation for adversarial training. The authors position this paper as the next step in this connection: because it uses convex relaxation, it can give provable bounds.

   Baselines and benchmarks: the attack baselines in the experiments are FGSM (Goodfellow et al., 2015) and PGD (Madry et al., 2017), compared against networks of the same architecture trained conventionally; the datasets are MNIST, Fashion-MNIST, HAR, SVHN and a 2D synthetic example.

   Collapse this answer

3. 03How does the paper address this problem?

   Write the convex outer approximation of the adversarial polytope as an LP, use its dual network in a single backpropagation to obtain a provable upper bound on the robust loss, then minimize it with SGD.

   Overall approach: construct a convex outer approximation to the adversarial polytope of a ReLU network, and write "the worst-case loss within the outer approximation" as a linear program; prove that the dual feasible region of this LP is itself a network resembling backpropagation (the dual network), so that a single modified backpropagation yields a provable upper bound on the robust loss, which is then trained with standard stochastic gradient methods.

   Problem setup and convex outer approximation

   • The network is a k-layer feedforward ReLU network, ẑi+1 = Wi zi + bi, zi = max{ẑi, 0}, where Wi may be a matrix multiplication or a linear operator such as convolution.
   • The adversarial polytope is defined as Z_ϵ(x) = {f_θ(x+Δ) : |Δ|_∞ ≤ ϵ}, i.e., the reachable set of final-layer activations when the input is perturbed within the ℓ∞ ball; this set is non-convex.
   • Key relaxation: given elementwise lower and upper bounds ℓ, u on the pre-activation of a ReLU, replace the ReLU equality with its upper convex envelope (z ≥ 0, z ≥ ẑ, −uẑ + (u−ℓ)z ≤ −uℓ); the relaxation is exact when ℓ and u have the same sign. The resulting outer approximation is denoted Z̃ε(x).

   Dual network

   • Minimizing cT ẑk over the outer approximation (c = ey* − ey_targ) is an LP; if the objective value is positive for all target classes, the sample is proven robust within the ε ball.
   • Theorem 1: the dual of this LP can be written as a k-layer feedforward network gθ(c, α): νk = −c, ν̂i = WiT νi+1, with free variables αi,j ∈ [0,1] introduced for activations that cross zero (set Ii), in a form resembling leaky ReLU.
   • In practice α is not optimized explicitly; instead a fixed dual feasible solution αi,j = ui,j / (ui,j − ℓi,j) is taken, making the entire backpropagation a linear function; the authors say this choice is derived from the conjugate set of the ReLU relaxation (Appendix A.3), and that the bounds are quite tight in practice.
   • For ℓp norm perturbations, one only needs to replace the ℓ1 norm in the dual objective with the dual norm ℓq; the paper's experiments do only ℓ∞.

   Layerwise activation bound computation

   • The dual objective Jε(x, gθ(c)) can give bounds for any linear function cT ẑk; taking c = I and c = −I yields the upper and lower bounds of each activation (Algorithm 1, computed incrementally layer by layer).
   • The computational cost mainly comes from two places: passing the "identity matrix" forward through the input layer of the network dimension by dimension, and doing one forward pass from the intermediate layer for each activation that crosses zero; the authors acknowledge this is the least scalable part and list bottleneck layers, random projections, etc. as future work.

   Robust optimization and guarantees

   • Theorem 2: for a monotone loss L satisfying translation invariance (Property 1) (cross-entropy, hinge, and 0-1 loss all satisfy it), the worst-case adversarial loss is upper-bounded by L(−J_ϵ(x, g_θ(e_y 1^T − I)), y), a quantity called the robust loss; the overall objective is differentiable and can be trained with any SGD variant and autodiff.
   • Corollary 1: if Jε(x, gθ(ey*1T − I)) ≥ 0 (elementwise), then the sample is provably robust within the ε ball; the proportion of samples that do not satisfy the certificate is called robust error, a provable upper bound on the error achievable by any adversarial attack.
   • Corollary 2: replacing the true label with the predicted label ŷ, if the same condition holds then x cannot be an adversarial example — test-time detection has zero false negatives (no adversarial example is missed), but may falsely flag normal samples.
   • Newton's method can also be used to find, for each sample, the maximum ε for which a robustness certificate exists, as a lower bound on the ℓ∞ distance to the decision boundary (Equation 17).

   Collapse this answer

4. 04What experiments did the paper conduct?

   Train robust networks on 2D synthetic data, MNIST, Fashion-MNIST, HAR, and SVHN, and report clean/FGSM/PGD error and robust error upper bounds.

   Experimental setup

   • Networks tested: the 2D example uses a 2-100-100-100-100-2 fully connected network; MNIST, Fashion-MNIST, SVHN use the same ConvNet (two convolutional layers with 16 and 32 channels, stride 2, followed by fully connected layers of 100 and 10); HAR uses a single-layer fully connected network with 500 hidden units.
   • Datasets: MNIST, Fashion-MNIST (Xiao et al., 2017), HAR (Anguita et al., 2013), SVHN, and randomly generated 12-point 2D binary classification data (Appendix B.1).
   • Attack baselines and comparisons: FGSM and PGD; the comparison models are normally trained networks of the same architecture.
   • Metrics: test error, FGSM error, PGD error, robust error bound (the proportion of samples that are not provably robust, an upper bound on the error reachable by any attack).
   • Training parameters: Adam; learning rate 0.001 for MNIST/Fashion-MNIST/SVHN, 0.0001 for HAR; batch size 50 (20 for SVHN); all trained for 100 epochs; MNIST and SVHN use an ε increasing schedule (MNIST uniformly increases from 0.05 to 0.1 over the first 50 epochs, SVHN from 0.001 to 0.01).
   • Hardware: a single Titan X GPU; MNIST robust training for 100 epochs takes about 5 hours.

   Main results

   According to Table 1 (rows are different problems and whether robust training is used, ε as shown):

   Swipe horizontally to read the table

   Problem	Robust training	ε	Test error	FGSM	PGD	Robust bound
   MNIST	×	0.1	1.07%	50.01%	81.68%	100%
   MNIST	√	0.1	1.80%	3.93%	4.11%	5.82%
   Fashion-MNIST	×	0.1	9.36%	77.98%	81.85%	100%
   Fashion-MNIST	√	0.1	21.73%	31.25%	31.63%	34.53%
   HAR	×	0.05	4.95%	60.57%	63.82%	81.56%
   HAR	√	0.05	7.80%	21.49%	21.52%	21.90%
   SVHN	×	0.01	16.01%	62.21%	83.43%	100%
   SVHN	√	0.01	20.38%	33.28%	33.74%	40.67%

   • The authors point out that the robust error bound of the robust models is lower than the error reached by PGD attacks on the normally trained models; on the robust models, the FGSM/PGD errors are both lower than their robust bound.
   • The cost is a rise in clean error: on all four datasets the test error of the robust models is higher than that of the normal models (see table).
   • The authors state that the 5.8% MNIST robust error compares with the 35% guarantee bound of Raghunathan et al. (2018), and that it is the largest provably verified network known to the authors.

   Tightness analysis of the bound

   • What was measured: on the MNIST convolutional model, the primal LP is solved exactly and compared with the dual lower bound (Figure 11); on the HAR single-layer network, the FGSM error and the robust bound are compared after training at different ε (Table 2).
   • Results: Table 2 shows that on the HAR single-layer network after training, the lower bound at each ε is almost equal to the FGSM error (e.g., at ε=0.05, FGSM 22.20%, bound 22.80%; at ε=1, both are 81.80%), on which basis the authors call the bound tight in this case; in Figure 11 the dual lower bound of the robustly trained model is close to the primal solution, and the gap is larger for randomly initialized and normally trained models (the authors state that the three groups of curves in the figure differ in their degree of separation).
   • Random network visualization: Appendix Figure 6 shows that on a random network, when ε is small (0.05) the outer approximation almost coincides with the true polytope, and as ε grows (0.1, 0.25) the bound becomes looser; the naive layerwise bound gives ẑk,1 ∈ [−11.68, 13.47] while the true range is about [1.81, 1.85], which the authors call "essentially useless".

   2D example and maximum ε distance

   • 2D example: at ε=0.08, the normally trained classifier has a misclassified point within the ℓ∞ ball of every point; robust training achieves zero robust error (Figure 3, per the authors).
   • Maximum ε distance: Newton's method (5–6 steps) is used to compute the maximum ε at which each test sample is provably robust (Figure 5); under normal training the lower bound from correctly classified samples to the decision boundary is about 0.007, and robust training (ε=0.1) pushes it to 0.1; misclassified samples are generally closer to the decision boundary (per the authors).

   Other ablations and analyses

   • ε schedule: on MNIST, training directly with ε=0.1 fails to converge for some random seeds; after uniformly increasing from 0.05 to 0.1 over the first 50 epochs, all these seeds converge (Appendix B.2).
   • Convolutional kernel sparsity: after robust training, the two convolutional kernels on MNIST are highly sparse, some entirely zero, which the authors attribute to the ℓ1 term in Equation (6) (Figures 8, 9).
   • Distribution of activation sets: the histograms in Figure 10 show that the number of activations in the cross-zero set Ii at each layer is small, which the authors state makes the bound tighter and cheaper to compute.
   • SVHN learning curves: in Figure 14 the metrics computed according to the schedule ε keep rising after the first several epochs, which the authors take to indicate that robust training on SVHN has reached a bottleneck given the model capacity and requires a larger model.

   Collapse this answer

5. 05What are some points that can be further explored?

   The authors point out two major directions: scalability and attack model coverage; experiments are limited to four small-to-medium datasets and the ℓ∞ norm.

   Limitations and future directions noted by the authors

   • Scalability (Section 3.3 and Section 4.4): computing activation bounds requires passing the identity matrix forward through the network dimension by dimension (one sample per input dimension, and more for each activation that crosses zero in intermediate layers), which is "completely infeasible" at ImageNet scale; the authors propose possible approaches such as bottleneck layers, other dual bounds, and random projections, but explicitly say this remains future work.
   • Attack model coverage (5. Conclusion): attacks outside the norm ball need to be characterized; the authors cite Sharif et al. (2016)'s eyeglass attack and Engstrom et al. (2017)'s rotation and translation attacks as examples that are not ℓ∞-bounded, and believe there is still a great deal of work in understanding broader sets of adversarial examples (possibly highly non-convex input sets).
   • Combining complementary bounds (2. Background and Related Work): the authors note that on small networks the bounds in this paper are complementary to the SDP bounds of Raghunathan et al. (2018) (this paper has lower robust test error and higher standard test error), and consider finding ways to combine the two kinds of bounds a useful future direction.
   • Broader application of the method (5. Conclusion): the authors believe that general techniques such as optimizing relaxed convex networks and representing dual problems with non-convex networks may apply to problems beyond adversarial examples that require optimizing over network inputs or latent spaces.

   Scope of experiments

   • The networks tested have three architectures in total: a 5-layer fully connected network for the 2D example, a two-layer convolutional ConvNet shared by MNIST/Fashion-MNIST/SVHN, and a single-layer network with 500 hidden units for HAR (Section 4).
   • The attacks evaluated are FGSM and PGD, with perturbations all in the ℓ∞ norm; the paper says the method can be extended to other ℓp norms, but the experiments report only ℓ∞ (Section 3.2, Table 1).
   • Training all uses Adam, 100 epochs, batch size 50 (20 for SVHN); the paper does not report the number of repetitions or variance for each result (Appendix B).
   • Empirical evaluation of bound tightness is conducted on the MNIST convolutional model (Figure 11) and the HAR single-layer network (Table 2); Fashion-MNIST and SVHN do not report comparison with the original LP.
   • The paper does not report numerical false positive rates for test-time detection (Corollary 2), only stating that detection has zero false negatives and may falsely flag normal samples (Section 3.5).

   Collapse this answer

6. 06Summarize the main content of the paper

   Use the dual network to reduce robust training to a few forward/backward passes, giving provable robust error upper bounds on four datasets.

   A defense paper on provable adversarial robustness: against the arms-race situation where "defenses are always bypassed by new attacks", the authors propose training deep ReLU classifiers that are provably robust to arbitrary ℓ∞-bounded perturbations, assuming the attacker fully knows the model.

   • Method: Construct a convex outer approximation to the adversarial polytope (a linear relaxation of ReLU), write the worst-case loss as an LP; prove that its dual feasible region is a network resembling backpropagation, and after taking a fixed dual feasible solution, a single backward pass yields an upper bound on the robust loss, which is fully differentiable and trained with standard SGD; the same certificate can detect adversarial examples at test time with zero false negatives.
   • MNIST (ε=0.1, two-layer convolutional network): robust test error upper bound 5.82%, FGSM/PGD only reach 3.93%/4.11%; the normally trained model has PGD error 81.68% (Table 1).
   • Other datasets: Fashion-MNIST (ε=0.1) robust bound 34.53%, HAR (ε=0.05) 21.90%, SVHN (ε=0.01) 40.67%, all lower than the PGD error of the normally trained models (Table 1).
   • Tightness of the bound: on HAR single-layer network after training, the lower bound at each ε is almost equal to the FGSM error (Table 2); on the MNIST robust model the dual lower bound is close to the exact LP solution (Figure 11).
   • Cost and conclusion: clean error rises (MNIST 1.07%→1.80%), MNIST training takes about 5 hours, two to three orders of magnitude more expensive than normal training; the authors state this is the largest provably verified network at the time, and point out that scaling to ImageNet scale and covering attacks beyond the norm ball are future directions.

   Collapse this answer

Related papers