## 5 Attacks
### Attacks against k-NN
\begin{split}&\{\bar{x}_{1},\ldots,\bar{x}_{m/2}\}=\arg\min_{X^{ \prime}}\sum_{x^{\prime}\in X^{\prime}}||x^{\prime}-x||\\ &\text{subject to }\forall x^{\prime}\in X^{\prime},f(x^{\prime})=y^ {\prime},y^{\prime}\
eq y.\end{split}  \tag{2}\]  
The second half is generated as follows:  
\[ \begin{split}&\{\bar{x}_{m/2+1},\ldots,\bar{x}_{m}\}=\arg\min_{X^{ \prime}}\sum_{x^{\prime}\in X^{\prime}}||x^{\prime}-x||\\ &\text{subject to }\forall x^{\prime}\in X^{\prime},f(x^{\prime})=y.\end{split}  \tag{3}\]  
Once the guide samples have been found, the following optimization problem is supposed to be solved by the adversary in order to generate an adversarial perturbation \(\delta\):  
\[\min_{\delta}\sum_{i=1}^{m}\max\Bigl{\{}\omega_{i}\Bigl{(}||\bar{x}_{i}-(x+ \delta)||-\eta^{2}\Bigr{)}+\Delta,0\Bigr{\}}+c||\delta||^{2}, \tag{4}\]  
where \(\Delta\) a small constant greater than zero, e.g., \(1\times 10^{-5}\), \(c\) is a balancing constant, and other notations are the same as in (1). To find \(c\) a binary search is used: in case of the successful attack, \(c\) is increased and, in the opposite case, \(c\) is decreased. The attack is executed multiple times: one for each training sample nearest to \(x\) whose class is different from \(y\). Study [128] proposes an adversarial example attack against k-NN algorithm via solving the following optimization problem with regards to \(\lambda\):  
\[\max_{\lambda\geq 0}\biggl{\{}-\frac{1}{2}\lambda^{T}AA^{T}\lambda-\lambda^{T}b \biggr{\}}, \tag{5}\]  
where matrix \(A=\{a_{i}\}\) and vector \(b=\{b_{i}\}\). If \(f(\bar{x}_{i})=y\), \(a_{i}=\hat{x}-\bar{x}_{i}\) and \(b_{i}=\frac{||x-\bar{x}_{i}||^{2}-||x-\hat{x}||^{2}}{2}\), otherwise they are equal to zeros. The adversarial perturbation can then be crafted as \(\delta=A^{T}\lambda\). This optimization problem can be solved via a greedy coordinate ascent algorithm. The solving time can be decreased by applying a screening rule to remove variables in each such problem. A region-based attack against a k-NN classifier is proposed in [129]. The attack is based on \((s,m)\)-decomposition which is a partition of the training samples into convex polyhedra \(P_{1},\ldots,P_{s}\). Each of these polyhedras can be defined by \(m\) linear constraints. If there is such an \((s,m)\)-decomposition exists for a classifier \(f\) that \(f(x)\) is constant \(\forall x\in P_{i}\)\(\forall i\), then classifier \(f\) is \((s,m)\)-decomposable. Since k-NN is \((s,m)\)-decomposable, an adversarial example for \(x\) can be found by first determining all polyhedra \(P_{i}\) with the corresponding class label \(\hat{y}_{i}\) such that \(f(x)\
eq\hat{y}_{i}\). After that, the following minimization problem is supposed to be solved by the adversary:  
\[\min_{i:f(x)\
eq\hat{y}_{i}}\min_{x\in P_{i}}||x-\hat{x}||, \tag{6}\]  
where \(P_{i}\) is described by \(m\) linear constraints and the norm objective is convex. Thus, each inner minimization problem in (6) can be solved separately via solving a convex program. Solving the inner problem results in candidates \(\hat{x}^{i}\in P_{i}\)\(\forall i\). Taking the outer minimum over \(i\) with \(f(x)\
eq\hat{y}_{i}\) leads to the optimal adversarial example \(\arg\min_{\hat{x}^{i}}||x-\hat{x}^{i}||\). When \(k=1\), this is efficiently solvable, but, unfortunately, for \(k>1\), this attack does not scale well. The attack approach proposed is similar to the one proposed in [128]. In [130], an adversarial example attack against k-NN classifiers based on higher-order Voronoi diagrams is proposed. Assuming \(L_{i}^{(k)}\) is a subset of \(k\) samples from the training dataset \(X\), order-k Voronoi cell associated with \(L_{i}^{(k)}\) includes the points from that are closer to \(L_{i}^{(k)}\) than any other \(k\) points of \(X\). Voronoi facet is a boundary of an order-k Voronoi cell. In the algorithm, finding the set of facets that comprise an unvisited cell can be carried out by finding bisectors which are active with respect to this cell.