Faster Repeated Evasion Attacks in Tree Ensembles
Authors: Lorenzo Cascioli
Laurens Devos
Ondrej Kuzelka
Jesse Davis
Venue: NeurIPS 2024 poster (2024)
Keywords: ML
Tree Ensembles
Verification
Evasion Attacks
Adversarial Attacks
Primary area: safety_in_machine_learning

Abstract: Tree ensembles are one of the most widely used model classes. However, these models are susceptible to adversarial examples, i.e., slightly perturbed examples that elicit a misprediction. There has been significant research on designing approaches to construct such examples for tree ensembles. But this is a computationally challenging problem that often must be solved a large number of times (e.g., for all examples in a training set). This is compounded by the fact that current approaches attempt to find such examples from scratch. In contrast, we exploit the fact that multiple similar problems are being solved. Specifically, our approach exploits the insight that adversarial examples for tree ensembles tend to perturb a consistent but relatively small set of features. We show that we can quickly identify this set of features and use this knowledge to speedup constructing adversarial examples.

Faster Repeated Evasion Attacks in Tree Ensembles
Lorenzo Cascioli
Laurens Devos
Department of Computer Science
Department of Computer Science KU Leuven Leuven, Belgium
KU Leuven
Leuven, Belgium
lorenzo. www.ioaiioicciieieeeeeeee.. be
Ondrej Kuzelka
Jesse Davis
Faculty Electrical Engineering
Department of Computer Science
Czech Technical University in Prague Prague, Czech Republic
KU Leuven Leuven, Belgium
Abstract
Tree ensembles are one of the most widely used model classes. However, these mod- els susceptible to adversarial examples, i.e., slightly perturbed examples that elicit a misprediction. There has been significant research on designing approaches construct such examples for ensembles. But this is computationally chal- lenging problem that often must be solved large number of times (e.g.. for all examples in training set). This compounded by the fact that current approaches attempt to find such examples from scratch. In contrast, we exploit the fact that multiple similar problems are being solved. Specificallyy our approach exploits the insight that adversarial examples for tree ensembles tend to perturb a consistent but relatively small set of features. We show that we can quickly identify this of features and use this knowledge to speedup constructing adversarial examples.
Introduction
One of the most popular and widely used classes of models is ensembles which encompasses techniques such as gradient boosting [16] and random forests [3] However, like other flexible model classes such as (deep) neural networks 28 they are susceptible to evasion attacks 23 That is, an adversary can craft an imperceptible perturbation that, when applied to an otherwise valid input example, elicits a misprediction by the ensemble, As an example, consider bank that uses learned model to assess whether to approve or deny loan applications. In this setting, an evasion attack could entail slightly altering a potential customer's data (e.g., adding one month their work seniority) that results in the model making different decision on the customer's 's application. The slightly modified customer record an adversarial example. There is significant interest in reasoning about tree ensembles to both generate such adversarial examples [5] 36) and perform empirical robustness where the goal is to determine how close the nearest adversarial example is.
checking 23 10
Generating adversarial examples is an NP-hard problem 23 which has spurred the development of approximate techniques [36 10]. These methods exploit the structure of the trees to find adversarial examples faster, e.g., by using graph transformations S or discrete (heuristic) search [36] I0 12].
Still, these techniques can be slow, particularly there a large number of attributes in the domain. This is compounded by the fact that one often wants to generate large sets of adversarial examples.
weakness existing approaches is that they ignore the fact that adversarial example generation is often a sequential task where multiple similar problems are being solved in a row. That is, one has access large number of "normal" examples each of which should be perturbed elicit
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

misprediction. Alas, existing approaches treat each considered example in isolation and solve the problem from scratch. However, there are likely regularities among the problems, meaning that the algorithms perform redundant work. If these regularities can be identified efficiently and this information can be exploited to guide the search for an adversarial example, then the run time performance of repeated adversarial example generation can be improved.
Studying these regularities in order to make adversarial example generation faster is an important problem. First, it advances our understanding of the nature of adversarial examples in tree ensembles and their generation methods. This might inspire improvements to generation methods, and in turn
lead to better defense or detection methods. Second, model evaluation by verification [26] 29 [0] is quickly becoming important as machine learning applied in sensitive application areas. Being able to efficiently generate udversarial examples is crucial for computing empirical robustness (e.g.. [TO), adversarial accuracy (e-g.. (32) ), and for model hardening (e.g., (23). Third, some scenarios exist where an attacker would want to perform a large scale evasion attack. For example, some DNS registries use models to flag new domain registrations as potentially malicious (e.g., for phishing, fake webshops) 227 and scammers likely need to register many such domains. Finally, techniques in the planning community for analyzing policy safety through predicate abstraction involve performing repeated verification queries on the same model 30 3 222]
We propose a novel approach that analyzes previously solved adversarial example generation tasks to inform the search for subsequent tasks. Our approach is based on the observation that for fixed learned tree ensemble, adversarial examples tend to be generated by perturbing the same, relatively small set of features. We propose theoretically grounded manner to quickly find this set of features. We then propose two novel strategies to use the identified features to guide the search for adversarial examples, one of which is guaranteed to produce an adversarial example if it exists. We apply our proposed approach to two different algorithms for generating adversarial examples 223 [0]. Empirically, our approaches result in speedups of up to 36x/21x and on average of 9x/4x (+ 8x/3x). The source code for the presented algorithms and all the experiments publicly available at https 7/gi
2 Preliminaries
We briefly explain tree ensembles, evasion attacks, and the two adversarial generation methods used in the experiments. We assume d-dimensional input space X' C ARd and binary output space y = 13. We focus on binary classification because most existing methods for generating adversarial examples for tree ensembles are designed for this setting 23 10
Tree Ensembles Tree ensembles include algorithms such as (gradient) boosted decision trees (GBDTs) 16, 9] and random forests B3 25). A tree ensemble contains a number of trees and most implementations only learn binary trees. A binary tree T contains two types of nodes. Internal nodes store references to a left and a right sub-tree, and split condition on some attribute f in the form of less-than comparison X₁ т, where is the split value. Leaf nodes have no children and only contain an output value. Each tree starts with a rool node, the only one without a parent.
Given example v. an individual tree is evaluated recursively starting from the rool node. In each internal node, the split condition is applied and it is satisfied, then the example sorted to the left subtree and if not it is sorted to the right one. This procedure terminates when a leaf node is reached. The final prediction of the ensemble T(x) is obtained by combining the predicted leaf values for each tree in the ensemble. In gradient boosting, the class probability is computed by applying sigmoid transformation to the sum of the leaf values.
Evasion Attacks An evasion attack involves manipulating valid inputs x into adversarial examples T in order to elicit misprediction 23 Following existing work on tree ensembles [23] 7 10], we say that ă is an adversarial example for normal example x when (1) | - æIloo < 5 where 5 is a user-selected maximum distance (i.e., the two are sufficiently close), (2) the ensemble predicts the correct label for x, and (3) the model's predicted labels for ă and r differ.
We briefly describe the two existing adversarial example generation methods A: (T, x. 5, /max) + (SAT($), UNSAT, TIMBOUT) used in this paper: kantchelian (3 and veritas [10. These methods take as input ensemble T, a normal example x, maximum perturbation size 8, and
2

---

timeout mmax. They output (ž) where è is an adversarial example for z, UNSAT, indicating that no adversarial example exists, or TIMEOUT, indicating that no result could be found within max.. Timeouts are explicitly handled because adversarial example generation is NP-hard 23
kantchelian formulates the adversarial example generation task mixed-integer linear program (MILP) and uses a generic MILP solver (e.g., Gurobi [20]). Specifically, kantchelian directly minimizes the å || ~| م0 value. Given an example æ. computes:
min ||
- x x|
subject to T(x) T
(I)
This approach exploits the fact that tree ensemble can be viewed as a set of linear (in)equalities.
Three sets of MILP variables are used. Predicate variables p; represent the split conditions, i.e., each ps logically corresponds to a split on an attribute f: p; = leaf node is active. The bound variable b represents the 6x distance between the original example x and the adversarial example E. Constraints between the variables encode the structure of the tree. A set of predicate consistency constraints encode the ordering between splits. For example, if two split values T1 < 72 appear in the tree for attribute f. and p1 f < T1 and P2 = f < Tg. then p1 = p2. Leaf consistency constraints enforce that a Ieaf is only active when the splits on the root-to-lcaf path to that Icaf are satisfied. Lastly, the mislabel constraint requires the output be a certain class: for leaf values U/. E, v,4y S O. The objective directly minimizes the bound variable.
T. Leaf variables I indicate whether
veritas improves upon kantchelian in terms of run time by formulating the adversarial example generation problem as a heuristic search problem in a graph representation of the ensemble (originally proposed by (8). The nodes in this graph correspond to the leaves in the trees of the ensemble. Guided by heuristic, the search then repeatedly selects compatible leaves. Leaves of two different trees are compatible when the conjunction of the split conditions along the root-to-leaf paths of the leaves are logically consistent. For given 8, veritas solves the following optimization problem
optimize T(x) (T) subject to || =0 < 6
The output of the model T is maximized when the target class for म is positive, and minimized otherwise. While veritas can also directly optimize ó, in this paper we will use a predefined ō for veritas. To the best of our knowledge, veritas is the fastest approximate evasion attack for tree ensembles (see Appendix B.I
3 Method
Adversarial example generation methods are often applied in the following setting:
tree ensemble T, set of test examples D, and maximum perturbation size 6 Generate adversarial examples for each x E DD
Given
The goal of this paper is to exploit the fact that adversarial examples are sequentially generated for each example in D. By analyzing previously found adversarial examples, we aim to improve the efficiency of adversarial example generation algorithms by biasing the search towards the perturbations that are most likely to lead to an adversarial example.
Our hypothesis is that some parts of the ensemble are disproportionately sensitive small perturba- tions, i.e., crossing the thresholds of split conditions in these parts of the ensemble results in large changes in the predicted value. Prior work has hypothesized that robustness is related features and that such features are included in models because learners search for any signal that improves predictive performance (21). One would expect that the attributes used in the split condi- tions in these disproportionately sensitive parts are exploited by adversarial examples more frequently than other attributes. Figure iillutrrates this point by showing how often each attribute is perturbed in set of a 10 000 adversarial examples generated by kantchelian for two datasets. The bar plots distinguish among attributes are (1) never modified by any adversarial example (left), (2) modified by at least one but at most 5% of all adversarial examples (middle), and (3) modified by more than 5% of the adversarial examples (right). Less than 10% of the attributes are used by more than 5% of the adversarial examples. The figure shows that regularities exist in constructed adversarial examples: examples generated for different normal examples tend to exhibit perturbations to the same small set of attributes. Thus the two questions are how can one identify these frequentlymmodife attributes and how can algorithms exploit this knowledge to more quickly generate adversarial examples.
fragile
We are abusing termiooloyy: here, ((x) is the predicted probability. Previously, it the predicted label.
3

---

Number of attribules
mmist
webspam
784
254
392
127
< 5% 5%
5% 2 5%
Frequency modifications
Figure Bar plots showing that most attributes are not modified by the majority of adversarial examples on the miist and webspam datascts. The leftmost bar shows the number of attributes that are never changed by any of the 000 adversarial examples generated by kantchelian' approach. The middle bar shows the number of attributes that modified at least once but most by 5% of the adversarial examples. The rightmost bar shows the number of frequently modified features.
Our proposed approach has parts. The first part simplifies the search for adversarial examples by only allowing perturbations to a limited subset of features. Namely, we exploit the knowledge that certain feature values are fixed to simplify the ensemble, by pruning away branches that never be reached. The second part identifies a subset of commonly perturbed features by counting how often each feature is perturbed by adversarial examples. The size of this subset is determined by applying theoretically grounded statistical test.
3.1 Modifying the Search Procedure
Our proposed approach speeds up the adversarial example generation procedure by limiting the scope of the adversarial perturbations to a subset of features Fss. This section assumes that we are given such subset of features. The next section covers how to identify these features.
We consider three settings: full, pruned, and mixed. The full setting is the original configuration of kantchelian and veritas: the methods may perturb any attribute within a certain maximum distance 8. That is, for each attribute f E with value Ty, the attribute values are limited to [xy 6, x 5]. Algorithm I summarizes the pruned and mixed approaches. We now describe both in greater detail.
Algorithm Fast repeated adversarial example generation
parameters: maximum perturbation size 8, timcouts efull and torx for full and pruned, genera- tion method A: :
1:
+ (SAT(T), UNSAT, TIMEOUT)
2: function GENERATE D, Fs, mixed flag)
3: D+0
4:
for E D do
5:
Tprun f- PRUNE full: Fs,
(Sec. 3.1
6:
+ A (T prun, 5, (prua)
7:
a + SAT(() mixed flag set then a A (Taal,, x, 5, fful"
8:
9:
end
D D+DURE {a}
11: end for
return: D
13: end function
Pruned Approach The pruned setting disallows modifications to the attributes the non-selected set of attributes Fas = F\ Fs. We accomplish this by pruning the trees in the ensemble. Any node splitting on attributes child node that can be reached by examples with the fixed value for the attribute. Figure 2 shows an example of this procedure. We refer to this procedure as PRUNE(T: a.). The adversarial example generation methods can be applied normal to the pruned ensemble, but they will only generate adversarial examples with perturbations to the attributes in Fs. Pruning simplifies the MILP problem of kantchelian because all predicate variables p; that correspond to splits in internal nodes of pruned
FNS removed. Its parent node directly connected the only

---

HEIGHT < 200
HEIGHT < 200
AGE < 50
Figure 2: An example tree using two attributes HEIGHT and AGE (left). Suppose Fxs {AGE). Given an example where AGE = 55, we can prune away the internal node splitting on AGE. In the resulting tree (right), subtree (b) is pruned because it is unreachable given that AGE 55 and only subtrees (a) and (c) remain.
subtrees, and leaf variables I that correspond to leaves of pruned subtrees be removed from the mathematical formulation. For veritas, the search space is reduced size because the pruned leaves removed from the graph representation of the ensemble. Hence, for both systems, average, the problem difficulty is reduced by pruning the ensembles.
Pruning the trees does not affect the validity of generated adversarial examples: if T is an adversarial example for a normal example x generated on a pruned ensemble, then T also an adversarial example for the full ensemble.
Proposition 3.1. Given normal example that is correctly classified by the full ensemble That- Let T prun = PRUNE(TJJuL, fult, Fs,z) and Tt A(Tpran; T. ô, (max) (i.e., Tprua(2) + Torwn (3) and ||2 2 < 6). Then it holds that [z)((z) o (T).
Proof. Because only branches not visited by removed, T (p)un(x) Tuu The values for features in ENs are fixed, so these values are equal between x and æ. Hence, 2 only visits branches in Thu that are also in T pran. Therefore, Tpron (ă) (T).
However, an UNSAT generated on a prumed ensemble inconclusive: it might still be the case that an adversarial example exists for the full ensemble, albeit one with perturbations to features in Eus- The pruned setting generates a f'als negative if reports UNSAT, yet the full setting reports SAT.
Mixed Approach The mixed setting takes advantage of the fast adversarial generation capabilities of the prumed setting, but falls back to the full setting when the pruned setting returns an UNSAT or times out. A much stricter timeout tprun is used for the pruned setting to fully take advantage of the fast SA while avoiding spending time on an uninformative UNSAT. The mixed setting is guaranteed find an adversarial example if the full setting can find one.
Theorem 3.2. Assume normal example x and maximum distance 6. an adversarial example can be found for the full ensemble Tal then the mixed setting is guaranteed to find an it such that || x 111 8 and (1) + (T)
Proof. The mixed setting first operates on the pruned ensemble Tprun using a tight timeout and optimizes Equation or 2 using kantchelian veritas respectively. This returns (1) adversarial example ă. (2) an UNSAT or (3) times out. In case (1), the generated adversarial example is also an adversarial example for the full ensemble (Prop B. In cases (2) and (3), the mixed setting falls back to the full setting operating on the full ensemble T fult with the same timeout, Hence, it inherits the full method's guarantees.
3.2 Identifying Relevant Features
A good subset of relevant attributes Fs should satisfy two properties. First, it should minimize the number of false negatives, which occur when the pruned approach reports UNSAT. but the full approach reports SAT. Second, the feature subset should be small. The smaller Fs is, the more the ensemble can be pruned, and the larger the speedup is. These two objectives are somewhat in tension. Including more features will reduce the number of false negatives but limit the speedups, whereas using a very small subset will restrict the search too much resulting many false negatives (or slow calls to the full search in the mixed setting). The procedure is given in Algorithm 2
5

---

We address the first requirement by adding features to the subset that are frequently perturbed by adversarial examples. We rank features by counting how often each one differs between the perturbed adversarial examples in D so far and their corresponding normal examples in D.
The second requirement met by statistically testing whether the identified subset guarantees that the false negative rate is smaller than a given threshold r with probability least 1 1 7), for specified confidence parameter 1). If it is not guaranteed, then the subset is expanded. This is done at most 4 times for subsets of 5%, 10%, 20%, 30% of the features (EXPANDFFATUREEST) Algorithm 2). If all tests fail, then final feature subset of 40% of the most commonly modified features is used. We do not go beyond 40% because using the full feature set is then more efficient. Each test is executed on small set of n generated adversarial examples. A first zeroth set used merely for obtaining the first feature counts.
Fs, D, D) in
The statistical tests performed as follows. The null hypothesis is that FNR is greater than the threshold т. Take Dr = (21, .2....,INy INN the dataset we use to find the feature subset Fs. We define v (v,, ,2....., UN) ) to be the binary vector such that v; 1 if the pruned search with the feature subset Fs returns UNSAT for the example x; but the full search returns SAT, and H; 0 otherwise. Then the true false negative rate corresponding to Fş
be written as FNR E== U4. The small set of examples from which we are estimating the false negative rate is a random vector X = (X1, X2,....... X2...., sampled without replacement from Dr. We also define = =VV, V,,..., Vn), where V, is the binary random variable defined analogically to how we hypergeometric random variable. We use the
defined It follows that E is distributed method of inversion of acceptance intervals to find a one-sided confidence interval [0; for the false negative rate with confidence level equal to given 1 7) (see, e.g., Section 5.2 in 2 ), exploiting the fact that the cumulative distribution function of a hypergeometric distribution can be computed efficiently CONNIDENCEELNERVV confidence interval does not contain the threshold r. It follows from the basic properties of confidence intervals that this yields the desired test with confidence 1 17. Since execute the test 4 times in correction factor (we use confidence level 0.9). Note that the algorithm, we apply a union- there is trade-off. The higher n, the better the statistical estimates and the counts are, but also the more examples we process with a potentially suboptimal feature subset.
C, 17) in Algorithm 2}. We reject the null hypothesis if the
Algorithm 2 Find feature subset 1: parameters: set of normal examples D, sample size n, acceptable false negative rate r, confi- dence parameter 1)
2: Fs + 0
3: for k 0..4 do
4: DD <- GENERATE(T. D[kn, k(n + 1)], Fs, true)
5:
+- number of false negatives in D
6:
[0; AJ + INNEIDEACEENTERVA..C n,,))
7:
if the threshold T is in [0; A], then EXPANDFEATURESSET(S,, D,
8: else break the loop
9:
end for
10: return: Fs
4 Experiments
Empirically, we address three questions: (Q1) Is our approach able to improve the run time of gener- ating adversarial examples? (Q2) How does ensemble complexity affect our approach's 's performance? (Q3) What is our empirical false negative rate?
Because the described procedure is based on identifying a subset of relevant features, it makes sense to exploit it only when the dataset has large number of dimensions. Therefore, present numerical experiments for ten binary classification tasks on nigh-dimensional datasets, using both tabular data
and image data, as shown in Table [
Experimental Setup We apply 5-fold cross validation for each dataset. We use four of the folds to train an XGBoost [9] random forest [3] 22 GROOT forest (a robustified ensemble type (32))

---

ensemble T. From the test set, we randomly sample 100 normal examples and attempt to generate adversarial examples by perturbing each one using the kantchelian or veritas attack. Table] also
reports the adopted values of maximum perturbation ö and the hyperparameters of the learned ensembles, which were selected via tuning using the grid search described in Appendix B The experiments were run on an Intel(R) E3-1225 CPU with 32GiB of memory.
Table 1: Datasets' characteristics: N and #F are the number of examples and the number of features. higgs and prostate are random subsets of the original, bigger datasets. Multi-class classification datasets were converted to binary classification; for covtype we predict majority-vs-rest, for mnist and finnist we predict classes 0-4 vs. classes 5-9, and for sensorless classes 0-5 vs. classes 6-10. We also report adopted values of max allowed perturbation 5 and learners' tuned hyperparameters after the grid search described in Appendix B Each ensemble T has maximum tree depth and contains M trees. The learning rate for XGBoost 1s GROOT robustness is defined by e.
GGBottt
RF
GROOT
Dataset
N
#F
6
M
7
8
M
d
M
d
covtype
581k
54
0.1
50
0.9
0.3
50
10
0.4
50
10
0.01
finiist
70k
784
0.3
50
0.1
0.3
50
10
0.4
50
10
0,3
higgs
250k
33
0.08
50
0.08
0.4
miniboone
130k
51
0,08
50
0.1
0.08
50
10
0.5
50
10
0.01
mnist
70k
50
0.3
0.4
0.3
prostate
100k
103
0.1
50
0.5
0.2
50
I0
0.2
50
10
0.01
roadsafety
11lk
33
0.06
50
0.5
0.12
10
0.2
10
0.05
sensorless
58.5k
48
0,06
5U
0.5
0.12
10
0.2
10
0.01
vehicle
9Sk
101
0.15
50
0.1
0.15
10
0.4
50
10
0.1
webspam
350k
0.04
50
0.1
The pruned and mixed settings work as follows. We use the procedure from Section 3.2 to select
subset of relevant features. We use r = 0.25, n = 100 and 1j = 0.1. We then apply A Aggrithhm [ we generate 5 sets of adversarial examples to (1) find which features are perturbed most often and (2) determine the size of the feature subset F's. Therefore the extracted feature set gives us 1 17 = 90%
confidence that our true false negative rate is below 25%. After Algorithm 2 terminates, F's is fixed, and we run the pruned and mixed settings on all the remaining test examples (Algorithm [T. We set timeout of one minute for the full setting, and much stricter timeout of (kantchelian) or 0.1 (veritas) seconds in the pruned setting. We can be stricter with veritas as it is an approximate method that is faster than the exact kantchelian
Q1: Run Time Table reports the average run time for the full setting and the average speedup given by the pruned and mixed settings. We present here results for XGBoost and random forest, and report results for GROOT together with more extended results in Appendix C Considering all three model types and both attacks, speedups for the pruned setting in the range 1.4x-36.2x with an average of 9x (= 8x), and for the mixed in the range 1x-x5x with an average of 4x (+: 3x).
We notice that generating adversarial examples is more difficult for random forests (RF) than XGB. This leads to our strategies offering larger wins for RF than for XGB, with average speedups of 9.4x/3.5x (# 7. 7.2x/1.66 for RF and 4.7x/2.7x (# 3.4x/1 1.2x) for XGB. The robustified GROOT forests are even harder to attack, meaning our methods offer even larger improvements with average speedups of 11.4x/4.9x (+: 9.9x/5.0x)
Tables 5 and 6 in the supplement also report additional statisties on the presented experiments. On average, the mixed setting falls back to the full search 10.5% of the time. The model and attack type do not seem to have a strong influence on the proportion of calls to the full search. This helps it achieve a speedup by taking advantage of the fast SAT results of the prumed setting while still offering the theoretical guarantee from Theorem 3.2
We also report the attack success rate, which is the fraction of times where our methods generate an adversarial example given that a valid adversarial example exists for the full model. The pruned search has an average success rate of 90% (# 6%). The mixed search has success rate 100% by definition (Theorem 3.2)
2 Appenddix provides a sensitivity analysis for the hyperparameter settings the statistical test and timcouts.
See Tables and din the supplement.
7

---

Table 2: Average times and speedups when attempting to generate 10000 adversarial examples using kantchelian/verita on an XGBoost/random forest ensemble for full, pruned and mixed. A means that the dataset exceeded the global timeout of six hours.
Kantchelian XGB
Kantchelian RF
Veritas XGB
Veritas RF
Jull
primed
mixed
fiil
pruned
mixed
Jull
pramed
mixed
full
prined
mixed
coviype
9.9tn
3.3%
2.1x
25.7m
11.0%
3.7x
5.3s
1,7x
1.4%
45.0s
6.0%
2
fmnistt
1.5h
4.9%
3.9%
56.2m
7.8
4.3x
43.6s
14x
1.3%
6.6m
3.6x
3.0%
biges
3.3h
4.1x
1.8x
5.1h
3.0x
14x
20.4a
2.9x
2.4x
41.8m
21.4x
2.5x
miniboone
6.0h*
10.9%
3.4X
6.0h*
9.4X
5.2x
1.2m
8.4%
5.9%
12.9m
1188x
6.4x
mnist
23.9t
6m
3.3m
prostate
12.8m
3.4%
2.8%
6.0h"
11.8%
5.2x
9.9s
2.5x
2.2%
23.7m
16.9%
2.6x
rondualet
10.7m
3.0X
2.0%
4m.2m
5.4%
2.3x
11.4s
2.7%
2.1X
40.6m
33.5x
3.1%
sensorless
29.8m
2.3%
2.1X
52.5m
5.7%
3,6x
12.18
2.9%
188
4.1m
4.7%
1.5x
vehicle
2.5h
5.9%
3.4x
3.8h
7.1%
5.8%
19.4m
15.6%
1.9%
42.8m
9.1x
1.1x
webspam
24.2m
5.7%
18.8s
1.2x
Figure 3 shows the number of executed searches as function of time for four combinations of attack algorithm and model type For XGB, both attacks benefit. Moreover, the mixed setting is typically very close in run time to the pruned. On RF, the pruned setting offers larger speedups. However, we more noticeable difference between the pruned and the mixed search several datasets. This indicates that the mixed strategy falls back more often to an expensive search.
mnist
prostate
roadsafery
scnsorless
scarches
10k
Kantchelian
XGB
10m
20m
5m
10m
5m
10m
0
20m
seurches
10k
Kantchellan
RF
0
20m
40m
2.5h
5h
0
20m
40m
0
25m
50m
# searches
Veritas
XGB
scarches
10k
Veritas RF
2m
10m
20m
0.5h mixed
0
5m
full
pruned
Figure 3: Average run times for 10000 calls to full, prumed and mixed for kantchelian (top) and veritas (bottom). Results are given for both XGBoost and random forest for four selected datasets.
Finally, it is natural to wonder how the quality of the generated adversarial examples is affected by modified search procedure. While this difficult to quantify, Figure provides some examples of constructed adversarial examples for the mnis/ dataset and XGBoost ensemble. Visually, the examples constructed by full and pruned settings for both attacks are very similar. The examples constructed using kantchelian look more similar to the base example than those for veritas because kantchelian finds the closest possible adversarial example whereas veritas has a different objective: constructs adversarial example that will clicit highly confident misprediction. See Appendix for more generated examples.
B
Q2: Scaling Behavior Two key hyperparameters of tree ensembles are the maximum depth of each learned tree and the number of trees in the ensemble. We explore how varying these affects our approach, employing the same setup as described in Q1. We use the mnist dataset and omit
'The supplement shows these plots for all datasets plus for GROOT forests (see Appendix C

---

KAN Full
KAN prumed
VER full
VER pruand
3
T
2
Figure 4: Generated adversarial examples for an mnist digit and an XGBoost ensemble, using both attacks (full vs pruned).
kantchelian with RFs due its computational cost. Figure (top) shows how the run time to perform 10000 searches varies as function of the maximum tree depth for fixed ensemble size of 50. The run times for the pruned and mixed approaches grow very slowly as the depths are increased. In contrast, the sull search scales worse: deeper trees lead to higher run times. Figure S (bottom) shows how the run time to perform 10 000 searches varies as function of the ensemble size for a fixed maximum tree depth of for XGB and 10 for RF. Again, the praned and mixed approaches show much better scaling behavior. Note that veritas's 's full search shows a very large jump on RF when moving from 75 to 100 trees. These results indicate that our approaches will offer even better time performance than the standard full search for more complex ensembles.
Veritas XGB
Verilas
Kantchelian
2000
time (3)
50
25
50
max depth
10
tine (+)
:0
1000
pruned
full
1000
25
#tre05
25
50
75
100
25
50
75
100
25
50
75
100
Figure 5: Run time of full, mixed and pruned settings using veritas XGB, veritas RF, kantchelian XGB on mnist, and varying the max depth (top) and number of estimators in the ensemble (bottom).
Q3: Empirical FNR We use Algorithm to bound the false negative rate be less than 25% with high probability. Tables and 6| the supplement report the empirical false negative rates for all experiments. The average false negative rate is 7.5% and the maximum is 17.1%. Hence, empirically we achieve better results than the theory guarantees. Neither the ensemble method nor the attack type strongly influence the false negative rate. These small false negative rates still allow dramatically reducing the number of considered features. On average, Fs contains 17% the features. Out of 300 experiments we only select the maximum percentage of features 17 times. Generally, kantchelian requires slightly more features than veritas and RF models requires slightly more features than XGB/GROOT models.
To provide better intuition on the relationship between the empirical FNR and the speedup, Figure 6 shows this tradeoff two datasets using XGBoost. In essence, higher FNRs correspond to smaller feature subsets, hence larger speedups.
Related Work
Adversarial examples have been theoretically studied and defined in multiple different ways 14
18
Approaches reason about learned tree ensembles have received substantial interest in recent years including algorithms to perform evasion attacks 23 [5] (i.e., generate adversarial examples),
$5 folds x 10 datasets 3 ensemble types attacks

---

Kantch, mnist
Kantch. - prostate
Veritas - mnist
Veritas - prostate
10x
10x
4x
4x
Speedup
ox
Ox
0X
0X
Emp. FNR
0.2
0.2
0.0
0.2
Speedups achieved by the pruned setting when attempting to generate 10000 adversarial examples using kantchelian (left) and veritas (right) on an XGB ensemble, varying the empirical false negative rate. The dotted horizontal line corresponds to a speedup of 1x, i.e., same run time of the full setting.
Figure 6:
perform robustness checking 8 and verify that the ensembles satisfy certain criteria 26 29
Kantchelian al. [23] were the first show that tree ensembles are susceptible evasion attacks. Their MILP formulation is still the most frequently used method to check robustness and generate adversarial examples. Beyond this exact approach, several approximate approaches exist
35
36 though not all of them are able to generate concrete adversarial examples (e.g.. g 35
robust. Approaches for this include adding generated adversarial examples to the training data (model hardening) [23], modifying the splitting procedure 7 32]. Gaining further insights into how evasion attacks target tree ensembles, like those contained in this paper, may inspire novel ways to improve the robustness of learners.
Other work focuses making tree ensembles
Another line of work aims directly training tree ensembles that admit verification in polynomial time [S] [13. However, a drawback to current approaches is that they result in (large) decreases in predictive performance.
Finally, performing evasion attacks has been studied for other model classes with deep neural networks receiving particular attention 28 17 24 6.. However, ttae-offthhe-rr algorithms are tailored to one specific model type as they typically exploit specific properties of the model, c.g., the work on tree ensembles often exploits the logical structure of decision tree.
6 Conclusions
This paper explored two methods to efficiently generate adversarial examples for tree ensembles. We showed that considering only the same subset of features is typically sufficient to generate adversarial examples for tree ensemble models. We proposed a simple procedure to quickly identify such a subset of features, and two generic approaches that exploit it to speed up adversarial examples generation. We showed how to apply them to an exact (kantchelian) and approximate (veritas) evasion attack on three types of tree ensembles, and discussed their properties and run time performances.
Limitations. Our approach speeds up evasion attacks the specific scenario when the same model is repeatedly attacked. Plus, it excels on nigh-dimensional datasets. Our evaluation only considered loo attacks, whereas other norms such 4 and l2 are also relevant.
Impact Statement. While this work does make attacking tree ensembles faster, it is also important to understand what attackers may do. This work also targets increasing the applicability of robustness checking and hardening techniques, which can lead to approaches for training more robust models.
Acknowledgements. This research is supported by the Research Foundation Flanders (FWO, LC: 1118125N), The European Union's Horizon Europe Research and Innovation program under the grant agreement TUPLES No. 10107014 49 (LC, LD, OK, JD), and the Flemish Government under the "Onderzneksprogrrmmaa Artificöle Intelligentie (AI) Vlaanderen" program (JD).
References
[1] M. Andriushchenko and Hein. Provably robust boosted decision stumps and trees against adversarial attacks. In Advances in Neural Information Processing Systems, 2019,
10

---

[2] J. Bartroff, G. Lorden, and L. Wang. Optimal and fast confidence intervals for hypergeometric successes. The American Statistician, 2023.
[3] L. Breiman. Random forests. Machine learning, 2001.
[4] S. Calzavara, C. Lucchese, G. Tolooei, S. A. Abebe, and S. Orlando. Treant: training evasion- aware decision trees. Data Mining and Knowledge Discovery, 2020.
[5] S. Calzavara, L. Cazzaro, G. E. Pibiri, and N. Prezza. Verifiable learning for robust tree ensem- bles. In Proceedings of the 2023 ACM SIGSAC Conference Computer and Communications Security, 2023.
[6] N. Carlini and D. Wagner. Towards evaluating the robustness of neural networks. In IEEE Symposium Security and Privacy, 2017.
[7] H. Chen, H. Zhang, D. Boning, and C.-J. Hsieh. Robust decision trees against adversarial examples. In Proceedings of the 36th International Conference on Machine Learning. 2019.
[8] H. Chen, H. Zhang, S. Si, Y. Li, D. Boning, and C.-J. Hsieh. Robustess verification of tree-based models. In Advances in Neural Information Processing Systems, 2019.
[9] т. Chen and C. Guestrin. XGBoost: A scalable tree boosting system. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2016.
[10] L. Devos, W. Meert, and J. Davis. Versatile verification of tree ensembles. In Proceedings of the 38th International Conference on Machine Learning, 2021.
[11] L. Devos, W. Meert, and J. Davis. Verifying tree ensembles by reasoning about potential instances. In Proceedings of the 2021 SIAM International Conference Data Mining (SDM), 2021.
[12] L. Devos, L. Cascioli, and J. Davis. Robustness verification of multiclass tree ensembles. In Proceedings of the AAAI Conference on Artificial Intelligence, 2024.
[13] L. Devos, D. C. Oruç, W. Meert, H. Blockeel, and J. Davis. Tree ensemble compression for interpretability, In Advances in Interpretable Machine Learning and Artificial Intelligence (AIMLAI), 2024.
[14] D. I. Diochnos, S. Mahloujifar, and M. Mahmoody, Adversarial risk and robustness: General definitions and implications for the uniform distribution. In Advances in Neural Information Processing Systems, 2018.
[15] G. Einziger, M. Goldstein, Y. Sa'an and I. Segall. Verifying robustness of gradient boosted models. In Proceedings of the AAAI Conference on Artificial Intelligence, 2019.
[16] H. Friedman. Greedy function approximation: gradient boosting machine. Annals of statistics, 2001.
[17] I. J. Goodfellow, J. Shlens, and C. Szegedy. Explaining and harnessing adversarial examples. In International Conference on Learning Representations, 2015.
[18] Gourdeau, V. Kanade, M. Kwiatkowska, and J. Worrell. On the hardness of robust classifica- tion. Journal of Machine Learning Research, 2021.
[19] J.-Q. Guo, M.-Z. Teng, W. Gao, and 7. Zhou. Fast provably robust decision trees and boosting. In Proceedings of the 39th International Conference on Machine Learning, 2022.
[20] Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2023. URL http::/::
gurobi com)
[21] A. Ilyas, S. Santurkar, D. Tsipras, L. Engstrom, B. Tran, and A. Madry. Adversarial examples not bugs, they are features. In Advances in Neural Information Processing Systems, 2019.
[22] C. Jain, L. Cascioli, L. Devos, M. Vinzent, M. Steinmetz, J. Davis, and J. Hoffmann. Safety verification of tree-ensemble policies via predicate abstraction. In Proceedings of the 27th European Conference on Artificial Intelligence, 2024.

---

[23] A. Kantchelian, J. D. Tygar, and A. Joseph. Evasion and hardening of tree ensemble classifiers. In Proceedings of the 33th International Conference on Machine Learning, 2016.
[24] G. Katz, C. Barrett, D. Dill, K. Julian, and M. Kochenderfer. Reluplex: An efficient SMT solver for verifying deep neural networks. In Computer Aided Verification, 2017.
[25] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 2011.
[26] F. Ranzato and M. Zanella. Abstract interpretation of decision tree ensemble classifiers. In Proceedings of the AAAI Conference on Artificial Intelligence, 2020.
[27] Spooren, Vissers, Janssen, W. Joosen, and I.. Desmet. Premadoma: An operational solution for DNS registries to prevent malicious domain registrations. In Proceedings of the 35th Annual Computer Security Applications Conference, 2019.
[28] C. Szegedy, W. Zaremba, I. Sutskever, J. Bruna, D. Erhan, I. Goodfellow, and R. Fergus. Intrigu- ing properties of neural networks. In International Conference on Learning Representations. 2014.
[29] J. Törnblom and S. Nadjm-Tehrani. Formal verification of input-output mappings of tree ensembles. Science of Computer Programming, 2020.
[30] M. Vinzent, M. Steinmetz, and Hoffmann. Neural network action policy verification via predicate abstraction. In Proceedings of the International Conference on Automated Planning and Scheduling, 2022.
[31] M. Vinzent, S. Sharma, and Hoffmann. Neural policy safety verification via predicate abstraction: CEGAR. In Proceedings of the AAAI Conference Artificial Intelligence, 2023.
[32] D. Vos and S. Verwer. Efficient training of robust decision trees against adversarial examples. In Proceedings of the 38th International Conference on Machine Learning, 2021.
[33] D. Vos and S. Verwer. Robust optimal classification trees against adversarial examples. In Proceedings of the AAAI Conference on Artificial Intelligence, 2022.
[34] D. Vos and Verwer. Adversarially robust decision relabeling. In Machine Learning and Knowledge Discovery in Databases. ECML PKDD 2022., 2022.
[35] Y. Wang. H. Zhang, H. Chen, D. Boning, and C.-J. Hsieh. On Ip-norm robustness of ensemble decision stumps and trees. Proceedings of the 37th International Conference on Machine Learning, 2020.
[36] C. Zhang, H. Zhang, and C.-J. Hsieh. An efficient adversarial attack for tree ensembles. In Advances in Neural Information Processing Systems, 2020.
12

---

A Analysis of the Problem Setting
Adversarial examples are often generated for tasks like computing adversarial accuracy [2], com- puting empirical robustness [IO], and performing model hardening [23] The effect of using the approximation proposed in this paper differs for each task.
Computing the adversarial accuracy of classifier only requires determining whether an adversarial example z exists within the given for each provided normal example x. Because the mixed strategy reverts to the original complete search when the pruned approach returns UNSAT', as stated in Theorem 3.2 it is guaranteed to find an adversarial example if it exists, Hence, the mixed strategy can speed up computing the adversarial accuracy without affecting its value.
Computing the empirical robustness of classifier requires finding the nearest adversarial example i for each normal example x. Because the prumed approach does not consider all features and the mixed approach may not, they may return an adversarial example that is further away than the full search space was considered. Hence, when using an exact attack like kanichelian, the empirical robustness computed using the mixed strategy an overestimate of the true empirical robustness. We show this and we study what happens with approximate method in Appendix B
In model hardening, a large number of adversarial examples are generated and added the training data [23]. The prumed approach can be used to generate a lot more adversarial examples in fixed amount of time.
B Employed Datasets, Models and Attacks
We expand the discussion on Table which reports the characteristics of the employed datasets and models. In our experiments, we use ten high-dimensional datasets where the number of dimensions is greater than 25. We verified that our approach does not bring consistent run time improvements for datasets with less than 25 features, or with fully categorical domain (where the Is norm loses meaning).
Table D also reports the hyperparameters of the learned ensembles, which are tuned through grid search. For all model types, we choose the number of trees in {10, 20, 50J. Max depth is chosen in the range [3.6 6] for XGBoost, and in {5, 7, 10) for random forest and GROOT forest (which typically need deeper trees to work better). XGBoost learning rate is chosen among 10.1, 0.5, 0.9}. GROOT forest is chosen among (0.01, 0.05, 0.1, 0.3, 0.5). and we select the model with the largest e such that GROOT forest accuracy does not drop below 90% of the corresponding RF accuracy. Note that in GROOT a bigger e corresponds to more robust model, hence accuracy drops up to a point where the model can become useless in practice.
When running kantchelian on random forests and GROOT forests, we had limit the number of estimators to 25 due to the extremely long run times.
While the model sizes are smaller, these ensembles are already challenging for the full settings of kantchelian and veritas. This is also highlighted in Q2 from Section 4 where we empirically study the effect of inereasing the ensemble size performance. Those results show that the full procedures becomes increasingly slower as the ensemble complexity grows, and our method offers larger wins.
Table 3 gives specific reference to each of the considered datasets.
B.1 Comparison with LT Attack
We evaluate our two methods representative set of scenarios, varying the model type (XGBoost, random forest, GROOT forest), and the evasion attack variant (one exact (kantchelian) and one approximate (veritas)). Given the fact that (I) it is reasonable to expect that most evasion attacks will benefit from smaller pruned models, and (2) we see improvement across all these settings, we are confident that run time improvements also translate other evasion attack methods.
In practice, other approximate attacks alternative to veritas exist. To the best of our knowledge, no alternative outperforms veritas run times. Computationally, we have compared veritas to another popular oftte-of-the-art the-art method: LT-attack (36.. On the full setting, they have the same success rate and veritas is 25 to 60 times faster, shown in Table 4 for XGBoost ensembles.
13

---

Table 3: References to all the ten datasets used in the experiments.
Dataset
link
covtype
https: //ww: openml wwwpopeewo....o...ooo.eee
finnist
http8: www. wwp.e/// 0Tg/d/40996
higgs
httpa: //ww://wwwww.// www.:/pwwppp.......mm wwwpppew.................
org/d/42769
miniboone
httpa: /twp: openml org/d/44128
mnist
attps: /twp:://www... openm1 wtwpppeww..............e..
prostate
https://wwwz wwtp://mwwwwoomm.....mmm openmm.emmmmmmmmmmmm............ .rg/d/456/2
roadsafety
sttps://www.c http://wwwoppem.... httpelloog//////////
sensorless
attps://archive. ics. wwt.suucieeuuuu..
vehicle
wehspam
attpa://ww.ccst wtt.//wwww.ii....ooo www.::cee.eenu.u....ee........
Table Average run times for generating 100000 adversarial examples using L.T-attack and veritas in the full search setting.
miist
prostate
roadsafety
sensorless
LT
48m
10.5m
5. 5.0m
7.1m
veritas
0.8m
0.2m
0.2m
0.2m
C Expanded Experimental Results
Tables (kantchelian) and 6 (veritas) report the average times and speedups when attempting to generate 10000 adversarial examples in each of our experimental scenarios. The averages are computed over five folds. There is one table for each combination of attack (kantchelian, veritas) and ensemble type (XGB, random forest, GROOT forest). For each dataset, we also report the average size of the relevant feature subset Fs,, the percent of searches in the mixed setting that require making a call to the full search, the false negative rate (proportion of times that pruned returns UNSAT but full returns SAT),, the pruned setting success rate (i.e., adversarial example can be generated with the full search, and the pruned setting finds a valid adversarial example), and the percent of examples that were skipped due the full search reaching the global timeout of six hours. The pruned and mixed settings never reach the global timeout. Note that the mixed setting has attack success rate of 100% by definition.
Figures 7 (kantchelian) and (veritas) show the number of executed searches as a function time for kantchelian and veritas all ten datasets. Each plot contains the results for XGB (top). RF (middle) and GROOT forest (bottom). Hence these plots show the complete set results from Figure the main paper.
C.1 Run Time Standard Deviation and Timeouts
Tables (kantchelian) and (veritas) extend the time results of the presented experiments by additionally reporting standard deviations.
Tables 7 (kantchelian) and R (veritas) also show the percentage of searches that timed out for each dataset, ensemble type and method. In short, XGBoost ensembles are on average easier to verify, and the searches almost never time out. On the other hand, random forests and GROOT forests are more challenging. can happen that with a strict timeout, the prumed setting not able find a solution, as the task remains complex even working with reduced feature set. In those cases, pruned ends with TIMEOUT and mixed will have to execute the full search.
C.2 Tradeoff FNR vs Speedup
We further extend Figure from Q3 in Section 4 which explicitly shows the relationship between the empirical false negative rate and the speedup of the pruned setting.
14

---

Table 5: Average run times (and speedups) when attempting to generate 10 (00 adversarial examples using kantchelian
XGiBosst/rndom forest/GROOT forest ensemble for all three approaches: full, pruned and mixed. We also report the average size of the relevant feature subset, the number of calls to the full setting during mixed number of UNSAT number of TIMEOUT for pruned), the number of false negatives (pruned returns UNSAT' but full returns SAT'), the pruned attack success rate (i.e., pruned succeeds generating an adversarial example if an example can be generated for the full ensemble), and the percent of examples that were skipped due to the full search reaching the global timeout of six hours. Experiments that exceeded the timeout are starred. The pruned and mixed settings never reach the global timeout.
Kantchellan, XGBoost
full
primed
mised
% rol. feats
% full calls
false neg.
% pruned attack rate
% full skip
covtype
2.1x
fmnist
1.5h
18.5m
4.9x
22.9m
3.9x
14.6%
3.9%
3.9%
96. 1%
%
biges
47.7m
4.1x
1.8h
1.8x
18.
20. 20.0%
9.8%
80.4%
%
miniboone
6.0h
55.5m
9.0x
2.8h
3.4X
33.2%
9.2%
4.3%
91.7%
43.1%
mnist
23.9m
3.4m
6.9x
4.7m
5.1x
8.8%
4.0%
4.0%
96.
%
prostate
12.8m
3.8m
2.8x
93.3%
roadsafety
10.7mm
3.6m
3.0x
5.4m
2.0X
23.1%
12.9%
12.7%
87.2%
%
sensorless
14.4m
vehicle
2.5h
25.7m
5.9x
44.2m
3.4x
27.4%
12.2%
12.2% 2%
87.8%
%
webspam
21.2m
4.3m
5.7x
6.6m
3.7x
7.2%
8.7%
8.7%
91.3%
Kantchelian, RF
full
praned
mixed
% rel. fents
% full calls
% false
% prined attack success rute
% full skip
cuvtype
25. 7m
2.3m
11.0x
6.9m
3.7
5.6%
11.0%
8.5%
91.3%
%
fmnist
7.2m
13.0m
biges
5.1h
1.7h
3.0x
3.6h
1.4x
30.0%
27.0%
7.1%
73. 0%
0 %
miniboone
6.0h*
52 0m
9.1x
1.9h
5.2x
32
5.3%
2.1%
95.3%
56.1%
mnist
36.6m
6.4m
5.7x
7.6m
4.8%
10.5%
2.4%
2.4%
97.6%
%
prostate
6.0h*
56.4m
11.8%
2.5h
5.2x
11.4%
13.9%
4.2%
88.3%
64.2%
radssfety
45.2m
8.4m
5.4x
19.7m
2.3x
27.
14.8%
13.5%
86.3%
%
sensueless
52.5m
9.2m
5.7x
14.8m
3.6x
32.6%
10.9%
10.9%
89.1%
0 %
vehicle
39.3m
2.0%
webspam
1.5h
12.4m
7.3x
15.9m
5.7x
10.2%
2.0%
2.0%
97.
%
Kanlchelian, GROOT
full
pruned
mixed
full
false neg.
prined success rate
full skip
covtype
8.
1.9m
4.3x
2.4m
3.4x
6.2%
3.8%
3.5%
96.5%
%
fmnist
3.1h
15.6m
11.7x
21.1m
8.6x
5.3%
2.7%
2.
97. 1.3%%
%
higgs
6.04
2.0h
4.6h
41.1%
miniboone
2.0h
17 17.8m
6.8x
20.9m
5.8%
20.7%
<1
<1 %
99.0%
%
mnist
30.0m
5.5m
9.2x
16.3m
3.1x
5.4%
13.3%
13.3%
86.7%
prostate
6.0h
1.2h
10.3x
2.8h
4.5%
11.4%
14.7%
5.0%
86.5%
61.7%
madsafety
6.7m
1.5m
4.4x
4.2m
1.6%
35.45
34.3%
15.2%
81.3%
sensorless
55.6m
8.6m
12.7m
4.4x
13.2%
10.9%
10.0%
89.4%
%
vehicle
2.7h
29.75 7m
5.5x
53.8m
3.0X
23.3%
9.0%
8.9%
91.0%
%
webspun
24.1m
15

---

Table 6: Average run times (and speedups) when attempting generate 10 000 adversarial examples using veritas on an XGBoost/random forest/GROOT forest ensemble for all three approaches: fill, pruned and mixed. We also report the average size of the relevant feature subset, the number calls to the full setting during mixed (= number of UNSAT + number of TIMEOUT for prumed), the number of false negatives (pruned returns UNSAT' but full returns SAT'), the pruned attack success rate (i.e., pruned succeeds in generating adversarial example if an example can be generated for the full ensemble), and the percent of examples that were skipped due the full search reaching the global timeout of six hours. Experiments that exceeded the timeout are starred. The pruned and mixed settings never reach the global timeout.
Veritas, XGBoost
full
proned
mised
% rel. feats
% full calls
% false % pruned attack success rute
% full skip
covtype
5.3ss
3.1s
1.7%
3.8s
1.4x
5.9%
12. 12%
11.7%
88. 3%
%
fmnisst
3.8%
3.7%
biges
20.4s
7.1s
2.9x
8.6s
2.4x
20.0%
3.4%
2.9%
97-1%
%
miniboone
1.2m
8.5e
8.4x
12.0s
5.9x
14.8%
4.0%
3.8%
96.2%
%
mnist
47.9k
19.0s
2.5x
22.4s
2.1x
5.2%
7.5%
7.5%
92.5%
%
prostate
9.98
3.9s
2.5x
4.48
2.2x
11.2%
7.1%
6.1%
93 8%
%
roadsafety
sensueless
12.1s
4.28
2.9x
6.6s
1.8X
17.5%
15.
14.7%
85.29
0
vehicle
15.6x
10.0m
webspam
18.8a
7.3s
2.6x
9.0s
2.1X
5.3%
10.2%
10.2%
89.8%
%
Veritas, RF
full
prined
mixed
neg.
% pruned attack success rate
% skip
covtype
45.0s
7.5s
6.0x
15.4s
2.9x
5.9%
5.7%
4.4%
95.5%
%
fmiist
6.6m
1.8m
3.6
2.2m
3.0x
10.7%
10.9%
7.4%
89.
0 %
higes
21.4x
16.8m
31.3%
8.8%
miniboone
12.9m
1.1m
11.8x
2.0m
6.4x
19.2%
6.0%
4.8%
94.2% 2%
%
mnist
3.3m
1.1m
3.2%
1.2m
2.9x
10.3%
4.8%
3.5%
95. 95.2%
%
prostate
23.7mm
1.4m
16.9x
9.3m
2.6%
13.1%
11.5%
10.0%
89.19
%
madsafety
40.6m
1.2m
33.5x
13.0m
3.1x
18.8%
11.6%
11.19
88.9%
%
sensorless
4.1m
52.3s
4.7x
21.2%
12.1%
11.2%
87.9%
%
vehicle
42.8m
4.7m
9.1x
38.9m
1.1x
23.0%
32.8%
17.1%
67.3%
webspam
12.9m
3.3m
10.6m
1.2x
10.0%
13.9%
2.8%
86.2%
Veritas, GROOT
fidl
prined
mixed
% rel. Feats
% tull calls
% false neg.
% promed atlack
% full skip
covtype
15.9s
5.8s
2.8%
7.7s
2.
5.6%
4, 4.7%
4.4%
95.6%
%
fmnist
32.2m
63.6
36.2x
1.6m
20.5x
5.5%
2.1%
..%%
97.9%
%
higgs
1.1h
11 11.6m
21.8x
31.5m
8.1x
21.7%
7.9%
3.8% 8.8%
90.8%
16. 61%
miniboone
25.8x
9.7s
97.4%
mnist
3.1m
1.8m
1.7x
2.5m
1.2%
6.2%
11.8%
7.7%
88. 2%
%
prostate
33.9m
4.2m
8.1x
15.7m
2.2x
12.5%
19.7%
7.3%
80.4%
%
madsafety
1.0m
11.4s
5.5x
48.6k
1.3%
39.4%
18.7%
16.4%
83.2%
%
sensorless
3.4m
8.6s
23.8x
1.9m
1.8x
10.0%
11.5%
11.1%
88.8%
vehicle
4..0h
29.6x
2,0x
20.9%
9.7%
79.
1.4%
webspam
9.5m
2.2m
4.3x
4.6m
2.1X
9.0%
14.8%
8.2%
85.25
%
16

---

Kantchelian XGB
covtype
limist
biggs
miniboone
minist
# scarches
Time
0
5m
10m
1h
2h
2.5h
5b
10m
20m
prostate
roadsafety
seusorless
vehiclo
webspam
10k
searches
Tull'
prumed
mixed
Time
5m
10m
5m
20m
2h
10m
Kantchelian RF
covtype
higgs
10k
searches
Time
20m
25m
50m
2.5h
2.5h
20m
prostate
roadsafety
sensorless
velicle
webspam
10k
# searches
Tull
5k
pruned
mixed
Time
2.5h
5h
20m
40m
25m
50m
2h
1h
Kanfchelian GROOT
covtype
fmnist
higes
miniboonc
mnist
scarchass
Time
0
5m
2h
2.5h
5b
2h
20k
40m
prostate
roadsafitt
vehicle
webssaan
10k
searches
fill
pruned
mixed
Time
2h
Figure 7: Run times to attempt to generate adversarial examples for 10000 test examples with the three presented settings (fill, pruned and mixed), using kantchelian on XGBoost/random forest/GROOT forest ensemble, averaged over 5 folds.
In Figure 9 we show the empirical FNR on the x-axis versus the speedup of the pruned approach on the y-axis, using an XGB ensemble on four selected datasets. The empirical FNR is the fraction of times the pruned approach returns UNSAT but the full approach returns SAT. Going from left to
17

---

Veritas XGB
covtype
Imniss
higgs
miniboone
minist
# seurches
Time
0
2.5s
56
20s
40s
0
10s
20s
1m
20s
408
prostate
roadsafety
scusorless
vehiclo
webspam
10k
searches
full
prumed
mixed
Time
56
20m
10s
20s
Veritas RF
covtype
higgs
10k
searches
Time
20s
40s
2m
prostate
roadsafety
sensorless
velicle
webspam
10k
# searches
Full
pruned
mixed
Time
10tn
20m
0.5h
5m
0.5h
1h
10m
Veritas GROOT
covtype
fmnist
higes
miniboone
mnist
scarchas
Time
0
10s
20m
40m
0
2.5h
5b
5m
10m
0
2m
4m
prostate
roadsaliety
websspan
10k
searches
full
pruned
mixed
Time
20m
2.5h
Figure 8: Run times to attempt to generate adversarial examples for 10000 test examples with the three presented settings (fill, pruned and mixed), using veritas XGBoost/random forest/GROOT forest ensemble, averaged over 5 folds.
right along the x-axis, higher values of the FNR correspond to smaller subsets of selected features, hence more aggressive pruning. Using less features, the pruned search becomes faster, at the cost of more false negatives.
18

---

Table 7: Average run times (with standard deviations) when attempting to generate 10 000 adversarial examples using kantchelian on an XGBoost/random forest/GROOT forest ensemble for all three approaches: full, pruned and mixed. The average fraction of timeouts incurred during the search is also reported.
Kantchelian, XGBoest
timcouts
full
prumed
full
pruned
mixed
covtype
9.9m + .e
3.0m = 12.3a
4.7m
8.4g
0%
0%
0%
fmmist
1.5h
18.5m 11.4m
22.9m
biggs
3.3h 1. 3.3m
47.7m 1: 32.6m
1.8h
42.7tm
0%
9.6%
0%
miniboone
55.5m 24.2m
2.8h
52.3m
<1%
muist
23.9m 1: 1.3mm
3.4m 52.1s
4.7m 24.1s
0%
0%
0%
prostate
12.8m +: 14.3s
3.8m 1: 20.5s
4.6mm 11.0s
0%
0%
0%
roassfety
10.7m 28.2s
3.6m 40.99
5.4m 35.3a
0%
0%
0%
sensorless
29.8m 9..8m::2.88m
12.8m 58.0s
14.4m + 1.2m
<1%
0%
0%
vehicle
wehspam
24.2m 4: 1.7m
4.3m d: 2.1m
6.6m 35.4s
0%
0%
0%
Kantchelian, RF
full
primed
mixed
full
pruned
mixed
covtype
25.7m 6.2m
2.3un = 29.0s
6.9m = 1.9m
0%
0%
0%
56.2m
4.
13.0m
1.2m
higas
5.1h 27.5m
1.7h = 12.6m
3.6h 42.7m
0%
19.7%
0%
miniboone
6.0h 2.86
52.0m 4.8mm
1.9h 26.7au
0%
36.6m 1.8m
6.4tn :: 22.6s
7.6m 22.7s
0%
0%
prostate
6.0h 2.0s
56.4m +: 1.6m
2.5h 4.6m
<1%
<1%
0%
roadsafery
45.2m
2.6m
8.4m 3.2m
19.7m
2.2m
sensorleas
52.5m -: 2.7m
9.2m = 1.2m
14.8m = 1.0m
0%
0%
0%
vehicle
3.8h 2.5m
31.8m 12.4m
11.2m
webspam
5.0m
12.4m = 1.4m
15.9m 1.6m
0%
0%
0%
Kantchellan, GROOT
full
pruned
mixed
full
pruned
mixed
covtype
8.1 d: 50.7s
1.9tu 1: 27.2s
2.4mn 26.5s
0%
0%
0%
finnist
21.4m 3.0m
0%
biges
6.0h +: 0.9s
2.0h + 12.0m
4.6h #: 1.2h
0%
18.9%
0%
miniboone
2.0h 44.7m
17.8m + 2.6m
20.9m 1.2m
0%
0%
0%
muist
50.0mn 4: 2.2m
5.5m 1: 3.78
16.3m 2.5m
0%
0%
0%
prostate
6.0h 0.99
1.2h :: 10.5m
2.8h
0%
<1%
0%
roadsafety
6.7mm
1.5mu
4.2m 4:2m:::5200
sensorless
55.6mm 2.88.
8.6mm 1. 6.0m
12.7m 1.9m
0%
0%
0%
3.5mm
<1%
webspam
1.8h
18.6m 1.4m
24. 1.6m
0%
0%
0%
There are cases where false negatives are less problematic, such when one simply needs to generate a lot of adversarial examples for model hardening (23] In these cases, the pruned approach really excels offering run time improvements.
Note that for the considered datasets, FNR values higher than 25% are rare and only occur for very small subsets of features (e.g., 5 out of the 784 features mnist).
D Sensitivity Analysis
We briefly discuss how sensitive our algorithm is to the choice of its hyperparameters, namely the threshold and confidence for the statistical test in the feature selection process (see 3.2) and the timeout for the pruned setting.
19

---

Table 8: Average run times (with standard deviations) when attempting to generate 000 adver- sarial examples using veritas on an XGBoost/random forest/GROOT forest ensemble for all three approaches: full, pruned and mixed. The average fraction of timeouts incurred during the search is also reported.
Veritas, XGBoost
times
% timeouts
full
proned
mixxed
full
praned
mixed
covtype
5.3e 0.16
3.1e 0.2s
3.8a 0.2s
0%
0%
0%
limmist
43.6s 1.1s
31.98 +: 5.4s
33.6s 1: 3.0s
0%
<1%
0%
higgs
20.4s :: 0.3s
7.1s 0.1s
8.6s 0.4s
0%
0%
0%
miniboone
1.2m 8.0s
8.5s + 2.46
12.0s +: 2.5s
0%
0%
0%
mnist
47.96 1: 1.7s
19:08 1. 0.6es
22.4s 1. 1.1s
0%
0%
0%
prostate
3.96
4.4s 0.0ss
0%
0%
roadsafety
11.4a 2.76
4.2s 0.16
5.4a 0.5s
0%
0%
0%
sensorless
12.18 1.16
4.2g 0.88
6.6s 0.5g
0%
USE
0%
vehicle
19.4m
7.3m
1,2m d. 40.5s
10.0m 1: 4.2m
<1%
<1%
<1%
wehsqum
18.8s - 0.8s
7.36 = 0.6ss
9.0s 0.3s
0%
0%
0%
Veritas, RF
times
% timesuts
prumed
mixed
full
prined
covtypo
45.0s 5.5a
1.5c = 0.3s
15.4s + 2.8s
0%
finnist
6.6m 1.2m
1.8m 19.3s
2.2m + 19.0s
<1%
3.4%
<1%
biggs
41.8m +: 32.7m
2.0m = 1.1m
16.8m + 12.2m
<1%
1.1%
<1%
miniboone
1.6m
38.2s
2.0m 1.0m
mnist
3.3mm 9.5s
1.1m 5.76
1.2m 1: 5.8s
0%
1.3%
0%
prostate
23.7m
- 28.2s
9.3m +
madssfoty
40.6m = 14.7m
1,2m 28.18
13.0m = 5.6m
<1%
0%
0%
sensorless
4.1m 1.9m
$2.3e 19.11
2.8m + 1.7m
0%
<1%
0%
vehicle
42.8m 18.9m
4.7m = 1.6m
38.9m + 19.7m
<1%
15.6%
<1%
webspam
12.9m 2.5mm
3.3m = 27.48
10.6m + 2.1m
<1%
11.0%
<1%
Veritas, GROOT
times
% timesuts
Jull
promed
mixed
full
pruned
coviype
15.9% 1.4s
5.8s 1: 0,2s
7.7s 1: 1.9s
0%
0%
fmniist
32.2m
8.4m
53.46 +: 4.4s
1.6m 23.2s
<1%
<1%
<1%
biggs
4.1h 1.7h
11.6m + 8.7m
31.5m 13.0m
1.1%
4.0%
<1%
miniboone
3.7m
2.98
6.38
mnist
3.1m 59.0s
1.8m +: 25.46
2.5m = 54,8a
<1%
4.1%
<1%
prostate
33.9m
4.2m +: 36.4a
15.7m 1.2m
<1%
12.3%
<1%
roudsafety
1.0m 16.88
11.46 2.1s
48.6s 18.5s
0%
0%
0%
sensorless
3.4m 1.22m
8.66 3.66
1.9m 1: 2.7m
<1%
0%
vehicle
4.0
8.2m 3.7mm
2.1h 50.4m
1.2%
10.7%
<1%
webspam
9.5
2.2m = 1.1m
4.6m = 1.3m
<1%
6.6%
<1%
D.1 Sensitivity to Statistical Test Parameters
The statistical test described in 3.2 takes as hyperparameters the acceptable false negative rate 7 and the confidence - We perform sensitivity analysis where we vary E [0.05, 0.1, 0.25, 0.5) and 1 17 E [0.8, 0.9, 0.95) the miniboone dataset.
Table [ shows the mixed speedup for (veritas, XGBoost) for all combinations of the considered approach improves upon the run time of always running a full search (i.c., speedup is always > 1). When T = 0.05, many features are selected and hence there is less pruning. 0.1 and T = 0.25 perform identically. When the value of 1 y impacts the selected feature set. A confidence of 0.95 keeps the same feature set of smaller feature set, which
values for (FNR) and 7) (confidence). For all settings,
0.5.
0.1 and 0.25. However, lower confidence results in degrades the performance of the mixed setting because there are more calls to the full search.
Hence more in general, the threshold on the false negative rate is inversely proportional to the number of chosen features: the larger the selected feature subset, the lower the FNR will be. This is in tension with the goal of using small of feature subset as possible, to speed up the praned
20

---

Kantchellan
prostate
roadsafety
sensorless
10x
Pruned
Speedup
OX
0.0
0.2
0.0
0.2
0.0
0.2
0.0
0.2
Emp. FNR
Veritas
4x
Speedup
OX
0.0
0.2
0.0
0.2
0.0
0.2
0.0
0.2
Emp.
Figure 9: Speedups introduced by the pruned setting when attempting to generate 10000 test examples using kantchelian (top) and veritas (bottom) on an XGB ensemble, varying the empirical false negative rate. Higher FNRs correspond to smaller feature subsets. The dotted horizontal line corresponds to a speedup of 1x, i.c., same run time of the full setting.
setting. Moreover, a larger confidence 1 y can increase the number of selected features it shrinks the confidence interval for the empirical FNR.
Table 9: Speedup of the mixed setting when attempting generate 10000 adversarial examples for miniboone using (veritas, XGBoost), for different values of r (threshold on the allowed false negative rate) and 77 (confidence of the statistical test).
1)
mixed speedup
0.8
3.7x
0.05
0.9
3.7x
0.95
3.7x
0.8
6,3x
0.10
6.3x
0.95
6.3x
0.8
6.3x
0.25
0.9
6,3x
0.95
6.3x
0.8
1.9x
0.50
0.9
1.9x
0.95
6.3x
D.2 Sensitivity to Timeouts
Timeouts always need to be explicitly handled, due to the hardness of the evasion problem 23 While Tables and show that in most of our experiments timeouts are rare or totally absent, to complete the discussion we perform sensitivity analysis the value used for the pruned setting timeout. We vary sprun E [0.001, 0.01, 0.1, 1] seconds when attempting to generate 000 adversarial examples on the fmnist dataset. We only consider veritas for RF in this experiment.
Table TO shows the fraction of timeouts for the pruned setting as well as the pruned speedup and the mixed speedup for each value of max The smaller max the larger the number pruned timeouts,
21

---

which corresponds to faster (but less accurate) prumed search. If the timeout value is too low, this adversely affects mixed search because leads more calls the full procedure. Conversely, foxx is too large, the search becomes slower as the praned setting starts losing time on few slow instances.
Thus the ideal maa lays in between the two extremes. In the presented case, max = 0.01 works best. The best choice likely depends on the specific dataset, model, and attack type. However, tuning its value is time consuming (i.e., negates the benefits of the proposed approach).
Table 10: Fraction of pruned timeouts and speedup of the pruned and mixed settings when attempting to generate 10000 adversarial examples for finnist using (veritas, random forest), for different values of the pruned setting timeout iaxx (in seconds).
ppren (8)
% prumed timeouts
pruned speedup
mixed speedup
0.001
24%
7.9x
2.8x
0.01
12%
5.8x
3.2x
0.1
4%
2.8x
2.3x
1
1 1
1.1x
1.1x
E Quality of Generated Adversarial Examples
We extend Figure by further discussing the quality of generated adversarial examples, providing more examples, and looking in detail at their distance with respect to the base examples.
Figure 10 shows a large set of adversarial examples generated for mnist digits using kantchelian and veritas on an XGBoost ensemble. For each attack, we plot the base example x and the two adversarial examples generated with full and the pruned setting.
E.1 Empirical Robustness
Tables 11 (kantchelian) and 12 (veritas) show the average empirical robustness in all the performed experiments for the full, pruned and mixed settings. An ensemble's empirical robustness is defined as the average distance to the nearest adversarial example for each in test We use adversarial examples generated with the experiments presented in Q1 in Section 4 (and Appendix
The objective of the kantchelian attack is to find the closest adversarial example. Given that the method is exact, the full setting returns the optimal solution. The pruned search works with a restricted feature set, thus it might not be able to find the closest adversarial example, if that requires altering features not included in the selected feature subset. As a consequence, the empirical robustness values for the pruned and mixed search are overestimates of the true value given by the full setting.
Unlike kantchelian, veritas does not try to find the closest adversarial example. Instead, it maximizes the confidence that the ensemble assigns to the incorrect label. In this case, there is little difference in the empirical robustness values among all considered settings, with the pruned and mixed settings typically managing to even lower the distance to the base example.
E.2
Change in Predicted Probability for Adversarial Examples
veritas tries generate an adversarial example such that the ensemble assigns high a probability as possible to the incorrect label. Hence, a natural empirical measure for the quality of the generated examples compare the difference the ensembles probabilistic predictions for the adversarial examples generated by each approach. Namely, we compute T(ū)- T(ī') where 7 is generated by the full search, E' is generated by the pruned (mixed) search, and (in an abuse of notation) T T(x) returns the probability an example belongs to most likely class.
Table 13 shows the average differences in predicted probability between full and prunedlmixed adversarial examples.
Using kantchelian, adversarial examples generated with our approaches are assigned very similar probabilities to those generated with the full search. In veritas, differences are typically higher, as the model output is directly optimized.
22

---

Table 11: Average empirical robustness (i.e., distance to the closest adversarial example) for the full, mixed and pruned methods using kantchelian attack on XGBoost/random forest/GROOT forest ensembles.
Kantchelian, XGBoost
full
prined
mixed
euvtype
0.018 +:
0,038 4: 0.0
0,038 1: 0.0
frnnist
0.034 1:44411000 0.002
0.002
0.056 0.012
0,056 1: 0.012
higes
0.011 +.0
0.015
0.016 0.002
miniboone
0.001 0.0
0.001 +00
0.001 +
mnist
0.006
0,021 0.007
0.007
prosiate
0.02
0.037 0.001
0,038 1: 0.001
mansafety
0.015 0.004
sensorless
0.006 0.0001
0,008 1 0.001
0.009 1 0.0
vehicle
0.001
0.045 0.013
0.042 +: 0.011
webspam
0.0
0
0.006 0.002
Kantchelian, RF
fall
pruned
mixed
covtype
0,102 1: 0.003
0,113 1: 0.002
0,117 1: 0.001
frniist
0.002
0.045 0.016
biges
0.016
0.006
0.019 0.0
mimboone
0.001
0,001 0.0
0,001 + 0.0
mnist
0.000
0.003
0.023 0.002
prostate
0.058 0.0
0.0
0,094 +
ruadsafety
0.022
1:
sensorless
0.017 0.002
0.032 0.001
0,032 1: 0.001
0.001
0.033 0.006
webspam
0,003
0.006 -:
0.006 0.001
Kantchelian, GROOT
full
prined
inixed
cnvtype
0.136
0.1 +: 0.002
0,295
0,309
higes
0.109-1...08
0.015
0.127 1: 0.01
miniboone
0.0
0.014
0.048 + 0.014
mnist
0.207
0.296
0.298 0.0
prostate
0.063
0,091
0.000
0.096 1: 0.003
madsafety
0.002
0.011
0,092 1: 0.007
sensorless
0.051 0.003
0.003
0.079 0.013
1:
webspam
0.004
0.052
0.052 -: 0.002
F Expanded Related Work
Adversarial examples have been theoretically studied and defined in multiple different ways [4] More specifically, Ilyas al. showed how certain features in dataset might be fragile and thus naturally lead to adversarial examples [21]. Approaches to reason about learned tree ensembles have received substantial interest in recent years. These include algorithms for performing evasion attacks [23 [5] (i.c., generate adversarial examples), perform robustness checking [8], and verify that the ensembles satisfy certain criteria [1I [0] 26 29). Kantchelian et al. 23 were the first to show that, just like neural networks, tree ensembles are susceptible to evasion attacks. Their MILP formulation is still the most frequently used method to check robustness and generate adversarial examples. Other notable methods for adversarial example generation are SMT- -aT-d systems [15] II] These approaches propose varying ways to encode tree ensemble in set of logical formulas using the primitives from Satisfiability Modulo Theories (SMT). While the formulation of an ensemble in SMT is very elegant, it tends to perform worse than MIIP in practice.
Because MILP and SMT are exact approaches cases can be difficult (i.e., time consuming) to find. Often an approximate answer will be sufficient and several approximate methods have been proposed that are specifically tailored to tree ensembles. Chen et al. proposed K -ppatitee graph representation in which a max-clique corresponds specific output of the ensemble [8] 35). They introduced a fast method to approximately evaluate robustness,
T they search for the optimal answer which in certain
'MILP is technically anytime, but the approximate solutions are not useful in practice for this problem setting, [10]
23

---

Table 12: Average empirical robustness (i.e., distance to the closest adversarial example) for the full, mixed and pruned methods using veritas attack on XGBoost/random forest/GROOT forest ensembles.
Veritas,
prined
mixed
covtype
0.094++000
0,088 0.001
0.088 +
fmnist
0,287
0.275
0.276 0.004
higes
0.071 0.0
0.061 0.000
0.061 = 0.003
miniboone
0.003
0.01
0.029
mnist
0.289
0.003
0.257 : 0.013
prostate
mondsnetty
0.057
0.055
0.056
sensorless
0.0
0,049 0.00
vehicle
0.14
0
0.134 - 0.002
webspam
0.0
0.035 0.0001
0.035 = 0.001
Veritas, RF
full
pruned
mixed
covtype
0.272
0.006
1:
finnist
0,293
0.277 0.004
0,278 : 0.004
biges
0.00
0.065 0.002
0.066 0.002
miniboone
0,061 0.0.00
0,038 0.01
0.04 + 0.01
mnist
0.289
1.09-1.0..02
0.275 1: 0.004
0,276 1: 0.004
0.0
0.186
0.188 :: 0.002
nuadsafety
0.11 0.001
0.094 1: 0.006
0,097 1: 0.005
sensorless
vehicle
0,138
0,129 0.004
0.134 = 0.008
webspam
0.058 - 0.0
0.054 + 0.001
0.055 + 0.001
Veritas, GROOT
full
primed
inised
covtype
0.359-10.000
1
0.331 :: 0.006
fmnist
0,394-+0.0
0.002
0,383 0.003
higgs
0.37-4-.002
0.004
miniboone
0.449
0,223
0.233 0.051
mnist
0.3
0.003
0.39 0.003
prostate
0.196:1:0.0
0.001
0.192 1:
madsafety
0.191
0.187:1:0001
0.188 0.001
sensorless
0.189
0.009
0.17 0.007
vehicle
0.3
0.001
0,382 + 0.007
webspam
but it cannot generate concrete adversarial examples. Devos et al. further improved upon this work by proposing a heuristic search procedure in this graph which is capable of finding concrete adversarial examples very effectively [10]. Zhang et al. propose method based greedy discrete search through the space of leaves specifically optimized for fast adversarial example generation [36].
Other work focuses on making tree ensembles more robust. There are multiple approaches: adding generated adversarial examples to the training data (model hardening) (23 modifying the splitting using the framework of optimal decision trees to encode robustness constraints [33], relabeling and pruning the leaves of the trees (34), simplifying the base learner ① and using robust 0/1 loss [1]. Gaining further insights into how evasion attacks target tree ensembles, like those contained this paper, may inspire novel ways to improve the robustness of learners.
procedure 7 32
Another line of work aims at directly training tree ensembles that admit verification in polynomial time [5] [ However, a drawback current approaches is that they result in (large) decreases in predictive performance.
Finally, performing evasion attacks has been studied for other model classes with deep neural networks receiving particular attention 28 17 24 6). However, state-of-the-arr algorithms are tailored to one specific model type they typically exploit specific properties of the model, e.g., the work on tree ensembles often exploits the logical structure of decision tree.
24

---

Table 13: Average difference in predicted probability between adversarial example generated using mentchhllianveritaae with the full setting and an adversarial example generated with the prunedlmixed setting, for the same base example. All adversarial examples are those generated during the experi- ments from Section and Appendix C
Kantchelian
XGBoost
RF
GROOT
praned
mixed
proned
pruned
mixed
covtype
0.093 = 0.001
0.082 = 0.002
0,01 # 0.002
0.009 = 0.002
0.011 + 0.001
0.011 + 0.001
limiist
0.002
higgs
0.012 :1 0.001
0.01 0.001
0.005 0.0
0.003 0.0
0.007 0.000
0.005 1. 0,003
miniboone
0.013 0.001
0.011
0.006 0.0
0.006:0..0
0.005
mmist
0.109 :: 0.011
0.103 0.011
1.000
0.019 0.002
0.018 0.004
0.016 1 0.004
prostate
0.026 - 0.0
0.023 = 0.0
0.004:0.00
0.003 -
0.0
0.003 + 0.0
readsafety
0.135 0.025
0.019
0.002
0.011 0.001
0.033
0.027 = 0.014
sensorless
0.045 = 0.001
0.041 = 0.002
0.008 0.0
0.007 0.0
0.009 0.001
0.008 = 0.001
0.001
wehspam
0.049 0.006
0.044 0.004
0.007 - 0.0
0.006 - 0.0
0.006 0.06::0.00
0.005 + 0.0
Veritas
XGBoott
RF
GROOT
praned
mixed
proned
mixed
pruned
mixed
covtype
0.051 1:
Tmmist
0.228 0.065
0.213 = 0.056
0.373 : 0.011
0.327 0.009
0.379 +: 0.009
0.367 1 0.01
higgs
0.071 =: 0.006
0.067 = 0.005
0.062 1: 0.009
0.054 0.007
0.057 0.01
0.051 1: 0.009
miniboone
0.246 0.042
0.231 0.036
0.178 0.027
0.164
0.002
0.019
mnist
0.196 = 0.026
0.179 = 0.022
0.294 0.012
0.275 0.009
0.241 + 0.022
= 0.021
prostate
0.006
0.169
roadsafety
0.17 -1 D.04
0.146 1 D.031
0.083 1: 0.009
0.071 0.000
0.059 0.000
0.488 1 0.003
sensorless
0.003
0.113 0.012
vehicle
0.21 1231=0.000 0.026
0.175 0.017
0
0.135
0.0274
0.065 0.018
wehspam
0.274 = 0.008
0.244 = 0.009
0.267 0.011
0.226 0.01
0.206
0.231 1 0.016
25

---

x
KAN Full
.VER J. ffull
x "pruned
2
2
2
2
2
4
4
4
4
4
8
8
8
8
8
6
6
6
6
6
9
9
9
9
9
>
7
>
7
>
Figure 10: Adversarial examples generated for mnist with both attacks (kantchelian and veritas) on
an XGBoost ensemble, to show the quality of generated examples.
26

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the
paper's contributions and scope?
Answer: [Yes]
Justification: the abstract and introduction we claim that we can identify subset of relevant features to perform faster repeated evasion attacks by only perturbing those features.
Q1 in Section supports our claim. We provide further evidence Appendix
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: The limitations of the proposed methods are discussed in the paper. In Sections and 3 we clearly state that our approach speeds up adversarial example generation in scenarios where a lot of repeated evasion attacks need to be performed. We discuss the specific scenarios where this the case in Sections 3 and Appendix A At the beginning of Section 4
we also point out that our approach works best on high-dimensional datasets. We summarize these limitations in Section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "I "Limitations" section in their paper.
The paper should point any strong assumptions and how robust the results to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
27

---

3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: Theoretical results are only present in Section 3 which also reports the needed references and proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof's provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: In the paper clearly describe all the adopted tree ensemble types (XGB, RF, GROOT, Section 2). evasion attacks (kantchelian and veritas, Section 2 and datasets (Section aand Appendix B) The method is described in Section with the aid of Algorithms and 2. We then describe our experimental methodology in Section [ Table reports all datasets characteristics, each tuned model's hyperparameters, and the perturbation size ö for each attack. Finally, Table 3 points toward the publicly available sources we gathered the datasets from.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to a hosted model (e.g., in the of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
28

---

(c) If the contribution is new model (e.g.. a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provide full access to the code that implements our method and repro- duces all the experiments from the paper httppp///ggtuubb.co///ooroaaaaae laster-repeated eeeeeattd-evasionn-ne www.etteeeeeeeeeeeeeeeeee ensembles,
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips cc/
muuides/CodeSubmissee
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https Stw.eSdeeeeeoeeeeemeiieee
ssiinnolicyyy for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We perform 5-fold cross validation described in Section Appendix reports the full grid employed to tune all our ensembles through grid search. Plus, it discusses the choice of the employed evasion attacks.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
7. Experiment Statistical Significance
29

---

Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Given that our key performance metric is run time, we always report standard deviations on run times and related metrics (e.g., when we discuss speed ups in Sections ] and Tables 7 and 8 in the supplement report run time standard deviations for all the performed experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by emror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (c.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: The compute worker characteristics and memory are specified in Section 4
Run times are the key performance metric, henee they are thoroughly discussed Section and Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification:
We are aware of the code of ethics and not violate any clause.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
30

---

If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We included an impact statement in Section 6
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., dep.oymeet of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
31

---

Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Only the authors contributed to this paper. The adopted datasets (Table 3) models and attack methods (Section 2) are all publicly available and properly referenced. The license has been selected for submission in OpenReview (CC BY 4.0).
Justification:
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, satiaaetsspppesswiti paperswi thcode. com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The code implementing
method (described in Section 3 as well as all the presented experiments are publicly distributed https://github. com/ ensembles
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
32

---

According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/teview based on the requirements of your country institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
33


Reviews:
[{"review_id": "jMQaUvUVgz", "reviewer": "Reviewer_pRup", "summary": "The main goal of this paper is to show that it is feasible to speed up the generation of adversarial examples against tree ensembles by perturbing only a small subset of the feature space. Their approach expands the current literature by offering an algorithmic alternative that takes advantage of the smaller subset of features instead of generating new examples from scratch. The paper shows empirical evidence from experiments on numerous datasets across different domains to show the speedup in the generation of such adversarial examples. \nThe key to the approach is to use a mixed approach to generating examples, where the algorithm uses the only the subset of features, or pruned setting, and only if it fails to deliver a satisfactory result or times out do they fall back to using the full method, which will find an example if one exists. Naturally, one would ask how to determine such a subset of features, which the authors propose a statistical test to add features that minimize the false negative rate by a given threshold. \nExperimentally, they tested three tree ensembles on 10 datasets that were coerced to binary classification problems. The goal was to see how quickly they could generate 10,000 adversarial examples using their proposed methodology vs the current standard full approach. Evidence suggests that by pruning the ensemble to a subset of features significantly improves the generation of adversarial examples as well as helps scale the solution as tree depth increases when compared to the full approach.", "questions": "Do you have any data on parameter sensitivity? How sensitive is the method to the choice of parameters, such as the threshold for the statistical test and the timeouts?\nHow do different dataset characteristics, such as feature correlation and data sparsity, affect the performance of the proposed method? Are there specific types of datasets where the method performs particularly well or poorly?", "limitations": "There are limitations on the approach’s effectiveness given different dataset characteristics. The approach works better on high-dimensional data, but to what extent? Additionally, the authors could have added some statements of the risks of the use of this approach to create adversarial examples that could enable evasion attacks that could affect common systems. It may be helpful to explain the implications or informed hypotheses if this approach could better harden tree ensemble models and therefore reduce the threat. On another note, a limitation of this approach is the tradeoff for speed over completeness. It isn’t readily apparent to me how robust this method is to simply cherry picking the most vulnerable feature and creating all the examples from minor perturbations in that feature. So, while the generated examples are valid, they could represent a fragile set of examples. \nAdditionally, the datasets used are only for binary classification tasks, is this method appropriate or are the results as significant when given tasks outside binary classification?", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The biggest strength of this paper is that it is clearly written and easy to follow for a reader that has experience in tree-based methods for machine learning. Claims are well supported by experiments and there appears to be no significant roadblocks to reproducibility given the open nature of the datasets and that the authors plan to release code along with paper acceptance. Results are reported in both summary and detailed formats. The flow of the paper is consistent with current norms for papers in this vein of research. \nGiven that computational resources for large scale ML projects are at a premium, results like this can reduce the time to accomplish common tasks such as adversarial example generation are very helpful to practitioners and other researchers. If methods like this are then implemented in common packages, they can be of significant impact to the community writ large.", "weaknesses": "The largest weaknesses in this paper, to me, are around its originality and overall theoretical impact on the field. This is an incremental improvement to adversarial generation that has its theoretical underpinnings in feature selection of trees and tree ensembles. There is significant prior work on feature selection for trees, and although this is a novel implementation of this concept for adversarial example generation speedup, it is not a concept that is particularly novel. The paper's reliance on a statistical test for feature selection introduces an element of sensitivity to parameter choices, such as the threshold for the test and the timeouts for the pruned and full methods. A detailed sensitivity analysis could help in understanding the robustness of the method to these parameter settings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Originality / Impact**\nThe paper's impact and originality lie in the insight that we can efficiently perform evasion attacks by only perturbing a restricted set of features. \nTo our knowledge, there is little work on exploiting the sequential nature of performing evasion attacks, i.e., existing methods solve problems in isolation and do not exploit similarities among problems. This is useful for robustness checking of learned models (e.g., computing adversarial accuracy, cf. cites 1-4-6-8-20-28 from the paper). See also the response to Reviewer SynL for other cases this may be useful. \n\nOne difference with respect to feature selection is that traditionally one selects features prior to training a model, i.e., the model is learned with a reduced feature set. We identify features after the model is learned (perhaps this is more akin to feature importance) and use the found features to simplify the model.  \n\n**Parameter Sensitivity**\n\n**Threshold for statistical tests**\n This would be interesting. In general, the threshold on the FNR $\\tau$ is inversely proportional to the number of chosen features: the larger the selected feature subset, the lower the FNR will be. This is in tension with the goal of using as little of a feature subset as possible, to speed up the *pruned* setting. Moreover, a larger confidence $1-\\eta$ increases the number of selected features as it shrinks the confidence interval for the empirical FNR (see 3.2).\n\nWe ran the sensitivity analysis proposed by the reviewer on a single dataset. The table below shows the *mixed* speed-up for *miniboone* (*veritas*, XGBoost) using different values for $\\tau$ (FNR) and $1-\\eta$ (confidence).\nFor all parameter settings, our approach improves upon the run time compared to always running a full search. For a fixed $\\tau$, varying $1-\\eta$ does not impact the selected features subset or performance.  When $\\tau = 0.05$, many features are selected and hence there is less pruning.  $\\tau=0.1$ and $\\tau=0.25$ perform identically. When $\\tau=0.5$ the feature subset becomes very small, and while the *pruned* setting is extremely fast there are many UNSATs and hence more calls to the *full* search. We will add a more expansive analysis in the Supplement.\n\n| tau vs 1-eta  | 0.8   | 0.9     | 0.95 \n|---------------|-------|---------|------\n| 0.05          | 1.5x  | 1.5x    | 1.5x     \n| 0.1           | 2.6x  | 2.6x    | 2.6x    \n| 0.25          | 2.6x  | 2.6x    | 2.6x    \n| 0.5           | 1.7x  | 1.7x    | 1.7x    \n\n\nOur experiments used a conservative approach and set the false negative rate $\\tau$ below 0.25 with confidence $1-\\eta=0.9$. Empirically, this worked well and we achieve better results than the theory guarantees (average FNR of 7.5\\%, see Q3 in Section 4). \n     \n**Timeouts** \nGiven the hardness of evasion (Kantchelian et al. ICML'16), timeouts always need to be explicitly handled (see lines 75-80).\nThe chosen timeouts of 1 (*kantchelian*) and 0.1 (*veritas*) work for all the adopted datasets. Increasing the timeout parameter will not have a big impact as timeouts are rare as shown in Table 7 in the supplement. Decreasing it will lead to too many calls to the full procedure, negating the benefits of pruning. \n    \n\n**Dataset Characteristics**\n\n**How do feature correlation and data sparsity affect the performance of the proposed method?**\n Given that we select a subset of relevant features, correlation between features is likely unproblematic as redundant features will likely not be selected by the feature selection algorithm. If a certain feature is spare, it will likely be left out from the subset of relevant features, as the signal that the model can pick up will be weaker. \n    \n**Are there specific types of datasets where the method performs particularly well or poorly?**\nThe method generally worked well on the diverse set of datasets made of tabular data of various dimensionality and image data we considered.\nThe approach would not excel when the dataset has low dimensionality (hence it does not make sense to extract a subset of features) or has a fully categorical domain (where the l-infinity norm loses meaning).\n\n**High dimensional datasets: to what extent?**\nWe verified that our approach does not bring consistent run time improvements for datasets with less than 25 features.\nTherefore, we considered all the popular high-dimensional benchmark datasets we could find in related works. Suggestions for extra datasets are always welcome! \n  \n\n**Risk Statement**\nWe will add a clearer risk statement. We will highlight that that while this work does make attacking tree ensembles faster, being able to efficiently perform repeated evasion attacks is a key to understand what attackers can do, and to improve the applicability of robustness checking and hardening techniques, which ultimately mean reducing the threat on deployed models.\n\n\n**Robustness against simply modifying the most vulnerable features?**\nOnly modifying the most vulnerable feature would not work well in general and would indeed produce fragile examples. We identify a subset of relevant features so that on one hand we avoid losing time on \"irrelevant\" features, and on the other hand we still produce diverse enough adversarial examples. We discuss the quality of generated examples in Section D of the Supplement, using two different measures. In general, our method produces valid adversarial examples of sufficient quality (using *veritas*, even better than the *full* setting). \n\n**Tasks beyond binary classification** Most existing approaches to performing evasion attacks on tree ensembles are defined for binary classification, which is why this paper follows the same approach (cites 6-8-20-33). \nHowever, we do not see any reason why our approach should not work even on multi-class and regression problems.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "l9WFAEj7J2", "reviewer": "Reviewer_SynL", "summary": "This paper proposes a new method for a faster generation of adversarial attacks on tree ensembles such as XGBoost and random forest. The proposed approach has two parts: first, a subset of relevant attributes in a tree is identified. This step is inspired by an empirical. observation that on tree ensembles, most of the adversarial examples tend to perturb only a limited subset of features. Once this subset is identified, the tree is pruned accordingly and the adversarial example for this pruned tree is generated. Since generating adversarial examples for a pruned tree would require less computational time, this method could generate an adversarial example faster. Theoretically, it is shown that if an adversarial example for the pruned tree is generated, it is also going to be an adversarial example for the full tree. Experimental results on a few tabular + image data shows that the proposed method could provide around an order of magnitude speed-up in generating an adversarial example.", "questions": "- Can we generate the adversarial example with only a single example?\n\n- A figure that shows the attack success rate (y-axis) vs the number of parallel test examples (x-axis) used for attack generation would probably provide a better insight on this shortcoming.", "limitations": "- I would probably encourage the authors to discuss the above limitation in their paper as well.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper is well-written. It guides the reader well, and provides intuitions about the theoretical aspect of the work.\n\n- The proposed method is simple and easy to implement.\n\n- The experimental results demonstrate considerable speed-up in generating adversarial attacks.", "weaknesses": "- The main weakness of this paper for me is its settings. As it is mentioned in Line 106, the threat model in the paper assumes that we have access to a subset of test examples during attack generation. This assumption plays a crucial role in the proposed method, as only by having a subset of test examples we can determine the attribute subset which is subsequently going to be used for pruning the tree. In most of the adversarial example generation literature, the assumption is that the attacker can attack the model with even a single example. Considering this, it would cast a doubt on the contributions of the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Assume access to a subset of test examples during attack**\nWe specifically look at the case where somebody wants to generate **many** adversarial examples. \nThere are several scenarios where this is the case. In areas like phishing (or fake webshops), attackers need to generate and register many web domains. Registrars are employing automated techniques (see cite 23) to flag suspicious registrations. In this case, the attacker would know what has and has not been approved by a registrar, hence having access to unseen test examples is usually not an issue. This scenario is briefly mentioned in the intro, but we can expand upon it.\n\nMoreover, during model evaluation (i.e. before deployment) all existing methods for robustness checking require generating (or failing to generate) many adversarial examples, i.e., one for each example in a test set.  For example, this is the case for adversarial accuracy (Andriushchenko et al. NeurIPS'19, Calzavara et al. DMKD'20, Vos \\& Verwer ICML'21) and empirical robustness (Kantchelian et al. ICML'16, Chen et al. NeurIPS'19, Devos et al. ICML'21). Hence, in these relevant practical scenarios our approach would provide consistent run time improvements. \n\n**Can we generate the adversarial example with only a single example**\nYes because the method would just fall back to the original search procedure (i.e., Kantchelian or Veritas) on the full ensemble. However, this would not be an interesting use case for our approach and there would be no benefit to using it to just generate one example.\n\n**Figure with \"number of parallel test examples\" vs attacks success rate**\nWe are not sure we correctly interpret the reviewer's suggestion. If the \"number of parallel test examples\" stands for the number of examples used for the feature selection procedure described in 3.2, this number varies at each run depending on the results of the statistical test: as soon as it is guaranteed that the extracted feature subset ensures a low enough FNR, the procedure terminates, as outlined in Algorithm 2. Therefore in some datasets 100 examples are enough, and in some other cases we need up to 500 examples, making it difficult to summarize everything in a single figure. If the reviewer has a specific suggestion on how to do so, we will definitely insert it in the final version of the paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xAkBXCNvHg", "reviewer": "Reviewer_s5LR", "summary": "This paper proposes a new mechanism for performing computationally-efficient adversarial attacks on decision tree ensembles. Specifically, it considers the setting where an attacker wants to attack *many* samples in a dataset at the same time, and considers the *average* time to attack each sample. (The paper focuses specifically on the L_infinity threat model, but could be applied more generally.) \n\nThe proposed method is inspired by the empirical observation that, when attacking various different samples on the same trained model, attacks on decision tree ensembles tend to focus on only a subset of the total space of features, and consistently leave many features un-perturbed for all samples. The key idea is to limit the search space of the attack on later samples to only those features which are likely to be necessary to perturb, based on earlier attacks. This speeds up the attacks on the later samples.\n\nThis paper therefore proposes an algorithm that, after fully attacking only a small number of samples (using a \"base\" attack algorithm that can either be a full-verification MILP solver or a heuristic technique) identifies the features most likely to be involved in an attack; specifically, it ranks all of the features by how often they are perturbed. Then, using several additional small subsets of samples, the algorithm determines, coarsely, the minimum number of features that must be considered in the search space (i.e., the cutoff in the ranking) in order for the attack success rate, perturbing only these features, to be close, with high probability, to the attack success rate when perturbing all features. Finally, the attacker attacks the rest of the samples, only perturbing the identified subset of features.\n\nThe paper considers two attack variants: the \"pruned\" variant which, in the final stage, *only* performs the attack on the subset of features, and the \"mixed\" variant, which, if the attack fails in the specified L_infinity ball when considering only the subset of features, will then \"fall back\" on the full-feature-space search attack.  The \"mixed\" variant is guaranteed to have the same success rate as the full search, so only time comparisons are relevant when evaluating its success. Over a wide variety of standard datasets and decision tree ensemble models, the proposed methods are shown to produce significant speedups in attacks.", "questions": "I have two suggestions for improvements to the algorithm; perhaps you could try these?\n1. It seems odd to use effectively a \"sparse\" (L_0 constrained) adversarial attack when attacking under the the L_infinity threat model. Have you considered randomly perturbing (or perhaps maximally perturbing), within the L_infinity ball, all of the \"other\" features, that are not part of the identified sensitive-feature subset? This may give a somewhat-higher access rate on some classifiers, to the extent that the classifier is sensitive to random noise, without significantly increasing attack time.\n2. In the \"mixed\" setting defined in the paper, the entire objective of feature pruning is to reduce runtime: there is no trade-off between final success rate and runtime. Therefore, it occurs to me that during the ExpandFeatureSet loop in algorithm 2, rather than selecting the smallest feature set that is below an arbitrary FNR threshold, one could instead just select the subset size that directly minimizes the average runtime, in the \"mixed\" case with fall-backs to full attacks. Note that we are already running full attacks and subset attacks on these samples, so this shouldn't take any additional time. For the sake of sample-efficiency, one elegant way to approach this would be as a stochastic multi-arm bandit problem, where the \"arms\" are the choices of feature set sizes, and the \"reward\" is the negative runtime. Any existing bandit algorithm could then be applied.", "limitations": "The limitations section is perfunctory, and could be expanded: for example, the limits on the situations in which this attack is relevant could be discussed further. Societal impacts are addressed.", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "- The presentation is extremely clear and precise, and the paper appears to be very technically sound.\n- The problem setting is interesting, and the results are compelling.\n- Assuming that this is in fact the first paper, as claimed, to consider the \"high-throughput attack\" setting for adversarial attacks on decision tree ensembles, then it seems to be a highly impactful result. (However, this is not my area of expertise, so there may be prior work that I am not aware of.)", "weaknesses": "- The scope of interest in this work is perhaps somewhat limited:  it is fairly specific to the problem of attacking many samples on a decision tree ensemble in a batch.\n- The algorithm itself is simple, and empirically (rather than theoretically) motivated. However, it appears to be highly effective, so this is not a necessarily a problem.\n- The Limitations section could use some work, or be omitted: it does not mention any limitations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the two extremely interesting and insightful suggestions! We are in the process of exploring these and we will mention these possible variations in the final version of the paper. We agree with the reviewer and we think they could be effective in some specific use cases of our algorithm.\n\n**Randomly/maximally perturbing non-relevant features** \nThis is definitely a great observation! We believe that this is interesting and we are working on implementing this procedure.  Perturbing the non-relevant features should be tried when the pruned setting returns UNSAT or TIMEOUT. In these cases, the results of the pruned setting are unclear; therefore randomly perturbing non-selected features might result in a label flip and hence save the time of running a full search (if the pruned setting returns SAT, perturbing other features would not make sense: we have a valid adversarial example and changing other features could affect its predicted label). In these cases, as opposed to starting from the base example x (which would be like CUBE attack (Andriushchenko et al. NeurIPS'19)), one probably wants to start from something found by the search process.\n\nA side effect of adding random/maximal allowed perturbations is that the generated adversarial examples will be quite different than what would be found by the base algorithms (which is not problematic). \n\nMore generally, we have noticed that while *veritas* uses l-inf it tends, even in the *full* search,  to apply very sparse changes. Our intuition is that this is due to the fact that we are working with trees: each split only uses one attribute and trees have limited depth which means that going from the root to the leaf only involves a small number of attributes.\n\n**Just minimize runtime rather than selecting the smallest feature set**\nThis is also an extremely interesting point! The goal of the selected feature subset is indeed to reduce run time. The procedure proposed by the reviewer is effective and could benefit the *mixed* scenario. Our experiments hinted that a smaller feature subset is always reflected in a faster search, therefore we expect differences between the two approaches not to be consistent. However, this is a great idea and we are working to add it in the final version of the paper.\nFinally, we highlight that if the user has specific needs in terms of feature selection, a customized feature selection strategy can be applied in place of the one described in 3.2, and the rest of the method can still be employed as it is. \n\n**Limitations**\nWe will refine the *Limitations* sections to highlight that our approach is tailored to *repeated* evasion, and not cases where a single attack is performed.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "S6LGyW2CAH", "reviewer": "Reviewer_hmU3", "summary": "This paper studies adversarial attacks on tree ensemble models. The main contribution of this paper is to speed up (compared to *kantchelian* and *veritas*, please let me know if there is any misunderstanding) the process of crafting adversarial examples of tree ensemble models. It is claimed, under the setting of repeated adversarial attacks against the same model, that adversarial examples for tree ensembles tend to perturb a consistent but relatively small set of features, which is an interesting phenomenon. This paper advances the understanding of the adversarial robustness of tree ensemble models.", "questions": "+ In Line 20, \"generating adversarial examples is an NP-hard problem\" seems unreasonable since many existing methods can efficiently craft adversarial examples. Do you mean generating adversarial examples for tree ensemble is an NP-hard problem? \n+ In lines 28-29, the authors mentioned that previous works treat the clean examples in isolation while they make use of the regularities between clean examples to speed up adversarial attacks. The term \"regularity\" many times in this paper, but what is this regularity and what is the intuition behind this idea? I think it is better to illustrate the idea of \"regularities between clean examples\" with a figure.\n+ In Lines 48-48, \"we propose a theoretically grounded manner to quickly find this set of features\". I cannot find the results corresponding to this claim.\n+ What is the meaning of SAT and UNSAT? I suggest explaining the abbreviations when they first occur.", "limitations": "There is a limitation statement in Lines 312-313.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "+ As its title suggests, this paper proposes a faster method (compared to *kantchelian* and *veritas*) for performing repeated adversarial attacks, which would help the development of more robust tree ensemble models. The claim is backed by comprehensive experiments.\n\n+ The discussion in section 3 is easy to understand.", "weaknesses": "+ This paper does not comprehensively discuss the **related works**, which would lead to several problems:\n    +  To my knowledge, neural network is the most popular model in modern machine learning. I suggest further comparing the tree-ensemble models and neural networks in section 5. Besides, the existence of adversarial examples is first discovered in image classification (using NNs). I suggest providing an example of adversarial examples (in real-world applications) for tree ensemble models. I noticed that some experiments are on vision datasets like MNIST and FMNIST. I wonder whether tree ensemble models can beat (deep) neural networks in some tasks.\n    + This paper only mentions two adversarial attack methods for tree ensemble methods. I cannot properly evaluate the contribution of this paper without a comprehensive comparison with related works.\n\n+ As mentioned in the \"Questions\" part, the presentation of this paper can be further improved.\n+ It is confusing to use lowercase Italian letters to represent algorithms and datasets.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**NNs vs Tree Ensembles**\nJust because \"neural network is the most popular model in modern machine learning\" does not imply that all research should solely focus on them; we believe that diversity is also important. \nTree ensemble models like XGBoost are extremely popular, very easy to apply and still outperform NNs on tabular data (Grinsztajn et al. 2022).\n\nWe will add some references to techniques for the evasion of neural networks in Section 5. However, most state-of-the-art algorithms are now tailored to a specific model type. That is, they exploit properties of the model, e.g., the Kantchelian's MILP encoding exploits the logical structure of a decision tree. Hence, there are not always strong parallels between approaches for NNs and decision trees. \n\n**Examples of adv. ex. for tree ensembles**\nAdversarial examples are defined for tabular data as well as for image classification, and can therefore be generated for both NNs and tree ensembles. Consider a bank deploying a model to accept or deny loan requests by customers. A hacker may imperceptibly alter some user’s sensitive data to force a different outcome, e.g. a loan is rejected... but is accepted by subtly adding one month to the customer’s work seniority. We will add the example in the paper.\n\n**Not enough baselines** \nThe reviewer does not provide any concrete baselines that they would expect to be included in the analysis.\nAs an exact attack, we used *kantchelian*'s implementation as it proved to be faster than alternative SMT encodings (cites 9-12). We then considered several state-of-the-art approximate evasion attacks. We choose *veritas* as it is the best performing one to the best of our knowledge. In Section B.1 in the Supplement, we show how *veritas* is preferable with respect to another popular evasion method (LT attack). Thus we are unsure what the reviewer expects without specific references. \n\n**Problem Hardness**\nIn line 20, we mean that Kantchelian et al., ICML 2016 (cite 20 in the paper) showed that determining whether an adversarial example exists with a certain distance epsilon is NP-complete for decision trees. Finding the nearest adversarial example for a given normal example is not a decision problem, and hence we used the term NP-hard. \nThe same problem has been shown to be NP-complete for other model classes such as NNs [1]. \n\n[1] Guy Katz, Clark Barrett, David L Dill, Kyle Julian, Mykel J Kochenderfer, Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks, in Computer Aided Verification: 29th International Conference, CAV 2017.\n\n**Regularities** The term \"regularity\" refers to the fact that in many attacks (for different test examples) the same small number of features are perturbed to generate a valid adversarial example. This is also shown in Figure 1. We will make this clearer in the text.  \n\n**Theoretically grounded manner to identify relevant features** Section 3.2 presents an algorithm to identify a set of relevant features. \nThe adoption of a statistical test ensures that the extracted feature set guarantees a low enough false negative rate on the *mixed* setting.\nNamely, the statistical test guarantees with a $1 - \\eta$ probability that the false negative rate is below a threshold $\\tau$.  Both $\\eta$ and $\\tau$ are set by the user. \n\n**SAT/UNSAT** The first place that SAT/UNSAT are mentioned is Line 76, which describes the three possible outcomes of an evasion attack. SAT/UNSAT are defined immediately afterwards in Lines 78-80: the attack is SAT if a valid adversarial example is generated, UNSAT if a solution does not exist, or TIMEOUT if a solution could not be found within the allowed time limit. These are commonly used abbreviations\noriginating from mathematical logic.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Ms8ld38y3M", "reviewer": "Reviewer_fYgE", "summary": "The paper proposes a method to speed up the robustness verification of tree-based classifiers for all examples in a dataset. Previous methods solve the robustness verification problem for tree-based classifiers, which is NP-Complete, for each instance separately. However, the paper highlights that finding adversarial examples from a set of instances of the same dataset often requires perturbing only a small subset of features, called relevant features. The paper proposes a verification algorithm that employs state-of-the-art sound and complete verification algorithms. First, it tries to generate the adversarial example from this subset of relevant features and, if it is not found, tries again, considering all the features. Moreover, the paper proposes an algorithm to find the set of relevant features such that the probability that generating an adversarial example by perturbing only those features fails, even though the adversarial example exists, is less than a threshold with a certain confidence. The experimental evaluation considers two state-of-the-art verifiers and 11 tabular datasets commonly used in robustness verification literature. The experimental results show that verifying robustness by considering only the subset of relevant features results in a speed-up of up to 12x for gradient-boosted models and 6x for Random Forests.", "questions": "Is a set of relevant features present when generating adversarial examples against other threat models like $\\ell_1$​ and $\\ell_2$​? In other terms, does the proposed approach determine a speed-up when considering other attackers beyond $\\ell_\\infty$?\n\nHow does the proposed approach compare to approaches that speed up the efficiency of robustness verification by exploiting other points of view, like training models amenable to robustness verification [3]? (See the Weaknesses section for more details.)", "limitations": "The authors have explained the limitations of their approach appropriately, as claimed in the paper checklist. Furthermore, the authors have also discussed the potential negative societal impact of their work in Section 6. The experimental and implementation details have been thoroughly documented.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "**Original observation and algorithm that allow existing verifiers to speed up robustness verification of tree-based classifiers**: The observation that generating adversarial examples often requires perturbing only a subset of relevant features across instances of the same dataset is novel and leads to optimizing existing robustness verification algorithms. A disciplined approach is also provided to identify the subset of relevant features.\n\n**Theoretical analysis of the guarantees provided by the proposed verification algorithm**: Two theorems and their proofs are provided regarding the guarantees of the verification algorithm: (i) if an adversarial example is found by perturbing only the subset of relevant features, the same adversarial example will also work when considering all the features; (ii) if an adversarial example exists, the algorithm is guaranteed to find it.\n\n**The experimental settings considered are comprehensive and the results are significant**: The experimental evaluation is performed on several datasets and for two state-of-the-art verifiers. The results convincingly demonstrate the speed-up that can be achieved by considering only the relevant features. This is a significant result, as existing state-of-the-art verifiers struggle to verify the robustness of models based on decision trees.", "weaknesses": "**Only one threat model is considered**: Even though the $\\ell_\\infty$​ threat model is widely addressed in the literature, it would have been interesting to also consider the generalization of the proposal to other attackers like $\\ell_1$​ and $\\ell_2$ attackers that are considered in the literature when considering tabular data [1]. The kantchelian verifier can be used, since it supports also $\\ell_1$​ and $\\ell_2$ attackers.\n\n**Missing comparison with other methods to improve the efficiency of robustness verification**: Proposals in the literature have addressed the problem of speeding up robustness verification and adversarial examples generation by training models that are amenable to robustness verification. First, neural networks have been considered [2], but recently, tree-based classifiers that admit robustness verification in polytime have also been explored [3]. The authors should consider comparing their methodology with [3], which is not addressed in the related work. They should highlight the pros and cons of their proposals with respect to this other way to make robustness verification of forests more efficient.\n\n[1] Simonetto et. al., \"A unified framework for adversarial attack and defense in constrained feature space\", in IJCAI 2022.\n\n[2] Xiao et. al., “Training for faster adversarial robustness verification via inducing relu stability,” in ICLR, 2019.\n\n[3] Calzavara et. al., \"Verifiable Learning for Robust Tree Ensembles\", in CCS 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Why l-inf only?**\nWe choose to work with the l-inf norm as recent works on approximate evasion \nattacks primarily focus on this scenario.\nThis favours the experimental evaluation as these methods are the most efficient in literature, while still working in a perfectly reasonable scenario where the attack is defined by the magnitude of the largest perturbation. At the same time, we believe other attack models should present the same advantages when exploiting our approach, as the number of considered features is always a proxy for the hardness of the evasion. \n\n**Missing comparisons**\nWe thank the reviewer for the multiple useful references which will include and discuss in the paper!  Ensuring polynomial verifiability is an exciting and important line of work. A drawback to current approaches for polynomial verifiability is that they clearly do result in (large) decreases in predictive performance. Whether this is permissible will depend on the considered application.  We would also highlight that Section C in the supplement shows results for applying our approach to GROOT forests which are robustified ensembles (Vos \\& Verwer ICML'21).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper investigates the adversarial robustness of tree ensembles.  Along these lines the authors propose that only a small number of features are important for adversarial mispredictions.  The paper proposes an algorithm that can be used in order to identify the set of features that are vulnerable to small perturbations that could cause mispredictions of the perturbed instance.  The authors validate their proposed method using a diverse set of datasets that includes both tabular and image data.  

For the largest part the reviewers were satisfied with the paper and the responses received during the rebuttal and there has been mutual agreement on certain cases for certain clarifications to be provided in the final version of the manuscript.
Decision: Accept (poster)