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

薛 斌，胡建鵬

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（2）通過對程序運(yùn)用一系列標(biāo)準(zhǔn)化規(guī)則，在抽象語法樹的基礎(chǔ)上，將不同表現(xiàn)形式的程序語法樹轉(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é)主要對程序控制結(jié)構(gòu)進(jìn)行標(biāo)準(zhǔn)化轉(zhuǎn)換。在C 語言中有3 種基本的控制結(jié)構(gòu)：順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)。每一種控制結(jié)構(gòu)都可能有多種代碼書寫形式，這為源程序和模板程序的匹配帶來困難，所以需要對控制結(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 語句或switch 語句，if語句對應(yīng)的抽象語法樹有如下結(jié)構(gòu)特點(diǎn)：if 結(jié)點(diǎn)有3個(gè)孩子結(jié)點(diǎn)，從左至右依次排開，分別是條件表達(dá)式結(jié)點(diǎn)、執(zhí)行語句結(jié)點(diǎn)和else 語句結(jié)點(diǎn)；而在switch 語句中，switch 結(jié)點(diǎn)則可能有多個(gè)孩子結(jié)點(diǎn)，switch 括號內(nèi)的表達(dá)式結(jié)點(diǎn)在最左邊，default 結(jié)點(diǎn)在最右邊。

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

圖3 選擇結(jié)構(gòu)標(biāo)準(zhǔn)語法樹以及深層次嵌套結(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 語句、for 語句和do…while 語句。相對while 語句，do…while 語句至少會(huì)執(zhí)行一次循環(huán)體，本文在語法分析階段對do…while 語句做了預(yù)處理，將其循環(huán)體拷貝一次后，再轉(zhuǎn)換為while 語句。因此，只討論對while 語句和for語句所對應(yīng)的循環(huán)結(jié)構(gòu)進(jìn)行標(biāo)準(zhǔn)化。

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

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

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

控制結(jié)構(gòu)子樹主要包含選擇結(jié)構(gòu)子樹（if、switch 語句）以及循環(huán)結(jié)構(gòu)子樹（while、for 語句），因此選取這兩種控制結(jié)構(gòu)作為主要得分點(diǎn)來進(jìn)行相似度匹配。在求解樹編輯距離時(shí)，需要讓對應(yīng)的整棵樹進(jìn)行分解，并生成一系列子樹的集合，再去計(jì)算集合中每一棵子樹與其對應(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）則用來衡量兩棵樹之間的異構(gòu)程度。

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

圖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)分析階段對子樹中的每個(gè)結(jié)點(diǎn)賦予了不同的權(quán)值以反映其對應(yīng)考察點(diǎn)的難易性與重要程度。結(jié)點(diǎn)的權(quán)值越大，則代表該結(jié)點(diǎn)所對應(yīng)考核的內(nèi)容越重要或者難度越大。本文通過利用樹中各結(jié)點(diǎn)所賦予的權(quán)值大小，來計(jì)算源程序與模板程序之間的匹配相似度。該算法描述見表1。

表1 算法描述Tab.1 Algorithm Description

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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