王甜甜,許家歡,王克朝,2,蘇小紅

1(哈爾濱工業(yè)大學 計算機科學與技術學院,黑龍江 哈爾濱 150001)

2(哈爾濱學院 信息工程學院,黑龍江 哈爾濱 150086)

程序自動化調(diào)試有助于提高軟件開發(fā)和維護的效率,提高軟件的質(zhì)量.因此,研究人員針對工業(yè)軟件錯誤定位[1,2]和自動化修復[3,4]技術開展了大量的研究.

近年來,大規(guī)模網(wǎng)絡公開課(massive open online courses,簡稱MOOC)得到了廣泛的關注,EdX、Cousera、Udacity上的優(yōu)秀課程吸引了幾千名學生.然而,對于擁有大規(guī)模的學生數(shù)的 MOOC,教師很難與每個學生都一一進行點評互動.這給信息技術帶來了新的挑戰(zhàn):如何自動化地評價學生的學習效果、提供充分的反饋,與學生互動?

對于實踐性較強的程序設計課程而言,該問題的解決尤為重要.一方面,學生程序表示形式以及缺陷可能多種多樣,教師理解這些程序是很困難的;另一方面,程序調(diào)試是一項很困難的任務:如果沒有自動化技術的輔助,從源代碼中定位到一個錯誤則是一項具有挑戰(zhàn)性的工作.即使已經(jīng)定位到錯誤,依舊需要大量的時間來分析問題的根源并做出適當?shù)男拚?教師人工判別學生程序中的錯誤進而指出修正方法,不僅工作量大,而且效率低,可能花費幾天的時間才能給出反饋.當學生收到反饋后,需要重新回顧解題思路,這常常打消了他們進一步分析程序的積極性.因此,學生程序的自動化調(diào)試及評價反饋,也成為目前的一個研究熱點.

程序自動修復方法通常由兩個步驟構(gòu)成:首先定位可疑語句位置,然后優(yōu)選可疑度大的語句進行修復.學生程序中經(jīng)常可能含有概念錯誤,錯誤密度也遠遠大于工業(yè)代碼,缺陷的種類可能多種多樣,甚至可能缺少關鍵語句,因此可能對所有的測試用例都執(zhí)行失效.該特點導致學生在錯誤定位和修復這兩個步驟上和工業(yè)軟件調(diào)試都有所區(qū)別.

· 首先,工業(yè)界中的缺陷程序一般近似正確,并且補丁較小,錯誤定位方法研究基于的假設是“缺陷程序可以對某些測試用例執(zhí)行成功,而對另一些測試用例執(zhí)行失效”[5].通過對比成功執(zhí)行和失效執(zhí)行信息來定位可疑語句,例如,GenProg[6]等程序修復工具通常采用程序譜故障定位方法.然而學生程序中可能含有較大概念錯誤,導致程序?qū)λ袦y試用例均產(chǎn)生失效,該情況下無法對比成功測試用例和失效測試用例的執(zhí)行信息,因此需要研究適合于分析學生程序的錯誤定位方法.

· 另外,工業(yè)軟件難于獲得完整的規(guī)格說明,通常只能通過測試用例集評價修復程序,限制了程序修復的有效性.然而學生程序的規(guī)格說明是明確的,并且在編程練習或考試過程中可獲得大量的學生程序,這些學生程序中有很多程序是正確的,可作為潛在的示例程序來指導其他含有缺陷的程序的故障定位和修復.然而實現(xiàn)相同編程任務的學生程序可能具有相似的實現(xiàn)形式,也可能實現(xiàn)方式不同,這給程序分析帶來了困難.需要重點研究解決該問題.

本文針對學生程序設計的應用背景,研究程序的自動修復方法.

1 相關研究

1.1 修復學生程序的可行性

工業(yè)軟件自動化調(diào)試的一個主要難點問題在于無法獲知一個修正方案是否真正解決了錯誤根源,還是簡單地掩蓋了問題.通常,達到的最好解決程度是用測試用例或部分規(guī)格說明檢驗修正方案,這就導致了修正操作的種類、要修正的可疑語句位置、可用的修正元素的搜索空間巨大,進而導致修正方法的開銷巨大,并且難于充分地遍歷搜索空間,因而可能搜索不到正確補丁.

不同于工業(yè)軟件,學生程序具有以下特點.

(1) 完整的規(guī)格說明是已知的,給定問題的答案是已知的.除了測試用例外,還可以由教師事先編寫的完全滿足規(guī)格說明的參考程序,隱含了期望解的規(guī)格說明.另外,MOOC中學生提交了大量的正確程序,可以從這些程序中發(fā)現(xiàn)新的模板程序.

(2) 由于學生參加相同的課程,并且完成相同的題目,編寫程序的思路甚至所犯的錯誤通常也相似.

以上兩點,使得學生程序的自動化調(diào)試具有更強的可行性.

1.2 學生程序自動修復的研究現(xiàn)狀

MIT的Singh等人開發(fā)了AutoProf[7],利用基于約束的合成算法為程序設計提供反饋.除了提供參考程序外,還需要提供人工定義的形式化錯誤模型來描述解決給定問題時學生易犯錯誤的修復規(guī)則.基于修復規(guī)則自動推導合成缺陷程序的修復版本,使該修復版本與參考程序功能等價.該研究為程序設計調(diào)試和反饋提供了一種新的研究思路,但是仍存在局限性:修復能力由人工定義的錯誤模型決定,而人工定義錯誤模型比較困難,修復規(guī)則通常比較簡單,因此只能修改表達式類的簡單缺陷,無法新增和移動語句,也不能修復較大的概念錯誤.另外,基于約束的程序合成方法復雜度比較高.

Purdue大學的 Kim等人開發(fā)了 APEX[8],輸入?yún)⒖汲绦蚝蜏y試用例后,基于符號執(zhí)行、最大滿足求解和動態(tài)分析,通過匹配參考程序的成功執(zhí)行和缺陷程序的失效執(zhí)行的程序切片,來解釋缺陷的產(chǎn)生原因.受符號執(zhí)行的限制,該方法也只能對簡單缺陷提供修改建議,不能對復雜的概念錯誤,例如修改控制結(jié)構(gòu)、新增和移動語句等給出反饋.另外,該方法無法自動生成修復程序.

Yi等人研究了當前比較流行的工業(yè)軟件修復工具在修復學生程序中的性能[9],分析了 GenProg[6],AE[10],Prophet[11]和 Angelix[12]這 4個工具.它們均采用測試驅(qū)動的方法,即:如果補丁程序通過了測試集中所有測試用例,則認為該補丁是一個修復程序.例如,GenProg采用遺傳編程算法,試圖從待修復程序的其他地方轉(zhuǎn)移正確的語句,經(jīng)過不斷的演化,來使補丁程序通過所有測試.Yi等人基于這 4個工具,利用部分修復策略指導學生編程.即:如果一個程序?qū)χ俺晒Φ臏y試用例依然成功,之前失效的測試用例只要有一個變?yōu)槌晒?則認為該程序是一個部分修復,將部分修復反饋給學生,提示其修改程序.研究結(jié)果表明,這些工具的修復率較低.原因是這些工具通常每次只修改一個錯誤,而學生程序中錯誤通常較多,需要更復雜的修改;另外,測試只考慮了程序的執(zhí)行結(jié)果,而沒有考慮程序的行為和編程規(guī)范,指導搜索生成的補丁很可能犧牲了其他重要需求.因此,這些工具不適合直接應用于學生程序修復中.

以上研究給我們帶來的啟發(fā)是,學生程序需求明確且功能簡單,教師可以提供充分的滿足覆蓋要求的測試用例集合作為選擇補丁的判定準則.然而對于學生程序自動化調(diào)試而言,除了測試用例外,還可以提供教師事先編寫的模板程序.模板程序中隱含了期望解的規(guī)格說明,使得程序設計自動化調(diào)試具有更強的可行性.因此,如果能將模板程序也有效應用于程序修復的演化過程中,指導錯誤定位和補丁的生成,則有望定位和修復學生程序中缺失語句、存在依賴關系的多處復雜缺陷.

2 總體研究框架

2.1 示例演化驅(qū)動的學生程序自動修復研究框架

將模板程序引入程序修復的演化框架中,提出示例演化驅(qū)動的學生程序自動修復方法,如圖1所示,分為以下4個組成部分.

(1) 選擇示例程序:對源程序和模板程序進行解析,生成抽象語法樹,并計算其最大相似度,從而可以從模板程序集中選擇與學生程序結(jié)構(gòu)語義最為相似的模板程序作為參考示例程序.

(2) 靜態(tài)錯誤定位和差異分析:程序修復的一個關鍵問題是“修復操作的可選位置以及可用的修復算子相組合,生成了巨大的搜索空間”,學生程序修復也存在該問題.為了有效選擇修改位置、編輯操作以及從示例程序中轉(zhuǎn)移正確的語句,本文提出了基于示例的靜態(tài)錯誤定位和差異分析方法.一方面,通過匹配學生程序抽象語法樹和示例程序抽象語法樹,尋找學生程序中的差異語句節(jié)點,作為優(yōu)先修改位置賦以較高的選擇概率;將示例程序中差異節(jié)點作為候選的替換或插入節(jié)點,從而有效縮小修復轉(zhuǎn)換的搜索空間,提高修復有效性.另一方面,對差異節(jié)點進一步分析修復該位置缺陷可能的變異操作,區(qū)分增加、刪除、替換操作的權重,作為選擇變異操作的概率.這樣有助于根據(jù)實際的缺陷類型,選擇合適的變異操作,提高變異轉(zhuǎn)換的效率和有效性.由于無需執(zhí)行程序,該方法可以有效分析無法獲得成功執(zhí)行結(jié)果的學生程序.

(3) 動態(tài)變量映射:學生程序和示例程序可能使用不同的變量名,該模塊基于變量執(zhí)行值序列識別出學生程序和示例程序中的等價變量,獲得變量映射表,為后續(xù)變異過程中的變量重命名奠定基礎.

(4) 遺傳編程演化:在前3個模塊的基礎上,采用遺傳編程算法生成修復后的學生程序和修復操作方案.利用示例程序向待修復程序中移植正確的代碼,采用將示例程序語法樹中的子樹插入或替換到學生程序語法樹中的方法進行變異,生成的新程序即為一個變異體.在適應度計算時,不但考慮測試用例的通過情況,還考慮補丁程序與示例程序的語法結(jié)構(gòu)相似程度,指導補丁程序向期望的規(guī)格說明方向演化.通過在語法樹上進行多次交叉、變異操作,可修復多個缺陷.

Fig.1 Research framework for example-evolution-driven automatic repair of student programs圖1 示例演化驅(qū)動的學生程序自動修復研究框架

2.2 與GenProg的對比分析

本文方法和GenProg[9]都是基于遺傳編程框架研究程序的自動修復,不同之處見表1.

(1) 變異來源.GenProg通過重用、組合待修復程序中的已有語句來生成補丁,不能合成全新的代碼,如果修復元素沒有出現(xiàn)在程序的其他地方,則無法正確修復.本文方法從示例程序中挖掘語法樹子樹來進行變異,模板程序可為修復各種復雜缺陷提供充分的素材,也可以在修改時引入新的程序邏輯.

(2) 錯誤定位方法.GenProg采用基于程序譜的錯誤定位方法,該方法要求程序可以通過某些測試,而學生程序有的時候不能成功執(zhí)行,因此不適合使用該方法定位可疑語句.本文提出基于示例的錯誤定位方法,通過對學生程序和模板程序執(zhí)行上下文匹配,判斷學生程序語法樹和模板程序語法樹的相似節(jié)點和不同節(jié)點,一方面,識別到可能錯誤的節(jié)點;另一方面,可將模板程序中的差異節(jié)點作為候選修復節(jié)點.該方法考慮程序的上下文,有助于生成有意義的補丁.

(3) 適應度計算.由于工業(yè)軟件無法獲知規(guī)格說明的局限性,GenProg只使用通過測試用例數(shù)作為補丁程序的適應度衡量準則.而學生程序修復中,示例程序中蘊含了需求規(guī)格和編程規(guī)范,可以將其應用于度量補丁程序的適應度,因此,本文除了考慮測試結(jié)果外,還考慮補丁程序和示例程序的相似度,使得適應度的值更加精確,不會出現(xiàn)大量變異體適應度均為0的現(xiàn)象,有效指導補丁程序朝著期望演化.

(4) 變量重命名.GenProg沒有考慮不同上下文中變量名的差異,而實際上,實現(xiàn)類似功能的代碼在不同的上下文中可能具有不同的變量名.為了提高修復的有效性,本文提出了基于執(zhí)行值序列的變量映射方法,識別學生程序和示例程序中等價的不同變量名.

(5) 是否支持多缺陷修復.GenProg雖然能修復多處缺陷,但生成的補丁較簡單.本文方法在示例程序的指導下,通過對編輯序列的變異和交叉,可以成功修復含有多個復雜缺陷,即包含多個修復點的程序.

Table 1 Comparison between our method and GenProg表1 本文方法與GenProg的對比

3 關鍵技術

3.1 代碼多樣化問題

實現(xiàn)相同算法的多個程序語法表示形式可能不同.例如圖2中的程序代碼A與B,它們采用相同的迭代算法實現(xiàn)求baseexp的功能,但其語法表示形式不同,例如不同的變量名、語句順序以及控制結(jié)構(gòu)和表達式等,這種情況稱為代碼多樣化.

Fig.2 Sample programs with code variations圖2 包含代碼多樣化的程序示例

代碼多樣化給識別學生程序和模板程序的差異帶來了困難.為了解決這個問題,我們將代碼多樣化劃分為表達式、控制結(jié)構(gòu)、函數(shù)調(diào)用、變量名、語句順序多樣化等,并提出了基于結(jié)構(gòu)語義分析識別和消除這些代碼多樣化[13],進而識別等價的語法結(jié)構(gòu)和表達式等.一方面可以用于減少所需要提供的模板數(shù),對功能等價的含有代碼多樣化的程序只需提供一個模板;另一方面,提高學生程序和示例程序差異分析的準確性.

3.2 缺陷程序和示例程序的結(jié)構(gòu)語義和執(zhí)行特征值差異識別

為了有效定位學生程序中多種類型的缺陷,特別是缺失語句和錯誤變量以及存在依賴關系的復雜缺陷,并且避免代碼多樣化,特別是語句順序多樣化和變量名多樣化影響學生程序和示例程序差異分析的準確性,提出結(jié)構(gòu)語義和執(zhí)行特征值交互分析方法,使得即使在缺陷程序不能通過任何測試用例的情況下,也可以定位其中的可疑語句,進而有效限定修復的搜索空間,并反饋錯誤產(chǎn)生原因.

輸入示例程序、缺陷程序、測試用例集,目標是識別學生程序和示例程序中存在差異的結(jié)構(gòu)、變量、表達式及語句作為可疑位置,并將差異分析結(jié)果以圖和值序列的形式進行反饋,輔助理解錯誤的產(chǎn)生原因,并映射學生程序和模板程序中的變量,用以輔助程序修復.步驟如下.

(1) 對缺陷程序和示例程序進行執(zhí)行特征值分析,識別匹配變量對.對示例程序中的每個變量值序列分別與學生程序中的每個變量序列使用最長公共子序列算法,得到每兩個變量之間的相似度,與該變量值序列相似度最高的學生程序中的變量值序列即為對應的變量值序列.

(2) 采用最長公共子序列算法求缺陷程序和示例程序語法樹的最大匹配.

(3) 等價的賦值語句在程序執(zhí)行過程中有可能受到前面與其存在數(shù)據(jù)依賴關系的執(zhí)行語句的影響,得不到等價的特征值序列.為了避免漏檢,需要進一步分析未匹配的賦值語句,根據(jù)表達式的結(jié)構(gòu)語義,進一步識別結(jié)構(gòu)語義等價的賦值語句和可能匹配變量對.

(4) 輸出缺陷程序和示例程序的語法樹并標記未匹配的結(jié)構(gòu)和語句,并輸出匹配變量對、差異變量及其執(zhí)行特征值序列,輔助學生理解錯誤的產(chǎn)生原因.

3.3 動態(tài)變量映射

實現(xiàn)相同算法的程序通常具有相似的程序結(jié)構(gòu)特征和執(zhí)行特征.各變量在執(zhí)行過程中具有相同的值序列,這些值序列不受代碼多樣化的影響.通過匹配執(zhí)行特征值序列,可以消除這種語句順序和變量名多樣化的影響.例如圖2,由于C中的變量j和A中的變量i對相同的輸人都具有相同的值序列,因此(j,i)為匹配變量對.根據(jù)匹配變量對(j,i),則可以將C中的j=j+1和A中的i++語句準確匹配.

本文通過判定變量執(zhí)行過程中值序列的相似性進行變量映射,確定學生程序和示例程序中的對應變量,步驟如下.

(1) 采用在語法樹上實現(xiàn)程序插樁的方法,在不破壞程序語義的條件下,在程序語法樹上的變量初始化和賦值表達式節(jié)點之后插入探針語句,用以在后續(xù)執(zhí)行過程中捕獲變量的值.

(2) 反向生成代碼,并用測試用例執(zhí)行插樁后的程序,收集輸出的變量名和變量值序列.

(3) 通過對比兩個程序的變量執(zhí)行值序列,獲得兩個程序的對應變量,建立變量映射表.對示例程序B中的每個變量值序列分別與學生程序A中的每個變量序列使用最長公共子序列算法,得到每兩個變量之間的相似度,與該變量值序列相似度最高的學生程序A中的變量值序列即為對應的變量值序列.

(4) 在后續(xù)進行程序變異時,先判斷子樹中是否有變量映射表中的變量:如果有,則用變量映射表中與示例程序變量名對應的學生程序變量名對待替換的示例程序子樹中的變量進行替換,使變異體可以通過編譯和運行.

3.4 基于示例的靜態(tài)錯誤定位和差異分析

由于圖2中缺陷程序C中缺少對變量r的初始化語句,導致r=r*base和示例程序A中的r*=base沒有生成等價的執(zhí)行特征值序列,因而通過動態(tài)變量映射無法將(r,r)識別為匹配的變量對.對于這樣沒有找到匹配變量對的語句,進一步進行表達式標準化和語法匹配,可識別它們結(jié)構(gòu)語義等價,進而將(r,r)識別為可能匹配變量對.

如圖3所示,通過程序抽象語法樹的子樹匹配,判斷學生程序語法樹和示例程序語法樹的相似節(jié)點和不同節(jié)點,從而定位到可能含有缺陷的節(jié)點,并識別可能的變異操作,縮小搜索范圍.

Fig.3 Static fault localization based on example and difference analysis圖3 基于示例的靜態(tài)錯誤定位和差異分析

(1) 使用最長公共子序列算法求學生程序和示例程序抽象語法樹序列的最大匹配.

兩個節(jié)點為相同節(jié)點的判斷條件是:兩個節(jié)點對應的字符串值完全匹配且父節(jié)點類型相同.

父節(jié)點類型相同是為保證學生程序語法樹的節(jié)點A與模板程序語法樹的節(jié)點B在同一結(jié)構(gòu)中,如A的父節(jié)點是循環(huán)結(jié)構(gòu),那么B節(jié)點的父節(jié)點必須也是循環(huán)結(jié)構(gòu),考慮了程序上下文,保證程序結(jié)構(gòu)的準確性和代碼的完整性.由于執(zhí)行了結(jié)構(gòu)語義分析,可以將含有代碼多樣化的語句轉(zhuǎn)換為相同內(nèi)部表示形式.

(2) 記錄兩個節(jié)點序列中相同和不同的節(jié)點,對學生程序和示例程序的節(jié)點序列中每個節(jié)點賦予權值,匹配的節(jié)點賦予權值W1,不匹配的節(jié)點賦予權值W2,見公式(1)和公式(2):

在變異時隨機選擇變異節(jié)點,權值較高的節(jié)點被選中的概率更大,保證與示例程序不匹配的節(jié)點被選中參與修復的概率更大,避免盲目隨機選擇,提高修復的效率和準確性.

(3) 進一步分析學生程序和示例程序的節(jié)點序列中未匹配的節(jié)點,識別以下3類可能的變異操作節(jié)點位置,并給各個節(jié)點賦一個變異操作權值三元組〈WI,WR,WD〉,分別表示該位置執(zhí)行插入、替換和刪除操作的概率.

· 插入語句位置:示例程序節(jié)點序列中對應位置有語句,而學生程序中該位置缺少與之相匹配的語句,此時,該位置的前一個語句節(jié)點是一個可能插入語句的位置,它的〈WI=0.5,WR=0.25,WD=0.25〉.

· 替換語句位置:示例程序和學生程序此位置都有語句,但是內(nèi)容不完全匹配,則該節(jié)點是一個可能替換的語句位置,它的〈WI=0.25,WR=0.5,WD=0.25〉.

· 刪除語句位置:學生程序中的語句節(jié)點在示例程序中找不到與之匹配的語句,則該節(jié)點是一個可能刪除語句的位置,它的〈WI=0.25,WR=0.25,WD=0.5〉.

對于不存在上述情況的節(jié)點,則賦以相同的變異操作權重,即〈WI=0.33,WR=0.33,WD=0.33〉.

在執(zhí)行變異操作時,根據(jù)概率選擇變異位置和變異操作,既保留了遺傳算法的隨機性,也有助于指導補丁搜索朝著更有效的方向演化.

3.5 變異和交叉操作

為了節(jié)省變異體的存儲空間,使用編輯序列代替變異體存儲在種群中,編輯序列記錄了從學生程序到生成變異體經(jīng)歷的操作步驟.由于本文方法的目標是從示例程序中轉(zhuǎn)移正確邏輯和語句來修復學生程序中的缺陷語句,該轉(zhuǎn)換操作是基于程序的抽象語法樹執(zhí)行的.根據(jù)學生程序和示例程序抽象語法樹的匹配結(jié)果和需要的執(zhí)行的轉(zhuǎn)換操作,將變異操作分為3種,分別為插入(insert)、刪除(delete)、替換(replace)操作,見表2.

Table 2 Example of mutation operations表2 變異操作示例

在第3.4節(jié)的學生程序和示例程序的語法樹差異分析過程中,識別了學生程序中可能插入、刪除、或替換節(jié)點位置,并為這 3種變異操作賦以不同的權重,權重高的變異操作具有較高的選擇概率.這樣有助于根據(jù)實際的缺陷位置和類型,選擇合適的變異操作,提高變異轉(zhuǎn)換的效率和有效性.

為了增加遺傳的多樣性,在變異之后對群體中的各個個體即編輯序列,按概率執(zhí)行交叉操作.由于每個編輯操作都是一次針對特定的子樹操作,因此各個編輯操作之間是相互獨立的.本文方法的交叉操作沿用了GenProg所采用單點交叉操作.采用隨機選擇交叉點的策略,即隨機產(chǎn)生一個交叉點位置,兩個個體在交叉點位置互換部分編輯操作,形成兩個子個體.如圖4所示,分別生成兩個小于或等于編輯序列操作個數(shù)的隨機數(shù),利用該隨機數(shù)確定劃分位置,將序列1和序列2分別劃分為兩部分,將序列1的前一部分與序列2的后一部分連接起來,序列2的前一部分與序列1的后一部分連接起來,形成兩個新的編輯序列,替換原來的編輯序列,添加到種群中.

Fig.4 Example of crossover of editing sequences圖4 編輯序列交叉示例

3.6 適應度計算

變異體的適應度是遺傳演化的依據(jù),如公式(3)所示,根據(jù)變異體執(zhí)行時通過測試用例數(shù)和未通過測試用例數(shù)以及變異體語法樹與示例程序語法樹的結(jié)構(gòu)相似度3個元素衡量.

其中,P表示變異體,S表示示例程序;fitness(P)表示變異體P的適應度;posT是成功測試用例集合,|posT|是其中測試用例的個數(shù);negT表示失敗測試用例集合,|negT|是其中測試用例的個數(shù);t表示一個測試用例,|t∈posTandP passest|表示之前成功執(zhí)行的測試用例執(zhí)行變異體P時依然成功的個數(shù),|t∈negTandPpassest|表示之前執(zhí)行失敗的測試用例執(zhí)行變異體P時變?yōu)閳?zhí)行成功的個數(shù);SimpleTreeMatching(P,S)表示變異體P和示例程序S的子樹匹配相似度;wposT,wnegT和wsimilar表示相應的權重值.

適應度計算步驟如下.

(1) 對于每一個編輯序列,在學生程序的語法樹上執(zhí)行編輯序列中的所有操作,重構(gòu)語法樹,再將語法樹反向生成變異體;

(2) 使用測試用例執(zhí)行種群中所有變異體,得到程序執(zhí)行結(jié)果,統(tǒng)計成功通過測試用例的個數(shù)和失敗測試用例的個數(shù);

(3) 使用最長公共子序列算法計算變異體語法樹與示例程序語法樹的語法結(jié)構(gòu)匹配相似度;

(4) 利用公式(3)計算該變異體的適應度;

(5) 通過變異體的適應度來篩選種群中的變異體,按照適應度決定變異體被隨機選擇的概率,以達到演化的目的.

3.7 示例演化驅(qū)動的學生程序自動修復算法

示例演化驅(qū)動的學生程序自動修復算法如算法1所示.輸入含有缺陷的學生程序、示例程序、測試用例集以及遺傳算法的相關參數(shù),輸出修復程序.

算法1.示例演化驅(qū)動的學生程序自動修復算法.

Input:缺陷學生程序P;示例程序S;測試用例集T;種群規(guī)模popSize;迭代最大次數(shù)pop.

Output:適應度最高的修復程序Pr.

· 第1行和第2行分別對示例程序和學生程序進行語法解析,用列表的形式存儲語法樹節(jié)點.

· 第3行將示例程序語法樹的節(jié)點列表和源程序語法樹的節(jié)點列表使用改進的最長公共子序列算法,判斷兩個程序的節(jié)點相似性,即兩棵語法樹的子樹匹配.使用map存儲程序節(jié)點與變異位置概率以及變異操作概率值的映射.

· 第4行生成第1代編輯序列,使用二維數(shù)組group存儲popSize條編輯序列.

· 第6行將種群group中每一條編輯序列通過語法樹重構(gòu)和反向生成代碼形成變異體并執(zhí)行,按照將失敗測試用例轉(zhuǎn)變?yōu)槌晒y試用例的個數(shù)和成功通過成功測試用例的個數(shù)以及變異體與模板程序的語法結(jié)構(gòu)相似程度計算適應度.

· 第7行使用輪盤賭算法按概率隨機選擇需要變異的變異體.

· 第 8行對所選擇的變異體按照位置概率和變異操作概率進行變異,生成新的編輯序列添加到種群group中.

· 第9行選擇編輯序列和隨機選擇編輯序列的交叉點實現(xiàn)兩個編輯序列的交叉,保證種群內(nèi)變異體的多樣性,并使得變異體的數(shù)量維持popSize個不變.

· 循環(huán)執(zhí)行第5行～第9行,直到有變異體能夠通過全部測試用例或迭代次數(shù)達到之前設置的迭代最大次數(shù)pop次.

· 第11行輸出修復程序,如果沒有能夠通過全部測試用例的變異體,則輸出適應度最高的變異體.

4 學生程序自動修復有效性實驗分析

4.1 實驗數(shù)據(jù)和環(huán)境

開發(fā)了示例演化驅(qū)動的Java學生程序自動修復系統(tǒng),并使用賽碼網(wǎng)上的真實習題進行測試.選擇了10個真實在線編程題目,從真實學生提交的正確程序代碼中選取使用不同語法結(jié)構(gòu)的程序作為模板,并人工選擇確認測試用例集合,使各個測試用例集合滿足對所有模板程序的路徑覆蓋和條件判定覆蓋.再從真實學生提交的含有缺陷的程序代碼中選取不同錯誤版本,見表3.

Table 3 Experimental data表3 實驗數(shù)據(jù)

回文串程序的分析示例見http://homepage.hit.edu.cn/wangtiantian.

在選擇測試程序的過程中,發(fā)現(xiàn)有部分錯版本無法使用本文方法進行修復,包含以下幾種情況.

(1) 函數(shù)調(diào)用參數(shù)個數(shù)不同.由于學生程序和模板程序中實現(xiàn)相同功能的函數(shù)可能含有不同個數(shù)的參數(shù),而本文方法目前尚未考慮這種情況.

(2) 學生程序和模板程序的變量差異顯著.學生程序的錯誤變量執(zhí)行值序列和模板程序的變量執(zhí)行值序列可能出現(xiàn)完全不相同的情況,此時,變量映射會出現(xiàn)偏差,而變量名映射不準確會導致學生程序無法正確執(zhí)行.

(3) 多文件程序修復.當前只允許學生上傳單文件程序代碼,其中含有輸入輸出和 main函數(shù),可以直接編譯運行,目前尚不支持多個文件之間的函數(shù)調(diào)用的分析.

(4) 學生程序因含有語法錯誤編譯未通過.本文方法只針對可以編譯運行的學生程序進行自動修復,可以分析無法通過任何測試用例的學生程序,但不支持分析含有語法錯誤的學生程序.

最終,本文篩去上述類型的錯誤程序,選取了其中的100個錯誤版本作為測試數(shù)據(jù)進行實驗,其中,所有學生程序的平均代碼行數(shù)為73行.

本文從程序缺陷個數(shù)、缺陷類型和種群規(guī)模這 3個方面分析程序自動修復的相關因素.實驗環(huán)境硬件配置:2.3 GHz Intel Core i5處理器,8GB 2133MHz LPDDR3內(nèi)存.

4.2 缺陷個數(shù)和修復結(jié)果關系

缺陷個數(shù)對修復結(jié)果的影響見表4.本文方法可以修復含有多個缺陷的學生程序.當學生程序只有1到2個修復點時,修復率接近 100%;當含有 3個修復點時,修復率為 70%;當含有 4個及以上修復點時,修復率為 50%.種群規(guī)模與迭代次數(shù)增加,導致分析時間的增加.隨著學生程序中的修復點數(shù)量增多,系統(tǒng)的修復率降低,且運行時間增加;學生程序中修復點數(shù)量越少,系統(tǒng)的修復率越高,運行時間越短.

Table 4 Relationship between the number of bugs and repair results表4 缺陷個數(shù)和修復結(jié)果間的關系

多缺陷程序的修復率下降的主要原因是:盡管本文方法按照概率選擇修復位置和操作,但是可疑語句位置、用于插入和替換的示例語句位置以及變異操作的選擇都具有隨機性,修復點越多,則組合生成的補丁搜索空間越大,導致在有限的種群規(guī)模和迭代次數(shù)內(nèi)不能搜索到完全正確的補丁.

4.3 缺陷類型和修復結(jié)果關系

缺陷類型對修復結(jié)果的影響見表5,其中,表達式、條件語句、循環(huán)語句缺陷在實際編程中較為常見,但是修復率與節(jié)點類型沒有明顯的關聯(lián).這是因為本文方法采用從示例程序中移植正確語句的方法,不限定所移植語句的類型,因此支持各種類型缺陷的修復.

Table 5 Relationship between bug types and repair results表5 缺陷類型和修復結(jié)果間的關系

4.4 種群規(guī)模的大小和迭代次數(shù)對修復的影響

本文選擇10個含有4個及以上修復點的學生程序進行控制變量的實驗,其他條件一樣,測試種群規(guī)模的大小和迭代次數(shù)對程序自動修復的影響,結(jié)果見表6和表7.

迭代次數(shù)保持不變時,種群的規(guī)模增加會使修復成功的數(shù)量增加,平均修復或未修復程序的最高適應度也隨之增大,執(zhí)行時間隨之變長.當種群規(guī)模保持不變時,增加迭代次數(shù)可以使修復成功的數(shù)量增加,但是到了一定數(shù)量時,迭代次數(shù)的增加并不能帶來明顯的修復成功率變化,同時,運行時間也隨之增大.

Table 6 Relationship between population size and repair results表6 種群規(guī)模和修復結(jié)果間的關系

Table 7 Relationship between the number of iterations and repair results表7 迭代次數(shù)和修復結(jié)果間的關系

4.5 實驗結(jié)果分析與討論

本系統(tǒng)對于缺陷數(shù)量為1個～2個的程序修復率較高,運行時間在200s之內(nèi).對于缺陷數(shù)量大于2的學生程序,建議多次執(zhí)行或增大種群的規(guī)模.相比之下,增大種群規(guī)模更有助于提高修復率.因為種群規(guī)模變大,則每次迭代變異體的覆蓋錯誤范圍更大.

實驗也證明了在本系統(tǒng)所針對分析的語句類型范圍內(nèi),修復率與缺陷類型無關.但是對于本系統(tǒng)沒有涉及分析的語句類型,則無法得到修復結(jié)果.在今后的工作中,可擴展分析的語句節(jié)點類型,使本系統(tǒng)可以修復更多的缺陷類型.

通過人工排查無法修復的程序,發(fā)現(xiàn)變量映射對程序修復至關重要.對于可以獲得準確執(zhí)行值序列匹配的變量,本文的值序列匹配方法可以準確對其進行映射;然而如果存在值序列差別較大,或存在學生程序中有而模板程序中沒有的變量,則在執(zhí)行程序變異時會導致變量名未正確匹配而使變異體無法通過編譯.這也是本文需要進一步研究的關鍵內(nèi)容.

本文面向?qū)W生程序自動化調(diào)試,重點研究了改進遺傳編程的變異方法及適應度評價方法,并通過靜態(tài)錯誤定位縮小遺傳編程的搜索空間來提高修復有效性和效率.選擇策略和交叉算子則沿用了 GenProg中采用的方法.然而不同的選擇、交叉策略對程序修復結(jié)果也可能產(chǎn)生影響.Kou等人研究改進了GenProg的交叉策略[14],對所要交叉的個體對,根據(jù)差異度或測試用例通過率進行降序排序,選擇排序靠前的個體對執(zhí)行交叉操作;并且對比分析了單點交叉、均勻交叉和隨機交叉策略與其選擇策略配合使用時的程序修復效果.他們的實驗結(jié)果表明,采用其所提出的測試用例通過率優(yōu)先的選擇操作,并且應用隨機交叉策略時,程序修復效果優(yōu)于GenProg采用的單點交叉策略[14].類似地,本文的后續(xù)工作將進一步實驗分析不同選擇算子和交叉算子等對學生程序修復結(jié)果的影響.

5 結(jié) 論

本文針對學生程序研究自動修復方法.提出了示例演化驅(qū)動的程序修復方法,利用模板程序指導補丁的搜索和生成,以修復學生程序中多個復雜缺陷.提出了基于示例的靜態(tài)錯誤定位和差異分析方法,定位可疑語句并識別可能的變異操作,避免大量的盲目變異操作,縮小搜索空間.提出了基于值序列的變量映射方法,映射缺陷程序和示例程序中實現(xiàn)相同功能的變量.結(jié)合測試用例以及學生程序與示例程序的語法結(jié)構(gòu)相似度來評價補丁的適應度,使得適應度的值更加準確,不會出現(xiàn)大量變異體適應度均為 0的現(xiàn)象,有效指導補丁程序朝著期望演化.實現(xiàn)了一個針對Java語言學生程序自動修復的Web應用程序,為學生編程提供自動反饋,實驗結(jié)果驗證了該系統(tǒng)的有效性.后續(xù)將完善該方法研究,并進一步增強其實用性.