一種基于靜態(tài)詞法樹的程序相似性檢測(cè)方法

(北京航空航天大學(xué) 軟件工程研究所， 北京 100083)

摘 要：

傳統(tǒng)的程序相似性檢測(cè)工具并不能有效地檢測(cè)出一些常見的高級(jí)詞法、語(yǔ)義理解變換的抄襲方式。首先歸納了學(xué)生常用的三類抄襲手段，然后給出了基于詞法樹的程序相似性檢測(cè)方法。以C語(yǔ)言為例，總結(jié)了生成詞法樹的結(jié)構(gòu)體，并對(duì)程序的詞法樹進(jìn)行主數(shù)據(jù)流、結(jié)構(gòu)控制流和時(shí)序流分析后得出結(jié)構(gòu)體依賴圖；使用形式化的圖同型方法來(lái)判斷代碼是否相似，還給出了一個(gè)聚類方法以獲得彼此相似的程序子集。通過與JPlag、BuaaSim系統(tǒng)針對(duì)一組典型的抄襲樣本集進(jìn)行評(píng)測(cè)結(jié)果對(duì)比，本方法具有更好的檢測(cè)效果。

關(guān)鍵詞：抄襲； 相似性檢測(cè)； 詞法樹； 形式化； 聚類

中圖分類號(hào)：TP311文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695(2009)04-1316-04

Program similarity detection approach based on static lexical tree

XIONG Hao， YAN Hai-hua， HE Jian-ying， ZHAO Chang-hai

(Software Engineering Institute， Beihang University， Beijing 100083， China)

Abstract:

Traditional detecting tools for program similarity can not detect some modification strategies effectively， such as senior lexical transform， and semantic rewriting. This paper concluded the three plagiarism methods that were often used by students first. Described a detection approach program similarity based on lexical tree. Taking C programming language for example， the article summarized the structure unit in order to generate lexical tree， obtained structure unit dependence graph through the analysis of the main data sequence， structure controlling sequence， and time sequence， and proposed a formulated graph similarity method to carry out code similarity detection. Also introduced a clustering algorithm to find all groups of similar programs. By using a set of plagiarized scripts as testing programs， the evaluation result shows that the method is more effective， compared to JPlag and BuaaSim.

Key words：plagiarism; similarity detection; lexical tree; formalization; clustering

當(dāng)前國(guó)內(nèi)外的大學(xué)教育中作業(yè)抄襲現(xiàn)象非常普遍[1]，在計(jì)算機(jī)專業(yè)的程序設(shè)計(jì)課程作業(yè)中，抄襲現(xiàn)象更加嚴(yán)重[2]。其主要原因是抄襲者無(wú)須對(duì)源程序進(jìn)行理解，通過編輯器改變代碼的外觀就可達(dá)到抄襲目的。日益嚴(yán)重的抄襲現(xiàn)象勢(shì)必會(huì)影響教學(xué)質(zhì)量和學(xué)生本人的程序設(shè)計(jì)能力。教育工作者使用許多手段來(lái)禁止抄襲的發(fā)生，如抄襲處罰政策、針對(duì)不同的學(xué)生給出區(qū)別性作業(yè)以及獎(jiǎng)勵(lì)制度等，但這些措施都不能很好地杜絕抄襲現(xiàn)象的發(fā)生。傳統(tǒng)的人工檢測(cè)手段耗時(shí)費(fèi)力，且檢測(cè)結(jié)果的好壞與檢測(cè)者經(jīng)驗(yàn)和代碼規(guī)模有很大的關(guān)系。如今已有很多的軟件工具輔助教師檢測(cè)代碼的相似性[3~6]，但是這些檢測(cè)工具只能檢測(cè)出一些抄襲手段，而對(duì)于目前常用的抄襲方式，如冗余代碼添加、生成新函數(shù)等抄襲方式，檢測(cè)工具會(huì)因?yàn)闊o(wú)法消除噪聲的影響而不能檢測(cè)出程序抄襲。

針對(duì)上述問題，本文提出一種程序相似性檢測(cè)方法。該方法將程序轉(zhuǎn)換為靜態(tài)詞法樹，重點(diǎn)分析代碼的控制結(jié)構(gòu)和數(shù)據(jù)依賴，從詞法的角度消除了三類抄襲手段所帶來(lái)的干擾。實(shí)驗(yàn)結(jié)果表明，該方法能有效地檢測(cè)程序的相似性。

1 相關(guān)研究

程序相似性檢測(cè)技術(shù)最早可以追溯到20世紀(jì)70年代。Ottenstein[7]基于Halstead軟件度量方法，提出屬性度量的方式檢測(cè)代碼的相似度。在這種方法的影響下，后面的一些學(xué)者在檢測(cè)系統(tǒng)的設(shè)計(jì)中引入了更多的度量屬性特征[8]。但這些工作并沒有很好地改善相似度比較效果，改進(jìn)措施就是加入程序的結(jié)構(gòu)信息來(lái)度量相似度[9]。

JPlag[5]和MOSS[6]是當(dāng)前比較知名的程序相似性檢測(cè)系統(tǒng)。在程序相似性檢測(cè)過程中都考慮了結(jié)構(gòu)特征，將源代碼轉(zhuǎn)換為字符串流，然后使用算法來(lái)計(jì)算字符串流的相似度。相比純屬性度量方式，這兩個(gè)工具系統(tǒng)均可獲得很好的比較效果。此外還有學(xué)者使用案例推理[10]、神經(jīng)網(wǎng)絡(luò)[11]、優(yōu)化編譯[12]等方法來(lái)比較代碼的相似性。

大部分的檢測(cè)工具和方法都只能檢測(cè)很少的抄襲手段[13]，學(xué)生可以利用系統(tǒng)無(wú)法檢測(cè)出的抄襲手段來(lái)逃避抄襲檢測(cè)。所以，一個(gè)良好的檢測(cè)方法需要檢測(cè)出盡可能多的抄襲手段。雖然沒有權(quán)威的代碼抄襲手段分類，但筆者發(fā)現(xiàn)，抄襲者在不理解源代碼內(nèi)部流程的背景下，為了保證程序運(yùn)行的正確性，所做的代碼變換一般為三種方式：

a)低級(jí)變換方式，如修改注釋、更改變量名等。

b)詞法理解變換方式，如調(diào)整表達(dá)式、控制結(jié)構(gòu)語(yǔ)句等價(jià)變換等。

c)局部性語(yǔ)義理解變化方式，如函數(shù)分解和結(jié)合等。

前兩類的抄襲方式是在詞法層次上所做的代碼修改，對(duì)程序語(yǔ)言有所了解的學(xué)生經(jīng)常使用這兩類抄襲方式，10種典型的抄襲手段[14]可劃分到這兩類抄襲方式中。第三類抄襲方式涉及到程序語(yǔ)義，是學(xué)生充分理解源程序的某些代碼片段后所使用的抄襲方式。相比詞法變換，語(yǔ)義理解需要花費(fèi)更高的代價(jià)，但這類抄襲方式能夠在很大程度上改變?cè)创a的外觀，從而加大檢測(cè)的難度。

2 基于詞法樹的程序相似性檢測(cè)方法

基于靜態(tài)詞法樹的程序相似性檢測(cè)方法的核心思想是確定描述代碼的詞法樹；然后對(duì)詞法樹進(jìn)行數(shù)據(jù)依賴和控制依賴分析，將其轉(zhuǎn)換為結(jié)構(gòu)體依賴圖；最后，經(jīng)過相似性決策與聚類過程得出抄襲檢測(cè)結(jié)果。需要指出的是，本方法是以描述代碼的詞法樹為基礎(chǔ)，而詞法樹的生成與具體的程序設(shè)計(jì)語(yǔ)言有關(guān)。為方便描述檢測(cè)方法，本文選用C語(yǔ)言作為程序設(shè)計(jì)作業(yè)所用的語(yǔ)言。

2.1 靜態(tài)詞法樹

受時(shí)間估計(jì)上下文樹描述代碼的思想[15]啟發(fā)，本文使用靜態(tài)詞法樹來(lái)描述代碼，代碼被標(biāo)志為詞法樹中的結(jié)構(gòu)體，每個(gè)結(jié)構(gòu)體有且僅有一種類型。表1 總結(jié)了C語(yǔ)言的一些常見結(jié)構(gòu)體。

表1 代碼結(jié)構(gòu)體



編號(hào)類型結(jié)構(gòu)體描述

1(function name)_sequence函數(shù)入口

2declaration變量聲明

3assignment賦值語(yǔ)句（兩種方式：直接賦值和從終端，文本中獲得）

4returnreturn語(yǔ)句

5code除上述兩種結(jié)構(gòu)體語(yǔ)句外的語(yǔ)句，如printf語(yǔ)句

6for循環(huán)體(for、do/while、while語(yǔ)句區(qū)域)

7if判斷控制體（if、switch/case、if/else語(yǔ)句區(qū)域，三目運(yùn)算?）

8methodfor循環(huán)體中步進(jìn)方式表達(dá)式

9testfor、if結(jié)構(gòu)體控制表達(dá)式

10jump跳轉(zhuǎn)語(yǔ)句:goto、break、continue

11sequence流（同一嵌套層次中出現(xiàn)了至少兩個(gè)以上結(jié)構(gòu)體）

12call_(function name)自定義函數(shù)調(diào)用語(yǔ)句

詞法樹描述函數(shù)內(nèi)部代碼與函數(shù)之間的關(guān)系。諸如頭文件、函數(shù)或類型聲明等語(yǔ)句將被直接忽略，全局變量和宏定義將在引用處被替換。表1中編號(hào)2、3、5的結(jié)構(gòu)體以代碼行為基本單元；編號(hào)為1、4、6、7、10、12的結(jié)構(gòu)體生成與C語(yǔ)言關(guān)鍵字有關(guān)；結(jié)構(gòu)體8、9識(shí)別相應(yīng)的表達(dá)式；結(jié)構(gòu)體11不描述任何代碼。



圖1是一份代碼的靜態(tài)詞法樹形式，左側(cè)代碼查表1后得出詞法樹中的各個(gè)結(jié)構(gòu)體。詞法樹的層次體現(xiàn)了代碼嵌套關(guān)系，結(jié)構(gòu)體的數(shù)字序號(hào)是由詞法樹層次關(guān)系和結(jié)構(gòu)體生成順序確定的，子序號(hào)表示函數(shù)調(diào)用關(guān)系，詞法樹合并了序號(hào)連續(xù)且類型相同的結(jié)構(gòu)體。為方便后續(xù)的主數(shù)據(jù)流分析，引入結(jié)構(gòu)體屬性。根據(jù)結(jié)構(gòu)體所對(duì)應(yīng)的源代碼片段對(duì)變量的操作情況，有use（使用變量值）和change（改變變量值）兩種結(jié)構(gòu)體屬性。

2.2 結(jié)構(gòu)體依賴圖

結(jié)構(gòu)體依賴圖是在靜態(tài)詞法樹的基礎(chǔ)上，分析結(jié)構(gòu)體之間的數(shù)據(jù)依賴和控制依賴關(guān)系后生成的圖結(jié)構(gòu)。

2.2.1 主數(shù)據(jù)流分析

程序類作業(yè)自動(dòng)評(píng)判通常以程序作業(yè)的運(yùn)行結(jié)果與預(yù)期結(jié)果比較來(lái)判斷程序作業(yè)是否正確。輸出的運(yùn)行結(jié)果要么直接使用代碼中的某些變量值，要么與某些變量建立了間接關(guān)系。學(xué)生所使用的抄襲方式中，一般是在詞法層次上添加一些混淆信息來(lái)改變代碼外觀，增加人工閱讀代碼辨別抄襲的難度。而局部性語(yǔ)義理解的抄襲方式，也只在一些小的代碼片段上下功夫。一般來(lái)說，學(xué)生為保證提交代碼的正確性，很少或不會(huì)改變那些含有影響函數(shù)輸出的變量代碼，筆者將這些直接或間接影響函數(shù)輸出的變量稱為主數(shù)據(jù)。需要強(qiáng)調(diào)的是，直接影響函數(shù)輸出的語(yǔ)句有輸出顯示和函數(shù)返回語(yǔ)句。當(dāng)這些語(yǔ)句受控制條件影響時(shí)，那么控制條件中的變量間接影響函數(shù)輸出。主數(shù)據(jù)流分析的目的是獲得影響這些主數(shù)據(jù)值的結(jié)構(gòu)體序列。

主數(shù)據(jù)流分析算法的流程如圖2所示。算法開始時(shí)主數(shù)據(jù)流序列M為空值，輸入的集合A是根據(jù)詞法樹生成的含有主數(shù)據(jù)的結(jié)構(gòu)體集合， num函數(shù)是獲得結(jié)構(gòu)體在詞法樹中的序號(hào)值，type函數(shù)是結(jié)構(gòu)體查表1所得到的類型編號(hào)。算法經(jīng)過若干步迭代后，輸出所有主數(shù)據(jù)的結(jié)構(gòu)體序列。



2.2.2 結(jié)構(gòu)控制流分析

代碼的非順序執(zhí)行關(guān)系（跳轉(zhuǎn)、調(diào)用、控制）在很大程度上體現(xiàn)了編碼者的思維，并且對(duì)程序數(shù)據(jù)計(jì)算有很大影響。抄襲者往往因?yàn)楦淖冞@些非順序執(zhí)行關(guān)系會(huì)花費(fèi)相當(dāng)?shù)拇鷥r(jià)而放棄修改這種關(guān)系，所以通過分析代碼中的非順序執(zhí)行關(guān)系可以追蹤一些詞法層次上的代碼變換。筆者將代碼的非順序執(zhí)行關(guān)系稱為結(jié)構(gòu)控制關(guān)系，其在詞法樹上的表現(xiàn)形式為某一結(jié)構(gòu)體的存在影響其他結(jié)構(gòu)體，如內(nèi)嵌在if結(jié)構(gòu)體中test結(jié)構(gòu)體對(duì)其所有的子樹都有影響。結(jié)構(gòu)控制流分析的目的是確定結(jié)構(gòu)體之間的結(jié)構(gòu)控制關(guān)系，并生成結(jié)構(gòu)控制的結(jié)構(gòu)體序列。

2.2.3 代碼時(shí)序流分析

詞法樹中結(jié)構(gòu)體序號(hào)的順序關(guān)系將詞法樹降維成一維的鏈表結(jié)構(gòu)。代碼時(shí)序流是由詞法樹結(jié)構(gòu)體的序號(hào)順序排列生成的結(jié)構(gòu)體序列。由于詞法樹中結(jié)構(gòu)體可能存在子序號(hào)，那么代碼時(shí)序流是一個(gè)序列集合。時(shí)序流分析時(shí)必須考慮結(jié)構(gòu)體是否存在并行關(guān)系，這是因?yàn)閷儆谕磺短讓哟蔚拇a相互調(diào)整位置時(shí)，可能并不影響程序的最后結(jié)果。所謂的并行關(guān)系是指詞法樹的多個(gè)子樹之間對(duì)于變量的操作沒有出現(xiàn)“讀后寫”“寫后讀”“寫后寫”的現(xiàn)象。表1中只有編號(hào)為1和11結(jié)構(gòu)體的子樹可能存在并行關(guān)系。子樹不存在并行關(guān)系時(shí)，代碼時(shí)序流是根據(jù)原詞法樹生成；當(dāng)子樹存在并行關(guān)系時(shí)，代碼時(shí)序流除了由原詞法樹生成，還需要由交換存在并行關(guān)系的子樹位置后得到一些新的詞法樹生成。

圖1中代碼生成的詞法樹在刪除連線關(guān)系后，經(jīng)過上述三種流分析得到結(jié)構(gòu)體依賴圖（圖3）。其中，實(shí)線為函數(shù)中的主數(shù)據(jù)流，結(jié)構(gòu)控制流用虛線表示。因?yàn)閷?shí)線方框區(qū)域內(nèi)結(jié)構(gòu)體子樹沒有并行關(guān)系，代碼時(shí)序流由圖1中詞法樹序號(hào)確定。



程序規(guī)格化為詞法樹，通過流分析后轉(zhuǎn)換為結(jié)構(gòu)體依賴圖，后續(xù)的相似性決策階段將根據(jù)結(jié)構(gòu)體依賴圖最終判定代碼是否相似。

2.3 相似性決策

為確定兩份代碼是否存在抄襲，首先給出結(jié)構(gòu)體依賴圖的形式化定義。

定義1 結(jié)構(gòu)體依賴圖G=（V，E，U，，N）。其中，

V:結(jié)構(gòu)體依賴圖中節(jié)點(diǎn)的集合，|V|表示節(jié)點(diǎn)個(gè)數(shù)。

E：EV×V，G中的邊集合。

U:v∈V，U(v)=type_id，type_id為表1所示的節(jié)點(diǎn)類型編號(hào)。

:e∈E，(e)=edge_type，edge_type為邊類型，值為D(data)和C(control)。

N:V→I函數(shù)，對(duì)于v∈V，N(v)=id，id為G中節(jié)點(diǎn)的序號(hào)。

使用圖同型來(lái)決策代碼抄襲。如果兩份代碼結(jié)構(gòu)體依賴圖同型，則認(rèn)為代碼存在抄襲。下面給出圖同型的三個(gè)定義：

定義2 全相似。 圖G=(V，E，U，，N)與圖G′=(V′，E′，U′，′，N′)全相似，存在雙射函數(shù)f:V→V′，當(dāng)

v∈V，U(v)=U′(f(v))

e=(vi，vj)∈E，e′=(f(vi)，f(vj))∈E′使(e)=′(e′)

e′=(v′i，v′j)∈E′，e=(f-1(v′i)，f-1(v′j))∈E使′(e′)=(e)

v∈V，N(v)=N′(f(v))

定義3 子圖相似。單射函數(shù)f:V→V′，G=(V，E，U，，N)子圖相似于G′=(V′，E′，U′，′，N′)，當(dāng)且僅當(dāng)存在子圖SG′，函數(shù)F使S全相似于G。

定義4 τ相似。G=(V，E，U，，N)τ相似于G′=(V′，E′，U′，′，N′)，當(dāng)且僅當(dāng)存在SG，|S|≥τ|G|（|G|=|V|），S子圖相似于G′，τ∈(0，1]。

一般來(lái)說，詞法樹的生成可以消除由詞法變化抄襲手段所帶來(lái)的噪聲。考慮到抄襲的代價(jià)，局部性語(yǔ)義理解抄襲手段不可能同時(shí)使抄襲代碼與源代碼之間的主數(shù)據(jù)流、結(jié)構(gòu)控制流和時(shí)序流都達(dá)到很低的相似度水平。通常情況下，如果兩份代碼中存在抄襲，那么它們的結(jié)構(gòu)體依賴圖至少90%相似。而獨(dú)立編寫的程序結(jié)構(gòu)體依賴圖相似性在80%以下。故本文實(shí)驗(yàn)中所選用的τ值為0.9，此值為經(jīng)驗(yàn)值，受代碼長(zhǎng)度和抄襲代價(jià)的影響，可根據(jù)具體情況調(diào)整τ值。

2.4 相似程序集生成

程序的結(jié)構(gòu)體依賴圖兩兩之間判定是否圖同型之后，還需要通過聚類從所有提交的源程序集合中分析出相似的程序集合。聚類過程中最重要的是分析出最原始的程序（其他的抄襲程序均可視為抄襲這份代碼，或是抄襲者之間互相抄襲程序），并將其作為聚類種子，才可獲得最大程度的相似程序集。如A是源程序，B抄襲A，C抄襲A，如果使用B程序作為聚類種子，那么A與B代碼相似，但B和C代碼可能不相似，這樣聚類將會(huì)丟棄C程序。

考慮到在保證代碼執(zhí)行結(jié)果不變的前提下，在源程序中添加代碼的代價(jià)遠(yuǎn)小于刪除代碼的代價(jià)。筆者認(rèn)為聚類種子可以通過學(xué)習(xí)的方式獲得，即開始任選一個(gè)程序的結(jié)構(gòu)體依賴圖G作為聚類種子，在整個(gè)代碼集中兩兩比較后找到一個(gè)圖同型的依賴圖 G′，且|G′|<| G|；修改聚類種子為 G′，繼續(xù)在代碼集中比較，直至尋找到所有的圖同型的代碼。

3 實(shí)驗(yàn)及結(jié)果評(píng)測(cè)

JPlag提供在線免費(fèi)檢測(cè)功能[16]，是目前比較流行的代碼相似性檢測(cè)工具；BuaaSim系統(tǒng)采用優(yōu)化編譯的方法[12]，對(duì)課程程序作業(yè)有很好的抄襲檢測(cè)效果。筆者所做的實(shí)驗(yàn)是對(duì)于同一份評(píng)測(cè)樣本，由詞法樹方法人工分析獲得程序相似性評(píng)測(cè)結(jié)果，并將評(píng)測(cè)結(jié)果與JPlag系統(tǒng)、BuaaSim系統(tǒng)的評(píng)測(cè)結(jié)果進(jìn)行比較，發(fā)現(xiàn)本方法的長(zhǎng)處與不足。

3.1 實(shí)驗(yàn)設(shè)計(jì)

本文選取的是文獻(xiàn)[12]中的評(píng)測(cè)程序集。評(píng)測(cè)程序集是由一組C語(yǔ)言程序組成，所對(duì)應(yīng)的問題是統(tǒng)計(jì)出現(xiàn)次數(shù)最多的整數(shù)。程序集一共包括18份代碼。其中三份代碼是由三個(gè)同學(xué)獨(dú)立完成，而其他的代碼均是抄襲這三份代碼。另外，新增加了基于這三份代碼的10份抄襲樣本。評(píng)測(cè)程序集可以在http://pickup.mofile.com/1020443105711120下載。

3.2實(shí)驗(yàn)結(jié)果及分析

編號(hào)0、10和20是三個(gè)不同的原始程序，其他編號(hào)的程序都是抄襲這三個(gè)程序得到的。從表2的比較結(jié)果可以發(fā)現(xiàn)，BuaaSim和詞法樹方法的檢測(cè)效果都明顯好于JPlag，詞法樹的方法比BuaaSim系統(tǒng)多檢測(cè)出編號(hào)為8、12、17的代碼抄襲。經(jīng)過仔細(xì)分析，發(fā)現(xiàn)樣本提供者對(duì)于原始程序做了如下改動(dòng):

a）函數(shù)類型及返回值變換;

b）將一個(gè)函數(shù)分解成兩個(gè)函數(shù);

c）添加變量過程值依賴的冗余判斷條件;

d）改變if/else的控制條件和嵌套關(guān)系。

這四種抄襲手段大大降低了抄襲代碼和原始代碼的相似性，使JPlag和BuaaSim失效。以10和17號(hào)代碼為例，代碼片段如圖4所示。

表2 JPlag、BuaaSim和詞法樹的檢測(cè)結(jié)果



聚類結(jié)果

抄襲類{0，1，2，3，4，5，6，7，8，9}

{10，11，12，13，14，15，16，17，18，19}

{20，21，22，23，24，25，26，27}

JPlag{0，2，3，4，5，6，7}

{10，11，13，16}

{20，22，23，24，25}

BuaaSim{0，1，2，3，4，5，6，7，9}

{10，11，13，14，15，16，19}

{20，21，22，23，24，25，26，27}

詞法樹{0，1，2，3，4，5，6，7，8，9}

{10，11，12，13，14，15，16，17，19}

{20，21，22，23，24，25，26，27}

抄襲者對(duì)源代碼進(jìn)行一些簡(jiǎn)單分析后，主要使用上述b）~d）抄襲手段，這些手段都屬于局部性語(yǔ)義理解的變換方式。雖然沒有花費(fèi)抄襲者很高的代價(jià)，但使代碼的外貌特征改變很大，使用常規(guī)的基于字符流或是標(biāo)志符的方法，將無(wú)法檢測(cè)出這些抄襲手段，從而判定這兩個(gè)程序沒有抄襲。

這些局部性語(yǔ)義理解的抄襲手段并沒有改變對(duì)程序主數(shù)據(jù)的操作。使用詞法樹的方法，生成的結(jié)構(gòu)體依賴圖如圖5所示。受代碼片段的影響，各個(gè)結(jié)構(gòu)體的絕對(duì)位置無(wú)法確定，故而取消了結(jié)構(gòu)體的序號(hào)。

從形式化結(jié)構(gòu)體依賴圖可以發(fā)現(xiàn)，抄襲代碼的結(jié)構(gòu)體依賴圖G′比G多了

{e1:vi→vj，U(vi)=12，U(vj)=1，e2∶vx→vy，U(vx)=12，U(vy)=4，(e1)=C，(e2)=D}

G′子圖相似于G，從而確定圖所代表的兩份代碼存在抄襲。

三種方法都沒有檢測(cè)出編號(hào)為18的代碼抄襲。查看抄襲代碼后發(fā)現(xiàn)，樣本提供者改變了原始代碼鏈表的實(shí)現(xiàn)方法，轉(zhuǎn)換為多元數(shù)組結(jié)構(gòu)。采用這種抄襲手段需要付出很大的代價(jià)，且需要相當(dāng)?shù)木幊棠芰蛯?duì)數(shù)據(jù)實(shí)現(xiàn)方法轉(zhuǎn)換的理解。一般說來(lái)，在真正的教學(xué)中幾乎不會(huì)遇到這類的抄襲。



JPlag雖然是目前比較流行的代碼相似性檢測(cè)工具，但其遺漏的程序較多，一些簡(jiǎn)單的詞法變換、冗余代碼添加也能對(duì)代碼間相似度產(chǎn)生較大的影響，說明JPlag只能檢測(cè)低級(jí)的和部分詞法變換的抄襲，應(yīng)用范圍有限。BuaaSim要求檢測(cè)的樣本程序集是可編譯的，JPlag和詞法樹的方法即使編譯不通過，也可以進(jìn)行相似性比較。JPlag可以定位兩個(gè)程序之間存在抄襲的代碼片段，而BuaaSim優(yōu)化編譯后將丟失代碼段的定位信息，詞法樹形式換抄襲決策的方法也不能夠明確定位程序之間的抄襲片段。而且，詞法樹的方法限制了比較代碼的種類（代碼必須具有主數(shù)據(jù)），這是詞法樹方法的不足之處。

4 結(jié)束語(yǔ)

通過分析與實(shí)驗(yàn)可以看出，本文中所給出的代碼相似性檢測(cè)方法有較強(qiáng)的抗干擾能力。在總結(jié)并歸納了目前常見的三類抄襲方式之后，并沒有采用傳統(tǒng)的消除或者轉(zhuǎn)換抄襲代碼片段的方式，而是根據(jù)源代碼生成靜態(tài)詞法樹，然后再由詞法樹進(jìn)行三種流分析，有效地消除了抄襲手段所帶來(lái)的噪聲，給出的抄襲決策方法和聚類方法可以提取抄襲程序集。

下一步工作重點(diǎn)將是利用詞法樹方法開發(fā)代碼相似性檢測(cè)的系統(tǒng)平臺(tái)。相比其他檢測(cè)方法，本方法主要限制在比較代碼的種類上，無(wú)法檢測(cè)應(yīng)用型的程序設(shè)計(jì)作業(yè)，諸如MFC開發(fā)、代碼模塊功能添加等，這也是今后的努力方向。另外，對(duì)于大型作業(yè)，降低多元主數(shù)據(jù)流比較的時(shí)間復(fù)雜度也是本方法后續(xù)解決的問題。

參考文獻(xiàn)：

[1]VAMPLEW P， DERMOUDY J. An anti-plagiarism editor for software development courses[C]//Proc of the 7th Australasian Conference on Computing Education. Australasian: Australasian Computer Society Press， 2005:383-387.

[2]MCCABE D. Levels of cheating and plagiarism remain high[C/OL]. (2005). http://acadeicintegrity.org/.

[3]WHALE G. Plague: plagiarism detection using program structure， 8805[R]. Sydney: Dept of Computer Science， University of NSW， 1988.

[4]WISE M J. YAP3: Improved detection of similarities in computer program and other texts[J].ACM SIGCSE Bulletin， 1996，28(1):130-134.

[5]PRECHELT L， MALPOHL G， PHILIPPSEN M. Finding plagiarisms among a set of programs with JPlag[J]. Journal of Universal Computer Science， 2002， 8(11):1016-1038.

[6]MOSS: measure of software similarity [EB/OL] .http://theory.stanford.edu/~aiken/moss/.

[7]OTTENSTEIN K J. An algorithmic approach to the detection and prevention of plagiarism[J].ACM SIGSCE Bulletin， 1976， 8(4):30-41.

[8]FAIDHI J A W， ROBINSON S K. An empirical approach for detection program similarity and plagiarism within a university programming environment [J]. Computers and Education， 1987，11(1):11-19.

[9]VERCO K L， WISE M J. Software for detecting suspected plagiarism: comparing structure and attribute-counting systems[C] //Proc of the 1st Australian Conference on Computer Science Education. 1996:3-5.

[10]CLOUGH P. Plagiarism in natural and programming languages: an overview of current tools and technologies[R]. London: Department of Computer Science， University of Sheffield， 2000.

[11]ENGELS S， LAKSHMANAN V， CRAIG M. Plagiarism detection using feature-based neural networks[C] //Proc of the 38th SIGCSE Symposium on Computer Science Education New York:ACM Press， 2007:34-38.

[12]趙長(zhǎng)海，晏海華，金茂忠. 一個(gè)基于編譯優(yōu)化和反匯編的程序相似性檢測(cè)方法[J]. 北京航空航天大學(xué)學(xué)報(bào)， 2008，34(6): 711-715.

[13]LIU Chao， CHEN Chen， HAN Jia-wei， et al. GPLAG : detection of software plagiarism by program dependence graph analysis[C]//Proc of the 12th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. New York:ACM Press. 2006:872-881.

[14]JONES E L. Metrics based plagiarism monitoring[J]. Journal of Computing Sciences in Colleges， 2001，16(4):253-261.

[15]易會(huì)戰(zhàn)，陳娟，楊學(xué)軍. 基于語(yǔ)法樹的實(shí)時(shí)動(dòng)態(tài)電壓調(diào)節(jié)低功耗算法[J]. 軟件學(xué)報(bào)， 2005，16(10):1726-1734.

[16] JPlag[EB/OL].http://www.ipd.uni-karlsruhe.de/jplag/.