Linear code sequence and jump

Last updated

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 structural coverage analysis.

Contents

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.[ citation needed ]

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]

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 through to where 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). 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] [ dubious ]

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]

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

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.[ citation needed ] 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:

#include<stdlib.h>#include<string.h>#include<math.h>#define MAXCOLUMNS  26#define MAXROW      20#define MAXCOUNT    90#define ITERATIONS  750intmain(void){intcount=0,totals[MAXCOLUMNS],val=0;memset(totals,0,MAXCOLUMNS*sizeof(int));count=0;while(count<ITERATIONS){val=abs(rand())%MAXCOLUMNS;totals[val]+=1;if(totals[val]>MAXCOUNT){totals[val]=MAXCOUNT;}count++;}return(0);}

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.

Related Research Articles

In computer science, code coverage is a percentage measure of the degree to which the source code of a program is executed when a particular test suite is run. A program with high test coverage has more of its source code executed during testing, which suggests it has a lower chance of containing undetected software bugs compared to a program with low test coverage. Many different metrics can be used to calculate test coverage. Some of the most basic are the percentage of program subroutines and the percentage of program statements called during execution of the test suite.

Software testing is the act of examining the artifacts and the behavior of the software under test by validation and verification. Software testing can also provide an objective, independent view of the software to allow the business to appreciate and understand the risks of software implementation. Test techniques include, but are not necessarily limited to:

In computing, an optimizing compiler is a compiler that tries to minimize or maximize some attributes of an executable computer program. Common requirements are to minimize a program's execution time, memory footprint, storage size, and power consumption.

In computer science, control flow is the order in which individual statements, instructions or function calls of an imperative program are executed or evaluated. The emphasis on explicit control flow distinguishes an imperative programming language from a declarative programming language.

In compiler construction, a basic block is a straight-line code sequence with no branches in except to the entry and no branches out except at the exit. This restricted form makes a basic block highly amenable to analysis. Compilers usually decompose programs into their basic blocks as a first step in the analysis process. Basic blocks form the vertices or nodes in a control-flow graph.

White-box testing is a method of software testing that tests internal structures or workings of an application, as opposed to its functionality. In white-box testing, an internal perspective of the system is used to design test cases. The tester chooses inputs to exercise paths through the code and determine the expected outputs. This is analogous to testing nodes in a circuit, e.g. in-circuit testing (ICT). White-box testing can be applied at the unit, integration and system levels of the software testing process. Although traditional testers tended to think of white-box testing as being done at the unit level, it is used for integration and system testing more frequently today. It can test paths within a unit, paths between units during integration, and between subsystems during a system–level test. Though this method of test design can uncover many errors or problems, it has the potential to miss unimplemented parts of the specification or missing requirements. Where white-box testing is design-driven, that is, driven exclusively by agreed specifications of how each component of software is required to behave, white-box test techniques can accomplish assessment for unimplemented or missing requirements.

Cyclomatic complexity is a software metric used to indicate the complexity of a program. It is a quantitative measure of the number of linearly independent paths through a program's source code. It was developed by Thomas J. McCabe, Sr. in 1976.

Dynamic program analysis is analysis of computer software that involves executing the program in question. Dynamic program analysis includes familiar techniques from software engineering such as unit testing, debugging, and measuring code coverage, but also includes lesser-known techniques like program slicing and invariant inference. Dynamic program analysis is widely applied in security in the form of runtime memory error detection, fuzzing, dynamic symbolic execution, and taint tracking.

<span class="mw-page-title-main">Decision-to-decision path</span>

A decision-to-decision path, or DD-path, is a path of execution between two decisions. More recent versions of the concept also include the decisions themselves in their own DD-paths.

LDRA Testbed is core static and dynamic analysis engines for both host and embedded software. LDRA Testbed is made by Liverpool Data Research Associates (LDRA). LDRA Testbed provides the means to enforce compliance with coding standards such as MISRA, JSF++ AV, CERT C, CWE and provides visibility of software flaws that might typically pass through the standard build and test process to become latent problems. In addition, test effectiveness feedback is provided through structural coverage analysis reporting facilities, which support the requirements of the DO-178B standard up to and including Level-A.

<span class="mw-page-title-main">Control table</span>

Control tables are tables that control the control flow or play a major part in program control. There are no rigid rules about the structure or content of a control table—its qualifying attribute is its ability to direct control flow in some way through "execution" by a processor or interpreter. The design of such tables is sometimes referred to as table-driven design. In some cases, control tables can be specific implementations of finite-state-machine-based automata-based programming. If there are several hierarchical levels of control table they may behave in a manner equivalent to UML state machines

Professor Michael A. Hennell is a British computer scientist who has made leading contributions in the field of software testing.

<span class="mw-page-title-main">Liverpool Data Research Associates</span> Software companies of the United Kingdom

Liverpool Data Research Associates (LDRA) is a provider of software analysis, and test and requirements traceability tools for the Public and Private sectors and a pioneer in static and dynamic software analysis.

High performance computing applications run on massively parallel supercomputers consist of concurrent programs designed using multi-threaded, multi-process models. The applications may consist of various constructs with varying degree of parallelism. Although high performance concurrent programs use similar design patterns, models and principles as that of sequential programs, unlike sequential programs, they typically demonstrate non-deterministic behavior. The probability of bugs increases with the number of interactions between the various parallel constructs. Race conditions, data races, deadlocks, missed signals and live lock are common error types.

Tcov is a source code coverage analysis and statement-by-statement profiling tool for software written in Fortran, C and C++. Tcov generates exact counts of the number of times each statement in a program is executed and annotates source code to add instrumentation. It is a standard utility, provided free of cost with Sun Studio software.

Gcov is a source code coverage analysis and statement-by-statement profiling tool. Gcov generates exact counts of the number of times each statement in a program is executed and annotates source code to add instrumentation. Gcov comes as a standard utility with the GNU Compiler Collection (GCC) suite.

<span class="mw-page-title-main">Parasoft C/C++test</span> Integrated set of tools

Parasoft C/C++test is an integrated set of tools for testing C and C++ source code that software developers use to analyze, test, find defects, and measure the quality and security of their applications. It supports software development practices that are part of development testing, including static code analysis, dynamic code analysis, unit test case generation and execution, code coverage analysis, regression testing, runtime error detection, requirements traceability, and code review. It's a commercial tool that supports operation on Linux, Windows, and Solaris platforms as well as support for on-target embedded testing and cross compilers.

Java code coverage tools are of two types: first, tools that add statements to the Java source code and require its recompilation. Second, tools that instrument the bytecode, either before or during execution. The goal is to find out which parts of the code are tested by registering the lines of code executed when running a test.

This article discusses a set of tactics useful in software testing. It is intended as a comprehensive list of tactical approaches to Software Quality Assurance (more widely colloquially known as Quality Assurance and general application of the test method.

This glossary of computer science is a list of definitions of terms and concepts used in computer science, its sub-disciplines, and related fields, including terms relevant to software, data science, and computer programming.

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