肖崇星，李 郴，曹曉灑

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

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

肖崇星，李 郴，曹曉灑

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

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

敵對(duì)題；代碼相似性檢測(cè)；抽象語(yǔ)法樹(shù)

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

1 敵對(duì)題問(wèn)題簡(jiǎn)述

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

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

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

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

2 程序代碼相似性檢測(cè)常用算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

其主要流程如圖1所示。

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

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

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

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

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

（3）在保證語(yǔ)義的情況下，對(duì)能等價(jià)替換的語(yǔ)句進(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 語(yǔ)法樹(shù)結(jié)點(diǎn)的選擇和生成

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

3.3 特征向量提取及頻度計(jì)算

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

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

3.4 相似度的計(jì)算

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

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

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

3.5 判斷是否為敵對(duì)題

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

4 結(jié)語(yǔ)

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

[1]陳蕾.基于遺傳算法的自動(dòng)組卷系統(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]胡正軍.程序代碼相似度檢測(cè)方法研究與應(yīng)用[D].長(zhǎng)沙：中南大學(xué)，2012.

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

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

[6]汪忠國(guó)，吳敏.基于向量空間模型的題庫(kù)相似度檢查算法[J].計(jì)算機(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ù)挖掘。