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

朱良梅，洪曉彬

（廣州工商學院 工學院，廣東 廣州 510850)

0 引言

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

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

1 相關工作

早期的代碼相似度檢測技術的研究主要基于屬性計數的方法，其基本原理是從源代碼中抽取各種屬性度量元作為相似度評判的依據。該方法與所用的程序設計語言無關，實現較為簡單，但是不能分析部分程序段的抄襲，而且增加向量維數并不能改善檢測效果。

后期的研究主要考慮的是代碼的結構信息，目前基于結構度量的相似度檢測方法被主要包括：基于文本、基于詞法、基于語法、基于語義的檢測方法。基于文本的檢測方法將源代碼看作字符序列，比較代碼字符序列相似度并且返回字符串匹配結果集。這類方法易于實現，而且與語言無關，但是不能很好地檢測出在句法和語義層面上的代碼修改。基于詞法的檢測方法將代碼轉換成token（符號、詞匯）。將token 序列視為抽象的代碼表示。相比于基于文本的代碼表征方法來說，這種方法能夠匹配到代碼的特有信息，但從本質上沒有考慮代碼中所包含的結構信息，對代碼語句修改比較敏感。基于語法的檢測方法考慮源代碼語法規則，將源代碼轉換。

為其對應的抽象語法樹。基于樹的方法可以避免由于格式和句法問題引起的問題，能夠考慮到源代碼的結構特性，其缺點是不能識別出標識符和文本值的不同，并且計算開銷大。基于語義的方法不僅希望獲得代碼之中的結構信息，還試圖獲得代碼中的語義信息，復雜度非常高。除此之外，還有學者提出了新的檢測方法,比如，基于深度神經網絡的Oreo[4]、基于遞歸自編碼器和程序向量樹的檢測方法[5-6]等。

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

2.1 生成程序AST

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

圖1 Java示例代碼和抽象語法樹

2.2 構造特征序列

基于樹進行子樹匹配，計算開銷較大，本文對AST進行深度遍歷，將節點序列轉換為字符串特征序列。由于AST 的節點序列長度相比原代碼長度有明顯增長，本文在遍歷過程中通過節點過濾，有效縮短序列長度；此外，通過對等價控制結構進行轉換、對語義模糊節點賦予語義信息、運算符分類等，達到提取AST的結構和語義特征的目的。

2.2.1 節點過濾

1) 過濾函數外節點

由于一個類所實現的功能主要是由其行為即函數所決定的，其他節點與類功能沒有直接聯系，并且這部分節點極易被修改，以達到躲避抄襲檢測的目的。因此，本文在遍歷AST 節點序列時，忽略除函數以外的其他節點，只對文件內的若干函數及其內部節點進行遍歷，從而自動排除一系列簡單的代碼修改所帶來的噪聲影響。

2) 過濾無具體語義的節點

通過對AST包含的各種節點類型進行比較分析，發現其中有一些節點并不包含具體的語義信息，如圖2 中的節點ExpressionStatement、QualifiedName，這些節點對于代碼相似度檢測意義不大，本文予以過濾。

圖2 合并try-catch-finally語句

3) 過濾輸出日志相關的節點

對于常見的通過增加輸出日志的代碼以改變原程序結構的抄襲行為，獲取METHOD_INVOCATION類型節點的被調用的函數名，過濾掉與輸出日志相關的函數調用，如println、print、debug、info、error、log等。

2.2.2 等價控制結構轉換

1) 選擇結構

對if-else、switch-case 和條件判斷語句三種選擇結構進行等價處理，轉換為SELECT_CONDITION 和SELECT_BODY兩類節點。

2) 循環結構

對while、do-while 和for 三種循環結構進行等價處理，轉換為LOOP_CONDITION和LOOP_BODY兩類節點。

2.2.3 賦予語義信息

有些節點包含的語義信息模糊，需要結合上下文為這些節點進一步賦予語義信息。如將Block類型的節點分為：METHOD_BODY、LOOP_BODY、SELECT_BODY。

2.2.4 運算符分類

對前綴、中綴、后綴表達式按照運算類型分為NUM_EXPRESSION、RELATION_EXPRESSION、LOGIC_EXPRESSION、BIT_EXPRESSION和ASSIGN_EXPRESSION，需要注意a++、++a、a=a+1，這三類語句雖然寫法不同，但是實現的功能都是自增1，統一記為ASSIGN_EXPRESSION。

2.2.5 聲明語句拆分

變量聲明語句轉換為節點VAR_DEF，將合并的多個變量的聲明語句拆分成多個單獨的變量聲明；對帶有初始化值的變量聲明語句拆分為變量聲明VAR_DEF和賦值ASSIGN_EXPRESSION。

2.2.6 try-catch-finally語句合并

對try-catch-finally 語句進行合并，如圖2 所示，只關注與函數功能相關的代碼段code_block1 和code_block3，忽略與對異常的處理相關的代碼段code_block2。

經過對節點的過濾、合并、分類、轉換后共匯總得到18種節點類型，同時為了進一步縮短節點序列的長度，分別使用一個唯一的字母代替原節點類型，每個程序文件由這18個字母的不同組合表示，最終形成程序的特征序列。節點類型與對應字母關系如表1所示。

表1 抽象語法樹節點類型和對應的字母

2.3 聚類分析和抄襲檢測

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

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

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

3 實驗與分析

高校中比較流行的程序代碼抄襲檢測系統主要有德國Karlsruhe 大學的JPlag[9]和美國Stanford 大學的Moss系統[10]，其中Moss系統稍遜色于Jpalg系統[11]。目前還沒有一個公開且真實的包含大學生抄襲作業用例的數據集，因此本文從學生提交的Java編程作業中挑選具有典型抄襲手段的代碼進行聚類和相似度檢測，并與JPlag系統的檢測結果進行對比分析。

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

表2 程序代碼集與對應的抄襲類型

將39個代碼文件特征向量進行聚類分析，實驗中指定輪廓范圍系數α=0.3，對比不同聚類個數下的輪廓系數，發現當聚類個數為3 時，輪廓系數最接近1，聚類算法準確找到了A1、A2、A3共3個“抄襲團伙”。

3.1 代碼相似度計算結果對比分析

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

圖3 相似度計算結果與JPlag系統的對比

結果表明，實驗系統對于存在抄襲行為的代碼對，能夠得到較高的相似度，對于不存在抄襲行為的代碼對，能得到較低的相似度，而且所有存在抄襲行為代碼對的相似度明顯高于不存在抄襲行為的代碼對的相似度；對各種抄襲行為具有魯棒性，尤其是對于抄襲類型12（等價控制結構替換），實驗系統相似度結果明顯高于JPlag系統；對于抄襲類型10（增加冗余語句或變量）的計算結果不夠理想，因為冗余語句的插入有可能切斷原有的匹配字符串使其低于最小匹配長度，導致匹配串變少。

3.4 抄襲檢測結果對比分析

實驗代碼總計39份，JPlag系統檢測共產生741個代碼對，相似度分布范圍較廣，其中大部分代碼對的相似度低于40%；實驗系統對39 份代碼進行聚類，代碼被分成3個“抄襲團伙”，分別在抄襲團伙內部計算相似度，共產生234 個代碼對，代碼對數量相較JPlag系統有明顯減少，并且相似度低于40%的代碼占比為0，可以避免低閾值下出現誤判現象。相似度檢測結果分布對比如圖4所示。

圖4 相似度分布與JPlag系統的對比

4 結束語

提出的基于AST的程序代碼抄襲檢測方法，以文件內的函數集合而不是整個文件作為檢測對象，過濾掉與功能關系不大而極易被修改產生噪聲的大部分代碼，對AST節點進行過濾、合并、分類、轉換，對語義模糊的節點結合上下文賦予語義信息，提高了對等價結構轉換抄襲類型的檢測靈敏度；使用聚類分析將原本較大的代碼集劃分為若干小的“抄襲團伙”，減小計算量的同時，解決低閾值下抄襲檢測誤判的問題。然而，實驗部分所使用的數據集較小，還需要使用更大的數據集對文中方法進行驗證。另外，實驗系統僅實現了對Java代碼的抄襲檢測，后續考慮擴展到多語言的抄襲檢測。