# 2024q1 Homework1 (lab0)
contributed by < `shiang1212` >
:::danger
留意各式細節 (如上方的空白字元)，唯有重視小處並步步為營，方可挑戰原始程式碼規模超越三千七百萬行的 Linux 核心
:::
### Reviewed by `ssheep773`
* 這四個 commit 都是使用相同的 commit message "Add files via upload"
[commit 3085d94](https://github.com/Shiang1212/lab0-c/commit/3085d9468cfab57f81f5eddd58265ba1c8a288f9) 、 [commit 7cfd185](https://github.com/Shiang1212/lab0-c/commit/7cfd185923a2fb46cd7d23ca3fc12b95e2840d82) 、 [commit fdd430b](https://github.com/Shiang1212/lab0-c/commit/fdd430bd679c497cd01d6fd87aa9f1252ce5c4b8) 、 [commit 21feb34](https://github.com/Shiang1212/lab0-c/commit/21feb34b4648decd0b06fb4beb44367512ccf97c) ，使用相同的名稱且並未說明實際的更改內容，會導致後續維護困難
### Reviewed by `SimonLee0316`
* 在 git commit 時，不同功能<s>建議</s> 分開，這樣才好維護
> 明確指出是哪幾個 git commits，既然你認為這位學員做不好，那就做出一次好的給他看，這樣才有討論和學習的效果。 :notes: jserv
### Reviewed by `stevendd543`
* 在你比較 `malloc` 與 `calloc` 差異時，你將未初始化的 `malloc` 印出 0 的原因在於，讀取未被初始化的記憶體在 C 語言中屬於未定義的行為，因此在印出來的值是 garbage value 剛好是 0。[參考資料](https://www.geeksforgeeks.org/difference-between-malloc-and-calloc-with-examples/)
* 不必列出完整程式碼，我也是被老師提醒過，但後來發現不如把遇到的問題分析條列出來，不僅提醒自己，讀者也能學到東西。
>首先宣告一個 element_t，並為其配置記憶體，若配置失敗則回傳 false。接著為該 element_t 的 char *value 配置記憶體，注意 malloc 的記憶體大小為 strlen(s) + 1，應該是考慮到字串結束符號 '\0。此時如果配置失敗，在則回傳 false 之前，記得要把剛剛配置好的記憶體釋放掉。接著使用 strcpy 將字串內容 s 複製給該 element_t 的 char *value，這樣就完成了新節點的宣告。
舉例這段來說，其實你想表達在配置記憶體的流程與注意事項，這是好的探討，但在漢語上有些不通順，當你回頭看自己的筆記時，會發現自己把簡單的邏輯敘述的太雜亂。
## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
$ 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): 12
On-line CPU(s) list: 0-11
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i7-8750H CPU @ 2.20GHz
CPU family: 6
Model: 158
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
Stepping: 10
CPU max MHz: 4100.0000
CPU min MHz: 800.0000
BogoMIPS: 4399.99
Virtualization: VT-x
Caches (sum of all):
L1d: 192 KiB (6 instances)
L1i: 192 KiB (6 instances)
L2: 1.5 MiB (6 instances)
L3: 9 MiB (1 instance)
```
## 指定的佇列操作
### 先備知識
#### `element_t`
```c
typedef struct {
char *value;
struct list_head list;
} element_t;
```
#### `list_head`
```c
struct list_head {
struct list_head *prev;
struct list_head *next;
};
```
`element_t` 作為佇列中的基本元素（節點），該結構體的成員有 `char *value` 與 `struct list_node list`，前者用來表示該節點裝著什麼字串，後者為一結構體裝著兩個 `struct list_head` 的指標，用來表示該元素的前一個與後一個節點記憶體位置。
:::danger
改進你的漢語表達。
:::
整體架構如下圖：
參考<s>其他同學</s> 的圖後，發現製圖方法仍有錯誤，
:::danger
明確標注同學的 GitHub 帳號名稱。
:::
應使用 HackMD 中的程式碼區塊，如下
\```graphviz
(程式碼)
\```
待修改
:::danger
1. 使用 Graphviz 製圖，並嵌入到 HackMD
2. 避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景。
:::
### `q_new`
:::danger
程式碼註解一律用美式英語書寫。
:::
```diff
struct list_head *q_new()
{
struct list_head *head = malloc(sizeof(struct list_head));
+ if(!head)
+ return NULL;
INIT_LIST_HEAD(head); // prev and next point to head
return head;
}
```
:::danger
用語要精準，「正常」和「不正常」的分野對應於記憶體配置是如何？
> 已修正
:::
第 3 行使用到 `malloc` 配置記憶體給 `head`，**在記憶體空間充足且先前行為不存在記憶體越界存取的情況**，`malloc` 會配置一個大小為 `struct list_head` 位元組 (Byte) 的記憶體，並回傳一個指標指向該記憶體，但並不是每次 `malloc` 都會那麼順利。
:::danger
access 的翻譯是「存取」，而非「訪問」(visit)。
改進你的漢語表達。
> <s>已修正</s>
> 沒做到的事，不要輕易宣告。你認為上述是清晰、明確，且通順的漢語表達嗎？ :notes: jserv
:::
:::warning
前後關聯是什麼？
:::
以下節錄自 cmd 執行 `$ man malloc` 之結果：
> #### RETURN VALUE
>The malloc() and calloc() functions return a pointer to the allocated memory, which is suitably aligned for any built-in type. **On error, these functions return NULL. NULL may also be returned by a successful call to malloc() with a size of zero**, or by a successful call to calloc() with nmemb or size equal to zero.
使用 `malloc` 配置記憶體，在成功配置的情況下，`malloc` 會回傳一個指標指向對應大小的記憶體位置；在配置失敗或 size 為 0 的情況下，`malloc` 會回傳 NULL。所以需要用第 4～5 行。
此外，`malloc` 的 man page 提到：
>The **malloc()** function allocates size bytes and returns a pointer to the allocated memory. **The memory is not initialized**. If size is 0, then malloc() returns either NULL, or a unique pointer value that can later be successfully passed to free().
>
> The **calloc()** function allocates memory for an array of nmemb elements of size bytes each and returns a pointer to the allocated memory. **The memory is set to zero.** If nmemb or size is 0, then calloc() returns either NULL, or a unique pointer value that can later be successfully passed to free().
相比使用 `calloc`，在使用 `malloc` 配置記憶體時，該記憶體不會被初始化成 0。
好奇 `malloc` 丟出來的未初始化記憶體長怎樣，所以我寫了以下程式測試： (`test.c`)
```c
#include <stdio.h>
#include <stdlib.h>
int main()
{
int *arr = malloc(sizeof(int) * 16);
for(int i = 0; i < 16; i++)
printf("%d ", *(arr + i));
return 0;
}
```
編譯並執行：
```shell
$ gcc test.c`
$ ./a.out`
```
得到的結果：
`0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0`
:::danger
工程人員說話要精準，避免說「好像」。
:::
:::warning
不知道為什麼<s>看起來好像</s>初始化過，在猜會不會是沒被修改過的記憶體都是初始化為 0，或是 OS 和編譯器的關係，待研究。
sbrk()?
program break?
:::
### `q_free`
```c
void q_free(struct list_head *head)
{
if (!head)
return;
element_t *entry, *safe;
list_for_each_entry_safe (entry, safe, head, list)
q_release_element(entry);
free(head);
return;
}
```
:::danger
避免非必要的項目縮排 (即 `* `)，以清晰、明確，且流暢的漢語書寫。
> 已修正
:::
若 `head` 為空，則代表沒有記憶體需要被釋放，所以 return。接下來使用 `list.h` 裡面提供的 `list_for_each_entry_safe` 走訪每個節點。再使用 `q_release_element` 回收該節點的記憶體。最後回收掉 `head` 本身。
:::danger
不該先列出程式碼，相反的，你該先探討自己的想法、考慮因素，具體實施的方案，過程中可能會有副作用 (side effect)，這都要涵蓋。這是工程素養之一，即有效的溝通。
:::
### `q_insert_head`
```c
bool q_insert_head(struct list_head *head, char *s)
{
element_t *new = malloc(sizeof(element_t));
if(!new)
return false;
new->value = malloc(strlen(s) + 1);
if(!new->value)
{
free(new);
return false;
}
strcpy(new->value, s);
list_add(&new->list, head);
return true;
```
:::danger
避免非必要的項目縮排 (即 `* `)，以清晰、明確，且流暢的漢語書寫。
> <s>已修正</s>
> 沒做到的事，不要輕易宣告。你認為這份筆記以清晰、明確，且通順的漢語書寫嗎？ :notes: jserv
:::
首先宣告一個 `element_t`，並為其配置記憶體，若配置失敗則回傳 false。接著為該 `element_t` 的 `char *value` 配置記憶體，注意 `malloc` 的記憶體大小為 `strlen(s) + 1`，應該是考慮到字串結束符號 `'\0`。此時如果配置失敗，在則回傳 false 之前，記得要把剛剛配置好的記憶體釋放掉。接著使用 `strcpy` 將字串內容 `s` 複製給該 `element_t` 的 `char *value`，這樣就完成了新節點的宣告。
準備好要新增的節點之後，使用 `list.h` 提供的 `list_add`，將該`element_t` 串在 `head` 的前面，達到新增 `element_t` 於佇列前端之效果。
:::warning
參考 [wanghanchi](https://hackmd.io/@wanghanchi/linux2023-lab0)，在執行字串複製時，他使用 `memcpy` 取代 `strcpy`。
:::
我查看 `strcpy` 的 man page
> ### char *strcpy(char *dest, const char *src);
> #### DESCRIPTION
>The strcpy() function copies the string pointed to by src, including the terminating null byte ('\0'), to the buffer pointed to by dest. The strings may not overlap, and the destination string dest must be large enough to receive the copy. **Beware of buffer overruns! (See BUGS.)**
>#### BUGS
>**If the destination string of a strcpy() is not large enough, then anything might happen.** Overflowing fixed-length string buffers is a favorite cracker technique for taking complete control of the machine. Any time a program reads or copies data into a buffer, the program first needs to check that there's enough space. This may be unnecessary if you can show that overflow is impossible, but be careful: programs can get changed over time, in ways that may make the impossible possible.
總而言之，`strcpy` 會走訪 `src` 指向的字串的每個字元，在碰到空字元 `'\0'` 之前，逐 Byte 寫入 `dest`。但 `strcpy` 缺乏寫入合法性的判斷，影響程式的穩健性 (robustness)。
而 `string.h` 裡有一個與 `strcpy` 相似的函式：`char *strncpy(char *dest, const char *src, size_t n)`，以下為 strncpy 的 man page 提供的實作範例：
```c
char *strncpy(char *dest, const char *src, size_t n)
{
size_t i;
for (i = 0; i < n && src[i] != '\0'; i++)
dest[i] = src[i];
for ( ; i < n; i++)
dest[i] = '\0';
return dest;
}
```
這個函式相較 `strcpy` 多了一個 `size_t n` 參數，用來表示要寫入 `dest` 的字元數量，在呼叫函式的時候就先決定好要寫入的字元數量，確保不會有 overflow 的情況發生。
### `q_insert_tail`
如 `q_insert_head` ，把 `list_add(&new->list, head)` 改成 `list_add_tail(&new->list, head)`即可。
### `q_remove_head`
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *remove = list_entry(head->next, element_t, list);
if (bufsize)
{
strncpy(sp, remove->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
list_del(&remove->list);
return remove;
}
```
### `q_remove_head`、`q_remove_tail`
宣告一個 `element_t` 指標指向要刪除的節點 (head->next 或 head->prev)。確認 `bufisze != 0`並將該節點的字串內容複製給 `sp`，最後用 `list_del` 將該節點從鏈結串列中移除。
### `q_size`
先判斷該鏈結串列是否為空，是的話 return 0。接著走訪該鏈結串列的每個節點並累計長度。
### `q_delete_mid`
:::danger
不該先列出程式碼，相反的，你該先探討自己的想法、考慮因素，具體實施的方案，過程中可能會有副作用 (side effect)，這都要涵蓋。這是工程素養之一，即有效的溝通。
:::
```c
bool q_delete_mid(struct list_head *head)
{
if (!head)
return false;
struct list_head *fast = head->next->next, *slow = head->next;
while (!(fast == head->prev) && !(fast == head))
{
fast = fast->next->next;
if (fast == head->prev || fast == head) {
break;
}
slow = slow->next;
}
element_t *node = list_entry(slow->next, element_t, list);
list_del(&node->list);
q_release_element(node);
return true;
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
}
```
[7cfd185](https://github.com/sysprog21/lab0-c/commit/7cfd185923a2fb46cd7d23ca3fc12b95e2840d82) 中的 `q_delete_mid`，成功通過 [2095. Delete the Middle Node of a Linked List](https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/)，但完全無法應用在環狀雙向鏈結的場景下，於是我參考 [wanghanchi](https://hackmd.io/@wanghanchi/linux2023-lab0) 以及[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#circular-linked-list)中的龜兔賽跑 (快慢指標) 方法。
:::danger
什麼「核心」？本課程叫什麼名字，你還記得嗎？
> 已修正
:::
想法如下：
慢指標 `slow` 一次走一步，快指標 `fast` 一次走兩步，`fast` 走的步數會是 `slow` 的兩倍，所以**當 `fast` 走完鏈結串列的總長時，這時的 `slow` 只走了鏈結串列長度的一半**，也就是走到鏈結串列的中間節點，正好是 `q_delete_mid` 所要刪除的節點。
而判斷 `fast` 是否走到環狀鏈結串列的尾端可以分成兩個情況：
1. 鏈結串列的長度為奇數：
`fast` 從 `head` 出發後，每次走兩步，只會停在 `head` 和 Even 節點，而 `fast` 在走完鏈結串列的總長時，會剛好回到 `head`，判斷 `fast == head` 即可確認`fast` 是否走到該環狀鏈結串列的尾端。
2. 鏈結串列的長度為偶數：
這個情況 `fast` 只會停在 Even 節點，而最後一個 Even 節點正是 `head->prev`，所以判斷 `fast == head->prev`。
### `q_swap`
參考 [wanghanchi](https://hackmd.io/@wanghanchi/linux2023-lab0#q_swap) 的程式碼，**兩個節點位置交換，簡單來說就是把後者取出，放到前者的前面**，且因為是每兩個節點的交換，所以執行完交換後指標要往前兩個節點。
### `q_reverse`
```c
void q_reverse (struct list_head *head)
{
struct list_head *node, *safe;
list_for_each_safe (node, safe, head)
list_move(node, head);
}
```
參考 [randv](https://hackmd.io/@ranvd/linux2024-homework1#q_reverse) 的程式碼，使用 `list_for_each_safe` 走訪每個節點，用 `list_move` 將每個節點移除並放在 `head` 前端。
### `q_reverseK`
:::danger
不該先列出程式碼，相反的，你該先探討自己的想法、考慮因素，具體實施的方案，過程中可能會有副作用 (side effect)，這都要涵蓋。這是工程素養之一，即有效的溝通。
:::
```c=
void q_reverseK(struct list_head *head, int k)
{
// https://leetcode.com/problems/reverse-nodes-in-k-group/
if (!head || list_is_singular(head))
return;
struct list_head tmp_head;
INIT_LIST_HEAD(&tmp_head);
int ct = 0;
int size = q_size(head);
struct list_head *node, *safe;
list_for_each_safe (node, safe, head) {
ct += 1;
if (ct % k == 0 || ct == size) {
list_cut_position(&tmp_head, head, node);
q_reverse(&tmp_head);
list_splice_tail(&tmp_head, head);
}
if (ct == size)
break;
}
}
```
參考 [ShchangAnderson](https://hackmd.io/@ShchangAnderson/ryWsAyUna#q_reverseK) 的作法，走訪每個節點，每 `k` 個節點作一次 `q_reverse`，並用 `list_splice_tail` 從尾端存進一個新的串列。考慮到串列長度可能不整除 `k`，所以在判第 13 行加入 `ct == size`，保證剩餘的節點也能被處理到。
### `q_sort`
參考 [WangHanChi](https://hackmd.io/@wanghanchi/linux2023-lab0#q_sort) 的程式碼，採用 MergeSort 實作排序。
#### `merge_two_nodes`
:::danger
不該先列出程式碼，相反的，你該先探討自己的想法、考慮因素，具體實施的方案，過程中可能會有副作用 (side effect)，這都要涵蓋。這是工程素養之一，即有效的溝通。
:::
```c
struct list_head *merge_two_nodes(struct list_head *left,
struct list_head *right)
{
struct list_head *new_head = NULL, **indirect = &new_head, **iter = NULL;
for (; left && right; *iter = (*iter)->next) {
iter = strcmp(list_entry(left, element_t, list)->value,
list_entry(right, element_t, list)->value) >= 0
? &right
: &left;
*indirect = *iter;
indirect = &(*indirect)->next;
}
*indirect = (struct list_head *) ((uint64_t) left | (uint64_t) right);
return new_head;
}
```
使用間接指標，`iter` 負責找出目前擁有最小字串的節點是屬於哪個串列 (`left` or `right`)，`indirect` 負責將 `iter` 指的節點存進 `new_head`。
#### `merge_divide`
:::danger
不該先列出程式碼，相反的，你該先探討自己的想法、考慮因素，具體實施的方案，過程中可能會有副作用 (side effect)，這都要涵蓋。這是工程素養之一，即有效的溝通。
:::
```c
struct list_head *merge_divide(struct list_head *head)
{
if (!head || !head->next)
return head;
struct list_head *rabbit = head, *turtle = head, *middle;
for (; rabbit && rabbit->next;
rabbit = rabbit->next->next, turtle = turtle->next)
;
middle = turtle;
// cut off the link
turtle->prev->next = NULL;
struct list_head *left = merge_divide(head);
struct list_head *right = merge_divide(middle);
return merge_two_nodes(left, right);
}
```
利用快慢指標找出鍊結串列中點，找到後從中點將串列切開，變成 `head` 和 `middle` 兩條串列，再遞迴將這兩條串列從中點切開，直到每條串列只剩一個節點。
#### `q_sort`
:::danger
不該先列出程式碼，相反的，你該先探討自己的想法、考慮因素，具體實施的方案，過程中可能會有副作用 (side effect)，這都要涵蓋。這是工程素養之一，即有效的溝通。
:::
```c=
void q_sort(struct list_head *head, bool descend)
{
if (!head || list_empty(head))
return;
// cut off the link
head->prev->next = NULL;
head->next = merge_divide(head->next);
struct list_head *before = head, *after = head->next;
for (; after != NULL; after = after->next) {
after->prev = before;
before = after;
}
before->next = head;
head->prev = before;
}
```
第 6、7 行將 `head` 與原本為排序的串列斷開，並使用 `merge_divide` 得到排序好的串列。但因為 `merge_divide` 回傳的串列為單向鏈結串列，所以必須走訪每個節點，建構其 `*prev`。
### `q_ascend`、`q_descend`
:::danger
不該先列出程式碼，相反的，你該先探討自己的想法、考慮因素，具體實施的方案，過程中可能會有副作用 (side effect)，這都要涵蓋。這是工程素養之一，即有效的溝通。
:::
```c
int q_ascend(struct list_head *head)
{
// https://leetcode.com/problems/remove-nodes-from-linked-list/
if (!head || list_empty(head))
return 0;
element_t *right = list_entry(head->prev, element_t, list);
element_t *left = list_entry(head->prev->prev, element_t, list);
while (&left->list != head) {
if (strcmp(right->value, left->value) > 0) {
left = list_entry(left->list.prev, element_t, list);
right = list_entry(right->list.prev, element_t, list);
} else {
list_del(&left->list);
free(left->value);
free(left);
left = list_entry(right->list.prev, element_t, list);
}
}
return q_size(head);
}
```
該函式目的為刪除節點使該串列成為嚴格遞增/遞減串列。
這裡提到的數值遞增遞減，是指字串中逐字元的 ASCII 值，使用 `strcmp` 可以很好得到兩字串間字元的大小關係。
用兩個指標由後往前尋訪每個節點，當 `strcmp(right->value, left->value) > 0` 發生時，代表後節點的字串大於前節點的字串，兩節點為遞增關係。反之，當 `strcmp(right->value, left->value) < 0` 發生，代表前節點的字串大於後節點的字串，兩節點為遞減關係。
### `q_merge`
:::danger
不該先列出程式碼，相反的，你該先探討自己的想法、考慮因素，具體實施的方案，過程中可能會有副作用 (side effect)，這都要涵蓋。這是工程素養之一，即有效的溝通。
:::
```c
int q_merge(struct list_head *head, bool descend)
{
if (!head || list_empty(head)) {
return 0;
}
if (list_is_singular(head)) {
return list_entry(head->next, queue_contex_t, chain)->size;
}
queue_contex_t *merged_list = list_entry(head->next, queue_contex_t, chain);
for (struct list_head *p = head->next->next; p != head; p = p->next) {
queue_contex_t *node = list_entry(p, queue_contex_t, chain);
list_splice_init(node->q, merged_list->q);
}
q_sort(merged_list->q, descend);
return q_size(merged_list->q);
}
```
參考 [Kuanch](https://hackmd.io/@Kuanch/linux2024-homework1#%E5%AF%A6%E4%BD%9C%E6%8C%87%E5%AE%9A%E7%9A%84%E4%BD%87%E5%88%97%E6%93%8D%E4%BD%9C) 以及 [WangHanChi](https://hackmd.io/@wanghanchi/linux2023-lab0#q_merge) 的說明。
> 根據要求，傳入的 `head` 為 `queue_contex_t` 的 `head` ，因此也會需要將節點往 `next` 移動一格才開始存取每個 `queue` 的 `head`。
首先來看 `queue_contex_t` 是什麼東西
```c
typedef struct {
struct list_head *q;
struct list_head chain;
int size;
int id;
} queue_contex_t;
```
+ `q` 用來指向佇列的 head
+ `chain` 用來串連多個佇列的 head
+ `id`、`size` 紀錄該佇列的資訊
```graphviz
digraph node_t {
rankdir=LR;
subgraph head{
label ="head";
head [shape=record, label="head"];
}
subgraph cluster_0 {
label="queue_contex_t";
node1 [shape=record, label="<f1>*q | <f2>chain | size | id"];
}
subgraph cluster_1 {
label="queue_contex_t";
node2 [shape=record, label="*q | <f2>chain | size | id"];
}
{
head -> node1:f2;
node1:f2 -> node2:f2;
}
}
```
:::info
TODO: 增加 `*q` 指向雙向鏈結串列
:::
用 `p` 走訪這個 chain 的每個節點，合併每個節點指向的雙向鏈結串列至首個節點，最後再用 `q_sort` 將首個節點排序，實現合併並且排序的效果。
:::danger
1. HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」，不是用來「假裝自己有付出」。
2. 不要說「寫得很醜」這樣不明確的話語，你乾脆說「因為我的母語不是英語，所以我不適合寫程式」？我們在工程領域要知道哪裡做不好，才可改進，列出明確的改進事項。
3. 不要說「優化一下」，工程追求持續的演化和改進。
> 知道了!
:::
---
## 使用 valgrind 排除 qtest 記憶體問題
在終端機執行
make valgrind
trace-17 跑了很久，執行結果尚無找到記憶體問題。
```shell
TOTAL 100/100
```
---
## 論文閱讀〈Dude, is my code constant time?〉
### 論文介紹
這篇論文提出時序洩漏檢測 (timing leakage detection) 工具 dudect，用以評估程式碼在特定平台上是否能在常數時間內運行完畢。
現有的方法大多需要模擬硬體行為，而硬體製造商釋出的硬體資訊卻少之又少，十分不利於檢測工具的開發。這篇論文基於以上問題提出改善方案，提出的 dudect 檢測工具不使用靜態程式分析 (static analysis)，而是使用對於時間的統計分析 (statistical analysis)，藉此避免測量時間的方法對於硬體產生依賴性。
#### 時序攻擊
時序攻擊 (timing attack) 是[旁路攻擊](https://zh.wikipedia.org/zh-tw/%E6%97%81%E8%B7%AF%E6%94%BB%E5%87%BB)的一種，攻擊者透過加密算法所需的執行時間推斷敏感訊息，導致安全漏洞。舉例來說，若加密算法在判斷密碼是否正確時，是使用逐字元的判斷並在偵測字元不匹配時回傳，攻擊者在多次嘗試並觀察演算法的執行時間，判斷輸入字元是否匹配成功，進而推得出密碼。
為了避免時序攻擊，可以使用時序洩漏偵測工具，或是使用常數時間演算法來處理敏感資訊，將時間差異最小化，甚至可以引入隨機元素，使攻擊者難以通過觀察時間模式來推斷信息。
#### 時序洩漏偵測
時序洩漏偵測 (Timing leakage detection) 用於檢測演算法是否存在時序洩漏的風險，以此防止時序攻擊。通常會分析程式的執行模式，包括時間消耗、記憶體存取模式、CPU使用率等。透過觀察這些模式的變化，以發現可能存在的時序泄漏漏洞。
#### 論文方法步驟介紹
1. Measure execution time
測量兩個不同類別的輸入資料在加密函式上的執行時間，並得到兩個數據分布。
* a) Classes definition
使用兩種不同類別的輸入資料，反覆進行測驗，這篇論文採用 fix-vs-random 測驗方式，第一組輸入資料使用特定常數 (通常第一類會觸發 corner-case)，第二類則隨機產生。
* b) Cycle counters
使用 CPU 提供的 cycle counter，以獲得更精準的執行時間。
* c) Environmental conditions:
原文提到，為了最小化環境的差異，每次測量都對應到一個隨機的類別。
:::warning
疑問：不清楚 c) 的每個測量都對應一個隨機的類別是什麼意思，目前想法是每次測量都使用隨機的輸入資料類別，但這又和減少環境差異有什麼關係呢？
:::
2. Apply post-processing
得到數據分布後，可以對其進行資料後處理。
* a) Cropping
對於較長的執行時間，大部分的時間分佈都是呈 [positively skewed distribution](https://www.managedfuturesinvesting.com/what-is-skewness/)，可能是因為測量誤差 (measurement artifacts)，測量函式會受到 OS 或者外部程式影響。這種情況下，可以裁剪特定測量值以便後續檢定。
* b) Higher-order preprocessing
依照不同的假說檢定應用，使用更高階的資料預處理。
3. Apply statistical test
使用假說檢定試圖推翻虛無假說：「兩個數據分布是相同的」，驗證對立假說：「兩個數據分布不是相同的」，藉此判斷該加密函式是否存在時序洩漏問題。
* a) t-test
採用的假說檢定方法是 Welch-test。
### Student's t-distribution
#### 介紹
Student's t-distribution，簡稱 t 分布，t 分布為一連續對稱分布，t 分布與期望值為0變異數為1常態分布特徵相似(鐘形、對稱於平均數 0、數值向兩側延伸)。在樣本數小或母體標準差未知的情況下，使用樣本標準差取代母體標準差，並使用 t 分布進行推論。
t 分布定義了一個參數：自由度(degrees of freedom)，隨著自由度 越大，t 分布的分布狀況越接近常態分布，當自由度逼近無限時，t 分布就會退化成常態分布。
#### 用途
Student's t-distribution 可以用於假設檢定上，在樣本數過小或母體標準差未知的情況下，通常會比常態分布更適合用於假設檢定。
:::danger
沒做到的事，不用裝忙。
:::
### simulation 運作
參考 [jimmylu890303](https://hackmd.io/@jimmylu0303/linux2024-homework1#simulation-%E9%81%8B%E4%BD%9C) 的作法，在 trace-17 中，會檢查 `q_insert_head`、`q_insert_tail`、`q_remove_head`、`q_remove_tail` 是否能在常數時間內完成。
首先，在 `fixture.h` ，可以看到 `is_##x##_const()` 的宣告：
```c
/* Interface to test if function is constant */
#define _(x) bool is_##x##_const(void);
DUT_FUNCS
#undef _
```
:::danger
查閱 C 語言規格書，針對 Concatenation 進行解說，使用規格書裡頭的術語。
:::
:::info
TODO：C99 6.10.3.3 The ## operator
:::
在 <s>`#define` 中</s> ，"##" 表示的是連接運算子。以下為例子：
```c
#define Conn(x, y) x##y
int num = Conn(123, 456);
// num = 123456
char *str = Conn("abc","def");
// str = "abcdef"
```
其中的 `DUT_FUNCS` 又可以在 `constant.h` 裡看到：
```c
#define DUT_FUNCS \
_(insert_head) \
_(insert_tail) \
_(remove_head) \
_(remove_tail)
```
在 `qtest.c` 中，當 `simulation == 1` 時會呼叫 `is_##x##_const`。
```c
static bool queue_insert(position_t pos, int argc, char *argv[])
{
if (simulation) {
if (argc != 1) {
report(1, "%s does not need arguments in simulation mode", argv[0]);
return false;
}
bool ok =
pos == POS_TAIL ? is_insert_tail_const() : is_insert_head_const();
if (!ok) {
report(1,
"ERROR: Probably not constant time or wrong implementation");
return false;
}
report(1, "Probably constant time");
return ok;
}
...
}
```
```c
static bool queue_remove(position_t pos, int argc, char *argv[])
{
if (simulation) {
if (argc != 1) {
report(1, "%s does not need arguments in simulation mode", argv[0]);
return false;
}
bool ok =
pos == POS_TAIL ? is_remove_tail_const() : is_remove_head_const();
if (!ok) {
report(1,
"ERROR: Probably not constant time or wrong implementation");
return false;
}
report(1, "Probably constant time");
return ok;
}
...
}
```
又可以在 `fixture.c` 看 `is_##x##_const()` 的實作，發現最後會呼叫 `test_const(#op, DUT(op))`
```c
#define DUT_FUNC_IMPL(op) \
bool is_##op##_const(void) { return test_const(#op, DUT(op)); }
#define _(x) DUT_FUNC_IMPL(x)
DUT_FUNCS
#undef _
```
使用 `test_const(#op, DUT(op));` 進行測試。
```c
static bool test_const(char *text, int mode)
{
bool result = false;
t = malloc(sizeof(t_context_t));
for (int cnt = 0; cnt < TEST_TRIES; ++cnt) {
printf("Testing %s...(%d/%d)\n\n", text, cnt, TEST_TRIES);
init_once();
for (int i = 0; i < ENOUGH_MEASURE / (N_MEASURES - DROP_SIZE * 2) + 1;
++i)
result = doit(mode);
printf("\033[A\033[2K\033[A\033[2K");
if (result)
break;
}
free(t);
return result;
}
```
### 更改 deduct
> 在 oreparaz/dudect 的程式碼具備 percentile 的處理，但在 lab0-c 則無。
:::info
TODO：參考 [willwillhi](https://hackmd.io/@willwillhi/lab0-2023#dudect)、[Wufangni](https://hackmd.io/CBRWJ1UTT_6E27T1Lm4T1w?view#%E6%8F%90%E4%BE%9B%E6%96%B0%E7%9A%84%E5%91%BD%E4%BB%A4-shuffle)
:::
## Fisher-Yates Shuffle 實作
Fisher-Yates Shuffle 是由 Fisher 和 Yates 提出的亂序演算法，該演算法的實作概念：**從最後一個元素開始，將每個元素與其前面隨機一個元素交換**。
要在 lab0-c 裡實作 Fisher-Yates Shuffle，首先我們需要做出 swap function，這裡的 swap function 跟佇列操作裡的 `q_swap` 不同，`q_swap` 做的是**前後兩個元素的交換**，swap function 要做的是**任意兩個節點的交換**。
Sign in with Wallet
Connect another wallet