Niroshan Rajadurai

One of the challenges with developing software is to know when the software is at a sufficient quality such that we consider it ready to ship to our customers. The only provable way of ensuring that the our software will not contain any defects is to test it. Testing can occur at many stages, it could be unit testing, where we test a single class or source file in isolation to the rest of the system, integration testing, where we test the interaction of several units, while isolating others, or finally system testing where we test all of the software running as the final system. The challenge that software projects are faced with is to know when testing should stop. Is it sufficient to ensure every requirement has been tested?

HP conducted some research into this and discovered that testing without structural code coverage typically results in only 55% of the code being executed¹. What this means is that 45% of our software has not been executed before we ship the product to our customer! So this would indicate that measuring structural code coverage and then designing test cases to increase it's level would be useful in ensuring that the software we ship is of a higher quality than what it would be had we not used this measure.

Figure 1 - Code Coverage Flow

Structural code coverage can be broken down into many different kinds of measurements. It could be ensuring every function is executed, or every line of code, or more detailed measures of the branch decisions taken by the software. There are 3 types of structural code coverage that are typically used in applications that have some sort of safety critical requirement. These structural code coverage items are; Statement Coverage, Branch Coverage and modified condition decision coverage (MC/DC).

Statement Coverage is the measure of which executable lines of code have been executed. It does not take into consideration loops, or conditional statements. Just the statements within them. It should be noted that a statement is not the same as a line of code, in C, C++, Java or Ada typically a statement is terminated by a semicolon. In some scenarios, a single statement can span multiple lines of code. However, while Statement Coverage provides a good measure of what has and hasn't been executed in our program, it has some issues, lets take a look at the code below

By 'condition' being true, it is possible to achieve 100% code coverage. However, it misses the scenario where 'condition' is false. This program would dereference a null pointer in the later scenario. Hence we can see that while Statement Coverage is a good measure, we need to be able measure the flow of our code better.

Branch Coverage measures whether Boolean expressions tested in control structures are evaluated to both true and false. As an example for an 'if' statement, to ensure we have 100% coverage for it, both the 'true' and 'false' paths must be taken through the statement. If only one of the paths is taken, this is classed as 'partial' coverage. However, like Statement Coverage, there are some subtleties we need to be conscious of, especially when we work with languages that perform lazy evaluation. Lazy evaluation is the technique of delaying computation of a piece of code until it is needed. a typical scenario where this can occur is when we have complex Boolean expressions like the code below.

Figure 3 - Branch Coverage Defective Code Example

Consider the scenario that 'condition1' is false. Lazy evaluation would not need to evaluate 'condition2' or ' function1(*p)'. This would also result in covering the 'false' coverage path for 'if (condition1 && (condition2 || function1(*p)))'. Now lets consider the scenario that 'condition1' and 'condition2' are both 'true'. Again, lazy evaluation would result in 'function1(*p)' not being evaluated. This would also result in the 'true' coverage path being taken for the conditional above. In this case, it is possible to have 100% Branch coverage and still have potential defects in our software.

Modified condition decision coverage (MC/DC) is similar to Branch coverage and Statement coverage. It was created at Boeing and is typically required for aviation software for DO-178B Level A certification. It also measures the values of all Boolean components of a complex conditional, however it looks to address the issue raised by lazy evaluation, by requiring that every sub-condition that can affect the result of its encompassing decision is verified independent of the other sub-condition values. Looking at the example in Figure 3, we would need to verify 'condition1' for its true and false while holding 'condition2' and 'function1(*p)' fixed, then we would need to do the same, this time verifying 'condition2' for its true and false while holding 'condition1' and 'function1(*p)' fixed. finally we would do the same for 'function1(*p)', while holding 'condition1' and 'condition2' fixed. The verification of each sub-condition for its 'true' and 'false' values while holding the other sub-conditions fixed is known as an 'MC/DC pair'. An MC/DC truth table is typically used to identify pairs. An example of this can be seen in Figure 4.

Actual Expression is: ( condition1 && ( condition2 || function1 ( *p ) ) )
Condition "a" (Ca) is: condition1
Condition "b" (Cb) is: condition2
Condition "c" (Cc) is: function1 ( *p )
Simplified Expression is: ( a && ( b || c ) )
|----+----+----+----+------+----+----+----|
|Row |Ca  |Cb  |Cc  |Rslt  |Pa  |Pb  |Pc  |
|----+----+----+----+------+----+----+----|
|*1  |T   |T   |T   |T     |5   |    |    |
|----+----+----+----+------+----+----+----|
|*2  |T   |T   |F   |T     |6   |4   |    |
|----+----+----+----+------+----+----+----|
| 3  |T   |F   |T   |T     |7   |    |4   |
|----+----+----+----+------+----+----+----|
| 4  |T   |F   |F   |F     |    |2   |3   |
|----+----+----+----+------+----+----+----|
| 5  |F   |T   |T   |F     |1   |    |    |
|----+----+----+----+------+----+----+----|
| 6  |F   |T   |F   |F     |2   |    |    |
|----+----+----+----+------+----+----+----|
| 7  |F   |F   |T   |F     |3   |    |    |
|----+----+----+----+------+----+----+----|
Pa => no pair was satisfied 
   1/5 2/6 3/7
Pb => no pair was satisfied
   2/4
Pc => no pair was satisfied
   3/4