趙靖

（安徽科技學(xué)院，鳳陽233100）

0 引言

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

1 源代碼克隆與相似性檢測研究現(xiàn)狀

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

（1）完整拷貝；

（2）更改注釋語句；

（3）更改空白區(qū)域；

（4）修改源代碼格式、行數(shù)；

（5）重命名標(biāo)識符；

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

（7）修改源代碼次序；

（8）修改數(shù)據(jù)類型，但不會基本的代碼執(zhí)行結(jié)果，如int 改為long；

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

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

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

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

2.1 保留詞集合的選擇

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

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

代碼特征一般不會隨代碼的表現(xiàn)形式的變化而變化，即使修改也是少數(shù)的。所以一般而言，相似代碼的特征之間存在某種內(nèi)在的聯(lián)系。當(dāng)需要判別代碼間的相似度時，可以通過統(tǒng)計代碼的特征，獲取代碼特征相似度值。

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

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

輸入：代碼文檔簇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) 預(yù)處理子代碼：如刪除注釋，展開宏定義等

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

c) 線性掃描統(tǒng)計關(guān)鍵詞詞頻

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 結(jié)束

3 代碼重復(fù)檢測子系統(tǒng)設(shè)計與測試

3.1 代碼重復(fù)檢測子系統(tǒng)

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

3.2 實驗數(shù)據(jù)與測試結(jié)果

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

圖3 樣例源代碼對比分析——關(guān)鍵字的柱狀圖

圖4 樣例源代碼對比分析——關(guān)鍵字的餅圖

3.3 系統(tǒng)測試結(jié)果

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

圖5

表2

4 結(jié)語

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