第四章 白盒測(cè)試方法

第四章

白盒測(cè)試方法授課教師：

鄭煒第四章白盒測(cè)試方法4.1程序控制流圖4.1.1基本塊4.1.2流圖的定義與圖形表示4.2邏輯覆蓋測(cè)試4.2.1測(cè)試覆蓋率4.2.2測(cè)試覆蓋4.2.3測(cè)試覆蓋準(zhǔn)則之間的包含關(guān)系4.2.4測(cè)試覆蓋準(zhǔn)則第四章白盒測(cè)試方法4.3路徑分析與測(cè)試4.4數(shù)據(jù)流測(cè)試分析4.4.1測(cè)試充分性基礎(chǔ)4.4.2測(cè)試充分性準(zhǔn)則的度量4.4.3測(cè)試集充分性的度量4.4.4數(shù)據(jù)流概念4.4.5基于數(shù)據(jù)流的測(cè)試充分性準(zhǔn)則第四章白盒測(cè)試方法4.5變異測(cè)試4.5.1變異和變體4.5.2強(qiáng)變異和弱變異4.5.3用變異技術(shù)進(jìn)行測(cè)試評(píng)價(jià)4.5.4變異算子4.5.5變異算子的設(shè)計(jì)4.5.6變異測(cè)試的基本原則4.1.1基本塊基本塊：

如果P是一個(gè)由過(guò)程式程序設(shè)計(jì)語(yǔ)言（如C語(yǔ)言）編寫的程序，那么只有一個(gè)入口塊和出口塊的連續(xù)語(yǔ)句序列就可以被認(rèn)為是一個(gè)基本塊。

一個(gè)基本塊只有唯一的入口塊和出口塊，這個(gè)入口塊即為基本塊的第1條語(yǔ)句，出口塊是最后一條語(yǔ)句。程序的控制從入口塊進(jìn)入，從出口塊退出，除此之外程序不能在基本塊其他點(diǎn)退出或是中止。如果基本塊僅有一條語(yǔ)句，那么認(rèn)為入口和出口是重合的。4.1.1基本塊（1）第1行到第5行就構(gòu)成了一個(gè)基本塊，第1行是唯一的入口塊，第5行是唯一的出口塊。（2）還有某些程序分析工具把單條過(guò)程調(diào)用語(yǔ)句當(dāng)作一個(gè)單獨(dú)的基本塊。在這樣的定義下，可以把例4.1中的input語(yǔ)句也當(dāng)作一個(gè)基本塊。（3）函數(shù)調(diào)用本身常常被當(dāng)作基本塊，由于這些調(diào)用語(yǔ)句會(huì)造成控制程序從當(dāng)前執(zhí)行的函數(shù)轉(zhuǎn)移到別的地方，很容易導(dǎo)致程序的非正常終止。若無(wú)特別說(shuō)明，則認(rèn)為函數(shù)調(diào)用和其他順序語(yǔ)句是相同的，即認(rèn)為它們都不會(huì)引起程序中止。例4.1：示例程序4.1.2流圖的定義與圖形表示流圖G=(N,E)表示流圖G，其中N是節(jié)點(diǎn)的有限集合，E是有向邊的有限集合。Star出發(fā)節(jié)點(diǎn)，End終止節(jié)點(diǎn)。節(jié)點(diǎn)—橢圓或矩形框—表示基本塊箭頭—控制流的方向例4.1的圖形表示N={Start,1,2,3,4,End}E={(Start,1),(1,2),(1,3),(2,4)(3,4),(4,End)}第四章白盒測(cè)試方法4.1程序控制流圖4.1.1基本塊4.1.2流圖的定義與圖形表示4.2邏輯覆蓋測(cè)試4.2.1測(cè)試覆蓋率4.2.2測(cè)試覆蓋4.2.3測(cè)試覆蓋準(zhǔn)則之間的包含關(guān)系4.2.4測(cè)試覆蓋準(zhǔn)則4.2.1測(cè)試覆蓋率測(cè)試覆蓋率：用于確定測(cè)試所執(zhí)行到的覆蓋項(xiàng)的百分比，其中覆蓋項(xiàng)是指作為測(cè)試基礎(chǔ)的一個(gè)入口或?qū)傩?，如語(yǔ)句、分支、條件等。測(cè)試覆蓋率是對(duì)測(cè)試充分性的表示，它可以作為在測(cè)試分析報(bào)告中的一個(gè)可量化的指標(biāo)依據(jù)，一般認(rèn)為測(cè)試覆蓋率越高，測(cè)試效果越好。但是測(cè)試覆蓋率并非測(cè)試的絕對(duì)目標(biāo)，而只是一種手段。4.2.1測(cè)試覆蓋率

常用的測(cè)試覆蓋評(píng)測(cè)1.基于需求的測(cè)試覆蓋基于需求的測(cè)試覆蓋在測(cè)試生命周期中要評(píng)測(cè)多次，并在測(cè)試生命周期的里程碑處提供測(cè)試覆蓋的標(biāo)識(shí)（如已計(jì)劃的、已實(shí)施的、已執(zhí)行的和成功的測(cè)試覆蓋）。2.基于代碼的測(cè)試覆蓋基于代碼的測(cè)試覆蓋評(píng)測(cè)測(cè)試過(guò)程中已經(jīng)執(zhí)行的代碼的多少，與之相對(duì)的是要執(zhí)行的剩余代碼的多少?；诖a的測(cè)試覆蓋可以建立在控制流（語(yǔ)句、分支或路徑）或數(shù)據(jù)流的基礎(chǔ)上。4.2.2邏輯覆蓋覆蓋類型覆蓋標(biāo)準(zhǔn)語(yǔ)句覆蓋每行可執(zhí)行語(yǔ)句至少執(zhí)行一次判斷覆蓋每個(gè)真假分支至少被執(zhí)行一次條件覆蓋每個(gè)判斷中的每個(gè)條件的可能取值至少滿足一次條件/判斷組合覆蓋每個(gè)判斷中的每個(gè)條件的可能取值至少滿足一次每個(gè)判斷至少獲得一次“真”和一次“假”。多條件覆蓋每個(gè)判斷中的每個(gè)條件的各種可能組合至少出現(xiàn)一次4.2.2邏輯覆蓋覆蓋類型覆蓋標(biāo)準(zhǔn)修正條件覆蓋每個(gè)程序模塊的入口和出口點(diǎn)都至少要被調(diào)用一次，每個(gè)程序的判定到所有可能的結(jié)果值要至少轉(zhuǎn)換一次；程序的判定被分解為通過(guò)邏輯操作符“and”和“or”連接的布爾條件，每個(gè)條件對(duì)于判定的結(jié)果值是獨(dú)立的組合覆蓋

每個(gè)判定的所有可能的條件取值都至少出現(xiàn)一次。路徑覆蓋

所有可執(zhí)行路徑至少執(zhí)行一次4.2.3邏輯覆蓋準(zhǔn)則之間的包含關(guān)系組合覆蓋判定/條件覆蓋判斷覆蓋語(yǔ)句覆蓋條件覆蓋4.2.4測(cè)試覆蓋準(zhǔn)則測(cè)試覆蓋準(zhǔn)則1.錯(cuò)誤敏感測(cè)試用例分析（ErrorSensitiveTestCasesAnalysis，ESTCA）錯(cuò)誤敏感測(cè)試用例分析規(guī)則［規(guī)則1］對(duì)于ArelB（rel可以是<、=或>）型的分支謂詞，應(yīng)適當(dāng)?shù)剡x擇A與B的值，使得測(cè)試執(zhí)行到該分支語(yǔ)句時(shí)，A<B、A=B和A>B的情況分別出現(xiàn)一次。［規(guī)則2］對(duì)于ArelC（rel可以是>或<，A是變量，C是常量）型的分支謂詞，當(dāng)rel為<時(shí)，應(yīng)適當(dāng)?shù)剡x擇A的值，使A=C?M（M是距離C最小的容器容許正數(shù)，A和C均為整型時(shí)，M=1）。同樣，當(dāng)rel為>時(shí)，應(yīng)適當(dāng)?shù)剡x擇A，使A=C+M。［規(guī)則3］

對(duì)外部輸入變量賦值，使其在每一測(cè)試用例中均有不同的值與符號(hào)，并與同一組測(cè)試用例中其他變量的值與符號(hào)不一致。4.2.4測(cè)試覆蓋準(zhǔn)則測(cè)試覆蓋準(zhǔn)則

2.線性代碼序列與跳轉(zhuǎn)（LinearCodeSequenceandJump，LCSAJ）。層次LCSAJ覆蓋準(zhǔn)則第1層：語(yǔ)句覆蓋。第2層：分支覆蓋。第3層：LCSAJ覆蓋，即程序中的每個(gè)LCSAJ都至少在測(cè)試中經(jīng)歷過(guò)一次。第4層：兩兩LCSAJ覆蓋，即程序中的每?jī)蓚€(gè)相連的LCSAJ組合起來(lái)在測(cè)試中都要經(jīng)歷一次?！趎+2層：每n個(gè)首尾相連的LCSAJ組合在測(cè)試中都要經(jīng)歷一次。在實(shí)施測(cè)試時(shí)，若要實(shí)現(xiàn)上述的層次LCSAJ覆蓋，需要產(chǎn)生被測(cè)程序的所有LCSAJ。第四章白盒測(cè)試方法4.3路徑分析與測(cè)試4.4數(shù)據(jù)流測(cè)試分析4.4.1測(cè)試充分性基礎(chǔ)4.4.2測(cè)試充分性準(zhǔn)則的度量4.4.3測(cè)試集充分性的度量4.4.5基于數(shù)據(jù)流的測(cè)試充分性準(zhǔn)則4.3路徑分析與測(cè)試路徑測(cè)試路徑測(cè)試（PathTesting）是指根據(jù)路徑設(shè)計(jì)測(cè)試用例的一種技術(shù)，經(jīng)常用于狀態(tài)轉(zhuǎn)換測(cè)試中?；韭窂綔y(cè)試法是在程序控制流圖的基礎(chǔ)上，通過(guò)分析控制構(gòu)造的環(huán)路復(fù)雜性，導(dǎo)出基本可執(zhí)行的路徑集合，從而設(shè)計(jì)測(cè)試用例的方法。設(shè)計(jì)出的測(cè)試用例要保證在測(cè)試中程序的每個(gè)可執(zhí)行語(yǔ)句至少執(zhí)行一次借助漏洞掃描工具測(cè)試4.3路徑分析與測(cè)試基本路徑測(cè)試步驟（1）畫出程序的控制流圖。（2）計(jì)算程序的圈復(fù)雜度，導(dǎo)出程序基本路徑集中的獨(dú)立路徑條數(shù)，這是確定程序中每個(gè)可執(zhí)行語(yǔ)句至少執(zhí)行一次所需的測(cè)試用例數(shù)量的上界。（3）導(dǎo)出基本路徑集，確定程序的獨(dú)立路徑。（4）根據(jù)步驟（3）中的獨(dú)立路徑，設(shè)計(jì)測(cè)試用例的輸入數(shù)據(jù)和預(yù)期輸出結(jié)果。4.3路徑分析與測(cè)試示例程序：例4.2voidSort(intiRecordNum,intiType)1{2intx=0;3inty=0;4while(iRecordNum-->0)5{6if(iType==0)7{x=y+2;break;}8else9if(iType==1)10x=y+10;11else12x=y+20;13}14}4.3路徑分析與測(cè)試（1）畫出程序的控制流圖，如圖4-2（2）計(jì)算程序的圈復(fù)雜度圈復(fù)雜度的定義：V(G)=E?N+2PE表示控制流圖的邊的數(shù)量；N表示控制流圖的節(jié)點(diǎn)數(shù)；P表示控制流圖中相連接的部分圖4-2例4.2的控制流圖V(G)=10?8+2=44.3路徑分析與測(cè)試（3）導(dǎo)出獨(dú)立路徑圖4-2例4.2的控制流圖路徑1：4→14路徑2：4→6→7→14路徑3：4→6→9→10→13→4→14路徑4：4→6→9→12→13→4→144.3路徑分析與測(cè)試（4）設(shè)計(jì)測(cè)試用例

輸入數(shù)據(jù)預(yù)期輸出測(cè)試用例1irecordnum=0itype=0x=0y=0測(cè)試用例2irecordnum=1itype=0x=0y=0測(cè)試用例3irecordnum=1itype=1x=10y=0測(cè)試用例4irecordnum=1itype=2x=0y=20第四章白盒測(cè)試方法4.3路徑分析與測(cè)試4.4數(shù)據(jù)流測(cè)試分析4.4.1測(cè)試充分性基礎(chǔ)4.4.2測(cè)試充分性準(zhǔn)則的度量4.4.3測(cè)試集充分性的度量4.4.4數(shù)據(jù)流概念4.4.5基于數(shù)據(jù)流的測(cè)試充分性準(zhǔn)則4.4.1測(cè)試充分性基礎(chǔ)測(cè)試充分性準(zhǔn)則描述有謂詞和度量函數(shù)兩種形式。謂詞形式的充分性準(zhǔn)則描述將充分性定義為一個(gè)謂詞，用于確定測(cè)試數(shù)據(jù)必須具備什么性質(zhì)才是一個(gè)徹底的測(cè)試；度量函數(shù)形式的充分性準(zhǔn)則將充分性描述為測(cè)試的充分程度，是一種更廣義的充分性準(zhǔn)則定義。4.4.1測(cè)試充分性基礎(chǔ)定義4.1謂詞形式的充分性準(zhǔn)則定義4.2度量函數(shù)形式的充分性準(zhǔn)則

設(shè)P為被測(cè)程序，D是一可數(shù)集合，為P的輸入域，對(duì)d∈D，P(d)為程序的輸出；S是D→P(D)二元映射關(guān)系的一個(gè)子集，表示軟件規(guī)格說(shuō)明的集合；T是測(cè)試數(shù)據(jù)集合的集合，則謂詞形式的軟件測(cè)試充分性準(zhǔn)則C是一個(gè)定義在P×S×T上的謂詞，即C:P×S×T→{true,false}C(p,s,t)=true表示根據(jù)充分性準(zhǔn)則C和規(guī)格說(shuō)明s，用測(cè)試數(shù)據(jù)集t測(cè)試程序p是充分的，否則是不充分的。

一個(gè)測(cè)試數(shù)據(jù)的充分性準(zhǔn)則M是P×S×T到區(qū)間［0,1］上的映射，用數(shù)學(xué)形式可表示為M:P×S×T→［0,1］。M(s,

p,

t)=r表示根據(jù)規(guī)格說(shuō)明s和充分性準(zhǔn)則M，用測(cè)試數(shù)據(jù)集t

來(lái)測(cè)試程序p的充分度為r，顯然0≤r≤1，r越大說(shuō)明測(cè)試越充分。4.4.2測(cè)試充分性準(zhǔn)則的度量揭錯(cuò)能力：揭錯(cuò)能力是測(cè)試充分性準(zhǔn)則有效性的最直接的度量之一，如果使用充分性準(zhǔn)則A比使用充分性準(zhǔn)則B可以發(fā)現(xiàn)更多的軟件錯(cuò)誤，則認(rèn)為準(zhǔn)則A的有效性要高于準(zhǔn)則B。揭錯(cuò)能力可由缺陷檢測(cè)效力（FaultDetectionEffectiveness，F(xiàn)DE）和缺陷檢測(cè)概率（FaultDetectionProbability，F(xiàn)DP）來(lái)表示。4.4.2測(cè)試充分性準(zhǔn)則的度量揭錯(cuò)能力：為了對(duì)FDE和FDP進(jìn)行定量描述，首先定義一個(gè)有效性矩陣E，如表4-2所示。設(shè)軟件P包含了F1,…,Fm,共m個(gè)缺陷，根據(jù)測(cè)試準(zhǔn)則C，生成T1,T2,…,Tn，共n個(gè)測(cè)試集，則n個(gè)測(cè)試集對(duì)m個(gè)缺陷的檢測(cè)結(jié)果構(gòu)成了測(cè)試準(zhǔn)則C對(duì)軟件P的有效性矩陣E(m,n)，其中，ei，j=0表示測(cè)試集Tj未能檢測(cè)出缺陷Fi，ei，j=1表示測(cè)試集Tj能檢測(cè)出缺陷Fi。4.4.2測(cè)試充分性準(zhǔn)則的度量揭錯(cuò)能力：Fault（缺陷）Test

Suite（測(cè)試集）FDP（缺陷檢測(cè)概率）T1T2…Tj…TnF111………02/nF201………01/n…00………1…Fi………………………………………Fm10………0…FDE2/m…………1/m

表4-2：測(cè)試準(zhǔn)則C對(duì)程序P的有效性矩陣E4.4.2測(cè)試充分性準(zhǔn)則的度量揭錯(cuò)能力：定義4.3缺陷檢測(cè)效力給定測(cè)試集T和軟件P，T對(duì)P的缺陷檢測(cè)效力定義為T所檢測(cè)到的缺陷占P所包含缺陷的比率，即定義4.4缺陷檢測(cè)概率對(duì)軟件P所包含的缺陷類型Fi，滿足測(cè)試準(zhǔn)則C的所有測(cè)試集中能檢測(cè)到該缺陷的測(cè)試集占整個(gè)測(cè)試集的比率，即4.4.2測(cè)試充分性準(zhǔn)則的度量2.軟件可靠性：如果程序P經(jīng)過(guò)滿足測(cè)試充分性準(zhǔn)則A測(cè)試后的可靠性要比經(jīng)過(guò)滿足測(cè)試充分性準(zhǔn)則B測(cè)試后的可靠性高，則認(rèn)為測(cè)試充分性準(zhǔn)則A比測(cè)試充分性準(zhǔn)則B具有更好的有效性。軟件可靠性是衡量軟件質(zhì)量的最重要要素和軟件開發(fā)的最終目標(biāo)，但軟件可靠性指標(biāo)本身就是一個(gè)很復(fù)雜的問(wèn)題，利用可靠性對(duì)測(cè)試充分性準(zhǔn)則的有效性進(jìn)行比較是非常困難的。通過(guò)充分性準(zhǔn)則C測(cè)試后，為了表示軟件P可獲得的軟件可靠性程度，則需要綜合考慮缺陷的發(fā)生頻率和測(cè)試準(zhǔn)則的檢測(cè)效力。用缺陷的潛在失效距離（PotentialFailureDistance，PFD）對(duì)滿足某種充分性準(zhǔn)則測(cè)試后的軟件進(jìn)行可靠性度量。4.4.2測(cè)試充分性準(zhǔn)則的度量2.軟件可靠性：

定義4.5潛在失效距離其中，Poccur_i表示實(shí)際操作中導(dǎo)致軟件失效的概率；Pdetect_i表示通過(guò)某充分性準(zhǔn)則測(cè)試后錯(cuò)誤被移除的概率。其中，|Di|為會(huì)引發(fā)缺陷i的輸入空間的大小，|D|表示整個(gè)輸入空間的大小。對(duì)軟件P，其對(duì)測(cè)試準(zhǔn)則C的潛在失效距離定義為根據(jù)測(cè)試準(zhǔn)則C對(duì)P進(jìn)行充分測(cè)試后，該程序仍可能失效的概率為4.4.2測(cè)試充分性準(zhǔn)則的度量3.測(cè)試開銷：軟件測(cè)試是軟件開發(fā)中開銷較大的一項(xiàng)工程，測(cè)試開銷和所選擇的測(cè)試充分性準(zhǔn)則密切相關(guān)，其實(shí)質(zhì)是比較使用測(cè)試準(zhǔn)則所用的代價(jià)，最為簡(jiǎn)單的對(duì)測(cè)試開銷的度量是選擇某個(gè)測(cè)試準(zhǔn)則C時(shí)所需要的最少測(cè)試T。研究人員認(rèn)為，使用一個(gè)測(cè)試準(zhǔn)則進(jìn)行測(cè)試的開銷包括生成一組滿足測(cè)試準(zhǔn)則C的測(cè)試用例集的開銷、執(zhí)行測(cè)試的開銷，以及檢測(cè)輸出結(jié)果的開銷。4.4.3測(cè)試集充分性的度量覆蓋域一個(gè)測(cè)試集的充分性由一個(gè)有限集來(lái)度量。針對(duì)相對(duì)應(yīng)的測(cè)試準(zhǔn)則

C，根據(jù)軟件的需求或者軟件的代碼導(dǎo)出一個(gè)有限集，把這個(gè)有限集記為Ce，也就是所謂的覆蓋域。測(cè)試覆蓋有限集當(dāng)對(duì)某個(gè)測(cè)試集T的充分性進(jìn)行測(cè)試時(shí)，給定一個(gè)有n個(gè)元素的有限集Ce，n≥0。如果說(shuō)測(cè)試集T覆蓋有限集Ce，是指對(duì)于有限集Ce中的每個(gè)元素e，在測(cè)試集T中都至少有一個(gè)測(cè)試用例能夠?qū)λM(jìn)行測(cè)試。測(cè)試集的充分性假如測(cè)試集T覆蓋了有限集Ce中的所有元素，則認(rèn)為對(duì)于測(cè)試準(zhǔn)則C來(lái)說(shuō)測(cè)試集T是充分的；而假如測(cè)試集T只覆蓋了有限集Ce中的k個(gè)元素（k＜n），則認(rèn)為對(duì)于測(cè)試準(zhǔn)則C來(lái)說(shuō)測(cè)試集T是不充分的。4.4.3測(cè)試集充分性的度量測(cè)試覆蓋率

測(cè)試集T對(duì)測(cè)試準(zhǔn)則C的充分度用分?jǐn)?shù)k/n表示，這個(gè)分?jǐn)?shù)也被稱為是T對(duì)C的覆蓋率。測(cè)試充分性準(zhǔn)則

要確定有限集Ce中的每一個(gè)元素e是否都被測(cè)試集T測(cè)試到了，這需要依賴于元素e的程序P。如果程序P中的每條路徑都被遍歷至少一次，則認(rèn)為測(cè)試集T針對(duì)測(cè)試準(zhǔn)則C是充分的。

但是充分的測(cè)試集可能不能發(fā)現(xiàn)軟件中最明顯的錯(cuò)誤，例如，在對(duì)例4.3進(jìn)行編程時(shí)，若給出示例程序，這個(gè)程序顯然是錯(cuò)誤的；若以測(cè)試準(zhǔn)則C測(cè)試測(cè)試集T={t:x≤2,y≥3}，雖然測(cè)試集T相對(duì)于程序P是充分的，但顯然這個(gè)程序并不正確。4.4.3測(cè)試集充分性的度量例4.3考慮編寫程序sumProject，其需求如下。R1：當(dāng)x＜y時(shí)，求x與y之積，并在標(biāo)準(zhǔn)輸出設(shè)備上輸出x與y之積。R2：當(dāng)x≥y時(shí)，求x與y之和，并在標(biāo)準(zhǔn)輸出設(shè)備上輸出x與y之和。示例程序如下：一個(gè)充分的測(cè)試集有可能不能發(fā)現(xiàn)軟件中最明顯的錯(cuò)誤，但是這絲毫不影響測(cè)試充分性度量的價(jià)值。1begin2intx,y;3input(x,y);4sum=x+y;5output(sum);6end4.4.4數(shù)據(jù)流概念數(shù)據(jù)流控制流測(cè)試是面向程序的結(jié)構(gòu)，數(shù)據(jù)流測(cè)試面向的是程序中的變量。變量的定義

一個(gè)變量在程序中的某處出現(xiàn)使數(shù)據(jù)與該變量綁定變量的引用

一個(gè)變量在程序中的某處出現(xiàn)使之與該變量綁定的內(nèi)容被引用計(jì)算性引用：用于計(jì)算新數(shù)據(jù)或輸出結(jié)果，用c-use表示；謂詞性引用：用于計(jì)算判斷控制轉(zhuǎn)移方向的謂詞，用p-use表示。若一個(gè)變量被引用前在它出現(xiàn)的程序塊內(nèi)無(wú)其定義性出現(xiàn)，則該引用

稱為全局性引用；否則稱為局部性引用。4.4.4數(shù)據(jù)流概念為方便引用，可將之前論述過(guò)的控制流圖進(jìn)行改造，即去掉控制流圖中的判斷框，把其中的謂詞放在邊上，這種圖稱為具有數(shù)據(jù)信息的控制流圖。例如，圖4-3（b）所示的就是一個(gè)計(jì)算最大公約數(shù)的具有數(shù)據(jù)信息的控制流圖，而圖4-3（a）所示的則是該程序的控制流圖。4.4.4數(shù)據(jù)流概念變量的定義傳遞到引用定義定義4.8：<n1,n2,n3,…,nk>是具有數(shù)據(jù)流信息的控制流圖Gp中的一條路徑，x是程序中的一個(gè)變量。如果節(jié)點(diǎn)ni（i=1,2,…,k）都不含x的定義性出現(xiàn)，則該路徑稱為對(duì)于x來(lái)說(shuō)是無(wú)定義的。讓n0,nk為G中的節(jié)點(diǎn)，n0中包含變量x的定義性出現(xiàn)，nk中包含變量x的計(jì)算性引用出現(xiàn)。從節(jié)點(diǎn)n0到節(jié)點(diǎn)nk的路徑<n1,n2,n3,…,nk>稱為一條將x在n0中的定義傳遞到nk中的計(jì)算性引用的路徑，如果路徑對(duì)x來(lái)說(shuō)是無(wú)定義的，則稱x在n0中的定義可傳遞到nk中的計(jì)算性引用。4.4.4數(shù)據(jù)流概念全局/局部變量的使用一個(gè)變量可能在同一個(gè)基本塊中被定義、使用和重定義。考慮如下含有3條語(yǔ)句的基本塊：p=y+z;x=p+1;p=z*z;變量p的第1個(gè)定義是局部的，變量p的第2個(gè)定義是全局的，變量p的第1個(gè)使用也是局部使用。變量y和變量z的c-use是全局使用，變量x的定義也是全局的。注意：這里所講的全局變量和局部變量，是針對(duì)程序中的基本塊而言，這與傳統(tǒng)的全局和局部概念有所不同。傳統(tǒng)上，全局變量是在函數(shù)或模塊的外部聲明的，而局部變量是在函數(shù)或模塊的內(nèi)部聲明的。4.4.4數(shù)據(jù)流概念數(shù)據(jù)流圖程序的數(shù)據(jù)流圖（def-use圖），它刻畫了程序中的變量在不同的基本塊之間的定義流，與程序的控制流圖相似。CFG中的節(jié)點(diǎn)、邊以及所有的路徑都在數(shù)據(jù)流圖中保留了下來(lái)；程序的數(shù)據(jù)流圖可以從它的CFG中導(dǎo)出。設(shè)G=(N,

E)為程序P的CFG，其中，N是節(jié)點(diǎn)集合，E是邊集合。CFG中的節(jié)點(diǎn)對(duì)應(yīng)于P中的基本塊，假設(shè)程序P含有k>0個(gè)基本塊，b1、b2、…、bk基本塊defi定義在基本塊i中的變量的集合c-usei在基本塊i中有c-use的變量的集合p-usei在基本塊i中有p-use的變量的集合di(x)變量x在節(jié)點(diǎn)i中的定義ui(x)變量x在節(jié)點(diǎn)i中的使用程序中的變量聲明、賦值語(yǔ)句、輸入語(yǔ)句和傳址調(diào)用參數(shù)都可以用來(lái)定義變量。4.4.4數(shù)據(jù)流概念數(shù)據(jù)流圖考慮如下基本塊b，它包含兩條賦值語(yǔ)句和一個(gè)函數(shù)調(diào)用語(yǔ)句：由這個(gè)基本塊，得到defb

={p,

A}，c-useb

={y,

z,

p,

q,

number,

x,

i},

p-useb

={x,

y}。p=y+z;foo(p+q,number);//傳值參數(shù)A[i]=x+1;if(x>y){…};4.4.4數(shù)據(jù)流概念數(shù)據(jù)流圖p=y+z;foo(p+q,number);//傳值參數(shù)A[i]=x+1;if(x>y){…};步驟1計(jì)算P中每個(gè)基本塊i的defi、c-usei和p-usei。步驟2將節(jié)點(diǎn)集N中的每個(gè)節(jié)點(diǎn)i與defi、c-usei和p-usei關(guān)聯(lián)起來(lái)。步驟3針對(duì)每個(gè)具有非空p-use集并且在條件C處結(jié)束的節(jié)點(diǎn)i，當(dāng)條件C為真時(shí)，執(zhí)行的是邊(i,

j)，當(dāng)條件C為假時(shí)，執(zhí)行的是邊(i,

k)，分別將邊(i,

j)、(i,

k)與條件C、!C關(guān)聯(lián)起來(lái)。采用下面的過(guò)程，可以根據(jù)程序P及其CFG構(gòu)造出其數(shù)據(jù)流圖。4.4.4數(shù)據(jù)流概念def-use對(duì)def-use對(duì)勾畫了變量的一次特定的定義和使用，程序的數(shù)據(jù)流圖會(huì)包括該程序所有的def-use對(duì)。一個(gè)def-use對(duì)由一個(gè)變量在某個(gè)基本塊中的定義和該變量在另一個(gè)基本塊中的使用構(gòu)成。一般來(lái)說(shuō)，主要關(guān)心兩種類型的def-use對(duì)：一種是定義及其c-use構(gòu)成的def-use對(duì)；另一種是定義及其p-use構(gòu)成的def-use對(duì)。分別用集合dcu和dpu來(lái)描述這兩類def-use對(duì)。對(duì)一個(gè)變量而言，總有一個(gè)dcu集合和一個(gè)dpu集合。4.4.5基于數(shù)據(jù)流的測(cè)試充分性準(zhǔn)則設(shè)CU、PU分別表示程序P中定義的所有c-use總數(shù)量、p-use總數(shù)量。設(shè)v={v1,v2,…,vn}表示程序P中所有變量的集合，N表示程序P中節(jié)點(diǎn)集合，di表示vi的定義次數(shù)，1≤i≤n，0≤di≤|N|。CU和PU的計(jì)算如下：其中nj是變量vi第j次被定義時(shí)所在的節(jié)點(diǎn)，|S|表示集合S中元素的個(gè)數(shù)。CU和PU的計(jì)算4.4.5基于數(shù)據(jù)流的測(cè)試充分性準(zhǔn)則覆蓋率計(jì)算1.測(cè)試集T針對(duì)(P,R)的c-use覆蓋率計(jì)算如下：2.測(cè)試集T針對(duì)(P,R)的p-use覆蓋率計(jì)算如下：3.測(cè)試集T針對(duì)(P,R)的all-use覆蓋率計(jì)算如下第四章白盒測(cè)試方法4.5變異測(cè)試4.5.1變異和變體4.5.2強(qiáng)變異和弱變異4.5.3用變異技術(shù)進(jìn)行測(cè)試評(píng)價(jià)4.5.4變異算子4.5.5變異算子的設(shè)計(jì)4.5.6變異測(cè)試的基本原則4.5.1變異和變體原子性用P表示原始被測(cè)程序，M表示輕微變更程序P后得到的程序，則可以把程序M稱為程序P的變體（Mutation），程序P是程序M的父體（Parent）。1begin2intx,y;3input(x,y);4if(x<y)5output(x+y);6else7output(x*y)8end1begin2intx,y;3input(x,y);4if(x<y)5output(x-y);6else7output(x*y)8end變體：父體：4.5.1變異和變體一階變體在對(duì)程序進(jìn)行測(cè)試的時(shí)候，僅經(jīng)過(guò)一次變更而得到的變體稱為一階變體。高階變體同樣地，二階變體就是經(jīng)過(guò)了兩次簡(jiǎn)單變更而得到的變體，三階變體就是經(jīng)過(guò)了三次簡(jiǎn)單變更而得到的變體，依此類推。對(duì)一個(gè)一階變體再進(jìn)行一次簡(jiǎn)單變更就可以得到二階變體，也就是說(shuō)，一個(gè)n階變體可以由一個(gè)(n?1)階變體進(jìn)行一次簡(jiǎn)單變更而得到。高于一階的變體叫作高階變體。在實(shí)際中，使用最多的還是一階變體，主要原因有兩個(gè)：一個(gè)是在數(shù)量上，高階變體的數(shù)量遠(yuǎn)多于一階變體的數(shù)量，大量的變體會(huì)影響到充分性評(píng)價(jià)的可量測(cè)問(wèn)題；另一個(gè)是涉及耦合效應(yīng)。4.5.2強(qiáng)變異和弱變異強(qiáng)變異檢測(cè)給定被測(cè)程序P和基于程序P生成的一個(gè)變體M，若測(cè)試用例t在程序P和變體M上的輸出結(jié)果不一致，則稱測(cè)試用例t可以強(qiáng)變異檢測(cè)到變體m弱變異檢測(cè)假設(shè)被測(cè)程序

P

由

n

個(gè)程序?qū)嶓w構(gòu)成集合S={s1,s2,…,sn}。通過(guò)對(duì)程序?qū)嶓wsm執(zhí)行變異算子生成變體M，若測(cè)試用例t在程序P和變體M中的程序?qū)嶓wsm上執(zhí)行后的程序狀態(tài)出現(xiàn)不一致，則稱測(cè)試用例t可以弱變異檢測(cè)到變體M4.5.3用變異技術(shù)進(jìn)行測(cè)試評(píng)價(jià)圖4-4利用變異技術(shù)對(duì)測(cè)試集進(jìn)行充分性評(píng)價(jià)的過(guò)程4.5.3用變異技術(shù)進(jìn)行測(cè)試評(píng)價(jià)圖4-4采用了變異技術(shù)對(duì)測(cè)試集進(jìn)行充分性評(píng)價(jià)的步驟，共涉及12個(gè)具體的步驟。步驟

1

執(zhí)行程序評(píng)價(jià)測(cè)試集T針對(duì)于（P，R）充分性過(guò)程的第1步就是針對(duì)測(cè)試集T中的每個(gè)測(cè)試用例t執(zhí)行程序P。P(t)代表程序P執(zhí)行測(cè)試用例t時(shí)輸出變量的集合。步驟

2生成變體步驟2結(jié)束時(shí)得到一個(gè)變體集合L，其中包含的變體被稱為活躍變體，因?yàn)檫@些變體都還沒(méi)有與原來(lái)的程序區(qū)分開。4.5.3用變異技術(shù)進(jìn)行測(cè)試評(píng)價(jià)步驟3和步驟4選取下一個(gè)變體

選擇下一個(gè)將要考慮的變體，這個(gè)變體必須是以前沒(méi)有考慮過(guò)的。循環(huán)選取集合L中的變體，直到集合T中的每個(gè)變體都被選取過(guò)為止，被選取過(guò)的變體會(huì)被從集合L中剔除。步驟5和步驟6選取下一個(gè)測(cè)試用例

選取變體M后，下一個(gè)目標(biāo)就是從測(cè)試集T中找到一個(gè)測(cè)試用例，將變體與原程序分開。

循環(huán)結(jié)束條件：所有的測(cè)試用例都執(zhí)行完了，或變體M被某個(gè)測(cè)試用例發(fā)現(xiàn)，與原程序區(qū)別開了4.5.3用變異技術(shù)進(jìn)行測(cè)試評(píng)價(jià)步驟7～步驟9變體的執(zhí)行和分類對(duì)于已經(jīng)被選出的變體M和準(zhǔn)備執(zhí)行的測(cè)試用例t，在步驟7中使用測(cè)試用例t執(zhí)行變體M；在步驟8中，檢查針對(duì)測(cè)試用例t執(zhí)行變體M產(chǎn)生的結(jié)果與執(zhí)行程序P產(chǎn)生的結(jié)果是否相同。若存在測(cè)試用例t（t∈T），在變體M與原有程序P上的執(zhí)行結(jié)果不一致，則稱該變體M相對(duì)于測(cè)試用例集T是可殺除變體。若不存在任何測(cè)試用例t（t∈T），在變體M與原有程序P上的執(zhí)行結(jié)果一致，則稱該變體M相對(duì)于測(cè)試用例集T是可存活變體。步驟7～步驟9在活躍變體中區(qū)分可殺除變體和可存活變體的過(guò)程。4.5.3用變異技術(shù)進(jìn)行測(cè)試評(píng)價(jià)步驟10活躍變體

當(dāng)測(cè)試集T中沒(méi)有測(cè)試用例能將變體M與其父體程序P區(qū)分開來(lái)時(shí)，變體M被放回到活躍集合L中。步驟11等價(jià)變體

執(zhí)行完所有變體之后，要檢查是否還存在活躍變體，即檢查變體集合L是否為空。一部分可存活變體通過(guò)設(shè)計(jì)新的測(cè)試用例可以轉(zhuǎn)換成可殺除變體，剩余的可存活變體則可能是等價(jià)變體。若變體M與原有程序P在語(yǔ)法上存在差異，但在語(yǔ)義上與P保持一致，則稱M是P的等價(jià)變體。4.5.3用變異技術(shù)進(jìn)行測(cè)試評(píng)價(jià)步驟12