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

曹陽　劉正濤

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

關(guān)鍵詞：測試場景；活動流圖；深度優(yōu)先搜索；獨立路徑；自動生成

中圖分類號：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）

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

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

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

generation based on activity flow graph）

2.1 活動流圖的元素定義

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

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

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

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

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

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

；循環(huán)回路集合表示為C（AFG）。

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

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

2.2 測試場景生成策略的設(shè)計

根據(jù)獨立路徑的定義，獨立路徑集合能夠覆蓋活動流圖中所有的邊，且保證每條路徑中循環(huán)回路至多執(zhí)行一次；對應(yīng)的測試場景集合即為優(yōu)化的測試場景集合，實現(xiàn)了采用較少的測試場景覆蓋全部的工作流，同時解決了循環(huán)回路的執(zhí)行問題。基于活動流圖的測試場景生成策略如下：

（1）根據(jù)系統(tǒng)需求創(chuàng)建活動圖。

（2）將活動圖轉(zhuǎn)化為活動流圖。

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

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

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

3 關(guān)鍵算法的設(shè)計與實現(xiàn)（Design and implementation

of the key algorithm）

3.1 基于深度優(yōu)先策略的路徑搜索算法

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

（1）起始結(jié)點設(shè)置為已訪問，將其入棧。

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

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

（4）對于已入棧且已訪問的相鄰結(jié)點，說明存在循環(huán)回路，判斷w在棧中出現(xiàn)的次數(shù)是否小于該結(jié)點的出度；如果出現(xiàn)次數(shù)小于出度，則說明當(dāng)前循環(huán)回路為第一次執(zhí)行，將w入棧，同時將w作為棧頂元素，重新執(zhí)行第（2）步；否則，則訪問下一相鄰結(jié)點。

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

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

3.2 獨立路徑集合獲取算法

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

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

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

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

4 應(yīng)用實例（Examples of application）

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

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

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

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

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

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

（1）實現(xiàn)了根據(jù)活動流圖自動化獲取路徑集合。

（2）解決了循環(huán)回路帶來的復(fù)雜性問題；圖2中包含的三個循環(huán)回路在路徑中僅執(zhí)行一次。

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

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

5 結(jié)論（Conclusion）

本文提出了一種測試場景的自動生成策略，根據(jù)UML活動圖，給出了活動流圖的嚴格定義，通過改進的深度優(yōu)先搜索算法及路徑優(yōu)化算法，解決了測試場景中的循環(huán)回路問題與測試冗余問題。同時該策略能夠?qū)崿F(xiàn)測試場景的自動生成，并在一個商業(yè)系統(tǒng)測試過程中成功應(yīng)用，證明了測試結(jié)果具有較好的充分性，測試效率得到了顯著提高。

參考文獻（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].計算機應(yīng)用與軟件，2009，26（2）：107-110.

[5] 蘇翠翠，王曉軍.基于UML活動圖的測試用例生成方法研究[J].計算機技術(shù)與發(fā)展，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] 陳鑫，等.一種面向列車控制系統(tǒng)中安全攸關(guān)場景的測試用例自動生成方法[J].軟件學(xué)報，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活動圖測試用例優(yōu)化研究[J].現(xiàn)代電子技術(shù)，2015，38（19）：117-120.

作者簡介：

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

證，數(shù)據(jù)挖掘.

劉正濤（1975-），男，博士，副教授.研究領(lǐng)域：數(shù)據(jù)庫應(yīng)用.