基于遺傳算法的軟件業務流程測試路徑的研究

夏良 商偉 王兆星

摘 ?要： 近些年隨著軟件行業的迅速興起，軟件產品已經滲透到日常生活中的各個角落。作為軟件生命周期中重要階段的軟件測試，對軟件行業的發展有著十分重要的意義。對于軟件測試來講，測試質量是核心，測試效率是保證，一個好的測試過程就是要在保證軟件質量的基礎上盡可能提高軟件測試的效率。本文重點針對軟件系統級測試，基于遺傳算法對選取個體適應因素進行調整，達到保留必須存在的測試路徑，減少重復冗余測試路徑的目的，進而實現對測試路徑的自動選擇。

關鍵詞： 計算機軟件;業務流程測試;測試路徑選取;遺傳算法

中圖分類號： TP311.5 ? ?文獻標識碼： A ? ?DOI：10.3969/j.issn.1003-6970.2019.04.029

本文著錄格式：夏良，商偉，王兆星. 基于遺傳算法的軟件業務流程測試路徑的研究[J]. 軟件，2019，40（4）：133139

【Abstract】： Nowadays， as the software industry promptly developing， the software products have penetrated every area in our daily life. Software testing which is a significant period in the software life cycle， has a very important effect on the software industry. From the point of software testing， the testing quality is the core， and the testing efficiency is the guarantee. A good testing process is to improve the testing efficiency as much as possible on the basis of ensuring the testing quality.

This paper focus on the system software testing， adjust the selection of the individual fitness function based on genetic algorithm， to reserve the testing path which is imperative， and to reduce the redundancy of it， and eventually to realize the testing path automatically generation.

【Key words】： Computer software; Business Process Testing; Testing path selection; Genetic algorithm

0 ?引言

隨著信息科學技術的發展，計算機技術及其產物“軟件產品”已在各行各業中得到廣泛應用，軟件產品已成為人們日常工作和生活的必須品，而保證軟件質量已成為近年來軟件領域的一個重要話題。軟件中的一些缺陷將極有可能直接導致軟件失效，尤其在一些用戶量大或者安全系數高的關鍵領域（比如軍隊安防、核電控制、證券金融和銀行交易等），甚至可能造成災難[1]。

軟件測試就是保證軟件產品質量的有效活動之一。軟件測試會選取一些具有代表性的操作或數據，并將其組成測試用例，通過在被測程序上使用這些操作和數據，得到被測程序的實際反饋信息，再使用其與期望結果進行比較，最終得到被測程序是否滿足期望的結論。軟件測試有很多重要環節，其中測試數據的使用就是其中之一。一個有效的測試數據選擇方法可以實現對測試數據的精簡，減少大量重復或者無效的測試工作，這樣就可以在有限的條件下明確測試目標、擴大覆蓋規模，最終達到提高效率、節約成本的目的。研究表明，測試數據的選取直接影響了測試工作的效果，在一定程度上關乎整個軟件研發工作的進程[2]。

本文結合筆者實際測試工作，給出了一種個體適應度的計算方法，并依此給出了一種基于遺傳算法的測試路徑優選算法，該算法可以優化測試路徑的選取，減少冗余的測試用例，進而提高了測試效率，同時也對與流程測試路徑選取相關的研究提供了參考[3-10]。

1 ?業務流程測試

1.1 ?實驗材料

業務流程測試是指，針對用戶實際的使用場景，將系統中各相關的功能模塊或者配置項串聯起來，通過連貫的操作驅動系統中的數據進行一系列的變化，比對中間數據結果和最終數據結果來驗證被測系統是否滿足用戶需求的過程。業務流程測試是系統級測試中重要的測試環節，通過業務流程測試，可以有效降低軟件系統在交付后出現問題的幾率，減少后期維護成本，提高系統運行的穩定性[11-15]。

1.2 ?使用基本流圖表示業務流程路徑

在進行業務流程測試時，為了清晰的展現所有可能存在的業務流程路徑，通常需要根據實際的使用場景繪制流程圖，再將流程圖中的每個操作使用唯一的編號進行標識，進而繪制出便于識別每一條流程路徑的基本流圖。流程圖和基本流圖的示例如圖1所示。

1.3 ?獨立路徑的識別

對于一般的業務流程來講，僅需對每個判斷、每個分支以及任意兩節點之間的有向線段進行覆蓋，即可達到測試的目的。這種覆蓋方式就是“獨立路徑覆蓋”，而識別獨立路徑最簡單的方式就是在已覆蓋所有有向線段的基礎上，增加一條尚未覆蓋的新有向線段。假設某軟件系統中存在一系列的操作流程，對其進行分析形成的基本流圖如圖2所示。

這里可以明顯看出每天獨立路徑都是在其他已知路徑的基礎上，增加了一條未被識別的新有向線段。通過使用對獨立路徑覆蓋的方法，可以較為快速的找出所有需要覆蓋的測試路徑，在測試時間有限的情況下，盡可能的保證測試到更多的路徑。

2 ?遺傳算法

2.1 ?基本概念

遺傳算法的思想來源于達爾文生物進化理論，以“物競天擇”的概念模擬了自然界中生物的進化過程，對搜索空間進行自動優化，對搜索方向進行自動調整。

遺傳算法是一種全局搜索算法，重點強調種群中個體的適應度，通過適者生存的概念，自動完成對問題的求解。它僅從適應度這一個方面對種群中的個體進行評估，不受其他條件和因素的制約，這使得其在當今各領域中得到了十分廣泛的應用，尤其在信號處理、自動控制選擇等專業領域發揮了不小的作用[16-20]。

2.2 ?遺傳算法一般過程

遺傳操作在遺傳算法中是非常關鍵的，其目標就是根據個體對環境的適應度而施加一定的影響，從而實現對優良個體的保留和傳遞，通過這樣不斷的迭代和優化，最終達到進化的目的。

適應度函數又稱評價函數，它表示種群中的某個體對環境的適應能力，通過適應度函數可以直接評價某個體的優劣，以及其是否可以繁衍下一代。因為遺傳算法在整個搜索過程中僅使用適應度函數來評價個體的優劣程度，所以對于適應函數的設計就顯得非常重要，必須要在對問題進行充分分析和了解的基礎上，才能設計出適合的適應度函數。遺傳算法一般過程如圖3所示[21-25]。

3 ?基于遺傳算法的測試路徑選擇算法

3.1 ?使用基本流圖表示測試路徑

在基本流圖中，通過分支直接形成了不同的獨立路徑，分支越多則最終形成的獨立路徑就會越多。這里使用P（Path）表示路徑，n（node）表示節點，ns表示起始節點，ne表示終節點，L（line）表示相鄰兩節點之間的有向線段，通過節點的形式可表現為ni-nt。

下面用上文提到過的一個示例圖2進行詳細說明。為了不改變原圖中各節點編號，直接將1作為起始節點s，11作為終結點e，變化后的基本流圖如圖4所示。

3.2 ?路徑重復度計算

基于遺傳算法測試路徑選擇的技術難點在于確定每條路徑的適應度。對于測試路徑的選取來講，個體適應度的高低主要體現在“重復度”上。測試路徑的重復度越高，則說明這條路徑越接近已經被探索過的路徑;反之重復度越低，則說明這是一條新的、未被發現的路徑。那么選擇一個合理的重復度的計算方法對于本次研究來講就是一個比較重要的事情了。本文借鑒了前人的研究成果，采用了分段比較的方法，來確定測試路徑的重復度。

對于其中一條路徑Pt={ns-n1-n2……-nt-ne}，可以從第一個節點開始，依次向下取出長度為定值m的每條子路徑，第一條子路徑從ns開始直到nm結束，第二條子路徑從n1開始直到nm+1結束……這樣以此類推，每條子路徑都是在前一條的基礎上移出第一個節點再引入一個新的后續節點。這樣就有了路徑集合：

通過上面的方法就可以比較容易找出重復度較低的測試路徑。基于遺傳算法的測試路徑選擇中，可以使用對比已有路徑和新路徑的重復度的方法確定個體的適應度。兩條路徑上經過的相同節點越多，則說明這兩條路徑越接近，反之則說明兩條路徑之間的差別越大。在對個體適應度進行判斷時，個體重復度越高，則說明其與已有路徑越接近，個體適應度就越低，應該被淘汰;而重復度越低的，適應度就會越高，應該被保留[26-31]。

3.3 ?子路徑權值

在對測試路徑進行覆蓋時，通常會使用深度優先和廣度優先兩種方法。一般情況下，分支出現的越早，之后的兩條路徑差距越大，所以從某個方面來講，在測試時間有限的情況下，廣度優先的方法更優于深度優先的方法，它更容易選出多條差距較大的測試路徑。

可以借助為子路徑設置權值的思想來實現廣度優先，在子路徑集中，越靠前的子路徑其優先級就應該設定得越高，越靠后的則越低。這里使用前文中重復度計算的例子進行說明。

使用等比權值得到的結果與使用等差權值得到結果差距不大，且都與基本流圖的直觀感受基本一致，所以這兩種方法都可以使用，而且最終的結果差距不大，都可以滿足實際使用時的需要。

等差權值的優點在于計算精確，當出現重復的路徑時可以保證重復度剛好為1，其缺點在于對不同路徑的子路徑權值不同，每次進行比較的時候需要先確定權值才能進行比較;而等比權值對于所有路徑均是一樣的，使用起來比較方便，但如果路徑很短時，重復度結果就與1偏離較大。所以對于存在多分支的復雜流程來說，推薦使用等比權值，而簡單的流程推薦使用等差權值。

3.4 ?個體適應度計算

基于遺傳算法的測試路徑選取算法的核心在于如何確定個體適應度，確定一個合適的計算函數對個體適應度的計算以及搜索算法的效果都有著直接的影響。對于測試路徑的覆蓋問題來說，測試人員最不希望的進行的工作就是對同一條路徑進行反復的測試，但對于比較復雜的流程來講，通過人工選取的方式很難做到避免的冗余，所以本文中采用了計算測試路徑重復度的方法來輔助計算個體適應度。

在對個體重復度的計算方法和計算結果進行分析后，可以很容易的發現，重復度函數是一條值域在[0，1]之間的單調遞增的函數，這樣在計算個體適應度時，就可以通過最簡單的線性函數y=1f（x）來完成個體測試路徑適應度的計算。

前文中得出的mP1與mP2的重復度為：0.9（等差數列形式計算），所以mP2的適應度就應該為：10.9=0.1。類似的mP3的適應度為10.5=0.5。很明顯0.5>0.1，說明mP3的適應度要高于mP2的適應度，在選取時應該保留mP3淘汰mP2。將重復度計算函數帶入y=1f（x）中得出個體測試路徑的適應度公式。

子路徑權值成等差數列時，個體測試路徑的適應度

其中nPi是兩條路徑中各子路徑的重復程度，m為子路徑數量（如果相比較的兩條路徑的子路徑條數不一樣，則取較短的一條的子路徑個數），i是自然數[1， n]。

子路徑權值成等比數列時，個體測試路徑的適應度

其中nPi是兩條路徑中各子路徑的重復程度，m為子路徑數量（如果相比較的兩條路徑的子路徑條數不一樣，則取較短的一條的子路徑個數），i是自然數[1， n]。

從公式上看，當子路徑權值成等比數列時，公式更為簡單，對于比較復雜的測試路徑選取更加合適，這也再一次印證了上文中所說的對于存在多分支的復雜流程來說，推薦使用等比權值，而簡單的流程推薦使用等差權值。因為兩種方法計算出的適應度結果差距不大。

3.5 ?基于遺傳算法的測試路徑選擇

在選擇一條新的測試路徑時，需要分別對備選新路徑與每條已有路徑的適應度進行計算，并Min（SPi）的方式得出每條備選新路徑對已有多條路徑的多路徑適應度。

3.6 ?基于遺傳算法的測試路徑選取步驟

不管是通過人工方式還是基于某種算法測試路徑進行選取時，都必須認真分析現有業務需求和邏輯操作流程。在正確繪制業務流程圖、基本流圖之后才可以進行測試路徑的選取。基于遺傳算法的測試路徑選取步驟如下：

（1）首先要找到基本流圖中包含的所有的有向線段集合LS。

（2）再要確定第一條分支路徑，將該路徑直接加入測試路徑解集中，并將該路徑中包含的所有向線段在有向線段集合LS中刪除。確定該路徑的方法很簡單，僅需要識別出基本流圖中一條最短的路徑即可。如果發現存在多條最短路徑，則將其全部納入解集中。

（3）選取其他新的測試路徑并進行篩選，如果路徑中未包含當前有向線段集合LS中的元素時，則直接將其刪除;如果路徑中包含了有向線段集合LS中的元素時，則保留這些測試路徑并使用這些測試路徑與已有路徑解集中的測試路徑逐一進行重復度比較，得出單路徑的多個適應度值，并使用最值的方式得到每條新測試路徑的適應度。

（4）從所有適應度中選取適應度最高的一條測試路徑作為本次選擇的最優解并納入到解集中，同時刪除LS中對應的元素。如果出現適應度相同的多條路徑，則取路徑長度較短的一條，如果路徑長度也相同則取第一條。

（5）重復執行3-4兩個步驟，直到LS中沒有元素為止，此時所有的測試路徑已經全部被覆蓋，這樣就在測試路徑的解集中得到了全部的測試路徑。

4 ?結論

如今的測試技術和測試方法較之前相比已經有了很大的進步，單純的功能測試已經遠遠不能滿足當今軟件測試行業的發展需要，越來越多的時間和資源將被用于系統級的測試中。而且人們對于測試技術的追求也不斷提高，降低測試設計的復雜度已經成為了目前迫切需要解決的問題。目前對于路徑測試方面的測試技術和研究成果還比較有限，本文在現有研究成果的基礎上進行了深入的學習和研究，給出了一種新的更加適合實際測試工作需要的基于遺傳算法的軟件業務流程測試用例選取算法。對于流程測試路徑選取提供了參考，對于自動化測試在系統業務流程測試用的應用起到了指導作用。

參考文獻

[1] 顏樂鳴. 基于工作流的軟件測試過程模型研究[J]. 軟件， 2018， 39（5）： 160-165

[2] 翁秀木. 一個通用的軟件質量評估指標體系[J]. 軟件， 2015， 36（3）： 59-63

[3] 楊勛姮， 段明璐. 軟件缺陷分析技術的研究[J]. 軟件， 2018， 39（2）： 93-101

[4] 葉常春， 尹良澤. 面向小規模程序的輕型測試方法[J].軟件， 2015， 36（10）： 90-93

[5] 楊子健， 趙逢禹. 基于數據流約簡的測試用例生成策略研究[J]. 軟件， 2018， 39（4）： 191-195

[6] Huang C Y， Software reliability modeling and cost estimation incorporating testing-effort and efficiency[J]. Software Reliability Engineering， 1999， 22（4）： 62-72

[7] 朱少民. 軟件測試方法和技術[M]. 北京： 清華大學出版社， 2005

[8] Nirmal Kumar Gupta， Dr.Mukesh Kumar Rohil. Using Genetic Algorithm for Unit Testing of Object Oriented Software[C] ICETET 08， NewYorK， 2008： 308-313

[9] Glen.Myers著， 王峰， 陳杰譯. 軟件測試的藝術[M]. 北京： 機械工業出版社， 2006.

[10] Susan Khor， Peter Grogono. Using a Genetic Algorithm and Formal Concept Analysis to Generate Branch Coverage Test Data Automactically[J]. Proceeding of the 19th IEEE international conference on Automated software engineering： 346-349.

[11] Dr. Velur Rajappa， Arun Biradar， Satanik Panda. Efficient Software Test Case Generation Using Genetic Algorithms Based Graph Theory[J]. First International Conference on Emerging Trends in Engineering and Technology， ICETET 08， 2008： 298-303.

[12] 董敏， 畢盛， 齊德昱. 基于正則表達式的測試數據自動生成技術[J]. 計算機工程， 2009， 35（16）： 29-31.

[13] 付博. 基于模擬退火遺傳算法的軟件測試數據自動生成. 計算機工程與應用. 2005， 12： 82-84.

[14] 王溪波， 馬春， 杜曉舟. 面向路徑的測定數據自動生成工具設計與實現[J]. 沈陽航空工業學院學報， 2009， 26（3）： 54-59.

[15] 夏蕓， 劉峰. 基于免疫遺傳算法的路徑測試數據生成的研究[J]. 計算機應用， 2008， 28（3）： 723-725.

[16] 周澤巖， 張喜. 基于改進遺傳算法的TSP問題求解的研究. 物流技術， 2012（17）： 220-223.

[17] 張海藩. 軟件工程導論[M]. 第三版. 北京： 清華大學出版社， 2000.139-143.

[18] 鞏敦衛， 張巖. 一種新的多路徑覆蓋測試數據進化生成方法[J]. 電子學報， 2010（6）： 1300-1301.

[19] 張巖， 鞏敦衛. 基于搜索空間自動縮減的路徑覆蓋測試數據進化生成[J]. 電子學報， 2012， 40（5）： 1011-1016.

[20] 魏銳， 王海榮. 軟件測試數據自動生成方法研究. 電子設計工程， 2013（21）： 5-7.

[21] 曹洋， 胡春華， 陳少波， 李路明. 一種路徑測試數據自動生成方法. 計算機工程， 2011（9）： 25-28.

[22] 崔麗婷， 雷斌. 改進的遺傳算法及其在測試數據自動生成中的應用. 信息技術與信息化， 2013（4）： 110-115.

[23] 于遠誠， 潘洪軍， 李春秋. 遺傳算法在軟件測試中的應用. 浙江海洋學院學報， 2013（2）： 149-154.

[24] 史嬌嬌， 姜淑娟. 基于遺傳算法的動態可變參數的測試數據自動生成工具. 計算機科學， 2012（5）： 124-127.

[25] 夏輝， 宋昕， 王理. 基于Z路徑覆蓋的測試用例自動生成技術研究[J]. 現代電子技術， 2006（6）： 92-94.

[26] Willem Visser， Corina S. Pasareanu， Sarfraz Khurshid. Test Input Generation with Java Path Finder. ISSTA， 2004： 97-107.

[27] J.Wegener， A.Baresel， H.Sthamer. Evolutionary test environment for automatic structural testing[J]. Information and Software Technology， 2001， 43（4）： 841-854.

[28] 熊偉清， 魏平. 二進制蟻群進化算法[J]. 自動化學報. 2007， 33（3）： 259-264.

[29] 王柳毅， 熊偉清. 并行二級制蟻群算法的多峰函數優化[J].計算機工程與應用. 2006， 22（3）： 42-45.

[30] Yucheng Kao， Kevin Cheng. An ACO-Based Clustering Algorithm. 5th International Workshop， ANT， 2006， 340- 347.

[31] Michael Eley. Some Experiments with Ant Colony Algorithms for the Exam Timetabling Problem . 5th International Workshop， ANT， 2006， 492-499.