Adversarial black-box attacks aim to craft adversarial perturbations by querying input?output pairs of machine learning models. They are widely used to evaluate the robustness of pre-trained models. However, black-box attacks often su?er from the issue of query ine?ciency due to the high dimensionality of the input space, and therefore incur a false sense of model robustness. In this paper, we relax the conditions of the black-box threat model, and propose a novel technique called the spanning attack. By constraining adversarial perturbations in a low-dimensional subspace via spanning an auxiliary unlabeled dataset, the spanning attack signi?cantly improves the query e?ciency of black-box attacks. Extensive experiments show that the proposed method works favorably in both soft-label and hard-label black-box attacks.