第一章 绪论
1.1研究背景及意义
随着科技的迅猛发展，计算机软件已被普遍应用于日常生活中，例如，交通、医疗、金融等。这些软件一旦出现问题，就会影响到人们的日常生活，甚至带来巨大的损失。所以软件的质量和可靠性就显得非常的重要，软件测试必不可少。当然只追求完全测试是不可取的，测试是不可能穷尽的，所以测试充分性是基于一些准则而言的。传统上的测试都是利用覆盖率这个标准来衡量测试充分性的，近几年来变异测试作为一种评估测试用例集充分性的方法被广泛用于研究。
在变异测试中，为了模拟程序员经常犯的一些错误，测试人员需要在原程序中植入一些错误。然而，一个已知程序的潜在错误数量是庞大的，不可能模拟出所有的错误，因此聪明程序员假设和耦合效应假设为变异测试提供了理论基础。变异测试提供了一种称为变异充分性评分的测试标准来衡量一个测试用例集的有效性[1]。通过简单的语法更改故意将这些错误植入到原始程序中，以创建一组称为变异体的错误程序，每个程序包含不同的语法变化。为了评估给定测试集的质量，针对输入测试集执行这些变异体。在测试用例集中，如果任意的一个测试用例在变异体的运行结果和原始程序的运行结果不同，那么就检测到变异体的错误。
耦合效应假设是指，复杂错误是由简单错误耦合而成，一个测试数据集可以检测一个程序中的所有的简单错误也可以检测高百分比的复杂错误[1]。单个错误检测已经被研究和应用于测试领域，然而，考虑到在实际程序中，程序员所犯的错误不止一处，因此，双故障甚至更高的故障也需要考虑。本文考虑到双故障的情况。在变异测试中，在待测程序中插入单一缺陷的思想在以往缺陷中已根深蒂固。众所周知，高阶变异体的数量太庞大了以致于作为模拟缺陷的数据源不具有实用性。此外，有人认为耦合效应假设意味着高阶变异可能不是那么重要。由高阶变异的不实用性和耦合效应假设引出一个问题：高阶变异是否有必要？为了回答这个问题，我们首先回答：耦合效应假设是否存在？
........................
1.2国内外研究现状
变异测试的历史可以追溯到 1971 年立顿的一个学生报上[6]。该领域的诞生，也可通过 DeMillo[7]和 Hamlet[8]发表在 70 年代末的论文鉴定。变异测试也可以用作软件测试的单元级，集成级，和规格说明级。它已经被应用于许多程序语言，作为一种白盒单元测试技术。例如，Fortran 语言[9-14]、Ada 语言[15][16]、C 语言[17-23]、Java 语言[24-30]、C#语言[31-35]、SQL 语句[36-39]和 Aspect 语言[40-43]。变异测试也被用作集成测试。变异测试除了被用在软件的实现阶段，它也可以被用在设计阶段来测试程序的规格说明或者模型。例如，在设计阶段，变异测试被用作有限状态机[44]、状态图[45]、埃斯特尔规格[46]、Petri Nets[47]、网络协议[48]、安全策略[49]和网络服务[50]。变异测试自从 1970 年代第一次被发现已经被迅速且广泛的研究。去年，Mike 和Papadakis[51]等人还对变异测试的近 10 年进展进行了分析和调查，变异测试已经到了成熟的阶段，并在学术界和工业界逐渐普及。
变异测试致力于有效的找到足够的测试数据，这些测试数据被用于发现真正的错误。然而，所给程序的潜在错误数量是巨大的；不能用变异体来表示所有的错误。因此，传统的变异测试目标只是这些潜在错误的子集，他们接近程序的正确版本，希望这些足以模拟程序所有故障。这些理论基于两个假设：聪明程序员假设（CPH）[7][9]和耦合效应假设[7]。
聪明程序员假设由 DeMillo 等人在 1978 年提出[7]。它是指程序员是有优秀的，他们正常所写的程序接近程序的正确版本。所以，尽管优秀的程序员写的程序可能会有错误，我们假设这些错误仅仅是一些简单语法的错误。因此，变异测试的错误只是由几个简单的语法故障构成的，这代表这些错误是由“聪明程序员”造成的。聪明程序员假设的例子在 Acree 等人的著作中可以找到。程序使用的理论讨论也可以在 Budd 等人的著作中找到。
.........................
第二章 相关背景知识介绍
2.1变异测试
变异测试是一种基于缺陷可用于衡量测试用例检测错误能力的测试技术。变异测试不仅可以衡量用例有效性也可以被用来评估和提高测试用例集的测试充分性。测试者对程序进行一些语法改变形成变异体，这些改变称为变异算子。变异算子是从原始程序形成变异体的转换规则。例如，表 2.1 显示了一个一阶变异体 P’和二阶变异体 P’’。P’通过改变原程序 P 的运算符‘&&’为‘||’。P’’不仅改变了运算符‘&&’也将变量 c 改为!c，是二阶变异体。测试用例集 T将被每个变异体 P’执行，如果测试用例集 T 中任意一个测试用例在 P’上的执行结果和 P 的执行结果不一样，变异体 P’就被认为被杀死，反之，变异体存活。然而，存在一些变异体永远不会被杀死，因为他们总是和原程序有相同的结果。他们与原程序虽然语法不同，但是实现功能一样，因此他们称为等价变异体。表 2.2 是一个等价变异体的例子，运算符‘<’变异成‘!=’但是并不影响程序中循环体最终的结果。在移除等价变异体后，如果存在测试用例集不能检测所有的非等价变异体，测试者需要加入额外的测试用例来提高测试用例集的充分性。变异测试以变异评分来判断测试输入集的质量，变异评分是被杀死变异体的数量和总的非等价变异数量比值。可通过公式计算得出：
.........................
2.2问题描述
在第二章中，弱变异测试的提出是为了优化传统变异测试的执行过程，只需要关注程序中的部分组件。本文中关注的组件是布尔表达式，在分析弱变异测试中的耦合效应之前，先考虑一阶变异体和高阶变异的检测难度问题。也就是说，在同样的测试技术下，布尔规格测试中，一阶变异和高阶变异体哪个更难被测试用例给杀死？在实验中，由于高阶变异的复杂性，我们以二阶变异为高阶变异的代表。实验研究问题就明确为：在布尔规格测试中，一阶变异体和二阶变异体哪个更难被杀死？
我们利用错误检测概率作为度量标准来回答研究问题。对每一个变异体，包括一阶变异体和二阶变异体，统计能够杀死该变异体的测试用例的数量，将该数量除以所有可能测试用例的数量，可以得到失效测试用例百分比。在不考虑具体测试技术（或仅仅考虑最简单的随机测试技术）的情况下，该百分比直接描述了变异体被杀死的难易程度。显然，对于某一个变异体来说，失效测试用例百分比越高，说明该变异体越容易在测试中被检测（或杀死）；反之，则说明该变异体不容易在测试中被检测（或杀死）。
...........................
第五章 布尔规格的高阶变异测试方法
布尔规格的故障层次结构
基于故障的测试和变异分析之间存在密切的关系，变异算子通常被用于模拟潜在的故障。为了方便基于故障的测试方法研究，相同的变异算子引起的故障被分类为相同类别，成为故障类型或故障类别。一些实证研究发现，有些故障类别比其他类别的故障更难检测。这些研究促使研究人员对故障层次之间的关系进行了分析研究。
Kuhn 在布尔规格中确定了三种类型的故障之间的关系。他的研究是第一次尝试为布尔规格构建故障类型层次结构。这种层次结构可用于确定应该处理故障类的顺序，以便实现更具成本效益的测试。Tsuchiya 和 Kikuno 扩展了 Kuhn 的三个故障类型层次结构，包括缺失条件的故障类型。Lau 和 Yu 通过分析变量故障与字面故障之间的关系，进一步扩展了 Kuhn 的故障层次结构。他们的分析也可以应用于测试策略的设计和评估。所有这些研究是假设布尔规格表达式是析取范式。然而，实际程序和规范中的表达式不是析取范式的形式。有研究表明，
一般表达式中的单一故障可能对应于其析取范式中的多个故障。
.......................第六章 总结与展望
6.1总结
变异测试作为有一种基于故障的测试技术在近几年被广泛的研究。变异测试创建变异体来充分模拟原程序的所有可能的缺陷。然而，所给程序的所有潜在故障的数量是巨大的，很难形成充分的变异体来代表所有的故障。因此变异测试的可行性是基于两个假设：聪明程序员假设和耦合效应假设。耦合效应假设是说，复杂故障是由简单故障耦合而成，一个测试数据集可以检测一个程序中的所有的简单故障也可以检测高百分比的复杂故障。由高阶变异的不实用性和耦合效应假设引出一个问题：高阶变异是否有必要？
高阶变异是否必要也就相当于回答耦合效应是否存在的问题。我们首先分析变异体错误检测难度，比较一阶变异体和二阶变异体哪个更难被检测到。首先通过对 TCAS 系统中抽取的布尔表达式进行十种变异算子的变异，生成 24521 个一阶变异体，其中有 19131 个非等价变异体。通过完全测试的方法过滤出等价变异体并生成错误的失效测试用例。再对所有一阶变异体进行再变异生成 22336023 个二阶变异体，其中非等价变异体 20756637 个，再生成二阶变异体的失效测试用例。然后对一阶变异体和二阶变异体统计失效测试用例百分比，通过对比失效测试用例百分比比较一阶变异体和二阶变异体的检测难度。对实验结果显著性分析后，得出结论：二阶变异体相比一阶变异体整体更容易被检测。如果第一个故障类型为 CCF、CDF、LNF、LRF、MLF、SA0 和 SA1，二阶变异体比一阶变异体更容易被检测。无论第二阶故障类型是什么，二阶变异体都比一阶变异体更容易检测。
在比较过一阶变异体和二阶变异体检测难度后，对耦合效应进行分析。首先同样获得一阶变异体和一阶变异失败测试用例集，再进一步获取二阶变异体和二阶变异体失败测试用例集。为了避免测试用例冗余增大耦合效应成立的概率，我们需要对一阶测试用例集进行约简，
采用四种常见算法 Greedy 算法、GE 算法、GRE 算法和 Harrold 算法约简一阶测试用例集取得测试用例充分集。对二阶变异体，计算一阶测试充分集检测二阶变异体的百分比。我们知道如果耦合效应存在，那么一阶测试用例充分集检测二阶变异体的百分比是 100%。为了使结果更加清晰，将二阶变异的每种类型的测试百分比的实验均值与理论值做差，将差异值进行统计。差异值越大，说明耦合效应成立的概率越小。实验结果表明对任意故障类型，耦合效应都不能保证百分百成立。特别地，当变异类型设计故障 ENF 和 ORF 时，耦合效应成立的概率就明显降低。
参考文献（略）