# 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](https://gcc.gnu.org/onlinedocs/gcc/C-Extensions.html);
* `(b)` C99/C11 規格書對此已有正面描述，執行結果符合預期;
* `(c)` 會有上述執行結果，顯示 gcc 編譯器內部的實作錯誤;

:::success
延伸題目:
1. 在 C99 規格書和 gcc 手冊找到對應的描述，並充分解釋。透過 gcc 編譯時，加上選項 `-pedantic`
2. 承上，推測規格書和手冊為何要如此設計;
3. 嘗試用 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 規格描述;

提示：
1. 在資訊安全的漏洞回報中，[CWE-416: Use After Free](https://cwe.mitre.org/data/definitions/416.html) 提及 dangling pointer 的影響
2. 在 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.

:::success
延伸問題:
1. 從 C99/C11 規格和編譯器行為，解釋上述程式的運作，並找到真實世界中類似的案例，最好是 Linux 核心程式碼相關
2. 上方程式的 `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 微架構](https://en.wikipedia.org/wiki/P6_(microarchitecture))) 後引入新指令 `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](https://cryptocoding.net/index.php/Coding_rules#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

參考資料:
* [New P6 OpCodes: CMOV](http://www.rcollins.org/p6/opcodes/CMOV.html)
* [Compilers and constant-time code](http://www.reparaz.net/oscar/misc/cmov.html)
* [Linus Torvalds 針對 cmov 的討論](http://yarchive.net/comp/linux/cmov.html)
* [Why Constant-Time Crypto?](https://www.bearssl.org/constanttime.html)
* [Binary Search *eliminates* Branch Mispredictions](https://www.pvk.ca/Blog/2012/07/03/binary-search-star-eliminates-star-branch-mispredictions/)

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

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

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

:::success
延伸題目:
1. 詳述 Timing attack 並且舉出和 Linux/Android 有關的真實案例;
2. 參照 [clmul](https://hackmd.io/s/HkQfalnpe)，舉出密碼學裡頭 constant-time crypto 的實作，並佐以現代 Intel 處理器的加速指令作為探討對象，需要有演算法和效能分析;
3. 研讀 [Linus Torvalds 針對 cmov 的討論](http://yarchive.net/comp/linux/cmov.html) 和 [Branchless Conditionals (Compiler Optimization Technique)](http://www.blueraja.com/blog/285/branchless-conditionals-compiler-optimization-technique)，之後再解讀 [Linux Kernel Memory Barrier](https://www.kernel.org/doc/Documentation/memory-barriers.txt) 和 cmov 指令相關的段落
:::