王　寧,李潤東

(湖南工程學(xué)院 計(jì)算機(jī)與通信學(xué)院，湘潭 411104)

?

OnlineJudge中反抄襲機(jī)制的研究和實(shí)現(xiàn)

王寧,李潤東

(湖南工程學(xué)院 計(jì)算機(jī)與通信學(xué)院，湘潭 411104)

OnlineJudge中的反抄襲機(jī)制可以檢測到其在使用過程中的作弊現(xiàn)象，為了更深入地了解OnlineJudge的反作弊的實(shí)現(xiàn)原理，以HUSTOJ(眾多OJ中的一種)為研究對象，剖析其中的SIM相似度檢測軟件的運(yùn)行機(jī)制，以及在HUSTOJ中實(shí)現(xiàn)反作弊的方法.實(shí)驗(yàn)結(jié)果直觀的表明了SIM相似度檢測軟件的有效性.

OnlineJudge；反抄襲；HUSTOJ；SIM；相似度檢測

OnlineJudge[1]，即在線評判系統(tǒng)(簡稱OJ),被廣泛的運(yùn)用到現(xiàn)代教育教學(xué)中，尤其是在計(jì)算機(jī)類的學(xué)科的教學(xué)中，老師將題目發(fā)布到OJ系統(tǒng)中去，學(xué)生通過web端提交代碼至服務(wù)器，服務(wù)器接受到用戶提交的代碼之后，進(jìn)行編譯、運(yùn)行、評判后將結(jié)果返回給web端，將結(jié)果非常直觀的反饋給學(xué)生.

OJ系統(tǒng)方便了老師的教學(xué)，但是有些學(xué)生將別人的代碼進(jìn)行修改之后提交給OJ，這就產(chǎn)生了作弊的現(xiàn)象，這就阻礙了OJ系統(tǒng)在教學(xué)中的應(yīng)用，因此需要一套可以對提交的代碼進(jìn)行相似度檢測工具來杜絕此類現(xiàn)象的發(fā)生.HUSTOJ[2]，是眾多OJ中的一種，它使用開源的SIM軟件[3-4]來對代碼進(jìn)行相似度的檢測，很好的解決了這個(gè)問題.

圖1　HUSTOJ

1　SIM介紹

1.1相似度檢測的常用方法

相似度檢測一般有如下兩種方法[5]：

1.1.1屬性計(jì)數(shù)法

屬性計(jì)數(shù)法通過提取兩段代碼中的運(yùn)算符，操作符，行數(shù)，字符數(shù)，程序注釋等相關(guān)屬性的數(shù)量，并將它們表示為N元組，對N元組進(jìn)行規(guī)范化，并計(jì)算他們的歐幾里得距離，由此來判斷源碼的相似度.缺點(diǎn)：如果抄襲者加入一些多余的關(guān)鍵字，變量，甚至一些冗余的源碼，系統(tǒng)便很難檢測，而對于不屬于抄襲甚至完全不相關(guān)的源碼，由于屬性個(gè)數(shù)相近的原因可能存在較大的誤判概率.

1.1.2結(jié)構(gòu)度量法

結(jié)構(gòu)度量法從程序的結(jié)構(gòu)上進(jìn)行分析，避開了任何冗余代碼，主要分2個(gè)步驟：

(1)首先對源碼進(jìn)行詞法或語法分析并產(chǎn)生符號序列，在此過程中將同義詞映射為統(tǒng)一的形式，將自定義的標(biāo)識(shí)符轉(zhuǎn)換為標(biāo)準(zhǔn)符號，刪除空白符號和注釋，將大小寫字母轉(zhuǎn)化為小寫等；

(2)采用相關(guān)字符串匹配技術(shù)比較前面產(chǎn)生的符號序列，并求出其相似度.

1.2SIM工作原理

1.2.1SIM的工作方法

SIM屬于結(jié)構(gòu)度量法，首先，SIM將提交的源代碼用linux下的Lex詞法分析工具[6]進(jìn)行壓縮，Lex將源代碼轉(zhuǎn)換成相應(yīng)的標(biāo)識(shí)符(token)，轉(zhuǎn)化之后的標(biāo)識(shí)符很容易的被后續(xù)階段處理，源代碼就表示成為了另外一種緊縮的格式，并建立相應(yīng)的向前引用表，再采用一種檢測DNA序列相似性的算法，將壓縮串分成若干份，將每份壓縮串與另外的壓縮串中進(jìn)行匹配，匹配出來的子串將被刪除，直到不出現(xiàn)匹配的子串為止.在OJ中，系統(tǒng)只將當(dāng)前用戶與對應(yīng)題目的以往用戶的正確代碼進(jìn)行匹配，如果相似度達(dá)到某個(gè)閥值，就會(huì)在相對應(yīng)的數(shù)據(jù)庫中留下相關(guān)的記錄.

1.2.2SIM軟件中主要文件以及作用

sim.c獲得命令行參數(shù)，檢查參數(shù)，初始化語言，預(yù)計(jì)算表.

compare.c進(jìn)行比較

tokenarray.c使用lex對輸入進(jìn)行處理.TokenArray[]記錄著所有輸入的標(biāo)識(shí)符.

pass1.c讀取文件

pass2.c找到每個(gè)運(yùn)行線程的確切位置

pass3.c打印出相似度.

1.2.3SIM軟件的工作步驟

(1)文件讀取

用Lex詞法分析工具對每個(gè)文件的輸入進(jìn)行標(biāo)識(shí).每個(gè)標(biāo)示占一個(gè)字節(jié)，可能會(huì)占滿8位.標(biāo)識(shí)符存儲(chǔ)在TokenArray[]這個(gè)數(shù)組里面，如果溢出了，那么再分配內(nèi)存.為了盡可能的優(yōu)化pass2，一個(gè)辦法就是去記住每行開始的那個(gè)標(biāo)識(shí)符的位置.標(biāo)識(shí)符的位置存儲(chǔ)在nl_buff[]這個(gè)數(shù)組里面，如果一樣，也可以進(jìn)行再分配.如果由于缺少內(nèi)存而失敗，nl_buff[]會(huì)被舍棄，pass2會(huì)繼續(xù)的讀取文件.

(2)建立向前引用表

文本通過對每個(gè)子串和它右邊的子串來進(jìn)行比較，通過hash表可以更加的快速的去執(zhí)行.一旦整個(gè)文本被讀入，一張向前引用表就被建立.

(3)確定運(yùn)行線程的集合

如果在一個(gè)新文件中，在給定的位置找到一個(gè)正確的運(yùn)行，就調(diào)用add_run()函數(shù)，跳過這個(gè)新文件，阻止重復(fù)的運(yùn)行.

(4)確定每個(gè)運(yùn)行的線程的確切的位置

(5)按順序打印出的結(jié)果

2　反抄襲在HUSTOJ中的實(shí)現(xiàn)

2.1HUSTOJ的運(yùn)行機(jī)制

在HUSTOJ中，web端和core的連接方式默認(rèn)是通過數(shù)據(jù)庫連接 ，交互的過程主要是以下四個(gè)步驟：

(1)有新的代碼提交至服務(wù)器時(shí)，web端向solution表中插入記錄;

(2)core輪詢solution表，當(dāng)發(fā)現(xiàn)有新的記錄時(shí)執(zhí)行相應(yīng)的操作;

(3)core更新solution表的result字段;

(4)web端輪詢solution表將result字段顯示出來.

流程圖如圖2所示.

圖2　HUSTOJ工作流程圖

2.2在HUSTOJ中啟用SIM

在HUSTOJ的配置文件中有一個(gè)OJ_SIM_ENABLE=1的配置項(xiàng)，用來確定是否使用SIM進(jìn)行代碼相似度的檢測.

有一個(gè)專門的sim表存放著相關(guān)的信息，如圖3所示.

圖3　sim表結(jié)構(gòu)

如果啟用了這個(gè)配置項(xiàng)，那么core在進(jìn)行處理的時(shí)候，會(huì)調(diào)用SIM來進(jìn)行代碼相似度的檢測，并將結(jié)果更新至sim表中.

Core中使用SIM去進(jìn)行代碼相似度檢測的關(guān)鍵代碼如下:

intget_sim(intsolution_id,intlang,intpid,int&sim_s_id) {

charsrc_pth[BUFFER_SIZE];

//charcmd[BUFFER_SIZE];

sprintf(src_pth, "Main.%s",lang_ext[lang]);

intsim=execute_cmd("/usr/bin/sim.sh%s%d",src_pth,pid);

if(!sim) {

execute_cmd("/bin/mkdir../data/%d/ac/",pid);

execute_cmd("/bin/cp%s../data/%d/ac/%d.%s",src_pth,pid,solution_id,

lang_ext[lang]);

//ccppwill

if(lang== 0)

execute_cmd("/bin/ln../data/%d/ac/%d.%s../data/%d/ac/%d.%s",pid,

solution_id,lang_ext[lang],pid,solution_id,

lang_ext[lang+ 1]);

if(lang== 1)

execute_cmd("/bin/ln../data/%d/ac/%d.%s../data/%d/ac/%d.%s",pid,

solution_id,lang_ext[lang],pid,solution_id,

lang_ext[lang- 1]);

}else{

FILE*pf;

pf=fopen("sim", "r");

if(pf) {

fscanf(pf, "%d%d", &sim, &sim_s_id);

fclose(pf);

}

}

if(solution_id<=sim_s_id)

sim= 0;

returnsim;

}

當(dāng)用戶提交代碼給服務(wù)器的時(shí)候，core讀取配置文件，如果在配置文件中啟用了SIM相似度檢測，那么core在判題的過程中調(diào)用以上代碼，調(diào)用/usr/bin/sim.sh來進(jìn)行代碼相似度的檢測，當(dāng)發(fā)現(xiàn)是抄襲的代碼時(shí)，講結(jié)果記錄到數(shù)據(jù)庫中.

3　實(shí)驗(yàn)結(jié)果

在實(shí)驗(yàn)過程中，我們將已經(jīng)通過的代碼進(jìn)行如下的“抄襲”的處理.

已經(jīng)通過的代碼：

#include

intmain()

{

inta[5],i,j,max;

for(i=0;i<5;i++)

{

scanf("%d",&a[i]);

}

for(j=0;j<5;j++)

{

for(i=0;i<5-j-1;i++)

{

if(a[i]>a[i+1])

{

max=a[i];

a[i]=a[i+1];

a[i+1]=max;

}

}

}

for(i=0;i<5;i++)

{

printf("%d",a[i]);

}

printf(" ");

return0;

}

我們對已經(jīng)通過的代碼進(jìn)行兩次處理,處理過的代碼一在其基礎(chǔ)上修改了變量的名稱，結(jié)構(gòu)沒有變，預(yù)測是完全抄襲；處理過的代碼二在其基礎(chǔ)上修改了變量名以及程序的結(jié)構(gòu)，預(yù)測屬于部分抄襲.

將處理過的代碼提交給OJ系統(tǒng)，web端顯示的結(jié)果如下：

然后查看數(shù)據(jù)庫中的sim表中的記錄：

可以很清楚的看出處理過的代碼一的相似度是100，處理過的代碼二的相似度是92，結(jié)果是比較準(zhǔn)確的.

由結(jié)果可以得出結(jié)論，在HUSTOJ中，SIM可以有效的去對用戶提交上來的源代碼進(jìn)行相似度檢測！

4　結(jié)束語

通過對OnlineJudge中所采用的反作弊機(jī)制的

分析， 以及實(shí)驗(yàn)?zāi)M， 可以看出SIM代碼相似度檢測軟件可以很好的去解決用戶在使用OJ的過程中存在的抄襲現(xiàn)象，可以有效的減少抄襲現(xiàn)象的發(fā)生.

[1]陳榮欽,胡永良,應(yīng)建健,郭賢海. 在線評測系統(tǒng)中的源碼相似度檢測研究與實(shí)現(xiàn)[J]. 實(shí)驗(yàn)技術(shù)與管理,2014(4):109-111.

[2]張浩斌. 基于開放式云平臺(tái)的開源在線評測系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[J]. 計(jì)算機(jī)科學(xué),2012(S3):339-343.

[3]DickGrune.http://www.dickgrune.com/[EB/OL].

[4]胡正軍. 程序代碼相似度檢測方法研究及應(yīng)用[D].中南大學(xué)碩士學(xué)位論文,2012.

[5]莊奇東,王鍵聞,張楠,張爽,任娜.OnlineJudge系統(tǒng)的優(yōu)化[J]. 計(jì)算機(jī)系統(tǒng)應(yīng)用,2011(8):115-121.

ResearchandImplementofAnti-copyingMechanismonOnlineJudge

WANGNing,LIRun-dong

(CollegeofComputerandCommunication,HunanInsitituteofEngineering,Xiangtan411104,China)

Theanti-copyingmechanismofOnlineJudgecandetectthecheatinginOnlineJudgeduringtheusage.Tostudythetheoryofanti-copyingmechanism,thisarticleusesHUSTOJastheresearchobjecttoanalyzetheoperatingmechanismoftextsimilaritytesterSIMinthesystemandthewayofachievingit.TheresultofexperimentshowstheeffectivenessoftextsimilaritytesterSIM.

OnlineJudge;anti-plagiarism;HUSTOJ;SIM;similaritydetection

2015-09-28

湖南省教育廳普通高等學(xué)校教學(xué)改革研究項(xiàng)目(湘教通[2014]247-414).

王寧(1982-),男,講師,研究方向:無線網(wǎng)絡(luò)及應(yīng)用.

TP393

A

1671-119X(2016)01-0045-04