軟件測試資源與成本管控和最優發布策略

張 策，崔 剛，劉宏偉，孟凡超，傅忠傳

(1.哈爾濱工業大學計算機科學與技術學院，150001哈爾濱;

2.哈爾濱工業大學(威海)計算機科學與技術學院，264209山東威海)

以可靠性為核心的軟件質量通常與測試花費的時間、測試資源的消耗行為、測試方法緊密相關.測試時間延長，成本上升，可靠性獲得增長，但會增加推遲軟件發布的風險［1］;測試時間不足，成本受控，但發布后可靠性難以保證，增大了失效導致的連帶風險.顯然，測試過程中，測試資源的管理，確定影響成本的因素以及決策發布時間，對軟件質量自身與軟件公司的聲譽有著重要影響.

本文對圖1軟件測試中以可靠性為目標的軟件測試資源管控，成本模型與最優發布策略內容進行綜合評述.首先介紹有關概念，將研究內容劃分為4個部分進行闡釋，并給出其相互關系內涵，從實現技術分類角度討論了研究內容間差異;然后將其歸一化為5個子方面并選取典型模型進行歸類比較，最后給出結論.

1 基本概念

定義1 測試資源(testing resource，TR).

TR指軟件測試過程中所花費的資源，包括人力成本、CPU時間、執行的測試案例數量等，也稱之為測試工作量(testing effort，TE)［2-4］.

定義2 軟件可靠性增長模型 (software reliability growth model，SRGM).

SRGM基于失效數據，描述軟件測試過程中累積檢測的故障數量，TE與測試時間等的數學關系，是實現建模軟件可靠性提高過程的數學工具.

定義 3 最優發布策略 (optimal release policy，ORP).

ORP為達到測試的預期目標而確定軟件測試的最優時間長度.

定義4 軟件成本(Cost).

軟件成本是指軟件測試與運行階段為提高可靠性與確保軟件正常運行以及不期事件發生而連帶引發等所花費的成本總和.

圖1 以可靠性為核心的測試資源與成本管控和最優發布

2 研究問題與分類評述

軟件測試在檢測與排除掉Bug的過程中，不斷提高可靠性等質量屬性.由于測試過程本質上是一個受多因素制約的隨機過程，其涵蓋較多的研究內容.在對現有相關研究工作進行分類和梳理的基礎上，圖2描述了在軟件測試中以發布預期要求軟件為主要目標的相關研究活動內容.

圖2 研究問題分類及內在關系

從圖2可以看出:1)資源分配為模塊/構件分配一定量的測試資源;2)資源控制對所分配資源的消耗過程進行定量約束;3)成本模型實現軟件總成本的建模與控制，對風險超支進行管理; 4)最優發布實現在既定目標下最優發布可信的軟件制品.總體而言，測試資源管理和控制可實現資源的有效分配與消耗利用，對于達到預期可靠性以及成本不超支可建立重要保障，同時也為軟件的最優發布決策建立重要決策支持.這樣，也為確保發布資源消耗與可靠性受控的軟件提供保障.

2.1 測試資源分配

軟件測試中，軟件管理者首先應對資源進行有效分配.當前，測試資源分配主要應用在構件軟件 (component-based software，CBS)的模塊測試中［4］，可分類描述為表1中的5種情況.顯然，從最小化剩余故障或軟件測試成本的角度來進行測試資源分配研究居多.這里，需要特別指出:

1)表1中的第1和4種情況并非等價，例如，在不完美排錯情況下［16］，軟件中總的故障數量可能由于修改中引入新故障現象而存在一定量增加的過程.

2)測試時間分配在效用上與測試資源(預算)分配是可以等效的［9-10，13，17］.這是因為，在上個世紀80年代，TE被認為是測試時間［17］，但自90年代開始后，測試資源被認為是TE［4］，或者是TE的一種表示.

3)即使已采用了最優分配策略，所排除掉的故障也是有限的，因為測試會受到時間與成本的限制.

表1中5種模塊間最優的資源分配方案均是從不同的單一目標提出的優化模型，適用于單因素限制下的情況.顯然，提出多因素下最優分配模型也是學者們研究的重點.另外，測試資源分配應兼顧到體系結構和構件間的差異特征，應結合更多的實際來統籌考慮.

2.2 測試資源控制

測試資源控制用以對所分配資源的消耗過程進行優化控制，提高測試效率［18-19］，實現可靠性的預期增長.典型地，該問題可以描述為:1)設CBS，S= {Ci｜1≤i≤N}，規定模塊測試的終止時間為T2; 2)基于所建立的SRGM，Ci的測試資源消耗行為在T1(0＜T1＜T2)被估計;3)軟件管理人員根據T2時設定的目標(例如，應達到預期剩余故障)應確定在T1為Ci分配合適的測試資源ei.

另一方面，為了檢測更多的故障，軟件管理人員在必要的時間點進行TE的主動調整或可引入新的自動化工具與技術實現資源的合理控制，提高效率.此時，就需要從前后成本變化上進行更多的考慮.

事實上，測試資源控制是資源分配的一種特例，是對資源分配的動態優化過程，應始終以能夠提高故障檢修率和實現預定可靠性為目標.

表1 測試資源分配策略比較

2.3 成本模型

從軟件生命周期 TLC的角度，軟件成本E［C(T)］由測試階段成本Ct＜TTest與操作運行階段成本Ct≥TOperation兩大部分構成.不同成本模型的差異主要體現在:1)測試與運行階段所包含的子成本定義不同;2)m(t)與W(t)的不同.軟件成本在構成上，可分為傳統成本與擔保及風險成本［1，20］，如表2所示，其中，T為發布時間.

表2 軟件成本函數構成

當考慮傳統成本時，軟件成本函數E［C(T)］為

圖3給出了從測試準備(t=0)到整個生命周期結束(t=TLC)過程中所涉及到的成本構成.

圖3 軟件成本構成

圖3中C1、C3分別為測試與操作運行階段修復一個故障的成本，且C3＞C1［15，22，28，30］;C2為單位時間測試成本;C4為風險成本，即因軟件失效導致的成本.此外，軟件發布后的操作運行階段的可靠性R(x｜T)與測試階段并不相同，因此要區別對待，如

2.4 最優發布策略

軟件經過必要的測試之后，達到需求規定的目標后，可進行發布或交付給用戶.一般而言，最優發布與成本緊密相關［1，16，18-20，22-25］.Okumoto等［31］最早從成本——獲益的角度研究了軟件最優發布策略，之后的研究中最優發布問題在以下4種情況下被深入研究，如表3所示.

表3 軟件最優發布研究情況比較

其中前兩種情況較后兩種要廣泛得多，但隨著測試目標觀念的轉變以及測試資源管控水平的提高，第3種最優發布已開始被逐漸接受.這里，需要指出:

1)以上給出的均是成本的期望值 EC: E［C(T)］，Yang Bo等［36］依據概率論(大數定律)指出，即便E［C(T)］已達到最小值，很可能出現實際成本值AC＞E［C(T)］，造成成本超支.可計算概率P1(T)≡Pr{C(T)＞E［C(T)］}來進行此種不確定性的風險分析.

2)在求解過程中，對于SRGM中m(t)內的參數應該是基于實際的測試數據估計得到［16］，而并非是單純的借助解析或數值方法［22］來求得.

3)E［C(T)］可能會因涉及m(t)和TE而非常復雜，運用解析方法求解較為困難時宜采用非線性規劃軟件(AMPL)［13］以及數值求解軟件(MatheMatica，Matlab，SPSS，1stOpt)來運算.

3 關鍵技術問題討論

3.1 軟件體系結構建模

相比于忽略系統的具體結構，認為所有構件地位相當［2，3，5，9，11，13，15］，近來的測試資源/時間分配研究充分地考慮到了軟件內部的體系結構［2，8，9，14，37-38］.文獻［8］提出了考慮多因素的TE分配優化框架，兼顧到單一構件Ci對CBS可靠性R的貢獻，決定為其分配合適的測試工作量TE，用以實現預期的最小測試工作量花銷下的CBS可靠性目標Robjective.構件Ci對CBS可靠性R的貢獻取決于兩個因素:CBS系統體系結構和Ci的成本——可靠性關系.體系結構建模是對軟件內部結構特征和可能運行行為的一種描述.

1)系統級別的建模.系統級別的建模依據構件的可靠性Ri與系統結構A來進行.對于一個終止應用來說，其軟件結構可通過一個吸收的離散時間馬爾科夫鏈一步轉移概率矩陣Pn×n來表示.這些概率可通過操作剖面來獲得，操作剖面表示軟件實際的使用情況為

2)構件級別的建模.構件Ci建模表示為花銷的TE與該構件Ci的可靠性Ri之間的關系.影響構件Ci可靠性Ri的因素之一是測試中Ci消耗的TE.即便所有構件花費相同的TE，所獲得構件可靠性也不盡相同.Ci消耗的TE與所獲得的可靠性Ri之間的定量關系可通過 SRGM和 LLP(log linear process function)來表示.

總體而言，當前研究將軟件體系結構建模為各類馬爾科夫模型居多，使得可以用隨機過程的理論來處理;但馬爾科夫模型的假設較為苛刻，而真實的軟件運行具有很強的不確定性，這使得建模偏離實際較大，因而后續研究中需要考慮更多的實際情況來建模.

3.2 軟件測試過程建模方法

軟件測試過程中，結合具體的SRGM進行測試資源的管控與成本分析及最優發布，占有較大比例［2，3，6-7，9，12，15，17，39］，這其中又有部分研究明確提及到TE［2-3，18-19］.SRGM的核心是確定合適的累積的故障檢測數量函數m(t)［20，25］.由于不同研究對測試環境與過程在認識上的差異，已有大量的SRGMs被提出.本文研究中，這些SRGMs可以分為完美/不完美排錯、考慮/不考慮TE，表4中給出了部分SRGM比較.顯然，涵蓋不完美排錯與TE的SRGM能夠更加準確地描述實際的測試過程，對資源分配與控制更加精細，所建立的成本更為全面，但無疑會增加求解和分析的難度.

3.3 非線性最優化求解與仿真求解

在測試資源管控與最優發布的求解中，待求解的表達式可歸結為兩大類解決方法:1)拉格朗日乘子法(含庫恩-塔卡條件(KTC))、鞍值問題、GA、動態規劃DP等(非線性)最優化方法;2)在解析或數值解法難以處理復雜的公式化問題時，仿真［5，36，40］可被作為優選.

3.3.1 拉格朗日乘子法(LMM)及庫恩-塔卡條件(KTC)

LMM在測試資源分配模型中已被廣泛應用［3，6-7，9，11-13，15，39］，其本質是把約束條件乘以拉格朗日乘子λ后加到待求目標函數上求極值的方法，即構造拉格朗日等式為

同時，KTC則給出了求極大/小值的必要性條件.在最小化剩余故障進行測試資源分配的研究中，文獻［3］構造了拉格朗日等式來求解資源分配結果Xi為

基于KTC，式(1)存在最小值的必要條件為

一般而言，這類問題通常可歸結為:SRGM結合LMM等最優化方法求解模式:

1)若出現負解(即某Ci被分配的ei＜0)，則需要執行改進算法進行優化［3，6，13，15，17］.為防止負解出現，在所建立的資源分配優化模型中加上必要的限制條件即可.

2)若出現零解(即某Ci被分配的ei=0)，這也是不允許的.因為這表明此時Ci實際上沒有被分配測試資源，無法被測試［11］.其解決的辦法是重新設定資源分配條件，但這會增加求解的難度.

3.3.2 離散事件仿真(discrete event simulation，DES) DES是基于率函數控制的事件過程仿真方法［41］.在無窮小的時間間隔(t，t+dt)內，事件A發生的條件概率為λ(t)dt，其中λ(t)即為率函數，表示t時刻單位時間內故障發生的個數，即

4 典型案例模型研究比較

在上述分析的基礎上，表4選擇8個典型的模型從5個方面進行歸一化歸類分析，對測試資源分配與成本管控和最優發布技術問題進行了比較.

從表4可以看出，對于單一形式的軟件，研究主要側重于成本管控和最優發布，主要基于指數型SRGM所建立的簡潔的公式化形式，并以解析求解方法為主;由于構件軟件考慮到內部的體系結構特征，對測試資源的分配與管控和成本模型較為關注，所建立的公式化描述要復雜些，這使得求解方法更為繁瑣.測試資源分配與成本管控和最優發布技術問題可被建模為特定目標下的最優化問題，且正在向多目標融合方向發展.另外，由于模型中所考慮的因素也越來越豐富，傳統解析方法難以應對，相應的非線性求解方法逐漸成為優選.

總體而言，測試資源與成本管控和最優發布尚需要在以下幾個方面解決所面臨的問題.

1)測試資源的分配與管控應考慮到軟件體系結構特征，填補可靠性需求與資源平衡配置之間的差距.

2)由于實際隨機因素的不確定，未來研究中應側重考慮更多不完美排錯相關的SRGM來建立各類優化模型.

3)資源分配與控制的目的是實現成本模型受控下最優發布軟件.

4)測試資源與成本管控和最優發布問題應與可靠性的評估緊密聯系起來，實現以可靠性為核心的研究重點.

表4 研究內容解析與典型模型比較

5 結論

1)軟件測試已由過去的注重檢測與排除掉故障過渡到以不斷提高其可靠性為目標.因此，以可靠性為核心也成為了測試資源與成本管控和最優發布研究問題的關鍵.

2)執行測試資源管控為軟件管理者如何高效優化定量地分配與管理測試資源，控制開發成本，決策軟件最優發布提供了必要的決策支持.

3)如何管控有限的測試資源，使得在受限的開發測試時間內，在最小軟件成本的約束下最優發布可靠的軟件系統已成為多目標優化融合下的研究關注點.

［1］PHAM H，ZHANG Xuemei.A software cost model with warranty and risk costs［J］.IEEE Transactions on Computers，1999，48(1):71-75.

［2］JHA P C，GUPTA D，YANG Bo，et al.Optimal testing resource allocation during module testing considering cost，testing effort and reliability［J］.Computers＆Industrial Engineering，2009，57(3):1122-1130.

［3］HUANG C Y，LYU M R.Optimal testing resource allocation， and sensitivity analysis in software development［J］.IEEE Transactions on Reliability，2005，54(4):592-603.

［4］OHTERA H，YAMADA S.Optimal allocation and control problems for software-testing resources［J］.IEEE Transactions on Reliability，1990，39(2):171-176.

［5］LEUNG Y W.Dynamic resource-allocation for softwaremodule testing［J］.Journal of Systems and Software，1997，37(2):129-139.

［6］HUANG C Y，LO J H，KUO S Y，et al.Optimal allocation of testing resources for modular software systems［C］//Proceedings of 13thInternational Symposium on Software Reliability Engineering，Annapolis，Maryland:IEEE，2002:129-138.

［7］YAMADA S，ICHIMORI T，NISHIWAKI M.Optimal allocation policies fortesting-resource based on a software reliability growth model［J］.Mathematical and Computer Modelling，1995，22(10):295-301.

［8］FIONDELLA L，GOKHALE S S.Optimal allocation of testing effort considering software architecture［J］.IEEE Transactions on Reliability，2012，61(2):580-589.

［9］XIE Min，YANG Bo.Optimal testing-time allocation for modular systems［J］.International Journal of Quality＆Reliability Management，2001，18(8):854-863.

［10］BERMAN O，CUTLER M.Resource allocation during tests for optimally reliable software［J］.Computers＆Operations Research，2004，31(11):1847-1865.

［11］KAPUR P K，JHA P C，BARDHAN A K.Dynamic programming approach to testing resource allocation problem for modular software［J］.Journal of Applied Mathematics，2003，14:27-40.

［12］KHAN M G M，AHMAD N，RAFI L S.Optimal testing resource allocation for modular software based on a software reliability growth model: a dynamic programming approach［C］//International Conference on Computer Science and Software Engineering.Wuhan，Hubei:IEEE，2008:759-762.

［13］LYU M R，RANGARAJAN S，Van MOORSEL A P A. Optimalallocation of test resources for software reliability growth modeling in software development［J］. IEEE Transactions on Reliability，2002，51(2):183-192.

［14］PIETRANTUONO R，RUSSO S，TRIVEDI K S. Software reliabilityand testingtimeallocation:an architecture-based approach［J］.IEEE Transactions on Software Engineering，2010，36(3):323-337.

［15］HUANG C Y，LO J H.Optimal resource allocation for cost and reliability of modular software systems in the testing phase［J］.Journal of Systems and Software，2006，79(5):653-664.

［16］KAPUR P K，GUPTA D，GUPTA A，et al.Effect of introduction of fault and imperfect debugging on release time［J］.Journal of Applied Mathematics，2008:62-90.

［17］KUBAT P，KOCH H S.Managing test-procedures to achieve reliable software［J］.IEEE Transactions on Reliability，1983，32(3):299-303.

［18］HUANG C Y，LYU M R.Optimal release time for software systems considering cost，testing-effort，and test efficiency［J］.IEEE Transactions on Reliability，2005，54(4):583-591.

［19］HUANG C Y.Cost-reliability-optimal release policy for software reliability models incorporating improvements in testing efficiency［J］.Journal of Systems and Software，2005，77(2):139-155.

［20］ZHANG Xuemei，PHAM H.A software cost model with error removal times and risk costs［J］.International Journal of Systems Science，1998，29(4):435-442.

［21］WILLIAMS D R P.Study of the warranty cost model for software reliability with an imperfect debugging phenomenon［J］.Turk J Elec Engin，2007，15(3): 369-381.

［22］XIE Min，YANG Bo.A study of the effect of imperfect debugging on software development cost［J］.IEEE Transactions on Software Engineering，2003，29(5): 471-473.

［23］HUANG C Y，LIN C T.Analysis of software reliability modeling considering testing compression factor and failure-to-fault relationship［J］.IEEE Transactions on Computers，2010，59(2):283-288.

［24］BOLAND P J，Ní CHUíV N.Optimal times for software release when repair is imperfect［J］.Statistics＆Probability Letters，2007，77(12):1176-1184.

［25］ZHANG Xuemei，PHAM H.A software cost model with warranty cost，error removal times and risk costs［J］. IIE Transactions，1998，30(12):1135-1142.

［26］LIU C T，CHANG Y C.A reliability-constrained software release policy using a non-Gaussian Kalman filter model［J］.Probability in the Engineering and Informational Sciences，2007，21(2):301-314.

［27］WILLIAMS D R P.Optimal release policies for a software system with warranty cost and change-point phenomenon［J］. Turkish Journal of Electrical Engineering＆Computer Sciences，2013，21(1):234-245.

［28］PHAM H.A software cost model with imperfect debugging，random life cycle and penalty cost［J］.International Journal of Systems Science，1996，27(5):455-463.

［29］HOU R H，KUO S Y，CHANG Y P.Optimal release times for software systems with scheduled delivery time based ontheHGDM［J］.IEEE Transactionson Computers，1997，46(2):216-221.

［30］BOEHM B，ABTS C，CHULANI S.Software development cost estimation approaches——A survey［J］.Annals of Software Engineering，2000，10(1/4):177-205.

［31］OKUMOTO K，GOEL A L.Optimum release time for software systems based on reliability and cost criteria［J］. Journal of Systems and Software，1980，1:315-318.

［32］MORALI N，SOYER R.Optimal stopping in software testing［J］.Naval Research Logistics(NRL)，2003，50(1):88-104.

［33］KAPUR P K，PHAM H，AGGARWAL A G，et al.Two dimensional multi-release software reliability modeling and optimal release planning［J］.IEEE Transactions on Reliability，2012，61(3):758-768.

［34］JAIN M，GUPTA R.Optimal release policy of modulebased software［J］.Quality Technology and Quantitative Management，2011，8(2):147-165.

［35］LEUNG Y W.Optimum software release time with a given cost budget［J］.Journal of Systems and Software，1992，17(3):233-242.

［36］YANG Bo，HU Huajun，JIA Lixin.A study of uncertainty in software cost and its impact on optimal software release time［J］.IEEE Transactions on Software Engineering，2008，34(6):813-825.

［37］WANG Zai，TANG Ke，YAO Xin.Multi-objective approaches to optimal testing resource allocation in modular software systems［J］.IEEE Transactions on Reliability，2010，59(3):563-575.

［38］KAPUR P K，AGGARWAL A G，KAUR G.Simultaneous allocation of testing time and resources for a modular software［J］.International Journal of System Assurance Engineering and Management，2010，1(4):351-361.

［39］HOU R H，KUO S Y，CHANG Y P.Needed resources for software module test，using the hyper-geometric software reliability growth model［J］.IEEE Transactions on Reliability，1996，45(4):541-549.

［40］MASUDA Y，MIYAWAKI N，SUMITA U，et al.A statistical approach for determining release time of software system with modular structure［J］.IEEE Transactions on Reliability，1989，38(3):365-372.

［41］HUANG R，LYU M R，Kanoun K.Simulation techniques for component-based software reliability modeling with project application［C］//Proceedings of International Symposium on Information Systems and Engineering. Hong Kong:Comp Sci Res，Educ，＆Applicat Press，2001:283-289.