  This paper investigates the vulnerability of the nearest neighbors search,
which is a pivotal tool in data analysis and machine learning. The
vulnerability is gauged as the relative amount of perturbation that an attacker
needs to add onto a dataset point in order to modify its neighbor rank w.r.t. a
query. The statistical distribution of this quantity is derived from simple
assumptions. Experiments on six large scale datasets validate this model up to
some outliers which are explained in term of violations of the assumptions.
