基于符號(hào)ZBDD的組合測(cè)試研究.pdf

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

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

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

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