The success of Deep Learning and its potential use in many important safetycritical applications has motivated research on formal verification of Neural Network (NN) models. Despite the reputation of learned NN models to behave as black boxes and the theoretical hardness of proving their properties, researchers have been successful in verifying some classes of models by exploiting their piecewise linear structure. Unfortunately, most of these approaches test their algorithms without comparison with other approaches. As a result, the pros and cons of the different algorithms are not well understood. Motivated by the need to accelerate progress in this very important area, we investigate the trade-offs of a number of different approaches based on Mixed Integer Programming, Satisfiability Modulo Theory, as well as a novel method based on the Branch-and-Bound framework. We also propose a new data set of benchmarks, in addition to a collection of previously released testcases that can be used to compare existing methods. Our analysis not only allows a comparison to be made between different strategies, the comparison of results from different solvers also revealed implementation bugs in published methods. We expect that the availability of our benchmark and the analysis of the different approaches will allow researchers to develop and evaluate promising approaches for making progress on this important topic.
The paper compares some recently proposed method for validation of properties
of piece-wise linear neural networks and claims to propose a novel method for
the same. Unfortunately, the proposed "branch and bound method" does not explain
how to implement the "bound" part ("compute lower bound") -- and has been used 
several times in the same application, incl.:
Ruediger Ehlers. Planet. https://github.com/progirep/planet,
Chih-Hong Cheng, Georg Nuhrenberg, and Harald Ruess.  Maximum resilience of artificial neural networks. Automated Technology for Verification and Analysis
Alessio Lomuscio and Lalit Maganti.  An approach to reachability analysis for feed-forward relu neural networks. arXiv:1706.07351
Specifically, the authors say: "In our experiments, we use the result of 
minimising the variable corresponding to the output of the network, subject 
to the constraints of the linear approximation introduced by Ehlers (2017a)"
which sounds a bit like using linear programming relaxations, which is what
the approaches using branch and bound cited above use. If that is the case,
the paper does not have any original contribution. If that is not the case,
the authors may have some contribution to make, but have not made it in this
paper, as it does not explain the lower bound computation other than the one
based on LPs.
Generally, I find a jarring mis-fit between the motivation (deep learning
for driving, presumably involving millions or billions of parameters) and
the actual reach of the methods proposed (hundreds of parameters).
This reach is NOT inherent in integer programming, per se. Modern solvers
routinely solve instances with tens of millions of non-zeros in the constraint
matrix, but require a strong relaxation. The authors may hence consider
improving the LP relaxation, noting that the big-M constraint are notorious
for producing weak relaxations.