CoverageMeter
Code Coverage Measurement for C/C++

Part I
Code Coverage Overview

Chapter 1 Overview of Code Coverage Analysis provided by CoverageMeter

CoverageScanner is a C++ program that, from a practical point of view, replaces the usual compiler. It preprocesses the source code using the native preprocessor program, inserts instrumentation code and finally compiles/links the project file.
CoverageScanner instrumentation consists in:

declaring a static table that contains the result of instrumentation.
generating a library which produces an execution report upon program termination.
adding the instrumentation code itself for each relevant C/C++ statement or Boolean expression.

The compiler, linker and preprocessor used are from native environments (Example: gcc, VC6.0,...). These tools are solicited transparently and the developer only has to append ’cs’ to the compiler executable to activate the code coverage ¹. Example: ’csgcc’ instruments the source code and uses the ’gcc’ compiler to generate objects.
Another code coverage technique consists in adding measurement points according to debug information on the running time. However, instrumenting code during the generation phase makes it possible to analyses optimized code (many compilers produce unusable debug information on optimized code) and a finer analysis.
The principle code coverage analysis of CoverageScanner is not to highlight executed source lines. CoverageScanner places marks on execution paths which made the analysis independent from the source code formatting and groups all sequential instructions together in one measurement point and in so doing minimizes memory and performance loss.

1.1 Code instrumentation

1.1.1 Detection

CoverageScanner parses all C++ language and detects:

Execution paths.
Boolean expressions which produced different execution paths (if, for, while, switch…).

For example, take the following code:

   1 void foo()
   2 {
   3   found=false;
   4   for (i=0;(i<100) && ( ! found );i++)
   5   {
   6     if (i==50) break;
   7     if (i==20) found=true;
   8     if (i==30) found=true;
   9   }
  10   printf("foo\n");
  11 }
Figure 1.1: Source code sample

CoverageScanner firstly analyses the sequential statements to record each execution path. It determines which instructions need to be instrumented and places a flag which records the execution. To avoid performance problems, CoverageScanner groups all sequential instructions together and records their execution only once: before execution of the last sequential instruction.
This kind of code coverage instrumentation is usually called Statement Coverage.

In the example, the instrumented statements are underlined:

   1 void foo()
   2 {
   3   found=false;
   4   for (i=0;(i<100) && ( ! found );i++)
   5   {
   6     if (i==50) break;
   7     if (i==20) found=true;
   8     if (i==30) found=true;
   9   }
  10   printf("foo\n");
  11 }
Figure 1.2: Code coverage at branch level

In this example, lines 3 and 10 are not monitored due to the fact that lines 3, 10 and 11 are sequential operations. This doesn’t have an impact concerning coverage because if line 11 is executed then line 3 and 10 must be executed before.

Analysis of conditions determines which expressions are used in conditional statements (if, while, for, …). These statements separate the execution path into two or more portions. Code coverage monitors execution by recording if the condition was true or false during complete application execution.
This kind of code coverage instrumentation is usually called Decision Coverage.
In the example, the instrumented conditions are underlined (the instrumented statements are displayed in bold):

   1 void foo()
   2 {
   3   found=false;
   4   for (i=0;(i<100) && ( ! found );i++)
   5   {
   6     if (i==50) break;
   7     if (i==20) found=true;
   8     if (i==30) found=true;
   9   }
  10   printf("foo\n");
  11 }
Figure 1.3: Code coverage at decision level

The analysis of Boolean expressions will determine which combinations are used in Boolean operations (and, or, …) of a conditional statement (if, while, for, …). This makes it possible to have a finer analysis of why a code segment was executed.
This kind of code coverage instrumentation is usually called Condition Coverage.
For example, the statement return 0; of if (a || b) return 0; can be executed if a or b is true. Analysis of the Boolean expressions will record if variables a and b were true and false. This tells us if the statement ’return 0;’ was executed because only one of the 2 expressions were true during the test.

In the example, the instrumented Boolean expressions are underlined:

   1 void foo()
   2 {
   3   found=false;
   4   for (i=0;(i<100) && ( ! found );i++)
   5   {
   6     if (i==50) break;
   7     if (i==20) found=true;
   8     if (i==30) found=true;
   9   }
  10   printf("foo\n");
  11 }
Figure 1.4: Code coverage at condition level

1.1.2 Code insertion

After the detection phase, CoverageScanner inserts the instrumentation code itself as follows:

Sequential Statement: The statements are instrumented before their execution. The instrumentation consists in allocating a Boolean variable which detects if the code was executed or not.
Example:

   1 a=foo();
   2 a++;
   3 break;
will be changed into (The inserted code is displayed in purple):

   1 a=foo();
   2 a++;
   3 { inst[0]=1; break; }
inst[0] becomes 1 if the ’break’ statement is executed.
Conditional Statements and Boolean Expressions (full instrumentation): For Boolean expressions the same principle is used with the difference that not only the execution itself is recorded but also the state (true or false).

Example:
   1 if ( a<b )
   2   return 1;
will be changed into (The inserted code is displayed in purple):

   1 if ( (a<b) ? inst[0]=1 : inst[1]=1,0 )
   2   return 1;
inst[0] becomes 1 if the Boolean expression a<b was true.
inst[1] becomes 1 if the Boolean expression a<b was false.
Conditional Statements and Boolean Expressions (partial instrumentation): In some cases, recording if a boolean expression becomes true and false is redundant to a sequential statement instrumentation. For example, an if (b) return 0; else return 1; is completely covered by a statement coverage. In other words, recording additionally if b becomes true or false does not bring more information. Also for if (b) return 0; if is only necessary to check if b was false.
CoverageMeter suppresses per default all redundant instrumentations in order to minimize the code size and maximize the execution speed.
Example:
   1 if ( a<b )
   2   return 1;
will be changed into (The inserted code is displayed in purple):

   1 if ( a<b )
   2   return 1;
   3   else inst[0]=1 ;
inst[0] becomes 1 if the Boolean expression a<b was false. Due to the fact that the statement coverage records the instruction return 1;, it is not necessary to record if a<b was true;

Inserting the instrumentation code for the statement coverage in this example will produce the following code:

   1 char inst[5];
   2 void foo()
   3 {
   4   found=false;
   5   for (i=0;(i<100) && (! found);i++)
   6   {
   7     if (i==50 ) { inst[0]=1;break;}
   8     if (i==20 ) { inst[1]=1;found=true;}
   9     if (i==30 ) { inst[2]=1;found=true;}
  10   inst[3]=1; }
  11   printf("foo\n");
  12 inst[4]=1; }
Figure 1.5: Code coverage instrumentation at branch level

Inserting the instrumentation code for the decision coverage in this example will produce the following code:

   1 char inst[13];
   2 void foo()
   3 {
   4   found=false;
   5   for (i=0;((i<100 && ! found)?inst[0]=1:inst[1]=1,0);i++)
   6   {
   7     if ((i==50?inst[2]=1:inst[3]=1,0) ) { inst[4]=1;break;}
   8     if ((i==20?inst[5]=1:inst[6]=1,0) ) { inst[7]=1;found=true;}
   9     if ((i==30?inst[8]=1:inst[9]=1,0) ) { inst[10]=1;found=true;}
  10   inst[11]=1; }
  11   printf("foo\n");
  12 inst[12]=1; }
Figure 1.6: Code coverage instrumentation at decision level

Inserting the full instrumentation code for the condition coverage in this example will produce the following code:

   1 char inst[15];
   2 void foo()
   3 {
   4   found=false;
   5   for (i=0;((i<100)?inst[0]=1:inst[1]=1,0) && ((! found)?inst[2]=1:inst[3]=1,0);i++)
   6   {
   7     if ((i==50?inst[4]=1:inst[5]=1,0) ) { inst[6]=1;break;}
   8     if ((i==20?inst[7]=1:inst[8]=1,0) ) { inst[9]=1;found=true;}
   9     if ((i==30?inst[10]=1:inst[11]=1,0) ) { inst[12]=1;found=true;}
  10   inst[13]=1; }
  11   printf("foo\n");
  12 inst[14]=1; }
Figure 1.7: Full code coverage instrumentation at condition level

Inserting the partial instrumentation code for the condition coverage in this example will produce the following code:

   1 char inst[12];
   2 void foo()
   3 {
   4   found=false;
   5   for (i=0;((i<100)?inst[0]=1:inst[1]=1,0) && ((! found)?inst[2]=1:inst[3]=1,0);i++)
   6   {
   7     if (i==50 ) { inst[4]=1;break;} else inst[5]=1;
   8     if (i==20 ) { inst[6]=1;found=true;} else inst[7]=1;
   9     if (i==30 ) { inst[8]=1;found=true;} else inst[9]=1;
  10   inst[10]=1; }
  11   printf("foo\n");
  12 inst[11]=1; }
Figure 1.8: Partial code coverage instrumentation at condition level

1.1.3 Result of coverage analysis

CoverageBrowser is a graphical interface which analyzes the results of the instrumentation and displays:

in green, statements which are executed.
in red, statements which are not executed.
in orange, statements which are partially executed. These are Boolean expressions or conditional statements which were always true or false.

The output for the example would be:

   1 void foo()
   2 {
   3   found=false;
   4   for (i=0;(i<100) && ( ! found );i++)
   5   {
   6     if (i==50) break;
   7     if (i==20) found=true;
   8     if (i==30) found=true;
   9   }
  10   printf("foo\n");
  11 }
Figure 1.9: Code coverage output

i<100 is partially executed because i<100 was always true. i==50 and i==30 are also always false, but due to the fact that they are incorporated in an if ... then statement, it is not necessary to check if these expressions were true (here the non execution of the break; and found=true; statement are providing the same information). That’s why they are marked as fully executed.

1.2 Performance

The insertion of instrumentation increases the code size and also reduces application performance.
The additional inserted code is only a simple written operation in a fixed memory location for non-conditional expressions. The conditional expressions need more computation time due to the more detailed analysis used. Generally instrumented code is 60% to 90% bigger.
Performance loss is not very high, and in many cases a loss of only 10% to 30% in performance can be measured.

Detailed measurements are available in the Appendix (see chap. B) .

1.3 Statistics

Statistics calculated by CoverageMeter are not, usually, the number of tested source code lines compared to the overall number of source code lines. The calculation depends on the coding style adopted by the developer. That is why CoverageMeter computes statistics by calculating the number of executed instrumented instructions compared to the total number of instrumented instructions.
Each simple instrumented instruction (return, break statement, last instruction of a function, …) is recorded by one single instrumentation. A fully instrumented condition in a IF...THEN...ELSE statement uses two instrumentations: one for the true-case and one for the false-case. If partially instrumented uses only one instrumentation, the false-case or the true-case.

The statistics itself depends of the type of instrumentation. It is generally, not possible to compare a statistic value of a code coverage at branch or at decision level: having 80% coverage at decision level, does not give any information about the coverage at branch level, it can be bigger or smaller. The only certitude is that reaching a coverage of 100% is more difficult with a condition coverage than with a decision coverage and than branch coverage.
In our example, the coverage is between 60% and 75%, the following table shows the detail for each instrumentation.

Code coverage type	Instrumentations	Executed	Statistic
Branch (see figure 1.10)	5	3	60%
Decision partial (see figure 1.12)	9	7	77%
Decision full (see figure 1.11)	13	9	69%
Condition partial (see figure 1.14)	12	9	75%
Condition full (see figure 1.13)	15	10	66%

In the examples below, the detail of the calculation is displayed in subscript. The first number is the executed instrumentation and the second one the amount of instrumentations.

   1 void foo()
   2 {
   3   found=false;
   4   for (i=0;(i<100) && ( ! found );i++)
   5   {
   6     if (i==50) break;_{0/1 [not executed]}
   7     if (i==20) found=true;_{1/1 [executed]}
   8     if (i==30) found=true;_{0/1 [not executed]}
   9   }_{1/1 [executed]}
  10   printf("foo\n");
  11 }_{1/1 [executed]}
Figure 1.10: Code coverage statistic in the case of a full instrumentation at branch level

   1 void foo()
   2 {
   3   found=false;
   4   for (i=0;(i<100) && ( ! found )_{2/2 [was false and true]};i++)
   5   {
   6     if (i==50_{1/2 [was false but not true]}) break;_{0/1 [not executed]}
   7     if (i==20_{2/2 [was false and true]}) found=true;_{1/1 [executed]}
   8     if (i==30_{1/2 [was false but not true]}) found=true;_{0/1 [not executed]}
   9   }_{1/1 [executed]}
  10   printf("foo\n");
  11 }_{1/1 [executed]}
Figure 1.11: Code coverage statistic in the case of a full instrumentation at decision level

   1 void foo()
   2 {
   3   found=false;
   4   for (i=0;(i<100) && ( ! found )_{1/1 [was false]};i++)
   5   {
   6     if (i==50_{1/1 [was false]}) break;_{0/1 [not executed]}
   7     if (i==20_{1/1 [was false]}) found=true;_{1/1 [executed]}
   8     if (i==30_{1/1 [was false]}) found=true;_{0/1 [not executed]}
   9   }_{1/1 [executed]}
  10   printf("foo\n");
  11 }_{1/1 [executed]}
Figure 1.12: Code coverage statistic in the case of a partial instrumentation at decision level

   1 void foo()
   2 {
   3   found=false;
   4   for (i=0;(i<100)_{1/2 [was true but not false]} && ( ! found )_{2/2 [was false and true]};i++)
   5   {
   6     if (i==50_{1/2 [was false but not true]}) break;_{0/1 [not executed]}
   7     if (i==20_{2/2 [was false and true]}) found=true;_{1/1 [executed]}
   8     if (i==30_{1/2 [was false but not true]}) found=true;_{0/1 [not executed]}
   9   }_{1/1 [executed]}
  10   printf("foo\n");
  11 }_{1/1 [executed]}
Figure 1.13: Code coverage statistic in the case of a full instrumentation at condition level

   1 void foo()
   2 {
   3   found=false;
   4   for (i=0;(i<100)_{1/2 [was true but not false]} && ( ! found )_{2/2 [was false and true]};i++)
   5   {
   6     if (i==50_{1/1 [was false]}) break;_{0/1 [not executed]}
   7     if (i==20_{1/1 [was false]}) found=true;_{1/1 [executed]}
   8     if (i==30_{1/1 [was false]}) found=true;_{0/1 [not executed]}
   9   }_{1/1 [executed]}
  10   printf("foo\n");
  11 }_{1/1 [executed]}
Figure 1.14: Code coverage statistic in the case of a partial instrumentation at condition level

Chapter 2 Testing Methodologies

2.1 Coverage Hit vs Coverage Count

In some situations, for applications which requires a very high quality, requesting that a portion of code is executed is not enough. Two solutions are available:

Code Coverage Count: the test requirements consists of expecting that each instrumented code is executed at least a certain number of times. To do this, the instrumentation code inserted during the compilation has to count each execution¹, which has an impact on the execution performance.
Test Coverage Count: the test requirements consists of expecting that each instrumented code is executed at least by a certain number of test items. The code coverage count has the disadvantage that loops in the source receive a high count with only one execution. So setting a minimal code coverage count as goal is not always meaningful.
Setting a minimal number of test execution per each instrumented code is a way to give the same importance to loop, recursions and instructions executed only once.

2.2 Testing Strategies

CoverageMeter can be adapted to several testing strategies, from the first state of the development (unit tests) until complete product validation. CoverageBrowser permits to merge the code coverage result of each testing steps and so gives a precise overview of the global software quality.

2.2.1 Manual White Box Tests

White box testing (a.k.a. clear box testing, glass box testing or structural testing) uses an internal perspective of the system to design test cases based on internal structure. It requires programming skills to identify all paths through the software. The tester chooses test case inputs to exercise paths through the code and determines the appropriate outputs.
Definition from Wikipedia

Interactive white box tests a easy to proceed using CoverageMeter: once the application is compiled with CoverageScanner, the tester can execute it and after each execution import the execution report in CoverageBrowser.

2.2.2 Manual Black Box Tests

Black box testing takes an external perspective of the test object to derive test cases. These tests can be functional or non-functional, though usually functional. The test designer selects valid and invalid input and determines the correct output. There is no knowledge of the test object’s internal structure.
Definition from Wikipedia

Black box tests supposes that the tester doesn’t have the knowledge of the source code. It is possible to proceed exactly like for white box testing without distributing to the tester the instrumentation database (.csmes file) generated by CoverageScanner. The application under test will generate execution report which can be collected and analyzed after the testing cycle.
This method has the disadvantage that tester cannot comment and manage its own execution reports. CoverageMeter provides two different approach to enable the black box tester managing its own tests:

CoverageBrowser is able to generate an instrumentation database (.csmes file) which does not contain source code and browser information. With such database the tester can only manage the list of tests and see the statistics, but does not have access to any coverage information at source level.
A free application Execution Agent (see chap. III) permits to comment the execution report of the last executed tests without having the knowledge of the source code.

2.2.3 Unit Tests

Unit testing is a procedure used to validate that individual units of source code are working properly. A unit is the smallest testable part of an application. In procedural programming a unit may be an individual program, function, procedure etc, while in object-oriented programming, the smallest unit is always a Class; which may be a base/super class, abstract class or derived/child class.
Definition from Wikipedia

CoverageScanner permits to save the code coverage data generated by each unit test using the its library. (see chap. 24.2) As long as each source files are compiled with the save preprocessor defines, it is possible to reimport the execution reports in the instrumentation database of the real application.

2.2.4 Automatic Tests

CoverageMeter supports the possibility to add the execution name and its state directly in the execution report. No specific library is necessary and inserting this information can be performed directly by editing the execution report before and after the execution of a test item. This permits to integrate it into an automatic testing framework or in a simple script executing tests. (see chap. 24.1)

1: Command line option --cs-on of CoverageScanner.

Part I Code Coverage Overview