基于符號ZBDD的組合測試研究.pdf

1、軟件測試是避免軟件故障、保障軟件質(zhì)量的重要手段。在軟件測試中，測試用例集的規(guī)模和錯誤檢出率直接影響軟件測試的效果。因此，如何選取一個較小規(guī)模且具有較高錯誤檢出率的測試用例集是軟件測試的核心任務和關鍵問題。
　　組合測試（combinatorial testing，CT）是系統(tǒng)測試中一種非常有效的方法，它能在花費較小代價的情況下保證錯誤檢出率，在工業(yè)界被廣泛的應用。但是生成最小測試用例集問題的復雜度已經(jīng)被證明是NPC問題。組合測試方

2、法的復雜性吸引了軟件領域以及組合數(shù)學領域的大量學者的重視和研究。
　　采用符號或者隱式描述技術是減緩組合復雜性問題的一種可行策略。有序二叉決策圖(Ordered Binary Decision Diagram，OBDD)及其擴展形式可實現(xiàn)狀態(tài)空間或者變量組合的隱式表示和搜索，是迄今為止最為有效的符號技術之一。OBDD在待測系統(tǒng)、測試用例以及約束的表示上有著占用更小空間的優(yōu)勢。但是，對于很多系統(tǒng)，使用OBDD進行符號表示和計算時仍然

3、存在著節(jié)點冗余的問題。零壓縮二叉決策圖(Zero-suppressed Binary Decision Diagram，ZBDD)是為了克服OBDD表示和處理組合集合的不足而提出的一種新的數(shù)據(jù)結構。在組合集合的表示和處理問題上，相對于OBDD，ZBDD擁有更低的空間需求和更簡捷的表示方法等優(yōu)點。而且問題的規(guī)模越龐大，ZBDD的優(yōu)勢越明顯。所以本文基于ZBDD對組合測試進行了研究，主要研究了基于ZBDD的組合測試用例生成方法，利用ZBDD

4、的結構特性對測試系統(tǒng)進行更為緊湊的表示，結合貪心算法思想，生成2-4維覆蓋強度的測試用例集。論文的主要工作及取得的研究成果如下：
　　(1)設計了基于ZBDD的組合測試用例生成算法。首先利用ZBDD的pD-刪除規(guī)則的結點高度共享的特點對測試系統(tǒng)進行描述刻畫，然后利用ZBDD隱式操作，再結合貪心算法思想，在生成測試用例的同時逐步覆蓋所有組合，從而得到滿足覆蓋強度要求的測試用例集。
　　(2)設計了基于ZBDD的帶約束的組合測試