在線評測系統中的源碼相似度檢測研究與實現

陳榮欽，胡永良，應建健，郭賢海

（臺州學院 計算機應用研究所，浙江 臨海 317000）

在線評測（online judge，OJ）系統［1］是為 ACM 國際大學生程序設計競賽而設計的程序源碼評測系統。OJ系統通常用Web瀏覽器將用戶的源碼提交至服務器，并在服務器端編譯、運行程序，再通過預先給定的測試數據對程序進行檢測，然后將結果反饋至客戶端，整個過程全部由計算機自動處理，因此在國內外程序設計競賽中被廣泛采用。知名的OJ系統有Timus OJ［2］、ZOJ［3］、POJ［4］、HDOJ［5］等。

OJ系統的自動處理機制使其非常適合于程序設計類課程的實踐教學，但高校存在的抄襲現象阻礙了OJ系統在教學中的應用。研究表明，源碼抄襲與論文剽竊在高校教學過程中時有發生，并有不斷增長的趨勢［6－8］。由于 OJ系統的代碼提交量往往較大，如HDOJ的年提交量在100萬以上，且呈加速增長趨勢，手工檢測根本無法完成，因此迫切需要有高效的源碼自動檢測方法。

1 相關工作

源碼檢測屬于文本匹配范疇，文本匹配算法廣泛應用于生物技術、信息檢索、語言翻譯、入侵檢測等領域，主要有前綴搜索、后綴搜索、子串搜索等類型。

文本匹配問題可以描述為：給定一個文本串T［1，2，…，n］和一個模式串P［1，2，…，m］，其中m≤n，且T［i］和P［j］均屬于字母表∑。若存在s，使得T［s＋1，s＋2，…，s＋m］＝P［1，2，…，m］成立，則說明模式串P在文本串T中出現，且位移為s，其中0≤s≤n－m。文本匹配的研究已經較為成熟，代表性的算法有Rabin－Karp、KMP、有限自動機、BM 和 Sunday等算法［9］。在實際應用中，Rabin－Karp算法的平均復雜度為O（n＋m），通常應用于單個模式串在多個文本串中的匹配問題中。KMP算法和有限自動機的復雜度稍好，達到O（n），BM算法和Sunday算法的平均時間復雜度為O（n），最壞時間復雜度為O（nm），但對于短模式串的匹配問題，Sunday算法執行速度較快。

單純的文本匹配算法不能直接應用于源代碼匹配中，因為抄襲者只需通過文本替換功能修改變量名、函數名等即可使字符串匹配的相似度大大降低，因此還需要針對源碼的特點設計更好的算法，常見的方法有屬性計數法（attribute counting method）和結構度量法（structure metric method）。

1.1 屬性計數法

屬性計數法通過提取兩段代碼中的運算符、操作數、行數、字符數、程序注釋等相關屬性的數量，并將它們表示為N元組，對N元組進行規范化，并計算它們的歐幾里得距離，由此來判斷源碼的相似度。歐幾里得距離計算如公式（1）所示：

其中x和y分別是N 元屬性組，分別表示為（x1，x2，…，xN）和（y1，y2，…，yN），該方法的缺點是如果抄襲者加入一些多余的關鍵字、變量甚至一些冗余的源碼，系統便很難檢測［10］，而對于不屬于抄襲甚至完全不相關的源碼，由于屬性個數相近的原因可能存在較大的誤判概率。

1.2 結構度量法

結構度量法從程序的結構上進行分析，避開了任何冗余代碼，主要分2個步驟：（1）首先對源碼進行詞法或語法分析并產生符號序列，在此過程中將同義詞映射為統一的形式，將自定義的標志符轉換為標準符號，刪除空白符號和注釋，將大寫字母轉化為小寫等；（2）采用相關字符串匹配技術兩兩比較前面產生的符號序列，并求出其相似度［11］。該方法可以有效克服屬性計數法帶來的問題，因此在實際過程中應用更為廣泛，如 Sim［12］、JPlag［13］、YAP3［14］和 MOSS［15］等。

在OJ系統中，由于系統要承擔源碼正確性實時檢測的任務，因此服務器負載很重。而代碼相似度檢測的負載則更重，因為提交的每個源碼都需要與原有的所有源碼進行比較，因此單純的字符串匹配算法不可能滿足實時檢測的需求。

2 OJ系統中的源碼檢測過程

OJ系統源碼檢測過程主要包括給定檢測條件、查詢源碼、預處理、相似度檢測、統計檢測信息等部分，如圖1所示。

圖1 OJ系統中的源碼檢測流程

2.1 給定檢測條件進行源碼查詢

源碼保存在OJ系統的服務器端數據庫中，可以隨時調取。在調取源碼時，可以設定相關的條件，避免不必要的檢測，如忽略較短的源碼，只在指定的班級中、某次競賽或考試中調取，只在2個用戶之間進行匹配等，也可以設定在服務器負載輕的夜間自動啟動對當天的源碼進行抄襲檢測。

2.2 預處理

預處理階段針對采用的相似度檢測算法，對源碼進行適當處理，以便更有效地進行相似度檢測。針對屬性計數法可以刪除源碼中的空行、空白字符、注釋語句、雙引號中的文字等與代碼相似度無關的度量，同時記錄相關的屬性個數，如標志符、常量、數字等；針對結構度量法將源碼根據結構進行轉化，形成相應的標記流（token stream）；預處理得到相關數據根據需要將其直接存入數據庫，待下次檢測時直接取出，節省了預處理的時間。

2.3 相似度檢測

相似度檢測部分可以根據需要選擇屬性計數法或結構度量法。前者效率較高，但容易被學生通過加入冗余代碼降低相似度，可以用于檢測不經修改便提交到系統中的低級抄襲現象，在教學過程中的初始階段采用較為有效；結構度量法因為可以對程序的內部結構和控制流進行分析，因此精確度較高，可以在教學的后續階段使用（一般針對少部分擅長投機取巧的學生）。由于Rabin－Karp支持多模式匹配（multiple pattern match）的特點，因此在結構度量法中采用Rabin－Karp算法進行字符串匹配。屬性計數法處理過程為：

（1）只保留源碼中數字、字母和可見符號；

（2）濾除注釋語句以及雙引號內部文字；

（3）對源碼進行詞語分割，統計出基礎屬性數目，主要包括：n1（操作符種類）、n2（操作數種類）、N1（操作符總數）和N2（操作數總數）；

（4）定義詞匯量n＝n1＋n2，長度N＝N1＋N2，再根據詞匯量和長度定義容量V＝N·Log2（n），最后將這些信息組合成一個特征向量H（n，N，V）。通過計算所比較程序對的特征向量之間的距離進行相似度檢測，距離越小則相似度越高。結構度量法處理過程為：

①先對源碼進行詞法或語法分析，將同義詞映射為統一的形式，將所有用戶自定義標志符轉換為特定的符號，刪除空白和注釋字符，將大寫字母轉化為小寫，最終形成標記（token）串。其中的字符串T＝T1T2，散列函數設計如公式（2）所示

其中Si＝di，d為源碼字符集合的長度，q為一個較大的素數。

② 采用Rabin－Karp對標記流進行兩兩比較，在比較過程中，字符串的比較轉化為了散列值的比較，該方法使得算法的時間復雜度可以達到O（n），因此提高了比對效率。

2.4 統計檢測信息

相似檢測的結果如果大于設定的百分比閾值，則認定抄襲。由于在實際教學過程中，抄襲現象往往發生于2個用戶之間，并且用戶抄襲的源碼往往是批量的，因此系統在檢測過程中對“用戶對（即指抄襲的雙方用戶）”進行計數，并同時統計雙方用戶各自的抄襲頻率，優先調取頻率較高的用戶進行檢測。若“用戶對”的抄襲次數高于設定的閾值，將智能地對該“用戶對”進行源碼的完全檢測，以便于進一步確認該“用戶對”是否存在大量抄襲。檢測的結果存入數據庫，可以作為教師扣除學生積分的依據，從而有效地控制了抄襲現象。

3 結果分析

通過給定相關條件從OJ系統中抽取若干組源碼進行比對測試，屬性計數法的分析時間遠遠大于檢測時間，因此通過緩存預處理信息的方式可以大大提高源碼檢測效率，完全可以達到實時處理（平均每秒鐘約檢測5000組源碼），如表1所示。結構度量法的預處理時間與檢測時間較為接近，因為兩者的處理效率均為O（n），緩存預處理信息也能提高一倍（如表2所示）。

表1 屬性計數法性能分析

表2 結構度量法性能分析

4 結論

本文結合OJ系統的特性，采用屬性計數法與結構度量法相結合的方式對OJ系統的源碼進行了相似度檢測，通過緩存方式提高了檢測效率。檢測過程中通過動態調整用戶的權值來修正檢測模型，以便于更有效地控制用戶抄襲行為。實驗表明，該方法能較為有效地檢測OJ系統的源碼相似度。同時，該檢測方法已應用到臺州學院在線程序設計綜合平臺（http：／／acm.tzc.edu.cn），檢測效果良好，有效控制了本校學生的抄襲現象。

（

）

［1］Kurnia A，Lim A，Cheang B.Online Judge［J］.Computer ＆ Education，2001（36）：299－315.

［2］ Timus Online Judge［EB／OL］.［2013－07－11］.http：／／acm.timus.ru.

［3］Zhejiang University Online Judge［EB／OL］.［2013－07－10］.http：／／acm.zju.edu.cn.

［4］Peking University Online Judge［EB／OL］.［2013－07－10］.http：／／poj.org.

［5］Hangzhou Dianzi University Online Judge［EB／OL］.［2013－07－10］.http：／／acm.hdu.edu.cn.

［6］Bull J，Collins C，Coughlin E，et al.Technical Review of Plagiarism Detection Software Report［R］.CAA，University of Luton，2001.

［7］Culwin F，MacLeod A，Lancaster T.Source code Plagiarism in UK HE Computing Schools，Issues，Attitudes and Tools［R］.Technical Report No.SBU－CISM－01－02，South Bank University，2001.

［8］Sheard J，Dick M，Markham S，et al.Cheating and Plagiarism：Perceptions and Practices of First Year IT Students［C］／／In Proceedings of the 7th Annual Conference on Innovation and Technology in Computer Science Education，Aarhus，Denmark，ACM Press，2002：183－187.

［9］Singla N，Garg D.String Matching Algorithms and their Applicability in various Applications ［J］.International Journal of Soft Computing and Engineering（IJSCE），2012：218－222.

［10］Verco K，Wise M.Software for Detecting Suspected Plagiarism：Comparing Structure and Attribute Counting Systems［C］／／In Proceedings of Australian Conference on Computer Science Education，Sydney，Australia，1996：81－88.

［11］Arwin C，S.M.M.Tahaghogh.Plagiarism Detection across Programming Languages［C］／／ACM International Conference Proceeding Series，Proceedings of the 29th Australasian Computer Science Conference，Hobart，Australia，2006（48）：277－286.

［12］Gitchell D，Tran N.Sim：A Utility for Detecting Similarity in Computer Programs［C］／／In Proceedings of the Thirtieth SIGCSE Technical Symposium on Computer Science Education，ACM Press，1999：266－270.

［13］Prechelt L，Malpohl G，Philippsen M.Finding plagiarisms among a set of programs with JPlag［J］.Journal of Universal Computer Science，2002（8）：1016－1038.

［14］Wise M J.Detection of Similarities in Student Programs：YAP’ing May be Preferable to Plague’ing［C］／／ACM SIGSCE Bulletin（Proc.of 23rd SIGCSE Technical Symp），1992（24）：268－271.

［15］Aiken A.MOSS（Measure of Software Similarity）Plagiarism Detection System［EB／OL］.http：／／www.cs.berkeley.edu／moss／.University of Berkeley，CA.