A Geometry-Inspired Decision-Based Attack论文摘要

基本信息

会议/期刊	ICCV
年份	2019
机构	EPFL
一作	Yujia Liu
领域	Adversarial Example, Decision-based Black-box Attack

主要贡献

本文提出了一种新型黑盒对抗样本生成算法qFool。该算法不依赖模型输出的概率分布，仅利用Top-1预测结果就能构造出对抗样本。qFool算法的特点是查询次数较少，其变种qFool-subspace算法还能将对抗样本限制在输入的低频子空间中，在计算上更加高效。

背景

早期工作

对抗样本攻击算法根据攻击设定可分为白盒与黑盒两种。黑盒攻击假设攻击者不知道模型的内部细节（架构、参数、损失、梯度…），仅仅知道模型的输出结果。黑盒攻击又可以细分为Score-based和Decision-based。Scored-based攻击假设攻击者能知道模型输出的各类别概率分布，而Decision-based攻击假设攻击者只知道模型输出的Top1预测结果。

Decision-based黑盒攻击的早期工作包括Additive Gaussian Attack、Boundary Attack等。Additive Gaussian Attack生成的对抗样本对人眼来说太过于明显。Boundary Attack利用神经网络的决策边界的几何性质来构造对抗样本，方法颇为巧妙。Boundary Attack的另一大主要贡献还在于确立了黑盒攻击领域最主流的技术框架：先找到原始对抗样本，再用逼近法找到边界对抗样本，然后利用边界对抗样本的种种性质来寻找新的对抗样本，之后再逼近、寻找、…以此循环往复。

在技术路线上，Decision-based黑盒攻击的难点在于缺少模型的梯度信息（个人认为梯度方向和所谓模型决策边界信息在黑盒对抗领域其实是一回事），而模型的逆梯度方向是构造对抗样本的关键。目前已知的解决这一问题的方法包括Transfer-based和Sample-based。Transfer-based方法根据对抗样本在不同模型之间的迁移性，假设不同模型之间的梯度方向相似，先在本地训练替代模型，然后利用替代模型的梯度来代替未知的目标模型梯度。Sample-based方法利用模型决策边界附近的一些特殊性质，构造边界附近的梯度估计量，然后用蒙特卡洛采样法来计算出梯度的估计。

已有的Decision-based黑盒攻击方法的主要缺陷在于query次数过多，生成一张对抗样本图片普遍需要10000+次查询操作，这在实际攻击场景中是不现实的。在“减少query次数”这一方向上已经有了一些探索性的工作，例如引入主动学习框架、对特征进行筛选和降维等。

本文提出的qFool算法是Decision-based黑盒攻击领域在2019年的重要工作。qFool一方面继承了Boundary Attack的攻击框架，另一方面引入子空间采样的方法创新性地解决了查询次数过高的难题。在实验部分，qFool算法在攻击Google商业图片识别服务时仅用了~1500次查询。

灵感来源

该算法的灵感来源于一篇发表于NIPS2016的对抗样本理论工作：Robustness of classifiers: from adversarial to random noise。早期工作中指出，对抗样本附近的决策边界的曲面很小。

Fawzi et al. [7] have shown that the decision boundary has a quite small curvature in the vicinity of adversarial examples.

根据这一发现，如果在对抗样本附近的决策边界上找到“边界对抗样本”，那么对抗样本的梯度方向与邻近区域的边界对抗样本的梯度方向几乎一样。

因此，只要找到了边界对抗样本（较容易），就可以依循梯度方向来找到附近的对抗样本（较困难）。（把难题简单化）

评价

从查询效率上看，qFool超过了经典的Boundary Attack算法，仅利用~1500次查询就成功地攻击了Google商业图片识别服务。

从实验成果上看，qFool用实验证明了边界对抗样本附近的梯度和邻域内的对抗样本梯度几乎一样的性质，并且验证了在子空间内采样生成对抗扰动这条降维的技术路线确实可行。

2020年的很多黑盒攻击的工作在方案的复杂性和理论的严密性上超越了qFool算法。

细节

算法框架

这里只关心适用最广泛的targeted attack场景，伪代码如下：

输入：原始图片 x_0，目标图片 x_t，每次更新估计量所需的查询次数 nu，控制内循环查询次数的超参数 threshold
输出：对抗样本 x_adv

二分搜索寻找边界对抗样本
while 已消耗查询次数 < 总查询次数：
	为本轮迭代分配查询次数
	while 对抗样本更新幅度满足预设条件 and 总查询次数未耗尽：
    	在边界对抗样本上施加随机扰动（可以在频率子空间上施加扰动），查询 nu 次
        利用内部循环产生的所有查询结果来构造梯度的估计量
        新对抗样本 = 边界对抗样本 + 步长 * 梯度的估计量
        二分搜索，更新新对抗样本
    边界对抗样本 = 新对抗样本

算法中需要详细分析的有三点：

• 怎么估计边界对抗样本上的梯度？
• 总查询次数如何分配？
• 如何在子空间上进行采样？

梯度的估计

假设算法每轮迭代时向模型查询n次，那么每次构造n个随机噪声向量，采样后进行归一化，

$$\{\mathbf{\eta}_i\} \sim N(0, \mathbf{1}_n)$$

将噪声叠加到边界对抗样本P上，得到n个查询结果，

$$z_i = \left\{ \begin{array}{rcl} -1 & f(\mathcal{P}+\mathbf{\eta}_i)=f(\mathbf{x}_0) \\ +1 & f(\mathcal{P}+\mathbf{\eta}_i) \neq f(\mathbf{x}_0) \end{array}\right. , \;\;\; i=1,2,...,n$$

构造边界对抗样本附近的梯度的估计量，

$$\nabla f(\mathcal{x}_0) \approx \nabla f(\mathcal{P}) \approx \mathbf{\xi} = \frac{\sum^n_{i=1}{z_i \mathbf{\eta}_i}} {\|\sum^n_{i=1}{z_i \mathbf{\eta}_i}\|_2}$$

查询次数的分配策略

在理想的情况下，采样次数 n 充分大，采样得到的随机向量在决策边界两遍分布均匀，这样的话，算法利用 n 次查询得到的结果构造的统计量就能精确估计梯度。

但考虑到实际情况中，用户并不知道 n 的合适大小，采样得到的随机向量也可能分布并不充分均匀，就会为后续的梯度估计步骤引入误差，或者产生很大的对抗扰动。

论文还指出，初始对抗样本与原始样本之间的距离对最终生成的对抗样本质量有很大影响，因此算法更希望在前期找到尽可能好的对抗样本。（意味着前几轮的查询总次数更多）

为了避免以上情况，qFool算法提出了一种渐进的、贪心的分配策略：

• 固定每次查询/采样数目为 nu
• 多次查询组成算法的一轮迭代 （每轮迭代的查询次数 = 查询次数 * nu）
• 每轮迭代中，控制生成的扰动大小，控制方法是尽可能生成距离边界对抗样本更近的对抗样本
• 迭代轮数受查询的总次数限制

迭代进行的判定条件具体如下，

$$\frac{\|x^{(i)}_{adv} - \mathcal{P}_i\|}{n^{(i)}} \leq \epsilon \;\; \frac{\|x^{(i-1)}_{adv} - \mathcal{P}_i\|}{n^{(i-1)}} \;\;\;\; and \;\;\;\; \sum^i_{j=0}{n^{(j)}} < n$$

子空间采样

本论文对图像进行离散余弦变换（DCT），变换后的频率图的左上部分表示的是原图的低频部分。

qFool算法在低频部分截取维度大小为 m 的子空间，在这个空间范围内施加对抗扰动，然后用反离散余弦变换（IDCT）还原成对抗图片。

缩小维度让采样得到的随机噪声在决策边界的分布更加均匀，根据随机噪声估计得到的梯度方向也就更加精确，最终可以让生成的对抗扰动更小、更不易被察觉。在subspace内采样所需的查询次数更少。

相比之下，在full space内采样得到的噪声分布得极为稀疏，沿决策边界均匀分布的可能性也更低。