2025q1 Homework1 (lab0)

contributed by <MikazukiHikari>

作業書寫規範:

無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
不要在筆記內加入 [TOC] : 筆記左上方已有 Table of Contents (TOC) 功能，不需要畫蛇添足
不要變更預設的 CSS 也不要加入任何佈景主題: 這是「開發紀錄」，用於評分和接受同儕的檢閱
當在筆記中貼入程式碼時，避免非必要的行號，也就是該手動將 c= 或 cpp= 變更為 c 或 cpp。行號只在後續討論明確需要行號時，才要出現，否則維持精簡的展現。可留意「你所不知道的 C 語言: linked list 和非連續記憶體」裡頭程式碼展現的方式
HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」
留意科技詞彙的使用，請參見「資訊科技詞彙翻譯」及「詞彙對照表」
不要濫用 :::info, :::success, :::warning 等標示，儘量用清晰的文字書寫。:::danger 則僅限授課教師作為批注使用
避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景
在中文敘述中，使用全形標點符號，例如該用「，」，而非 ","。注意書名號的使用，即 〈 和 〉，非「小於」和「大於」符號
避免使用不必要的 emoji 字元

開發環境

$ uname -a
Linux victor-P30-F5 6.8.0-52-generic #53-Ubuntu SMP PREEMPT_DYNAMIC Sat Jan 11 00:06:25 UTC 2025 x86_64 x86_64 x86_64 GNU/Linux

$ gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0
Copyright (C) 2023 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ lscpu
Architecture:             x86_64
  CPU op-mode(s):         32-bit, 64-bit
  Address sizes:          39 bits physical, 48 bits virtual
  Byte Order:             Little Endian
CPU(s):                   8
  On-line CPU(s) list:    0-7
Vendor ID:                GenuineIntel
  Model name:             Intel(R) Core(TM) i7-7700 CPU @ 3.60GHz
    CPU family:           6
    Model:                158
    Thread(s) per core:   2
    Core(s) per socket:   4
    Socket(s):            1
    Stepping:             9
    CPU(s) scaling MHz:   30%
    CPU max MHz:          4200.0000
    CPU min MHz:          800.0000
    BogoMIPS:             7200.00
Caches (sum of all):      
  L1d:                    128 KiB (4 instances)
  L1i:                    128 KiB (4 instances)
  L2:                     1 MiB (4 instances)
  L3:                     8 MiB (1 instance)
NUMA:                     
  NUMA node(s):           1
  NUMA node0 CPU(s):      0-7

實作 queue.[ch]

q_new

先使用malloc配置記憶體空間給head，並且在配置後進行檢查。
若記憶體配置成功，則用 list.h 中的 INIT_LIST_HEAD 對節點初始化，最後回傳 head 。

q_free

先檢查 head 存不存在，若結果為不存在則無需處理。
~~接著再檢查是否僅包含head節點而無其他元素，若結果為是則可直接釋放 head 。~~ 根據從 Linux 核心的藝術談起，為了寫出 good taste 的版本，若head 無其他節點則 list_for_each_entry_safe 也會正常執行完成，最終再釋放 head ，因此，此特例不存在。
若否，則使用 list.h 中的 list_for_each_safe 逐一走訪佇列中的每個節點，透過 q_release_element 釋放每個節點佔用的記憶體，最後釋放 head 。

q_insert_head & q_insert_tail

先檢查 head 和 s 存不存在，若結果為不存在則無需處理。
使用malloc配置記憶體空間給new_element，並且在配置後進行檢查。

字串複製

1.~~使用malloc配置記憶體空間給value，並且在配置後進行檢查。~~
2.~~空間為 strlen(s) + 1 ， +1 是為了確保 \0 會被拷貝。由於我們已使用strlcpy ，其會確保 \0 會被拷貝，因此不需要額外 +1 。~~
3.~~使用 strlcpy 取代 strcpy ，防止 buffer overflow。~~
4.~~將 s 指向的字串複製過去。~~
5.直接使用 strdup ，其包含了配置記憶體空間給value以及 s 指向的字串複製過去的動作。

插入頭/尾

使用 list.h 提供的 list_add 或 list_add_tail 即可完成此操作。

q_remove_head / q_remove_tail

先檢查 head 存不存在、 head 是否有其他的節點、sp 存不存在，若結果為不存在、無節點則無需處理並回傳NULL。
使用list_entry取得鏈結串列的第一個/最後一個element_t *。
使用 strlcpy 將第一個/最後一個元素的value複製到 bufsize 。
最後，使用 list_del 移除元素，並回傳第一個/最後一個element_t *。

q_size

先檢查 head 存不存在及 head 是否有其他的節點。
使用 list_for_each 走訪佇列中的每個節點，並計算走過的節點數，最後回傳結果。

q_delete_mid

先檢查 head 存不存在及 head 是否有其他的節點，若結果為不存在則無需處理並回傳false。
由於此佇列是雙向環狀鏈結，我們可以使用head->next和head->prev得出第一個和最後一個節點，並使用迴圈使兩指標相向移動，當兩指標指向的是同一節點時或兩相鄰之節點則迴圈結束。
根據 LeetCode 2095 的描述，中間節點定義為第

⌊ \frac{𝑛}{2} ⌋

個節點，n為佇列長度。因此不管兩指標指向的是同一節點時或兩相鄰之節點，由最後一節點往前之指標指向之節點必為我們要移除的節點。
最後別忘了釋放被移除的節點的記憶體，因為此函式為delete，指某個節點將被「抹除」。

q_delete_dup

先檢查 head 存不存在及 head 是否有其他的節點，若結果為不存在則無需處理並回傳false。
使用 list.h 中的 list_for_each_safe 逐一走訪佇列中的每個節點，並使用list_entry取得nex和cur ，他們是element_t * 會逐一走訪佇列中的每個節點，並且nex恆為cur的下一個節點。
比較nex和cur的value，若相同則從佇列中移除cur的節點並釋放記憶體，根據 LeetCode 82，此節點也該被移除，然而我們還需要它用於判斷下個節點是否也該刪除，因此用isduplicate記錄此nex的節點為重複。
除此之外，我們還需要考慮另一種情況：現在訪問的cur節點是否因為和上一個被移除的節點重複而也該被移除，如果是則移除此節點並釋放記憶體。
最後，為了避免list_entry 在節點為head時會出錯的情形，有使用if判斷式，且這時候仍會執行：現在訪問的cur節點是否因為和上一個被移除的節點重複而也該被移除。

q_swap

先檢查 head 存不存在、 head 是否有其他的節點或僅有一個節點。
使用 list.h 中的 list_for_each_safe 逐一走訪佇列中的每個節點，並且safe恆為node的下一個節點。
使用list_move 將node移至safe後面，再將safe指標指向node的下一個節點以確保list_for_each_safe正常執行，如此便可達成LeetCode 24的要求。
此外q_swap其實也是q_reverseK的一個特例，相當於k=2。

q_reverse

若 head 不存在、 head 無其他節點或僅有一個節點，則無需處理。
使用 list.h 中的 list_for_each_safe 逐一走訪佇列中的每個節點，並且safe恆為node的下一個節點。在走訪過程中將各節點的指標next換成prev、prev換成next。
最後再將head的next和prev調換就好了。

q_reverseK

先檢查 head 存不存在、 head 是否有其他的節點或僅有一個節點。
使用雙層迴圈，外層代表需要反轉的次數，內層代表有哪些節點為一組執行反轉，當node走到這一組開始算的第k+1個節點時，跳離內層迴圈並將前k個node從佇列取出放至暫存的佇列tmp，接著執行q_reverse將整個佇列反轉，再將結果插入new_head的尾部；之後新的一輪迴圈，以此類推，直到node 走訪完佇列中的每個節點。
最後再將new_head插入已經沒有節點的head就完成了。

q_sort

此函式使用Merge Sort的方式實作，它比起Bubble Sort、Insertion Sort、Selection Sort都還要容易理解且複雜度為O(nlogn)速度比起上面三種快非常多。
要達成 Merge Sort ，過程中會需要不斷的做兩件事：將鏈表切成兩半 和 合併兩條已排序的鏈表
先檢查 head 存不存在、 head 是否有其他的節點或僅有一個節點。再打破環狀鏈表使其變成普通的雙向鏈表，並對 head->next 之後的部分進行 Merge Sort。
將鏈表切成兩半可以利用快慢指標，fast = slow->next代表鏈表對半切的分界，如此遞迴地將鏈表切成兩半直到每個新鏈表都只剩一個或沒有元素；接下來就是不斷地合併兩條已排序的鏈表，我們建立了一個函式merge_two_list能合併兩條已排序的鏈表 l1 和l2，且能根據參數descend決定是否降序排序。最終獲得一個無head的已排序的佇列。之後，將head->next指向此已排序佇列的第一個節點。next的部分就排序完成了
由於本來的佇列是雙向環狀鏈結，所以用cur逐一走訪佇列中的每個節點，將每個節點的prev指向其對應的前一個節點就完成了。

q_ascend / q_descend

若 head 不存在、 head 無其他節點，回傳0；僅有一個節點回傳1。
使用list_entry取得鏈結串列的最後一個element_t *。
接著使用和list_for_each_safe 類似的迴圈，但是從後面往前逐一走訪佇列中的每個節點，並且safe恆為node的前一個節點。再使用list_entry取得node的element_t *，為了能使用value去比較大小。
當node的value比右側節點大/小，移除並釋放此節點；若node的value比右側節點大/小，更新 last，因為往左走時應該記住最小值/最大值，確保最終鏈表是遞增/遞減排序的
最後回傳處理好的佇列的節點數。

q_merge

若 head 不存在、 head 無其他節點，回傳0；若只有一個節點回傳第一個」佇列的節點數。
使用list_entry取得鏈結串列的第一個queue_contex_t *，接著打破第一個環狀鏈表q使其變成普通的雙向鏈表以適用merge_two_list。
用迴圈執行等同於「佇列的數量-1」的次數，其代表「合併兩個queue」這個動作要做「佇列的數量-1」次，再使用list_entry取得鏈結串列的下一個queue_contex_t *，並也打破環狀鏈表。
將當前節點的佇列和下一個節點的佇列用merge_two_list合併到 node->q，接著要清空已無節點的佇列next_node->q，這邊使用INIT_LIST_HEAD將其初始化為空鏈表，這邊不能使用free因為其不會正確釋放鏈表中的所有節點，會導致內存洩漏。最後再將指針指向下一個queue_contex_t的節點，之後新的一輪迴圈，以此類推。
最終，整個queue_contex_t會只剩一個佇列，由於本來的佇列是雙向環狀鏈結，所以用cur逐一走訪佇列中的每個節點，將每個節點的prev指向其對應的前一個節點
最後回傳用q_size得到的這個最後的佇列的節點數。

亂數+論文閱讀

在 qtest 提供新的命令 shuffle

使用 Fisher-Yates shuffle 來實作洗牌，每次從剩餘的部份中隨機抽取一個 node 後將其插入到最末端。
在測試過程中，由於 queue.h 不能做改動，因此我在本地端修改 queue.c、 queue.h 和 qtest.c 並使用 make重新編譯，如此便成功添加shuffle指令，在推送至 GitHub 時我再將 queue.h 中的定義移除。

測試

參考 lab0-d 提供的 code 建立 shuffle_test.py 測試程式來測試，對串列組合1-2-3-4進行1百萬次的 shuffle，經過大約29分鐘的執行後得到以下統計結果:

串列組合	測試的頻率	期望的頻率	串列組合	測試的頻率	期望的頻率
1 2 3 4	41447	41666	3 1 2 4	41722	41666
1 2 4 3	41639	41666	3 1 4 2	41960	41666
1 3 2 4	41799	41666	3 2 1 4	41606	41666
1 3 4 2	41654	41666	3 2 4 1	41635	41666
1 4 2 3	41265	41666	3 4 1 2	41462	41666
1 4 3 2	41740	41666	3 4 2 1	41968	41666
2 1 3 4	41512	41666	4 1 2 3	41691	41666
2 1 4 3	41818	41666	4 1 3 2	41612	41666
2 3 1 4	41267	41666	4 2 1 3	41418	41666
2 3 4 1	42023	41666	4 2 3 1	41484	41666
2 4 1 3	41629	41666	4 3 1 2	41986	41666
2 4 3 1	41819	41666	4 3 2 1	41844	41666

chi square sum:  25.20649930398886

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

根據卡方分布表，在自由度為 23 的情況下，所得的 P-value 值介於 0.1 到 0.9 之間，遠大於常見的顯著性水準 P = 0.05。因此，我們無法拒絕虛無假設（

𝐻 0

），表示目前的測試樣本不足以證明 shuffle 的結果並非均勻分布。這可能是因為測試次數不足，意味著樣本資料不拒絕 shuffle 函式的結果，或是 shuffle 函式本身確實為 Uniform distribution 。
此外，從上方長條圖可見，24項數據之間的差異不大，整體分佈較接近常態分布。

亂度

閱讀 lab0(D)可知：

亂數的直覺與統計描述

直覺上，亂數代表無法預測的事件結果。
統計學透過機率分佈來描述亂數，使其具有可分析性。
雖然無法確定單次事件結果，但可以計算其發生範圍的機率或長期趨勢。

隨機性的資訊觀點

若一段文字無法傳遞資訊，可視為隨機，例如無意義的字母組合。
反之，若文字有可讀資訊，則非隨機。
資訊含量可作為衡量隨機性的標準。

資訊含量 Entropy

又名Shannon Entropy 定義是某個隨機事件平均每個結果發生時所能傳達出的資訊量，公式如下：

$S = - \sum_{i = 1}^{n} P (x_{i}) l o g_{b} P (x_{i}) = \sum_{i = 1}^{n} P (x_{i}) I (x_{i})$
實際上也是 Self-information 的期望值為
$𝐼 (𝑥 𝑖)$ ，計算公式如下：

$I (x_{i}) = l o g_{b} (\frac{1}{P (x_{i})})$

可見，當事件發生的機率

P

上升時，其所包含的資訊量

I

便會下降。透過將發生機率與資訊量相乘，可以計算出其期望值

S

，進而評估系統所攜帶的總資訊量。

其和機器學習常使用的Cross Entropy 的公式挺相似的：

H (p, q) = - \sum_{x} p (x) \log q (x)

其中

𝑞 (𝑥)

是模型預測分佈，而

𝑝 (𝑥)

為真實分佈。

Shannon Entropy vs. Cross Entropy

	Shannon Entropy $H (P)$	Cross Entropy $H (P, Q)$
目的	衡量單一分佈的不確定性	衡量兩個分佈之間的相似度
$當 P = Q$	與交叉熵相等	等於 Shannon 熵
應用	資訊理論、編碼長度估計	機器學習損失函數、模型評估

實作 ent 亂度

實作的部分參考了 Charlie Chiou 大大的實作

讀取 linux 內建的 PRNG 前 1024 位元，並生成 random.txt。

$ head -c 1024 /dev/random > random.txt

重複輸出 ABCDEF 的字串並且擷取前 1024 位元，並生成 nonrandom.txt。

$ yes "ABCDEF" | head -c 1024 > nonrandom.txt

使用 ent 測試，可以得到下列結果：

$ ent random.txt
Entropy = 7.809143 bits per byte.

Optimum compression would reduce the size
of this 1024 byte file by 2 percent.

Chi square distribution for 1024 samples is 257.50, and randomly
would exceed this value 44.44 percent of the times.

Arithmetic mean value of data bytes is 128.7373 (127.5 = random).
Monte Carlo value for Pi is 3.223529412 (error 2.61 percent).
Serial correlation coefficient is -0.043946 (totally uncorrelated = 0.0).

$ ent nonrandom.txt
Entropy = 2.807348 bits per byte.

Optimum compression would reduce the size
of this 1024 byte file by 64 percent.

Chi square distribution for 1024 samples is 36425.50, and randomly
would exceed this value less than 0.01 percent of the times.

Arithmetic mean value of data bytes is 59.2979 (127.5 = random).
Monte Carlo value for Pi is 4.000000000 (error 27.32 percent).
Serial correlation coefficient is -0.162361 (totally uncorrelated = 0.0).

可以了解到 random.txt 因為內容隨機因此每一位元所包含的資料量較大，反應在 Entropy 上， 1 byte 包含接近8 bits 的資訊量。而 nonrandom.txt 的內容為重複的 6 個數字 + 1 個換行符號，因此每一個數字或符號出現機率為 1/7 ，透過公式計算：

S = - \sum_{i = 1}^{n} P (x_{i}) l o g_{b} P (x_{i}) = - 7 \times (\frac{1}{7}) \times \log_{2} \frac{1}{7} = 2.807355

和實際結果接近，表示 1 byte 僅攜帶約 2.8 bits 的資訊量
計算P-value：

from scipy import stats
a = 1 - stats.chi2.pdf(257.5, 1023)
b = 1 - stats.chi2.cdf(36425.5, 1023)
>a
1.0
>b
0.0

可知前者數據為隨機的；後者則否。

實作 qtest 亂度

一樣參考了 Charlie Chiou 大大的實作
在 qtest 中執行 option entropy 1 並搭配 ih RAND 10 來觀察亂數的分佈，其輸出結果如下：

cmd> it RAND 10
l = [zgqlnj(29.69%) dcnrtipab(37.50%) iqzvhbya(35.94%) abqumpfr(35.94%) nyiov(26.56%) kptuou(26.56%) tjljft(21.88%) lfuwrxlf(29.69%) gstphxag(32.81%) kfhzvzdtf(32.81%)]

熵的計算是透過 shannon_entropy.c 來計算：

統計字元頻率
bucket 是大小為 256 (BUCKET_SIZE = 1 << 8) 的陣列，用來計算每個字元的頻率

for (uint32_t i = 0; i < count; i++)
    bucket[s[i]]++;

這段程式碼遍歷整個字串 s，並記錄每個字元出現的次數。
2. 計算每個字元的機率和熵

for (uint32_t i = 0; i < BUCKET_SIZE; i++) {
    if (bucket[i]) {
        uint64_t p = bucket[i];
        p *= LOG2_ARG_SHIFT / count;
        entropy_sum += -p * log2_lshift16(p);
    }
}

字元出現的機率
$𝑃 (𝑥_{𝑖})$ ：

$p = \frac{字元出現次數}{總字元數 c o u n t}$

但這裡用的是 p *= LOG2_ARG_SHIFT / count;，因為 LOG2_ARG_SHIFT 是用來做整數近似計算的。

計算熵
$S$

S = - \sum_{i = 1}^{n} P (x_{i}) l o g_{b} P (x_{i})

這裡 log2_lshift16(p) 是一個預計算好的 log2 函數，使用了左移 16-bit 來進行整數運算，避免使用浮點數計算。

正規化熵值

entropy_sum /= LOG2_ARG_SHIFT;
return entropy_sum * 100.0 / entropy_max;

先將 entropy_sum 除以 LOG2_ARG_SHIFT 來轉換回標準熵值
再將結果正規化成百分比（範圍 0% ~ 100%）

以結果中以 gstphxag(32.81%) 為例，計算每個數字出現的機率如下：

words	times	probability	$l o g_{2} p (x)$	$- p (x) l o g_{2} p (x)$
g	2	2/8 = 0.25	-2	0.5
s	1	1/8 = 0.125	-3	0.375
t	1	1/8 = 0.125	-3	0.375
p	1	1/8 = 0.125	-3	0.375
h	1	1/8 = 0.125	-3	0.375
x	1	1/8 = 0.125	-3	0.375
a	1	1/8 = 0.125	-3	0.375
sum				2.75

總和為 2.75，又因為使用 1byte 編碼最大可包含的資訊量為 8bits，因此可透過下列公式正規化。

E n t r o p y = \frac{2.75}{8} \times 100 = 34.375

與程式計算大致吻合。

Dude, is my code constant time?

Time attack 屬於 side-channel attacks 的一種，攻擊者透過分析加密演算法的執行時間，試圖推測密碼系統的機密資訊並加以破解。
論文提出了 Dudect 工具，避免依賴靜態程式分析（static analysis），轉而採用對時間進行統計分析（statistical analysis），檢測一段程式是否能在 constant time 內完成任務。這種方法能降低測量時間時對硬體的依賴性，提升分析的適用性與準確性，也能避免被時序攻擊。

Timing Leakage Detection

本實驗的理論基於對執行時間的 leakage detection test 。透過比較兩組不同的測試資料，檢驗其執行時間的分佈是否存在顯著差異，以評估是否存在時間相關的資訊洩漏。

Step 1: Measure execution time

首先，反覆測量兩種 class 的輸入數據在加密函式上的執行時間：

random class：每次進行測量時，皆隨機選擇輸入數據。
fix class：每次進行測量時，皆固定選擇輸入數據。

Step 2: Apply post-processing

獲取執行時間，在進行統計檢定之前，可以先對數據進行適當的預處理

Cropping：
對於較長的執行時間，一般的時間分佈會呈現正偏，這通常是由測量誤差所引起，因為主要的測量函數可能會受到操作系統或外部程式的影響。在這種情況下，可以對測量值進行裁剪（即去除掉大於某個閾值的測量值），以減少這些異常值對分析結果的干擾，從而提高統計檢定的準確性。
Higher-order preprocessing:
統計檢驗可以通過高階預處理（high-order preprocessing）來獲得更深入的分析結果。例如，使用中心化積。

Step 3: Apply statistical test

最後，是透過統計檢驗試圖反證null hypothesis ––– 兩個時間分佈相等。有幾個可用的檢驗方式：

t-test：採用 Welch’s t-test。當 t 檢定拒絕虛無假設（無法證明平均值的差異），意味著執行時間為常數時間（constant time）。
Non-parametric tests：可透過 Non-parametric tests檢驗。其優點是這些測試通常對於潜在的總體分布的假設較少；缺點是他們可能收斂較慢，需要更多樣本。

Results

論文的後面則是針對不同的案例，透過論文方法驗證是否為constant time的結果。

而我照著上面的脈絡去查看dudect的原始碼，並分析 dedect 的原始碼
我將其分成四個步驟：

準備輸入資料

prepare_inputs(ctx->config, ctx->input_data, ctx->classes);

產生隨機測試資料，並對資料進行分類（通常是兩組不同的輸入）。

測量執行時間

static void measure(dudect_ctx_t *ctx) {
  for (size_t i = 0; i < ctx->config->number_measurements; i++) {
    ctx->ticks[i] = cpucycles();
    do_one_computation(ctx->input_data + i * ctx->config->chunk_size);
  }

  for (size_t i = 0; i < ctx->config->number_measurements-1; i++) {
    ctx->exec_times[i] = ctx->ticks[i+1] - ctx->ticks[i];
  }
}

測量目標函式 do_one_computation() 的執行時間，使用 cpucycles() 取得 CPU 時間戳記，並相減得出執行時間。

更新統計數據

static void update_statistics(dudect_ctx_t *ctx) {
  for (size_t i = 10; i < (ctx->config->number_measurements-1); i++) {
    int64_t difference = ctx->exec_times[i];

    if (difference < 0) {
      continue;
    }

    t_push(ctx->ttest_ctxs[0], difference, ctx->classes[i]);

    for (size_t crop_index = 0; crop_index < DUDECT_NUMBER_PERCENTILES; crop_index++) {
      if (difference < ctx->percentiles[crop_index]) {
        t_push(ctx->ttest_ctxs[crop_index + 1], difference, ctx->classes[i]);
      }
    }

    if (ctx->ttest_ctxs[0]->n[0] > 10000) {
      double centered = (double)difference - ctx->ttest_ctxs[0]->mean[ctx->classes[i]];
      t_push(ctx->ttest_ctxs[1 + DUDECT_NUMBER_PERCENTILES], centered * centered, ctx->classes[i]);
    }
  }
}

計算 Welch’s t-test，將執行時間數據分類並儲存，透過 t_push() 計算樣本數、平均值、變異數，共有三層檢測，分別是：原始執行時間的 t-test、不同裁剪門檻值下的 t-test、變異數檢測（中心化平方變異數 t-test）

分析結果與報告

static dudect_state_t report(dudect_ctx_t *ctx) {
  ttest_ctx_t *t = max_test(ctx);
  double max_t = fabs(t_compute(t));
  double number_traces_max_t = t->n[0] +  t->n[1];
  double max_tau = max_t / sqrt(number_traces_max_t);

  printf("meas: %7.2lf M, ", (number_traces_max_t / 1e6));
  if (number_traces_max_t < DUDECT_ENOUGH_MEASUREMENTS) {
    printf("not enough measurements (%.0f still to go).\n",
            DUDECT_ENOUGH_MEASUREMENTS-number_traces_max_t);
    return DUDECT_NO_LEAKAGE_EVIDENCE_YET;
  }

  printf("max t: %+7.2f, max tau: %.2e, (5/tau)^2: %.2e.",
    max_t, max_tau, (double)(5*5)/(double)(max_tau*max_tau));

  if (max_t > t_threshold_bananas) {
    printf(" Definitely not constant time.\n");
    return DUDECT_LEAKAGE_FOUND;
  }
  if (max_t > t_threshold_moderate) {
    printf(" Probably not constant time.\n");
    return DUDECT_LEAKAGE_FOUND;
  }
  if (max_t < t_threshold_moderate) {
    printf(" For the moment, maybe constant time.\n");
  }
  return DUDECT_NO_LEAKAGE_EVIDENCE_YET;
}

max_test(ctx) 找出最大 t 值的測試
max_t 是 Welch’s t-test 的最大值
max_tau 是標準化後的 t 值
(5/tau)^2 是估計最少需要多少次測量才能偵測出漏洞
判斷是否非常數時間：

max_t > t_threshold_bananas → Definitely not constant time
max_t > t_threshold_moderate → Probably not constant time
max_t < t_threshold_moderate → Maybe constant time

q_insert_head/q_insert_tail 非常數時間問題

在 TESTING trace trace-17-complexity 中，插入節點的功能總是被認為不是常數時間完成
在實際追蹤測試程式之前，我原本以為可能跟 strlcpy 有關，然而在試了也修改過多次後，依然沒辦法成功，有時候本地端會意外的成功，然而遠端卻從未成功。
在參考了 weiso131 大大和 Charlie Chiou 大大的實作後，大概知道了作業原始檔中和論文原始碼在執行步驟上的差別：

將 dudect 論文原始碼中的 prepare_percentiles 部份新增至作業原始檔中
將 update_statics 中的部份迴圈跳過，使其和論文的方法「丟棄第一次的執行結果並用 prepare percentile 取而代之」一致。
移除DROP_SIZE。在 constant.c 測量數據的時候，其範圍是從 DROP_SIZE 到 N_MEASURES - DROP_SIZE，這可能會導致會在計算 t 值的時候，會計算到未初始化的且不是測量數據的數值。

Linux 核心的鏈結串列排序

Linux 核心原始程式碼的 merge sort 是使用 bottom up 的合併方式，因為對 cache 較友善其過程中就是一直合併，cache 被參照到的機會更大。
而 list_sort 為了避免 cache thrashing 因此將合併：不合併維持在 2：1，因為只要

3 \times 2^{𝑘}

可以放得進 L1 cache。
count 為 pending list 中節點的數量，在 count 變 count + 1 後，可能會有兩種情況：

當 count + 1 後為
$2^{𝑘}$ ，就不合併（只有 leading 1 是 1，其餘都為 0）
當 count + 1 後不為
$2^{𝑘}$ ，就合併

count 變化	count 二進位	merge	pending 上的節點
0 $\to$ 1	0000 $\to$ 0001	no（ $2^{0}$ ）	1
1 $\to$ 2	0001 $\to$ 0010	no（ $2^{1}$ ）	1 $\leftarrow$ 1
2 $\to$ 3	0010 $\to$ 0011	yes	(2) $\leftarrow$ 1
3 $\to$ 4	0011 $\to$ 0100	no（ $2^{2}$ ）	2 $\leftarrow$ 1 $\leftarrow$ 1
4 $\to$ 5	0100 $\to$ 0101	yes	2 $\leftarrow$ (2) $\leftarrow$ 1
5 $\to$ 6	0101 $\to$ 0110	yes	(4) $\leftarrow$ 1 $\leftarrow$ 1
6 $\to$ 7	0110 $\to$ 0111	yes	4 $\leftarrow$ (2) $\leftarrow$ 1
7 $\to$ 8	0111 $\to$ 1000	no（ $2^{3}$ ）	4 $\leftarrow$ 2 $\leftarrow$ 1 $\leftarrow$ 1
8 $\to$ 9	1000 $\to$ 1001	yes	4 $\leftarrow$ 2 $\leftarrow$ (2) $\leftarrow$ 1
9 $\to$ 10	1001 $\to$ 1010	yes	4 $\leftarrow$ (4) $\leftarrow$ 1 $\leftarrow$ 1
10 $\to$ 11	1010 $\to$ 1011	yes	4 $\leftarrow$ 4 $\leftarrow$ (2) $\leftarrow$ 1
11 $\to$ 12	1011 $\to$ 1100	yes	(8) $\leftarrow$ 2 $\leftarrow$ 1 $\leftarrow$ 1
12 $\to$ 13	1100 $\to$ 1101	yes	8 $\leftarrow$ 2 $\leftarrow$ (2) $\leftarrow$ 1
13 $\to$ 14	1101 $\to$ 1110	yes	8 $\leftarrow$ (4) $\leftarrow$ 1 $\leftarrow$ 1
14 $\to$ 15	1110 $\to$ 1111	yes	8 $\leftarrow$ 4 $\leftarrow$ (2) $\leftarrow$ 1
15 $\to$ 16	1111 $\to$ 10000	no（ $2^{4}$ ）	8 $\leftarrow$ 4 $\leftarrow$ 2 $\leftarrow$ 1 $\leftarrow$ 1

除了知道是否要合併外，還需要知道從哪個位置開始合併
透過移動 tail 來完成：

for (bits = count; bits & 1; bits >>= 1)
    tail = &(*tail)->prev;
}

for迴圈中會一次一次的左移 bits 並檢查最低位的是否為 0 ，直到目標:找到 count 的最低位元為 0 的位置，如果 count 是奇數，tail 會回退 (代表前面有可合併的清單)；如果 count 是偶數，跳過這個for迴圈。
接著進入合併操作：

if (likely(bits)) {
    struct list_head *a = *tail, *b = a->prev;
    
    a = merge(priv, cmp, b, a);
    a->prev = b->prev;
    *tail = a;
}

若 bits 為真，代表有兩個長度相同的區塊需合併，透過 merge 函數合併 a 和 b，合併後的結果存回 *tail，形成更大的已排序區塊。
完成 merge 後便將下一個 list 的元素增加到 pending 中等待下一次的合併：

list->prev = pending;
pending = list;
list = list->next;
pending->next = NULL;
count++;

pending 已經是「組合好的多層清單」，每層是長度為 2^k 的已排序清單，從 pending 最後一層開始，不斷合併 pending 和 list，list 變成新的合併結果，並繼續向上合併。最後由 merge_final 建構回原本的雙向鍊結串列，至此完成 list_sort：

list = pending;
pending = pending->prev;
for (;;) {
    struct list_head *next = pending->prev;

    if (!next)
        break;
    list = merge(priv, cmp, pending, list);
    pending = next;
}
merge_final(priv, cmp, head, pending, list);