機器學習在軟件測試用例集優化生成中的應用

胡 靜, 趙 瑩

(上海電機學院電子信息學院,上海200240)

機器學習在軟件測試用例集優化生成中的應用

胡 靜, 趙 瑩

(上海電機學院電子信息學院,上海200240)

軟件測試用例集生成是軟件測試中的重要環節。如何優化軟件測試用例集,有效提高軟件測試用例集的質量,已成為提高軟件測試效率的主要手段。機器學習是解決這類問題的有效方法,目前也取得了許多重大的成果。本文對機器學習在軟件測試用例集優化生成中的國內外研究現狀及存在問題進行了分析,并在此基礎上對機器學習與軟件測試用例優化結合的發展趨勢提出了看法。

軟件測試用例集;機器學習;遺傳算法;流形學習;測試用例優化生成

Abstract：Software test suite generation is important in software testing.Improving quality of test suite is a key in software testing.Machine learning is an effective way in solving the problem,and have a lot of results.This paper introduces some current research,methods and problems in machine learning for optimized generation test suites,and provides some opinions.

Key words:software test suite;machine learning;genetic algorithms;manifold learning;optimized generation of test suite

軟件測試是為了發現錯誤而執行程序的過程,其中,設計和生成有效的測試用例是決定軟件測試質量的重要保證[1]。選取一批對錯誤敏感的測試用例可有效地提高發現軟件錯誤的可能性,從而降低軟件測試成本[2]。因此,如何發現對錯誤敏感的測試用例一直都是軟件測試人員所研究的重要課題。

測試用例的生成可以被理解成一個數據抽樣的過程,即根據相應的數據測試覆蓋標準,采用一定的方法,在數據集中進行抽樣,以獲取一批高質量的、對隨后的測試過程貢獻較大的測試用例[3]。這個過程可以看成是一個學習過程,通過對測試用例總集的不斷學習,從中獲取高質量的用例子集,并盡可能地降低測試用例的總數,節省測試成本。因而機器學習的方法自然而然地就成為了人們關注的焦點,各種機器學習的方法和成果被用來設計與生成軟件測試用例,并取得了相應的研究成果,使得機器學習的方法在軟件測試中發揮了越來越大的作用[4-5]。

1 國內外研究現狀

軟件測試方法是為了更好地實現軟件測試的目的而提出的途徑和優良做法,其內容非常豐富,依據不同的目的、不同的角度有許多不同的分類結果。其中以功能測試和結構測試最為經典,本文以這兩種測試方法為主,介紹軟件測試與機器學習二者的結合。

在功能測試領域中,主要是以檢查程序是否正確執行規格說明書的手段來完成測試任務,測試用例的生成是根據規格說明來選擇的。早期的測試由于缺乏形式化標準的規格說明,不能很好地完成測試要求。為了盡可能多地發現被測系統中的缺陷,最理想的情況是將系統中所有合法和不合法的輸入情況全部執行一遍,故一般采用人工方式選擇測試用例集。在利用機器學習方法優化測試用例集方面,Cohen等[6-8]提出了一種數據啟發方法,根據某種啟發性原則來選取測試用例集,其中啟發性原則的好壞直接影響測試的結果,同時開發了相應的測試數據自動生成系統AETG(Automatic Efficient Test Generate)。Lei等[9]利用貪心算法,提出一種依據參數順序來組合測試數據生成的方法。該算法的主要思想是每次從測試用例集中挑選出能滿足最多測試需求的測試用例,然后在測試需求中去掉被該測試用例滿足的測試需求,直到所有測試需求都被滿足,這時可以認為挑選出來的測試用例所組成的集合就是最優測試用例集。該方法也開發了相應的測試數據生成工具 PAIRTEST。此外,Cohen等[10-11]將模擬退火法應用于測試數據生成;Schrocder等[12]提出了一種測試數據約簡方法,利用系統的輸入-輸出關系等附加信息,在不降低錯誤檢測能力前提下,對測試數據集進行約簡。

在結構測試領域中,主要根據程序的內部結構設計測試用例,檢測程序的每條路徑是否都按照預定的要求正確執行。結構測試要求對被測程序的結構特性做到一定程度的覆蓋,如語句覆蓋、分支覆蓋、數據流覆蓋、路徑覆蓋等。其測試數據生成是在輸入域中,尋找滿足測試準則的輸入數據的過程。

結構測試用例的生成較多地受到符號執行等自動化技術的局限,不能自動產生達到滿意覆蓋程度的用例集,故測試人員需要手工生成數據以覆蓋一些特定的目標。隨機測試雖然可以提高自動化程度,但是它會產生大量的測試數據,查錯率也不是很高[13]。

機器學習方法在結構測試領域的應用主要以遺傳算法為主。遺傳算法在機器學習領域是一個非常有前途的學習算法,它將測試用例的生成問題轉化為一個利用遺傳算法進行數值優化的問題。其中,被搜索的解空間就是測試數據空間,最優解就是滿足特定測試目標測試數據。該搜索過程可以完全自動化,從而有助于提高測試效率。在遺傳算法中,適應度函數根據測試數據對結構性元素的覆蓋程度來計算測試數據的重要性。Poper等[14]提出了一種基于程序流程圖的適應度函數構造方法,適應于語句覆蓋與分支覆蓋。Weichselbaum等[15]提出了一種新的進化測試方法,可用于語句、分支與條件覆蓋。針對不同的測試目標,研究者們[16-17]提出了一系列的適應度值構造方法,可用于語句與分支的覆蓋。此外,還有一些方法可用于條件覆蓋[18]。

機器學習與軟件測試技術結合在我國雖然起步較晚,但隨著軟件測試在我國許多部門越來越受到重視,關于機器學習與測試用例集優化研究也越來越被重視起來,并取得了一些成果。如文獻[19]提出了基于貝葉斯統計推斷理論的軟件測試用例估計方法,以貝葉斯的統計理論為依據,在對隨機測試過程進行形式化描述的基礎上,確定測試用例分布的總體信息。文獻[20]提出了應用模糊數學理論,給出選取測試用例的方法,并證明此方法有效。

上述研究或從輸入域的角度,探索利用機器學習的方法精簡輸入集,節省了測試時間,提高了測試效率;或從輸入-輸出對的角度,探索測試數據與測試目標之間的距離,試圖縮短從輸入空間到輸出空間的有效路徑,達到整體提高測試效率的目的。每個方法都取得了一定的成果,也存在著一些問題。

2 存在的若干問題

在結構測試領域,機器學習方法是精選少量的測試用例的科學有效的方法,也是研究者們研究的重點[21-22],也取得了一些成果。但是,由于最優的測試用例生成是一個多項式復雜度的非確定性難題(NP),所以大多數方法都只是提供了近似解,每種方法在特定情況下都存在著不足之處。

(1)遺傳算法、模擬退火法等優化方法最大的特點就是可以很快地生成滿足測試目標的測試數據,且檢錯能力也大大提高。但是,大多數的研究僅針對控制流測試中的語句覆蓋和分支覆蓋,對于路徑覆蓋的研究較少。此外,目前的研究僅限于單元測試領域,較少深入到集成測試領域中。

(2)遺傳算法中,適應度函數設計是決定遺傳算法執行結果好壞的關鍵。在面向結構性測試的應用中,適應度函數的設計一般遵循如下規則[6]:適應度函數根據數據對結構性元素的覆蓋程度來計算測試數據的適應度值。此類方法先要構造測試程序流程圖,然后利用測試數據執行軌跡來計算相應的適應值。其適應度函數 F的構造為

F取值為[0,1]。適應度函數的設計不僅能考慮測試過程中非常重要的覆蓋因素,而且還能考慮測試過程中的空間和時間因素,則所設計的適應度值將更具有通用性。若適應度函數的設計思路設計為

式中,Tj為時間參數,j∈[0,1];Kj為空間參數;cost(Tj,Kj)的值與空間、時間都相關,即與內存的消耗量成反比,與程序運行的速度成正比;而cov(Tj,Kj)的值取決于測試用例所覆蓋到的路徑的價值,被覆蓋的路經越新,其分數就越高。但是目前在遺傳算法與測試用例生成的結合中,按照這種思想來設計適應度函數的應用還較少。

貝葉斯理論可以簡單地被描述成一條原則:為了預見未來,必須要看過去。某件事情發生的概率大致可由它過去發生的頻率近似估計出來。貝葉斯方法的最大特點是方法簡單,理論依據充分,模型假設易于理解等,但是其缺點也很明顯,即它的先驗分布函數估計建立在隨機的先驗分布函數基礎上,受隨機測試數據選取影響較大,雖然要求盡可能地選取均勻分布的隨機測試數據,卻給隨機測試也帶來了一定的難度。

啟發式算法是一種根據某種啟發性原則來選取測試用例的選擇性測試方法,啟發性原則的好壞直接影響測試的結果。對于一些測試數據,較難自動地構造出啟發性原則,故如何構造合適的啟發性選擇原則,也是研究人員研究的重點所在。

3 分析與展望

一個成功的測試用例集首先應該滿足充分性,即待測軟件在這個有限的測試用例集上的行為,應該充分體現軟件在整個輸入空間的行為。無論理論研究還是實驗結果都表明,對于相同數量的測試數據,結合機器學習方法所產生的測試數據,在發現錯誤的能力方面明顯要高于隨機性所產生的測試數據。但是到底能提高多少還是一個未知數,即對利用某種機器學習方法而挑選出來的測試用例集,其價值到底有多高?每個測試用例對測試的貢獻有多大?還缺乏一個根本的度量。

機器學習與具體的領域知識相結合,以此來解決一些實際問題,其主要途徑有:①整體建模方式;②局部建模方法。目前機器學習方法在軟件測試用例生成方面的研究大多采用整體建模的方法,實際上就是先假設滿足測試要求的所有用例集存在,然后在所有測試用例集上選擇較小的、較優的用例集。此外,局部建模的方法在解決非線性、海量數據處理方面有著比整體建模方法更大的優勢,如流形學習法、集群學習法等。從測試角度看,某些軟件系統功能龐大,參數復雜,滿足測試要求的測試用例具有數量大、維數高的特點。解決這類軟件系統的測試用例精簡問題一般難度都較大,如遺傳算法中適應度函數的設計,啟發式方法中啟發性信息的確定等。

作為機器學習的重要研究領域——流形學習的主要目的在于發現并學習數據集里的內在規律與性質,完成或協助完成數據挖掘等各項任務[23]。流形學習和軟件測試用例精簡看起來是兩個不同的概念,但兩者之間存在一定的聯系。

假設所有測試用例的集合記為Uall,被測軟件系統如果有 N個測試參數,每個參數有 T個取值,每個取值里又有 t個元素,且任何一個測試用例都不是其他測試用例的線性組合,顯然,Uall∈Rn(Rn為實數高維空間)具有高維非線性的特點。同時,又由于它們屬于同一被測軟件,因此,從高維空間角度看,它們具有連續分布的特性,即在Uall中,從一個測試用例Ui(1

從感知的角度看,流形是認知的基礎,任何一個高維流形一般存在于一個非線性低維流形上[24-25],認知過程在很大程度上是通過這種非線性低維流形表示來識別事物的。也就是說,無論流形結構有多么復雜,人們都可以通過少數幾個“本質”參數去迅速地認識它,同理,被測軟件的測試用例集合也可通過這些“關鍵”參數來認識其內在規律和性質。

利用流形學習的方法進行軟件測試用例集精簡,其目標就是從在高維空間里具有“流形”分布的全體測試用例集中選擇出“最具代表性”的測試用例集,以達到有效精簡測試用例集的目的。對于中、大型軟件系統,從輸入空間角度看,因測試數據集滿足非線性、海量數據集的特點,故如流形學習等基于局部建模的機器學習方法與軟件測試領域結合將有著更好、更廣泛的發展前景。

4 結 語

隨著軟件測試工作的重要性越來越高,以及機器學習方法與其結合越來越緊密,期望機器學習解決的測試問題層出不窮。各類機器學習方法在軟件測試方面的應用由此派生。這無論對機器學習領域還是軟件測試領域來說,都具有十分重要的研究價值。

[1]Myer GJ,Sandler C,Badgett T,et al.The art of software testing[M].2nd ed.[S.l.]:John Wiley&Sons,2004:234-240.

[2]Patton R.Software Testing.[M].2nd ed.[S.l.]:SAMS&Education,2006:10-14.

[3]Clarke J,Dolado J J,Haman M,et al.Reformu lating software engineering as a search problem[J]. IEE Proceedings Software,2003,150(3):161-175.

[4]Kuhn D R,Wallace D R,Gallo A M.Software fault interaction and implication for software testing[J].IEEE Transcations on Software Engineering,2004,30(6):418-421.

[5]Wegener J.Overview of evolutionary testing[C]//IEEE Seminal Workshop.T oronto,Canada:IEEE,2001:46-54.

[6]Coher D M,Dalal S R,Fredman M,et al.The AETG system:an approach to testing based on combinatoral design[J].IEEE Transactions on Software Engineering,1997,23(7):437-444.

[7]Coher D M,Dalal S R,Parelius J,et al.The combinatorial design approach to automatic test generation[J].IEEE software,1996,13(5):83-88.

[8]Cohen D M,Fredman M L.New techniques for designing qualitatively independentsystem[J].Journal of combinatorial design,1998,6(6):411-416.

[9]Tai K C,Lei Y.A test generation strategy for pairwise testing[J].IEEE Transactions on Software Engineer,2002,28(1):109-111.

[10]Poole J.A method to determine a basis set of paths to perform program testing[EB/OL].[2009-12-28].http:∥hissa.nist.gov/publications/nistir5737.

[11]Cohen M B,Gibbons P B,Mugridge W B,et al.Constructing testsuites forinteraction testing[C]//Processing of the 25th International Conference on Software Engineering.Washington,D C:IEEE Computer Society,2003:38-48.

[12]Schroeder P J,Korel B.Black-box test reduction using input-output analysis[J].ACM SIGSOFT Software Engineering Notes,2000:173-177.

[13]Chen T Y,Tes T H,Zhou Zhiquan.Fault-based testing without the need of oracle[J].Information and Software Technology,2003,45(1):1-9.

[14]Roper M.Computer-aided software testing using genetic algorithms[C]//The10th international software quality week(QW'97).San Francisco,USA:[s.n],1997.

[15]Weichselbaum R. Software testautomation by means of genetic algorithms[C]//Proceedings of The 6th International Conference on Software Testing,Analysis and Review.Munich,Germany:[s.n.],1998.

[16]Sthamer H H.The automatic generation of software test data using genetic algorithms[D].Pontyprid,U K:Thesis University of Glamorgan,1996.

[17]Traccy N,Clark J,Mander K,et al.An automated framework for structural test-data generation[C]//Proceedings of the 13th IEEE Conference on Automated Software Engineering.Hawaii,USA:[s.n.],1998:285-288.

[18]Kaner C,Bach J,Pettichord B.Lessons learned in software testing[J].Computing Reviews,2004,45(12):769-770.

[19]張廣梅.軟件測試與可靠性評估[D].北京:中科院計算技術研究所,2006.

[20]楊勁濤,郭荷清.一種精簡測試用例方法的研究[J].計算機科學,2005,32(5):236-239,F004.

[21]莢 偉,謝軍闿,奚紅宇,等.遺傳算法在軟件測試數據生成中的應用[J].北京航天航空大學學報,1998,24(4):434-437.

[22]史 亮,徐寶文.測試數據自動生成技術研究[D].南京:東南大學,2006:5-8.

[23]趙連偉,羅四維,趙艷敞,等.高維數據流形的低維嵌入及嵌入維數研究[J].軟件學報,2005,16(8):1423-1430.

[24]Camastra F.Data dimensionality estimation methods:a survey[J].Pattern Recognition,2003,36(12):2945-2954.

[25]Gonzalez J,Rojas J,Pomares H,et al.A new clustering technique forfunction approximation[J].IEEE Transactions on NeuralNetworks,2002,13(1):132-142.

Application of Machine Learning in Optimized Generation of Software Test Suite

HU J ing, Z HAO Ying
(School of Electrics and Information,Shanghai Dianji University,Shanghai 200240,China)

TP 18;TP 311.56

A

1671-2730(2010)03-0162-05

2010-02-26

上海市教育委員會科研創新項目(09Y2479)

胡 靜(1964-),女,副教授,博士,專業方向為機器學習與智能信息處理,E-mail:hujing@sdju.edu.cn