# Evading Black-box Classifiers Without Breaking Eggs

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 42 references that are in the map.
- First posted on arXiv 5 Jun 2023.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Learning Transferable Visual Models From Natural Language Supervision](https://mlsanity.com/paper/2103.00020/) (2021)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [LAION-5B: An open large-scale dataset for training next generation image-text models](https://mlsanity.com/paper/2210.08402/) (2022)
- [Evasion Attacks against Machine Learning at Test Time](https://mlsanity.com/paper/1708.06131/) (2017)
- [ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Models](https://mlsanity.com/paper/1708.03999/) (2017)
- [On Adaptive Attacks to Adversarial Example Defenses](https://mlsanity.com/paper/2002.08347/) (2020)
- [Decision-Based Adversarial Attacks: Reliable Attacks Against Black-Box Machine Learning Models](https://mlsanity.com/paper/1712.04248/) (2017)
- [Transferability in Machine Learning: from Phenomena to Black-Box Attacks using Adversarial Samples](https://mlsanity.com/paper/1605.07277/) (2016)
- [HopSkipJumpAttack: A Query-Efficient Decision-Based Attack](https://mlsanity.com/paper/1904.02144/) (2019)
- [Query-Efficient Hard-label Black-box Attack:An Optimization-based Approach](https://mlsanity.com/paper/1807.04457/) (2018)
- [Sign-OPT: A Query-Efficient Hard-label Adversarial Attack](https://mlsanity.com/paper/1909.10773/) (2019)
- [Zeroth-Order Stochastic Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1805.10367/) (2018)
- [QEBA: Query-Efficient Boundary-Based Blackbox Attack](https://mlsanity.com/paper/2005.14137/) (2020)
- [RayS: A Ray Searching Method for Hard-label Adversarial Attack](https://mlsanity.com/paper/2006.12792/) (2020)
- [Motivating the Rules of the Game for Adversarial Example Research](https://mlsanity.com/paper/1807.06732/) (2018)
- [Stateful Detection of Black-Box Adversarial Attacks](https://mlsanity.com/paper/1907.05587/) (2019)
- ["Real Attackers Don't Compute Gradients": Bridging the Gap Between Adversarial ML Research and Practice](https://mlsanity.com/paper/2212.14315/) (2022)
- [Guessing Smart: Biased Sampling for Efficient Black-Box Adversarial Attacks](https://mlsanity.com/paper/1812.09803/) (2018)
- [Blacklight: Scalable Defense for Neural Networks against Query-Based Black-Box Attacks](https://mlsanity.com/paper/2006.14042/) (2020)
- [Black-box Adversarial Attacks on Commercial Speech Platforms with Minimal Information](https://mlsanity.com/paper/2110.09714/) (2021)
- [AdVersarial: Perceptual Ad Blocking meets Adversarial Machine Learning](https://mlsanity.com/paper/1811.03194/) (2018)
- [Adversarial attacks on Copyright Detection Systems](https://mlsanity.com/paper/1906.07153/) (2019)
- [Safe non-smooth black-box optimization with application to policy search](https://mlsanity.com/paper/1912.09466/) (2019)
- [Preprocessors Matter! Realistic Decision-Based Attacks on Machine Learning Systems](https://mlsanity.com/paper/2210.03297/) (2022)

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

- [SoK: Blockchain-Based Decentralized AI (DeAI)](https://mlsanity.com/paper/2411.17461/) (2024)
- [The Adaptive Arms Race: Redefining Robustness in AI Security](https://mlsanity.com/paper/2312.13435/) (2023)
- [Turn Fake into Real: Adversarial Head Turn Attacks Against Deepfake Detection](https://mlsanity.com/paper/2309.01104/) (2023)
- [Towards Non-Adversarial Algorithmic Recourse](https://mlsanity.com/paper/2403.10330/) (2024)
- [Constrained Adaptive Attacks: Realistic Evaluation of Adversarial Examples and Robust Training of Deep Neural Networks for Tabular Data](https://mlsanity.com/paper/2311.04503/) (2023)
- [Taking off the Rose-Tinted Glasses: A Critical Look at Adversarial ML Through the Lens of Evasion Attacks](https://mlsanity.com/paper/2410.12076/) (2024)
- [Understanding Adversarial Transfer: Why Representation-Space Attacks Fail Where Data-Space Attacks Succeed](https://mlsanity.com/paper/2510.01494/) (2025)
- [SEA: Shareable and Explainable Attribution for Query-based Black-box Attacks](https://mlsanity.com/paper/2308.11845/) (2023)
- [TA3: Testing Against Adversarial Attacks on Machine Learning Models](https://mlsanity.com/paper/2410.05334/) (2024)
- [FRAUD-RLA: A new reinforcement learning adversarial attack against credit card fraud detection](https://mlsanity.com/paper/2502.02290/) (2025)
- [Rewriting the Budget: A General Framework for Black-Box Attacks Under Cost Asymmetry](https://mlsanity.com/paper/2506.06933/) (2025)
- [Almost for Free: Crafting Adversarial Examples with Convolutional Image Filters](https://mlsanity.com/paper/2605.01098/) (2026)
- [REPLICANT: Learning Policies for Evading and Hardening Malware Detectors](https://mlsanity.com/paper/2608.28499/) (2026)

## Abstract (arXiv)

Decision-based evasion attacks repeatedly query a black-box classifier to generate adversarial examples. Prior work measures the cost of such attacks by the total number of queries made to the classifier. We argue this metric is flawed. Most security-critical machine learning systems aim to weed out "bad" data (e.g., malware, harmful content, etc). Queries to such systems carry a fundamentally asymmetric cost: queries detected as "bad" come at a higher cost because they trigger additional security filters, e.g., usage throttling or account suspension. Yet, we find that existing decision-based attacks issue a large number of "bad" queries, which likely renders them ineffective against security-critical systems. We then design new attacks that reduce the number of bad queries by 1.5-7.3×, but often at a significant increase in total (non-bad) queries. We thus pose it as an open problem to build black-box attacks that are more effective under realistic cost metrics.