The practice of testing software systems modelled as Finite State Machines (FSMs) has garnered significant attention owing to its simplicity. In FSM-based testing, the tester derives a test suite from the FSM model representing the system’s specification. Subsequently, this test suite is executed against the implementation, and the tester uses the output to decide whether the implementation conforms to the specification. Often, a test suite generation technique requires input sequences to check whether the FSM is in the intended state. This task is referred to asstate identificationand is often carried out using a set of input sequences called a characterising set. Even though the use of characterising sets simplifies testing, they require a reliable reset or reset sequence and additional transfer sequences. Unfortunately, resetting the underlying system can be costly or may entail manual configuration. In addition, transfer sequences do not directly contribute to testing. This work introduces a class of characterising sets (Ordered Characterising Sets(O-WSets)) that avoid using resets or transfers by design. We show that checking the existence of such a characterising set is NP-complete. We introduce the notion of bounded O-WSets (BO-WSets), which are types of O-WSets that limit transfer usage, and give an algorithm that constructs these. In experiments, on average, the proposed approach led to reductions in the number of resets (95% for real FSMs; 99.73% for synthetic FSMs), the number of transfer inputs (53% for real FSMs; 63.3% for synthetic FSMs) and the number of inputs in state identification sequences (50% for real FSMs; 66.6% for synthetic FSMs). Additionally, the proposed algorithm reduced the time and memory required to derive state identification sequences by 85% and 23%, respectively. Finally, the approach led to test suites with 49.3% fewer sequences and 33.3% fewer inputs on average.

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$\mathcal{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.

The increasing complexity and criticality of software systems have led to growing interest in automated test generation. One of the most promising approaches is to use model-based testing (MBT), in which test automation is based on a model of theimplementation under test (IUT), with much of the work concerning finite state machine (FSM) models. Many FSM-based test generation techniques use, possibly adaptive, sequences to check the state of the IUT. Of particular interest are adaptive distinguishing sequences (ADSs) because their use can lead to relatively small tests. However, not all systems possess an ADS. In this work, we generalise the notion of incomplete ADSs to non-deterministic partial and observable FSMs. We show that the problem of checking the existence of a set of$k$incomplete ADSs that separates every pair of states is PSPACE-hard. Further, we generalise the notion of invertible sequences to non-deterministic partial and observable FSMs and show how invertible sequences can be used to derive additional incomplete ADSs. We propose a novel algorithm to generate incomplete ADSs and describe the results of experiments that evaluated its performance. The results indicate that the proposed method can generate sequences to identify states of the IUT and is faster and can process larger FSMs than other existing methods.

Summary Tests can be derived from extended finite state machine (EFSM) specifications considering the coverage of single‐transfer faults, all transitions using a transition tour, all‐uses, edge‐pair, and prime path with side trip. We provide novel empirical assessments of the effectiveness of these test suites. The first assessment determines for each pair of test suites if there is a difference between the pair in covering EFSM faults of six EFSM specifications. If the difference is found significant, we determine which test suite outperforms the other. The second assessment is similar to the first; yet, it is carried out against code faults of 12 Java implementations of the specifications. Besides, two assessments are provided to determine whether test suites have better coverage of certain classes of EFSM (or code) faults than others. The evaluation uses proper data transformation of mutation scores andp‐value adjustments for controlling Type I error due to multiple tests. Furthermore, we show that subsuming mutants have an impact on mutation scores of both EFSM and code faults; and accordingly, we use a score that removes them in order not to invalidate the obtained results. The assessments show that all‐uses tests were outperformed by all other tests; transition tours outperformed both edge‐pair and prime path with side trips; and single‐transfer fault tests outperformed all other test suites. Similar results are obtained over the considered EFSM and code fault domains, and there were no significant differences between the test suites coverage of different classes of EFSM and code faults.

Model-based testing is a structured method to test complex systems. Scaling up model-based testing to large systems requires improving the efficiency of various steps involved in testcase generation and more importantly, in test-execution. One of the most costly steps of model-based testing is to bring the system to a known state, best achieved through synchronising sequences. A synchronising sequence is an input sequence that brings a given system to a predetermined state regardless of system’s initial state. Depending on the structure, the system might be complete, i.e., all inputs are applicable at every state of the system. However, some systems are partial and in this case not all inputs are usable at every state. Derivation of synchronising sequences from complete or partial systems is a challenging task. In this paper, we introduce a novel Q-learning algorithm that can derive synchronising sequences from systems with complete or partial structures. The proposed algorithm is faster and can process larger systems than the fastest sequential algorithm that derives synchronising sequences from complete systems. Moreover, the proposed method is also faster and can process larger systems than the most recent massively parallel algorithm that derives synchronising sequences from partial systems. Furthermore, the proposed algorithm generates shorter synchronising sequences.

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 ofUIOsto 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${\mathcal K}$-UIOs:UIOsthat lead to at most${\mathcal K}$output sequences from states of$M$. We show that checking${\mathcal K}$-UIOexistence 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${\mathcal K}$-UIOsand the results of experiments on randomly generated and real FSM specifications. The proposed algorithm was able to constructUIOsin cases where the existingUIOgeneration algorithm could not and was able to constructUIOsfrom FSMs with 38K states and 400K transitions.

Featured Finite State Machines (FFSMs) were proposed as a modeling formalism that represents the abstract behavior of an entire software product line (SPL). Several model-based testing techniques have been developed to support test case generation for SPL specifications, but none support the full fault coverage criterion for SPLs at the family-wide level. In this paper, we propose an extension of the Harmonized State Identifiers (HSI) method, an FSM-based testing method supporting full fault coverage. By extending the HSI method for FFSMs, we are able to generate a single configurable test suite for groups of SPL products that can be instantiated using feature constraints. We implement a graphical tool named ConFTGen to guide the design, validation, derivation and test case generation for state, transition and full fault coverage of FFSMs. Experimental results indicate a reduction of approximately 50% on the number of test cases required to test 20 random SPL products. Also, we investigate the applicability of our method by applying it to a case study from the automotive domain, namely the Body Comfort System.

There has been long-standing interest in automatically generating test sequences from a finite state machine (FSM) and more recently this has been extended to the case where there are multiple physically distributed testers and so we are testing from a multi-port FSM. This paper explores the problem of generating a controllable preset distinguishing sequence (PDS) from a multi-port FSM, motivated by the fact that many FSM-based test generation algorithms use PDSs. We prove that it is generally undecidable whether a multi-port FSM has a controllable PDS but provide a class of multi-port FSMs for which the problem is decidable. We also consider the important case where there is an upper bound ` on the length of PDSs of interest, proving that controllable PDS existence is PSPACE-hard and in EXPSPACE. In practice the upper bound ` is likely to be a polynomial in terms of the size of the multi-port FSM and in this case controllable PDS existence is NP- Complete.

A distinguishing sequence (DS) for a finite-state machine (FSM) is an input sequence that distinguishes every pair of states of the FSM. There are techniques that generate a test sequence with guaranteed fault detection power, and it has been found that shorter test sequences can be produced if DSs are used. Despite these benefits, however, until recently the only published DS generation algorithms have been for deterministic FSMs. This article develops a massively parallel algorithm, which can be used in Graphics Processing Units (GPUs) Computing, to generate DSs from partial observable non-deterministic FSMs. We also present the results of experiments using randomly generated FSMs and some benchmark FSMs. The results are promising and indicate that the proposed algorithm can derive DSs from partial observable non-deterministic FSMs with 32,000 states in an acceptable amount of time.

This paper concerns the problem of testing from a finite state machine (FSM) M modelling a system that interacts with its environment at multiple physically distributed interfaces, called ports. We assume that the distributed test architecture is used: there is a local tester at each port, the tester at port p only observes events at p, and the testers do not interact during testing. This paper formalises the notion of an adaptive test strategy and what it means for an adaptive test strategy to be controllable. We provide algorithms to check whether a global strategy is controllable and to generate a controllable adaptive distinguishing sequence (ADS). We prove that controllable ADS existence is PSPACE-hard and that the problem of deciding whether M has a controllable ADS with length l is NP-hard. In practice, there is likely to be a polynomial upper bound on the length of ADS in which we are interested and for this case the decision problem is NP-complete.

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.

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.

Given a Finite State Machine (FSM) M, a Distinguishing Sequence (DS) is a test that identifies the state of M. While there are two types of DSs, preset DSs (PDSs) and adaptive DSs (ADSs), not all FSMs possess a DS. In this paper, we examine the problem of finding incomplete PDSs and ADSs, exploring associated optimisation problems: finding a largest set of states that has a DS and finding a smallest set of DSs that, between them, distinguish all of the states. We also propose a greedy algorithm to produce a small set of incomplete ADSs and use experiments to compare this with two previously published algorithms for generating state identifiers. We show that the optimisation problems related to incomplete ADSs and PDSs are PSPACE-Complete as are corresponding approximation problems. In the experiments we found that incomplete ADSs produced by the proposed greedy algorithm led to relatively compact state identifiers.

Abstract We study the relation between synchronizing sequences and preset distinguishing sequences which are some special sequences used in finite state machine based testing. We show that the problems related to preset distinguishing sequences can be converted into related problems of synchronizing sequences. Using the results existing in the literature for synchronizing sequences, we offer several reflections of these results for preset distinguishing sequences. Although computing a preset distinguishing sequence is PSPACE-hard , we do identify a class of machines for which computing a preset distinguishing sequence can be performed in polynomial time and argue that this class is practically relevant. We also present an experimental study to compare the performance of exponential brute-force and polynomial heuristic algorithms to compute a preset distinguishing sequence.