多階段多目標動態測試資源分配算法

牛福強，張國富,2，蘇兆品,2，岳 峰

(1.合肥工業大學 計算機與信息學院，安徽 合肥 230601；2.合肥工業大學 工業安全與應急技術安徽省重點實驗室，安徽 合肥 230601)

0 引 言

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

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

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

1 問題描述

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

(1)

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

(2)

(3)

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

(4)

在衡量軟件系統質量的標準中，軟件內平均每個模塊剩余錯誤數量是軟件可靠性最為直接、有效的表述。每一個模塊在軟件系統中的相對重要程度隨著測試階段的不同而有所不同，可以根據需求進行相應的調整。軟件系統在第i個測試階段的剩余錯誤總數為

(5)

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

(6)

2 多階段NSGA-II動態分配算法

2.1 NSGA-II

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

圖2 NSGA-II算法流程

2.2 參數估計

(7)

(8)

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

(9)

2.3 種群重新初始化

2.4 約束處理

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

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

2.5 算法描述

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

圖3 MS-NSGA-II多目標動態測試時間分配算法流程

3 實驗結果與分析

3.1 實驗參數和評價指標

在進行實驗驗證之前，我們需要配置相應的軟件系統模塊參數以及算法相關參數。

表1 模塊的初始參數

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

表2 算法的基本參數

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

3.2 與動態單目標的對比

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

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

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

表3 系統剩余錯誤數苛刻閾值下的解

3.3 與靜態多目標的對比

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

表4 每個測試環境的階段數和測試時間劃分

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

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

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

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

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

表6 NSGA-II和MS-NSGA-II的覆蓋值(均值±標準差)

4 結束語

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