Certified Robustness to Adversarial Examples with Differential Privacy
文章目录
@article{lecuyer2019certified,
title={Certified Robustness to Adversarial Examples with Differential Privacy},
author={Lecuyer, Mathias and Atlidakis, Vaggelis and Geambasu, Roxana and Hsu, Daniel and Jana, Suman},
pages={656–672},
year={2019}}
概
基于DP(differential privacy), 通过构造 ( ϵ , δ ) (\epsilon,\delta) (ϵ,δ)-DP机制, 可以得到certified robustness (在满足一定的条件下).
主要内容
Differential Privacy
DP, 差分隐私, 严格来说它是形容一些满足特定条件的随机机制. 它的背景是, 一些数据库, 在处理查询的时候, 虽然可以采用匿名机制, 但是一些别有心思的人可以通过查询获得一些特定的知识来推断出某些人或物具有的特殊的性质. 什么时候这种情况容易出现? 假设所有数据的全集是
X
\mathcal{X}
X, 而
x
,
y
x, y
x,y是由
X
\mathcal{X}
X中某些数据构成的数据库,
A
A
A是一种处理查询的机制,
A
(
x
,
ξ
)
A(x, \xi)
A(x,ξ)会返回一次查询的基于
x
x
x中返回的结果, 如果机制
A
A
A能够保护隐私, 那么它应该使得查询者不容易分辨返回的结果是基于
x
x
x还是
y
y
y. 假设
S
S
S是我们通过查询获得的一些输出, 那么随机机制
A
A
A符合
(
ϵ
,
δ
)
(\epsilon,\delta)
(ϵ,δ)-DP, 当
P
(
A
(
x
)
∈
S
)
≤
e
ϵ
P
(
A
(
y
)
∈
S
)
+
δ
,
P(A(x)\in S) \le e^{\epsilon} P(A(y) \in S) + \delta,
P(A(x)∈S)≤eϵP(A(y)∈S)+δ,
对于任意的
ρ
(
x
,
y
)
≤
1
\rho(x,y)\le1
ρ(x,y)≤1， 任意的输出集合
S
S
S, 任意的
x
,
y
⊂
X
x, y \subset \mathcal{X}
x,y⊂X.
直观的解释就是, 对数据库
x
x
x改变某一条数据, 其输出的范围的变化并不明显, 去掉
δ
\delta
δ会更容易理解:
P
(
A
(
x
)
∈
S
)
P
(
A
(
y
)
∈
S
)
≤
e
ϵ
,
ϵ
>
0.
\frac{P(A(x)\in S)}{P(A(y)\in S)} \le e^{\epsilon}, \epsilon > 0.
P(A(y)∈S)P(A(x)∈S)≤eϵ,ϵ>0.
显然
P
(
A
(
x
)
∈
S
)
P
(
A
(
y
)
∈
S
)
=
1
\frac{P(A(x)\in S)}{P(A(y)\in S)}=1
P(A(y)∈S)P(A(x)∈S)=1的时候, 我们就完全无法分辨改变的那个数据归属, 也即这个数据的存在不会改变整体的一些统计性质, 这意味着这个数据的意义是一般的. 这也就保护了隐私.
需要注意的是, 一般意义上 ρ \rho ρ为hamming距离, 但是论文中的都是一般的p范数(怎么推广不是很清楚).
insensitivity
∀ α ∈ B p ( L ) , y k ( x + α ) > max i : i ≠ k y i ( x + α ) . (1) \tag{1} \forall \alpha \in B_p(L), \quad y_k(x+\alpha) > \max_{i:i\not=k} y_i(x+\alpha). ∀α∈Bp(L),yk(x+α)>i:i=kmaxyi(x+α).(1)
其中 y k y_k yk是网络的第k个输出, 即在 B p ( L ) B_p(L) Bp(L)内网络不会改变它的判断.
但是, 现在的问题是, 一般的神经网络在
L
L
L不是很大的时候, 就会被干扰导致误判, 所以作者就希望转而寻求下面的insensitivity
∀
α
∈
B
p
(
L
)
,
E
(
y
k
(
x
+
α
)
)
>
max
i
:
i
≠
k
E
(
y
i
(
x
+
α
)
)
.
\forall \alpha \in B_p(L), \quad \mathbb{E}(y_k(x+\alpha)) > \max_{i:i\not=k} \mathbb{E} (y_i(x+\alpha)).
∀α∈Bp(L),E(yk(x+α))>i:i=kmaxE(yi(x+α)).
作者发现, DP机制可以完成这一目标.
Lemma1
注意条件
[
0
,
b
]
[0, b]
[0,b], 所以应当假设神经网络的输出是概率(softmax后)向量.
Proposition1
Proposition 1. (Robustness Condition) Suppose
A
A
A satisfies
(
ϵ
,
δ
)
(\epsilon, \delta)
(ϵ,δ)-DP with respect to a
p
p
p-norm metric. For any input
x
x
x, if for some
k
∈
K
k \in \mathcal{K}
k∈K,
E
(
A
k
(
x
)
)
>
e
2
ϵ
max
i
:
i
≠
k
E
(
A
i
(
x
)
)
+
(
1
+
e
ϵ
)
δ
,
(4)
\tag{4} \mathbb{E}(A_k(x)) > e^{2\epsilon} \max_{i:i\not=k} \mathbb{E}(A_i(x)) + (1+e^{\epsilon})\delta,
E(Ak(x))>e2ϵi:i=kmaxE(Ai(x))+(1+eϵ)δ,(4)
then the multiclass classification model based on label probability vector
y
(
x
)
=
(
E
(
A
1
(
x
)
)
,
…
,
E
(
A
K
(
x
)
)
)
y(x)=(\mathbb{E}(A_1(x)), \ldots, \mathbb{E}(A_{K}(x)))
y(x)=(E(A1(x)),…,E(AK(x))) is robust to attacks
α
\alpha
α of size
∥
α
∥
p
≤
1
\|\alpha\|_p \le 1
∥α∥p≤1 on input
x
x
x.
条件(4)很重要, 这说明加入了DP机制并非就能让所有的样本都鲁棒, 从某种程度上讲, 只有那些“confidence"高的才能够有certified robustness.
如何令网络为 ( ϵ , δ ) (\epsilon,\delta) (ϵ,δ)-DP
首先来看, 如何让普通的函数
f
f
f为
(
ϵ
,
δ
)
(\epsilon, \delta)
(ϵ,δ)-DP, 假设
Δ
p
,
q
=
Δ
p
,
q
g
=
max
x
,
x
′
:
x
≠
x
′
∥
g
(
x
)
−
g
(
x
′
)
∥
q
∥
x
−
x
′
∥
p
\Delta_{p, q} = \Delta_{p,q}^g=\max_{x,x':x \not =x'} \frac{\|g(x)-g(x')\|_q}{\|x-x'\|_p}
Δp,q=Δp,qg=x,x′:x=x′max∥x−x′∥p∥g(x)−g(x′)∥q
为
f
f
f的
p
,
q
p,q
p,q-sensitivity.
则
A
(
x
)
:
=
f
(
x
)
+
r
,
q
=
1
,
A(x):= f(x) + r, \quad q=1,
A(x):=f(x)+r,q=1,
是
(
ϵ
,
0
)
(\epsilon, 0)
(ϵ,0)-DP的, 其中
σ
=
2
Δ
p
,
1
L
/
ϵ
\sigma=\sqrt{2} \Delta_{p, 1} L/\epsilon
σ=2
Δp,1L/ϵ,
r
∼
L
a
p
(
0
,
σ
)
:
=
2
2
σ
exp
(
−
2
∣
r
∣
σ
)
.
r\sim \mathrm{Lap}(0, \sigma):=\frac{\sqrt{2}}{2\sigma} \exp(-\frac{\sqrt{2}|r|}{\sigma}).
r∼Lap(0,σ):=2σ2
exp(−σ2
∣r∣).
证明:
P
x
(
z
)
P
y
(
z
)
=
P
(
A
(
x
)
=
z
)
P
(
A
(
y
)
=
z
)
=
P
(
r
=
z
−
f
(
x
)
)
P
(
r
=
z
−
f
(
y
)
)
=
exp
(
−
2
∣
z
−
f
(
x
)
∣
σ
)
exp
(
−
2
∣
z
−
f
(
y
)
∣
σ
)
=
exp
(
2
(
∣
z
−
f
(
y
)
∣
−
∣
z
−
f
(
x
)
∣
)
σ
)
≤
exp
(
2
(
∣
f
(
x
)
−
f
(
y
)
∣
)
σ
)
=
exp
(
ϵ
(
∣
f
(
x
)
−
f
(
y
)
∣
)
Δ
p
,
1
L
)
≤
exp
(
ϵ
)
.
\begin{array}{ll} \frac{P_x(z)}{P_y(z)} &= \frac{P(A(x)=z)}{P(A(y)=z)} \\ &= \frac{P(r=z-f(x))}{P(r=z-f(y))} \\ &= \frac{\exp(-\frac{\sqrt{2}|z-f(x)|}{\sigma})}{\exp(-\frac{\sqrt{2}|z-f(y)|}{\sigma})} \\ &= \exp(\frac{\sqrt{2}(|z-f(y)|-|z-f(x)|)}{\sigma}) \\ &\le \exp(\frac{\sqrt{2}(|f(x)-f(y)|)}{\sigma}) \\ &= \exp(\frac{\epsilon(|f(x)-f(y)|)}{\Delta_{p,1} L}) \\ &\le \exp(\epsilon). \end{array}
Py(z)Px(z)=P(A(y)=z)P(A(x)=z)=P(r=z−f(y))P(r=z−f(x))=exp(−σ2
∣z−f(y)∣)exp(−σ2
∣z−f(x)∣)=exp(σ2
(∣z−f(y)∣−∣z−f(x)∣))≤exp(σ2
(∣f(x)−f(y)∣))=exp(Δp,1Lϵ(∣f(x)−f(y)∣))≤exp(ϵ).
注意, ∣ f ( x ) − f ( y ) ∣ L ≤ Δ p , 1 \frac{|f(x)-f(y)|}{L}\le \Delta_{p, 1} L∣f(x)−f(y)∣≤Δp,1.
还有一种是高斯机制, 即加高斯噪声, 对应
L
2
L_2
L2攻击.
r
∼
N
(
0
,
σ
2
)
,
σ
=
2
ln
(
1.25
δ
)
Δ
p
,
2
L
/
ϵ
,
r \sim \mathcal{N}(0, \sigma^2), \sigma= \sqrt{2\ln(\frac{1.25}{\delta})} \Delta_{p,2} L/\epsilon,
r∼N(0,σ2),σ=2ln(δ1.25)
Δp,2L/ϵ,
此时
A
(
x
)
A(x)
A(x)为
(
ϵ
,
δ
)
(\epsilon, \delta)
(ϵ,δ)-DP.
然后由上图可知, 通过在加入噪声,
g
(
x
)
→
g
(
x
)
+
r
,
g(x) \rightarrow g(x) + r,
g(x)→g(x)+r,
Q
(
x
)
=
h
∘
g
(
x
)
→
A
(
x
)
=
h
∘
(
g
(
x
)
+
r
)
.
Q(x)=h \circ g(x) \rightarrow A(x)= h \circ (g(x) + r).
Q(x)=h∘g(x)→A(x)=h∘(g(x)+r).
那么
g
+
r
g+r
g+r是DP,
A
A
A是DP吗, 答案是的.
P
(
h
∘
(
g
(
x
)
+
r
)
∈
S
)
=
P
(
g
(
x
)
+
r
∈
h
−
1
(
S
)
)
≤
e
ϵ
P
(
g
(
y
)
+
r
∈
h
−
1
(
S
)
)
+
δ
=
e
ϵ
P
(
h
∘
(
g
(
y
)
+
r
)
∈
S
)
+
δ
.
\begin{array}{ll} P(h\circ (g(x)+r) \in S) &= P( g(x)+r \in h^{-1}(S)) \\ &\le e^{\epsilon} P(g(y)+r \in h^{-1}(S)) + \delta \\ &= e^{\epsilon} P(h \circ (g(y) +r) \in S) + \delta. \end{array}
P(h∘(g(x)+r)∈S)=P(g(x)+r∈h−1(S))≤eϵP(g(y)+r∈h−1(S))+δ=eϵP(h∘(g(y)+r)∈S)+δ.
in practice
上面, 我都是基于
E
\mathbb{E}
E才会有certified robustness的, 但是神经网络的期望是没法直接算的, 只好用蒙特卡洛采样估计, 即
E
^
(
A
(
x
)
)
=
1
N
∑
n
=
1
N
h
∘
(
g
(
x
)
+
r
n
)
.
\hat{\mathbb{E}} (A(x)) = \frac{1}{N}\sum_{n=1}^N h \circ (g(x)+r_n).
E^(A(x))=N1n=1∑Nh∘(g(x)+rn).
当然, 这个时候就没法百分百保证robust了, 有
其中 E ^ l b , E ^ u b \hat{\mathbb{E}}^{lb}, \hat{\mathbb{E}}^{ub} E^lb,E^ub分别是置信下界和上界, 具体怎么来的回看论文吧, 我没推出来.
也就是符合上面近似条件的样本, 有至少 η \eta η的概率是robust的.
注: 还有噪声加在哪一层, 文中给出了答复.
certified robustness 的估计大概需要300采样, 普通的预测25次就足够了.