WO2004068347A1

WO2004068347A1 - Method and apparatus for categorising test scripts

Info

Publication number: WO2004068347A1
Application number: PCT/EP2003/050989
Authority: WO
Inventors: William Peter Robin Mitchell; Dominic Paul Baker; David King
Original assignee: Motorola Inc
Current assignee: Motorola Solutions Inc
Priority date: 2003-01-29
Filing date: 2003-12-11
Publication date: 2004-08-12
Anticipated expiration: 2005-07-29
Also published as: AU2003298355A1; GB2397905B; GB2397905A; GB0302013D0

Abstract

A method (200) of validating a system specification comprises the steps of generating (210) a set of events of a system specification; and generating (220) a set of test scripts relating to the system specification. The method further comprises the steps of defining (240) a number of partial orders based on a number of the set of events to obtain at least one weight for substantially each test script; and assessing (250) the at least one weight to select (270) an appropriate test script for validating whether a system implementation corresponds to the system specification. In this manner, the process provides an indication as to which tests, from a number of automatically generated tests are the best tests to perform first in validating a system specification. As such, the process identifies the parts of the system implementation that will be most error prone.

Description

Method And Apparatus For Categorising Test Scripts

Field of the Invention

This invention relates to selecting test scripts for validating system specifications. The invention is applicable to, but not limited to, validating system specifications in the form of message sequence charts. In particular, the method categorises test scripts from weights derived from a partial order, such that optimal test scripts can be selected.

Background of the Invention

In the field of this invention it is known that during system development, software tools are frequently used to automatically generate test scripts from system specifications. The test scripts are used to validate the operation of the system prior to integration of the system's components. A system specification includes system requirements that are described in some formal notation such as Message Sequence Charts (MSCs) . Other graphical notations that are often used include: Unified Modelling Language (UML) or Specification and Description Language (SDL) . Such software tools are often employed in validating telecommunication systems. In this case, a collection of individual test scripts may be considered, in combination, as representing a test specification to validate the operation of the whole telecommunication system.

By generating these test scripts, a system designer is able to simulate the functionality and operation of a practical telecommunication system. Advantageously, this enables flaws and discrepancies to be determined prior to manufacture and full system installation. A first example of a test script technique can be found in "An Industrial Use of FP: A Tool for Generating Test Scripts from System Specifications", International Conference on Functional Programming, by P. Baker, C. Jervis, D. King, in Trends in Functional Programming, 2000, ISBN 18415002400.

Such test script tools are designed to explore all possible behaviours of a system. In this regard, the tools typically produce a substantial number of tests; including both obvious and non-obvious scenarios. For example a superficially simple specification, say with an elementary MSC having only twenty-four messages, can lead to a vast number (i.e. 2,704,156) of different test scripts.

Tools such as "ptk" (a tool described in the above mentioned Baker et al. reference) may take the requirements specification in MSC form and automatically generate the complete set of test scripts that are required for system conformance testing. However, ptk is limited with regard to the total number of test scripts that it is able to generate.

A second example of a test script technique can be found in the document authored by Gerard J. Holzmann, Doron A. Peled, and Margaret H. Redberg, titled "Design Tools for Requirements Engineering", published in Bell Laboratories Technical Journal, Winter 1997. In this document, a software tool is described that allows the user to analyse requirements for racing conditions. However, this document fails to provide any significant analysis beyond this basic scenario. Three particular problems arise when large numbers of test scripts are derived from a system specification: (i) How to construct such a potentially huge number of test scripts; (ii) How to analyse such a large number of test scripts; and

(iii) How to decide which test cases are needed, since it may well be the case that many of the test scripts are either not required or are unimportant. Often, there are too many automatically generated tests to execute within the available time. Furthermore, some of the generated tests may be potentially redundant in the scope of black box testing, even though they may represent valid behaviours of the system.

With conventional test specifications comprising multiple test scripts, a significant problem emanates from system designers simulating a system's performance in SDL (ITU Recommendation Z.100, Specification and Description Language) . In this regard, the system designers have to write the code by hand. This is extremely time consuming and prone to error.

In using these notations to define system requirements, designers tend to think of the most obvious behaviours of the system first (e.g. the designers simulate the common system scenarios first) . However, depending upon the semantics of the graphical notation used, system specifications may also include non-obvious behaviours, which at first glance are not apparent to the designer when developing the specification.

A need has therefore arisen for a mechanism to detect such non-obvious behaviours in a system specification, particularly in a partially specified system, thereby alleviating the above-mentioned problems.

Summary of Invention In a first aspect, the present invention provides a method of validating a system specification, as claimed in Claim 1. In a second aspect, the present invention provides a storage medium storing processor-implementable instructions, as claimed in Claim 8. In a third aspect, the present invention provides an apparatus, as claimed in Claim 9. Further aspects of the present invention are as claimed in the dependent Claims.

The inventors of the present invention have recognised that none of the known test-script techniques address the aforementioned problems. Accordingly, the inventors have proposed a solution whereby automatically generated test scripts are categorised according to a suitable numerical weighting scheme. The weighting scheme differentiates the most obvious behaviours from the non-obvious behaviours. In doing so, the user is able to quickly assess those test scripts that represent the obvious behaviours, and consequently can concentrate on making sure that the most obvious behaviours are addressed first.

In addition, the user is able to remove those tests that are not appropriate. For example, a test script that only contains events that are sent to the system under test is generally useless for black-box testing. It is envisaged that the ability to select the most appropriate test scripts may also be used in feature interaction studies, as well as debugging of system requirements. Brief Description of the Drawings

Embodiments of the present invention will now be described, by way of example only, with reference to the accompanying drawings, in which: FIG. 1 is a flowchart showing the process for generating a conformance test suite including a partial specification in accordance with the preferred embodiment of the present invention;

FIG. 2 is a flowchart showing a method of validating a system specification by selecting the most appropriate test scripts in accordance with the preferred embodiment of the present invention;

FIG. 3 is a directed graph illustrating a movement between events; FIG. 4 illustrates a message sequence chart that highlights the benefits gained from the preferred embodiment of the present invention; and

FIG. 5 illustrates a block diagram overview of a software tool system that implements the methods according to the preferred embodiments of the present invention.

Description of Preferred Embodiments

Referring now to FIG. 1, a flowchart 100 illustrates a method for generating a conformance test suite including a partial specification, in accordance with the preferred embodiment of the present invention. A system specification, i.e. a specification of the functional requirements of a system, is often described in terms of a message sequence chart (MSC) . However, a skilled artisan would recognise that this is not the only form such a specification may take. It is envisaged that the inventive concepts described hereafter are applicable to formats and graphical notations such as: Unified Modelling Language (UML) or Specification and Description Language (SDL) .

FIG. 1 shows a flowchart of the input steps that may occur in defining a conformance test suite including when the tests comprise a partial specification. The inputs to the process include, for example, a list of: (i) Marketing requirements, 110, (ii) Existing infrastructure requirements or elements, 120, and

(iii) Existing feature requirements, 130.

Clearly, for other systems, alternative or additional requirements can be used. Singly, or in combination, the above requirements may be embellished with additional functional feature requirements in step 140 before being passed to a specification editor 150. The purpose of such a specification editor 150 is to describe a partial ordering of the events that occur when operating the system. It is then possible to regard a specification as a partial order on a set of events. Hence, the specification editor forms a partial specification with one or more additional features, in step 160. The partial specification is then used to generate a conformance test suite, as shown in step 170.

This is the context of a specification that will be used to describe the preferred embodiment of the present invention. The partial ordering describes the relative order in which the events are to occur, in practice, as specified by the functional requirements.

First, in order to define a system specification, we need to define the notation to be used. Secondly, a mechanism for assigning a weighting parameter is described where the weighting parameter is based on any arbitrary partial order. Thirdly, a mechanism describes how this technique can be applied to a particular partial order representing a requirements specification.

1. Defining the notation to be used

In accordance with the preferred embodiment of the present invention, any trace resulting from implementing the system specification will be denoted by, for example, a sequence of the form <aι, .... , a_n>. In this regard, each a is an event defined by the system specification.

The preferred embodiment of the present invention is based upon the idea of using a set of partial orders to assign weights to a resulting set of tests scripts. Test scripts are then used to check that a system implementation conforms to its corresponding specification.

2. Assigning general weights from partial orders

A relation < between pairs of elements of X is called a partial order when the following conditions hold:

(i) If x<y and y<z then x<z, e. g. x must occur before z; and

(ii) It is not the case that x<x for any x in X, e.g. x does not occur before itself.

In order to explain the preferred embodiment of the present invention, let us assume that there exists a set of events E. For each event ^λe', a partial order < (e) of E is provided. These partial orders are used to define a weight for any sequence of events. In this manner, a number of weights can be generalised to specific test scripts, as the test scripts can be described as sequences of events of the system.

First, let us define a distance function distance ( , a) , which takes an event a ^r and a number 'm' as input. The distance function returns, as an output, a set of events b' . This definition indicates those events which, according to < (a) , occur after *a' and are separated by ^Λm-1' other events occurring after 'a' . For these events b' , there exists a set of distinct events a_i, for i ranging from 0 to m' , such that: a = a_0< (a) a_K (a) . . . < (a) a_m = b [1]

Next, let us define a function d (a,b) . If events 'a' and b" occur in a sequence 's', the function defines the number of events to the right of ^Λa' that are before b' . If b' does not occur to the right of 'a' in s' , then this number is undefined.

Further, let us define n (s,a, ) to be the maximum value for d (a , b) when be distance (m, a) . It is noteworthy that jb' does not necessarily exist in all cases. In this regard, the number n may not always be defined. Given a value of *b' that is a distance ^Λm' from 'a', 'b' may occur many times in the sequence s. Hence, n(s, a, , ) defines the furthest such distance of b' from ^xa' in the sequence.

Finally, let us define n (s, a) to be the value n (s, a, m) _r where m is the first number for which n (s, a, m) is defined. Where ^Λa' is followed immediately by an event b' in the sequence, then n(s,a) is the distance from ^''a' to the furthest occurrence of ^Λb' , to the right of a' in the sequence. If there is no value of in where n (s, a , m) is defined, then n (s, a) is defined to be infinite.

In accordance with the preferred embodiment of the present invention, the weighting function w (s) of a sequence s is defined as the sum of the square of the values n (s_r a) where a ranges over the send events in s . It is noteworthy that this definition of the weighting function depends on the partial orders < (a) having been defined for each event a.

Thus, a general method of defining a weight for a sequence of events has been described above, based on a set of partial orders.

The next part of the method defines partial orders based on the visual layout given by a system requirement, the resulting weights can be used to categorise the test scripts for debugging purposes or test selection.

3. Defining partial orders based on the Visual Weight

A requirements specification, such as a Message Sequence Chart, states in what order events can occur with respect to one another. Hence, one may conclude that the requirements define a partial order (<) of the events contained within the system.

First, let us define an initial event to be any event x, where there is no event y where y<x. An initial event, in this context, can be regarded as one of the first events that could possibly happen according to the requirements specification.

Next, let us define the time step for an event x within the requirements as the maximum number of events which lie between it and any initial event. In effect, the time step of x is therefore set to one less than the length of the longest sequence: a_l< a_2 < < a_n = x, [2]

Where a_l can be any initial event.

If it is assumed that events are synchronised by some global clock, and all events commence at the first possible instance, the time step of x can be intuitively represented as a first clock tick of when x can occur. Furthermore, and notably in the context of the present invention, let us define that two events are partners if the two events have the same time step (intuitively they can occur simultaneously under the above clock scenario) .

Finally, let us define the partial orders < (a) for each event 'a', which are then used to define the weights w (s) as above for any test scripts. Here, in accordance with the preferred embodiment of the present invention, the partial order < (a) may be defined using four rules, as follows:

When the set of partners for a is not empty, let us define < (a) by:

(i) a< (a)p, for any partner p of a , (ii) p< (a) a ' for any event, where a<a ' and p is a partner of a,

(iii) x< (a) y whenever x is not a and there is a sequence of inequalities: x < a_l < a_2 < . . . < a_k < y [3]

Such that no two consecutive events are both send or receive events, i.e. they must switch from send to receive or receive to send.

When the set of partners for a is empty, let us define < (a) by: (iv) x< (a) y whenever there is a sequence of inequalities: x < a_l < a_2 < . . . < a_k < y [4]

Such that no two consecutive events are both send or receive events.

Thus, a method of using a set of partial orders to assign a weighting function to a resulting set of test scripts has been described. The weighting function is then determined according to the above set of rules .

It is within the contemplation of the present invention that the inventive concepts are not limited to four rules, nor are they limited to the above described rules. A skilled artisan will appreciate that, in general terms, the preferred method defines a number of partial orders based on a set of events to obtain at least one weight for substantially each test script. The at least one weight is then assessed in order to select an appropriate test script to be used for validating whether a system implementation corresponds to a system specification.

In particular, a skilled artisan will appreciate that the present invention proposes to generate a set of test scripts by identifying a causality of the system specification. In this regard, the step of defining a number of partial orders comprises defining an additional causality to obtain the at least one weight. In the preferred embodiment of the present invention, the step of defining an additional causality comprises identifying a number of partners for a first event, where the timing of the first event and its partner events may occur substantially concurrently.

Preferably, partner events are performed immediately after the identified first event in a test script. Furthermore, the test . script preferably alternates between a send event and a receive event when a partner relationship is not applied at a point in a test script sequence. The at least one weight is assessed by introducing a distance function to determine a maximum distance between events that can occur consecutively.

In order to appreciate the operation of the method for categorising test scripts by applying weights derived from a partial order, let us consider the following three example scenarios .

Example 1:

Let us consider a simplified sequence of events as illustrated in the directed graph 300 in FIG. 3. To arrive at event ^Λd' 320 in the sequence, the sequence can be commenced at event 'a' 305, followed by event ^λj ' 310. Alternatively, the sequence can commence at event 'c' 315 and move to event ' ' 320. It can be seen from this graph that the initial event set is {a , c) , and the time steps for each event are calculated as (a, 0) , (b, 1) , (d, 2) , and (c, 0) . From this information, it is easy to determine that only events ^,a^/ 305 and 'c' 315 have the same time step. Hence, in accordance with the preferred embodiment of the present invention, it is possible to define a ^r 305 and V 315 as partners. Given the partner information we can now define the partial orders for each event in the graph, using the rules 1-4, as detailed above:

< (a) = (a<c) , (c<b) , (c<d) [5] < (b) = (c<d) , (a<b) [6]

< (c) = (c<a) , (a<d) , (a<b) [7]

< (d) = (a<b) , (c<d) [8]

Hence, in [5] where ^Λa' and ^Λc' have been identified as partners, the event c' is modified to be performed immediately after ''a' and before 'b' and ' , following the sequence shown in FIG. 3.

Furthermore, the process from event ^λh' in [6] follows the normal ordering of events as 'b' has no partners.

Hence, in [7] where ^"'a' and ^,c' have been identified as partners, the event ^λa' is modified to be performed immediately after ^Λc' and before 'b' and ' , following the sequence shown in FIG. 3.

Furthermore, the process from event ^λd' in [8] follows the normal ordering of events as d^r has no partners.

For the above example in FIG. 3, ''a' and ^]c' are the only send events. Hence, we define the weight for a sequence ^,s' (which contains the letters a ' , b' , c^r and 'd'_r in some order) as: w (s) =n (s , a) ² + n (s, c) ². [9] For example, if we consider the sequence <a,b, c, d>. The next event from 'a' in the given sequence is ^Λb' . Using the partial ordering in [5], the maximum distance of b' from 'a' is ^Λ2' (as c' has been inserted between ^,a' and ^Λb⁷ ) . In the given sequence, the next event from c' is ' . In addition, in [7], the maximum distance of ^λd' from 'c' is ^λ2' (as ^''a' has been inserted between c' and ^Λd' ) .

Thus, applying these maximum distance calculations in equation [9] of w(s) would yield: a weighting value w(s) = 2² +2². Thereby, for this simple arrangement, a weighting of ^Λ8' is determined.

Example 2 :

As a second example, to highlight the benefits to be obtained from employing the inventive concepts herein described, let us consider the Message Sequence Chart (MSC) illustrated in FIG.3.

The dotted arrow represents a message which will be described further shortly, but which is not considered initially. A possible test behaviour represented by this example could be:

<a, d, e, b, c_r £, h_r g, i, j, 1, k>

This sequence follows the visual order of events, as shown in FIG. 3. Working out the weight for this sequence of events yields the value ^λ36' . However, if we introduce the dotted arrow into the requirements, as shown, then we can have the sequence:

Notably, this sequence has the weight '0' . The reason the weight was initially so high is that ^Λa' and h ^r were partners because they both had a zero time step, i.e. transitions commenced at these points. Whereas, in the second trace (with the dotted line) 'h' is no longer a partner of ^Λa', it now has time step ^Λ8', and ^xa' has time step 0' . Thus, this example illustrates that even though a specification appears to be obvious, that by using weights it is possible to provide the user with better information that can be used during the validation of specific system requirements.

Example 3:

As a third example, to highlight the benefits to be obtained from employing the inventive concepts herein described, let us consider the case where a designer wants to test the implementation of a system - generally referred to as the System Under Test (SUT) . In such cases, test scripts can only be used to verify the observable events - those events that can be physically monitored by the test system.

In order to monitor such events, a test script will generally send some event e' that acts as trigger for the SUT to respond with an appropriate message.

Generally, it makes no sense (and should therefore be avoided whenever possible) to have test scripts that send messages to the SUT, for which no subsequent response is received. For such test scripts sequences the aforementioned method would yield an infinite weighting because there would be no event ^, _J further down the trace. Thus, the method would yield e' < (e) ^λb' . This is a very clear signal to a designer that the test may be wrong. Namely, the test script contains a message for which it will not be able to verify the response of the SUT.

It is within the contemplation of the invention that a system designer may configure or adapt any suitable apparatus, for example a computer or processor in a computer, in order to implement the aforementioned embodiment. Alternatively, a processor may be programmed from instructions stored on a suitable storage medium, such as computer memory, hard disk, floppy disk, ROM, PROM etc, in order to implement the above process. The processor may be a computer, a network of computers, or one or more dedicated processors.

The method is intended to be included in a software tool, within a computer, whose input is a collection of MSCs. The output of the software tool is designed to be the most appropriate tests from a set of tests that are automatically generated from a system specification.

One example of such a test system 500, which includes the software tool, is illustrated in FIG. 5. The test system is preferably a telecommunication system, whose overview includes a test-ordering generator 510, operably coupled to a specification function 520. The specification function 520 is, in turn, operably coupled to a man machine interface (MMI) 530. In accordance with the preferred embodiment of the present invention, the test- ordering generator 510 has been adapted to include a function 512 that categorises test scripts by applying weights derived from a Partial order as generated in the above manner. The categorising function 512 provides an output 514 in a standard format, which could be in an MSC format, a software definable language (SDL) format, a tree and tabular combined notation (TTCN) , etc.

The specification function 520 includes the system specification 522, for example a wireless communication system specification, operably coupled to a specification editor function 524 to generate the partial specification. The specification editor function 524 receives information from, and passes information to, a machine operating system interface 526. The machine operating system interface 526 communicates with the man machine interface (MMI) 530. The MMI 530 includes a computation process 532, which accesses one or more physical memory storage devices 534 in order to obtain data to assist the aforementioned methods. The computation process 532 is also operably coupled to a visual display 536 and a user input device 538 such as a keyboard.

The examples given above are merely exemplary, and it will be appreciated that the invention may be applied to other examples of system specifications. Also, variation in the algorithms or notation are possible, in particular by using conventional finite state automaton generating options.

Advantageously, the inventors of the present invention have recognised the benefits that result from a knowledge of the more important tests in the automatic testing of a system. In this regard, the inventors propose a mechanism to identify and focus on the most appropriate system tests, of the many hundreds of tests that can be automatically generated.

Method of the invention: The inventive concepts hereinbefore described detail a method of validating a system specification. The method comprises the step of generating a set of events of a system specification and generating a set of test scripts relating to the system specification. Notably, the method also includes the steps of defining a number of partial orders based on a number of the set of events to obtain at least one weight for substantially each test script and assessing the at least one weight to select an appropriate test script for validating whether a system implementation corresponds to the system specification.

It will be understood that the methods for identifying the more appropriate tests, from a number of automatically generated test scripts as described above, provide at least one or more of the following advantages : (i) The process provides an indication as to which test scripts are the most important and therefore the best test scripts to perform first. This is in contrast to providing a random list of tests that are to be performed, some of which may be worthless.

(ii) The process identifies the parts of the system implementation that will be most error prone.

Whilst specific, and preferred, implementations of the present invention are described above, it is clear that one skilled in the art could readily apply variations and modifications of such inventive concepts.

Thus, a mechanism to identify the more appropriate test scripts from a number of automatically generated test scripts has been provided, where the disadvantages described with reference to prior art mechanisms have been substantially alleviated.

Claims

1. A method. (200) of validating a system specification, the method comprising the step of: generating (210) a set of events of a system specification; and generating (220) a set of test scripts relating to said system specification; the method characterised by the steps of: defining (240) a number of partial orders based on a number of said set of events to obtain at least one weight for substantially each test script; and assessing said at least one weight to select (270) an appropriate test script for validating whether a system implementation corresponds to said system specification.

2. The method (200) of validating a system specification according to Claim 1, wherein the step of generating a set of test scripts (220) is obtained by identifying a causality within said system specification, and said step of defining a number of partial orders (240) comprises defining an additional causality to obtain said at least one weight.

3. The method (200) of validating a system specification according to Claim 2, wherein the step of defining an additional causality comprises identifying a number of partner events for a first event (230) , where the first event and its partner events may occur substantially concurrently.

4. The method (200) of validating a system specification according to Claim 3, wherein said step of identifying comprises incorporating one or more partner events immediately after said first event.

5. The method (200) of validating a system specification according to Claim 3 or Claim 4, wherein said step of identifying comprises substantially alternating between a send event and a receive event when a partner relationship is not applied at a point in a sequence.

6. The method (200) of validating a system specification according to any preceding Claim, wherein the step of assessing said at least one weight (260) comprises introducing a distance function to determine a maximum distance between events that can occur consecutively, and assessing a weight based on said maximum distance.

7. The method (200) of validating a system specification according to any preceding claim, wherein the system is a telecommunication system.

8. A storage medium (534) storing processor-implementable instructions for controlling one or more processors to carry out the method of any of Claims 1 to 7.

9. Apparatus (500, 510), for example a computer, adapted to implement the method of any of Claims 1 to 7.