并行测试和变异测试七篇文献总结[一]

Using Evolutionary Computation to Improve Mutation Testing

主要讲变异测试中使用遗传算法。

Motivation:遗传算法可以减少变异体子集而不会丢失重要信息。分析了突变测试的最新进展，这有助于降低与此技术相关的成本，并提出应用它们来解决进化突变测试（EMT）中的当前缺陷.

将重点放在突变测试中提出的方法应用于进化突变测试，这是一种基于遗传算法选择减少的突变体集的技术,并且整合以下方法：

1.基于质量度量的选择性变异。

​ 我们可以选择丢弃一部分突变操作符（基于操作符的选择性突变）或优先选择最有价值的操作符（基于秩的突变体选择）的突变体。

进化变异测试的提出：

Dom´ınguez-Jim´enez, J.J., Estero-Botaro, A., Garc´ıa-Dom´ınguez, A., Medina-Bulo, I.: Evolutionary mutation testing. Inf. Softw. Technol. 53(10), 1108–1123 (2011). http://dx.doi.org/10.1016/j.infsof.2011.03.008

潜在等效变异体：测试套件未检测到的变异体

难以杀死的变异体:仅通过特异性测试案例杀死的变异体，不会杀死其他变异体

EMT可以找到强突变体。

EMT降低变异测试成本的两个途径：

• EMT不是从所有变异算子生成突变体，而是仅根据质量度量在排名后从最佳值运算符生成突变体。
• 不是以相同的概率产生突变体，而是以基于秩的方式选择突变体：从最佳值算子中选择突变体的概率更高。 该标准应用于在每一代遗传算法中随机产生的突变体子集。

应用于C ++中的类级别的变异算子时，基于突变的选择产生比基于变异算子的选择更好的结果。

EMT的优点：

通过删除分类底部的变异算子，EMT的效率得到提高，因为它将避免遗传算法产生低质量的突变体。遗传算法可以更快地找到可以导致测试套件增强的那些突变体。 这些突变体可以标记为抗性突变体。

非等价变异体存活的原因是：1.测试套件不覆盖突变体。2.测试套件覆盖突变体但是却不能揭示其突变。

而第二点可以通过基于质量度量的突变体生成方式来改进。

2.多目标进化突变测试

在遗传算法的适应度函数方面应该考虑：

• 最大化覆盖范围的影响：EMT不能区分等价变异体和抗性变异体，这样可以选择具有最高概率的非等价变异体。
• 最大化代码的覆盖范围：最好在整个程序的代码中传播突变。
• 最大化变异算子集中的散射

3.TCE (Trivial Compiler Equivalence)

TCE可以自动的检测一些等价变异体。显示出能够在C编码的程序中平均减少30％的等效突变体集.

TCE结合使用编译器gcc和实用程序diff：gcc用于编译代码并生成优化的可执行文件，而diff允许比较这些可执行文件以搜索程序的不同版本之间的等价。

该机制可以检测两种类型的变异体：

• 等价突变体的一个子集：原始程序的二元文件与突变体之间没有差异时，突变体被识别为等价。
• 重复突变体的子集：当从突变体衍生的二元文件等于从另一个突变体衍生的二元文件时，突变体被识别为重复的。

TCE中最昂贵的任务就是编译时间。

将EMT和TCE结合使用：

• 在执行EMT之前应用TCE，在这种情况下，编译所有突变体以创建可执行文件，TCE将它们与原始程序的可执行文件进行比较。然后标记由TCE检测为等价的那些突变体以避免它们可以在EMT的执行期间使用。
• 在执行EMT期间应用TCE。 在这种情况下，使用TCE分析在每一代中选择的突变体。 那些被认定为等价的突变体通过分配给它们的适应值来惩罚。

注意：

TCE仅适用于C程序。

在等价突变体和抗性突变体稍微不同的前提下，一些等价的突变体可能可以指导遗传算法选择新一代的抗性突变体。 因此，去除等价的突变体可能会影响对潜在等价突变体的搜索。

future:

尝试找到一种方法避免执行所有的测试用例来计算适应度函数，特别是在执行时间较长的时候。

CUT:Automatic Unit Testing in the Cloud

ISSTA’17-DEMOS, July 2017, Santa Barbara, CA, USA

Alessio Gambi, Sebastian Kappler, Johannes Lampel, and Andreas Zeller

通过分布式环境并行运行单元测试。

本文提出了一种云单元测试。一种在分布式执行环境中自动执行单元测试的工具。CUT为虚拟机或者容器分配适当的计算资源，并安排对它们执行测试，开发人员不需要更改现有的单元测试代码，并且可以轻松控制测试执行的资源分配和测试调度。执行期间，CUT监视器发布有关正在运行的测试的事件，这些事件启用了流分析。

网址：https://www.st.cs.uni-saarland.de/testing/cut/

在本文中，我们通过利用云等分布式执行环境的强大功能来解决加速测试执行的问题。

CUT的优势：

完全自动化和透明度，CUT采用面向切面编程（AOP）来隐藏访问云的低级机制，并且将测试执行分布在开发人员的远程资源上。包括在多个单一测试方法级别自动并行化测试执行的能力。

高效的资源分配和灵活性。大多数基于云的测试解决方案。开发人员无法轻松控制测试运行的位置和每个测试的资源数量。CUT开发人员可以决定单元测试是在本地还是远程，以及需要多少资源。CUT允许测试执行共享计算资源，从而提高测试的成本和效率。

测试依赖性，当前用于并行化测试的解决方案假设完全依赖于单元测试。但是，测试并不总是独立的，这导致了非确定性的测试执行和误报。CUT可以采取考虑到测试依赖性信息以实现确定性执行。

步骤：

set up:

config

test runners

准备好虚拟机后，根据集群策略将测试集中到独立的执行单元。根据部署策略将集群部署到本地或远程的测试运行器。根据调度策略命令测试执行。

这些策略都由开发者定义。

Execution：

每个测试运行器从其队列中查看要执行的下一个测试（对象）的引用。然后，自定义类加载器尝试延迟加载正确执行单元测试所需的类和数据。如果测试运行器已经可以使用它们，则执行继续。否则，自定义类加载器从类中提取类的字节码和数据。同时，测试运行器缓存类和数据，使得这些可以在后续测试执行中重用，可能最小化总体执行开销。

Monitoring and Reporting：

所有CUT组件都连接到共享事件序列以发布和接收监听事件。

云管理器发布事件，如虚拟机的启动或关闭。

测试运行器发布有关单元测试生命周期的事件：测试开始，完成和失败。

分析和报告组件将所有事件存储为pository以进行进一步数据分析。

porter组件面向开发人员并提供两种类型的报告：1.alive-report它捕获有关开发人员单元测试状态和上下文的事件流。2.测试执行的最终摘要，其中包括基本统计信息和有关失败测试的详细信息，即堆栈跟踪。

消息中间件采用Apache ActiveMQ

技术实现：

采用Java实现。测试开源工具Junit。采用maven自动化构建。云的中间件选用 JCloud-Scale 。

实验环境：

使用Tachyon（加州大学伯克利分校AMPLab开发的高效虚拟分布式存储，附带一个广泛的测试套件）作为测试主题使我们有机会评估CUT在具有大型测试套件的系统环境中并行化测试执行的能力。

使用Crystal评估CUT是否能正确处理测试的依赖性。

对于此评估，我们选择使用轻量级容器而不是标准虚拟机，因为它们可以在逻辑上隔离测试执行，因为容器启动时间比VM要长。 但是，我们必须注意到CUT不仅限于容器;事实上，它可以在容器，虚拟机和虚拟机内的容器上分配单元测试。此外，CUT可以跨测试执行重复使用虚拟机，从而它们启动造成的开销。

CUT构建测试依赖图，将属于同一弱连接的测试集群在一起，并根据拓扑排序在同一VM上的每个集群中执行测试。

最近工作：

将软件测试移植到云端。

与HadoopUnit相比，CUT不需要广泛而繁琐的设置，允许开发人员控制资源分配，并且可以处理测试依赖性。

future:

Improved Strategies

Continuous Integration in the Cloud

Continuous Testing in the Cloud

Concolic testing导向性随机测试

Distributed software testing

https://patents.google.com/patent/US9811451B1/en

测试实例还可以配置被测软件和能够对软件执行测试的测试运行器。 软件测试服务可以将测试放在队列上，例如队列服务提供的队列。 在测试实例上执行的测试运行程序可以使测试出列并对软件执行测试。 一旦完成了测试软件的测试，就可以取消配置测试实例。

背景：

如果软件开发团队利用此类测试来批准对软件的更改，则执行测试所需的大量时间可能会限制团队进行代码更改的能力，并使更改能够及时部署到生产环境中。

由于执行软件测试有时需要很长时间，因此一些软件开发团队最终会减少对软件执行的测试数量。 这意味着代码更改可以更快地到达生产环境。 但是，这也意味着软件包含错误的风险大于执行更彻底的测试的风险。 在许多环境中，部署包含错误的软件的风险较高是不可接受的。

上述问题的一种解决方案是利用允许多线程执行测试的测试平台。 使用这样的平台，可以在同一过程中同时执行多个测试。 但是，这种解决方案通常有其自身的局限性。 例如，为了执行多线程测试执行，测试开发人员必须以确保测试对多线程执行安全的方式编写测试。 因此，为多线程执行创建测试可能需要软件开发人员进行大量额外的工作。 另外，多线程执行仅扩展到执行它们的计算机的计算资源（例如CPU和存储器）的限制。 因此，多线程执行测试的好处可能会受到限制。

分布式软件测试的技术。通过这些技术的实现，开发人员创建的软件测试可以分发到多个测试实例，以便并行执行。通过以这种方式并行执行软件测试，与非并行执行相比，可以减少执行测试所需的时间量。此外，通过并行执行软件测试，可以执行确保高质量软件所需的大量测试，同时允许软件及时部署到生产环境中。这些技术使得能够并行执行软件测试，而不需要软件开发者以任何方式修改他们现有的测试。

这里公开的软件测试服务被配置为接收对软件执行测试的请求（这里可以称为“被测软件”）。 该请求可以包括软件或对软件的引用，测试或对测试的引用，以及可能的一个或多个测试偏好。 例如，该请求可以由被测软件的软件开发者生成并提交给软件测试服务。

开发人员指定的测试首选项可以定义关于如何将测试分发到测试实例以便并行执行的各种首选项。例如但不限于，测试首选项可以明确指定用于对软件执行测试的测试实例的数量。作为另一个示例，测试首选项可以指定测试的最大执行时间。在这种情况下，可以基于测试的历史测试执行时间数据来确定用于在大约最大执行时间内完成测试的测试实例的数量。或者，如果历史测试执行时间数据不可用于测试，则可以基于与测试类似的其他测试的历史测试执行时间数据来确定用于在大约最大执行时间内完成测试的测试实例的数量。要进行。测试偏好还可以指定关于执行测试的方式的其他或替代偏好。

一旦确定了用于测试的测试实例的数量，软件测试服务就可以使测试实例被供应。 例如，在一种配置中，软件测试服务可以利用在服务提供商网络中执行的按需计算服务来提供测试实例。 测试实例可以是VM实例，软件容器，专用服务器计算机或适合于对被测软件执行测试的其他类型的软件执行环境。 一旦配置了测试实例，就可以将测试中的软件和测试运行器部署到测试实例。 测试运行器是可执行软件，配置为获得测试，对被测软件执行测试，并提供测试结果。

在一个特定配置中，软件测试服务被配置为利用由在服务提供商网络中执行的队列服务提供的队列来向在测试实例上执行的测试运行器提供测试。 例如，软件测试服务可以在这样的队列上放置测试或包括对测试的引用的消息。 在测试实例上执行的测试运行器可以使测试从队列中出列，并对测试中的软件执行测试。 测试运行器将继续出列测试并执行测试，直到队列中没有进一步的测试。

软件测试服务还可以确定是否所有测试都已完成。 如果已完成测试软件的所有测试，则可以取消配置测试实例。 例如但不限于，可以指示在服务提供商网络中执行的按需计算服务来取消供应测试实例。 通过这种方式，测试实例仅在测试期间使用，并且一旦测试完成就可以销毁。

Cloud-Based Parallel Concolic Execution

解决路径爆炸（Path explosion）问题，本文提出了一种名为PACCI的方法，通过利用云基础设施来并行化执行并适应计算资源的剧烈变化。PACCI为MapReduce编程模型量身定制了执行，并考虑了云基础架构的功能。

主要解决了几个挑战性的问题：

独立探索不同的程序路径。

构建可扩展的路径探索模块，以支持从全局角度确定测试输入的优先级。

初步实验结果表明，PACCI是可扩展的（例如，使用24个节点获得大约20倍的加速），并且其效率分别在资源波动和节点故障下略微下降约5％和6.1％。

具体而言，PACCI通过将程序的复杂执行视为任务来定制对MapReduce编程模型的执行，并动态地将任务划分为映射子任务并减少子任务。一个map子任务收集一个路径条件并生成一个测试输入组，而一个reduce子任务优先生成测试输入。

设计PACCI时面临的挑战：

• 首先，由于具有执行性的迭代性，因此独立探索每条路径并非易事。我们通过仔细设计并行的concolic执行来解决这个问题，包括由子任务完成的工作，子任务的连接和接口，子任务的维护和调度等。
• 其次，设计可扩展的并不简单。
• 路径探索模块，用于支持测试输入的全局优先级。

PACCI将路径探索算法放在减少子任务中，以便它具有由映射子任务产生的所有数据的全局视图，并允许用户包括更多路径探索算法。

我们已经在Spark和Mesos之上实现了PACCI。 初步评估结果表明，PACCI与计算节点的数量呈线性关系，在资源波动和节点故障下的效率方面表现良好。

主要贡献：

•我们提出了PACCI，这是一种新颖的并行执行器，可以加速执行，并通过利用云来适应计算资源的变化。
•我们实现了PACCI，初步结果表明PACCI具有可扩展性，即使存在资源波动和节点故障也能很好地运行。 PACCI是https://github.com/SymSecGroup/PACCI的开源软件。

如何确保每个程序路径的探索独立于其他路径？

遵循MapReduce编程模型，PACCI使用映射子任务来探索单个路径。 每个map子任务都使用一个测试输入运行程序，收集路径条件，并生成新的测试输入（如果有的话）。 我们使用驱动程序来维护和分派map subtasks，以便map subtasks不需要相互协调。

如何实现可扩展的globalaware路径探索模块？

我们在减少例程中实现路径探索算法，以便PACCI可以处理所有未执行的测试输入，即使它们位于不同的从站中。 此外，我们在单独的模块中包含路径探索的代码，因此分析人员可以通过简单地扩展reduce子任务例程来添加自己的路径探索算法。

Test-Driven Development for Parallel Applications

2017 Second International Conference on Information Systems Engineering

John W. Burris

本文将介绍一种使用TDD进程进行并行请求开发的方法，介绍TestDriven开发过程，一个用于并行编程的示例API，以及由xUnit单元测试框架促进的单元测试。

MPI

The MPI standard is widely used in the high-performance computing industry and has multiple cross-platform implementations.

MPI规范允许特定于并行应用程序的逻辑错误，这些错误不容易使用TDD捕获。

死锁和竞争条件是两个这样的逻辑错误

竞争条件是执行结果可以根据从其他异步执行线程接收的消息顺序而改变的条件。

用于确定这些错误中任何一个错误的可能性的用例的有效性是未来研究的一个领域。

将TDD应用到并行应用的步骤：

识别将在单个执行线程中运行的应用程序的部分（在需求中给出）以及将并行运行的软件部分。

在单个执行线程中运行的部分采用传统的TDD方法，并且可以和并行部分独立开来。

并行软件设计的四部分：

partition(分区), communication(通信), agglomeration(集聚), and mapping(映射).

分区涉及将系统分解为较小的任务。 通信是为了实现并行性而创建如何传递消息的计划。 集聚将流程组合在一起以提高表现。 映射将特定任务分配给特定进程。

Designing and Building Parallel Programs: Concepts and Tools for Parallel Software Engineering. Reading,

COMPI:Concolic Testing for MPI Applications

Concolic Testing：concrete and symbolic混合实际执行和符号执行的测试

Concolic执行维护一个实际状态和一个符号化状态：实际状态将所有变量映射到实际值，符号状态只映射那些有非实际值的变量。Concolic执行首先用一些给定的或者随机的输入来执行程序，收集执行过程中条件语句对输入的符号化约束，然后使用约束求解器去推理输入的变化，从而将下一次程序的执行导向另一条执行路径。

**就是在已有实际输入得到的路径上，对分支路径条件进行取反，就可以让执行走向另外一条路径。**这个过程会不断地重复，加上系统化或启发式的路径选择算法，直到所有的路径都被探索，或者用户定义的覆盖目标达到，或者时间开销超过预计。

COMPI:

MPI应用程序的第一个实用的concolic测试工具。

对MPI程序检测的要求：

• 检测MPI语义相关的错误
• 大规模检测或诊断复杂的错误
• 最终复制并表现出非确定性错误

MPI程序的特点：

• 只测试一个进程的标准的concolic测试对于运行多个进程的MPI应用程序来说是不够的。
• 测试不能发现只能在使用一定数量的进程后才能执行的分支，因为它忽略了MPI语义使得它无法改变进程的数量。

开销：

• 首先，太大的输入会使测试变得非常慢，有时甚至会因为所需的内存超出计算平台的内存限制而失败。
• 其次，使用相同的重量级仪器运行所有进程会产生不必要的高开销，因为并非所有进程都需要执行符号执行。
• 第三，在存在表征MPI应用程序的循环时浪费了太多的努力，因为循环导致生成太多冗余约束并且解决以及使用它们进行测试无助于提高分支覆盖率。

COMPI降低开销的策略:

输入上限、双向控制、减少约束集

COMPI的工作流程:

Instrumentation

Testing

由于其对MPI语义的了解，它通过改变进程数量和焦点过程自动驱动测试。 记录所有流程的覆盖范围可确保准确记录整体覆盖范围。

选用的搜索策略：

BoundedDFS

Parallel mutation testing

并行运行突变体以提高变异测试的效率

变异测试的开销：

the number of mutants generated

on the number of test cases

Nm:number of mutants(变异体的数量)

Gt:generation time of one mutant一个变异体的产生时间

Ntc:number of test cases测试用例的数量

Et:execution time of one test case一个测试用例的执行时间

M${}_t$=G${}_t$*N${}_m$+max{Et${}_i$ * N${}_{tci}$ * (N${}_{mi}$+1)}

因此，研究并行变异测试技术是减少突变体执行时间而不失去有效性的必要任务。

本论文主要关注测试执行阶段的执行时间

降低执行阶段的计算成本。

文章结构：

第2节描述了并行变异测试的一些工作，并证明了对该技术的新研究的必要性。

第3节描述了研究中使用的分布算法。

第4节用于执行实验的工具。

第5节显示了实验的设计。

第6节描述了获得的结果。

第7节给出了一些结论和未来的工作。

作者提出了三种分布算法：

按原始顺序分发变异体，随机均匀的分发变异体，突变型变异体的均匀分布。

关于静态分布算法，作者确定最有效的算法通过突变类型分配突变体，因为它实现了最高的加速。

突变体分布的动静态策略以及测试用例分布的动静态策略。

优化计算资源的使用：

通常，使用比处理器更多的块并且具有相对小的块来获得最佳结果。chunk是一组发送到处理器的任务。

动态策略：

‘Guided Self-Scheduling’ 引导式自我调度

Factoring Self-Scheduling保理自我调度

‘Trapezoid Self-Scheduling’ 梯形自我调度

‘Quadratic Self-Scheduling’ 二次自我调度

实现了两种静态和三种动态算法

• DMBO(Distribute Mutants Between Operators )在算子之间分配突变体。根据变异体集合划分。这是一种静态算法，将给定变异算子生成的突变体分布在与处理器一样多的块中。每个块包含m${}_{op}$/p个变异体。这种算法减少了节点之间通信的时间，并且网络流量是最小的。因为每个处理器仅在突变过程中接收一次块。但是每个处理器的处理时间不同。 然而，由于突变体和测试用例的性质，并非所有的执行都需要相同的时间，因此可能和Offutt等人的工作一样。 [16]显示，某些处理器将先于其他处理器完成，总处理时间将是最慢处理器所用的时间。
• DTC(Distribute Test Cases )适应负载均衡策略的变异测试。静态算法，**根据测试用例的数量划分。**每个块包含t/p个测试用例。缺点是处理器之间不通信。
• GMOD(Give Mutants On Demand )按需提供突变体算法。是一个动态算法。将执行分成仅包含一个具有所有测试用例的突变体的块。因此，分几次将块传送到并行处理器，直到所有块都被传送出去。增加了节点之间的通信，因为许多块被发送到每个处理器并且网络流量也增加了。因此网络特性可能对总时间有很大影响。由于算法的动态特性，所有并行处理器几乎可以同时完成。
• GTCOD(Give Test Cases On Demand )适应负载均衡分配策略的。动态算法，将执行分成块，每个块只包含一个测试用例和所有突变体。增加了节点之间的通信，因为许多快被发送到每个处理器并且网络流量增加，这个算法增加了传输GOD的算法，因为突变体的数量通常远高于测试用例的数量。处理器之间没有通信。
• PEDRO( Dynamic Ranking and Ordering )动态排序算法。包含俩个阶段：**1，排名阶段类似于DMBO算法。2，排序阶段与GMOD算法类似。**第一个阶段不会增加网络流量，第二个阶段可以防止某些并行处理器在其他处理器之前完成。可以配置的两个参数：1，用户确定的整数用于确定每个阶段中要执行的块的数量。2，并行处理器的数量，提供使算法适应并行系统所需的信息。排名阶段向每个处理器发送相同数量的工作。这个阶段对于后续订购阶段的节点排名很有用。 在此第一阶段，执行仅发送到处理器节点一次，从而减少了网络流量。

工具介绍：

Bacterio：

local node;remote executor node;facade node

每一个节点都可以放在不同的计算机上。

local node:

create mutants, execute mutants and view results

执行过程：

突变体创建和结果计算在本地节点中执行，并且只有测试用例的执行在远程执行器节点上并行执行。这些节点接收测试和突变体，执行突变体并发送回 检测结果。 外观节点负责根据所选择的分发算法从本地节点接收所有突变体和测试以及它们在远程执行器节点之间的分布。

本地节点：

它生成突变体并使用从其他节点获得的测试结果计算测试实现的突变分数。

远程节点：

充当执行程序服务器，当突变过程开始时，该节点未被通知并询问块（由突变体和测试集组成）。当接收到存储空间时，远程执行程序会执行测试，以获得包含块的重要信息，并将测试结果发送回去。 然后它要求更多的执行。 如果没有更多的执行要运行，它会再次等待另一个突变过

外观节点:

实验在四个应用程序上进行。 其中三个用于比较第3节中描述的五种算法。然后将两种最相似的算法与第四种应用进行比较。 所有应用程序都是用Java编写的。

这四种应用程序分别使:

Monopoly:用程序模拟Monopoly棋盘游戏。

Cinema：电影院管理系统。

Chess：在线国际象棋游戏，实验中仅使用服务器部分。

Analysis package of Commons Math:包含数学和统计功能的类库。

每个应用都有一个Junit的测试套件。

实验结果及分析：

PEDRO and GMOD 算法获得了较好的结果。 DMBO是第三个比较好的算法。

主要原因在于等待时间。另一个原因是通信时间的影响。因此，等待时间对总时间几乎没有影响，这意味着以等待时间为代价减少总时间的算法（GMOD和PEDRO算法）优于反向算法（DMBO算法）。

remoteExecutor节点无法知道被其他remoteExecutor节点杀死的突变体，因此，它可能执行已经被另一个节点杀死的突变体。

the DTC and GTCOD algorithms ran more executions than the others, with GTCOD algorithm being worse than DTC algorithm

(i)研究并行执行技术在增加并行节点数量时的行为，以及（ii）研究该技术在同构和异构环境中的行为。

当计算机数量显着增长时，就会达到一个点，效率不会增加而是会降低。

并行执行技术可以快速有效地降低突变的计算成本。 由于它是第一个快速降低计算成本的部分，因此只需要少量计算机即可。 例如，在实验中使用具有八个并行计算机的环境，即8C1异构环境。 在Analysis包的情况下，总时间将执行时间减少了86.55％（从6131减少到825秒）。