Gaussian MRF Covariance Modeling for Efficient Black-Box Adversarial Attacks
Authors: Anit Kumar Sahu
J. Zico Kolter
Satya Narayan Shukla
Venue:  (2020)
Keywords: Black-Box Adversarial Attacks
Gaussian Markov Random Fields

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. 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.

Under review as a conference paper at ICLR 2020
GAUSSIAN MRF COVARIANCE MODELING FOR EFFI- CIENT FLACK-BOX ADVERSARIAL ATTACKS
Anonymous authors Paper under double-blind review
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. We employ Markov Random Fields (MRF) to exploit the structure of input data 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 the art to achieve comparable performance. In particular, in the regime of lower query budgets, show that method is particularly effective in terms of fewer average queries with high attack accuracy while employing one-step attacks.
INTRODUCTION
Most methods for adversarial attacks on deep learning models operate in the so-called white-box setting (Goodfellow et al. 2014), where the model being attacked, and its gradients, are assumed to be fully known. Recently, however there has also been considerable attention given to the black-box setting as well, where the model is unknown and can only be queried by a user, and which much better captures the "typical" state by which an attack can interact with model (Chen et al., [217]] Tu et al. 2019 Tyas et al. 2019 Moon et al. 2019). And several past methods in this area have conclusively demonstrated that, given sufficient number of queries, it is possible to achieve similarly effective attacks in the -bx setting akin to the white-box setting. However, as has also been demonstrated by past work Πlyas et al. (2019) 2018), the efficiency of these black-box attacks (the number of queries need to find an adversarial example) is fundamentally limited unless they can exploit the spatial correlation structure inherent in the model's gradients. Yet, at the same time, most previous methods have used rather ad-hoc methods of modeling such correlation structure, such as using "tillng" bases and priors over time Ilyas et al.] (2019) that require attack vectors be constant over large regions, or by other means such as using smoothly-varying perturbations Myas al. (2018) to estimate these gradients.
In this work, we present new, more rigorous approach to model the correlation structure of the gradients within the black-box adversarial setting. In particular, we propose to model the gradient of the model loss function with respect to the input image using a Gaussian Markov Random Field (GMRF). This approach offers a number of advantages over prior methods: 1) it naturally captures the spatial correlation observed empirically in most deep learning models; 2) using the model, we are able to compute exact posterior estimates over the true gradient given observed data, while also fitting the parameters of the GMRF itself via an expectation maximization (EM) approach; and 3) the method provides a natural alternative uniformly sampling perturbations, based upon the eigenvectors of the covariance matrix. Although representing the joint covariance over the entire input image may seem intractable for large-scale images, we can efficiently compute necessary terms for very general forms of grid-based GMRFs using the Fast Fourier Transform (FFT).
We evaluate our approuch by attempting to find adversarial examples, over multiple different data sets and model architectures, using the GMRF combined with very simple greedy zeroth order search technique; the method effectively forms a "black-box" version of the fast gradient sign method (FGSM), by constructing an estimate of the gradient at the input image itself, then taking single signed step in this direction. Despite its simplicity, we show that owing to the correlation structure provided by the GMRF model, the approach outperforms more complex approaches such as the BANDITS-TU TD (Ilyas et al. 2019) or PARSIMONIOUS (Moon et al. 2019) methods (the current state of the art in black-box attacks), especially for small query budgets.

---

Under review as a conference paper at ICLR 2020
2 RELATED WORK
Black-box adversarial attacks can be broadly categorized across a few different dimensions: optimization- based versus transfer-based attacks, and score-based versus decision-based attacks.
In the aptimization-basel adversarial setting, the adversarial attack is formulated as the problem of maximizing some loss function (c.g., the accuracy of the classifier or some continuous variant) using a zeroth order oracle, i.e., by making queries to the classifier. And within this optimization setting, there is an important distinction between score-based attacks, which directly observe traditional model loss, class probability, or other continuous output of the classifier on a given example, versus decision-based attacks, which only observe the hard label predicted by the classifier. Decision based attacks have been studied by |renddl et al. (2017): Chen et al. (2019 2017), and (not surprisingly) typically require more queries to the classifier than the score-based setting.
In the regime of score-based attacks, the first such iterative attack on class of binary classifiers was first studied by Nelson al.] (2012). A real-world application of black-box attacks to fool a PDF malware classitier was demonstrated by (Xu et al.) 2016). for which a genetic algorithm was used. Narodytska & Kasiviswanathan (2017) demonstrated the first black-box attack on deep neural networks. Subsequently black-box attacks based on zeroth order optimization schemes, using tech- niques such as KWSA (Kiefer et al. 1952) and RDSA (Nesterov & &Sookoiny| (0177) were developed in Chen et al. (201)); [yya et al. (2018). Though Chen et al. (2017) generated successful attacks attainin high attack accuracy, the method was found to be extremely query hungry which was then remedied to an extent by (Ilyas et al. 2018). In [lyas et al. (2019), the authors exploit correlation of gradients across iterations by setting prior and use a piece wise constant perturbation, i.e., tiling to develop a query efficient black-box method. Recently [Moon et al. (2019) used a combinatorial optimization perspective to address the black-box adversarial attack problem.
A concurrent line of work Paperno et al.] (2017) has considered the transfer-based setting, rather than the optimization setting. These approaches create adversarial attacks by training a surrogate network with the aim to mimic the target model's decisions, which are then obtained through black- box queries. With the substitute model in place, the attack method then uses white-box attack strategies in order to transfer the attacks to the original target model. However, substitute network based attack strategies have been found to have higher query complexity than those based on gradient estimation.
The exploitation of the structure of the input data space so as to append a regularizer has been recently found to be effective for robust learning. In particular, in [Lin al. (2019) showed that by using Wasserstein-2 geometry to capture semantically meaningful neighborhoods in the space of images helps to learn discriminative models that are robust to in-class variations of the input data.
Setting of this work In this paper, we are specifically focused on the optimization basee, score- based setting, following most directly upon the work of (Chen et al. [0117] [lyas et al.) (2018) 2019 Moon et al. 2019). However, our contribution is also largely orthogonal to the methods presented in these prior works. Specifically, we show that by modeling the covariance structure of the gradient using a Gaussian MRF, a very simple approach (which largely mirrors the simple black box search from (Ilyas et al. 2018)) achieves performance that is competitive than the best current methods, especially when using relatively few queries. We further emphasize that while we focus on this simple search strategy here, nothing would prevent this GMRF approach from being applied to other black-box search strategies as well.
ADVERSARIAL ATTACKS
In the context of classifiers, adversarial examples are carefully crafted inputs to the classifier which have been perturbed by an additive perturbation so as to cause the classifier to misclassify the input. In particular, so as to ensure minimal visual distortion, the perturbation is subjected to a constraint in terms of its magnitude typically pre-specified in terms of np-norm, for some fixed p. less than some cp. Furthermore in the context of classifiers, attacks can be further classified into targeted or untargeted attacks. For simplicity and brevity, in this paper, we restrict our attention to untargeted attacks.
Formally, define a classifier C: X + y with corresponding classification loss function T(xx, y), where x E X' is the input to the classifier, y E V, X' is the set of inputs and y is the set of labels. Technically speaking, the objective of generating misclassified example can be posed as
2

---

Under review as a conference paper at ICLR 2020
an optimization problem. In particular, the aim is to generate adversarial example x' for given input x which maximizes L(x'.)) y) but still remains cy-lose terms of specified metric, to the original input. Thus, the generation of an adversarial attack can be formalized as a constrained optimization as follows:
x
arg L(x'w))
(1)
x' p Stt
We give a brief overview of adversarial attacks categorized in terms of access to information namely, white-box and black-box attacks.
3.1 WHITE-BOX ADVERSARIAL ATTACKS
White-box settings assume access to the entire classifier and the analytical form of the possibly non- convex classifier loss function. White-box methods can be further categorized into single iteration and multiple iterations based methods. In the class of single iteration white-box methods, the Fast Gradient Sign Method (FGSM) has been very successful, which computes the adversarial input in the following way:
= Epsign (VL(x, y))
(2)
FGSM is however limited to generation of Lo based bounded adversarial inputs. Given, a constrained optimization problem at hand with access to first order oracle, the most effective method is projected gradient descent (PGD). This multi iteration method generates the adversarial input X5 by performing iterations with Xo x, where is specified apriori. In particular, at the 1-th iteration, PGD generates the perturbed input x; as follows:
X IlB,(x..) (xt-1 + vpsi)
with St (0.1, 1x
(3)
where Iy denotes the projection onto the set S, Bp .²) is the f, ball of radius s centered at x', y denotes the step size, and aU the boundary a set U. By making, St to be the projection the gradient V v,L(x=11: y) at æ onto the unit E, ball, it is ensured that s; is the unit é,- norm vector that has the largest inner product with V=I(xi11, the normalized gradient, while for p = oc, the projection corresponds to the sign of the gradient. Moreover, due the projection at each iteration, the adversarial input generated at every iteration conforms the specified constraint.
When p 2, the projection corresponds to
However, in most real world deployments, it is impractical to assume complete access to the clas- sifier and analytic form of the corresponding loss function, which makes black-box settings more realistic.
3.2 BLACK-BOX ADVERSARIAL ATTACKS
In a typical black-box setting, the adversary has only access to a zeroth order oracle, which when queried for an input (x, y). yields the value of the loss function L(x, y). In spite of the information constraints and typically high dimensional inputs, black-box attacks have been shown be pretty
effective (Ilyas et al. 2019 2018 Moon et al. 2019).
The main building block of black-box methods is finite difference schemes as to estimate gradients. Two of the most widely finite difference schemes are the Kiefer-Wolfowit Stochas- tic Approximation (KWSA Kiefer et al. (1952) and Random Directions Stochastic Approxima- tion (RDSA)(Nesteroy & Spokoiny| 2017 KWSA operates as follows:
@ (x = Σ ek (L(x + dex, v) - I(x, /8
Σ e Vz A=1
where ej, ei...., Cd are canonical basis vectors. The estimator can be further extended to higher order finite difference operators, but in the face of possibly non-smooth loss functions do not improve the accuracy of the estimator at the cost of additional queries. Hence, the first or the second order finite difference operators have been proven to be extremely effective. Though KWSA yields reasonably accurate gradient estimates, it is prohibitively query hungry. For instance, for Inception classifier for ImageNet, for every gradient estimate KWSA would require 299 299 x 3 queries. RDSA provides a better alternative which operates as follows:
m
((x = m Σ
Zk (L(x + 82k, y) L(x, v)) 15
(5)
3

---

Under review as a conference paper at ICLR 2020
where 2 's are usually drawn from normal distribution. While RDSA is more query efficient than KWSA, still needs a lot of queries to have a reasonably accurate estimate which typically scales with dimension. The step size ó > 0 in RDSA and KWSA is a key parameter of choice; higher 5 could lead to extremely biased estimates, while lower 8 can lead to an unstable estimator. In light of the two aforementioned gradient estimation schemes, the PGD attack (c.f. equation 3 can be suitably modified to suit black-box attacks as follows:
X (x.e) + r/Si)
with St = (l0 V (xL(xx-1,)).
(6)
However, owing the biased gradient estimates, though PGD based black-box attack is successful turns out to be query hungry. In particular, in order to ensure sufficient increase of the objective at each iteration the query complexity scales with dimension and hence is prohibitively large. However, most if not all successful black-box adversarial attacks tend be multi iteration based methods. In the sequel, we develop a query efficient single step black-box box adversarial attack.
4 QUERY EFFICIENT SINGLE ITERATION BLACK-BOX ATTACKS
In this section, we develop the query efficient single iteration black-box attack method.
4.1 GRADIENT CORRELATION
In most black-box adversarial attacks, the gradient terms across different images are implicitly as- sumed to be independent from each other. However, even inspecting adversarial examples visually, it is apparent that the gradients across different images exhibit correlation. In fact, gradient terms seem to be heavily correlated, and a black-box method aiming to find adversarial examples using as few queries possible should exploit this correlation. We propose to exploit and model these correlations using a Gaussian Markov random field. Formally, letting be the input to a classifier, and g = VL(x,U) y) the gradient of the loss function with respect to the input, we are attempting to query and estimate the gradient, then we aim to put a prior distribution over
g (O,
where Σ is a non-identity covariance matrix modeling the correlation between terms. Following common practice we are not going to model Sigma, but rather model the inverse covariance matrix A = -E- -E',a a setting also known as the Gaussian Markov random field (GMRF) setting, given that the non-zero entries in A correspond exactly the edges in graphical model describing the distri- bution. And even more specifically, we are not going to attempt to model each entry of A separately, but use parameterized Gaussian MRF with relatively few free parameters. For example, if x is a 2D image, then we may have one parameter a governing the diagonal terms Ar, a, Vi, and another governing adjacent pixels Aij = B for i.j corresponding to indices that are neighboring in the original image. We will jointly refer to all the parameters of this model 0, in this case (ax, B3, and we refer to the resulting A as A(0).
We then consider the problem of fitting a parameterized MRF model to estimate gradients of inputs
(1) ((),, using n directional derivatives for each input given by G = "). .g.. (mn))] The maximum likelihood estimation for this problem is precisely the optimization problem
min tr()A(()) logdet (oggde(A(())) (A())),
(8)
where S - 15 E; (t) is the sample covariance and logdet denotes the log determinant. This is in fact the standard Gaussian maximum likelihood estimation problem. While this is a standard problem for the case of general covariance (minimizing A just the inverse of the same covari- ance), when we use a parameterized form of A, it becomes less clear how to solve this optimization problem efficiently. As we show, however, this optimization problem can be casily solved using the Fourier Transform; we focus for simplicity of presentation on the 2D case, but the method is easily generalizable to three dimensional convolutions to capture color channels in addition to the spatial dimensions itself (and we use this 3I) form for all color images). First, focus on evaluating the
4

---

Under review as a conference paper at ICLR 2020
trace term. The key idea here is that the Lambda operator can be viewed as (circular) convolution
0
8 0
K
3 0
3
which then lets us compute tr(SA(0)) as sum of the elements of the product of G and the zero padded 2D convolution of G and K. For the log determinant term, can again exploit the fact that a convolution operator. Specifically, because it a convolution, we know can be diagonalized using the discrete Fourier transform.
= Q DQ
where Q is the the Fast Fourier Transform (FFT) basis, and the eigenvalues being the diagonal elements of D can be found by an Fast Fourier Transform (FFT) to the zero-padded convolution operator; thus, we can compute the log determinant term by simply taking the sum of the log of the FFT-computed eigenvalues. We then employ Newton's 's method to optimize the objective. The entire procedure estimating the GMRF parameters is depicted in Algorithm|] I For N N sized image, the dominating cost for the procedure will be the O log N) computation the 2D FFT; this constrasts with the ( naive complexity of forming, e.g., the naive eigen decomposition of the N2 N2 inverse covariance.
Algorithm Solving for GMRF
1: procedure SOLVING GMRF( (6) u
Ji=1, 8)
2: Draw n vectors (1) 3.... (n) ~ (O.I)
3: Estimate g ,......m.... (mm)) where g = u()) (L(x(0 O + ,n)), -(x(0- -500), /2
4:
Generate G from G by concatenating along each dimension.
5:
Calculate tr(SA(0)) sum G conv2d(K, G)): conv2d denotes 2D convolution sum (log(FF((A)) A is the zero prro-pddeed convolution operator 7: Use Newton's s method minimize the objective in equation
6:
Calculate (ogdet(A
return 8:
4.2 GRADIENT ESTIMATION
Under the aforementioned GMRF framework, we can interpret black-box gradient estimation as a Gaussian inference problem. Specifically, in our setting above, we have assumed that the gradient point follows the normal distribution with the prescribed inverse covariance
g g~ NO, A-
When observe the loss function value some point x', this be viewed noisy observation of the gradient
L(x)) ~ L(x) + Tx''x'-x- (x' xx,,
where we do an abuse of notation by dropping in T(x,y). Thus, given a set of sample points (1) ,I,),...,x (m) and their corresponding loss function values [(x(1)),... mmx(m)), we have the fol- lowing characterization of the distribution
x
Ligg ~ N(Xg,
where
L = ((xx1))-(( ... ((x(m)) L(x) x
[(x(x) x) ... (x(1)) x)
The perturbed points { 1 generated according to supplied vectors (1mm dure. Under this condition, the posterior g|L, given by
pmm to the proce-
L ~ -AAAX'XX/ x L, (A+x
'The FFT operation technically operates circular convolutions (meaning the convolution wraps around the image), and thus the covariance naively models correlation between, c.g., the first and last rows of image. However, this is minor issue in practice since: 1) can be largely mitigated by zero pero-padding the input image hefore applying the FFT-based convolution, and 2) even if entrrelllentirelly.. the effect of few additional circular in the covariance estimation is minimal.
5

---

Under review as a conference paper at ICLR 2020
Comparion of Sredhora. mageher-OO01
Minbor Dec
Figure I: Summary of comparison of attack accuracy with query budgets for FFT basis vectors and normal distribution for &o with 0.05 on VGG16-bn trained on ImageNet. attacks
The matrix of interest that need solve for is the inverse covariance term
A X.
This a convolution plus a low rank matrix (the X X term is rank m, and we typically have m & n because we have relatively few samples and high dimensional input). We can not solve for this matrix exactly using the FFI, but we can still solve for it efficiently (requiring only an m m inverse) using the matrix inversion lemma, specifically using Woodburry's 's matrix inversion lemma
a (A+ 02 x
1
=A---A-XX (6'I+XA-XT) XA-1.
Since the term needs be computed explicitly for at least the inner inverse, explicitly maintain the term U = A Note that in the sequential sampling setting (where we sequentially sample j
(1) points one at a time), this matrix could be maintained over all samples, so that just single solve would be required for each new sample. We use the mean of the the conditional distribution [ as the gradient estimate. The gradient estimation procedure is depicted in Algorithm 2
Algorithm 2 Gradient Estimation
procedure GRADEST(x, {z 1 0, 8)
2: Compute L, by querying the model at fx + Jm and (x (1)
3: Compute X 26, (1) ..... ((())
4: Compute g (A + X XXXXXX0 X/02) x L1 using FFT
5: return g
4.3 GRADIENT ESTIMATION: DIRECTIONAL DERIVATIVES
In order to estimate the gradient efficiently Algorithm a key role is played by the vectors (z()) im mal distribution. However, it is worth noting that the inverse covariance distribution of the gradients by construction is convolution operator and hence is diagonalized by the FFT basis. In particular, the low frequency components of the FFT basis vectors enhanced the attack accuracy significantly, an example of which is depicted in Figure [ for black-box attacks on VGG16-bn classifier for Im- ageNet with e 0.05. With the gradient estimate hand, the adversarial input for is generated using FGSM as follows:
Jim] which perturb the input. One particular choice being sampling the directions from nor-
Xadv = x + esign (g)
The entire procedure consisting of GMRF inference and gradient inference is presented in Algorithm We provide more details about the performance our gradient estimation scheme in terms of various metrics such as mean square error and cosine similarity between the estimated gradient and the true gradients in the Appendix A.6
3

---

Under review as a conference paper at ICLR 2020
Algorithm 3 GMRF based black-box FGSM
1: procedure BB-FGSM(O, 51, d,
2: f- SOLVING GMRF((x(0) 1 6)
3: {z()) J t FFT basis vectors
4: g + GRADEST(X, 12())_ 0, 61,0)
5: Xade = + esign (g)
6:
return Xade
EXPERIMENTS
In this section, we focus on the untargeted attack setting where the goal is to generate a perturbation so as to get an original image originally classified correctly by the classification model to be misclas- sified to any class other than the original class. In particular, we consider foo attacks on ImageNet (Deng al. 2009) and MNIST (Leeun al. 1998) and evaluate the performance in terms of attack success rate with a given query budget and average query count.
The attack success rate is defined as the ratio of the number of images successfully misclassified to the total number of input images. Among the set of input images, we discard images which were misclassified by the classifier. The average query count is computed on the queries made for successful attacks.
5.1 EXPERIMENTS ON MNIST
We compare the performance of the proposed method with that of white-box FGSM (Goodfellow) et al. 2014)) across different values of for bounds ranging from 0.05 to 0.3 in increments of 0.05 over query budgets from 20 200. We use the pre-trained LeNet model available from Pytorch to demonstrate the attacks. We use all the correctly classified images from the 10,000 images (scaled to [0. IJ) in the MNIST test set. To generate the sample gradients, for GMRF estimation, 1, 000 queries were used. To further illustrate the importance of incorporating a non-identity gradient covariance, we also provide experimental results for a version of our proposed algorithm which takes the gradient covariance method exhibits better attack accuracy than white-box FGSM in around 75 queries and the gap in the performance is further magnified with increasing number of queries. On the other hand, the version of our algorithm with identity gradient covariance consistently under performs with respect to the white-box FGSM attack. In particular, the identity covariance version only reaches close to the white-box FGSM attack performance in 200 queries. This further illustrates the effectiveness of our proposed algorithm and the importance of modelling the gradient covariance as a GMRF and more generally as a non-identity covariance matrix.
be an identity matrix. As shown Figure 2, our proposed attack
The superior performance of proposed framework compared white-box FGSM demon- strated in Figure/ can be attributed to the following reason. First, incorporating the gradient non- identity covariance structure into the gradient estimation scheme, allows our perturbation to be able use structural gradient information from other images too. On the other hand, white box FGSM treats gradient of every image to be independent of gradients of other images. This is further illus- trated by our experimental findings based on the version of our algorithm considering the gradient covariance be identity matrix.
5.2 EXPERIMENTS ON IMAGENET
We compare the performance of the proposed method with that of NES Ilyas et al.) 2018). BANDITS-TD (Ilyas al., 2019) and PARSIMONIOUS (Moon al.) 2019). which are the current state of the art in Eoo based black-box attacks. For ImageNet, we consider three classifiers namely, ResNet50 (He et al. 2015), Inception-v3 (Szegedy al. 2015) and VGG bn (Simonyan & Zis- (serman 2014). We use the pre-trained models provided by Py Torch for attacking these classifiers.
We use all the correctly classified images from the 50,000 images (scaled to [0. 1]) in the ImageNet validation set.
7

---

Under review as a conference paper at ICLR 2020
<=3.5
Ew0.
Artoc Succst
74
1-0J
1-2
1-1.2
631
Suntee Quier
30
Nonder
Namber Ounnes
Figure 2: Summary of comparison of the proposed attack and the proposed attack with identity gradient covariance with white-box FGSM for attack accuracy with query budgets for MNIST on LeNet
Successrod rote
Success rote
Froend Leneta11
mor LanetLT
600
<80
1006
600
Figure 3: VGG16-bn: Attack Figure 4: ResNe150: Attack Figure 5: Inception-v3: Attack
success rate function of success rate function of success rate function of query budget
query budget
query budget
The foo perturbation bound set 0.05. We the implementation and hyperparameters provided by Πyya et al. (019)) for NES and BANDITS-TD. Similarly for PARSIMONIOUS, we use the implementatiorf] and hyperparameters given by (Moon al. 2019). The last 50 images of the ImageNet validation set are used for estimating the parameters of the GMRF. In particular, to generate the sample gradients, for each model, 5, 000 queries were used for the GMRF estimation. The specifics of the GMRF model, the values of the parameters and the associated hyperparameters (which were obtained by grid search) for the proposed algorithm for the three classifiers are relegated to the Appendix. Figures 3]55 the evolution of attack accuracy with different querying budgets. the regime of low query budget with less than 200 query budget, our algorithm outperforms PARSIMONIOUS, though it exhibits inferior performance in the higher query budget regime.
As shown in Table I proposed algorithm in spite of being single-step attack, outperforms BANDITS- and NES by achieving higher attack success rate. Despite the higher success rate, proposed method uses fewer queries on an average as compared to BANDITS-TD and NES. Thus, the proposed method strictly dominates BANDITS-TD and NES every metric.
The proficiency our proposed scheme in the low query budget regime can be attributed to the utilization of the correlation between gradients across images and the usage of FFT basis vectors for calculating directional derivatives. In partieular, the FFT basis vectors being the eigen vectors of the covariance matrix provide for systematic dimensionality reduction.
8

---

Under review as a conference paper at ICLR 2020
Table I: Summary of 2o attacks with 0.05 ImageNet attacks using NES, BANDITS-TD, PAR- SIMONIOUS and the proposed method with query budget of 1000 per image
VGG16-bn
Resnet50
Inception-v3
Attack
Success
Avg. Queries
Success
Avg. Queries
Success
Avg. Queries
NES 73.08%
441.38
57.73%
471.24
46.75%
467.02
Parsimonious
98.24%
175.76
95.73%
186.43
80.86%
247.11
Banditsrp 85.91%
133.67
78.80%
181.15
69.83%
212.55
Proposed 86.92%
118.28
81.22%
132.09
69.97%
192.69
6 CONCLUSION
In this paper, we have developed a GMRF based covariance modeling technique so as to streamline the gradient estimation scheme catered towards black-box adversarial attacks. In particular, due the streamlined gradient estimation scheme, we could alleviate the issue of random directional derivative searches which plagues every zeroth order optimization scheme due to biased gradient estimates. The gradient estimation scheme can be used in any gradient based black-box adversarial attack method to attain higher attack accuracies with lower query counts. Our method facilitates single iteration based query efficient black-box attacks which we demonstrated to be as potent as multi-step attacks multiple architectures and datasets in terms of attack success rate. We also em- ployed techniques from matrix analysis and FFT make our attack computationally efficient. Our results open avenues for more effective covariance modeling techniques so as to further streamline gradient estimation schemes to facilitate query efficient black-box adversarial attacks.
REFERENCES
Wieland Brendel, Jonas Rauber, and Matthias Bethge. Decision- based adversarial attacks: Reliable attacks against black-box machine learning models. arXiv preprint arXiv:1712.04248, 2017.
Jianbo Chen, Michael I. Jordan, and Martin J. Wainwright. Hopskipjumpattack: A query-efficient decision-based attack. 2019.
Pin-Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsieh. Zoo: Zeroth order opti- mization based black-box attacks to deep neural networks without training substitute models. In Proceedings of the 10th ACM Workshop 15-26, New York, NY, USA, 2017. ACM. ISBN 978- 1 1-200-5202244 doi: 10.1145/3122572. 3140448. URL http:://o: acm. org 10. /tt...o.......111111333332222... 314444
Artificial Intelligence and Security, AlSec '17, pp-
Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Feii ImageNet: A Large-Scale Hierarchical Image Database. In CVPR09, 2009.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint arXiv:1412.6572. 2014.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. 2016 IEEE Conference Computer Vision and Pattern Recognition (CVPR), pp. 770- 778, 2015.
Andrew Ilyas, Logan Engstrom, Anish Athalye, and Jessy Lin. Black-box adversarial attacks with limited queries and information. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 2137 2146, StockholmsmAAd ssan, Stockholm Sweden, 10-15 15 Jul 2018. PMLR. htt.:pppp/ppoceeennggnn..mpppepp
htm
Andrew Ilass Logan Engstrom, and Aleksander Madry. Prior convictions: Black-box adversarial
attacks with bandits and priors. In International Conference on Learning Representations, 2019. URL
wtt.//ertuut... id BKMiWhR5K7
Jack Kiefer, Jacob Wolfowitz, et al. Stochastic estimation of the maximum of regression function. The Annals of Mathematical Statistics, 23(3):462-466 1952.

---

Under review as a conference paper at ICLR 2020
Yann Lecun, LÅl'on Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, pp. 2278-2324, 1998.
Alex Tong Lin, Yonatan Dukler, Wuchen Li, and Guido Montúfar. Wasserstein diffusion tikhonov regularization. arXiv preprint 19X,vv9990006800 2019.
Seungyong Moon, Gaon An, and Hyun Oh Song. Parsimonious black-box adversarial attacks via efficient combinatorial optimization. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 Proceed- ings of Machine Learning Research, pp. 4636-4645, Long Beach, California, USA, 09-15 Jun 2019. PMLR. URL BRLLtttp://prreeednngg mir pww.s.ppp.s..e................. v ptress/v97/moonna.... httml
Nina Narodytska and Shiva Kasiviswanathan. Simple black-box adversarial attacks on deep neural networks. In 2017 IEEE Conference on Computer Vision and Pattern Recognition Workshops (CVPRW), pp. 1310-1318. IEEE, 2017.
Blaine Nelson, Benjamin IP Rubinstein, Ling Huang, Anthony D Joseph, Steven Lee, Satish Rao, and JD Tygar. Query strategies for evading convex-inducing classifiers Journal of Machine Learning Research, (1MMay):1293-133:: 2012.
Yurii Nesterov and Vladimir Spokoiny. Random gradient- free minimization of convex functions. Foundations of Computational Mathematics, 17(2):527-566, 2017.
Nicolas Papernot, Patrick McDaniel, Ian Goodfellow, Somesh Jha, Z Berkay Celik, and Ananthram Swami. Practical black-box attacks against machine learning. In Proceedings of the 2017 ACM on Asia conference on computer and communications security, pp- 506-519. ACM, 2017.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition, 2014. cite arxiv:1409.1555
Christian Szegedy, Vincent Vanhoucke, Sergey loffe, Jonathon Shlens, and Zbigniew Wojna. Re- thinking the inception architecture for computer vision. 2016 IEEE Conference Computer Vision and Pattern Recognition (CVPR), pp. 2818-2826, 2015.
Chun-Chen Tu, Pai-Shun Ting, Pin-Yu Yu Chen, Sijia Liu, Huan Zhang, Jinfeng Yi, Cho-Jui Hsieh, and Shin-Ming Cheng. Autozoom: Autoencoder-based zeroth order optimization method for attacking black-box neural networks. In The Thirty-Third AAAI Conference Artificial Intel- ligence, AAAI 2019, The Thirty-First Innovative Applications of Artificial Intelligence Confer- ence, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu, Hawaii, USA, January 27 February 1, 2019., pp. 742-749, 2019. URI. https://aan aaai http:://aaai.ogg/////.. ojs/ index. paceeexppppppeeemm AAAI http///artcieeevvieoa wit.ee//vee///5/3
Weilin Xu, Yanjun Qi, and David Evans. Automatically evading classifiers. In Proceedings of the 2016 Network and Distributed Systems Symposium, pp. 21-24, 2016.
A APPENDIX
A.1 MNIST EXPERIMENTS
The GMRF model used for MNIST is given by Ar, = a, A, = A++14 = A - A =
8, A A A;-1,441 = A;+1,i-1 = =Y, where Ai,j denotes the (i. j-th element of A. For estimating the GMRF parameters, each of them with 50 vectors drawn from a normal distribution. For the attack, we use low frequency basis vectors of the FFT basis. The following table gives the values of the different hyperparameters used in the attack. Except for the GMRF parameters, all the other parameters were determined using grid search.
use the last 20 images of the MNIST test set and perturb
A.2 VGG16 EXPERIMENTS
The GMRF model used for VGG16 for Imagenet is given by Ao,s, A, Ao A0,4415 A0,1,-1 A0,=-1, = 8, A0,4115+1 = A0,i-1,t41 = An,i-15511 A0.41.i-1 = K, A1,,i A-1,2, = 7, where in Ag.ij. & denotes the channel. We also tried out GMRF models of lower and higher degree of association and selected the one performing the best. For estimating the
10

---

Under review as a conference paper at ICLR 2020
Table 2: MNIST Experiment Settings
6
0.1
21094408
B
-5116365
?
284558.1562
10
81 0.15
GMRF parameters, we use the last 50 images of the ImageNet validation set and perturb each of them with 50 vectors drawn from normal distribution. For the attack, we use low frequency basis vectors of the FFT basis. The following table gives the values of the different hyperparameters used in the attack. Except for the GMRF parameters, all the other parameters were determined using grid
Table 3: ImageNet VGG-16 Experiment Settings
0.1
a
633.44
8
24..0
7
222..0
-2.0 K
1.0
0.05
search.
A.3 RESNET5O EXPERIMENTS
The GMRF model used for VGG16 for Imagenet is given by Ao,i, a, A0,144 A0,441,
Ag,i.i1 = A,,-1,i = B, A0,++1,+11 A0,5-1,+1
An,--1,-11 = A0,i+1,i-1 = K, Ao,
A0,1,1-2 A0,4-2,
A0,42,4 A0. A0,i-1,42
A0,442,41 = A0.142,-11
A1,2 A-1.i. = 7, where in Ak.i.j* denotes the channel. We also tried out GMRF models of lower and higher degree of association and we selected the one performing the best. For estimating the GMRF parameters,
Ag.i-1,i-2 A0.i+1,122 -,0--2,i-1 -0..-2.+11
use the last 50 images the ImageNet validation set and perturb each of them with 50 vectors drawn from a normal distribution. For the attack, we use low frequency basis vectors of the FFT basis. The following table gives the values of the different hyperparameters used in the attack. Except for the
Table 4: ImageNet ResNet50 Experiment Settings
5
0.1
2631.93
8
263.33
837.16
K
6.78
28.09
0.5
61
0.05
GMRF parameters, all the other parameters were determined using grid search.
11

---

Under review as a conference paper at ICLR 2020
A.4 INCEPTION V3 EXPERIMENTS
The GMRF model used for VGG16 for Imagenet is given by Ao,i. = a, A0,1441 = A0,041,
A0,i5-1 A,,i11í = 3, A0,s+1,441 A0,5-1,41
A,,1-15-11
A0,441,-11 K. A0,1.42 A0,442,411
A0,i,i2 = An,i-2,
An.442, A0,i+1,122 A0,1-1.42
Ap.14,i-1
A,,i-1,i-2 = 1., -,, A0.--24+1 = V, 1, A1,2, A-1.i, = 7, where in As.i.j.
k denotes the channel. We also tried out GMRF models of lower and higher degree of association and we selected the one performing the best. For estimating the GMRF parameters, we use the last 50 images of the ImageNet validation set and perturb each of them with 50 vectors drawn from a normal distribution. For the attack, we use low frequency cosine basis vectors of the FFT basis. The following table gives the values of the different hyperparameters used in the attack. Except for the
Table 5: ImageNet Inception v3 Experiment Settings
8
0.1
ax
8964.89
2960.87
?
841.13
K
1155.66
V
286.03
o 0.5
81
0.05
GMRF parameters, all the other parameters were determined using grid search.
A.5 EFFICIENT COMPUTATION OF FFT BASIS
We use the fact that the covariance and the inverse covariance matrix because of being convolutional operators are diagonalized by the FFT basis. Let us assume the image of size e x w, where e, and w denote the number of channels. height and width of the gradient. We define tensor S of zeros of size X h X 2, where the last dimension to account for both the real and complex components. In order to generate the lowest frequency basis vector, we set the the first element the tensor of the first channel, i.e, S0,0.0.0 = 1 and take the inverse FFT. This gives us the lowest cosine basis vector. We do the same for the other channels, by just setting the corresponding component to 1 and taking the inverse FFT. Setting, Sp.o.0. = and then taking the inverse FFT yields the lowest frequent sine component. In order to generate the low frequency components. we start from the beginning of a row and proceed along diagonally by incrementing the row and column index by one. At each entry of the tensor, we repeat it for every channel once at time.
A.6 GRADIENT ESTIMATION PERFORMANCE
We illustrate the performance of our gradient estimation scheme in this section through experiments on the MNIST and the ImageNet dataset using LeNet and VGG-16br respectively. We use two met- rics namely, mean squared error the normalized estimated gradient with respect to the normalized true gradient and the cosine similarity between the estimated gradient and the true gradient. In order to perform our analysis, we 500 data samples from the test set to estimate the gradient using the GMRF framework. First, we estimate the GMRF parameters as previously described in Algorithm and then perform the MAP estimation for the gradient. For MNIST, we demonstrate the gradient estimation performance on two regimes, i.e., 40 query budget where our scheme is outperfomed by white-box FGSM and 200 query budget where the vice versa happens. As evident from Figures 6b and 7bb our scheme generates gradient estimates which have low MSE. For, the 40 query bud- get setting, the cosine similarity is centered around 0.3. while for the 200 query budget setting, the cosine similarity is centered around 0.2. Had our gradient estimates completely aligned with that of the true gradient in woite-box FGSM our performance would have been upper bounded by the performance of white-box FGSM. essence, our scheme finds directions for adversarial per- turbations, which in itself does not maximize the loss but is able to find direction which leads to misclassification of the examples.
12

---

Under review as a conference paper at ICLR 2020
The gradient estimation performance for ImageNet using VGGI6-bn is depicted in Figure 8. In order perform our analysis, we sample 500 data samples from the ImageNet validation set to estimate the gradient using the GMRF framework. First, we estimate the GMRF parameters as previously described in Algorithm and then perform the MAP estimation for the gradient. We specifically consider the query budget to be 200. Out the 400 correctly classified images, white- box FGSM and our proposed algorithm attain attack accuracies of 0.9268 and 0.7804 respectively. While, the gradient estimation performance in terms of MSE impressive, the cosine similarity shows that the estimated gradient does not quite coincide directionally with the true gradient. The difference in the directions explains the inferior performance of our proposed scheme in this regime. worth noting that the dimension of the imput data for VGG16-bn is 150528. From classical results in zeroth-order optimization it is well known that in a dddimensional space, O(d) queries required to obtain nearly bias-free gradient estimate. Our framework uses only 200 queries to estimate the gradient which resides in 150528 dimensional space. In spite of the possible erroneous directional characteristic of our estimated gradient, it still manages to achieve 0.78 success rate and outperforms BANDITS-TD and PARSIMONIOUS in the 200 query budget regime.
10a
30
10a
10a
10
10
16
5-
5
-75
-5.0
-2.5
0.0
2.5
5.0
75
Ie-4
0.0016 0.0018 0.0020 0.0022 0.0024
0.1
0.2
0.3
0.4
(a) Truc Gradient Distribution
(b) Mean squared error
(c) Cosine Similarity
Figure LeNet, MNIST, query budget
10a
10a
20
104
15
167
10
5-
10a
-2.5
5.0010
0.0015
0.0020
0. 0.0025
(a) True Gradient Distribution
(b) Mean squared error
(c) Cosine Similarity
Figure 7: LeNet, MNIST, 200 query budget
60
40
30
30
10a
20
20
10a
1.32
(a) True Gradient Distribution
(b) Mean squared error
(c) Cosine Similarity
Figure 8: VGG-16bn, ImageNet, 200 query budget
13

---

Under review as a conference paper at ICLR 2020
A.7 AUTOCORRELATION
provide further evidence for considering non-identity covariance for modelling the gradient covariance. In figure 9, we plot the autocorrelation of the true gradients from 100 images sampled from the MNIST test for different kernel sizes, i.e., 9 9 and 11 11 for the LeNet model. In figure 10, we plot the autocorrelation of the third channel of the true gradients from 50 images sampled from the ImageNet validation set for two different kernel sizes, i.e., 9 and 11 11 for the VGG16-bn model. The autocorrelation plots show the correlation across dimensions and across images to be substantial so as to provide even more evidence and reason for the gradient model we have considered in this paper.
10
10
1
0.8
0.6
0.6
0.4
0.4
0.2
0.2
-.0
10
2
2
(a) 9 x 9 kernel
(b) 11 x 11 kernel
Figure 9: Autocorrelation of the gradients: MNIST, LeNet
1
0.6
0.4
0.2
0.2
0.0
0
2
(a) 9 x 9 kernel
(b) 11 x 11 kernel
Figure 10: Autocorrelatin of the gradients: ImageNet, VGG16-bn
14


Reviews:
[{"review_id": "HkxENuvTFH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper employs Markov random fields to exploit the input data structure and further model the covariance structure of the gradients. This embeds covariance structures of input data space into the gradient operator for an adversary attack.\nThey further use this gradient operator with a fast gradient sign Method. The numerics show effective for using fewer queries to obtain high attack accuracy. This paper is well written with clear derivations. I suggest the publication of the paper.\n\n In fact, modeling the structure of an input space structure into the adversary attack is a good direction. For similar intuitions in this direction, I recommend a related work:\n      \n         \"A. Lin, Y. Dukler, W. Li, G. Montufar, Wasserstein Diffusion Tikhonov Regularization\" \n ", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HJe8shqRYB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\n- The ideas in this paper have practical utility. The paper is unfortunately not very carefully written, and the arguments require occasionally some guesswork.\n\n- There is not a sufficient discussion of experimental findings. Why does the proposed method works better than a white box FGSM for instance? \n\n- 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. \n\n- 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. \nIn 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.\n\n- 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. \n\n- 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. \n\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "B1gYI3PpFB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors propose a method for black box adversarial image generation. The idea is to learn a parameterization of a precision matrix so that gradients of a network's loss are assumed to be drawn from a corresponding Gaussian. The parameters of this model are fit efficiently using the spectral theorem that their particular parameterization of the precision matrix allows them to use. Gradient estimation is then viewed as a Gaussian conditioning problem given observations (see last equation on page 5).\n\nOverall, I think the method is elegant -- particular in comparison to many existing approaches in the literature that rely on highly complex machinery like genetic algorithms and the like. My main source of questions is the experimental results section, which I currently view as somewhat weak and a little confusing -- I would be more than happy to increase my score if my concerns are sufficiently addressed.\n\nFirst, I'm not sure that the story told by Figure 3 and Table 1 is entirely clear. On the whole at a given sufficiently high success rate (say, 80%), it seems that the authors' approach consistently loses to the Parsimonious attack of Moon et al., 2019? The authors' method seems to perform strictly better than Bandits_{TD} and NES, but the gap between the Parsimonious attack and the authors' is quite substantial past 300 evaluations.\n\nThis ultimately leaves me with the question of what to do with this paper. The learning framework used to estimate gradients is clever, but doesn't seem to me to be methodologically groundbreaking to the point where it can stand on its own merits independent of its performance in comparison to other techniques. Particularly considering other papers have been published since the Ilyas et al., 2019 paper that outperform Bandits_{TD} and NES in terms of query efficiency, I worry that this paper simply presents a decent idea with middling results.\n\nI'd therefore like the authors to primarily comment on the broader impact they believe their paper will have. The conclusion primarily focuses on the introduction of the method: does it have substantial merits past its empirical performance?", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a Markov Random Fields (MRF) for generating adversarial examples in a black-box setting, where only it has access to loss function evaluations. The method exploits the structure of input data to model the covariance structure of the gradients. Empirically, the resulting method uses fewer queries than the current state of the art to achieve comparable performance. Overall, the paper has valuable contributions. The main issue is on empirical evaluation, which can be strengthened, e.g., by including results with multi-step methods and more thorough analysis of the estimated gradients.
Decision: Reject