Clang前端的F-ASTMut突变优化技术及其应用

软件影响16（2023）100500原始软件出版物使用Clang前端的F-ASTMut突变优化技术Sten Vercammena，Serge Demeyera，Markus Borgb比利时安特卫普大学b瑞典隆德RISE研究所AB，瑞典A R T I C L E I N F O保留字：突变测试工具ClangC++语言A B标准F-ASTMut是一个基于操作的C语言家族的开源突变测试研究工具抽象语法树该工具旨在进行详细的测量、分析和优化技术的调整。F-ASTMut的目标是分析优化技术的加速比，以最终实现工业环境中的突变测试。目前，F-ASTMut具有四种优化技术：无效突变体的排除方案，测试范围缩小到仅覆盖相关突变体，突变体模式和分流突变测试。该实现依赖于Clang前端，允许未来的工作扩展或构建在我们的解决方案之上代码元数据当前代码版本v0.2用于此代码版本的代码/存储库的永久链接https://github.com/SoftwareImpacts/SIMPAC-2022-257Reproducible Capsule的永久链接https://codeocean.com/capsule/3514968/tree/v1法律代码许可证GPL 3.0使用git的代码版本控制系统使用C++的软件代码语言、工具和服务 巨蟒， bash、SQL编译要求，操作环境依赖性llvm，llvm-dev，clang，libclang-dev，cmake sqlite3，libsqlite 3-dev，git，cmake，bash如果可用开发人员文档/手册链接https://github.com/Sten-Vercammen/F-ASTMut问题支持电子邮件Sten. uantwerpen.be1. F-ASTMut描述F-ASTMut是一个开源的基于抽象语法树的变异测试研究工具，用于C语言家族。 该工具实现了各种优化技术，以加快突变测试。变异测试的主要目的是验证测试集的故障检测能力。为此，人工断层-称为突变体-被注入 到源代码中。对于每个故障，都需要运行测试套件。导致至少一个失败的测试用例的突变体的分数提供了测试套件的故障检测能力的指示。检测到的变异体越多，测试套件就越强大作为一种研究工具，F-ASTMut的主要目的是从而实现细粒度的性能分析。该工具旨在收集各种优化技术的影响统计数据。突变测试过程的每个阶段都是分开的，即突变体生成，编译和执行[1]。对于每个阶段，精确的时间收集数据。然后，可以将不同的优化技术或所述技术的版本相互比较或分析以进一步改进。2. F-ASTMut内置技术F-ASTMut结合了一个未优化的基线技术和四个互补的优化：1. 一种排除无效突变体的检测技术。2. 一个测试套件减少技术，以执行无法到达的突变体和一个改进的版本，只执行那些测试，达到特定的突变体。3. 一种突变模式技术，通过一次编译所有的突变体来4. 一种分流技术，通过从突变点而不是从测试套件的开头开始启动突变体来减少执行开销。本文中的代码（和数据）已由Code Ocean认证为可复制：（https://codeocean.com/）。更多关于生殖器的信息徽章倡议可在https://www.elsevier.com/physical-sciences-and-engineering/computer-science/journals上查阅。∗ 通讯作者。电子邮件地址：Sten. uantwerpen.be（S. Vercammen），Serge. uantwerpen.be（S. Demeyer），markus.borg@ cs.lth.se（M. Borg）。https://doi.org/10.1016/j.simpa.2023.100500接收日期：2022年11月22日;接收日期：2022年12月25日;接受日期：2023年3月19日2665-9638/©2023作者。由Elsevier B.V.出版。这是一篇开放获取的文章，使用CC BY许可证（http://creativecommons.org/licenses/by/4.0/）。可在ScienceDirect上获得目录列表软件影响期刊主页：www.journals.elsevier.com/software-impactsS. Vercammen，S.Demeyer和M.博格软件影响16（2023）1005002图1.一、 F-ASTMut实现策略和算法步骤（第一步在底部）。所有优化都使用相同的突变体生成方法，以确保可以比较每次优化的结果加速。图1说明了不同的优化以及它们对编译时间和测试执行时间的影响。这个数字应该从下到上，从左到右阅读• 未优化。首先，（这适用于所有优化）必须生成突变体本身;如黄色框所示 在底部这是通过访问者遍历Clang编译器前端提供的抽象语法树来实现的。然后，对于每个注入的突变体，必须重新编译完整的源代码。我们将其分为三类：（1）可达到的突变体，由相当大的橙色框显示;（2）不可达到的突变体;（3）无效突变体。我们认为最后两个是开销，因为无法到达的突变体将永远不会在执行过程中检测到，因此其结果是预先确定的。 在未优化的方法中，我们用蓝色表示这一点和其他开销。无效的突变体将无法编译，因此它们的结果也是预定的。在这个时间点上，我们有一个编译版本的系统为每个注入突变。剩下要做的是对每个突变体进行所有测试，如标记为T1-T5的绿色和红色框所示;绿色标记通过测试（突变体未被杀死），而红色标记失败的测试（突变体被杀死）。理想情况下，每个突变体都被杀死。F-ASTMut中包含的第一个优化是在突变体的生成中。在这里，Clang的语义分析器允许我们检测无效的突变体并排除它们;这包括在黄色框中。对于第二次优化，使用代码插入来识别不可达突变体;如紫色框所示利用这两种优化允许从未优化的方法中排除蓝框。• 示意图模式技术使用运行时配置参数选择适当的突变体，一次注入所有突变体。该技术要求所有注入的突变体都是有效的，因此需要在开始时进行额外的步骤：“排除无效突变体”。这里我们只需要编译一次系统，因此显示编译时间的橙色块减少了，并且编译无效突变体的开销也被删除了。测试执行时间（红色和绿色框）不受影响。• 可达架构。F-ASTMut中包含可达突变体的改进版本。在这里，而不是只检测完全无法到达的突变体，该技术检测哪些测试用例到达并执行突变体。我们需要一个额外的分析（紫色的块• 分流最后一种优化技术从突变点而不是从测试套件的开始启动突变。与之前的优化相比，我们现在可以减少每个单独测试的测试执行时间3. F-ASTMut底层技术Clang项目为C系列编程语言提供了语言前端和工具对于LLVM项目[https://clang.llvm.org]LLVM项目是一个模块化和可重用的编译器和工具链技术的集合。[...]能够支持任意编程语言的静态和动态编译。[LLVM.org]LLVM是围绕低级语言独立的中间表示LLVM IR设计的编译工具的集合。S. Vercammen，S.Demeyer和M.博格软件影响16（2023）1005003表1Clang和LLVM IR突变测试工具。工具名称Mutation levelMutation operators突变优化AccMutLLVM IRAOR、ROR、LCR、SDL、. . .变异模式，模状态CCmutatorLLVM IR并发变异运算符DextoolAST AOR、ROR、LCR、SDL、UOI分布、突变体示意图、通过代码覆盖率识别未达到的突变体MartLLVM IR操作员组MuCPP AST类水平突变体还原突变体集MullLLVM IR LLVM fragments基于调用深度限制突变体总数SRCIROR AST AOR、LCR、ROR、ICR微生物等效性，通过代码覆盖率排除未达到的突变体该项目包括将源代码转换为LLVM IR的前端，重写LLVM IR以变得更快的优化器，以及从LLVM IR为不同架构生成机器代码的后端。Clang是LLVM最著名的前端。它支持C家族中的语言，如C、C++和C++-C等。在内部，Clang将程序表示为抽象语法树（AST）。Clang还包括一个语义分析器，允许进行类型检查和其他编译时检查。此外，Clang包含几个基于访问者模式的库，允许将更多的分析或转换添加到前端。LLVM和Clang是为C语言家族构建静态分析工具的事实标准。这些工具在AST水平或LLVM IR水平上改变程序。在LLVM IR级别进行突变的优点是它们将适用于任何前端，但缺点是在LLVM IR中注入的突变体很难甚至不可能追溯到测试中原始代码中的源表示，这允许生成许多无效突变体[2]。另一方面，程序的AST表示接近于源代码。因此，在该水平上突变提供了良好的可追溯性，因为这些突变体可以在源代码中表示。在AST级别突变的另一个优点是，前端语义分析器可以用于确保突变的代码是编译时正确的，有效地消除了无效突变体的公认问题。F-ASTMut依赖于Clang的LibTooling库，以及它从AST中遍历所有声明、语句和表达式的能力。对于这些声明、语句和表达式中的每一个，都将创建变体，即所谓的突变体。这是通过使用变异操作符来完成的，这些操作符描述了哪些代码片段应该被更改以及根据哪些规则进行更改。例如，AOR（算术运算符替换）变异运算符描述了算术运算符应该被其他算术运算符替换。例如，驻留在二进制表达 式 "“ 中 的 乘 法 ������”“ 运 算 符 可 以 通 过 将 乘 法 替 换 为 ”+“ 、 ”-“、”scin“和”%“运算符来创建突变体。为了确保操作符替换的可追溯性，F-ASTMut存储了发生突变的文件名、原始操作符开头和结尾的偏移量以及突变体本身。对于每个执行的突变体，F-ASTMut存储是否到达突变体，运行相应的测试用例需要多长时间，以及突变体是否被杀死。由于某些突变体在执行过程中可能会导致无限循环，因此用户可以为每个突变体设置最大执行时间。如果测试套件无法在此时间内完成执行，F-ASTMut将停止测试执行并记录突变体超时。超时的突变体可以被认为是被杀死的，因为它们在连续整合测试中也会超时。这些信息可以被提取出来形成一个报告，告知开发人员哪些突变体从未被测试套件检测到，以及在哪里在它们所在的源代码4. 相关工作在表1中，我们列出了基于Clang和/或LLVM IR的最突出的突变测试工具，按字母顺序排列，功能和优化。我们简要地解释了他们采用了哪些优化措施，并参考了量化证据（如果存在）。AccMut（基于IR）具有突变模式方法和称为模状态的优化，该优化将突变模式技术应用于局部状态。他们已经证明了突变模式方法的平均加速比为8.95倍[3]。CCmutator（基于IR）是一个LLVM IR突变测试工具，专门设计用于突变并发结构[4]。Dextool（基于AST）是一个开源框架，用于测试和静态分析（通常是安全关键的）代码。1它允许分布式突变测试与突变模式方法相结合，并可以排除位于未覆盖代码中的突变测试套件。Mart（基于IR）目前支持18个不同的操作符组（68个片段和816个操作符）[5]。这些运算符组与LLVM IR语法匹配以创建突变体。用户可以实现额外的操作员组，以进一步扩展其能力。Mart在内存中实现了Trivial Quantifier Equivalence，以消除等价和重复的突变体[6]。MuCPP（基于AST）通过遍历ClangAST并使用版本控制系统将突变体存储在不同分支中来生成突变体[7]。MuCPP在类级别实现了突变。这些包括与继承、多态性和动态绑定、方法重载、异常处理、对象和成员替换等相关的变化。该研究旨在通过消除所谓的非生产性突变体来减少需要执行的突变体总量。这些包括等效突变体、无效突变体、易杀死突变体和死代码中的突变体Mull（基于IR）是一个开源的突变测试工具2，它修改LLVM的片段中间 表示（LLVM IR）。它只需要重新编译修改后的片段来执行突变体，保持编译开销低[2]。Mull包括一个do-less优化，您可以将执行的突变体限制为从测试用例开始的特定调用深度内的那些突变体。SRCIROR（基于AST或IR）是一个工具集，可以设置为在AST水平或LLVM IR水平执行突变测试[8]。这两种变体都实现了AOR、LCR、ROR、ICR突变操作符。SRCIROR允许根据代码覆盖率指标过滤掉不可访问的突变体。它还允许使用平凡的编译器等价来过滤掉一些等价的突变体[6]。目前最先进的技术表明，在LLVM和Clang编译器框架之上，C语言家族的突变分析是可能的。然而，在何种程度上的各种优化策略允许减少编译和执行开销是未知的。特别地，不存在允许对不同优化和/或其组合进行详细测量和分析的工具。第1https://github.com/joakim-brannstrom/dextool2 https://github.com/mull-project/mullS. Vercammen，S.Demeyer和M.博格软件影响16（2023）1005004表2优化标志F-ASTMut。优化标志传统实现EXPORT_MUTANTS EXPORT_NON_COMPILING_MUTANTS检测可达突变体EXPORT_REACHABLE_MUTANTS突变图式 &出口_突变体Split-Stream SPLIT_STREAM表3目前在F-ASTMut中实现的变异操作符。5. F-ASTMut的影响关系运算符是，=，>，>=，==，！为算术运算符为：+、−、、scin、%逻辑连接器包括：||、&&、、|、&哪些突变体可以通过哪些测试用例到达。然后，可以利用该信息来加速传统的实施方式或另一实施方式。使用F-ASTMut，我们已经看到与基线相比，突变测试加速高达30.5倍，这是一个未优化的实现[9]。F-ASTMut允许研究人员测量突变测试优化的加速影响和潜在延迟。F-ASTMut还包括突出的突变优化技术，如突变模式，分流突变测试和测试套件减少技术，只执行那些测试，达到特定的突变。 我们将该工具开源，以便可以扩展和/或调整。研究人员可以利用这个工具来确定突变优化技术的瓶颈在哪里，如何对它们采取行动来改进它们，并定量分析这些改进。例如，我们已经观察到，我们的突变体图式技术，一次编译所有突变体，并允许激活突变体，在运行时，当同一语句中存在许多突变时，会导致相当大的执行开销。F-ASTMut允许我们确定延迟的原因以及如何改进优化的实施。F-ASTMut还允许我们量化我们或其他研究人员对优化技术所做的6. F-ASTMut研究利用率工具的主要部分在工具文件夹下的main.cpp文件中实现。这部分负责分析目标源代码，生成和导出突变体，并使用注入的突变体对相同的源代码进行检测。我们的工具也有配套的脚本，驱动特定优化的执行。每个优化都位于自己的文件夹中。研究人员可以扩展该工具的主要部分或调整附带的脚本，以实现自己的优化或运行自己的实验。F-ASTMut的功能可以通过设置表2中列出了不同的标志。下面我们简要概述F-ASTMut的可能性。F-ASTMut可以生成突变体并将其存储到编号的突变体.csv文件中。该文件包含原始代码的开始和结束位置，以及要取代其位置的变异代码。由于F-ASTMut依赖于 在Clang基础设施上，它可以自动确定生成的突变体是否可以编译。因此，我们有两个不同的标志来导出有效和不可编译的突变体。优化技术可以直接插入主工具，也可以利用附带的脚本来处理生成的突变体。对于我们的传统实现，我们开发了一个附带的传统脚本，将生成的突变体单独插入到代码库中，单独编译它们并运行相应的测试套件。我们的EXPORT_REACHABLE_MUTANTS标志通过在所有突变体的位置内放置标记来检测代码库。运行附带的可访问脚本将执行代码库并收集优化，例如突变模式。对 于 我 们 的 突 变 模 式 技 术 ， 需 要 激 活 SCHEMATA 和 EXPORT_MUTANTS标志。 该技术在主工具中实现，并直接对代码库进行仪表化，以一次包含所有突变体。附带的schemata脚本从导出的mutants.csv文件中提取突变体编号。然后，它单独激活每个突变体，并针对突变的源代码运行测试套件。或者，只有可达到的突变体可以通过结合先前的技术来激活。使用SPLIT_STREAM标志激活分流优化。就像模式优化一样，它对代码库进行检测，并依赖于脚本来针对测试套件运行突变体7. F-ASTMut的局限性和未来的工作在F-ASTMut0.2版本中，我们实现了关系运算符替换（ROR）、算术运算符替换（AOR）和逻辑连接器替换（LCR）（见表3）。当前版本的F-ASTMut可以很容易地扩展到支持其他二元变异运算符和一元运算符。其他变异操作符，如访问修饰符更改（AMC），可以将私有函数更改为公共函数，可能需要更多的开发工作。突 变 模 式 的 驱 动 程 序 依 赖 于 程 序 外 部 的 信 息 ， 通 过 设 置MUTANT_NR变量来控制突变体的激活。MUTANT_NR变量是在运行时初始化的，因此永远不会是const。这意味着F-ASTMut不能在const和constexpr函数中使用该变量，因为这些函数是在编译时计算的，并且MUTANT_NR值在编译时无法知道。因此，F-ASTMut不能像改变非const函数那样改变const和constexpr函数。这包括类型定义（例如使用... ）、模板参数、static_asserts等。因此，在0.2版中，F-ASTMut没有实现这些类型的变化。这可以通过为每个变异操作创建单独的值和/或函数，并通过在使用它们的源代码中的任何地方选择正确的值和/或函数来实现（例如，const val变为const val_0，const val_1，const val_2，. . . ）的。突变模式技术的当前实现使用三元运算符，它是if语句的简写版本。当许多突变体位于一个表达式中时，这会导致一些执行延迟。我们设想，这可以通过使用开关情况[9]实现突变图式技术来优化。在今后的工作中，应解决的突变体卡在无限循环的检测机制的改进。 目前，有一个基于整个测试套件而不是单个测试用例的执行时间的单一超时。几乎一半的分析时间代码短描述ROR关系运算符替换用另一个操作员替换一个操作员AOR算术运算符替换用另一个运算符替换单个算术运算符LCR逻辑连接器更换将单个逻辑连接器替换为反向连接器。S. Vercammen，S.Demeyer和M.博格软件影响16（2023）1005005的时间，为每个测试用例指定一个减少的超时将进一步加速分析。竞合利益这项工作得到了比利时公共资助组织佛兰德研究基金会（FWO）的资助。这里报告的研究没有直接或间接的工业支持引用[1]Y.贾，M. Harman，变异测试发展的分析与综述，IEEE Trans.Softw.2004。Eng.37（5）（2011）649-678。[2]A.杰尼索夫，S. Pankevich，Mull it over：Mutation testing based on LLVM，in：2018IEEE International Conference on Software Testing ， Verification andValidationWorkshops，ICSTW，IEEE，2018，pp. 25比31[3]B. Wang ， Y. Xiong ， Y.什 湖 ， 加 - 地 Zhang ， L. Hao ， Faster mutation analysisviaequivalence modulo states ， in ： Proceedings of the 26th ACM SIGSOFTInternationalSymposium on Software Testing and Analysis， ACM ， New York，NY，USA，2017，pp. 295-306.[4]M.草野角Wang，CCmutator：A mutation generator for concurrency constructsinmultithreadedC/C++applications，in：201328thIEEE/ACMInternationalConferenceon Automated Software Engineering ， ASE ， IEEE ，2013，pp. 722-725[5]T.T. Chekam，M. Papadakis，Y. Le Traon，Mart：LLVM的突变体生成工具，在：2019年第27届ACM欧洲软件工程会议联合会议和软件工程基础研讨会的会议记录，2019年，pp。1080-1084.[6]M. Papadakis ， Y.贾 ， M.Harman ， Y.Le Traon ， Trivial compilerequivalence ： A large scale empirical study of a simple ， fast and effectiveequivalentmutantdetectiontechnique ， in ： Proceedingsofthe37thInternational Conference onSoftware Engineering-Volume 1 ， IEEE Press ，Piscataway，NJ，USA，2015，pp. 936 -946[7]德 尔 加 多 -佩 雷 斯 岛 Medina-Bulo， F. Palomo-Lozano ，A. 加 西 亚 -多 明 格 斯Domínguez-Jiménez， Assessment of class mutation operators for C++ withtheMuCPP mutation system，Inf. 软件。Technol. 81（2017）169[8]F.哈里里，阿。Shi，Srciror：用于c源代码和llvm中间表示的突变测试的工具集，在：第33届ACM/IEEE自动化软件工程国际会议论文集，2018年，pp. 860-863[9]S. Vercammen，S. Demeyer，M. Borg，N. Pettersson，G. Hedin，Mutation testingoptimisationsusingtheClangFront-end，2022，http://dx.doi.org/10.48550/ARXIV。2210.17215，URLhttps://arxiv.org/abs/2210.17215。