## 5 Attacks
### Attacks against Tree Ensembles  
The framework proposed in [129] can also be applied to tree-based classifiers since any decision tree is \((L,D)\)-decomposable where \(D\) is the tree depth and \(L\) is the number of the tree leaves. If a classifier is an ensemble of \(T\) trees, then it is \((L^{T},DT)\)-decomposable assuming that each tree in the ensemble has depth \(D\) and \(L\) leaves. Therefore, the region-based attack is based on solving optimization problem (6). In [131], a linear attack against a single decision tree is proposed. The main idea of the attack algorithm is to determine such a box for each leaf node that any example in this box is labelled according to this leaf. The node \(i\)'s box can be described as the Cartesian product \(B^{i}=(l_{1}^{i},r_{1}^{i}]\times\ldots\times(l_{d}^{i},r_{d}^{i}]\) of \(d\) intervals on the real line. Here \(d\) is the dimension of the samples. By definition, the box of the root node is defined as \((-\infty,+\infty)\times\ldots\times(-\infty,+\infty)\). Boxes of an internal node \(i\) children are calculated by splitting one of the box's intervals. If \(p\) and \(q\) are the \(i\)-th node's child on the left and on the right, respectively, their boxes \(B^{p}=(l_{1}^{p},r_{1}^{p}]\times\ldots\times(l_{d}^{p},r_{d}^{p}]\) and \(B^{q}=(l_{1}^{q},r_{1}^{q}]\times\ldots\times(l_{d}^{q},r_{d}^{q}]\) can be found as follows:  
\[(l_{t}^{p},r_{t}^{p}] = \begin{cases}(l_{t}^{i},r_{t}^{i}],\text{ if }t\
eq t_{i},\\ (l_{t}^{i},\min\{r_{t}^{i},\eta_{i}\}],\text{ if }t=t_{i}\end{cases}  \tag{7}\] \[(l_{t}^{q},r_{t}^{q}] = \begin{cases}(l_{t}^{i},r_{t}^{i}],\text{ if }t\
eq t_{i},\\ (\max\{l_{t}^{i},\eta_{i}\},r_{t}^{i}],\text{ if }t=t_{i}.\end{cases} \]  
Once the boxes for internal nodes have been computed, the boxes for leaf nodes can also be obtained using (7). Once the box for each leaf node has been computed, the minimal perturbation which changes a new unlabeled sample \(x\) to move towards a leaf node \(i\) can be found as follows:  
\[\delta(x,B^{i})= \begin{cases}0,\text{ if }\tilde{x}\in(l_{t}^{i},r_{t}^{i}], \\ \tilde{x}-r_{t}^{i},\text{ if }\tilde{x}>r_{t}^{i},\\ l_{t}^{i}-\tilde{x},\text{ if }\tilde{x}<l_{t}^{i}.\end{cases}  \tag{8}\]  
After that, the minimal perturbation is supposed to be computed as \(\delta=\min_{l:\eta_{i}\
eq\eta}||\delta(x,B^{i}||\). Here \(v_{i}\) is the label of leaf node \(i\). Such a perturbation can be found by testing boxes \(B^{i}\) for all the leaves. After that, the minimal perturbation is selected. This algorithm is linear-time and it allows for exact verification of a single decision tree robustness. Unfortunately, finding an exact optimal adversarial perturbation for an ensemble of trees requires exponential time and it is not scalable when the size of the ensemble and the depth of the trees grow [132]. In [133], a simple attack algorithm against a decision tree classifier is proposed. It follows the procedure described in the previous section. In particular, to find an adversarial sample, given a sample and a tree, an adversary simply searches for leaves with a class label that is different from the class of the unperturbed sample in the neighbourhood of the leaf corresponding to the decision tree's original prediction. After that, the path from the original leaf to the adversarial leaf is determined. Next, the sample is perturbed according to the conditions on this path in order to force the decision tree to misclassify the sample as the one belonging to the adversarial class. The shortest path based attack algorithm against a tree-based ensemble is proposed in [134]. The algorithm also focuses on attacking a binary tree-based classifier. Without loss of generality it assumes that an adversary attempts to flip the label for a new sample \(x\) labelled by the ensemble as 1. The shortest path in the algorithm is defined as the one requiring the minimum number of changes over features, i.e., minimising \(||x-\tilde{x}||\) to change the decision of a classification tree.