  Despite having high accuracy, neural nets have been shown to be susceptible
to adversarial examples, where a small perturbation to an input can cause it to
become mislabeled. We propose metrics for measuring the robustness of a neural
net and devise a novel algorithm for approximating these metrics based on an
encoding of robustness as a linear program. We show how our metrics can be used
to evaluate the robustness of deep neural nets with experiments on the MNIST
and CIFAR-10 datasets. Our algorithm generates more informative estimates of
robustness metrics compared to estimates based on existing algorithms.
Furthermore, we show how existing approaches to improving robustness "overfit"
to adversarial examples generated using a specific algorithm. Finally, we show
that our techniques can be used to additionally improve neural net robustness
both according to the metrics that we propose, but also according to previously
proposed metrics.
