趙靖

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

0 引言

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

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

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

（1）完整拷貝；

（2）更改注釋語(yǔ)句；

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

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

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

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

（7）修改源代碼次序；

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

（9）添加冗余語(yǔ)句或變量；

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

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

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

2.1 保留詞集合的選擇

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

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

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

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

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

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

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

步驟：

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

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

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

d) 得到詞頻向量Kvi

（2）for i=1 to n

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

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

（3）利用對(duì)稱性填充S

（4）輸出S 結(jié)束

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

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

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

3.2 實(shí)驗(yàn)數(shù)據(jù)與測(cè)試結(jié)果

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

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

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

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

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

圖5

表2

4 結(jié)語(yǔ)

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