# Evaluating Robustness of Neural Networks with Mixed Integer Programming

arXiv: https://arxiv.org/abs/1711.07356 · HTML: https://mlsanity.com/paper/1711.07356/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Nov 2017.

## Built on by (most cited first, 14 of 14)

- [Globally-Robust Neural Networks](https://mlsanity.com/paper/2102.08452/) (2021)
- [Orthogonalizing Convolutional Layers with the Cayley Transform](https://mlsanity.com/paper/2104.07167/) (2021)
- [Don't Lie to Me! Robust and Efficient Explainability with Verified Perturbation Analysis](https://mlsanity.com/paper/2202.07728/) (2022)
- [Efficient Certified Defenses Against Patch Attacks on Image Classifiers](https://mlsanity.com/paper/2102.04154/) (2021)
- [Block-Recurrent Dynamics in Vision Transformers](https://mlsanity.com/paper/2512.19941/) (2025)
- [Abstraction and Refinement: Towards Scalable and Exact Verification of Neural Networks](https://mlsanity.com/paper/2207.00759/) (2022)
- [Fast Training of Provably Robust Neural Networks by SingleProp](https://mlsanity.com/paper/2102.01208/) (2021)
- [FETA: Fairness Enforced Verifying, Training, and Predicting Algorithms for Neural Networks](https://mlsanity.com/paper/2206.00553/) (2022)
- [Prediction without Preclusion: Recourse Verification with Reachable Sets](https://mlsanity.com/paper/2308.12820/) (2023)
- [Beyond Benchmarks: On The False Promise of AI Regulation](https://mlsanity.com/paper/2501.15693/) (2025)
- [Provably Adversarially Robust Nearest Prototype Classifiers](https://mlsanity.com/paper/2207.07208/) (2022)
- [Verification of Neural Network Control Systems in Continuous Time](https://mlsanity.com/paper/2406.00157/) (2024)
- [Sparse Polynomial Optimization: Theory and Practice](https://mlsanity.com/paper/2208.11158/) (2022)
- [On the tightness of linear relaxation based robustness certification methods](https://mlsanity.com/paper/2210.00178/) (2022)

## Abstract (arXiv)

Neural networks have demonstrated considerable success on a wide variety of real-world problems. However, networks trained only to optimize for training accuracy can often be fooled by adversarial examples - slightly perturbed inputs that are misclassified with high confidence. Verification of networks enables us to gauge their vulnerability to such adversarial examples. We formulate verification of piecewise-linear neural networks as a mixed integer program. On a representative task of finding minimum adversarial distortions, our verifier is two to three orders of magnitude quicker than the state-of-the-art. We achieve this computational speedup via tight formulations for non-linearities, as well as a novel presolve algorithm that makes full use of all information available. The computational speedup allows us to verify properties on convolutional networks with an order of magnitude more ReLUs than networks previously verified by any complete verifier. In particular, we determine for the first time the exact adversarial accuracy of an MNIST classifier to perturbations with bounded l_∞ norm ε=0.1: for this classifier, we find an adversarial example for 4.38% of samples, and a certificate of robustness (to perturbations with bounded norm) for the remainder. Across all robust training procedures and network architectures considered, we are able to certify more samples than the state-of-the-art and find more adversarial examples than a strong first-order attack.