軟件質(zhì)量保證與測(cè)試4.4基本路徑覆蓋第4章白盒測(cè)試SoftwareQualityAssuranceandTesting

在把程序抽象為有向圖之后，我們把從程序入口到出口經(jīng)過的各個(gè)節(jié)點(diǎn)的有序排列稱為路徑，可用路徑表達(dá)式來(lái)表示這樣的一條路徑。路徑表達(dá)式可以是節(jié)點(diǎn)序列，也可以是弧序列，例如有如圖所示程序控制流圖，其可能的程序執(zhí)行路徑如下表所示。程序中的路徑

需要注意的是，程序中存在循環(huán)時(shí)，如果執(zhí)行循環(huán)的次數(shù)不同，那么對(duì)應(yīng)的執(zhí)行路徑就不同，例如表中路徑3和路徑4就是由于程序執(zhí)行循環(huán)次數(shù)不同而形成的不同的路徑。程序中的路徑路徑編號(hào)弧序列表示節(jié)點(diǎn)序列表示1acde1-2-3-4-52abe1-2-4-53abefabe1-2-4-5-1-2-4-54abefabefabe1-2-4-5-1-2-4-5-1-2-4-55abefacde1-2-4-5-1-2-3-4-5..................

基本的路徑表達(dá)，采用的是節(jié)點(diǎn)序列，或者是弧序列，例如表中路徑1為acde，或者1-2-3-4-5。為增強(qiáng)路徑表達(dá)能力，可以在路徑表達(dá)式引入加法和乘方，加法可以表達(dá)IF分支結(jié)構(gòu)，乘方可以表達(dá)循環(huán)結(jié)構(gòu)。

設(shè)有程序控制流圖如右圖所示，則它所有可能的路徑可表達(dá)為：(ac+bd)e(fe)n，n為循環(huán)的次數(shù)。程序中的路徑完全的路徑覆蓋一般不可能

程序中的一條IF語(yǔ)句就會(huì)形成兩條路徑。兩條IF語(yǔ)句的串聯(lián)就會(huì)有四條路徑，在實(shí)際問題中，即使一個(gè)不太復(fù)雜的程序，其可能的路徑都是一個(gè)龐大的數(shù)字，而如果程序中存在循環(huán)，則可能的路徑就是天文數(shù)字。完全的路徑覆蓋一般不可能設(shè)有如圖所示的一個(gè)程序流程圖，如果程序中循環(huán)的執(zhí)行上限是10次，那么可能有多少條程序執(zhí)行路徑？答案是，可能的程序執(zhí)行路徑條數(shù)L：=40+41+42+43+……+410=1398101完全的路徑覆蓋一般不可能

假設(shè)圖中所有可能的路徑都是可執(zhí)行路徑，某臺(tái)計(jì)算機(jī)對(duì)該程序執(zhí)行一次循環(huán)大約需要10微秒，那么把所有可能的路徑都測(cè)試一遍，大約需要的時(shí)間為：

1398101*10/1000000≈14（秒）

假設(shè)該計(jì)算機(jī)一年365天每天24小時(shí)不停機(jī)，如果程序中循環(huán)的執(zhí)行次數(shù)上限是20次，那么把所有可能的路徑都測(cè)試一遍大約需要4072小時(shí)，如果循環(huán)次數(shù)上限是100次，則大約需要6.79*1047年。由此可見，對(duì)于實(shí)際的應(yīng)用程序，做路徑窮舉測(cè)試是不可行的?；韭窂礁采w

既然無(wú)法對(duì)一個(gè)實(shí)際的應(yīng)用程序進(jìn)行路徑的窮舉測(cè)試，那么就只能選取部分路徑來(lái)進(jìn)行測(cè)試?；韭窂礁采w就是在程序控制流圖的基礎(chǔ)上，通過分析控制流圖的環(huán)路復(fù)雜性，然后導(dǎo)出程序獨(dú)立路徑集合，再設(shè)計(jì)測(cè)試用例覆蓋所有獨(dú)立路徑的一種動(dòng)態(tài)白盒測(cè)試方法。由于基本路徑覆蓋把程序中的所有節(jié)點(diǎn)都覆蓋到了，所以程序中的每一條可執(zhí)行語(yǔ)句也至少會(huì)被執(zhí)行一次，也就是說滿足基本路徑覆蓋就一定是滿足語(yǔ)句覆蓋的。基本路徑覆蓋

所謂獨(dú)立路徑是指，和其他的獨(dú)立路徑相比，至少有一個(gè)路徑節(jié)點(diǎn)是新的，未被其他獨(dú)立路徑所包含。

從程序的環(huán)路復(fù)雜度可導(dǎo)出程序基本路徑集合中的獨(dú)立路徑條數(shù)：

程序獨(dú)立路徑條數(shù)=程序的環(huán)路復(fù)雜度

這是確保程序中每個(gè)可執(zhí)行語(yǔ)句至少執(zhí)行一次所必須的測(cè)試用例數(shù)目的下界。

得出程序獨(dú)立路徑條數(shù)后，再根據(jù)控制流圖，得出各條獨(dú)立路徑。所有獨(dú)立路徑組成獨(dú)立路徑集合，也就是基本路徑集合?；韭窂礁采w畫出程序控制流圖2)計(jì)算程序環(huán)路復(fù)雜性3)確定獨(dú)立路徑集合4)為每條獨(dú)立路徑設(shè)計(jì)測(cè)試用例

基本路徑覆蓋應(yīng)當(dāng)確保基本路徑集中的每一條路徑都能被執(zhí)行到。一般是為每條獨(dú)立路徑設(shè)計(jì)一個(gè)測(cè)試用例，執(zhí)行這個(gè)測(cè)試用例時(shí)，就能確保該獨(dú)立路徑會(huì)被執(zhí)行。

借助于專門的工具軟件，導(dǎo)出控制流圖和確定基本路徑的過程均可以自動(dòng)完成。

基本路徑覆蓋測(cè)試法的基本步驟如下：基本路徑覆蓋

在基本路徑測(cè)試中，稱為圖形矩陣的數(shù)據(jù)結(jié)構(gòu)很有用。利用圖形矩陣可以確定控制流圖的環(huán)路復(fù)雜度，也就是基本路徑集合中基本路徑的條數(shù)。一個(gè)圖形矩陣是—個(gè)方陣，其行/列都是控制流圖中的節(jié)點(diǎn)，每行和每列依次對(duì)應(yīng)到一個(gè)被標(biāo)識(shí)的節(jié)點(diǎn)，矩陣元素對(duì)應(yīng)到節(jié)點(diǎn)間的連接（即?。?。在圖形矩陣中控制流圖的每一個(gè)節(jié)點(diǎn)都用數(shù)字加以標(biāo)識(shí)，每一條邊都用字母加以標(biāo)識(shí)。如果在控制流團(tuán)中第i個(gè)結(jié)點(diǎn)到第j個(gè)結(jié)點(diǎn)有一個(gè)名為x的邊相連接，則在對(duì)應(yīng)的圖形矩陣中第i行/第j列有—個(gè)非空的元素?；韭窂礁采w

對(duì)每個(gè)矩陣項(xiàng)加入連接權(quán)值，圖形矩陣就可以用于在測(cè)試中評(píng)估程序的控制結(jié)構(gòu)，連接權(quán)值為控制流提供了另外的信息。最簡(jiǎn)單的情況下，連接權(quán)值是1或0，分別表示存在連接或不存在連接。但是，連接權(quán)值可以被賦予更多有用的屬性，如：執(zhí)行連接的概率；穿越連接的處理時(shí)間；穿越連接時(shí)所需的內(nèi)存；穿越連接時(shí)所需的資源等。

如果連接權(quán)值為1表示存在連接，那么圖中有兩個(gè)元素為1的行所代表的節(jié)點(diǎn)就一定是一個(gè)判定節(jié)點(diǎn)，通過計(jì)算圖形矩陣中有兩個(gè)元素為1的行的個(gè)數(shù)，就可以得出總的判定節(jié)點(diǎn)數(shù)，從而得出環(huán)路復(fù)雜度。這是確定環(huán)路復(fù)雜度的另一種方法。基本路徑覆蓋

給出一個(gè)圖形矩陣的實(shí)例如下：左邊為程序控制流圖，右邊為對(duì)應(yīng)的圖形矩陣?；韭窂礁采w

圖形矩陣中，有兩個(gè)元素為1的行有3個(gè)，所以判定節(jié)點(diǎn)數(shù)為3，從而得出環(huán)路復(fù)雜度為3+1=4。基本路徑覆蓋實(shí)例

下面我們來(lái)看一個(gè)基本路徑覆蓋的例子。

請(qǐng)針對(duì)程序段IsLeap，為變量year設(shè)計(jì)測(cè)試用例，滿足基本路徑覆蓋，假設(shè)year的取值范圍為1000——9999。

基本路徑覆蓋實(shí)例intIsLeap(intyear){ if(year%4==0){ if(year%100==0){ if(year%400==0) leap=1; else leap=0; }elseleap=1; }else leap=0;returnleap;}基本路徑覆蓋實(shí)例(1)繪制出程序代碼對(duì)應(yīng)的控制流圖，如下圖所示?；韭窂礁采w實(shí)例(2)計(jì)算環(huán)路復(fù)雜度V(G)。 V(G)=E-N+2=14-12+2=4；V(G)=判定點(diǎn)數(shù)+1=3+1=4

V(G)=區(qū)域數(shù)=4(3)確定獨(dú)立路徑集合。 1-2-3-11-12 1-2-4-5-10-11-12 1-2-4-6-7-9-10-11-12 1-2-4-6-8-9-10-11-12(4)設(shè)計(jì)測(cè)試用例。

針對(duì)各條獨(dú)立路徑設(shè)計(jì)的測(cè)試用例，如表所示?；韭窂礁采w實(shí)例測(cè)試用例編號(hào)測(cè)試數(shù)據(jù)預(yù)期執(zhí)行結(jié)果測(cè)試路徑1year