《基于进化优化的软件变异测试理论及应用》阐述基于进化优化的软件变异测试基本原理及应用，内容主要涉及等价变异体检测、基于相关性分析的变异体约简、变异测试数据进化生成及变异准则改进等。《基于进化优化的软件变异测试理论及应用》除了详细阐述所采用的原理与方法之外，还给出不同方法在基准和工业软件测试中的应用，以及全面的方法对比和结果分析。《基于进化优化的软件变异测试理论及应用》是作者多项国家和省部级科研项目系列研究成果的结晶。

　　第1章进化变异测试入门
　　任何软件都不可避免地存在这样或者那样的错误。对软件进行测试可以有效降低软件错误的数量，从而提高软件的质量。因此，软件测试这一工作越来越受到人们的重视。
　　同时，软件测试也是一项非常烦琐的工作，需要投入大量的人力、物力和时间。研究结果表明，软件研发机构大约有50%的工作量花在测试上。对一些要求高可靠性、高安全性的软件，用在测试方面的工作量更高。如果能实现测试工作自动化，将大大缩短测试所需的时间，从而缩短软件的开发周期，提高软件的质量和市场竞争力。而进行软件自动测试的核心，是采用有针对性的理论和方法，生成有效的测试数据，以满足既定的测试充分性准则[1]。
　　变异测试是一种面向缺陷检测的软件自动测试技术，具有排错能力强、方便灵活及自动化程度高等优点，既可以用来生成测试数据，又可以用来衡量测试数据集的检错能力。但是，变异测试需要消耗大量计算资源，从而很难在实际测试中得以应用。因此，如何提高变异测试的效率是值得深入研究的课题[2]。
　　对复杂软件的测试问题，采用诸如遗传算法等智能优化方法进行求解，以期取得更高的求解效率，是近年来软件工程界一种全新的研究方法，并且取得了很多可喜的研究成果[3]。
　　鉴于此，本书针对变异测试问题，研究基于进化优化的复杂软件变异测试理论及应用。该问题属于计算机、自动化与应用数学等多个学科有机交叉的研究方向，不仅有广泛而重要的应用背景，还具有鲜明的新颖性与挑战性。相应研究成果不但能够缩减软件测试成本，提高软件质量，而且能够扩大遗传算法的应用范围，因此，具有重要的理论意义和实用价值。
　　本章内容安排如下：1.1节～1.3节分别是软件测试简介、变异测试简介和软件进化测试简介；1.4节给出研究现状分析，并指出当前研究存在的问题；在1.5节给出本书的主要内容及结构安排之后，1.6节总结本章内容。
　　1.1软件测试简介
　　软件测试是在软件投入市场使用之前，对软件的需求分析、规格说明及源代码等进行的最终复审，是保障软件质量的重要手段和必要依据。
　　软件测试主要通过技术、流程、工具、人员及管理手段，检测软件文档、软件中间产品和最终产品，查找和报告软件缺陷、错误及隐患的方法，通过跟踪缺陷、错误及隐患的修正过程，确保软件产品、中间产品和文档符合软件工程过程需求和用户的最终需求。
　　当前，随着软件应用领域的不断深入，软件的复杂程度日益增大，开发周期不断缩短，对软件质量的要求也逐步提高。因此，如何提高软件测试水平和效率，从而有效保证软件质量，是值得业内和学术界深入研究的课题，也是软件企业谋求发展的必经之道。
　　1.1.1软件测试基本方法
　　按照软件开发的不同阶段，软件测试可以分为单元测试、集成测试、确认测试及系统测试等。其中，单元测试主要针对程序的最小组成单元（模块）进行正确性检验。通过测试，保证各程序模块能够实现正确的功能；集成测试把已经通过单元测试的模块进行组装后，再对组装后模块的体系结构进行测试；确认测试主要检查成品软件是否能够完成需求规格说明中规定的各种功能和软件配置是否正确等；而系统测试则把已经完成确认测试的软件投入实际运行环境，与其他系统组合在一起进行测试。
　　按照是否执行被测程序，软件测试分为静态测试和动态测试两种。其中，静态测试不执行被测软件，仅通过分析或检查程序的语法、结构、过程及接口等判定程序有无错误；而动态测试需要以测试数据为输入运行被测软件，通过检查运行结果与预期结果的差异判定程序是否错误。
　　按照测试过程中是否需要程序代码，软件测试又可以分为黑盒、白盒及灰盒测试三种。其中，黑盒测试不需要程序代码，只需要知道程序应该完成的功能或约束。黑盒测试完全忽略被测程序的内部结构，只检查程序是否能够正确地接收输入数据，并产生正确的输出；白盒测试需要详细的程序代码，检查软件内部的状态是否正常。通常，测试人员依据程序的内部逻辑结构和相关信息设计所需的测试数据，并以该测试数据为输入运行程序，通过检查程序的内部状态，确定该程序是否发生异常；而灰盒测试则是黑盒和白盒测试的融合，它既关注程序的功能，也关注程序的内部状态，同时具备黑盒测试和白盒测试的优点。
　　本书主要考虑应用范围广泛的白盒测试。软件测试的重要性是毋庸置疑的，而软件测试的核心是测试数据。如何根据一定的测试充分性准则生成相应的测试数据是软件测试的关键问题。因此，下面简要介绍白盒测试中常用的测试数据生成方法。
　　1.1.2测试数据生成
　　生成测试数据的过程是非常烦琐的，往往需要花费大量的时间。如果能实现测试数据的自动生成，将有效减轻测试人员的劳动强度，提高软件测试的效率和软件质量，从而节省软件的开发成本。总体来讲，有四种测试数据生成方法，分别为随机法、静态法、动态法和试探法。
　　随机法通过对被测程序的输入空间随机采样，生成覆盖测试目标的数据。该方法简单易行，不受软件类型的限制，且能够快速生成大量的测试数据。但是该方法在生成测试数据时具有很大的盲目性，特别是对于一些复杂的被测程序，很难满足所有的测试要求。因此，人们提出各种自适应随机测试方法，目的是提高所生成测试数据的空间分布特性[4，5]。
　　静态法仅对程序进行静态的分析和转化，不需要实际执行被测程序，如Botella等[6]提出的符号执行法、王志言和刘椿年[7]提出的区间算术法等。在生成测试数据策略方面，张德平等[8]提出一种资源受限的测试数据分配算法。静态法节省了执行程序的时间，但是该类方法通常需要执行大量的代数和（或）区间运算，特别是当输入变量个数很多时，计算量往往是非常大的。另外，该类方法无法处理输入空间为无穷区间的软件测试。
　　动态法基于程序的实际运行生成测试数据，且生成测试数据的过程是确定的，如Miller和Spooner[9]提出的直线式程序法、Korel[10]提出的改变变量法、王雪莲等[11]提出的基于前向分析的动态程序切片方法、Callagher和Narasimhan[12]提出的罚函数法，以及Gupta等[13]提出的迭代松弛法等。该类方法节省了人工分析所需的工作量，但生成测试数据的时间往往很长，且最终结果和初始测试数据的好坏关系很大，因此，得到的测试数据往往不是最佳的。
　　与动态法不同的是，试探法虽然也基于被测程序的实际运行，但是生成测试数据的过程带有很大的随机性，这类方法包括禁忌搜索、微粒群优化、人工免疫、模拟退火和遗传算法等。本书在生成测试数据时，主要采用试探法对建立的模型进行求解。
　　1.2变异测试简介
　　变异测试是一种面向缺陷检测的软件测试技术，最早由DeMillo等[14]和Hamlet[15]提出。变异测试具有排错能力强、方便灵活及自动化程度高等优点，既可以揭示软件的缺陷，又可以衡量测试数据集的检错能力。因此，变异测试自诞生以来，得到了快速发展，应用范围也非常广泛。
　　1.2.1变异测试基本原理
　　变异测试的基本原理是：首先，采用变异算子对被测程序做微小的合乎语法的变动，例如，将关系运算符“>”替换为“<”，从而产生大量的新程序，每个新程序称为一个变异体；然后，基于相同的测试数据运行原程序和变异体，并比较二者输出的异同。如果不同，就认为测试数据将该变异体杀死。
　　杀死变异体需要具备3个条件，分别是可达性、感染性和传播性[16]。记原程序为G，变异体为M，X为测试数据，s为发生变异的语句，则上述条件可描述如下：
　　（1）可达性。以X为输入运行G时，能够执行到变异语句s。
　　（2）感染性。执行变异语句s后，M产生不同于G的状态。
　　（3）传播性。M与G的输出不同，即M与G在变异语句处产生的不一致状态能够传递到程序的输出。
　　需要注意的是，并不是所有的变异体都能被杀死。总体来讲，导致变异体不能被杀死的原因有两个：①测试数据集不够充分；②变异体在功能上等价于原程序，称这类变异体为等价变异体。
　　变异测试通过变异得分对测试数据集的性能进行评价。所谓测试数据集的变异得分，是指被杀死的变异体数目与所有非等价变异体数目的比值。只有当所有变异体都被杀死，或者变异得分已经达到预期要求时，变异测试才结束。
　　目前，对变异测试的研究主要包括等价变异体检测、变异体约简和变异测试数据辅助生成等方面。
　　1.2.2变异测试基本假设
　　变异测试的初衷是能够有效识别出可以发现程序真正缺陷的测试数据。但是对于一个给定的程序，有大量的、种类繁多的潜在缺陷。虽然人们已经给出多种变异算子，但仍然不可能生成代表所有实际缺陷的变异体。因此，对传统的变异测试而言，其目标往往是生成这些实际缺陷的子集，并希望用这些子集来充分模拟所有缺陷。这个理论基于两个假说：称职程序员假说和耦合效应。这两个假说都是DeMillo等[14]在1978年首次提出的。
　　称职程序员假说是对程序员的行为作出的假设。程序员是称职的，是假设程序员开发的程序非常接近正确版本。虽然一个称职的程序员可能在开发程序时编入一个缺陷，但是假设这些故障只是微小的缺陷，通过简单的语法改变就可更正。因此，通过几个简单的语法变动而构成的缺陷被应用在变异测试中，也表示这些缺陷是由“称职的程序员”造成的。
　　耦合效应是对变异分析中缺陷类型作出的假设。耦合效应指出，测试数据通过几个简单的错误就可以区分所有程序与正确程序的不同之处，是非常灵敏的。也就是说，测试数据如果能够分辨出简单的错误，那么也可以分辨出更多更为复杂的错误。Offutt[17]给出了简单缺陷和复杂缺陷更为精确的定义，在他的定义中，一个简单缺陷是可以通过改变程序中一个简易的语法得到的；而一个复杂缺陷是通过对程序作多次语法变化得到的。根据Offutt的耦合效应假说，复杂缺陷被耦合到简单缺陷中，通过这样一种方法，一个能够发现程序中所有简单缺陷的测试数据集也将能够发现大量复杂缺陷。因此，传统的变异测试仅限于使用简单的变异体。
　　1.2.3变异测试存在的问题
　　研究结果表明，比起传统的测试方法，变异测试生成的测试数据具有更好的错误检测能力。但是，已有的变异测试方法存在很多难以解决的问题，如等价变异体问题、变异体数量庞大的问题及变异测试执行代价问题。
　　对于一个已给出的程序G，设M为程序G的一个变异体。如果M与G语法不同，但是输出结果永远相同，则称M为G的等价变异体。经验结果表明，在所有变异体中，等价变异体占10%～40%[18，19]。变异得分是建立在没有等价变异体的基础上的。如果等价变异体不能被完全检测到，那么变异得分就永远不可能达到100%。等价变异体的存在，不会给提高测试数据集的质量带来任何好处，相反，还要花费大量的时间执行这些等价变异体。因此，等价变异体问题是变异测试中的一个重要课题。
　　另外，为数众多的变异体是影响变异测试效率的主要原因。结果表明，即使是一个非常小的程序，也可以产生数量众多的变异体。因此，如何在不影响测试效果的前提下有效降低变异体的数量已成为一个普遍的研究课题。
　　阻碍变异测试得到广泛应用的另一个重要问题是一个测试集执行大量变异体所产生的高昂计算成本。除了降低产生的变异体的数量之外，也可以通过优化变异体执行过程减少计算成本。
　　总之，变异测试还存在很多亟待解决的困难问题，这些问题的很好解决将为变异测试得到广泛应用扫清障碍，使其得到更好的发展。
　　1.3软件进化测试简介
　　1.3.1遗传算法基本原理
　　遗传算法产生于20世纪60年代，是由美国密歇根大学的Holland及其学生和同事发展起来的[20-24]。20世纪80年代，对遗传算法的研究得到快速发展，在理论研究方面，算法的理论基础日趋成熟；在应用研究方面，算法在越来越多的领域得到成功应用[25-27]。20世纪90年代，遗传算法在计算科学、自动控制、模式识别、工程设计、智能故障诊断、管理科学和社会科学等几乎所有学科领域各方面的应用都得到爆炸式的发展。至此，对遗传算法的理论研究和应用研究已全面展开[28]。
　　遗传算法是一种模拟自然界生物进化和遗传变异机制的全局概率搜索方法，它提供了一种求解复杂优化问题的通用框架。由于该方法对优化问题的目标函数没有特别的限制，且具有内在并行性和全局搜索能力，所以得到了学术界和工业界的普遍关注。
　　采用遗传算法解决优化问题时，首先，通过随机方式产生若干待求解问题的数字编码，即染色体
　　……