基于頻繁閉合序列模式挖掘的學(xué)生程序雷同檢測

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

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

0 引 言

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

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

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

1 學(xué)生程序雷同檢測模型

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

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

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

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

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

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

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

2 關(guān)鍵技術(shù)

2.1 散列處理

散列處理把源程序經(jīng)過詞法分析生成的token序列的各個子串映射為比本身短得多的散列值，相同的子串得到同樣的散列值。采用“hashpjw”散列算法能夠盡可能地避免不同子串產(chǎn)生相同的數(shù)字序列，從而把字符串的匹配問題轉(zhuǎn)換為整數(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ù)據(jù)庫SDB，最小支持度閾值min＿sup

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

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

3.foreach 頻繁1模式f1in F1

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

5.foreach f1in F1

6.將f1作為前綴；

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

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

9.FCS←調(diào)用bide算法產(chǎn)生閉合序列模式；

10.return FCS；

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

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

輸出：當(dāng)前頻繁閉合序列集合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←遞歸調(diào)用bide算法產(chǎn)生閉合序列模式；

13.return FCS；

本文應(yīng)用BIDE 算法，從已經(jīng)生成的序列數(shù)據(jù)庫中查找支持度大于等于2的頻繁序列，這些頻繁序列與程序之間的雷同代碼相對應(yīng)。識別出的學(xué)生程序間的一個雷同代碼片段組實例如圖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 是經(jīng)過BIDE 挖掘算法后計算出的兩個程序之間的相似代碼行數(shù)；sim（A，B）是程序A 和程序B 之間的相似度值。

2.4 程序相似度和對應(yīng)雷同代碼關(guān)系分析步驟

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

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

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

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

（5）輸出雷同程序列表和相對應(yīng)的雷同代碼。

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

3.1 基準(zhǔn)測試集

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

表1 基準(zhǔn)測試集Table 1 Benchmark

3.2 雷同檢測結(jié)果代碼實例

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

3.3 雷同檢測結(jié)果分析

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

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

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

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

圖4 檢測出的一組雷同程序?qū)嵗鼺ig.4 Example of plagiarized programs

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

4 結(jié) 論

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

（2）通過檢測實際的學(xué)生程序，證明本文方法可以有效檢測各種標(biāo)識符重命名、插入和刪除了部分語句的雷同代碼片段，因此與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］.計算機工程與設(shè)計，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］.計算機應(yīng)用研究，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.