## 5 Attacks
### Attacks against k-NN  
In the most straight-forward white-box attack scenario against a k-NN model with \(k\) equal to one and Euclidean distance being the distance metric, in order to transform a new unlabeled sample in such a way that it is misclassified as a given target class, it is sufficient for an adversary to select a sample from the target class, and move the new sample towards the target sample along the straight line joining them. Assuming that all data samples are distinct, as the amount of perturbation increases, the perturbed sample would eventually find itself with the target sample as its nearest neighbour [125]. In the case, the target class is not given, i.e., the adversary aims to transform the unlabeled sample in such a way that it is misclassified, no matter which class the perturbed sample belongs to. As mentioned above, such a straight-forward attack is white-box as the adversary would require to know both the training dataset and the distance metric. This attack vector acts as the basis for a naive attack proposed in [126]. When \(k=1\) this strategy is able to easily find an optimal adversarial example. However, it is unclear how to do this efficiently for bigger values of \(k\). There is no guarantee of an optimal solution when using the algorithm proposed above for each set of \(k\) training samples. Furthermore, it is extremely inefficient and the solution complexity increases exponentially with \(k\). To resolve these issues, study [126] proposes the following attack algorithm. First, the nearest neighbour \(\hat{x}\) from any class \(\hat{y}\) other than \(y\) is found. This sample is added to an empty set \(S\). After that, out of all samples with class \(\hat{y}\), the nearest sample to the mean of \(S\) is found and added to \(S\). This step is repeated until \(|S|=\left\lceil\frac{k}{2}\right\rceil\). Finally, \(x\) is moved towards the mean of \(S\) until the classifier's prediction differs from \(y\). It is worth noticing that the attack is non-targeted, however it can be transformed into the targeted one by selecting \(\hat{x}\) as the nearest to \(x\) which has the given target class. Authors in [126] also propose a gradient-based attack. First, a target label \(\hat{y}\) is selected as the class which minimises the distance from an original sample \(x\) to the mean of all samples of some class \(y^{\prime}\
eq y\), where \(y\) is the class label of \(x\). After that, \(m\) samples from the same class \(\hat{y}\) that are closest to \(x\) are picked. Next, \(x\) is moved further from the samples with the original class \(y\) and closer to the ones with the target class \(\hat{y}\) using a gradient-based optimization algorithm. In other words, to craft such an adversarial perturbation \(\delta\), the following optimization problem should be solved:  
\[ \begin{split}&\min_{\delta}\sum_{i=1}^{m}\omega_{i}\sigma(|| \tilde{x}_{i}-(x+\delta)||-\eta)\\ &\text{subject to }||\delta||\leq\epsilon,\end{split}  \tag{1}\]  
where \(\tilde{x}_{1},\ldots,\tilde{x}_{m}\) are the \(m\) training samples selected by the algorithm, \(\omega_{i}=1\) if the label of \(\tilde{x}_{i}\) is \(\hat{y}\), otherwise \(\omega_{i}=-1\), \(\sigma\) is a sigmoid \(\sigma(z)=1/(1+e^{-\alpha z})\) in which \"steepness\" of the function is controlled with the help of hyperparameter \(\alpha\), \(\eta\) is the average distance between a sample in the training dataset and its \(k\)-th nearest neighbour, and \(\epsilon\) is the maximal perturbation size. This attack is non-targeted, but it can be transformed to the targeted one by picking a certain target class \(\hat{y}\). Another gradient-based attack against k-NN is proposed in [127]. As in the previous case, it starts with generating a subset of \(m\) guide samples \(\bar{X}=\{\bar{x}_{1},\ldots,\bar{x}_{m}\}\). The first half of these samples is generated in the same manner as in the previous attack case:  
\[