軟件結(jié)構(gòu)化測(cè)試用例自動(dòng)生成方法

軟件結(jié)構(gòu)化測(cè)試用例自動(dòng)生成方法樊瑋;朱賀【摘要】軟件測(cè)試和軟件開發(fā)對(duì)軟件質(zhì)量具有同等重要的意義，其工作量很大，且其許多過程又適于自動(dòng)化，于是軟件測(cè)試自動(dòng)化應(yīng)運(yùn)而生.測(cè)試用例的生成是軟件測(cè)試過程的重要環(huán)節(jié),近年來，人們開始嘗試將人工智能技術(shù)運(yùn)用于測(cè)試用例生成問題中,產(chǎn)生進(jìn)化測(cè)試思想方法.文中對(duì)基于結(jié)構(gòu)化的測(cè)試用例自動(dòng)生成方法研究現(xiàn)狀作了介紹，重點(diǎn)介紹了進(jìn)化測(cè)試并對(duì)其基于不同進(jìn)化計(jì)算算法的應(yīng)用情況進(jìn)行了比較和總結(jié).應(yīng)用結(jié)果表明進(jìn)化測(cè)試方法是當(dāng)前最為高效的軟件測(cè)試用例自動(dòng)生成方法最后對(duì)進(jìn)化測(cè)試進(jìn)一步的研究方向提出了看法.【期刊名稱】《計(jì)算機(jī)技術(shù)與發(fā)展》【年(卷)，期】2010(020)005【總頁數(shù)】4頁(P26-28,33)【關(guān)鍵詞】軟件測(cè)試;進(jìn)化測(cè)試;測(cè)試用例生成;進(jìn)化算法【作者】樊瑋;朱賀【作者單位】中國(guó)民航大學(xué)，計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，天津,300300;中國(guó)民航大學(xué)，計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，天津,300300【正文語種】中文【中圖分類】TP311.56軟件測(cè)試是保證軟件可靠性的主要手段，其目的是發(fā)現(xiàn)軟件錯(cuò)誤、提高軟件質(zhì)量。通常，軟件測(cè)試的工作量很大，且許多操作是重復(fù)性的、非智力性的和非創(chuàng)造性的，并要求精確，計(jì)算機(jī)適合代替人工去完成這樣的任務(wù)。測(cè)試用例生成是軟件測(cè)試過程的重要環(huán)節(jié)彳艮長(zhǎng)時(shí)間，測(cè)試人員根據(jù)經(jīng)驗(yàn)采用手工方法設(shè)計(jì)測(cè)試用例，測(cè)試用例的自動(dòng)生成將有效地減輕測(cè)試人員的勞動(dòng)強(qiáng)度，降低軟件開發(fā)成本。根據(jù)估算［1］,對(duì)于一個(gè)典型的大型軟件項(xiàng)目若能自動(dòng)生成測(cè)試用例，大約能節(jié)省整個(gè)軟件開發(fā)費(fèi)用的4%。文中首先介紹結(jié)構(gòu)化測(cè)試的一般方法;然后詳細(xì)介紹結(jié)構(gòu)化測(cè)試的最新方法——進(jìn)化測(cè)試;之后，將介紹幾種用于進(jìn)化測(cè)試的進(jìn)化算法;最后對(duì)結(jié)構(gòu)化測(cè)試用例自動(dòng)生成方法進(jìn)行總結(jié)。1結(jié)構(gòu)化測(cè)試方法基于程序結(jié)構(gòu)的測(cè)試用例自動(dòng)生成方法包括隨機(jī)法、符號(hào)執(zhí)行法和基于程序執(zhí)行的方法。1.1隨機(jī)法D.Bird［2］等采用隨機(jī)法自動(dòng)生成測(cè)試用例，隨機(jī)法是最簡(jiǎn)單的動(dòng)態(tài)生成測(cè)試數(shù)據(jù)的方法，在實(shí)際運(yùn)用中甚至可以產(chǎn)生幾乎任何一種類型的測(cè)試數(shù)據(jù)。因?yàn)槿魏螖?shù)據(jù)類型在計(jì)算機(jī)中的表示歸根到底都是一組二進(jìn)制串，它的基本思想是對(duì)輸入數(shù)據(jù)域進(jìn)行隨機(jī)取樣，可以用于黑盒測(cè)試啟前很多測(cè)試工具用的就是這種隨機(jī)法。1.2符號(hào)執(zhí)行法C.Ramanmoorthy［3］、Clarke［4］和P.D.Coward［5］及王言志等人［6］提出的都是符號(hào)執(zhí)行法。該方法的主要思想是使用符號(hào)值，如變量的名稱，而不是實(shí)際的數(shù)據(jù)來代表程序輸入，并在執(zhí)行過程中產(chǎn)生關(guān)于輸入符號(hào)的代數(shù)表達(dá)式。它建立約束系統(tǒng)的方式主要有兩種：從前向后替換和從后向前替換［3］。但是隨著程序規(guī)模的增大，符號(hào)表達(dá)式變得很長(zhǎng)，求解一般比較困難。1.3Korel法與前面的靜態(tài)方法對(duì)應(yīng)的是動(dòng)態(tài)法。所謂動(dòng)態(tài)法是要從變量的最小定義域中選取一組值作為程序的輸入，然后運(yùn)行程序并根據(jù)運(yùn)行情況修改輸入的值。Korel［7］所提出的方法就是動(dòng)態(tài)法的一種：從輸入域D中任選一組數(shù)據(jù)，按步進(jìn)的方式運(yùn)行程序p,即一次前進(jìn)一個(gè)分支謂詞。若當(dāng)前分支謂詞的值不符合要求，就建立一個(gè)分支函數(shù)，然后用函數(shù)最小化方法調(diào)整輸入變量值,使得在仍能經(jīng)過已成功經(jīng)過的子路徑的前提下,適應(yīng)值f為負(fù)數(shù)（或0）。該方法先用探測(cè)性搜索確定前進(jìn)方向,再用模式性搜索使分支函數(shù)值盡快達(dá)到最小值，并采用動(dòng)態(tài)數(shù)據(jù)流分析技術(shù)確定影響分支謂詞的變量減小搜索的盲目性。1.4進(jìn)化測(cè)試方法近年來，人們開始嘗試將人工智能技術(shù)運(yùn)用于軟件測(cè)試。首先選擇輸入數(shù)據(jù)并執(zhí)行程序，然后根據(jù)執(zhí)行結(jié)果〃進(jìn)化”出新的輸入數(shù)據(jù)繼續(xù)試探，直至找到正確的解。其優(yōu)點(diǎn)是不受搜索空間限制性條件的約束并且不需要其它輔助性信息（如導(dǎo)數(shù)）,所以對(duì)于一些傳統(tǒng)方法難于處理的大空間、全局優(yōu)化等復(fù)雜度較高的問題，該方法具有獨(dú)特的優(yōu)勢(shì)和高效性。具有全局尋優(yōu)能力而又有較高魯棒性的進(jìn)化算法應(yīng)用在這個(gè)空間中進(jìn)行測(cè)試用例的搜索成為最佳選擇,即進(jìn)化測(cè)試。2進(jìn)化測(cè)試進(jìn)化測(cè)試即利用現(xiàn)代啟發(fā)式組合優(yōu)化技術(shù)來產(chǎn)生軟件測(cè)試用例的方法，基于進(jìn)化測(cè)試思想的優(yōu)化方法已成功應(yīng)用于大規(guī)模集成電路測(cè)試（Cornoetal.1996）。進(jìn)化測(cè)試系統(tǒng)遵從一種動(dòng)態(tài)測(cè)試用例產(chǎn)生策略。系統(tǒng)存在一個(gè)適值函數(shù)，每一步選擇一個(gè)實(shí)體作為實(shí)際的測(cè)試目標(biāo),執(zhí)行測(cè)試用例，若該測(cè)試用例完成該目標(biāo)，適值函數(shù)取最小值,否則根據(jù)被測(cè)代碼的執(zhí)行信息按比例賦予適值函數(shù)一個(gè)近似值。然后，搜索算法通過當(dāng)前一組測(cè)試用例的適值函數(shù)值來產(chǎn)生下一組測(cè)試用例。進(jìn)化測(cè)試用例產(chǎn)生模式［8］如圖1所示，每一次循環(huán)都包含兩個(gè)連續(xù)的過程：選擇和優(yōu)化。圖1進(jìn)化測(cè)試模式盡管存在多種不同的選擇策略，但其共同的方式都是通過能夠反映被測(cè)代碼結(jié)構(gòu)性質(zhì)的圖形來決定目標(biāo)實(shí)體，即控制流圖。在控制流圖中,程序分支可以由每一個(gè)出度為1的結(jié)點(diǎn)向量來定義。按圖1所示模式，接下來要解決的是一個(gè)優(yōu)化問題，具體來說就是給定一個(gè)由程序輸入空間所限定的一個(gè)搜索空間Q和一個(gè)適值函數(shù)h:Q->IR,搜索x*eQ使h(x*)<h(x)對(duì)xeQ。當(dāng)輸入到達(dá)目標(biāo)實(shí)體時(shí)，函數(shù)h為最小值。下面介紹進(jìn)化測(cè)試模式的兩個(gè)核心過程。優(yōu)化過程。這個(gè)過程主要來解決前面所提到的優(yōu)化問題。一個(gè)0-1串代表一個(gè)輸入，它的適應(yīng)值由函數(shù)h計(jì)算。計(jì)算適應(yīng)值h所需的一些信息通過被測(cè)代碼實(shí)際執(zhí)行來獲取。每個(gè)分支綁定一個(gè)輸入集，用于存儲(chǔ)那些對(duì)該分支取得較好適應(yīng)值的輸入。在優(yōu)化過程中，盡管每次都有一個(gè)系統(tǒng)目標(biāo)，但同時(shí)考慮當(dāng)前輸入對(duì)每一個(gè)未被覆蓋的分支的適用性，若該分支被覆蓋到了則該分支確定為已覆蓋，否則該輸入的適應(yīng)值好于該分支參考集中的最差個(gè)體，則用該輸入替換那個(gè)最差的個(gè)體。選擇過程。候選分支是那些未被覆蓋到的分支。目標(biāo)分支是其參考集中個(gè)體的平均適應(yīng)值最差的分支。當(dāng)出現(xiàn)均值相等時(shí)，則通過深度優(yōu)先策略來決定選取哪個(gè)分支為目標(biāo)。3用于測(cè)試用例生成的進(jìn)化算法本質(zhì)上進(jìn)化算法是不依賴具體問題的直接搜索方法，算法和進(jìn)化測(cè)試系統(tǒng)框架通過種群和適值函數(shù)聯(lián)結(jié)起來［9］。下面將簡(jiǎn)要介紹進(jìn)化測(cè)試的幾種進(jìn)化算法。3.1遺傳算法遺傳算法進(jìn)行進(jìn)化測(cè)試［10~13］的實(shí)踐中，常常遇到數(shù)據(jù)收斂過慢的問題，直接導(dǎo)致測(cè)試數(shù)據(jù)生成速度不高乃至最終無法生成。因?yàn)榻徊纥c(diǎn)位置為隨機(jī)選擇，因此常常會(huì)選擇不當(dāng)，導(dǎo)致交叉后生成新的數(shù)據(jù)的適應(yīng)度值反而有所下降。3.2模擬退火算法模擬退火算法在測(cè)試用例生成問題上［14~17］,其一般是作為遺傳算法的一個(gè)協(xié)作算法來使用。引入模擬退火算法當(dāng)中的Metropolis準(zhǔn)則，并且根據(jù)實(shí)際情況對(duì)個(gè)體鄰域的構(gòu)造加以改進(jìn)，采用新方法構(gòu)造個(gè)體的鄰域。這樣可以在一定程度上保持物種的多樣性，使得算法不至于陷入局部最優(yōu)化解當(dāng)中，并且可以提高算法整體收斂速度。3.3蟻群算法蟻群算法生成軟件測(cè)試用例是在知識(shí)表示的基礎(chǔ)上,應(yīng)用蟻群算法完成知識(shí)推理，其關(guān)鍵是設(shè)計(jì)表示用例的螞蟻路徑。在測(cè)試用例生成問題上［18~21］由于搜索初期信息素相對(duì)匱乏,導(dǎo)致算法的搜索效率降低,正反饋機(jī)制容易產(chǎn)生停滯早熟現(xiàn)象。為了克服蟻群算法的不足，多數(shù)作法往往引入遺傳算子，利用其變異操作,增加搜索的隨機(jī)性、快速性和全局收斂性。3.4禁忌搜索禁忌搜索思想最早由Lover(1986)提出，它是對(duì)局部鄰域搜索的一種擴(kuò)展，是一種全局逐步尋優(yōu)算法，是對(duì)人類智力過程的一種模擬。在測(cè)試用例生成問題上［22-24］,其通過設(shè)置近期操作的禁忌表，以當(dāng)前解鄰域中未在禁忌表中出現(xiàn)或滿足藐視規(guī)則的最佳狀態(tài)來替換當(dāng)前狀態(tài)，而并不在乎其性能是否優(yōu)于當(dāng)前解,按此原則產(chǎn)生一定的突跳性以避免局部極小，同時(shí)也避免迂回搜索的出現(xiàn)。3.5免疫算法免疫算法是模擬生物免疫系統(tǒng)智能行為的仿生算法。在進(jìn)化測(cè)試過程中［25］,免疫系統(tǒng)利用多樣性產(chǎn)生和維持機(jī)制，來保持解群體的多樣性,從而克服一般尋優(yōu)過程尤其是多峰值函數(shù)中最難應(yīng)付的〃早熟”問題，最終求得全局最優(yōu)解。而且可以引入疫苗接種機(jī)制，即利用先驗(yàn)知識(shí)來引導(dǎo)尋優(yōu)過程，進(jìn)一步提高算法的快速性和有效性。3.6粒子群算法粒子群算法源于鳥群捕食行為的研究。在測(cè)試用例生成問題上[26,27],其優(yōu)勢(shì)是算法收斂速度快，但由于其易于陷入局部最優(yōu)且搜索精度不高，所以通常要與其它優(yōu)化算法協(xié)作來發(fā)揮其優(yōu)勢(shì),彌補(bǔ)其不足。3.7分布估計(jì)算法分布估計(jì)算法提出了一種全新的進(jìn)化模式[28],它由遺傳算法演化而來，沒有了傳統(tǒng)的交叉、變異等操作，取而代之的是概率模型的學(xué)習(xí)和采樣。在進(jìn)化測(cè)試[8,29]中，其通過一個(gè)概率模型描述候選解空間的分布，采用統(tǒng)計(jì)學(xué)習(xí)手段從上一代種群選擇優(yōu)秀個(gè)體來更新解分布的概率模型，然后利用概率模型隨機(jī)采樣產(chǎn)生新的種群，上一代的優(yōu)秀個(gè)體的特性能很好地體現(xiàn)到下一代中，故其收斂速度較快。4結(jié)束語軟件測(cè)試用例生成經(jīng)歷了從測(cè)試人員根據(jù)經(jīng)驗(yàn)采用手工設(shè)計(jì)方法到借助計(jì)算機(jī)自動(dòng)生成,自動(dòng)生成方法又經(jīng)歷了從靜態(tài)方法到動(dòng)態(tài)方法，從人工智能技術(shù)的引入又產(chǎn)生了進(jìn)化測(cè)試方法，每一次發(fā)展都使測(cè)試用例生成效率得到了極大的提高。人們的應(yīng)用結(jié)果表明進(jìn)化測(cè)試方法是當(dāng)前最為高效的軟件測(cè)試用例自動(dòng)生成方法。通過進(jìn)化測(cè)試模式可見，測(cè)試用例自動(dòng)生成問題也是一個(gè)多目標(biāo)優(yōu)化問題，且程序中的條件可能是多個(gè)參數(shù)的復(fù)合表達(dá)式,故進(jìn)化算法中所產(chǎn)生的用例個(gè)體可能是多變量相關(guān)的。誠(chéng)然,將更多的適于求解多目標(biāo)優(yōu)化和多變量相關(guān)的算法引入進(jìn)化測(cè)試中是值得嘗試和研究的。參考文獻(xiàn)：黃錫滋.軟件可靠性、安全性與質(zhì)量保證[M].北京：電子工業(yè)出版社,2004:1516.BirdD,MunozC.Automaticgenerationofrandomselfcheckingtestcases[J].IBMSystem,1983,22(3):229-245.RamamoorthyCV,HoSBF,ChenWT.Ontheautomatedgenerationofprogramtestdata[J].IEEETransonSoftwareEngineering,1976,SE-2(4):293-300.ClarkeLA.ASystemtoGenerateTestDataSymbolicallyandExecutePrograms[J].IEEETransactionSoftwareEngineering,1976,2(3):215-222.CowardPD.Symbolicexecutionandtesting[J].InformationandSoftwareTechnology,1991(2):53-64.王言志,劉椿年.區(qū)間算術(shù)在軟件測(cè)試中的應(yīng)用[J].軟件學(xué)報(bào),1998,9(6):438-443.KorelB.AutomatedSoftwareTestDataGeneration[J].IEEETransactionsonsoftwareengineering,1990,16(8):870-879.SagarnaR,LozanoJ.OnthePerformanceofestimationofdistributionalgorithmsappliedtosoftwaretesting[J].AppliedArtificialIntelligence,2005,19(5):457-489.王凌.智能優(yōu)化算法及其應(yīng)用[M].北京：清華大學(xué)出版社,2001.BalujaS.Population-basedincrementallearning:Amethodforintegratinggeneticsearch-basedfunctionoptimizationandcompetitivelearning[R].Pittsburgh:CarnegieMellonUniversity,1994.SthamerJBH,EyresD.Automaticstructuraltestingusinggeneticalgorithms[J].SoftwareEngineeringJournal,1996,11(5):299-306.SthamerH.TheAutomaticGenerationofSoftwareTestDataUsingGeneticAlgorithms[D].Pontyprid,Wales,GreatBritain:UniversityofGlamorgan,1996.PargasR,HaroldM,PeckR.Test-datagenerationusinggeneticalgorithms[J].JournalofSoftwareTesting,VerificationandReliability,1999,9(4):263-282.TraceyN,ClarkJ,ManderK,etal.AnAutomatedFrameworkforStructuralTest-DataGeneration[C]//InProceedingsoftheInternationalConferenceonAutomatedSoftwareEngineering.[s.l.]:IEEE,1998.LiBin,LiZhishu,ChenYanhong.AutomaticTestDataGenerationToolBasedonGeneticSimulatedAnnealingAlgorithm[C]//InternationalConferenceonComputationalIntelligenceandSecurityWorkshops.[s.l.]:IEEE,2007:183-186.馬敏，陳光，陳東義.基于Petri網(wǎng)和模擬退火遺傳算法的并行測(cè)試研究[J].儀器儀表學(xué)報(bào),2007(2):331-336.傅博.基于模擬退火遺傳算法的軟件測(cè)試數(shù)據(jù)自動(dòng)生成[J].計(jì)算機(jī)工程與應(yīng)用2005(12):82-84.陳路遠(yuǎn).基于螞蟻算法的路徑測(cè)試數(shù)據(jù)自動(dòng)生成方法研究[D].天津：河北工業(yè)大學(xué),2007.胡先智.基于遺傳螞蟻融合算法的測(cè)試用例生成研究[D].西安：西安理工大學(xué),2008.傅博.基于蟻群算法的軟件測(cè)試數(shù)據(jù)自動(dòng)生成[J].計(jì)算機(jī)工程與應(yīng)用,2007(12):97-100.陳明師，劉曉杰，李濤.基于多態(tài)蟻群的測(cè)試用例自動(dòng)生成[J].計(jì)算機(jī)應(yīng)用研究,2009,26(6):2347-2348.DiazaE,TuyaaJ,BlancoaR,etal.Atabusearchalgorithmforstruct