基于AST 的程序代碼相似性度量研究

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

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

0 引言

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

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

1 相關(guān)定義

1.1 相似度定義

Yamamoto等［3］給出了兩個軟件系統(tǒng)的相似度的定義。對于兩個軟件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表示所有的匹配對(Pi，Xj)，其中Rs?P×X，則P和X的相似性定義為

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

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

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

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

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

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

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

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

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

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

2.1 代碼預(yù)處理

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

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

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

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

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

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

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

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

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

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

2.2 生成抽象語法樹

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

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

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

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

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

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

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

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

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

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

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

對待問題“求解2 000以內(nèi)的質(zhì)數(shù)”，其源程序Test01.java和抄襲程序Test04.java(重新排版程序順序格式)的抽象語法樹遍歷后存儲信息提取對比分析結(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)換成字符串序列后可進行相似性計算。

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

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

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

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

2.3 相似性度量

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

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

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

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

2.4 閾值的選擇

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

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

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

3 實驗分析

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

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

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

3.2 實驗結(jié)果與分析

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

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

通過相似度檢測結(jié)果得到的實驗系統(tǒng)與Moss檢測系統(tǒng)的結(jié)果對比分析圖如圖4所示。

圖4 相似度對比分析圖Fig.4 Similarity comparison analysis chart

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

4 結(jié)語

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

今后將進一步研究以彌補不足之處，如:通過格式化源碼進一步去除冗余信息;擴大測試集，增強實驗說服力;完善成為可進行多種語言代碼的抄襲檢測系統(tǒng)，從而提高實驗系統(tǒng)的擴展性和適應(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］熊浩，晏海華，郭濤，等.代碼相似性檢測技術(shù):研究綜述［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)化匹配同源性檢測技術(shù)研究［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)化和反匯編的程序相似性檢測方法［J］.北京航空航天大學(xué)學(xué)報，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è)剽竊檢測中的應(yīng)用［J］.安徽科技學(xué)院學(xué)報，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.