一種面向路徑覆蓋的測試用例進化生成方法

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

摘 要：提出一種測試用例生成方法.針對穿越程序各節點間測試用例數目的不等性，引入測試用例穿越程序后流量均衡性的概念，給出節點間流量均衡因子的定義及計算過程，并根據個體加入前后流量均衡性，設置遺傳算法的適應值函數，以快速進化生成覆蓋目標路徑的測試用例.

關鍵詞：路徑覆蓋;測試用例生成;遺傳算法

[中圖分類號]TP301 ? [文獻標志碼]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

測試是軟件開發生命周期中關鍵而又昂貴的組成部分，軟件測試的目標是通過一個潛在的測試數據集盡可能多地揭露缺陷.自動化軟件測試可以有效減少測試代價并獲得可信的結果[1]，其基本前提是自動生成測試數據.近些年，許多學者應用進化算法[2]來生成滿足指定覆蓋準則的測試數據.遺傳算法是常用的進化算法之一，該算法具有較強的優化能力，當使用遺傳算法生成滿足特定覆蓋標準的測試數據時，首先會執行一些隨機產生的測試數據，之后依據適應值函數評價數據的優劣，在搜索機制的作用下，更加接近目標的測試數據將被不斷生成，直到滿足需求為止.[3-5]

本文提出一種面向路徑覆蓋的測試用例進化生成方法，通過設置適應值函數，應用遺傳算法進化生成測試數據，目的是實現測試的充分性，快速達到路徑覆蓋率，提高軟件測試的效率.研究主要包括兩方面：負載均衡以及基于流量均衡的測試用例生成方法.

1 負載均衡和測試用例進化生成方法

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

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

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

控制流圖是一個有向圖，見圖1.圖1（a）是一個源程序，圖1（b）是圖1（a）中源程序所對應的控制流圖.

2.2 流量均衡的相關定義

定義1 在控制流圖中，節點nj稱為節點ni的直接后繼節點，當且僅當：nj是ni的直接后繼模塊，nj控制依賴于ni，記為njni .如圖1中的節點n2和n3是節點n1的直接后繼節點.

定義2 分叉節點.記NUM（i）為節點ni的直接后繼節點數目，若NUM（i）>1，則稱節點ni為分叉節點.如圖1中的節點n1和n5，均為分叉節點.

定義3 節點ni的流量用Tij表示，指種群中個體運行程序后穿越節點ni上的第j個后繼節點的測試用例數目.

定義4 流量均衡因子.根據圖1所示的程序及控制流圖不難看出，對于復雜的計算機程序，容易穿越的節點將有大量的測試用例通過，而難覆蓋的節點有很少甚至根本沒有測試用例通過，這會導致前一種情況會有大量冗余的測試用例產生.因此，研究節點間流量均衡性，使得生成的測試用例向穿越難以覆蓋的節點進化.

（1）節點間流量均衡因子及其計算方法

4 結語

本文提出一種面向路徑覆蓋的測試用例進化生成方法，方法中考慮了穿越節點間的測試用例均衡性，并定義了流量均衡因子，給出計算過程，通過設置遺傳算法的適應值函數，優先保留改善流量均衡性的個體，以更快地生成覆蓋目標路徑的測試數據.

參考文獻

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

[2]張功杰，謝春麗.面向測試用例生成的集合進化算法實現[J].牡丹江師范學院學報：自然科學版，2017（2）：1-5.

[3]周明，孫樹棟.遺傳算法原理及應用[M].北京：國防工業出版社，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]劉彩霞.集群網絡負載均衡技術分析及實現[J].內蒙古大學學報：自然科學版，2005，36（5）：555-559.

[7]秦光.多路徑路由網絡負載均衡算法研究[J].計算機仿真，2011，28（11）：118-121.

[8]趙東，韓曉艷，趙宏偉，等.基于分類優化的物聯網節點負載均衡策略[J].吉林大學學報：工學版，45（3），2015：926-931.

[9]宋寧博，范敏，王玲.基于HEED的無線傳感器網絡負載均衡路由算法[J].計算機工程與應用.2015，51（11），83-87.

[10]解文斌，鮮明，陳永光.基于等概率路由模型的傳感器網絡負載均衡研究[J].電子與信息學報：32（5），2010：1205-1211.

[11]張健.基于多目標優化函數的無線傳感器網絡負載均衡路由協議[J].安慶師范學院學報：自然科學版，2015，21（4）：33-36.

[12]張巖.基于精英學習的多路徑覆蓋測試數據進化生成[J].牡丹江師范學院學報：自然科學版，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] 謝曉園，徐寶文，史亮，等.面向路徑覆蓋的演化測試用例生成技術[J].軟件學報，2009，20 （12），3117-3136.