多目标并发程序噪声注入群体优化方法.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN112269736A(43)申请公布日2021.01.26(21)申请号202011155668.5(22)申请日2020.10.26(71)申请人西安邮电大学地址710061陕西省西安市长安南路563号(72)发明人孙家泽杨彦漫单力佳王曙燕舒新峰(51)Int.Cl.G06F11/36(2006.01)权利要求书1页说明书4页附图2页(54)发明名称多目标并发程序噪声注入群体优化方法(57)摘要本发明针对并发程序噪声注入优化问题，公开了多目标并发程序噪声注入群体优化方法，属于并发程序测试领域。该方法首先对噪声注入编码，采用佳点集方法生成初始种群，并以并发程序执行时出现并发错误的次数与注入噪声的数量作为优化目标；然后求解初始种群中所有非支配解并保留在外部集合中；其次，对种群中的每个个体进行变异、交叉、选择操作生成新一代种群，更新外部集合并记录个体对应的适应度值；最后当达到迭代终止条件时，外部集合中的所有解即为并发程序噪声注入最优解集。本发明提供了一种有效且稳定的并发程序测试多目标噪声注入优化方法，有助于提高并发缺陷测试效率，降低测试代价。CN112269736ACN112269736A权利要求书1/1页1.多目标并发程序噪声注入群体优化方法，其特征在于包括以下步骤：步骤一：针对一个噪声注入序列Ti，使用L＝{1,2,...,i,...,m}表示被测并发程序的m个程序语句位置，其中i∈L,1≤i≤m，使用inject∈{0,1，2,3}表示某个程序语句位置是否注入噪声以及注入的噪声类型，当inject＝0时表示该程序位置不注入噪声，inject＝1时表示在该程序位置注入sleep()噪声，inject＝2时表示在该程序位置注入wait()噪声，inject＝3时表示在该程序位置注入yield()噪声，Ti是由噪声注入的程序位置与注入的噪声类型的有序序列组成，首先采用佳点集方法产生种群规模为N的初始种群集合PT，并根据噪声注入序列对被测并发程序进行噪声注入；步骤二：使用被测并发程序在运行过程中出现的并发错误次数与注入的噪声数量作为优化目标函数f1与f2，其中f1、f2的定义域为PT，值域为实数，当f1的值越大f2的值越小时，说明该噪声注入序列更加优良，对于个体T1和T2，T1,T2∈PT，求解PT中所有满足f1(T1)>f1(T2)并且f2(T1)>f2(T2)，或者f1(T1)＜f1(T2)并且f2(T1)＜f2(T2)帕累托支配关系的非支配解个体，并将求解得到的所有非支配解个体保存到外部非支配解集P_set中，其余个体保存在非帕累托集NP_set中，设定种群规模N、缩放因子F、交叉概率CR以及最大迭代次数，令迭代次数i＝1，开始迭代；步骤三：在第i次迭代中，从种群中随机选取三个个体Tr1(i),Tr2(i),Tr3(i)且r1≠r2≠r3，对于P_set中的个体Tm(i)＝(Tm,1(i),Tm,2(i),...,Tm,n1(i))生成变异向量Hm(i)：Hm(i)＝Tm,r1(i)+F×(Tm,r2(i)-Tm,r3(i))对于NP_set中的个体Tn(i)＝(Tn,1(i),Tn,2(i),...,Tn,n2(i))生成变异向量Hn(i)：Hn(i)＝Tgbest(i)+F×(Tm,r2(i)-Tm,r3(i))其中Tgbest(i)为当前种群中适应度值最好的个体，F∈[0,2]为缩放因子，用于调节向量差异的步长幅值以避免进化过程出现停滞；步骤四：在第i次迭代中，从NP_set和P_set中分别随机选择个体进行交叉操作，即对于群体中第i代第n个个体Tn(i)与第第i代第k个变异向量Hk(i)，首先至少随机选择变异向量Hk(i)中的一维变量作为交叉向量Vn的D维变量，对于其他维变量，可利用交叉概率CR决定交叉向量Vn中各基因位分别由Tn(i)或Hk(i)中的哪个提供，交叉操作的具体形式为：其中，rand()为[0,1]之间均匀分布的随机数，CR∈[0,1]；步骤五：在第i次迭代中，对于交叉后个体Vn(i)与原个体Tn(i)，求解二者是否互为支配关系，若交叉后个体Vn(i)支配原个体Tn(i)，则将交叉后个体Vn(i)加入到P_set中；若原个体Tn(i)支配交叉后个体Vn(i)，则将原个体作为选择后的个体加入到P_set；步骤六：根据帕累托最优条件更新外部非支配解集P_set，两两比较P_set中的个体，将不是非支配解个体删除，使更新后的P_set中均为非支配解，记录本次迭代后的P_set中所有个体的并发错误次数与插入噪声的数量；步骤七：判断终止条件，迭代的终止条件是当前迭代次数大于最大迭代次数，若迭代终止条件成立，那么此时外部非支配解集P_set