實驗考試系統中的基于詞頻代碼反剽竊技術

趙靖

（安徽科技學院，鳳陽233100）

0 引言

隨著網絡發展，在線編碼在線考試系統OJ 的大量應用，有效地檢測源代碼克隆剽竊有著應用，是代碼設計課程，作業拷貝現象尤為嚴重。由于編程作業這類電子文件易于拷貝，拷貝者只需要通過修改代碼外觀，或者增加注釋、增加多余代碼就可達到拷貝目的?，F有文本檢測工具往往只能針對某些特定的拷貝手段，檢測效果和效率都比較低，也很難應用到代碼中去。

1 源代碼克隆與相似性檢測研究現狀

通過對OJ 后臺源代碼拷貝情況的研究發現，源代碼拷貝行為不僅僅指原封不動的拷貝復制，更多的是把別人的源代碼拷貝過來后稍作修改為自己所用。根據拷貝所付出的努力，常用的拷貝方式[1-4]從易到難依次為：

（1）完整拷貝；

（2）更改注釋語句；

（3）更改空白區域；

（4）修改源代碼格式、行數；

（5）重命名標識符；

（6）修改代碼表達式中的操作數或操作符的次序；

（7）修改源代碼次序；

（8）修改數據類型，但不會基本的代碼執行結果，如int 改為long；

（9）添加冗余語句或變量；

（10）用更為復雜的等價語句替換原有語句。

通過對AOJ 后臺的代碼查看：一類學生拷貝別人的源代碼是因為根本不懂怎么編程，所以采取完全復制，這樣的拷貝是最簡單的；還有一類是不太明白也不想花時間去學習編程，他們往往把別人的源代碼復制過來做點簡單修改，例如上述第（1）到第（6）類的修改，這樣的修改不需要對相關知識做深入了解就可進行，所以也是一種明顯的拷貝行為；另外一類是想通過模仿別人的來入手去編程，其方法也多是在別人源代碼的基礎上進行修改，但這樣的修改往往是對相關知識已有一定了解或做了一定了解之后的修改，實際上已經涉及到了修改源代碼的結構，如第（7）到第（10）類的修改。一個好的檢測系統應該對上述10 種拷貝手段有比較強的檢測能力，否則學生就會利用系統無法檢測蒙混過關。

2 基于保留詞詞頻分布的源代碼相似度計算

2.1 保留詞集合的選擇

代碼的特征是指根據代碼的內在性質，提取出在源代碼中的不易變化的修改特性：代碼的物理結構，包括代碼文件大小、行數，等等，這里以GCC 源代碼為例，C 源代碼的特征可以包含到多個方面，這些特征均可以用于定量統計來反映C 源源代碼本身的特征。C語言源代碼中存在許多各種類型的標識符，主要分為操作符、保留字和用戶自定義標識符三大類，如表1所示。

表1 高級語言的標識符分類(C 語言為例)

代碼特征一般不會隨代碼的表現形式的變化而變化，即使修改也是少數的。所以一般而言，相似代碼的特征之間存在某種內在的聯系。當需要判別代碼間的相似度時，可以通過統計代碼的特征，獲取代碼特征相似度值。

2.2 基于保留詞詞頻的源代碼相似度算法

在傳統的文本相似度方法的基礎上，我們著重利用代碼語言自身的特點——特別是代碼的良構型和表達的等價性上給出如下的計算算法：

輸入：代碼文檔簇Ci (i=1..n)_

輸出：相似度矩陣Sij (i=1..n,j=1..n)矩陣S 為實對稱陣，顯然滿足Sii=1，Sij=Sji，0＜=Sij＜=1

步驟：

（1）for i=1 to n，對文檔Ci a) 預處理子代碼：如刪除注釋，展開宏定義等

b) 將等價的系統保留詞全部用統一的關鍵詞替代：如for 全部替換為while，switch-case 全部替換為if else 等

c) 線性掃描統計關鍵詞詞頻

d) 得到詞頻向量Kvi

（2）for i=1 to n

a) for j=i+1 to n-1

b) 對Kvi，Kvj 利用夾角余弦方法[2,3,5]計算相似度Sij，并排序輸出

（3）利用對稱性填充S

（4）輸出S 結束

3 代碼重復檢測子系統設計與測試

3.1 代碼重復檢測子系統

AOJ 代碼重復檢測系統功能模塊和邏輯結構：①預處理源代碼：預處理源代碼主要是解決兩個問題：刪除掉那些與代碼結構無關的空格、注釋等無用信息；把一些不影響到句子語義或代碼結構的詞法元素用一個規定的通用標記串去替換。由于不是用字符串比較的方法，而采用特征計數的方法，從而，空白行對本文的結果不會構成任何影響，所以預處理中不需要處理空白行。②詞法分析：詞法分析的任務是根據語言的詞法規則對構成源代碼的字符串進行分解，識別出具有獨立意義的記號序列（Token）。詞法規則是Token 的形成規則，它規定了符號字符Token 的起止序列。③展示出代碼分析結果：展示出代碼分析結果的任務是能夠以3D 柱狀圖或3D 餅圖或文本的形式展示出單個代碼和兩個代碼的分析結果，可以僅展示保留字、常量、用戶自定義標識符、預編譯指令、頭文件名、分界符、運算符、運算符，也可以展示全部Token 的，可以展示單個代碼，也可以展示兩個代碼的對比情況。④計算兩個代碼的相似度：采用特征計數的方法計算兩個代碼的相似度，把每個代碼分析出的特征放入Map，計算時先讓每個Map 中包含所有要比較的字段（最大化），然后取出組成相應的值組成多頻集合，通過集合的交集與并集求出每個字段的權重，然后相加，最后除以集合總的大小（歸一化），從而求出了兩個代碼間的相似度，最后由相似度的值給出兩個代碼是否存在拷貝可能的結論。

3.2 實驗數據與測試結果

為了驗證基于詞頻的源代碼相似性檢測方法，我們利用JFC/Eclipse/JFreeChart 等插件技術實現了原型系統系統可以對源代碼文本進行處理分析，并給出可視化分析結果與評價意見，如圖2-4 所示，由于系統算法效率較高，可以對大尺寸、多文件的源代碼文件計算給出實時響應。

圖3 樣例源代碼對比分析——關鍵字的柱狀圖

圖4 樣例源代碼對比分析——關鍵字的餅圖

3.3 系統測試結果

我們針對上文所述的幾種常見的拷貝手段的分析做了以下的實驗，包括對while-for 循環、int-long、子函數替換源代碼塊等替代，部分源代碼來自于在線競賽平臺的服務器，其結果如表2。

圖5

表2

4 結語

考慮到代碼的高度結構化特征，以及結構化特征是依賴于代碼保留詞的事實，我們在傳統的基于特征或者結構度量的方法基礎上引入了保留字頻率向量模型來檢測代碼間的相似性，實驗表明基于保留詞詞頻的相似性檢測方法具有較強的抗干擾能力，可以克服常用的拷貝方法帶來的噪聲；實驗效果表明可以快速檢測出上述的近10 種源代碼簡單克隆方法，實驗效果較好。以后考慮進一步改進等價保留字模型或結合代碼的語義層面或引入編譯優化技術和反匯編工具對源代碼進行規一化，消除增加冗余源代碼、重排序源代碼塊、替換控制結構等價等常規方法無法檢測到的干擾等。