多階段多目標(biāo)動態(tài)測試資源分配算法

牛福強(qiáng)，張國富,2，蘇兆品,2，岳 峰

(1.合肥工業(yè)大學(xué) 計算機(jī)與信息學(xué)院，安徽 合肥 230601；2.合肥工業(yè)大學(xué) 工業(yè)安全與應(yīng)急技術(shù)安徽省重點實驗室，安徽 合肥 230601)

0 引 言

獲得高質(zhì)量和滿足市場需求度的軟件是軟件測試最為重要的目標(biāo)，軟件測試?yán)孟臏y試資源檢測軟件故障，發(fā)現(xiàn)并修復(fù)軟件漏洞是獲取高可靠性軟件的必要途徑[1,2]。軟件測試消耗的資源接近軟件開發(fā)總資源的一半[3]。隨著基于搜索的軟件工程的迅速發(fā)展[7]，一些演化計算技術(shù)被用來求解測試資源分配問題[8,9]，如遺傳算法[10]、蟻群優(yōu)化[11]。

在現(xiàn)實環(huán)境當(dāng)中，軟件測試是動態(tài)的、不確定的，同一個測試模塊在不同測試階段所展現(xiàn)出的特征也有差別。軟件系統(tǒng)中的模塊錯誤數(shù)量在測試行為執(zhí)行前已經(jīng)被預(yù)估，其每個模塊相關(guān)參數(shù)和分配到的測試資源也不會隨著錯誤的發(fā)現(xiàn)、前期測試階段獲得的經(jīng)驗而進(jìn)行相應(yīng)的調(diào)整，這種靜態(tài)環(huán)境下的最優(yōu)化測試資源分配問題在以往工作中[4-6]進(jìn)行了非常全面的研究。Zeephongsekul等[12]通過統(tǒng)計歷史階段的發(fā)現(xiàn)的錯誤數(shù)量以及檢測出每個錯誤的時間點對下一個階段的模塊參數(shù)利用極大似然估計進(jìn)行了重估。Chaudhary等[13]針對最大化檢測錯誤數(shù)的優(yōu)化問題提出了一種基于差分進(jìn)化算法的多階段測試資源分配算法(MS-DE)。陸陽等[14]采取將測試資源劃分成多個階段分配給軟件系統(tǒng)，階段資源可以根據(jù)每個模塊的可靠性進(jìn)行相應(yīng)的調(diào)整，以便幫助解集更快收斂。但是模塊參數(shù)并沒有根據(jù)檢測出的錯誤數(shù)進(jìn)行參數(shù)的重估，仍然屬于測試行為未發(fā)生的靜態(tài)環(huán)境下，所進(jìn)行的多階段測試資源的預(yù)分配，與實際中的測試存在較大的差異，不符合動態(tài)測試資源分配中的動態(tài)屬性。

本文結(jié)合了傳統(tǒng)研究中基于演化算法多個目標(biāo)同時優(yōu)化的特點以及動態(tài)測試資源分配中的基于歷史信息動態(tài)調(diào)整模塊參數(shù)以及每個測試階段的測試資源。測試人員可以根據(jù)實際的需求在每個測試階段獲得的目標(biāo)解集中選出偏好解，根據(jù)該偏好解執(zhí)行測試并收集相關(guān)的錯誤信息，收集到的錯誤信息將會用于之后的測試階段參數(shù)的估計，從而使下一階段優(yōu)化中獲得符合實際的解決方案。并且能夠基于實際情況將有限的測試資源分配需求度高的模塊，從而獲得滿足市場需求的高可靠性軟件系統(tǒng)。

1 問題描述

圖1 總的可用測試時間多階段劃分

(1)

在每個測試階段執(zhí)行前，測試管理者都要從當(dāng)前階段算法給出最優(yōu)解集選取一個最符合當(dāng)前市場需求或者高可靠性的偏好解作為執(zhí)行方案。而該偏好解給出總消耗的測試時間必定小于或等于該測試階段可用的總測試時間，因此在第i階段可用的總測試時間與實際消耗的測試資源之間的關(guān)系滿足

(2)

(3)

可以求解上述一階微分方程，我們可以發(fā)現(xiàn)模塊j在階段i中平均檢測到的錯誤數(shù)與消耗的測試時間呈指數(shù)關(guān)系，如下

(4)

在衡量軟件系統(tǒng)質(zhì)量的標(biāo)準(zhǔn)中，軟件內(nèi)平均每個模塊剩余錯誤數(shù)量是軟件可靠性最為直接、有效的表述。每一個模塊在軟件系統(tǒng)中的相對重要程度隨著測試階段的不同而有所不同，可以根據(jù)需求進(jìn)行相應(yīng)的調(diào)整。軟件系統(tǒng)在第i個測試階段的剩余錯誤總數(shù)為

(5)

綜上所述，為能夠獲得滿足市場需求的軟件系統(tǒng)，在每個階段給予可用消耗的測試時間以及軟件系統(tǒng)剩余的錯誤總數(shù)雙重約束下，力求最小化軟件系統(tǒng)錯誤總數(shù)以及最小化測試時間消耗，從而形成多階段、兩目標(biāo)、動態(tài)求解測試時間分配優(yōu)化問題模型

(6)

2 多階段NSGA-II動態(tài)分配算法

2.1 NSGA-II

多目標(biāo)優(yōu)化算法NSGA-II[10]是最為經(jīng)典的演化算法之一，該優(yōu)化算法的性能已經(jīng)在以往的研究以及工程實踐中得到廣泛的認(rèn)可。NSGA-II能夠簡單有效選取全局最優(yōu)解，并且在同時優(yōu)化兩個目標(biāo)問題模型中具有較大的優(yōu)勢。經(jīng)過研究人員不斷研究，NSGA-II的性能也變得更加完善，但該算法的整體框架和基本思想沒有改變。多目標(biāo)算法NSGA-II針對兩個目標(biāo)雙重約束問題基本框架為：在測試時間限制范圍內(nèi)生成規(guī)模為N的初始種群，即含一個有N個解的解集，該N個解是隨機(jī)生成、廣泛分布的，對初始種群進(jìn)行非支配排序，非支配排序的原則是在兩個目標(biāo)能夠支配其它解排在上層，稱之為非支配解；在目標(biāo)中各有優(yōu)劣，將會排序分布在同一層。然后在非支配排序后種群中利用二進(jìn)制錦標(biāo)賽選擇兩個父代個體，進(jìn)行二進(jìn)制交叉以及多項式變異的遺傳操作，從而產(chǎn)生兩個子代個體。將父代與子代個體進(jìn)行合并，種群大小為2N，對合并后的種群進(jìn)行非支配排序，非支配排序過程中，不只通過兩個目標(biāo)的最優(yōu)程度進(jìn)行判斷，還需要加入個體違背約束的程度，一個個體違背約束的程度越高，得到的排序位置越靠近下層，淘汰的幾率也就越高。然后根據(jù)非支配排序的位置選取N個子代種群，不同層的選擇上層，較優(yōu)的非支配解將容易保存下來；同層之間計算擁擠距離，保留擁擠距離相對較大的，從而保證子代種群的多樣性。通過非支配關(guān)系以及擁擠距離保持子代的精英性以及多樣性。子代總是能夠支配父代，重復(fù)上述步驟，不斷趨近Pareto前沿[14]，直到滿足算法終止條件。具體流程如圖2所示。二進(jìn)制錦標(biāo)賽選擇、模擬二進(jìn)制交叉和多項式變異3個基本操作的具體細(xì)節(jié)請參照文獻(xiàn)[16]，這里不再贅述。

圖2 NSGA-II算法流程

2.2 參數(shù)估計

(7)

(8)

利用上述的對數(shù)似然函數(shù)可以得到如下的微分方程組

(9)

2.3 種群重新初始化

2.4 約束處理

根據(jù)上一節(jié)編碼方式和種群初始化，我們不難發(fā)現(xiàn)即使個體中的每個元素符合約束條件，個體有可能不符合約束式(6)中約束條件。除此之外，根據(jù)演化算法的迭代進(jìn)化過程中，遺傳操作包括交叉操作、變異操作都有可能導(dǎo)致個體中的元素以及個體違背上述的約束條件。盡管演化算法能夠淘汰不符合約束的個體，大量的違規(guī)個體通過遺傳操作將會大概率產(chǎn)生的違規(guī)的子代，不利于種群的進(jìn)化，減慢種群的收斂速度。因此我們需要對個體中的元素以及個體進(jìn)行測試時間上的約束，幫助算法快速收斂。本文對種群初始化以及交叉、變異操作后，對種群中的每個個體以及個體元素進(jìn)行密切監(jiān)控，若存在違背約束條件則對編碼進(jìn)行修正，具體修正思路如下：

上述約束處理能夠減少違規(guī)解的參與遺傳進(jìn)化當(dāng)中，有利于加快種群進(jìn)化的收斂速度；另外這種約束處理添加了隨機(jī)性能夠保證個體的合法性，又能夠保持種群的多樣性。

2.5 算法描述

綜上所述，我們將參數(shù)估計、種群初始化以及約束處理與傳統(tǒng)的NSGA-II相結(jié)合產(chǎn)生多階段兩個目標(biāo)動態(tài)測試時間分配算法(MS-NSGA-II)，該算法的整體思想是，能夠解決同時優(yōu)化兩個目標(biāo)、雙重約束下的測試時間分配問題。測試管理者可以根據(jù)偏好選取符合實際的解，根據(jù)偏好解動態(tài)調(diào)整后續(xù)測試階段的可用測試時間。

圖3 MS-NSGA-II多目標(biāo)動態(tài)測試時間分配算法流程

3 實驗結(jié)果與分析

3.1 實驗參數(shù)和評價指標(biāo)

在進(jìn)行實驗驗證之前，我們需要配置相應(yīng)的軟件系統(tǒng)模塊參數(shù)以及算法相關(guān)參數(shù)。

表1 模塊的初始參數(shù)

在本文中我們結(jié)合了兩個目標(biāo)模型和多階段的特性，為了說明所提出的MS-NSGA-II的優(yōu)點，將采用動態(tài)單目標(biāo)MS-DE[13]和靜態(tài)多目標(biāo)NSGA-II與其對比，3種算法所用到的參數(shù)見表2。

表2 算法的基本參數(shù)

另外，我們需要對算法的結(jié)果進(jìn)行處理和評估，以便比較算法之間的優(yōu)劣。評價多目標(biāo)優(yōu)化結(jié)果的兩種經(jīng)典標(biāo)準(zhǔn)容量值(capacity)和滿足客戶解的標(biāo)準(zhǔn)覆蓋指標(biāo)[10](standard cover metric)。容量值是表示算法解集中滿足一定標(biāo)準(zhǔn)的解的數(shù)量，數(shù)量越多算法性能越好；覆蓋指標(biāo)是解集A中的解覆蓋解集B中所有解的百分比，百分比大的算法性能優(yōu)良。

3.2 與動態(tài)單目標(biāo)的對比

在該部分實驗當(dāng)中，我們比較MS-NSGA-II以及MS-DE兩種算法。首先針對30(n=30)個模塊的軟件系統(tǒng)進(jìn)行實驗，另外還需要將總的測試時間分為3個測試階段(p=3)：[0,70 000]、[70 000,130 000]、[130 000,200 000]。MS-DE為單目標(biāo)優(yōu)化，因此只針對式(6)中的Si優(yōu)化。每個階段檢測出的錯誤數(shù)根據(jù)式(4)的值附近隨機(jī)給出，兩種算法保持一致。每個階段的偏好解設(shè)置剩余錯誤數(shù)最少的(MS-DE只能獲取該類型的解)。將所獲得的最終解集進(jìn)行畫圖，如圖4所示。由圖可以看出，MS-DE優(yōu)化后獲得一個單解，而MS-NSGA-II每個測試階段都會獲得一個解集，最終解集中有相當(dāng)一部分解的系統(tǒng)剩余錯誤數(shù)少于MS-DE的單解。因此我們可以得出MS-NSGA-II能夠提供多個候選解的同時，系統(tǒng)剩余錯誤數(shù)量最少的解優(yōu)于MS-DE的單解。

圖4 MS-DE和MS-NSGA-II得到的解集

為了更加凸顯出MS-NSGA-II的優(yōu)點，我們以MS-DE的單解作為偏好解，在MS-NSGA-II的解集中挑選出好于該偏好解(Si目標(biāo)值小于等于4.457 99)統(tǒng)計數(shù)量，并且將剩余錯誤數(shù)最小的列見表3。由表3中數(shù)據(jù)可以得到無論從解的質(zhì)量以及數(shù)量，MS-NSGA-II的解集都要優(yōu)于MS-DE的單解，因此MS-NSGA-II的算法性能要好于MS-DE。

表3 系統(tǒng)剩余錯誤數(shù)苛刻閾值下的解

3.3 與靜態(tài)多目標(biāo)的對比

同樣我們針對30個模塊系統(tǒng)進(jìn)行測試時間分配，NSGA-II和MS-NSGA-II兩個算法的之間的性能。由于NSGA-II為靜態(tài)環(huán)境下的測試時間分配，所以只有一個測試階段；在此部分為了說明多階段的優(yōu)點我們將MS-NSGA-II的測試時間劃分成4種環(huán)境：2個、3個、4個和5個測試階段與NSGA-II進(jìn)行比較，每個測試環(huán)境各測試階段的測試資源劃分見表4。

表4 每個測試環(huán)境的階段數(shù)和測試時間劃分

針對兩種算法每個環(huán)境進(jìn)行30組的實驗，選取其中一組實驗畫圖，如圖5所示。由于兩個算法都獲得是解集，因此可以從圖中看出兩個解集匯成不同的曲線，該曲線能夠說明測試時間和剩余錯誤數(shù)之間的關(guān)系。另外4種環(huán)境下MS-NSGA-II的米子點解集處于NSGA-II點解集的下方，通過支配關(guān)系的比較，我們能夠得出MS-NSGA-II的解集要好于NSGA-II的解集。另外我們看出測試階段數(shù)越多解集的質(zhì)量并不一定好，在環(huán)境3、4中的解集質(zhì)量不如環(huán)境1、2中的解集質(zhì)量。MS-NSGA-II解集好于NSGA-II原因在于多階段的參數(shù)估計形成正反饋，可以將有限的測試時間分配給更需要的模塊，因此表明MS-NSGA-II的性能優(yōu)于NSGA-II。為了說明算法能夠動態(tài)調(diào)整各個測試階段的測試時間，充分的利用測試時間，我們在環(huán)境4中(p=5時)選取兩個模塊，將測試階段和每個階段分配到的測試時間畫圖，如圖6所示。從圖中我們可以得到，模塊1在前面階段分配到的測試資源較多，也就是可靠性達(dá)到一定時，算法將不會再把測試時間分配給該模塊。模塊2在前面測試階段分配到的資源較少，可靠性較低，算法通過調(diào)整在后期測試階段分配給該模塊的資源增多。因此MS-NSGA-II算法具有動態(tài)調(diào)整資源的功能。

圖5 NSGA-II和MS-NSGA-II得到的解集

圖6 每個階段分配的測試時間

另外，以上比較了兩種算法整個解集的比較，我們還需要采用更為嚴(yán)格的標(biāo)準(zhǔn)比較兩種算法的性能，即設(shè)置更為嚴(yán)格的閾值解Si≤6.6下的兩種算法容量值之間的比較，以及符合嚴(yán)格閾值解的覆蓋值比較。經(jīng)過30次實驗結(jié)果進(jìn)行統(tǒng)計平均見表5，由表所得MS-NSGA-II得到的平均容量值要大于NSGA-II，盡管在測試環(huán)境4中，MS-NSGA-II略大于NSGA-II，說明在相同的實驗環(huán)境當(dāng)中，MS-NSGA-II多階段反饋能夠幫助解集快速收斂的特點，從而獲得的更多的滿意解。在30次實驗中挑選出Si≤6.6的解完成覆蓋值的比較并進(jìn)行統(tǒng)計分析，我們給出了覆蓋值的均值和標(biāo)準(zhǔn)差, 并基于Wilcoxon Rank Sum檢驗[17](0.05的顯著性水平)進(jìn)行顯著性分析，用黑體標(biāo)出差異顯著的最佳均值。如表6所示，在測試環(huán)境1、2、3中MS-NSGA-II覆蓋值要明顯優(yōu)于NSGA-II，說明在前3個測試環(huán)境中，MS-NSGA-II能夠挖掘到了更好的測試時間分配方案。但是，在測試環(huán)境4中MS-NSGA-II并沒有表現(xiàn)出較大的優(yōu)勢。綜合圖5以及表5、表6中數(shù)據(jù)，容量值和覆蓋值都有所下降，因此得出測試階段數(shù)量增多并不能夠幫助獲得高質(zhì)量的解集。原因在于總的迭代次數(shù)是有限的，測試階段數(shù)增加，每個測試階段的迭代次數(shù)減少，各階段的解集并沒有達(dá)到算法收斂需求。

表5 NSGA-II和MS-NSGA-II的平均容量值

表6 NSGA-II和MS-NSGA-II的覆蓋值(均值±標(biāo)準(zhǔn)差)

4 結(jié)束語

軟件測試消耗大量的測試資源，本文將動態(tài)優(yōu)化以及多目標(biāo)相結(jié)合，提出一種基于NSGA-II的多階段兩個目標(biāo)動態(tài)測試資源分配算法。該算法兼具了動態(tài)測試資源多階段正反饋的屬性以及多目標(biāo)同時優(yōu)化的優(yōu)點，其中參數(shù)估計、種群初始化以及約束處理能夠自適應(yīng)調(diào)整每個測試階段的測試資源幫助解集快速收斂。通過與動態(tài)單目標(biāo)MS-DE和靜態(tài)多目標(biāo)NSGA-II的對比實驗分析，MS-NSGA-II能夠提供更多更高質(zhì)量的測試資源分配方案。在未來的研究中，我們將致力于如何合理的劃分測試階段。