Gaussian MRF Covariance Modeling for Efficient Black-Box Adversarial Attacks

Anit Kumar Sahu, Satya Narayan Shukla, J. Zico KolterarXiv 2020 · OpenReview

Abstract

We study the problem of generating adversarial examples in a black-box setting, where we only have access to a zeroth order oracle, providing us with loss function evaluations. Although this setting has been investigated in previous work, most past approaches using zeroth order optimization implicitly assume that the gradients of the loss function with respect to the input images are unstructured. In this work, we show that in fact substantial correlations exist within these gradients, and we propose to capture these correlations via a Gaussian Markov random field (GMRF). Given the intractability of the explicit covariance structure of the MRF, we show that the covariance structure can be efficiently represented using the Fast Fourier Transform (FFT), along with low-rank updates to perform exact posterior estimation under this model. We use this modeling technique to find fast one-step adversarial attacks, akin to a black-box version of the Fast Gradient Sign Method (FGSM), and show that the method uses fewer queries and achieves higher attack success rates than the current state of the art. We also highlight the general applicability of this gradient modeling setup.

Introduction

Adversarial attacks involve making tiny, invisible changes to an image to trick a machine learning model. In a white-box setting, the attacker has access to the model's internal parameters and can calculate exact gradients. However, in a black-box setting, the attacker is blind and must guess perturbations based on model outputs. The primary challenge in black-box attacks is query efficiency: most methods treat every pixel as independent, requiring thousands of queries to find a successful perturbation. This paper introduces a mathematically rigorous way to exploit the spatial structure of image gradients to find attacks significantly faster.

Methods: Modeling Gradients with GMRFs

The authors propose modeling the gradient of the loss function as a Gaussian Markov Random Field (GMRF). This approach is built on three key pillars:

  1. Gradient Correlation: Gradients in deep networks are not random noise; they are highly correlated spatially. If changing pixel A increases the loss, changing the neighboring pixel B likely will too. Visualizing the autocorrelation of gradients confirms a consistent spatial "texture" to model failures.
  2. The GMRF Prior: The gradient $g$ is modeled with a prior distribution $g \sim \mathcal{N}(0, \Sigma)$. Instead of an identity matrix, an inverse covariance matrix (precision matrix) encodes these neighbor relationships.
  3. FFT Acceleration: Calculating these relationships for high-resolution images is computationally prohibitive. However, because the GMRF structure acts like a convolution, the authors use the Fast Fourier Transform (FFT) to diagonalize the matrix, reducing complexity to $O(N^2 \log N)$ and making it feasible for datasets like ImageNet.
Visualization of gradient spatial correlations, demonstrating the structured 'texture' of model failures.

Using this model, the authors created BB-FGSM (Black-Box Fast Gradient Sign Method), which estimates the gradient's posterior mean using a small number of queries and takes a single step in that direction.

Key Results

The proposed method was evaluated on MNIST and ImageNet against models like VGG16-bn, ResNet50, and Inception-v3.

Query Efficiency

BB-FGSM consistently outperformed existing methods like NES and BANDITS-TD, especially under low query budgets. On ImageNet (VGG16-bn), the proposed method required only ~57 queries on average to succeed, compared to 141 queries for BANDITS-TD and 452 queries for NES.

Success Rates

With a budget of 1,000 queries, the method achieved a 95.17% success rate on VGG16 and 92.01% on ResNet50. The GMRF modeling proves most dominant in the low-query regime (200–400 queries), as it extracts more directional information from every single query than unstructured methods.

Attack success rate vs. query budget across different perturbation levels (epsilon). The GMRF-based method significantly outperforms baselines in low-query regimes.

Insights and Limitations

  • Regularization: In some MNIST tests, the black-box method achieved higher accuracy than white-box FGSM because the GMRF acts as a regularizer, finding a "cleaner" attack direction than the raw, noisy gradient.
  • Frequency Sensitivity: Perturbing images using low-frequency FFT basis vectors (smooth changes) is more effective than high-frequency noise.
  • Limitations: The method requires an offline phase to estimate GMRF parameters for a specific model. Additionally, it is currently a one-step attack; integrating GMRF estimation into iterative multi-step attacks (like PGD) remains a promising area for future research.

Conclusion

By moving away from the assumption of unstructured gradients and adopting a GMRF-based spatial prior, this work provides a principled framework for highly query-efficient black-box adversarial attacks. The use of FFT-based acceleration ensures the method scales to modern, high-resolution computer vision tasks.

Summary updated

Abstract

We study the problem of generating adversarial examples in a black-box setting, where we only have access to a zeroth order oracle, providing us with loss function evaluations. Although this setting has been investigated in previous work, most past approaches using zeroth order optimization implicitly assume that the gradients of the loss function with respect to the input images are \emph{unstructured}. In this work, we show that in fact substantial correlations exist within these gradients, and we propose to capture these correlations via a Gaussian Markov random field (GMRF). Given the intractability of the explicit covariance structure of the MRF, we show that the covariance structure can be efficiently represented using the Fast Fourier Transform (FFT), along with low-rank updates to perform exact posterior estimation under this model. We use this modeling technique to find fast one-step adversarial attacks, akin to a black-box version of the Fast Gradient Sign Method~(FGSM), and show that the method uses fewer queries and achieves higher attack success rates than the current state of the art. We also highlight the general applicability of this gradient modeling setup.
BibTeX
@misc{sahu2020gaussian,
  author = {Anit Kumar Sahu and Satya Narayan Shukla and J. Zico Kolter},
  title = {{Gaussian MRF Covariance Modeling for Efficient Black-Box Adversarial Attacks}},
  year = {2020},
  eprint = {2010.04205},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2010.04205},
}
Figure