Faster Repeated Evasion Attacks in Tree Ensembles

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.

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

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

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

3

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.

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.

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

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

Rating

5

Confidence

4

Soundness

3

Presentation

2

Contribution

2

Limitations

There is a limitation statement in Lines 312-313.

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.

Strengths

- The presentation is extremely clear and precise, and the paper appears to be very technically sound. - The problem setting is interesting, and the results are compelling. - 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. - 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

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.

Rating

7

Confidence

2

Soundness

4

Presentation

4

Contribution

2

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.

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.

Strengths

- The paper is well-written. It guides the reader well, and provides intuitions about the theoretical aspect of the work. - The proposed method is simple and easy to implement. - 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.

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.

Rating

4

Confidence

4

Soundness

3

Presentation

3

Contribution

2

Limitations

- I would probably encourage the authors to discuss the above limitation in their paper as well.

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.

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

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?

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

2

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?

Thanks for your response

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.

Response to Rebuttal

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.