随着软件复杂性的不断提高,测试成本急剧增加。对于具有不确定性的消息传递接口（Message-Passing Interface,MPI）并行程序而言,生成覆盖该程序目标路径的测试数据将消耗更高的测试成本。此外,基于进化优化生成覆盖目标路径的测试数据时,需要多次执行程序以评价测试数据的性能,这进一步提升了测试成本。鉴于此,研究MPI并行程序路径覆盖测试数据低耗进化理论与方法是非常必要的。首先,针对不确定性导致MPI并行程序测试成本高的问题,提出路径覆盖测试数据生成通信序列选择方法。该方法基于拉丁超立方体采样获得若干程序输入;在每一通信序列下,基于每一采样的程序输入执行被测MPI并行程序,并基于这些程序输入遍历的路径与目标路径的相似度,排序所有通信序列;基于符号执行选择可行的最优通信序列,并在所选通信序列下,基于进化优化生成覆盖目标路径的测试数据。将所提方法应用于7个基准MPI并行程序,并与其它3种典型方法比较。实验结果表明,基于选择的最优通信序列能够高效生成覆盖目标路径的测试数据。然后,针对已有代理模型评估测试数据的方式所需成本高的问题,提出集成代理模型驱动的路径覆盖测试数据进化生成方法。该方法基于进化优化生成若干测试数据,并与这些测试数据的评价值一起形成样本集;基于MPI并行编程标准构建集成代理模型,并利用形成的样本集训练构建的代理模型,用于估计测试数据的性能;根据估计的性能排序测试数据,并通过选择少部分性能优越的测试数据执行程序得到评价值,用于后续的测试数据生成。将所提方法应用于7个基准MPI并行程序,并与其它3种典型方法比较。实验结果表明,所提方法能够降低测试数据生成成本。接着,针对测试数据生成问题具有的多模态特性,提出聚类与代理模型融合的路径覆盖测试数据进化生成方法。该方法考虑问题的多模态特性,将样本集聚为若干类,并基于每类样本训练一个代理模型;采用进化优化生成测试数据时,利用训练的代理模型估计每一测试数据的性能;选择少部分代表性测试数据执行程序得到评价值,以引导种群的后续进化,减少需要执行程序的次数。将所提方法应用于7个基准MPI并行程序,并与其它5种典型方法比较。实验结果表明,所提方法能够大幅度降低测试数据生成成本。最后,针对MPI并行程序部分进程执行成本高的问题,提出分布式代理模型引导的路径覆盖测试数据进化生成方法。该方法确定高成本进程及其输入变量,并产生该进程的初始样本集,用于训练相应的代理模型;基于每一高成本进程的代理模型,估计测试数据在该进程的性能,并与该测试数据在其它进程的性能评价一起,形成测试数据的性能估计值;基于测试数据的性能估计值,选择少部分性能优越的测试数据执行程序得到评价值,以指导测试数据的后续生成。将所提方法应用于7个基准MPI并行程序,并与其它4种典型方法比较。实验结果表明,所提方法能够显著降低测试数据生成成本。上述成果丰富了MPI并行程序路径覆盖测试数据进化生成理论与方法,降低了测试数据生成所需的计算成本,具有重要的理论意义和实用价值。本文总共有图16幅,表30张,参考文献139篇。