# ShuffleDetect: Detecting Adversarial Images against Convolutional Neural Networks
## 4 ShuffleDetect  
The general goal of the shuffling process is to interchange different parts of an image. We noticed in [23] that if one shuffles a clean image, CNNs usually classify the shuffled image into the same category as the unshuffled clean image. We also noticed that the situation differs from an adversarial image because CNNs usually tend to classify the shuffled adversarial image that is no longer in the same category as the unshuffled adversarial image, at least for those created by the two attacks of [23] (which are considered again in Section 6). These findings, valid for the two attacks, led to the detection method exposed below, which is based on the assumption that shuffling affects the adversarial noise more than it affects the image's original components, whichever the attack. **Shuffling an image. ** One is given image \(\mathcal{I}\) of fixed (square) size \(n\times n\) fitting the CNN's input size, and an integer \(s\), such that patches of size \(s\times s\) create a partition in the mathematical meaning of the term, or a grid in the more visual meaning of the term, of \(\mathcal{I}\). This latter condition requires that \(s\) divides \(n\) since the number of patches is the integer \(N_{s}=\left(\frac{n}{s}\right)^{2}\). It is convenient in practice to label the patch \(P_{i,j}\), positioned in the \(i\)th column and \(j\)th row of the grid, as \(P_{k}\), where \(k=\frac{n}{s}(i-1)+j\) for \(1\leq i,j\leq\frac{n}{s}\) (see Table 2 in Appendix B for an example, which is used in our experiments actually). The set of possible scrambles of an image of size \(n\times n\) is essentially parametrized by the symmetric group \(\mathfrak{S}_{N_{s}}\) of permutations of \(N_{s}\) letters since \(\mathfrak{S}_{N_{s}}\) operate on the set of \(N_{s}\) patches. Indeed, a permutation \(\sigma\in\mathfrak{S}_{N_{s}}\) is represented as a finite product of cycles, each of the form \((k_{1},k_{2},\dots,k_{M})\), these cycles having two-by-two disjoint supports. Each cycle symbolizes that the \(M\) patches \(P_{k_{1}},P_{k_{2}},\dots,P_{k_{M}}\), associated to \(k_{1},k_{2},\dots,k_{M}\), respectively, are rotated in a circular way: \(P_{k_{1}}\) takes the position of \(P_{k_{2}}\), and so on until \(P_{k_{M}}\) takes the position of \(P_{k_{1}}\). The group \(\mathfrak{S}_{N_{s}}\) is of order \(N_{s}!\), and is non-trivial provided \(s\) is a strict divisor of \(n\), which we assume from now on. Given \(\sigma\in\mathfrak{S}_{N_{s}}\), one denotes by \(sh_{\sigma}(\mathcal{I},s)\) the image obtained from \(\mathcal{I}\) by swapping its patches according to \(\sigma\). Both the unshuffled image \(\mathcal{I}\) and the shuffled image \(sh_{\sigma}(\mathcal{I},s)\) are given to the CNN for classification. Figure 1 illustrates the process with the partition of an image into 4 patches \(P_{1},P_{2},P_{3},P_{4}\): The permutation \(\sigma\in\mathfrak{S}_{4}\), selected among the altogether \(4!=24\) elements of \(\mathfrak{S}_{4}\), is defined as the product of two cycles of length 2, which actually amounts to interchanging the patches on the diagonals. **ShuffleDetect. ** To some extent, the global design of the algorithm ShuffleDetect mimics the design of classical probabilistic primality tests (such as those of Fermat, Solovay-Strassen, or Miller-Rabin, see [24], chapter 7 for instance), where the validity of an equation, which should be satisfied if a given integer \(p\) is a prime, is checked for a series of rounds until either one has gained confidence (parameterized by the number of rounds) that \(p\) is probably a prime or the equation is not satisfied for one of the rounds, in which case one knows that \(p\) is not a prime. In our context, the equation, which assesses the detection of whether image \(\mathcal{I}\) is adversarial or not, consists of comparing the dominating categories, given by a given CNN \(\mathcal{C}\), before and after shuffling, for many permutations. With consistent notations, one round of this detection method for image \(\mathcal{I}\) is as follows.