# Robust Decision Trees Against Adversarial Examples

arXiv: https://arxiv.org/abs/1902.10660 · HTML: https://mlsanity.com/paper/1902.10660/

## Key facts

- Cited by 40 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Feb 2019.

## Built on by (most cited first, 30 of 40)

- [Trustworthy AI: A Computational Perspective](https://mlsanity.com/paper/2107.06641/) (2021)
- [A Review of Formal Methods applied to Machine Learning](https://mlsanity.com/paper/2104.02466/) (2021)
- [Certifying Robustness to Programmable Data Bias in Decision Trees](https://mlsanity.com/paper/2110.04363/) (2021)
- [SoK: Explainable Machine Learning for Computer Security Applications](https://mlsanity.com/paper/2208.10605/) (2022)
- [Connecting Interpretability and Robustness in Decision Trees through Separation](https://mlsanity.com/paper/2102.07048/) (2021)
- [Adversarial Robustness for Tabular Data through Cost and Utility Awareness](https://mlsanity.com/paper/2208.13058/) (2022)
- [Adaptative Perturbation Patterns: Realistic Adversarial Learning for Robust Intrusion Detection](https://mlsanity.com/paper/2203.04234/) (2022)
- [Individually Fair Gradient Boosting](https://mlsanity.com/paper/2103.16785/) (2021)
- [Robust Optimal Classification Trees Against Adversarial Examples](https://mlsanity.com/paper/2109.03857/) (2021)
- [Towards Adversarial Realism and Robust Learning for IoT Intrusion Detection and Classification](https://mlsanity.com/paper/2301.13122/) (2023)
- [SoK: Realistic Adversarial Attacks and Defenses for Intelligent Network Intrusion Detection](https://mlsanity.com/paper/2308.06819/) (2023)
- [Threat Assessment in Machine Learning based Systems](https://mlsanity.com/paper/2207.00091/) (2022)
- [A.I. Robustness: a Human-Centered Perspective on Technological Challenges and Opportunities](https://mlsanity.com/paper/2210.08906/) (2022)
- [Learning Decision Trees and Forests with Algorithmic Recourse](https://mlsanity.com/paper/2406.01098/) (2024)
- [(De-)Randomized Smoothing for Decision Stump Ensembles](https://mlsanity.com/paper/2205.13909/) (2022)
- [Fair Training of Decision Tree Classifiers](https://mlsanity.com/paper/2101.00909/) (2021)
- [Beyond Robustness: Resilience Verification of Tree-Based Classifiers](https://mlsanity.com/paper/2112.02705/) (2021)
- [Des-q: a quantum algorithm to provably speedup retraining of decision trees](https://mlsanity.com/paper/2309.09976/) (2023)
- [Verifiable Learning for Robust Tree Ensembles](https://mlsanity.com/paper/2305.03626/) (2023)
- [Robustness Verification for Knowledge-Based Logic of Risky Driving Scenes](https://mlsanity.com/paper/2312.16364/) (2023)
- [Adversarial Attack and Defense for Non-Parametric Two-Sample Tests](https://mlsanity.com/paper/2202.03077/) (2022)
- [Provably Adversarially Robust Nearest Prototype Classifiers](https://mlsanity.com/paper/2207.07208/) (2022)
- [Learning Optimal Classification Trees Robust to Distribution Shifts](https://mlsanity.com/paper/2310.17772/) (2023)
- [Coevolutionary Algorithm for Building Robust Decision Trees under Minimax Regret](https://mlsanity.com/paper/2312.09078/) (2023)
- [Data-Aware and Scalable Sensitivity Analysis for Decision Tree Ensembles](https://mlsanity.com/paper/2602.07453/) (2026)
- [Transferable Adversarial Robustness for Categorical Data via Universal Robust Embeddings](https://mlsanity.com/paper/2306.04064/) (2023)
- [Interpretable Differencing of Machine Learning Models](https://mlsanity.com/paper/2306.06473/) (2023)
- [Faster Repeated Evasion Attacks in Tree Ensembles](https://mlsanity.com/paper/2402.08586/) (2024)
- [Cultivating Archipelago of Forests: Evolving Robust Decision Trees through Island Coevolution](https://mlsanity.com/paper/2412.13762/) (2024)
- [Soft regression trees: a model variant and a decomposition training algorithm](https://mlsanity.com/paper/2501.05942/) (2025)

## Abstract (arXiv)

Although adversarial examples and model robustness have been extensively studied in the context of linear models and neural networks, research on this issue in tree-based models and how to make tree-based models robust against adversarial examples is still limited. In this paper, we show that tree based models are also vulnerable to adversarial examples and develop a novel algorithm to learn robust trees. At its core, our method aims to optimize the performance under the worst-case perturbation of input features, which leads to a max-min saddle point problem. Incorporating this saddle point objective into the decision tree building procedure is non-trivial due to the discrete nature of trees --- a naive approach to finding the best split according to this saddle point objective will take exponential time. To make our approach practical and scalable, we propose efficient tree building algorithms by approximating the inner minimizer in this saddle point problem, and present efficient implementations for classical information gain based trees as well as state-of-the-art tree boosting models such as XGBoost. Experimental results on real world datasets demonstrate that the proposed algorithms can substantially improve the robustness of tree-based models against adversarial examples.