, , ,,

(后勤科學與技術研究所，北京 100071)

0 引言

單元測試是保證軟件質量的重要手段[1]，能夠在前期有效發(fā)現(xiàn)代碼中存在的問題，避免將缺陷引入軟件。在單元測試中，主要的覆蓋準則有語句覆蓋、判定覆蓋、條件覆蓋、判定/條件覆蓋、條件組合覆蓋和路徑覆蓋，其中路徑覆蓋是最強的覆蓋準則，通過設計測試用例覆蓋程序中所有可能的路徑，發(fā)現(xiàn)其中存在的缺陷和錯誤。但當路徑數(shù)量很大，尤其是存在循環(huán)時，很難做到完全覆蓋，需要把路徑數(shù)量壓縮到一定程度?；韭窂綔y試方法[2]在一定程度上解決了這一問題，通過只針對一組合理的路徑即基本路徑集合進行覆蓋測試，而不是窮舉所有路徑，有效避免了路徑爆炸問題。

目前針對基本路徑集求解已有很多研究[3-5]，如路徑字符串組合算法[3]、基于圖深度優(yōu)先搜索算法等[4]，基于狀態(tài)圖的測試路徑自動生成算法[5]等?，F(xiàn)有方法主要以控制流圖為輸入來生成基本路徑集合[6-8]，減少了人工分析得到基本路徑集合的工作量。為了減少由代碼生成控制流圖以及執(zhí)行路徑與基本路徑集合比對的工作量，本文提出了針對Java源碼的路徑測試自動化方法，首先通過對Java代碼的分析構建控制流圖和實現(xiàn)程序插樁，保持控制流圖和代碼插樁中節(jié)點的一致性，然后通過控制流圖生成基本路徑集合，最后執(zhí)行插樁后被測程序判斷測試數(shù)據(jù)對基本路徑集合的覆蓋程度。

1 控制流圖定義與構造

基本路徑集通過分析被測程序的控制流圖來得到，因此在基本路徑測試過程中，首先要根據(jù)程序流程來繪制控制流圖?？刂屏鲌D是描述程序流程的一種圖示方法，以結點和邊的方式表示了一個程序執(zhí)行過程中會遍歷到的所有路徑。

1.1 控制流圖結構

將控制流圖涉及到的分支結構主要劃分為4種：while/for循環(huán)，do-while循環(huán)，if-else分支，switch-case分支，如圖1所示。其中每條有向邊由父節(jié)點指向子節(jié)點，邊上標注的“L”和“R”分別代表子節(jié)點是父節(jié)點的左子節(jié)點和右子節(jié)點，由于switch節(jié)點可以有多個子節(jié)點，因此其子節(jié)點按1到n的順序進行標注。

圖1 分支結構

1.2 數(shù)據(jù)結構

控制流圖中的節(jié)點主要分為三類，數(shù)據(jù)結構如圖2所示?；竟?jié)點類型BranchNode代表了普通節(jié)點，屬性id的值為正整數(shù)，每個節(jié)點的id是唯一的，屬性visited為布爾值，用來在路徑遍歷時標記節(jié)點是否被訪問過，屬性leftChild和rightChild分別記錄了節(jié)點的左右子節(jié)點。WhileForBranchNode為while/for循環(huán)結構和do-while循環(huán)結構的條件判斷節(jié)點，相比普通節(jié)點增加了exitNode屬性，記錄了循環(huán)的退出節(jié)點，用于在循環(huán)遍歷過程中退出循環(huán)。SwitchBranchNode為switch-case分支結構的switch節(jié)點，與普通節(jié)點不同，switch節(jié)點可能包含不止兩個子節(jié)點，因此采用屬性children記錄子節(jié)點列表。

圖2 控制流圖節(jié)點的數(shù)據(jù)結構

每個節(jié)點具有兩個屬性branchNo和branchGo，分別記錄了該節(jié)點所屬上一層分支節(jié)點和自分支節(jié)點后的分支編號，對于非分支節(jié)點的子節(jié)點，該處值均取-1，假設id為1的節(jié)點為分支節(jié)點，下面有兩個分支，分別有節(jié)點2和3，則節(jié)點2和3的(branchNo, branchGo)屬性值為(1, 0)和(1, 1)，若節(jié)點1下不止兩個分支，則子節(jié)點的branchGo值依次取0，1，2等整數(shù)。二元組(branchNo, branchGo)記錄了節(jié)點在程序流圖所處的位置，一條路徑即可由(branchNo, branchGo)的列表標識。

1.3 控制流圖生成

由被測程序生成控制流圖主要分為3個步驟：詞法分析、語法分析和控制流圖構造，如圖3所示。

圖3 控制流圖生成

詞法分析和語法分析采用Antlr工具輔助實現(xiàn)，Antlr可以根據(jù)用戶提供的語法文件自動生成相應的詞法/語法分析器。通過詞法分析，將被測程序解析為離散的字符組，即Tokens，包括關鍵字、標識符、符號和操作符等，供語法分析器使用。語法分析器將Tokens組織起來，轉換為AST(Abstract Syntax Tree，抽象語法樹)。樹上的每個節(jié)點都表示源代碼中的一種結構，為下一步程序控制流圖的構造提供信息。

控制流圖構造通過對AST進行遍歷實現(xiàn)，將程序中的語句劃分為基本塊，基本塊是順序執(zhí)行的語句序列，其中只有一個入口和出口，針對Java程序，基本塊的入口語句只能是程序的第一條語句，轉移語句(break、continue等)的目標語句或緊跟在條件轉移語句(if-else、while、for、switch-case等)之后的語句。一條入口語句到下一條入口語句間的所有語句構成一個基本塊?；緣K即對應于控制流圖中的節(jié)點，基本塊之間的轉移關系為控制流圖中的邊，通過基本塊的劃分和轉移關系的確定，即可得到被測程序的控制流圖。

在控制流圖生成過程中，對分支節(jié)點的id從1進行編號，其子節(jié)點稱為分支子節(jié)點，也即branchNo和branchGo屬性非負值的節(jié)點，通過記錄分支子節(jié)點的 (branchNo, branchGo)屬性值即可唯一標識一條路徑。

2 基本路徑生成

2.1 算法思想

通過深度優(yōu)先搜索遍歷控制流圖，在不存在循環(huán)的情況下，每遇到一個分支節(jié)點，則復制當前的子路徑，并針對后繼的每個節(jié)點繼續(xù)進行搜索；由于循環(huán)的存在，需要避免搜索算法陷入死循環(huán)無法結束，為每個節(jié)點設置訪問標志，當再次遍歷到已訪問過的節(jié)點時，有如下3種情況：

1)while/for/do-while的判斷節(jié)點:直接訪問退出節(jié)點，因已訪問過該節(jié)點的分支，本次直接退出循環(huán)，遍歷后面的節(jié)點。

2)分支節(jié)點:選擇其中一個節(jié)點繼續(xù)，出現(xiàn)該種情況原因是存在分支嵌套或分支并列，已訪問過該節(jié)點的分支，本次遍歷不再訪問所有分支，避免產(chǎn)生冗余路徑。

3)其他節(jié)點:選擇其子節(jié)點繼續(xù)，出現(xiàn)該種情況原因是存在分支嵌套或分支并列。由于while/for循環(huán)體的最后一個節(jié)點左側子節(jié)點為空，右側子節(jié)點指向循環(huán)判斷語句，因此需要判斷當前節(jié)點是否是while/for循環(huán)體，若是，則選擇右側節(jié)點繼續(xù)遍歷，否則，選擇左側節(jié)點繼續(xù)遍歷。

2.2 基本路徑生成算法

算法為visitPrimePath(currentNode, path)，其中currentNode代表當前節(jié)點，初始輸入為程序入口節(jié)點，path用于記錄路徑，算法步驟如下：

步驟1： 如果currentNode是結束節(jié)點，終止，否則轉到步驟2；

步驟2：如果currentNode.visited為true，執(zhí)行步驟2.1，否則，轉到步驟3；

步驟2.1：如果節(jié)點類型為while/for/do-while循環(huán)的判斷節(jié)點，取循環(huán)的結束節(jié)點currentNode.exitNode，執(zhí)行visitPrimePath(currentNode.exitNode, path)，否則執(zhí)行步驟2.2；

步驟2.2：如果類型為switch，對第一個子節(jié)點firstChildNode執(zhí)行visitPrimePath(firstChildNode, path)，否則執(zhí)行步驟2.3；

步驟2.3：若currentNode是分支子節(jié)點則將其加入path，如果節(jié)點的左子節(jié)點leftChild不為null，執(zhí)行visitPrimePath(currentNode.leftChild, path)，否則，執(zhí)行visitPrimePath(currentNode.rightChild, path)；

步驟3：若currentNode是分支子節(jié)點則將其加入path，令currentNode.visited=true，執(zhí)行步驟3.1；

步驟3.1：如果是switch類型，依次對每個子節(jié)點childenNode執(zhí)行visitPrimePath(currentNode.exitNode, path)，否則執(zhí)行步驟3.2；

步驟3.2：判斷左子節(jié)點是否為null，如不為null，執(zhí)行visitPrimePath(currentNode.leftChild, path)；判斷右子節(jié)點是否為null，如不為null，執(zhí)行visitPrimePath(currentNode.rightChild, path)。

2.3 算法證明

算法功能正確性證明如下：

1)每條程序路徑都是獨立路徑，即每條路徑都至少包含一條其他路徑未包含的邊。

在程序流圖遍歷過程中，第一次遇到分支節(jié)點時，算法分別選擇不同的分支繼續(xù)遍歷；當再次遇到訪問過的節(jié)點時，則當前路徑已包含了其他路徑未包含的邊，則在當前節(jié)點只選擇其中一個繼續(xù)進行遍歷。因此能夠保證生成的每一條路徑包含獨立的邊，即每條程序路徑都是獨立路徑。

2)程序中所有的邊都被訪問。

由算法visitPrimePath(currentNode, path)第3步可以看出，針對switch節(jié)點，其所有的子節(jié)點都被訪問，即所有分支均被訪問；針對其他節(jié)點，如果子節(jié)點不為空，則繼續(xù)遍歷，即訪問了當前節(jié)點所有分支。因此，程序中所有的邊都被訪問。

3)程序中的所有的、不屬于基本路徑集的路徑都可由基本路徑集中的路徑經(jīng)過線性運算得到。

對于一條需要通過基本路徑線性運算得到的路徑，稱之為目標路徑。分為兩種情況來討論：

第一種情況，目標路徑中不包含重復片段，如圖4所示，左側為目標路徑，右側路徑1到路徑2n-1來自生成的路徑集合。目標路徑由n條邊組成，路徑1包含了片段a，路徑3包含了片段b，由第1)、2)的證明可知，路徑1和3是來自于生成的路徑集合(這里假設不存在一條路徑包含a和b兩個片段的情況，即路徑1和3不同)，則存在路徑2和路徑3有著相同的子路徑x且節(jié)點1后的路徑不同，即節(jié)點1為分支節(jié)點，由算法可知，分支節(jié)點前的所有不同子路徑必經(jīng)過同一條子路徑到達結束節(jié)點，對于路徑1和路徑2，節(jié)點1前的子路徑不同，必然會存在一條路徑2使得節(jié)點1后的子路徑相同，路徑1、2、3計算可得到路徑a-b-z，依次推導，可得路徑1、2、3…2n-1均在生成的路徑集中且可以通過線性計算得到目標路徑。

圖4 不存在重復片段的路徑

第二種情況，目標路徑中存在重復片段，如圖5所示，當程序中存在循環(huán)時，目標路徑中可能會存在重復片段，以圖5(a)為例，假設目標路徑為x-a-b-a-b-a-c-y，由路徑生成算法可知，生成的路徑集合中包括x-a-c-y和x-a-b-a-c-y，經(jīng)過簡單線性運算可得到子路徑b-a，與路徑x-a-b-a-c-y相加即可得到目標路徑，圖5(b)中的程序控制流圖亦是如此，因此程序中存在循環(huán)時，重復片段也可通過生成路徑的線性運算得到。即程序中的其他路徑都可由算法生成的路徑集合中的路徑經(jīng)過線性運算得到。

圖5 存在重復片段的路徑

綜合以上三點證明，生成的路徑集合為基本路徑集合。

3 程序插樁

為了記錄程序實際執(zhí)行過程中的路徑，需要在程序中插入記錄執(zhí)行路徑信息的語句，即程序插樁。主要思路是在程序的分支節(jié)點處插入語句記錄程序執(zhí)行時的分支走向，執(zhí)行結束后，每個節(jié)點處的分支走向即為此次執(zhí)行的路徑。為了便于與基本路徑集合中的路徑進行比對，在插樁時采用與程序控制流圖節(jié)點一致的數(shù)據(jù)結構。

遍歷AST時，在Token流中指定位置插入語句，最后輸出Token流即為插樁后的被測程序。在每個可能的分支處插入節(jié)點，與控制流圖中的節(jié)點保持一致。

插樁語句形式如下：

PathRec path = new PathRec();

path.addBranchNode(BranchNode node);

采用PathRec記錄節(jié)點序列，在程序執(zhí)行過程中，通過addBranchNode方法收集執(zhí)行路徑上的節(jié)點，即可得到執(zhí)行路徑。

4 基本路徑覆蓋測試

基本路徑覆蓋測試的目標是使程序的每一條基本路徑都被執(zhí)行。通過基本路徑集合的獲取和程序插樁，可以判斷在測試過程中是否覆蓋了基本路徑集合。測試流程如圖6所示。以測試數(shù)據(jù)[9-10]為輸入，執(zhí)行插樁后的被測程序，并獲取執(zhí)行路徑，將執(zhí)行路徑并與基本路徑集合進行比對，若相同則從基本路徑集合中刪除該路徑，直至路徑集合為空，則實現(xiàn)了對被測程序的路徑覆蓋。針對特定的測試數(shù)據(jù)集合，也可以判斷其對基本路徑的覆蓋程度。

圖6 測試流程圖

5 實驗與分析

以被測程序Sample為例進行實驗，對基本路徑測試方法進行驗證，Sample程序如下：

public class Sample{

public int test(int array[], int length){

int sum = 0, average = 0;

綜上所述，在交通建設過程中，路橋建設占據(jù)重要地位。特別是高速公路橋梁施工建設方面，樁基逐漸成為橋梁工程的主要內(nèi)容。而鉆孔灌注樁施工技術發(fā)展趨于成熟，但仍會受地質條件等因素影響，制約施工質量。在這種情況下，應合理化地改善鉆孔灌注樁技術，確保高速公路橋梁建設更穩(wěn)定安全。

for(int i=0;i

if(array[i] >= 0)

sum += array[i];

else

sum -= array[i];

}

average = sum/length;

return average;

}

首先，構造被測程序的控制流圖，圖7為生成的控制流圖。

圖7 Sample控制流圖

然后，對程序進行插樁，插樁后被測程序為：

import path.PathRec;

public class Sample {

public static PathRec path = new PathRec();

public int test(int array[], int length) {

int sum = 0, average = 0;

for (int i = 0;i< length; i++) {

path.addBranchNode(new BranchNode(1, 0));

if (array[i] >= 0) {

path.addBranchNode(new BranchNode(2, 0));

sum += array[i];

} else {

path.addBranchNode(new BranchNode(2, 1) );

sum -= array[i];

}

}

path.addBranchNode(new BranchNode(1, 1));

average = sum / length;

return average;

}

}

根據(jù)生成的控制流圖生成基本路徑集合，基本路徑集合為：

(1,0) ->(2,0) ->(1,1)，

(1,0) ->(2,1) ->(1,1)，

(1,1)。

最后，采用人工或自動方式生成測試數(shù)據(jù)，執(zhí)行插樁后的被測程序，獲取測試數(shù)據(jù)對應的執(zhí)行路徑，驗證測試數(shù)據(jù)集合對基本路徑的滿足程度。針對Sample程序， 當測試數(shù)據(jù)為{[2,1],1}，{[-2,1],1}，{[2,1],0}時，即可實現(xiàn)對基本路徑的覆蓋。

6 結論

本文通過對Java源碼進行分析，構建程序的控制流圖，同時對被測程序進行插樁；根據(jù)控制流圖生成基本路徑集合，在插樁后的被測程序執(zhí)行過程中記錄執(zhí)行路徑；通過執(zhí)行路徑和基本路徑的自動化比對，判斷測試數(shù)據(jù)對基本路徑集合的覆蓋程度。通過實驗證明了該方法在Java程序基本路徑測試中的有效性。

下一步將在路徑生成的過程中對分支條件進行分析處理，采用符號執(zhí)行、約束求解等方法來篩選出不可行路徑，從而減少后期測試工作量，提高測試效率。

參考文獻：

[1] 張小松，等譯. 軟件測試 [M]. 北京: 機械工業(yè)出版社, 2006.

[2] 施冬梅. 嵌入式軟件路徑覆蓋測試的研究[J]. 計算機測量與控制, 2010, 18(10): 2236-2237.

[3] 王 敏, 陳亞光. 用于基本路徑測試的路徑字符串組合算法[J]. 計算機工程與科學, 2013, 35(12):134-140.

[4] 吳取勁, 陽小華, 鹿江春, 等. 一種基于圖深度優(yōu)先搜索的基本路徑集自動生成優(yōu)算法[J]. 南華大學學報:自然科學版, 2012, 26(12):87-90.

[5] 李 鵬, 彭祥偉, 周 喜, 等. 基于狀態(tài)圖的測試路徑自動生成[J]. 計算機工程, 2011, 37(1):25-29.

[6] 張廣梅, 李曉維, 韓叢英. 路徑測試中基本路徑集的自動生成[J]. 計算機工程, 2007, 33(22):195-197.

[7] 韓 寒, 姜淑娟. 路徑測試中基本路徑集自動生成方法的研究[J]. 微電子學與計算機, 2013, 30(1):104-109.

[8] 王 冠, 景小寧, 王彥軍. 基本路徑測試中的McCabe算法改進與應用[J]. 哈爾濱理工大學學報, 2010, 15(1):48-51.

[9] 馮俊池, 于 磊. 測試數(shù)據(jù)生成中遺傳算法的改進[J]. 計算機輔助設計與圖形學學報, 2015, 27 (10) :2008-2014.

[10] Anand S, Burke E K, Chen T Y, et al. An orchestrated survey of methodologies for automated software test case generation[J]. Journal of Systems and Software, 2013, 86(8): 1978-2001.