# 2019q1 第 3 週測驗題 (上)
:::info
目的: 檢驗學員對 C 程式設計的認知
:::

---

### 測驗 `1`

考慮到 [memcmp](http://man7.org/linux/man-pages/man3/memcmp.3.html) 一種實作如下: (行為和 ISO C90 有出入)

#include <stdint.h>
#include <stddef.h>
int memcmp(const uint8_t *m1, const uint8_t *m1, size_t n) {
    for (size_t i = 0; i < n; ++i ) {
        int diff = m1[i] - m2[i];
        if (diff != 0) return (diff < 0) ? -1 : +1;
    }
    return 0;
}

我們可能因此承受 [information leakage](https://en.wikipedia.org/wiki/Information_leakage) 的風險，於是著手避免使用 conditional branching 一類的指令，從而避免 [side-channel attack](https://en.wikipedia.org/wiki/Side-channel_attack)。

為了避免 conditional branch 指令的出現，我們可將 `(res > 0) - (res < 0)` 替換為 `((res - 1) >> 8) + (res >> 8) + 1`。隨後我們實作下方功能等價但避免 branch 的 `memcmp`:

#include <stdint.h>
#include <stddef.h>
int cst_memcmp(const void *m1, const void *m2, size_t n) {
    const uint8_t *pm1 = (const uint8_t *) m1 + n;
    const uint8_t *pm2 = (const uint8_t *) m2 + n;
    int res = 0;
    if (n) {
        do {
            int diff = *--pm1 - *--pm2;
            res = (res & ((X & ~diff) >> 8)) | Y;
        } while (pm1 != m1);
    }
    return ((res - 1) >> 8) + (res >> 8) + 1;
}

注意: 在 Linux 核心內部的實作方式可見:
* [[PATCH] crypto_memcmp: add constant-time memcmp](https://www.spinics.net/lists/linux-crypto/msg09542.html)
* [Re: [PATCH] crypto_memcmp: add constant-time memcmp](https://www.spinics.net/lists/linux-crypto/msg09551.html)

請補完程式碼。

==作答區==

X = ?
* `(a)` diff
* `(b)` (diff + 1)
* `(c)` (diff - 1)
* `(d)` 1
* `(e)` 0

Y = ?
* `(a)` diff
* `(b)` (diff + 1)
* `(c)` (diff - 1)
* `(d)` 1
* `(e)` 0

:::success
延伸問題:
1. 解釋上述程式的原理，需要從機率統計的觀點分析;
* 為何不能用事先計算好的表格呢？ (提示: cache 的影響)
* 如何驗證程式正確以及 constant-time 呢？
3. 研讀下方論文並解說:
* [Remote timing attacks are practical](https://crypto.stanford.edu/~dabo/abstracts/ssl-timing.html)
* [A Lesson In Timing Attacks (or, Don't use MessageDigest.isEquals)](http://codahale.com/a-lesson-in-timing-attacks/)
4. 在 Linux 核心找到這類 constant-time 的操作程式碼，予以解說和設計實驗;
:::

---

### 測驗 `2`

考慮以下計算平方根的程式:

#include <stdint.h>
  
/* The algorithm uses the property that computing x² is trivial compared to
 * sqrt. It will search the biggest x so that x² <= v, assuming we compute
 * sqrt(v).
 */
int32_t sqrt_I2I(int32_t v) {
    uint32_t r = v;           // r = v - x²
    uint32_t b = 0x40000000;  // a²
    uint32_t q = 0;           // 2ax
    while (b > 0) {
        uint32_t t = q + b;  // t = 2ax + a²
        q >>= 1;             // if a' = a/2, then q' = q/2
        if (r >= t) {        // if (v - x²) >= 2ax + a²
            r -= t;          // r' = (v - x²) - (2ax + a²)
            q += b;          // if x' = (x + a) then ax' = ax + a²,
                             // thus q' = q' + b
        }
        b >>= 2;  // if a' = a/2, then b' = b / 4
    }
    return q;
}

該函式利用 (x + a)^2^ = x^2^ + 2ax + a^2^ 漸進找出平方根。不過上面的程式僅能處理整數，我們引入 [fixed point](http://www-inst.eecs.berkeley.edu/~cs61c/sp06/handout/fixedpt.html) 來表達浮點數，改寫程式碼如下:

/* A fixed point is a 32 bit value with the comma between
 * the bits 15 and 16, where bit 0 is the less significant bit of the value.
 * FIXME: Larger numbers might cause overflow and rounding error.
 */
typedef int32_t fixed;

fixed sqrt_I2F(int32_t v) {
    if (!v) return 0;
    uint32_t r = v;
    uint32_t b = 0x40000000;
    uint32_t q = 0;
    while (b > 0) {
        uint32_t t = q + b;
        if (r >= t) {
            r -= t, q = t + b;
        }
        Q;
    }
    if (r >= q) ++q;
    return q;
}

請補完程式。

==作答區==

Q = ?

* `(a)` b >>= 2
* `(b)` r >>= 1
* `(c)` r <<= 1
* `(d)` b >>= 1
* `(e)` b <<= 1
* `(f)` r >>= 1, b <<= 1
* `(g)` r <<= 1, b >>= 1

:::success
延伸問題:
1. 解釋上述程式碼運作原理，並找出類似的開放原始碼程式;
2. 上述 `sqrt_I2F` 函式存在 overflow 風險，請提出修正方案並驗證;
:::

---

### 測驗 `3`

考慮以下 linked list 程式:

#include <stddef.h>
struct node {
    int data;
    struct node *next;
} *head;

void insert(struct node *newt) {
    struct node *node = head, *prev = NULL;
    while (node != NULL && node->data < newt->data) {
        prev = node;
        node = node->next;
    }
    newt->next = node;
    if (prev == NULL)
        head = newt;
    else
        prev->next = newt;
}

可透過以下 pointer to pointer 改寫 `insert` 函式，功能等價但更簡潔，如下:

void insert(struct node *newt)
{
    struct node **link = &head;
    while (*link && A)
        B;
    newt->next = *link;
    *link = newt;

請補完程式碼。

==作答區==

A = ?
* `(a)` *link->data < newt->data
* `(b)` (*link)->data < newt->data
* `(c)` **link->data < newt->data
* `(d)` (link)->data < newt->data

B = ?
* `(a)` *link = *link->next
* `(b)` (*link) = (*link)->next
* `(c)` link = (*link)->next;
* `(d)` link = &(*link)->next;

:::success
延伸問題:
在 Linux 核心找出運用類似的手法的程式碼並解說
:::

---