智能服务终端的探索性自适应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种不同自动服务设备的测试结果可知，尽管这些设备的功能没有明显的缺陷，但在用户逻辑上普遍存在各种各样的问题,其质量问题仍然有待进一步提高.

智能服务终端从目前单一服务型阶段正在逐步过渡到“一机多用，多机协同”阶段，如何保证智能化的多服务型的网络化智能服务终端始终健康有序地工作，尽早发现其中隐藏的问题，是我们正在进行的研究方向.

作者贡献声明：聂钰格负责相关实验设计、算法设计和论文撰写;殷蓓蓓和裴翰宇提出了自适应测试相关指导意见并进行了论文修改;李莉提出指导意见，讨论论文结构，参与论文修改;徐立鑫进行了编码和平台集成.