  Blackbox adversarial attacks can be categorized into transfer- and
query-based attacks. Transfer methods do not require any feedback from the
victim model, but provide lower success rates compared to query-based methods.
Query attacks often require a large number of queries for success. To achieve
the best of both approaches, recent efforts have tried to combine them, but
still require hundreds of queries to achieve high success rates (especially for
targeted attacks). In this paper, we propose a novel method for Blackbox
Attacks via Surrogate Ensemble Search (BASES) that can generate highly
successful blackbox attacks using an extremely small number of queries. We
first define a perturbation machine that generates a perturbed image by
minimizing a weighted loss function over a fixed set of surrogate models. To
generate an attack for a given victim model, we search over the weights in the
loss function using queries generated by the perturbation machine. Since the
dimension of the search space is small (same as the number of surrogate
models), the search requires a small number of queries. We demonstrate that our
proposed method achieves better success rate with at least 30x fewer queries
compared to state-of-the-art methods on different image classifiers trained
with ImageNet. In particular, our method requires as few as 3 queries per image
(on average) to achieve more than a 90% success rate for targeted attacks and
1-2 queries per image for over a 99% success rate for untargeted attacks. Our
method is also effective on Google Cloud Vision API and achieved a 91%
untargeted attack success rate with 2.9 queries per image. We also show that
the perturbations generated by our proposed method are highly transferable and
can be adopted for hard-label blackbox attacks. We also show effectiveness of
BASES for hiding attacks on object detectors.
