1 概述

1.1 题目

??2021ICML：稀疏细微对抗攻击同伦算法 (Sparse and imperceptible adversarial attack via a homotopy algorithm)

1.2 代码

??Torch：https://github.com/VITA-Group/SparseADV_Homotopy

1.3 摘要

??稀疏对抗攻击仅需一些 $\ell_0$ 范化的像素便能愚弄深度神经网络 (DNN)。近期有工作将它与 $\ell_\infty$ 扰动幅度的细微扰动结合。由此产生的稀疏细微攻击呈现相关性，并揭示了更多的DNN与其脆弱性的内容。
??进一步，耦合了 $\ell_0$ 正则和非凸框约束的优化更加困难，相应地攻击也更具挑战性。一种同伦算法被提出来应对这一挑战，其在一个统一的框架中同时解决稀疏性和扰动界限：
??1）在每一次迭代中，非凸规划算法非单调加速近端梯度 (nmAPG) 需要优化 $\ell_0$ 正则对抗损失；
??2）为避免陷入局部最小值，添加了 $\ell_0$ 更改控制步骤，以及一个可选的攻击后步骤；
??3）扩展算法到结构稀疏正则；
??4）同时在攻击和非攻击领域验证所提出的同伦攻击 (Homotopy attack) 的有效性，数据集包括CIFAR-10和ImageNet。

1.4 Bib

@inproceedings{Zhu:2021:1286812877,
author		=	{Ming Kang Zhu and Tian Long Chen and Zhang Yang Wang},
title		=	{Sparse and imperceptible adversarial attack via a homotopy algorithm},
booktitle	=	{Proceedings of International Conference on Machine Learning},
pages		=	{12868--12877},
year		=	{2021},
url			=	{http://proceedings.mlr.press/v139/zhu21a.html}
}

2 方法

2.1 问题定义

??令 $\mathcal{X}$ 表示原始图像的集合，一个训练的DNN分类器用于将 $\mathcal{X}$ 中的每张图像 $x\in\mathbb{R}^n$ 转换为类标签 $y\in\mathcal{Y}=\{1,2,\dots,K\}$ 。给定图像 $x_0\in\mathcal{X}$ ，目标是找到一个稀疏细微扰动 $\delta\in\mathbb{R}^n$ ，其可以将图像 $x_0+\delta$ 误分类为类别 $t$ 。与此同时，扰动的数量应该尽可能小，扰动的量级亦是如此：
$\tag{1} \begin{array}{ll} \min_\delta&f(x_0+\delta,t)+\lambda\|\delta\|_0\\ s.t.&\|\delta\|_\infty\leq\epsilon,0\leq x_0+\delta\leq1. \end{array}$ ??这里 $f ()$ 是类似于交叉熵的损失函数、 $\lambda$ 是稀疏度控制参数，以及 $\epsilon$ 是允许的最大扰动量级。以上目标可以更改为非目标攻击：
$\tag{2} \begin{array}{ll} \min_\delta&f(x_0+\delta,y_0)+\lambda\|\delta\|_0\\ s.t.&\|\delta\|_\infty\leq\epsilon,0\leq x_0+\delta\leq1. \end{array}$ ??求解公式 (1) 和 (2) 的算法具有很多共同点，因此接下来重点讨论公式 (1)。另除非特别说明，两者的步骤是共同的。

2.2 nmAPG求解算法

??由于公式1中的约束均为框约束，因此可以简化为一个 $\delta\in[l,u]$ ，其中 $l,u\in\mathbb{R}^n$ ，以及 $0\in[l.u]$ 。令 $I_{[l,u]}$ 表示指示函数：
$I_{[l,u]}=\left\{ \begin{array}{ll} 0,&\delta\in[l,u]\\ +\infty,&否则. \end{array} \right.$ ??公式1可以重写为：
$\tag{3} \min_\delta f(x_0+\delta,t)+\lambda\|\delta\|_0+I_{[l,u]}(\delta).$ ??非凸和非平滑性使得公式3的求解似乎不可行。经典的加速近端梯度 (APG) 方法已被证明对凸优化问题是有效的，但仍不清楚通常的APG是否可以收敛到非凸规划的临界点。Li等人针对非凸和非光滑程序提出了两种收敛加速近端梯度方法，其中公式3是一种特殊情况，本文中采样线性搜索非单调APG (nmAPG) 算法。
??APG首先使用当前和先前的解决方案获得外推解决方案，然后解决近端映射问题。当扩展APG到非凸规划问题时，主要的挑战是防止由于振荡现象引起的错误外推。Li等人引入了一个监视器来防止和纠正错误的外推，使它们满足足够的下降特性。在实践中，由于不完全知道梯度的Lipstchiz常数，nmAPG使用以BB步长初始化的回溯搜索来搜索步长。
??接下来说明如何使用nmAPG来求解公式3。假设 $f$ 是一个平滑非凸函数，其梯度有Lipstchiz常数 $L$ 。给定 $\delta^k$ ，有：
$f(x_0+\delta,t)\leq f(x_0+\delta^k,t)+\nabla_\delta f(x_0+\delta^k,t)^T(\delta-\delta^k)+\frac{L}{2}\|\delta-\delta^k\|^2,$ 其中 $\|\cdot\|$ 是 $\|\cdot\|_2$ 的简化。
??然后考虑问题：
$\min_\delta f(x_0+\delta^k,t)+\nabla_\delta f(x_0+\delta^k,t)^T(\delta-\delta^k)+\frac{L}{2}\|\delta-\delta^k\|^2+\lambda\|\delta\|_0+I_{[l,u]},$ 其等价于
$\tag{4} \min_\delta \frac{L}{2}\|\delta-[\delta^k-\frac{1}{L}\nabla_\delta f(x_0+\delta^k,t)]\|^2\lambda\|\delta\|_0+I_{[l,u]}.$ ??令 $g(\delta)=\lambda\|\delta\|_0+I_{[l,u]}(\delta)$ ，公式4的解表示为：
$\tag{5} \text{Prox}_{\frac{1}{L}g}(\delta^k-\frac{1}{L}\nabla f(x_0+\delta^k,t))=\argmin_\delta\frac{L}{2}\|\delta-[\delta^k-\frac{1}{L}\nabla_\delta f(x_0+\delta^k,t)]\|^2\lambda\|\delta\|_0+I_{[l,u]}.$ ??事实上，其可以显式获得。令：
$S_L(\delta)=\delta-\frac{1}{L}\nabla_\delta f(x_0+\delta,t),\forall\delta\in[l,u],$ 以及
$\Pi_{[l,u]}(\delta)=\argmin\{\|y-\delta\|:y\in[l,u]\},\forall\delta\in\mathbb{R}^n.$ ??对于所有的 $i=1,2,\dots,n$ ，公式4的最优解为：
$\delta_i^{k+1}=\left\{ \begin{array}{ll} [\Pi_{[l,u]}(S_L(\delta^k))],&[S_L(\delta^k)]^2_i-[\Pi_{[l,u]}(S_L(\delta^k))-S_L(\delta^k)]_i^2>\frac{2\lambda}{L};\\ 0,&其他. \end{array} \right.$ ??由于 $g(\delta)=\lambda\|\delta\|_0+I_{[l,u]}(\delta)$ 是一个下半连续函数，在一些温和的条件下，可以确保nmAPG收敛到公式3的临界点。

2.3 扩展到分组稀疏

??分组稀疏于近期引入至对抗攻击以提供更多的结构性与可解释性的扰动。为了将我们的算法从按元素 $\ell_0$ 正则扩展到分组稀疏，需要重新制定问题和nmAPG。
??假设输入图像 $x_0$ 可以被划分为 $m$ 个组 $x^T=(x^T_{G_1},\dots,x^T_{G_m})$ ，那么关于分组稀疏和不可感知的问题可以转换为：
$\tag{6} \begin{array}{ll} \min_\delta&f(x_0+\delta,t)+\lambda\|\delta\|_{2,0}\\ s.t.&\|\delta\|_\infty\leq\epsilon,0\leq x_0+\delta\leq1, \end{array}$ 其中
$\|\delta\|_{2,0}=|\{i:\|\delta_{G_i}\neq0,i=1,2,\dots,m\}|.$ ??同样使用指示函数，有：
$\min_\delta f(x_0+\delta,t)+\lambda\|\delta\|_{2,0}+I_{[l,u]}(\delta).$ ??令 $f$ 是一个平滑非凸函数，其梯度是具有 Lipschitz常数 $L$ 的Lipschitzian。与公式4类似，考虑如下问题：
$\tag{8} \begin{aligned} &\min _{\delta} \frac{L}{2}\left\|\delta-\left[\delta^{k}-\frac{1}{L} \nabla_{\delta} f\left(x_{0}+\delta^{k}, t\right)\right]\right\|^{2}+\lambda\|\delta\|_{2,0} \\ &\quad+I_{[l, u]}(\delta) \\ &=\min _{\delta} \frac{L}{2}\left\|\delta-s_{L}\left(\delta^{k}\right)\right\|^{2}+\lambda\|\delta\|_{2,0}+I_{[l, u]}(\delta) \end{aligned}$ ??Beck和Hallak提出了比公式8更普遍问题的解决方案。尽管可以应用它们的推导，但为了完整起见，仍然展示了公式8的简明解决方案并给出了简单的证明。

??定理2.1. 公式8的最小解为，对于所有的 $i=1,2,\dots,m$ ：
$\delta_{G_{i}}^{k+1}=\left\{\begin{array}{ll} {\left[\prod_{[l, u]}\left(s_{L}\left(\delta^{k}\right)\right)\right]_{G_{i}},} & \text { }\left\|\left[s_{L}\left(\delta^{k}\right)\right]_{G_{i}}\right\|^{2}- \|\left[\Pi_{[l, u]}\left(s_{L}\left(\delta^{k}\right)\right)-s_{L}(\right. \left.\left.\delta^{k}\right)\right]_{G_{i}} \|^{2}>\frac{2 \lambda}{L}\\ 0，&\text { otherwise } \end{array}\right.$

??证明. 首先，由于按组独立，公式8可以分解为 $m$ 个子问题：
$\tag{10} \min _{\delta_{G_{i}}} \frac{L}{2}\left\|\left[\delta-s_{L}\left(\delta^{k}\right)\right]_{G_{i}}\right\|^{2}+\lambda \cdot \operatorname{sgn}\left(\left\|\delta_{G_{i}}\right\|\right)+I_{\left[l_{G_{i}}, u_{G_{i}}\right]}\left(\delta_{G_{i}}\right),$ ??如果 $\left\|\delta_{G_{i}}\right\|=0$ ，则意味着 $\delta_{G_{1}}=0$ ，则优化目标的值为 $\frac{L}{2}\left\|\left[s_{L}\left(\delta^{k}\right)\right]_{G_{i}}\right\|^{2}$ ；如果 $\left\|\delta_{G_{i}}\right\| \neq 0$ ，则 $\operatorname{sgn}\left(\left\|\delta_{G_{i}}\right\|\right)=1$ ，此时公式10变为：
$\tag{11} \lambda+\sum_{j \in G_{i}} \min _{\delta_{j}} \frac{L}{2}\left(\delta_{j}-\left[s_{L}\left(\delta^{k}\right)\right]_{j}\right)^{2}+I_{\left[l_{j}, u_{j}\right]}\left(\delta_{j}\right) .$ ??在公式11中，有最小解为 $\left[\Pi_{[l, u]}\left(s_{L}\left(\delta^{k}\right)\right)\right]_{j}, \quad \forall j \in G_{i}$ , which can be unified as $\left[\Pi_{[l, u]}\left(s_{L}\left(\delta^{k}\right)\right)\right]_{G_{i}}$ ，有最小值为：
$\lambda+\sum_{j \in G_{i}} \frac{L}{2}\left(\left[\Pi_{[l, u]}\left(s_{L}\left(\delta^{k}\right)\right)-s_{L}\left(\delta^{k}\right)\right]_{j}\right)^{2},$ 其可以被重写为 $\lambda+\frac{L}{2} \|\left[\Pi_{[l, u]}\left(s_{L}\left(\delta^{k}\right)\right)-\right.$ $\left.s_{L}\left(\delta^{k}\right)\right]_{G_{i}} \|^{2}$ 。因此对比两个优化目标，公式8的解可以由公式9获得。

??令 $g(\delta)=\lambda\|\delta\|_{2,0}+I_{[l, u]}(\delta)$ ，公式8的解表示为：
$\begin{aligned} &\operatorname{Prox}_{\frac{1}{\mathrm{t}} g}\left(\delta^{k}-\frac{1}{L} \nabla_{\delta} f\left(x_{0}+\delta^{k}, t\right)\right) \\ &=\underset{\delta}{\operatorname{argmin}} \frac{L}{2}\left\|\delta-\left[\delta^{k}-\frac{1}{L} \nabla_{\delta} f\left(x_{0}+\delta^{k}, t\right)\right]\right\|^{2}+\lambda\|\delta\|_{2,0} \\ &\quad+I_{[l, u]}(\delta) . \end{aligned}$ ??注意 $g(\delta)=\lambda\|\delta\|_{2,0}+I_{[l, u]}(\delta)$ 也是一个合法下半连续函数，nmAPG也能收敛到一个临界点。

2.4 于解中引入同伦 (Homotopy)

??使用正则化优化的现有稀疏对抗攻击方法通常预先选择一个特别的固定权重以控制稀疏性的正则化项。此设置过于理想化，在实践中需要在调整权重时进行多次反复试验才能达到某些所需的稀疏度。为了缓解这个问题，我们使用同伦管理中的一个算法来制定nmAPG，其允许我们为所有正则化器雇佣一个权重降序序列以完成优化。它可以保证多阶段同伦解。在每一个阶段中，使用nmAPG优化公式1直接达到最大内循环次数。这可以从最后一个阶段不断地提供一个稀疏的初始解，用于下一个阶段的优化，从而得到最终的稀疏解。
??尽管同伦是一个用于凸优化的高效灵活策略，但是它不能直接应用于如DNN对抗攻击这样的高维非凸问题。例如优化函数是高度非凸的，即使公式1的nmAPG的输入扰动是稀疏的，nmAPG的收敛解也可能是一个糟糕的局部最小值且可能不稀疏。接下来描述一些稳定策略。

2.4.1 初始化权重搜索

??权重 $\lambda$ 的初始值对于接下来的性能有很大影响。对于同伦，公式1的理想初始权重应当使得nmAPG的解 $\delta$ 接近 $0$ ：
??1）以粗粒度方式增加 $\lambda$ ，直到一次迭代的nmAPG给出 $\delta=0$ ，因为如果 $\lambda$ 足够大，nmAPG将专注于优化稀疏函数；
??2）以相对细粒度的方式减小 $\lambda$ ，直到 nmAPG的第一次迭代开始更新 $\delta$ ；
??3）获得的 $\lambda$ 乘以指定常数 $c$ 以更好地执行稀疏约束。算法1总结了该过程。

2.4.2 通过 $\ell_0$ 范数变化来附加稀疏控制

??即使有一个好的初始化权重， $\ell_0$ 正则的同伦解仍然对沿同伦路径的正则化参数 $\lambda$ 敏感，这可能在公式1的损失函数与正则器均非凸时，无法准确地控制稀疏度。此外，由于公式1的 $\lambda$ 固定，哪怕nmAPG的输入解是稀疏的，器收敛解也可能是非稀疏的。因此有必要引入额外的稀疏控制。
??特别地，在同伦的每次外循环中，我们限制 $\ell_0$ 的最大数为 $v$ 。假设 $r$ 是当前同伦外循环中对 nmAPG的输入扰动的 $\ell_0$ 范数。然后，在nmAPG的内循环结束时，我们简单地保留具有最高 $(r + v)$ 绝对值的 $\delta$ ，并将所有其他 $\delta$ 减少到 0。这将保持扰动的非零条目数量稳定增加，从而避免了权重的小幅减少使扰动的 $\ell_0$ 范数突然增加的情况。
??在同伦算法中， $v$ 的值是一个输入常量。当满足以下条件时，它会临时更新为一个小的正整数输入到nmAPG：
$\tag{12} \frac{\|\delta^{k+1}\|_1}{\|\delta^{k+1}_0\|_0}\leq\epsilon*\gamma,$ 其中 $\gamma<1$ 是一个用户指定的常量。这样设置的原因是，如果公式12满足， $\delta^{k+1}$ 的平均扰动量级将远小于不可见阈值 $\epsilon$ ，这意味着 $\|\delta^{k+1}\|_0$ 实体的数量不足以攻击分类模型。因此 $v$ 被设置为一个临时正整数，nmAPG将在很小的 $v$ 下优化直接与公式12相逆。

2.4.3 优化攻击的扰动

??上述策略已经可以生成稀疏对抗扰动。然而，我们注意到同伦算法有时仍会陷入局部最小，这似乎对于非凸 $f$ 是不可避免的。此时，随着同伦算法的减小，扰动的 $\ell_1$ 范数与相应的 $\ell_0$ 范数不成比例地增加，这意味着该算法不能有效地使用被扰动的条目，并且满足不等式公式12。因此该公式被看作是一个促发条件，表内nmAPG已经陷入局部最优。
??为了缓解这个问题，提出一些“推动”来帮组算法更快地逃离局部最小。在同伦算法的外循环中，检查公式12是否满足。如果满足，则执行以下攻击后扰动步骤：
$\tag{13} \begin{array}{ll} \min_\delta&w_1f(x_0+\delta,t)+w_2\|\delta\|_p\\ s.t.&\|\delta\|_\infty\leq\epsilon,0\leq x_0+\delta\leq1, \end{array}$ 其中 $w_1\gg w_2$ ， $p$ 是 $1$ 、 $2$ ，或者 $\infty$ ，以及 $\delta$ 是仅针对nmAPG阶段的输出扰动的非零条目强制执行。
??关于 $w_1\gg w_2$ 的假设使得优化器能够聚焦于最小化函数 $f$ ，而 $\|\delta\|_p$ 的值可能增加。而当公式12违背时，这说明算法可能已经逃离局部最小。由于仅提供了一些推动方向而不是准确的更新，使用梯度下降优化公式13的迭代次数与当前的 $\ell_0$ 成比例。在攻击后阶段之后，结合下一次同伦外循环中 $v$ 较小的nmAPG 阶段，扰动的 $\ell_1$ 范数会增加，从而违反不等式公式12，然后可以将 $v$ 恢复正常。
??算法2展示了完整的同伦攻击过程。