基于遺傳算法與XML的測(cè)試用例自動(dòng)生成執(zhí)行系統(tǒng)研究與實(shí)現(xiàn)

劉慰+應(yīng)新洋

摘 要： 自動(dòng)化軟件測(cè)試技術(shù)因?yàn)槠湫矢?，成本低的?yōu)點(diǎn)，成為近年來(lái)軟件測(cè)試技術(shù)的重要研究方向和發(fā)展趨勢(shì)。文章提出并實(shí)現(xiàn)了一個(gè)測(cè)試用例自動(dòng)生成與執(zhí)行系統(tǒng)，能夠利用以遺傳算法為核心的測(cè)試數(shù)據(jù)生成方法，自動(dòng)生成測(cè)試數(shù)據(jù)及XML測(cè)試用例文件，自動(dòng)執(zhí)行測(cè)試用例并以XML的格式記錄測(cè)試結(jié)果。

關(guān)鍵詞： 自動(dòng)化測(cè)試； 遺傳算法； XML； 自動(dòng)生成； 自動(dòng)執(zhí)行

中圖分類號(hào)：TP311.5 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1006-8228（2018）02-67-04

Abstract： Because of its high efficiency and low cost， automated software testing technology has become an important research direction and development trend of software testing technology in recent years. This paper presents and implements a test case automatic generation and execution system， by using the genetic algorithm as the core test data generation method， it can automatically generate test data and the XML styled test case file， and automatically executes the test case and records the test results with XML format.

Key words： automatic testing； genetic algorithm； XML； automatic generation； automatic execution

0 引言

軟件測(cè)試是保證軟件質(zhì)量的重要手段。傳統(tǒng)的人工測(cè)試存在著成本高，效率低的缺點(diǎn)，所以自動(dòng)化測(cè)試技術(shù)就成為近年來(lái)軟件測(cè)試技術(shù)的重要研究方向與發(fā)展趨勢(shì)。自動(dòng)化測(cè)試技術(shù)能夠有效提高測(cè)試的質(zhì)量與效率，降低測(cè)試成本。

目前，自動(dòng)化測(cè)試技術(shù)的研究方向主要包括測(cè)試數(shù)據(jù)的自動(dòng)生成與測(cè)試用例自動(dòng)執(zhí)行兩個(gè)方面，但將這兩者結(jié)合的研究還較少。

本文提出并實(shí)現(xiàn)了一個(gè)測(cè)試用例自動(dòng)生成與執(zhí)行系統(tǒng)，能夠利用以遺傳算法為核心的測(cè)試數(shù)據(jù)生成方法自動(dòng)生成測(cè)試數(shù)據(jù)，然后生成基于XML（Extensible Markup Language）的測(cè)試用例文件，之后自動(dòng)執(zhí)行測(cè)試用例并以XML的格式記錄測(cè)試結(jié)果。

1 系統(tǒng)總體設(shè)計(jì)

本系統(tǒng)使用C#語(yǔ)言實(shí)現(xiàn)，采用XML描述與存儲(chǔ)測(cè)試過(guò)程中所需的各種數(shù)據(jù)，如測(cè)試配置、測(cè)試用例與測(cè)試結(jié)果。系統(tǒng)分為程序主界面、測(cè)試配置處理、測(cè)試數(shù)據(jù)自動(dòng)生成，測(cè)試用例處理，測(cè)試用例自動(dòng)執(zhí)行這五個(gè)模塊，系統(tǒng)數(shù)據(jù)流如圖1所示。

2 自動(dòng)生成測(cè)試數(shù)據(jù)

測(cè)試數(shù)據(jù)自動(dòng)生成模塊是系統(tǒng)的核心模塊，能自動(dòng)搜索并獲取一組測(cè)試數(shù)據(jù)，實(shí)現(xiàn)對(duì)被測(cè)函數(shù)的路徑覆蓋測(cè)試與邊界值測(cè)試。使用隨機(jī)法[1]自動(dòng)生成測(cè)試數(shù)據(jù)時(shí)間成本很低，但效率低下，很難搜索到特殊的測(cè)試數(shù)據(jù)，如三角形分類函數(shù)測(cè)試中三條邊相等，或日期計(jì)算函數(shù)測(cè)試中輸入日期為2000年2月29日的情況。近年來(lái)，不少研究者將遺傳算法引入了測(cè)試數(shù)據(jù)生成領(lǐng)域，并取得了良好的效果，如Jones B.F.[2]的實(shí)驗(yàn)表明，針對(duì)三角形分類函數(shù)，遺傳算法生成的測(cè)試數(shù)據(jù)數(shù)，要比隨機(jī)法小1～2個(gè)數(shù)量級(jí)。史亮[3]在博士論文中也對(duì)使用遺傳算法的測(cè)試數(shù)據(jù)自動(dòng)生成技術(shù)進(jìn)行了研究?；谶z傳算法收斂速度快、易于操作的優(yōu)點(diǎn)，本系統(tǒng)將其作為測(cè)試數(shù)據(jù)自動(dòng)生成方法的核心算法，并在此基礎(chǔ)上利用邊界值法生成一組測(cè)試數(shù)據(jù)作為補(bǔ)充。

2.1 使用遺傳算法生成實(shí)現(xiàn)路徑覆蓋的測(cè)試數(shù)據(jù)

遺傳算法（Genetic Algorithm）通過(guò)借鑒生物界中的自然選擇和自然遺傳機(jī)制，把可能的解編碼為一個(gè)向量（即染色體），并將若干個(gè)染色組成一個(gè)種群，模擬種群通過(guò)選擇、交叉及變異等機(jī)制進(jìn)行進(jìn)化的過(guò)程。該種群在每次迭代中都保留一組適應(yīng)度高的候選個(gè)體，通過(guò)若干代進(jìn)化之后，理想情況下其適應(yīng)度達(dá)到近似最優(yōu)的狀態(tài)。

2.1.1 選擇操作

選擇操作模擬了生物界優(yōu)勝劣汰的自然選擇現(xiàn)象，作用是從種群中選擇出一些染色體作為父本進(jìn)行遺傳操作，從而決定種群中哪些染色體的基因?qū)⒈贿z傳給子代。選擇的方法有輪盤(pán)賭法、精英法、混合法等。本系統(tǒng)同時(shí)提供了這3種方法，具體算法如下：

⑴ 輪盤(pán)賭法：其基本思想就是染色體被選中的概率與其適應(yīng)度的大小成正比，具體步驟為：①計(jì)算每個(gè)染色體的適應(yīng)度；②計(jì)算所有染色體適應(yīng)度之和；③計(jì)算每個(gè)染色體的選擇概率（即當(dāng)前染色體適應(yīng)度/所有染色體適應(yīng)度之和）；④計(jì)算所有染色體的累積選擇概率（即第一個(gè)染色體到當(dāng)前染色體的選擇概率之和）；⑤隨機(jī)生成一個(gè)[0，1]之間的數(shù)r，若r在染色體Ci的累積選擇概率區(qū)間內(nèi)，則將該染色體加入優(yōu)勝染色體集合中；⑥重復(fù)步驟；⑤M次（M為種群中的染色體個(gè)數(shù)）。

⑵ 精英法：其基本思想就是選取適應(yīng)度最高的一批染色體，具體步驟為：①將所有染色體按適應(yīng)度從高到低排列；②將前N個(gè)染色體加入優(yōu)勝染色體集合中。選取個(gè)數(shù)N=種群染色體總數(shù)×預(yù)設(shè)的存活率。

⑶ 混合法：結(jié)合了輪盤(pán)賭法與精英法思想。具體步驟為：①按照精英法，選取N個(gè)染色體；②剩余染色體按照輪盤(pán)賭法進(jìn)行選擇。

2.1.2 交叉操作

交叉操作模擬了生物界中的基因重組。交叉操作分為單點(diǎn)交叉法與多點(diǎn)交叉法。本系統(tǒng)采用單點(diǎn)交叉法，步驟如下：endprint

⑴ 在種群中隨機(jī)選擇兩個(gè)染色體，作為新一代染色體的父母；

⑵ 隨機(jī)生成一個(gè)范圍在[1，L-1]之間的整數(shù)，作為交叉位置，其中L為染色體長(zhǎng)度；

⑶ 父染色體與母染色體從交叉位置起，互換基因，得到新的子代染色體；

⑷ 重復(fù)步驟⑴M次，M為需要產(chǎn)生的子代染色體個(gè)數(shù)。

2.1.3 變異操作

變異操作以一定的概率改變?nèi)旧w中的某些基因，并產(chǎn)生新的染色體，以提供逃脫局部最小值的手段。本系統(tǒng)中，種群中染色體的變異概率可以由用戶設(shè)置（默認(rèn)為30%），若該染色體發(fā)生變異，則隨機(jī)抽取某位基因，并將該基因上的等位基因取反，即：從0變?yōu)?，或從1變?yōu)?。

2.1.4 使用遺傳算法生成實(shí)現(xiàn)路徑覆蓋的測(cè)試數(shù)據(jù)的具體步驟

系統(tǒng)利用遺傳算法生成實(shí)現(xiàn)路徑覆蓋測(cè)試的測(cè)試數(shù)據(jù)的具體步驟如下：

⑴ 對(duì)被測(cè)函數(shù)進(jìn)行插樁操作，即在保持原有邏輯結(jié)構(gòu)的基礎(chǔ)上在被測(cè)程序中加入檢查語(yǔ)句，使其能夠在測(cè)試時(shí)輸出程序執(zhí)行路徑；

⑵ 從用戶事先輸入的期望路徑集中選取本次搜索要覆蓋的期望路徑；

⑶ 根據(jù)預(yù)設(shè)的種群數(shù)量、染色體長(zhǎng)度、選擇策略、變異率、存活率、隨機(jī)選擇率等參數(shù)，隨機(jī)生成初始種群；

⑷ 選取當(dāng)前種群中適應(yīng)度最高的染色體，根據(jù)二進(jìn)制編碼[4]方式進(jìn)行解碼，解碼公式為，并將解碼后的值作為被測(cè)函數(shù)的輸入數(shù)據(jù)，得到程序執(zhí)行路徑。系統(tǒng)提供了路徑匹配法與節(jié)點(diǎn)匹配法這兩種適應(yīng)度計(jì)算方法，由用戶根據(jù)被測(cè)函數(shù)具體情況進(jìn)行選擇。其中路徑匹配法得到的適應(yīng)度為程序執(zhí)行路徑與期望路徑的最長(zhǎng)子串長(zhǎng)度，節(jié)點(diǎn)匹配法得到的適應(yīng)度為程序執(zhí)行路徑與期望路徑中相同的節(jié)點(diǎn)個(gè)數(shù)；

⑸ 若程序執(zhí)行路徑與期望路徑一致，則將測(cè)試數(shù)據(jù)加入測(cè)試數(shù)據(jù)集，停止進(jìn)化，回到步驟⑵；否則對(duì)種群進(jìn)行選擇、交叉與變異操作，并回到步驟⑷。其中的選擇操作可以是輪盤(pán)賭法、精英法或是混合法，由用戶根據(jù)數(shù)據(jù)搜索效率進(jìn)行選擇。

2.2 利用邊界值法生成實(shí)現(xiàn)邊界值測(cè)試的測(cè)試數(shù)據(jù)集

路徑覆蓋法只能對(duì)程序的邏輯結(jié)構(gòu)進(jìn)行測(cè)試，而不能有效地測(cè)試程序?qū)τ跀?shù)據(jù)邊界的處理是否正確，所以本系統(tǒng)使用邊界值法生成一組測(cè)試數(shù)據(jù)對(duì)其進(jìn)行補(bǔ)充，其基本思想是選取來(lái)自等價(jià)類的邊界的值，通常選取略小于最小值、最小值、略高于最小值、正常值、略低于最大值、最大值、略大于最大值這7個(gè)值。若輸入數(shù)據(jù)取值范圍為，則測(cè)試數(shù)據(jù)集（數(shù)據(jù)類型為整型，則μ=1，否則μ=0.1。若存在多個(gè)輸入數(shù)據(jù)，則在一個(gè)測(cè)試用例中只有一個(gè)輸入數(shù)據(jù)能取邊界值，其余輸入數(shù)據(jù)都必須取正常值，以便在程序未通過(guò)測(cè)試時(shí)分析導(dǎo)致錯(cuò)誤的原因。系統(tǒng)通過(guò)遍歷所有被測(cè)函數(shù)參數(shù)的上下界，并取得全部邊界值與正常值的組合，作為測(cè)試數(shù)據(jù)加入測(cè)試數(shù)據(jù)集中。

3 生成基于XML的測(cè)試用例文件

在得到測(cè)試數(shù)據(jù)集后，需要將測(cè)試數(shù)據(jù)轉(zhuǎn)換為計(jì)算機(jī)能夠自動(dòng)執(zhí)行的測(cè)試用例。傳統(tǒng)的測(cè)試用例存儲(chǔ)方式，如Word或Excel文檔等，存在描述不規(guī)范，文件較大，不便于計(jì)算機(jī)自動(dòng)處理等缺點(diǎn)。芮素娟[5]對(duì)基于XML的測(cè)試用例復(fù)用技術(shù)進(jìn)行了研究，表明XML具有層次化、擴(kuò)展性好、輕量，能夠進(jìn)行數(shù)據(jù)有效性驗(yàn)證、便于計(jì)算機(jī)處理等優(yōu)點(diǎn)。本系統(tǒng)采用XML來(lái)存儲(chǔ)測(cè)試用例與測(cè)試結(jié)果。

測(cè)試用例處理模塊利用.NET Framework中提供的XDocument類，將內(nèi)存中的測(cè)試套件對(duì)象（TestSuite）序列化為XML文件，每個(gè)測(cè)試套件元素中都包含測(cè)試套件名稱、被測(cè)函數(shù)名稱與一組測(cè)試用例子元素（TestCase）；每個(gè)測(cè)試用例元素又包含一組測(cè)試斷言（Assertion）子元素；每個(gè)測(cè)試斷言元素中又包含一組輸入數(shù)據(jù)、期望結(jié)果、實(shí)際結(jié)果與測(cè)試結(jié)果。使用XSD（XML Schema Definition）表示的測(cè)試用例文件結(jié)構(gòu)如圖2所示。

4 執(zhí)行測(cè)試用例并記錄測(cè)試結(jié)果

測(cè)試用例處理模塊生成測(cè)試用例文件后，需要用戶編輯該文件并在每個(gè)測(cè)試斷言的ExpectedOutput標(biāo)簽之間輸入該條測(cè)試數(shù)據(jù)對(duì)應(yīng)的期望結(jié)果。在用戶指定要執(zhí)行的測(cè)試用例文件后，測(cè)試用例自動(dòng)執(zhí)行模塊會(huì)將其反序列化為一個(gè)TestSuite對(duì)象，然后遍歷其中的所有的測(cè)試斷言，獲取測(cè)試數(shù)據(jù)，并調(diào)用被測(cè)函數(shù)得到實(shí)際輸出結(jié)果，并與斷言中的期望結(jié)果作比較，若一致，則將測(cè)試結(jié)果記為“Passed”，否則記為“Failed”。所有測(cè)試完成后，統(tǒng)計(jì)測(cè)試用例總數(shù)、通過(guò)數(shù)與未通過(guò)數(shù)，并記錄到測(cè)試用例文件中。測(cè)試用例文件結(jié)構(gòu)如圖3所示。

5 結(jié)束語(yǔ)

本系統(tǒng)能夠通過(guò)遺傳算法高效地獲取實(shí)現(xiàn)路徑覆蓋的測(cè)試數(shù)據(jù)，尤其是在輸入數(shù)據(jù)取值范圍很大的情況下，能夠搜索到使用隨機(jī)法很難搜索到的測(cè)試數(shù)據(jù)，且搜索速度有較大提高。在此基礎(chǔ)上，還能通過(guò)邊界值法生成一組補(bǔ)充測(cè)試數(shù)據(jù)，進(jìn)一步提高測(cè)試的質(zhì)量。除此之外，系統(tǒng)利用XML描述并存儲(chǔ)測(cè)試用例與測(cè)試結(jié)果，提高了程序的擴(kuò)展性，且便于計(jì)算機(jī)自動(dòng)處理。今后系統(tǒng)可以從兩個(gè)方面改進(jìn)：①引入控制流分析功能，實(shí)現(xiàn)被測(cè)函數(shù)插樁操作自動(dòng)化；②采用自適應(yīng)遺傳算法，動(dòng)態(tài)地改變各種參數(shù)，進(jìn)一步提高測(cè)試數(shù)據(jù)查找效率。

參考文獻(xiàn)（References）：

[1] Bird D. L.， C. U. Munoz. Automatic Generation of andom Self-Checking Test Cases[J].IBM Systems Journal，1983.22（3）：229-245

[2] Jones B. F.， Eyres D. E.， Sthamer H. H.A Strategy for sing Genetic Algorithms to Automate Branch and Fault-Based Testing[J]. The Computer Journal，1998.41（2）：98-107

[3] 史亮.測(cè)試數(shù)據(jù)自動(dòng)生成技術(shù)研究[D].東南大學(xué)博士學(xué)位論文，2006.

[4] 吉根林.遺傳算法研究綜述[J].計(jì)算機(jī)應(yīng)用與軟件，2004.2：69-73

[5] 芮素娟.基于XML的測(cè)試用例復(fù)用研究[D].西南大學(xué)碩士學(xué)位論文，2006.endprint