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%.
