# 2019q1 Homework1 (lab0) contributed by < `afcidk` > * [C Programming Lab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf) * [F01: lab0](https://hackmd.io/s/BJA8EgFB4) :::success 後續改進: 1. 參照 [dudect](https://github.com/oreparaz/dudect) 和對應的論文 [dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)，學習其中檢測時間複雜度的機制，對本題要求 $O(1)$ 的實作部分，給予更廣泛的測試; 2. 重新整理下方共筆 (刪去過時資訊)，學習技術文件的撰寫，可參照 [基於 C 語言標準研究與系統程式安全議題](https://hackmd.io/s/S15o_K3cQ) 的風格; :notes: jserv ::: ## 實驗環境 作業系統：Linux elementaryOS 4.16.9-041609-generic gcc 版本：8.1.0 :::info gcc 版本應該升級到 7.2+, 否則後續有些實驗 (如 LTO) 會無效 :notes: jserv ::: ## 作業目標 * 重新熟悉 linked list 以及記憶體管理。 * 了解單元測試的重要性 ## 作業要求 我們需要以 linked list 實作 queue，並且支援 LIFO 和 FIFO。 因為我們是在基礎的程式碼再加上自己實作的函式，因此事先了解整個檔案目錄的結構是很重要的。 ## 專案內的各個檔案解釋 首先，我們觀察一下有哪些檔案，並為他們下上對應的註解 * console：負責處理 qtest 的各種命令 * harness：Overload `malloc` 和 `free`，增加額外的檢查 * qtest：qtest 的主程式 * queue：操作 queue 相關的函式 * report：回報在 harness 中做的檢查狀態 * `driver.py`：一個協助我們進行單元測試的腳本 * `*.cmd`：單元測試的測試檔案，共有 15 個 ## 實作 `queue.h` 裡頭定義了我們需要實作的函式，分別是 * q_new * q_free * q_insert_head * q_insert_tail * q_remove_head * q_size * q_reverse 另外，原本提供的資料結構 ```clike /* Queue structure */ typedef struct { list_ele_t *head; } queue_t; ``` 也許沒辦法提供一個有效率 ( $O(1)$ ) 的方式做出 `q_insert_tail` 以及 `q_size`，因此需要做適當的修改。 ### 為什麼需要 function hooking 在 `harness.h` 裡頭，我們可以發現兩行巨集，由此可得知 `free()` 和 `malloc()` 這兩個函式都被對應到自己實作的 `test_free()` 以及 `test_malloc()` ```clike #define free test_free #define malloc test_malloc ``` 其實整個 `harness.h` 最外層是被一層 macro 包裝起來了 ```clike #ifdef INTERNAL //.... skipped #else #define free test_free #define malloc test_malloc #endif ``` 可以看到當 `INTERNAL` 沒有被定義時，我們的 `free/malloc` 才會被 hook 成 `test_free/test_malloc`。 接下來再找找看哪些檔案有引入 `harness.h`，發現如下3個檔案 * qtest.c ```clike #define INTERNAL 1 #include "harness.h" ``` * queue.c ```clike #include "harness.h" ``` * harness.c ```clike #define INTERNAL 1 #include "harness.h" ``` 由此可知我們實作的時候，使用的 `free/malloc` 都會被 hook 成已經寫好的 `test_free/test_malloc`，這樣做的用意是提供多一層的檢查，讓程式在出錯（e.g. double free）時不會直接 crash 而是印出錯誤訊息。 然而，這樣做也有一些缺點，像是我們沒有辦法使用有呼叫 `malloc` / `free` 的其他標準函式，例如 `strdup()`。 :::warning 可以比照 test_malloc/test_free，去封裝 `strdup` 一類的函式嗎？若可，提交對應的 pull request :notes: jserv ::: :::info pull request: https://github.com/sysprog21/lab0-c/pull/6 ::: ### q_new 這部份會初始化我們的 queue，需要注意判斷 `malloc` 有沒有成功。 ```clike queue_t *q_new() { queue_t *q = malloc(sizeof(queue_t)); if (!q) { return NULL; } q->head = NULL; q->tail = NULL; q->size = 0; return q; } ``` ### q_free 只需要使用到一個指標就可以了[^1]，一直刪掉 head 直到整個 queue 清空。 ```clike void q_free(queue_t *q) { if (!q) return; list_ele_t *ptr = q->head; list_ele_t *prev = NULL; while (ptr) { prev = ptr; ptr = ptr->next; free(prev->value); free(prev); } /* Free queue structure */ free(q); } ``` ### q_insert_head 要記得每次 malloc 過後都要確認是不是有成功，如果沒有成功的化要把先前 malloc 過的東西都 free 回去。 另外因為 queue 的資料結構多了 tail，所以我們需要判斷如果 queue 長度是 1 的化，tail 的值也要改動，雖然這邊是 insert_head。 ```clike bool q_insert_head(queue_t *q, char *s) { list_ele_t *newh; if (!q) { return false; } ++q->size; newh = malloc(sizeof(list_ele_t)); if (!newh) return false; char *value = malloc((strlen(s) + 1) * sizeof(char)); if (!value) { free(newh); return false; } memset(value, 0, strlen(s) + 1); strcpy(value, s); newh->value = value; newh->next = q->head; q->head = newh; if (q->size == 1) q->tail = newh; return true; } ``` ### q_insert_tail ```clike bool q_insert_tail(queue_t *q, char *s) { list_ele_t *newh; if (!q) { return false; } ++q->size; newh = malloc(sizeof(list_ele_t)); if (!newh) return false; char *value = malloc((strlen(s) + 1) * sizeof(char)); if (!value) { free(newh); return false; } memset(value, 0, strlen(s) + 1); strcpy(value, s); newh->value = value; if (q->size == 1) { q->tail = newh; q->head = newh; } q->tail->next = newh; q->tail = newh; q->tail->next = NULL; if (q->size == 1) q->head = newh; return true; } ``` ### q_remove_head 注意到如果要刪除第一個元素，除了 queue 要存在，queue 裏面也要有至少一個元素。 還有另外一個命令 (`rh`) 不需要紀錄刪除的字串，這時候 `bufsize` 是 0，也需要特別判斷。 ```clike bool q_remove_head(queue_t *q, char *sp, size_t bufsize) { if (!q || !q->head) return false; if (bufsize != 0) { if (strlen(q->head->value) > bufsize) { strncpy(sp, q->head->value, bufsize); sp[bufsize - 1] = 0; } else { strcpy(sp, q->head->value); } } list_ele_t *tmp = q->head; q->head = q->head->next; free(tmp->value); free(tmp); --q->size; return true; } ``` ### q_size 為了達到 $O(1)$ 的時間複雜度，所以我直接修改 queue 的結構，增加了 `size`，在每次操作時都會更改到 `size`。 ```clike int q_size(queue_t *q) { if (!q || !q->head) return 0; return q->size; } ``` ### q_reverse ```clike void q_free(queue_t *q) { if (!q) return; list_ele_t *tmp = NULL; while (q->head) { tmp = q->head; q->head = q->head->next; free(tmp->value); free(tmp); } /* Free queue structure */ free(q); } ``` ## 驗證常數時間複雜度 根據 [dudect](https://github.com/oreparaz/dudect) 工具以及提出的對應論文 [Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)，我們得知了一種以實驗而非理論驗證時間複雜度的方法。 他透過 timing attack (精確一點只算是 leakage，因為洩漏的資訊太少不足以完成一項攻擊) 來檢測。 一種 leakage detection 的方式是 fix-vs-random test。這個方式透過餵給程式固定以及隨機的資料，再比較執行時間的差異。 [dudect](https://github.com/oreparaz/dudect) 使用的方法便是這種 fix-vs-random test。在得到執行時間後，利用 t-test 檢查兩種測試資料是否差異。 最後我取 [dudect](https://github.com/oreparaz/dudect) 中計算 t-test 的部份，修改後放到 qtest 中。執行 `qtest -t` 可以測試 `q_insert_tail` 和 `q_size` 是否可能非常數時間複雜度。 > 不過我還沒有把 fix-vs-random test 理解得很透澈，看完之後再來補上 `qtest -t` 相關的程式碼在這個 [commit](https://github.com/afcidk/lab0-c/commit/0dffa11692db3888730c2f62f1349c67b8188af3) push 上去了，不小心逛到這裡的同學可以把他 clone 下來，再把 queue 替換成自己的實作試試看~ 執行後可能會有類似這樣的輸出 ``` Note1: Since we use statictic method to test if the function has constant time complexity, sometimes it requires larger time to show that it REALLY IS POLYNOMINAL time, however, you can tell instinctively that it is not constant time if the calculating process is too slow. :) (normally, the change of "max t" field should be really fast) Note2: You should pass the original time limit (1 sec) first! Testing insert_tail... Press Ctrl-C to enter next mode meas: 0.01 M, max t: +2.35, max tau: 2.50e-02, (5/tau)^2: 4.00e+04. For the moment, maybe constant time. ^C Testing q_size...... press Ctrl-C to leave. meas: 0.09 M, max t: +1.43, max tau: 4.73e-03, (5/tau)^2: 1.12e+06. For the moment, maybe constant time. ``` ## Reference [^1]: [ktvexe 的開發紀錄](https://hackmd.io/s/HJJtkhYBE#q_free)
Last changed by  
 
Pei Hsuan Hung
1758
Published on HackMD