2014組合測試解析

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

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

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

貪心算法IPO算法包括兩個(gè)核心步驟：水平擴(kuò)展和垂直擴(kuò)展。在這兩個(gè)維度的擴(kuò)展上，算法依據(jù)確定的因素來預(yù)備參數(shù)擴(kuò)展和取值的次序。以兩兩組合掩蓋為例，從這兩個(gè)維度來爭論IPO算法的影響因素及可擴(kuò)展點(diǎn)。在水平擴(kuò)展時(shí)，算法需要為矩陣增加一個(gè)參數(shù)列，給這一列上的每一項(xiàng)賦值，盡可能的掩蓋更多的未掩蓋t元組。因此，從以下三個(gè)影響因子：新增參數(shù)列的選擇、已有測試用例集的擴(kuò)展次序、新增參數(shù)的取值選擇進(jìn)展分析。水平擴(kuò)展后，算法可能還未完全掩蓋已擴(kuò)展參數(shù)的兩兩組合，因此，還需要進(jìn)展垂直擴(kuò)展，即增加新的測試用例以掩蓋尚未掩蓋的二元組。從上述例子中可以看出，垂直擴(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