Faster Repeated Evasion Attacks in Tree Ensembles

Authors: lorenzo  cascioli
laurens  devos
ondrej  kuzelka
jesse  davis
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 17:18:14

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.

Main paper: 
 introduction: 
 One of the most popular and widely used classes of models is tree 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, 17] , 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 a bank that uses a 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 to their work seniority) that results in the model making a different decision on the customer's application. The slightly modified customer record is an adversarial example. There is significant interest in reasoning about tree ensembles to both generate such adversarial examples [15, 36] and perform empirical robustness checking [23, 8, 10] where the goal is to determine how close the nearest adversarial example is.Generating adversarial examples is an NP-hard problem [23] , which has spurred the development of approximate techniques [8, 36, 10] . These methods exploit the structure of the trees to find adversarial examples faster, e.g., by using graph transformations [8] or discrete (heuristic) search [36, 10, 12] . Still, these techniques can be slow, particularly if there is 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.A weakness to 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 to a large number of "normal" examples each of which should be perturbed to elicit a 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, 10] is quickly becoming important as machine learning is applied in sensitive application areas. Being able to efficiently generate adversarial examples is crucial for computing empirical robustness (e.g., [10] ), 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) [27] 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, 31, 22] .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 a fixed learned tree ensemble, adversarial examples tend to be generated by perturbing the same, relatively small set of features. We propose a 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 [23, 10] . 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 is publicly available at https: //github.com/lorenzocascioli/faster-repeated-evasion-tree-ensembles. 
preliminaries: 
 We briefly explain tree ensembles, evasion attacks, and the two adversarial generation methods used in the experiments. We assume a d-dimensional input space X ⊆ R d and binary output space Y = {-1, 1}. We focus on binary classification because most existing methods for generating adversarial examples for tree ensembles are designed for this setting [1, 23, 10] .Tree Ensembles Tree ensembles include algorithms such as (gradient) boosted decision trees (GBDTs) [16, 9] and random forests [3, 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 a split condition on some attribute f in the form of a less-than comparison X f < τ , where τ is the split value. Leaf nodes have no children and only contain an output value. Each tree starts with a root node, the only one without a parent.Given an example x, an individual tree is evaluated recursively starting from the root node. In each internal node, the split condition is applied and if it is satisfied, then the example is 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 a sigmoid transformation to the sum of the leaf values.x in order to elicit a misprediction [23] . Following existing work on tree ensembles [23, 7, 10] , we say that x is an adversarial example for normal example x when (1) ∥x -x∥ ∞ < δ where δ 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 x and x differ.We briefly describe the two existing adversarial example generation methods A : (T , x, δ, t max ) → {SAT (x), UNSAT , TIMEOUT } used in this paper: kantchelian [23] and veritas [10] . These methods take as input an ensemble T , a normal example x, a maximum perturbation size δ, and a timeout t max . They output SAT (x), where x is an adversarial example for x, UNSAT , indicating that no adversarial example exists, or TIMEOUT , indicating that no result could be found within t max . Timeouts are explicitly handled because adversarial example generation is NP-hard [23] . kantchelian formulates the adversarial example generation task as a mixed-integer linear program (MILP) and uses a generic MILP solver (e.g., Gurobi [20] ). Specifically, kantchelian directly minimizes the δ = ∥x -x∥ ∞ value. Given an example x, it computes:EQUATIONThis approach exploits the fact that a tree ensemble can be viewed as a set of linear (in)equalities. Three sets of MILP variables are used. Predicate variables p i represent the split conditions, i.e., each p i logically corresponds to a split on an attribute f : p i ≡ f < τ . Leaf variables l i indicate whether a leaf node is active. The bound variable b represents the l ∞ distance between the original example x and the adversarial example x. 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 τ 1 < τ 2 appear in the tree for attribute f , andp 1 ≡ f < τ 1 and p 2 ≡ f < τ 2 , then p 1 =⇒ p 2 .Leaf consistency constraints enforce that a leaf is only active when the splits on the root-to-leaf path to that leaf are satisfied. Lastly, the mislabel constraint requires the output to be a certain class: for leaf values v i , i v i l i ≶ 0. The objective directly minimizes the bound variable.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 a 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 a given δ, veritas solves the following optimization problem:EQUATIONThe output of the model T (x) is maximized when the target class for x 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.1). 
method: 
 Adversarial example generation methods are often applied in the following setting:Given a tree ensemble T , a set of test examples D, and a maximum perturbation size δ Generate adversarial examples for each x ∈ D.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 to small perturbations, 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 to fragile 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 conditions in these disproportionately sensitive parts are exploited by adversarial examples more frequently than other attributes. Figure 1 Our proposed approach has two 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 can 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 a theoretically grounded statistical test.Our proposed approach speeds up the adversarial example generation procedure by limiting the scope of the adversarial perturbations to a subset of features F S . This section assumes that we are given such a 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 δ. That is, for each attribute f ∈ F with value x f , the attribute values are limited to [x f -δ, x f + δ]. Algorithm 1 summarizes the pruned and mixed approaches. We now describe both in greater detail.Algorithm 1 Fast repeated adversarial example generation 1: parameters: maximum perturbation size δ, timeouts t full max and t prun max for full and pruned, generation method A : (T , x, δ, t) → {SAT (x), UNSAT , TIMEOUT } return: D 13: end function Pruned Approach The pruned setting disallows modifications to the attributes in the non-selected set of attributes F NS = F \ F S . We accomplish this by pruning the trees in the ensemble. Any node splitting on attributes in F NS is removed. Its parent node is directly connected to the only 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 , F S , x). The adversarial example generation methods can be applied as normal to the pruned ensemble, but they will only generate adversarial examples with perturbations to the attributes in F S . Pruning simplifies the MILP problem of kantchelian because all predicate variables p i that correspond to splits in internal nodes of pruned 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.T prun ← PRUNE (T full , F S , x) (Sec. 3.1) 6: α ← A (T prun , x, δ, t prun max ) 7: if α ̸ = SAT (x) ∧ mixed flag set then 8: α ← A T full , x, δ, t fullsubtrees, and leaf variables l i that correspond to leaves of pruned subtrees can be removed from the mathematical formulation. For veritas, the search space is reduced in size because the pruned leaves are removed from the graph representation of the ensemble. Hence, for both systems, on average, the problem difficulty is reduced by pruning the ensembles.Pruning the trees does not affect the validity of generated adversarial examples: if x is an adversarial example for a normal example x generated on a pruned ensemble, then x is also an adversarial example for the full ensemble. Proposition 3.1. Given normal example x that is correctly classified by the full ensemble T full .Let T prun = PRUNE(T full , F S , x) and x = A(T prun , x, δ, t max ) (i.e., T prun (x) ̸ = T prun (x) and ∥x -x∥ ∞ < δ). Then it holds that T full (x) ̸ = T full (x).Proof. Because only branches not visited by x are removed, T prun (x) = T full (x). The values for features in F NS are fixed, so these values are equal between x and x. Hence, x only visits branches in T full that are also in T prun . Therefore, T prun (x) = T full (x).However, an UNSAT generated on a pruned ensemble is inconclusive: it might still be the case that an adversarial example exists for the full ensemble, albeit one with perturbations to features in F NS .The pruned setting generates a false negative if it reports UNSAT , yet the full setting reports SAT .The mixed setting takes advantage of the fast adversarial generation capabilities of the pruned setting, but falls back to the full setting when the pruned setting returns an UNSAT or times out. A much stricter timeout t prun max is used for the pruned setting to fully take advantage of the fast SAT s, while avoiding spending time on an uninformative UNSAT . The mixed setting is guaranteed to find an adversarial example if the full setting can find one. Theorem 3.2. Assume a normal example x and maximum distance δ. If an adversarial example can be found for the full ensemble T full , then the mixed setting is guaranteed to find an x such that ∥x -x∥ ∞ < δ and T full (x) ̸ = T full (x).Proof. The mixed setting first operates on the pruned ensemble T prun using a tight timeout and optimizes Equation 1 or 2 using kantchelian or veritas respectively. This returns (1) an adversarial example x, (2) an UNSAT or (3) times out. In case (1), the generated adversarial example x is also an adversarial example for the full ensemble (Prop 3.1). In cases (2) and (3), the mixed setting falls back to the full setting operating on the full ensemble T full with the same timeout. Hence, it inherits the full method's guarantees.A good subset of relevant attributes F S 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 F S 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 in many false negatives (or slow calls to the full search in the mixed setting). The procedure is given in Algorithm 2.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 is met by statistically testing whether the identified subset guarantees that the false negative rate is smaller than a given threshold τ with probability at least 1 -η, for a specified confidence parameter η. 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 (EXPANDFEATURESET(F S , D, D) in Algorithm 2). If all tests fail, then a 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 a small set of n generated adversarial examples. A first zeroth set is used merely for obtaining the first feature counts.The statistical tests are performed as follows. The null hypothesis is that FNR is greater than the threshold τ . Take D F = (x 1 , x 2 , . . . , x N ) the dataset we use to find the feature subset F S . We define v = (v 1 , v 2 , . . . , v N ) to be the binary vector such that v i = 1 if the pruned search with the feature subset F S returns UNSAT for the example x i but the full search returns SAT , and v i = 0 otherwise. Then the true false negative rate corresponding to F S can be written asFNR = 1 N N i=1 v i .The small set of n examples from which we are estimating the false negative rate is a random vector X = (X 1 , X 2 , . . . , X n ) sampled without replacement from D F . We also define V = (V 1 , V 2 , . . . , V n ) where V i is the binary random variable defined analogically to how we defined v i . It follows that n i=1 V i is distributed as a hypergeometric random variable. We use the method of inversion of acceptance intervals to find a one-sided confidence interval [0; ∆] for the false negative rate with confidence level equal to a given 1 -η (see, e.g., Section 5.2 in [2] ), exploiting the fact that the cumulative distribution function of a hypergeometric distribution can be computed efficiently (CONFIDENCEINTERVAL(v, n, η) in Algorithm 2). We reject the null hypothesis if the confidence interval does not contain the threshold τ . It follows from the basic properties of confidence intervals that this yields the desired test with confidence 1 -η. Since we execute the test 4 times in the algorithm, we apply a union-bound correction of factor 4 (we use confidence level 0.9). Note that there is a 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. [0; ∆] ← CONFIDENCEINTERVAL(v, n, η) 7:if the threshold τ is in [0; ∆], then EXPANDFEATURESET(F S , D, D)8:else break the loop 9: end for 10: return: F SQuestion: 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 crossreferenced. • 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 a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 
experiments: 
 Empirically, we address three questions: (Q1) Is our approach able to improve the run time of generating adversarial examples? (Q2) How does ensemble complexity affect our approach'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 a large number of dimensions. Therefore, we present numerical experiments for ten binary classification tasks on high-dimensional datasets, using both tabular data and image data, as shown in Table 1 .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, 25] or GROOT forest (a robustified ensemble type [32] ) ensemble T . From the test set, we randomly sample 10 000 normal examples and attempt to generate adversarial examples by perturbing each one using the kantchelian or veritas attack. Table 1 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 fmnist 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 δ and learners' tuned hyperparameters after the grid search described in Appendix B. Each ensemble T has maximum tree depth d and contains M trees. The learning rate for XGBoost is η. GROOT robustness is defined by ϵ. The pruned and mixed settings work as follows. We use the procedure from Section 3.2 to select a subset of relevant features. We use τ = 0.25, n = 100 and η = 0.1. We then apply Algorithm 2: we generate 5 sets of n 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 a 1-η = 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 1). We set a timeout of one minute for the full setting, and a much stricter timeout of 1 (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.2 EQUATIONQ1: Run Time Table 2 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 are in the range 1.4x-36.2x with an average of 9x (± 8x), and for the mixed in the range 1.1x-20.5x 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.2x/1.6x) for RF and 4.7x/2.7x (± 3.4x/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). 3Tables 5 and 6 in the supplement also report additional statistics 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 pruned 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). Figure 3 shows the number of executed searches as a function of time for four combinations of attack algorithm and model type. 4 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 see a more noticeable difference between the pruned and the mixed search on several datasets. This indicates that the mixed strategy falls back more often to an expensive full search. 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 kantchelian with RFs due to its computational cost. Figure 5 (top) shows how the run time to perform 10 000 searches varies as function of the maximum tree depth for a 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 full search scales worse: deeper trees lead to higher run times. Figure 5 (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 6 for XGB and 10 for RF. Again, the pruned and mixed approaches show much better scaling behavior. Note that veritas'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 run time performance than the standard full search for more complex ensembles. Q3: Empirical FNR We use Algorithm 2 to bound the false negative rate to be less than 25% with high probability. Tables 5 and 6 in 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, F S contains 17% of the features. Out of 300 experiments, 5 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 a better intuition on the relationship between the empirical FNR and the speedup, Figure 6 shows this tradeoff on two datasets using XGBoost. In essence, higher FNRs correspond to smaller feature subsets, hence larger speedups.Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it 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 we clearly describe all the adopted tree ensemble types (XGB, RF, GROOT, Section 2), evasion attacks (kantchelian and veritas, Section 2), and datasets (Section 4 and Appendix B). The method is described in Section 3 with the aid of Algorithms 1 and 2. We then describe our experimental methodology in Section 4. Table 1 reports all datasets characteristics, each tuned model's hyperparameters, and the max perturbation size δ for each attack. Finally, Table 3 points toward the publicly available sources we gathered the datasets from. 
related work: 
 Adversarial examples have been theoretically studied and defined in multiple different ways [14, 18] .Approaches to reason about learned tree ensembles have received substantial interest in recent years including algorithms to perform evasion attacks [23, 15] (i.e., generate adversarial examples), perform robustness checking [8] , and verify that the ensembles satisfy certain criteria [11, 10, 26, 29] . Kantchelian et al. [23] were the first to show that tree ensembles are susceptible to 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 [8, 10, 35, 36] though not all of them are able to generate concrete adversarial examples (e.g., [8, 35] ).Other work focuses on making tree ensembles more robust. Approaches for this include adding generated adversarial examples to the training data (model hardening) [23] , or modifying the splitting procedure [7, 4, 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.Another line of work aims at directly training tree ensembles that admit verification in polynomial time [5, 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, state-of-the-art algorithms are tailored to one specific model type as they typically exploit specific properties of the model, e.g., the work on tree ensembles often exploits the logical structure of a decision tree. 
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 in the specific scenario when the same model is repeatedly attacked. Plus, it excels on high-dimensional datasets. Our evaluation only considered l ∞ attacks, whereas other norms such l 1 and l 2 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. 
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 is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or 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., deployment 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 not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to 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 to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: -Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to 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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to 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. 
 
 Appendix: Adversarial examples are often generated for tasks like computing adversarial accuracy [32] , computing empirical robustness [10] , and performing model hardening [23] . The effect of using the approximation proposed in this paper differs for each task.Computing the adversarial accuracy of a classifier only requires determining whether an adversarial example x 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 an 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 a classifier requires finding the nearest adversarial example x for each normal example x. Because the pruned approach does not consider all features and the mixed approach may not, they may return an adversarial example that is further away than if the full search space was considered. Hence, when using an exact attack like kantchelian, the empirical robustness computed using the mixed strategy is an overestimate of the true empirical robustness. We show this and we study what happens with an approximate method in Appendix E.In model hardening, a large number of adversarial examples are generated and added to the training data [23] . The pruned approach can be used to generate a lot more adversarial examples in a fixed amount of time.We expand the discussion on Table 1 , 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 a fully categorical domain (where the l ∞ norm loses meaning). When running kantchelian on random forests and GROOT forests, we had to 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 increasing the ensemble size on 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.We evaluate our two methods on a 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 (1) 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 to 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 state-of-the-art method: LT-attack [36] . On the full setting, they have the same success rate and veritas is 25 to 60 times faster, as shown in Table 4 for XGBoost ensembles. Tables 5 (kantchelian) and 6 (veritas) report the average times and speedups when attempting to generate 10 000 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 F S , 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., an 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 to 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. Tables 7 (kantchelian) and 8 (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. It can happen that with a strict timeout, the pruned setting is not able to find a solution, as the task remains complex even working with a reduced feature set. In those cases, pruned ends with a TIMEOUT and mixed will have to execute the full search.We further extend Figure 6 from Q3 in Section 4, which explicitly shows the relationship between the empirical false negative rate and the speedup of the pruned setting. 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 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. There are cases where false negatives are less problematic, such as when one simply needs to generate a lot of adversarial examples for model hardening [23] . In these cases, the pruned approach really excels at 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 in mnist).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. The statistical test described in 3.2 takes as hyperparameters the acceptable false negative rate τ and the confidence 1 -η. We perform a sensitivity analysis where we vary τ ∈ [0.05, 0.1, 0.25, 0.5] and 1 -η ∈ [0.8, 0.9, 0.95] on the miniboone dataset.Table 9 shows the mixed speedup for (veritas, XGBoost) for all combinations of the considered values for τ (FNR) and 1 -η (confidence). For all settings, our approach improves upon the run time of always running a full search (i.e., speedup is always > 1). When τ = 0.05, many features are selected and hence there is less pruning. τ = 0.1 and τ = 0.25 perform identically. When τ = 0.5, the value of 1 -η impacts the selected feature set. A confidence of 0.95 keeps the same feature set of τ = 0.1 and τ = 0.25. However, a lower confidence results in an even smaller feature set, which 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 as small of a feature subset as possible, to speed up the pruned setting. Moreover, a larger confidence 1 -η can increase the number of selected features as it shrinks the confidence interval for the empirical FNR. Timeouts always need to be explicitly handled, due to the hardness of the evasion problem [23] . While Tables 7 and 8 show that in most of our experiments timeouts are rare or totally absent, to complete the discussion we perform a sensitivity analysis on the value used for the pruned setting timeout. We vary t prun max ∈ [0.001, 0.01, 0.1, 1] seconds when attempting to generate 10 000 adversarial examples on the fmnist dataset. We only consider veritas for RF in this experiment.Table 10 shows the fraction of timeouts for the pruned setting as well as the pruned speedup and the mixed speedup for each value of t prun max . The smaller t prun max , the larger the number pruned timeouts, which corresponds to a faster (but less accurate) pruned search. If the timeout value is too low, this adversely affects mixed search because it leads to more calls to the full procedure. Conversely, if t prun max is too large, the search becomes slower as the pruned setting starts losing time on a few slow instances.Thus the ideal t prun max lays in between the two extremes. In the presented case, t prun 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). 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 the full and the pruned setting.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 x in a test set. We use adversarial examples generated with the experiments presented in Q1 in Section 4 (and Appendix C).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.veritas tries to generate an adversarial example such that the ensemble assigns as high a probability as possible to the incorrect label. Hence, a natural empirical measure for the quality of the generated examples is to compare the difference in the ensembles probabilistic predictions for the adversarial examples generated by each approach. Namely, we compute T (x) -T (x ′ ) where x is generated by the full search, x′ is generated by the pruned (mixed) search, and (in an abuse of notation) T (x) returns the probability an example belongs to most likely class.Table 13 shows the average differences in predicted probability between full and pruned/mixed 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. Adversarial examples have been theoretically studied and defined in multiple different ways [14, 18] . More specifically, Ilyas et al. showed how certain features in a 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, 15] (i.e., generate adversarial examples), perform robustness checking [8] , and verify that the ensembles satisfy certain criteria [11, 10, 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-based systems [15, 11] . These approaches propose varying ways to encode a tree ensemble in a 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 MILP in practice.Because MILP and SMT are exact approaches, 6 they search for the optimal answer which in certain 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 a K-partite graph representation in which a max-clique corresponds to a specific output of the ensemble [8, 35] . They introduced a fast method to approximately evaluate robustness, [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 procedure [7, 4, 32] , 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 [1] and using a robust 0/1 loss [19] . 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.Another line of work aims at directly training tree ensembles that admit verification in polynomial time [5, 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, state-of-the-art algorithms are tailored to one specific model type as they typically exploit specific properties of the model, e.g., the work on tree ensembles often exploits the logical structure of a decision tree. Justification: The limitations of the proposed methods are discussed in the paper. In Sections 1 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 is the case in Sections 1, 3 and in 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 6. 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 are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are 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 on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a 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, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.• 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 a 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 a 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 to 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 to replicate the results, access to a hosted model (e.g., in the case 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 submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. 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 1 and 4). Tables 7 and 8 • If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).38th Conference on Neural Information Processing Systems (NeurIPS 2024).We are abusing terminology: here, T (x) is the predicted probability. Previously, it was the predicted label.Appendix D provides a sensitivity analysis for the hyperparameter settings of the statistical test and timeouts.See Tables5 and 6in the supplement.The supplement shows these plots for all datasets plus for GROOT forests (see Appendix C).5 folds x 10 datasets x 3 ensemble types x 2 attacksMILP is technically anytime, but the approximate solutions are not useful in practice for this problem setting, see[10]. 


Decision: 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.

Reviews: review: paper_summary: paper_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. 
The 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. 
Experimentally, 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.
strength_weakness: strength_weakness: 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.
questions: 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?
How 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: 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. 
Additionally, 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?
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.
questions: questions: - Can we generate the adversarial example with only a single example?

- 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: limitations: - I would probably encourage the authors to discuss the above limitation in their paper as well.
paper_summary: paper_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.) 

The 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.

This 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.

The 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.
strength_weakness: strength_weakness: - 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.
- 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.
- The Limitations section could use some work, or be omitted: it does not mention any limitations.
questions: questions: I have two suggestions for improvements to the algorithm; perhaps you could try these?
1. 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.
2. 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: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: + This paper does not comprehensively discuss the **related works**, which would lead to several problems:
    +  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.
    + 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.

+ As mentioned in the "Questions" part, the presentation of this paper can be further improved.
+ It is confusing to use lowercase Italian letters to represent algorithms and datasets.
questions: 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? 
+ 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.
+ 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.
+ What is the meaning of SAT and UNSAT? I suggest explaining the abbreviations when they first occur.
limitations: limitations: There is a limitation statement in Lines 312-313.
paper_summary: paper_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.
strength_weakness: strength_weakness: **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.

**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.

[1] Simonetto et. al., "A unified framework for adversarial attack and defense in constrained feature space", in IJCAI 2022.

[2] Xiao et. al., “Training for faster adversarial robustness verification via inducing relu stability,” in ICLR, 2019.

[3] Calzavara et. al., "Verifiable Learning for Robust Tree Ensembles", in CCS 2023.
questions: 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$?

How 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: 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.

Comments: title: Response to Rebuttal
Thanks for your response
comment: Thank you for your response! We will expand the next version of the paper mentioning the suggested variations.

As for the last point, we meant “a smaller feature subset“ that still guarantees the bound on the FNR. Therefore the mentioned scenario with a feature set of size one would not be possible, as it would produce too many false negatives. The proposed alternative is now clear to us and we are working on it!
Thank for you incorporating our responses into your assessment of this work. We will indeed revise the paper for its next iteration.
Thank you for considering my suggestions, and agreeing to expand the limitation section. I am keeping my original score of 'Accept'.

I was slightly confused by your comment that "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." To clarify, in my suggestion, I meant to refer minimizing to the _average_ runtime, _including the time for the full-feature search in instances where the "mixed" strategy falls back to performing a full search._ Therefore, a smaller feature set should not always lead to a faster average search. (Trivially, for example, if the feature set is of size one, then nearly every instance will fall back to full search, so the total time will be approximately equal to or even slightly greater than simply performing a full search.) By minimizing total average runtime directly, this should eliminate the need for an arbitrary success threshold hyper-parameter, at least in this "mixed" case.
Dear authors, 

Thanks for your quick reply, which answers all my questions. I suggest revising the paper according to the reply in future revisions. 

In summary, this paper studies an interesting problem about speeding up the adversarial attack against the tree ensemble models. Although this problem does not attract much attention from the community, it helps improve the performance of adversarial attacks in some specific scenarios. I will raise the score to 5.
Dear Reviewer SynL, 

Can you please comment and indicate if your questions/concerns have been addressed by the authors' response?  If you have any follow-up clarification questions, please ask your questions _as soon as possible_.  We do not want to leave less than 24 hours to the authors to comment/respond to your response.

Your AC
We will respond to your points in reverse order.
 
3. Section 4.2 of Kantchelian et al. has a section entitled "Theoretical Hardness of Evasion". 

This section studies the computational complexity of constructing what they call an evading example, which is what we refer to as an adversarial example for tree ensembles. The proof in this section of their paper shows that it is possible to cast a known NP-complete problem (3SAT) as an instance of an evasion problem for tree ensembles using a linear reduction. This means the usual: if one had a polynomial time evasion algorithm, it would be possible to solve any problem instance of the well-known NP-complete problem in poly time, which is generally seen as a contradiction.

Thus Kantchelian et al. is indeed showing what we state in the paper wrt to the hardness of constructing adversarial examples for tree ensembles.  We would also highlight that other tree-based evasion attack papers make similar statements about the hardness of the problem (e.g., https://arxiv.org/pdf/2010.11598). 

This theoretical result is not at odds with statement that in practice it may often be possible to easily find evading/adversarial examples; just like one can efficiently solve many 3SAT problems using modern satisfiability solvers.  

2. We agree that is absolutely OK to ask to include additional baselines in an experiment. However,  "I cannot properly evaluate the contribution of this paper without a comprehensive comparison with related works" is neither a constructive nor actionable comment. Could you please provide a specific attack that you would expect to see included in our evaluation?

While there may be 10s of approaches for NN, there are far fewer for trees. As far as we are aware, approaches developed for NNs are not directly applicable to trees. If you have specific attacks for NNs that are applicable to trees, please let us know.

As stated in our initial rebuttal, we have provided justifications for omissions in the paper. We omitted SMT-based approaches (See appendix E) because they are an exact approach like Kantchelian but do not perform as well as Kantchelian.  Similarly, as discussed in B.1 we have omitted the LT attack because it has the same success rate while being an order of magnitude (or more) slower than Veritas.  We are not convinced that it is meaningful to try to improve on the less performant approaches: even with improved run times one would still prefer the more performant Kantchelian and Veritas approaches in practice.

1. We will include the hack example and further explain adversarial examples in Tabular data. For another example of this in tabular data is about domain name registrations which is discussed in the introduction and expanded upon in our response to reviewer SynL.
Thank you for your response. We will absolutely add both points that you requested in the next version of the paper!
Thank you. We will add the clarifications and include the sensitivity study in the next version of the paper!
Dear authors,

I have read the rebuttal, which addresses some of my concerns. I still have some follow-up questions.

1. About NNs v.s. Tree Ensembles. **The authors seem to have not fully understood my main concern.**
To be clear, I am not saying "all research should solely focus on NNs". As mentioned in my review,  adversarial examples are first observed in *vision data* (or more precisely, in the last five years, the term "adversarial examples" in the ML community often refers to vision adversarial examples first observed in 2013). Since the tree ensemble models are "very easy to apply and still outperform NNs on *tabular data*" as claimed by the authors, **there is a gap between tree ensemble models and adversarial examples.**

    The hack's example in the rebuttal helped me understand the adversarial examples in tabular data. I suggest the authors also explain **what the adversarial examples are in Table 1.**  Providing some examples of the data and the corresponding adversarial examples in the datasets would help.

    I also suggest the authors reconsider the choice of Figure 4. Maybe tabular data is more suitable here. 

2. As for the baseline, in vision adversarial attacks, it is common to compare 10+ attack methods, while in this paper only two methods are compared. It is natural for a reader to ask whether this question (i.e., adversarial attacks against tree ensemble models) is in line with the community's taste.

3. About the Problem Hardness. According to the rebuttal, "generating adversarial examples is an NP-hard problem" in Line 20 is a term misuse. The question of "determining whether an adversarial example exists" discussed by Kantchelian et al., ICML 2016 and [1] is referred to as "robust verification/certification" in the literature, which is parallel to adversarial attack, adversarial defense, and adversarial training. The above two references can not support the claim that "generating adversarial examples is an NP-hard problem". The authors seem to be unfamiliar with the research on the adversarial robustness of machine learning models. In vision data, in most cases, the adversary can craft an adversarial example using a 10-step PGD. Therefore, I do not believe crafting adversarial examples is a computationally hard problem. Nevertheless, this paper significantly speeds up Kantchelian and veritas. The discussion here is mainly about the representation.
I thank the authors for their response. 

It would have been interesting to see some results on your approach applied with $l_1$ or $l_2$-norm attackers, but I understand that computing these new results requires time. Additionally, since Veritas supports only $l_\infty$-attackers, this tool would have required an extension. However, I agree with your statement that the proposed approach should show advantages even when applied to these two threat models. I hope you will provide some experimental evidence on this fact in a next version of the paper.

I strongly encourage the authors to add the following to the paper:
- Acknowledgment that the choice to work only with $l_\infty$-norm attackers is a limitation of your evaluation. Although it is a popular attacker, $l_2$ and $l_1$ norms have also been adopted in the literature.
- The discussion on polynomial verifiability in the related work section, as you mentioned in your response.
I have received the rebuttal comments and appreciate the author's response. Particularly, thank you for performing and reporting on the sensitivity analysis for the parameters. I also agree with your statements on the dataset characteristics, thank you for the clarifications. I will continue to review and discuss with the other reviewers.