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