软件测试是软件开发生命周期中的一个重要过程,其目的是通过检测尽可能多的缺陷来保证软件质量。变异测试是一种面向缺陷的测试技术,一个变异语句对应一个缺陷,包含这些变异语句的新程序称为变异体。变异分支是基于变异测试的必要条件,由被测语句和它的变异语句构成。变异测试是一种评估测试集充分性的典型技术,也常常用于辅助生成测试数据。一般情况下,在进行软件测试时,程序的输入作为需要生成的测试数据。遗传算法一直被广泛的应用于高效生成测试数据。多种群遗传算法是一种高性能的遗传算法,它的种群由多个子种群组成的,种群的个体具有潜在的并行性,使得它在软件测试中具有更强的处理能力和效率。在进行变异测试时,往往生成大量的变异体,不仅导致高昂的测试代价,而且生成杀死这些变异体的测试数据也是一项艰巨的任务,尤其对于难杀死的变异体(顽固变异体)。针对以上问题,本文研究变异分支驱动的软件测试数据进化生成理论与方法。首先,针对覆盖众多变异分支的测试数据难生成问题,以变异分支之间相关性的知识为驱动,提出一种变异分支构建可执行路径的测试数据进化生成方法。该方法基于变异分支之间的执行相关性,形成若干新变异分支;再采用统计分析方法,基于新变异分支与被测语句构建一或多条可执行路径。由此将变异分支覆盖问题转化为路径覆盖问题。之后,建立基于路径覆盖测试数据生成的数学模型,并采用多种群遗传算法生成覆盖这些路径的测试数据。实验结果表明,所提方法能生成较少的可执行路径,且运行时间短,而且可执行路径能覆盖所有的变异分支,进而高效生成比较小的测试集。然后,借鉴上面变异分支的研究成果,针对杀死众多变异体的测试数据难生成问题,以变异分支之间相关性和变异分支自身特征的知识为驱动,提出一种变异分支模糊聚类的测试数据进化生成方法。该方法借鉴“分而治之”的思想,基于弱变异测试准则,选择杀死难度高的变异分支(顽固变异体)为聚类中心,先模糊聚类变异分支。之后建立基于分支覆盖约束的测试数据生成数学模型。再针对多个簇,基于强变异测试准则,采用多种群遗传算法生成测试数据。实验结果表明,模糊聚类方法有助于降低变异测试的执行代价;多种群遗传算法以并行方式高效生成高质量测试数据。接着,改进上面进化算法,针对顽固变异体的测试数据难生成问题,以变异分支与搜索域关联知识为驱动,提出一种变异分支覆盖难度引导的测试数据进化生成方法。该方法首先基于变异分支的覆盖难度确定变异体的顽固性。之后,建立路径约束的变异测试数据生成问题的数学模型。对于顽固变异体,考虑到能杀死它们的测试数据形成的域比较小,基于多种群协同进化遗传算法设计一种动态缩减搜索域的进化策略,生成测试数据。实验结果表明,所提评价变异体顽固性的指标是合理的;动态缩减搜索域有助于高效生成具有高质量的测试数据。最后,改进上面传统数学模型,解决覆盖多顽固变异分支测试数据难生成问题,以变异分支与输入变量之间相关性的知识为驱动,提出基于程序输入分组变异分支的测试数据进化生成方法。该方法将输入变量与变异分支相关性的判定转化为输入变量与目标路径相关性的判定;再基于相关输入分量分组变异分支。之后,针对多个变异分支组,选取相关输入变量作为决策变量,建立一种多任务测试数据生成数学模型;最后,基于多种群遗传算法生成测试数据。实验结果表明,所提方法移除不相关变量,有助于缩减搜索域;并且分组变异分支,有利于采用多任务方式生成测试数据,显著提高测试数据生成的效率。综上所述,所提理论和方法以变异分支为驱动,融合进化算法、聚类和统计分析等方法生成软件测试数据,是自动化、人工智能、应用数学,以及计算机等多个学科的有机交叉。研究内容具有明确的应用背景和产业需求,富有鲜明的新颖性和挑战性,研究成果不仅提高了软件测试数据的生成效率,保障软件产品质量,而且丰富了变异测试理论,对于软件测试具有重要的理论意义和实用价值。