Exact Certification of Data-Poisoning Attacks Using Mixed-Integer Programming
Preprint
Abstract
This work introduces a verification framework that provides both sound and complete guarantees for data poisoning attacks during neural network training. We formulate adversarial data manipulation, model training, and test-time evaluation in a single mixed-integer quadratic programming (MIQCP) problem. Finding the global optimum of the proposed formulation provably yields worst-case poisoning attacks, while simultaneously bounding the effectiveness of all possible attacks on the given training pipeline. Our framework encodes both the gradient-based training dynamics and model evaluation at test time, enabling the first exact certification of training-time robustness. Experimental evaluation on small models confirms that our approach delivers a complete characterization of robustness against data poisoning.Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- When Deep Learning Meets Polyhedral Theory: A SurveyINFORMS Journal on Computing, 2026
- A Comprehensive Survey on Poisoning Attacks and Countermeasures in Machine LearningACM Computing Surveys, 2022
- Strong Mixed-Integer Programming Formulations for Trained Neural Networks2019
- An abstract domain for certifying neural networksProceedings of the ACM on Programming Languages, 2019
- Deep neural networks and mixed integer linear optimizationConstraints, 2018
- Fake Co-visitation Injection Attacks to Recommender Systems2017
- Three enhancements for optimization-based bound tighteningJournal of Global Optimization, 2016
- The Species Problem in IrisAnnals of the Missouri Botanical Garden, 1936