Source-linked AI summary
Evasion and Hardening of Tree Ensemble Classifiers
Alex Kantchelian, J. D. Tygar, Anthony D. Joseph
TL;DR
The paper addresses how to systematically find nearby inputs that change tree-ensemble predictions and assess their robustness. It develops exact and approximate evasion algorithms, then shows tree ensembles are highly susceptible while adversarial boosting hardens boosted trees without accuracy loss.
Problem
Small perturbations can change model predictions, creating robustness concerns and security risks for machine-learning applications where attackers seek cost-effective evasions.
Method
The paper combines MILP-based optimal evasion, symbolic-prediction-based approximate evasion, and adversarial boosting using evading instances during training.
Results
Gradient boosted trees and random forests are extremely susceptible to evasions, while adversarial boosting produces a significantly harder-to-evade model without sacrificing accuracy.
Takeaways & Limitations
The algorithms provide systematic robustness assessments for tree ensembles, and adversarial boosting can harden boosted trees on the benchmark task.
Takeaways & Limitations
Efficiently solving all evasion instances is not expected unless P = NP, and exact MILP solving can take significant time on difficult models.
Abstract
from arXiv · showhide
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.
1. Introduction
The paper addresses the largely overlooked evasion of tree ensembles, developing exact and approximate methods to measure and generate evasions. On handwritten digit classification, tree ensembles are consistently brittle, while adversarial boosting hardens boosted trees without sacrificing accuracy.
- Small perturbations can cause correctly classified inputs to receive inaccurate predictions, revealing brittleness in contemporary classifiers.
- Evasion matters because robust generalization should require sufficiently large changes, while attackers seek small, cost-effective modifications in security applications.
- Prior evasion research focused mainly on differentiable models and L2 distance, leaving non-differentiable tree ensembles comparatively understudied.
- On handwritten digit classification, boosted trees and random forests are consistently the most brittle models despite competitive accuracy, while adversarial boosting improves robustness without accuracy loss.
- The approximate algorithm uses symbolic prediction to compute fast finite differences and generate evading instances for adversarial boosting.
2. Related Work
The paper extends evasion analysis beyond the mainly differentiable models studied previously and contrasts its tree-ensemble methods with related neural-network hardening ideas. It reports that adversarial boosting increases robustness without reducing accuracy.
- Before this work, evasion studies largely targeted linear or differentiable models, with only one cited study addressing tree ensembles through a genetic algorithm for malicious PDFs.
- The authors work directly in feature space to measure intrinsic model robustness and provide guaranteed worst-case lower bounds, unlike application-specific feature extraction settings.
- Despite their extreme non-linearity, boosted trees are reported as more susceptible to evasion than neural networks.
- Adversarial boosting produces increased robustness for boosted trees without degrading accuracy and yields the most robust model in the benchmark problem.
3. The Optimal Evasion Problem
The optimal evasion problem seeks the nearest input that changes a classifier's prediction, with the distance function defining the attack cost and robustness notion. The paper studies four feature-decomposable distances and notes a binary-feature degeneracy.
- Given classifier c, instance x, and distance d, optimal evasion finds an x′ minimizing d(x, x′) subject to c(x) ≠ c(x′).
- The formal setting considers binary classifiers over an n-dimensional feature space, with Y = {−1, 1} and X ⊂ R^n.
- The distance function represents the attacker's feature-change cost and determines the resulting notion of d-evasion or d-robustness.
- The analysis assumes costs decompose over feature dimensions and evaluates four representative distances with different deformation patterns.
- L0 or Hamming distance favors sparse, localized changes with arbitrary magnitude, and the optimal algorithm supports non-uniform feature costs.
- L1 and L2 encourage localized small changes, whereas L∞ favors uniformly distributed changes with the smallest possible magnitude.
- For binary-valued features, L1 and L2 reduce to L0 and L∞, producing the trivial solution value 1.
4. Evading Tree Ensemble Models
This section formalizes evasion for tree ensembles, proves its worst-case computational hardness, and develops exact MILP and approximate algorithms. The approximate method uses symbolic prediction to reduce search complexity while targeting single-feature changes.
- Model and problem: Sum-ensembles combine binary regression trees whose threshold predicates determine paths to numerical leaf predictions.The paper restricts predicates to single-feature thresholds, excluding oblique trees.
- Theoretical hardness: Finding an input with a specified sign under a tree ensemble is NP-complete, so optimal evasion contains an NP-complete feasibility subproblem.The hardness proof reduces from 3-SAT by encoding assignments in feature values and clauses as regression trees.
- Optimal evasion: The exact algorithm reduces optimal evasion to a Mixed Integer Linear Program without big-M constraints and supports multiple Lp distances.Predicate, leaf, and optional bound variables encode consistency, active leaves, and the L∞ objective.
- Optimal evasion: Predicate-consistency constraints enforce implications among thresholds over the same feature, preventing logically inconsistent predicate assignments.For K sorted thresholds on one feature, the formulation uses K −1 implication inequalities.
- Approximate evasion: O(|f| log |f|) symbolic prediction improves exponentially over brute-force search for the approximate single-feature optimization subproblem.The method tracks feasible dimension-interval-prediction tuples through each tree and selects the largest score variation.
5. Results
The evaluation benchmarks tree ensembles on MNIST digit classification and compares their evasion robustness with several alternative models. It also examines adversarial boosting as a hardening strategy for boosted trees.
- 5.1. Dataset and Method: The benchmark uses binary MNIST classification of handwritten “2” versus “6”, with 11,876 training images, 1,990 testing images, and 100 jointly correctly classified evaluation instances.Each image has 28×28 grayscale pixels, represented in a 784-dimensional feature space.
- 5.2. Considered Models: Seven models are benchmarked, including boosted decision trees, random forests, regularized linear models, an RBF-SVM, a neural network, and convex polytope machines.BDT uses XGBoost, RF uses scikit-learn, and the testing-set error rates are summarized in Table 1.
- 5.3. Robustness: Across all deformation metrics, boosted trees and random forests rank near the bottom for robustness despite competitive accuracy.The comparison evaluates optimal or best-effort evasion bounds over 100 correctly classified evaluation instances.
- 5.3. Robustness: Negligible L1 or L2 perturbations suffice to evade the tree ensembles, while RBF-SVM is reported as the hardest model to evade.NN and CPM show similar robustness, and the L1-regularized linear model is more brittle than its L2 counterpart.
- 5.4. Hardening by Adversarial Boosting: Adversarial boosting augments each boosting round with freshly generated evading instances and their correct labels, doubling the training set for that round.The symbolic prediction-based procedure generated more than 11 million adversarial instances across 1,000 rounds while training on no more than 24,000 instances at a time.
- 5.4. Hardening by Adversarial Boosting: The hardened BDT-R has slightly higher testing accuracy than BDT and is more robust to L0 evasions, but is more sensitive to L1, L2, and L∞ evasions.The MILP solver did not finish the optimal search after one day; the reported bound used a fast-evasion warm start and one hour of solver search.
6. Conclusion
The paper presents exact and approximate algorithms for computing tree-ensemble evasions and demonstrates substantial susceptibility of boosted trees and random forests. Adversarial boosting produces models that are harder to evade without sacrificing accuracy, while its success across datasets remains unknown.
- 6. Conclusion: The paper presents one exact and one approximate algorithm for systematically computing evasions of boosted trees and random forests.The exact method targets optimality, while the approximate method prioritizes speed.
- 6. Conclusion: On a digit recognition task, both gradient boosted trees and random forests are extremely susceptible to evasions.
- 6. Conclusion: Adversarial boosting trains models that are hard to evade without sacrificing accuracy.
- 6. Conclusion: Whether adversarial boosting succeeds on all possible datasets remains unknown.The authors identify understanding this hardening approach as a future-work direction.