基于遗传算法的统计回归测试数据生成方法

摘要

本发明公布了一种基于遗传算法的统计回归测试数据生成方法，旨在可以高效快速地生成覆盖目标路径的测试数据。具体步骤如下：(1)根据回归测试过程中的修改语句，确定相关输入变量；(2)对与修改语句相关输入变量的概率分布进行建模；(3)基于修改前程序中输入分量的部分概率分布及其扰动值形成初始种群；(4)根据设计的适应度函数，对种群中的每个个体计算其适应值；(5)根据计算出的个体适应值，判断目标函数是否找到最优解，若找到，则输出测试数据并转步骤6；否则，对个体进行变异操作，生成新个体并返回步骤4；(6)结合与修改语句不相关输入变量的概率分布，得到所有输入变量的概率分布；并基于该分布采样，生成测试数据。

主权项

基于遗传算法的统计回归测试数据生成方法，其特征在于其特征在于如下步骤：步骤1.1：针对回归测试数据生成问题，建立满足修改后程序覆盖概率要求的输入变量的部分概率分布数学模型，其特征在于，以提高输入变量概率分布构建的效率为目标，以输入变量与分支语句的相关性，只更新与修改语句相关输入变量的概率分布为约束，建立基于遗传算法的统计回归测试数据生成问题的数学模型如下：$\min f(d_i,|D_{ij}^{\prime }|,p_{x_{ij}})$s.t. d_i∈Z⁺|D'_ij|∈[0,|D'_i|]$p_{x_{ij}}\in [0,1]$i＝1,2,…,v；j＝1,2,…,d_i为了使输入变量独立于实际的数据类型和范围，对被测程序的每个输入分量标准化，使每个分量的取值均在[0,1)之间，记标准化后输入变量为X＝{x₁,x₂,…,x_n}，其中n是输入变量包含分量的个数；与修改语句相关的输入分量记为X₁＝{x₁,x₂,…,x_v}，其中，v是与修改语句相关的输入分量的个数，v≤n；D′_i为输入分量x_i的输入域，为将D′_i划分后的若干数据间隔，d_i是D′_i划分的数据间隔数，间隔长度分别为那么，分别为x_i在各数据间隔上的取值概率，有$p_{x_{i}1}+p_{x_{i}2}+...+p_{x_i{d}_i}=1;$步骤1.2：针对步骤1.1中给出的数学模型，设计了一种含约束的进化优化的求解方法，适应度函数表示为：根据步骤1.1中的数学模型，将寻找部分概率分布的问题建模为一个优化问题，优化的目标为基于某概率分布采样得到的测试数据，覆盖目标路径的最小概率与设定的期望最小概率p'_min的差值，记为从概率分布中采样，得到K个测试数据，计算这些测试数据运行程序后覆盖目标路径集的统计特性；程序包含的目标路径集为L':{l₁',l₂',…,l_m′′}，假设对于任一l_i'∈L'，被测试数据执行的概率为那么，m'条目标路径对应的执行概率分别为这样一来：$\hat{p}=\frac{1}{K}\underset{{l_i}^{\prime }\in L}{min}\left(\underset{j=1}{\overset{K}{\Sigma }}{e}_{{l_i}^{\prime },j}\right)$步骤1.3：使用遗传算法求解其描述的优化问题，以得到满足修改后程序覆盖概率要求的输入变量的部分概率；步骤1.3.1：首先对d_i,|D′_ij|,采用实数编码得到d_i,|D′_ij|,那么，形成的进化个体，记为可以表示为步骤1.3.2：初始种群基于Φ₁及其扰动值形成，输入分量在修改前程序中的部分概率分布为Φ₁，把该部分概率分布作为初始进化种群的部分个体，将提高初始种群的性能，加快种群向Φ'₁进化的速度，因Φ'₂是与修改语句不相关的输入分量对应的概率分布，所以，程序修改前这些与修改语句不相干的输入分量的部分概率分布已经存在，且与Φ'₂相等，故Φ₁＝Φ/Φ'₂；步骤1.3.3：计算个体适应值，当等于p'_min时，得到的部分概率分布即为需要建立的满足修改后程序覆盖要求的部分概率分布；步骤1.3.4：设置变异概率p_m，随机生成[0,1]之间的一个随机数，若该随机数小于或等于p_m，则从中随机选择一个基因位，实施变异操作，对于实施变异操作的基因位，再随机选择一种相应的变异算子，所有可能的变异算子如下表所列：ε和σ的取值根据具体程序确定，如整型输入分量x的输入域为[0,100)，标准化到[0,1)之间，实数编码后仍为[0,1)，对该分量实施或变异算子时，要求数据间隔的变化符合输入分量的数据类型，且能够产生有效的变化，故设置ε＝0.01，这样可以让分量x的数据间隔在[0,100)之间以步长1增大或减小，由于采样概率的取值在[0,1]之间，故σ一般取0.1，并非所有的变异操作，都能满足个体对应输入变量的概率分布要求，鉴于此，种群进化过程中，比较当前个体与父代个体的适应值，跟踪个体适应值变小的变异操作，若当前个体的适应值小于父代，则继续用前一代的变异操作；反之依一定概率选择上表中的一个变异操作。