基于通讯多端口有限状态机的协议互操作性测试生成方法

摘要

基于通讯多端口有限状态机的协议互操作性测试生成方法属于网络协议测试技术领域，其特征在于所述方法依次含有以下步骤：把协议系统规范描述为一个通讯多端口有限状态机模型，并用基于单激励原则的互操作性测试生成技术生成抽象测试集1；计算测试集1的错误覆盖度，必要时用所述增强测试生成方法生成错误覆盖度更高的抽象测试集2；根据实际测试场景确定分布式测试架构；把测试集2分布到各测试部件上时，通过在测试序列中添加测试部件间的协调消息的方法以解决控制观察问题，得到抽象测试集3；进一步可将其转化为实际的测试脚本。本发明适用于各种不同的分布式测试架构，具有一定的通用性。

主权项

1、基于通讯多端口有限状态机的协议互操作性测试生成方法，其特征在于，所述方法是在网络操作环境中对一个由不同的网络设备构成的互操作性被测系统依次按以下步骤实现的：步骤1：在计算机中，把互操作性被测试系统规范描述为一个通讯多端口有限状态机模型Ms：设：在所述的一个互操作性被测试系统中包含两个或多个协议实体，而各协议实体的规范是已知的；则：所述互操作性被测试系统用一个通讯多端口有限状态机来描述，该通讯多端口有限状态机是m个组件状态机的集合，用Ms表示，Ms＝{M1，M2，…，Mm}；各组件状态机用于描述各协议实体的规范，同时定义了各组件状态机间的端口映射关系，用该关系描述所述被测试系统的网络拓扑；组件状态机用Mi表示，i＝1，2，…，m，Mi是一个包含n个端口的多端口有限状态机，其端口分别编号为1～n，Mi是一个八元组，Mi＝(S，I，O，δ，λ，s0，Q，R)：●S是Mi的有限状态集合，s0∈S是Mi的初始状态；●I＝(I1，I2，…Ik，…，In)，其中Ik是端口k上的输入符号的集合，k＝1，2，…，n；a∈Ik可记作k:a；I＝I1∪I2∪…∪Ik∪…∪In是Mi所有输入符号的集合；●O＝(O1，O2，…，Ok，…，On)，其中Ok是端口k上的输出符号的集合，k＝1，2，…，n；b∈Ok可记作k:b；O＝O1∪O2∪…∪Ok∪…∪On是Mi的所有输出符号的集合；●δ是状态变迁函数：δ：S×I→S，其中→表示映射关系；λ是输出函数：λ：S×I→O，其中→表示映射关系；一条变迁t可表示为(s1，in/out，s2)或$s_1\stackrel{\mathrm{in}/\mathrm{out}}{\to }{s}_2,$其中s1，s2∈S，in∈I，out∈O并且δ(s1，in)＝s2，λ(s1，in)＝out；所有变迁集合记为T；●Q＝(Q1，Q2，…Qk，…，Qn)，其中Qk是端口k的输入队列，k＝1，2，…，n；这些队列都是先进先出FIFO队列；●R＝(R1，R2，…，Rn)表示端口映射关系，其中Rk是端口k的端口映射关系，k＝1，2，…，n，其形式为1)Mj:h，其中j≠i，表示Mi的端口k连接到Mi的端口h；或2)env，表示Mi的端口k与外部环境相连；将与外部环境连接的端口称为“外部端口”，与其它组件状态机通讯的端口称为“内部端口”；与外部环境交换的输入或输出称为外部输入或输出，不同组件状态机之间交换的输入或输出称为内部输入或输出；步骤2：采用基于单激励原则的互操作性测试生成技术生成抽象测试集1，依次按以下步骤进行：对于如前所述的被测试系统规范模型Ms，如果各组件状态机Mi的当前状态分别为si，i＝1，2，…，m，则Ms的全局状态可表示为向量(s1，s2，…，sm)，而Ms的初始全局状态则为(s10，s20，...，sm0)，其中si0为Mi的初始状态，i＝1，2，…，m；与全局状态相对应，各组件状态机的状态称为局部状态；稳定全局状态指的是，在这些全局状态下，如果不从环境施加外部输入，则状态不会发生变化；与此相反，其它状态则称为暂时全局状态；稳定全局状态之间的变迁称为全局变迁，即在某个稳定全局状态下，施加一个外部输入，系统中各组件状态机所经历的变迁按时序组成一条全局变迁；与此相对应，每个组件状态机中的变迁称为局部变迁；步骤2.1采用基于广度优先搜索的方法，生成所有测试主体和所有稳定全局状态的前导测试步，即由初始全局状态到该全局状态的一个测试序列：设一个全局状态的队列为To_extend，一个全局状态集合为Extended，则(1)初始化过程：清空To_extend和Extended；(2)将初始全局状态(s10，s20，…，sn0)从队尾压入队列To_extend；(3)如果队列To_extend不空，则执行(4)～(8)步；如果队列To_extend为空，则停止；(4)从队列To_extend的队首取出一个全局状态，记作gs；(5)如果gs属于集合Extended，则转到第(3)步；(6)将gs加入到集合Extended中；(7)将gs设置为系统Ms的当前全局状态，对于所有可能的外部输入ein，执行以下步骤：(7.1)计算Ms在全局状态gs下，施加外部输入ein形成的全局变迁，记作gt；同时计算出Ms的新的全局状态，记作new_gs；(a)设置gt为ein，并且设置输入符号in为ein；(b)在Ms上施加输入in，得到输出，记作out，在gt末尾附加out；同时更新Ms全局状态；(c)得到out所在端口，记作P1；跟据端口映射关系，得到其映射端口P2；(d)如果P2为外部环境env，则步骤(7.1)执行完毕，记录gt，并记录Ms的新的全局状态new_gs；(e)否则设置in为out，转到(b)；(7.2)将gt作为一个测试主体记录下来；(7.3)如果new_gs不属于集合Extended，则(a)求取new_gs的前导测试步：new_gs的前导测试步为gs的前导测试步附加上gt；(b)记录new_gs的前导测试步；(c)将new_gs从队尾压入队列To_extend；(8)转到第(3)步；步骤2.2将测试主体和前导测试步组装为互操作性测试例：(1)对于所有测试主体，执行以下步骤：(1.1)得到该测试主体的初始全局状态，记作gs；(1.2)得到gs的前导测试步；(1.3)将测试主体附加到gs的前导测试步之后，即得到一个测试例；(2)所有测试例即组成抽象测试集1；步骤3：对步骤2生成的测试集1进行错误覆盖度分析，依次按以下步骤进行：步骤3.1生成错误模型：模型的可能错误有输出错误和变迁错误两类；在所述系统规范的某个组件状态机Mi中选择一条变迁tr，改变该变迁的末状态或输出，得到错误变迁ftr，在Mi中用ftr代替tr，即可得到一个单一错误模型，记作Ms(Mi·tr，Mi·ftr)；步骤3.2生成所述被测试系统中所有的单一错误模型，相应的集合记为Impl(Ms)；步骤3.3在所述Impl(Ms)的每个模型上模拟执行从步骤2得到的抽象测试集1，施加外部输入，检查输出是否与预期相同，如果不同，则表明抽象测试集1中的相应测试例无法通过，测试集1能够检测出模型错误；步骤3.4采用下述公式计算所述测试集1的错误覆盖度：$\mathrm{FC}(\mathrm{Ms},\mathrm{IOTS})=\frac{\mathrm{Nt}\left(\mathrm{Ms}\right)-\mathrm{Np}(\mathrm{Ms},\mathrm{IOTS})}{\mathrm{Nt}\left(\mathrm{Ms}\right)}$其中，Nt(Ms)为所述Impl(Ms)中错误实现状态机的总数；IOTS是给定的所述测试集1；Np(Ms，IOTS)为Impl(Ms)中能够通过所述测试集1的错误实现的数目，由步骤3.3可计算出；步骤4：若步骤3得到的错误覆盖度达不到设定值，则依次按照以下步骤采用增强的测试生成方法生成覆盖度更高的抽象测试集2：对于每个变迁错误模型，执行步骤4.1～步骤4.2：步骤4.1依次模拟执行每个测试例，如果测试例包含变迁错误但又无法检测出该错误，则将其记录下来，作为备选；步骤4.2在步骤4.1所记录下来的多个测试例中，选择长度最小的一个测试例；如果只有一个测试例，则选择该测试例即可；对该测试例添加末状态验证序列，得到一个新的测试例，其步骤依次如下：设定：错误模型Ms(Mi·tr，Mi·ftr)，其错误位于组件状态机Mi中；长度最小的测试例为tck；(1)计算系统规范Ms在执行完测试例tck后的全局末状态，记作end_gs(Ms，tck)，从而得到Mi的局部状态，记作local_statei(end_gs(Ms，tck))；(2)这时只需验证Mi的局部状态是否为local_statei(end_gs(Ms，tck))即可，采用下述后继树的方法求取末状态验证序列：后继树的根节点标记为初始情况下Mi的所有可能局部状态集合，从该节点出发添加各条分枝，每个分枝分别标记为可能的外部输入，根据施加该外部输入后系统可能的可观察行为，对初始状态集合进行划分；继续上述过程，直到被验证局部状态local_statei(end_gs(Ms，tck))被划分为单元素集合；状态验证序列即为从根节点到被验证状态单元素集合节点路径上的变迁序列，如果有多个满足条件的变迁序列，则从中挑选出长度最短的一条，即包含的局部变迁数最少的一条，作为所求的末状态验证序列，记作DS(end_gs(Ms，tck)，Mi)；(3)由测试例tck扩展得到的新测试例则为tck·DS(end_gs(Ms，tck)，Mi)，即在tck后面添加末状态验证序列DS(end_gs(Ms，tck)，Mi)；步骤4.3用所有的从步骤4.1～步骤4.2得到的新生成的测试例替代测试集1中对应的原测试例，得到新的抽象测试集2；步骤5：根据实际的测试场景确定分布式测试架构；所述分布式测试架构包括：若干测试部件和对于被测试系统的若干访问点：每个测试部件包含一个或多个对被测系统的访问点，测试部件的作用是执行测试例中与其包含的访问点相关的测试行为；所述访问点包括控制观察点PCO和观察点PO两类：控制观察点PCO用于控制和观察被测实现IUT外部端口上的外部行为，而观察点PO则没有控制功能，只用于观察IUT之间的交互；测试部件分为两类：主测试部件MTC和从测试部件PTC，从测试部件用于控制包含其中的访问点，而主测试部件则用于创建其它四个并行测试部件，并计算测试例的全局判决，所有测试部件可通过一个通讯通道进行相互之间的通讯；步骤6：把测试集2分布到各测试部件上，最终生成分布式同步测试序列，得到抽象测试集3：测试集2中的每个测试例可表示为一个全局变迁的序列，设一个测试例tck＝Gt1·Gt2·…·GtL，其中Gti＝Lti_1·Lti_2·…·Lti_li，i＝1，2，…，L，li是全局变迁Gti所包含的局部变迁的数目，Lti_j表示各局部变迁，j＝1，2，…，li；相应的分布式测试架构包含n个测试部件TC1，TC2，…，TCn，每个测试部件中包含若干访问点PCO或PO；设分布式同步测试序列为DTS(TCi)，i＝1，2，…，n，分别表示分布到各测试部件上的测试序列；则：步骤6.1将各DTS(TCi)初始化为空序列，i＝1，2，…，n；步骤6.2对于测试例中的每个全局变迁，依次执行以下步骤：(1)得到该全局变迁的外部输入所对应的访问点及其所在测试部件，分别记作ePCO和TCh；(2)如果该全局变迁不是测试例中的第一个全局变迁，则：如果ePCO与上一个相邻全局变迁的最后一个输出所对应的访问点不同，则(a)得到上一个相邻全局变迁的最后一个输出所对应的访问点所在的测试部件，记作TCk；(b)在DTS(TCk)中添加一个协调消息发送事件，记作！CM(TCk→TCh)，表示从测试部件TCk向TCh发送一个协调消息；(c)在DTS(TCh)中添加一个协调消息接收事件，记作 CM(TCk→TCh)；(3)得到由该全局变迁引发的输出所对应的所有访问点，对于每个访问点：(a)得到该访问点所在的测试部件TCk’；(b)如果TCk’与TCh不同，则在DTS(TCh)中添加一个协调消息发送事件，记作！CM(TCh→TCk’)；在DTS(TCk’)中添加一个协调消息接收事件，记作 CM(TCh→TCk’)；(4)在DTS(TCh)中添加该全局变迁的外部输入事件；(5)对于每个输出动作，在相应的测试部件的测试序列中添加该输出事件；步骤6.3对于测试集2中的每一个测试例，执行步骤6.1和6.2，得到相应的分布式同步测试例，所有这些测试例组成测试集3；步骤7：把步骤6所得到的抽象测试集3通过自动或人工的方式转换为实际的测试脚本，可在前述分布式测试架构上实际执行。