2018q1 第 11 週測驗題 (上)

測驗 `1`

考慮以下程式碼:

#include <stdio.h>
struct empty { };
int main() {
    printf("%d\n", sizeof(void));
    printf("%d\n", sizeof(struct empty));
}

在 gcc 編譯時指定 -std=c99 (參照 C99 規範) 輸出為以下兩行:

1
0

從以下選項中挑出最接近的描述。
注意：同樣的程式碼經過 C 和 C++ 編譯器產生的執行檔有截然不同的輸出

作答區

A = ?

(a) 這程式之所以能夠通過編譯，是因為 GNU extensions;
(b) C99/C11 規格書對此已有正面描述，執行結果符合預期;
(c) 會有上述執行結果，顯示 gcc 編譯器內部的實作錯誤;

延伸題目:

在 C99 規格書和 gcc 手冊找到對應的描述，並充分解釋。透過 gcc 編譯時，加上選項 -pedantic
承上，推測規格書和手冊為何要如此設計;
嘗試用 C++ 編譯器 (如 g++ 和 clang++) 編譯上述程式，並且參照 C++ 規格書解釋為何如此;

測驗 `2`

考慮以下程式碼:

























#include <inttypes.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[]) {
    char *p, *q;
    uintptr_t pv, qv;
    {
        char a = 3;
        p = &a;
        pv = (uintptr_t) p;
    }
    {
        char b = 4;
        q = &b;
        qv = (uintptr_t) q;
    }
    if (p != q) {
        printf("%p is different from %p\n", (void *) p, (void *) q);
        printf("%" PRIxPTR " is not the same as %" PRIxPTR "\n", pv, qv);
    } else {
        printf("Surprise!\n");                                                                                                                                
    }
    return 0;
}

這段程式碼在 macOS 和 GNU/Linux 有著不同的執行輸出：

macOS 17.5.0 / x86_64 平台上用 clang-902.0.39.1 編譯，得到以下執行輸出

0x7ffee37fbabf is different from 0x7ffee37fbabe
7ffee37fbabf is not the same as 7ffee37fbabe

Ubuntu Linux 17.10 / x86-64 平台用 gcc-7.2.0 編譯得到以下執行輸出
```
Surprise!
```

從以下選項中挑出最接近的描述

作答區

B = ?

(a) 純粹只是 C 編譯器行為的落差，實務上不需特別留意;
(b) char a 和 char b 這兩個物件的生命週期僅分別在第 11 行和第 16 行有效，一旦超出 scope (作用範圍)，C 語言編譯器就會主動釋放物件，而透過 & (value-of) 運算子得到的地址自然就不再有效;
(c) char a 和 char b 這兩個物件的生命週期僅分別在第 11 行和第 16 行有效，一旦超出 scope (作用範圍) 仍操作物件的話，會導致 undefined behaviour;
(d) gcc 的實作不符合 C99/C11 規格描述;

提示：

在資訊安全的漏洞回報中，CWE-416: Use After Free 提及 dangling pointer 的影響
在 C11 規格書中 6.2.4:2 節提及物件的生命週期:

The lifetime of an object is the portion of program execution during which storage is guaranteed to be reserved for it. An object exists, has a constant address, and retains its last-stored value throughout its lifetime. If an object is referred to outside of its lifetime, the behavior is undefined. The value of a pointer becomes indeterminate when the object it points to (or just past) reaches the end of its lifetime.

延伸問題:

從 C99/C11 規格和編譯器行為，解釋上述程式的運作，並找到真實世界中類似的案例，最好是 Linux 核心程式碼相關
上方程式的 PRIxPTR 為何？在哪裡定義？

測驗 `3`

考慮以下 cmov (contional move) 指令的 C 程式實作:

void *cmoveq(int c, void *p1, void *p2) {
    void *r = p1;
    if (!c) r = p2;
    return r;
}

在 Intel Pentium Pro (也稱為 P6 微架構) 後引入新指令 cmoveq，於是上面的 C 程式等價於以下 x86_64 組合語言輸出:

cmoveq:
    testl   %edi, %edi
    cmoveq  %rdx, %rsi
    movq    %rsi, %rax
    retq

關鍵不僅在於程式碼的密度 (code density)，更在於少了分支，這對於密碼學的實作非常關鍵，依據 cryptocoding.net 的建議 Avoid branchings controlled by secret data，這可避免 timing attack。請改寫上述 C 程式，使其得以在常數時間內完成 cmoveq 等價功能。欲改寫的新程式碼如下：

#include <stdint.h>
void *cmoveq(int c, void *p1, void *p2) {
    uintptr_t mask = -(!!c);
    return  (void *) (((uintptr_t) C1) | ((uintptr_t) C2));
}

請補完上述 C1 和 C2 程式碼。

作答區

C1 = ?

(a) p1 | mask
(b) p1 ^ mask
(c) p1 & mask
(d) p1 | ~mask
(e) p1 ^ ~mask
(f) p1 & ~mask

C2 = ?

(a) p2 | mask
(b) p2 ^ mask
(c) p2 & mask
(d) p2 | ~mask
(e) p2 ^ ~mask
(f) p2 & ~mask

參考資料:

現在的編譯器最佳化已能夠分析特定程式模式，並以硬體指令替代，如 clang/llvm 可將上述 cmov 程式轉為對應包含 cmov 指令的組合語言，實驗方式為:

$ clang -S -Ofast -fomit-frame-pointer -fno-asynchronous-unwind-tables cmov.c

檢查編譯器產生的 cmov.s，確認裡頭包含 cmoveq 指令

延伸題目:

詳述 Timing attack 並且舉出和 Linux/Android 有關的真實案例;
參照 clmul，舉出密碼學裡頭 constant-time crypto 的實作，並佐以現代 Intel 處理器的加速指令作為探討對象，需要有演算法和效能分析;
研讀 Linus Torvalds 針對 cmov 的討論和 Branchless Conditionals (Compiler Optimization Technique)，之後再解讀 Linux Kernel Memory Barrier 和 cmov 指令相關的段落

2018q1 第 11 週測驗題 (上)

測驗 1

測驗 2

測驗 3

測驗 `1`

測驗 `2`

測驗 `3`