PaperlayerView exact revision on arXiv

Source-linked AI summary

Guessing Smart: Biased Sampling for Efficient Black-Box Adversarial Attacks

Thomas Brunner, Frederik Diehl, Michael Truong Le, Alois Knoll

arXiv:1812.09803v3stat.MLcs.CRcs.CVcs.LG

TL;DR

Adversarial examples can pose safety and security concerns, and exact-label targeted attacks are especially difficult. The paper reframes the Boundary Attack as biased sampling using domain knowledge, and reports that its combined biases outperform prior label-only attacks.

  • Problem

    Targeted attacks require an exact specified label and are strictly harder; transfer-based attacks can be unreliable, while the Boundary Attack is query-intensive.

    Source: §1 · p. 2, §2.1 · p. 2, §2.2 · p. 2

  • Method

    The paper reframes the Boundary Attack as biased sampling, using low-frequency patterns, regional masks, and surrogate-model gradients.

    Source: §1 · p. 2

  • Results

    The combined biased Boundary Attack significantly outperforms previous state of the art in label-only black-box attacks, reaching 85% success after 15,000 queries.

    Source: §4.1.1 · p. 6, §5 · p. 8

  • Takeaways & Limitations

    Decision-based black-box attacks can be sped up by incorporating prior knowledge into the Boundary Attack’s sampling distribution.

    Source: §5 · p. 8

    The Boundary Attack typically requires hundreds of thousands of model queries to achieve its results.

    Source: §2.2 · p. 2

Abstract

from arXiv · show

We consider adversarial examples for image classification in the black-box decision-based setting. Here, an attacker cannot access confidence scores, but only the final label. Most attacks for this scenario are either unreliable or inefficient. Focusing on the latter, we show that a specific class of attacks, Boundary Attacks, can be reinterpreted as a biased sampling framework that gains efficiency from domain knowledge. We identify three such biases, image frequency, regional masks and surrogate gradients, and evaluate their performance against an ImageNet classifier. We show that the combination of these biases outperforms the state of the art by a wide margin. We also showcase an efficient way to attack the Google Cloud Vision API, where we craft convincing perturbations with just a few hundred queries. Finally, the methods we propose have also been found to work very well against strong defenses: Our targeted attack won second place in the NeurIPS 2018 Adversarial Vision Challenge.

1. Introduction

The paper addresses black-box adversarial attacks, which raise safety and security concerns and become harder when only labels are available or an exact target label is required. It reframes the Boundary Attack as biased sampling and reports that combining three biases outperforms prior label-only attacks.

1. Introduction

  • Decision-based black-box attacks expose only a discrete top-1 label, making gradient estimation very inefficient despite their broader real-world reach.White-box attacks can use gradients computed from model parameters, which are unavailable in the black-box setting.Source: §1 · p. 1
  • The threat setting requires a convincing adversarial example in fewer than 15,000 queries.The paper notes that attacks needing millions of queries and potentially hours may not be feasible.Source: §1 · pp. 1–2
  • Targeted attacks require the exact specified label and are strictly harder than untargeted attacks, which succeed on any label other than the original.An untargeted attack can sometimes succeed by finding a label that requires little change.Source: §1 · p. 2
  • The Boundary Attack is reframed as a biased-sampling framework that gains efficiency from prior beliefs about the target domain.The proposed biases are low-frequency patterns, regional masks, and surrogate-model gradients.Source: §1 · p. 2
  • The combined biases drastically outperform the previous state of the art in label-only black-box attacks.The paper reports this comparison for its approach.Source: §1 · p. 2

2. Related Work

Related work contrasts efficient but brittle transfer attacks with flexible sampling methods that can be too query-intensive. The Boundary Attack is a strong sampling-based approach, but typically requires many model queries.

2.1. Transfer-based

  • Transfer-based attacks can be efficient but unreliable: reduced transferability can make them fail completely, even after thousands of iterations.The attacker may need to train substitute models as robust as the defender’s.Source: §2.1 · p. 2

2.2. Sampling-based

  • Sampling-based attacks avoid direct transfer, but random search in high-dimensional input space can be very inefficient.The simplest hypersphere-sampling approach has been dismissed as unviable, though the paper reports accelerating it in some scenarios.Source: §2.2 · p. 2
  • The Boundary Attack produces examples competitive with state-of-the-art white-box attacks, but typically requires hundreds of thousands of model queries.It initializes from an input of the target class and takes small steps along the decision boundary toward the original input.Source: §2.2 · p. 2
  • Recent black-box work largely targets score-based classifiers, an easier setting, although its sampling biases may also benefit from the proposed approach.The authors report that Ilyas et al.’s discrete-label gradient-estimation variant is less efficient than Boundary Attack variants.Source: §2.2 · p. 2

3. Biased Boundary Attacks

The Boundary Attack is recast as biased sampling, using domain priors to favor perturbations more likely to succeed. The section develops low-frequency, regional-mask, and surrogate-gradient biases, then relates them to concurrent prior-based work.

3. Biased Boundary Attacks

  • The Boundary Attack's independent-pixel sampling is inefficient on robust models, motivating biases that favor plausible image perturbations and likely adversarial directions.The authors outline three such biases for image classification: low-frequency patterns, regional masks, and surrogate gradients.Source: §3 · p. 3

3.1. Low-frequency perturbations

  • Perlin-noise sampling concentrates orthogonal perturbations in low-frequency directions and improves attack efficiency in the authors' experiments.The authors hypothesize that low-frequency perturbations may improve robustness because high-frequency patterns are often targeted by filtering defenses.Source: §3.1 · p. 3

3.2. Regional masking

  • Regional masks weight each step toward pixels that differ more between the target-class and attacked images, and the evaluation reports a significant efficiency improvement.The mask is recalculated during the attack; it amplifies distortion in high-difference pixels and dampens it in similar pixels while keeping perturbation magnitude constant.Source: §3.2 · p. 4, Figure 3 · p. 4

3.3. Gradients from surrogate models

  • The surrogate-gradient bias extends sampling with limited gradient information, so low transferability slows the method rather than causing the complete failure typical of transfer attacks.The bias strength w is tuned to surrogate performance; the authors report that even surrogates too weak for direct transfer attacks can be used.Source: §3.3 · pp. 4–5

3.4. Concurrent work

  • Concurrent work also uses prior information to improve query efficiency; its data-dependent prior resembles the paper's low-frequency bias, while its time-dependent prior is suggested as a possible future addition.The authors expect Guo et al.'s frequency-filtered perturbations to resemble patterns from their Perlin bias.Source: §3.4 · p. 5

4. Evaluation

The evaluation tests biased Boundary Attacks on ImageNet and Google Cloud Vision, finding that combining the biases improves ImageNet attack performance and that the API attacks succeed with limited queries. The section also compares the method with other label-only attacks and explores flexible target criteria.

4.1. ImageNet

  • The ImageNet evaluation uses 1,000 validation images with fixed random target labels and runs each attack for up to 15,000 queries.The attacks share starting points found by searching for the nearest target-class image and locating the decision boundary, typically in fewer than 10 queries.Source: §4.1 · pp. 5–6

4.1.2 Comparison to state of the art

  • The biased Boundary Attack outperforms the other evaluated label-only attacks; Ilyas et al. [10] do not succeed within the query range considered.The comparison uses the same data and targets across methods; the table reports the comparison.Source: Table 2 · p. 6, §4.1.2 · pp. 6–7

4.1.1 Ablation study of biases

  • On ImageNet, combining all three biases yields 85% success after 15,000 queries, and the biases can be combined without interfering.Table 1 reports that each bias improves efficiency, with Perlin strongest, followed by mask and surrogate biases.Source: §4.1.1 · p. 6, Table 1 · p. 6

4.1.2 Comparison to state of the art

  • The PGD transfer attack succeeds very early when it works, but fails in most cases; the authors conclude that it needs a stronger surrogate model.The gradient bias uses a pre-trained Inception-Resnet-v2 surrogate that performs poorly in a PGD transfer attack.Source: §4.1 · p. 6, §4.1.2 · p. 7

4.2. Google Cloud Vision API

  • The Google Cloud Vision attack accepts any boolean criterion on model output, allowing target groups such as labels containing “bear” rather than one exact class.The API's exact classes are unknown, and its labels include near-redundant alternatives.Source: §4.2 · p. 7, §4.2.1 · p. 7

4.2.1 Turning a person into a bear

  • After 346 queries, the person-to-bear attack produces a visible perturbation small enough to fool an unsuspecting observer.Its target criterion accepts bear-related labels while excluding output labels referring to a person.Source: §4.2.1 · p. 7

4.2.2 Making pedestrians disappear

  • The pedestrian-removal attack produces an image after 1,000 queries with a perturbation small enough to fool an unsuspecting observer.Its criterion removes “pedestrian” and related labels from the prediction vector.Source: Figure 6 · p. 7, §4.2.2 · p. 8

5. Conclusion

The conclusion frames the Boundary Attack as biased sampling that can use domain knowledge to speed up decision-based black-box attacks. The authors report strong performance and point to additional priors as a path for extending the framework.

5. Conclusion

  • The biased Boundary Attack is a sampling framework in which prior knowledge speeds attacks by modifying the distribution from which samples are drawn.The authors say decision-based black-box attacks can be greatly sped up with prior knowledge.Source: §5 · p. 8
  • Three proposed priors draw on image-classification intuitions and connections to other black-box attack research, but the surrogate-gradient bias alone yields no substantial improvement.The authors identify the small benefit from surrogates with near-zero transferability as promising for future study.Source: §5 · p. 8
  • Other perturbation patterns, spatial transforms, adversarial blending strategies, and target-class semantic intuitions could also be integrated as priors.The authors say these are among the forms of domain knowledge not yet incorporated into adversarial attacks.Source: §5 · p. 8
  • The implementation significantly outperforms prior black-box label-only attacks and can produce convincing results after very few iterations.The authors say the threat of black-box adversarial examples becomes more realistic as a result.Source: §5 · p. 8

A. Evaluation images

The ImageNet examples compare perturbation distances for different combinations of biases and show that their effects vary by image. Combining biases can substantially reduce perturbation norm, although an individual bias can also hurt on a particular example.

A. Evaluation images

  • For the snowplow-to-Chesapeake-Bay-retriever example, the mask bias is especially effective when the start and original images have similar backgrounds.The reported dℓ2 values are 27.10 with no bias, 21.73 with surrogate only, 13.19 with mask only, and 12.40 with mask+surrogate.Source: Figure 7 · p. 10, A. Evaluation images · p. 10
  • For the goose-to-lipstick example, mask+surrogate is slightly worse than surrogate alone, but combining all biases is still significantly better.The reported dℓ2 values are 42.36 with no bias, 40.51 with surrogate only, 42.69 with mask only, and 41.69 with mask+surrogate.Source: Figure 8 · p. 11, A. Evaluation images · p. 11
  • 88%: for the cello-to-black-stork example, all biases reduce perturbation norm versus no bias.The surrogate bias alone is detrimental on this image.Source: Figure 9 · p. 12, A. Evaluation images · p. 12

B.1. Boundary Attack

The Boundary Attack implementation adjusts step sizes to prioritize early query efficiency, while the other attacks use their ImageNet hyperparameters from their public implementations.

B.1. Boundary Attack

  • The attack uses orthogonal and source step sizes of η = 0.05 and ϵ = 0.002, rather than the original implementation's 0.01 for both.These settings take smaller steps toward the source image while allowing more extreme orthogonal perturbations; the authors found that this increases candidate success and reduces stalling.Source: §B.1 · p. 13
  • Because low-query success statistics are noisy and the original adaptation scheme was detrimental below 15,000 queries, the authors use a different step-size strategy.They prioritize making progress in the early stages of an attack over reaching near-zero perturbations.Source: §B.1 · p. 13
  • The strategy counts consecutive unsuccessful candidates, reduces both step sizes as failures accumulate, and resets them after a success or 50 consecutive failures.The 50-failure reset is a fail-safe; the authors report that this occurred often without bias but seldom with the Perlin bias.Source: §B.1 · p. 13
  • After success, step sizes revert immediately to their original values, but this can waste samples beyond 10,000 queries by restoring larger steps too often.The authors suggest partially reinstating the original adaptation method or using step-size annealing as possible alternatives.Source: §B.1 · p. 13

B.2. Other attacks

  • For attacks other than the Boundary Attack, the authors use the ImageNet hyperparameters from each implementation's publicly available source code.Source: §B.2 · p. 13

C. Submission to NeurIPS 2018 Adversarial Vision Challenge

The authors evaluate their attack in the NeurIPS 2018 Adversarial Vision Challenge, a black-box decision-based competition against robust models. Their submission placed second in the targeted attack track.

C. Submission to NeurIPS 2018 Adversarial Vision Challenge

  • The submission won second place in the targeted attack track of the NeurIPS 2018 Adversarial Vision Challenge.The authors present the competition as a way to evaluate attacks against state-of-the-art robust models and defenses.Source: C. Submission to NeurIPS 2018… · p. 14
  • The challenge is an iterative black-box decision-based competition with robust-model, untargeted-attack, and targeted-attack tracks.The robust-model track maximizes the norm of successful perturbations; attack tracks minimize distance, with targeted attacks required to reach a specific label.Source: C. Submission to NeurIPS 2018… · p. 14
  • Each evaluation run uses 200 images at 64x64 resolution, allows 1,000 queries per image, and scores attacks by median ℓ2 perturbation norm across 200 images and the top-five models.Lower scores are better.Source: C. Submission to NeurIPS 2018… · p. 14
  • More than 60 teams competed, and the authors regard the top-five models as a reasonable depiction of state-of-the-art robustness.They report that most winning models used variations of Ensemble Adversarial Training, while most winning attacks used PGD transfer variants with large adversarially trained ensembles.Source: C. Submission to NeurIPS 2018… · p. 14
  • The challenge models use Tiny ImageNet's 200 classes and are evaluated on a secret hold-out set unknown to participants.The dataset has 500 images per class, and model inputs are color images at 64x64 pixels.Source: C. Submission to NeurIPS 2018… · p. 14

C.1. Random guessing with low frequency

Replacing uniform random sampling with normalized Perlin noise made untargeted attacks more efficient and reduced adversarial perturbation distance. The experiment used a 1000-query budget and was limited to untargeted attacks because targeted random guessing seemed too difficult.

C.1. Random guessing with low frequency

  • The experiment compared uniform samples from an ℓ2-hypersphere around the original image with normalized Perlin-noise samples.The Perlin frequency was set to 5 for Tiny ImageNet.Source: §C.1 · p. 14
  • The evaluation used 1000 queries per image and restricted random guessing to the untargeted track, where 199 adversarial labels made random success reasonably likely.Binary search reduced the sampling distance ε whenever an adversarial example was found; the authors said targeted random guessing might be too difficult.Source: §C.1 · p. 14
  • Perlin patterns reduced adversarial perturbation distance by 63% and made the attack more efficient on Tiny ImageNet.The attack also placed in the untargeted track’s top 10.Source: §C.1 · p. 14

C.2. Biased Boundary Attack

In the targeted AVC track, adding Perlin noise and surrogate gradients made the Boundary Attack substantially more efficient than the unbiased baseline. The authors report a 53% reduction in median ℓ2 distance overall, while noting that the AVC entry omitted mask bias because of time constraints.

C.2. Biased Boundary Attack

  • The unbiased Boundary Attack worked but was too slow for the targeted setting, with its starting point still clearly visible after 1000 iterations.Source: §C.2 · p. 14
  • Adding projected gradients from a surrogate model with bias strength w = 0.5 further reduced median ℓ2 distance by another 37%, or 53% total versus the original Boundary Attack; after 1000 iterations, the butterfly was almost invisible.Source: §C.2 · p. 15
  • Perlin bias alone decreased median ℓ2 distance by 25% in the targeted AVC evaluation.The bias replaces the orthogonal-step sampling distribution with Perlin patterns.Source: Table 4 · p. 15, §C.2 · p. 15
  • The AVC submission combined public ResNet18 and ResNet50 baselines, and the authors say it outperformed most submissions while using surrogate models more efficiently than direct transfer attacks.They note this ensemble was stronger than their ImageNet surrogate but weaker than those used by most winning submissions.Source: §C.2 · p. 15
  • The AVC entry did not implement mask bias because of time constraints.Source: §C.2 · p. 15
Loading 1812.09803v3…