智能服務終端的探索性自適應FSM測試方法

聶鈺格 殷蓓蓓 裴翰宇 李 莉 徐立鑫

1(北京航空航天大學自動化科學與電氣工程學院 北京 100083)

2(東北林業大學信息與計算機工程學院 哈爾濱 150040)

3(計算機軟件新技術國家重點實驗室(南京大學) 南京 210023)

(zy2103520@buaa.edu.cn)

21世紀以來，軟件的作用大幅提升，軟件正逐步重新定義一切，但與此同時諸多軟件問題也隨之而來[1].在對軟件沒有進行規范而有效的測試時就倉促地把軟件交付給客戶，很有可能為軟件的使用埋下隱患.因此，為了保障軟件的質量，對軟件進行規范而有效的測試變得十分重要.然而軟件測試工作極其龐雜，需要消耗較多的人力和物力.隨著現代軟件技術的發展和人們需求水平的提高，軟件系統規模擴大、版本更新頻繁、開發與測試難以對接、邊開發邊測試、在測試中需要不斷考慮軟件的新技術和新特性等因素導致測試工作量龐大且難以規范化，工作難度顯著提升.

傳統的軟件測試自動化程度不高，大多依賴于人工測試，是一項軟件開發過程中耗費最大的、勞動密集型的活動.由于人工測試受制于測試工程師的理論基礎、經驗和創造力，因此測試效率低下、易出錯、測試不完全和測試用例不可再生.為增強測試系統化和規范化程度，提高軟件測試效率，降低測試費用，測試自動化已成為一種必然的趨勢.隨著自動化測試的興起，工業界、學術界紛紛開發起自己的自動化測試工具.現有的測試工具雖然著重點各有不同，一般都存在3方面的問題：

1) 目前主流的自動化測試工具主要有以Selenium，Robot Framework等為代表的用于Web應用程序的功能測試的工具和框架，有以Appium為代表的用于移動應用程序測試的工具，有以SoapUI等為代表的專注于接口測試的工具，有以JMeter，Loadrunner，Monkey等為代表的專注于性能測試的工具，還有像IBM Rational Test Manager這樣用于計劃、組織、執行、管理和報告所有測試活動的測試活動管理工具.它們一般情況下只能部分支持某些過程的自動化，例如有的工具只支持測試用例的自動生成，有的只支持測試用例的執行，有的支持自動化比對測試結果，很少有支持從建模到測試用例生成到執行結果比對全程自動化的工具.目前，前期的建模工作主要由人工完成，測試工具的自動化程度不高.

2) 從測試場景的角度來說，許多現實的測試場景是規格說明不充分的黑盒測試，而且軟件的迭代需要不斷進行回歸測試，因此保證建模的準確性和測試用例的充分性十分重要.

3) 測試工具主要是針對Web應用系統或移動應用軟件的特性所設計的，需要通過改進更好地服務于日常生活中無處不見且未來一定會更為普及的智能服務終端系統的測試[2].

由于測試用例的生成依賴于被測試對象的性質和測試人員的經驗，具有較大的主觀性，即從何種角度出發、以何種模型來設計具有很大的不確定性，因此可以發現目前市場上缺乏普遍適用且簡單實用的建模和測試用例生成的自動化工具.

在軟件測試過程中，測試設計者可以使用各種各樣的建模方式來指定測試模型.基于模型的測試 (model based testing, MBT) 就是一種很有前景的黑盒測試方法，MBT是指由軟件的行為模型產生測試用例，再測試實際的軟件實現是否與模型一致.模型描述了軟件“做什么”，而不是“怎么做”，因此由模型導出測試用例時不必考慮程序的具體實現[3].

軟件系統的模型通常被定義為狀態及狀態間的遷移，有限狀態機就是描述這種結構最自然的模型[4]，因此主要被用來進行測試用例的生成及優化.有限狀態機是表示有限個狀態以及在這些狀態之間的轉移和動作等行為的數學模型，它主要是由一系列狀態和輸入事件組成.在計算機科學中，有限狀態機被廣泛用于建模應用行為、硬件電路系統設計、軟件工程、編譯器、網絡協議、計算語言的研究[3].隨著基于狀態機的應用和開發越來越廣泛，對狀態機的測試也越來越受到業界的重視.

過去幾十年，以有限狀態機(finite state machine, FSM)模型為代表的一些基于模型的測試生成方法和測試準則已被相繼提出.例如DS方法[5]、W方法[6]、UIO方法[7]、狀態覆蓋準則[8]、遷移覆蓋準則[9]和獨立遷移覆蓋[9]等.然而，由于測試意圖的不同，上述這些測試生成方法和測試準則都具有一定的局限性，并不能解決所有的問題.例如，雖然W方法具有很強的錯誤探測能力，但該方法生成的測試序列包含大量的冗余，導致測試成本的急劇增加.面對不同的測試場景，應當比較其特點，選擇較為合適的方案來進行測試[10].本文在已有軟件測試方法的基礎上，提出一種基于FSM的探索性自適應測試方法，該方法針對當前軟件特點，主要解決缺乏充分明確規格說明的黑盒測試和需要不斷進行回歸測試的測試問題.

隨著社會的發展，傳統的售貨方式已經滿足不了人們的需求，近幾年我們可以發現，在中國的街頭以及各行各業也出現了智能服務終端的爆發式增長.當然，智能服務終端指的不僅僅是自動售貨機，它也包含了一切能夠為人們提供專門服務的自助設備.當今時代，物聯網、人工智能等無人化技術日趨成熟，隨著現代社會的高速發展及人們生活水平的提高， 飲料、零食、生活用品等自動售貨機，電影票、地鐵票、高鐵、飛機票等自動售票機，集掛號、繳費、查詢等于一體的醫療系統自助服務終端，銀行的ATM機，校園里的校園卡辦理和繳費機，行政部門里的政務查詢機……各式各樣的智能服務終端設備逐漸成為市民日常生活中不可缺少的部分.這些設備的廣泛使用也帶來了新的問題，即要加強對智能服務終端系統的測試，預防和降低其錯誤的出現，提高用戶體驗.

智能服務終端普遍是通過圖形用戶界面(GUI)即采用圖形方式顯示計算機操作界面的[11]，在圖形用戶界面，用戶看到和操作的都是圖形對象，相同的操作總是以同樣的方式來完成，這就意味著智能服務終端擁有狀態及狀態遷移特征清晰明確且數量有限的特點.智能服務終端為了滿足人們不斷變化的需求，需要頻繁地迭代，它的規格說明往往不夠充分和規范.因此基于FSM的探索性自適應測試方法可以有效地應用于智能服務終端測試，該方法在規格說明不詳或缺乏，以及軟件快速迭代需要不斷回歸測試情況下仍能高效可行.

本文的主要貢獻有3個方面:

1) 針對現有的智能服務終端特點，基于有限狀態機測試的理論與方法，提出了一種探索性自適應的建模和測試用例生成方法，為系統規格說明未知或不充分場景下的黑盒測試提供了新思路，特別是為智能服務終端系統持續迭代、不斷更新升級的場景下的回歸測試提供了高效的方法， 避免了重新生成并執行全部測試用例，減少回歸測試的開銷.

2) 本文搭建了一個支持基于FSM的探索性自適應測試的服務平臺，核心功能為建模和生成測試用例套件.對10種不同的主流智能服務終端進行了實踐研究，驗證了本文方法的有效性.

3) 將本文方法與傳統FSM測試方法、狀態轉換測試方法等進行了比較，并總結了目前智能服務終端普遍的缺陷和問題.

1 探索性自適應FSM測試

有限狀態機又稱為有限狀態自動機或簡稱為狀態機，是表示有限個狀態以及在這些狀態之間的遷移和動作等行為的數學模型.在實際應用中，人們常常應用確定性有限狀態機(deterministic finite state machine, DFSM)描述軟件系統的行為，因此本文所指的FSM是特指確定性有限狀態機.對于一個給定的屬于有限狀態機的狀態和一個屬于該自動機字母表內的字符，它都能根據事先給定的遷移函數轉移到下一個確定的狀態.

定義1.FSM定義.一個FSM可以用六元組〈S，S0，I，O，δ，λ〉表示.其中，S為狀態的有限集合，S0∈S為初始狀態;I為輸入的有限集合;O為輸出的有限集合;δ:S×I→S為狀態轉移函數;λ:S×I→O為輸出函數.即當FSM在狀態s∈S上收到輸入x∈I后，它會轉移到狀態δ(s，x)，并產生輸出λ(s，x)[12].

用ε∈I，ε∈O分別代表空輸入和空輸出.對于空輸入FSM會留在原來的狀態且產生空輸出，即?s∈S，δ(s，ε)=s，λ(s，ε)=ε.

狀態轉移函數和輸出函數可以用一種自然的方式從單個輸入擴展到1個輸入序列上.即δ(s，x·v)=δ(δ(s，x)，v)，給出輸入序列最后到達的狀態;λ(s，x·v)=λ(s，x)·λ(δ(s，x)，v)，給出輸入序列產生的每個輸出.其中“·”表示2個序列的連接.

用狀態轉換圖(state transition diagram)可以更直觀地表示FSM.狀態轉換圖是一個有向圖，節點代表狀態，邊代表遷移，每條邊上都標記有該遷移對應的輸入和輸出，用符號“/”分隔.如圖1所示:

Fig. 1 State transition diagram of FSM圖1 FSM的狀態轉換圖

下面解釋探索性自適應FSM測試方法中包含的測試理念，并以遞進的方式逐步刻畫該測試方法的概率.

1) 狀態轉換測試.根據測試對象的規格說明，可以將測試對象抽象為一個狀態轉換圖，根據狀態轉換圖設計測試用例系統檢測狀態轉換過程中可能存在的問題.測試的有效程度取決于狀態轉換圖是否正確反映了測試對象的規格說明.

設計測試用例執行狀態圖中的轉換，1條測試用例可以執行多個轉換，對于每條測試用例要指定:軟件的起始狀態、軟件的輸入、預期輸出和預期的最終狀態.對于該測試用例執行的每個轉換要指定以下信息:起點狀態、觸發狀態轉換的事件、預期的狀態轉換發生時的動作和預期的下一個狀態.測試用例可以用來測試軟件中有效的轉換，也可以測試那些無法推測的轉換.

對于狀態轉換測試同樣可以定義測試強度和完成準則:①每個狀態至少執行1次；②每個狀態轉換至少執行1次；③所有不符合規格說明的狀態轉換都已檢查.

對于一些要求比較高的應用程序，可能還需要聲明3個狀態轉換測試準則：①所有的狀態和輸入的組合；②所有狀態轉換的組合；③所有狀態的任意順序的所有轉換，也可以重復連續.

2) 探索性測試(exploratory testing).它是一種把對系統的探索和對系統的測試緊密地結合起來的測試方法.在系統規格未知或不充分的情況下，可以通過探索性測試獲取到被測對象的各種信息.這種測試方法強調測試人員個人的自由和責任，可以充分發揮他們的創造性和積極性.同時，它還強調測試設計和測試執行的同時性，這種同時性是相對于傳統軟件測試過程中“先設計，后執行”來說的，它把測試過程看成是一種與測試相關的學習，一種測試設計、測試執行和測試結果的解釋同時進行且相互促進的活動，在整個測試項目中，這些活動可以在并行進行的過程中不斷優化[13].

3) 自適應測試(adaptive testing).它是一種與探索性測試有異曲同工之處的測試方法，也被稱為軟件測試的控制論方法，是以反饋和優化為核心的軟件測試方法.自適應測試可以利用測試過程中的歷史信息指導未來的測試步驟(如測試用例的選擇)，估計被測對象的性質和參數，根據這些參數更有針對性地選擇測試用例，實現給定目標下的最優測試.運用自適應測試應當根據測試過程中收集到的測試數據以及人們對待測試軟件的理解進行在線調整，與路徑測試、功能測試等傳統方法不同的是：自適應測試具有明確的優化目標，在測試過程中不斷根據先驗知識進行目標優化，而傳統方法一般都不具備動態優化功能[13].

Fig. 2 Framework of exploratory adaptive testing based on FSM圖2 探索性自適應FSM測試框架

4) 探索性自適應測試.它是將探索性測試和自適應測試相結合的一種測試方法，適用于在系統缺乏規格說明或規格說明不明確的場景，且削減了回歸測試的開銷.首先，在測試模型Mt為空的時候，我們對系統按照相應的測試策略進行探索性測試，將測試信息存入測試歷史數據庫中，并通過測試歷史信息生成初步的系統模型.其次，不斷地用生成的模型Mt和測試歷史信息迭代生成新的測試用例At，測試執行后將結果Zt輸入到測試歷史數據庫中，使系統模型與真實的系統無限接近并使測試滿足相應的測試準則. 在本文中我們將測試模型定為有限狀態機模型，如圖2所示. 具體的測試流程如圖3所示.首先由測試人員在待測系統上進行探索性測試，獲取到系統的初步信息，根據這個信息對系統初步建模；然后通過模型自動生成測試用例，用新生成的測試用例再對系統實施測試，獲取到系統的bug和模型的bug，一旦找到模型的bug就改進模型生成新的測試用例再測試，重復這一過程直到模型與系統幾乎完全一致. 該過程體現了軟件控制論中的“反饋” “優化”“控制”.

Fig. 3 Flow chart of exploratory adaptive test圖3 探索性自適應測試流程圖

5) 探索性自適應FSM測試.在傳統的基于FSM的測試中，假定待測系統的規格(specification)與實現(implementation under test, IUT)都可以建模為FSM，且IUT是一個黑盒，其狀態無法直接觀察.因此要測試實現與規格是否一致，就需要從規格FSM中導出測試序列，輸入到待測實現FSM中，觀察實際的輸出序列是否與預期一致，其過程如圖4所示.如果一個序列保證能夠檢測出所有給定種類的錯誤，就將其稱為檢查序列(checking sequence).基于FSM的測試就是要構造這樣的序列.

Fig. 4 Process of FSM-based testing圖4 基于FSM的測試過程

現代軟件系統多使用圖形用戶界面(GUI)，尤其是目前市面上的智能服務終端系統，其擁有狀態及狀態遷移特征明顯且數量有限的特點，因此可以為之建立六元組〈S，S0，I，O，δ，λ〉清晰明確的有限狀態機模型，不需要構造檢查序列.能夠構造出清晰明確的六元組的有限狀態機模型可以與狀態轉換圖相結合，為探索性自適應測試提供模型支撐.

2 本文方法及實例分析

我們研究了當前現實生活中常用的10多種智能服務終端，根據有限狀態機的六元組〈S，S0，I，O，δ，λ〉建立模型，依據該模型的元素特性，提出了一種針對智能服務終端的無環狀態及狀態遷移覆蓋測試算法(算法1) ，這里的無環指的是無內部循環.由該方法生成的測試用例數量少，測試充分性程度高.

算法1.智能服務終端無環狀態及狀態遷移覆蓋測試用例生成.

輸入：〈S，S0，I，O，δ，λ〉；

輸出：無環路徑集TS.

① 根據智能服務終端FSM模型〈S，S0，I，O，δ，λ〉構造初始狀態為S1的狀態遷移圖G;/*廣度優先遍歷算法*/

②TS←?;

③ESvisited←?;/*已被訪問過的邊集合*/

④Q←Queue();/*狀態節點隊列(當前節點，到當前節點的路徑)*/

⑤Nfirst←S1;/*初始狀態節點*/

⑥Pfirst←createPathTo(S1);/*到初始狀態的路徑*/

⑦Q.enQueue(Nfirst,Pfirst);

⑧ whileQ.isNotEmpty() do

⑨N,P←Q.deQueue();

⑩ ifG.getAdjacency(N).isEmpty() then

/*擴展路徑達到新的狀態節點*/

/*記錄被覆蓋到的狀態遷移*/

/*新的路徑進入隊列*/

展將出現環，終止*/

算法1所描述的過程是：將隊列中的每一個元素定義為當前節點和到當前節點的路徑.首先，根據構建的模型信息，將初始狀態節點和到該節點的路徑(此時到初始狀態節點無路徑，即該路徑信息中僅有S1)入隊，即初始化隊列信息.然后，判斷隊列是否為空，如果非空，則進入循環體.將隊列中第1個元素分別賦給節點和路徑變量.接著開始判斷該節點是否存在鄰節點.如果不存在即該無環路徑已經遍歷到最后一個節點，則將這一整條路徑存入結果集中；如果存在鄰節點即該路徑并未遍歷完，則判斷它的下一條邊是否已經被訪問過，若未被訪問過，則將這條邊和它所連接的節點接到之前的路徑后，更新原來的路徑記錄，并將這條邊標記為已被訪問過.這樣的好處在于當有多個可達下一鄰節點的邊時，會優先選擇未被訪問過的邊，盡量避免重復測試已經測試過的狀態遷移.若所有到下一鄰節點的邊均已被訪問過，則表明該路徑再擴展將出現環，此時將該路徑存入結果集并終止循環.

以下以最具代表性的智能服務終端為例，選擇地鐵站中的1臺型號為富士FVM-CP33P12-NFSQ-3的自助飲料售貨機為測試設備，介紹如何在有限狀態機的理論基礎上，利用算法1的無環狀態及狀態遷移覆蓋測試用例生成方法對智能服務終端進行探索性自適應測試.

2.1 探索性測試過程

自助飲料售貨機的詳細規格說明難以獲得，因此對該設備建立準確的模型尤為困難.本文通過探索性測試的方式獲取將該設備建模為FSM模型所必須的六元組中的各項元素.

首先，觀察自助飲料售貨機，可知它所售飲料價格均為3元或5元，且只接受1元硬幣、5元或10元紙幣，除現金支付外，還可以使用微信、支付寶、銀聯支付.此售貨機的小屏幕在無人使用時可投放廣告，使用時可提供即時的信息反饋，達到友好的交互體驗.

其次，探索性地點擊該設備系統中的每一個功能按鍵，并記錄每一次操作所涉及到的初始狀態、輸入狀態、輸出狀態、遷移后狀態，如表1所示.在探索性測試時，應注意盡量涉及到每一個狀態的邊際輸入，例如狀態在輸入為“超時”的情況下的輸出是什么.

2.2 建立模型

根據此售貨機的使用流程，建立了FSM模型，如圖5所示.圖5中，圓圈代表一個狀態，一條有向線段表示一個狀態轉移，線段上的符號“/”前面的文字表示輸入、后面的文字表示輸出，一條有向線段從初始狀態通過輸入指向其轉移后狀態并產生輸出.將S1設置為起始狀態(start element).圖5中的所有因素能夠分別對應有限狀態機模型的六元組〈S，S0，I，O，δ，λ〉.

Table 1 Vending Machine Status and Status Migration Mable表1 自動售貨機的狀態及狀態遷移表

2.3 自適應測試

根據所建立的模型，應用算法1生成了如下14條測試用例:

1)S1→選擇商品/售空→S1；

2)S1→選擇商品/等待選擇支付方式→S2→銀聯/二維碼→S6→錯誤app掃碼/錯誤→S2；

3)S1→選擇商品/等待選擇支付方式→S2→支付寶/二維碼→S4→錯誤app掃碼/錯誤→S2；

4)S1→選擇商品/等待選擇支付方式→S2→支付寶/二維碼→S4→掃碼/掃碼成功→S7；

5)S1→選擇商品/等待選擇支付方式→S2→現金/價格→S3→超時/取消購買→S1；

6)S1→選擇商品/等待選擇支付方式→S2→微信/二維碼→S5→掃碼/掃碼成功→S7→購買成功/成功→S1；

7)S1→選擇商品/等待選擇支付方式→S2→現金/價格→S3→非規定金額/退回現金→S2；

8)S1→選擇商品/等待選擇支付方式→S2→銀聯/二維碼→S6→掃碼/掃碼成功→S7；

9)S1→選擇商品/等待選擇支付方式→S2→現金/價格→S3→大于規定金額/找零不足退回現金→S2；

10)S1→選擇商品/等待選擇支付方式→S2→現金/價格→S3→小于/退回現金→S1；

11)S1→選擇商品/等待選擇支付方式→S2→現金/價格→S3→=/出貨→S1；

12)S1→選擇商品/等待選擇支付方式→S2→微信/二維碼→S5→錯誤app掃碼/錯誤→S2；

13)S1→選擇商品/等待選擇支付方式→S2→微信/二維碼→S5→掃碼/掃碼成功→S7→取消購買/取消成功→S1；

14)S1→選擇商品/等待選擇支付方式→S2→現金/價格→S3→>應付價格且為規定金額/出貨+找零→S1.

Fig. 5 Diagram1 of vending machine status transition圖5 自動售貨機狀態轉換圖1

根據以上14條測試用例對該售貨機進行測試，在測試過程中需記錄每一條用例的測試結果并觀察是否存在其他輸入方式，主要彌補在探索性測試的時候產生的疏漏.記錄的測試結果包括2種性質:一種是測試過程中測出系統真實存在的bug;另一種則是由于上一輪建模不準確而遺漏或錯誤的一些狀態和狀態遷移，下文稱之為“建模bug”.在測試過程中，遇到bug時，記錄bug即可；一旦碰到建模bug，應立即停止這一輪的測試，對模型進行相應的修改，并重新生成新的測試套件(去除了已測試過且沒有問題的測試用例)進行新一輪測試.當不再發現新的建模bug時，可以視為模型與實際設備規格一致.

經過不斷地自適應測試后，整理所有記錄的測試結果反饋可以發現存在的建模bug有：

1) 微信和支付寶的二維碼是相同的，所以它們的二維碼通用，而銀聯的二維碼是不同于微信與支付寶的，如果用微信和支付寶掃描銀聯的二維碼則會提示用戶選擇正確的應用進行支付，可以將S4，S5狀態合并為一個狀態.

2) 在選擇好支付方式之后即在狀態S3,S4,S5,S6時還可以直接點擊返回上一級S2，在S3,S4,S5狀態時也會因超時而返回首頁.在S2狀態時可以直接點擊返回首頁或因超時返回首頁.

存在系統bug有：

1) 當售貨機找零不足時，如果用戶選擇了一款超出其剩余找零范圍的飲品，售貨機并不會自動吐出紙幣，而需要用戶按下退幣手柄才會將紙幣退出.若用戶沒有按下退幣手柄，而選了另外一種價格較高的飲料時，則會購買成功并退出多余的硬幣.

2) 并不是每一種狀態都有對應的輸出反饋給用戶，沒有足夠的輸出會導致用戶不知道在當前狀態下可以做哪些操作，降低用戶體驗.

Fig. 6 Diagram2 of vending machine status transition圖6 自動售貨機狀態轉換圖2

模型最終將會被調整成如圖6所示.根據此模型重新生成測試用例套件，通過測試用例文本比對(對于狀態的比對是通過狀態的名稱比對的，而非通過狀態代號，例如狀態轉換圖1中的S6和狀態轉換圖2中的S7雖然代號不同，但表示的都是等待用戶確認購買狀態，在比對時將它們視為同一狀態)，將已經測試過且沒有問題的用例排除后，產生最后一輪測試的測試套件.除第1輪過程為探索性測試―建模―生成測試用例―測試外，之后不斷重復測試―改模―生成測試用例―測試的過程，這一部分不斷重復的過程即為自適應測試.每一輪記錄好測試出的bug，并根據測試出的建模bug不斷完善所建模型，使之達到與被測系統一致.

3 實驗設計及結果

為了進一步驗證本文所提方法的應用價值，以及深入發現智能服務終端存在的問題，我們提出了3個研究問題，設計了一組實驗，進行了系統的實證研究和總結.

3.1 研究問題

我們主要關注本文提出的測試方法所需要的測試用例規模、測試用例集的測試覆蓋率和故障檢測能力等問題，因此，我們的研究問題有3個:

研究問題1.通過探索性自適應測試方法所建的模型能否覆蓋智能服務終端系統的所有功能，并且能夠與之相吻合，實現高效的FSM測試.

研究問題2.通過無環狀態及狀態遷移覆蓋算法所生成的測試用例，是否能覆蓋被測系統所有的狀態和遷移，實現高效的狀態轉換測試.

研究問題3.本文提出的這套測試方法是否能夠發現一些問題，找到一些漏洞.

3.2 實驗對象

我們選擇表2中的10種智能服務終端，這些服務終端分別來自校園、醫院、地鐵、高鐵、超市和電影院等各種公共場所，本文選擇了這些代表性智能服務終端之后，先進行探索性測試，然后建模，通過算法1生成測試用例后按照測試用例表逐一進行測試再進行不斷自適應測試.

3.3 基于GraphWalker的工具設計與實現

GraphWalker[14]是一個GitHub上基于測試模型的用例生成開源工具.它主要應用于FSM,EFSM模型，可以用來以有向圖的形式讀取FSM圖形模型、EFSM圖形模型、json模型，并根據這些圖生成測試用例路徑.GraphWalker提供了一個稱為Studio的編輯器，可以在其中創建和編輯模型，并且Studio可以做的不僅僅是編輯.在該工具中，可以通過運行測試路徑生成來驗證模型，以便用戶可以驗證模型的正確性.由于GraphWalker僅提供隨機生成測試用例的功能，因此需要將本文所使用的算法植入進去，對其進行擴展.

GraphWalker提供3種工作方式：1)作為第三方庫，可被Java測試程序直接調用；2)作為可執行程序，以offline模式加載模型，直接運行；3)作為可執行程序，以online模式提供服務.使用GraphWalker輔助建模的主要操作是在Graph-Walker的編輯器視圖區域，按住鍵盤鍵V的同時單機鼠標左鍵可以創建一個頂點，按住鍵盤鍵E的同時將鼠標從第1個頂點拖到第2個頂點并釋放，可以創建一條邊.

本文將把GraphWalker的studio編輯器作為可執行程序，以online模式嵌入，用于實現建模的主要功能，并對生成路徑的算法進行重新定義和描述，以此來生成用戶所需的測試用例.

3.4 實驗結果

實驗結果基本與我們所寫測試用例預期一致，這10種服務終端大體上都能達到完成其目標功能的要求，但在一些細節上還沒有考慮周全，一定程度上會影響用戶的使用體驗，給用戶帶來麻煩.另外，一些機器出現了較為明顯的大問題，這也反映出多數機器還是停留在完成功能階段，沒有考慮到各種問題發生后的補救措施.

對于研究問題1，實驗表明我們對智能服務終端所建模型是準確的，完全覆蓋了機器的所有功能，并且能夠與之相吻合，從表2第3列和第4列中可以看到，用少量的測試用例實現高效的FSM測試.

對于研究問題2，根據模型所寫出的測試用例能達到100%的路徑覆蓋率、功能覆蓋率和k-切換覆蓋率，從而實現高效的狀態轉移測試，具體見表2第5～7列.

對于研究問題3，本文提出的這套測試方法在測試每一種設備都發現了一些問題，并將所有問題分為十大類.問題數量見表2中最后一列，具體發現的問題內容如表3所示.

Table 2 Experimental Object and Testing Results表2 實驗對象及測試結果

Table 3 Founded Problems List表3 發現問題列表

續表3

3.5 關于智能服務終端的實驗總結與建議

通過這10個實驗我們可以發現，目前國內常用的幾款智能服務終端是非常有針對性的，十分的功能化，通常是為了某一單一功能或領域而服務的，且提供的服務具有普遍性、大眾性.一般是在首頁顯示所有的大功能分類，然后通過與用戶的互動逐層細分，幫助用戶完成操作.在任意過程中，用戶中斷操作離開，大多數機器會設置超時限制，自動回到首頁，也有極少數機器忽略了這一設置.另外，我們發現近30%的機器各個功能之間、上下級之間有缺少切換聯系、切換不合理、聯系不緊密的問題.例如，當用戶好不容易選好了車票的各個選項進入支付頁面時，又想回去修改部分內容，當點擊返回鍵，機器返回的不是上一級而是首頁，諸如此類問題會給用戶帶來很大的麻煩，甚至造成一些操作失誤從而帶來不必要的損失.

對于銷售類的智能服務終端，我們發現現金支付是支付方式中最容易造成錯誤的支付方式，機器不僅需要識別現金面額是否符合設定的面額，還需判斷現金數量是小于、等于還是大于應付金額，除此之外，機器中剩余的找零也應在考慮范圍內.我們在測試地鐵售票機時，就出現了當我們所支付金額小于應付金額時機器本應將現金全部退還卻少退了1元的情況.有些機器直接禁止了現金購買方式，這確實在一定程度上降低了機器錯誤的概率.一般使用二維碼支付時，若發生錯誤基本上是由于網絡問題，機器也應該提供一些相應的反饋方式和止損辦法.相信在未來紙幣的使用會越來越少，甚至消失，那時更多要考慮的就是網絡支付的問題應對了.另一方面，當所售貨物售空時，部分機器會禁止用戶對此商品的購買，但有些機器只是顯示售空并未限制用戶對此商品的購買，且多數機器缺乏一定的調整機制，或是反饋不及時.關于購買商品的數量問題，我們發現很少有機器可以選擇購買商品的數量，建議其增加一個狀態讓用戶不用重復同樣的購買操作，提高用戶體驗.另外，在提高自助服務終端與用戶交互的角度，我們也建議該類機器可以提供一些商品的基本信息，如生產日期，供用戶參考.

對于涉及卡類的智能服務終端，例如自助校園卡服務終端、ATM機、自助醫療服務終端等，當對卡的依賴過大時，就會在使用時造成一定的不便.例如，在使用自助校園卡服務終端時必須一直將校園卡貼在機器上，在使用ATM機時經常莫名其妙地退卡而重新插卡.建議此類的自助服務終端能夠逐漸向填卡號、驗證碼或者直接掃描二維碼的方式靠攏，實現無卡化.

我們認為智能服務終端首先應盡量做到步驟模塊化、簡單化，使用戶在操作時能夠十分清晰地認知到每一個步驟的功能，能夠輕松地掌握和理解機器的操作；其次應盡量做到用戶友好化、各界面聯系合理化，使用戶在使用時有良好的體驗；最后也是最重要的，智能服務終端要有一定容錯性、錯誤反饋能力和錯誤補救措施，要充分考慮到會出現的各種錯誤，提前設置好相應的反應機制，以保障用戶的利益為首要提前.

4 相關工作及比較

4.1 關于FSM的相關工作及比較

基于有限狀態機的測試生成研究始于1956年Moore對自動機的研究[15].20世紀60年代，Hennine[5]提出了區分序列(distinguishing sequence, DS)方法，用一條輸入序列來區分出所有的狀態，以檢驗狀態機的正確性.但該方法并不適用于所有的狀態機，因為區分序列未必存在. 20世紀70年代，Chow[6]對DS方法進行了擴展，使用一個集合代替了區分序列來辨識狀態，這種方法被稱為“W方法”.

后來有人提出，對不同的狀態可以使用不同的序列來進行測試，這樣可以縮短所需的序列長度，這就是唯一輸入/輸出(unique input/output, UIO)方法[7]，UIO方法是通過UIOS(unique input/output sequence)即在某一狀態下能產生與其他所有狀態都不同的輸出的輸入序列來識別是否達到預期狀態的.UIO不僅比DS更短，而且存在的概率也更高，因此這種方法得到了廣泛的應用.但后來Chan等人[16]發現，這種方法存在漏洞，不能保證發現應用中的所有錯誤.因此他們在UIO方法的基礎上，又提出了一種改進的添加驗證程序的UIO方法(UIO approach with the addition of a verification procedure, UIOv)方法，保證其能產生出正確的檢測序列.

針對W方法，許多人嘗試對其改進，最后形成了一種Wp方法.相較W方法，它借鑒了UIO方法的思想，使用不同的集合去區分狀態，因而可以減少產生的測試用例長度[17].另外一種基于部分W方法(partial W-method, Wp)方法的改進方法是R-Wp方法[18]，該方法使用狀態覆蓋集、遷移覆蓋集和特征集來實現算法，減少了Wp方法中的錯誤轉換，從而優化了用例.Cutigi[19]結合了多種測試用例生成算法，提出了一種減少測試用例并且提高測試覆蓋率的方法.此外在實際測試中，另一種經常使用的基于狀態機的測試序列生成算法是T方法[20]，該方法通過隨機產生一系列測試輸入，這些測試輸入組成測試用例，在測試實現下，以遍歷了狀態機的所有狀態和遷移為止，如圖7所示：

Fig. 7 The evolution of FSM圖7 FSM方法變遷

最近幾年有關狀態機測試的研究不局限于狀態機本身的方法研究，而是更多利用狀態機特點模擬現實的研究對象，結合對象和模擬的狀態機模型的特點進行相應的測試.Petrenko等人[21]利用狀態機模型測試非確定系統的自適應性；Endo等人[22]利用狀態機模型對測試用例的特征和有效性進行測試；Ermakov等人[23]利用狀態機模型測試錯誤的軟件組件，提出到達癥狀的路徑中高概率出現的轉換即高概率錯誤轉換的方法，該方法較簡單卻不嚴謹，但對實際測試有一定的幫助.Pinheiro[24]利用狀態機測試用例生成方法應用于衛星的通信軟件測試中，取得很好的效果.2009年10月17～20日，在微軟亞洲研究院主辦的可驗證軟件工作組大會上，Wolfram Schulte博士介紹了微軟公司最新的基于FSM的測試工具Spec Explorer和Spec#.國內的有關狀態機測試方面的研究也逐漸多元化，包括模型健壯性測試、抽象狀態機測試以及其他一些狀態機模型描述的系統的測試研究[25-26].

W方法、UIO方法等諸多方法雖然在用法上有些許差別，但無一例外都是幫助我們在無法直觀地檢測到遷移后狀態的情況下，判斷遷移后狀態是否與我們所期盼和預測的狀態一致.而就目前常用的幾款自助服務終端而言，遷移后狀態是明確的、可觀測的，每一種狀態都有一種獨立的輸出與之一一對應，所以不需要構造檢測序列對遷移后狀態進行特定的識別.

4.2 自適應測試方法的優越性

一般傳統的測試方法首先根據待測試系統模型設計一組滿足要求的測試用例；然后執行測試用例，根據測試結果分析，定位修改故障；最后補充回歸測試用例，或者調整模型，重新生成測試用例.

自適應測試在發現問題的第一時間，就著手處理問題，調整測試用例生成策略.僅以調整模型為例，可以粗略估計一下自適應測試的測試成本.

假設測試原來的模型M需要m條測試用例，在測試到第i條測試用例(1

可見，自適應測試方法更加靈活，且能夠通過不斷迭代以較少的代價較好地解決需求規格缺乏或不詳的問題.

4.3 關于其他覆蓋準則的相關工作及比較

針對智能服務終端的特征——功能相互獨立、狀態及狀態遷移清晰明確，功能覆蓋、狀態轉換覆蓋、遷移覆蓋及獨立遷移覆蓋都是能夠衡量其覆蓋率的覆蓋準則.

功能覆蓋是描述軟件實際實現的功能與軟件需要實現的功能之間的關系，該覆蓋準則的覆蓋率越高意味著軟件對功能需求實現得越到位，但功能覆蓋的粒度過高，未考慮到2個狀態之間的關系和狀態遷移上的問題，難以很好地反映狀態切換中的問題.

狀態轉換覆蓋率(0-切換覆蓋率)是描述每2個狀態之間轉換的關系.它考慮狀態之間的轉換是否順暢、可行，是一種局部的測試，當覆蓋率達到100%時表示所有的狀態轉換都被測試到了.本文的覆蓋準則包含了的狀態轉換覆蓋，并在單純的狀態轉換覆蓋基礎上進行了拓展.

遷移覆蓋指的是由FSM模型所生成的包含了所有狀態遷移的序列的覆蓋準則.獨立遷移覆蓋是在遷移覆蓋的基礎上加上了測試用例集合中任意2個遷移序列都沒有相同遷移，且任意1條遷移序列本身沒有冗余遷移的約束.遷移覆蓋準則與狀態轉換覆蓋準則一樣，都被本文的覆蓋準則包含在內，而獨立遷移覆蓋準則實際上難以實現.

總的來說，本文所用的狀態及狀態遷移覆蓋不僅兼顧了功能覆蓋、狀態轉換覆蓋、遷移覆蓋，而且在一定程度上彌補了這些準則的不充分之處，測試用例少，測試充分性程度高.

4.4 智能服務終端的其他測試方法

對智能服務終端的測試分為對硬件的測試和對軟件的測試，在開發過程中對軟件系統的測試包含了函數的接口測試、模塊的集成測試、整機的聯調測試[27].但是這樣的測試避免不了由于開發人員對需求理解的偏差等情況而導致的軟件系統缺陷.

智能服務終端系統是由各種功能模塊組成的，從測試或維修人員的角度通常使用功能測試.但是由于智能服務終端可以實現的功能以及內部模塊較多、輸入空間較大，測試用例的可靠性和科學性、測試的充分性難以保證，測試人員難以系統地進行測試，一些邊界情況也很容易被忽略.

本文提出的測試方法能夠對已有方法的有效補充，可以克服上述測試過程中的一些不足，實現充分有效的測試.

5 結論及未來工作

人們對有限狀態機理論的研究和應用已經有近60年的歷史，真正要把這些成熟的理論成果應用起來，在現實生活中發揮作用，還需要做一些轉化和創新，并不能直接照搬硬套.受限于規格不明確等各種現實因素，難以對智能服務終端精準建模，但通過探索性測試和自適應測試的不斷調整，可以很好地將有限狀態機的測試理論和方法應用于智能服務終端的測試.實證表明，本文提出的針對智能服務終端的探索性自適應FSM測試方法就是一種很實用的測試方法.這套理論和方法是否能夠被廣泛地應用于其他的測試對象，有待作進一步的驗證.

智能服務終端已經被各行各業廣泛地應用于降低成本、提高服務質量.從10種不同自動服務設備的測試結果可知，盡管這些設備的功能沒有明顯的缺陷，但在用戶邏輯上普遍存在各種各樣的問題,其質量問題仍然有待進一步提高.

智能服務終端從目前單一服務型階段正在逐步過渡到“一機多用，多機協同”階段，如何保證智能化的多服務型的網絡化智能服務終端始終健康有序地工作，盡早發現其中隱藏的問題，是我們正在進行的研究方向.

作者貢獻聲明：聶鈺格負責相關實驗設計、算法設計和論文撰寫;殷蓓蓓和裴翰宇提出了自適應測試相關指導意見并進行了論文修改;李莉提出指導意見，討論論文結構，參與論文修改;徐立鑫進行了編碼和平臺集成.