Less is More: Dimension Reduction Finds On-Manifold Adversarial Examples in Hard-Label Attacks
Authors: Washington Garcia
Pin-Yu Chen
Somesh Jha
Hamilton Scott Clouse
Kevin R. B. Butler
Venue: ICLR 2022 Submitted (2022)
Keywords: hard-label attacks
adversarial machine learning
generalization

Abstract: Designing deep networks robust to adversarial examples remains an open problem. Likewise, recent zeroth-order hard-label attacks on image classification models have shown comparable performance to their first-order, gradient-level alternatives. It was recently shown in the gradient-level setting that regular adversarial examples leave the data manifold, while their on-manifold counterparts are in fact generalization errors. In this paper, we argue that query efficiency in the zeroth-order setting is connected to an adversary's traversal through the data manifold. To explain this behavior, we propose an information-theoretic argument based on a noisy manifold distance oracle, which leaks manifold information through the adversary's gradient estimate. Through numerical experiments of manifold-gradient mutual information, we show this behavior acts as a function of the effective problem dimensionality. On high-dimensional real-world datasets and multiple zeroth-order attacks using dimension reduction, we observe the same behavior to produce samples closer to the data manifold. This can result in up to 4x decrease in the manifold distance measure, regardless of the model robustness. Our results suggest that taking the manifold-gradient mutual information into account can thus inform better robust model design in the future, and avoid leakage of the sensitive data manifold information.

Under review as a conference paper at ICLR 2022
DIMENSION REDUCTION FINDS ON-MANIFOLD ADVERSARIAL EXAMPLES IN HARD- LABEL ATTACKS
LESS IS MORE:
Anonymous authors Paper under double-blind review
ABSTRACT
Designing deep networks robust to adversarial examples remains an open problem. Likewise, recent zeroth-order hard-label attacks on image classification models have shown comparable performance to their first-order, gradient-level alternatives. It was recently shown in the gradient-leved setting that regular adversarial examples leave the data manifold, while their on on-manifold counterparts are in fact generaliza- tion errors. In this paper, we argue that query efficiency in the zeroth-ordes setting is connected to adversary's traversal through the data manifold. To explain this behavior, we propose an information-theone distance oracle, which leaks manifold information through the adversary's s gradient estimate. Through numerical experiments of manifold-gradin ggaddient mutual information, we show this behavior acts as function of the effective problem dimensional- ity. On high- dimeeniiiiin real-world datasets and multiple zeroth-order attacks using dimension reduction, we observe the same behavior to produce samples closer to the data manifold. This can result in up to 4x decrease in the manifold distance measure, regardless of the model robustness. Our results suggest that taking the manifold- -arifolldgrrdient mutual information into account can thus inform better robust model design in the future, and avoid leakage of the sensitive data manifold information.
argument based on a noixy manifold
INTRODUCTION
Adversarial examples against deep learning models were originally investigated as blind spots in classification (Szegedy et al. [013 Goodfellow et al. [014). Formal methods for discovering these blind spots emerged, which we denote as gradient-leve attacks, and became the first techniques to reach widespread attention within the deep learning community (Papernot et al., 2016 Moosavi] Dezfooli et al., 2015; Carlini & Wagner 2016, 2017, Chen et al., 2018). order to compute the necessary gradient information, such techniques required access to the model parameters and sizeable query budget. These shortcomings were addressed by the creation of score-level attacks, which only require the confidence values output by the deep learning models (Fredrikson al. 2015] Tramer et al. 2016, Chen et al. 2017 Ilyas et al. 2018). However, these attacks still rely on models divulge information that would be impractical to receive in real-world systems. By contrast, hard-label attacks make no assumptions about receiving side information, and only the predicted class is observable, thus providing the weakest, yet most realistic adversarial threat model. These methods, which originated from random- walk on the decision boundary (Brendel et al. (017)). have been carefully refined offer convergence guarantees (Cheng et al., 2019). query efficiency (Chen) et al. 2019 Cheng et al. 2020), and capability in the physical world Feng et al. (2020).
Despite the steady improvements of hard-label attacks, open questions persist about their behavior, and adversarial machine learning (AML) attacks at large. Adversarial examples were originally assumed to lie in rare pockets of the input space (Goodfellow et al.) [2014), but this conventional wisdom was later challenged by the boundary tilting assumption (Tanay & Griffin 2016 Gilmer et al., 2018), which adopts a "tatt-ggo view of the input space living on a dimve--dmensional manifold. This is supported by Stutz et al. (2019), who suggest that regular adversarial examples leave the data manifold, while on- ma-miiifold adversarial examples are generalization errors. From a data-geometric perspective, an adversarial example's distance the manifold primarily describes

---

Under review as a conference paper at ICLR 2022
the amount of semantic features preserved during the attack process. This makes it advantageous to produce on- on-manifold adversarial examples, since the adversary can exploit the inherent generalization error of the model while producing samples that semantically similar for humans. However, the true data manifold is either difficult or impossible to describe, and relying solely on approximations of the manifold can lead to the creation of crude adversarial examples (Stutz et al. (019).
In this paper, we adopt the boundary-tilting assumption and demonstrate an unexpected benefit of query-efficient zeroth-order attacks, i.e., attacks enabled by the use of dimensionality reduction techniques. These attacks are more likely to discover on-manifold examples, which we theoretically demonstrate is the result of manifold- graddientt mutual information. Our results suggest that this quantity can increase as a function of the data dimensionality. This information leakage leads to adversarial examples that are on-manifold generalization errors. With this knowledge, we empirically demonstrate how to improve hard-label attacks in a generic yet principled way, and potentially re-think their interaction with model robustness and public-facing systems in the near future.
For clarity, we provide block diagram of our claims and experiments in the Appendix (Section A.3 Our specific contributions are as follows:
Introduction of manifold distance oracle. To create on-manifold examples, the adversary must (implicitly) leverage manifold information during the attack phase. We thus propose an information- theoretic formulation of the noisy manifold distance (NMD) oracle, which can explain how zeroth- order attacks craft on-manifold examples. We theoretically demonstrate on a Gaussian data model that manifold- gradient mutual information can increase function of data dimensionality. We empirically show this is true even on large-scale image datasets such as CIFAR- 10 and ImageNet. This finding relates known behavior in the gradient-level setting, where semantic manifold priors (e.g., shapes and textures) can be leaked from robust models (Engstrom et al. 2019).
Reveal new insights of manifold feedback during query-efficient zeroth-order search. In practice, the data manifold is difficult to characterize. We propose the use of three proxies for manifold distance, which all show consistent results in terms of an adversary's ability to search near the manifold. This methodology allows us to empirically demonstrate the connection between dimension reduction, model robustness, and manifold feedback from the model, beyond the known convergence rates tied to dimensionality (Nesterov & Spokoiny 2017). Our findings inform how to search closer the manifold (Table D reduce gradient deviation (Table 2 and improve query efficiency (Figure in simple and generic way for hard-laber attacks.
Attack-agnon method for super-pixel pixel grouping. We show that spatial dimension reduction of a decision- based gradient estimate acts as an attack- and snowledge-agnostic method for searching over super-pixels of an image. More importantly, this helps attacker exploit model's reaction to salient input changes, leading to samples closer to the manifold compared to the attack on full dimension. As a result, we demonstrate up 200% and 340% success rate improvement for state-of-the-ar hard-label attacks HSJA (Chen et al. 2019) and Sign-OPT attack (Cheng et al. 2020). respectively.
2 RELATED WORK
Since the original discovery of adversarial samples against deep models (Szegedy al.) 2013 Goodfellow et al. 2014), the prevailing question was why such examples existed. The original assumption was that adversarial examples lived in low-probability pockets of the input space, and were never encountered during parameter optimization (Szegedy et al. 2013). This effect was believed to be amplified by the linearity of weight activations in the presence of small perturbations (Goodfellow et al. 2014). These assumptions were later challenged by the boundary tilting assumption, which in summary 1) asserts that the train and test sets of a model only occupy a sub- sub-manifold of the true data, while the decision boundary lies close to samples on and beyond the sub-manifold (Tanay & Griffin 2016), and 2) supports the "data geometric" view, where high-dimensional geometry of the true data manifold enables low-probability error set to exist (Gilmer et al. 2018 8) Likewise the boundary tilting assumption describes adversarial samples as leaving the manifold, which has inspired defenses based projecting such samples back to the data manifold (Dalal et al. 2019 Samangouei et al. 2018). However, these approaches were later defcated by adaptive attacks (Carlini et al. 20199Carlin & Wagner 2017 Tramer al. 2020).
2

---

Under review as a conference paper at ICLR 2022
We investigate the scenario where adversary uses seroth-order information (i.e., top-1 label feed- back) to estimate the desired gradient direction (Cheng et al. 2020 Chen et al. 2019 Contemporary attacks in this setting variants of random gradient-free method (RGF) (Nsterov & Spokoiny 2017), and rely on formulations which convert the top-1 (hard) label, which is step function, into a continuous real-valued function g : Rd IR, which takes search direction 0 e IR and outputs the distance to the nearest ad veressrril example (Cheng et al. (2018). The gradient estimate is conceived as function of the gradient Vg and can be estimated with either two samples of information (Sign- (Chen et al., 2019). Details of specific formulations for each attack are provided in Section (ection[A.2 of the Appendix.
OPT) (Cheng et al. 2020), or single point (HopSkipJump
Query efficiency is persistent desire in the study of hard-label attacks. One clue for achieving efficiency comes from the theory of gradient estimation error and convergence, which shows that the estimation cost is polynomial in d, the dimension of the optimized variable, thus motivating the use of standard dimension dimension-reduuttoo reduction techniques (Tu et al., 2019). However, to date is not completely understood how this relates to traversal through the data manifold. We leverage previous results of
the gradient- setting (Stutz et al. 2019 Engstrom et al., 2019) to formulate an explanation of manifold leakage during hard-label adversarial attacks.
NOISY MANIFOLD DISTANCE ORACLE
Santurkar et al. 2019) demonstrate that the gradients of robust models have higher visual semantic alignment with the data compared gradients of standard models. We build this finding by first assuming that the benign observable data generates from a true lower-dimension distribution. Under the boundary-tilting assumption, this lower-dimension distribution forms manifold onto which new observations, either benign or adversarial, can be encoded (Tanay & Griffin| 2016). Likewise, we assume that deep learning models will learn a diwensdi representation the observable data, e.g., feature layers of convolutional neural networks learn to encode training observations onto a low dimension approximate manifold (Zhang et al. 2018). When an adversary creates adversarial samples, they are leveraging pathway that shadows the model gradient, not the true manifold. Thus there is the possibility that adversarial samples are considered "off-manifold", e.g., cannot be expected to generate naturally from the true manifold. However, it is critical for adversarial samples to be as close to the manifold as possible, since on-manifoll adversarial examples can exploit the fundamental generalization error of the model (Stutz al. 2019). More formally, define the notion of manifold distance as follows.
Definition 3.1 (Manifold Distance). Consider the benign sample Xy and adversarial counterpart x. Assuming perfect encoding back to the true manifold do the manifold distance is defined as d()(x)), (x))). where is a distance function with the domain of the true manifold.
Unfortunately, unless the true manifold for a dataset is known, it is impossible to define &. Instead, proxy d' can be used such that d'(x,x') x') ~ d(((x), é(x')). In practice, one can implement d' with any perceptual distance score, such as Learned Perceptual Image Patch Similarity (Zhang et al. 2018). If relying on a distance measure d, such as the Ln-norm, an approximate encoder Φ'(-) .(-) can be learned using reconstruction-bart feature layers of convolutional neural networks (Zhang et al. 2018). We are interested in the class of hard-label adversaries that implicitly minimize some proxy of the manifold distance. Given the result of Santurkar et al. (2019), the robust model's gradient could be treated as a manifold distance oracle, because it leaks the direction towards its approximate manifold. As result, the model acts as an oracle responding to queries about manifold distance, or in other words, an implicit proxy for manifold distance, d'. In the hard-label setting, the data manifold, true gradient, and model parameters are not accessible. Thus we are interested in a decision- based version of the manifold distance oracle, defined as follows.
training of autoencoders (Stutz et al. 2019), or leveraging
Definition 3.2 (Noisy Manifold Distance Oracle). Consider a manifold distance oracle instantiating d', benign sample Xg. and pair of adversarial samples (x', x") such that d' (x,, < d'(xo. x"). e.g., x' is considered on-manifold while x" is not. In the hard-label setting, the noisy manifold distance (NMD) oracle instantiates d" such that d' (x(o,x x') = and d" x 1.
During a hard-label attack, the adversary searches in a direction that minimizes perceptual distance to the original sample. Concurrently, the adversary can be said to implicitly minimize the expected
3

---

Under review as a conference paper at ICLR 2022
output of the NMD oracle, which is a binary indicator that sample is on- manifold or not. Without knowledge of the true (or approximate) manifold, this requires careful selection of the search direction from the current sample. Since the search direction of contemporary hard-label attacks is synthesized over expectation of a ball around the adversarial sample, we are interested in search directions such as Xg x' which minimize the expected distance to the manifold.
To formalize the entailed information in the NMD oracle, we turn to a standard result in data processing, which states the following: Definition 3.3 (Data Processing Inequality (DPI) (Beaudry & Renner 2012)). three random variables form the Markov chain X - Y + Z, then their mutual information (MI) has the relation T(X;Y) > (X:2).
We assume the data manifold M,, the input gradient G, and the hard-label gradient estimate & will form the Markov chain M - g G G. This assumption is reasonable due the observations by Santurkar et al.] (019)); modifying the sampled data manifold (e.g.. by adding adversarial samples through saddle-pon point optimization) causally induces smoother loss surface, which imposes its own gradient distribution. Likewise, the true gradient and gradient estimate of hard-label attack are causally linked due the estimate's 's bounded variance (Cheng et al. 2020).
If 9) is larger for adversarially robust models, by Definition 3.3 is larger, which means more manifold information could be leaked in the noisy gradient. This information could be used search in the direction where d" is minimized in expectation, leading towards on on-manifold examples. However, DPI only offers an upper bound, thus the distance decrease not guaranteed, only suggested. In the information theoretic sense, does this mean the gradients of models robust in an c-ball around each sample can reveal more information about the distance to training data than standard models? An immediate follow-up concern is whether other factors can influence the model to reveal this information, such as the problem dimensionality, As first step we posit the following hypothesis:
the upper bound on [(M, 9)
Hypothesis 1. Consider the manifold distribution M which can generate data to train a natural model with gradient distribution G. and train robust model with smoothed gradient distribution G'. We posit that their manifold gradient mutual information 1 has the relation [(M, G') 2 9),
In order to empirically verify Hypothesis] D we must parameterize the notion of model robustness while solving for I (M, 9). given an arbitrary gradient distribution G and manifold distribution M. Schmidt et al. 2018) have shown that robust training requires additional data function of the data dimensionality. We leverage the data model and results from (Schmidt et al. (2018) to derive an analytical solution for I [MM, 9), since can parameterize model robustness function of data size and dimensionality. Consequently, the remainder of our theoretical analysis assumes a Gaussian
mixture data model.
Definition 3.4 (Data model and optimal weights (Schmidt et al. 2018)). Let pa IR be the per-class centers (means) and let a > O be the variance parameter. Then the (He, aI) - model is defined by the following distribution over (x, y) E Rd x {+1]: : First, draw label y E (+1} uniformly at random. Then sample the data point x E Rd from N(y (y-M,al)) pl)
Definition 3.5 (Optimal classification weight (Schmidt et al.
2018)) Fix o < cid's for the universal constant C1. and samples (X1, 81). (Xn. Vn.) drawn d.2.d from the (μ,, a -Gaussian model with |||||| = vd (i.e., Ma = for all dimensions E {0, ......... d)). Schmidt et al. (2018) prove that the weight setting w- Σ i=1 W: yields an -robust classification error of at most 1% for the linear classifier fa d {+1} instantiated as (w) sign WT (x)x if
1,
for e < P
7 Uze Vd. for 1o S 5
2
for a universal constant c2.
Note that the instantiation of w must change with choice of e and d. We can leverage the weight settings function of n and d to give definition of manifold-gradient mutual information.
4

---

Under review as a conference paper at ICLR 2022
C ==
C2 102
1(M 1l..)e.. (bits)
0.2
0.000
0.000
0.180
0.180
0,250
0250
0.1
10
10a
10a
10
10a
10a
d
d
Figure I: a) Average per-dimension mutual information (1) over dimension for values of 0o and e in Equation 13 log-scale d-axis with d [5, 2000), average over ten seeds. The approximate mutual information higher for robust and standard models at lower d regardless of C2 and choice e.
3.1 MANIFOLD-GRADIEN MUTUAL INFORMATION
Notice the classifier sgn(-) in Definition 3.5 is discontinuous X = 0 any dimension k. Instead
consider the sub-gradie uub-gradient of the classifier X < 0 and Xx 0. In either case (non-robust or robust), the input sub-gradient for fa (x+) is defined dimension-wise for our isotropic Gaussian as Vx; fw. sign Wa. Since the weight of each dimension is Gaussian distributed with N(ux, r²), we can define the distribution of gradients as G Rademacher (IP Wi. We 2 0]). Using this fact, we define manifold-gradicn manifold-gre gradient point-wise joint probabilities between gi and X₁: each dimension for the sub-gradient cases where X;; 0 and X 0, 2) defining the
mutual information in three parts: 1) defining the
marginal probability under the gradient, and 3) the marginal probability under the manifold. The complete derivation of the joint and marginal probabilities can be found in Section of the Appendix. The three parts are used the standard definition mutual information (Cover& & Thomas 2006).
Notation. Fix a c for both cases. We denote the sub-manifold sampled from the positive (y 1) and negative = 1) classes M and M respectivvel. For brevity we label x 0 as x and X2 < 0 as x
Definition 3.6 Manifold-Gradienn Mutual Information). We define the manifold manifold-gradient mutual information, based the standard definition of mutual information from information theory (Cover Thomas 2006), as
I(M, (M, ((M =
/ p(1,x") log( Pe (1)ppx(x)))
p(1,x*)
dxx +2 p(-1,x*) log( p(-1,x*)
dx
pg(-1)pm((e
(2)
with the total unnormalized mutual information defined as the summation over dimensions (due dimension co-independence) 9), Dd I(M,
3.2 MUTUAL INFORMATION AS A FUNCTION OF DIMENSIONALITY
To provide numerical support for Hypothesis] 1 run experiments using the Riemann approximation of Equation 13, provided in the Appendix as Equation [5 We estimate the average per-dimension
mutual information, (M, 9), J(M.0). for the case where x E Rd while varying the dimen-
sionality term d E [5, 2000) against values of c2 E {1,1000 100) and E {0.000, 08180, 0.250]. The values 62 represent two multiplicative factors for number of samples in robust models (Equation In experiments, multiply each branch Equation by a large constant (10*). We run the approximation over ten different random seeds and show the average with standard error shaded.
target error within 10-1 (c.g., 0.9 < pg((1 + ps(-1) < 1.0). Thus
The estimation result is shown in Figure D with log-scale x-axis. Regardless C2 and c, lower values of the dimensionality evidence higher mutual information. We minimize variance of the estimate when C2 = 102 (right plot shaded area), which follows intuition due to the higher sample count the estimate.
5

---

Under review as a conference paper at ICLR 2022
Observation 1. Given reduced data dimensionality, robust model could increase (M, and lead to leaking better search direction through the gradient (e.g., act manifold distance oracle). This supports Hypothesis] 1
This can theoretically explain the high visual alignment observed empirically by Engstrom et al. (2019) Santuurra al. (2019) on robust models. From the security perspective, the NMD oracle acts as a side channel leaking sensitive information as a factor of the model robustness and data dimensionality.
4 ZEROTH-ORDER SEARCH THROUGH THE MANIFOLD DISTANCE ORACLE
According to Observation I, the true gradient and manifold of robust model have higher mutual information, and this is exacerbated by reducing the data dimensionality. Under our Markov chain assumption, this means an attack algorithm can act as a noisy manifold distance oracle, and this oracle could be upper bounded by the true gradient-manifold mutual information. Although the data dimensionality and robustness are controlled by the model designer, an attacker can search in arbitrarily lower dimensionality through cineunsion-reduction techniques, such autoencoder-bast -based attacks (Tu et al. 2019). In fact, in the image domain the intrinsic dimensionality of data can be lower than the true dimension (Amsaleg al. 2017). In order to connect the notion of manifold- -graddeen mutual information with on on-manifold adversarial samples of real datasets, we posit the following.
Hypothesis 2. Consider Observation 7 and Definition 3.3 (DPI), then due to the higher upper bound on I [M,, 9) and leaking better search directions, hhardllbed adversary can minimize d' in expectation on robust models when the gradient estimate dimensionality is reduced.
In the most common problem setting, the adversary is interested attacking a K-way multi- class classification model Rd - {1...., K}. Given an original example Xo. the goal is to generate adversarial example x such that x is close to Xg and f [x) + fxxo), where closeness is often approximated by the ny-norm of x Xg. In the gradient-level setting, we require the gradient
vf(-). However, in the hard-label setting we are forced to estimate
0f(x) without access to V f.(.). 4x
only decision evaluations of f. Rather than optimizing the step function f. hard-label attacks minimize the continuous function g()), which is an estimate of the distance to the nearest decision boundary in the direction 0. We evaluate the effect of dimension reduction 2020) and HopSkiplumpAAttace (HSJA) (Chen et al.. 2019), as both are considered state-of-ther art in the literature, and rely minimization of g(-)- We provide brief overview of their formulation in Section A.2 of the Appendix, and leave details to the respective authors' work. Alternative hard-label attacks. such RayS by Chen & Gu (020)), do not rely on the explicit zeroth-order gradient estimate from the model. This style of attack behaves differently since it can adapt to the problem dimension independent of the true gradient, which we demonstrate in Section of the Appendix.
Oign-OPT attack (Cheng et al.)
4.1 DIMENSION-
HEROTH-ORDER SEARCH
To test Hypothesis 2 modify existing hard-label attacks to produce dimension-redunn variants. This scheme enables dynamic scaling of the effective dimensionality regardless of specific attack formulation. In practice we implement the reduction through an encoding map E Rd + IRd for reduced dimension d' and decoding map D Rdd' + Rdd In general the adversarial sample is created by Xo + (D(O')) ||D()'))) where 0' E Rdd and is optimized depending the respective attack (e.g.. Oig and HSJA), and as before, g is a measure of distance to the decision boundary in direction D(0'). The mapping functions can be initialized with either an autoencoder (AE), or pair of channel-wise bilinear transform functions (henceforth referred to as BiLN) which simply scales the spatial dimension of the input up or down. This represents two distinct methods to search over super-pixels
D(e')
the image, which either rely on an approximate description of the manifold (AE), or instead exploit the known spatial co-dependence of images (BiLN). The implementation and training details of the AE variant can be found in Section A.4.2 of the Appendix. To study implement random variant of
the effect of dimension-reduueee BiLN (Rand) which samples a subset of coordinates uniform- -aaforrm-randoly from the source image as the dimension-reduced version, then replaces the pixels at these coordinates with those from the gradient
without semantic information,

---

Under review as a conference paper at ICLR 2022
estimate. This is meant to show the effect of discarding some semantic information (e.g., spatial correlation) in the update.
4.2 ESTIMATING MANIFOLD DISTANCE
We leverage three proxies of manifold distance in order to test Hypothesis 2 The Learned Perceptual Image Patch Similarity (LPIPS) acts as a proxy for manifold distance, d', and computes a distance that correlated well with human perception in human studies (Zhang et al. 2018 Laidlaw et al.) 2021). We use the same LPIPS code and checkpoint provided by the authors. Fréchet Inception Distance (FID) (Heusel et al. 2018) is similar to LPIPS, and leverages the internal representations of deep networks as an approximate encoding onto the manifold. Although FID lacks human studies, [Heusel
studies,HHeusel et al. (2018) show it is viable for scoring the visual quality of synthetically generated images, which offers us a comparison against LPIPS. In addition to LPIPS and FID, we create an approximate encoding o' by taking the encoder of trained autoencoders for each dataset, which can be used to compute Ls distance between encoded samples. In other words, this lets us compute [xx'(x)) - o' [x) for benign sample Xy and adversarial sample x. The results on FID and our trained autoencoder were consistent with LPIPS, so they are described in Section A.5.9 of the Appendix.
Finally, if hard-label gradient estimates on real-world data resulted in sample close to the approx- imate manifold, we could say the gradient estimates leveraged noisy mutual information, which may be upper bounded by the clean mutual information (Hypothesis D. This would manifest in a lower gradient deviation, or in other words, the distance between the true gradient and gradient estimate at the first attack step. We can further infer that the adversarial training effectively smooths the sampled data manifold (which generates from true manifold) by augmenting perturbed data samples during training. The smoothing yields well-defined boundary that aligns with salient input changes (Santurkar et al.) (019)). and should further lower variance of the gradient estimate compared natural models, which improves the baseline performance of an attack. We test this by calculating per per-pixel gradient deviation llg- for true gradient g (in the direction of the adversarial label), first "
gradient estimate g. estimate height H, and estimate width W. When taking the true input gradient in the direction of the adversaria label, we the victim model's original criterion to calculate the gradient, which was cross-entropy for all models in our evaluation.
5 RESULTS & DISCUSSION
We test Hypothesis by comparing two SotA hard-label attacks with their compatible dimension- reduced variants, against both natural and robust models. First show empirical evidence of the relationship between manifold distance and dimension-reduced attacks in Section B.TT [.T] Next in Section 5.2. we investigate the result of Section 5.1 from the perspective of reducing error in the gradient estimate. Finally in Section 5.3
we show how these observations inform better attack design.
Setup. We perform experiments using CIFAR-10 Krizhevsky 2009) and ImageNet (Krizhevsky let al. 2012) for RGB image data. The natural CIFAR- network is the same implementation open- sourced by Cheng et al. (2020). The architecture for ImageNet is the Resnet50 network taken from the PyTorch Torchvision library, and the accompanying pre-trained weights act as the natural model] l In addition, we leverage the representative adversarial training technique proposed by Madry et al. (2017) (and their c and ImageNet. The BiLN variants downscale to 16 16 for CIFAR-10 10, and 32 x 32 for ImageNet. We use Lnom versions of attacks for all experiments. and the same e values for natural models as the robust CIFAR-10 and robust ImageNet (hereafter referred to as Madry CIFAR- and Madry ImageNet). All attacks run for 25k queries without early stopping For brevity, we only show results for the untargeted case. Additional implementation details, such as hyperparameters and hardware used, can be found in the Appendices (Section A.4). Code for experiments is provided in the supplementary materials.
255 8 0.031 checkpoints for Loo setting) as the robust models for CIFAR- 10
correctly classified samples.
htm
7

---

Under review as a conference paper at ICLR 2022
Natural CIFAR-10
Madry
Natural
Madry ImageNet
Attack Variant
CIFAR-10
ImageNet
HSJA
0.132 0.098'
1.335 + 0.611
0.257 = 0.378
1.249 - 0.652
HSJA+BiLN
0.252 + 0.165t
1.147 0.535
0.170
1.205 0
HSJA+Rand
1.433 + 0.7471
2.384 + 0.5031
1.276 = 0.6491
1.183 + 0.596]
Sign-OPT
0,105 = 0.081
0.768 + 0.408
0.768 = 0.872
1.229 = 0.771
Sign- Sign-OPT+BiLN
0.225 + 0.146t
0.849 = 0.3971
0.176 = 0.204]
0.708 + 0,461]
Sign- Rand
0.440 + 0,464
1.021 0.5931
0.356 = 0.385
0.367 + 0.361]
Sign-OPT+AE
0.331 + 0.389t
0.660 0.302)
1.034 0.571
1.658 0.6381
Table I: Average LPIPS scores for each attack's s set of 200 adversarial samples on CIFAR- and ImageNet (lower is better). Arrows denote higher or lower score compared to baseline variant, and starred items indicate highest success rate.
Med. Benign Local ID
0.469
0.224
1.039
2.013
Natural CIFAR-10
Madry CIFAR-
Natural ImageNet
Madry ImageNet
Attack Variant
HSJA
6.65 0.61*
5.46 + 0.06
77.35 + 0.04
77.32 + 0.00
HSJA+BiLN
5.37 0.691
3,86 + 0.101*
55.12 + 1.371*
56.14 3.22 + 2.73]
HSJA+Rand
11.33 + 7.41f
2.01 + 1.65]
72.19 + 59.98]
Sign-OPT
3.72 + 0.99
0.71 + 0.38
1.70 + 1.01
0.55 + 0.18
Sign-OPT+BiLL
3.71 + 1.02]
0.78 + 0.351
1.83 + 0.97t
1.74 0.561
Ragn-OPT+Rand
8.21 6.671
2.32 2.071
37.54 1 46.201
6.72 1 1.544
Sign-OPT+AE
4.66 0.861
2.48 0.321
36.83 1 0.151
36.87 0.311
Table 2: Average per-pixel gradient deviation natural and robust CIFAR-10 (unit of 10 and ImageNet (unit of 10-2) over 200 samples. Top row lists the median Local Intrinsic Dimensionality (LID) of benign samples from the dataset. Arrows denote higher lower deviation compared to baseline variant, and starred items indicate highest success rate.
5.1 MANIFOLD DISTANCE
LPIPS results are shown in Table [ with colored arrows denoting either lower distance than baseline variant (green arrow), or a higher distance (red arrow). Generally, the dimension-reduced variants lower the proxy of manifold distance on ImageNet more often than on CIFAR-10 (green arrows). The random sampling variant (*-Rand) discards the semantic priors of the estimate, and in fact it achieved the lowest SR AUC scores, despite having lower scores. Our results using LPIPS are consistent with -. distance of the manifold approximation (Section A.5.9), and Fréchet Inception Distance (Section A.5.8), which all demonstrate tendency to be lower with dimension-reduced attacks.
Observation 2. Dimension-reducee hard-label attacks can have lower LPIPS score, Tes approxi- mated distance, and Fréchet Inception Distance (and thus lower manifold distance) on robust models if they preserve semantic priors in the update, which supports Hypothesis 2
5.2 GRADIENT DEVIATION
The results for gradient deviation are shown in Table 2 Notably, an attack can have high gradient deviation despite low LPIPS score (AE case, bottom row). Likewise, low deviation does not imply successful attack, as we show later with the Rand variant (rows three and six). We investigated why Madry ImageNet did not always have lower gradient deviation, which we posit is due to having higher true dimensionality. For the benign samples of each dataset we estimated the Local Intrinsic Dimensionality (LID), which was proposed to estimate true data dimensionality in a region around samples (Amsaleg et al. (017). In the top row of Table 2 we find the median LID is similar between natural and robust CIFAR- 10, but much higher on robust ImageNet than natural. Since our results of Section 3 suggested that higher problem dimension reduced mutual information, the Madry ImageNet model reduces the leakage through the NMD oracle through higher true data dimensionality. We leave a deeper analysis of this direction for future work. Results additional
suspect
8

---

Under review as a conference paper at ICLR 2022
Natural CIFAR-10 E= 0.031
Madry CIFAR-10 8 0.031
Natural ImageNet
Madry ImageNet 0.031
E == 0.031
BILN HSJA
Sucess Rat
BILNIASIA 32
Raad HSSN 16
Rudd HSAA RHSI 32
0.25
0.25
0.00
0.00
Stg-OOFf
S
0.75
Rand Siani
0.75
BILNI Siga
Suzena
0.50
AEsSien-OFT
BiL.N Sin-OPT
0.50
SEl-Siga OPT
Randh Sigs OPT 3:
0.25
0.25
0.00
0.00
10000
20000
0
10000
20000
10000
20000
10000
20000
of queries
of quesies
A quesies
# of queries
(a)
(b)
Figure Success rates across attacks over 200 samples on CIFAR-I0 (a) and ImageNet (b).
robust CIFAR-IO models are provided in Section A.5.2 of the Appendix, which exhibited a similar trend of lower gradient deviation. Sign-OPT has universally lower gradient deviation than HSJA, which aligns with findings Liu et al. (2020).
The gradient deviation is universally lower on the robust CIFAR-10 model for BiLN attacks (rows two and five). For ImageNet, deviation on robust models is either lower or similar (rows one, two, four, and seven).
Observation
5.3 INFORMING PRACTICE
We have shown that dimension reduction has unexpected consequences in terms of manifold distance, and on CIFAR-10 10 and some ImageNet cases, leads to lower gradient deviation on the robust model. We finalize our contribution by providing a comprehensive evaluation of the attack success rates in Figure against number of queries. The plots are quantified by taking their max max-normalized Trapezoid rule area-under-curve (AUC) For comparison, the highest AUC scores are starred in the previous tables. Our dimension-reduced HSJA+BiLN variant (yellow line) surpasses the previous SotA hard-label attack for ImageNet, HSJA, on both natural and robust models. This variant also exhibited the lowest LPIPS score across attack variants. However, lowest LPIPS score does not imply highest SR, evidenced with HSJA+Rand on natural ImageNet (brown line, AUC= 0.077) and Sign- OPT variants on either dataset (e.g., yellow line in Madry ImageNet, AUC- 0.215). Low gradient deviation does not imply higher attack success, evidenced by Oign in Table for Madry CIFAR- 10 (AUC= 0.156) or HSJA+Rand and Sign-OPT+Rand (AUC= 0.088 and AUC= 0.092, respectively). The Rand variants, combined with our findings so far, allow us say the following.
For
Observation 4. Successful attacks exhibit preservation of leaked semantic priors. Measures of manifold distance such as LPIPS tend to be lower on fimension-reducee attacks, independent of variance in the gradient estimate.
We posit that minimizing gradient deviation through correction of estimator bias alone could be misleading, since the semantic information provided by better NMD oracle (due dimension reduction) can potentially improve the gradient deviation. Although our theoretical analysis focuses on robust models, we suspect future hard-label attacks may treat as useful prior, which carries with it implications about when to deploy robust models in society. On the contrary, natural models will respond to any input changes, even they are semantically meaningless (Santurkar et al. 2019). so depending on the adversary's 's goal (e.g., evasion or information leakage), they could be less useful in the hard-label setting.
Tables with all normalized SR AUC scores are provided in Section A.5.3 of the Appendix.

---

show over Under review as a conference paper at ICLR 2022
6 CONCLUSION
Despite the recent progress in zeroth-order attack methods, open questions remain about their precise behavior. We develop an coormationntthoretti analysis that sheds light on their ability to produce on-manifold adversarial examples. Through experiments real-world datasets, two-fold increase attack success rates by leveraging new findings about manifold distance and gradient deviation. With knowledge of the manifold-gradiess relationship. it is possible to further refine hard-label attacks, and inform a better evaluation of model robustness. Given the availability of larger datasets in the future, method may turn the strength of deep learning, which is efficiently extracting patterns in large-scale data, into a weakness.
REFERENCES
L. Amsaleg. J. Bailey, D. Barbe, S. Erfani, M. E. Houle, V. Nguyen, and M. Radovanovié. The vulnerability of learning to adversarial perturbation increases with intrinsic dimensionality. In 2017 IEEE Workshop Information Forensics and Security (WIFS), pp. 1-6, December 2017. doi: 10.1109/WIFS. ST09//IFS.2017.2250 2017.8267651.
Normand J. Beaudry and Renato Renner. An intuitive proof of the data processing inequality.
orXiv:1107.072 [quant-ph), September 2012.
arXiv: 1107.0740.
Wicland Brendel, Jonas Rauber. and Matthias Bethge. Decision-Basee Adversarial Attacks: Reliable Attacks Against Black Box Machine Learning Models. 1rXivv1712.0444 [cs. stat), December 2017. /ottt://arxiiie wwwp:/iiivrrrroooooooooo www.orggaaaao /1712. 04248
arXiv: 1712.04248.
Nicholas Carlini and David Wagner. Towards Evaluating the Robustness of Neural Networks. In Security and Privacy (SP), pp. 582-597, 2016. ISBN 978-1-5090-5533-3, doi: 10. 10.11////P20174499
arXiv: 1608.04644 ISSN: 108 1011601..
Nicholas Carlini and David Wagner. Adversarial Examples Are Not Easily Detected: Bypassing Ten Detection Methods. In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security AlSec '17, pp. 3-14, Dallas, Texas, USA, 2017, ACM Press. ISBN 978- 144003-50---- didio
4. doi: 14.1144/3128572.555 1285572.112272 URL httptttt/eee //l acm
F128572.31400
Nicholas Carlini, Anish Athalye, Nicolas Papernot, Wieland Brendel, Jonas Rauber, Dimitris Tsipras, Ian Goodfellow, Aleksander Madry, and Alexey Kurakin. On Evaluating Adversarial Robustness. arXiv: /902. 06705 [cs, stat], February 2019. URL http:://arrai..orrr////////22.. arXiv: 1902.06705.
Jianbo Chen, Michael I. Jordan, and Martin J. Wainwright. HopSkiplumpAttac:: Query-Efficient Recision-Based Attack. arXiv: 1904.02/44 [cs, math, stat), April 2019. URL http:://////a org/abs/1904 02144
arXiv: 1904.02144.
Jinghui Chen and Quanquan Gu. RayS: A Ray Searching Method for Hard-label Adversaiial Attack. arXiv:2006. /2792 [es, star], June 2020. URL http:://aaxiv...rr//////2/2/6 arXiv: 2006.12799
Pin-Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsich. ZOO: Zeroth order optimization based black-box attacks deep neural networks without training substitute models. In ACM Workshop on Artificial Intelligence and Security, pp. 15-26 2017.
Pin-Yt Yu Chen, Yash Sharma, Huan Zhang, Jinfeng Yi, and Cho-Jui Hsieh. Ead: elastic-net attacks to deep neural networks via adversarial examples. In Thirly-second AAAI conference artificial intelligence, 2018.
Minhao Cheng, Thong Le, Pin- Yu Chen, Jinfeng Yi, Huan Zhang, and Cho-Jui Hsieh. Query- -ufri-Efficient Hard-label Black- black-boxxaa At Optimization- based Approach. arXiy: /80, 007.04457 [cs, stat), July 2018. URL h /ttt:://arae httt:::///xxii..orr/aa//////// 00007.0445555 04457
arXiv: 1807. 900.00457.
10

---

Under review as a conference paper at ICLR 2022
Minhao Cheng, Thong Le, Pin- Yu Chen, Jinfeng Yi, Huan Zhang, and Cho-Jui Hsich. Query- efficient hard-label black-box attack: An optimization- based approach. International Conference Learning Representations, 2019.
Minhao Cheng, Simranjit Singh, Patrick Chen, Pin-Yu Chen, Sijia Liu, and Cho-Jui Hsich. SIGN-
OPT: A QUERY-EFFICIEES HARD-LABEL ADVERSARIAL ATTACK. The International
Conference on Learning Representations (ICLR), pp. 16, 2020. T https::/ nett/orruniddsSKIIOOW
Jeremy M. Cohen, Elan Rosenfeld, and J. Zico Kolter. Certified Adversarial Robustness via Ran- domized Smoothing. arXiv:1902.000 02918 [cs, stat], February 2019. URL http:://rrxxv..o//
abs abs/1902. 02918
arXiv: 1902.02918.
Thomas M Cover and Joy A Thomas. Elements of Information Theory. Wiley-Interscience. John Wiley & Sons, 2nd edition, 2006.
Logan Engstrom, Andrew Ilyas, Shibani Santurkar, Dimitris Tsipras, Brandon Tran, and Alck- sander Madry. Learning Perceptually-Aligne Representations via Adversarial Robustness. arXiv: 00945 [cs, stat), June 2019. URL
arXiv: 1906.00945.
Ryan Feng, Jiefeng Chen, Nelson Manohar, Earlence Fernandes, Somesh Jha, and Atul Prakash. Query-Efficieee Physical Hard-Label Attacks on Deep Learning Visual Classifica- tion. arXiv:2002.07000 [cs], February 2020.
07088
arXiv: 2002.07088.
Matt Fredrikson, Somesh Jha, and Thomas Ristenpart. Model Inversion Attacks that Exploit Con- fidence Information and Basic Countermeasures. Proceedings of the 22nd ACM SIGSAC Con- ference on Computer and Communications Security CCS '15, pp. 1322-1333, 2015. ISSN 15437221. doi: 10. 145/28 0772280013.222 0100.2813677. URL http:http://l.c... actp://lllc.....m org/citate ion. cfm? doid=2810100 03. 3677
ISBN: 978433333..25.
Justin Gilmer, Luke Metz, Fartash Faghri, Samuel S. Schoenholz, Maithra Raghu, Martin Wattenberg, and lan Goodfellow. The Relationship Between High-Dimensional Geometry and Adversarial Examples. arXiv: vrrXiv/801... 000.42774 [cs], September 2018. URL httt:://axxi...rtttttt 02774 arXiv: 1801.021 022744..
lan J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and Hamessing Adversarial Examples. 2014. ISSN 0012-7183. URL htt.:::/aaax.v.or//aaas///////// /et.b////111...5511 arXiv: 1412.6572 ISBN: 1412.6572.
Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. GANs Trained by a Two Time-Scale Update Rule Converge to a Local Nash Equilibrium.
arXiv:1706.0mm 000000080011111 [cs, stat), January 2018. URL htth::ttp//aaat org. abs 1706. 08500 arXiv: 1706.08500.
Andrew Ilyas, Logan Engstrom, Anish Athalye, and Jessy Lin. Black-box Adversarial Attacks with Limited Queries and Information.
08598 [cs, stat], July 2018. URL http: arXiv: 1804.08598.
//axxiv.org/ab...
08598
Ajil Jalal, Andrew Ilyas, Constantinos Daskalakis, and Alexandros G. Dimakis. The Robust Manifold Defense: Adversarial Training using Generative Models. arXiv:1712.0911 [cs, stat), July 2019.
U /ttt:://axxivv arxiv. org. abs//bl2 09196 arXiv: 1712.09196.
Kim Jungeum and Xiao Wang. Sensible Adversarial Learning. 2020. URL
https:/
openreview www.eet//dde /eeet/ddffanm wwtppdddddld...... RVKwx
Alex Krizhevsky. Learning Multiple Layers of Features from Tiny Images. pp. 60, 2009.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey Hinton. ImageNet Classification with Deep Convolutional Neural Networks. In F. Pereira, C. J. C. Burges, L. Bottou, and K. Q. Weinberger (eds.), Advances in Neural Information Processing Systems 25, pp. Curran Associates, Inc., 2012. URL http:: wttpseerssiisis niws. wwwpppppppppppe///pppppppppppppt www.ggnett-clsssllceii.ooo wwwssificatiiiiicccc with htgpasafcccccttttttc---eeeoooooo oow.aooooooiiiiaaaaoaoeeeeeeeeee
4824 1824-imagene imw.eneteeett..mm
pdf

---

Under review as a conference paper at ICLR 2022
Cassidy Laidlaw, Sahil Singla, and Soheil Feizi. Perceptual Adversarial Robustness: Defense Against Unseen Threat Models. arXiv:2006. 222220066.2550 I2655 [cs, stat], July 2021. URL httt:://axxii.oort abs/2008 12655
arXiv: 1000612655.
Sijia Liu, Pin-Yu Chen, Bhavya Kailkhura, Gaoyuan Zhang, Alfred Hero, and Pramod K. Varsh- ney. A Primer on Zeroth-Order Optimization in Signal Processing and Machine Learning. (tt::2006.06222 [cs, eess, stat], June 2020. URLhttp: URLhttp:/aaxxi.org www.aiiw...g.aaaaoaooaaaaaaaaaaa wtwp:///...//.......o0 06224 arXiv: 2006.06224.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards Deep Learning Models Resistant to Adversarial Attacks. arXiv:1706.00 06083 [cs, stat], June 2017. URL htt.:ttt///axx..oo////////////00 06080
06083
arXiv: 1706.06083.
Seyed-Mohsen Moosavi-Dezfooll, Alhussein Fawzi, and Pascal Frossard. DeepFool: a simple and accurate method to fool deep neural networks. 2015. ISSN 10636919. doi: 10. 1009/
UtL.pttp///arrt...rrrraa/////// 0451/
arXiv: 1511.04599 ISBN:
9781467388511.
Yurii Nesterov and Vladimir Spokoiny. Random Gradient- Free Minimization of Convex Functions.
Foundations of Computational Mathematics, 17(2):527-566 April 2017. ISSN 1615-3375, 1615- 3383. doi: 10. s1 210208-015-92200 9296-2
U htt.:http//innee spr nger. wtwpg//ooooooooooooooo.ooooee.ee wtt.ooom..........
Nicolas Papernot, Patrick Medaniel, Somesh Jha, Matt Fredrikson, Z. Berkay Celik, and Ananthram Swami. The limitations of deep learning in adversarial settings. Proceedings 2016 IEEE European
Symposium Security and Privacy, EURO S and P 2016, pp. 372-38 172-387,4 2016. doi: 10. 10.1109/ EuroSP:2016.36. /tLpttt:://rxxxv. httpaaxiiv..rraabaee/e 9781509017515.
07528
arXiv: 1511.07528 ISBN:
Pouya Samangouei, Maya Kabkab, and Rama Chellappa. Defense-gan: Protecting classifiers against adversarial attacks using generative models. International Conference on Learning Representations, 2018.
Shibani Santurkar, Dimitris Tsipras, Brandon Tran, Andrew Ilyas, Logan Engstrom, and Aleksander Madry. Image Synthesis with Single (Robust) Classifier. arXiv: arXiv:1906. 1et...906999955 [cs, stat), June 2019. abs / 1906. 09453
URL
arXiv: 1906.09453.
Ludwig Schmidt, Shibani Santurkar, Dimitris Tsipras, Kunal Talwar, and Aleksander Madry. Adver- sarially Robust Generalization Requires More Data. 1rXiv:/804. / 11285 [cs, stat], May 2018. URL
http:://axiv... www.arwwwww..o.aaooomoo abw.r//////////..../. 11285 arXiv: 1804. 1285.
David Stutz, Matthias Hein, and Bernt Schiele. Disentangling Adversarial Robustness and General- ization. IEEE Conference on Computer Vision and Puttern Recognition (CVPR), pp. 12. IEEE Computer Society, 2019.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. pp. 1-10, 2013. ISSN 15499618. doi: 10. 10.102///22009208. /RLphtt::///rxee org hbtp:/bb//1111 6199 1549-9618.
arXiv: 1312.6199 ISBN:
Christian Szegedy, Vincent Vanhoucke, Sergey loffe, Jon Shlens, and Zbigniew Wojna. Rethinking the inception architecture for computer vision. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2818-28221 2016.
Thomas Tanay and Lewis Griffin. Boundary Tilting Persepective on the Phenomenon of Adversarial Examples. arXiv: 1608.07690 [cs, stat), August 2016. /tt.:tt///ai...orrraa////////
07690 arXiv: 1608.07690.
Florian Tramer, Nicholas Carlini, Wieland Brendel, and Aleksander Madry. On Adaptive Attacks to Adversarial Example Defenses. arXiv:2002.08344 [cs, stat], February 2020. URL http: 7/ a rxiv, wwwp..org//ab///22..00 08347
arXiv: 2002.08347.
12

---

Under review as a conference paper at ICLR 2022
Florian Tramèr, Fan Zhang, Floriantra Er Epfl, Ari Juels, Michael K Reiter, and Thomas Ristenpart. Stealing Machine Learning Models via Prediction APIs. 2016. URL https?
7/www. www.ux. org/ wtt.://nww...///ooeeeeeeeeeeeeee
presentation//ramme ISBN: 978-19199991999
Chun-Chen Tu, Paishun Ting, Pin-Yu Yu Chen, Sijia Liu, Huan Zhang, Jinfeng Yi, Cho-Jui Hsieh, and Shin-Ming Cheng. AutoZOOM: Autoencoder Basedd Zeroth Order Optimization Method for Attacking Black-Box Neural Networks. Proceedings of the AAAI Conference on Artificial Intelligence, 23:742-749, July 2019. ISSN 2374-3468, 2159-5399
doi: v0.16009/aaivvv330011 3301742. URL https: www.aaaaa.... org. / ndex htt.://pppp...aaaaaaaaaaaaaa////
AAA
Haichao Zhang and Jianyu Wang. Defense Against Adversarial Attacks Using Feature Scattering- based Adversarial Training. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' textuuotesine Alché-Buc, F. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems 32, pp. 1831-1841. Curran Associates, Inc., 2019.
Haichao Zhang and Wei Xu. Adversarial Interpolattion Training: A approach for improving model robustness. 2020. URL
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric P Xing, Laurent El Ghaoui, and Michael Jordan. Theoretically Principled Trade-off between Robustness and Accuracy. PMLR, pp. 11, 2019.
Richard Zhang, Phillip Isola, Alexei A. Efros, Eli Shechtman, and Oliver Wang. The Unreasonable Effectiveness of Deep Features as a Perceptual Metric. In 2018 IEEE/CVF Conference on Computer Vision and Puttern Recognition, pp. 586-595, Salt Lake City, UT, June 2018. IEEE, ISBN 978-1- 1- 5386-6420-9. doi: 10. 109/CVPR. 201.C 8.00068. #icument/85781655
URL httpthts///eeeppppp/b/p wetpeeeeppooreeeeeeeeoo .org..rg//
Xiao Zhang, Jinghui Chen, Quanquan Gu, and David Evans. Understanding the Intrinsic Robustness of Image Distributions using Conditional Generative Models. arXiv:2003.008: 00077700008888888 (cs, stat), February 2020. URL / //axxiv wttp/ag////////o 2003. C0378
arXiv: 2003.00378.
13

---

Under review as a conference paper at ICLR 2022
A
APPENDIX
A.1 DERIVATION OF MANIFOLD-GRADIINN MUTUAL INFORMATION (MT)
We define the manifold-gradien point- joint probability in case-wise manner, for the respective values under g E (-1,1) and x E Rd We are concerned with the sub-gradient cases where x > (denoted x+) and x < 0 (denoted x which correspond to fixed values of g based class means with E {-1, }. This gives for each dimension k;
p(g: 1,x²)
exp
k
14
20
2
(3)
X +
p(ge 1,x;)
exp
20 2T
2
p(g. -1,x,)
1
exp
x
+
14
20 v 2
2
(4)
1
x
p(g: -1,,x,)
exp
20 v 2m
2
Since the Schmidt et al. Gaussian mixture is created symmetrically (the probability mass is evenly split between the two classes i.e., the mixture comprises one Gaussian offset by pa and mirrored at Xx = 0) we can simplify to
)
pg: x,,,,
exp
x
pkk
(5)
20 2 2T
2
p(gx -1,x,)
exp
1
k
pk
2
2
where X Nyy 14, M.. In words, Equation 6 the symmetrical tail of the Gaussian mixture marginal while Equation 5 the remainder of the mixture.
Similarly, a point-wise gradient is given as the Rademacher outcome ga E (+1). The choice of directly influences the marginal probability over the manifold. The marginal probability over the manifold can given as the Riemann approximations
2
1
x
14
PB 1).
exp
A
20
20T2
2
1=1
and
n
k +
pglgi = -1) 20 / 2m
exp
A
(8)
i=1
with A; xt, xt for arbitrary X E [x] 1, x
and is controlled by the hyper-parameter
The marginal for the manifold under the gradient is given similarly
(x() = p(gk
1,xtt + p(ge = -1, xx,
x
2
1/xx +
x
pbk
(9)
exp
exp
0V24
2n
14

---

Under review as a conference paper at ICLR 2022
where x > 0 for all dimensions k. Denote the sub-manifold sampled from the positive (y 1) and negative (y - classes as MM and . respectively. Our definition for manifold-gradee mutual information is based the standard definition of mutual information from information theory (Cover & T'homas 2006).
I(M,g)e.. J.m P(gk. xx. log(
p(gk: xx)
dgæ dx
(10)
Pg gg (x+)
where is treated as hyper-paramette controlling the value of in pg())). By substitution into Equation 10 we have
IMM = S,,, p(1, log(
p(1,xk)
dxc
pe (1(1)p.M(X5
(1I)
S p(1,, log(
p(-1,x1 1, xCk) p (xx)
dx::
This is split further similar to true positive, true negative, false positive, and false negative, as
I(M,9)a. = Sur. Mm p(1,x;) log(
p(1,xt)
Pe Pc (M(1)) dx
+ S x(1, log(
p(1,xp. xx)
dxc
PG (1 1P
(12)
+ S.v. Mi
pl (111, Xx
p(-1,x7 log(
dx
Pg 1)pm (x
+ / M 1(11,x log(
pl 11,
ddc
Pg
( pG(-1)p.Mxx,
and simplified due symmetry 0 as
I(M = ʃ p(1, log(
p(1, xxxxx
dx
PGl (c((1)pM(x))
(13)
+2 / M+
p( 10(11, X
p(-1,x) log(
dx
pg p
The total un-normalized mutual information is given by the summation over dimensions [(M, 9). =
Ex=1 [MM,)) ().k. Notably the cases for each possible scenario under detection theory are repre- sented. Each case bounded by the results of Schmidt al.) (2018). By substitution from each marginal and joint probability in Equations and respectively, we have the closed form solution for mutual information.
This leads to the Riemann approximation of Equation 13
p(1, xx,e)
(1, = Σ p(1, X x log
A
Pg (1)P)) (xT,x)
1=1
(14)
p( 11-1, xxxxk
p( ( x + Σ
log(
A,
Pg ( 1) (x:
with A; = x variate Gaussian (Cover & Thomas 2006), the final mutual information the summation over each dimension,
x for arbitrary positive x E [x_ 1,k xtx) Since x is a standard multi-
15

---

Under review as a conference paper at ICLR 2022
p(1,)7,))
I(, 2
Σ
p 1 x log(
Pg ()())uM(X) )
(15)
7
p( p(-1,x
p-11, log
P (x D
A.2 HARD-LABEL ATTACK FORMULATION
Contemporary hard-label attacks variants of random gradient-free method (RGF) (Nesterov & Spokoiny 2017). a gradient estimator which yields the estimate g over q random directions {u, J/
OPT-Attack For benign example Xg, true label you and hard-label black box function f Rd {1...., K}. Cheng et al. (2019) define the objective function F + R as a function of search direction 0, where the optimal solution is g(0"), the minimum distance from Xo to the nearest adversarial example along the direction 0" For the untargeted attack, g(0) is the distance any decision boundary along direction 0, and allows for estimating the gradient as
Σ (-0
1
g
Bu.) 9()) UI
(16)
8
where 3 is small smoothing parameter. Notably, g is continuous even f is a non-continuous step function.
Sign-OPT Cheng et al. (2020) later improved the query efficiency by only considering the sign of the gradient estimate,
(g(0) =
Σ sign (g(0 Bui) g(0)) u.
(17)
We focus the Sign-OPT variant, since the findings are more relevant to the current state-of-theeart.
HopSkipJumpAAttad Similar to Sign-OPT, HopSkiplumpAttuck (HSJA) (Chen et al.) 2019) uses zeroth-order sign oracle to improve Boundary Attack (Brendel et al. 2017). HS.AA lacks the convergence analysis of Sign-OPT and relies on one-point gradient estimate. Regardless, HSJA competitive and can excel in the Loo setting.
Dimension-reduced Sign-OPT & HSJA. In general, for attacks relying on the Cheng et (0199
formulation, the update in Equation 16 becomes
(0' + Bu() g(0") u
g
(18)
1=0
for the reduced-dimension Gaussian vectors {u] E RRd } for integer < dl and direction O' Rdd The reduced-dimensiee
direction 0' is initialized randomly with 0' ~ N((, 1) for the untargeted case, or for the targeted case as = E(x),, where x, is a test sample correctly classified as target class t by the victim model. This scheme also applies to HSJA, since HSJA performs single-point sign estimate. As in the normal variants, g is used to update 0'.
A.3 MAIN PAPER BLOCK DIAGRAM
block diagram of assumptions, claims, and observations is shown in Figure
16

---

Under review as a conference paper at ICLR 2022
External Result:
External Result: Semantic leakage robust model gradients [Santurkar' 19. Engstrom"
External Result: Robust models require data [Schmidt
LPIPS corralates humen perception (Zhang at Laidlaw al.211]
External Result: Robust model dectaion boundary sligns
Data Processing Inequaiity (DPI)
with salient
[Beaudry and
Renner' 12]
Input changes [Santukar 19).
Section 3
Assumption: Manitold, Gracient and gradient Markov Chain
Assumption: Models learn dimensian representation of and encode priore.
Section 3
Section
Hypotheeis 1: Manifald-Gradient Manifold-GG Gradient
Hypothesis 2: adversary can sample closer data manifold.
MI higher on robust models.
Table
Figure Section
Observation 3: Dim. attacks decrease estimate variance (rows 5).
Observation 1: MI can increase with dimension.
Section 5.1 Table
reduced hard label attacks have lower PIPS, soproxinsted menifold distance (Lp-norm), and FID score they preserve priors.
Section Figure 2
Successful attacks preserve priore, tend to exhibit lower LPIPS score.
Figure 3: Block diagram summarizing the assumptions, claims, and observations of the main paper.
17

---

Under review as a conference paper at ICLR 2022
A.4 IMPLEMENTATION DETAILS
A.4.1 HARDWARE AND ATTACK HYPERPARAMETERS
All experiments in the main paper were performed on an internal performance compute cluster equipped with NVIDIA Tesla V100 Tensor Core GPUs and high-speed non-volatile flash storage. In total 16 GPUs, 1TB main system memory, and 40 Intel Xeon CPU cores were used to run experiments completely.
Depending on dataset dimension, HSIA requires tuning of parameter ry for best performance. CIFAR-10 10 we used y 10.0. For ImageNet, it was necessary to set Y 2 1000.0 to re-create the published results of the regular variant (Chen et al.) 2019). Due to similar performance we use 1000.0 for regular and dimension-reducet variants. We note that the fimension-redueee variants like HSJA+BiLN were less sensitive to y, performing similarly regardless the setting.
A.4.2 ADVERSARY AUTOENCODER
We are primarily interested in the effect of reduced search resolution on attack behavior. Thus in this work, given candidate direction O' and magnitude (or radius) r, the adversarial sample in the AE case is the blending (1 Xn + rD (E(x)) + 0')
For AE attack variants, we implement the same architecture described by Tu al. (019). Specifically leverages fully convolutional network for the encoder and decoder. Every AE is trained using the held out test set,
assume disjoint data between adversary and victim.
The adversary's s AE is tuned to minimize reconstruction error of input images, so the output quality of the AE will depend the adversary's ability to collect data. We assume the adversary only has access to the test set, which tends to be considerably less informative than the training set. This crude manifold approximation can manifest as an additional layer of distortion on top of adversarial noise. With BiLN, no additional training is required, so it synthesizes search directions independent of the adversary's manifold description (i.e., possible extracted knowledge about test samples).
ImageNet samples are downsized to 128x 128 before passing to the AE, and the output of the AE is scaled back to 224x224, as described by Tu et al. (2019).
A.4.3 DATA SAMPLING
Original samples are chosen from the test set using the technique from Chen et al. (2019): on CIFAR-10, five random samples are taken from each of ten uniform-randomly chosen classes (i.e., 50 total samples). On the ImageNet dataset, ten random classes are uniform uniform-random)) randomly chosen and ten random samples taken from each (100 total samples).
A.5 SUPPLEMENTAL RESULTS
A.5.1 QUERY VS. DISTORTION PLOTS
We show the model queries against attack distortion measurement Figure 4 to accompany the results in the main paper. The distortion is much higher and stays higher with Rand variants, due to discarding important semantic information. The plots evidence that BiLN variants (yellow lines) offer simple yet effective way to improve the query efficiency of the hard-label attacks.
A.5.2 GRADIENT DEVIATION ON ROBUST CIFAR-10
In Table we show supplementary gradient deviation results for CIFAR- 10 using different defense mechanisms or robust models. In general they exhibit the same trend as our main paper results, which that dimension-reduuce attacks manage reduce gradient deviation across each robust model.
18

---

Under review as a conference paper at ICLR 2022
Natural CIFAR-I0 10
Madry CIFAR-I0
Natural ImageNet
Madry ImageNet
Distortion (L.)
0.3
Distortion (Lw)
0.200
Razdi BBM
H85A
HSIA
0.2
HSAA
0.10
0.1
0.05
0.25
Distortion (L.)
0.3
BILN-Sum-OPT 16 (St
Sigs OPT
Distortion (La)
0.20
Sep-OPT
BiLN-Sipn-er DPT 32
Randi Siga OPT
0.2
Al--Siga-Ort
0.10
0.1
0.05
10000
20000
10000
10000
20000
10000
20000
of queries
of queries
of queries
of queries
(b)
Figure 4: Query vs, distortion plots for a) CIFAR-I0 and b) ImageNet, corresponding to the success rate plots in the main text. Dashed lines denote the value of c.
TRADES
Interpolation
Feat. Seatlsing
SENSE
Zhong et al. 2019
Zhang
2020
Zhang & Wang 2019
Jungeum Wang
0.05-42+0 0on1
0.9542++0.
0.0541+0
0.0556+0.00
IISAA BBLN
0.0395:+00 0001
0. 0.0393++0. 8001
0.0401+0 0084
0.0389=0.00m o065
HSZA Rondd
0.008 004
0. 0.002 D05
0.216 000
0.222
Sign-OPT
0.004222 coos
D. 0.00399.0.0m DO0T
0.001910 0004
0.008310-0104
Sign-OFT BILM
0.0826620
0007
0.002331-0.00 pons
0.0020120 0004
0.007520.011
D.0U7::0.000
0.004
0.006
0.0925
Sign-PP444F
0.02571:0 0002
0.028210 8002
0.02594:0 0000
0.0278.0..0m
Table Per-pixel gradient deviation measured across additional robust CIFAR- 10 models
A.5.3 SUCCESS RATE NORMALIZED AUC SCORES
Tables 5 and 4 show the max-normalized Trapezoid rule area-under-curve (AUC) measurements for the success rate plots of the main text. Highest scores are bolded. Notably, the HSJA+BiLN variant earns the highest score in almost all cases.
A.5.4 SUCCESS RATE SCORES
We provide the success rates over all samples at specific query intervals in Tables and
A.5.5
ATTACKING A SMOOTHED MODEL
Gaussian smoothing is technique of performing adversarial training with sampled affected by Gaussian noise. At test time, inference is achieved via a Monte Carlo search over many Gaussian- perturbed versions of the sample under test. The SotA time of writing, randomized smoothing proposed by Cohen et al. (2019). is good candidate for hard-label attacks since the true gradient of the smoothed model is undefined. We use the checkpoint corresponding to smoothing parameter 0.5 and 1.0. These results are shown in Figure 5 In general, the BiLN variant exceeds all other variants in the natural ImageNet case, with small improvement on the smoothed model. Although it can find samples closer to the smoothed e, only fraction are within the bound.
We observed that it is detrimental to set x = D(E(xo) + r0') or x D(r0') directly. Despite remaining on the data manifold by attacking it directly, the approximation of the data manifold is crude, which results in large distortion (tttz al. 2019)
19

---

Under review as a conference paper at ICLR 2022
Natural CIFAR-10
Madry
Attack Variant
CIFAR-10
HSJA
1.000
0.650
HSJA+BiLN
0.968
1.000
HSJA+Rand
0,033
0,088
Sign-OPT
0.763
0.171
Sign-OPT+BiLN
0,310
0.156
Sign-OPT+Rand
0.144
0.092
Sign-OPT+AF
0.312
0.300
Table 4: Success Rate (SR) Normalized AUC scores for CIFAR-10 SR plots of the main text. Higher is better.
Natural ImageNet
Madry ImageNet
Attack Variant
HSJA
0.867
0.470
ISJI++BiLN
1.000
1.000
HSIA+Rand
0.077
0.211
Sign-OPT
0.364
0.153
Sign-OPT+BiLN
0.376
0,215
Sign-OPT+Rand
0.070
0.033
Sign-OPT+AE
0.018
0.105
Table 5: Success Rate (SR) Normalized AUC scores for ImageNet SR plots of the main text. Higher better.
Natural ImageNet
Smouthing ImageNel
Natural ImageNet 3.0
Smoothing ImageNet
Distortion (La)
80
HSIA BENNHSSA 32
1.0
60
Rand
40
Sucees Rate
Nel 12 Rtadd-iSSA 12
0.6
0.2
0.0
Distortion (La)
60
80
Sigu OPT
Ruadt-Sin--PP
BLN 3P
0.8
1.0
Sign OPT
tit nrr RindeSiga Alt-Sig--P
40
0.6
10000
20000
10000
20000
10000
20000
of queries
queries
(b)
Figure 5: Results of attacking Smoothed ImageNet Cohen al. (019 in the L2 setting for a) query vs. distortion and b) query vs. success rate, Dashed lines denote the value of e.
A.5.6 ATTACKING WITHOUT GRADIENT ESTIMATE
We perform additional experiments with attack that does not perform explicit gradient estimate.
Chen & Gu (020) propose an alternative hard-label attack method which is to search for the minimum decision boundary radius from sample Xg, along ray direction 0. Instead of searching over Bd to minimize (0), Chen et al. propose to perform ray search over directions 0 E {-1, 1)"", resulting in 2d maximum possible directions. This reduction of the search resolution enables SotA query
20

---

Under review as a conference paper at ICLR 2022
Natural @
Madry @ 4k
Natural 11k
Madry 11k
Natural 25k
Madry
Attack Variant
@ 25k
HSJA
0.905
0.100
0.995
0.145
1.000
0.180
HSJA+BiLN
0.850
0.165
0.970
0.225
0.985
0.255
RSJA+Rand
0,040
0,020
0.020
0.020
0.040
0.000
Sign-OPT
0.515
0.030
0.795
0.040
0.890
0.040
Sign-OPT+BiLLN
0.235
0.035
0.310
0.035
0.355
0.035
Rign-OPT+Rand
0.060
0.020
0.200
0.020
0.180
0.020
Sign-OPT+AE
0.210
0.055
0.325
0.065
0.345
0.070
Table 6: CIFAR-10 succeess rate values at query intervals 4k, 11k, and 25k, for setting 255
Natural @
Madry @ 4k
Natural 11k
Madry 11k
Natural @ 25k
Madry @ 25k
Attack Variant
HSJA
0.550
0.105
0.850
0.130
0.965
0.165
HSJA+BiLN
0.835
0.240
0.965
0.290
1.000
0.335
HSJA+Rand
0.070
0.060
0.070
0.060
0.070
0.060
Sign-OPT
0,210
0,045
0.335
0.045
0.485
0.045
Sign-OPT-BiLN
0.240
0.055
0.345
0.065
0.445
0.065
Sign-OPT+Rand
0.050
0.010
0.070
0.010
0.070
0.010
Sign-OPT+AE
0.015
0.030
0.015
0.030
0.020
0.040
Table ImageNet succcess rate values at query intervals 4k, 11k, and 25k, for setting
205
Natural
Madry Adv.Tr.
RoyS
0.3
Distortion (L.))
Rill a-
BiLNaRay'S b-2
0.2
BiL.NaRayS bonk
ii.
0.0
10000
20800
10000
20000
# of queries
# of queries
Figure 6: Results for RayS on the CIFAR-10 dataset, corresponding to distortion against query usage (dotted red line denotes the value of e, shaded areas mark standard deviation).
efficiency in the Loe setting with proof of convergence. The search resolution is further reduced by the hierarchical variant of RayS, which performs on-the-fly upscaling of image super-pixels.
The intuition behind RayS attack is to perform a discrete search in at most 2d directions. Chen al. also perform hierarchical search over progressively larger super-pixels of the image. This has the effect of already upscaling on-the-fly (Chen & Gu 2020). RayS has the unique behavior of performing discrete search for the decision boundary, rather than an explicit gradient estimate. To achieve an appropriate reduced-dimension version of RayS, we modify the calculation of in Algorithm of Chen Gu (2020), which either speeds up upscaling by a factor (i.e., 8 = + a), extends the search through specific block index by factor 6 (increase block level at k 2*b instead of A = 2*).
The result of attacking CIFAR-10 with RayS is shown in Figure 6 The BiLN variants of RayS each have minimal effect on overall query efficiency (Insets 6 and 6 ii). This result of RayS not relying on explicit gradient estimation. When comparing the FID-64 score, the dimension--edueee variants of RayS do not have a large variation between them (Inset side-effect of the adaptive super-pixel search, which automatically scale the super-pixel size as the search progresses.
21

---

Under review as a conference paper at ICLR 2022
Natural CIFAR-10 10
Madry
Natural
Madry ImageNet
CIFAR-10
ImageNet
Benign
0.787 + 0.830
0.564 1.724
1.206 = 0.803
2.623 + 2.383
HSJA
8.014 +: 5.829
62.709 + 112.416
4.798 1 2.578
3.342 1 2.263
HSJA+BiLN
7.497 + 5.811
50.467 + 100.057
4.787 + 2.550
4.290 + 4.524
HSlA+Rand
6.156 + 6.053
15.745 + 24.195
5.191 = 1.948
3.132 + 2.489
Sign-OPT
7.240 + 5.006
51.191 + 100.080
1.747 + 1.988
3.707 + 3.660
SNgn-OPT+BiLN
6.308 + 4.079
47.355 + 119.958
4.547 + 2.118
4.808 + 4.873
Sign-OPT+Rand
5.576 + 4.178
12.792 + 13.546
5.364 + 1.757
4.867 = 3.369
Sign-OPT+AE
6.700 + 4.735
51.380 = 103.355
4.891 + 2.299
3.791 = 3.598
Table 8: Measurement of Local Intrinsic Dimensionality (LID) averaged over 200 samples.
A.5.7 LOCAL INTRINSIC DIMENSIONALITY
In Table we show the average Local Intrinsic Dimensionality Amsaleg et al. (2017) for each dataset and attack combination.
A.5.8 FRÉCHET INCEPTION DISTANCE
Unfortunately, the data manifold of real-world datasets is difficult to describe. This is an open problem in the study of Generative Adversarial Networks (GANs), since designers require that generator images are on-manifold (i.e., in-distribution Zhang et al. (2020)) to preserve semantic relationships between images. This has motivated the recently proposed Fréchet Inception Distance (FID) that acts as surrogate measure of the manifold distance over set of RGB image samples (Heusel et al. 2018). As an additional proxy for manifold distance, we run experiments that assume adversarial samples are synthetically generated images from the data manifold, which can later be compared to their unmodified counterparts on the true manifold using FID. As result, this estimation process is only available from the defender's perspective. Since FII) uses an Inception-V3 coding layer (Szegedy cct al. 2016) to encode images, the estimation correlates with distortion of semantic high-level features. Thus sampling closer to the data manifold will result in a lower FID score. The attacks in our experiments do not target the Inception- V3 network, so the FID metric will not rely on any internal aspects of the victim models.
FID score is calculated using the 64-dimensional max pooling layer of the Inception- V3 deep network for coding (denoted FID-64 in this supplementary material), taken from open-source implementation fl The choice of the 64-dimensional feature layer allows to calculate full-rank FID without the full 2,048 sample count of original FID, which is prohibitive based on the scale of our analysis. Since the coding layer differs slightly from the original FID-2048 implementation, the magnitudes will differ from those published by Heusel al. (0118.
The comparison of FID scores is shown in Table D for natural and robust models. The scores for ImageNet on pecension-reducee attack variants (italicized) are universally lower (as low as 0.014, bold), while on CIFAR- 10 the regular variants did not exhibit the behavior. We posit that the higher dimensionality of ImageNet (224 x 224) enables dimension reduction to be more effective than the lower dimension CIFAR-10 (32 x 32). In general, attacks have a higher FID score on robust models than natural models. This can be explained by the fact that robust models are more secure in a region around the original sample, as result the adversarial sample discovery is further away from the true manifold. The random variant (Rand) in rows three and six evidences that the preservation of semantic priors is important during the update, otherwise samples have high manifold distance. The regular variants of HSJA and Sign-OPT are capable of high FID scores on robust models. However, dimension-reduced variants have universal behavior to reduce the score in the robust setting, similar to the natural setting for ImageNet. AE variants exhibit higher FID score than BiL,, since BiL can rescale invariant of the adversary's manifold knowledge (c.g., only having knowledge of test set).
22

---

Under review as a conference paper at ICLR 2022
Natural CIFAR-10
Madry CIFAR-10
Natural ImageNet
Madry ImageNet
Attack Variant
HSJA
0.005
1.622
1.026
29.756
HSIA+BiLN
0.006t
0.373L
0.012
4.646 +
HSJA+Rand
2.1981
8.2561
3,4041
2.354
Sign-OPT
0.001
0.305
20,969
38,505
Sign-OPT+BiLN
0,0021
0,045L
0.0091
0.062.1
Sign-OPT+Rand
0.1411
0.2101
0.234|
0.156.
Sign-OPT+AR
0.3331
0.008.
1.5144
7.8694
Table 9: Fréchet Inception Distance (FID) scores for each attack's set 200 adversarial samples on CIFAR-10 and ImageNet (lower is better). denotes highest success rate (SR) AUC. Arrows denote higher or lower score compared to baseline variant.
Natural CIFAR-10
Madry
Natural ImageNet
Madry ImageNet
Attack Variant
CIFAR-10
HSJA
0.016 + 0.012"
0.162 + 0.099
0.030 + 0.046
0.170 + 0.119
HSJA+BiLN
0.033 + 0.024
0.156 + 0.096.,"
0.019 0.0174"
0.169 0.12
HSJA+Rand
0.334 + 0.1761
0.457 + 0.1011
0.309 0.1361
0.308 + 0.1411
Sign-OPT
0.015 = 0.013
0.137 = 0.088
0.096 = 0.118
0.152 = 0.112 0.112
Sign-OPT+BiLN
0.048 0.0391
0.191 0.103t
0.040 0.044)
0.171 0.1051
Sign-OPT+Rand
0.084 = 0.0921
0,214 = 0.100
0.082 0.077
0.087 0.059
Sign-OPT+AE
0.058 + 0.123t
0.094 + 0.068.)
0.235 0.2001
0.586 0.2991
Table 10: Loc distance between adversarial and benign samples projected to approximated manifold (using autoencoder trained on training data) for each attack's set 200 adversarial samples on CIFAR- 10 and ImageNet (lower is better). Arrows denote higher lower distance compared to baseline variant, and starred items indicate highest success rate.
A.5.9 Loo -NRM OVER APPROXIMATE MANIFOLD
We re-use the setup described in Section A.4.2 but train the autoencoders using the training data (defender's perspective) instead of test data (attacker's perspective). The results are shown in Table To The HSJA+BiLN attack variants were successful in lowering distance for both natural and robust ImageNet. Generally, Sign-OPT variants were most successful for lowering distance from baseline variant for both CIFAR-10 and ImageNet. The primary factor the dataset dimensionality, with dimension reduction having bigger impact on ImageNet than CIFAR-10 (green arrows in ImageNet are more widespread). Likewise, robust models always exhibit a higher distance than natural. This can be explained by the fact that adversarially trained models are more robust in region around the benign sample, thus the successful adversarial sample will be farther away.
A.5.10 VISUAL RESULTS CIFAR-10
We provide visual qualitative results for each attack on CIFAR-10 in Figure
A.
VISUAL RESULTS IMAGENET
We provide visual qualitative results for each attack ImageNet in Figure
23

---

Under review as a conference paper at ICLR 2022
Queries: Original
(350)
Original
(a) Sign-OPT on CIFARIO
(b) Sign-OPT on CIFAR10 (Madry Adv. Tr.)
Queries:
13867 00.0
25128 L- -0.5
Final (x50)
Queries: Original
13949 0.57
25383 0.57
Final (X50)
Original
-0.20
Lou 0.64
(c) BiLN+Sign-OPP CIFARIO
(d) BiLN+Sign-OPT CIFAR10 (Madry Adv. Tr.)
Queries:
972 T 0.30
14021 L =0.07
25356
Final (s50)
Queries:
900 L 0.77
15778 Zio 0.21
25084 L_ 0.00
Pinal (x50)
Origital
Tu 0.07
Original
AE+Sign-OFF OPT on CIFARIO
(f) AE Sign-OPT CIFAR1O (Madry Adv. Tr.)
9898 Y_ -0.01
25417 1_ -001
9898 -0.09
25417 0..0
Final (x50)
Original
-0.17
(150)
Original
D0445
(g) HSJA on CIFAR10
(h) HSJA on CIFARIO (Madry Adv. Tr.)
Original
-0.1
-001
Osiginal
00.52
-0.07
(i) BiLN+HSJA on CIFARIO
BiLN+HSIA on CIFARIO (Madry Adv. Tr.)
Queries:
11955 Jan -0.01
25001 Lis
Queries: Oxiginal
J8 Lay -1.94
11327
25005
Final
Original
(X50)
(k) RayS on CIFARI0
(I) RayS CIFAR10 (Madry Adv. Tr.)
Figure 7: Visual selection of attack trajectories on CIFAR-10.
24

---

Under review as a conference paper at ICLR 2022
Queries: Original
934 Ze -0.27
18257 Zoe 0006
25330 Lo 00.03
Final (x100)
Queries: Original
917 L- -0.10
13723 L- -0.08
25429 L- 0000
Final 0 (x100)
(a) Sign-OPT on ImageNet
(b) Sign-OPT on ImageNet (Madry Adv. Tr.)
Final (x100)
Original
0000
-0.05
(x100)
Original
-0.18
-0.07
-0.08
(c) BiLN+Sign-OPT on ImageNet
(d) BiL on ImageNet (Madry Adv. Tr.)
Queriest Original
13447
25230 For -0.20
Queries: Original
25425
Final (x100)
(x100)
For -0.09
(e) AE+Sign-OPT
ImageNet
(l) AE+Sign-OPT on ImageNet (Madry Adv. Tr.)
Queries: Original
LIKEZ Z.e. =0.01
25667 L 0,00
Final (x100)
Queries: Original
37 L- 0007
TUNZH L. =0.02
25667 L_ 0.00
Final # (x100)
Y =023
(g) HSJA on ImageNet
(h) HSJA on ImageNet (Madry Adv. Tr.)
9742
Final
Original
-0.00
Oviginal
-0.01
(x10k))
(i) BiLN+HSJA ImageNet
(i) BiLN+HSIA ImageNet (Madry Adv. Tr.)
Figure 8: Visual selection of attack trajectories on ImageNet.
25


Reviews:
[{"review_id": "lI_5MVTI62k", "reviewer": "Reviewer_tKPt", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "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": "I am not completely familiar with this line of research, and thus cannot properly position the current work w.r.t. existing literature. Therefore, I have lowered my confidence until I see other reviewers' comments. But, for now:\n\nPaper is hard to read, unless the reader has complete and exact knowledge about at least 2 or 3 previous works. Lots of technical terms, specific algorithms and methodologies have been borrowed from the said works, without any discussion or re-definition inside the main body. IMO, this has made the paper less informative. For example, it might not be a bad idea to briefly overview zeroth-order hard-label attacks, or \"boundary-tilting assumption\" which according to author(s) plays an important role in this paper. In particular, this part:\n- \"We investigate the scenario where an adversary uses zeroth-order information to estimate the desired gradient direction (Cheng et al., 2020; Chen et al., 2019). Thus the adversary uses only the top-1 label feedback from their model query to synthesize samples. The desire\nfor better query efficiency motivated the use of dimension reduction in hard-label attacks.\"\n\nof the \"Related Works\" section can be replaced by one or two paragraphs that briefly describe the main approaches behind each of these sentences. Another example is that author(s) have repeatedly referred to a new MI measure which 1) helps the adversary to craft on-manifold attacks, and also 2) its value \"increases as a function of data dimensionality\". However, the meaning and possible significance of the latter argument is vague and non-informative, at least for a non-familiar reader.\n\nAuthor(s) have relied on a claimed argument, that MI between manifold distribution and the gradient of a robust model is larger than that of an ordinary model, in order to propose their own method of leveraging manifold information during the attack. Is it rigorously justified with exact theoretical arguments? or the claim about MI value only supports the proposed method, intuitively? In other words, do you have any \"theorems\" to theoretically support your method? If the answer is no, then this paper is more of an experimental investigation of an idea, rather than a theoretical analysis.\n\nMoreover, the transitions from some parts of the paper to the next parts are not smooth. For example, transition from Hypothesis 1 to Definition 3.4 can be made more smooth through adding proper explanations. Definition 3.6 is vague. Please add some explanations on how the given formulation corresponds to the MI between low-dimensional manifold distribution $\\mathcal{M}$ and the gradient distribution (?) $\\mathcal{G}$. Let us begin with what is $p_{\\mathcal{G}}(1)$?\n\nI haven't checked the experimental parts.\n\n----------------------------------------------------------------\n\nMinor comments and suggestions:\n- Please correct the citation format at the end of Par. 1 in Introduction section.", "summary_of_the_paper": "This paper concerns zeroth-order hard-label adversarial attacks on machine learning models, and in particular, how to strengthen them through leveraging manifold information. The core idea is inspired from a series of intuitions and observations around the fact that the gradient of a robust model has more information regarding the underlying low-dimensional manifold of the data, compared to that of a naturally trained model. Author(s) have built upon this inspiration and proposed the noisy manifold distance oracle, which can leak manifold information to the adversary during forging its attack. Author(s) have also implemented their method on a number of real-world datasets.", "summary_of_the_review": "I am not completely familiar with this line of research, and thus cannot properly assess the current work. IMO, paper suffers from non-informative and cryptic explanations. This issue can be solved by briefly discussing the many technical terms and concepts that paper has implicitly or explicitly utilized.\n\nAlso, it seems that this work is not completely grounded on a firm theoretical ground. A number of core ideas and intuitions have been triggered by some theoretical analysis, but have been mostly investigated through experiments.\n\nAt this moment, my vote is weak reject (with a low confidence). However, I want to see other reviewers' comments and study a number of references inside the manuscript to have a better judgement.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "EfsO3RFw23z", "reviewer": "Reviewer_iTBK", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "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": "[Strength]\n1 It is very interesting to see the theoretical illustrations that compared with the natural model, the robust model could provide more information about data manifold (i.e. verification of hypothesis 1), which actually provides theoretical justification of (Santurkar et al. (2019)). \n\n2 This paper further argues dimension-reduced hard-label attacks are more effective on robust models than on standardly trained models. \n\n[Weakness]\n1 This paper is based on the assumption that adversarial data are features, not bugs. However, there is evidence that weakens the basic assumption this paper is built on, e.g., adversarial data are just bugs. <https://distill.pub/2019/advex-bugs-discussion/response-5/>\n\n2 Although this paper provides some interesting insights about the hard-label attacks, it does not produce the effective designs of hard-label attack methods, which undermines the paper's significance.\n\n3 The arguments are scattered, which does not form a uniform and compelling viewpoint. Sadly, I still find some experiments in Section 5 cannot well support the paper's arguments.\n\n[Questions]\n1 In the top of page 3, the author(s) stated that \"The desire for better query efficiency motivated the use of dimension reduction in hard-label attacks. However, to date it is not completely understood how this relates to traversal through the data manifold.\"\nI do not catch up with the logical link of the above statement. Could authors illustrate more to me?\n\n2 I get confused about the linkage between NMD and Hypothesis 1. May I know why NMD definition matters to Hypothesis 1?\nBesides, at the bottom of page 5, the authors stated that \"the NMD oracle acts as a side channel leaking sensitive information as a factor of the model robustness and data dimensionality.\"  Could I know what the authors mean about this?  Could I understand in this way that hard-label attacks against a robust model could reveal more sensitive training data information; the low data's dimensionality could worsen this information leakage?\nIf my understanding were correct, this could contradict the common sense that memoization by standard training could leak sensitive information.\n\n3 In Figure 1, why the variance (shade) is larger for blue lines and smaller for red lines? Besides, it seems that all red, blue, and yellow lines are not well separated. \n\n4 Could I check the success rate of methods stated in Table 1. \n\n5 May I know what is manifold distance. In other words, what is d'' in Hypothesis 2? Could the author(s) provide more details to me? ", "summary_of_the_paper": "[Summary]\nThis paper is based on a basic assumption that adversarial data are off-manifold and cannot be generated naturally from the true manifold. \n\nThis paper provides information-theoretic analysis on the hard-label adversarial attacks from the manifold perspective. \n", "summary_of_the_review": "Although this paper provides some interesting points relating to hard-label attacks on robust models, I feel the paper's arguments are scattered, which does not form a uniform and compelling viewpoint. Thereby, I hope the authors could reorganize the paper and highlight a compelling point. \n\n\n\n##### Post rebuttal #### \nMany thanks for authors' feedback. \nI have read other reviewers' comments and corresponding feedback. \nI agree with other reviewers' evaluations such as \"poor writing\", \"unclear points\", etc. \nI keep my score unchanged. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "5bn-bVymOG", "reviewer": "Reviewer_Wy2g", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "Strengths:\n- The paper is interesting to read and presents several results. \n- The topic of understanding adversarial attacks is important and timely. \n- The findings on dimension reduction attacks, reduced resolution, and query efficiency seem to be new and possibly significant.\n\nWeaknesses:\n- The main shortcoming is the presentation of the paper, which makes it difficult to understand and appreciate. It is often unclear from the text what exactly the authors mean in their arguments and how the arguments are supported.\n- The structure of the paper should be improved. Currently, the paper is written as a stream of arguments (definitions, hypotheses, and observations), which are not well supported. For example, it is unclear whether the observations rely only on the presented empirical study.\n- In this regard, I believe the experimental study should be more extensive in order to provide a more substantial empirical evidence for the arguments made in the paper.", "summary_of_the_paper": "The paper addresses hard-label adversarial attacks from a geometric/manifold perspective. Specifically, it examines examples that live close to or on the data manifold. The paper presents a noisy manifold distance based on information-theoretic considerations and proposes three ways to approximate it (taking into account that the data manifold is unknown). Experimental results of HSJA and Sign-OPT attacks on CIFAR-10 and ImageNet are presented.", "summary_of_the_review": "Interesting paper, but arguments are not sufficiently supported", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "3fWvpL2cbGe", "reviewer": "Reviewer_cq6A", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "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": "The focus of this paper—black-box attacks against publicly available deep learning systems—is an important issue from a security perspective, and thus a key research problem. That being said, the paper is poorly written: without a clear hypothesis, or convincing experimental or theoretical results. Several assumptions and claims are made in the paper without being properly substantiated. I have listed more specific comments/questions below:\n\n[Section 3] \n\n- The motivation behind NMD is not provided. In particular, even if the gradients of the robust model are aligned with the data manifold (which is not a direct takeaway from Santurkar et al.), it is not clear why the adversary would have access to a robust model in the first place.\n- The assumptions after Definition 3 are not sufficiently justified. References are cited, however these claims are not made by prior work.\n- The upped bound being larger does not imply that I(M, $\\\"{G}$) is larger.\n\n[Section 4]\n\n- What is the motivation for random BiLN?\n- How exactly is the gradient deviation measured? In particular, how (and when) is the true gradient calculated?\n\n[Section 5]\n\n- It is not clear why the LPIPS distance or the gradient deviation are quantities we should care about in practice. After all, in this setting, the adversary would care only about the attack success rate. And as the authors themselves report, there is no direct correlation between LPIPS/gradient deviation and SR.\n- The results reported in Tables 1 and 2 do not show a consistent trend from the proposed modifications.\n- Results are reported over 50-100 examples of the dataset (which for ImageNet does not even have 1 example per class), and thus could have large statistical fluctuations. Why did the authors choose to report metrics on such small subsets of the data?\n- The connections between the theoretical section (which explores the relationship between manifold-gradient MI and dimensionality for robust models), and doing dimensionality reduction in practice for *standard* (non-robust) models isn't provided.", "summary_of_the_paper": "This paper studies zeroth-order hard-label adversarial attacks. In particular, the authors explore the connection between how the gradient can reveal information about the data manifold, and its dependence on data dimensionality. They also empirically consider attacks with reduced dimensionality in practice.", "summary_of_the_review": "The presentation of this paper could be substantially improved---including outlining the central hypothesis and performing experimental evaluations in more standard settings.\n\n### Post-rebuttal update\n\nI thank the authors for their detailed response. Unfortunately, my concerns with the paper regarding the presentation and motivation (which are also shared by other reviewers), as well as the practical significance of the proposed method still hold. In particular:\n\n- I believe that the paper would benefit from a significant rewrite to clarify precisely the main claims, justify assumptions, and better connect the different sections. \n\n- Regarding the experimental findings, the canonical measure of success of black-box-attacks is the ASR for a fixed epsilon. In this regard, does not seem to be a significant improvement. Moreover, the statistical significance of the findings is hard to verify---in Tables 1 and 2, the differences w.r.t. baselines often lie within confidence intervals, and in many cases the standard deviation is larger than the mean itself. The time constraints of the rebuttal phase are not a justification for not providing results over enough samples. The authors should have verified the statistical significance of their results (by increasing the number of samples till they get reasonable confidence intervals) as part of the original submission.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: In this work, authors study query efficiency in the zeroth-order setting of adversarial examples. Reviewers pointed out several weaknesses in the work. They mentioned the paper is not well-organized and poorly written, experiments are not comprehensive and the practical significance of the proposed method is unclear. Although reviewers appreciated authors' efforts and responses in the discussion period, they felt that the paper is not above the accept threshold this round and still needs a bit more work.
Decision: Reject