基于抽象語法樹的代碼抄襲檢測方法的改進*

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

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

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

1 AST簡介

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

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

2 基于AST的代碼抄襲檢測方法的改進

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

2.1 加權(quán)簡化語法樹

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

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

(1)

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

(2)

(3)

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

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

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

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

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

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

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

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

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

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

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

特征向量間距離的計算公式為

(4)

2.3 計算代碼相似度

(1)節(jié)點相似度計算.

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

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

(5)

節(jié)點語義相似度sims的計算公式為

(6)

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

(7)

在實際的代碼抄襲檢測過程中，語義相似度和文本相似度都很重要，綜合考慮這2類相似度，得到節(jié)點a和b之間的相似度的計算公式為

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

(8)

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

(9)

(10)

(2)子樹相似度計算.

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

(11)

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

(12)

(13)

(3)代碼相似度計算.

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

(14)

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

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

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

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

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

Step 2 語法分析.使用ANTLR對源代碼進行語法分析，得到AST.

Step 3 節(jié)點整合.對語法分析樹中的節(jié)點進行整合，得到簡化后的AST.

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

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

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

3 實驗部分

3.1 實驗環(huán)境

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

3.2 實驗數(shù)據(jù)

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

表1 源碼修改說明

3.3 評估方法

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

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

3.4 實驗結(jié)果

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

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

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

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

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

4 結(jié)語

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