# DSA 2024 in-class QA memo
## Tasks
### 1. 試圖搞壞 TA 給的 executable

寫程式除了要確保正確性以外，安全性也是很重要的，尤其像 C 這種需要手動進行記憶體管理的程式語言，如果沒有處理好安全性，很可能被拿來做壞事。

我們會給你一個執行檔，是這次題目的sample solution，請你運用寫程式的經驗，生出有機會把程式搞壞（e.g. segmentation fault）的輸入。

如果你生出的測資成功戳到我們期望你找到的安全性錯誤，程式會印出一個 flag，請將獲得的 flags 與戳到該 flag 的測資以**表格**形式整理呈現。

注意：即使戳到錯誤、程式印出flag後程式仍然可以執行是正常的。

若你戳到真的 segmentation fault，也請將戳到的測資附上來（若不方便直接附上請文字描述測資為何），將有 bonus 分數。
### 2. 分析 TA 給的 executable 內部實做的演算法之時間/空間複雜度

同一個 executable，請設計不同數量級的**合法測資**，並將這些測資餵給 executable 後去測量程式執行時間及記憶體用量，最後猜測/分析這個 executable 內部的 **Student set API** 為何種實做方式（猜測的根據為複雜度），並將結果呈現於 report 中

記得附上你是用什麼指令去測量程式執行時間及記憶體用量，以及指令執行結果的截圖。

所有的 operations 都會調用 student set

- register 會用到 `sset_insert`
- withdraw 會用到 `sset_remove`
- check 會用到 `sset_contains`

#### Student set API

#include <stdbool.h>
#ifndef SSET_H
#define SSET_H

typedef struct StudentSet StudentSet;
struct StudentSet {
    /* define any field you need here */
};

void sset_init(StudentSet *set);
void sset_destroy(StudentSet *set);
bool sset_insert(StudentSet *set, const char *value);   // return true if the insertion is successful, false otherwise
bool sset_remove(StudentSet *set, const char *value);   // return true if the removal is successful, false otherwise
bool sset_contains(const StudentSet *set, const char *value);

#endif

### 3. Performance evaluation report

將上述方法應用至 RD 所開發出來的程式上，並將不同數量級的輸入所需要的執行時間/記憶體用量等以**表格**形式整理起來。

記得附上你是用什麼指令去測量程式執行時間及記憶體用量，以及指令執行結果的截圖。
### 4. Correctness testdata generation

請繳交你生出來用以檢查 RD 程式正確性的測試資料。
每筆測資應該包含輸入及**正解**。
（建議正解可以用 python 或 C++ 等語言生）

兩個選項：

交 generator，需附上 README
交手動生成的測資

如果你把 generator 生出來的大量測資交上來，你在這部份會獲得 0 分 :)
### 5. Testbench script

請用 python 或 bash （或任何程式語言）寫出一個可以按照以下步驟進行的 script：

1. Compile C code
2. 執行 executable
3. 從檔案讀入輸入
4. 比較執行檔輸出與正確答案是否一致的
5. 輸出結果

需要附上 README 來告訴我們如何使用你的 script。
#### 參考的執行格式

你還是可以自訂格式，只需要在 README 寫清楚即可。

python：
`python3 ./testbench.py <executable name> <input file> <answer file>`
e.g. `python3 ./testbench.py ./a.out input.txt answer.txt`

bash：
`./testbench.sh <executable name> <input file> <answer file>`
e.g. `./testbench.sh ./a.out input.txt answer.txt`
#### 規定的輸出格式

（這是規定，不是參考）

若無視 trailing spaces 及 empty lines 之後，程式輸出與答案一致，輸出 `Correct`，否則輸出 `Wrong`。
## 提供檔案

1. TA executable
- Arm MacOS: https://drive.google.com/file/d/11hlo1sodqb3sjeqkzyZZzx-ExUc6uFvB/view?usp=sharing

- x86 MacOS:
https://drive.google.com/file/d/1rf-8h043CxX95zjcIHgWtN_VXoLM4xSA/view?usp=sharing

- x86 Linux:
https://drive.google.com/file/d/1Dojb3blDGzRedWxdd-04qfGgIR5AeKsF/view?usp=sharing

- x86 Windows: (很可能被防毒擋，擔心的話請使用下述方法)
https://drive.google.com/file/d/1ZAZ-hGmt5n508afo5X13oPghusT1XAFG/view?usp=sharing

- 使用 CoCalc：（須先下載 x86 Linux 的執行檔）
https://hackmd.io/@voSpYmsMQDG6fs1reqfgpw/rysKlf4bR

2. Flags table
flags.csv

## 繳交檔案

檔案名：teamXX_QA.zip，XX為第幾組，第1~9組請寫01~09
解壓縮後的結構

teamXX_QA
├── flags.csv
├── report.pdf
├── testbench
│   ├── README
│   └── (script)
└── testdata
    ├── (generator)
    │     or
    ├── (1.in)
    ├── (1.out)
    ├── ...
    └── (n.out)

`flags.csv`：同上面所述
`report.pdf`：將分析 TA executable / RD executable 的 report 整理起來。
`testbench`：將 testbench script 及 README 交上來。
`testdata`：同上面所述，generator/手生測資擇一繳交，禁止繳交 generator 生出來的大量測資。

請將 zip 檔繳交到 NTU COOL（兩個 QA 繳交一份就好）, 同時把 report.pdf 繳交到 Gradescope。


### Testbench script 10%

正確 script 得滿分。