消息传递并行程序路径覆盖测试数据生成问题的模型及其进化求解方法

Model of Test Data Generation for Path Coverage of Message-Passing Parallel Programs and Its Evolution-Based Solution

测试数据生成是软件测试的关键,近年来得到国内外学者的广泛关注.但是,已有的研究成果主要面向串行程序.任务划分、进程调度和网络延迟,使得并行程序的执行具有不确定性,给并行程序的测试数据生成带来很大挑战.文中研究消息传递并行程序面向路径覆盖的测试数据生成问题,提出并行程序的路径表示,定义等价路径并给出寻找方法.基于此,建立并行程序路径覆盖测试数据生成问题的数学模型,并采用遗传算法求解该模型.作者将所提方法应用于6个基准测试程序,并与随机法比较.实验结果表明,文中所提方法可以高效生成覆盖目标路径的测试数据.

Generating test data is pivotal in software testing, which has brought to wide-ranging attention from domestic and foreign scholars in recent years. However, previous research results are mainly suitable for serial programs. Task partition, process schedule and network delay make the execution of parallel programs uncertain, giving rise to challenges in test data generation of parallel programs. This paper investigated the problem of generating test data for path coverage of message-passing parallel programs. It first presented a method of representing a path of a parallel program, followed by defining an equivalent path and giving a method of searching for it. Based on these, it built a mathematical model of generating test data for path coverage of a mes- sage-passing parallel program, and gave a strategy of solving the model by using a genetic algo- rithm. The proposed method was applied to six benchmark programs and compared to the random method. The experimental results show that the proposed method can effectively generate test data covering the target path.