陳陽梅，丁曉明

(1.西南大學(xué) 計(jì)算機(jī)與信息科學(xué)學(xué)院，重慶400715;2.重慶市智能軟件與軟件工程重點(diǎn)實(shí)驗(yàn)室，重慶400715)

軟件測(cè)試是保證軟件質(zhì)量和可靠性的重要手段。在進(jìn)行軟件測(cè)試時(shí)，測(cè)試人員首先確定軟件測(cè)試需求，并根據(jù)該測(cè)試需求集設(shè)計(jì)出一套完整的測(cè)試用例，該測(cè)試用例集滿足所有的測(cè)試需求。由此，該測(cè)試用例集的數(shù)量和質(zhì)量決定軟件測(cè)試的成本和有效性。在軟件開發(fā)過程中，由于各模塊的不斷修改完善，各模塊的不斷添加和融合以及最后對(duì)整個(gè)系統(tǒng)的可靠性和有效性驗(yàn)證，需要頻繁地進(jìn)行回歸測(cè)試，在此過程中測(cè)試用例集的數(shù)量將會(huì)越來越大，其中的冗余測(cè)試用例也會(huì)越來越多。為了提高軟件測(cè)試效率，降低測(cè)試成本，這就很有必要地進(jìn)行測(cè)試用例集約簡。

1 測(cè)試用例集約簡相關(guān)概念

1993年，M.J.Harrold等人首次提出了測(cè)試用例集約簡的概念［1］。令測(cè)試用例集T與測(cè)試需求集R的二元關(guān)系S(T，R)={(t，r)∈T×R:測(cè)試用例t滿足測(cè)試需求r}，即S(T，R)表示測(cè)試用例t∈T與測(cè)試需求r∈R的滿足關(guān)系［8］。

如表1所示，測(cè)試需求集R={r1，r2，…，r6}，測(cè)試用例集 T={t1，t2，…，t7}以及集合 R與集合 T的關(guān)系S(T，R)。

由表1可知，T1={t1，t3，t7}即可滿足所有的測(cè)試需求并且T1是T的子集。在測(cè)試用例集T中存在著兩種測(cè)試用例，一種是對(duì)于測(cè)試來說必不可少的測(cè)試用例，另一種是冗余的測(cè)試用例，這些測(cè)試用例對(duì)測(cè)試本身來說并沒有執(zhí)行的價(jià)值，相反，執(zhí)行它們反而會(huì)增加測(cè)試成本。測(cè)試用例集約簡問題:令測(cè)試需求集R={r1，r2，…，rm}，并有測(cè)試用例集T={t1，t2，…，tn}滿足所有的測(cè)試需求 ri，測(cè)試用例集約簡問題就是要在測(cè)試用例集T中找到一個(gè)子集T'，即如果T'的任意真子集T'1都不能實(shí)現(xiàn)對(duì)測(cè)試需求集R的充分測(cè)試，有Req(T')=R，?T'1?T1，Re q(T'1)≠R，則測(cè)試用例集T'稱為滿足測(cè)試需求集R的最小測(cè)試用例集，其中Re q(T')，Re q(T'1)分別表示測(cè)試用例集T'和測(cè)試用例集T'1所滿足測(cè)試需求所組成的集合。

表1 測(cè)試需求與測(cè)試用例的滿足關(guān)系S(T，R)

2 求解測(cè)試用例集約簡問題的方法初探

目前已有的測(cè)試用例集約簡方法主要分為兩大類:基于組合覆蓋的測(cè)試用例集約簡技術(shù)和基于測(cè)試需求集的測(cè)試用例集約簡技術(shù)。

2.1 基于組合覆蓋的測(cè)試用例集約簡技術(shù)

(1)正交試驗(yàn)設(shè)計(jì)方法。正交試驗(yàn)設(shè)計(jì)方法實(shí)現(xiàn)了對(duì)各個(gè)參數(shù)的兩兩組合的等概率覆蓋，是一種比較成熟且有效的測(cè)試用例選擇方法［17］。該算法在測(cè)試用例選取的過程中仍會(huì)產(chǎn)生數(shù)量較大的測(cè)試用例集，無法得到最優(yōu)集。

(2)兩兩組合覆蓋。兩兩組合覆蓋的概念最早于1985年由Mandl提出。兩兩組合覆蓋測(cè)試是一種覆蓋任意單個(gè)系統(tǒng)因素、任兩個(gè)系統(tǒng)因素間的組合以及盡可能多地多個(gè)因素間組合的方法［17］。該算法能大幅度地減少測(cè)試用例的數(shù)量，從而降低測(cè)試成本。Lei和Tai于2002年利用貪心算法，提出了一種基于參數(shù)順序的漸進(jìn)擴(kuò)充的兩兩組合覆蓋測(cè)試用例生成方法并實(shí)現(xiàn)了相應(yīng)的測(cè)試用例自動(dòng)自成系統(tǒng)(Pairwise Test System)［21］，隨后有研究人員在此基礎(chǔ)上進(jìn)行改進(jìn)，提出基于IPO策略的有參數(shù)約束的兩兩組合覆蓋測(cè)試算法［21］。

2.2 基于測(cè)試需求集的測(cè)試用例集約簡技術(shù)

(1)啟發(fā)式算法?，F(xiàn)有的啟發(fā)式算法主要有貪心算法、HGS算法、GE＆GRE算法等。貪心算法(簡稱G算法)逐次從原始測(cè)試用例集T中挑選一個(gè)測(cè)試用例ti，并使得ti能最大限度地滿足測(cè)試需求集R中尚未被滿足的測(cè)試需求，然后將已滿足的測(cè)試需求從測(cè)試需求集R中刪除。重復(fù)上述過程，直到所有的測(cè)試需求都被滿足，即測(cè)試需求集R為空集。該算法最壞情況下的時(shí)間復(fù)雜度為O(mn·min(m，n))［8，9］。

HGS算法是M.J.Harrold等人提出的一種根據(jù)測(cè)試用例的重要性來選擇測(cè)試用例的啟發(fā)式算法。該算法首先將測(cè)試需求 r1，r2，…，rm分成測(cè)試需求子集合 R1，R2，…，Rd(d≤n)，Ri(i=1，2，…，d)表示所有正好可以被T中第i條測(cè)試用例滿足的測(cè)試需求。因此，HGS算法首先選出滿足R1中測(cè)試需求的測(cè)試用例，并從測(cè)試需求集R中刪除已被滿足的測(cè)試需求。重復(fù)上述過程，直到所有的測(cè)試需求子集Ri(i=2，3，…，d)全部被滿足。該算法最壞情況下的時(shí)間復(fù)雜度為O(m(m+n)d)［8］。

GE＆GRE算法是T.Y.Chen等人在貪心算法的基礎(chǔ)上提出的。GE算法在貪心算法和必不可少策略的基礎(chǔ)上，首先找出必不可少的測(cè)試用例，再使用貪心算法繼續(xù)選擇測(cè)試用例。該算法最壞情況下的時(shí)間復(fù)雜度為O(mn·min(m，n))［8，9］。GRE算法基于必不可少策略、冗余策略和貪心策略三種策略提出的。GRE算法反復(fù)地交替使用必不可少策略和冗余策略，直到這兩種策略都無法應(yīng)用，再使用貪心算法選擇測(cè)試用例滿足剩下的測(cè)試需求。該算法最壞時(shí)間復(fù)雜度為O(min(m，n)(m+n2k))［8，9］，其中k表示一個(gè)測(cè)試用例最多能滿足的測(cè)試需求的數(shù)量。

0－1整數(shù)規(guī)劃法將最優(yōu)代表集選擇問題轉(zhuǎn)化為整數(shù)線性規(guī)劃問題(Integer Linear Programming)。整數(shù)規(guī)劃方法適用于多種約束條件、適應(yīng)值函數(shù)和測(cè)試充分性準(zhǔn)則，是啟發(fā)式方法的重要補(bǔ)充。該算法時(shí)間復(fù)雜度較高，運(yùn)算開銷成指數(shù)級(jí)增長［8］。

(2)智能搜索算法?，F(xiàn)有的智能搜索算法主要有:遺傳算法(GA算法)、蟻群算法及基于蟻群算法的改進(jìn)算法、粒子群算法以及一些改進(jìn)的算法。

遺傳算法(GA算法)［10］是一種基于啟發(fā)式搜索的算法模型，該算法模型模擬達(dá)爾文的遺傳選擇和自然淘汰的生物進(jìn)化過程完成對(duì)原有測(cè)試用例集的約簡。首先，基于原有的測(cè)試用例集進(jìn)行種群編碼并在此基礎(chǔ)上隨機(jī)產(chǎn)生N個(gè)解構(gòu)成初始種群;然后，采用競爭選擇從種群中選出2個(gè)解p1，p2，并通過融合雜交算子p1，p2生成新的解C。利用測(cè)試覆蓋率、測(cè)試運(yùn)行代價(jià)等信息確保C的可行性并去除冗余。隨后用C替代種群中高于平均適應(yīng)值的個(gè)體。重復(fù)上述過程，直到產(chǎn)生t=M個(gè)不重復(fù)個(gè)體，從種群中選出具有最小適應(yīng)值的個(gè)體作為最優(yōu)解。該算法可在一定程度上得到測(cè)試用例集約簡的近似最優(yōu)解，但無法保證得到的約簡后的測(cè)試用例集為最優(yōu)的集合。

蟻群算法(Ant Colony Optimization algorithm，ACO)是一種利用群體智能，根據(jù)蟻群覓食活動(dòng)的規(guī)律進(jìn)行優(yōu)化搜索的算法模型［12，20］。該算法首先根據(jù)測(cè)試需求集 R={r1，r2，…，rm}與原有測(cè)試用例集 T={t1，t2，…，tn}構(gòu)造集合覆蓋模型，將構(gòu)造得到的測(cè)試需求集和測(cè)試用例集矩陣的每一列都賦一個(gè)相等的代價(jià)值C。然后，根據(jù)覆蓋原則，測(cè)試用例運(yùn)行代價(jià)等信息對(duì)原有測(cè)試用例集進(jìn)行約簡，求解集合覆蓋問題過程中滿足約束條件:每一個(gè)測(cè)試用例看成一個(gè)節(jié)點(diǎn)，并且每個(gè)節(jié)點(diǎn)最多能被螞蟻訪問一次;約簡后的測(cè)試用例集中的測(cè)試用例必須覆蓋矩陣中所有的行，即滿足所有的測(cè)試需求。該算法雖然能在一定程度上生成數(shù)量較少且覆蓋較多成對(duì)組合的測(cè)試用例，但該算法一般需要較長的搜索時(shí)間，同時(shí)，該算法容易出現(xiàn)停滯現(xiàn)象，當(dāng)搜索到一定程度時(shí)，所有個(gè)體發(fā)現(xiàn)的解完全一致。

基于變異因子的蟻群算法(TSR-ACA)［16］將遺傳算法和蟻群算法相結(jié)合，在基本蟻群算法的基礎(chǔ)上通過引入遺傳算法的變異因子增加搜索的隨機(jī)性、快速性和全局收斂性來克服早熟停滯的缺陷。

蟻群模擬退火混合算法(Ant-Simulated Annealing algorithm，ASA)是將模擬退火思想引入蟻群算法以此來形成新的算法［17］。模擬退火算法(Simulated Annealing algorithm，SA)以物理系統(tǒng)退火過程的相似性為基礎(chǔ)并適當(dāng)?shù)乜刂茰囟鹊南陆颠^程來實(shí)現(xiàn)模擬退火，從而求解全局優(yōu)化問題。該算法以蟻群算法為主，首先利用模擬退火算法在蟻群算法初期產(chǎn)生較優(yōu)解;然后，按照蟻群算法完成一次循環(huán)遍歷，再采用模擬退火算法在解的領(lǐng)域內(nèi)尋找另外一個(gè)解。該混合算法分為2部分，即SA階段和ACO階段:首先通過模擬退火算法求解領(lǐng)域解的方法產(chǎn)生一個(gè)初始測(cè)試用例集，隨后通過蟻群算法對(duì)初始測(cè)試用例集進(jìn)行約簡。

需求驅(qū)動(dòng)的測(cè)試用例集約簡方法［13］是由國內(nèi)的聶長海等人提出的。該方法首先對(duì)測(cè)試需求集R進(jìn)行約簡，得到約簡測(cè)試需求集R'，然后，針對(duì)約簡測(cè)試需求集R'，采用已有的測(cè)試用例集生成和約簡方法，得到測(cè)試用例約簡集。該算法能有效地減少后續(xù)測(cè)試用例生成和約簡的計(jì)算開銷，在一定程度上對(duì)現(xiàn)有的測(cè)試用例集約簡方法進(jìn)行了補(bǔ)充。

近年來測(cè)試用例集的約簡問題得到了越來越多的研究者的關(guān)注，約簡技術(shù)也得到了不斷的提高，不少研究人員也提出了自己的測(cè)試用例集約簡技術(shù)，如基于依賴分析的方法［3，4］，基于程序操作語差異(operation difference)［5］的方法，基于調(diào)用棧覆蓋(call stacks coverage)［6］的方法，基于 MC/DC(Modified Condition Decision Coverage)覆蓋［7］方法，基于程序切片的測(cè)試用例集約簡方法［6］，改進(jìn)的AETG方法和蟻群算法相結(jié)合的方法［17］等。

3 測(cè)試用例集約簡問題評(píng)價(jià)體系

為了比較不同測(cè)試用例集約簡算法的性能，分析各種約簡算法的適用范圍，對(duì)于測(cè)試用例集約簡算法通常采用以下4個(gè)屬性來評(píng)價(jià)其約簡效果［8］:

(1)充分性(Adequacy)。約簡后的測(cè)試用例集應(yīng)保持與原始用例集相同的測(cè)試充分性準(zhǔn)則。

(2)精確性(Precision)。約簡后的測(cè)試用例集能夠最大限度地剔除冗余測(cè)試用例，減小測(cè)試用例集的規(guī)模。

(3)效益(Cost-effectiveness)。用于測(cè)試用例集約簡的費(fèi)用(即運(yùn)行約簡算法得到最優(yōu)測(cè)試用例集的費(fèi)用)應(yīng)該小于使用約簡后測(cè)試用例集進(jìn)行測(cè)試所節(jié)省的費(fèi)用，即需要考慮測(cè)試用例集算法的開銷。

(4)通用性(Generality)。測(cè)試用例集約簡算法可以適用于不同類型的程序、不同的測(cè)試充分性準(zhǔn)則等。

測(cè)試用例集約簡問題在整個(gè)求解過程中，在滿足給定測(cè)試目標(biāo)的前提下，刪除測(cè)試用例集中的冗余測(cè)試用例，以盡可能少的測(cè)試用例充分滿足測(cè)試目標(biāo)，從而削減測(cè)試用例集的規(guī)模，降低運(yùn)行、維護(hù)測(cè)試用例集的開銷。與測(cè)試用例集約簡問題強(qiáng)相關(guān)的一個(gè)問題是測(cè)試用例集的錯(cuò)誤檢測(cè)能力，即如何在測(cè)試用例集的規(guī)模及錯(cuò)誤檢測(cè)能力中找到一個(gè)平衡點(diǎn)，在滿足一定測(cè)試充分性準(zhǔn)則的前提下，減小測(cè)試用例集規(guī)模并盡可能地保持測(cè)試用例集的錯(cuò)誤檢測(cè)能力，這也成為了當(dāng)前測(cè)試用例集約簡問題的重要研究課題。

G.Rothermel等人提出的APFD評(píng)價(jià)方法目前得到了廣泛的應(yīng)用，該方法能有效評(píng)估優(yōu)化測(cè)試用例集的平均錯(cuò)誤檢測(cè)效率。設(shè)測(cè)試用例集T中有n個(gè)測(cè)試用例，現(xiàn)已檢測(cè)出的錯(cuò)誤集合F中有m個(gè)錯(cuò)誤，TFi表示T檢測(cè)到錯(cuò)誤i的第一個(gè)測(cè)試用例在T中的位置，則對(duì)應(yīng)的APFD值如下所示:

由上式可知，APFD值介于0～100%之間，APFD值越大，其錯(cuò)誤檢測(cè)效率越高。在此基礎(chǔ)上，S.Elbaum等人提出了改進(jìn)的APFDc方法，用于評(píng)估當(dāng)錯(cuò)誤嚴(yán)重等級(jí)和測(cè)試用例開銷不同時(shí)，給定優(yōu)化測(cè)試用例集的平均錯(cuò)誤檢測(cè)效率［8，15］。

4 結(jié)束語

隨著軟件測(cè)試技術(shù)的不斷更新和提高，如何尋找到更為有效的測(cè)試用例集約簡算法，特別是同時(shí)考慮到測(cè)試用例約簡率及其錯(cuò)誤檢測(cè)能力的雙目標(biāo)測(cè)試用例集優(yōu)化方法，成為了當(dāng)前軟件測(cè)試領(lǐng)域中的關(guān)鍵問題和研究重點(diǎn)之一。由測(cè)試用例集約簡問題的研究表明，未來的研究工作主要將集中在以下幾個(gè)方面［8］:

(1)從測(cè)試用例集的規(guī)模及錯(cuò)誤檢測(cè)能力出發(fā)，結(jié)合測(cè)試用例優(yōu)先級(jí)技術(shù)和基于搜索的優(yōu)化方法，研究多測(cè)試充分性準(zhǔn)則的測(cè)試用例集約簡方法和多目標(biāo)的測(cè)試用例集優(yōu)化方法，實(shí)現(xiàn)全面的測(cè)試用例集優(yōu)化;

(2)繼續(xù)研究新的測(cè)試用例集約簡算法、模型，力求在合理的時(shí)間復(fù)雜度下，減小測(cè)試用例集規(guī)模;

(3)采用仿真實(shí)驗(yàn)或大型程序?qū)嶒?yàn)來分析、比較現(xiàn)有方法的性能、適用范圍，為測(cè)試人員選擇有效的測(cè)試用例集約簡方法提供建議和指導(dǎo);

(4)設(shè)計(jì)并開發(fā)有效的測(cè)試用例集約簡工具，實(shí)現(xiàn)測(cè)試用例集約簡過程的自動(dòng)化。

［1］HARROLD M J，GUPTA R，SOFFA M L.A methodology for controlling the size of a test suite［J］.ACM Transactions on Software Engineering and Methodology，1993，2(3):270-285

［2］SRIKANTH H.Requirements-based test case prioritization［C］.Student Research Forum in the 12thACM SIGSOFT International Symposium on the Foundations of Software Engineering，2004

［3］VAYSBURGB，TAHAT L，KOREL B.Dependence analysis in reduction of requirement based test suites［C］//Proceedings of the ACM International Symposium on Software Testing and Analysis，2002:107-111

［4］JOURDAN G V，RITTHIRUQNGDECH P，URAL H.Test suite reduction based on dependence analysis［C］//Proceedings of the 21stIEEE International Symposium on Computer and Information Sciences，2006:1021-1030

［5］ HARDER M，MELLEN J，ERNST M D.Improving test suites via operational abstraction［D］//Proceedings of the 25th International Conference on Software Engineering，2003:60-71

［6］MCMASTER S，MEMON A M.Call stack coverage for test suite reduction［C］//Proceedings of the 21stIEEE International Conference on Software Maintenance，2005:539-548

［7］ JONES J A，HARROLG M J.Test-suite reduction and prioritization for modified condition/decision coverage ［J］.IEEE Transactions on Software Engineering，2003，3(29):195-209

［8］章曉芳，陳林，徐寶文，等.測(cè)試用例集約簡問題研究及其進(jìn)展［J］.計(jì)算機(jī)科學(xué)與探索，2008，2(3):236-247

［9］章曉芳，徐寶文，聶長海，等.一種基于測(cè)試需求約簡的測(cè)試用例集優(yōu)化方法［J］.軟件學(xué)報(bào)，2007，18(4):821-831

［10］聶長海，徐寶文.一種最小測(cè)試用例集生成方法［J］.計(jì)算機(jī)學(xué)報(bào)，2003，26(12):1690-1695

［11］吳潔，丁曉明.基于程序切片的測(cè)試用例集約簡方法［J］.重慶交通大學(xué)學(xué)報(bào):自然科學(xué)報(bào)，2010，29(2):319-320

［12］丁革建，鄭燕妮，張璐.基于蟻群算法的測(cè)試用例集最小化研究［J］.計(jì)算機(jī)工程，2009，35(6):213-215

［13］李克文，楊志霞.基于回歸測(cè)試模型的用例集的優(yōu)化方法研究［J］.微計(jì)算機(jī)應(yīng)用，2008，29(10):7-11

［14］全君林，陸璐.基于遺傳算法測(cè)試用例集極小化研究［J］.計(jì)算機(jī)工程與應(yīng)用，2009，45(19):58-61

［15］彭園園，熊盛武.測(cè)試用例集的優(yōu)化技術(shù)分析與改進(jìn)［J］.計(jì)算機(jī)應(yīng)用技術(shù)，2009，6:77-80

［16］華麗，丁曉明.一種新的縮減測(cè)試用例集的算法［J］.西南師范大學(xué)學(xué)報(bào):自然科學(xué)版，2009，34(6):119-122

［17］楊志霞.基于回歸測(cè)試模型的用例集的優(yōu)化研究［D］.中國石油大學(xué)(華東)，2009

［18］單錦輝，姜瑛，孫萍.軟件測(cè)試研究進(jìn)展［J］.北京大學(xué)學(xué)報(bào):自然科學(xué)報(bào)，2005，41(1):134-145

［19］鄭燕妮，李志蜀，李奇.蟻群模擬退火算法在測(cè)試用例約簡中的應(yīng)用［J］.計(jì)算機(jī)工程，2009，35(2):197-199

［20］任洪麗，張偉，梁家安.基于蟻群算法的測(cè)試用例集優(yōu)化方法［J］.計(jì)算機(jī)工程與應(yīng)用，2010，46(29):58-62

［21］曾勁濤，陳建明.有參數(shù)約束的兩兩組合覆蓋測(cè)試用例生成的研究［J］.蘇州大學(xué)學(xué)報(bào):自然科學(xué)版，2008，24(1):45-49.