Year: 2021

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.

heading: 1 INTRODUCTION
text: Adversarial examples against deep learning models were originally investigated as blind spots in classification (Szegedy et al., 2013; Goodfellow et al., 2014). Formal methods for discovering these blind spots emerged, which we denote as gradient-level attacks, and became the first techniques to reach widespread attention within the deep learning community (Papernot et al., 2016; MoosaviDezfooli et al., 2015; Carlini & Wagner, 2016; 2017; Chen et al., 2018). In order to compute the necessary gradient information, such techniques required access to the model parameters and a 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 et al., 2015; Tramèr et al., 2016; Chen et al., 2017; Ilyas et al., 2018). However, these attacks still rely on models to 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 a random-walk on the decision boundary (Brendel et al., 2017), have been carefully refined to 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 “data-geometric” view of the input space living on a lower-dimensional manifold. This is supported by Stutz et al. (2019), who suggest that regular adversarial examples leave the data manifold, while on-manifold adversarial examples are generalization errors. From a data-geometric perspective, an adversarial example’s distance to the manifold primarily describes
the amount of semantic features preserved during the attack process. This makes it advantageous to produce on-manifold adversarial examples, since the adversary can exploit the inherent generalization error of the model while producing samples that are 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., 2019).
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-gradient 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 a 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 informationtheoretic formulation of the noisy manifold distance (NMD) oracle, which can explain how zerothorder attacks craft on-manifold examples. We theoretically demonstrate on a Gaussian data model that manifold-gradient mutual information can increase as a 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 to 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 to the manifold (Table 1), reduce gradient deviation (Table 2), and improve query efficiency (Figure 2) in a simple and generic way for hard-label attacks.
• Attack-agnostic method for super-pixel grouping. We show that spatial dimension reduction of a decision-based gradient estimate acts as an attack- and knowledge-agnostic method for searching over super-pixels of an image. More importantly, this helps an attacker exploit a 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 to 200% and 340% success rate improvement for state-of-the-art hard-label attacks HSJA (Chen et al., 2019) and Sign-OPT attack (Cheng et al., 2020), respectively.

heading: 2 RELATED WORK
text: Since the original discovery of adversarial samples against deep models (Szegedy et 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-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 a low-probability error set to exist (Gilmer et al., 2018). Likewise the boundary tilting assumption describes adversarial samples as leaving the manifold, which has inspired defenses based on projecting such samples back to the data manifold (Jalal et al., 2019; Samangouei et al., 2018). However, these approaches were later defeated by adaptive attacks (Carlini et al., 2019; Carlini & Wagner, 2017; Tramer et al., 2020).
We investigate the scenario where an adversary uses zeroth-order information (i.e., top-1 label feedback) to estimate the desired gradient direction (Cheng et al., 2020; Chen et al., 2019). Contemporary attacks in this setting are variants of random gradient-free method (RGF) (Nesterov & Spokoiny, 2017), and rely on formulations which convert the top-1 (hard) label, which is a step function, into a continuous real-valued function g : Rd → R, which takes search direction θ ∈ Rd and outputs the distance to the nearest adversarial example (Cheng et al., 2018). The gradient estimate is conceived as a function of the gradient ∇g and can be estimated with either two samples of information (SignOPT) (Cheng et al., 2020), or a single point (HopSkipJumpAttack) (Chen et al., 2019). Details of specific formulations for each attack are provided in Section A.2 of the Appendix.
Query efficiency is a 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-reduction techniques (Tu et al., 2019). However, to date it is not completely understood how this relates to traversal through the data manifold. We leverage previous results of the gradient-level setting (Stutz et al., 2019; Engstrom et al., 2019) to formulate an explanation of manifold leakage during hard-label adversarial attacks.

heading: 3 NOISY MANIFOLD DISTANCE ORACLE
text: Santurkar et al. (2019) demonstrate that the gradients of robust models have higher visual semantic alignment with the data compared to gradients of standard models. We build on 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 a 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 lower-dimension representation of 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 a 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-manifold adversarial examples can exploit the fundamental generalization error of the model (Stutz et al., 2019). More formally, we define the notion of manifold distance as follows.
Definition 3.1 (Manifold Distance). Consider the benign sample x0 and adversarial counterpart x. Assuming a perfect encoding back to the true manifold φ, the manifold distance is defined as d(φ(x0), φ(x)), where d 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, a proxy d′ can be used such that d′(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 Lp-norm, an approximate encoder φ′(·) ∼ φ(·) can be learned using reconstruction-based training of autoencoders (Stutz et al., 2019), or leveraging 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 a 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.
Definition 3.2 (Noisy Manifold Distance Oracle). Consider a manifold distance oracle instantiating d′, benign sample x0, and pair of adversarial samples (x′,x′′) such that d′(x0,x′) < d′(x0,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′′(x0,x′) = 0 and d′′(x0,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
output of the NMD oracle, which is a binary indicator that a 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 x0 − 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)). If three random variables form the Markov chain X → Y → Z, then their mutual information (MI) has the relation I(X;Y ) > I(X;Z).
We assume the data manifoldM, the input gradient G, and the hard-label gradient estimate G̈ will form the Markov chainM→ G → G̈. This assumption is reasonable due to the observations by Santurkar et al. (2019); modifying the sampled data manifold (e.g., by adding adversarial samples through saddle-point optimization) causally induces a smoother loss surface, which imposes its own gradient distribution. Likewise, the true gradient and gradient estimate of hard-label attack are causally linked due to the estimate’s bounded variance (Cheng et al., 2020).
If I(M,G) is larger for adversarially robust models, by Definition 3.3 the upper bound on I(M, G̈) is larger, which means more manifold information could be leaked in the noisy gradient. This information could be used to search in the direction where d′′ is minimized in expectation, leading towards on-manifold examples. However, DPI only offers an upper bound, thus the distance decrease is not guaranteed, only suggested. In the information theoretic sense, does this mean the gradients of models robust in an -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 a first step we posit the following hypothesis:
Hypothesis 1. Consider the manifold distributionM 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 I has the relation I(M,G′) ≥ I(M,G).
In order to empirically verify Hypothesis 1, we must parameterize the notion of model robustness while solving for I(M,G), given an arbitrary gradient distribution G and manifold distributionM. Schmidt et al. (2018) have shown that robust training requires additional data as a function of the data dimensionality. We leverage the data model and results from Schmidt et al. (2018) to derive an analytical solution for I(M,G), since we can parameterize model robustness as a 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 µ ∈ Rd be the per-class centers (means) and let σ > 0 be the variance parameter. Then the (µ, σI)-Gaussian model is defined by the following distribution over (x, y) ∈ Rd × {±1}: First, draw a label y ∈ {±1} uniformly at random. Then sample the data point x ∈ Rd from N (y · µ, σI).
Definition 3.5 (Optimal classification weight (Schmidt et al., 2018)). Fix σ ≤ c1d 1 4 for the universal constant c1, and samples (x1, y1), · · · , (xn, yn) drawn i.i.d from the (µ, σI)-Gaussian model with ||µ|| = √ d (i.e., µk = 1 for all dimensions k ∈ {0, . . . , d}). Schmidt et al. (2018) prove that the
weight setting ŵ = 1n ∑n i=1 yixi yields an l ∞-robust classification error of at most 1% for the linear classifier fŵ : Rd → {±1} instantiated as fŵ(x) = sign(ŵTx) if
n ≥
{ 1, for ≤ 1
4 d− 1 4
c2 2 √ d, for 1 4 d− 1 4 ≤ ≤ 1 4 , (1)
for a universal constant c2.
Note that the instantiation of ŵ must change with choice of and d. We can leverage the weight settings as a function of n and d to give a definition of manifold-gradient mutual information.

heading: 3.1 MANIFOLD-GRADIENT MUTUAL INFORMATION
text: Notice the classifier sgn(·) in Definition 3.5 is discontinuous at xk = 0 for any dimension k. Instead we consider the sub-gradient of the classifier at xk < 0 and xk > 0. In either case (non-robust or robust), the input sub-gradient for fŵ(x′k) is defined dimension-wise for our isotropic Gaussian as ∇x′kfŵk = signwk. Since the weight of each dimension is Gaussian distributed with ŵk ∼ N (µk, σ2), we can define the distribution of gradients as G ∼ Rademacher (Pŵk∼N [ŵk ≥ 0]). Using this fact, we define manifold-gradient mutual information in three parts: 1) defining the manifold-gradient point-wise joint probabilities between gk and xk at each dimension k for the sub-gradient cases where xk > 0 and xk < 0, 2) defining the manifold-gradient 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 A.1 of the Appendix. The three parts are used in the standard definition of mutual information (Cover & Thomas, 2006).
Notation. Fix σ = c1d 1 4 for both cases. We denote the sub-manifold sampled from the positive (y = 1) and negative (y = −1) classes asM+ andM−, respectively. For brevity we label xk > 0 as x+ and xk < 0 as x−.
Definition 3.6 (Manifold-Gradient Mutual Information). We define the manifold-gradient mutual information, based on the standard definition of mutual information from information theory (Cover & Thomas, 2006), as
I(M,G) ,k = 2 ∫ M+ p(1,x+) log( p(1,x+) pG(1)pM(x+) ) dx+ + 2 ∫ M+ p(−1, x+) log( p(−1, x +) pG(−1)pM(x+) ) dx+.
(2)
with the total unnormalized mutual information defined as the summation over dimensions (due to dimension co-independence) I(M,G) = ∑d k=1 I(M,G) ,k.

heading: 3.2 MUTUAL INFORMATION AS A FUNCTION OF DIMENSIONALITY
text: To provide numerical support for Hypothesis 1, we run experiments using the Riemann approximation of Equation 13, provided in the Appendix as Equation 15. We estimate the average per-dimension mutual information, I(M,G) ,k = I(M,G) d , for the case where x ∈ R
d while varying the dimensionality term d ∈ [5, 2000) against values of c2 ∈ {1, 100} and ∈ {0.000, 0.180, 0.250}. The values of c2 represent two multiplicative factors for number of samples in robust models (Equation 1). In our experiments, we target an error within 10−1 (e.g., 0.9 ≤ pG(1) + pG(−1) ≤ 1.0). Thus we multiply each branch of Equation 1 by a large constant (104). We run the approximation over ten different random seeds and show the average with standard error shaded.
The estimation result is shown in Figure 1 with log-scale x-axis. Regardless of c2 and , lower values of the dimensionality evidence a 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 in the estimate.
Observation 1. Given reduced data dimensionality, a robust model could increase I(M,G) ,k and lead to leaking better search direction through the gradient (e.g., act as manifold distance oracle). This supports Hypothesis 1.
This can theoretically explain the high visual alignment observed empirically by Engstrom et al. (2019) and Santurkar et 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.

heading: 4 ZEROTH-ORDER SEARCH THROUGH THE MANIFOLD DISTANCE ORACLE
text: According to Observation 1, the true gradient and manifold of a 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 dimension-reduction techniques, such as autoencoder-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 et al., 2017). In order to connect the notion of manifold-gradient mutual information with on-manifold adversarial samples of real datasets, we posit the following.
Hypothesis 2. Consider Observation 1 and Definition 3.3 (DPI), then due to the higher upper bound on I(M, G̈) and leaking better search directions, a hard-label 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 in attacking a K-way multiclass classification model f : Rd → {1, . . . ,K}. Given an original example x0, the goal is to generate adversarial example x such that x is close to x0 and f(x) 6= f(x0), where closeness is often approximated by the Lp-norm of x− x0. In the gradient-level setting, we require the gradient ∇f(·). However, in the hard-label setting we are forced to estimate ∂f(x)∂x without access to∇f(·), 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 θ. We evaluate the effect of dimension reduction on Sign-OPT attack (Cheng et al., 2020) and HopSkipJumpAttack (HSJA) (Chen et al., 2019), as both are considered state-of-the-art in the literature, and rely on minimization of g(·). We provide a 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 as RayS by Chen & Gu (2020), 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 A.5.6 of the Appendix.

heading: 4.1 DIMENSION-REDUCED ZEROTH-ORDER SEARCH
text: To test Hypothesis 2, we modify existing hard-label attacks to produce dimension-reduced 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 → Rd′ for reduced dimension d′ and decoding map D : Rd′ → Rd. In general the adversarial sample is created by x = x0 + g (D(θ′)) D(θ ′) ||D(θ′)|| , where θ
′ ∈ Rd′ and is optimized depending on the respective attack (e.g., Sign-OPT and HSJA), and as before, g is a measure of distance to the decision boundary in direction D(θ′). The mapping functions can be initialized with either an autoencoder (AE), or a 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 of 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 the effect of dimension-reduction without semantic information, we implement a random variant of BiLN (Rand) which samples a subset of coordinates uniform-randomly from the source image as the dimension-reduced version, then replaces the pixels at these coordinates with those from the gradient
estimate. This is meant to show the effect of discarding some semantic information (e.g., spatial correlation) in the update.

heading: 4.2 ESTIMATING MANIFOLD DISTANCE
text: 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. Fré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 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 φ′ by taking the encoder of trained autoencoders for each dataset, which can be used to compute L∞ distance between encoded samples. In other words, this lets us compute ||φ′(x0) − φ′(x)||∞ for benign sample x0 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 a sample close to the approximate manifold, we could say the gradient estimates leveraged noisy mutual information, which may be upper bounded by the clean mutual information (Hypothesis 1). 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 a well-defined boundary that aligns with salient input changes (Santurkar et al., 2019), and should further lower variance of the gradient estimate compared to natural models, which improves the baseline performance of an attack. We test this by calculating per-pixel gradient deviation ||g−ĝ||2H×W 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 adversarial label, we use the victim model’s original criterion to calculate the gradient, which was cross-entropy for all models in our evaluation.

heading: 5 RESULTS & DISCUSSION
text: We test Hypothesis 2 by comparing two SotA hard-label attacks with their compatible dimensionreduced variants, against both natural and robust models. First we show empirical evidence of the relationship between manifold distance and dimension-reduced attacks in Section 5.1. 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 et al., 2012) for RGB image data. The natural CIFAR-10 network is the same implementation opensourced 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.1 In addition, we leverage the representative adversarial training technique proposed by Madry et al. (2017) (and their = 8255 = 0.031 checkpoints for L∞ setting) as the robust models for CIFAR-10 and ImageNet. The BiLN variants downscale to 16× 16 for CIFAR-10, and 32× 32 for ImageNet. We use L∞-norm versions of attacks for all experiments, and the same values for natural models as the robust CIFAR-10 and robust ImageNet (hereafter referred to as Madry CIFAR-10 and Madry ImageNet). All attacks run for 25k queries without early stopping on correctly classified samples. 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.
1https://pytorch.org/docs/stable/torchvision/models.html

heading: 5.1 MANIFOLD DISTANCE
text: LPIPS results are shown in Table 1, 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 L∞ distance of the manifold approximation (Section A.5.9), and Fréchet Inception Distance (Section A.5.8), which all demonstrate a tendency to be lower with dimension-reduced attacks. Observation 2. Dimension-reduced hard-label attacks can have lower LPIPS score, L∞ approximated distance, and Fréchet Inception Distance (and thus lower manifold distance) on robust models if they preserve semantic priors in the update, which supports Hypothesis 2.

heading: 5.2 GRADIENT DEVIATION
text: 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 a 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., 2017). 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, we suspect 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 on additional
robust CIFAR-10 models are provided in Section A.5.2 of the Appendix, which exhibited a similar trend of lower gradient deviation. Sign-OPT has a universally lower gradient deviation than HSJA, which aligns with findings of Liu et al. (2020).
Observation 3. 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).

heading: 5.3 INFORMING PRACTICE
text: We have shown that dimension reduction has unexpected consequences in terms of manifold distance, and on CIFAR-10 and some ImageNet cases, leads to a lower gradient deviation on the robust model. We finalize our contribution by providing a comprehensive evaluation of the attack success rates in Figure 2 against number of queries. The plots are quantified by taking their max-normalized Trapezoid rule area-under-curve (AUC).2 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 SignOPT 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 Sign-OPT+BiLN in Table 2 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 to say the following.
Observation 4. Successful attacks exhibit preservation of leaked semantic priors. Measures of manifold distance such as LPIPS tend to be lower on dimension-reduced 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 a better NMD oracle (due to 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 a 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 if they are semantically meaningless (Santurkar et al., 2019), so depending on the adversary’s goal (e.g., evasion or information leakage), they could be less useful in the hard-label setting.
2Tables with all normalized SR AUC scores are provided in Section A.5.3 of the Appendix.

heading: 6 CONCLUSION
text: Despite the recent progress in zeroth-order attack methods, open questions remain about their precise behavior. We develop an information-theoretic analysis that sheds light on their ability to produce on-manifold adversarial examples. Through experiments on real-world datasets, we show an over two-fold increase in attack success rates by leveraging new findings about manifold distance and gradient deviation. With knowledge of the manifold-gradient 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, our method may turn the strength of deep learning, which is efficiently extracting patterns in large-scale data, into a weakness.

heading: A APPENDIX

heading: A.1 DERIVATION OF MANIFOLD-GRADIENT MUTUAL INFORMATION (MI)
text: We define the manifold-gradient point-wise joint probability in a case-wise manner, for the respective values under g ∈ {−1, 1}d and x ∈ Rd. We are concerned with the sub-gradient cases where x > 0 (denoted x+) and x < 0 (denoted x−) which correspond to fixed values of g based on class means y · µ with y ∈ {−1, 1}. This gives for each dimension k,
p(gk = 1,x + k ) =
1 2σ √ 2π exp
( −1
2
( x+k − µk
σ
)2)
p(gk = 1,x − k ) =
1 2σ √ 2π exp
( −1
2
( x+k + µk
σ
)2) (3)
p(gk = −1,x+k ) = 1
2σ √ 2π exp
( −1
2
( x+k + µk
σ
)2)
p(gk = −1,x−k ) = 1
2σ √ 2π exp
( −1
2
( x+k − µk
σ
)2) .
(4)
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 µk and mirrored at xk = 0) we can simplify to
p(gk = 1,x + k ) =
1 2σ √ 2π exp
( −1
2
( x+k − µk
σ
)2) , (5)
p(gk = −1,x+k ) = 1
2σ √ 2π exp
( −1
2
( x+k + µk
σ
)2) , (6)
where x ∼ N (y · µ, σI). In words, Equation 6 is the symmetrical tail of the Gaussian mixture marginal while Equation 5 is the remainder of the mixture.
Similarly, a point-wise gradient is given as the Rademacher outcome gk ∈ {±1}. The choice of directly influences the marginal probability over the manifold. The marginal probability over the manifold can be given as the Riemann approximations
pG(gk = 1) = 1
2σ √ 2π n∑ i=1 exp
( −1
2
( x∗i,k − µk
σ
)2) ∆i (7)
and
pG(gk = −1) = 1
2σ √ 2π n∑ i=1 exp
( −1
2
( x∗i,k + µk
σ
)2) ∆i, (8)
with ∆i = x+i,k−x + i−1,k for arbitrary x ∗ i,k ∈ [x + i−1,k,x + i,k], and n is controlled by the hyper-parameter
.
The marginal for the manifold under the gradient is given similarly as
pM(xk) = p(gk = 1,x + k ) + p(gk = −1,x + k )
= 1
σ √ 2π exp
( −1
2
( x+k − µk
σ
)2) + 1
σ √ 2π exp
( −1
2
( x+k + µk
σ
)2) ,
(9)
where x+k > 0 for all dimensions k. Denote the sub-manifold sampled from the positive (y = 1) and negative (y = −1) classes asM+ andM−, respectively. Our definition for manifold-gradient mutual information is based on the standard definition of mutual information from information theory (Cover & Thomas, 2006),
I(M,G) ,k = ∫ M ∫ G p(gk,xk) log( p(gk,xk) pG(gk)pM(xk) ) dgk dxk, (10)
where is treated as a hyper-parameter controlling the value of n in pG(gk). By substitution into Equation 10 we have
I(M,G) ,k = ∫ M p(1,xk) log( p(1,xk) pG(1)pM(xk) ) dxk
+ ∫ M p(−1,xk) log( p(−1,xk) pG(−1)pM(xk) ) dxk.
(11)
This is split further similar to true positive, true negative, false positive, and false negative, as
I(M,G) ,k = ∫ M+ p(1,x+k ) log( p(1,x+k ) pG(1)pM(x + k ) ) dx+k
+ ∫ M− p(1,x−k ) log( p(1,x−k ) pG(1)pM(x − k ) ) dx−k
+ ∫ M+ p(−1,x+k ) log( p(−1,x+k ) pG(−1)pM(x+k ) ) dx+k
+ ∫ M− p(−1,x−k ) log( p(−1,x−k ) pG(−1)pM(x−k ) ) dx−k ,
(12)
and simplified due to symmetry at 0 as I(M,G) ,k = 2 ∫ M+ p(1,x+k ) log( p(1,x+k ) pG(1)pM(x + k ) ) dx+k
+ 2 ∫ M+ p(−1,x+k ) log( p(−1,x+k ) pG(−1)pM(x+k ) ) dx+k .
(13)
The total un-normalized mutual information is given by the summation over dimensions I(M,G) =∑d k=1 I(M,G) ,k. Notably the cases for each possible scenario under detection theory are represented. Each case is bounded by the results of Schmidt et al. (2018). By substitution from each marginal and joint probability in Equations 8, 3, and 4 respectively, we have the closed form solution for mutual information.
This leads to the Riemann approximation of Equation 13,
I(M,G) ,k = 2 n∑ i=1 p(1,x∗i,k) log( p(1,x∗i,k) pG(1)pM(x∗i,k) ) ∆i
+ 2 n∑ i=1 p(−1,x∗i,k) log( p(−1,x∗i,k) pG(−1)pM(x∗i,k) ) ∆i.
(14)
with ∆i = x+i,k − x + i−1,k for arbitrary positive x ∗ i,k ∈ [x + i−1,k,x + i,k]. Since x + is a standard multivariate Gaussian (Cover & Thomas, 2006), the final mutual information is the summation over each dimension,
I(M,G) = 2 d∑ k=1 n∑ i=1 p(1,x∗i,k) log( p(1,x∗i,k) pG(1)pM(x∗i,k) ) ∆i
+ 2 d∑ k=1 n∑ i=1 p(−1,x∗i,k) log( p(−1,x∗i,k) pG(−1)pM(x∗i,k) ) ∆i.
(15)

heading: A.2 HARD-LABEL ATTACK FORMULATION
text: Contemporary hard-label attacks are variants of random gradient-free method (RGF) (Nesterov & Spokoiny, 2017), a gradient estimator which yields the estimate ĝ over q random directions {ui}qi=1.
OPT-Attack For benign example x0, true label y0, and hard-label black-box function f : Rd → {1, . . . ,K}, Cheng et al. (2019) define the objective function g : Rd → R as a function of search direction θ, where the optimal solution is g(θ∗), the minimum distance from x0 to the nearest adversarial example along the direction θ∗. For the untargeted attack, g(θ) is the distance to any decision boundary along direction θ, and allows for estimating the gradient as
ĝ = 1
q q∑ i=0 g(θ + βui)− g(θ) β · ui, (16)
where β is a small smoothing parameter. Notably, g(θ) is continuous even if 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(θ) ≈ ĝ := q∑ i=1 sign (g(θ + βui)− g(θ))ui. (17)
We focus on the Sign-OPT variant, since the findings are more relevant to the current state-of-the-art.
HopSkipJumpAttack Similar to Sign-OPT, HopSkipJumpAttack (HSJA) (Chen et al., 2019) uses a zeroth-order sign oracle to improve Boundary Attack (Brendel et al., 2017). HSJA lacks the convergence analysis of Sign-OPT and relies on one-point gradient estimate. Regardless, HSJA is competitive and can excel in the L∞ setting.
Dimension-reduced Sign-OPT & HSJA. In general, for attacks relying on the Cheng et al. (2019) formulation, the update in Equation 16 becomes
ĝ = 1
q q∑ i=0 g(θ′ + βu′i)− g(θ′) β · u′i (18)
for the reduced-dimension Gaussian vectors {u′i ∈ Rd ′}qi=0 for integer d′ < d and direction θ′ ∈ Rd ′ . The reduced-dimension direction θ′ is initialized randomly with θ′ ∼ N (0, 1) for the untargeted case, or for the targeted case as θ′ = E(xt), where xt is a test sample correctly classified as target class t by the victim model. This scheme also applies to HSJA, since HSJA performs a single-point sign estimate. As in the normal variants, ĝ is used to update θ′.

heading: A.3 MAIN PAPER BLOCK DIAGRAM
text: A block diagram of assumptions, claims, and observations is shown in Figure 3.
A.4 IMPLEMENTATION DETAILS

heading: A.4.1 HARDWARE AND ATTACK HYPERPARAMETERS
text: All experiments in the main paper were performed on an internal high-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, HSJA requires tuning of parameter γ for best performance. On CIFAR-10 we used γ = 10.0. For ImageNet, it was necessary to set γ ≥ 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-reduced variants. We note that the dimension-reduced variants like HSJA+BiLN were less sensitive to γ, performing similarly regardless of the setting.

heading: A.4.2 ADVERSARY AUTOENCODER
text: We are primarily interested in the effect of reduced search resolution on attack behavior. Thus in this work, given a candidate direction θ′ and magnitude (or radius) r, the adversarial sample in the AE case is the blending (1− r)x0 + rD (E(x0) + θ′).3
For AE attack variants, we implement the same architecture described by Tu et al. (2019). Specifically it leverages a fully convolutional network for the encoder and decoder. Every AE is trained using the held out test set, as we assume disjoint data between adversary and victim.
The adversary’s AE is tuned to minimize reconstruction error of input images, so the output quality of the AE will depend on 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 128x128 before passing to the AE, and the output of the AE is scaled back to 224x224, as described by Tu et al. (2019).

heading: A.4.3 DATA SAMPLING
text: 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-randomly chosen and ten random samples taken from each (100 total samples).

heading: A.5 SUPPLEMENTAL RESULTS

heading: A.5.1 QUERY VS. DISTORTION PLOTS
text: We show the model queries against attack distortion measurement in 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 a simple yet effective way to improve the query efficiency of the hard-label attacks.

heading: A.5.2 GRADIENT DEVIATION ON ROBUST CIFAR-10
text: In Table 3 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 is that dimension-reduced attacks manage to reduce gradient deviation across each robust model.

heading: A.5.3 SUCCESS RATE NORMALIZED AUC SCORES
text: 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.

heading: A.5.4 SUCCESS RATE SCORES
text: We provide the success rates over all samples at specific query intervals in Tables 6 and 7.

heading: A.5.5 ATTACKING A SMOOTHED MODEL
text: Gaussian smoothing is a technique of performing adversarial training with sampled affected by Gaussian noise. At test time, inference is achieved via a Monte Carlo search over many Gaussianperturbed versions of the sample under test. The SotA at time of writing, randomized smoothing proposed by Cohen et al. (2019), is a 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 , only a fraction are within the bound.
3We observed that it is detrimental to set x = D(E(x0) + rθ′) or x = D(rθ′) directly. Despite remaining on the data manifold by attacking it directly, the approximation of the data manifold is crude, which results in large distortion (Stutz et al., 2019)

heading: A.5.6 ATTACKING WITHOUT GRADIENT ESTIMATE
text: We perform additional experiments with an attack that does not perform an explicit gradient estimate. Chen & Gu (2020) propose an alternative hard-label attack method which is to search for the minimum decision boundary radius r from a sample x0, along a ray direction θ. Instead of searching over Rd to minimize g(θ), Chen et al. propose to perform ray search over directions θ ∈ {−1, 1}d, resulting in 2d maximum possible directions. This reduction of the search resolution enables SotA query
efficiency in the L∞ 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 et al. also perform a 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 a 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 s in Algorithm 3 of Chen & Gu (2020), which either speeds up upscaling by a factor a (i.e., s = s+ a), or extends the search through a specific block index by a factor b (increase block level at k = 2sb instead of k = 2s).
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.i and 6.ii). This is a result of RayS not relying on explicit gradient estimation. When comparing the FID-64 score, the dimension-reduced variants of RayS do not have a large variation between them (Inset 6.i), a side-effect of the adaptive super-pixel search, which can automatically scale the super-pixel size as the search progresses.

heading: A.5.7 LOCAL INTRINSIC DIMENSIONALITY
text: In Table 8 we show the average Local Intrinsic Dimensionality Amsaleg et al. (2017) for each dataset and attack combination.

heading: A.5.8 FRÉCHET INCEPTION DISTANCE
text: 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 Fréchet Inception Distance (FID) that acts as a surrogate measure of the manifold distance over a 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 a result, this estimation process is only available from the defender’s perspective. Since FID uses an Inception-V3 coding layer (Szegedy et 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 as FID-64 in this supplementary material), taken from an open-source implementation.4 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 et al. (2018).
The comparison of FID scores is shown in Table 9 for natural and robust models. The scores for ImageNet on dimension-reduced 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× 224) enables dimension reduction to be more effective than the lower dimension CIFAR-10 (32× 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 a 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 a universal behavior to reduce the score in the robust setting, similar to the natural setting for ImageNet. AE variants exhibit higher FID score than BiLN, since BiLN can rescale invariant of the adversary’s manifold knowledge (e.g., only having knowledge of test set).
4https://github.com/mseitzer/pytorch-fid

heading: A.5.9 L∞-NORM OVER APPROXIMATE MANIFOLD
text: 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 10. 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 is the dataset dimensionality, with dimension reduction having a 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 a 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 7.
A.5.11 VISUAL RESULTS - IMAGENET
We provide visual qualitative results for each attack on ImageNet in Figure 8.

Review summaries:
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.

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.

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.