The Test Management Guide Software Test Guide RSS Feed
*
Accessibility

Background

BS7925-2 Annex B - Guidelines for Testing and Test Measurement

LCSAJ Testing



Annex B   
(informative)

Guidelines for Testing Techniques and Test Measurement

B.12  LCSAJ Testing

Introduction

An LCSAJ (which stands for Linear Code Sequence And Jump) is defined as a linear sequence of executable code commencing either from the start of a program or from a point to which control flow may jump and terminated either by a specific control flow jump or by the end of the program. It may contain predicates which must be satisfied in order to execute the linear code sequence and terminating jump.

Example

Some reformatting may be needed to allow LCSAJs to be expressed in terms of line numbers. The basic reformatting rule is that each branch must leave from the end of a line and arrive at the start of a line.

Consider the following program which is designed to categorise positive integers into prime and non-prime, and to give factors for those which are non-prime. Note that integer division is used, so Num DIV 2 will give a value of 2 when Num = 5, for example.  The code on line 5 calculates the remainder left after Factor is divided into Num. For example, if Factor is 5 and Num is 13, the expression evaluates to 3. For reasons of simplicity, the program makes no checks on the input.

 

            1          READ (Num);

            2          WHILE NOT End of File DO

            3                      Prime := TRUE;

            4                      FOR Factor := 2 TO Num DIV 2 DO

            5                                  IF Num - (Num DIV Factor)*Factor = 0 THEN

            6                                              WRITE (Factor, ` is a factor of', Num);

            7                                              Prime := FALSE;

            8                                  ENDIF;

            9                      ENDFOR;

            10                     IF Prime = TRUE THEN

            11                                 WRITE (Num, ` is prime');

            12                     ENDIF;

            13                     READ (Num);

            14         ENDWHILE;

            15         WRITE (`End of prime number program');

 

 

Deriving LCSAJs

To progress methodically, firstly list the table of branches as shown below. These are listed with a note of the necessary conditions to satisfy them.

(Note that our convention is to consider the transfer of control as being to the line after the line indicating the end of a control structure. An alternative is to regard control as being transferred to the end line; this would give different line numbers in the LCSAJs, but they would be essentially the same. The branching structure of loops is language dependent and may be different from that used here.)

 

(2->3)       :           requires NOT End of File

(2->15)     : Jump requires End of File

(4->5)       :           requires the loop to execute, i.e. Num DIV 2 is greater than or equal to 2

(4->10)     : Jump  requires the loop to be a zero-trip, i.e. Num DIV 2 is less than 2

(5->6)       :           requires the IF statement on line 5 to be true

(5->9)       : Jump  requires the IF statement on line 5 to be false

(9->5)       : Jump  requires a further iteration of the FOR loop to take place

(9->10)     :           requires the FOR loop to have exhausted

(10->11)   :           requires Prime to be true

(10->13)   : Jump  requires Prime to be false

(14->2)     : Jump  must always take place

 

From this list, find the LCSAJ start points. These are the start of the component (line 1) and lines to which control flow can jump from other than the preceding line (lines 2, 5, 9, 10, 13 and 15). For example, if the IF statement on line 10 is false, control will jump from line 10 to line 13.

The first LCSAJ starts at line 1. The first possible jump following line 1 is (2->15), so our first LCSAJ is (1, 2, 15).

There are other LCSAJs starting from line 1. If we had taken the (2->3) branch, we would have continued executing a linear code sequence with line 3. The next possible jump is (4->10), so our second LCSAJ is (1, 4, 10).

Again, we could have taken the (4->5) branch at this point. At line 5, there is a choice of a jump to line 9 or a branch to the next line. At line 9, there is the choice of a jump back to line 5 or a branch to the next line. At line 10, there is the choice of a jump to line 13 or a branch to the next line. The linear code sequence can extend as far as line 14, where control flow must return to line 2 to test the WHILE condition.

There are 6 LCSAJs starting from line 1. They are (1, 2, 15), (1, 4, 10), (1, 5, 9), (1, 9, 5), (1, 10, 13), and (1, 14, 2). To execute LCSAJ (1, 14, 2) requires a total of 5 branches to execute in sequence, namely (2->3), (4->5), (5->6), (9->10), (10->11) followed by the jump (14->2).

Continue the search for each LCSAJ start line. Since the outer loop will always transfer control from line 14 to line 2, there will be a set of LCSAJs which start from line 2 rather than from line 1. The reasoning for how far they go is exactly the same as for the LCSAJs starting from line 1, so the set of LCSAJs starting from line 2 is (2, 2, 15), (2, 4, 10), (2, 5, 9), (2, 9, 5), (2, 10, 13), and (2, 14, 2).

The complete set of LCSAJs are shown in the next clause. Note that the last LCSAJ is given as (15, 15, exit). We can start from line 15 because it is possible to jump to line 15 when the WHILE condition on line 2 is false. The convention is that any linear code sequence reaching the last line of the component has a `jump' to the program exit.

Test Cases

In this example, some test cases are used as a starting point.  When these tests are analysed for LCSAJ coverage, a number of LCSAJs are shown as not covered.

The initial test input consists of one prime number (5), one non-prime number (6), and a special case number (2). All numbers are input to the component at once in a single test (without ending the program and restarting it). The initial test case set is:

 

Test Case

Input

Expected Outcome

1

5

5 is prime

 

6

2 is a factor of 6

 

 

3 is a factor of 6

 

2

2 is prime

 

 

End of prime number program

 

 

LCSAJ Coverage Analysis

The LCSAJs are shown below, together with coverage achieved by the initial test. Asterisks are used to highlight those LCSAJs which have not yet been covered. LCSAJ coverage is normally measured using a software tool.

 

LCSAJ

 

START   LINE

FINISH   LINE

JUMP TO LINE

TIMES EXECUTED

1

2

15

0 ***

1

4

10

0 ***

1

5

9

1

1

9

5

0 ***

1

10

13

0 ***

1

14

2

0 ***

2

2

15

1

2

4

10

1

2

5

9

0 ***

2

9

5

1

2

10

13

0 ***

2

14

2

0 ***

5

5

9

0 ***

5

9

5

0 ***

5

10

13

1

5

14

2

0 ***

9

9

5

0 ***

9

10

13

0 ***

9

14

2

1

10

10

13

0 ***

10

14

2

1

13

14

2

1

15

15

exit

1

Number of LCSAJs

23

Number executed

9

Number not executed

14

LCSAJ Coverage

39%

 

Additional tests may now be devised to maximise the LCSAJ Coverage. These are described below.

LCSAJ         Comments

(1, 2, 15)      A new test is needed with no data, so the End of File is found immediately.

(1, 4, 10)      A new test is needed with a number less than 4 as first in the list.

(1, 9, 5)        A new test is needed with an even number greater than 5 as first in the list.

(1, 10, 13)     A new test is needed with the number 4 as first in the list.

(2, 5, 9)        This will be executed with an odd number greater than 4 which is not the first in the list.

(2, 10, 13)     This will be executed with the number 4 which is not the first in the list.

(5, 5, 9)        This will be executed by a number greater than 6.

(5, 9, 5)        This will be executed by an odd non-prime number greater than 7.

(9, 9, 5)        This will be executed by a number greater than 7.

(9, 10, 13)     This will be executed by an odd non-prime number greater than 8.

 

Infeasible LCSAJs

After executing line 7, Prime has the value false. The branch from line 10 to 11 requires Prime to be true. Hence, the following 3 LCSAJs whose linear code sequence contains at least the section from line 7 to line 11 are infeasible: (1, 14, 2), (2, 14, 2) and (5, 14, 2).

The remaining LCSAJ (10, 10, 13) is also infeasible. This LCSAJ requires Prime to be false on line 10. However, for the LCSAJ to start at line 10, it is necessary to jump from line 4 to line 10, i.e. a zero-trip loop. This implies that line 3 has been executed in the previous LCSAJ, setting Prime to true. This LCSAJ is not infeasible by itself but it is infeasible in any combination with others.

New Test Sets

Test Case

Input

Expected Output

LCSAJs executed

2

<none>

End of prime number program

(1, 2, 15)

3

2

2 is prime

(1, 4, 10)

 

4

2 is a factor of 4

(2, 10, 13)

 

 

End of prime number program

 

4

8

2 is a factor of 8

(1, 9, 5)

 

 

4 is a factor of 8

(5, 5, 9)

 

 

End of prime number program

 

5

4

2 is a factor of 4

(1, 10, 13)

 

11

11 is prime

(2, 5, 9)

 

 

 

(9, 9, 5)

 

 

 

(5, 5, 9)

 

 

 

(9, 10, 13)

 

 

End of prime number program

 

 

By running these extra tests, LCSAJ coverage is maximised with 19 of 23 LCSAJs executed, a measure of 83%.



© RuleWorks - All Rights Reserved - Policy - - Sitemap