# 2023q1 Homework1 (quiz1)
contributed by < [chiwawachiwawa](https://github.com/Chiwawachiwawa) >
:::danger
注意書寫規範，中英文間用一個空白字元區隔。依循[資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)指示，調整用語。
:notes: jserv
:::
:::info
好的!
:::
[kernel_code](https://github.com/torvalds/linux/blob/master/include/linux/list.h)
## 作業要求
- [ ] 修改 `queue.[ch]` 以完成 `make test` 自動評分系統的所有項目
- [ ] 研讀 Linux 核心原始程式碼的 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 並嘗試引入到 lab0-c 專案，比較你自己實作的 merge sort 和 Linux 核心程式碼之間效能落差
- [ ] 確保 `qtest` 提供的 `web` 命令可以搭配上述佇列使用
- [ ] 新增命令 `shuffle`, 參考 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle)
- [ ] 在 `qtest` 中執行 `option entropy 1` 並搭配 `ih RAND 10`
- [ ] 研讀論文〈[Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)〉，解釋本程式的 “simulation” 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 [Student’s t-distribution](https://en.wikipedia.org/wiki/Student%27s_t-distribution) 及程式實作的原理。
## 開發環境
## 更改 queue.c
### 1.new
```c
struct list_head *q_new()
{
struct list_head *queue_head = malloc(sizeof(struct list_head));
if (!queue_head)
return NULL;
INIT_LIST_HEAD(queue_head);
return queue_head;
}
```
:::danger
依循 [CONTRIBUTING.md](https://github.com/sysprog21/lab0-c/blob/master/CONTRIBUTING.md) 規範的程式碼風格，包含本筆記列出的程式碼。
:notes: jserv
:::
<s>[malloc():](https://legacy.cplusplus.com/reference/cstdlib/malloc/?kw=malloc)</s>
[malloc(3)](https://man7.org/linux/man-pages/man3/malloc.3.html)
> man page 視為第一手材料。
> :notes: jserv
> 好的!會注意
> :dog: chiwawa
### 2.free
[free():](http://tw.gitbook.net/c_standard_library/c_function_free.html)
```c
void q_free(struct list_head *l)
{
if(!l)
return;
element_t *q_entry , *enable;
list_for_each_entry_safe(q_entry, enable, l, list)
{
q_release_element(q_entry);
}
free(l);
}
```
### 3.q_insert_head
```c
bool q_insert_head(struct list_head *head, char *s)//testing
{
if(!head)
return false;
element_t *insert_node = malloc(sizeof(element_t));
if(!insert_node)
return false;
size_t strsize = strlen(s) + 1;
insert_node->value = malloc(strsize * sizeof(char));
if(!insert_node->value){
free(insert_node);
return false;
}
memcpy(insert_node->value, s, strsize);
list_add(&insert_node->list, head);
return true;
}
```
### 4.q_insert_tail
```c
bool q_insert_tail(struct list_head *head, char *s)//**testing
{
if(!head)
return false;
element_t *insert_node = malloc(sizeof(element_t));
if(!insert_node)
return false;
size_t strsize = strlen(s) + 1;
insert_node->value = malloc(strsize * sizeof(char));
if(!insert_node->value){
free(insert_node);
return false;
}
memcpy(insert_node->value, s, strsize);
list_add_tail(&insert_node->list, head);
return true;
}
```
### 5.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 *rmtarget = list_last_entry(head, element_t, list);
list_del(&rmtarget->list);
if(sp){
size_t len = strlen(rmtarget->value) + 1;
len = (bufsize - 1) > len ? len : (bufsize - 1);
strncpy(sp, rmtarget->value, len);
sp[len] = '\0';
}
return rmtarget;
}
```
### 6.q_remove_tail
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if(!head||list_empty(head))
return NULL;
element_t *element = list_last_entry(head, element_t, list);
if (sp) {
strncpy(sp, element->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
list_del(&element->list);
return element;
}
```
### 7.q_size
這邊我採用的是經典的逐個走訪
```c
int q_size(struct list_head *head)
{
if(!head)
return 0;
int count = 0;
struct list_head *node;
list_for_each (node, head)
count++;
return count;
}
```
### 8.q_delete_mid
我用的方法為上課時提到的***快慢法***
:::danger
注意用語！
:notes: jserv
:::
:::info
done!
:::
```
bool q_delete_mid(struct list_head *head)
{
if(!head || list_empty(head))
return false;
struct list_head *s = head->next, *f = head->next;
while (f != head && f != head->prev){
s = s->next;
f = f->next->next;
}
element_t *rmelement = list_entry(s, element_t, list);
list_del(&rmelement->list);
q_release_element(rmelement);
return true;
}
```
### 9.q_delete_dup
我想要嘗試使用 hash 來實作，此方法為暫時的權宜之計
```c
bool q_delete_dup(struct list_head *head)
{
if (!head || list_empty(head))
return false;
element_t *imm_node, *next_node;
bool dupornot = false;
list_for_each_entry_safe(imm_node, next_node, head, list){
if(imm_node->list.next != head && strcmp(imm_node->value, next_node->value) == 0){
list_del(&imm_node->list);
q_release_element(imm_node);
dupornot = true;
}
else if(dupornot){
list_del(&imm_node->list);
q_release_element(imm_node);
dupornot = false;
}
}
return true;
}
```
### 10.q_swap**
```
void q_swap(struct list_head *head)
if (head && !list_empty(head)){
struct list_head *target = head->next;
while (target != head && target->next != head){
struct list_head *temp = target;
list_move(target, temp->next);
target = target->next;
}
}
return;
}
```
### 11.q_reverse
無限迴圈
```c
void q_reverse(struct list_head *head) {
if (!head||list_empty)
return NULL;
struct list_head *imm_node, *enable_node;
list_for_each_entry_safe(imm_node, enable_node, head);{
list_move(head, imm_node);
}
}
```
fixed
```c
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head))
return;
struct list_head *n, *s, *t;
list_for_each_safe (n, s, head) {
t = n->next;
n->next = n->prev;
n->prev = t;
}
t = head->next;
head->next = head->prev;
head->prev = t;
}
```
### 12.q_reversek
:::danger
不用張貼完整程式碼，開發紀錄著重於你的想法、考量因素，還有相關的分析。僅列出佐證用的程式碼即可。
:notes: jserv
:::
:::info
好的!會注意。
:::
利用了上面的revers來解決,每K個元素作一次revers,利用一個counter來實作。
fixed
```c
/* Reverse the nodes of the list k at a time */
void q_reverseK(struct list_head *head, int k)
{
if(!head || list_empty(head))
return;
struct list_head *n, *s, iter, *fake_head = head;
int counter = 0;
INIT_LIST_HEAD(&iter);
list_for_each_safe(n, s, head){
counter++;
if(counter == k){
list_cut_position(&iter, fake_head, n);
q_reverse(&iter);
list_splice_init(&iter, fake_head);
counter = 0;
fake_head = s->prev;
}
}
}
```
### 13.q_sort(testing...)
採用分而治之的方式來解,採取 Doubly-linked List 結構,首先我們找到中心點,並將我們的 doubly-linked List 分為兩段,並且利用地回進行排序,再透過 list_cut_position(&r, head, mid) 進行切割,然後利用 list_splice_init(head, &l) 來將沒有head的那一端定義一個新的head出來,最後利用while來進行比較,將剩餘的 element 轉移到尾部。
```c
void q_sort(struct list_head *head){
if(!head || list_empty(head) || list_is_singular(head))
return;
struct list_head *middle;
{
struct list_head *l, *r;
l = head->prev;
r = head->next;
while (r != l && r->next != l)
{
r = r->next;
l = l->prev;
}
middle = r;
}
LIST_HEAD(r);
LIST_HEAD(l);
list_cut_position(&r, head, mid);
list_splice_init(head, &l);
q_sort(&r);
q_sort(&l);
while (!list_empty(&r) && !list_empty(&l))
{
if (strcmp(list_first_entry(&r, element_t, list)->value,
list_first_entry(&l, element_t, list)->value)<= 0)
{
list_move_tail(r.next, head);
}
else{
list_move_tail(l.next, head);
}
}
list_splice_tail(&r, head);
list_splice_tail(&l, head);
}
```
### 14.q_descend
```c
int q_descend(struct list_head *head)
{
struct list_head *c = head->prev, *n = head->prev->prev;
while(n != head){
if(strcmp(list_entry(n, element_t, list)->value,list_entry(c, element_t, list)->value) < 0){
list_del(n);
}
else{
c = n;
}
n = n->prev;
}
return q_size(head);
}
```
### 15.q_merge
在參考 [alanjian85](https://hackmd.io/@alanjian85/lab0-2023) 同學的實作後，我想要重新寫我的 `q_merge` (我一開始認為不能新增其他的函式)。
```c
int q_merge(struct list_head *head)
{
// https://leetcode.com/problems/merge-k-sorted-lists/
if (!head || list_empty(head))
return 0;
int count = 0;
struct list_head *first_head, temp_head;
first_head = list_entry(head->next, queue_contex_t, chain)->q;
INIT_LIST_HEAD(&temp_head);
for (;;) {
element_t *min_num = NULL;
queue_contex_t *entry, *min_content;
list_for_each_entry (entry, head, chain) {
if (entry->q == NULL || list_empty(entry->q))
continue;
element_t *element = list_first_entry(entry->q, element_t, list);
if (!min_num || strcmp(element->value, min_num->value) < 0) {
min_num = element;
min_content = entry;
}
}
if (!min_num)
break;
list_move_tail(&min_num->list, &temp_head);
count++;
if (min_content->q != first_head && list_empty(min_content->q))
min_content->q = NULL;
}
list_splice(&temp_head, first_head);
return count;
}
```
```
```
:::danger
文字訊息「不要」用螢幕截圖來展現，尊重視障朋友的閱讀權益。
:notes: jserv
> 好的!
:::
---
## 論文閱讀[Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)
### 什麼是 Student's t-distribution ?
t分佈的機率密度函數（ probability density function ）包含一個自由度（ degrees of freedom ）參數，自由度是樣本量 n 減去 1 。自由度越大， t 分佈越接近正態分佈。 t 分佈的機率密度函數是對稱的，且其平均值為 0。
t 分佈在機率密度函數曲線下的面積為 1 ，可以使用t表或統計軟件計算 t 分佈的機率。
t 分佈在統計學中有廣泛應用，例如用於小樣本量的假設檢定，或計算置信區間等。
### [dudect](https://)
Dudect 是一種偵測雙重執行（ Double Execution ）攻擊的工具。
本程式利用了統計的方式來進行檢測我們的程式是否存在擁有倍以上手法攻擊的漏洞。
### 統計學在本作業之中的應用
對於本程式的應用,我們在執行 make test 時,可以看到以下訊息:
```
Testing if time complexity of XXX is constant
meas:not enough measurements (XXXXX still to go)
```
這就是本作業再進行"隨機的(目前暫定為,等等我們會探討)"檢驗,利用 dudect 來測量我們這些程式是否為 constent time
在這其中,我發現了一個非常有趣的現象(見下一節)
## 隨機性
我在實作的過程中,發現了一個現象,在我們不改變 queue[ch] 兩個檔案的前提之下,每次測驗的分數,雖然看似相同,但是有少數出現較高或是較低的現象(如圖下所見)
1.第一次出現了 94 分
2.但我在之後的測試(以及之前多次的測試)皆為上述的 89 分
但總體上,我發現這個現象只會發生比預期分數還高的情形,比預期分數還低的情況我還沒遇到過,為了測試這個猜想,我用我的電腦測試了 30 次,其中出現了 94 分的情形有 2 次,其餘 28 次皆為 89 分,這個情形令我十分好奇,因此我想了解其中的原因。
3.首先,我們打開專案中的檔案,有關隨機性的部分 `random.[ch]` 。
很明顯,我根本看不懂,這時候,我想到利用chatGPT能否給我需要的資訊來參考。
由 chatGPT 的提示可以知道,作業中的檔案是為 Unix-like 平台定義了 randombytes() 實作,而有了他的提示之後,我發現我可以讀 [gcc/libstdc++-v3/include/bits/random.h](https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/random.h)，透過它來了解我們的程式是如何產出「隨機性」。
因為這段程式有 6000 多行,這代表又需要我們的 chatGPT 上場了。
## True Random Number Generator
* `random_device` 是 C++ STL 中提供的一種用於產生真正的隨機數的類。它的行為會根據系統而有所不同，但通常會使用優質熵源（如硬件噪聲）來生成隨機數。**(來自 chatGPT )**。這種情況下,是可以產生"真正的"隨機數的,而在察看了原文件後,我發現作品中使用 randombytes_linux_randombytes_getrandom() 來生成亂數,這樣就代表,其實我們在作業中得到的亂數是真正的亂數,而非是經過數學運算的,這也是 dudect 派上用場的原因之一,因為這個專案他強調的是不需要我們硬體的設計(在文章開頭有提到),就可以拿來判別是否為 constent time (他利用的是統計學),
### getrandom()
Linux kernel 中有一些驅動程式會使用硬體 TRNG 來生成隨機數,當需要隨機數時,Linux kernel 會檢查這些裝置是否可用，並且使用它們生成隨機數。
**以下這段來自chatGPT**
`除了硬體 TRNG 外，還有一些使用軟體技術來實作 TRNG 的方法。例如，Linux kernel 中有一個名為 "entropy pool" 的子系統，該子系統收集系統中不可預測的事件，例如中斷、鍵盤輸入和網絡數據包等。這些事件被稱為 "熵源"，它們被使用來產生隨機數。這個子系統可以防止軟體 PRNG 因缺乏熵而產生可預測的隨機數。`
[如何實作一個TRNG](https://blog.csdn.net/swithin_he/article/details/80795421?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522167692703716800225566406%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=167692703716800225566406&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduend~default-2-80795421-null-null.142^v73^control_1,201^v4^add_ask,239^v2^insert_chatgpt&utm_term=TRNG%20verilog&spm=1018.2226.3001.4187) CSDN
## Pseudo Random Number Generator
待更新。
## 針對成績變動後經過討論後的結果
對專案的缺陷部分進行 trace
Sign in with Wallet
Connect another wallet