Query-Efficient Black-Box Attacks on Machine Learning Models

This direction is split into other directions: query-intensive black-box optimization, black-box query efficiency. Its last version stays readable and citable here.

Version 1 of 1938 papers1,279 conceptsfrozen 2026-10-04

In the theoretical world of adversarial machine learning, an attacker is often modeled as having an "oracle"—a black box that provides an answer for every question asked. In this vacuum, an adversary can query a model millions of times to map its decision boundaries or steal its weights.

In the real world, however, every query has a cost. Commercial APIs like GPT-4 or DALL-E 3 charge per request, and security systems monitor for anomalous traffic patterns. High-frequency, repetitive querying is a "loud" behavior that triggers rate-limiters and anomaly detection. This has shifted the research frontier from simply finding vulnerabilities to finding them efficiently and stealthily.

The Problem of High-Volume Probing

Traditional black-box attacks, such as the One pixel attack by Danilo Vasconcellos Vargas, demonstrated that deep networks are fragile. However, as Nina Narodytska and Shiva Kasiviswanathan noted, these iterative searches often require a massive volume of queries to converge.

When an attacker lacks internal access to a model's gradients (the "slope" that points toward a mistake), they must estimate them. Standard zeroth-order optimization is notoriously query-hungry. Researchers like Haishan Ye and Tong Zhang addressed this in ZO-HessAware by approximating the "curvature" (Hessian) of the decision boundary, allowing the attack to find successful perturbations with a fraction of the usual queries.

Stealth through Local Surrogates

One of the most effective ways to reduce the query footprint on a target system is to move the "noisy" part of the search to a local environment. This is the core intuition behind Model Stealing and Mirroring.

In MEGA, Chi Hong and Lydia Y. Chen show that by using a collaborative generator-substitute network, an attacker can clone a model's functionality using minimal API interactions. Similarly, ShadowBreak, developed by Honglin Mu and Libo Qin, trains a "mirror model" on benign data. The attacker performs the iterative, detectable search for vulnerabilities on this local replica first, only sending the final, refined "jailbreak" to the target system. This approach achieved a 92% success rate while submitting 18x fewer detectable malicious queries.

Intelligent Search and Fuzzing

Rather than random trial-and-error, modern attacks treat vulnerability discovery as a sophisticated optimization problem.

  • Bayesian Optimization: Deokjae Lee and colleagues introduced Bayesian Red Teaming, which uses past evaluations to "guess" where the next failure might be, discovering three times more unique vulnerabilities within a fixed budget than brute-force methods.
  • Reinforcement Learning: Frameworks like PathSeeker and QROA treat jailbreaking as a navigation problem, using RL agents to "learn" the path through a model's safety guardrails.
  • Evolutionary Fuzzing: GPTFUZZER and JailFuzzer apply software testing principles (fuzzing) to LLMs. By mutating successful "seed" prompts and using Monte Carlo Tree Search, they evolve highly effective attacks that bypass filters with significantly lower overhead.

Exploiting Input Structure and Asymmetry

The latest wave of research focuses on "one-shot" or highly structured attacks that require almost no iteration. FlipAttack, by YINGWEI MA and Jinlan Fu, exploits the autoregressive nature of LLMs by simply flipping the order of characters. This bypasses safety filters that look for specific keywords at the start of a prompt, achieving a ~98% success rate in a single query.

Furthermore, Seyed-Mohsen Moosavi-Dezfooli argues in Rewriting the Budget that we must account for cost asymmetry. In the real world, a "benign" query that fails to jailbreak a model is cheap, but a "flagged" query that triggers a safety filter is expensive because it risks an account ban. Their framework, AGREST, optimizes attacks by intelligently balancing these high-risk and low-risk interactions.

Why It Works: The Efficiency Frontier

The success of these methods reveals a fundamental truth about modern AI: vulnerabilities are not isolated points, but regions. By using smarter search algorithms (Bayesian, RL), local surrogates (ShadowBreak), or structural exploits (FlipAttack), researchers have shown that an adversary doesn't need to "see" inside the box to break it. They only need enough information to find the edge of a vulnerable region, and they can now do so with a footprint small enough to vanish into the noise of normal traffic.

Papers in this version

Showing 60 of 938 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_query_efficient_black_box_attacks_on_mac_c62b5318,
  title = {Query-Efficient Black-Box Attacks on Machine Learning Models},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/query-efficient-black-box-attacks-on-machine-learning-models/rdr_c62b53181ac64753b98f8c99badd0fcb},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_query_efficient_black_box_attacks_on_mac_c62b5318_v1,
  title = {Query-Efficient Black-Box Attacks on Machine Learning Models},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/query-efficient-black-box-attacks-on-machine-learning-models/rdr_c62b53181ac64753b98f8c99badd0fcb/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}