  The query-based black-box attacks, which don't require any knowledge about
the attacked models and datasets, have raised serious threats to machine
learning models in many real applications. In this work, we study a simple but
promising defense technique, dubbed Random Noise Defense (RND) against
query-based black-box attacks, which adds proper Gaussian noise to each query.
It is lightweight and can be directly combined with any off-the-shelf models
and other defense strategies. However, the theoretical guarantee of random
noise defense is missing, and the actual effectiveness of this defense is not
yet fully understood. In this work, we present solid theoretical analyses to
demonstrate that the defense effect of RND against the query-based black-box
attack and the corresponding adaptive attack heavily depends on the magnitude
ratio between the random noise added by the defender (i.e., RND) and the random
noise added by the attacker for gradient estimation. Extensive experiments on
CIFAR-10 and ImageNet verify our theoretical studies. Based on RND, we also
propose a stronger defense method that combines RND with Gaussian augmentation
training (RND-GT) and achieves better defense performance.
