检索结果-内蒙古大学图书馆

Accelerating Finite State Machine-Based Testing Using Reinforcement Learning

IEEE TRANSACTIONS ON software engineering 2024年第3期50卷 574-597页

作者： Turker, Uraz Cengiz Hierons, Robert M. El-Fakih, Khaled Mousavi, Mohammad Reza Tyukin, Ivan Y. Univ Lancaster Sch Comp & Commun Lancaster LA1 4YW England Univ Sheffield Dept Comp Sci Sheffield S10 2AH England Amer Univ Sharjah Dept Comp Sci & Engn Sharjah 26666 U Arab Emirates Kings Coll London Dept Informat London WC2R 2LS England Kings Coll London Dept Math London WC2R 2LS England

Testing is a crucial phase in the development of complex systems, and this has led to interest in automated test generation techniques based on state-based models. Many approaches use models that are types of finite state machine (FSM). Corresponding test generation algorithms typically require that certain test components, such as reset sequences (RSs) and preset distinguishing sequences (PDSs), have been produced for the FSM specification. Unfortunately, the generation of RSs and PDSs is computationally expensive, and this affects the scalability of such FSM-based test generation algorithms. This paper addresses this scalability problem by introducing a reinforcement learning framework: the Q-Graph framework for MBT. We show how this framework can be used in the generation of RSs and PDSs and consider both (potentially partial) timed and untimed models. The proposed approach was evaluated using three types of FSMs: randomly generated FSMs, FSMs from a benchmark, and an FSM of an Engine Status Manager for a printer. In experiments, the proposed approach was much faster and used much less memory than the state-of-the-art methods in computing PDSs and RSs.

关键词： Finite state machines reset sequences state identification sequences reinforcement learning Q-value function software engineering/software/program verification software engineering/test design software engineering/testing and debugging

来源：评论

学校读者我要写书评

暂无评论

Testing from Partial Finite State Machines without Harmonised Traces

引用

IEEE TRANSACTIONS ON software engineering 2017年第11期43卷 1033-1043页

作者： Hierons, Robert Mark Brunel Univ London Dept Comp Sci Uxbridge UB8 3PH Middx England

This paper concerns the problem of testing from a partial, possibly non-deterministic, finite state machine (FSM) S. Two notions of correctness (quasi-reduction and quasi-equivalence) have previously been defined for partial FSMs but these, and the corresponding test generation techniques, only apply to FSMs that have harmonised traces. We show how quasi-reduction and quasi-equivalence can be generalised to all partial FSMs. We also consider the problem of generating an m-complete test suite from a partial FSM S: a test suite that is guaranteed to determine correctness as long as the system under test has no more than m states. We prove that we can complete S to form a completely-specified non-deterministic FSM S' such that any m-complete test suite generated from S' can be converted into an m-complete test suite for S. We also show that there is a correspondence between test suites that are reduced for S and S' and also that are minimal for S and S'.

关键词： software engineering/software/program verification software engineering/testing and debugging systems and software checking experiment partial finite state machine

来源：评论

学校读者我要写书评

暂无评论

K-Branching UIO Sequences for Partially Specified Observable Non-Deterministic FSMs

引用

IEEE TRANSACTIONS ON software engineering 2021年第5期47卷 1029-1040页

作者： El-Fakih, Khaled Hierons, Robert M. Turker, Uraz Cengiz Amer Univ Sharjah Comp Sci & Engn Sharjah U Arab Emirates Univ Sheffield Comp Sci Sheffield S10 2TN S Yorkshire England Gebze Tech Univ Comp Engn Kocaeli Turkey

In black-box testing, test sequences may be constructed from systems modelled as deterministic finite-state machines (DFSMs) or, more generally, observable non-deterministic finite state machines (ONFSMs). Test sequences usually contain state identification sequences, with unique input output sequences (UIOS) often being used with DFSMs. This paper extends the notion of UIOS to ONFSMs. One challenge is that, as a result of non-determinism, the application of an input sequence can lead to exponentially many expected output sequences. To address this scalability problem, we introduce K-UIOS: UIOS that lead to at most K output sequences from states of M. We show that checking K-UIO existence is PSPACE-Complete if the problem is suitably bounded;otherwise it is in EXPSPACE and PSPACE-Hard. We provide a massively parallel algorithm for constructing K-UIOS and the results of experiments on randomly generated and real FSM specifications. The proposed algorithm was able to construct UIOS in cases where the existing UIO generation algorithm could not and was able to construct UIOS from FSMs with 38K states and 400K transitions.

关键词： software engineering/software/program verification software engineering/testing and debugging software engineering/test design finite state machine unique input output sequence generation general purpose graphics processing units

来源：评论

学校读者我要写书评

暂无评论

Generating Complete Controllable Test Suites for Distributed Testing

引用

IEEE TRANSACTIONS ON software engineering 2015年第3期41卷 279-293页

作者： Hierons, Robert M. Brunel Univ Dept Comp Uxbridge UB8 3PH Middx England

A test suite is m-complete for finite state machine (FSM) M if it distinguishes betweenM and all faulty FSMs with m states or fewer. While there are several algorithms that generate m-complete test suites, they cannot be directly used in distributed testing since there can be additional controllability and observability problems. Indeed, previous results show that there is no general method for generating an m-complete test suite for distributed testing and so the focus has been on conditions under which this is possible. This paper takes a different approach, which is to generate what we call c(m)-complete test suites: controllable test suites that distinguish an FSM N with no more than m states fromM if this is possible in controllable testing. Thus, under the hypothesis that the system under test has no more than m states, a c(m)-complete test suite achieves as much as is possible given the restriction that testing should be controllable. We show how the problem of generating a c(m)-complete test suite can be mapped to the problem of generating an m-complete test suite for a partial FSM. Thus, standard test suite generation methods can be adapted for use in distributed testing.

关键词： software engineering/software/program verification software engineering/testing and debugging systems and software distributed testing test suite generation checking experiment

来源：评论

学校读者我要写书评

暂无评论

Parallel Algorithms for Generating Harmonised State Identifiers and Characterising Sets

引用

IEEE TRANSACTIONS ON COMPUTERS 2016年第11期65卷 3370-3383页

作者： Hierons, Robert M. Turker, Uraz Cengiz Brunel Univ Dept Comp Sci London UB8 3PH England

Many automated finite state machine (FSM) based test generation algorithms require that a characterising set or a set of harmonised state identifiers is first produced. The only previously published algorithms for partial FSMs were brute-force algorithms with exponential worst case time complexity. This paper presents polynomial time algorithms and also massively parallel implementations of both the polynomial time algorithms and the brute-force algorithms. In the experiments the parallel algorithms scaled better than the sequential algorithms and took much less time. Interestingly, while the parallel version of the polynomial time algorithm was fastest for most sizes of FSMs, the parallel version of the brute-force algorithm scaled better due to lower memory requirements.

关键词： software engineering/software/program verification software engineering/testing and debugging software engineering/test design finite state machine characterising sets harmonised state identifiers general purpose graphics processing units

来源：评论

学校读者我要写书评

暂无评论

Oracles for Distributed Testing

引用

IEEE TRANSACTIONS ON software engineering 2012年第3期38卷 629-641页

作者： Hierons, Robert Mark Brunel Univ Sch Informat Syst Comp & Math Uxbridge UB8 3PH Middx England

The problem of deciding whether an observed behavior is acceptable is the oracle problem. When testing from a finite state machine (FSM), it is easy to solve the oracle problem and so it has received relatively little attention for FSMs. However, if the system under test has physically distributed interfaces, called ports, then in distributed testing, we observe a local trace at each port and we compare the set of local traces with the set of allowed behaviors (global traces). This paper investigates the oracle problem for deterministic and nondeterministic FSMs and for two alternative definitions of conformance for distributed testing. We show that the oracle problem can be solved in polynomial time for the weaker notion of conformance ((sic)(w)) but is NP-hard for the stronger notion of conformance ((sic)(s)), even if the FSM is deterministic. However, when testing from a deterministic FSM with controllable input sequences, the oracle problem can be solved in polynomial time and similar results hold for nondeterministic FSMs. Thus, in some cases, the oracle problem can be efficiently solved when using (sic)(s) and where this is not the case, we can use the decision procedure for (sic)(w) as a sound approximation.

关键词： software engineering/software/program verification software engineering/testing and debugging systems and software distributed systems finite state machine nondeterminism test oracle controllability local observability

来源：评论

学校读者我要写书评

暂无评论

Parallel Algorithms for Testing Finite State Machines: Generating UIO Sequences

引用

IEEE TRANSACTIONS ON software engineering 2016年第11期42卷 1077-1091页

作者： Hierons, Robert M. Turker, Uraz Cengiz Brunel Univ London Dept Comp Sci London England

This paper describes an efficient parallel algorithm that uses many-core GPUs for automatically deriving Unique Input Output sequences (UIOs) from Finite State Machines. The proposed algorithm uses the global scope of the GPU's global memory through coalesced memory access and minimises the transfer between CPU and GPU memory. The results of experiments indicate that the proposed method yields considerably better results compared to a single core UIO construction algorithm. Our algorithm is scalable and when multiple GPUs are added into the system the approach can handle FSMs whose size is larger than the memory available on a single GPU.

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：