# Enumerating Safe Regions in Deep Neural Networks with Provable Probabilistic Guarantees

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 30 references that are in the map.
- First posted on arXiv 18 Aug 2023.

## Builds on (most cited first, 19 of 19)

- [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)
- [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)
- [An Introduction to Convolutional Neural Networks](https://mlsanity.com/paper/1511.08458/) (2015)
- [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)
- [Algorithms for Verifying Deep Neural Networks](https://mlsanity.com/paper/1903.06758/) (2019)
- [Formal Security Analysis of Neural Networks using Symbolic Intervals](https://mlsanity.com/paper/1804.10829/) (2018)
- [Efficient Formal Safety Analysis of Neural Networks](https://mlsanity.com/paper/1809.08098/) (2018)
- [General Cutting Planes for Bound-Propagation-Based Neural Network Verification](https://mlsanity.com/paper/2208.05740/) (2022)
- [The Second International Verification of Neural Networks Competition (VNN-COMP 2021): Summary and Results](https://mlsanity.com/paper/2109.00498/) (2021)
- [Quantitative Verification of Neural Networks And its Security Applications](https://mlsanity.com/paper/1906.10395/) (2019)
- [Verifying Learning-Based Robotic Navigation Systems](https://mlsanity.com/paper/2205.13536/) (2022)
- [Neural Network Repair with Reachability Analysis](https://mlsanity.com/paper/2108.04214/) (2021)
- [The #DNN-Verification Problem: Counting Unsafe Inputs for Deep Neural Networks](https://mlsanity.com/paper/2301.07068/) (2023)
- [Curriculum Learning for Safe Mapless Navigation](https://mlsanity.com/paper/2112.12490/) (2021)
- [Safe Deep Reinforcement Learning by Verifying Task-Level Properties](https://mlsanity.com/paper/2302.10030/) (2023)
- [Constrained Reinforcement Learning and Formal Verification for Safe Colonoscopy Navigation](https://mlsanity.com/paper/2303.03207/) (2023)
- [Online Safety Property Collection and Refinement for Safe Deep Reinforcement Learning in Mapless Navigation](https://mlsanity.com/paper/2302.06695/) (2023)

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

- [Verification-Guided Shielding for Deep Reinforcement Learning](https://mlsanity.com/paper/2406.06507/) (2024)
- [Analyzing Adversarial Inputs in Deep Reinforcement Learning](https://mlsanity.com/paper/2402.05284/) (2024)
- [ModelVerification.jl: a Comprehensive Toolbox for Formally Verifying Deep Neural Networks](https://mlsanity.com/paper/2407.01639/) (2024)
- [Rigorous Probabilistic Guarantees for Robust Counterfactual Explanations](https://mlsanity.com/paper/2407.07482/) (2024)
- [Improving Policy Optimization via varepsilon-Retrain](https://mlsanity.com/paper/2406.08315/) (2024)
- [Solving Probabilistic Verification Problems of Neural Networks using Branch and Bound](https://mlsanity.com/paper/2405.17556/) (2024)
- [Advancing Neural Network Verification through Hierarchical Safety Abstract Interpretation](https://mlsanity.com/paper/2505.05235/) (2025)
- [Designing Control Barrier Function via Probabilistic Enumeration for Safe Reinforcement Learning Navigation](https://mlsanity.com/paper/2504.21643/) (2025)
- [Probabilistic Robustness Analysis in High Dimensional Space: Application to Semantic Segmentation Network](https://mlsanity.com/paper/2509.11838/) (2025)
- [On the Probabilistic Learnability of Compact Neural Network Preimage Bounds](https://mlsanity.com/paper/2511.11656/) (2025)
- [Inductive Learning of Robot Task Knowledge from Raw Data and Online Expert Feedback](https://mlsanity.com/paper/2501.07507/) (2025)
- [Probabilistically Tightened Linear Relaxation-based Perturbation Analysis for Neural Network Verification](https://mlsanity.com/paper/2507.05405/) (2025)
- [Scaling #DNN-Verification Tools with Efficient Bound Propagation and Parallel Computing](https://mlsanity.com/paper/2312.05890/) (2023)
- [LEVIS: Large Exact Verifiable Input Spaces for Neural Networks](https://mlsanity.com/paper/2408.08824/) (2024)
- [Formal Verification of Variational Quantum Circuits](https://mlsanity.com/paper/2507.10635/) (2025)
- [BaB-prob: Branch and Bound with Preactivation Splitting for Probabilistic Verification of Neural Networks](https://mlsanity.com/paper/2509.25647/) (2025)
- [Probabilistic Verification of Recurrent Neural Networks for Single and Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2605.14758/) (2026)
- [Verifiable Foundation Models for Robot Safety](https://mlsanity.com/paper/2606.23754/) (2026)
- [A Survey on the Verification of Reinforcement Learning Policies](https://mlsanity.com/paper/2607.16210/) (2026)

## Abstract (arXiv)

Identifying safe areas is a key point to guarantee trust for systems that are based on Deep Neural Networks (DNNs). To this end, we introduce the AllDNN-Verification problem: given a safety property and a DNN, enumerate the set of all the regions of the property input domain which are safe, i.e., where the property does hold. Due to the #P-hardness of the problem, we propose an efficient approximation method called epsilon-ProVe. Our approach exploits a controllable underestimation of the output reachable sets obtained via statistical prediction of tolerance limits, and can provide a tight (with provable probabilistic guarantees) lower estimate of the safe areas. Our empirical evaluation on different standard benchmarks shows the scalability and effectiveness of our method, offering valuable insights for this new type of verification of DNNs.