# BNN-DP: Robustness Certification of Bayesian Neural Networks via Dynamic Programming

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 38 references that are in the map.
- First posted on arXiv 19 Jun 2023.

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

- [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)
- [Dropout as a Bayesian Approximation: Representing Model Uncertainty in Deep Learning](https://mlsanity.com/paper/1506.02142/) (2015)
- [The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks](https://mlsanity.com/paper/1803.03635/) (2018)
- [Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks](https://mlsanity.com/paper/1702.01135/) (2017)
- [Provable defenses against adversarial examples via the convex outer adversarial polytope](https://mlsanity.com/paper/1711.00851/) (2017)
- [Efficient Neural Network Robustness Certification with General Activation Functions](https://mlsanity.com/paper/1811.00866/) (2018)
- [Wild Patterns: Ten Years After the Rise of Adversarial Machine Learning](https://mlsanity.com/paper/1712.03141/) (2017)
- [Probabilistic Backpropagation for Scalable Learning of Bayesian Neural Networks](https://mlsanity.com/paper/1502.05336/) (2015)
- [Towards Fast Computation of Certified Robustness for ReLU Networks](https://mlsanity.com/paper/1804.09699/) (2018)
- [Algorithms for Verifying Deep Neural Networks](https://mlsanity.com/paper/1903.06758/) (2019)
- [Understanding Measures of Uncertainty for Adversarial Example Detection](https://mlsanity.com/paper/1803.08533/) (2018)
- [Practical Deep Learning with Bayesian Principles](https://mlsanity.com/paper/1906.02506/) (2019)
- [Fast and Scalable Bayesian Deep Learning by Weight-Perturbation in Adam](https://mlsanity.com/paper/1806.04854/) (2018)
- [Noisy Natural Gradient as Variational Inference](https://mlsanity.com/paper/1712.02390/) (2017)
- [Uncertainty-Aware Reinforcement Learning for Collision Avoidance](https://mlsanity.com/paper/1702.01182/) (2017)
- [Robustness of Bayesian Neural Networks to Gradient-Based Attacks](https://mlsanity.com/paper/2002.04359/) (2020)
- [Probabilistic Safety for Bayesian Neural Networks](https://mlsanity.com/paper/2004.10281/) (2020)
- [Statistical Guarantees for the Robustness of Bayesian Neural Networks](https://mlsanity.com/paper/1903.01980/) (2019)
- [Lagrangian Decomposition for Neural Network Verification](https://mlsanity.com/paper/2002.10410/) (2020)
- [Bayesian Inference with Certifiable Adversarial Robustness](https://mlsanity.com/paper/2102.05289/) (2021)
- [Robustness Guarantees for Bayesian Inference with Gaussian Processes](https://mlsanity.com/paper/1809.06452/) (2018)
- [Individual Fairness Guarantees for Neural Networks](https://mlsanity.com/paper/2205.05763/) (2022)
- [Make Sure You're Unsure: A Framework for Verifying Probabilistic Specifications](https://mlsanity.com/paper/2102.09479/) (2021)
- [Infinite Time Horizon Safety of Bayesian Neural Networks](https://mlsanity.com/paper/2111.03165/) (2021)
- [Adversarial Phenomenon in the Eyes of Bayesian Deep Learning](https://mlsanity.com/paper/1711.08244/) (2017)
- [Adversarial Vulnerability Bounds for Gaussian Process Classification](https://mlsanity.com/paper/1909.08864/) (2019)
- [Adversarial Robustness Guarantees for Gaussian Processes](https://mlsanity.com/paper/2104.03180/) (2021)

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

- [Certified Robustness to Data Poisoning in Gradient-Based Training](https://mlsanity.com/paper/2406.05670/) (2024)
- [Adversarial Robustness Certification for Bayesian Neural Networks](https://mlsanity.com/paper/2306.13614/) (2023)
- [Tight Verification of Probabilistic Robustness in Bayesian Neural Networks](https://mlsanity.com/paper/2401.11627/) (2024)
- [Solving Probabilistic Verification Problems of Neural Networks using Branch and Bound](https://mlsanity.com/paper/2405.17556/) (2024)
- [Finite Neural Networks as Mixtures of Gaussian Processes: From Provable Error Bounds to Prior Selection](https://mlsanity.com/paper/2407.18707/) (2024)
- [Risk-Averse Certification of Bayesian Neural Networks](https://mlsanity.com/paper/2411.19729/) (2024)
- [Clustered Randomized Smoothing for Stochastic Prediction Functions](https://mlsanity.com/paper/2608.12037/) (2026)
- [Certified Uncertainty Propagation in One-Shot Federated Bayesian Models via Posterior Event Transport](https://mlsanity.com/paper/2609.16373/) (2026)

## Abstract (arXiv)

In this paper, we introduce BNN-DP, an efficient algorithmic framework for analysis of adversarial robustness of Bayesian Neural Networks (BNNs). Given a compact set of input points Tsubset ℝn, BNN-DP computes lower and upper bounds on the BNN's predictions for all the points in T. The framework is based on an interpretation of BNNs as stochastic dynamical systems, which enables the use of Dynamic Programming (DP) algorithms to bound the prediction range along the layers of the network. Specifically, the method uses bound propagation techniques and convex relaxations to derive a backward recursion procedure to over-approximate the prediction range of the BNN with piecewise affine functions. The algorithm is general and can handle both regression and classification tasks. On a set of experiments on various regression and classification tasks and BNN architectures, we show that BNN-DP outperforms state-of-the-art methods by up to four orders of magnitude in both tightness of the bounds and computational efficiency.