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