劉呈龍，賈勝穎，張麗萍，劉東升

（內(nèi)蒙古師范大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，內(nèi)蒙古 呼和浩特010022）

0 引 言

程序設(shè)計(jì)是高等院校計(jì)算機(jī)專業(yè)教學(xué)中不可或缺的實(shí)踐與教學(xué)環(huán)節(jié)。作業(yè)以電子文檔形式提交給教師是程序設(shè)計(jì)類課程的共同特點(diǎn)。學(xué)生完成作業(yè)的過程中從網(wǎng)上下載或拷貝其它同學(xué)的代碼的現(xiàn)象愈演愈烈。因此，抑制抄襲現(xiàn)象、提高程序設(shè)計(jì)類課程的教學(xué)質(zhì)量越來越重要。這就需要準(zhǔn)確、快速的抄襲檢測方法，因此，對(duì)有效的抄襲識(shí)別技術(shù)及其應(yīng)用研究有重要的意義。本文主要研究基于AST的代碼抄襲檢測方法。首先將代碼轉(zhuǎn)換成AST；然后運(yùn)用序列匹配［1］的方法進(jìn)行相似度的計(jì)算；提取相似部分的特征生成空間向量，對(duì)生成的向量聚類分析，找到 “抄襲團(tuán)伙”。

1 相關(guān)的代碼抄襲檢測方法

國外對(duì)程序相似度相關(guān)研究始于20世紀(jì)70年代。1976年，Halstead首先提出了用屬性計(jì)數(shù)AC（attribute counting）的方法檢測程序代碼的抄襲問題。一年后，基于AC的代碼抄襲檢測系統(tǒng)誕生［2］。而隨著程序的結(jié)構(gòu)信息被加入到檢測中，出現(xiàn)了基于程序結(jié)構(gòu)的檢測方法SM（structure metrics），雖然增加了空間和時(shí)間的開銷，但大大提高了檢測的精度。而現(xiàn)在的代碼復(fù)制檢測系統(tǒng)大多采用AC與SM相結(jié)合的檢測方法。如德國Karlsruhe大學(xué)的JPlag［3］和美國Stanford大學(xué)的 Moss系統(tǒng)［4］等。

國內(nèi)方面也取得了一些成果，有人提出了基于編譯優(yōu)化和反匯編的程序相似性檢測方法［5］以及一種Java源代碼和字節(jié)碼都適用的剽竊檢測方法［6］。內(nèi)蒙古師范大學(xué)分別對(duì)源代碼層面和非源碼層面的相似度檢測進(jìn)行了較深入的研究，并取得了一些進(jìn)展［7－10］。但目前國內(nèi)大多數(shù)的研究僅停留在代碼的相似度計(jì)算上，對(duì)相似度計(jì)算的結(jié)果進(jìn)行分析、聚類的研究較少，很少能找出 “抄襲團(tuán)伙”。本文在相似度計(jì)算的基礎(chǔ)上使用聚類［11］的分析方法，對(duì)AST中的特征信息進(jìn)行分析，在找到 “抄襲團(tuán)伙”方面做出一些嘗試。本研究運(yùn)用比源代碼具有更多結(jié)構(gòu)信息的AST為模型，運(yùn)用計(jì)算生物學(xué)中序列匹配算法得出代碼相似度，而后提取特征進(jìn)行聚類分析，從而找到 “抄襲團(tuán)伙”。

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

基于AST的抄襲檢測方法分3個(gè)階段：代碼形式化；相似度計(jì)算；聚類分析。如圖1所示。源程序通過語法分析工具生成AST，存儲(chǔ)AST序列生成序列表，進(jìn)行相似度計(jì)算，提取相似部分特征生成特征向量，運(yùn)用聚類的方法對(duì)特征向量進(jìn)行分析。

圖1 基于AST的代碼抄襲檢測流程

2.1 代碼形式化

本文采用AST作為相似度檢測的模型，主要基于以下考慮：AST是程序的編譯或者解釋過程中的一個(gè)中間數(shù)據(jù)結(jié)構(gòu)，從語法樹中既可以體現(xiàn)出結(jié)構(gòu)信息也可以保留源程序中的屬性特征，為抄襲檢測提供更加準(zhǔn)確、全面的信息。生成AST有多種方法，本文采用ANTLR（another tool for language recognition）對(duì)源代碼解析生成AST。

ANTLR是一個(gè)語法分析工具［12］，使用ANTLR來生成AST主要因?yàn)椋孩貯NTLR為開源的語法分析器，便于進(jìn)行二次開發(fā)，優(yōu)化生成的語法樹。②ANTLR生成的AST中的冗余信息較少，便于閱讀與優(yōu)化。③ANTLR可以使用不同的文法文件生成不同的語法分析器，從而對(duì)不同的語言進(jìn)行分析有很高的靈活性。

使用ANTLR生成AST分為兩步［13］第一步，讀取解析文件，在讀取分析文法文件中的規(guī)則后，ANTLR可以生成相應(yīng)詞法和語法分析器；利用生成的詞法分析器，先將輸入的程序代碼轉(zhuǎn)換成由短語組成的流，再作為語法分析器的輸入從而得出最終的結(jié)果——AST。通過遍歷AST生成AST的序列代碼段。例如：源代碼1.cpp經(jīng)過ANTLR解析后得到的AST如圖2所示。

我們將源程序中的每一行代碼與生成的AST進(jìn)行比對(duì)發(fā)現(xiàn)，AST中包含了源代碼的屬性特征與結(jié)構(gòu)特征，見表1所示。

圖2 1.cpp對(duì)應(yīng)的AST

表1 源程序與AST特征對(duì)照

2.2 相似度計(jì)算

根據(jù)源代碼抽象表示方式和相似度檢測粒度選取層次的不同，所采用的檢測技術(shù)也不同，常見的檢測技術(shù)包括基于文本、基于樹和基于圖的檢測方法。

本文采用先將源代碼轉(zhuǎn)換成AST，再對(duì)AST進(jìn)行遍歷生成代碼序列，接下來采用基于序列匹配的代碼相似度檢測方法進(jìn)性抄襲檢測，同時(shí)兼顧速度和語義兩個(gè)方面的要求，從而獲得準(zhǔn)確率更高、時(shí)間空間效率更好的檢測結(jié)果。本文將比對(duì)粒度固定在函數(shù)級(jí)別，用函數(shù)所對(duì)應(yīng)的AST序列進(jìn)行比對(duì)。這樣做有兩個(gè)個(gè)好處：①將檢測粒度定為以函數(shù)為單元，生成的AST序列不會(huì)過長，降低匹配算法的空間時(shí)間消耗；②將AST的序列進(jìn)行比對(duì)，比源代碼層面含有更多的結(jié)構(gòu)信息，去除了源代碼中如注釋、空白符等對(duì)比對(duì)的干擾，提高了比對(duì)精度。

2.2.1 AST序列的存儲(chǔ)

保存下來的代碼序列包含了AST中的結(jié)構(gòu)信息，還包含如文件名、函數(shù)名、程序行號(hào)等內(nèi)容。本文把生成的代碼序列存入Hashtable中，Hashtable繼承Map接口，實(shí)現(xiàn)一個(gè)key－value映射的哈希表。任何非空 （non－null）的對(duì)象都可作為key或者value。對(duì)生成的AST進(jìn)行優(yōu)化，減少AST的長度，即把結(jié)點(diǎn)token名稱的長度統(tǒng)一為兩個(gè)字母，存入Hashtable中。生成的Hashtable如圖3所示。

圖3 AST序列存儲(chǔ)格式

2.2.2 序列匹配

運(yùn)用SmithWater－man算法進(jìn)行相似度計(jì)算，得到程序相似度值，并進(jìn)行有效性及適用性評(píng)價(jià)。該算法主要用于計(jì)算生物學(xué)領(lǐng)域，在尋找序列最優(yōu)相似匹配方面有較好的效果。該算法首先以兩個(gè)匹配序列為橫縱坐標(biāo)建立矩陣，然后運(yùn)用迭代的方法生成分矩陣，其中包含著所有可能相似的分值，比較各分矩陣的分值，其中最高的為最優(yōu)匹配。

對(duì)于給定的兩條序列S＝s1，s2，s3，…，sn和 T＝t1，t2，t3，…，tm，它們對(duì)應(yīng)的長度分別n和m，根據(jù)動(dòng)態(tài)規(guī)劃的算法，我們需要構(gòu)造一個(gè)大小為 （n＋1）× （m＋1）的矩陣用來存放所有可能的比對(duì)結(jié)果，矩陣可以通過如下的公式計(jì)算得到：

（1）初始條件

（2）遞歸關(guān)系

式中：1≤i≤n，1≤j≤m，Wx——在序列中添加一個(gè)長度為x的空位的罰分，Wy——在序列中添加一個(gè)長度為y的空位的罰分。運(yùn)用動(dòng)態(tài)規(guī)劃的方法回溯尋找高分分矩陣即最佳匹配。分矩陣分?jǐn)?shù)計(jì)算偽代碼如圖4所示。

2.2.3 代碼的相似度計(jì)算

運(yùn)用Smith Water－man算法可以得到代碼X與Y的最大匹配集合，通過該集合可以計(jì)算兩程序的AST序列的相似度，利用該結(jié)果運(yùn)用以下公式度量兩個(gè)對(duì)應(yīng)的程序代碼X，Y的相似度。

圖4 Smith waterman算法分矩陣計(jì)算

式中：X，Y——待比對(duì)序列。SLength （X，Y）——X與Y最大匹配集合的字符串長度。Length（X）——X中字符的個(gè)數(shù)。Length（Y）——Y中字符的個(gè)數(shù)。

2.3 聚類分析

相似度計(jì)算之后，通過保存下來的源程序的行號(hào)在二元序列表中找到相應(yīng)的AST代碼序列生成特征向量用于聚類分析，本文運(yùn)用向量空間模型VSM （vector space model）來進(jìn)行聚類分析。VSM是由Gerard Salton于1969年提出的［14］，廣泛應(yīng)用于信息檢索領(lǐng)域。該模型的主要思想是：將文檔抽象為空間中的一個(gè)點(diǎn)，而空間的維數(shù)及點(diǎn)的坐標(biāo)則由文檔中的特征詞和該詞在文檔中的權(quán)重決定的。VSM模型與空間映射關(guān)系表2所示。

表2 VSM模型與空間的映射關(guān)系

每一篇文檔都可以用其中的一些有代表性的詞或短語來表示，空間向量就是由這些詞及其權(quán)重構(gòu)成的：（W1，j，W2，j，W5，j…Wn，j）。其中，Wi，j為文檔Di中詞條i的權(quán)重。TF表示詞條i在文檔Di中出現(xiàn)的次數(shù)。

權(quán)重計(jì)算

IDF的計(jì)算

式中：N——文檔集合中所有的文檔數(shù)目，ni——整個(gè)文檔集合中出現(xiàn)過詞條i的文檔的總數(shù)。

本文提取AST序列中的特征信息生成VSM，以函數(shù)為例，特征信息包括：FunctionDef函數(shù)聲明、FunctionCall函數(shù)調(diào)用等特征。計(jì)算取得VSM后運(yùn)用k－medoids算法［15］進(jìn)行聚類分析。該算法屬于劃分方法中的一種常用的聚類算法并有較好的抗噪能力。具體算法如圖5所示。

圖5 k－medoids算法流程

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

3.1 抄襲檢測實(shí)驗(yàn)

實(shí)驗(yàn)對(duì)12對(duì)C語言程序進(jìn)行了測試，12對(duì)程序分別對(duì)應(yīng)了12種抄襲手段，包括：完整拷貝；修改注釋；重新排版；標(biāo)識(shí)符重命名；代碼塊重排序；代碼塊內(nèi)語句重排序；常量替換；改變表達(dá)式中的操作符或者操作數(shù)順序；改變數(shù)據(jù)類型；增加冗余的語句或者變量；表達(dá)式拆分；替換控制結(jié)構(gòu)為等價(jià)的控制結(jié)構(gòu)。代碼檢測結(jié)果與Moss系統(tǒng)對(duì)比結(jié)果如圖6所示。

圖6 測試結(jié)果與Moss對(duì)比

從實(shí)驗(yàn)結(jié)果可以看出本文介紹的基于AST的抄襲檢測方法對(duì)不同的抄襲行為有較好的檢測效果，尤其在對(duì)完全拷貝、修改注釋、常量替換、替換控制結(jié)構(gòu)為等價(jià)的控制結(jié)構(gòu)等方面效果顯著。但是在檢測增加冗余的語句或者變量、表達(dá)式拆分等抄襲手段時(shí)仍然有很多的誤差。主要原因是冗余語句與拆分的表達(dá)式使生成的AST的長度與原型程序有較大的變化，影響了決策函數(shù)的分母，產(chǎn)生誤差。由圖7中的YX12.cpp與CX12.cpp的檢測結(jié)果可以看出本方法的精度優(yōu)于Moss系統(tǒng)。而Moss系統(tǒng)在檢測控制結(jié)構(gòu)的替換方面有較強(qiáng)的噪音干擾。

圖7 YX12.cpp與CX12.cpp檢測結(jié)果截圖

3.2 聚類分析

本文對(duì)另外15份C語言程序代碼進(jìn)行聚類分析實(shí)驗(yàn)。其中包括3份原型代碼，抄襲3份原型的代碼各兩份，其余6份分別為與原型有相同抄襲行為的代碼。其中包括的抄襲方式有：程序逐行拷貝；for、while循環(huán)變換；變量名變換。代碼1、4、5、10、11的抄襲方式為逐行拷貝；代碼2、6、7、12、13的抄襲方式為循環(huán)替換；代碼3、8、9、14、15為變量名替換。

相似度計(jì)算結(jié)果如圖8所示。聚類分析實(shí)驗(yàn)結(jié)果表3所示。由表3的聚類分析結(jié)果可以看出基于AST的相似度檢測及之后的聚類結(jié)果基本實(shí)現(xiàn)了對(duì)抄襲特征的分類，從而對(duì)抄襲集群進(jìn)行匯總。

圖8 部分程序相似度結(jié)果

4 結(jié)束語

運(yùn)用了AST作為代碼抄襲檢測的模型，并結(jié)合生物學(xué)中序列匹配的方法進(jìn)行相似度的計(jì)算。根據(jù)計(jì)算結(jié)果提取AST的特征值進(jìn)行聚類分析找到 “抄襲團(tuán)伙”。下一步我們的工作：①對(duì)提取的AST特征進(jìn)行進(jìn)一步分析同時(shí)對(duì)聚類算法進(jìn)行優(yōu)化，減少噪音的出現(xiàn)。②該實(shí)驗(yàn)系統(tǒng)實(shí)現(xiàn)了C代碼的抄襲檢測，后續(xù)只要制定和完善多語言的文法文件，實(shí)現(xiàn)對(duì)多語言的檢測，從而提高實(shí)驗(yàn)系統(tǒng)的通用性和可擴(kuò)展性。

表3 聚類結(jié)果

［1］WU Demin，CHENG Jun.Research on algorithm of pair wise alignment ［J］.Computer Engineering and Applications，2008，44 （36）：48－50 （in Chinese）.［吳德敏，陳俊.雙序列比對(duì)的算法研究 ［J］.計(jì)算機(jī)工程與應(yīng)用，2008，44 （36）：48－50.］

［2］Aiken A.Moss：A system for detecting software plagiarism［EB／OL］. ［2009－12－21］.http：／／theory.stanford.edu／～aiken／moss／.

［3］Emeric K，Moritz K.JPlag：A system that finds similarities among multiple sets of source code files［EB／OL］.［2009－02－01］http：／／www.ipd.Uni－karlsruhe.de／jplag／.

［4］Aiken A.Moss：A system for detecting software plagiarism［EB／OL］. ［2009－02－01］.http：／／theory.stanford.edu／～aiken／moss／.

［5］ZHAO Changhai，YAN Haihua，JIN Maozhong.Approach based on compiling optimization and disassembling to detect program similarity ［J］.Beijing University of Aeronautics and Astronautics，2008，34 （6）：711－715 （in Chinese）. ［趙長海，晏海華，金茂忠.基于編譯優(yōu)化和反匯編的程序相似性檢測方法 ［J］.北京航空航天大學(xué)學(xué)報(bào)，2008，34 （6）：711－715.］

［6］LI Hu，LIU Chao，LIU Nan，et al.Method and its system of Java source and byte code plagiarism detection ［J］.Beijing University of Aeronautics and Astronautics，2010，36 （4）：424－428（in Chinese）.［李虎，劉超，劉楠，等.Java源代碼字節(jié)碼剽竊檢測方法及支持系統(tǒng) ［J］.北京航空航天大學(xué)學(xué)報(bào)，2010，36 （4）：424－428.］

［7］LIU Dongsheng，ZHONG Mei，SHI Shumin，et al.An AST plagiarism detection model for procedural programming languages ［C］.The World Congress in Computer Science Computer Engineering ＆ Applied Computing，2010：187－191.

［8］LI Yanchen，LIU Dongsheng.Suffix tree based plagiarism detection method for C code ［C］.International Conference on Future Computer Control and Communication，2010：210－213.

［9］ZHONG Mei，ZHANG Liping，LIU Dongsheng.Plagiarism detection algorithm based on XML for C code ［J］.Computer Engineering and Applications，2011，47 （8）：215－218 （in Chinese）.［鐘美，張麗萍，劉東升.一種基于XML的C代碼抄襲檢測算法 ［J］.計(jì)算機(jī)工程與應(yīng)用，2011，47 （8）：215－218.］

［10］ZHANG Liping，LIU Dongsheng，LI Yanchen.Research on code copy detecting strategy and it’s evaluation mechanism based on syntax tree ［J］.Journal of Inner Mongolia University，2010，41（5）：594－600 （in Chinese）.［張麗萍，劉東升，李彥臣.基于語法樹的程序代碼復(fù)制檢測方法及其評(píng)價(jià)機(jī)制的研究［J］.內(nèi)蒙古大學(xué)學(xué)報(bào)，2010，41 （5）：594－600.］

［11］XIONG Yun.The research on biological sequential pattern mining and clustering ［D］.Shanghai：Fudan University，2007（in Chinese）. ［熊赟.生物序列模式挖掘與聚類研究［D］.上海：復(fù)旦大學(xué)，2007.］

［12］XIAO Li，XIAO Jingzhong.Structure of field language base on ANTLR ［J］.Computer Science，2011，38 （7A）：91－92（in Chinese）.［肖麗，校景中.基于ANTLR的領(lǐng)域語言構(gòu)造 ［J］.計(jì)算機(jī)科學(xué)，2011，38 （7A）：91－92.］

［13］XIN Tianqing.Design and implementation of code clone analysis system based on sequence matching［D］.Dalian：Dalian Polytechnic University，2008 （in Chinese）. ［辛天卿.基于序列匹配的代碼克隆分析系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn) ［D］.大連：大連理工大學(xué)，2008.］

［14］YAO Qingyun.Research of VSM－based Chinese text clustering algorithms ［D］.Shanghai：Shanghai Jiaotong University，2008（in Chinese）.［姚清耘.基于向量空間模型的中文文本聚類方法的研究 ［D］.上海：上海交通大學(xué)，2008.］

［15］XIA Ningxia，SU Yidan，QIN Xi.Efficient k－medoids clustering algorithm ［J］.Application Research of Computers，2010，27 （12）：4517－4519 （in Chinese）.［夏寧霞，蘇一丹，覃希.一種高效的K－medoids聚類算法 ［J］.計(jì)算機(jī)應(yīng)用研究，2010，27 （12）：4517－4519.］