【正文】 狀態(tài)和狀態(tài)之間的動(dòng)作，這些動(dòng)作都是由一個(gè)個(gè)函數(shù)和方法的調(diào)用序列組成的。同時(shí)給系統(tǒng)留好接口，利于以后換用新的pairwise生成算法，具體的算法設(shè)計(jì)將在第四章介紹。首先構(gòu)造前兩個(gè)參數(shù)的所有組合，形成一個(gè)小的矩陣，再分別為矩陣添加一列和必要多的行，覆蓋完所有元組后結(jié)束。微軟開(kāi)發(fā)的工具PICT采用類似AETG的方法生成測(cè)試用例[22]，不同之處在于，PICT每次產(chǎn)生的結(jié)果是相同的。按照擴(kuò)展方式的不同，又可以分為一維擴(kuò)展和二維擴(kuò)展。近年來(lái)流行的模擬自然界行為的智能優(yōu)化算法中，目前已經(jīng)應(yīng)用到組合測(cè)試中的主要有模擬退火、禁忌搜索、遺傳算法等等。但我們可以利用局部搜索方法，比如啟發(fā)式搜索算法，在較短的時(shí)間內(nèi)就可以搜索出近似最優(yōu)解。數(shù)學(xué)構(gòu)造方法僅限于某些特定大小或者組合強(qiáng)度的覆蓋數(shù)組的構(gòu)造，不具有通用性。構(gòu)造最優(yōu)覆蓋數(shù)組的實(shí)際上是一個(gè)NP完全問(wèn)題[20]，我們知道，NP完全問(wèn)題是一系列可以互相轉(zhuǎn)化的問(wèn)題。坍塌的缺陷在于，最終得到的覆蓋數(shù)組往往并不是最優(yōu)解，一般比最優(yōu)解要大。Sloane在其網(wǎng)站上總結(jié)記錄了超過(guò)200個(gè)正交數(shù)組[18]。組合測(cè)試用例生成的本質(zhì)是構(gòu)造覆蓋數(shù)組，最早的構(gòu)造方法是利用正交數(shù)組，其定義和覆蓋數(shù)組類似，唯一區(qū)別在于正交數(shù)組中所有t元組出現(xiàn)的次數(shù)相同，而覆蓋數(shù)組不保證這一點(diǎn)。tway覆蓋數(shù)組的特點(diǎn)是，任意t個(gè)參數(shù)的所有排列組合都將分別出現(xiàn)在覆蓋數(shù)組的某一行中，比如上圖中的ABC、DEG、HIJ，三個(gè)參數(shù)共有8種排列組合（000、00001100、101111）都被覆蓋數(shù)組所覆蓋。圖24 3way覆蓋數(shù)組圖24列出了對(duì)于具有10個(gè)變量、每個(gè)變量各有兩種取值的3way覆蓋數(shù)組。相關(guān)的字體處理函數(shù)需要根據(jù)用戶的輸入來(lái)相應(yīng)修改文字效果，該函數(shù)需要在所有的可能情況下都正常工作，而一共有210=1024種可能。編號(hào)操作系統(tǒng)瀏覽器網(wǎng)絡(luò)協(xié)議處理器平臺(tái)數(shù)據(jù)庫(kù)1XPIEIPv4IntelMySQL2XPFireFoxIPv6AMDSybase3XPIEIPv6IntelOracle4OS XFireFoxIPv4AMDMySQL5OS XIEIPv4IntelSybase6OS XFireFoxIPv4IntelOracle7RHELIEIPv6AMDMySQL8RHELFireFoxIPv4IntelSybase9RHELFireFoxIPv4AMDOracle10OSXFireFoxIPv6AMDOracle表22 pairwise測(cè)試的配置即使被測(cè)軟件沒(méi)有配置選項(xiàng)，軟件仍要處理一些輸入。3=72種硬件平臺(tái)。2考慮一款受5個(gè)配置因素影響的應(yīng)用：操作系統(tǒng)（Windows XP、Apple OS X、Red Hat Enterprise Linux），瀏覽器（IE、FireFox），網(wǎng)絡(luò)協(xié)議（IPvIPv6），處理器平臺(tái)（Intel、AMD）和數(shù)據(jù)庫(kù)（MySQL、Sybase、Oracle），一共3因?yàn)闋可娴接布h(huán)境的搭建，配置參數(shù)測(cè)試中每增加一種測(cè)試情況比單純地多寫(xiě)一個(gè)測(cè)試用例所花的代價(jià)大得多。最壞的情況下，當(dāng)組合強(qiáng)度和參數(shù)的數(shù)目相等時(shí)，組合測(cè)試退化為枚舉測(cè)試。使用pairwise技術(shù)后，總測(cè)試用例數(shù)目從原來(lái)的MN下降到了約M * N。特別的，生成2way的測(cè)試用例集的方法被稱為pairwise（或allpairs）測(cè)試方法。以NASA應(yīng)用為例，67%的錯(cuò)誤由單個(gè)參數(shù)觸發(fā)，93%由兩個(gè)參數(shù)相互作用后觸發(fā)，98%由三個(gè)參數(shù)一起造成。圖23 不同組合強(qiáng)度下的錯(cuò)誤發(fā)現(xiàn)率圖23是NIST報(bào)告中總結(jié)的幾個(gè)應(yīng)用使用不同組合強(qiáng)度的測(cè)試用例集測(cè)試后的錯(cuò)誤發(fā)現(xiàn)率曲線[17]。該理論是基于以下事實(shí)的，軟件中的錯(cuò)誤大部分都是由單個(gè)參數(shù)所導(dǎo)致的，一般最多是由兩個(gè)參數(shù)相互作用而觸發(fā)，三個(gè)或三個(gè)以上的情況幾乎沒(méi)有。但是現(xiàn)實(shí)并不允許測(cè)試人員這么做，因?yàn)樵斐傻臏y(cè)試用例數(shù)量是指數(shù)性爆炸增長(zhǎng)的，N個(gè)分別有M種取值的影響因素將需要MN個(gè)測(cè)試用例來(lái)完成測(cè)試。軟件能否經(jīng)得住各種條件下的考驗(yàn)，是軟件測(cè)試需要解決的問(wèn)題。問(wèn)題有許多可能的影響因素，比如跟軟件安裝所在機(jī)器的操作系統(tǒng)類型有關(guān)，或者是系統(tǒng)物理內(nèi)存的大小，甚至網(wǎng)卡型號(hào)等等?？梢酝ㄟ^(guò)指定初始遍歷節(jié)點(diǎn)和限定路徑長(zhǎng)度的方法來(lái)減少生成測(cè)試用例的數(shù)量，但是更好的是下面介紹的組合測(cè)試。我們選用的是FSM模型，所以可以利用圖論中的一些遍歷方法，比如廣度優(yōu)先遍歷算法或者深度優(yōu)先遍歷算法，每找到的一條可執(zhí)行路徑對(duì)應(yīng)于一個(gè)測(cè)試用例。馬爾可夫鏈模型為MBT提供了測(cè)試的側(cè)重點(diǎn)，即著重測(cè)試那些用戶經(jīng)常使用的功能。把復(fù)雜系統(tǒng)拆分為相對(duì)獨(dú)立的組件單獨(dú)分析，也是所有MBT測(cè)試用例生成方法通用的竅門。類似于描述程序所有可執(zhí)行路徑的控制流和描述程序所有變量定義和內(nèi)存使用的數(shù)據(jù)流，事件流模型描述的是GUI上所有可執(zhí)行的事件序列。模型檢測(cè)會(huì)遇到的問(wèn)題是，生成的用例中存在過(guò)多冗余用例,導(dǎo)致軟件測(cè)試執(zhí)行的代價(jià)增加。無(wú)論檢測(cè)結(jié)果是滿足屬性還是違背屬性，都可以形成測(cè)試用例。其中約束編程是一種通過(guò)約束來(lái)描述變量間關(guān)系的編程方法，求解約束的方法有布爾式求解方法和數(shù)值分析方法。當(dāng)需要為程序的特定執(zhí)行路徑尋找輸入時(shí)，沿著路徑使用符號(hào)執(zhí)行的方法，結(jié)合途中遇到的一些分支斷言，我們可以求出預(yù)期輸入所需要滿足的約束。定理證明方法原先是被用于自動(dòng)證明數(shù)學(xué)公式，MBT生成測(cè)試用例時(shí)根據(jù)邏輯表達(dá)式的有效說(shuō)明把模型劃分為不同等價(jià)類，每個(gè)等價(jià)類描述了SUT的某一行為。MBT中使用的測(cè)試用例生成方法主要依賴于所使用的模型表現(xiàn)形式，針對(duì)不同的模型表現(xiàn)形式，研究者分別想出了一些解決方案。如果以后需要額外考慮系統(tǒng)事件和測(cè)試輸入的概率分布，只需要為每個(gè)狀態(tài)之間的遷移動(dòng)作增加概率相關(guān)屬性，非常輕松地支持統(tǒng)計(jì)式模型。我們也并不需要描述系統(tǒng)行為隨著時(shí)間變化的變化情況，RBAC測(cè)試中不涉及分布式并發(fā)操作，側(cè)重關(guān)心系統(tǒng)控制流而不是數(shù)據(jù)流，可見(jiàn)基本的FSM模型就已經(jīng)滿足相關(guān)要求。圖22 FSM示例我們工具主要面向的是RBAC功能的測(cè)試，頻繁關(guān)心具有不同權(quán)限的不同角色所能執(zhí)行的操作。之后又有人刪去了Harel的狀態(tài)圖模型中的部分特性，同時(shí)增加了一些新的特性，形成了統(tǒng)一建模語(yǔ)言（UML，Unified Modeling Language）狀態(tài)機(jī)模型。圖22是一個(gè)描述了門的四種不同狀態(tài)及其轉(zhuǎn)換關(guān)系的FSM。通常是以節(jié)點(diǎn)和弧線的形式出現(xiàn)，節(jié)點(diǎn)代表系統(tǒng)的狀態(tài)，弧線代表系統(tǒng)的動(dòng)作或操作。想要同時(shí)滿足以上所有的特性是很困難的，但是可以把幾種不同的模型整合成一個(gè)，揚(yáng)長(zhǎng)避短地得到理想模型。然后在被測(cè)系統(tǒng)（SUT， System Under Test）環(huán)境中真正執(zhí)行所有測(cè)試用例（步驟51），可以利用測(cè)試腳本來(lái)自動(dòng)化執(zhí)行測(cè)試，最終得到測(cè)試結(jié)果（步驟52）。首先在系統(tǒng)需求或者規(guī)約文檔的基礎(chǔ)上建立某種形式的模型（步驟1），模型說(shuō)明了系統(tǒng)所有的潛在行為意圖。至于產(chǎn)生其它輔助性內(nèi)容的工具，它在不同項(xiàng)目之間不具有可移植性，只有根據(jù)不同項(xiàng)目來(lái)專門設(shè)計(jì)實(shí)現(xiàn)。如果沒(méi)有使用正確的模型表現(xiàn)形式，會(huì)拖累影響整個(gè)測(cè)試流程。第二章 基于模型的測(cè)試2.. MBT一般操作流程基于模型的測(cè)試依賴于三項(xiàng)關(guān)鍵技術(shù)：模型的表現(xiàn)形式、測(cè)試用例的生成算法和產(chǎn)生其它輔助性內(nèi)容（包括預(yù)期結(jié)果）的工具[12]。第五章通過(guò)一個(gè)虛構(gòu)的自動(dòng)取款機(jī)（ATM， Automatic Teller Machines）系統(tǒng)來(lái)演示如何使用我們完成的工具進(jìn)行MBT測(cè)試。第三章介紹系統(tǒng)的總體架構(gòu)和簡(jiǎn)要闡述系統(tǒng)各模塊的功能。因?yàn)榕c傳統(tǒng)的單純正交排列組合測(cè)試相比，配對(duì)組合測(cè)試技術(shù)具有較大的優(yōu)越性。該測(cè)試工具將被主要用于微軟公司SCCM系統(tǒng)的基于角色權(quán)限控制（RBAC， RoleBased Access Control）功能的測(cè)試。. 項(xiàng)目背景和論文結(jié)構(gòu). 項(xiàng)目背景本課題來(lái)源于作者實(shí)習(xí)所在的微軟公司，旨在遵照基于模型的軟件測(cè)試?yán)碚撻_(kāi)始實(shí)現(xiàn)一款自動(dòng)化測(cè)試工具，該工具能夠支持有限狀態(tài)機(jī)模型的輸入，然后自動(dòng)生成抽象測(cè)試用例。目前代表性的支持MBT的測(cè)試工具有：IBM公司的GOTCHATCBeans軟件測(cè)試套件，面向Java、C/C++語(yǔ)言編寫(xiě)的應(yīng)用程序接口（API, Application Program Interfaces）和軟件協(xié)議[7]；微軟公司的Spec Explorer工具，具有創(chuàng)建軟件行為模型、可視化分析模型、驗(yàn)證模型有效性和根據(jù)模型生成測(cè)試用例等功能[8]；“凈室”公司的CleanTest，主要用于凈室軟件工程中使用的統(tǒng)計(jì)測(cè)試過(guò)程[9]。傳統(tǒng)的人工測(cè)試的測(cè)試用例都是依據(jù)系統(tǒng)需求定義的，MBT的測(cè)試用例生成算法難免產(chǎn)生一些無(wú)效冗余的測(cè)試用例，測(cè)試用例通過(guò)率不再是衡量軟件測(cè)試效率的有效標(biāo)準(zhǔn)。實(shí)施MBT的測(cè)試人員需要具有比普通測(cè)試人員更強(qiáng)的系統(tǒng)抽象能力，因?yàn)镾UT很可能并不容易建模。傳統(tǒng)的測(cè)試方法很可能需要重新設(shè)計(jì)編寫(xiě)所有測(cè)試用例，MBT只需要調(diào)整模型后再自動(dòng)生成測(cè)試用例。我們知道，軟件開(kāi)發(fā)中的錯(cuò)誤越早發(fā)現(xiàn)需要付出的修復(fù)代價(jià)越小，MBT把一些錯(cuò)誤扼殺在需求階段，貢獻(xiàn)無(wú)疑是巨大的。有時(shí)侯測(cè)試用例沒(méi)有通過(guò)，并不是因?yàn)槌绦蚓帉?xiě)的錯(cuò)誤，而是因?yàn)橄到y(tǒng)需求定義存在錯(cuò)誤。而且MBT可以提高測(cè)試效率，因?yàn)槿斯y(cè)試受限于測(cè)試人員的思維活躍程度，MBT使用的測(cè)試用例生成算法和啟發(fā)式用例選擇機(jī)制能夠快速生成大量測(cè)試用例，達(dá)到對(duì)模型更高的覆蓋率卻僅需要多花費(fèi)少量運(yùn)行測(cè)試用例生成程序的時(shí)間。當(dāng)然MBT也不是萬(wàn)能的，它發(fā)現(xiàn)錯(cuò)誤的能力很大程度上依賴于建模和選擇測(cè)試用例選擇要求人員的水平。而微軟公司的某一應(yīng)用中，MBT發(fā)現(xiàn)了多10倍的錯(cuò)誤[14]。事實(shí)證明，MBT確實(shí)具有很強(qiáng)的錯(cuò)誤發(fā)現(xiàn)能力。模型所帶來(lái)的回報(bào)也是巨大的，因?yàn)橐坏┠Ｐ捅淮_立且其能夠準(zhǔn)確反映被測(cè)系統(tǒng)的真實(shí)需求，軟件測(cè)試工具就能夠分析模型自動(dòng)得到測(cè)試用例。為了抽象出理想的模型可能需要花費(fèi)一定的時(shí)間，但是模型構(gòu)建的工作可以在軟件開(kāi)發(fā)生命周期的早期就開(kāi)始，只要求被測(cè)系統(tǒng)的需求定義完成即可。當(dāng)測(cè)試本身就需要多次重復(fù)時(shí)（比如回歸測(cè)試、壓力測(cè)試），其優(yōu)點(diǎn)將更加顯著。絕大部分軟件測(cè)試工具并不能自動(dòng)完成整個(gè)測(cè)試過(guò)程，測(cè)試人員依然需要事先編寫(xiě)好測(cè)試腳本或測(cè)試用例，即一組測(cè)試輸入、執(zhí)行條件和預(yù)期結(jié)果?；诖a的測(cè)試是指通過(guò)程序提供的公共接口，直接驗(yàn)證各個(gè)類、庫(kù)和模塊在不同的輸入情況下返回結(jié)果的正確性與否，如xUnit系列框架。于是人們需要開(kāi)發(fā)一些自動(dòng)化工具來(lái)管理或者執(zhí)行測(cè)試過(guò)程，雖然編寫(xiě)軟件測(cè)試工具需要引入額外的工作量，但是軟件測(cè)試工具能大大提高軟件測(cè)試的效率和質(zhì)量，并且市面上也已經(jīng)存在著許多現(xiàn)成的測(cè)試工具。常用的判斷標(biāo)準(zhǔn)有：代碼覆蓋率、測(cè)試用例通過(guò)率、缺陷數(shù)量收斂率等等。時(shí)間測(cè)試階段 1956面向調(diào)試時(shí)期19571978面向論證時(shí)期19791982面向破壞時(shí)期19831987面向評(píng)估時(shí)期1988 now 面向防止時(shí)期表11 測(cè)試的發(fā)展階段[6]