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