# Combinatorial Attacks on Binarized Neural Networks

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Oct 2018.

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

- [Advances in adversarial attacks and defenses in computer vision: A survey](https://mlsanity.com/paper/2108.00401/) (2021)
- [Learning Optimal Prescriptive Trees from Observational Data](https://mlsanity.com/paper/2108.13628/) (2021)
- [Modeling Design and Control Problems Involving Neural Network Surrogates](https://mlsanity.com/paper/2111.10489/) (2021)
- [Computational Tradeoffs of Optimization-Based Bound Tightening in ReLU Networks](https://mlsanity.com/paper/2312.16699/) (2023)
- [Efficient and Robust Mixed-Integer Optimization Methods for Training Binarized Deep Neural Networks](https://mlsanity.com/paper/2110.11382/) (2021)
- [Defensive Tensorization](https://mlsanity.com/paper/2110.13859/) (2021)
- [Multi-Objective Linear Ensembles for Robust and Sparse Training of Few-Bit Neural Networks](https://mlsanity.com/paper/2212.03659/) (2022)
- [Verifying Properties of Binary Neural Networks Using Sparse Polynomial Optimization](https://mlsanity.com/paper/2405.17049/) (2024)
- [ARBiBench: Benchmarking Adversarial Robustness of Binarized Neural Networks](https://mlsanity.com/paper/2312.13575/) (2023)
- [Tightening convex relaxations of trained neural networks: a unified approach for convex and S-shaped activations](https://mlsanity.com/paper/2410.23362/) (2024)
- [On Integer Programming for the Binarized Neural Network Verification Problem](https://mlsanity.com/paper/2510.01525/) (2025)

## Abstract (arXiv)

Binarized Neural Networks (BNNs) have recently attracted significant interest due to their computational efficiency. Concurrently, it has been shown that neural networks may be overly sensitive to "attacks" - tiny adversarial changes in the input - which may be detrimental to their use in safety-critical domains. Designing attack algorithms that effectively fool trained models is a key step towards learning robust neural networks. The discrete, non-differentiable nature of BNNs, which distinguishes them from their full-precision counterparts, poses a challenge to gradient-based attacks. In this work, we study the problem of attacking a BNN through the lens of combinatorial and integer optimization. We propose a Mixed Integer Linear Programming (MILP) formulation of the problem. While exact and flexible, the MILP quickly becomes intractable as the network and perturbation space grow. To address this issue, we propose IProp, a decomposition-based algorithm that solves a sequence of much smaller MILP problems. Experimentally, we evaluate both proposed methods against the standard gradient-based attack (FGSM) on MNIST and Fashion-MNIST, and show that IProp performs favorably compared to FGSM, while scaling beyond the limits of the MILP.