Robustness Bounds on the Successful Adversarial Examples: Theory and
  Practice
Hiroaki Maeshima Akira Otsuka
Adversarial example (AE) is an attack method for machine learning, which is
crafted by adding imperceptible perturbation to the data inducing
misclassification. In the current paper, we investigated the upper bound of the
probability of successful AEs based on the Gaussian Process (GP)
classification. We proved a new upper bound that depends on AE's perturbation
norm, the kernel function used in GP, and the distance of the closest pair with
different labels in the training dataset. Surprisingly, the upper bound is
determined regardless of the distribution of the sample dataset. We showed that
our theoretical result was confirmed through the experiment using ImageNet. In
addition, we showed that changing the parameters of the kernel function induces
a change of the upper bound of the probability of successful AEs.