【文章內(nèi)容簡介】 at Enterprise Linux），瀏覽器（IE、FireFox），網(wǎng)絡(luò)協(xié)議（IPvIPv6），處理器平臺(tái)（Intel、AMD）和數(shù)據(jù)庫（MySQL、Sybase、Oracle），一共32223=72種硬件平臺(tái)。pairwise測試只需要設(shè)計(jì)如下10個(gè)測試，就覆蓋了每一種影響因素和另外一種影響因素的所有組合。編號(hào)操作系統(tǒng)瀏覽器網(wǎng)絡(luò)協(xié)議處理器平臺(tái)數(shù)據(jù)庫1XPIEIPv4IntelMySQL2XPFireFoxIPv6AMDSybase3XPIEIPv6IntelOracle4OS XFireFoxIPv4AMDMySQL5OS XIEIPv4IntelSybase6OS XFireFoxIPv4IntelOracle7RHELIEIPv6AMDMySQL8RHELFireFoxIPv4IntelSybase9RHELFireFoxIPv4AMDOracle10OSXFireFoxIPv6AMDOracle表22 pairwise測試的配置即使被測軟件沒有配置選項(xiàng)，軟件仍要處理一些輸入。例如，Word 2010應(yīng)用程序至少允許用戶對(duì)拖黑文字進(jìn)行10種不同操作：設(shè)為上標(biāo)、設(shè)為下標(biāo)、加粗、加下劃線、設(shè)為斜體、加刪除線、加灰色背景、加陰影效果、加倒影效果、加熒光效果。相關(guān)的字體處理函數(shù)需要根據(jù)用戶的輸入來相應(yīng)修改文字效果，該函數(shù)需要在所有的可能情況下都正常工作，而一共有210=1024種可能。前面的經(jīng)驗(yàn)告訴我們，3way的測試用例就能夠達(dá)到90%以上的錯(cuò)誤發(fā)現(xiàn)率，具有較高的收益代價(jià)比。圖24 3way覆蓋數(shù)組圖24列出了對(duì)于具有10個(gè)變量、每個(gè)變量各有兩種取值的3way覆蓋數(shù)組。覆蓋數(shù)組并不唯一，這只是其中一種情況。tway覆蓋數(shù)組的特點(diǎn)是，任意t個(gè)參數(shù)的所有排列組合都將分別出現(xiàn)在覆蓋數(shù)組的某一行中，比如上圖中的ABC、DEG、HIJ，三個(gè)參數(shù)共有8種排列組合（000、00001100、101111）都被覆蓋數(shù)組所覆蓋。覆蓋數(shù)組的每一行對(duì)應(yīng)一個(gè)測試用例，相比之前的1024個(gè)測試用例，組合測試只需要13個(gè)測試用例。組合測試用例生成的本質(zhì)是構(gòu)造覆蓋數(shù)組，最早的構(gòu)造方法是利用正交數(shù)組，其定義和覆蓋數(shù)組類似，唯一區(qū)別在于正交數(shù)組中所有t元組出現(xiàn)的次數(shù)相同，而覆蓋數(shù)組不保證這一點(diǎn)。在某些特殊的情況下，正交數(shù)組就是最優(yōu)的覆蓋數(shù)組，為此，如何構(gòu)造正交數(shù)組問題吸引了大量的研究者研究。Sloane在其網(wǎng)站上總結(jié)記錄了超過200個(gè)正交數(shù)組[18]。利用計(jì)算機(jī)也可以自動(dòng)求解出部分類型的正交數(shù)組，由已知的大覆蓋數(shù)組構(gòu)造小覆蓋數(shù)組的方法被稱為坍塌[19]。坍塌的缺陷在于，最終得到的覆蓋數(shù)組往往并不是最優(yōu)解，一般比最優(yōu)解要大。另一種構(gòu)造方法剛好相反，是由已知的小覆蓋數(shù)組遞歸構(gòu)造出大覆蓋數(shù)組。構(gòu)造最優(yōu)覆蓋數(shù)組的實(shí)際上是一個(gè)NP完全問題[20]，我們知道，NP完全問題是一系列可以互相轉(zhuǎn)化的問題。于是我們可以利用和借鑒其它NP完全問題的研究成果來構(gòu)造覆蓋數(shù)組，比如第一個(gè)被證明為NP完全問題的可滿足性問題，整數(shù)規(guī)劃問題，圖論問題等等。數(shù)學(xué)構(gòu)造方法僅限于某些特定大小或者組合強(qiáng)度的覆蓋數(shù)組的構(gòu)造，不具有通用性。NP完全問題則是困擾了人類多年的超級(jí)難題，目前還沒有突破性解法，所以轉(zhuǎn)化為其它問題也是大同小異。但我們可以利用局部搜索方法，比如啟發(fā)式搜索算法，在較短的時(shí)間內(nèi)就可以搜索出近似最優(yōu)解。啟發(fā)式搜索算法是利用一個(gè)已有的數(shù)組，通過合適的變換得到一個(gè)更優(yōu)的覆蓋矩陣，不斷地變換直到得到一個(gè)較優(yōu)的矩陣。近年來流行的模擬自然界行為的智能優(yōu)化算法中，目前已經(jīng)應(yīng)用到組合測試中的主要有模擬退火、禁忌搜索、遺傳算法等等。更為有效的方法是貪心算法，貪心算法的思想是從空矩陣開始，然后逐行或者逐列地?cái)U(kuò)展矩陣，直到所有的t元組都被覆蓋。按照擴(kuò)展方式的不同，又可以分為一維擴(kuò)展和二維擴(kuò)展。商業(yè)工具AETG最先提出一維擴(kuò)展的方法[21]，依次增加一行，每次盡可能多地覆蓋未覆蓋的t元組。微軟開發(fā)的工具PICT采用類似AETG的方法生成測試用例[22]，不同之處在于，PICT每次產(chǎn)生的結(jié)果是相同的。Lei等人提出的IPO（Inparameterorder）[23]方法屬于二維擴(kuò)展，該算法主要針對(duì)pairwise測試。首先構(gòu)造前兩個(gè)參數(shù)的所有組合，形成一個(gè)小的矩陣，再分別為矩陣添加一列和必要多的行，覆蓋完所有元組后結(jié)束。我們將模仿PICT工具中pairwise算法的主要思想，使用一維擴(kuò)展的貪心算法來生成覆蓋數(shù)組。同時(shí)給系統(tǒng)留好接口，利于以后換用新的pairwise生成算法，具體的算法設(shè)計(jì)將在第四章介紹。. MBT預(yù)期輸出生成三大關(guān)鍵技術(shù)就只剩下輔助性內(nèi)容生成工具了，輔助性工具主要還是為了解決預(yù)期輸出的生成問題。前面我們構(gòu)造了系統(tǒng)的模型，模型描述了系統(tǒng)的狀態(tài)和狀態(tài)之間的動(dòng)作，這些動(dòng)作都是由一個(gè)個(gè)函數(shù)和方法的調(diào)用序列組成的。SUT提供的API往往不能和測試用例的要求完全契合，為了讓測試用例能夠順利地在SUT上執(zhí)行，需要測試人員在SUT之上再包裝一層，即圖21中的適配器層。嚴(yán)格地說，我們編寫的工具只負(fù)責(zé)生成基本的測試用例框架，或者稱為抽象的測試用例。測試用例中相當(dāng)于使用了打樁的設(shè)計(jì)模式，樁的實(shí)際實(shí)現(xiàn)由最終的測試人員補(bǔ)充完成，樁的實(shí)現(xiàn)包括對(duì)SUT提供的API的封裝組合和測試判斷邏輯的編寫。我們把這些樁叫做token，token對(duì)應(yīng)于適配器層中的某個(gè)函數(shù)和方法，兩者可以直接一一對(duì)應(yīng)，也可以先序列化為可擴(kuò)展標(biāo)記語言（XML，Extensible Markup Language）文件再利用XML解析器之類的工具生成測試用例。這樣MBT的整個(gè)測試工具都變得項(xiàng)目之間可移植了，如果某一測試條件和預(yù)期結(jié)果不同則在token中拋出異常，拋出的異常隨后被測試工具捕獲，最終判定該測試用例不通過。圖25展示了一個(gè)測試工具自動(dòng)生成的測試用例，用戶需要實(shí)現(xiàn)token_1和token_2的具體邏輯，然后測試用例就能夠被真正執(zhí)行了。token_1和token_2執(zhí)行過程中如果發(fā)現(xiàn)錯(cuò)誤會(huì)觸發(fā)異常，程序打印出錯(cuò)誤提示，同時(shí)導(dǎo)致測試用例的總錯(cuò)誤個(gè)數(shù)加一。反之，一切正常并給出通過提示。圖25 測試用例示例另外我們也可以利用pairwise來完成部分情況下預(yù)期輸出的生成。對(duì)于相同輸出結(jié)果的某些參數(shù)取值組合，把輸出結(jié)果也當(dāng)作pairwise算法輸入?yún)?shù)的一項(xiàng)，輸出結(jié)果列和其它輸入?yún)?shù)的區(qū)別在于其取值唯一。PICT工具還支持混合組合強(qiáng)度的測試用例生成，以及輸入各種約束，比如指定某些參數(shù)的組合形式必須出現(xiàn)或者不出現(xiàn)，所以具有較強(qiáng)的預(yù)期輸出生成能力。不過如果預(yù)期輸出涉及復(fù)雜的判斷邏輯，還是使用委托給token來處理的方法較好。第三章 系統(tǒng)架構(gòu)3.. 功能概述及流程課題要求完成的基于模型的自動(dòng)化測試工具的功能包括：支持輸入FSM模型、支持添加token、支持pairwise組合測試、支持生成測試用例框架、支持序列化FSM模型到文件和反序列化讀入。其中考慮到token的可復(fù)用性，用戶可以直接在工具上定義token順序執(zhí)行序列組成的函數(shù)過程，更復(fù)雜的函數(shù)過程則通過添加新的token實(shí)現(xiàn)。用戶使用該工具生成測試用例的流程如下：圖31 生成測試用例流程用戶可以直接繪制FSM模型，或者在以前保存的模型基礎(chǔ)上修改模型，工具支持FSM模型的序列化與反序列化。繪制FSM模型時(shí)首先需要定義一些FSM的狀態(tài)轉(zhuǎn)換動(dòng)作中用到的token和這些token組成的若干函數(shù)過程，隨后在模型繪制面板中畫出FSM模型相應(yīng)的有向圖。FSM模型的有向圖包括代表不同狀態(tài)的圓形節(jié)點(diǎn)，以及代表狀態(tài)間轉(zhuǎn)換動(dòng)作的弧線。一個(gè)token或函數(shù)過程可以在相同的或者不同的狀態(tài)轉(zhuǎn)換動(dòng)作中被反復(fù)使用，只要求這些token或函數(shù)過程方法頭中所定義的參數(shù)被正確地賦予某個(gè)常量或者變量。變量可以有多個(gè)允許的取值，用戶在pairwise相關(guān)面板輸入各個(gè)變量的可能取值，接下來工具將分析FSM模型尋找所以可執(zhí)行路徑，同時(shí)結(jié)合路徑長度限制和pairwise技術(shù)來生成測試用例。最后用戶還可以在生成的測試用例中再人工選擇部分測試用例出來，保存為最終需要被執(zhí)行的測試用例。. 系統(tǒng)架構(gòu)工具設(shè)計(jì)的主要目的是為了自動(dòng)生成測試用例，而模型是驅(qū)動(dòng)MBT各測試過程的根本，所以系統(tǒng)架構(gòu)中最核心的部分是FSM的數(shù)據(jù)模型，數(shù)據(jù)模型描述了FSM中各個(gè)狀態(tài)和轉(zhuǎn)換動(dòng)作的詳細(xì)屬性。比如狀態(tài)名稱，轉(zhuǎn)換動(dòng)作名稱，用戶所定義token的名稱和所需輸入輸出參數(shù)，函數(shù)過程的名稱和其中包含的token執(zhí)行序列等等。圖32 系統(tǒng)總體架構(gòu)用戶不是生硬地使用形式化語言來描述FSM數(shù)據(jù)模型，工具提供了可視化界面，實(shí)現(xiàn)了鼠標(biāo)選取不同繪圖元素再拖拽調(diào)整的繪圖方式。此外，為了持久化保存繪制好的FSM模型，系統(tǒng)包含了序列化模塊，用于模型的序列化與反序列化。測試用例的生成過程是基于兩大模塊來完成的，F(xiàn)SM模型遍歷模塊負(fù)責(zé)生成各種可執(zhí)行路徑，pairwise測試模塊負(fù)責(zé)生成參數(shù)變量取值的不同組合。最后把參數(shù)變量取值代入可執(zhí)行路徑中，即得到測試用例。第四章 系統(tǒng)各功能實(shí)現(xiàn)4.前一章中我們介紹了系統(tǒng)的整體架構(gòu)，下面將逐一介紹系統(tǒng)各模塊的具體實(shí)現(xiàn)，整個(gè)系統(tǒng)都使用C語言編寫完成。. FSM數(shù)據(jù)模型實(shí)現(xiàn)我們知道FSM數(shù)據(jù)模型是影響系統(tǒng)的關(guān)鍵，圖41列出了系統(tǒng)實(shí)際實(shí)現(xiàn)過程中FSM數(shù)據(jù)模型相關(guān)各類之間的關(guān)系。對(duì)于一些簡單的set和get方法圖中并沒有標(biāo)出，其它輔助性的方法也予于省略。圖41 FSM數(shù)據(jù)模型的類圖類FSM中記錄著系統(tǒng)FSM數(shù)據(jù)模型的所有信息，它里面有兩個(gè)鏈表分別記錄FSM的狀態(tài)實(shí)例和轉(zhuǎn)換動(dòng)作實(shí)例，同時(shí)有兩個(gè)Dictionary分別記錄狀態(tài)和轉(zhuǎn)換動(dòng)作的名稱與實(shí)例之間的映射關(guān)系。狀態(tài)由類State描述，該類的屬性有狀態(tài)標(biāo)識(shí)id、狀態(tài)類型type和狀態(tài)后置動(dòng)作鏈表nextActions。我們定義了三種狀態(tài)類型：Entry、Free和Exit，Entry和Exit分別代表初始狀態(tài)和終止?fàn)顟B(tài)，F(xiàn)ree代表其他自由狀態(tài)。狀態(tài)動(dòng)作由類Action描述，該類的屬性有動(dòng)作標(biāo)識(shí)id、出發(fā)狀態(tài)名稱from、目的狀態(tài)名稱to以及動(dòng)作的方法實(shí)現(xiàn)鏈表stubs。在尋找可執(zhí)行的測試路徑過程中，程序從初始狀態(tài)開始深度遍歷FSM有向圖，直到到達(dá)某個(gè)終止?fàn)顟B(tài)或路徑長度達(dá)到限制才結(jié)束。類Tour的每個(gè)實(shí)例代表一條被發(fā)現(xiàn)的可執(zhí)行路徑，因?yàn)橛脩舨⒉粎⑴cTour的命名，所以該類中設(shè)置了一個(gè)全局靜態(tài)的標(biāo)識(shí)計(jì)數(shù)器域idCounter，每新創(chuàng)建一個(gè)新實(shí)例時(shí)計(jì)數(shù)器自動(dòng)加一，必要的時(shí)候可以通過ResetIdCounter方法重置計(jì)數(shù)器。除了以上代表FSM實(shí)體組成部分的類，F(xiàn)SM數(shù)據(jù)模型還必須描述SUT相關(guān)部分的信息。抽象類ActionImpl描述了測試中調(diào)用的SUT接口，準(zhǔn)確地說是測試適配器層中的接口，它的兩個(gè)抽象方法GenDefa