# Dude, is my code constant time?

## Introduction
由於計時攻擊的興起，作者提到下列不同的工具可以確認執行原始碼時，是否為常數時間。但是這些工具都需要建立硬體模型，這不是個簡單的任務，尤其CPU製造商不會公布太多CPU的硬體細節。因此提出`dudect`，利用旁道攻擊的概念，透過統計分析運行時間是否為常數時間。這樣的方法就無需建立硬體模型並且可以運行在每一個不同的硬體上。

- ctgring: Valgrind的擴充功能
- Flow-tracker
- ctverif

## 方法
簡而言之，本論文提供了一種可以偵測出程式是否洩漏運行時間的方法

### Step 1: 測量執行時間
分別使用兩種不同的資料集重複的測量程式的運行時間。
- Class definition: 一種是固定輸入的資料集，另一種則是隨機輸入的資料集。固定輸入的資料集通常包含極端情況
- Cycle counters: 大部分的CPU都提供了這個功能，通常比起測量時間還要準確
- Environmental conditions: 為了降低環境造成的影響，會隨機選擇不同的資料集，資料集會在開始測量時間之前完成

### Step 2: 後處理
在每一次測量結束之後，統計分析之前，需要對資料做以下處理

- Cropping: 典型的時間分布呈現正偏態，朝著較長的執行時間方向，這可能是由測量工具、主程序被作業系統或其他無關活動中斷所引起的。這時候我們可以將超過最大值的測量值當作最大值或者乾脆丟棄這筆測量值
- Higher-order preprocessing: 根據所應用的統計測試，對資料做對應的前處理

### Step 3: 統計檢定
針對兩種類別的資料集，嘗試反駁虛無假說"兩者時間分布相同"，可以用以下檢定方式

- t-test: T檢定，判斷在給定的信心區間內是否有顯著差異
- Non-parametric tests: 使用符號(正負)或排序(大小順序)取代測量數值，或使用各分類的次數以進行統計分析。 適用於類別、序位尺度資料分析與資料分布未知的情況。

## 成果

### 實作
[dudect](https://github.com/oreparaz/dudect)僅使用約300行C程式碼。實驗運行在2015 MacBook並且透過LLVM/clang-703.0.31 `-O2`選項編譯。每個實驗都執行了120秒。

- Pre-processing: 丟棄大於$p$百分位的測量值。這是因為測量值特別大的時候通常不是由於程式碼引起的，所以主要會將檢定的焦點集中在測量值較小的部分
- Statistical test: 使用t-test來檢定是否為常數時間

### 記憶體的比較
第一個研究的目標是判斷常用的記憶體比較功能執行時間是否為常數時間。記憶體比較功能常出現在密碼驗證或者訊息驗證。
因此，基於`memcmp`實作一個直觀的16位元記憶體比對程式作為[smoke test](https://seanacnet.com/website-related/smoke-testing/)。

## Trace `dudect`
發現 `update_statistics` 會忽略前10個以及最後一個測量值，在 `update_statistics` 之前會根據執行時間 `exec_times` 從小到大做排序。

### Compare `lab0-c/dudect`
`lab0-c`中的實作沒有對測量值做排序，我想應該要做完排序之後再丟棄離群值來增強檢定的穩健性。並且在測試數量超過10000筆時對測量值做Centered product前處理