Global Robustness Evaluation of Deep Neural Networks with Provable Guarantees for L0 Norm

Wenjie Ruan, Min Wu, Youcheng Sun, Xiaowei Huang, Daniel Kroening, Marta KwiatkowskaarXiv 2018 · arXiv

Abstract

Deep Neural Networks (DNNs) are susceptible to adversarial perturbations, where minor input modifications lead to incorrect classifications. While heuristic attacks and formal verification methods exist, they often struggle with the non-differentiable $L_0$ norm, which counts the number of altered pixels. This paper presents L0-TRE, a novel evaluation framework that provides provable lower and upper bounds on $L_0$ robustness. By leveraging GPU-accelerated tensor operations and an "anytime" algorithmic structure, L0-TRE bridges the gap between fast heuristic methods and slow formal solvers, offering significant speedups and tighter robustness guarantees across standard benchmarks including MNIST, CIFAR-10, and ImageNet.

1. Introduction

The vulnerability of Deep Neural Networks to adversarial examples poses significant risks in safety-critical applications such as autonomous driving and medical imaging. Robustness evaluation typically falls into two categories: heuristic attacks, which find adversarial examples quickly but lack guarantees, and formal verification, which provides absolute proofs but suffers from poor scalability due to state-space explosion.

This research focuses specifically on the $L_0$ norm, a metric that measures the number of modified pixels regardless of the magnitude of change. The $L_0$ norm is particularly challenging because it is non-differentiable, rendering standard gradient-based attacks ineffective. Furthermore, computing the exact maximum safe radius under the $L_0$ norm is an NP-hard problem. This paper introduces a scalable, tensor-based approach to provide anytime provable guarantees for $L_0$ robustness.

2. Methodology: The L0-TRE Framework

To address the computational complexity of $L_0$ verification, the authors propose L0-TRE, characterized by three core pillars:

2.1 Anytime Algorithm

Unlike traditional verifiers that require completion to provide a result, L0-TRE is an "anytime" algorithm. It continuously computes and tightens two values: a lower bound (the radius within which the network is guaranteed to be safe) and an upper bound (the radius at which an adversarial example is known to exist). This allows practitioners to stop the process at any point and receive a mathematically bounded estimate of robustness, which eventually converges to the exact value given sufficient time.

2.2 Tensor-based Parallelization

Traditional verification tools often rely on CPU-bound constraint solvers. L0-TRE reframes the non-convex optimization problem of finding adversarial perturbations into multi-dimensional tensor operations. This transition allows the framework to exploit the massive parallel processing power of modern GPUs, evaluating thousands of input subspaces simultaneously rather than sequentially.

To ensure the mathematical soundness of the lower bounds, the framework employs a grid search technique. By utilizing the network's Lipschitz constant, the algorithm can guarantee that it has identified the global minimum sensitivity within a specific subspace, preventing the "false sense of security" often provided by heuristic-only methods.

3. Experimental Evaluation

The effectiveness of L0-TRE was evaluated using a diverse set of computer vision benchmarks:

  • MNIST & CIFAR-10: Used for measuring convergence speed and comparing against state-of-the-art attack and verification tools.
  • ImageNet: Used to demonstrate scalability on large-scale architectures, including AlexNet, VGG-16/19, and ResNet-50/101.

4. Key Results and Insights

4.1 Computational Efficiency

The shift to tensor-based GPU execution yielded dramatic performance improvements. L0-TRE demonstrated speeds 38x faster on MNIST and 93x faster on CIFAR-10 compared to CPU-based execution. When compared to the DLV verification tool, L0-TRE was over 1000x faster, highlighting the advantages of parallelized tensor operations over traditional solvers.

4.2 Robustness and Attack Performance

When utilized as an adversarial attacker (via its upper-bound logic), L0-TRE outperformed existing state-of-the-art methods. On CIFAR-10, it successfully identified adversarial examples by modifying an average of only 2.62 pixels. Furthermore, the tool proved highly effective for test case generation, achieving ~99% neuron coverage on MNIST and CIFAR-10, significantly higher than the 80-83% achieved by tools like DeepXplore.

4.3 Architecture and Robustness

The study revealed that higher classification accuracy does not inherently imply higher robustness. In fact, deeper architectures or those with excessive convolutional layers sometimes exhibited lower $L_0$ robustness. Conversely, the inclusion of batch-normalization layers was found to generally improve the model's resilience against $L_0$ perturbations.

5. Conclusion

L0-TRE provides a practical and mathematically rigorous framework for evaluating the $L_0$ robustness of deep neural networks. By combining anytime convergence with GPU-accelerated tensor operations, it offers a scalable solution for verifying large-scale models. While the NP-hard nature of the problem remains a challenge for absolute convergence on massive networks, the ability to provide tightening provable bounds represents a significant step forward for safety-critical AI deployment. Future work will explore extending these tensor-based bounding techniques to continuous norms such as $L_2$ and $L_\infty$.

Summary updated

Abstract

Deployment of deep neural networks (DNNs) in safety- or security-critical systems requires provable guarantees on their correct behaviour. A common requirement is robustness to adversarial perturbations in a neighbourhood around an input. In this paper we focus on the $L_0$ norm and aim to compute, for a trained DNN and an input, the maximal radius of a safe norm ball around the input within which there are no adversarial examples. Then we define global robustness as an expectation of the maximal safe radius over a test data set. We first show that the problem is NP-hard, and then propose an approximate approach to iteratively compute lower and upper bounds on the network's robustness. The approach is \emph{anytime}, i.e., it returns intermediate bounds and robustness estimates that are gradually, but strictly, improved as the computation proceeds; \emph{tensor-based}, i.e., the computation is conducted over a set of inputs simultaneously, instead of one by one, to enable efficient GPU computation; and has \emph{provable guarantees}, i.e., both the bounds and the robustness estimates can converge to their optimal values. Finally, we demonstrate the utility of the proposed approach in practice to compute tight bounds by applying and adapting the anytime algorithm to a set of challenging problems, including global robustness evaluation, competitive $L_0$ attacks, test case generation for DNNs, and local robustness evaluation on large-scale ImageNet DNNs. We release the code of all case studies via GitHub.
BibTeX
@misc{ruan2018global,
  author = {Wenjie Ruan and Min Wu and Youcheng Sun and Xiaowei Huang and Daniel Kroening and Marta Kwiatkowska},
  title = {{Global Robustness Evaluation of Deep Neural Networks with Provable Guarantees for L0 Norm}},
  year = {2018},
  eprint = {1804.05805},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1804.05805},
}
Figure