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

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

版塊 |鑒源論壇 · 觀模

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

01充分性問題的提出和變遷

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

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

對測試集合進(jìn)行期望的覆蓋分析是當(dāng)前判定測試充分性的主要方法。本文也從覆蓋角度說明測試的充分性。實踐表明，如果正確合理地運(yùn)用覆蓋分析，其對保證軟件和軟件測試本身的質(zhì)量能夠起到積極的作用。例如，結(jié)構(gòu)覆蓋分析（Structural Coverage Analysis）是在安全關(guān)鍵系統(tǒng)領(lǐng)域被廣泛應(yīng)用的覆蓋分析方法。當(dāng)與“基于需求的測試”相結(jié)合（這個前提很重要，詳情可參考[4]），結(jié)構(gòu)覆蓋分析不僅可以發(fā)現(xiàn)測試集合的漏測，更能發(fā)現(xiàn)代碼中的功能缺失（本該實現(xiàn)而沒有實現(xiàn)的功能）和功能多余（無中生有的功能）[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)，因此，常把前兩者合稱為結(jié)構(gòu)覆蓋（Structural Coverage）。每種覆蓋根據(jù)需要滿足的不同要求又包含不同的準(zhǔn)則。圖1展示了主流的覆蓋準(zhǔn)則。本文主要說明控制流覆蓋和數(shù)據(jù)流覆蓋。

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

2.1控制流覆蓋

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

圖 2

圖 3

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

表 1

（1）語句覆蓋

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

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

（2）分支覆蓋

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

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

（3）路徑覆蓋

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

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

（4）基路徑覆蓋

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

圖 4

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

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

2.2邏輯謂詞覆蓋

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

（1）判定覆蓋

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

（2）條件覆蓋

條件覆蓋（Condition Coverage）用于衡量構(gòu)成判定的各個條件得到執(zhí)行的程度。如果測試集合能夠使每個條件的真假至少各被執(zhí)行一次, 則說測試集合滿足了條件覆蓋。例如，測試集合 {in_dis = 0, in_dis = 501}不滿足 (in_dis >= 0) && (in_dis <= 500)的條件覆蓋，因為，條件in_dis >= 0的假沒有被執(zhí)行?？梢姡卸ǜ采w不能保證構(gòu)成判定的條件得到充分測試。同樣，條件覆蓋也不能保證判定覆蓋。

（3）判定-條件覆蓋

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

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

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

表 2

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

（5）多條件覆蓋

多條件覆蓋(Multiple Conditions Coverage)用于衡量條件值的組合得到執(zhí)行的程度。如果測試集合能夠使得每個條件值的組合被至少執(zhí)行一次，那么則說該測試集合滿足了多條件覆蓋。對于(in_dis >= 0) && (in_dis <= 500)而言，為了滿足多條件覆蓋，測試集合要測試下面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ì)上是對各種變量按照邏輯不斷進(jìn)行讀寫運(yùn)算的過程。數(shù)據(jù)流覆蓋從測試集合對變量讀寫邏輯的覆蓋程度分析測試的充分性。在數(shù)據(jù)流覆蓋中，寫叫做定義，讀叫做使用，讀寫邏輯通過定義-使用路徑刻畫。對某一變量v而言，如果程序語句將一個值存入與v相關(guān)的存儲單元，則稱該語句定義了變量v；如果程序語句訪問了與v相關(guān)存儲單元中的值，則稱該語句使用了變量v。連接變量定義和使用的定義清除的簡單路徑，叫變量的定義-使用路徑。所謂定義清除是指除了路徑的開始節(jié)點外，該路徑不存在變量的其它定義節(jié)點。變量的定義、使用和定義-使用路徑等信息可以通過數(shù)據(jù)流圖獲得。圖5是一個數(shù)據(jù)流圖示例，通過在CFG上增加節(jié)點和邊的定義和使用信息就可以得到數(shù)據(jù)流圖。圖中，def(n)和use(n)分別表示節(jié)點n的定義信息和使用信息。def(ni,nj)和use(ni,nj) 分別表示邊(ni,nj)的定義信息和使用信息。對于變量out_dis在節(jié)點1的定義而言，(1,2,6)是一條定義-使用路徑，而(1,2,3,4)則不是，因為在這條路徑中，除了節(jié)點1外，還有節(jié)點4也是out_dis的定義節(jié)點。

圖 5

（1）全定義覆蓋

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

（2）全使用覆蓋

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

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

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

圖 6

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

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

圖 7

參考資料：

[1] 朱鴻, 金陵紫著. 軟件質(zhì)量保障與測試. 科學(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.

審核編輯黃宇