  We propose a simple and highly query-efficient black-box adversarial attack
named SWITCH, which has a state-of-the-art performance in the score-based
setting. SWITCH features a highly efficient and effective utilization of the
gradient of a surrogate model $\hat{\mathbf{g}}$ w.r.t. the input image, i.e.,
the transferable gradient. In each iteration, SWITCH first tries to update the
current sample along the direction of $\hat{\mathbf{g}}$, but considers
switching to its opposite direction $-\hat{\mathbf{g}}$ if our algorithm
detects that it does not increase the value of the attack objective function.
We justify the choice of switching to the opposite direction by a local
approximate linearity assumption. In SWITCH, only one or two queries are needed
per iteration, but it is still effective due to the rich information provided
by the transferable gradient, thereby resulting in unprecedented query
efficiency. To improve the robustness of SWITCH, we further propose
SWITCH$_\text{RGF}$ in which the update follows the direction of a random
gradient-free (RGF) estimate when neither $\hat{\mathbf{g}}$ nor its opposite
direction can increase the objective, while maintaining the advantage of SWITCH
in terms of query efficiency. Experimental results conducted on CIFAR-10,
CIFAR-100 and TinyImageNet show that compared with other methods, SWITCH
achieves a satisfactory attack success rate using much fewer queries, and
SWITCH$_\text{RGF}$ achieves the state-of-the-art attack success rate with
fewer queries overall. Our approach can serve as a strong baseline for future
black-box attacks because of its simplicity. The PyTorch source code is
released on https://github.com/machanic/SWITCH.
