一種基于UML活動圖的測試場景自動生成策略

曹陽　劉正濤

摘 要：傳統的場景法在設計測試用例的過程中存在著構造場景困難、冗余度高、設計效率低下等問題。針對此問題，提出了一種基于UML活動圖的測試場景自動生成策略。在建立活動流圖模型后，采用改進的深度優先搜索算法獲得路徑集合，應用路徑優化算法生成測試路徑及測試場景。通過在商用的供應商協同平臺的測試過程中應用該策略，驗證了其有效性。實踐結果表明，該策略較好的解決了循環工作流產生的路徑爆炸問題，降低了測試場景的冗余度。

關鍵詞：測試場景；活動流圖；深度優先搜索；獨立路徑；自動生成

中圖分類號：TP312 文獻標識碼：A

Abstract：In the process of designing test case through the traditional scene method，there are many problems，including scene construction difficulty，high redundancy and low design efficiency.To solve this problem，the paper proposes a scheme for test scene automatic generation based on UML activity diagram.On the basis of the activity flow graph，the improved depth-first search algorithm is adopted to obtain path collection，and the path optimization algorithm method is applied to generate test path and test scene.The effectiveness of this scheme has already been verified in a testing process of a commercial supplier collaboration platform.The practice results indicate that the scheme can effectively solve the problem of path explosion caused by cycle workflow and significantly reduce the redundancy of test scene.

Keywords：test scene；activity flow graph；depth-first search；independent path；automatic generation

1 引言（Introduction）

基于場景的測試用例設計方法[1]是一種重要的黑盒測試技術，其核心思想是通過分析軟件需求，構建各種測試場景，并尋找測試場景與系統輸入參數、特征狀態的關聯關系進行測試用例的設計。測試場景的構建是場景法的關鍵環節，傳統的從軟件需求規格說明中提取基本流、備選流進行測試場景構建的方法存在效率低下、執行困難等問題。因此，探索測試場景自動生成策略成為運用場景法設計測試用例的重要研究點之一?；赨ML模型驅動測試用例自動生成是一種基于模型的軟件測試技術，在自動生成測試用例方面有廣泛的研究[2，3]。其中UML活動圖用于表示系統業務的工作流程，被認為是最適合描述軟件過程的模型，因此眾多研究者在使用UML活動圖生成測試場景方面做了一定的研究。周飛等提出將活動圖轉化為有向圖，通過構建圖的搜索樹生成測試場景[4]；蘇翠翠等提出了一種基于路徑覆蓋的測試場景生成算法[5]；Jena等提出了活動流圖（Activity Flow Graph，AFG）的概念，設計了測試場景模型，并采用遺傳算法生成測試場景[6]。這些研究為基于UML活動圖構建測試場景提供了良好的思路，但是存在著以下問題：一是構建的模型在形式化定義上有所欠缺；二是未能實現測試場景的自動化生成；三是未考慮復雜測試場景中的循環工作流的執行與優化。

本文通過對活動流圖進行形式化定義，給出了測試場景的自動生成策略，針對系統需求中存在循環工作流的情況提出了一種測試場景優化算法，顯著降低了測試場景的冗余性，提高了測試設計效率。

2 基于活動流圖的測試場景生成策略（Test scene

generation based on activity flow graph）

2.1 活動流圖的元素定義

由于UML是一種半形式化的建模語言，因此需要采用一種更好的可形式化表示的圖來構造測試場景模型?；顒恿鲌D由活動圖轉化而來，通過把活動圖中的各種元素按照一定的規則映射而成[7]，其本質是一個有向圖。圖1表示了一個活動圖與活動流圖的映射關系。

定義1：活動流圖用一個四元組

表示。其中表示圖中所有結點的集合，N為活動流圖中所有結點的數量；表示圖中所有邊的集合，M為活動流圖中所有邊的數量；為活動流圖中唯一的起始結點；表示活動流圖中終結結點的集合，n為所有終結結點的數量。邊可以由一個有序結點對表示，即。

定義2：路徑集合是活動流圖中所有從起始結點到終結結點由邊連接而成的結點序列，記為，np為活動流圖中路徑的總數。路徑可以由組成該路徑的邊的有序集合表示，記為，ne為路徑p包含的邊數。

根據活動圖與活動流圖的映射關系，一條路徑表示系統用例從開始到結束的執行流程，對應著一個測試場景，路徑集合則對應測試場景集合，構建測試場景的問題就轉化為獲取活動流圖路徑集合的問題。對于較復雜的系統需求，所構建的活動圖往往包含循環工作流；循環會導致路徑的組合爆炸，對活動圖中所有可能的路徑進行窮盡測試是無法達到的[8]。為了得到所有路徑集合，需要對循環工作流進行合理處理。循環可展開成為無限長的路徑序列，為了控制路徑序列的長度，限定測試場景中每個循環只展開一次[9]。同時，路徑集合中的路徑之間存在大量相同的邊，使其對應的測試場景之間存在較多相同的測試工作流，從而導致設計出的測試用例存在冗余，因此需要對路徑集合進行優化，降低冗余度。

定義3：循環回路是某路徑中含有一組邊，且由這組邊形成的一個閉合回路，即

；循環回路集合表示為C（AFG）。

定義4：獨立路徑是至少存在一條路徑集合中其余路徑不包含的邊，且不含循環回路或包含的各個循環回路至多執行一次的路徑。獨立路徑表示為：。

活動流圖中所有的獨立路徑組成的集合稱為獨立路徑集合，記為。獨立路徑集合為路徑集合的一個子集，即。

2.2 測試場景生成策略的設計

根據獨立路徑的定義，獨立路徑集合能夠覆蓋活動流圖中所有的邊，且保證每條路徑中循環回路至多執行一次；對應的測試場景集合即為優化的測試場景集合，實現了采用較少的測試場景覆蓋全部的工作流，同時解決了循環回路的執行問題?；诨顒恿鲌D的測試場景生成策略如下：

（1）根據系統需求創建活動圖。

（2）將活動圖轉化為活動流圖。

（3）基于改進的深度優先搜索算法獲取活動流圖的路徑集合。

（4）采用路徑優化算法獲取活動流圖的獨立路徑集合。

（5）根據獨立路徑集合生成測試場景。

3 關鍵算法的設計與實現（Design and implementation

of the key algorithm）

3.1 基于深度優先策略的路徑搜索算法

深度優先搜索算法（Depth First Search，DFS）是一種經典的圖遍歷算法，可以用于獲取圖的路徑集合。在基于UML活動圖生成測試場景的研究中，多為面向有向無環圖的獲取路徑集合的DFS算法[10，11]。但有向無環圖不包含循環回路，因此針對本文的研究內容，提出了一種改進的深度優先搜索算法，以解決循環回路的問題，具體思想如下：

（1）起始結點設置為已訪問，將其入棧。

（2）獲取棧頂元素v的相鄰結點集合W。

（3）對集合W進行遍歷，對于未入棧且未被訪問的相鄰結點，將其入棧，并標記為已訪問，同時將w作為棧頂元素，重新執行第（2）步。

（4）對于已入棧且已訪問的相鄰結點，說明存在循環回路，判斷w在棧中出現的次數是否小于該結點的出度；如果出現次數小于出度，則說明當前循環回路為第一次執行，將w入棧，同時將w作為棧頂元素，重新執行第（2）步；否則，則訪問下一相鄰結點。

（5）如果W集合中不存在步驟（3）（4）中的兩類相鄰結點，則將W集合中的每個結點標記為未訪問，將棧頂元素v出棧。

（6）當棧頂元素為終結結點，即W為空時，將棧中的結點按照逆序排列構成的路徑加入路徑集合P（AFG）中，并彈出棧頂元素。

3.2 獨立路徑集合獲取算法

在路徑集合中根據獨立路徑的定義進行路徑篩選，可以得到獨立路徑集合。獨立路徑集合的獲取算法思想如下：

（1）任選一條路徑作為獨立路徑，初始化獨立路徑集合。

（2）對剩余路徑進行遍歷，逐條驗證其是否為獨立路徑，將獨立路徑加入獨立路徑集合。

（3）對第（1）步中得到的獨立路徑集合中的每條路徑再次進行遍歷，移除不滿足獨立路徑條件的路徑。

4 應用實例（Examples of application）

供應商協同平臺是一個將企業采購管理系統與供應鏈管理系統對接形成線上流程的一體化平臺，為企業拉動與上游客戶之間在訂貨協作、商品推介、庫存查看、資金支付、物流查詢、渠道溝通等業務環節的緊密協作。平臺中包含眾多業務流程，其中“采購物資”流程是一個較為復雜的系統需求，包含若干審批環節。以該流程為測試對象驗證本文提出的測試場景自動生成策略的有效性。根據系統需求，構建“采購物資”流程的活動圖如圖2所示。

根據獨立路徑集合的獲取算法，得到獨立路徑集合如表2所示。將獨立路徑表示的結點序列映射至圖1中，生成的測試場景如下：

測試場景1：Start—生成詢價單—采購組審批未通過—修改詢價單—生成詢價單—采購組審批通過—部門審批未通過—記錄問題詢價單—End。

測試場景2：Start—生成詢價單—采購組審批通過—部門審批通過—生成采購單—審批采購單未通過—評審問題采購單（可以解決）—修改采購單—審批采購單未通過—評審問題采購單（不可解決）—關閉采購單—End。

測試場景3：Start—生成詢價單—采購組審批通過—部門審批通過—生成采購單—審批采購單通過—生成發貨單—審批發貨單未通過—修改發貨單—審批發貨單通過—發貨—End。

通過對實例的應用結果進行分析，提出的測試場景生成策略解決了以下問題：

（1）實現了根據活動流圖自動化獲取路徑集合。

（2）解決了循環回路帶來的復雜性問題；圖2中包含的三個循環回路在路徑中僅執行一次。

（3）通過路徑優化，將14個測試場景優化為三個測試場景，降低了測試冗余性。

（4）優化后的測試場景能夠使系統工作流達到100%的測試覆蓋率，具有較好的測試充分性。

5 結論（Conclusion）

本文提出了一種測試場景的自動生成策略，根據UML活動圖，給出了活動流圖的嚴格定義，通過改進的深度優先搜索算法及路徑優化算法，解決了測試場景中的循環回路問題與測試冗余問題。同時該策略能夠實現測試場景的自動生成，并在一個商業系統測試過程中成功應用，證明了測試結果具有較好的充分性，測試效率得到了顯著提高。

參考文獻（References）

[1] Anand S，et al.An Orchestrated Survey of Methodologies for Automated Software Test Case Generation[J].Journal of Systems and Software，2013，86（8）：1978-2001.

[2] Utting M，Pretschner A，Legeard B.A Taxonomy of Model-based Testing Approaches[J].Software Testing Verification and Reliability，2012，22（5）：297-312.

[3] Shirole M，Kumar R.UML Behavioral Model Based Test Case Generation：a Survey[J].ACM SIGSOFT Software Engineering Notes，2013，38（4）：1-13.

[4] 周飛，楊根興，蔡立志.基于UML的測試用例生成方法研究[J].計算機應用與軟件，2009，26（2）：107-110.

[5] 蘇翠翠，王曉軍.基于UML活動圖的測試用例生成方法研究[J].計算機技術與發展，2010，20（8）：49-51.

[6] Jena A K，Swain S K，Mohapatra D P.A Novel Approach for Test Case Generation from UML Activity Diagram[C].Issues and Challenges in Intelligent Computing Techniques （ICICT），2014 International Conference on.IEEE，2014：621-629.

[7] Kundu D，Samanta D.A Novel Approach to Generate Test Cases from UML Activity Diagrams[J].Journal of Object Technology，2009，8（3）：65-83.

[8] 楊鶴標，李云平.基于UML活動圖的功能測試場景生成方法[J].計算機工程，2011，37（2）：55-57.

[9] 陳鑫，等.一種面向列車控制系統中安全攸關場景的測試用例自動生成方法[J].軟件學報，2015，26（2）：269-278.

[10] Sharma C，Sabharwal S，Sibal R.A Survey on Software Testing Techniques Using Genetic Algorithm[J].International Journal of Computer Science Issues，2014，10（1）：381-393.

[11] 李浩，陳鋒.基于遺傳算法的UML活動圖測試用例優化研究[J].現代電子技術，2015，38（19）：117-120.

作者簡介：

曹 陽（1982-），男，碩士，講師.研究領域：軟件測試與驗

證，數據挖掘.

劉正濤（1975-），男，博士，副教授.研究領域：數據庫應用.