Query-Efficient Adversarial Attack Based on Latin Hypercube Sampling

Dan Wang, Jiayu Lin, Yuan-Gen Wang

Abstract

Decision-based adversarial attacks are critical for evaluating the robustness of black-box deep learning models. However, existing boundary attacks are often query-inefficient, requiring thousands of samples to estimate gradients. This paper presents LHS-BA, a novel attack that utilizes Latin Hypercube Sampling (LHS) to significantly improve query efficiency. By ensuring a more uniform and symmetric distribution of noise samples, LHS-BA achieves lower distortion adversarial examples with fewer model queries than state-of-the-art methods like HopSkipJumpAttack.

Introduction

Adversarial attacks expose vulnerabilities in deep learning models by identifying small, often imperceptible perturbations that lead to misclassification. In real-world "black-box" scenarios, attackers typically only have access to the model's final decision (hard labels). Boundary Attacks (BAs) are effective in this setting but are notoriously "query-hungry" because they rely on Simple Random Sampling (SRS) to estimate gradients at the decision boundary. SRS lacks uniformity, necessitating a large number of samples for reliable estimation, which is impractical for commercial APIs with query limits or costs.

Methodology

The proposed Latin Hypercube Sampling based Boundary Attack (LHS-BA) replaces SRS with Latin Hypercube Sampling (LHS) for gradient estimation. LHS is a stratified sampling technique that ensures samples are evenly distributed across the input space. In one dimension, it divides the probability distribution into $M$ equal intervals and selects one point from each. In two dimensions, it ensures that each sample is the only one in its respective row and column of a grid, similar to a Latin Square.

LHS ensures better uniformity and symmetry compared to simple random sampling.

The attack follows an iterative three-step process: estimating the gradient using $M$ random vectors generated via LHS, moving a small distance in that direction, and projecting back to the decision boundary using a binary search. The inherent symmetry of LHS allows noise components in non-gradient directions to cancel out more effectively than in SRS, leading to more accurate estimates with fewer samples.

Experimental Results

LHS-BA was evaluated on MNIST, CIFAR-10, CIFAR-100, and ImageNet-1K datasets against various architectures, including CNNs, ResNets, and DenseNets.

Quantitative results for untargeted attacks across various datasets and models.

As shown in the results for untargeted attacks, LHS-BA consistently outperforms the original Boundary Attack and HopSkipJumpAttack (HSJA). The advantage is most pronounced under tight query budgets. For instance, on ImageNet-1K with a 1,000-query budget, LHS-BA achieved a mean $l_2$ distortion of 33.598, significantly lower than HSJA (40.745) and the original BA (77.083). In targeted attacks, which are inherently more difficult, LHS-BA also led the pack; on CIFAR-10 (ResNet-20) with 1,000 queries, it reached a distortion of 3.066, while HSJA was at 4.226.

Discussion and Conclusion

LHS-BA demonstrates that the sampling strategy is a key factor in the efficiency of decision-based attacks. Its performance in high-dimensional spaces like ImageNet highlights the importance of covering the distribution interval thoroughly, which SRS often fails to do. While high-resolution images still require significant queries for imperceptible distortion, LHS-BA represents a major step toward practical black-box testing. Future work may explore adaptive sampling rates based on local boundary geometry to further optimize efficiency.

Summary updated

Abstract

In order to be applicable in real-world scenario, Boundary Attacks (BAs) were proposed and ensured one hundred percent attack success rate with only decision information. However, existing BA methods craft adversarial examples by leveraging a simple random sampling (SRS) to estimate the gradient, consuming a large number of model queries. To overcome the drawback of SRS, this paper proposes a Latin Hypercube Sampling based Boundary Attack (LHS-BA) to save query budget. Compared with SRS, LHS has better uniformity under the same limited number of random samples. Therefore, the average on these random samples is closer to the true gradient than that estimated by SRS. Various experiments are conducted on benchmark datasets including MNIST, CIFAR, and ImageNet-1K. Experimental results demonstrate the superiority of the proposed LHS-BA over the state-of-the-art BA methods in terms of query efficiency. The source codes are publicly available at https://github.com/GZHU-DVL/LHS-BA.
BibTeX
@inproceedings{wang2022query,
  author = {Dan Wang and Jiayu Lin and Yuan-Gen Wang},
  title = {{Query-Efficient Adversarial Attack Based on Latin Hypercube Sampling}},
  booktitle = {ICIP},
  year = {2022},
  url = {https://openreview.net/forum?id=EwID6m_sqQZ},
}
Figure