[paper]Towards Evaluating the Robustness of Neural Networks(C&W)
本文提出了针对Denfensive distillation这种防御措施的C&W算法（基于三种不同距离的对抗样本生成算法），同时也具有一定的迁移性。
本文把构建对抗样本的过程转化为一个最优化问题：
其中 D D D是衡量原始图像与对抗样本之间的距离, 三种不同距离分别为 L 0 L_{0} L0范数 L 2 L_{2} L2范数和 L ∞ L_{\infty } L∞范数。
但由于 C ( x + δ ) = t C(x+δ)=t C(x+δ)=t这个问题很难直接求解，因此作者通过构造函数 f ( x , t ) f(x,t) f(x,t) 使得在 f ( x , t ) ≤ 0 f(x,t)≤0 f(x,t)≤0时，此条件满足。
则问题转换为:
为了保证输出能够产生一个合理的图像，需要 0 ≤ x i + δ i ≤ 1 0≤xi+δi≤1 0≤xi+δi≤1，这实际上被称为盒约束 (box constraints)。
本文提出了三种盒约束优化问题的解决方法：
- 投影梯度下降(Projected gradient descent):每实施一步梯度下降，就把计算结果限制在box内，这种方法对于具有复杂更新步骤的梯度下降方法（例如，具有动量的梯度下降）效果不太好，在剪切真实的 x i x_{i} xi时也修改了下一次迭代的输入。
- 裁剪梯度下降法(Clipped gradient descent):与每一步迭代裁剪xx的值不同的，该方法将裁剪直接放入了优化目标，即用 f ( m i n ( m a x ( x + δ , 0 ) , 1 ) ) f(min(max(x+δ,0),1)) f(min(max(x+δ,0),1))代替原目标函数 f ( x + δ ) ) f(x+δ)) f(x+δ))。但这种方法，只是对目标函数进行了约束，可能会存在 x i + δ i x_{i}+\delta _{i} xi+δi超过最大值的情况，这样就会出现梯度为0的结果，以至于 x i x_{i} xi即使减少，梯度上也无法检测到。
- 改变变量(Change of variables)：通过引入变量 w i w_{i} wi，使得：
且满足 x i + δ i ∈ [ 0 , 1 ] x_{i}+\delta _{i}∈[0,1] xi+δi∈[0,1]。
据此，本文提出了对应与三种范数约束的求解方法：
- L 2 L_{2} L2 attack
可以通过调整 k k k来控制错误分类发生的置信度。 参数 k k k鼓励求解器找到一个对抗样本 x ′ x′ x′，被高度置信地归类为 t t t类。还可以使用多次随机初始化来减少陷入局部最优解的概率。对于 L 2 L_{2} L2攻击中常量 c c c，本文提出：可以从很小的值开始，例如 1 0 − 4 10^{−4} 10−4；如果没找到就将 c c c翻倍，直至找到或者达到最大值，例如 1 0 10 10^{10} 1010；如果找到就使用该 c c c值。 - L 0 L_{0} L0 attack
由于 L 0 L_{0} L0范数不可微，因此不能使用标准的梯度下降法来进行求解。可以基于 L 2 L_{2} L2攻击来生成 L 0 L_{0} L0攻击。具体而言，就是先根据 L 2 L_{2} L2攻击生成扰动向量 δ δ δ，并且令 g = ∇ f ( x + δ ) g=∇f(x+δ) g=∇f(x+δ)，然后根据评估函数 g g g选择像素 i = a r g m i n i g i ⋅ δ i i=arg\underset{i}{min}g_{i}\cdot \delta _{i} i=argimingi⋅δi（ g i g_{i} gi实际上评估的是像素ii对于输出 f f f的影响），然后固定像素 i i i，再利用 L 2 L_{2} L2攻击生成对抗样本，直至无法找到对抗样本为止。
实际上 L 0 L_{0} L0攻击效果并不是很好。 - L ∞ L_{\infty } L∞ attack
对于无穷范数，假设使用公式：
m i n c ⋅ f ( x + δ ) + ∥ δ ∥ ∞ min\ \ c \cdot f(x+\delta )+\left \| \delta \right \|_{\infty} min c⋅f(x+δ)+∥δ∥∞
发现梯度下降法的效果并不理想，这是由于 ∥ δ ∥ ∞ \left \| \delta \right \|_{\infty} ∥δ∥∞只会惩罚向量中最大的那个元素，而对于其余元素没有任何影响。因此，梯度下降很快就会停滞在两个次优解之间。 考虑一个情况，其中 i = 0.5 i=0.5 i=0.5和 j = 0.5 − ϵ j=0.5−ϵ j=0.5−ϵ。 L ∞ L_{\infty } L∞只会惩罚 δ i \delta _{i} δi而不会惩罚 δ j \delta _{j} δj。并且 ∂ ∂ δ j ∥ δ ∥ ∞ \frac{\partial }{\partial \delta _{j}}\left \| \delta \right \|_{\infty} ∂δj∂∥δ∥∞在该点的值为0，因此梯度仍然会增大 δ i \delta _{i} δi，尽管它已经很大。 因此在下一次迭代中，可能会移动到 δ j \delta _{j} δj比 δ i \delta _{i} δi略大的位置，比如 i = 0.5 − ϵ ′ i=0.5−ϵ′ i=0.5−ϵ′和 j = 0.5 + ϵ ′ ′ j=0.5+ϵ′′ j=0.5+ϵ′′，这就可能陷入僵局。 换句话说，梯度下降可能在 δ i \delta _{i} δi= δ j \delta _{j} δj=0.5的线上来回摆动。
因此可将问题优化如下：
在每次迭代之后，如果对所有的 i i i都有 δ i < τ \delta _{i}< \tau δi<τ，可以将 τ \tau τ减少0.9倍并重复; 否则，终止搜索。
假设必须选择一个好的常数 c c c用于 L ∞ L_{\infty } L∞攻击。 可以采用与 L 0 L_{0} L0攻击相同的方法：首先将 c c c设置为非常低的值，然后以此 c c c值运行 L ∞ L_{\infty } L∞攻击。 如果失败，加倍 c c c并重试，直到成功。 如果 c c c超过固定阈值，我们中止搜索。
在每次迭代中使用“热启动”进行梯度下降，则该算法的速度与之前的 L 2 L_{2} L2算法（使用单个起点）一样快。
实验结果：
