Research map / Adversarial robustness and security / Certified and empirical robustness
Faster Repeated Evasion Attacks in Tree Ensembles
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Speeds up repeated evasion attacks on tree ensembles by identifying a small, statistically validated set of frequently perturbed features and pruning the ensemble to those features (with a fallback to the full search for guarantees).
Problem
Generating adversarial examples for tree ensembles is NP-hard and expensive, and it is typically repeated for many examples, yet existing methods solve each instance from scratch.
Approach
Adversarial examples for a fixed tree ensemble tend to perturb the same small set of features; learn this set from previously generated examples, prune the ensemble to those features for faster search, and fall back to the full search on UNSAT/timeout (mixed setting), with a hypergeometric-based test choosing the subset size.
Key results
- Pruned setting speeds up kantchelian by 2.4x-25.4x and veritas by 1.6x-35.9x across datasets and ensemble types.
- Mixed setting (guaranteed to find an adversarial example if full search can) gives 1.6x-7.1x speedup for kantchelian and 1.0x-4.5x for veritas.
- Empirical false negative rate averages 6.4% (max 11.8%), below the 25% theoretical bound; the selected feature subset averages 19.1% of features.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Restrict adversarial perturbations to frequently modified features and prune the ensemble (ablation) | Kantchelian and Veritas attacks on XGBoost and random forests · Ten classification datasets; 10,000 test examples | run time: 2.4x-25.4x; 1.6x-35.9x | Helped |
| Use a pruned search first, then fall back to the full search for UNSAT or timeout (ablation) | Kantchelian and Veritas attacks on XGBoost and random forests · Ten classification datasets; 10,000 test examples | run time: 1.6x-7.1x; 1.0x-4.5x | Helped |
| Use the mixed strategy rather than pruned-only search (ablation) | Kantchelian and Veritas on random forests · higgs and other RF datasets | run time: 1.0×; 1.1× | Mixed |
| Restrict the search to a selected feature subset (ablation) | Pruned attack setting · Ten classification datasets | false negative rate: 6.4%; 11.8% | Hurt |
| Use the mixed strategy to fall back to full search when pruned search cannot return an adversarial example (ablation) | Adversarial accuracy evaluation · Tree-ensemble test examples | adversarial accuracy | No clear effect |
| Use pruned or mixed search instead of full Kantchelian search (ablation) | Empirical robustness estimation · Tree-ensemble test examples | empirical robustness | Hurt |
Surprising findings
- Full kantchelian on random forests hit the six-hour global timeout on several datasets, so some examples were skipped.
Limitations
- Pruned setting can return false negatives (UNSAT while full search finds SAT), so the mixed fallback is needed for guarantees.
- Mixed setting can produce overestimated empirical robustness with exact kantchelian.
- Random forests are harder to attack; pruned search often times out on them.
Experimental setup
Datasets: covtype fmnist higgs miniboone mnist prostate roadsafety sensorless vehicle webspam
Benchmarks: covtype fmnist higgs miniboone mnist prostate roadsafety sensorless vehicle webspam
Metrics: run time speedup false negative rate empirical robustness
Baselines: kantchelian full search veritas full search
Builds on: kantchelian attack veritas XGBoost random forest
Closest papers by meaning
- An Efficient Adversarial Attack for Tree Ensembles (NeurIPS 2020 · similarity 0.91)
- Evasion and Hardening of Tree Ensemble Classifiers (ICML 2016 · similarity 0.89)
- Robustness Verification of Multi-Class Tree Ensembles (AAAI 2024 · similarity 0.88)
- Robust Decision Trees Against Adversarial Examples (ICML 2019 · similarity 0.88)
- Rethinking Model Ensemble in Transfer-based Adversarial Attacks (ICLR 2024 · similarity 0.85)
- Understanding Model Ensemble in Transferable Adversarial Attack (ICML 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.