Minimizing Characterizing sets
Minimizing Characterizing sets
复制标题
最小化特征集
DOI：
10.1016/j.scico.2021.102645
复制
发表时间：
2021
影响因子：
1.3
通讯作者：
Cengiz Türker U
中科院分区：
文献类型：
--
作者：
Cengiz Türker U
确定性有限状态机（FSM）的特征集（CS）是一组输入序列，在它们之间分离（区分）m的所有状态。CSs在几种测试生成技术中使用，这些技术返回具有保证故障检测能力的测试套件。CS中输入序列的数量直接影响应用结果测试套件的成本。在本文中，我们研究了从FSM中导出最小CS的决策问题的复杂性，证明了用k序列检验CS的存在性是pspace完全的。我们还考虑CS的长度，它是CS中输入序列长度的总和。结果表明，判断是否存在长度最大的CS的问题是np完全的。受这些结果的启发，我们引入了一种启发式方法，从确定性FSM构建CS，目的是最小化输入序列的数量。我们通过评估其在经典测试生成算法（w方法）中使用时的效果来评估所提出的算法。在评估中，我们使用了随机生成的fsm和基准fsm。结果表明，该算法将测试序列的数量平均减少了37.3%，测试套件的总长度平均减少了34.6%。
A characterizing set (CS) for a deterministic finite state machine (FSM)Mis a set of input sequences that, between them, separate (distinguish) all of the states ofM. CSs are used within several test generation techniques that return test suites with guaranteed fault detection power. The number of input sequences in a CS directly affects the cost of applying the resultant test suite. In this paper, we study the complexity of decision problems associated with deriving a smallest CS from an FSM, showing that checking the existence of a CS withKsequences is PSPACE-complete. We also consider the length of a CS, which is the sum of the lengths of the input sequences in the CS. It transpires that the problem of deciding whether there is a CS with length at mostKis NP-complete. Motivated by these results, we introduce a heuristic to construct a CS, from a deterministic FSM, with the aim of minimizing the number of input sequences. We evaluated the proposed algorithm by assessing its effect when used within a classical test generation algorithm (the W-method). In the evaluation, we used both randomly generated FSMs and benchmark FSMs. The results are promising, with the proposed algorithm reducing the number of test sequences by 37.3% and decreasing the total length of the test suites by 34.6% on average.