GenAttack: Practical Black-box Attacks with Gradient-Free Optimization

Moustafa Alzantot; Yash Sharma; Supriyo Chakraborty; Huan Zhang; Cho-Jui Hsieh; Mani Srivastava

Source-linked AI summary

GenAttack: Practical Black-box Attacks with Gradient-Free Optimization

Moustafa Alzantot, Yash Sharma, Supriyo Chakraborty, Huan Zhang, Cho-Jui Hsieh, Mani Srivastava

arXiv:1805.11090v3May 28, 2018cs.LGcs.AIcs.CRcs.CV

TL;DR

Deep neural networks remain vulnerable to adversarial examples when an attacker has only query access, while existing black-box methods can require many queries. GenAttack uses gradient-free genetic optimization to synthesize targeted adversarial examples, achieving substantially fewer queries across MNIST, CIFAR-10, and ImageNet and attacking selected ImageNet defenses.

Problem
Existing black-box adversarial attacks require significant queries for substitute-network training or gradient estimation despite query-only access.
Method
GenAttack uses population-based genetic algorithms to perform gradient-free black-box optimization without computing or approximating gradients.
Results
GenAttack successfully performed targeted attacks with significantly fewer queries than prior approaches across MNIST, CIFAR-10, and ImageNet models.
Takeaways & Limitations
GenAttack’s gradient-free query efficiency enabled successful attacks against ensemble adversarial training and randomized, non-differentiable ImageNet defenses.
Takeaways & Limitations
The threat model excludes access to hidden-layer values, including logits, and the reported defense results cover selected defenses rather than all defenses.

Abstract

from arXiv · show

Deep neural networks are vulnerable to adversarial examples, even in the black-box setting, where the attacker is restricted solely to query access. Existing black-box approaches to generating adversarial examples typically require a significant number of queries, either for training a substitute network or performing gradient estimation. We introduce GenAttack, a gradient-free optimization technique that uses genetic algorithms for synthesizing adversarial examples in the black-box setting. Our experiments on different datasets (MNIST, CIFAR-10, and ImageNet) show that GenAttack can successfully generate visually imperceptible adversarial examples against state-of-the-art image recognition models with orders of magnitude fewer queries than previous approaches. Against MNIST and CIFAR-10 models, GenAttack required roughly 2,126 and 2,568 times fewer queries respectively, than ZOO, the prior state-of-the-art black-box attack. In order to scale up the attack to large-scale high-dimensional ImageNet models, we perform a series of optimizations that further improve the query efficiency of our attack leading to 237 times fewer queries against the Inception-v3 model than ZOO. Furthermore, we show that GenAttack can successfully attack some state-of-the-art ImageNet defenses, including ensemble adversarial training and non-differentiable or randomized input transformations. Our results suggest that evolutionary algorithms open up a promising area of research into effective black-box attacks.

1 INTRODUCTION

Deep neural networks are vulnerable to adversarial examples, while black-box attacks are constrained to query access and existing approaches can require many queries. GenAttack addresses this setting with gradient-free genetic optimization and achieves substantially lower query counts across image-classification tasks and selected defenses.

Black-box attackers may access only classifier input-output pairs, without the architecture, parameters, or training data.
GenAttack evolves a population of feasible adversarial solutions with genetic algorithms, avoiding gradient computation and approximation.
2,126, 2,568, and 237 times fewer queries were required by GenAttack on MNIST, CIFAR-10, and ImageNet, respectively, than the current state-of-the-art black-box attack.
GenAttack successfully attacked state-of-the-art ImageNet defenses, including ensemble adversarial training and randomized, non-differentiable input transformations.
The paper presents evolutionary algorithms as a promising direction for effective black-box adversarial attacks.

2 RELATED WORK

Prior adversarial-example research includes white-box gradient-based attacks, transfer-based black-box methods, and query-based gradient estimation. These approaches motivate black-box methods such as ZOO, while gradient-manipulating defenses create additional challenges.

White-box attacks use complete model access and backpropagation, whereas black-box attacks rely on input-output access without backpropagation.
Transferability allows adversarial examples generated on one model to be misclassified by another, motivating substitute-model black-box attacks.
ZOO performs black-box optimization with finite-difference gradient estimates, requiring two queries per input coordinate.
536,406 queries are required for one gradient estimate when attacking Inception-v3 on ImageNet with ZOO.
Some defenses manipulate gradients by making them nonexistent, incorrect, random-dependent, or unusable, including non-differentiable input transformations.

3 THREAT MODEL

The threat model gives the attacker query-only access to a classifier and asks for a targeted, perceptually similar adversarial example. The attacker must select a target label while minimizing an Lp distance, commonly L2 or L∞.

The attacker has no knowledge of the network architecture, parameters, or training data and can only query the target model.
The classifier returns prediction scores, but the attacker cannot access hidden-layer values, including logits.
The targeted attack seeks an adversarial example classified as a chosen target label t from the available class labels.
The perturbation minimizes Lp distance to preserve perceptual similarity, with Lp often chosen as L2 or L∞.
This threat model is equivalent to prior black-box attack settings and resembles a chosen-plain-text attack in cryptography.

4 GENATTACK ALGORITHM

GenAttack uses genetic algorithms for gradient-free black-box optimization, evolving feasible candidate populations toward targeted adversarial examples. Dimensionality reduction and adaptive parameter scaling improve query efficiency while preserving the L∞ constraint.

GenAttack Algorithm: GenAttack evolves populations of candidate solutions with fitness-based selection, crossover, mutation, and elitism until a targeted adversarial example is found.The algorithm seeks x_adv classified as target label t while satisfying ||x_orig − x_adv||∞ ≤ δ_max.
Fitness Function: The fitness function jointly rewards increasing the target-class score and decreasing competing-class probabilities, using logarithms to improve numerical stability.
Genetic Operations: Crossover selects each feature from either parent according to fitness-derived probabilities, while mutation adds bounded uniform noise and clipping preserves the permissible L∞ distortion.
Query Efficiency: The algorithm limits population size because high-dimensional search requires larger populations, while evaluating each member increases query costs.
4.1.1 Dimensionality Reduction: GenAttack uses dimensionality reduction by learning lower-dimensional adversarial noise, resizing it bilinearly, and adding it to the original input.The reduced dimension d′ is smaller than the input dimension d, so one noise value can perturb multiple neighboring pixels.
4.1.2 Adaptive Parameter Scaling: Adaptive parameter scaling decreases mutation probability ρ and mutation range α after consecutive plateaus in the elite member’s fitness.The plateau counter increments after 100 consecutive steps without improvement, with minimum values ρ_min = 0.1 and α_min = 0.15.

5 RESULTS

GenAttack is evaluated against state-of-the-art image classifiers and defenses on MNIST, CIFAR-10, and ImageNet. It succeeds in targeted black-box attacks while using substantially fewer queries than ZOO, including large reductions on all three datasets.

Evaluation Setup: Experiments attack state-of-the-art MNIST, CIFAR-10, and ImageNet classifiers, comparing GenAttack with ZOO using attack success rate, runtime, and median queries over successful attacks.Inception-v3 is used for ImageNet, and C&W white-box results provide attack-success perspective.
ImageNet Defenses: GenAttack is also evaluated against ensemble adversarial training and randomized, non-differentiable input-transformation defenses on ImageNet.
Experimental Configuration: ImageNet experiments use a larger query budget and adaptive updates of ρ and α, reflecting the substantially higher dimensionality of the images.The maximum query budget is 1,000,000 for ImageNet versus 100,000 for MNIST and CIFAR-10.
5.1.1 MNIST and CIFAR-10: 2,126 times fewer queries on MNIST and 2,568 times fewer on CIFAR-10 make GenAttack more efficient than ZOO while both attacks succeed.

ImageNet:

On ImageNet, GenAttack scales more effectively than ZOO and its unoptimized genetic baseline, while comparisons with parallel attacks reveal a query–distortion trade-off.

ImageNet results: 237 times more efficient than ZOO, and 9 times more query efficient than the GA baseline on ImageNet.ZOO does not succeed consistently in the targeted case; the GA baseline omits dimensionality reduction and adaptive parameter scaling.
ImageNet results: Table 2 reports attack success rate and median successful-example queries for C&W, ZOO, GenAttack, and the GA baseline at equivalent L∞ distortion.The table compares normally trained InceptionV3 and ensemble adversarially trained Ens4AdvInceptionV3 models.
Comparison with parallel efforts: 25% fewer queries than [14] under the same L∞ distance constraint, at the cost of a slight increase in L2 distance.The comparison uses results at first success and reports both query counts and distortion distances.
Comparison with parallel efforts: 15% less queries than [31], despite [31] having higher distortion in both L∞ and L2 distances.[31] also uses post-processing to reduce distortion, which significantly increases its query cost.

5.2 Attacking Defenses

GenAttack is evaluated against ensemble adversarial training and non-differentiable or randomized input transformations, including JPEG compression and total variance minimization. The experiments show successful attacks under constrained distortions, including 95% success against ensemble adversarial training and 70% success against randomized TVM.

Attacking Ensemble Adversarial Training: GenAttack achieves 95% success against the strongly defended Ens4AdvInceptionV3 model, with only a limited increase in query count.The experiment uses 100 randomly sampled test images and targets, and δmax = 0.05.
Attacking Non-Differentiable, Randomized Input Transformations: GenAttack bypasses bit-depth reduction, JPEG compression, and total variance minimization in the black-box setting.The paper attributes this capability to gradient-free, multi-modal, population-based optimization.
Attacking Non-Differentiable, Randomized Input Transformations: High success rates are achieved against non-differentiable transformations on both CIFAR-10 and ImageNet, including JPEG compression with quality level 75.Figure 4 presents a visual example against JPEG compression at L∞ = 0.15.
Attacking Non-Differentiable, Randomized Input Transformations: TVM randomly drops 50% of pixels and reconstructs the image through denoising, while its slow processing and randomized scores increase attack difficulty.The defense also lowers clean-input accuracy from 80% to 40% unless the model is retrained with transformed examples.
Attacking Non-Differentiable, Randomized Input Transformations: 70% success is achieved against randomized TVM at L∞ = 0.15, using 32 queries per population member to estimate robust fitness.An adversarial example counts as successful only when classified as the target label three times consecutively.

Comparison to ZOO and C&W:.

GenAttack succeeds where gradient-based C&W cannot directly operate on non-differentiable transformations, while ZOO achieves only limited success against these defenses on ImageNet.

Comparison to ZOO and C&W: ZOO achieves 8% and 0% success against ImageNet bit-depth reduction and JPEG compression defenses, respectively.C&W cannot succeed without manipulating the non-differentiable component, which is not applicable in the black-box setting.

5.3 Hyper-parameters values selection

Because genetic algorithms are sensitive to hyper-parameter choices, the paper examines their effect on query efficiency to select values for evaluation.

Hyper-parameters values selection: Hyper-parameter selection is studied in terms of query efficiency because genetic algorithms are sensitive to population and mutation-rate choices.The analysis informs the hyper-parameter values used in Section 5.

Population size:

Population size trades off exploration and convergence speed against total query cost. The experiments identify six as a reasonable balance, while adaptive mutation improves performance over fixed rates.

Population size: Larger populations improve search-space exploration within fewer iterations but increase queries because each population member requires one query.Figure 5 measures mean queries and iterations to success across population sizes on 20 images.
Population size: A population size of six balances convergence speed and total query count.This value is selected from the population-size experiment.
Mutation probability: Adaptive mutation rates outperform fixed rates by encouraging exploration initially and increasing exploitation near convergence.The mutation probability is gradually decayed according to equations in Section 4.

6 CONCLUSION

GenAttack is presented as an efficient gradient-free black-box attack using genetic algorithms. It succeeds against image-classification models and several state-of-the-art ImageNet defenses, including randomized transformations.

GenAttack uses a population-based genetic algorithm for gradient-free black-box optimization.
GenAttack successfully performs targeted black-box attacks on MNIST, CIFAR-10, and ImageNet models with fewer queries than previous state-of-the-art methods.
GenAttack succeeds against ensemble adversarial training, non-differentiable transformations, and randomized transformations by generalizing its fitness function to an expectation over transformations.