An Efficient Adversarial Attack for Tree Ensembles

Abstract

We study the problem of efficient adversarial attacks on tree based ensembles such as gradient boosting decision trees (GBDTs) and random forests (RFs). Since these models are non-continuous step functions and gradient does not exist, most existing efficient adversarial attacks are not applicable. Although decision-based black-box attacks can be applied, they cannot utilize the special structure of trees. In our work, we transform the attack problem into a discrete search problem specially designed for tree ensembles, where the goal is to find a valid "leaf tuple" that leads to mis-classification while having the shortest distance to the original input. With this formulation, we show that a simple yet effective greedy algorithm can be applied to iteratively optimize the adversarial example by moving the leaf tuple to its neighborhood within hamming distance 1. Experimental results on several large GBDT and RF models with up to hundreds of trees demonstrate that our method can be thousands of times faster than the previous mixed-integer linear programming (MILP) based approach, while also providing smaller (better) adversarial examples than decision-based black-box attacks on general ${\ell }_p$ ($p=1,2,\infty$) norm perturbations. Our code is available at https://github.com/chong-z/tree-ensemble-attack.

arXiv commentNeurIPS 2020

References in corpus (12)

• Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms
• Intriguing properties of neural networks
• ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Models
• Searching for Exotic Particles in High-Energy Physics with Deep Learning
• Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examples
• Black-box Adversarial Attacks with Limited Queries and Information
• Guessing Smart: Biased Sampling for Efficient Black-Box Adversarial Attacks
• GPU-acceleration for Large-scale Tree Boosting
• Robust Decision Trees Against Adversarial Examples
• Robustness Verification of Tree-based Models
• Provably Robust Boosted Decision Stumps and Trees against Adversarial Attacks
• AutoZOOM: Autoencoder-based Zeroth Order Optimization Method for Attacking Black-box Neural Networks