消息传递并行程序拥有简单的开发方式、实现的便捷性,以及优秀的兼容性能,是当前应用最广泛的并行程序之一。消息传递并行程序包含多个进程,这些进程并行执行,协同完成一个任务,使得基于该类程序的问题求解具有高效性。与串行程序相比,该类程序要复杂的多,进程间通过消息传递完成通信,使得执行过程具有不确定性,同时可能伴随着数据竞争、资源冲突,以及死锁等新问题的出现。因此,消息传递并行程序的可靠性要求更高,对其进行测试显得尤其重要。为测试程序,需要确定待测试的目标,可以是一或多个语句、分支、路径,或者其它代码片断。已有学者指出,基于语句、分支等其他的许多软件测试问题都可以转化为路径覆盖测试数据生成问题。因此,寻找覆盖路径的测试数据是非常重要的。消息传递并行程序通常包含多个进程调度序列。针对路径覆盖的测试数据生成问题,本文首先研究从程序中选择可高效生成期望测试数据调度序列的方法,以提高测试效率;但随着程序复杂度的提高,需要测试的路径也急剧增多,如果逐一寻找覆盖这些路径的测试数据,那么,需要多次运行程序,才能生成相应的测试数据。如果多条路径对应选择的调度序列相同,相应的测试数据生成问题,可建模为多目标优化问题,以减少程序运行的次数,从而提高测试数据生成的效率。但是,当路径的数量很多时,将导致建模的优化问题包含过多的目标函数,大大增加问题求解的难度。鉴于此,本文提出一种适用的路径分组方法,将复杂的多目标优化问题分解为多个简单的子优化问题,从而进一步提高测试数据生成的效率;待测试的路径分组后,本文最后给出详细的测试数据问题的求解过程。文章主要包括如下3个方面:(1)针对消息传递并行程序的路径覆盖准则,提出测试数据生成的调度序列选择方法。不同调度序列下覆盖路径测试数据生成的难度存在很大差别。调度序列选择不当,将大大限制测试效率的提高。所提方法旨在针对待覆盖的路径,选择一个性能优越且可行的调度序列,以高效的生成期望的测试数据。首先,在程序的输入空间中基于拉丁超立方采样,生成程序输入集合;然后,以每一采样值在每一调度序列下执行程序,得到覆盖路径与目标路径的相似度,并基于此排序调度序列;最后,基于静态分析,寻找性能优越且可行的调度序列。所提方法充分考虑调度序列对消息传递并行程序执行的影响,为该类程序的测试提供了行之有效的途径。(2)同一调度序列下,待覆盖路径的数量很多时,通过对上述路径合理分组,将测试数据生成问题建模为多个简单的子优化问题,从而提高路径覆盖测试数据生成的效率。考虑到已有方法得到的路径分组,组内路径之间的相似度偏低,路径覆盖测试数据的生成会受到限制。为克服上述缺陷,本文提出一种新的路径分组方法,该方法将组内已有的目标路径均视为基准路径,并基于与这些基准路径的相似度,将剩余的待覆盖路径分组,以提高组内所有目标路径的相似度,从而提高相应的测试数据生成的效率。此外,基于进程直接涉及的程序输入,设定进程子路径相似度的权值,并基于这些子路径的相似度及其权值,计算路径间的相似度。(3)基于上述研究内容,给出测试数据生成的实现过程。该实现过程的核心是遗传算法。作为一种受自然界生物进化启发,产生的基于种群的全局概率搜索方法,遗传算法具有自学习性和自适应性等优点。首先,将测试数据生成问题转化为优化问题,然后,采用遗传算法求解上述优化问题,以生成期望的测试数据。本文提出的方法,不仅提高了基于路径覆盖的消息传递并行程序的测试效率,还扩大了遗传算法的应用范围,具有非常重要的理论意义和实用价值。