2014組合測(cè)試解析

組合測(cè)試緒論軟件系統(tǒng)的故障往往是由一些難以預(yù)料的系統(tǒng)因素及其相互作用而引起的，為了檢測(cè)這些故障，必需設(shè)計(jì)一組測(cè)試用例，對(duì)系統(tǒng)因素的各種組合狀況進(jìn)展充分掩蓋的測(cè)試。通過對(duì)各個(gè)參數(shù)的不同輸入數(shù)據(jù)進(jìn)展組合，可以驗(yàn)證軟件系統(tǒng)在不同條件下的行為。例如：對(duì)于微軟的Word軟件，其字體設(shè)置對(duì)話框總共有19個(gè)輸入?yún)?shù)需要設(shè)置.經(jīng)過等價(jià)類劃分和邊界值處理后，假設(shè)進(jìn)展全組合的測(cè)試，那么會(huì)產(chǎn)生上萬個(gè)測(cè)試用例。充分組合測(cè)試的最終測(cè)試用例數(shù)是浩大的，如何從中選擇一個(gè)規(guī)模較小的、能更有效的找出軟件故障的子集作為測(cè)試用例集是測(cè)試用例生成中一個(gè)很重要的問題。緒論依據(jù)爭(zhēng)論統(tǒng)計(jì)說明，很多程序的錯(cuò)誤都是由少數(shù)幾個(gè)參數(shù)及參數(shù)之間的相互作用而導(dǎo)致。Willace和Kuhn等人在美國(guó)國(guó)家標(biāo)準(zhǔn)與技術(shù)協(xié)會(huì)〔NIST〕期刊上發(fā)表的論文指出：經(jīng)過大量的調(diào)查爭(zhēng)論后覺察，在軟件把握的醫(yī)療系統(tǒng)中，98%的故障是由變量對(duì)之間的交互所導(dǎo)致的；Kuhn和Reilly等人在對(duì)Mozilla掃瞄器的錯(cuò)誤報(bào)告進(jìn)展分析和爭(zhēng)論后說明：該系統(tǒng)的70%以上的錯(cuò)誤是由2個(gè)以內(nèi)的參數(shù)相互作用而引發(fā)的，90%以上的錯(cuò)誤是由3個(gè)以內(nèi)的參數(shù)相互作用而引發(fā)的。緒論組合測(cè)試其根本思想是從統(tǒng)計(jì)學(xué)的角度對(duì)測(cè)試試驗(yàn)進(jìn)展設(shè)計(jì)。該方法設(shè)計(jì)的測(cè)試用例以參數(shù)及參數(shù)之間的交互為掩蓋標(biāo)準(zhǔn)，雖然不能夠進(jìn)展完全的測(cè)試，但是利用該方法進(jìn)展的測(cè)試得到的結(jié)果能夠在確定程度上反映系統(tǒng)的內(nèi)部規(guī)律，具有確定的代表性。這種方法對(duì)由系統(tǒng)輸入、外部大事等相互作用而產(chǎn)生的故障系統(tǒng)，具有較強(qiáng)的檢錯(cuò)力氣。目前，對(duì)組合測(cè)試用例生成方法的爭(zhēng)論主要包括：兩兩組合測(cè)試用例生成技術(shù)N維組合測(cè)試用例生成技術(shù)變力度組合測(cè)試用例生成技術(shù)帶優(yōu)先級(jí)的組合測(cè)試用例生成技術(shù)帶約束的組合測(cè)試用例生成技術(shù)組合測(cè)試中錯(cuò)誤定位技術(shù)緒論兩兩組合掩蓋測(cè)試用例生成例如假設(shè)系統(tǒng)有3個(gè)因素，每個(gè)因素有3個(gè)不同的取值，分別為A1,A2,A3；B1,B2,B3；C1,C2,C3。對(duì)于測(cè)試用例t=〔A1,B1,C1〕，其對(duì)應(yīng)的兩兩組合表示是一個(gè)集合S’={〔A1,B1〕,〔A1,C1〕,〔B1,C1〕}，如以以下圖：測(cè)試用例t=〔A1,B1,C1〕掩蓋了〔A1,B1〕,〔A1,C1〕,〔B1,C1〕3個(gè)兩兩組合元素。兩兩組合掩蓋測(cè)試舉例一個(gè)網(wǎng)絡(luò)信息系統(tǒng)如表所示，需要進(jìn)展兼容性測(cè)試，假設(shè)需要進(jìn)展完全的測(cè)試，那么該系統(tǒng)需要81個(gè)測(cè)試用例，但是假設(shè)承受兩兩組合測(cè)試技術(shù)進(jìn)展測(cè)試，只需要9個(gè)測(cè)試用例。兩兩組合掩蓋測(cè)試舉例兩兩組合掩蓋測(cè)試舉例兩兩組合測(cè)試用例設(shè)計(jì)方法生成最優(yōu)的兩兩組合測(cè)試用例集的問題已經(jīng)被證明是一個(gè)NP問題。在實(shí)際的測(cè)試用例生成過程中，一般嘗試用各種近似算法求解。這些方法大致可以分為如下幾類：數(shù)學(xué)構(gòu)造法、貪心算法、元啟發(fā)式算法。不同的測(cè)試用例集所掩蓋的兩兩組合元素?cái)?shù)量不同。在同樣大小的測(cè)試用例集的條件下，掩蓋的兩兩組合元素?cái)?shù)量越多，說明該測(cè)試用例集的測(cè)試效果越好。數(shù)學(xué)構(gòu)造法目前的數(shù)學(xué)構(gòu)造方法根本上都是基于正交矩陣，并在此根底上開發(fā)了組合測(cè)試用例生成工具。比方：Bell試驗(yàn)室研發(fā)的CATS工具，Williams開發(fā)的Tconfig工具，IBMHaifa爭(zhēng)論院的WHITCH工程。

代數(shù)方法由于各種代數(shù)構(gòu)造的限制，僅適用于成對(duì)組合掩蓋測(cè)試用例的自動(dòng)生成，不簡(jiǎn)潔被擴(kuò)展到更高維數(shù)的組合掩蓋的測(cè)試用例的自動(dòng)生成中。兩兩組合測(cè)試用例設(shè)計(jì)方法開頭時(shí)，由于A、B、C三個(gè)元素的最低水平數(shù)為2，我們則以因素為3，水平數(shù)為2來選擇正交表，并進(jìn)展用例的生成。此時(shí)測(cè)試用例集為{(A1,B1,C1),(A1,B2,C2),(A2,B1,C2),(A2,B2,C2)}。此時(shí)，未被掩蓋的成對(duì)組合W={(A1,C3),(A2,C3),(B1,C3),(B2,C3)}。在W中，A1消逝1次，A2消逝1次，B1消逝1次，B2消逝1次，C3消逝3次，因此，選擇消逝次數(shù)最多的C3產(chǎn)生測(cè)試用例T5=(*,*,C3)。接下來，要從A1,A2中選擇一個(gè)作為因素A的水平值。假設(shè)選擇A1，則可以掩蓋(A1,C3)；假設(shè)選擇A2，則可以掩蓋(A2,C3)。不妨選擇A1,則T5=(A1,*,C3)。下面要從B1,B2中選擇一個(gè)作為因素B的水平值。假設(shè)選擇B1，則可以掩蓋W中的(B1,C3)；假設(shè)選擇B2，則可以掩蓋W中的(B2,C3)。由于選擇B1,B2所掩蓋的W中的成對(duì)組合個(gè)數(shù)一樣，不妨選擇B2，即T5=(A1,B2,C3)，此時(shí)未被掩蓋的成對(duì)組合集合W={(A2,C3),(B1,C3)}。依據(jù)同樣方法，可得到T6=(A2,B1,C3)。參與T6后，W為空。生成過程完畢。正交設(shè)計(jì)法舉例存在缺乏：1〕正交矩陣問題始終是組合數(shù)學(xué)界爭(zhēng)論的問題，目前小規(guī)模的正交表已經(jīng)被構(gòu)造出來，但是對(duì)于大規(guī)模的正交矩陣的構(gòu)造目前還沒有很好的方法。2〕現(xiàn)在學(xué)術(shù)界對(duì)于對(duì)稱正交表的爭(zhēng)論較多，對(duì)于混合水平的正交表的構(gòu)造爭(zhēng)論較少，而混合水平的正交表更加符合實(shí)際工程的組合測(cè)試需求。3〕在正交矩陣中每個(gè)組合消逝的次數(shù)是一樣的，這在組合測(cè)試中不是必需的，只需要每個(gè)組合被掩蓋一次就可以，所以依據(jù)正交試驗(yàn)設(shè)計(jì)得到的兩兩組合測(cè)試用例集中可能含有冗余的測(cè)試用例。正交設(shè)計(jì)法

貪心算法的思想是從空矩陣開頭，逐行或者逐列地?cái)U(kuò)展矩陣，直到全部的t組合都被覆蓋。按照策略的不同，些貪心算法可以分為使用逐條生成測(cè)試用例〔one-test-at-a-time〕策略和逐參數(shù)擴(kuò)展〔in-parameter-order〕策略兩種不同的策略。其中，one-test-at-a-time策略是使用一維擴(kuò)展的擴(kuò)展方式，IPO策略是一種二維擴(kuò)展的擴(kuò)展方式。貪心算法基于one-test-at-a-time策略的算法即一維擴(kuò)展方式，是在構(gòu)造掩蓋數(shù)組時(shí)，依據(jù)貪心策略依次增加一行，使得這一行掩蓋一些未掩蓋的t元組，直到全部t元組都被掩蓋。使用one-test-at-a-time策略，抱負(fù)的狀況是使用全局貪心算法，即在每次選擇測(cè)試用例時(shí)，選擇能最大限度掩蓋Uncover中組合的用例。AETG是美國(guó)貝爾試驗(yàn)室的和等人依據(jù)啟發(fā)式方法研制的測(cè)試數(shù)據(jù)生成工具。該工具可以依據(jù)測(cè)試要求，產(chǎn)生滿足因素的成對(duì)組合掩蓋或多個(gè)因素的組合掩蓋測(cè)試數(shù)據(jù)。AETG開頭于一個(gè)空的測(cè)試用例集，每次往測(cè)試用例集參與一個(gè)測(cè)試用例。為了得到一個(gè)新的測(cè)試用例，首先依據(jù)貪心算產(chǎn)生一組候選用例，然后從中選擇能夠掩蓋最多未被掩蓋的成對(duì)組合的用例。類似算法有：CAST,TCG,DDA,PSSA等。基于one-test-at-a-time策略的算法設(shè)某個(gè)被測(cè)系統(tǒng)有3個(gè)因素〔A、B、C〕，因素A有2個(gè)值〔A1和A2〕，因素B有2個(gè)值〔B1和B2〕，因素C有3個(gè)值〔C1、C2、C3〕。依據(jù)AETG算法，測(cè)試用例生成過程如以以以下圖所示。基于one-test-at-a-time策略的算法基于one-test-at-a-time策略的算法〔2〕逐參數(shù)擴(kuò)展策略逐參數(shù)擴(kuò)展策略與逐條用例擴(kuò)展策略的不同之處在于逐參數(shù)擴(kuò)展是以參數(shù)為單位進(jìn)展擴(kuò)展，假設(shè)只有一個(gè)參數(shù)需要擴(kuò)展，那么直接添加到系統(tǒng)中即可，當(dāng)有多個(gè)參數(shù)需要擴(kuò)展時(shí)，就要對(duì)參數(shù)進(jìn)展排序，然后將參數(shù)取值個(gè)數(shù)最多的一個(gè)的參數(shù)作為候選的參數(shù)。由于每個(gè)參數(shù)都有不同的取值，使用貪心算法來選擇適宜的參數(shù)值添加到相應(yīng)的測(cè)試用例中，當(dāng)照舊有未被掩蓋的組合時(shí)，需要添加新的測(cè)試用例來掩蓋這些漏掉的組合。貪心算法IPO算法美國(guó)北卡羅萊納大學(xué)計(jì)算機(jī)系的Y.Lei和提出一種基于參數(shù)挨次的漸進(jìn)擴(kuò)展的兩兩組合掩蓋測(cè)試數(shù)據(jù)生成方法。與AETG算法不同，IPO算法的根本思想是以參數(shù)為對(duì)象，初始時(shí)先生成滿足組合掩蓋的測(cè)試要求的用例集合T，然后一個(gè)個(gè)擴(kuò)展剩余的參數(shù)，直至全部的參數(shù)都被包涵到測(cè)試用例中，并在算法中時(shí)刻都盡可能使測(cè)試集個(gè)數(shù)大小保持最優(yōu)。

貪心算法IPO算法包括兩個(gè)核心步驟：水平擴(kuò)展和垂直擴(kuò)展。在這兩個(gè)維度的擴(kuò)展上，算法依據(jù)確定的因素來預(yù)備參數(shù)擴(kuò)展和取值的次序。以兩兩組合掩蓋為例，從這兩個(gè)維度來爭(zhēng)論IPO算法的影響因素及可擴(kuò)展點(diǎn)。在水平擴(kuò)展時(shí)，算法需要為矩陣增加一個(gè)參數(shù)列，給這一列上的每一項(xiàng)賦值，盡可能的掩蓋更多的未掩蓋t元組。因此，從以下三個(gè)影響因子：新增參數(shù)列的選擇、已有測(cè)試用例集的擴(kuò)展次序、新增參數(shù)的取值選擇進(jìn)展分析。水平擴(kuò)展后，算法可能還未完全掩蓋已擴(kuò)展參數(shù)的兩兩組合，因此，還需要進(jìn)展垂直擴(kuò)展，即增加新的測(cè)試用例以掩蓋尚未掩蓋的二元組。從上述例子中可以看出，垂直擴(kuò)展是將尚未擴(kuò)展的用例直接作為新增用例參與。這將形成新增用例中存在一些no-care位，如何在后續(xù)擴(kuò)展中為這些no-care位賦值也將影響IPO算法的結(jié)果。IPO算法IPO算法舉例IPO算法舉例貪心算法的根本思想是從小到大構(gòu)造矩陣，直到全部的掩蓋條件都得到滿足．另外一種查找最優(yōu)的(或者較優(yōu)的)掩蓋數(shù)組的方法是，利用一個(gè)已有的數(shù)組，通過適宜的變換得到一個(gè)更優(yōu)的掩蓋矩陣．這樣，通過逐次變換得到較優(yōu)的矩陣．為了避開陷入局部最優(yōu)，算法承受了一些啟發(fā)式的策略，通過多樣化或變異的方法跳出局部最優(yōu)點(diǎn)．元啟發(fā)式搜尋算法元啟發(fā)式算法主要可以分為兩類：個(gè)體搜尋算法〔IndividualSearch〕和群體搜尋算法〔Popu