论文解读-Hybrid Batch Attacks: Finding Black-box Adversarial Examples with Limited Queries (USENIX‘20)
Hybrid Batch Attacks: Finding Black-box Adversarial Examples with Limited Queries
这篇文章是我在组会上汇报的一篇论文，这篇文章比较不错，因此我的笔记也更详细一些，如有借鉴请注明出处，谢谢。
本文作者针对黑盒攻击提出了混合攻击，将黑盒攻击两类主要的攻击方法结合起来，极大地降低了攻击成本，同时提升了成功率。此外作者针对更符合实际的场景提出了Hybrid Batch Attack，使得攻击者可以用极低得查询成本得到一定数量的对抗样本。同时攻击过程中的副产物用来fine-tuning本地模型，更接近目标模型。
Introduction
正常的样本有目的、有约束的加上一些扰动可能就会使得机器学习模型产生错误分类，这种样本就是对抗样本。高效的寻找对抗样本的方法是在白盒条件下，但是如果是在黑盒条件中，一般只有API接口可以调用，这就导致攻击的代价很高，因为调用接口有时间、数量和费用限制。黑盒攻击的难点，但是同时这也是黑盒攻击优势点，因为一般大家觉得我只要把模型部署在云上只提供API接口，我只要做好web安全，我的模型就一定是安全的了，会给人一种错误的安全感。
目前黑盒攻击主要可以划分为两类：transfer attacks 和optimization attacks 。首先就是模型可以在不同的数据集上迁移学习，反过来对抗样本也经常会在不同的模型上迁移。【比如图像分类模型就20种以内】所以攻击者可以在本地模型上利用白盒攻击生成对抗样本，然后希望迁移到目标模型上。因为本地模型的对抗样本可能无法成功转移到目标模型，所以这个transfer loss就会很高，特别是对于有目标的攻击，攻击者的目标是要找出模型输出到某一特定错误类别的对抗样本，而不是仅仅是分错就可以了。
Optimization attacks是将攻击目标制定为黑盒优化问题，针对目标模型使用一系列大量的查询来攻击，有很高的成功率，但是因为用到的查询太多，所以代价很高。
本文尝试了三种把二者结合起来的方法，发现确实有一种方法可以把transfer attack和optimization attack结合起来，可以大幅提高黑盒攻击成功率同时降低查询代价。他发现迁移攻击失败的样本是optimization attack攻击很好的起始样本 。
Background
Transfer Attacks
迁移攻击利用了对抗样本也在不同模型上迁移的性质。攻击者在本地模型上开展标准的白盒攻击获得对抗样本，然后希望迁移到目标模型上。大部分工作假设攻击者可以接触到相似的训练数据或者基于相似数据分布的预训练模型。如果有预训练模型的话就不用查询目标函数来训练本地模型了。否则需要通过查询目标模型来训练本地模型，也被称为 substitute training 。需要很多查询才能替代训练一个有用的本地模型，而且对于复杂模型效果有限。
还有一种增强迁移攻击的方法是修改在本地模型上的白盒攻击。比如动量方法、攻击输入多样性、平移不变优化。
Optimization Attacks
optimization-based attacks通过定义一个目标函数，然后迭代的扰动输入来优化目标函数。这要求对目标模型的查询会返回一个完整的预测得分，然后区分出哪些设计估计目标函数的梯度，哪些不依赖估计梯度。
梯度攻击
基于梯度的黑盒攻击在数值上估计目标模型的梯度，并用其执行标准的白盒攻击。
这一类代表是ZOO(zeroth-order optimization)attack，通过有限差分，利用数值方法去估计梯度，从而去改变输入，但是查询次数太多了。很多基于此的工作(ZOO+PCA、AutoZOOM、NES、Bandits_{TD}、SignHunter等等)都是在想尽办法减少查询次数，提高效率。可以看出ZOO是一种很好的梯度攻击方法，但是效率太低，改善其效率是之后研究者心心念念的事情
无梯度攻击
基于搜索的启发式方法. 效率比基于梯度的还差.
更严格的黑盒攻击
目标模型不返回全部概率, 仅返回最高的几个置信分数或者just label. 针对这个问题最朴素的方法是从目标样本出发random walk.
Hybrid Attacks
首先假设本地可以预训练一个类似的模型，可以用类似的训练数据。作者提出本文的三个假设：
- 本地模型的对抗样本相对于原始种子，是optimization attacks更好的起始点。 不同的模型往往会有相似的分类边界，因此假设尽管在本地模型上的对抗样本可能不能迁移到目标模型上，但这些样本仍然更加接近分类边界，是更好的攻击起始点
- optimization attacks学到的标签可以来tune本地模型。生成横跨本地模型分类边界的样本可以训练本地模型更接近目标模型。因此优化搜索查询的结果可能包含更丰富的信息，比如真是目标决策边界。这些新标记的输入是优化攻击的副产品，可以用来微调本地模型来提高其可迁移性。
- 本地模型可以帮助梯度搜索。因为对于相同的分类任务，不同的模型往往会有相似的分类边界，因此假设本地模型的梯度信息可能帮助校准梯度估计。
攻击方法
基于前两种假设，通过两种方式结合迁移攻击和优化攻击：
结合流程图理解Hybrid Attack的算法：
选一张种子在本地模型上白盒攻击，然后将本地模型的上的对抗样本迁移到目标模型上，如果迁移攻击成功了就成功了，如果失败了这个样本就是优化攻击的起始点（种子图像也要传进模型？）。不管黑盒攻击成功与否，攻击期间得到的标签都可以用来微调本地模型。
实验评价
本地模型是Ensemble模型，可以提高迁移率、减少查询。
白盒攻击用PGD。
优化攻击用NES和AutoZOOM。
有目标攻击就以预测概率最低的类别作为目标。对于robust models用无目标攻击，因为这些模型旨在防御无目标攻击。
攻击距离度量和幅度
用L_{\infty}来衡量扰动距离，这是黑盒对抗攻击研究中最常用的强度指标。AutoZOOM是L_2攻击，通过在每次优化迭代中，将被攻击的图像剪切到原始种子的\epsilon-ball(L_1)空间中 。L_2是欧氏距离，就是两个样本/图像之间的欧式距离；L_{\infty} 是极大值，就是两个样本之间每一维差值的最大值。
本地模型候选项结果
相较于直接用原始种子进行黑盒攻击，在本地模型的对抗样本的基础上进行黑盒攻击，效率大大提高，对于AutoZOOM-Normal MNIST model，总体成本降低了多达81%，对于Auto-ZOOM和NES在Normal model上，成本至少降低了三分之一。成本降低有两个原因：一是一些样本直接迁移成功了，这样查询成本是1；二是没有迁移成功的样本是梯度攻击很有用的起始点。最后两列可以看出来。也存在worse than original seed。
攻击鲁棒模型
对鲁棒模型提升不大。可能是因为普通模型和鲁棒模型在vulnerability space上不同。这也符合Tsipras等人的发现：用于图像分类任务的鲁棒模型捕获图像的关键特征，而普通模型捕获相对嘈杂的特征。因此针对鲁棒模型的对抗样本就要扰动关键特征(目标区域)，而只干扰无关特征就可以攻击正常模型。那么将本地模型也换成鲁棒模型，可以发现，鲁棒模型攻击鲁棒模型效果好，普通模型攻击普通模型效果好：
但是鲁棒模型攻击普通模型效果就很差，这也印证了二者有不同的攻击平面，不在同一个空间里。
那是不是超大Ensemble模型？
Ensemble模型不能同时对正常目标模型和鲁棒正常模型有高迁移率，或者有时候是中间值。一个可能的原因是白盒攻击是用在mixed ensembles上的，攻击会focus在普通模型上因为普通模型更易攻击(比如可以很显著的降低损失函数)，从而更偏向普通函数，从而对抗样本不怎么会迁移到鲁棒模型上。这一点可以从途中看出来，即使模型混合了普通和鲁棒模型，它仍然偏向普通模型的迁移率，对鲁棒模型的迁移率反而降低了。可以用下图来解释：
作者在这也说了，如何偏向Ensemble模型中的鲁棒模型也是一个有趣的问题。
在实践中，攻击者可以根据观察动态调整本地模型，在第一次尝试时，针对特定目标使用不同的本地Ensemble，测试迁移效果，然后选择最合适的。
微调本地模型
在黑盒攻击期间，生成了两类不同的input-label pairs。一类是通过对当前图像随机添加小噪音来估计目标模型梯度得到的；一类是在沿着估计得到的梯度的方向进行扰动时得到的。因为被扰动的图像是沿着决策边界的方向移动的，
所以后者(左图中绿框内)包括目标模型边界更丰富的信息。
扰动图像及其标签加入训练数据集进行Fine-tuning，数据多了就采样训练。
理论上对每一个种子样本混合攻击结束后，都应该更新一次模型，但是减少开销，定期更新，比如50、100个种子之后。
两个实验来测试微调效果：
- 假设2，检查本地模型的成功率会不会因为fine-tuning提高。这个实验可以帮助检查假设2的适用性，排除其他假设的干扰。
- 假设2和假设3，评估平均查询开销和攻击成功率有没有变化，从而评估攻击者结合混合攻击，可以从fine-tuning过程获益多少。
结果如下，在MNIST模型上效果有提升，但是在CIFAR上效果剧烈下降：
第二个实验：
对于Normal MNIST模型，提升幅度似乎比第一个实验大一些，所以可能是将本地的对抗样本作为对抗样本起点的促进效果。（不讲吧）通过利用混合攻击过程的副产品，针对MNIST模型的攻击成本显著降低了。还有一个现象，本地模型根据鲁棒模型fine-tuning之后也变得越来越鲁棒，例如：对本地模型NES攻击的成功率从96.6%降到了25.2%，这显示微调后的本地模型更抵抗PGD攻击。
作者还是无法解释为什么CIFAR10模型降低这么多。一个猜测是可能与训练CIFAR10模型的困难有关：基于梯度攻击返回的结果与特定种子高度相似，并且可能不够多样化，无法训练有效本地模型。MNIST模型倾向于从outliers（非自然图像）中学习，而更现实的数据集如CIFAR10倾向于从个更多prototypical（自然）示例中学习。因此CIFAR10模型的标签副产品更可能是outliers，会降低学习效果。
Batch Attack
前面讲的攻击都是假设我有一个固定的种子集，然后我想对这里的每一个种子都攻击成功。但是这样很容易被检测出来攻击意图，在实际攻击中没必要这样做，我们为了获得尽可能多的对抗样本，所以应该优先找出容易攻击的种子。（下图中灰色的样本点）
这里的优先策略的实现方式就是把算法中的selectSeed函数换成: \underset{\mathbf{x} \in \mathbf{X}}{\arg \min }EstimatedAttack \operatorname{cost}(\mathbf{x}, F)
Hybrid Batch Attack可以分为两阶段：第一阶段，利用本地模型的信息**（白盒攻击本地模型时的PGD步数）找到可能转移迁移攻击的种子；目标模型的信息 （所有种子对目标模型查询一次，计算Loss）**也用上，来选择优化攻击的候选对象。
第一阶段：迁移攻击
第一阶段是为了迁移攻击，这一阶段同时做两件事情：本地模型PGD攻击找对抗样本来迁移攻击；根据本地模型PGD攻击的难易程度排序对抗样本。假设本地模型越容易找到的对抗样本，那么该样本越可能存在于目标模型的弱点区域内，这里PGD-steps来作为排序策略。
结果： 
第一阶段只检查可迁移性，和优化攻击无关。
如果只是想获得一定数量的对抗样本，比如1000个中的1%，根据优先级查询可迁移性能够显著降低成本。
第二阶段：优化攻击
第一阶段的迁移攻击查询成本低，但是成功率低，不能找到足够的对抗样本，需要在剩下的样本中继续用优化攻击。
可以看出来如果只想要10%的对抗样本，那按这种排序策略，取前10%来优化攻击，查询成本可以降低90%。（前10%样本要查询1522次，但是整个样本集的平均查询次数是14828次）
优先级策略
结果可以看出优先处理一些种子可以降低成本，但是要能够利用这些差异，需要有一种预先识别低成本种子的方法。
只用基于本地模型的排序方法的缺点是：本地模型对成本的估计可能不完全适用于目标模型。因此提出第二种优先级策略，利用对目标模型进行一次查询获得的信息。查询可以得到每个种子的预测分数，然后用来在第二阶段对剩余种子排序。特别的是，低成本种子往往对于目标模型有着较小的Loss。损失函数值小就意味着更接近攻击目标。
举个例子，对于一个输入x, 和想要攻击的类别t，损失函数定义：
l(\mathbf{x}, t)=\left(\max _{i \neq t} \log f(\mathbf{x})_{i}-\log f(\mathbf{x})_{t}\right)^{+}
对于无目标攻击：
l(\mathbf{x}, y)=\max \left(\log f(\mathbf{x})_{y}-\right. \left.\max _{i \neq y} \log f(\mathbf{x})_{i}\right)^{+}
f(x)是预测分数分布，所以f(x)_i是模型对于输入x属于类别i的概率预测。
结果： 比较了两种优先级策略（PGD-steps和target model loss）以及随机选取来验证低开销。(只验证这两个策略)
因为用来攻击的样本是同一批样本，只是一个先选后选的问题，所以图像的终点是收在一起的。可以看到两种方法都好于随机选，用target loss会更好点。这个提升太夸张了。
攻击效果总体比较
和两种退化策略相比：
- retroactive optimal ： 这个是上帝视角，提供一个性能的上限，即假知道每个种子真实的优先级
- random ： 随机选种子，并尽力对每个种子攻击（直至成功或达到查询限制）。这代表了攻击每个种子的传统黑盒攻击方法。
这个时候是只比 target loss、retroactive optimal、random 三种策略在纯黑盒攻击的开销。
但是在ImageNet Model上效果只提升了一点。
对于target loss strategy，完整的两阶段策略（hybrid attack）比baseline attack在ImageNet Model上效果提升好。这可能是因为: baseline attack的攻击出发点是原始种子，即自然照片，而ImageNet往往过拟合这些自然照片。因此在这种情况下target loss在预测其实际攻击成本方面没有太大帮助。相反，hybrid attack的攻击出发点已经是对抗样本了，已经偏离了自然分布，所以ImageNet不太会过拟合，target loss更有帮助。
完整的两阶段混合攻击与上帝视角、随机选取策略对比：
（上帝视角前半部分基本是线性的，因为他可以直接1次选出迁移样本）两阶段策略几乎已经和上帝视角差不多了。几乎可以把下图中灰色样本点优先选择出来攻击：
