Black-box adversarial sample generation based on differential evolution

Junyu Lin, Lei Xu, Yingqi Liu, Xiangyu Zhang

TL;DR

This paper introduces BMI-FGSM, a novel black-box attack that generates adversarial samples by using Differential Evolution to "guess" the gradients of a neural network. By combining evolutionary search with momentum-based iterative methods, the authors achieve high success rates and better transferability than previous black-box techniques while remaining significantly faster than state-of-the-art optimization-based attacks.

What Problem Does This Paper Address?

Deep Neural Networks (DNNs) are notoriously fragile; tiny, imperceptible changes to an input (adversarial perturbations) can trick a model into confident misclassification. Most powerful attacks are "white-box," meaning the attacker has full access to the model's internal architecture and gradients.

Examples of original images, the generated perturbations, and the resulting adversarial examples.

In the real world, however, attackers usually face a "black box"—an API like Google Cloud or Alibaba Aliyun where you can only see the output for a given input. Generating adversarial samples in this setting is difficult because you can't calculate gradients directly. Existing black-box methods are often either incredibly slow (requiring thousands of queries) or struggle to produce "transferable" samples that work across different models. This paper seeks a middle ground: an efficient, query-limited attack that doesn't need internal model access.

Methods

The authors propose the Black-box Momentum Iterative Fast Gradient Sign Method (BMI-FGSM). The core idea is to treat the search for a gradient as an evolutionary problem rather than a calculus problem.

The iterative gradient-based method utilizing differential evolution to estimate gradient signs.
  1. Differential Evolution (DE): Instead of backpropagation, the algorithm maintains a "population" of potential gradient signs. These candidates evolve over generations through mutation and crossover. The "fitness" of a candidate is determined by how much it increases the model's loss (i.e., how much it confuses the model).
  2. Momentum via Candidate Reuse: In white-box attacks, "momentum" helps stabilize the search. In a black-box setting, simply accumulating gradients leads to error buildup. BMI-FGSM solves this by keeping the best-performing candidates from the previous iteration and using them to seed the next population, effectively carrying over "directional knowledge."
  3. Double Step Size: The authors found that using the same step size for searching and for actually perturbing the image leads to getting stuck in local optima. They use a larger step size ($\alpha$) for exploration (finding the gradient direction) and a smaller, permanent step size ($\beta$) for the actual attack.

Datasets

The method was evaluated on three standard benchmarks:

  • MNIST: Handwritten digits (60,000 images).
  • CIFAR10: Small color images across 10 classes (60,000 images).
  • ImageNet: Large-scale dataset used to test the algorithm's scalability on complex, high-dimensional inputs.
  • Real-world API: The authors also tested their method against the commercial Aliyun Image Recognition API to demonstrate practical feasibility.

Key Insights and Ideas

  • Sign over Magnitude: The paper reinforces the idea that you don't need the exact gradient value to break a model; knowing the sign (the direction) of the gradient is often sufficient.
  • Evolution as a Gradient Proxy: Differential Evolution is particularly well-suited here because it is "derivative-free." It can handle the noisy, non-continuous landscapes of black-box APIs where traditional optimization might fail.
  • The Efficiency-Transferability Trade-off: Optimization-based black-box attacks (like ZOO) often overfit to the specific target model, making the samples less likely to fool a different model. By using a momentum-based approach, BMI-FGSM generates samples that are more "general" and thus more transferable.

Key Results

  • Success Rates: On MNIST and CIFAR10, BMI-FGSM achieved a 100% success rate for untargeted attacks and over 95% for targeted attacks.
  • Speed: BMI-FGSM is significantly faster than ZOO (a leading optimization attack). For example, on MNIST, it generated samples in 16.7 seconds compared to ZOO's 68.4 seconds.
  • ImageNet Performance: On the much harder ImageNet dataset, the "Double Step Size" and "Candidate Reuse" were critical. Without them, success rates dropped significantly (from 98.6% to 70.3% or even 0%).
  • Real-world Impact: The attack successfully triggered misclassifications on the Aliyun API with a 92% success rate within a budget of 5,000 queries. For instance, a "Cleaver" was misidentified as a "Sundial" with 55% confidence.

Limitations and Future Work

  • Query Budget: While more efficient than some predecessors, the method still requires multiple queries to the target model per iteration. In highly restricted or expensive API environments, this could still be a barrier.
  • Defense Sensitivity: The paper primarily tests against undefended models. The authors note that future work should involve testing BMI-FGSM against models specifically trained with adversarial defenses (like adversarial training).
  • Cross-Domain Application: The current work is focused on image classification. The authors suggest exploring how these evolutionary black-box techniques might apply to other domains, such as natural language processing or speech recognition.

Summary updated

BibTeX
@article{lin2020black,
  author = {Junyu Lin and Lei Xu and Yingqi Liu and Xiangyu Zhang},
  title = {{Black-box adversarial sample generation based on differential evolution}},
  journal = {J. Syst. Softw.},
  year = {2020},
  doi = {10.1016/j.jss.2020.110767},
}
Figure