本文为本周讨论班分享论文，特此记录

文章链接

概述

本文发表在USENIX 21，作者来自哥伦比亚大学，通讯作者为Jana Suman。文章提出了使用领域知识构建树集成（Tree ensemble）分类算法的，开销驱动的feature的建模，同时提出新的训练算法，旨在根据建模的结果构建更加鲁棒的树集成分类模型，提高攻击者调整feature攻击模型的开销。

相比于不使用feature训练的普通模型和使用了切比雪夫距离（$L_p$ norm distance）来说，在4个数据集中可以做到提高攻击者的最小攻击成本（使用切比雪夫距离衡量），面对攻击时能够维持一个比较高的准确率，同时相比前人的具有鲁棒性的训练算法来说作者提出的算法在准确率和误报率上能够有一个更好的结果；在实际的安全应用场景中，作者使用了推特的垃圾链接分类任务进行验证，最好能够提高攻击者10.6倍的攻击成本。

背景

  • 决策树可以用来构建分类任务，从根节点出发根据输入的特征（features）选择左右子树，最终到达一个叶子节点作为输入特征的预测结果；
  • 树集成是决策树预测结果的聚合，常用的聚合方式有取平均（随机森林，Random Forest）以及求和（梯度引导的决策树，Gradient Boosted Decision Tree，GBDT）；随机森林以及梯度引导决策树算法是作者在评估中主要使用到的两种树集成算法，前者比后者在处理过拟合方面更加优秀；
  • 树集成算法训练出来的模型对输入的特征向量的值进行分类，攻击者在攻击树集成算法的时候一般通过调整feature使得模型预测错误；

  • 鲁棒性的树集成算法一般通过$L_p$距离来衡量攻击者攻击的开销，同时在训练的时候也会考虑到$L_p$距离来训练更加鲁棒的模型，但是这种衡量的方法在暗含的假设中存在两个问题：

    • 所有特征的调整开销相同

    • 同一个特征调整方向的开销相同

      在安全相关的分类模型中，用来训练的特征明显不满足上述两个假设，如攻击者想要修改特征中的域名或掌握一个新的IP地址两者的开销明显不同，在恶意软件的特征中，想要增加一个特定特征和减少一个特定特征（可能和恶意软件的功能相关）的开销同样不同；

特征开销建模以及算法设计

文章的主要贡献点分成两部分：

  • 对开销进行建模
  • 提出使用开销模型的树集成模型训练方法

开销建模

作者对特征应该考虑的因素进行总结，包括经济性（Economic），功能性（Functionality），可疑性（Suspiciousness），单调性（Monotonicity，指特征调整的方向），攻击使用到的初始种子的属性（Attack seed），根据以上的因素对特征的调整开销进行排序。

特征约束函数将特征值约束到其可以调整的一段区间中（在特征归一化之后），作者使用了两种模型来对调整空间进行建模，包括：

  • 块状模型，对开销的相对大小进行衡量

  • 以及条件模型，根据特征值与极值的接近程度决定调整的空间

鲁棒的训练方法

算法的改进思路从调整树集成算法中决策树的子节点构造方法入手，如下图所示，$\eta$表示构造左右子树时候对某一个特征的分割，使用增益函数（Shannon entropy, Gini impurity, or any general loss function ）对分割的效果进行衡量。

图中不同形状的点表示不同的类别，在上方的图中在$x_4$和$x_5$设置分割可以在没有攻击的情况下达到最高的准确率；但是在受到攻击的情况下，两个数据点的调整空间使得攻击者可以降低模型的准确率，而使用下方的图的分割，可以在受到攻击的情况下保持一个更高的准确率，模型的鲁棒性得到提高。

作者将寻找更加鲁棒性分割的问题转换为一个优化问题，算法的流程就不详细展开了，个人感觉是把可以调整的点逐个加入到左右子树中，计算增益函数的最大值。

结果以及评估

作者的结果评估分成两个部分：

  • 基于前人工作的开销模型，使用本文提出的鲁棒性的算法训练了一个模型，在4个数据集上和一般训练方法训练得到的模型以及前人工作$^1$中的算法中的模型进行比较，比较的维度包括：

    • $L_p$衡量下的攻击者的最小开销
    • 攻击强度提高的情况下模型的准确率变化
    • 相比前人的鲁棒模型在准确率和误报率的变化情况

  • 端到端的安全攻击实验，应用到推特的垃圾链接分类安全任务，在最优的情况下可以使攻击者的攻击开销提高10.6倍；同时根据评估的结果作者指出模型的性能需要通过调整超参来达到更好的效果，并不是一味地假设攻击者的攻击能力越强越能获得更鲁棒的模型。

个人总结

  • 文章能够指出前人用来衡量攻击者攻击条件的$L_p$的不足，即对所有特征一视同仁以及调整的方向一视同仁，这种方式会引入模型训练的结果不够鲁棒；
  • 但是特征的开销模型需要投入很多的人力，这种建模方法不够自动化，这也导致了作者的方法在可扩展性上具有一定的局限；

【1】H. Chen, H. Zhang, D. Boning, and C.-J. Hsieh. Robust de-cision trees against adversarial examples. InInternationalConference on Machine Learning (ICML), 2019.