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

蘇亭 華東師范大學軟件工程學院教授

版塊 |鑒源論壇 · 觀模

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

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

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

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

對測試集合進行期望的覆蓋分析是當前判定測試充分性的主要方法。本文也從覆蓋角度說明測試的充分性。實踐表明，如果正確合理地運用覆蓋分析，其對保證軟件和軟件測試本身的質量能夠起到積極的作用。例如，結構覆蓋分析（Structural Coverage Analysis）是在安全關鍵系統領域被廣泛應用的覆蓋分析方法。當與“基于需求的測試”相結合（這個前提很重要，詳情可參考[4]），結構覆蓋分析不僅可以發現測試集合的漏測，更能發現代碼中的功能缺失（本該實現而沒有實現的功能）和功能多余（無中生有的功能）[4]，更好地保證系統的安全性（Safety）。

02有哪些主流的覆蓋準則

傳統上，主流的覆蓋準則有控制流覆蓋（Control Flow Coverage）、數據流覆蓋(Data Flow Coverage)、變異覆蓋(Mutation Coverage)、分域覆蓋(Domain Partition Coverage)。由于面向代碼的結構，因此，常把前兩者合稱為結構覆蓋（Structural Coverage）。每種覆蓋根據需要滿足的不同要求又包含不同的準則。圖1展示了主流的覆蓋準則。本文主要說明控制流覆蓋和數據流覆蓋。

圖1 主流的覆蓋準則

2.1控制流覆蓋

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

圖 2

圖 3

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

表 1

（1）語句覆蓋

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

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

（2）分支覆蓋

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

分支覆蓋是比語句覆蓋嚴格的準則，同時，也需要注意分支也不一定是可執性的。

（3）路徑覆蓋

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

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

（4）基路徑覆蓋

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

圖 4

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

基路徑是比分支覆蓋強，但比路徑覆蓋弱的準則，可以有效地降低必須測試的路徑數，但同樣存在不可行的基路徑的問題。

2.2邏輯謂詞覆蓋

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

（1）判定覆蓋

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

（2）條件覆蓋

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

（3）判定-條件覆蓋

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

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

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

表 2

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

（5）多條件覆蓋

多條件覆蓋(Multiple Conditions Coverage)用于衡量條件值的組合得到執行的程度。如果測試集合能夠使得每個條件值的組合被至少執行一次，那么則說該測試集合滿足了多條件覆蓋。對于(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 數據流覆蓋

程序本質上是對各種變量按照邏輯不斷進行讀寫運算的過程。數據流覆蓋從測試集合對變量讀寫邏輯的覆蓋程度分析測試的充分性。在數據流覆蓋中，寫叫做定義，讀叫做使用，讀寫邏輯通過定義-使用路徑刻畫。對某一變量v而言，如果程序語句將一個值存入與v相關的存儲單元，則稱該語句定義了變量v；如果程序語句訪問了與v相關存儲單元中的值，則稱該語句使用了變量v。連接變量定義和使用的定義清除的簡單路徑，叫變量的定義-使用路徑。所謂定義清除是指除了路徑的開始節點外，該路徑不存在變量的其它定義節點。變量的定義、使用和定義-使用路徑等信息可以通過數據流圖獲得。圖5是一個數據流圖示例，通過在CFG上增加節點和邊的定義和使用信息就可以得到數據流圖。圖中，def(n)和use(n)分別表示節點n的定義信息和使用信息。def(ni,nj)和use(ni,nj) 分別表示邊(ni,nj)的定義信息和使用信息。對于變量out_dis在節點1的定義而言，(1,2,6)是一條定義-使用路徑，而(1,2,3,4)則不是，因為在這條路徑中，除了節點1外，還有節點4也是out_dis的定義節點。

圖 5

（1）全定義覆蓋

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

（2）全使用覆蓋

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

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

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

圖 6

03覆蓋準則的揭錯能力

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

圖 7

參考資料：

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

審核編輯黃宇