Robust Decision Trees Against Adversarial Examples

Abstract

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.

Cited by in corpus (15)

• Adaptative Perturbation Patterns: Realistic Adversarial Learning for Robust Intrusion Detection
• Robustness Verification of Tree-based Models
• Opportunities and Challenges in Deep Learning Adversarial Robustness: A Survey
• Walling up Backdoors in Intrusion Detection Systems
• Embedding and Extraction of Knowledge in Tree Ensemble Classifiers
• Towards Security Threats of Deep Learning Systems: A Survey
• Not All Datasets Are Born Equal: On Heterogeneous Data and Adversarial Examples
• Cost-Aware Robust Tree Ensembles for Security Applications
• An Efficient Adversarial Attack for Tree Ensembles
• Spanning Attack: Reinforce Black-box Attacks with Unlabeled Data
• A Review of Formal Methods applied to Machine Learning
• Versatile Verification of Tree Ensembles
• On ${\ell }_p$-norm Robustness of Ensemble Stumps and Trees
• BOSH: An Efficient Meta Algorithm for Decision-based Attacks
• Certifying Robustness to Programmable Data Bias in Decision Trees