Finding adversarial examples for deep neural networks often feels like searching for a needle in a high-dimensional haystack. If an attacker wants to fool an image classifier or a video recognition system without knowing its internal weights (a "black-box" setting), they must estimate gradients or map decision boundaries purely by querying the model.
If the input space has $d$ dimensions (where $d$ represents thousands of pixels), a naive search requires an impractical number of queries, suffering severely from the curse of dimensionality.
However, a rich body of research demonstrates that attackers do not need to search all $d$ dimensions. Instead, adversarial vulnerability is concentrated within highly structured, low-dimensional subspaces. By restricting the search to these narrow slices of the input space, optimization becomes drastically more efficient, turning an intractable black-box search into a highly practical threat.
Why Do Low-Dimensional Vulnerabilities Exist?
To understand why this approach works, we must look at the geometry of how neural networks represent data. High-dimensional inputs like images do not uniformly fill their space; instead, natural data clusters onto a much lower-dimensional manifold.
As explained by John E. Hopcroft et al. in Computer Science in the Information Age, adversarial examples typically occur when an input is nudged perpendicular to these low-dimensional category manifolds. Because the manifold itself occupies a tiny fraction of the total activation space, even a small perpendicular shift can push the representation across a decision boundary into an entirely different class region, while remaining virtually identical to human observers.
Furthermore, network instability is mathematically confined to a small number of specific directions. Donsub Rim et al. demonstrate in A Stability Analysis of Neural Networks and Its Application to Tsunami Early Warning that applying singular value decomposition (SVD) to a model's mapping function isolates a limited set of highly sensitive input directions that maximize prediction error, regardless of how many parameters the model contains.
This geometric concentration means that adversarial examples are not isolated glitches scattered randomly across the input space. As proven theoretically by Elvis Dohmatob et al. in Origins of Low-Dimensional Adversarial Perturbations, deep classifiers are inherently vulnerable within low-dimensional slices—particularly "eigen-subspaces" derived from the covariance matrix of the model's gradients. If an attacker can identify these sensitive directions, they can ignore the rest of the high-dimensional space entirely.
Constructing the Subspace: Data and Model Priors
In a black-box scenario, the attacker cannot calculate the exact gradient of the target model. To find an effective low-dimensional subspace to search, they must rely on two primary types of priors: data-driven and model-driven.
Data-Driven Subspaces
One intuitive approach is to align the adversarial search with the natural variations of the data distribution. In Black-box Attacks on Deep Neural Networks via Gradient Estimation and Practical Black-Box Attacks on Deep Neural Networks Using Efficient Query Mechanisms, Arjun Bhagoji et al. apply Principal Component Analysis (PCA) to the input data to identify its primary components.
By restricting gradient estimation exclusively to these high-variance principal components, the authors decouple the query budget from the raw pixel count. This allows the attack to scale independently of input resolution, making attacks on high-resolution images computationally feasible.
Model-Driven Subspaces (Surrogates)
Alternatively, attackers can exploit the fact that different neural networks trained on similar tasks learn remarkably similar representations. Instead of searching raw pixel space, attackers can use a white-box "surrogate" model to construct a promising subspace.
Steven Y. Guo et al. formalize this in Subspace Attack: Exploiting Promising Subspaces for Query-Efficient Black-box Attacks. by constraining the black-box perturbation search to a low-dimensional subspace spanned by the gradients of a few reference models.
Expanding on this intuition, Nicholas A. Lord et al. show in Attacking deep networks with surrogate-based adversarial black-box methods is easy that restricting the search space to the row space (coimage) of a surrogate model's Jacobian matrix collapses the search dimensionality from hundreds of thousands of pixels down to the number of output classes.
Similarly, Zikui Cai et al. demonstrate in Blackbox Attacks via Surrogate Ensemble Search that the search space can be shifted entirely out of the pixel domain into a low-dimensional weight space of pre-trained surrogate models, finding successful perturbations in just a handful of queries.
[High-Dimensional Pixel Space (R^d)]
│
▼ (Project via PCA or Surrogate Jacobian)
[Low-Dimensional Subspace (R^k)] ◄─── Focus optimization here
│
▼ (Query & Update Coefficients)
[Successful Adversarial Perturbation]
To extract the most impactful directions from a proxy model without exhaustive computation, Linjun Zhou et al. introduce Adversarial Eigen Attack on BlackBox Models. By performing an SVD on a proxy model's Jacobian matrix, the attack identifies the right singular vectors that most significantly alter internal feature representations, providing a prioritized, low-rank basis for the black-box search.
Structural and Geometric Reductions
Subspaces do not always have to be derived from statistical decompositions like PCA or SVD; they can also be engineered by enforcing structural constraints that exploit domain geometry.
- Spatial Tiling: Images possess high spatial correlation. Andrew Ilyas et al. exploit this in Prior Convictions: Black-box Adversarial Attacks with Bandits and Priors by grouping pixels into discrete blocks (tiling) and estimating gradients for these blocks rather than individual pixels, drastically shrinking the optimization space.
- Geometric Parameterization: In video classification, the temporal dimension causes the raw search space to explode. Shasha Li et al. circumvent this in Adversarial Attacks on Black Box Video Classifiers: Leveraging the Power of Geometric Transformations by parameterizing perturbations through low-degree-of-freedom geometric transformations (such as translation and dilation) rather than pixel-level noise, achieving high success rates with far fewer queries.
- Planar Projections: For hard-label attacks (where the model only returns the top predicted class label), navigating the decision boundary is notoriously difficult. Chen Ma et al. show in Finding Optimal Tangent Points for Reducing Distortions of Hard-label Attacks that this high-dimensional boundary navigation can be simplified into a two-dimensional geometry problem by projecting the search onto a 2D plane spanned by the estimated gradient and the vector pointing back to the original benign image.
The Scaling Laws of Subspace Constraints
If an attacker restricts their search to a lower-dimensional subspace, how many dimensions do they actually need to retain to remain successful?
Charles Godfrey et al. systematically explore this question in How many dimensions are required to find an adversarial example? by projecting gradient-based perturbations onto random low-dimensional subspaces. They reveal a predictable scaling law: a model's adversarial vulnerability is fundamentally governed by the ratio of controllable dimensions to the total input size.
This predictable vulnerability scaling extends beyond vision models into language models. In Scaling Laws for Adversarial Attacks on Language Model Activations and Tokens, Stanislav Fort uses fractional dimensionality probing to demonstrate a linear scaling law in Large Language Models. By manipulating only a tiny fraction of internal activation dimensions, an attacker can precisely dictate a disproportionately large number of output tokens.
Ultimately, the success of subspace-constrained search proves that deep neural networks are not vulnerable to random high-dimensional noise. Instead, their vulnerabilities lie along highly concentrated, low-dimensional geometric manifolds that can be mapped, transferred, and exploited with remarkable efficiency.
Key Foundational Work
Black-box Attacks on Deep Neural Networks via Gradient Estimation (2018) — contributed 3 concept elements to this direction.
Practical Black-Box Attacks on Deep Neural Networks Using Efficient Query Mechanisms (2018) — contributed 2 concept elements to this direction.
Delving into Transferable Adversarial Examples and Black-box Attacks (2017) — contributed 2 concept elements to this direction.