首页> 外文期刊>Automated software engineering >Estimating the feasibility of transition paths in extended finite state machines
【24h】

Estimating the feasibility of transition paths in extended finite state machines

机译:估计扩展有限状态机中过渡路径的可行性

获取原文
获取原文并翻译 | 示例

摘要

There has been significant interest in automating testing on the basis of an extended finite state machine (EFSM) model of the required behaviour of the implementation under test (IUT). Many test criteria require that certain parts of the EFSM are executed. For example, we may want to execute every transition of the EFSM. In order to find a test suite (set of input sequences) that achieves this we might first derive a set of paths through the EFSM that satisfy the criterion using, for example, algorithms from graph theory. We then attempt to produce input sequences that trigger these paths. Unfortunately, however, the EFSM might have infeasible paths and the problem of determining whether a path is feasible is generally undecidable. This paper describes an approach in which a fitness function is used to estimate how easy it is to find an input sequence to trigger a given path through an EFSM. Such a fitness function could be used in a search-based approach in which we search for a path with good fitness that achieves a test objective, such as executing a particular transition, and then search for an input sequence that triggers the path. If this second search fails then we search for another path with good fitness and repeat the process. We give a computationally inexpensive approach (fitness function) that estimates the feasibility of a path. In order to evaluate this fitness function we compared the fitnessrnof a path with the ease with which an input sequence can be produced using search to trigger the path and we used random sampling in order to estimate this. The empirical evidence suggests that a reasonably good correlation (0.72 and 0.62) exists between the fitness of a path, produced using the proposed fitness function, and an estimate of the ease with which we can randomly generate an input sequence to trigger the path.
机译:在扩展的有限状态机(EFSM)模型的基础上,对被测实现(IUT)的所需行为进行自动化测试引起了极大的兴趣。许多测试标准要求执行EFSM的某些部分。例如,我们可能要执行EFSM的每个转换。为了找到实现这一目标的测试套件(一组输入序列),我们可能首先使用例如图论算法通过EFSM得出一组满足标准的路径。然后,我们尝试产生触发这些路径的输入序列。然而,不幸的是,EFSM可能具有不可行的路径,而确定路径是否可行的问题通常是不确定的。本文介绍了一种方法,其中使用适应度函数来估计查找输入序列以触发通过EFSM的给定路径的难易程度。可以在基于搜索的方法中使用这样的适应度函数,在该方法中,我们搜索具有良好适应性的路径来实现测试目标,例如执行特定的过渡,然后搜索触发该路径的输入序列。如果第二次搜索失败,那么我们将搜索另一条适合的路径并重复该过程。我们提供了一种计算上不昂贵的方法(适应度函数),该方法可以估算路径的可行性。为了评估此适应度函数,我们将fitnessrnof路径与通过搜索触发路径可以轻松生成输入序列的路径进行了比较,并使用随机采样进行了估算。经验证据表明,使用拟议的适应度函数生成的路径的适应度与我们可以随机生成输入序列以触发该路径的难易程度的估计值之间存在合理良好的相关性(0.72和0.62)。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号