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

本研究提出针对树集合算法的两种新型分类器干扰算法，第一种算法使用 Mixed Integer Linear Program 求解器寻找在一定约束条件下的最优干扰实例，第二种算法通过基于符号预测的快速有限差分方法在速度和准确性之间进行权衡。在数字识别任务中，该研究证明了提升树和随机森林算法极易受到干扰，并通过增加干扰实例的训练集来提高提升树的鲁棒性，不会对其分类准确性造成影响。