Abstract The correspondence of active learning and testing of finite-state machines (FSMs) has been known for a while; however, it was not utilized in the learning. We propose a new framework called the observation tree approach that allows one to use the testing theory to improve the performance of active learning. The improvement is demonstrated on three novel learning algorithms that implement the observation tree approach. They outperform the standard learning algorithms, such as the L* algorithm, in the setting where a minimally adequate teacher provides counterexamples. Moreover, they can also significantly reduce the dependency on the teacher using the assumption of extra states that is well-established in the testing of FSMs. This is immensely helpful as a teacher does not have to be available if one learns a model of a black box, such as a system only accessible via a network.

Models play a crucial role in the development and maintenance of software systems, but are often neglected during the development process due to the considerable manual effort required to produce them. In response to this problem, numerous techniques have been developed that seek to automate the model generation task with the aid of increasingly accurate algorithms from the domain of Machine Learning. From an empirical perspective, these are extremely challenging to compare; there are many factors that are difficult to control (e.g. the richness of the input and the complexity of subject systems), and numerous practical issues that are just as troublesome (e.g. tool availability). This paper describes the StaMinA ( Sta te M achine In ference A pproaches) competiton, that was designed to address these problems. The competition attracted numerous submissions, many of which were improved or adapted versions of techniques that had not been subjected to extensive empirical evaluations, and had not been evaluated with respect to their ability to infer models of software systems. This paper shows how many of these techniques substantially improve on the state of the art, providing insights into some of the factors that could underpin the success of the best techniques. In a more general sense it demonstrates the potential for competitions to act as a useful basis for empirical software engineering by (a) spurring the development of new techniques and (b) facilitating their comparative evaluation to an extent that would usually be prohibitively challenging without the active participation of the developers.

State machines capture the sequential behavior of software systems. Their intuitive visual notation, along with a range of powerful verification and testing techniques render them an important part of the model-driven software engineering process. There are several situations that require the ability to identify and quantify the differences between two state machines (e.g. to evaluate the accuracy of state machine inference techniques is measured by the similarity of a reverse-engineered model to its reference model). State machines can be compared from two complementary perspectives: (1) In terms of theirlanguage-- the externally observable sequences of events that are permitted or not, and (2) in terms of theirstructure-- the actual states and transitions that govern the behavior. This article describes two techniques to compare models in terms of these two perspectives. It shows how the difference can be quantified and measured by adapting existing binary classification performance measures for the purpose. The approaches have been implemented by the authors, and the implementation is openly available. Feasibility is demonstrated via a case study to compare two real state machine inference approaches. Scalability and accuracy are assessed experimentally with respect to a large collection of randomly synthesized models.

Testing methods aiming to demonstrate that an implementation behaves the same as a specification X-machine (extended finite-state machine) usually assume that (1) all states are terminal states and (2) there are no priorities associated with operations on transitions. The considered model for the machine is such that outputs for transitions leading to non-terminal states will be buffered and contents of buffers will only be made observable when terminal states are entered. The X-machine testing method has been extended in this work to handle such an extension of X-machines (EFSM).Priorities of operations determine the order in which guards of transitions are evaluated. This makes it possible to reduce the size of a test suite. For instance, if testing has shown that a transition with a specific guard g has been implemented from some state, then no lower-priority transition with a guard implied by g may ever be executed from that state. It is hence not necessary to test for the presence of such a lower-priority transition.

Finite state machine-based abstractions of software behaviour are popular because they can be used as the basis for a wide range of (semi-) automated verification and validation techniques. These can however rarely be applied in practice, because the specifications are rarely kept up- to-date or even generated in the first place. Several techniques to reverse-engineer these specifications have been proposed, but they are rarely used in practice because their input requirements (i.e. the number of execution traces) are often very high if they are to produce an accurate result. An insufficient set of traces usually results in a state machine that is either too general, or incomplete. Temporal logic formulae can often be used to concisely express constraints on system behaviour that might otherwise require thousands of execution traces to identify. This paper describes an extension of an existing state machine inference technique that accounts for temporal logic formulae, and encourages the addition of new formulae as the inference process converges on a solution. The implementation of this process is openly available, and some preliminary results are provided.

Abstract Grammar inference is a family of machine learning techniques that aim to infer grammars from a sample of sentences in some (unknown) language. Dynamic analysis is a family of techniques in the domain of software engineering that attempts to infer rules that govern the behaviour of software systems from a sample of executions. Despite their disparate domains, both fields have broadly similar aims; they try to infer rules that govern the behaviour of some unknown system from a sample of observations. Deriving general rules about program behaviour from dynamic analysis is difficult because it is virtually impossible to identify and supply a complete sample of necessary program executions. The problems that arise with incomplete input samples have been extensively investigated in the grammar inference community. This has resulted in a number of advances that have produced increasingly sophisticated solutions that are more successful at accurately inferring grammars from (potentially) sparse information about the underlying system. This paper investigates the similarities and shows how many of these advances can be applied with similar effect to dynamic analysis problems by a series of small experiments on random state machines. Copyright © 2008 John Wiley & Sons, Ltd.

Abstract Finite‐state machine specifications form the basis for a number of rigorous state‐based testing techniques and can help to understand program behaviour. Unfortunately they are rarely maintained during software development, which means that these benefits can rarely be fully exploited. This paper describes a technique that, given a set of states that are of interest to a developer, uses symbolic execution to reverse‐engineer state transitions from source code. A particularly novel aspect of our approach is that, besides determining whether or not a state transition can take place, it also identifies the paths through the source code that govern a transition. The technique has been implemented as a prototype, enabling its preliminary evaluation with respect to real software systems. Copyright © 2007 John Wiley & Sons, Ltd.

Abstract The X-machine testing method has been developed as an application of the W-method to testing the control structure of an implementation, against a specification. The method was proven to demonstrate the equivalence of the behaviour of the two, subject to a number of conditions both a specification and an implementation are expected to satisfy, such as (1) determinism of the two and (2) that functions labelling arcs on a transition diagram of a specification control structure have been tested in advance. Since the original publication of the testing method, a number of extensions have been published, removing the restrictions mentioned above. This paper surveys the extensions of the X-machine testing method, for (1) testing of functions together with testing of a transition diagram, (2) equivalence testing of a non-deterministic implementation against a non-deterministic specification, (3) conformance testing of a deterministic implementation against a non-deterministic specification and (4) equivalence testing of a system of concurrently executing and communicating X-machines, against a specification.

Abstract An existing statechart testing method developed by the authors allows a tester to show the equivalence of the behaviour of an implementation of some software system to its Harel statechart specification, by testing. This requires a rather large test set and satisfaction of certain requirements for both a specification and an implementation. Introduction of additional constraints permits reduction in a test set size, without weakening of the conclusions obtained by testing. This paper describes how a test set can be derived from a relatively big statechart and investigates the role of a few specific constraints in the reduction of test set size, depending on where in the system structure these constraints are used. The main contribution of the paper is a demonstration that enforcing relatively weak constraints in the right place of a system's structure makes it possible to reduce the size of a test set by many orders of magnitude. The practical use of the contribution is to help developers structure a system under construction in such a way that it is completely testable using the described testing method with few additional constraints. Copyright © 2004 John Wiley & Sons, Ltd.

Formal methods have traditionally been used for specification and development of software. However there are potential benefits for the testing stage as well. The panel session associated with this paper explores the usefulness or otherwise of formal methods in various contexts for improving software testing. A number of different possibilities for the use of formal methods are explored and questions raised. The contributors are all members of the UK FORTEST Network on formal methods and testing. Although the authors generally believe that formal methods are useful in aiding the testing process, this paper is intended to provoke discussion. Dissenters are encouraged to put their views to the panel or individually to the authors.

Abstract A number of current control systems for aircraft have been specified with statecharts. The risk of failures requires the use of a formal testing approach to ensure that all possible faults are considered. However, testing the compliance of an implementation of a system to its specification is dependent on the specification method and little work has been reported relating to the use of statechart‐specific methods. This paper describes a modification of a formal testing method for extended finite‐state machines to handle the above problem. The method allows one to demonstrate correct behaviour of an implementation of some system, with respect to its specification, provided certain specific requirements for both of them are satisfied. The case study illustrates these and shows the applicability of the method. By considering the process used to develop the system it is possible to reduce the size of the test set dramatically; the method to be described is easy to automate. Copyright © 2001 John Wiley & Sons, Ltd.