基于EFSM不定型切片测试用例自动生成的研究

苏 宁 郭俊霞 李 征 赵瑞莲

(北京化工大学信息科学与技术学院 北京 100029) (suning311@163.com)

基于EFSM不定型切片测试用例自动生成的研究

苏 宁 郭俊霞 李 征 赵瑞莲

(北京化工大学信息科学与技术学院 北京 100029) (suning311@163.com)

基于模型的测试是软件测试中一个重要分支，但随着模型规模的增大，测试用例生成也变得越来越困难.扩展有限状态机(extended finite state machine, EFSM)是一种广泛应用的模型，它是对有限状态机(finite state machine，FSM)的扩展，能够更精确地刻画软件系统的动态行为.对EFSM模型的测试主要包含2个部分：测试迁移路径的生成和覆盖测试迁移路径的测试数据的生成.基于搜索的方法已被应用于测试数据的生成.为了提高在大规模EFSM模型中测试用例生成的效率，在前期对EFSM模型非终止性研究新型依赖性分析和切片技术的基础上，提出了基于EFSM模型不定型切片的测试用例生成方法和测试用例补全方法.通过2个案例分析得出：基于模型切片可以更加准确地生成可行路径和提高测试强度.基于7个基准EFSM模型的实验结果表明，在大多数情况下，在切片上生成测试用例的效率都比在原模型上高.

EFSM模型；依赖性分析；切片；测试用例生成；测试用例补全

Fig. 1 The EFSM model of lift and its amorphous slice图1 电梯EFSM模型及其不定型切片

模型是软件系统的抽象，基于模型的测试[1-2]将软件测试提前到模型阶段，采用形式化的方法验证软件行为，从而发现软件中的错误和故障，是软件测试领域中的一个重要研究方向.扩展有限状态机(extended finite state machine, EFSM)模型在有限状态机(finite state machine, FSM)模型的基础上增加了变量、操作和状态迁移的前置条件.EFSM模型可以更加精确地刻画软件系统的动态行为，因此被广泛应用于通信协议软件、嵌入式系统、对象之间的交互行为建模等.基于EFSM模型的测试技术具有重要的研究意义与实用价值.

通常来说，基于EFSM模型的测试用例生成主要包含2个部分：测试迁移路径的生成和覆盖迁移路径的测试数据生成[3].其中，测试迁移路径生成是指生成一条从起始迁移到被测迁移的连续迁移序列路径；测试数据生成是指根据测试迁移路径生成迁移中的事件以及事件上的变量值.近年来，随着基于搜索的软件工程及软件测试技术的发展，启发式搜索算法在EFSM模型测试数据生成中的应用获得了很大进展，主要包括禁忌搜索算法[3]、遗传算法(genetic algorithm， GA)[4-5]、模拟退火算法[6]、爬山算法[7]等，其中Zhao等人[4]研究了基于遗传搜索的EFSM模型测试数据生成效率的影响因素，表明测试用例的生成效率与EFSM模型的规模成反比关系.在实际应用中，软件系统规模的增大使对应模型的规模也变得越来越大，这必将会导致测试难度的增加和效率的降低.

为了提高EFSM模型中测试用例生成的效率，本文提出了一种基于模型切片的测试用例生成方法.与程序切片技术相似，EFSM模型切片同样是根据依赖性分析，以原模型特定迁移为准则对模型进行约简.不同的是EFSM模型自身具有非决定性和非终止性，目前针对模型非终止性的依赖性分析[8]和切片方法[9]已有了一定的研究，为基于模型切片的测试用例生成奠定了基础.依赖性分析可以准确识别出模型中与被测迁移有依赖关系的迁移，而切片方法则可以移除没有依赖关系的迁移，进而缩短测试路径，提高测试用例生成效率.另外，覆盖被测迁移的路径通常有很多，现有的方法优先选取最短路径.但一条包含尽可能多的具有依赖关系迁移的测试路径，其测试强度会大大增强，能够发现更加复杂的错误.目前，基于程序切片的测试已有了广泛的研究和应用[10]，但基于模型切片的测试还是一个有待开发的研究领域.

本文考虑了基于依赖性分析的EFSM模型不定型切片[9]用于测试用例生成.不定型切片只保留了模型的语义但不再保留模型的语法，即以EFSM模型的特定迁移为准则生成切片模型，其行为与原模型一致，但结构不同.基于EFSM模型切片生成测试用例，首先生成覆盖被测对象的测试路径，但由于模型结构的改变，基于切片模型生成的测试路径不能直接匹配到原模型上，进而生成的测试数据不能直接应用到原模型上.例如图1(a)给出了电梯系统门控制器的EFSM模型[11]，它描述电梯等待乘客进入或离开，以及开关门的过程；图1(b)是对原模型进行依赖分析后应用约简合并规则形成的不定型切片.以t11为被测迁移，从原模型(如图1(a)所示)中选取一条从t1到t11的路径，会优先选取最短路径[t1，t3，t5，t10，t11]，但在切片模型(如图1(b)所示)中会选取路径[t5，t11].由于不定型切片算法中的约简合并规则导致了测试路径变短，可以降低测试用例生成成本，但切片上生成的测试数据不能在原模型上直接使用.研究发现，切片上的测试路径是原模型对应路径的子集，所以可以设计补全方法来保证在原模型上运行.本文进一步提出测试路径和测试数据的补全规则，并通过7个基准的EFSM模型实验验证，证明了方法的可行性.

本文的主要贡献有：1)提出了基于EFSM模型不定型切片的测试用例生成方法框架；2)给出了基于EFSM模型切片迁移路径选取准则，和在原模型上选取测试路径相比，基于切片的方法可以精确选取测试路径，同时提高测试强度；3)针对切片过程中迁移的约简和状态的合并，给出了测试路径补全规则和测试数据补全规则；4)实验结果表明切片上生成的测试数据通过补全规则可以全部在原模型上运行，并且在大多数情况下，在切片上生成测试用例的效率比在原模型上高.

1 EFSM模型及相关概念

1.1 扩展有限状态机(EFSM)模型

定义1. 扩展有限状态机(EFSM).EFSM可以表示为一个六元组，M=(S，s0，T，E，Var，v0)，其中S，T，E，Var分别是状态集、迁移集、触发事件集和变量集.迁移集T中的每个迁移t由源状态source(t)∈S，目标状态target(t)∈S和标签label(t)组成.标签的形式为e[c]a，其中e∈E，当事件e触发后，若满足c中的条件，则执行a中的一系列操作.标签中的每个部分都是可选的.若迁移t的标签为空，称之为ε-迁移.若迁移满足source(t)=target(t)，称之为自循环迁移.若迁移满足source(tj)=target(ti)，称tj是ti的后继迁移.若迁移是以初始状态Start为源状态，称之为起始迁移.

1.2 依赖分析

一般说来，依赖关系主要有2种：数据依赖和控制依赖.其中，数据依赖体现的是迁移上变量的定义使用关系，控制依赖体现的是迁移之间的支配关系.

定义2. 数据依赖(data dependence, DD).ti→DDtj表示迁移tj对于变量v数据依赖于迁移ti满足：

1)v∈vdef(ti)，其中vdef(ti) 是由迁移ti定义的变量集合，即由迁移ti上的操作定义或作为事件参数定义的;

2)v∈vuse(tj)，其中vuse(tj)是迁移tj在触发条件和操作中使用的变量集合;

3) 存在一条从ti出发到tj的EFSM路径，其中v没有被任何中间迁移修改过.

定义3. 控制依赖(control dependence， CD).ti→CDtj表示迁移tj控制依赖于迁移ti当且仅当ti具有至少一个兄弟迁移tk并且：

1) 对于所有路径π∈PATH(ti)，source(tj) 属于π;

2) 存在一条路径π∈PATH(tk)，满足source(tj)不属于π.

根据路径类型的不同，控制依赖主要可以分为3种类型[8]：非终止敏感控制依赖(non-termination sensitive control dependence， NTSCD)、非终止非敏感控制依赖(non-termination insensitive control de-pendence, NTICD)、不公平非终止非敏感控制依赖(unfair non-termination insensitive control dependence， UNTICD).本文主要考虑的是NTICD和NTSCD.除了对应路径类型的不同，NTICD和NTSCD还有一个很大的区别，就是NTICD无法计算出control sink(control sink是指可以形成一个强连通结构的迁移集合K，其中，K中的每个迁移的后继迁移也都存在于K)中的控制依赖信息,但是NTSCD却可以.所以在大多数情况下，使用NTSCD生成的切片也会比用NTICD生成的切片大一些.

1.3 不定型切片

根据是否保留原模型的语法，模型切片可以分为定型切片和不定型切片.定型切片是基于依赖分析，依据切片准则，将与切片准则中的被测迁移无关的迁移标签置空得到的.在得到定型切片后，依据制定的约简合并规则移除空迁移(即ε-迁移)就可以得到不定型切片.

定义4. 切片准则(slicing criterion).EFSM模型的切片准则是一个(t,V)对，其中t∈T，变量集V⊆Var.

Fig. 2 The EFSM model of ATM图2 ATM取款机的EFSM模型

定义5. 切片(slice).EFSM模型切片M′是对原EFSM模型M的约简.如果e1是M的输入事件，那么M′存在一个输入事件e2，使得：

1)e2是e1的子序列.在不改变元素顺序的情况下，移除序列e1中的一些元素，从而得到其子序列e2.

2) 当触发M中的e1时，t上的变量V的值与M′中e2触发期间的t上的V值相等.

本文采用文献[9]中定义使用的约简合并规则来生成不定型切片.文献中先应用Ilie和Yu[12]定义的规则合并状态移除ε-迁移，然后应用ε-消除移除剩余的ε-迁移以及不可达的状态，最后应用迁移之间的恒等关系(左恒等右恒等)生成一个最小化的切片模型.

1.4 迁移路径

定义6. 迁移路径(transition path， TP).EFSM模型的路径指的是连续的迁移序列.即路径π=[t1，t2，…，ti-1，ti，ti+1，…，tn]，其中target(ti)=source(ti+1),1≤i

一条迁移路径TP是可行迁移路径(feasible transition path， FTP) 当且仅当存在输入使其按顺序遍历路径中的每个迁移ti.然而在EFSM模型中，由于动作(action)和条件(condition)中变量之间的依赖关系，导致了给定的迁移路径TP可能是不可行的[13].

2 实例研究

在本节中，我们通过2个实例对基于EFSM模型切片的测试用例生成优势，即基于模型切片可以更加准确地生成可行路径和提高测试强度进行说明.

图2是ATM取款机的EFSM模型[14]，模型中描述了2种账户类型(查询和储蓄)和3种交易类型(取款、存款和查询余额).迁移t3是3次输入密码错误后退出系统的操作.为了正确测试迁移t3，要连续3次输入错误密码，即t2迁移连续执行3次.在原模型中选取从初始迁移t1到t3的路径时，由于t2是一条自循环迁移，可以加入路径中，也可以不加入路径中.而路径选取会优先选取最短路径，即[t1，t3]，但显然这是一条不可行路径.

在使用基于切片的测试方法中，首先以被测迁移t3为准则生成切片，如图3所示.由于切片是通过依赖分析得到的，也就是说对切片准则存在影响的迁移都应该包含在切片中.从图3所示的切片中，可以直观地看出迁移t2对切片准则中的t3存在影响，也就是说在选取从t1到t3的路径时，要将t2包含进路径中才可能保证选取路径的可行性.

第2个实例同样以图2所示ATM模型为例，但选取迁移t11为测试对象.在原模型中选取一条从t1到t11的路径，会优先选取最短路径[t1，t4，t6，t7，t11].图4给出了以t11为切片准则生成的不定型切片，可以直观地发现与t11存在依赖关系的所有迁移.为了保证测试的有效性和强度，可以通过设定规则将与之有依赖关系的迁移(如t13，t14)尽可能包含进路径中，这种情况下在切片中选取的路径长度会变长，但测试强度也会增大.

Fig. 3 Amorphous slice with slicing criterion t3 for Fig.2图3 图2中模型以t3为切片准则生成的不定型切片

Fig. 4 Amorphous slice with slicing criterion t11 for Fig.2图4 图2中模型以t11为切片准则生成的不定型切片

3 基于不定型切片测试用例的生成

3.1 方法概述

本文考虑的不定型切片是基于依赖性分析的，所以要首先对模型进行依赖分析，得到其迁移之间的依赖关系.之后，就可以依据切片准则以及状态迁移的合并约简准则得到目标模型，也就是不定型切片.不定型切片虽然是对原模型的约简，但也是一个EFSM模型，测试用例生成的步骤同样适用，所以要首先基于切片模型生成测试路径，然后再对路径生成测试数据.在切片上生成的测试数据，需要在原模型中运行.依据切片的定义，可以知道基于切片生成的测试数据是原模型测试数据的子集，需要设计补全方法将其补全才能保证在原模型上运行.

图5给出了基于不定型切片的测试用例生成系统框图.从图5中可以看出，基于不定型切片的测试用例生成主要包含2部分：切片生成(slicing)和测试生成(test generation).图5中虚线框部分，即测试用例生成是本文研究的重点.

Fig. 5 The framework of amorphous slicing based test case generation图5 基于不定型切片测试用例生成的基本框图

切片生成主要包括依赖分析(dependence analysis)和用切片工具(slicing tool)生成切片.

1) 依赖分析.分析EFSM模型迁移之间的依赖关系，包括数据依赖关系和控制依赖关系.

2) 切片工具.以被测迁移为切片准则在依赖分析的基础上生成不定型切片.

测试生成主要包括在切片上生成测试用例(test case generation)和补全测试用例(test case compensating).

1) 生成测试用例.首先在切片上生成测试路径，然后对测试路径生成测试数据.

2) 补全测试用例.在切片上生成测试用例后，要在原EFSM模型中运行来执行测试.根据不定型切片的定义，针对切片准则在切片上生成的路径应是原模型对应路径的子集.为保证切片上生成的测试用例能在原模型上运行需要对路径进行补全，并对新迁移上的变量补全测试数据.

3.2 基于不定型切片的测试用例生成

EFSM模型的不定型切片是对原模型的约简，它虽然不再保留原EFSM模型的语法，但是仍然保留了原模型的语义.在EFSM模型切片上生成测试用例和原模型相同，也包含2个步骤：测试迁移路径的生成和测试数据的生成.

3.2.1 测试迁移路径的生成

本文是以被测迁移为测试对象来进行测试用例生成，以验证被测迁移的正确性，故本文的测试路径指的是从起始迁移到被测迁移的连续迁移序列.

不定型切片是对原EFSM模型进行依赖分析后，依据切片准则对原模型某些状态进行合并，某些迁移进行约简后得到的.保留在切片中的迁移都是与被测迁移存在依赖关系的迁移.一般来说路径通常选取最短路径，但是通过第2节的实例研究可以知道，为了保证测试路径的可行性和测试强度，应该选取更多对被测迁移存在影响的迁移加入到路径当中.与此同时，由于切片中可能会存在迁移的合并，如图6中的t9t10，在选取路径的时候也需对此问题进行考虑.

所以，依据上面的分析以及不定型切片的特点，定义3个规则：

规则1. 若切片中包含原模型中的自循环迁移，在选取路径时，要至少遍历这个自循环一次.

规则2. 在选取路径时，要尽可能多地包含切片中的迁移，即选取最长简单路径(最长简单路径是指含有最多迁移的简单路径).

规则3. 若切片中存在迁移的合并，在选取路径时，可只选择其中一个迁移进行遍历.

Fig. 6 Amorphous slice with slicing criterion t9 for Fig.2图6 图2中模型以t9为切片准则生成的不定型切片

规则1考虑的是第2节中案例1的情况，即原模型的自循环迁移如果包含在切片中，则和被测对象之间一定存在依赖关系，也就是对其会产生影响，不包含在路径中会导致路径的不可行；规则2考虑的是第2节中案例2的情况，即通过对切片的分析，在选取最短路径的基础上可以考虑加入更多的与被测对象存在依赖关系的迁移到路径中去，也就是选取最长简单路径，从而增加测试强度；规则3是针对存在等价迁移的情况，从图6中可以看到t9t10是一条合并的迁移，它是在切片形成的过程中对迁移做恒等分析造成的，也就是说合并的迁移在合并前相对于被测对象是等价的，所以在选取路径的时候，选择其一加入路径中即可.

3.2.2 测试数据的生成

在生成了测试路径之后就可以对这条路径进行测试数据的生成.测试数据指的是路径上的事件以及事件上的输入变量值.本文使用了基于遗传算法的EFSM模型测试数据自动化生成的方法[4].

Fig. 7 Example of test data图7 测试数据举例

具体而言，给定一条测试路径[t1，t2，…，tm]，对应测试数据是[e1[c1]a1，e2[c2]a2，…，em[cm]am]，其中ei[ci]ai表示迁移ti上的事件ei被触发后，如果满足ci中的条件，则执行ai中的动作.遗传算法的个体就是按顺序出现的事件序列e1，e2， …，em以及事件上的输入变量值x=(x1，x2，…，xn).图7给出了一条含有3个迁移的路径.路径中的测试序列是(eve1(a,b)，eve2，eve3)，其中a，b是需要生成数值的变量.例如(eve1(2,3)，eve2，eve3)是可以遍历这条路径的测试数据.

3.2.3 切片路径的补全

在切片上生成的测试数据，需要在原模型上运行.通过前面的分析以及切片的定义可知，在切片上生成的测试路径是原模型对应测试路径的子集，需要进行路径补全并对新补充的迁移生成测试数据.

通过对切片路径与对应原模型路径的对比分析，定义2个规则:

还是以图1为例，假设在切片模型(图1(b))中选取的测试路径是[t5，t11]，相对于原模型这是一条不完整的路径，无法直接将其对应到原模型路径中去，需要对其进行补充.首先发现切片路径中的起始迁移t5不是原模型(如图1(a)所示)中的起始迁移(原模型的起始迁移为t1)，此时就需要按照规则4补充原模型中从t1到t5的连续迁移序列；进一步观察可以发现，在原模型(如图1(a)所示)中t11不是t5的后继迁移，此时也需要对路径进行补充，也就是按照规则5补充原模型中从t5到t11的连续迁移序列.

显然，若规则4和规则5都不满足则无需进行路径的补全，即切片路径直接对应于原模型中的路径.

需要补充的迁移是在切片形成的过程中约简的，与被测迁移没有数据依赖或者控制依赖的关系.在选择补充路径的时候只需要选取一条可行的路径进行补充即可.

3.2.4 测试数据的补全

补全完路径之后，需对补充的迁移路径上的变量生成测试数据，这样才是完整的测试数据，才能保证其能在原模型上运行.通过对补充路径中的迁移进行分析，定义2个规则:

规则6. 若补充迁移上的变量v是切片路径中已存在的变量，则将切片上生成的测试数据直接赋值给v.

规则7. 若补充迁移上的变量v是新引入的变量，则根据变量v的值域，采用随机算法生成测试数据.

规则6指的是对于已经在切片路径中存在的变量，它在对切片路径生成测试数据的时候已经有了数值，所以就不用再对其进行测试数据的生成，直接将切片上生成的测试数据复制给它即可.而对于规则7中新引入的变量，它之所以会在切片形成过程中随着它所在的迁移被一起约简，是因为它与被测迁移上的变量不存在任何数据依赖关系，那么在对其生成测试数据时，只要随机生成一个值保证能够通过路径中的新增迁移即可.

4 实验及结果分析

为了验证基于EFSM模型切片测试用例生成方法的有效性，本文提出3个研究问题，并通过实验进行验证.

RQ1. 在切片上生成的测试用例在原模型是否可行？

RQ2. 在切片上和原模型上生成测试用例，哪种方法生成测试用例的效率更高？

RQ3. 不同的依赖关系得到的切片是否会影响测试用例的生成效率？

4.1 实验设计

本文选取了7个基准模型进行实验.表1给出了每个模型的状态数(s)、迁移数(t)、事件数(e)以及出现在迁移标签上的变量数(v)，最后4列给出了实验中使用的切片算法生成切片平均大小.实验平台为一台配有16核英特尔Xeon®CPU E5620主频2.40 GHz的服务器，编程语言为Python.

实验过程中，分别把7个模型的每个迁移作为被测对象，同时基于原模型和切片模型，生成能够覆盖被测迁移的测试数据.不定型切片使用了SLIMER工具[9]，依赖性分析包括了NTICD和NTSCD两种控制依赖关系及数据依赖DD.原模型上的测试用例生成采用了文献[4]中的基于GA的方法，基于切片的测试用例生成按本文提出的方法生成路径及测试数据，并按规则补全成可以在原模型上运行的测试数据.

Table 1 Description of Experimental Models

4.2 实验结果和分析

由于EFSM模型不定型切片的特点，切片上的测试数据需经过补全才能运行在原模型上.RQ1的提出是为了检验本文提出的路径补全规则和数据补全规则.测试数据的生成和补全是全自动完成的，在测试数据运行阶段，我们通过人工检验了生成的测试数据能否在对应的原模型上运行.检验结果是在切片上生成的测试数据通过路径补全和数据补全在原模型上都是可行的，说明了本文提出的补全规则是正确的.

针对后2个问题，虽然切片尺寸小，理论上生成测试用例的时间少，但执行EFSM模型的依赖性分析和切片及后期的用例补全等操作都会额外增加时间，所以只能通过实验结果来比较不同方法生成测试用例的效率.在实验过程中分别采用了NTICD+DD和NTSCD+DD依赖关系生成切片，并统计了在切片上生成测试用例的时间和在原模型上生成测试用例的时间.

在基于切片生成测试用例时，因为每个模型的依赖性分析只需要执行一次就可以完成所有切片，在统计测试用例生成时间上，设计了2种方法，一种是对模型中单个迁移ti的比较，另一种是模型整体上的比较.图8、图9分别给出了7个模型中单个迁移ti以及模型整体上在生成测试用例时间上的比较.图8中单个迁移的时间不包含依赖性分析，图9中以模型整体分析上加入了一次依赖性分析时间.由于有些模型时间跨度较大，图上的时间是对其取lg得到的结果.Lift模型生成测试用例的时间较短，图9中Lift模型的时间是乘100后得到的结果.

图8中的横轴表示迁移，纵轴表示测试用例生成的时间(以秒为单位).从图8中可以看出，ATM， FuelPump， Lift(Lift仅在NTICD+DD)在切片上生成测试用例的效率比在原模型上高，Cashier，PrintToken，Vending Machine，Lift(Lift仅在NTSCD+DD)在切片上生成测试用例的效率比在原模型上低，而CruiseControl在切片上生成测试用例的效率和在原模型上差不多.通过分析CruiseControl的切片可以发现，CruiseControl切片形状与原模型形状几乎相同，故其在切片上做测试用例生成与在原模型上的结果差不多.虽然有些模型在切片上生成测试用例的效率较低，但是通过分析实验数据可知其在切片上生成测试用例的时间与原模型上的时间差基本上都在2 s以内.结合表1进一步分析比较切片与原模型测试用例生成可以发现，切片对原模型约简得越多，其做测试用例的生成效率越好.

对于RQ3，结合表1中NTICD+DD与NTSCD+DD平均切片大小分析图8中的数据，可以发现当切片规模相近时(如ATM，Cashier，CruiseControl，FuelPump)， 2种切片的测试用例生成效率也相近；当切片规模相差较大时(如Vending Machine，Lift)，切片越大，其生成测试用例的效率就越低.对于PrintToken模型，2种切片的规模差不多，但是发现某些迁移用NTICD+DD生成测试用例的效率低些.通过分析实验数据可知，这是由于这些迁移生成的切片时间较长导致的(2种切片的测试用例的生成时间差不多).

Fig. 8 The comparison of test generation between slices and original EFSMs on single transition ti图8 单个迁移ti在切片上和原模型上的测试用例生成效率比较

Fig. 9 The comparison of test generation between slices and original EFSMs on whole EFSM图9 EFSM整体在切片上和原模型上的测试用例生成效率比较

图9中的横轴表示模型，纵轴表示测试用例生成的时间(以秒为单位).从图9可以看出，除了PrintToken模型，其余6个模型整体上在NTICD+DD切片上的测试用例生成效率都比在原模型上生成效率高些.而导致PrintToken模型切片测试用例生成效率低的原因是其生成切片的时间较长，但平均时间差仍基本在2 s内.

对于RQ3，同样结合表1中NTICD+DD与NTSCD+DD平均切片大小分析图9中的数据，可以发现不同依赖关系得到的切片不会影响测试用例生成效率，测试用例生成效率与切片规模的大小相关：切片规模越小，其生成测试用例的效率就越高(如ATM，Cashier，FuelPump，VendingMachine，Lift).由于CruiseControl模型的2种切片的规模和形状差不多，故其整体上生成测试用例的效率也差不多.而PrintToken模型由于使用NTICD+DD生成切片的时间整体上较长，故其生成测试用例的效率较低.

5 相关工作

本文方法的思想来源于基于程序切片的测试用例生成，关于程序切片的测试现在已经有大量的研究，可以参阅相关综述文章[15-17].

EFSM模型是状态模型的一种，目前存在一些针对其他的状态切片的方法.Heimdahl等人[18]提出了一个需求状态机语言(Requirement State Machine Language, RSML)规则说明的切片方法，首先它通过移除不满足定义条件的行为来进行约简；然后依据一个迁移或者变量，用数据流和控制流做切片.Wang等人[19]给出了一个扩展的层次自动机(extended hierarchical automaton, EHA)[20]切片算法.通过分层处理，依据并发和通信，他们定义了数据依赖和控制依赖,并通过得到的依赖关系依据切片准则生成切片.

在针对EFSM模型切片的研究中，根据切片准则的不同，以迁移触发事件为准则的模型切片方法被提出，称为基于事件的模型切片(也称为模型映射Model Projection)[21-22].该触发事件集在模型外部环境中将不再能够被触发(即事件失效)，形成了一个具有约束的模型外部环境.Androutsopoulos等人[9]对EFSM模型的不定型切片进行了研究，介绍了基于依赖集的EFSM模型切片算法以及一个工具，并证实了他们提出的算法适合基于依赖的切片.

由于EFSM模型在FSM模型的基础上增加了变量以及状态迁移的前置条件，迁移之间可能会存在冲突导致迁移路径的不可行.基于FSM模型的测试用例生成方法不能直接用于EFSM模型中，所以有学者对EFSM模型的测试用例生成做了研究.文献[4,14,23-30]是对测试路径生成做的研究，这些文献给出了判定路径可行的方法，从而为后续生成有效的测试数据奠定了理论基础.其中，Hierons等人[28-29]尝试通过扩展EFSM模型来绕开不可行路径问题.经过扩展后的EFSM模型简化了测试序列的生成，并且扩展后的EFSM模型中的所有路径都是可行的.最终，这个方法选取了一组可执行路径集和相应的可以覆盖所选测试准则的测试数据集.Duale等人[26,30]考虑解决EFSM模型中2条迁移之间的冲突问题.他们消除冲突的方法是基于一种图像分割技术，这个技术将存在冲突的迁移分别置于2个独立的子图中，以避免它们包含在相同的路径中.在这些方法中，通过对原EFSM模型进行研究以处理路径的不可行性；而本文通过对EFSM模型不定型切片进行研究，在切片的基础上对路径不可行性进行处理.文献[3-7,31-35]对测试数据的生成做了研究，他们大多采用基于搜索的算法生成测试数据，其中，Zhao等人[4]采用遗传算法生成测试数据，本文在不定型切片上生成测试数据时也采用了遗传算法.

6 结束语

本文提出了一种基于EFSM模型不定型切片的测试用例生成方法，并通过案例分析说明基于EFSM模型切片的测试用例生成方法可以更准确地选取测试路径和有效增大测试强度.根据切片上测试路径是原模型对应路径子集的特点，提出了测试路径和测试数据补全规则.实验结果显示在切片上生成的测试数据补全后都可在原模型上运行.同时基于切片的方法中测试用例生成效率在大多数情况下都比较高，效率低的主要原因是依赖性分析和执行切片的时间较长，但整体评价时间差在2 s范围内.

[1]Padgham L, Zhang Zhiyong, Thangarajah J, et al. Model-based test oracle generation for automated unit testing of agent systems[J]. IEEE Trans on Software Engineering, 2013, 39(9): 1230-1244

[2]Enoiu E P, Sundmark D, Pettersson P. Model-based test suite generation for function block diagrams using the uppaal model checker[C]Proc of the 6th IEEE Int Conf on Software Testing, Verification and Validation Workshops (ICSTW). Piscataway, NJ: IEEE, 2013: 158-167

[3]Ren Jun, Zhao Ruilian, Li Zheng. Automatic generation of test data for extended finite state machine models based on Tabu search algorithm[J]. Journal of Computer Applications, 2011, 31(9): 2440-2443 (in Chinese)(任君, 赵瑞莲, 李征. 基于禁忌搜索算法的可扩展有限状态机模型测试数据自动生成[J]. 计算机应用, 2011, 31(9): 2440-2443)

[4]Zhao Ruilian, Harman M, Li Zheng. Empirical study on the efficiency of search based test generation for EFSM models[C]Proc of the 3rd IEEE Int Conf on Software Testing, Verification, and Validation Workshops (ICSTW). Piscataway, NJ: IEEE, 2010: 222-231

[5]Zhou Xiaofei, Zhao Ruilian, You Feng. EFSM-based test data generation with multi-population genetic algorithm[C]Proc of the 5th IEEE Int Conf on Software Engineering and Service Science (ICSESS). Piscataway, NJ: IEEE, 2014: 925-928

[6]Cheng Xichao. Test data automatic generation based on simulated annealing algorithm for EFSM [D]. Beijing: Beijing University of Chemical Technology, 2011 (in Chinese)(程喜朝. 基于模拟退火算法的 EFSM 模型测试数据自动生成[D]. 北京: 北京化工大学, 2011)

[7]Kalaji A S, Hierons R M, Swift S. A search-based approach for automatic test generation from extended finite state machine (EFSM)[C]Proc of Testing: Academic and Industrial Conf-Practice and Research Techniques(TAIC PART). Piscataway, NJ: IEEE, 2009: 131-132

[8]Androutsopoulos K, Gold N, Harman M, et al. A theoretical and empirical study of EFSM dependence[C]Proc of the 25th IEEE Int Conf on Software Maintenance (ICSM). Piscataway, NJ: IEEE, 2009: 287-296

[9]Androutsopoulos K, Clark D, Harman M, et al. Amorphous slicing of extended finite state machines[J]. IEEE Trans on Software Engineering, 2013, 39(7): 892-909

[10]Binkley D. The application of program slicing to regression testing[J]. Information and Software Technology, 1998, 40(11): 583-594

[11]Strobl F, Wisspeintner A. Specification of an elevator control system—An autofocus case study[JOL]. 1999[2015-12-09]. https:www.researchgate.netpublication239552338_Specification_of_an_Elevator_Control_System_An_AutoFocus_Case_Study

[12]Ilie L, Yu S. Reducing NFAs by invariant equivalences[J]. Theoretical Computer Science, 2003, 306(1): 373-390

[13]Kalaji A S, Hierons R M, Swift S. Generating feasible transition paths for testing from an extended finite state machine (EFSM)[C]Proc of the 3rd IEEE Int Conf on Software Testing Verification and Validation (ICST). Piscataway, NJ: IEEE, 2009: 230-239

[14]Korel B, Singh I, Tahat L, et al. Slicing of state-based models[C]Proc of the 19th IEEE Int Conf on Software Maintenance (ICSM). Piscataway, NJ: IEEE, 2003: 34-43

[15]Tip F. A survey of program slicing techniques[J]. Journal of Programming Languages, 1995, 3(3): 121-189

[16]Binkley D, Harman M. A survey of empirical results on program slicing[J]. Advances in Computers, 2004, 62(1112): 105-178

[17]Xu Baowen, Qian Jun, Zhang Xiaofang, et al. A brief survey of program slicing[J]. ACM SIGSOFT Software Engineering Notes, 2005, 30(2): 1-36

[18]Heimdahl M P E, Whalen M W. Reduction and slicing of hierarchical state machines[J]ACM SIGSOFT Software Engineering Notes, 1999, 22(6): 450-467

[19]Wang Ji, Dong Wei, Qi Zhichang. Slicing hierarchical automata for model checking UML statecharts[C]Proc of the 4th Int Conf on Formal Engineering Methods: Formal Methods and Software Engineering. Berlin: Springer, 2002: 435-446

[20]Dong Wei, Wang Ji, Qi Xuan, et al. Model checking UML statecharts[C]Proc of the 8th Asia-Pacific on Software Engineering Conf (APSEC). Los Alamitos, CA: IEEE Computer Scienty, 2001: 363-370

[21]Androutsopoulos K, Binkley D, Clark D, et al. Model projection: Simplifying models in response to restricting the environment[C]Proc of the 33rd Int Conf on Software Engineering. New York: ACM, 2011: 291-300

[22]Lano K, Rahimi S K. Slicing techniques for UML models[J]. Journal of Object Technology, 2011, 10(11): 1-49

[23]Yang Rui, Chen Zhenyu, Xu Baowen, et al. Improve the effectiveness of test case generation on EFSM via automatic path feasibility analysis[C]Proc of the 13th IEEE Int Symp on High -Assurance Systems Engineering (HASE). Piscataway, NJ: IEEE, 2011: 17-24

[24]Wu Tianyong, Yan Jun, Zhang Jian. A path-oriented approach to generating executable test sequences for extended finite state machines[C]Proc of the 6th IEEE Int Symp on Theoretical Aspects of Software Engineering. Piscataway, NJ: IEEE, 2012: 267-270

[25]Lu Gongzheng, Miao Huaikou. Feasibility analysis of the EFSM transition path combining slicing with theorem proving[C]Proc of IEEE Int Symp on Theoretical Aspects of Software Engineering. Piscataway, NJ: IEEE, 2013: 153-156

[26]Duale A Y, Uyar M U. A method enabling feasible conformance test sequence generation for EFSM models[J]. IEEE Trans on Computers, 2004, 53(5): 614-627

[27]Wong S, Ooi C Y, Hau Y W, et al. Feasible transition path generation for EFSM-based system testing[C]Proc of IEEE Int Symp on Circuits and Systems. Piscataway, NJ: IEEE, 2013: 1724-1727

[28]Hierons R M, Kim T H, Ural H. Expanding an extended finite state machine to aid testability[C]Proc of Int Computer Software and Applications Conf on Prolonging Software Life: Development and Redevelopment. Los Alamitos, CA: IEEE Computer Society, 2002: 334-339

[29]Hierons R M, Kim T H, Ural H. On the testability of SDL specifications[J]. Computer Networks, 2004, 44(5): 681-700

[30]Uyar M U, Duale A Y. Test generation for EFSM models of complex army protocols with inconsistencies[C]Proc of Century Military Communications Conf. Piscataway, NJ: IEEE, 2000: 340-346

[31]Kalaji A S, Hierons R M, Swift S. An integrated search-based approach for automatic testing from extended finite state machine (EFSM) models[J]. Information and Software Technology, 2011, 53(12): 1297-1318

[32]Yano T, Martins E, De Sousa F L. MOST: A multi-objective search-based testing from EFSM[C]Proc of the 4th IEEE Int Conf on Software Testing, Verification and Validation Workshops. Piscataway, NJ: IEEE, 2011: 164-173

[33]Asoudeh N, Labiche Y. Multi-objective construction of an entire adequate test suite for an EFSM[C]Proc of the 25th IEEE Int Symp on Software Reliability Engineering. Piscataway, NJ: IEEE, 2014: 288-299

[34]Zhang Jie, Yang Rui, Chen Zhenyu, et al. Automated EFSM-based test case generation with scatter search[C]Proc of the 7th Int Workshop on Automation of Software Test. Piscataway, NJ: IEEE, 2012: 76-82

[35]You Juan, Li Junquan, Xia Song. Algorithm for generating test sequences based on branch and bound in EFSM model[J]. Application Research of Computers, 2013, 30(5): 1349-1352 (in Chinese)(尤娟, 李俊全, 夏松. 基于分支界限搜索的EFSM协议测试序列生成算法[J]. 计算机应用研究, 2013, 30(5): 1349-1352)

Su Ning, born in 1990. Master candidate. Her main research interests include EFSM model slicing and test generation.

Guo Junxia, born in 1977. PhD, lecturer. Senior member of CCF. Her main research interests include partial information extraction and Web application testing (gjxia@mail.buct.edu.cn).

Li Zheng, born in 1974. Professor and PhD supervisor. Senior member of CCF. His main research interests include software analysis and testing, model analysis and testing, search based software testing.

Zhao Ruilian, born in 1964. Professor and PhD supervisor. Senior member of CCF. Her main research interests include software testing and software reliability analysis (rlzhao@mail.buct.edu.cn).

EFSM Amorphous Slicing Based Test Case Generation

Su Ning, Guo Junxia, Li Zheng, and Zhao Ruilian

(CollegeofInformationScienceandTechnology,BeijingUniversityofChemicalTechnology,Beijing100029)

Model based testing is a crucial dimension in software testing. However, with the increase of model scale, model based test case generation is becoming more and more arduous. Extended Finite State Machine (EFSM) has been widely used in industry, which is extended from Finite State Machine (FSM), and can depict the dynamic behavior of software system more accurately. EFSM based test case generation mainly includes two parts: test transition paths generation and test data generation that covers the test transition paths, in which search based technology is adapted in test data generation. In order to improve the efficiency of test case generation in large-scale EFSM models, EFSM slicing based test case generation and test case compensating are proposed based on the previous research on EFSM dependence analysis and slicing for non-termination of EFSM models. Two case studies are introduced to show that model slicing based test case generation is more accurate in feasible path generation and test intensity improvement. In this paper, the experiments on 7 standard EFSMs are conducted, and the results show that all of the test case generated from slice can be used in the original model, and in most cases, test case generation efficiency on slice is higher than that on the original model.

EFSM model; dependence analysis; slicing; test case generation; test case compensating

2015-12-09；

2016-06-14

国家自然科学基金项目(61170082,61472025)；教育部新世纪优秀人才支持计划项目(NCET-12-0757) This work was supported by the National Natural Science Foundation of China (61170082, 61472025) and the Project for New Century Excellent Talents in University (NCET-12-0757).

李征(lizheng@mail.buct.edu.cn)

TP311