# The Hammer and the Nut: Is Bilevel Optimization Really Needed to Poison Linear Classifiers?

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Placed in Backdoor and data poisoning attacks, one of 12 directions in LLM safety and security.
- Builds on 24 of its 33 references that are in the map.
- First posted on arXiv 23 Mar 2021.

## Placed in

- LLM safety and security / [Backdoor and data poisoning attacks](https://mlsanity.com/safety/backdoor-and-data-poisoning-attacks/)

## Builds on (most cited first, 24 of 24)

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Towards Evaluating the Robustness of Neural Networks](https://mlsanity.com/paper/1608.04644/) (2016)
- [Understanding Black-box Predictions via Influence Functions](https://mlsanity.com/paper/1703.04730/) (2017)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Targeted Backdoor Attacks on Deep Learning Systems Using Data Poisoning](https://mlsanity.com/paper/1712.05526/) (2017)
- [Evasion Attacks against Machine Learning at Test Time](https://mlsanity.com/paper/1708.06131/) (2017)
- [Improving Transferability of Adversarial Examples with Input Diversity](https://mlsanity.com/paper/1803.06978/) (2018)
- [One pixel attack for fooling deep neural networks](https://mlsanity.com/paper/1710.08864/) (2017)
- [Delving into Transferable Adversarial Examples and Black-box Attacks](https://mlsanity.com/paper/1611.02770/) (2016)
- [Poison Frogs! Targeted Clean-Label Poisoning Attacks on Neural Networks](https://mlsanity.com/paper/1804.00792/) (2018)
- [Wild Patterns: Ten Years After the Rise of Adversarial Machine Learning](https://mlsanity.com/paper/1712.03141/) (2017)
- [Towards Poisoning of Deep Learning Algorithms with Back-gradient Optimization](https://mlsanity.com/paper/1708.08689/) (2017)
- [Witches' Brew: Industrial Scale Data Poisoning via Gradient Matching](https://mlsanity.com/paper/2009.02276/) (2020)
- [Transferable Clean-Label Poisoning Attacks on Deep Neural Nets](https://mlsanity.com/paper/1905.05897/) (2019)
- [Adversarial Machine Learning -- Industry Perspectives](https://mlsanity.com/paper/2002.05646/) (2020)
- [Subpopulation Data Poisoning Attacks](https://mlsanity.com/paper/2006.14026/) (2020)
- [Functionality-preserving Black-box Optimization of Adversarial Windows Malware](https://mlsanity.com/paper/2003.13526/) (2020)
- [Generative Poisoning Attack Method Against Neural Networks](https://mlsanity.com/paper/1703.01340/) (2017)
- [On Defending Against Label Flipping Attacks on Malware Detection Systems](https://mlsanity.com/paper/1908.04473/) (2019)
- [Is Data Clustering in Adversarial Settings Secure?](https://mlsanity.com/paper/1811.09982/) (2018)
- [A black-box adversarial attack for poisoning clustering](https://mlsanity.com/paper/2009.05474/) (2020)
- [Poisoning Behavioral Malware Clustering](https://mlsanity.com/paper/1811.09985/) (2018)
- [Attack Strength vs. Detectability Dilemma in Adversarial Machine Learning](https://mlsanity.com/paper/1802.07295/) (2018)

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

- [Wild Patterns Reloaded: A Survey of Machine Learning Security against Training Data Poisoning](https://mlsanity.com/paper/2205.01992/) (2022)
- [Energy-Latency Attacks via Sponge Poisoning](https://mlsanity.com/paper/2203.08147/) (2022)
- [Minimizing Energy Consumption of Deep Learning Models by Energy-Aware Training](https://mlsanity.com/paper/2307.00368/) (2023)
- [What Distributions are Robust to Indiscriminate Poisoning Attacks for Linear Learners?](https://mlsanity.com/paper/2307.01073/) (2023)
- [Hardening RGB-D Object Recognition Systems against Adversarial Patch Attacks](https://mlsanity.com/paper/2309.07106/) (2023)
- [Resource Consumption Threats in Large Language Models](https://mlsanity.com/paper/2603.16068/) (2026)
- [Empirical Perturbation Analysis of Linear System Solvers from a Data Poisoning Perspective](https://mlsanity.com/paper/2410.00878/) (2024)
- [Defending Against Beta Poisoning Attacks in Machine Learning Models](https://mlsanity.com/paper/2508.01276/) (2025)
- [On Robustness of Linear Classifiers to Targeted Data Poisoning](https://mlsanity.com/paper/2511.12722/) (2025)

## Abstract (arXiv)

One of the most concerning threats for modern AI systems is data poisoning, where the attacker injects maliciously crafted training data to corrupt the system's behavior at test time. Availability poisoning is a particularly worrisome subset of poisoning attacks where the attacker aims to cause a Denial-of-Service (DoS) attack. However, the state-of-the-art algorithms are computationally expensive because they try to solve a complex bi-level optimization problem (the "hammer"). We observed that in particular conditions, namely, where the target model is linear (the "nut"), the usage of computationally costly procedures can be avoided. We propose a counter-intuitive but efficient heuristic that allows contaminating the training set such that the target system's performance is highly compromised. We further suggest a re-parameterization trick to decrease the number of variables to be optimized. Finally, we demonstrate that, under the considered settings, our framework achieves comparable, or even better, performances in terms of the attacker's objective while being significantly more computationally efficient.