# AESOP: Adjustable Exhaustive Search for One-Pixel Attacks in Deep Neural Networks
## 1 Introduction  
In the past decade, machine learning techniques including deep neural networks have made significant achievements [1; 2]. The precision of artificial intelligence, particularly in image classification, recommendation systems and natural language processing, matches or outperforms human cognitive capabilities. Despite these successes, recent research has revealed that imperceptible modifications of input images may make well-trained networks unstable; that is, _adversarial perturbations_ induce them to misclassify input images [3; 4]. Thus, _adversarial examples_ containing imperceptible perturbations are considered as significant obstacles to employment of neural networks in safety-critical systems, such as autonomous vehicles and air traffic collision avoidance systems [5; 6].  
In this study, we investigate _one-pixel attacks_[7] among adversarial examples. These are input images that differ from the original input image in _only_ one pixel, but cause a given neural network to classify them incorrectly. Existing methods [7; 8] for identifying one-pixel attacks utilize elaborate searches. However, they _sometimes_ miss one-pixel attacks since they do not explore the entire search space. Moreover, the constraint solvers that they employ as a core engine cannot utilize the parallelism of state-of-the-art GPUs.  
Therefore, in this paper, we propose an efficient method for identifying one-pixel attacks using an _exhaustive search_. Our technique explores all the search space _in parallel_ using GPUs. An exhaustive search can identify attacks that existing methods overlook, but in certain cases it may require a large amount of time owing to the inherent search space. Hence, we analyze the patterns of one-pixel attacks on well-trained neural networks for the MNIST data set [9]. Our experiments reveal the following: even Convolutional neural networks (CNNs) [10; 11] with over 99.7% accuracy (i.e., 0.3% error rate) are subjectedto one-pixel attacks for 2% of input images. More importantly, one-pixel attacks occur consecutively with respect to location and pixel value. Based on these results, we propose an _adjustable exhaustive search_ that can dramatically reduce the search space but still detect most attacks. Our method can adjust the exhaustiveness of the search, wherein we probe alternately by skipping pixels and pixel values, rather than examining for each pixel index and pixel value. In addition, our search utilizes the locality of the attack distribution. We present our analysis and experimental results obtained using the MNIST data set to demonstrate that our technique can efficiently detect one-pixel attacks. The contributions of this paper are as follows:  
* This study performs thorough experiment with _well-trained CNNs for one-pixel attacks with the entire MNIST testing set_. The experimental result provides deep insights into one-pixel attacks for hand written digits, which can improve the robustness of neural networks.
* Based on the attack patterns we have observed, we propose a novel _adjustable exhaustive search algorithm_ for the one-pixel attack problem.
* We develop an efficient tool to identify one-pixel attacks by an adjustable exhaustive search. It could identify over 99% of one-pixel attacks with approximately 10% of the time.  
The remainder of this paper is organized as follows: Section 2 presents the related research. In Section 3, we formalize the one-pixel attack problem we study in this paper. In Section 4, we present our first algorithm for exhaustively searching one-pixel attacks and provide insights gained from exhaustive experiments. In Section 5, we propose an adjustable exhaustive search to identify attacks efficiently and present experimental results to validate the proposed adjustable technique. Finally, the conclusions are presented in Section 6.