Try   HackMD

2024q1 Homework1 (lab0)

contributed by < Wufangni >

開發環境

$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0

$ lscpu
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         39 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  16
  On-line CPU(s) list:   0-15
Vendor ID:               GenuineIntel
  Model name:            12th Gen Intel(R) Core(TM) i5-12500H
    CPU family:          6
    Model:               154
    Thread(s) per core:  2
    Core(s) per socket:  12
    Socket(s):           1
    Stepping:            3
    CPU max MHz:         4500.0000
    CPU min MHz:         400.0000
    BogoMIPS:            6220.80

針對佇列操作的程式碼實作

q_new

commit_0f1697a

allocate 的翻譯是「配置」,以區格 dispatch (分發/分配)

已更改

先建立指向 list_head 結構的 head 指標,並使用 malloc 配置一個記憶體空間,最後回傳經由 INIT_LIST_HEAD 初始化後的 head 指標。

段落中的程式碼標注,使用 1 個 backtick,而非 3 個。

已更改

避免過多的中英文混用,已有明確翻譯詞彙者,例如「鏈結串列」(linked list) 和「佇列」(queue),就使用該中文詞彙,英文則留給變數名稱、人名,或者缺乏通用翻譯詞彙的場景。

q_free

commit_e34d5f1

利用 list_for_each_entry_safe 逐一走訪每個節點,並利用 q_release_element 釋放該節點的記憶體空間,最後釋放指向佇列第一個元素的 head 指標。

無論標題和內文中,中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)

已更改

q_insert_head

commit_289d41c

段落中的程式碼標注,使用 1 個 backtick,而非 3 個。

已更改

利用 malloc 配置記憶體空間給新增節點使用,並將欲新增的字元參數指定給新增節點的 value ,再使用 list_add 新增節點到 list 的前端。

q_insert_tail

commit_9f62397

段落中的程式碼標注,使用 1 個 backtick,而非 3 個。

已更改

q_insert_head 大致相同,差別在於 list_add 部份改為使用list_add_tail

q_remove_head

commit_ad185d6

利用 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 皆往下一跳節點。

if (strcmp(cur_element->value, ori_element->value) != 0 && 
    flag == false) {
    ori = cur;
    cur = cur->next;
} 

*ori*cur 節點的 value 若相同,則刪除 *cur 所指節點,且 *cur 往下一跳節點,flag 設為 true 表示目前 *ori 所指節點的值有重複。

} else {
    flag = true;
    cur = cur->next;
    element_t *tmp_element = list_entry(cur->prev, element_t, list);
    list_del(&tmp_element->list);
    free(tmp_element->value);
    free(tmp_element);
    if (cur == head) {
        element_t *tmp2_element = list_entry(ori, element_t, list);
        list_del(&tmp2_element->list);
        free(tmp2_element->value);
        free(tmp2_element);
        break;
    }

*ori*cur 節點的 value 不相同且 flag 為 true,刪除 *ori 所指節點,將 *ori 指到與 *cur 相同節點,*cur 往下一節點繼續執行。

} else if (strcmp(cur_element->value, ori_element->value) != 0 &&
           flag == true) {
    element_t *tmp_element = list_entry(ori, element_t, list);
    list_del(&tmp_element->list);
    ori = cur;
    free(tmp_element->value);
    free(tmp_element);
    cur = cur->next;
    flag = false;
}

實作程式碼在 commit_bcbeaf7

q_swap

新增 *front*behind 兩指標對兩兩節點做互換。

while (true) {
    if (front == head || behind == head)
        break;
    (front->prev)->next = behind;
    behind->prev = front->prev;
    (behind->next)->prev = front;
    front->next = behind->next;
    front->prev = behind;
    behind->next = front;
    front = front->next;
    behind = front->next;
}

實作程式碼在 commit_f6ddd47

q_reverse

使用 list_for_each_safe 對每個節點互換 *prev*next 指標。

struct list_head *nex, *s;
list_for_each_safe (nex, s, head) {
    element_t *tmp_element = list_entry(nex->next, element_t, list);
    nex->next = nex->prev;
    nex->prev = &tmp_element->list;
}
struct list_head *tmp_head_next = head->next;
head->next = head->prev;
head->prev = tmp_head_next;

實作程式碼在 commit_f6ddd47

q_reverseK

新增 *h*t 兩指標分別指向每組要替換的頭跟尾節點,將此組的頭與尾節點與原先 list 斷開並使用 q_reverse 做反轉,連回原本的list後將 *cur 指向反傳後在此組節點中最尾端的 *h,跑 k 次迴圈後停止。

struct list_head *h, *t, *cur = head;
for (int i = 0; i < (q_size(head) / k); i++) {
    h = cur->next;
    t = h;
    for (int j = 1; j < k; j++)
        t = t->next;
    cur->next = t->next;
    (t->next)->prev = cur;
    t->next = h;
    h->prev = t;
    q_reverse(h);
    h->next = cur->next;
    (h->next)->prev = h;
    t->prev = cur;
    cur->next = t;
    cur = h;
}

實作程式碼在 commit_ceb5070

q_sort

先建立一個可回傳 list_head 的 function merge,用 *pos1*pos2 分別指向兩個 list 的第一個節點,若 *pos1 所指節點值比較小則往下跳一節點再做比較,比較大則刪除 *pos2 所指節點並將 *pos2 往下一節點移動,直到 *pos1*pos2 跳至 head 。若此時 *pos2 指向的list中尚有節點則從第一個節點逐一加到 *pos1 所在 list 最後端。

struct list_head *merge(struct list_head *head1, struct list_head *head2)
{
    struct list_head *pos1 = head1->next, *pos2 = head2->next, *insert;
    while (pos1 != head1 && pos2 != head2) {
        element_t *ele1 = list_entry(pos1, element_t, list);
        element_t *ele2 = list_entry(pos2, element_t, list);
        if (strcmp(ele1->value, ele2->value) > 0) {
            insert = pos2;
            pos2 = pos2->next;
            list_del(&ele2->list);
            (pos1->prev)->next = insert;
            insert->next = pos1;
            insert->prev = pos1->prev;
            pos1->prev = insert;
        } else {
            pos1 = pos1->next;
        }
    }
    while (pos2 != head2) {
        insert = pos2;
        pos2 = pos2->next;
        list_del(&list_entry(insert, element_t, list)->list);
        list_add_tail(&list_entry(insert, element_t, list)->list, head1);
    }
    return head1;
}

實作出 merge sort 的遞迴 function merge_divide,再利用剛創好的 merge 合併兩 list 。

struct list_head *merge_divide(struct list_head *head)
{
    struct list_head *mid = head->next, *mid_prev, new_head;
    if (q_size(head) <= 1)
        return head;

    for (int i = 0; i < q_size(head) / 2; i++)
        mid = mid->next;
    struct list_head *new_pos = &new_head;
    new_pos->next = mid;
    new_pos->prev = head->prev;
    (head->prev)->next = new_pos;
    mid_prev = mid->prev;
    mid->prev = new_pos;

    head->prev = mid_prev;
    mid_prev->next = head;

    return merge(merge_divide(head), merge_divide(new_pos));
}

實作程式碼在 commit_aed93df

q_ascend / q_descend

q_ascend 對每個節點皆往下逐一檢查,若此節點往下有比它的值還小的節點存在則刪除此節點,且換下一節點檢查。
q_dscendq_ascend 大致一樣,唯一差別在於 q_dscend 尋找比它大的節點,找到才做刪除。

for (int i = 0; i < len; i++) {
    bool delete = false;
    if (cur->next == head)
        break;
    struct list_head *node_ = cur->next;
    element_t *cur_element = list_entry(cur, element_t, list);
    for (int j = i + 1; j < len; j++) {
        element_t *nod_element = list_entry(node_, element_t, list);
        if (strcmp(cur_element->value, nod_element->value) < 0) {
            cur = cur->next;
            list_del(&cur_element->list);
            free(cur_element->value);
            free(cur_element);
            delete = true;
            break;
        }
        node_ = node_->next;
    }
    if (delete == false)
        cur = cur->next;
}

q_ascend 實作程式碼在 commit_5008760
q_dscend 實作程式碼在 commit_8e8a14a

q_merge

commit_aed93df

對照 Dictionary.comimplement 一詞的解釋:

  • to fulfill; perform; carry out:
  • to put into effect according to or by means of a definite plan or procedure.
  • Computers. to realize or instantiate (an element in a program), often under certain conditions as specified by the software involved.
  • to fill out or supplement

「實作」會是符合上述 "implement" 語意的譯詞,取「起」以「創作」的意思,而「製造」本質上是固定輸入並通常產生固定輸出的行為。

資訊科技詞彙翻譯

實做 merge_two_list ,作法與上述提到的 merge 相似,差別在於沒有回傳值。

利用 head 指向每個 queue_contex_t 位置串列,將第一個 queue_contex_t 包含的 q 分別與每個 queue_contex_t->q 做 merge。

int q_merge(struct list_head *head, bool descend)
{
    if (!head || list_empty(head))
        return 0;
    struct list_head *first_q = head->next, *next_q = first_q->next;
    queue_contex_t *first_queue = list_entry(first_q, queue_contex_t, chain);
    if (descend == true)
        q_reverse(first_queue->q);
    while (next_q != head) {
        queue_contex_t *next_queue = list_entry(next_q, queue_contex_t, chain);
        if (descend == true)
            q_reverse(next_queue->q);
        merge_two_list(first_queue->q, next_queue->q);
        next_q = next_q->next;
    }
    return q_size(first_queue->q);
}

你如何確認目前的測試程式已涵蓋排序演算法的最差狀況?


研讀並引入 lib/list_sort.c

command 的翻譯是「命令」,而非「指令」(instruction),這裡其實不是「命令」,而是編譯器提供的選項 (option),查閱 GCC 手冊。

好的,謝謝老師 。

__attribute__ 屬於 GCC 的一種編譯器命令,可用來指示編譯器進行一些高階處理和檢查工作,查閱 GCC 手冊得知 nonnull(2,3,4) 指示第 2 、 3 、 4 不能為空值。

__attribute__((nonnull(2,3,4)))

*priv 用來記錄傳入的 cmp function回傳的值,若 cmp(priv, a, b) <= 0 則表示 a < b ,將 a 加入尾端並把 *a 往後移一節,若 *a 為空串列則回 *b 做排序。

段落中的程式碼標注,使用 1 個 backtick,而非 3 個。

已更改

static struct list_head *merge(void *priv, list_cmp_func_t cmp,
				struct list_head *a, struct list_head *b)
{
	struct list_head *head, **tail = &head;

	for (;;) {
		/* if equal, take 'a' -- important for sort stability */
		if (cmp(priv, a, b) <= 0) {
			*tail = a;
			tail = &a->next;
			a = a->next;
			if (!a) {
				*tail = b;
				break;
			}
		} else {
			*tail = b;
			tail = &b->next;
			b = b->next;
			if (!b) {
				*tail = a;
				break;
			}
		}
	}
	return head;
}

先排除 list 為空值或只有一個節點的情況,再利用 head->prev->next 將 list 轉為單向鏈結串列。

struct list_head *list = head->next, *pending = NULL;
size_t count = 0;	/* Count of pending */

if (list == head->prev)	/* Zero or one elements */
    return;

/* Convert to a null-terminated singly-linked list. */
head->prev->next = NULL;

將 list_sort.c 及 list_sort.h 引入 lab0-c ,在 qutest.c 中用 extern 外部宣告 list_sort 函式。

+typedef int + __attribute__((nonnull(2, 3))) (*list_cmp_func_t)(void *, + const struct list_head *, + const struct list_head *); +extern void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp);

定義 cmp 函式減少後續重複程式碼使用。

+int cmp(void *priv, const struct list_head *a, const struct list_head *b) +{ + return strcmp(list_entry(a, element_t, list)->value, + list_entry(b, element_t, list)->value); +}

新增 listsort 命令。

ADD_COMMAND(reverse, "Reverse queue", ""); ADD_COMMAND(sort, "Sort queue in ascending/descening order", ""); + ADD_COMMAND(listsort, "Sort queue in ascending/descening order", ""); ADD_COMMAND(size, "Compute queue size n times (default: n == 1)", "[n]"); ADD_COMMAND(show, "Show queue contents", ""); ADD_COMMAND(dm, "Delete middle node in queue", "");

修改 Makefile。

OBJS := qtest.o report.o console.o harness.o queue.o \ random.o dudect/constant.o dudect/fixture.o dudect/ttest.o \ shannon_entropy.o \ - linenoise.o web.o + linenoise.o web.o list_sort.o deps := $(OBJS:%.o=.%.o.d)

詳細程式碼在 commit_b8e0681

提供新的命令 shuffle

參考 Fisher–Yates shuffle 實做洗牌演算法,新增 q_shuffle 函式根據下面步驟進行:

  1. 確認鏈節串列不為空值。
  2. 使用 q_size 計算鍊結串列長度,並用 for 迴圈從最尾端依序向前做交換。
  3. 從目前要交換的節點之前找出隨機節點,使用 srand(time(NULL)) 更改 seed 避免每次找隨機值結果不變。
  4. 利用 swap 交換兩節點,直到 *last 指向第二節點時停止迴圈。
void q_shuffle(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    
    struct list_head *last = head->prev;
    for (int len = q_size(head); len > 1; len--) {
        srand(time(NULL));
        int random_idx = rand() % len;

        struct list_head *random_node = head->next;

        while (random_idx--)
            random_node = random_node->next;
        
        swap(last, random_node);

        last = last->prev;
    }
}

使用 ADD_COMMAND 新增 shuffle 命令。

ADD_COMMAND(reverse, "Reverse queue", ""); ADD_COMMAND(sort, "Sort queue in ascending/descening order", ""); ADD_COMMAND(listsort, "Sort queue in ascending/descening order", ""); + ADD_COMMAND(shuffle, "Shuffle the queue using Fisher-Yates Shuffle", ""); ADD_COMMAND(size, "Compute queue size n times (default: n == 1)", "[n]"); ADD_COMMAND(show, "Show queue contents", ""); ADD_COMMAND(dm, "Delete middle node in queue", "");

修改 Makefile。

OBJS := qtest.o report.o console.o harness.o queue.o \ random.o dudect/constant.o dudect/fixture.o dudect/ttest.o \ shannon_entropy.o \ - linenoise.o web.o list_sort.o + linenoise.o web.o list_sort.o shuffle.o \ deps := $(OBJS:%.o=.%.o.d)

詳細程式碼在commit_adfc198

研讀論文〈Dude, is my code constant time?〉

Timing attacks 是一種廣泛的 side-channel attacks ,不同於直接使用密碼學演算上的攻擊手段,他是利用系統執行時間的特性進行破解。舉例來說,在判斷一段密碼是否與原密碼相符時,若是從第一個字母逐一比對遇到不符合再回傳錯誤警告,就可利用回傳時間來判斷前面正確的字符有幾個,進而產生資安疑慮。
有多數研究和偵測執行可變時間的方法被開發出來,例如 ctgrindFlow-trackerctverif ,大多需要對硬體進行建模,但困難點在於較難取得 CPU 細節資訊,此論文提出 dudect 方法可利用統計分析的程式判定是否達成 constant-time ,不用依靠靜態分析可避免硬體上的限制。

Step 1: Measure execution time

  • 針對不同輸入資料重複對執行時間進行觀察,第一種資料通常為固定的值,第二種為隨機產生。
  • 現在 CPU 提供週期計數器(Cycle counters)可準確獲取執行時間。
  • 最小化環境差異造成的影響,每次測量都會對應隨機產生的輸入分類。

Step 2: Apply post-processing

在進入統計分析之前會先對每個單獨的測量值進行一些後處理:

  • Cropping:可能會因為 OS 或一些外部因素導致時間分佈呈現 positive skew ,這時候可透過裁減 (crop) 掉一些超過 threshold 的測量結果。
  • Higher-order preprocessing:使用高階的預處理方式有益於測量,例如scentered productmimicking higher-order DPA attack

Step 3: Apply statistical test

透過統計檢定來反駁兩執行時間相等的假設,有幾種檢測方式如 t-testNon-parametric tests 等。

dudect

從每個 trace 中追蹤第17筆測資會無法通過,觀察內部指令為進入 simulation 判斷時造成的問題,回到 qtest.c 中觀察程式做 constant time 判斷使用到的兩函式分別為 is_insert_tail_const()is_insert_head_const()

if (simulation) {
    if (argc != 1) {
        report(1, "%s does not need arguments in simulation mode", argv[0]);
        return false;
    }
    bool ok =
        pos == POS_TAIL ? is_insert_tail_const() : is_insert_head_const();
    if (!ok) {
        report(1,
               "ERROR: Probably not constant time or wrong implementation");
        return false;
    }
    report(1, "Probably constant time");
    return ok;
}

兩函式存放位置在 fixture.h 檔案中,裡面定義了 DUT_FUNCS 用來測試是否達到 constant time 。

#ifndef DUDECT_FIXTURE_H
#define DUDECT_FIXTURE_H

#include <stdbool.h>
#include "constant.h"

/* Interface to test if function is constant */
#define _(x) bool is_##x##_const(void);
DUT_FUNCS
#undef _

#endif

fixture.c 中找到關於 constant time 的實作程式,與 dudect 原始程式碼做比對發現缺漏了部份內容。

static void prepare_percentiles(dudect_ctx_t *ctx) {
  qsort(ctx->exec_times, ctx->config->number_measurements, sizeof(int64_t), (int (*)(const void *, const void *))cmp);
  for (size_t i = 0; i < DUDECT_NUMBER_PERCENTILES; i++) {
    ctx->percentiles[i] = percentile(
        ctx->exec_times, 1 - (pow(0.5, 10 * (double)(i + 1) / DUDECT_NUMBER_PERCENTILES)),
        ctx->config->number_measurements);
  }
}

fixture.c 補上 prepare_percentiles 函式,且因 prepare_percentiles 使用了 DUDECT_NUMBER_PERCENTILES 定義及其餘函式所以需要一併補齊。

static int cmp(const int64_t *a, const int64_t *b) {
    if (*a == *b)
        return 0;
    return (*a > *b) ? 1 : -1;
}

static int64_t percentile(int64_t *a_sorted, double which, size_t size) {
  size_t array_position = (size_t)((double)size * (double)which);
  assert(array_position < size);
  return a_sorted[array_position];
}

doit 函式中新增剛補上的 prepare_percentiles ,且修改有使用到 DUDECT_NUMBER_PERCENTILES 定義的 update_statistics 參數。

@@ -123,6 +161,7 @@ static bool doit(int mode) int64_t *exec_times = calloc(N_MEASURES, sizeof(int64_t)); uint8_t *classes = calloc(N_MEASURES, sizeof(uint8_t)); uint8_t *input_data = calloc(N_MEASURES * CHUNK_SIZE, sizeof(uint8_t)); + int64_t *percentiles = calloc(DUDECT_NUMBER_PERCENTILES, sizeof(int64_t)); if (!before_ticks || !after_ticks || !exec_times || !classes || !input_data) { @@ -133,7 +172,8 @@ static bool doit(int mode) bool ret = measure(before_ticks, after_ticks, input_data, mode); differentiate(exec_times, before_ticks, after_ticks); - update_statistics(exec_times, classes); + prepare_percentiles(percentiles, exec_times); + update_statistics(exec_times, classes, percentiles); ret &= report();

再使用 make test 測試所有 trace ,可發現所有測試項目都可通過。

fangni@fangni-G5-KF:~/linux2024/lab0-c$ make test
scripts/driver.py -c
---	Trace		Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
---	trace-01-ops	5/5
+++ TESTING trace trace-02-ops:
# Test of insert_head, insert_tail, remove_head, remove_tail, and delete_mid
---	trace-02-ops	6/6
+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, remove_head, reverse and merge
---	trace-03-ops	6/6
+++ TESTING trace trace-04-ops:
# Test of insert_head, insert_tail, size, swap, and sort
---	trace-04-ops	6/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head, reverse, size, swap, and sort
---	trace-05-ops	6/6
+++ TESTING trace trace-06-ops:
# Test of insert_head, insert_tail, delete duplicate, sort, descend and reverseK
---	trace-06-ops	6/6
+++ TESTING trace trace-07-string:
# Test of truncated strings
---	trace-07-string	6/6
+++ TESTING trace trace-08-robust:
# Test operations on empty queue
---	trace-08-robust	6/6
+++ TESTING trace trace-09-robust:
# Test remove_head with NULL argument
---	trace-09-robust	6/6
+++ TESTING trace trace-10-robust:
# Test operations on NULL queue
---	trace-10-robust	6/6
+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
---	trace-11-malloc	6/6
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
---	trace-12-malloc	6/6
+++ TESTING trace trace-13-malloc:
# Test of malloc failure on new
---	trace-13-malloc	6/6
+++ TESTING trace trace-14-perf:
# Test performance of insert_tail, reverse, and sort
---	trace-14-perf	6/6
+++ TESTING trace trace-15-perf:
# Test performance of sort with random and descending orders
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
---	trace-15-perf	6/6
+++ TESTING trace trace-16-perf:
# Test performance of insert_tail
---	trace-16-perf	6/6
+++ TESTING trace trace-17-complexity:
# Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant
Probably constant time
Probably constant time
Probably constant time
Probably constant time
---     trace-17-complexity     5/5
---	TOTAL		100/100

詳細程式碼在 commit_50da0ff