Java自動(dòng)化基本路徑測試技術(shù)研究

, , ,,

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

0 引言

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

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

1 控制流圖定義與構(gòu)造

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

1.1 控制流圖結(jié)構(gòu)

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

圖1 分支結(jié)構(gòu)

1.2 數(shù)據(jù)結(jié)構(gòu)

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

圖2 控制流圖節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)

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

1.3 控制流圖生成

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

圖3 控制流圖生成

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

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

在控制流圖生成過程中，對分支節(jié)點(diǎn)的id從1進(jìn)行編號(hào)，其子節(jié)點(diǎn)稱為分支子節(jié)點(diǎn)，也即branchNo和branchGo屬性非負(fù)值的節(jié)點(diǎn)，通過記錄分支子節(jié)點(diǎn)的 (branchNo, branchGo)屬性值即可唯一標(biāo)識(shí)一條路徑。

2 基本路徑生成

2.1 算法思想

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

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

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

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

2.2 基本路徑生成算法

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

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

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

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

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

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

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

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

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

2.3 算法證明

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

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

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

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

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

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

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

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

圖4 不存在重復(fù)片段的路徑

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

圖5 存在重復(fù)片段的路徑

綜合以上三點(diǎn)證明，生成的路徑集合為基本路徑集合。

3 程序插樁

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

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

插樁語句形式如下：

PathRec path = new PathRec();

path.addBranchNode(BranchNode node);

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

4 基本路徑覆蓋測試

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

圖6 測試流程圖

5 實(shí)驗(yàn)與分析

以被測程序Sample為例進(jìn)行實(shí)驗(yàn)，對基本路徑測試方法進(jìn)行驗(yàn)證，Sample程序如下：

public class Sample{

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

int sum = 0, average = 0;

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

for(int i=0;i

if(array[i] >= 0)

sum += array[i];

else

sum -= array[i];

}

average = sum/length;

return average;

}

首先，構(gòu)造被測程序的控制流圖，圖7為生成的控制流圖。

圖7 Sample控制流圖

然后，對程序進(jìn)行插樁，插樁后被測程序?yàn)椋?/p>

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)。

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

6 結(jié)論

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

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

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

[9] 馮俊池, 于 磊. 測試數(shù)據(jù)生成中遺傳算法的改進(jìn)[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 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.