## 5 Attacks
### Attacks against Tree Ensembles
The search for the shortest path starts by finding all internal nodes of tree \(f_{i}\) of the ensemble for which \(f_{i}(x)>0\). After that, all the paths from each node \(n\) of the tree to leaf \(-1\) are found excluding the paths which include other node \(n^{\prime}\
eq n\). The shortest path \(P_{i}\) is selected from the paths needed to be modified to flip the label of \(x\). This algorithm essentially manipulates a vote casted by an individual decision tree via a local solution. For a tree ensemble, more steps are needed to find the features of \(x\) which are supposed to be modified. For this reason, a weight is assigned to each selected feature in the shortest path. The first feature at a parent node is assumed to be the most influential over a decision whereas impacts of other features in the shortest path are significantly smaller. It is worth noting that there may be multiple shortest paths with the same length. To avoid the situation when the same feature is overweighted because of this, only one shortest path is selected randomly. Once an optimal feature \(x_{k}\) has been found, the corresponding features in the shortest path are supposed to be removed according to the following rules: if length of \(P_{i}=1\), delete \(P_{i}\); if length of \(P_{i}>1\) and \(x_{k}\in P_{ij}\), delete \(x_{k}\) from \(P_{ij}\) if length of \(P_{i}>1\) and \(x_{k}\
ot\in P_{ij}\), delete \(P_{ij}\), where \(P_{ij}\) is the \(j\)-th path in the shortest path \(P_{i}\) in case there are several paths of the same length. In the black-box settings, i.e., when the attacker does not know the original model parameters, the search for adversarial examples can be carried out for a substitute set of trees. In [135], an iterative leaf tuple attack approach is proposed. The algorithm starts with a sample \(\tilde{x}\) which is already adversarial, i.e., \(f(\tilde{x})\
eq y\). At each step, a new sample \(\tilde{x}^{\prime}\) which has the minimum distance to \(x\) is selected within a small neighborhood around \(\tilde{x}\). The algorithm stops when \(\tilde{x}^{\prime}\) does not provide a smaller perturbation than \(\tilde{x}\). The algorithm uses the following notations. \(C(x)=(i^{(1)}(x),\ldots,i^{(K)}(x))\) denotes the index tuple of \(K\) prediction leaves from input \(x\). As previously, \(B^{i}=(l_{1}^{i},r_{1}^{i}]\times\ldots\times(l_{d}^{i},r_{d}^{i}]\) is the box of boundaries around the \(i\)-th node, such that each sample inside this box falls into this node. \(B(C(x))=\bigcap_{i\in C(x)}B^{i}=\bigcap_{i\in C(x)}(l_{1}^{i},r_{1}^{i}]\times \ldots\times\bigcap_{i\in C(x)}(l_{d}^{i},r_{d}^{i}]\) denotes the Cartesian product of the intersection of \(K\) such bounding boxes in the ensemble. If \(\tilde{x}\in B(\tilde{C})\) is the sample which minimizes the distance between \(\tilde{C}\) and \(x\) the indexes of trees that bound \(\tilde{x}\) are denoted as \(T_{bound}(\tilde{C})=\{t|\text{ OnEdge}(\tilde{x},B^{\tilde{C}^{(t)}})\forall t \in\{1,\ldots,K\}\}\), where \(\text{OnEdge}(x,B)\) is equal to 1 if \(x\) corresponds to the right or the left bound of \(B\) for at least one dimension. The attack proposed is white-box as the adversary is required to have perfect knowledge of all the trees in the ensemble. Study [136] proposes a simple black-box cube attack against an ensemble of boosted trees. The attack algorithm proposed aims to craft an adversarial perturbation \(\delta:||\delta||\leq e\) against binary tree-based classifier \(f(x)\), i.e., label \(y=1\) if \(f(x)>0\) and \(y=-1\) if \(f(x)\leq 0\). Thus, an unlabeled sample \(x\) with label \(y\) is classified correctly if \(yf(x)>0\). Projecting a perturbed sample \(\tilde{x}+\delta\) onto ball \(B(x,\epsilon)\) means that if \(\tilde{x}+\delta\) is outside of that ball it is moved to the closest point inside the ball.