Linear code sequence and jump

Linear code sequence and jump (LCSAJ), in the broad sense, is a software analysis method used to identify structural units in code under test. Its primary use is with dynamic software analysis to help answer the question "How much testing is enough?".^[1] Dynamic software analysis is used to measure the quality and efficacy of software test data, where the quantification is performed in terms of structural units of the code under test. When used to quantify the structural units exercised by a given set of test data, dynamic analysis is also referred to as coverage analysis.

In a narrower sense, an LCSAJ is a well-defined linear region of a program's code. When used in this sense, LCSAJ is also called JJ-path, standing for jump-to-jump path.

History

The LCSAJ analysis method was devised by Professor Michael Hennell in order to perform quality assessments on the mathematical libraries on which his nuclear physics research at the University of Liverpool depended.^[2][3] Professor Hennell later founded the Liverpool Data Research Associates (LDRA) company to commercialize the software test-bed produced for this work, resulting in the LDRA Testbed product.

Introduced in 1976, the LCSAJ^[4] is now also referred to as the jump-to-jump path (JJ-path).^[5] It has also been called Liverpool's Contribution to Silly Acronyms and Jokes.

Definition and characteristics of LCSAJ as a code region

An LCSAJ is a software code path fragment consisting of a sequence of code (a linear code sequence) followed by a control flow Jump, and consists of the following three items:^[6]

• the start of the linear sequence of executable statements
• the end of the linear sequence
• the target line to which control flow is transferred at the end of the linear sequence.

Unlike (maximal) basic blocks, LCSAJs can overlap with each other because a jump (out) may occur in the middle of an LCSAJ, while it isn't allowed in the middle of a basic block. In particular, conditional jumps generate overlapping LCSAJs: one which runs thorough the test when the condition evaluates to false and another that ends at the jump when the condition evaluates to true. (The example given further below in this article illustrates such an occurrence.) Thus every basic block is an LCSAJs, but an LCSAJs may consist of more than one basic block. According to a monograph from 1986, LCSAJs were typically four times larger than basic blocks.^[7]

The formal definition of a LCSAJ can be given in terms of basic blocks as follows:^[8]

a sequence of one or more consecutively numbered basic blocks, p, (p+1), ..., q, of a code unit, followed by a control flow jump either out of the code [unit] or to a basic block numbered r, where r≠(q+1), and either p=1 or there exists a control flow jump to block p from some other block in the unit. (A basic block to which such a control flow jump can be made is referred to as a target of the [LCSAJ] jump.)

According to Jorgensen's 2013 textbook, outside Great Britain and ISTQB literature, the same notion is called DD-path.^[9]

Test effectiveness ratio

Coverage analysis metrics are used to gauge how much testing has been achieved. The most basic metric is the proportion of statements executed, Test Effectiveness Ratio 1 (TER1):^[10]

TER1 = $\frac{\text{number of statements executed by the test data}}{\text{total number of executable statements}}$

Higher level coverage metrics can also be generated, in particular:^[11]

TER2 = $\frac{\text{number of control-flow branches executed by the test data}}{\text{total number of control-flow branches}}$

TER3 = $\frac{\text{number of LCSAJs executed by the test data}}{\text{total number of LCSAJs}}$

These metrics satisfy a pure hierarchy, whereby when TER3 = 100% has been achieved it follows that TER2 = 100% and TER1 = 100% have also been achieved.

Both the TER1 & TER2 metrics were in use in the early 1970s and the third dates from the late 1970s. The requirement for achieving TER1 = 100% was the level originally selected for the DO-178 avionics standard until it was supplemented by the MCDC (modified condition/decision coverage) additional requirement in 1992.^[12] Higher levels TER3 = 100% have been mandated for many other projects, including aerospace, telephony and banking. One practical problem of using TER3 is that many LCSAJs can never be executed due to the conflicting conditions they contain.

Example

Consider the following C code:

 1 #include    <stdlib.h>
 2 #include    <string.h>
 3 #include    <math.h>
 4 
 5 #define MAXCOLUMNS  26
 6 #define MAXROW      20
 7 #define MAXCOUNT    90
 8 #define ITERATIONS  750
 9 
10 int main (void)
11 {
12     int count = 0, totals[MAXCOLUMNS], val = 0;
13 
14     memset (totals, 0, MAXCOLUMNS * sizeof(int));
15 
16     count = 0;
17     while ( count < ITERATIONS )
18     {
19         val = abs(rand()) % MAXCOLUMNS;
20         totals[val] += 1;
21         if ( totals[val] > MAXCOUNT )
22         {
23             totals[val] = MAXCOUNT;
24         }
25         count++;
26     }
27     
28     return (0);
29 
30 }

From this code, the following is a complete list of the LCSAJ triples for this code

LCSAJ Number	Start Line	Finish Line	Jump To Line
1	10	17	28
2	10	21	25
3	10	26	17
4	17	17	28
5	17	21	25
6	17	26	17
7	25	26	17
8	28	28	−1

From this example it can be seen that the basic block identified by an LCSAJ triple may span a decision point, reflecting the conditions that must be in place in order for the LCSAJ to be executed. For instance, LCSAJ 2 for the above example includes the while statement where the condition (count < ITERATIONS) evaluates to true.

Each line of code has an LCSAJ 'density' associated with it; line 17, for instance, appears within 6 unique LCSAJs - i.e. it has an LCSAJ density of 6. This is helpful when evaluating the maintainability of the code; If a line of code is to be changed then the density is indicative of how many LCSAJs will be affected by that change.

A coverage level of TER3 = 100% would be achieved when the test data used causes the execution of each of these LCSAJs at least once.

References

1. M.A.Hennell, D.Hedley and M.R.Woodward, "Quantifying the test effectiveness of Algol 68 programs", Proceedings of the Strathclyde ALGOL 68 conference 1977, pp. 36 – 41, ISSN 0362-1340
2. M. A. Hennell, An experimental testbed for numerical software. {I}. {Fortran}, The Computer Journal 21(4):333--336, @nov, 1978
3. M. A. Hennell and D. Hedley, An experimental testbed for numerical software. {II}. {ALGOL 68}, The Computer Journal 22(1):53--56, @feb, 1979
4. M.A. Hennell, M.R.Woodward and D.Hedley, "On program analysis", Information Processing Letters, 5(5), pp. 136 – 140, 1976
5. M. R. Woodward, M. A. Hennell, "On the relationship between two control-flow coverage criteria: all JJ-paths and MCDC", Information and Software Technology 48 (2006) pp. 433–440
6. M.A.Hennell, D.Hedley and I.J.Riddell, "Assessing a Class of Software Tools", Proceedings of the 7th International Conference on Software Engineering March 1984, pp. 266 – 277. ISSN 0270-5257
7. Martyn A. Ould and Charles Unwin, ed. (1986). Testing in Software Development. Cambridge University Press. p. 102. ISBN 978-0-521-33786-1.
8. Groenda, Henning (2013). Certifying Software Component Performance Specifications. KIT Scientific Publishing. pp. 198–200. ISBN 978-3-7315-0080-3. quoting from Yates, D. F. (2009). "Inclusion, subsumption, JJ-paths, and structured path testing: a Redress". Software Testing, Verification and Reliability 19 (3): 199–213. doi:10.1002/stvr.400.
9. Paul C. Jorgensen (2013). Software Testing: A Craftsman’s Approach, Fourth Edition. CRC Press. p. 136. ISBN 978-1-4665-6068-0.
10. J.R.Brown, "Practical Application of Automated Software Tools", TRW Report No. TRW-SS-72-05, presented at WESCON, 1972
11. M.R.Woodward, D.Hedley and M.A.Hennell, “Experience with Path Analysis and Testing of Programs”, IEEE Transactions on Software Engineering, Vol. 6, No. 3, pp. 278 – 286, May 1980
12. Software Considerations in Airborne System and Equipment Certification-RTCA/DO-178B, RTCA Inc., Washington D.C., December 1992