PaperlayerView exact revision on arXiv

Source-linked AI summary

QEBA: Query-Efficient Boundary-Based Blackbox Attack

Huichen Li, Xiaojun Xu, Xiaolu Zhang, Shuang Yang, Bo Li

arXiv:2005.14137v1cs.LGcs.CVstat.ML

TL;DR

Adversarial examples threaten ML systems, including safety-critical applications, while practical blackbox attacks lack full model access and can require many queries. QEBA uses label-only boundary attacks with dimension-reduced gradient estimation, and reports lower perturbation magnitude with fewer queries and 100% success than state-of-the-art blackbox methods. The paper also evaluates attacks on ImageNet, CelebA, and commercial APIs.

  • Problem

    Blackbox adversarial attacks need practical query-efficient methods because attackers typically lack access to deployed models and high-dimensional gradient estimation requires many queries.

  • Method

    QEBA performs label-only boundary-based attacks using spatial, low-frequency, or intrinsic-component subspaces for gradient estimation.

  • Results

    Lower perturbation magnitude with fewer queries and 100% attack success rate was reported against state-of-the-art blackbox methods on ImageNet and CelebA, with additional commercial-API attacks.

  • Takeaways & Limitations

    QEBA significantly reduces required queries while producing high-quality adversarial examples against offline models and online real-world APIs.

  • Takeaways & Limitations

    Further extensive studies are required to compare subspace factors and identify new subspace types, while PCA can be challenging in time and memory efficiency on large data.

Abstract

from arXiv · show

Machine learning (ML), especially deep neural networks (DNNs) have been widely used in various applications, including several safety-critical ones (e.g. autonomous driving). As a result, recent research about adversarial examples has raised great concerns. Such adversarial attacks can be achieved by adding a small magnitude of perturbation to the input to mislead model prediction. While several whitebox attacks have demonstrated their effectiveness, which assume that the attackers have full access to the machine learning models; blackbox attacks are more realistic in practice. In this paper, we propose a Query-Efficient Boundary-based blackbox Attack (QEBA) based only on model's final prediction labels. We theoretically show why previous boundary-based attack with gradient estimation on the whole gradient space is not efficient in terms of query numbers, and provide optimality analysis for our dimension reduction-based gradient estimation. On the other hand, we conducted extensive experiments on ImageNet and CelebA datasets to evaluate QEBA. We show that compared with the state-of-the-art blackbox attacks, QEBA is able to use a smaller number of queries to achieve a lower magnitude of perturbation with 100% attack success rate. We also show case studies of attacks on real-world APIs including MEGVII Face++ and Microsoft Azure.

1. Introduction

QEBA addresses the practical need for blackbox adversarial attacks by reducing query costs while using only final prediction labels. It combines dimension-reduced gradient estimation with boundary-based optimization and evaluates the approach on image datasets and commercial APIs.

  • Motivation: Blackbox attacks are more practical than whitebox attacks because real-world applications generally do not release their models.Whitebox methods rely on model gradients and have also been shown to be defendable.
  • QEBA framework: QEBA uses only final prediction labels and targets query reduction for boundary-based blackbox attacks.The framework addresses the high query cost of estimating gradients in high-dimensional image spaces.
  • QEBA framework: QEBA estimates gradients in representative subspaces rather than the whole image space, using spatial, low-frequency, or intrinsic-component sampling.The paper theoretically analyzes the optimality of these subspace-based estimators relative to estimation in the original space.
  • Evaluation: 100% attack success rate was achieved with lower perturbation magnitude and fewer queries than state-of-the-art blackbox methods on ImageNet and CelebA.The experiments used ResNet models and also included attacks against MEGVII Face++ and Microsoft Azure APIs.
  • Evaluation: Further studies are required to compare more factors across the three subspaces and identify new subspace types.This limitation is stated alongside the paper’s initial empirical observations of the subspace choices.

2. Problem Definition

The problem is to construct a targeted adversarial image that remains classified with a chosen malicious label while staying close to a benign target image. In the label-only blackbox setting, the attacker observes predicted labels but not the model parameters or confidence scores.

  • Blackbox setting: The attacker queries updated images and receives only their predicted labels, without access to model parameters or confidence scores.For a k-way classifier, the returned label is the class with the highest confidence score.
  • Attack setup: A source image from the malicious class is moved toward a benign target image while retaining the malicious label.An image on the decision boundary that is classified as malicious is called a boundary-image.
  • Objective: The adversary seeks an image classified as y_mal that minimizes its distance to the target image.The distance metric is usually the L2-norm or L∞-norm, and the paper focuses on targeted attacks.

3. Query-Efficient Boundary-based blackbox Attack (QEBA)

QEBA reduces blackbox attack queries by estimating the decision-boundary gradient within representative lower-dimensional subspaces, then iteratively updating and projecting adversarial images. It explores spatial, low-frequency, and intrinsic-component subspaces to make gradient estimation more efficient.

  • General framework: QEBA initializes an adversarial image, estimates the gradient near the decision boundary, moves along that gradient, and projects the result back to the boundary.The pipeline is based on HSJA and uses only the victim model’s decision output.
  • General framework: The gradient estimator samples perturbations from a representative subspace instead of the full space, reducing the dimensionality of query generation.Random perturbations are mapped through an orthonormal basis, and Monte Carlo queries approximate the adversarial prediction-score gradient.
  • Spatial Transformed Subspace (QEBA-S): QEBA-S samples a lower-dimensional spatial perturbation and maps it back to image space using bilinear interpolation.The method is motivated by local similarity in image gradients and uses a dimension reduction factor r.
  • Low Frequency Subspace (QEBA-F): QEBA-F samples perturbations from the low-frequency image subspace using DCT and inverse DCT transformations.The lower ⌊N/r⌋ portion of the frequency domain is used as the reduced subspace.
  • Intrinsic Component Subspace (QEBA-I): QEBA-I constructs an intrinsic subspace by applying PCA to gradients from reference models and extracting the top principal components.Randomized PCA is used because the ImageNet data dimension exceeds 150k and the dense gradient matrix creates time, memory, and storage challenges.

4. Theoretic Analysis on QEBA

QEBA’s dimension-reduced gradient estimation yields tighter theoretical bounds than sampling the entire gradient space. The benefit depends on how much of the gradient lies in the chosen representative subspace.

  • Theoretical benefit: Dimension reduction gives a tighter gradient-estimation bound than sampling from a representative subspace’s complement or the full gradient space.The analysis establishes the benefit of sampling within a representative subspace.
  • Theorem: The expected cosine similarity between the estimated and true gradients is bounded under Lipschitz-gradient, orthogonality, and orthonormal-basis assumptions.The theorem assumes S(x) has L-Lipschitz gradients, sampled directions are mutually orthogonal, and WᵀW = I.
  • Whole-space baseline: With m = 3 × 224 × 224 and B = 100, sampling the entire space yields similarity of only around 0.02.This illustrates the inefficiency of whole-space gradient estimation in high-dimensional image inputs.
  • Empirical implication: When n = m/16, experiments reach ρ = 0.5, and the expected cosine similarity increases to around 0.06.The higher captured gradient proportion improves estimation quality and supports more efficient attacks.

5. Experiments

The experiments evaluate QEBA variants against HSJA on offline image models and commercial APIs, using query efficiency, perturbation magnitude, and attack success as key criteria. Across these settings, optimized subspaces produce more efficient and smoother attacks while preserving successful boundary-based attacks.

  • Experimental setup: The evaluation compares QEBA-S, QEBA-F, and QEBA-I with HSJA on ImageNet, CelebA, Face++, and Azure.Offline experiments use ResNet models and randomly selected correctly classified source-target pairs; online experiments use Face++ ‘compare’ and Azure ‘detect’ APIs.
  • Evaluation metrics: Attack quality is measured by average MSE to the target image and attack success rate under query and MSE thresholds.Lower MSE indicates smaller perturbation and greater similarity to the target, while fewer queries indicate greater efficiency.
  • Offline-model results: All three QEBA methods outperform HSJA significantly on average MSE and success-rate evaluations across ImageNet and CelebA.The success-rate curves use MSE thresholds of 10^-3 for ImageNet and 10^-5 for CelebA.
  • Offline-model results: Sampling in optimized subspaces performs better than sampling in the original space, while the intrinsic component subspace does not outperform the spatial and low-frequency subspaces.The authors attribute the intrinsic-subspace result potentially to using 280000 cases to identify components in a 150528-dimensional space.
  • Offline-model results: On ImageNet, subspace sampling reaches MSE below 1 × 10^-3 in around 2K queries, with lower MSE after 10K queries.At roughly 2K queries, adversarial perturbations are already difficult to distinguish visually in the example.
  • Online-API results: On Face++ and Azure, all methods produce successful attacks, but QEBA generates smoother, lower-perturbation instances more efficiently than HSJA.HSJA produces duplicated eyes on Face++ and cat-ear artifacts on Azure, while QEBA achieves smaller distances to the target image.

6. Related Work

Prior blackbox attacks include boundary-based methods that use final classifier decisions, but their random sampling can converge slowly and require many queries. Related work improves perturbation sampling or estimates boundary gradients, while other approaches use score-based or evolutionary techniques.

  • Boundary-based attacks: Boundary Attack uses only final classifier decisions, starting from a malicious-class source image and moving toward the target image.It uses reject sampling and random walks along the decision boundary.
  • Boundary-based attacks: Randomly sampled steps make Boundary Attack converge slowly and require many queries.This motivates more efficient perturbation and gradient-estimation strategies.
  • Boundary-based attacks: Several methods improve Boundary Attack by replacing Gaussian perturbations with Perlin noise, alpha distributions, or DCT-based sampling.These methods choose random perturbations more strategically at each step.
  • Boundary-based attacks: Monte Carlo methods approximate the gradient around the decision boundary to improve blackbox attack performance.These approaches remain related to boundary-based query strategies.
  • Other blackbox attacks: Other blackbox attacks transform boundary outputs into continuous scores or use evolutionary algorithms for decision-based face-recognition attacks.Dimension-reduction methods had also been explored for score-based attacks requiring confidence-score access.

7. Conclusion

QEBA is a general query-efficient boundary-based blackbox attack framework that uses spatial, frequency, and intrinsic-component subspaces. Its theory analyzes subspace gradient estimation, and experiments report fewer queries, high-quality adversarial examples, and attacks against offline models and real-world APIs.

  • Conclusion: QEBA is a general query-efficient boundary-based blackbox attack framework.The framework is designed to reduce the number of model queries.
  • Conclusion: Three subspace approaches reduce queries through spatial, frequency, and intrinsic-component optimization.These perspectives define the framework’s main attack variations.
  • Conclusion: Theoretical analysis shows optimality of subspace-based gradient estimation compared with estimation over the original space.The conclusion frames this as the basis for query reduction.
  • Conclusion: Extensive experiments report significantly fewer required queries and high-quality adversarial examples against offline models and online real-world APIs.The reported API evaluations include both offline and online settings.

A. Proof of Theorem 1

The proof analyzes gradient estimation from random orthonormal directions in an m-dimensional space. It bounds the expected cosine similarity between the estimated and true gradients using a dimension-dependent constant and boundary smoothness assumptions.

  • Lemma 1: Lemma 1 assumes an L-Lipschitz gradient near a boundary point and B mutually orthogonal unit vectors sampled from R^m.The lemma studies the expected alignment between estimated and true gradients.
  • Bound: The expected cosine similarity is bounded by a dimension-dependent constant c_m, with c_m ∈ (2/π, 1).The proof obtains the theorem from the lemma and bounds the relevant beta-function expression through scaling.
  • Proof setup: The sampled vectors are expanded into an orthonormal basis so the gradient direction can be analyzed coordinate-wise.This proof representation introduces basis coordinates for the normalized gradient.
  • Sign analysis: The boundary-response sign is determined for coordinates outside the interval [-w,w], with an undetermined region between the thresholds.Here w is defined from the gradient smoothness, query radius, and gradient norm.
  • Gradient estimation: The estimated gradient is rewritten in terms of the coordinate-dependent signs before its cosine similarity is calculated.The proof derives the estimator from the sign behavior and then combines the resulting expressions.
  • Bound: The proof further bounds the beta-function term between 2√m and π√m to establish the stated conclusion.This calculation supplies the dimension-dependent normalization used in the cosine-similarity bound.
Loading 2005.14137v1…