在批改娘上爬到排行榜首的小技巧

從一個小漏洞帶你從原始碼理解沙盒的實作細節！

某天在隨意瀏覽 JudgeGirl 的時候，意外發現某些新手題的排行榜有些異狀：

Statistic | Judge Girl

這屆的新生好像都有點厲害啊。不對不對，當一隻程式連啟動都需要 30 ms 左右的時候，用同一個編譯參數的這些程式是怎麼做到讀完測資、算完答案輸出然後離開的？

幸好批改娘在 AC 了一道題目之後就能看到所有傳送到這個題目的程式碼。看了程式碼之後大概知道做法很簡單，就是在 main 的開頭加上一個 fork()。系統程式課上應該會介紹，如果這個函數呼叫成功的話，程式會在此一分為二：產生一隻新的程序，並在這裡回傳 0，本來的程序稱為父程序，則會回傳 pid (> 0)。接著，讓父程序正常離開，像這樣：

#include <unistd.h>  /* fork */
int main() {
  if (fork() != 0) return 0;
  /* your other code goes here... */
}

「怎麼可以這樣寫呢？」你的系統程式課老師皺著眉頭問。沒錯，這是一個錯誤的寫法，通常子程序要先結束，由父程序呼叫 wait() 來等待並讓核心釋放其資源，可是這裡的子程序還在執行，父程序卻先結束了。這個「孤兒」會被一個特別的程序接管，這個程序的 pid 為 1，名稱通常為 init。然而，一提交到 JudgeGirl 以後，

神奇的事情發生了！

為了解釋到底發生了什麼事，在此節錄批改娘沙盒端的程式碼如下 (經 clang-format 格式化並加上註解)：

首先用來運行待評測程式的函式如下：

static void do_slave(char *argv[]) {
  /* ... */
  assert(setgid(NOGROUP) == 0);
  assert(setuid(NOBODY) == 0);
  struct rlimit rlim;
  /* 設定最大子程序數量，NPROC_LIMIT 是一個自定義的 macro，預設為 1024 */
  rlim.rlim_max = NPROC_LIMIT;
  rlim.rlim_cur = rlim.rlim_max;
  assert(setrlimit(RLIMIT_NPROC, &rlim) == 0);
  /* 先暫停 (STOPPED)，等待開始計時後才喚醒 */
  assert(raise(SIGSTOP) == 0);
  /* 設定 scheduler 為 FIFO，
     且優先序為次高，僅低於 master；
     這個值通常是 98 */
  {
    struct sched_param param;
    param.sched_priority = sched_get_priority_max(SCHED_FIFO) - 1;
    assert(sched_setscheduler(0, SCHED_FIFO, &param) == 0);
  }
  /* 開始運行受測程式。
     如果成功的話控制權就不會再回來了，
     回傳任何東西都是不應該發生的。
     其實可以在 execvp() 後直接 assert(0) 就好 XD */
  assert(execvp(argv[0], argv) != -1 && 0);
}

再來是檢測、回報上面這個子程序的狀態的函式：

static void do_master(int TL, long long ML) {
  /* ... */
  int status;
  /* 等到 child 停下來 */
  assert(waitpid(slave, &status, WUNTRACED) == slave);
  /* 確定 child 的狀態變成 STOPPED */
  assert(WIFSTOPPED(status) && WSTOPSIG(status) == SIGSTOP);
  /* 設定計時器，開始計時 */
  signal(SIGALRM, handler);
  unsigned int t = GetTickCount();
  alarm(TL);
  /* 讓 child 繼續執行 */
  assert(kill(slave, SIGCONT) == 0);
  /* 停在這裡直到 child 離開 */
  assert(waitpid(slave, &status, 0) == slave);
  /* 解除計時器，算經過的時間 */
  alarm(0);
  t = GetTickCount() - t;
  /* 對其他沙盒內殘餘的程序傳送 SIGTERM，令其終止 */
  dummy(system("killall -u nobody"));
  /* ... */
}

的確，父程序在極短的時間內被終止了，t 會紀錄到父程序存活的時間。但子程序這時候還默默地在運作，且因為被設定 real-time priority 為 98 的關係， killall 會經過相當可觀的時間才將 SIGTERM 遞送 (deliver) 給子程序，這幾十到幾百毫秒通常夠讓子程序把解答輸出完畢，然後若無其事地退出了。

更有趣的是，就算超時也完全不會觸發到 TLE 或 RE，因為計時完之後 alarm 就被解除了，而且父程式的確是正常終止的。至於記憶體用量的部分，通常不會觸發 MLE ，因為計算記憶體用量的時候子程序還沒結束，所以算到的記憶體是運行到一半的 (父+子) 的總記憶體而已 (還記得 fork 的時候是 copy-on-write 嗎？)。然而由於設置了 memory control group 的關係，子程序在用盡記憶體上限的時候仍然會被強制終止，但父程序不會知道，自然無法觸發 MLE 或 RE。這裡可以看到，善用作業系統提供的安全機制，能在更低的層面上保護資源，即使業務邏輯不幸出錯，也不至於曝露出難以收拾的安全漏洞。

附帶一提，通常無法 AC 是因為答案還來不及輸出完就被終止掉而造成 WA。

解法之一：PID namespace

NeoHOJ 的做法是開一個 PID namespace，並且讓受測程式在這個 namespace 下的 pid = 1，也就是擔任 init 的角色。依照 Linux 核心的設計，pid = 1 的程序，核心會特別處理，不論是否在 namespace 下皆適用：

(以下引文節錄自 pid_namespaces(7))

If the "init" process of a PID namespace terminates, the kernel terminates all of the processes in the namespace via a SIGKILL signal. This behavior reflects the fact that the "init" process is essential for the correct operation of a PID namespace. In this case, a subsequent fork(2) into this PID namespace fail with the error ENOMEM; it is not possible to create a new process in a PID namespace whose "init" process has terminated. […]

只要 init 終止，其他任何程序就會立刻收到 SIGKILL，而且這個 signal 無法被捕捉，從而確保了整個 PID namespace 的所有子程序都會立刻被終止。這樣，測 init 存活的時間才會真正代表整個程序存活的時間。

然而這些特性會造成別的問題。考慮以下程式碼：

思考：raise 一定會等到訊號被傳遞給自己才繼續執行，為何這隻程式在 PID namespace 會進入無窮迴圈？

這時候要留意到另一個特性：

Only signals for which the “init” process has established a signal handler can be sent to the “init” process by other members of the PID namespace. This restriction applies even to privileged processes, and prevents other members of the PID namespace from accidentally killing the “init” process.

只有在有建立對應的處理常式 (handler) 的時候，init 才有機會捕捉到 signals，除此之外的 signal 都會被忽略，這麼做是為了增加 init 的相容性，不會收到有定義但未考慮到的 signal 而莫名其妙死掉。

因為 SIGKILL 天生就不能被捕捉，這段程式碼怎麼改都是徒勞無功。但其他大部分的 signals，像是輸出太長造成管線中斷 (broken pipe) 而生的SIGPIPE，就應該要被妥善處理了。於是，我們勢必要自己寫一個 init，然後讓這個 init 建立子程序執行受測程式，至於其他 init 應該具有的特性，可以參考 nsjail 的 dummy init process。

可惜這部分還沒實作到 NeoHOJ 上 (大哭)。

結語 (WIP)

NeoHOJ 所用的核心 nsjail，筆者拜讀完其程式碼及梳理其架構後，認為是十分優秀的系統程式設計參考教材，若有時間會再撰文和大家分享這一年多來的開發過程。反觀 JudgeGirl 的實作策略雖然十分縝密，但大部分程式碼都是作者獨立開發完成，缺乏真實情境的整合測試，智者千慮必有一疏，難免被系統程式設計的修課強者在不經意間發現破綻。或者說，寫 judge 本來就是系統程式設計實務，最 hardcore 的那種。但筆者一時之間也想不到簡易的修補方式，再有勞各位熟悉系統程式設計的各位讀者幫忙發 PR 了。

最後，歡迎來 NeoHOJ 測試：https://hoj.kuang0.me/

也歡迎到 GitHub 查看後端的原始碼！

如果你覺得這篇文章有幫助到你，你可以自由捐獻到以下以太坊地址，用於補貼伺服器營運所需費用：0x5FAC38F0D21F324f066F0C60AF2E9AD7b3bcAC4F

後記

文章寫好之後再打開連結一看，發現那些用這個技巧的排行都被刪掉了的樣子 (變成 100 分的 RE)。好吧，文章拖太久，不過還好圖有事先截，證明我所言不虛 XD。

(2019/12/16 更新) 忘記提到，對其他 judge 最簡單的解法就是用 seccomp-bpf 等核心提供的機制，直接禁止使用者呼叫 fork，但在 JudgeGirl 上這不可行，是因為裡面有一些平行程式設計的題目就需要多個程序 (執行緒)。

(2020/2/11 更新) 後端增加一個 fork 的文字檢查，可以參考這個 commit。