Recent machine learning models are highly sensitive to adversarial input perturbation. That is, an attacker may easily mislead a well-performing image classification system by altering some pixels. However, proving that a network will have correct output when changing some regions of the images, is quite challenging. Because of this, only a few works targeted this problem. Although there are an increasing number of studies on this field, reliable robustness evaluation is still an open issue. In this work, we will attempt to contribute in this direction. We will present new interval arithmetic based algorithms to provide adversarial example free image patches for trained artificial neural networks.
One of the hottest topics in present artificial intelligence research is to understand
the phenomenon of adversarial examples for machine learning techniques applying
artificial neural networks [
Using adversarial examples generated by existing attack algorithms like those in [11, 4, 13], an ofending driver can easily prevent the system to identify him. Even in black box cases, i.e. when the attacker has no access to model parameters, the attack can be successful [12]. This makes it dificult to apply these state-ofthe-art techniques in any safety critical settings. One might naively use attack algorithms for evaluating robustness. However, as show in [4], robustness against some attacks does not mean that the network is robust. Later, stronger attacks may be developed, which will be able to fool the network. A certified evaluation may end this arms race. Further, it motivates to develop reliable methods for evaluating neural networks.
In this paper we present our first results on implementing an interval arithmetic based reliable algorithm to describe adversarial example free zones on an image for trained artificial neural networks.
There are already many available shocking results regarding adversarial examples
for artificial neural networks (see e.g. those in [
∘ = { ∘ | ∈ and ∈ }, , ∈ I, where I is the set of compact intervals [, ], where , ∈ R and ≤ . The arithmetic definition is: [, ] + [, ] = [ + , + ], [, ] − [, ] = [ − ,
− ], [, ] · [, ] = [min(, , , ), max(, , , )], [, ]/[, ] = [, ] · [1/, 1/ ] if 0 ∈/ [, ].
These definitions are equivalent. Although the obtained result intervals seem to be sharp, it is not the case. The inclusion of the function
( ) = 2 − obtained for the interval [0, 1] is [−1, 1], while the range of the function ( ) (the set of possible values) is here just [−0.25, 0.0]. Using more sophisticated techniques the problem of the too loose enclosure can be overcome – at the cost of higher computing times.
In a floating point environment (most cases) the outward rounding is important to have a conservative inclusion that is a must in computer supported mathematical proofs. Outward rounding means that the bounds of the calculated result intervals are rounded in such a way that all result points are within the given bounds. In other words, the lower bound is always rounded toward −∞, and the upper bound toward ∞. This can easily be realized applying the four rounding modes of the IEEE 754 standard (available on most programming languages and computers). Several programming languages and packages support interval arithmetic based inclusion function generation: C-XSC, FORTRAN-XSC, PASCAL-XSC, and PROFIL/BIAS. Interval packages are available in several symbolic and numerical systems such as Maple, Mathematica, Matlab. The package for the latter one, Intlab is especially easy to use.
It is important to note that interval calculations do not require the knowledge of the symbolic expression of the underlying functions, it is enough if a computer subroutine is available. In our case a Python code was applied. Linear sums and sigmoid or other monotonous functions used in artificial neural networks are explicitly advantageous for interval inclusion functions: sharp bounding is expected in general. On the other hand, non-monotonic activations can also be handled by the presented method.
For our problem, we need a proper method to describe the large dimensional sets that cannot contain adversarial examples. For this purpose, an interval arithmetic based algorithm describing the level sets of nonlinear optimization problems [5] seems to be appropriate. Unfortunately, this algorithm scales up very badly with increasing dimension. This is why first we developed interval arithmetic based algorithms that are capable of describing the level sets of an artificial neural network around a feasible positive sample. In this way, we could ensure with mathematical rigor that adversarial samples cannot exist within the found bounds. According to our experiences, benevolent problems show much better complexity numbers compared to theoretically possible pessimistic convergence rates.
The simple, logistic regression model were trained on the subset of the MNIST dataset [9] that includes two classes: 3 and 7. We used 10 images from this database which contain 28 × 28 pixel grayscale images of handwritten digits. Assuming examples ( , ), ∈ R , ∈ {0, 1}, = 1, . . . , , the goal is to approximate the data using the logistic function
≈ ( + ) = 1/(1 + − + ). ︁∑ 3.1. Changes on the whole picture First we checked how much we can change the actual grayscale values of a picture without having an adversarial example case. It means, that for each pixel we allowed a given amount of relative change in the grayscale values. E.g. 1% means an alteration of 3 for a pixel that has the white of the value 255. We understand the relative change in the neighborhood of zero still in an absolute way, i.e. if the given pixel was black with the grayscale value of zero, then in our calculation the interval [0, 1] was actually checked. Note that this way of adding noise to a picture is realistic in the sense, that many practical situations can fall into this category, including for example trafic sign pictures in a slightly foggy weather. Also, many documented adversarial examples were obtained by added random noise, where the relative change in the grayscale values were limited.
We composed a simple greedy algorithm to find the largest possible relative diference value eficiently. Here
is the number of pixels; is the picture pixels in a vector;
is the number of percent of changes to be checked, first it is set to one; 0 is the starting picture;
is a boolean variable meaning whether the network gives a value above 0.5: then it is true, otherwise false. The simplified pseudo code of the algorithm is:
is the proven number of percents, initially set to zero; 0. If ( 0) > 0.5 then 2. Let be an dimensional interval 3. For = 1 to do (a) If = 0, then = [0, 2 * /
100] (b) Otherwise, if = 1, then = [1 − 2 * / (c) Otherwise = [ − / 100, + / 100], and check the end points: if the lower one is negative, then set it to zero, if the upper one is larger than 1, then set it to 1.
= − 0.1 = 0 and STOP
From computational point of view, the above described checking means a single interval evaluation of a trained network, when instead of the usual real number grayscale values, real compact intervals should be evaluated. Since interval calculation is according to the rule of thumb 4-35 times slower than the respective real number calculations, this type of adversary example free set checking does not require long computation. This is why we have composed a simple algorithm that will increase the size of the checked interval until the respective conditions are hurt. Our measured computation times for 10 images was 5.05 seconds. Note that if two possible values form the interval box in each dimension, then one interval evaluation will prove that all the 2784 points satisfy the condition set by the trained artificial neural network. This is obviously not to be completed with one-by-one real evaluations.
The proven amount of changes on the gray scale values everywhere on Figure 2 without having an adversarial example were in the order of appearance: 1%, 1%, 1%, and 2%, respectively. These proven values are useful in real life situations. 3.2. Arbitrary large changes in neighboring points As a second try, we aimed to find those maximal rectangles in an image for which all pixels may change their grayscale value arbitrarily between 0 and 255 without being classified incorrectly. Basically, we grow squares around given pixels, check their recognizability, and if it was positive, then enlarge them. Again, we built a simple, eficient greedy algorithm for this purpose. Also, we take care of the sides of the original image, that is why our result may be a rectangle. We repeat our growing procedure for all the pixels of our image, and return that rectangle that had the most pixels.
The obtained results are illustrated on Figure 3 for some of the studied images. The calculated number of pixels to be changed arbitrarily were between 88 and 190 (compare it with the 28 × 28 = 784 pixels in the images). The combined running time for the second round of 10 test images was 1971.87 second, i.e. closely half an hour.
We are still in the phase when we explore the capabilities of interval arithmetic based algorithms for describing the sensitivity of trained natural neural networks to changes in object to be classified, but we find our present results encouraging enough to continue our research project. The next issue can be the frightening case of small patches changing the recognized meaning of trafic signs. On the other hand, we could also be capable of proving where the next adversarial example is relative to a given image. Acknowledgements. This research was supported by the project E“xtending the activities of the HU-MATHS-IN Hungarian Industrial and Innovation Mathematical Service Network” EFOP3.6.2-16-2017-00015, 2018-1.3.1-VKE-2018-00033. The authors are grateful for the anonymous referees for their useful suggestions to improve the paper. [1] Ba, J. and Kingma, D., Adam: A Method for Stochastic Optimization. 3rd Intl.
Conf. on Learning Representations (ICLR), 2015, http://arxiv.org/abs/1412.6980 [2] Bánhelyi, B., Csendes, T., Garay, B.M., and Hatvani, L., A computerassisted proof for Sigma_3-chaos in the forced damped pendulum equation. SIAM J. on Applied Dynamical Systems Vol. 7. (2008), 843–867. [3] Bánhelyi, B., Csendes, T., Krisztin, T., and Neumaier, A., Global attractivity of the zero solution for Wright’s equation. SIAM J. on Applied Dynamical Systems Vol. 13 (2014), 537–563. [4] Carlini, N. and Wagner, D.A.,, Towards Evaluating the Robustness of Neural
Networks. IEEE Symposium on Security and Privacy, SP 2017, San Jose [5] Csendes, T., An interval method for bounding level sets of parameter estimation problems, Computing Vol. 41 (1989), 75–86. [6] Fazlyab, M., Morari, M., and Pappas, G.J., Safety Verification and Robustness Analysis of Neural Networks via Quadratic Constraints and Semidefinite Programming. arXiv:1903.01287v1. [7] Goodfellow, I., Shlens, J., and Christian Szegedy, Explaining and Harnessing Adversarial Examples. International Conference on Learning Representations, 2015 [12] N. Narodytska and S. Kasiviswanathan, Simple Black-Box Adversarial Attacks on Deep Neural Networks. IEEE Conference on Computer Vision and Pattern Recognition Workshops (CVPRW), 2017 [13] Su, J., Vargas, D.V., and Kouichi, S., One pixel attack for fooling deep neural networks. arXiv:1710.08864.