肖崇星，李 郴，曹曉灑

（中國礦業(yè)大學(xué)（北京） 機電與信息工程學(xué)院，北京 100083）

基于代碼相似性算法的敵對題發(fā)現(xiàn)問題研究

肖崇星，李 郴，曹曉灑

（中國礦業(yè)大學(xué)（北京） 機電與信息工程學(xué)院，北京 100083）

試卷中可能出現(xiàn)的敵對題問題，是影響試卷質(zhì)量的一個重要因素，針對這一問題，文章在分析了C語言試卷中讀程序題和編程題的特點及研究了常用程序代碼相似性檢測算法的基礎(chǔ)上，給出了一種基于抽象語法樹的敵對題發(fā)現(xiàn)算法，希望能較好地解決C語言自動組卷系統(tǒng)中出現(xiàn)的敵對題問題，從而進(jìn)一步提高C語言自動組卷系統(tǒng)的組卷質(zhì)量。

敵對題；代碼相似性檢測；抽象語法樹

伴隨著互聯(lián)網(wǎng)和計算機新技術(shù)的發(fā)展，越來越多的教學(xué)環(huán)節(jié)向電子化和網(wǎng)絡(luò)化轉(zhuǎn)變，其中傳統(tǒng)的手工出卷方式變成利用計算機技術(shù)自動生成試卷就是一個普遍的現(xiàn)象[1]。利用計算機組卷不僅減少了教師的工作量，而且提高了試卷評判環(huán)節(jié)的公平性。因此自動組卷系統(tǒng)目前已成為評價計算機教育資源管理系統(tǒng)好壞的重要標(biāo)志，然而在組卷系統(tǒng)生成的試卷中，有時會發(fā)生敵對題問題，敵對題問題也叫“相互提示”問題，就是同一套試卷中若出現(xiàn)某一道試題的題目對另一道試題要求做答的答案產(chǎn)生提示性作用，就認(rèn)為這套試卷中出現(xiàn)了敵對題的問題。針對上述問題，本文提出了基于抽象語法樹的敵對題發(fā)現(xiàn)算法，希望能較好地處理C語言試卷中讀程序題與編程題易出現(xiàn)敵對題的問題。

1 敵對題問題簡述

敵對題問題是伴隨著試卷的產(chǎn)生而出現(xiàn)的，前期人工組卷時可以人為盡量避免敵對題的出現(xiàn)，但隨著計算機組卷逐漸代替人工組卷后，較多組卷算法對敵對題問題解決得不是很好，敵對題問題在試卷中出現(xiàn)的概率較高，并且由于組卷算法在其他方面的不斷優(yōu)化改進(jìn)，使其在解決組卷過程中的其他問題比如知識點均勻分布，重難點分布等的效果有較大提高，從而使敵對題問題與組卷質(zhì)量之間的矛盾日趨明顯。

敵對題是組卷系統(tǒng)在組卷后期產(chǎn)生的一個問題，其特點如下：

（1）同一份試卷中一道試題的題目和另外一道試題的答案相似或者相同。

（2）同一份試卷中一道試題的題目內(nèi)容對另外一道試題的答案產(chǎn)生了功能性的提示作用。

2 程序代碼相似性檢測常用算法

目前對于程序代碼相似性的檢測算法主要有基于屬性計數(shù)的相似性檢測算法和基于結(jié)構(gòu)度量的相似性檢測算法以及這兩種相似性檢測算法相結(jié)合的檢測算法[2]。本章研究程序代碼相似性檢測算法，目的在于對C語言自動組卷系統(tǒng)生成的試卷中讀程序題的代碼與編程題的答案代碼進(jìn)行相似性分析，以檢出試卷中可能出現(xiàn)的敵對題。

2.1 基于屬性計數(shù)的相似性檢測算法

基于屬性計數(shù)的檢測方法主要是從源代碼中抽取出各種度量元素，如關(guān)鍵字、操作符數(shù)、循環(huán)數(shù)等，不考慮程序的內(nèi)部結(jié)構(gòu)。HALSTEAD提出的軟件科學(xué)度量方法是最早和最典型的屬性計數(shù)法，它從程序中提取出數(shù)個軟件度量特征，并使用這些特征來比較程序，其提出的屬性計數(shù)法中統(tǒng)計如下4個屬性。

N1=所有操作符的總數(shù)；N2=所有操作數(shù)的總數(shù)；n1=操作符的種類數(shù)；n2=操作數(shù)的種類數(shù)。則定義程序的長度為N=N1+N2和詞匯量n=n1+n2，在此基礎(chǔ)上得到程序的容量V如下：V=Nlog2（n）。

最后得到HALSTEAD特征向量，即H（n，N，V）。通過計算2個特征向量的歐幾里得距離即可獲得其相似度。計算公式如下：D=sqrt（（n1-n2）2+（N1-N2）2+（V1-V0）2）。

歐幾里得距離越大，表明要比較程序之間的差別性越大，反之則表明程序之間差別性越小，2個相同程序的相似度為0。

2.2 基于結(jié)構(gòu)度量的相似性檢測算法

因為屬性計數(shù)法中比對結(jié)果的抽象，不能得到具體的相似地方，而且它沒有考慮程序的結(jié)構(gòu)內(nèi)信息，若是改變了源程序的結(jié)構(gòu)，這種程序比對方式的效率就會低下。而基于結(jié)構(gòu)度量的相似性比對方法則要對程序的內(nèi)部結(jié)構(gòu)進(jìn)行檢測分析，如分析程序的控制結(jié)構(gòu)、計算程序代碼的嵌套深度、查找程序間數(shù)據(jù)的依賴情況等，之后通過文本分析，將程序代碼處理成標(biāo)記串。最后，相應(yīng)的程序代碼將變成一個字符串，之后采用串匹配算法比對得到的字符串，再依據(jù)比對的結(jié)果來決定要比對的程序是否相似。

2.3 基于屬性計數(shù)的相似性檢測算法與基于結(jié)構(gòu)度量的相似性檢測算法的結(jié)合

隨著對相似性代碼檢測算法研究的不斷深入，一些學(xué)者提出了將上述兩種算法相結(jié)合的方法，并相繼開發(fā)出了一些系統(tǒng)，比如Donaldson開發(fā)的相似性度量系統(tǒng)，但是兩種相似性檢測算法相結(jié)合的技術(shù)，最后階段的相似性計算大多還是利用結(jié)構(gòu)度量檢測算法中串的比較方法或者是對它的改進(jìn)方法，比如胡正軍[3]、張麗萍等[4]用貪婪式字符串匹配算法來計算字符串之間的相似性問題，張鵬[5]采用的是最長公共子序列法等，從而時間或空間的開銷相對也較大。

綜上所述，基于屬性計數(shù)的檢測方法因為沒有考慮到程序的結(jié)構(gòu)內(nèi)部信息，而使檢測算法的效果相對較低。而基于結(jié)構(gòu)度量的相似性檢測方法和兩種算法相結(jié)合的方法都要對程序的內(nèi)部結(jié)構(gòu)進(jìn)行分析比對，將程序轉(zhuǎn)換成標(biāo)記串，然后按照串匹配的算法比對這些標(biāo)記串，雖然相對提高了程序比對的精確度，但由于它們很大一部分是利用字符串匹配算法來計算源代碼標(biāo)準(zhǔn)化產(chǎn)生的標(biāo)記串的相似度，從而增加了空間和時間的開銷。

針對上述情況，本文提出了一種基于抽象語法樹的敵對題發(fā)現(xiàn)算法，其主要思想是在結(jié)構(gòu)度量的相似性檢測算法程序標(biāo)準(zhǔn)化步驟中采用抽象語法樹作為程序的中間表示形式，將源代碼進(jìn)行轉(zhuǎn)換，之后引入了空間向量模型[6]的思想，求其待比較程序的抽象語法樹屬性，最后采用編碼理論中的漢明距離概念，由漢明距離編輯公式，獲得一種新的計算代碼相似性方法。

3 發(fā)現(xiàn)敵對題的設(shè)計策略

在C語言試卷發(fā)現(xiàn)敵對題的過程中，首先是把需要比對的試題程序代碼進(jìn)行語法分析而獲得其相應(yīng)的語法樹，對獲得的源程序的語法樹結(jié)點進(jìn)行分類統(tǒng)計計算，根據(jù)二進(jìn)制邏輯加法運算統(tǒng)計語法樹的結(jié)點屬性向量，之后求取兩個向量的漢明距離，最后通過漢明距離值/n與預(yù)設(shè)閾值的比較判定同一套試卷中讀程序題的代碼是否與編程題的答案代碼相似。如果兩個向量的漢明距離值/n大于預(yù)設(shè)閾值時，就認(rèn)為這兩道試題是敵對題的可能性較大。

其主要流程如圖1所示。

圖1 敵對題發(fā)現(xiàn)流程

3.1 程序代碼預(yù)操作

預(yù)操作部分是指待檢測程序文本在生成抽象語法樹之前，對程序源代碼進(jìn)行去噪和等價結(jié)構(gòu)的一致化。去噪是指將源程序代碼去除掉所有的注釋部分和程序代碼中空的行，將多個連續(xù)的空格變成一個空格，等價結(jié)構(gòu)的一致化是指將語義上等價的語句進(jìn)行相關(guān)的統(tǒng)一化。針對C語言為例，其主要有以下幾個方面：

（1）去掉程序中所有在符號“//”之后，“/* */”之間的程序注釋內(nèi)容。

（2）去除掉程序中存在的空行并將多個連續(xù)的空格變成一個空格。

（3）在保證語義的情況下，對能等價替換的語句進(jìn)行統(tǒng)一化處理，如將i++和++i等替換為同一種形式等。

（4）將do-while和for這種功能相似的結(jié)構(gòu)轉(zhuǎn)換成同一種循環(huán)結(jié)構(gòu)，switch-case結(jié)構(gòu)轉(zhuǎn)換成if-else判斷結(jié)構(gòu)等。

3.2 語法樹結(jié)點的選擇和生成

抽象語法樹中的結(jié)點也就是后期程序的特征屬性，這里我們可以選擇以下結(jié)點[聲明變量，常量，標(biāo)識符，表達(dá)式語句，條件語句，循環(huán)結(jié)構(gòu),結(jié)構(gòu)體及其數(shù)組，過程及函數(shù)等]來表示語法樹的每個結(jié)點，父類結(jié)點的屬性向量是其全部子類結(jié)點的屬性向量的邏輯加法運算和。

3.3 特征向量提取及頻度計算

在得到相應(yīng)試題程序的抽象語法樹后，就要針對相應(yīng)的文件來提取里面的結(jié)構(gòu)信息。這里是從該語法樹中提取其相應(yīng)的結(jié)點作為其特征向量屬性，其結(jié)點為[聲明變量，常量，標(biāo)識符，表達(dá)式語句，條件語句，循環(huán)結(jié)構(gòu),結(jié)構(gòu)體及其數(shù)組，過程及函數(shù)等]，得到如下兩個特征向量。

表示待檢查試題程序p和已有試題程序d的特征屬性向量，其中wk和qk的值為0或1，0表示程序在這分量位置上的屬性是沒有的，1表示程序在這分量位置上的屬性是有的，反之也可以類似決定。

3.4 相似度的計算

得到要比較代碼的特征向量后，需要進(jìn)行相似度的計算，在計算階段采用漢明距離的計算公式，經(jīng)過上一步得到相應(yīng)語法樹的特征向量如下，只是wk和qk的值為0或1。

和qk分別表示讀程序題對應(yīng)的特征向量p和編程題的答案對應(yīng)的特征向量d中第k位的屬性分量，要么為1，要么為0，⊕就是模2加運算。對于計算機中，模2加運算非常方便，運算速度非?？?，時間復(fù)雜度有明顯的降低。

用上述公式計算程序代碼相似度是準(zhǔn)確的，因為，它計算得出的數(shù)值在0～1之間，當(dāng)兩段程序代碼完全相似時，sim(p,d)的值為1，當(dāng)兩段代碼完全不相似時，sim(p,d)的值為0，準(zhǔn)確地呈現(xiàn)出程序代碼之間的區(qū)別，并且也同向量夾角余弦的計算原理相同。由此計算兩段程序的抽象語法樹相似度就可判斷兩段程序是否相似，若計算結(jié)果大于預(yù)設(shè)閾值，則認(rèn)為這兩段程序相似性的概率大。

3.5 判斷是否為敵對題

根據(jù)得到的值來與相應(yīng)的閾值進(jìn)行比較，若結(jié)果大于等于預(yù)設(shè)閾值，則可以認(rèn)為試卷中這兩道試題是敵對題的可能性比較大，結(jié)合敵對題的另一個特點，分析其編程題的代碼結(jié)構(gòu)，從中提取出功能語句，與讀程序題得到的功能語句進(jìn)行比對得到一個值，最后對其兩個值求其期望值，若最后的值大于等于閾值，就可認(rèn)為其為敵對題，之后就需要替換試卷中的一道試題，以保證組卷質(zhì)量。

4 結(jié)語

本文以組卷系統(tǒng)在生成的試卷中易出現(xiàn)敵對題問題為出發(fā)點，針對C語言自動組卷系統(tǒng)在組卷后期讀程序題和編程題較易出現(xiàn)相互敵對的問題進(jìn)行分析研究，設(shè)計了一個基于抽象語法樹的敵對題判斷模型，目的在于檢出C語言試卷中的敵對題，從而提高C語言自動組卷系統(tǒng)的組卷質(zhì)量。

[1]陳蕾.基于遺傳算法的自動組卷系統(tǒng)研究與應(yīng)用[D].成都：四川大學(xué)，2006.

[2]BAKER B S，GIANCARLO R. Sparse Dynamic Programming for Longest Common Subsequence from Fragments[J].Algorithms，2002（2）：231-254.

[3]胡正軍.程序代碼相似度檢測方法研究與應(yīng)用[D].長沙：中南大學(xué)，2012.

[4]張麗萍，劉東升，李彥臣，等.一種基于AST的代碼抄襲檢測方法[J].計算機應(yīng)用研究，2011（12）：4616-4620.

[5]張鵬.C程序相似代碼識別方法的研究與實現(xiàn)[D].大連：大連理工大學(xué)，2007.

[6]汪忠國，吳敏.基于向量空間模型的題庫相似度檢查算法[J].計算機系統(tǒng)應(yīng)用，2010（3）：213-216.

Research on hostile problem detection based on code similarity algorithm

Xiao Chongxing, Li Chen, Cao Xiaosa
（Mechatronics and Information Engineering College of China University of Mining and Technology, Beijing 100083, China）

Hostile questions may appear in the test, which is one of the important factors affecting the quality of test paper, aiming at this problem, based on analyzing the characteristics of reading questions and programming questions C language test and researching the commonly used code detection based similarity algorithm, this paper gave an algorithm for discovering hostile items based on abstract syntax tree, in order to solve the problem of C hostile language automatic test system of the test paper, so as to further improve the quality of the C language automatic test system.

hostile question; code similarity detection; abstract syntax tree

肖崇星（1990—），男，河南駐馬店，碩士研究生；研究方向：數(shù)據(jù)挖掘。