Towards Query-Efficient Black-Box Adversary with Zeroth-Order Natural Gradient Descent

Siyue Wang, Pu Zhao

TL;DR

This paper introduces ZO-NGD, a novel black-box adversarial attack method that significantly reduces the number of queries needed to fool deep neural networks. By combining zeroth-order gradient estimation with second-order natural gradient descent, ZO-NGD achieves higher query efficiency, making it more practical for real-world scenarios where model access is limited.

What Problem Does This Paper Address?

Deep neural networks (DNNs) have achieved remarkable success in various fields, but they are notoriously vulnerable to adversarial attacks. These attacks involve making subtle, imperceptible modifications to input data (like images) that can cause DNNs to misclassify them. While white-box attacks, which assume full knowledge of the model, are well-studied, they are often impractical. Black-box attacks, where the attacker can only query the model and observe its outputs, are more realistic. However, existing black-box methods often require a large number of queries, which can be costly, time-consuming, and easily detectable. This paper addresses the challenge of developing query-efficient black-box adversarial attacks that can effectively fool DNNs with minimal interaction.

Methods

The core innovation of this paper is the Zeroth-Order Natural Gradient Descent (ZO-NGD) method. It tackles the black-box constraint by:

  • Zeroth-Order Gradient Estimation: Since the attacker doesn't have direct access to the model's gradients, ZO-NGD uses a technique called zeroth-order optimization. This involves making multiple queries with slightly perturbed inputs to estimate the gradient of the loss function. This is a standard approach in black-box settings, but ZO-NGD cleverly extracts additional information during these queries.
  • Second-Order Natural Gradient Descent (NGD): Instead of just using the estimated first-order gradient (like many existing methods), ZO-NGD incorporates second-order information. Specifically, it uses the Fisher Information Matrix (FIM) to rescale the gradient. NGD is known for its faster convergence compared to standard gradient descent, especially in probabilistic models.
  • Co-optimization: The key insight is that the process of estimating the loss function's gradient (zeroth-order) can also be used to estimate components of the FIM without requiring additional queries. This "free" extraction of second-order information is crucial for query efficiency.
  • Scalability: To handle the high dimensionality of FIM in large datasets like ImageNet, the paper proposes an efficient approximation method that avoids direct computation and inversion of the full FIM, keeping the computational complexity manageable.
  • Damping: A damping technique is applied to the FIM to stabilize the training process and prevent overly large updates, which is a common practice in NGD.

Datasets

The paper evaluates ZO-NGD on the following image classification datasets:

  • MNIST: A dataset of handwritten digits.
  • CIFAR-10: A dataset of 10 common object classes.
  • ImageNet: A large-scale dataset of diverse images.

The authors used pre-trained models for ImageNet (Inception v3) and trained their own models for MNIST and CIFAR-10.

Key Insights and Ideas

  • Leveraging Second-Order Information for Black-Box Attacks: The paper demonstrates that incorporating second-order information (via NGD and FIM) can significantly improve the query efficiency of black-box adversarial attacks, a domain traditionally dominated by first-order methods.
  • Query Efficiency through Information Co-extraction: The most significant insight is the ability to estimate the Fisher Information Matrix (FIM) as a byproduct of the zeroth-order gradient estimation process, thus avoiding extra queries and making the attack more stealthy and cost-effective.
  • Natural Gradient's Geometric Interpretation: The paper highlights that natural gradient descent operates in the "distribution space" rather than the parameter space, making it invariant to model reparameterization and potentially more robust.
  • Practicality of Black-Box Attacks: By significantly reducing query counts, ZO-NGD makes black-box adversarial attacks more feasible in real-world scenarios where direct model access is restricted (e.g., cloud-based APIs).

Key Results

  • Significant Query Reduction: ZO-NGD consistently achieved a much lower number of queries compared to state-of-the-art black-box attack methods like NES-PGD and ZOO. For example, on MNIST, ZO-NGD required 523 queries compared to 1,243 for NES-PGD. On ImageNet, it achieved a query reduction of up to 96.5% compared to NES-PGD.
  • High Success Rates: Despite the reduced query count, ZO-NGD maintained high success rates in generating adversarial examples, often comparable to or exceeding other methods. For instance, it achieved a 98.7% success rate on MNIST and 97% on ImageNet.
  • Robustness to Model Architectures: The method showed consistent performance across different model architectures (VGG16, ResNet) and datasets.
  • Transferability: Adversarial examples generated by ZO-NGD demonstrated good transferability to other models (ResNet and VGG16), achieving high attack success rates even when attacking different architectures.

Limitations and Future Work

  • Parameter Sensitivity: While the method is generally robust, the paper notes that the choice of hyperparameters like $\mu$ and $\epsilon$ can influence query efficiency, with larger $\epsilon$ generally leading to fewer queries. The parameter $\gamma$ for damping also plays a role.
  • Approximation of FIM: The paper uses the outer product approximation for the FIM. While empirically shown to be effective, it's still an approximation.
  • Future Work: The authors suggest that the ZO-NGD method can be easily adapted to white-box settings by using exact gradients, potentially leading to even higher query efficiency. Further exploration of its application to other domains beyond image classification is also a natural extension.

Summary updated

Abstract

Despite the great achievements of the modern deep neural networks (DNNs), the vulnerability/robustness of state-of-the-art DNNs raises security concerns in many application domains requiring high reliability. Various adversarial attacks are proposed to sabotage the learning performance of DNN models. Among those, the black-box adversarial attack methods have received special attentions owing to their practicality and simplicity. Black-box attacks usually prefer less queries in order to maintain stealthy and low costs. However, most of the current black-box attack methods adopt the first-order gradient descent method, which may come with certain deficiencies such as relatively slow convergence and high sensitivity to hyper-parameter settings. In this paper, we propose a zeroth-order natural gradient descent (ZO-NGD) method to design the adversarial attacks, which incorporates the zeroth-order gradient estimation technique catering to the black-box attack scenario and the second-order natural gradient descent to achieve higher query efficiency. The empirical evaluations on image classification datasets demonstrate that ZO-NGD can obtain significantly lower model query complexities compared with state-of-the-art attack methods.
BibTeX
@inproceedings{wang2020towards,
  author = {Siyue Wang and Pu Zhao},
  title = {{Towards Query-Efficient Black-Box Adversary with Zeroth-Order Natural Gradient Descent}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i04.6173},
}
Figure