Gaussian MRF Covariance Modeling for Efficient Black-Box Adversarial Attacks
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. We employ Markov Random Fields (MRF) to exploit the structure of input data to systematically model the covariance structure of the gradients. The MRF structure in addition to Bayesian inference for the gradients facilitates one-step attacks akin to Fast Gradient Sign Method (FGSM) albeit in the black-box setting. The resulting method uses fewer queries than the current state of the art to achieve comparable performance. In particular, in the regime of lower query budgets, we show that our method is particularly effective in terms of fewer average queries with high attack accuracy while employing one-step attacks.
This paper deals with the problem of finding an adversarial examples when only the output of a model can be evaluated, but not its gradient. The key idea of the paper is building a Gaussian MRF (a Gaussian with a sparse inverse covariance matrix with a special band structure) to maintain a model for the gradients for predicting search directions. The approach is sensible and uses the FFT trick applicable for diagonalizing covariance matrices with circulant structure. - The ideas in this paper have practical utility. The paper is unfortunately not very carefully written, and the arguments require occasionally some guesswork. - There is not a sufficient discussion of experimental findings. Why does the proposed method works better than a white box FGSM for instance? - I don’t fully understand what ‘solving for GMRF’ means (Alg 1). I would expect it is estimating the parameters of the covariance function but this algorithm just calculates the likelihood. - Given the simple coupling structure with parameter tying, this problem seems to be closely related to estimating AR(N) style models (alpha and beta parameters) so I am surprised to see only a general treatment. In this problem, it seems much more natural to estimate theta and g recursively and concurrently, and there are very well known algorithms related to Kalman filtering. Please discuss. - The evaluation of the idea is not complete While it is certainly interesting to see that such a simple heuristic can achieve comparable performance on standard datasets over other black-box attack methods in the limited query budget regime, I would expect to see some experiments that illustrate the quality of the gradient estimator more closely (not only its final effectiveness for finding a search direction inside of an optimization method) and more strong justification of the proposed model. - As the entire contribution hinges on the observation that gradients across dimensions of an example as well as across examples in a dataset are correlated, it would have been also very informative to show estimates of autocorrelation functions of the gradients on different datasets to justify the basic modelling choices.
You are a member of the scientific community tasked with peer review. Review the following paper title and abstract.
### Title + Abstract
Gaussian MRF Covariance Modeling for Efficient Black-Box Adversarial Attacks
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. We employ Markov Random Fields (MRF) to exploit the structure of input data to systematically model the covariance structure of the gradients. The MRF structure in addition to Bayesian inference for the gradients facilitates one-step attacks akin to Fast Gradient Sign Method (FGSM) albeit in the black-box setting. The resulting method uses fewer queries than the current state of the art to achieve comparable performance. In particular, in the regime of lower query budgets, we show that our method is particularly effective in terms of fewer average queries with high attack accuracy while employing one-step attacks.
user
<think>Okay, to do a decent peer review, I should start with summarizing what the work is about. This includes novelty, contributions, clarity, and impact. I might include suggestions to issues that I find critical to the usefulness of the work. Starting with novelty, there are different types of novelty. The first aspect of novelty is scope and scale. Is the work covering a broader perspective than previous works? The second aspect is methodology. Is the proposed methodology novel compared to previous methods? Do they provide any significant advantage over previous methodologies? The third aspect is results. Are the results different compared previous work? Does this lead to any novel theories or an extension of current theories? Next is clarity, I will be reading the work in depth and analyze if any sentences can be potentially ambiguous or misleading. If any sentences are ambiguous, I will state them and give a suggestion on how to rephrase such sentence or how to make more clear to the audience. Lastly, impact is important. I will attempt to predict how such work will impact the scientific community. This might include the applications of such work and how the work might transform the way we study a certain topic. Finally, I will might only mention issues that are critical. This is to keep the review as concise and helpful as possible.</think>



This paper deals with the problem of finding an adversarial examples when only the output of a model can be evaluated, but not its gradient. The key idea of the paper is building a Gaussian MRF (a Gaussian with a sparse inverse covariance matrix with a special band structure) to maintain a model for the gradients for predicting search directions. The approach is sensible and uses the FFT trick applicable for diagonalizing covariance matrices with circulant structure. - The ideas in this paper have practical utility. The paper is unfortunately not very carefully written, and the arguments require occasionally some guesswork. - There is not a sufficient discussion of experimental findings. Why does the proposed method works better than a white box FGSM for instance? - I don’t fully understand what ‘solving for GMRF’ means (Alg 1). I would expect it is estimating the parameters of the covariance function but this algorithm just calculates the likelihood. - Given the simple coupling structure with parameter tying, this problem seems to be closely related to estimating AR(N) style models (alpha and beta parameters) so I am surprised to see only a general treatment. In this problem, it seems much more natural to estimate theta and g recursively and concurrently, and there are very well known algorithms related to Kalman filtering. Please discuss. - The evaluation of the idea is not complete While it is certainly interesting to see that such a simple heuristic can achieve comparable performance on standard datasets over other black-box attack methods in the limited query budget regime, I would expect to see some experiments that illustrate the quality of the gradient estimator more closely (not only its final effectiveness for finding a search direction inside of an optimization method) and more strong justification of the proposed model. - As the entire contribution hinges on the observation that gradients across dimensions of an example as well as across examples in a dataset are correlated, it would have been also very informative to show estimates of autocorrelation functions of the gradients on different datasets to justify the basic modelling choices.
assistant
This paper deals with the problem of finding an adversarial examples when only the output of a model can be evaluated, but not its gradient. The key idea of the paper is building a Gaussian MRF (a Gaussian with a sparse inverse covariance matrix with a special band structure) to maintain a model for the gradients for predicting search directions. The approach is sensible and uses the FFT trick applicable for diagonalizing covariance matrices with circulant structure. - The ideas in this paper have practical utility. The paper is unfortunately not very carefully written, and the arguments require occasionally some guesswork. - There is not a sufficient discussion of experimental findings. Why does the proposed method works better than a white box FGSM for instance? - I don’t fully understand what ‘solving for GMRF’ means (Alg 1). I would expect it is estimating the parameters of the covariance function but this algorithm just calculates the likelihood. - Given the simple coupling structure with parameter tying, this problem seems to be closely related to estimating AR(N) style models (alpha and beta parameters) so I am surprised to see only a general treatment. In this problem, it seems much more natural to estimate theta and g recursively and concurrently, and there are very well known algorithms related to Kalman filtering. Please discuss. - The evaluation of the idea is not complete While it is certainly interesting to see that such a simple heuristic can achieve comparable performance on standard datasets over other black-box attack methods in the limited query budget regime, I would expect to see some experiments that illustrate the quality of the gradient estimator more closely (not only its final effectiveness for finding a search direction inside of an optimization method) and more strong justification of the proposed model. - As the entire contribution hinges on the observation that gradients across dimensions of an example as well as across examples in a dataset are correlated, it would have been also very informative to show estimates of autocorrelation functions of the gradients on different datasets to justify the basic modelling choices.