動態可靠性約束的多階段測試資源分配研究

占德志，張國富，2，3，蘇兆品，2，3，岳 峰，2

（1.合肥工業大學計算機與信息學院，合肥 230601；2.合肥工業大學工業安全與應急技術安徽省重點實驗室，合肥 230601；3.安全關鍵工業測控技術教育部工程研究中心，合肥 230601）

0 概述

軟件測試的目的是檢測軟件故障、發現和糾正軟件缺陷從而提高軟件的可靠性，其對軟件項目開發至關重要［1-3］。對于一個軟件開發項目而言，有接近一半的軟件開發資源耗費于軟件測試［4］。實際可分配的測試資源往往有限，因此，在軟件測試中，軟件項目經理的首要任務是制定合理且高效的測試資源分配方案，實現以最小代價（指測試成本和測試資源消耗）獲得最大軟件可靠性［5-7］的目的。

近年來，為了在軟件可靠性、測試成本和測試資源之間實現一個理想的均衡，測試資源分配被描述為一個多目標優化問題，以最大程度地提高軟件可靠性并盡可能地降低測試成本和測試資源消耗［8-10］。部分多目標進化算法（Multi-ObjectiveEvolutionary Algorithms，MOEAs）被用于解決多目標測試資源分配問題，如非支配排序遺傳算法［11-12］和加權歸一化多目標差分進化算法［13］等。與單目標優化算法只輸出單個解相比，MOEAs可以得到一個Pareto最優解集，從而為用戶提供多種選擇，這些不同的選擇分別對應可靠性、成本和測試時間之間不同的折中方案，因此，可以幫助用戶對整個測試周期進行更加合理的安排［14］。

但是，上述研究均針對靜態優化環境，都是簡單地假設軟件測試只有一個完整的靜態階段。在實際的軟件測試過程中，整個測試周期往往會被劃分成若干個測試階段，在不同測試階段用戶可能有不同的需求，這就需要根據每個階段的測試需求動態制定不同的測試資源分配方案。為此，LEUNG［15］利用拉格朗日乘子法最小化每個階段的平均錯誤數，該方法屬于單目標多階段測試資源分配方案。在多階段多目標測試資源分配（Multi-Stage Multi-ObjectiveTesting Resource Allocation，MSMOTRA）方面，陸陽等人［16］利用多目標差分進化算法，在每個階段根據不同的測試時間總量來實現最大化可靠性和最小化測試成本的目的，但是，該方法忽略了一個重要細節，即軟件中的模塊在經歷了上一階段的測試后其關鍵模塊參數（如剩余錯誤數、錯誤檢測率等）都已經發生變化，如果還是按照初始參數進行優化，將缺少前一測試階段的測試結果反饋，從而導致算法不能達到更深層的收斂，給出的解往往嚴重偏離實際最優解。為了解決這一問題，牛福強［17］首先根據上一階段的測試資源分配方案和測試結果對模塊參數進行重新估計，然后利用新的模塊參數和第三代廣義多目標差分進化（Generalized Differential Evolution 3，GDE3）算法［18］在當前階段進行優化。但是，該方法在選擇每個階段的最優方案時偏好性太強，只考慮最優非支配解集中可靠性最高的解，而沒有考慮測試成本和測試時間，不能充分體現多目標優化的優勢。

雖然已有研究可以很好地解決多目標測試資源分配問題，但是通常只關注測試時間總量約束，沒有考慮用戶對軟件的可靠性需求，導致在解集中存在許多可靠性非常低的測試資源分配方案，這些無用解帶來了巨大的計算開銷和信息冗余，也背離了研究多目標測試資源分配問題的初衷。

本文從用戶對軟件可靠性需求的角度出發，構建一種動態可靠性約束的多階段多目標測試資源分配模型，基于每個階段不同的可靠性約束來為各個模塊分配一個測試時間下限，以降低搜索空間?；贕DE3、參數估計、種群重新初始化和最優方案選擇，提出一種多階段多目標測試資源分配算法，以在滿足用戶對軟件可靠性需求的同時為用戶提供滿意的解集。

1 問題描述

與慣例相同［11-13］，本文基于經典的并串聯模塊軟件系統研究測試資源分配問題。如圖1所示，軟件系統包括m∈N個子系統，每個子系統Sj(j∈(1，2，…，m))包含nj∈N個模塊。測試資源分配的目的是給系統中的每個模塊Mjk(k∈(1，2，…，nj))分配合適的測試資源，以提高系統的整體可靠性。

圖1 并串聯模塊軟件系統結構Fig.1 Structue of parallel-series modular software system

在軟件測試過程中，主流的測試資源分配問題均是針對測試時間分配［11-13］，考慮如何合理分配軟件測試人員的總工作時間（即軟件測試人員數乘以每個測試人員的工作時間，通常以小時為單位）。與多數已有研究相同［11-13］，本文也依據測試時間來分析測試資源分配問題。不失一般性，本文采用文獻［17］中測試階段的劃分方式，假設總的測試時間T*被劃分成p∈N個連續的測試階段，其中，第i∈（1，2，…，p）個階段的測試時間預分配量為，滿設模塊Mjk在階段i分配到的測試時間為，則階段i的實際分配總量Ti應該小于前i個階段的預分配量之和減去前i-1個階段的實際分配量之和［17］，計算如下：

在前面每個階段選取的分配方案不一定恰好用完預分配量，因此，可能在每個階段都有少量的剩余測試時間可供下一階段使用。

子系統Sj是由nj個子模塊并聯組成的，當子模塊都不工作時，該子系統壽命結束，可以根據Mjk模塊的可靠性求出子系統Sj在第i個測試階段的可靠性［17］，計算如下：定義，第i個測試階段的系統可靠性Ri可定義如下：

根據文獻［17］中對并串聯模塊軟件系統的可靠性

綜上，本文所研究的動態可靠性約束的多階段多目標測試資源分配問題（DRC-MSMOTRA）可以形式化表示為：

在每個測試階段需要滿足不同的可靠性約束和測試時間約束，因此，式（6）是一個典型的動態約束多目標優化問題，解決該問題的難點是每個階段的解空間都大不相同，傳統的優化方法很難適應搜索空間的動態變化，因此，本文采用適應性更高的多目標進化算法進行求解。

2 多階段多目標測試資源分配算法設計

本文選擇廣義多目標差分進化算法GDE3［18］作為DRC-MSMOTRA問題的基本求解框架，這是因為GDE3在針對3個目標優化問題時相比非支配排序遺傳算法［11-12］速度更快，需要設置的參數更少，算法收斂性更好。關于GDE3的詳細介紹可參考文獻［18］，本文結合基本GDE3，提出多階段動態可靠性約束處理算法MS-DRC-GDE3。MS-DRC-GDE3算法的每個個體采用一維實數編碼，編碼中的每一個基因位代表一個模塊被投入的測試時間。每個個體的優劣用式（6）中的f1、f2、f33個函數同時進行評估。

MS-DRC-GDE3算法流程如圖2所示，具體步驟為：

步驟1判斷i是否已達到最大階段數p，如果已達到，則結束算法；否則，執行步驟2。

步驟2判斷當前階段是否為第1個階段，如果不是，則根據前面階段的測試結果對所有模塊重新進行參數估計，然后根據新的模塊參數對種群重新進行初始化以生成父代種群。

步驟3對種群執行選擇、差分變異和交叉等進化操作以生成子代種群，再將父代和子代種群一起進行非支配排序和擁擠度計算，選擇最優的個體組成新的父代種群。

步驟4判斷算法是否達到本階段的最大迭代次數，如果未達到，則執行步驟3；否則，對最后的最優解集執行加權歸一化處理，選擇適應度最小的解作為階段i的最優分配方案，當階段i測試完畢，進入下一階段，i=i+1，執行步驟1。

圖2 MS-DRC-GDE3算法流程Fig.2 Procedure of MS-DRC-GDE3 algorithm

2.1 模塊參數估計

在多階段測試資源分配中，前面階段的測試結果會直接影響模塊的關鍵參數，包括剩余錯誤總數與錯誤檢測率因此，在一個測試階段i執行完畢后，需要對i+1階段的模塊參數重新進行估計，否則會誤導算法的進化。在軟件測試中，通常的做法是收集在每個模塊上消耗的測試時間和檢測出的錯誤數，然后利用這些數據對模塊的參數進行極大似然估計［17］，計算如下：

2.2 種群初始化

在DRC-MSMOTRA問題中，每個階段的可靠性約束和測試時間約束均不相同，因此，在種群進化前需要對種群按照新的約束空間重新進行初始化。鑒于每個階段的迭代次數不可能無限大，因此，如何在較少的迭代次數內迅速搜索到較好的解是首先需要解決的問題。一個最直接的做法就是在種群初始化時盡量讓種群靠近最優解集區域，為此，本文通過模型分析來降低搜索空間。以第i個測試階段為例，因為可靠性的取值為［0，1］之間的實數，由式（2）的連乘積可以得到如下的必要條件：

在子系統Sj中，至少要有一個模塊分配的測試時間滿足上式，本文將該測試時間下限記為：

本文在種群初始化時利用上述條件盡量讓種群靠近最優解集區域。對于第1個測試階段，個體編碼中每個模塊對應的基因位隨機初始化為：

對于第i＞1個階段，由于前一階段的分配方案對于本階段具有一定指導作用，比如可以顯示哪些模塊比較耗時。基于此，本文根據前一階段方案的分配比例來進行初始化，如下：

容易驗證通過式（9）和式（10）或式（11）初始化的個體都滿足測試時間的上下界約束。需要指出的是，上述初始化過程并不能保證每個個體都滿足可靠性約束下界，因為式（8）只是一個必要條件。本文目的是盡可能地讓個體靠近滿足可靠性需求的區域，從而讓個體迅速逼近最優解集，加快算法的收斂。

2.3 加權歸一化處理

在每一個測試階段，當種群進化到最大迭代次數時，MS-DRC-GDE3算法會輸出一個最優解集，用戶需要從解集中挑選一個解作為當前階段的測試時間分配方案。傳統的做法是選擇解集中可靠性目標值最大的解，但這種選擇方式偏好性太強，忽略了測試成本和測試時間消耗的平衡。本文采用文獻［13］中的加權歸一化方法來選取最優解。加權歸一化方法可以簡單快速地衡量多目標解的優劣，該方法在衡量解的分布性方面有較大優勢，同時可兼顧收斂性，已在多目標優化問題的求解中得到廣泛應用［19-20］。

加權歸一化方法首先對解集中的每一個目標進行min-max歸一化，以消除3個目標之間的統計誤差，其次利用復合目標適應度函數將多目標整合成復合單目標其中，wy為目標y的加權值，f(x)表示第x個多目標解的適應度值。由于本文的目的是權衡可靠性、測試成本和測試時間3個目標，因此適應度函數表示為：

最后，比較每個解的適應度值，選取適應度值最小的解作為當前階段的最優測試資源分配方案。

2.4 時間復雜度分析

時間復雜度直接影響算法的收斂速度以及運行時間。MS-DRC-GDE3算法的基本流程如圖2所示，假設種群的規模為N，優化的目標個數為M，在種群初始化以及選擇、交叉和變異階段只處理最高等級的N個個體，該操作的時間復雜度為O(N)。在非支配排序和擁擠度計算階段算法的時間復雜度與原有的GDE3算法保持一致，為O(MN·lbN)［18］。加權歸一化處理階段也僅處理最高等級的N個個體，同理，其復雜度也是O(N)。另外，本文所提算法為多階段算法，其總階段數為P，每個階段的迭代次數為Gmax。綜上，MS-DRC-GDE3算法的總時間復雜度為O(P·Gmax·MN·lbN)。

3 實驗結果與分析

3.1 實驗參數和評價指標

為了驗證本文所提模型和算法的有效性，模擬2個并串聯模塊軟件系統進行測試。第1個系統共有11個子系統、30個模塊，稱為復雜系統，第2個系統共有16個子系統、50個模塊，稱為大型系統。系統模型參數信息如表1所示，系統中的初始模塊參數范圍如表2所示，測試階段相關參數如表3所示。對于每個系統，根據表2所給的范圍隨機生成10組初始模塊參數，與表3所給的約束參數一起構成相應的實驗測試實例，且每個實例在Intel Core i7CPU、10 GB RAM個人計算機上獨立運行30次。

表1 系統模型參數信息Table 1 System model parameters information

表2 初始模塊參數范圍Table 2 Initial parameters range of modules

表3 測試階段相關參數Table 3 Related parameters of testing stage

為了驗證本文所提MS-DRC-GDE3算法的有效性，將其與文獻［17］中的多階段測試資源分配算法MS-GDE3進行對比分析。為了對比的公平性，加權歸一化過程中的w1、w2、w3采用文獻［13］中的推薦設置｛0.1，0.4，0.5｝，MS-DRC-GDE3算法的其他參數與MS-GDE3算法保持一致，種群規模為100，交叉概率為0.9，變異概率為0.7。

為了對比不同算法所得分配方案的優劣，本文采用經典的覆蓋值（Coverage Value，CV）［21］指標來評估不同算法的收斂性。覆蓋值提供了一種最直接的比較方式，假設A和B分別是2種不同的算法所獲得的解集，A中一個解的所有目標值都不比B中另一個解的所有目標值差，則認為前者覆蓋了后者。CV（A，B）表示B被A中解集所覆蓋的百分比，即B中被A覆蓋的解的個數與B中解的總數的比值。若CV（A，B）大于CV（B，A），則意味著A中的解相比B更優。在計算時，為了使算法在每個實例中獲得的解集更具統計學意義，首先將每個算法對應每個實例運行30次的解組合在一起，然后去掉重復的解，最后計算每個算法組合解集之間的CV值［22］。此外，為了衡量算法的整體性能，本文采用較流行的超體積值指標［11，13］。超體積表示非支配解集和參考點之間的空間體積大小，其可以從整體上衡量解集的收斂性和多樣性，超體積值越高表示解集的整體質量越高。在計算超體積時，參考點的選擇至關重要。對于每個實例，本文合并所有算法30次運行所獲得的解集，然后去掉重復解并根據非支配關系對所有解進行排序，去掉所有被支配的解，最后將剩余非支配解集中每個目標的最大值略微放大作為最終的參考點［22］。

3.2 不同模型的對比

與文獻［17］中的多階段模型MSMOTRA不同，本文DRC-MSMOTRA模型為了滿足用戶的可靠性需求，在每個階段都有不同的可靠性約束，本次實驗將分析上述2種模型的優劣。根據表1的2個模擬系統各隨機生成10個不同的實例，為了對比的公平性，基于與MSMOTRA模型契合的MS-GDE3算法進行測試。

2種模型所得解集的覆蓋值結果如表4所示，其中，A和B分別表示DRC-MSMOTRA模型和MSMOTRA模型，較優的覆蓋值用加粗字體表示。從表4可以看出，在復雜系統中，與MSMOTRA模型獲得的解相比，DRC-MSMOTRA模型在3個階段中解的覆蓋值分別提高約97個、42個和48個百分點，平均提高了約62個百分點。對于大型系統，與MSMOTRA模型獲得的解相比，DRC-MSMOTRA模型在3個階段中解的覆蓋值分別提高約90個、61個和26個百分點，平均提高了約59個百分點。上述實驗結果表明，在不同軟件系統不同參數的條件下，與MSMOTRA模型相比，DRC-MSMOTRA模型可以獲得更優的解，更能滿足用戶的可靠性需求。

表4 2種模型的覆蓋值對比結果Table 4 Comparison results of coverage values of two models

需要指出的是，在第2階段和第3階段，在極個別實例上會出現CV（A，B）與CV（B，A）相差不是很大的情況，尤其是在大型系統的第3階段，這說明MS-GDE3算法在DRC-MSMOTRA模型上有時也能獲得理想的解集，因此，有必要進一步測試分析MS-GDE3算法在DRC-MSMOTRA模型上的綜合表現。

3.3 不同算法的對比

本文根據表1的2個模擬系統隨機生成10個不同的實例，基于本文DRC-MSMOTRA模型對比分析MS-DRC-GDE3算法和MS-GDE3算法的性能。2種算法得到的覆蓋值結果如表5所示，其中，A和B分別表示MS-DRC-GDE3算法和MS-GDE3算法。從表5可以看出，在復雜系統中，與MS-GDE3算法相比，MS-DRC-GDE3算法在3個階段中解的覆蓋值分別提高約73個、66個和67個百分點，平均提高了約69個百分點。對于大型系統，與MS-GDE3算法相比，MS-DRC-GDE3算法在3個階段中解的覆蓋值分別提高約76個、75個和89個百分比，平均提高了約80個百分比。上述實驗結果表明，在不同軟件系統不同參數的條件下，MS-DRC-GDE3算法在每個階段所獲解的質量均高于MS-GDE3算法。

表5 2種算法的覆蓋值對比結果Table 5 Comparison results of coverage values of two algorithms

為了進一步分析2種算法的整體性能，對比2種算法所得解集的超體積的均值和標準差，結果如表6、表7所示，括號內為標準差。從表6、表7可以看出，MS-DRCGDE3算法的超體積明顯優于MS-GDE3算法，這說明MS-DRC-GDE3算法的解集整體質量更高。此外，標準差能夠體現數據的波動幅度，在第1階段，MS-DRCGDE3算法的超體積標準差比MS-GDE3算法小一個數量級，在第2、第3階段，雖然MS-DRC-GDE3算法的超體積標準差比MS-GDE3算法略大，但是結合均值和標準差明顯可以看出，MS-DRC-GDE3算法的超體積實際波動都比MS-GDE3算法小，這說明MS-DRC-GDE3算法比MS-GDE3算法更加穩定，可以在收斂性和多樣性之間實現更好的平衡。造成上述結果的原因是MSDRC-GDE3算法根據每個階段中用戶的可靠性需求推導出每個模塊的測試時間下限，根據該最低時間要求對種群進行初始化，從而使得整個種群迅速地向用戶滿意的解區域逼近。此外，MS-DRC-GDE3算法采用的加權歸一化方法，可以取得可靠性、成本和測試時間三者之間的均衡，從而在每個階段使種群有更多的空間去探索更好的解。

表6 2種算法在復雜系統中的超體積結果對比Table 6 Comparison of super volume results of two algorithms in complex system

表7 2種算法在大型系統中的超體積結果對比Table 7 Comparison of super volume results of two algorithms in large scale system

為了更加直觀地解釋超體積指標代表的含義，圖3給出2種算法分別在復雜系統實例6、大型系統實例5上最后階段的解集的分布，2種對比算法在這2種實例上的超體積值差異較大，可以更加清晰地展現超體積值的特點。從圖3可以看出，與MS-GDE3算法相比，MS-DRC-GDE3算法得到的解在目標空間的分布更廣，具有更好的多樣性。此外，MS-DRCGDE3算法的收斂性比MS-GDE3算法更好，MSDRC-GDE3算法解集中有相當多的分配方案明顯優于MS-GDE3算法，即前者具有更高的可靠性、更低的測試成本和更短的測試時間。

圖3 2種算法所獲解的分布Fig.3 Distribution of solutions obtained by two algorithms

4 結束語

基于多目標進化算法的多目標測試資源分配可以給用戶在可靠性、成本和測試時間上提供較多折中的方案，從而使用戶有更多的體驗，但已有測試資源分配方案大多只考慮測試時間約束而忽略了用戶的可靠性需求，導致解集中存在大量可靠性很低的方案，降低了用戶滿意度。本文針對多階段測試資源分配問題，從用戶對軟件的可靠性需求角度出發，構建一種動態可靠性約束的多階段多目標測試資源分配模型，基于模塊參數估計、考慮時間下限的種群初始化、加權歸一化、多目標差分進化算法，設計一種動態可靠性約束的多階段多目標測試資源分配算法。實驗結果表明，本文所提模型和算法具有有效性且能夠取得良好的資源分配效果。下一步將考慮成本約束并嘗試基于成本約束來分析和推演每個模塊的測試時間上限，此外，還將改進算法中的擁擠度計算等環節，從而進一步提升算法的整體性能。