  Probabilistic verification of neural networks is concerned with formally
analysing the output distribution of a neural network under a probability
distribution of the inputs. Examples of probabilistic verification include
verifying the demographic parity fairness notion or quantifying the safety of a
neural network. We present a new algorithm for the probabilistic verification
of neural networks based on an algorithm for computing and iteratively refining
lower and upper bounds on probabilities over the outputs of a neural network.
By applying state-of-the-art bound propagation and branch and bound techniques
from non-probabilistic neural network verification, our algorithm significantly
outpaces existing probabilistic verification algorithms, reducing solving times
for various benchmarks from the literature from tens of minutes to tens of
seconds. Furthermore, our algorithm compares favourably even to dedicated
algorithms for restricted subsets of probabilistic verification. We complement
our empirical evaluation with a theoretical analysis, proving that our
algorithm is sound and, under mildly restrictive conditions, also complete when
using a suitable set of heuristics.
