Standard adversarial machine learning relies on a simple, powerful mechanism: if you have access to a model's internal weights, you can compute the gradient of its loss function with respect to its input. This gradient acts as a compass, pointing exactly how to tweak an image, text prompt, or audio clip to force a misclassification.
But what happens when the gradient disappears? In real-world deployments, models are typically locked behind APIs that only return a final prediction score or a discrete label. In other domains, the input space itself is non-differentiable—such as discrete text tokens, graph structures, or malware binaries.
To bypass these restrictions, researchers use black-box adversarial optimization. Instead of calculating gradients through backpropagation, these methods treat the target model as an opaque oracle. By leveraging derivative-free optimization (DFO) techniques, they map out and exploit a model's decision boundaries using only its outputs. As Mahmood et al. establish in Back in Black, these score-based attacks use continuous confidence scores to iteratively guide perturbations, proving that internal model architecture is not required to systematically break deep learning systems.
Local Exploration via Random Search
Imagine trying to find the lowest point of a valley in pitch-black darkness. You cannot see the slope, but you can measure your current altitude. If you take a step in a random direction and your altitude drops, you keep moving that way; if it rises, you step back and try another direction.
This coordinate-descent intuition underpins localized random search attacks. In Simple Black-box Adversarial Attacks, Guo et al. introduced SimBA, a method that samples random vectors from an orthonormal basis and applies them to an input. By checking both the positive and negative directions of the sampled vector, the algorithm ensures a steady decrease in the model's confidence for the correct class without ever estimating an explicit gradient.
[Original Input] ---> Query Model ---> Get Confidence Score
|
Apply Random Local Update (e.g., Square or Vector)
|
v
[Perturbed Input] --> Query Model ---> Check Score
|
+------------------------------------+
|
v
Score Decreased?
├── Yes: Keep update, iterate.
└── No: Discard update, try new direction.
While pixel-level random adjustments work, they can be query-intensive. To optimize this process, Andriushchenko developed the Square Attack, which replaces isolated pixel changes with localized, square-shaped updates. This works because natural images exhibit heavy spatial correlation; changing a coherent block of pixels alters the high-level semantic features perceived by convolutional layers far more effectively than scattered noise. Crucially, because this structured random search relies strictly on output scores rather than backpropagation, Andriushchenko demonstrates that it completely bypasses "gradient masking" defenses—security measures that intentionally obfuscate internal gradients to thwart white-box attacks.
Global Navigation via Evolutionary Algorithms
Local random search is highly effective when the input space is continuous and smooth. However, many real-world attack surfaces are discrete, highly non-linear, or strictly constrained. For example, modifying a Windows malware executable requires preserving its malicious functionality; changing a single random byte might corrupt the file header and crash the program entirely.
To navigate these rugged landscapes, optimization frameworks turn to population-based evolutionary algorithms. Instead of tracking a single point, these algorithms maintain a diverse pool of candidate perturbations that undergo selection, crossover, and mutation based on their "fitness"—defined by how effectively they lower the target detector's confidence score.
In the context of binary executable evasion, Biggio developed GAMMA (Efficient Black-box Optimization of Adversarial Windows Malware with Constrained Manipulations), which uses genetic operators to inject benign code sections into non-functional "dead zones" of malware files. Similarly, Demetrio et al. show in Adversarial EXEmples that optimizing functionality-preserving manipulations allows malicious payloads to seamlessly blend in with legitimate software patterns.
The utility of evolutionary optimization spans across multiple modalities:
- Computer Vision: Vargas (Attacking Convolutional Neural Network using Differential Evolution) showed that population-based differential evolution can navigate high-dimensional spaces to find global optima that local gradient methods miss, famously enabling the modification of just a few pixels to trigger misclassification.
- Physical Threats: In Physically Realizable Adversarial Examples for LiDAR Object Detection, a genetic algorithm was used to evolve the geometry of 3D meshes over multiple generations, selecting for physical shapes that minimize detection confidence and render vehicles invisible to LiDAR sensors.
As Lapid et al. note in An Evolutionary, Gradient-Free, Query-Efficient, Black-Box Algorithm for Generating Adversarial Instances in Deep Convolutional Neural Networks, these evolutionary approaches are inherently resilient against input transformations (such as spatial smoothing or JPEG compression) because they do not rely on fragile, localized gradient vectors that can be easily disrupted by smoothing defenses.
Reconstructing Gradients via Zeroth-Order Estimation
When an attacker wants the precision and speed of gradient descent but lacks access to internal weights, they can estimate the missing gradient using zeroth-order optimization.
The mathematical engine behind this approach is typically the Natural Evolution Strategy (NES). Instead of evaluating a single input, the attacker queries the target model with a tight cluster of random perturbations centered around the current input. By observing how the output scores shift across this local neighborhood, the attacker can mathematically reconstruct an approximation of the loss gradient.
[Perturbation 1] -> Score A
/
Current Input [X] ---- [Perturbation 2] -> Score B ===> Compute Average Directional Change ===> Estimated Gradient Vector
\
[Perturbation 3] -> Score C
This technique bridges the gap between white-box optimization and black-box constraints. For instance, Chen et al. developed FAKEBOB (Who is Real Bob? Adversarial Attacks on Speaker Recognition Systems), utilizing NES gradient estimation to craft voice clones that bypass biometric speaker verification systems with near-perfect success rates. In the video domain, Cao et al. introduced StyleFool, which uses NES to estimate loss gradients through iterative queries. These estimates guide a projected gradient descent process that applies style-transfer modifications, ensuring that adversarial videos successfully fool classification networks while remaining visually natural to human observers.
Self-Evaluation and Discrete Prompt Optimization
The emergence of Large Language Models (LLMs) and vision-language models introduces a unique challenge: text tokens are discrete, and generative outputs are open-ended. Traditional logit-based score feedback is frequently hidden behind commercial web APIs, meaning attackers cannot observe fine-grained probability shifts.
To overcome this, modern black-box optimization loops treat the target model not just as a victim, but as its own evaluator. In Black-box Optimization of LLM Outputs by Asking for Directions, Zhang et al. exploit a core property of LLMs: they are significantly better at relative comparison than absolute self-rating. The optimization loop generates two slightly altered inputs and asks the LLM itself to choose which one better aligns with an adversarial objective. This pairwise comparison acts as a discrete hill-climbing signal, proving that highly capable models can be systematically steered into jailbreaks or misclassifications without logit access.
Similarly, in the visual-generative space, Yang et al. developed BSPA (Exploring Black-box Stealthy Prompt Attacks against Image Generators). BSPA uses automated feedback loops and pseudo-labeling to iteratively refine benign-looking prompts until they bypass safety filters to generate restricted content. By treating the entire generative pipeline as an end-to-end black box, these methods demonstrate that safety guardrails can be systematically eroded through purely query-driven optimization.