# 2020q3 Homework1 (lab0) contributed by <`sammer1107`> ###### tags: `進階電腦系統理論與實作` ## 開發環境 ```shell $ uname -a Linux Aspire-V5-591G 4.15.0-117-generic #118~16.04.1-Ubuntu SMP Sat Sep 5 23:35:06 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux $ gcc --version gcc (Ubuntu 5.4.0-6ubuntu1~16.04.12) 5.4.0 20160609 ``` # 9/12 ## 實作 O(1) q_size ```c= typedef struct { list_ele_t *head; /* Linked list of elements */ size_t size; } queue_t; ``` ```c= int q_size(queue_t *q) { if (q == NULL) { return 0; } else { return q->size; } } ``` 首先和牛刀小試的內容一樣，我藉由在 `queue_t` 中新增一 `size` 變數，來達到常數時間得到 queue 的大小。但同時要確保在刪除、新增 queue 節點時，要記得正確紀錄 `size` 變化。 ## 修正 q_new ```c= queue_t *q_new() { queue_t *q = malloc(sizeof(queue_t)); if (q) { q->head = NULL; q->size = 0; } return q; } ``` 判斷 `q` 非 `NULL` 之後我們才能初始化 queue 並回傳記憶體位置，若為 `NULL` 則按照規則要求回傳 `NULL`。 ## 實作 q_free ```c= void q_free(queue_t *q) { if (!q) return; while (q->head) { list_ele_t *next; next = q->head->next; free(q->head->value); free(q->head); q->head = next; } free(q); } ``` 此函式作用就是首先走訪整個 list 並釋放每個節點的字串以及節點本身。最後才釋放 queue 的 struct。 ::: warning :warning: 這時我還沒實作 insert function 中 copy 字串的功能，所以這裡釋放的字串事實上不是歸 queue 管的，所以要儘快完成 copy 的功能。 ::: ## 實作 q_insert_head ```c= bool q_insert_head(queue_t *q, char *s) { list_ele_t *newh; char *string; size_t str_len = strlen(s) + 1; // include null terminator if (q == NULL) { return false; } newh = malloc(sizeof(list_ele_t)); string = malloc(sizeof(char) * str_len); if (newh == NULL || string == NULL) { free(newh); free(string); return false; } strncpy(string, s, str_len); newh->value = string; newh->next = q->head; q->head = newh; q->size += 1; return true; } ``` + 這裡首先要檢查 q 是否為 `NULL`，若是則按照規則回傳 false。 + 在來要取得需要的記憶體包含節點本身與字串，而 12~14 行之所以可以一起判斷並一起釋放是根據[文件](https://en.cppreference.com/w/c/memory/free)所說，就算指標是 `NULL` 也可以傳入 `free` + 得到記憶體後只需 copy 字串、將節點插在頭並修正 queue 大小即可。 ## 實作 q_insert_tail 要達成常數時間在尾巴插入，我們就需要一個指標一直紀錄著尾巴的位置。因此要修改 `queue_t`: ```c= typedef struct { list_ele_t *head; /* Linked list of elements */ list_ele_t *tail; size_t size; } queue_t; ``` 而 `q_insert_tail` 的內容就與 `q_insert_head` 大致相同。下面的 3~18 行都在做一樣的事。 值得注意的事這裡要處理當 list 為空的情況，當 list 為空，頭跟尾都會直接指向新節點;若非空，則將新節點接在後面。 ```c= bool q_insert_tail(queue_t *q, char *s) { list_ele_t *new; char *string; size_t str_len = strlen(s) + 1; // include null terminator if (q == NULL) { return false; } new = malloc(sizeof(list_ele_t)); string = malloc(sizeof(char) * str_len); if (new == NULL || string == NULL) { free(new); free(string); return false; } strncpy(string, s, str_len); new->value = string; new->next = NULL; if (q->size == 0) { q->head = q->tail = new; } else { q->tail->next = new; q->tail = new; } q->size += 1; return true; } ``` 因為增加了新的 `tail` 指標要維護，原本的 `q_insert_head` 也要做對應的改變，在 21 行後改成: ```c=21 if (q->size == 0) { q->tail = q->head; } q->size += 1; return true; ``` ## 實作 q_remove_head ```c= bool q_remove_head(queue_t *q, char *sp, size_t bufsize) { if (!q || !q->head) return false; list_ele_t *removed = q->head; snprintf(sp, bufsize, "%s", removed->value); if (q->size == 1) { q->tail = q->head = NULL; } else { q->head = q->head->next; } list_element_free(removed); q->size -= 1; return true; } ``` ```c= void list_element_free(list_ele_t *ele) { free(ele->value); free(ele); } ``` + 3~4: 若 `q` 為 NULL 或 list 為空則回傳 false + 6~8: 取得要移除的元素並把字傳複製回 buffer + 10~14: 1. 若 list 剩一個元素，則同時要更動 head 與 tail，因為他們目前都指到此元素 2. 若有兩個或更多，則只需要更動頭即可 + 16: 這裡我發現 remove 與 free 的函式都需要釋放節點，所以我把他寫成一個函式，方便日後擴充 # 9/14 ## 實作 q_reverse ```c= void q_reverse(queue_t *q) { list_ele_t *cursor = NULL; q->tail = q->head; while (q->head) { list_ele_t *tmp = q->head->next; q->head->next = cursor; cursor = q->head; q->head = tmp; } q->head = cursor; } ``` 這裡使用和 quiz1 中一樣的實作 ## 實作 q_sort ```c= void q_sort(queue_t *q) { if (!q) return; q->head = merge_sort_list(q->head); // update tail q->tail = q->head; while (q->tail->next) { q->tail = q->tail->next; } } list_ele_t *merge_sort_list(list_ele_t *head) { // NULL or single node if (!head || !head->next) { return head; } // split list list_ele_t *first = head, *second = head; while (second->next && second->next->next) { second = second->next->next; first = first->next; } second = first->next; first->next = NULL; first = merge_sort_list(head); second = merge_sort_list(second); return merge_sorted(first, second); } list_ele_t *merge_sorted(list_ele_t *head1, list_ele_t *head2) { list_ele_t *new_head; list_ele_t **indirect=&new_head; while (head1 && head2) { if (strcmp(head1->value, head2->value) < 0) { *indirect = head1; head1 = head1->next; } else { *indirect = head2; head2 = head2->next; } indirect = &(*indirect)->next; } if (head1) { *indirect = head1; } else { *indirect = head2; } return new_head; } ``` ### q_sort 函式 + 此函式只檢查 `q` 是否為 `NULL`，至於 list 可能為空或元素只有一個的情況則會交由 `merge_sort_list()` 處理 + 值得注意的是，`merge_sort_list` 只會回傳新的頭，因此要在 8~10 行重新去找找新的尾巴。 ### merge_sort_list 函式 + 先檢查是否為空或是單個元素，若是，則已經排序好，直接回傳。 + 若不是: + 22~28: 這裡的作用在於把 list 對分成兩半。我們使用一個一次走一格的指標 `first` 與令一個一次走兩格的指標 `second`。當 `second` 走到底時，`first` 差不多走到中間，因此第2段的開頭設定在 `second` 的下一節點，而第1段的開頭則是原本的 `head`。 + 30~31: 對第1段與第2段繼續做遞迴呼叫，持續分割並排序 + 33: 合併兩已排序的 list 並回傳新的頭 ### merge_sorted 函式 + 38~39: 這裡我先創造了一個指標 `new_head` 用來指向新的頭，以及指標的指標 `indirect`。藉由使用指標的指標的技巧，可以不必為第一個節點寫專屬的 code。 + 41~49: 比較兩個list的節點，小的就拉過來接到新的 list 最後面。 + 52~55: 當有一個 list 先走完時，我們把剩下的那條直接接過來。 + 58: 最後回傳新的頭位置 ## 完成實作後第一次完整的測試 這次測試我只拿了 76 分，我發現原來是少處理了很多例外狀況: + ### Test operations on NULL queue + 手動執行對應的測試: `./qtest -f traces/trace-07-robust.cmd` + 發現原來是 reverse 忘記檢查 `q` 是否為 `NULL` + 加上 ```c if (!q) return; ``` 在 reverse 開頭即可 + ### Test operations on empty queue + 手動執行對應的測試: `./qtest -f traces/trace-08-robust.cmd` + 發現是原先的 sort 並沒有很好的處理 empty queue 會在第 9 行 dereference 了 null pointer ```c=7 // update tail q->tail = q->head; // NULL here while (q->tail->next) { q->tail = q->tail->next; } ``` + 所以 `q_sort` 的 3~4 應該改成: ```c=3 if (!q || !q->head) return; ``` 來包含為空的情況 + 如此在 `merge_sort_list()` 中也不需要檢查是否為 `NULL` 了，因為我很確定目前切割的方式不會切出 `NULL` ```c=16 // single node if (!head->next) { return head; } ``` + ### Test of malloc failure on insert_head & malloc failure on insert_tail + 我發現原本的程式碼應該是會正確的回傳 `false` 的，但由於我把創建新節點的程式碼變成一個函式了，再這之後我反而忘記在函式回傳後檢查回傳值，造成 test fail。 + 修改後的程式碼長這樣(insert tail 同理): ```c list_ele_t *list_element_new(char *s) { size_t len = strlen(s) + 1; // include null terminator list_ele_t *new = malloc(sizeof(list_ele_t)); if (new == NULL) { return NULL; } new->value = malloc(sizeof(char) * len); if (new->value == NULL) { free(new); return NULL; } new->next = NULL; strncpy(new->value, s, len); return new; } bool q_insert_head(queue_t *q, char *s) { list_ele_t *newh; if (q == NULL) { return false; } newh = list_element_new(s); if (!newh) return false; newh->next = q->head; q->head = newh; if (q->size == 0) { q->tail = q->head; } q->size += 1; return true; } ``` ### 修改完以上就成功得到 :100: 分了。 # 9/15 ## 修正記憶體錯誤 + 當我開啟 AddressSanitizer 後發現最後一個 case 會無法通過: ```shell $ make SANITIZER=1 $ ./qtest -f traces/trace-17-complexity.cmd cmd> # Test if q_insert_tail and q_size is constant time complexity cmd> option simulation 1 ================================================================= ==8662==ERROR: AddressSanitizer: global-buffer-overflow on address 0x000000614540 at pc 0x000000406304 bp 0x7fffee21b590 sp 0x7fffee21b580 READ of size 4 at 0x000000614540 thread T0 #0 0x406303 in do_option_cmd /home/sammer/guts/hw1_lab0/console.c:368 #1 0x405007 in interpret_cmda /home/sammer/guts/hw1_lab0/console.c:220 #2 0x405a2e in interpret_cmd /home/sammer/guts/hw1_lab0/console.c:243 #3 0x406563 in cmd_select /home/sammer/guts/hw1_lab0/console.c:569 #4 0x40697d in run_console /home/sammer/guts/hw1_lab0/console.c:628 #5 0x403eb2 in main /home/sammer/guts/hw1_lab0/qtest.c:772 #6 0x7f6195a3483f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x2083f) #7 0x401af8 in _start (/home/sammer/guts/hw1_lab0/qtest+0x401af8) 0x000000614541 is located 0 bytes to the right of global variable 'simulation' defined in 'console.c:20:6' (0x614540) of size 1 'simulation' is ascii string '' SUMMARY: AddressSanitizer: global-buffer-overflow /home/sammer/guts/hw1_lab0/console.c:368 do_option_cmd Shadow bytes around the buggy address: 0x0000800ba850: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0x0000800ba860: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0x0000800ba870: 00 00 00 00 00 00 00 00 00 00 00 00 f9 f9 f9 f9 0x0000800ba880: 00 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9 0x0000800ba890: 00 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9 =>0x0000800ba8a0: 00 f9 f9 f9 f9 f9 f9 f9[01]f9 f9 f9 f9 f9 f9 f9 0x0000800ba8b0: 01 f9 f9 f9 f9 f9 f9 f9 04 f9 f9 f9 f9 f9 f9 f9 0x0000800ba8c0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0x0000800ba8d0: 00 00 00 00 00 00 00 00 00 f9 f9 f9 f9 f9 f9 f9 0x0000800ba8e0: 01 f9 f9 f9 f9 f9 f9 f9 01 f9 f9 f9 f9 f9 f9 f9 0x0000800ba8f0: 04 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9 Shadow byte legend (one shadow byte represents 8 application bytes): Addressable: 00 Partially addressable: 01 02 03 04 05 06 07 Heap left redzone: fa Heap right redzone: fb Freed heap region: fd Stack left redzone: f1 Stack mid redzone: f2 Stack right redzone: f3 Stack partial redzone: f4 Stack after return: f5 Stack use after scope: f8 Global redzone: f9 Global init order: f6 Poisoned by user: f7 Container overflow: fc Array cookie: ac Intra object redzone: bb ASan internal: fe ==8662==ABORTING ``` + 追查到對應的程式碼位置 `do_option_cmd in console.c:368`，發現應該是在存取 valp 的時候出現了問題。 ```c=366 while (!found && plist) { if (strcmp(plist->name, name) == 0) { int oldval = *plist->valp; *plist->valp = value; if (plist->setter) plist->setter(oldval); found = true; } else plist = plist->next; } ``` + 由於出錯的指令是 `option simulation 1`，所以我追查到產生 `param_ele` 的定義: ``` typedef struct PELE param_ele, *param_ptr; struct PELE { char *name; int *valp; char *documentation; /* Function that gets called whenever parameter changes */ setter_function setter; param_ptr next; }; ``` 發現 valp 應該是要是一個指向 `int` 的指標，但在 `console.c:102` 的地方我們把一個 bool 的位置轉型成了 `int*` 硬傳進去。 ```c=20 bool simulation = false; ``` ```c=102 add_param("simulation", (int *) &simulation, "Start/Stop simulation mode",NULL); ``` + 在我的編譯器上 `sizeof(bool)` 的結果為 1，因此當我們 dereference `valp`，會讀取出界，因為 `sizeof(int)` 為 4。 + 同理在 echo 的選項設定也有一樣的問題。 ```c=107 add_param("echo", (int *) &echo, "Do/don't echo commands", NULL); ``` + 將 `simulation` 與 `echo` 都改成 int 型態就解決上述問題了。 ## Massif 視覺化 我直接使用 test case 17 來觀察記憶體使用狀況。 **檔案內容:** ``` # Test if q_insert_tail and q_size is constant time complexity option simulation 1 it size option simulation 0 ``` **測試命令:** ```shell $ valgrind --tool=massif ./qtest -f traces/trace-17-complexity.cmd ``` ![](https://i.imgur.com/7aQhlld.jpg) :::warning 大部分的趨勢線是緩和變化的，這是因為預設模式下，要好幾個 snapshot 才會有一個 detailed snapshot，所以大部分的線中間都是因為沒有紀錄的所以是直線。正常來講 test_malloc 跟 total heap 應該要同上同下。 ::: 藉由調高 snapshot 次數到 200 以及 detailed snapshot 頻率到 3，我們可以看到 simulation 更完整的模樣: 不斷的配置大小不一樣的 queue 做測試，導致 heap 空間劇烈變化。 ![](https://i.imgur.com/dJjriYG.jpg) # Dude, is my code constant time? 閱讀 ## 論文的動機 + 非常數時間的演算法容易遭遇 timing attack，會造成安全威脅 + 儘管理論上應該是常數時間的演算法，也可能因為實作方式而變得不是常數時間，因此需要作驗證 + 做驗證並不容易，既有工具往往需要對硬體有一定的假設 + **dudect 單純使用統計方法，可避免因硬體差異造成的麻煩** ## Simulation 實作 從函式 `do_insert_tail()` 與 `do_size()`，我們可以看出 simulation 的起點在函式 `is_insert_tail_const()` 與 `is_size_const()`。 以 `is_size_const()` 為例： ```c=177 bool is_size_const(void) { bool result = false; t = malloc(sizeof(t_ctx)); for (int cnt = 0; cnt < test_tries; ++cnt) { printf("Testing size...(%d/%d)\n\n", cnt, test_tries); init_once(); for (int i = 0; i < enough_measurements / (number_measurements - drop_size * 2) + 1; ++i) result = doit(1); printf("\033[A\033[2K\033[A\033[2K"); if (result == true) break; } free(t); return result; } ``` #### 變數說明 + t_ctx: 這個變數用來紀錄兩個 class 目前的 sample 數、平均值、與平均的差的平方的總合(sum of squares of differences)，之後會用 Welford method 來更新這些值 ```c typedef struct { double mean[2]; // mean of each class double m2[2]; // sum of squared errors double n[2]; // number of sample in each class } t_ctx; ``` #### 程式碼 + (181) 第一個迴圈: 這裡的作用在於假如做完 `enough_measurement` 個測量之後，都測出來非常數時間，就再試一次，直到試了 `test_tries` 次。如果做了 `test_tries` 次都否決 null hypothesis，我們才說他是非常數時間。 + (184) 第二個回圈: 每次進迴圈會做 `number_measurements - drop_size * 2` 次測量(在 `doit()` 內)，直到做了 **至少** `enough_measurements` 個測量。 ### doit() ```c=120 static bool doit(int mode) { int64_t *before_ticks = calloc(number_measurements + 1, sizeof(int64_t)); int64_t *after_ticks = calloc(number_measurements + 1, sizeof(int64_t)); int64_t *exec_times = calloc(number_measurements, sizeof(int64_t)); uint8_t *classes = calloc(number_measurements, sizeof(uint8_t)); uint8_t *input_data = calloc(number_measurements * chunk_size, sizeof(uint8_t)); if (!before_ticks || !after_ticks || !exec_times || !classes || !input_data) { die(); } prepare_inputs(input_data, classes); measure(before_ticks, after_ticks, input_data, mode); differentiate(exec_times, before_ticks, after_ticks); update_statistics(exec_times, classes); bool ret = report(); free(before_ticks); free(after_ticks); free(exec_times); free(classes); free(input_data); return ret; } ``` #### 變數說明 + `before_ticks`: 用來紀錄每一個 measure 前的 cycle count + `after_ticks`: 用來紀錄每一個 measure 後的 cycle count :::danger :warning: 這裡 `before_ticks` 與 `after_ticks` 皆要了 `number_measurements + 1` 的空間，這應該是**錯的**。由於我們已經把開始與結束時間分開紀錄，就不需要多一個空間。 :eye: 觀察原作者的 dudect 專案，他之所以需要 `+1` ，是因為他只紀錄每一個 measurement 開始的時間，並用下一次開始的時間當作上一次結束的時間，因此才需要多一個來紀錄最後一次結束的時間。 ::: + `exec_times`: 藉由 `before_ticks` 和 `after_ticks` 可以算出執行時間 + `classes`: 用來紀錄每一個 measurement 是屬於哪一個 class ，由於要確保時間等外在因素的干擾，所以才要隨機的混合兩種 class 的測量。 + `input_data`: 用來裝隨機產生的 bytes，這些隨機資料會決定之後測試 random class 時，要先在頭插入多少節點，才測試 `insert_tail` 和 `size`。 ### prepare_input() ```c=39 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; } } ``` #### 程式碼 + 41行: 這裡我們總共產生了 `number_measurements * chunk_size` 個 random byte 。其中 chunk size 為 16 (byte)，但我們之後在 45 行及 measure 中用到的時候是用 2 byte 而已： + measure() ```c= dut_insert_head( get_random_string(), *(uint16_t *) (input_data + i * chunk_size) % 10000); ``` :::danger :warning: 意思就是我們每產生 16 個 byte，實際用到的只有 2 byte (uint16_t 為 16 bit)。**我想 chunk_size 應該設成 2 即可**，除非是隨機上的考量？我直覺上是不需要有額外的 byte 的 ::: + 42~46: 這裡我們才逐一個決定每一個 measurement 的 class，如果是 fixed-class (=0) ，就在把對應的 chunk 設成 0，到時候測試時就不會在頭插入任何節點。 + 48~52: 這裡則是產生 number_measurement 個隨機字串長度的部份，每個字串長度 7 加上一個 null terminator。 :::warning 這裡使用的巨集 NR_MEASURE 與 `number_measurements` 是同值，但為了讓程式碼更一致，也許應該用 `number_measurements` 就好？ ::: ### measure() ```c=55 void measure(int64_t *before_ticks, int64_t *after_ticks, uint8_t *input_data, int mode) { assert(mode == test_insert_tail || mode == test_size); if (mode == test_insert_tail) { for (size_t i = drop_size; i < number_measurements - drop_size; i++) { char *s = get_random_string(); dut_new(); dut_insert_head( get_random_string(), *(uint16_t *) (input_data + i * chunk_size) % 10000); before_ticks[i] = cpucycles(); dut_insert_tail(s, 1); after_ticks[i] = cpucycles(); dut_free(); } } else { for (size_t i = drop_size; i < number_measurements - drop_size; i++) { dut_new(); dut_insert_head( get_random_string(), *(uint16_t *) (input_data + i * chunk_size) % 10000); before_ticks[i] = cpucycles(); dut_size(1); after_ticks[i] = cpucycles(); dut_free(); } } } ``` #### 程式碼 + 測試 insert tail (61~72) 原理與下面 size 差不多 + 測試 size (74~83) 這裡總共要做 `number_measurements - drop_size*2` 次的測試，每次的測試步驟如下： 1. 根據前面隨機的 `input_data` ，我們插入隨機個一樣的字串到頭 2. 紀錄目前 cycle 3. 執行要測試的函式 4. 紀錄結束的 cycle :::danger :warning: 這裡可以看到在前面 `drop_size` 個跟後面 `drop_size` 個的 `input_data` 其實都沒用到。 我想 drop 的動作應該是**基於統計的考量？** 但就空間而言應該有更經濟的作法: 不儲存這些 drop 的 `input_data` 以及對應的 `before_ticks`,`after_ticks`,`exec_times`,`classes`。 ::: ### differentiate() ```c=61 static void differentiate(int64_t *exec_times, int64_t *before_ticks, int64_t *after_ticks) { for (size_t i = 0; i < number_measurements; i++) { exec_times[i] = after_ticks[i] - before_ticks[i]; } } ``` 這個函式是計算執行時間，結束時間減開始時間即是執行時間。 :::danger :warning: 這裡我發現，這個步驟其實可以在 measure 中就做完，如此我們只需要一個 exec_times 即可，根本不需要多花費 2 倍的空間 (before_ticks, after_ticks) 來存放數字。 ::: ### update_statistics() ```c=70 static void update_statistics(int64_t *exec_times, uint8_t *classes) { for (size_t i = 0; i < number_measurements; i++) { int64_t difference = exec_times[i]; /* Cpu cycle counter overflowed or dropped measurement */ if (difference <= 0) { continue; } /* do a t-test on the execution time */ t_push(t, difference, classes[i]); } } ``` 這個函式把所有有效的測量(去除 dropped 與剛好遇到 counter overflow的情況)，都傳入 t_push： ```c=19 void t_push(t_ctx *ctx, double x, uint8_t class) { assert(class == 0 || class == 1); ctx->n[class]++; /* Welford method for computing online variance * in a numerically stable way. */ double delta = x - ctx->mean[class]; ctx->mean[class] = ctx->mean[class] + delta / ctx->n[class]; ctx->m2[class] = ctx->m2[class] + delta * (x - ctx->mean[class]); } ``` t_push 會使用 Welford method，來計算加入新 sample 後對應的平均、與平均的差平方總和與 sample 數量。 ### report() ```c=83 static bool report(void) { 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("\033[A\033[2K"); printf("meas: %7.2lf M, ", (number_traces_max_t / 1e6)); if (number_traces_max_t < enough_measurements) { printf("not enough measurements (%.0f still to go).\n", enough_measurements - number_traces_max_t); return false; } ``` ```c=108 printf("max t: %+7.2f, max tau: %.2e, (5/tau)^2: %.2e.\n", max_t, max_tau, (double) (5 * 5) / (double) (max_tau * max_tau)); if (max_t > t_threshold_bananas) { return false; } else if (max_t > t_threshold_moderate) { return false; } else { /* max_t < t_threshold_moderate */ return true; } } ``` #### 程式碼 + 85: 這裡跟據公式計算 t value 的絕對值，會取絕對值是因為我們做的是 two-tailed test。 $$ t = \frac{\bar{X_0} - \bar{X_1}}{\sqrt{\frac{s^2_1}{N_1} + \frac{s^2_2}{N_2}}} $$ + 111 與 113 的作用在於檢查 t 是否大於一定值。當 t value 絕對值過大，說明 fixed 與 random 兩個 class 的 mean 有很大的可能並不相同，否決了 null hypothesis (null 為兩個 distribution 一樣) + t_threshold_bananas: 非常誇張的標準，如果 t 到了這麼大，非常確定是非常數時間。 + t_threshold_moderate: 一個比較合理的標準 + 若 115 成立則代表無法否決 null hypothesis，t 過小，代表兩個平均值的差異可能只是隨機的。 ### 結尾 我們已經走過了整個流程，回到 `is_size_const`： ```c=177 bool is_size_const(void) { bool result = false; t = malloc(sizeof(t_ctx)); for (int cnt = 0; cnt < test_tries; ++cnt) { printf("Testing size...(%d/%d)\n\n", cnt, test_tries); init_once(); for (int i = 0; i < enough_measurements / (number_measurements - drop_size * 2) + 1; ++i) result = doit(1); printf("\033[A\033[2K\033[A\033[2K"); if (result == true) break; } free(t); return result; } ``` + 若做完 `number_measurements` 後，若 `doit` 回傳 `true`，則代表這次檢驗出來 null hypothesis 成立，應該為常數時間。回傳到 `do_size` 後程式印出 Probably constant time。 + 若做完後 `doit` 回傳 `false`，則代表這次檢驗出來 null hypothesis 被否決，應該為非常數時間。但我們總共有 `test_tries` 次機會，如果都失敗程式才會回傳並印出 Probably not constant time ## Simulation 實作缺陷 作者在論文中提到了要做 post-processing，但程式碼中似乎沒處理到這部份。
Last changed by  
 
Yu Jen Lin
358

Read more

2020q3 Homework1 (quiz1)

contributed by < sammer1107 > [TOC] AA1 & AA2 void add_entry(node_t **head, int new_value) { node_t **indirect = head; node_t *new_node = malloc(sizeof(node_t));

12/15/2020
2020q3 Homework3 (quiz3)

contributed by < sammer1107 > 測驗題 測驗 1 int asr_i(signed int m, unsigned int n) { const int logical = (((int) -1) OP1) > 0; unsigned int fixu = -(logical & (OP2)); int fix = *(int *) &fixu;

11/18/2020
2020q3 Homework6 (kcalc)

contributed by < sammer1107 > 作業說明 完善測試機制 原本的 test case 跑完也不確定結果到底正不正確，所以我決定先從改善 test 機制開始。 NAN="NAN_INT" INF="INF_INT"

11/11/2020
2020q3 Homework5 (quiz5)

contributed by < sammer1107 > ==測驗題目== 測驗 1 #include <stdio.h> #include <stdlib.h> double divop(double orig, int slots) { if (slots == 1 || orig == 0)

11/10/2020
Read more from Yu Jen Lin
Published on HackMD