基于代碼相似度的隱含學生行為模式挖掘

徐雅靜　李通　劉玉濤

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

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

0 引 言

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

1 代碼相似度檢測

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

1.1 預處理、標準化、Hash

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

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

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

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

1.2 GS-LCS算法

Hash編碼后，對于源代碼的匹配就轉換成對于數字序列的匹配。GS-LCS算法中，針對學生在代碼拷貝中可能增加、刪除或改變部分表達式，采用忽略間隙策略進行匹配；對于代碼塊的順序改變、代碼塊中表達式的順序，則采用分段策略進行匹配。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]范圍內（θ1為預先設置的可忽略間隙距離），視為一個相似子序列，如圖3所示相似子序列1。回溯算法每調用一次找到一個子序列，回溯算法具體如下：

步驟4：更新矩陣，即將已匹配的序列所在行全部置0，反復調用回溯算法找出所有相似子序列li，注意相似子序列長度>1。

經過優化，GS-LCS算法的時間復雜度為O（M*N）。

1.3 計算相似度

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

（2）

2 實驗分析

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

2.1 作業相似度分析

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

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

2.2 學生拷貝行為分析

根據相似度分析，我們對每一個學生在6次作業中出現的拷貝行為次數進行統計，統計結果如圖4所示，可以看出一班的拷貝行為最輕，二班其次，三班最為嚴重。

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

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

3 結 語

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

參考文獻：

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

（編輯：宋文婷）