HackMD
dudect/src/dudect.h
dudect_config_t
typedef struct {
size_t chunk_size;
size_t number_measurements;
} dudect_config_t;
存儲測試設定
- chunk_size：每個測試區塊的大小。
- number_measurements：測試的執行次數。
ttest_ctx_t
typedef struct {
double mean[2];
double m2[2];
double n[2];
} ttest_ctx_t;
存儲 t-test 變數
- mean[2]：兩組數據 (class 0, class 1) 的平均值。
- m2[2]：變異數計算過程中的累積值 (Welford Method)。
- n[2]：測試樣本數量。
dudect_ctx_t
typedef struct {
int64_t *ticks;
int64_t *exec_times;
uint8_t *input_data;
uint8_t *classes;
dudect_config_t *config;
ttest_ctx_t *ttest_ctxs[DUDECT_TESTS];
int64_t *percentiles;
} dudect_ctx_t;
存儲測試數據
- ticks：存儲 CPU 週期計數 (cpucycles() 返回的數值)。
- exec_times：存儲函式執行時間 (after_ticks - before_ticks)。
- input_data：存儲測試輸入數據。
- classes：存儲輸入數據的分類 (class 0 or class 1)。
- ttest_ctxs：存儲不同的 t-test 結果。
- percentiles：存儲不同的 t-test 門檻值。
dudect_state_t
typedef enum {
DUDECT_LEAKAGE_FOUND=0,
DUDECT_NO_LEAKAGE_EVIDENCE_YET
} dudect_state_t;
dudect_init
int dudect_init(dudect_ctx_t *ctx, dudect_config_t *conf)
{
ctx->config = (dudect_config_t*) calloc(1, sizeof(*conf));
ctx->config->number_measurements = conf->number_measurements;
ctx->config->chunk_size = conf->chunk_size;
ctx->ticks = (int64_t*) calloc(ctx->config->number_measurements, sizeof(int64_t));
ctx->exec_times = (int64_t*) calloc(ctx->config->number_measurements, sizeof(int64_t));
ctx->classes = (uint8_t*) calloc(ctx->config->number_measurements, sizeof(uint8_t)); // 記錄測試的類別 (0: 雜訊, 1: 目標)
ctx->input_data = (uint8_t*) calloc(ctx->config->number_measurements * ctx->config->chunk_size, sizeof(uint8_t)); // 測試輸入資料
初始化 ctx，並分配記憶體
for (int i = 0; i < DUDECT_TESTS; i++) {
ctx->ttest_ctxs[i] = (ttest_ctx_t *)calloc(1, sizeof(ttest_ctx_t));
assert(ctx->ttest_ctxs[i]);
t_init(ctx->ttest_ctxs[i]);
}
初始化 Welch’s t-test 統計數據
ctx->percentiles = (int64_t*) calloc(DUDECT_NUMBER_PERCENTILES, sizeof(int64_t));
dudect 會篩選執行時間的前 DUDECT_NUMBER_PERCENTILES 個最快的數據，避免 OS 影響
assert(ctx->ticks);
assert(ctx->exec_times);
assert(ctx->classes);
assert(ctx->input_data);
assert(ctx->percentiles);
return 0;
assert() 確保記憶體分配成功，避免 malloc() 失敗
return 0 表示 dudect_init() 初始化成功
為甚麼使用 calloc 而不是 malloc 呢?
calloc v.s malloc
Allocates memory for an array of num objects of size and initializes all bytes in the allocated storage to zero.
If allocation succeeds, returns a pointer to the lowest (first) byte in the allocated memory block that is suitably aligned for any object type with fundamental alignment.
If size is zero, the behavior is implementation defined (null pointer may be returned, or some non-null pointer may be returned that may not be used to access storage).
calloc is thread-safe: it behaves as though only accessing the memory locations visible through its argument, and not any static storage.
A previous call to free, free_sized, and free_aligned_sized(since C23) or realloc that deallocates a region of memory synchronizes-with a call to calloc that allocates the same or a part of the same region of memory. This synchronization occurs after any access to the memory by the deallocating function and before any access to the memory by calloc. There is a single total order of all allocation and deallocation functions operating on each particular region of memory.
dudect_main
dudect_state_t dudect_main(dudect_ctx_t *ctx) {
prepare_inputs(ctx->config, ctx->input_data, ctx->classes);
measure(ctx);
bool first_time = ctx->percentiles[DUDECT_NUMBER_PERCENTILES - 1] == 0;
dudect_state_t ret = DUDECT_NO_LEAKAGE_EVIDENCE_YET;
if (first_time) {
// throw away the first batch of measurements.
// this helps warming things up.
prepare_percentiles(ctx);
} else {
update_statistics(ctx);
ret = report(ctx);
}
return ret;
}
Welch’s t-test 統計測試
static void t_push(ttest_ctx_t *ctx, double x, uint8_t clazz) {
assert(clazz == 0 || clazz == 1);
ctx->n[clazz]++;
/*
estimate variance on the fly as per the Welford method.
this gives good numerical stability, see Knuth's TAOCP vol 2
*/
double delta = x - ctx->mean[clazz];
ctx->mean[clazz] = ctx->mean[clazz] + delta / ctx->n[clazz];
ctx->m2[clazz] = ctx->m2[clazz] + delta * (x - ctx->mean[clazz]);
}
這是 Welford 方法 的實作，它可以在線更新均值和變異數。
x 是執行時間，根據它的 class (clazz=0 or 1)，更新 mean 和 variance。
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-value 來比較兩組數據的均值是否有顯著差異。
測量函式執行時間
static void measure(dudect_ctx_t *ctx) {
for (size_t i = 0; i < ctx->config->number_measurements; i++) {
ctx->ticks[i] = cpucycles();
do_one_computation(ctx->input_data + i * ctx->config->chunk_size);
}
for (size_t i = 0; i < ctx->config->number_measurements-1; i++) {
ctx->exec_times[i] = ctx->ticks[i+1] - ctx->ticks[i];
}
}
- 記錄執行前的 CPU 週期 (cpucycles())
- 執行測試函式 (do_one_computation())
- 記錄執行後的 CPU 週期
- 計算函式執行時間 (exec_times[i] = ticks[i+1] - ticks[i])
更新統計數據
static void update_statistics(dudect_ctx_t *ctx) {
for (size_t i = 10 /* discard the first few measurements */; i < (ctx->config->number_measurements-1); i++) {
int64_t difference = ctx->exec_times[i];
if (difference < 0) {
continue; // the cpu cycle counter overflowed, just throw away the measurement
}
// t-test on the execution time
t_push(ctx->ttest_ctxs[0], difference, ctx->classes[i]);
// t-test on cropped execution times, for several cropping thresholds.
for (size_t crop_index = 0; crop_index < DUDECT_NUMBER_PERCENTILES; crop_index++) {
if (difference < ctx->percentiles[crop_index]) {
t_push(ctx->ttest_ctxs[crop_index + 1], difference, ctx->classes[i]);
}
}
// second-order test (only if we have more than 10000 measurements).
// Centered product pre-processing.
if (ctx->ttest_ctxs[0]->n[0] > 10000) {
double centered = (double)difference - ctx->ttest_ctxs[0]->mean[ctx->classes[i]];
t_push(ctx->ttest_ctxs[1 + DUDECT_NUMBER_PERCENTILES], centered * centered, ctx->classes[i]);
}
}
}
這裡會丟棄前 10 次測試數據 (warming-up 階段)，然後將執行時間存入 t-test。
結果報告
static dudect_state_t report(dudect_ctx_t *ctx) {
#if DUDECT_TRACE
for (size_t i = 0; i < DUDECT_TESTS; i++) {
printf(" bucket %zu has %f measurements\n", i, ctx->ttest_ctxs[i]->n[0] + ctx->ttest_ctxs[i]->n[1]);
}
printf("t-test on raw measurements\n");
report_test(ctx->ttest_ctxs[0]);
printf("t-test on cropped measurements\n");
for (size_t i = 0; i < DUDECT_NUMBER_PERCENTILES; i++) {
report_test(ctx->ttest_ctxs[i + 1]);
}
printf("t-test for second order leakage\n");
report_test(ctx->ttest_ctxs[1 + DUDECT_NUMBER_PERCENTILES]);
#endif /* DUDECT_TRACE */
ttest_ctx_t *t = max_test(ctx);
double max_t = fabs(t_compute(t));
double number_traces_max_t = t->n[0] + t->n[1];
double max_tau = max_t / sqrt(number_traces_max_t);
// print the number of measurements of the test that yielded max t.
// sometimes you can see this number go down - this can be confusing
// but can happen (different test)
printf("meas: %7.2lf M, ", (number_traces_max_t / 1e6));
if (number_traces_max_t < DUDECT_ENOUGH_MEASUREMENTS) {
printf("not enough measurements (%.0f still to go).\n", DUDECT_ENOUGH_MEASUREMENTS-number_traces_max_t);
return DUDECT_NO_LEAKAGE_EVIDENCE_YET;
}
/*
* We report the following statistics:
*
* max_t: the t value
* max_tau: a t value normalized by sqrt(number of measurements).
* this way we can compare max_tau taken with different
* number of measurements. This is sort of "distance
* between distributions", independent of number of
* measurements.
* (5/tau)^2: how many measurements we would need to barely
* detect the leak, if present. "barely detect the
* leak" here means have a t value greater than 5.
*
* The first metric is standard; the other two aren't (but
* pretty sensible imho)
*/
printf("max t: %+7.2f, max tau: %.2e, (5/tau)^2: %.2e.",
max_t,
max_tau,
(double)(5*5)/(double)(max_tau*max_tau));
if (max_t > t_threshold_bananas) {
printf(" Definitely not constant time.\n");
return DUDECT_LEAKAGE_FOUND;
}
if (max_t > t_threshold_moderate) {
printf(" Probably not constant time.\n");
return DUDECT_LEAKAGE_FOUND;
}
if (max_t < t_threshold_moderate) {
printf(" For the moment, maybe constant time.\n");
}
return DUDECT_NO_LEAKAGE_EVIDENCE_YET;
}
主函式
dudect_state_t dudect_main(dudect_ctx_t *ctx) {
prepare_inputs(ctx->config, ctx->input_data, ctx->classes);
measure(ctx);
bool first_time = ctx->percentiles[DUDECT_NUMBER_PERCENTILES - 1] == 0;
dudect_state_t ret = DUDECT_NO_LEAKAGE_EVIDENCE_YET;
if (first_time) {
// throw away the first batch of measurements.
// this helps warming things up.
prepare_percentiles(ctx);
} else {
update_statistics(ctx);
ret = report(ctx);
}
return ret;
}
examples/simple/example.c
這個 example.c 程式使用 dudect 來測試 check_tag() 函式是否為 constant-time，也就是 不會根據輸入值影響執行時間。
example.c 的核心目標
- 定義一個目標函式 (check_tag())，並使用 memcmp() 來比較兩組 byte 陣列。
memcmp 是一個典型的非固定時間函數，因為它在發現第一個不匹配時會提前退出。這在論文的 III-B 節（Memory Comparison）中被證實為具有時序洩漏。
- 使用 dudect 來測試 check_tag() 是否為 constant-time。
- 隨機產生測試數據，並將其分類成不同的測試組 (class 0 和 class 1)。
- 透過 dudect_main() 反覆執行測試，直到偵測到時間洩漏 (leakage) 或測試結束。
/* target function to check for constant time */
int check_tag(uint8_t *x, uint8_t *y, size_t len) {
return memcmp(x, y, len);
}
- 這個函式使用 memcmp() 來比較 x 和 y 這兩個陣列是否相同。
- memcmp() 可能不是 constant-time，因為它會根據第一個不同的 byte 提早回傳結果，導致不同輸入的執行時間不同。
- dudect 會測試這個函式，看看它是否會根據輸入的不同影響執行時間。
模擬密鑰
#define SECRET_LEN_BYTES (512)
uint8_t secret[SECRET_LEN_BYTES] = {0, 1, 2, 3, 4, 5, 6, 42};
- 定義一個 secret 陣列，模擬一段 512 bytes 的密鑰 (secret key)。
- check_tag() 會與這個密鑰比較，看看不同的輸入是否會導致不同的執行時間。
/* this will be called over and over */
uint8_t do_one_computation(uint8_t *data) {
/* simulate totally bogus MAC check in non-constant time */
return check_tag(data, secret, SECRET_LEN_BYTES);
}
- 這個函式每次執行時，都會比較 data 和 secret。
- 這是 dudect 實際測試的目標函式，它會測量 check_tag() 的執行時間，來判斷是否為 constant-time。
- 論文 II-A 節提到，執行時間會針對不同輸入類別進行測量，這裡模擬了一個非固定時間的 MAC 檢查
void prepare_inputs(dudect_config_t *c, uint8_t *input_data, uint8_t *classes) {
randombytes(input_data, c->number_measurements * c->chunk_size);
for (size_t i = 0; i < c->number_measurements; i++) {
/* it is important to randomize the class sequence */
classes[i] = randombit();
if (classes[i] == 0) {
memset(input_data + (size_t)i * c->chunk_size, 0x00, c->chunk_size);
} else {
// leave random
}
}
}
- 產生隨機輸入 (randombytes() 產生隨機數據)。
- 將測試數據分類：
- class 0 (固定值)：全為 0x00，用 memset() 設定。
- class 1 (隨機數據)：保持隨機。
randombit 隨機分配類別（0 或 1）
- 這確保了 dudect 在測試時，能夠偵測函式在不同類別輸入 (class 0 vs. class 1) 下的執行時間是否一致。
run_test - 執行測試
int run_test(void) {
dudect_config_t config = {
.chunk_size = SECRET_LEN_BYTES,
#ifdef MEASUREMENTS_PER_CHUNK
.number_measurements = MEASUREMENTS_PER_CHUNK,
#else
.number_measurements = 500,
#endif
};
dudect_ctx_t ctx;
dudect_init(&ctx, &config);
/*
Call dudect_main() until
- returns something different than DUDECT_NO_LEAKAGE_EVIDENCE_YET, or
- you spent too much time testing and give up
Recommended that you wrap this program with timeout(2) if you don't
have infinite time.
For example this will run for 20 mins:
$ timeout 1200 ./your-executable
*/
dudect_state_t state = DUDECT_NO_LEAKAGE_EVIDENCE_YET;
while (state == DUDECT_NO_LEAKAGE_EVIDENCE_YET) {
state = dudect_main(&ctx);
}
dudect_free(&ctx);
return (int)state;
}
- 設定 dudect_config_t：
- chunk_size = 512 (SECRET_LEN_BYTES)SECRET_LEN_BYTES = 512，表示 每個測試區塊的大小是 512 bytes。 測試時，每次會提供 512 bytes 的輸入給 check_tag()。
- number_measurements = 500 → 測試 500 次。
- 初始化 dudect_ctx_t (測試上下文)
dudect_init(&ctx, &config);ctx 是 dudect 測試的上下文 (context) 它儲存 所有的測試數據、執行時間記錄、t-test 統計數據。- dudect_init 會 分配記憶體，準備 ctx 的資料結構、設定測試參數 (來自 config)、初始化 Welch’s t-test 統計數據。
- 重複執行 dudect_main()
- 直到 dudect_main() 偵測到時間洩漏 (leakage found) 或測試完成。
- 釋放記憶體
- dudect_free(&ctx);
run_test() 是 執行 constant-time 測試的主函式，回傳 0 或 1：
0 (DUDECT_NO_LEAKAGE_EVIDENCE_YET) → 尚未發現時間洩漏 (可能是 constant-time)。
1 (DUDECT_LEAKAGE_FOUND) → 發現時間洩漏 (可能不是 constant-time)。
進入點
int main(int argc, char **argv) {
(void)argc;
(void)argv;
run_test();
}
(void)argc; 和 (void)argv; 這部分不影響程式的執行邏輯，只是為了讓編譯器知道這些變數是「刻意不使用」，而不是「程式設計師忘記使用」。
若沒有這兩行可能會產生像是 warning: unused parameter ‘argc’ [-Wunused-parameter] 的警告
且 如果程式的未來版本可能會接受命令列參數，那麼保留 argc 和 argv 是個 良好的習慣
example.c 主要使用的 dudect.h 函式
| 函式 | 來自 | 用途 |
|---|---|---|
dudect_init() |
dudect.h |
初始化測試環境 |
dudect_main() |
dudect.h |
執行測試 |
dudect_free() |
dudect.h |
釋放記憶體 |
randombytes |
dudect.h |
產生隨機數據 |
randombit() |
dudect.h |
產生隨機 0 或 1 |
