We consider a data corruption scenario in the classical (k) Nearest Neighbors ((k)-NN) algorithm, that is, the testing data are randomly perturbed. Under such a scenario, the impact of corruption level on the asymptotic regret is carefully characterized. In particular, our theoretical analysis reveals a phase transition phenomenon that, when the corruption level (\omega) is below a critical order (i.e., small-(\omega) regime), the asymptotic regret remains the same; when it is beyond that order (i.e., large-(\omega) regime), the asymptotic regret deteriorates polynomially. Surprisingly, we obtain a negative result that the classical noise-injection approach will not help improve the testing performance in the beginning stage of the large-(\omega) regime, even in the level of the multiplicative constant of asymptotic regret. As a technical by-product, we prove that under different model assumptions, the pre-processed 1-NN proposed in \cite{xue2017achieving} will at most achieve a sub-optimal rate when the data dimension (d>4) even if (k) is chosen optimally in the pre-processing step.