Blog

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 相差的正負值 關於迭代次數與參數正確性成正相關的證明 Proof by ChatGPT o3 雜訊容忍 加總錯誤次數 Minimize 不過由於需要minimize的為indicator, 無法解開(NP-hard), 可改進此演算法 ...

Intro 不需要把所有東西放進dRAM : 不是整支執行檔都會用到 Partial Loading Programmer不需要再考慮空間問題 降低每隻程式使用的空間 -> 更多程式同時執行 降低Swapping的成本 Virtual address space address從0到空間終點 Physical memory -> page frames MMU自動做位址轉換 VM空間遠大於physical memory 定址空間中允許hole的存在 : 支援動態分配(heap, stack) Demand paging Start 不會載入所有page 把所有page mark unloded Page fault 執行時access到還沒載入的page 這時才把對應的page載入 Page load 前面handle完之後繼續執行, 就像那個page一直存在 Page replacement swap到disk Swap算法 FIFO LRU : 使用過去經驗, Counter / Stack Second chance : FIFO + refernce bit (ref==0 才swap out) Enhanced second chance : 再加上dirty bit, 優先級為 $dirty < reference$ Optimal : 預測接下來最久用不到的, 使用LRU近似 Copy-on-write 每個process的shared memory都是同一份 做寫入時才會做複製 CoW -> fork(), no CoW -> vfork() Shared memory must zero out -> C裡面的global variable初始都是0 (BSS) Page replacement algorithm FIFO ...

Intro Load program : disk -> memory CPU能直接存取的只有Main memory, register Memory unit : addr + read request / write request Main memory可能需要很多CPU cycle : Stall Cache介於Memory與Register之間 記憶體管理的目標 性能 最大化利用記憶體 提升存取速度 保護 防止越界存取 保護資料 靈活性 動態分配 Responsiveness Context switch Address binding Compile-time binding Logical address -> known physical address Prehistoric / Embeded Load-time binding 程式載入memory -> 轉換physical address 靜態分配 Run-time binding 硬體支援(MMU) 動態分配 + Virtual memory -> 程式可以在任意address執行 Contiguous allocation Early method 通常拆成兩個partition : OS(通常在高address), 剩下的是Process 每個process分配到一個segment Relocation register : 防止越界存取 Base register : 最低address Limit register : 邏輯address上界 MMU 動態分配邏輯地址 破碎化問題 First-fit 或是 Best-fit Internal fragment : 分配到的chunk太大 External fragment : 總空間可以滿足request, 但是分散掉 First-fit analysis : 大約 $\frac{1}{3}$ 的memory沒辦法使用 -> 50% rule Paging Intro Process -> memory pages (4k/8k) Physical -> memory page frames (4k/8k) Page table 對每個process建映射表 Access某個address時, Page table上 Page number -> Frame number Page table base register : PTBR Page table length register : PTLR Page miss -> page fault, 從disk載入 Address translation Logical address Page number Page offset MMU自動做 logical address -> physical address 的轉換 問題 Internal fragmentation 位址轉換的overhead 透過TLB解決, 如TLB miss才去查page table (TLB為MMU的一部分) Page table占用的空間 Structure Types Sigle-level page table Multi-level page table Inverted page table : physical -> index Huge pages : larger page size Two-level paging : 對page table做paging ...

Intro 必須滿足以下所有條件 : Mutual Exclusion : 獨佔資源 Hold and wait : request不滿足時不會release現有資源 No preemption : 不能強制收回資源 Circular waiting : 存在round概念，每個process都在等別人 處理方式 Prevention 破壞mutual exclusion : 共享資源 破壞hold and wait : request之前先release Preemption : 強制收回 破壞circular waiting : 對Allocation設定線性順序 Avoidance Banker’s Algorithm 假定系統處在Safe state, 若分配後導致不安全，則拒絕 維護Available, Max, Allocation, Need, 其中 : $$ Need[i][j] = Max[i][j]-Allocation[i][j] $$ 流程如下 : Initial check $Request[i] \leq Need[i]$ $Request[i] \leq Available$ Tentative allocation 假設暫時分配如下(還沒分配) $Available = Available - Request[i]$ $Allocation[i] = Allocation[i] + Request[i]$ $Need[i] = Need[i] - Request[i]$ Safety check 搜尋安全順序 假設 $Work=Available, \quad Finish[i]=false$ 對所有process遍歷, 若滿足則 $Work = Work + Allocation[i]; Finish[i]=true$ 如果結束時所有 $Finish[i]=true$ 則系統安全 Allocate 檢查通過才會分配 Detection Single : 對RAG做拓樸排序, 如無法偵測到環則無deadlock Multiple : 檢查unsafe state (Banker’s Algo) Recovery Terminate process : 殺到沒有deadlock Preempt resource Ignore Modern OS ignore deadlock 使用者需要手動重啟Windows

Intro 多處理器處理同筆資料 同時寫入 -> 錯誤 Race condition problem 操作global的程式碼不應同步執行 Race contidion其中一解 : critical section Mutual exclusion : 同一時間只有一個task在CS Progress : 沒有task在CS -> 令其他task進入 Bounded waiting : 不讓其他task等太多次 Peterson’s solution 假設只有兩個task, 且支援atomic instruction, shared memory 概念可擴展到任意數量task Code: //Task 0 while(1) { flag[0]=1; //task0 want to enter CS turn=1; //in case task1 wants to enter CS while(flag[1] && turn==1); //wait for task1 //Critical Section flag[0]=0; } //Task 1 while(1) { flag[1]=1; turn=0; while(flag[0] && turn==0); //Critical Section flag[1]=0; } 註: flag與turn的設置不可對調，否則會產生同時在CS的情況 ...

Intro Multiprogramming : 為了獲得最大CPU使用率 CPU burst先，接著才是I/O burst 主要考慮CPU Scheduler 排程器在以下期間發揮作用 : Switches from running to waiting state Swithces from running to ready state Switches from wating to ready Terminate Preemptive & Non-Preemptive Preemptive : 排程器可以依據時間片/優先級搶佔CPU 主流，fast-responsive且資源共享 有race condition風險 Non-Preemptive : 排程只發生在指定情況(Terminate, Switch to waiting…) 只在Process釋放CPU時重新分配 設計上更簡單，但是poor-responsive Dispatcher Switch context Switch to user mode Jump to location in order to restart program Dispatch Latency Scheduling Criteria CPU utilization Throughput Turnaround time Waiting time Response time 排程演算法 FCFS First-come, first-served ...

使用工具 VM 分析工具 : PEBear, DLL Export Viewer 組語除錯工具 : WinREPL C++ ROP Gadget : rp++ Debugger : x64dbg, Windbg Preview Windbg操作 | : Process Status ~ : Thread Status 顯示記憶體內容 : d{b|d|q|u} + Ln (顯示N個) 以某種資料結構解讀 : dt (module)!_name + rn (recursive) 對記憶體寫入 : 數值e{b|d|q}, 字串e{a|u|za|zu} (z : 指以NULL做結尾) 暫存器 : r, r [reg] = [val] 取值 : poi 反組譯 : u, uf 斷點 : bp [addr] .if [cond]{} .else{gc} 列出載入的模組 : lm 執行 : go, Step in : t, Step over : p Mapping : !address 查看權限 : !vprot 查看Error Code : !error Value [Flags], Flags=Win32, NTSTATUS… 查看Symbol : x module!symbol 呼叫慣例 流程控制 : call / ret 參數 : 使用 CX, DX, R8, R9, stack Prologue, Epilogue : 保存/恢復上一個frame的RBP Buffer Overflow 列舉一些危險的函數 ...