1.一种基于相关输入变量的变异体分组方法，设被测程序为G，对其包含的语句实施变异，得到变异体集合为M＝{M1,M2,…,Mn}，n是变异体的个数；将这些变异体转化的变异分支插入到G中，得到新的被测程序G'；设程序的输入向量为X＝(x1,x2,…,xm)，m是程序输入变量的个数；输入域D(X)是每个输入变量域的叉乘,即D(X)＝D(x1)×D(x2)×…×D(xm)；其特征在于：该方法包括以下步骤：S1：构建变异测试用例生成的优化模型；

S2：动态确定变异体与输入变量之间的相关性；

S3：分组变异体；

所述的步骤S1构建变异测试用例生成的优化模型的方法为：记fi(X)为目标函数，反映程序的输入向量X基于弱变异测试准则，是否杀死变异体Mi，当Mi被杀死，fi(X)＝0，否则，fi(X)＝1；Mi被杀死当且仅当fi(X)取最小值0；因此生成杀死Mi测试用例问题可以转化为求解fi(X)最小值问题，记为：min fi(X)

fi(X)只取0和1两个值，很难指导种群的进化；为给种群进化提供更多的信息，在模型中增加一个约束函数gi(X)；

X覆盖Mi的前提是，必须可达原语句s，因此定义X是否覆盖s为约束函数gi(X)；覆盖s的分支距离，设为disti(X)；那么，disti(X)＝0时当且仅当X能够覆盖s，分支距离的值可以任意大，将其进行归一化处理；令由上式可知，0≤gi(X)＜1，且gi(X)＝0当且仅当disti(X)＝0，即，如果X能够覆盖s，那么，gi(X)取值为0；

那么，杀死Mi的测试用例生成问题的数学模型为：min(fi(X))

s.t.

采用基于遗传算法求解上式最优解时，程序的输入向量为遗传算法的决策变量，记为X＝(x1,x2,L,xm)，那么，适应值函数定义为，fiti(X)＝fi(X)×(gi(X)+d)其中，d是一个很小的常数，它的作用确保括号中的值大于0；由上式可知，进化个体性能越好，fiti(X)越小；当fiti(X)＝0时，种群找到了最优解X；

步骤S2动态确定变异体与输入变量之间的相关性的方法为：为了判定变异体Mi与输入变量xj的相关性，首先，随机生成一些进化个体，作为基准测试数据，计算它的适应值；然后，对xj做扰动，扰动后的值替换xj的值，计算新测试数据的适应值；最后，通过计算xj扰动前、后对应的适应值，判定变异体与输入变量的相关性；具体为：

确定扰动值的方法，在D(xj)内随机取一个值γ1，接近D(xj)上、下边界附近随机各取两个值γ2,γ3；

设ρij为Mi与xj是否相关的标记变量，Mi与xj相关，标记ρij＝1，否则，ρij＝0；

设Size为种群中进化个体的个数，第k个进化个体为 其中 对应xj的取值；

基于适应值判定变异体与输入变量的相关性算法：输入：Mi,i＝1,2,…,n；xj,j＝1,2,L,m；

输出：ρij或杀死Mi的测试用例；

A1：随机生成进化个体 k＝1,2,L,Size，然后执行G'，计算它的目标函数fi(Uk)的值；

A2：如果fi(Uk)＝0，输出杀死Mi测试用例Uk；否则，转A3；

A3：如果gi(X)＝0,计算fiti(Uk)的值；否则，转A1；

A4：

A5： 执行G'，计算

A6：如果 ρij＝1；否则，转A7；

A7：如果 且

那么ρij＝0，否则ρij＝1；

A8：输出ρij；

步骤S3分组变异体的方法为：将变异体与输入变量之间的相关矩阵表示为：其中Oi＝(ρi1,ρi2,…,ρim)为Λ的行向量；

分组变异体的算法为：

输入：M，X，Λ；

输出：变异体组C1,C2,…,Cβ；

B1:k＝1，

B2:设

B3:在 对Oi＝(ρi1,ρi2,…,ρim)与Oi＝(ρi1,ρi2,…,ρim),i＝2,3,…,m，实施异或运算如果 第1行和第i行对应的变异体放入Ck中，将O1&Oi值为1对应的第j列的相关输入变量保存；最后获得第k组变异分支 其中 为变异分支的个数；与其相关的输入变量记为 其中lk为相关变量个数；

B4:从M中删除 从Λ删除 对应的行，删除对应的列；

B5:判断Λ是否为空；如果不为空，k＝k+1；转B2；否则，转B6；

B6:输出变异体组C1,C2,…,Cβ。