Model-based mutant equivalence detection using automata language equivalence and simulations
Model-based mutant equivalence detection using automata language equivalence and simulations
复制标题
DOI：
10.1016/j.jss.2018.03.010
复制
发表时间：
2018-07
期刊：
影响因子：
--
通讯作者：
Andreas Classen;P. Heymans;Pierre-Yves Schobbens
中科院分区：
文献类型：
--
作者：
Andreas Classen;P. Heymans;Pierre-Yves Schobbens
突变分析是一种用于评估测试套件强度的流行技术。它依赖于突变分数，这表明它们的缺陷揭示潜力。然而，存在其行为等同于原始系统的突变体，这浪费了分析资源并且妨碍了100%突变评分的满足。对于有限行为模型，等价突变问题（EMP）可以转化为非确定性有限自动机的语言等价问题。然而，这些解决方案是相当昂贵的，使得计算难以承受时，用于解决电磁脉冲。在本文中，我们报告了我们的评估国家的最先进的精确的语言等价工具和两个我们提出的语法。我们使用了12个模型，由（多达）15，000个状态和4710个突变体组成。我们引入了一个随机和突变偏置的模拟算法，作为比较的基线。我们的研究结果表明，在弱突变的情况下，精确的方法往往快十倍以上。对于强突变，对于大于300个状态的模型，我们的有偏模拟可以快1000倍，同时将错误分类非等效突变体的错误限制为平均8%。因此，我们的结论是，可以结合的方法，以提高效率。
Mutation analysis is a popular technique for assessing the strength of test suites. It relies on the mutation score, which indicates their fault-revealing potential. Yet, there are mutants whose behaviour is equivalent to the original system, wasting analysis resources and preventing the satisfaction of a 100% mutation score. For finite behavioural models, the Equivalent Mutant Problem (EMP) can be transformed to the language equivalence problem of non-deterministic finite automata for which many solutions exist. However, these solutions are quite expensive, making computation unbearable when used for tackling the EMP. In this paper, we report on our assessment of a state-of-the-art exact language equivalence tool and two heuristics we proposed. We used 12 models, composed of (up to) 15,000 states, and 4710 mutants. We introduce a random and a mutation-biased simulation heuristics, used as baselines for comparison. Our results show that the exact approach is often more than ten times faster in the weak mutation scenario. For strong mutation, our biased simulations can be up to 1000 times faster for models larger than 300 states, while limiting the error of misclassifying non-equivalent mutants as equivalent to 8% on average. We therefore conclude that the approaches can be combined for improved efficiency.