多準則優化的規模約束型測試用例選擇

吳先平

（復旦大學附屬上海市第五人民醫院 上海200000）

多準則優化的規模約束型測試用例選擇

吳先平

（復旦大學附屬上海市第五人民醫院 上海200000）

軟件修改之后可以重新測試之前的所有用例來發現錯誤，但是這種方法耗費巨大，為了減少測試用例數量，優化測試工作，本文提出了一種全新的用例選擇方法，即從現有的測試用例集中挑選一定數量的用例并進行重新排序。該方法塑造了一個線性規劃問題，采用兩個代碼覆蓋準則并放寬約束來發現接近最優方案的用例，然后對這些用例使用投票機制獲得最優用例集，最后采用最大化最小覆蓋的貪心算法進行迭代排序。實驗表明在大部分案例中，新方法的性能相比現有方法有顯著的改進，而且一致性更好。

軟件回歸測試；測試用例選擇；線性規劃

軟件系統會不斷更新來滿足用戶新的使用需求，每次更新都需要軟件回歸測試來發現錯誤。研究表明提高測試效率最好的途徑是減少測試集用例[1-6]，主要有兩種方法：回歸測試選擇（RTS）和回歸測試排序（RTP）。RTS和RTP技術的相關研究有兩個公有的結論：第一，技術的相對性能隨不同的程序而變化[1-2]，因此需要尋求一致性更好的方法。第二，某些實例的方案和假設的最優方案之間存在著差距[3-4]，表明現有的準則和算法不充分，而使用多準則方法有助于緩解這個問題[5]。

回歸測試技術成本效用模型的一個重要因素是時間約束，傳統RTP或者RTS的解決方案在時間約束下可能不是最優方案。事先獲得一個時間約束來選出一個測試子集并排序非常有必要，即從原有的測試集中選出給定數量的測試子集，在所有這種規模的子集中其記分函數是最優的。

1 軟件回歸測試相關工作

1.1 回歸測試用例選擇研究

目前的回歸測試選擇技術分為3種：最小化、安全化和基于覆蓋的選擇。最小化技術選擇最小測試用例集來滿足被修改代碼部分的最小覆蓋準則。如1977年Fischer使用zeroone整數規劃找到測試用例的最小子集來覆蓋軟件系統的每一個元素[8]。最小化技術有效的減少了測試集規模，但是可能漏掉某些可以發現錯誤的用例[9]。為了盡量消除這種失誤，Rothermel，Harrold提出了安全RTS技術[10]，使測試集的規模邊際遞減，同時保證了較高的精確性[2-11]?；诟采w的RTS技術選擇滿足覆蓋率要求的測試用例[12-14]，例如數據流覆蓋技術[12]選擇所有因為代碼修改導致數據交互的用例。這類技術的成本通常處于最小化和安全化技術之間，但是都不能直接控制測試用例的數量。

各種RTS技術的優劣可以用成本效益分析模型來評估。研究表明[1-16]，沒有任何一種技術能在各種情況下始終有最好的成本效益，根據產品的特性和測試流程的差異需選用不同的測試技術。因此迫使研究人員研究多準則方法來解決這個問題。

Yoo，Harman提出了帕累托最優化的多準則選擇方法[5]。通過遺傳算法來找到帕累托最優方案點解決兩種選擇問題：基于最小執行時間和最大代碼覆蓋的二維問題以及基于最小執行時間、最大代碼覆蓋和歷史錯誤覆蓋的三維問題。測試人員需要根據實際情況從這些最優方案點中選擇最終方案，但是在已知時間有限的情況下，帕累托方法并沒有太多優勢。

1.2 回歸測試用例排序研究

研究者提出了多種排序技術并進行了實驗研究，其中大部分使用貪心算法來優化錯誤相關的準則如代碼覆蓋，對測試用例進行重新排序。為了提高代碼覆蓋技術的性能，研究人員引入了其他參數如變化，錯誤索引[3]及相關片區或者增加反饋機制，研究表明各技術性能存在顯著差異，且在不同的程序中也不一致。

傳統貪心算法簡化了RTP問題的搜索，但是不能確保最優解決方案。Li等研究了基于搜索的非貪心算法，不評估對錯誤檢測率的影響而關注最大化覆蓋率，提出了3種技術（2優貪心算法，遺傳算法，爬山法）并和兩個傳統的基于覆蓋的技術（貪心和附加貪心算法）進行了對比，但是結果表明貪心算法是非常有效的。

2 新方法提出

2.1 問題描述

已知：一個程序Pv，它的測試用例集合T={T1，…，Tn}；Pv+1表示新版本程序，由M個元素構成，A={a1，…，aM}。定義數字L≤N，函數Fv+1是從一個測試用例集合得到一個正的分級數量，問題：

尋找S?T，使其滿足|S|=L，且?S′?L，|S′|=L?FV+1（S′）≤Fv+1（S）。

定義ZM={1，…，M}表示從1到M的整數集合，ZM={1，…，N}表示從1到N的整數集合。我們使用索引來簡化軟件元素和測試用例。（例如：m∈ZM指第m個軟件元素，并且n∈ZN指第m個測試用例）同時，在將集合作為參數時，我們使用元素的索引來替代集合。

為了解決SRTS問題，我們提出了多準則非貪心優化方法。以下從優化準則和優化算法兩個方面進行描述。

2.2 優化準則

通常我們定義記分函數F為檢測到的錯誤數目，由于錯誤數目是未知的，因此還需要建立其他的得分函數，并與錯誤數目具有某種統計關系。給定一個測試集S?ZN，定義測試集S對程序單元集合A測試能力為一個正的標量，記為D（S），并假定：

1）D（S）能相對精確地表示測試集S對程序集合A的錯誤檢測能力；

2）D（S）的值可以得到，并且與之聯系的搜索問題可以用數學表達式表述.

我們將它稱為D函數，一個典型的D函數就是S中測試用例的代碼覆蓋率。令dm（S）表示測試集S對程序單元集合A中第m個單元的錯誤測試能力。假設

其中，δm（sn）表示第n個測試用例sn∈S對第m個程序單元αm∈A的錯誤測試能力。如前所述，在本文中定義δm（sn）為sn∈S對αm∈A的代碼覆蓋率，那么測試集（S）對每個程序單元（m）的代碼覆蓋率是每個測試用例（n）對此程序單元的代碼覆蓋率（δm（sn））的總和。我們定義兩個D函數：

wm是一系列權重，強調各個程序單元在軟件測試中的重要性。例如本文中使用的程序單元檢測出錯誤的可能性、或者該程序單元在軟件功能中的作用。

Dmin函數（式3）最大化所有程序單元上的最小代碼覆蓋率，與貪婪算法中反饋機理作用類似，使代碼覆蓋率在系統程序單元中的分布更均勻，從而提高了測試集的錯誤檢測能力。最大化最小覆蓋率易生成多種優化結果，為進一步縮小解決方案的范圍，我們增加了第二個函數Dsum，并且與第一個D函數弱相關，這樣可以實現優化問題的0-1IP編程設計，通過運用權重wm可以為各個程序單元設置優先級。

假設只關注于選取L個測試用例最大化Dsum，其中wm取1。結果為Dsum（{1，3，5，7}）=721+716+596+540=2573（L=4）；Dsum（{1，3，5，7}）=2573+187=2760（L=5）；Dsum（{1，3，4，5，6，7}）= 2760+160=2920（L=6）。

可以看到L的增加僅帶來D值少量的變化。而L=4時，相應的d1（{1，3，5，7}）=15+2+5+30=52，d2（{1，3，5，7}）=101，以及d3（{1，3，5，7}）=2420。此時Dmin（{1，3，5，7}）=min（52，101，2420）=52。如果將用例4取代5，得到Dsum（{1，3，5，7}）=2164和Dmin（{1，3，5，7}）=129。此時Dmin從52變到129（將近兩倍），代價是Dsum從2420減為2164。Dmin增長兩倍意味著可以保證每單個程序單元至少有相對于以前兩倍的代碼覆蓋率。略微下降表明某些程序單元被覆蓋少了，但那些單元卻可被其他測試用例覆蓋。例如，用例5覆蓋單元3最多，同時單元3也被用例1，3，7覆蓋。所以用例5發現的錯誤也極可能被其他用例發現。

上述案例表明采用單一D函數，相當一大部分的測試用例增加僅能對D值增長產生微弱的貢獻。采用多個D函數在數學上有兩大好處：第一，有時候很多優化方案會得到相同D值，另一個選擇準則有助于決定最終方案。第二，優化單一D函數可能出現上限，此時另一個D函數可有助于超越D值上限。為了同時優化兩個D函數，我們需要相應的優化算法來支持。

2.3 優化算法

優化多準則的算法至少具有以下性質：

2）可用于搜索一個給定規模D約束的優化問題；

3）能同時處理兩個目標函數。

傳統貪婪算法已經用于解決RTP問題。優點是規模可變，滿足第一個性質，但是貪婪算法對規模約束不敏感，因此不能用于優化特定規模的問題。此外，貪婪算法不具有回溯選擇的功能，所以一個差的選擇可能進入最終的方案。因此文中提出了一個多準則非貪婪選擇算法，在兩個特定的目標函數要求下，選擇規模約束的測試用例集，然后提出了一個貪婪算法對規模測試用例進行排序。

3 實驗設計

3.1 非獨立變量及參數設置

在問題1中，非獨立變量是錯誤檢出率（FDR），即測試集檢出錯誤的百分比。在問題2中，我們關注被發現的錯誤數和錯誤檢出率，相應的由FDR和平均錯誤檢出率（APFD）來體現[3]。

對于權重wm，令無修改的類權重為0，比平均修改水平高的類為1，而低于平均修改水平的類為0.5。

多次實驗表明，λ1的步長應足夠小以充分覆蓋問題空間，l值的范圍對LP問題的求解非常重要，范圍過窄則可能求解點遠離Pareto前沿，范圍過寬又會導致運行時間急劇增加。我們定義λ1以步長0.01在區域內變化λ2=1-λ1，。搜索算法在l∈[10，100]范圍內運行。另外對程序單元進行了3個層次的劃分以便取得最好的結果。

3.2 用于對比的其他技術

3.2.1 基于覆蓋的排序技術

RTP算法作為SRTS問題的一個解決方案，基于覆蓋利用簡單的準則和算法，成本效益明顯。我們采用了兩個基于覆蓋的技術用于方法層面的比較，即全覆蓋（MTC）和額外覆蓋（MAC）[4，18]。

3.2.2 基于貝葉斯（BN）網絡的技術

采用多準則的基于貝葉斯網絡的方法（BN-based）是較復雜RTP技術。文中比較了兩個基于貝葉斯網絡的技術：BN和BNA。BNA是采用了反饋機理的BN。

3.2.3 時間可知排序技術

已知時間的排序技術可以簡化為STRT問題。如Walcott等的時間明確方法（WTA），該方法基于遺傳算法，使用單一覆蓋準則并考慮覆蓋率之間的重疊。我們對WTA技術稍作修改以采用本文中的覆蓋數據，輸入參數基于黑箱層面，遵循其建議設置參數為：30個體，50代，70%的交叉和10%的變異，并定義第一個用例的執行時間為一個單位。時間已知問題規定了用例數的上界而不是一個確切的數值，在對比實驗中的用例數總是低于期望值l-2，因此我們運行l+2數值來解決上述問題。

4 實驗配置

文中實驗運行SIR的5個開放Java源碼：Ant，Nanoxml（Nano），Galileo，Xml-security（Xml），和Jmeter，這些代碼已廣泛地應用于回歸測試的經驗研究。

Andrews以及Do和Rothermel對Java程序測試集排序問題的變異錯誤進行了研究，我們采用相同的變異錯誤集，并使用SIR中可用的追蹤代碼（由Sofa工具生成）作為塊級別的覆蓋數據；每個類中被覆蓋的塊百分比作為類級別的覆蓋數據。

方法級別的覆蓋數據沿用Do等的做法[4]，即每個方法所產生的至少一個修改塊，被標記為被覆蓋，否則被標記為不被覆蓋，該數據通過字節代碼分析工具Sandmark來獲得。

我們對每一個程序版本建立了規模隨機（至少15）的100個變異群，并基于全局變異矩陣為每一個變異群建立個體錯誤矩陣。運行每一個錯誤矩陣100次來檢測每一個涉及的技術。

5 實驗結果

5.1 規模約束選擇

針對問題1我們對比了IP方法及其他方法的錯誤檢測率。在Ant程序中所有技術的結果相近。在Nano程序中，WTA技術在L=50及25的時間約束下表現最好。Galileo程序中，IP技術在兩種規模約束下都明顯好于其他技術。Jmeter程序中，IP在L=25時稍稍好于其他技術。在Xml程序中，IP和WTA技術比其他技術要好。總體來說，IP技術在大多數程序中的表現最好。

5.2 用例選擇及排序

該問題主要探究RTS結合RTP技術是否比單獨的RTP技術更好。圖1至圖5表明了不同測試用例中各技術對錯誤的探測率，我們共研究了5種技術（IP+Gmin，Gmin，BNA，MAC及WTA）并觀察到了2個現象，一是IP+Gmin技術的曲線在一半的案例中都是處于Gmin曲線之上，對于其他案例的結果很接近。因此我們可以說IP+Gmin的技術比單獨的Gmin技術要好。

圖1 Ant程序各技術錯誤檢測率

更有趣的發現是除了Nano程序，其他程序中當時，IP（25）+Gmin比IP（50）+Gmin的方法明顯要優，而在Nano程序中，這兩種方法一樣。這種規律同樣適用于WTA方法。這個結果表明，IP技術及WTA技術成功的將測試用例的規?？s小在要求的范圍之內。WTA選擇及排序同時進行，而IP+ Gmin技術先選擇再排序。

圖2 Nano程序各技術錯誤檢測率

圖3 Galileo程序各技術錯誤檢測率

圖4 Jmeter程序各技術錯誤檢測率

圖5 Xml程序各技術錯誤檢測率

5.3 實驗局限性

實驗中的非獨立變量是簡單源于直覺的，另外本文專注于解決LP問題的一致性方法，執行時間不是我們主要討論的問題，因此僅以IP技術為例對執行時間進行了粗略的考量。實驗中的技術基于不同平臺，由不同水平的專家所開發，將來的研究可在相同的平臺和專家水平上進行運行時間的比較。

6 結束語

為了優化軟件回歸測試的測試集，提高測試的有效性，文中構建了一個線性規劃（IP）問題，采用最大-最小準則和覆蓋數準則，針對IP問題提出了一種近似和次優的數學解決方案，然后提出了一個投票機制，來選出最終的解決方案，最后提出了一個貪心算法來對選出的測試用例子集進行排序。

通過采用SIR程序庫中的5個JAVA程序對以上3種技術進行了實驗評價并和現有技術進行了比較。實驗表明，文中提出的方法在所研究的40%的案例中的性能最高，在另外40%的案例中表現較好，而在剩下的20%的案例中表現一般。更重要的是文中提出的方法比現有其他方法表現了更好的一致性。

基于文中提出的方法將來可以采用其他多準則對規模約束問題進行更深入的研究，而且多準則方法可以用于其他算法：如貪心算法可以始于單個算法，遇到限制的情況下再引入更多的算法，或者選擇新用例的時候在不同準則中進行切換。當我們理解了不同技術性能差異的原因之后，研究人員可以針對某個特定的環境創造自己的算法來選擇最適合的準則。

除此之外，我們還可以在更廣泛的規模約束水平以及其他控制技術，其他的程序或者考慮到了早期的錯誤檢測率及未完成的測試等綜合情況中進行更深入的研究。我們研究了IP+Gmin的技術，還可以進一步研究IP+其他RTP技術的組合性能。我們沒有考慮到單個測試用例運行的執行時間，也沒有考慮到執行提出的方法的時間需求，將來可以就這些未考慮的因素進行更廣泛的研究。

[1]H.Do and G.Rothermel.An Empirical Study of Regression Testing Techniques Incorporating Context and Lifetime Factors and Improved Cost-Benefit Models[C]//Proc.Int’l Symp. Foundations of Software Eng.，2006：141-151.

[2]T.L.Graves，M.J.Harrold，J.-M.Kim，et al.An Empirical Study of Regression Test Selection Techniques[C]//ACM Trans.Software Eng.and Methodology，2001，10（2）：184-208.

[3]S.Elbaum，A.G.Malishevsky，G.Rothermel.Test Case Prioritization:A Family of Empirical Studies[C]//IEEE Trans. Software Eng.，2002，28（2）：159-182.

[4]H.Do，G.Rothermel，A.Kinneer.Prioritizing JUnit Test Cases:An Empirical Assessment and Cost-Benefits Analysis [C]//Empirical Software Eng.:An Int’l J.，2006，11（1）：33-70.

[5]S.Yoo，M.Harman.Pareto Efficient Multi-Objective Test Case Selection[C]//Proc.Int’l Symp.Software Testing and Analysis，2007：140-150.

[6]H.Do，S.Mirarab，L.Tahvildari，et al.An Empirical Study of the Effect of Time Constraints on the Cost-Benefits of Regression Testing[C]//Proc.ACM SIGSOFT Int’l Symp.Foundations of Software Eng.，2008：71-82.

[7]H.Do，S.Elbaum，G.Rothermel.Supporting Controlled Ex-perimentation with Testing Techniques:An Infrastructure and Its Potential Impact[C]//Empirical Software Eng.:An Int’l J.，2005，10（4）：405-435.

[8]K.Fischer.A Test Case Selection Method for the Validation of Software Maintenance Modifications[C]//Proc.Int’l Computer Software and Applications Conf.，1977：421-426.

[9]T.L.Graves，M.J.Harrold，J.-M.Kim，et al.An Empirical Study of Regression Test Selection Techniques[C]//ACM Trans.Software Eng.and Methodology，2001，10（2）：184-208.

[10]G.Rothermel，M.J.Harrold.A Safe，Efficient Regression Test Selection Technique[C]//ACM Trans.Software Eng.and Methodology，1997，6（2）：173-210.

[11]G.Rothermel，M.J.Harrold.Analyzing Regression Test Selection Techniques[C]//IEEE Trans.Software Eng.，1996，22（8）：529-551.

[12]M.Harrold，M.Soffa.An Incremental Approach to Unit Testing during Maintenance[C]//Proc.Int’l Conf.Software Maintenance，1988：362-367.

[13]L.White，H.Leung.A Firewall Concept for Both Control-Flow and Data-Flow in Regression Integration Testing[C]// Proc.Int’l Conf.Software Maintenance，1992：262-271.

[14]D.Binkley.Semantics Guided Regression Test Cost Reduction[C]//IEEE Trans.Software Eng.，1997，23（8）：498-516.

[15]H.Leung，L.White.A Cost Model to Compare Regression Test Strategies[C]//Proc.Int’l Conf.Software Maintenance，1991：201-208.

[16]A.G.Malishevsky，G.Rothermel，S.Elbaum.Modeling the Cost-Benefits Tradeoffs for Regression Testing Techniques[C] //Proc.Int’l Conf.Software Maintenance，2002：204-213.

Multiple criteria optimization for scale constrained test case selection

WU Xian-ping
（The Fifth People’s Hospital of Shanghai Fudan University，Shanghai 200000，China）

One traditional approach to detect errors of software after modification is to rerun all the previous test cases，which is too costly.To optimize test and reduce test cost，we proposed a new approach which is to select a predefined quantity of test cases from existed cases and re-order them.This approach forms an IP problem，uses two coverage-based criteria and constraint relaxation to find cases close to best solution，then a voting mechanism is used to select the subset cases and then are prioritized with Maximize minimum coverage based Greedy algorithm in regression.The proposed approach was evaluated against other existing ones with experiment and the result showed that the new approach performed better in most cases with higher consistency.

software regression test；pareto optimality；test case selection；linear programming

TN99

A

1674－6236（2016）24-0049-04

2016-03-03 稿件編號：201603027

吳先平（1979—），女，湖北恩施人，碩士。研究方向：信息管理。