1、基于模型的自動化測試工具的實現摘要基于模型的測試是本文首先介紹了Atmel-View框架以及菜單系統UI在其中所將扮演的角色、與各個功能模塊間的關系。其次講解了Atmel-View內存映射窗口結合OSD應用的UI設計思想，涉及了多圖層表現的想法，硬件OSD與偽OSD的比較使用。然后詳細闡述了基于Atmel-View的菜單系統方案和框架結構，針對最重要的MenuMode菜單構建函數分析其數據抽象、界面繪制和事件響應處理過程。其后介紹Nucleus Plus，給出進程通信、進程同步在菜單系統中支持藍牙模塊的應用方法。本方案的實現提供了一套層次化、結構化、可擴展的電子相框菜單系統，并有效支持了藍牙模

2、塊的應用。關鍵詞：OSD，內存映射窗口，菜單系統，UIFULFILL UI OF DIGITAL PHOTO FRAMEBASED ON ATMEL-VIEWABSTRACTAtmel Corporation's Atmel-View is the application for board AT76C120, it has already provided low level realization for digital photo frame, and it could be an extendable and mature solution. Based on current

3、functions of Atmel-View, we will design and fulfill the Menu System.Firstly the framework of Atmel-View, which role Menu System UI acts and how it relates with other function modules were introduced in this paper. Then the concept of SDRAM- Mapping Window with OSD's usage was proposed. It referr

4、ed to the idea of multiple image layer interface and the comparison the usage of hardware OSD and Pseudo OSD. Then the details of Menu System's framework were illustrated. The process of data abstraction, interface drawing and event handling were analyzed for the most important Menu building fun

5、ction MenuMode. After that Nucleus Plus was introduced and the method to use process communication, process synchronization for supporting Bluetooth module in Menu System was given. The UI solution provides a layered, structural and extendable Menu System for digital photo frame. And it effectively

6、supports Bluetooth module.Key words: OSD, SDRAM-Mapping Window, Menu System, UI目 錄第一章 緒論21.1.軟件測試簡介21.2.軟件測試工具發展現狀21.3.項目背景和論文結構21.3.1.項目背景21.3.2.論文結構2第二章 基于模型的測試22.1.MBT一般操作流程22.2.MBT模型表現形式22.3.MBT測試用例生成22.4.MBT預期輸出生成2第三章 系統架構23.1.功能概述及流程23.2.系統架構2第四章 系統各功能實現2第五章 實例分析：ATM系統2第六章 結論及展望2參考文獻2第一章 緒論1.1

7、. 軟件測試簡介隨著電子信息化的飛速發展，計算機軟件已經遍布于人類社會的各個角落，遠至月球探測衛星的發射系統，近至個人攜帶的MP3音樂播放器。但是軟件帶來巨大便利的同時，軟件中的任何微小缺陷也可能帶來難以估量的損失。據美國國家標準技術研究院（NIST）2002年公布的一份研究報告顯示，軟件故障平均每年對美國經濟造成的損失約為595億美元，占其國民生產總值的0.6% 1 。因此，如何保證軟件的質量顯得尤為關鍵。軟件測試能夠有效地幫助軟件開發人員找出系統中存在的錯誤，從而在很大程度上保證軟件的質量?，F代軟件工程理論將軟件測試作為軟件開發過程的重要組成部分，軟件開發過程中有一半以上的資源都花費在軟件

8、測試上。早期的軟件測試等同于程序調試，1957年Charles Baker才正式將兩者區別開來，他認為調試側重于保證程序運行，而測試側重于保證程序解決問題2。1979年Myers提出“測試是帶有發現錯誤意圖去執行程序的過程”3，越是發現了錯誤才說明測試過程的成功。1983年美國國家標準局（NBS）發表了評估軟件生命周期各階段的測試方法4，同年美國電氣和電子工程師協會（IEEE）發布了八大軟件測試相關文檔的標準5，人們開始利用這些評估標準來衡量測試軟件的質量。1988年David Gelperin等在書中寫道，“測試是為了證明軟件符合需求規約，發現缺陷和防止錯誤”6。時間測試階段 -1956面向

9、調試時期1957-1978面向論證時期1979-1982面向破壞時期1983-1987面向評估時期1988- now 面向防止時期表1-1 測試的發展階段6測試不可能遍歷所有可能出現的情況，必須在適當的時候終止測試。如果一味地追求缺陷數量，很可能得不償失。常用的判斷標準有：代碼覆蓋率、測試用例通過率、缺陷數量收斂率等等。圖1-1 缺陷數量收斂圖1.2. 軟件測試工具發展現狀純手工地進行軟件測試往往是費時費力的，而且測試人員容易因為疏忽產生失誤，測試準確性無法得到足夠的保證。于是人們需要開發一些自動化工具來管理或者執行測試過程，雖然編寫軟件測試工具需要引入額外的工作量，但是軟件測試工具能大大提高

10、軟件測試的效率和質量，并且市面上也已經存在著許多現成的測試工具。名稱產商簡介WinRunnerMercury Interactive支持自動錄制、檢測和回放用戶操作LoadRunnerMercury Interactive模擬大量并發負載來預測系統性能TestDirectorMercury Interactive基于Web的測試管理系統RobotIBM具有測試和管理的雙重功能xUnit最流行的開源單元測試框架SilkTestBorland軟件功能測試工具WASMicrosoft強大的網站壓力測試工具JTestParasoft針對Java語言的自動化白盒測試工具JMeterApache100%用

11、Java實現的功能和性能測試工具WebLoadRadViewWeb性能測試和分析工具表1-2 常用軟件測試工具一般來說，自動化測試可以分為：基于代碼的測試和基于圖形化用戶界面的測試?；诖a的測試是指通過程序提供的公共接口，直接驗證各個類、庫和模塊在不同的輸入情況下返回結果的正確性與否，如xUnit系列框架。而基于圖形化用戶界面的測試則是通過模擬用戶動作行為（比如鍵盤輸入、鼠標點擊），產生某些事件來觀察和判斷程序響應是否滿足預期，如WinRunner。絕大部分軟件測試工具并不能自動完成整個測試過程，測試人員依然需要事先編寫好測試腳本或測試用例，即一組測試輸入、執行條件和預期結果。測試用例能夠被

12、快速和反復地執行，方便地使得發現的軟件錯誤重現。當測試本身就需要多次重復時（比如回歸測試、壓力測試），其優點將更加顯著?；谀Ｐ偷臏y試（MBT, Model-Based Testing）是一種輕量級自動生成測試用例的方法，測試人員的關注點在于構建一個能夠描述被測系統各方面數據和行為的形式化機器可讀模型。為了抽象出理想的模型可能需要花費一定的時間，但是模型構建的工作可以在軟件開發生命周期的早期就開始，只要求被測系統的需求定義完成即可。而且往往在將非形式化的需求轉化為形式化的模型過程中，需求中的遺漏和不足部分將被發現。模型所帶來的回報也是巨大的，因為一旦模型被確立且其能夠準確反映被測系統的真實需求

13、，軟件測試工具就能夠分析模型自動得到測試用例。軟件測試的主要目的就是發現錯誤。事實證明，MBT確實具有很強的錯誤發現能力。IBM公司和BMW公司的研究表明，MBT發現的錯誤和手工設計的測試集發現的錯誤數量差不多。而微軟公司的某一應用中，MBT發現了多10倍的錯誤14。其它的一些研究結果中（如圖1-2），和人工測試相比MBT都是發現更多或者相同數量的錯誤。當然MBT也不是萬能的，它發現錯誤的能力很大程度上依賴于建模和選擇測試用例選擇要求人員的水平。圖1-2 各種測試方法整個測試過程的花費時間圖14MBT能否降低測試的花費和時間，取決于建立和維護模型加上生成測試用例花費的時間是否比其它方法設計和維

14、護測試集所需要的時間少，通常情況下答案是肯定的。而且MBT可以提高測試效率，因為人工測試受限于測試人員的思維活躍程度，MBT使用的測試用例生成算法和啟發式用例選擇機制能夠快速生成大量測試用例，達到對模型更高的覆蓋率卻僅需要多花費少量運行測試用例生成程序的時間。如果SUT支持大規模地測試，MBT必然將發現更多的錯誤。有時侯測試用例沒有通過，并不是因為程序編寫的錯誤，而是因為系統需求定義存在錯誤。其它形式的軟件測試一般無法發現此類錯誤，但是MBT可以。我們知道，軟件開發中的錯誤越早發現需要付出的修復代價越小，MBT把一些錯誤扼殺在需求階段，貢獻無疑是巨大的。此外， MBT具有良好的應付軟件需求變更

15、的能力。傳統的測試方法很可能需要重新設計編寫所有測試用例，MBT只需要調整模型后再自動生成測試用例。凡事有利必有弊，好的模型可以讓測試過程一帆風順，模型也給測試過程帶來了許多問題。實施MBT的測試人員需要具有比普通測試人員更強的系統抽象能力，因為SUT很可能并不容易建模。當MBT的測試用例沒有通過時，測試人員無法斷定是SUT存在錯誤還是建模存在錯誤，增加了錯誤分析的代價。傳統的人工測試的測試用例都是依據系統需求定義的，MBT的測試用例生成算法難免產生一些無效冗余的測試用例，測試用例通過率不再是衡量軟件測試效率的有效標準。認識到這些MBT的不足之處，我們才能更加正確地利用MBT。目前代表性的支持

16、MBT的測試工具有：IBM公司的GOTCHA-TCBeans軟件測試套件，面向Java、C/C+語言編寫的應用程序接口（API, Application Program Interfaces）和軟件協議7；微軟公司的Spec Explorer工具，具有創建軟件行為模型、可視化分析模型、驗證模型有效性和根據模型生成測試用例等功能8；“凈室”公司的CleanTest，主要用于凈室軟件工程中使用的統計測試過程9。此外，軍方也積極嘗試MBT技術，比如美國海軍水面戰中心開發的SMERFS10和CASRE11。1.3. 項目背景和論文結構1.3.1. 項目背景本課題來源于作者實習所在的微軟公司，旨在遵照基

17、于模型的軟件測試理論開始實現一款自動化測試工具，該工具能夠支持有限狀態機模型的輸入，然后自動生成抽象測試用例。用戶填充實現完整的測試用例后，此工具能執行測試用例并給出測試報告。該測試工具將被主要用于微軟公司SCCM系統的基于角色權限控制（RBAC， Role-Based Access Control）功能的測試。特別地，在測試用例生成過程中算法需要結合參數配對組合測試技術，盡可能縮減測試用例數目卻又不影響測試質量。因為與傳統的單純正交排列組合測試相比，配對組合測試技術具有較大的優越性。1.3.2. 論文結構本文第二章主要介紹MBT測試技術，依照MBT測試的一般流程來說明工具使用的模型表現形式、

18、測試用例生成算法和預期輸出的生成。第三章介紹系統的總體架構和簡要闡述系統各模塊的功能。第四章使用類圖和算法偽代碼詳細討論系統的設計和實現。第五章通過一個虛構的自動取款機（ATM， Automatic Teller Machines）系統來演示如何使用我們完成的工具進行MBT測試。最后作簡要的總結及展望。第二章 基于模型的測試2.2.1. MBT一般操作流程基于模型的測試依賴于三項關鍵技術：模型的表現形式、測試用例的生成算法和產生其它輔助性內容（包括預期結果）的工具12。模型是MBT技術的核心，不同領域的不同軟件系統適用的模型表現形式都不盡相同，測試人員應該結合被測系統的工作特點和自身對模型的熟

19、悉程度來慎重選擇。如果沒有使用正確的模型表現形式，會拖累影響整個測試流程。針對各個不同的模型表現形式，如今已有許多測試用例算法與之對應，我們可以在實際應用過程中靈活地借鑒參考來設計自己的算法。至于產生其它輔助性內容的工具，它在不同項目之間不具有可移植性，只有根據不同項目來專門設計實現。圖2-1 MBT一般操作流程13上圖展示了MBT的一般操作流程。首先在系統需求或者規約文檔的基礎上建立某種形式的模型（步驟1），模型說明了系統所有的潛在行為意圖。接下來需要定義測試用例的選擇要求（步驟2），形成測試用例規約（步驟3），編寫算法將其應用于模型之上來生成測試用例（步驟4）。然后在被測系統（SUT， S

20、ystem Under Test）環境中真正執行所有測試用例（步驟5-1），可以利用測試腳本來自動化執行測試，最終得到測試結果（步驟5-2）。2.2. MBT模型表現形式理想的模型需要容易被測試人員理解，能夠把大的復雜的問題描述成小的簡單的系統，最好還是以一種測試用例生成工具方便識別的形式。想要同時滿足以上所有的特性是很困難的，但是可以把幾種不同的模型整合成一個，揚長避短地得到理想模型。在MBT中使用過的模型可能有幾十甚至上百種，我們不可能也沒有必要去逐一了解，Mark Utting和Bruno Legeard把它們大致分為以下幾種 14：類型示例基于Pre/PostB、OCL、JML、Spe

21、c#、Z基于轉換FSM、狀態圖、UML狀態機統計式馬爾可夫鏈基于歷史消息隊列圖、UML順序圖函數式HOL系統操作式Petri網數據流式Lustre、塊狀圖表2-1 MBT模型分類基于轉換的模型是我們最為熟悉的模型類型，它們集中于描述系統在不同狀態之間的轉換過程。通常是以節點和弧線的形式出現，節點代表系統的狀態，弧線代表系統的動作或操作。有限狀態機（FSM， Finite State Machine）模型可以被認為是該類模型的鼻祖，是極其重要的一種模型表現形式。圖2-2是一個描述了門的四種不同狀態及其轉換關系的FSM。Harel在FSM的基礎上添加了層次、并發和交流概念，擴展成了狀態圖模型15，

22、從而在面對復雜系統時也能夠輕松建立模型。之后又有人刪去了Harel的狀態圖模型中的部分特性，同時增加了一些新的特性，形成了統一建模語言（UML，Unified Modeling Language）狀態機模型。UML狀態機模型用于定義類之間狀態相關的行為，包括方法調用和數據域的修改。圖2-2 FSM示例我們工具主要面向的是RBAC功能的測試，頻繁關心具有不同權限的不同角色所能執行的操作。把系統抽象為變量集合和修改這些變量操作的基于Pre/Post的模型需要測試人員預先學習一段時間才能完全掌握，所以基本不予考慮。我們也并不需要描述系統行為隨著時間變化的變化情況，RBAC測試中不涉及分布式并發操作，

23、側重關心系統控制流而不是數據流，可見基本的FSM模型就已經滿足相關要求。而且FMS模型也最為簡便，測試工具識別起來沒有任何問題，降低了編寫測試工具的難度，測試人員構建模型時可以從SUT設計文檔中的UML狀態圖稍加變化直接轉化而來。如果以后需要額外考慮系統事件和測試輸入的概率分布，只需要為每個狀態之間的遷移動作增加概率相關屬性，非常輕松地支持統計式模型。2.3. MBT測試用例生成軟件測試過程中的執行和監督過程已經可以使用現代化的自動測試工具代替完成，至于如何生成測試用例，依然是一件棘手的事情。MBT中使用的測試用例生成方法主要依賴于所使用的模型表現形式，針對不同的模型表現形式，研究者分別想出了

24、一些解決方案。如果系統的模型是由一系列邏輯表達式所組成的，那么可以使用定理證明的方法。定理證明方法原先是被用于自動證明數學公式，MBT生成測試用例時根據邏輯表達式的有效說明把模型劃分為不同等價類，每個等價類描述了SUT的某一行為。這些等價類就可以用于生成測試用例，最簡單的劃分方法是析取范式的方法。當需要為程序的特定執行路徑尋找輸入時，沿著路徑使用符號執行的方法，結合途中遇到的一些分支斷言，我們可以求出預期輸入所需要滿足的約束。于是可以用各種約束來建立MBT的模型，收集不同執行路徑中數據約束再利用約束編程中的方法求解得到測試用例。其中約束編程是一種通過約束來描述變量間關系的編程方法，求解約束的方

25、法有布爾式求解方法和數值分析方法。MBT自然還會讓人想到模型檢測，即檢測模型是否滿足特定的屬性。無論檢測結果是滿足屬性還是違背屬性，都可以形成測試用例。但是一般來說反例的作用更大，因為測試用例中的各種斷言正是通過反例來生成的，從而有效地識別出系統是否正常工作。模型檢測會遇到的問題是，生成的用例中存在過多冗余用例,導致軟件測試執行的代價增加。為此，Hamon 等人詳細討論提出了高效模型檢測的方法16。類似于描述程序所有可執行路徑的控制流和描述程序所有變量定義和內存使用的數據流，事件流模型描述的是GUI上所有可執行的事件序列。通常情況下，GUI又可以分為不同的層次結構，比如整個GUI系統是由各種對

26、話框所組成的，那么系統的事件流圖就是由對話框各自的事件流圖組成的。把復雜系統拆分為相對獨立的組件單獨分析，也是所有MBT測試用例生成方法通用的竅門。馬爾可夫鏈也是MBT中生成測試用例的重要方法之一，它由兩大部件組成：代表系統所有使用場景的FSM和評價FSM來說明系統統計性使用信息的操作說明。馬爾可夫鏈模型為MBT提供了測試的側重點，即著重測試那些用戶經常使用的功能。因為對于系統中那些極少概率出現的錯誤，是幾乎不可能被發現的。我們選用的是FSM模型，所以可以利用圖論中的一些遍歷方法，比如廣度優先遍歷算法或者深度優先遍歷算法，每找到的一條可執行路徑對應于一個測試用例。當FSM包含的狀態比較多時，遍

27、歷組成FSM有向圖產生的測試用例數量可能太多，不僅難以測試包含冗余測試用例?？梢酝ㄟ^指定初始遍歷節點和限定路徑長度的方法來減少生成測試用例的數量，但是更好的是下面介紹的組合測試。軟件開發者和用戶經常還會遇到這樣的問題，把同樣的軟件應用從一臺機器換到另外一臺機器上使用時，原先從未出過故障的軟件突然變得無法正常使用。問題有許多可能的影響因素，比如跟軟件安裝所在機器的操作系統類型有關，或者是系統物理內存的大小，甚至網卡型號等等。除了硬件環境的不同，軟件接受的輸入參數也很可能不同，比如同一款Web應用發布后，不同國家的用戶將會輸入不同編碼的內容。軟件能否經得住各種條件下的考驗，是軟件測試需要解決的問題

28、。當然，最簡單和理想的情況下是把所有可能出現的硬件配置和參數取值都測試一遍。但是現實并不允許測試人員這么做，因為造成的測試用例數量是指數性爆炸增長的，N個分別有M種取值的影響因素將需要MN個測試用例來完成測試。后來人們發現通過巧妙地選取測試用例，只要求某些參數的組合情況被包含，能夠在保證測試效率的同時大大縮減測試用例數量。該理論是基于以下事實的，軟件中的錯誤大部分都是由單個參數所導致的，一般最多是由兩個參數相互作用而觸發，三個或三個以上的情況幾乎沒有。如果測試用例集包含了任意t個參數的所有取值組合，那么稱該測試用例集組合強度為t，或者說它是t-way的。圖2-3 不同組合強度下的錯誤發現率圖2

29、-3是NIST報告中總結的幾個應用使用不同組合強度的測試用例集測試后的錯誤發現率曲線17。我們可以看出，隨著組合強度的增加，錯誤發現率顯著增長。以NASA應用為例，67%的錯誤由單個參數觸發，93%由兩個參數相互作用后觸發，98%由三個參數一起造成。其它應用的錯誤發現率曲線也都比較相像，組合強度等于4到6時錯誤發現率都達到了將近100%。特別的，生成2-way的測試用例集的方法被稱為pair-wise（或all-pairs）測試方法。目前pair-wise是使用最普遍的組合測試技術，因為軟件中的絕大部分錯誤都只由一個或兩個參數造成，pair-wise生成的測試用例能夠覆蓋足夠的錯誤空間。使用p

30、air-wise技術后，總測試用例數目從原來的MN下降到了約M * N。至于生成高組合強度的測試用例，測試用例集發現錯誤的能力沒有實質上的提高，卻會導致生成算法的更加復雜化和產生多得多的測試用例。最壞的情況下，當組合強度和參數的數目相等時，組合測試退化為枚舉測試。組合測試的最早提出，也就是為了簡化軟件在各種配置環境下的測試。因為牽涉到硬件環境的搭建，配置參數測試中每增加一種測試情況比單純地多寫一個測試用例所花的代價大得多。人們迫切需要解決這一問題，使得配置參數測試成為了組合測試中最為發達的形式，尤其在那些要求適應不同硬件平臺和環境的軟件的測試過程中?？紤]一款受5個配置因素影響的應用：操作系統（

31、Windows XP、Apple OS X、Red Hat Enterprise Linux），瀏覽器（IE、FireFox），網絡協議（IPv4、IPv6），處理器平臺（Intel、AMD）和數據庫（MySQL、Sybase、Oracle），一共3·2·2·2·3=72種硬件平臺。pair-wise測試只需要設計如下10個測試，就覆蓋了每一種影響因素和另外一種影響因素的所有組合。編號操作系統瀏覽器網絡協議處理器平臺數據庫1XPIEIPv4IntelMySQL2XPFireFoxIPv6AMDSybase3XPIEIPv6IntelOracle4OS X

32、FireFoxIPv4AMDMySQL5OS XIEIPv4IntelSybase6OS XFireFoxIPv4IntelOracle7RHELIEIPv6AMDMySQL8RHELFireFoxIPv4IntelSybase9RHELFireFoxIPv4AMDOracle10OSXFireFoxIPv6AMDOracle表2-2 pair-wise測試的配置即使被測軟件沒有配置選項，軟件仍要處理一些輸入。例如，Word 2010應用程序至少允許用戶對拖黑文字進行10種不同操作：設為上標、設為下標、加粗、加下劃線、設為斜體、加刪除線、加灰色背景、加陰影效果、加倒影效果、加熒光效果。相關的字

33、體處理函數需要根據用戶的輸入來相應修改文字效果，該函數需要在所有的可能情況下都正常工作，而一共有210=1024種可能。前面的經驗告訴我們，3-way的測試用例就能夠達到90%以上的錯誤發現率，具有較高的收益-代價比。圖2-4 3-way覆蓋數組圖2-4列出了對于具有10個變量、每個變量各有兩種取值的3-way覆蓋數組。覆蓋數組并不唯一，這只是其中一種情況。t-way覆蓋數組的特點是，任意t個參數的所有排列組合都將分別出現在覆蓋數組的某一行中，比如上圖中的ABC、DEG、HIJ，三個參數共有8種排列組合（000、001、010、011、100、101、110、111）都被覆蓋數組所覆蓋。覆蓋數

34、組的每一行對應一個測試用例，相比之前的1024個測試用例，組合測試只需要13個測試用例。組合測試用例生成的本質是構造覆蓋數組，最早的構造方法是利用正交數組，其定義和覆蓋數組類似，唯一區別在于正交數組中所有t元組出現的次數相同，而覆蓋數組不保證這一點。在某些特殊的情況下，正交數組就是最優的覆蓋數組，為此，如何構造正交數組問題吸引了大量的研究者研究。Sloane在其網站上總結記錄了超過200個正交數組18。利用計算機也可以自動求解出部分類型的正交數組，由已知的大覆蓋數組構造小覆蓋數組的方法被稱為坍塌19。坍塌的缺陷在于，最終得到的覆蓋數組往往并不是最優解，一般比最優解要大。另一種構造方法剛好相反，

35、是由已知的小覆蓋數組遞歸構造出大覆蓋數組。構造最優覆蓋數組的實際上是一個NP完全問題20，我們知道，NP完全問題是一系列可以互相轉化的問題。于是我們可以利用和借鑒其它NP完全問題的研究成果來構造覆蓋數組，比如第一個被證明為NP完全問題的可滿足性問題，整數規劃問題，圖論問題等等。數學構造方法僅限于某些特定大小或者組合強度的覆蓋數組的構造，不具有通用性。NP完全問題則是困擾了人類多年的超級難題，目前還沒有突破性解法，所以轉化為其它問題也是大同小異。但我們可以利用局部搜索方法，比如啟發式搜索算法，在較短的時間內就可以搜索出近似最優解。啟發式搜索算法是利用一個已有的數組，通過合適的變換得到一個更優的覆

36、蓋矩陣，不斷地變換直到得到一個較優的矩陣。近年來流行的模擬自然界行為的智能優化算法中，目前已經應用到組合測試中的主要有模擬退火、禁忌搜索、遺傳算法等等。更為有效的方法是貪心算法，貪心算法的思想是從空矩陣開始，然后逐行或者逐列地擴展矩陣，直到所有的t元組都被覆蓋。按照擴展方式的不同，又可以分為一維擴展和二維擴展。商業工具AETG最先提出一維擴展的方法21，依次增加一行，每次盡可能多地覆蓋未覆蓋的t元組。微軟開發的工具PICT采用類似AETG的方法生成測試用例22，不同之處在于，PICT每次產生的結果是相同的。Lei等人提出的IPO（In-parameter-order）23方法屬于二維擴展，該算

37、法主要針對pair-wise測試。首先構造前兩個參數的所有組合，形成一個小的矩陣，再分別為矩陣添加一列和必要多的行，覆蓋完所有元組后結束。我們將模仿PICT工具中pair-wise算法的主要思想，使用一維擴展的貪心算法來生成覆蓋數組。同時給系統留好接口，利于以后換用新的pair-wise生成算法，具體的算法設計將在第四章介紹。2.4. MBT預期輸出生成三大關鍵技術就只剩下輔助性內容生成工具了，輔助性工具主要還是為了解決預期輸出的生成問題。前面我們構造了系統的模型，模型描述了系統的狀態和狀態之間的動作，這些動作都是由一個個函數和方法的調用序列組成的。SUT提供的API往往不能和測試用例的要求完

38、全契合，為了讓測試用例能夠順利地在SUT上執行，需要測試人員在SUT之上再包裝一層，即圖2-1中的適配器層。嚴格地說，我們編寫的工具只負責生成基本的測試用例框架，或者稱為抽象的測試用例。測試用例中相當于使用了打樁的設計模式，樁的實際實現由最終的測試人員補充完成，樁的實現包括對SUT提供的API的封裝組合和測試判斷邏輯的編寫。我們把這些樁叫做token，token對應于適配器層中的某個函數和方法，兩者可以直接一一對應，也可以先序列化為可擴展標記語言（XML，Extensible Markup Language）文件再利用XML解析器之類的工具生成測試用例。這樣MBT的整個測試工具都變得項目之間可

39、移植了，如果某一測試條件和預期結果不同則在token中拋出異常，拋出的異常隨后被測試工具捕獲，最終判定該測試用例不通過。圖2-5展示了一個測試工具自動生成的測試用例，用戶需要實現token_1和token_2的具體邏輯，然后測試用例就能夠被真正執行了。token_1和token_2執行過程中如果發現錯誤會觸發異常，程序打印出錯誤提示，同時導致測試用例的總錯誤個數加一。反之，一切正常并給出通過提示。圖2-5 測試用例示例另外我們也可以利用pair-wise來完成部分情況下預期輸出的生成。對于相同輸出結果的某些參數取值組合，把輸出結果也當作pair-wise算法輸入參數的一項，輸出結果列和其它輸入

40、參數的區別在于其取值唯一。PICT工具還支持混合組合強度的測試用例生成，以及輸入各種約束，比如指定某些參數的組合形式必須出現或者不出現，所以具有較強的預期輸出生成能力。不過如果預期輸出涉及復雜的判斷邏輯，還是使用委托給token來處理的方法較好。第三章 系統架構3.3.1. 功能概述及流程課題要求完成的基于模型的自動化測試工具的功能包括：支持輸入FSM模型、支持添加token、支持pair-wise組合測試、支持生成測試用例框架、支持序列化FSM模型到文件和反序列化讀入。其中考慮到token的可復用性，用戶可以直接在工具上定義token順序執行序列組成的函數過程，更復雜的函數過程則通過添加新的

41、token實現。用戶使用該工具生成測試用例的流程如下：圖3-1 生成測試用例流程用戶可以直接繪制FSM模型，或者在以前保存的模型基礎上修改模型，工具支持FSM模型的序列化與反序列化。繪制FSM模型時首先需要定義一些FSM的狀態轉換動作中用到的token和這些token組成的若干函數過程，隨后在模型繪制面板中畫出FSM模型相應的有向圖。FSM模型的有向圖包括代表不同狀態的圓形節點，以及代表狀態間轉換動作的弧線。一個token或函數過程可以在相同的或者不同的狀態轉換動作中被反復使用，只要求這些token或函數過程方法頭中所定義的參數被正確地賦予某個常量或者變量。變量可以有多個允許的取值，用戶在pa

42、ir-wise相關面板輸入各個變量的可能取值，接下來工具將分析FSM模型尋找所以可執行路徑，同時結合路徑長度限制和pair-wise技術來生成測試用例。最后用戶還可以在生成的測試用例中再人工選擇部分測試用例出來，保存為最終需要被執行的測試用例。3.2. 系統架構工具設計的主要目的是為了自動生成測試用例，而模型是驅動MBT各測試過程的根本，所以系統架構中最核心的部分是FSM的數據模型，數據模型描述了FSM中各個狀態和轉換動作的詳細屬性。比如狀態名稱，轉換動作名稱，用戶所定義token的名稱和所需輸入輸出參數，函數過程的名稱和其中包含的token執行序列等等。圖3-2 系統總體架構用戶不是生硬地使

43、用形式化語言來描述FSM數據模型，工具提供了可視化界面，實現了鼠標選取不同繪圖元素再拖拽調整的繪圖方式。此外，為了持久化保存繪制好的FSM模型，系統包含了序列化模塊，用于模型的序列化與反序列化。測試用例的生成過程是基于兩大模塊來完成的，FSM模型遍歷模塊負責生成各種可執行路徑，pair-wise測試模塊負責生成參數變量取值的不同組合。最后把參數變量取值代入可執行路徑中，即得到測試用例。第四章 系統各功能實現4.前一章中我們介紹了系統的整體架構，下面將逐一介紹系統各模塊的具體實現，整個系統都使用C#語言編寫完成。4.1. FSM數據模型實現我們知道FSM數據模型是影響系統的關鍵，圖4-1列出了系

44、統實際實現過程中FSM數據模型相關各類之間的關系。對于一些簡單的set和get方法圖中并沒有標出，其它輔助性的方法也予于省略。圖4-1 FSM數據模型的類圖類FSM中記錄著系統FSM數據模型的所有信息，它里面有兩個鏈表分別記錄FSM的狀態實例和轉換動作實例，同時有兩個Dictionary分別記錄狀態和轉換動作的名稱與實例之間的映射關系。狀態由類State描述，該類的屬性有狀態標識id、狀態類型type和狀態后置動作鏈表nextActions。我們定義了三種狀態類型：Entry、Free和Exit，Entry和Exit分別代表初始狀態和終止狀態，Free代表其他自由狀態。狀態動作由類Action

45、描述，該類的屬性有動作標識id、出發狀態名稱from、目的狀態名稱to以及動作的方法實現鏈表stubs。在尋找可執行的測試路徑過程中，程序從初始狀態開始深度遍歷FSM有向圖，直到到達某個終止狀態或路徑長度達到限制才結束。類Tour的每個實例代表一條被發現的可執行路徑，因為用戶并不參與Tour的命名，所以該類中設置了一個全局靜態的標識計數器域idCounter，每新創建一個新實例時計數器自動加一，必要的時候可以通過ResetIdCounter方法重置計數器。除了以上代表FSM實體組成部分的類，FSM數據模型還必須描述SUT相關部分的信息。抽象類ActionImpl描述了測試中調用的SUT接口，準

46、確地說是測試適配器層中的接口，它的兩個抽象方法GenDefault和GetCopy分別用于初始化和返回克隆實例。類TokenImpl和類FunctionImpl繼承了類ActionImpl，其中類TokenImpl表示的是用戶定義的基本token，而類FunctionImpl表示的這些token順序序列組成的函數過程。考慮到函數過程和轉換動作的相似性，類FunctionImpl中直接包含了一個類Action的實例。最后，注意一下參數和變量的區別：參數指的是函數方法頭中定義的輸入，而變量是在實際調用函數方法時對參數的賦值。我們使用類Parameter來表示參數，而用類Variable來表示對參數

47、的賦值，包括常量和變量。類Variable中包含一個根據其標識名稱name來判斷的方法IsVariable。4.2. 可視化和序列化實現系統的用戶界面部分是利用WinForm技術實現的。雖然WinForm技術中已經提供了許多可以直接使用的組件，但是距離我們的要求還是有一定差距，所以我們自己設計實現了新的組件來完成FSM模型的可視化。圖4-2 FSM模型可視化模塊的類圖接口IRenderable定義了新組件通用的屬性和方法，包括組件的位置信息、繪制組件過程中觸發不同事件的響應函數（Paint、PrePaint、PostPaint和PaintFocus），方法IsSelected則用于判斷該組件是

48、否被鼠標選中。類StateR和TourR直接實現了接口IRenderable，但是類ActionR和類FunctionR實現的則是接口IRenderable的擴展接口IActionRenderable，該接口添加了一個保存轉換動作信息的域。這些類對應于FSM數據模型中的類，繪圖的實際過程由C#語言提供的系統類System.Drawing.Graphics完成，涉及到的API24參見表4-1。方法名稱作用DrawCurve繪制經過一組指定的Point結構的曲線DrawLine繪制一條連接由坐標對指定的兩個點的線條DrawPolygon繪制由一組Point結構定義的多邊形DrawString在指定

49、位置并由指定的Brush和Font對象繪制指定的文本字符串FillEllipse填充邊框所定義橢圓的內部，該邊框由一對坐標、一個寬度和一個高度指定表4-1 類Graphics部分方法圖4-3展示了這幾個類的繪圖效果，類StateR繪制紫色的圓圈代表狀態節點，類ActionR則繪制了兩種代表轉換動作的深綠色弧線。如果出發狀態和目的狀態相同，那么將繪制如action_0的弧線；如果出發狀態和目的狀態不同，則按照事先設計的弧度在兩個狀態節點之間繪制如action_1的弧線，另外增加一個三角形標志表明方向。類FunctionR以灰色粗線加圓點的形式繪制用戶自定義函數過程的標記，默認排列在FSM繪制區域

50、的左上角。類TourR把用戶選中的可執行路徑用黃色重描一遍。圖4-3 自定義UI組件示例C#語言提供了方便的標記功能來支持對象的序列化與反序列化（圖4-4）。首先把準備序列化的對象標記為Serializable，然后根據不同的需要和屬性特點把公共屬性都標記為XmlAttribute、XmlArray或XmlIgnore，公共屬性中的自定義類型也需要在定義文件中添加相應的標記。每個希望被序列化的公共屬性必須提供set和get方法，否則該屬性無法被正確序列化到XML文件中。XmlAttribute表示把該屬性作為對象XML根節點的一個屬性；XmlArray表示該屬性是數組類型的，整個屬性將被添加為

51、根節點的一個子節點，另外每個數組元素又會被序列化為該子節點的一個子節點；XmlIgnore則表示忽略此屬性，該屬性不參與對象的序列化過程。系統類System.Xml.Serialization.XmlSerializer使得編程人員能夠控制如何將對象編碼到XML文件中，并且支持從XML文件中重新創建原始狀態的對象。接下來FSM模型的序列化與反序列化工作只要通過調用類XmlSerializer的兩個簡單方法就可以了。方法Serialize負責把對象的某個實例序列化到某個輸出流中，方法DeSerialize則負責從某個輸入流中反序列化出原始狀態的對象。圖4-4 XML序列化與反序列化示例代碼4.3

52、. 模型遍歷算法實現顯然測試的基本要求之一應該是至少把FSM模型中的每個狀態和每個轉換動作都執行一遍，不過這樣并不能很好地覆蓋被測代碼，而且許多重要的測試場景都會被遺漏。最為全面地測試FSM模型的方法是找出其有向圖中的所有可執行路徑，然后把它們都轉換為測試用例去執行。但是這樣遍歷出來的測試用例數目又往往過于龐大，其中很大一部分還是冗余性測試用例。折衷的辦法是通過路徑長度來限制測試用例的產生，同時用戶構建FSM模型時有意識地把復雜系統拆分為幾個子系統來單獨進行測試，繪制FSM模型時也可以分別指定不同的初始狀態來尋找路徑。對于工具生成的測試用例集，用戶還可以在條件允許的情況下篩選出與SUT使用場景

53、緊密相關的部分測試用例，形成最終的測試用例集。圖4-5 模型遍歷算法核心代碼模型遍歷算法的本質是圖論中的廣度優先搜索（BFS， Breadth-First Search）算法，圖4-5給出了算法的核心代碼。算法初始時中間結果鏈表tours中只有一項包含初始狀態entry的路徑，以后每次迭代都檢查tours里的每個出口狀態的下一轉換動作，試圖增長一個單位的路徑長度。為了不讓搜索得到的路徑包含太多重復回路，如果新擴展的動作已經被原路徑多次包含，該路徑及其擴展路徑都將被拋棄。此外，路徑的末狀態必須為出口狀態，并且沒有后續動作或者指向其自身，路徑還必須滿足設定的長度要求。4.4. pair-wise測

54、試實現此部分的實現主要模仿微軟PICT工具22，運用一維擴展的貪心算法策略逐步得到覆蓋矩陣。算法分為兩個階段：準備階段和生成階段。圖4-6 參數組合示例22準備階段將計算出生成階段所要用到的各種信息，包括需要被覆蓋的不同參數取值組合。假設我們需要對A、B、C三個參數進行pair-wise組合測試，A和B有兩種可能取值，C有三種可能取值。那么它們之間的兩兩組合情況有：AB、AC、BC，具體的取值可能如圖4-6所示，pair-wise測試的最終目的就是全部覆蓋這些取值情況。PICT中把每種取值情況分為三種狀態：已覆蓋、未覆蓋、排除，我們實現的自動化測試工具中不考慮帶有約束的pair-wise測試，

55、所以只有前兩種狀態。每當生成一種新的測試用例時，被新測試用例覆蓋的取值情況狀態會跟隨之改變，算法直到所有取值情況的狀態都為覆蓋時終止。圖4-7 PICT算法偽代碼22原始算法的偽代碼如圖4-7，算法生成新測試用例時優先選取種子組合，即某些測試者認為比較重要，應該優先出現的取值組合。我們不考慮此特性的功能，下面介紹如何完成新測試用例ri的生成。如果ri為空，那么選擇一種剩有最多未覆蓋取值組合的參數組合，比如圖4-6例子中生成第一個測試用例時AB剩有4種取值組合，而AC和BC則各有6種取值組合。當存在多個相同最大剩余取值組合的參數組合時，只選擇第一個參數組合的第一種取值情況，即AC的00情況首先被

56、選用。因為ri中還有未確定取值的參數B，所以繼續while循環到else部分，考慮所有取值情況集合P中包含至少一個未確定取值參數的子集Q，再從Q中篩選出與ri取值一致的取值情況。于是我們篩選出了AB的00、01，BC的00、10。如果在這些篩選出的取值情況中有未覆蓋組合，那么選擇能新覆蓋最多取值組合的一項；如果它們都已覆蓋，那么隨機選擇一項。這里篩選出的4種取值情況都只能新覆蓋1種取值組合，所以使用AB的00，至此我們就生成了第一個測試用例，隨后的測試用例生成都如上述過程。為了方便調試和用戶擴充pair-wise算法，該模塊被設計為獨立的可執行文件。系統調用該模塊時，首先通過配置文件提供的路徑定位，然后利用系統類System.Diagnostics.Process另外啟動一個隱藏命令行窗口的進程運行。對于測試工具來說，這些操作都由類PictFile封裝。用戶自己實現的pair-wise算法只要滿足輸入參數和輸出格式與我們設計的相同，即能夠在配置文件中指定并良好地整合。輸入參數和輸出格式由類PictInputVariable和類PictOutputVariable說明，因為輸出都是包含一組參數的取值情況的，所以類PictOutputVarList內部封裝了一個類PictOutputVariable的鏈表。圖4-