PaperlayerView exact revision on arXiv

Source-linked AI summary

GeoDA: a geometric framework for black-box adversarial attacks

Ali Rahmati, Seyed-Mohsen Moosavi-Dezfooli, Pascal Frossard, Huaiyu Dai

arXiv:2003.06468v1cs.CVcs.CRcs.LG

TL;DR

GeoDA addresses the difficult setting of decision-based black-box attacks where each query returns only a classifier’s top-1 label and query budgets are small. It estimates decision-boundary normals from low curvature, then iteratively constructs general ℓp perturbations; experiments report smaller perturbations with fewer queries, while the ℓ2 case has convergence and query-allocation guarantees.

  • Problem

    Decision-based black-box attacks must find small adversarial perturbations when the attacker has no model parameters and receives only top-1 labels from a limited query budget.

  • Method

    GeoDA locally linearizes low-curvature decision boundaries, estimates their normals, and iteratively generates query-efficient ℓp perturbations.

  • Results

    GeoDA outperforms state-of-the-art black-box attacks by generating smaller perturbations with fewer queries, while the ℓ2 algorithm converges to minimal perturbations.

  • Takeaways & Limitations

    The framework provides a principled geometric approach for query-efficient decision-based attacks across ℓp norms, with stronger guarantees in the ℓ2 case.

  • Takeaways & Limitations

    The framework is scoped to classifiers with low-curvature decision boundaries and assumes a limited total query budget.

Abstract

from arXiv · show

Adversarial examples are known as carefully perturbed images fooling image classifiers. We propose a geometric framework to generate adversarial examples in one of the most challenging black-box settings where the adversary can only generate a small number of queries, each of them returning the top-$1$ label of the classifier. Our framework is based on the observation that the decision boundary of deep networks usually has a small mean curvature in the vicinity of data samples. We propose an effective iterative algorithm to generate query-efficient black-box perturbations with small $\ell_p$ norms for $p \ge 1$, which is confirmed via experimental evaluations on state-of-the-art natural image classifiers. Moreover, for $p=2$, we theoretically show that our algorithm actually converges to the minimal $\ell_2$-perturbation when the curvature of the decision boundary is bounded. We also obtain the optimal distribution of the queries over the iterations of the algorithm. Finally, experimental results confirm that our principled black-box attack algorithm performs better than state-of-the-art algorithms as it generates smaller perturbations with a reduced number of queries.

1. Introduction

The paper targets decision-based black-box attacks with only top-1 label access, using low decision-boundary curvature to estimate boundary normals and reduce queries. GeoDA supports general ℓp perturbations, provides ℓ2 convergence and query-allocation results, and incorporates prior information.

  • 1. Introduction: The method is designed for decision-based black-box evaluation, a setting relevant to applications such as autonomous systems and healthcare.In this setting, the adversary does not have full model access and receives only classifier outputs.
  • 1. Introduction: GeoDA uses low mean curvature near data samples to estimate decision-boundary normals with only top-1 label queries.The framework linearizes the boundary locally and uses this geometric prior to reduce the queries needed to fool the classifier.
  • 1. Introduction: The framework generates query-efficient ℓp black-box perturbations for p ≥ 1 and is evaluated on state-of-the-art natural image classifiers.The paper presents algorithms across ℓp norms and reports experimental effectiveness on modern classifiers.
  • 1. Introduction: For p = 2, GeoDA is shown to converge to the minimal ℓ2 perturbation while optimizing query allocation across iterative steps.The contribution includes both a convergence result and a theoretically derived distribution of queries over iterations.
  • 1. Introduction: GeoDA incorporates transferability and subspace constraints, with theory showing that prior information can improve normal-vector estimation accuracy.These priors bias the search space toward more accurate normal estimates.

2. Related work

Prior black-box attacks include score-based and decision-based methods, but many assume access to losses, probabilities, or multiple ranked labels. GeoDA instead develops a geometric, principled framework for general ℓp perturbations with ℓ2 convergence guarantees and optimized query allocation.

  • 2. Related work: Many existing black-box attacks assume access to loss values, prediction probabilities, or several sorted labels, which may be unrealistic.Decision-based attacks are more challenging because they expose less information about the target classifier.
  • 2. Related work: GeoDA replaces predominantly heuristic norm-minimization methods with a geometric framework for efficient general ℓp-norm perturbations.The framework is grounded in the geometric properties of deep-network decision boundaries.
  • 2. Related work: GeoDA provides convergence guarantees for ℓ2 perturbations and theoretically optimizes the distribution of queries across iterations.The query allocation is intended to use a limited query budget more efficiently.

3. Problem statement

The problem is to find a minimally distorted perturbation that changes a classifier’s top-1 label when the attacker lacks model parameters and receives only label queries. GeoDA addresses this by locating a nearby boundary point, locally linearizing the boundary, and estimating its normal with few queries.

  • 3. Problem statement: The attack minimizes a distance D(x, x + v) subject to changing the classifier’s top-1 label.The distance may be any function, including ℓp norms, and the attack is non-targeted.
  • 3. Problem statement: A small adversarial perturbation can be constructed by reaching the nearest decision boundary and moving beyond it along the boundary normal.The normal is therefore central to geometry-based attack construction.
  • 3. Problem statement: Low mean curvature near data samples permits local linearization of the decision boundary and supports geometric estimation of its normal.This property is the key prior used to make the black-box optimization tractable.
  • 3. Problem statement: A boundary point xB can be found by binary search, after which the normal estimator is computed using N1 classifier queries.For p = 2, the estimated direction is the direction of the minimal perturbation.
  • 3. Problem statement: Only top-1 label access makes the problem difficult because the attacker lacks model parameters and information required by zero-order optimization methods.GeoDA therefore focuses on estimating the boundary normal using geometric priors and minimal queries.

4. The estimator

GeoDA estimates the decision-boundary normal using top-1 queries on Gaussian perturbations, exploiting truncated-distribution structure and optional search-space priors. The estimator supports non-asymptotic error analysis and an optimal query allocation for the iterative attack.

  • Normal-vector estimation: GeoDA estimates the decision-boundary normal by querying Gaussian perturbations around a boundary point and separating adversarial from correctly classified samples.Samples are modeled through a hyperplane-truncated multivariate Gaussian distribution; correctly classified samples can be sign-flipped to improve estimation efficiency.
  • Normal-vector estimation: With full-rank covariance Σ, the truncated-distribution mean contains enough information to recover the boundary-normal direction.For the isotropic choice Σ = σI, the mean direction directly estimates the normal direction.
  • Perturbation priors: Prior information modifies Σ to focus sampling on useful directions, including low-frequency subspaces and transferred directions from another model.The transferred direction contributes through a tunable exploitation–exploration trade-off, while the modified covariance yields a more accurate normal estimate.
  • Estimator guarantees: The estimator applies to any classifier with a low-curvature decision boundary, not only deep networks.The framework analyzes normal estimation for flat boundaries and provides a non-asymptotic bound rather than relying only on asymptotic convergence.
  • Algorithm: Algorithm 1 allocates the query budget across iterations, finds an initial boundary point, and repeatedly estimates the normal to construct the adversarial example.The algorithm uses an optimal query distribution and iteratively updates the attack direction from the estimated normal.

5. Geometric decision-based attacks (GeoDA)

GeoDA turns local decision-boundary linearization into iterative black-box attacks for general ℓp norms, including ℓ2 convergence guarantees and query allocation under finite budgets. It also extends to sparse perturbations, while experiments compare perturbation quality, iterations, and sparsity-related fooling rates.

  • Geometric decision-based attacks: The general framework constructs query-efficient ℓp perturbations for p ≥ 1, with p = 1, 2, and ∞ handled through specialized update rules and line searches.The method estimates a boundary point and normal, solves the linearized norm-minimization problem, and updates the iterate.
  • Geometric decision-based attacks: GeoDA iteratively relinearizes the boundary at updated points because nonzero curvature prevents a single estimated normal from exactly matching the minimal perturbation.Each iteration solves the local linearized problem and moves to a new estimated boundary point.
  • 5.1. ℓ2 perturbation: For a bounded-curvature boundary with κr < 1, GeoDA’s ℓ2 iterates converge linearly to the minimum ℓ2 distance.The convergence statement assumes the curvature-radius product is below one and specifies a rate λ < 1.
  • 5.1. ℓ2 perturbation: Under a finite query budget, GeoDA’s convergence error reflects both boundary curvature and noisy normal estimates from limited queries.The analysis formulates query allocation as minimizing error across iterations; early iterations can use fewer queries before increasing the allocation.
  • Sparse perturbations: Sparse GeoDA selects the smallest set of extreme-valued coordinates needed to reach an approximated boundary under box constraints.It identifies top-k normal-vector coordinates and uses binary search to minimize k, starting from an ℓ2 GeoDA boundary point.

6. Experiments

Experiments evaluate GeoDA on ImageNet across ℓp norms, sparse perturbations, query allocation, and prior information. GeoDA achieves smaller perturbations with fewer iterations than competing decision-based attacks, especially under limited queries.

  • 6. Experiments: The evaluation uses 350 correctly classified, randomly selected ImageNet validation images on a pretrained ResNet-50, with median ℓp norms used for performance assessment.Sparse GeoDA additionally reports fooling rate and sparsity based on perturbed coordinates.
  • 6.2. Performance analysis: GeoDA generates smaller ℓ2 perturbations than HopSkipJump when the query budget is small, while requiring fewer iterations as queries increase.Its performance approaches HopSkipJump at larger query budgets, and its lower iteration count supports parallelization.
  • 6.2. Performance analysis: With limited queries, sparse GeoDA produces perturbations at about 3% sparsity relative to the white-box SparseFool attack, with an acceptable fooling rate.Increasing ζ raises fooling rate and sparsity, while smaller ζ produces sparser examples but lowers the chance of crossing the actual boundary.
  • 6.2. Performance analysis: GeoDA generates ℓ2 full-space, ℓ2 subspace, ℓ∞ full-space, ℓ∞ subspace, and ℓ1 sparse adversarial examples under a 10,000-query budget.The perturbations are magnified by approximately 10× for visibility.
  • 6.3. Effect of hyper-parameters on the performance: DCT subspace prior information reduces the ℓ2 perturbation norm by approximately 27% compared with the full-space case.The experiments also evaluate transferability as a prior for estimating the decision-boundary normal.
  • 6.2. Performance analysis: The query-allocation parameter λ performs worst near single-iteration and uniform distributions, motivating the intermediate choice λ = 0.6.The extreme cases are λ →0 and λ = 1, respectively.

7. Conclusion

The paper presents GeoDA as a geometric, query-efficient decision-based black-box attack using only top-1 labels. Its low-curvature assumption supports normal estimation, ℓ2 convergence guarantees, optimized query allocation, and strong empirical performance against state-of-the-art attacks.

  • 7. Conclusion: GeoDA uses the small curvature of deep-network decision boundaries near data samples to estimate boundary normals with few top-1 label queries.The resulting framework targets query-efficient ℓp-norm attacks in the decision-based black-box setting.
  • 7. Conclusion: For ℓ2 attacks, GeoDA theoretically converges to minimal adversarial perturbations and mathematically optimizes query allocation across iterative search steps.The conclusion also reports extensive experiments showing superior performance to state-of-the-art black-box attacks.

A. Proof of Lemma 2

The lemma proof establishes concentration for estimating the mean of a truncated Gaussian distribution used in GeoDA's normal estimation. It verifies sub-Gaussianity and bounds covariance terms needed for the sample-mean error guarantee.

  • A. Proof of Lemma 2: The truncated normal distribution is shown to be sub-Gaussian, allowing a concentration bound for the sample-mean estimator.The proof uses the truncated distribution's exponentially decaying tails to rule out heavy-tailed behavior.
  • A. Proof of Lemma 2: The proof evaluates the truncated Gaussian under a hyperplane constraint by transforming variables through a Cholesky factorization of the covariance matrix.This calculation verifies the sub-Gaussian condition for all unit directions.
  • A. Proof of Lemma 2: The sample mean provides a high-probability error bound after N neural-network queries, with the bound depending on covariance trace and maximum eigenvalue terms.The covariance eigenvalue is bounded using Weyl's inequality and the rank-1 normal-vector component.

B. Proof of Theorem 1

Theorem 1 is proved by analyzing GeoDA's iterative geometry for convex and concave decision boundaries with bounded curvature. In both cases, the perturbation radius decreases toward the minimum distance under the stated assumptions.

  • B. Proof of Theorem 1: The proof analyzes two curvature cases and uses geometric relations among the radius, curvature bound R, and angle θ_t to establish convergence.The iterative update is based on the boundary-normal direction and the distances from the original point.
  • Convex Curved Bounded Boundary: For convex bounded-curvature boundaries, assuming tan^2(θ_t) ≤ 0.2R/r and r/R < 1, the radius r_t decreases toward the minimum perturbation r.The proof shows θ_t decreases across iterations and r_t is increasing in θ_t, yielding r_{t+1} < r_t.
  • Concave Curved Bounded Boundary: For concave bounded-curvature boundaries, sin(θ_{t+K}) converges exponentially to zero, causing the iterates' radius to converge to the minimum distance.The convergence rate satisfies λ ∈ (0, 1) when r < R.

C. Proof of Theorem 2

The proof bounds the perturbation error by separating gradient-estimation error caused by finite queries from the iterative update behavior. It compares constructive and destructive gradient errors to characterize best- and worst-case bounds.

  • C. Proof of Theorem 2: The proof applies the iterative update and reverse-triangle-inequality analysis to derive a bound on the estimated perturbation distance.The derivation proceeds by multiplying the gradient-related inequality by the current radius and substituting the iterative radius expression.
  • C. Proof of Theorem 2: Best-case gradient errors make each estimated boundary distance smaller, whereas worst-case errors make it larger.The analysis treats practical behavior as lying between these constructive and destructive extremes.
  • C. Proof of Theorem 2: The perturbation bound accounts for gradient-estimation error introduced by the limited number of queries at each iteration.The supplied passages identify this term as the error due to a limited number of queries.

D. Proof of Theorem 3

The proof formulates the query-allocation problem as a convex optimization problem, solves it through duality and KKT conditions, and obtains the optimal queries per iteration. The resulting allocation increases queries later in the search.

  • D. Proof of Theorem 3: The convex query-allocation problem has zero duality gap, so its solution can be obtained from the dual problem.The proof introduces the Lagrangian and KKT conditions for the constrained optimization.
  • D. Proof of Theorem 3: The KKT derivation shows that the query budget constraint holds with equality and rules out an unconstrained infinite-query solution.Assuming unused budget forces the dual variable to zero, which contradicts the resulting infinite query allocation.
  • D. Proof of Theorem 3: The proof obtains the optimal number of queries for each iteration from the dual variable.This allocation is then related to the asymptotic ratio of queries across iterations.
  • D. Proof of Theorem 3: The optimal query distribution increases across iterations by a factor of λ^-2.The paper connects this allocation to the empirically supported low-curvature behavior near data points.
  • D. Proof of Theorem 3: The proof concludes after substituting the KKT-derived allocation into the constrained optimization conditions.The supplied proof passage explicitly marks completion after this derivation.

9. Additional experiment results

Additional experiments visualize GeoDA perturbations across ℓ2, ℓ∞, and ℓ1 settings and compare its performance across ResNet classifiers. The results indicate consistent behavior across a wide variety of deep networks.

  • 9. Additional experiment results: GeoDA generates adversarial examples for ℓ2 fullspace, ℓ2 subspace, ℓ∞ fullspace, ℓ∞ subspace, and ℓ1 sparse settings using N = 10000 queries.The figures show original images alongside the corresponding adversarial perturbations.
  • 9. Additional experiment results: The generated perturbations are reported as not quite visible in the displayed examples.The passage introduces the visual comparison of original images and perturbations before noting their limited visibility.
  • 9. Additional experiment results: Table 3 compares GeoDA across different ResNet image classifiers.The supplied table caption identifies the comparison scope, while the accompanying text describes the cross-network trend.
  • 9. Additional experiment results: GeoDA follows almost the same performance trend across a wide variety of deep networks.The passage attributes this consistency to the framework’s low-mean-curvature boundary assumption, which is reported as empirically verified.
Loading 2003.06468v1…