測(cè)試用例之路徑覆蓋

路徑覆蓋測(cè)試呂金和(沈陽市電化教育館，遼寧沈陽110032)摘要隨著軟件的廣泛應(yīng)用及其規(guī)模和復(fù)雜度不斷地提高，軟件測(cè)試的方法也有許多。本文討論了完全路徑覆蓋測(cè)試方法和基于控制流圖的路徑測(cè)試的改進(jìn)方法。關(guān)鍵詞完全路徑覆蓋；基于控制流圖1引言軟件測(cè)試的步驟是單元測(cè)試、集成測(cè)試、系統(tǒng)測(cè)試、確認(rèn)測(cè)試和回歸測(cè)試。單元測(cè)試是軟件測(cè)試的基本組成部分，也是最重要的部分之一。而單元測(cè)試主要采用的是白盒測(cè)試的技術(shù)。白盒測(cè)試又稱結(jié)構(gòu)測(cè)試、邏輯驅(qū)動(dòng)測(cè)試或基于程序的測(cè)試。一般用來分析程序的內(nèi)部結(jié)構(gòu)。它依賴于對(duì)程序細(xì)節(jié)的嚴(yán)密驗(yàn)證，針對(duì)特定條件和循環(huán)設(shè)計(jì)測(cè)試用例，對(duì)程序的邏輯路徑進(jìn)行測(cè)試。通過在程序的不同點(diǎn)檢驗(yàn)程序狀態(tài)，來判定其實(shí)際情況是否和預(yù)期的狀態(tài)相一致。用這種方法進(jìn)行程序測(cè)試時(shí)，測(cè)試者可以看到被測(cè)程序，并利用其分析程序的內(nèi)部構(gòu)造。因此，白盒測(cè)試要求對(duì)被測(cè)程序的結(jié)構(gòu)特性做到一定程度的覆蓋，并以軟件中的某類成分是否都已經(jīng)得到測(cè)試為準(zhǔn)則來判斷軟件測(cè)試的充分性，也稱為基于覆蓋的測(cè)試技術(shù)。例如，語句覆蓋是一種邏輯覆蓋準(zhǔn)則，它要求選擇測(cè)試數(shù)據(jù)使得程序中所有語句都得到運(yùn)行，并根據(jù)是否所有語句都得到了運(yùn)行來決定測(cè)試是否可以終止。到目前為止，已提出了幾十種覆蓋技術(shù)。在這些覆蓋的技術(shù)中，覆蓋率最高的就是路徑覆蓋技術(shù)。路徑覆蓋，要求程序的每條可能路徑都至少執(zhí)行一次，如果程序中有環(huán)，則要求每個(gè)環(huán)至少經(jīng)過一次。一般來說，語句覆蓋是很弱的邏輯覆蓋標(biāo)準(zhǔn)，判斷覆蓋比語句覆蓋強(qiáng)，條件覆蓋通常比判定覆蓋強(qiáng)，判定一條件覆蓋是判定覆蓋和條件覆蓋的綜合，條件組合覆蓋則比前面幾種覆蓋標(biāo)準(zhǔn)要強(qiáng)，但并不一定比路徑覆蓋強(qiáng)，下面我們討論的完全路徑覆蓋測(cè)試方法和基于控制流圖的路徑測(cè)試的改進(jìn)方法研究。2完全路徑覆蓋測(cè)試方法雖然路徑覆蓋是覆蓋率最高的，但是，簡單的程序路徑數(shù)量很少，而復(fù)雜的程序路徑數(shù)量巨大，要實(shí)現(xiàn)路徑覆蓋幾乎不可能，即測(cè)試量過大；另外，即使?jié)M足了程序結(jié)構(gòu)一般意義上的路徑覆蓋，仍然不能保證被測(cè)程序的正確性，即測(cè)試不足。如果要求測(cè)試更加充分，則要求增加更多的測(cè)試用例來提高覆蓋率，測(cè)試量會(huì)更大，于是，測(cè)試中就產(chǎn)生了測(cè)試量過大和測(cè)試不足這一對(duì)矛盾。對(duì)于獨(dú)立路徑數(shù)的計(jì)算可以采用下面的方法：第一步，從流圖中找出程序所有的必經(jīng)節(jié)點(diǎn)(流圖中任何獨(dú)立路徑都必定經(jīng)過的節(jié)點(diǎn)叫做必經(jīng)節(jié)點(diǎn))，記作IV(i)，其中i為整數(shù)且0<=i<=N。第二步，從流圖中找出從必經(jīng)節(jié)點(diǎn)N(i)到必經(jīng)節(jié)點(diǎn)N(i+1)的獨(dú)立路徑數(shù)W(i)，其中i為整數(shù)且0<=i<N。第三步，重復(fù)上一步，直到程序結(jié)尾。第四步，根據(jù)乘法法則，獨(dú)立路徑數(shù)=W(i)，其中i為整數(shù)且0<=i<N，即獨(dú)立路徑數(shù)=W(0)*W(1)* *W(N一1)。完全路徑是指所有獨(dú)立路徑的集合，非完全路徑就是所有獨(dú)立路徑集合的真子集。由于程序中可能會(huì)包含有多個(gè)條件的判定，所以程序流程圖可能包含有隱含路徑，從而有程序流圖轉(zhuǎn)換成的對(duì)應(yīng)流圖可能包含有隱藏路徑。如圖1、圖2所示。

消除隱含路徑的辦法就是將含有多個(gè)條件的判定分為多個(gè)判定。即把圖1的程序流圖轉(zhuǎn)換成如圖3所示，圖4是其對(duì)應(yīng)的流圖。圖4中，節(jié)點(diǎn)1，4，7為必經(jīng)節(jié)點(diǎn)，W（0）=3,W（1）=3，所以獨(dú)立路徑數(shù)=3*3=9。由此，要達(dá)到完全路徑覆蓋就需要設(shè)計(jì)9個(gè)測(cè)試用例，從而使得測(cè)試量更加龐大。根據(jù)線性代碼序列與跳轉(zhuǎn)的測(cè)試覆蓋準(zhǔn)則，將程序在必經(jīng)節(jié)點(diǎn)處割斷，分別對(duì)每一段程序進(jìn)行完全路徑覆蓋的充分測(cè)試。對(duì)于被割斷的程序片斷，由于沒有參數(shù)人口，可以在程序片斷的開頭增加代碼對(duì)參數(shù)進(jìn)行初始化。從而達(dá)到完全測(cè)試，緩解測(cè)試量過大與測(cè)試不足的矛盾。圖1程序流圖圖2圖1對(duì)應(yīng)的流圖

圖3沒有隱含路徑的程序流圖圖4圖3的對(duì)應(yīng)流圖圖3沒有隱含路徑的程序流圖圖4圖3的對(duì)應(yīng)流圖總結(jié)完全路徑覆蓋的具體步驟如下：第一步，將判定語句的條件進(jìn)行分離，細(xì)化程序流程圖，使其不含隱含路徑。第二步，根據(jù)程序流程圖畫出流圖，找出必經(jīng)節(jié)點(diǎn)，必經(jīng)節(jié)點(diǎn)數(shù)為N。第三步，將程序流程圖在必經(jīng)節(jié)點(diǎn)處割斷，將整個(gè)程序分解為N+1個(gè)程序片斷。第四步，找出程序片斷i的完全路徑，為程序片斷i的每條獨(dú)立路徑設(shè)計(jì)用例，其中：1<=i<=N+l。第五，結(jié)合所設(shè)計(jì)的測(cè)試用例，將程序片斷i的參數(shù)初始化，其中1<=i<=N+1。第六步，將測(cè)試用例付諸測(cè)試，重復(fù)第四步至第六步，直到i=N+1。3基于控制流圖的路徑測(cè)試的改進(jìn)方法研究根據(jù)測(cè)試的目標(biāo)，選擇一個(gè)有一定效果且開銷較小的覆蓋準(zhǔn)則，或者是根據(jù)一定的標(biāo)準(zhǔn)，選擇所有完整邏輯路徑中的一個(gè)有限子集來進(jìn)行測(cè)試，用最小的測(cè)試用例，發(fā)現(xiàn)程序中最多的錯(cuò)誤。采用自動(dòng)機(jī)的思想和理論改進(jìn)，可以生成少的測(cè)試用例，而達(dá)到所有路徑的覆蓋。首先在程序的控制流圖上，每條路徑給一個(gè)標(biāo)示，如e1，e2,e3,...，ek等，其中e0為惟一的入f_=_1弧，e為最后一個(gè)唯一的出口弧。通過轉(zhuǎn)化可以將控制流程圖轉(zhuǎn)換成只含有路徑的自動(dòng)機(jī)，根據(jù)自動(dòng)機(jī)可以求出從eO到e的n(nN1)條路徑。具體步驟如下：第一步，輸入：程序源代碼程序。第二步，輸出：含有從e0到e的n(nN1)條路徑。第三步，根據(jù)程序塊的概念將程序源代碼轉(zhuǎn)換成相應(yīng)的控制流程圖。第四步，在每條弧上標(biāo)注el，e2,...，em(m為弧的總條數(shù))。第五步，為了便于算法的實(shí)現(xiàn)，增加了兩個(gè)空結(jié)點(diǎn)，其中一個(gè)s結(jié)點(diǎn)作為整個(gè)程序控制流程圖的起始結(jié)點(diǎn)，其入度為0，出度為1，并與e0進(jìn)行相連；en+l結(jié)點(diǎn)作為整個(gè)程序控制流程圖的終止結(jié)點(diǎn)，其入度為1，出度為0，并與e進(jìn)行相連。如果，一個(gè)控制流程圖的結(jié)點(diǎn)數(shù)為n，則經(jīng)過變換總的結(jié)點(diǎn)數(shù)為n+2。第六步，根據(jù)表1的轉(zhuǎn)換規(guī)則將控制流程圖轉(zhuǎn)換成以弧為結(jié)點(diǎn)的自動(dòng)機(jī)M。第七步，覆蓋路徑的尋找，尋找e0到e的n(nN1)條路徑。尋找回邊。并將回邊構(gòu)成的結(jié)點(diǎn)抽象成一個(gè)子結(jié)點(diǎn)，重復(fù)做①，直到所有的回邊均抽象成子結(jié)點(diǎn)。將自動(dòng)機(jī)_)If轉(zhuǎn)換成等價(jià)的M’。在自動(dòng)機(jī)M’上得到從e0到e的n(nN1)條獨(dú)立路徑。4總結(jié)以上只介紹了兩種了路徑覆蓋的測(cè)試方法，路徑覆蓋測(cè)試作為覆蓋率最高的一種測(cè)試方法，對(duì)其完善和簡化，將提高軟件測(cè)試的完備性以及軟件測(cè)試的效率。參考文獻(xiàn)宮云戰(zhàn).軟件測(cè)試；國防工業(yè)出版社出版2006年1月賀青春，葉柏龍.完全路徑