## TODO: 為何 Linux 核心用到 jhash？
首先先理解 jhash 的運作流程
1. 初始化變數 : 將三個 32-bit 的變數 a, b, c 設定為某些初始常數，這會當作內部的 hash 狀態。
2. 分段處理輸入資料 : 每次讀取 12 bytes（3 個 32-bit word），依序加到 a、b、c 三個暫存器中。
3. 進行 mix 運算：將 a、b、c 做一系列的加、減、XOR、rotate 的操作，以達成 entropy 的擴散與高敏感度。++**擴散**的意思 : 資料中每個輸入 bit 所帶來的隨機資訊，會在 hash 函數中經過多輪複雜的運算後，平均分布到最終輸出的每一個位元上。這表示輸入中每個變動，都能有效地影響輸出中大部分甚至所有位元。**高敏感度**的意思 : 當輸入資料發生極小的變化，哪怕只是一個 bit ，hash 的輸出結果就會有極大且無規律的改變。++
4. 重複處理直到輸入吃完 : 如果最後剩餘不到 12 bytes，則依據剩餘長度進行最後一次特殊的填補與 mix。
5. 最後回傳的 c (通常是 c )雜湊值
那 jhash 的核心就在於 rotate
```c
a -= c; a ^= rol32(c, 4); c += b;
```
hash function 的重點是要不漏掉資訊同時能重新洗牌，那 rotation 本身只是重排 bit 位置，但如果將 rotation 的結果參與 XOR、加法、減法、再次 rot 等混合操作，簡單來說， rotation 可以讓某個高位 bit 可以變成低位，靠著後續 XOR 的操作可以完全打亂整體 bit 結構，避免 `bit correlation` 的發生。
Linux 其實使用多種 hash fucntion 在不同的場景，而 `jhash` 最常使用就是在不牽涉到外部使用者資料、不需要抗攻擊能力，但又常常需要快速查找、分類、配對的情境， `dcache` 就是其中一個場景，可用於檔案路徑的雜湊查找，那為甚麼相較於黃金比例的 `Fibonacci hash` ，linux 傾向使用 jhash 呢?
* `jhash` 只用加減、XOR、rotate且無需使用乘法或 lookup 表
* `jhash` 經過 多輪 bit mixing，對任意位元變化都能擴散，避免 clustering ，對比之下 `Fibonacci hashing` 只對尾段 bit 改變的 key 有良好分布，但高位變化小時很容易 clustering ，甚至發生 collision 。
* 許多 kernel 結構使用 字串作為 key ，但 `Fibonacci hash` 完全不支援
在 git log 中找不到相關有指出 hash 函式選用依據，但有在註解中找到
```c
/*
* This is the single most critical data structure when it comes
* to the dcache: the hashtable for lookups. Somebody should try
* to make this good - I've just made it work.
*
* This hash‑function tries to avoid losing too many bits of hash
* information, yet avoid using a prime hash‑size or similar.
*/
#define D_HASHBITS d_hash_shift
#define D_HASHMASK d_hash_mask
```
後來發現 dcache 使用的其實是 `full_name_hash()` 這個 function 。
```c
unsigned long hash = 0;
for (i = 0; i < len; i++) {
hash = (hash + (c << 4) + (c >> 4)) * 11;
}
hash = (unsigned int) hash;
```
根據註解的句子做解釋 :
* `avoid losing too many bits of hash information` : 一般來說，遮罩的話可能會丟失高位資訊，所以這個函式會先進行如 `hash += hash >> shift` 的操作，把高位資訊折疊回來，盡量保留原本雜湊值中的分布特性與 entropy 。
* `yet avoid using a prime hash-size or similar` : 一般來說，用質數作為表大小可以減少碰撞，使用 `2^n` 大小的表，可以用位元遮罩`（& (2^n - 1)）`來快速計算 bucket index，這比 `% prime` 快得多，Linux 核心考慮的是效能與 cache locality，不是數學上的理想分佈。
## TODO: 為何多種雜湊函數存在於核心？
Linux 中不同子系統對雜湊函數的需求不同，例如
* `dentry` 利用了 hash 可以達到快速查詢的目標
* `netfilter` 利用 hash 封包流分類
* `random.c` 也會利用 hash 來處理 `entropy`
~~我認為~~在更均勻且低碰撞的雜湊函數下，可以加速查找效率跟資料的分類與比對。
## TODO: ASLR
### 整理 [2025-03-25](https://hackmd.io/QISdbcjUShy1Be48NHVqaw?view#nyraa) 問答簡記 & ASLR 的侷限
閱讀完[ nyraa ](https://github.com/nyraa?tab=repositories)同學整理 ASLR 的筆記後，~~大致上是搭配一本書~~這本書標題為 `"Exploiting Linux and PaX ASLR’s Weaknesses on 32- and 64-bit Systems"` 這本書主要去深入分析 Linux 與 PaX 的 ASLR 實作弱點。
1. Low Entropy
* Page Alignment : 原理是記憶體必須依照 page 大小對齊才能配置，~~普通~~ 常見的 page 大小為 4KB ， 4KB 為 $2^{12}$ = 4096 bytes 換算成二進位為 `1000000000000` (後面 12 個 0 )，因為若不以 4096 bytes 為單位放的話，作業系統會不知道要把那個 page 放在哪裡。而 Huge page 大小為 2MB = $2^{21}$ =2097152 = `1000000000000000000000` (後面 21 個 0 )，這些被固定的 bits 就是 ASLR 無法利用的 entropy 位元，即使你有 32-bit 或 64-bit 的地址空間，但真正能用來做隨機的 bits 被減少了。
* 為了~~兼容性~~相容性與避免 Fragmentation，Linux 限制了分佈範圍PaX 允許物件隨機在整個 VMA，但 Linux 會讓 mmap、libs、heap 各用自己的一小塊區域來隨機。這會導致一個記憶體區段只有 $2^8$ = 256 種可能位置 ⇒ 實際 entropy 僅約 8 bits ，++這麼低的隨機性使得攻擊者可以透過暴力猜測嘗試所有可能位址，在極短時間內就可能命中目標區段（如 libc 或 heap）。若目標系統使用如 `Apache` 或 `Android Zygote` 等 fork 模型，攻擊者甚至可以透過反覆建立子行程並保留相同記憶體配置，以逐步測試並突破 ASLR 的保護機制。++
2. Non-uniform distribution
* ASLR 理想狀況下，希望各種載入位址是 uniform 的，==而 uniform 在統計學的定義是所有可能的數值都有「相等的機率」被選到==，也就是每個可能的記憶體位置被選到的機率都相等。但根據下列圖顯示，舉例來說 PaX 32-bit 因為是兩個隨機變數相加，會導致產生三角形分布，也就是中心極限定理（CLT），意思是若一個隨機變數 𝑋1,𝑋2,…,𝑋𝑛 是獨立同分布（i.i.d.），且期望值與變異數有限，則當 𝑛→∞，它們的「平均」或「總和」會趨近於常態分布，++根據 CLT 的數學表示式 : $$
Z=\frac{S_n - \mathbb{E}[S_n]}{\sqrt{\mathrm{Var}(S_n)}} \xrightarrow{d} \mathcal{N}(0, 1)
$$這個式子的意思是++
> ++把多個隨機變數加總後，先減掉它們的平均期望值，再除以標準差，這個結果就會越來越接近「標準常態分布」——也就是中間值機率高、兩邊機率低的鐘形曲線。這樣的結果可以進一步用來「查標準常態分布表」，計算某個值落在特定範圍內的機率。舉例來說，若經過標準化後得到的 Z 值為 1，查表可知其機率約為 0.8413，代表該值小於平均值加上一個標準差的機率為 84.13%。這種查表方式可用來預估落在某區間內的機率大小，也說明為何分布集中的 ASLR 位址可能被更容易猜中。++
3. Correlation Between Maps
* 在理想的 ASLR 中，每個記憶體區段（如 libc、heap、stack、mmap）應該都是獨立隨機配置的。但實際上，很多情況下這些區段的位址是有關聯的，攻擊者若知道某一區段的位址，就可能推測出其他區段的大致位置。
1. Total Correlation : 只要知道一個函式庫的位址，就能知道所有函式庫、heap、stack 的相對位址
2. Positive Correlation : 意思是有部分位址資訊是有關的，但不能完全確定整體位址
3. Useless Correlation : 不同區段之間毫無關係，知道一個區段完全無法推論另一個。這才是理想 ASLR 應有的目標。
4. Memory Layout Inheritance
* 在 Linux 中，當程式使用 `fork()` 系統呼叫建立子行程時，新的子行程會繼承~~父行程~~++親代節點++的整個記憶體佈局，這代表即使系統開啟了 ASLR ，這些位址在子行程中也不會重新隨機化，而是完全複製~~父行程~~++親代節點++當前的記憶體分佈。這種行為在安全上產生嚴重風險，特別是在常見的伺服器應用中，如 Apache 或 PHP-FPM，這些服務常採用 `pre-fork` 模型，先 fork 出大量子行程等待請求。攻擊者若能導致其中一個子行程崩潰，~~父行程~~++親代節點++通常會重新 fork 一個新的子行程來替補，但由於新的子行程繼承了與上一個完全相同的++記憶體++佈局，攻擊者即可反覆對相同記憶體位置進行爆破，極大提升成功率。這種「記憶體位址可重生」的行為破壞了 ASLR 應有的隨機性保障，使得原本應該難以預測的位置，變成攻擊者可以一再嘗試的固定目標。
### 討論 entropy 的來源
1948年， Claude Shannon 在其論文[《A Mathematical Theory of Communication》](https://people.math.harvard.edu/~ctm/home/text/others/shannon/entropy/entropy.pdf)中，將熵的概念引入資訊理論，提出了資訊熵的概念，用以衡量訊息的不確定性。他指出這個不確定性函數應該滿足以下三項基本條件：
1. 連續性 : 熵 $H(p_1, \ldots, p_n)$ 對於所有機率變數 $Pi$ 是連續的，意思是機率的微小變化不應造成熵的不連續跳動。
2. 極大性 : 若所有事件是「等可能」的（例如 pi = 1/n )，那麼事件總數 n 越多，熵 H 越大。越多。簡單來說意思是選擇越多，不確定性就應該越大。
3. 可加性 : 若某個事件的選擇是兩階段決定的，則總熵應等於第一階段熵，加上該階段下條件熵的加權平均。
根據以上三個條件可定義出公式為 :
$S = - \sum^{n}_{i=1} P(x_i) log_b P(x_i)=\sum^{n}_{i=1} P(x_i)I(x_i)$
在資訊理論中，熵越高，表示資訊的不確定性越大；熵越低，表示資訊越有序、可預測。
++而之中為甚麼使用 log 而不是其他數學理論呢?++
++1. 資訊量與加法性（ Additivity ）來看 :
當你有多個獨立事件（例如兩枚硬幣），你希望 $H(X,Y) = H(X) + H(Y)$ 意思是總資訊量 = 個別資訊量相加，對數函數有乘法轉加法的性質 $log(xy)=logx+logy$ 所以用對數，才能讓機率乘積對應到資訊量加總。
2. 遞增性 :
在information theory中，$-log2(1/p)$ 也稱之為資訊本體( self-information )，也就是說，越不常出現的訊息往往帶著越大的資訊含量，同理來說，如果當一個事件一定會發生(機率 p = 1)，那就不帶來任何新資訊，用對數表示就是 $log(1) = 0$。
3. 公式可以表達成當每件事機率相同， entropy 會越大，舉例假設一個三面骰子，他的 entropy 加總後會是 1.585 bits ，但如果出現不均勻的現象，則 entropy 就會小於 1.585 bits。++
[參考資料](https://www.quora.com/Why-is-there-a-logarithmic-function-in-the-entropy-formula)
## TODO: 重現 [Chaos: Function Granularity Runtime Address Layout Space Randomization for Kernel Module](https://dl.acm.org/doi/10.1145/3678015.3680476) 實驗並檢討論
**《Chaos: Function Granularity Runtime Address Layout Space Randomization for Kernel Module》** 這篇的內容主要在說
* 將 ASLR 細化到函式等級，兼顧隨機性與執行效率。
* 在執行期定時重排函式記憶體位置，有效對抗持續性攻擊。
* 從原本相對位置固定，到使用 `Fisher-Yates` 演算法重新排列所有函式段順序，導致 gadget 相對位址不斷變動進而讓 entropy 增加。
首先要重現此論文方法首要目標就是要將函式的機器碼完整複製到新的記憶體空間，參考[網路上的資料](https://blog.csdn.net/weixin_45030965/article/details/127340459)找到的方法是 `module_alloc()` ，但我在編譯時發生以下錯誤
```gcc
ERROR: modpost: "module_alloc" [/home/junan/chaos/chaos_module.ko] undefined!
```
使用~~指令~~++命令++尋找模組
```
grep module_alloc /proc/kallsyms
```
輸出空白，代表Linux 核心沒有將它對外 export 。
:::info
後來發現 Ubuntu 6.11 系列為了安全考量，封鎖了許多可執行記憶體操作的 API ，除了下載最新 Linux kernel 進行更改外，還有其他可行的方法可以做執行記憶體操作嗎?
:::
## TODO: 閱讀 [教材](https://hackmd.io/@sysprog/linux2025-lab0/%2F%40sysprog%2Flinux2025-lab0-d) 並紀錄問題
**1. What is random**?
亂數表示事件發生無法被預測，或其發生機率在所有可能結果中是平均的。從統計學角度，亂數通常與「不可預測性」和「等機率性」相關。且理想亂數的分布應該服從均勻分布$$X \sim U(a, b)$$意思是任一值被選中的機率相同。
**2. How to measure the randomness?**
亂數的測量本質上是：觀察結果的機率分布與資訊不確定性（Entropy），教材中提到三個方法
1. Information Entropy : 它的核心概念是當一件事情越難發生、越不可預測，它所帶來的資訊量就越大。因此，我們可以透過計算每個事件發生的機率來求出整體的不確定程度。如果所有結果機率都一樣（像是均勻分布），那麼整體的 entropy 會達到最大值，代表這是一組高度隨機、無法預測的序列。這種方法特別適合用來分析文字、檔案或亂數來源的資訊密度。
2. Statistical Randomness Tests : 簡單來說就是計算每個數字的出現次數，它不是看每個值帶來多少資訊，而是直接檢查這些結果在統計上看起來是否像亂數。我們把一組亂數的各種結果出現次數統計起來，看它們是否接近理想的均勻分布。如果出現某些數字特別多或少，那這組數據就可能帶有偏差。像是 Chi-square Test 跟 ent 工具。
3. PRNG 數學定義與對抗測試 : PRNG 是一種可計算但難以預測的亂數產生器，模擬一個 adversary ，給它一串亂數樣本，看是否能準確預測下一個數值，若成功率顯著高於隨機猜測，代表亂數生成器存在模式或漏洞。
:::info
1. 教材上前面說亂數是無法預測的，後面卻又以機率的方式去衡量亂數，若真的隨機不是應該要無法描述來表示嗎?
2. ideal entropy 只要增加取值範圍 N 就會提高，但實際 entropy 卻不一定跟著漲。那除了分布不均之外，還有哪些結構性原因會讓 entropy 與 $\log_2 n$ 產生「落差上限」？
3. 若不可預測性才是亂數的核心，為什麼主流測試仍以統計做度量？是否存在一種能測出不可預測的理論度量？
:::
## TODO: 機率統計: 看書
參考資料 : http://ccckmit.wikidot.com/st:video
並且搭配書籍吳忠武教授的[機率與統計](https://eshop.hwatai.com.tw/SalePage/Index/7004691?lang=zh-TW)用書邊看邊了解，但書的內容實在太多，所以打算暑假的時候再來好好讀，目前是利用書籍搭配網站先學習基礎知識。
<img src="https://hackmd.io/_uploads/r1ozrx14el.jpg" width="300">
Sign in with Wallet
Connect another wallet