多準(zhǔn)則優(yōu)化的規(guī)模約束型測(cè)試用例選擇

吳先平

（復(fù)旦大學(xué)附屬上海市第五人民醫(yī)院 上海200000）

多準(zhǔn)則優(yōu)化的規(guī)模約束型測(cè)試用例選擇

吳先平

（復(fù)旦大學(xué)附屬上海市第五人民醫(yī)院 上海200000）

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

軟件回歸測(cè)試；測(cè)試用例選擇；線性規(guī)劃

軟件系統(tǒng)會(huì)不斷更新來(lái)滿足用戶新的使用需求，每次更新都需要軟件回歸測(cè)試來(lái)發(fā)現(xiàn)錯(cuò)誤。研究表明提高測(cè)試效率最好的途徑是減少測(cè)試集用例[1-6]，主要有兩種方法：回歸測(cè)試選擇（RTS）和回歸測(cè)試排序（RTP）。RTS和RTP技術(shù)的相關(guān)研究有兩個(gè)公有的結(jié)論：第一，技術(shù)的相對(duì)性能隨不同的程序而變化[1-2]，因此需要尋求一致性更好的方法。第二，某些實(shí)例的方案和假設(shè)的最優(yōu)方案之間存在著差距[3-4]，表明現(xiàn)有的準(zhǔn)則和算法不充分，而使用多準(zhǔn)則方法有助于緩解這個(gè)問(wèn)題[5]。

回歸測(cè)試技術(shù)成本效用模型的一個(gè)重要因素是時(shí)間約束，傳統(tǒng)RTP或者RTS的解決方案在時(shí)間約束下可能不是最優(yōu)方案。事先獲得一個(gè)時(shí)間約束來(lái)選出一個(gè)測(cè)試子集并排序非常有必要，即從原有的測(cè)試集中選出給定數(shù)量的測(cè)試子集，在所有這種規(guī)模的子集中其記分函數(shù)是最優(yōu)的。

1 軟件回歸測(cè)試相關(guān)工作

1.1 回歸測(cè)試用例選擇研究

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

各種RTS技術(shù)的優(yōu)劣可以用成本效益分析模型來(lái)評(píng)估。研究表明[1-16]，沒(méi)有任何一種技術(shù)能在各種情況下始終有最好的成本效益，根據(jù)產(chǎn)品的特性和測(cè)試流程的差異需選用不同的測(cè)試技術(shù)。因此迫使研究人員研究多準(zhǔn)則方法來(lái)解決這個(gè)問(wèn)題。

Yoo，Harman提出了帕累托最優(yōu)化的多準(zhǔn)則選擇方法[5]。通過(guò)遺傳算法來(lái)找到帕累托最優(yōu)方案點(diǎn)解決兩種選擇問(wèn)題：基于最小執(zhí)行時(shí)間和最大代碼覆蓋的二維問(wèn)題以及基于最小執(zhí)行時(shí)間、最大代碼覆蓋和歷史錯(cuò)誤覆蓋的三維問(wèn)題。測(cè)試人員需要根據(jù)實(shí)際情況從這些最優(yōu)方案點(diǎn)中選擇最終方案，但是在已知時(shí)間有限的情況下，帕累托方法并沒(méi)有太多優(yōu)勢(shì)。

1.2 回歸測(cè)試用例排序研究

研究者提出了多種排序技術(shù)并進(jìn)行了實(shí)驗(yàn)研究，其中大部分使用貪心算法來(lái)優(yōu)化錯(cuò)誤相關(guān)的準(zhǔn)則如代碼覆蓋，對(duì)測(cè)試用例進(jìn)行重新排序。為了提高代碼覆蓋技術(shù)的性能，研究人員引入了其他參數(shù)如變化，錯(cuò)誤索引[3]及相關(guān)片區(qū)或者增加反饋機(jī)制，研究表明各技術(shù)性能存在顯著差異，且在不同的程序中也不一致。

傳統(tǒng)貪心算法簡(jiǎn)化了RTP問(wèn)題的搜索，但是不能確保最優(yōu)解決方案。Li等研究了基于搜索的非貪心算法，不評(píng)估對(duì)錯(cuò)誤檢測(cè)率的影響而關(guān)注最大化覆蓋率，提出了3種技術(shù)（2優(yōu)貪心算法，遺傳算法，爬山法）并和兩個(gè)傳統(tǒng)的基于覆蓋的技術(shù)（貪心和附加貪心算法）進(jìn)行了對(duì)比，但是結(jié)果表明貪心算法是非常有效的。

2 新方法提出

2.1 問(wèn)題描述

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

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

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

為了解決SRTS問(wèn)題，我們提出了多準(zhǔn)則非貪心優(yōu)化方法。以下從優(yōu)化準(zhǔn)則和優(yōu)化算法兩個(gè)方面進(jìn)行描述。

2.2 優(yōu)化準(zhǔn)則

通常我們定義記分函數(shù)F為檢測(cè)到的錯(cuò)誤數(shù)目，由于錯(cuò)誤數(shù)目是未知的，因此還需要建立其他的得分函數(shù)，并與錯(cuò)誤數(shù)目具有某種統(tǒng)計(jì)關(guān)系。給定一個(gè)測(cè)試集S?ZN，定義測(cè)試集S對(duì)程序單元集合A測(cè)試能力為一個(gè)正的標(biāo)量，記為D（S），并假定：

1）D（S）能相對(duì)精確地表示測(cè)試集S對(duì)程序集合A的錯(cuò)誤檢測(cè)能力；

2）D（S）的值可以得到，并且與之聯(lián)系的搜索問(wèn)題可以用數(shù)學(xué)表達(dá)式表述.

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

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

wm是一系列權(quán)重，強(qiáng)調(diào)各個(gè)程序單元在軟件測(cè)試中的重要性。例如本文中使用的程序單元檢測(cè)出錯(cuò)誤的可能性、或者該程序單元在軟件功能中的作用。

Dmin函數(shù)（式3）最大化所有程序單元上的最小代碼覆蓋率，與貪婪算法中反饋機(jī)理作用類似，使代碼覆蓋率在系統(tǒng)程序單元中的分布更均勻，從而提高了測(cè)試集的錯(cuò)誤檢測(cè)能力。最大化最小覆蓋率易生成多種優(yōu)化結(jié)果，為進(jìn)一步縮小解決方案的范圍，我們?cè)黾恿说诙€(gè)函數(shù)Dsum，并且與第一個(gè)D函數(shù)弱相關(guān)，這樣可以實(shí)現(xiàn)優(yōu)化問(wèn)題的0-1IP編程設(shè)計(jì)，通過(guò)運(yùn)用權(quán)重wm可以為各個(gè)程序單元設(shè)置優(yōu)先級(jí)。

假設(shè)只關(guān)注于選取L個(gè)測(cè)試用例最大化Dsum，其中wm取1。結(jié)果為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的增加僅帶來(lái)D值少量的變化。而L=4時(shí)，相應(yīng)的d1（{1，3，5，7}）=15+2+5+30=52，d2（{1，3，5，7}）=101，以及d3（{1，3，5，7}）=2420。此時(shí)Dmin（{1，3，5，7}）=min（52，101，2420）=52。如果將用例4取代5，得到Dsum（{1，3，5，7}）=2164和Dmin（{1，3，5，7}）=129。此時(shí)Dmin從52變到129（將近兩倍），代價(jià)是Dsum從2420減為2164。Dmin增長(zhǎng)兩倍意味著可以保證每單個(gè)程序單元至少有相對(duì)于以前兩倍的代碼覆蓋率。略微下降表明某些程序單元被覆蓋少了，但那些單元卻可被其他測(cè)試用例覆蓋。例如，用例5覆蓋單元3最多，同時(shí)單元3也被用例1，3，7覆蓋。所以用例5發(fā)現(xiàn)的錯(cuò)誤也極可能被其他用例發(fā)現(xiàn)。

上述案例表明采用單一D函數(shù)，相當(dāng)一大部分的測(cè)試用例增加僅能對(duì)D值增長(zhǎng)產(chǎn)生微弱的貢獻(xiàn)。采用多個(gè)D函數(shù)在數(shù)學(xué)上有兩大好處：第一，有時(shí)候很多優(yōu)化方案會(huì)得到相同D值，另一個(gè)選擇準(zhǔn)則有助于決定最終方案。第二，優(yōu)化單一D函數(shù)可能出現(xiàn)上限，此時(shí)另一個(gè)D函數(shù)可有助于超越D值上限。為了同時(shí)優(yōu)化兩個(gè)D函數(shù)，我們需要相應(yīng)的優(yōu)化算法來(lái)支持。

2.3 優(yōu)化算法

優(yōu)化多準(zhǔn)則的算法至少具有以下性質(zhì)：

2）可用于搜索一個(gè)給定規(guī)模D約束的優(yōu)化問(wèn)題；

3）能同時(shí)處理兩個(gè)目標(biāo)函數(shù)。

傳統(tǒng)貪婪算法已經(jīng)用于解決RTP問(wèn)題。優(yōu)點(diǎn)是規(guī)?？勺?，滿足第一個(gè)性質(zhì)，但是貪婪算法對(duì)規(guī)模約束不敏感，因此不能用于優(yōu)化特定規(guī)模的問(wèn)題。此外，貪婪算法不具有回溯選擇的功能，所以一個(gè)差的選擇可能進(jìn)入最終的方案。因此文中提出了一個(gè)多準(zhǔn)則非貪婪選擇算法，在兩個(gè)特定的目標(biāo)函數(shù)要求下，選擇規(guī)模約束的測(cè)試用例集，然后提出了一個(gè)貪婪算法對(duì)規(guī)模測(cè)試用例進(jìn)行排序。

3 實(shí)驗(yàn)設(shè)計(jì)

3.1 非獨(dú)立變量及參數(shù)設(shè)置

在問(wèn)題1中，非獨(dú)立變量是錯(cuò)誤檢出率（FDR），即測(cè)試集檢出錯(cuò)誤的百分比。在問(wèn)題2中，我們關(guān)注被發(fā)現(xiàn)的錯(cuò)誤數(shù)和錯(cuò)誤檢出率，相應(yīng)的由FDR和平均錯(cuò)誤檢出率（APFD）來(lái)體現(xiàn)[3]。

對(duì)于權(quán)重wm，令無(wú)修改的類權(quán)重為0，比平均修改水平高的類為1，而低于平均修改水平的類為0.5。

多次實(shí)驗(yàn)表明，λ1的步長(zhǎng)應(yīng)足夠小以充分覆蓋問(wèn)題空間，l值的范圍對(duì)LP問(wèn)題的求解非常重要，范圍過(guò)窄則可能求解點(diǎn)遠(yuǎn)離Pareto前沿，范圍過(guò)寬又會(huì)導(dǎo)致運(yùn)行時(shí)間急劇增加。我們定義λ1以步長(zhǎng)0.01在區(qū)域內(nèi)變化λ2=1-λ1，。搜索算法在l∈[10，100]范圍內(nèi)運(yùn)行。另外對(duì)程序單元進(jìn)行了3個(gè)層次的劃分以便取得最好的結(jié)果。

3.2 用于對(duì)比的其他技術(shù)

3.2.1 基于覆蓋的排序技術(shù)

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

3.2.2 基于貝葉斯（BN）網(wǎng)絡(luò)的技術(shù)

采用多準(zhǔn)則的基于貝葉斯網(wǎng)絡(luò)的方法（BN-based）是較復(fù)雜RTP技術(shù)。文中比較了兩個(gè)基于貝葉斯網(wǎng)絡(luò)的技術(shù)：BN和BNA。BNA是采用了反饋機(jī)理的BN。

3.2.3 時(shí)間可知排序技術(shù)

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

4 實(shí)驗(yàn)配置

文中實(shí)驗(yàn)運(yùn)行SIR的5個(gè)開放Java源碼：Ant，Nanoxml（Nano），Galileo，Xml-security（Xml），和Jmeter，這些代碼已廣泛地應(yīng)用于回歸測(cè)試的經(jīng)驗(yàn)研究。

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

方法級(jí)別的覆蓋數(shù)據(jù)沿用Do等的做法[4]，即每個(gè)方法所產(chǎn)生的至少一個(gè)修改塊，被標(biāo)記為被覆蓋，否則被標(biāo)記為不被覆蓋，該數(shù)據(jù)通過(guò)字節(jié)代碼分析工具Sandmark來(lái)獲得。

我們對(duì)每一個(gè)程序版本建立了規(guī)模隨機(jī)（至少15）的100個(gè)變異群，并基于全局變異矩陣為每一個(gè)變異群建立個(gè)體錯(cuò)誤矩陣。運(yùn)行每一個(gè)錯(cuò)誤矩陣100次來(lái)檢測(cè)每一個(gè)涉及的技術(shù)。

5 實(shí)驗(yàn)結(jié)果

5.1 規(guī)模約束選擇

針對(duì)問(wèn)題1我們對(duì)比了IP方法及其他方法的錯(cuò)誤檢測(cè)率。在Ant程序中所有技術(shù)的結(jié)果相近。在Nano程序中，WTA技術(shù)在L=50及25的時(shí)間約束下表現(xiàn)最好。Galileo程序中，IP技術(shù)在兩種規(guī)模約束下都明顯好于其他技術(shù)。Jmeter程序中，IP在L=25時(shí)稍稍好于其他技術(shù)。在Xml程序中，IP和WTA技術(shù)比其他技術(shù)要好?？傮w來(lái)說(shuō)，IP技術(shù)在大多數(shù)程序中的表現(xiàn)最好。

5.2 用例選擇及排序

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

圖1 Ant程序各技術(shù)錯(cuò)誤檢測(cè)率

更有趣的發(fā)現(xiàn)是除了Nano程序，其他程序中當(dāng)時(shí)，IP（25）+Gmin比IP（50）+Gmin的方法明顯要優(yōu)，而在Nano程序中，這兩種方法一樣。這種規(guī)律同樣適用于WTA方法。這個(gè)結(jié)果表明，IP技術(shù)及WTA技術(shù)成功的將測(cè)試用例的規(guī)?？s小在要求的范圍之內(nèi)。WTA選擇及排序同時(shí)進(jìn)行，而IP+ Gmin技術(shù)先選擇再排序。

圖2 Nano程序各技術(shù)錯(cuò)誤檢測(cè)率

圖3 Galileo程序各技術(shù)錯(cuò)誤檢測(cè)率

圖4 Jmeter程序各技術(shù)錯(cuò)誤檢測(cè)率

圖5 Xml程序各技術(shù)錯(cuò)誤檢測(cè)率

5.3 實(shí)驗(yàn)局限性

實(shí)驗(yàn)中的非獨(dú)立變量是簡(jiǎn)單源于直覺(jué)的，另外本文專注于解決LP問(wèn)題的一致性方法，執(zhí)行時(shí)間不是我們主要討論的問(wèn)題，因此僅以IP技術(shù)為例對(duì)執(zhí)行時(shí)間進(jìn)行了粗略的考量。實(shí)驗(yàn)中的技術(shù)基于不同平臺(tái)，由不同水平的專家所開發(fā)，將來(lái)的研究可在相同的平臺(tái)和專家水平上進(jìn)行運(yùn)行時(shí)間的比較。

6 結(jié)束語(yǔ)

為了優(yōu)化軟件回歸測(cè)試的測(cè)試集，提高測(cè)試的有效性，文中構(gòu)建了一個(gè)線性規(guī)劃（IP）問(wèn)題，采用最大-最小準(zhǔn)則和覆蓋數(shù)準(zhǔn)則，針對(duì)IP問(wèn)題提出了一種近似和次優(yōu)的數(shù)學(xué)解決方案，然后提出了一個(gè)投票機(jī)制，來(lái)選出最終的解決方案，最后提出了一個(gè)貪心算法來(lái)對(duì)選出的測(cè)試用例子集進(jìn)行排序。

通過(guò)采用SIR程序庫(kù)中的5個(gè)JAVA程序?qū)σ陨?種技術(shù)進(jìn)行了實(shí)驗(yàn)評(píng)價(jià)并和現(xiàn)有技術(shù)進(jìn)行了比較。實(shí)驗(yàn)表明，文中提出的方法在所研究的40%的案例中的性能最高，在另外40%的案例中表現(xiàn)較好，而在剩下的20%的案例中表現(xiàn)一般。更重要的是文中提出的方法比現(xiàn)有其他方法表現(xiàn)了更好的一致性。

基于文中提出的方法將來(lái)可以采用其他多準(zhǔn)則對(duì)規(guī)模約束問(wèn)題進(jìn)行更深入的研究，而且多準(zhǔn)則方法可以用于其他算法：如貪心算法可以始于單個(gè)算法，遇到限制的情況下再引入更多的算法，或者選擇新用例的時(shí)候在不同準(zhǔn)則中進(jìn)行切換。當(dāng)我們理解了不同技術(shù)性能差異的原因之后，研究人員可以針對(duì)某個(gè)特定的環(huán)境創(chuàng)造自己的算法來(lái)選擇最適合的準(zhǔn)則。

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

[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 稿件編號(hào)：201603027

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