【文章摘要】

协议的一致性测试是用来检验协议实现是否符合协议规范，其关键技术就是测试序列的生成。本文提出了一种基于扩展的有限状态自动机EFSM 的全面的可执行的测试序列生成方法。该方法使用UIOE 方法对控制流进行分析，使用all-du-path 标准对数据流进行分析。通过使用改进的转换可执行分析TEA 和逆向判定性，用深度优先搜索的方法扩展出一棵转换可执行分析树，然后生成包含控制流和数据流的可执行测试序列。

【关键词】

一致性测试; 测试序列生成; 转换可执行分析; 逆向判定性

0 引言

协议一致性测试的主要目的是验证一个协议实现是否和它对应的协议描述一致，或者是在多大程度上一致，主要包括两方面：控制流测试和数据流测试。如何生成包含这两个方面的测试序列成为协议一致性测试的关键内容。为了得到标准的测试序列，需要对协议的行为建立模型，扩展的有限状态自动机EFSM 是在协议测试方面使用的较为广泛的一种模型。EFSM 是有限状态机FSM 的扩展，FSM 是对协议控制流进行描述，而EFSM 增加了对数据流的描述本文提出了一种基于EFSM 的包含控制流和数据流的协议一致性测试序列生成方法：使用TEA 方法和all-du-path 标准利用深度优先搜索扩展成可执行分析树，利用逆向判定性原理减小扩展空间，最后生成可执行的较短的覆盖面广的测试序列。

1 EFSM 模型

一个EFSM 模型M 通常被定义成一个8 元组<S,s0,V,I,O,P,A,T>，S 是状态集； s0 是初始状态，V 是变量集；I 是输入集； O 是输出集；P 是操作在变量上的谓词集；A 是操作在变量上的行为集；T 是非空转换集，T 中的元素t=(si,i,p,a,o,sj)， si 和sj 分别是转换t 的头状态和尾状态， i ∈ I，p ∈ P，a ∈ A，o ∈ O。

如果一个EFSM M 中的每个状态都可以通过某个可执行转换序列到达M 中的其他状态，那么M 是转换强连通的。如果M 中的每个状态都至少有一个可执行转换，那么M 是无陷阱的。如果M 是转换强连通的且无陷阱，那么M 中的每个状态都至少有一个可执行UIO 序列并且M 中的每一个转换都可以被测试。

本文提出的测试序列生成算法中的EFSM 为转换强连通且无陷阱。

2 控制流分析

控制流测试是检验一个转换是否生成了期望输出并达到了正确的最终状态。UIOE 方法是一种基于转换可执行分析的方法，以状态配置为节点，以可执行转换为弧，采用广度优先的策略，扩展生成可执行分析树，进而生成可转换序列。但是这种方法生成的序列较长，而且所需要扩展的状态空间太大，所以我们使用逆向判定性来改进UIOE 方法以缩短测试序列长度。如果由转换t 的输入输出和尾状态就可以判定出t 的头状态，那么t 是一个逆向可判定转换。每个UIOE 都是以一个逆向可判定转换开始的，一个转换t 可测试，那么至少存在一个可执行逆向可判定转换，它的头状态是t 的末状态。因此，使用逆向可判定性可以很大程度的缩小可执行扩展空间并从而缩短测试序列长度。

3 数据流分析

数据流测试的主要内容是测试状态转换之间的依赖关系。在文献[4] 中，作者定义了一系列程序测试数据选择标准， 这些标准定义了程序中变量的定义和使用间的关系。在这些标准中，最强的标准all-path 代价太大而且在回路的时候可能会产生无限多的路径，所以我们选择稍弱一点的all-du-path 标准，它可以只测试那些有数据依赖关系的路径从而产生一个合理的近似值。一个转换序列集合P 满足all-du-path 标准是指对于P 中的每个转换t，t 上定义的所有变量集合为def(t),P 包含t 关于def(t) 上所有变量的def-use 序列。

4 测试序列的生成

①把转换集合T 分为逆向可判定转换集合TI 和非逆向可判定转换TR，计算每个转换的def(t)，配置初始状态，从TI 中选择初始状态的一个可执行的逆向可判定转换作为待测转换。

②对待测转换进行可执行扩展。根据深度优先搜索的策略，确定某个变量作为路径的开始，然后找到该变量的def-use 路径，根据转换是否为环来确定路径的终止。

③对TEA 树中当前层的所有状态， 从T 中选择所有可执行的转换进行扩展， 对在扩展中出现在某逆向可判定转换前的末测试转换，视为待测转换。

④在TEA 树分支结束时记录找到的可执行测试子序列。

⑤所有的转换都测试完毕，算法结束。

5 结论

本文提出了一种新的基于EFSM 描述下协议的一致性测试序列生成方法，实现了控制流和数据流两方面的测试，我们在测试序列选择过程中使用了逆向可判定性来缩小转换可执行分析扩展空间，在TEA 树的扩展中记录了所有的def-use 对和对应的测试子序列。该方法在测试覆盖面和可执行性还有测试序列长度上具有明显优点，是一种行之有效的方法。在今后的工作中，我们会在实时性等方面做出优化和改进。

【参考文献】

[1] 孟凡淇. 协议一致性测试方法的研究. 信息与电脑. 软件开发与设计.2013.03:12-13.

[ 2 ] H u a n g C M , C h i a n g M S , J a n g M Y , U I O E : A P r o t o c o l T e s t S e q u n e n c e G e n e r a t i o n M e t h o d Using the Transition Executability Analysis(TEA)[J],Computer Communica tion,1998,21(16):1462-1475.

[3] 周晓煜，屈玉贵，赵保华. 利用逆向判定性缩短EFSM 的测试序列的长度. 通信学报.2000,21(11):48-55.

[4]Rapps S,Weyuker E J:Selecting S o f t w a r e T e s t D a t a T s i n g D a t a F l o w I n f o r m a t i o n [ J ] . I E E E T r a n s a c t i o n s o n S o f t w a r e Engineering,1985,11(4):367-375.