协议一致性测试用例生成模型研究

齐建业，李 强，余 祥

（电子工程学院，安徽 合肥230037）

0 引 言

对协议进行一致性测试，通过有限状态机（finite state machine，FSM）对协议标准文本描述进行形式化分析，由于主观上的理解可能会在建模中产生偏差，影响后续测试用例的生成。利用FSM 直接描述协议标准文本，转化过程比较抽象，要求相对较高。由于UML 具有交互性强、直观生动的特点，可以通过UML 图自动生成软件测试用例［1］。因此，可以采用UML 中的活动图对被测协议标准的功能说明进行描述，进而生成协议一致性测试的测试用例。

本文建立了协议一致性测试用例生成模型，由形式化活动图、扩展有限状态机和算法FADToEFSM 组成。通过形式化定义UML 活动图，可以将由自然语言描述的任意的协议标准文本转化为形式化的活动图，降低了协议形式化分析的复杂程度。设计FADToEFSM 算法将形式化的活动图转化为扩展有限状态机（extended finite state machine，EFSM），将EFSM 再转化为测试用例，上述两个转化过程按照数学运算，消除了协议一致性测试覆盖的不完备问题。根据实际被测的协议实现产品说明实例化测试数据，生成协议一致性测试用例。

1 相关概念

1.1 形式化活动图

活动图是UML模型中用于对系统的动态行为建模的一种图形工具，它或是对活动的序列进行描述，或是描述对活动控制转化进行描述。UML 对动态语义的描述不是十分清楚，例如一个活动图的节点可以描述事件、退出、入口以及执行等4 种动作，具体是哪一种动作，不清楚。因此，对活动图模型中若干图形元素的语义和语法进行形式化。

定义1 形式化活动图（formal activity diagram，FAD）［2］

通过图像来描述协议实现之间的数据包交互关系：

FAD＝＜ID，Start，End，SA，IN，OUT，Judge，FL，Con＞

（1）标识ID：唯一地标识一个FAD；

（2）系统动作SA：描述数据包生成；

（3）输出动作OUT：描述数据包发送；

（4）输入动作IN：描述数据包捕获；

（5）起始端点Start：描述FAD 的开始状态，即START 事件，限定一个FAD 只有一个起始点；

（6）结束端点End：描述FAD 的终结状态，即CLOSURE事件，限定一个FAD 只有一个结束点；

（7）判断框Judge：作为一种条件判断，描述一个或者几个进口点、出口点；

（8）连线FL：描述FAD 中两个节点之间的控制流线条；

（9）联系点Con：作为连线的连接部分，可以有一条或多条连线进入，限定只有一个连线出口。

1.2 扩展有限状态机

定义2 扩展的有限状态机（EFSM）［2］

扩展有限状态机EFSM 用五元组来表示：EFSM＝（S，s0，sF，T，δ）。扩展有限状态机将形式化活动图转换为转移事件集合以及状态集合。集合元素的唯一性，使得用同一语义的转移事件或状态时，使用唯一的定义，从而避免了语义矛盾的产生。

2 FAD 转换EFSM 算法

根据EFSM 的定义，设计从FAD到EFSM 的转换原则：

（1）将起始端点转换为开始状态s0；

（2）将系统动作转换为EFSM 中的一个事件状态和一个系统转移Trig＿SystemAction＿Num；

（3）将输入动作转换为一个空伪状态St＿Empty＿Num 和一个输入转移；

（4）将输出动作转换为EFSM 中的一个输出状态和一个自动转移Trig＿Automation；

（5）将判断框转换为在EFSM 中增加一个St＿Fork－Join＿Num，根据出口判断增加Trig＿Constraint＿Num 和空伪状态St＿Empty＿Num；

（6）连接点只起到两条流线之间的传递作用，没有状态转化；

（7）将结束点转化为结束状态sF。

根据上述转换规则，设计了将FAD 转换为EFSM 的算法。

算法：EFSM 自动生成produceEFSMFromFAD （fad）

算法原理：将形式化活动图中的图元按照从初始点到结束点的顺序添加到EFSM 中。如果EFSM 中没有则增加一个新状态，同时添加一个转移事件；如果扩展有限状态机中已经有相应图元转化的状态，那么只增加一个转移事件；如果是连接点，不转化，检查并转化下一个图元。

输入：FAD

输出：EFSM

算法步骤：

（1）新建一个EFSM 类的对象efsm；

（2）将开始状态s0添加到efsm；

（3）调用局部函数constructEFSM（StartObj，efsm）将FAD分解为EFSM片段；

（4）调用局部函数AddtoEFSM（NextObj，StartObj，efsm）将分解的EFSM 片段添加到扩展有限状态机中；

（5）从结束状态中删除不符合定义的状态；

（6）返回efsm。

其中，局部函数constructEFSM（StartObj，efsm）是一个递归函数，它的作用是将FAD 中图元分解为EFSM 片段，按照图元类型和转换规则将FAD 中起始点和结束点转化为EFSM 中的初始状态和结束状态，将系统动作转化为EFSM 中的事件状态和系统转移，将输入操作转化为EFSM 中的一个输入转移和空伪状态，将输出操作转化为EFSM 中的自动转移和输出状态，将判定框转化为EFSM 中的连接复合伪状态，根据出口增加条件转移和空伪状态。constructEFSM（StartObj，efsm）中定义了递归函数AddtoEFSM（NextObj，StartObj，efsm），它的作用是将由FAD片段转换生成的EFSM 片段添加到扩展有限状态机中。

3 测试用例生成

测试用例生成是根据扩展有限状态机转化为测试序列，然后对测试序列进行实例化。其中，从EFSM 生成测试序列就是要找出所有从初始状态到结束状态的可行序列；实例化测试序列即是对EFSM 中包含的数据进行实例化，生成执行的测试用例。

3.1 测试序列生成

测试序列是EFSM 中的所有状态序列集合。根据有向图的广度优先搜索算法将EFSM 转换为测试序列。

算法：从扩展有限状态机构造一个测试序列集合produceTPS

算法原理：新建一条测试序列，从EFSM 的初始状态s0开始，对扩展有限状态机中的状态和转移进行遍历，添加到测试序列中。测试序列按照分支判定的数目划分为相应的若干测试序列，遇到扩展有限状态机中的结束状态sF结束遍历［3］。

输入：efsm输出：测试序列集合TPS：tps＝｛tp1，tp2，…tpn｝算法步骤：

（1）新建测试序列tp，并将efsm 的开始状态s0加入到tp中；

（2）将新建序列加入到测试序列集合中；

（3）调用局部函数contructTP 将遍历的状态添加到测试序列中；

（4）去除测试序列集合中的每一条序列的空状态；

（5）返回tps；

其中，局部函数contructTP 是一个递归函数，它的作用是将当前遍历到的状态补充到当前序列中，并更新测试序列集合。

算法produceTPS采用广度优先搜索算法，对EFSM 中的状态和转移进行遍历，在最差的情形下，必须寻找到所有可能节点的所有序列，因此其时间复杂度为O（n＋e），其中n 是EFSM 中的状态节点数目，e是EFSM 中的连线数目。

3.2 实例化测试序列

对测试序列实例化，是对由EFSM 生成的测试序列中的测试数据进行实例化，生成有效的测试用例。对测试数据实例化，是对测试过程中的数据包字段数值通过边界值分析［4］和等价类划分［5］的方法进行赋值。

边界值分析法对字段数值域的最大值、最小值、范围内任意值、较小于最大值、较小于最小值、较大于最大值、较大于最小值根据协议标准文本描述来分别设计测试用例。等价类划分法将字段数值域划分为无效等价类和有效等价类，在每一个等价类中再根据边界值分析法设计一个测试数据。

以测试字段 “会话标识”为例设计一组测试用例进行说明，按照协议标准规定其类型为数字，大小为2B，划分有效等价类为（0，0xFFFF］。

（1）利用边界值法，设计如下字段数值：

字段数值取值1：0xFFFF（上界）

字段数值取值2：0（下界）

（2）利用等价类划分法，设计如下测试用例：

字段数值取值3：－1（不符合协议标准）

字段数值取值4：0x10000（不符合协议标准）

字段数值取值5：＃￥%＆＊＠（非数字字符）

字段数值取值6：空 （即数据包中没有 “消息长度”这个字段）

（3）根据数据包的实际长度，为其赋予1 个正确的数值。

因此，为字段 “会话标识”设计总计7个测试用例。

4 算法分析与比较

以测试IKE协议为例，从测试序列生成、测试序列错误覆盖度、测试用例测试覆盖和测试用例执行效率，对测试序列生成算法produceTPS与UIO 方法［6］、BUIO 方法［7］进行分析比较。具体地讲就是，对测试序列生成算法produceTPS与UIO 方法、BUIO 方法从测试序列生成和测试序列错误覆盖度进行分析比较；对测试用例生成算法produceTC与文献［8－11］，从测试用例测试覆盖和测试用例执行效率进行分析比较。

4.1 测试序列生成和错误覆盖度分析

（1）测试序列生成分析

测试序列的长度及其错误覆盖度决定了测试序列生成算法的优劣。其中，测试序列的长度决定了测试过程的工作时间，测试每个状态转换的可用测试序列，其长度等于可用测试序列中的状态个数；错误覆盖度表征了测试序列的检错能力和可信赖程度。

以测试IKE协议主模式客户端预共享验证方式为例，UIO 方法生成的测试序列长度最长为39，BUIO 方法生成的测试序列长度最长为22［12］；produceTPS 算法生成的测试序列长度最长为11，缩短比例分别为71.79%和50%。

在EFSM 中，通过produceTPS算法生成的每个状态的可用测试序列见表1。

则produceTPS算法生成的可用测试序列T1～T8长度与UIO 方法和BUIO 方法生成的可用测试序列长度［10］对比如图1所示。

图1 测试序列长度

由图1可见，对每个状态转换的可用测试序列长度来说，produceTPS算法比UIO 算法短，比BUIO 算法长。测试用例中的测试步骤由测试序列的长度决定，因此produceTPS算法优于UIO 方法；produceTPS 算法之所以比BUIO 方法生成测试序列长，是因为BUIO 方法在生成测试序列的过程中，没有考虑到构造数据包的状态，因此通过BUIO 方法生成的测试序列来进一步设计与生成测试用例，需要主观上对抽象测试序列的理解。测试数据包的构造在测试用例中是一项重要环节，produceTPS算法添加了构造数据包的状态，就可以通过测试序列自动生成测试用例，使得测试用例描述的测试过程更加完整和清楚，更容易进行测试执行，可以减少后期工作量。

表1 可用测试序列

（2）错误覆盖度分析比较

UIO 方法和BUIO 方法都是以UIO 序列为特征序列来验证每次转换的末状态，对FSM 中的所有转换进行了遍历，其错误覆盖度都超过99%［12］。而produceTPS算法基于有向图的广度优先搜索算法，也是对FSM 中的所有转换进行了遍历，并且严格遵循关键子句逻辑覆盖准则，因此其错误覆盖度与UIO 方法和BUIO 方法相近，都超过99%。但是UIO 方法和BUIO 方法基于的FSM 没有完全形式化，不同转换的末状态可能是同一个状态（如自转移），所以在形式化描述上UIO 方法和BUIO 方法不如produceTPS算法。

4.2 测试用例测试覆盖和测试用例执行效率分析比较

测试用例测试覆盖分析比较

设计与生成的测试用例应覆盖被测协议标准的所有功能点，颗粒度划分适当，没有冗余。测试数据应遵循错误覆盖准则，生成的测试用例既包括测试行为与测试数据正确的测试用例，也包括测试行为与测试数据不正确的测试用例。

通过测试用例生成算法produceTC设计IPsec协议测试集，对字段数值采用等价类划分和边界值分析法相结合的方式进行赋值。IPsec协议包括3个子协议：IKE 协议、认证头协议AH 和封装安全载荷协议ESP。

采用等价类划分和边界值分析法为IPsec每个协议设计一个测试集，见表2。每个测试集包含若干测试项，分为有效等价类划分项和无效等价类划分项；再根据测试项设计相应的有效等价类测试用例和无效等价类测试用例。

表2 IPsec协议测试集

将表2设计的IPsec协议测试集与已有的IPsec协议测试集［8－11］进行对比分析。各文献中设计的测试用例数如图2所示。

图2 测试集比较

对图2中的数据进行对比分析如下：

（1）由可知，对于IKE 协议，文献［8－10］中并没有为其设计测试用例；文献［11］中没有对AH 协议和ESP协议设计测试用例。由于ESP 协议、AH 协议和IKE 协议是IPsec协议的重要组成部分，其中任意一个协议的测试用例缺失对于整个IPsec协议测试集来说都是不完备的。

（2）对于文献［8－10］中设计的AH 和ESP 协议测试用例集，并没有给出具体的测试用例设计过程，因此不方便对比分析。

（3）文献［11］有91个IKE 协议测试用例，有45个功能性测试用例和46个行为性测试用例，并且行为测试用例中没有覆盖不正确行为的测试用例。由于IKE 协议中的功能测试用例和行为测试用例可结合进行［11］，重复设计导致测试用例冗余。

（4）本文针对IKE、AH、ESP协议分别进行了测试用例设计，如所示，共设计1785个测试用例。进行测试用例设计时，通过边界值原则和等价类划分原则设计字段数值生成测试用例，可以尽量避免冗余测试用例的产生。

因此根据以上分析可知，本文设计的协议测试集比现有的测试集在测试覆盖度方面更全面。

测试用例的执行效率分析

文献［8－10］中，未涉及IKE 测试集，文献［11］利用UIO 算法为IKE 协议设计了正确的行为测试用例。论文采用produceTPS算法生成测试序列，与UIO 算法相比，减少了测试序列的平均长度。因此本文在设计测试用例时，是利用produceTPS算法生成的较短测试序列上进行的，生成的测试用例中包含测试步骤更少，执行时测试效率更高。

5 结束语

在协议的一致性测试中，通过测试用例指导测试执行。本文提出一种基于形式化活动图和扩展有限状态机的协议一致性测试用例生成模型，利用FAD 对协议标准中说明的协议功能描述进行形式化建模，设计算法将FAD 转换为EFSM 自动生成测试用例。通过一个实例与已有的测试序列生成算法进行对比分析，结果表明在测试序列、测试序列错误覆盖度、测试用例测试覆盖和测试用例执行效率均具有一定的优越性。

［1］TONG Yi，DONG Bidan.Test cases automatic generation from UML state diagram ［J］.Microcomputer Information，2011，27 （9）：201－203 （in Chinese）. ［佟轶，董碧丹.UML 状态图的测试用例自动生成 ［J］.微计算机信息，2011，27 （9）：201－203.］

［2］QI Jianye，LI Qiang，YU Xiang.Research on test case generation using formal activity diagram of protocol conformance testing ［J］.Journal of Anhui University （Natural Science Edition），2013，37 （3）：75－80 （in Chinese）. ［齐建业，李强，余祥.基于形式活动图的协议一致性测试用例生成方法研究［J］.安徽大学学报 （自然科学版），2013，37 （3）：75－80.］

［3］YU Xiang，LI Qiang，QI Jianye.A research on automated software test case generation based on control flow ［J］.Journal of Inner Mongolia University （Natural Science Edition），2011，42 （5）：521－527 （in Chinese）. ［余祥，李强，齐建业.基于控制流程的软件测试用例自动生成方法研究 ［J］.内蒙古大学学报 （自然科学版），2011，42 （5）：521－527.］

［4］LIU Chunling，LEI Haihong.Design method of black－box testing case ［J］. Modern Electronics Technique，2012，33（20）：46－48 （in Chinese）.［刘春玲，雷海红.黑盒测试用例设计方法研究 ［J］.现代电子技术，2012，33 （20）：46－48.］

［5］GUO Xi，ZHANG Huanguo.Approach for reduced test suite generation based on predicate abstraction ［J］.Journal on Communications，2012，33 （3）：35－43 （in Chinese）. ［郭曦，张焕国.基于谓词抽象的测试用例约减生成方法 ［J］.通信学报，2012，33 （3）：35－43.］

［6］Gu Juan，Yuan Dongming，Hu Hefei，et al.An improved method based on UIOv for test sequence generation ［C］／／IEEE 14th International Conference on Communication Technology，2012：573－577.

［7］GAO Zhanchun，HU Xiaoling，JIANG Yanjun，et al.Research on BUIO generation and test sequences generation algorithms［J］.Computer Engineer and Applications，2011，47（6）：116－118 （in Chinese）.［高占春，胡晓玲，蒋砚军，等.BUIO 生成及测试序列生成算法研究 ［J］.计算机工程与应用，2011，47 （6）：116－118.］

［8］TIAN Jun.Research on IPv6protocol conformance test and implementation of the test system ［D］.Beijing：Institute of Computing Technology Chinese Academy of Sciences，2001（in Chinese）.［田军.IPv6协议一致性测试研究及测试系统实现 ［D］.北京：中国科学院计算技术研究所，2001.］

［9］ZHENG Hongxia.A test case design method for IPv6protocol conformance testing ［D］.Beijing：Institute of Computing Technology Chinese Academy of Sciences，2003 （in Chinese）.［郑红霞.IPv6协议一致性测试例设计方法 ［D］.北京：中国科学院计算技术研究所，2003.］

［10］LV Chao.Research on the design of IPSec protocol confor－mance testing system ［D］.Hefei：University of Science and Technology of China，2005 （in Chinese）.［吕超.IPSec协议一致性测试系统的设计研究［D］.合肥：中国科学技术大学，2005.］

［11］WANG Wenjuan.Research on the test suite generation for security protocol［D］.Zhengzhou：The PLA Information Engineering University，2009 （in Chinese）. ［王文娟.安全协议测试集生成技术研究 ［D］.郑州：解放军信息工程大学，2009.］

［12］MA Yan.Research on optimizing test techonolgy of IPSec protocol［D］.Zhengzhou：The PLA Information Enginee－ring University，2010 （in Chinese）.［马艳.IPSec协议测试优化技术研究 ［D］.郑州：解放军信息工程大学，2010.］