Control flow-oriented test procedures

Relationship between different control flow graph-oriented test procedures.

The control flow-oriented test procedures , also known as coverage tests , belong to the group of structure-oriented test methods .

The control flow-oriented test procedures are based on the control flow graph of the program. These tests are white box tests , which means that the structure of the program must be known.

The individual test procedures are designated with Cx , whereby the "C" stands for "Coverage", which means the coverage or the entirety of the evaluated information.

Nomenclatures

There are several types of names that look very similar to one another, but have different meanings:

• Does the name begin with a small c → see Harry M. Sneed , Mario Winter: Testing object-oriented software. Hanser Verlag, ISBN 3-446-21820-3 .
• If the name starts with a capital C and the following number is on the baseline like the C, e.g. B. C4 → Ernest Wallmüller, "Software - Quality Assurance in Practice", Hanser Verlag.
• If the designation begins with a capital C and the following digit is a subscript, for example C ₁ , it is below the baseline → see standard DO-178B .

The IEC 61508 part 7 and its derived Annexes to EN 50128 not use abbreviations for these metrics.

The different types of tests

Line coverage tests

Even before the hierarchy of the C _x test procedures, there is the line coverage indicator provided by many tools in software development. It is a little more fuzzy than C ₀ , is not based directly on the control flow graph , but can often be obtained directly from the information that the debugger supplies anyway.

With the line coverage, the instructions are not considered, only the executable source code lines. Any number of test cases for

 if(false){print "abgedeckt?";}

would lead to a line coverage of 100%, whereas it would be for the syntactically and semantically identical but differently formatted program

 if(false){
   print "abgedeckt?";
 }

only leads to a line coverage of 50%.

As a rule, however, the differences in practical application are not relevant, as other measures in software development such as coding guidelines ("style guides") have largely homogenized the source code formatting.

advantages

• see C ₀
• Easier technical implementation using the line numbers supplied by debuggers

disadvantage

• no standard metric like C ₀
• supplies different values ​​for syntactically identical programs depending on the formatting

C ₀ . Statement coverage test

To cover the statements, it is sufficient to test all nodes (red) in the control flow graph once.

Statement coverage tests, also called C0 tests, test each statement at least once. If every instruction in a program has been executed at least once, one speaks of complete instruction coverage. If complete instruction coverage has been achieved, then it is certain that no dead code (instructions that are never executed) exists in the program.

Statement coverage tests are rarely used as the main testing tool in a completeness test because they are usually too weak for that.

Metric (measurement)

The statement coverage is determined as follows:

${\displaystyle C_{\text{0}}={\frac {\text{Anzahl der durchlaufenen Anweisungen}}{\text{Gesamtanzahl der Anweisungen}}}x100\%\,}$

advantage

The statement coverage offers the following advantages:

• it does not cover attainable instructions in the source code on
• Statement coverage can be achieved quickly compared to other coverage measures

disadvantage

However, the statement coverage should not be used as the sole test criterion, because:

• Statement coverage evaluates every statement in the source code equally
• In the case of control structures (loops, conditions, ...) the data dependencies are not taken into account and
• empty branches are not detected

Example with source code

The following source code is given:

 /* z wird das Doppelte des größeren Werts von x oder y zugewiesen */
 int z = x;
 if (y > x)
    z = y;
 z *= 2;

In this case, a single test case is sufficient to achieve complete instruction coverage, for example x = 0, y = 2. If y is not greater than x, then z = y is not executed and full instruction coverage is not achieved. In order to test all branches (if and else) once, the branch coverage should be used as a test criterion.

Example with control flow graph

The following control flow graph is given:

For this control flow graph, the instruction coverage can be achieved with a test case: {(Start, 1, 2, 3, 4, 5, Stop)}.

C ₁ . Branch Coverage Test

Branch coverage test

General

The branch coverage test (C ₁ test; also called edge coverage, decision coverage test, branch or edge coverage) includes the statement coverage test completely. Stricter criteria must be met for the C ₁ test than for the statement coverage test. In the field of control flow-oriented testing, the branch coverage test is used as a minimum criterion. With the help of the branch coverage test, program branches that cannot be executed can be tracked down. On the basis of this, software parts that are often run through can then be specifically optimized.

Analogous to the instruction coverage test, in order to make the code coverage measurable, the code in the figure below is instrumented by a Boolean auxiliary variable test.

In contrast to the statement coverage test, the branch coverage test runs through all branches. The branch coverage test is also called the decision coverage test because the auxiliary variable must be run through at least once with the values ​​true and false. In this case, the while loop must be iterated at least twice. Moving through the branches also ensures that each node (statement) is executed at least once. The criterion for the instruction coverage test is thus also met. Hence, the branch coverage test subsumes the statement coverage test. It is difficult to generate test cases for the branch coverage test where operating system states or file constellations have to be tested. Furthermore, this technique of testing is not suitable for testing 'loops' and composite decisions, since neither combinations of branches nor complex decisions can be taken into account. Extensions must be used for this.

The cyclomatic complexity indicates how many test cases are necessary at most to achieve branch coverage.

The branch coverage proves to be far more problematic. In the event that all nodes are rated equally, the interdependencies are not considered. This means that there is no linear relationship between the coverage rate achieved and the ratio between the number of test cases required for this and the actual number of test cases that are necessary for 100 percent branch coverage. To improve the branch coverage test, a branch that is dependent on another branch is no longer considered. The branches that are not dependent are said to be primitive.

Metric

Therefore the following results for the coverage:

${\displaystyle C_{\text{primitiv}}={\frac {\text{Anzahl der ausgefuehrten primitiven Zweige}}{\text{Anzahl aller primitiven Zweige}}}x100\%\,}$.

advantages

• Reveals unreachable branches
• Error detection rate around 33%. One fifth of them are calculation errors, the rest are control flow errors.

disadvantage

• Dependencies between conditions are not taken into account
• Loops are insufficiently tested; see path coverage test
• complex branching conditions are only weakly tested

Examples

The following source code is given:

 /* z wird das Doppelte des größeren Werts von x oder y zugewiesen */
 int z = x;
 if (y > x)
    z = y;
 z *= 2;

In contrast to the statement coverage test, more than one test case is now necessary to achieve 100% branch coverage, since both the case for the If branch and the case for the If branch that has not been run through must be checked:

Test case 1: x = 0, y = 2 Test case 2: x = 2, y = 0

As in the instruction coverage test, different test cases are possible that meet the required criterion. After execution, it turns out that the result in both test cases corresponds to the specification and the test has therefore been passed.

Another example:

The following control flow graph is given:

A branch coverage is {(start, 1, 2, 3, 4, 5 stop), (start, 1, 3, 5, stop)}.

C ₂ . Path Coverage Test

With the path coverage test (also C2 test or English path coverage), the possible paths from the start node to the end node are considered in the control flow graph.

Overview

• C ₂ a - full path coverage test
• C ₂ b - Boundary-Interior path coverage test
• C ₂ c - Structured path coverage test

C ₂ a - full path coverage test

All possible paths are tested. Problem: Programs with loops can have an extremely large number of paths.

C ₂ b - Boundary Interior Path Coverage Test

In principle like the C ₂ a test, only that the number of loops are now reduced to a maximum of two.

There are two groups of paths for each loop:

Boundary test

• Each loop is entered exactly once and all paths in the loop body are processed once.

Interior test

• The inside of the loop is considered to have been tested when all paths that are possible when running twice have been processed.

C ₂ c - Structured path coverage test

In principle like the C ₂ b test, only that the number of loop runs is now reduced to a given natural number n.

advantage

• High error detection rate

disadvantage

• unapproachable paths due to conditions

example

The following control flow graph is given:

A path coverage is {(start, 1, 2, 3, 4, 5 stop), (start, 1, 3, 5, stop), (start, 1, 3, 4, 5, stop), (start, 1, 2, 3, 5, stop)}.

C ₃ . Condition coverage test

Condition coverage test

The problem with the previous coverage tests (C ₁ test, C ₂ test) is that compound, hierarchical conditions are not tested sufficiently.

• C ₃ a - single condition coverage test
• C ₃ b - multiple condition coverage test
• C ₃ c - minimum multiple condition coverage test
• rating

C ₃ a - single condition coverage test

Each atomic condition of a decision must be tested once with true and once with false. Example:

boolean a,b;
if(a || b)
{
    ...
}

A minimum test case set that satisfies the simple condition coverage is {(a=false, b=false), (a=true, b=true)}.

C ₃ b - multiple condition coverage test

This test looks at all atomic conditions of a condition. If there are n atomic conditions in the condition, then combinations are formed. ${\displaystyle 2^{n}}$

For the above example this means that 4 test cases are created.

C ₃ c - minimum multiple condition coverage test

This version creates more test cases than C ₃ a and less than C ₃ b by evaluating each condition (atomic and composite) to true and false. The logical structure is taken into account and the C ₁ test (branch coverage test) is completely included in this test. Another point is that the C ₃ c test is calculable. In the above example, the test case {(a=false, b=true)}or is {(a=false, b=false)}selected, since otherwise the logical structure is terminated at the first partial condition.

advantage

• High error detection rate

disadvantage

• unapproachable paths due to conditions

rating

• Incomplete evaluation of a condition by a programming language with so-called short circuit evaluation such as C ++, C, Java, C #.

Example:

 if (a && b)
 {
     ...
 }
 else
 {
    // Lese b aus
 }

If a is false, the assignment of the variable b does not matter. For example a = false and b = null, then an error occurs in the else branch

Summary

	Short name	fulfilled condition	feasibility
Statement coverage test	C 0	each statement is executed at least once	pretty easy
Branch coverage test	C 1	every edge in the control flow graph (CFG) is run through at least once	realistic minimum requirement, reasonable effort
Path coverage test	C 2
Completely	C 2 a	All possible paths are traversed	impossible with grinding
Boundary interior	C 2 b	like C 2 a, but loops are run through according to special rules	laborious
Structured	C 2 c	like C 2 b, but loops are run through exactly n times	laborious
Condition coverage test	C 3
Single condition	C 3 a	each atomic condition is tested once with true and false
Multiple condition	C 3 b	every true / false combination of atomic conditions is tested	very high effort
Minimal multiple condition	C 3 c	each atomic condition and the overall condition is tested with true and false	high effort

rating

The quality of a test depends crucially on the test selected: If the test was only carried out according to C ₀ with 100% coverage, this is still not a reliable indicator of error-free software. If, on the other hand, the test was carried out with C ₂ to 100%, this would represent a good criterion for error-free or poor software. Unfortunately, due to the combinatorial explosion, in practice this test is only carried out for safety-critical software (e.g. aviation ).

The second important variable is the degree of coverage. However, these can only be compared with each other when using the same test. With a high degree of coverage, more errors are found than with a low one.

See also

• Control flow graph
• Software metrics
• Test coverage

literature

• Helmut Balzert: Textbook of software technology. Spektrum Verlag 2008, ISBN 978-3-8274-1161-7 .
• Andreas Spillner, Tilo Linz: Basic knowledge of software testing. dpunkt.Verlag 2005, ISBN 3-89864-358-1 .
• Harry M. Sneed, Mario Winter: Testing object-oriented software. Hanser Verlag 2002, ISBN 3-446-21820-3 .
• Ernest Wallmüller: Software quality assurance in practice. Hanser Verlag 2001, ISBN 3-446-21367-8 .

Web links

• christian-grafe.de Seminar paper on the topic (basics of this page; PDF file; 511 kB)
• christian-grafe.de PowerPoint presentation about the procedures and theoretical principles
• informatik.hu-berlin.de Prof. Dr Holger Schlingloff, Fraunhofer Ges., FIRST, "Overlaps" (PDF file; 337 kB)
• bullseye.com Steve Cornett, "Code Coverage Analysis"
• rtca.org DO-248B, Final Annual Report For Clarification Of DO-178B “Software Considerations In Airborne Systems And Equipment Certification”
• verifysoft.com (PDF; 920 kB) Professor Dr. D. Fischer: Code coverage on embedded systems