Evasion and Hardening of Tree Ensemble Classifiers

Abstract

Classifier evasion consists in finding for a given instance $x$ the nearest instance $x^{\prime }$ such that the classifier predictions of $x$ and $x^{\prime }$ 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.

11 pages, 7 figures, Appears in Proceedings of the 33rd International Conference on Machine Learning (ICML), New York, NY, USA, 2016. JMLR: W&CP volume 48

References in corpus (2)

• Towards Deep Neural Network Architectures Robust to Adversarial Examples
• Efficient non-greedy optimization of decision trees

Cited by in corpus (32)

• Wild Patterns: Ten Years After the Rise of Adversarial Machine Learning
• A General Framework for Adversarial Examples with Objectives
• DARTS: Deceiving Autonomous Cars with Toxic Signs
• Practical Black-Box Attacks against Machine Learning
• Why Do Adversarial Attacks Transfer? Explaining Transferability of Evasion and Poisoning Attacks
• Malware Makeover: Breaking ML-based Static Analysis by Modifying Executable Bytes
• Robustness Verification of Tree-based Models
• Provably Robust Boosted Decision Stumps and Trees against Adversarial Attacks
• A Theoretical Framework for Robustness of (Deep) Classifiers against Adversarial Examples
• Learning Security Classifiers with Verified Global Robustness Properties
• A General Retraining Framework for Scalable Adversarial Classification
• Adversarial Detection of Flash Malware: Limitations and Open Issues
• Improving Robustness of ML Classifiers against Realizable Evasion Attacks Using Conserved Features
• Evaluating the Robustness of Nearest Neighbor Classifiers: A Primal-Dual Perspective
• Embedding and Extraction of Knowledge in Tree Ensemble Classifiers
• Not All Datasets Are Born Equal: On Heterogeneous Data and Adversarial Examples
• Cost-Aware Robust Tree Ensembles for Security Applications
• Better the Devil you Know: An Analysis of Evasion Attacks using Out-of-Distribution Adversarial Examples
• On Training Robust PDF Malware Classifiers
• $n$-ML: Mitigating Adversarial Examples via Ensembles of Topologically Manipulated Classifiers
• Spanning Attack: Reinforce Black-box Attacks with Unlabeled Data
• Resilient Linear Classification: An Approach to Deal with Attacks on Training Data
• Connecting Interpretability and Robustness in Decision Trees through Separation
• A Review of Formal Methods applied to Machine Learning
• On ${\ell }_p$-norm Robustness of Ensemble Stumps and Trees
• Versatile Verification of Tree Ensembles
• When are Non-Parametric Methods Robust?
• Towards adversarial robustness with 01 loss neural networks
• Defending Against Adversarial Attacks Using Random Forests
• Enhancing Transformation-based Defenses using a Distribution Classifier
• BOSH: An Efficient Meta Algorithm for Decision-based Attacks
• Where Does the Robustness Come from? A Study of the Transformation-based Ensemble Defence