PaperlayerView exact revision on arXiv

Source-linked AI summary

CNN-Cert: An Efficient Framework for Certifying Robustness of Convolutional Neural Networks

Akhilan Boopathy, Tsui-Wei Weng, Pin-Yu Chen, Sijia Liu, Luca Daniel

arXiv:1811.12395v1stat.MLcs.CRcs.LG

TL;DR

Finding minimum adversarial distortion for ReLU networks is NP-complete, and prior certification methods often focus on fully connected layers. CNN-Cert certifies varied CNN architectures and activation functions by applying linear bounds to network building blocks. The paper reports speedups of up to 17 times over Fast-Lin and 366 times over dual-LP, with similar or better verification bounds.

  • Problem

    Finding minimum adversarial distortion for ReLU networks is NP-complete, while prior certification methods often focus on fully connected layers and may lack architectural or activation-function generality.

    Source: Introduction · p. 1

  • Method

    CNN-Cert applies linear bounding techniques to nonlinear network building blocks and exploits convolution operations to certify diverse CNN architectures and activation functions.

    Source: Introduction · p. 2, General framework · p. 3

  • Results

    CNN-Cert achieves up to 17 times speed-up compared to Fast-Lin and up to 366 times speed-up compared to dual-LP, with similar or even better verification bounds.

    Source: Introduction · p. 2

  • Takeaways & Limitations

    Fast-Lin and CROWN are special cases of CNN-Cert, which supports architectures including residual, pooling, and batch-normalization blocks.

    Source: General framework · p. 5

    The certification setting assumes an ℓp norm-ball threat model and full access to all model parameters.

    Source: Background and Related Work · p. 2

Abstract

from arXiv · show

Verifying robustness of neural network classifiers has attracted great interests and attention due to the success of deep neural networks and their unexpected vulnerability to adversarial perturbations. Although finding minimum adversarial distortion of neural networks (with ReLU activations) has been shown to be an NP-complete problem, obtaining a non-trivial lower bound of minimum distortion as a provable robustness guarantee is possible. However, most previous works only focused on simple fully-connected layers (multilayer perceptrons) and were limited to ReLU activations. This motivates us to propose a general and efficient framework, CNN-Cert, that is capable of certifying robustness on general convolutional neural networks. Our framework is general -- we can handle various architectures including convolutional layers, max-pooling layers, batch normalization layer, residual blocks, as well as general activation functions; our approach is efficient -- by exploiting the special structure of convolutional layers, we achieve up to 17 and 11 times of speed-up compared to the state-of-the-art certification algorithms (e.g. Fast-Lin, CROWN) and 366 times of speed-up compared to the dual-LP approach while our algorithm obtains similar or even better verification bounds. In addition, CNN-Cert generalizes state-of-the-art algorithms e.g. Fast-Lin and CROWN. We demonstrate by extensive experiments that our method outperforms state-of-the-art lower-bound-based certification algorithms in terms of both bound quality and speed.

Introduction

CNN-Cert addresses limits in prior robustness verification by supporting diverse CNN architectures and activation functions while exploiting convolution structure. The paper reports substantial speedups with similar or better verification bounds.

Introduction

  • Prior efficient methods often focus on fully connected networks, while converting convolutions to fully connected layers may sacrifice efficiency.Finding minimum distortion for ReLU networks is NP-complete, motivating non-trivial lower bounds as a scalable alternative.Source: Introduction · p. 1
  • CNN-Cert certifies CNNs with convolution, pooling, batch normalization, residual blocks, and general activation functions.The paper names ReLU, tanh, sigmoid, and arctan as examples, and says other variants can be incorporated.Source: Introduction · p. 2
  • CNN-Cert exploits convolution operations to improve certification efficiency.The introduction points readers to Table 1 for a comparison of verification-based methods, but the supplied caption gives no cell values.Source: Introduction · p. 2, Table 1 · p. 2
  • CNN-Cert achieves up to 17 times speed-up compared to Fast-Lin and up to 366 times speed-up compared to dual-LP, with similar or even better verification bounds.The framework's cost is described as similar to forward propagation.Source: Introduction · p. 2

Background and Related Work

This section contrasts empirical defenses and attack-agnostic verification, then frames CNN-Cert against prior certification methods that often target fully connected networks. It also defines the norm-bounded threat model and the certificate being sought.

Background and Related Work

  • Adaptive attacks have bypassed some defenses under the same threat model, whereas verification certifies robustness against all possible attacks within that model.Adversarial training has shown strong empirical defense performance, and verification has validated robustness improvements from adversarial training.Source: Background and Related Work · p. 2
  • Efficient certificates provide lower bounds on minimum distortion, since finding the minimum for ReLU networks is NP-complete (Katz et al. 2017).Prior methods may be limited to fully connected layers; some analytical bounds are too loose or restricted to one or two hidden layers.Source: Background and Related Work · p. 2
  • Under the ℓp norm-ball threat model with full model access, ρcert is a radius within which no perturbation changes the predicted class.The minimum adversarial distortion ρmin is the smallest perturbation that changes the prediction; ρcert must be smaller than ρmin.Source: Background and Related Work · p. 2

CNN-Cert: A General and Efficient Framework for Robustness Certification

CNN-Cert derives explicit network-output bounds by linear bounding individual nonlinear building blocks, then propagates them to certify robustness under ℓp-bounded perturbations. It covers common CNN components and general activations, and contains Fast-Lin and CROWN as special cases.

CNN-Cert: A General and Efficient Framework for Robustness Certification

  • CNN-Cert handles convolution, max-pooling, batch normalization, residual blocks, and general activations, with Fast-Lin and CROWN as special cases.With the same ReLU bounds, it matches CROWN; for general activations, more accurate linear bounds yield certificate quality improvements of up to 260%.Source: CNN-Cert: A General and Efficient… · p. 3, General framework · p. 5

General framework

  • Linear upper and lower bounds for each building block are back-propagated to derive explicit network-output bounds under ℓp-bounded input perturbations.Bounds for activation and convolution blocks can be applied iteratively; the framework also incorporates residual, pooling, and batch-normalization layers.Source: General framework · pp. 3–4
  • For max-pooling, linear bounds use the input range and pooled index set; average-pooling bounds are averages of the corresponding input bounds.Batch normalization scales and shifts both upper and lower bounds, while residual-block bounds depend on the component layers and their linear-bound parameters.Source: General framework · p. 4
  • Global output bounds over the ℓp input ball support certification: bisection finds the largest radius for which the predicted-class lower bound exceeds each target-class upper bound.Intermediate layer bounds also depend on the perturbation radius and are computed using the same explicit bounding forms.Source: General framework · p. 5
  • CNN-Cert is 2.5–11.4× faster than CROWN while matching its ReLU certificate or improving certificate quality by up to 260% for general activations.Across experiments against Fast-Lin and dual-LP approaches, it maintains similar or better certified bounds, with reported improvement around 8–20%.Source: General framework · p. 5
  • CNN-Cert runs in polynomial time and has cost similar to forward propagation, unlike exact minimum-distortion methods such as Reluplex, which are NP-complete.For a pure CNN, the stated complexity is O(r^2m^6k^4n^3), compared with O(r^6m^2n^3) for the equivalent fully connected network.Source: General framework · p. 5

Experiments

Experiments compare CNN-Cert with lower-bound verification methods across five classes of networks. The results report stronger certified bounds and faster runtimes on pure CNNs, improvements on general CNNs and ResNets, and non-trivial bounds across tested activation functions.

Experimental setup

  • Experiments compare five network classes, evaluating 10 random test images and attack targets; reported averages over 100 images are similar where available.Models are trained for 10 epochs, with hyperparameters tuned for validation accuracy.Source: Experiments · pp. 5, 7

Results (I): pure CNNs with ReLU activation

  • CNN-Cert's certified lower bounds are 8-20% larger than Fast-Lin and Dual-LP, and it runs multiple orders faster than Dual-LP.It is also faster than Fast-Lin, with over an order of magnitude speedup for the smallest network.Source: Table 3 · p. 6, Table 4 · p. 6, Experiments · p. 7

Results (II), (III): general CNNs and ResNet with ReLU activation

  • CNN-Cert improves on Fast-Lin-style ReLU bounds for general CNNs and on Fast-Lin for ResNets; no-pooling LeNet-style bounds exceed pooling-version bounds, while batch normalization yields smaller bounds.The comparisons include general CNNs with pooling and batch normalization and residual networks.Source: Table 5 · p. 6, Experiments · p. 7, Table 6 · p. 7

Results (IV): general CNNs and ResNet with general activations

  • CNN-Cert efficiently finds non-trivial lower bounds for all tested activation functions without significant computational penalty; some 7-layer sigmoid results are omitted for poor test accuracy.Source: Experiments · p. 7, Table 7 · p. 7

Results (V): Small MLP networks

  • On small MNIST MLPs, certified lower-bound methods remain around 2 times from exact Reluplex distortion, while CLEVER and attack methods approach it without guarantees.Reluplex computes minimum adversarial distortion for the small 2-layer network.Source: Experiments · pp. 7–8, Table 8 · p. 7

Conclusion and Future Work

CNN-Cert applies linear bounding techniques to certify robustness across varied CNN architectures and activation functions. Experiments across four CNN classes report tighter non-trivial certified bounds and greater runtime efficiency than other methods.

Appendix (a) Derivation of Act-Conv block: Ar

The appendix derives bounds for convolutional, residual, and pooling blocks. It applies activation bounds within convolution sums, accounts for weight signs, and constructs bounds for pooled maxima.

Act-Conv block

Residual block

Pooling block

(d) Additional experiment results

The appendix captions identify additional certified-bound and runtime results for pure ReLU networks, and bounds and runtimes for general CNNs and ResNets. They also describe a general-activation comparison and note an omitted sigmoid network.

  • Tables 10 and 11 provide additional certified-bound and runtime results, respectively, for pure ReLU networks.Source: Table 10 · p. 15, Table 11 · p. 16
  • Table 12 covers bounds and runtimes for general CNNs and ResNets with general activations, omitting the 7-layer sigmoid network due to poor test accuracy.Source: Table 12 · p. 17
  • Table 13 compares CROWN and CNN-Cert with general activations; its caption attributes CNN-Cert-Ada's better bounds for sigmoid, tanh, and arctan to more accurate activation bounds.Source: Table 13 · p. 17
Loading 1811.12395v1…