基于AST的程序代碼抄襲檢測(cè)方法研究

朱良梅，洪曉彬

（廣州工商學(xué)院 工學(xué)院，廣東 廣州 510850)

0 引言

代碼抄襲是指復(fù)制或拷貝代碼而不做任何改動(dòng)或只是進(jìn)行適度的修改，代碼抄襲問(wèn)題在高校程序設(shè)計(jì)類(lèi)課程中普遍存在。對(duì)學(xué)生的調(diào)查研究表明：33%～75%的學(xué)生承認(rèn)在學(xué)習(xí)期間至少抄襲過(guò)一次[1-2]，抄襲導(dǎo)致考試出現(xiàn)更高的不及格率和較低的考試成績(jī)，考試不及格的學(xué)生中大約有84%曾經(jīng)抄襲編程作業(yè)[3]。代碼抄襲現(xiàn)象泛濫已經(jīng)嚴(yán)重影響學(xué)生能力的培養(yǎng)和教師教學(xué)的效果，然而在眾多作業(yè)中，依靠人工方式分辨出每份作業(yè)是否抄襲和作業(yè)中哪些地方涉及抄襲是一件費(fèi)時(shí)費(fèi)力的事情。為了更高效地檢測(cè)作業(yè)抄襲問(wèn)題，出現(xiàn)了一大批程序代碼抄襲檢測(cè)工具，這類(lèi)工具通過(guò)測(cè)量代碼對(duì)的相似度來(lái)判斷是否涉及抄襲，相似度越高則抄襲的可能性越大，較低的相似度則意味著兩份作業(yè)沒(méi)有抄襲。代碼相似度檢測(cè)是代碼抄襲檢測(cè)的核心，代碼相似度檢測(cè)技術(shù)的研究具有重要意義。

目前常見(jiàn)的相似度檢測(cè)系統(tǒng)采用較為簡(jiǎn)單的文本或者詞法分析，抗混淆能力較弱，無(wú)法檢測(cè)控制結(jié)構(gòu)等價(jià)替換等抄襲行為；一般在整個(gè)代碼提交集合中進(jìn)行檢測(cè)，缺少有效篩選檢測(cè)候選集的方法，計(jì)算量較大。本文提出了基于抽象語(yǔ)法樹(shù)(AST) 的Java程序代碼抄襲檢測(cè)方法，首先通過(guò)語(yǔ)法分析生成程序的AST，然后遍歷AST，過(guò)濾不重要的節(jié)點(diǎn)，對(duì)選擇和循環(huán)結(jié)構(gòu)語(yǔ)句進(jìn)行語(yǔ)義轉(zhuǎn)換，賦予節(jié)點(diǎn)語(yǔ)義信息，構(gòu)造程序的特征序列；統(tǒng)計(jì)特征序列的節(jié)點(diǎn)頻度，生成特征向量，通過(guò)聚類(lèi)分析將同一批次作業(yè)劃分為若干較小的“抄襲團(tuán)伙”；在“抄襲團(tuán)伙”內(nèi)使用貪婪字符串匹配算法比對(duì)特征序列計(jì)算程序相似度。

1 相關(guān)工作

早期的代碼相似度檢測(cè)技術(shù)的研究主要基于屬性計(jì)數(shù)的方法，其基本原理是從源代碼中抽取各種屬性度量元作為相似度評(píng)判的依據(jù)。該方法與所用的程序設(shè)計(jì)語(yǔ)言無(wú)關(guān)，實(shí)現(xiàn)較為簡(jiǎn)單，但是不能分析部分程序段的抄襲，而且增加向量維數(shù)并不能改善檢測(cè)效果。

后期的研究主要考慮的是代碼的結(jié)構(gòu)信息，目前基于結(jié)構(gòu)度量的相似度檢測(cè)方法被主要包括：基于文本、基于詞法、基于語(yǔ)法、基于語(yǔ)義的檢測(cè)方法?；谖谋镜臋z測(cè)方法將源代碼看作字符序列，比較代碼字符序列相似度并且返回字符串匹配結(jié)果集。這類(lèi)方法易于實(shí)現(xiàn)，而且與語(yǔ)言無(wú)關(guān)，但是不能很好地檢測(cè)出在句法和語(yǔ)義層面上的代碼修改?；谠~法的檢測(cè)方法將代碼轉(zhuǎn)換成token（符號(hào)、詞匯）。將token 序列視為抽象的代碼表示。相比于基于文本的代碼表征方法來(lái)說(shuō)，這種方法能夠匹配到代碼的特有信息，但從本質(zhì)上沒(méi)有考慮代碼中所包含的結(jié)構(gòu)信息，對(duì)代碼語(yǔ)句修改比較敏感。基于語(yǔ)法的檢測(cè)方法考慮源代碼語(yǔ)法規(guī)則，將源代碼轉(zhuǎn)換。

為其對(duì)應(yīng)的抽象語(yǔ)法樹(shù)?；跇?shù)的方法可以避免由于格式和句法問(wèn)題引起的問(wèn)題，能夠考慮到源代碼的結(jié)構(gòu)特性，其缺點(diǎn)是不能識(shí)別出標(biāo)識(shí)符和文本值的不同，并且計(jì)算開(kāi)銷(xiāo)大。基于語(yǔ)義的方法不僅希望獲得代碼之中的結(jié)構(gòu)信息，還試圖獲得代碼中的語(yǔ)義信息，復(fù)雜度非常高。除此之外，還有學(xué)者提出了新的檢測(cè)方法,比如，基于深度神經(jīng)網(wǎng)絡(luò)的Oreo[4]、基于遞歸自編碼器和程序向量樹(shù)的檢測(cè)方法[5-6]等。

2 基于AST 的程序代碼抄襲檢測(cè)方法

2.1 生成程序AST

依次讀取程序代碼集中的一個(gè)個(gè)代碼文件，利用Eclipse 平臺(tái)的JDT(Java Development Tool) 工具套件自動(dòng)化抽取代碼集中Java 程序的抽象語(yǔ)法樹(shù)。圖1 所示為由Java 語(yǔ)言編寫(xiě)的一段示例代碼及其對(duì)應(yīng)的AST，AST 自動(dòng)去除了原代碼中的注釋、空格、換行等，為抄襲檢測(cè)降低了干擾；此外，AST 中除了與原代碼相對(duì)應(yīng)的葉子節(jié)點(diǎn)外，新增了大量非葉子節(jié)點(diǎn)，使得整個(gè)AST的節(jié)點(diǎn)序列長(zhǎng)度相比原代碼長(zhǎng)度有明顯增長(zhǎng)。

圖1 Java示例代碼和抽象語(yǔ)法樹(shù)

2.2 構(gòu)造特征序列

基于樹(shù)進(jìn)行子樹(shù)匹配，計(jì)算開(kāi)銷(xiāo)較大，本文對(duì)AST進(jìn)行深度遍歷，將節(jié)點(diǎn)序列轉(zhuǎn)換為字符串特征序列。由于AST 的節(jié)點(diǎn)序列長(zhǎng)度相比原代碼長(zhǎng)度有明顯增長(zhǎng)，本文在遍歷過(guò)程中通過(guò)節(jié)點(diǎn)過(guò)濾，有效縮短序列長(zhǎng)度；此外，通過(guò)對(duì)等價(jià)控制結(jié)構(gòu)進(jìn)行轉(zhuǎn)換、對(duì)語(yǔ)義模糊節(jié)點(diǎn)賦予語(yǔ)義信息、運(yùn)算符分類(lèi)等，達(dá)到提取AST的結(jié)構(gòu)和語(yǔ)義特征的目的。

2.2.1 節(jié)點(diǎn)過(guò)濾

1) 過(guò)濾函數(shù)外節(jié)點(diǎn)

由于一個(gè)類(lèi)所實(shí)現(xiàn)的功能主要是由其行為即函數(shù)所決定的，其他節(jié)點(diǎn)與類(lèi)功能沒(méi)有直接聯(lián)系，并且這部分節(jié)點(diǎn)極易被修改，以達(dá)到躲避抄襲檢測(cè)的目的。因此，本文在遍歷AST 節(jié)點(diǎn)序列時(shí)，忽略除函數(shù)以外的其他節(jié)點(diǎn)，只對(duì)文件內(nèi)的若干函數(shù)及其內(nèi)部節(jié)點(diǎn)進(jìn)行遍歷，從而自動(dòng)排除一系列簡(jiǎn)單的代碼修改所帶來(lái)的噪聲影響。

2) 過(guò)濾無(wú)具體語(yǔ)義的節(jié)點(diǎn)

通過(guò)對(duì)AST包含的各種節(jié)點(diǎn)類(lèi)型進(jìn)行比較分析，發(fā)現(xiàn)其中有一些節(jié)點(diǎn)并不包含具體的語(yǔ)義信息，如圖2 中的節(jié)點(diǎn)ExpressionStatement、QualifiedName，這些節(jié)點(diǎn)對(duì)于代碼相似度檢測(cè)意義不大，本文予以過(guò)濾。

圖2 合并try-catch-finally語(yǔ)句

3) 過(guò)濾輸出日志相關(guān)的節(jié)點(diǎn)

對(duì)于常見(jiàn)的通過(guò)增加輸出日志的代碼以改變?cè)绦蚪Y(jié)構(gòu)的抄襲行為，獲取METHOD_INVOCATION類(lèi)型節(jié)點(diǎn)的被調(diào)用的函數(shù)名，過(guò)濾掉與輸出日志相關(guān)的函數(shù)調(diào)用，如println、print、debug、info、error、log等。

2.2.2 等價(jià)控制結(jié)構(gòu)轉(zhuǎn)換

1) 選擇結(jié)構(gòu)

對(duì)if-else、switch-case 和條件判斷語(yǔ)句三種選擇結(jié)構(gòu)進(jìn)行等價(jià)處理，轉(zhuǎn)換為SELECT_CONDITION 和SELECT_BODY兩類(lèi)節(jié)點(diǎn)。

2) 循環(huán)結(jié)構(gòu)

對(duì)while、do-while 和for 三種循環(huán)結(jié)構(gòu)進(jìn)行等價(jià)處理，轉(zhuǎn)換為L(zhǎng)OOP_CONDITION和LOOP_BODY兩類(lèi)節(jié)點(diǎn)。

2.2.3 賦予語(yǔ)義信息

有些節(jié)點(diǎn)包含的語(yǔ)義信息模糊，需要結(jié)合上下文為這些節(jié)點(diǎn)進(jìn)一步賦予語(yǔ)義信息。如將Block類(lèi)型的節(jié)點(diǎn)分為：METHOD_BODY、LOOP_BODY、SELECT_BODY。

2.2.4 運(yùn)算符分類(lèi)

對(duì)前綴、中綴、后綴表達(dá)式按照運(yùn)算類(lèi)型分為NUM_EXPRESSION、RELATION_EXPRESSION、LOGIC_EXPRESSION、BIT_EXPRESSION和ASSIGN_EXPRESSION，需要注意a++、++a、a=a+1，這三類(lèi)語(yǔ)句雖然寫(xiě)法不同，但是實(shí)現(xiàn)的功能都是自增1，統(tǒng)一記為ASSIGN_EXPRESSION。

2.2.5 聲明語(yǔ)句拆分

變量聲明語(yǔ)句轉(zhuǎn)換為節(jié)點(diǎn)VAR_DEF，將合并的多個(gè)變量的聲明語(yǔ)句拆分成多個(gè)單獨(dú)的變量聲明；對(duì)帶有初始化值的變量聲明語(yǔ)句拆分為變量聲明VAR_DEF和賦值A(chǔ)SSIGN_EXPRESSION。

2.2.6 try-catch-finally語(yǔ)句合并

對(duì)try-catch-finally 語(yǔ)句進(jìn)行合并，如圖2 所示，只關(guān)注與函數(shù)功能相關(guān)的代碼段code_block1 和code_block3，忽略與對(duì)異常的處理相關(guān)的代碼段code_block2。

經(jīng)過(guò)對(duì)節(jié)點(diǎn)的過(guò)濾、合并、分類(lèi)、轉(zhuǎn)換后共匯總得到18種節(jié)點(diǎn)類(lèi)型，同時(shí)為了進(jìn)一步縮短節(jié)點(diǎn)序列的長(zhǎng)度，分別使用一個(gè)唯一的字母代替原節(jié)點(diǎn)類(lèi)型，每個(gè)程序文件由這18個(gè)字母的不同組合表示，最終形成程序的特征序列。節(jié)點(diǎn)類(lèi)型與對(duì)應(yīng)字母關(guān)系如表1所示。

表1 抽象語(yǔ)法樹(shù)節(jié)點(diǎn)類(lèi)型和對(duì)應(yīng)的字母

2.3 聚類(lèi)分析和抄襲檢測(cè)

為了更高效地篩選抄襲檢測(cè)候選代碼集，使用聚類(lèi)算法將代碼集劃分為若干“抄襲團(tuán)伙”。統(tǒng)計(jì)程序特征序列中不同節(jié)點(diǎn)類(lèi)型的頻度，將程序特征序列構(gòu)造為一個(gè)18維的整型特征向量，向量中的每一維代表一種節(jié)點(diǎn)類(lèi)型，每一維的值代表該節(jié)點(diǎn)類(lèi)型的頻度。例如，圖2 中示例代碼的節(jié)點(diǎn)類(lèi)型序列為：METHOD_DEF、METHOD_BODY、VAR_DEF、ASSIGN_EXPRESSION，特征序列為：NPJI，特征向量為(0，...,1,1,...,1,0,1,0,0) ,其中第9、10、14、16維的值為1，其他維的值為0。

程序代碼作業(yè)集被轉(zhuǎn)換為特征向量的集合，使用K-means 算法完成向量聚類(lèi)，找出代碼作業(yè)集中的“抄襲團(tuán)伙”。K-means算法將一組特征向量劃分為K個(gè)無(wú)交集的簇，具有原理簡(jiǎn)單、收斂速度較快的特點(diǎn)，但需要用戶指定聚類(lèi)個(gè)數(shù)K。為了確定較為合適的聚類(lèi)個(gè)數(shù)，使用輪廓系數(shù)作為選擇聚類(lèi)個(gè)數(shù)的依據(jù)。根據(jù)“簇內(nèi)差異小，簇外差異大”的原則，整個(gè)數(shù)據(jù)集的平均輪廓系統(tǒng)越接近1，聚類(lèi)效果越好[8]。依次計(jì)算當(dāng)聚類(lèi)個(gè)數(shù)在【2，α×N】范圍內(nèi)對(duì)應(yīng)的輪廓系數(shù)，其中N為向量集合中的總的向量個(gè)數(shù)，α(0＜α＜1) 為范圍系數(shù)，輪廓系數(shù)最接近1處對(duì)應(yīng)的聚類(lèi)個(gè)數(shù)則為合適的K值。

在各個(gè)“抄襲團(tuán)伙”內(nèi)使用貪婪字符串匹配算法(GST)[7]兩兩比對(duì)程序的特征序列，盡可能找出兩個(gè)特征序列中的匹配。GST算法運(yùn)行結(jié)束后，會(huì)得到最大匹配集合，通過(guò)該集合可以進(jìn)行兩個(gè)程序的相似度計(jì)算。

3 實(shí)驗(yàn)與分析

高校中比較流行的程序代碼抄襲檢測(cè)系統(tǒng)主要有德國(guó)Karlsruhe 大學(xué)的JPlag[9]和美國(guó)Stanford 大學(xué)的Moss系統(tǒng)[10]，其中Moss系統(tǒng)稍遜色于Jpalg系統(tǒng)[11]。目前還沒(méi)有一個(gè)公開(kāi)且真實(shí)的包含大學(xué)生抄襲作業(yè)用例的數(shù)據(jù)集，因此本文從學(xué)生提交的Java編程作業(yè)中挑選具有典型抄襲手段的代碼進(jìn)行聚類(lèi)和相似度檢測(cè)，并與JPlag系統(tǒng)的檢測(cè)結(jié)果進(jìn)行對(duì)比分析。

本文選取“求最大公約數(shù)”的若干程序代碼進(jìn)行實(shí)驗(yàn)，作業(yè)總計(jì)39 份，其中有3 份不同版本的原始程序代碼，分別是A1、A2、A3，其余36 份作業(yè)是在原始程序代碼基礎(chǔ)上使用抄襲手段[12]后得到的抄襲代碼集，抄襲代碼集與對(duì)應(yīng)的抄襲類(lèi)型如表2所示。

表2 程序代碼集與對(duì)應(yīng)的抄襲類(lèi)型

將39個(gè)代碼文件特征向量進(jìn)行聚類(lèi)分析，實(shí)驗(yàn)中指定輪廓范圍系數(shù)α=0.3，對(duì)比不同聚類(lèi)個(gè)數(shù)下的輪廓系數(shù)，發(fā)現(xiàn)當(dāng)聚類(lèi)個(gè)數(shù)為3 時(shí)，輪廓系數(shù)最接近1，聚類(lèi)算法準(zhǔn)確找到了A1、A2、A3共3個(gè)“抄襲團(tuán)伙”。

3.1 代碼相似度計(jì)算結(jié)果對(duì)比分析

本文在A1、A2、A3三個(gè)代碼集中，分別計(jì)算12種抄襲行為相對(duì)于原始程序的相似度，并將計(jì)算結(jié)果的平均值與JPlag系統(tǒng)的計(jì)算結(jié)果的平均值，以及3份原始代碼之間的相似度進(jìn)行對(duì)比，對(duì)比結(jié)果如圖3所示。

圖3 相似度計(jì)算結(jié)果與JPlag系統(tǒng)的對(duì)比

結(jié)果表明，實(shí)驗(yàn)系統(tǒng)對(duì)于存在抄襲行為的代碼對(duì)，能夠得到較高的相似度，對(duì)于不存在抄襲行為的代碼對(duì)，能得到較低的相似度，而且所有存在抄襲行為代碼對(duì)的相似度明顯高于不存在抄襲行為的代碼對(duì)的相似度；對(duì)各種抄襲行為具有魯棒性，尤其是對(duì)于抄襲類(lèi)型12（等價(jià)控制結(jié)構(gòu)替換），實(shí)驗(yàn)系統(tǒng)相似度結(jié)果明顯高于JPlag系統(tǒng)；對(duì)于抄襲類(lèi)型10（增加冗余語(yǔ)句或變量）的計(jì)算結(jié)果不夠理想，因?yàn)槿哂嗾Z(yǔ)句的插入有可能切斷原有的匹配字符串使其低于最小匹配長(zhǎng)度，導(dǎo)致匹配串變少。

3.4 抄襲檢測(cè)結(jié)果對(duì)比分析

實(shí)驗(yàn)代碼總計(jì)39份，JPlag系統(tǒng)檢測(cè)共產(chǎn)生741個(gè)代碼對(duì)，相似度分布范圍較廣，其中大部分代碼對(duì)的相似度低于40%；實(shí)驗(yàn)系統(tǒng)對(duì)39 份代碼進(jìn)行聚類(lèi)，代碼被分成3個(gè)“抄襲團(tuán)伙”，分別在抄襲團(tuán)伙內(nèi)部計(jì)算相似度，共產(chǎn)生234 個(gè)代碼對(duì)，代碼對(duì)數(shù)量相較JPlag系統(tǒng)有明顯減少，并且相似度低于40%的代碼占比為0，可以避免低閾值下出現(xiàn)誤判現(xiàn)象。相似度檢測(cè)結(jié)果分布對(duì)比如圖4所示。

圖4 相似度分布與JPlag系統(tǒng)的對(duì)比

4 結(jié)束語(yǔ)

提出的基于AST的程序代碼抄襲檢測(cè)方法，以文件內(nèi)的函數(shù)集合而不是整個(gè)文件作為檢測(cè)對(duì)象，過(guò)濾掉與功能關(guān)系不大而極易被修改產(chǎn)生噪聲的大部分代碼，對(duì)AST節(jié)點(diǎn)進(jìn)行過(guò)濾、合并、分類(lèi)、轉(zhuǎn)換，對(duì)語(yǔ)義模糊的節(jié)點(diǎn)結(jié)合上下文賦予語(yǔ)義信息，提高了對(duì)等價(jià)結(jié)構(gòu)轉(zhuǎn)換抄襲類(lèi)型的檢測(cè)靈敏度；使用聚類(lèi)分析將原本較大的代碼集劃分為若干小的“抄襲團(tuán)伙”，減小計(jì)算量的同時(shí)，解決低閾值下抄襲檢測(cè)誤判的問(wèn)題。然而，實(shí)驗(yàn)部分所使用的數(shù)據(jù)集較小，還需要使用更大的數(shù)據(jù)集對(duì)文中方法進(jìn)行驗(yàn)證。另外，實(shí)驗(yàn)系統(tǒng)僅實(shí)現(xiàn)了對(duì)Java代碼的抄襲檢測(cè)，后續(xù)考慮擴(kuò)展到多語(yǔ)言的抄襲檢測(cè)。