〈Dude, is my code constant time?〉

相關名詞：
Sample mean

Introduce

Our tool does not rely on static analysis but on statistical analysis 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 、 ARM 有 systick
timer )

c) Environmental conditions

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

Step 2: Apply post-processing

在統計分析之前，可以對單獨測量值進行後處理。

a) Cropping
在較長的執行時間中，典型的時間分佈呈現 positively skewed (分佈平均值傾向中間偏左)。

b) Higher-order preprocessing
根據應用的統計測試，使用些高階預處理器 ( higherorder pre-processing ) 會有所幫助。

Step 3: Apply statistical test

用統計測試證明 '兩個時間分佈相等' 是錯的。

a) t-test

又稱 Student's test，論文中使用的 Welch’s t-test 為 t-test 的改良，當兩樣本有差異或不同大小時來的更可靠，此統計方法用於測試均值的等價性，若失敗就代表有一階 timing information leakage 。

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

b) Non-parametric tests

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