劉飛翔，龍冬冬，歐幸茹，陳昌奉

(吉首大學(xué)信息科學(xué)與工程學(xué)院，湖南 吉首 416000)

隨著數(shù)據(jù)開(kāi)源的不斷擴(kuò)大，代碼抄襲現(xiàn)象在程序設(shè)計(jì)類課程作業(yè)中頻頻出現(xiàn).為了保證程序設(shè)計(jì)類課程教學(xué)質(zhì)量和規(guī)范軟件開(kāi)發(fā)行為，國(guó)內(nèi)外研究人員設(shè)計(jì)了各種類型的代碼抄襲檢測(cè)方法，其中源代碼的抽象語(yǔ)法樹(shù)(Abstract Syntax Tree，AST)能有效地表示出源碼中的重要語(yǔ)法特征信息，被廣泛應(yīng)用在代碼抄襲檢測(cè)中[1-5].然而，不同源代碼的AST中存在數(shù)量不一、結(jié)構(gòu)不一的子樹(shù)和節(jié)點(diǎn)，會(huì)導(dǎo)致基于AST的代碼抄襲檢測(cè)效果不佳[6].此外，在代碼語(yǔ)義表達(dá)方面的局限性，也會(huì)使得基于AST的代碼抄襲檢測(cè)方法無(wú)法準(zhǔn)確檢測(cè)出語(yǔ)義層面的代碼抄襲[7].針對(duì)以上問(wèn)題，筆者擬設(shè)計(jì)將加權(quán)簡(jiǎn)化語(yǔ)法樹(shù)和子樹(shù)匹配相結(jié)合的程序代碼抄襲檢測(cè)方法，以期實(shí)現(xiàn)對(duì)源代碼語(yǔ)義層面抄襲的檢測(cè)，同時(shí)提高檢測(cè)準(zhǔn)確率.

1 AST簡(jiǎn)介

AST也稱語(yǔ)法樹(shù)，它由源代碼經(jīng)過(guò)詞法分析和語(yǔ)法分析生成[8]，樹(shù)上的每個(gè)節(jié)點(diǎn)都表示源代碼的一種結(jié)構(gòu).基于AST的抄襲檢測(cè)大多是對(duì)兩者的每一棵子樹(shù)進(jìn)行遍歷對(duì)比，從而得出相似度.因?yàn)樽訕?shù)的對(duì)比順序不會(huì)影響對(duì)比結(jié)果，所以此方法能有效應(yīng)對(duì)標(biāo)識(shí)符重命名、代碼重排序等抄襲手段[9].

代碼抄襲檢測(cè)首先需要對(duì)源文件進(jìn)行編譯，借助開(kāi)源語(yǔ)法分析器(ANother Tool for Language Recognition，ANTLR)和GNU編譯器套件(GNU Compiler Collection，GCC)等工具，經(jīng)過(guò)詞法分析、語(yǔ)法分析等一系列過(guò)程后生成對(duì)應(yīng)源碼的AST；接著對(duì)語(yǔ)法樹(shù)子樹(shù)上的信息進(jìn)行特征提取，將信息轉(zhuǎn)化成特征向量、Hash值或者特征標(biāo)記串集合等形式；然后選取如編輯距離、歐氏距離、樹(shù)核函數(shù)等方法計(jì)算子樹(shù)的距離，從而得到相似度；最后通過(guò)與閾值進(jìn)行對(duì)比來(lái)判定是否存在抄襲[10].

2 基于AST的代碼抄襲檢測(cè)方法的改進(jìn)

改進(jìn)的基于AST的代碼抄襲檢測(cè)方法(簡(jiǎn)稱IAST)充分利用詞頻-逆詞頻[11](Term Frequency-Inverse Document Frequency，TF-IDF)設(shè)置語(yǔ)法樹(shù)不同節(jié)點(diǎn)的權(quán)值，并根據(jù)生成的語(yǔ)法樹(shù)中的不同結(jié)構(gòu)成分分別設(shè)置公式以實(shí)現(xiàn)對(duì)源代碼的相似度計(jì)算.此方法的實(shí)現(xiàn)主要分為3個(gè)階段，即加權(quán)簡(jiǎn)化語(yǔ)法樹(shù)、生成特征向量和相似距離、計(jì)算代碼相似度.

2.1 加權(quán)簡(jiǎn)化語(yǔ)法樹(shù)

數(shù)據(jù)集中的每一份代碼都對(duì)應(yīng)著一棵AST，每棵語(yǔ)法樹(shù)上都存在數(shù)量不一的子樹(shù).用A表示一棵語(yǔ)法樹(shù)，AI表示語(yǔ)法樹(shù)A的第I棵子樹(shù)，樹(shù)上的節(jié)點(diǎn)記為a，子樹(shù)AI的節(jié)點(diǎn)的權(quán)值記為Fa,AI.根據(jù)TF-IDF的定義，對(duì)子樹(shù)AI進(jìn)行中序遍歷得到子樹(shù)節(jié)點(diǎn)，若子樹(shù)節(jié)點(diǎn)都是不能表示語(yǔ)義信息的非關(guān)鍵節(jié)點(diǎn)，則認(rèn)為子樹(shù)AI在語(yǔ)義上沒(méi)有貢獻(xiàn)，設(shè)置該子樹(shù)的權(quán)值為0；若子樹(shù)節(jié)點(diǎn)并非都是非關(guān)鍵節(jié)點(diǎn)，則權(quán)值Fa,AI的計(jì)算公式為

Fa,AI=WTF(a,AI)·WIDF(a,AI),

(1)

其中WTF表示子樹(shù)節(jié)點(diǎn)的詞頻，WIDF表示子樹(shù)節(jié)點(diǎn)的逆詞頻.由TF-IDF的定義可知，WTF(a,AI)和WIDF(a,AI)的計(jì)算公式分別為

(2)

(3)

其中：f(a,AI)表示節(jié)點(diǎn)a在AST的AI中出現(xiàn)的頻數(shù)；f(AI)表示子樹(shù)AI中的節(jié)點(diǎn)總數(shù)；c(a)表示包含節(jié)點(diǎn)a的子樹(shù)總數(shù)；p表示AST的子樹(shù)總數(shù)，也可以表示數(shù)據(jù)集中代碼文件的總數(shù).

對(duì)AST進(jìn)行加權(quán)簡(jiǎn)化之后，代碼樣本中存在的框架部分會(huì)被賦予較低的權(quán)重，在檢測(cè)時(shí)可以降低正例樣本被檢測(cè)為負(fù)樣本的概率，有助于提高抄襲檢測(cè)的準(zhǔn)確度.

2.2 生成特征向量和相似距離

將遍歷數(shù)據(jù)集中所有語(yǔ)法樹(shù)得到的關(guān)鍵節(jié)點(diǎn)類型的集合作為特征項(xiàng)，則子樹(shù)的特征向量由它所包含的特征項(xiàng)表示，子樹(shù)根節(jié)點(diǎn)的特征向量由除根節(jié)點(diǎn)之外的所有節(jié)點(diǎn)的特征向量綜合表示，這樣子樹(shù)根節(jié)點(diǎn)的特征向量能綜合表示子樹(shù)所含的信息量.

提取代碼樣本A和B，將樣本A和B分別用節(jié)點(diǎn)a和b表示.設(shè)樣本A和B包含的節(jié)點(diǎn)個(gè)數(shù)分別為m和n，則樣本A和B的節(jié)點(diǎn)表示形式分別為

A={a1,a2,…,am},B={b1,b2,…,bn}.

設(shè)樣本A和B包含的子樹(shù)個(gè)數(shù)分別為p和q，則樣本A和B的子樹(shù)表示形式分別為

A={A1,A2,…,Ap},B={B1,B2,…,Bq}.

設(shè)子樹(shù)樣本AI和BJ包含的節(jié)點(diǎn)個(gè)數(shù)分別為k和l，則子樹(shù)AI和BJ用節(jié)點(diǎn)分別表示為

AI={a1,a2,…,ak},BJ={b1,b2,…,bl},

其中ai和bj分別為樣本A的第i個(gè)子節(jié)點(diǎn)和樣本B的第j個(gè)子節(jié)點(diǎn).設(shè)節(jié)點(diǎn)的特征向量為x=(x1,x2,…,xt)，其中xi為節(jié)點(diǎn)對(duì)應(yīng)的特征項(xiàng)，t為特征項(xiàng)的個(gè)數(shù)，那么樣本A中節(jié)點(diǎn)a與樣本B中節(jié)點(diǎn)b對(duì)應(yīng)的特征向量分別為

特征向量間距離的計(jì)算公式為

(4)

2.3 計(jì)算代碼相似度

(1)節(jié)點(diǎn)相似度計(jì)算.

在代碼抄襲檢測(cè)過(guò)程中，可以將代碼節(jié)點(diǎn)的相似度計(jì)算分為語(yǔ)義相似度計(jì)算和文本相似度計(jì)算[12]，通過(guò)賦予合適的權(quán)重計(jì)算出節(jié)點(diǎn)相似度.

在抄襲檢測(cè)過(guò)程中，為了顯著劃分抄襲和非抄襲的界限，引入如下函數(shù)：

(5)

節(jié)點(diǎn)語(yǔ)義相似度sims的計(jì)算公式為

(6)

節(jié)點(diǎn)文本相似度simt可以表示樣本對(duì)應(yīng)的各個(gè)節(jié)點(diǎn)之間的權(quán)重相關(guān)度，具體計(jì)算公式為

(7)

在實(shí)際的代碼抄襲檢測(cè)過(guò)程中，語(yǔ)義相似度和文本相似度都很重要，綜合考慮這2類相似度，得到節(jié)點(diǎn)a和b之間的相似度的計(jì)算公式為

sim(a,b)=α1sims(a,b)+α2simt(a,b).

(8)

由于樣本A中的節(jié)點(diǎn)ai可能與樣本B中的多個(gè)節(jié)點(diǎn)存在相似關(guān)系，因此樣本A中的節(jié)點(diǎn)ai與樣本B中的節(jié)點(diǎn)的相似度取樣本A中的節(jié)點(diǎn)ai與樣本B中的所有節(jié)點(diǎn)的相似度的最大值，樣本B的節(jié)點(diǎn)相似度計(jì)算同樣本A.計(jì)算公式為

(9)

(10)

(2)子樹(shù)相似度計(jì)算.

在獲取節(jié)點(diǎn)相似度之后，可根據(jù)AST的結(jié)構(gòu)特征計(jì)算2份樣本代碼之間的子樹(shù)相似度.由于某一子樹(shù)可能包含多個(gè)子節(jié)點(diǎn)，因此子樹(shù)之間的代碼相似度計(jì)算公式為

(11)

類似于節(jié)點(diǎn)相似度計(jì)算方法，樣本A和B之間的子樹(shù)相似度的計(jì)算公式分別為

(12)

(13)

(3)代碼相似度計(jì)算.

利用(5)～(13)式可以計(jì)算出樣本A和B對(duì)應(yīng)的AST的節(jié)點(diǎn)相似度和子樹(shù)相似度，于是代碼樣本A和B對(duì)應(yīng)的語(yǔ)法樹(shù)相似度，即代碼A和B之間的相似度計(jì)算公式為

(14)

2.4 算法實(shí)現(xiàn)流程

在IAST中，首先利用語(yǔ)法分析工具生成源代碼的AST，并通過(guò)對(duì)變量名進(jìn)行統(tǒng)一等方式實(shí)現(xiàn)AST的簡(jiǎn)化；接著采用TF-IDF算法對(duì)語(yǔ)法樹(shù)中的節(jié)點(diǎn)進(jìn)行賦權(quán)；然后提取語(yǔ)法樹(shù)中節(jié)點(diǎn)的類型去重集合作為特征項(xiàng)，并統(tǒng)計(jì)所有節(jié)點(diǎn)的特征向量；最后通過(guò)計(jì)算每棵子樹(shù)的距離實(shí)現(xiàn)抄襲判定.基于IAST的代碼抄襲檢測(cè)方法的實(shí)現(xiàn)流程如圖1所示.

圖1 基于IAST的代碼抄襲檢測(cè)算法流程

算法實(shí)現(xiàn)流程如下：

Step 1 初始化.設(shè)置語(yǔ)義和文本相似度配比參數(shù)α1，α2及抄襲判定閾值θ.

Step 2 語(yǔ)法分析.使用ANTLR對(duì)源代碼進(jìn)行語(yǔ)法分析，得到AST.

Step 3 節(jié)點(diǎn)整合.對(duì)語(yǔ)法分析樹(shù)中的節(jié)點(diǎn)進(jìn)行整合，得到簡(jiǎn)化后的AST.

Step 4 權(quán)重賦值.采用TF-IDF((1)～(3)式)對(duì)簡(jiǎn)化后的AST中的節(jié)點(diǎn)進(jìn)行權(quán)重賦值.

Step 5 特征向量和相似距離生成.對(duì)AST進(jìn)行特征提取，得到表征節(jié)點(diǎn)的特征向量，并利用(4)式計(jì)算源代碼之間的相似距離.

Step 6 相似度計(jì)算.利用(14)式計(jì)算源代碼兩兩之間的相似度，并通過(guò)與閾值進(jìn)行比較來(lái)判定抄襲是否存在.

3 實(shí)驗(yàn)部分

3.1 實(shí)驗(yàn)環(huán)境

本實(shí)驗(yàn)操作系統(tǒng)為Windows10，搭載6核處理器，16 GB內(nèi)存，1T硬盤(pán).實(shí)驗(yàn)主體程序代碼使用python語(yǔ)言完成.

3.2 實(shí)驗(yàn)數(shù)據(jù)

采用C語(yǔ)言程序代碼作為實(shí)驗(yàn)數(shù)據(jù)，數(shù)據(jù)集包含10個(gè)編程題的源代碼及對(duì)應(yīng)的12種抄襲手段產(chǎn)生的代碼，源碼修改方式與對(duì)應(yīng)的抄襲類型見(jiàn)表1.

表1 源碼修改說(shuō)明

3.3 評(píng)估方法

采用準(zhǔn)確率[13](E)對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行評(píng)估.準(zhǔn)確率是指檢測(cè)結(jié)果正確的樣本數(shù)占總樣本的比例，其計(jì)算公式為

其中：CTP表示檢測(cè)結(jié)果正確的抄襲代碼樣本數(shù)；CTN表示檢測(cè)結(jié)果正確的非抄襲代碼樣本數(shù)；CFP表示檢測(cè)結(jié)果錯(cuò)誤的抄襲代碼樣本數(shù)；CFN表示檢測(cè)結(jié)果錯(cuò)誤的非抄襲代碼樣本數(shù).

3.4 實(shí)驗(yàn)結(jié)果

基于實(shí)驗(yàn)給出的數(shù)據(jù)集，設(shè)置相似度配比系數(shù)和閾值，得到不同系數(shù)對(duì)應(yīng)的抄襲檢測(cè)準(zhǔn)確率(表2).

表2 不同系數(shù)對(duì)應(yīng)的抄襲檢測(cè)結(jié)果

由表2可知，當(dāng)α1=0.75，α2=0.25時(shí)，準(zhǔn)確率比其他相似度配比的更高，且在該相似度配比下當(dāng)θ=0.5時(shí)，準(zhǔn)確率比其他相似度系數(shù)閾值的更高.于是，將語(yǔ)義和文本相似度的配比分別設(shè)置為0.75和0.25，閾值設(shè)置為0.5，再對(duì)數(shù)據(jù)集中不同抄襲類型的代碼分別進(jìn)行檢測(cè)，用準(zhǔn)確率衡量檢測(cè)效果.將IAST與基于AST的抄襲檢測(cè)方法[7](Z-AST)進(jìn)行對(duì)比，得到不同抄襲代碼類型的檢測(cè)準(zhǔn)確率(表3).

表3 基于不同抄襲類型的檢測(cè)結(jié)果

由表3可知，IAST對(duì)Type-1和Type-2類型的代碼抄襲行為檢測(cè)準(zhǔn)確率均高于0.9，對(duì)Type-3和Type-4類型的檢測(cè)準(zhǔn)確率相對(duì)較低，分別為0.878和0.650，但是其有效性較Z-AST的高.由此可見(jiàn)，IAST能有效檢測(cè)Type-1～4類型的代碼抄襲行為.

4 結(jié)語(yǔ)

針對(duì)傳統(tǒng)基于AST代碼抄襲檢測(cè)中存在的問(wèn)題，筆者設(shè)計(jì)了改進(jìn)的基于AST的代碼抄襲檢測(cè)方法.該方法通過(guò)將源代碼AST分解為子樹(shù)，再檢測(cè)子樹(shù)的語(yǔ)義相似度和文本相似度，從而確定代碼之間的相似度.實(shí)驗(yàn)結(jié)果表明，IAST能有效地檢測(cè)Type-1～2及部分Type-3～4類型的代碼抄襲，對(duì)于數(shù)據(jù)類型替換、代碼結(jié)構(gòu)等價(jià)替換等傳統(tǒng)的基于AST的代碼抄襲檢測(cè)方法無(wú)法判別的抄襲行為同樣具有較好的檢測(cè)效果.另外，與Z-AST在相同的小量級(jí)別的代碼數(shù)據(jù)集上進(jìn)行對(duì)比時(shí)，該方法的檢測(cè)有效性更高.值得一提的是，IAST雖然對(duì)語(yǔ)法樹(shù)結(jié)構(gòu)作了一定的簡(jiǎn)化，但是采用的相似度計(jì)算方法仍要對(duì)每棵子樹(shù)進(jìn)行遍歷，方法的時(shí)間復(fù)雜度仍然較高，因此筆者接下來(lái)將針對(duì)這一問(wèn)題繼續(xù)展開(kāi)研究.