变异测试是一种有效的软件测试方法,但高昂的测试代价,使其可行性和应用范围受到很大限制。消息传递并行程序是一类应用广泛的并行程序。为了保证该类程序的可靠性,有必要对其实施变异测试。消息传递并行程序不仅包含为数众多的语句类型和通信函数,其执行还具有不确定性和死锁等特征,这使得消息传递并行程序的变异测试异常困难。因此,有必要提出降低该类程序变异测试代价的理论与方法。本文针对消息传递并行程序,分别从弱变异测试转化、变异体约简,以及测试数据生成等3个方面进行研究。首先,提出消息传递并行程序的弱变异测试转化方法,将变异体杀死问题转化为分支覆盖问题。为此,根据消息传递并行程序不同类型的语句,采用针对性的方法构建变异条件语句;在避免程序发生死锁的前提下,将变异条件语句插入原程序中,形成新的被测程序,从而实现消息传递并行程序的弱变异测试转化。该方法将变异体杀死问题转化为分支覆盖问题,为采用结构覆盖方法解决变异测试问题奠定了基础。其次,提出基于占优度的变异体约简方法,减少需要杀死的变异体。为此,定义分支的占优度,并给出各分支之间占优度和各分支被占优度的计算方法,用于分析分支之间的相关关系;基于占优度和被占优度,给出判断冗余变异条件语句真分支的方法,并删除与冗余分支对应的变异体,以得到约简后的变异体。该方法不但能够保证变异测试的有效性,还能够提高变异测试的效率。最后,针对变异测试数据生成问题,提出基于遗传算法的消息传递并行程序变异测试数据自动生成方法,以高效生成变异测试数据。为此,基于消息传递并行程序弱变异测试转化后的新程序,建立分支覆盖测试数据生成问题的数学模型;采用遗传算法求解该模型,以生成消息传递并行程序的变异测试数据。该方法能够有效提高变异测试数据生成的效率。本文提出的方法,提高了消息传递并行程序变异测试的效率,扩大了变异测试的应用范围,具有重要的理论意义和实用价值。