在線評測系統(tǒng)中的源碼相似度檢測研究與實(shí)現(xiàn)

陳榮欽，胡永良，應(yīng)建健，郭賢海

（臺州學(xué)院 計(jì)算機(jī)應(yīng)用研究所，浙江 臨海 317000）

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

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

1 相關(guān)工作

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

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

單純的文本匹配算法不能直接應(yīng)用于源代碼匹配中，因?yàn)槌u者只需通過文本替換功能修改變量名、函數(shù)名等即可使字符串匹配的相似度大大降低，因此還需要針對源碼的特點(diǎn)設(shè)計(jì)更好的算法，常見的方法有屬性計(jì)數(shù)法（attribute counting method）和結(jié)構(gòu)度量法（structure metric method）。

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

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

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

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

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

在OJ系統(tǒng)中，由于系統(tǒng)要承擔(dān)源碼正確性實(shí)時(shí)檢測的任務(wù)，因此服務(wù)器負(fù)載很重。而代碼相似度檢測的負(fù)載則更重，因?yàn)樘峤坏拿總€(gè)源碼都需要與原有的所有源碼進(jìn)行比較，因此單純的字符串匹配算法不可能滿足實(shí)時(shí)檢測的需求。

2 OJ系統(tǒng)中的源碼檢測過程

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

圖1 OJ系統(tǒng)中的源碼檢測流程

2.1 給定檢測條件進(jìn)行源碼查詢

源碼保存在OJ系統(tǒng)的服務(wù)器端數(shù)據(jù)庫中，可以隨時(shí)調(diào)取。在調(diào)取源碼時(shí)，可以設(shè)定相關(guān)的條件，避免不必要的檢測，如忽略較短的源碼，只在指定的班級中、某次競賽或考試中調(diào)取，只在2個(gè)用戶之間進(jìn)行匹配等，也可以設(shè)定在服務(wù)器負(fù)載輕的夜間自動(dòng)啟動(dòng)對當(dāng)天的源碼進(jìn)行抄襲檢測。

2.2 預(yù)處理

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

2.3 相似度檢測

相似度檢測部分可以根據(jù)需要選擇屬性計(jì)數(shù)法或結(jié)構(gòu)度量法。前者效率較高，但容易被學(xué)生通過加入冗余代碼降低相似度，可以用于檢測不經(jīng)修改便提交到系統(tǒng)中的低級抄襲現(xiàn)象，在教學(xué)過程中的初始階段采用較為有效；結(jié)構(gòu)度量法因?yàn)榭梢詫Τ绦虻膬?nèi)部結(jié)構(gòu)和控制流進(jìn)行分析，因此精確度較高，可以在教學(xué)的后續(xù)階段使用（一般針對少部分擅長投機(jī)取巧的學(xué)生）。由于Rabin－Karp支持多模式匹配（multiple pattern match）的特點(diǎn)，因此在結(jié)構(gòu)度量法中采用Rabin－Karp算法進(jìn)行字符串匹配。屬性計(jì)數(shù)法處理過程為：

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

（2）濾除注釋語句以及雙引號內(nèi)部文字；

（3）對源碼進(jìn)行詞語分割，統(tǒng)計(jì)出基礎(chǔ)屬性數(shù)目，主要包括：n1（操作符種類）、n2（操作數(shù)種類）、N1（操作符總數(shù)）和N2（操作數(shù)總數(shù)）；

（4）定義詞匯量n＝n1＋n2，長度N＝N1＋N2，再根據(jù)詞匯量和長度定義容量V＝N·Log2（n），最后將這些信息組合成一個(gè)特征向量H（n，N，V）。通過計(jì)算所比較程序?qū)Φ奶卣飨蛄恐g的距離進(jìn)行相似度檢測，距離越小則相似度越高。結(jié)構(gòu)度量法處理過程為：

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

其中Si＝di，d為源碼字符集合的長度，q為一個(gè)較大的素?cái)?shù)。

② 采用Rabin－Karp對標(biāo)記流進(jìn)行兩兩比較，在比較過程中，字符串的比較轉(zhuǎn)化為了散列值的比較，該方法使得算法的時(shí)間復(fù)雜度可以達(dá)到O（n），因此提高了比對效率。

2.4 統(tǒng)計(jì)檢測信息

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

3 結(jié)果分析

通過給定相關(guān)條件從OJ系統(tǒng)中抽取若干組源碼進(jìn)行比對測試，屬性計(jì)數(shù)法的分析時(shí)間遠(yuǎn)遠(yuǎn)大于檢測時(shí)間，因此通過緩存預(yù)處理信息的方式可以大大提高源碼檢測效率，完全可以達(dá)到實(shí)時(shí)處理（平均每秒鐘約檢測5000組源碼），如表1所示。結(jié)構(gòu)度量法的預(yù)處理時(shí)間與檢測時(shí)間較為接近，因?yàn)閮烧叩奶幚硇示鶠镺（n），緩存預(yù)處理信息也能提高一倍（如表2所示）。

表1 屬性計(jì)數(shù)法性能分析

表2 結(jié)構(gòu)度量法性能分析

4 結(jié)論

本文結(jié)合OJ系統(tǒng)的特性，采用屬性計(jì)數(shù)法與結(jié)構(gòu)度量法相結(jié)合的方式對OJ系統(tǒng)的源碼進(jìn)行了相似度檢測，通過緩存方式提高了檢測效率。檢測過程中通過動(dòng)態(tài)調(diào)整用戶的權(quán)值來修正檢測模型，以便于更有效地控制用戶抄襲行為。實(shí)驗(yàn)表明，該方法能較為有效地檢測OJ系統(tǒng)的源碼相似度。同時(shí)，該檢測方法已應(yīng)用到臺州學(xué)院在線程序設(shè)計(jì)綜合平臺（http：／／acm.tzc.edu.cn），檢測效果良好，有效控制了本校學(xué)生的抄襲現(xiàn)象。

（

）

［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.