徐雅靜　李通　劉玉濤

摘 要：針對學(xué)生在編程中出現(xiàn)的代碼拷貝問題，提出用一種改進的分段最長公共子序列匹配算法分析代碼相似度，進一步挖掘隱藏在相似代碼背后的學(xué)生之間合作關(guān)系以及行為模式，對于如何了解、干預(yù)和避免學(xué)生抄襲行為的擴散以及正確評價學(xué)生的編程能力進行積極有益的探索。

關(guān)鍵詞：代碼相似度；行為模式挖掘；合作關(guān)系挖掘；LCS（大于3個，小于8個）

0 引 言

計算機編程類課程一直以來面臨一個難以解決的問題——代碼拷貝問題，該問題嚴重影響教師對于教學(xué)中學(xué)生程序設(shè)計能力和編程實踐水平的評估，進而影響教師有效針對學(xué)生編程情況的一系列教學(xué)設(shè)計。隨著計算機科學(xué)在人工智能、程序理解等領(lǐng)域的發(fā)展，各種代碼相似度檢測的方法相繼提出，如基于Token比較的方法[1]、基于文本檢測的方法[2]、基于語法樹[3]的方法、基于依賴關(guān)系圖的方法[4]等，這些方法在檢測類型、時間復(fù)雜度等方面都存在不同程度的局限性[5]。因此，我們提出一種針對輕量級代碼檢測的可忽略間隙的分段最長公共子序列（gapped and segmented longest common sequence， GS-LCS）算法，該方法考慮了學(xué)生代碼拷貝的習(xí)慣，能有效檢測代碼的相似度。

1 代碼相似度檢測

計算機教學(xué)中代碼算法復(fù)雜度及代碼長度相對有限，對于同一題目會有大量學(xué)生進行算法設(shè)計和編程。學(xué)生常用的10種抄襲手段包括逐字拷貝、更改注釋語句、更改空白區(qū)域、重新命名標識符、改變代碼塊的順序、改變代碼塊中語句的順序、改變表達式中操作符和操作數(shù)的順序、更改數(shù)據(jù)類型控制邏輯、增加冗余的語句和變量、用等價的控制結(jié)構(gòu)替換原有控制結(jié)構(gòu)[6]。我們通過分析學(xué)生代碼，發(fā)現(xiàn)其中較為高級的代碼拷貝形式“用等價的控制結(jié)構(gòu)替換原有控制結(jié)構(gòu)”應(yīng)該不屬于抄襲?；谏鲜龇治?，我們提出的GS-LCS算法步驟如圖1所示。

1.1 預(yù)處理、標準化、Hash

代碼相似度檢測流程中的預(yù)處理、標準化、Hash 3個步驟將源代碼轉(zhuǎn)換為Hash數(shù)字序列，進行CS-LCS算法的匹配，如圖2所示。

（1）預(yù)處理：用于去掉注釋、空白，并將代碼按照預(yù)定義的分隔符如“；”“{”、“}”等分割成獨立的表達式；

（2）標準化：用于將其中的標識符包括常量、變量、函數(shù)名等，替換成統(tǒng)一的符號“$”，關(guān)鍵字、操作符保持不變；

（3）Hash：用來將每一個獨立的表達式進行唯一的編碼。

1.2 GS-LCS算法

Hash編碼后，對于源代碼的匹配就轉(zhuǎn)換成對于數(shù)字序列的匹配。GS-LCS算法中，針對學(xué)生在代碼拷貝中可能增加、刪除或改變部分表達式，采用忽略間隙策略進行匹配；對于代碼塊的順序改變、代碼塊中表達式的順序，則采用分段策略進行匹配。GS-LCS算法的基本思想如圖3所示。

GS-LCS算法對源代碼進行兩兩比較，若源代碼A生成的Hash序列為（a1，a2，…， aN），源代碼B生成的Hash序列（b1，b2，…， bM），則GS-LCS算法按照如下步驟進行。

步驟1：初始化T為（N+1）×（M+1）的矩陣，其中第一行和第一列置0；

步驟2：按照公式1對序列a和b進行逐行匹配，生成矩陣T；

步驟3：分段回溯，從矩陣T [M，N]開始從右至左、從下至上遍歷，若兩個相似Hash值間隔在[0，θ1]范圍內(nèi)（θ1為預(yù)先設(shè)置的可忽略間隙距離），視為一個相似子序列，如圖3所示相似子序列1?；厮菟惴空{(diào)用一次找到一個子序列，回溯算法具體如下：

步驟4：更新矩陣，即將已匹配的序列所在行全部置0，反復(fù)調(diào)用回溯算法找出所有相似子序列l(wèi)i，注意相似子序列長度>1。

經(jīng)過優(yōu)化，GS-LCS算法的時間復(fù)雜度為O（M*N）。

1.3 計算相似度

根據(jù)GS-LCS算法可以得到任意兩個源文件的所有相似Hash子序列L={l1，l2…lk}，因此我們根據(jù)公式（2）計算相似度，其中M， N分別為待比較文件a和b的有效獨立表達式總數(shù)。

（2）

2 實驗分析

我們隨機抽取3個班6個作業(yè)題目進行測試和驗證，3個班每班人數(shù)分別為20、22和21；實驗中我們設(shè)置的忽略間隙θ1=2，根據(jù)題目的難易、算法的多樣性、代碼量等，用半監(jiān)督的方式為每一個題目設(shè)置3種不同的相似度閾值θ2={0.75，0.8，0.85}，見表1，若sim（a，b）≥θ2，則認為文件a和b為拷貝。

2.1 作業(yè)相似度分析

根據(jù)表1的設(shè)置，我們對3個班的6份作業(yè)進行相似度兩兩比較，算法準確率和召回率見表2。

可以看出，題目1（約瑟夫環(huán)）的準確率和召回率最高，主要是由于其解題方法較為多樣化，相似代碼較為集中；題目4（排序）的準確率和召回率都較差，主要是由于該作業(yè)實現(xiàn)7個不同的排序算法，每個算法代碼量較小，解題方法較單一；題目6（圖）準確率較高，但召回率較差，因為該題目中涉及的部分算法如最短路徑、最小生成樹等比較難，解題思路較為一致，其他算法具有一定的多樣性分布。

2.2 學(xué)生拷貝行為分析

根據(jù)相似度分析，我們對每一個學(xué)生在6次作業(yè)中出現(xiàn)的拷貝行為次數(shù)進行統(tǒng)計，統(tǒng)計結(jié)果如圖4所示，可以看出一班的拷貝行為最輕，二班其次，三班最為嚴重。

其次，我們對每個題目的代碼相似分布進行分析，如圖5所示。相似代碼對代表學(xué)生之間的拷貝關(guān)系，從中我們可以看出班內(nèi)代碼拷貝現(xiàn)象遠遠多于班級之間，代碼拷貝趨向于小組協(xié)作模式，即每個班內(nèi)容易形成3～5個同學(xué)的子集團進行合作拷貝，并且相似代碼的編號較連續(xù)，說明相鄰的學(xué)生趨向于形成拷貝小組的可能性更大。

最后，我們對相似代碼對進行統(tǒng)計，在6次作業(yè)中超過3次相似度大于閾值的代碼對，則認為是穩(wěn)定拷貝合作關(guān)系，我們可以得到圖6所示的合作關(guān)系圖，可以發(fā)現(xiàn)，班級內(nèi)部存在{15-20，12-18，10-11，29-30}4個穩(wěn)定合作對，存在{24，28，32，34}， {31，35，36，37，38，39，40}，{56，58，62，63}3個穩(wěn)定拷貝協(xié)作組以及{44，46，48，54，55，59}1個拷貝合作鏈；班級之間僅有4和57兩個節(jié)點具有穩(wěn)定拷貝關(guān)系，因此教學(xué)中只需要重點關(guān)注班內(nèi)穩(wěn)定合作關(guān)系，即可有效避免代碼過度拷貝及擴散。

3 結(jié) 語

GS-LCS算法能夠有效地檢測存在于學(xué)生作業(yè)和實驗中的代碼拷貝，因此計算機程序設(shè)計類課程中的學(xué)生代碼拷貝行為，尤其是學(xué)生之間的拷貝寫作依賴行為，可以通過代碼相似度的計算來發(fā)現(xiàn)、評估和監(jiān)管，從而有助于教師更好地了解學(xué)生的真實編程水平，有效設(shè)計教學(xué)內(nèi)容，促進課程良性發(fā)展。

參考文獻：

[1] Kamiya T， Kusumoto S， Inoue K. CCFinder： A multilinguistic token-based code clone detection system for large scale source code[J].IEEE Transactions on Software Engineering， 2002， 28（7）： 654-670.

[2] Schleimer S， Wilkerson D S， Aiken A. Winnowing： Local algorithms for document fingerprinting[C]//Proceedings of the 2003 ACM SIGMOD international conference on Management of data. New York： ACM， 2003： 76-85.

[3] Koschke R， Falke R， Frenzel P. Clone detection using abstract syntax suffix trees[C]//13th Working Conference on Reverse Engineering. Washington D C： IEEE， 2006： 253-262.

[4] Higo Y， Yasushi U， Nishino M， et al. Incremental code clone detection：A pdg-based approach[C]//18th Working Conference on Reverse Engineering. Washington D C： IEEE， 2011： 3-12.

[5] Roy C K， Cordy J R. A survey on software clone detection research[R]. Kingston： School of Computing， Queens University， 2007.

[6] Jones E L. Metrics based plagarism monitoring[J]. Journal of Computing Sciences in Colleges， 2001， 16（4）： 253-261.

（編輯：宋文婷）