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

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

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

3(計(jì)算機(jī)軟件新技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室(南京大學(xué)) 南京 210023)

(zy2103520@buaa.edu.cn)

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

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

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

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

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

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

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

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

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

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

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

本文的主要貢獻(xiàn)有3個(gè)方面:

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

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

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

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

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

定義1.FSM定義.一個(gè)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ù).即當(dāng)FSM在狀態(tài)s∈S上收到輸入x∈I后，它會(huì)轉(zhuǎn)移到狀態(tài)δ(s，x)，并產(chǎn)生輸出λ(s，x)[12].

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

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

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

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

下面解釋探索性自適應(yīng)FSM測(cè)試方法中包含的測(cè)試?yán)砟?，并以遞進(jìn)的方式逐步刻畫該測(cè)試方法的概率.

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

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

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

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

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

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

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

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

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

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

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

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

2 本文方法及實(shí)例分析

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

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

輸入：〈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é)點(diǎn)隊(duì)列(當(dāng)前節(jié)點(diǎn)，到當(dāng)前節(jié)點(diǎn)的路徑)*/

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

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

⑦Q.enQueue(Nfirst,Pfirst);

⑧ whileQ.isNotEmpty() do

⑨N,P←Q.deQueue();

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

/*擴(kuò)展路徑達(dá)到新的狀態(tài)節(jié)點(diǎn)*/

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

/*新的路徑進(jìn)入隊(duì)列*/

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

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

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

2.1 探索性測(cè)試過程

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

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

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

2.2 建立模型

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

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

2.3 自適應(yīng)測(cè)試

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)設(shè)計(jì)及結(jié)果

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

3.1 研究問題

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

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

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

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

3.2 實(shí)驗(yàn)對(duì)象

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

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

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

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

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

3.4 實(shí)驗(yàn)結(jié)果

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

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

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

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

Table 2 Experimental Object and Testing Results表2 實(shí)驗(yàn)對(duì)象及測(cè)試結(jié)果

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

續(xù)表3

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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