測試用例集約簡方法綜述

陳陽梅，丁曉明

(1.西南大學 計算機與信息科學學院，重慶400715;2.重慶市智能軟件與軟件工程重點實驗室，重慶400715)

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

1 測試用例集約簡相關概念

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

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

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

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

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

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

2.1 基于組合覆蓋的測試用例集約簡技術

(1)正交試驗設計方法。正交試驗設計方法實現了對各個參數的兩兩組合的等概率覆蓋，是一種比較成熟且有效的測試用例選擇方法［17］。該算法在測試用例選取的過程中仍會產生數量較大的測試用例集，無法得到最優集。

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

2.2 基于測試需求集的測試用例集約簡技術

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

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

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

0－1整數規劃法將最優代表集選擇問題轉化為整數線性規劃問題(Integer Linear Programming)。整數規劃方法適用于多種約束條件、適應值函數和測試充分性準則，是啟發式方法的重要補充。該算法時間復雜度較高，運算開銷成指數級增長［8］。

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

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

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

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

蟻群模擬退火混合算法(Ant-Simulated Annealing algorithm，ASA)是將模擬退火思想引入蟻群算法以此來形成新的算法［17］。模擬退火算法(Simulated Annealing algorithm，SA)以物理系統退火過程的相似性為基礎并適當地控制溫度的下降過程來實現模擬退火，從而求解全局優化問題。該算法以蟻群算法為主，首先利用模擬退火算法在蟻群算法初期產生較優解;然后，按照蟻群算法完成一次循環遍歷，再采用模擬退火算法在解的領域內尋找另外一個解。該混合算法分為2部分，即SA階段和ACO階段:首先通過模擬退火算法求解領域解的方法產生一個初始測試用例集，隨后通過蟻群算法對初始測試用例集進行約簡。

需求驅動的測試用例集約簡方法［13］是由國內的聶長海等人提出的。該方法首先對測試需求集R進行約簡，得到約簡測試需求集R'，然后，針對約簡測試需求集R'，采用已有的測試用例集生成和約簡方法，得到測試用例約簡集。該算法能有效地減少后續測試用例生成和約簡的計算開銷，在一定程度上對現有的測試用例集約簡方法進行了補充。

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

3 測試用例集約簡問題評價體系

為了比較不同測試用例集約簡算法的性能，分析各種約簡算法的適用范圍，對于測試用例集約簡算法通常采用以下4個屬性來評價其約簡效果［8］:

(1)充分性(Adequacy)。約簡后的測試用例集應保持與原始用例集相同的測試充分性準則。

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

(3)效益(Cost-effectiveness)。用于測試用例集約簡的費用(即運行約簡算法得到最優測試用例集的費用)應該小于使用約簡后測試用例集進行測試所節省的費用，即需要考慮測試用例集算法的開銷。

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

測試用例集約簡問題在整個求解過程中，在滿足給定測試目標的前提下，刪除測試用例集中的冗余測試用例，以盡可能少的測試用例充分滿足測試目標，從而削減測試用例集的規模，降低運行、維護測試用例集的開銷。與測試用例集約簡問題強相關的一個問題是測試用例集的錯誤檢測能力，即如何在測試用例集的規模及錯誤檢測能力中找到一個平衡點，在滿足一定測試充分性準則的前提下，減小測試用例集規模并盡可能地保持測試用例集的錯誤檢測能力，這也成為了當前測試用例集約簡問題的重要研究課題。

G.Rothermel等人提出的APFD評價方法目前得到了廣泛的應用，該方法能有效評估優化測試用例集的平均錯誤檢測效率。設測試用例集T中有n個測試用例，現已檢測出的錯誤集合F中有m個錯誤，TFi表示T檢測到錯誤i的第一個測試用例在T中的位置，則對應的APFD值如下所示:

由上式可知，APFD值介于0～100%之間，APFD值越大，其錯誤檢測效率越高。在此基礎上，S.Elbaum等人提出了改進的APFDc方法，用于評估當錯誤嚴重等級和測試用例開銷不同時，給定優化測試用例集的平均錯誤檢測效率［8，15］。

4 結束語

隨著軟件測試技術的不斷更新和提高，如何尋找到更為有效的測試用例集約簡算法，特別是同時考慮到測試用例約簡率及其錯誤檢測能力的雙目標測試用例集優化方法，成為了當前軟件測試領域中的關鍵問題和研究重點之一。由測試用例集約簡問題的研究表明，未來的研究工作主要將集中在以下幾個方面［8］:

(1)從測試用例集的規模及錯誤檢測能力出發，結合測試用例優先級技術和基于搜索的優化方法，研究多測試充分性準則的測試用例集約簡方法和多目標的測試用例集優化方法，實現全面的測試用例集優化;

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

(3)采用仿真實驗或大型程序實驗來分析、比較現有方法的性能、適用范圍，為測試人員選擇有效的測試用例集約簡方法提供建議和指導;

(4)設計并開發有效的測試用例集約簡工具，實現測試用例集約簡過程的自動化。

［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］章曉芳，陳林，徐寶文，等.測試用例集約簡問題研究及其進展［J］.計算機科學與探索，2008，2(3):236-247

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

［10］聶長海，徐寶文.一種最小測試用例集生成方法［J］.計算機學報，2003，26(12):1690-1695

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

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

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

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

［15］彭園園，熊盛武.測試用例集的優化技術分析與改進［J］.計算機應用技術，2009，6:77-80

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

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

［18］單錦輝，姜瑛，孫萍.軟件測試研究進展［J］.北京大學學報:自然科學報，2005，41(1):134-145

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

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

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