基于有限状态机的协议测试方法

时间:2022-04-10 11:48:31

基于有限状态机的协议测试方法

摘要:该文首先介绍了有限状态机的一般理论并描述了两种确定型有限状态机模型,之后将有限状态机模型引入通信系统中,并以GTP协议为例介绍了通信协议报文在GPRS网络中流转的过程及测试方法。

关键词:有限状态机;协议测试;通信系统

中图分类号:TP393 文献标识码:A 文章编号:1009-3044(2013)09-2161-05

在通信系统建模中,使用着各种类型的有限状态机,每个有限状态机都有一个状态集合(包括初始状态)和一个输入集合表,还有一个转化函数,它对每个由状态和输入条件构成的序列,指定了下一个状态。有限状态机作为经常使用的一个抽象机器模型,被广泛的使用在通信网络中,是一个进行系统建模的有力工具。

本文从有限状态机的一般理论出发,以GTP协议为例介绍和描述了有限状态机模型及基于它的协议测试方法。

1 确定型有限状态机

确定型的有限状态机是指针对一个可能的输入,只有一个状态的迁移,非确定的有限状态机是对每一个可能的输入可以有多个状态迁移,接收到输入时候从中多个状态转移中非确定的选择一个。

下面介绍它的两种模型。

1.1 带输出的有限状态机模型

一个有限状态机的形式化定义是这样:一个确定的有限状态机M:

S是一个有限的状态集合;

I是一个有限的输入字母表;

O是一个有限的输出字母表O;

一个状态转移函数f为每个状态和输入对指派一个新的状态;

一个输出函数g为每个状态和输入对指派一个输出,还有一个初始状态s0。

下面以一个状态图来进行说明:

有限状态机是抽象出来的一个数学模型,与现实世界比较,通过很多理想的假设来简化系统设计的复杂程度。比如,假设系统的几个状态是可以穷举的,即可以认为在行为上是固定的。当系统从一个状态通过条件变化迁移到另外一个状态,迁移是很迅速并且一次有效的。

为了建模的需要,人们开发了各种不同类型的有限状态机模型,主要应用的模型有Mealy状态机和Moore状态机。在Mealy状态机模型中,对一个转移都附加有输出动作,Moore 状态机对每一个状态都有附加输出动作。

1.2 不带输出的有限状态机

不带输出的有限状态机是用来作为识别语言而设计的。这些机器不产生输出,但是有终止状态。

一个有限状态机的形式化定义是这样:一个确定的有限状态机M:

S 是一个有限的状态集合;

I 是一个有限的输入字母表;

f是一个状态转移函数,为每个状态的输入对指派下一个状态;

s0 是一个初始装态;

F是一个由终结状态构成的S的子集。

不带输出的有限状态机可以用一个状态图来表示,在状态图中,终结状态用双圈表示。

前面讨论的有限状态机都是确定型的,因为对于每对状态和输入值,转移函数只给出唯一的下一个状态。而非确定有限状态机模型,它对每队输入和状态,有多个可能的下一个状态。

一个状态集合S,一个输入字母表I,一个转移函数f为每个状态和输入对指定下一个状态集合,一个初始状态s0,和一个由终结状态构成的S的子集F。

非确定型状态机和确定型状态机的唯一区别就是他们的转移函数不同,确定型有限状态机的输入只有一个状态的转移,非确定型状态机可以有多个状态转移。非确定型状态机可以转化成确定型状态机。

2 通信系统中的有限状态机

在GPRS网络中,同一个公众陆地移动网(Public Land Mobile-communication Network,以下简称PLMN)中的GPRS支持节点(GPRS Support Nodes,以下简称GSN)节点,比如GGSN节点和SGSN节点,都采用GTP协议进行数据传输,并采用GTP协议进行隧道管理。所谓隧道管理就是承载在GTP协议上的PDP(Packet Date Protocol)报文的激活、更新、分离等一系列的过程。PDP的管理也是GTP-C和GTP-U的一个重要功能。在GTP隧道管理中,系统之间的状态主要是在PDP上下文的创建、更新、删除等状态之间进行转移的。

在图3中,PDP上下文有ACTIVE,CREATE,UPDATE,DELETE,IDLE等五个状态,每个状态之间的迁移需要一定的条件。从IDLE状态不能直接迁移到DELETE,中间必须经过一个CREATE状态的转移,从CREATE状态也不能直接迁移到UPDATE状态,因为PDP报文的UPDATE动作是在PDP的传输隧道建立之后才能发送,而建立PDP 隧道是需要进行ACTIVE动作,同样的道理,从IDLE状态也不能直接迁移到UPDATE状态。

当测试系统开启之后,由于没有加载测试用例,系统处于IDLE状态,即空闲状态,此时没有测试用例通过TTCN-3系统来完成,如果在IDLE状态之后执行TTCN-3中的初始化动作,即创建主测试成分(Main Testing Component,以下简称MTC)、并行测试成分(Parallel Test Component,以下简称PTC)、测试端口、配置参数、连接测试系统和通信端口、连接各个测试端口和测试端口,那么此时系统状态则转移到CREATE,此时表明PDP报文初始化已经完成但是现在还没有被真正执行,条件RE_START/stInitCreate是指初始化发送序列的条件。

当系统处于CREATE状态时候,经过一个激活的操作过程,可以到达ACTIVE状态。由ACTIVE状态可以迁移到UPDATE状态,也可以由UPDATE状态迁移到ACTIVE状态。由ACTIVE状态也可以直接迁移到DELETE状态,这个代表系统激活了PDP报文,成功创建了PDP隧道,但是没有发送数据量,然后直接删除PDP隧道,直接退出测试系统。

下面分别将各个状态时候的系统状态进行描述一下。

2.1 CREATE状态

一个PDP的CREATE的过程是由IDLE过程迁移而来,CREATE的过程主要是创建并初始化通信端口,并把通信端口和测试系统通过MAP映射进行连接,或者是端口之间通过CONNECT操作连接。初始化的过程也包括一些常用协议的初始化操作,由于被测试系统是GGSN,GGSN的周边的接口有Gx,Gy,Gz,所以在CREATE的过程中,针对不同的测试端口需要进行不同的初始化操作,比如数据报文发送在Gx接口,与之相对应的是Gx接口上的DIAMETER协议,那么需要进行Gx接口的初始化并初始化DIAMETER协议的TTCN-3模板,在Gy接口上进行测试,需要初始化的是Gy接口,并初始化GTP’协议的TTCN-3模板,等。

由于在整个PDP上下文的传输过程中,传输分为GTP-C信令面和GTP-U用户面,所以在初始化操作里需要同时对GTP-C和GTP-U的TTCN-3模板进行初始化。

总体而言,一个CREATE过程中需要进行的主要的状态转移过程如下:

Step 1.初始化MTC,主要是运行在MTC上的一些通信端口参数;

Step 2.初始化Gi接口,因为Gi接口是GTP协议主要的通信接口,承载SGSN和GGSN之间的控制信令和用户信令的数据传输,所以第一个应该初始化并且探测Gi接口时候已经初始化成功,如果没有,则可以迁移到DELETE状态,表示初始化失败,清除原先操作。

Step 3.初始化DHCP(Dynamic Host Configuration Protocol)服务,进行动态域名配置,主要是把MS请求的APN名字转化成IP地址,并作动态分配;如果DHCP初始化成功,则迁移到step 4.否则,迁移到DELETE状态,表示初始化失败,清除原先操作。

Step 4.初始化RADIUS(Remote Authentication Dial In User Service)服务,如果RADIUS初始化成功,则迁移到step5,否则,迁移到DELETE状态,表示初始化失败,清除原先操作。

Step 5. 初始化Gz接口上CGF,并打开计费端口,否则迁移到step3,重新开始。

当以上步骤都完成后,PDP的运行环境由INIT迁移到ACTIVE状态,表示各种环境已经配置,可以发送GTP报文进行通信。

2.2 ACTIVE状态

如图4所示:

当PDP报文经过CREATE过程后,PDP的状态迁移到ACTIVE状态,ACTIVE表明现在已经初始化了PDP的运行环境并创建了PDP,现在PDP处于激活状态,可以通过通信端口发送数据报文。

由ACTIVE状态可以迁移到UPDATE状态,表明GTP-C协议在信令面成功创建PDP隧道之后,当PDP 上下文请求的Qos需要更改、GTP 信道发生变化、GTP的传输的版本由v0改变为v1时,由GSN中的节点SGSN发送更新PDP请求,此时如果GGSN反馈的是请求接受的消息,则测试行为成功迁移到UPDATE状态。

一个ACTIVE状态迁移到DELETE状态的原因有两点:一是因为一次成功的测试已经完成,PDP报文的GPT-C和GTP-U报文已经发送并且成功创建了测试环境,测试例正常完成后系统退出;二是因为经过ACTIVE过程PDP传输隧道成功创建之后,SGSN发送Delete PDP Context Request请求并被GGSN成功接受并反馈Delete PDP Context Response之后,系统状态迁移到DELETE。

由ACTIVE过程到GTPU_REBUILD状态并不是一个状态过程的迁移,在图中出现的原因是表明在PDP 隧道创建成功之后,对于同一个手机基站MS(Mobile Station)而言,在一个PDP隧道里面可以进行多次的GTP-U报文的传输,只要用称作为TEID的字段和NSAPI字段进行标识即可,这个也符合在GPRS网络中的电路交换原理,GTP协议把信令面和用户面进行了分离,即分离成GTP-C和GTP-U,一次信令面表明的是隧道建立,传输,释放等控制,但是在隧道中传输中采用用户面的GTP-U报文,做到了一次创建,多次使用。

2.3 UPDATE状态

UPDATE状态是由ACTIVE状态转移过来,ACTIVE状态是进入UPDATE状态的唯一前趋状态,PDP报文只有在成功发送了ACTVIE激活流程之后才能进行更新操作,DELETE是UPDATE状态的唯一后趋状态,表明在经过UPDATE状态之后,系统运行测试用例结束,通过DELETE状态清除原先的配置操作,归还请求的处理机请求并释放资源。

UPDATE的过程主要是由SGSN发送Update PDP Context Request 并且GGSN发送Update PDP Context Response响应消息,表明MS请求的PDP更新请求得到GGSN的同意,然后可以进行数据量的传输,在传输数据信息的过程中,采用的是GTP-U协议。

2.3 DELETE状态

进入DELETE的状态主要是做系统清理工作,比如关闭在通信过程中的测试端口,关闭SACC(Service Aware Charging and Control),关闭DHCP通信连接,关闭RADIUS的通信连接,等等。其主要过程可以用图6状态图来表示。

3 结束语

本文介绍了有限状态机的基本概念和相关理论,主要分析了有限状态机中的确定性有限状态机,结合实例说明了确定性有限状态机的两种理论模型,即带输出的有限状态机模型和不带输出的有限状态机模型,并根据有限状态机的状态迁移图来讲述了在一个GTP报文从INIT状态,经过ACTIVE、UPDATE、DELETE状态,最后退出到IDLE状态的各个过程以及在各个状态转换中进行测试的方法。

参考文献:

[1] Myers G J.The art of software of testing[M].New Jersey:John Wiley and Sons,2004.

[2] Hopcroft J E,Motwani R,Ullman J D.Introduction to Automata Theory, Languages and Computation[M].2nd ed.Addison-Wesley,2001.

[3] Hoare C A municating Sequential Processes[J].Communications of the ACM,1978,21(8).

[4] Kwang Ting Cheng,Krishnakumar A S.Automatic functional test generation using the extended finite state machine model[C]. New York, NY, USA:DAC'93 Proceedings of the 30th international Design Automation Conference ACM,1993: 86-91.

[5] ETSI ES 201 873-1 v2.2.1.Methods for Testing and Specification (MTS);The Testing and Test Control Notation version 3;Part1:TTCN-3 Core Language,27-28[S].2003.

[6] Newkirk J W,Vorontsov A A.Test-Driven,Developmentment in Microsoft .NET[M].Microsoft Press,2004.

[7] Astels D.Test-Driven Developmentment:A practical Guide[M]. Prentice Hall,2003.

上一篇:信息技术网络考试系统的研究与设计 下一篇:以项目实践提升计算机专业学生的综合能力