| 主权项 |
一种基于变量依赖的并行扩展有限状态机的协议测试生成方法，其特征在于，所述方法是在网络操作环境中对于一个被测试的网络设备依次执行以下步骤实现的：步骤1：在计算机中，把被测试的网络设备的协议规范描述为一个并行扩展有限状态机模型Ms；步骤2：采用忽略变量依赖的扩展有限状态机测试生成技术生成组件状态机抽象测试集；步骤3：针对外部变量，生成可执行化外部前导序列；步骤4：采用链接外部前导序列的方法对组件状态机抽象测试集进行可执行化处理；步骤5：生成关于外部变量的跨状态机抽象测试集；步骤6：将经过步骤4处理的组件状态机抽象测试集与步骤5生成的跨状态机抽象测试集合并，删除重复或被包含的测试序列，得到协议状态机的抽象测试集；其中，步骤1具体为：设：在所述被测试的网络设备中包含一个或多个协议，各协议包含一个或多个可并行工作的进程，各协议的规范是已知的；则：将所述被测试的网络设备用一个并行扩展有限状态机模型来描述，所述并行扩展有限状态机模型是n个组件状态机的集合，用Ms表示，Ms={M1,M2，…,Mn}；各组件状态机用于描述各协议进程的规范，所述组件状态机用Mi表示，i=0,1,…,n，Mi是一个八元组，Mi=(S,s0,VI,VE,I,O,TR,T)：其中，S是Mi的有限状态集合；s0∈S，是Mi的初始状态；VI=(Vi1,Vi2,…Vik,…,Vin)，其中Vik是所有定义与使用均在Mi内部 的变量，称为内部变量，k=1,2,…,n，n为正整数，VI是Mi所有内部变量的集合；VE=(Ve1,Ve2,…Vek,…,Ven)，其中Vek是所有定义在Mi外部，但是在Mi内部被使用的变量，称为外部变量，k=1,2,…,n，n为正整数，VE是Mi所有外部变量的集合；I=(I1,I2,…Ik,…,In)，其中Ik是Mi的一个输入符号，k=1,2,…,n，n为正整数，I是Mi所有输入符号的集合，I为非空集合；O=(O1,O2,…Ok,…,On)，其中Ok是Mi的一个输出符号，k=1,2,…,n，n为正整数，O是Mi所有输出符号的集合，O为非空集合；TR=(TR1,TR2,…TRk,…,TRn)，其中TRk是Mi的一个时钟，k=1,2,…,n，n为正整数，TRk能够被Mi的任意变迁读取，TR是Mi所有时钟的集合；T=(T1,T2,…Tk,…,Tn)是Mi所有变迁的集合，T为非空集合，其中Tk是Mi的一个变迁，k=1,2,…,n，n为正整数，Tk是一个六元组，Tk=(sstart,send,Ik,Ok,P,A)：其中，sstart∈S，是Tk的初始状态；send∈S，是Tk的末状态；Ik∈I，是Tk的输入符号；Ok∈O，是Tk的输出符号；P是关于VI中的内部变量、VE中的外部变量、输入Ik、一些常量和时钟超时事件的谓词表达式；A是Tk执行时的行为序列，A包括变量赋值行为、输出行为以及时钟创建行为中的一项或多项，A中的行为顺序执行；其中，步骤2依次按以下步骤执行：设两个全局组件状态机的集合分别为To_be_generated和Generated，每个组件状态机有一个对应的测试例集合TSi，i=1,2,…,n， 则步骤2.1、初始化过程：清空To_be_generated和Generated；步骤2.2、将所有组件状态机M1,M2,…,Mn放入集合To_be_generated；步骤2.3、如果集合To_be_generated不为空，则执行步骤2.4～2.10；否则停止；步骤2.4、从集合To_be_generated中取出一个组件状态机，记作Mi；步骤2.5、对Mi执行以下步骤：(1)找出Mi的每条变迁中的所有内部变量定义、内部变量使用和外部变量使用；(2)为Mi的每条变迁，生成含有最少外部变量使用的最短前导序列；(3)如果Mi的每条变迁都已完成路径生成，继续步骤2.6；否则，取一条变迁，记作Ti，执行以下步骤：(3.1)如果在Ti中被定义的每个内部变量都已完成生成，重复(3)；否则，取一个在Ti中被定义的内部变量，记作vi，继续(3.2)；(3.2)如果使用vi的每一条变迁都已完成生成，重复(3.1)；否则，取一条使用vi的变迁，记作Tj，继续(3.3)，j≠i；(3.3)将Ti加入路径，设Ts=Ti；(3.4)如果Ts的后继变迁，记作Ts+1，不含有对vi的定义，则将Ts+1加入路径，继续(3.5)；否则，丢弃Ts+1，尝试Ts的其他后继变迁，如果已没有未尝试过的后继变迁，则从路径中删除Ts，找到路径中Ts的前导变迁，记作Ts‑1，使Ts=Ts‑1，如果Ts=Ti，丢弃路径并跳转到(3.2)，否则重复(3.4)；(3.5)设Ts+2是Ts+1的后继变迁，如果Ts+1不是Tj，则使 Ts=Ts+1，Ts+1=Ts+2，并重复(3.4)；如果Ts+1=Tj，继续(3.6)；(3.6)如果路径中没有不可执行的变迁，则继续步骤2.6；否则，找到路径中不可执行的变迁，记作Tue，找到使Tue不可执行的变量，记作vue，如果vue是外部变量，则标记Tue为可执行，更新Tue为路径中下一个不可执行的变迁，重复(3.6)；如果vue是内部变量，并且Tue在Mi中的前导变迁Te中存在使Tue可执行的对vue的定义，则生成从路径中Tue的前导变迁出发，包含前导变迁Te并回到路径中Tue的前导的环，将环插入路径中并继续步骤2.6；如果无法生成使Tue可执行的环或不存在使Tue可执行的Te，则丢弃该路径并跳转到(3.2)；步骤2.6、为每一条路径添加使状态机回到初始状态的后置序列，形成完整路径，然后加入集合TSi；步骤2.7、删除集合TSi中重复的或能够被TSi中其它路径包含的路径；步骤2.8、如果Mi中没有未被覆盖的变迁，则执行步骤2.9；如果Mi中仍有未被覆盖的变迁，记作Tk，生成覆盖该变迁的路径，加入集合TSi，重复步骤2.8；步骤2.9、将Mi加入到集合Generated中；步骤2.10、转到步骤2.3；其中，步骤3依次按以下步骤执行：设一个外部变量集合为EV，两个前导序列集合分别为PU和PE，则：步骤3.1、遍历所有组件状态机的所有变迁，将所有外部使用的变量放入EV；步骤3.2、遍历所有组件状态机的所有变迁，如果变迁包含对EV中任意变量的定义，生成该变迁的含有最少外部变量使用的最短前导序列并放入PU；步骤3.3、遍历PU中所有前导序列，如果前导序列可执行，则将该前导序列放入PE；步骤3.4、如果PU为空，继续步骤4；如果PU不为空，取其中的前导序列，记作pu，如果PE中存在能够使pu可执行的一个或多个前导序列，则将这些前导序列与pu链接，将pu移动到PE中并重复步骤3.4；如果PE中存在能够通过多次执行使pu可执行的一个或多个定义，则将含有这些定义的前导序列生成环并形成新的前导序列，将新的前导序列与pu链接，将pu移动到PE中并重复步骤3.4；如果pu仍然无法执行，重新生成pu并重复步骤3.4；其中，步骤4依次按以下步骤执行：步骤4.1、遍历所有组件状态机抽象测试集TSi的所有测试序列，如果存在由于存在外部变量使用而无法执行的序列，取一个无法执行的序列，记作pdu，继续步骤4.2；如果所有测试序列都已可执行，则继续步骤5；步骤4.2、如果PE中存在可以使pdu可执行的一个或多个前导序列，则将这些前导序列与pdu链接，继续步骤4.3；如果PE中存在能够通过多次执行使pdu可执行的一个或多个定义，则将含有这些定义的前导序列生成环并形成新的前导序列，将新的前导序列与pdu链接，继续步骤4.3；如果pdu仍然无法执行，则丢弃pdu；步骤4.3、重复步骤4.1；其中，步骤5依次按以下步骤执行：步骤5.1：遍历所有组件状态机的所有变迁，如果所有变迁都已遍历，则继续步骤6；如果仍有未遍历的、含有外部变量使用的变迁，记作t，则对t执行以下步骤：(1)生成t的含有最少外部变量使用的最短前导序列，记作pt；(2)如果PE中存在能够使pt可执行的一个或多个前导序列，则将这些前导序列与pt链接，继续步骤5.2；如果PE中存在能够通过多次执行使pt可执行的一个或多个定义，则将含有这些定义的前导序列生成环并形成新的前导序列，将新的前导序列与pt链接，继续步骤5.2；如果pt仍然无法执行，则跳转回步骤5.1中的(1)；步骤5.2：遍历PE中的所有前导序列，如果所有序列都已遍历，则继续步骤5.3；如果仍有未遍历的、含有pt中所使用外部变量的定义的前导序列，将该前导序列与pt链接，构成跨状态机测试序列，加入跨状态机抽象测试集；步骤5.3：重复步骤5.1。 |
