曹陽　劉正濤

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

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

中圖分類號(hào)：TP312 文獻(xiàn)標(biāo)識(shí)碼：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）

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

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

2 基于活動(dòng)流圖的測(cè)試場(chǎng)景生成策略（Test scene

generation based on activity flow graph）

2.1 活動(dòng)流圖的元素定義

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

定義1：活動(dòng)流圖用一個(gè)四元組

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

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

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

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

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

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

活動(dòng)流圖中所有的獨(dú)立路徑組成的集合稱為獨(dú)立路徑集合，記為。獨(dú)立路徑集合為路徑集合的一個(gè)子集，即。

2.2 測(cè)試場(chǎng)景生成策略的設(shè)計(jì)

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

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

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

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

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

（5）根據(jù)獨(dú)立路徑集合生成測(cè)試場(chǎng)景。

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

of the key algorithm）

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

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

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

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

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

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

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

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

3.2 獨(dú)立路徑集合獲取算法

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

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

（2）對(duì)剩余路徑進(jìn)行遍歷，逐條驗(yàn)證其是否為獨(dú)立路徑，將獨(dú)立路徑加入獨(dú)立路徑集合。

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

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

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

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

測(cè)試場(chǎng)景1：Start—生成詢價(jià)單—采購組審批未通過—修改詢價(jià)單—生成詢價(jià)單—采購組審批通過—部門審批未通過—記錄問題詢價(jià)單—End。

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

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

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

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

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

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

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

5 結(jié)論（Conclusion）

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

參考文獻(xiàn)（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的測(cè)試用例生成方法研究[J].計(jì)算機(jī)應(yīng)用與軟件，2009，26（2）：107-110.

[5] 蘇翠翠，王曉軍.基于UML活動(dòng)圖的測(cè)試用例生成方法研究[J].計(jì)算機(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] 楊鶴標(biāo)，李云平.基于UML活動(dòng)圖的功能測(cè)試場(chǎng)景生成方法[J].計(jì)算機(jī)工程，2011，37（2）：55-57.

[9] 陳鑫，等.一種面向列車控制系統(tǒng)中安全攸關(guān)場(chǎng)景的測(cè)試用例自動(dòng)生成方法[J].軟件學(xué)報(bào)，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活動(dòng)圖測(cè)試用例優(yōu)化研究[J].現(xiàn)代電子技術(shù)，2015，38（19）：117-120.

作者簡介：

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

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

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