1.一种基于多种群协同进化的变异测试数据生成方法,其特征在于如下步骤:步骤1.1:基于变异语句的可达难度和涉及程序输入变量个数,确定变异体杀死难度;
步骤1.2:建立基于路径覆盖约束的生成变异测试数据问题的数学模型;
步骤1.3:针对难杀死变异体,采用多种群协同进化遗传算法,根据种群进化时提供的信息,确定搜索域缩减的时机和策略,然后逐渐动态缩减搜索域,生成变异测试数据;
其中,确定变异体杀死难度时,设计的评价指标为变异语句的可达难度和涉及程序输入变量个数;
变异语句的可达难度,记为指标I,如果变异语句s'是可达的,那么,从变异体M的开始到变异语句s',至少存在一条可执行路径;假设从M开始到变异语句s',存在L条可执行路径;那么设第l条路径,包含的条件语句为sl1,sl2,…,sl|l|,|l|为条件语句的个数;这些条件语句执行的概率分别为p(sl1),p(sl2),…,p(sl|l|),那么,第l条路径的执行概率pl为:pl=p(sl1)×p(sl2)×…×p(sl|l|)记通过第l条路径到达s'的难度为Rl,可以表示为:Rl=1‑pl
T
变异语句涉及程序输入的个数,记为指标II;M的输入向量记为X=(x1,x2,...,xm) ,X的取值域为D,那么X∈D;通过第l条路径到达s',包含的输入变量,记为 Kl为输入变量的个数;
指标I的取值为[0,1),而指标II的取值为[1,m],需要将指标II变换到(0,1];记变换后的指标值为K′l,那么,
指标I和指标II具有的重要程度分别记为w1,w2,且w1+w2=1;记w1>w2,那么,杀死变异体M综合指标Dif(M)表示为:
设阈值为θ;如果Dif(M)≥θ,那么M为难杀死的变异体;
建立基于路径覆盖约束的生成变异测试数据问题的数学模型时,记目标函数为f(X),表示输入向量X能否杀死变异体M,如果X能够杀死M,那么,f(X)取值为0,否则,f(X)取值为
1,其表达式为:
生成杀死M的测试数据问题,可以转化为求函数f(X)的最小值问题,记为min f(X);
约束函数记为g(X),Dif(M)指标I中对应的路径作为目标路径q;执行M时,X的穿越的路径记为 q和 的相似度表示为g(X);
基于f(X)和g(X),建立生成变异测试数据问题的数学模型为: