Technical Summary: Tangent Subspace Boundary Attack (TSBA)

Problem Statement

The paper addresses the challenge of decision-based black-box adversarial attacks, a setting where an attacker has access only to the final predicted label of a target model, without access to confidence scores or gradients. This setting is particularly difficult in high-dimensional input spaces (e.g., ImageNet) because the lack of gradient information makes efficient exploration of the input space to find minimal perturbations extremely hard.

Existing methods suffer from fundamental limitations:

• Boundary Attack: Relies on high-dimensional random sampling and rejection, leading to poor query efficiency.
• HopSkipJumpAttack (HSJA): Improves efficiency by estimating gradients via random sampling but introduces high variance and substantial query overhead.
• General Limitation: Prior approaches often fail to explicitly exploit the local geometric structure of the decision boundary, leading to unstable exploration, radial expansion of perturbations, and redundant queries.

Methodology: Tangent Subspace Boundary Attack (TSBA)

The authors propose TSBA, a decision-based attack that explicitly incorporates geometric constraints to stabilize the search process and reduce query variance. The core philosophy is to decouple boundary approximation from direction exploration.

The methodology consists of three key components:

1. Boundary Projection via Binary Search

Instead of gradually reducing perturbation magnitude through random walks, TSBA explicitly projects the current adversarial point onto the decision boundary.

• Given an adversarial point $x_{adv}$ and the original input $x_o$, the algorithm defines a line segment between them.
• It performs a binary search to find the smallest step size $\lambda$ such that the point $(1-\lambda)x_o + \lambda x_{adv}$ is still misclassified.
• This yields a projected point $x_b$ that lies precisely on the decision boundary, eliminating redundant distance-reduction steps found in prior methods.

2. Tangent-Space Constrained Updates

To ensure that updates move toward the original image without increasing the distance (radial expansion), TSBA enforces an orthogonality constraint.

• At a boundary point $x_b$, the "source direction" is defined as $v_k = x_b - x_o$.
• Any candidate perturbation $\delta$ is projected onto the tangent space orthogonal to $v_k$:
  $$\delta \leftarrow \delta - \frac{\langle \delta, v_k \rangle}{\|v_k\|^2} v_k$$
• Theoretical Justification: The paper proves (Proposition 1) that under this orthogonality constraint, the distance to the original input $\|x_{b}^{k+1} - x_o\|$ does not increase after projection. This ensures a locally monotonic reduction in distortion.

3. Low-Dimensional Subspace Sampling

To address the inefficiency of sampling in high-dimensional spaces ($d \gg 1$), TSBA restricts perturbations to a low-dimensional subspace.

• A basis $U \in \mathbb{R}^{d \times k}$ (where $k \ll d$) is used.
• Perturbations are sampled as $\delta = Uz$, where $z \sim \mathcal{N}(0, I_k)$.
• This structured sampling significantly increases the probability of finding effective directions compared to full-dimensional random sampling.

Algorithm Flow:

1. Project initial adversarial example to the boundary via binary search.
2. Sample a perturbation in a low-dimensional subspace.
3. Project the perturbation onto the tangent space (orthogonal to the source direction).
4. Update the point and re-project to the boundary via binary search.
5. Repeat until convergence or query budget exhaustion.

Key Contributions

The authors summarize their contributions as follows:

1. Boundary Projection Mechanism: An efficient binary search approach to approximate the decision boundary, removing redundant steps inherent in prior random-walk methods.
2. Tangent-Space Update Strategy: A novel constraint enforcing orthogonality to the source direction, theoretically guaranteeing locally monotonic reduction in perturbation magnitude.
3. Structured Subspace Sampling: The integration of low-dimensional subspace sampling to improve exploration efficiency and stability in high-dimensional spaces.
4. Empirical Validation: Extensive experiments demonstrating superior query efficiency and competitive distortion compared to state-of-the-art methods.

Experimental Results

Experiments were conducted on the ImageNet dataset using a pretrained ResNet-50 model, comparing TSBA against Boundary Attack and HopSkipJumpAttack (HSJA).

Query Efficiency and Success Rate

• Success Rate: Under a query budget of 500, TSBA achieved a 46% success rate, outperforming HSJA (38%) and Boundary Attack (28%). At 1500 queries, TSBA reached 80%, compared to 73% (HSJA) and 61% (Boundary Attack).
• Query Cost: TSBA required significantly fewer median queries to succeed. For a 500-query budget, TSBA needed a median of 150 queries, whereas HSJA needed 210 and Boundary Attack needed 340.

Query-Distortion Trade-off

• TSBA consistently achieved lower $\ell_2$ distortion across all query budgets.
• In the low-query regime (<1000 queries), TSBA showed a significant advantage in rapidly approaching the decision boundary with minimal distortion.

Robustness Evaluation

TSBA was tested against defended models (Adversarially Trained PGD and Randomized Smoothing RS).

• Under an RMSE constraint ($\le 0.1$), TSBA achieved success rates of 70-72% on robust models, significantly outperforming Boundary Attack (35-48%) and HSJA (55-69%).
• TSBA also required fewer queries (approx. 1600-1700) compared to HSJA (5001) and Boundary Attack (2200+) to achieve successful attacks on robust models.

Qualitative Analysis

Visual analysis of perturbations revealed that TSBA generates lower-magnitude, more localized perturbations concentrated on semantically informative regions (e.g., object boundaries), whereas Boundary Attack produced high-frequency noise across large image regions.

Ablation Study

Removing any of the three core components (Boundary Projection, Tangent Constraint, or Subspace Sampling) resulted in degraded performance:

• Without Projection: Increased queries and distortion.
• Without Tangent Constraint: Reduced stability and slower convergence.
• Without Subspace: Significantly degraded query efficiency due to the difficulty of high-dimensional random sampling.

Significance and Claims

The paper claims that the inefficiency of existing decision-based attacks stems from an under-exploitation of the local geometric structure of the decision boundary. By explicitly constraining updates to a tangent subspace and decoupling boundary approximation from direction exploration, TSBA provides a principled mechanism to:

1. Stabilize the search process by avoiding radial expansion of perturbations.
2. Reduce variance in sampled directions.
3. Achieve query efficiency comparable to or better than gradient-estimation methods without actually estimating gradients.

The authors conclude that TSBA highlights the fundamental role of local decision boundary geometry in adversarial vulnerability and offers a new direction for designing efficient black-box attacks. They note that their approach suggests adversarial perturbations can be effectively optimized within a low-dimensional tangent structure.

Future work is proposed to investigate adaptive subspace learning, dynamic step-size control, and extensions to video and 3D data, as well as exploring theoretical guarantees on convergence and query complexity.