Sign-OPT：一种查询高效的硬标签对抗攻击

1. 01这篇论文试图解决什么问题？

   降低 hard-label 黑盒对抗攻击的查询开销：已有方法攻击单个样本通常需超过 20,000 次查询。

   核心问题：在只能拿到模型预测标签（hard-label）的黑盒设定下，如何用更少的查询生成对抗样本。

   • 场景与重要性：作者认为这是评估机器学习系统鲁棒性时最实际的受限访问设定——模型对攻击者隐藏，只能查询并得到决策结果。已有 hard-label 攻击算法通常需要超过 20,000 次查询才能攻击一个样本。
   • 现有方法的不足：Boundary attack 基于决策面上的随机游走，作者指出它没有收敛保证；Cheng et al. (2019) 把 hard-label 攻击重写为优化问题，可用零阶优化求解，但每次函数求值都要靠二分搜索、消耗数十次查询，攻击单张图像仍需约 20,000 次查询。
   • 核心观察：作者认为（i）让算法收敛并不需要很精确的方向导数数值；（ii）存在一种不完美但有信息量的方向导数估计，只需一次查询即可算出它的符号。
   • 论文提出的方法：基于单查询符号预言机（single query oracle）设计新的零阶优化算法 Sign-OPT，以及用 SVM 恢复梯度的变体 SVM-OPT，并给出收敛性分析。
   • 威胁模型：
     • 攻击者目标：对给定样本生成小扰动使模型误分类（untargeted）或预测为指定目标类（targeted），以 L2 扰动衡量。
     • 攻击者知识：hard-label black-box——不知道模型结构与权重。
     • 攻击者能力：可查询模型并获得对应的 hard-label 决策（top-1 预测类别），查询次数受限。
     • 受害系统：图像分类模型（MNIST/CIFAR-10 上的 CNN、ImageNet 上的 ResNet-50）。

   收起这一问

2. 02有哪些相关研究？

   相关工作分白盒攻击、软标签黑盒攻击、hard-label 黑盒攻击三组，本文属于第三组。

   白盒攻击

   • Goodfellow et al. (2015)、Carlini & Wagner (2017)、Madry et al. (2017) 等——在模型完全暴露给攻击者的设定下基于梯度构造攻击，代表方法包括 C&W 和 PGD。
   • Athalye et al. (2018)——提出 BPDA 攻击，绕过使用混淆梯度的防御。

   软标签（概率输出）黑盒攻击

   • Chen et al. (2017)——用坐标式有限差分估计输出概率变化并做坐标下降；Ilyas et al. (2018a) 用 NES 直接估计梯度；后续变体（Ilyas et al., 2018b; Tu et al., 2019）利用侧信息加速。
   • Al-Dujaili & O'Reilly (2019)——提出基于 signSGD 的 SignHunter，在软标签设定下用符号估计加速收敛。
   • Liu et al. (2019)——为软标签黑盒攻击设计 ZO-SignSGD；论文指出其估计器对整个向量取符号、忽略随机方向 uq 的方向，实践中收敛更慢（见第 4.4 节与 Figure 5(b)）。

   hard-label 黑盒攻击

   • Brendel et al. (2017)——最早研究该问题，提出基于决策边界附近随机游走的 Boundary attack；论文指出它没有收敛保证。
   • Ilyas et al. (2018a) 的 Query-Limited attack——用查询估计概率分数，把 hard-label 问题转成 soft-label 问题。
   • Cheng et al. (2019)——把 hard-label 攻击重新形式化为"寻找距决策边界最短方向"的优化问题（论文称 Cheng's formulation），本文沿用该形式。
   • Chen et al. (2019)（HopSkipJumpAttack）——把零阶符号预言机用于改进 Boundary attack；论文指出区别在于本文提出新的零阶梯度下降算法、给出收敛保证、针对 Cheng's formulation 降低查询复杂度，且对方用单点梯度估计、方差更大（附录 A.1 有对比）。

   基线与基准：对比基线为 Boundary attack、OPT-based attack（Cheng et al., 2019）、Guessing Smart Attack（Brunner et al., 2018，实验中去掉依赖相似模型的先验）和白盒 C&W L2 攻击；数据集为 MNIST、CIFAR-10、ImageNet-1000。

   作者将本文定位为：沿用 Cheng's formulation 的光滑性优势，但用单查询符号估计替代有限差分，从而把 hard-label 攻击的查询复杂度降低 5–10 倍。

   收起这一问

3. 03论文如何解决这个问题？

   沿用 Cheng's formulation，用单查询估计方向导数符号，构造新的零阶梯度下降算法 Sign-OPT。

   整体思路：沿用 Cheng et al. (2019) 把 hard-label 攻击写成"寻找距决策边界最短方向"的优化问题，但不估计方向导数的大小，只用一次查询估计它的符号，据此设计 Sign-OPT 算法。

   问题形式化

   • 给定样本 x0、真实标签 y0 和 hard-label 黑盒函数 f，untargeted 攻击的目标为 min_θ g(θ)，其中 g(θ) = argmin_λ>0 f(x0 + λθ/|θ|) ≠ y0，即方向 θ 上到决策边界的最短距离。
   • 作者称该目标函数通常光滑，且 g 的值可通过二分搜索用 hard-label 查询求出；但 Cheng et al. (2019) 每次求值都要二分搜索，消耗数十次查询。

   单查询符号预言机

   • 关键设计：对新方向 θ+εu，在距 x0 为 g(θ) 处查询一次模型，若预测不等于 y0 则取 +1，否则取 −1，即得到 sign(g(θ+εu) − g(θ))。
   • 含义：若该点落在边界外，说明新方向到边界的距离更小，u 是使 g 下降的下降方向；每个符号只需 1 次查询。

   Sign-OPT 算法

   • 每次迭代采样 Q 个随机向量 uq（高斯或均匀分布），用 ĝ = 1/Q∑_q sign(g(θ+ϵ u_q)−g(θ)) · u_q 估计梯度，只需 Q 次查询，再以步长 η 更新 θ ← θ − ηĝ。
   • 与 ZO-SignSGD（Liu et al., 2019）的区别：对方对整个向量取符号，而 Sign-OPT 保留了随机方向 uq 的模长信息；作者称这使其成为一种新的零阶优化算法，现有收敛分析不适用。
   • 收敛结果：在 g 为 L-smooth、梯度有界、梯度噪声单峰对称的假设下，取 ηt = O(1/√(QdT))、ε = O(1/(dT))，有 E[‖∇g(θ)‖²] = O(√d/√T + d/√Q)（Theorem 3.1，证明见附录 A.2）。

   SVM-OPT 变体

   • 把每个符号 yq = sign(⟨∇g(θ), uq⟩) 当作样本 uq 的标签，解一个硬间隔 SVM 二次规划恢复更准确的梯度估计 z，再更新 θ（Algorithm 2）。

   实现细节

   • 步长 η 用与 Cheng et al. (2019) 相同的线搜索估计；g(θ) 用二分搜索近似；初始 θ0 通过在 100 个随机方向上求 g(θ) 取最优得到（targeted 攻击用目标类的 100 个训练样本）。
   • 成功判定：以 median distortion（x 次查询内所有样本对抗扰动的中位数）为主要指标，辅以给定阈值 ε 下的 success rate。

   收起这一问

4. 04论文做了哪些实验？

   在 MNIST、CIFAR-10、ImageNet 上对比 4 种攻击，作者称 Sign-OPT 查询数少 5–10 倍且扰动更小。

   实验设置

   • 被测模型：MNIST 与 CIFAR-10 用 Carlini & Wagner (2017) 提供的 CNN（九层），准确率分别为 99.5% 和 82.5%；ImageNet-1000 用 torchvision 预训练 ResNet-50，Top-1 准确率 76.15%。
   • 数据集：MNIST、CIFAR-10、ImageNet-1000；每个攻击从验证集随机抽 100 个样本（untargeted 只取被正确分类的样本）。
   • 基线：Boundary attack、OPT-based attack（Cheng et al., 2019）、Guessing Smart Attack（去掉依赖相似模型的先验）、白盒 C&W L2 攻击。
   • 指标：median distortion（x 次查询内达到的对抗扰动中位数）为主；success rate（x 次查询内扰动低于阈值 ε 的样本比例），阈值随数据集而定（MNIST ε=1.5、CIFAR-10 ε=0.5、ImageNet ε=3.0）。
   • 超参数：Q = 200（在少量样本上调出，用于本节全部实验）；论文未报告重复次数。

   主结果

   Table 1：untargeted L2 攻击，给定查询数下的平均 L2 扰动与 SR。

   表格较宽，可左右滑动

   方法	MNIST 14k 查询 Avg L2 / SR(ε=1.5)	CIFAR-10 12k 查询 Avg L2 / SR(ε=0.5)	ImageNet 160k 查询 Avg L2 / SR(ε=3.0)
   Boundary	2.13 / 16.3%	0.78 / 29.2%	4.62 / 41.6%
   OPT	1.76 / 36.0%	0.33 / 61.0%	4.27 / 34.0%
   Guessing Smart	1.68 / 43.0%	0.24 / 80.0%	12.88 / 12.0%
   Sign-OPT	1.09 / 94.0%	0.13 / 95.0%	1.21 / 90.0%
   C&W（白盒）	0.88 / 99.0%	0.25 / 85.0%	1.51 / 80.0%

   • 作者称 Sign-OPT 在查询效率上持续优于现有 hard-label 方法，且多数情况下收敛到更小的扰动。
   • 作者称 Sign-OPT 的解与白盒 C&W 相当：CIFAR-10 上更好、MNIST 上更差、ImageNet 上相当（据 Table 1 末行与 Figure 4）。
   • ImageNet 例外：在 4,000 与 30,000 次查询处，Guessing Smart 的平均扰动（16.69、13.27）小于 Sign-OPT（23.19、2.99 之前的早期点）；到 30,000 次查询时 Sign-OPT 达 2.99、SR 50.0%，作者称其他攻击达到中位扰动 3.0 需超过 200k 次查询。

   Targeted 攻击

   • 测了什么：MNIST 与 CIFAR-10 上的 targeted L2 攻击（Figure 5(a)）。结果：作者称 C&W 白盒攻击在 MNIST 上的平均扰动为 1.51，Sign-OPT 达到该水平约需 12k 次查询，其他方法需超过 120k 次。
   • 单样本示例（Figure 2）：MNIST 上一个样本，Sign-OPT 约 6k 次查询得到 L2 扰动 0.94，OPT-based 攻击约 35k 次查询才达到相同水平。
   • CIFAR-10 成功率（Figure 6）：untargeted 与 targeted 在 ε=0.6 和 ε=0.3 阈值下，Sign-OPT 曲线整体高于其他方法（图中仅可读曲线相对位置）。

   单查询预言机的有效性

   • 测了什么：把 ZO-SignSGD 扩展到 hard-label 设定，比较"直接结合 Cheng et al. (2019) 的二分搜索估计"与"加单查询符号预言机"两种用法（Figure 5(b)，CIFAR-10）。
   • 结果：作者称简单组合 ZO-SignSGD 与 Cheng et al. (2019) 效率不高，加单查询预言机后查询数下降；Sign-OPT 仍优于带单查询预言机的 ZO-SignSGD，作者解释为其梯度保留了 u 的模长。

   其他消融与分析

   • Sign-OPT vs SVM-OPT（Figure 3 前两幅，MNIST/CIFAR-10，L2，targeted 与 untargeted）：两者查询效率相当，论文因此主实验只报 Sign-OPT。
   • Q 的影响（Figure 3 第三幅，CIFAR-10，Q=10 到 1000）：作者称 Q 不影响最终收敛点，Q 小则梯度估计噪声大、收敛延迟，Q 大则每次估计耗时多，Q=200 较均衡。
   • 与 HopSkipJumpAttack 对比（附录 A.1，Figure 7，MNIST/CIFAR-10，L2）：作者称两者查询消耗相当，部分情况下 Sign-OPT 收敛到更好的解；作者认为对方单点估计方差更大，初期略快但最终扰动略大。

   收起这一问

5. 05有什么可以进一步探索的点？

   论文未专门讨论局限；实验限于 3 个图像数据集、2 个模型、每个攻击 100 个样本。

   作者指出的局限与后续方向

   • 论文未专门讨论局限（无 Limitations 或 Future Work 小节）。
   • 第 4.1 节提到：Q 较小会给梯度估计带来噪声、延迟收敛，Q 较大则每次梯度估计耗时较多——这是作者写明的超参数权衡，而非独立局限讨论。

   实验覆盖范围

   • 被测模型为 2 个：MNIST/CIFAR-10 上的 CNN（Carlini & Wagner 提供的九层网络）和 ImageNet 上的 ResNet-50（第 4 节）。
   • 数据集为 MNIST、CIFAR-10、ImageNet-1000 三个图像分类数据集；每个攻击随机抽 100 个验证集样本（第 4 节）。
   • 攻击设定覆盖 untargeted 与 targeted、L2 范数；Boundary attack 只在 L2 设定下对比（第 4 节）。
   • 对比方法为 Boundary、OPT-based、Guessing Smart、白盒 C&W，以及附录 A.1 的 HopSkipJumpAttack 和第 4.4 节的 ZO-SignSGD 变体。
   • 论文未报告每个设置的重复次数、统计显著性检验，也未报告攻击的实际耗时（仅提到 Q 大时每次估计耗时多）。

   收起这一问

6. 06总结一下论文的主要内容

   Sign-OPT 用单查询符号估计把 hard-label 黑盒攻击的查询数降低 5–10 倍（作者称），并有收敛保证。

   一篇 ICLR 2020 的对抗攻击论文，针对 hard-label 黑盒设定——攻击者只能查询模型并拿到 top-1 预测标签——生成 L2 对抗样本。

   • 问题：已有 hard-label 攻击（如 Boundary、Cheng et al. 2019 的 OPT-based）攻击单个样本通常需超过 20,000 次查询，因为每次函数求值都要二分搜索。
   • 方法：沿用 Cheng's formulation（寻找距决策边界最短的方向），但只估计方向导数的符号而非大小：对新方向在距离 g(θ) 处查询一次即可得到一个符号，Q 次查询构成梯度估计，配合新的零阶梯度下降更新（保留随机方向模长，区别于 ZO-SignSGD）。作者给出收敛分析：E[‖∇g(θ)‖²] = O(√d/√T + d/√Q)。
   • 主要结果（untargeted L2，Table 1）：MNIST 14,000 次查询时平均扰动 1.09、SR(ε=1.5) 94.0%（OPT 为 1.76 / 36.0%）；CIFAR-10 12,000 次查询时 0.13、SR(ε=0.5) 95.0%；ImageNet ResNet-50 上 30,000 次查询内中位扰动低于 3.0，作者称其他攻击需超过 200,000 次。
   • 作者结论：Sign-OPT 查询数比现有方法少 5–10 倍，多数情况下扰动更小，且解与白盒 C&W 相当；作者认为单查询符号预言机可普遍改进 hard-label 设定下的多种优化方法，可作为实际的查询高效鲁棒性评估工具。

   收起这一问

相关论文