基于 LAMP 架構(gòu)的 ACM/ICPC在線評(píng)測(cè)系統(tǒng)設(shè)計(jì)

摘 要 本課題在牡丹江師范學(xué)院已有的在線評(píng)測(cè)系統(tǒng)上進(jìn)行全面重構(gòu)，將 OJ 系統(tǒng)各個(gè)組成部分進(jìn)行解耦，使得 OJ 系統(tǒng)各個(gè)模塊之間獨(dú)立性增強(qiáng)，容易修改現(xiàn)有功能及擴(kuò)充新功能，以應(yīng)對(duì)舉辦比賽時(shí)的訪問(wèn)壓力。包括本課題的系統(tǒng)架構(gòu)設(shè)計(jì)，對(duì)其下各個(gè)模塊核心內(nèi)容的闡述，包括基于 Linux 系統(tǒng)的沙箱模型、基于 Java 的多線程服務(wù)器、基于AMP 架構(gòu)和 MVC 設(shè)計(jì)模式的 Web 前端系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)，以及影響系統(tǒng)安全的各種因素和對(duì)應(yīng)的解決方案。

關(guān)鍵詞 在線評(píng)測(cè)系統(tǒng) ACM/ICPC LAMP 架構(gòu)

中圖分類(lèi)號(hào)：TP311.52 文獻(xiàn)標(biāo)識(shí)碼：A

0 緒論

ACM/ICPC 目的旨在使大學(xué)生運(yùn)用計(jì)算機(jī)來(lái)充分展示自己分析問(wèn)題和解決問(wèn)題的能力。在線評(píng)測(cè)系統(tǒng)(Online Judge System，以下簡(jiǎn)稱 OJ）起到了非常重要的作用。集訓(xùn)隊(duì)員可以在線評(píng)測(cè)系統(tǒng)上挑選各種題目挑戰(zhàn)自我，提高自我，學(xué)習(xí)各種數(shù)據(jù)結(jié)構(gòu)和算法；在統(tǒng)一組織的集中訓(xùn)練中可以通過(guò)指定題目的形式來(lái)強(qiáng)化訓(xùn)練效果；而在線評(píng)測(cè)系統(tǒng)對(duì)比賽功能的支持，進(jìn)一步提高了集訓(xùn)隊(duì)員的學(xué)習(xí)熱情，同時(shí)還可以模擬比賽的環(huán)境，培養(yǎng)那些計(jì)劃參與 ACM/ICPC 賽事的隊(duì)伍的團(tuán)結(jié)合作能力。

但是其中大部分OJ 系統(tǒng)是閉源、封閉的，無(wú)法獲取其源代碼進(jìn)行修改擴(kuò)充以滿足現(xiàn)有需求，牡丹江師范學(xué)院 ACM/ICPC 集訓(xùn)隊(duì)才于 2010 年推出自己的OJ。但是該系統(tǒng)存在幾個(gè)問(wèn)題：一，效率不足，無(wú)法承受每年牡丹江師范學(xué)院程序設(shè)計(jì)大賽預(yù)選賽的壓力；二，由于該系統(tǒng)沒(méi)有應(yīng)用沙箱技術(shù)運(yùn)行用戶代碼，存在安全隱患，可能直接導(dǎo)致服務(wù)器被劫持。此后，Google Code 上陸續(xù)出現(xiàn)了幾個(gè)開(kāi)源 OJ 系統(tǒng)，但是在架構(gòu)設(shè)計(jì)上仍不夠完善，且無(wú)法與原系統(tǒng)的數(shù)據(jù)格式兼容，因此，有必要重新開(kāi)發(fā)一個(gè)經(jīng)過(guò)合理設(shè)計(jì)的新 OJ 系統(tǒng)，從根本上解決上述的問(wèn)題，為集訓(xùn)隊(duì)提供一個(gè)穩(wěn)定可用的學(xué)習(xí)環(huán)境。

1 系統(tǒng)架構(gòu)設(shè)計(jì)

為了方便用戶的使用，本系統(tǒng)采用 B/S 架構(gòu)，只要用戶使用的是有網(wǎng)絡(luò)接入的計(jì)算機(jī)，就可以通過(guò)瀏覽器進(jìn)行訪問(wèn)。根據(jù)該系統(tǒng)的具體情況，在設(shè)計(jì)上將其分為以下四個(gè)組成部分：（1）網(wǎng)站系統(tǒng)（Web 端）；（2）評(píng)測(cè)核心（Judge）；（3）評(píng)測(cè)核心封裝層（Judge Wrapper）；監(jiān)聽(tīng)守護(hù)進(jìn)程（Daemon）。

在設(shè)計(jì)上，該項(xiàng)目將系統(tǒng)的幾個(gè)主要組成模塊充分解耦，一方面，多個(gè)模塊之間可以并行開(kāi)發(fā)；另一方面，各個(gè)模塊解耦后使得系統(tǒng)的修改和擴(kuò)充更加容易，每個(gè)模塊的可重用性也相應(yīng)增強(qiáng)。例如，當(dāng)其他學(xué)校需要實(shí)現(xiàn)一個(gè)功能界面完全不同的 OJ 系統(tǒng)或是作業(yè)平臺(tái)時(shí)，可以直接采用本項(xiàng)目的評(píng)測(cè)核心，避免重復(fù)開(kāi)發(fā)。

2 評(píng)測(cè)核心的設(shè)計(jì)與實(shí)現(xiàn)

作為在線評(píng)測(cè)系統(tǒng)中最核心的部分，尤其是需要監(jiān)控用戶運(yùn)行，需要涉及到很多相關(guān)技術(shù)，特別是與系統(tǒng)底層關(guān)系密切的技術(shù)。在 Linux 下，系統(tǒng)調(diào)用的實(shí)現(xiàn)通常是用戶程序通過(guò)觸發(fā)80號(hào)軟中斷或者執(zhí)行 SYSCALL/SYSENTER 等平臺(tái)相關(guān)的 CPU 指令陷入到內(nèi)核中，內(nèi)核通過(guò)寄存器獲 取用戶程序的輸入，在通過(guò)嚴(yán)格的檢查后執(zhí)行相應(yīng)操作。

在本系統(tǒng)中涉及的主要系統(tǒng)調(diào)用包括 fork、setitimer、execve、wait、ptrace、setrlimit、chroot、setuid 等。

（1）fork 系統(tǒng)調(diào)用通過(guò)復(fù)制調(diào)用進(jìn)程的上下文來(lái)創(chuàng)建一個(gè)新進(jìn)程。（2）setitimer 系統(tǒng)調(diào)用用于設(shè)置定時(shí)器。（3）execve 系統(tǒng)調(diào)用用于載入一個(gè)新的可執(zhí)行程序，替換當(dāng)前進(jìn)程的地址空間。（4）wait 系統(tǒng)調(diào)用允許父進(jìn)程阻塞，直到子進(jìn)程發(fā)生一些事件。（5）ptrace 系統(tǒng)調(diào)用是一個(gè)可以使父進(jìn)程在用戶層攔截和修改系統(tǒng)調(diào)用的函數(shù)，可以監(jiān)控和控制其他進(jìn)程，該函數(shù)還能夠改變子進(jìn)程中的寄存器和內(nèi)核映像，因而可以實(shí)現(xiàn)斷點(diǎn)調(diào)試和系統(tǒng)調(diào)用的跟蹤。（6）setrlimit 系統(tǒng)調(diào)用可以改變進(jìn)程的資源限制。（7）chroot 系統(tǒng)調(diào)用使得調(diào)用進(jìn)程的將某一目錄當(dāng)作其根目錄，以此限制該進(jìn)程及子進(jìn)程對(duì)該目錄外文件的訪問(wèn)。（8）setuid 系統(tǒng)調(diào)用允許進(jìn)程改變其有效用戶 ID。在本系統(tǒng)中，用戶提交的代碼可能存在惡意，對(duì)其編譯后的程序需要運(yùn)行在服務(wù)器上，因此必須對(duì)其進(jìn)行嚴(yán)密的監(jiān)控，防止惡意代碼帶來(lái)的危害。在本系統(tǒng)支持的四種語(yǔ)言中，C、C++、Pascal 三者經(jīng)過(guò)編譯后產(chǎn)生本地代碼，可以通過(guò)Linux 系統(tǒng)調(diào)用（主要是 fork、execve、chroot、setuid 和 ptrace）來(lái)創(chuàng)建一個(gè)沙箱，限制惡意代碼訪問(wèn)文件、控制系統(tǒng)的權(quán)限，尤其是通過(guò) ptrace 來(lái)限制可使用的系統(tǒng)調(diào)用，在很大程度上保證了系統(tǒng)的安全。

運(yùn)行時(shí)檢測(cè)是最重要、最復(fù)雜的運(yùn)行時(shí)監(jiān)控機(jī)制。本系統(tǒng)中通過(guò) ptrace 系統(tǒng)調(diào)用來(lái)監(jiān)控用戶進(jìn)程。每當(dāng)用戶進(jìn)程出發(fā)一個(gè)系統(tǒng)調(diào)用，或者是收到某些信號(hào)的時(shí)候，用戶進(jìn)程會(huì)將控制權(quán)暫時(shí)移交給監(jiān)控核心。監(jiān)控核心將嚴(yán)格監(jiān)控用戶進(jìn)程的各項(xiàng)參數(shù)，以保證其不執(zhí)行危害系統(tǒng)安全的操作：（1）檢查程序是否正常退出。（2）檢查程序是否收到了非正常的信號(hào)。（3）通過(guò)進(jìn)程的缺頁(yè)中斷次數(shù)計(jì)算進(jìn)程使用的內(nèi)存資源是否超出限制。（4）檢查進(jìn)程系統(tǒng)調(diào)用是否合法。

在以上四項(xiàng)檢測(cè)都不存在問(wèn)題的情況下，用戶進(jìn)程才能繼續(xù)執(zhí)行。

由于題目根據(jù)其合法結(jié)果數(shù)量可以分成普通類(lèi)型和 Special Judge 類(lèi)型，因此針對(duì)不同的類(lèi)型，需要分別對(duì)其進(jìn)行判斷。（1）普通類(lèi)型的題目，其合法結(jié)果唯一，因此只需要簡(jiǎn)單判斷用戶程序與標(biāo)準(zhǔn)答案的一致性即可。（2）Special Judge 類(lèi)型的題目，在本系統(tǒng)中，約定了 SPJ 程序的名稱以及數(shù)據(jù)的傳遞方式，包括標(biāo)準(zhǔn)輸出、用戶輸出，以及 SPJ 程序的數(shù)據(jù)，由評(píng)測(cè)核心調(diào)用 SPJ 程序來(lái)完成最后的評(píng)判過(guò)程。

3 評(píng)測(cè)核心層的設(shè)計(jì)與實(shí)現(xiàn)

每當(dāng)用戶提交一份新的代碼，Wrapper 即會(huì)被調(diào)用，從數(shù)據(jù)庫(kù)中獲取代碼的詳細(xì)信息。在此階段需要關(guān)注的信息主要包括：（1）用戶提交的代碼本身及其關(guān)鍵屬性（如語(yǔ)言類(lèi)型）。（2）此代碼的提交用戶類(lèi)型，是普通用戶還是管理員。（3）此代碼所屬的題目是否處于正在進(jìn)行的比賽。（4）此代碼是否已經(jīng)被評(píng)測(cè)過(guò)。

根據(jù)評(píng)測(cè)核心在設(shè)計(jì)上的約定，封裝層需要通過(guò)命令行的方式提供多個(gè)參數(shù)，包括語(yǔ)言類(lèi)型、源文件路徑、題號(hào)、數(shù)據(jù)目錄、臨時(shí)目錄、時(shí)間限制、內(nèi)存限制、輸出限制等。根據(jù)評(píng)測(cè)核心在設(shè)計(jì)上的約定，以其返回值和輸出來(lái)標(biāo)識(shí)一次評(píng)測(cè)的結(jié)果。如果核心的返回值非0，表示在評(píng)測(cè)過(guò)程中出現(xiàn)錯(cuò)誤，屬于系統(tǒng)錯(cuò)誤；否則可以從核心的輸出字符串中讀取出運(yùn)行結(jié)果、內(nèi)存占用、時(shí)間占用等信息。

4 監(jiān)聽(tīng)守護(hù)進(jìn)程的設(shè)計(jì)與實(shí)現(xiàn)

監(jiān)聽(tīng)守護(hù)進(jìn)程（Daemon）采用了一個(gè)事件驅(qū)動(dòng)模型：每當(dāng)用戶提交代碼時(shí)，Web 端主動(dòng)通知 Daemon，Daemon 載入評(píng)測(cè)核心封裝層，以觸發(fā)一個(gè)完整的評(píng)測(cè)流程。這樣的事件驅(qū)動(dòng)模型使得 Daemon 的運(yùn)行更加有效率，且能夠及時(shí)響應(yīng)請(qǐng)求。由于 TCP 協(xié)議提供了面向連接且可靠的通信服務(wù)，而服務(wù)器采用了事件驅(qū)動(dòng)機(jī)制，因此，完成一個(gè) TCP 服務(wù)器來(lái)實(shí)現(xiàn) Daemon，是一個(gè)最簡(jiǎn)單且合適的方案。由于 Java 提供的 Socket、線程等庫(kù)都對(duì)系統(tǒng)底層提供的響應(yīng)機(jī)制進(jìn)行了比較完善的封裝，同時(shí)在語(yǔ)言層次上提供了線程之間的同步和互斥機(jī)制，因此，本系統(tǒng)采用 Java 進(jìn)行開(kāi)發(fā)，能夠使 Daemon 運(yùn)行得更穩(wěn)定。

5 結(jié)論

本課題實(shí)現(xiàn)的在線評(píng)測(cè)系統(tǒng)目前已完成，并運(yùn)行在牡丹江師范學(xué)院 ACM/ICPC 集訓(xùn)隊(duì)的服務(wù)器上，為所有 ACM/ICPC 參與者與其他程序設(shè)計(jì)愛(ài)好者提供服務(wù)。最終實(shí)現(xiàn)版本在面對(duì)全面的單元測(cè)試和大量的用戶盲測(cè)，穩(wěn)定高效地通過(guò)了各種正確、不正確及攻擊性用戶程序的測(cè)試，并且保證了系統(tǒng)安全，達(dá)到了預(yù)期的目標(biāo)。

參考文獻(xiàn)

[1] [美]W.Richard Stevens， Stephen A. Rago著.UNIX 環(huán)境高級(jí)編程（第二版）[M].尤晉元，張亞英，戚正偉，譯.機(jī)械工業(yè)出版社，2006.

[2] [美]Erich Gamma， Richard Helm， Ralph Johnson， John Vlissides著.設(shè)計(jì)模式：可復(fù)用面向?qū)ο筌浖幕A(chǔ)[M].李英軍，馬曉星，蔡敏，劉建中等譯.機(jī)械工業(yè)出版社，2000.

[3] [美]Samuel P.Harison III， Guy L. Steele Jr著.C語(yǔ)言參考手冊(cè)[M].邱仲潘等，譯.機(jī)械工業(yè)出版社，2003.

[4] 王歡，楊樹(shù)青著.Linux 環(huán)境下 C 編程指南[M].清華大學(xué)出版社，2007.

[5] 王騰，姚丹霖.Online Judge 系統(tǒng)的設(shè)計(jì)開(kāi)發(fā)[J].計(jì)算機(jī)應(yīng)用與軟件，2006(12).

[6] 周高嶔.基于白箱測(cè)試的源代碼在線評(píng)測(cè)系統(tǒng)[D].北京化工大學(xué)，2005.