# Linux 核心專題: 判定常數時間
> 執行人: Booker-Chen
> [專題解說影片](https://youtu.be/Bdd_wdWfaF4)
## 任務簡介
回顧第一次作業提到的 dudect，詳述其原理，並重現相關實驗，從而歸納出判斷給定的程式碼是否屬於常數時間的實作。應彙整其他學員的成果，例如：
* [weihsinyeh](https://hackmd.io/@weihsinyeh/SJUVTnEn6)
* [vax-r](https://hackmd.io/@vax-r/linux2024-homework1)
* [Kuanch](https://hackmd.io/@Kuanch/linux2024-homework1)
## TODO: 探討常數時間的重要性
> 為什麼需要知道程式碼的執行是否為常數時間 ?
> 從資訊安全、密碼學，和處理器的行為來探討。
在 [解讀計算機編碼](https://hackmd.io/@sysprog/binary-representation#%E8%A7%A3%E8%AE%80%E8%A8%88%E7%AE%97%E6%A9%9F%E7%B7%A8%E7%A2%BC) 中提到若一段程式碼的運行不是常數時間的話，就可能會被發起時序攻擊 ([timing attack](https://en.wikipedia.org/wiki/Timing_attack))。
### 取絕對值 `abs`
有分支 (branch) 的絕對值函式
```c
int abs(int value)
{
return (value < 0) ? -value : value;
}
```
該函式當遇到負數時會比遇到正數時多執行 `-value` 這道敘述，
針對 32 位元沒有分支 (branchless) 的絕對值函式
```c
int32_t abs(int32_t x)
{
int32_t mask = (x >> 31);
return (x ^ mask) - mask;
}
```
當 `x` > `0`，`mask` = `0x00000000`，`(x ^ mask)` = `x`，`x - mask` = `x`。
當 `x` < `0`，`mask` = `0xFFFFFFFF`，`(x ^ mask)` = `~x`，`~x - mask` = `~x + 1` = `-x`
### memcmp
在 [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` 的運行並不是常數時間，因為當它在比較的過程中一發現兩者不同，就會直接回傳值了。
常數時間的 `memcmp`
[2019q1 第 3 週測驗題 (上) 測驗一](https://hackmd.io/@sysprog/S1weT4iLE?type=view#%E6%B8%AC%E9%A9%97-1)
```c
#include <stdint.h>
#include <stddef.h>
int cst_memcmp(const void *m1, const void *m2, size_t n) {
const uint8_t *pm1 = (const uint8_t *) m1 + n;
const uint8_t *pm2 = (const uint8_t *) m2 + n;
int res = 0;
if (n) {
do {
int diff = *--pm1 - *--pm2;
res = (res & (((diff - 1) & ~diff) >> 8)) | diff;
} while (pm1 != m1);
}
return ((res - 1) >> 8) + (res >> 8) + 1;
}
```
<s>
X = `(diff - 1)`
Y = `diff`
</s>
:::danger
專注於程式碼本身，不要列出填空的 X, Y
:::
>收到，已更改
**解析 `res = (res & (((diff - 1) & ~diff) >> 8)) | diff`**
`diff` 的範圍為 255 ~ -255，即 `0x000000FF` ~ `0x00000000`，`0xFFFFFFFF` ~ `0xFFFFFF01`。
當 `diff` = `0`
`((diff - 1) & ~diff)` = `0xFFFFFFFF & 0xFFFFFFFF` = `0xFFFFFFFF`
`0xFFFFFFFF >> 8` = `0xFFFFFFFF`
`res & 0xFFFFFFFF` = `res`
`res | diff` = `res | 0` = `res`
`res` = `res`
當 `diff` != `0`
`(((diff - 1) & ~diff) >> 8)` = `0`
`res & 0` = `0`
`0 | diff` = `diff`
`res` = `diff`
**解析 `((res - 1) >> 8) + (res >> 8) + 1`**
若 `res` > `0`
`(res - 1) >> 8` = `0`
`res >> 8` = `0`
`0 + 0 + 1` = `1`
若 `res` < `0`
`(res - 1) >> 8` = `0xFFFFFFFF`
`res >> 8` = `0xFFFFFFFF`
`0xFFFFFFFF + 0xFFFFFFFF + 1` = `-1`
若 `res` = `0`
`(res - 1) >> 8` = `0xFFFFFFFF`
`res >> 8` = `0`
`0xFFFFFFFF + 0 + 1` = `0`
:::info
其他常數時間的 `memcmp` [實作](https://github.com/chmike/cst_time_memcmp)
:::
## TODO: dudect 背後的原理
> 研讀[論文](https://eprint.iacr.org/2016/1123.pdf)，應彙整其他學員的成果，詳述其原理，提及相關數學和統計學議題。
### 為什麼選擇 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)，在目標平台上對一段程式碼做執行時間的統計分析，如此一來就巧妙的規避需要模擬硬體的問題。
### leakage detection test 實作流程
:::info
此部分的程式碼解釋採用的是最接近論文發表日期 2017 年 5 月 27 日的 commit [5237cc0](https://github.com/oreparaz/dudect/commit/5237cc08bf3365ad4ec26bb40a947736ebdfc5b6) 這個版本。
:::
#### 第一步 : Measure execution time
我們要重複地測量一個函式在兩個不同 class 的 input data 下的執行時間。
1. Classes definition: 論文中採用的是 fix-vs-random，fixed class 是用來做 corner-case processing。
2. Cycle counter: 現今的 CPU 提供 cycle counter 讓我們可以用來精準的測量出執行時間。
在 cpucycles.c 中有 `cpucycles` 這個函式，其功能為回傳 processor 的 time-stamp counter 的值。
[rdtsc](https://www.aldeid.com/wiki/X86-assembly/Instructions/rdtsc) 這道指令會把 time-stamp counter 存進 EDX:EAX 這兩個暫存器中，透過宣告兩個無號整數 `hi`、`lo`，將 EDX、EAX 的值讀取出來，再透過將 `hi` 左移 32 位並與 `lo` 做 bitwise OR 之後，回傳 time-stamp counter 的值。
```c
int64_t cpucycles(void)
{
unsigned int hi, lo;
__asm__ volatile("rdtsc\n\t" : "=a"(lo), "=d"(hi));
return ((int64_t)lo) | (((int64_t)hi) << 32);
}
```
3. Environmental conditions: 為了減少環境的干擾，我們會在開始測量前，透過隨機指派 class 產生 input data。
在要測試的檔案中完成函式 `prepare_input`。一開始使用 `randombytes` 這個函式使 input data 全部為 random class，接下來再透過 `classes[i] = randombit();` 這行程式碼將該次量測的 input data 透過隨機的方式選擇使用 fix class 或是 random class。
:::danger
注意書寫規範：
* 使用 lab0 規範的程式碼書寫風格，務必用 clang-format 確認一致
:::
>lab0-c 採用的程式碼開發風格: [CONTRIBUTING.md](https://github.com/sysprog21/lab0-c/blob/master/CONTRIBUTING.md)
>已修正
```c
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) {
memset(input_data + (size_t)i * chunk_size, 0x00, chunk_size);
} else {
/* leave random */
}
}
}
```
#### 第二步 : Apply post-processing
在開始執行 statistical analysis 之前，我們可以採用一些 post-processing 的方法。
1. Cropping
通常時間分佈會朝較長的執行時間份佈，而呈現正偏差 ([positively skewed](https://en.wikipedia.org/wiki/Skewness)) 。原因來自於 OS 的中斷或是很多行程的 Logical control flows 交錯…與測量目標無關的事件。為了避免這種情況，我們可以設定閾值，當執行時間超過這個閾值，就忽略掉該次的測量。
可以透過 percentile.c 中的 `percentile` 函式和 fixture.c 中的 `prepare_percentile` 函式設定閾值。
:::danger
注意書寫規範：
* 使用 lab0 規範的程式碼書寫風格，務必用 clang-format 確認一致
:::
>已修正
`prepare_percentiles` 函式會將執行時間的陣列、一個 0 ~ 1 的值 (此處為函數 $1 - 0.5^\frac{10 \times (i + 1)}{DUDECT\_NUMBER\_PERCENTILES}$)、執行時間的陣列長度傳給 `percentile` 函式，並依據其回傳的值設為百分位數。
```c
static void prepare_percentiles(int64_t *ticks)
{
for (size_t i = 0; i < number_percentiles; i++) {
percentiles[i] = percentile(ticks,
1 - (pow(0.5, 10 * (double)(i + 1) / number_percentiles)),
number_measurements);
}
}
```
`percentile` 函式會依照 `prepare_percentiles` 傳過來的值做計算後把相應位置的值回傳回去。
```c
int64_t percentile(int64_t *a, double which, size_t size) {
qsort(a, size, sizeof(int64_t), (int (*)(const void *, const void *))cmp);
size_t array_position = (size_t)((double)size * (double)which);
assert(array_position >= 0);
assert(array_position < size);
/* printf("percentile %f is %lld\n", which, a[array_position]); */
return a[array_position];
}
```
>關於閾值的選取是否合理 ?
對函數 $1 - 0.5^\frac{10 \times (i + 1)}{DUDECT\_NUMBER\_PERCENTILES}$ 做分析，`DUDECT_NUMBER_PERCENTILES` 作者設為 `100`。
| i | $1 - 0.5^\frac{10 \times (i + 1)}{100}$ |
|:---:| --------------------------------------- |
| 0 | 0.06696700846 |
| 1 | 0.1294494367 |
| 2 | 0.1877476036 |
| 3 | 0.2421417167 |
| ... | ...|
| 49 | 0.96875 |
| 50 | 0.970842719 |
| 51 | 0.9727952949 |
| ... | ...|
| 97 | 0.9988782243 |
| 98 | 0.9989533462 |
| 99 | 0.9990234375 |
可以看到在閾值的選取上，後 50 筆資料會集中選取後 3% 的執行時間，但是越長的執行時間就代表中間可能遇到與測量目標無關的事件。
2. Higher-order preprocessing
這裡不理解，只能從引用的論文 [Leakage Assessment Methodology](https://www.iacr.org/archive/ches2015/92930478/92930478.pdf) 中找到描述 :
>For a second-order univariate test the mean of the mean-free squared traces $Y = (X − \mu) ^ 2$ is actually the variance ($CM_2$) of the original traces.
對應到 fixture.c 中的 `update_statistics` 函式
```c
/*
* do a second-order test (only if we have more than 10000 measurements).
* Centered product pre-processing.
*/
if (t[0]->n[0] > 10000) {
double centered = (double)difference - t[0]->mean[classes[i]];
t_push(t[1 + number_percentiles], centered * centered, classes[i]);
}
```
#### 第三步 : Apply statistical test
#### dudect 採用的 statistical test
我們要使用 statistical test 嘗試推翻[虛無假說](https://en.wikipedia.org/wiki/Null_hypothesis) $H_0$ "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 online algorithm](https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance) 做使用。
Welch's t-test 是 [Student's t-test](https://en.wikipedia.org/wiki/Student%27s_t-test) 的一種，適用於兩個獨立樣本具有相同或不相同的樣本數以及異質變異數的情況下。
Student's t-test 是一種虛無假說測試，當測試樣本在虛無假說下遵從 [Student's t-distribution](https://en.wikipedia.org/wiki/Student%27s_t-distribution) 就可以使用。
#### 解釋 student's t-distribution
Student's t-distribution，$t_v$，是一個連續的機率分佈函數 (如下圖)。
$t_v$ 的分佈型態由參數 $v$ 決定， $v = 1$ 時 $t_v$ 就是 [standard Cauchy distribution](https://en.wikipedia.org/wiki/Cauchy_distribution) ，當 $v \rightarrow \infty$ 時， $t_v$ 就是 [standard Normal distribution](https://en.wikipedia.org/wiki/Normal_distribution#Standard_normal_distribution)。
$v$，即為自由度 ([Degrees of freedom](https://en.wikipedia.org/wiki/Degrees_of_freedom_(statistics)))，關於自由度的描述 :
>In general, the degrees of freedom of an estimate of a parameter are equal to the number of independent scores that go into the estimate minus the number of parameters used as intermediate steps in the estimation of the parameter itself.
舉例來說，量測 $N$ 個獨立點的變異數，獨立量測數值的個數為 $N$ ，而 intermediate step 使用的參數 (在這裡就是平均數) 只有一個，所以自由度為 $N-1$ 。
Student's t-distribution 的機率分佈函數可以寫成 :
$f(t) = \cfrac{\Gamma(\cfrac{v+1}{2})}{\sqrt{\pi v} \Gamma(\cfrac{v}{2})} (1 + \cfrac{t^2}{v})^{-(v+1)/2}$
當 $v > 1$ 且為偶數時， $f(t) = \cfrac{(v-1)(v-3)\cdots 5\cdot 3}{2 \sqrt{v} (v-2)(v-4)\cdots 4\cdot 2} (1 + \cfrac{t^2}{v})^{-(v+1)/2}$
當 $v > 1$ 且為奇數時， $f(t) = \cfrac{(v-1)(v-3)\cdots 4\cdot 2}{2 \sqrt{v} (v-2)(v-4)\cdots 5\cdot 3} (1 + \cfrac{t^2}{v})^{-(v+1)/2}$
這個機率分佈函數是對稱的，而且長的很像平均數為 0，變異數為 1 的常態分佈，只是頂端矮了一點，兩邊高了一點。
當 $v$ 為 30 時就已經很接近常態分佈了(如下圖，紅線為 t-distribution，藍線為 normal distribution，綠線從中間依序往上為 $v$ = 1, 2, 3, 5, 10)。
#### 程式碼實做 Welch's t-test
在 ttest.c 中有 `t_push` 和 `t_compute` 這兩個函式可以用做計算 Welch's t-test 的 t 值。
透過 Welford's online algorithm 可以求得[樣本平均](https://en.wikipedia.org/wiki/Mean) $\overline{x}_n$ 、有偏樣本變異數 ([biased sample variance](https://en.wikipedia.org/wiki/Variance#Biased_sample_variance)) ${{\sigma}_n}^2$ 、無偏樣本變異數 ([unbiased sample variance](https://en.wikipedia.org/wiki/Variance#Unbiased_sample_variance)) ${{s}_n}^2$
這裡使用 Welford's online algorithm 有兩個好處
1. 節省記憶體空間
2. 避免 [Catastrophic cancellation](https://en.wikipedia.org/wiki/Catastrophic_cancellation)
`t_push` 函式計算出平均 $\overline{x}_n$ 以及 $M_{2,n}$。
計算 $\overline{x}_n$
$$
\overline{x}_n
\ = \
\overline{x}_{n - 1}
\ + \
\cfrac{x_n - \overline{x}_{n - 1}}{n}
$$
計算 $M_{2,n}$
$$
M_{2,n}
\ = \
M_{2,n - 1}
\ + \
(x_n - \overline{x}_{n-1})
\ \times\
(x_n - \overline{x}_n)
$$
:::danger
注意書寫規範：
* 使用 lab0 規範的程式碼書寫風格，務必用 clang-format 確認一致
:::
>已修正
```c
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.
* see Knuth Vol 2
*/
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_compute` 函式透過 `t_push` 函式得出的 $M_{2,n}$ 計算出無偏樣本變異數 ${{s}_n}^2$ ，進而求出 t 值。
$$
{{s}_n}^2
\ = \
\cfrac{M_{2,n}}{n - 1}
$$
$$
t
\ = \
\cfrac{\overline{x}_1 - \overline{x}_2}{\sqrt{{{s}_{\overline{x}_1}}^2 \ + \ {{s}_{\overline{x}_2}}^2}}
$$
:::danger
注意書寫規範：
* 使用 lab0 規範的程式碼書寫風格，務必用 clang-format 確認一致
:::
>已修正
```c
static double t_compute(ttest_ctx_t *ctx)
{
double var[2] = {0.0, 0.0};
var[0] = ctx->m2[0] / (ctx->n[0] - 1);
var[1] = ctx->m2[1] / (ctx->n[1] - 1);
double num = (ctx->mean[0] - ctx->mean[1]);
double den = sqrt(var[0] / ctx->n[0] + var[1] / ctx->n[1]);
double t_value = num / den;
return t_value;
}
```
#### 選擇使用 Welch's t-test 的原因 :
dudect 判斷一段程式碼是否為常數時間的依據為比較兩個不同 class 的 timing distribution。所以我們需要知道兩個不同 class 執行時間的平均值和變異數。然而在 `prepare_input` 這個函式採用了 randomly chosen class，這樣會使得兩個獨立樣本具有相同或者不相同的樣本數，再加上我們無從得知母體的變異數以及兩個樣本的變異數可能相同或不同，所以選擇使用 Welch's t-test。
### 問題與討論
#### How many measurements to take?
作者在論文的 IV. DISCUSSION -> (e) 提到我們到底要做多少次的量測 ?
當一個 leakage detection test 在 $N$ 個樣本的量測下無法推翻虛無假說，那我們不能進一步的推斷在 $N + 1$ 個樣本下也會有一樣的結果。
設定一個確切的量測數量是一個評估者的職責。當有證明足以推翻這個量測數量，比方說量測數量可以更多，那評估的結果也會跟著變動。
leakage detection test 並不會直接告訴你這段程式碼一定會或一定不會有 timing leakage，而是用統計的結果告訴你這段程式碼 “可能” 會有 timing leakage。
#### 關於作者設定的一些數值
在閱讀論文以及重現實驗的過程中，發現作者對於閾值以及執行次數的設定上沒有到很嚴謹以及有些地方沒有很清楚。
1. 關於 random class 和 fix class 的 timing distribution 累積分布函數圖的繪製。
2. 論文中的 t 值設定為超過 4.5 即兩個 class 的 timing distribution 有很大的機率不一樣，但實驗中卻設為 10。
3. 為什麼在 10000 筆量測前不能做 statistic test。
4. 為什麼設定 t 值超過 500 (`t_threshold_bananas`) 就絕對不是常數時間。
關於這些提問我在 dudect 的 GitHub 發了一個 [discussion](https://github.com/oreparaz/dudect/discussions/42)。
## TODO: 重現實驗
> 選定原有程式和新增測試案例，重現常數時間判定的實驗。
這篇論文是在 2017 年 5 月 27 日發表的，所以該論文的實驗應該是使用最接近發表日期的 [5237cc0](https://github.com/oreparaz/dudect/commit/5237cc08bf3365ad4ec26bb40a947736ebdfc5b6) 這個 commit 版本。
### 執行環境
:::danger
避免在虛擬機器上重現實驗。
:::
```shell
$ gcc --version
gcc (Ubuntu 13.2.0-23ubuntu4) 13.2.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: Intel(R) Core(TM) i7-10870H CPU @ 2.20GHz
CPU family: 6
Model: 165
Thread(s) per core: 2
Core(s) per socket: 8
Socket(s): 1
Stepping: 2
BogoMIPS: 4416.01
Virtualization features:
Virtualization: VT-x
Hypervisor vendor: Microsoft
Virtualization type: full
Caches (sum of all):
L1d: 256 KiB (8 instances)
L1i: 256 KiB (8 instances)
L2: 2 MiB (8 instances)
L3: 16 MiB (1 instance)
Vulnerabilities:
Gather data sampling: Unknown: Dependent on hypervisor status
Itlb multihit: KVM: Mitigation: VMX disabled
L1tf: Not affected
Mds: Not affected
Meltdown: Not affected
Mmio stale data: Vulnerable: Clear CPU buffers attempted, no microcode; SMT Host state unknown
Retbleed: Mitigation; Enhanced IBRS
Spec rstack overflow: Not affected
Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl and seccomp
Spectre v1: Mitigation; usercopy/swapgs barriers and __user pointer sanitization
Spectre v2: Mitigation; Enhanced IBRS, IBPB conditional, RSB filling, PBRSB-eIBRS SW sequence
Srbds: Unknown: Dependent on hypervisor status
Tsx async abort: Not affected
```
### 測試一
設定一個長度為 16-bytes 的字串 `s`，該字串用來當作正確密碼。
我們要檢測函式 `memcmp` 在比較兩個字串的操作上是否為常數時間。
:::danger
注意書寫規範：
* 使用 lab0 規範的程式碼書寫風格，務必用 clang-format 確認一致
:::
>已修正
```c
uint8_t secret[16] = {0x2b, 0x7e, 0x15, 0x16, 0x28, 0xae, 0xd2, 0xa6,
0xab, 0xf7, 0x15, 0x88, 0x09, 0xcf, 0x4f, 0x3c};
uint8_t do_one_computation(uint8_t *data)
{
return (uint8_t)memcmp(secret, data, 16);
}
```
fix class 設定為 `s`，即正確密碼 ([白箱測試](https://en.wikipedia.org/wiki/White-box_testing))。
用 fix class 和 random class 各執行 `do_one_computation` 10000 遍，將範圍介在 `percentiles[0]` 和 `percentiles[99]` 之間的執行時間繪製成[累積分布函數](https://en.wikipedia.org/wiki/Cumulative_distribution_function)圖。
t 值設定為 4.5，超過 4.5 表示 fix class 和 random class 兩者的 timing distribution 有極大的可能不同。
`number_measurements` 設置為 `1e6`，這個值為每一次測試需要執行 `do_one_computation` 的次數。
下圖為執行 120 秒後，t 值的變化趨勢，每條線代表不同的百分位數。
### 測試二
同測試一，但 fix class 設定為 16 個位元皆為 `0` 的陣列 ([黑箱測試](https://en.wikipedia.org/wiki/Black-box_testing))。
下圖為執行 120 秒後，t 值的變化趨勢，每條線代表不同的百分位數。
下圖為執行 600 秒後，t 值的變化趨勢，每條線代表不同的百分位數。
### 測試三
fix class 設定為 16 個位元皆為 `0` 的陣列，`memcmp` 在位元組比較的過程中，不會一發現兩者相異馬上回傳結果，而是會逐位元組比較完指定長度之後再回傳結果。
:::danger
注意書寫規範：
* 使用 lab0 規範的程式碼書寫風格，務必用 clang-format 確認一致
:::
>已修正
```c
static int util_cmp_const(const void *a, const void *b, const size_t size)
{
const unsigned char *_a = (const unsigned char *)a;
const unsigned char *_b = (const unsigned char *)b;
unsigned char result = 0;
size_t i;
for (i = 0; i < size; i++) {
result |= _a[i] ^ _b[i];
}
return result; /* returns 0 if equal, nonzero otherwise */
}
```
下圖為執行 120 秒後，t 值的變化趨勢，每條線代表不同的百分位數。
Sign in with Wallet
Connect another wallet