Robustness Verification of Tree-based Models

Abstract

We study the robustness verification problem for tree-based models, including decision trees, random forests (RFs) and gradient boosted decision trees (GBDTs). Formal robustness verification of decision tree ensembles involves finding the exact minimal adversarial perturbation or a guaranteed lower bound of it. Existing approaches find the minimal adversarial perturbation by a mixed integer linear programming (MILP) problem, which takes exponential time so is impractical for large ensembles. Although this verification problem is NP-complete in general, we give a more precise complexity characterization. We show that there is a simple linear time algorithm for verifying a single tree, and for tree ensembles, the verification problem can be cast as a max-clique problem on a multi-partite graph with bounded boxicity. For low dimensional problems when boxicity can be viewed as constant, this reformulation leads to a polynomial time algorithm. For general problems, by exploiting the boxicity of the graph, we develop an efficient multi-level verification algorithm that can give tight lower bounds on the robustness of decision tree ensembles, while allowing iterative improvement and any-time termination. OnRF/GBDT models trained on 10 datasets, our algorithm is hundreds of times faster than the previous approach that requires solving MILPs, and is able to give tight robustness verification bounds on large GBDTs with hundreds of deep trees.

Hongge Chen and Huan Zhang contributed equally

References in corpus (19)

• ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Models
• Towards Deep Learning Models Resistant to Adversarial Attacks
• Transferability in Machine Learning: from Phenomena to Black-Box Attacks using Adversarial Samples
• Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examples
• Delving into Transferable Adversarial Examples and Black-box Attacks
• Provable defenses against adversarial examples via the convex outer adversarial polytope
• Robust Physical-World Attacks on Deep Learning Models
• Adversarial Risk and the Dangers of Evaluating Against Weak Attacks
• Evaluating Robustness of Neural Networks with Mixed Integer Programming
• Verifiable Reinforcement Learning via Policy Extraction
• A Unified View of Piecewise Linear Neural Network Verification
• A Convex Relaxation Barrier to Tight Robustness Verification of Neural Networks
• Structured Adversarial Attack: Towards General Implementation and Better Interpretability
• Evasion and Hardening of Tree Ensemble Classifiers
• GPU-acceleration for Large-scale Tree Boosting
• Robust Decision Trees Against Adversarial Examples
• Formal Verification of Input-Output Mappings of Tree Ensembles
• Formal Verification of Decision-Tree Ensemble Model and Detection of its Violating-input-value Ranges
• Verifying Aircraft Collision Avoidance Neural Networks Through Linear Approximations of Safe Regions

Cited by in corpus (3)

• A Review of Adversarial Attack and Defense for Classification Methods
• Cost-Aware Robust Tree Ensembles for Security Applications
• An Efficient Adversarial Attack for Tree Ensembles