软件测试已经被认为是软件工程学科中最重要的研究领域之一,并且仍然是软件质量评估和改进中最被广泛实践和研究的方法之一。通过复杂的抽象,软件工程师已经将测试集成到软件开发价值链的每个层次。但是不管怎么努力,“缺陷”还是会在不经意间“潜入”软件,导致软件最终失效。因此,大量的测试技术被提出用来增强开发人员的信心,高质量的软件具有满足相关人群各种愿望的特定功能。大多数这类技术都关注于选择测试用例的策略。如何生成高效的测试用例已经成为学术界和工业界关注的主题。在对这一主题的众多贡献中,随机测试（RT,Random Testing）是最成功的,并且由于其简单、灵活、高效、易于自动化等优点而受到人们的青睐。最近,越来越多的研究人员开始关注RT的有效性,他们批评RT未能利用任何程序信息来指导测试过程。RT的机制建立在软件使用和行为不能被预测的前提下,因此评估软件质量的测试输入也应该以不可预测（随机）的方式进行选择。尽管这一论断仍然正确,但各种经验观察表明,程序员更容易犯某些类型的错误,从而造成大多数程序失效的输入聚集化。这些引起输入失效的几何形状和分布被称为失效模式。根据这些额外信息,这些研究人员试图通过在程序的输入域均匀分布测试用例来改进RT,从而能够利用这些可能存在的故障模式改善RT的故障检测能力。这类方法被统一归类为自适应随机测试（ART,Adaptive Random Testing）方法。因此,ART系统地指导或过滤随机生成的测试用例,以增强测试用例的均匀分布从而提高RT的有效性。到目前为止,均匀分布测试用例的机制也导致了ART的昂贵开销。RT方法在某些场景下仍然比ART方法更快发现软件故障,而且由于大多数情况下,一旦检测到故障,测试过程就会终止,因此许多人认为ART相对于RT的优势是表面的,因此对ART充满了疑虑。此外,有研究结果表明,ART在有效性方面非常接近其理论的最佳情况。这促使支持者们多年来加强了相关研究,从而提高ART效率的同时保证其本身具有的有效性。尽管存在时间开销大的难题,ART为软件测试提供了一个新的视角,并为使软件使用更安全、更可靠提供了全新的推动力。本研究为该领域做出了一定的贡献,提高了ART测试的效率和效果。本文的主要贡献如下:1.提出一种改进的FSCS-ART算法（FSCS-O,Fixed Sized Candidate Set with Overlapping）,FSCS-O通过重叠机制为FSCS选择固定大小的候选测试集。FSCS测试用例选择涉及两个主要过程:随机选择候选（潜在的）测试用例和识别最佳候选测试用例的过程。第一阶段较为琐碎,但是在确定最佳候选测试用例的过程中,FSCS会陷入一个逻辑陷阱,即通过计算每个候选测试用例与所有之前已执行测试用例之间的距离来评估候选测试用例。这个选择标准使其在逻辑上不可能实现在不降低有效性的情况下提高效率。本文利用数据挖掘策略获取附加信息,从而定义了一种新的名为重叠机制的选择标准,即当前评估候选测试用例的距离度量优于最近执行测试用例的验证值。通过分析FSCS的测试集,发现在测试用例选择过程中,约有50%的时间中出现了重叠状况。这有力地证明了使用重叠而不是原来的“最佳候选”标准将大大降低FSCS的开销。新提出的方法不需要对每个候选测试用例进行评价。在评价过程中,一旦出现重叠的情况,寻找最佳候选测试用例的过程就将终止。模拟和真实程序的实验结果表明,FSCS-O减少了FSCS多达四分之一的计算量而没有影响它的有效性。2.提出一种关系内存选择（RMS,Relational Memory Selection）的ART方案以降低测试用例选择开销。ART的开销负担源于不断增长的失败测试用例数,随着尝试寻找程序错误的失败次数的不断增加,生成连续测试用例的负担也随之增加。因此,我们使用一种仅执行子集而不是执行整个已执行测试用例集来降低ART生成用例开销的策略,也能更好地实现当前的研究目标。为此,分区是最自然的解决方案,但是如何才能有效地实现分区呢?RMS以大量分区的利用和协调为基础,从而实现降低开销成本。同时所有分区使用每个分区中已执行测试用例的相应子集来生成测试用例。为了在执行生成的测试用例的同时实现均匀分布,提出了一种两级的自适应随机序列（ARS,Adaptive Random Sequence）实现方法,该方法在空间上同时考虑了测试用例的局部和全局多样性内容。实验结果表明,与已有的基于分块的故障检测方法相比,该方法在高维空间中保持了良好的故障检测能力,大大提高了传统ART方法的检测效率。其效率水平也优于现有ART的开销削减策略。3.为了进一步提高镜像自适应随机测试（MART,Mirror Adaptive Random Testing）的效率,提出了一种基于已执行测试用例空间位置的遗忘策略,该策略在不影响失效检测能力的前提下,极大地降低了MART的时间复杂度。理论分析表明,MART相对于普通ART的优势取决于用于测试的镜像分区数量。但实验证据表明,实现更多的镜像分区并不一定能保证测试资源的有效利用。进一步的证据表明,MART自身的优势也被证明是它自身的弱点,这使得测试人员面临着应该实施一个更低还是更高的镜像方案的两难境地。在测试过程开始之前,测试人员需要为MART选择一个分区方案,从而确定输入域每个维度中的分区数量。不幸的是,存在一个潜在的风险,即程序的故障区域可能与导致产生有缺陷镜像测试用例的输入域的一个或多个维度没有任何关系。在测试人员无论何时划分维度时,镜像分区的分配方式是源区域内的任何分区都不会与其对应的镜像分区共享一个公共范围。为此,将输入域中的多个分区指定为源区域。然后通过系统地消除线性相关的分区,将其余的分区逻辑地分配给每个源区域作为镜像域。从而消除了产生冗余镜像测试用例的潜在风险,进一步提高了镜像自适应随机测试的效率。4.在镜像自适应随机测试（MART,Mirror Adaptive Random Testing）用例选择策略中,多样性都被认为是一个有良好共识的原则。在这一研究中,MART的问题被定义为一个多样性危机。MART的映射函数被认为是造成这种困境的罪魁祸首。本文提出了一种随机边界镜像变换（RBMT,Random Border Mirror Transform）的镜像测试策略,RBMT既继承了MART的所有优点又不受其缺陷影响。RBMT将多样性矢量集成到MART的位移矢量中,从而生成在所有维度上都是唯一的镜像测试用例。首先,通过在每个镜像分区输入域的每个维度上定义一个随机边界来创建实际镜像分区的虚拟镜像。这将在原分区和虚拟镜像分区中创建一组完全相同的分区副本。然后将使用MART测试用例创建的图像（通过位移向量）转换为虚拟图像,之后在原镜像域中选择对应的图像对从而生成实际的测试用例。通过使用仿真模拟和真实程序进行实验从而评估提出的方法。RBMT比MART的所有方案都有显著的改善。研究还发现,即使使用MART的最佳推荐方案,RBMT在所有被研究的实验方案中也能保证稳定的有效性和效率。