Branch and Bound for Piecewise Linear Neural Network Verification
  The success of Deep Learning and its potential use in many safety-critical
applications has motivated research on formal verification of Neural Network
(NN) models. In this context, verification involves proving or disproving that
an NN model satisfies certain input-output properties. Despite the reputation
of learned NN models as black boxes, and the theoretical hardness of proving
useful properties about them, researchers have been successful in verifying
some classes of models by exploiting their piecewise linear structure and
taking insights from formal methods such as Satisifiability Modulo Theory.
However, these methods are still far from scaling to realistic neural networks.
To facilitate progress on this crucial area, we exploit the Mixed Integer
Linear Programming (MIP) formulation of verification to propose a family of
algorithms based on Branch-and-Bound (BaB). We show that our family contains
previous verification methods as special cases. With the help of the BaB
framework, we make three key contributions. Firstly, we identify new methods
that combine the strengths of multiple existing approaches, accomplishing
significant performance improvements over previous state of the art. Secondly,
we introduce an effective branching strategy on ReLU non-linearities. This
branching strategy allows us to efficiently and successfully deal with high
input dimensional problems with convolutional network architecture, on which
previous methods fail frequently. Finally, we propose comprehensive test data
sets and benchmarks which includes a collection of previously released
testcases. We use the data sets to conduct a thorough experimental comparison
of existing and new algorithms and to provide an inclusive analysis of the
factors impacting the hardness of verification problems.
