相似度檢測技術在計算機實驗教學中的應用研究

張華++周學權++張淼++鄭宏珍++初佃輝

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

【關鍵詞】相似度檢測 實驗教學 代碼抄襲

1 計算機實驗教學中存在的問題

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

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

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

2 相似度檢測需求分析與設計

2.1 需求分析

應用于程序設計實驗教學平臺中的代碼相似度檢測模塊應符合以下要求：

（1）應當基于一種可靠的代碼相似度計算方法；

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

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

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

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

2.2 流程設計

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

2.3 算法設計

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

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

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

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

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

（1）

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

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

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

（2）

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

3 算法應用

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

4 結束語

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

參考文獻

[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è)大學.高級語言程序設計能力訓練平臺.http：//sc.hit.edu.cn/train.

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

[10]浙江大學.程序設計類實驗輔助教學平臺.https：//pta.patest.cn/.

[11]成都琛石科技.實驗樓.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].計算機工程，2012，38（06）：37-39.

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

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

作者簡介

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

周學權（1979-），男，廣東省惠州市人。碩士學位。講師。主要研究方向為個性化教學、服務大組合與優(yōu)化。

張淼（1979-），女，內(nèi)蒙古自治區(qū)包頭市人。碩士學位。講師。主要研究方向為有效教學、密碼學及其應用。

作者單位

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