查询高效的基于决策的黑盒深度学习模型稀疏攻击

查询效率的需求。在基于决策或黑盒设置中，以高攻击成功率实现查询效率对对抗目标至关重要。因为：i) 对手能够大规模发动攻击；ii) 发动攻击的成本降低；iii) 对手能够绕过那些可以采用方法识别恶意活动（基于连续大量相似输入的查询并将其视为欺诈）的系统并挫败其攻击。此外，从防御角度来看，更少的查询次数显著减少了训练模型和防御机制的评估时间。因此，查询高效的攻击算法有助于设计新防御和模型架构的研究，同时通过在大规模部署前评估模型，使机器学习即服务提供商受益。

我们在下面总结我们的贡献和结果：

• 我们提出了一种新的稀疏攻击——SparseEvo——一种基于进化的算法，能够利用仅访问模型的 top-1 预测标签来在模型的输入空间中搜索对抗样本，同时最小化误导模型所需的扰动像素数量。
• 与最先进的对应算法 Pointwise 相比，我们的攻击算法能显著减少模型查询次数。此外，SparseEvo 实现了可比的成功率。

在稀疏攻击中遇到的离散搜索空间阻碍了这些密集攻击算法有效地搜索稀疏对抗样本。

据我们所知，最近采用贪婪搜索方法寻找稀疏对抗扰动的攻击——Pointwise（Schott 等人，2019）是第一个基于决策的稀疏方法。该方法在非目标设置和低分辨率数据集上有效，但被认为需要极其大量的查询才能在大规模数据集和目标攻击设置中实现低稀疏对抗扰动（如第 4 节所见）。总之，当前的黑盒稀疏对抗攻击方法在稀疏性和查询效率上仍有不足。开发基于决策的稀疏攻击提出了一个具有挑战性的优化问题，因为：i) 仅能有限地访问目标模型的决策；以及 ii) $l_0$ 范数约束优化的 NP 难问题。

3 提出的方法

3.1 问题表述

在我们的稀疏攻击设置中，给定一个归一化的源图像 $x \in [0, 1]^{C \times W \times H}$ 及其对应的来自标签集 $Y = {1, 2, \dots, K}$ 的真实标签 $y$，其中 $K$ 表示类别数，$C$、$W$ 和 $H$ 分别表示图像的通道数、宽度和高度。我们要攻击的分类器是 $f: \mathbb{R}^{C \times W \times H} \to Y$；我们对其的访问仅限于其输出标签。在目标设置中，$x$ 被扰动，使得获得的实例 $\tilde{x} \in \mathbb{R}^{C \times W \times H}$ 被误分类为由对手选择的期望类别标签 $\tilde{y} \in Y$。我们将输入 $x$ 的期望类别称为目标类别，其真实类别称为源类别。在非目标设置中，对手操纵输入 $x$ 以改变分类器的决策到除其实类别外的任何类别标签，即 $\tilde{y} \in Y$ 且 $\tilde{y} \neq y$。形式上，寻找最佳对抗实例 $x^*$ 的稀疏对抗攻击（目标或非目标）可以表述为一个约束优化问题：

$$x^* = \arg \min_{\tilde{x}} | x - \tilde{x} |_0 \quad \mathrm{s.t.} \quad f(x^*) = \tilde{y}. \quad (1)$$

其中 $| \cdot |_0$ 是表示扰动像素数量的 $\ell_0$ 范数。方程 1 中旨在最小化扰动像素数量的优化问题导致了一个 NP 难问题（Modas & Moosavi-Dezfooli, 2019; Dong 等人，2020）。因此，考虑到约束以及在此设置下 $f$ 不可微的事实，优化问题的解并非易事。

3.2 SPARSEEVO 攻击算法

我们设计了一种高效的参数搜索方法——SparseEvo——基于进化算法方法，通过迭代改进潜在解的过程来搜索理想的解。通过重组、变异、适应度评估和选择的过程，种群的质量随时间提高以产生理想的解。重要的是，我们基于进化的搜索方法不需要关于底层目标模型的先验知识，例如模型架构或模型参数来构建评估潜在解的适应度函数。因此，算法 1 和图 2 详述的这种方法非常适合在黑盒设置中解决方程 1 中的非平凡优化问题，并为 NP 难问题提供了一种可能的补救措施。我们在下面详述算法的公式。

定义降维搜索空间。在将参数搜索方法应用于该问题时，每个候选解可以定义为一个参数集，包含定义对抗输入在搜索空间 $\mathbb{R}^{C \times W \times H}$ 中所有扰动像素的坐标和 RGB 值。天真地应用通用参数搜索方法来寻找潜在解——参数集——正如在单像素算法（Su 等人，2019）中观察到的那样，效果不佳，因为对模型的查询次数随着输入图像大小和扰动像素数量迅速增长。我们提出了两种技术来减小搜索空间。为便于参数搜索方法，我们建议不搜索定义每个扰动像素坐标和 RGB 值的参数，而只搜索定义源图像中待扰动像素坐标的参数——即我们旨在为其制作对抗性扰动的图像。构建所有形式为坐标值的参数集的候选解取决于扰动像素的数量，并阻碍方法的实现。因此，我们将种群中的每个候选解向量化为一个二元向量 $v \in {0, 1}^N$，其中 0 位和 1 位分别表示未扰动和扰动的像素，$N$ 是图像的总像素数。$v$ 的每个元素对应一个像素，每个元素的位置 $i$ 由一个映射函数 $\phi(n,m)$ 标识。这里，我们采用一种简单的展平技术，由映射函数 $\phi(n,m) = n + W \times (m - 1)$ 定义，其中 $n$、$m$ 是像素的坐标，$W$ 是图像的宽度，以进一步减小搜索空间。对于这些扰动像素的颜色值，我们从目标类别的起始图像（在目标攻击中，我们旨在将源图像误分类到该目标类别）中对应的像素选择 RGB 值。我们在图 2 的算法上下文中展示了源图像和起始图像。所有候选解——二元向量——可以在迭代过程中改变和进化，直到达到理想的解。因此，我们的参数搜索方法本质上转变为一种将发现注入源图像以构建对抗样本的最小、最有效像素集的方法。令人惊讶的是，这种方法被证明是基于决策的稀疏攻击的极其有效的策略。

原始的搜索空间 $\mathbb{R}^{C \times W \times H}$ 现在被转换为新的搜索空间 ${0, 1}^N$，其中 $N = WH$ 是总像素数。换句话说，关于 RGB 值和 $n$、$m$ 坐标的搜索空间被转换为关于 $i = \phi(n,m)$ 的搜索空间，而无需探索 RGB 值。因此，与原始搜索空间相比，这些技术导致了搜索空间大小的减小。

图 2：SparseEvo 算法示意图。种群初始化创建第一代种群。该种群通过二元差分重组、变异、适应度评估（对抗样本构建和适应度计算）和选择阶段在迭代中进化。源图像和起始图像（用于目标攻击）用于在种群初始化时创建初始候选解——二元向量表示——以及在适应度评估阶段基于候选解 $v^{(m)}$ 构建对抗样本。

适应度评估。在描述算法的其他阶段之前，我们描述用于确定候选解优劣的适应度评估，这对于种群初始化和适应度评估阶段是必要的。

对抗样本构建。由于候选解——一个二元向量 $v$ ——用于构建对抗样本，其适应度通过计算其对应对抗样本的优化目标来衡量。因此，我们首先根据以下公式产生对应于 $v$ 的对抗样本，其中 $c,n,m$ 表示像素的通道和两个坐标。

$$\tilde{x}{c,n,m} \leftarrow (1 - v_1)x{c,n,m} + v_1 x'_{c,n,m}. \quad (2)$$

适应度函数公式。适应度函数应反映优化目标。在基于分数的设置中，目标是优化损失使得给定输入可以被误分类，适应度函数基于输出分数是合理的选择（如 Alzantot 等人，2019；Qiu 等人，2021）。然而，在我们的问题中，最小化 $l_0$ 失真的目标直接导致了一个 NP 难问题。为减轻这一计算负担，Modas & Moosavi-Dezfooli（2019）将 $l_0$ 松弛为 $l_1$ 范数以构建白盒攻击 SparseFool，并且可以访问输出分数，这与基于决策的设置不同。尽管如此，在基于决策的设置中，我们发现优化 $l_2$ 范数比 $l_1$ 提供了更好的替代方案。因此，在本文中，我们将（目标攻击的）适应度函数 $g$ 表述为：

$$g(\tilde{x}) \leftarrow \begin{cases} | x - \tilde{x} |_2, & \mathrm{if} f(\tilde{x}) = \tilde{y} \ \infty , & \mathrm{otherwise} \end{cases}, \quad (3)$$

其中 $\tilde{x}$ 是使用方程 2 构建的图像，$\tilde{y}$ 是目标类别。非目标攻击的类似适应度函数可以表述为方程 3，但约束条件现在是 $f(\tilde{x}) \neq y$。

种群初始化。回想一下，我们的搜索目标是发现由二元向量表示的最小扰动——候选解。因此，我们从初始化的向量 $v^{(o)}$ 中初始化一个包含 $p$ 个不同候选解的种群，$v^{(o)}$ 的公式如下，其中 $C$ 为通道数。

$$v_1^{(o)} \leftarrow \begin{cases} 0, & \mathrm{if} x_{c,n,m} = x'_{c,n,m} \forall c \in {1, \dots, C} \ 1, & \mathrm{otherwise} \end{cases} \quad (4)$$

每个候选解仅通过随机改变 $v^{(o)}$ 中的 $d$ 个 1 位来生成，其中 $d = \lfloor \alpha WH \rfloor$，$\alpha$ 是初始化率。如果一个候选解的适应度得分不是 $\infty$，则成功添加到种群中；我们在方程 3 中解释了我们的适应度函数。否则，随机翻转另外 $d$ 个 1 位以生成另一个候选解。重复此过程，直到找到所有 $p$ 个成功的候选解并存储在种群集 $V$ 中。每个候选解的对应适应度得分存储在适应度得分矩阵 $G$ 中。种群初始化阶段的伪代码详见附录 A.1 中的算法 2。

图 3：算法 1（第 6 行）和方程 5 所示的二元差分重组。$\odot$ 是逐元素乘积，$v^{(ks)}$、$v^{(j)}$、$v^{(q)}$ 分别是种群中最好的和两个随机选择的候选解。

二元差分重组。在遗传算法中使用的一些重组方法中，例如 k 点交叉或均匀交叉，一对亲本交配为下一代产生后代。然而，在种群初始化阶段之后，所有第一代亲本彼此之间略有不同，因为它们都是从初始化的向量 $v^{(o)}$ 生成的。因此，这些交叉变体导致次优解和低查询效率。为了解决这个问题，我们增加了种群中的多样性。受差分进化算法（Storn & Price, 1997）的启发，我们通过变异和组合多个现有亲本来创建下一代。尽管如此，天真地应用 DE 是不切实际的，因为 DE 算法的变异操作将多个选定亲本的加权差加到另一个亲本上以产生后代。这些个体是实坐标空间中的向量，因此后代可以从加权的实值差中受益，但在我们提出的搜索空间中无法获得这种好处，因为所有候选解都是二元向量。因此，我们提出了二元差分重组方案——一种基于 GA 中均匀交叉和 DE 中变异概念的混合方法。

有不同的变异方案，它们会影响整体性能（Manolis & Vagelis, 2020）。在基于决策攻击的问题中，通过附录 A.3 中展示的经验结果，我们观察到重组最佳和两个选定候选解的方法优于其他方法。因此，我们首先从种群中均匀随机选择两个候选解 $v^{(i)}$ 和 $v^{(q)}$。然后，我们采用均匀交叉，以相等概率从任一选定候选解中选择每个位，以产生一个新的候选解。随后，将种群中的最佳个体 $v^{(ks)}$ 与新候选解重组，方法是改变 $v^{(ks)}$ 中所有在新候选解中对应位为 0 的 1 位。形式上，二元差分重组可以表述为：

$$v^{(r)} \leftarrow v^{(ks)} \odot \mathrm{UniformCrossover}(v^{(i)}, v^{(q)}) \quad (5)$$

其中 $\odot$ 是逐元素乘积。该操作在图 3 中可视化。由于从个体间的差异中获益，我们的方法能够如第 4 节所示促进进化进展。

变异。种群中的多样性是实现在搜索空间中进行探索以获得更好个体的关键因素。因此，旨在促进这种种群多样性的变异操作是我们方法的关键组成部分，重组后的每个后代都可能发生变异。在实践中，我们随机均匀选择后代 $v_0$ 的所有 1 位中的 $\mu$ 部分，并将这些位设为零。我们不选择 0 位进行改变，因为这阻碍优化进展并需要更多迭代来搜索最优解。

选择。我们简单的直觉是，具有更好适应度值的个体应该在未来的世代中存活下来。在问题 1 中，较小的适应度值更好，代表更不易察觉的对抗样本。为此，如果种群中最差的个体比后代的适应度值高，它将被丢弃，新的后代将被选择取代其位置。

4 实验与评估

4.1 实验设置

攻击和数据集。为了全面评估 SparseEvo 的有效性，我们采用了两个不同维度的标准计算机视觉任务：CIFAR10（Krizhevsky 等人）和 ImageNet（Deng 等人，2009）。我们与最先进的稀疏攻击算法 Pointwise（Schott 等人，2019）进行比较，并使用白盒稀疏攻击 PGD0（Croce & Hein，2019）作为黑盒基于决策对应方法的基准。对于评估集，我们选择一个平衡的样本集。我们分别从 CIFAR10 和 ImageNet 中随机抽取 1000 和 200 张正确分类的测试图像。这些选定的图像在 10 个（CIFAR10）和 200 个随机选择的（ImageNet）类别中均匀分布。在目标设置中，对于来自 CIFAR10 的每张图像，攻击将其真实标签翻转为 9 个目标类别，而对于来自 ImageNet 的每张图像，为了减少评估任务的计算负担，随机选择一组五个目标类别。所有参数设置总结在附录 A.2 中。

模型。对于基于卷积的模型，我们使用最先进的架构——ResNet——（He 等人，2016），特别是用于 CIFAR10 的 ResNet18，达到 95.28% 的测试准确率，以及 torchvision（Marcel & Rodriguez, 2010）提供的用于 ImageNet 的预训练 ResNet-50，具有 76.15% 的 Top-1 标签测试准确率。对于基于注意力的模型，我们选择了预训练的 ViT-B/16 模型，获得 77.91% 的 Top-1 标签测试准确率（Dosovitskiy 等人，2021）。值得注意的是，该模型由 Google 在大规模高分辨率 ImageNet 数据集上训练。

评估指标。为了评估方法的性能，我们将归一化稀疏度量定义为 $l_0$ - 范数失真除以图像的总像素数，然后计算评估集上稀疏度的中位数——因为它对异常值不敏感。用于评估模型鲁棒性的一个度量是攻击成功率。如果一个生成的扰动能够产生稀疏度低于给定稀疏度阈值的对抗样本，则被认为是成功的。

目标和非目标设置。我们的攻击在非目标设置和目标设置下分别经过 3000 次和 15000 次查询后，能够收敛到极高的稀疏度。而 Pointwise 在两种设置下都未能收敛到较低的值。

攻击成功率。图 5b 显示，仅用 1000 次查询，SparseEvo 在所有不同稀疏度阈值下都优于具有 5000 次查询预算的 Pointwise。值得注意的是，在非目标设置中，具有 5000 次查询预算的 SparseEvo 在稀疏度阈值从 0.002 开始能够获得比理想白盒 PGD0 略高的 ASR。在更困难的目标设置中——仅用 15000 次查询的 SparseEvo 能够获得比 PGD0 稍低的 ASR，而当查询预算为 20000 时，我们的攻击在稀疏度阈值大于 0.01 时与 PGD0 一样鲁棒。

4.4 比较变换器和 CNN 的鲁棒性

在本节中，我们比较 ViT 和 ResNet50 模型在非目标设置和目标设置下对稀疏扰动的鲁棒性。图 6 报告了这些模型在 ImageNet 的 100 张图像评估集上的对抗样本准确率。我们在附录表 3 中总结了不同查询预算和攻击设置下的结果。总体而言，我们发现 ViT 的性能如预期般下降，但似乎比 ResNet50 模型更不易受到影响。特别是在非目标设置下，在不同稀疏度阈值下，ViT 的准确率在 SparseEvo 和 PGD0 下都高于 ResNet50 模型。有趣的是，SparseEvo 只需要 2000 次的小查询预算就能使 ResNet50 的准确率下降到与白盒 PGD0 相似的程度，而要使 SparseEvo 对 ViT 的攻击效果比 PGD0 差，则需要多达 5000 次查询。在目标场景中，我们观察到在低查询预算下（例如 10000），ResNet50 在 SparseEvo 下比 ViT 鲁棒得多，而在 20000 次查询时，ResNet50 和 ViT 模型的准确率几乎相似，并且当稀疏扰动大于 0.02 时降至接近零。值得注意的是，具有足够查询限制（例如 20000）的 SparseEvo 能够保持其对 ViT 和 ResNet50 的攻击有效性，而 PGD0 的攻击有效性在攻击 ViT 时会降低——表现为更低的准确率分数。

图 4：在 ImageNet 评估集上使用 ResNet50 模型（图像尺寸 $W \times H$：224×224）。a) 中位数稀疏度（使用第一和第三四分位数作为下界和上界误差条）与模型查询次数的关系；b) 攻击成功率与稀疏度阈值的关系。在目标和非目标攻击设置下，我们的 SparseEvo 在查询效率和实现稀疏度方面均优于 Pointwise。

图 5：在 ImageNet 评估集上使用 ViT 模型（图像尺寸 $W \times H$：224×224）。a) 中位数稀疏度（使用第一和第三四分位数作为下界和上界误差条）与模型查询次数的关系；b) 攻击成功率与稀疏度阈值的关系。

图 6：针对 ImageNet 评估集的 ViT 与 ResNet，在不同查询预算下攻击成功率与稀疏度阈值的关系。PGD0 是白盒攻击（理想情况）。

5 结论

在这项工作中，我们提出了一种在基于决策场景下的稀疏攻击新算法——SparseEvo。我们的综合结果表明，在给定的查询预算内，SparseEvo 在稀疏度和 ASR 方面都优于最先进的黑盒攻击。更重要的是，在高分辨率和大规模数据集上，与黑盒设置中现有的稀疏攻击相比，SparseEvo 展示了显著的查询效率和更低的稀疏度。

最值得注意的是，我们的黑盒攻击在小的查询预算下，实现了与最先进的白盒攻击——PGD0——相当的成功率（更多见解请读者参阅附录 A.9）。

参考文献

A 附录

A.1 种群初始化

算法 2 呈现了我们种群初始化方法的伪代码，如第 3.2 节所述。

2.1 超参数 我们在表 1 中列出了在 CIFAR10 和 ImageNet 两个不同评估集上用于 SparseEvo 的关键超参数。该超参数集适用于攻击大规模高分辨率数据集 ImageNet 上的 ViT-B/16。值得注意的是，在从高分辨率任务转换到低分辨率 CIFAR10 任务时，我们只需要调整变异率；因此，我们的方法提供了一个鲁棒的算法，可以轻松适应不同的视觉任务。 我们所有 ImageNet 实验任务（包括在 ResNet50 和 ViT 模型上的实验）中使用的图像大小是 (3 通道) × 224 (W) × 224 (H)。这是我们使用的 ImageNet 数据集上预训练模型（PyTorch）的标准输入大小。

表 1：我们实验中的超参数设置

A.3 对超参数的鲁棒性以及研究重组和变异方案

在本节中，我们进行了全面的实验，以研究我们算法中使用的超参数的影响以及我们考虑的不同重组和变异方案。这些实验是在 CIFAR10 上随机选择的 1000 张图像上以非目标设置进行的。对于超参数研究，我们一次调整种群大小或变异率，同时使用重组种群中最佳和两个随机候选的方案以及仅变异 1 位二元值的方案。

图 7a 显示，在不同的种群大小和变异率 0.04 下，即使是小的种群大小 10 也足以让 SparseEvo 快速收敛。在 200 次查询后，我们使用较大种群大小的方法几乎收敛到与种群大小 10 一样低的稀疏度。因此，种群大小对 SparseEvo 的整体性能影响很小。在变异率 0.04 和固定种群大小 10 的情况下，与其他变异率相比，算法表现良好且最快收敛到低稀疏度，如图 7b 所示。因此，我们的攻击方法受变异率的影响更大，但这并不意外。

图 7：在 CIFAR10 上使用 ResNet18 的稀疏度与模型查询次数的关系，以显示不同超参数对 SparseEvo 的影响。

为了评估不同重组和变异步骤方案如何影响我们的方法，我们使用种群大小 10 和变异率 0.01，并一次改变重组或变异方案。图 7c 说明，重组三个随机选择的个体无法达到与重组最佳和其他两个个体的方案一样高的查询效率。

1-位变异——或者同时 0-位和 1-位——0 & 1-位变异——一次改变一个二元向量。对于 1-位变异方案，我们随机改变选定二元向量所有 1 位中的一个因子 $\mu$。对于同时变异 0-位和 1-位的方案，我们随机翻转 $n$ 个 1 位和 $\frac{n(1 - \beta)}{\beta}$ 个 0 位，其中 $n = \mu \beta$。我们发现仅变异 1 位的方案略好于 $\beta = 0.8$ 和 $\beta = 0.9$ 的其他方案，因为同时变异 0 和 1 位可能减慢收敛速度，如图 7d 所示。

A.4 稀疏攻击对对抗性训练模型的鲁棒性

在本节中，我们研究了不同稀疏攻击对在 CIFAR10 任务上使用 $l_\infty$ 扰动进行对抗性训练的 ResNet-18 网络的鲁棒性——这是对抗攻击最有效的防御机制之一（Athalye 等人，2018）。这个对抗性训练网络的准确率为 83.87%。我们选择 PGD0（Croce & Hein, 2019），一个最先进的白盒攻击作为比较基准。本实验中使用的基于对抗性训练的模型是使用 Madry 等人（2018）提出的投影梯度下降对抗性训练训练的。

实验在一个从 CIFAR10 随机抽取的平衡评估集上进行（我们在第 4.1 节描述了数据集）。中位数稀疏度与查询次数的关系如图 8 所示。结果表明 SparseEvo 比 Pointwise 攻击收敛更快。图 8 还显示了对抗性训练模型的不同攻击方法在不同失真水平和查询限制下的攻击成功率。我们观察到，我们的攻击能够仅用 500 次的非常有限的查询预算，获得与理想白盒 PGD0 基线攻击相当的性能。同时，SparseEvo 在给定 200 次查询预算时与 Pointwise 相当，并在 500 次查询预算时优于 Pointwise。

图 8：针对 CIFAR10 任务上对抗性训练模型的不同稀疏攻击。我们展示了稀疏度与查询次数的关系以及 ASR 与稀疏度在两种不同查询预算下的关系：200 和 500。

A.5 针对 CIFAR10 任务 CNN 模型的攻击

图 9a 显示了中位数稀疏度与查询次数的关系，以及用作下界和上界误差条的第一和第三四分位数。该图提供了在非目标设置和目标设置下，针对 CIFAR10 评估集不同攻击的综合比较。我们的攻击在查询次数和稀疏度方面始终优于 Pointwise 攻击。特别是在非目标设置中，我们的攻击能够通过扰动极少数像素来制作对抗图像，对于 CIFAR10 上的大多数图像，平均在 2000 次查询内完成；而 Pointwise 在此评估集上仅获得 0.75 的稀疏度。在目标设置中，在给定的查询预算下，SparseEvo 收敛到比 Pointwise 攻击更低的稀疏度。

攻击成功率。图 9b 说明了在 CIFAR10 评估集上，SparseEvo 在不同稀疏度阈值和不同查询预算下的 ASR，并与 PGD0（理想白盒基线）和 Pointwise（最先进的黑盒稀疏攻击）的最佳成就进行了比较。在非目标设置中，我们观察到使用 200 次或更多查询的 SparseEvo 比使用 500 次查询的 Pointwise 获得更高的成功率。值得注意的是，我们的黑盒稀疏攻击可以在 500 次的较小查询预算下实现与 PGD0 相当的 ASR。在目标设置中，仅用 500 次查询，我们的攻击在所有稀疏度阈值上表现出显著优于 Pointwise 的 ASR，而 SparseEvo 在 2000 次查询预算下实现的 ASR 仅略低于 PGD0（理想白盒基线）。

图 9：使用 ResNet18 模型的 CIFAR10 评估集。a) 中位数稀疏度与模型查询次数的关系，第一和第三四分位数用作下界和上界误差条；b) 攻击成功率与稀疏度阈值的关系。

表 2：不同查询预算下的中位数稀疏度和 ASR。在小规模和大型平衡数据集上，不同攻击（PGD、Pointwise 和 SparseEvo）之间的综合比较。

表 3：在不同查询预算和稀疏度阈值下，ResNet50 和 ViT 在攻击下的准确率。在 ImageNet 的小规模和大型平衡评估集上，不同攻击（PGD 和 SparseEvo）之间的综合比较。

A.6 与 POINTWISE 的算法比较

在本节中，我们讨论为什么 SparseEvo 能够用少得多的查询搜索到理想的解（扰动像素数更少的对抗样本）。

1. 贪婪与进化方法。Pointwise 选择贪婪地最小化扰动像素数量，方法是每次随机选择和改变起始图像 $x' \in R^{C \times W \times H}$ 的一个随机选择的像素位置 $i,j$ 的一个维度（即单个颜色通道）（即每次查询）。如果改变成功欺骗了模型，它将被保留；否则，改变将被丢弃。相比之下，SparseEvo 一次评估多个像素的候选提议，并同时改变一个像素的所有维度，以产生用于下一次进化的新候选解或后代；因此它能够更快收敛并使用更少的查询。
2. 更小的搜索空间。Pointwise 的公式导致搜索空间大小为 $C \times W \times H$，其中 $C$ 是三个 RGB 通道，$W$ 是图像宽度，$H$ 是图像高度。我们将此搜索空间减少到 $W \times H$，因为 SparseEvo 仅搜索像素位置，但不尝试搜索每个像素的不同颜色（参见第 3.2 节和附录 A.7 中的'定义降维搜索空间'）。
3. 对大图像尺寸更好的可扩展性。鉴于 PointWise 一次只改变一个维度（即一个像素），为了减少起始图像（目标类别）像素值与源图像不同的数量（以最小化 L0），随机选择方法需要在后续迭代中选择：i) 相同的像素位置 $i,j$ 和 ii) 相同像素位置 $i,j$ 的不同颜色通道，以使起始图像（目标类别图像）中的给定像素值 $i,j$ 与源图像相同。虽然这在像 CIFAR10 这样的小图像任务（具有较小的 $W$ 和 $H$ 值）中更可能发生，但在 ImageNet 任务中使用大输入图像的 20,000 次查询预算内，这几乎不可能发生，因为 1000 个测试图像对的平均稀疏度值几乎保持为 1。
4. 对'好'解的迭代改进。重要的是，我们的方法通过一个迭代改进先前迭代中基于目标函数的良好解的过程，来搜索具有最小扰动像素数的解。相比之下，Pointwise 采用纯粹的随机方法来选择要改变的像素维度和位置 $i,j$。

A.7 与作为基线的改进版 POINTWISE 算法的比较

*表 4：目标攻击设置下不同查询次数时的平均稀疏度度量（越低越好）。SparseEvo 与改进版 Pointwise 在 ImageNet 上 100 对图像集上的比较（此处 PW- np 表示选择数设为 np 的 PointWise，斜体字表示 PW 的最佳结果）。

PointWise 随机选择和改变图像 $x' \in R^{C \times W \times H}$ 的一个随机选择的像素位置 $i,j$ 的一个维度（一个颜色通道）每次（即每次查询）。因此，Pointwise 的公式导致搜索空间大小为 $C \times W \times H$，其中 $C$ 是三个 RGB 通道，$W$ 是图像宽度，$H$ 是图像高度。因此，它对于大图像尺寸（例如大小为 224×224 的 ImageNet）不可扩展；这可以在图 4 和 5 中观察到。

在本节中，我们尝试通过修改 PointWise 使其一次执行多次选择（即每次查询）来提高其在 ImageNet 上的查询效率，并使用不同的选择参数 $n_p$ 进行了一系列实验。表 4 显示了我们的改进版 Pointwise 方法在不同选择参数值下获得的平均稀疏度；$n_p = 4, 8, 16, 32, 64, 128$。结果表明，

改进版 Pointwise 算法的最佳性能——PW-8——比原始实现好得多，但仍远落后于我们的方法。在各种查询预算下，SparseEvo 仍然优于我们改进的 Pointwise 算法。我们可以将完整的结果集添加到论文的最终版本中。

A.8 与适应于构建稀疏攻击的密集攻击的比较

我们有动机研究是否可以将基于决策的密集攻击（L2 和 L∞ 约束），例如 BA（Brendel 等人，2018）、HSJA（Chen 等人，2020）、QEBA（Li 等人，2020）、NLBA（Li 等人，2021）、PSBA（Zhang 等人，2021）、SignOPT（Cheng 等人，2020）或 RayS（Chen & Gu, 2020），通过投影到 L0 - 球来适应稀疏设置。这个想法很有前景，因为 PGD 可以被成功地适应到稀疏设置中，以在白盒设置中提供稀疏攻击算法。在本节中，我们进行了一项研究，通过修改 HSJA 方法来评估这个想法，因为它被证明是一种查询高效的基于决策的密集攻击（L2 和 L∞ 约束），将其改为称为 L0 - HSJA 的 L0 约束算法。值得注意的是，对于其他方法，例如 QEBA、NLBA、PSBA、SignOPT 或 RayS，也可以进行同样的修改。

重要的是，HSJA 的作者提出了两种不同的梯度估计方式，专门为 L2 和 L∞ 场景制定。然而，L0 距离度量不可微，因此不适合标准梯度下降（Carlini & Wagner, 2017; Fan 等人，2020），因此我们利用 L2 来估计梯度。L0 - HSJA 算法与已发布的 HSJA 之间的区别在于投影步骤。L0 - HSJA 不像 HSJA 那样执行 L2 和 L∞ 投影步骤，而是执行与 PGD10 方法类似的 L0 投影。为了搜索要扰动的最小像素数，我们采用二分搜索来最小化 L0。在每次迭代中（使用来自 HSJA 的发现的对抗样本），我们执行以下投影过程：

1. L0 -HSJA 对由 HSJA 制作的样本对抗样本与源图像之间的像素差异进行排序。
2. L0 -HSJA 然后对 $k$ 执行二分搜索，$k$ 表示从由 HSJA 制作的样本对抗样本中保留的（扰动）像素的最小数量。这里，$k = \frac{ur + lr}{2}$，其中 $lr$ 和 $ur$ 是下界和上界范围，分别初始化为 0 和 $N$。$N$ 是图像中的总像素数。
3. 随后，我们创建一个候选稀疏对抗样本，仅保留 HSJA 制作的对抗样本中差异最小的前 $k$ 个像素，并将制作的样本的其余像素替换为我们计划欺骗的源图像中的对应像素。这些前 $k$ 个像素与其对应像素的差异最小。这就产生了用于评估的投影图像 $x_p$。如果投影样本能够成功误导受害模型，则 $ur$ 用 $k$ 更新（以搜索更少的扰动像素数）。否则，用 $k$ 更新 $lr$。
4. 重复此步骤，直到 $ur$ 和 $lr$ 的差值小于或等于阈值 1。

对于 L0 - HSJA 的后续迭代，我们使用投影图像 $x_p$ 来制作新的对抗样本 $x'_p$，以试图改进当前迭代的投影对抗样本。

我们得到的结果如表 5 所示，说明了在 CIFAR-10 上 100 对图像集的平均稀疏度。我们的评估表明，将 L0 投影应用于为 L2 和 L∞ 方法制定的密集攻击，并不能产生旨在最小化扰动像素数量的查询高效的稀疏攻击。我们可以理解这个结果，因为在每个投影步骤中，修改后的 L0 - HSJA 算法仍然需要大量的查询来确定最小化 L0 的投影（换句话说，确定要保留的最小像素数，使得制作的样本仍然是对抗性的）。

据我们所知，在黑盒基于决策的设置中，没有有效的方法来确定可以投影多少个像素以及哪些像素，使得扰动后的图像不会越过 DNN 模型的未知决策边界。此外，最小化要投影的选定像素数量的问题导致了一个 NP 难问题（Modas & Moosavi-Dezfooli, 2019; Dong 等人，2020）。尽管我们使用具有最小扰动像素数的投影图像，L2 和 L∞ 基于决策的攻击需要在后续迭代中扰动整个图像，因此下一次迭代不一定朝着最小化扰动像素数量的目标移动。因此，L0 - HSJA 和其他密集方法并未为稀疏攻击提供有效的算法。

*表 5：目标设置下不同查询次数时的平均稀疏度度量（越低越好）。L0 - HSJA 和 SparseEvo 在 CIFAR10 上 100 对图像集上的比较。

A.9 关于与白盒基线结果的讨论

值得注意的是，PGD0 是 PGD 攻击适应到 L0 的版本，带有投影。PGD0 简单地将 PGD 攻击生成的对抗样本投影到 L0 - 球上（我们之前在附录 A.8 中描述了关于采用非稀疏基于决策攻击的过程）。这种投影不能保证投影解为后续的 PGD 迭代提供最佳梯度下降方向，以找到最小化 L0 的对抗样本。因此，即使可以完全访问模型，PGD0 也可能不总是产生最优解，而只是一个近似解。所以 PGD0 可能不总是攻击性能的上限，特别是在 ImageNet 上的非目标设置中，如图 5(b) 和图 6 的第二张图所示。

图 10：目标攻击设置下的可视化。使用我们的 SparseEvo 攻击算法在为 ImageNet 任务构建的黑盒模型上生成的稀疏攻击恶意实例，具有不同的查询预算。