基于故障檢測(cè)上下文的等價(jià)變異體識(shí)別算法

于 暢 王雅文 林 歡 宮云戰(zhàn)

(網(wǎng)絡(luò)與交換技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室(北京郵電大學(xué)) 北京 100876)(shuoxunyc@bupt.edu.cn)

變異測(cè)試(mutation testing)是一種基于故障的軟件測(cè)試分析方法[1]，它通過(guò)向被測(cè)軟件注入一組人工故障，以模擬軟件開(kāi)發(fā)過(guò)程中引入的代碼缺陷[2].這些故障被進(jìn)一步用于評(píng)估測(cè)試充分性[3-5]，并輔助測(cè)試人員開(kāi)發(fā)測(cè)試用例以提高測(cè)試質(zhì)量[6-8].相關(guān)研究[9-10]表明，相較結(jié)構(gòu)化覆蓋準(zhǔn)則[11]，該技術(shù)具有更強(qiáng)的檢錯(cuò)能力.

在變異測(cè)試中，通過(guò)修改被測(cè)程序源代碼的語(yǔ)法結(jié)構(gòu)注入故障，被修改后的故障程序稱(chēng)為變異體，而代碼修改規(guī)則稱(chēng)為變異算子.例如，關(guān)系運(yùn)算符替換算子(relational operator replacement, ROR)對(duì)關(guān)系表達(dá)式xy，x≥y，x==y以及x≠y共5個(gè)變異體.在變異測(cè)試中，如果1個(gè)變異體m與被測(cè)程序p在測(cè)試輸入x上的輸出不同，則稱(chēng)變異體m被測(cè)試輸入x殺死.

盡管變異測(cè)試能為被測(cè)程序生成大量變異體，然而并非所有變異體對(duì)測(cè)試數(shù)據(jù)質(zhì)量的提高都有幫助[12-13].Ammann等人[14-18]的研究表明：現(xiàn)有的變異測(cè)試工具會(huì)生成超過(guò)80%的無(wú)效變異體.這些無(wú)效變異體不僅會(huì)增加測(cè)試成本和執(zhí)行時(shí)間，同時(shí)還會(huì)降低變異分析的有效性，降低測(cè)試質(zhì)量.其中一類(lèi)對(duì)變異測(cè)試影響較大的無(wú)效變異體是等價(jià)變異體[19].

等價(jià)變異體指的是與原程序保持語(yǔ)義等價(jià)的變異體程序[20].這類(lèi)變異體無(wú)法被任何的測(cè)試輸入殺死，既不能有效地模擬故障缺陷，也無(wú)法改進(jìn)測(cè)試數(shù)據(jù)充分性.因此在測(cè)試前，需要將程序中的等價(jià)變異體識(shí)別并移除.圖1展示了一個(gè)示例程序以說(shuō)明變異體的等價(jià)性：mutant-1和mutant-2將運(yùn)算符“<”替換為“≤”生成故障程序.其中mutant-1是非等價(jià)變異體：它會(huì)導(dǎo)致數(shù)組下標(biāo)k越界從而造成程序異常退出.而mutant-2是等價(jià)變異體：該變異體總是輸出數(shù)組的最小值，與原程序的輸出完全一致，因而mutant-2無(wú)法被任意的測(cè)試用例殺死.

Fig. 1 Equivalent mutant and non-equivalent mutant

長(zhǎng)期以來(lái)，等價(jià)變異體識(shí)別是研究領(lǐng)域和工業(yè)界所面臨的一個(gè)主要難題.一方面，通過(guò)人工審查判斷變異體的等價(jià)性平均需要6～15 min[21-23].另一方面，現(xiàn)有技術(shù)[24-32]無(wú)法有效識(shí)別等價(jià)變異體，存在2方面不足：

1) 準(zhǔn)確度低.現(xiàn)有技術(shù)使用不完整的故障特征來(lái)推斷變異體的等價(jià)性，導(dǎo)致識(shí)別技術(shù)產(chǎn)生大量的錯(cuò)分類(lèi)樣例[24-28].

2) 擴(kuò)展性差.以往的研究方法依賴(lài)于人工設(shè)計(jì)的推理規(guī)則，這些規(guī)則只能識(shí)別少量的等價(jià)性模式，如不可達(dá)路徑或數(shù)據(jù)流模式等.對(duì)于實(shí)踐中復(fù)雜多樣的等價(jià)性模式，這類(lèi)技術(shù)的可擴(kuò)展性將受到限制[33].

為了能提高識(shí)別的精準(zhǔn)性和有效性，本文提出了基于故障檢測(cè)上下文的等價(jià)變異體識(shí)別算法.該算法通過(guò)抽取變異體的故障檢測(cè)上下文作為特征，并通過(guò)機(jī)器學(xué)習(xí)對(duì)復(fù)雜特征進(jìn)行分析，從而實(shí)現(xiàn)等價(jià)變異體的自動(dòng)分類(lèi)和識(shí)別.故障檢測(cè)上下文包含了與故障檢測(cè)過(guò)程相關(guān)的程序切片.使用機(jī)器學(xué)習(xí)技術(shù)實(shí)現(xiàn)等價(jià)變異識(shí)別是基于3方面的考慮：

1) 等價(jià)變異體識(shí)別存在數(shù)據(jù)量大、故障特征復(fù)雜的問(wèn)題.傳統(tǒng)的邏輯推理技術(shù)對(duì)復(fù)雜故障的分析能力有限；而統(tǒng)計(jì)學(xué)習(xí)技術(shù)為復(fù)雜特征的大數(shù)據(jù)信息提供了有效的分析手段.

2) 統(tǒng)計(jì)學(xué)習(xí)的分類(lèi)準(zhǔn)確度會(huì)隨著訓(xùn)練樣本的增加而不斷改進(jìn)，從而增強(qiáng)了等價(jià)變異體識(shí)別的有效性和方法的擴(kuò)展性.

3) 現(xiàn)有的機(jī)器學(xué)習(xí)研究提供了大量成熟的機(jī)器學(xué)習(xí)模型庫(kù)，為本文快速和有效地實(shí)現(xiàn)等價(jià)變異體分類(lèi)提供了技術(shù)上的保障.

我們將本文提出的方法應(yīng)用于22個(gè)C程序的共計(jì)118 000個(gè)變異體進(jìn)行評(píng)估.實(shí)驗(yàn)結(jié)果表明：

1) 在5-折交叉驗(yàn)證中，基于故障檢測(cè)上下文的等價(jià)變異識(shí)別算法取得93%的預(yù)測(cè)準(zhǔn)確率(accuracy).

2) 在跨工程間驗(yàn)證中，基于故障檢測(cè)上下文的技術(shù)取得77%以上的分類(lèi)精準(zhǔn)度(precision)和78%的召回率(recall).

1 相關(guān)工作

長(zhǎng)期以來(lái)，等價(jià)變異識(shí)別問(wèn)題不僅是阻礙變異測(cè)試被工業(yè)界廣泛應(yīng)用的關(guān)鍵原因；同時(shí)也是變異測(cè)試領(lǐng)域的主要難題.造成該問(wèn)題未被攻克的原因有：

1) 等價(jià)變異體數(shù)量巨大.根據(jù)Yao等人[30]的實(shí)驗(yàn)研究數(shù)據(jù)，等價(jià)變異體的數(shù)量占變異體總量的10%～15%.

2) 人工等價(jià)性檢測(cè)耗時(shí).Schuler等人[21]的研究報(bào)告指出，人工判斷變異體等價(jià)性平均需要6～15 min.

3) 自動(dòng)識(shí)別等價(jià)變異異常困難.研究者們已經(jīng)證明，等價(jià)變異檢測(cè)是不可解問(wèn)題.這意味著對(duì)任一被測(cè)程序p和變異體m，不存在算法A能準(zhǔn)確地判斷m的等價(jià)性[20].

一方面，通過(guò)人工手段從大量樣本中確認(rèn)等價(jià)變異體是不切實(shí)際的；另一方面，由于等價(jià)變異體識(shí)別問(wèn)題的不可判定性，使得到目前為止，尚不存在能有效檢測(cè)等價(jià)變異體的技術(shù)工具.因此，在實(shí)踐中，研究者們只能近似地解決該問(wèn)題：要么為特定變異算子設(shè)計(jì)相對(duì)精準(zhǔn)的等價(jià)變異體識(shí)別規(guī)則，要么設(shè)計(jì)一個(gè)面向通用故障類(lèi)型的近似算法.前者可以取得較高的檢測(cè)精度，但是可擴(kuò)展性較差；而后者雖然適用于大部分實(shí)踐中的被測(cè)軟件，但是精準(zhǔn)度較差.為了開(kāi)發(fā)有效的等價(jià)變異體識(shí)別算法，Madeyski等人[19]為該算法提出了2方面的需求：

1) 精確性需求.要求通過(guò)算法A檢測(cè)出的變異體均為等價(jià)變異體.令D為算法A識(shí)別的等價(jià)變異體集，E為實(shí)際的等價(jià)變異體集.精確性要求算法A具有高精確率P，其中P的定義為

(1)

2) 可用性需求.要求被測(cè)程序的大部分等價(jià)變異體都被算法A檢測(cè)出來(lái).換言之，要求算法A具有高召回率R，其中R的定義為

(2)

Madeyski等人[19]對(duì)30年來(lái)等價(jià)變異體相關(guān)工作進(jìn)行了系統(tǒng)性的分類(lèi)和總結(jié)，將現(xiàn)有的等價(jià)變異體識(shí)別技術(shù)分為5組，分別是：

1) 基于編譯優(yōu)化的等價(jià)變異檢測(cè)方法[27-28]；

2) 基于程序約束的等價(jià)變異檢測(cè)方法[24-26]；

3) 基于程序影響的等價(jià)變異體選擇方法[21-22]；

4) 基于層次關(guān)系的等價(jià)變異體優(yōu)化方法[15-16]；

5) 基于變異算子的等價(jià)變異體選擇方法[29-30].

其中，基于編譯優(yōu)化和程序約束的等價(jià)變異體檢測(cè)算法通過(guò)形式化驗(yàn)證和程序證明技術(shù)，嚴(yán)格論證程序間的等價(jià)關(guān)系，具有較高的精準(zhǔn)性.然而，由于形式驗(yàn)證通常依賴(lài)于人工設(shè)計(jì)的推理規(guī)則，使得這類(lèi)方法通常適用于識(shí)別復(fù)雜度較低的等價(jià)變異體；對(duì)于復(fù)雜的等價(jià)性模式，該算法的召回率較低.

此外，基于程序影響和變異算子的等價(jià)變異體選擇算法通過(guò)經(jīng)驗(yàn)研究和統(tǒng)計(jì)分析等手段，從大量的樣例中挖掘等價(jià)變異體的算子和程序影響模式.然而，現(xiàn)有技術(shù)依賴(lài)于人工特征建模，提取的特征相對(duì)單一，難以確保挖掘到的等價(jià)變異體特征是否適用于更復(fù)雜的被測(cè)程序，其精準(zhǔn)度和泛用性受到限制[19].

表1總結(jié)了現(xiàn)有等價(jià)變異體識(shí)別算法的精確率、召回率及其存在的缺陷.可以發(fā)現(xiàn)，現(xiàn)有的等價(jià)變異檢測(cè)技術(shù)無(wú)法同時(shí)取得較高的精確率和召回率.為了提高等價(jià)變異體識(shí)別的精準(zhǔn)性和有效性，本文將提出基于故障檢測(cè)上下文的等價(jià)變異體識(shí)別算法.

Table 1 Existing Equivalent Mutant Detection Algorithms

2 故障檢測(cè)上下文

2.1 故障檢測(cè)上下文與等價(jià)變異體

在軟件測(cè)試中，故障檢測(cè)條件描述了測(cè)試用例為殺死變異體需要滿(mǎn)足的約束，包括[20]：

1) 覆蓋約束.故障所在的語(yǔ)句被測(cè)試用例覆蓋.

2) 觸發(fā)約束.故障語(yǔ)句的執(zhí)行觸發(fā)運(yùn)行時(shí)錯(cuò)誤.

3) 傳播約束.運(yùn)行時(shí)錯(cuò)誤傳播并改變程序輸出.

給定變異體m和被測(cè)程序p，令CR，CI，CP表示變異體m的覆蓋、觸發(fā)和傳播約束，則變異體m的檢測(cè)條件可以描述為

CR∧CI∧CP.

(3)

基于約束的等價(jià)變異體識(shí)別算法[25]通過(guò)驗(yàn)證該約束條件的可滿(mǎn)足性來(lái)判斷變異等價(jià)性.在實(shí)踐中，為了提取故障檢測(cè)條件，開(kāi)發(fā)者需要通過(guò)靜態(tài)分析工具，從源碼中提取與檢測(cè)條件相關(guān)的代碼來(lái)推斷變異體的等價(jià)性.本文將與檢測(cè)條件相關(guān)的程序切片稱(chēng)為故障檢測(cè)上下文(fault detection context, FDC).FDC為判斷故障的可檢測(cè)性提供了證據(jù)信息，是識(shí)別等價(jià)變異體的前提條件[26].

圖2展示了圖1中mutant-1和mutant-2的故障檢測(cè)上下文.其中，mutant-1的檢測(cè)上下文不包括語(yǔ)句min=Integer.Maximal和returnmin；而mutant-2的上下文移除了無(wú)關(guān)語(yǔ)句length=list.Length.

Fig. 2 Fault detection context for mutants

通過(guò)分析mutant-1的FDC中for語(yǔ)句k=0，k++可以證明，變異體k≤length必然在k==length時(shí)引發(fā)運(yùn)行時(shí)錯(cuò)誤，執(zhí)行循環(huán)語(yǔ)句體；同時(shí)，通過(guò)分析循環(huán)體的list[k]

與此同時(shí)，通過(guò)分析mutant-2的FDC可以發(fā)現(xiàn)，當(dāng)list[k]==min時(shí)，雖然故障條件list[k]≤min會(huì)錯(cuò)誤地執(zhí)行賦值語(yǔ)句min=list[k]，但是該賦值對(duì)最終結(jié)果沒(méi)有影響，故mutant-2是等價(jià)變異體.

在上面的分析中，故障檢測(cè)上下文為推斷變異體的等價(jià)性提供了證據(jù)信息.對(duì)任一等價(jià)變異體識(shí)別技術(shù)而言，一個(gè)重要的技術(shù)瓶頸是如何自動(dòng)地抽取故障檢測(cè)上下文，以提高識(shí)別準(zhǔn)確率.本節(jié)將提供FDC的形式定義，以支持故障檢測(cè)上下文的自動(dòng)抽取.

2.2 故障檢測(cè)上下文與程序依賴(lài)圖

故障檢測(cè)上下文是故障注入點(diǎn)的依賴(lài)子圖.下面回顧程序依賴(lài)圖[34-36]的定義.

定義1.控制流程圖.令p為被測(cè)程序，p的控制流圖(control flow graph, CFG)是一個(gè)多元組，記作CFG=(p,N,E,entry,exit).其中，N為程序p的語(yǔ)句集，表示控制流圖的節(jié)點(diǎn)；E為控制流圖的有向邊，滿(mǎn)足(x,y)∈E當(dāng)且僅當(dāng)語(yǔ)句y可能在x后被執(zhí)行；entry和exit分別是程序入口和出口節(jié)點(diǎn).

定義2.控制支配關(guān)系.給定程序p的控制流圖CFG，語(yǔ)句x被語(yǔ)句y后向支配，當(dāng)且僅當(dāng)所有從x到出口exit的路徑都經(jīng)過(guò)y，意味著y是x到程序出口的必經(jīng)點(diǎn).

定義3.控制依賴(lài)關(guān)系.令x和y是程序p的2條語(yǔ)句，定義y控制依賴(lài)于x，記作y→Cx，當(dāng)且僅當(dāng)：1)存在1條從x到y(tǒng)的路徑，其中y后向支配路徑上除x外的所有語(yǔ)句；2)x不被y后向支配.其中，控制依賴(lài)關(guān)系滿(mǎn)足傳遞性，有

(x→Cy)∧(y→Cz)?(x→Cz).

(4)

定義4.直接控制依賴(lài)關(guān)系.給定語(yǔ)句x和y，稱(chēng)y直接控制依賴(lài)于x，記作y→DCx，當(dāng)且僅當(dāng)y→Cx，且不存在其他語(yǔ)句z使y→Cz且z→Cx.在結(jié)構(gòu)化程序中，直接控制依賴(lài)關(guān)系y→DCx意味著x往往是1個(gè)分支條件，而y是該條件的真分支或假分支上必經(jīng)的某條語(yǔ)句.

定義5.數(shù)據(jù)依賴(lài)關(guān)系.令U(s)表示語(yǔ)句s中使用的變量集，D(t)表示語(yǔ)句t中被定義(或賦值)的變量集；定義直接數(shù)據(jù)依賴(lài)s→DD[x]t，使得存在x∈U(s)且x∈D(t)，且存在1條從t到s的路徑，使得該路徑上沒(méi)有其他語(yǔ)句對(duì)變量x進(jìn)行再賦值.其中，直接數(shù)據(jù)依賴(lài)關(guān)系表示變量x在語(yǔ)句s中的使用值是在語(yǔ)句t中被定義的.

定義6.程序依賴(lài)圖(program dependence graph, PDG).PDG是一個(gè)有向圖G=(N,E)，其中N為程序語(yǔ)句集，關(guān)系集E包括：

1) 控制依賴(lài)邊(s,c,b)，c為分支條件而b為布爾值，表示從c到s是真分支還是假分支；

2) 數(shù)據(jù)依賴(lài)邊(s,t,x)，其中s通過(guò)使用變量x直接數(shù)據(jù)依賴(lài)于t.

圖3展示了圖1中的案例程序的程序依賴(lài)圖.其中，分支條件k

Fig. 3 Program dependence graph

基于程序依賴(lài)圖模型的概念，下面引入k階依賴(lài)子圖.

定義7.控制依賴(lài)子圖.給定程序依賴(lài)圖G以及語(yǔ)句s，定義語(yǔ)句s的k階依賴(lài)子圖(k≥0)是G的一個(gè)子圖，記作Gs,k=(s,Ns,k,Es,k)，其中Ns,k和Es,k表示子圖的節(jié)點(diǎn)集和有向邊集，它們滿(mǎn)足

Ns,k={t|?e∈Es,k,t∈e},

(5)

Es,k={e|?p∈Ps,k,e∈p},

(6)

其中Ps,k是依賴(lài)圖G的一個(gè)簡(jiǎn)單路徑子集，滿(mǎn)足

(7)

Fig. 4 First-order dependence subgraph example

在定義7中，ps,t是程序依賴(lài)圖中一條從s到t的簡(jiǎn)單路徑；該路徑不包含重復(fù)的有向邊.從定義7不難發(fā)現(xiàn)，路徑集Ps,k包含了所有從s出發(fā)或者到達(dá)s的長(zhǎng)度不大于k的簡(jiǎn)單路集.而k階依賴(lài)子圖包含依賴(lài)圖中以s為中心、距離為k以?xún)?nèi)的節(jié)點(diǎn)和邊.作為例子，考慮圖4中l(wèi)ist[k]

在圖4中故障語(yǔ)句list[k]

從上述分析不難看出，k階依賴(lài)子圖能自動(dòng)識(shí)別與檢測(cè)條件相關(guān)的語(yǔ)句及依賴(lài)關(guān)系，因此本文將故障語(yǔ)句的k階依賴(lài)子圖定義為故障檢測(cè)上下文.

定義8.故障檢測(cè)上下文.令oprt為變異算子，s為變異體m的注入語(yǔ)句，m的故障檢測(cè)上下文定義為二元組FDCm=(oprt,Gs,k)，其中Gs,k是以s為中心的k階依賴(lài)子圖.

Fig. 5 Second-order dependence graph example

2.3 故障檢測(cè)上下文與依賴(lài)鏈長(zhǎng)度

在定義8中，非負(fù)整數(shù)k是一個(gè)由用戶(hù)指定的超參數(shù)，關(guān)于k的選擇將會(huì)影響FDCm的特征有效性.當(dāng)k太小時(shí)，F(xiàn)DCm表示力不足；而k太大時(shí)，F(xiàn)DCm中將包含大量的依賴(lài)路徑鏈，其中只有極少部分被用于等價(jià)變異體判定，導(dǎo)致FDCm包含了太多噪音信息，進(jìn)而降低算法有效性.

圖5通過(guò)圖1中mutant-1的二階依賴(lài)子圖說(shuō)明了這一問(wèn)題.其中灰色節(jié)點(diǎn)為論證變異體的等價(jià)性提供了證據(jù)信息，其他無(wú)色節(jié)點(diǎn)為沒(méi)有使用到的信息.

不難發(fā)現(xiàn)，大部分對(duì)等價(jià)變異體識(shí)別過(guò)程有幫助的語(yǔ)句和依賴(lài)關(guān)系與故障注入點(diǎn)的距離都比較近，都在一階依賴(lài)子圖范圍內(nèi).為了降低特征表示的復(fù)雜度以及分析的有效性，在實(shí)驗(yàn)評(píng)估中本文限制k=2.

3 等價(jià)變異體識(shí)別算法

故障檢測(cè)上下文特征為推斷變異體等價(jià)性提供了充分的分析信息.因此理論上可以通過(guò)邏輯推理和形式驗(yàn)證技術(shù)，在FDC的基礎(chǔ)上實(shí)現(xiàn)等價(jià)變異體檢測(cè).然而，邏輯推理技術(shù)強(qiáng)烈地依賴(lài)于人工設(shè)計(jì)的推導(dǎo)規(guī)則；這些規(guī)則通常只能通過(guò)簡(jiǎn)單的上下文模式識(shí)別等價(jià)變異體，對(duì)復(fù)雜模式，其可擴(kuò)展性將受到限制.

為了能在故障檢測(cè)上下文的基礎(chǔ)上有效地識(shí)別等價(jià)變異，本文提出采用統(tǒng)計(jì)學(xué)習(xí)技術(shù)實(shí)現(xiàn)基于FDC的等價(jià)變異體識(shí)別算法.其理由為：首先，等價(jià)變異體存在數(shù)量大、特征復(fù)雜等問(wèn)題，而統(tǒng)計(jì)學(xué)習(xí)技術(shù)為分析復(fù)雜特征的大數(shù)據(jù)信息提供了有效的分析手段；其次，統(tǒng)計(jì)學(xué)習(xí)的分類(lèi)準(zhǔn)確度會(huì)隨著訓(xùn)練樣本的增加而不斷改進(jìn)，增強(qiáng)了識(shí)別方法的可用性和擴(kuò)展性；最后，現(xiàn)有的機(jī)器學(xué)習(xí)研究提供了大量成熟的機(jī)器學(xué)習(xí)模型庫(kù)，為本文快速和有效地實(shí)現(xiàn)等價(jià)變異體分類(lèi)提供了技術(shù)上的支持.

3.1 算法流程

圖6展現(xiàn)了該算法的流程圖，包括訓(xùn)練樣本標(biāo)簽化、故障特征提取、故障特性文檔化、訓(xùn)練分類(lèi)器以及變異體分類(lèi)5個(gè)子過(guò)程.

Fig. 6 FDC-based equivalent mutant detection flowchat

樣本標(biāo)簽化過(guò)程通過(guò)人工輔助的軟件測(cè)試手段，識(shí)別訓(xùn)練樣本中的每一個(gè)變異體m是否為等價(jià)變異體，輸出是一個(gè)帶標(biāo)簽的二元組(m,y)，其中y為布爾值，表示m是否為等價(jià)變異體.

故障特征提取過(guò)程通過(guò)程序依賴(lài)分析提取變異體依賴(lài)子圖，作為變異體m故障檢測(cè)上下文FDCm.接著，故障特征文檔化過(guò)程將結(jié)構(gòu)化的故障檢測(cè)上下文轉(zhuǎn)換為故障檢測(cè)文檔(fault detection document, FDD)，該文檔是一個(gè)以自然文本描述故障檢測(cè)上下文的語(yǔ)句集，記作FDDm.該文檔將結(jié)構(gòu)化的程序分析問(wèn)題轉(zhuǎn)換為文本分類(lèi)問(wèn)題，并使用現(xiàn)成的統(tǒng)計(jì)學(xué)習(xí)模型進(jìn)行分析，將變異體分類(lèi)為等價(jià)或非等價(jià).

接下來(lái)將解釋故障檢測(cè)文檔的模型定義、故障檢測(cè)上下文到故障檢測(cè)文檔的轉(zhuǎn)換規(guī)則，以及統(tǒng)計(jì)學(xué)習(xí)技術(shù)如何使用故障文檔模型識(shí)別等價(jià)變異體.

3.2 故障檢測(cè)文檔

故障檢測(cè)文檔是由句子(sentence)構(gòu)成的集合

FDDm={S1,S2,…,SD},

(8)

其中，每個(gè)句子Si是一個(gè)由單詞(word)構(gòu)成的不定長(zhǎng)序列，用于描述k階依賴(lài)子圖中一條以故障注入點(diǎn)s為起點(diǎn)或終點(diǎn)的依賴(lài)關(guān)系鏈，表示為

Si=(wi,1,wi,2,…,wi,n-1,wi,n).

(9)

在該定義中序列Si的一個(gè)單詞wi,j表示依賴(lài)關(guān)系鏈上的一個(gè)節(jié)點(diǎn)或節(jié)點(diǎn)之間的關(guān)系.其中，節(jié)點(diǎn)單詞描述節(jié)點(diǎn)的抽象語(yǔ)法樹(shù)類(lèi)型，而關(guān)系單詞描述語(yǔ)句與語(yǔ)句、語(yǔ)句與變量的關(guān)系.表2列出了一部分節(jié)點(diǎn)和關(guān)系的對(duì)應(yīng)描述單詞.

Table 2 Objects in FDD and Words for Describing

作為例子，考慮圖5中的3條依賴(lài)關(guān)系路徑，分別是list[k]

以第1條依賴(lài)路徑為例，路徑的起始點(diǎn)對(duì)應(yīng)變異體，其單詞(<,≤)表示變異算子；接著，變異節(jié)點(diǎn)連接到故障注入點(diǎn)list[k]

Fig. 7 Fault detection document example

使用故障檢測(cè)文檔作為故障特征輸入的原因有2方面：

首先，從機(jī)器學(xué)習(xí)模型的角度出發(fā)，序列化的文檔模型適用于大部分現(xiàn)有的且成熟的機(jī)器學(xué)習(xí)模型.這類(lèi)模型對(duì)數(shù)據(jù)量和樣本輸入的魯棒性更強(qiáng)；而以結(jié)構(gòu)化特征為輸入的模型如神經(jīng)網(wǎng)絡(luò)，對(duì)輸入數(shù)據(jù)量的要求則更高.從實(shí)用性的角度，直接以結(jié)構(gòu)化的故障檢測(cè)上下文作為特征未必能取得比故障檢測(cè)文檔更好的分類(lèi)效果.

其次，從等價(jià)變異體識(shí)別角度考慮，結(jié)構(gòu)化的故障上下文特征要求使用抽象的推理規(guī)則和形式驗(yàn)證技術(shù)，使得等價(jià)變異分類(lèi)器的可擴(kuò)展性受到限制.而通過(guò)將故障檢測(cè)上下文轉(zhuǎn)換為故障檢測(cè)文檔，等價(jià)變異體識(shí)別問(wèn)題被轉(zhuǎn)換為了相對(duì)簡(jiǎn)單的文本分類(lèi)問(wèn)題，而后者提供了相對(duì)簡(jiǎn)單的推理規(guī)則，確保模型的簡(jiǎn)易和泛用性.

3.3 故障特征編碼

大部分現(xiàn)有的機(jī)器學(xué)習(xí)模型，如貝葉斯網(wǎng)絡(luò)、支持向量機(jī)、隨機(jī)森林或多層感知器，都是以一個(gè)定長(zhǎng)的實(shí)值向量作為特征輸入；而在3.2節(jié)中引入的故障文檔模型卻包含了可變數(shù)量的語(yǔ)句和單詞.為此，在訓(xùn)練分類(lèi)器之前，需要將故障文檔FDDm轉(zhuǎn)換為一個(gè)定長(zhǎng)的實(shí)數(shù)向量Xm.故障檢測(cè)文檔的特征編碼分為3個(gè)階段，分別是預(yù)處理、句編碼和文檔編碼.

3.3.1 預(yù)處理

在預(yù)處理階段，故障檢測(cè)文檔中表示節(jié)點(diǎn)和邊的單詞會(huì)被重組，以構(gòu)成表示具有完整語(yǔ)義信息的關(guān)系組合詞.具體而言，在一個(gè)依賴(lài)路徑中，設(shè)nx和ny為相鄰節(jié)點(diǎn)對(duì)應(yīng)單詞，ex,y連接從nx到ny的依賴(lài)關(guān)系的對(duì)應(yīng)單詞，則nx和ny的關(guān)系組合詞為

wx,y=nx·ex,y·ny,

(10)

其中‘·’表示字符串連接操作.

對(duì)于一個(gè)給定的語(yǔ)句，其詞序列為(n1,e1,2,n2,e2,3,n3,…,er-1,r,nr).經(jīng)過(guò)預(yù)處理后，該序列的單詞組合為關(guān)系詞組，有

Si=(w1,2,w2,3,…,wk,k+1,…,wr-1,r),

(11)

其中wk,k+1=nk·ek,k+1·nk+1表示關(guān)系組合詞.

將鄰接節(jié)點(diǎn)組合起來(lái)的思想是基于這一觀察：在依賴(lài)路徑中，單獨(dú)表示節(jié)點(diǎn)和邊的單詞無(wú)法描述“依賴(lài)關(guān)系”的語(yǔ)義.而鄰接點(diǎn)的關(guān)系組合詞能表示依賴(lài)鏈中一個(gè)最基本的連接關(guān)系語(yǔ)義，這將有效地提升特征編碼的表達(dá)能力.

3.3.2 句編碼

在故障檢測(cè)文檔中，一個(gè)語(yǔ)句描述了從故障注入點(diǎn)出發(fā)(或終止)的一條完整依賴(lài)鏈；其中每個(gè)單詞表示依賴(lài)鏈中的一條依賴(lài)邊.對(duì)于由一組特定順序構(gòu)成的依賴(lài)鏈，它往往描述了特殊的故障檢測(cè)上下文結(jié)構(gòu).如圖7中第3行的依賴(lài)鏈描述了變異體對(duì)程序的影響方式，首先通過(guò)對(duì)變量min賦值，然后通過(guò)返回語(yǔ)句影響外部輸出.

顯然，每個(gè)語(yǔ)句都表示某種特定的“主題”，如故障通過(guò)某種方式影響外部變量，或者通過(guò)某條特殊路徑被覆蓋.語(yǔ)句編碼的目的是將這種主題語(yǔ)義從詞序列中抽離出來(lái)，以向量的形式進(jìn)行表示.這種向量被稱(chēng)為句向量(sentence vector)[37].

在自然語(yǔ)言處理領(lǐng)域doc2vec[38]是一種自動(dòng)抽取句向量的機(jī)器學(xué)習(xí)算法.該算法的基本思想是，在給定算法的部分單詞的條件下，根據(jù)算法的主題語(yǔ)義向量，可以恢復(fù)出剩余空缺單詞.

圖8展示了doc2vec基于分布式存儲(chǔ)(distributed memory)的實(shí)現(xiàn).以圖7中第3行語(yǔ)句為例，如果去除最后一個(gè)min到returnmin的依賴(lài)關(guān)系，使用doc2vec生成的句向量可以從其他依賴(lài)關(guān)系后恢復(fù)出該依賴(lài)關(guān)系，這意味著“通過(guò)返回語(yǔ)句影響程序”的語(yǔ)義信息已經(jīng)被抽取到了該語(yǔ)句的句向量中.給定依賴(lài)路徑的語(yǔ)句Si，doc2vec算法將輸入語(yǔ)句Si轉(zhuǎn)換為一個(gè)固定長(zhǎng)度的句向量，記作Di.

Fig. 8 Distributed memory model in doc2vec

3.3.3 文檔編碼

在句向量編碼完成后，故障檢測(cè)文檔被轉(zhuǎn)換為由一組句向量Di構(gòu)成的集合，記作

FDDm={D1,D2,…,Dn}.

(12)

在等價(jià)變異體分析中，并非所有的語(yǔ)句(依賴(lài)鏈)都被用于論證變異體的等價(jià)性.正如2.3節(jié)圖5的案例所展示的那樣，故障檢測(cè)上下文中，一部分依賴(lài)關(guān)系起著關(guān)鍵，而另一些依賴(lài)關(guān)系則幾乎毫無(wú)幫助.基于這一觀察，可以假設(shè)變異體的特征向量是其檢測(cè)文檔中句向量的加權(quán)和，滿(mǎn)足

(13)

其中，參數(shù)αi表示每個(gè)語(yǔ)句的權(quán)重，權(quán)重參數(shù)是非負(fù)實(shí)數(shù)，其總和為1.在等價(jià)變異體識(shí)別過(guò)程中，權(quán)重越大的語(yǔ)句表示故障檢測(cè)上下文中對(duì)論證變異體等價(jià)性越關(guān)鍵的依賴(lài)路徑；反之，權(quán)重越小的語(yǔ)句表示對(duì)論證等價(jià)性幫助越小的路徑；權(quán)重等于0表示該依賴(lài)路徑對(duì)在論證等價(jià)變異體中沒(méi)有幫助.

本文采用了基于注意力機(jī)制的全連接網(wǎng)絡(luò)，實(shí)現(xiàn)對(duì)文檔向量的表示學(xué)習(xí).圖9展示了這種基于注意力機(jī)制的表示學(xué)習(xí)網(wǎng)絡(luò)的整體框架[39-40].

Fig. 9 Attention-based document embedding networks

首先，故障檢測(cè)文檔的所有語(yǔ)句通過(guò)doc2vec算法映射到一組句向量，這組句向量大小是可變的.由于注意力權(quán)重向量通常是定長(zhǎng)的(設(shè)為n)，這里采用截?cái)嗖呗裕毫罟收衔臋n包含d個(gè)句子，如果dn，只取前n個(gè)句向量，而忽略多余的d-n個(gè)句子信息.

接著，通過(guò)一個(gè)注意力權(quán)重網(wǎng)絡(luò)注意力權(quán)重計(jì)算每個(gè)句向量的權(quán)重αi.其中，注意力網(wǎng)絡(luò)定義了一個(gè)長(zhǎng)度為n的注意力向量，記作β.對(duì)每個(gè)句向量Di其權(quán)重計(jì)算為

(14)

從式(14)不難看出，各個(gè)語(yǔ)句的權(quán)重總和為1.

Fig. 10 Feature-based equivalent mutation detection

在完成了權(quán)重計(jì)算后，根據(jù)式(13)求出故障檢測(cè)文檔的特征向量Xm.最后Xm通過(guò)一個(gè)Sigmoid函數(shù)映射到概率Pm.這一概率表示變異體m為等價(jià)變異體的概率.概率Pm被進(jìn)一步與變異體的類(lèi)別label進(jìn)行比較，并計(jì)算成本函數(shù)：

(15)

其中,N表示訓(xùn)練樣本總數(shù)，ym表示m的類(lèi)別標(biāo)簽，ym=1表示m為等價(jià)變異體.式(15)計(jì)算N個(gè)樣例中被正確分類(lèi)的訓(xùn)練樣本比例，對(duì)應(yīng)于分類(lèi)精確率.在獲得成本函數(shù)值之后，根據(jù)神經(jīng)網(wǎng)絡(luò)的反向傳遞算法，進(jìn)一步優(yōu)化注意力權(quán)重和Sigmoid網(wǎng)絡(luò)參數(shù)，進(jìn)而得到最優(yōu)的文檔表示學(xué)習(xí)網(wǎng)絡(luò).

3.4 機(jī)器學(xué)習(xí)分類(lèi)

在獲得了故障特征向量Xm后，這些故障特征被進(jìn)一步用作一系列機(jī)器學(xué)習(xí)分類(lèi)器的輸入.在本文中，將會(huì)考慮貝葉斯、邏輯回歸、決策樹(shù)、隨機(jī)森林、梯度上升、多層感知器等分類(lèi)器以實(shí)現(xiàn)基于故障檢測(cè)上下文的等價(jià)變異體識(shí)別技術(shù).

4 與現(xiàn)有技術(shù)的比較

基于特征的變異體分類(lèi)算法為評(píng)估故障特征以及等價(jià)變異體識(shí)別算法的有效性提供了分析框架.令被測(cè)程序p的變異體集合為M.基于特征的等價(jià)變異體識(shí)別方法會(huì)為每個(gè)變異體m定義一個(gè)故障特征x，所有這些特征的集合稱(chēng)為特征空間F.定義F上的特征提取函數(shù)Φ:M→F，使得函數(shù)Φ(m)返回m在F中的特征點(diǎn)x.

給定變異體在F中的特征點(diǎn)x，引入特征分類(lèi)函數(shù)Ψ:F→{0,1}，該函數(shù)負(fù)責(zé)根據(jù)故障特征x判斷其對(duì)應(yīng)變異體是否為等價(jià)變異.Ψ(x)=1表示具有特征x的變異體為等價(jià)變異體.

通過(guò)組合特征提取函數(shù)Φ和等價(jià)分類(lèi)函數(shù)Ψ，一個(gè)等價(jià)變異體識(shí)別算法可以通過(guò)下面的復(fù)合函數(shù)抽象表示出來(lái)：

y=Ψ(Φ(m))，

(16)

其中y為算法預(yù)測(cè)的變異體m的類(lèi)別.

現(xiàn)有的等價(jià)變異體識(shí)別技術(shù)以及本文提出的基于故障檢測(cè)上下文的識(shí)別算法都可以看作是基于特征的變異體分類(lèi)算法的某種具體實(shí)現(xiàn)，如圖10所示.

其中，基于選擇變異的實(shí)現(xiàn)方案使用最單一的特征(變異算子)和最寬松的判定條件(相關(guān)性分析)判定等價(jià)變異體，極大地降低了分類(lèi)的準(zhǔn)確性.而基于約束求解的實(shí)現(xiàn)方法使用過(guò)度抽象和復(fù)雜的符號(hào)表示作為特征，增加了分類(lèi)算法實(shí)現(xiàn)的難度，極大地限制了算法的適用范圍，降低了召回率.

相比之下，本文提出的等價(jià)變異體識(shí)別算法以故障檢測(cè)上下文為輸入，確保了故障特征的復(fù)雜性和信息量.同時(shí)，通過(guò)統(tǒng)計(jì)學(xué)習(xí)技術(shù)，自動(dòng)化構(gòu)建等價(jià)變異分類(lèi)器，簡(jiǎn)化了算法實(shí)現(xiàn)，提高了可擴(kuò)展性.

在現(xiàn)實(shí)中，研究者們往往希望近似地推斷變異體的等價(jià)性.這意味著對(duì)于給定的被測(cè)程序及其變異體樣本集M，能最大化其在樣本集上的識(shí)別準(zhǔn)確度(accuracy).accuracy的定義為

(17)

其中，謂詞equiv(m)表示m為等價(jià)變異體.給定特征空間F和特征提取函數(shù)Φ，定義一個(gè)最優(yōu)等價(jià)判定函數(shù)Ψ*，使得復(fù)合函數(shù)Ψ*(Φ(m))在任意變異體構(gòu)成的集合M上實(shí)現(xiàn)分類(lèi)精確率的最大化，有

Ψ*:maxaccuracy.

(18)

對(duì)一個(gè)大小有限的給定的變異體集M，可以證明，總存在一個(gè)可以實(shí)現(xiàn)最優(yōu)等價(jià)判定函數(shù)Ψ*的算法.算法1給出其基本原理：令Mx為集合M中符合特征點(diǎn)x的變異體子集；當(dāng)Mx中等價(jià)變異體個(gè)數(shù)大于或等于非等價(jià)變異體個(gè)數(shù)時(shí)，可以將特征點(diǎn)x映射到1；反之則將特征點(diǎn)x映射到0.算法1的基本思想是通過(guò)最小化集合Mx中的誤分類(lèi)樣本數(shù)來(lái)最大化預(yù)測(cè)精確率.其中，Ex和Nx分別表示Mx中等價(jià)和非等價(jià)變異體構(gòu)成的集合.

算法1.有限樣本集上的最優(yōu)等價(jià)分類(lèi)算法.

① functiondetermine_euivalence(x):

②Mx={M中符合特征x的變異體};

③Ex={Mx中的等價(jià)變異體};

④Nx={Mx中的非等價(jià)變異體};

⑤ if |Ex|≥|Nx|:

⑥ return true;

⑦ else

⑧ return false;

⑨ end if

⑩ end function

需要注意的是，算法1不是一個(gè)實(shí)用化的算法，它的目的是衡量故障特征F對(duì)等價(jià)變異體識(shí)別的有效性：在一組測(cè)試樣本集M上，算法1的最優(yōu)分類(lèi)所取得的精確率是任一分類(lèi)函數(shù)在樣本集M上該特征所能取得的最大精確率.

一個(gè)好的特征空間應(yīng)該保證對(duì)于任意的特征點(diǎn)x，其對(duì)應(yīng)的變異體中大部分要么都是等價(jià)的，要么都是非等價(jià)的.這要求從特征點(diǎn)x到變異等價(jià)性的映射關(guān)系的隨機(jī)性應(yīng)該盡可能地小.在后面的分析中，還將用特征點(diǎn)的熵(混亂度)來(lái)評(píng)估x的好壞，有

H(x)=-pe×lb(pe)-(1-pe)×lb(pe),

(19)

其中pe表示Mx中等價(jià)變異體所占比例.當(dāng)pe=1或者pe=0時(shí)，有H(x)=0，此時(shí)特征點(diǎn)對(duì)應(yīng)的所有變異樣本都對(duì)應(yīng)到等價(jià)或者非等價(jià)，也因此從x到等價(jià)性的映射關(guān)系是完全確定的.當(dāng)pe=0.5時(shí)，H(x)=1且最大化；此時(shí)無(wú)法判斷具有特征x的變異體是屬于等價(jià)變異體還是非等價(jià)變異體.

5 實(shí)驗(yàn)評(píng)估

為了驗(yàn)證本文提出的基于故障檢測(cè)上下文的等價(jià)變異識(shí)別方法的有效性以及可用性，我們進(jìn)行了一個(gè)實(shí)驗(yàn)研究.本文提出了3個(gè)研究問(wèn)題來(lái)估計(jì)提出方法的有效性.

Q1. 在等價(jià)變異體的識(shí)別問(wèn)題中，故障檢測(cè)上下文是否是好的故障特征表示.

Q2. 哪一類(lèi)機(jī)器學(xué)習(xí)模型更適用于基于故障檢測(cè)上下文的等價(jià)變異程序的識(shí)別任務(wù).

Q3. 相比于現(xiàn)有技術(shù)，基于故障檢測(cè)上下文的等價(jià)變異識(shí)別是否具有更好的精確率和泛用度.

5.1 實(shí)驗(yàn)程序

本文使用了來(lái)自22個(gè)C程序、共計(jì)118 000個(gè)變異體樣例作為訓(xùn)練樣本，來(lái)構(gòu)造適用于等價(jià)變異體識(shí)別任務(wù)的機(jī)器學(xué)習(xí)分類(lèi)器.表3列出了實(shí)驗(yàn)中使用到的程序、代碼復(fù)雜度以及變異體個(gè)數(shù).

實(shí)驗(yàn)中我們使用C程序變異測(cè)試工具Proteum[41]實(shí)現(xiàn)對(duì)程序源代碼的自動(dòng)故障注入功能.為了避免生成過(guò)多的樣本數(shù)、減少手工構(gòu)造等價(jià)變異體的成本，本文去除了常量替換和變量替換類(lèi)型的變異算子.根據(jù)以往的研究，這篩選策略能確保測(cè)試的有效性.為識(shí)別訓(xùn)練樣本中每一個(gè)變異體的等價(jià)性，本文使用項(xiàng)目組開(kāi)發(fā)的開(kāi)源變異測(cè)試工具JCMuta①輔助等價(jià)變異體的人工識(shí)別工作.步驟如下：

1) 通過(guò)自動(dòng)化工具生成分支覆蓋測(cè)試用例集T；

2) 在變異體集M上執(zhí)行測(cè)試集T，并將所有被T殺死的變異體標(biāo)記為“非等價(jià)的”；

3) 對(duì)未被殺死的18 526個(gè)變異體，人工分析其是否為等價(jià)變異體.

Table 3 Subject Programs, Test Cases and Mutants Number

為了簡(jiǎn)化人工分析的難度，本文通過(guò)JCMuta工具收集了每個(gè)變異體在測(cè)試過(guò)程中被測(cè)試用例覆蓋和檢測(cè)的程度.具體而言，JCMuta可以統(tǒng)計(jì)某條故障語(yǔ)句是否多少測(cè)試用例覆蓋；如果沒(méi)有測(cè)試用例覆蓋故障語(yǔ)句，則提示用戶(hù)該變異體等價(jià)的原因是因?yàn)檎Z(yǔ)句不可達(dá)；類(lèi)似地，通過(guò)分析程序中間變量的值是否發(fā)生變化，判斷一個(gè)變異體等價(jià)的原因是無(wú)法觸發(fā)狀態(tài)錯(cuò)誤，還是錯(cuò)誤無(wú)法傳播.基于上述分析，通過(guò)2個(gè)月的分析，識(shí)別了11 126個(gè)等價(jià)變異樣例.

最后，通過(guò)使用原型工具JCMuta，我們?yōu)槊恳粋€(gè)變異體提取相應(yīng)的2階依賴(lài)子圖和故障檢測(cè)上下文，并根據(jù)等價(jià)變異體識(shí)別算法將其轉(zhuǎn)換為故障檢測(cè)文檔和特征向量.在實(shí)驗(yàn)中，我們使用scikit-learn的編程庫(kù)搭建機(jī)器學(xué)習(xí)分類(lèi)器.

5.2 Q1. 故障檢測(cè)上下文特征評(píng)估

為了評(píng)估故障檢測(cè)上下文特征的有效性，實(shí)驗(yàn)使用了故障檢測(cè)上下文特征向量的信息熵，采用式(19)來(lái)估計(jì)特征的有效性.特征點(diǎn)的信息熵越大，說(shuō)明基于該特征點(diǎn)對(duì)等價(jià)性判斷的確定性越低.

圖11展示了故障特征向量空間中每個(gè)特征點(diǎn)Xm的信息熵的密度分布函數(shù).從圖11可以發(fā)現(xiàn)，多達(dá)98%的特征向量對(duì)應(yīng)的熵H(x)=0，意味著對(duì)于實(shí)驗(yàn)中使用的大部分故障上下文特征x到等價(jià)性的映射關(guān)系是完全確定的.除此之外，只有約0.7%特征點(diǎn)的信息熵較高，其H(x)>0.50.

Fig. 11 Distribution of entropy of FCD feature points

表4進(jìn)一步展示了，在故障檢測(cè)上下文特征空間以及給定訓(xùn)練樣本中，最優(yōu)分類(lèi)器(算法1)所能取得的精確率、等價(jià)類(lèi)精確率和召回率等信息.其中，最優(yōu)分類(lèi)器能夠取得97.5%的分類(lèi)精確率，取得多于90%的精確率以及91%的召回率.此外，基于故障檢測(cè)上下文的等價(jià)變異識(shí)別方法能取得遠(yuǎn)高于傳統(tǒng)的等價(jià)變異識(shí)別算法的精確率和召回率(關(guān)于傳統(tǒng)方法在等價(jià)變異識(shí)別問(wèn)題中的精確率和召回率見(jiàn)表1).

Table 4 Accuracy, Precision and Recall in Cross-Validation

5.3 Q2.統(tǒng)計(jì)學(xué)習(xí)模型比較

表4展示了在訓(xùn)練樣本交叉驗(yàn)證中，各種機(jī)器學(xué)習(xí)分類(lèi)器在驗(yàn)證集(validation set)所取得的準(zhǔn)確率(accuracy)、精確率(precision)、召回率(recall)信息.對(duì)最優(yōu)分類(lèi)器，我們采用Train-set=Test-set(在訓(xùn)練集上訓(xùn)練和驗(yàn)證)來(lái)驗(yàn)證特征空間有效性.而對(duì)其他機(jī)器學(xué)習(xí)模型，我們采用了2-折和5-折交叉驗(yàn)證技術(shù)去評(píng)估機(jī)器學(xué)習(xí)分類(lèi)器的分類(lèi)準(zhǔn)確率、精確率、召回率.

從表4可以發(fā)現(xiàn)，基于故障檢測(cè)上下文的最優(yōu)分類(lèi)器的精確率是97%，這是所有其他機(jī)器學(xué)習(xí)分類(lèi)器在交叉驗(yàn)證中能夠獲得的最高分?jǐn)?shù).在實(shí)驗(yàn)中使用的學(xué)習(xí)模型中，決策樹(shù)、隨機(jī)森林、梯度上升、Bagging和多層感知器在交叉驗(yàn)證中取得了最佳分類(lèi)效果.其中決策樹(shù)能夠獲得92%的精確率以及83%的等價(jià)類(lèi)精確率；分?jǐn)?shù)最高的多層感知機(jī)取得了90%的識(shí)別精確率，并檢測(cè)了超過(guò)82%的等價(jià)變異體.

此外，通過(guò)比較2-折和5-折交叉驗(yàn)證結(jié)果可以發(fā)現(xiàn)，雖然在2-折驗(yàn)證中，各個(gè)分類(lèi)器的精準(zhǔn)度和召回率都有所下降，但是這一下降并不明顯，意味著本文提出的特征構(gòu)造和編碼方式使得學(xué)習(xí)模型對(duì)訓(xùn)練樣本數(shù)魯棒性相對(duì)較高，有較好的擴(kuò)展性.

5.4 Q3. 模型泛用性評(píng)估

為了驗(yàn)證機(jī)器學(xué)習(xí)模型在訓(xùn)練集以外程序中進(jìn)行等價(jià)變異識(shí)別任務(wù)的泛用性，本文采用了留一工程間驗(yàn)證(leave-one-project, LOP).非形式地，LOP驗(yàn)證每次以訓(xùn)練樣本中的1個(gè)工程的變異體為測(cè)試集，而剩余其他程序的樣本為訓(xùn)練集，進(jìn)行學(xué)習(xí)和預(yù)測(cè).

圖12展示了多層感知機(jī)分類(lèi)器在實(shí)驗(yàn)中使用的22個(gè)被測(cè)程序上的LOP驗(yàn)證的等價(jià)類(lèi)精準(zhǔn)度以及召回率信息.可以發(fā)現(xiàn)，對(duì)于某些被測(cè)的程序，如md5，prime_factor,print_tokens2,replace,space,flex,sed，分類(lèi)器能取得超過(guò)90%的預(yù)測(cè)精確率；然而對(duì)另一些程序，如calendar,triangle,schedule2,gzip，多層感知器取得的精確率甚至低于50%.類(lèi)似地，多層感知機(jī)在print_tokens,md4,quick_sort上的召回率在90%以上，在replace,triangle中召回率低于45%.

Fig. 12 Leave-one-project validation results

造成學(xué)習(xí)模型在一部分被測(cè)程序的變異體樣本作為測(cè)試集時(shí)性能下降的原因，是因?yàn)槟承┍粶y(cè)程序中存在其他程序中未曾出現(xiàn)過(guò)的特征模式，這使得學(xué)習(xí)模型無(wú)法根據(jù)其他程序的經(jīng)驗(yàn)，對(duì)具有未曾遇到過(guò)的故障特征的變異體進(jìn)行有效分類(lèi).

表5給出了實(shí)驗(yàn)中使用的5個(gè)機(jī)器學(xué)習(xí)模型在LOP驗(yàn)證中取得的平均精確率(precision)和平均召回率(recall).其中，多層感知機(jī)的平均精確率和召回率遠(yuǎn)高于其他模型.這也意味著通過(guò)注意力網(wǎng)絡(luò)生成的文檔表示特征更適合通過(guò)多層全連通網(wǎng)絡(luò)預(yù)測(cè)等價(jià)性.

Table 5 Leave-One-Project Average Precision and Recall

5.5 有效性威脅

首先，本文對(duì)變異體的故障檢測(cè)上下文的文檔模型并未保證從特征空間到變異等價(jià)性的映射是完全確定性的.圖13以calendar程序的被測(cè)代碼為例，這段代碼將日歷信息存儲(chǔ)到字符串緩存buffer中.

Fig. 13 Example of mutant being incorrectly classified

在該例子中，條件語(yǔ)句真假分支的語(yǔ)句輸出是等價(jià)的.而判斷該變異體的等價(jià)性依賴(lài)于對(duì)sprintf格式化參數(shù)的理解，本文提出的故障檢測(cè)上下文特征并不能有效表示這類(lèi)與功能相關(guān)的代碼模式特征.

其次，本文使用機(jī)器學(xué)習(xí)技術(shù)來(lái)構(gòu)建從故障上下文特征到變異體等價(jià)性之間的映射關(guān)系.然而該映射的精確性和泛用性依賴(lài)于使用數(shù)據(jù)的代表性和廣泛性.在實(shí)驗(yàn)中本文僅收集了22組被測(cè)程序的變異體作為訓(xùn)練數(shù)據(jù)集，其泛用性仍有待強(qiáng)化.

最后，通過(guò)機(jī)器學(xué)習(xí)技術(shù)檢測(cè)等價(jià)變異體要求用戶(hù)首先提供一組等價(jià)變異體的訓(xùn)練樣例.這意味著在該方法投入實(shí)踐之前，手工或者半自動(dòng)的等價(jià)變異體檢測(cè)仍然是必要的.這一定程度又限制了該方法的迅速普及和使用.

6 總結(jié)與未來(lái)工作

長(zhǎng)期以來(lái)，等價(jià)變異識(shí)別問(wèn)題一直是阻礙變異測(cè)試方法在產(chǎn)業(yè)界普及的關(guān)鍵障礙[42].現(xiàn)有的等價(jià)變異體識(shí)別算法難以同時(shí)在精確率和召回率方面取得較好的檢測(cè)效果.

為了解決這一問(wèn)題，本文提出了基于故障檢測(cè)上下文的等價(jià)變異識(shí)別方法.該方法定義變異體的故障檢測(cè)上下文作為特征，通過(guò)轉(zhuǎn)換為文檔模型，使得該問(wèn)題轉(zhuǎn)變成文檔分類(lèi)問(wèn)題；最后，通過(guò)基于注意力機(jī)制的表示學(xué)習(xí)模型，生成故障檢測(cè)上下文的文檔特征向量，并以該向量為輸入，訓(xùn)練機(jī)器學(xué)習(xí)模型，以實(shí)現(xiàn)對(duì)變異體等價(jià)性的自動(dòng)識(shí)別.

在實(shí)驗(yàn)分析中，本文提出的方法在22個(gè)被測(cè)程序的118 000個(gè)變異體上取得了超過(guò)94%的預(yù)測(cè)精確率.其中在5-折交叉驗(yàn)證中，多層感知機(jī)取得了91%的精確率(precision)和85%的召回率(recall)，意味著該方法檢測(cè)出來(lái)的變異體超90%為等價(jià)變異體，且樣本中約80%的等價(jià)變異體被檢測(cè).在工程間驗(yàn)證中，機(jī)器學(xué)習(xí)技術(shù)取得77%的預(yù)測(cè)精準(zhǔn)度和78%的召回率，驗(yàn)證了本文提出方法的泛用性.本文的其他貢獻(xiàn)包括：

1) 提出了用于進(jìn)行等價(jià)變異體檢測(cè)的故障檢測(cè)上下文特征模型以及提取該特征的程序分析原型工具JCMuta.

2) 通過(guò)實(shí)驗(yàn)分析，驗(yàn)證了基于故障檢測(cè)上下文的等價(jià)變異識(shí)別技術(shù)的有效性，并指出深度學(xué)習(xí)框架是相對(duì)適合實(shí)現(xiàn)本文提出方法的一種學(xué)習(xí)技術(shù).

在未來(lái)的工作中，我們將基于故障檢測(cè)上下文特征和機(jī)器學(xué)習(xí)模型識(shí)別等價(jià)變異體可能的故障上下文模式，并通過(guò)挖掘這些模式，為測(cè)試和開(kāi)發(fā)人員更好地檢測(cè)等價(jià)變異體提供建議.