Evasion and Hardening of Tree Ensemble Classifiers

By Alex Kantchelian, J. Doug Tygar, Anthony D. Joseph. 2015

227 citations recorded by the source corpus.

Classifier evasion consists in finding for a given instance $x$ the nearest instance $x'$ such that the classifier predictions of $x$ and $x'$ are different. We present two novel algorithms for systematically computing evasions for tree ensembles such as boosted trees and random forests. Our first algorithm uses a Mixed Integer Linear Program solver and finds the optimal evading instance under an expressive set of constraints. Our second algorithm trades off optimality for speed by using symbolic prediction, a novel algorithm for fast finite differences on tree ensembles. On a digit recognition task, we demonstrate that both gradient boosted trees and random forests are extremely susceptible to evasions. Finally, we harden a boosted tree model without loss of predictive accuracy by augmenting the training set of each boosting round with evading instances, a technique we call adversarial boosting.

Subfields: Artificial Intelligence, Evaluation & Benchmarks, Safety, Robustness & Interpretability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Evaluation & Benchmarks

In Safety, Robustness & Interpretability

Citations in the corpus

Certified Robustness to Adversarial Examples with Differential Privacy (2018, background): “Attacks have used various norms to quantify an attacker’s ability to perturb an image: the 0-norm [43], 1-norm [28], [7], 2-norm [53], [7], [2], and ∞-norm [19], [59], [7], [2], [35].”
Wild Patterns: Ten Years After the Rise of Adversarial Machine Learning (2017, background): “Non-di ﬀ erentiable learning algorithms, like decision trees and random forests, can be attacked with more complex strategies [73] or using the same algorithm against a differentiable surrogate learner [72].”
Adversarial Detection of Flash Malware: Limitations and Open Issues (2017, background): “For this reason, we can not state with certainty that Random Forests are generally more secure (a more powerful white-box attack as that in [20] may enable evading them with higher probability).”
Enhancing robustness of machine learning systems via data transformations (2017, background): “Evasion attacks have been proposed for a variety of machine learning classifiers such as Support Vector Machines [3], [13], tree-based classifiers [13], [7] such as random forests and boosted trees and more recently for neural networks [5], [17], [14], [8], [4], [12].”
A Theoretical Framework for Robustness of (Deep) Classifiers against Adversarial Examples (2016, background): “Related studies (Szegedy et al., 2013; Goodfellow et al., 2014; Xu et al., 2016; Kantchelian et al., 2015; Rndic & Laskov, 2014; Biggio et al., 2013; Papernot et al., 2016b; Sinha et al., 2016) assume the adversary does not have an opportunity to inﬂuence the training data, but instead ﬁnds…”
Better the Devil you Know: An Analysis of Evasion Attacks using Out-of-Distribution Adversarial Examples (2019, methodology): “This paper’s focus is evasion attacks which have been proposed against supervised ML algorithms used for image classification [13, 18, 24, 45, 97, 114], object detection [26, 83, 127], image segmentation [6, 41], speech recognition [19, 133] as well as other tasks [27, 48, 65, 129]; generative model”
Hardening Classifiers against Evasion: the Good, the Bad, and the Ugly (2017, methodology): “sprouted for evasion models acting directly on features [7], [20], [1], [16].”
Feature Conservation in Adversarial Classifier Evasion: A Case Study (2017, methodology): “The approach builds on feature-space iterative retraining methods proposed by Li et al. [19] and Kantchelian et al. [16], but is, to our knowledge, the ﬁrst method which uses problem space evasion for evaluating and boosting evasion robustness.”
Resilient Linear Classification: An Approach to Deal with Attacks on Training Data (2017, unknown): “, support vector machines (SVMs), principal component analysis, logistic regression, articial neural network, and (ensemble) decision trees – can strategically alter the training data to minimize the accuracy of the algorithms [6, 7, 23, 27, 34, 46], to maliciously aect the performance of data-dri”
Dimensionality Reduction as a Defense against Evasion Attacks on Machine Learning Classifiers (2017, background): “[18] propose defenses against optimal attacks designed specifically for tree-based classifiers.”
On the Connection between Differential Privacy and Adversarial Robustness in Machine Learning (2018, methodology): “Attacks have used various norms to quantify the power given to the attacker: the 0-norm [33], 1-norm [19, 6], 2-norm [41, 6, 1], and ∞-norm [12, 44, 6, 1, 25].”
Digital Investigation of PDF Files: Unveiling Traces of Embedded Malware (2017, background): “and provide improved security guarantees [9], [10], [15].”
On the Security of Machine Learning in Malware C&C Detection (2016, methodology): “Kantchelian et al. [2016] propose a method of evading tree ensemble–based classifiers such as boosted trees and random forest.”
On the Suitability of Lp-Norms for Creating and Preventing Adversarial Examples (2018, methodology): “To defend against adversarial examples, prior work has focused on either training more robust deep neural networks (DNNs) that are not susceptible to small perturbations [7, 11, 14, 17, 24, 29, 12], or developing techniques to detect adversarial examples [6, 8, 18, 19, 35].”
Why Do Adversarial Attacks Transfer? Explaining Transferability of Evasion and Poisoning Attacks (2018, background): “We finally remark that non-differentiable learning algorithms, like decision trees and random forests, can be attacked with more complex strategies [17,19] or using gradient-based optimization against a differentiable surrogate learner [31,37].”
Adversarial Generative Nets: Neural Network Attacks on State-of-the-Art Face Recognition (2018, background): “training process with adversarial examples in the hope that the DNN will learn to classify them correctly [20], [29], [34], [59].”