# 2019q3 Homework1 (review)
contributed by < `justapig9020` >
## 預期目標
- 隨堂測驗回顧
- 誠實面對自己
- 問題討論
## 作業要求
* 從 [課程簡介和注意須知](https://docs.google.com/presentation/d/1Wo22s5aYuuyry97-z2MMmUmdxhjD0wKTdhxIW5oqjvo/edit?usp=sharing), [第 1 週測驗題](https://hackmd.io/@sysprog/HksKVpUIr) 選出你感興趣的 3 個題組進行作答，並且回答附帶的「延伸問題」
* 應當包含 [課程簡介和注意須知](https://docs.google.com/presentation/d/1Wo22s5aYuuyry97-z2MMmUmdxhjD0wKTdhxIW5oqjvo/edit?usp=sharing) 的 Page 9 到 Page 16 裡頭的 C 語言程式設計議題
* 比照 [課前測驗參考解答: Q1](https://hackmd.io/s/ByzoiggIb) 和 [對 Linked List 進行氣泡排序](https://hackmd.io/s/BklGm1MhZ) 的模式來撰寫共筆，需要詳細分析自己的想法、參閱的材料 (包含 C 語言規格書的章節)，以及==進行相關實驗==
* 閱讀 [第一週課程進度](http://wiki.csie.ncku.edu.tw/sysprog/schedule) 所有材料，記錄所見所聞並提問，若有不能理解的部分，請標註出來。善用 HackMD 的語法 `:::info` 和 `:::` 標註你的提問
:::info
像是這樣標註提問
:::
## 參考資料閱讀
[參考資料閱讀筆記](https://hackmd.io/@justapig9020/2019q3_week1_info)
## 第ㄧ週 測驗``一``
### Code
```c
#include <stdio.h>
#define align4(x) (((x) + K) & (-4))
int main(void) {
int p = 0x1997;
printf("align4(p) is %08x\n", align4(p));
return 0;
}
```
### Question && Answer
預期程式輸出 ``align4(p) is 00001998``, 則``K =`` ?
- Ans: ``3``
---
### 想法與思考
題目希望能透過 ``align4()`` 這個巨集來將位址以 ``4`` 個單位對齊，由 ``bit mask`` 為 ``-4 (0xfffffffc)`` 便可了解，設待處理之位址為 ``n`` ，為了讓所有 ``n%4 != 0`` 之位址都能向前平移至下一個對齊點，因此需要加上對齊基準 ``-1`` 之數值，在此為 ``4-1 = 3`` 來滿足條件。
在透過 google 翻譯了解到題目是在討論關於位址對齊 (英文苦手 Orz )，首先我所想到的是剛入門資安領域時的一個問題:
``` asm
push ebp
mov ebp,esp
and esp,0xfffffff0
sub exp,0x10
```
:::danger
文字訊息==不要==用圖片去表達，不僅排版不一致，日後要搜尋檢索也困難
:notes: jserv
:::
這是個執行於 ``x86`` 環境下的[程式](https://pwnable.tw/challenge/#3)，透過 ``gdb`` 分析其 main function ，第 0, 1, 3 行十分容易理解，無非就是在對 stack 進行平移以利接下來函數的變數儲存，但是第二行的 ```and esp,0xfffffff0``` 卻百思不得其解，經過搜尋後得知是在對記憶體進行對齊。
::: success
由於 stack 是由記憶體高位址長向記憶體低位址，而本題目預設似乎是往高處長，所以在對 stack 進行 alingment 時不需要像本題目一樣在添加一個 offset 後再進行 and 運算。
:::
### 延伸題目
::: success
寫至這裡突然發現似乎跟測驗``二``有點類似，姑且算是測驗``一`` ``二``的混合（？
:::
```cpp
#define __ALIGN_KERNEL(x, a) __ALIGN_KERNEL_MASK(x, (typeof(x))(a) - 1)
#define __ALIGN_KERNEL_MASK(x, mask) (((x) + (mask)) & ~(mask))
#define ALIGN(x, a) __ALIGN_KERNEL((x), (a))
```
查看引用本巨集的檔案，並選擇其中之一
[drivers/net/ethernet/stmicro/stmmac/stmmac_main.c](https://github.com/torvalds/linux/blob/master/drivers/net/ethernet/stmicro/stmmac/stmmac_main.c) 研究。
並延伸如下之巨集
```cpp
#define STMMAC_ALIGN(x) __ALIGN_KERNEL(x, SMP_CACHE_BYTES)
```
所延伸出之巨集發現被使用於此 function:
```cpp
static int stmmac_open(struct net_device *dev)
{
...
priv->dma_buf_sz = STMMAC_ALIGN(buf_sz);
priv->rx_copybreak = STMMAC_RX_COPYBREAK;
...
}
```
此程式是被用於控制網路介面，於 ifconfig xxx up 時執行，而 ``priv->dma_buf_sz = STMMAC_ALIGN(buf_sz);`` 的作用為根據 buf_sz 初始化 DMA 的 Buffer size ，其中 ``STMMAC_ALIGN`` 是先將 buf_sz 做對齊，而根據 ``#define STMMAC_ALIGN(x) __ALIGN_KERNEL(x, SMP_CACHE_BYTES)`` 可以得知對齊之標準為 ==SMP_CACHE_BYTES== ，是根據不同硬體所改變的 ``cache`` 大小的數值，推測是為了盡可能使 buffer 可以一次被全部讀入 cache 中，換言之是為了增加記憶體存取效率所使用。
:::warning
ifconfig is deprecated in favor of iproute2 (the ip command) on GNU/Linux.
:notes: jserv
:::
此外根據[文章](https://blog.csdn.net/heliangbin87/article/details/75997189)所示，這邊應該同時要初始化 `tx`, `rx` 的 buffer 不知道為何新版本的程式似乎將其移除了。
### 記憶體對齊
#### 電腦的記憶單位
1. ``bit``
電腦最小的記憶單位，可以保存 0/1 。
3. ``byte``
一般來說 1 ``byte`` = 8 ``bits`` ，但也並非絕對。
- [DEFCON 25 cLEMENCy](https://github.com/legitbs/cLEMENCy) 為了 2017 年 DEFCON 專門開發的 1 ``byte`` = ==9== ``bits`` 架構。
5. ``word``
早期記憶體的最小存儲單位，根據系統架構所定義，目前主流架構多為 4 ``bytes`` 或 8 ``btyes``。
- 以 [IBM 160](https://en.wikipedia.org/wiki/IBM_System/360#Technical_description) 為分界，之前多使用 ``word`` 或 ``bit`` 定址，之後則多為 ``byte``。
- ``cache`` 是以 ``word`` 的整數倍從記憶體存取資料，若 ``word`` 能被定義成 ``byte`` 的 2 的次方倍，在記憶體定址上會較有效率。
#### 電腦的儲存結構
由於 cpu 與週邊設備時脈速度差異過大，因此往往需要透過中間設備逐漸加速以確保寶貴得 cpu 資源不會被浪費在等待資料傳輸上，因此記憶體與 cache 在此背景下誕生。
> [reference](https://sites.google.com/site/nutncsie10412/ge-ren-jian-jie/ji-yi-ti)
由此圖可以看出越靠近 ``cpu`` 的設備速度越快，但儲存成本上升也意味著空間越少，以目前的電腦運作模式是將需要長久儲存的資料放置於 ``Mass Memory`` ，正在執行的 ``Process`` 則會被載入 ``Main Memory`` ，當 ``cpu`` 要存取 ``Main Memory`` 中的資料時則會被依序載入各級 ``cache`` 中，最後再將資料放入 ``Register`` 中做運算。
#### cache 的運作方式
當 ``cpu`` 需要使用某個記憶體位址中的資料時，會先去尋找該位址的資料是否有被儲存於 ``cache`` 中，如果存在便能直接存取，若無法找到則會觸發 ``cache miss`` ， ``cache`` 必須要前往記憶體存取資料。
#### 記憶體對齊的優點
由於 ``cache`` 與記憶體之間的存取通常是以 ``word`` 為單位，因此若能將資料以 ``word`` 為單位對齊，就能確保資料在讀取時不會橫跨兩個 ``cache`` 之間，以免需要做複數次讀取才能將資料在 ``cpu`` ``cache`` ``memory`` 之間傳送。
:::danger
「確保資料在讀取時不會橫跨兩個 ``cache`` 之間」這樣的陳述有誤，請思考並修正。注意 cacheline 的行為，以及 cache 本質上是 sequential access，而 main memory 則是 random access，這兩者的落差又會對效能有何衝擊？ (hint: locality)
:notes: jserv
:::
以上面所提出的例子就是在規劃 ``buffer`` 時刻意以 ``cache`` 的 size 作為對齊依據，以確保資料盡可能的被存入同一 ``cache`` 中。
### 類似應用
藉由相同概念所實作的 branchless 四捨五入
```cpp
#include <stdio.h>
int r(int a)
{
return (a + 5) / 10 * 10;
}
```
---
## 第一週 測驗 ``三``
### Code
考慮以下 C 程式碼:
``` c
#include <stdbool.h>
bool func(unsigned int x) {
return x && ((x & (~x + 1)) == x);
```
可改寫為以下等價的程式碼:
``` c
bool func(unsigned int x) {
unsigned int unknown = 0;
while (x && unknown <= 1) {
if ((x & Z) == 1)
unknown++;
x >>= 1;
}
return (unknown == 1);
}
```
### Question && Answer
請補完程式。
``Z`` = ?
- Ans: ``1``
---
### 想法與思考
這個程式是在判別 ``x`` 是否為 2 的次方倍，若 ``x`` 為 2 的次方倍，則意味著 ``x`` 除最高一位元為 **1** 外，其他位元皆為 **0** (0b10...0) ，第二段城市正是利用這個特性去歷遍並檢測整個數中是否只有一個 **1** ，而第一段程式則是利用 ``bitwise`` 操作將整個檢測變成 ``branchless`` ，且運作時間也從 O(n) 縮減為 O(1) ，其原理是將 ``x`` 透過 ``not`` 運算並加一成為 ``x'`` ，如果 ``x`` 是二的倍數則 ``x'`` 會為 ``0b1...10...0`` 其中最低位的 1 正好會是 ``x`` 唯一的一的所在位置，之後再透過 ``and`` 運算(0b1...10...0 & 0b0...010...0)，結果便會跟 ``x`` 相等。
若 ``x`` 不為二的次方倍，則最後結果必定不相等。
前面與 ``x`` 的邏輯 ``and`` 運算是為了排除 ``x==0`` 的狀況。
### 延伸題目
``` c
int max (int a,int b)
{
return a^((a^b) & (-(b>a)));
}
```
由於 ``a`` **xor** ``a`` 會等於 ``0``，藉由這個原理，便可以透過用 cmp 的結果創造之 mask 控制 ``a`` **xor** ``0`` 或是 ``a^b`` 來得到要回傳的值。
#### setcc
Sets the destination register operand to ``0`` or ``1`` depending on the settings of status flags.
``setcc`` 是一系列指令，作用是向目標暫存器存入當前某特定 ``status flag`` 的數值，以此獲得比較結果
透過 ``setcc`` 指令，能使 ``cmp`` 並回傳結果的流程變成 ``O(1)``，透過 ``objdump`` 觀察發現這邊是使用 ``setl`` 。
``` asm
emp ecx, dword ptr [rbp-8]
setl dl
```
#### Constant time progeam
當程式存在分支時，表示其執行時期的特定某時間的狀態是難以預測的，目前能想到兩大缺點
1. 存在被 side channel attack 的風險
2. 在 Real time 環境下難以預測工作完成時間
:::warning
思考現代中央處理器的 branch predictor 原理
:notes: jserv
:::
##### 資料存取
某些資料存取，例如陣列，看似是常數時間，但是如果此資料大到足以導致 cache miss 或是 page fault 的話，依然是存在無法再嘗試時間內完成的風險。
#### Side channel attack
所謂 side channel atttack 是指不直接利用城市的邏輯漏洞，反而是利用程式邏輯，並透過觀測其他執行時期的行為來進行攻擊。
:::danger
注意偏好的程式碼縮排，4 spaces，` { ` 前後有空白
:notes: jserv
:::
```cpp
#include <stdbool.h>
bool my_strcmp(const char *c1, const char *c2)
{
while (*c1 | *c2) {
if (*c1 != *c2) {
return false;
}
c1++;
c2++;
}
return true;
}
````
透過此 function 進行字串比較時，此程式並不能保證在常數時間內執行，若此 function 被用於密碼比較時，會產生被 Time-based side channel attack 的風險，由於指令運算需要時間，因此進行不同次比較的時間是不同的，例如 "hello" 分別與 "hell" "he" 比較時所花費的時間是不同的，因此透過觀測執行時間，可以推估出當前當前正確的密碼位數。
以一只允許英文小寫長度為 ``n`` 的密碼系統來說，原本的複雜度為 $24^n$ 但若有此 side-channel attack 漏洞，猜測密碼的複雜度會大幅下降至 24*n 。
**實驗**
::: success
為了方便觀測與實作，在比較時刻意加入 sleep() 來擴大執行時間差異
:::
``` c
#include<stdbool.h>
#include<stdlib.h>
#include<stdio.h>
#include<time.h>
#include<unistd.h>
bool my_strcmp(char *c1)
{
char pw[] = "hi";
char *c2 = pw;
while(*c1|*c2){
sleep(1);
if(*c1!=*c2){
return false;
}
c1++;
c2++;
}
return true;
}
char* side_channel()
{
puts("== side ==");
char *c1;
int i,t,o;
bool ans;
c1 = malloc(10);
i = -1; // current char
t = -1; // last function execut time
o = 0; // running times
c1[0] = '\0';
do {
o++;
printf ("%d: %s\n", o, c1);
int ts, te;
ts = time(0);
ans = my_strcmp(c1);
te = time(0);
if (te-ts+1 > t){ // if find next pw
c1[++i] = 'a';
c1[i+1] = '\0';
t = te-ts+1;
}else{ // try next alphabet
c1[i]++;
}
}while(!ans);
c1[i]--;
printf("Times:%d\n", o);
return c1;
}
void is_z(char *c)
{
if(*c=='z'){
*c = 'a';
is_z(c+1);
}else{
(*c)++;
}
}
char* non_side_channel()
{
puts("== non-side ==");
char *c1;
int i=0, o=0, mod=26;
c1 = malloc(10);
c1[0] = 'a';
c1[1] = '\0';
while(!my_strcmp(c1)){
printf("%d: %s\n",++o , c1);
is_z(c1);
if(o%mod==0){
c1[++i] = 'a';
c1[i+1] = '\0';
mod *= 26;
}
}
printf("Times:%d\n", o);
return c1;
}
int main(void)
{
char *pw = side_channel ();
printf ("%s\n\n", pw);
pw = non_side_channel ();
printf ("%s\n", pw);
return 0;
}
```
```
== side ==
1:
2: a
...
18: hi
Times:18
hi
== non_side ==
1: a
...
241: gi
Times:241
hi
```
可以發現利用 side channel attack 可以大幅度縮減暴力破解時間。
---
## 課程說明 第 ``十一`` 頁
### Code
``` c
#include <stdio.h>
int main() { return (*******puts)("Hello"); }
```
### Question && Answer
能否編譯並執行呢？若可，為什麼呢？
### 想法與思考
Function 的名字在 c 語言中被稱之為 ``function designator`` ，根據劍橋字典， [designate](https://dictionary.cambridge.org/zht/%E8%A9%9E%E5%85%B8/%E8%8B%B1%E8%AA%9E/designate) 為
> to choose someone officially to do a particular job
以此推測 ``designator`` 意味著叫某人去做某事的某人，也就是說我們透過 ``function designator`` (某人) 叫程序 (某人) 去執行 function 的內容 (某事)，而 function designator 的型態即為該 function 的 return type。
摘錄 C99 規格書:
> C99 [ 6.3.2.1 ] A ``function designator`` is an expression that has ``function type``. ==Except== when it is ``the operand of the sizeof operator`` or ``the unary & operator``, a ``function designator`` with type ‘‘``function returning type``’’ is converted to an expression that has type ‘‘``pointer to function returning type``’’.
根據此敘述所示，首先 ``funciton designator`` 表示其擁有 ``funtion type`` 且 ``function designator`` 的型態為 ``function returning type``。
當一 ``function designator`` 有 ``function returning type`` 時被視為 ``pointer to function returning type``。
```
gdb-peda$ print func
$1 = {int ()} 0x4004d6 <func>
```
但有兩個例外，分別是被帶入 sizeof() 時，以及與一元運算子 `&` 進行運算。
首先關於一元運算子 `&` :
> C99 [6.5.3.2] The unary `&` operator yields the address of its operand. If the operand has type ‘‘type’’, the result has type ‘‘pointer to type’’. If the operand is the result of a unary `*` operator, neither that operator nor the & operator is evaluated and the result is as if both were omitted, except that the constraints on the operators still apply and the result is not an lvalue.
> C99 [6.5.3.2] The unary * operator denotes indirection. If the operand points to a function, the result is a function designator
首先我們能得知若對型態為 `type` 運算元進行一元運算子 `&` 運算，則會得到型態為 pointer to `type` 的結果， 若運算元進行過一元運算子 `*` 運算，則 `&` `*` 會相互抵銷。
若對 ``pointer to a function`` 進行一元運算子 `*` 運算，則會返回 ``function designator``
```
gdb-peda$ print *func
$2 = {int ()} 0x4004d6 <func>
```
> C99 [6.5.3.2] The operand of the unary & operator shall be either a function designator, the result of a [] or unary * operator, or an lvalue that designates an object that is not a bit-field and is not declared with the register storage-class specifier.
由上述可知由於 ``function designator`` 經過一元運算子 `&` 運算後結果為 ``pointer to function type``。
對 ``pointer to a function`` 進行一元運算子 `*` 運算，則會返回 ``function designator``
由於 ``function designator`` 為 ``function returnng type`` 因此經過一次一元運算子 `&` 運算後的 ``pointer to function returning type`` 並不被視作 ``function designator`` 又因為此狀態下的 ``pointer to function returning type`` 是只保存在暫存器中，因此不符合 ``is not declared with the register storage-class specifier`` ，最終導致 ``Syntax error``。
```
gdb-peda$ print &func
$3 = (int (*)()) 0x4004d6 <func>
gdb-peda$ print &*func
$4 = (int (*)()) 0x4004d6 <func>
gdb-peda$ print *&*func
$5 = {int ()} 0x4004d6 <func>
gdb-peda$ print &&*func
A syntax error in expression, near `&&*func'.
```
最後來探討一下 function call 這件事
> C99 [6.5.2.2] The expression that denotes the called function(80) shall have type pointer to function returning void or returning an object type other than an array type.
> 80) Most often, this is the result of converting an identifier that is a function designator.
滿足 function call 的必要條件是，你所 call 的 function 必須是一個 ``pointer to function returning type`` ，也就是說一個 function call 可以被視為
``identifier with pointer to function returning type`` ==(== ``argument list`` ==)==
這邊分成三種情況討論。
1. func()
- 由於 func 代表 func(){} (我猜是因為能在 symbol table 中找到) 因此 func 具有 function type ，因此 func 是 ``function designator`` ，因此滿足 function call 的首要條件，再加上 ``()`` 就能進行 function call。
3. *func()
- 由於 func 代表 func(){} (我猜是因為能在 symbol table 中找到) 因此 func 具有 function type ，因此 func 是 ``function designator`` ，又當 ``function designator`` 是 ``function returning type`` 時被視作 ``pointer to function return type`` ，當一元運算子 ``*`` 與 ``pointer to function`` 進行運算時會得到結果為 ``function designator`` ，因此滿足 function call 的首要條件，再加上 ``()`` 就能進行 function call。
5. &func()
- 由於 func 代表 func(){} (我猜是因為能在 symbol table 中找到) 因此 func 具有 function type ，因此 func 是 ``function designator`` ，由於 ``function designator`` 經過一元運算子 `&` 運算後結果為 ``pointer to function type`` ，因此滿足 function call 的首要條件，再加上 ``()`` 就能進行 function call。
透過以下實驗觀察
::: success
此程式必須在編譯時加入 -z execstack 來關閉 NX 保護才能正確執行。
:::
```cpp
char code1[] = "\x31\xc0\x48\xbb\xd1\x9d\x96\x91\xd0\x8c\x97\xff\x48\xf7\xdb\x53\x54\x5f\x99\x52\x57\x54\x5e\xb0\x3b\x0f\x05";
int main(void)
{
char code2[] = "\x31\xc0\x48\xbb\xd1\x9d\x96\x91\xd0\x8c\x97\xff\x48\xf7\xdb\x53\x54\x5f\x99\x52\x57\x54\x5e\xb0\x3b\x0f\x05";
((void(*)())code1)();
((void(*)())code2)();
((void())code1)();
// fun.c:7:6: error: cast specifies function type
// ((void())code1)();
code2();
// fun.c:5:10: note: declared here
// char code2[] = ....
return 0;
}
```
我們透過字元陣列的方式寫入可執行的資料，再透過 ``function call`` 來執行他們，例如[這個程式](http://shell-storm.org/shellcode/files/shellcode-806.php)就是在測試 shell code ，前兩組 function call 透過強制轉型成 ``pointer to function returning type`` 的方式成功執行，而第三個因為無法被強制轉型成 ``function returning type`` 而失敗，最後一組因為在進行 function call 時， identifier type 並不為 ``pointer to funtion returning type`` 而失敗。
::: success
func:
- type: function returning type
- value: address of function
&func:
- type: pointer to function returning type. e.g. `int (*)()``
- value: address of function
*func:
- type: function returning type. e.g. ``int ()``
- value: address of function
:::
::: success
argument / parameter
之前一直搞不懂兩者之間的差異，參照 c 語言規格書後發現， argument 指的是 function call 時提供的參數，而 parameter 則是 function 所預期傳入的參數
:::
::: success
sizeof 是一個 operator
:::
:::danger
摘錄 C 語言規格書對應描述並論述
:notes: jserv
:::
~~根據 C 語言規格書， ＊、& 兩個都是右結合，且跟 ``指向 function 的東西``進行運算結果會是 ``function designator``，由於原本的 function designator 已經指向 function 的 address ，因此在運算後依然是 function designator，這就有點像對 $e^x$ 微分依然是 $e^x$ 一樣，不論經過幾次運算依舊回到原點。~~
::: success
或許能在 compiler 的實作中找到驗證
:::
###### tags: `sysprog2019`
Sign in with Wallet
Connect another wallet