张 昇，刘春宝

(吉林大学，吉林长春 130041)

1 引言

为了保证软件质量通过软件测试保证软件正确性，软件测试核心是制定优质测试计划得到测试用例[1-3]。评定软件质量的有效方式为实施全面的软件测试，可找出软件内的错误，降低开发的错误风险[4，5]。在软件测试的过程中，测试者为了验证新版软件中是否存在新的错误[6]，需重新测试新版软件[7]。为了实现对软件原有数据扩增需覆盖软件的新增与修改内容。软件系统具有的并发特性，存在大量的测试数据影响软件模型的状态空间及软件的测试效率[8]，软件测试数据扩增算法可提高软件测试效率。

但是以往软件测试数据扩增算法非常局限，如吴诗辉等，研究基于神经网络的仿真优化算法[9]，在软件测试数据扩增过程中，由于该算法训练过于复杂，导致软件测试数据扩增效果不佳；刘静等，基于分布式压缩感知的联合检测与跟踪算法[10]，在软件测试数据扩增中，由于该算法在计算时间长导致后期软件测试数据，因此本文研究基于状态空间剪枝的软件测试数据扩增算法。

2 基于状态空间剪枝的软件测试数据扩增算法

2.1 SCPN模型实例实施并发无关行为段的分类

软件系统采用着色Petri网(Colored Petri Net，CPN)实施控制流模型明确及初始标识。面对分段行为的CPN(Segmentation Behavior of CPN，SCPN)，SCPN模型是测试序列生成方法的模型基础，是对CPN扩展。

SCPN=(P，T，A，Σ，V，C，G，E，I)表示1个SCPN模型包括1九元组，有限的变迁(Transition)集合、位置(Place)集合分别用T、P描述；A表示有向弧(Arc)集合且A满足条件A⊆P×T∪T×P；变量(Variable)集合用V描述，对任意变量v∈V，满足Type[v]∈∑；初始化函数(Initialization function)用I描述，定义位置原始数据；1个非空颜色集(Color set)用Σ描述，主要作用是CPN定义数据类型；防卫表函数(Guard function)用G描述，用于表示每个变迁方位表达式；颜色集函数(Color function)用C描述，主要作用是定义位置内的数据类型；弧表达函数(Arc expression function)用E描述，用于表示弧表达式。

变迁集合T包括：

待测行为变迁集合(Tested Behavior Transition)，用TT描述，STT表示待测行为段(Segmentation of Tested Behavior Transition)包括TT内1组连续的相关弧和变迁位置，1个待测行为段用STT{T1，T2，…，Tn}描述。其内T1，T2，…，Tn∈STT。相关行为变迁集合(Related Behavior Transition)用TR描述，STR表示相关行为段(Segmentation of Related Behavior Transition)包括TR内1组连续的相关弧和位置，1个相关行为段用STR{T1，T2，…，Tn}描述，其内T1，T2，…，Tn∈STR。TU表示并发无关行为变迁集合(Unrelated Behavior Transition)；STU表示并发无关行为段(Segmentation of Unrelated Behavior Transition)包括TU内1组连续的相关弧和变迁位置，1个并发无关行为段用STU{T1，T2，…，Tn}描述，其内T1，T2，…，Tn∈STU。

非并发无关行为变迁集合用TN描述，STN表示非并发无关行为段(Segmentation of Non-concurrent Unrelated Behavior Transition)包括Tn中一组连续的相关弧和变迁位置定1个非并发无关行为段用STN{T1，T2，…，Tn}描述，其内T1，T2，…，Tn∈STN。变迁集合T满足：T=TT∪TR∪TU∪TN。SCPN模型实例，见图1。

图1 SCPN模型实例

图1描述1个3路并发的SCPN模型，数据相关行为变迁用TE描述，待测行为用TC、TG描述，并发无关行为TA、TB、TD、TF、TH确定按照模型中是否与待测、相关行为具有并发关系。

SCPN模型实例的并发无关行为段的分类，用图2描述。因为并发无关行为段操作复杂，测试过程中，依照位置关系进行分类处理[11，12]，依据分类结果实施不同规则的剪枝操作。在软件测试内的一条分支上，如果在所有待测行为段后有并发无关行为段；纯无关行为段(Pure STU，PSTU)在软件测试内并发无关行为段占据1整条分支的行为片段；前无关行为段(Before STU，BSTU)；中无关变迁集合(Middle Transition，MT)表示MT中一个变迁元素；中无关行为段(Middle STU，MSTU)。

图2 并发无关行为段的分类

在图2内，STT{TG}表示对于待测行为段，存在前无关行为段BSTU{TA，TB}、后无关行为段(AfterSTU，ASTU)，后无关行为段ASTU{TD}、PSTU{TH}。STT{TC}表示对于待测行为段，存在中无关行为段用MSTU{TF}描述、纯无关行为段用PSTU{TH}描述。

2.2 状态空间剪枝的软件测试序列生成算法

通过状态节点的剪枝算法，处理并发无关行为段分类后待测行为段的状态集。输入系统模型、待测或相关行为段的匹配初、末状态集，判断无关行为段类型，依据类型不同，分别实施特定状态节点剪枝操作，缩减状态空间的规模，得到末状态集、匹配初。

采用状态空间剪枝的测试序列生成算法获取软件测试数据，该算法流程，如图3描述。

图3 测试序列生成算法

由图3可知：将系统模型及其状态空间作为输入数据，采用状态节点投影对所有待测行为段实施操作；对无关行为段类型实施判断，如果有中无关行为段，实施变迁弧剪枝操作；如果存在无关行为段，获取可达子图，变迁弧剪枝操作；若在内侧行为段，去重可达子图，依据状态空间，操作全序列测试。

2.3 数据序列扩增算法

依据上小节获取的软件该测试序列，采用自适应粒子群优化算法，实现软件测试数据扩增。

2.3.1 初始种群选择

为了降低测试序列数据生成个数，使用初始种群实施序列数据扩增。

在新版本程序P′输入用t1，t2，…，tm表示2.1小节获取的测试序列数据集，生成的执行路径用p′(t1)，p′(t2)，…，p′(tm)描述。程序P′的路径p′i和p′j穿越的节点序列分别用n′i1，n′i2，…，n′i|p′i|、n′j1，n′j2，…，n′j|p′j|描述，路径相似度计算，用式(1)描述

S(p′i，p′j)=Nsame/|p′j|

(1)

其内：路径p′i相对于p′j的路径相似度用S(p′i，p′j)描述；路径p′i和p′j穿越的相同节点个数用Nsame描述，且Nsame/|p′i∪p′j|。

(2)

2.3.2 自适应粒子群算法

自适应粒子群算法为了实现粒子的位置x接近目前问题的最优解x*仅需研究x的直接变化，进化公式，如式(3)所示：

(3)

惯性权重决定算法的精度与收敛速度。若惯性权重较低时，对算法局部搜索非常有利；若惯性权重较高时，对算法全局搜索非常有利。

通过调整惯性权重，优化粒子群算法，粒子聚集度φ计算，用式(4)描述

φ=|fg-f′avg|

(4)

其内：种群粒子的平均适应值用favg描述；采用种群内适应值大于favg粒子适应值再次平均计算出f′avg；种群的全局最优解用f描述。

自适应调整方法包括

1)当f(xi)>f′avg时，表示xi逼近最优解，惯性权重越小，惯性权重具体计算，如式(5)描述

(5)

2)当favg≤f(xi)≤f′avg时，表示粒子的状况很普通，惯性权重随迭代次数的增加而增大，在求解时非线性减少，用式(6)余弦定理表示：

(6)

其内：最大进化代数、当前进化代数分别用T、t描述。

3)当f(xi)

(7)

其内，常数用d描述。

(8)

2.3.3 用自适应粒子群优化算法流程

基于粒子群优化算法的数据集扩增算法具体流程如下：

例如：为了输出生成覆盖新版本程序P′的测试序列数据采用输入原程序P的测试序列数据集T。

step 1：相似度矩阵是通过式(2)求得，设置初始参数、初始种群。

step 2：判断终止条件符合程度，判断扩增数据覆盖P′目标路径最大化。如果符合，转到step 6。

step 3：测试序列数据的适应值按照适应度函数调整全局最优pgd、个体最优值pid，并通过式(5)～式(7)设置惯性权重。

step 4：通过式(8)，为了获取目标路径的不同子Pdif与穿越路径路径，确定输入分量ti1，ti2，…，tin，采用Step 1选取测试序列数据作为输入。

step 5：依据step 3获取的参数导入式(3)，更新输入变量ti1，ti2，…，tin生成新的测试序列数据后，转到step2。

step 6：输出覆盖P′的测试序列数据集。

3 仿真研究

仿真测试程序为西门子工业程序集中的程序Tcas、三角形判定程序Triangle、基准程序Next Day，在实验中，全部程序在jdkl.7.0-25环境下运行。为验证本文算法的有效性，实验对比方法选用本文算法与文献[9]基于神经网络的仿真优化算法、文献[10]基于分布式压缩感知的联合检测与跟踪算法实施软件测试数据扩增效率及算法性能仿真分析，基本参数设定包括惯性权重wmax=1.8、wmin=0.4，进化最大代数T=1000，学习因子a1=a2=2。测试程序信息用表l描述。

表1 测试程序信息

3.1 软件测试数据扩增效率分析

采用本文算法与神经网络算法、分布式压缩感知算法，运行测试程序20次，生成目标路径测试数据，对不同指标进行记录，实验结果用表2描述。

由表2数据可知：对比三种算法在不同基准程序的扩增效率，本文算法比神经网络算法、分布式压缩感知算法，测试数据扩增效率平均分别提高了约57%和82%。本文算法均差小，运行时间最短，平均运行时间0.51s。因此，本文算法软件测试数据效率高。

3.2 算法性能分析

选取西门子工业程序集中的Tcas程序，三种算法在迭代过程中对目标路径的覆盖率，用图4描述。

图4 目标路径覆盖率

通过图4数据表明：本文算法比神经网络算法、分布式压缩感知算法相比，在覆盖目标路径方面具有较大的优势，

本文算法在进化代数400时，目标路径覆盖率达到1.0，并在后期的目标路径覆盖率保持平稳，而神经网络算法、分布式压缩感知算法目标路径覆盖率低，后期的目标路径覆盖率有波动。

4 结论

为了提高软件测试的效率，研究基于状态空间剪枝的软件测试数据扩增算法。软件测试时按照并发无关行为段在软件测试内的位置实施分类，依据分类结果实施不同规则的剪枝操作，生成测试序列，采用自适应粒子群优化算法实施软件测试序列数据集扩增。通过仿真结果表明，本文算法在生成覆盖目标路径测试数据的效率高，实现软件测试数据扩增。由于本人时间与精力有限，仍有许多不足之处，以后将研究重点放在实际的软件测评的过程中，采用更先进的算法与科学技术，优化软件测试数据扩增算法的实际应用效果。