Blog

Intro 尋找最大Margin的超平面 : $\text{fatness}(\mathbf{w}) = \min_{n=1,…,N} \text{distance}(\mathbf{x}_n, \mathbf{w})$ 標準型式 : Hard-Margin SVM Distance 先做投影 : $\text{distance}(\mathbf{x}, b, \mathbf{w}) = \frac{|\mathbf{w}^T (\mathbf{x} - \mathbf{x}’)|}{|\mathbf{w}|}$ 化簡完之後 : $= \frac{|\mathbf{w}^T \mathbf{x} + b|}{|\mathbf{w}|}$ 分離條件 對於所有點 $n$ 須滿足 : $y_n(\mathbf{w}^T \mathbf{x}_n + b) > 0$ (正確分類) 距離 : $\frac{y_n(\mathbf{w}^T \mathbf{x}_n + b)}{||\mathbf{w}||}$ 因為有縮放不變，可以設條件 $y_n(\mathbf{w}^T \mathbf{x}_n + b) = 1$ ，這樣margin就變成 $\frac{1}{||\mathbf{w}||}$ 最終的目標為最小化 $||\mathbf{w}||$ SVM with QP Solver SVM : $$ \begin{aligned} \text{Optimal } (b, \mathbf{w}) &= ? \ \min_{b, \mathbf{w}} & \frac{1}{2} \mathbf{w}^T \mathbf{w} \ \text{subject to } & y_n (\mathbf{w}^T \mathbf{x}_n + b) \ge 1, \quad \text{for } n = 1, 2, …, N \end{aligned} $$ ...

Intro $$ G(x) = \sum_{c=1}^{C} [b(x) = c] G_c(x) $$ Basic Decision Tree Algorithm 當還未滿足終止條件時，執行 : 學一個分割準則 $b(x)$ 當前節點分割 : $\mathcal{D}$ to $C$ parts $\mathcal{D}_c = {(x_n, y_n): b(x_n) = c}$ 分割出來的子集再做遞迴呼叫 : $G_c \leftarrow DecisionTree(\mathcal{D}_c)$ 返回當前節點的預測函數 : $G(x) = \sum_{c=1}^{C} [b(x) = c] G_c(x)$ C&RT (Classification and Regression Tree) Algorithm Branching 選擇最佳分割準則 總是創造二元樹 基於leaf的最佳常數 : $g_t(x) = E_{y|\text{optimal constant}}$ Purifying 用一個簡單的閾值做二元分類 純化節點 : $b(x) = \underset{\text{decision stumps } h(x)}{\operatorname{argmin}} [D_c \text{ with } h] \cdot \text{impurity}(D_c \text{ with } h)$ Some Metrics Regression Error : $\text{impurity}(\mathcal{D}) = \frac{1}{N} \sum_{n=1}^{N} (y_n - \bar{y})^2$ Classification Error : $1 - \max_{1 \le k \le K} \frac{\sum_{n=1}^{N} \mathbb{I}(y_n = k)}{N}$ Gini Index : $1 - \sum_{k=1}^{K} \left( \frac{\sum_{n=1}^{N} \mathbb{I}(y_n = k)}{N} \right)^2$ Algorithm 邊界條件 : 不能再做分支 學一個分割準則 : $b(x) = \underset{\text{decision stumps } h(x)}{\operatorname{argmin}} [D_c \text{ with } h] \cdot \text{impurity}(D_c \text{ with } h)$ 考慮最佳的樹樁 : $\mathcal{D}_c = {(\mathbf{x}_n, y_n) : b(\mathbf{x}_n) = c}$ ，切出兩個子集 遞迴 返回組合之後的模型 : $G(\mathbf{x}) = \sum_{c=1}^{2} \mathbb{I}(b(\mathbf{x}) = c) G_c(\mathbf{x})$ Regularize Pruning 做決策樹時，同時把複雜度加入懲罰項 先長出完全樹，再去每一步選擇能最小化 (Error + 複雜度) 的node Branching on Categorial Features 可以根據出現率 / label相關性排序，再做類似數值特徵的閾值分類 Surrogate Branch 關鍵的特徵剛好缺值 在訓練時對每個 $b(x)$ 就先算一次次要分裂，想辦法用其他特徵構造出效果差不多的樹樁 遺失資料時可以用替代路徑做分類 Properties 決策樹優勢 易於理解和視覺化 能處理數值和類別特徵 自動特徵選擇 複雜資料集處理 多維特徵空間分割 複雜決策邊界學習 Adaptive Boosting 結合弱分類器最後集成一個強大的分類器 Boostrap (Re-Weighting) 對原始資料做抽樣(有重複，不平均) 每個Learner想辦法最小化誤差 如果每次只是隨機Boostrap，Base Learner會太相似，重採樣強迫學習不同的解 ...

Generative Adversarial Network Intro 把一些雜訊隨機映射到圖片裡面 Generator : 學生，生成圖像 Discriminator : 老師，判別圖像是不是假的 Generator 神經網路 Input : 高維度向量(雜訊) Output : 圖像 輸入向量的每個維度代表某些特徵 Discriminator判別器 也是個神經網路 Input : 圖像 Output : 標量值 用來判斷Generator的輸出是真的還是假的(打分數) 對抗式訓練流程 初始化Generator, Discriminator 進入循環，每個epoch重複 : 固定G、更新D，學習給真實物件高分 : $\theta_d \leftarrow \theta_d + \eta \nabla_{\theta_d} \tilde{V}(\theta_d)$ 固定D、更新G，學習產生可以騙過D的圖片 : 最小化 $-V_G = \frac{1}{m} \sum_{i=1}^{m} \log (1 - D(G(z^i)))$ ， $\theta_g \leftarrow \theta_g - \eta \nabla_{\theta_g} \tilde{V}(\theta_g)$ Loss Function MinMax函數 : $\min_G \max_D V(D, G) = E_{x \sim p_{\text{data}}(x)}[\log D(x)] + E_{z \sim p_z(z)}[\log(1 - D(G(z)))]$ D學會最大會欺騙能力 G學會最大會欺騙能力 GAN Structured Learning Structured Learning 輸出 : 序列、矩陣、圖形、樹 Translation / Speech Recognition / Text to Image … Challenge One-Shot / Zero-Shot Learning 輸出空間太大 (很多類別沒有訓練資料) 規劃能力? 組件依賴性? GAN Generator : 只用來生成(組件級生成) Discriminator : 用來整題評估，找出最優解(planning) Generator / Discriminator learn by itself Generator 深度網路也可以拿來生成 (Recall : Auto-encoder) 只能模仿外觀，難以學習組件關聯 (無腦堆疊會導致無法訓練/過擬合) Discriminator 考慮整體畫面 生成問題 (負樣本從哪來?) Mode Collapsing 生成器只學到部分模式(容量不足) 多樣性不足(泛化能力差) Conditional Generation by GAN Text-to-Image 傳統監督 : 模糊圖像 Conditional GAN : 判別器接收圖片與條件，判別匹配程度 Image-to-Image 傳統監督(close) : 類似Auto encoder Conditional GAN : 判別labal與生成圖片是否為real pair Unsupervised Conditional Generation by GAN Direct Transformation 問題與解決 問題: 可能忽略輸入 解決方案: 網路設計避免問題 預訓練編碼器網路 Cycle consistency Cycle GAN 雙向轉換: $G_{X\rightarrow Y}$ 和 $G_{Y\rightarrow X}$ 循環一致性損失 Silver Hair範例 StarGAN: 多域處理 Projection to Common Space 架構 Domain X/Y各有Encoder和Decoder 共同潛在空間投影 重建誤差最小化 改進技術 參數共享: Couple GAN, UNIT Domain Discriminator Cycle Consistency: ComboGAN Semantic Consistency: DTN / XGAN Applications Image Disentanglement車輛面向轉換 混合風格生成 Collection style transfer Object transfiguration Season transfer Photo generation from paintings Photo enhancement Diffusion Model Intro ...

先從Auto Encoder開始 透過兩組神經網路學習資料的特徵表示法 透過decoder盡可能還原輸入 Intro 由很多部件組成，部件形成一些Block (encoder block, decoder block)，堆疊這些block形成encoder, decoder Encoder & Decoder + Attention Encoder接收序列資料，透過位置編碼輸入模型，並產生Context Vector Decoder接收右移過的decoder輸出 (自回歸)，並結合Encoder的Context Vector (注意力) Embedding Word Embedding : Bagging / Word2Vec Positional Embedding : 可以用訓練或是公式 $PE_{(pos, 2i)} = \sin(pos / 10000^{2i / d_{model}})$ $PE_{(pos, 2i+1)} = \cos(pos / 10000^{2i / d_{model}})$ 最後將兩者相加，得到輸入的向量表示法，用來餵給Transformer Attention Scaled Dot-Product Attention QKV矩陣 (Query, Key, Value) 最終的Attention Score是Value的加權和 Value為Key與Query的相似度，而不同的Q會產出不同的注意力 (Query Driven) $$ \text{Attention}(Q, K, V) = \text{softmax}(\frac{QK^T}{\sqrt{d_k}})V $$ ...

Intro 具有記憶的神經網路 適合處理序列資料 (NLP) 在每一步RNN都會通過當前的輸入與隱藏狀態計算出現在的隱藏狀態 : $$ h_t = f_W(\mathbf{h}_{t-1}, \mathbf{x}_t) $$ 然後再把隱藏狀態轉換成輸出 : $$ y_t = W_{hy}\mathbf{h}_t $$ Jordan Network Elman Network的recurrent經過延遲後作為現在這個layer的輸入，但Jordan是把輸出層當作記憶 Bidirectional Network 當序列資料整筆都是可預測的 (例如NLP任務)，利用雙向RNN可以更好的理解上下文 RNN的缺點 遺忘資訊 : 因為每個時間步模型都會更新隱藏狀態 (矩陣乘法)，如果權重小於1，就會導致前一個隱藏狀態的影響快速縮小 訓練不穩定 使用時間反向傳播 (BPTT)，在每個時間點上展開成一個前向傳播的NN 反向傳播一直乘權重 + 激活，導致梯度消失 反之則會導致梯度指數增長，需要引入正則化 RNN的優點 高靈活性 : 可以處裡多種序列對序列的架構 (一對一、一對多、…) 用途 : 圖像描述(一對多) / 語意分類(多對一) / 翻譯(多對多) / 影片分類(多對多) / 文本生成(一對多/多對多) LSTM 用來解決長距離依賴 顯式記憶 (記憶細胞) 加上Gate來控制記憶單元的進出流量 (正則化) Memory Cell 圖中沒有標明的矩陣操作都是加法 輸入 : 當前的輸入 前一個隱藏狀態 前一個記憶 輸出 : ...

Intro 原論文 : Learning to Detect Memory-Related Vulnerabilities Motivation Memory-related Vulnerability可以大致理解為CTF中的Pwn相關Bug Pattern (Overflow, Use After Free, Out Of Bound, …)，也有一些其他的例如Memory Leak， 不過大多數的類型都涵蓋在Pwn的類別。而在對CVE的分析中發現，在其中被回報的漏洞有四成左右都是記憶體相關弱點，因此成為許多研究的目標，主要可以劃分為以下幾個面向 : Core Problem : 記憶體弱點的重要性以及危害性。記憶體弱點大多數時候都可以造成RCE (假如是在Stack上甚至可以很簡單的控Return Address)或是DoS (讓服務崩潰) Context : 記憶體弱點出現的地方大多數都是C/C++這種低階語言，因為支援手動、未被抽象化封裝的記憶體管理(malloc, free)，相比高階語言更加脆弱(error-prone) Goal : 在開發階段就及早偵測漏洞，去避免後續維護的成本。以藍芽為例，藍芽標準可能會有未定義行為(需要SDK去進行定義)，再往下又會有硬體製造商SDK的軟體錯誤以及開發者所撰寫程式碼的錯誤。 在整條供應鏈中只要任何一個環節出現弱點，都會對下游的軟體造成重大危害，就算下游針對不安全的SDK進行防禦(Sandbox, Seccomp, …)仍然有可能被攻破(Tesla in Pwn2Own 2023，參考 影片)。 因此及早偵測漏洞成為有價值的研究點 Existing Approaches 目前主流的漏洞分析主要為以下幾個方式 : 傳統的Static Analysis : 通常就是漏洞研究員在做的事，不過人工分析往往離不開以下幾個問題 : 極度仰賴既定的Pattern去做分析，可能沒辦法覆蓋所有可能的弱點 需要大量知識，若經驗不足可能無法正確識別漏洞，且需要花費成本去研究新的弱點(發現新的利用手法) 當Codebase變得相當大，分析工作的難度會急遽上升 基於深度學習的自動化分析 : 主要用來克服人工定義、辨識Bug pattern的困難，但往往無法發揮很好的效果 : 對於整體上下文的理解不足 : 深度學習在一個單位內通常只能處理少部分的程式碼片段(基本上大多數時候涵蓋範圍不會超過一個函數)，但記憶體漏洞通常會需要對多個函數的行為做分析 (例如經典的Heap選單題)，很多Bug難以透過分析一個小片段就去斷言是否存在，例如RNN或是NLP，他們就不是為了拿來處理這類問題的。 難以捕捉多粒度特徵 : 如同上一點說的，但有人想到可以用AST這種控制流的圖丟給GNN學習。這樣的作法又引起另外一個問題 : 當你把整支程式的AST丟給一個GNN， 又會遇到GNN自己本身在大規模的圖難以克服的問題，例如Oversmoothing，或是難以學習長期相依性 錯雜流程圖的相關問題 : 不同類型的抽象化(CPG, SDG)的Edge定義不同，但基於GNN的方法又只是用一些很簡單的分類法，導致難以準確的捕捉語意 MVD+ 結合小規模的學習(Code Slice)以及大規模(AST, CFG, …)的分析框架，解決了上述的三個問題 : ...

Intro 與神經網路類似, 但使用卷積取代權重向量 原本每層是 Perceptron -> Activation 現在變成 Convolution -> Activation -> Pooling 相對於NNet的參數量更少 Convolution 每個kernel(filter) 去跟 feature map 的對應區域做矩陣乘法 乘完之後移動，步數由stride決定 e.g. input=6x6, kernel=3x3, stride=1 -> 4x4 feature 可以使用超過一個kernel，就會增加feature的第三個維度 (2 kernel -> 2x4x4 feature) 例如 : RGB 3 channel 經由卷積層之後，下一個node相連的參數與kernel size相同，因此可以減少參數量 Pooling 這邊以Max Pooling為例 根據一個window去取區域內的最大值 可以做到降低特徵圖大小 -> subsampling 因保留最大值，最重要的特徵還是在，而且可以保持平移不變 減少參數量 Back Propagation (DL) 遵循以下公式: $$ \omega_i \leftarrow \omega_i - \eta \frac{\partial E}{\partial \omega_i} + \alpha \omega_i - \lambda \eta \omega_i $$ ...

前言 眾所周知，glibc在2.24引入vtable檢查，使針對vtable的攻擊手段如FSOP, House of Orange等攻擊手法失效，不過很快有一條新的利用鏈被發現，就是FILE成員中的 _wide_data段，在glibc執行_wide_data上vtable的函式時，並不會進行vtable進行檢查，因此衍生出如House of Apple等可以在高版本(>=2.35)通殺的利用手段． 本文主要探討在glibc 2.31環境下利用_wide_data進行vtable劫持，以達成control flow FILE結構分析 所有的原始碼皆取自 glibc source browser : Glibc 2.31 Source code 當在C語言進行如 FILE *fp=fopen(...) 或是使用stdin/stdout/stderr時，glibc都是使用以下結構： struct _IO_FILE_plus { FILE file; const struct _IO_jump_t *vtable; }; 其中FILE在內部的實作如下： struct _IO_FILE_complete { struct _IO_FILE _file; #endif __off64_t _offset; /* Wide character stream stuff. */ struct _IO_codecvt *_codecvt; struct _IO_wide_data *_wide_data; struct _IO_FILE *_freeres_list; void *_freeres_buf; size_t __pad5; int _mode; /* Make sure we don't get into trouble again. */ char _unused2[15 * sizeof (int) - 4 * sizeof (void *) - sizeof (size_t)]; // 你可以把它當作padding }; 其中可以看到除了描述FILE結構相關的_file之外，還有許多用來描述Wide character的相關member, 其中可以看到*_wide_data，追進去看一下相關定義： ...

Intro 把許多神經元合成一個layer 藉由多個layer去把input映射到output 對整個模型的權重 $W_{ij}$ 去做學習 為深度學習之基礎 Activation function 用來決定一個節點是否要激活 同時用於normalize節點輸出 共分為以下三類 Binary step Linear step : 無法用於預測不同input對應的weight Non-Linear step : 允許堆疊layer, backpropagation 常見的非線性激活函數 : Sigmoid, tanh, ReLU, Leaky ReLU Sigmoid 輸出介於0與1 用於概率輸出 由於輸出中心非0, 會造成梯度下降時方向偏移, 而影響收斂速度 Tanh 輸出介於-1與1 (以0作為中心) 相較Sigmoid有更大動態範圍 輸入過大時, 也容易發生梯度消失 ReLU 實作上非常簡單: $$ f(x) = max(0, x) $$ 可緩解梯度消失 在負區為零可提升特徵表示之泛化能力 不過若輸入包含大量負數, 會導致死亡ReLU Leaky ReLU 與ReLU非常雷同, 不過在負區時加入一個斜率 額外的參數可能影響performance Architecture of Deep Learning 在每層layer要對下一層進行輸出時, 會在權重上再額外加上一個常數維度, 舉例： 在 3-5-1 的NNet中, 共有如下數目的weight: ...

Perceptron Intro 深度學習基礎單元（神經元） Linear classifier Perceptron Learning Algorithm 基本定義 資料 : $ (x, y) \Rightarrow (x_1, x_2) $ 方程式 : $ w_0c + w_1x_1 + w_2x_2 = (w_0, w_1, w_2) \cdot (c, x_1, x_2) = 0 $ 資料點位於直線右側時, 等式結果為正, 反之則為負 基本算法 : 修正錯誤 遇到錯誤的點時將往x方向的法向量加入w, 迫使資料點被放置於直線的另一側 實作方式 指定迭代次數, 若參數可正確分類則return 處理高維度資料 訂立一個 threshold, 取內積結果與 threshold 相差的正負值 關於迭代次數與參數正確性成正相關的證明 當 $\mathbf w^{(t)}$ 對樣本 $(x_k,y_k)$ 分類錯誤時，PLA會做以下更新 : $$ \mathbf w^{(t+1)} = \mathbf w^{(t)} + y_k x_k $$ ...