PEREGRiNN: Penalized-Relaxation Greedy Neural Network Verifier
  Neural Networks (NNs) have increasingly apparent safety implications
commensurate with their proliferation in real-world applications: both
unanticipated as well as adversarial misclassifications can result in fatal
outcomes. As a consequence, techniques of formal verification have been
recognized as crucial to the design and deployment of safe NNs. In this paper,
we introduce a new approach to formally verify the most commonly considered
safety specifications for ReLU NNs -- i.e. polytopic specifications on the
input and output of the network. Like some other approaches, ours uses a
relaxed convex program to mitigate the combinatorial complexity of the problem.
However, unique in our approach is the way we use a convex solver not only as a
linear feasibility checker, but also as a means of penalizing the amount of
relaxation allowed in solutions. In particular, we encode each ReLU by means of
the usual linear constraints, and combine this with a convex objective function
that penalizes the discrepancy between the output of each neuron and its
relaxation. This convex function is further structured to force the largest
relaxations to appear closest to the input layer; this provides the further
benefit that the most problematic neurons are conditioned as early as possible,
when conditioning layer by layer. This paradigm can be leveraged to create a
verification algorithm that is not only faster in general than competing
approaches, but is also able to verify considerably more safety properties; we
evaluated PEREGRiNN on a standard MNIST robustness verification suite to
substantiate these claims.
