基于代碼相似性算法的敵對題發現問題研究

肖崇星，李 郴，曹曉灑

（中國礦業大學（北京） 機電與信息工程學院，北京 100083）

基于代碼相似性算法的敵對題發現問題研究

肖崇星，李 郴，曹曉灑

（中國礦業大學（北京） 機電與信息工程學院，北京 100083）

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

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

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

1 敵對題問題簡述

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

敵對題是組卷系統在組卷后期產生的一個問題，其特點如下：

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

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

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

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

2.1 基于屬性計數的相似性檢測算法

基于屬性計數的檢測方法主要是從源代碼中抽取出各種度量元素，如關鍵字、操作符數、循環數等，不考慮程序的內部結構。HALSTEAD提出的軟件科學度量方法是最早和最典型的屬性計數法，它從程序中提取出數個軟件度量特征，并使用這些特征來比較程序，其提出的屬性計數法中統計如下4個屬性。

N1=所有操作符的總數；N2=所有操作數的總數；n1=操作符的種類數；n2=操作數的種類數。則定義程序的長度為N=N1+N2和詞匯量n=n1+n2，在此基礎上得到程序的容量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 基于結構度量的相似性檢測算法

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

2.3 基于屬性計數的相似性檢測算法與基于結構度量的相似性檢測算法的結合

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

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

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

3 發現敵對題的設計策略

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

其主要流程如圖1所示。

圖1 敵對題發現流程

3.1 程序代碼預操作

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

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

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

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

（4）將do-while和for這種功能相似的結構轉換成同一種循環結構，switch-case結構轉換成if-else判斷結構等。

3.2 語法樹結點的選擇和生成

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

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

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

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

3.4 相似度的計算

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

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

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

3.5 判斷是否為敵對題

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

4 結語

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

[1]陳蕾.基于遺傳算法的自動組卷系統研究與應用[D].成都：四川大學，2006.

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

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

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

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

[6]汪忠國，吳敏.基于向量空間模型的題庫相似度檢查算法[J].計算機系統應用，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—），男，河南駐馬店，碩士研究生；研究方向：數據挖掘。