During regression testing, a modified system is often retested using an existing test suite. Since the size of the test suite may be very large, testers are interested in detecting faults in the modified system as early as possible during this retesting process. Test prioritization attempts to order tests for execution so that the chances of early detection of faults during retesting are increased. The existing prioritization methods are based on the source code of the system under test. In this paper, we present and evaluate two model-based selective methods and a dependence-based method of test prioritization utilizing the state-based model of the system under test. These methods assume that the modifications are made both on the system under test and its model. The existing test suite is executed on the system model and information about this execution is used to prioritize tests. Execution of the model is inexpensive as compared with execution of the system under test; therefore, the overhead associated with test prioritization is relatively small. In addition, we present an analytical framework for evaluation of test prioritization methods. This framework may reduce the cost of evaluation as compared with the framework that is based on observation. We have performed an empirical study in which we compared different test prioritization methods. The results of the empirical study suggest that system models may improve the effectiveness of test prioritization with respect to early fault detection. L. TAHAT ET AL. be very expensive. Test prioritization orders tests from the existing test suite, for 'execution' in such a way that faults in the modified system are uncovered early during the retesting process. Test prioritization methods [14-21] order tests according to some criterion, e.g. a code coverage is achieved at the fastest rate. Tests are then executed in this prioritized order: tests with higher priority, based on the prioritization criterion, are executed first, whereas tests with lower priority are executed later. The existing test prioritization techniques use the source code and information gathered during previous executions of the system to prioritize the test suite for system retesting. Notice that test prioritization is appropriate for software systems for which execution of a test suite is expensive in terms of time and resources. For systems for which execution of a test suite is very fast, test prioritization may have limited benefits. System models are often used during the development of a software system, e.g. in partial code generation and in test generation for model-based testing. Several modelling languages have been developed to model state-based software systems, e.g. State Charts [22], Extended Finite State Machines (EFSM) [23], and Specification Description Language (SDL) [24]. In the recent years, several model-based test generation [23, 25-29] and test suite reduction [9, 13] techniques have been developed based on these modelling languages. In this paper, we present a model-based test prioritization approach. Our approach prioritizes tests using information from the original and modified system models together with information collected during the execution of the modified model on an existing test suite. Based on this approach, we present two model-based test prioritization methods: model-based selective test prioritization and model dependence-based test prioritization. We have performed an empirical study in which we compared effectiveness of the presented test prioritization methods. In addition, we present an analytical framework for evaluation of some test prioritization methods with respect to the effectiveness of early fault detection. The remainder of this paper is organized as follows: Section 2 provides an overview of the EFSMbased system modelling. Section 3 gives the preliminaries on the problem of test prioritization and presents the model-based test prioritization. Section 4 presents the proposed model-based selective test prioritization method. Section 5 presents the proposed model dependence-based test prioritization method. In Section 6, a framework for comparison of test prioritization methods is discussed. In Section 7, the results of an empirical study are presented. Section 8 outlines the related work on test prioritization. In Section 9, conclusions and future research directions are discussed. System models for state-based systems describe the system behaviour by a set of states and transitions between these states. The most popular formal description techniques (languages) used for modelling of state-based systems are: Extended Finite State Machines (EFSMs), Specification Description Language (SDL), and State Charts. These languages are often graphical, which makes them easy to comprehend and utilize. They have received wide industry acceptance, especially in the fields of telecommunications, embedded systems, and computer networking, where state-based systems are prevalent. In this paper, we concentrate on system models given as EFSMs; the underlying model for other modelling languages for state-based systems such as SDL. An EFSM consists of a set of states (including a start state and an exit state) and transitions between states. A transition is triggered at its originating state when an event occurs (i.e. an input is received) and an enabling condition (i.e. a Boolean expression) associated with the transition is satisfied. When the transition is triggered, a sequence of actions may be performed (which may manipulate variables and produce an output) and the system is transferred to the terminating state of the transition. An EFSM M is expressed formally as a 7 tuple: M = ( , Q, Start, Exit, V , O, R), where is the set of events, Q is the set of states, Start ∈ Q is the start state, Exit ∈ Q is the exit state, V is a finite set of variables, O is the set of actions, R is the set of transitions, where each transition
The existing test suite is executed on the system model and information about this execution is used to prioritize tests REF .
Regression test suite prioritization using system models
Softw. Test. Verification Reliab.
Softw. Test. Verification Reliab.
Computer Science