2018q1 Homework3 (list)

生日悖論

• 自我檢查事項
• 如何透過近似的運算式，估算上述機率計算呢？附上有效的 LaTeX 算式
• Birthday problem 對資訊安全的影響在哪些層面？
• 像是 Random Number Generator 這樣的產生器，是否能產生「夠亂」的亂數呢？

---

生日悖論是個相當有趣的問題，一年有 365 天，若每個人出生在任一天的機率相等，那某個人出生在某一天的機率為

$\frac{1}{365}$ ，是個相當微小的數字，乍一看還以為是計算

$1-(\frac{364}{365}{)}^n\ge 0.5$ ，錯誤計算後得出的結果是

$n\ge 252$ ，所以我們直覺上會認為在一個房間中要有足夠多人才會使得機率大於 50%，但是透過計算卻會發現房裡只要有超過 23 個人，其中兩人生日恰好相同的機率就會超過 50%。
所以若正確的列出算式的話則必須從下式求

$n$

$$P=1-\frac{364}{365}\ast \frac{363}{365}\ast \frac{362}{365}\ast ...\ast \frac{365-n}{365}\ge 0.5$$
相當複雜，可以用以下算式估算

$$n(p;d)\approx \sqrt{2d\ast ln(\frac{1}{1-p})}$$
計算

$n(0.5;365)$，會得出 22.494 相當接近於正確答案 23

Birthday problem 對資訊安全的影響在哪些層面？

所以可以看出問題的癥結點在於我們總是刻意忽略微小數值帶來的變化，將這個問題套用到資訊安全的領域上(尤其是密碼學)，可以發現不少利用此種弱點的攻擊，這被稱為 Birthday attack

其中一例是 hash function 的碰撞問題，以 SHA-256 為例，他會將任意大小的資料轉成 256-bit 大小的輸出，假設每個相異 hash 發生的機率相等，則我們可以預期每

$2^{256}$ 次 hash 必定發生一次碰撞，但是根據生日悖論的結論，可以計算出

$n(0.5;2^{256})\approx 2^{128}$，意思就是只要惡意的嘗試

$2^{128}$ 次 就有超過一半的機率發生一次碰撞，

像是 Random Number Generator 這樣的產生器，是否能產生「夠亂」的亂數呢？

---

linux 風格的 link-list

• 自我檢查事項:
• 為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？
• Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量
• GNU extension 的 typeof 有何作用？在程式碼中扮演什麼角色？
• 解釋以下巨集的原理

#define container_of(ptr, type, member)                            \
    __extension__({                                                \
        const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
        (type *) ((char *) __pmember - offsetof(type, member));    \
    })

• 除了你熟悉的 add 和 delete 操作，list.h 還定義一系列操作，為什麼呢？這些有什麼益處？
• LIST_POISONING 這樣的設計有何意義？
• linked list 採用環狀是基於哪些考量？
• list_for_each_safe 和 list_for_each 的差異在哪？“safe” 在執行時期的影響為何？
• for_each 風格的開發方式對程式開發者的影響為何？
• 提示：對照其他程式語言，如 Perl 和 Python
• 程式註解裡頭大量存在 @ 符號，這有何意義？你能否應用在後續的程式開發呢？
• 提示: 對照看 Doxygen
• tests/ 目錄底下的 unit test 的作用為何？就軟體工程來說的精神為何？
• tests/ 目錄的 unit test 可如何持續精進和改善呢？

---

為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？

function call 在 32/64 位元下的實作方式不盡相同，不過大致上會是下方的流程

• 儲存參數至 stack/reg 上
• 儲存下一個指令的地址至 stack
• 儲存 bp 至 stack
• 將 bp 修改為 sp
• 移動 sp 創造 stack frame
• function execute
• 將 sp 修改為 bp
• 還原 bp
• 還原下個指令至 ip

相較於直接展開 define 並操作，可以發現在一次的 function call 中會發生多次記憶體存取讓整體執行效率下降。

linux link-list 結構

linux 上的 link-list 結構和我們平常使用的稍有不同，若是由我定義可能會將資料和連結用的指標放在同一結構中，

struct list_node {
    int data;
    struct list_node *next;
    struct list_node *prev;
}

但在 linux 上的做法是，在 linked-list 結構中不定義額外的資料或指標，將其模組化，等到要使用時再將其放入儲存該 data 的結構中，透過 macro container_of(ptr, type, member) 來還原到原結構的起始位置。

struct list_head {
    struct list_head *next
    struct list_head *prev;
};