2019q1 Homework1 (lab0)

contributed by < afcidk >

• C Programming Lab
• F01: lab0

後續改進:

1. 參照 dudect 和對應的論文 dude, is my code constant time?，學習其中檢測時間複雜度的機制，對本題要求
   $O(1)$ 的實作部分，給予更廣泛的測試;
2. 重新整理下方共筆 (刪去過時資訊)，學習技術文件的撰寫，可參照 基於 C 語言標準研究與系統程式安全議題 的風格;
   jserv

實驗環境

作業系統：Linux elementaryOS 4.16.9-041609-generic
gcc 版本：8.1.0

gcc 版本應該升級到 7.2+, 否則後續有些實驗 (如 LTO) 會無效

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

另外，原本提供的資料結構

/* 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()

#define free test_free
#define malloc test_malloc

其實整個 harness.h 最外層是被一層 macro 包裝起來了

#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
  ​​​​#define INTERNAL 1
  ​​​​#include "harness.h"
  

• queue.c
  ​​​​#include "harness.h"
  

• harness.c
  ​​​​#define INTERNAL 1
  ​​​​#include "harness.h"
  

由此可知我們實作的時候，使用的 free/malloc 都會被 hook 成已經寫好的 test_free/test_malloc，這樣做的用意是提供多一層的檢查，讓程式在出錯（e.g. double free）時不會直接 crash 而是印出錯誤訊息。

然而，這樣做也有一些缺點，像是我們沒有辦法使用有呼叫 malloc / free 的其他標準函式，例如 strdup()。

可以比照 test_malloc/test_free，去封裝 strdup 一類的函式嗎？若可，提交對應的 pull request

jserv

pull request: https://github.com/sysprog21/lab0-c/pull/6

q_new

這部份會初始化我們的 queue，需要注意判斷 malloc 有沒有成功。

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 清空。

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。

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

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，也需要特別判斷。

 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。

int q_size(queue_t *q)
{
    if (!q || !q->head)
        return 0;
    return q->size;
}

q_reverse

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 工具以及提出的對應論文 Dude, is my code constant time?，我們得知了一種以實驗而非理論驗證時間複雜度的方法。

他透過 timing attack (精確一點只算是 leakage，因為洩漏的資訊太少不足以完成一項攻擊) 來檢測。

一種 leakage detection 的方式是 fix-vs-random test。這個方式透過餵給程式固定以及隨機的資料，再比較執行時間的差異。

dudect 使用的方法便是這種 fix-vs-random test。在得到執行時間後，利用 t-test 檢查兩種測試資料是否差異。

最後我取 dudect 中計算 t-test 的部份，修改後放到 qtest 中。執行 qtest -t 可以測試 q_insert_tail 和 q_size 是否可能非常數時間複雜度。

不過我還沒有把 fix-vs-random test 理解得很透澈，看完之後再來補上

qtest -t 相關的程式碼在這個 commit 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 的開發紀錄 ↩︎