Source-linked AI summary
Efficient Neural Network Robustness Certification with General Activation Functions
Huan Zhang, Tsui-Wei Weng, Pin-Yu Chen, Cho-Jui Hsieh, Luca Daniel
TL;DR
Robustness certification seeks tractable lower bounds on minimum adversarial distortion, but general activation functions remain insufficiently addressed. CROWN uses linear or quadratic activation bounds with adaptive surrogate selection, improving ReLU-network certificates while efficiently handling several general activations.
Problem
Generic robustness certification for activation functions beyond piece-wise linear ReLU remains largely unexplored, despite the challenge of finding minimum adversarial distortion.
Method
CROWN certifies neural networks by bounding general activation functions with linear or quadratic upper and lower functions and adaptively selecting bounds for each neuron.
Results
CROWN improves certified lower bounds on ReLU networks by up to 26% over previous work and efficiently certifies non-trivial bounds for ReLU, tanh, sigmoid, and arctan networks.
Takeaways & Limitations
CROWN provides an efficient framework for certified lower bounds across large neural networks with different activation functions.
Takeaways & Limitations
The framework’s global bounds include additional terms beyond the linear ϵ term whose effects are not characterized here.
Abstract
from arXiv · showhide
Finding minimum distortion of adversarial examples and thus certifying robustness in neural network classifiers for given data points is known to be a challenging problem. Nevertheless, recently it has been shown to be possible to give a non-trivial certified lower bound of minimum adversarial distortion, and some recent progress has been made towards this direction by exploiting the piece-wise linear nature of ReLU activations. However, a generic robustness certification for general activation functions still remains largely unexplored. To address this issue, in this paper we introduce CROWN, a general framework to certify robustness of neural networks with general activation functions for given input data points. The novelty in our algorithm consists of bounding a given activation function with linear and quadratic functions, hence allowing it to tackle general activation functions including but not limited to four popular choices: ReLU, tanh, sigmoid and arctan. In addition, we facilitate the search for a tighter certified lower bound by adaptively selecting appropriate surrogates for each neuron activation. Experimental results show that CROWN on ReLU networks can notably improve the certified lower bounds compared to the current state-of-the-art algorithm Fast-Lin, while having comparable computational efficiency. Furthermore, CROWN also demonstrates its effectiveness and flexibility on networks with general activation functions, including tanh, sigmoid and arctan.
1 Introduction
The paper frames robustness certification as finding certified lower bounds on minimum adversarial distortion, especially for deep networks and general activation functions. CROWN addresses the limited scope of ReLU-focused methods with adaptive linear or quadratic activation bounds.
- Motivation: Robustness certification seeks to ensure that every point in an ℓp neighborhood of x0 has the same inference outcome.The minimum distance to a misclassified nearby example is the largest possible robustness certificate for x0.
- Motivation: Finding minimum adversarial distortion is NP-complete for ReLU networks, making formal verification computationally demanding even for small networks.The paper specifically identifies Reluplex as suffering from scalability issues.
- Research gap: Generalizing robustness certification beyond piece-wise linear ReLU activations, including tanh and sigmoid, remains largely unexplored.The paper motivates a framework that supports general activation functions.
- Approach: CROWN uses linear or quadratic upper and lower activation bounds and adaptively selects bounds to reduce approximation errors.The framework targets general activation functions that are not necessarily piece-wise linear.
- Reported contributions: Up to 26% improvements in certified lower bounds are reported for CROWN compared with previous work.The paper also reports certification for networks with over 10,000 neurons in about 1 minute on 1 CPU core.
2 Background and Related Work
Prior certification methods include exact solver-based approaches and analytical lower bounds, but they face computational, architectural, or activation-function constraints. The paper distinguishes provable local ℓp-ball certification from empirical and distributional robustness approaches.
- Exact verification: MILP, SMT, and SAT-based methods can find minimum distortion for ReLU networks but are limited to very small networks by NP-completeness.Reluplex may take several hours on a ReLU network with only 5 inputs and 5 outputs.
- Analytical bounds: Operator-norm and Jacobian-based lower bounds do not exploit ReLU structure and can therefore be very loose.Local-Lipschitz approaches introduce additional restrictions, including continuous differentiability and difficulty deriving closed forms beyond two layers.
- Method limitations: Some local-Lipschitz certification methods require continuously differentiable activation functions, excluding ReLU networks.Soft-plus is given as an example of an activation covered by that requirement.
- Scope distinctions: Empirical adversarial training and region-based classification exhibit robustness against several attacks but fall outside provable robustness certification.These approaches are discussed as distinct from the certification problem addressed here.
- Scope distinctions: Wasserstein distributional robustness certification differs from the paper’s local robustness model based on an ℓp ball around an input.The distinction concerns the robustness notion rather than solver scalability.
3 CROWN: A general framework for certifying neural networks
CROWN certifies neural-network robustness by propagating adaptive linear or quadratic activation bounds through networks and then searching for the largest certified distortion bound. The framework covers general activations and supports efficient certification without optimization solvers for general ℓp distortions.
- General framework: CROWN derives explicit network output bounds by replacing each neuron’s activation with linear upper and lower functions and back-propagating equivalent weights and biases.Different neurons may use different slopes, enabling adaptive approximations during bound computation.
- General framework: For inputs in an ℓp ball, CROWN converts the resulting linear output bounds into closed-form global bounds using the dual norm.These bounds provide the quantities used to certify minimum targeted and untargeted adversarial distortion.
- General activations: CROWN accommodates ReLU, tanh, sigmoid, arctan, and other activations by constructing suitable linear upper and lower bounds for each neuron.The bounds can use neuron-specific parameters determined from pre-activation intervals and sign-based neuron partitions.
- Adaptive bounds: Adaptive selection of linear activation bounds generalizes Fast-Lin, which uses identical upper and lower slopes and applies only to ReLU networks.The paper identifies adaptive approximation selection as the main contributor to tighter certified lower bounds.
- Efficiency: CROWN computes analytic output bounds efficiently, with O(m2n3) time complexity for an m-layer ReLU network with n neurons per layer and n outputs.The paper contrasts this polynomial-time complexity with exponential-time SMT and mixed-integer optimization approaches.
- Quadratic extension: Quadratic activation bounds can be added to the framework, extending CROWN beyond linear approximations.This extension is presented as an additional source of flexibility for bounding activation functions.
4 Experiments
Experiments compare CROWN variants with Fast-Lin, Fast-Lip, LP-Full, and Reluplex on MNIST and CIFAR-10 networks. CROWN-Ada achieves stronger certified lower bounds while maintaining practical computational efficiency, and CROWN-general extends certification to several non-piecewise-linear activations.
- Setup: Experiments use MLPs trained on MNIST and CIFAR-10, including pretrained ReLU models and matched test images and attack targets.The ReLU evaluation uses 100 random test images and random attack targets for comparability with prior work.
- Implementation: The implementation uses matrix operations with single-threaded BLAS on an Intel Skylake CPU for comparison across methods.The code is implemented in Python using NumPy and Numba.
- Small networks: Figure 2 compares certified lower bounds, minimum distortion, and computation time for ℓ2 and ℓ∞ distortions across six methods.The right-axis computation time uses a logarithmic scale; CLEVER scores and C&W upper bounds are also shown.
- Small networks: CROWN-Quad on two-layer networks and CROWN-Ada achieve the largest certified lower bounds on small networks.Reluplex and LP-Full are orders of magnitude slower than the other methods.
- Large ReLU networks: CROWN-Ada significantly outperforms Fast-Lin and Fast-Lip on large ReLU networks, with computation time below 2X Fast-Lin and comparable to Fast-Lip.Table 4 reports averages over 100 images after skipping misclassified images, with random attack targets.
- Different activations: CROWN-general certifies non-trivial lower bounds for ReLU, tanh, sigmoid, and arctan networks, with about 20% additional computational overhead versus CROWN-Ada on ReLU networks.The activation-function comparison covers different ℓp norms on large networks.
5 Conclusion
The paper presents CROWN for efficiently computing certified lower bounds on minimum adversarial distortion. Experiments show improved ReLU certification and efficient certification for large networks with multiple activation functions.
- 5 Conclusion: CROWN efficiently computes certified lower bounds of minimum distortion for a given data point and supports general activation functions.The framework uses adaptive bounds to improve robustness certification.
- 5 Conclusion: Experiments show that CROWN outperforms state-of-the-art baselines on ReLU networks.
- 5 Conclusion: CROWN efficiently certifies non-trivial lower bounds for large networks with over 10K neurons and different activation functions.
A Proof of Theorem 3.2
The proof derives output upper and lower bounds by recursively propagating activation-function bounds through the network. The construction separates cases according to weight signs and repeatedly rewrites equivalent weights and biases.
- Upper bound: The derivation selects different bound terms according to whether each associated weight is non-negative or negative.
- Upper bound: The upper-bound proof recursively unwraps activation functions from the output layer toward the input using the right-hand sides of the activation bounds.
- Recursive transformation: After each layer, constant terms are collected and summation orders are swapped to form equivalent weights and biases for the next recursion.
- Recursive transformation: The final upper bound is obtained by iterating the same procedure until the first layer and defining the resulting expression as the network-output bound.
- Boundary conditions: Boundary cases specify coefficient choices at the initial and final recursion layers.
- Lower bound: The lower-bound derivation follows the same recursion but uses the left-hand sides of the activation bounds instead of the right-hand sides.
B Proof of Corollary 3.3
The corollary extends the recursive bound construction to quadratic activation approximations and establishes global bounds over an ℓp neighborhood. The sigmoid illustration shows the corresponding linear-bound construction.
- Global bound: The global-bound argument applies the resulting network bounds to every x in the ℓp ball around x0 and uses dual-norm relations in the final step.
- Sigmoid illustration: The sigmoid illustration depicts linear upper and lower bounds for σ(y) = sigmoid.
- Quadratic approximation: For quadratic approximations, the upper-bound derivation replaces the linear activation bounds with quadratic functions while retaining the same propagation framework.
- Quadratic approximation: Substituting the preceding layer into the quadratic expression separates quadratic, linear, and constant terms of the transformed network representation.
- Quadratic approximation: The quadratic lower bound is obtained analogously by swapping the upper-bound activation functions for their lower-bound counterparts.
E.1 Results on CROWN-Ada
Table 6 compares CROWN-Ada’s certified lower bounds for ReLU networks with several alternative certification and Lipschitz-based methods.
- E.1 Results on CROWN-Ada: Table 6 compares CROWN-Ada with Fast-Lin, Fast-Lip, Op-nrom, Op-norm, LP-full, and Reluplex.LP-full and Reluplex cannot finish within a reasonable amount of time for all reported networks.
- E.1 Results on CROWN-Ada: Op-norm computes each layer’s operator norm, multiplies these norms into a global Lipschitz constant, and uses it to compute a robustness lower bound.For p = 2, the operator norm is the spectral norm.
- E.1 Results on CROWN-Ada: The table reports certified lower-bound comparisons involving CROWN-Ada, Fast-Lin, Fast-Lip, and Lipschitz- or optimization-based baselines.
E.2 Results on CROWN-general
Table 7 compares CROWN-Ada on ReLU networks with CROWN-general on networks using tanh, sigmoid, and arctan activations under multiple norms and targeted attack classes.
- E.2 Results on CROWN-general: Table 7 compares CROWN-Ada on ReLU networks with CROWN-general on tanh, sigmoid, and arctan networks.
- E.2 Results on CROWN-general: CIFAR sigmoid models are excluded because they achieve much worse accuracy than the other networks.
- E.2 Results on CROWN-general: For each norm, robustness is evaluated against runner-up, random, and least-likely targeted attack classes.These classes are defined by the target class’s probability ranking.