---
tags: Linux2020
---
# 2020q3 Homework1 (lab0)
contributed by <`YLowy`>
## 開發環境
```
$ uname -a
Linux ylowy-X550VX 5.4.0-47-generic #51-Ubuntu SMP Fri Sep 4 19:50:52 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux
$ gcc --version
gcc (Ubuntu 9.3.0-10ubuntu2) 9.3.0
```
## 待解決: 某些情況下進行 make test 整個 ubundtu 直接掛掉，需要強制重新開機
- ~~待測試~~
- 以解決
## 目前進度
1. 熟悉 Git/GitHub, 環境架設, HackMD
2. GNU, Linux 開發工具:
* Cppcheck
* git-good-commit
* clang-format: 隨時提醒自己別用 TAB
* valgrind
3. 完成 queue.c/h
## 實驗過程
### q_size
~~範例 q_size 就不提了~~ 我錯了我好爛
有點東西要注意如果我沒有 queue 的時候呼叫 q_size 會出錯
這裡要判斷 q 是否為NULL
```c=
int q_size(queue_t *q)
{
if(!q)
return 0;
else
return q->size;
}
```
稍微精簡一下
```c=
int q_size(queue_t *q)
{
return q?q->size:0;
}
```
### q_insert_head (後面微改)
想在 Queue 中頭尾加入 element，先修改 queue.h 中 Queue structure
這樣我的 Queue Type 會有兩個指向頭尾 element 的 pointer
```c=
/* Queue structure */
typedef struct {
list_ele_t *head; /* Linked list of head elements */
list_lel_t *tail; /*Linked list of tail elements*/
int size; /*Queue's size for q-size*/
} queue_t;
```
再來修改 queue.c 中 q_new() , q_insert_head
q_insert_head 部分已經寫好但是有提到 2 問題:
1. 如果 queue 為 NULL 時的處理 -> return false
2. 如果 call malloc 回傳 NULL 要做處理 -> ~~這邊我想應該是做 try/except 做~~ -> 用 NULL 判斷就可以處理
```c=
//1. 先改 q_new() 增加 head tail size
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
if(!q)
return NULL;
q->head = NULL;
q->tail = NULL;
q->size = 0;
return q;
}
//2. q_insert_head 修改如下
bool q_insert_head(queue_t *q, char *s)
{
list_ele_t *newh;
if (!q)
return false;
newh = malloc(sizeof(list_ele_t));
if(!newh)
return false;
newh->value = malloc(sizeof(char)*strlen(s)+1);
if(!newh->value)
return false;
strncpy(newh->value,s,strlen(s)+1);
newh->next = q->head;
q->head = newh;
if(!q->size)
q->tail = newh;
q->size++;
return true;
}
```
花了點時間回想 linklist 的寫法 zzz
[strncpy()](https://en.cppreference.com/w/c/string/byte/strncpy) 這超容易忘記
然後要 commit 上去時候意外發現了
```
$ clang-format -i queue.h
$ clang-format -i queue.c
$ git commit -a
Following files need to be cleaned up:
queue.c
queue.h
queue.c:48:9: error: Memory leak: newh [memleak]
return false;
^
queue.c:75:9: error: Memory leak: newt [memleak]
return false;
^
Fail to pass static analysis.
```
後來發現在做
```c=
if(!newt->value)
return false;
```
的時候建置失敗回傳 false 前面有 malloc 一些空間忘記釋放，在回傳前free掉即可
```c=
if(!newt->value){
free(newt);
return false;
}
```
就可以 commit 並 push
### q_insert_tail (後面微改)
幾乎和上面一樣
```c=
bool q_insert_tail(queue_t *q, char *s)
{
list_ele_t *newt;
if (!q)
return false;
newt = malloc(sizeof(list_ele_t));
if (!newt)
return false;
newt->value = malloc(sizeof(char) * strlen(s) + 1);
if (!newt->value) {
free(newt);
return false;
}
strncpy(newt->value, s, strlen(s) + 1);
newt->next = NULL;
if (!q->size){
q->head = newt;
q->tail = newt;
}
else{
q->tail->next = newt;
}
q->size++;
return true;
}
```
### q_free
釋放掉整個 queue ，但是也要 free 掉原本在 element 裡的字串
```c=
void q_free(queue_t *q)
{
while(q->head){
list_ele_t *ptr = q->head;
free(q->head->value);
q->head = q->head->next;
free(ptr);
}
free(q);
}
```
### q_remove_head
按照註解做這邊問題不大
開始前先確定引數中 `size_t` 的定義:
According to the 1999 ISO C standard (C99), size_t is an unsigned integer type of at least 16 bit (see sections 7.17 and 7.18.3).
我的理解為這樣可以確保製造記憶體空間是正確的，若丟入負值會造成記憶體越權存取相關錯誤
```c=
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (!q)
return false;
if (!q->size)
return false;
if (sp && q->head->value) {
memset(sp, '\0', bufsize);
strncpy(sp, q->head->value, bufsize - 1);
} else
return false;
list_ele_t *ptr = q->head;
q->head = q->head->next;
free(ptr->value);
free(ptr);
q->size--;
return true;
}
```
### q_reverse
這邊是我目前想最久的部分，老實說第一眼看到這裡面我的直覺就是全部先 pop 出並且 push 到一個 stack 結構裡面，再從 stack 中 pop 並且 push 到原先 queue中。
不過題目限制就只好換其他方法了。
有個比較直觀的方法是用3個 pointer 去做，不過我選用其他的方法:
```c=
void q_reverse(queue_t *q)
{
if (q->size < 2) {
printf("elements in queue lower than 2\n");
return;
}
list_ele_t *ptr = q->head->next->next;
q->tail->next = q->head;
while (q->head->next != q->tail) {
q->head->next->next = q->tail->next;
q->tail->next = q->head->next;
q->head->next = ptr;
ptr = ptr->next;
}
q->tail = q->head;
q->head = q->head->next;
q->tail->next = NULL;
}
```
這個`while (q->head->next != q->tail) {...}`裡面做的事情下圖表示:
原本的 q 要做 reverse
```graphviz
digraph graphname {
rankdir=LR;
A [label="A" color=Blue, fontcolor=Red, fontsize=24, shape=box]
B [label="B" color=Blue, fontcolor=Red, fontsize=24, shape=box]
C [label="C" color=Blue, fontcolor=Red, fontsize=24, shape=box]
D [label="D" color=Blue, fontcolor=Red, fontsize=24, shape=box]
E [label="E" color=Blue, fontcolor=Red, fontsize=24, shape=box]
head[label="Head"]
tail[label="Tail"]
A->B [fontcolor=black]
B->C [fontcolor=black]
C->D [fontcolor=black]
D->E [fontcolor=black]
head->A [fontcolor=black]
tail->E [fontcolor=black]
E->NULL [fontcolor=black]
}
```
q 的 Initial
1. ptr = head->next->next
2. tail->next = head
```graphviz
digraph graphname {
rankdir=LR;
A [label="A" color=Blue, fontcolor=Red, fontsize=24, shape=box]
B [label="B" color=Blue, fontcolor=Red, fontsize=24, shape=box]
C [label="C" color=Blue, fontcolor=Red, fontsize=24, shape=box]
D [label="D" color=Blue, fontcolor=Red, fontsize=24, shape=box]
E [label="E" color=Blue, fontcolor=Red, fontsize=24, shape=box]
head[label="Head"]
tail[label="Tail"]
ptr[label="ptr"]
A->B [fontcolor=black]
B->C [fontcolor=black]
C->D [fontcolor=black]
D->E [fontcolor=black]
ptr->C [fontcolor=black]
head->A [fontcolor=black]
tail->E [fontcolor=black]
E->A [fontcolor=black]
}
```
再來做 while(..)
```graphviz
digraph graphname {
rankdir=LR;
A [label="A" color=Blue, fontcolor=Red, fontsize=24, shape=box]
B [label="B" color=Blue, fontcolor=Red, fontsize=24, shape=box]
C [label="C" color=Blue, fontcolor=Red, fontsize=24, shape=box]
D [label="D" color=Blue, fontcolor=Red, fontsize=24, shape=box]
E [label="E" color=Blue, fontcolor=Red, fontsize=24, shape=box]
head[label="Head"]
tail[label="Tail"]
ptr[label="ptr"]
A->C [fontcolor=black]
B->A [fontcolor=black]
C->D [fontcolor=black]
D->E [fontcolor=black]
E->B [fontcolor=black]
ptr->D [fontcolor=black]
head->A [fontcolor=black]
tail->E [fontcolor=black]
}
```
```graphviz
digraph graphname {
rankdir=LR;
A [label="A" color=Blue, fontcolor=Red, fontsize=24, shape=box]
B [label="B" color=Blue, fontcolor=Red, fontsize=24, shape=box]
C [label="C" color=Blue, fontcolor=Red, fontsize=24, shape=box]
D [label="D" color=Blue, fontcolor=Red, fontsize=24, shape=box]
E [label="E" color=Blue, fontcolor=Red, fontsize=24, shape=box]
head[label="Head"]
tail[label="Tail"]
ptr[label="ptr"]
A->D [fontcolor=black]
B->A [fontcolor=black]
C->B [fontcolor=black]
D->E [fontcolor=black]
E->C [fontcolor=black]
ptr->E [fontcolor=black]
head->A [fontcolor=black]
tail->E [fontcolor=black]
}
```
```graphviz
digraph graphname {
rankdir=LR;
A [label="A" color=Blue, fontcolor=Red, fontsize=24, shape=box]
B [label="B" color=Blue, fontcolor=Red, fontsize=24, shape=box]
C [label="C" color=Blue, fontcolor=Red, fontsize=24, shape=box]
D [label="D" color=Blue, fontcolor=Red, fontsize=24, shape=box]
E [label="E" color=Blue, fontcolor=Red, fontsize=24, shape=box]
head[label="Head"]
tail[label="Tail"]
ptr[label="ptr"]
A->E [fontcolor=black]
B->A [fontcolor=black]
C->B [fontcolor=black]
D->C [fontcolor=black]
E->D [fontcolor=black]
ptr->C [fontcolor=black]
head->A [fontcolor=black]
tail->E [fontcolor=black]
}
```
最後做 head tail調整
```graphviz
digraph graphname {
rankdir=LR;
A [label="A" color=Blue, fontcolor=Red, fontsize=24, shape=box]
B [label="B" color=Blue, fontcolor=Red, fontsize=24, shape=box]
C [label="C" color=Blue, fontcolor=Red, fontsize=24, shape=box]
D [label="D" color=Blue, fontcolor=Red, fontsize=24, shape=box]
E [label="E" color=Blue, fontcolor=Red, fontsize=24, shape=box]
head[label="Head"]
tail[label="Tail"]
A->NULL [fontcolor=black]
B->A [fontcolor=black]
C->B [fontcolor=black]
D->C [fontcolor=black]
E->D [fontcolor=black]
head->E [fontcolor=black]
tail->A [fontcolor=black]
}
```
### q_sort
Sort elements of queue in ascending order
字串大小做升序排序 (?)
如果說要對於一個 list 做 sort 我參考資料:[Merge Sort Algorithm for Singly Linked List](https://www.techiedelight.com/merge-sort-singly-linked-list/)
~~ctrl-c/v大法好~~
[一分半了解 Merge Sort](https://www.youtube.com/watch?v=JSceec-wEyw&ab_channel=GeeksforGeeks)
[Better Way](https://npes87184.github.io/2015-09-12-linkedListSort/)
```c=
void q_sort(queue_t *q)
{
if (!q)
return;
if (q->size < 3)
return;
q->head = mergeSortList(q->head);
q->tail = q->head;
while (q->tail->next)
q->tail = q->tail->next;
}
list_ele_t *merge(list_ele_t *L1, list_ele_t *L2)
{
// merge with recursive
if (!L2)
return L1;
if (!L1)
return L2;
if (strcmp(L1->value, L2->value) < 0) {
printf("L1=%s L2=%s\n", L1->value, L2->value);
L1->next = merge(L1->next, L2);
return L1;
} else {
L2->next = merge(L1, L2->next);
return L2;
}
}
list_ele_t *mergeSortList(list_ele_t *head)
{
if (!head || !head->next)
return head;
// tmp pointer for original q->head
list_ele_t *ptr1 = head->next;
list_ele_t *ptr2 = head;
while (ptr1 && ptr1->next) {
ptr2 = ptr2->next;
ptr1 = ptr1->next->next;
}
ptr1 = ptr2->next;
ptr2->next = NULL;
// sort start
list_ele_t *L1 = mergeSortList(head);
list_ele_t *L2 = mergeSortList(ptr1);
return merge(L1, L2);
}
```
OK 順利寫道個段落了再來是 ` make test` 囉，然後意外發生了
trace-07-robust.cmd:
```c=
# Test operations on NULL queue
option fail 10
option malloc 0
free
ih bear
it dolphin
rh
reverse
size
sort
```
看來是對於當在 q=NULL 時候出了點錯誤，仔細看看發現問題在 insert function
修改過後 pass
```c=
bool q_insert_tail(queue_t *q, char *s)
{
if (!q)
return false;
list_ele_t *newt;
newt = malloc(sizeof(list_ele_t));
if (!newt)
return false;
newt->value = malloc(sizeof(char) * strlen(s) + 1);
if (!newt->value) {
free(newt);
return false;
}
strncpy(newt->value, s, strlen(s) + 1);
newt->next = NULL;
if (!q->size) {
q->head = newt;
} else {
q->tail->next = newt;
}
q->tail = newt;
q->size++;
return true;
}
```
這邊解決了之後第二個問題:
```
# Test performance of size
--- trace-14-perf 6/6
+++ TESTING trace trace-15-perf:
# Test performance of insert_tail, size, reverse, and sort
--- trace-15-perf 0/6
+++ TESTING trace trace-16-perf:
# Test performance of sort with random and descending orders
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
--- trace-16-perf 6/6
+++ TESTING trace trace-17-complexity:
# Test if q_insert_tail and q_size is constant time complexity
Probably constant time
Probably constant time
--- trace-17-complexity 5/5
--- TOTAL 94/100
```
trace-15-perf 沒過啊，看一下第15項測試如下
```
# Test performance of insert_tail, size, reverse, and sort
option fail 0
option malloc 0
new
ih dolphin 1000000
it gerbil 1000000
size 1000
reverse
sort
size 1000
```
stack爆炸啦
在這裡大概猜到了我在 merge sort 用遞迴的寫法，如果改成用 while 應該就可以...吧?
◢▆▅▄▃ 崩╰(〒皿〒)╯潰 ▃▄▅▆◣ 我花了時間寫成遞迴形式誒，又要重改了
對 merge(...) 做更改
```
list_ele_t *merge(list_ele_t *l1, list_ele_t *l2)
{
if (!l2)
return l1;
if (!l1)
return l2;
list_ele_t *curr, *head;
if (strcmp(l1->value, l2->value) < 0) {
head = l1;
l1 = l1->next;
} else {
head = l2;
l2 = l2->next;
}
curr = head;
while (l1 && l2) {
if (strcmp(l1->value, l2->value) < 0) {
curr->next = l1;
l1 = l1->next;
} else {
curr->next = l2;
l2 = l2->next;
}
curr = curr->next;
}
if (l1)
curr->next = l1;
if (l2)
curr->next = l2;
return head;
}
```
到這裡就完成 queue.c 的修改了
```
--- trace-14-perf 6/6
+++ TESTING trace trace-15-perf:
# Test performance of insert_tail, size, reverse, and sort
--- trace-15-perf 6/6
+++ TESTING trace trace-16-perf:
# Test performance of sort with random and descending orders
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
--- trace-16-perf 6/6
+++ TESTING trace trace-17-complexity:
# Test if q_insert_tail and q_size is constant time complexity
Probably constant time
Probably constant time
--- trace-17-complexity 5/5
--- TOTAL 100/100
ylowy@ylowy-X550VX:~/linux2020/lab0
```
終於順利過test了
## Valgrind
```
make clean
make valgrind
```
結果顯示:
```
--- trace-16-perf 0/6
+++ TESTING trace trace-17-complexity:
# Test if q_insert_tail and q_size is constant time complexity
Testing insert_tail...(0/10)
==13203== Invalid write of size 4
==13203== at 0x10DDED: q_free (queue.c:35)
==13203== by 0x10E44C: measure (constant.c:71)
==13203== by 0x10E636: doit (fixture.c:136)
==13203== by 0x10E88E: is_insert_tail_const (fixture.c:168)
```
每一個trace測試在一開始就出現了 `Invalid write of size 4` 這樣的錯誤訊息
### 安裝 visualizer
```
sudo apt-get update -y
sudo apt-get install -y massif-visualizer
```
再用 massif-visualizer 可以看到精美的圖了
### Address Sanitizer 做分析
```
花了好一段時間看這個部分，只看懂大概原理跟使用方法
不過對於將 shadow 記憶體定址在原本記憶體位址的1/8?
把8個 bytes 看作一組並判斷 posion byte 這個地方還能理解
不過程式碼裡面
"*a>>3"
這裡我覺得應該不只有單純變成1/8大小那麼簡單，下次回來要再看一次
```
操作部分:
```
$ make clean
$ make SANITIZER=1
$ make test
```
看到一排錯誤就覺得不妙了，乾
```
ylowy@ylowy-X550VX:~/linux2020/lab0-c$ make test
scripts/driver.py -c
--- Trace Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
=================================================================
==4036==ERROR: AddressSanitizer: heap-use-after-free on address 0x606000000050 at pc 0x55778e8b0898 bp 0x7fff73406a80 sp 0x7fff73406a70
WRITE of size 4 at 0x606000000050 thread T0
#0 0x55778e8b0897 in q_free /home/ylowy/linux2020/lab0-c/queue.c:35
#1 0x55778e8aa9c3 in queue_quit /home/ylowy/linux2020/lab0-c/qtest.c:661
#2 0x55778e8ae9fa in do_quit_cmd /home/ylowy/linux2020/lab0-c/console.c:288
#3 0x55778e8affb9 in finish_cmd /home/ylowy/linux2020/lab0-c/console.c:616
#4 0x55778e8ad16a in main /home/ylowy/linux2020/lab0-c/qtest.c:773
#5 0x7fcb290570b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
#6 0x55778e8aa88d in _start (/home/ylowy/linux2020/lab0-c/qtest+0x788d)
0x606000000050 is located 48 bytes inside of 64-byte region [0x606000000020,0x606000000060)
freed by thread T0 here:
#0 0x7fcb2947e7cf in __interceptor_free (/lib/x86_64-linux-gnu/libasan.so.5+0x10d7cf)
#1 0x55778e8b0482 in test_free /home/ylowy/linux2020/lab0-c/harness.c:209
#2 0x55778e8b084c in q_free /home/ylowy/linux2020/lab0-c/queue.c:34
#3 0x55778e8aa9c3 in queue_quit /home/ylowy/linux2020/lab0-c/qtest.c:661
#4 0x55778e8ae9fa in do_quit_cmd /home/ylowy/linux2020/lab0-c/console.c:288
#5 0x55778e8affb9 in finish_cmd /home/ylowy/linux2020/lab0-c/console.c:616
#6 0x55778e8ad16a in main /home/ylowy/linux2020/lab0-c/qtest.c:773
#7 0x7fcb290570b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
previously allocated by thread T0 here:
#0 0x7fcb2947ebc8 in malloc (/lib/x86_64-linux-gnu/libasan.so.5+0x10dbc8)
#1 0x55778e8b00ec in test_malloc /home/ylowy/linux2020/lab0-c/harness.c:138
#2 0x55778e8b071f in q_new /home/ylowy/linux2020/lab0-c/queue.c:14
#3 0x55778e8ac863 in do_new /home/ylowy/linux2020/lab0-c/qtest.c:124
#4 0x55778e8ae572 in interpret_cmda /home/ylowy/linux2020/lab0-c/console.c:220
#5 0x55778e8aefb9 in interpret_cmd /home/ylowy/linux2020/lab0-c/console.c:243
#6 0x55778e8afc64 in cmd_select /home/ylowy/linux2020/lab0-c/console.c:569
#7 0x55778e8b0032 in run_console /home/ylowy/linux2020/lab0-c/console.c:628
#8 0x55778e8ad0ad in main /home/ylowy/linux2020/lab0-c/qtest.c:772
#9 0x7fcb290570b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
SUMMARY: AddressSanitizer: heap-use-after-free /home/ylowy/linux2020/lab0-c/queue.c:35 in q_free
Shadow bytes around the buggy address:
0x0c0c7fff7fb0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c0c7fff7fc0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c0c7fff7fd0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c0c7fff7fe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c0c7fff7ff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x0c0c7fff8000: fa fa fa fa fd fd fd fd fd fd[fd]fd fa fa fa fa
0x0c0c7fff8010: fd fd fd fd fd fd fd fa fa fa fa fa fd fd fd fd
0x0c0c7fff8020: fd fd fd fa fa fa fa fa fd fd fd fd fd fd fd fa
0x0c0c7fff8030: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c0c7fff8040: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c0c7fff8050: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
Addressable: 00
Partially addressable: 01 02 03 04 05 06 07
Heap left redzone: fa
Freed heap region: fd
Stack left redzone: f1
Stack mid redzone: f2
Stack right redzone: f3
Stack after return: f5
Stack use after scope: f8
Global redzone: f9
Global init order: f6
Poisoned by user: f7
Container overflow: fc
Array cookie: ac
Intra object redzone: bb
ASan internal: fe
Left alloca redzone: ca
Right alloca redzone: cb
Shadow gap: cc
==4036==ABORTING
--- trace-01-ops 0/6
```
看結論部分
```
SUMMARY: AddressSanitizer: heap-use-after-free /home/ylowy/linux2020/lab0-c/queue.c:35 in q_free
```
所以是我在 q_free 有操作到已經釋放的資料了，看了一下
```c=23
void q_free(queue_t *q)
{
if (!q)
return;
while (q->head) {
list_ele_t *ptr = q->head;
free(q->head->value);
q->head = q->head->next;
free(ptr);
}
free(q);
q->size = 0;
}
```
我好爛
怎麼連這個都會寫錯 = =
更改成下面:
```c=23
void q_free(queue_t *q)
{
if (!q)
return;
while (q->head) {
list_ele_t *ptr = q->head;
free(q->head->value);
q->head = q->head->next;
free(ptr);
}
q->size = 0;
free(q);
}
```
再 remake 跑一次
```
+++ TESTING trace trace-17-complexity:
# Test if q_insert_tail and q_size is constant time complexity
=================================================================
==4593==ERROR: AddressSanitizer: global-buffer-overflow on address 0x55b15f6a89e0 at pc 0x55b15f6979e5 bp 0x7ffc354314a0 sp 0x7ffc35431490
READ of size 4 at 0x55b15f6a89e0 thread T0
#0 0x55b15f6979e4 in do_option_cmd /home/ylowy/linux2020/lab0-c/console.c:368
#1 0x55b15f696572 in interpret_cmda /home/ylowy/linux2020/lab0-c/console.c:220
#2 0x55b15f696fb9 in interpret_cmd /home/ylowy/linux2020/lab0-c/console.c:243
#3 0x55b15f697c64 in cmd_select /home/ylowy/linux2020/lab0-c/console.c:569
#4 0x55b15f698032 in run_console /home/ylowy/linux2020/lab0-c/console.c:628
#5 0x55b15f6950ad in main /home/ylowy/linux2020/lab0-c/qtest.c:772
#6 0x7f79dbc960b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
#7 0x55b15f69288d in _start (/home/ylowy/linux2020/lab0-c/qtest+0x788d)
0x55b15f6a89e1 is located 0 bytes to the right of global variable 'simulation' defined in 'console.c:20:6' (0x55b15f6a89e0) of size 1
'simulation' is ascii string ''
SUMMARY: AddressSanitizer: global-buffer-overflow /home/ylowy/linux2020/lab0-c/console.c:368 in do_option_cmd
Shadow bytes around the buggy address:
0x0ab6abecd0e0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ab6abecd0f0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ab6abecd100: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ab6abecd110: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9
0x0ab6abecd120: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9
=>0x0ab6abecd130: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9[01]f9 f9 f9
0x0ab6abecd140: f9 f9 f9 f9 00 00 00 00 01 f9 f9 f9 f9 f9 f9 f9
0x0ab6abecd150: 04 f9 f9 f9 f9 f9 f9 f9 00 00 00 00 00 00 00 00
0x0ab6abecd160: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ab6abecd170: 00 f9 f9 f9 f9 f9 f9 f9 01 f9 f9 f9 f9 f9 f9 f9
0x0ab6abecd180: 01 f9 f9 f9 f9 f9 f9 f9 04 f9 f9 f9 f9 f9 f9 f9
Shadow byte legend (one shadow byte represents 8 application bytes):
Addressable: 00
Partially addressable: 01 02 03 04 05 06 07
Heap left redzone: fa
Freed heap region: fd
Stack left redzone: f1
Stack mid redzone: f2
Stack right redzone: f3
Stack after return: f5
Stack use after scope: f8
Global redzone: f9
Global init order: f6
Poisoned by user: f7
Container overflow: fc
Array cookie: ac
Intra object redzone: bb
ASan internal: fe
Left alloca redzone: ca
Right alloca redzone: cb
Shadow gap: cc
==4593==ABORTING
--- trace-17-complexity 0/5
--- TOTAL 95/100
```
nice!!剩下一個而已
第 17 測試有全域變數中的 buffer overflow 問題
```
SUMMARY: AddressSanitizer: global-buffer-overflow /home/ylowy/linux2020/lab0-c/console.c:368 in do_option_cmd
```
來看看 console.c 的部分
```c=339
static bool do_option_cmd(int argc, char *argv[])
{
if (argc == 1) {
param_ptr plist = param_list;
report(1, "Options:");
while (plist) {
report(1, "\t%s\t%d\t%s", plist->name, *plist->valp,
plist->documentation);
plist = plist->next;
}
return true;
}
for (int i = 1; i < argc; i++) {
char *name = argv[i];
int value = 0;
bool found = false;
/* Get value from next argument */
if (i + 1 >= argc) {
report(1, "No value given for parameter %s", name);
return false;
} else if (!get_int(argv[++i], &value)) {
report(1, "Cannot parse '%s' as integer", argv[i]);
return false;
}
/* Find parameter in list */
param_ptr plist = param_list;
while (!found && plist) {
if (strcmp(plist->name, name) == 0) {
int oldval = *plist->valp;
*plist->valp = value;
if (plist->setter)
plist->setter(oldval);
found = true;
} else
plist = plist->next;
}
/* Didn't find parameter */
if (!found) {
report(1, "Unknown parameter '%s'", name);
return false;
}
}
return true;
}
```
程式碼上找不到什麼問題，不過他提到全域變數的溢位，也許要看看全域變數的部分
```c=18
/* Some global values */
bool simulation = false;
```
找到問題了!!!!!
這裡 console.c 宣告一個全域布林變數 simulation
但是在使用 function add_param 做了很壞的事情:
```c=102
add_param("simulation", (int *) &simulation, "Start/Stop simulation mode",
NULL);add_param("simulation", (int *) &simulation, "Start/Stop simulation mode",
NULL);
```
把指向布林變數的變數 強制轉型成 the pointer to int
壞!壞透了!!!!!
於是乎在這個 function 裡面，他把原本的 the pointer to bool assign to the pointer to int
C 沒有 array index out of bound 的檢查機制 (C99) <-我記得是這樣
然後又因為最佳化的情況，雖然 bool 只佔了一個 byte 編譯器給他一個 byte 空間後，下個全域變數給到下個 word 上
這三個空出來的 bytes 就是造成 global-buffer-overflow 而在測試環境下結果卻沒出錯的原因!!!
```c=132
void add_param(char *name,
int *valp,
char *documentation,
setter_function setter)
{
param_ptr next_param = param_list;
param_ptr *last_loc = ¶m_list;
while (next_param && strcmp(name, next_param->name) > 0) {
last_loc = &next_param->next;
next_param = next_param->next;
}
param_ptr ele = (param_ptr) malloc_or_fail(sizeof(param_ele), "add_param");
ele->name = name;
ele->valp = valp;
ele->documentation = documentation;
ele->setter = setter;
ele->next = next_param;
*last_loc = ele;
}
```
驗證猜想是否正確:
```
objdump -D -M intel ./qtest > obj
```
看看全域變數在執行期間定址在哪裡:
```
000000000001d960 <param_list>:
...
000000000001d9a0 <cmd_list>:
...
000000000001d9e0 <simulation>:
...
000000000001da20 <__odr_asan.simulation>:
...
000000000001da40 <time_limited>:
...
```
....
有點怪
後來發現我忘記 remake 這是之前 Address Sanitizer 執行時會插入程式碼導致後面轉成 machine code 結果不同
remake之後:
```
000000000000b520 <simulation>:
b520: 00 00 add BYTE PTR [rax],al
...
000000000000b524 <quit_helper_cnt>:
...
000000000000b540 <quit_helpers>:
```
沒錯跟想的一樣
雖然給一個 bool 這樣 1 byte 大小的空間，然而下個位址空間是在下 4 個 bytes 上 (0b520 -> 0b524)
在 gdb 下跑 qtest:
先在 main 下中斷點，執行到 main 正要開始的地方
查看這時候 simulation 的位址在哪裡: `p &simulation
$1 = (_Bool *) 0x55555555f520 <simulation>`
查看當時附近 memory 狀態: `x/16 0x55555555f520`
幾乎對囉
```
ylowy@ylowy-X550VX:~/linux2020/lab0-c$ gdb ./qtest
GNU gdb (Ubuntu 9.1-0ubuntu1) 9.1
Copyright (C) 2020 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.
Type "show copying" and "show warranty" for details.
This GDB was configured as "x86_64-linux-gnu".
Type "show configuration" for configuration details.
For bug reporting instructions, please see:
<http://www.gnu.org/software/gdb/bugs/>.
Find the GDB manual and other documentation resources online at:
<http://www.gnu.org/software/gdb/documentation/>.
For help, type "help".
Type "apropos word" to search for commands related to "word"...
Reading symbols from ./qtest...
(gdb) b main
Breakpoint 1 at 0x3b88: file qtest.c, line 719.
(gdb) r
Starting program: /home/ylowy/linux2020/lab0-c/qtest
Breakpoint 1, main (argc=1, argv=0x7fffffffdf38) at qtest.c:719
719 {
(gdb) p &simulation
$1 = (_Bool *) 0x55555555f520 <simulation>
(gdb) x/4 0x55555555f520
0x55555555f520 <simulation>: 0 0 0 0
(gdb) x/16 0x55555555f520
0x55555555f520 <simulation>: 0 0 0 0
0x55555555f530: 0 0 0 0
0x55555555f540 <quit_helpers>: 0 0 0 0
0x55555555f550 <quit_helpers+16>: 0 0 0 0
```
修改就簡單了: bool -> int
console.c
```c=19
/* Some global values */
int simulation = false;
```
console.h
```c=8
/* Simulation flag of console option */
extern int simulation;
```
再 remake 跑一次 make test
```
--- trace-16-perf 6/6
+++ TESTING trace trace-17-complexity:
# Test if q_insert_tail and q_size is constant time complexity
Probably constant time
Probably constant time
--- trace-17-complexity 5/5
--- TOTAL 100/100
```
順利過關
## Dude, is my code constant time? 研讀
### 時序攻擊
在第二周課程中才有對 timing attack 的初步認知，能夠建立 "O(1)" 的演算法對於資安領域十分重要
### 方法
在程式執行時用 "Leakage detection test" 測量
#### 第一步 : Measure execution time
1. Classes definition
利用兩種不同類別的輸入做比較 a. fixed-vs-random tests b. random
2. Cycle counters
現在CPU都有提供 Cycle counters
3. Environmental conditions
input 都要事先準備好
#### 第二步 : Apply post-processing
在做最後分析前會對資料做些處理:
1. Cropping :
極端值都先取出 (可能被OS或者其他程式中斷)
2. Higher-order preprocessing :
apply some higher-order pre-process 不太理解??
我的想法是在做統計分析處理之前可以可以做最佳處理化 (?) 讓 CPU 溫度維持固定會者其他原因讓統計結果資料能如預期(?
#### 第三步 Apply statistical test
做完 post-processing 的資料會被進行統計分析 並試著駁斥 Null hypothesis (the two timing distributions are equal) 的方式
科普 : 虛無假說 (Null hypothesis)
虛無假說的內容一般是希望能證明為錯誤的假設
1. t-test : Welch's t-test (兩組資料變異數不同時的 t-test) + 雙尾檢定
2. Non-parametric tests : Kolomogorov Smirnov
補:
在不知道母體平均數時，利用抽樣的資訊來推論出近似常態分配的分佈。自由度會影響學生 t 分佈的圖型。自由度無限大的學生 t 分佈便是常態分佈。 (感謝強者我同學)
在qtest.c中
```c=252
static bool do_insert_tail(int argc, char *argv[])
{
if (simulation) {
if (argc != 1) {
report(1, "%s does not need arguments in simulation mode", argv[0]);
return false;
}
bool ok = is_insert_tail_const();
if (!ok) {
report(1, "ERROR: Probably not constant time");
return false;
}
report(1, "Probably constant time");
return ok;
}
...
```
simulation = true 時候會執行 bool ok = is_insert_tail_const();
dudect/fixture.c
```c=156
bool is_insert_tail_const(void)
{
bool result = false;
t = malloc(sizeof(t_ctx));
for (int cnt = 0; cnt < test_tries; ++cnt) {
printf("Testing insert_tail...(%d/%d)\n\n", cnt, test_tries);
init_once();
for (int i = 0;
i <
enough_measurements / (number_measurements - drop_size * 2) + 1;
++i)
result = doit(0);
printf("\033[A\033[2K\033[A\033[2K");
if (result == true)
break;
}
free(t);
return result;
}
```
看看`init_once();` 做了啥
```c=150
static void init_once(void)
{
init_dut();
t_init(t);
}
```
其中 t 為全域變數
```
static t_ctx *t;
```
```c=5
typedef struct {
double mean[2];
double m2[2];
double n[2];
} t_ctx;
```
dudect/constant.c
```c=27
/* Implement the necessary queue interface to simulation */
void init_dut(void)
{
q = NULL;
}
```
dudect/ttest.c
```c=42
void t_init(t_ctx *ctx)
{
for (int class = 0; class < 2; class ++) {
ctx->mean[class] = 0.0;
ctx->m2[class] = 0.0;
ctx->n[class] = 0.0;
}
return;
}
```
至於 init_once(); 在於初始化統計資料
注意到有定義 `#define test_tries 10` 給10次機會讓他去 disprove 前面所說的 Null hypothesis
所以我們注重了解在迴圈內部再寫甚麼
```c=
for (int cnt = 0; cnt < test_tries; ++cnt) {
printf("Testing insert_tail...(%d/%d)\n\n", cnt, test_tries);
init_once();
for (int i = 0;
i <
enough_measurements / (number_measurements - drop_size * 2) + 1;
++i)
result = doit(0);
printf("\033[A\033[2K\033[A\033[2K");
if (result == true)
break;
}
```
第二層 for 是讓裡面 doit 作足夠多次，再來看看 doit(0) 在做什麼的
dudect/fixture.c
```c=120
static bool doit(int mode)
{
int64_t *before_ticks = calloc(number_measurements + 1, sizeof(int64_t));
int64_t *after_ticks = calloc(number_measurements + 1, sizeof(int64_t));
int64_t *exec_times = calloc(number_measurements, sizeof(int64_t));
uint8_t *classes = calloc(number_measurements, sizeof(uint8_t));
uint8_t *input_data =
calloc(number_measurements * chunk_size, sizeof(uint8_t));
if (!before_ticks || !after_ticks || !exec_times || !classes ||
!input_data) {
die();
}
prepare_inputs(input_data, classes);
measure(before_ticks, after_ticks, input_data, mode);
differentiate(exec_times, before_ticks, after_ticks);
update_statistics(exec_times, classes);
bool ret = report();
free(before_ticks);
free(after_ticks);
free(exec_times);
free(classes);
free(input_data);
return ret;
}
```
這裡好多部分一個一個看:
calloc() 想成 malloc 後裡面填0
```c=
if (!before_ticks || !after_ticks || !exec_times || !classes ||
!input_data) {
die();
}
```
檢查上面資源有沒有建立起來
prepare_inputs:
```c=
void prepare_inputs(uint8_t *input_data, uint8_t *classes)
{
randombytes(input_data, number_measurements * chunk_size);
for (size_t i = 0; i < number_measurements; i++) {
classes[i] = randombit();
if (classes[i] == 0)
*(uint16_t *) (input_data + i * chunk_size) = 0x00;
}
for (size_t i = 0; i < NR_MEASURE; ++i) {
/* Generate random string */
randombytes((uint8_t *) random_string[i], 7);
random_string[i][7] = 0;
}
}
```
classes 決定是 fix 或者是 random
random.c:
```c=7
/* shameless stolen from ebacs */
void randombytes(uint8_t *x, size_t how_much)
{
ssize_t i;
static int fd = -1;
ssize_t xlen = (ssize_t) how_much;
assert(xlen >= 0);
if (fd == -1) {
for (;;) {
fd = open("/dev/urandom", O_RDONLY);
if (fd != -1)
break;
sleep(1);
}
}
while (xlen > 0) {
if (xlen < 1048576)
i = xlen;
else
i = 1048576;
i = read(fd, x, (size_t) i);
if (i < 1) {
sleep(1);
continue;
}
x += i;
xlen -= i;
}
}
```
讓 x 得到亂數
randombit 就是透過 randombytes 以 bitwise mask 方式得到
也就是說prepare_input 用於讓我們的決定插入該次 disprove 的 queue_t
constant.c
void measure()
```c=55
void measure(int64_t *before_ticks,
int64_t *after_ticks,
uint8_t *input_data,
int mode)
{
assert(mode == test_insert_tail || mode == test_size);
if (mode == test_insert_tail) {
for (size_t i = drop_size; i < number_measurements - drop_size; i++) {
char *s = get_random_string();
dut_new();
dut_insert_head(
get_random_string(),
*(uint16_t *) (input_data + i * chunk_size) % 10000);
before_ticks[i] = cpucycles();
dut_insert_tail(s, 1);
after_ticks[i] = cpucycles();
dut_free();
}
} else {
for (size_t i = drop_size; i < number_measurements - drop_size; i++) {
dut_new();
dut_insert_head(
get_random_string(),
*(uint16_t *) (input_data + i * chunk_size) % 10000);
before_ticks[i] = cpucycles();
dut_size(1);
after_ticks[i] = cpucycles();
dut_free();
}
}
}
```
簡單而言就是存入 CPU cycle 紀錄執行時間
放進 doit() 參數 mode 只是判斷 test_insert_tail 或 test_size
fixture.c
```c=61
static void differentiate(int64_t *exec_times,
int64_t *before_ticks,
int64_t *after_ticks)
{
for (size_t i = 0; i < number_measurements; i++) {
exec_times[i] = after_ticks[i] - before_ticks[i];
}
}
```
找出每一次執行時間
```c=70
static void update_statistics(int64_t *exec_times, uint8_t *classes)
{
for (size_t i = 0; i < number_measurements; i++) {
int64_t difference = exec_times[i];
/* Cpu cycle counter overflowed or dropped measurement */
if (difference <= 0) {
continue;
}
/* do a t-test on the execution time */
t_push(t, difference, classes[i]);
}
}
```
以該次實驗結果做記錄，並透過 t_push 更新原本的 t_ctx structure (Welford method)
report()
這邊再次參考強者我同學共筆 非常感謝 !!!
report : 算出檢驗統計量 t[1]，在檢查有沒有太過異常資料 (OS 或者其他程式中斷)
( t > t_threshold_bananas 就是所判斷異常故丟掉， t > t_threshold_moderate 就是落在臨界點附近的拒絕域)
也是我們照輪文所說的以雙尾檢定 (?)
假如落在拒絕域，則拒絕零假設，表示 fix class 的執行時間分布與 random class 的執行時間分布不同，也就表示執行時間並非常數。
假若沒有落在拒絕域，則暫時不拒絕零假設，表示暫時不拒絕 fix class 的時間分布與 random class 相同，也就表示執行時間為常數。
#### 提問
1. 基本上由於還是可能存在極為極端狀況在常數時間複雜度演算法上使用 dudect 卻判斷為非常數，10 次是否能計算信心指數，又要怎麼設計實驗找出誤判率 ?
2. 臨界點的判斷怎麼來的 ?
3. 說好的雙尾檢定呢 ? 我只看到判斷後面閘值啊 ?
## 作業要求
- [x] GitHub Fork
- [x] 修改 queue.c/h & q_sort
- [x] 運用 Valgrind 排除 qtest 實作的記憶體錯誤，並透過 Massif 視覺化 “simulation” 過程中的記憶體使用量，需要設計對應的實驗
- [x] 研讀論文 Dude, is my code constant time?，解釋本程式的 “simulation” 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 Student’s t-distribution 及程式實作的原理。注意：現有實作存在若干致命缺陷，請討論並提出解決方案;
- [ ] 實驗設計
- [ ] 抱歉了挑戰題，我真的很需要睡眠這個酷東東，我們下輪再見
Sign in with Wallet
Connect another wallet