将变异测试和蜕变测试应用于 MiniZinc 调度问题

《Information and Software Technology》：Applying mutation testing and metamorphic testing to MiniZinc scheduling problems

　　

摘要

背景：软件测试对于确保复杂优化和约束满足系统的质量至关重要。尽管面向命令式编程语言的测试技术已经相当成熟，但将其应用于MiniZinc等声明式语言仍然在很大程度上被忽视。

目标：本文通过研究蜕变测试（MT）和变异测试在MiniZinc调度问题模型中的有效性，来弥补这一研究空白。

方法：我们系统地设计并实现了专门针对MiniZinc和调度约束的新型蜕变关系（MRs）。此外，我们引入了一套42个变异算子，旨在暴露声明式建模中常见的故障。我们通过以资源约束项目调度问题（RCPSP）作为基准的广泛实证评估来验证所提出的方法。

结果：我们的研究发现表明，所提出的蜕变关系在揭示传统测试技术和原始源代码测试套件未能检测到的细微缺陷方面非常有效。此外，对42个变异算子的分析表明，其中很大一部分能够暴露关键故障，为增强MiniZinc程序测试套件的完整性和可靠性提供了有价值的指标。

结论：本研究推进了约束编程模型测试领域的现有技术，促进了在关键应用领域（如工业优化环境）中开发更加健壮和可靠的解决方案。

引言

软件测试是软件开发中一项基本且必要的任务，需要使用各种专门为此目的设计的技术[1]。这些技术可以是通用的，也可以专门针对特定的编程语言或应用领域进行定制。在编程中一个经常涉及的应用领域是调度，其目标是在前驱关系和资源约束下实现最优解。对于此类问题，声明式编程语言（如MiniZinc [2]）具有特别的优势，因为它们允许对问题规范进行近乎直接的实现，并通过求解器搜索或优化潜在解。尽管成熟的软件测试技术已经存在，但其中一些尚未被广泛应用于约束满足和优化背景下这些声明式语言的程序测试。

在此背景下，变异测试[3]——在C、C++、Java等各种编程语言和不同编程范式中都有现成的工具——提供了一个有前景的机会。因此，为带有约束的程序实现变异测试系统并评估测试套件质量，代表了一项重大挑战和贡献。与此同时，蜕变测试已证明是一种虽然比变异测试年轻但在近年来取得巨大发展和成功的技术，并且有专门为其举办的会议[4]、[5]。利用蜕变测试来改进测试套件特别值得探索，因为这是一种在问题领域被考虑在内的技术。

因此，基于上述原因，本文的主要贡献为：

- 为一个新领域（调度程序测试）设计和实现蜕变关系。
- 一组针对MiniZinc的变异算子，用于使用变异测试评估该语言的测试。
- 结合NP难调度问题——资源约束项目调度问题[6]、[7]（RCPSP1）以及与RCPSP相关的蜕变关系进行实验，旨在改进测试套件。
- 分析MiniZinc变异算子的有效性。
- 分析所实现的蜕变关系的有效性。

本文的结构如下：第2节描述了本文其余部分使用的背景知识和定义；第3节解释了本文提出的方案；第4节介绍了实验所使用的方法论；第5节呈现了实验结果及其讨论；第6节讨论了相关工作；第7节描述了有效性威胁；最后第8节给出结论和未来的工作。

节选部分

约束编程中的调度问题

约束编程是一种求解组合问题的范式，其中变量之间的关系以约束的形式表达[8]。当一个约束问题中的所有变量都被实例化且所有约束都被满足时，该问题即被求解。一般来说，变量遍历一个有限值集合，这对应于有限域上的约束编程[9]。

定义1 约束满足问题[2]（CSP）被定义为一个三元组（X, Dom, C），其中X = (x?, …, x?)是一个元组。

提案

本提案旨在评估按照固定方案实现调度问题的MiniZinc程序，采用两种测试方法。首先，我们将采用蜕变测试，设计并实现蜕变关系以生成增强型测试套件。其次，我们将应用变异测试。鉴于目前尚不存在针对MiniZinc的变异系统，我们将开发并实现适当的变异算子以创建变异体，从而评估测试套件的效力。

方法论

为了评估所提出的方法（该方法结合了上述两种软件测试技术——变异测试和蜕变测试），本节提出了一些研究问题，并描述了实验所基于的程序。

结果与讨论

本节分析了实验所得结果，并回答了研究问题。此外，还对结果进行了讨论。

相关工作

关于相关工作，约束求解和蜕变测试在过去已以不同方式相结合。然而，现有研究关注的是其他方面或领域，其方法与我们的有所不同。首先，Gotlieb和Botella在[27]中使用约束逻辑编程来寻找使给定蜕变关系失败的测试用例。他们给出了一些示例，可以证明程序满足这些蜕变关系。该论文提出了一种使用该方法的原型实现。

有效性威胁

以下我们讨论了上一节所述实验结果的有效性威胁。

结论与未来工作

总之，本研究成功展示了将蜕变测试和变异测试应用于MiniZinc开发的约束编程模型的显著优势。我们证明，通过系统地设计蜕变关系和全面的变异算子套件，可以有效地检测MiniZinc程序中的各种缺陷，从而增强这些模型的可靠性和可信度。我们利用资源约束项目调度问题（RCPSP）进行了实证研究。

贡献者声明

Ma del Carmen de Castro-Cabrera：写作 – 审阅与编辑，写作 – 原创草稿，验证，软件，方法论，调查，构思。Sonia Estévez-Martín：写作 – 审阅与编辑，写作 – 原创草稿，验证，软件，资源，方法论，调查，数据整理，构思。Luis Llana Díaz：写作 – 审阅与编辑，写作 – 原创草稿，验证，软件，资源，方法论，调查，形式分析，数据整理。

利益冲突声明

作者声明他们没有任何已知的竞争性经济利益或个人关系可能影响本文报告的工作。

致谢

第一和最后一位作者获得了由MICIU/AEI/10.13039/501100011033和ERDF/EU资助的I+D+i拨款PID2021-122215NB-C33（AwESOMe）的支持。

第二和第三位作者获得了西班牙科学与创新部国家研究局（AEI）的拨款PID2021-122215NB-C31（AwESOMe）以及马德里自治区的拨款TEC-2024/COM-235（DESAFíO-CM）的支持。

Ma del Carmen de Castro-Cabrera | Sonia Estévez-Martín | Luis Llana Díaz | Antonio García-Dominguez
卡迪斯大学 Puerto Real (Cádiz), 安达卢西亚, 西班牙