張華++周學(xué)權(quán)++張淼++鄭宏珍++初佃輝

摘 要計算機(jī)實(shí)驗(yàn)教學(xué)平臺是現(xiàn)代實(shí)驗(yàn)教學(xué)改革的一個重要內(nèi)容。然而，在以往的實(shí)驗(yàn)教學(xué)模式中，僅憑教師檢查很難發(fā)現(xiàn)學(xué)生作業(yè)是否抄襲。為了解決此問題，本文將基于數(shù)字指紋的代碼相似度檢測算法應(yīng)用到程序設(shè)計實(shí)驗(yàn)教學(xué)平臺中。實(shí)踐表明，學(xué)生之間的抄襲現(xiàn)象得到控制，教師的評判工作量也大大降低。

【關(guān)鍵詞】相似度檢測 實(shí)驗(yàn)教學(xué) 代碼抄襲

1 計算機(jī)實(shí)驗(yàn)教學(xué)中存在的問題

在程序設(shè)計、數(shù)據(jù)結(jié)構(gòu)與算法等課程的實(shí)驗(yàn)教學(xué)中，部分學(xué)生由于沒有學(xué)好課程或者出于其他目的，會抄襲其他同學(xué)的作業(yè)。在這種情況下，教師在檢查學(xué)生實(shí)驗(yàn)作業(yè)的同時，還要在大量的作業(yè)中檢查抄襲現(xiàn)象，這無疑地增加了教師的工作量，有時甚至很難通過手工操作完成。因此，實(shí)現(xiàn)代碼相似度的自動檢測，具有很重要的現(xiàn)實(shí)意義。

國外對代碼相似度檢測的研究起步較早。MOSS，Jplag，SIM和YAP系列等系統(tǒng)都是比較著名的代碼相似度檢測工具。其中MOSS和Jplag還有支持WEB訪問的調(diào)用接口。國內(nèi)也出現(xiàn)了不少具有相似度檢測功能的在線實(shí)驗(yàn)平臺，如哈工大的高級語言程序設(shè)計能力訓(xùn)練平臺及考試系統(tǒng)、國防科大的Trustie、浙大的PTA、成都琛石科技的實(shí)驗(yàn)樓等。

基于以上對代碼相似度檢測算法和系統(tǒng)研究現(xiàn)狀的分析，本文結(jié)合基于數(shù)字指紋的代碼相似度檢測算法完成代碼相似度檢測模塊的設(shè)計與實(shí)現(xiàn)。

2 相似度檢測需求分析與設(shè)計

2.1 需求分析

應(yīng)用于程序設(shè)計實(shí)驗(yàn)教學(xué)平臺中的代碼相似度檢測模塊應(yīng)符合以下要求：

（1）應(yīng)當(dāng)基于一種可靠的代碼相似度計算方法；

（2）所基于的算法應(yīng)易于移植（可針對不同語言）；

（3）友好的用戶界面，方便教師對學(xué)生在線提交的作業(yè)進(jìn)行抄襲檢查；

（4）輸出信息中應(yīng)明確給出所有具有抄襲嫌疑的代碼。

只有達(dá)到這樣的要求，才能減輕教師的工作量并在有效降低抄襲率的情況下提高實(shí)驗(yàn)教學(xué)的質(zhì)量。

2.2 流程設(shè)計

代碼相似度檢測是程序設(shè)計實(shí)驗(yàn)平臺的核心子功能，教師通過選擇學(xué)期號、課程號、實(shí)驗(yàn)號和編碼語言，對學(xué)生上傳的源代碼進(jìn)行相似度的檢測，代碼檢測流程如圖1所示。可以看出，送入相似度檢測內(nèi)核的文件不僅是根據(jù)學(xué)期號、課程號和實(shí)驗(yàn)號獲得的代碼文件，有時還要有檢測范圍選擇。同班檢測時，是最小的檢測范圍，僅僅針對檢測目錄下相同班號的代碼文件進(jìn)行檢測；同屆檢測，對檢測目錄下的所有文件進(jìn)行檢測；隔屆檢測，則需要引入往屆學(xué)生提交的代碼作為參考文件來進(jìn)行檢測。

2.3 算法設(shè)計

借鑒論文中的思想，將數(shù)字指紋提取算法作為抄襲檢測模塊的核心?；跀?shù)字指紋的代碼相似度檢測算法的具體步驟如下：

Step 1 預(yù)處理：對程序源代碼進(jìn)行過濾和替換處理。首先，把程序中所有的注釋、空行、宏命令、與代碼語義無關(guān)的內(nèi)容全部去掉。

Step 2 分詞：將代碼中所含的不同類型的符號之間加上間隔符“空格”，若原來就有空格的則予以保留。

Step 3 格式化：將用戶自定義的標(biāo)識符替換成UDEF，將數(shù)據(jù)類型替換成DTYPE，將標(biāo)準(zhǔn)輸出printf及內(nèi)容替換成printf（），將cout及內(nèi)容替換成cout<<，并且刪除代碼中詞語詞之間的空格。

Step 4 數(shù)值化：將代碼重疊切分成長度為g的特征片段，根據(jù)哈希函數(shù)計算得到數(shù)值集合。假設(shè)起始位置為i，對于長度為g的特征片段，其哈希值計算公式如下：

（1）

其中Ci是該片段中某個字符對應(yīng)的ASCII碼，g是片段長度即指紋粒度，M是一個很大的數(shù)。

Step 5 指紋化：從獲得的數(shù)值序列中去掉無效數(shù)值集合（由代碼編寫規(guī)則產(chǎn)生的相同代碼片段，經(jīng)數(shù)值化處理生成的集合）后，對有效數(shù)值序列進(jìn)行重疊切分，并采用最小Hash法獲取最終的數(shù)字指紋序列，即對有效數(shù)值序列進(jìn)行重疊切分，窗口大小為w，其次在每個切分過后的數(shù)值片段中選擇最小的Hash值，其中每個位置的數(shù)值只能被選擇一次。

Step 6 相似度計算：獲取兩段代碼的數(shù)字序列后，通過二者間最長公共子序列求得相似度值。

（2）

其中F（A）、F（B）為分別表示代碼A和B的數(shù)字指紋序列，|LCS（F（A），F(xiàn)（B））|表示指紋序列之間的最長公共子序列。

3 算法應(yīng)用

上述相似度檢測算法在我校數(shù)據(jù)結(jié)構(gòu)實(shí)踐教學(xué)平臺中進(jìn)行了應(yīng)用。教師進(jìn)入如圖2所示的代碼查重頁面，通過下拉框選擇學(xué)期號、課程號、實(shí)驗(yàn)題號（大實(shí)驗(yàn)標(biāo)題序號，子實(shí)驗(yàn)標(biāo)題序號），點(diǎn)擊“提交”便會得到一個要檢測的文件清單。點(diǎn)擊“查看結(jié)果”則啟動相似度檢測功能，并返回如圖3所示的檢測結(jié)果，這里只截取了其中的一條。File1和File2分別對應(yīng)相似度檢測模塊所檢測的兩個文件，Matched代表這兩個文件的相似程度。點(diǎn)擊任意一側(cè)的藍(lán)色鏈接，還可以具體查看該側(cè)代碼和另一側(cè)代碼相似的部分，并以紅色標(biāo)出，方便教師對抄襲行為進(jìn)行詳細(xì)鑒定，保證實(shí)驗(yàn)的質(zhì)量和成績的公平性。

4 結(jié)束語

本文實(shí)現(xiàn)的基于數(shù)字指紋的代碼相似度檢測算法可以應(yīng)用到程序設(shè)計實(shí)驗(yàn)教學(xué)平臺中。一方面，能夠給出源程序間的相似度值，減少教師的工作量；同時，還能給出相似代碼的具體位置，以便教師進(jìn)一步人工比對，保證公平性。下一步將開發(fā)對多文檔程序的相似度檢測模塊，并設(shè)計更加優(yōu)化的相似度檢測算法。

參考文獻(xiàn)

[1]Ottenstein K J.An algorithmic approach to the detection and prevention of plagiarism[J].Acm Sigcse Bulletin，1976，8（04）：30-41.endprint

[2]Parker A，Hamblen J O.Computer algorithms for plagiarism detection[J].IEEE Transactions on Education， 1989，32（02）：94-99.

[3]Aiken A.Moss：a system for detecting software plagiarism.http：//theory.stanford.edu/～aiken/moss/.

[4]Prechelt L，Malpohl G，Philippsen M.Finding plagiarisms among a set of programs with Jplag[J].Journal of Universal Computer Science，2002，8（11）：1016-1038.

[5]Gitchell D，Tran N.Sim：A Utility for Detecting Similarity in Computer Programs[C].Proceedings of the 30th SIGCSE Technical Symposium.New Orleans，LA，USA，1999.

[6]Wise M J.Detection of similarities in student programs：YAPing may be preferable to Plagueing[C].Proceedings of the 23th SIGCSE Technical Symposium. Kansas City，USA，1992，24（01）：268-271.

[7]Thomas Lancaster，F(xiàn)intan Culwin.A Comparison of Source Code Plagiarism Detection Engines[J].Computer Science Education，2004，14（02）：101-112.

[8]哈爾濱工業(yè)大學(xué).高級語言程序設(shè)計能力訓(xùn)練平臺.http：//sc.hit.edu.cn/train.

[9]國防科學(xué)技術(shù)大學(xué).Trustie創(chuàng)新實(shí)踐社區(qū).https：//www.trustie.net.

[10]浙江大學(xué).程序設(shè)計類實(shí)驗(yàn)輔助教學(xué)平臺.https：//pta.patest.cn/.

[11]成都琛石科技.實(shí)驗(yàn)樓.https：//www.shiyanlou.com/.

[12]Schleimer S，Wilkerson D S，Aiken A.Winnowing：local algorithms for document fingerprinting[C].ACM SIGMOD International Conference on Management of Data.ACM，2003：76-85.

[13]古平，張鋒，周海濤.一種程序源代碼相似度度量方法[J].計算機(jī)工程，2012，38（06）：37-39.

[14]黃柳柳，黃河燕，史樹敏.面向代碼相似度檢測的指紋選取方法[J].計算機(jī)工程與應(yīng)用，2010，46（27）：169-171.

[15]鄧愛萍.程序代碼相似度度量算法研究[J].計算機(jī)工程與設(shè)計，2008，29（17）：4636-4638.

作者簡介

張華（1978-），男，內(nèi)蒙古自治區(qū)通遼市人。碩士學(xué)位。講師。主要研究方向?yàn)樵诰€教學(xué)、服務(wù)大數(shù)據(jù)。

周學(xué)權(quán)（1979-），男，廣東省惠州市人。碩士學(xué)位。講師。主要研究方向?yàn)閭€性化教學(xué)、服務(wù)大組合與優(yōu)化。

張淼（1979-），女，內(nèi)蒙古自治區(qū)包頭市人。碩士學(xué)位。講師。主要研究方向?yàn)橛行Ы虒W(xué)、密碼學(xué)及其應(yīng)用。

作者單位

哈爾濱工業(yè)大學(xué)（威海）計算機(jī)科學(xué)與技術(shù)學(xué)院 山東省威海市 264209endprint