基于报文变异的协议鲁棒性测试生成方法

摘要

基于报文变异的协议鲁棒性测试生成方法属于网络协议测试技术领域，其特征在于所述方法依次含有以下步骤：把协议规范描述为一个不确定性参数化扩展有限状态机，建立鲁棒性要求并构造正常验证序列，利用多种变异策略生成单域异常报文，如果单域异常报文注入后导致确定性变迁，则生成单域变异复合异常测试例-1，如果单域异常报文注入后导致非确定性变迁，则生成单域变异复合异常测试例-2，然后使用“pairwise(两两组合)”方法对多域异常进行两两组合，如果多域异常报文注入后导致确定性变迁，则生成多域复合异常测试例-1，如果多域异常报文注入后导致非确定性变迁，则生成多域变异复合异常测试例-2。本发明适用于各种不同的网络协议，具有很好的通用性。

主权项

1.基于报文变异的协议鲁棒性测试生成方法，其特征在于，所述方法是在网络操作环境中对于一个被测试的网络设备依次按以下步骤实现的：步骤(1)：用一个不确定性参数化扩展有限状态机NPEFSM描述一个被测协议实现：所述NPEFSM表示为<S， s₀，I，O，T>，其中：●S：有限状态集合，S＝S_spec，S_spec包含协议规范中定义的状态，定义S＝{s_k|k＝1，2，...}，任意一个s_k都是不确定状态，表示在异常报文注入下不确定变迁的末状态，根据协议规范中关于该变迁不确定或模糊的规定推断出s_k处在S的哪个子集中，所以，S＝S_spec＝(S_spec∪S)；●s₀：初始状态；●包含p个输入；每个输入携带一个参数向量值1≤k≤p；所述p个输入中既包含协议规范中定义的输入，记为I_spec，由有效的报文和部分无效报文组成，也包含了协议规范中没有明确定义的大量输入，记为I_unspec，全部是无效报文；●包含q个输出；每个输出携带一个参数向量值1≤k≤q；●是为描述变迁定义的变量，用向量表示，这些变量和输入、输出携带的参数不同；●T：变迁集合，T＝T_spec∪T_nondeter，其中：T_spec表示在协议规范中给出明确规定的变迁，T_nondeter包含下面两种变迁并都导致末状态s^*∈S，一种是：对于任意状态s_i，收到输入i_j∈I_unspec，对应的变迁在协议规范里都没有明确规定；另外存在一种变迁，尽管i_j∈I_spec，对应的变迁在协议规范里没有定义，或者仅给出模糊或不确定的说明，详细定义如下：对于t∈T_spec，其中s_j∈S_spec，s_k∈S_spec；或者为空，其中s和s^*分别是该变迁的初始状态和末状态；是携带参数的输入和输出；是基于变量集合和输入的断言；动作是基于当前变量值、输入的操作，并作用于变量值和输出；对于t∈T_nondeter，其中s_j∈S_spec，s_k∈S；输出和动作未知或者不确定，用“-”表示；断言始终为真true；步骤(2)：依次按以下步骤进行建立鲁棒性要求以及建立正常验证序列，所述鲁棒性要求是指在无效报文注入后，状态及行为仍然保持正常并符合协议规范的一致性要求：步骤(2.1)建立正常验证序列_1：假设是一个无效报文并且如果s_j ∈S_spec；或者为空，根据s_j的状态验证序列构造正常验证序列，步骤(2.2)建立正常验证序列_2：假设是一个无效报文并且如果s_i∈S_spec，s_k∈S且根据s_k的状态识别序列构造正常验证序列，步骤(2.3)建立正常验证序列_2-1近似替代正常验证序列_2：由于状态识别序列的构造复杂，故需要建立正常验证序列_2-1代替正常验证序列_2，首先定义强制变迁：假设并且s_j∈S_spec，是强制变迁，当且仅当，存在使得利用强制变迁可以建立正常验证序列_2-1：无效报文注入后，末状态为s_k∈S并且如果存在强制变迁：(s_k∈S_k)→s_j，通过报文注入触发这种变迁并根据s_j的状态验证序列构造正常验证序列；步骤(3)：首先仅针对输入的报文一个域进行变异，其它域值都是合法的，对应的测试例为单域变异复合异常测试例，如果异常注入后的变迁是确定变迁T_spec，称为单域变异复合 异常测试例-1，其生成步骤如下：步骤(3.1)初始化：定义一个关于有效报文pdu的测试组TestGroup_pdu并初始为空，步骤(3.2)输入一个有效的报文pdu＝{f₁，f₂，....，f_l ，....，f_N}，共包含N个域，其中pdu.f_l对应的异常域值为M个，用表示，假设 f _l的取值范围为：f_i∈[最小值，最大值]，则这些异常域值包括{最小值，最小值+1，最小值+2*(最大值-最小值)/n，最小值+3*(最大值-最小值)/n，...，最大值-1，最大值}，其中n是划分参数，由设定者制定；另外还要定义其它异常报文：报文的每个域依次移除后生成的多个异常报文，并且每个异常报文仅有一个域被移除，其它域保持不变；每个域被双倍字节的域代替生成的多个异常报文，并且每个异常报文仅有一个域被代替，其它域保持不变；步骤(3.3)定义一个关于pdu.f_l的测试例并初始为空，保存域pdu. f _l的有效域值；步骤(3.4)将“从s₀到s_i的状态引导序列”添加到中；步骤(3.5)对于每一个执行如下步骤：把e_k赋值给pdu.f_l，把“无效报文注入”作为一个测试序列添加到中，然后把“从s_j到s_i的状态引导序列”也添加到中；步骤(3.6)将状态s_i验证序列添加到中；步骤(3.7)把添加到TestGroup_pdu中；步骤(3.8)把步骤(3.3)保存的有效域值重新赋值给被变异域pdu. f_l；步骤(3.9)对于每个域 f_l∈pdu，都分别执行从步骤(3.3)到步骤(3.8)的所有步骤；步骤(4)：对于单域变异复合异常测试例，如果异常注入后的变迁是不确定变迁T_nondeter，称为单域变异复合异常测试例-2，其生成步骤如下：步骤(4.1)初始化：定义一个关于有效报文pdu的测试组TestGroup_pdu并初始为空，步骤(4.2)输入一个有效的报文pdu＝{f₁，f₂....， f_l....，f_N}，共包含N个域，其中pdu.f_l对应的异常域值为M个，用表示，假设f_l的取值范围为：f_i∈[最小值，最大值]，则这些异常域值包括{最小值，最小值+1，最小值+2*(最大值-最小值)/n，最小值+3*(最大值-最小值)/n，...，最大值-1，最大值}，其中n是划分参数，由设定者制 定；另外还要定义其它异常报文：报文的每个域依次移除后生成的多个异常报文，并且每个异常报文仅有一个域被移除，其它域保持不变；每个域被双倍字节的域代替生成的多个异常报文，并且每个异常报文仅有一个域被代替，其它域保持不变；步骤(4.3)定义一个关于pdu.f _l的测试例并初始为空，保存域pdu. f_l的有效域值；步骤(4.4)将“从s₀到s_i的状态引导序列”添加到中；步骤(4.5)对于每一个执行如下步骤：把e_k赋值给pdu.f_l，把“无效报文注入”作为一个测试序列添加到中，把“利用强制变迁s_k→s_j建立的从s_k到s_j的状态引导序列”添加到中，然后把“从s_j到s_i的状态引导序列”也添加到中；步骤(4.6)将“状态s_i验证序列”添加到中；步骤(4.7)把添加到TestGroup_pdu中；步骤(4.8)把步骤(4.3)保存的有效域值重新赋值给被变异域pdu.f _l；步骤(4.9)对于每个域f _l∈pdu，都分别执行从步骤(4.3)到步骤(4.8)的所有步骤；步骤(5)：将输入的异常报文的多个域同时变异，对应的测试例为多域变异复合异常测试例，如果异常注入后的变迁是确定变迁T_spec，称为多域变异复合异常测试例-1，其生成步骤如下：步骤(5.1)初始化：定义一个关于有效报文pdu的测试组TestGroup_pdu并初始为空；步骤(5.2)输入一个有效的报文pdu＝{f₁，f₂....， f_l....，f_N}，共包含N个域，每个域的异常域值集合已经在步骤(3.2)或者步骤(4.2)中生成；F＝{F₁，F₂，...F_M}，对于任意l，1≤l≤M，F_l是几个域的组合，组合方式由测试者制定，进而M值可确定；步骤(5.3)定义一个关于的测试例并初始为空；保存pdu.F_l中各域的有效域值；步骤(5.4)将“从s₀到s_i的状态引导序列”添加到中；步骤(5.5)利用已有的pairwise算法来组合 F _l中各域的域值生成异常值集合对于每 一个执行如下步骤：把E_k赋值给pdu.F_l，把“无效报文注入”序列添加到中，然后把“从s_j到s_i的状态引导序列”添加到中；步骤(5.6)将“状态s_i验证序列”添加到中；步骤(5.7)把添加到TestGroup_pdu中；步骤(5.8)把步骤(5.3)保存的有效域值重新赋值给被变异域组合pdu.F_l；步骤(5.9)对于每个域组合F _l∈F，分别执行从步骤(5.3)到步骤(5.8)的所有步骤，步骤(6)：对于多域变异复合异常测试例，如果异常注入后的变迁是不确定变迁T_nondeter，称为多域变异复合异常测试例-2，其生成步骤如下：步骤(6.1)初始化：定义一个关于有效报文pdu的测试组TestGroup_pdu并初始为空；步骤(6.2)输入一个有效的报文pdu＝{f₁，f₂....， f_l....，f_N}，共包含N个域，每个域的异常域值集合已经在步骤(3.2)或者步骤(4.2)中生成；F＝{F₁，F₂，...F_M}，对于任意l，F_l是几个域的组合，组合方式由测试者制定，进而M值可确定；步骤(6.3)定义一个关于F _l的测试例并初始为空；保存pdu.F_l中各域的有效域值；步骤(6.4)将“从s₀到s_i的状态引导序列”添加到中；步骤(6.5)利用已有的pairwise算法组合F_l中各域的域值生成异常值集合对于每一个执行如下步骤：把E_k赋值给pdu.F_l，把“无效报文注入”序列添加到中，把“利用强制变迁s_k→s_j建立的从s_k到s_j的状态引导序列”添加到中，然后把“从s_j到s_i的状态引导序列”添加到中；步骤(6.6)将“状态s_i验证序列”添加到中；步骤(6.7)把添加到TestGroup_pdu中；步骤(6.8)把步骤(6.3)保存的有效域值重新赋值给被变异域组合pdu. F_l；步骤(6.9)对于每个域组合 F_l∈F，分别执行从步骤(6.3)到步骤(6.8)的所有步骤。