--- # System prepended metadata title: 第四週 Certified Robustness tags: [機器學習安全特論] --- # Certified Robustness / CR 介紹 如其名，有認證的 Robustness。 之前介紹的防禦都是所謂的 Empirical Defense，沒有任何的理論保證，都是說在某種情境下，然後嘗試供給自己訓練的模型，看看防禦的數值結果。 但是這個數值不是固定的，他會隨著情境的不同，或是更強的攻擊出現而變更差。 所以這個主題就是希望可以在「某些假設之下」，模型遭受各式強烈攻擊可以有的安全下限。 >在這個領域 Certification 有時又叫做 Verification ## 領域的分支 分為 Probabilistic 跟 Deterministic。 - 從先前的內容可以知道將模型搭配上「機率」，可以有不錯的保護效果 - 但是目前這個領域目前還只有 Incomplete 的方法，無法確定一個 model 到底有沒有 ADX - 方法叫做「**RS**」 - 有 Probabilistic，就有 Deterministic 的方法 - 這個目前有 Incomplete 跟 Complete 兩種方法 - Complete 的話雖然可以確定一個 model 有沒有 ADX，但代價是需要很難的工具： 「**MIP 或 SAT**」 - 因為代價太高了，目前並不 scalable - MIP 就是 MILP - Incomplete 只能確保部份的 example 是不是 ADX - 方法目前分為兩支：Linear Relaxation 跟 Lipschitz - Linear Relaxation 顧名思義就是從 MIP relaxation 後得到的解法 - 根據 relaxation 的程度有不同的 bound - 方法有「**LP**」 - 另一個從 LR 分下來的分支叫做 Linear Bound，方法有「**IBP 跟 CROWN**」 - Lipschitz 方法就是去看 Lipschitz constant - Lipschitz constant 較小代表 model 概念上來說變動程度不會很大，robust 程度就比較高 - 目前這個領域有兩派，一個是去算一個 model 的 Lipschitz constant 是多少，或是 bound 在哪 - 另一個是嘗試建構出一個 model，具有特殊的結構可以使他的 Lipschitz constant 在某個 bound 內 - Lipschitz constant 的壞處是 expressive 的能力比較差 :::warning 這週的內容會提到 RS、 Deterministic 的 Complete，以及 Incomplete 中的 LR。 老師說助教下週會介紹 RS 的最新研究，以及有時間的話會提到一些 Lipschitz 的方法 ::: ## CR 想知道什麼 給一個 model $f$，3集一個 example $(x,y)$，和一個範圍 $\epsilon$。 >範圍 $\epsilon$ 就是第一週提到，可以做變動的範圍大小 有兩種 Certification： - Exact Certification： - 如果這個在該範圍下沒有任何 perturbation 可以讓模型犯錯，那麼就要回答 YES - 如果存在的話要回答 NO - 這樣就可以知道這個 model 經過攻擊後的正確率是多少了 - 但從上面可以知道這是個 NP hard 難度 - Relaxed Certification： - 如果這個在該範圍下沒有任何 perturbation 可以讓模型犯錯，那麼就要回答 YES - 跟上面一樣 - 如果「可能」存在的話要回答 NO - 也就是保證只剩一邊 --- # Exact Certification 可以用 MILP 去解； MILP 可以去看我的智慧型汽車導論，有稍微介紹。 ## 問題 model 會使用一個比較 general 的模型表示法： $$ \begin{align} z_1&=x\\ z_{i+1}&=ReLU(W_i z_i+b),\ i=1,...,d-1\\ h_{\theta}(x)&=W_d z_d+b\\ \end{align} $$ $x$ 就是 input，當中每一層的 $x$ 是 $z$，通往下一層配對的權重矩陣是 $W$。 這樣一來我們的問題就可以被描述成一個最佳化問題： $$ \begin{align} \underset{z_1:d}{\text{minimize }}& (e_y-e_{y_{\text{targ}}})^{T}(W_dz_d+b)\\ \text{subject to }&z_{i+1}=ReLU(W_i z_i+b)\\ &||z_1-x||_{\infty}\le \epsilon\\ \end{align} $$ - 上面是一個「target attack」，使用 $l_{\infty}$ 作為範圍。 - $(e_y-e_{y_{\text{targ}}})^{T}(W_dz_d+b)$ ，其實拆成 $e_y ^{T}(W_dz_d+b)-e_{y_{\text{targ}}}^{T}(W_dz_d+b)$ 會比較好理解 - $e_{i}$ 是單位向量，只有 $i$ 這個方向是 1，其他都是 0 - 假設上面最佳化問題真的找到了最佳解 - 如果是大於 0，那就代表不管如何攻擊，一定都會把 $x$ 分類成 $y$，因為在 $y$ 這個 class 的分量比較大 - 如果是小於 0，那就代表一定可以透過攻擊，使 model 把 $x$ 分到 $y_{targ}$ 這個類別，因為 $y_{targ}$ 的分量比較大 ## 轉成 MILP $$ \begin{align} \text{subject to }&z_{i+1}=ReLU(W_i z_i+b)\\ &||z_1-x||_{\infty}\le \epsilon\\ \end{align} $$ 把這兩個限制轉成 MILP 的形式： - $||z_1-x||_{\infty}\le \epsilon$ - 這個比較好處理，根據 $l_{\infty}$ 的定義，就是 $\text{max}(|z_{1,i}-x_{i}|)\le \epsilon$，再拆掉絕對值。 - 不知道為什麼老師講義是寫 $z_1-x\le \epsilon$ 跟 $z_1-x\ge -\epsilon$，理論上這兩個應該是向量才對 - $z_{i+1}=ReLU(W_i z_i+b)$ - 簡潔版：$z=ReLU(x)$，並且我們要知道 $x$ 的上下界 $x\in [l,u]$ - 而 $z=ReLU(x)$ 跟下面的限制是等價的： - $a=\mathbf{1}[[x\ge0]]$，沒錯，是 boolean function - $z\le x-l(1-a)$ - $z\le u\cdot a$ - $z \ge x$ - $z \ge 0$ - 只要把 $x \le 0$ 跟 $x < 0$ 的時候帶進去，就會發現跟 ReLU 是一樣的 - 然後那個 boolean function 就是導致難算的原因，或者說他就是 MILP 中 Integer 的部分，因為他限制了 $a$ 只能是 $\mathbf{1}$ 或 $\mathbf{0}$ - 要怎麼知道 ReLU 中 $x$ 的上下界？ - 有很多種方法可以得到，只不過寬鬆的程度不一樣，下面是講義的例子： - 對於某一層 $z$，如果已知 $l\le z \le u$： - 把該層的 $W$ 拆出 $W_+$ 跟 $W_-$，一個只有大於等於 0 的權重，一個則只有小於等於 0 - 於是就可以神奇的得到：$W_+ l - W_- u + b\le Wz+b \le W_+ u - W_- l + b$ - 因為 $W=W_+ + W_-$，所以 $l\le z \le u$ 就可以知道 $(W_+ + W_-)l + b\le Wz+b \le (W_+ + W_-)u + b$ - 好吧我不知道 ## ReLU 的問題 因為那個 boolean function 會導致 Integer Programming，所以目前： - 如果可以確保 $l$ 跟 $u$ 同號，那麼就可以移除 boolean function，就可以從 IP 退化為 LP - 所以有人把 LOSS 中加入 $-tanh(1+l\cdot u)$ 這個項，讓模型比較容易出現 $l$ 跟 $u$ 同號的情形 - 另一個是讓 $W$ 變得更稀疏，這樣 MILP 的 Solver 就可以解更快 :::warning 但是目前來說依舊是非常慢，也不 Scalable，只能跑在小型 model，但是小型 model 往往不是那些有著最佳 robust accuracy 的 model ::: # Convex Relaxation 既然 MILP 那麼難，那麼我們就放鬆一下：)。 ## Convex set 一個範圍是 Convex set ，代表在這個範圍中任取兩點，兩點的中間點也會在這個範圍內。 >[參見WIKI](https://zh.wikipedia.org/zh-tw/%E5%87%B8%E9%9B%86) 一旦範圍是 Convex set，就有一些好性質可以用；但是 $z=ReLU(x)$ 限制的 $z$ 的範圍，不是 Convex set，而是一個「有折角的直線」。 所以我們就把範圍放鬆，把那個「有折角的直線」，多補一條線接在兩端，構成一個三角形，這個範圍內都可以選。 >請參考講義的圖 如果範圍變成那個多邊形，這樣一來限制的範圍就會從原本 ReLU 的範圍，變成： - $z_{i+1}\ge 0$ - 這個是水平等於 0 那條 - $z_{i+1}\ge W_{i}z_i+b$ - 這個是原本的斜直線那條 - $z_{i+1}\le \frac{u_i}{u_i-l_i}(z_i-l_i)$ - 這個是補上去的那條，但我不是很知道他怎麼推導的 這樣一來，問題**就從 MILP 變成 LP** 了，這就是 Convex Set 得到的好性質。 ## Lower Bound of MILP 上面的做法就是放寬限制，讓解的範圍變多了，但這會讓得到的解變成 MILP 的 Lower Bound： $$ \text{Objective(LP)}\le \text{Objective(MILP)} $$ - 如果 LP 解出來大於 0，那麼很安全，MILP 的解一定也大於 0，沒有問題發生 - 如果 LP 解出來小於 0，MILP 的解就有可能大於 0 或小於 0，這就有問題了 - 我們就不知道 MILP 的解到底是哪種情形 --- # Random Smoothness / RS 這個方法的構想很簡單\[Cohen et al. ICML’19\]： - 原本一個 model 在判斷一個 $x$ 是哪一類的時候，就是單純「對那個 $x$」做計算 - RS 方法則是改成以 $x$ 為中心的常態分佈 $\mathcal{N}(x,\sigma^2I)$ 那群點做判斷 - 例如假設在這樣的分佈下，有 80% 的機率是熊貓，15% 機率是長臂猿, 5% 是貓 - 那麼模型就會回傳熊貓 這個方法有效的原因也很直覺，因為攻擊時就是只移動一點點，如果改成用上面的方式，「在一般情況下」攻擊要移動的距離就要很大才會有效 ## 保證半徑 作者有算出一個點的保證半徑，也就是在該半徑內，top class 都可以被正確的回傳： $$ R=\frac{\sigma}{2}({\phi}^{-1}(p_A)-{\phi}^{-1}(p_B)) $$ - $\sigma$ 就是採樣時高斯分佈的標準差，越大的話 $R$ 會越大 - 但是有可能會降低正確率，因為範圍越大，則機率最高的 class 可能不是正確的 class - $p_A$ 是 top class 的占比，$p_A$ 是 second class 的占比 - ${\phi}^{-1}$ 是標準高斯分佈 CDF 的反函數 [**請見WIKI**](https://zh.wikipedia.org/zh-tw/%E6%AD%A3%E6%80%81%E5%88%86%E5%B8%83#%E7%B4%AF%E7%A9%8D%E5%88%86%E5%B8%83%E5%87%BD%E6%95%B8) - $x\sim \mathcal{N}(0,1)$，則 ${\phi}^{-1}(p)=v\text{ s.t. }\mathbb{P}_x(x\le v)=p$ - 因為 ${\phi}^{-1}$ 是單調的，機率越高 ${\phi}^{-1}$ 值越大 - 所以直白上來說 ${\phi}^{-1}(p_A)-{\phi}^{-1}(p_B)$ 這個是在算兩者的占比的差距 ## 蒙地卡羅 但是對於一個 model 來說，在某個範圍內機率分佈是不知道的，所以就是蒙地卡羅派上用場的時候了。 藉由採樣足夠多的點，求得 $p_A$ 的下限跟 $p_B$ 的上限。 所以上面的公式可以修改成： $$ R=\frac{\sigma}{2}({\phi}^{-1}({p_A}^{↓})-{\phi}^{-1}({p_B}^{↑})) $$ ## Formal Definition 接著把上面的描述轉成數學的形式。 模型就是： $$ f：\mathbb{R}^d\rightarrow y $$ $y$ 是 class 的集合。 我們想將 $f$ 轉換成一個 smoothed classifier $g$： $$ g(x):=\underset{c\in y}{\text{argmax }}\mathbb{P}_{\epsilon}(f(x+\epsilon)=c) $$ >$\epsilon \sim \mathcal{N}(x,\sigma^2\mathbf{1})$ 就是上面說的，以 $x$ 為中心的常態分佈，看看哪個類別的機率最大。 然後只要滿足下面的不等式： $$ \mathbb{P}_{\epsilon}(f(x+\epsilon)=c_A)\ge{p_A}^{↓}\ge{p_B}^{↑}\ge\underset{c\ne c_A}{\max}\mathbb{P}_{\epsilon}(f(x+\epsilon)=c) $$ >右邊那項就是機率第二高的 class，上下箭頭代表上下限。 則： $$ \begin{align} g(x+\delta)=c_A\ \text{for all } ||\delta||_{2}< R\\ R=\frac{\sigma}{2}({\phi}^{-1}({p_A}^{↓})-{\phi}^{-1}({p_B}^{↑})) \end{align} $$ :::info 要注意，並沒有說 $c_A$ 就是正確的 class，而是單純是機率最高的 class ::: :::warning 雖然 $\phi^{-1}$ 的值可以是負的，但是因為有確保 ${p_A}^{↓}\ge{p_B}^{↑}$，加上單調性質，所以可以知道會得到非負的值 ::: ## Gaussian data augmentation 對於固定的 $\sigma$，想要增加半徑的話就是要有較高的 $p_A$ 上限跟較低的 $p_B$ 下限，所以作者有說模型要先訓練成在 gaussian noise 下也有很好的表現會比較好。 ## Certification Procedure 接下來介紹要怎麼用這個 $R$ 來求得 Certified Accuracy。 情境如下： - 首先會給定一個目標半徑 $T$，就是攻擊的半徑 - 採樣時的 $\sigma$ 是給定的 - 然後檢查在測試集中哪些點，用上面的方法算出的 R 滿足兩件事情： - $R\ge T$ - $R$ 半徑內機率最大的點跟 label 是符合的 這樣就可以算出哪些點是分對跟分錯了；下面是演算法： - 先做較小數量的抽量 $n_0$，從這次抽的資料當中，紀錄數量最多的 class 作為 $\hat{c_A}$ - 接著再抽一次較大數量 $n$，然後紀錄 $\hat{c_A}$ 的數量 $n_{C_A}$ - 根據 $n_{C_A}$，抽取數量 $n$，以及一個信賴常數 $\alpha$，計算出 ${p_A}^{↓}$ - 我們至少有 $1-\alpha$ 的信心可以確保 ${p_A}^{↓}$ 是正確的下限 - 如果 ${p_A}^{↓}>\frac{1}{2}$，回傳預測的 $\hat{c_A}$ 作為預測的 class，以及由 ${p_A}^{↓}$ 算出的 $R$ - $R$ 可以由一條公式算出： - $R=\frac{\sigma}{2}({\phi}^{-1}({p_A}^{↓})-{\phi}^{-1}({p_B}^{↑}))\ge R=\frac{\sigma}{2}({\phi}^{-1}({p_A}^{↓})-{\phi}^{-1}(1-{p_A}^{↓}))$ - $=\frac{\sigma}{2}({\phi}^{-1}({p_A}^{↓})+{\phi}^{-1}({p_A}^{↓}))$ (對稱性質) - $=\sigma{\phi}^{-1}({p_A}^{↓})$ - 不然就回傳 $ABSTAIN$，說窩不知道 也就是說，只要結果回傳的不是窩不知道，那麼我們就至少有 $1-\alpha$ 的信心可以確保模型在半徑 R 內，$g(x+\delta)=\hat{c_A}$。 :::warning 但是要注意： - $\hat{c_A}$ 不一定是正確的 class，因為隨著 $\sigma$ 變大，雖然半徑變大了，但是占比最多的 class 很有可能就不會是真正的 label；從講義後面的圖表也可以看到正確率會隨 $\sigma$ 變大而下降。 而會算在 incorrect 的除了上述的分錯之外，回答窩不知道也算在錯，情況有可能是： - $n_0$ 太小，取樣不足 - 第一大跟第二大占比太接近 這兩個原因導致算出的 ${p_A}^{↓}\le\frac{1}{2}$，而得到窩不知道的回答。 ::: ## Increasing Certified Radius 想要提升 $R$ 以增加 Robust 程度，如果在固定 $\sigma$ 的情況下，會跟第二次的 $n$ 以及信心值 $\alpha$ 有關。 作者有推導出 ${p_A}^{↓}$ 有個很緊的 lower bound 是 $\alpha^{\frac{1}{n}}$，也就是說 $\alpha$ 越小，想要提升 ${p_A}^{↓}$(或者說提升$R=\sigma{\phi}^{-1}({p_A}^{↓})$)，就需要越大的 $n$，而且 $R$ 的成長幅度很緩慢。 ## Inference 上述是拿來用於驗證的，現在要介紹的是平常用於預測時的算法，或者說 $g$ 本身是如何計算的。 - 一樣進行大數量的取樣，然後紀錄第一第二多的兩種類別 $\hat{c_A}$ 跟 $\hat{c_B}$，以及對應的數量 $n_A$ 跟 $n_B$ - 去做 BinomialPValue 的虛無檢驗 - 要檢驗的是 $\text{BinomialPValue}(n_A, n_A+n_B, 0.5)$ - $\text{BinomialPValue}(i, n, q)$ 的意思是，計算成功機率為 $q$ 的二項式分佈 - 然後給定一個拒絕假設的機率 $\alpha$，選定分佈的某範圍機率加總為 $\alpha$，有分為單尾跟雙尾 - 最後看 $i$ 有沒有在拒絕範圍內，意思就是說 $i$ 有沒有落在那個機率很小的範圍內 - 有的話就代表成功的機率不是 $q$，此時要拒絕虛無假設 - 所以上面想要知道的是 $n_A$ 在 $n_A+n_B$ 中是不是 0.5% - 如果 p 值比 $\alpha$ 大，代表我們接受虛無假說，相信真的是 0.5%，回傳 ABSTAIN 窩不知道 - 相信是 0.5% 代表這兩種 class 數量很接近，model 會無法分出是哪個 class - 否則就是拒絕，相信不是 0.5%，回傳 $\hat{c_A}$ 作者有接著證明拒絕之後回傳的 $\hat{c_A}$，但是犯錯 $\hat{c_A}\ne c_A$ 的機率至多就是 $\alpha$： $$ \begin{align} &\mathbb{P}(\hat{c_A}\ne c_A, \text{ no abstain })\\ = & \mathbb{P}(\hat{c_A}\ne c_A)\cdot\mathbb{P}(\text{ no abstain }| \hat{c_A}\ne c_A)\\ \le & \mathbb{P}(\text{ no abstain }| \hat{c_A}\ne c_A)=\alpha\\ \end{align} $$ --- # Future Research Direction RS 目前只適用 $l_2$ 的距離，如果是其他距離函數就會需要換掉 noise，或是用其他研究方式。 - 例如 $l_1$ 就要改用 [Laplace noise](https://zh.wikipedia.org/wiki/%E6%8B%89%E6%99%AE%E6%8B%89%E6%96%AF%E5%88%86%E5%B8%83) 而不是 Gaussian noise 並且作者有說，如果想要提高 Certified Accuracy，可以根據特定的模型做實驗的修正，例如善用模型的某些特性，可以得到更精確的 Certified Accuracy。 - 因為這篇 paper 是黑盒，也就是完全對模型沒有任何假設 - 老師說其實這也是優點，不一定真的要改成用灰盒 # Is Certified Robustness All We Need \[Wang & Bovik et al. IEEE signal processing magazine’09\] 這篇有提到，其實人類的視覺跟 $l_p$ distance 有很大的差距。 例如範例的圖中，雖然那幾張圖的 $l_2$ 距離都一樣，但是就人眼來看，已經從寫實變成畢卡索了。 # Small Changes Can Be Semantically Meaningful 雖然提到了那麼久的攻擊跟防禦，都是在「微小的改動」上做研究；但其實有時候「微小的改動」卻是有意義的而不是無意或是帶有惡意的。 如果一個模型非常抗擾動，那他有可能就因此對這些「微小的改動」很遲鈍。 - 例如數字辨識，0 跟 8 、5 跟 3 等等，加上顏色配置，可能只差一點點的 pixel # “Breaking” Certified Defenses \[Ghiasi et al. ICLR 2020\] 老師說這其實只是下個很聳動的標題，因為 RS 的理論保證就在那了。 這篇 paper 是透過調整明暗度，來達到人眼看不出來，但是 $l_2$ 的距離卻很大，使得準確率很低。 - 但是調整明暗度這個做法並不是基於 $l_2$ 距離，也就是說這篇 paper 是使用不同的 threat model 了 - 這篇 paper 是想說 RS 只專注於 $l_2$ 意義不大 :::info 老師有提到另一篇也是再說 break Certified Defenses，他是對 Numerical 計算的部分動手腳找到破綻，但是就算是 Edge case :::