程序代碼相似度檢測(cè)方法的設(shè)計(jì)與實(shí)現(xiàn)

全上克，楊新鋒

0 引言

隨著信息技術(shù)的高速發(fā)展，信息技術(shù)與教育教學(xué)的結(jié)合已經(jīng)越來(lái)越緊密，針對(duì)各類程序設(shè)計(jì)課程，就有統(tǒng)一的程序語(yǔ)言支撐平臺(tái)來(lái)幫助教學(xué)，程序語(yǔ)言支撐平臺(tái)為學(xué)生提供了一個(gè)綜臺(tái)統(tǒng)一在線練習(xí)平臺(tái)，幫助學(xué)生提供編程能力，同時(shí)也幫助教師布置程序設(shè)計(jì)課程的作業(yè)和考試，這種利用信息技術(shù)實(shí)現(xiàn)教學(xué)自動(dòng)化大大提高了教師批改作業(yè)和考試的效率[1]。然而也正是因?yàn)樾畔⒓夹g(shù)的發(fā)展，從互聯(lián)網(wǎng)上獲取程序資源也越來(lái)越方便和快捷，有些學(xué)生可能直接從網(wǎng)上查找相關(guān)程序或者從同學(xué)那里直接復(fù)制程序提交給程序語(yǔ)言支撐平臺(tái)。教師如果去手工檢查每個(gè)程序，需要進(jìn)行兩兩對(duì)比，這樣會(huì)耗費(fèi)大量的時(shí)間和精力。

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

1 程序代碼抄襲描述

由于程序代碼不像普通文本那樣沒(méi)有特別的規(guī)范，程序代碼的修改必須保證代碼不像普通文本那樣沒(méi)有特別的規(guī)范，程序代碼的修改必須保證代碼正確運(yùn)行的前提下才有作用。這就造成了代碼抄襲過(guò)程中抄襲程度的不同和檢測(cè)難度級(jí)別的不同[4]。

2 代碼相似度定義

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

使用屬性計(jì)數(shù)法來(lái)進(jìn)行源代碼的剽竊檢測(cè)時(shí)，首先對(duì)能表示程序特性的度量指標(biāo)進(jìn)行統(tǒng)計(jì)，生成其特征向量。然后可用向量空間模型的夾角來(lái)度量向量之間的相似性[6]。

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

由公式（1）可知， Sim( P1,P2)越接近 1，說(shuō)明比較的2個(gè)程序P1與P2相似越密切；若等于1，則說(shuō)明2個(gè)程序是同一個(gè)程序或完全相同，或者是在沒(méi)有改變程序結(jié)構(gòu)和標(biāo)識(shí)符個(gè)數(shù)的情況下拷貝生成的另一個(gè)程序；反之亦然，但由于 C語(yǔ)言程序的總體結(jié)構(gòu)相同（使用同樣的操作符號(hào)和關(guān)鍵字）， Sim(P 1,P 2) =0的情況很難達(dá)到。

3 代碼相似度檢測(cè)方法的設(shè)計(jì)

3.1 屬性計(jì)數(shù)法

1）常用元素的選定

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

2）獲取元素的方法

在統(tǒng)計(jì)程序里面一些元素的時(shí)候，我們可以利用Lex，Lex是非常著名的詞法分析工具，描述規(guī)則采用正則表達(dá)式[7]。描述詞法分析器的文件*.l，經(jīng)過(guò)lex編譯后，生成一個(gè)lex.yy.c的文件，然后由C編譯器編譯生成一個(gè)詞法分析器。詞法分析器，簡(jiǎn)單來(lái)說(shuō)，其任務(wù)就是輸入的各種符號(hào)，轉(zhuǎn)換成相應(yīng)的標(biāo)識(shí)符（token），轉(zhuǎn)化后的標(biāo)識(shí)符很容易被后續(xù)階段處理，其過(guò)程如圖1所示：

圖1 Lex工作原理圖

這樣我們?cè)?Lex下面寫出想要抽取元素的規(guī)則就行，Lex會(huì)生成對(duì)應(yīng)這些規(guī)則的C語(yǔ)言代碼。

3.2 結(jié)構(gòu)度量法

1）常用程序結(jié)構(gòu)的選定

在抽取程序常用結(jié)構(gòu)的時(shí)候，我們同樣得找一些具有代表性的結(jié)構(gòu)，比如for循環(huán)，while循環(huán)，if-else等常用結(jié)構(gòu)，選定的結(jié)構(gòu)為：（1）if-else結(jié)構(gòu)出現(xiàn)的次數(shù)；（2）函數(shù)個(gè)數(shù)；（3）for循環(huán)個(gè)數(shù)；（4）while循環(huán)個(gè)數(shù)；（5）do-while循環(huán)個(gè)數(shù)；（6）調(diào)用函數(shù)次數(shù)。

2）獲取常用結(jié)構(gòu)的方法

當(dāng)我們需要從一個(gè)程序里抽取常用邏輯結(jié)構(gòu)的時(shí)候，我們需要構(gòu)建C語(yǔ)言語(yǔ)法樹，構(gòu)建好C語(yǔ)言語(yǔ)法樹后，從相應(yīng)的語(yǔ)法樹上面抽取邏輯結(jié)構(gòu)，該部分的難點(diǎn)在于如何構(gòu)建語(yǔ)法樹[8]。

在構(gòu)建語(yǔ)法樹的時(shí)候，采用了開(kāi)源代碼ucc的方法，利用ucc來(lái)將程序生成相應(yīng)的語(yǔ)法結(jié)構(gòu)。將語(yǔ)法結(jié)構(gòu)存到一個(gè)*.txt文件中，然后從這個(gè)文件中抽取邏輯結(jié)構(gòu)，可以繼續(xù)采用Lex來(lái)抽取。

3.3 特征向量的生成

總前說(shuō)述，我們已經(jīng)能夠生成每個(gè)程序相應(yīng)的特征向量P(x1,x2...x14)。x1（代碼行數(shù)），x2（自定義數(shù)組個(gè)數(shù)），x3 (自定義變量個(gè)數(shù))，x4 (自定義變量使用總數(shù))，x5(關(guān)鍵字個(gè)數(shù))，x6(數(shù)值常量個(gè)數(shù))，x7(字符字符串常量個(gè)數(shù))，x8(運(yùn)算符個(gè)數(shù))，x9(if-else結(jié)構(gòu)個(gè)數(shù))，x10(函數(shù)個(gè)數(shù))，x11(for循環(huán)個(gè)數(shù))，x12(while循環(huán)個(gè)數(shù))，x13(do-while循環(huán)個(gè)數(shù))，x14(調(diào)用函數(shù)次數(shù))。

4 代碼相似度檢測(cè)方法的實(shí)現(xiàn)

4.1 獲取常用元素的實(shí)現(xiàn)

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

在獲取自定義變量個(gè)數(shù)的時(shí)候我們將重復(fù)出現(xiàn)的同一個(gè)變量只能當(dāng)作一個(gè)，這邊需要我們進(jìn)行一個(gè)去重操作。用一個(gè)數(shù)組來(lái)維護(hù)自定義變量，檢測(cè)到一個(gè)單詞時(shí)，先到這個(gè)數(shù)組里面判斷一下這個(gè)單詞是否存在，如果存在，x3不變，否則就讓x3加1。

算法偽代碼描述：

根據(jù)樣例輸入我們得出的結(jié)果與之匹配，樣例我們只是利用一部分程序，并不是完全的程序，因?yàn)槲覀兂槿≡氐臅r(shí)候并不需要將整個(gè)程序里面的信息都抽取出來(lái)，我們只是抽取一部分符合條件的，我們?cè)诔槿∵^(guò)程中會(huì)過(guò)濾掉頭文件行、宏定義行、注釋行等。

4.2 獲取程序常用結(jié)構(gòu)的實(shí)現(xiàn)

在獲取程序常用結(jié)構(gòu)的時(shí)候，關(guān)鍵是如何生成相對(duì)應(yīng)程序的語(yǔ)法樹，只有先生成了語(yǔ)法樹才能從中抽取程序結(jié)構(gòu)信息[9]。生成語(yǔ)法樹采用ucc生成。ucc會(huì)將相應(yīng)的程序生成語(yǔ)法樹，語(yǔ)法樹存放在*.asm文件中[10]。樣例如下：

在生成語(yǔ)法樹之后，可以針對(duì)相應(yīng)的文件來(lái)抽取里面的結(jié)構(gòu)信息，抽取的結(jié)構(gòu)及方法如下：

（1）if-else結(jié)構(gòu):生成的語(yǔ)法樹結(jié)構(gòu)形式如if...then...else...end-else...end-if我們可以采用直接提取 if個(gè)數(shù)，else個(gè)數(shù)，然后最后對(duì)相應(yīng)的個(gè)數(shù)除以2。

（2）函數(shù)個(gè)數(shù)：在每一個(gè)函數(shù)的開(kāi)頭，都會(huì)有一個(gè)function，形式如 function 函數(shù)名，我們可以直接抽取function的個(gè)數(shù)，因?yàn)槊總€(gè)函數(shù)只可能出現(xiàn)一次function。

（3）for循環(huán)個(gè)數(shù): for循環(huán)生成語(yǔ)法樹格式如for...end-for我們可以提取for個(gè)數(shù)和end-for個(gè)數(shù)，兩者個(gè)數(shù)肯定是相等的。

（4）while循環(huán)個(gè)數(shù)：while結(jié)構(gòu)跟for循環(huán)結(jié)構(gòu)類似，while...end-while我們同樣提取while和end-while的個(gè)數(shù)就行。

（5）do-while循環(huán)個(gè)數(shù)：do-while循環(huán)結(jié)構(gòu)是do(判斷條件){......}，我們可以通過(guò)查找 do出現(xiàn)的次數(shù)來(lái)確定有多少個(gè)do-while循環(huán)。

（6）調(diào)用函數(shù)次數(shù)：在程序內(nèi)部有許多調(diào)用的函數(shù)，比如printf, scanf以及自己寫的一些函數(shù)，在調(diào)用函數(shù)的時(shí)候語(yǔ)法數(shù)格式如：call函數(shù)名（.......）。

程序結(jié)構(gòu)信息提取出來(lái)后我們可以將這些結(jié)構(gòu)元素和4.1節(jié)提取出來(lái)的基本元素結(jié)合，這樣會(huì)形成一個(gè)特征向量，這個(gè)向量就是這個(gè)程序?qū)?yīng)的特征向量。每個(gè)程序就可以利用此方法來(lái)生成特征向量。0.890713。52006)812106)

4.3 計(jì)算程序間特征向量的相似度

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

程序樣例一：

程序樣例二：

程序樣例一：2806261110613（基本元素）812106（結(jié)構(gòu)元素）

程序樣例二：20373095210（基本元素）452006（結(jié)構(gòu)元素）

程序樣例一計(jì)算出來(lái)的特征向量p1(2806261110613

程序樣例二計(jì)算出來(lái)的特征向量p2(203730952104

由于結(jié)構(gòu)元素相比于基本元素，結(jié)構(gòu)相似顯得更加重要，經(jīng)過(guò)二分法計(jì)算，將基本元素設(shè)為43.2%，結(jié)構(gòu)元素設(shè)為56.8%較為合適。利用公式1計(jì)算出來(lái)的相似度結(jié)果為：

5 總結(jié)

程序代碼相似度檢測(cè)方法的研究主要是應(yīng)用于代碼抄襲檢測(cè)，代碼抄襲檢測(cè)必須能夠檢測(cè)各種程度的抄襲情況，并給出抄襲代碼段，方便教師監(jiān)督學(xué)生的學(xué)習(xí)情況，這對(duì)高校程序語(yǔ)言課程的教學(xué)有重大實(shí)際意義，大大減輕了教師的教學(xué)負(fù)擔(dān)。同時(shí)代碼相似度檢測(cè)還能應(yīng)用于軟件版權(quán)的判斷上，具有重大的商業(yè)價(jià)值。

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

[2]王繼遠(yuǎn).一種用于軟件作業(yè)評(píng)判系統(tǒng)的程序結(jié)構(gòu)分析算法的設(shè)計(jì)與實(shí)現(xiàn)[D].北京郵電大學(xué),2007

[3]王寧.編程題自動(dòng)評(píng)分系統(tǒng)中結(jié)構(gòu)體的研究與實(shí)現(xiàn)[D].哈爾濱工業(yè)大學(xué),2006

[4]程金宏.程序代碼相似度自動(dòng)度量研究[D].內(nèi)蒙古師范大學(xué),2007

[5]趙長(zhǎng)海，金茂忠.基于編譯優(yōu)化和反匯編的程序相似性檢測(cè)方法[D].北京航空航天大學(xué)，2008

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

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

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

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

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