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

1(哈爾濱工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,黑龍江 哈爾濱 150001)

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

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

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

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

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

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

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

本文針對學(xué)生程序設(shè)計(jì)的應(yīng)用背景,研究程序的自動(dòng)修復(fù)方法.

1 相關(guān)研究

1.1 修復(fù)學(xué)生程序的可行性

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

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

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

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

以上兩點(diǎn),使得學(xué)生程序的自動(dòng)化調(diào)試具有更強(qiáng)的可行性.

1.2 學(xué)生程序自動(dòng)修復(fù)的研究現(xiàn)狀

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

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

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

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

2 總體研究框架

2.1 示例演化驅(qū)動(dòng)的學(xué)生程序自動(dòng)修復(fù)研究框架

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

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

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

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

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

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

2.2 與GenProg的對比分析

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

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

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

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

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

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

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

3 關(guān)鍵技術(shù)

3.1 代碼多樣化問題

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

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

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

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

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

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

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

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

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

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

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

實(shí)現(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ǔn)確匹配.

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

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

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

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

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

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

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

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

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

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

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

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

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

在變異時(shí)隨機(jī)選擇變異節(jié)點(diǎn),權(quán)值較高的節(jié)點(diǎn)被選中的概率更大,保證與示例程序不匹配的節(jié)點(diǎn)被選中參與修復(fù)的概率更大,避免盲目隨機(jī)選擇,提高修復(fù)的效率和準(zhǔn)確性.

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

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

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

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

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

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

3.5 變異和交叉操作

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

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

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

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

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

3.6 適應(yīng)度計(jì)算

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

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

適應(yīng)度計(jì)算步驟如下.

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

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

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

(4) 利用公式(3)計(jì)算該變異體的適應(yīng)度;

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

3.7 示例演化驅(qū)動(dòng)的學(xué)生程序自動(dòng)修復(fù)算法

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

算法1.示例演化驅(qū)動(dòng)的學(xué)生程序自動(dòng)修復(fù)算法.

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

Output:適應(yīng)度最高的修復(fù)程序Pr.

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

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

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

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

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

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

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

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

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

4 學(xué)生程序自動(dòng)修復(fù)有效性實(shí)驗(yàn)分析

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

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

Table 3 Experimental data表3 實(shí)驗(yàn)數(shù)據(jù)

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

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

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

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

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

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

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

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

4.2 缺陷個(gè)數(shù)和修復(fù)結(jié)果關(guān)系

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

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

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

4.3 缺陷類型和修復(fù)結(jié)果關(guān)系

缺陷類型對修復(fù)結(jié)果的影響見表5,其中,表達(dá)式、條件語句、循環(huán)語句缺陷在實(shí)際編程中較為常見,但是修復(fù)率與節(jié)點(diǎn)類型沒有明顯的關(guān)聯(lián).這是因?yàn)楸疚姆椒ú捎脧氖纠绦蛑幸浦舱_語句的方法,不限定所移植語句的類型,因此支持各種類型缺陷的修復(fù).

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

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

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

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

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

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

4.5 實(shí)驗(yàn)結(jié)果分析與討論

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

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

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

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

5 結(jié) 論

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