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