Certified Robustness to Adversarial Examples with Differential Privacy

Lecuyer M, Atlidakis V, Geambasu R, et al. Certified Robustness to Adversarial Examples with Differential Privacy[C]. ieee symposium on security and privacy, 2019: 656-672.

@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), 通過構(gòu)造 $(\epsilon,\delta)$ -DP機制, 可以得到certified robustness (在滿足一定的條件下).

主要內(nèi)容

Differential Privacy

DP, 差分隱私, 嚴(yán)格來說它是形容一些滿足特定條件的隨機機制. 它的背景是, 一些數(shù)據(jù)庫, 在處理查詢的時候, 雖然可以采用匿名機制, 但是一些別有心思的人可以通過查詢獲得一些特定的知識來推斷出某些人或物具有的特殊的性質(zhì). 什么時候這種情況容易出現(xiàn)? 假設(shè)所有數(shù)據(jù)的全集是 $\mathcal{X}$ , 而 $x, y$ 是由 $\mathcal{X}$ 中某些數(shù)據(jù)構(gòu)成的數(shù)據(jù)庫, $A$ 是一種處理查詢的機制, $A(x, \xi)$ 會返回一次查詢的基于 $x$ 中返回的結(jié)果, 如果機制 $A$ 能夠保護隱私, 那么它應(yīng)該使得查詢者不容易分辨返回的結(jié)果是基于 $x$ 還是 $y$ . 假設(shè) $S$ 是我們通過查詢獲得的一些輸出, 那么隨機機制 $A$ 符合 $(\epsilon,\delta)$ -DP, 當(dāng)
$P(A(x)\in S) \le e^{\epsilon} P(A(y) \in S) + \delta,$
對于任意的 $\rho(x,y)\le1$ ，任意的輸出集合 $S$ , 任意的 $x, y \subset \mathcal{X}$ .
直觀的解釋就是, 對數(shù)據(jù)庫 $x$ 改變某一條數(shù)據(jù), 其輸出的范圍的變化并不明顯, 去掉 $\delta$ 會更容易理解:
$\frac{P(A(x)\in S)}{P(A(y)\in S)} \le e^{\epsilon}, \epsilon > 0.$
顯然 $\frac{P(A(x)\in S)}{P(A(y)\in S)}=1$ 的時候, 我們就完全無法分辨改變的那個數(shù)據(jù)歸屬, 也即這個數(shù)據(jù)的存在不會改變整體的一些統(tǒng)計性質(zhì), 這意味著這個數(shù)據(jù)的意義是一般的. 這也就保護了隱私.

需要注意的是, 一般意義上 $\rho$ 為hamming距離, 但是論文中的都是一般的p范數(shù)(怎么推廣不是很清楚).

insensitivity

$\tag{1} \forall \alpha \in B_p(L), \quad y_k(x+\alpha) > \max_{i:i\not=k} y_i(x+\alpha).$

其中 $y_k$ 是網(wǎng)絡(luò)的第k個輸出, 即在 $B_p(L)$ 內(nèi)網(wǎng)絡(luò)不會改變它的判斷.

但是, 現(xiàn)在的問題是, 一般的神經(jīng)網(wǎng)絡(luò)在 $L$ 不是很大的時候, 就會被干擾導(dǎo)致誤判, 所以作者就希望轉(zhuǎn)而尋求下面的insensitivity
$\forall \alpha \in B_p(L), \quad \mathbb{E}(y_k(x+\alpha)) > \max_{i:i\not=k} \mathbb{E} (y_i(x+\alpha)).$

作者發(fā)現(xiàn), DP機制可以完成這一目標(biāo).

Lemma1

在這里插入圖片描述

注意條件

[0, b]

, 所以應(yīng)當(dāng)假設(shè)神經(jīng)網(wǎng)絡(luò)的輸出是概率(softmax后)向量.

Proposition1

Proposition 1. (Robustness Condition) Suppose $A$ satisfies $(\epsilon, \delta)$ -DP with respect to a $p$ -norm metric. For any input $x$ , if for some $k \in \mathcal{K}$ ,
$\tag{4} \mathbb{E}(A_k(x)) > e^{2\epsilon} \max_{i:i\not=k} \mathbb{E}(A_i(x)) + (1+e^{\epsilon})\delta,$
then the multiclass classification model based on label probability vector $y(x)=(\mathbb{E}(A_1(x)), \ldots, \mathbb{E}(A_{K}(x)))$ is robust to attacks $\alpha$ of size $\|\alpha\|_p \le 1$ on input $x$ .

條件(4)很重要, 這說明加入了DP機制并非就能讓所有的樣本都魯棒, 從某種程度上講, 只有那些“confidence"高的才能夠有certified robustness.

如何令網(wǎng)絡(luò)為 $(\epsilon,\delta)$ -DP

在這里插入圖片描述

首先來看, 如何讓普通的函數(shù) $f$ 為 $(\epsilon, \delta)$ -DP, 假設(shè)
$\Delta_{p, q} = \Delta_{p,q}^g=\max_{x,x':x \not =x'} \frac{\|g(x)-g(x')\|_q}{\|x-x'\|_p}$
為 $f$ 的 $p,q$ -sensitivity.
則
$A(x):= f(x) + r, \quad q=1,$
是 $(\epsilon, 0)$ -DP的, 其中 $\sigma=\sqrt{2} \Delta_{p, 1} L/\epsilon$ ,
$r\sim \mathrm{Lap}(0, \sigma):=\frac{\sqrt{2}}{2\sigma} \exp(-\frac{\sqrt{2}|r|}{\sigma}).$
證明:
$\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}$

注意, $\frac{|f(x)-f(y)|}{L}\le \Delta_{p, 1}$ .

還有一種是高斯機制, 即加高斯噪聲, 對應(yīng) $L_2$ 攻擊.
$r \sim \mathcal{N}(0, \sigma^2), \sigma= \sqrt{2\ln(\frac{1.25}{\delta})} \Delta_{p,2} L/\epsilon,$
此時 $A(x)$ 為 $(\epsilon, \delta)$ -DP.

然后由上圖可知, 通過在加入噪聲,
$g(x) \rightarrow g(x) + r,$
$Q(x)=h \circ g(x) \rightarrow A(x)= h \circ (g(x) + r).$

那么 $g+r$ 是DP, $A$ 是DP嗎, 答案是的.
$\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}$

in practice

上面, 我都是基于 $\mathbb{E}$ 才會有certified robustness的, 但是神經(jīng)網(wǎng)絡(luò)的期望是沒法直接算的, 只好用蒙特卡洛采樣估計, 即
$\hat{\mathbb{E}} (A(x)) = \frac{1}{N}\sum_{n=1}^N h \circ (g(x)+r_n).$
當(dāng)然, 這個時候就沒法百分百保證robust了, 有