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

一種基于UML活動圖的測試場景自動生成策略Abstract：Intheprocessofdesigningtestcasethroughthetraditionalscenemethod，therearemanyproblems，includingsceneconstructiondifficulty，highredundancyandlowdesignefficiency.Tosolvethisproblem，thepaperproposesaschemefortestsceneautomaticgenerationbasedonUMLactivitydiagram.Onthebasisoftheactivityflowgraph，theimproveddepth-firstsearchalgorithmisadoptedtoobtainpathcollection，andthepathoptimizationalgorithmmethodisappliedtogeneratetestpathandtestscene.Theeffectivenessofthisschemehasalreadybeenverifiedinatestingprocessofacommercialsuppliercollaborationplatform.Thepracticeresultsindicatethattheschemecaneffectivelysolvetheproblemofpathexplosioncausedbycycleworkflowandsignificantlyreducetheredundancyoftestscene.Keywords：testscene；activityflowgraph；depth-firstsearch；independentpath；automaticgeneration引言（Introduction）基于場景的測試用例設(shè)計方法[1]是一種重要的黑盒測試技術(shù)，其核心思想是通過分析軟件需求，構(gòu)建各種測試場景，并尋找測試場景與系統(tǒng)輸入?yún)?shù)、特征狀態(tài)的關(guān)聯(lián)關(guān)系進(jìn)行測試用例的設(shè)計。測試場景的構(gòu)建是場景法的關(guān)鍵環(huán)節(jié)，傳統(tǒng)的從軟件需求規(guī)格說明中提取基本流、備選流進(jìn)行測試場景構(gòu)建的方法存在效率低下、執(zhí)行困難等問題。因此，探索測試場景自動生成策略成為運用場景法設(shè)計測試用例的重要研究點之一?；赨ML模型驅(qū)動測試用例自動生成是一種基于模型的軟件測試技術(shù)，在自動生成測試用例方面有廣泛的研究[2，3]。其中UML活動圖用于表示系統(tǒng)業(yè)務(wù)的工作流程，被認(rèn)為是最適合描述軟件過程的模型，因此眾多研究者在使用UML活動圖生成測試場景方面做了一定的研究。周飛等提出將活動圖轉(zhuǎn)化為有向圖，通過構(gòu)建圖的搜索樹生成測試場景[4]；蘇翠翠等提出了一種基于路徑覆蓋的測試場景生成算法[5]；Jena等提出了活動流圖（ActivityFlowGraph，AFG）的概念，設(shè)計了測試場景模型，并采用遺傳算法生成測試場景[6]。這些研究為基于UML活動圖構(gòu)建測試場景提供了良好的思路，但是存在著以下問題：一是構(gòu)建的模型在形式化定義上有所欠缺；二是未能實現(xiàn)測試場景的自動化生成；三是未考慮復(fù)雜測試場景中的循環(huán)工作流的執(zhí)行與優(yōu)化。本文通過對活動流圖進(jìn)行形式化定義，給出了測試場景的自動生成策略，針對系統(tǒng)需求中存在循環(huán)工作流的情況提出了一種測試場景優(yōu)化算法，顯著降低了測試場景的冗余性，提高了測試設(shè)計效率?；诨顒恿鲌D的測試場景生成策略（Testscenegenerationbasedonactivityflowgraph）2.1活動流圖的元素定義由于UML是一種半形式化的建模語言，因此需要采用一種更好的可形式化表示的圖來構(gòu)造測試場景模型。活動流圖由活動圖轉(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)致路徑的組合爆炸，對活動圖中所有可能的路徑進(jìn)行窮盡測試是無法達(dá)到的[8]。為了得到所有路徑集合，需要對循環(huán)工作流進(jìn)行合理處理。循環(huán)可展開成為無限長的路徑序列，為了控制路徑序列的長度，限定測試場景中每個循環(huán)只展開一次[9]。同時，路徑集合中的路徑之間存在大量相同的邊，使其對應(yīng)的測試場景之間存在較多相同的測試工作流，從而導(dǎo)致設(shè)計出的測試用例存在冗余，因此需要對路徑集合進(jìn)行優(yōu)化，降低冗余度。定義3：循環(huán)回路是某路徑中含有一組邊，且由這組邊形成的一個閉合回路，即；循環(huán)回路集合表示為C（AFG）。定義4：獨立路徑是至少存在一條路徑集合中其余路徑不包含的邊，且不含循環(huán)回路或包含的各個循環(huán)回路至多執(zhí)行一次的路徑。獨立路徑表示為：?；顒恿鲌D中所有的獨立路徑組成的集合稱為獨立路徑集合，記為。獨立路徑集合為路徑集合的一個子集，即。2.2測試場景生成策略的設(shè)計根據(jù)獨立路徑的定義，獨立路徑集合能夠覆蓋活動流圖中所有的邊，且保證每條路徑中循環(huán)回路至多執(zhí)行一次；對應(yīng)的測試場景集合即為優(yōu)化的測試場景集合，實現(xiàn)了采用較少的測試場景覆蓋全部的工作流，同時解決了循環(huán)回路的執(zhí)行問題?；诨顒恿鲌D的測試場景生成策略如下：（1）根據(jù)系統(tǒng)需求創(chuàng)建活動圖。（2）將活動圖轉(zhuǎn)化為活動流圖。基于改進(jìn)的深度優(yōu)先搜索算法獲取活動流圖的路徑集合。采用路徑優(yōu)化算法獲取活動流圖的獨立路徑集合。根據(jù)獨立路徑集合生成測試場景。關(guān)鍵算法的設(shè)計與實現(xiàn)（Designandimplementationofthekeyalgorithm）3.1基于深度優(yōu)先策略的路徑搜索算法深度優(yōu)先搜索算法（DepthFirstSearch，DFS）是一種經(jīng)典的圖遍歷算法，可以用于獲取圖的路徑集合。在基于UML活動圖生成測試場景的研究中，多為面向有向無環(huán)圖的獲取路徑集合的DFS算法[10，11]。但有向無環(huán)圖不包含循環(huán)回路，因此針對本文的研究內(nèi)容，提出了一種改進(jìn)的深度優(yōu)先搜索算法，以解決循環(huán)回路的問題，具體思想如下：起始結(jié)點設(shè)置為已訪問，將其入棧。獲取棧頂元素v的相鄰結(jié)點集合W。對集合W進(jìn)行遍歷，對于未入棧且未被訪問的相鄰結(jié)點，將其入棧，并標(biāo)記為已訪問，同時將w作為棧頂元素，重新執(zhí)行第（2）步。對于已入棧且已訪問的相鄰結(jié)點，說明存在循環(huán)回路，判斷w在棧中出現(xiàn)的次數(shù)是否小于該結(jié)點的出度；如果出現(xiàn)次數(shù)小于出度，則說明當(dāng)前循環(huán)回路為第一次執(zhí)行，將w入棧，同時將w作為棧頂元素，重新執(zhí)行第（2）步；否則，則訪問下一相鄰結(jié)點。如果W集合中不存在步驟（3）（4）中的兩類相鄰結(jié)點，則將W集合中的每個結(jié)點標(biāo)記為未訪問，將棧頂元素v出棧。當(dāng)棧頂元素為終結(jié)結(jié)點，即W為空時，將棧中的結(jié)點按照逆序排列構(gòu)成的路徑加入路徑集合P（AFG）中，并彈出棧頂元素。3.2獨立路徑集合獲取算法在路徑集合中根據(jù)獨立路徑的定義進(jìn)行路徑篩選，可以得到獨立路徑集合。獨立路徑集合的獲取算法思想如下：任選一條路徑作為獨立路徑，初始化獨立路徑集合。對剩余路徑進(jìn)行遍歷，逐條驗證其是否為獨立路徑，將獨立路徑加入獨立路徑集合。對第（1）步中得到的獨立路徑集合中的每條路徑再次進(jìn)行遍歷，移除不滿足獨立路徑條件的路徑。4應(yīng)用實例（Examplesofapplication）供應(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é)果進(jìn)行分析，提出的測試場景生成策略解決了以下問題：實現(xiàn)了根據(jù)活動流圖自動化獲取路徑集合。解決了循環(huán)回路帶來的復(fù)雜性問題；圖2中包含的三個循環(huán)回路在路徑中僅執(zhí)行一次。通過路徑優(yōu)化，將14個測試場景優(yōu)化為三個測試場景，降低了測試