# AESOP: Adjustable Exhaustive Search for One-Pixel Attacks in Deep Neural Networks
## 4 Exhaustive Search for One-Pixel Attacks
### Experimental Results of Exhaustive Search
\begin{table}
\begin{tabular}{c c c c} \hline
**Consecutive Pixels** & **Frequency** & **Rate** & **Accumulated Rate** \\ \hline
1 & 216 & 5.47\% & 100.00\% \\
2 & 605 & 15.32\% & 94.53\% \\
3 & 630 & 15.95\% & 79.21\% \\
4 & 545 & 13.80\% & 63.26\% \\
5 & 404 & 10.23\% & 49.46\% \\
6–18 & 1549 & 39.23\% & 39.23\% \\ \hline Total & 3949 & 100.00\% & — \\ \hline \end{tabular}
\end{table} 
Table 2: Index consecutiveness of one-pixel attacks. \begin{table}
\begin{tabular}{c c c c} \hline
**Consecutive Values** & **Frequency** & **Rate** & **Accumulated Rate** \\ \hline
1 & 20 & 0.51\% & 100.00\% \\
2 & 20 & 0.51\% & 99.49\% \\
3 & 17 & 0.43\% & 98.99\% \\
4 & 21 & 0.53\% & 98.56\% \\
5 & 22 & 0.56\% & 99.02\% \\
6 & 23 & 0.58\% & 97.47\% \\
7 & 30 & 0.76\% & 96.89\% \\
8 & 22 & 0.56\% & 96.13\% \\
9 & 23 & 0.58\% & 95.57\% \\
10–256 & 3726 & 94.99\% & 94.99\% \\ \hline Total & 3949 & 100.00\% & — \\ \hline \end{tabular}
\end{table} 
Table 3: Value consecutiveness of one-pixel attacks. Figure 2: One-pixel attack for each digit in MNIST. Table 3 represents the consecutiveness of the vulnerable pixel values. The leftmost column indicates the number of consecutive values that can cause a one-pixel attack. For example, 5 indicates case in which five consecutive values induce a one-pixel attack. Its frequency and rate are 22% and 0.56%, respectively. In this case, similar to consecutive pixels, even if we examine only one value out of every five pixel values, we can detect a corresponding one-pixel attack. The rightmost column presents the accumulated rate; e.g., even if we inspect only one value out of every five values which saves 80% of search space, we can identify 99.02% of one-pixel attacks. Figure 3 shows the distribution of one-pixel attacks for each digit. In each figure, the darkness represents the relative frequency of a one-pixel attack occurring on each digit. In the case of digit 1, many one-pixel attacks appear vertically according to shape of the digit 1. Overall, most one-  
* Even well-trained networks can undergo one-pixel attacks on the MNIST data set. * Over 90% of one-pixel attacks occur at consecutive pixels. * In terms of the pixel value, more than 99% of one-pixel attacks occur on consecutive values. * One-pixel attacks rarely occur at the outermost edge. Based on the results, we propose an adjustable exhaustive search for one-pixel attacks where users provide parameters that can tune the degree of alternation. The pixel alternation parameters \(a_{v}\) and \(a_{h}\) specify the number of pixels that we omit to inspect a one-pixel attack; that is, we examine only one pixel out of every \(a_{v}\) pixels vertically and \(a_{h}\) pixels horizontally, respectively. Similarly, the pixel value alternation parameter \(a_{val}\) determines the number of pixel values which we leap. In addition, the parameter \(e\) configures not to probe for one-pixel attacks outside the \(e\)-th outer edge. Algorithm 2 presents our adjustable exhaustive search algorithm. First, it identifies the class \(t_{\mathbf{x}}\) of a given original input image \(\mathbf{x}\) (line 2). Then, this algorithm generates a one-pixel different input \(\mathbf{x}^{\prime}\) only when the pixel index and value satisfy a constraint given by the parameters \(a_{h},a_{v},a_{val}\) and \(e\) (lines 3-9). Then, it examines whether the output class \(t_{\mathbf{x}^{\prime}}\) of \(\mathbf{x}^{\prime}\) is different from the output class \(t_{\mathbf{x}}\) of the original input image \(\mathbf{x}\) (line 13). The loops are executed in parallel with GPUs. Once the loop terminates, it returns a set \(E\) of perturbations for one-pixel attacks (line 17).