Square Attack：基于随机搜索的查询高效黑盒对抗攻击

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

   作者提出不依赖梯度的 score-based 黑盒攻击 Square Attack，解决黑盒攻击查询多、成功率低的问题。

   核心问题：现有 score-based 黑盒对抗攻击查询效率低、成功率有时明显低于白盒攻击，而基于梯度的攻击易受梯度遮蔽影响。

   • 问题场景：对抗样本对安全关键的机器学习应用构成威胁；许多防御被更强的攻击攻破，其中梯度混淆或遮蔽（gradient obfuscation/masking）常使看似鲁棒的模型实际不鲁棒（按作者说法）。
   • 现有方法不足：作者称，基于有限差分梯度估计的黑盒攻击受梯度遮蔽影响，且需要查询分类器很多次才能找到对抗样本，成功率有时显著低于白盒攻击。
   • 核心观察：成功的 l∞ 扰动通常位于 l∞ 球与图像空间交集的角点；卷积网络对局部方形、每通道同号的扰动敏感，因此可用随机搜索配合方形更新。
   • 论文提出：Square Attack，一种基于随机搜索的 score-based 黑盒 l2 与 l∞ 攻击，配合特定初始化与方形更新；作者称其在无目标设置下查询效率与成功率均优于已有方法。
   • 威胁模型：
     • 攻击者目标：生成 lp 范数约束下的对抗样本，分无目标（改变预测类别）与有目标（指定类别）两种。
     • 知识：score-based，即可查询分类器输出的各类别概率分布，但无法访问模型内部。
     • 能力：对每个点有查询预算（如 ImageNet 实验 10,000 次），不依赖替代模型等额外信息。
     • 受害系统：图像分类器（ImageNet、MNIST、CIFAR-10 上的常规模型与对抗训练/防御模型）。

   收起这一问

2. 02有哪些相关研究？

   相关工作分四组：梯度估计类、随机搜索/进化类、角点搜索类与其他威胁模型；基线为 Bandits、SignHunter 等。

   梯度估计类 score-based 攻击

   • [6,30,56]——通过在输入点周围采样噪声近似梯度；作者称这类方法在高维输入（如图像分类）上需要很多查询。
   • 降维改进：[6] 用数据主成分、[55] 在自编码器潜空间搜索、[31] 用低维噪声分布（Bandits）。

   随机搜索与进化策略类

   • [3]（GenAttack）——用遗传算法生成对抗样本，可降低随机化与离散化防御的鲁棒准确率。
   • [28]（SimBA）——可看作随机搜索变体，在正交基上选搜索方向、每步最多试两个候选更新；作者指出其每步只做小的 l2 修改且正交更新无法撤销，查询效率可能次优。

   基于 l∞ 球角点搜索的攻击

   • [49]（Parsimonious）与 [2]（SignHunter）——在粗网格上做局部搜索、分量只取 ±ε，再细化网格；[2] 将此解释为梯度符号估计。
   • [39]（DFO）——用进化算法做离散与连续优化，借用 [31] 的“tiling trick”把扰动划分为方形；作者指出其方形的大小和位置在开始时固定、不优化，且这类离散优化方法不易直接适配 l2 范数。
   • [50]（BayesAttack）——基于贝叶斯优化，作者称只在低查询区间有竞争力。

   其他威胁与知识模型

   • 决策型（decision-based）攻击 [9,16,27,11,13]——只能查询分类器决策，场景更受限。
   • 替代模型/迁移类 [44,57,17,23,52] 与利用目标数据分布的 [35]——作者指出这类额外知识带来的查询效率提升未计入训练替代模型的计算成本，在 ImageNet 规模上尤其高。

   基线与基准：论文在 ImageNet 上对比 Bandits [31]、Parsimonious [49]、DFOc/DFOd [39]、SignHunter [2]、SimBA-DCT [28]（l2）与 BayesAttack [50]（低查询区间）；在 MNIST/CIFAR-10 防御模型上对比 PGD（1/10/100/10000 次重启）、Bandits、SignHunter、SimBA。

   作者将本文定位为：不依赖梯度信息、不用替代模型的 score-based 攻击，与固定网格方法的区别在于同时优化方形的位置与颜色，且同一框架覆盖 l∞ 与 l2 两种范数。

   收起这一问

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

   Square Attack 用随机搜索，每步采样局部方形更新使扰动近似位于可行集边界，l∞ 与 l2 各有专用采样分布。

   整体思路：把找对抗样本写成约束优化问题，用随机搜索求解；每步在随机位置采样一个局部方形更新，使扰动在投影前位于 lp 球边界，从而几乎用满扰动预算。

   问题设定

   • 分类器 f : [0,1]^d → R^K；无目标攻击要求 arg max_k f_k(x̂) ≠ y 且 ‖x̂−x‖_p ≤ ε、x̂ ∈ [0,1]^d。
   • 写成约束优化：min_{x̂∈[0,1]^d} L(f(x̂), y)，s.t. |x̂−x|_p ≤ ϵ；实验用间隔损失 L(f(x̂), y) = f_y(x̂) − max_{k≠y} f_k(x̂)。

   通用算法框架（Algorithm 1）

   • 每步：按预定递减计划取方形边长 h(i)，采样更新 δ，把 x̂+δ 投影到 lp 球与 [0,1]^d，若损失下降则接受。
   • 找到对抗样本即停止；时间复杂度由 f 的评估次数主导，最多 N 次。
   • 与经典随机搜索的区别：每步扰动 x̂−x 在投影前位于球边界，且修改集中在方形区域；与 [31,49,39] 的区别是方形位置与颜色都被优化，而非固定在网格上。
   • 方形边长：h 为最接近 √(p·w²) 的正整数（l2 版 h ≥ 3）；初始 p 是唯一自由参数；N = 10000 时在迭代 {10, 50, 200, 1000, 2000, 4000, 6000, 8000} 处将 p 减半。

   l∞ 版设计

   • 初始化：宽度为 1 的竖条纹，每条颜色从 {−ε, ε}^c 均匀采样；作者称发现卷积网络对这类扰动敏感。
   • 采样分布（Algorithm 2）：随机选位置，取 h×h 方形窗口，每个颜色通道独立从 {−2ε, 2ε} 采一个值、窗口内同号；投影（裁剪）后远离边界的分量都取 x_i ± ε，即扰动位于 l∞ 球的角点。

   l2 版设计

   • 初始化：5×5 网格状平铺，每块用下述 η 形状，整体缩放到 l2 范数 ε 并裁剪。
   • 更新形状：η 有两个绝对值大、符号相反的“中心”，离中心越远绝对值越小但不为零（Fig. 2 给出 h = 8 的示例）；作者称这种局部高对比更新提升查询效率。
   • 采样分布（Algorithm 3）：随机选两个方形窗口 W1、W2，把 W2 的扰动置零、将其 l2 预算转移给 W1，使新扰动仍在半径 ε 的球面上（Proposition 1 保证 ‖x̂+δ−x‖₂ = ε）。

   理论依据

   • Proposition 2：在 E[δ_t]=0 与 Eq. (3) 的假设下，随机搜索以步长 γ_t = γ/√T 收敛到 L-smooth 目标的临界点；作者说明该假设对实际采样分布 P 不直接成立（Sup. A.3 给出反例），但对逐像素独立采样的 P_multiple 成立（Sup. A.4）。
   • Proposition 3：在只能修改 k 个元素时，（近似）方形能最大化被完全覆盖的 s×s 卷积滤波器数量，为方形优于矩形提供直觉。
   • 有目标攻击（Sup. E.1）：改用目标类交叉熵损失，作者称间隔损失在有目标设置下查询效率次优。

   收起这一问

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

   在 ImageNet 三模型上对比五种黑盒攻击，并在 MNIST/CIFAR-10 鲁棒模型上与白盒 PGD 比较。

   实验设置

   • 被测模型：ImageNet 上用 PyTorch 预训练的 Inception v3、ResNet-50、VGG-16-BN；附录加测 DRN-A-50、DRN-C-42、DRN-D-38；MNIST 上用 [37] 的 l∞ 对抗训练模型与 TRADES [61]；CIFAR-10/MNIST 上用 CLP、LSQ [33] 与 post-averaging 防御 [36]。
   • 数据：ImageNet 验证集 1,000 张图；有目标 l2 实验用 200 个点；SignHunter 有目标评测用 100 个点。
   • 基线：Bandits [31]、Parsimonious [49]、DFOc/DFOd [39]、SignHunter [2]、SimBA-DCT [28]、BayesAttack [50]（低查询区间）；除注明外使用原论文代码与建议参数，部分结果取自原论文。
   • 指标：失败率、成功攻击的平均/中位查询数（只对原本分类正确且攻击成功的点统计）、鲁棒准确率。
   • 预算与参数：无目标攻击每点 10,000 次查询；l∞ 取 ε = 0.05，l2 取 ε = 5；Square Attack 的 p 对所有模型固定为 0.05（l∞）与 0.1（l2）。
   • 重复次数：主实验未报告重复；附录 D 用 10 个随机种子测稳定性。

   主结果

   ImageNet 无目标攻击，10,000 查询预算（据 Table 2；Parsimonious 只报告了 Inception v3）：

   表格较宽，可左右滑动

   范数	攻击	失败率 I/R/V	平均查询 I/R/V	中位查询 I/R/V
   l∞	Bandits	3.4/1.4/2.0%	957/727/394	218/136/36
   l∞	DFOc–CMA	0.8/0.0/0.1%	630/270/219	259/143/107
   l∞	DFOd–Diag. CMA	2.3/1.2/0.5%	424/417/211	20/20/2
   l∞	SignHunter	1.0/0.1/0.3%	471/129/95	95/39/43
   l∞	Square Attack	0.3/0.0/0.0%	197/73/31	24/11/1
   l2	Bandits	9.8/6.8/10.2%	1486/939/511	660/392/196
   l2	SimBA-DCT	35.5/12.7/7.9%	651/582/452	564/467/360
   l2	Square Attack	7.1/0.7/0.8%	1100/616/377	385/170/109

   • 作者称 Square Attack 在所有模型与范数下失败率最低（除 l2 在 Inception v3 上为 7.1% 外均 < 1%），且几乎总是查询更少。
   • 作者称最接近的竞争者 SignHunter 平均查询仍多 1.8–3 倍且失败率更高；DFOc–CMA 中位查询有竞争力，但失败率更高、平均查询多 2–7 倍。
   • 因 Square Attack 失败率低，其查询统计偏向“难”样本；只在三者都成功的点上重算（Table 3），作者称平均查询至少改进 1.5×、中位至少 2×。

   与白盒攻击的比较

   • 鲁棒模型（Table 4）：MNIST l∞ ε = 0.3，p = 0.8、20k 查询、50 次随机重启；Madry 等 [37] 模型上鲁棒准确率 88.25%（白盒 SOTA 88.13%），TRADES [61] 上 92.58%，作者称超过 [20] 的白盒攻击、取得新 SOTA。
   • 梯度遮蔽（Table 5）：[37] 的 l∞ 对抗训练模型在 l2 威胁下，ε = 2.5 时 Square Attack 单次运行鲁棒准确率 2.4%，PGD100 为 36.0%，SignHunter 94.9%、Bandits 32.4%、SimBA 75.8%；作者称 Square Attack 不受梯度遮蔽影响。
   • CLP/LSQ 防御（Table 6）：p = 0.3、20k 查询；MNIST ε = 0.3 时 CLP 6.1%、LSQ 2.6%（PGD 万次重启分别为 4.1%、5.0%）；作者称多数情况下单次运行即接近 PGDR，且平均优于 Bandits 与 SignHunter。

   有目标攻击与其他结果

   • 有目标（Table 9，Inception-v3）：l∞（100k 查询预算）Square Attack 失败率 0.0%、平均 4584 次查询，作者称比最近的竞争者少 1.5 倍；l2（60k 预算、200 点）失败率 33.5%，高于 Bandits 24.5% 与 SimBA-DCT 25.5%，但平均与中位查询更低（19794/15946）。
   • post-averaging 防御（Table 12）：ε = 8/255，Square Attack（p = 0.3）把鲁棒准确率从 PGD 测得的 88.4% 降到 15.8%（CIFAR-10）、从 76.1% 降到 0.4%（ImageNet）；作者称该防御不如其声称的鲁棒。
   • 膨胀卷积架构（Table 10）：DRN-A-50/C-42/D-38 上 l∞ ε = 0.05 失败率均 0.0%，平均查询 86/57/48；作者称攻击不限于标准卷积网络。

   其他消融与分析

   • 设计消融（Table 1，ResNet-50，l∞ ε = 0.05）：方形+每通道同号+竖条纹为 73 次平均查询，随机形状+逐像素符号为 401；作者称方形优于矩形（93）与随机形状。
   • 初始化：竖条纹比均匀初始化平均查询少约 25%，中位减半（Table 1）。
   • p 的敏感性（Fig. 5）：l∞ 在 p ∈ [0.0125, 0.4] 失败率均 0.0%、平均查询低于 140；l2 在 p ∈ [0.05, 0.4] 表现接近，p ∈ {0.0125, 0.025} 时略差。
   • 随机种子稳定性（Table 8，10 个种子）：ImageNet ResNet-50 l∞ 失败率 0.0% ± 0.0%、平均查询 72 ± 2；MNIST l2 鲁棒准确率 16.0% ± 1.4%。
   • 不可感知扰动（Table 11）：ε = 4/255 时 VGG/ResNet-50/Inception v3 失败率 0.5/0.3/5.4%。
   • 低查询区间（Fig. 4、Fig. 6）：作者称 Square Attack 在 200 查询内优于包括 BayesAttack 在内的所有方法；Fig. 6 中 BayesAttack 与 DFO 的数据来自与作者的个人交流，分别在 500 与 10,000 个采样点上评估。

   收起这一问

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

   论文未设专门局限章节；实验覆盖三个 ImageNet 模型与若干 MNIST/CIFAR-10 防御模型。

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

   • 论文未专门讨论局限，没有 Limitations 或 Future Work 小节。以下为主文中作者明确写出的方法适用性说明：
   • 收敛分析不直接适用于实际的 l∞ 采样分布 P：Sec. 4.1 与 Sup. A.3 给出反例，说明 Eq. (3) 的假设对 P 不成立，只对逐像素独立采样的 P_multiple 成立，且作者称 P_multiple 表现不如 Algorithm 2 的分布。
   • l2 版“显著更难分析”（Sec. 4 开头），理论论证主要针对 l∞ 版。
   • 有目标 l2 攻击失败率高于竞争者：Sup. E.1 报告 Square Attack 失败率 33.5%，高于 Bandits 的 24.5% 与 SimBA-DCT 的 25.5%（查询数更低，但统计基于不同数量的成功点）。

   实验覆盖范围

   • 无目标主实验覆盖 ImageNet 上 Inception v3、ResNet-50、VGG-16-BN 三个模型，各 1,000 张验证集图像（Sec. 5.1）。
   • 有目标实验只在 Inception-v3 上做：l∞ 用 1,000 张图、100k 查询预算，l2 用 200 个点、60k 预算（Sup. E.1）。
   • 鲁棒模型与防御评测包括：MNIST 上 [37] 与 TRADES [61]（l∞ ε = 0.3）、[37] 模型在 l2 威胁下、CLP/LSQ [33]（MNIST 与 CIFAR-10）、post-averaging [36]（CIFAR-10 与 ImageNet）。
   • 附录补充：膨胀卷积架构 DRN-A-50/C-42/D-38（Table 10）、不可感知扰动 ε = 4/255（Table 11）、10 个随机种子的稳定性（Table 8）。
   • 论文未报告主实验的重复次数；部分对比结果取自原论文，Fig. 4/Fig. 6 中 BayesAttack 与 DFO 的逐查询成功率来自与原作者的个人交流且评估点数不同（500 与 10,000）。

   收起这一问

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

   作者提出基于随机搜索的黑盒攻击 Square Attack，作者称查询效率与成功率优于已有方法，且不受梯度遮蔽影响。

   Square Attack 是一种 score-based 黑盒对抗攻击，针对 l∞ 与 l2 范数约束的图像分类器，作者称其不需要梯度信息，因此不受梯度遮蔽影响。

   • 要解决的问题：作者称现有黑盒攻击查询次数多、成功率有时低于白盒攻击，而梯度遮蔽使基于梯度的评估失真。
   • 方法要点：随机搜索框架下，每步在随机位置采样局部方形更新，使扰动近似位于 lp 球边界；l∞ 版用竖条纹初始化、每通道同号更新，l2 版用双中心更新并在两窗口间转移扰动质量；唯一自由参数 p 控制初始方形大小。
   • ImageNet 主结果（Table 2）：无目标 l∞（ε = 0.05）在 Inception v3/ResNet-50/VGG-16-BN 上失败率 0.3/0.0/0.0%，平均查询 197/73/31；l2（ε = 5）失败率 7.1/0.7/0.8%，作者称优于 Bandits、SignHunter、DFO、SimBA-DCT 等。
   • 与白盒攻击比较：MNIST TRADES 模型上鲁棒准确率 92.58%（Table 4），作者称超过白盒攻击取得新 SOTA；对存在梯度遮蔽的模型，l2 ε = 2.5 时单次运行鲁棒准确率 2.4%，而 PGD100 为 36.0%（Table 5）。
   • 防御评估：post-averaging 防御在 ImageNet 上的鲁棒准确率从 PGD 测得的 76.1% 降至 0.4%（Table 12），作者称直接套用白盒 PGD 会导致不准确的鲁棒性估计。
   • 作者结论：作者认为该攻击即使在白盒攻击需要大量重启与迭代的场景下也可用于鲁棒性评估；后续工作 [21] 已将其纳入 AutoAttack。

   收起这一问

相关论文