胡 靜, 趙 瑩

(上海電機(jī)學(xué)院電子信息學(xué)院,上海200240)

機(jī)器學(xué)習(xí)在軟件測試用例集優(yōu)化生成中的應(yīng)用

胡 靜, 趙 瑩

(上海電機(jī)學(xué)院電子信息學(xué)院,上海200240)

軟件測試用例集生成是軟件測試中的重要環(huán)節(jié)。如何優(yōu)化軟件測試用例集,有效提高軟件測試用例集的質(zhì)量,已成為提高軟件測試效率的主要手段。機(jī)器學(xué)習(xí)是解決這類問題的有效方法,目前也取得了許多重大的成果。本文對機(jī)器學(xué)習(xí)在軟件測試用例集優(yōu)化生成中的國內(nèi)外研究現(xiàn)狀及存在問題進(jìn)行了分析,并在此基礎(chǔ)上對機(jī)器學(xué)習(xí)與軟件測試用例優(yōu)化結(jié)合的發(fā)展趨勢提出了看法。

軟件測試用例集;機(jī)器學(xué)習(xí);遺傳算法;流形學(xué)習(xí);測試用例優(yōu)化生成

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

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

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

1 國內(nèi)外研究現(xiàn)狀

軟件測試方法是為了更好地實現(xiàn)軟件測試的目的而提出的途徑和優(yōu)良做法,其內(nèi)容非常豐富,依據(jù)不同的目的、不同的角度有許多不同的分類結(jié)果。其中以功能測試和結(jié)構(gòu)測試最為經(jīng)典,本文以這兩種測試方法為主,介紹軟件測試與機(jī)器學(xué)習(xí)二者的結(jié)合。

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

在結(jié)構(gòu)測試領(lǐng)域中,主要根據(jù)程序的內(nèi)部結(jié)構(gòu)設(shè)計測試用例,檢測程序的每條路徑是否都按照預(yù)定的要求正確執(zhí)行。結(jié)構(gòu)測試要求對被測程序的結(jié)構(gòu)特性做到一定程度的覆蓋,如語句覆蓋、分支覆蓋、數(shù)據(jù)流覆蓋、路徑覆蓋等。其測試數(shù)據(jù)生成是在輸入域中,尋找滿足測試準(zhǔn)則的輸入數(shù)據(jù)的過程。

結(jié)構(gòu)測試用例的生成較多地受到符號執(zhí)行等自動化技術(shù)的局限,不能自動產(chǎn)生達(dá)到滿意覆蓋程度的用例集,故測試人員需要手工生成數(shù)據(jù)以覆蓋一些特定的目標(biāo)。隨機(jī)測試雖然可以提高自動化程度,但是它會產(chǎn)生大量的測試數(shù)據(jù),查錯率也不是很高[13]。

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

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

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

2 存在的若干問題

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

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

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

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

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

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

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

3 分析與展望

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

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

作為機(jī)器學(xué)習(xí)的重要研究領(lǐng)域——流形學(xué)習(xí)的主要目的在于發(fā)現(xiàn)并學(xué)習(xí)數(shù)據(jù)集里的內(nèi)在規(guī)律與性質(zhì),完成或協(xié)助完成數(shù)據(jù)挖掘等各項任務(wù)[23]。流形學(xué)習(xí)和軟件測試用例精簡看起來是兩個不同的概念,但兩者之間存在一定的聯(lián)系。

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

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

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

4 結(jié) 語

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

[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].北京:中科院計算技術(shù)研究所,2006.

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

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

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

[23]趙連偉,羅四維,趙艷敞,等.高維數(shù)據(jù)流形的低維嵌入及嵌入維數(shù)研究[J].軟件學(xué)報,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

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

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