朱 波，鄭 虹，孫琳琳，楊友星

(長春工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，長春130012)

0 引言

隨著計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)的飛速發(fā)展，信息資源在方便快捷獲取的同時(shí)，資源的抄襲現(xiàn)象愈加普遍。其中，在計(jì)算機(jī)程序設(shè)計(jì)類課程中，學(xué)生間的抄襲情況極為嚴(yán)重。澳大利亞蒙納什(Monash)大學(xué)對(duì)其學(xué)生中的代碼抄襲現(xiàn)象進(jìn)行調(diào)查統(tǒng)計(jì)顯示:高達(dá)85.4%的學(xué)生承認(rèn)抄襲過他人的作業(yè)［1，2］。另外，在軟件商業(yè)領(lǐng)域，不同軟件企業(yè)因?yàn)檐浖a(chǎn)品相似所引發(fā)的產(chǎn)權(quán)糾紛也越來越多。為扼制不良抄襲學(xué)風(fēng)，加強(qiáng)對(duì)知識(shí)產(chǎn)權(quán)的保護(hù)力度，對(duì)程序代碼相似性度量的研究顯得日趨重要。

筆者在研究國內(nèi)外程序代碼抄襲檢測(cè)的基礎(chǔ)上，針對(duì)Java程序中常見的抄襲手段，提出一種基于AST的檢測(cè)Java程序代碼抄襲的方法。首先對(duì)程序代碼進(jìn)行預(yù)處理，減少冗余信息;然后對(duì)預(yù)處理后的代碼進(jìn)行遍歷生成AST;最后通過采用自適應(yīng)閾值選取方式，對(duì)AST進(jìn)行相似度計(jì)算，判定是否抄襲，最終生成相似度檢測(cè)報(bào)告。

1 相關(guān)定義

1.1 相似度定義

Yamamoto等［3］給出了兩個(gè)軟件系統(tǒng)的相似度的定義。對(duì)于兩個(gè)軟件P和X，軟件P是由元素P1，P2，…，Pm組成，P 的集合構(gòu)成表示為{P1，P2，…，Pm}。同樣，軟件 X 由元素 X1，X2，…，Xn組成，其元素的集合表示為{X1，X2，…，Xn}。其中P，X中的元素可以表示軟件P和X中的文件或代碼行。

假設(shè)能求出Pi與Xj(1≤i≤m且1≤j≤n)間的匹配，用集合Rs表示所有的匹配對(duì)(Pi，Xj)，其中Rs?P×X，則P和X的相似性定義為

根據(jù)式(1)可看出，相似性S為一個(gè)比值，由Rs中元素的個(gè)數(shù)比上P和X中元素的個(gè)數(shù)和所得。如果Rs較小，相應(yīng)的S也較小。當(dāng)Rs=?時(shí)，S=0;當(dāng)P和X完全相等時(shí)，S=1，則說明軟件P和X存在抄襲現(xiàn)象。

目前對(duì)于相似度沒有統(tǒng)一的定義，而程序代碼的相似度與上述的軟件系統(tǒng)的相似度相同，所以可將相似度定義為定量比較兩個(gè)程序源代碼之間的相關(guān)性，其結(jié)果一般用某個(gè)數(shù)值表示。

1.2 程序代碼相似性度量方法

現(xiàn)在常用的程序源代碼相似性度量方法主要有4種［4］:空間向量法、Token序列法、抽象語法樹法以及程序依賴圖方法。

1)空間向量法?？臻g向量法是將存在于程序中的操作符、操作數(shù)等作為程序的特征，把程序及其結(jié)構(gòu)以特征向量的形式表征，再通過度量任意2個(gè)向量之間的距離衡量程序之間的相似程度。

2)Token序列法［5］。Token序列法是將輸入的源代碼經(jīng)過詞匯分析器分析，在一定規(guī)則的約束下將源代碼轉(zhuǎn)換成Token序列，然后利用匹配算法(LCS:Longest Common Subsequence)度量程序間的相似程度。這樣做可以檢測(cè)出具有不同句法但卻有相似功能的代碼段，往往會(huì)隱藏程序的組織結(jié)構(gòu)。

3)抽象語法樹法。抽象語法樹(AST:Abstract Syntax Tree)是程序編譯階段的一種中間表示形式，可以比較直觀地表示出程序代碼的語法結(jié)構(gòu)，并含有程序代碼結(jié)構(gòu)顯示所需的全部靜態(tài)信息。其通過比較子樹與其他子樹之間的相似程度對(duì)程序的相似性進(jìn)行度量。該方法體現(xiàn)了程序的語義結(jié)構(gòu)，具有較高的相似性度量效果。

4)程序依賴圖法。程序依賴圖(PDG:Program Dependence Graph)可表示程序內(nèi)部數(shù)據(jù)以及控制依賴關(guān)系，能在語義級(jí)別上對(duì)程序代碼進(jìn)行分析，但該方法在程序依賴圖構(gòu)造和比較過程中時(shí)間開銷較大。

2 基于抽象語法樹的相似性度量

基于抽象語法樹的相似性度量方法分為代碼預(yù)處理、構(gòu)造抽象語法樹、相似度計(jì)算和閾值分析生成檢測(cè)報(bào)告。如圖1所示，先將代碼進(jìn)行預(yù)處理，消除冗余信息，以便提高效率;再進(jìn)行詞法語法分析生成抽象語法樹;最后通過抽象語法樹遍歷生成的屬性、方法等語義標(biāo)記序列進(jìn)行相似度計(jì)算，與自適應(yīng)閾值對(duì)比分析，生成最終的檢測(cè)報(bào)告。

2.1 代碼預(yù)處理

圖1 相似度度量流程圖Fig.1 Similarity measure flow chart

為加快系統(tǒng)的運(yùn)行速度，減少生成抽象語法樹時(shí)的冗余信息，提交源程序后，必須過濾一些存在于源代碼之中的對(duì)相似度檢測(cè)沒有影響的信息，如空格、注釋等。筆者以Java程序?yàn)槔?，說明對(duì)源程序代碼的預(yù)處理，主要有以下幾方面:

1)去掉程序中所有在符號(hào)“//”之后、“/＊ ＊/”和“/＊＊ ＊/”之間的程序注釋內(nèi)容;

2)將程序開始部分所有以“import”開頭的引包代碼刪除;

3)過濾掉程序中存在的空行;

4)刪除每行程序代碼中的第1個(gè)非空字符之前的所有空格和“Tab”鍵;

5)保留運(yùn)算符等描述程序代碼的邏輯功能的代碼部分;

6)在保證語義的情況下，對(duì)能等價(jià)替換的語句進(jìn)行統(tǒng)一化處理，如將i=i+1，i++，++j統(tǒng)一替換為一種形式;

7)對(duì)Java程序中的主函數(shù)框架部分統(tǒng)一使用“main{}”進(jìn)行替換;

8)在不改變程序語義的情況下，將輸出語句“System.out.print();”和“System.out.print－ln();”等價(jià)變換為“out(輸出內(nèi)容)”。

2.2 生成抽象語法樹

將完成代碼預(yù)處理的程序轉(zhuǎn)換成與之對(duì)應(yīng)的抽象語法樹，從而在語義的基礎(chǔ)上為相似性度量提供一個(gè)高效規(guī)范的數(shù)學(xué)模型。創(chuàng)建抽象語法樹的規(guī)則設(shè)定為從葉子節(jié)點(diǎn)開始創(chuàng)建，先創(chuàng)建父節(jié)點(diǎn)后創(chuàng)建子節(jié)點(diǎn)，再將它們關(guān)聯(lián)起來。創(chuàng)建AST算法描述如下。

1)解析空的代碼創(chuàng)建一個(gè)空的AST:

①定義語言規(guī)范;②設(shè)置字符的編碼方式;③設(shè)置編譯單元節(jié)點(diǎn);④得到空的AST。

2)創(chuàng)建類，把類節(jié)點(diǎn)作為編譯單元的子節(jié)點(diǎn):

①創(chuàng)建類節(jié)點(diǎn);②添加類名;③添加類可見性;④將類節(jié)點(diǎn)連接為編譯單元的子節(jié)點(diǎn)。

3)創(chuàng)建函數(shù)方法，并作為類節(jié)點(diǎn)classDec的子節(jié)點(diǎn):

①添加方法名;②添加方法可見性;③添加方法體;④將方法節(jié)點(diǎn)連接為類節(jié)點(diǎn)的子節(jié)點(diǎn)。

4)創(chuàng)建方法體中的方法語句，并以此作為類節(jié)點(diǎn)methodDec的子節(jié)點(diǎn):

①對(duì)方法體中的語句進(jìn)行分析，設(shè)置節(jié)點(diǎn);②根據(jù)循環(huán)語句、條件語句等分類設(shè)置節(jié)點(diǎn)。

在生成抽象語法樹后，可以從待檢測(cè)程序的抽象語法樹中將源程序的屬性、方法等語義信息遍歷取出，以便為后續(xù)的相似性度量提供語義支持。

將生成的抽象語法樹的屬性、方法取出，放入Block數(shù)組中。獲取源程序中的屬性集合，并將其放入attribute_array［］數(shù)組中;獲取源程序中的方法集合，將其放入method_array［］數(shù)組中。

對(duì)待問題“求解2 000以內(nèi)的質(zhì)數(shù)”，其源程序Test01.java和抄襲程序Test04.java(重新排版程序順序格式)的抽象語法樹遍歷后存儲(chǔ)信息提取對(duì)比分析結(jié)果如圖2和圖3所示。

圖2 Test01的AST信息遍歷Fig.2 Test01 AST information traversal

圖3 Test04的AST信息遍歷Fig.3 Test04 AST information traversal

由圖2和圖3可以看到，源程序和抄襲程序生成抽象語法樹后其程序的結(jié)構(gòu)及語義信息。將其轉(zhuǎn)換成字符串序列后可進(jìn)行相似性計(jì)算。

為清晰地進(jìn)行數(shù)據(jù)存儲(chǔ)和更新，可將源程序的語義信息存儲(chǔ)到表中，方便后續(xù)使用。具體實(shí)現(xiàn)步驟如下。

1)將數(shù)據(jù)存儲(chǔ)表(DST:Data Store Table)定義為一個(gè)三元關(guān)系D=(Class，F(xiàn)ield，Method)，其中Class表示類名、Field表示屬性名、Method表示使用該變量的方法名。

2)將函數(shù)信息表(MIT:Method Information Table)定義為一個(gè)四元關(guān)系M=(Class，Method，Method_call，Method_para)，其中Method表示方法名、Method_call表示被調(diào)用的方法、Method_para表示函數(shù)的參數(shù)信息。

3)將類名和方法名作為主鍵，在獲取程序語義信息時(shí)向表中填入數(shù)據(jù)。

2.3 相似性度量

將需要檢測(cè)的源程序的語義信息存儲(chǔ)后即可將屬性、方法等結(jié)構(gòu)語義信息遍歷取出，利用JDT(Java Development Tooling)平臺(tái)并調(diào)用ASTParser類形成序列代碼，再通過貪婪字符串匹配算法(GST:Greedy String Tiling)［6，7］計(jì)算提交的源程序之間的相似性度量問題。該算法的偽代碼如下。

GST算法可以盡可能找出兩個(gè)子串中的匹配，對(duì)屬性方法形成的子串中可能存在的最大匹配進(jìn)行檢測(cè)，進(jìn)而為相似性度量提供支持。

GST算法運(yùn)行結(jié)束后，會(huì)得到最大匹配集合tiles，通過該集合可以進(jìn)行源程序與抄襲程序的相似度計(jì)算。將所有匹配序列的長度和記為SSum，源程序P和抄襲程序T可通過公式

進(jìn)行程序間的相似性度量檢測(cè)。其中Pl和Tl分別為源程序和抄襲程序的AST序列代碼長度。

2.4 閾值的選擇

筆者在進(jìn)行相似性度量時(shí)，先根據(jù)多種抄襲手段修改源程序，得到若干個(gè)修改后的抄襲程序。再將源程序與抄襲程序進(jìn)行相似性度量，每次相似性度量結(jié)果用相似度Ssim表示。而在程序代碼抄襲檢測(cè)過程中，僅依靠單次檢測(cè)相似度的高低進(jìn)行抄襲判定是不恰當(dāng)?shù)模挥挟?dāng)相似度的值超過某個(gè)設(shè)定的閾值時(shí)，才能判定為抄襲。

筆者采用自適應(yīng)閾值法，根據(jù)源程序、檢測(cè)次數(shù)等因素的不同自動(dòng)調(diào)節(jié)每次檢測(cè)的閾值，避免了經(jīng)驗(yàn)化設(shè)置閾值的弊端。設(shè)進(jìn)行n次相似度檢測(cè)的閾值為Sthreshold，其計(jì)算如下

其中Smax為n次檢測(cè)中得到的相似度最大值，Smin為n次檢測(cè)中得到的相似度最小值。

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

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

對(duì)問題“求解2 000以內(nèi)的質(zhì)數(shù)”，選取一個(gè)含有13個(gè)Java語言程序代碼的測(cè)試集，其中Test01為Java源程序。將Test01與其他12個(gè)Java程序(Test02…Tset13)構(gòu)成12對(duì)測(cè)試對(duì)進(jìn)行相似性度量檢測(cè)。

其中12對(duì)測(cè)試程序分別對(duì)應(yīng)12種抄襲手段［8］:1)程序完整拷貝;2)修改程序注釋;3)重新排版程序格式;4)重命名標(biāo)識(shí)符;5)重排序代碼塊;6)代碼塊內(nèi)語句重排序;7)常量替換;8)修改表達(dá)式中的操作符或操作數(shù)順序;9)改變數(shù)據(jù)類型;10)增加冗余的語句或變量;11)表達(dá)式拆分;12)替換控制結(jié)構(gòu)為等價(jià)的控制結(jié)構(gòu)。

3.2 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)對(duì)比系統(tǒng)使用Moss系統(tǒng)［9］，該系統(tǒng)采用串匹配算法(Winnowing算法［10，11］)通過將處理字符串放入哈希表再從表中選取一個(gè)子集進(jìn)行比較，以此進(jìn)行相似性度量。對(duì)12對(duì)程序進(jìn)行相似性度量得到的相似度結(jié)果及相同度量程序下Moss系統(tǒng)的檢測(cè)結(jié)果如表1所示。

表1 相似度檢測(cè)結(jié)果Tab.1 Similarity detection results

通過相似度檢測(cè)結(jié)果得到的實(shí)驗(yàn)系統(tǒng)與Moss檢測(cè)系統(tǒng)的結(jié)果對(duì)比分析圖如圖4所示。

圖4 相似度對(duì)比分析圖Fig.4 Similarity comparison analysis chart

根據(jù)式(3)計(jì)算本次測(cè)試集的閾值Sthreshold=0.75，若相似度Ssim大于Sthreshold，則判定為抄襲。通過實(shí)驗(yàn)結(jié)果對(duì)比分析可以看出，筆者設(shè)計(jì)的基于AST的相似性度量方法對(duì)不同的抄襲手段有較好的檢測(cè)效果。特別是對(duì)程序完整拷貝、標(biāo)識(shí)符的重命名、代碼塊語句順序的重排序以及表達(dá)式的拆分度量檢測(cè)方面有較為顯著的效果。但對(duì)度量增加冗余代碼等抄襲手段仍然有一定的誤差。主要是因?yàn)樵黾尤哂啻a容易使生成的AST序列長度與源程序有較大的變化，產(chǎn)生誤差。

4 結(jié)語

筆者提出一種利用AST檢測(cè)Java程序代碼的相似性度量方法，在語義的層次上達(dá)到了度量檢測(cè)的目的。實(shí)驗(yàn)分析和測(cè)試表明，該方法能較好地檢測(cè)多種抄襲手段，相比Moss抄襲檢測(cè)系統(tǒng)也具有較高的檢測(cè)效率，達(dá)到了預(yù)期的效果。但在增加冗余代碼等方面，用該方法進(jìn)行度量時(shí)還有一些不足之處，相似度有一定程度的降低。

今后將進(jìn)一步研究以彌補(bǔ)不足之處，如:通過格式化源碼進(jìn)一步去除冗余信息;擴(kuò)大測(cè)試集，增強(qiáng)實(shí)驗(yàn)說服力;完善成為可進(jìn)行多種語言代碼的抄襲檢測(cè)系統(tǒng)，從而提高實(shí)驗(yàn)系統(tǒng)的擴(kuò)展性和適應(yīng)性。

［1］SHEARD J，DICK M，MARKHAM S，et al.Cheating and Plagiarism:Perceptions and Practices of First Year IT Students［C］∥Proccedings of the 7th Annual SIGCSE Conference on Innovation and Technology in ComputerScience Education.New York:ACM Press，2002:183－187.

［2］GEORGINA C，MIKE J.Source－Code Plagiarism:A UK Academic Perspective ［R］.Warks:Department of Computer Science，University of Warwick，2006.

［3］YAMAMOTO T，MATSUSHITA M.Measuring Similarity of Large Software Systems Based on Source Code Correspondence［D］.Osaka:Division of Software Science，Graduate School of Engineering Science，Osaka University，2002:4－5.

［4］熊浩，晏海華，郭濤，等.代碼相似性檢測(cè)技術(shù):研究綜述［J］.計(jì)算機(jī)科學(xué)與技術(shù)，2010，37(8):9－14.XIONG Hao，YAN Haihua，GUO Tao，et al.Code Similarity Detection:A Survey ［J］.Computer Science，2010，37(8):9－14.

［5］劉云龍.基于Token的結(jié)構(gòu)化匹配同源性檢測(cè)技術(shù)研究［J］.計(jì)算機(jī)應(yīng)用研究，2014，31(6):1841－1845.LIU Yunlong.Token－Based Structured Code Matching Homology Detection Technology ［J］.Application Research of Computers，2014，31(6):1841－1845.

［6］MICHAEL J WISE.String Similarity via Greedy String Tiling and Running Karp－Rabin Matching［D］.Sydney:Department of Computer Science，University of Sydney，1993.

［7］MICHAEL J WISE.Neweyes:A System for Comparing Biological Sequences Using the Running Karp－Rabin Greedy String Tiling Algorithm［C］∥Third International Conference on Intelligent Systems for Molecular Biology.Cambridge，England:［s.n.］，2006:393－401.

［8］趙長海，晏海華，金茂忠.基于編譯優(yōu)化和反匯編的程序相似性檢測(cè)方法［J］.北京航空航天大學(xué)學(xué)報(bào)，2008，34(6):711－715.ZHAO Changhai，YAN Haihua，JIN Maozhong.An Approach Based on Compiling Optimization and Disassembling to Detect Program Similarity［J］.Joumal of Beijing University of Aeronautics and Astronautics，2008，34(6):711－715.

［9］AIKEN A MOSS:A System for Detecting Software Plagiarism ［EB/OL］.(2009－02－01). ［2012－10－08］.http:∥theory.stanford.edu/～aiken/moss/.

［10］SAUL SCHLEIMER，DANIEL S WILKERSON，ALEX AIKEN.Winnowing:Local Algorithms for Documemt Fingerprinting［C］∥ACM SIGMOD 2003.San Diego:ACM Press，2003:204－212.

［11］李香云，葛華.Winnowing算法在作業(yè)剽竊檢測(cè)中的應(yīng)用［J］.安徽科技學(xué)院學(xué)報(bào)，2013，27(4):42－45.LI Xiangyun，GE Hua.Application of the Winnowing Algorithm in Assignment Plagiarism Detection ［J］.Journal of Anhui Science and Technology University，2013，27(4):42－45.