# 2024q1 Homework5 (assessment)
contributed by < `Booker-Chen` >

## 紀錄閱讀[〈因為自動飲料機而延畢的那一年〉](https://blog.opasschang.com/the-story-of-auto-beverage-machine-1/)的啟發

閱讀完這則回顧文之後，我蠻佩服作者在決定好一個方向之後，可以就這樣毅然決然地走下去。雖然他也有提到在過程中有想要放棄的念頭，但是在身邊的人給與鼓勵以及他自己去找 Jserv 聊聊之後，他還是決定已經開始走的路要走完，並且到最後還真的做出了一個看起來蠻成功的成品出來。今天換作是我說要做一個非資工系本科的東西要燒錢然後會搞到延畢，可能就要家庭革命好幾回了，而且中間也要找到有興趣和自己一起參與專案的該專業領域的同學們，然後遭遇滿滿的問題跟挫折，有沒有那個決心和毅力走下去我自己覺得我是沒那個能耐啦。

在這則回顧文的第 13 篇中提到他需要知道要買多大容量的機器來裝冰塊，他不是靠感覺去決定，而是透過飲料店的實際數據來推估，對應到 Jserv 一直和我們強調我們做出來的東西不能有不確定的因素(不要一直說好像)。要買多大的容器可以透過數據去明確的推估需要多大，而不是大概要多大。就像在第一次實體討論的時候，雖然老師有說是用 [dudect](https://github.com/oreparaz/dudect) 這個程式來測試程式的執行是不是常數時間，但是我們從來沒有考慮過這個測試程式到底合不合理、準不準確。

在聽完 Jserv 的這段靈魂發問，瞬間理解為什麼需要我們去研讀論文，除了能知道程式碼的運作理論之外，還能讓我們自行判斷這樣的運作合不合理。所以在寫作業的時候，要明確的知道自己使用的演算法以及程式的運作機制，需要使用其他工具或者是參考別人的程式碼的時候不要無腦的直接拿來用，直接拿來抄，而是要先去研究其機制以及是不是正確的，像是 Jserv 超討厭的 CSDN。還有就是如果這個工具有在 GitHub 上，如果發現有錯誤或是可以改進的地方，有餘力的話可以發個 PR 看對方會不會理你；發現其他學員的程式碼或敘述可以改進或有錯誤，可以直接在 Hackmd 上跟他交流交流。

回顧文第 5 篇中還有提到自動飲料機如果製作出來不管成本和效益能動就行，那根本不會有商家願意採用，就很像 Jserv 說的，在現在二十一世紀，如果做出來的東西能動就行，那他就是垃圾。我們如果要做東西出來應該是有人願意用，有商業價值的，而不是像我們應付課程趕出來的作業，只有一個使用者，助教，然後自己根本不會想要使用它。

在回顧文第 22 篇中作者調侃道資工系的學生不會寫程式，機械系的學生不會做機械，電工系的學生不會焊電路，而這也和 Jserv 諷刺的高等教育一樣。大學應付課程拿了高分，然後呢?在上這堂 Linux 核心設計時才發現自己以前學到的是多麼的不足。考試只能考考古，以前沒出過的題目那現在也不能出，考出來就會被學生亂寫教學評鑑或在網路上罵爆。聽 Jserv 在課堂上提到過以前的大學一堂課的通過率只有不到兩成，而且能在課堂上扎扎實實的學到東西，我也覺得回歸到這樣的模式好像挺不錯的但是我可能就會畢不了業了。

## 研讀第 1 到第 6 週[「課程教材」](https://wiki.csie.ncku.edu.tw/linux/schedule)

## 研讀 [CS:APP 3/e](https://csapp.cs.cmu.edu/)

### [DATA : Tmin](https://csapp.cs.cmu.edu/3e/waside/waside-tmin.pdf)

以下為 `signed int` 的最大值和最小值在 C 的 lists.h 這個 header file 的定義：

/* Minimum and maximum values a ‘signed int’ can hold. */
#define INT_MAX 2147483647
#define INT_MIN (-INT_MAX - 1)

這個時候就有一個疑問了，為什麼 `INT_MIN` 的定義是 `(-INT_MAX - 1)` 而不是 `-2147483648` 或 `0x80000000` 呢 ?

首先我們要知道當編譯器遇到一個 `-X` 這樣形式的數字，它會先確定 `X` 的值和型別，然後再對其取負號。

接下來我們看下面這兩張表

如果我定義 `INT_MIN` 為 `-2147483648`，那我們就要先確定 `2147483648` 的型別和值，但是在 32 位元下 `int` 沒辦法表示 `2147483648`，所以編譯器就會往下找找到可以容得下 `2147483648` 的型別。

如果是 C90 的話，就會把 `2147483648` 轉型成 `unsigned`，然而，`2147483648` 和 `-2147483648` 的 16 進位表示式是一樣的，所以 `-2147483648` 到最後會變成 `unsigned` 的 `2147483648`。反觀 C99，編譯器會把 `2147483648` 轉型成 `long long` (64位元)，`2147483648` 和 `-2147483648` 的 16 進位表示式不一樣，所以到最後會變成 `long long` 的`-2147483648`。

如果我將`INT_MIN` 定義為 `0x80000000`，那最後結果就會和 C90 一樣，被定義為 `unsigned` 的 `0x80000000`，也就是 `2147483648`。

## 想投入的專案

因為前一個月對於這門課程的投入甚微，所以我個人覺得自己如果可以的話專題就繼續完成 [lab0](https://github.com/Booker-Chen/lab0-c)，在之後與老師討論後再看需要完成的程度。

---

[專題解說影片](https://youtu.be/1EVuylFajC8)

branchless max

// Return the max value of given values
int max(int a, int b)
{
    return a ^ ((a ^ b) & -(a < b));
}

TODO: 上述程式碼是否適用於無號整數？

首先先分析程式碼，如果 a 大於 b 的話，那 -(a < b) 的結果就會是 0，則 (a ^ b) 就會和 0 做 bitwise AND 得到 0，再來就是把 a 和 0 做 bitwise XOR，得到最後的回傳值為 a。

如果 a 小於 b，那 -(a < b) 的結果就會是 -1，則 (a ^ b) 就會和 -1 做 bitwise AND，得到 (a ^ b)，再來就是計算 a ^ (a ^ b)，得到最後的回傳值為 b。

所以只要能夠正確地比較 a 和 b 的大小，就可以使用這個方法。

回到問題，此程式碼是否適用於無號整數，答案是可以，但前提是 a 和 b 都要是無號整數。在 [CS:APP 第 2 章重點提示和練習](https://hackmd.io/@sysprog/CSAPP-ch2) 中提到 :

> 當無號數與有號數在 C 語言混合在單一表示式時，有號數會被轉換為無號數。在運算子操作時會有些意外的結果。有號數負值會因為轉換成 2 補數後，反而負值會大於正值。因此要注意混用時的運算狀況。

所以當 a 和 b 同時都是整數或無號整數時，就可以用該程式碼來比大小。

TODO: 針對無號整數，實作不需要分支的 min 和 max

無號整數也可以用上面的那個程式實作出不需要分支的 max，所以要求 min 的話只要把 < 改成 > 就行了。

// Return the min value of given values
unsigned min(unsigned a, unsigned b)
{
    return b ^ ((a ^ b) & -(a < b));
}

sign extension: https://en.wikipedia.org/wiki/Sign_extension => 為何如此？

當我們需要將較小位元的有號整數擴展成較大位元的有號整數的時候，比方說要將一個 6 位元的整數擴展成 32 位元的整數，那就需要用到 sign extension。

要實現 sign extension 首先需要知道該位元整數的 `MSB` 是 0 或 1。如果 `MSB` 是 0 的話那最高位就全部為 0；如果 `MSB` 是 1 的話那最高位就全部為 1。

比方說我想要對一個 6 位元的整數做 sign extension 成 16 位元。假設這個整數的二進位表示為 `011101`，它的 `MSB` 為 0，那做完 sign extension 後它就會變 `0000000000011101`；假設這個整數的二進位表示為 `110010`，它的 `MSB` 為 1，那做完 sign extension 後它就會變 `1111111111110010`。

實際的操作可以參考 [Bit Twiddling Hacks 解析 (一) 的 Sign Extension](https://hackmd.io/@0xff07/BTS/https%3A%2F%2Fhackmd.io%2F%400xff07%2FORAORAORAORA#Sign-Extension)

zero extension

zero extension 就是最高位全部都設成 0，主要是用在擴展無號整數。

int32_t x = ???;
(int16_t) x => signness 不變

TODO: 重作 lab0 裡頭的 dudect 強化，「重讀」論文 (紀錄不理解的地方，第幾段第幾行第幾個字，重現實驗)
> https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-d
> 為何要用 Student T Test?

**為什麼需要知道程式碼的運行是否為常數時間 ?**

在密碼學的實作上，如果程式碼的運行不是常數時間，就能夠透過監測程式碼的執行時間進行[時序攻擊](https://en.wikipedia.org/wiki/Timing_attack)，從而取得密碼或金鑰等的機密資訊。Paul C. Kocher 在 1996 年發表的這篇論文 [Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems](https://link.springer.com/chapter/10.1007/3-540-68697-5_9) 就是透過監測執行時間進而取得私鑰破解加密系統。

**為什麼選擇使用 dudect ?**

網路上有很多其他常數時間的檢測工具，像是 [ctgrind](https://github.com/agl/ctgrind) 和 [ctverif](https://github.com/michael-emmi/ctverif)，那為什麼我們要使用 dudect 呢 ? 因為前面提到的這些檢測工具需要模擬硬體設備，然而要模擬出一個完整並且正確的硬體設備並不是一件容易的事。反觀 dudect 則是透過 [leakage detection tests](https://dl.acm.org/doi/pdf/10.1145/1015047.1015050)，在目標平台上對一段程式碼做執行時間的統計學分析，如此一來就巧妙的規避需要模擬硬體的問題。

**程式運作原理**

簡單來說，dudect 是對程式碼的執行時間做 leakage detection test。首先我們會先測量兩個不同類別的 input data 的執行時間，再來比較兩者的時間分佈在統計學上是否有所不同。

第一步 : Measure execution time

我們要重複地測量 cryptographic function 在兩個不同 class 的 input data 下的執行時間，這裡有幾個需要注意的點。

1. Classes definition: 論文中採用的是 fix-vs-random，fixed class 是用來做 corner-case processing。

2. Cycle counter: 現今的 CPU 提供 cycle counter 讓我們可以用來精準的測量出執行時間。
在 dudect.h 中有 `cpucycles` 這個函式，其功能為回傳 processor 的 time-stamp counter 的值。
`__rdtsc()` 的[作用](https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.htm#text=rdtsc&ig_expand=4395,5273)是取得 processor 的 time-stamp counter 的值。
`_mm_mfence()` 的[作用](https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.htm#text=mfence&ig_expand=4395,5273,4395)是確保在執行下一個指令前，所有對記憶體存取的操作都要先執行完。

static inline int64_t cpucycles(void) {
  _mm_mfence();
  return (int64_t)__rdtsc();
}

3. Environmental conditions: 為了減少環境的干擾，我們會在開始測量前，用隨機的方式選擇 class 並且準備好 input data。
在要測試的檔案中完成 `prepare_input(dudect_config_t *c, uint8_t *input_data, uint8_t *classes)` 這個函式，以達成隨機選擇 class 及準備好 input data。

第二步 : Apply post-processing

在開始執行 statistical analysis 之前，我們可以採用一些 post-processing 的方法。

1. Cropping
當執行時間越長，timing distribution 就會越不準確，因為可能遇到 interrupt。為了避免這種情況，我們可以設定閾值，當執行時間超過這個閾值，就忽略掉該次的測量。
在 dudect.h 中有 `percentile` 和 `prepare_percentile` 這兩個函式用來設定閾值。
2. Higher-order preprocessing

第三步 : Apply statistical test

我們要使用 statistical test 嘗試推翻虛無假說 "the two timing distributions are equal"。

這篇論文在 III. Result -> A. Implement -> (b) Statistical test 中說明使用的 statistical test 是 [Welch's t-test](https://en.wikipedia.org/wiki/Welch%27s_t-test) 搭配 [Welford's variance computation method](https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance) 做使用。

選擇使用 Welch's t-test 的原因 :

Welch's t-test 是 [Student's t-test](https://en.wikipedia.org/wiki/Student%27s_t-test) 的一種變形，當兩個獨立樣本具有相同或不相同的樣本數以及異質變異數的情況下就可以使用 Welch's t-test。

dudect 判斷一段程式碼是否為常數時間的依據為比較兩個不同 class 的 timing distribution。所以我們需要知道兩個不同 class 的執行時間的平均值和變異數。然而在 `prepare_input` 這個函式採用了 randomly chosen class，這樣會使得兩個獨立樣本具有相同或者不相同的樣本數，再加上我們無從得知母體的變異數以及兩個樣本的變異數可能相同或不同，所以選擇使用 Welch's t-test。

在 dudect.h 中有 `t_push` 和 `t_compute` 這兩個函式可以用做計算 Welch's t-test 的 t 值。

**檢測結果**

:::info
論文中並未提及為何設置 `DUDECT_ENOUGH_MEASUREMENTS` 為 10000
:::

檢測函式 `check_tag` 的運行是否為常數時間。
該函式的功能為比較 `x` 和 `y` 這兩個陣列的前 `len` 個 byte 做比較。

int check_tag(uint8_t *x, uint8_t *y, size_t len) {
    return memcmp(x, y, len);
}

在 [Linux manual page](https://man7.org/linux/man-pages/man3/memcmp.3.html) 提到關於 `memcmp` 的描述
>Do not use memcmp() to compare confidential data, such as cryptographic secrets, because the CPU time required for the comparison depends on the contents of the addresses compared, this function is subject to timing-based side-channel attacks. In such cases, a function that performs comparisons indeterministic time, depending only on n (the quantity of bytes compared) is required.

從這段描述中可以得知 `memcmp` 的運行並不是常數時間，因為當它在比較的過程中一發現兩者不同，就會直接回傳值了。

第一個測試 : 設定 fix class 的 input data 為 s ([白箱測試](https://en.wikipedia.org/wiki/White-box_testing))

當 input data 是 fix class 的時候，`memcmp` 會把 `len` 比完才回傳，所以和 random closs 的 timing distribution 會有蠻明顯的不同。
可以很明顯的知道不會是常數時間。

第二個測試 : 設定 fix class 的 input data 是全部為 0 的陣列 ([黑箱測試](https://en.wikipedia.org/wiki/Black-box_testing))

fix class 的 input data 全部設為 0 和 random class 的 timing distribution 應該會蠻近似的只是不會到完全重疊，所以還是可以檢測到 timing leakage，但是 t 值相對於第一個測試小很多。

第三個測試 : 實作一個常數時間的 `memcmp`

參考自 github 的 [cst_time_memcmp](https://github.com/chmike/cst_time_memcmp)

int check_tag(uint8_t *x, uint8_t *y, size_t len) {
    const uint8_t *px = (const uint8_t*)x; 
    const uint8_t *py = (const uint8_t*)y; 
    int res = 0, diff;
    if (len > 0) {
        do {
            --len;
            diff = px[len] - py[len];
            res = (res & -!diff) | diff;
        } while (len != 0);
    }
    return (res > 0) - (res < 0);
}

如果 `diff` 為 0，那 `res` 的值不變；如果 `diff` 為非 0 整數，`res` 的值為 `diff`。

因為這個 `memcmp` 不會因為一發現兩者不同就直接回傳值，而是會等比完指定的長度 `len` 之後再回傳值。

所以 fix class 和 random class 的 timing distribution 會重疊，那就可能會是常數時間。

>TODO:
>繪製圖表
>鑽研 higher-order preprocessing
>詳閱重要部分引用之論文