Global Robustness Evaluation of Deep Neural Networks with Provable Guarantees for the L₀ Norm

2018/04/16 by Wenjie Ruan, Min Wu, Ruan, Wenjie +9 · 1 citation
Computer Science · Mathematics · #Advanced Neural Network Applications #Adversarial Robustness in Machine Learning #Computer Vision and Pattern Recognition (cs.CV) #Cryptography and Security (cs.CR) #Domain Adaptation and Few-Shot Learning #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #cs.CR #cs.CV #cs.LG #stat.ML

paper · pdf · doi:10.48550/arxiv.1804.05805

42 Pages, Github: https://github.com/TrustAI/L0-TRE

openalex publication_date 2018/04/16 · arxiv created 2018/11/20 · arxiv updated 2018/11/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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₀ 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 anytime, i.e., it returns intermediate bounds and robustness estimates that are gradually, but strictly, improved as the computation proceeds; 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 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₀ 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.

Citations

• Very Deep Convolutional Networks for Large-Scale Image Recognition
• DeepTest: Automated Testing of Deep-Neural-Network-driven Autonomous Cars
• Output Range Analysis for Deep Neural Networks
• Provably Minimally-Distorted Adversarial Examples

Cited by

• A Survey of Safety and Trustworthiness of Deep Neural Networks: Verification, Testing, Adversarial Attack and Defence, and Interpretability

Related

• Globally-Robust Neural Networks
• Verification of Neural Networks' Global Robustness
• Global Robustness Verification Networks
• ε-weakened Robustness of Deep Neural Networks
• Certifying Global Robustness for Deep Neural Networks