[paper]DeepFool: a simple and accurate method to fool deep neural networks

本文目标是寻求最小的扰动来达到生成对抗样本的目标，因此提出了DeepFool的算法来生成扰动，并且提出了一种量化分类器鲁棒性的方法。
这是第一个通过计算出最小的必要扰动，并应用到对抗样本构建的方法，使用的限制扰动规模的方法是L2范数。最终得到的对抗样本效果要优于前面的FGSM和JSMA方法，但是这三者都需要比较大的计算资源。
根据样本 $x$ ，标签 $\hat{k}(x)$ ：
可以称 $\Delta (x,\hat{k})$ 为 $\hat{k}$ 在点 $x$ 上的鲁棒性。
分类器 $\hat{k}$ 的鲁棒性定义为：

论文主要贡献：

提出了一个简单的精确的方法来计算对抗扰动以及比较不同分类器的鲁棒性
通过实验表明：
1）本文提出的方法相比之前的方法能够更可靠，更有效地计算对抗扰动。
2）用对抗样本扩充训练数据可以显著提高分类器对对抗扰动的鲁棒性。
使用不精确的方法计算对抗扰动可能会导致关于鲁棒性的不同结论，甚至可能会产生误导性结论。本文提出的方法可以更好地理解这种现象及其影响因素。

二分类模型的DeepFool算法：

二分类模型 $\hat{k}(x) =sign(f(x))$ ，分类器边界 $\mathcal{F}=\{x:f(x)=0\}$ ，且 $f(x) = w^T x+b$ 。 $x_{0};f)$ 等于 $x_0$ 到分类边界 $\mathcal{F}$ 的距离，也可以用 $r_*(x_0)$ 表示：

当 $f$ 是线性时，在点 $x_i$ 的附近，线性分类器的扰动计算公式为：

如果 $f$ 是可微的二值分类器，可以采用迭代的操作来估计其鲁棒性。迭代过程为：先通过线性扰动计算公式得到 $r_i$ ，然后更新 $x_i=x_0+r_i$ 并不断迭代。直到 $f(x_{i+1})$ 改变符号时，迭代停止。

实际上，上述算法经常会收敛到 $\mathcal{F}$ 边界上的一个点，为了到达分类边界的另一边，最后的扰动向量 $\hat{r}$ 通常会乘以一个常数 $1+\eta$ 。

多分类模型的DeepFool算法：

多分类模型的DeepFool算法可以看作是二分类模型DeepFool的聚合。假设多分类模型有 $c$ 类。可知 $\hat{k}(x) = argmax_kf_k(x)$ 。
对于线性可微多分类模型
只需要：

设 $W$ 的第 $k$ 列为 $w_k$ :

$P$ 为判定 $\hat{k}(x_0)$ 的区域, 则 $x + r$ 应落在 $P^{c}$ ，且 $Δ(x_0;f)=dist(x_0,P^{c})$ 。
记 $x_0$ 离P的边界最近的标签为 $\hat{l}(x_0)$ :
该公式的意思其实就是两个 $f(x_0)$ 之间的距离。
因此可以将 $x_0$ 误分类为 $\hat{l}(x_0)$ ，扰动为：

对于非线性可微多分类模型
依然使用迭代的方法，在每次迭代过程中， $P$ 可用如下表述：

该迭代算法是贪婪算法，没有被证实一定可以收敛到最优解，但能够得到最小扰动的良好近似。DeepFool与优化算法紧密相连，在二分类情形下，它可以看作是牛顿迭代算法，用于在欠定情形下求非线性方程组的根，这种算法被称为正规流法。这个算法，也可以被看成是梯度下降方法，在每次迭代时自动选择自适应步长。在多分类器的算法中的线性化也类似于序列凸规划，其中约束在每一步都被线性化。

拓展到 $l_p$ 范数

之前所使用的公式中都是使用的 $l_2$ norm，其实，我们也可以使用 $l_p \ norm$ ，算法也可以找到较好的结果。相应的公式需要更改为：

其中 $\frac{p}{p-1}$ ， $\bigodot$ 是点积，当 $p=\infty$ 时，公式为：

实验结果：

从实验结果中可以看出，DeepFool能够得到更小的扰动，而且DeepFool花费的时间比L-BFGS要少，因为L-BFGS优化的目标函数代价太高，而DeepFool只需要很少的迭代次数就能够收敛。
使用由DeepFool训练出来的对抗样本进行Fine-tuning后，网络的鲁棒性变的更好了，而使用FGSM进行Fine-tuning却让网络的鲁棒性变差了。
作者认为，这是因为因为FGSM生成的扰动过大，用过大的扰动进行Fine-tuning会让网络的鲁棒性变差。而且FGSM的作用更像是正则化，而不能够代替原始数据来进行训练。