软件测试是保证软件质量的重要手段。已有统计结果表明,软件测试占开发成本的50%以上,包括:说明测试需求、准备测试数据、执行被测软件,以及评价与分析测试结果等十分耗时、枯燥也是非常困难并容易出错的诸多环节。如果将这些环节自动化,无疑将会缩短软件的开发周期,提高软件质量,从而增强其市场竞争力。而进行软件自动测试的核心,是采用有针对性的理论和方法,生成有效的测试数据,以满足既定的测试充分性准则。已有研究结果表明,对于复杂软件的测试数据生成问题,传统的随机法和基于形式分析的方法往往难以奏效。近年来,虽然也有许多学者采用模拟退火算法、遗传算法,以及禁忌搜索算法等智能优化方法解决该问题,但由于考虑问题的片面性,得到的结果往往难以用于实际的复杂软件测试中。本文分别针对路径覆盖、语句覆盖和变异测试问题,研究复杂软件测试数据进化生成理论及应用。首先,针对路径覆盖问题,提出基于条件语句相关性的不可行路径自动检测理论与方法:先给出基于数理统计的条件语句相关性判定原理,再利用条件语句相关性检测程序的不可行路径。该方法可以检测程序的全部或大部分不可行路径,为有效解决路径覆盖问题奠定了基础;为提高测试数据生成效率,建立了多路径覆盖测试数据生成问题的数学模型,并给出相应的进化优化求解方法。该方法采用多种群同时进化,每个子种群优化一个子问题。算法的关键在于不同种群间的个体信息共享,通过个体信息共享,增强了每个子种群找到最优解的概率,从而提高整个算法的效率;为解决很多路径覆盖问题,建立了基于分组的很多路径测试数据生成问题的数学模型并给出进化求解方案。先基于路径相似度对目标路径进行分组,每组对应一个相对简单的优化子问题。利用遗传算法求解时,采用多种群进化,每个子种群对应一个子优化问题。同组路径间相似度大于给定的阈值,从而保证了算法具有较高的求解效率。基于优化进程,不断简化子优化问题,进一步提高了算法的收敛速度。其次,针对标记变量问题,提出基于等价关系的可测试性转化理论,以及基于可测试性转化的测试数据进化生成方法,基本思想是:对于涉及标记变量问题的目标语句,找到与其满足等价关系的语句(集),且该语句(集)位于目标语句的前面,从而把覆盖原目标语句的测试数据生成问题转化为覆盖等价语句(集)的测试数据生成问题。该方法不需要转化源程序,只需要转化目标语句,大大降低了问题求解的难度;为解决测试数据冗余问题,提出利用占优关系约简目标语句集的测试数据生成方法。先基于语句间的占优关系,构造目标语句集的占优关系图,再运用图论方法求取占优关系图的最小路覆盖,其顶点对应的目标语句集即为约简集,覆盖约简集的测试数据同样可以覆盖原有目标语句集。该方法不但有效减少冗余测试数据,还大大提高测试数据生成的效率。最后,针对变异测试问题,提出基于路径比较和路径覆盖的变异测试方法。先给出基于路径比较的变异测试准则:如果某测试数据在源程序和变异体中所穿越的路径不同,则认为变异体被杀死,在一定程度上降低了测试数据生成问题的难度。然后,给出基于路径覆盖的变异测试数据生成方法。该方法以杀死变异体作为目标,把满足特定路径覆盖作为约束建立优化模型,并采用遗传算法求解,有效提高了变异测试的效率。本文的研究成果大大丰富了软件测试理论,提高了测试数据生成的效率和质量,具有重要理论意义和实际应用价值。