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

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

0 引 言

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

1 相關的代碼抄襲檢測方法

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

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

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

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

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

2.1 代碼形式化

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

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

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

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

圖2 1.cpp對應的AST

表1 源程序與AST特征對照

2.2 相似度計算

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

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

2.2.1 AST序列的存儲

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

圖3 AST序列存儲格式

2.2.2 序列匹配

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

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

（1）初始條件

（2）遞歸關系

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

2.2.3 代碼的相似度計算

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

圖4 Smith waterman算法分矩陣計算

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

2.3 聚類分析

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

表2 VSM模型與空間的映射關系

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

權重計算

IDF的計算

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

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

圖5 k－medoids算法流程

3 實驗與分析

3.1 抄襲檢測實驗

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

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

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

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

3.2 聚類分析

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

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

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

4 結(jié)束語

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

表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）.［吳德敏，陳俊.雙序列比對的算法研究 ［J］.計算機工程與應用，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］.北京航空航天大學學報，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］.北京航空航天大學學報，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］.計算機工程與應用，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）.［張麗萍，劉東升，李彥臣.基于語法樹的程序代碼復制檢測方法及其評價機制的研究［J］.內(nèi)蒙古大學學報，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］.上海：復旦大學，2007.］

［12］XIAO Li，XIAO Jingzhong.Structure of field language base on ANTLR ［J］.Computer Science，2011，38 （7A）：91－92（in Chinese）.［肖麗，校景中.基于ANTLR的領域語言構(gòu)造 ［J］.計算機科學，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)設計與實現(xiàn) ［D］.大連：大連理工大學，2008.］

［14］YAO Qingyun.Research of VSM－based Chinese text clustering algorithms ［D］.Shanghai：Shanghai Jiaotong University，2008（in Chinese）.［姚清耘.基于向量空間模型的中文文本聚類方法的研究 ［D］.上海：上海交通大學，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］.計算機應用研究，2010，27 （12）：4517－4519.］