基于遺傳算法的UML活動圖測試用例優(yōu)化研究

李浩　陳鋒

摘 要： 測試用例的選擇在軟件測試中十分重要，良好的測試用例可以減少時間和資源的使用，因此提出了一種基于遺傳算法的UML活動圖自動生成測試用例的算法。通過建立UML活動圖模型，將活動圖轉換為有向圖，然后采用深度優(yōu)先搜索方法獲得測試路徑，應用遺傳算法優(yōu)化得到測試路徑。該算法可以提供優(yōu)先需要測試的路徑，用于自動生成高質量的測試用例，提高測試任務的工作效率。

關鍵詞： UML； 測試用例； 活動圖； 深度優(yōu)先搜索算法； 遺傳算法

中圖分類號： TN911?34 文獻標識碼： A 文章編號： 1004?373X（2015）19?0117?04

Abstract： The selection of test cases in software testing is important， and the better test cases can reduce time and resource usage. An algorithm of automatic generation test cases of UML activity diagram based on genetic algorithm is proposed. The activity diagram is converted into digraph by establishing UML activity diagram model. The testing path is acquired by adopting depth first search （DFS） method， and obtained by using genetic algorithm optimization. This algorithm can provide the path needed to be tested first to generate high quality test cases automatically. The work efficiency of the test task can be improved.

Keywords： UML； test case； activity diagram； depth first search method； genetic algorithm

0 引 言

隨著信息技術的發(fā)展，軟件技術在各行業(yè)領域中的應用日益廣泛。作為軟件質量的保證，軟件測試在軟件開發(fā)中的作用逐漸得到重視。國內外相關學者在基于模型的測試技術以及測試用例自動生成上，開展了大量的研究[1?3]。UML（Unified Modeling Language）作為軟件建模的標準，激發(fā)了研究者極大的熱情，UML模型在設計測試用例方面的重要性得到了充分的驗證。UML中包含狀態(tài)圖、活動圖和序列圖等，文獻[4?6]給出了基于UML狀態(tài)圖、序列圖和協作圖生成測試用例的方法。對于描述系統動態(tài)行為，UML活動圖（Activity Diagram）被認為是最適合描述軟件過程的模型[7]。本質上，活動圖是一種流程圖，該模型是描述系統業(yè)務過程的重要工具，不僅能定義活動中對象的角色、屬性和狀態(tài)的變化，也適用于描述滿足用例要求所進行的活動以及活動時間的約束關系，強調對象間的控制流程。Rudram研究了如何使用UML活動圖生成測試用例的方法[8]，提出了形式化的活動圖。M.S.Chen等人提出一種基于UML活動圖的隨機測試用例生成方法[9]。對于生成的測試路徑，適當的優(yōu)化能夠在滿足較高測試覆蓋率的基礎上，減少測試用例的數量，從而進一步降低測試成本，提高測試效率。本文采用DFS算法尋找UML狀態(tài)圖中的測試路徑，將遺傳算法用于優(yōu)化測試路徑。

1 UML活動圖與測試用例

（4）[dependent（CA）]表示存在與CA有依賴關系的所有對象，[dependent（CA）={o（o，a）∈Fo，a∈CA，o∈O}?][{o（a，o）∈Fo，a∈CA，o∈O}]。設[D=（A，O，T，Fc，Fo，C，S，E）]是一個活動圖，[a∈A]是圖中的一個結構化活動，描述結構化活動[a]的圖記為[Da，][D]是活動圖[Da]的父圖，[Da]是活動圖[D]的子圖。

其中，TS表示針對活動圖[D]的測試場景，每個測試場景由活動圖中一系列相關的活動（包括活動的遷移信息、觸發(fā)事件等）組成；Data表示測試場景TS所需要的測試數據，是指對應于特定測試場景的輸入信息（包括各種類型的數據等）。

2 測試路徑生成

2.1 UML活動圖的建立規(guī)則

活動圖是對系統的活動動態(tài)建模的行為視圖，如圖1所示。針對測試對象，為了使UML活動圖能較好地生成測試用例，在建模時需要遵循以下的可測試性設計規(guī)則[11?12]：

（1） 滿足結構化條件，一個活動圖有惟一的起始節(jié)點，分支節(jié)點與匯合節(jié)點要求配對出現；

（2） 不存在孤立節(jié)點，除了起始節(jié)點和結束節(jié)點之外，每個節(jié)點至少有輸入邊、輸出邊各一條，使活動圖的每個節(jié)點都是可達的；

（3） 業(yè)務過程中的各個環(huán)節(jié)通常會涉及到對象狀態(tài)的變遷，可以采用對象流描述，同一對象可能多次出現，表明該對象處于對象生存周期的不同時間點，對應著對象的不同狀態(tài)；

（4） 業(yè)務過程中的各個活動也會涉及到參數模型的某些參數，如配置參數、功能參數和環(huán)境參數等，為了表示活動圖中的這些參數，需要給活動節(jié)點加注釋，記為：參數1：參數2：參數3：…；

（5） 一般情況下，在活動圖中的決策節(jié)點擁有若干條件分支，為了識別出優(yōu)先遍歷的條件分支，可以在這個條件分支中使用構造符加以區(qū)分；

（6） 如果在循環(huán)體內存在Fork?join塊或者在Fork?join塊內存在嵌套的Fork?join塊，可以使用結構化活動替換此Fork?join塊，然后再構建該結構化活動的活動子圖。

2.2 活動圖轉換

在活動圖上，從起始節(jié)點到終止節(jié)點任意可能的路徑，都能表示為待測軟件的一個測試場景，由路徑上的動作狀態(tài)和轉換組成的活動執(zhí)行序列[11]。為了獲得活動圖中所有的測試路徑，首先應當將活動圖轉化為如圖2所示的有向圖，根據相應的測試覆蓋準則，通過對有向圖采用深度優(yōu)先搜索，獲取起始點到終節(jié)點的所有活動序列，即得到了測試路徑。

深度優(yōu)先搜索算法（Depth First Search）是一種遞歸算法，對每一個可能的分支路徑深入到不能再深入為止，而且每個節(jié)點只能訪問一次。每次在訪問完當前頂點后，首先訪問當前頂點的一個未被訪問過的鄰接頂點，然后去訪問這個鄰接點的一個未被訪問過的鄰接點[13]。圖3為深度優(yōu)先搜索算法流程圖，算法內容如下：

（1） 訪問初始頂點[v，]標記頂點[v]已訪問；

（2） 查找[v]的第一個鄰接頂點[w；]

（3） 若[w]存在，繼續(xù)執(zhí)行；否則回溯到[v，]繼續(xù)尋找[v]的另外一個未訪問過的鄰接點；

（4） 若[w]尚未被訪問，則訪問頂點[w]并標記頂點[w]為已訪問；

（5） 繼續(xù)查找頂點[w]的下一個鄰接頂點[wi，]將[v]取值[wi，]回到步驟（3），直到圖中所有的頂點全部訪問完成為止。

測試用例包含測試路徑和相應的輸入數據，每一條測試路徑對應一個相應的測試場景。在得到測試路徑之后，通過加入輸入、輸出參數和決策條件等信息，就能得到完整的測試用例。

3 基于遺傳算法的UML活動圖生成測試用例

遺傳算法（Genetic Algorithm）是一類仿生算法[14]，借鑒生物界適者生存，優(yōu)勝劣汰遺傳機制的進化規(guī)律演化而來的隨機化搜索方法。通過對生物進化行為的描述，將生物學特性用于實際計算問題中，是計算機科學、人工智能和模式識別等領域中用于解決最優(yōu)化的一種搜索啟發(fā)式算法。

3.1 遺傳算法介紹

遺傳算法的基本運算過程如下：

（1） 抽象待解決問題，進行編碼；

（2） 初始化種群，設置最大進化代數為[T，]隨機生成[n]個個體作為初始群體[P（0）=p1，p2，…，pn；]

（3） 采用適應度函數，計算現有群體[P（t）]中各個個體的適應度；

（4） 根據群體中個體的適應度，將選擇算子作用于群體，把優(yōu)化的個體遺傳到下一代或配對交叉產生新的個體遺傳到下一代；

（5） 將交叉算子和變異算子作用于群體，得到新一代群體[P（t+1）；]

（6） 若[t=T，]選取進化過程中所得到的具有最大適應度個體作為最優(yōu)解輸出，終止計算若不滿足，則返回步驟（3）。

3.2 UML活動圖生成測試用例算法

根據上文的論述，將遺傳算法用于UML活動圖自動生成優(yōu)化測試路徑，算法步驟如下：

（1）生成測試對象的活動圖，將其轉換為活動有向圖。

（2） 對判斷或選擇節(jié)點編碼，隨機生成一組測試數據，作為初始化種群。

（3） 對于每一個測試數據：

① 使用DFS算法遍歷有向圖，按順序使每個節(jié)點入棧，得到棧的容量Smax；

② 對于每個節(jié)點，節(jié)點基于棧的權值[w]表示為[w=Smax-k，][k]為當前節(jié)點上方的節(jié)點號，并行的節(jié)點指定相同的[w；]

③ 對于每個判斷或選擇節(jié)點，它的分支節(jié)點權值[w]相同，插入相鄰的分支節(jié)點并且更新頂點，忽略分支節(jié)點和先前插入的判斷或選擇節(jié)點。

（4） 計算每個個體的適應度[F，][F=i=1n（wei+wsi）=][i=1n[Edge（i）+Stack（i）]]，其中Edge（i）表示每個節(jié)點的流入邊個數與流出邊個數之積，表示為[Edge（i）=In（i）*Out（i），]Stack（i）為節(jié)點基于棧的權值。

（5） 選擇初始化的種群個體數據，分別求出相應的適應度。

（6） 隨機生成0～1區(qū)間的實數[R，]如果[R<0.8，]執(zhí)行交叉；[R>0.8，]執(zhí)行變異。

（7） 對適應度較高的個體根據[R]的值執(zhí)行交叉、變異操作，得到新的個體。

（8） 將新個體代入下一代種群，隨機加入若干個體，維持種群規(guī)模，形成新的種群。

（9） 重復上述遺傳算法步驟，直至所有路徑被覆蓋或者設置的種群數達到最大化。

（10） 選擇適應度最大的個體，其所對應的即是最佳路徑，結束。

3.3 實驗分析

如圖2所示，選取判斷或選擇節(jié)點4，8和14，進行三位二進制編碼，0表示“否”，1表示“是”，對于節(jié)點14，0表示“Transfer”，1表示“Withdraw”。例如，000就能表示路徑1→2→3→4→6→9→10→13→18。如表1所示，列舉了圖2中各個節(jié)點基于棧的權值，表2所示為各節(jié)點權值之和。

4 結 語

本文提出了一種基于遺傳算法優(yōu)化測試路徑的自動生成方法。詳細地描述了UML活動圖模型的屬性，UML活動圖轉化為有向圖的規(guī)則，采用DFS算法獲得測試路徑和使用遺傳算法優(yōu)化測試路徑的步驟。該方法可以尋找最優(yōu)化的測試路徑，用于優(yōu)先測試，能在一定程度上提高測試效率。如何設計實現相應的自動化工具，將成為未來的研究方向。

參考文獻

[1] OFFUTT A J， XIONG Y， LIU S. Criteria for generating specification?based tests [C]// Proceedings of 1999 the 4th IEEE International Conference on Engineering of Complex Computer Systems. Las Vegas： IEEE， 1999： 119?129.endprint

[2] RIEBISCH M， PHILIPPOW I， GOTZE M. UML?based statistical test case generation [J]. Lecture Notes in Computer Science， 2003， 8（19）： 394?411.

[3] 王林章，李宣東，鄭國梁.一個基于UML協作圖的集成測試用例生成方法[J].電子學報，2004，32（8）：1290?1296.

[4] FRAIKIN F， LEONHARDT T. SeDiTeC?testing based on sequence diagrams [C]// Proceedings of 2002 the 17th IEEE International Conference on Automated Software Engineering. [S.l.]： IEEE， 2002： 261?266.

[5] OFFUTT A J， ABDURAZIK A. Using UML collaboration diagrams for static checking and test generation [C]// Proceedings of 2000 the 3rd Advancing International Conference. New York： Springer Berlin Heidelberg， 2000： 383?386.

[6] BRIAND L， LABICHE Y. A UML?based approach to system testing [J]. Journal of Software and Systems Modeling， Springer Verlag， 2002， 1： 10?42.

[7] MCLEOD G， HALPIN T， KANGASSALO H， et al. Unified modeling language （UML）： a critical evaluation and suggested future [C]// Proceedings of 2001 the 34th Annual Hawaii International Conference on System Science. Hawaii ： 2001， 3： 112?114.

[8] RUDRAM C. Generating test cases from UML [D]. Sheffield ： University of Sheffield， 2000.

[9] CHEN Mingsong， QIU Xiaokang， LI Xuandong. Automatic test case generation for UML activity diagrams [C]// Proceedings of 2006 International Workshop on Automation of Software Test. Shanghai， China： ACM， 2006： 1?8.

[10] 袁潔松，王林章，李宣東，等.UMLTGF：一個基于灰盒方法從UML活動圖生成測試用例的工具[J].計算機研究與發(fā)展，2006，43（1）：46?53.

[11] 蘇翠翠.一種基于UML活動圖生成測試用例的方法[D].南京：南京郵電大學，2011.

[12] 解楠.基于UML活動圖模型的測試用例自動生成方法研究[D].西安：西安電子科技大學，2011.

[13] WEISS M A. Data structures and problem solving using Java [M]. Boston： Addison Wesley， 2005.

[14] 王小平，蓸立明.遺傳算法理論、應用與軟件實現[M].西安：西安交通大學出版社，2002.endprint