InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Optimal test suite generation subject to time and cost constraints

IP.com Disclosure Number: IPCOM000019887D
Original Publication Date: 2003-Oct-07
Included in the Prior Art Database: 2003-Oct-07
Document File: 3 page(s) / 45K

Publishing Venue



Proposed: 1. A tool that generates tests subject to cost constraints on the individual steps of the test case. 2. An algorithm and technique for generating test suites satisfying a set of coverage goals at a minimum or close to minimum cost.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 42% of the total text.

Page 1 of 3

Optimal test suite generation subject to time and cost constraints

The generation of test suites for software or hardware components is now becoming an accepted practice, and there are several commercial tools and IBM* internal tools for the generation of test suites. The input to these tools consists of

A model of the behavioral specifications of the unit (software or hardware) under

test - hereafter UUT. This model may take the form of an EFSM (extended finite state machine) or a set of message sequence charts, use cases, or other well-known formalisms for describing the behavior of software systems (e.g. SDL, StateCharts, Simulink etc.). In all cases, the model can be converted into a labelled directed graph, with nodes representing the possible states of the software, and directed arcs labelled by the stimulus that causes the software to transition from one state to another. A set of coverage goals or features (states, transitions, paths etc.) of the directed

graph that should be included in the test suite.

    One significant drawback of all the tools available is the lack of discrimination between transitions of the directed graph - which later become steps in the test cases.

    A test case is a path in the directed graph. A test suite is a set of test cases. In practical situations some transitions are much more expensive than others in terms of the resources (time, cost, additional hardware) needed to make these transitions occur in the UUT. This is particularly true of some systems which require several hours to set up a particular step in a test case. For example, a "cold start" on some machines can take more than an hour. If this fact is not factored into test generation, the resulting test suite may take so long to execute that it becomes useless.Thus minimizing the needed resources is critical.

    The invention uses the following technique to guarantee a minmum cost solution to the problem of generating a test suite of minimum cost.

    The user, when defining the artifact which models the behavior of the UUT, is required to set a transition cost TC(t) for each transition t in the model. The cost may be any non-negative number, computed as the dollar equivalent of the resources (time, hardware, inconvenience, etc.) needed to perform the transition. A setup cost SC(s) must also be assigned to any setup s required to bring the UUT to a state from which test cases may be started. - There may be more than one setup s, with varying costs (e.g. warm start, cold start, etc.).

    We also assign teardown or completion costs CC(s) to states s, which represent the cost of completing a test case, once a particular state s has been reached in a test case.

    A coverage task is a feature (state, transition, path) of the model which the tester is required to cover in some test case. A coverage task may also be given as a characterization of a set of states/transitions/paths, where the coverage goal is to ensure that at least one member of the set is in...