衛(wèi)軍超　耿楠

摘要：針對(duì)傳統(tǒng)相似度算法應(yīng)用在程序設(shè)計(jì)課程作業(yè)檢測(cè)中精度較低這一問(wèn)題，通過(guò)研究最長(zhǎng)公共子序列等算法，發(fā)現(xiàn)其優(yōu)缺點(diǎn)，在分析的基礎(chǔ)上，結(jié)合結(jié)構(gòu)度量技術(shù)和屬性技術(shù)兩種技術(shù)，提出一種性能較好的程序相似度計(jì)算方法。方法首先對(duì)源程序進(jìn)行初步處理，將程序中的注釋語(yǔ)句和空格刪除，再次確定常用元素及常用結(jié)構(gòu)，然后利用Lex統(tǒng)計(jì)、抽取程序元素；利用開源代碼ucc生成語(yǔ)法樹，之后抽取相應(yīng)的語(yǔ)法結(jié)構(gòu)；最后生成特征向量，并計(jì)算代碼相似度。實(shí)驗(yàn)結(jié)果表明該方法比最長(zhǎng)公共子序列算法精度提高了10.6%。

關(guān)鍵詞：屬性計(jì)數(shù)法；結(jié)構(gòu)度量技術(shù) ；相似度度量

中圖分類號(hào)： TP311 文獻(xiàn)標(biāo)志碼： A 文章編號(hào)：1009-3044（2017）05-0039-02

Abstract： To solve the problem of the low precision of testing for similarity of program codes in traditional ways， this thesis proposes an improved technique to make such a test on the combination of technology of attribute counting and that of structure calculation through studying and comparing several different methods of calculating the Longest Common Subsequence. Firstly， source program is processed primarily， annotation statements and spaces are deleted， and common elements and structures get confirmation； next， statistics are made by means of Lex， program elements are extracted， and abstract syntax trees get to be generated using UCC； then， grammar structures are extracted； lastly， eigenvector is produced and the similarity can get calculated. The experimental result shows that the new method is 10.6 percent more precise than those of calculating the Longest Common Subsequence.

Key words： attribute counting； structure measurement； similarity measurement

在程序設(shè)計(jì)課程教學(xué)中，尤其是在上機(jī)編程訓(xùn)練過(guò)程中，需要學(xué)生通過(guò)獨(dú)立地編程練習(xí)來(lái)提高程序設(shè)計(jì)能力，然而實(shí)際的情況是部分學(xué)生存在不同程度地抄襲他人的作業(yè)。在這種情況下，教師要批閱學(xué)生的作業(yè)，同時(shí)要甄別抄襲程度，通過(guò)手工操作很難準(zhǔn)確完成。因此，在程序設(shè)計(jì)類課程中，要甄別學(xué)生作業(yè)是否抄襲采用計(jì)算機(jī)自動(dòng)度量的辦法，具有很重要的現(xiàn)實(shí)意義。

早在二十世紀(jì)七十年代時(shí)，Ottenstein[1]就已經(jīng)是開始使用屬性計(jì)數(shù)法，通過(guò)其對(duì)抄襲檢測(cè)系統(tǒng)的使用，人們對(duì)于屬性計(jì)數(shù)法的重視程度不斷提高。設(shè)計(jì)的抄襲檢測(cè)系統(tǒng)使用了Halstead提出的屬性計(jì)數(shù)法，該系統(tǒng)應(yīng)用于FORTRAN語(yǔ)言源程序的相似度檢測(cè)；利用屬性計(jì)數(shù)技術(shù)設(shè)計(jì)的相似度檢測(cè)系統(tǒng)沒(méi)有考慮程序的結(jié)構(gòu)信息，導(dǎo)致誤判率較高。而結(jié)構(gòu)度量技術(shù)克服了屬性計(jì)數(shù)法帶來(lái)的一些問(wèn)題，因此在實(shí)際過(guò)程中應(yīng)用比較廣泛，如：Sim、JPag、YAP3[2，3]、和MOSS[4]等。從國(guó)內(nèi)外的研究現(xiàn)狀可以發(fā)現(xiàn)，國(guó)內(nèi)對(duì)于相似度檢測(cè)的起步晚、研究少，且絕大多數(shù)的重點(diǎn)在中文分詞和語(yǔ)義的研究上，應(yīng)用于論文抄襲檢測(cè)。國(guó)外的抄襲檢測(cè)系統(tǒng)較多且比較成熟，可是大多數(shù)研究匯集在文本轉(zhuǎn)換和串匹配算法方面。源程序的抄襲和一般的文本抄襲有差異，不同結(jié)構(gòu)的代碼可以實(shí)現(xiàn)相同的功能。一些學(xué)生為了躲避抄襲檢測(cè)，采用比較高級(jí)的抄襲方法，如添加冗余代碼、控制結(jié)構(gòu)等價(jià)變換等，即源代碼中的部分內(nèi)容用等價(jià)功能的語(yǔ)句進(jìn)行替換，如將if語(yǔ)句修改成switch語(yǔ)句，將while循環(huán)語(yǔ)句改為for循環(huán)等，這樣修改會(huì)降低串匹配算法的有效性。

針對(duì)于上述問(wèn)題的存在，本文在對(duì)集中相似性檢測(cè)方法進(jìn)行了研究，并在研究的基礎(chǔ)上提出一種能夠有效改進(jìn)這些方法，并且可以實(shí)現(xiàn)檢測(cè)效能的方法。

1 相關(guān)研究

當(dāng)前，對(duì)于相似度度量技術(shù)的使用中，主要是形成了兩種度量技術(shù)，一種是屬性計(jì)數(shù)法，另外一種是機(jī)構(gòu)度量技術(shù)，這兩種方法各有特色，在相似度檢測(cè)中發(fā)揮了巨大的功能。

1）屬性計(jì)數(shù)法

屬性計(jì)數(shù)法是Halstead提出的軟件科學(xué)度量方法。在屬性計(jì)數(shù)法的使用中，主要是設(shè)計(jì)到幾個(gè)數(shù)值的表示。首先是表示所用到的操作符的種類數(shù)，這個(gè)是用[η1]進(jìn)行表示，對(duì)于用到的操作數(shù)的種類數(shù)就是利用[η2]表示。值得注意的是，在這個(gè)過(guò)程中對(duì)于操作符的總數(shù)和操作數(shù)的總數(shù)也是需要進(jìn)行計(jì)數(shù)，分別是用[N1]，[N2]進(jìn)行表示。對(duì)于代碼的總行數(shù)來(lái)說(shuō)，在公式計(jì)算的過(guò)程中，是用L進(jìn)行表示。

該方法的缺點(diǎn)是若是抄襲者插入一些不相關(guān)的關(guān)鍵字、變量、完全無(wú)關(guān)的函數(shù)，該算法便很難檢測(cè)，而對(duì)于不屬于抄襲的源代碼，因?yàn)閷傩詡€(gè)數(shù)相近，可能會(huì)產(chǎn)生較大的誤判概率。

屬性計(jì)數(shù)法拋棄了絕大多數(shù)的程序結(jié)構(gòu)信息，而結(jié)構(gòu)度量技術(shù)恰恰彌補(bǔ)了屬性計(jì)數(shù)法的這一缺陷。

2）結(jié)構(gòu)度量技術(shù)

結(jié)構(gòu)度量技術(shù)對(duì)于程序之間的相似度的檢驗(yàn)，主要是通過(guò)分析其程序的特征結(jié)構(gòu)來(lái)進(jìn)行度量。具體來(lái)說(shuō)，結(jié)構(gòu)度量技術(shù)主要是通過(guò)分析各個(gè)程序中嵌套深度、控制結(jié)構(gòu)的內(nèi)容等之間存在的不同分析相似性的高低。在該方法操作的過(guò)程中，第一步就是對(duì)程序的結(jié)構(gòu)進(jìn)行分析，這是整個(gè)操作中最為重要的步驟，不僅如此，在分析的過(guò)程中，還要保證能夠?qū)⒊绦蛘Z(yǔ)言中的元素特點(diǎn)進(jìn)行轉(zhuǎn)換，主要是轉(zhuǎn)換成標(biāo)記序列。經(jīng)過(guò)一系列的操作，兩個(gè)程序就的長(zhǎng)度逐漸縮小，并且?guī)缀蹙褪且宰址男问酱嬖冢@樣，就能夠?qū)ζ渲兴惴ㄝ^少的字符串進(jìn)行相似度的比較，并且可以根據(jù)比較的結(jié)果得出兩個(gè)程序之間相似的程度，這個(gè)方法較為可靠，獲得結(jié)果也是比較有典型性。

代碼相似度度量技術(shù)各有優(yōu)缺點(diǎn)，屬性計(jì)數(shù)算法運(yùn)行時(shí)間復(fù)雜度較低，但其拋棄太多程序結(jié)構(gòu)信息，其性能較低；而結(jié)構(gòu)度量技術(shù)檢測(cè)源代碼性能較高，但是時(shí)間復(fù)雜度也較高。因此，本文旨在探索一種綜合屬性計(jì)數(shù)和結(jié)構(gòu)度量技術(shù)優(yōu)點(diǎn)而時(shí)間復(fù)雜度相對(duì)較低的相似度計(jì)算方法。

2 基于程序結(jié)構(gòu)度量的常見相似度計(jì)算方法

對(duì)于程序結(jié)構(gòu)度量相似度的算法，主要是通過(guò)對(duì)于程序的結(jié)構(gòu)信息、執(zhí)行的流程判定程序等進(jìn)行分析，并在比較分析的基礎(chǔ)上得出其相似度的判定結(jié)論。當(dāng)前，在結(jié)構(gòu)度量技術(shù)中比較常用的方法，首先就是Levenshtein距離，其次還有最長(zhǎng)公共子序列和串的散列值匹配算法等，這些方法在使用的過(guò)程中各有特色，本文會(huì)對(duì)其進(jìn)行一一介紹。

2.1 Levenshtein距離

Levenshtein距離又稱為編輯距離（ED：Edit Distance），是俄國(guó)科學(xué)家Vladimir Levenshtein在二十世紀(jì)六十年代中提出來(lái)的一種相似度比較算法。在這個(gè)算法中，主要是通過(guò)比較最少編輯次數(shù)確定其相似程度。具體來(lái)說(shuō)，是將需要對(duì)比的兩個(gè)字符串進(jìn)行轉(zhuǎn)換，也就是將其中的一組字符串經(jīng)過(guò)一系列的編輯轉(zhuǎn)換成另外一個(gè)字符串。包括對(duì)于這個(gè)字符串進(jìn)行的插入、替換以及刪除等編輯操作，保證經(jīng)過(guò)編輯之后，兩個(gè)字符串之間沒(méi)有差別。如果使用的編輯次數(shù)較少就可以實(shí)現(xiàn)將一個(gè)字符串轉(zhuǎn)換成另一個(gè)，那么兩者之間的相似性程度就是比較高[5]。Levenshtein距離可用如下算法求得：設(shè)對(duì)于待檢測(cè)源碼字符串串[S，T]的編輯距離為[D（|S|，|T|）]，其編輯距離相似度[sim（S，T）]計(jì)算公式是：

2.2 最長(zhǎng)公共子序列

最長(zhǎng)公共子序列（Longest Common Subsequence，LCS）[6]方法主要是通過(guò)對(duì)于進(jìn)行相似度檢測(cè)的兩個(gè)字符串進(jìn)行刪除操作，在操作的過(guò)程中對(duì)于字符的順序不改變，經(jīng)過(guò)一系列的刪除之后，獲得其中字符長(zhǎng)度最長(zhǎng)的字符序列，并對(duì)其進(jìn)行比較。如果源程序的字符串中存在的最長(zhǎng)公共子序列長(zhǎng)度愈長(zhǎng)，那就說(shuō)明兩個(gè)字符串之間的相似程度越高。

G.Whale基于最長(zhǎng)公共子序列算法對(duì)源代碼進(jìn)行了相似度比較，開發(fā)了Plague系統(tǒng)，實(shí)現(xiàn)了程序的自動(dòng)抄襲檢測(cè)。

參考文獻(xiàn)：

[1] Ottenstein K J. An Algorithmic Approach to the Detection and Prevention of plagiarism[J]. CSD-TR200， 1976，103（2）.

[2] Michael J.Wise. YAP3：Improved Detection of Similarities in Computer Program and other Texts[J] . Department of Computer Science， University of Sydney， 2003， 10（3）.

[3] Wise. M. J. Detectiom of similarities in student programs. SIGSCI Technical Symposium， Kansas City， USA， 1992.

[4] Clough. P. Plagiarism in natural and programming languages：An overview of current tools and technologies. Research Memoranda：CS-00-05， Deoartment of Computer Sicencce， University of Sheffield， 2000.

[5] 鄭凱，歐陽(yáng)林艷，林強(qiáng)，等.LCS算法與編輯距離算法的研究[J].信息通信，2015，31（5）.

[6] 古平，張鋒，周海濤.一種程序源代碼相似度度量方法[J].計(jì)算機(jī)工程，2012，38（6）.