楊 羊,潘超月,曹天歌,李 征

(北京化工大學(xué) 信息科學(xué)與技術(shù)學(xué)院,北京 100029)

1 引言

持續(xù)集成環(huán)境允許代碼頻繁地集成到主干上以進(jìn)行軟件的更改[1].持續(xù)集成測試用例優(yōu)先排序針對每次集成連續(xù)地進(jìn)行測試用例執(zhí)行序列的調(diào)整,以保障持續(xù)集成的每次修改沒有引入新的錯(cuò)誤[2].基于強(qiáng)化學(xué)習(xí)的持續(xù)集成測試用例優(yōu)先排序技術(shù)[3],通過歷史經(jīng)驗(yàn)的學(xué)習(xí)自適應(yīng)地進(jìn)行測試用例優(yōu)先排序策略的調(diào)整,以適應(yīng)持續(xù)集成環(huán)境的變化,其框架被定義為reinforced test case selection (RETECS).

強(qiáng)化學(xué)習(xí)與持續(xù)集成測試用例優(yōu)先排序的交互如圖1所示.強(qiáng)化學(xué)習(xí)主要包括環(huán)境、智能體、動(dòng)作和獎(jiǎng)勵(lì)4 個(gè)元素[4].針對持續(xù)集成測試用例優(yōu)先排序,環(huán)境是持續(xù)集成周期,環(huán)境中的狀態(tài)是在每一集成周期提交的測試用例的元數(shù)據(jù),包括測試用例預(yù)計(jì)運(yùn)行時(shí)間和測試用例歷史執(zhí)行結(jié)果等;智能體是依據(jù)歷史經(jīng)驗(yàn)進(jìn)行測試用例優(yōu)先排序決策的中樞;動(dòng)作是智能體根據(jù)歷史學(xué)習(xí)的策略進(jìn)行當(dāng)前持續(xù)集成周期測試用例優(yōu)先級排序結(jié)果的返回;獎(jiǎng)勵(lì)是對當(dāng)前測試用例優(yōu)先排序策略的反饋,通過評價(jià)當(dāng)前集成周期測試用例執(zhí)行結(jié)果以實(shí)現(xiàn)獎(jiǎng)勵(lì).

強(qiáng)化學(xué)習(xí)是一種基于獎(jiǎng)勵(lì)機(jī)制的機(jī)器學(xué)習(xí)方法,核心是通過獎(jiǎng)勵(lì)函數(shù)對當(dāng)前行為進(jìn)行有效的評估,并反饋給智能體選擇合適的后續(xù)行為,以實(shí)現(xiàn)期望的最大化.基于強(qiáng)化學(xué)習(xí)的持續(xù)集成測試用例優(yōu)先排序技術(shù),通過對測試用例實(shí)施獎(jiǎng)勵(lì)以實(shí)現(xiàn)測試用例優(yōu)先排序策略的調(diào)整,從而最終提高持續(xù)集成測試用例優(yōu)先排序的質(zhì)量.測試用例的獎(jiǎng)勵(lì)包括獎(jiǎng)勵(lì)函數(shù)設(shè)計(jì)方法和獎(jiǎng)勵(lì)對象選擇策略.Yang 等人[5]系統(tǒng)化研究了獎(jiǎng)勵(lì)函數(shù)設(shè)計(jì)方法,提出了基于歷史信息的獎(jiǎng)勵(lì)函數(shù),通過提取測試用例歷史信息序列的特征以實(shí)現(xiàn)測試用例檢錯(cuò)能力的度量,可以實(shí)現(xiàn)測試用例優(yōu)先排序效果的優(yōu)化.

獎(jiǎng)勵(lì)對象選擇策略通常選擇執(zhí)行失效測試用例作為獎(jiǎng)勵(lì)對象實(shí)施獎(jiǎng)勵(lì).然而,實(shí)際工業(yè)軟件持續(xù)集成測試具有集成高頻繁和測試低失效的特點(diǎn).例如,在Google開源數(shù)據(jù)集GSDTSR 中,共集成336 個(gè)周期,其中284個(gè)周期存在執(zhí)行失效,涉及5 555 個(gè)測試用例的1 260 618次測試執(zhí)行,其中失效執(zhí)行只占0.25%.在基于執(zhí)行失效的獎(jiǎng)勵(lì)對象選擇策略下,持續(xù)集成測試的低失效會(huì)引發(fā)獎(jiǎng)勵(lì)對象稀少,從而導(dǎo)致強(qiáng)化學(xué)習(xí)獎(jiǎng)勵(lì)稀疏問題,減緩了強(qiáng)化學(xué)習(xí)速度,甚至可能導(dǎo)致智能體生成高隨機(jī)的策略[6],難以真正應(yīng)用于實(shí)際工業(yè)生產(chǎn)環(huán)境中.如何解決基于強(qiáng)化學(xué)習(xí)的持續(xù)集成測試用例優(yōu)先排序技術(shù)在實(shí)際工業(yè)環(huán)境中產(chǎn)生的獎(jiǎng)勵(lì)稀疏問題,是本文的研究重點(diǎn).

獎(jiǎng)勵(lì)稀疏問題的核心是獎(jiǎng)勵(lì)對象稀少,可以通過增加獎(jiǎng)勵(lì)對象來解決獎(jiǎng)勵(lì)稀疏問題.測試用例優(yōu)先排序旨在優(yōu)先執(zhí)行潛在失效測試用例.當(dāng)前執(zhí)行失效的測試用例,基于失效測試與測試失效的相關(guān)性[7],在后續(xù)測試執(zhí)行中具有較大的失效可能性,該理論不適用于執(zhí)行通過的測試用例.在測試用例優(yōu)先排序中考慮測試用例之間的依賴關(guān)系,理論上會(huì)使排序結(jié)果更優(yōu),但依賴性分析特別是大規(guī)模程序的依賴性分析是一個(gè)非常耗時(shí)的過程,難以滿足持續(xù)集成測試的快速反饋需求.在測試用例優(yōu)先排序中考慮測試用例之間的相似關(guān)系,即基于相似性的測試用例優(yōu)先排序[8],通過測試用例間的相似性度量,優(yōu)先執(zhí)行有相同特征的測試用例,可以有效提高測試序列的檢錯(cuò)能力.因此,本文基于相似測試用例的假設(shè),提出一種測試用例相似性的度量方法,并選擇與失效測試用例集相似的通過測試用例實(shí)施獎(jiǎng)勵(lì),以解決獎(jiǎng)勵(lì)對象稀少導(dǎo)致的強(qiáng)化學(xué)習(xí)獎(jiǎng)勵(lì)稀疏問題.

根據(jù)集成測試的快速反饋需求,Bagherzadeh 等人[9]認(rèn)為持續(xù)集成測試用例優(yōu)先排序的最優(yōu)序列為檢錯(cuò)能力高并且執(zhí)行時(shí)間短的序列,即優(yōu)先執(zhí)行檢錯(cuò)能力高的測試用例,在相同的檢錯(cuò)能力下優(yōu)先執(zhí)行運(yùn)行時(shí)間短的測試用例.因此,本文針對測試用例相似性度量考慮以下兩個(gè)因素.首先,測試用例的歷史執(zhí)行信息序列相似的測試用例具有相似的檢錯(cuò)能力,即兩個(gè)測試用例在歷史執(zhí)行過程中執(zhí)行結(jié)果相似,在后續(xù)測試中執(zhí)行結(jié)果可能相同.所以選擇與失效測試用例歷史執(zhí)行信息序列相似的執(zhí)行通過測試用例實(shí)施獎(jiǎng)勵(lì),有助于在后續(xù)測試中提升高檢錯(cuò)能力測試用例的執(zhí)行順序.其次,在第一個(gè)條件的基礎(chǔ)上,具有相似執(zhí)行時(shí)間的測試用例有利于優(yōu)化測試執(zhí)行時(shí)間,從而提升反饋速度.

本文通過歷史信息序列特征和執(zhí)行時(shí)間設(shè)計(jì)了一個(gè)多維度相似性度量方法,通過增加獎(jiǎng)勵(lì)與執(zhí)行失效測試用例相似的執(zhí)行通過測試用例,解決強(qiáng)化學(xué)習(xí)獎(jiǎng)勵(lì)稀疏問題,從而實(shí)現(xiàn)基于強(qiáng)化學(xué)習(xí)的持續(xù)集成測試用例優(yōu)先排序技術(shù)在實(shí)際工業(yè)界的應(yīng)用.最終,在大規(guī)模工業(yè)數(shù)據(jù)集上驗(yàn)證了基于強(qiáng)化學(xué)習(xí)的持續(xù)集成測試用例優(yōu)先排序在基于相似性的獎(jiǎng)勵(lì)對象選擇策略下的有效性.

2 基于相似性的獎(jiǎng)勵(lì)對象選擇策略

基于強(qiáng)化學(xué)習(xí)的持續(xù)集成測試用例優(yōu)先排序通過歷史經(jīng)驗(yàn)的學(xué)習(xí),盡可能多地獎(jiǎng)勵(lì)潛在失效測試用例,通過測試用例優(yōu)先排序策略的調(diào)整以實(shí)現(xiàn)在后續(xù)測試中優(yōu)先執(zhí)行失效測試用例.基于失效測試與測試失效的相關(guān)性[7],當(dāng)前執(zhí)行失效測試用例在后續(xù)測試中具有更大的潛在失效可能性,智能體對其實(shí)施獎(jiǎng)勵(lì)有助于提高測試用例優(yōu)先排序效果.然而實(shí)際工業(yè)程序中低失效的持續(xù)集成測試導(dǎo)致基于強(qiáng)化學(xué)習(xí)的持續(xù)集成測試用例優(yōu)先排序獎(jiǎng)勵(lì)對象稀少,即獎(jiǎng)勵(lì)稀疏,減緩了強(qiáng)化學(xué)習(xí)的速度,甚至形成難以收斂的高隨機(jī)策略.

為了解決強(qiáng)化學(xué)習(xí)的獎(jiǎng)勵(lì)稀疏問題,在獎(jiǎng)勵(lì)失效測試用例的基礎(chǔ)上,基于測試用例相似性假設(shè)[8],本文針對執(zhí)行通過測試用例與執(zhí)行失效測試用例進(jìn)行相似性分析,從而實(shí)現(xiàn)對執(zhí)行通過測試用例實(shí)施獎(jiǎng)勵(lì),并提出基于相似性的獎(jiǎng)勵(lì)對象選擇策略.

2.1 持續(xù)集成測試用例特征分析

基于相似性的測試用例優(yōu)先排序技術(shù)在回歸測試中證明了存在相似性的測試用例擁有相似的錯(cuò)誤檢測率[8],并且具有潛在失效可能的測試用例傾向于聚集在連續(xù)的區(qū)域[10].

相似性度量的概念是許多研究領(lǐng)域的研究主題.兩個(gè)物體共有特征的程度被稱為相似性,它們不同的程度被稱為距離.許多軟件測試文獻(xiàn)量化了測試用例之間的相似性,例如在基于覆蓋的測試優(yōu)化中,使用覆蓋信息進(jìn)行測試用例之間相似性的度量[11].測試用例的相似性度量因素還涉及測試路徑[12,13]、測試用例相關(guān)源代碼[14]、測試輸入和輸出[15]、從測試腳本中提取的主題模型[16]、測試用例的歷史失效信息[17]等.

在基于強(qiáng)化學(xué)習(xí)的持續(xù)集成測試用例優(yōu)先排序中,智能體根據(jù)歷史學(xué)習(xí)的策略針對測試用例元數(shù)據(jù)進(jìn)行識(shí)別以產(chǎn)生測試用例優(yōu)先排序結(jié)果.測試用例元數(shù)據(jù)通過持續(xù)集成測試日志的提取,包括Cycle、ID、Duration、LastRun、LastResults和Verdict,這些屬性及其解釋如表1所示.

表1 測試用例元數(shù)據(jù)

針對在同一周期的測試用例,根據(jù)當(dāng)前執(zhí)行結(jié)果的不同,即Verdict的不同,可以有效地識(shí)別失效測試用例對被測系統(tǒng)的失效影響.對于執(zhí)行通過測試用例,基于Verdict 無法度量其失效影響,然而其歷史執(zhí)行結(jié)果LastResults 可以描述其在歷史執(zhí)行過程中的失效情況.針對歷史執(zhí)行過程相似的測試用例,其在未來執(zhí)行中可能有相同的測試結(jié)果.因此,可以基于測試用例的歷史執(zhí)行過程進(jìn)行測試用例的相似性度量.

持續(xù)集成測試是一種黑盒測試方法,在快速反饋需求下,基于黑盒測試的測試用例執(zhí)行時(shí)間,在相近測試內(nèi)容下其執(zhí)行時(shí)間非常接近.測試用例優(yōu)先排序旨在優(yōu)先執(zhí)行潛在失效測試用例.在實(shí)際工業(yè)程序中,潛在失效的測試用例可能與執(zhí)行失效測試用例不完全相同,但是非常相似,例如,當(dāng)新測試用例是舊失效測試用例的修改版本時(shí),新測試用例可以捕捉未檢測到的系統(tǒng)故障,但是當(dāng)前執(zhí)行通過.新測試用例與舊測試用例的執(zhí)行時(shí)間Duration 非常接近或者相同.因此新測試用例由于與舊測試用例相似,并且具有類似的執(zhí)行時(shí)間,具有相似的失效影響,在后續(xù)測試中應(yīng)該被優(yōu)先執(zhí)行.

基于測試失效的假設(shè),失效測試用例對被測系統(tǒng)具有失效影響,智能體對其實(shí)施獎(jiǎng)勵(lì).本文通過提取測試用例的歷史執(zhí)行信息序列LastResults 與測試執(zhí)行時(shí)間Duration 進(jìn)行執(zhí)行通過測試用例與執(zhí)行失效測試用例集的相似性度量,以識(shí)別執(zhí)行通過測試用例集中具有失效影響的測試用例,從而實(shí)現(xiàn)獎(jiǎng)勵(lì)的實(shí)施.

2.2 測試用例相似性度量方法

測試用例的相似性度量,通過提取測試用例的特征以實(shí)現(xiàn)測試用例間的相似性計(jì)算.本文針對持續(xù)集成測試用例使用歷史執(zhí)行信息序列LastResults和執(zhí)行時(shí)間Duration 信息,進(jìn)行測試用例的特征向量定義,如定義1 所示.

定義1.測試用例的特征向量(feature vector of test case).

其中,totalTimei表示持續(xù)集成i周期的計(jì)劃執(zhí)行時(shí)間,t.durationi表示測試用例t在i周期的執(zhí)行時(shí)間,是測試用例t在i周期執(zhí)行時(shí)間的歸一化,t.lastresultsi表示測試用例t在i周期測試執(zhí)行后的歷史執(zhí)行信息序列.

測試用例的特征向量通過測試用例的特征提取以實(shí)現(xiàn)測試用例間的相似性度量.本文通過測試用例的歷史執(zhí)行信息序列和執(zhí)行時(shí)間的屬性,進(jìn)行測試用例的特征提取,定義了測試用例的特征向量,并進(jìn)一步根據(jù)特征向量進(jìn)行兩兩測試用例間的特征距離計(jì)算以實(shí)現(xiàn)相似性計(jì)算.

相似性函數(shù)通過兩兩測試用例間的特征距離計(jì)算以度量測試用例相似程度.相似性距離計(jì)算的常用方法包括杰卡德距離[11]、Gower-Legendre[18]、Sokal-Sneath[19]、歐氏距離[20–22]、余弦相似性[23]和比例二進(jìn)制距離[21,24,25]等.Wang 等人[26]通過深入研究了這6 種常用相似性計(jì)算公式對基于相似性的測試用例優(yōu)先排序效果的影響,研究表明歐氏距離比其他相似性距離計(jì)算公式更有助于進(jìn)行測試用例優(yōu)先排序,從而更有效地發(fā)現(xiàn)程序錯(cuò)誤.因此,本文采用歐氏距離進(jìn)行持續(xù)集成測試的測試用例相似性函數(shù)計(jì)算,通過特征向量的逐一比較實(shí)現(xiàn)測試用例的相似性度量,其相似性計(jì)算函數(shù)如定義2 所示.

定義2.測試用例相似性函數(shù)(test case similarity,TCS).

其中,t1表示執(zhí)行通過測試用例,t2表示執(zhí)行失效測試用例,Featurei(t1j)表示測試用例t1在第i集成周期的特征向量的第j個(gè)特征,n是測試用例t1和t2的最短有效歷史執(zhí)行序列長度.由于在持續(xù)集成測試中測試用例出現(xiàn)的頻率不同,導(dǎo)致測試用例的歷史執(zhí)行信息序列長度不同.為了有效地進(jìn)行特征向量的比較,基于失效測試與測試失效的相關(guān)性[7],本文依據(jù)測試用例中歷史信息序列較短的序列長度,選擇臨近歷史信息序列進(jìn)行相似性的計(jì)算,從而實(shí)現(xiàn)全面測試用例相似性比較.

測試用例相似性函數(shù)通過兩兩測試用例的特征向量距離計(jì)算,以實(shí)現(xiàn)測試用例的相似性度量.距離越小,即相似性值越低,表明這兩個(gè)測試用例越相似.

2.3 基于相似性的獎(jiǎng)勵(lì)對象選擇方法

基于失效測試與測試失效的相關(guān)性[7],失效測試用例具有較高的檢錯(cuò)能力,在后續(xù)測試中需要進(jìn)行優(yōu)先級的提升,因此智能體優(yōu)先對失效測試用例實(shí)施獎(jiǎng)勵(lì)以實(shí)現(xiàn)測試用例優(yōu)先排序策略的調(diào)整,使其適應(yīng)后續(xù)持續(xù)測試.然而,持續(xù)集成測試的低失效特征,即失效測試執(zhí)行稀少,導(dǎo)致基于強(qiáng)化學(xué)習(xí)的持續(xù)集成測試用例優(yōu)先排序獎(jiǎng)勵(lì)對象稀少,導(dǎo)致獎(jiǎng)勵(lì)稀疏問題,影響了強(qiáng)化學(xué)習(xí)的學(xué)習(xí)速度和學(xué)習(xí)質(zhì)量.

在持續(xù)集成測試中,對于當(dāng)前執(zhí)行通過測試用例,一方面存在頻繁失效、偶然通過的測試用例,另一方面存在測試用例是舊測試用例的修復(fù)版本.這些測試用例在后續(xù)測試中存在失效可能性,因此具有一定的失效影響,然而無法基于當(dāng)前執(zhí)行結(jié)果進(jìn)行有效的度量.為了有效度量執(zhí)行通過測試用例的失效影響,本文通過與執(zhí)行失效測試用例的相似性分析,以選擇執(zhí)行通過測試用例集中與執(zhí)行失效測試用例相似的測試用例實(shí)施獎(jiǎng)勵(lì),進(jìn)一步提出基于相似性的獎(jiǎng)勵(lì)對象選擇策略.智能體針對執(zhí)行通過測試用例,使用與執(zhí)行失效測試用例的相似性分析方法,實(shí)現(xiàn)執(zhí)行通過測試用例的失效影響分析,從而增加獎(jiǎng)勵(lì)與執(zhí)行失效測試用例相似的執(zhí)行通過測試用例.

針對在某一集成周期的測試用例集,在測試執(zhí)行后,智能體首先對失效測試用例進(jìn)行獎(jiǎng)勵(lì),進(jìn)一步將執(zhí)行通過測試用例逐一與失效測試用例集進(jìn)行相似性分析以尋找具有失效影響的執(zhí)行通過測試用例.若執(zhí)行通過測試用例與執(zhí)行失效測試用例存在相似性,則該執(zhí)行通過測試用例具有失效影響,智能體應(yīng)該獎(jiǎng)勵(lì)該測試用例,否則執(zhí)行通過測試用例不被獎(jiǎng)勵(lì).其執(zhí)行流程如圖2所示.根據(jù)其執(zhí)行過程,本文進(jìn)一步定義了基于相似性的獎(jiǎng)勵(lì)對象選擇策略如定義3 所示.

定義3.基于相似性的獎(jiǎng)勵(lì)對象選擇策略(similaritybased reward object selection strategy).

對于第i個(gè)周期的測試套件Ti={t1,t2,…,tj,…,tn},如果測試用例tj執(zhí)行失效,則獎(jiǎng)勵(lì)測試用例tj;若測試用例tj執(zhí)行通過,但測試用例tj與Ti中的失效測試用例t′存在相似性,即則獎(jiǎng)勵(lì)測試用例tj;其他情況智能體不獎(jiǎng)勵(lì)測試用例.

基于相似性的獎(jiǎng)勵(lì)對象選擇策略的獎(jiǎng)勵(lì)方式,如式(3)所示.

其中,rewardvalue是基于任意獎(jiǎng)勵(lì)函數(shù)計(jì)算的測試用例的獎(jiǎng)勵(lì)值,t.verdict表示測試用例t的執(zhí)行結(jié)果,1 表示執(zhí)行失效,0 表示執(zhí)行通過,t′是該周期中任意執(zhí)行失效測試用例.

本文通過持續(xù)集成測試用例的特征分析,提出考慮測試用例歷史執(zhí)行信息序列和執(zhí)行時(shí)間的多維度測試用例特征向量表示方法,并進(jìn)一步基于特征向量進(jìn)行測試用例間的相似性度量.基于測試用例的相似性特征,本文提出基于相似性的獎(jiǎng)勵(lì)對象選擇策略,在獎(jiǎng)勵(lì)失效測試用例的基礎(chǔ)上,通過相似性的判斷,自適應(yīng)地選擇執(zhí)行通過測試用例進(jìn)行獎(jiǎng)勵(lì)以解決在實(shí)際工業(yè)程序中的獎(jiǎng)勵(lì)稀疏問題.

3 實(shí)驗(yàn)設(shè)計(jì)及結(jié)果分析

基于強(qiáng)化學(xué)習(xí)的持續(xù)集成測試用例優(yōu)先排序過程如圖3所示,其中虛線部分存在于持續(xù)集成環(huán)境中,實(shí)線部分存在于強(qiáng)化學(xué)習(xí)框架中.對于每個(gè)集成周期中提交的測試用例集,強(qiáng)化學(xué)習(xí)的智能體根據(jù)歷史學(xué)習(xí)的測試用例優(yōu)先排序策略定義測試用例的優(yōu)先級,進(jìn)一步根據(jù)快速反饋的時(shí)間約束選擇測試用例以進(jìn)行測試排序從而實(shí)現(xiàn)測試執(zhí)行,最后根據(jù)執(zhí)行結(jié)果進(jìn)行評價(jià)并反饋給開發(fā)人員和強(qiáng)化學(xué)習(xí)的智能體.智能體根據(jù)反饋的結(jié)果選擇測試用例實(shí)施獎(jiǎng)勵(lì),即獎(jiǎng)勵(lì)對象選擇策略,并進(jìn)一步根據(jù)獎(jiǎng)勵(lì)的結(jié)果為后續(xù)集成測試調(diào)整測試用例優(yōu)先排序策略,使其適應(yīng)于持續(xù)集成系統(tǒng)的連續(xù)變化.

3.1 研究問題

本文針對在實(shí)際工業(yè)程序存在集成高頻繁但是測試低失效的特征,在基于強(qiáng)化學(xué)習(xí)的持續(xù)集成測試用例優(yōu)先排序中研究獎(jiǎng)勵(lì)對象稀少導(dǎo)致強(qiáng)化學(xué)習(xí)的獎(jiǎng)勵(lì)稀疏問題,提出基于相似性的獎(jiǎng)勵(lì)對象選擇策略.本文從以下3 個(gè)研究問題進(jìn)行實(shí)驗(yàn)的分析和驗(yàn)證.

問題1.在基于相似性的獎(jiǎng)勵(lì)對象選擇策略中,如何進(jìn)行相似性閾值的選取,從而實(shí)現(xiàn)持續(xù)集成測試用例優(yōu)先排序?

問題2.基于相似性的獎(jiǎng)勵(lì)對象選擇策略對基于強(qiáng)化學(xué)習(xí)的持續(xù)集成測試用例優(yōu)先排序質(zhì)量的影響如何?

問題3.基于相似性的獎(jiǎng)勵(lì)對象選擇策略對基于強(qiáng)化學(xué)習(xí)的持續(xù)集成測試用例優(yōu)先排序框架的時(shí)間開銷影響如何?

問題1 通過不同閾值下基于相似性獎(jiǎng)勵(lì)對象選擇策略對測試用例優(yōu)先排序效果的影響研究,選擇適合目標(biāo)程序的最佳閾值.問題2 通過基于相似性的獎(jiǎng)勵(lì)對象選擇策略與基于執(zhí)行失效的獎(jiǎng)勵(lì)對象選擇策略進(jìn)行測試用例優(yōu)先排序質(zhì)量的對比,驗(yàn)證基于相似性的獎(jiǎng)勵(lì)對象選擇策略的有效性.問題3 是對不同獎(jiǎng)勵(lì)對象選擇策略下的框架時(shí)間開銷進(jìn)行對比.

3.2 評價(jià)指標(biāo)

本文為了比較不同獎(jiǎng)勵(lì)對象選擇策略,在基于強(qiáng)化學(xué)習(xí)的持續(xù)集成測試用例優(yōu)先排序下對持續(xù)集成測試用例優(yōu)先排序效果通過NAPFD (normalized average percentage of faults detected),TTF (test to fail),Recall和時(shí)間開銷4 個(gè)評價(jià)指標(biāo)進(jìn)行度量.

(1)NAPFD

平均歷史檢測率(APFD,average percentage of faults detected)[27]作為測試用例優(yōu)先排序效果評價(jià)的有效方法,在檢測到序列中所有錯(cuò)誤的假設(shè)下,根據(jù)測試序列中失效位置的索引進(jìn)行測試序列的評價(jià).然而,基于強(qiáng)化學(xué)習(xí)的持續(xù)集成測試用例優(yōu)先排序,使用測試用例選擇的快速反饋機(jī)制模擬,使得只有占一半執(zhí)行時(shí)間的測試用例被執(zhí)行,即存在失效的測試用例不被執(zhí)行.由于APFD 只適用于可以檢測到所有錯(cuò)誤的測試用例序列,即不存在測試用例選擇.因此,Qu 等人[28]于2007年提出APFD的擴(kuò)展NAPFD,根據(jù)實(shí)際檢測錯(cuò)誤率來進(jìn)行失效分布的計(jì)算,適用于存在測試用例選擇的測試用例優(yōu)先排序序列.

NAPFD 作為測試用例優(yōu)先排序的評價(jià)標(biāo)準(zhǔn)[28],其定義為:

根據(jù)NAPFD的定義,在持續(xù)集成測試中,如果所有的錯(cuò)誤均被檢測到,則p=1,NAPFD 與APFD 等同;如果存在錯(cuò)誤未被檢測到,則p<1,基于NAPFD的評價(jià)更符合實(shí)際情況.

(2)TTF

TTF 根據(jù)測試執(zhí)行中首次執(zhí)行失效的測試用例在測試序列中的位置進(jìn)行評價(jià).測試用例優(yōu)先排序的目標(biāo)是優(yōu)先執(zhí)行失效測試用例.失效位置越靠前,測試用例優(yōu)先排序效果越好.因此,TTF 可以有效地評價(jià)測試用例優(yōu)先排序的效果.TTF 值越小,即執(zhí)行失效測試用例在執(zhí)行序列中位置越靠前,則測試用例優(yōu)先排序的效果越好.

(3)Recall

為了有效地評價(jià)持續(xù)集成測試用例優(yōu)先排序的質(zhì)量,引入Recall 來評價(jià)每一周期實(shí)際檢測到錯(cuò)誤的比例.Recall 根據(jù)測試執(zhí)行序列中實(shí)際檢測錯(cuò)誤與集成周期內(nèi)實(shí)際存在錯(cuò)誤的比重進(jìn)行度量.Recall 在測試選擇的基礎(chǔ)上,計(jì)算占總執(zhí)行時(shí)間一半的測試用例集檢測到的錯(cuò)誤占該周期實(shí)際總錯(cuò)誤的比例.Recall 值越高,則執(zhí)行序列檢測的錯(cuò)誤越多,相應(yīng)的測試用例優(yōu)先排序效果越好.

(4)時(shí)間開銷

時(shí)間開銷作為測試用例優(yōu)先排序技術(shù)的重要評價(jià)指標(biāo),對算法的執(zhí)行效率進(jìn)行評價(jià).針對基于強(qiáng)化學(xué)習(xí)的持續(xù)集成測試用例優(yōu)先排序技術(shù),其時(shí)間開銷包括獎(jiǎng)勵(lì)計(jì)算的時(shí)間、智能體的學(xué)習(xí)時(shí)間、測試用例執(zhí)行信息的更新時(shí)間和測試用例優(yōu)先排序的時(shí)間等.

3.3 實(shí)驗(yàn)對象及設(shè)計(jì)

本文針對個(gè)6 工業(yè)數(shù)據(jù)集進(jìn)行相關(guān)實(shí)驗(yàn),其中IOF/ROL、Paint Control和GSDTSR為Spieker 等人[3]研究中所使用的數(shù)據(jù)集,Rails為開源工業(yè)數(shù)據(jù)集(http://gihub.com/elbum/CI?Datasets.git),其他2 個(gè)數(shù)據(jù)集為研究者共享的持續(xù)集成測試日志(https://travistorrent.testroots.org/buildlogs/20-12-2016/).測試用例是唯一識(shí)別碼,在持續(xù)集成的不同周期中測試不同的組件,并記錄了相關(guān)的測試執(zhí)行結(jié)果.表2列出了6 個(gè)工業(yè)數(shù)據(jù)集的持續(xù)集成測試的詳細(xì)信息,包括測試用例數(shù)、持續(xù)集成周期數(shù)、持續(xù)集成測試執(zhí)行結(jié)果數(shù)、持續(xù)集成失效率和頻率.集成周期不僅給出了持續(xù)集成的周期數(shù),并標(biāo)注了實(shí)際測試過程中失效周期數(shù),執(zhí)行結(jié)果數(shù)強(qiáng)調(diào)的是在整個(gè)持續(xù)集成過程中測試執(zhí)行總數(shù),失效率表示持續(xù)集成測試過程中測試失效占總測試執(zhí)行的比例,頻率統(tǒng)計(jì)了測試用例在每一周期進(jìn)行測試的概率.

表2 工業(yè)數(shù)據(jù)集信息

在基于強(qiáng)化學(xué)習(xí)的持續(xù)集成測試用例優(yōu)先排序中,獎(jiǎng)勵(lì)函數(shù)設(shè)計(jì)方法采用目前最優(yōu)的基于歷史信息的獎(jiǎng)勵(lì)函數(shù)[5],即基于平均歷史失效分布的獎(jiǎng)勵(lì)函數(shù)APHF(average percentage of historical failure).在實(shí)際工業(yè)數(shù)據(jù)集中,針對龐大歷史信息,本文使用滑動(dòng)窗進(jìn)行臨近歷史信息的特征選取[29],即通過提取臨近歷史信息的特征以實(shí)現(xiàn)獎(jiǎng)勵(lì)計(jì)算效率的提升.本文基于持續(xù)集成測試的連續(xù)變化,采用基于動(dòng)態(tài)滑動(dòng)窗的臨近歷史信息選擇方法,即滑動(dòng)窗尺寸隨著持續(xù)集成測試進(jìn)程動(dòng)態(tài)變化,以實(shí)現(xiàn)自適應(yīng)的獎(jiǎng)勵(lì)計(jì)算[30].

3.4 實(shí)驗(yàn)結(jié)果及分析

本小節(jié)分別針對3 個(gè)研究問題進(jìn)行實(shí)驗(yàn)結(jié)果的展示及分析.

3.4.1 測試用例相似性閾值選取分析

本小節(jié)針對問題1 進(jìn)行實(shí)驗(yàn)分析.測試用例相似性通過測試用例之間的特征匹配以實(shí)現(xiàn)相似性度量.在基于相似性的獎(jiǎng)勵(lì)對象選擇策略中,使用執(zhí)行通過測試用例與執(zhí)行失效測試用例進(jìn)行相似性對比,從測試歷史執(zhí)行信息序列和測試執(zhí)行時(shí)間角度進(jìn)行多維度特征匹配,從而確定智能體是否對執(zhí)行通過測試用例進(jìn)行獎(jiǎng)勵(lì).由于工業(yè)數(shù)據(jù)集存在不同的失效率、測試頻率等特征,在具體數(shù)據(jù)集中相似性閾值的不同,會(huì)導(dǎo)致不同的獎(jiǎng)勵(lì)對象數(shù)量,從而產(chǎn)生不同的測試用例優(yōu)先排序效果.因此需要針對不同的數(shù)據(jù)集進(jìn)行相似性閾值的選取分析.

首先對工業(yè)數(shù)據(jù)集進(jìn)行相似性特征分析,即基于相似性度量方法進(jìn)行測試用例相似性指標(biāo)值的分析,圖4統(tǒng)計(jì)了在6 個(gè)數(shù)據(jù)集上進(jìn)行測試用例相似性值分析的具體分布情況,針對具體數(shù)據(jù)集,縱坐標(biāo)表示基于相似性計(jì)算獲得的相似性值.由于在不同數(shù)據(jù)集上測試用例的執(zhí)行過程和結(jié)果不同,導(dǎo)致相似性值的范圍不同,并且相似性值存在較多的異常數(shù)據(jù),因此為了更好地確定適用于不同數(shù)據(jù)集的相似性閾值,本文首先依據(jù)相似性值的分布針對具體數(shù)據(jù)集選取相似性值分布的下四分位數(shù)、中位數(shù)和上四分位數(shù)作為基于測試用例相似性的獎(jiǎng)勵(lì)對象選擇策略閾值,其統(tǒng)計(jì)結(jié)果如表3所示.

表3 針對工業(yè)數(shù)據(jù)集的測試用例相似性閾值ε 選取

進(jìn)一步在基于強(qiáng)化學(xué)習(xí)的持續(xù)集成測試用例優(yōu)先排序中依據(jù)基于相似性的獎(jiǎng)勵(lì)對象選擇策略,使用不同的相似性閾值進(jìn)行基于強(qiáng)化學(xué)習(xí)的持續(xù)集成測試用例優(yōu)先排序,并使用NAPFD 指標(biāo)進(jìn)行持續(xù)集成測試用例優(yōu)先排序質(zhì)量的評價(jià),并實(shí)現(xiàn)不同閾值的測試用例優(yōu)先排序效果的對比,其結(jié)果如表4所示,其中加粗字體標(biāo)注了在該閾值下可以取得最好的NAPFD 值.

表4 基于不同相似性閾值選取的持續(xù)集成測試用例優(yōu)先排序NAPFD 值(%)

相似性閾值的選取,決定了在基于強(qiáng)化學(xué)習(xí)的持續(xù)集成測試用例優(yōu)先排序中增加獎(jiǎng)勵(lì)的執(zhí)行通過測試用例的數(shù)量.增加獎(jiǎng)勵(lì)的數(shù)量過多,反而會(huì)降低失效影響大的執(zhí)行通過測試用例的優(yōu)先級;而增加獎(jiǎng)勵(lì)的數(shù)量過少,導(dǎo)致部分失效影響大的執(zhí)行通過測試用例無法獲得有效的獎(jiǎng)勵(lì),從而降低測試用例優(yōu)先排序效果.

因此針對6 個(gè)數(shù)據(jù)集,本文根據(jù)NAPFD的結(jié)果對比分別選取Paint Control的7.681 2、IOF/ROL的0.000 6、GSDTSR的0.003 4、Rails的1.000 0、MyBatis的2.645 8和Apache Drill的0.012 6 作為基于相似性的獎(jiǎng)勵(lì)對象選擇策略的相似性閾值,以實(shí)現(xiàn)在有效的獎(jiǎng)勵(lì)數(shù)量增加下獲得測試用例優(yōu)先排序效果優(yōu)化,為后續(xù)實(shí)驗(yàn)及分析奠定基礎(chǔ).

3.4.2 基于相似性的獎(jiǎng)勵(lì)對象選擇策略有效性分析

本小節(jié)針對問題2 進(jìn)行實(shí)驗(yàn)分析.基于相似性的獎(jiǎng)勵(lì)對象選擇策略,在獎(jiǎng)勵(lì)失效測試用例的基礎(chǔ)上,通過相似性分析自適應(yīng)地選擇執(zhí)行通過測試用例實(shí)施獎(jiǎng)勵(lì),從而實(shí)現(xiàn)獎(jiǎng)勵(lì)對象數(shù)量的增加以解決獎(jiǎng)勵(lì)稀疏問題.在基于強(qiáng)化學(xué)習(xí)的持續(xù)集成測試用例優(yōu)先排序中,本文采用相同的獎(jiǎng)勵(lì)函數(shù)設(shè)計(jì)方法APHF,通過不同獎(jiǎng)勵(lì)對象選擇策略,即基于執(zhí)行失效的獎(jiǎng)勵(lì)對象選擇策略(APHF_P)和基于相似性的獎(jiǎng)勵(lì)對象選擇策略(APHF_S),在NAPFD、Recall和TTF 三個(gè)指標(biāo)下進(jìn)行測試用例優(yōu)先排序質(zhì)量的對比.實(shí)驗(yàn)結(jié)果如表5所示,其中加粗?jǐn)?shù)據(jù)部分標(biāo)注了在基于相似性的獎(jiǎng)勵(lì)對象選擇策略下,測試用例優(yōu)先排序評價(jià)指標(biāo)值優(yōu)于基于執(zhí)行失效的獎(jiǎng)勵(lì)對象選擇策略的情況.

根據(jù)表5所示的實(shí)驗(yàn)結(jié)果,從整體平均上來看,基于相似性的獎(jiǎng)勵(lì)對象選擇策略在不同的評價(jià)指標(biāo)上均可以有效地進(jìn)行指標(biāo)值的提升,NAPFD 可以獲得5.94%的提升,Recall 可以有效地改進(jìn)5.51%的錯(cuò)誤檢測率,并且在TTF 上可以有效地提升57.42 個(gè)失效測試用例在測試序列中首次執(zhí)行失效的位置.針對具體數(shù)據(jù)集的分析可以看出,在6 個(gè)數(shù)據(jù)集上,基于相似性的獎(jiǎng)勵(lì)對象選擇策略可以有效改進(jìn)4 個(gè)數(shù)據(jù)集的測試用例優(yōu)先排序質(zhì)量,尤其在GSDTSR 中可以明顯提升34.51%的NAPFD 值、34.13%的Recall 值和293.15位的TTF.

在基于相似性的獎(jiǎng)勵(lì)對象選擇策略下,通過相似性閾值的判斷來增加獎(jiǎng)勵(lì)執(zhí)行通過測試用例.相比于基于執(zhí)行失效的獎(jiǎng)勵(lì)對象獎(jiǎng)勵(lì)策略,基于相似性的獎(jiǎng)勵(lì)對象選擇策略增加了強(qiáng)化學(xué)習(xí)的獎(jiǎng)勵(lì)數(shù)量,緩解了面向持續(xù)集成測試用例優(yōu)先排序的強(qiáng)化學(xué)習(xí)獎(jiǎng)勵(lì)對象稀少問題.獎(jiǎng)勵(lì)對象的增加,使得強(qiáng)化學(xué)習(xí)的智能體可以接收到更多環(huán)境的反饋,從而更好地進(jìn)行測試用例優(yōu)先排序策略的調(diào)整,最終實(shí)現(xiàn)測試用例優(yōu)先排序質(zhì)量的提升.

綜上所述,基于相似性的獎(jiǎng)勵(lì)對象選擇策略通過增加獎(jiǎng)勵(lì)與執(zhí)行失效測試用例存在相似的執(zhí)行通過測試用例,有效地增加了面向持續(xù)集成測試用例優(yōu)先排序的強(qiáng)化學(xué)習(xí)獎(jiǎng)勵(lì)對象,解決了強(qiáng)化學(xué)習(xí)的獎(jiǎng)勵(lì)稀疏問題,并進(jìn)一步有效地提升了測試用例優(yōu)先排序效果.

3.4.3 基于相似性的獎(jiǎng)勵(lì)對象選擇策略的時(shí)間開銷分析

本小節(jié)針對問題3 進(jìn)行實(shí)驗(yàn)分析.基于相似性的獎(jiǎng)勵(lì)對象選擇策略在基于強(qiáng)化學(xué)習(xí)的持續(xù)集成測試用例優(yōu)先排序中,通過相似性分析以實(shí)現(xiàn)測試用例優(yōu)先排序質(zhì)量的提升,在一定程度上是以時(shí)間開銷為代價(jià)進(jìn)行測試用例優(yōu)先排序質(zhì)量的提升,理論上增加了基于強(qiáng)化學(xué)習(xí)的持續(xù)集成測試優(yōu)先排序框架的時(shí)間開銷.本文進(jìn)一步在基于強(qiáng)化學(xué)習(xí)的持續(xù)集成測試用例優(yōu)先排序中使用基于執(zhí)行失效的獎(jiǎng)勵(lì)對象選擇策略和基于相似性的獎(jiǎng)勵(lì)對象選擇策略進(jìn)行時(shí)間開銷的對比分析,其時(shí)間開銷展示如表6所示.

表6 基于不同獎(jiǎng)勵(lì)對象選擇策略的持續(xù)集成測試用例優(yōu)先排序時(shí)間開銷(s)

基于強(qiáng)化學(xué)習(xí)的持續(xù)集成測試用例優(yōu)先排序框架的時(shí)間開銷,不僅包括了獎(jiǎng)勵(lì)計(jì)算的時(shí)間、智能體的學(xué)習(xí)時(shí)間和測試用例優(yōu)先排序的時(shí)間,還考慮了獎(jiǎng)勵(lì)對象選擇的時(shí)間,以及相似性分析的時(shí)間.根據(jù)表6所示的時(shí)間開銷結(jié)果,明顯看出基于相似性的獎(jiǎng)勵(lì)對象選擇策略在大部分?jǐn)?shù)據(jù)集上均明顯增加了時(shí)間開銷,這是由于在每一周期進(jìn)行相似性分析增加了相應(yīng)的時(shí)間開銷,然而基于相似性的獎(jiǎng)勵(lì)對象選擇策略通過解決強(qiáng)化學(xué)習(xí)的獎(jiǎng)勵(lì)稀疏問題,加速了強(qiáng)化學(xué)習(xí)的學(xué)習(xí)速度,因此對于框架整體來說,其平均時(shí)間開銷的增加均是秒級,是可以接受的時(shí)間開銷增加.

綜上所述,基于相似性的獎(jiǎng)勵(lì)對象選擇策略在有限的時(shí)間開銷增加下,不僅通過獎(jiǎng)勵(lì)對象的增加有效地解決了基于強(qiáng)化學(xué)習(xí)的持續(xù)集成測試用例優(yōu)先排序獎(jiǎng)勵(lì)稀疏問題,還有效了提升了持續(xù)集成測試用例優(yōu)先排序質(zhì)量.

4 結(jié)論與展望

本文針對工業(yè)程序的持續(xù)集成測試存在頻繁迭代和測試失效低導(dǎo)致獎(jiǎng)勵(lì)稀疏的問題,在基于強(qiáng)化學(xué)習(xí)的持續(xù)集成測試用例優(yōu)先排序中,依據(jù)測試用例的歷史執(zhí)行過程和執(zhí)行時(shí)間提出了基于相似性的獎(jiǎng)勵(lì)對象選擇策略,在獎(jiǎng)勵(lì)失效測試用例的基礎(chǔ)上,通過選擇與失效測試用例存在相似的通過測試用例作為額外獎(jiǎng)勵(lì)對象,有效解決了獎(jiǎng)勵(lì)稀疏問題.提出的方法在有限時(shí)間開銷增長下,有效地提升了測試用例優(yōu)先排序效果.

未來進(jìn)一步研究構(gòu)建基于強(qiáng)化學(xué)習(xí)的持續(xù)集成測試用例優(yōu)先排序策略網(wǎng)絡(luò).通過自適應(yīng)學(xué)習(xí)測試用例的新特征以實(shí)現(xiàn)測試用例優(yōu)先排序策略的調(diào)整,從而生成適合后續(xù)的測試用例優(yōu)先排序策略.