---
tags: 論文閱讀, C
---
# 論文閱讀：Dude, is my code constant time?

[論文連結](https://eprint.iacr.org/2016/1123.pdf)
[dudect Github](https://github.com/oreparaz/dudect)

### Introduction
[Side-channel attack](https://en.wikipedia.org/wiki/Side-channel_attack) 是一種利用系統實作上的特性，而不是用密碼學演算法本身的攻擊，其中 [Timing attacks](https://en.wikipedia.org/wiki/Timing_attack) 是其中一種很常見的手法，可以透過演算法的執行時間進而破解，舉例來說，一個判斷密碼是否正確的算法是從第一個字母開始逐一比對，一遇到不一樣的就馬上返回錯誤，那我們就可以透過多次嘗試，並觀察時間來判斷輸入是否正確。

現今也有一些評估的工具了，像是 `Valgrind` 的延伸 `ctgrind`，還有 `ctverif` 透過靜態的程式分析，但是有一些共同的缺陷是這些方法需要對硬體建模，但是困難的是 CPU 製造商通常不會給太多細節的資訊。

這篇論文的貢獻是，透過自己開發的 `dudect`，一個透過統計分析的程式判斷程式是否是 constant-time 在給定的平台之下。與其他工具透過靜態分析的手法不同，`dudect` 是透過 timing leakeage detection tests 對執行時間的統計分析，就可以避開底層硬體的限制，不侷限某特定 CPU 硬體平台。

#### A. Step 1: Measure execution time

- a) Classes definition:
- 給定兩種不同類別的輸入資料，重複對方法進行測量，最常見的就是 fix-vs-random tests
- 第一種資料是固定一個常數的值，第二種資料則是每次測量都隨機產生。
- 第一種資料通常會給定一個特別的值，來觸發 corner-case(such as low-weight for arithmetic operations)
- b) Cycle counters:
- 現今的 CPU 提供的 cycle counters 可以很精準的獲得執行的時間。
- c) Environmental conditions:
- 為了減少環境的差異，每次測量都會對應隨機的輸入值分類。

#### B. Step 2: Apply post-processing
在統計分析之前需要做一些後處理。
- a) Cropping:
- 典型的時間分布會呈現正偏態(positive skew)，可能是 OS 或是外部活動導致測量誤差(measurement artifacts)，可以透過裁減(crop)掉一些超過 threshold 的測量結果。
- b) Higher-order preprocessing:
- 統計測試可以透過 high-order preprocessing 得到更加的分析結果。例如 centered product 、mimicking higher-order DPA attacks。

#### C. Step 3: Apply statistical test
運用統計學試著推翻虛無假說 (null hypothesis)，這邊的虛無假說就是「兩個時間分布是相同的」，底下參考 [WeiCheng14159](https://hackmd.io/@WeiCheng14159/HyAa0RTVP#%E8%AB%96%E6%96%87%E7%A0%94%E8%AE%80)。

- Hypothesis Testing 簡介：
- Null hypothesis (H0) 是我們想要測定的假說
- Alternative hypothesis (H1) 是 H0 的反面
- 結果的判定：
- Reject Null Hypothesis 代表我們在統計上有足夠的證據，證明 H0 是錯的，故 H1 是對的
- Fail to reject Null Hypothesis 代表在統計上沒有足夠的證據，證明 H0 是錯的
- a) t-test:
- 一個很簡單方便實作的是 Welch’s t-test，這個統計測試兩個平均數是否相同，
- b) Non-parametric tests:(無母數統計分析)
- 一個很常見的方法是 Kolmogorov-Smirnov，好處是其依賴比較少關於底層分布的假設，缺點是可能收斂的比較慢或是需要更多樣本。
- Welch’s t-test
- 先簡介 [Student's t-test](https://en.wikipedia.org/wiki/Student%27s_t-test) 就是抽樣下的常態分佈，常用來比較兩組樣本的平均值是否有差異。
- [Welch's t-test](https://en.wikipedia.org/wiki/Welch%27s_t-test) 則是在兩個樣本的變異數不相等的情況下會更加的準確。
- 定義：
* $\mu_1$：`class 1` 真正的執行時間的平均值（未知）
* $\mu_2$：`class 2` 真正的執行時間的平均值（未知）
* $\sigma_1$：`class 1` 採樣的執行時間的標準差（已知）
* $\sigma_2$：`class 2` 採樣的執行時間的標準差（已知）
* $n_1$：`class 1` 的樣本數（已知）
* $n_2$：`class 2` 的樣本數（已知）
* $\bar x_1$：`class 1` 採樣的的執行時間的平均值（已知）
* $\bar x_2$：`class 2` 採樣的的執行時間的平均值（已知）
* $H_0$：$\mu_1 - \mu_2 = 0$ 假設`class 1` 和`class 2` 的平均執行時間相等，亦為 ==『兩個 `class` 的執行時間分佈是相同的』==
* $H_1$：$\mu_1 - \mu_2 \neq 0$ 假設`class 1` 和`class 2` 的平均執行時間並不相等，亦為 ==『兩個 `class` 的執行時間分佈是不同的』==
* 計算檢定統計量 $t = \frac{\bar x_1 - \bar x_2}{\sqrt{\frac{\sigma_1^2}{n_1}+ \frac{\sigma_2^2}{n_2}}}$
* $t$ 越接近 0 代表兩組數據的差異越小
* lab0 實作上只有到這裡，然後直接檢查 $t$ 是否大於 `t_threshold_moderate`

### 實作細節

`lab0-c` 的 Welch’s test 測試項目有兩個:

- `is_insert_tail_const()`: 用來測試將字串加到 Queue 尾端的執行時間是否能在常數時間完成。
- `is_size_const()`: 用來測試取得 Queue 大小時間是否能在常數時間完成。

每個測項又細分兩個階段:

- Pre-processing: 主要測量待測物 (給定的程式碼) 的執行時間 (CPU cycle)，其步驟如下:
- 兩種產生 Queue 方式 (即對照 Welch’s Test 所需兩組取樣資料):
- Queue 大小 = 0 $→$ 論文提及的 `fix class`
- Queue 大小 = n (隨機產生)，並插入 n 個相同的隨機字串至 Queue 開頭 (字串長度=7bytes, 加上結束字元 `'\0'` 則為 8bytes) $→$ 論文提及的 `random class`
- 執行待測物 (`is_insert_tail_const()` 或 `is_size_const()`)，並記錄執行時間 (CPU cycles)
- Statistical test: 將所記錄的CPU執行時間 (CPU cycles) 套用如下 Welch’s test 公式，用以計算t value。可對照 lab0-c 原始碼的 `t_push()` 與 `t_compute()`。其所計算得出 t value 就可用來判斷測試項目是否在常數時間完成。

在 `fixture.c` 當中可以看到，最後會根據 t 值大小來判定是否為 constant time。

/* threshold values for Welch's t-test */
#define t_threshold_bananas                                                  \
    500                         /* Test failed with overwhelming probability \
                                 */
#define t_threshold_moderate 10 /* Test failed */

if (max_t > t_threshold_bananas) {
    return false;
} else if (max_t > t_threshold_moderate) {
    return false;
} else { /* max_t < t_threshold_moderate */
    return true;
}