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

技术领域

本发明属于软件测试技术领域，具体涉及到并发程序噪声注入优化问题，提出了一种多目标并发程序噪声注入群体优化方法。

背景技术

在当前多核处理器充分普及的并发时代，多线程并发程序因其可以显著提高系统的资源利用率、计算速度快等优点得到了广泛的应用，但是由于线程调度交错执行具有不确定性，使得很多并发缺陷难以被发现，这样会增加软件调试和维护的代价。并发程序缺陷的暴露在多线程程序的研究中有着很重要的地位，因为并发缺陷检测、修复、规避的前提是暴露出并发缺陷，如果找到一个可以有效且全面暴露并发缺陷的方法不仅对并发缺陷的研究而且对提高软件质量等其他方面同样有着重要的意义。

为了尽可能多的检测并发错误，国内外众多学者致力于使用噪声注入技术检测并发错误的研究，以此来增加程序在执行期间出现并发错误的可能性，提高测试效率。基于噪声注入的并发缺陷检测技术是按照噪声注入序列对待测并发程序进行噪声注入，噪声注入序列包括噪声注入程序位置、注入的噪声类型。通常并发程序的规模比较庞大，注入的过多的噪声语句数量会使CPU频繁的执行上下文切换，这样不但会增加程序的运行时间开销和降低内存利用率，甚至还有可能会隐藏掉某些并发错误。为此，本发明提出了多目标并发程序噪声注入群体优化方法，该方法可以有效的优化并发程序执行过程中并发错误出现的次数和注入噪声语句的位置数量，使这两个目标达到相对较优。

发明内容

噪声注入技术是指在并发程序中注入如sleep()、wait()、yield()等噪声语句，干扰调度器对线程的调度，强制CPU执行上下文切换，增加并发错误出现的概率。在使用噪声注入序列对待测程序进行噪声注入过程中，目标是使并发程序执行过程中并发错误出现的次数尽可能增多，而注入噪声语句数量要尽可能减少。

本发明为多目标并发程序噪声注入群体优化方法，如图1所示，该方法的特征包括以下步骤：

步骤一：针对一个噪声注入序列T

步骤二：使用被测并发程序在运行过程中出现的并发错误次数与注入的噪声数量作为优化目标函数f

步骤三：在第i次迭代中，从种群中随机选取三个个体T

H

对于NP_set中的个体T

H

其中T

步骤四：在第i次迭代中，从NP_set和P_set中分别随机选择个体进行交叉操作，即对于群体中第i代第n个个体T

其中，rand()为[0,1]之间均匀分布的随机数，CR∈[0,1]；

步骤五：在第i次迭代中，对于交叉后个体V

步骤六：根据帕累托最优条件更新外部非支配解集P_set，两两比较P_set中的个体，将不是非支配解个体删除，使更新后的P_set中均为非支配解，记录本次迭代后的P_set中所有个体的并发错误次数与插入噪声的数量；

步骤七：判断终止条件，迭代的终止条件是当前迭代次数大于最大迭代次数，若迭代终止条件成立，那么此时外部非支配解集P_set为多目标噪声注入优化问题的最优解集，输出该解集并停止迭代；否则，令迭代次数i＝i+1，返回步骤三。

附图说明

附图1为多目标并发程序噪声注入群体优化方法的流程图。

附图2为多目标并发程序噪声注入不同方法的平均并发错误出现次数对比图。

附图3为并发错误出现次数随噪声注入数量变化的散点图。

具体实施方式

以经典基准程序“Airlines”的噪声注入优化为例，结合附图1对本发明提出的多目标并发程序噪声注入群体优化方法的具体实施方式进行说明。

步骤一：针对一个噪声注入序列T

步骤二：使用被测准程序“Airlines”在运行过程中出现的并发错误次数与注入的噪声数量作为优化目标函数f

步骤三：在第i次迭代中，从种群中随机选取三个个体T

H

对于NP_set中的个体T

H

其中T

步骤四：在第i次迭代中，从NP_set和P_set中分别随机选择个体进行交叉操作，即对于群体中第i代第n个个体T

其中，rand()为[0,1]之间均匀分布的随机数，CR∈[0,1]；

步骤五：在第i次迭代中，对于交叉后个体V

步骤六：根据帕累托最优条件更新外部非支配解集P_set，两两比较P_set中的个体，将不是非支配解个体删除，使更新后的P_set中均为非支配解，记录本次迭代后的P_set中所有个体出现的并发错误次数与插入噪声的数量；

步骤七：判断终止条件，本方法的迭代终止条件是当前迭代次数大于最大迭代次数MAX＝100，若迭代终止条件成立，那么此时外部非支配解集P_set为多目标噪声注入优化问题的最优解集，输出该解集并停止迭代；否则，令迭代次数i＝i+1，返回步骤三。例如，第100次迭代后，输出的最优噪声注入序列为(43,1)(295,3)(1256,1)(2865,3)(3145,3)(98,2)(365,2)(1345,2)(1963,2)(3241,1)(123,1)(365,2)(1345,2)(2245,3)(2936,2)(98,2)(421,1)(1856,3)(2547,1)(3145,3)(43,1)(214,2)(2105,1)(2547,1)(2714,1)(96,3)(254,3)(1756,3)(3012,2)(3041,3)

通过以上过程可以实现多目标并发程序噪声注入群体优化方法，针对基准程序“Airlines”，使用RN方法、GA方法与本发明中的方法分别进行10次实验，图2是10次实验中，迭代100次的并发错误出现次数平均值，从图2可以看出，本方法可以得到并发错误出现次数更多的噪声注入序列；针对基准程序“Airlines”使用本发明中的方法独立进行5次，图3是5次实验中，迭代100次并发错误出现次数随噪声注入数量变化的散点图，从图3可以看出，本方法得到的实验结果相对集中，因此本方法在噪声注入优化时是稳定的。