Characterizing Adversarial Subspaces Using Local Intrinsic Dimensionality
Abstract
深度神经网络对于对抗样本的攻击是十分脆弱的。要理解对抗样本，我们需要对对抗样本所在空间（对抗子空间）进行特征描述。作者通过局部固有维数（Local Intrinsic Dimensionality, LID）来表征对抗子空间的维数特性。作者首先提供了有关对抗性扰动如何影响对抗性区域的LID特征的解释，然后从实验证明了LID这一特性可以帮助区分先进的攻击技术产生的对抗样本。
1. Before Reading
由于本人对该领域了解甚少，在阅读之前，对本文[1]中提到的一些概念和知识进行了一些粗浅的了解，并做了些整理。
1.1 The Manifold
流形(Manifold)是局部具有欧式空间性质的空间，包括各种纬度的曲线曲面，例如球体、弯曲的平面等。流形的局部和欧式空间是同构的。流形是线性子空间的一种非线性推广。
机器学习的数据集实际上就是高维空间中的一个流形，而不同label的数据则分布在不同的子流形中。文献[2]深入分析了对抗样本在高维空间中的特征，提出了对抗样本的成因：对抗性的扰动将样本移出了数据流形，即认为对抗样本在数据流形之外。作者基于假设，认为对抗样本的位置有三种情况：
a) 对抗样本越过决策边界，但离流形’+'仍保持一定距离；
b) 流形’+'具有一个pocket的结构，对抗样本位于pocket中，这种情况是很难检测的；
c) 对抗样本离决策边界和子流形都很近。
1.2 Related Work
如摘要中所言，检测的想法之一是描述对抗子空间的特征。基于这种想法的工作，除了本文提到的LID外，还有一些其他的方法。
1.2.1 k-mean Distance
k-mean distance （KM）是指样本x与k个最邻近的样本点的距离。通过KM来对对抗样本进行分辨是一种十分自然的想法。由于对抗样本与真实样本位于不同流形，我们有理由认为，对抗样本离真实的样本的距离会更远。
但通过KM检测仍是不完美的，就比如1.1中的图所示，对于图b，c而言当对抗样本离真实样本的子流形很近时，这种检测的效果并不好。
1.2.2 Kernel Density
核密度（Kernel Density，KD）在https://blog.csdn.net/Angel_Yuaner/article/details/47951111中已经介绍的十分详细了，这里便不再赘述。核密度通过样本x周围小体积内的样本点数来衡量x距离子流形的远近。但与KM一样，对于某些情况，其检测效果并不好。
1.2.3 Bayesian Neural Network Uncertainty
这个方法[3]涉及许多统计的内容，没有细看。
2. What did the paper do?
作者通过局部固有维数（Local Intrinsic Dimensionality, LID）来表征对抗子空间的维数特性，并提供了有关对抗性扰动如何影响对抗性区域的LID特征的解释，然后从实验证明了LID这一特性可以帮助区分先进的攻击技术产生的对抗样本。
2.1 Local Intrinsic Dimensionality
在固有维数的理论中，经典扩展模型认为，维数代表了随着与参照样本点的距离增加，样本点周围包含的数据点的数目的增长率。举一个直观的例子，在m维的欧式空间中，一个球的体积正比于半径的m次方：
V
2
/
V
1
=
(
r
2
/
r
1
)
m
⇒
m
=
l
n
(
V
2
/
V
1
)
l
n
(
r
2
/
r
1
)
V_2/V_1=(r_2/r_1)^m \Rightarrow m=\frac{ln(V_2/V_1)}{ln(r_2/r_1)}
V2/V1=(r2/r1)m⇒m=ln(r2/r1)ln(V2/V1)
基于类似的想法，我们用数据的概率分布 F 代替上例中的体积，可以定义 LID：
L
I
D
F
(
r
)
≜
lim
ϵ
→
0
l
n
(
F
(
(
1
+
ϵ
)
⋅
r
)
/
F
(
r
)
)
l
n
(
1
+
ϵ
)
=
r
⋅
F
′
(
r
)
F
(
r
)
L
I
D
F
=
lim
r
→
0
L
I
D
F
(
r
)
LID_F(r)\triangleq \lim_{\epsilon \to 0}\frac{ln(F((1+\epsilon)\cdot r)/F(r))}{ln(1+\epsilon)}=\frac{r \cdot F'(r)}{F(r)}\\ LID_F=\lim_{r \to 0}LID_F(r)
LIDF(r)≜ϵ→0limln(1+ϵ)ln(F((1+ϵ)⋅r)/F(r))=F(r)r⋅F′(r)LIDF=r→0limLIDF(r)
LID描述了概率分布 F 随距离增加的速率（
r
L
I
D
r^{LID}
rLID）。由于我们并不知道实际的概率分布，我们需要对概率分布进行估计。以下给出LID的最大似然估计：
L
I
D
^
(
x
)
=
−
(
1
k
∑
i
=
1
k
l
o
g
r
i
(
x
)
r
k
(
x
)
)
−
1
\widehat{LID}(x)=-(\frac{1}{k}\sum_{i=1}^klog\frac{r_i(x)}{r_k(x)})^{-1}
LID
(x)=−(k1i=1∑klogrk(x)ri(x))−1
其中，
r
i
(
x
)
r_i(x)
ri(x) 表示样本x与他的第i邻近的样本点的距离，
r
k
(
x
)
r_k(x)
rk(x) 表示最大的距离。
为什么我们能通过LID来检测对抗样本呢？
事实上，我们估计LID的时候是利用的k-neighbors 去近似估计LID。如果我们认为，对抗样本的邻居都在正常数据的流形上，那这样一个样本就不大可能是对抗样本了，更可能是正常样本，因此我们猜测有一些邻居在别的流形上，因此这个对抗样本所在的空间应该是span{k-neighbors所在的流形}，因此，对抗样本的维度会比正常数据的维度要高，即，对抗样本的LID要大于正常数据的LID。
2.2 Results
可见，对抗样本的LID是高于正常样本和噪声的，这说明对抗子空间具有比正常数据更高的固有维数。同时，对抗性样本与正常数据的LID在网络的更深层更容易区分开。
同时，作者还将LID与KD的稳定性进行了对比，带宽和k值对LID的影响很小，而对KD的影响则较大。
作者还对LID的普适性进行了研究，发现LID对大部分的攻击方法都有很好的效果，而KD，BU则对部分攻击方法的防御效果很差。
作者还尝试对LID进行了Opt白盒攻击，其攻击目标设定为：
m
i
n
i
m
i
z
e
∣
∣
x
−
x
a
d
v
∣
∣
2
2
+
α
⋅
(
l
(
x
a
d
v
)
+
l
(
L
I
D
(
x
a
d
v
)
)
)
)
minimize\ \ ||x-x_{adv}||_2^2+\alpha\cdot(l(x_{adv})+l(LID(x_{adv}))))
minimize ∣∣x−xadv∣∣22+α⋅(l(xadv)+l(LID(xadv))))
攻击结果如下：
作者以此证明了LID这种检测方法的鲁棒性。但是不幸的是，这种检测方法在文章[4]中被攻破了。
3. Comment
在之前的工作中，KD是用概率密度来区分对抗样本和正常样本，KM是通过平均距离来区分。这两种方法显然都太简单了一些。对抗样本本身就是离正常样本非常近的数据集，用距离和密度这两种性质来区分并不是一个很好的选择。而LID关注的是维数性质，这是一个更本质的特征，比起距离、密度而言，其效果会更好。利用LID来检测对抗样本这是一个十分创新的idea。
LID具有许多优点：
- 运算成本小，可以通过Minibatch减小运算成本，受k值影响小；
- 对于大多数攻击有效；
- 具有普适性，通过一个攻击模型得到的detector对其他的攻击模型仍有很好的效果。
读完才发现，这居然是我们王老师的文章！！！看了OpenReview上的一些评价，大多是很好的评价——“I really enjoyed reading this paper. All the statements are very clear, the structure is transparent and easy to follow. The writing is excellent. ”
要说有什么不好的地方，那大概就是最终还是被攻破了吧。这说明LID这种方法仍是有瑕疵的。但这也许不是LID的问题，而是这种detection的策略过于简单。仅仅凭借一个值来进行分类这种策略是否有些“lazy”？
Reference
[1] Ma X, Li B, Wang Y, et al. Characterizing adversarial subspaces using local intrinsic dimensionality[J]. arXiv preprint arXiv:1801.02613, 2018.
[2] Feinman R, Curtin R R, Shintre S, et al. Detecting adversarial samples from artifacts[J]. arXiv preprint arXiv:1703.00410, 2017.
[3] Grosse K, Manoharan P, Papernot N, et al. On the (statistical) detection of adversarial examples[J]. arXiv preprint arXiv:1702.06280, 2017.
[4] Athalye A, Carlini N, Wagner D. Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples[C]//International Conference on Machine Learning. PMLR, 2018: 274-283.