基于動(dòng)態(tài)檢測(cè)與靜態(tài)分析的自動(dòng)評(píng)分方法研究

薛 斌，胡建鵬

（上海工程技術(shù)大學(xué) 電子電氣工程學(xué)院，上海 201620）

0 引言

C 語(yǔ)言是高校中工科專業(yè)的必修基礎(chǔ)課程，也是國(guó)際上廣為流行的高級(jí)程序設(shè)計(jì)語(yǔ)言。在C 語(yǔ)言程序設(shè)計(jì)課程中，考核學(xué)生知識(shí)掌握程度的重要手段之一就是對(duì)編程能力的考察，學(xué)生只有通過(guò)大量的上機(jī)代碼實(shí)踐，才能更好地理解C 語(yǔ)言程序的精髓。目前，高校普遍采用線上系統(tǒng)對(duì)C 語(yǔ)言編程題進(jìn)行上機(jī)考試，但此類系統(tǒng)大多僅有通過(guò)與錯(cuò)誤兩種運(yùn)行結(jié)果。只關(guān)注程序運(yùn)行的結(jié)果，而忽視程序本身，這既不能合理地考察學(xué)生對(duì)知識(shí)的掌握程度，也不能讓學(xué)生得到及時(shí)有效的反饋。為了對(duì)運(yùn)行結(jié)果異常以及不能運(yùn)行的學(xué)生程序進(jìn)行評(píng)分，教師仍需要把學(xué)生編寫的答案打印出來(lái)，進(jìn)行人工評(píng)分，不僅效率低下，而且評(píng)分結(jié)果可能會(huì)受到閱卷老師的主觀因素影響。

本文結(jié)合動(dòng)態(tài)檢測(cè)與靜態(tài)分析策略，設(shè)計(jì)了一種新型的C 語(yǔ)言自動(dòng)評(píng)分方法，并將該方法融合到線上實(shí)驗(yàn)系統(tǒng)中。首先，進(jìn)行動(dòng)態(tài)檢測(cè)，利用KMP算法執(zhí)行關(guān)鍵字匹配，若匹配相似度落入預(yù)期值區(qū)間，再將學(xué)生程序代碼轉(zhuǎn)換為可執(zhí)行文件，通過(guò)預(yù)先設(shè)置的測(cè)試用例來(lái)驅(qū)動(dòng)評(píng)分。若關(guān)鍵字匹配未通過(guò)、程序無(wú)法運(yùn)行以及運(yùn)行期間出現(xiàn)異常，則進(jìn)行靜態(tài)分析，對(duì)學(xué)生源程序代碼和模板程序代碼進(jìn)行標(biāo)準(zhǔn)化，通過(guò)控制結(jié)構(gòu)子樹的匹配相似度來(lái)綜合評(píng)分。

1 動(dòng)態(tài)檢測(cè)方案設(shè)計(jì)

基于動(dòng)態(tài)檢測(cè)的自動(dòng)評(píng)分方法屬于軟件自動(dòng)化測(cè)試方法［1］，其核心的檢測(cè)步驟如下：預(yù)先設(shè)置好測(cè)試用例作為輸入數(shù)據(jù)；把源程序轉(zhuǎn)換為可執(zhí)行文件并運(yùn)行；通過(guò)判斷期望值與輸出數(shù)據(jù)是否相等來(lái)進(jìn)行自動(dòng)評(píng)分。但是對(duì)于某些編程題來(lái)說(shuō)，學(xué)生可以對(duì)照測(cè)試用例來(lái)編寫代碼，以達(dá)到欺騙系統(tǒng)并獲取得分的目的。為了杜絕此類狀況，并減少系統(tǒng)無(wú)效運(yùn)行的次數(shù)，本系統(tǒng)在執(zhí)行動(dòng)態(tài)檢測(cè)時(shí)，首先會(huì)通過(guò)Knuth－Morri－Pratt［2］（簡(jiǎn)稱KMP）算法進(jìn)行關(guān)鍵字的匹配，當(dāng)整體匹配相似度落入預(yù)期值區(qū)間時(shí)，便執(zhí)行后續(xù)步驟，否則轉(zhuǎn)入靜態(tài)檢測(cè)流程［3］。

1.1 基于KMP 算法的關(guān)鍵字檢測(cè)

本系統(tǒng)主要針對(duì)非計(jì)算機(jī)專業(yè)的學(xué)生群體，編程考題相對(duì)簡(jiǎn)單，而且很多C 語(yǔ)言關(guān)鍵字也不在教學(xué)使用范圍內(nèi)，如register、auto、volatile，故本文在原有關(guān)鍵字范圍基礎(chǔ)上做一些刪減，并增加了有利于考察代碼邏輯的特征詞，如stdio.h、stdlib.h、sqrt（）、abs（）等。針對(duì)關(guān)鍵字檢測(cè)的操作步驟如下：

（1）從頭至尾掃描程序代碼，刪掉代碼中所有的空格、空行以及注釋；

（2）對(duì)學(xué)生源程序進(jìn)行詞法分析，檢查程序的token 流，剔除掉所有的變量與自定義的函數(shù)名，剩下的即為C 語(yǔ)言關(guān)鍵字所組成的字符串，把這些字符串作為關(guān)鍵字匹配的特征字符串；

（3）利用KMP 算法對(duì)源程序模式串和預(yù)設(shè)的主特征字符串進(jìn)行匹配并記錄匹配結(jié)果，最終計(jì)算出整體的相似度。

1.2 動(dòng)態(tài)檢測(cè)執(zhí)行

基于動(dòng)態(tài)檢測(cè)的評(píng)分方法主要解決的問(wèn)題包括：設(shè)置合理的測(cè)試用例，盡可能完整地覆蓋代碼的執(zhí)行路徑；配置系統(tǒng)程序的沙盒安全保護(hù)機(jī)制；檢測(cè)數(shù)據(jù)結(jié)果的分析。動(dòng)態(tài)檢測(cè)的整體步驟如下：

（1）關(guān)鍵字匹配：使用KMP 算法對(duì)源程序與模板程序中的關(guān)鍵字進(jìn)行匹配操作；

（2）預(yù)處理：讀取系統(tǒng)配置文件、讀取編程題目信息以及測(cè)試用例數(shù)據(jù)；

（3）編譯：對(duì)程序進(jìn)行編譯并檢查語(yǔ)法，以生成可執(zhí)行程序；

（4）執(zhí)行：運(yùn)行程序，依次輸入全部測(cè)試數(shù)據(jù)，監(jiān)控代碼的執(zhí)行狀態(tài)；

（5）測(cè)試：獲取學(xué)生程序的執(zhí)行結(jié)果，包括正常執(zhí)行的輸出結(jié)果或程序異常結(jié)束的結(jié)果，若正常執(zhí)行并退出，則將程序的輸出數(shù)據(jù)與模板的標(biāo)準(zhǔn)數(shù)據(jù)進(jìn)行對(duì)比并評(píng)定分?jǐn)?shù)?；趧?dòng)態(tài)檢測(cè)的自動(dòng)評(píng)分模型如圖1 所示。

圖1 動(dòng)態(tài)檢測(cè)評(píng)分模型Fig.1 Dynamic detection scoring model

2 靜態(tài)分析方案設(shè)計(jì)

通過(guò)對(duì)程序進(jìn)行詞法分析、語(yǔ)法分析等預(yù)處理操作，輸出程序的中間轉(zhuǎn)換形式——抽象語(yǔ)法樹（Abstract Syntax Tree，AST）［3］，繼而模擬人工評(píng)分的思路：

（1）首先在組建編程題庫(kù)時(shí)對(duì)每道題目提供得分點(diǎn)，本文選取控制結(jié)構(gòu)作為靜態(tài)評(píng)分的關(guān)鍵因素；

（2）對(duì)抽象語(yǔ)法樹進(jìn)行標(biāo)準(zhǔn)化處理，以消除程序語(yǔ)義的多樣性，減少答案模板的數(shù)量，然后根據(jù)AST 中結(jié)點(diǎn)的類型提取出對(duì)應(yīng)的控制結(jié)構(gòu)子樹；

（3）利用基于結(jié)點(diǎn)權(quán)值的樹編輯距離算法來(lái)匹配標(biāo)準(zhǔn)化后的源程序與模板程序的控制結(jié)構(gòu)子樹，并計(jì)算其相似度［4］；求解控制結(jié)構(gòu)各個(gè)模塊的得分值（模塊的預(yù)設(shè)總分值乘以對(duì)應(yīng)模塊的相似度）；最后，綜合各模塊的評(píng)分結(jié)果求和并得出靜態(tài)分析的最終評(píng)分結(jié)果。

2.1 程序標(biāo)準(zhǔn)化

抽象語(yǔ)法樹作為一種數(shù)據(jù)載體，不僅包含了源程序?qū)?yīng)結(jié)點(diǎn)的所有信息，還包括了結(jié)點(diǎn)之間的結(jié)構(gòu)關(guān)系。針對(duì)抽象語(yǔ)法樹進(jìn)行標(biāo)準(zhǔn)化，包含兩個(gè)部分：

（1）利用基于關(guān)鍵詞Trie 樹的GCC 抽象語(yǔ)法樹消除冗余算法，對(duì)抽象語(yǔ)法樹進(jìn)行冗余優(yōu)化處理［5］，冗余優(yōu)化示意如圖2 所示；

圖2 冗余優(yōu)化整體示意圖Fig.2 Overall schematic of redundancy optimization

（2）通過(guò)對(duì)程序運(yùn)用一系列標(biāo)準(zhǔn)化規(guī)則，在抽象語(yǔ)法樹的基礎(chǔ)上，將不同表現(xiàn)形式的程序語(yǔ)法樹轉(zhuǎn)換成統(tǒng)一的表現(xiàn)形式，這樣不僅可以消除學(xué)生源程序代碼的多樣性、減少標(biāo)準(zhǔn)答案模板的數(shù)量，還能提高相似度匹配的準(zhǔn)確率。

為了后續(xù)更好地實(shí)現(xiàn)程序控制結(jié)構(gòu)的相似度匹配，本文在程序標(biāo)準(zhǔn)化環(huán)節(jié)主要對(duì)程序控制結(jié)構(gòu)進(jìn)行標(biāo)準(zhǔn)化轉(zhuǎn)換。在C 語(yǔ)言中有3 種基本的控制結(jié)構(gòu)：順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)。每一種控制結(jié)構(gòu)都可能有多種代碼書寫形式，這為源程序和模板程序的匹配帶來(lái)困難，所以需要對(duì)控制結(jié)構(gòu)進(jìn)行標(biāo)準(zhǔn)化。

2.1.1 選擇結(jié)構(gòu)的標(biāo)準(zhǔn)化

實(shí)現(xiàn)選擇結(jié)構(gòu)可采用if 語(yǔ)句或switch 語(yǔ)句，if語(yǔ)句對(duì)應(yīng)的抽象語(yǔ)法樹有如下結(jié)構(gòu)特點(diǎn)：if 結(jié)點(diǎn)有3個(gè)孩子結(jié)點(diǎn)，從左至右依次排開，分別是條件表達(dá)式結(jié)點(diǎn)、執(zhí)行語(yǔ)句結(jié)點(diǎn)和else 語(yǔ)句結(jié)點(diǎn)；而在switch 語(yǔ)句中，switch 結(jié)點(diǎn)則可能有多個(gè)孩子結(jié)點(diǎn)，switch 括號(hào)內(nèi)的表達(dá)式結(jié)點(diǎn)在最左邊，default 結(jié)點(diǎn)在最右邊。

針對(duì)選擇結(jié)構(gòu)的兩種不同形式的抽象語(yǔ)法樹，首先轉(zhuǎn)換為統(tǒng)一的語(yǔ)法樹形式，再進(jìn)行標(biāo)準(zhǔn)化處理，包括：刪除得不到執(zhí)行的分支、刪除空分支、提取各分支中的公共表達(dá)式、合并選擇結(jié)構(gòu)、將各分支深層次的嵌套結(jié)構(gòu)轉(zhuǎn)換為多分支選擇結(jié)構(gòu)。標(biāo)準(zhǔn)語(yǔ)法樹形式以及深層次嵌套結(jié)構(gòu)轉(zhuǎn)換如圖3 所示。

圖3 選擇結(jié)構(gòu)標(biāo)準(zhǔn)語(yǔ)法樹以及深層次嵌套結(jié)構(gòu)轉(zhuǎn)換示意圖Fig.3 The standard syntax tree of the selected structure and the conversion diagram of the deep nested structure

2.1.2 循環(huán)結(jié)構(gòu)的標(biāo)準(zhǔn)化

實(shí)現(xiàn)循環(huán)結(jié)構(gòu)可采用while 語(yǔ)句、for 語(yǔ)句和do…while 語(yǔ)句。相對(duì)while 語(yǔ)句，do…while 語(yǔ)句至少會(huì)執(zhí)行一次循環(huán)體，本文在語(yǔ)法分析階段對(duì)do…while 語(yǔ)句做了預(yù)處理，將其循環(huán)體拷貝一次后，再轉(zhuǎn)換為while 語(yǔ)句。因此，只討論對(duì)while 語(yǔ)句和for語(yǔ)句所對(duì)應(yīng)的循環(huán)結(jié)構(gòu)進(jìn)行標(biāo)準(zhǔn)化。

針對(duì)上述兩種循環(huán)語(yǔ)句所對(duì)應(yīng)不同形式的抽象語(yǔ)法樹，首先統(tǒng)一其表現(xiàn)形式，將循環(huán)語(yǔ)句的結(jié)點(diǎn)均表示為L(zhǎng)oop結(jié)點(diǎn)，并對(duì)其分支結(jié)構(gòu)進(jìn)行統(tǒng)一的規(guī)范化處理和標(biāo)準(zhǔn)化轉(zhuǎn)換，包括：重新排列各層循環(huán)的順序、刪除條件表達(dá)式恒為假的循環(huán)分支、將循環(huán)體中值不會(huì)發(fā)生改變的語(yǔ)句提取到循環(huán)體外等。

另外，for 語(yǔ)句需要進(jìn)行額外的處理：將初始化表達(dá)式插入到Loop結(jié)點(diǎn)之前，條件表達(dá)式的位置保持不變，再將遞增遞減表達(dá)式放到循環(huán)體中。因?yàn)榇蠖鄶?shù)條件表達(dá)式屬于關(guān)系表達(dá)式，所以可對(duì)其進(jìn)行適當(dāng)?shù)奶幚恚纾篿≤N?i ＜N ＋1。

2.2 基于樹編輯距離的控制結(jié)構(gòu)子樹匹配

控制結(jié)構(gòu)子樹主要包含選擇結(jié)構(gòu)子樹（if、switch 語(yǔ)句）以及循環(huán)結(jié)構(gòu)子樹（while、for 語(yǔ)句），因此選取這兩種控制結(jié)構(gòu)作為主要得分點(diǎn)來(lái)進(jìn)行相似度匹配。在求解樹編輯距離時(shí)，需要讓對(duì)應(yīng)的整棵樹進(jìn)行分解，并生成一系列子樹的集合，再去計(jì)算集合中每一棵子樹與其對(duì)應(yīng)模板子樹的樹編輯距離，遞歸地重復(fù)上述計(jì)算與分解步驟，直到集合中的子樹不能再分解為止。

2.2.1 樹編輯距離算法

樹編輯距離指的是完成從有序樹T1到有序樹T2的樹映射f（T1→T2）所需要進(jìn)行的樹編輯操作的最小代價(jià)。其中，樹編輯操作包含樹結(jié)點(diǎn)的插入、刪除以及替換操作，并且每一個(gè)編輯操作都有相應(yīng)的代價(jià)，用公式（3）表示：

其中，μ（f（T1→T2））是完成有序樹之間的映射f（T1→T2）所需要的編輯操作的代價(jià)，而參數(shù)d（T1，T2）則用來(lái)衡量?jī)煽脴渲g的異構(gòu)程度。

如圖4 所示，用虛線連接與編輯操作無(wú)關(guān)的樹結(jié)點(diǎn)，同時(shí)參照各個(gè)考核點(diǎn)的重要程度來(lái)標(biāo)注出對(duì)應(yīng)結(jié)點(diǎn)的權(quán)值大小。因此，可以利用樹編輯距離來(lái)衡量樹之間的匹配相似度。編輯操作包括刪除結(jié)點(diǎn)decl2、插入結(jié)點(diǎn)expr2，由樹編輯距離的定義可知：d(T1，T2)＝2，并且當(dāng)兩棵樹之間的樹編輯距離越大，說(shuō)明兩棵樹之間映射所需要的編輯操作越多，因而兩棵樹之間的匹配相似度越小。

圖4 T1 →T2 的映射Fig.4 Mapping between T1 and T2

2.2.2 匹配子樹并計(jì)算相似度

在實(shí)際考試中每道編程題所要考核的重點(diǎn)內(nèi)容會(huì)有所不同，為了更好地完成特定的教學(xué)目標(biāo)，本文在靜態(tài)分析階段對(duì)子樹中的每個(gè)結(jié)點(diǎn)賦予了不同的權(quán)值以反映其對(duì)應(yīng)考察點(diǎn)的難易性與重要程度。結(jié)點(diǎn)的權(quán)值越大，則代表該結(jié)點(diǎn)所對(duì)應(yīng)考核的內(nèi)容越重要或者難度越大。本文通過(guò)利用樹中各結(jié)點(diǎn)所賦予的權(quán)值大小，來(lái)計(jì)算源程序與模板程序之間的匹配相似度。該算法描述見表1。

表1 算法描述Tab.1 Algorithm Description

根據(jù)算法得出加權(quán)樹之間的編輯距離（即wEdist ＝M[m][n] ），同時(shí)，利用基于結(jié)點(diǎn)權(quán)值的樹編輯距離公式（4）來(lái)求解源程序與模板程序之間的匹配相似度：

以圖4 中的有序樹映射f（T1→T2）為例，由上述算法可知，加權(quán)樹T1與T2之間的樹編輯距離為4，由公式（4）計(jì)算得到匹配相似度為0.74。

3 系統(tǒng)實(shí)驗(yàn)結(jié)果與分析

為測(cè)試本系統(tǒng)的有效性和準(zhǔn)確率，請(qǐng)80 名學(xué)生使用本系統(tǒng)進(jìn)行編程考核。系統(tǒng)模板試題庫(kù)一共選取了10 道具有代表性的編程題目，每一位學(xué)生會(huì)隨機(jī)抽取一道題目進(jìn)行解答，每道編程題的分值為10分。使用了動(dòng)態(tài)檢測(cè)與靜態(tài)分析相結(jié)合的自動(dòng)評(píng)分方案，該方案所采用的評(píng)分標(biāo)準(zhǔn)見表2。

表2 編程題的評(píng)分標(biāo)準(zhǔn)Tab.2 Scoring criteria for programming questions

評(píng)分標(biāo)準(zhǔn)中首先進(jìn)行關(guān)鍵字檢測(cè)，若檢測(cè)未通過(guò)則直接扣除4 分，若檢測(cè)通過(guò)便動(dòng)態(tài)執(zhí)行源程序，執(zhí)行期間若出現(xiàn)異?；虿荒苷＿\(yùn)行，則扣除2 分。動(dòng)態(tài)檢測(cè)階段完成后執(zhí)行靜態(tài)分析，結(jié)合控制結(jié)構(gòu)匹配相似度進(jìn)行綜合評(píng)分。

為更好地對(duì)比自動(dòng)評(píng)分與人工評(píng)分之間的差異，本文使用絕對(duì)誤差與相對(duì)誤差來(lái)衡量。

同時(shí)，每個(gè)試題編號(hào)所對(duì)應(yīng)的學(xué)生抽取人數(shù)，見表3。

表3 各編程試題的抽取人數(shù)Tab.3 The number of students drawn for each program problem

對(duì)于第k個(gè)編程試題，Tk代表人工評(píng)分所得到的分值；Mk代表自動(dòng)評(píng)分得到的分值；n表示抽取到第k個(gè)試題的學(xué)生人數(shù)。利用絕對(duì)誤差Δ與相對(duì)誤差δ的數(shù)學(xué)公式（5）進(jìn)行計(jì)算，得出的誤差統(tǒng)計(jì)數(shù)據(jù)，見表4。

表4 自動(dòng)評(píng)分方案的誤差統(tǒng)計(jì)Tab.4 Error statistics of automatic scoring scheme

根據(jù)表4 可知，自動(dòng)評(píng)分方案符合人工評(píng)分的思路，并且誤差值也均在合理的范圍內(nèi)，這說(shuō)明自動(dòng)評(píng)分方案具有較高的準(zhǔn)確率，同時(shí)大大提高了評(píng)分的效率，具有很高的實(shí)用價(jià)值。

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

本文提出一種基于動(dòng)態(tài)檢測(cè)與靜態(tài)分析相結(jié)合的評(píng)分方法，該方法已經(jīng)實(shí)現(xiàn)并被集成到在線實(shí)驗(yàn)系統(tǒng)中。實(shí)驗(yàn)結(jié)果表明，本系統(tǒng)評(píng)分準(zhǔn)確率較高，系統(tǒng)穩(wěn)定高效，基本滿足學(xué)生編程題的自動(dòng)評(píng)分需求，達(dá)到預(yù)期效果。