作者 |孫海英華東師范大學(xué)軟件工程學(xué)院講師

蘇亭 華東師范大學(xué)軟件工程學(xué)院教授

版塊 |鑒源論壇 · 觀(guān)模

按語(yǔ)：由于無(wú)法窮舉被測(cè)軟件完整的輸入空間，各種軟件動(dòng)態(tài)測(cè)試方法本質(zhì)上都是圍繞”如何構(gòu)造測(cè)試集合以使其展現(xiàn)的部分行為能夠高效有效地反映軟件的整體行為“而展開(kāi)。判斷測(cè)試集合在軟件上的表現(xiàn)是否能夠充分反映該軟件的總體表現(xiàn)，在測(cè)試領(lǐng)域中叫充分性問(wèn)題。雖然，目前還存在尚不能圓滿(mǎn)解決的難題和各種爭(zhēng)議，但是這并不妨礙充分性問(wèn)題作為測(cè)試領(lǐng)域的奠基和科學(xué)基礎(chǔ)的地位，影響并指導(dǎo)著軟件測(cè)試從技術(shù)到管理的方方面面。

01充分性問(wèn)題的提出和變遷

1975年，Goodenough和Gerhart在研究軟件測(cè)試是否能夠保證軟件的正確性（指軟件與規(guī)約的一致性）時(shí)，突破性地引入了測(cè)試充分性（Test Adequacy）這一概念，用以確定測(cè)試數(shù)據(jù)必須具備什么性質(zhì)才是一個(gè)徹底的測(cè)試，即成功的測(cè)試意味著被測(cè)程序的正確性[1]。為此，Goodenough和Gerhart提出了測(cè)試充分性準(zhǔn)則的可靠性和正確性需求[2]。換句話(huà)說(shuō)，能夠滿(mǎn)足測(cè)試充分性準(zhǔn)則的可靠性和正確性的測(cè)試集合就是一個(gè)徹底的測(cè)試，能夠說(shuō)明被測(cè)軟件的正確性。

然而，不幸的是，很快Goodenough和Gerhart的測(cè)試充分性理論被指出存在錯(cuò)誤。在1976年，Howden證明了Goodenough和Gerhart提出的充分性準(zhǔn)則需求存在重大缺陷，通過(guò)測(cè)試的充分性保證軟件的正確性是不可行的[3]。盡管如此，由于軟件測(cè)試的充分性是軟件在有限多個(gè)測(cè)試數(shù)據(jù)上的行為判斷軟件在所有輸入數(shù)據(jù)上的邏輯基礎(chǔ)，因而充分性的叫法被保留了下來(lái)。雖然不能滿(mǎn)足提出時(shí)證明軟件正確性的初衷，但是，充分性準(zhǔn)則為分析和度量軟件測(cè)試質(zhì)量提供了一條客觀(guān)的途徑。除此以外，充分性準(zhǔn)則還可用于確定測(cè)試過(guò)程中需要觀(guān)察的內(nèi)容、作為測(cè)試停止標(biāo)準(zhǔn)之一以及當(dāng)測(cè)試集合未能達(dá)到期望的充分性準(zhǔn)則時(shí)，指導(dǎo)測(cè)試數(shù)據(jù)的補(bǔ)充。

對(duì)測(cè)試集合進(jìn)行期望的覆蓋分析是當(dāng)前判定測(cè)試充分性的主要方法。本文也從覆蓋角度說(shuō)明測(cè)試的充分性。實(shí)踐表明，如果正確合理地運(yùn)用覆蓋分析，其對(duì)保證軟件和軟件測(cè)試本身的質(zhì)量能夠起到積極的作用。例如，結(jié)構(gòu)覆蓋分析（Structural Coverage Analysis）是在安全關(guān)鍵系統(tǒng)領(lǐng)域被廣泛應(yīng)用的覆蓋分析方法。當(dāng)與“基于需求的測(cè)試”相結(jié)合（這個(gè)前提很重要，詳情可參考[4]），結(jié)構(gòu)覆蓋分析不僅可以發(fā)現(xiàn)測(cè)試集合的漏測(cè)，更能發(fā)現(xiàn)代碼中的功能缺失（本該實(shí)現(xiàn)而沒(méi)有實(shí)現(xiàn)的功能）和功能多余（無(wú)中生有的功能）[4]，更好地保證系統(tǒng)的安全性（Safety）。

02有哪些主流的覆蓋準(zhǔn)則

傳統(tǒng)上，主流的覆蓋準(zhǔn)則有控制流覆蓋（Control Flow Coverage）、數(shù)據(jù)流覆蓋(Data Flow Coverage)、變異覆蓋(Mutation Coverage)、分域覆蓋(Domain Partition Coverage)。由于面向代碼的結(jié)構(gòu)，因此，常把前兩者合稱(chēng)為結(jié)構(gòu)覆蓋（Structural Coverage）。每種覆蓋根據(jù)需要滿(mǎn)足的不同要求又包含不同的準(zhǔn)則。圖1展示了主流的覆蓋準(zhǔn)則。本文主要說(shuō)明控制流覆蓋和數(shù)據(jù)流覆蓋。

圖1 主流的覆蓋準(zhǔn)則

2.1控制流覆蓋

控制流覆蓋以控制流圖為測(cè)試充分程度分析基礎(chǔ)?？刂屏鲌D（Control Flow Graph，CFG）是面向代碼控制結(jié)構(gòu)的抽象模型，是由塊(Block)和連接塊的邊(Edge)構(gòu)成的有向圖。其中，塊是圖的節(jié)點(diǎn)，對(duì)應(yīng)滿(mǎn)足“原子規(guī)則”的語(yǔ)句序列集合，即塊內(nèi)的任意一條語(yǔ)句執(zhí)行其它語(yǔ)句必須執(zhí)行。連接塊的邊是圖的有向邊，對(duì)應(yīng)代碼的控制關(guān)系。后面我們用節(jié)點(diǎn)指代塊。對(duì)于圖2給出的代碼，圖3示例了塊的劃分和相應(yīng)的CFG，其中，節(jié)點(diǎn)1為開(kāi)始節(jié)點(diǎn)，6為終止節(jié)點(diǎn)。

圖 2

圖 3

路徑是CFG中由若干相鄰邊連接形成的通路，采用節(jié)點(diǎn)序列表示。路徑中含有的邊的數(shù)目是路徑的長(zhǎng)度。表1列舉了圖3所示CFG的部分路徑。因?yàn)樵揅FG中有回路，所以存在無(wú)數(shù)條路徑。如果路徑的開(kāi)始節(jié)點(diǎn)是CFG的初始節(jié)點(diǎn)，終止節(jié)點(diǎn)是CFG的終止節(jié)點(diǎn)，則該路徑被稱(chēng)為完整路徑。例如，圖3中給出的路徑只有(1,2,6)是完整路徑，其它都不是。一個(gè)測(cè)試用例的執(zhí)行對(duì)應(yīng)一條完整路徑。

表 1

（1）語(yǔ)句覆蓋

語(yǔ)句覆蓋（Statement Coverage）要求代碼的所有語(yǔ)句至少被執(zhí)行一次。由于CFG塊與語(yǔ)句的對(duì)應(yīng)關(guān)系，因此，語(yǔ)句覆蓋的正式定義為：測(cè)試集合T稱(chēng)為語(yǔ)句覆蓋充分的，當(dāng)且僅當(dāng)執(zhí)行T產(chǎn)生的完整路徑集合L覆蓋了控制流圖中的所有節(jié)點(diǎn)。如果使用符號(hào)Node(G)表示控制流圖的節(jié)點(diǎn)集合，Node(L)表示L包含的節(jié)點(diǎn)集合，則測(cè)試集合T的語(yǔ)句覆蓋率為：

語(yǔ)句覆蓋是級(jí)別最低的覆蓋準(zhǔn)則，但需要注意到并不是每條語(yǔ)句都可執(zhí)行。

（2）分支覆蓋

分支覆蓋（Branch Coverage）要求代碼中的所有控制轉(zhuǎn)移至少被執(zhí)行一次?？刂妻D(zhuǎn)移表現(xiàn)為CFG的邊，控制轉(zhuǎn)移得到測(cè)試意味著相應(yīng)的邊在測(cè)試集合對(duì)應(yīng)的完整路徑中出現(xiàn)。因此，分支覆蓋準(zhǔn)則的定義如下：測(cè)試集合T稱(chēng)為分支覆蓋充分的，當(dāng)且僅當(dāng)執(zhí)行T產(chǎn)生的完整路徑集合L覆蓋了控制流圖中的所有邊。如果使用符號(hào)Edge(G)表示控制流圖的邊集合，Edge(L)表示L包含的控制流圖中的邊集合，則測(cè)試集合T的分支覆蓋率為：

分支覆蓋是比語(yǔ)句覆蓋嚴(yán)格的準(zhǔn)則，同時(shí)，也需要注意分支也不一定是可執(zhí)性的。

（3）路徑覆蓋

路徑覆蓋（Path Coverage）要求代碼中每條完整路徑至少被執(zhí)行一次，其定義如下：測(cè)試集合T稱(chēng)為路徑覆蓋充分的，當(dāng)且僅當(dāng)執(zhí)行T產(chǎn)生的完整路徑集合L覆蓋了控制流圖中的所有完整路徑。如果使用符號(hào)Path(G)表示控制流圖的所有完整路徑集合，則測(cè)試集合T的路徑覆蓋率為：

路徑覆蓋進(jìn)一步強(qiáng)化了分支覆蓋，是比分支覆蓋更加嚴(yán)格的準(zhǔn)則。實(shí)際上，由于CFG中可能存在無(wú)窮多條完整路徑和不可行路徑，路徑覆蓋的要求過(guò)于嚴(yán)格，以致于無(wú)法付諸實(shí)踐。因此，一般情況下，會(huì)選擇一個(gè)有限的完整路徑子集進(jìn)行測(cè)試。

（4）基路徑覆蓋

基路徑覆蓋（Prime Path Coverage）是比路徑覆蓋弱的一種面向路徑的覆蓋準(zhǔn)則，由Jeff Offut等人提出[5]。該覆蓋要求構(gòu)成完整路徑的每一條公共子路徑，即基路徑，至少被執(zhí)行一次。基路徑是滿(mǎn)足路徑獨(dú)特性規(guī)則的簡(jiǎn)單路徑。所謂簡(jiǎn)單路徑(Simple Path) 是指CFG中不含回路的路徑，即除了開(kāi)始節(jié)點(diǎn)和終止節(jié)點(diǎn)外，路徑中每個(gè)節(jié)點(diǎn)出現(xiàn)的次數(shù)有且僅有一次。例如，表1中所列的路徑，長(zhǎng)度超過(guò)3的路徑都不是簡(jiǎn)單路徑。除了必須是簡(jiǎn)單路徑，為了滿(mǎn)足路徑獨(dú)特性規(guī)則，基路徑不能是其它簡(jiǎn)單路徑的子路徑。例如，表1的(3,4,2)是簡(jiǎn)單路徑但不是基路徑，因?yàn)樗?3,4,2,3)的子路徑，(3,4,2,3)是一條基路徑。給定一個(gè)控制流圖 G，可以通過(guò)先計(jì)算G的簡(jiǎn)單路徑集合，再按照基路徑定義從中篩選基路徑集合的方法求解G的基路徑集合。圖4給出了求解過(guò)程的示例。

圖 4

基路徑覆蓋要求每條基路徑至少被執(zhí)行一次，其定義如下：測(cè)試集合T稱(chēng)為基路徑覆蓋充分的，當(dāng)且僅當(dāng)執(zhí)行T產(chǎn)生的完整路徑集合L訪(fǎng)問(wèn)了控制流圖中的所有基路徑。如果使用符號(hào)PP(G)表示控制流圖的所有基路徑集合，PP(L)表示L訪(fǎng)問(wèn)的基路徑集合，則測(cè)試集合T的基路徑覆蓋率為：

基路徑是比分支覆蓋強(qiáng)，但比路徑覆蓋弱的準(zhǔn)則，可以有效地降低必須測(cè)試的路徑數(shù)，但同樣存在不可行的基路徑的問(wèn)題。

2.2邏輯謂詞覆蓋

邏輯謂詞即可以是規(guī)約中的邏輯條件，也可以指代碼中的邏輯表達(dá)式。邏輯謂詞決定控制轉(zhuǎn)移方向，對(duì)代碼功能的正確實(shí)現(xiàn)具有重要意義。邏輯謂詞涉及條件和判定兩個(gè)概念。條件指不含布爾算子的邏輯謂詞，可以是布爾變量、關(guān)系表達(dá)式及其非。判定通常由條件通過(guò)布爾算子“與”、“或”、“非”連接起來(lái)的邏輯謂詞。例如，(in_dis >= 0) && (in_dis <= 500)是一個(gè)判定，(in_dis >= 0)和(in_dis <= 500)則是條件。

（1）判定覆蓋

判定覆蓋（Decision Coverage）用于衡量判定得到執(zhí)行的程度。如果測(cè)試集合能夠使得每個(gè)判定的真假情況至少各被執(zhí)行一次, 則說(shuō)該測(cè)試集合滿(mǎn)足了判定覆蓋。例如，測(cè)試集合{in_dis = 0, in_dis=501}滿(mǎn)足(in_dis >= 0) && (in_dis <= 500)的判定覆蓋，因?yàn)椋?in_dis >= 0) && (in_dis <= 500)的真和假均被執(zhí)行了。

（2）條件覆蓋

條件覆蓋（Condition Coverage）用于衡量構(gòu)成判定的各個(gè)條件得到執(zhí)行的程度。如果測(cè)試集合能夠使每個(gè)條件的真假至少各被執(zhí)行一次, 則說(shuō)測(cè)試集合滿(mǎn)足了條件覆蓋。例如，測(cè)試集合 {in_dis = 0, in_dis = 501}不滿(mǎn)足 (in_dis >= 0) && (in_dis <= 500)的條件覆蓋，因?yàn)椋瑮l件in_dis >= 0的假?zèng)]有被執(zhí)行。可見(jiàn)，判定覆蓋不能保證構(gòu)成判定的條件得到充分測(cè)試。同樣，條件覆蓋也不能保證判定覆蓋。

（3）判定-條件覆蓋

判定-條件覆蓋（Decision-Condition Coverage）用于衡量判定及構(gòu)成判定的每個(gè)條件得到執(zhí)行的程度。如果測(cè)試集合能夠使每個(gè)判定的真假至少各被執(zhí)行一次并且構(gòu)成判定的每個(gè)條件的真假至少各被執(zhí)行一次, 則說(shuō)該測(cè)試集合滿(mǎn)足了判定-條件覆蓋。例如測(cè)試集合{in_dis = 0, in_dis = -1, in_dis = 501}，滿(mǎn)足(in_dis >= 0) && (in_dis <= 500)的判定-條件覆蓋。

（4）修正的判定-條件覆蓋

由于在控制邏輯功能規(guī)約中，常存在一個(gè)條件值的變化引起整個(gè)判定結(jié)果改變的情況，而判定-條件覆蓋不能充分地測(cè)試這種場(chǎng)景。因此，修正的判定-條件覆蓋（Modified Decision-Condition Coverage，MC/DC）除了要求測(cè)試集合滿(mǎn)足外判定-條件覆蓋中所有的標(biāo)準(zhǔn)外，還期望構(gòu)成每個(gè)判定的每個(gè)條件能獨(dú)立地影響整個(gè)判定的結(jié)果。獨(dú)立地影響整個(gè)判定的結(jié)果是指在其它條件取值不變的情況下，只改變當(dāng)前條件的取值就能使得整個(gè)判定的結(jié)果發(fā)生變化。對(duì)于(in_dis >= 0) && (in_dis <= 500)而言，表2的測(cè)試集合滿(mǎn)足MC/DC。因tc1和tc3展現(xiàn)了條件in_dis >= 0獨(dú)立地對(duì)判定結(jié)果的影響（in_dis<=500始終取T，只有in_dis >= 0的取值從T變?yōu)镕），tc1和tc2展現(xiàn)了條件in_dis <= 500獨(dú)立地對(duì)判定結(jié)果的影響，且每個(gè)條件的真假值，判定的真假值也都被執(zhí)行了。

表 2

對(duì)于每個(gè)條件，可以采用異或算法計(jì)算能夠使其獨(dú)立影響整個(gè)判定結(jié)果時(shí)，其它條件的測(cè)試輸入值，具體過(guò)程可參考[5]。MC/DC是高覆蓋級(jí)別的標(biāo)準(zhǔn)，測(cè)試成本和難度較大，一般情況下，只有高安全等級(jí)軟件的測(cè)試才會(huì)被要求滿(mǎn)足MC/DC覆蓋。

（5）多條件覆蓋

多條件覆蓋(Multiple Conditions Coverage)用于衡量條件值的組合得到執(zhí)行的程度。如果測(cè)試集合能夠使得每個(gè)條件值的組合被至少執(zhí)行一次，那么則說(shuō)該測(cè)試集合滿(mǎn)足了多條件覆蓋。對(duì)于(in_dis >= 0) && (in_dis <= 500)而言，為了滿(mǎn)足多條件覆蓋，測(cè)試集合要測(cè)試下面4種值組合：

·in_dis >= 0為真且in_dis <= 500為真

·in_dis >= 0為真且in_dis <= 500為假

·in_dis >= 0為假且in_dis <= 500為真

·in_dis >= 0為假且in_dis <= 500為假

2.3 數(shù)據(jù)流覆蓋

程序本質(zhì)上是對(duì)各種變量按照邏輯不斷進(jìn)行讀寫(xiě)運(yùn)算的過(guò)程。數(shù)據(jù)流覆蓋從測(cè)試集合對(duì)變量讀寫(xiě)邏輯的覆蓋程度分析測(cè)試的充分性。在數(shù)據(jù)流覆蓋中，寫(xiě)叫做定義，讀叫做使用，讀寫(xiě)邏輯通過(guò)定義-使用路徑刻畫(huà)。對(duì)某一變量v而言，如果程序語(yǔ)句將一個(gè)值存入與v相關(guān)的存儲(chǔ)單元，則稱(chēng)該語(yǔ)句定義了變量v；如果程序語(yǔ)句訪(fǎng)問(wèn)了與v相關(guān)存儲(chǔ)單元中的值，則稱(chēng)該語(yǔ)句使用了變量v。連接變量定義和使用的定義清除的簡(jiǎn)單路徑，叫變量的定義-使用路徑。所謂定義清除是指除了路徑的開(kāi)始節(jié)點(diǎn)外，該路徑不存在變量的其它定義節(jié)點(diǎn)。變量的定義、使用和定義-使用路徑等信息可以通過(guò)數(shù)據(jù)流圖獲得。圖5是一個(gè)數(shù)據(jù)流圖示例，通過(guò)在CFG上增加節(jié)點(diǎn)和邊的定義和使用信息就可以得到數(shù)據(jù)流圖。圖中，def(n)和use(n)分別表示節(jié)點(diǎn)n的定義信息和使用信息。def(ni,nj)和use(ni,nj) 分別表示邊(ni,nj)的定義信息和使用信息。對(duì)于變量out_dis在節(jié)點(diǎn)1的定義而言，(1,2,6)是一條定義-使用路徑，而(1,2,3,4)則不是，因?yàn)樵谶@條路徑中，除了節(jié)點(diǎn)1外，還有節(jié)點(diǎn)4也是out_dis的定義節(jié)點(diǎn)。

圖 5

（1）全定義覆蓋

全定義覆蓋（All Defs Coverage）要求每個(gè)變量的每個(gè)定義至少被有效使用一次。測(cè)試集合T滿(mǎn)足全定義覆蓋，當(dāng)且僅當(dāng)存在一個(gè)執(zhí)行T產(chǎn)生的完整路徑集合L的子路徑集合包含每個(gè)變量的每個(gè)定義和某個(gè)該定義的使用構(gòu)成的定義-使用路徑集合。

（2）全使用覆蓋

全使用覆蓋（All Uses Coverage）要求每個(gè)變量的每個(gè)使用至少被執(zhí)行一次。測(cè)試集合T滿(mǎn)足全使用覆蓋，當(dāng)且僅當(dāng)存在一個(gè)執(zhí)行T產(chǎn)生的完整路徑集合L的子路徑集合包含每個(gè)變量的每個(gè)定義和所有該定義的使用構(gòu)成的定義-使用路徑集合。

（3）全定義-使用路徑覆蓋

全定義-使用路徑覆蓋（All DU-paths Coverage）要求所有定義-使用路徑至少被執(zhí)行一次。測(cè)試集合T滿(mǎn)足全定義-使用路徑覆蓋，當(dāng)且僅當(dāng)執(zhí)行T產(chǎn)生的完整路徑集合L訪(fǎng)問(wèn)了所有數(shù)據(jù)流圖中的定義-使用路徑。圖6給出了上述3個(gè)覆蓋準(zhǔn)則之間的差異說(shuō)明。

圖 6

03覆蓋準(zhǔn)則的揭錯(cuò)能力

揭錯(cuò)能力(Defect Detecting Ability)是指測(cè)試集合發(fā)現(xiàn)缺陷的能力。不同的覆蓋準(zhǔn)則，揭錯(cuò)能力不同。研究表明，如果運(yùn)用的方式合理，高級(jí)別的覆蓋準(zhǔn)則發(fā)現(xiàn)缺陷的能力比低級(jí)別的覆蓋準(zhǔn)則發(fā)現(xiàn)缺陷的能力強(qiáng)。覆蓋準(zhǔn)則級(jí)別的高低用“包含關(guān)系”定義：如果說(shuō)A準(zhǔn)則的覆蓋級(jí)別比B準(zhǔn)則高，即A包含B，則意味著滿(mǎn)足A的測(cè)試集合也滿(mǎn)足B。圖7給出了邏輯謂詞覆蓋準(zhǔn)則的包含情況。由圖可得，多條件覆蓋級(jí)別最高揭錯(cuò)能力最強(qiáng)，判定覆蓋和條件覆蓋之間沒(méi)有關(guān)系，意味著滿(mǎn)足判定覆蓋并不一定滿(mǎn)足條件覆蓋，反之亦然。語(yǔ)句覆蓋級(jí)別最低揭錯(cuò)能力最弱。

圖 7

參考資料：

[1] 朱鴻, 金陵紫著. 軟件質(zhì)量保障與測(cè)試. 科學(xué)出版社, 1997.

[2] J. B. Goodenough, S. L. Gerhart, Toward a theory of test data selection, IEEE Transaction on Software Engineering, SE-3 (June), 1975.

[3] W. E. Howden, Reliability of the path analysis testing strategy, IEEE Transaction on Software Engineering, SE-2, (Sept.), 208–215, 1976.

[4] Kelly J. Hayhurst，Dan S. Veerhusen，John J. Chilenski，Leanna K. Rierson，A Practical Tutorial on Modified Condition/Decision Coverage，Technical Report. NASA Langley Technical Report Server. 2001.

[5] Paul Ammann, Jeff Offutt, Introduction to software testing（2nd Edition）, Cambridge University Press, 2017.

審核編輯黃宇