In machine learning security, crafting an adversarial perturbation is straightforward when you have full access to a model's internal weights. By computing the gradient of the loss function via backpropagation, you can determine exactly how to alter an input to change the model's prediction.
But what happens when the target model is a "black box"—accessible only via an API that returns confidence scores or discrete labels? Without direct access to gradients, finding an adversarial vulnerability becomes a massive optimization challenge.
The field of surrogate-based gradient estimation solves this problem. By leveraging a local, fully accessible "surrogate" model to guide black-box queries, researchers have transformed black-box attacks from slow, query-intensive brute-force searches into highly efficient, targeted operations.
The Curse of Black-Box Estimation
To attack a black box without internal access, early methods relied on Zeroth-Order Optimization (ZOO). As detailed by Huan Zhang et al. in ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Models, an attacker can numerically estimate the gradient at any point by querying the target model with small, coordinate-wise perturbations.
Imagine trying to find the peak of a mountain in pitch-black darkness. You cannot see the slope, so you must tap the ground with a cane in every direction to figure out which way goes up.
If your input space is small, this works well. But for high-dimensional inputs like images, the number of directions you must tap explodes. Uniformly sampling a high-dimensional space requires thousands of expensive API queries, making pure zeroth-order optimization highly impractical for real-world systems.
The Core Insight: Functional Similarity
We can drastically outperform random guessing because deep neural networks trained on similar tasks learn remarkably similar functions. They carve up the input space using comparable decision boundaries and exhibit similar loss landscapes. This phenomenon is known as adversarial transferability.
Early foundational work by Battista Biggio et al. in Evasion Attacks against Machine Learning at Test Time demonstrated that an attacker could train a local surrogate model on a representative dataset and use its gradients to craft perturbations that successfully transfer to an unseen target system.
More recently, Nicholas A. Lord et al. showed in Attacking deep networks with surrogate-based adversarial black-box methods is easy that this functional similarity is so pronounced that the loss gradient of a local surrogate can often be used as a direct update direction for a remote victim, bypassing complex numerical estimation entirely.
Returning to our mountain analogy: while you are standing on a black-box mountain in the dark, you happen to possess a topographic map of a similar, neighboring mountain (the surrogate model). The map is not perfectly accurate for your current location, but it gives you an excellent macro-level heuristic of where the ridges and valleys lie.
The Hybrid Paradigm: Biasing the Search Space
Pure transfer attacks can fail if the surrogate and target architectures diverge significantly. Conversely, pure query-based optimization is too slow. The modern breakthrough in this domain is a hybrid paradigm: using surrogate gradients to bias or constrain query-based optimization.
As systematized by Fnu Suya et al. in SoK: Pitfalls in Evaluating Black-Box Attacks, combining transfer-based priors with query-based optimization yields a powerful synergy. Instead of tapping your cane in 360 degrees, you consult your surrogate map, see that the ridge likely runs northeast, and focus almost all your queries in that specific direction.
Thomas Brunner et al. formalized this in Guessing Smart: Biased Sampling for Efficient Black-Box Adversarial Attacks, demonstrating that sampling random search steps from a distribution heavily biased toward the surrogate's gradient drastically reduces the query budget required to find successful adversarial directions.
Algorithmic Mechanisms for Injecting Priors
Researchers have developed several distinct mathematical frameworks to integrate surrogate priors into the query loop:
1. Subspace Restriction
Instead of exploring the full, high-dimensional input space, attackers can restrict their search to a low-dimensional subspace spanned by the gradients of reference models. Steven Y. Guo et al. implemented this in Subspace Attack: Exploiting Promising Subspaces for Query-Efficient Black-box Attacks., demonstrating a 2x to 4x reduction in queries.
Taking this further, Huichen Li et al. showed in Nonlinear Projection Based Gradient Estimation for Query Efficient Blackbox Attacks that generative models (like VAEs or GANs) can be trained on surrogate gradient information to learn a low-dimensional representational prior, allowing the optimization process to completely ignore noisy, irrelevant input dimensions.
2. Dynamic Blending
How much should you trust your surrogate map versus your real-time queries? Rather than relying on rigid heuristics, Yinpeng Dong et al. formulated this balance as a loss minimization problem in Query-Efficient Black-box Adversarial Attacks Guided by a Transfer-based Prior. By dynamically calculating blending coefficients based on the estimated cosine similarity between the surrogate and target models, the attack relies heavily on the surrogate early on, but shifts toward direct query feedback if the surrogate prior proves inaccurate.
3. Bandit Optimization
Gradient estimation can also be framed as a continuous learning problem. Andrew Ilyas et al. proved in Prior Convictions: Black-box Adversarial Attacks with Bandits and Priors that framing the attack as a bandit optimization problem allows the attacker to maintain a persistent, evolving belief about the gradient direction across successive queries, integrating both temporal consistency and data-dependent priors seamlessly.
Conquering Hard-Label Boundaries
The most restrictive black-box setting is the "hard-label" scenario, where the target API returns only a discrete class label (e.g., "Cat") without any underlying probability scores. Classic geometric attacks, such as HopSkipJumpAttack: A Query-Efficient Decision-Based Attack by Jianbo Chen et al., walk along the decision boundary and estimate its orientation by observing where the labels flip.
To make these boundary walks query-efficient, Chen Ma et al. introduced Prior-OPT in Boosting Ray Search Procedure of Hard-label Attacks with Transfer-based Priors. This method injects white-box surrogate gradients directly into the boundary ray-search procedure, focusing the search on promising geometric directions.
The efficacy of these surrogate-guided hard-label methods has been extensively validated in standardized frameworks like BlackboxBench by Meixi Zheng et al. To optimize this process further, Ziang Yan et al. demonstrated in Policy-Driven Attack: Learning to Query for Hard-label Black-box Adversarial Examples that a reinforcement learning policy network can be trained to leverage internal gradient information to learn highly efficient query strategies.
Beyond Attacks: Defenses and Broader Applications
The core mechanic of surrogate-based gradient estimation—using a proxy model to predict and manipulate the gradient landscape of an unknown target—extends far beyond standard adversarial evasion.
Model Stealing Defenses
When adversaries try to clone a proprietary model by querying its API, defenders can turn surrogate modeling against them. In How to Steer Your Adversary: Targeted and Efficient Model Stealing Defenses with Gradient Redirection, Mantas Mazeika et al. showed that a defender can train a local surrogate to simulate the attacker's training process. The defender can then minimally perturb API outputs to actively redirect the attacker's gradients in a harmless direction.
Similarly, Tribhuvanesh Orekondy et al. developed Prediction Poisoning: Towards Defenses Against DNN Model Stealing Attacks, which uses a surrogate model to estimate the Jacobian of the loss function, ensuring that defensive output poisoning transfers effectively across diverse, unknown attacker architectures.
Data Ordering and Poisoning
Surrogates can also map out how models learn over time. Ilia Shumailov et al. demonstrated in Manipulating SGD with Data Ordering Attacks that a proxy model can approximate the loss landscape of a target model well enough to identify specific sequences of clean training data that stall or manipulate stochastic gradient descent (SGD). Zhonglin Ye et al. extended this proxy-gradient approach to higher-order relational structures in Momentum gradient-based untargeted poisoning attack on hypergraph neural networks.
Evolving and Large-Scale Systems
The paradigm continues to expand into complex distributed and multi-modal domains:
- Split Federated Learning: Jingtao Li et al. designed EMGAN: Early-Mix-GAN on Extracting Server-Side Model in Split Federated Learning, which trains a surrogate concurrently with a target model's initial training phase, capturing evolving gradients as a learning curriculum.
- Backdoor Optimization: The authors of Low-Frequency Black-Box Backdoor Attack via Evolutionary Algorithm utilize a semi-trained surrogate model to efficiently evaluate the effectiveness of low-frequency triggers without needing to retrain the victim model.
- Vision-Language Models: When scaling up to massive models, Daizong Liu et al. showed in Pandora's Box: Towards Building Universal Attackers against Real-World Large Vision-Language Models that weighting gradient estimates based on their historical importance across iterations allows universal adversarial patches to converge rapidly against black-box vision-language systems.
Key Foundational Work
Guessing Smart: Biased Sampling for Efficient Black-Box Adversarial Attacks (2019) — contributed 2 concept elements to this direction.
Subspace Attack: Exploiting Promising Subspaces for Query-Efficient Black-box Attacks. (2019) — contributed 2 concept elements to this direction.
Improving Black-box Adversarial Attacks with a Transfer-based Prior (2019) — contributed 2 concept elements to this direction.