通过凸外对抗多面体实现可证明的对抗样本防御

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

   如何训练对任意范数有界对抗扰动可证明鲁棒的深度 ReLU 分类器，并在测试时零漏报地检测对抗样本。

   核心问题：训练对任意范数有界对抗扰动可证明（provably）鲁棒的深度 ReLU 分类器，而非只在已知攻击下表现好。

   • 问题场景与重要性：作者称对抗样本攻防陷入"军备竞赛"——distillation 等防御相继被新攻击攻破，黑盒攻击同样有效，检测对抗样本也很困难；对高风险应用，分类器被骗一次的代价可能很高。
   • 现有方法的不足：作者认为，精确验证方法（SMT、整数规划）本质上是组合式的，难以扩展到中等规模网络，且计算代价太高、无法嵌入鲁棒训练流程；layerwise 界（如 Parseval networks）则比本文的外逼近界差"多个数量级"（附录 B.1 给出数值对比）。
   • 核心观察：对对抗多面体（adversarial polytope，即输入在范数球内扰动时末层激活可达的集合）构造凸外逼近；若外逼近内没有点能改变预测类别，就证明该样本鲁棒。该外逼近上的最坏情况损失是一个线性规划，其对偶问题本身可写成一个类似反向传播的网络。
   • 论文提出的内容：一种鲁棒优化训练流程，用对偶网络单次反向传播算出鲁棒损失的可证明上界，用标准 SGD 变体最小化它；同时给出测试时检测对抗样本的证书（零漏报，但可能误报正常样本）。
   • 威胁模型：
     • 攻击者目标：对输入施加扰动使分类器误分类。
     • 攻击者知识：作者假设攻击者拥有分类器的全部知识（full knowledge of the classifier），不依赖"security through obscurity"。
     • 攻击者能力：ℓ∞ 范数不超过 ε 的扰动（实验用 ε=0.1/0.05/0.01）；论文称方法可扩展到其他 ℓp 范数，但实验只做 ℓ∞。
     • 受害系统：k 层前馈 ReLU 网络（含卷积等线性算子层）。

   收起这一问

2. 02有哪些相关研究？

   相关工作分四组：精确组合验证、可计算的鲁棒界、同期认证防御，以及鲁棒优化与对抗训练的连接。

   精确（组合式）验证

   • SMT 求解器（Huang et al., 2017；Katz et al., 2017；Ehlers, 2017；Carlini et al., 2017）与整数规划方法（Lomuscio & Maganti, 2017；Tjeng & Tedrake, 2017；Cheng et al., 2017）——对精确对抗多面体做推理。论文指出其中 PLANET（Ehlers, 2017）也用了与本文相同的 ReLU 线性松弛，但只作为组合求解的子步骤；作者认为这类方法难以扩展到中等规模网络，且代价太高、无法嵌入训练。

   可计算的鲁棒界

   • Parseval networks（Cisse et al., 2017）——正则化权重矩阵的 ℓ2 算子范数；Peck et al. (2017)——限制逐层范数扩张。论文称本文研究了类似的 layerwise 界，并给出对比称其通常比本文外逼近界差多个数量级（附录 B.1）。
   • Hein & Andriushchenko (2017)——两层网络 ℓ2 扰动的可证明保证，但训练时用的是界的替代物而非精确界；Sinha et al. (2018)——基于 Wasserstein 分布距离的认证鲁棒性，论文称不清楚如何转化为传统的范数有界对抗模型。

   最相近的同期工作

   • Raghunathan et al. (2018)——基于半定规划松弛对抗多面体（同样经对偶化为特征值问题）并用于鲁棒训练。论文指出其只适用于两层全连接网络，而本文适用于含卷积等任意线性算子层的深度网络；作者称在 MNIST 上其保证界为 35% 误差、本文鲁棒界为 5.8% 误差，同时指出在对方的小网络上两种界互补（本文鲁棒测试误差更低、常规测试误差更高），作者认为结合两种界是未来方向。

   鲁棒优化与对抗训练

   • 鲁棒优化（Ben-Tal et al., 2009；Xu et al., 2009）——在问题数据属于有界集合时求解优化；Goodfellow et al. (2015) 指出线性模型的对抗鲁棒性等价于 ℓ1 权重惩罚；Madry et al. (2017) 用非凸 min-max 公式做对抗训练。作者将本文定位为这一连接的下一步：因采用凸松弛，可给出可证明的界。

   基线与基准：实验中的攻击基线为 FGSM（Goodfellow et al., 2015）和 PGD（Madry et al., 2017），对比对象为常规训练的相同结构网络；数据集为 MNIST、Fashion-MNIST、HAR、SVHN 及一个 2D 合成例子。

   收起这一问

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

   把对抗多面体的凸外逼近写成 LP，用其对偶网络单次反向传播得到可证明的鲁棒损失上界，再用 SGD 最小化。

   整体思路：对 ReLU 网络的对抗多面体构造凸外逼近，把"外逼近内最坏情况损失"写成一个线性规划；证明该 LP 的对偶可行域本身是一个类似反向传播的网络（对偶网络），从而用一次修改过的反向传播即可得到鲁棒损失的可证明上界，再用标准随机梯度方法训练。

   问题设定与凸外逼近

   • 网络为 k 层前馈 ReLU 网络，ẑi+1 = Wi zi + bi，zi = max{ẑi, 0}，Wi 可为矩阵乘或卷积等线性算子。
   • 对抗多面体定义为 Z_ϵ(x) = {f_θ(x+Δ) : |Δ|_∞ ≤ ϵ}，即输入在 ℓ∞ 球内扰动时末层激活的可达集合；该集合非凸。
   • 关键松弛：已知 ReLU 前激活的逐元素上下界 ℓ、u 时，把 ReLU 等式替换为其上凸包络（z ≥ 0、z ≥ ẑ、−uẑ + (u−ℓ)z ≤ −uℓ）；ℓ、u 同号时松弛精确。替换后的外逼近记为 Z̃ε(x)。

   对偶网络

   • 在外逼近上最小化 cT ẑk（c = ey* − ey_targ）是一个 LP；若对所有目标类目标值都为正，则证明该样本在 ε 球内鲁棒。
   • Theorem 1：该 LP 的对偶可写成一个 k 层前馈网络 gθ(c, α)：νk = −c，ν̂i = WiT νi+1，对跨零激活（集合 Ii）引入自由变量 αi,j ∈ [0,1]，形式类似 leaky ReLU。
   • 实践中不显式优化 α，而取固定的对偶可行解 αi,j = ui,j / (ui,j − ℓi,j)，使整个反向传播成为线性函数；作者称该选择由 ReLU 松弛的共轭集合推导得到（附录 A.3），且实践中界相当紧。
   • 对 ℓp 范数扰动，只需把对偶目标中的 ℓ1 范数换成对偶范数 ℓq；论文实验只做 ℓ∞。

   逐层激活界计算

   • 对偶目标 Jε(x, gθ(c)) 可对任意线性函数 cT ẑk 给出界，取 c = I 和 c = −I 即得各激活的上下界（Algorithm 1，逐层递增计算）。
   • 计算代价主要来自两处：把"单位矩阵"逐维前向通过网络的输入层，以及对每个跨零激活从中间层各做一次前向；作者承认这是扩展性最差的部分，把 bottleneck 层、随机投影等列为未来工作。

   鲁棒优化与保证

   • Theorem 2：对满足平移不变性（Property 1）的单调损失 L（交叉熵、hinge、0-1 损失均满足），最坏情况对抗损失可被 L(−J_ϵ(x, g_θ(e_y 1^T − I)), y) 上界，该量称为鲁棒损失；整体目标可微，可用任意 SGD 变体与 autodiff 训练。
   • Corollary 1：若 Jε(x, gθ(ey*1T − I)) ≥ 0（逐元素），则该样本在 ε 球内可证明鲁棒；不满足证书的样本比例记为 robust error，是任何对抗攻击可达误差的可证明上界。
   • Corollary 2：把真实标签换成预测标签 ŷ，同样条件成立则 x 不可能是对抗样本——测试时检测零漏报（不会漏掉任何对抗样本），但可能误报正常样本。
   • 还可用 Newton 法对每个样本求存在鲁棒证书的最大 ε，作为到决策边界的 ℓ∞ 距离下界（式 17）。

   收起这一问

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

   在 2D 合成数据、MNIST、Fashion-MNIST、HAR、SVHN 上训练鲁棒网络，报告 clean/FGSM/PGD 误差与鲁棒误差上界。

   实验设置

   • 被测网络：2D 例子用 2-100-100-100-100-2 全连接网络；MNIST、Fashion-MNIST、SVHN 用同一 ConvNet（两个卷积层 16、32 通道，stride 2，后接 100、10 的全连接层）；HAR 用单层 500 隐单元全连接网络。
   • 数据集：MNIST、Fashion-MNIST（Xiao et al., 2017）、HAR（Anguita et al., 2013）、SVHN，以及随机生成的 12 点 2D 二分类数据（附录 B.1）。
   • 攻击基线与对比：FGSM 与 PGD；对比模型为常规训练（normal train）的相同结构网络。
   • 指标：test error、FGSM error、PGD error、robust error bound（不可证明鲁棒的样本比例，是任意攻击可达误差的上界）。
   • 训练参数：Adam；MNIST/Fashion-MNIST/SVHN 学习率 0.001，HAR 0.0001；batch size 50（SVHN 为 20）；均训练 100 epochs；MNIST 与 SVHN 用 ε 递增调度（MNIST 前 50 epochs 从 0.05 均匀升到 0.1，SVHN 从 0.001 升到 0.01）。
   • 硬件：单块 Titan X GPU；MNIST 鲁棒训练 100 epochs 约 5 小时。

   主结果

   据 Table 1（各行为不同问题与是否鲁棒训练，ε 见表）：

   表格较宽，可左右滑动

   问题	鲁棒训练	ε	Test error	FGSM	PGD	Robust bound
   MNIST	×	0.1	1.07%	50.01%	81.68%	100%
   MNIST	√	0.1	1.80%	3.93%	4.11%	5.82%
   Fashion-MNIST	×	0.1	9.36%	77.98%	81.85%	100%
   Fashion-MNIST	√	0.1	21.73%	31.25%	31.63%	34.53%
   HAR	×	0.05	4.95%	60.57%	63.82%	81.56%
   HAR	√	0.05	7.80%	21.49%	21.52%	21.90%
   SVHN	×	0.01	16.01%	62.21%	83.43%	100%
   SVHN	√	0.01	20.38%	33.28%	33.74%	40.67%

   • 作者指出，鲁棒模型的 robust error bound 低于常规训练模型被 PGD 攻击达到的误差；鲁棒模型上 FGSM/PGD 误差均低于其鲁棒界。
   • 代价是 clean 误差上升：四个数据集上鲁棒模型的 test error 均高于常规模型（见表）。
   • 作者称 5.8% 的 MNIST 鲁棒误差对比 Raghunathan et al. (2018) 的 35% 保证界，且是作者所知最大的可证明验证网络。

   界的紧度分析

   • 测了什么：在 MNIST 卷积模型上精确求解原始 LP 并与对偶下界比较（Figure 11）；在 HAR 单层网络上对不同 ε 训练后比较 FGSM 误差与鲁棒界（Table 2）。
   • 结果：Table 2 显示 HAR 单层网络训练后各 ε 下界与 FGSM 误差几乎相等（如 ε=0.05 时 FGSM 22.20%、界 22.80%；ε=1 时两者均为 81.80%），作者据此称此时界是紧的；Figure 11 中鲁棒训练模型的对偶下界与原始解接近，随机初始化和常规训练模型的差距更大（作者称，图中可见三组曲线分离程度不同）。
   • 随机网络可视化：附录 Figure 6 显示随机网络上 ε 小（0.05）时外逼近与真实多面体几乎重合，ε 增大（0.1、0.25）后界变松；layerwise 朴素界给出 ẑk,1 ∈ [−11.68, 13.47] 而真实范围约 [1.81, 1.85]，作者称其"基本无用"。

   2D 例子与最大 ε 距离

   • 2D 例子：ε=0.08 时常规训练的分类器在每个点的 ℓ∞ 球内都存在误分类点；鲁棒训练达到零鲁棒误差（Figure 3，作者称）。
   • 最大 ε 距离：用 Newton 法（5–6 步）计算每个测试样本可证明鲁棒的最大 ε（Figure 5）；常规训练下正确分类样本到决策边界的下界约 0.007，鲁棒训练（ε=0.1）后推到 0.1；误分类样本总体更靠近决策边界（作者称）。

   其他消融与分析

   • ε 调度：MNIST 上直接以 ε=0.1 训练时部分随机种子不收敛，从前 50 epochs 由 0.05 均匀升到 0.1 后这些种子均能收敛（附录 B.2）。
   • 卷积核稀疏性：鲁棒训练后 MNIST 两层卷积核高度稀疏、部分全零，作者归因于式 (6) 中的 ℓ1 项（Figure 8、9）。
   • 激活集合分布：Figure 10 直方图显示各层跨零集合 Ii 的激活数量较少，作者称这使界更紧且计算更省。
   • SVHN 学习曲线：Figure 14 中按调度 ε 计算的指标在前若干 epoch 后持续上升，作者认为这说明给定模型容量下 SVHN 的鲁棒训练已达瓶颈、需要更大模型。

   收起这一问

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

   作者指出扩展性与攻击模型覆盖两大方向；实验限于四个中小数据集与 ℓ∞ 范数。

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

   • 扩展性（3.3 节与 4.4 节）：计算激活界需要把单位矩阵逐维前向通过网络（每个输入维度一个样本，中间层每个跨零激活还要更多），对 ImageNet 规模"完全不可行"；作者提出 bottleneck 层、其他对偶界、随机投影等可能手段，但明确说这仍是 future work。
   • 攻击模型覆盖（5. Conclusion）：需要刻画范数球之外的攻击，作者举例 Sharif et al. (2016) 的眼镜攻击和 Engstrom et al. (2017) 的旋转平移攻击都不是 ℓ∞ 有界的，认为理解更广泛的对抗样本集合（可能是高度非凸的输入集合）还有大量工作。
   • 结合互补的界（2. Background and Related Work）：作者指出在小网络上本文的界与 Raghunathan et al. (2018) 的 SDP 界互补（本文鲁棒测试误差更低、常规测试误差更高），认为寻找结合两种界的方法是有用的未来方向。
   • 方法的更广泛应用（5. Conclusion）：作者认为优化松弛凸网络、用非凸网络表示对偶问题这类通用技术，可能适用于对抗样本之外、需要对网络输入或隐空间做优化的问题。

   实验覆盖范围

   • 被测网络共三种结构：2D 例子的 5 层全连接网络、MNIST/Fashion-MNIST/SVHN 共用的两层卷积 ConvNet、HAR 的单层 500 隐单元网络（第 4 节）。
   • 评测的攻击为 FGSM 与 PGD，扰动均为 ℓ∞ 范数；论文称方法可扩展到其他 ℓp 范数，但实验只报告 ℓ∞（3.2 节、Table 1）。
   • 训练均用 Adam、100 epochs，batch size 50（SVHN 为 20）；论文未报告每个结果的重复次数或方差（附录 B）。
   • 界的紧度实证在 MNIST 卷积模型（Figure 11）和 HAR 单层网络（Table 2）上进行；Fashion-MNIST 与 SVHN 未报告原始 LP 对比。
   • 论文未报告测试时检测（Corollary 2）的误报率数值，只说明检测零漏报、可能误报正常样本（3.5 节）。

   收起这一问

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

   用对偶网络把鲁棒训练化为几次前向/反向传播，在四个数据集上给出可证明的鲁棒误差上界。

   一篇关于可证明对抗鲁棒性的防御论文：针对"防御总被新攻击绕过"的军备竞赛局面，作者提出训练对任意 ℓ∞ 有界扰动可证明鲁棒的深度 ReLU 分类器，假设攻击者完全了解模型。

   • 方法：对对抗多面体构造凸外逼近（ReLU 的线性松弛），把最坏情况损失写成 LP；证明其对偶可行域是一个类似反向传播的网络，取固定对偶可行解后单次反向传播即得鲁棒损失上界，整体可微、用标准 SGD 训练；同一证书可在测试时零漏报地检测对抗样本。
   • MNIST（ε=0.1，两层卷积网络）：鲁棒测试误差上界 5.82%，FGSM/PGD 仅达 3.93%/4.11%；常规训练模型 PGD 误差 81.68%（Table 1）。
   • 其他数据集：Fashion-MNIST（ε=0.1）鲁棒界 34.53%，HAR（ε=0.05）21.90%，SVHN（ε=0.01）40.67%，均低于常规模型的 PGD 误差（Table 1）。
   • 界的紧度：HAR 单层网络训练后各 ε 下界与 FGSM 误差几乎相等（Table 2）；MNIST 鲁棒模型上对偶下界与精确 LP 解接近（Figure 11）。
   • 代价与结论：clean 误差上升（MNIST 1.07%→1.80%），MNIST 训练约 5 小时、比常规训练贵两到三个数量级；作者称这是当时最大的可证明验证网络，并指出扩展到 ImageNet 规模和覆盖范数球之外的攻击是后续方向。

   收起这一问

相关论文