智能服務(wù)終端的探索性自適應(yīng)FSM測試方法

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

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

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

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

(zy2103520@buaa.edu.cn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3) 將本文方法與傳統(tǒng)FSM測試方法、狀態(tài)轉(zhuǎn)換測試方法等進行了比較，并總結(jié)了目前智能服務(wù)終端普遍的缺陷和問題.

1 探索性自適應(yīng)FSM測試

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

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

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

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

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

Fig. 1 State transition diagram of FSM圖1 FSM的狀態(tài)轉(zhuǎn)換圖

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

1) 狀態(tài)轉(zhuǎn)換測試.根據(jù)測試對象的規(guī)格說明，可以將測試對象抽象為一個狀態(tài)轉(zhuǎn)換圖，根據(jù)狀態(tài)轉(zhuǎn)換圖設(shè)計測試用例系統(tǒng)檢測狀態(tài)轉(zhuǎn)換過程中可能存在的問題.測試的有效程度取決于狀態(tài)轉(zhuǎn)換圖是否正確反映了測試對象的規(guī)格說明.

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

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

對于一些要求比較高的應(yīng)用程序，可能還需要聲明3個狀態(tài)轉(zhuǎn)換測試準則：①所有的狀態(tài)和輸入的組合；②所有狀態(tài)轉(zhuǎn)換的組合；③所有狀態(tài)的任意順序的所有轉(zhuǎn)換，也可以重復(fù)連續(xù).

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

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

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

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

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

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

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

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

2 本文方法及實例分析

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

算法1.智能服務(wù)終端無環(huán)狀態(tài)及狀態(tài)遷移覆蓋測試用例生成.

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

輸出：無環(huán)路徑集TS.

① 根據(jù)智能服務(wù)終端FSM模型〈S，S0，I，O，δ，λ〉構(gòu)造初始狀態(tài)為S1的狀態(tài)遷移圖G;/*廣度優(yōu)先遍歷算法*/

②TS←?;

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

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

⑤Nfirst←S1;/*初始狀態(tài)節(jié)點*/

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

⑦Q.enQueue(Nfirst,Pfirst);

⑧ whileQ.isNotEmpty() do

⑨N,P←Q.deQueue();

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

/*擴展路徑達到新的狀態(tài)節(jié)點*/

/*記錄被覆蓋到的狀態(tài)遷移*/

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

展將出現(xiàn)環(huán)，終止*/

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

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

2.1 探索性測試過程

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

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

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

2.2 建立模型

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

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

2.3 自適應(yīng)測試

根據(jù)所建立的模型，應(yīng)用算法1生成了如下14條測試用例:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Fig. 5 Diagram1 of vending machine status transition圖5 自動售貨機狀態(tài)轉(zhuǎn)換圖1

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

經(jīng)過不斷地自適應(yīng)測試后，整理所有記錄的測試結(jié)果反饋可以發(fā)現(xiàn)存在的建模bug有：

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

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

存在系統(tǒng)bug有：

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

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

Fig. 6 Diagram2 of vending machine status transition圖6 自動售貨機狀態(tài)轉(zhuǎn)換圖2

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

3 實驗設(shè)計及結(jié)果

為了進一步驗證本文所提方法的應(yīng)用價值，以及深入發(fā)現(xiàn)智能服務(wù)終端存在的問題，我們提出了3個研究問題，設(shè)計了一組實驗，進行了系統(tǒng)的實證研究和總結(jié).

3.1 研究問題

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

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

研究問題2.通過無環(huán)狀態(tài)及狀態(tài)遷移覆蓋算法所生成的測試用例，是否能覆蓋被測系統(tǒng)所有的狀態(tài)和遷移，實現(xiàn)高效的狀態(tài)轉(zhuǎn)換測試.

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

3.2 實驗對象

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

3.3 基于GraphWalker的工具設(shè)計與實現(xiàn)

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

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

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

3.4 實驗結(jié)果

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

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

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

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

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

Table 3 Founded Problems List表3 發(fā)現(xiàn)問題列表

續(xù)表3

3.5 關(guān)于智能服務(wù)終端的實驗總結(jié)與建議

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

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

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

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

4 相關(guān)工作及比較

4.1 關(guān)于FSM的相關(guān)工作及比較

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

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

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

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

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

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

4.2 自適應(yīng)測試方法的優(yōu)越性

一般傳統(tǒng)的測試方法首先根據(jù)待測試系統(tǒng)模型設(shè)計一組滿足要求的測試用例；然后執(zhí)行測試用例，根據(jù)測試結(jié)果分析，定位修改故障；最后補充回歸測試用例，或者調(diào)整模型，重新生成測試用例.

自適應(yīng)測試在發(fā)現(xiàn)問題的第一時間，就著手處理問題，調(diào)整測試用例生成策略.僅以調(diào)整模型為例，可以粗略估計一下自適應(yīng)測試的測試成本.

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

可見，自適應(yīng)測試方法更加靈活，且能夠通過不斷迭代以較少的代價較好地解決需求規(guī)格缺乏或不詳?shù)膯栴}.

4.3 關(guān)于其他覆蓋準則的相關(guān)工作及比較

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

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

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

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

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

4.4 智能服務(wù)終端的其他測試方法

對智能服務(wù)終端的測試分為對硬件的測試和對軟件的測試，在開發(fā)過程中對軟件系統(tǒng)的測試包含了函數(shù)的接口測試、模塊的集成測試、整機的聯(lián)調(diào)測試[27].但是這樣的測試避免不了由于開發(fā)人員對需求理解的偏差等情況而導(dǎo)致的軟件系統(tǒng)缺陷.

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

本文提出的測試方法能夠?qū)σ延蟹椒ǖ挠行аa充，可以克服上述測試過程中的一些不足，實現(xiàn)充分有效的測試.

5 結(jié)論及未來工作

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

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

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

作者貢獻聲明：聶鈺格負責相關(guān)實驗設(shè)計、算法設(shè)計和論文撰寫;殷蓓蓓和裴翰宇提出了自適應(yīng)測試相關(guān)指導(dǎo)意見并進行了論文修改;李莉提出指導(dǎo)意見，討論論文結(jié)構(gòu)，參與論文修改;徐立鑫進行了編碼和平臺集成.