Generating adversarial examples in a black-box setting retains a significant
challenge with vast practical application prospects. In particular, existing
black-box attacks suffer from the need for excessive queries, as it is
non-trivial to find an appropriate direction to optimize in the
high-dimensional space. In this paper, we propose Projection &
Probability-driven Black-box Attack (PPBA) to tackle this problem by reducing
the solution space and providing better optimization. For reducing the solution
space, we first model the adversarial perturbation optimization problem as a
process of recovering frequency-sparse perturbations with compressed sensing,
under the setting that random noise in the low-frequency space is more likely
to be adversarial. We then propose a simple method to construct a low-frequency
constrained sensing matrix, which works as a plug-and-play projection matrix to
reduce the dimensionality. Such a sensing matrix is shown to be flexible enough
to be integrated into existing methods like NES and Bandits$_{TD}$. For better
optimization, we perform a random walk with a probability-driven strategy,
which utilizes all queries over the whole progress to make full use of the
sensing matrix for a less query budget. Extensive experiments show that our
method requires at most 24% fewer queries with a higher attack success rate
compared with state-of-the-art approaches. Finally, the attack method is
evaluated on the real-world online service, i.e., Google Cloud Vision API,
which further demonstrates our practical potentials.

通过压缩感知和概率驱动策略，利用少量请求达到更好的优化效果，从而解决黑盒攻击中存在的过多请求的问题，并在与其他攻击方法比较后证明其具有更高的攻击成功率。