基路徑覆蓋測試用例自動生成方法研究

宋 想，宋曉秋（中國航天科工集團第二研究院706所，北京100854）

0 引 言

軟件的單元測試中控制流測試中諸如語句覆蓋、分支覆蓋、條件覆蓋、判定－條件覆蓋、路徑覆蓋等問題和數(shù)據(jù)流測試中的全定值覆蓋、全引用覆蓋等問題都可以歸結(jié)為面向路徑的測試用例生成問題［1］。本文主要研究的是基于程序直接執(zhí)行的路徑覆蓋問題。

路徑覆蓋是一種非常苛刻的覆蓋準則，即使一小段代碼包含的路徑數(shù)也可能是非常龐大的。

如下面一段代碼：

其程序結(jié)構(gòu)圖如圖1所示。

圖1 程序結(jié)構(gòu)

這段程序可能的路徑數(shù)為220。要做到百分之百路徑覆蓋，測試人員的工作量是非常巨大的。測試人員往往只能根據(jù)一定的準則對全路徑集合的某個有限子集進行測試。

在上世紀八十年代，Thomas McCabe提出了基路徑的概念，他認為可以將程序中所有可達的路徑集合看成一個向量空間，對應向量空間中基的概念，存在著一組基路徑，對基路徑的線性組合可以覆蓋整個路徑集合，因此McCabe認為找出路徑空間中的一組基路徑進行測試，如果這組基路徑?jīng)]有問題，則可以期待能夠用這組基路徑表示的一切路徑組合都沒有問題［2］。

目前，基路徑覆蓋測試用例的生成都是先根據(jù)程序得到流程圖，然后求出程序的圈復雜度，再根據(jù)流程圖找出一組基路徑，最后分別求出每條基路徑對應的測試用例。但由于機械地將源代碼表達為有向圖和程序路徑，掩蓋了代碼中的邏輯信息，通過程序圖得到的基路徑在程序?qū)嶋H運行中由于存在相互矛盾的語義依賴關(guān)系有些是不可達的，也就無法得到相應的測試用例。為此，本文通過執(zhí)行一個用例得到一個路徑向量，執(zhí)行若干用例得到一個路徑向量矩陣，利用進化的思想不斷逼近程序真實的邏輯圈復雜度，最終求得滿足基路徑覆蓋百分之百的測試用例。

1 圈復雜度

McCabe在1976年提出了圈復雜度的概念，他認為在一個強連通圖G中，圈數(shù)等于最大的線性無關(guān)的環(huán)數(shù)［3］。在所有的路徑集合中，存在若干條基路徑，其他的所有路徑都可以由這幾條路徑來線性表示，基路徑的條數(shù)就是圈復雜度［3］。

圈復雜度目前可以通過如下方法求得［4］：

（1）控制流圖：V （G）＝E－N＋2p，p＝1；

（2）強流通圖：V （G）＝E－N＋p，p為強流通區(qū)域的個數(shù)；

（3）V （G）＝R，R表示控制流圖將將平面劃分的區(qū)域的數(shù)量；

（4）V （G）＝p＋1，其中p表示判定節(jié)點的數(shù)量，若判定為復合條件，則應將復合條件分解。每個case語句以及每個if，if else，語句都應算一個判定。

以上圈復雜度的求法都是一種靜態(tài)的求法，都沒有動態(tài)運行程序。由于代碼前后會存在語義依賴關(guān)系，這種靜態(tài)求法得的圈復雜度會比程序?qū)嶋H邏輯上的圈復雜度大。

2 傳統(tǒng)基路徑覆蓋測試用例生成方法及存在的問題

傳統(tǒng)基路徑覆蓋測試用例的的生成方法一般有以下4個步驟：

（1）根據(jù)程序生成程序?qū)慕Y(jié)構(gòu)圖；

（2）根據(jù)程序的結(jié)構(gòu)圖求出程序的圈復雜度；

（3）根據(jù)結(jié)構(gòu)圖求出一組基路徑；

（4）針對基路徑組中的每條路徑求出相應的測試用例。

傳統(tǒng)基路徑覆蓋測試用例的生成方法不僅繁瑣，而且機械地將程序轉(zhuǎn)換為結(jié)構(gòu)圖，沒有實際運行被測程序，完全是一種靜態(tài)的方法。這種靜態(tài)方法完全忽視了程序語義之間的相互依賴關(guān)系，導致得到的某些獨立路徑在邏輯上其實是不可達的，也就無法生成對應的測試用例。不可達路徑的存在導致測試數(shù)據(jù)生成階段大量人力，財力的浪費，增加了軟件測試的成本。

針對存在的路徑不可達問題，有人對傳統(tǒng)算法提出了改進的方法。在得到基路徑集后，求每條獨立路徑之前，對每條獨立路徑進行可達性檢測。針對不可達路徑的檢測問題解決方法，總體上可以劃分為兩類：一類是靜態(tài)分析技術(shù)；第二類是動態(tài)分析技術(shù)［5］。

對于靜態(tài)分析技術(shù)，其本質(zhì)是檢測各條件語句之間的相關(guān)性，即通過分析條件語句之間的分支沖突來判斷目標路徑是否可達，這類技術(shù)主要包括路徑條件可滿足性方法以及探測分支相關(guān)性方法［6］。路徑條件可滿足性的方法由于關(guān)聯(lián)到程序中所有的路徑條件信息，缺乏相對性，對于規(guī)模較大的軟件來說，耗費的代價太大，因此往往很難在實際工程中應用；R.Gupta以及Bodik.R兩位學者都提出了探測分支相關(guān)性的方法，但他們提出的方法只能針對極少的條件謂詞種類，這樣使得分支的覆蓋率太低，另外探測分支相關(guān)語句的方法由于缺乏針對性，使得搜索到的信息很多都是無用的，這導致判斷分支相關(guān)性的代價增加了［7］。

動態(tài)分析技術(shù)的基本思想是在一個程序的運行過程中，通過動態(tài)測試數(shù)據(jù)的生成算法來檢測路徑的可達性［8］。但是，測試數(shù)據(jù)的產(chǎn)生往往依靠符號執(zhí)行，因此動態(tài)分析技術(shù)與符號執(zhí)行方法幾乎需要花費同樣昂貴的代價。另外動態(tài)方法由于其試探性使得測試用例的生成和探測性執(zhí)行產(chǎn)生大量的耗費，還有可能排除掉測試域比較窄的可達路徑，直接影響到測試的充分性［9］。

下面以常用的三角形程序為例說明傳統(tǒng)基路徑覆蓋測試用例生成的過程以及存在的問題：

以上代碼的結(jié)構(gòu)如圖2所示。

圖2 三角形程序結(jié)構(gòu)

根據(jù)V （G）＝E－N＋2p，p＝1求其圈復雜度，將E＝14，N＝11代人得V （G）＝5.

下面根據(jù)McCabe的基線方法來確定基路徑集合：首先挑出一個包含盡可能多判斷節(jié)點的路徑，不妨選擇1－2－4－6－8－9－結(jié)束。接下來回溯基線路徑，依次翻轉(zhuǎn)每個判斷節(jié)點，翻轉(zhuǎn)判斷節(jié)點8得到路徑1－2－4－6－8－10－結(jié)束，翻轉(zhuǎn)判斷節(jié)點6，得到路徑1－2－4－6－7－結(jié)束，翻轉(zhuǎn)判斷節(jié)點4得到路徑集合1－2－4－5－結(jié)束，翻轉(zhuǎn)判斷節(jié)點1得到路徑1－3－4－6－8－9－結(jié)束。由此得到下列基路徑集合：

傳統(tǒng)基路徑測試用例生成的下一步就是針對基路徑組中的每條路徑分別生成對應的測試用例。

由于存在相互矛盾的語義依賴關(guān)系，3－4－6在程序?qū)嶋H運行過程中是不可達的路徑，所以上述基路徑集合中1－3－4－6－8－9－結(jié)束是不可達的，也就無法生成對應的測試用例。

3 本文提出的基路徑覆蓋測試用例生成算法

算法基于以下基路徑覆蓋的充分性判別方法［10］：

設待測程序有n行，根據(jù)其程序結(jié)構(gòu)圖得出其圈復雜度為V。

（1）執(zhí)行一個測試用例時，若經(jīng)過某一行，記為1，未經(jīng)過某行記為0，執(zhí)行完一個測試用例后便得到一個n位的0、1向量；

（2）執(zhí)行完m個測試用例后便得到一個m行n列的向量矩陣。求出矩陣的秩為R；

（3）若R＜V，說明測試不夠充分，沒有測試到一組完整的基路徑；若R＝V，說明基路徑覆蓋率為百分之百；

（4）當用例不斷增加時，得到的秩隨用例數(shù)變化的曲線應該漸漸趨向平滑。

若直接應用上述充分性判別方法生成測試用例，存在4個問題：

（1）仍需要先生成程序的結(jié)構(gòu)圖，然后根據(jù)結(jié)構(gòu)圖得出圈復雜度；

（2）忽視了程序的語義依賴關(guān)系，根據(jù)結(jié)構(gòu)圖得出的圈復雜度可能比程序?qū)嶋H運行時的圈復雜度要大；

（3）當用例數(shù)逐漸增加時，得到的向量矩陣也越來越大，求矩陣的秩計算代價也增加了；

（4）用例的增加帶有盲目性，不利于生成測試用例集的效率，而且用例數(shù)越多越背離基路徑測試基的思想。

為解決以上問題本文基于一種進化的思想，動態(tài)運行程序，逐漸接近程序的實際圈復雜度，不斷進化找到一個向量矩陣使得圈復雜度具有最大值，該向量矩陣對應的測試用例集合即為滿足基路徑覆蓋測試的用例集合。

以遺傳算法為尋優(yōu)搜索算法來說明：設被測程序的輸入為M個，M個數(shù)據(jù)稱為一組，被測程序的圈復雜度為V，V的初始值為2。設T＝V，以T組數(shù)據(jù)的組合作為種群的一個個體，以該T組數(shù)據(jù)執(zhí)行被測程序得到的向量矩陣的秩為R，以值P＝R作為個體的適應度。當找到P＝V的個體后，V＝V＋1，繼續(xù)進化；當沒有找到P＝V的個體時，P＝V－1的個體對應的V－1組數(shù)據(jù)作為滿足基路徑覆蓋測試的測試用例，程序圈復雜度為V＝V－1。個體結(jié)構(gòu)圖如圖3所示。

圖3 個體結(jié)構(gòu)

當沒有找到P＝V的個體時，進化算法并不能絕對的保證程序的圈復雜度達不到V，存在沒有找到P＝V的個體，但程序圈復雜度為V的可能性。為了減小這種可能性，并考慮到以下事實：若存在某個判定的分支從沒有被走過，那么程序中至少有一條路徑?jīng)]有被走過，當沒有找到P＝V的個體，并且存在沒有被走過的分支時，進行進化尋找P＝V的個體。因此，需要標記某個分支是否沒有被走到過。

是否找到目標圈復雜度、是否存在未經(jīng)過的分支的各個組合情況的處理對策見表1。

表1 處理對策表

為了得到用例執(zhí)行后經(jīng)過的路徑向量以及判斷是否存在未經(jīng)過的分支，需要對源程序進行預處理，預處理方式如下：通過插裝的方法來判斷是否經(jīng)過了某一行。考慮到每行都插裝工作量過大、得到的矩陣向量會過長，在每個分支的第一個語句后進行插裝。通過判定節(jié)點統(tǒng)計程序中的分支數(shù)n，向量以數(shù)組C［n］來表示，通過數(shù)組B［n］來標記是否經(jīng)過某個分支，兩數(shù)組元素初始值都為零。將C［m］＝1，B［m］＝1插裝在第m＋1個分支中第一個語句后。執(zhí)行完一個用例后就可以得到該用例對應的路徑向量。執(zhí)行完所有用例后就知道是否存在未經(jīng)過的分支。

綜上所述，本文提出的基路徑覆蓋測試用例自動生成算法過程如下：

（1）對源程序進行預處理；

（2）V＝2；

（3）T＝V，以T組數(shù)據(jù)的組合作為種群的一個個體，以該T組數(shù)據(jù)執(zhí)行被測程序得到的向量矩陣的秩為R，以值P＝R作為個體的適應度；

（4）當找到P＝V的個體后，V＝V＋1，繼續(xù)進化，轉(zhuǎn)到步驟 （6）；當沒有找到P＝V的個體時，執(zhí)行步驟 （5）；

（5）若存在未經(jīng)過的分支，轉(zhuǎn)到步驟 （6），若不存在未經(jīng)過的分支，執(zhí)行步驟 （7）；

（6）對種群進行選擇、交叉、變異操作，轉(zhuǎn)到步驟（3）；

（7）V＝ V－1，程序圈復雜度為V－1，以P＝V－1的個體對應的數(shù)據(jù)作為測試用例，算法結(jié)束。

以遺傳算法作為尋優(yōu)搜索算法，則以上過程模型如圖4所示。

個體包含數(shù)據(jù)組數(shù)的變化：目標圈復雜度為V時，個體包含的數(shù)據(jù)組數(shù)為T＝V，當目標圈復雜度為V＋1時，個體包含的數(shù)據(jù)組數(shù)變?yōu)門＝V＋1。個體組數(shù)變化有兩個途徑：①保留個體原來的V組數(shù)據(jù)，在步驟 （6）的交叉操作中，被選中進行交叉的兩個個體，彼此添加對方的一組數(shù)據(jù)；②執(zhí)行完步驟 （6）中的選擇、交叉、變異操作后為每個個體再隨機生成一組數(shù)據(jù)。

以常用的三角形程序為例說明本文基路徑覆蓋測試用例自動生成的動態(tài)方法。

圖4 算法模型

為了得到用例執(zhí)行后經(jīng)過的路徑向量以及判斷是否存在未經(jīng)過的分支，需要對源程序進行插裝。考慮到每行都插裝工作量過大、得到的矩陣向量會過長，在每個分支的第一個語句后進行插裝。通過判定節(jié)點統(tǒng)計程序中的分支數(shù)n，向量以數(shù)組C［n］來表示，通過數(shù)組B［n］來標記是否經(jīng)過某個分支，兩數(shù)組元素初始值都為零。將C［m］＝1，B［m］＝1插裝在第m＋1個分支中第一個語句后。執(zhí)行完一個用例后就可以得到該用例對應的路徑向量。執(zhí)行完所有用例后就知道是否存在未經(jīng)過的分支。插裝后的源程序如下：

通過對參數(shù)的分析，確定參數(shù)為a，b，c，數(shù)據(jù)類型為int型。不妨設int型為8位，每個參數(shù)用8位的二進制編碼表示，則一組數(shù)據(jù)可以用24位的二進制編碼表示。設進化過程中目標圈復雜度大小為V，則一個個體可以用V個24位的二進制編碼表示。

圖5 三角形問題個體組成

以遺傳算法作為尋優(yōu)搜索算法，種群大小設定為500，最大進化代數(shù)為100，以每個個體得到的矩陣向量的秩作為個體的適應度。選擇運算中保留適應度最高的個體，并用最優(yōu)個體替換最差個體，交叉運算中交叉率設為0.8，變異運算中變異率設為0.02。每個個體包含的數(shù)據(jù)組數(shù)增加時通過執(zhí)行完步驟 （6）中的選擇、交叉、變異操作后為每個個體再隨機生成一組數(shù)據(jù)。

算法代碼實現(xiàn)后統(tǒng)計運行50次的結(jié)果，發(fā)現(xiàn)有47運行能得到三角形程序的真實邏輯圈復雜度4，三次運行得到的圈復雜度為3，得到滿足基路徑覆蓋百分之百的測試用例的概率為94%，所需要的進化代數(shù)最少為17次，最大為82次，平均為32.6次。試驗結(jié)果表明本文提出算法能夠有效地生成滿足基路徑覆蓋百分之百的測試用例。

4 結(jié)束語

傳統(tǒng)算法先生成程序的結(jié)構(gòu)圖，然后通過結(jié)構(gòu)圖靜態(tài)的分析出程序的圈復雜度，這種的靜態(tài)的分析忽視了程序的語言間的相互依賴關(guān)系，求出的圈復雜度可能比實際的程序圈復雜度大，本文算法，不需要生成程序的結(jié)構(gòu)圖，動態(tài)運行程序，通過進化的方法逐漸逼近程序的實際圈復雜度；

傳統(tǒng)算法需要針對基路徑組的每條路徑，逐條求出覆蓋每條路徑的測試用例，本文算法在求出程序的實際圈復雜度的同時，得到了覆蓋整個基路徑組的測試用例；

傳統(tǒng)算法因為忽視了語義間的相互依賴關(guān)系，可能存在路徑不可達問題，也就無法生成不可達路徑的測試用例，本文算法動態(tài)運行程序，不存在路徑不可達問題。

［1］CHEN Jifeng.Framework of automatic test data generation for software structure ［J］.Computer Engineering，2007，33 （8）：3425－3428（in Chinese）.［陳繼鋒 .一種結(jié)構(gòu)測試數(shù)據(jù)自動生成的框架 ［J］.計算機工程，2007，33 （8）：3425－3428.］

［2］LI Yonghua.Research of methods of getting the basic paths dynamically without unreachable paths （in Chinese）.［李勇華.消除不可達路徑的基路徑自動獲取方法研究 ［J］.武漢理工大學學報，2009，23 （3）：23－29.］

［3］XIAO Liqiong.The core of software testing ［M］.Beijing：Electronic Industry Press，2011 （in Chinese）. ［肖利瓊.軟側(cè)之魂 ［M］.北京：電子工業(yè)出版社，2011.］

［4］RONG Zhiwen，LI Jia，CAI Lizhi.Software testing method researching of cyclomatic complexity ［J］.Software Industry and Engineering，2012，6 （1）：28－34 （in Chinese）.［榮志文，李嘉，蔡立志.基于圈復雜度的軟件測試方法研究 ［J］.軟件產(chǎn)業(yè)與工程，2012，6 （1）：28－34.］

［5］JIA Songtao，ZHANG Hongwei.Framework and application of testing data generation based on paths ［J］.Micro Computer Information （Management），2010，26 （2－3）：45－54 （in Chinese）. ［賈松濤，張紅衛(wèi).面向路徑的測試數(shù)據(jù)生成框架及應用 ［J］.微計算機信息 （管控一體化），2010，26 （2－3）：45－54.］

［6］Kostas Sturgeon.Representation and reasoning with non－binary constraints［D］.The Univ of Strathclyde，2010.

［7］Ngo M N，Tan H B K.Heuristics－based infeasible path detection for dynamic test data generation ［J］.Information and Software Technology，2008，50 （7／8）：641－655.

［8］Brahman P，Marian S，Hussein H，et al.Automated analysis of Reo circuits using symbolic execution ［J］.Electronic Notes in Theoretical Computer Science，2009 （255）：137－158.

［9］LI Junyi.Research on testing case generate automatically ［D］.Changsha：Hunan University，2007 （in Chinese）.［李軍義.軟件測試用例自動生成技術(shù)研究 ［D］.長沙：湖南大學，2007.］

［10］CAO Fengyan.An application research of creating test cases automatically based on basie path test ［D］.Dalian：Dalian Marring Univesity，2007 （in Chinese）. ［曹烽燕.基于基本路徑測試的測試用例自動生成應用研究 ［D］.大連：大連海事大學，2007.］