HackMD
2020q1 Homework 1
contributed by < timmycc >
Fork and Clone
點選文內連結到 lab0-c 的 Repository 後，fork 到自己的 github，再 clone 到電腦上來進行修改。
Implement the function
文中提到了 q_insert_tail 和 q_size 需要將原本 O(n) 時間複雜度的實作改寫為 O(1) 時間複雜度
原本這兩種操作勢必都要從頭開始 traverse，唯一達到常數時間的方法是在 typedef 加入 tail 跟 size 兩種屬性。(仔細看 code 中的 comment 其實有提示)
修改後 typedef 的部分即為
typedef struct {
list_ele_t *head; /* Linked list of elements */
list_ele_t *tail; /* a pointer point to tail */
int size;
} queue_t;
這邊要銘記在心，再來其他操作當然也要做出相對應的調整。
回到 queue.c，第一個需要修改的函式為 new，comment 中提到了如果 malloc 回傳了 null 的話 new 也回傳 null，因此在底下新增一個判斷式，來檢查我的 q 是不是有正確的分配到東西並做出要求的回傳
queue_t *q = malloc(sizeof(queue_t));
if (!q) {
return NULL;
}
再來看到底下還有 q->head = NULL 總覺得怪怪的，別忘了前面我們已經修改了原本的 typedef，所以應該要改成
q->head = NULL;
q->tail = NULL;
q->size = 0;
return q;
q_free
提示了要你做出釋放這個 list 的方法，因此來一個一個稽查，只要底下還有被指向的人就 free 他，在之後的插入等動作中，list->value 也會 malloc，所以這邊記得也要 free，以及剛開始就要檢查輸入的 queue 是否有東西，避免之後對 NULL 進行操作給你噴紅字，在後面其他相關的操作也要記得。
void q_free(queue_t *q)
{
if (!q) {
return;
}
list_ele_t *ptr = q->head;
while (ptr) {
list_ele_t *self;
self = ptr;
ptr = ptr->next;
if (self->value) {
free(self->value);
}
free(self);
}
free(q);
}
q_insert_head
要求 malloc 後把 argument 內的 char 放進去，最後回傳一個 boolean 來表示成功與否。剛開始要 malloc 一個 list/list->value 所需要的空間，跟前面一樣記得要檢查 malloc 回傳是否為 null，記得在失敗後把剛剛拿的空間還回去，確定都完成的畫最後幫 size+1。
bool q_insert_head(queue_t *q, char *s)
{
list_ele_t *newh;
if (!q) {
return false;
}
newh = malloc(sizeof(list_ele_t));
if (!newh) {
return false;
}
newh->value = malloc((strlen(s) + 1) * sizeof(char));
if (!newh->value) {
free(newh);
return false;
}
memcpy(newh->value, s, (strlen(s) + 1));
newh->next = q->head;
q->head = newh;
if (!q->tail) {
q->tail = q->head;
}
q->size++;
return true;
}
q_insert_tail
類似於 q_insert_head，稍作修改即可
bool q_insert_tail(queue_t *q, char *s)
{
if (!q) {
return false;
}
list_ele_t *newt;
newt = malloc(sizeof(list_ele_t));
if (!newt) {
return false;
}
newt->value = malloc((strlen(s) + 1) * sizeof(char));
if (!newt->value) {
free(newt);
return false;
}
memcpy(newt->value, s, (strlen(s) + 1));
if (!q->tail) {
q->head = newt;
q->tail = newt;
} else {
q->tail->next = newt;
q->tail = newt;
}
newt->next = NULL;
q->size++;
return true;
}
remove_head
如果 sp 不為 null 則把被移除的字串複製進去，一樣要修改相關的屬性
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (!q || !q->head)
return false;
list_ele_t *rmhead = q->head;
if (bufsize > 0 && sp) {
strncpy(sp, q->head->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
q->head = rmhead->next;
if (rmhead == q->tail) {
q->tail = NULL;
}
free(rmhead->value);
free(rmhead);
q->size--;
return true;
}
–
size
終於來的最簡單的 XD
int q_size(queue_t *q)
{
if (!q) {
return 0;
}
return q->size;
}
reverse
則要求過程中不得增減空間，若 q 沒有東西則不動作，於是我們遞迴的往下走，最後補上while 中無法處理的末項，把這目的寫出來就完成了，不過怕考慮得不夠周到，還是先用筆畫個範例後才實際的寫下過程
void q_reverse(queue_t *q)
{
if (!q || q->size < 2) {
return;
}
list_ele_t *pre, *cur, *nex;
pre = NULL;
cur = q->head;
nex = cur->next;
q->tail = cur;
while (nex) {
cur->next = pre;
pre = cur;
cur = nex;
nex = cur->next;
}
cur->next = pre;
q->head = cur;
return;
}
sort
更新: 礙於 make test 中要求的效能問題，最後還是改成了 merge sort，寫完記得把新增的merge補充在 queue.h。
一樣開頭先對 input 做檢查，再來將原有的 list 分成 left 跟 right，然後計算他們個別的 size 來取得正確頭尾，並且以 divide and conquer 的精神完成這項 sort。
void q_sort(queue_t *q)
{
if (!q || q->size < 2)
return;
queue_t left, right;
left.size = (q->size >> 1) + (q->size & 1);
right.size = q->size >> 1;
list_ele_t *cur = left.head = q->head;
right.tail = q->tail;
for (size_t i = 0; i < left.size - 1; i++)
cur = cur->next;
left.tail = cur;
right.head = cur->next;
left.tail->next = NULL;
q->head = q->tail = NULL;
q_sort(&left);
q_sort(&right);
q_merge(&left, &right, q);
}
void q_merge(queue_t *left, queue_t *right, queue_t *q)
{
q->size = left->size + right->size;
list_ele_t *l = left->head, *r = right->head;
list_ele_t *tem = NULL;
if (strnatcmp(left->head->value, right->head->value) < 0) {
q->head = left->head;
} else {
q->head = right->head;
}
q->tail = q->head;
for (size_t i = 0; i < q->size; i++) {
if (!r || (l && strnatcmp(l->value, r->value) < 0)) {
tem = l;
l = l->next;
} else {
tem = r;
r = r->next;
}
q->tail->next = tem;
q->tail = tem;
}
tem->next = NULL;
}
3/17: 達到 $ make test 中的要求，我還記得第一次做完後出來一個 24/100，之後發現原來是要做到正確才有分數，所以…，總之有幾個問題，記得 malloc 過的部分，並且確實在 free 或刪除等相關的操作 free 掉，以及開頭就要對輸入進行檢查，避免後續對一個 NULL 上下其手直接跳紅字，造成 segmentation fault (invalid page fault)，除了輸入有可能是 NULL，自己寫的也有對 NULL pointer 操作的，多次修改後才總算處理完，實在沒什麼效率 (應該在某邊遇到的問題) 雖然我想離其他人去進行效能分析或其他改進還有段距離，但在交出作業的 18 天後終於有空把 $ make test 弄到 100/100，希望能趕快趕上進度。
介紹 dudect
實驗
文中說明如何使用 dudect 來分析一段程式碼的時間複雜度是否在常數時間內。
首先重複的測量加密函數對兩種不同 class 的 input (fix-vs-random)的執行時間，內文還有提到了 Timing attack 這東西(延伸: 為什麼密碼的檢查必須對任何輸入都要經過同樣的時間? 解讀計算機編碼)，之後以 leakage detection test (from the area of hardware side-channels) 來檢驗，fix 代表第一種資料輸入為固定的值，random 代表第二種是隨機的值，clock cycle 的部分有些 CPU 會提供 counter，以及之後提到 environment 的限制來降低對測量結果的影響。
再來 apply post-processing，在執行前就預先處理，避免過大的 input 被 OS 或其他事件干擾造成測量上的誤差，實驗後的測量會經過處理去掉超出範圍的值來取得較精準的結果，之後使用 Welch’s t-test with Welford’s variance computation method 來 disprove null hypothesis “the two timing distributions are equal”。。
Memory comparison
第一個 case 實驗 16-byte memory comparison function based on memcmp，對“secret” fixed string s 來進行比較，這邊 evaluator 是知道 s 是什麼的，先前提到的fixed class 輸入為 s，random class 的輸入則為 uniformly distributed random 16-byte strings，兩者輸入後進行比較並且檢測他的執行時間，Fig. 1為兩種 class 在花費 clock cycle 上的 cdf，由圖中兩種 class 執行時間的差異可知存在 Timing leakage，假設 t = 4.5時，所有測量的結果都使得前面的 test fail。
之後作者對實驗做出一些改變(black box-testing)，evaluator 改為不知道 s，所以 fixed class 輸入改為0，但結果依然是 reject null hypothesis。
第二個 case 改為由 compared by logical operation，即任意輸入都會經過相同的過程，不會因為輸入的差異而提早或延遲，從 Fig. 5/6 可以看出跟前面明顯的差異，兩種 class 幾乎呈現一樣的分布。
其他
測試 T-tables AES implementation，Fixed class 為隨機選取 input plaintext 後固定，Fig. 7/8顯示同樣有 timing attack 的風險。然而 imeplemented by bitslicing 則得到接近相同的分布(Fig. 9/10)，implemented by vector permutation 同樣沒有 leakage 的風險。Curve25519 on an ARM7TDMI 的實驗中 input fixed class 為全零，random class 為 uniformly distributed random input points，結果是明顯的 leakage。
Apply on lab0-c
觀察 qtest 後, 裡頭檢查時間複雜度的 function 在 dudect 的 fixture, 在 lab0-c 中 dudect 先計
算
資料則由 prepare_inputs 產生
void prepare_inputs(uint8_t *input_data, uint8_t *classes)
{
randombytes(input_data, number_measurements * chunk_size);
for (size_t i = 0; i < number_measurements; i++) {
classes[i] = randombit();
if (classes[i] == 0)
*(uint16_t *) (input_data + i * chunk_size) = 0x00;
}
for (size_t i = 0; i < NR_MEASURE; ++i) {
/* Generate random string */
randombytes((uint8_t *) random_string[i], 7);
random_string[i][7] = 0;
}
}
亂數產生 input 並隨機加入 random class 或 fixed class, 若是 random class 不動作, 而 fixed class 則是令首兩位 byte 為0, 由論文中的描述可以知道為什麼出來的結果是 probably constant time, 但比較不同的是 lab0-c 中的方法並沒有去除極端值的部份
Valgrind, 利用 massif 來觀察記憶體使用狀況
(待補)
使用 massif 的過程會出現 unknown operation 的錯誤，根據 @ZhuMon 在共筆中提出的解決方案，將我始終沒發現就在 lab0-c 資料夾中的 .valgrindrc 做出同樣的修改
- --leak-check=full
+ --memcheck:leak-check=full
之後即可順利執行
ctimmy@ctimmy-GP62-7REX:~/linux2020/lab0-c$ valgrind --tool=massif --stacks=yes --time-unit=i ./qtest
cmd> new
cmd> new
q = []
cmd> ih RAND 10
cmd> ih RAND 10
q = [qjjgrauz ftsxljw oiqlfdgam pzbfydal qwtmxbv sqoqpnxv vhswgjjoz yvxuxc sucvx uxjzzonhq]
cmd> reverse
cmd> reverse
q = [uxjzzonhq sucvx yvxuxc vhswgjjoz sqoqpnxv qwtmxbv pzbfydal oiqlfdgam ftsxljw qjjgrauz]
cmd> sort
cmd> sort
q = [ftsxljw oiqlfdgam pzbfydal qjjgrauz qwtmxbv sqoqpnxv sucvx uxjzzonhq vhswgjjoz yvxuxc]
cmd> free
cmd> free
q = NULL
cmd> quit
cmd> quit
Freeing queue
結束之後 Valgrind 會在 lab0-c 輸出一個名字為 massif.out.<pid> 的報告，點進去 lab0-c 後就會看到我們要的檔案了，輸入 ms_print massif.out.<pid> 後即可看到相關的圖表，如下(圖的部分格式似乎會有點不一樣)
ctimmy@ctimmy-GP62-7REX:~/linux2020/lab0-c$ ms_print massif.out.4648
--------------------------------------------------------------------------------
Command: ./qtest
Massif arguments: --stacks=yes --time-unit=i
ms_print arguments: massif.out.4648
--------------------------------------------------------------------------------
KB
14.80^ ##:
| # : @ @
| @ # : @ @:
| @ # ::@:::@:::
| @ :# ::@:: @:::
| @:::# ::@:: @:::@
| @: :# ::@:: @:::@
| @: :# ::@:: @:::@
| @: :# ::@:: @:::@
| @: :# ::@:: @:::@
| @: :# ::@:: @:::@
| @ @: :# ::@:: @:::@
| @ @: :# ::@:: @:::@
| @ @: :# ::@:: @:::@
| @ @: :# ::@:: @:::@
| @ @: :# ::@:: @:::@
| @ @: :# ::@:: @:::@
| @:: @: :# ::@:: @:::@:
| @:::: ::@@ @:: : :::: @: :: ::::: :@: :# ::@:: @:::@:
| @::: :::::::::@ :@:@:::::::::: ::@:::::: : ::::@: :# ::@:: @:::@:
0 +----------------------------------------------------------------------->ki
0 286.6
Number of snapshots: 66
Detailed snapshots: [2, 3, 13, 15, 17, 28, 40, 43 (peak), 46, 50, 60]
