# Verification of Neural Networks' Global Robustness

arXiv: https://arxiv.org/abs/2402.19322 · HTML: https://mlsanity.com/paper/2402.19322/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 58 references that are in the map.
- First posted on arXiv 29 Feb 2024.

## Builds on (most cited first, 30 of 33)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Towards Evaluating the Robustness of Neural Networks](https://mlsanity.com/paper/1608.04644/) (2016)
- [Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks](https://mlsanity.com/paper/1702.01135/) (2017)
- [ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Models](https://mlsanity.com/paper/1708.03999/) (2017)
- [Formal Verification of Piece-Wise Linear Feed-Forward Neural Networks](https://mlsanity.com/paper/1705.01320/) (2017)
- [Beta-CROWN: Efficient Bound Propagation with Per-neuron Split Constraints for Complete and Incomplete Neural Network Robustness Verification](https://mlsanity.com/paper/2103.06624/) (2021)
- [Efficient Formal Safety Analysis of Neural Networks](https://mlsanity.com/paper/1809.08098/) (2018)
- [EAD: Elastic-Net Attacks to Deep Neural Networks via Adversarial Examples](https://mlsanity.com/paper/1709.04114/) (2017)
- [DPatch: An Adversarial Patch Attack on Object Detectors](https://mlsanity.com/paper/1806.02299/) (2018)
- [AutoZOOM: Autoencoder-based Zeroth Order Optimization Method for Attacking Black-box Neural Networks](https://mlsanity.com/paper/1805.11770/) (2018)
- [Globally-Robust Neural Networks](https://mlsanity.com/paper/2102.08452/) (2021)
- [Measuring Neural Net Robustness with Constraints](https://mlsanity.com/paper/1605.07262/) (2016)
- [Unrestricted Adversarial Examples via Semantic Manipulation](https://mlsanity.com/paper/1904.06347/) (2019)
- [Exploring the Landscape of Spatial Robustness](https://mlsanity.com/paper/1712.02779/) (2017)
- [Defending Against Physically Realizable Attacks on Image Classification](https://mlsanity.com/paper/1909.09552/) (2019)
- [Understanding Adversarial Examples from the Mutual Influence of Images and Perturbations](https://mlsanity.com/paper/2007.06189/) (2020)
- [Rethinking Lipschitz Neural Networks and Certified Robustness: A Boolean Function Perspective](https://mlsanity.com/paper/2210.01787/) (2022)
- [Optimization and Abstraction: A Synergistic Approach for Analyzing Neural Network Robustness](https://mlsanity.com/paper/1904.09959/) (2019)
- [On the Certified Robustness for Ensemble Models and Beyond](https://mlsanity.com/paper/2107.10873/) (2021)
- [Robustness of Neural Networks: A Probabilistic and Practical Approach](https://mlsanity.com/paper/1902.05983/) (2019)
- [Unravelling Robustness of Deep Learning based Face Recognition Against Adversarial Attacks](https://mlsanity.com/paper/1803.00401/) (2018)
- [On the Decision Boundaries of Neural Networks: A Tropical Geometry Perspective](https://mlsanity.com/paper/2002.08838/) (2020)
- [Adversarial Robustness with Non-uniform Perturbations](https://mlsanity.com/paper/2102.12002/) (2021)
- [Efficient Global Robustness Certification of Neural Networks via Interleaving Twin-Network Encoding](https://mlsanity.com/paper/2203.14141/) (2022)
- [Verification of Non-Linear Specifications for Neural Networks](https://mlsanity.com/paper/1902.09592/) (2019)
- [Learning Security Classifiers with Verified Global Robustness Properties](https://mlsanity.com/paper/2105.11363/) (2021)

## Built on by (most cited first, 10 of 10)

- [Logic Gate Neural Networks are Good for Verification](https://mlsanity.com/paper/2505.19932/) (2025)
- [A Survey of Neural Network Robustness Assessment in Image Recognition](https://mlsanity.com/paper/2404.08285/) (2024)
- [Monitoring Robustness and Individual Fairness](https://mlsanity.com/paper/2506.00496/) (2025)
- [VeriFlow: Modeling Distributions for Neural Network Verification](https://mlsanity.com/paper/2406.14265/) (2024)
- [A Formally Verified Robustness Certifier for Neural Networks (Extended Version)](https://mlsanity.com/paper/2505.06958/) (2025)
- [Mini-Batch Robustness Verification of Deep Neural Networks](https://mlsanity.com/paper/2508.15454/) (2025)
- [VNN-LIB 2.0: Rigorous Foundations for Neural Network Verification](https://mlsanity.com/paper/2605.07451/) (2026)
- [TestifAI: Tomography-Based Testing for Deep Learning Systems](https://mlsanity.com/paper/2608.18900/) (2026)
- [Talking with Verifiers: Automatic Specification Generation for Neural Network Verification](https://mlsanity.com/paper/2603.02235/) (2026)
- [Local Neighborhood Instability in Parametric Projections: Quantitative and Visual Analysis](https://mlsanity.com/paper/2604.21617/) (2026)

## Abstract (arXiv)

Neural networks are successful in various applications but are also susceptible to adversarial attacks. To show the safety of network classifiers, many verifiers have been introduced to reason about the local robustness of a given input to a given perturbation. While successful, local robustness cannot generalize to unseen inputs. Several works analyze global robustness properties, however, neither can provide a precise guarantee about the cases where a network classifier does not change its classification. In this work, we propose a new global robustness property for classifiers aiming at finding the minimal globally robust bound, which naturally extends the popular local robustness property for classifiers. We introduce VHAGaR, an anytime verifier for computing this bound. VHAGaR relies on three main ideas: encoding the problem as a mixed-integer programming and pruning the search space by identifying dependencies stemming from the perturbation or the network's computation and generalizing adversarial attacks to unknown inputs. We evaluate VHAGaR on several datasets and classifiers and show that, given a three hour timeout, the average gap between the lower and upper bound on the minimal globally robust bound computed by VHAGaR is 1.9, while the gap of an existing global robustness verifier is 154.7. Moreover, VHAGaR is 130.6x faster than this verifier. Our results further indicate that leveraging dependencies and adversarial attacks makes VHAGaR 78.6x faster.