# 〈Dude, is my code constant time?〉
相關名詞：
[Sample mean](https://en.wikipedia.org/wiki/Sample_mean_and_covariance)

## Introduce
Our tool does not rely on static analysis but on [statistical analysis](https://zh.wikipedia.org/wiki/%E9%9D%9C%E6%85%8B%E7%A8%8B%E5%BA%8F%E5%88%86%E6%9E%90) of execution timing measurements on the target platform. In this way, we circumvent the problem of modeling the underlying hardware.
## 實做方法 : TIMING LEAKAGE DETECTION
對執行時間進行洩漏檢測。測量兩個輸入資料的執行時間 (execution time) ，然後檢查兩者時間分佈在統計上是否有不同 (statistically different)。
### Step 1: Measure execution time
重複對兩個不同輸入資料測量其加密函式 (cryptographic function) 的執行時間。

a) Classes definition

在 fix-vs-random leakage detection test 中給定兩種不同輸入類別
- 固定資料 (The fixed value might be chosen to trigger certain “special” corner-case processing )
- 隨機資料

b) Cycle counters

現代 CPU 中都提供 cycle counters 的功能 ( x86 有 [TSC register](https://en.wikipedia.org/wiki/Time_Stamp_Counter) 、 ARM 有 [systick
timer](https://www.keil.com/pack/doc/CMSIS/Core/html/group__SysTick__gr.html) )

c) Environmental conditions

為了最小化環境變化對結果造成的影響，每次測量都對應一個隨機選擇的 class。

### Step 2: Apply post-processing
在統計分析之前，可以對單獨測量值進行後處理。

a) Cropping
在較長的執行時間中，典型的時間分佈呈現 [positively skewed](https://en.wikipedia.org/wiki/Skewness) (分佈平均值傾向中間偏左)。

b) Higher-order preprocessing
根據應用的統計測試，使用些高階預處理器 ( higherorder pre-processing ) 會有所幫助。
### Step 3: Apply statistical test
用統計測試證明 '兩個時間分佈相等' 是錯的。

a) t-test

又稱 [Student's test](https://zh.wikipedia.org/zh-tw/%E5%8F%B8%E5%BE%92%E9%A0%93t%E6%AA%A2%E5%AE%9A)，論文中使用的 [Welch’s t-test](https://en.wikipedia.org/wiki/Welch's_t-test) 為 t-test 的改良，當兩樣本有差異或不同大小時來的更可靠，此統計方法用於測試均值的等價性，若失敗就代表有一階 timing information leakage 。

當 t-test 與 cropping pre-processing 結合時，不僅在測試均值是否相等( equality of means )，還測試更高階的統計情境，因 cropping 是非線性的轉換。

b) Non-parametric tests

優點在於依賴更少的假設在 underlying distributions 上，缺點為收斂的更慢，需要更多的樣本。