contributed by < Wufangni
>
q_new
allocate 的翻譯是「配置」,以區格 dispatch (分發/分配)
已更改
先建立指向 list_head
結構的 head 指標,並使用 malloc
配置一個記憶體空間,最後回傳經由 INIT_LIST_HEAD
初始化後的 head 指標。
段落中的程式碼標注,使用 1 個 backtick,而非 3 個。
已更改
避免過多的中英文混用,已有明確翻譯詞彙者,例如「鏈結串列」(linked list) 和「佇列」(queue),就使用該中文詞彙,英文則留給變數名稱、人名,或者缺乏通用翻譯詞彙的場景。
q_free
利用 list_for_each_entry_safe
逐一走訪每個節點,並利用 q_release_element
釋放該節點的記憶體空間,最後釋放指向佇列第一個元素的 head 指標。
無論標題和內文中,中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
已更改
q_insert_head
段落中的程式碼標注,使用 1 個 backtick,而非 3 個。
已更改
利用 malloc
配置記憶體空間給新增節點使用,並將欲新增的字元參數指定給新增節點的 value ,再使用 list_add
新增節點到 list 的前端。
q_insert_tail
段落中的程式碼標注,使用 1 個 backtick,而非 3 個。
已更改
與 q_insert_head
大致相同,差別在於 list_add
部份改為使用list_add_tail
。
q_remove_head
利用 head->next
建立欲刪除的 remove_h_list
,先儲存 remove_h_list
的值到 sp
字元中,再對 head->next
所指節點做 list_del
。
段落中的程式碼標注,使用 1 個 backtick,而非 3 個。
已更改
q_remove_tail
與 q_remove_head
大致相同,差別在於 head->next
部份改為 head->prev
。
段落中的程式碼標注,使用 1 個 backtick,而非 3 個。
已更改
實作程式碼在 commit_ad185d6。
q_size
新增 node_count
變數計數每個節點數量再做回傳。
實作程式碼在 commit_ad4ada0。
q_delete_mid
使用 q_size
抓取 list 總節點數,新增 *cur
指標,並用 for 迴圈到總節點數的一半逐一往下跳到中間節點。
利用 *cur
建立removed_element
,使用 list_del
斷開 *cur
在 list 中的連結,最後用 free
釋放 removed_element
。
實作程式碼在 commit_3bb6704。
q_delete_dup
新增 *ori
和 *cur
兩個指標,*ori
從第一個節點開始,*cur
指向 *ori
的下一個節點持續往下跑,直到 *cur
指到 head 才結束迴圈。
設置布林值 flag 判斷是否 *ori
的 value 為重複值(初始值為 false ),若 *ori
和 *cur
節點的 value 不相同,且 flag 判斷先前沒有與 *ori
重複的值被刪除,則 *ori
與 *cur
皆往下一跳節點。
*ori
和 *cur
節點的 value 若相同,則刪除 *cur
所指節點,且 *cur
往下一跳節點,flag 設為 true 表示目前 *ori
所指節點的值有重複。
*ori
和 *cur
節點的 value 不相同且 flag 為 true,刪除 *ori
所指節點,將 *ori
指到與 *cur
相同節點,*cur
往下一節點繼續執行。
實作程式碼在 commit_bcbeaf7。
q_swap
新增 *front
和 *behind
兩指標對兩兩節點做互換。
實作程式碼在 commit_f6ddd47。
q_reverse
使用 list_for_each_safe
對每個節點互換 *prev
和 *next
指標。
實作程式碼在 commit_f6ddd47。
q_reverseK
新增 *h
及 *t
兩指標分別指向每組要替換的頭跟尾節點,將此組的頭與尾節點與原先 list 斷開並使用 q_reverse
做反轉,連回原本的list後將 *cur
指向反傳後在此組節點中最尾端的 *h
,跑 k 次迴圈後停止。
實作程式碼在 commit_ceb5070。
q_sort
先建立一個可回傳 list_head
的 function merge
,用 *pos1
及 *pos2
分別指向兩個 list 的第一個節點,若 *pos1
所指節點值比較小則往下跳一節點再做比較,比較大則刪除 *pos2
所指節點並將 *pos2
往下一節點移動,直到 *pos1
或 *pos2
跳至 head 。若此時 *pos2
指向的list中尚有節點則從第一個節點逐一加到 *pos1
所在 list 最後端。
實作出 merge sort 的遞迴 function merge_divide
,再利用剛創好的 merge
合併兩 list 。
實作程式碼在 commit_aed93df。
q_ascend
/ q_descend
q_ascend
對每個節點皆往下逐一檢查,若此節點往下有比它的值還小的節點存在則刪除此節點,且換下一節點檢查。
q_dscend
與 q_ascend
大致一樣,唯一差別在於 q_dscend
尋找比它大的節點,找到才做刪除。
q_ascend
實作程式碼在 commit_5008760。
q_dscend
實作程式碼在 commit_8e8a14a。
q_merge
對照 Dictionary.com 對 implement 一詞的解釋:
「實作」會是符合上述 "implement" 語意的譯詞,取「起」以「創作」的意思,而「製造」本質上是固定輸入並通常產生固定輸出的行為。
實做 merge_two_list
,作法與上述提到的 merge
相似,差別在於沒有回傳值。
利用 head
指向每個 queue_contex_t
位置串列,將第一個 queue_contex_t
包含的 q
分別與每個 queue_contex_t->q
做 merge。
你如何確認目前的測試程式已涵蓋排序演算法的最差狀況?
lib/list_sort.c
command 的翻譯是「命令」,而非「指令」(instruction),這裡其實不是「命令」,而是編譯器提供的選項 (option),查閱 GCC 手冊。
好的,謝謝老師 。
__attribute__
屬於 GCC 的一種編譯器命令,可用來指示編譯器進行一些高階處理和檢查工作,查閱 GCC 手冊得知 nonnull(2,3,4)
指示第 2 、 3 、 4 不能為空值。
*priv
用來記錄傳入的 cmp function回傳的值,若 cmp(priv, a, b) <= 0
則表示 a < b ,將 a 加入尾端並把 *a
往後移一節,若 *a
為空串列則回 *b
做排序。
段落中的程式碼標注,使用 1 個 backtick,而非 3 個。
已更改
先排除 list 為空值或只有一個節點的情況,再利用 head->prev->next
將 list 轉為單向鏈結串列。
將 list_sort.c 及 list_sort.h 引入 lab0-c ,在 qutest.c 中用 extern
外部宣告 list_sort
函式。
定義 cmp
函式減少後續重複程式碼使用。
新增 listsort 命令。
修改 Makefile。
詳細程式碼在 commit_b8e0681。
shuffle
參考 Fisher–Yates shuffle 實做洗牌演算法,新增 q_shuffle
函式根據下面步驟進行:
q_size
計算鍊結串列長度,並用 for 迴圈從最尾端依序向前做交換。srand(time(NULL))
更改 seed
避免每次找隨機值結果不變。swap
交換兩節點,直到 *last
指向第二節點時停止迴圈。使用 ADD_COMMAND
新增 shuffle
命令。
修改 Makefile。
詳細程式碼在commit_adfc198。
Timing attacks
是一種廣泛的 side-channel attacks
,不同於直接使用密碼學演算上的攻擊手段,他是利用系統執行時間的特性進行破解。舉例來說,在判斷一段密碼是否與原密碼相符時,若是從第一個字母逐一比對遇到不符合再回傳錯誤警告,就可利用回傳時間來判斷前面正確的字符有幾個,進而產生資安疑慮。
有多數研究和偵測執行可變時間的方法被開發出來,例如 ctgrind
、Flow-tracker
或 ctverif
,大多需要對硬體進行建模,但困難點在於較難取得 CPU 細節資訊,此論文提出 dudect
方法可利用統計分析的程式判定是否達成 constant-time ,不用依靠靜態分析可避免硬體上的限制。
在進入統計分析之前會先對每個單獨的測量值進行一些後處理:
scentered product
、mimicking higher-order DPA attack
。透過統計檢定來反駁兩執行時間相等的假設,有幾種檢測方式如 t-test
及 Non-parametric tests
等。
dudect
從每個 trace 中追蹤第17筆測資會無法通過,觀察內部指令為進入 simulation
判斷時造成的問題,回到 qtest.c
中觀察程式做 constant time 判斷使用到的兩函式分別為 is_insert_tail_const()
及 is_insert_head_const()
兩函式存放位置在 fixture.h
檔案中,裡面定義了 DUT_FUNCS
用來測試是否達到 constant time 。
到 fixture.c
中找到關於 constant time 的實作程式,與 dudect 原始程式碼做比對發現缺漏了部份內容。
在 fixture.c
補上 prepare_percentiles
函式,且因 prepare_percentiles
使用了 DUDECT_NUMBER_PERCENTILES
定義及其餘函式所以需要一併補齊。
在 doit
函式中新增剛補上的 prepare_percentiles
,且修改有使用到 DUDECT_NUMBER_PERCENTILES
定義的 update_statistics
參數。
再使用 make test
測試所有 trace ,可發現所有測試項目都可通過。
詳細程式碼在 commit_50da0ff。