Source-linked AI summary
Certified Defenses against Adversarial Examples
Aditi Raghunathan, Jacob Steinhardt, Percy Liang
TL;DR
Adversarial defenses can be defeated by stronger attacks, motivating certificates that cover all attacks in a specified perturbation class. The paper uses a semidefinite relaxation to produce a differentiable worst-case-loss upper bound and trains networks against it. On MNIST, the resulting certificate limits error to 35% for ℓ∞ perturbations of ϵ = 0.1.
Problem
Stronger attacks can defeat defenses evaluated against known attacks, while exact worst-case error over an ℓ∞ ball is computationally intractable.
Method
A semidefinite relaxation computes a differentiable upper bound on worst-case loss for one-hidden-layer networks, which is jointly optimized with network parameters.
Results
35% is the certified maximum MNIST test error for ℓ∞ perturbations of size ϵ = 0.1, alongside 4.2% clean test error.
Takeaways & Limitations
The method provides a certifiable, trainable, and scalable defense against adversarial examples for two-layer networks.
Takeaways & Limitations
The approach is limited to two-layer networks, whereas a contrasting approach extends to deeper networks and trains a four-layer CNN with a provable 5.7% adversarial-error bound.
Abstract
from arXiv · showhide
While neural networks have achieved high accuracy on standard image classification benchmarks, their accuracy drops to nearly zero in the presence of small adversarial perturbations to test inputs. Defenses based on regularization and adversarial training have been proposed, but often followed by new, stronger attacks that defeat these defenses. Can we somehow end this arms race? In this work, we study this problem for neural networks with one hidden layer. We first propose a method based on a semidefinite relaxation that outputs a certificate that for a given network and test input, no attack can force the error to exceed a certain value. Second, as this certificate is differentiable, we jointly optimize it with the network parameters, providing an adaptive regularizer that encourages robustness against all attacks. On MNIST, our approach produces a network and a certificate that no attack that perturbs each pixel by at most ε= 0.1 can cause more than 35% test error.
1 INTRODUCTION
Adversarial examples expose a serious vulnerability because stronger attacks repeatedly defeat defenses evaluated only against known attacks. The paper addresses this arms race with a trainable upper-bound certificate for two-layer networks, achieving a certified MNIST error bound under ℓ∞ perturbations.
- Stronger attacks have repeatedly rendered defenses such as defensive distillation and FGSM adversarial training ineffective.
- Exact worst-case error over an ℓ∞ ball is computationally intractable, while heuristic attack losses provide only lower bounds on that error.
- Sharp curvature can make local linear approximations inaccurate, causing FGSM-based attack evaluations to underestimate the optimal attack.
- A semidefinite relaxation efficiently computes an upper bound on worst-case loss for one-hidden-layer networks, certifying robustness against all attacks for a given input.
- The differentiable certificate is jointly optimized with network parameters as a regularizer encouraging robustness against all ℓ∞ attacks.
- 4.2% clean test error accompanies a certificate that no ℓ∞ perturbation with ϵ = 0.1 can cause more than 35% test error on MNIST.
2 SETUP
The setup defines score-based classification, pairwise margins, and an ℓ∞ attack model in a white-box setting. For one-hidden-layer networks, the optimal attack maximizes an incorrect-versus-correct margin over the perturbation ball.
- A score-based classifier assigns the class with the highest class score.
- The pairwise margin f_ij(x) is positive exactly when class i scores above alternative class j.
- The paper studies linear classifiers and one-hidden-layer neural networks with scoring functions parameterized by W and V.
- The neural-network activation is applied elementwise, with examples including ReLU and sigmoid functions whose gradients are bounded.
- An attacker may perturb every feature by at most ϵ, restricting the perturbed input to an ℓ∞ ball around the original input.
- In the white-box setting, the optimal untargeted attack maximizes an incorrect class's pairwise margin over the perturbation ball.
3 CERTIFICATE ON THE ADVERSARIAL LOSS
The paper bounds worst-case adversarial loss for two-layer networks by replacing an intractable optimization with a tractable semidefinite relaxation. The resulting certificate covers all attacks within the perturbation ball and extends to multiclass pairwise margins.
- The optimal attack maximizes the incorrect-versus-correct pairwise margin within the ℓ∞ perturbation ball, but computing it is intractable.For binary classification, an attack succeeds when the optimized margin exceeds zero.
- Local gradient approximations such as FGSM can fail when defenses create sharp curvature near training points.Such gradient masking makes the linear approximation unreliable while stronger attacks can still find large margins.
- The method integrates gradients across the entire perturbation ball rather than evaluating only the gradient at the original input.This produces an exact gradient-based expression before applying tractable upper bounds.
- For two-layer networks, bounded activation derivatives reduce the gradient maximization to a non-convex quadratic program, then an SDP relaxation supplies an upper bound.The relaxation is motivated by the similarity of the quadratic program to MAXCUT and is efficiently approximable through semidefinite programming.
- The resulting certificate upper-bounds adversarial loss for any attacker and can be computed once for a model because the SDP depends only on network weights.The construction generalizes from binary margins to pairwise multiclass margins.
4 TRAINING THE CERTIFICATE
The certificate becomes a training regularizer by jointly optimizing classification loss, robustness terms, network parameters, and dual variables. Duality makes this optimization efficient and also provides a directly usable robustness certificate during training.
- The training objective combines classification loss with regularization terms that reduce the certificate-related pairwise robustness quantities.This targets both predictive margins and the bound's adversarial component.
- Directly differentiating through the SDP is slow, motivating a dual formulation with additional variables optimized alongside the network parameters.The dual equivalence removes the need to solve the SDP separately for every gradient computation.
- The dual objective can be optimized efficiently with stochastic gradient methods using the maximum eigenvalue of a matrix.Iterative methods such as Lanczos compute the required top eigenvector for gradients.
- Any dual objective value is an upper bound on the primal optimum, yielding a dual certificate of robustness during training.The trained model therefore obtains a quick upper bound on worst-case adversarial loss without repeatedly optimizing an SDP.
5 OTHER UPPER BOUNDS
The paper compares its certificate with simpler spectral- and Frobenius-norm upper bounds. These alternatives follow from norm-based bounds on the network's response to perturbations, while the proposed comparison evaluates their relative tightness.
- The experiments compare the proposed upper bound with spectral and Frobenius norm bounds.These comparisons concern upper bounds on adversarial loss rather than exact worst-case loss.
- The spectral bound uses the output-weight norm, activation contractivity, and the spectral norm of the first-layer weights.It bounds the perturbed network response using the maximum singular value of the weight matrix.
- The spectral-norm vulnerability measure has been considered in prior work on adversarial examples.The cited prior approaches also relate robustness to layerwise spectral norms.
- The Frobenius bound replaces the spectral norm with the larger Frobenius norm, making it a corresponding but potentially looser upper bound.The construction follows from ∥W∥F ≥ ∥W∥2.
6 EXPERIMENTS
Experiments on MNIST evaluate certified upper bounds, attack performance, and training objectives for two-layer networks. Training directly against the SDP certificate yields the clearest combination of robustness and certifiability, while comparisons expose architecture and optimization trade-offs.
- Evaluation setup: The MNIST study evaluates upper bounds on adversarial loss against PGD lower bounds, using the proposed SDP, Frobenius, and spectral certificates.Exact adversarial loss is difficult to compute, so attack losses provide lower bounds for comparison.
- Certificate quality: SDP-NN is the only evaluated network that is both robust to attacks and has relatively tight upper bounds.Its certificate is tighter than the Frobenius and spectral bounds across the considered networks.
- Training objective: Spectral and Frobenius regularization do not encourage adversarial robustness as effectively as the SDP certificate training objective.Their PGD performance is worse than SDP-NN’s certified upper bound against all attacks.
- Attack evaluation: The SDP-trained network shows substantial robustness against PGD, Carlini-Wagner, and FGSM despite not being trained specifically against any of them.Figure 3b compares SDP-NN against all three attacks.
- Comparisons: At ε = 0.1, SDP-NN has 16% error against PGD and a 35% upper bound against any attack, compared with 11% PGD error for same-architecture AT-NN.The authors attribute most of the remaining gap to smaller network depth rather than SDP conservatism.
- Implementation details: Weighted regularization improves both the PGD lower bound and SDP upper bound, while automatically obtained dual certificates nearly match exactly solved SDP certificates.The dual certificates also enable robustness tracking during training and hyperparameter tuning.
7 DISCUSSION
The discussion positions certifiable training as a response to empirical attack–defense cycles and relates the approach to verification, robustness certification, and broader security settings. It also emphasizes that verification remains difficult for arbitrary networks, while suggesting that trainable models can be made more amenable to certification.
- The paper proposes producing robustness certificates and training networks against them to obtain provable protection against adversaries.
- The approach is presented alongside convex-relaxation, SMT-based, gradient-based, and other verification methods, with differing computational trade-offs and guarantees.
- The paper situates adversarial examples within a broader literature of attacks and defenses, including poisoning attacks and multiple test-time attack strategies.
- Certificate-based performance guarantees are relevant to safety-critical systems, self-driving cars, and security against training-time attacks.
- The discussion notes that robustness verification for arbitrary neural networks should be hard, analogously to undecidability results for general program properties.
- The authors suggest that learning networks amenable to verification may support stronger robustness specifications for natural-image representations.
A DUALITY
The appendix derives a dual formulation for the semidefinite relaxation by adding a redundant trace constraint, forming a Lagrangian, and applying minimax duality. Nonnegativity of the dual variable is then handled through the maximizing term.
- The primal semidefinite program maximizes ⟨M, P⟩ subject to P ⪰0 and diag(P) ≤1.
- A redundant constraint tr(P) ≤d + m + 1 is added because the SDP dimension and diagonal bound already imply it.
- The derivation forms a Lagrangian for diag(P) ≤1 while retaining the positive-semidefinite and trace constraints.
- Minimax duality swaps the minimization and maximization order to obtain the dual optimization problem.
- The dual variable c can be optimized without an explicit nonnegativity constraint because the maximizing term favors replacing c with max(c, 0).