一種面向路徑覆蓋的測(cè)試用例進(jìn)化生成方法

范書(shū)平 劉志宇 楊禹軍 李明 馬寶英 高晨光 朱旭東 王雪艷 李瑩 李力力 樊俊杰

摘 要：提出一種測(cè)試用例生成方法.針對(duì)穿越程序各節(jié)點(diǎn)間測(cè)試用例數(shù)目的不等性，引入測(cè)試用例穿越程序后流量均衡性的概念，給出節(jié)點(diǎn)間流量均衡因子的定義及計(jì)算過(guò)程，并根據(jù)個(gè)體加入前后流量均衡性，設(shè)置遺傳算法的適應(yīng)值函數(shù)，以快速進(jìn)化生成覆蓋目標(biāo)路徑的測(cè)試用例.

關(guān)鍵詞：路徑覆蓋;測(cè)試用例生成;遺傳算法

[中圖分類(lèi)號(hào)]TP301 ? [文獻(xiàn)標(biāo)志碼]A

Abstract：Aiming at the unequal number of test cases that traversing the nodes of program， the concept of flow balance is introduced， and the definition and calculation process of flow equilibrium factor between nodes are given. Finally， according to the flow balance before and after individual joining， the fitness function of Genetic Algorithms is set up. So the test cases covering the target path can be generated by rapid evolution.

Key words：path coverage;test case generation;genetic algorithms

測(cè)試是軟件開(kāi)發(fā)生命周期中關(guān)鍵而又昂貴的組成部分，軟件測(cè)試的目標(biāo)是通過(guò)一個(gè)潛在的測(cè)試數(shù)據(jù)集盡可能多地揭露缺陷.自動(dòng)化軟件測(cè)試可以有效減少測(cè)試代價(jià)并獲得可信的結(jié)果[1]，其基本前提是自動(dòng)生成測(cè)試數(shù)據(jù).近些年，許多學(xué)者應(yīng)用進(jìn)化算法[2]來(lái)生成滿足指定覆蓋準(zhǔn)則的測(cè)試數(shù)據(jù).遺傳算法是常用的進(jìn)化算法之一，該算法具有較強(qiáng)的優(yōu)化能力，當(dāng)使用遺傳算法生成滿足特定覆蓋標(biāo)準(zhǔn)的測(cè)試數(shù)據(jù)時(shí)，首先會(huì)執(zhí)行一些隨機(jī)產(chǎn)生的測(cè)試數(shù)據(jù)，之后依據(jù)適應(yīng)值函數(shù)評(píng)價(jià)數(shù)據(jù)的優(yōu)劣，在搜索機(jī)制的作用下，更加接近目標(biāo)的測(cè)試數(shù)據(jù)將被不斷生成，直到滿足需求為止.[3-5]

本文提出一種面向路徑覆蓋的測(cè)試用例進(jìn)化生成方法，通過(guò)設(shè)置適應(yīng)值函數(shù)，應(yīng)用遺傳算法進(jìn)化生成測(cè)試數(shù)據(jù)，目的是實(shí)現(xiàn)測(cè)試的充分性，快速達(dá)到路徑覆蓋率，提高軟件測(cè)試的效率.研究主要包括兩方面：負(fù)載均衡以及基于流量均衡的測(cè)試用例生成方法.

1 負(fù)載均衡和測(cè)試用例進(jìn)化生成方法

負(fù)載均衡作為一種策略，能夠讓多臺(tái)服務(wù)器或多條鏈路共同承擔(dān)繁重的計(jì)算或大吞吐量工作，從而以較低成本消除網(wǎng)絡(luò)瓶頸，提高網(wǎng)絡(luò)的靈活性和可靠性.針對(duì)網(wǎng)絡(luò)通信不暢的問(wèn)題，負(fù)載均衡技術(shù)已廣泛應(yīng)用于計(jì)算機(jī)網(wǎng)絡(luò)中.[6-8]針對(duì)無(wú)線傳感器網(wǎng)絡(luò)的負(fù)載均衡問(wèn)題，宋寧博[9]等人在HEED的基礎(chǔ)上，通過(guò)改進(jìn)簇問(wèn)路由協(xié)議提出了一種網(wǎng)絡(luò)負(fù)載均衡路由算法.解文斌[10]等人提出一種基于等概率路由模型的傳感器網(wǎng)絡(luò)負(fù)載均衡方法.張健[11]等人提出一種基于多目標(biāo)優(yōu)化函數(shù)的無(wú)線傳感器網(wǎng)絡(luò)負(fù)載均衡路由協(xié)議，協(xié)議中將節(jié)點(diǎn)可用能量、節(jié)點(diǎn)之間的物理距離以及路由跳數(shù)等參數(shù)引入到路由選擇函數(shù)中.負(fù)載均衡應(yīng)用在測(cè)試用例生成中還沒(méi)有比較成熟的研究成果.

應(yīng)用遺傳算法生成測(cè)試數(shù)據(jù)方面已有很多成果.張巖[12]提出的測(cè)試數(shù)據(jù)生成方法中，引入了精英學(xué)習(xí)的概念，加快了遺傳算法的求解速度，提高了目標(biāo)測(cè)試數(shù)據(jù)的生成效率.Gong[13]等人提出的測(cè)試數(shù)據(jù)生成方法中，適應(yīng)值函數(shù)僅考慮個(gè)體穿越路徑與目標(biāo)路徑從前至后連續(xù)相同節(jié)點(diǎn)的個(gè)數(shù).謝曉園[14]等人提出用相同節(jié)點(diǎn)個(gè)數(shù)表示測(cè)試數(shù)據(jù)穿越路徑與目標(biāo)路徑的相似程度，并給出三種相似度的計(jì)算方法，這兩種方法在本質(zhì)上給出了表示層接近度的新方法.應(yīng)用遺傳算法進(jìn)化種群測(cè)試用例生成方法的最終目標(biāo)是生成覆蓋目標(biāo)路徑的用例，當(dāng)找到穿越全部目標(biāo)路徑的測(cè)試數(shù)據(jù)或者達(dá)到條件時(shí)就終止了遺傳算法.實(shí)際在測(cè)試用例生成時(shí)，除了考慮目標(biāo)路徑的覆蓋情況，還要考慮所生成測(cè)試用例的有效性與測(cè)試代價(jià).鑒于此，本文提出在測(cè)試用例生成時(shí)，考慮流量均衡性，以快速生成覆蓋目標(biāo)路徑的測(cè)試用例.

2 程序的流量均衡性2.1 控制流圖

控制流圖是一個(gè)有向圖，見(jiàn)圖1.圖1（a）是一個(gè)源程序，圖1（b）是圖1（a）中源程序所對(duì)應(yīng)的控制流圖.

2.2 流量均衡的相關(guān)定義

定義1 在控制流圖中，節(jié)點(diǎn)nj稱(chēng)為節(jié)點(diǎn)ni的直接后繼節(jié)點(diǎn)，當(dāng)且僅當(dāng)：nj是ni的直接后繼模塊，nj控制依賴(lài)于ni，記為njni .如圖1中的節(jié)點(diǎn)n2和n3是節(jié)點(diǎn)n1的直接后繼節(jié)點(diǎn).

定義2 分叉節(jié)點(diǎn).記NUM（i）為節(jié)點(diǎn)ni的直接后繼節(jié)點(diǎn)數(shù)目，若NUM（i）>1，則稱(chēng)節(jié)點(diǎn)ni為分叉節(jié)點(diǎn).如圖1中的節(jié)點(diǎn)n1和n5，均為分叉節(jié)點(diǎn).

定義3 節(jié)點(diǎn)ni的流量用Tij表示，指種群中個(gè)體運(yùn)行程序后穿越節(jié)點(diǎn)ni上的第j個(gè)后繼節(jié)點(diǎn)的測(cè)試用例數(shù)目.

定義4 流量均衡因子.根據(jù)圖1所示的程序及控制流圖不難看出，對(duì)于復(fù)雜的計(jì)算機(jī)程序，容易穿越的節(jié)點(diǎn)將有大量的測(cè)試用例通過(guò)，而難覆蓋的節(jié)點(diǎn)有很少甚至根本沒(méi)有測(cè)試用例通過(guò)，這會(huì)導(dǎo)致前一種情況會(huì)有大量冗余的測(cè)試用例產(chǎn)生.因此，研究節(jié)點(diǎn)間流量均衡性，使得生成的測(cè)試用例向穿越難以覆蓋的節(jié)點(diǎn)進(jìn)化.

（1）節(jié)點(diǎn)間流量均衡因子及其計(jì)算方法

4 結(jié)語(yǔ)

本文提出一種面向路徑覆蓋的測(cè)試用例進(jìn)化生成方法，方法中考慮了穿越節(jié)點(diǎn)間的測(cè)試用例均衡性，并定義了流量均衡因子，給出計(jì)算過(guò)程，通過(guò)設(shè)置遺傳算法的適應(yīng)值函數(shù)，優(yōu)先保留改善流量均衡性的個(gè)體，以更快地生成覆蓋目標(biāo)路徑的測(cè)試數(shù)據(jù).

參考文獻(xiàn)

[1]Mansour N，Salame M.Data generation for path testing[J].Softw.Qual.Control，2004，12 （2）：121-136.

[2]張功杰，謝春麗.面向測(cè)試用例生成的集合進(jìn)化算法實(shí)現(xiàn)[J].牡丹江師范學(xué)院學(xué)報(bào)：自然科學(xué)版，2017（2）：1-5.

[3]周明，孫樹(shù)棟.遺傳算法原理及應(yīng)用[M].北京：國(guó)防工業(yè)出版社，2002.1-20.

[4]Sofokleous A A，Andreou A S.Automatic，evolutionary test data generation for dynamic software testing[J].Systems and Software，2008，81（11）：1883-1898.

[5]Kristof Bohmer，Stefanie Rinderle-Ma.A Genetic Algorithm for Automatic Business Process Test Case Selection[J].OTM conferences，2015，166-184.

[6]劉彩霞.集群網(wǎng)絡(luò)負(fù)載均衡技術(shù)分析及實(shí)現(xiàn)[J].內(nèi)蒙古大學(xué)學(xué)報(bào)：自然科學(xué)版，2005，36（5）：555-559.

[7]秦光.多路徑路由網(wǎng)絡(luò)負(fù)載均衡算法研究[J].計(jì)算機(jī)仿真，2011，28（11）：118-121.

[8]趙東，韓曉艷，趙宏偉，等.基于分類(lèi)優(yōu)化的物聯(lián)網(wǎng)節(jié)點(diǎn)負(fù)載均衡策略[J].吉林大學(xué)學(xué)報(bào)：工學(xué)版，45（3），2015：926-931.

[9]宋寧博，范敏，王玲.基于HEED的無(wú)線傳感器網(wǎng)絡(luò)負(fù)載均衡路由算法[J].計(jì)算機(jī)工程與應(yīng)用.2015，51（11），83-87.

[10]解文斌，鮮明，陳永光.基于等概率路由模型的傳感器網(wǎng)絡(luò)負(fù)載均衡研究[J].電子與信息學(xué)報(bào)：32（5），2010：1205-1211.

[11]張健.基于多目標(biāo)優(yōu)化函數(shù)的無(wú)線傳感器網(wǎng)絡(luò)負(fù)載均衡路由協(xié)議[J].安慶師范學(xué)院學(xué)報(bào)：自然科學(xué)版，2015，21（4）：33-36.

[12]張巖.基于精英學(xué)習(xí)的多路徑覆蓋測(cè)試數(shù)據(jù)進(jìn)化生成[J].牡丹江師范學(xué)院學(xué)報(bào)：自然科學(xué)版，2012（4），20-22.

[13]Gong D W，Zhang W Q，Zhang Y. Evolutionary generation of test data for multiple paths coverage[J].Chinese Journal of Electronics，2011，19（2）：233-237.

[14] 謝曉園，徐寶文，史亮，等.面向路徑覆蓋的演化測(cè)試用例生成技術(shù)[J].軟件學(xué)報(bào)，2009，20 （12），3117-3136.