程序代碼相似度檢測方法的設計與實現

全上克，楊新鋒

0 引言

隨著信息技術的高速發展，信息技術與教育教學的結合已經越來越緊密，針對各類程序設計課程，就有統一的程序語言支撐平臺來幫助教學，程序語言支撐平臺為學生提供了一個綜臺統一在線練習平臺，幫助學生提供編程能力，同時也幫助教師布置程序設計課程的作業和考試，這種利用信息技術實現教學自動化大大提高了教師批改作業和考試的效率[1]。然而也正是因為信息技術的發展，從互聯網上獲取程序資源也越來越方便和快捷，有些學生可能直接從網上查找相關程序或者從同學那里直接復制程序提交給程序語言支撐平臺。教師如果去手工檢查每個程序，需要進行兩兩對比，這樣會耗費大量的時間和精力。

從早在20世紀70年代初開始，就有學者研究阻止大規模拷貝程序的技術和軟件，出現了一批比較典型的程序源代碼剽竊檢測系統[2]。從國內外的研究現狀可以發現，國內在對程序相似度判別的研究做的非常少，大部分集中在對中文分詞和語義的研究上。而國外雖然有很多成熟的系統，也發展結構化度量等成熟的技術，但都是基于文本轉換和串匹配算法來實現代碼相似度檢測的。程序代碼的抄襲跟普通文本抄襲還有不同，不同的代碼可能實現同樣的功能.有些聰明的抄襲者會使用一些技巧對代碼進行修改，比如for循環變成while循環、添加很多中間變量，這樣會降低串匹配算法的有效性。如何找到一種更合適的方法來檢測更智能的抄襲是本文研究的重點[3]。

1 程序代碼抄襲描述

由于程序代碼不像普通文本那樣沒有特別的規范，程序代碼的修改必須保證代碼不像普通文本那樣沒有特別的規范，程序代碼的修改必須保證代碼正確運行的前提下才有作用。這就造成了代碼抄襲過程中抄襲程度的不同和檢測難度級別的不同[4]。

2 代碼相似度定義

代碼相似度表示一個程序與另外一個程序之間的相似程度，很明顯100%相似就是完全相等。兩個程序是否存在抄襲關系就是通過代碼相似度來進行度量的，相似度越高，抄襲的可能性越大[5]。

使用屬性計數法來進行源代碼的剽竊檢測時，首先對能表示程序特性的度量指標進行統計，生成其特征向量。然后可用向量空間模型的夾角來度量向量之間的相似性[6]。

令P1表示候選程序，其詞頻向量為P1( w1,w2,...,wn),P2表示檢測程序，其詞頻向量為P2 (x1,x 2,....,xn),其中 wi, xi(1＜= i ＜= N)表示各特征值的詞頻，則程序段P1和P2之間的相似度Sim (P1,P2)用向量空間模型的余弦公式來度量，代碼相似度定義如公式

由公式（1）可知， Sim( P1,P2)越接近 1，說明比較的2個程序P1與P2相似越密切；若等于1，則說明2個程序是同一個程序或完全相同，或者是在沒有改變程序結構和標識符個數的情況下拷貝生成的另一個程序；反之亦然，但由于 C語言程序的總體結構相同（使用同樣的操作符號和關鍵字）， Sim(P 1,P 2) =0的情況很難達到。

3 代碼相似度檢測方法的設計

3.1 屬性計數法

1）常用元素的選定

在計算特征向量之間的相似度時，向量中的元素需要謹慎挑選。在挑選一段程序里面的常用屬性的時候，應該選取一些具有特征意義的，本文挑選出以下幾個屬性作為特征向量里面的元素：（1）代碼行數；（2）數組個數：統計出程序里定義了多少個數組；（3）自定義變量：統計程序里面不重復出現的自定義變量個數；（4）自定義變量總數：查找程序里面出現的自定義變量總數；（5）關鍵字：計算一下程序里面出現了多少次關鍵字；（6）數值常量：常量分為數值常量和字符常量；（7）字符常量：字符常量里面包括單個字符和字符串；（8）運算符。

2）獲取元素的方法

在統計程序里面一些元素的時候，我們可以利用Lex，Lex是非常著名的詞法分析工具，描述規則采用正則表達式[7]。描述詞法分析器的文件*.l，經過lex編譯后，生成一個lex.yy.c的文件，然后由C編譯器編譯生成一個詞法分析器。詞法分析器，簡單來說，其任務就是輸入的各種符號，轉換成相應的標識符（token），轉化后的標識符很容易被后續階段處理，其過程如圖1所示：

圖1 Lex工作原理圖

這樣我們在 Lex下面寫出想要抽取元素的規則就行，Lex會生成對應這些規則的C語言代碼。

3.2 結構度量法

1）常用程序結構的選定

在抽取程序常用結構的時候，我們同樣得找一些具有代表性的結構，比如for循環，while循環，if-else等常用結構，選定的結構為：（1）if-else結構出現的次數；（2）函數個數；（3）for循環個數；（4）while循環個數；（5）do-while循環個數；（6）調用函數次數。

2）獲取常用結構的方法

當我們需要從一個程序里抽取常用邏輯結構的時候，我們需要構建C語言語法樹，構建好C語言語法樹后，從相應的語法樹上面抽取邏輯結構，該部分的難點在于如何構建語法樹[8]。

在構建語法樹的時候，采用了開源代碼ucc的方法，利用ucc來將程序生成相應的語法結構。將語法結構存到一個*.txt文件中，然后從這個文件中抽取邏輯結構，可以繼續采用Lex來抽取。

3.3 特征向量的生成

總前說述，我們已經能夠生成每個程序相應的特征向量P(x1,x2...x14)。x1（代碼行數），x2（自定義數組個數），x3 (自定義變量個數)，x4 (自定義變量使用總數)，x5(關鍵字個數)，x6(數值常量個數)，x7(字符字符串常量個數)，x8(運算符個數)，x9(if-else結構個數)，x10(函數個數)，x11(for循環個數)，x12(while循環個數)，x13(do-while循環個數)，x14(調用函數次數)。

4 代碼相似度檢測方法的實現

4.1 獲取常用元素的實現

在常用元素的獲取過程中，關鍵難點在于如何獲取自定義變量的個數（x3）以及自定義變量使用的總數(x4)和關鍵字個數(x5)。

在獲取自定義變量個數的時候我們將重復出現的同一個變量只能當作一個，這邊需要我們進行一個去重操作。用一個數組來維護自定義變量，檢測到一個單詞時，先到這個數組里面判斷一下這個單詞是否存在，如果存在，x3不變，否則就讓x3加1。

算法偽代碼描述：

根據樣例輸入我們得出的結果與之匹配，樣例我們只是利用一部分程序，并不是完全的程序，因為我們抽取元素的時候并不需要將整個程序里面的信息都抽取出來，我們只是抽取一部分符合條件的，我們在抽取過程中會過濾掉頭文件行、宏定義行、注釋行等。

4.2 獲取程序常用結構的實現

在獲取程序常用結構的時候，關鍵是如何生成相對應程序的語法樹，只有先生成了語法樹才能從中抽取程序結構信息[9]。生成語法樹采用ucc生成。ucc會將相應的程序生成語法樹，語法樹存放在*.asm文件中[10]。樣例如下：

在生成語法樹之后，可以針對相應的文件來抽取里面的結構信息，抽取的結構及方法如下：

（1）if-else結構:生成的語法樹結構形式如if...then...else...end-else...end-if我們可以采用直接提取 if個數，else個數，然后最后對相應的個數除以2。

（2）函數個數：在每一個函數的開頭，都會有一個function，形式如 function 函數名，我們可以直接抽取function的個數，因為每個函數只可能出現一次function。

（3）for循環個數: for循環生成語法樹格式如for...end-for我們可以提取for個數和end-for個數，兩者個數肯定是相等的。

（4）while循環個數：while結構跟for循環結構類似，while...end-while我們同樣提取while和end-while的個數就行。

（5）do-while循環個數：do-while循環結構是do(判斷條件){......}，我們可以通過查找 do出現的次數來確定有多少個do-while循環。

（6）調用函數次數：在程序內部有許多調用的函數，比如printf, scanf以及自己寫的一些函數，在調用函數的時候語法數格式如：call函數名（.......）。

程序結構信息提取出來后我們可以將這些結構元素和4.1節提取出來的基本元素結合，這樣會形成一個特征向量，這個向量就是這個程序對應的特征向量。每個程序就可以利用此方法來生成特征向量。0.890713。52006)812106)

4.3 計算程序間特征向量的相似度

這一節主要介紹下如何計算程序間的相似度。有兩段樣例程序如下：

程序樣例一：

程序樣例二：

程序樣例一：2806261110613（基本元素）812106（結構元素）

程序樣例二：20373095210（基本元素）452006（結構元素）

程序樣例一計算出來的特征向量p1(2806261110613

程序樣例二計算出來的特征向量p2(203730952104

由于結構元素相比于基本元素，結構相似顯得更加重要，經過二分法計算，將基本元素設為43.2%，結構元素設為56.8%較為合適。利用公式1計算出來的相似度結果為：

5 總結

程序代碼相似度檢測方法的研究主要是應用于代碼抄襲檢測，代碼抄襲檢測必須能夠檢測各種程度的抄襲情況，并給出抄襲代碼段，方便教師監督學生的學習情況，這對高校程序語言課程的教學有重大實際意義，大大減輕了教師的教學負擔。同時代碼相似度檢測還能應用于軟件版權的判斷上，具有重大的商業價值。

[1]張文典，任冬偉.程序抄襲判定系統[J].小型微型計算機系統，1988,9(10):34-39

[2]王繼遠.一種用于軟件作業評判系統的程序結構分析算法的設計與實現[D].北京郵電大學,2007

[3]王寧.編程題自動評分系統中結構體的研究與實現[D].哈爾濱工業大學,2006

[4]程金宏.程序代碼相似度自動度量研究[D].內蒙古師范大學,2007

[5]趙長海，金茂忠.基于編譯優化和反匯編的程序相似性檢測方法[D].北京航空航天大學，2008

[6]王成，劉金剛.一種改進的字符串匹配算法[J].計算機工程，2006,32（2):62-64.

[7]Alfred,V.A.等著；趙建華等譯.編譯原理 第2版[M].北京:機械工業出版社，2009.1

[8]于海英，趙俊嵐.最長公共子序列算法在程序代碼相似度度量中的應用[J].內蒙古大學學報(自然科學版),2008，39(2):60-64

[9]鄧愛萍.程序代碼相似度度量算法研究[J].計算機工程與設計，2008，29(17):72-76

[10]于海英.程序代碼相似度度量的研究與實現[J].計算機工程，2010，36(4):88-92