Ideally, in FSM-based testing, a test suite should have as few input symbols and sequences as possible, speeding up its execution, and being able to reveal as many faulty implementations as possible in a given fault domain. Unfortunately, in general, it is an NP-hard problem. Several test generation methods have been proposed to generate a test suite with full fault detection capability. However, they usually generate large test suites with many sequences. In this paper, we propose a search-based software testing method aiming to generate test suites that represent a good trade-off between its cost and its fault coverage. A new encoding, called Node-depth-outdegree Encoding (NDOE) and its mutation and initialization operators are proposed. Also, a new fitness function is presented. The proposed fitness is composed of three objectives: minimize the test suite length, minimize the number of test sequences, and maximize the fault coverage, which analysis is based on mutation score. The experimental results show that the proposed method is able to generate lower cost test suites, with high mutation score, than literature test generation methods.

The effectiveness of Model-Based Testing (MBT) is mainly due to the potential for automation it offers.If the model is formal and machine-readable, test cases can be derived automatically.The Extended Finite State Machine (EFSM) is a formal modeling technique widely used to represent a system.However, EFSM is not a common practice in industry.On the other hand, the Unified Modeling Language (UML) has become the de-facto standard for modeling software, but due to the lack of formal semantics, its diagrams can have ambiguous interpretations and are not suitable for testing automation.In this context, we present a systematic procedure for generating tests from a UML model.More specifically, our approach proposes a mapping from the UML Sequence Diagram into Extended Finite State Machine in order to provide a precise semantics to them and uses the ModelJUnit and JUnit libraries in order to generate test cases automatically.

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.

Summary In service‐oriented architecture testing, the behaviour of a composite service and its partner services can be represented as an event graph (model). As test cases are derived from such a model, the Chinese postman problem (CPP) algorithm is applied to cover all edges. Although CPP provides an optimal solution, there is a lack of alternative algorithms to obtain not only a faster execution but also a satisfactory solution. This paper introduces the event tree algorithm (ETA) to generate test cases from event sequence models for Web service compositions. Two strategies are also proposed to improve ETA: First, a greedy strategy to build the tree is defined based on the cost of expanding given edges. Second, redundant elements are eliminated (pruned) in the tree. Four versions of ETA are compared with CPP with respect to test suite size, generation time, number of test sequences, and test sequence length.

Testing as a Service (TaaS) is a new business and service model that provides efficient and effective software quality assurance and enables the use of a cloud for the meeting of quality standards, requirements and consumer's needs. However, problems that limit the effective use of TaaS involve lack of standardization in writing, execution, configuration and management of tests and lack of portability and interoperability among TaaS platforms - the so-called lock-in problem. The lock-in problem is a serious threat to software testing in the cloud and may become critical when a provider decides to suddenly increase prices, or shows serious technical availability problems. This paper proposes a novel approach for solving the lock-in problem in TaaS with the use of design patterns. The aim to assist software engineers and quality control managers in building testing solutions that are both portable and interoperable and promote a more widespread adoption of the TaaS model in cloud computing.

Context: The demand from industry for more dependable and scalable test-development mechanisms has fostered the use of formal models to guide the generation of tests.Despite many advancements having been obtained with state-based models, such as Finite State Machines (FSMs) and Input/Output Transition Systems (IOTSs), more advanced formalisms are required to specify large, state-rich, concurrent systems.Circus, a state-rich process algebra combining Z, CSP and a refinement calculus, is suitable for this; however, deriving tests from such models is accordingly more challenging.Recently, a testing theory has been stated for Circus, allowing the verification of process refinement based on exhaustive test sets.Objective: We investigate fault-based testing for refinement from Circus specifications using mutation.We seek the benefits of such techniques in test-set quality assertion and fault-based test-case selection.We target results relevant not only for Circus, but to any process algebra for refinement that combines CSP with a data language.Method: We present a formal definition for fault-based test sets, extending the Circus testing theory, and an extensive study of mutation operators for Circus.Using these results, we propose an approach to generate tests to kill mutants.Finally, we explain how prototype tool support can be obtained with the implementation of a mutant generator, a translator from Circus to CSP, and a refinement checker for CSP, and with a more sophisticated chain of tools that support the use of symbolic tests.Results: We formally characterise mutation testing for Circus, defining the exhaustive test sets that can kill a given mutant.We also provide a technique to select tests from these sets based on specification traces of the mutants.Finally, we present mutation operators that consider faults related to both reactive and data manipulation behaviour.Altogether, we define a new fault-based test-generation technique for Circus.Conclusion: We conclude that mutation testing for Circus can truly aid making test generation from state-rich model more tractable, by focussing on particular faults.

Many approaches have been proposed for checking test suite completeness for Finite State Machines (FSMs). Some approaches provide sufficient conditions whereas others give necessary and sufficient conditions for test suite completeness. One method, called the CONF method, is based on sufficient conditions, and relies on a search for confirmed sets when checking completeness. If a confirmed set cannot be found, then the outcome is inconclusive. Another method, the SIM method, is based on the notion of simulation relations, and relies on necessary and sufficient conditions when checking test suite completeness. The SIM method always returns conclusive verdicts about suite completeness. In this work, we describe experimental results comparing these two methods. We also investigate when both methods can be combined for checking completeness of test suites. We evaluate both strategies according to different parameters of the FSMs, such as the number of states and the number of transitions in the FSM models, the size of input and output alphabets of the FSM models, as well as the size of the test suites. We also report on the relative rates of conclusive and inconclusive verdicts when using both methods. We see that these methods are complementary, which allows for a combined strategy: the CONF method is the fastest in terms of processing time, while the SIM method is not as scalable in terms of the size of the specifications. The experimental results indicated a substantial difference for the rate of positive verdicts obtained by the SIM method when compared with the number of positive answers returned by the CONF method.

Extended finite state machines (EFSMs) provide a rigorous model for the derivation of functional tests for software systems and protocols. Various types of data-flow, control-flow, graph-based, and state machine based test selection criteria can be used for deriving tests from a given EFSM specification. Also, traditional types of state machine based notions of faults, such as transfer and output parameter faults, and common types of assignment faults can be used to describe the fault domains of EFSMs. We present an assessment of the most known types of EFSM test selection criteria such as test suites that cover single transfer faults, double transfer faults, single output parameter faults, and many types of single assignment faults of a given EFSM specification. Also, test suites that cover edge-pair, prime path, prime path with side trip, and all-uses criterion are derived from the graph and flow-graph representations of the specification. We also consider transition tour and random test suites. The assessment ranks the considered test suites in terms of their length and their coverage of single transfer, double transfer, and different type of single assignment faults. Dispersion of the obtained results is assessed and results are summarized.

Several methods have been proposed for generating tests from a Finite State Machine (FSM) representation of systems. Even though these methods usually generate large test suites, each with many sequences, the methods possess the important feature of generating test suites with guaranteed fault coverage. In this paper, we propose approaches for reducing the size of a test suite while maintaining the same fault coverage. The approaches combine the test suite sequences, aiming at both reducing the test suite length and the number of sequences, and then check whether the resulting test suite satisfies conditions that are known to ensure that the coverage remains unaltered. The experimental results in random FSMs show on average 78% (maximum: 97.0%) of reduction of the number of test cases and on average 42% (maximum: 63.8%) of reduction of total length of test suites produced by classical FSM-based generation methods.

Abstract Model-based testing overcomes challenges in software testing by generating automated test cases from behavior models, e.g. finite state machine (FSM) and input/output transition system (IOTS). Despite the existence of methods for IOTSs, the problem of selection of test cases is an important and difficult topic. The current methods from IOTSs do not provide the same support offered by the existing theory for FSMs, as complete fault coverage. In this paper, we propose a test generation method for IOTSs based on the W method developed for FSMs. The basic idea is to generate a transition cover set and a characterization set and concatenate them to generate complete test suites for IOTSs in a bounded number of steps. The method generates test suites with complete fault coverage for a given fault domain and is targeted at a class of IOTSs, called mealy IOTS, which accepts inputs only in stable states. Results from a case study show the proposed algorithm can achieve better results than a classical method for IOTSs.

There exists a significant body of work devoted to so-called complete tests which guarantee the detection of all the faults in a given fault domain. Several methods for generating complete tests for finite state machines (FSMs) which are based on a distinguishing sequence (DS) have been proposed. These methods even if extended to use adaptive DSs apply only to deterministic FSMs and the question arises whether they can be extended to non-deterministic FSMs to test for trace inclusion. In this paper, we generalize the notion of DS to a so-called total state separator, which is an adaptive experiment distinguishing states in any FSM that is trace included into the specification FSM. We then propose a method to test non-deterministic FSMs for trace inclusion. State separator is a key means of the proposed method, which has two phases: in the first phase, a preset test is constructed, which should be repeatedly applied to a non-deterministic implementation, thus requiring its resetting; in the second phase, the implementation is tested online and no reset is required. To the best of our knowledge, this is the first method which tests non-deterministic FSMs for the trace inclusion conformance relation, while avoiding resetting implementations to re-execute tests for transition verification.

Summary Testing is a key activity to assure the quality of concurrent applications. In recent years, a variety of different mechanisms have been proposed to test concurrent software. However, a persistent problem is the high testing cost because of the large number of different synchronization sequences that must be tested. When structural testing criteria are adopted, a large number of infeasible synchronization sequences is generated, increasing the testing cost. Although the use of reachability testing reduces the number of infeasible combination (because only feasible synchronization sequences are generated), many synchronization combinations are also generated, and this again results in a testing cost with exponential behavior. This paper presents a new composite approach that uses reachability testing to guide the selection of the synchronization sequences tests according to a specific structural testing criterion. This new composite approach is empirically evaluated in the context of message‐passing concurrent programs developed with MPI. The experimental study evaluates both the cost and effectiveness of proposed composite approach in comparison with traditional reachability testing and structural testing. The results confirm that the use of the new composite approach has advantages for testing of concurrent applications. Copyright © 2015 John Wiley & Sons, Ltd.

SUMMARY The behavior of composed Web services depends on the results of the invoked services; unexpected behavior of one of the invoked services can threat the correct execution of an entire composition. This paper proposes an event‐based approach to black‐box testing of Web service compositions based on event sequence graphs, which are extended by facilities to deal not only with service behavior under regular circumstances (i.e., where cooperating services are working as expected) but also with their behavior in undesirable situations (i.e., where cooperating services arenotworking as expected). Furthermore, the approach can be used independently of artifacts (e.g., Business Process Execution Language) or type of composition (orchestration/choreography). A large case study, based on a commercial Web application, demonstrates the feasibility of the approach and analyzes its characteristics. Test generation and execution are supported by dedicated tools. Especially, the use of an enterprise service bus for test execution is noteworthy and differs from other approaches. The results of the case study encourage to suggest that the new approach has the power to detect faults systematically, performing properly even with complex and large compositions. Copyright © 2012 John Wiley & Sons, Ltd.

Service-oriented architectures and Web services have been widely adopted by enterprises to pervade integration among software systems. As reliable services are essential to assure that these systems work correctly, formal and systematic testing should be performed. This paper reports the application of a model-based approach to test Web services in the context of real-world applications of a multinational computer technology corporation. The employed approach is called ESG4WSC, in which an event-driven model is provided to support modeling and test case generation, as well as an environment to support the concretization and test execution.

Testing from finite state machines has been widely investigated due to its well-founded and sound theory as well as its practical application in different areas, e.g., Web-based systems and protocol testing. There has been a recurrent interest in developing methods capable of generating test suites that detect all faults in a given fault domain. However, the proposal of new methods motivates the comparison with traditional methods. In this context, we conducted a set of experiments that compares W, HSI, H, SPY, and P methods. The results have shown that H, SPY, and P methods produce smaller test suites than traditional methods (W, HSI). Although the P method presented the shortest test suite in most cases, its reduction is smaller compared with H and SPY. We have also observed that the reduction ratio in partial machines is smaller than that in complete machines.

A checking sequence is a single input sequence which is able to reveal all the faults in a given fault domain. There are many methods for generating checking sequences for deterministic finite state machines (FSM), however, we are not aware of any generalization to no deterministic machines. No deterministic specifications are needed for software testing, as they describe the behavior of a wider class of reactive systems than deterministic FSMs when depending on the environment conditions, a no deterministic system is allowed to take different runs under the same input sequence. In this paper, we propose a method for constructing checking sequences when both the specification and implementations under test are modeled by no deterministic FSMs.

SUMMARY A long‐standing problem when testing from a deterministic finite state machine is to guarantee full fault coverage even if the faults introduce extra states in the implementations. It is well known that such tests should include the sequences in a traversal set which contains all input sequences of length defined by the number of extra states. This paper suggests the SPY method, which helps reduce the length of tests by distributing sequences of the traversal set and reducing test branching. It is also demonstrated that an additional assumption about the implementation under test relaxes the requirement of the complete traversal set. The results of the experimental comparison of the proposed method with an existing method indicate that the resulting reduction can reach 40%. Experimental results suggest that the additional assumption about the implementation can help in further reducing the test suite length. Copyright © 2011 John Wiley & Sons, Ltd.

In this paper, we consider a classical problem of complete test generation for deterministic finite-state machines (FSMs) in a more general setting. The first generalization is that the number of states in implementation FSMs can even be smaller than that of the specification FSM. Previous work deals only with the case when the implementation FSMs are allowed to have the same number of states as the specification FSM. This generalization provides more options to the test designer: when traditional methods trigger a test explosion for large specification machines, tests with a lower, but yet guaranteed, fault coverage can still be generated. The second generalization is that tests can be generated starting with a user-defined test suite, by incrementally extending it until the desired fault coverage is achieved. Solving the generalized test derivation problem, we formulate sufficient conditions for test suite completeness weaker than the existing ones and use them to elaborate an algorithm that can be used both for extending user-defined test suites to achieve the desired fault coverage and for test generation. We present the experimental results that indicate that the proposed algorithm allows obtaining a trade-off between the length and fault coverage of test suites.

In testing from a Finite State Machine (FSM), the generation of test suites which guarantee full fault detection, known as complete test suites, has been a long-standing research topic. In this paper, we present conditions that are sufficient for a test suite to be complete. We demonstrate that the existing conditions are special cases of the proposed ones. An algorithm that checks whether a given test suite is complete is given. The experimental results show that the algorithm can be used for relatively large FSMs and test suites.

In this paper we present a generalization to the W-method, which can be used for automatically generating test cases.In contrast to the W-method, this generalization allows for test case generation even in the absence of characterization sets for the specification.We give proofs of correctness for this generalization, and show how to derive the original W-method from it as a particular case.Proofs of correctness for the W-method, not given in the original paper, are also presented in a clear and detailed way.

Abstract Parallel programs present some features such as concurrency, communication and synchronization that make the test a challenging activity. Because of these characteristics, the direct application of traditional testing is not always possible and adequate testing criteria and tools are necessary. In this paper we investigate the challenges of validating message‐passing parallel programs and present a set of specific testing criteria. We introduce a family of structural testing criteria based on a test model. The model captures control and data flow of the message‐passing programs, by considering their sequential and parallel aspects. The criteria provide a coverage measure that can be used for evaluating the progress of the testing activity and also provide guidelines for the generation of test data. We also describe a tool, called ValiPar, which supports the application of the proposed testing criteria. Currently, ValiPar is configured for parallel virtual machine (PVM) and message‐passing interface (MPI). Results of the application of the proposed criteria to MPI programs are also presented and analyzed. Copyright © 2008 John Wiley & Sons, Ltd.

This paper presents a technique to select subsets of the test cases, reducing the time consumed during the evaluation of a new software version and maintaining the ability to detect defects introduced. Our technique is based on a model to classify test case suites by using an ART-2A selforganizing neural network architecture. Each test case is summarized in a feature vector, which contains all the relevant information about the software behavior. The neural network classifies feature vectors into clusters, which are labeled according to software behavior. The source code of a new software version is analyzed to determine the most adequate clusters from which the test case subset will be selected. Experiments compared feature vectors obtained from all-uses code coverage information to a random selection approach. Results confirm the new technique has improved the precision and recall metrics adopted.