Hard-label manifold: the unexpected advantage of query efficiency in finding on-manifold adversarial examples
Hard-label Manifolds: Unexpected Advantages of Query Efficiency for Finding On-manifold Adversarial Examples
The authors propose using a noisy manifold distance oracle to explain the manifold information leakage of hard-label attacks, and state that the dimensionality-reduction variants reduce FID-64 by at most two times.
Hard-label black-box attack: the attacker only obtains the top-1 label returned by the model query, with no gradients, confidence, or other side information; the target is a K-class image classification model, and the goal is to generate an adversarial example close to x0 that is misclassified; the AE variant assumes the attacker can only access the test set.
- Hard-label black-box attacks require only the top-1 label and are the most realistic threat model, but the relationship between the query efficiency gains brought by dimensionality reduction and whether examples lie on the data manifold is not yet clear.
- The authors propose an information-theoretic model of a noisy manifold distance oracle, derive a closed-form solution for manifold-gradient mutual information, and plug bilinear dimensionality reduction (BiLN) and autoencoders (AE) into attacks such as Sign-OPT and HSJA, using FID-64 to estimate manifold distance.
- On CIFAR-10 and ImageNet, the FID-64 of the dimensionality-reduction variants is generally lower than that of the original attacks; the authors state that manifold distance is reduced by at most two times and query efficiency is improved by up to 76% (Sign-OPT) and 28% (HSJA), and that this is independent of model robustness.
- The authors state that the AE's manifold description is coarse and its effectiveness depends on the setting; the attacker cannot modify the model to make it overparameterized, and this mutual-information gain axis is left for future work; the experiments cover only 100 samples each from CIFAR-10 and ImageNet, with a 25k query budget.
- Evaluated models
- Natural CIFAR-10 networkMadry Adv.Tr.Resnet50Resnet50 (randomized smoothing)
- Benchmarks
- CIFAR-10ImageNet
- Metrics
- FID-64Avg. L∞ distortionAvg. L2 distortionsuccess rategradient deviation (L∞/L2)
Washington Garcia, Pin-Yu Chen, Somesh Jha and other researchers propose in the paper that the query efficiency of zeroth-order hard-label attacks on image classification models is related to the attacker's movement path in the data manifold. Prior gradient-level research showed that conventional adversarial examples leave the data manifold, whereas on-manifold adversarial examples are in fact generalization error; based on this, the paper proposes an information-theoretic explanation based on a noisy manifold distance oracle, namely that the attacker's gradient estimation leaks manifold information, and numerical experiments show that the mutual information between the manifold and the gradient varies with the effective problem dimension and the number of training points. On real datasets and various zeroth-order attacks using dimensionality reduction, this general behavior brings samples closer to the data manifold, with manifold distance metrics reduced by up to half, and is independent of model robustness. The authors argue that incorporating the mutual information between the manifold and the gradient can help design more robust models in the future and avoid leakage of sensitive data manifolds.
Paper analysis
What problem does this paper attempt to solve?
Explain why dimensionality-reduction hard-label attacks more easily produce adversarial examples on the manifold, and propose an information-theoretic explanation.
Core question: what is the relationship between the query efficiency of zeroth-order hard-label attacks and the location of adversarial examples on the data manifold; the paper proposes an information-theoretic explanation and uses it to improve attacks.
- Problem setting: Stutz et al. (2019) argue that conventional adversarial examples leave the data manifold, whereas on-manifold adversarial examples are actually the model's generalization error; generating on-manifold examples can exploit the model's inherent generalization error while preserving semantic similarity.
- Existing gaps: hard-label attacks have used dimensionality reduction to improve query efficiency, but the authors state that the relationship between dimensionality reduction and traversing the data manifold has so far not been fully understood; the true manifold is hard to describe, and relying on an approximate manifold produces coarse adversarial examples.
- Core observation: the authors argue that query efficiency is related to the attacker's behavior in traversing the manifold; although dimensionality reduction shrinks the search space, the manifold-gradient mutual information may increase as the effective dimension and the number of training points vary.
- Paper proposes: an information-theoretic model of the noisy manifold distance (NMD) oracle; extending score-level dimensionality reduction techniques to hard-label attacks; using FID scores to estimate the attacker's manifold information gain; the BiLN superpixel grouping method.
- Threat model:
- Goal: generate an adversarial example x for a K-class image classification model such that x is close to x0 and f(x) ≠ f(x0).
- Knowledge: hard-label black box, only the top-1 label returned by the query is obtained, no gradients, no confidence.
- Capability: control the query input; the AE variant assumes the attacker can only access a test-set-trained autoencoder.
- Victim systems: naturally trained CIFAR-10 networks, Madry adversarially trained models, ImageNet Resnet50, and randomized smoothing models.
What related research exists?
Related work is organized along three lines: geometric explanations of adversarial examples, hard-label attacks, and manifold leakage.
Geometric explanations of adversarial examples
- Szegedy et al. (2013), Goodfellow et al. (2014)—discovered adversarial examples, hypothesized that they lie in low-probability regions of the input space, and that linearity amplifies this effect.
- Tanay & Griffin (2016), Gilmer et al. (2018)—boundary tilting and the manifold hypothesis: the training and test sets occupy only a submanifold, and the decision boundary lies close to samples on the manifold.
- Stutz et al. (2019)—argue that conventional adversarial examples leave the manifold, and that on-manifold adversarial examples are generalization error; this paper adopts their boundary-tilting hypothesis.
Manifold defenses and their failure
- Jalal et al. (2019), Samangouei et al. (2018)—defenses based on projecting samples back onto the data manifold.
- Carlini et al. (2019), Tramer et al. (2020)—the paper states that the above manifold defenses were later defeated by adaptive attacks.
Evolution of black-box attacks
- Gradient-level attacks (Papernot et al., 2016; Carlini & Wagner, 2016)—require model parameters and a large query budget.
- score-level attacks (Chen et al., 2017; Ilyas et al., 2018)—require only confidence outputs; Tu et al. (2019)'s AutoZOOM introduced dimensionality reduction at the score level, and this paper extends it to hard-label.
- hard-label attacks—Boundary Attack (Brendel et al., 2017), OPT-Attack (Cheng et al., 2019), Sign-OPT (Cheng et al., 2020), HSJA (Chen et al., 2019), RayS (Chen & Gu, 2020).
Information leakage of robust models
- Engstrom et al. (2019), Santurkar et al. (2019)—robust model gradients have higher visual-semantic alignment with the data; the paper states that its formulation describes leakage for both natural and robust models, which differs from these works.
- Schmidt et al. (2018)—the data required for robust training grows with dimension; this paper borrows its Gaussian mixture data model to derive mutual information.
Baselines and benchmarks: The baseline attacks are the original Sign-OPT, HSJA, and RayS; the benchmarks are CIFAR-10 and ImageNet. The authors position this paper as providing a unified explanation of the behavior of dimensionality-reduction hard-label attacks via manifold-gradient mutual information, and improving attack design accordingly.
How does the paper address this problem?
Use the NMD oracle information-theoretic model to explain leakage, then plug BiLN/AE dimensionality reduction into hard-label attacks and measure with FID-64.
Overall approach: treat the gradient estimation of hard-label attacks as a channel that leaks manifold information from a noisy manifold distance (NMD) oracle, first derive the manifold-gradient mutual information on the Gaussian data model of Schmidt et al. (2018), then plug dimensionality-reduced search into existing attacks and verify with FID-64.
Data model and mutual-information derivation
- Gaussian mixture model: Adopt the (θ, σ)-Gaussian model of Schmidt et al. (2018), with labels y ∈ {±1} sampled uniformly, x ~ N(y·θ, σ²I), and the manifold parameterized by (θ*, σ).
- Weight settings: In the non-robust case ŵ = y·x (single sample); in the robust case ŵ = (1/n)Σyᵢxᵢ, with the sample size n scaled with ε and d according to formula (1), and the constant c2 controlling the amplification of the number of training points.
- Closed-form mutual information: Fixing d = 1, the gradient distribution is Bernoulli, and by symmetry it simplifies to I(G, M)ϵ = 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+ (formula 2), meaning the mutual information between the true gradient and the data manifold; the numerical experiments use its Riemann approximation (formula 3).
- Numerical experiment settings: c and c1 are fixed at 0.5, varying c2 ∈ {1, 5, 10, 15}, ε ∈ {0.0, 0.125, 0.250}, d ∈ [1, 10³], assuming dimensions are co-independent and the manifold is described by n points.
Dimensionality-reduced zeroth-order search
- Encoder-decoder framework: Encoding map E: R^d → R^d′, decoding map D: R^d′ → R^d, with adversarial examples generated as x = x0 + g(D(θ′)) (D(θ′))/(|D(θ′)|) (formula 7), meaning searching for a direction in the reduced space and then mapping it back to the original space.
- Two mappings: Autoencoder (AE, approximately describing the manifold, trained only on the test set) and channel-wise bilinear transform (BiLN, up/down-sampling by a fixed scaling factor, requiring no training, exploiting image-space correlations).
- Plugging into attacks: Sign-OPT's gradient estimation is changed to sampling over dimensionality-reduced Gaussian directions {u′ᵢ ∈ R^d′} (formula 8); in the untargeted case θ′ is randomly initialized, and in the targeted case θ′ = E(x_t); HSJA's single-point sign estimation applies likewise.
Estimating manifold distance
- FID-64: Treat adversarial examples as generated images and use the FID score as a proxy measure of manifold distance; it uses the 64-dimensional max pooling layer of Inception-V3 for encoding, allowing full-rank FID to be computed with fewer than 2048 samples.
- Independence note: The paper states that the experiments do not target Inception-V3, so the FID measure does not depend on the victim model's internals.
Success criterion
- The attack goal is f(x) ≠ f(x0) (untargeted attack), measured by Lp distortion, success rate, and FID-64 as a function of queries; CIFAR-10 uses the L∞ version (matching the regularization norm of the Madry model), and ImageNet uses the L2 version (matching the certified norm of randomized smoothing).
What experiments did the paper conduct?
Comparing dimensionality-reduction attack variants on CIFAR-10/ImageNet, FID-64 generally decreases, with query efficiency improving by up to 76%.
Experimental setup
- Models tested: CIFAR-10 natural network (Cheng et al. 2020 open-source implementation), Madry adversarially trained model (L∞, ε = 0.031); ImageNet pretrained Resnet50, Cohen et al. (2019) randomized smoothing model (σ = 0.5, ε ≃ 1.0, L2).
- Attack methods: Sign-OPT, HSJA and their BiLN and AE dimensionality-reduction variants; Appendix D.2 additionally tests RayS and BiLN+RayS.
- Datasets and samples: For CIFAR-10 and ImageNet, 10 classes × 10 random samples per class are taken from the test set, 100 in total.
- Budget and metrics: All attacks run for 25k queries without early stopping; the metrics are average L∞/L2 distortion, success rate, and FID-64; only the untargeted case is reported.
- Gradient deviation experiment: Table 1, on the natural CIFAR-10 model, with 50 samples per attack variant, compares the L∞/L2 norm of the first gradient estimate with the true gradient.
- Number of repetitions: Not reported in the paper.
Main results
According to Table 2 (CIFAR-10, ε = 0.031, Avg. L∞ / SR / FID-64 at 4k/8k/14k queries):
Swipe horizontally to read the table
Attack variant Natural model 4k Natural model 14k Madry 4k Madry 14k HSJA 0.01 / 98.0 / 0.02 0.01 / 100.0 / 0.01 0.09 / 15.0 / 3.57 0.06 / 27.0 / 1.69 BiLN+HSJA 16 0.02 / 82.0 / 0.03 0.01 / 97.0 / 0.01 0.07 / 25.0 / 0.68 0.05 / 32.0 / 0.37 Sign-OPT 0.06 / 52.0 / 0.70 0.02 / 79.0 / 0.00 0.33 / 2.0 / 2.28 0.28 / 3.0 / 0.59 BiLN+Sign-OPT 16 0.09 / 21.0 / 0.01 0.06 / 36.0 / 0.00 0.37 / 2.0 / 0.08 0.33 / 3.0 / 0.04 AE+Sign-OPT 0.09 / 20.0 / 0.01 0.06 / 35.0 / 0.00 0.20 / 8.0 / 0.01 0.15 / 11.0 / 0.21 RayS 0.01 / 93.0→100.0 / 0.02 0.01 / 100.0 / 0.01 0.05 / 33.0 0.04 / 39.0 / 0.23 - The authors state that the FID-64 of the dimensionality-reduction variants is generally lower, with BiLN+Sign-OPT lower by up to two orders of magnitude, and AE+Sign-OPT peaking at 0.28 and then stabilizing near 0.004 (Figure 3b).
- On the Madry model, the FID-64 of BiLN+Sign-OPT and AE+Sign-OPT eventually matches the baseline scores of the natural model; the authors conclude from this that manifold information leakage is independent of model sample complexity.
- The authors state that BiLN dimensionality reduction brings query efficiency gains of up to 28% and 76% for HSJA and Sign-OPT on robust models, respectively; in Figure 3a, BiLN+HSJA reduces the average distortion from 0.09 to 0.07 at 4k queries on the Madry model.
Gradient deviation analysis (Table 1)
- What was measured: On the natural CIFAR-10 model, the deviation of each variant's first gradient estimate from the true input gradient (averaged over 50 samples).
- Results: Sign-OPT+BiLN has the lowest L∞ deviation (4.067 ± 1.252), and HSJA the highest (4.884 ± 1.208); for L2 deviation as well, the Sign-OPT variants are overall lower than the HSJA variants.
- Authors' interpretation: HSJA's single-point estimate is noisier and, by the data processing inequality, has lower mutual information, which explains why BiLN+HSJA's FID-64 fails to match the natural model baseline on robust models.
ImageNet and RayS supplementary experiments (Appendix D.1, D.2)
- ImageNet (L2): At 8k queries, the success rates of BiLN+HSJA and BiLN+Sign-OPT increase by 1.4x and 2.1x, respectively; in Figure 4b, the FID-64 of the BiLN variants is lower than that of the original and AE variants.
- RayS (CIFAR-10): BiLN+RayS variants have little effect on query efficiency (Figure 5a), and their FID-64 differs little from one another (Figure 5b); the authors say this is because RayS does not perform explicit gradient estimation, and its adaptive superpixel search automatically adjusts the scale.
Other ablations and analyses
- Mutual-information numerical experiments (Figure 2): When c2 = 1, increasing ε does not change the mutual information; as c2 increases, the mutual information rises with ε, most noticeably at ε = 0.25, and the mutual information is higher at low d.
- Exception of the AE variant: The authors state that the success of AE+Sign-OPT is scenario-dependent, and that the low quality of the AE manifold description does not allow fine-grained adjustment of the perturbation.
- Exception of BiLN+HSJA: On robust models its distortion performance is better than the original HSJA, but its FID-64 does not match the natural model baseline (the authors attribute this to the single-point estimate).
What are some points that can be further explored?
The authors note that the AE description is coarse and that the over-parameterization axis is left for future work; the experiments cover only 100 samples each from two datasets.
Limitations noted by the authors and future directions
- Over-parameterization axis left for future work (Section 3.2): Attackers cannot modify the model to make it over-parameterized; the authors say this mutual-information gain axis is left for future research, and this paper focuses on the effective dimensions controllable by the attacker.
- AE manifold description is coarse (Sections 4.3, 5.2): The AE is trained only on the test set, and the approximation superimposes additional distortion on the adversarial noise; the authors say the success of AE+Sign-OPT is scenario-dependent, and a low-quality manifold description does not allow fine-grained adjustment.
- Noise in HSJA single-point estimation (Section 6): The authors hypothesize that the single-point method leaves the manifold earlier because it updates the reference sample online, and they support this empirical argument with a gradient deviation experiment.
- Using the manifold description to select superpixel groups (Section 6): The authors propose that an attack could learn the manifold description and then use it to select the most relevant superpixel groups in the image, as a future attack design direction.
- Guiding robust model design (Abstract, Section 7): The authors say that incorporating manifold-gradient mutual information into consideration can inform the design of better robust models in the future, avoiding sensitive data manifold leakage.
Scope of experiments
- There are 4 models tested: the CIFAR-10 natural network, the Madry adversarially trained model, ImageNet Resnet50, and the Cohen et al. randomized smoothing model.
- The datasets are CIFAR-10 and ImageNet, with 100 test samples each (10 classes × 10 each); the attack budget is 25k queries, and only untargeted attacks are reported.
- The attacks cover Sign-OPT, HSJA, RayS, and the BiLN/AE dimensionality-reduction variants; CIFAR-10 uses L∞ and ImageNet uses L2.
- The gradient deviation experiment uses 50 samples per variant (Table 1); the paper does not report the number of experimental repetitions.
- The mutual-information conclusions come from the analytical derivation for d = 1 and numerical approximations for d ∈ [1, 10³] (Figure 2), not from direct measurements on real models.
Summarize the main content of the paper
Information-theoretic explanation of manifold leakage in dimensionality-reduction hard-label attacks, with FID-64 reduced by up to two times and query efficiency improved by up to 76%.
An analysis and improvement paper on the behavior of hard-label black-box adversarial attacks. The problem the authors address is: dimensionality reduction techniques improve the query efficiency of zeroth-order attacks, but the relationship between this efficiency and whether adversarial examples lie on the data manifold was previously not understood.
- Method: proposes an information-theoretic model of the noisy manifold distance (NMD) oracle, and derives a closed-form solution for manifold-gradient mutual information on the Gaussian data model of Schmidt et al. (2018); plugs bilinear dimensionality reduction (BiLN) and autoencoders (AE) into Sign-OPT and HSJA, and uses FID-64 to estimate manifold distance.
- Theoretical results: numerical experiments show that when the training-point scaling factor c2 is sufficiently large, mutual information at low dimension d rises as the perturbation ε increases (Figure 2); the authors state that this can explain the high visual alignment of gradients of robust models.
- Experimental results: on CIFAR-10, the FID-64 of the dimensionality-reduction variants is generally lower than that of the original attacks, BiLN+Sign-OPT is lower by up to two orders of magnitude, and AE+Sign-OPT stabilizes near 0.004 (Figure 3b); the authors state that manifold distance is reduced by at most two times, and that this is independent of model robustness.
- Query efficiency: the authors state that BiLN brings query efficiency gains of up to 28% and 76% for HSJA and Sign-OPT respectively on robust models; on ImageNet, the success rates at 8k queries increase by 1.4x and 2.1x respectively.
- Exception: the FID-64 of BiLN+HSJA on robust models does not match the natural-model baseline; the authors attribute this to the greater noise of HSJA's single-point estimate (its gradient deviation is the highest in Table 1, with L∞ of 4.884).
- Authors' conclusion: manifold-gradient mutual information can guide the design of hard-label attacks (targeting high-level features), and provides information for future robust model design to avoid data manifold leakage.
Related papers
- Theoretically Principled Trade-off for Stateful Defenses against Query-Based Black-Box AttacksAnalysis / interpretabilityarXiv