王克朝，王甜甜，蘇小紅，馬培軍

（1.哈爾濱學院 軟件學院，哈爾濱150086；2.哈爾濱工業(yè)大學 計算機學院，哈爾濱150001）

0 引 言

在計算機程序設計類課程教學中，經常存在程序抄襲行為。被考核者抄襲他人程序后，稍作修改甚至不做任何修改便作為自己的程序提交，在一定程度上限制了考核準確性和效率，降低考核成績的可信度。如果采用人工方法去檢測學生程序之間的雷同程度，查找剽竊代碼工作量巨大。

目前常用的程序雷同檢測方法主要有兩類：屬性計數(shù)法［1－2］和結構度量法［3－8］?；趯傩杂嫈?shù)法的雷同檢測計算每一個程序的n個不同的軟件度量指標（如控制流、數(shù)據依賴、控制結構等），以便于將程序映射到一個n 維的笛卡爾空間，然后考慮彼此鄰近的程序組可能為剽竊。單純的屬性計數(shù)法拋棄了太多的程序結構信息，導致檢測結果的錯誤率很高。例如，如果抄襲程序只有部分程序段是抄襲的，或者修改了原程序中條件語句的結構，則用屬性計數(shù)法檢測是失效的?；诮Y構度量法的雷同檢測通過對程序的內部結構進行分析比較來判斷其相似性。目前主流系統(tǒng)大多采用對表達源程序的字符串進行比較的方法，如MOSS［9］等。這種方法考慮了程序的詞法信息，卻沒有考慮語義信息，對多種變化都很敏感，因此大多只能識別進行簡單修改（如標識符重命名等）的剽竊代碼。在使用MOSS的過程中還發(fā)現(xiàn)，如果在學生程序中加入一些冗余的語句、聲明冗余的變量或者拆分語句，則會降低剽竊檢測的準確性。

為了解決上述問題，本文引入數(shù)據挖掘算法中的雙向擴展頻繁閉合序列模式挖掘（BIdirectional extension based frequent closed sequence mining，BIDE）技術［10］，提出基于BIDE挖掘的學生程序雷同檢測方法。

1 學生程序雷同檢測模型

基于BIDE挖掘的學生程序雷同檢測模型如圖1所示，具體實現(xiàn)步驟如下：

圖1 基于BIDE挖掘的學生程序雷同檢測模型Fig.1 Plagiarism detection model based on BIDE

（1）將學生程序進行詞法分析，轉化成token序列表示。為了能夠識別修改過的雷同代碼片段，將所有類型相同的標識符（變量、函數(shù)名等）映射成相同的值，不考慮它們實際的名字，并將等價關鍵字統(tǒng)一表示。

（2）將步驟1中得到的token序列散列映射為數(shù)字序列。以基本程序塊為單位將數(shù)字序列劃分為若干段，創(chuàng)建一個數(shù)字序列數(shù)據庫，以便將雷同代碼檢測問題轉換成一個頻繁序列模式挖掘問題。

（3）使用數(shù)據挖掘技術中的頻繁閉合序列模式挖掘BIDE算法，將支持度閾值設為2，即查找在序列數(shù)據庫中至少出現(xiàn)兩次的頻繁序列——這些頻繁序列對應于源程序中完全匹配的代碼片段。采用的挖掘算法允許序列中插入gap，因此，可以識別插入、刪除或修改了語句的代碼片段。

（4）計算程序之間的相似度，進而判定是否是雷同程序；同時對挖掘出來的程序中的雷同代碼片段所在的行設置標志位，根據標志位合并雷同代碼片段，分析出程序中對應的雷同代碼。

（5）輸出疑似雷同程序列表，顯示相應雷同代碼。

2 關鍵技術

2.1 散列處理

散列處理把源程序經過詞法分析生成的token序列的各個子串映射為比本身短得多的散列值，相同的子串得到同樣的散列值。采用“hashpjw”散列算法能夠盡可能地避免不同子串產生相同的數(shù)字序列，從而把字符串的匹配問題轉換為整數(shù)的匹配問題，進而通過BIDE 挖掘算法挖掘出相同的數(shù)字序列。采用“hashpjw”散列算法得到的數(shù)字序列示例如圖2所示。

2.2 BIDE挖掘算法

BIDE是一種采用雙向擴展策略頻繁閉合子集挖掘方法。前向擴展用于增加前綴模式并檢查前綴模式的閉包，后向擴展用于檢查前綴模式的

圖2 采用“hashpjw”散列算法生成的數(shù)字序列實例Fig.2 Example of digital sequence mapped by“hashpjw”

閉包并通過剪枝縮小搜索空間。因此與其他同類方法相比更為高效。BIDE 及其子算法描述如下所示。

Algorithm：BIDE（SDB，min＿sup，F(xiàn)CS）

輸入：序列數(shù)據庫SDB，最小支持度閾值min＿sup

輸出：頻繁閉合序列集合FCS

2.F1←頻繁1模式序列；

3.foreach 頻繁1模式f1in F1

4.SDBf1←為f1建立偽投影數(shù)據庫；

5.foreach f1in F1

6.將f1作為前綴；

7.if（向后掃描不能將f1剪枝）

8.BEI←f1向后擴展事件的個數(shù)；

9.FCS←調用bide算法產生閉合序列模式；

10.return FCS；

Algorithm：bide（Sp＿SDB Sp，min＿sup，BEI，F(xiàn)CS）

輸入：投影序列數(shù)據庫Sp＿SDB，前綴序列Sp，最小支持度閾值min＿sup，后向擴展事件數(shù)BEI

輸出：當前頻繁閉合序列集合FCS

1.LFI←掃描Sp＿SDB找出Sp的本地頻繁項；

2.FEI←Sp向前擴展項的個數(shù)；

3.if（（BEO＋FEI）＝＝0）

4.FCS＝FCS∪｛Sp｝

5.foreach i in LFI

8.foreach i in LFI

12.FCS←遞歸調用bide算法產生閉合序列模式；

13.return FCS；

本文應用BIDE 算法，從已經生成的序列數(shù)據庫中查找支持度大于等于2的頻繁序列，這些頻繁序列與程序之間的雷同代碼相對應。識別出的學生程序間的一個雷同代碼片段組實例如圖3所示（其中，SEQ 表示代碼片段的數(shù)字序列，LEN表示代碼片段的長度，SUP 表示代碼片段的支持度，F(xiàn)ilePath 表示代碼片段所在程序的路徑，Lines表示代碼片段在程序中的所在行，RELAL表示代碼片段在原程序函數(shù)中的行數(shù)）。

圖3 BIDE算法挖掘出的雷同代碼片段實例Fig.3 Example of similar code mined by BIDE

2.3 程序相似度計算

程序相似度的計算公式定義如下：

式中：｜A｜和｜B｜分別為程序A 和程序B 中代碼行數(shù)；A ∩B 是經過BIDE 挖掘算法后計算出的兩個程序之間的相似代碼行數(shù)；sim（A，B）是程序A 和程序B 之間的相似度值。

2.4 程序相似度和對應雷同代碼關系分析步驟

（1）統(tǒng)計每個源程序中的代碼行數(shù)。

（2）計算程序之間相似代碼的行數(shù)：對程序中的每行相似代碼設置標志位，若該行相似代碼已經出現(xiàn)過，則跳過處理，否則繼續(xù)處理，從而得到程序中所有不重復出現(xiàn)的相似代碼。

（3）計算程序之間的相似度，查找程序之間對應的雷同代碼：若計算出的sim（A，B）高于預定的閾值，則認為程序A 和程序B 是雷同程序。

（4）排序算法：經過上述步驟（1）（2）（3）之后，根據得到的程序之間的相似度，按降序排序算法進行排序，得到由高到底的雷同程序列表。

（5）輸出雷同程序列表和相對應的雷同代碼。

3 系統(tǒng)測試結果及分析

3.1 基準測試集

為了測試本文方法的檢測效果，選擇5個實際的學生作業(yè)題目。這些程序已被第三方授課教師采用人工檢測的方式確認了其中的雷同程序組。然而由于實際剽竊的程序組數(shù)有限，本文還采用了人工注入的方式，對每組題目由授課教師模擬學生常見的抄襲方式，在已有程序的基礎上進行修改，如標識符重命名、插入和刪除部分語句，生成新的雷同程序組。最后將原程序和人工注入的程序集合統(tǒng)稱為人工檢測集合，作為本實驗的基準測試集，如表1所示。分別采用MOSS和本文方法對每組程序進行雷同檢測，統(tǒng)計檢測結果的誤檢率和漏檢率。

表1 基準測試集Table 1 Benchmark

3.2 雷同檢測結果代碼實例

圖4標注出來的代碼為系統(tǒng)檢測出的兩程序之間對應的雷同代碼，雷同度為91.25%。

3.3 雷同檢測結果分析

雷同檢測結果的誤檢率和漏檢率計算公式如下：

式中：絕對值符號表示檢測出的雷同程序組數(shù)；｜系統(tǒng)檢測∩人工檢測｜表示系統(tǒng)檢測出基準測試集合中所提供的雷同程序組數(shù)。

根據實際經驗，由于初學者在程序設計時具有類似的實現(xiàn)思路，并且常常需要使用指定的語法結構，因此程序會存在一定的相似性。一般相似度為70%以下的程序組是雷同程序的可能性比較小。即使這些程序中可能存在剽竊，也是經過了較大的修改，加入了抄襲者自己的思考。因此，本文重點分析MOSS和本文方法輸出的相似度大于70%的雷同程序組，結果如表2所示。表中∩表示｜系統(tǒng)檢測∩人工檢測｜。

由表2可以看出：兩種方法對于相似度較高的代碼均具有較高的準確性。對于相似度80%以上的雷同程序組的誤檢率為0。但是在實驗中本文方法和MOSS均出現(xiàn)一次誤檢，誤檢的兩個程序比較類似于修改了的雷同程序，而實際中是由相似的編程思路和編程風格導致的。對于這種相似度不是很高的雷同程序組而言，教師最好進一步確認是否真正是雷同程序。但是對于相似度70%～80%的雷同程序組而言，大多情況下是對抄襲程序進行了修改，本文方法具有較低的誤檢和漏檢。這是因為本文方法是在詞法分析生成的token序列的基礎上進行分析和BIDE挖掘的，可以有效檢測各種標識符重命名、插入和刪除了部分語句的雷同代碼片段。

圖4 檢測出的一組雷同程序實例Fig.4 Example of plagiarized programs

表2 本文方法與MOSS的誤檢率和漏檢率Table 2 False positive rate and false negative rate of our method vs MOSS

4 結 論

（1）提出了基于頻繁閉合序列模式挖掘的學生程序雷同檢測方法。在詞法分析的基礎上，將學生程序映射為數(shù)字序列，進而應用數(shù)據挖掘技術中的頻繁閉合序列模式挖掘BIDE 算法檢測雷同代碼片段。該方法不但可以準確地給出雷同程序的統(tǒng)計信息，還能夠較為直觀地顯示雷同代碼片段。

（2）通過檢測實際的學生程序，證明本文方法可以有效檢測各種標識符重命名、插入和刪除了部分語句的雷同代碼片段，因此與MOSS工具相比，本文方法具有較低的誤檢率和漏檢率。

［1］Shawky D M，Ali A F.An approach for assessing similarity metrics used in metric－based clone detection techniques［C］∥The 3rd IEEE International Conference on Computer Science and Information Technology（ICCSIT），Chengdu，2010：580－584.

［2］Brixtel R，F(xiàn)ontaine M，Lesner B，et al.Languageindependent clone detection applied to plagiarism detection［C］∥The 10th IEEE Working Conference on Source Code Analysis and Manipulation（SCAM），Timisoara，2010：77－86.

［3］Dang Y，Ge S，Huang R，et al.Code clone detection experience at Microsoft［C］∥Proceedings of the 5th International Workshop on Software Clones，ACM，2011：63－64.

［4］Zibran M F，Roy C K.IDE－based real－time focused search for near－miss clones［C］∥Proceedings of the 27th Annual ACM Symposium on Applied Computing，ACM，2012：1235－1242.

［5］Higo Y，Kamiya T，Kusumoto S，et al.Method and implementation for investigating code clones in a software system［J］.Information and Software Technology，2007，49（9）：985－998.

［6］鄧愛萍.程序代碼相似度度量算法研究［J］.計算機工程與設計，2008，29（17）：4636－4638.Deng Ai－ping.Study on similarity measurement of program code［J］.Computer Engineering and Design，2008，29（17）：4636－4638.

［7］古平，張鋒，周海濤.一種程序源代碼相似度度量方法［J］.計算機工程，2012，38（6）：37－39.Gu Ping，Zhang Feng，Zhou Hai－tao.Method of program source code similarity measurement［J］.Computer Engineering，2012，38（6）：37－39.

［8］張麗萍，劉東升，李彥臣，等.一種基于AST 的代碼抄襲檢測方法［J］.計算機應用研究，2011，28（12）：4616－4620.Zhang Li－ping，Liu Dong－sheng，Li Yan－chen，et al.AST－based code plagiarism detection method［J］.Application Research of Computers，2011，28（12）：4616－4620.

［9］Schleimer S，Wilkerson D S，Aiken A.Winnowing：local algorithms for document fingerprinting［C］∥Proceedings of the ACM SIGMOD International Conference on Management of Data，ACM，2003：76－85.

［10］Wang J，Han J.BIDE：efficient mining of frequent closed sequences［C］∥IEEE 20th International Conference on Data Engineering，2004：79－90.