2019-12-22

Security►CTF

justCTF 2019 Writeup

Link: https://2019.justctf.team/

這算是我第一場（比較認真打的）CTF 比賽，於是來發一個公開的 writeup 吧！

我和 3 個同學組隊參加這場比賽，順便當成計算機安全課程 Final CTF 的賽前練習。

Sanity check

這場比賽的簽到題，雖然說是簽到題，雖然算是簽到題但 flag 也沒那麼好找啦！discord 上面就有一些人哀嚎解不出這題 😂。

這題的 flag 其實就是在比賽規則中寫的範例 flag：justCTF{something_h3re!}，還好我看規則時有試著把範例 flag 貼上去看看，所以沒被這題卡住 :) 。

Will it stop?

題目大意

這題的概念大概是：把你的 code 傳上對方的伺服器，然後它會幫你編譯。就 PDF 中的故事而言，它理論上還會在伺服器上執行你的程式，但實際上假如你上傳一個能夠成功編譯的程式碼上去，linker 會報錯（根據 discord，這是正常的），所以這題是要你在 compile 階段去攻下 flag。

解題過程

這是我一開賽就看的題目，那時候也沒注意到這題的難度被歸類為 Medium 而非 Easy，覺得有趣就看了。

看到這題我就馬上想到用 #include "path/to/flag" 的方式來讓我輸出機器上的檔案，然而我卻猜不到 flag 在哪裡。根據題目中的提示，flag 在使用者的家目錄，然而我卻沒辦法猜出使用者名稱，我試著研究了一些 GCC 的 pragma，沒有一個能夠幫助我找到使用者名稱或工作目錄等有用的資訊。

星期六晚上回來和隊友討論這題（當天下午有別的事情就沒參賽），隊友建議我看看 /etc/passwd，於是就輕鬆看到了以下資訊（使用者名稱）：

How many lines does your C program parsing a Python code have?
1
Write your program now:
#include "/etc/passwd"
Ok, let's build it!
In file included from <stdin>:1:0:
/etc/passwd:1:8: error: expected '=', ',', ';', 'asm' or '__attribute__' before ':' token
 aturing:x:1000:1000::/home/aturing:/bin/sh
        ^
COMPILATION FAILED

起初，我其實嘗試過 include /proc/self 底下的東西，但找不到檔案，接著就沒繼續嘗試 include 系統文件了。果然有隊友討論很重要，否則這題卡在這點上就太虧了！

2019-05-05

Machine Learning

Keras Embedding Layer 搭配 gensim Word2Vec 用法

在使用 RNN (Recurrent Neural Network) 做文字相關的處理時，我們可以利用 gensim 的 Word2Vec 將一個詞彙轉成一個向量表達。

一個簡單的作法是，將 training data 和 testing data 資料裡的那些詞彙以對應的向量取代，然而這樣會很佔記憶體，以我目前的作業為例（2019 李宏毅機器學習作業6，這次作業資料是不公開的），training data + testing data 約 20 MB 但經過 Word2Vec 的轉換後就變成超過 10 GB 了，不僅執行速度慢，甚至電腦上根本不會有那麼多的記憶體。

為了避免這個問題，我們會將 Word2Vec 中的詞彙做個編號(index)，接著將 training / testing data 中的資料以這個編號取代，在 keras 上訓練時，我們則需要將 index 到 vector 的對應傳入（w2v_model.wv.vectors提供了這個對應，以下稱之index2vec）。

用法範例: https://gist.github.com/domen111/64cb6628cd57c2ffa4f91024ba6190ae

接著在 keras 上需要利用 keras.layers.Embedding來把index2vec傳入，keras.layers.Embedding參數如下：

1	keras.layers.Embedding(input_dim, output_dim, embeddings_initializer='uniform', embeddings_regularizer=None, activity_regularizer=None, embeddings_constraint=None, mask_zero=False, input_length=None)

在 model 的第一層加入：

1	model.add(Embedding(index2vec.shape[0], index2vec.shape[1], weights=[index2vec], trainable=False))

weights指定要把每個詞彙 Embedding 成什麼，也就是我們的 index2vec 表格，input_dim指定字典的大小，output_dim指定向量的長度。

2016-09-19

Competitive Programming►Introduction

Online Judge 基礎觀念：多測資輸入不需把資料都讀入後再輸出

有的題目會要求一次輸入多筆測資，例如：
TOJ 3
NTU judgegirl 80

常見初學者的寫法會將所有的資料讀入，存進陣列裡面，一個一個處理完之後再輸出。

但事實上不需要這麼做，你只需要每次讀入一個一組測資，直接輸出答案就行了！完全不需要浪費額外記憶體去開陣列。
以 TOJ 5 為例：

#include <stdio.h>
int gcd(int a,int b){/*略*/}
int main()
{
	int T;
	scanf("%d",&T);
	for(int i=0;i<T;i++)
	{
		int a,b;
		scanf("%d %d",&a,&b);
		printf("%d",gcd(a,b));
	}
}

題目的output不是要求要一次輸出所有答案嗎？事實上並不是的。在你電腦裡面的terminal（或者cmd）中，輸入和輸出會有即時的互動，也就是說當你打完每一組測試資料，它就會立刻輸出答案，因此你會看到輸入和輸出湊在一起的情況。

在 Online Judge 中，輸入和輸出可以當成兩個檔案，因此先後順序是沒有關係的。
在你的電腦中，可以在terminal模擬類似的環境：

開啟terminal（在windows上則是cmd）。
使用cd命令切換到測資和執行檔所在的資料夾。
把要輸入的測試資料存成一個文字檔，例如input.txt，
執行以下命令：執行檔 < input.txt > output.txt 或者 執行檔 < input.txt，此處使用了 io redirection 的技巧，細節可以自行上網查詢。

我們把input.txt作為程式的輸入資料，輸出的資料則存在output.txt，在 Online Judge 中也是使用類似的方法實作。

2016-04-14

Competitive Programming►Problems

UVa 1569 - Multiple

Link: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4351

自己想不出這題，網路上題解也不多，後來研究了這篇的code才知道怎麼寫。

解法

想個暴利的解法，把題目給定的M個數字排序後，用這些數字去組合，BFS搜索下去(必須用BFS去搜索才會優先找到較小的數字)，搜索的過程一邊模N就能判斷最後是不是N的倍數(搜索完成)。
不過這樣的作法複雜度是指數級別的，而且沒辦法判斷是不是找不到答案(需輸出0)。

接著我們可以發現一件事，假設某兩個狀態模N後是一樣的，則由他們到答案的路徑也是一樣的，所以他們之間較晚搜索到的數字可以直接忽略，因此狀態只剩下N種，紀錄一下哪個模數出現過即可。

2016-04-11

Competitive Programming►Problems

TIOJ 1272 - The Agency

Link: http://tioj.ck.tp.edu.tw/problems/1272

用DFS入出順序做樹壓平，壓平後用資料結構維護即可。

可以用支援區間修改單點查詢的線段樹維護，不過這裡我用BIT。

2016-04-10

Competitive Programming►Introduction

Google Code Jam 賽制介紹

解題 / 大小測資

每題有分大小測資，解題時下載輸入測資檔，並上傳輸出答案
我習慣使用 出入重導向 的方式，或者也可以直接在程式碼裡面寫成 file i/o
小測資 下載後必須在4分鐘內上傳答案，若答案錯誤或超時未上傳，會被加4分鐘的penalty(如果最後這題AC的話)，上傳後會立刻知道是否正確

2016-04-03

Competitive Programming►Problems